基于网页分块思想的pagerank算法研究与优化

《基于网页分块思想的pagerank算法研究与优化》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于网页分块思想的PageRank算法研究与优化：PageRank是一种典型的搜索结果排序算法。本文首先分析了PageRank算法的工作原理及X页分块的基本思想；然后研究了一种基于VIPS分块技术的块级PageRank改进算法，并提出了简化X页分块过程、融合计算PageRank排名值等优化措施；最后对该算法的应用实现进行了必要的展望。　　关键词：X页分块；VIPS算法；链接分析；PageRank算法　　　　搜索结果排序算法是搜索引擎的核心算法，主要解决如何给用户提供最相关的查询结果的问题，通常有基于内容分析和基于链接分析两大类。PageRank是Google采用的一种基于链接分析

2、的搜索结果排序算法，PageRank值越高的X页，在结果中出现的位置就越靠前。由于单纯的PageRank算法独立于检索主题，忽略了页面内部的层次结构及相关内容，因此，难以取得准确的排序结果。　　1PageRank链接分析算法　　PageRank算法建立在随机冲浪模型上，将整个看作一个有向链接图：G=（V，E），其中V是节点X页集，E是边集（从页面i到j的链接）。基本思想是：如果一个页面被其他页面引用，则该页面可能是重要页面；一个页面尽管没有被多次引用，但被一个重要页面引用，那么该页面也可能是重要页面；一个页面的重要性被平摊到它所引用的所有页面[1]。　　PageRank算法基于整

3、个的的链接结构来计算各X页的重要性，初始计算方法如下公式（1）所示：　　其中PRn+1（P）表示第n+1次迭代运算中X页P的Page-　　Rank值，Ti表示链入P的X页，C（Ti）表示Ti链出的X页总数，N为X页的总数量，d为阻尼系数，Google通常取值为0.85。　　有向链接图中每条边的权重值是链接分摊出去的PageRank值，如果定义n维列向量P来表示各X页的PageRank值，则P=（P（1），P（2），…，P（n））T。定义A为图的邻接矩阵，矩阵元素的值就是X页间的链接权重，则求n个公式（1）的方程可以转换成矩阵：ATP=P，计算PageRank值就转化成了计算邻接矩

4、阵A的特征向量。预先给定一个初值，经过迭代计算后，最终可得到X页的PageRank排名值[2]。　　2X页分块思想　　X页具有典型的语义分块特征，X页分块是按照该特征来理解和分析X页内容的新技术，在X页文档分类、信息提取、搜索引擎优化等方面具有重要作用，主要有基于DOM树分析、页面信息分析、页面布局关系分析及视觉特征分析等方法[3]。　　VIPS是DengCai等人提出的一种基于视觉特征分析的X页分块算法，它将页面整体视为一个视觉块，并根据预设内聚度（PDoC）进行迭代分割而得到划分结果[4]。该算法将X页看作三元组：Ω=（Ο，Φ，δ），其中Ο=（Ω1，Ω2，…，Ωk），表示给定

5、页面上的所有的不重叠的语义块集合，而每一个语义块Ωi又可被定义为三元组Ωi=（Οi，Φi，δi），如此迭代循环。Φ=（φ1，φ2，…，φT），表示当前页面上的所有水平和垂直分隔条（不真正存在，但具有一定的宽度和高度）的集合。δ=（ζ1，ζ2，…，ζm），描述Ω集合中两个语义块间的关系，可用δ=Ο×Ο→Φ∪{NULL}描述。其中每个ζ都是一个（Ωi，Ωj）二元组，表示块Ωi和Ωj之间存在一个分割。　　VIPS算法将整个分页过程分成页面块提取、分隔条提取、语义块重构三个步骤，并组成一次语义块检测的完整过程（图1）。当全部的语义块被提取出来以后，整个X页基于视觉的内容结构就构建完成。　

6、　3基于X页分块思想的PageRank算法　　传统PageRank算法将链接关系定位在页面之上，无法辨识是否与主题内容相关，搜索结果中容易出现无关X页，产生“主题漂移”、偏重“旧X页”等问题[5]。X页分块操作将一个页面分割为多个语义块，不仅过滤了与页面语义无关的导航、广告、友情等链接信息，而且有助于提取主题信息。基于X页分块的PageRank算法，需要重构X页与块、块与块之间的关系[6]。　　3.1X页与X页块关系定义　　X页关系图定义为Gp（Vp，Ep，（向量空间模型）[7]的X页或X页块的内容相似度，p为权重系数，用来调节PageRank值和内容相似度的计算比重，取值范围在

7、0到1之间。对于不同的X页内容对象而言，可以利用不同的特征作为该对象的向量，比如X页文本，可以使用TF*IDF（词频*文档频率）来建立X页的向量空间，对于X页图像，可以使用颜色、形状、纹理等低层特征来建立向量空间，从而针对这些特征计算出X页内容相似度。　5块级PageRank算法的应用与展望　　通过分析X页、语义块、超链接之间的关系，块级PageRank算法构建出了基于分块的X页链接关系图模型。根据待查询内容的不同特征构建相应的VSM向量空间，改进后的块级PageRank算法可以