信息检索和XML数据.ppt

第26章 信息检索（Information Retrieval IR）,不同：,相同： 都支持大数据集上使用索引加快查询,26.2 信息检索介绍,布尔查询-database AND（Microsoft OR IBM）用户制定一个由词和布尔操作符（and，or，not） 排序查询-用户指定一个或多个词，并且查询的结果是一系列按照查询相关度排序的文档。 将满足布尔查询条件的文档进行排序是IR搜索引擎很重要的一个方面。,26.2.1 向量空间模型,向量空间模型-将文档表示为词向量的方法。将一个文档表示为一个向量，其中每个词对应向量的一个入口，如果词j在文档i中出现k次，则文档i的文档向量在位置j上的值为k。,26.2.2 词的TF/IDF权重 （Term frequency/Inverse document frequency）,词频-文档向量中某个词的值，或者文档中该词出现的次数。 Zipfian-Zipf发现一个词在一个有相当长度的文档中的等级序号（该词按出现次数排列的词表中的位置，称之为rank，r），与该词出现的次数（frequency，f）的乘积几乎是一个常数（constant，C） r*f=C。,r*f26000左右 c*10 和该书的实际总词数260430很接近,26.2.2 词的TF/IDF权重,Zipfian(续) r*f=C说明，一个词的出现次数和它的等级序号成反比，出现次数越多，序号越小。出现次数最多的排第一，出现次数最少的排最后。它们的积是一常数。 关于r和f关系的论述被称为“Zipfs ：Law”。某种现象出现次数如果符合Zipf定律，这种现象就被认为具备Zipf分布。,26.2.2 词的TF/IDF权重,词的频率是按照zipfian分布的。 X轴的每个位置对应一个词，按照出现的次数降序排列 Y轴对应该词出现次数 停止词出现次数非常多的词，例：a,an,the。对于搜索没有很大用途，文档在预处理中被去掉这些词。,例：对于一个含有linux kernel这两个词的搜索，如果我们对含有kernel的文档比对含有linux的文档给予较高的重要性，我们就可能获得较好的结果。如何做？,26.2.2 词的TF/IDF权重,改进文档向量表示方法： Wij=tij*log(N/nj) Wij文档向量表示法的文档i的向量中词j的关联值（TF/IDF权重） tij词频 N文档的总数 nj词j出现过的文档数 IDF倒排文档频率 log(N/nj) 有效的增加了出现次数少的词的权重 例：一个有10000个文档的集， 在半数文档中出现过的词的IDF=0.3 lg2=0.3 在一个文档中出现过的词的IDF=4 lg104=4,26.2.2 词的TF/IDF权重,例：“原子能的应用” “原子能”是很专业的词 “应用”是很通用的词 词频： 2 5 每个词给一个权重： 一个词预测主题能力强，权重就越大，反之，权重越小。 停止词的权重应该是零 IDF如果一个关键词只在很少的网页中出现，我们通过它就很容易锁定搜索目标，它的权重应该大，反之，如果一个词在大量网页中出现，我们看到它仍然不清楚要找什么内容，因此，它应该小。 “原子能”log500=2.7 “的” log1=0 “应用”log2=0.3 100000/200 100000/100000 100000/50000,26.2.2 词的TF/IDF权重,长度规范化 文档D 文档D（对D加入大量新词修改） 词t的TF/IDF权重 在D和D文档向量中的值是一样的 直觉 t在D的权重应该变小 因此如果两个文档对于某一给定词含有同样的出现次数，对于 描述文档的重要性的词还依赖于文档的长度。 长度规范法：减少词的权重随着词的频率增加而增加的情况。 余弦长度规范法：,t文档集中词的个数 wij没有长度规范化的TF/IDF权重 Wij*是经过长度调整的TF/IDF权重,26.2.3文档相似性排序,将排序查询的结果中的文档进行排序。 一个排序查询本身能被看作一个文档 用文档相似性作为基础对查询结果进行排序：与查询相近的文档排在前面，不相近的排在后面 如果一个共有t个词出现在文档集中，我们可以将文档向量放在一个t维空间中，其中每个坐标对应一个词。 两个向量的紧密度的传统计算方法是他们的点乘：,26.2.3文档相似性排序,查询Q与一个文档Di的相似性： Sim(Q,Di)=,Sim（Q，D1）=（0.4*0.8）+（0.8*0.3）=0.56 Sim（Q，D2）=（0.4*0.2）+（0.8*0.7）=0.64 所以 D2查询结果中排序比D1靠前,TERM B,TERM A,26.2.3查准率和查全率,查全率和查准率是目前衡量检索效果的相对合理的指标。 查全率=（检索出的相关信息量/系统中的相关信息总量）*100% 查准率=（检索出的相关信息量/检索出的信息总量）*100% 查全率衡量检索系统检出相关信息的能力 查准率检索系统拒绝非相关信息的能力,26.2.3查准率和查全率,查全率和查准率都有局限性 查全率局限性系统中相关信息究竟有多少一般不确知，只能估计。 查准率局限性如果检索结果是题录式而非全文式，由于题录的内容简单，必须找到该题录的全文，才能正确判断出该信息是否符合检索课题的需要。 在查全率和查准率之间存在着相反的相互依赖关系如果提高查全率就会降低查准率，反之亦然。 搜索引擎系统查全率不成问题，难比较，少使用，关心查准率，即是否为用户提供相关度高的，高质量的导航信息。 提高查准率的方法：增加使用“与”“非” 提高查全的方法：增加使用“or”,26.3为文本搜索建立索引,预处理： 删去停止词，有效减少索引大小。 用词干法将相关的词转化为规范的形式，减少了要索引词的个数，可以检索不含查询词但含有查询词变体的文档。 例：run running runner的词干都是run，词干run被索引，所有这个词干的变体都被处理为run。 一个指令runner的查询将找出所有词干为run的词的文档。,26.3.1 倒排索引,倒排索引能够快速获得含有查询词的所有文档的数据结构。 倒排列表对于每一个词，索引维护一个入口列表（倒排列表）用来描述词的出现情况，其中每一个含有该词的文档占一个入口。,Docid=3,Docid=1,Docid=1,Docid=3,Docid=1,Docid=2,Docid=1,Docid=2,Docid=2,Docid=3,Docid=4,2,4,3,3,2,1,1,3,1,2,Docid=4,2,3,5,1,Docid=4,词典（内存中）,倒排列表，放置文件（磁盘上）,例：james有一个倒排列表，文档1.3.4各占一个入口 agent有一个倒排列表， 文档1.2各占一个入口， 文档1的入口列出了出现位置1和5,26.3.1 倒排索引,倒排列表词t的倒排列表中文档d所占入口记录了词t在文档D中出现的细节（例：1、词在文档中的位置的列表2、词每次出现的附加信息（是否在title中）3、文档的长度） 记录文件倒排列表的集合 词典为了为每一个查询词很快的找到倒排列表，所有查询词被组织在一个二级索引结构中（B+树，哈希索引），比记录文件小的多，每个词只需一个入口。 词典中含有预处理后的词，每个词只需一个入口， 1、该入口对应的词 2、关于其倒排列表的统计信息（倒排列表中入口个数即含该词的文档个数， 附加信息：如该词的IDF， IDF=log(N/nj) N=文档总数 Nj=词j出现过的文档数） 3、倒排列表的地址 优点：简单，高性能 缺点：很大的空间消耗，索引大小是原大小的300%,使用倒排索引, 当倒排列表很长时，讲每个词的倒排列表中的文档对于该词的相关度事先计算出来，并将倒排列表按照相关度顺序，而不是按id排序，可加快查询。但维护代价高。 对含有一个词的查询，首先查找词典获得该词的倒排列表的地址，然后获取倒排列表，其中的docid被映射到文档物理地址，这样就得到相应文档。 如果结果是需要排序的，在倒排列表中每个文档对于查询词的相关度都要计算，然后文档按相关度依次获取。 对含有多个词的查询，一次值获取一个查询次的倒排列表，然后对这些倒排列表取交集。由若干分离的词构成的查询，其结果是几个倒排列表的合并。 例： “James” 查词典找到倒排列表地址，从磁盘上获得到排列表，获得文档1、3、4 “James”AND“Bond”二个倒排列表进行交集运算，获得文档1、4 “James”or“Bond”获取二个词的倒排列表，然后以任意顺序讲这个二个列表合并。,26.3.2签名文件,签名文件-是文本数据库的另一种索引结构，能有效支持布尔查询。对于数据库中的每一个文档都有一个索引记录。 签名-这个索引记录被称为该文档的签名 签名宽度-每个签名的长度都固定为b位，b被称为签名宽度。B依赖于文档中出现的词。 我们使用哈希函数将文档中的每个词映射到位。（除非我们对于词汇表中的每一个词都使用一个位，否则，同一位会被不同的词设置多次。因哈希函数将二个词映射到了同一位。） 如果在签名S2中的所有位在S1中都被置位，我们称S1与S2相匹配。 例：S1：1101 S2：1100,26.3.2签名文件,（一）对一个同时含有若干个词的查询： 首先，通过哈希函数生成查询签名 扫描签名文件，找出所有与查询签名相匹配的文档签名 获取每一个可能的文档并检查该文档是否真的含有这个词 伪积极-一个文档签名与查询签名相匹配的文档，如果不含有查询中的所有词被称为伪积极。伪积极是一种代价昂贵的错误，因为对应的文档会被从磁盘中获取、解析、取词干、并检查其是否含有查询词。 （二）对于若干个词分离的查询 生成一个查询签名的列表，每个签名对应一个词。 扫描签名文件，找出与签名列表中任意一个签名相匹配的文档签名。,例1：查询James： 计算该词的哈希值1000 扫描签名文件，找出匹配的索引记录。1 2 3 4 获取所有文档并检查伪积极的情况；文档2伪积极,例2：查询“James”AND“Bond” 查询签名“1100” 扫描签名文件，匹配的索引记录1、2、4 文档2伪积极,例3：查询“movie”AND“Madison” 查询签名为0011 文档3匹配 无伪积极,26.3.2签名文件,26.4 Web搜索引擎,搜索引擎-Internet上专门提供查询服务的一类网站，它以一定的策略在互联网中搜索、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的作用。 搜索引擎系统：目录式搜索引擎 机器人搜索引擎 元搜索引擎,26.4 Web搜索引擎,目录式搜索引擎：加入了人的智能、信息准确、导航质量好，缺点是需要人工介入、维护量大、信息量少、信息更新不及时 机器人搜索引擎：通过网络搜索软件（网络蜘蛛，网络爬行机器人，网络搜索机器人）或网站登录等发那个是，以某种策略自动地在互联网中搜集和发现信息，经过加工处理后建库，从而对用户提出的各种查询作出响应，提供用户所需信息。该类搜索引擎的优点的信息量大、更新及时、毋须人工干预，缺点是返回信息过多，有很多无关信息，用户必须从结果中进行筛选。 例：Google、FAST、Lyws、“天网”、“百度” 元搜索引擎：这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，讲返回结果重复排除、重新排序等处理后作为自己的结果返回给用户。优点:返回信息量大、更全；缺点：不能够充分使用搜索引擎的功能，用户需做更多的筛选。WebCrawler、InfoMarket,26.4.1 搜索引擎的体系结构,以google为例： （1）爬行机器人 Crawler （2）知识库 Repository （3）索引系统 indexer （4）排序器 Sorter （5）搜索器 searcher,26.4.1 搜索引擎的体系结构,（1）网络爬行机器人（网络自动搜索软件、又称为网络蜘蛛） 功能：在互联网中漫游，发现和下载信息。尽可能多、快地搜索新信息和定期更新旧信息，避免死连接和无效连接，实现常采用分布式、并行计算技术，以提高信息发现和更新的速度。 （2）知识库：网络爬行机器人下载的网页以一定格式存储在知识库中，以便查询。 （3）索引系统：理解知识库中的信息，从中抽取索引项，生成索引表。 （4）排序器：网页是按一定顺序提供给用户的，一般每个网页有一个值，表示这个网页重要性，成为Rank值。网页按Rank值排序。计算Rank值要考虑各个方面对重要性影响。典型算法PageRank。 （5）搜索器：一般利用一个Web服务器，根据用户的查询在索引器中快速检出文档，利用排序器的结果，把查询结果提供给用户。,26.4.2 Ranking系统,评价一个搜索搜索引擎的性能，查全率和查准率。查准率更重要。 Ranking系统是影响查准率的一个重要因素。 查准率：检索出的相关信息量/检索出的信息总量。 在搜索引擎领域中，查准率一般不用所有返回结果来计算，而是取前N个，N一般取值50或100。 对一个查询请求，结果排序是根据rank值，因此ranking系统好坏影响查询的质量。,26.4.2 Ranking系统,Google如何计算文档的rank值？ 例1：单个词的查询 (1) 在词表中查找该词 每个词汇有几种不同的类型：标题、链接描述文字、URL、普通大字号文本、普通小字号文本每种类型有自己的类型权重，这些类型权重就组成一个类型权重向量。（type-weight） (2) Google计算词表中每种类型词汇的数量，再转换成词频权重向量（count-weight） (3) 计算词频权重向量和类型权重向量的标量积作为文档的IR值。 (4) IR值结合PageRank值作为文档最后rank 例2：多词查询 除了考虑词频和类型权重，还考虑到多个词汇间的相邻度。,26.4.2 Ranking系统,PageRank算法google两位创始人Sergey Brin和Larry Page建立，1998年配置进Google搜索引擎中，得出结果的准确性大大超过了其竞争对手。 （1）PageRank算法的由来 随机访问一个网页的可能性就是它的PageRank值。 一个网页有很多网页指向它，或者一些PageRank值高的（yahoo、163、sohu、sina）网页指向它，则这个网页很重要。 （2）计算PageRank值 PageRank思想-引用网页的链接数，一定程度上反映了该网页的重要性和质量。 PageRank定义： 假设T1，Tn，链接指向网页A的页面，系数d是取值范围在0和1之间的衰减因子，通常d=0.85。C（Ti）定义为网页Ti指向其它网页的链接数。网页A的PageRank值由下式指出： PR（A）=（1-d）+d（PR（T1）/C（T1）+PR（Tn）/C（Tn）,26.4.3HITS算法,HITS算法（Hypertex-Induced Topic Search）由Cornell University的Jonkleinberg博士于1998年提出的。是IBM研究项目 HITS算法思想： Web没有统一规划的结构。但其结构也有一定的规律可循。Community Community中的页面可分为两种类型： （1）表达某一主题的页面，authority （2）页面指向很多的authority，主要功能把这些authority联结在一起，称为hub,26.4.3HITS算法,HITS算法的基础-authority和hub之间相互优化的关系。 这两种页面具有不同的优势，对用户而言，具有不同的意义。 (1)如果用户需要了解一个陌生领域的研究内容，hub页面所包含的超链接、能提供丰富的信息。 (2)如果用户希望查找一个具体的概念，则authority页面的定位更加准确。 (3)因此，HITS算法为每一个页面引入二个权值：authority权值和hub权值。最后分别输出一组具有最大authority权值的页面和一组具有最大hub权值的页面。,26.4.3HITS算法,HITS算法-将web模型化为一个有向图。每个页面代表图中的一个节点，从页面A到页面B的一个超链接对应于二个节点之间的边。 计算分二步： 第一步：采样步，搜索一个称为基集的页面集合。 第二步：往复步，在基集中找出好的权威和hub页面。,26.4.3HITS算法,第一步 采样步使用传统方法获取一组含有查询词的页面。例如，我们可以将查询作为一个关键字搜索来处理，并获取含有查询词的网页。这些结果页面构成的集合为根集。 链接页-包含有指向根集中某些页的超链接，或根集中的某页有 指向它的超链接。 基 集-所有的链接页+根集 基 页-链接页+根页 第二步 目标是找出哪些页面是好hub，哪些是好权威，并将最好的hub和权威作为结果返回。 每个基页： hub权重-该页作为一个hub的质量 权威权重-该页作为一个权威的质量 某个页的权重： 如果很多好hub对某页有超链接，那么该页就是好权威 如果某页有很多指向好权威的超链接，该页就是好hub,HITS算法与PageRank算法的比较分析,显而易见，两者均是基于链接分析的搜索引擎排序算法，并且在算法中二者均利用了特征向量作为理论基础