第21章 信息检索 概述 利用项进行相关性排名 利用超链接的相关性 同义词, 多义词, 本体 文档的索引 检索有效性度量 Web抓取和索引

Presentation on theme: "第21章 信息检索 概述 利用项进行相关性排名 利用超链接的相关性 同义词, 多义词, 本体 文档的索引 检索有效性度量 Web抓取和索引"— Presentation transcript:

1 第21章 信息检索 概述 利用项进行相关性排名 利用超链接的相关性 同义词, 多义词, 本体 文档的索引 检索有效性度量 Web抓取和索引
信息检索:网页排名之外 目录与分类

2 概述 信息检索(IR)系统所用数据模型比数据库系统简单 信息被组织成文档集合 文档中包含的数据是非结构化的:没有模式
基于用户输入(如关键词或文档样例)来查找相关文档 用户用关键字来描述要检索的文档 文档与一组关键字相关联 甚至可用于带有描述性关键词的非文本数据(如视频) IR系统例 在线图书馆目录: 存储条目 在线文档管理系统: 存储报纸文章的系统 Web: 存储网页

3 概述(续) IR与数据库系统的不同之处 IR系统不处理事务更新(涉及并发控制与恢复) 数据库系统处理结构化数据, 具有定义数据组织的模式
根据关键词的搜索 根据相关度估计的检索结果排名

4 关键词搜索 文档常用一个关键词集合来描述 在全文本(full text)检索中, 文档中的所有单词都视为关键词.
IR系统利用关键词和逻辑连接词and, or, not 来形成查询表达式 And 是隐含的, 即使不显式说明 在全文本(full text)检索中, 文档中的所有单词都视为关键词. 对于非结构化文档可能没有关键字信息 用术语词项(term)来指文档中的词

5 利用词项的相关度排名 基于对查询的相关度估计进行文档排名是关键的 相关性排名基于下列因素 返回的文档数目巨大
全文检索使相关或不相关的词项具有平等地位 相关性排名基于下列因素 词项频率:关键词在文档中的出现频率 基于假设: 相关词项会在文档中多次出现 只用词频是不妥的: 文档长度? 相关性与词频是正比关系? 逆文档频率:关键词在多少文档中出现 越少  给关键词越多重要度 指向文档的超链接 指向文档的链接越多  文档越重要

6 利用词项的相关度排名(续) TF-IDF(词项频率-逆文档频率)排名: Cornell SMART系统 n(d ) = 文档d 中词项的数目
n(d, t ) = 词项t 在文档d 中的出现数目 n(t ) = 包含词项t 的文档数目 文档d 相对于词项t 的相关度 log是为了避免对频繁词项赋予过多权值 考虑了文档长度 文档d 相对于查询Q (词项集合)的相关度: 利用逆文档频率对词项加权 Cornell SMART系统

7 利用词项的相关度排名(续) 多数系统对上述模型进行了改进 出现在标题, 作者列表, 节标题等等中的词应给予较高的重要度
在文档中首次出现很晚的词应给予较低的重要度 删除极其常见的词, 如 “a”, “an”, “the”, “it” 等,它们的IDF很低 称为停止词 接近度: 若查询中的多个词项在文档中紧靠在一起出现, 该文档具有比它们远远分开出现时更高的重要度 按相关性得分递减的次序返回文档 通常只返回前面少数文档, 而非所有文档

8 基于相似度的检索 基于相似度的检索: 检索与给定文档相似的文档 相似度可以根据共同词项来定义
例如, 在d 中找出k 个具有最高r (d,t ) = TF(d, t) / n (t )的词项, 并用这些词项查询其他文档 向量空间模型: 定义一个n-维空间, 其中n 是文档集合中出现的词项总数. 表示文档d 的点: 该点的第i 个坐标是r (d,ti ) 文档d 的向量: 连接原点和表示d 的点 余弦相似度: 两个文档的向量的夹角的余弦.

9 相似度计算: 实例 与newdoc最相似的是哪个文档? doc1 doc2
text mining search engine travel map government president congress doc1 doc2 …… Sim(newdoc,doc1)=4.8* *4.5 Sim(newdoc,doc2)=2.4*2.4 Sim(newdoc,doc3)=0 text mining travel map search engine govern president congress IDF(faked) doc1 2(4.8) 1(4.5) (2.1) 1(5.4) doc2 1(2.4 ) (5.6) 1(3.3) doc (2.2) 1(3.2) (4.3) newdoc 1(2.4) 1(4.5)

10 基于相似度的检索 相关反馈: 相似度可用来精化关键词查询结果
用户从被关键词查询返回的文档中选择一些最相关的文档, 系统再找出与这些文档相似的其他文档 也可用于关键词搜索的结果 基于余弦相似度对文档聚类

11 利用超链接的相关度 早期Web搜索引擎只考虑TF-IDF: 与一个查询的关键词相关的网页数目可能是巨大的
容易造成“搜索引擎spamming” 例如一个旅游网站可在其网页中加入许多词“travel”的出现, 从而使其网页针对关键词travel的排位很高 网页具有纯文本文档所没有的重要信息:超链接 可以利用超链接来获得更好的相关度排名 网页的相关度尤其受到指向该网页的超链接的影响

12 热门度排名 热门度排名(或称威望排名)方法: 利用网站的热门程度(如: 多少人访问它)来给与查询关键词匹配的网页排名
例如,google.com是包含关键词"google"的最热门网站,应当排在最前面 与TF-IDF方法结合以得到更全面的相关度 问题: 如何定义并求出网页的热门度? 网页被访问的次数: 难以获得此数据 利用指向网页的超链接作为其热门度的测度(见后)

13 热门度度量 方法一: 利用指向一个网页的网页数目作为网页热门程度的度量
外部超链接常指向某网站的根网页, 网站内部网页可能被错误的认为是不热门的 方法二: 针对网站进行热门度度量, 而非针对每个网页 站点内的网页都有同样的热门度 但“站点”概念难以定义(URL前缀?) 很多网站包含热门度不同的涉及多个主题的网页 方法三: 威望传递 对来自本身具有高威望的网站/页的链接赋予较大权重 循环定义 建立并求解联立线性方程组 此思想来自社交网络理论(1950s提出): 定义人的威望 例如美国总统具有高威望, 因为很多人都认识他 被高威望的人所认识的人也有较高威望

14 PageRank Google搜索引擎的排名方法 思想: 网页的热门程度依赖于指向它的网页的热门程度 随机漫步模型 从一随机网页起步
以概率 跳到另一随机选择的网页, 或以概率1-  随机选择一个当前网页上的链接并跟随此链接 一个网页的PageRank就是随机漫步者在任意给定时刻访问该网页的概率 被许多网页指向的网页更可能被访问 被具有高PageRank的网页指向的网页更可能被访问 设有N个网页, 各网页的PageRank(初值定为1/N)由下式计算. 迭代计算此方程组, 直至收敛(或变化很小):

15 热门度的其他测度 PageRank算法的缺点 未考虑查询关键词. 热门度应与相关度相结合.
例如: 被具有很高PR的google.com顺便提到的词Stanford可能导致该网页被认为是与Stanford最相关的查询结果 解决方法一: 利用在锚文本中的关键词来判断所指网页的相关内容 如: <a href= University</a> 解决方法二: 只利用包含查询关键词的网页来计算热门度, 而非所有网页. 动态计算,代价高 PageRank是一次性静态计算的, 并为所有查询所重用 HITS算法利用了这个思想

16 HITS算法 利用链接信息: 若p指向q, 则说明p的作者推荐q authority: 包含某主题的实际信息的网页-- 权威
hub: 包含许多指向某主题相关网页的链接的网页 -- 枢纽 好的hub指向许多好的authority 基于所指向的authorities的威望来计算每个网页的hub威望 好的authority被许多好的hub指向 基于指向它的hub的威望来计算每个网页的authority威望 HITS算法: 先找出包含查询关键词的部分网页, 构成根集合(root set) 将根集合扩展为基集合(base set): 被根集合指向的, 指向根集合的 利用基集合计算热门度: 每个网页p都有authority权ap和hub权hp 通过求解线性方程组得到各网页的ap和hp 利用ap来对查询的返回结果进行排位输出

17 搜索引擎作弊 设计网页使之对于某些查询获得高的相关度排名,即使并非真正热门站点.
例如,旅游站点(甚至非旅游站点)希望针对关键词“旅游”获得高相关度排名, 则可在页面中多次使用"旅游"这个词,从而得到较高TF-IDF PageRank能够避免 设计一组相互指向的网页 HITS容易受到作弊行为的影响 容易建立一个指向权威网页的网页,从而得到一个较高Hub威望 该网页中再包含指向自己的网页的超链接,从而得到一个较高的Authority威望

18 同义词与多义词 同(近)义词 例: 文档: “motorcycle repair”, 查询: “motorcycle maintenance” 需要认识到“maintenance” 和 “repair”是同义词 系统能够扩展查询为 “motorcycle and (repair or maintenance)” 多义词: 指同音(通常也同形)但不同义的词 例如“object” 作为名词/ 动词具有不同意义 可从上下文来消除歧义 (一定程度上) 利用同义词来自动扩展查询可能带来问题 同义词可能有其他意义 需要理解用户想要的意义以推出同义词 或者向用户验证同义词

19 基于概念的查询 方法 对每个词, 从上下文确定其代表的概念 用概念替换词
例如: table若确定为数据库表, 则替换成table:data概念; 否则可能替换成table:furniture 本体: 反映概念间联系的层次结构 例如E-R模型中的is-a联系, 又如part-of联系 wordnet.princeton.edu, globalwordnet.org, Cyc 本体方法可用于在特定领域中对术语进行标准化 本体可以将多种语言链接在一起 语义网(Semantic Web)的基础(在此不叙)

20 文档索引 倒排索引: 将关键词Ki 映射到一个包含Ki 的文档集合 Si 文档用标识符标识 倒排索引还可以记录
关键词在文档中的位置: 以允许基于接近度的排位 关键词的TF和DF: 以允许基于TF-IDF的排位 and运算: 找出包含所有K1, K2, ..., Kn 的文档 交集, S1 S2 .....  Sn or运算: 至少包含一个K1, K2, …, Kn 的文档 并集, S1 S2 .....  Sn,. not运算: S - Si 保持每个Si 是有序的(按热门度排序)以允许通过归并实现高效的交集/并集运算 “not” 也能通过归并有序列表高效实现

21 检索效果的度量 IR系统通过使用只支持近似检索的索引结构来节省空间. 这可能导致:
误弃(false negative或false drop) – 某些相关文档未被检索到. 误选(false positive) – 某些不相关文档可能被检索到. 对许多应用来说, 一个好的索引应该不允许任何误弃, 但是可以允许一些误选(以后过滤掉). Web索引中, 误选也是不希望的, 因为过滤较慢 IR系统的性能指标: 查准率(precision) – 检索到的文档中与查询相关的文档所占百分比. 查全率(recall) – 与查询相关的文档中被检索出来的百分比. 相关的 检索到的 相关文档 全体文档

22 检索效果的度量(续) 相关度排位策略影响检索有效性测度 相关文档排位低, 则导致误弃. 不相关文档排位高, 则导致误选.
查全率与查准率的权衡: 可通过检索许多文档 (调低相关度)来增加查全率, 但是会取得许多不相关文档, 从而降低查准率. 检索有效性的度量: 将查全率作为取得的文档数目的函数来度量, 而非单一数值 将查准率作为查全率的函数来度量 等价地, 也是取得的文档数目的函数 例如 “查全率为50%时查准率为75%, 查全率为75%时查准率为60%” 问题: 如何定义哪些文档实际上是相关的, 哪些不是 创建基准测试

23 Web抓取 网络爬搜器(Web crawler): 查找并搜集Web上信息的程序 递归地跟随已知文档中的超链接, 找出其他文档
从一个种子文档集合开始 取得的文档 交给一个索引系统 索引后可以丢弃, 或保存为缓存副本 爬遍整个Web 需花费大量时间 搜索引擎通常只覆盖Web的一部分, 而非全部 执行一次爬搜可能需要数月时间

24 Web搜索引擎(续) 爬搜是由多台机器上的多个进程并行进行的 将要爬搜的链接(或站点)集合存储在数据库中 将此集合中的链接交给每个爬搜器进程
在爬搜来的网页中发现的新链接先加入这个集合, 如果不是立即爬搜则以后再爬搜 爬搜来的网页交给威望计算及索引系统 网页需要周期性地重新爬搜以便更新 威望计算及索引系统也运行在多个机器上 创建索引的新拷贝而不是修改旧索引 旧索引用来回答查询 新旧拷贝周期性地互换角色 多台机器用来回答查询 索引可保存在内存中 查询可被分配到不同机器以平衡负载

25 标准Web搜索引擎体系结构

26 信息检索:网页排名之外 查询结果多样化 信息抽取系统将文本形式的信息转换成结构化形式
例如: 从文本房产广告中抽取房屋属性(大小, 地址, 卧室个数等) 从一篇文章中抽取主题和人名 问题回答系统: 对用户问题提供直接的答案 从问题生成若干关键词查询 利用搜索引擎执行关键词查询 分析返回的文档, 找出能回答问题的文档片断 对结构化数据的关键词查询 用关系或XML来存储抽取的结构数据 查找包含关键词的元组或元素, 以及其间的连接路径 系统寻找数据间的关联来回答查询

27 目录 图书馆将相关文档存储在一起以便利浏览 用户不仅可以看到所要的文档, 还可看到相关的文档.
分类系统将逻辑上相关的文档组织在一起以便于浏览. 组织是层次式的: 分类层次

28 图书馆系统的一个分类层次

29 分类DAG 在信息检索系统中 相关文档无需存储在相近位置 但需要逻辑地组织文档, 因此也要用到类似图书馆系统的分类层次
文档无需保存在分类层次中的单一位置, 可以处于分类层次中的多个位置 因此, 分类层次是个有向无圈图 (DAG)

30 图书馆信息检索系统的分类DAG

31 Web目录 目录就是分类DAG结构 叶节点存储关于该节点主题的文档的链接 内节点也可能存储文档链接(不能划归任何子结点的文档)
课题: 目录层次应该是怎样的? 例如 Yahoo! 目录, Open Directory项目 给定一个文档, 确定哪些目录节点是与该文档相关的类别 经常是手工做的 可以基于词项相似性将文档分类到分类层次中

32 End of Chapter