PDF《信息检索与数据挖掘 2019/3/16 1》

1 2019/3/16 信息检索与数据挖掘

1 信息检索与数据挖掘 信息检索与数据挖掘 第5章 向量模型及检索系统 ――第一讲 向量模型

2 2019/3/16 信息检索与数据挖掘 课程内容 ? ? 第1章 绪论 ? 第2章 布尔检索及倒排索引 ? 第3章 词典查找及扩展的倒排索引 ? 第4章 索引构建和索引压缩 ? 第5章 向量模型及检索系统 ? 向量模型 ? 检索系统 ? 第6章 检索的评价 ? 第7章 相关反馈和查询扩展 ? 第8章 概率模型 ? 第9章 基于语言建模的检索模型 ? 第10章 文本分类 ? 第11章 文本聚类 ? 第12章Web搜索 ? 第13章 多媒体信息检索 ? 第14章 其他应用简介

3 2019/3/16 信息检索与数据挖掘 本讲提纲 ? 回顾 ? 排序式检索 ? 词项频率 ? tf-idf权重计算 ? 向量空间模型

4 2019/3/16 信息检索与数据挖掘 ? 回顾 ? 排序式检索 ? 词项频率 ? tf-idf权重计算 ? 向量空间模型 本讲提纲

5 2019/3/16 信息检索与数据挖掘 回顾:布尔检索 ? 文档表示 ? 一个文档被表示为关键词的集合 ? 查询表示 ? 查询式(Queries)被表示为关键词的布尔组合,用 与、 或、非 连接起来(主析取范式DNF ) ? 相关度计算 ? 一个文档当且仅当它能够满足布尔查询式时,才将其检 索出来 ? 检索策略是二值匹配

6 2019/3/16 信息检索与数据挖掘 回顾:倒排索引 词项词典 倒排记录表 倒排记录 Brutus Calpurnia Caesar

1 2

4 5

6 16

57 132

1 2

4 11

31 45

173 2

31 174

54 101 Dictionary Postings List

7 2019/3/16 信息检索与数据挖掘 回顾:词典的建立及扩展的倒排索 引 ?如何建立词项词典? ?文档解析:格式?语言?编码方式? ?词条化:词条(Tokens)/词项(Terms) ?停用词:停用词表?查表法 or 基于文档频率 ?词项归一化:等价类??同义词扩展表 ?词形归并:am, are, is ?be ?词干还原:去除单词两端词缀、Porter算法 ?如何实现倒排记录表? ? 跳表:跳表指针(位置、个数、更新问题) ? 短语查询 ? 二元词索引?扩展的二元词索引:词性标注 ? 位置信息索引?邻近查询 ? 混合索引机制

8 2019/3/16 信息检索与数据挖掘 回顾:索引构建 ? 基于排序的索引构建算法 ? 它是一种最原始的在内存中进行倒排的方法 ? 基于块的排序索引算法 ? 合并排序操作对于基于磁盘的排序来说很高效(避免寻道) ? 内存式单遍扫描索引构建算法 ? 没有全局的词典 ? 对每个块都生成单独的词典 ? 不对倒排记录进行排序 ? 有新的倒排记录出现时,直接在倒排记录表中增加一项 ? 采用MapReduce的分布式索引构建算法 ? 动态索引构建算法:多个索引,对数合并

9 2019/3/16 信息检索与数据挖掘 回顾:索引压缩 ? 词项的统计特性:Heaps定律和Zipf定律 ? 词典压缩 ? 将词典看成单一字符串、按块存储、前端编码 ? 倒排记录表压缩 ? 可变字节编码和γ编码 文档集(文本、XML标签等) 3,600.

0 文档集(文本) 960.0 词项关联矩阵 40,000.0 倒排记录表,未压缩(32位字) 400.0 倒排记录表,未压缩(20位) 250.0 倒排记录表,可变字节码 116.0 倒排记录表,γ编码 101.0 MB

10 2019/3/16 信息检索与数据挖掘 将整部词典看成单一字符串 回顾:索引压缩

11 2019/3/16 信息检索与数据挖掘 单一字符串方式下按块存储 回顾:索引压缩

12 2019/3/16 信息检索与数据挖掘 对间隔编码 回顾:索引压缩

13 2019/3/16 信息检索与数据挖掘 可变字节(VB)码 ?被很多商用/研究系统所采用 ?设定一个专用位 (高位) c作为延续位(continuation bit) ?如果间隔表示少于7比特,那么c 置1,将间隔编入一个 字节的后7位中 ?否则:将低7位放入当前字节中,并将c 置0,剩下的位 数采用同样的方法进行处理,最后一个字节的c置1(表示 结束) 回顾:索引压缩