Web文本挖掘技术研究

关键词　Web挖掘，文本挖掘，文本分类，文本聚类，多维文本分析
中图法分类号　TP391； TP393

Abstract　With the flood of information on the Web, Web mining is a new research issue which draws great interest from many communities. Currently, there is no agreement about Web mining yet. It needs more discussion among scientists in order to define what it is exactly. Meanwhile, the development of Web mining system will promote its research in turn. In this paper, a systemic discussion about the principle of Web mining is presented, including the definition, the relationship between information mining and retrieval on the Web, the taxonomy and function. Then the methods of text mining on the Web are discussed in detail and a prototype of Web text mining system WebMiner is introduced. WebMiner is a multi-agent system which combines text mining and multi-dimension text analysis in order to help user in mining HTML documents on the Web efficiently and effectively.
Key words　Web mining, text mining, text categorization, text clustering, multi-dimension text analysis

　　在Web迅猛发展的同时，我们不能忽视“信息爆炸”的问题，即信息极大丰富而知识相对匮乏.据估计，Web已经发展成为拥有3亿页面的分布式信息空间，而且这个数字仍以每4至6个月翻一倍的速度增加^［1］.在这些大量、异质的Web信息资源中，蕴含着具有巨大潜在价值的知识.人们迫切需要能够从Web上快速、有效地发现资源和知识的工具.Web上的搜索引擎部分地解决了资源发现问题，但由于精确度不高等原因，其效果远不能使人满意.此外，搜索引擎的目的在于发现Web上的资源，就Web上的知识发现而言，即使检索精度再高，搜索引擎也不能够胜任.为此，我们需要开发比信息检索层次更高的新技术.为了从大量数据的集合中发现有效、新颖、有用、可理解的模式，数据库领域采用了数据挖掘技术^［2］.但是，数据挖掘的绝大部分工作所涉及的是结构化数据库，很少有处理Web上的异质、非结构化信息的工作.Web挖掘作为数据挖掘的一个新主题，引起了人们的极大兴趣.同时，它也是一个富于争议的研究方向.目前，对于Web挖掘的含义、功能等尚无统一的结论，需要国内外学者在理论上开展更多的讨论以进行精确地定义.此外，Web挖掘系统的开发对其研究也将起到很大推进作用.
　　在本文中，我们对Web挖掘技术作了系统性的研究.给出了Web挖掘的定义，讨论了Web挖掘与传统的数据挖掘以及Web信息检索之间的关系；对Web挖掘的任务进行了分类，重点讨论了Web文本挖掘和结构挖掘的功能；分析了Web文本挖掘的方法，包括文本的特征表示、文本分类和文本聚类.最后，简单介绍了我们设计的一个Web文档挖掘系统原型WebMiner.

　　Web挖掘是一项综合技术，涉及Web、数据挖掘、计算机语言学、信息学等多个领域.不同研究者从自身的领域出发，对Web挖掘的含义有着不同的理解，项目开发也各有其侧重点.例如，有些计算机语言学家认为，Web文档为自然语言理解提供了丰富的语料，可以从中自动地学习词语的意义，以进行词义辨析或确定词语所属的概念^［3］.我们从更为一般的角度出发，对Web挖掘作如下定义.
　　定义1. Web挖掘是指从大量Web文档的集合C中发现隐含的模式p.如果将C看作输入，将p看作输出，那么Web挖掘的过程就是从输入到输出的一个映射ξ: C→p.
　　Web挖掘从数据挖掘发展而来，因此其定义与我们熟知的数据挖掘定义^［2］相类似.但是，Web挖掘与传统的数据挖掘相比有许多独特之处.首先，Web挖掘的对象是大量、异质、分布的Web文档.我们认为，以Web作为中间件对数据库进行挖掘，以及对Web服务器上的日志、用户信息等数据所开展的挖掘工作，仍属于传统的数据挖掘的范畴.其次，Web在逻辑上是一个由文档节点和超链构成的图，因此Web挖掘所得到的模式可能是关于Web内容的，也可能是关于Web结构的.此外，由于Web文档本身是半结构化或无结构的，且缺乏机器可理解的语义，而数据挖掘的对象局限于数据库中的结构化数据，并利用关系表格等存储结构来发现知识，因此有些数据挖掘技术并不适用于Web挖掘，即使可用也需要建立在对Web文档进行预处理的基础之上.这样，开发新的Web挖掘技术，以及对Web文档进行预处理以得到关于文档的特征表示，便成为Web挖掘研究的重点.

　　定义2. Web信息检索，是指从大量Web文档的集合C中找到与给定的查询请求q相关的、恰当数目的文档子集S.Web信息检索的过程也对应于一个映射ζ：(C, q)→S.
　　从60年代以来，信息检索领域在索引模型、文档内容表示、匹配策略等方面取得了许多研究成果.这些成果被成功地应用在Web上，产生了搜索引擎，例如Yahoo!，Alta-vista等.搜索引擎工作的一般流程包括：使用Robot搜集Web文档、对文档集合建立倒排索引、分析用户的查询请求、匹配文档与查询请求以计算二者之间的相似度、对查询结果进行排序以及用户相关度回馈^［4］.

　　Web上的挖掘和信息检索是两种不同的技术，其区别主要表现在以下几个方面.
　　(1) 方法论不同. 信息检索是目标驱动的，用户需要明确提出查询要求；而挖掘是机会主义的，其结果独立于用户的信息需求，也是用户所无法预知的；
　　(2) 着眼点不同. 信息检索着重于文档中显式存储的字词和链接；而挖掘试图更多地理解其内容和结构；
　　(3) 目的不同. 信息检索的目的在于帮助用户发现资源，即从大量文档中找到满足其查询请求的文档子集；而挖掘是为了揭示文档中隐含的知识；
　　(4) 评价方法不同. 信息检索使用精度（precision）和召回率（recall）来评价其性能，要求返回尽可能多的相关文档，同时不相关的文档尽可能少.而挖掘采用收益（gain）、置信度（certainty）、简洁性（simplicity）等来衡量所发现知识的有效性、可用性和可理解性；
　　(5) 使用场合不同. 有时信息检索系统返回太多的结果以致用户无法一一浏览，有时用户没有明确的信息需求，有时用户希望发现文档集合中所具有的结构、趋势、含义，在这些场合下，就需要使用挖掘技术.
　　尽管Web挖掘是比信息检索层次更高的技术，但它并不是用来取代信息检索技术，二者是相辅相成的.一方面，这两种技术各有所长，有各自适用的场合；另一方面，我们可以利用Web挖掘的研究成果来提高信息检索的精度和效率，改善检索结果的组织，使信息检索系统发展到一个新的水平.

　　在逻辑上，我们可以把Web看作是位于物理网络之上的一个有向图G=(N, E)，其中节点集N对应于Web上的所有文档，而有向边集E则对应于节点之间的超链.对节点集作进一步的划分，N={N_l, N_nl}.所有的非叶节点N_nl是HTML文档，其中除了包含文本以外，还包含了标记以指定文档的属性和内部结构，或者嵌入了超链以表示文档间的结构关系.叶节点N_l可以是HTML文档，也可以是其它格式的文档，例如PostScript等文本文件，以及图形、音频等媒体文件.如图1所示.N中每个节点都有一个URL，其中包含了关于该节点所位于的Web站点和目录路径的结构信息.
　　Web上信息的多样性决定了Web挖掘任务的多样性.按照处理对象的不同，我们将Web挖掘分为两大类：内容挖掘和结构挖掘.前者指的是从Web文档的内容信息中抽取知识，而后者指的是从Web文档的结构信息中推导知识.Web内容挖掘又分为对文本文档（包括text，HTML等格式）和多媒体文档（包括image，audio，video等媒体类型）的挖掘.Web结构挖掘不仅仅局限于文档之间的超链结构，还包括文档内部的结构、文档URL中的目录路径结构等.如图2所示.在本文中，我们仅对Web上的文本挖掘和结构挖掘加以讨论，下文中提及的“文档”指的是文本文档，不包括多媒体文档.有关Web上的多媒体挖掘，感兴趣的读者可以参见文献［5］，其中介绍了一个简单的Web多媒体挖掘系统原型.

图2　Web挖掘的分类

3.2　Web文本挖掘

　　Web文本挖掘可以对Web上大量文档集合的内容进行总结、分类、聚类、关联分析，以及利用Web文档进行趋势预测等.
　　文本总结是指从文档中抽取关键信息，用简洁的形式对文档内容进行摘要或解释.这样，用户不需要浏览全文就可以了解文档或文档集合的总体内容.文本总结在有些场合十分有用，例如，搜索引擎在向用户返回查询结果时，通常需要给出文档的摘要.目前，绝大部分搜索引擎采用的方法是简单地截取文档的前几行.文献［6］提出了使用中心文档来代表文档集合，使用中心词汇来表示文档的方法，并给出了求取中心文档和中心词汇的算法.
　　文本分类是指按照预先定义的主题类别，为文档集合中的每个文档确定一个类别.这样，用户不但能够方便地浏览文档，而且可以通过限制搜索范围来使文档的查找更为容易.目前，Yahoo!通过人工来对Web上的文档进行分类，这大大影响了索引的页面数目（Yahoo! 索引的覆盖范围远远小于Alta-vista等搜索引擎）.利用文本分类技术可以对大量文档进行快速、有效地自动分类.目前，文本分类的算法有很多种，比较常用的有TFIDF^［7］和Naive Bayes^［8］等方法.
　　文本聚类与分类的不同之处在于，聚类没有预先定义好的主题类别，它的目标是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能地大，而不同簇间的相似度尽可能地小.Hearst等人的研究已经证明了“聚类假设”，即与用户查询相关的文档通常会聚类得比较靠近，而远离与用户查询不相关的文档^［9］.因此，我们可以利用文本聚类技术将搜索引擎的检索结果划分为若干个簇，用户只需要考虑那些相关的簇，大大缩小了所需要浏览的结果数量.目前，有多种文本聚类算法，大致可以分为两种类型：以G-HAC等算法为代表的层次凝聚法^［10］，以k-means等算法为代表的平面划分法^［11］.文献［12］介绍了将G-HAC和k-means集合起来的Buckshot方法和Fractionation方法.
　　关联分析是指从文档集合中找出不同词语之间的关系.Brin提出了一种从大量文档中发现一对词语出现模式的算法，并用来在Web上寻找作者和书名的出现模式，从而发现了数千本在Amazon网站上找不到的新书籍^［13］.Wang等人以Web上的电影介绍作为测试文档，通过使用OEM模型从这些半结构化的页面中抽取词语项，进而得到一些关于电影名称、导演、演员、编剧的出现模式^［14］.
　　分布分析与趋势预测是指通过对Web文档的分析，得到特定数据在某个历史时刻的情况或将来的取值趋势.Feldman等人使用多种分布模型对路透社的两万多篇新闻进行了挖掘，得到主题、国家、组织、人、股票交易之间的相对分布，揭示了一些有趣的趋势^［15］.Wüthrich等人通过分析Web上出版的权威性经济文章，对每天的股票市场指数进行预测，取得了良好的效果^［16］.
　　需要说明的是，Web上的文本挖掘和通常的平面文本挖掘的功能和方法比较类似，但是，Web文档中的标记，例如〈Title〉，〈Heading〉等蕴含了额外的信息，我们可以利用这些信息来提高Web文本挖掘的性能.

3.3　Web结构挖掘

　　由于Web中包含的结构信息处理起来比较困难，因此通常的Web搜索引擎等工具仅将Web看作是一个平面文档的集合，而忽略了其中的结构信息.Web结构挖掘的目的在于揭示蕴含在这些文档结构信息中的有用模式.
　　文档之间的超链反映了文档间的某种联系，例如包含、从属等.超链中的标记文本（anchor）对链宿页面也起到了概括作用，这种概括在一定程度上比链宿页面作者所作的概括（页面的标题）要更为客观、准确.Craven等人使用一阶学习方法对Web页面间的超链类型进行分类，以判断页面间的members-of-project，department-of-persons等关系；同时，他们还利用超链中的标记文本对链宿页面进行分类，取得了较好的效果^［17］.超链还反映了文档间的引用关系，一个页面被引用的次数体现了该页面的重要性.Brin等人通过综合考虑页面的引用次数和链源页面的重要性来判断链宿页面的重要性，从而设计出能够查询与用户请求相关的“权威”页面的搜索引擎^［18］.
　　每个Web页面并不是原子对象，其内部有或多或少的结构.Spertus对Web页面的内部结构作了研究，提出了一些启发式规则，并用于寻找与给定的页面集合｛P₁，…，P_n｝相关的其它页面^［19］.DiPasquo使用HTML结构树对Web页面进行分析，得到其内部结构特征，从而学习公司的名称和地址等信息在页面中的出现模式^［20］.
　　Web页面的URL可能会反映页面的类型，也可能会反映页面之间的目录结构关系.Spertus提出了与Web页面URL有关的启发式规则，并用于寻找个人主页，或者寻找改变了位置的Web页面的新位置^［19］.
　　目前，与Web挖掘有关的各种项目涉及了上述任务的某个方面^{［6～8,10～13,15,16］}，也有一些项目综合考虑了Web的内容和结构因素，将文本挖掘与结构挖掘结合起来，以取得更好的效果^{［14,17～20］}.尽管与多媒体信息相比，文本信息显得比较普通，但文本仍然是记载和传播信息的最主要媒体.此外，文本挖掘又相对容易取得技术突破，其中的许多研究成果也可以为多媒体挖掘和结构挖掘所借鉴.因此对文本挖掘技术的研究具有十分重要的意义和广泛的应用前景.下面，我们重点对Web文本挖掘的方法和系统设计进行讨论.

4　Web文本挖掘方法

　　在Web文本挖掘中，文本的特征表示是挖掘工作的基础，而文本分类和聚类是两种最重要、最基本的挖掘功能.

4.1　文本的特征表示

　　与数据库中的结构化数据相比，Web文档具有有限的结构，或者根本就没有结构.即使具有一些结构，也是着重于格式，而非文档内容.不同类型文档的结构也不一致.此外，文档的内容是人类所使用的自然语言，计算机很难处理其语义.文本信息源的这些特殊性使得现有的数据挖掘技术无法直接应用于其上.我们需要对文本进行预处理，抽取代表其特征的元数据.这些特征可以用结构化的形式保存，作为文档的中间表示形式.
　　文本特征指的是关于文本的元数据，分为描述性特征，例如文本的名称、日期、大小、类型等；以及语义性特征，例如文本的作者、机构、标题、内容等.描述性特征易于获得，而语义性特征则较难得到.W3C近来制定的XML^［21］，RDF^［22］等规范提供了对Web文档资源进行描述的语言和框架.在此基础上，我们可以从半结构化的Web文档中抽取作者、机构等特征.
　　对于内容这个难以表示的特征，我们首先要找到一种能够被计算机所处理的表示方法.矢量空间模型（VSM）是近年来应用较多且效果较好的方法之一^［23］.在该模型中，文档空间被看作是由一组正交词条矢量所张成的矢量空间，每个文档d表示为其中的一个范化特征矢量V(d)=(t₁, w₁(d);…;t_i, w_i(d);…; t_n, w_n(d))，其中t_i为词条项，w_i(d)为t_i在d中的权值.可以将d中出现的所有单词作为t_i，也可以要求t_i是d中出现的所有短语，从而提高内容特征表示的准确性.w_i(d)一般被定义为t_i在d中出现频率tf_i(d)的函数，即w_i(d)=Ψ(tf_i(d)). 常用的Ψ有：布尔函数平方根函数对数函数Ψ=log(tf_i(d)+1)；TFIDF函数其中，N为所有文档的数目，n_i为含有词条t_i的文档数目.

4.2　文本分类

　　文本分类是一种典型的有教师的机器学习问题，一般分为训练和分类两个阶段，具体过程如下.
　　训练阶段：
　　(1) 定义类别集合C={c₁,…, c_i,…,c_m}，这些类别可以是层次式的，也可以是并列式的；
　　(2) 给出训练文档集合S={s₁,…,s_j,…,s_n}，每个训练文档s_j被标上所属的类别标识c_i；
　　(3) 统计S中所有文档的特征矢量V(s_j)，确定代表C中每个类别的特征矢量V(c_i)；
　　分类阶段：
　　(4) 对于测试文档集合T={d₁,…,d_k,…,d_r}中的每个待分类文档d_k，计算其特征矢量V(d_k)与每个V(c_i)之间的相似度sim(d_k,c_i)；
　　(5) 选取相似度最大的一个类别作为d_k的类别.
　　有时也可以为d_k指定多个类别，只要d_k与这些类别之间的相似度超过某个预定的阈值.如果d_k与所有类别的相似度均低于阈值，那么通常将该文档放在一边，由用户来做最终决定.对于类别与预定义类别不匹配的文档而言，这是合理的，也是必须的.如果这种情况经常发生，则说明需要修改预定义类别，然后重新进行上述训练与分类过程.
　　在计算sim(d_k, c_i)时，有多种方法可供选择.最简单的方法是仅考虑两个特征矢量中所包含的词条的重叠程度，即其中，n_∩(d_k,c_i)是V(d_k)和V(c_i)具有的相同词条数目，n_∪(d_k,c_i)是V(d_k)和V(c_i)具有的所有词条数目；最常用的方法是考虑两个特征矢量之间的夹角余弦，即sim(d_k, c_i)=

4.3　文本聚类

　　文本聚类是一种典型的无教师的机器学习问题.目前的文本聚类方法大致可以分为层次凝聚法和平面划分法两种类型.
　　对于给定的文档集合D={d₁,…, d_i,…,d_n}，层次凝聚法的具体过程如下：
　　(1) 将D中的每个文档d_i看作是一个具有单个成员的簇c_i={d_i}，这些簇构成了D的一个聚类C={c₁,…,c_i,…,c_n}；
　　(2) 计算C中每对簇(c_i,c_j)之间的相似度sim(c_i,c_j)；
　　(3) 选取具有最大相似度的簇对并将c_i和c_j合并为一个新的簇c_k=c_i∪c_j，从而构成了D的一个新的聚类C={c₁,…,c_n-1}；
　　(4) 重复上述步骤，直至C中剩下一个簇为止.
　　该过程构造出一棵生成树，其中包含了簇的层次信息，以及所有簇内和簇间的相似度.层次聚类方法是最为常用的聚类方法，它能够生成层次化的嵌套簇，且准确度较高.但是，在每次合并时，需要全局地比较所有簇之间的相似度，并选择出最佳的两个簇，因此运行速度较慢，不适合于大量文档的集合.
　　平面划分法与层次凝聚法的区别在于，它将文档集合水平地分割为若干个簇，而不是生成层次化的嵌套簇.对于给定的文档集合D={d₁,…,d_i,…,d_n}，平面划分法的具体过程如下.
　　① 确定要生成的簇的数目k；
　　② 按照某种原则生成k个聚类中心作为聚类的种子S={s₁,…,s_j,…,s_k}；
　　③ 对D中的每个文档d_i，依次计算它与各个种子s_j的相似度sim(d_i,s_j)；
　　④ 选取具有最大相似度的种子将d_i归入以s_j为聚类中心的簇c_j，从而得到D的一个聚类C={c₁,…,c_k}.
　　⑤ 重复步骤②、③、④若干次，以得到较为稳定的聚类结果.
　　该方法的运行速度较快，但是必须事先确定k的取值，且种子选取的好坏对聚类结果有较大影响.

5　Web文本挖掘系统原型WebMiner

　　我们在对Web挖掘技术进行系统研究的理论基础之上，设计了一个Web文本挖掘系统原型WebMiner(如图3所示). WebMiner采用了多agent的体系结构，将多维文本分析与文本挖掘这两种技术有机地结合起来，以帮助用户快速、有效地挖掘Web上的HTML文档.以下给出系统组件和系统行为的简要描述.