信息检索模型与搜索引擎排序算法

《信息检索模型与搜索引擎排序算法》由会员分享，可在线阅读，更多相关《信息检索模型与搜索引擎排序算法（44页珍藏版）》请在装配图网上搜索。

1、信息检索与搜索引擎排序算法信息检索与搜索引擎排序算法 -徐艳霞主要内容主要内容 1 信息检索模型介绍信息检索模型介绍 2 搜索引擎典型排序算法介绍搜索引擎典型排序算法介绍 3 适用于数学公式搜索引擎排序算法探讨适用于数学公式搜索引擎排序算法探讨搜索引擎排序标准如果我牙疼，应该去看怎样的医生呢？假设我只有三种选择：如果我牙疼，应该去看怎样的医生呢？假设我只有三种选择：A医生，既治眼病，又治胃病；医生，既治眼病，又治胃病；B医生，既治牙病，又治胃病，还治眼病；医生，既治牙病，又治胃病，还治眼病；C医生，专治牙病医生，专治牙病。假如再加一个条件：假如再加一个条件：B医生经验丰富，有二十年从医经历，医

2、术高明，医生经验丰富，有二十年从医经历，医术高明，而而C医生只有五年从医经验。医生只有五年从医经验。结论：结论：择医需要考虑两个条件，择医需要考虑两个条件，1：医生的专长与病情的适配程度：医生的专长与病情的适配程度 2：医生的医术医生的医术 网页内容与用户查询的匹配程度网页内容与用户查询的匹配程度 搜索引擎排序搜索引擎排序 网页本身的质量网页本身的质量 目录 1.1 信息检索模型的定义信息检索模型的定义 1.2 布尔模型布尔模型 1.3 向量空间模型向量空间模型 1.4 概率模型概率模型 1.5 典型的搜索引擎排序算法典型的搜索引擎排序算法 1.6 适用于数学公式搜索引擎排序算法的适用于数学公

3、式搜索引擎排序算法的探探 讨讨信息检索模型信息检索模型 1 信息检索模型的定义信息检索模型的定义 什么是数学模型？什么是数学模型？为了某种特定目的，通过对现实世界的某一特定对象做出为了某种特定目的，通过对现实世界的某一特定对象做出一些必要的简化与设，运用适当的数学工具得到的一种数一些必要的简化与设，运用适当的数学工具得到的一种数学结构。学结构。面对相同的输入，模型的输出应能够无限地逼近现实世界面对相同的输入，模型的输出应能够无限地逼近现实世界的输出。的输出。信息检索模型信息检索模型 是用来描述文档和用户查询的表示形式以及它们之间相关是用来描述文档和用户查询的表示形式以及它们之间相关性的框架性的

4、框架信息检索模型信息检索模型 信息检索的实质问题信息检索的实质问题 对于所有文档，根据其与用户查询的相关程度由大到小对于所有文档，根据其与用户查询的相关程度由大到小进行排序。进行排序。信息检索模型与搜索引擎排序算法关系信息检索模型与搜索引擎排序算法关系 好的检索模型在相关性上产生和人类决策非常相关的结好的检索模型在相关性上产生和人类决策非常相关的结果，基于好的检索模型的排序算法能够在排序结果顶部返果，基于好的检索模型的排序算法能够在排序结果顶部返回相关的文档。回相关的文档。在在TREC数据集上的试验中，最有效的排序算法来自于数据集上的试验中，最有效的排序算法来自于被明确定义的检索模型。（在商用

5、的搜索引擎中，所使用被明确定义的检索模型。（在商用的搜索引擎中，所使用的检索模型没用明确的定义，但其排序算法都依赖于坚实的检索模型没用明确的定义，但其排序算法都依赖于坚实的数学基础）的数学基础）信息检索模型信息检索模型信息检索模型信息检索模型 相关性概念相关性概念 信息检索系统的形式化表示信息检索系统的形式化表示相关性相关性 主题相关（一篇文档被判定和一个查询是同一主题）1.相关性 用户相关（考虑用户在判定相关性时涉及的所有因素）二元相关（简单判定一篇文档是相关还是非相关）2.相关性 多元相关（从多个层次判断相关性）信息检索模型信息检索模型 信息检索系统的形式化表示 D,Q,F,R(Di,q)

6、1.文档表示文档表示 D 文档集合的机内表示文档集合的机内表示 D=D1,D2,Dm 为了满足检索匹配所要求的快速与便利，文档为了满足检索匹配所要求的快速与便利，文档Di通常由通常由从文档中抽取的能够表达文档内容的特征项（如索引项从文档中抽取的能够表达文档内容的特征项（如索引项/检索词检索词/关键词）来表示关键词）来表示 设设T=t1,t2,tn 为系统索引项集合为系统索引项集合 则则Di=di1,di2,din(dij0)dij索引词索引词tj在文档在文档Di中的重要性（权值中的重要性（权值weight）信息检索模型信息检索模型 D,Q,F,R(Di,q)2 查询项表示查询项表示 查询项查询

7、项Q表示为有表示为有m个权值的向量：个权值的向量：Q=(q1,q2,q3,qm)其中其中qj是第是第j个词项的权值。个词项的权值。3 F 文档与查询查询之间的匹配框架文档与查询查询之间的匹配框架 4 R(Di,q)文档与用户查询之间相关度计算函数文档与用户查询之间相关度计算函数例：例：D1：Tropical Freshwater Aquarium Fish.D2：Tropical Fish,Aquarium Care,Tank Setup.D3：Keeping Tropical Fish and Goldfish in Aquariums,and Fish Bowls.D4：The Tropi

8、cal Tank Homepage-Tropical Fish and Aquariums.文档向量表示：文档向量表示：Terms Documents D1 D2 D3 D4aquarium 1 1 1 1bowl 0 0 1 0care 0 1 0 0Fish 1 1 2 1Freshwater 1 0 0 0Goldfish 0 0 1 0Homepage 0 0 0 1Keep 0 0 1 0Setup 0 1 0 0Tank 0 1 0 1Tropical 1 1 1 2查询表示：查询表示：如：查询项为“tropical fish”,则基于以上查询项的向量表示形式为：q=(0,0,0,

9、1,0,0,0,0,0,0,1).信息检索模型信息检索模型 1.1 信息检索模型的定义信息检索模型的定义 1.2 布尔模型布尔模型 1.3 向量空间模型向量空间模型 1.4 概率模型概率模型 1.5 典型的搜索引擎排序算法典型的搜索引擎排序算法 1.6 适用于数学公式搜索引擎排序算法的适用于数学公式搜索引擎排序算法的探探 讨讨布尔模型布尔模型 最早的最早的IR模型模型 1957年，年，YBar-Hille就对布尔逻辑应用于计算机信息检就对布尔逻辑应用于计算机信息检索的可能性进行了探讨目前仍然应用于商业系统中索的可能性进行了探讨目前仍然应用于商业系统中 典型系统：典型系统：Lucene 布尔模型

10、的前提假设：布尔模型的前提假设：1.在检索到的集合中所有文档关于相关性是等价的。在检索到的集合中所有文档关于相关性是等价的。2.相关性是二元的。相关性是二元的。特点 1.检索的结果只输出结果（检索的结果只输出结果（TURE|FALSE)。2.查询项被描述为布尔逻辑操作符查询项被描述为布尔逻辑操作符(AND,OR,NOT)。布尔模型布尔模型 Q 查询查询q被表式成索引项的布尔组合形式被表式成索引项的布尔组合形式 为方便计算文档为方便计算文档D和查询和查询q之间的相关度，一般之间的相关度，一般将查询将查询q的布尔表达式转换成的布尔表达式转换成析取范式析取范式（Disjunctive Normal

11、Form，DNF）的形式）的形式 Example q=(a b)z (az)(b z)(1,0,1)(1,1,1)(0,1,1)析取范式析取范式（1）由有限个简单合取式构成的析取式称为析）由有限个简单合取式构成的析取式称为析取范式。取范式。（2）仅由有限个文字构成的合取式称为简单合）仅由有限个文字构成的合取式称为简单合取式。取式。布尔模型布尔模型 Example：q=病毒病毒and（计算机（计算机or 电脑）电脑）and not 医医 D:D1：据报道据报道计算机病毒计算机病毒最近猖獗最近猖獗 D2：小王虽然是学：小王虽然是学医医的，但对研究的，但对研究电脑病毒电脑病毒也感兴趣也感兴趣 D3：

12、计算机计算机程序发现了艾滋病程序发现了艾滋病病毒病毒传播途径传播途径 上述文档哪一个会被检索到？上述文档哪一个会被检索到？q=病毒病毒(计算机计算机电脑电脑)医医 q-dnf=(病毒病毒计算机计算机医医)(病毒病毒电脑电脑医医)采用完全匹配的方式采用完全匹配的方式 -If sim(Di,q)=1,返回返回 -If sim(Di,q)=0，不返回，不返回布尔模型布尔模型 Example D-D1：a,b,c,f,g,h D1=(1,1,0)-D2：a,f,b,x,y,z D2=(1,1,1)q-(ab)z (1,0,1)(0,1,1)(1,1,1)F-sim(D1,q)=0-sim(D2,q)=

13、1 R-将文档将文档2返回返回布尔模型布尔模型 缺点：缺点：效率完全依赖于用户，包含特定检效率完全依赖于用户，包含特定检索词的所有文档将按照某种和相关性无关索词的所有文档将按照某种和相关性无关的顺序（如：日期）呈现给用户。的顺序（如：日期）呈现给用户。优点：优点：查询项无局限性，可以是任何文档查询项无局限性，可以是任何文档的特征而只非词语，可以直接在检索规范的特征而只非词语，可以直接在检索规范中融入元数据，如文档日期，文档类型。中融入元数据，如文档日期，文档类型。比排序检索更有效，文档可以在搜索过程比排序检索更有效，文档可以在搜索过程中快速被剔除。中快速被剔除。信息检索模型 1.1 信息检索模

14、型的定义信息检索模型的定义 1.2 布尔模型布尔模型 1.3 向量空间模型向量空间模型 1.4 概率模型概率模型 1.5 典型的搜索引擎排序算法典型的搜索引擎排序算法 1.6 适用于数学公式搜索引擎排序算法的适用于数学公式搜索引擎排序算法的探探 讨讨向量空间模型向量空间模型 向量空间模型（向量空间模型（Vector Space Model，VSM）是由）是由GSalton等人在等人在1958年提出的年提出的 代表系统代表系统 SMART（System for the Manipulation and Retrieval of Text）这一系统理论框架到现在仍然是信息检索这一系统理论框架到现在

15、仍然是信息检索技术研究的基础技术研究的基础向量空间模型向量空间模型1.仍然采用如前所述的信息检索系统的形式化表示。仍然采用如前所述的信息检索系统的形式化表示。2.向量空间模型的定义：向量空间模型的定义：D=D1,D2,Di=(Di1,Di2,Din)Dij0 Q q=(q1,q2,qn)qj0 F 非完全匹配方式非完全匹配方式 R 在在VSM中，由于文档和查询都是向量，因此用文档和查询两个向量相似度中，由于文档和查询都是向量，因此用文档和查询两个向量相似度来估计文档和查询的相关性来估计文档和查询的相关性 文档和查询之间的相关度具有较强的可计算性和可操作性，不再只有文档和查询之间的相关度具有较强

16、的可计算性和可操作性，不再只有0和和1两个值两个值 sim(Di,q)3 前提假设前提假设 1.在检索到的集合中所有文档关于相关性是不等价的。在检索到的集合中所有文档关于相关性是不等价的。2.相关性是多元元的。相关性是多元元的。3.查询关键字之间是相互独立的。查询关键字之间是相互独立的。向量空间模型向量空间模型 例图：例图：相似度度量的提出相似度度量的提出 基于以上表示和分析可以通过计算表示文档和查询点基于以上表示和分析可以通过计算表示文档和查询点之间的距离来进行排序。之间的距离来进行排序。词项1词项2词项3查询查询文档文档2文档文档1向量空间模型向量空间模型余弦相似度度量方法余弦相似度度量方

17、法内积值没有界限内积值没有界限 不象概率值，要在不象概率值，要在(0,1)之间之间对长文档有利对长文档有利 内积用于衡量有多少词项匹配成功，而不计算有多少词项匹配失败内积用于衡量有多少词项匹配成功，而不计算有多少词项匹配失败 长文档包含大量独立词项，每个词项均多次出现，因此一般而言，和长文档包含大量独立词项，每个词项均多次出现，因此一般而言，和查询式中的词项匹配成功的可能性就会比短文档大。查询式中的词项匹配成功的可能性就会比短文档大。利用向量长度对内积进行归一化利用向量长度对内积进行归一化12211cos(,)nijjjinnijjjjdqDQdq=邋向量空间模型向量空间模型 Example

18、D1=(0.5,0.8,0.3)D2=(0.9,0.4,0.2)Q=(1.5,1.0,0)cos(D1,Q)=0.87;cos(D2,Q)=0.97;优点：优点：-反映出不同关键词在文档中的重要程度。反映出不同关键词在文档中的重要程度。-可以根据结果文档对于查询串的相关度通过余弦相似度度可以根据结果文档对于查询串的相关度通过余弦相似度度量等公式对结果文档进行排序量等公式对结果文档进行排序-可以控制输出结果的数量可以控制输出结果的数量向量空间模型向量空间模型 缺点：缺点：认为关键词之间是相互独立的，这一假设有时不符合自然语言的实认为关键词之间是相互独立的，这一假设有时不符合自然语言的实际情况，未

19、能揭示词语之间的关系际情况，未能揭示词语之间的关系。如何确定词项在文档中的权值？如何确定词项在文档中的权值？使用使用tf.idf方法，方法，(tf索引项在一个文档中出现的次数；索引项在一个文档中出现的次数；idf索引项在整索引项在整个文档集合中出现的频率，称为反文档频率，如果一个词素出现在个文档集合中出现的频率，称为反文档频率，如果一个词素出现在少量的文档中，则该词项被赋予较大的权值，参考少量的文档中，则该词项被赋予较大的权值，参考熵农信息论熵农信息论）是文档是文档Di中词项中词项k的频率，的频率，fik是词项是词项k在文档中出现的次数。在文档中出现的次数。为了避免长文档中很多词项只出现一次，

20、其他词项出现成百上千次，为了避免长文档中很多词项只出现一次，其他词项出现成百上千次，对以上取对数，倒置文档斌率反映了文档数据集中词项的重要性。对以上取对数，倒置文档斌率反映了文档数据集中词项的重要性。Idfk是词项是词项k的倒置文档频率，的倒置文档频率，N是文档数据集中文档的个数，是文档数据集中文档的个数，nk是是词项词项k出现过的文档个数。出现过的文档个数。1ikiknijjftffiktflogkkNidfn向量空间模型向量空间模型 最终典型的文档词项权值形式为：词项频率加1是为了保证频率为1的词项具有非零权值。著名的Rocchio算法基于向量空间模型，并加入了用户判定文档的相关性来修改查

21、询项。21(log()1)log(/)log()1.0)log(/)ikkiknikkkfNndfNn信息检索模型 1.1 信息检索模型的定义信息检索模型的定义 1.2 布尔模型布尔模型 1.3 向量空间模型向量空间模型 1.4 概率模型概率模型 1.5 典型的搜索引擎排序算法典型的搜索引擎排序算法 1.6 适用于数学公式搜索引擎排序算法的适用于数学公式搜索引擎排序算法的探探 讨讨概率模型概率模型 概率论模型，亦称为二值独立检索模型。1976年由Roberston和Sparck Jones提出的经典概率模型。在概率的框架下解决IR的问题。概率模型 给定一个用户查询，存在一个文档集合，该集合只包

22、括与查询完全相关的文档而不包括其他不相关的文档，称该集合为理想结果集合。如何描述这个理想结果集合？即：该理想结果集合具有什么样的属性？基于相关反馈的原理，需要进行一个逐步求精的过程 PRP(probability ranking principle)将信息获取看成是一个过程：用户提交一个查询，系统提供给用户它所认为的相关结果列表；用户考察这个集合后给出一些辅助信息，系统再进一步根据这辅助信息（加上以前的信息）得到一个新的相关结果列表；如此继续。如果每次结果列表中的元素总是按照和查询相关的概率递减排序的话，则系统的整体效果会最好。其中概率的计算应该是基于当时所能得到的所有信息。概率模型-相关概念

23、 贝叶斯定理：词条的独立假设：P(AB)=P(A)P(B)当且仅当 A与B相互独立 由此对一篇文档而言，若文档中的各个索引词相互独立，则有 P(dj)=P(k1)P(kt)()()|()|(BPAPABPBAP概率模型 定义：设索引词的权重为二值的，即：R表示已知的相关文档集（或最初的猜测集），用 表示R的补集。表示文档dj与查询q相关的概率，表示文档dj与查询q不相关的概率。文档dj与查询q的相似度sim(dj,q)可以定义为：0,1,0,1ijiqwwR(|)jP R d(|)jP R d(|)(,)(|)jjjP Rdsim dqP Rd概率模型 根据贝叶斯定理有(|)()(,)(|)(

24、)jjjP dRP Rsim d qP dRP R(|)(,)(|)jjjP Rdsim dqP Rd概率模型 假设标引词独立，则 这是概率模型中排序计算的主要表达式。()1()0()1()0(|)(|)(,)(|)(|)ijijijijiig dg djiig dg dP k RP kRsim d qP k RP k R(|)()(,)(|)()jjjP dRP Rsim dqP dRP R概率模型 取对数，在相同背景下，忽略对所有因子保持恒定不变的因子，则有1(|)1(|)(,)loglog1(|)(|)tiijiqijiiiP k RP k Rsim d qwwP k RP k R()1

25、()0()1()0(|)(|)(,)(|)(|)ijijijijiig dg djiig dg dP k RP kRsim d qP k RP k R概率模型 如何计算上式中的 和 呢？简单假设作为最初的猜测1).对所有的索引词ki是恒定不变的，通常取为0.5，即 2).不相关文档中的索引词ki的分布可以通过文档集中索引词的分 布来估计，即其中，ni表示包含索引词ki 的文档数，N表示集合中的文档总数。初始值确定后，根据与查询q相关的大小进行初步排序，取前若干个文档作为相关查询集合。之后通过如下方法进行改进(即开始递归计算)。(|)iPk R(|)iPk R(|)iP kR(|)0.5iP k

26、 R(|)iinP kRN概率模型 用V表示概率模型初步检出并经过排序的文档子集 Vi表示V中包含索引词ki的文档数。改进 和 的过程如下：1）用已经检出的文档中索引词ki的分布来估计 2).假定所有未检出的文档都是不相关的来估计 如此递归重复这一过程，得到理想结果集合(|)iP kR(|)iP kR(|)iP kR(|)iiVP kRV(|)iP kR(|)iiinVP kRNV概率模型 对较小的V和Vi上述计算会出现问题，如V=1和Vi=0，可做一些改进：调整因子也可以为ni/N，即0.5(|)1iiVP kRV0.5(|)1iiinVP kRNV(|)1iiinVNP kRV(|)1ii

27、iinnVNP kRNV概率模型 该方法的缺点:不考虑索引词在文档中出现的频率,所有权值都是二元的.索引词之间相互独立的假设。信息检索模型 1.1 信息检索模型的定义信息检索模型的定义 1.2 布尔模型布尔模型 1.3 向量空间模型向量空间模型 1.4 概率模型概率模型 1.5 典型的搜索引擎排序算法典型的搜索引擎排序算法 1.6 适用于数学公式搜索引擎排序算法的适用于数学公式搜索引擎排序算法的探探 讨讨典型的搜索引擎排序算法典型的搜索引擎排序算法Yahoo!搜索隐身列出影响相关程度的因素有：和差选字符创相同的字串搜索隐身列出影响相关程度的因素有：和差选字符创相同的字串多寡。多寡。词频和位置加

28、权算法。词频和位置加权算法。核心思想：核心思想：以空间向量模型为基础以空间向量模型为基础，以关键字与网页的关系作为，以关键字与网页的关系作为网页排序的依据，关键词与网页的关系是根据关键词在网页中出现的次数网页排序的依据，关键词与网页的关系是根据关键词在网页中出现的次数和位置两个方面进行权值的计算。和位置两个方面进行权值的计算。关键词的频次采用上文中的频次计算方法关键词的频次采用上文中的频次计算方法；位置加权则是根据关键词在网页中出现的不同位置及版式来赋予不同位置加权则是根据关键词在网页中出现的不同位置及版式来赋予不同的权值，位置的重要性不同，则权值不同，版式不同，权值也有区别。其的权值，位置的

29、重要性不同，则权值不同，版式不同，权值也有区别。其中关键词的位置有中关键词的位置有:网页标题、网页标题、META标签、正文标题、正文内容、超链接标签、正文标题、正文内容、超链接锚文本等锚文本等;版式有版式有:字号大小、是否加粗等强调特征。对于重要的位置如标字号大小、是否加粗等强调特征。对于重要的位置如标题、正文的结尾等出现的关键词则赋予较大的权值。题、正文的结尾等出现的关键词则赋予较大的权值。该排序算法根据关键词的位置和频次加权得出关键词与网页的相似度，该排序算法根据关键词的位置和频次加权得出关键词与网页的相似度，按照关键词在网页中的权值大小对该搜索结果进行排序。按照关键词在网页中的权值大小对

30、该搜索结果进行排序。其核心公式为上文中的余弦相似度量公式。其核心公式为上文中的余弦相似度量公式。缺点：比较适用于结构化文档数据，无法应对关键词堆砌现象。缺点：比较适用于结构化文档数据，无法应对关键词堆砌现象。Google核心排序算法：核心排序算法：PageRank算法。算法。典型的搜索引擎排序算法典型的搜索引擎排序算法 PageRank算法：算法：将网页或者文档视作一个点，网页之间的超链接视作将网页或者文档视作一个点，网页之间的超链接视作有向边，则会构成一个巨大的有向图。有向边，则会构成一个巨大的有向图。相同颜色代表主体相关网页（主题相关的点的连接要多于相同颜色代表主体相关网页（主题相关的点的

31、连接要多于普通网页之间的连接），点之间的有向连接反映了网页之普通网页之间的连接），点之间的有向连接反映了网页之间互相引用，参考和推荐的关系，入度越多，则被引用或间互相引用，参考和推荐的关系，入度越多，则被引用或推荐的次数越多，网页的重要性就越大。推荐的次数越多，网页的重要性就越大。典型的搜索引擎排序算法典型的搜索引擎排序算法基于以上分析，基于以上分析，PageRank的核心公式为：的核心公式为：其中：其中：PR(a)：页面：页面a的网页级别；的网页级别；PR(T1):页面页面T1的网页级别，页面的网页级别，页面T1链向链向a；C(T1)：页面：页面T1链出的链接数量；链出的链接数量；d：阻尼系数，取值在：阻尼系数，取值在0-1之间（用来模仿用户无目的的连接到之间（用来模仿用户无目的的连接到 另一个页面）。另一个页面）。11()(1)()/().()/()nnPR add PR TC TPR TC T