PDF《第十章 信息检索》

第十章 信息检索 詹卫东 2002.

7 http://icl.pku.edu.cn/doubtfire/course/CL/2001_2002_2.htm

2 提纲 ?

1 什么是信息检索(information retrieval) ?

2 信息检索的基本方法 ? 2.1 布尔模型 ? 2.2 向量空间模型 ? 2.3 概率模型 ?

3 信息检索系统的评测 ?

4 小结:信息检索的困难

3 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

4 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 system Common user oriented IR system

5 IR的需求发展 C Birth of World Wide Web

1990 C

50 million pages in November

1995 C

320 million pages in December

1997 C

800 million pages in February

1999 C

1 billion pages in

2000 C and growing every day Internet &

World Wide Web History http://www.elsop.com/wrc/h_web.htm media of information : from Hardcopy to electronic device online data -- online information service

6 IR系统的一般模式 相关反馈 检索结果 检索对查询表达式 进行分析处理 生成查询表达式 文档表示 建立索引 匹配过程 用户需求 文档

3 查询表示

1 文档索引

5 相关性反馈 relevance feedback

2 文档表示

4 匹配/检索

7 Web search的一般模式 Web Pages Documents Pool 后台工作 Spider Search Engine User Queries Index Related Pages 用户界面

8 2 信息检索的基本方法 ? 布尔模型 (Boolean Model) ? 向量空间模型(Vector Space Model) ? 概率模型 (Probabilistic Model)

9 2.1 布尔模型 查询表达式:由逻辑算子AND, OR, NOT连接若干 项目 (term)构成 e.g. 1) 飞碟 2) 飞碟 AND 美国 3) 飞碟 AND ( 中国 OR (NOT 科幻小说 )) 检索/匹配:返回1,文档符合Query要求 返回0,文档不符合Query要求 Exact Matching

10 布尔检索示例 Terms Query: 飞碟 AND 小说 地铁飞碟大学美国小说科幻……文档D1

1 1

1 1

0 0 … D2

0 1

1 1

0 1 … D3

1 0

0 1

0 0 … D4

1 1

0 0

1 1 … … Retrieval/ Matching Result: D4

11 真值表(truth table) P Q NOT P P AND Q P OR Q

0 0 TRUE FALSE FALSE

0 1 TRUE FALSE TRUE

1 0 FALSE FALSE TRUE

1 1 FALSE TRUE TRUE

12 布尔检索的优缺点 2)检索结果地位平等,无法排序 2)查询表达式易于掌握 1)不够精确,不能反映不同 项目 对一个 文档的重要程度的差异 1)简单、速度快 缺点: 优点: 飞碟 AND 小说 :只能检索出D4,无法显现D1,D2,D3的差异 飞碟 OR 小说 :可以检出D1,D2,D4,但无法显现它们的差异

13 扩展的布尔检索(extended Boolean Model) 基本思想:将非此即彼的匹配方式改为计算相似度similarity e.g. 对于Term1 OR Term2 形式的Query,相似度公式为:

2 ) ( ) , (

2 2 y x d q sim j or + = 对于Term1 AND Term2 形式的Query,相似度公式为:

2 )

1 ( )

1 (

1 ) , (

2 2 y x d q sim j and ? + ? ? = x表示Term1在文档dj中的重要程度 ∈(0,1) y表示Term2在文档dj中的重要程度 ∈(0,1)

14 扩展的布尔检索相似度计算示例

1 1 D4

0 0 D3 0.707 0.293 D2 0.707 0.293 D1 飞碟 OR 小说 飞碟 AND 小说 Query Doc Sim() x, y =