网页采集器的自动识别算法(1.PageRank哪些链接分析技术？PageRank有哪些改进？)

　　网页采集器的自动识别算法(1.PageRank哪些链接分析技术？PageRank有哪些改进？)

　　链接分析最重要的应用是搜索引擎，此外，在论文检索、社交网络等方面也有应用。

　　1. 使用了哪些链接分析技术？

　　2. PageRank技术的基本定义是什么？

　　3. PageRank 做了哪些改进？考虑了哪些因素？

　　4. 有哪些链接作弊技术可用？如何消除这些作弊？

　　5. 什么HITS算法？与 PageRank 有什么区别？

　　1. 使用了哪些链接分析技术？

　　1）倒排索引：第一代搜索技术，将网页的数据分解成关键词项，然后通过关键字构建索引，通过关键字索引找到对应的网页。此外，还有非主属性值，称为次键值。具有倒排索引的文件称为倒排文件，倒排文件中的二级关键字索引称为倒排列表。倒排表可以对集合进行合并、相交等操作，得到结果后再对记录进行操作。

　　2）PageRank：关注链接的入度和出度，即本网页与其他网页的关系，计算一个PR值来判断该网页的重要性。词条是搜索引擎查询的另一个依据，可以说是第一个过滤项。

　　3）HITS：分析网页的导航和权限，判断网页的作用。

　　2. PageRank 的基本定义是什么？

　　一个有向图，每个顶点都有入度和出度，并附有网页跳转概率。这种图的关系用一个矩阵来表示，形成一个web转移矩阵M。

　　冲浪者（surfer）所在位置的概率分布可以用一个n维向量v来描述，其中第j个分量表示冲浪者在第j个网页上的概率。

　　而v1 = M*v0，表示冲浪者经历了一步操作/跳转。当冲浪者进行了多次跳跃时，冲浪者的分布接近一个极限，即v = M*v，冲浪者的位置分布不再发生变化。

　　此时，v恰好是M的特征向量。

　　PageRank 的出现受到了引文分析的启发。

　　PageRank 是一种概率分布，其值是通过迭代过程计算得出的。

　　普通PageRank的结构存在两个问题：

　　1）终止点现象，即有些顶点只有入度没有出度，所以当到达页面时，冲浪者会消失，再也不出来了。

　　2）采集器Trap 蜘蛛陷阱：一组网页，进入后只在内部互相跳转，从不指向外部网页。这样一来，上网者进入后，只会出现在这组页面中，无法离开。

　　这两个问题都可以通过“征税”来解决。

　　解决方案：

　　1）终结点问题：

　　一种。移除终止点，但可能会产生更多的终止点或孤子。

　　湾。修改随机上网者的上网过程，即“征税”。与 采集器 陷阱处理相同

　　2）采集器陷阱：

　　它也是以税收方式处理的，允许每个随机冲浪者以很小的概率随机跳转到一个随机网页。也就是说，v = b*M*v + (1-b)*e/n，b 是一个选定的常数，通常在 0.8 和 0.9 之间。e 是所有分量都等于 1 的向量，n 是图中所有节点的数量。

　　b*M*v 表示随机冲浪者以概率 b 选择出口跳转的情况，(1-b)*M*e/n 表示随机新冲浪者以概率 (1-b) 选择用户访问.

　　这避免了陷阱和终止点问题。

　　3. 什么是面向主题的 PageRank？它解决了什么问题？

　　先来说说问题的根源。纯pagerank算法只考虑网页本身的因素，没有考虑用户自身的习惯、喜好等因素。每个人都有自己的特点。如果考虑到这些因素，那么PageRank会更准确。所以每个人都得存储自己的PageRank，但是这是不可能的，因为PageRank向量本身就是巨大的n，而每个人m都有唯一的PageRank，所以需要的空间是n*m。所需的存储空间太大，没有必要。并且记录客户的历史操作，很容易触发用户隐私问题。

　　如何考虑用户偏好？

　　即使用面向主题的PageRank对网页进行分类，如体育、娱乐、政治、经济、军事等，每类网页都有一个PageRank值，每个用户只需要保留每一个的特征数据网页类型。每个类别的网页都使用面向主题的 PageRank 来表示。

　　解决方案：

　　有偏的随机游走模型，面向主题的PageRank与普通的PageRank类似，即v = b*M*v + (1-b)*Se/|S|，区别在于Se是有偏的的新冲浪者向量，将属于同一主题的所有组件设置为1，将其他组件设置为0，从而形成有偏差的转换模型。迭代计算出的最终PageRank值就是PageRank值。

　　4. 有哪些链接作弊技术可用？有多危险？如何消除这些作弊？

　　链接作弊，如果你想办法提高自己页面的PageRank/网站。

　　怎么做？一般有两种方式：

　　1）自己建一些网页，并指向一些需要作弊的网页的链接，即自建Farm，俗称垃圾场；

　　2）通过其他网页的留言功能，将作弊链接放入留言中，如果好的话，关于...，请看

　　作弊有多危险？

　　一个简单的模型用于推导垃圾页面的 pagerank 值的计算：

　　假设目标页面的pagerank值为y，并且有m个页面链接到它。如果“抽税”的参数为b，一般为0.85，则支持/链接垃圾页面的pagerank值为

　　b * y / m + (1 - b) / n

　　如果外部启用垃圾邮件的目标页面的值为x，内部启用垃圾邮件的页面的值为b * m * (b * y / m + (1 - b) / n)，红色部分就是上面每一个支持页面m个页面的pagerank值乘以m。

　　那么 y = x + b * m * (b * y / m + (1 - b) / n) = x + (b^2) *y + b * (1-b) * m / n,求解方程：

　　y = x / (1 - b^2) + c * m / n，并且 c=b/(1+b)

　　b 的值为 0.85，则 1/(1-b^2) = 3.6, c = 0.46. 因此，使用这个这种方法可以将外部链接的效果放大3.6倍，加上0.46倍的m/n所有垃圾网页与所有网页的比例。

　　如何杜绝作弊？

　　彻底消除是不可能的，新的作弊手段不断涌现。

　　常用方法：

　　1）信任等级；使用面向主题的 PageRank 来降低垃圾网页的 pagerank 值。

　　2）垃圾邮件质量，即识别潜在的垃圾网页，允许搜索引擎删除或降低这些网页的pagerank值。

　　信任等级：

　　获取主题页面有两种方式：

　　一种。人工检查一系列网页以确定哪些是可靠的。您可以先筛选排名靠前的页面。因此，通过作弊获得最高排名更加困难。

　　湾。选择比较可信的受限域名，如.edu.、.gov。页面

　　垃圾邮件质量：

　　首先，计算正常的pagerank值r，以及Trust topic pagerank值t（有偏随机游走模型）

　　然后，可以计算出每个网页p的垃圾邮件程度：(r - t)/r，如果接近1，则表示该网页p可能是垃圾网页；如果它很小且接近于 0，则表示网页 p 不是垃圾网页。r的值接近t，即如果网页普通pagerank的计算值与主题pagerank的计算值相近，则可靠性高。否则，它的 pagerank 值可能是由一些垃圾网页贡献的。

　　5. 什么HITS算法？与 PageRank 有什么区别？

　　“导航页面和权威页面”的计算方式与pagerank类似，通过矩阵向量方法迭代，直到收敛点。其算法也称为HITS算法。

　　pagerank 考虑网页重要性的一维重要性信息，而 HITS 则认为网页具有二维重要性信息：

　　1）权威页面：提供某个主题的信息并且具有非常重要的信息的页面称为权威页面。

　　2）导航页面：不提供主题信息但可以找到有关主题信息的页面称为导航页面。

　　表示：每个网页都有一个权限和导航属性。如果用h和a来表示网页的两个属性，那么h和a的第j个分量分别代表第j个网页的权限值和Navigation值。

　　每个网页的导航度等于其链接页面的权威度的累积，每个网页的权威度等于其链接网页的导航度的累积。并保证正常化。

　　这样就会形成一个回归方程：“导航页面会指向很多权威页面，权威页面会被很多导航页面指向”。本质上，它仍然是一个迭代的矩阵向量乘法运算。

　　如果网页的链接矩阵为L，导航度向量为h，权威度向量为a。

　　那么 h = d* L * a，其中 d 是一个常数，

　　和 a = u * Lt * h，其中 Lt 是 L 的转置。L 是一个 0-1 矩阵。

　　由上述重叠运算方法推导出：

　　h = d * u * L * Lt * h

　　a = d * u * Lt * L * a

　　由于L*Lt的解不方便，所以h和a最好是重叠计算，每次计算都需要归一化。

　　但是端点和 采集器 陷阱不会影响 HITS 的解决方案。所以没有必要建立税收制度。