Web文本挖掘技术研究
王继成 潘金贵 张福炎
摘 要 作为从浩瀚的Web信息资源中发现潜在的、有价值知识的一种有效技术,Web挖掘正悄然兴起,倍受关注.目前,Web挖掘的研究正处于发展阶段,尚无统一的结论,需要国内外学者在理论上开展更多的讨论.同时,Web挖掘系统的开发对其研究也将起到很大推进作用.首先探讨了Web挖掘的有关理论,从Web挖掘的定义、Web挖掘与Web信息检索的关系、Web挖掘任务的分类与功能等方面加以阐述.然后重点分析了Web文本挖掘的方法,包括:文本的特征表示、文本分类与文本聚类.在此基础上简单介绍了一个Web文本挖掘系统原型WebMiner.WebMiner采用了多agent体系结构,将多维文本分析与文本挖掘这两种技术有机地结合起来,以帮助用户快速、有效地挖掘Web上的HTML文档.
关键词 Web挖掘,文本挖掘,文本分类,文本聚类,多维文本分析
中图法分类号 TP391; TP393
RESEARCH ON WEB TEXTMINING
WANG Ji-Cheng, PAN Jin-Gui, andZHANG Fu-Yan
(Department of Computer Science and Technology, Nanjing University,Nanjing 210093)
(State Key Laboratory for Novel Software Technology, NanjingUniversity, Nanjing 210093)
Abstract Withthe flood of information on the Web, Web mining is a new researchissue which draws great interest from many communities. Currently,there is no agreement about Web mining yet. It needs morediscussion among scientists in order to define what it is exactly.Meanwhile, the development of Web mining system will promote itsresearch in turn. In this paper, a systemic discussion about theprinciple of Web mining is presented, including the definition, therelationship between information mining and retrieval on the Web,the taxonomy and function. Then the methods of text mining on theWeb are discussed in detail and a prototype of Web text miningsystem WebMiner is introduced. WebMiner is a multi-agent systemwhich combines text mining and multi-dimension text analysis inorder to help user in mining HTML documents on the Web efficientlyand effectively.
Key words Web mining, text mining, textcategorization, text clustering, multi-dimension textanalysis
1 引言
在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.
2 Web挖掘与Web信息检索
2.1 Web挖掘的定义
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.2 Web信息检索的定义
定义2.Web信息检索,是指从大量Web文档的集合C中找到与给定的查询请求q相关的、恰当数目的文档子集S.Web信息检索的过程也对应于一个映射ζ:(C,q)→S.
从60年代以来,信息检索领域在索引模型、文档内容表示、匹配策略等方面取得了许多研究成果.这些成果被成功地应用在Web上,产生了搜索引擎,例如Yahoo!,Alta-vista等.搜索引擎工作的一般流程包括:使用Robot搜集Web文档、对文档集合建立倒排索引、分析用户的查询请求、匹配文档与查询请求以计算二者之间的相似度、对查询结果进行排序以及用户相关度回馈[4].
2.3 Web上的挖掘与信息检索
Web上的挖掘和信息检索是两种不同的技术,其区别主要表现在以下几个方面.
(1) 方法论不同.信息检索是目标驱动的,用户需要明确提出查询要求;而挖掘是机会主义的,其结果独立于用户的信息需求,也是用户所无法预知的;
(2) 着眼点不同. 信息检索着重于文档中显式存储的字词和链接;而挖掘试图更多地理解其内容和结构;
(3) 目的不同.信息检索的目的在于帮助用户发现资源,即从大量文档中找到满足其查询请求的文档子集;而挖掘是为了揭示文档中隐含的知识;
(4) 评价方法不同.信息检索使用精度(precision)和召回率(recall)来评价其性能,要求返回尽可能多的相关文档,同时不相关的文档尽可能少.而挖掘采用收益(gain)、置信度(certainty)、简洁性(simplicity)等来衡量所发现知识的有效性、可用性和可理解性;
(5) 使用场合不同.有时信息检索系统返回太多的结果以致用户无法一一浏览,有时用户没有明确的信息需求,有时用户希望发现文档集合中所具有的结构、趋势、含义,在这些场合下,就需要使用挖掘技术.
尽管Web挖掘是比信息检索层次更高的技术,但它并不是用来取代信息检索技术,二者是相辅相成的.一方面,这两种技术各有所长,有各自适用的场合;另一方面,我们可以利用Web挖掘的研究成果来提高信息检索的精度和效率,改善检索结果的组织,使信息检索系统发展到一个新的水平.
3 Web挖掘的任务
3.1 Web挖掘任务的分类
在逻辑上,我们可以把Web看作是位于物理网络之上的一个有向图G=(N,E),其中节点集N对应于Web上的所有文档,而有向边集E则对应于节点之间的超链.对节点集作进一步的划分,N={Nl,Nnl}.所有的非叶节点Nnl是HTML文档,其中除了包含文本以外,还包含了标记以指定文档的属性和内部结构,或者嵌入了超链以表示文档间的结构关系.叶节点Nl可以是HTML文档,也可以是其它格式的文档,例如PostScript等文本文件,以及图形、音频等媒体文件.如图1所示.N中每个节点都有一个URL,其中包含了关于该节点所位于的Web站点和目录路径的结构信息.
Web上信息的多样性决定了Web挖掘任务的多样性.按照处理对象的不同,我们将Web挖掘分为两大类:内容挖掘和结构挖掘.前者指的是从Web文档的内容信息中抽取知识,而后者指的是从Web文档的结构信息中推导知识.Web内容挖掘又分为对文本文档(包括text,HTML等格式)和多媒体文档(包括image,audio,video等媒体类型)的挖掘.Web结构挖掘不仅仅局限于文档之间的超链结构,还包括文档内部的结构、文档URL中的目录路径结构等.如图2所示.在本文中,我们仅对Web上的文本挖掘和结构挖掘加以讨论,下文中提及的“文档”指的是文本文档,不包括多媒体文档.有关Web上的多媒体挖掘,感兴趣的读者可以参见文献[5],其中介绍了一个简单的Web多媒体挖掘系统原型.
图1 Web的逻辑结构 |
图2 Web挖掘的分类 3.2 Web文本挖掘 Web文本挖掘可以对Web上大量文档集合的内容进行总结、分类、聚类、关联分析,以及利用Web文档进行趋势预测等. 3.3 Web结构挖掘 由于Web中包含的结构信息处理起来比较困难,因此通常的Web搜索引擎等工具仅将Web看作是一个平面文档的集合,而忽略了其中的结构信息.Web结构挖掘的目的在于揭示蕴含在这些文档结构信息中的有用模式. 4 Web文本挖掘方法 在Web文本挖掘中,文本的特征表示是挖掘工作的基础,而文本分类和聚类是两种最重要、最基本的挖掘功能. 4.1 文本的特征表示 与数据库中的结构化数据相比,Web文档具有有限的结构,或者根本就没有结构.即使具有一些结构,也是着重于格式,而非文档内容.不同类型文档的结构也不一致.此外,文档的内容是人类所使用的自然语言,计算机很难处理其语义.文本信息源的这些特殊性使得现有的数据挖掘技术无法直接应用于其上.我们需要对文本进行预处理,抽取代表其特征的元数据.这些特征可以用结构化的形式保存,作为文档的中间表示形式. 4.2 文本分类 文本分类是一种典型的有教师的机器学习问题,一般分为训练和分类两个阶段,具体过程如下. 4.3 文本聚类 文本聚类是一种典型的无教师的机器学习问题.目前的文本聚类方法大致可以分为层次凝聚法和平面划分法两种类型. 5 Web文本挖掘系统原型WebMiner 我们在对Web挖掘技术进行系统研究的理论基础之上,设计了一个Web文本挖掘系统原型WebMiner(如图3所示).WebMiner采用了多agent的体系结构,将多维文本分析与文本挖掘这两种技术有机地结合起来,以帮助用户快速、有效地挖掘Web上的HTML文档.以下给出系统组件和系统行为的简要描述. |
图3 Web文本挖掘系统原型WebMiner
5.1 系统组件 (1)文本搜集agent:利用信息访问技术将分布在多个Web服务器上的待挖掘文档集成在WebMiner的本地文本库中.
(2)文本预处理agent:利用启发式规则和自然语言处理技术从文本中抽取出代表其特征的元数据,并存放在文本特征库中,作为文本挖掘的基础.
(3) 文本分类agent:利用其内部知识库,按照预定义的类别层次,对文档集合(或者其中的部分子集)的内容进行分类.
(4) 文本聚类agent:利用其内部知识库,对文档集合(或者其中的部分子集)的内容进行聚类.
(5)多维文本分析引擎:WebMiner引入了文本超立方体模型和多维文本分析技术,为用户提供关于文档的多维视图.多维文本分析引擎还具有统计分析功能,从而能够揭示文档集合的特征分布和趋势.此外,多维文本分析引擎还可以对大量文档的集合进行特征修剪,包括横向文档选择和纵向特征投影两种方式.
(6)用户接口agent:在用户与多维文本分析引擎之间起着桥梁作用.它为用户提供可视化接口,将用户的请求转化为专用语言传递给多维文本分析引擎,并将多维文本分析引擎返回的多维文本视图和文档展示给用户.
每个agent作为系统的一个组件,能够完成相对独立的工作.这些部件可以位于同一台计算机上,也可以分布在网络中的多台计算机上.此外,由于系统高度模块化,因此易于加入新的部件.同时,各个agent之间通过相互协作来完成挖掘的全过程.其中,多维文本分析引擎以文本预处理为基础,以文本挖掘为支撑.文本超立方体中的维来自于文本预处理所得到的文本特征属性,例如时间、作者等.而文档主题类别的生成以及文档之间关系的聚类分析又依赖于文档挖掘技术.反过来,多维文本分析引擎又为文本挖掘提供了有效的可视化手段和特征修剪工具.文档集合的特征修剪结果可以展现给用户,也可以作为挖掘对象输入到文本分类agent和文本聚类agent.如图3所示. 用户通过与系统中各个组件进行交互来实现Web文本挖掘的全过程.首先,用户给出搜集策略(例如,起始URL列表、指定主题或者网络域等)以指导文本搜集agent进行Web文档的搜集.然后,文本预处理agent从搜集到的Web文档中抽取描述性特征和语义性特征.此后,用户有多种方案供选择,包括:使用多维分析引擎对文档特征进行多维分析,得到多维文档视图(每个视图对应于文档集合的一个子集);按照预定义的类别层次,对文档集合(或者其中的部分子集)的内容进行分类;当预定义的类别层次与文档集合的内在层次不符合时,用户可以修改或重新创建文本分类agent的预定义类别层次和训练文档,或者利用文本聚类agent对文档集合进行聚类得到文档簇;由于簇也是文档的集合,因此,当用户对某个簇感兴趣,而这个簇中又包含很多文档时,可以再次使用文本聚类agent将簇进一步划分为子簇,直到每个簇中包含的文档数目适中为止.用户与系统的交互存在多次反复,直到获得满意的结果为止. 在Web信息充斥的情况下,Web挖掘是一个具有极大潜力的研究方向.一些国际会议,例如KDD'97、IJCAI'99等,已经或即将举行有关Web挖掘的专题讨论,对其理论、体系结构、算法等展开研究.本文对Web挖掘的定义、任务、功能作了系统性的研究,着重分析了Web文本挖掘的方法,并设计了一个Web文本挖掘系统原型WebMiner.在该领域仍有许多问题值得探讨,包括:适用于大规模文档集合的有效算法,利用XML规范对Web文档元数据进行描述和抽取,设计更多的Web挖掘部件以丰富WebMiner的功能等,这些将是我们下一步研究要解决的问题.王继成,男,1973年生,博士研究生,研究方向为信息检索与挖掘.
潘金贵,男,1952年生,教授,研究方向为中间件、agent技术.
张福炎,男,1939年生,教授,博士生导师,研究方向为数字化图书馆、多媒体技术.
王继成(南京大学计算机科学与技术系 南京 210093)
(南京大学软件新技术国家重点实验室 南京 210093)
潘金贵(南京大学计算机科学与技术系 南京 210093)
(南京大学软件新技术国家重点实验室 南京 210093)
张福炎(南京大学计算机科学与技术系 南京 210093)
(南京大学软件新技术国家重点实验室 南京 210093)
5.2 系统行为
6 结束语
参考文献
1,Lawrence S et al. Searchingthe World Wide Web. Science, 1998, 280(5360): 98~100
2, Fayyad U et al. The KDD process for extracting useful knowledgefrom volumes of data. Communications of the ACM, 1996, 39(11):27~34
3, Hahn U, Schnattinger K. Deep knowledge discovery from naturallanguage texts. In: Proc of the 3rd Int'l Conf on KnowledgeDiscovery and Data Mining. Newport Beach, 1997. 175~178
4,Gudivada V N et al. Information retrieval on the World Wide Web.IEEE Internet Computing, 1997, 1(5): 58~68
5,Zaïane O R, Han J et al.MultiMedia-miner: A system prototype for multimedia data mining.In: Proc of 1998 ACM-SIGMOD Conf on Management of Data. Seattle,1998. 581~583
6,Pirolli P, Schank P et al. Scatter/gather browsing communicatesthe topic structure of a very large text collection. In: Proc ofthe ACM SIGCHI Conf on Human Factors in Computing Systems. 1996.http://www.acm.org/sigs/sigchi/chi96/proceedings/papers/pirolli/pp-txt.htm
7,邹 涛, 王继成等. 基于WWW的资料搜集系统的设计与实现. 情报学报, 1999, 18(3): 195~201
, (Zou Tao, Wang Jicheng et al. The design and implementation ofan information gathering system on the Web. Journal of the ChinaSociety for Scientific and Technical Information(in Chinese), 1999,18(3): 195~201)
8,Choon Yang Quek. Classification of world wide web documents[Senior Honors dissertation]. School of Computer Science, CamegieMellon University, 1997
9,Hearst M A, Pedersen J. Reexamining the cluster hypothesis:Scatter/gather on retrieval results. In: Proc of the 19th AnnualInt'l ACM/SIGIR Conf. Zurich, 1996. 76~84
10,Willet P. Recent trends in hierarchical document clustering: Acritical review. Information Processing and Management, 1988, 24:577~597
11,Rocchio J J. Document retrievalsystems——Optimization andevaluation [Ph D dissertation]. Harvard University, Cambridge, MA,1966
12,Cutting D et al. Scatter/gather: A cluster-based approach tobrowsing large document collections. In: Proc of the 15th AnnualInt'l ACM/SIGIR Conf. Copenhagen, 1992. 318~329
13,Brin S. Extracting patterns and relations from the World WideWeb. In: Proc of WebDB Workshop at EDBT'98. Valencia, 1998
14, Wang Ke, Liu Huiqing. Schema discovery from semi-structureddata. In: Proc of the 3rd Int'l Conf on Knowledge Discovery andData Mining. Newport Beach, 1997
15,Feldman R, Dagan I. Knowledge discovery in textualdatabases(KDT). In: Proc of the 1st Int'l Conf on KnowledgeDiscovery. Montreal, 1995. 112~117
16,Wüthrich B, Permunetilleke D,Leung S et al. Daily prediction of major stock indices from textualWWW data. In: Proc of the 4th Int'l Conf on Knowledge Discovery.New York, 1998
17,Craven M, Slattery S, Nigam K. First-order learning for Webmining. In: Proc of the 10th European Conf on Machine Learning.Chemnitz, 1998
18,Brin S et al. The anatomy of large-scale hypertextual web searchengine. In: Proc of the Seventh Int'l World Wide Web Conf. 1998.http://decweb.ethz.ch/www7/1921/com1921.htm
19,Spertus E. ParaSite: Mining structural information on the web.In: Proc of the Sixth Int'l World Wide Web Conf. 1997.http://decweb.ethz.ch/www6/Technical/paper206/paper206.html
20, DiPasquo D. Using HTML formatting to aid in natural languageprocessing on the World Wide Web [Senior Honors dissertation].School of Computer Science, Canegie Mellon University, 1998
21,Bray T, Paoli J, Sperberg-McQueen C M. Extensible MarkupLanguage (XML) 1.0 specification. World Wide Web ConsortiumRecommendation. 1998. http://www.w3.org/TR/REC-xml/
22,Lassila O, Swick R R. Resource Description Framework(RDF) Modeland Syntax Specification. World Wide Web Consortium Recommendation.1999. http://www.w3.org/TR/REC-rdf-syntax/
23,Salton G, Wong A, Yang C S. A vector space model for automaticindexing. Communications of the ACM, 1975, 18(5):613~620
文献来源:http://blog.csdn.net/chengg0769/archive/2007/07/18/1697376.aspx
furtherreading:昝红英.基于实体属性的中文网页检索研究.北京大学博士研究生学位论文,2004.5