快速关于搜索引擎算法的分析

现今随着互联网的不断发展，网络在人群中的普及，很多人都意识到存在于网络中的商机，所以各种各样类型的网站如雨后春笋般一夜而出，那么对于这么多的网站 搜索引擎是如何对其进行一定程度的排序，然后根据什么判定标准给出的排名呢？期间计算过程非常复杂，这里北京网站优化专家—网域动力给大家普及一下这 方面的知识，通常的三种算法让大家了解一下。   搜索引擎Google最初是斯坦福大学的博士研究生Sergey Brin和Lawrence Page实现的一个原型系统[2]，现在已经发展成为WWW上最好的搜索引擎之一。Google的体系结构类似于传统的搜索引擎，它与传统的搜索引擎最大 的不同处在于对网页进行了基于权威值的排序处理，使最重要的网页出现在结果的最前面。Google通过PageRank元算法计算出网页的 PageRank值，从而决定网页在结果集中的出现位置，PageRank值越高的网页，在结果中出现的位置越前。    PageRank算法    PageRank算法基于下面2个前提：   前提1：一个网页被多次引用，则它可能是很重要的；一个网页虽然没有被多次引用，但是被重要的网页引用，则它也可能是很重要的；一个网页的重要性被平均的传递到它所引用的网页。这种重要的网页称为权威（Authoritive）网页。   前提2：假定用户一开始随机的访问网页集合中的一个网页，以后跟随网页的向外链接向前浏览网页，不回退浏览，浏览下一个网页的概率就是被浏览网页的PageRank值。   简单PageRank算法描述如下：u是一个网页， 是u指向的网页集合， 是指向u的网页集合， 是u指向外的链接数，显然 =| | ，c是一个用于规范化的因子（Google通常取0.85），（这种表示法也适用于以后介绍的算法）则u的Rank值计算如下：   这就是算法的形式化描述，也可以用矩阵来描述此算法，设A为一个方阵，行和列对应网页集的网页。如果网页i有指向网页j的一个链接，则 ，否则 ＝0。设V是对应网页集的一个向量，有V=cAV，V为A的特征根为c的特征向量。实际上，只需要求出最大特征根的特征向量，就是网页集对应的最终 PageRank值，这可以用迭代方法计算。   如果有2个相互指向的网页a，b,他们不指向其它任何网页，另外有某个网页c，指向a，b中的某一个，比如a，那么在迭代计算中，a，b的rank值不分布出去而不断的累计。如下图：   为了解决这个问题，Sergey Brin和Lawrence Page改进了算法，引入了衰退因子E(u)，E(U)是对应网页集的某一向量，对应rank的初始值，算法改进如下：其中， ＝1，对应的矩阵形式为V’=c(AV’+E)。   另外还有一些特殊的链接，指向的网页没有向外的链接。PageRank计算时，把这种链接首先除去，等计算完以后再加入，这对原来计算出的网页的rank值影响是很小的。   Pagerank算法除了对搜索结果进行排序外，还可以应用到其它方面，如估算网络流量，向后链接的预测器，为用户导航等。   SALSA算法   PageRank算法是基于用户随机的向前浏览网页的直觉知识，HITS算法考虑的是Authoritive网页和Hub网页之间的加强关系。实际应用 中，用户大多数情况下是向前浏览网页，但是很多时候也会回退浏览网页。基于上述直觉知识，R. Lempel和S. Moran提出了SALSA（Stochastic Approach for Link-Structure Analysis）算法[8]，考虑了用户回退浏览网页的情况，保留了PageRank的随机漫游和HITS中把网页分为Authoritive和Hub 的思想，取消了Authoritive和Hub之间的相互加强关系。   具体算法如下：１．和HITS算法的第一步一样，得到根集并且扩展为网页集合T，并除去孤立节点。２．从集合T构造无向图G’＝（Vh，Va，E）Vh = { sh |　　 s∈C and out-degree(s) > 0 } ( G’的Hub边).Va = { sa |　　 s∈C and in-degree(s) > 0 } (G’的Authority边).E= { (sh , ra) |　　s－>r　　 in T　}这就定义了2条链，Authority链和Hub链。３．定义2条马尔可夫链的变化矩阵，也是随机矩阵，分别是Hub矩阵H，Authority矩阵A。４．求出矩阵H，A的主特征向量，就是对应的马尔可夫链的静态分布。５．A中值大的对应的网页就是所要找的重要网页。SALSA算法没有HITS中相互加强的迭代过程，计算量远小于HITS。SALSA算法只考虑直接相邻的网页对自身A/H的影响，而HITS是计算整个网页集合T对自身AH的影响。   实际应用中，SALSA在扩展根集时忽略了很多无关的链接，比如１．同一站点内的链接，因为这些链接大多只起导航作用。２．CGI 脚本链接。３．广告和赞助商链接。   试验结果表明，对于单主题查询java，SALSA有比HITS更精确的结果，对于多主题查询abortion，HITS的结果集中于主题的某个方面，而SALSA算法的结果覆盖了多个方面，也就是说，对于TKC现象，SALSA算法比HITS算法有更高的健壮性。   HITS算法   HITS（Hyperlink－Induced Topic Search）算法是利用Hub/Authority方法的搜索方法，算法如下：将查询q提交给传统的基于关键字匹配的搜索引擎．搜索引擎返回很多网页， 从中取前n个网页作为根集(root set)，用S表示。S满足如下3个条件：   1．S中网页数量相对较小   2．S中网页大多数是与查询q相关的网页   3．S中网页包含较多的权威网页。   通过向S中加入被S引用的网页和引用S的网页将S扩展成一个更大的集合T．   以T中的Hub网页为顶点集Vl，以权威网页为顶点集V2，Vl中的网页到V2中的网页的超链接为边集E，形成一个二分有向图SG＝(V1，V2，E)。 对V1中的任一个顶点v，用h(v)表示网页v的Hub值，对V2中的顶点u，用a(u)表示网页的Authority值。开始时 h(v)＝a(u)＝1，对u执行I操作修改它的a(u)，对v执行O操作修改它的h(v)，然后规范化a（u），h（v），如此不断的重复计算下面的操 作I，O，直到a（u），h（v）收敛。（证明此算法收敛可见 ）I 操作： （1） O操作： （2）   每次迭代后需要对a(u),h(v)进行规范化处理：   式(1)反映了若一个网页由很多好的Hub指向，则其权威值会相应增加(即权威值增加为所有指向它的网页的现有Hub值之和)。式(2)反映了若一个网页指向许多好的权威页，则Hub值也会相应增加(即Hub值增加为该网页链接的所有网页的权威值之和)。   和PageRank算法一样，可以用矩阵形式来描述算法，这里省略不写。   HITS算法输出一组具有较大Hub值的网页和具有较大权威值的网页。   链接算法的分类及其评价   链接分析算法可以用来提高搜索引擎的查询效果，可以发现WWW上的重要的社区，可以分析某个网站的拓扑结构，声望，分类等，可以用来实现文档的自动分类等。归根结底，能够帮助用户在WWW海量的信息里面准确找到需要的信息。这是一个正在迅速发展的研究领域。   上面我们从历史的角度总结了链接分析算法的发展历程，较为详细的介绍了算法的基本思想和具体实现，对算法的存在的问题也做了讨论。这些算法有的处于研究阶 段，有的已经在具体的系统实现了。这些算法大体可以分为3类，基于随机漫游模型的，比如PageRank，Repution算法，基于Hub和 Authority相互加强模型的，如HITS及其变种，基于概率模型的，如SALSA，PHITS，基于贝叶斯模型的，如贝叶斯算法及其简化版本。所有 的算法在实际应用中都结合传统的内容分析技术进行了优化。一些实际的系统实现了某些算法，并且获得了很好的效果，Google实现了PageRank算 法，IBM Almaden Research Center 的Clever Project实现了ARC算法，多伦多大学计算机系实现了一个原型系统TOPIC，来计算指定网页有声望的主题。   AT&T香农实验室的Brian Amento在指出，用权威性来评价网页的质量和人类专家评价的结果是一致的，并且各种链接分析算法的结果在大多数的情况下差别很小。但是，Allan Borodin也指出没有一种算法是完美的，在某些查询下，结果可能很好，在另外的查询下，结果可能很差[11]。所以应该根据不同查询的情况，选择不同 的合适的算法。   基于链接分析的算法，提供了一种衡量网页质量的客观方法，独立于语言，独立于内容，不需人工干预就能自动发现WEB上重要的资源，挖掘出WEB上重要的社区，自动实现文档分类。但是也有一些共同的问题影响着算法的精度。１．根集的质量。根集质量应该是很高的，否则，扩展后的网页集会增加很多无关的网页，产生主题漂移，主题泛化等一系列的问题，计算量也增加很多。算法再好，也无法在低质量网页集找出很多高质量的网页。２．噪音链接。WEB上不是每个链接都包含了有用的信息，比如广告，站点导航，赞助商，用于友情交换的链接，对于链接分析不仅没有帮助，而且还影响结果。如何有效的去除这些无关链接，也是算法的一个关键点。３．锚文本的利用。锚文本有很高的精度，对链接和目标网页的描述比较精确。上述算法在具体的实现中利用了锚文本来优化算法。如何准确充分的利用锚文本，对算法的精度影响很大。４．查询的分类。每种算法都有自身的适用情况，对于不同的查询，应该采用不同的算法，以求获得最好的结果。因此，对于查询的分类也显得非常重要。   当然，这些问题带有很大的主观性，比如，质量不能精确的定义，链接是否包含重要的信息也没有有效的方法能准确的判定，分析锚文本又涉及到语义问题，查询的 分类也没有明确界限。如果算法要取得更好的效果，在这几个方面需要继续做深入的研究，相信在不久的将来会有更多的有趣和有用的成果出现。福州网站建设 福州网站制作 网络营销 福州网站设计 网站优化 网站推广排名 福州网络公司