ir讲义2013 3 建模资料

1、信息检索模型信息检索模型检索系统的基本模式检索系统的基本模式网页网页互联网互联网匹配匹配检索结果检索结果用户需求用户需求网页采集网页采集分分析析处处理理第三讲第三讲检索模型检索模型建立索引建立索引索引库索引库信息检索模型信息检索模型模型模型 对真实的处理过程的理想化的抽象的描述。对真实的处理过程的理想化的抽象的描述。数学模型数学模型 用数学语言和数学方法来描述过程用数学语言和数学方法来描述过程 研究过程的属性、作出判断、得到结论研究过程的属性、作出判断、得到结论信息检索模型信息检索模型 是一个形式框架，该框架支持信息检索过程的所有主要阶段，包括：是一个形式框架，该框架支持信息检索过程的所有主要

2、阶段，包括： 文本表示、用户需求表示文本表示、用户需求表示 需求与文本的匹配需求与文本的匹配 检索到的文本排序检索到的文本排序信息检索模型的定义信息检索模型的定义 一个四元组：一个四元组：D, Q, F, R(qi,dj) D是文献的逻辑视图（文献的表示）是文献的逻辑视图（文献的表示） Q是用户需求的逻辑视图（查询）是用户需求的逻辑视图（查询） F是一种机制，用于构建是一种机制，用于构建D、Q和它们之间的关系和它们之间的关系 R(qi,dj)是排序函数，输出一个与查询是排序函数，输出一个与查询qi和文献表示和文献表示dj有有关的实数关的实数基本概念基本概念 文献（文献（Document） 泛指

3、各种机器可读的记录，泛指各种机器可读的记录，通常指一篇文章通常指一篇文章 特征项（特征项（Index Term） 也称为索引项、标引词等也称为索引项、标引词等 从一篇文本（查询）抽出的从一篇文本（查询）抽出的代表该文本（查询）内容的代表该文本（查询）内容的基本语言单位基本语言单位让我们高举中国特色社会让我们高举中国特色社会主义伟大旗帜，更加紧密主义伟大旗帜，更加紧密地团结在党中央周围，万地团结在党中央周围，万众一心，开拓奋进，为夺众一心，开拓奋进，为夺取全面建设小康社会新胜取全面建设小康社会新胜利、谱写人民美好生活新利、谱写人民美好生活新篇章而努力奋斗！篇章而努力奋斗！ 让、我们、高举、中国特

4、色、社会让、我们、高举、中国特色、社会主义、伟大、旗帜、更加、紧密地、主义、伟大、旗帜、更加、紧密地、团结、在、党中央、周围、团结、在、党中央、周围、万众一心、开拓、奋进、为、万众一心、开拓、奋进、为、夺取、全面、建设、小康、社会、夺取、全面、建设、小康、社会、新、胜利、谱写、人民、美好、新、胜利、谱写、人民、美好、生活、新、篇章、而、努力、奋斗生活、新、篇章、而、努力、奋斗基本概念基本概念 权重权重 不是所有的词对于表示文本内容具有同样的重要性不是所有的词对于表示文本内容具有同样的重要性 wi,j表示文本表示文本dj中的标引词中的标引词ki的权值（假设独立）的权值（假设独立） ki表示标引词

5、，表示标引词，t是系统中标引词的数目是系统中标引词的数目 K所有标引词的集合，所有标引词的集合，K=k1, k2, , kt wi,j=0 表示表示ki在在dj中没有出现中没有出现 文本文本dj可以用标引词向量来表示，可以用标引词向量来表示，dj=w1,j, w2,j, , wt,j gi(dj)返回返回t维向量维向量dj中标引词中标引词ki的权重，的权重，gi(dj)=wi,j模型的分类模型的分类 按所使用的数学方法分类按所使用的数学方法分类 基于集合论基于集合论 布尔模型布尔模型 基于线性代数基于线性代数 向量空间模型向量空间模型 基于概率论基于概率论 概率模型概率模型布尔模型（基于集合论

6、）布尔模型（基于集合论）D（文献表示）（文献表示）表示为不带权重的标引词的集合，或者说，二值的标引词权重表示为不带权重的标引词的集合，或者说，二值的标引词权重wi,j0或者或者wi,j1Q（查询）（查询）表示为标引词的布尔表达式表示为标引词的布尔表达式用用and、or、not连接标引词构成查询连接标引词构成查询F（联系机制）（联系机制）布尔表达式转换为集合表达式布尔表达式转换为集合表达式布尔算子布尔算子and（）、）、or（）、）、not（）替换为交（）替换为交（）、并（）、并（）、补（）、补（）R（排序）（排序）对于每个标引词对于每个标引词ki，得到一个文本的集合，得到一个文本的集合Dkid

7、j|wi,j=1在结果集合里的文本是相关的，其他是不相关的在结果集合里的文本是相关的，其他是不相关的布尔模型举例布尔模型举例,),(,6215363216421DDDDDDDDDDDDD1|,jijkiwdD布尔模型评价布尔模型评价 简单，定义清晰简单，定义清晰 文本或者相关或者不相关，没有强弱之分文本或者相关或者不相关，没有强弱之分 将文本分为两个集合，相关的，不相关的，将文本分为两个集合，相关的，不相关的，因此不需要排序因此不需要排序 可能会导致结果非常少或者非常多可能会导致结果非常少或者非常多布尔模型的实现布尔模型的实现输入：各种文档（输入：各种文档（PDF, DOC, TXT, HTM

8、L, XML）输出：索引表输出：索引表处理过程处理过程格式转换格式转换文档编号文档编号结构分析结构分析检索最小单元识别检索最小单元识别细结构化细结构化构建索引空间构建索引空间保存文件保存文件向量空间模型（基于线性代数）向量空间模型（基于线性代数）D（文献表示）（文献表示） 文本表示为带权重的标引词的集合，文本表示为带权重的标引词的集合，dj=w1,j, w2,j, , wt,j 权重表示该标引词与该文本的相关程度权重表示该标引词与该文本的相关程度Q（查询）（查询） 查询也表示为带权重的标引词的集合，查询也表示为带权重的标引词的集合， q=w1,q, w2,q, , wt,q 权重表示标引词与用

9、户需求的相关程度权重表示标引词与用户需求的相关程度F（联系机制）（联系机制） 文本和查询有同样的表示（文本和查询有同样的表示（ t维空间的向量）维空间的向量） 查询被当作为假想的文本查询被当作为假想的文本向量空间模型（基于线性代数）向量空间模型（基于线性代数） R（排序）（排序） 用向量夹角的余弦计算用向量夹角的余弦计算dj和和q的相似度的相似度tiqitijitiqijijjjwwwwqdqdqdsim1,21,21,),(从文本到向量空间从文本到向量空间文本的向量表示示例文本的向量表示示例夹角余弦计算举例夹角余弦计算举例常用的相似度计算方法常用的相似度计算方法特征项的权重设定特征项的权重设

10、定索引过程首先要从文献中抽取重要词，把它索引过程首先要从文献中抽取重要词，把它们映射到特征项集中，进行权重计算。们映射到特征项集中，进行权重计算。由于文献中不同词汇的出现频率随文章的内由于文献中不同词汇的出现频率随文章的内容和作者的习惯而不同，因此，最初的索引容和作者的习惯而不同，因此，最初的索引系统都是从应用词频开始的。系统都是从应用词频开始的。实际应用中显得有些粗糙实际应用中显得有些粗糙为什么中频词好？为什么中频词好？两个阈值怎么选取？两个阈值怎么选取？但是，这些思想为信息检索系统中项的选取但是，这些思想为信息检索系统中项的选取奠定了基础奠定了基础为什么中频词好为什么中频词好 简单地把所有

11、的词汇都作为文献的特征项，检索效果并不简单地把所有的词汇都作为文献的特征项，检索效果并不很好很好 不同的词汇对文献的表示作用不同不同的词汇对文献的表示作用不同 一般说来，常用词在所有文献中都有着较高的频率，区分度低一般说来，常用词在所有文献中都有着较高的频率，区分度低 罕用词在文献集中的出现次数较少，难以确定它们的统计规律，罕用词在文献集中的出现次数较少，难以确定它们的统计规律，相关度低相关度低 而中等频率的词汇常常与文献所表示的主题相关，区分度较高，而中等频率的词汇常常与文献所表示的主题相关，区分度较高，表示能力最强，最有价值。表示能力最强，最有价值。有价值的特征项有价值的特征项有价值的特征

12、项应具备以下特征：有价值的特征项应具备以下特征： 相关度相关度 与文献内容有关，以便在需要时进行索引项的检索与文献内容有关，以便在需要时进行索引项的检索 区分度区分度 能将一篇文献与其它文献区分开能将一篇文献与其它文献区分开怎么度量怎么度量 项频率项频率tf（文献内频率）（文献内频率） 反比文献频率反比文献频率idf（inverse document frequency）项频率项频率 tf 一个项的重要性随着它在文献中的出现频率的提一个项的重要性随着它在文献中的出现频率的提高而提高高而提高 我们应该采用某种依项的出现频率单调递增函数我们应该采用某种依项的出现频率单调递增函数来估算权重来估算权重

13、 项在文献中出现的次数称为项频率（项在文献中出现的次数称为项频率（term frequency, tf），根据项频率计算项的重要性的），根据项频率计算项的重要性的函数称为项频率因子，简称函数称为项频率因子，简称tf因子。因子。常用的常用的tf因子因子 原始原始tf因子：直接用项频率因子：直接用项频率tf作为作为tf因子因子 对数对数tf因子：因子：1+ln(tf) 二元二元tf因子：不考虑项频率因子：不考虑项频率tf，其值根据项是否在文献中，其值根据项是否在文献中出现为出现为1或或0（出现时为（出现时为1，否则为，否则为0）。）。 改进的改进的tf因子：因子：0.5+0.5*tf/文献中的最大

14、文献中的最大tf 大规模的测试表明，对数大规模的测试表明，对数tf因子的效果最好因子的效果最好反比文献频率反比文献频率idf 在许多篇文献中出现的项的区分度小于仅在很少几篇文献在许多篇文献中出现的项的区分度小于仅在很少几篇文献中出现的项中出现的项 这表明应该用一个依项在其中出现的文献数目单调递减函数来评这表明应该用一个依项在其中出现的文献数目单调递减函数来评估项的重要性估项的重要性 基于这个原因，人们提出反比文献频率因子，简称基于这个原因，人们提出反比文献频率因子，简称idf因因子子 一般用一般用log(N/nk)或各种变形来计算。或各种变形来计算。 其中，其中，N是文献总数，是文献总数，nk

15、是第是第k个特征项在其中出现的文献数，称个特征项在其中出现的文献数，称为项的文献频率为项的文献频率tf.idf tf.idftf.idf 示例示例tf.idf 示例示例向量空间模型评价向量空间模型评价 使用了更高级的数学工具，同样清晰使用了更高级的数学工具，同样清晰 标引词加权标引词加权 相似度有强弱之分相似度有强弱之分 可以排序可以排序 结果数量可控结果数量可控 top 10, top 20, 布尔模型布尔模型简单，定义清晰简单，定义清晰相似度没有强弱相似度没有强弱之分之分不排序不排序可能会导致结果可能会导致结果非常少或者非常非常少或者非常多多向量空间模型评价向量空间模型评价 项之间线性无关

16、的假设项之间线性无关的假设 在自然语言中，词或短语之间存在着十分密切的在自然语言中，词或短语之间存在着十分密切的联系，即存在联系，即存在“斜交斜交”现象，很难满足假定条件，现象，很难满足假定条件，对计算结果的可靠性造成一定的影响对计算结果的可靠性造成一定的影响 将复杂的语义关系，归结为简单的向量结构，丢将复杂的语义关系，归结为简单的向量结构，丢失了许多有价值的线索失了许多有价值的线索布尔模型（基于集合论）布尔模型（基于集合论）D（文献表示）（文献表示）表示为不带权重的标引词的集合，或者说，二值的标引词权重表示为不带权重的标引词的集合，或者说，二值的标引词权重wi,j0或者或者wi,j1Q（查询

17、）（查询）表示为标引词的布尔表达式表示为标引词的布尔表达式用用and、or、not连接标引词构成查询连接标引词构成查询F（联系机制）（联系机制）布尔表达式转换为集合表达式布尔表达式转换为集合表达式布尔算子布尔算子and（）、）、or（）、）、not（）替换为交（）替换为交（）、并（）、并（）、补（）、补（）R（排序）（排序）对于每个标引词对于每个标引词ki，得到一个文本的集合，得到一个文本的集合Dkidj|wi,j=1在结果集合里的文本是相关的，其他是不相关的在结果集合里的文本是相关的，其他是不相关的基本概念基本概念 文献（文献（Document） 泛指各种机器可读的记录，泛指各种机器可读的记

18、录，通常指一篇文章通常指一篇文章 特征项（特征项（Index Term） 也称为索引项、标引词等也称为索引项、标引词等 从一篇文本（查询）抽出的从一篇文本（查询）抽出的代表该文本（查询）内容的代表该文本（查询）内容的基本语言单位基本语言单位让我们高举中国特色社会让我们高举中国特色社会主义伟大旗帜，更加紧密主义伟大旗帜，更加紧密地团结在党中央周围，万地团结在党中央周围，万众一心，开拓奋进，为夺众一心，开拓奋进，为夺取全面建设小康社会新胜取全面建设小康社会新胜利、谱写人民美好生活新利、谱写人民美好生活新篇章而努力奋斗！篇章而努力奋斗！ 让、我们、高举、中国特色、社会让、我们、高举、中国特色、社会主

19、义、伟大、旗帜、更加、紧密地、主义、伟大、旗帜、更加、紧密地、团结、在、党中央、周围、团结、在、党中央、周围、万众一心、开拓、奋进、为、万众一心、开拓、奋进、为、夺取、全面、建设、小康、社会、夺取、全面、建设、小康、社会、新、胜利、谱写、人民、美好、新、胜利、谱写、人民、美好、生活、新、篇章、而、努力、奋斗生活、新、篇章、而、努力、奋斗模糊集模糊集 模糊集的运算模糊集的运算)(),(min()()(),(max()()(1)(uuuuuuuuBABABABAAA向量空间模型评价向量空间模型评价使用了更高级的数学工具，同样清晰使用了更高级的数学工具，同样清晰标引词加权标引词加权相似度有强弱之分相

20、似度有强弱之分可以排序可以排序结果数量可控结果数量可控 top 10, top 20, 标引词相互独立标引词相互独立当今最流行的检索模型当今最流行的检索模型布尔模型布尔模型简单，定义清晰简单，定义清晰相似度没有强弱相似度没有强弱之分之分不排序不排序可能会导致结果可能会导致结果非常少或者非常非常少或者非常多多独立吗？独立吗？广义向量空间模型广义向量空间模型 标引词并不独立标引词并不独立 标引词之间如何联系标引词之间如何联系 正交变换正交变换 标准正交基标准正交基从文本到向量空间从文本到向量空间多少维的向量？多少维的向量？维数急剧上升维数急剧上升 随着数据库表的记录的增大，特征值会变随着数据库表的

21、记录的增大，特征值会变得很大。对应的文档向量空间大小的维数得很大。对应的文档向量空间大小的维数会急剧上升。会急剧上升。 如：对于一个含有如：对于一个含有100个记录的表来说，其文个记录的表来说，其文档向量空间大小的维数达到档向量空间大小的维数达到1000是很正常的是很正常的 但如此大或更大维数的向量之间运算的时间复但如此大或更大维数的向量之间运算的时间复杂度会很高，直接影响查快率。杂度会很高，直接影响查快率。奇异值分解奇异值分解第一个矩阵第一个矩阵X中的每一行表示意思相关的一类词，其中的每个非零元素表示中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵最后一个矩阵Y中的每一列表示同一主题一类文章，其中每个元素表示这类中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。文章中每篇文章的相关性。中间的矩阵则表示类词和文章类之间的相关性。中间的矩阵则表示类词和文章类之间的相关性。因此，只要对关联矩阵因此，只要对关联矩阵A进行一次奇异值分解，就可以同时完成了近义词分进行一次奇异值分解，就可以同时完成了