免规则采集器列表算法(2019独角兽企业重金招聘Python工程师标准(gt)(图))

　　免规则采集器列表算法(2019独角兽企业重金招聘Python工程师标准(gt)(图))

　　2019独角兽企业招聘Python工程师标准>>>

　　一、简单的PageRank计算

　　首先，我们将Web抽象如下： 1、将每个网页抽象成一个节点；2、如果页面 A 有直接到 B 的链接，则从 A 到 B 存在有向边（多个相同链接不重复计算边）。因此，整个 Web 被抽象为一个有向图。

　　现在假设世界上只有四个网页：A、B、C、D。抽象结构如下图所示。显然，这个图是强连接的（从任何节点，你可以到达任何其他节点）。

　　然后需要使用合适的数据结构来表示页面之间的连接关系。PageRank算法就是基于这样一个背景思想：随机上网者访问的页面越多，质量可能就越高，而随机上网者在浏览网页时主要通过超链接跳转到页面，所以我们需要分析构成的超链接。图结构用于估计每个网页被访问的频率。更直观地说，一个网页的 PangRank 越高，随机浏览者在浏览该网页的过程中停留在该页面的概率就越大，该网页的重要性就越高。

　　为简单起见，我们可以假设当一个随机的冲浪者停留在一个页面上时，跳转到该页面上每个链接页面的概率是相同的。比如上图中，页面A链接到B、C、D，所以用户从A跳转到B、C、D的概率各为1/3。假设总共有N个网页，可以组织一个N维矩阵：第i行第j列的值代表用户从第j页到第i页的概率。这样的矩阵称为转移矩阵。上图中四个网页对应的转移矩阵M如下：

　　那么，假设随机浏览者从n个页面出来的初始概率相等，那么初始概率分布向量是一个n维的列向量V0，每个维度为1/n。这里我们有 4 页，所以 V0-1=[1/4, 1/4, 1/4, 1/4]。

　　这样，我们就可以从初始向量 V0 开始，不断地将转移矩阵 M 左乘。用户在浏览网页时主要通过超链接使i跳转后，停留在每个页面的概率为：Mi*V。停止直到最后两次迭代在结果向量中产生非常小的差异。实际上，对于 Web，50 到 75 次迭代足以收敛，误差控制在双精度。

　　以下是前四次跳转时每次迭代后每个页面的PageRank值：

　　可以看出，随着迭代次数的增加，网页A的PageRank值越来越大，接近其极限概率3/9。这也说明随机上网者停留在A页面的概率大于B、C、D页面，页面也更重要。

　　二、问题一：死胡同

　　终止点是没有出链的点，比如下图中的C。

　　如果我们不对其进行处理，让终止点存在，那么随着PageRank迭代次数的增加，每个网页的PageRank值会趋于0，这样就无法得到网页相对重要性的信息.

　　通过从图中删除它们及其传入链来处理终止。这样做之后，可以生成更多的端点，并继续迭代消除端点。但最终我们得到了一个强连通子图，其中所有节点都是非终端的。我们以左图为例进行说明。按照上述步骤消除终止点后得到左图，得到右图。

　　我们得到右图对应的转移矩阵，计算图中A、B、C的PageRank值。

　　我们得到A、B、C的PageRank值分别为2/9、4/9、3/9，然后按照删除的逆序计算C、E的PageRank值. 由于 C 是最后被删除的，因此首先计算 C 的 PageRank 值。A有3个外链，所以它贡献了1/3的PageRank值给C。D有3个外链，所以它贡献了1/2的PageRank值给C。所以C的PageRank为

　　. E的入链只有C，C的出链只有E，所以E的PageRank值等于C的PageRank值。

　　需要注意的是，当前所有节点的PageRank值之和已经超过1，因此不能代表随机浏览者的概率分布，但仍能反映对页面相对重要性的合理估计。

　　三、问题2：采集器蜘蛛陷阱

　　采集器陷阱是一组节点，虽然它们都不是终止点，但它们都没有出链指向该集合之外的其他节点。采集器 陷阱导致计算时将所有 PageRank 值分配给 采集器 陷阱内的节点。

　　如下图所示，C是一个单节点采集器陷阱及其转移矩阵。

　　随着迭代的进行，C 的 PageRank 值趋于 1，而其他不在 采集器 陷阱中的节点的 PageRank 值趋于 0。

　　采集器 陷阱的处理方式是允许每个随机浏览者随机跳转到一个随机页面，跳转概率很小，而不必遵循当前页面上的外链。因此，根据上一次PageRank估计值V和转移矩阵M估计下一次迭代后的PageRank值V'的迭代公式变为：

　　其中 β 是一个选定的常数，通常介于 0.8 和 0.9 之间。e 是一个向量，其分量全为 1，维度为 n，其中 n 是 Web 图中所有节点的个数。βMv 表示随机冲浪者以概率 β 从当前网页中选择外链向前移动的情况。(1−β)e/n 是一个所有分量为 (1−β)/n 的向量，它表示一个新的随机冲浪者具有 (1−β) 概率随机选择要访问的网页。

　　取β=0.8，上图的迭代公式变为：

　　以下是之前迭代的结果：

　　作为一个采集器 陷阱，C 获得了超过一半的 PageRank 值，但这种影响是有限的，并且每个其他节点也获得了一些 PageRank 值。

　　-------------------------------------------------

　　参考：

　　《大数据：互联网*敏*感*词*数据挖掘与分布式处理》王斌老师_ICTIR及其对应英文电子书《海量数据集挖掘》