web数据挖掘__11链接分析.ppt

* * * * 根据链接结构寻找相似网页 * 给定网页P,令R(根集)中t (e.g. 200) 个网页指向P. 从R中获得基集S. 在S上运行 HITS. 返回S中最好的权威网页作为P的最相似网页. 相似网页结果 * Given “” Strengths and weaknesses of HITS * Strength: its ability to rank pages according to the query topic, which may be able to provide more relevant authority and hub pages. Weaknesses: It is easily spammed. It is in fact quite easy to influence HITS since adding out-links in one’s own page is so easy. Topic drift. Many pages in the expanded set may not be on topic. Inefficiency at query time: The query time evaluation is slow. Collecting the root set, expanding it and performing eigenvector computation are all expensive operations PageRank与Hits算法 * 它们都利用了网页和超链组成的有向图，根据相互链接的关系进行递归的运算。 但是，两者又有很大的区别，主要在于运算的时机 Google是在网页搜集告一段落时，离线的使用一定的算法计算每个网页的权值，在检索时只需要从数据库中取出这些数据即可，而不用做额外的运算，这样做的好处是检索的速度快，但丧失了检索时的灵活型。 HITS使用即时分析运算策略，每得到一个检索，它都要从数据库中找到相应的网页，同时提取出这些网页和链接构成的有向子图，再运算获得各个网页的相应链接权值。这种方法虽然灵活性强，并且更加精确，但在用户检索时进行如此大量的运算，检索效率显然不高。 Road map * Introduction Social network analysis PageRank HITS Summary 链接分析技术小结 * 提供了一种衡量网页质量的客观方法 独立于语言，独立于内容，不需人工干预就能自动发现WEB上重要的资源 挖掘出WEB上重要的社区，自动实现文档分类 链接分析技术小结（影响因素） * 根集的质量。根集质量应该是很高的，否则，扩展后的网页集会增加很多无关的网页，产生主题漂移，主题泛化等一系列的问题，计算量也增加很多。算法再好，也无法在低质量网页集找出很多高质量的网页。 噪音链接。WEB上不是每个链接都包含了有用的信息，比如广告，站点导航，赞助商，用于友情交换的链接，对于链接分析不仅没有帮助，而且还影响结果。如何有效的去除这些无关链接，也是算法的一个关键点。 查询的分类。每种算法都有自身的适用情况，对于不同的查询，应该采用不同的算法，以求获得最好的结果。因此，对于查询的分类也显得非常重要。 * * * * * * * * * * * * * * * * * * * * * * * * * PageRank 根据社会关系网中的等级权威值，网页i的重要程度（它的PageRank）由指向它的其他网页的PageRank之和决定 由于一个网页可能指向许多其他的网页，那么PageRank值将被所有他所指向的网页所共享 * Initial PageRank Idea * 初始化网页p排序公式: Nq 是网页q链出总数. 网页q, 将它权威性的值平均分给它指向的网页（例如p）. c 是归一化常数集. Initial PageRank Idea (cont.) * PageRank 处理过程. .1 .09 .05 .05 .03 .03 .03 .08 .08 .03 初始算法 * 迭代排序过程直到收敛: S为网页集合 初始化 ?p?S: R(p) = 1/|S| 直到排序不再改变 或者两次结果之差小于一定阈值(convergence) For each p?S: For each p?S: R(p) = cR′(p) (normalize) 初始算法的问题 * ?如果有2个相互指向的网页a，b,他们不指向其它任何网页，另外有某个网页c，指向a，b中的某一个，比如a，那么在迭代计算中，a，b的rank值不分布出去而不断的累计。如下图： 随机冲浪模型(Rando