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

《信息检索与搜索引擎排序算法.ppt》由会员分享，可在线阅读，更多相关《信息检索与搜索引擎排序算法.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、信息检索与搜索引擎排序算法,- 徐艳霞,主要内容,1 信息检索模型介绍 2 搜索引擎典型排序算法介绍 3 适用于数学公式搜索引擎排序算法探讨,搜索引擎排序标准,如果我牙疼，应该去看怎样的医生呢？假设我只有三种选择： A医生，既治眼病，又治胃病； B医生，既治牙病，又治胃病，还治眼病； C医生，专治牙病。 假如再加一个条件：B医生经验丰富，有二十年从医经历，医术高明，而C医生只有五年从医经验。 结论：择医需要考虑两个条件，1：医生的专长与病情的适配程度 2：医生的医术 网页内容与用户查询的匹配程度 搜索引擎排序 网页本身的质量,目录,1.1 信息检索模型的定义及检索系统的形式化表示 1.2 布尔

2、模型 1.3 向量空间模型 1.4 概率模型 1.5 典型的搜索引擎排序算法,信息检索模型,1 信息检索模型的定义 什么是数学模型？ 为了某种特定目的，通过对现实世界的某一特定对象做出一些必要的简化与假设，运用适当的数学工具得到的一种数学结构。 面对相同的输入，模型的输出应能够无限地逼近现实世界的输出。 信息检索模型 是用来描述文档和用户查询的表示形式以及它们之间相关性的框架,信息检索模型,信息检索的实质问题 对于所有文档，根据其与用户查询的相关程度由大到小进行排序。 信息检索模型与搜索引擎排序算法关系 好的信息检索模型在相关性上产生和人类决策非常相关的结果，基于好的检索模型的排序算法能够在排

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

4、Dm 为了满足检索匹配所要求的快速与便利，文档Di通常由从文档中抽取的能够表达文档内容的特征项（如索引项/检索词/关键词）来表示 设T=t1, t2 , , tn 为系统索引项集合。 则Di =di1,di2 , ,din (dij0) dij索引词tj在文档Di中的重要性（权值weight）,信息检索模型,D,Q,F,R(Di,q) 2 查询项Q表示 查询项Q表示为有n个权值的向量： Q=(q1,q2,q3,qn) 其中qj是第j个词项的权值。 3 F 文档与查询查询之间的匹配框架 4 R(Di, q)文档与用户查询之间相关度计算函数 例： D1：Tropical Freshwater Aq

5、uarium 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 Goldfis

6、h 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就对布尔逻辑应用于计算机信息检索的

7、可能性进行了探讨目前仍然应用于商业系统中 布尔模型的前提假设： 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）由有限个简单合取式构

8、成的析取式称为析取范式。 （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,

9、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 典型的搜索引擎排序算法,向量空间模

10、型,向量空间模型（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中，由于文档和查询都是向量，因此用文档和查询两个向量相似度来估计

11、文档和查询的相关性 文档和查询之间的相关度具有较强的可计算性和可操作性，不再只有0和1两个值 sim(Di ,q) 3 前提假设 1.在检索到的集合中所有文档关于相关性是不等价的。 2.相关性是多元元的。 3.查询关键字之间是相互独立的。,向量空间模型,例图： 相似度度量的提出 基于以上表示和分析可以通过计算表示文档和查询点之间的距离来进行排序。,词项1,词项2,词项3,查询,文档2,文档1,向量空间模型,余弦相似度度量方法 内积值没有界限 不象概率值，要在(0,1)之间 对长文档有利 内积用于衡量有多少词项匹配成功，而不计算有多少词项匹配失败 长文档包含大量独立词项，每个词项均多次出现，因此

12、一般而言，和查询式中的词项匹配成功的可能性就会比短文档大。 利用向量长度对内积进行归一化,向量空间模型,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

13、方法，(tf索引项在一个文档中出现的次数；idf索引项在整个文档集合中出现的频率，称为反文档频率，如果一个词素出现在少量的文档中，则该词项被赋予较大的权值，参考香农信息论），该方法有很多变形，但都是基于tf和idf的组合形式。 是文档Di中词项k的频率，fik是词项k在文档中出现的次数。,向量空间模型,为了避免长文档中很多词项只出现一次，其他词项出现成百上千次，对以上取对数。 倒置文档频率反映了文档数据集中词项的重要性。 Idfk是词项k的倒置文档频率，N是文档数据集中文档的个数，nk是词项k出现过的文档个数。,向量空间模型,最终典型的文档词项权值形式为： 词项频率加1是为了保证频率为1的词项

14、具有非零权值。 著名的Rocchio算法基于向量空间模型，并加入了用户判定文档的相关性来修改查询项。,香农信息论,信息量是指从N个相等可能事件中选出一个事件所需要的信息度量或含量,也就是在辩识N个事件中特定的一个事件的过程中所需要提问“是或否”的最少次数. 香农（C. E. Shannon）信息论应用概率来描述不确定性。信息是用不确定性的量度定义的.一个消息的可能性愈小,其信息量愈多;而消息的可能性愈大,则其信息愈少.事件出现的概率小，不确定性越多，信息量就大，反之则少 如何计算信息量的多少？在日常生活中，极少发生的事件一旦发生是容易引起人们关注的，而司空见惯的事不会引起注意，也就是说，极少见

15、的事件所带来的信息量多。如果用统计学的术语来描述，就是出现概率小的事件信息量多。因此，事件出现得概率越小，信息量愈大。即信息量的多少是与事件发生频繁(即概率大小)成反比。,信息检索模型,1.1 信息检索模型的定义 1.2 布尔模型 1.3 向量空间模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 1.6 适用于数学公式搜索引擎排序算法的探 讨,概率模型,概率论模型，亦称为二值独立检索模型。 1976年由Roberston和Sparck Jones提出的经典概率模型。在概率的框架下解决IR的问题。 、 对于特定的查询，计算相关文档的概率和不相关文档的概率。换句话说，当P(R|D)P(NR|

16、D)时，判定文档是相关的。 采用贝叶斯决策法则。,概率模型,贝叶斯定理： 独立假设定理：P(AB)= P(A) P(B) 当且仅当 A与B相互独立。 由此对一篇文档而言，假设文档中的各个索引词相互独立，则有： P(dj)=P(k1)P(kt) 如：假设词项“总统”在相关文档中的概率为0.02，“林肯”的概率为0.03，如果新的文档中包括这两个词项，那么假设词项的出现是独立的，则在相关文档中词语整体出现的概率为0.02X0.03=0.0006。,概率模型,1.设索引词的权重为二值的，即： 2.R表示已知的相关文档集（或最初的猜测集），用 表示R的补集。 表示文档dj与查询q相关的概率， 表示文档

17、dj与查询q不相关的概率。文档dj与查询q的相似度sim(dj, q)可以定义为：,概率模型,根据贝叶斯定理有,概率模型,假设索引词项独立，则 这是概率模型中排序计算的主要表达式。,概率模型,取对数，在相同背景下，忽略对所有因子保持恒定不变的因子，则有,概率模型,如何计算上式中的 和 呢 ？ 简单假设作为最初的猜测 1). 对所有的索引词ki是恒定不变的，通常取为0.5，即 2).不相关文档中的索引词ki的分布可以通过文档集中索引词的分 布来估计，即 其中，ni表示包含索引词ki 的文档数， N表示集合中的文档总数。 初始值确定后，根据与查询q相关的大小进行初步排序，取前若干个文档作为相关查询

18、集合。之后通过如下方法进行改进(即开始递归计算)。,概率模型,总结：在此模型中，假设词项的权重是二值的，则文档可表示为一组二元向量，即Di=（d1,d2,dn),其中di=1表示词项i出现在文档中，反之为0。假设二：词项的出现的独立的。（二元独立模型，基于此模型的算法有BM25算法） 该方法的缺点: 不考虑索引词在文档中出现的频率,所有权值都是二元的. 索引词之间相互独立的假设。 优点 文档可以按照相关概率递减的顺序来排序。,信息检索模型,1.1 信息检索模型的定义 1.2 布尔模型 1.3 向量空间模型 1.4 概率模型 1.5 典型的搜索引擎排序算法,典型的搜索引擎排序算法,1.Yahoo

19、!搜索引擎列出影响相关程度的因素有：和查询字符创相同的字串多寡。 2.词频和位置加权算法。 核心思想：以空间向量模型为基础 ，以关键字与网页的关系作为网页排序的依据，关键词与网页的关系是根据关键词在网页中出现的次数和位置两个方面进行权值的计算。 关键词的频次采用上文中的频次计算方法 ； 位置加权则是根据关键词在网页中出现的不同位置及版式来赋予不同的权值，位置的重要性不同，则权值不同，版式不同，权值也有区别。其中关键词的位置有:网页标题、META标签、正文标题、正文内容、超链接锚文本等;版式有:字号大小、是否加粗等强调特征。对于重要的位置如标题、正文的结尾等出现的关键词则赋予较大的权值。 该排序

20、算法根据关键词的位置和频次加权得出关键词与网页的相似度，按照关键词在网页中的权值大小对该搜索结果进行排序。 其核心公式为上文中的余弦相似度量公式。 缺点：比较适用于结构化文档数据，无法应对关键词堆砌现象。 3 .Google核心排序算法：PageRank算法。,典型的搜索引擎排序算法,PageRank算法： 将网页或者文档视作一个点，网页之间的超链接视作有向边，则会构成一个巨大的有向图。 相同颜色代表主体相关网页（主题相关的点的连接要多于普通网页之间的连接），点之间的有向连接反映了网页之间互相引用，参考和推荐的关系，入度越多，则被引用或推荐的次数越多，网页的重要性就越大。,典型的搜索引擎排序算

21、法,基于以上分析，PageRank的核心公式为： 其中：PR(a)：页面a的网页级别； PR(T1):页面T1的网页级别，页面T1链向a； C(T1)：页面T1链出的链接数量； d：阻尼系数，取值在0-1之间（为了避免Link Sink(许多网页没有入链或出链的问题） 4. TopicSensitive PageRank(主题敏感PageRank算法） 加入了主题相关的因素 5. Hilltop 算法 算法的指导思想与PageRank是一致的，即通过链接的数量和质量来确定搜索结果的排序权重。与PageRank不同的是，在Hilltop中仅考虑那些专家页面(Export Sources)，即专门用于引导人们浏览资源的页面。,典型的搜索引擎排序算法,6. HITS算法的排名准确性要比PageRank高。但是HITS 最大的问题在于它是一个依赖于查询关键字的算法，在线运算量大，极大地影响了算法的可伸缩性，从而难以应用于大规模的网页数据集。 问题： 数学公式搜索引擎要解决的排序问题： 1.公式的匹配；如何去衡量查询公式与文档的匹配程度？ 2.文档（网页）本身的质量如何去衡量？,