数据挖掘的链接分析

　　链接分析最重要的应用是搜索引擎. 此外，在纸张检索和社交网络中也有应用.

　　1. 您拥有哪些链接分析技术？

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

　　3. PageRank进行了哪些改进？考虑什么因素？

　　4. 什么是链接作弊技术？如何消除这些作弊行为？

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

　　1. 您拥有哪些链接分析技术？

　　1）倒排索引: 第一代搜索技术将网页数据分解为关键字项，然后根据关键字建立索引，并通过关键字索引找到相应的网页. 此外，还有非主要属性值，称为次要键值. 具有反向索引的文件称为反向文件，反向文件中的辅助关键字索引称为反向表. 在倒置的表中，您可以执行诸如合并和相交集合之类的操作，然后在获得结果之后对记录进行操作.

　　2）PageRank: 注意链接的进度和出度，即此网页与其他网页之间的关系，并计算PR值以确定该网页的重要性. 该术语是搜索引擎查询的另一个基础，可以说它是第一个过滤项.

　　3）HITS: 分析网页的导航和权限，以确定网页的作用.

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

　　一个有向图，每个顶点都有一个入度和出度，并附有一个网页跳转概率. 此类图的关系由矩阵表示，以形成网络过渡矩阵M.

　　冲浪者（互联网用户）位置的概率分布可以用n维向量v来描述，其中第j个分量代表第j个网页上冲浪者的概率.

　　v1 = M * v0，这意味着冲浪者经历了操作/跳跃的步骤. 当冲浪者经历了许多跳跃时，冲浪者的分布接近极限，即v = M * v，冲浪者的位置分布不再改变.

　　此时，v只是M的特征向量.

　　PageRank的出现是受到引文分析的启发.

　　PageRank是一种概率分布，其值的计算需要一个迭代过程.

　　普通PageRank的结构有两个问题:

　　1）终结点现象，即某些顶点仅具有入度，而没有出度，因此当它们到达网页时，冲浪者将消失并且不再出来.

　　2）蜘蛛陷阱: 进入一组网页后，它们仅在内部相互跳转，而从不指向外部网页. 结果，冲浪者仅在进入后才出现在这组网页中，而不能离开.

　　两个问题都可以通过“税收”解决.

　　解决方案:

　　1）终端问题:

　　a. 删除端点，但可能会创建更多端点或孤立的子图.

　　b. 修改随机冲浪者的冲浪过程，即“税收”. 与采集器陷阱的处理方法相同

　　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为A偏向的新冲浪者向量，它将属于同一主题的所有成分设置为1，将其他成分设置为0，从而形成偏向的转移模型. 迭代计算得出的最终PageRank值是主题的PageRank值.

　　4. 什么是链接作弊技术？有多有害？如何消除这些作弊行为？

　　链接欺骗，如果您尝试提高网页/网站的PageRank值.

　　该怎么做？通常有两种方法:

　　1）构建一些自建网页，并指向一些需要欺骗的网页链接，即自建农场，通常称为垃圾场；

　　2）通过其他网页的消息功能，在消息中放置作弊链接，例如，请参见...

　　作弊有多有害？

　　使用一个简单的模型来得出垃圾邮件网页的pagerank值的计算:

　　假设某个目标网页的pagerank值为y，则内部链接了m个网页. 如果“税收”的参数为b，通常为0.85，则支持/链接到垃圾邮件的网页的pagerank值为

　　b * y / m +（1-b）/ n

　　如果外部垃圾邮件支持目标网页的值为x，内部垃圾邮件支持网页的值为b * m *（b * y / m +（1-b）/ n），则红色部分是每个所支持网页的pagerank值（m个网页）乘以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）TrustRank；使用面向主题的PageRank来降低垃圾邮件网页的pagerank值.

　　2）垃圾邮件数量，用于识别可能是垃圾邮件的网页，并允许搜索引擎删除或降低这些网页的pagerank值.

　　TrustRank:

　　有两种获取主题网页的方法:

　　a. 手动检查一系列网页，以确定哪些是可靠的. 您可以先将pagerank过滤为要调查的前几个网页，因此，很难通过作弊来达到前几个.

　　b. 选择受限域名. 这些域名具有很高的信誉度，例如.edu. ，. gov. 网页

　　垃圾邮件数量:

　　首先，计算普通pagerank值r和Trust主题pagerank值t（偏向随机游走模型）

　　然后，可以计算每个网页p的垃圾邮件程度: （rt）/ 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个网页的度值和导航度值的权限.

　　每个网页的导航程度等于链接页面的权限的累积，并且每个网页的权威性等于链接页面的导航的权限. 并确保规范化.

　　这将形成回归方程式: “导航页面将指向许多权威页面，而权威页面将由许多导航页面指向. ”从本质上讲，它仍然是矩阵向量迭代乘法运算.

　　如果网页的链接矩阵为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的解决方案. 因此，无需建立税收征管机制.