数据挖掘之复杂类型数据的挖掘学习笔记（3）

Web 挖掘

万维网目前是一个巨大，分布广泛，全球性的信息服务中心，它涉及新闻，广告，消费信息，

金融管理，教育，政府，电子商务，和许多其他信息服务。Web 还包含了丰富和动态的超链接信息，以及Web 页面的访问和使用信息，这为数据挖掘提供了丰富的资源。然而基于以下的分析，Web 对有效的资源和知识发现还是具有极大的挑战性。

 

<对有效的数据仓库和数据挖掘而言，Web 似乎太庞大了。Web 的数据量目前以兆兆字节

（terabytes）计算，而且仍然在迅速地增长。许多机构和社团都在把各自大量的可访问信息置于网上。这使得几乎不可能去构造一个数据仓库来复制，存储，或集成Web 上的所有数据。

< Web 页面的复杂性远比任何传统的文本文档复杂的多。Web 页面缺乏同一的结构，它包含了远比任何一组书籍或其它文本文档多得多的风格和内容。Web 可以看作一个巨大的数字图书馆；然而，这一图书馆中的大量文档并不根据任何有关排列次序加以组织。它没有分类索引，更没有按标题，作者，扉页，目次等的索引。对在这样一个图书馆中搜索希望得到的信息是极具挑战性的。

< Web 是一个动态极强的信息源。Web 不仅以极快的速度增长，而且其信息还在不断地发生着更新。新闻，股票市场，公司广告，和Web 服务中心都在不断地更新着各自的页面。链接信息和访问记录也在频繁地更新之中。

< Web 面对的是一个广泛的形形色色的用户群体。目前因特网上连接有约五千万台工作站，其用户群仍在不断地扩展当中。各个用户可以有不同的背景，兴趣，和使用目的。大部分用户并不了解信息网络结构，不清楚搜索的高昂代价，极容易在“黑暗”的网络中迷失方向，也极容易在“跳跃式”访问中烦乱不已和在等待信息中失去耐心。

< Web 上的信息只有很小的一部分是相关的或有用的。据说99%的Web 信息相对99%的用户是无用的。虽然这看起来不是很明显，但一个人只是关心Web 上的很小很小一部分信息确是事实，Web 所包含的其余信息对用户来说是不感兴趣的，而且会淹没所希望得到的搜索结果。

 

目前基于关键字的搜索引擎存在一些问题。首先，对任一范围的话题，都可能很容易地包含成百上千的文档。这会使得搜索引擎返回的文档数过于庞大，其中很多与话题的相关性并不大，或所包含的内容质量不高。其次，很多与话题相关的文档可能并不包含相应的关键字。这被称为多义问题

 

 

挖掘Web 链接结构，识别权威Web 页面

“什么是‘权威’(authoritative) Web 页面？”假设要搜索某一给定话题的Web 页面，例如金融投资方面的页面。这时我们希望得到与之相关的Web 页面外，还希望所检索到的页面具有高质量，或针对该话题具有权威性。

 

“但是搜索引擎如何能够自动找出话题的权威Web 页面？”这里基于了一个有意思的发现，即权威性（authority）可由Web 页面链接来反映。Web 不仅由页面组成，而且还包含了从一个页面指向另一个页面的超链接。超链接包含了大量人类潜在的语义，它有助于自动分析出权威性语义。当一个Web 页面的作者建立指向另一个页面的指针时，这可以看作是作者对另一页面的注解。把一个页面的来自不同作者的注解收集起来，就可以用来反映该的页面的重要性，并可以很自然地用于权威Web 页面的发现。因此，大量的Web 链接信息提供了丰富的关于Web 内容相关性，质量，和结构方面的信息，这对Web 挖掘是可以利用的一个重要资源。

 

与杂志的引用率不同，Web 链接结构具有特殊的特征。首先，不是每一个超链接都具有注解性。有些链接是为其它目的而创建的，如为了导航或为了付费广告。总体上，若大部分超链接具有注解功能，就可以用于权威判断。其次，基于商业或竞争的考虑，很少有Web 页面会指向其竞争领域的权威页面。

 

由于Web 链接结构存在这些局限性，人们提出了另外一种重要的Web 页面，称为hub。一个hub 是指一个或多个Web 页面，它提供了指向权威页面的链接集合。Hub 页面本身可能并不突出，或着说可能没有几个链接指向它们。但是，hub 页面却提供了指向就某个公共话题而言最为突出的站点链接。此类页面可以是主页上的推荐链接列表，例如一门课程主页上的推荐参考文献站点，或商业站点上的专业装配站点。Hub 页面起到了隐含说明某话题权威页面的作用。通常，好的hub 是指向许多好的authority 的页面；好的authority 是指由许多好的hub 所指向的页。这种hub 与authority之间的相互作用，可用于权威页面的挖掘和高质量Web 结构和资源的自动发现。

 

“那么，如何利用hub 页去找出权威页？”算法HITS（Hyperlink-Induced Topic Search），是利用hub 的搜索算法，其内容如下。

 

首先，HITS 由查询词得到一初始结果集，比如，由基于索引的搜索引擎得到200 个页面。这些页面构成了根集（root set）。由于这些页面中的许多页面是假定与搜索内容相关的，因此它们中应包含指向最权威页面的指针。故此，根集可进一步扩展为基本集（base set），它包含了所有由根集中的页所指向的页，以及所有指向根集页的页。可以为基本集设定一个上限，如1000 至5000（页），用于指明扩展的一个尺度。

 

其次，是权重传播（weight-propagation）阶段。这是一递归过程，用于决定hub 与authority 权

重的值。值得一提的是，由于具有相同Web 域（即在URL 中具有相同一级域名）的两个页面之间的链接，经常是起到导航的功能，因此对authority 没有贡献，此类链接可以从权重传播分析中去除。

 

Web 文档的自动分类

在Web 文档自动分类中，基于一组预先分类好的文档，可以从予定义好分类目录中为每一文档赋予一个类标签。例如，Yahoo!的分类和其相关文档可以作为训练集，用于导出Web 文档分类模式。这一模式可以用于对新的Web 文档加以分类。

 

Web 使用记录的挖掘

“什么是 Web 使用记录的挖掘（Web usage mining）？”除了Web 内容和Web 链接结构，Web 挖掘的另一个重要任务是Web 使用记录挖掘，它通过挖掘Web 日志记录，来发现用户访问Web 页面的模式。通过分析和探究Web 日志记录中的规律，可以识别电子商务的潜在客户，增强对最终用户的因特网信息服务的质量和交付，并改进Web 服务器系统的性能。

 

Web 服务器通常保存了对Web 页面的每一次访问的（Web）日志项，或叫Weblog 项。它包括了所请求的URL，发出请求的IP 地址，和时间戳。对基于Web 的电子商务服务器，保存了大量的Web访问日志记录。热点的Web 站点每天可以记录下数以百兆的Weblog 记录。Weblog 数据库提供了有关Web 动态的丰富信息。因此研究复杂的Weblog 挖掘技术是十分重要的。

 

在开发Web 使用记录挖掘技术中，我们可能要考虑如下问题。首先，虽然Weblog 分析可以设想出许多激动人心的潜在应用，但重要的一点是此类应用的成功要依赖于从这一巨大原始日志数据中能够发现什么样可靠和有效的知识，有能发现多少。通常，原始的Weblog 数据需要经过清洗，精简，和转换，以便于检索和分析有意义和有用的信息。原则上，这些预处理方法与第3 章中讨论的类似，只不过经常需要定制的预处理方法。

 

其次，基于URL，时间，IP 地址，和Web 页面内容信息，可以在Weblog 数据库上构造多维视图，进行多维分析OLAP 分析，用于找出头N 个用户，头N 被访问页面，最频繁访问时间期，等等，这有助于发现潜在客户，市场等。

 

第三，在Weblog 记录上可以进行数据挖掘，用于找出关联模式，序列模式，和Web 访问趋势等。对Web 访问模式挖掘，通常需要采用进一不的手段获得用户访问的附加信息，以便于做更为详细的Weblog 分析。此类附加信息一般包括Web 服务器缓冲中，用户浏览Web 页面的序列等等。