《计算语言学讲义11上)信息检索入门（王斌）》由会员分享，可在线阅读，更多相关《计算语言学讲义11上)信息检索入门（王斌）（53页珍藏版）》请在金锄头文库上搜索。
1、信息检索入门 Introduction to Information Retrieval 中国科学院计算技术研究所 王斌 骆卫华 2006.5 内容 ?信息检索的基本概念 ?信息检索的基本流程 ?信息检索的评价方法 ?信息采集 ?信息分析及索引 ?信息检索模型及其他相似度计算方法 ?查询扩展及相关反馈 内容 ?信息检索的基本概念?信息检索的基本概念? ?信息检索的基本流程 ?信息检索的评价方法 ?信息采集 ?信息分析及索引 ?信息检索模型及其他相似度计算方法 ?查询扩展及相关反馈 查询 相关的结果 信息检索 ?Information Retrieval(IR)：从文档集合中返回满足用 户需求的
2、信息 ?例1：返回与信息检索相关的网页?搜索引擎(Search Engine, SE) ?例2：毛主席的生日是哪天？?问答系统(Question Answering, QA) ?例3：返回联想PC的型号、配置、价格等信息?信息抽取 (Information Extraction, IE) ?例4：订阅有关NBA的新闻?信息过滤(Information Filtering)、信息推荐(Information Recommending) ?狭义的IR通常是指Information Search，广义的IR包含 非常多的内容(SE, QA, IE, ) 信息检索和数据库检索 信息检索数据库检索 检索
3、对 象 检索方 式 检索语 言 无结构、半结构数据 如网页、图片 结构化数据 如：员工数据库 通常是近似检索 如：每个结果有相关度 得分 通常是精确检索 如：姓名=“李 明” 主要是自然语言 如：查与超女相关的新 闻 SQL结构化语言 近年来，两种检索已经逐渐融合，边界越来越不明显。 信息检索的基本概念 ?用户需求(Information Need，IN) ?严格地说，IN存在于用户的内心，但是通常用文字来描述， 如 查找与2006世界杯相关的新闻，通常也称为主题(Topic) ?IN提交给检索系统时称为查询(Query)，如 2006 世界杯，一 个IN可以对应多个Query ?文档(Doc
4、ument) ?可以是文本、图像、视频、语音文件等 ?文档集合(Collection) ?所有待检索的文档构成的集合 相关度(Relevance) ?相关度目前也没有统一的定义，简单地认为是查询和文档的匹配相似度 得分 ?形式上说，相关度是一个函数R，输入是查询Q、文档D和文档集合C，返 回的是一个实数值 ?R=f(Q,D,C) ?信息检索就是给定一个查询Q，从文档集合C中计算每篇文档D与Q的相关 度并排序(Ranking)。 ?相关度通常只有相对意义，对一个Q，不同文档的相关度可以比较，而 对于不同的Q的相关度不便比较 ?相关度的输入信息可以更多，比如用户的背景信息、用户的查询历史等 等 ?
5、现代信息检索中相关度不是唯一度量，如还有：重要度、权威度、新颖 度等度量。 ?Google中据说用了上百种排名因子 内容 ?信息检索的基本概念 ?信息检索的基本流程?信息检索的基本流程? ?信息检索的评价方法 ?信息采集 ?信息分析及索引 ?信息检索模型及其他相似度计算方法 ?查询扩展及相关反馈 基本流程 Internet GATHERING 流程介绍 ?信息采集(Information Gathering) ?获取信息，通常是指从Internet上获取信息 ?信息标引(Information Indexing) ?将查询和文档表示成方便检索的某种方式 ?信息标引通常也包括信息分析的组织 ?相
6、似度计算和排序(Ranking) ?相关反馈(Feedback) ?根据用户的交互重新构造查询进行检索 ?可以不通过用户自动进行，称为伪相关反馈，比如假定前5篇 文档相关 内容 ?信息检索的基本概念 ?信息检索的基本流程 ?信息检索的评价方法?信息检索的评价方法? ?信息采集 ?信息分析及索引 ?信息检索模型及其他相似度计算方法 ?查询扩展及相关反馈 评价什么？ ?效率 (Efficiency)可以采用通常的评价方法 ?标引和检索算法的速度 ?索引的更新能力 ?存储开销 ?并行或分布计算能力 ?效果 (Effectiveness) ?找到多少相关文档 ?遗漏了多少相关文档 ?找到的结果中非相关
7、文档有多少 如何评价(效果)？ ?相同的文档集合，相同的主题集合，相同的评价指 标，不同的检索系统进行比较。 ?The Cranfield Experiments, Cyril W. Cleverdon, Cranfield College of Aeronautics, 1957 1968 (hundreds of docs) ?SMART System, Gerald Salton, Cornell University, 1964- 1988 (thousands of docs,) ?TREC(Text REtrieval Conference), Donna Harman, Nati
8、onal Institute of Standards and Technology (NIST), 1992 - (millions of docs, 100k to 7.5M per set, training Qs and test Qs, 150 each) 评价指标 RR NN NR RN not retrieved not relevant retrieved not relevant retrieved relevant not retrieved relevant retrieved not retrieved not relevant relevant Doc set 评价指
9、标 ?召回率(Recall): RR/(RR + NR)，返回的相关结 果数占实际相关结果总数的比率，也称为查全 率 ?正确率(Precision): RR/(RR + RN)，返回的结 果中真正相关结果的比率，也称为查准率 ?一个例子：查询Q，本应该有100篇相关文档， 某个系统返回200篇文档，其中80篇是真正相 关的文档，Recall=80/100, Precision=80/200 ?两个指标分别度量了系统的某个方面 评价指标 ?平均正确率(Average Precision, AP)：对不同召回率点 上的正确率进行平均 ?未插值的AP: 某个查询Q共有5个相关结果，某系统排序返回 的
10、相关文档的位置分别是第1，第2，第5，第10，第20位，则 AP=(1/1+2/2+3/5+4/10+5/20)/5 ?插值的AP:在召回率分别为0,0.1,0.2,1.0的十个点上的正确 率求平均 ?MAP(Mean AP)：对所有查询求平均 ?PrecisionN：在第N个位置上的正确率，P10, P20对大规模搜索引擎非常有效 内容 ?信息检索的基本概念 ?信息检索的基本流程 ?信息检索的评价方法 ?信息采集?信息采集? ?信息分析及索引 ?信息检索模型及其他相似度计算方法 ?查询扩展及相关反馈 信息采集的概念 ?主要是指通过Web页面之间的链接关系从 Web上自动获取页面信息,并且随着
11、链接不 断向所需要的Web页面扩展的过程 ?实际上是图的遍历过程 ?通过种子页面或站点(Seed)，获取更多的链 接，将它们作为下一步种子，循环 ?这个过程永远不会结束！ 信息采集的基本结构 研究的问题 ?遍历算法： ?深度优先 vs 广度优先 ?剪枝方法 ?页面更新 ?更新周期 ?快速重复检测 ?重复URL ?重复页面 ?动态页面采集 ?工程实现：并行、吞吐率 内容 ?信息检索的基本概念 ?信息检索的基本流程 ?信息检索的评价方法 ?信息采集 ?信息分析及索引?信息分析及索引? ?信息检索模型及其他相似度计算方法 ?查询扩展及相关反馈 信息分析 ?信息分析是对原始数据的预处理 ?格式分析与转
12、换(html/xml/doc/pdf/rtf) ?语种识别、编码识别与转换 (GB/BIG5/Unicode) ?噪声数据的清洗 ?冗余数据的处理 ?信息编号 信息索引(1) ?为加快搜索速度，建立特定的数据结构 ?不可能是逐个文档扫描(太慢) ?倒排表、后缀树、签名表等等 ?大规模海量数据的索引常常用倒排表结 构 ?Inverted file ?所有的搜索引擎都用倒排表 ?速度最快 倒排索引示例 ?文档1： b d a b b c b a d c ?文档2：a b c d a c d b d a b 文档ID号 偏移位置 dictionaryPosting list 建立倒排索引的大致框架
13、分词 ?对于中文，分词的作用实际上是要找出一个个 的索引单位 ?例子：李明天天都准时上班 ?索引单位 ?字：李 明 天 天 都 准 时 上 班 ?索引量太大，查全率百分百，但是查准率低，比如查“明 天” 这句话也会出来 ?词：李明 天天 都 准时 上班 ?索引量大大降低，查准率较高，查全率不是百分百，而且 还会受分词错误的影响，比如上面可能会切分成：李 明天 天都 准时 上班 英文词根还原 ?进行词根还原： stop/stops/stopping/stopped?stop ?好处：减少词典量；坏处：按词形查不到， 词根还原还可能出现错误 ?不进行词根还原： ?Stopped?sto+ppe+d
14、 ?好处：支持词形查询；坏处：增加词典量 停用词消除 ?停用词(stop words)是指那些出现频率高 但是无重要意义，通常不会作为查询词 出现的词，如“的”、“地”、“得”、“都”、 “是”等等 ?消除：通常是通过查表的方式去除，去除的 好处-大大较少索引量，坏处-有些平时 的停用词在某些上下文可能有意义 排序 ?排序就是对分词产生的（文档号，单 词号，出现位置）三元组按照单词号 排序，单词号相同的项再按照文档号 排序，单词号和文档号都相同的再按 照出现位置排序。 ?排序是为了方便写入临时索引文件。 排序举例（1） ?文档1 ?b d a b b c b a d c ?文档2 ?a b c
15、 d a c d b d a b 排序举例（2） 对文档1分析产生的三元组如下： b d a b b c b a d c (文档号，单词号，位置） (1,b,1) (1,d,2) (1,a,3) (1,b,4) (1,b,5) (1,c,6) (1,b,7) (1,a,8) (1,d,9) (1,c,10) 排序举例（3） 对文档2分析产生的三元组如下： ?a b c d a c d b d a b (文档号，单词号，位置） (2,a,1) (2,b,2) (2,c,3) (2,d,4) (2,a,5) (2,c,6) (2,d,7) (2,b,8) (2,d,9) (2,a,10) (2,b
16、,11) 排序举例（4） (1,b,1) (1,d,2) (1,a,3) (1,b,4) (1,b,5) (1,c,6) (1,b,7) (1,a,8) (1,d,9) (1,c,10) (2,a,1) (2,b,2) (2,c,3) (2,d,4) (2,a,5) (2,c,6) (2,d,7) (2,b,8) (2,d,9) (2,a,10) (2,b,11) (1,a,3) (1,a,8) (2,a,1) (2,a,5) (2,a,10) (1,b,1) (1,b,4) (1,b,5) (1,b,7) (2,b,2) (2,b,8) (2,b,11) (1,c,6) (1,c,10) (2,c,6) (1,d,2) (1,d,9) (2,d,4) (2,d,7) (2,d,9) 写入临时索引文件 (1,a,3) (1,a,8) (2,a,1) (2,a,5) (2,a,10) (1,b,1) (1,b,4) (1,b,5) (1,b,7) (2,b,2) (2,b,8) (2,b,11) (1,c,6) (1,c,
