Data mining for hypertext: A tutorial survey（超文本数据挖掘综述）
Soumen Chakrabarti
Indian Institute of Technology Bombay
soumen@cse.iitb.ernet.in
张凯 王斌 译
{zk,wangbin}@ict.ac.cn
2001年9月
SIGKDD Explorations. Copyright©2000 ACM SIGKDD, Jan 2000. Volume 1, Issue 2
摘要：由于拥有8亿多涉及人类各个领域的网页，Web为数据挖掘的研究提供了肥沃的土壤，这些研究对信息的搜索是十分重要的。现在，网上冲浪者访问Web有两种主要方式：点击超链和通过关键词进行搜索。这种访问常常带有试探性，效果不能让人满意。需要一种更好的方式来表达用户的信息需求，并使用比现有方法更结构化的方法来处理查询结果。为了达到这个目标，数据挖掘和机器学习技术将扮演极其重要的角色。
在这篇论文中，我们将对超文本(特别是Web)中的学习和挖掘技术的最新进展作考查。我们将回顾从有指导的、半指导的以及无指导的学习问题，重点讲述和数据仓库挖掘技术不同的超文本的数据挖掘技术所面临的主要挑战。
1. 引言
目前，文本和超文本的数据量超过了结构化数据。文本和超文本应用于数字图书馆，产品目录，评论，新闻组，医学报告，用户服务报告以及个人、组织和项目的主页等等各个方面。在Web流行之前，超文本已经被广泛应用。一些团体，如ACM SIGIR(http://www.acm.org, http://www.acm.org/sigir),SIGLINK/SIGWEB(http://www.acm.org/siglink),Digital Libraries (http: //www.acm.org/dl)等均从事基于文本和超文本数据库的有效查找和获取的研究工作。
Web信息的快速膨胀使传统的信息检索(IR)技术面临巨大的压力。当前的Web包括超过8亿个HTML页面，大约6万亿字节分布在3百万个服务器上。每天增加约1百万个页面，一般页面在几个月内将被更新，每个月更新几百个G的数据。就是连最大的搜索引擎，如 Alta Vista 和Hotbot,1999年2月时才索引了不到18%的Web页面[49]，而1997年晚期的比例为35%[6]。
不提数据量和流量的大小，互联网和它的用户与传统的信息检索有明显不同。互联网最多只是超媒体的“平民”，没有一致的标准和权威的指示。内容是由不同的人自治产生的，用无意义的词汇“兜售”(spamming)网页的做法非常多，以至于用关键词匹配的方法对这些网页的评价值很高，造成信息的误传。超链是用来“导航”，签注，引用，批评和朴素幻想。
搜索技术是从信息检索中发展而来的，面对新的挑战，它发展得较为缓慢。正象前面所说的，搜索引擎不能索引整个互联网。不只是有范围上的问题，搜索引擎的正确率非常低，它们的召回率(返回的相关文档占所有相关文档的比率)和准确率(返回的相关文档占返回的所有文档的比率)都非常低。文本搜索的一般问题，如多词一义，一词多义和上下文敏感性问题在Web上也变得非常严重。不仅如此，针对现存的网络文本的部分结构，需要加入一维来进行处理。 因为IR技术主要针对文档(document)，而Web提供的是有向图形式的半结构化数据，其节点是简单或者复杂的对象，边是域标记(tag?)。
除了IR团体之外，有很多语言学家和计算语言学家也研究文档和自然语言(NL)的应用。现在的NL技术能够分析良结构(well-defined)的句子[36,71,28,68]，较好地消除多义词歧义[3,62,11]，在连续文本中标记出词性(part-of-speech)信息[3,32]，写出规范的机器可识别的自然语言文档[67,40,65]，并进行自然语言翻译[39,5,4]。自然语言和信息检索技术的结合可以用来自动生成超链[9,2,35,46,12]，用相关词汇扩展查询。由于一些未知的原因，流行的Web搜索引擎在这些方面进展缓慢。尽管我们认为更好的语义理解是一个发展趋势，NLP仍然不在本文的讨论范围之内。
提纲：本文中我们将集中讨论如何用统计学技术从文本、超文本、半结构化数据中学习出不同形式的结构。
模型：在第二节中，我们将讨论一些用来表示超文本和半结构化数据的模型。
有指导的学习：在第三节中，我们讨论有指导的学习和分类的技术。
无指导的学习：在第四节中，我们讨论无指导的学习和聚类的技术
半指导的学习：实际的应用常常介于完全指导和无指导之间，我们称之为半指导的学习，我们将在第五节中讨论
社会网络分析：它是区分超文本挖掘和数据挖掘的一个关键特征。很多检索技术就是对超链中的结构化数据的分析。
2. 基本模型
严格来说，文本的模型必须建立对客观世界知识的机器表示，必须引入自然语言语法。既然我们将我们的工作限定于统计学的分析，我们需要找到满足应用的对文本，超文本和半结构化数据的合适的表示。下面我们来讨论这个问题。
2.1 文本的模型
在IR领域，文档传统上是用向量空间模型来表示的[63,29]。对于一篇文档，先用一些简单的句法规则(如英语中以空白作为间隔符)从文本中提取token(可能是一个或者多词)，然后将这些token进行词干还原(stem)，变成规整的形式(如reading->read, is,was,are->be)。每个规整的形式(term，项)表示欧氏空间的一个坐标轴。每个文档是该空间的一个向量。在最初的形式中，如果一个项t在文档d中出现n(d,t)次，则文档d的第t个分量为n(d,t)。可以选择让每个文档的长度正规化为1，一般用L1,L2,..等形式。||d||1= ，||d||2= ,||d||∞=maxtn(d,t)
这种表示方法并没有考虑到在决定文档类型时某些词汇(如algebra)可能比其他词汇(如 the或者is)更重要。如果t在N篇文档中的Nt篇中出现，Nt/N就表示一种词汇的稀有性，即词汇的重要性。IDF(t)=1+log 使各个轴按照不同的比例伸长。（这个公式有很多变种，这个形式只是说明性的）这样d的第t个坐标值是 一般叫做“TFIDF”(term frequency times inverse document frequency)向量空间模型
另外，还可以为文本生成(text generation)建立概率模型。我们不承诺这些模型与语法及语义一致性无关。最简单的统计模型是二值(binary)模型(要么出现，要么不出现)。在这个模型中，一个文档是项(term)的集合，它是词典(所有term组成的集合)的一个子集，每个term的出现次数并不重要。在多值(multinomial)模型中，你可以想象一个骰子，它有很多面，就像词典中的词数那么多，在投掷的时候，每个面t都有一个出现概率θt，为了写一篇文档，作者首先固定好词数，然后每掷一个骰子就根据骰子朝上的那面对应的term写一个term。
这些方法虽然显得有一些粗糙，没有考虑到语言和语义的任何方面，但是它们在所处理问题中的效果却不错。所有这些方法尽管有小的差异但都把文档看作是term的集合，完全不管term之间的顺序。所以它们都称为“词袋”(bag-of-words)模型。
2.2 超文本的模型
超文本是在文本的基础上加上超链而成。根据不同的应用，有不同层次细节的模型。最简单的，超文本可以看作是一个有向图(D,L),D是节点、文档或者页面的集合，L是链接的集合。粗糙的模型不需要在节点中引入文本的模型。较精确的模型可以刻画一个节点和其特定邻居的term的联合分布状态。有人认为源文档实际上是一个项的序列，点缀着一些超链。这个可以用来建立链接和项之间的特定关系。
有时我们把文档看作是由特定主题的term分布而生成的。例如，与自行车有关的文档，其term的分布状态和考古学的完全不同。与考古学和自行车的杂志不同，Web不是孤立的，不同领域的节点可能会相互链接，（我们发现娱乐自行车网页较经常指向急救网页）。如果这种联系有正当理由，需要对这样的主题之间的关系建模。
2.3 半结构化数据的模型
除了超链，Web上还有另外的结构存在于文档内部和文档之间。一种常见的文档之间的结构是主题目录，如Open Directory Project(http://dmoz.org)和Yahoo(http://www.yahoo.com)。这种服务是通过人力构建的巨大主题目录分类树。每个目录有很多超链指向相关的站点(这些站点通常比较流行或者权威)。我们可以用is-a（特定主题,普遍主题）和example(主题，URL)这两种关系构建树形层次模型。尽管主题分类树是半结构化数据的典型例子，还是经常需要把它们区分开。
半结构化数据是Web(http://www9.org)和数据库研究团体(http://www.acm.org/sigmod)的结合点[25]：前者处理文档，后者处理数据。数据的形式由严格的结构关系表发展而来，这些关系表带有数值和字符串，能够自然地表示包括书，论文，电影，飞机引擎部件，芯片设计图等在内的复杂的客观事物，而不增加程序人员的负担。新出现的半结构化数据的自然表示(如XML，http://www.w3.org/XML/)是对象交换模型(Object Exchange Model，OEM，http://www-db.stranford.edu/~widom/xml-whitepaper.html)[54,33]的变种。在OEM中，数据是以原子或者组合对象的形式存在的，原子对象可能是整数或者字符串，组合对象通过带标记的边指向其他对象。HTML就是这种文档内结构(intra-document)的典型例子。
以上的非正规的结构推动数据挖掘技术从标准的结构化的数据仓库领域经过调整、扩展转向更适合于发现半结构化数据中的有用模式。
3. 有指导的学习
有指导的学习，又叫做分类，学习者首先从训练集合里接受数据，该集合的每项都有类别标记。学习算法利用这些数据进行训练，然后再对未分类的数据猜测其类别。
分类在超文本和半结构化数据中有很多应用。网上冲浪者使用主题目录，是因为它可以结构化和限定关键词搜索的范围，使查找更容易，举例来说，要查找限定与服饰而不是安全代理协议(http://www.socks.nec.com)有关的socks相关的文档 (用socks AND NOT network检索将丢失掉很多讲销售网络的服装站点) 。健壮的超文本分类可以用于管理电子邮件及新闻组和维护Web站点。
另外一个例子，一个将教员、学生和项目网页进行分类处理的校园搜索引擎可以响应在关键词上增加某一属性的查询(如查找喜欢骑自行车的教员)。进一步，通过学习不同类别网页之间的关系(advised-by, investigation-of)，可以提供进行更强大的搜索(如找出指导硕士研究生数大于系里的平均值的教员)。
[返回] 计算机科学论坛 →
计算机技术与应用 → 『 Web挖掘技术 』 → [转帖]超文本数据挖掘综述
(订阅本版)
2007/7/19 21:31:00
新浪微博
[转帖]超文本数据挖掘综述