搜索引擎相关度算法分析

搜索引擎相关度算法分析相关性，是搜索引擎优化中的重点。但是对于相关性的搜索引擎工作原理，相信大部分的SEOER对于都缺乏了解。作为职业SEO对于搜索引擎算法的研究是必须的，虽然说，我们不可能知道搜索引擎算法的全部。但是只需要我们主流搜索引擎技术的方向，你就可以知道搜索引擎时代的脉搏。相关度排序技术的产生主要是由搜索引擎的特点决定的。首先，现代搜索引擎能够访问的Web网页数量已经达到上十亿的规模，哪怕用Hu只是搜索其中很少的一部分内容，基于全文搜索技术的搜索引擎也能返回成千上万的页面。即便这些结果网页都是用Hu所需要的，用Hu也没有可能对所有的网页浏览一遍，所以能够将用Hu最感兴趣的结果网页放于前面，势必可以增强搜索引擎用Hu的满意度。其次，搜索引擎用Hu自身的检索专业能力通常很有限，在最为普遍的关键词检索行为中，用Hu一般只是键人几个词语。例如，Spink等曾对Excite等搜索引擎的近300位用Hu做过实验调查，发现人均输入的检索词为3.34个。国内部分学者也有相似的结论，发现90%左右的用Hu输入的中文检索单字为2〜6个，而且2字词居多，约占58%，其次为4字词（约占18%）和3字词（约占14%）。过少的检索词事实上无法真正表达用Hu的检索需求，而且用Hu通常也不去进行复杂的逻辑构造，只有相当少的用Hu进行布尔逻辑检索、限制性检索和高级检索等方法，仅有5.24%的检索式中包含有布尔逻辑算符。国内的部分学者的研究结果也表明，约40%的用Hu不能正确运用字段检索或二次检索，80%左右的用Hu不能正确运用高级检索功能，甚至还发现用Hu缺乏动力去学习复杂的检索技能，多数用Hu都寄希望于搜索引擎能够自动地为他们构造有效的检索式。由于缺乏过去联机检索中常常具备的检索人员，因此，用Hu实际的检索行为与用Hu理想的检索行为存在事实上的差距，检索结果的不满意也是不奇怪的。正是由于这个特点，搜索引擎就必须设法将用Hu最想要的网页结果尽可能地放到网页结果的前面，这就是网页相关度排序算法在搜索引擎中为什么非常重要的原因。现阶段的相关度排序技术主要有以下几种：一是基于传统信息检索技术的方式，它主要利用关键词本身在文档中的重要程度来对文档与用Hu查询要求的相关度做出测量，如利用网页中关键词出现的频率和位置。一般而言，检索出的网页文档中含有的查询关键词个数越多，相关性越大，并且此关键词的区分度越高；同时，查询关键词如果出现在诸如标题字段等重要位置上，则比出现在正文的相关度要大。二是超连分析技术，使用此技术的代表性搜索引擎有Google和Bai。和前者相比，它以网页被认可的重要程度作为检索结果的相关度排序依据。从设计思想上看，它更注重第三方对该网页的认可，如具有较大连入网页数的网页才是得到广泛认可的重要网页，而根据关键词位置和频率的传统方法只是一种网页自我认可的形式，缺乏客观性。最后还有一些其他方式，如由用Hu自由定义排序规则的自定义方式。北京大学的天网FTP搜索引擎就采用这种排序方式，它可以让用Hu选择诸如时间、大小、稳定性和距离等具体排序指标来对结果网页进行相关度排序。再如收费排名模式，它作为搜索引擎的一种主要赢利手段，在具有网络门Hu特点的大型搜索引擎中广为使用，但于担心影响搜索结果的客观性，这种方式不是它们的主流排序方式，而仅仅作为一个补充显示在付费搜索栏目中。相关度排序技术主要依赖于超连分析技术实现。超连分析技术可以提供多种功能，其中的主要功能就是解决结果网页的相关度排序问题。它主要是利用网页间存在的各种超连指向，对网页之间的引用关系进行分析，依据网页连人数的多少计算该网页的重要度权值。一般认为，如果A网页有超连指向B网页，相当于A网页投了B网页一票，即A认可了B网页的重要性。深入理解超连分析算法，可以根据连接结构把整个Web网页文档集看成一个有向的拓扑图，其中每个网页都构成图中的一个结点，网页之间的连接就构成了结点间的有向边，按照这个思想，可以根据每个结点的出度和入度来评价网页的重要性。对于超连分析技术，有代表性的算法主要是Page等设计的PageRank算法和Kleinberg创造的HITS算法。其中，PageRank算法在实际使用中的效果要好于HITS算法，这主要是由于以下原因：首先，PageRank算法可以一次性、脱机且独立于查询的对网页进行预计算以得到网页重要度的估计值，然后在具体的用Hu查询中，结合其他查询指标值，一起对查询结果进行相关性排序，从而节省了系统查询时的运算开销；其次，PageRank算法是利用整个网页集合进行计算的，不像HITS算法易受到局部连接陷阱的影响而产生“主题漂移”现象，所以现在这种技术广泛地应用在许多搜索引擎系统中，Google搜索引擎的广获成功也表明了以超连分析为特征的网页相关度排序算法日益成熟。PageRank技术基于一种假设，即对于Web中的一个网页A，如果存在指向网页A的连接，则可以将A看成是一个重要的网页。PageRank认为网页的连入连接数可以反映网页的重要程度，但是由于现实中的人们在设计网页的各种超连时往往并不严格，有很多网页的超连纯粹是为了诸如网站导航、商业广告等目的而制作，显然这类网页对于它所指向网页的重要程度贡献程度并不高。但是，由于算法的复杂性，PageRank没有过多考虑网页超连内容对网页重要度的影响，只是使用了两个相对简单的方法:其一，如果一个网页的连出网页数太多，则它对每个连出网页重要度的认可能力降低；其二，如果一个网页由于本身连入网页数很低造成它的重要程度降低，则它对连出网页重要度的影响也相应降低。所以，在实际计算中，网页A的重要性权值正比于连入网页A的重要性权值，并且和连入网页A的连出网页数量呈反比。由于无法知道网页A自身的重要性权值，所以决定每个网页的重要权值需要反复迭代地进行运算才能得到。也就是说，一个网页的重要性决定着同时也依赖于其他网页的重要性.【补充材料：搜索引擎的相关排序算法分析与优化】WWW是一个巨大的潜在的知识库，它所拥有的web页已经从最初的几千个发展到至今的20多亿个(已被编入索引).随着网络规模的爆炸性增长,搜索引擎已经成了帮助人们寻找相关信息的重要工具.据纽约市场研究机构朱比特通信公司的调查分析,88%的网上用户使用搜索工具，成为除Email之外使用最多的互联网应用之一.但是由于Web数据本身具有分布、异质、动态、半结构或非结构等特征，这无疑给Web上的信息检索提出了挑战[1].目前的搜索引擎普遍存在着查全率和查准率不高的现象，任何一个简单的查询都至少返回数以万计的检索结果，而其中只有很少一部分与用户真正的检索要求有关.同时，由于搜索引擎数据量巨大，而用户的接受能力有限，查全率对搜索引擎来说基本失去了评价的意义.而前X个检索结果的查准率对于用户的检索目标更具意义[1].影响查准率的因素有很多，相关排序算法是其中的一个关键点。1、相关排序的概念和存在的问题。传统上，人们将信息检索系统返回结果的排序称为“相关排序”(RelevanceRanking)，隐含其中各条目的顺序反映了结果和查询的相关程度.在搜索引擎中,其排序不是一个狭义的相关序,而是一种反映多种因素的综合统计优先序.在排序方面，搜索引擎目前存在的问题：(1)对于多数检索课题，要么输出的检索结果过载，记录数量达千条以上，给相关性判断带来困难;要么是零输出或输出量太少，造成过分的漏检.(2)在相关度方面，搜索引擎对相关度参数的选择、计量和算法各不相同.(3)由于搜索引擎是按照已定的相关度对检索结果进行排序，关键词检索返回结果的相关度排序方式单一，用户不能根据需要选择输入的排序方法，用户对结果的排序无能为力，因而用户基本上是在被动接受返回序列，这难免与用户的检索目标冲突，受到用户接受能力的限制，无疑会影响到检全率与检准率。2、现有的排序算法。现有的搜索引擎排序技术主要有PageRank算法和HITS算法.PageRank算法以“随机冲浪”模型为理论基础，而HITS算法使用Hub和Authority相互加强模型，二者都是利用了网页和超链组成的有向图，根据相互连接的关系进行递归运算.PageRank算法。LawrencePage和SergeyBrin描述了PageRank最初的算法，网页A页的PageRank值PR(A)=(1-d)+d(PR(T1)nC(T1)+-+PR(Tn)nC(Tn)),其中d为阻尼系数，且0<d<1。网页的PageRank值决定了随机访问到这个页面的概率.用户点击页面内的链接概率，完全由页面上链接数量的多少决定的，这也是上面PR(Ti)nC(Ti)的原因.因此，一个页面通过随机冲浪到达的概率就是链入它的页面上的链接被点击概率的和，且阻尼系数的减低了这个概率.阻尼系数的引入，是因为用户不可能无限的点击链接,常常因无聊而随机跳入另一个页面.由此可见，PageRank并不是将整个网站排等级，而是以单个页面计算的.页面A的PageRank值取决于那些连接到A页面的PageRank的递归值.PR(Ti)值并不是均等影响页面PR(A)的.在PageRank的计算公式里,T对于A的影响还受T的出站链接数C(T)的影响.这就是说,T的出站链接越多,A受T的这个连接的影响就越少.PR(A)是所有PR(Ti)之和.所以，对于A来说,每多增加一个入站链接都会增加PR(A).所有PR(Ti)之和乘以一个阻尼系数的,它的值在0到1之间.因此,阻尼系数的使用，减少了其它页面对当前页面A的排序贡献.另外,PageRank算法中对于向外链接的权值贡献是平均的，也就是不考虑不同链接的重要性.斯坦福大学计算机科学系Arvin的Arasu等科学家经过试验表明,PageRank算法计算效率还可以得到很大的提高HITS算法。HITS(Hyperlink-In的uce的TopicSearch)算法是利用HubnAuthority的搜索方法,具体算法如下:将查询q提交给传统的基于关键字匹配的搜索引擎.搜索引擎返回很多网页，从中取前n个网页作为根集(RootSet)，用S表示.S满足如下3个条件:S中网页数量相对较小;S中网页大多数是与查询q相关的网页;S中网页包含较多的权威网页.通过向S中加入被S引用的网页和引用S的网页，将S扩展成一个更大的集合T.以T中的Hub网页为顶点集V1,以权威网页为顶点集V2.V1中的网页到V2中的网页的超链接为边集E,形成一个二分有向图.对V1中的任一个顶点v,用h(v)表示网页v的Hub值,且h(v)收敛;对V2中的顶点u,用a(u)表示网页的Authority值.开始时h(v)=a(u)=1,对u执行I操作，修改它的a(u),对v执行O操作,修改它的h(v),然后规范化a(u)nh(v),如此不断的重复计算下面的I操作和O操作，直到a(u).其中I操作:a(u)=Eh(v);O操作:h(v)=Ea(u).每次迭代对a(u)、h(v)进行规范化处理:a(u)=a(u)nE[a(q)]2;h(v)=h(v)nE[h(q)]2.HITS算法可以获得比较好的查全率，输出一组具有较大Hub值的网页和具有较大权威值的网页.但在实际应用中,HITS算法有以下几个问题:由S生成T的时间开销是很昂贵的，由T生成有向图也很耗时，需要分别计算网页的AnH值，计算量大;网页中广告等无关链接影响A、H值的计算，降低HITS算法的精度;HITS算法只计算主特征向量，处理不好主题漂移问题;进行窄主题查询时，可能产生主题泛化问题.相关分析算法大体可以分为4类:基于随机漫游模型的算法，比如PageRank,Repution算法;基于Hub和Authority相互加强模型的算法,如HITS及其变种;基于概率模型的算法，如SALSA,PHITS;基于贝叶斯模型的算法,如贝叶斯算法.所有的算法在实际应用中都结合传统的内容分析技术进行优化[3].AllanBoro的in也指出没有一种算法是完美的,在某些查询下，结果可能很好，在另外的查询下，结果可能很差。3、排序算法的优化。要提高现有算法的精度,首先,必须增强根集的质量，算法再好，也无法在低质量网页集找出很多高质量的网页;其次，降低噪音链接;最后,选择合适的查询分类.为此，笔者提出了一个考虑综合因素的相关排序实现方案.3.1重组网页中特征项的权重。考虑到HTML的标签的功能不同，将其分为功能类和附加类，对其分配不同的权重表，设标签权重WBT(T,P)=EWBT(i)XLG(SMAXnS(P))XLG(NnT(t))，其中:SMAX表示最大网页可索引文本大小;S(P)代表网页P的可索引文本大小;N代表被索引网页的数量;T(t)代表包含特征项的网页数量.可以看出该方案综合考虑了标签权重、网页大小和特征项的频度.3.2利用改进的PageRank算法分配链接结构。PageRank因子的优化可从下面3个方面着手:设置导入链接PageRank得分;最大回馈和最小损耗的PageRank值的网页做导出链接;修正内部导航结构和内部页面的链接PageRank值，实现PageRank在网站内部的良好分布.设链接值nkiR(u)=CER(v)nN(v){vEB(u)}.其中:u表示一个网页;R(u)表示网页u的PageRank值;B(u)表示链接到网页u的网页集合，即网页u的链入网页集合;N(v)表示从网页v向外的链接数量,即网页v的链出网页数;C为规范化因子,用于保证所有网页的PageRank总和为常量.3.3利用锚文本技术修正其权值。锚文本就是链接文本，它既可以做为锚文本所在页面的内容评估，又能做为对所指向页面的评估，锚文本有很高的精度，对链接和目标网页的描述比较精确.可以利用相似度函数来计算锚文本和特征项，链接的相似度函数表达式:Slinks=W的XS的es+