PPT《信息检索》

信息检索 张宇哈尔滨工业大学计算机科学与技术学院zhangyu@ir.

hit.edu.cn 主要内容 什么是信息检索(information retrieval) 信息检索的基本方法布尔模型向量空间模型概率模型信息检索系统的评测小结:信息检索的困难

1 什么是信息检索(IR) Document Retrieval is defined as the matching of some stated user query against useful parts of free-text records.Donna Harman et al. , 1996, Document Retrieval, in Survey of the State of the Art in Human Language Technology IR的不同情形 信息源情况不同Formatted Data ( e.g. relational database )Unformatted Data ( e.g. free text, web page, etc. )查询方式不同Query based on regular expression( e.g. SQL )Query with Natural Language ( e.g. 汉语拼音的历史情况 )查询需求不同Expert oriented IR systemCommon user oriented IR system IR的需求发展 Birth of World Wide Web

199050 million pages in November

1995320 million pages in December

1997800 million pages in February

19991 billion pages in 2000and growing every daymedia of information : from Hardcopy to electronic deviceonline data --online information service IR系统的一般模式 Web search的一般模式

2 信息检索的基本方法 布尔模型(Boolean Model)向量空间模型(Vector Space Model)概率模型(Probabilistic Model) 2.1 布尔模型 查询表达式:由逻辑算子AND, OR, NOT连接若 干 项目 (term)构成e.g. 1) 飞碟 2) 飞碟 AND 美国 3) 飞碟 AND ( 中国 OR (NOT 科幻小说 ))检索/匹配:返回1,文档符合Query要求 返回0,文档不符合Query要求 Exact Matching 布尔检索示例 真值表(truth table) TRUE TRUE FALSE

1 1 TRUE FALSE FALSE

0 1 TRUE FALSE TRUE

1 0 FALSE FALSE TRUE

0 0 P OR Q P AND Q NOT P Q P 布尔检索的优缺点 2)检索结果地位平等,无法排序 2)查询表达式易于掌握 1)不够精确,不能反映不同 项目 对一个文档的重要程度的差异 1)简单、速度快 缺点 优点 飞碟 AND 小说 :只能检索出D4,无法显现D1,D2,D3的差异 飞碟 OR 小说 :可以检出D1,D2,D4,但无法显现它们的差异 扩展的布尔检索(extended Boolean Model) 基本思想:将非此即彼的匹配方式改为计算相似度similaritye.g. 对于Term1OR Term2形式的Query,相似度公式为:对于Term1AND Term2形式的Query,相似度公式为:a x表示Term1在文档dj中的重要程度∈(0,1)y表示Term2在文档dj中的重要程度∈(0,1) 扩展的布尔检索相似度计算示例 P-norm模型 将上述只包含两个项目的查询式的相似度计算进一步拓展为包含m 个项目的查询式的相似度计算xm表示第m 个项目在文档d中的权重1≤p≤∞ p表示项目间逻辑关系严格的程度(degree of strictness),取值为1最松,取值为无穷大最严 2.2 向量空间模型 文档D和查询Q(不妨统称为文本)都可用向量表示检索过程就是计算文档向量与查询向量之间的相似度可以根据相似度值的不同,对检索结果进行排序可以根据检索结果,进一步做相关检索(relevance feedback) 从文本到向量空间(vector space) 文档的向量表示示例 假定有三个项目: 葡萄 , 美酒 , 夜光杯 假定以项目在文本中的出现次数为项目的权值

2 0

0 q

2 7

3 d2

5 3

2 d1 夜光杯T3 美酒T2 葡萄T1 计算向量之间的相似程度 向量间相似程度的不同度量方法Inner productDice coefficientCosine coefficientJaccard coefficient 在上面的例子中,如何度量q跟d1相似还是跟d2相似? 夹角余弦:相似程度的度量方法之一 夹角余弦计算示例 索引项权值的计算(term weight) 权值的直观含义:一个项目对于一个文本的重要程度即一个项目在多大程度上可以将这个文档与其他文档区别开计算权值的两种简单方式:(1)项目-出现/不出现:1或0(2)项目-出现的次数:0,1,2,…需要更好的加权方法(3)tf.idf加权法(term frequency ?inverse document frequency)项频率 逆向文档频率 tf.idf 加权 Term frequency:termi 在文档dj中的出现次数,记做tfi,j tfi,j 越高,意味着termi 对于文档dj 就越重要比如:一篇谈论乔丹的文章,可以预期 乔丹 、 飞人 的tf值会比较高Document frequency:含有termi 的文档的数量,记做dfidfi 越高,意味着termi 在衡量文档之间相似性方面作用越低,比如 的 的df值肯定非常高,因此不具有区别性,这类词称为 非焦点词 Inverse document frequency:跟dfi 形成 反比关系 ,idfi 值越高,意味着termi对于文档的区别意义越大N为全部文档的数量.如果一个项目仅出现在一个文档中,idf=logN,如果一个项目出现在所有文档中,idf= log1 =