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

信息检索与搜索引擎排序算法,- 徐艳霞,主要内容,1 信息检索模型介绍 2 搜索引擎典型排序算法介绍 3 适用于数学公式搜索引擎排序算法探讨,搜索引擎排序标准,如果我牙疼，应该去看怎样的医生呢？假设我只有三种选择： A医生，既治眼病，又治胃病； B医生，既治牙病，又治胃病，还治眼病； C医生，专治牙病。 假如再加一个条件：B医生经验丰富，有二十年从医经历，医术高明，而C医生只有五年从医经验。 结论：择医需要考虑两个条件，1：医生的专长与病情的适配程度 2：医生的医术 网页内容与用户查询的匹配程度 搜索引擎排序 网页本身的质量,目录,1.1 信息检索模型的定义 1.2 布尔模型 1.3 向量空间模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 1.6 适用于数学公式搜索引擎排序算法的探 讨,信息检索模型,1 信息检索模型的定义 什么是数学模型？ 为了某种特定目的，通过对现实世界的某一特定对象做出一些必要的简化与设，运用适当的数学工具得到的一种数学结构。 面对相同的输入，模型的输出应能够无限地逼近现实世界的输出。 信息检索模型 是用来描述文档和用户查询的表示形式以及它们之间相关性的框架,信息检索模型,信息检索的实质问题 对于所有文档，根据其与用户查询的相关程度由大到小进行排序。 信息检索模型与搜索引擎排序算法关系 好的检索模型在相关性上产生和人类决策非常相关的结果，基于好的检索模型的排序算法能够在排序结果顶部返回相关的文档。 在TREC数据集上的试验中，最有效的排序算法来自于被明确定义的检索模型。（在商用的搜索引擎中，所使用的检索模型没用明确的定义，但其排序算法都依赖于坚实的数学基础）,信息检索模型,信息检索模型,相关性概念 信息检索系统的形式化表示 相关性 主题相关（一篇文档被判定和一个查询是同一主题） 1.相关性 用户相关 （考虑用户在判定相关性时涉及的所有因素） 二元相关（简单判定一篇文档是相关还是非相关） 2.相关性 多元相关 （从多个层次判断相关性）,信息检索模型,信息检索系统的形式化表示 D,Q,F,R(Di,q) 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 查询项表示 查询项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 Tropical Tank Homepage-Tropical Fish and Aquariums.,文档向量表示：,Terms Documents D1 D2 D3 D4 aquarium 1 1 1 1 bowl 0 0 1 0 care 0 1 0 0 Fish 1 1 2 1 Freshwater 1 0 0 0 Goldfish 0 0 1 0 Homepage 0 0 0 1 Keep 0 0 1 0 Setup 0 1 0 0 Tank 0 1 0 1 Tropical 1 1 1 2 查询表示： 如：查询项为“tropical fish”,则基于以上查询项的向量表示形式为： q=(0,0,0,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 布尔模型的前提假设： 1.在检索到的集合中所有文档关于相关性是等价的。 2.相关性是二元的。 特点 1.检索的结果只输出结果（TURE | FALSE)。 2.查询项被描述为布尔逻辑操作符(AND,OR,NOT)。,布尔模型,Q 查询q被表式成索引项的布尔组合形式 为方便计算文档D和查询q之间的相关度，一般将查询q的布尔表达式转换成析取范式（Disjunctive Normal 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：计算机程序发现了艾滋病病毒传播途径 上述文档哪一个会被检索到？ 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)=1 R -将文档2返回,布尔模型,缺点：效率完全依赖于用户，包含特定检索词的所有文档将按照某种和相关性无关的顺序（如：日期）呈现给用户。 优点：查询项无局限性，可以是任何文档的特征而只非词语，可以直接在检索规范中融入元数据，如文档日期，文档类型。比排序检索更有效，文档可以在搜索过程中快速被剔除。,信息检索模型,1.1 信息检索模型的定义 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） 这一系统理论框架到现在仍然是信息检索技术研究的基础,向量空间模型,1 .仍然采用如前所述的信息检索系统的形式化表示。 2 .向量空间模型的定义： D=D1, D2, Di=(Di1 , Di2 , ,Din ) Dij0 Q q= (q1 , q2 , ,qn ) qj0 F 非完全匹配方式 R 在VSM中，由于文档和查询都是向量，因此用文档和查询两个向量相似度来估计文档和查询的相关性 文档和查询之间的相关度具有较强的可计算性和可操作性，不再只有0和1两个值 sim(Di ,q) 3 前提假设 1.在检索到的集合中所有文档关于相关性是不等价的。 2.相关性是多元元的。 3.查询关键字之间是相互独立的。,向量空间模型,例图： 相似度度量的提出 基于以上表示和分析可以通过计算表示文档和查询点之间的距离来进行排序。,词项1,词项2,词项3,查询,文档2,文档1,向量空间模型,余弦相似度度量方法 内积值没有界限 不象概率值，要在(0,1)之间 对长文档有利 内积用于衡量有多少词项匹配成功，而不计算有多少词项匹配失败 长文档包含大量独立词项，每个词项均多次出现，因此一般而言，和查询式中的词项匹配成功的可能性就会比短文档大。 利用向量长度对内积进行归一化,向量空间模型,Example 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; 优点： - 反映出不同关键词在文档中的重要程度。 - 可以根据结果文档对于查询串的相关度通过余弦相似度度量等公式对结果文档进行排序 - 可以控制输出结果的数量,向量空间模型,缺点： 认为关键词之间是相互独立的，这一假设有时不符合自然语言的实际情况，未能揭示词语之间的关系。 如何确定词项在文档中的权值？ 使用tf.idf方法，(tf索引项在一个文档中出现的次数；idf索引项在整个文档集合中出现的频率，称为反文档频率，如果一个词素出现在少量的文档中，则该词项被赋予较大的权值，参考熵农信息论） 是文档Di中词项k的频率，fik是词项k在文档中出现的次数。 为了避免长文档中很多词项只出现一次，其他词项出现成百上千次，对以上取对数，倒置文档斌率反映了文档数据集中词项的重要性。 Idfk是词项k的倒置文档频率，N是文档数据集中文档的个数，nk是词项k出现过的文档个数。,向量空间模型,最终典型的文档词项权值形式为： 词项频率加1是为了保证频率为1的词项具有非零权值。 著名的Rocchio算法基于向量空间模型，并加入了用户判定文档的相关性来修改查询项。,信息检索模型,1.1 信息检索模型的定义 1.2 布尔模型 1.3 向量空间模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 1.6 适用于数学公式搜索引擎排序算法的探 讨,概率模型,概率论模型，亦称为二值独立检索模型。 1976年由Roberston和Sparck Jones提出的经典概率模型。在概率的框架下解决IR的问题。,概率模型,给定一个用户查询，存在一个文档集合，该集合只包括与查询完全相关的文档而不包括其他不相关的文档，称该集合为理想结果集合。 如何描述这个理想结果集合？即：该理想结果集合具有什么样的属性？ 基于相关反馈的原理，需要进行一个逐步求精的过程,PRP (probability ranking principle),将信息获取看成是一个过程：用户提交一个查询，系统提供给用户它所认为的相关结果列表；用户考察这个集合后给出一些辅助信息，系统再进一步根据这辅助信息（加上以前的信息）得到一个新的相关结果列表；如此继续。 如果每次结果列表中的元素总是按照和查询相关的概率递减排序的话，则系统的整体效果会最好。 其中概率的计算应该是基于当时所能得到的所有信息。,概率模型-相关概念,贝叶斯定理： 词条的独立假设：P(AB)= P(A) P(B) 当且仅当 A与B相互独立 由此对一篇文档而言，若文档中的各个索引词相互独立，则有 P(dj)=P(k1)P(kt),概率模型,定义：设索引词的权重为二值的，即： R表示已知的相关文档集（或最初的猜测集），用 表示R的补集。 表示文档dj与查询q相关的概率， 表示文档dj与查询q不相关的概率。文档dj与查询q的相似度sim(dj, q)可以定义为：,概率模型,根据贝叶斯定理有,概率模型,假设标引词独立，则 这是概率模型中排序计算的主要表达式。,概率模型,取对数，在相同背景下，忽略对所有因子保持恒定不变的因子，则有,概率模型,如何计算上式中的 和 呢 ？ 简单假设作为最初的猜测 1). 对所有的索引词ki是恒定不变的，通常取为0.5，即 2).不相关文档中的索引词ki的分布可以通过文档集中索引词的分 布来估计，即 其中，ni表示包含索引词ki 的文档数， N表示集合中的文档总数。 初始值确定后，根据与查询q相关的大小进行初步排序，取前若干个文档作为相关查询集合。之后通过如下方法进行改进(即开始递归计算)。,概率模型,用V表示概率模型初步检出并经过排序的文档子集 Vi表示V中包含索引词ki的文档数。 改进 和 的过程如下： 1）用已经检出的文档中索引词ki的分布来估计 2). 假定所有未检出的文档都是不相关的来估计 如此递归重复这一过程，得到理想结果集合,概率模型,对较小的V和Vi上述计算会出现问题，如V=1和Vi=0，可做一些改进： 调整因子也可以为ni/N， 即,概率模型,该方法的缺点: 不考虑索引词在文档中出现的频率,所有权值都是二元的. 索引词之间相互独立的假设。,信息检索模型,1.1 信息检索模型的定义 1.2 布尔模型 1.3 向量空间模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 1.6 适用于数学公式搜索引擎排序算法的探 讨,典型的搜索引擎排序算法,Yahoo!搜索隐身列出影响相关程度的因素有：和差选字符创相同的字串多寡。 词频和位置加权算法。 核心思想：以空间向量模型为基础 ，以关键字与网页的关系作为网页排序的依据，关键词与网页的关系是根据关键词在网页中出现的次数和位置两个方面进行权值的计算。 关