9.2Web挖掘
Web挖掘
[P1] Web挖掘是数据挖掘技术在Web环境下的应用，是涉及Web技术、数据挖掘、计算机技术、
信息科学等多个领域的一项技术。本节简要介绍Web挖掘的相关概念和技术。
[P2] 这章我们介绍 Web挖掘，分两部分内容介绍。第一部分，我们介绍 Web 挖掘概述，第二部分，我们重点介绍搜索引擎的工作原理，Web结构挖掘的主要算法 PageRank 。
[P3] 首先，什么是Web挖掘。 Web挖掘是指从大量的Web文档集合中发现蕴涵、未知、有潜在应用价值、非平凡的模式。它所处理的对象包括静态网页、Web数据库、Web结构、用户使用记录等信息。通过Web挖掘可以将Web文档分类、抽取主题、分析用户浏览站点的行为特点，以帮助用户获取、归纳信息，改进站点结构，为用户提供个性化服务等。
[P4] 那 Web 挖掘和数据挖掘有什么区别呢？Web挖掘的研究对象是以 半结构化 和 无结构 文档为中心的Web网页，这些数据没有统一的模式，数据的内容和表示互相交织，数据内容基本上没有语义信息进行描述，仅仅依靠 HTML 语法对数据进行结构上的描述，可以说 Web 网页的复杂性远比任何传统的文本文档大。为了对这种半结构化数据进行分析和处理，Web挖掘必须和其他研究手段结合起来。由于涉及很多知识领域，Web 挖掘是数据库、信息获取、人工智能、机器学习、模式识别、统计学、自然语言处理等多个研究方向的交汇点。
[P5] Web挖掘的基本步骤一般有四步。第一步，查找资源：从目标Web文档中得到数据。第二步，信息选择和预处理：从取得的Web资源中剔除无用信息和将信息进行必要的整理。第三步，模式发现：在同一个站点内部或在多个站点之间自动进行模式发现。第四步，模式分析：验证、解释所发现的的模式
[P6] Web挖掘的分类。Web上信息的多样性决定了 Web 挖掘任务的多样性。Web 挖掘的分类方法也有很多，如按 Web 文本的语言分类、按挖掘站点的属性分类等。根据挖掘对象的不同，可以分为 Web内容挖掘、Web结构挖掘 和 Web使用挖掘 三类，如图所示。Web 结构挖掘里面包含 超链接挖掘 和 内部结构挖掘。Web 内容挖掘 又分为 Web文本挖掘、多媒体挖掘。最后，Web使用挖掘 分为 客户挖掘 和 日志挖掘。
[P7] Web挖掘的主要应用有三类，分别是，在搜索引擎中的应用，在电子商务中的应用，在知识服务中的应用。Web挖掘在搜索引擎中的主要应用有 : 网页文本自动分类、权威网页的发现 和 用户兴趣偏好挖掘等。Web挖掘在电子商务中的主要应用有 : 用户的分类与聚类、网站内容的重组、网络流量分配情况、用户访问随时间变化情况分析、用户来源分析等。Web挖掘在知识服务中的主要应用有 : 知识建构、网站广告点击率、访问站点用户的浏览器和平台分析、用户的个性和兴趣挖掘、预测用户可能访问的网页、用户行为趋势分析 和 用户分类等。
[P8] 现在来说，Web 的挖掘最主要的应用还是 Web 结构的挖掘，最典型的应用就是大家每天都在使用的 搜索引擎。Web 结构包括不同网页之间的超链接 和一个网页内部的超链接，以及文档 URL 中的目录路径结构等。Web结构挖掘通常用于挖掘 Web 网页上的超链接结构，即Web超链接结构分析，从而发现那些包含于超文本结构之中的信息，帮助自动推断出那些权威网页，揭示出蕴含于文档结构中的个性化信息。Web 结构挖掘常见的有 PageRank 和 HITS 这两个算法。
[P9] PageRank 算法是 Web 超链接结构分析中最成功的代表之一。该算法由 Stanford 大学的 Brin 和 Page 提出，是评价网页权威性的一种重要工具。搜索引擎 Google 就是利用该算法和 anchor text 标记、词频统计等因素相结合的方法对检索出的大量结果进行相关度排序，将最权威的网页尽量排在前面，网页的权威性就是通过 PageRank 值来度量的。在 Google 中按“数据挖掘”关键字搜索，Google 先按关键字查找到众多满足要求的网页，根据超链接的结构，计算出网页的 PageRank 值，然后依其大小列出相关的网页。PageRank算法的理论基础是 : 忽略Web网页上的文本和其他内容，只考虑网页间的超链接，把Web看成是一个巨大的有向图，只计算这个有向图的入站指向数量。
[P10] PageRank 算法的假设是：若一个网页 a 有到另一个网页 b 的超链接，则认为此超链接是网页 a 的作者对网页 b 的推荐，且两个网页的内容具有相似的主题。如果大量的网页推荐同一个网页，则后者被认为是一个权威网页。所以一个网页的入度越大，其权威就越高。一个拥有高权威值的网页指向的网页比一个拥有低权威值的网页指向的网页更加重要。如果一个网页被其他重要的网页所指向，那么该网页也很重要。我们用一个简单的生活常识来说明 PageRank。在社会中，我们每个人会有认识的人， 我们每个人也会被别人认识，普通人，认识你的人也就是你周围的朋友，顶多100个人差不多了，所以你的权重就是 100， 但是，如果是一个明星，全国认识他的有1亿人，那他的权重就是 1亿。所以，最核心的权重，不是你认识多少人，而是有多少人认识你。网页的 PageRank 权重也一样，最核心的权重是 有多少别的网页通过链接指向你，如果有1亿个网页都指向你这个网页，那你这个网页的权重就是1亿，那这个网页的权重就非常非常高，比如微博这个网站的首页。
[P11] PageRank 值的具体定义如下：将 Web 对应成有向图，令 u、v 为网页，记 Fu 为 u 所指向的网页集合，记 Bu 为指向网页 u 的网页集合。令 Nu 为网页 u 上的链接数，则网页 u 的 PageRank 值 PR(u) 可以简单地定义为课件上的公式。
[P12] 公式的含义是：网页 u 的 PageRank 值等于所有指向它的网页为它传入的 PageRank 值。如果网页 u 上有 Nu 个链接，那么它会把自身的 PageRank 值 PR(u) 平均地传出，即每一个链接传出 PR(u)/Nu。简单的说，如果一个网页初始的 PageRank 值是 100， 并且网页中有 50个链接，那么就分配给每个链接的权重为 2 。 所有的网页都这样操作，把自己的权重平均分配给自己包含的链接。那么，一个网页的权重，就等于它收到别的网页分配给它的权重的总和。一个生活中的比喻，给你捐款的人越多，你拿到的钱就越多， 你的财富就越高，你的权重也就越高。看课件中的图，网页 A 的 PageRank 值等于 B、C、D 分配给它的 PageRank 值的总和，可以想象为 B、C、D 给 A 的捐款的总和。
[P13] 假设 a、b、c 是3个网页，其链接结构如图所示。在开始计算之前先要赋给每个网页一个初始 PageRank 值，注意，初始值的选取不会影响 PageRank 值计算的结果，假设为（0，2.5，2.5）。计算的过程如下
[P14] 首先记住 PageRank 的初始值，a 为 0， b 为 2.5，c 为 2.5，我们后面用 PR 值来简称。现在我们来计算第一次迭代，首先，a 的入站来自 c ，c 的出站只有 1 条，所以，a 的 PR 值等于 c 的 PR值 除以 1 也就是 2.5 ，所以 第一次迭代之后 a 的 PR 值为 2.5 。接下来计算 b ，b 的入站只有来自 a，a 的出站有到 b，c 两条，所以 b 的 PR 值为 a 的初始 PR 值除以 2，a 的初始 PR 值为 0 ，所以 得到 0 除以 2，所以 b 第一次迭代后的 PR 值为 0 。接下来计算 c ，c 的入站有 2条，一条来自 a，一条来自 b，所以 c 的 PR 值需要把这两条入站都累加起来。我们分别来计算这两条入站，首先是来自 a 的入站，a 有2条出站，所以分给 c 的只有 二分之一，也就是 a 的 PR 的 二分之一，由于 a 的初始 PR 为 0，所以这里分给 c 的也只有 二分之一。接着，计算来自 b 的入站，b 的出站只有 1条，所以 b 分给 c 的 PR 就是 b 的 PR 值。最终汇总，c 的 PR 值累加 来自 a 和 b 分配的 PR，最终得到 c 的 PR 值为 2.5 。
[P15] 刚才第一次迭代，我们得到 a，b，c 的 PR 值分别为 2.5，0，2.5 。现在，我们做第二次迭代计算。首先，a 的入站来自 c ， c 的出站只有 1 条，所以 a 的 PR 值等于 c 的 PR 值 除以 1，所以 a 的 PR 值得到 2.5 。接下来，再计算 b 的 PR 值，b 的入站来自 a，a 的出站有 2 条，所以 a 分给 b 的PR 只有 二分之一，所以 b 的 PR 等于 a 的 PR 的二分之一，也就是第一轮 a 的 PR 值的一半，计算出来的是 1.25 。最后，我们计算 c 的 PR 值，c 的入站来自 a 和 b，所以 c 的 PR 值需要累计 a 和 b 分配的 PR 。然后，a 的出站有 2条，所以分给 c 的只有 二分之一，这里就是 2.5 的 二分之一，也就是 1.25 。b 的出站只有 1条，所以 b 的 PR 就分给 c，b 在第一轮迭代的 PR 是 0 ，所以分配给 c 也是 0 。最终，c 的 PR 是两个累加起来，最终 PR 值为 1.25 。最终，第二轮，我们得到 a，b，c 的 PR 分别为 2.5, 1.25，1.25 。按照这个计算方法，继续迭代下去，直到两次迭代的 PageRank 值差异比较小了，我们就停止迭代，完成了算法的收敛。
[P16] PageRank 的算法如课件所示，这里是代码表示的算法，大家课后可以具体查看。
[P17] PageRank 算法的优点是：它是一个与查询无关的静态算法，所有网页的 PageRank 值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。其缺点是：人们的查询具有主题特征，PageRank 忽略了主题相关性，导致结果的相关性和主题性降低，例如，许多链接只是为导航和广告，PageRank 可能错误地计算其重要性；另外，这样计算的结果是旧网页等级总会比新网页高，因为即使是非常好的新网页也不会有很多上游链接，除非它是某个站点的子站点。所以，PageRank 适合对历史网页排序，但是对一些实时性要求比较高的地方不适用，比如搜索新闻，大家都希望看到最新的新闻，所以新闻网页不能用 PageRank 算法，必须用另外的算法。大家可以看看百度新闻的搜索结果，基本上都是最新的新闻排在前面，而不是链接指向多的网页排前面。
[P18] 最后总结一下，这章我们介绍了 Web挖掘。现在是互联网时代，大量的信息都保存在 Web网页中，Web 挖掘目前也是数据挖掘的最大应用，最典型的就是我们每天都在使用的搜索引擎。目前 Web挖掘 中用的最普遍的都是 Web结构挖掘，最重要的算法就是 PageRank 算法。