2.3.1Pagerank 算法背景
伴随着全球计算机信息技术的飞速发展,通过互联网搜寻来获取信息给用 户的生活带来了巨大的便利。但是人们怎样才能在浩瀚的信息海洋中快速搜寻 到有用的信息呢? 1988年,Google公司的创始人、Stanford大学计算机博士 Lawrence Page和Sergey Brin合作共同研究出了 Pagerank算法[85],通过这种算 法能对搜索引擎上的网页的相关性和重要性进行排名,从而在信息筛选方面给 用户提供便利。伴随着Google公司在全世界范围内取得巨大成功,Pagerank算 法也成为全球经典的十大数据挖掘算法及改变未来的九大算法之一。互联网上 庞大的网页群之间彼此链接存在着十分复杂的相关性,Pagerank算法正是基于 网页的链接关系来进行网页的排序,网页的重要度高低直接决定着其排名的高 低。
2.3.2Pagerank 算法原理
Pagerank算法是单纯依据页面之间的复杂链接关系来进行重要度计算,每 个页面的重要度指标为其Pagerank值(下文将简称PR值),重要度高的页面将 对应较高的PR值,而不太重要的网页将对应较低的PR值。表2.1是部分国内 网站的PR值排名。通过表格可知PR值与网页的反链数有关,所谓反链数即从 其他网页导入本网页的链接数量(在有向图中称为入度)。一般来讲反链数越多 (入度越大),其PR值也越大,但通过表格统计发现腾讯网的反链数为1252835 个,在所有网页中是最多的,但是其PR值仅仅排在第三位,这是因为页面的 PR值不仅与其反链数有关,还与被链接过来网页的重要度有关。就像在由多个 社会个体组成的社会关系网络中衡量个体的社会影响力,不仅需要朋友越多, 而且还要朋友质量越高才代表个体的社会地位越高。
所以Pagemnk算法的主要原理是:如果页面A能够链接到页面B,那么将 认为页面A传递给页面B —个重要度值(PR值),此值的大小取决于页面A的 重要度(PR值)以及其出链数,并假设任何页面的重要度都被平均传递到它所 链接的页面。由于网页之间存在相互链接关系,这个计算过程会一直迭代下去, 最后根据页面迭代后的平稳PR值进行排序。基于这一思想,将整个互联网系 统抽象成一个有向图G= (V,E),其中将n个页面抽象成网络图的节点V,用有向边E代表页面之间的链接关系。若网页'、%、...Vk是链入到网页A的页面 节点,那么网页A的PR值PR(A)计算公式为:
式(2.4)中PR(Vi)和CCV;)为分别为页面节点'的PR值和出度;根据 Pagerank算法原理我们可以总结出:
①链入到页面A的网页数量k越大,页面A的PR值就会越大,页面A的重要度越大;
②页面A的链入页面乂、%、...'的重要度越大,页面A会受它们的影响变得更重要;
③页面节点\的出度越大,即CCVD越大,那么页面节点A从页面节点乂处 分得的PR值越少。
公式(2.4)假设当用户在浏览页面\时,下一个浏览页面是均匀地选择下
一个其所指向的页面。Pagemnk算法可以用随机冲浪模式来进行刻画[85],用户 在互联网上随机浏览网页,那么网页的重要度和网页被访问的概率成正比,得 到的PR值就是网页被访问的概率和网页排序的依据。如图有6个页面A、B、 C、D、E、F,假如初始PR值都是1,那么:
图中页面节点重要度排名依次是B、A、C、E、F、D,图2.7所示的有向 图是一种非常理想的情况,节点的重要度只能沿着有向边进行传递,是否任何 有向图经过反复迭代后会达到平稳状态呢?显然不会,由若干个节点组成的有 向图中,如果存在以下3种情况,那么节点的PR值将不会收敛。
①如果存在强连通图(图中任意节点相互可达)只有入链没有出链,我们 称这种情况为等级下沉(Rank sinks)如图2.9所示,网页节点D、E、F组成的
强连通图只有入链没有出链,那么来自其他节点的PR值进入强连通图后会一 直停留,无法进入节点A、B、C。最终的结果是节点D、E、F的PR值会一直 增大,直到节点A、B、C的PR值为0,那么PR值的计算将失去意义。
②如果有向图中存在节点F只有链入的页面节点,并且出度为0,如图2.10 所示,我们称之为等级泄露(Rank leaks),那么页面访问将被困在页面节点F, 页面节点A、B、C、D、E的PR值终将会变为0,而节点F的PR值将达到最 大,显然这种情况也无法通过迭代获得平稳的PR值。
③有向图中存在节点F的出度和入度都为0,我们称之为孤立节点,如图 2.11,那么按照公式(2.4),节点F的PR值将会为0,但是页面F还有被用户 访问的可能,显然PR值为0不符合实际。
其中PR (A)为网页A的PR值,n为总页面的数量,'、、...'代表能够链入A的页面,CCX)为页面节点\的出度,d为阻尼因子,它是为了避免等级 下沉或登记泄露而设立的缓冲因子,它代表页面沿着链接方向进行传递的概率为d,谷歌公司一般取为d=0.85,每条链接对应传递的PR值都是 考虑到孤立节点的存在,赋予每个页面节点一个PR初始值^^。
2.3.3PR值的矩阵化计算
当有向图中节点比较少时,可以通过解方程组的方式进行节点的PR值计 算,但是当节点数量比较庞大时,这种方法就显得难以实现。Pagerank算法假 设用户所浏览的网页与过去的浏览历史无关,依赖现有的浏览状态,可以看作
是一个马尔可夫过程,那么对于n个页面和链接关系组成的有向图G = (V,E),
其邻接矩阵C中元素为1的个数为有向图的链接数,将矩阵C每行元素除以此 行元素的总和(行元素全为0除外)会得到一个矩阵C',矩阵Cf每行元素之 和都为1,那么矩阵C'可以看作是马尔科夫转移概率矩阵。图2.7所示的有向 图的邻接矩阵及转移概率矩阵分别为:
若指定一个n维向量P,向量的分量分别代表各个网页节点的PR值,Px+1表
示第(x+1)次迭代所得到的各个网页的PR值所组成的(nxl)矩阵,用概率转 移矩阵计算PR值的公式为:
其中E为(nxl)阶矩阵并且元素全为1,设S为指定的迭代收敛平稳阀值, 取各网页节点的初始PR值P1,迭代计算当满足|PX+1-PX|<S时,迭代结束。 所以Pagemnk算法的实现过程可以通过如图2.12所示的算法流程图来进行刻画。
本文采摘自“基于故障率相关的加工中心的可靠性及风险评估”,因为编辑困难导致有些函数、表格、图片、内容无法显示,有需要者可以在网络中查找相关文章!
本文由伯特利数控整理发表文章均来自网络仅供学习参考,转载请注明!