WEB数据挖掘技术研究

WE B 数据挖掘技术研究周　涛,　李　军,　陆惠玲(陕西理工学院数学与计算机科学系,陕西汉中723000)[摘要]　对Web 数据挖掘进行了全面的论述,并讨论了Web 挖掘的分类和应用.在此基础上阐述了当前流行的挖掘技术,给出了Web 数据模型,指出Web 数据挖掘的发展方向和趋势.[关键词]　数据挖掘;Web 数据挖掘;Web 数据模型[中图分类号]TP3931092　[文献标识码]A [文章编号]1007-0842(2004)03-0086-050　引 言传统的数据挖掘技术处理对象主要是基于数据库、数据仓库等的结构化数据,很少处理Web 上异质、非结构化信息,因此,对Web 数据的挖掘具有很大的挑战.(1)Web 数据对数据挖掘而言,Web 似乎太庞大了.Web 上的数据正在以G 字节计算,而且仍在迅速的增长.(2)Web 页面的复杂性高于任何传统的文本文档.Web 页面缺乏统一的结构,它包含了远比任何一组书籍或其他文本文档多得多的风格和内容.(3)Web 是一个动态性极强的信息源,其信息在不断的发生更新.(4)Web 面对的是一个形形色色的用户群体,各个用户有着不同的兴趣和使用目的,用户群体也表现出多样性、随机性的特点.(5)对一个人来说,Web 上的信息只有很小的一部分是有用的,其余信息是不感兴趣的.这些无用的信息会影响所希望得到的搜索结果.(6)Web 信息具有分布性、多维性、混沌性.有用信息的获得变的日益困难,绝大多数用户在Internet 上查询或浏览信息时,往往是通过一些知名的门户网站提供的搜索引擎来实现的.但是无论这个引擎采用什么样的搜索技术,它总是存在着以下两个问题:查准率低和查全率低.所谓查准率低是指当用户输入关键字检索信息时,返回的结果动辄成百上千条,甚至上万条,而真正有用的也许只有几条,相当一部分检索结果是与检索内容无关的信息,有些甚至是死链接;所谓查全率低是指搜索引擎返回的结果并不能穷举Web 中所有与检索内容相关的Web 页,也许返回的结果仅仅是相关内容中很少的一部分.[收稿日期]　2003-03-07[作者简介]　周涛(1977-),男,宁夏同心县人,陕西理工学院数学与计算机科学系助教,齐齐哈尔大学计算机系硕士研究生,主要从事数据库理论、数据挖掘的研究;李军(1964-),男,陕西省永寿县人,陕西理工学院数学与计算机科学系讲师,主要从事计算机网络及数据库系统的研究.第22卷第1期2004年6月汉中师范学院学报(自然科学)Journal of Hanzhong T eachers C ollege (Natural Science )V ol 122N o 11June 12004第1期周　涛,等:WE B数据挖掘技术研究87　上述挑战推动了Web挖掘技术的研究工作,Web挖掘已经成为数据挖掘的一个活跃的分支,引起了人们广泛的兴趣.1　Web挖掘和数据挖掘(Data Mining,DM)111　数据挖掘数据挖掘就是从大量的、不完全的、有噪音的、模糊的、随机的实际应用数据中,抽取隐含的、不为人们事先知道的、但又是潜在有用的关联信息和知识的发现过程.数据挖掘与传统分析工具不同的是数据挖掘使用的是基于发现的方法,运用模式匹配和其它算法决定数据之间的重要联系.112　Web挖掘Web挖掘是一种特殊的数据挖掘,到目前为止还没有一个统一的概念,我们可以借鉴数据挖掘的概念给出Web挖掘的定义.所谓Web挖掘就是指从大量非结构化、异构的Web信息资源中发现有效的、新颖的、潜在可用的及最终可以理解的知识(包括概念、模式、规则、规律、约束及可视化等形式)的非平凡过程.113　Web挖掘与数据挖掘的区别[5]Web挖掘是由数据挖掘发展而来的,Web挖掘与数据挖掘相比,有其自己的特点.首先,Web挖掘的对象是大量的、异质的、分布的Web文档.以Web作为中间件对数据库进行挖掘,以及对Web服务器上的日志、用户信息等数据开展的挖掘工作,仍属于传统数据挖掘的范畴,但目前大多数文献将此类数据挖掘划入Web挖掘.其次,Web在逻辑上是一个由文档节点和超链接构成的图,因此,Web挖掘所得到的模式可能是关于Web内容的,也可以是关于Web结构的.再次,由于Web本身的无结构、半结构,且缺乏机器可以理解的语义,而传统的数据挖掘的对象局限于数据库中的结构化数据,有许多数据挖掘技术不适应于Web挖掘,即使可用也需对Web文档进行预处理.这样,就需要开发新的Web挖掘技术.2　Web挖掘的分类Web信息的复杂性决定了Web挖掘任务的多样性,目前研究的主要有三种Web挖掘技术:Web内容挖掘(Web C ontent Mining)、Web访问信息(Web日志)的挖掘(Web Usage Mining)和Web结构挖掘(Web Structure Mining).其分类结构如图1所示.图1　WE B挖掘分类88　汉中师范学院学报(自然科学)2004年第22卷211　Web内容挖掘(Web C ontent Mining)Web内容挖掘就是从Web页面上的文件内容及其描述信息中获取潜在的、有价值的知识和模式的过程.Web内容挖掘主要有两大部分[3]:(1)对文本文件(包括txt、P ostScript、pd f、html等)的挖掘称为文本挖掘.许多基于数据仓库的挖掘算法经过相应的改进处理就可以用于文本的挖掘.比如数据归纳、分类、聚类、关联规则的挖掘等.Web文本的挖掘对象可以是结构化的、也可以是半结构化的和非结构化的.挖掘的结果是对某个文本文件的概括和总结,也可以是对整个文本集的分类或聚集的结果[3].特征表示是指以一定的特征项来表示文档信息,特征表示模型很多,常用的有布尔逻辑型、向量特征型、概率型等.近年来应用较多且效果较好的特征表示方法是向量空间模型(Vector S pace M odel,VS M)[4].在VS M中,将文档看成由一组词条{T,T2,…,T n}构成,对于每一词条T i都根据其1在文档中的重要性赋予一定的权值W,可以将其看成一个n维坐标系,W1,W2,…,W n为i对应的坐标值,因此每一篇文档都可以映射为由一组词条矢量张成的向量空间中的一个点,对于所有待挖掘的文档都用词条特征向量{T,W1,T2,W2,…,T n,W n}来表示.这种1向量空间模型的表示方法优点在于将非结构化的文本表示为向量形式,使得各种数学处理成为可能.该方法的缺点也是显然的,首先,该模型关于词间关系相互独立的基本假设(正交假设)在实际实施的过程中几乎无法满足,文档中的词往往存在一定的相关性,即出现斜交的情况.其次,词汇具有的同义或者多义现象也会影响文本信息的分析处理.再次,权值的给定主观因素太强,随意性太大,给以后的计算带来了太大的误差.(2)对多媒体文档(包括image、audio、video)的挖掘称之为多媒体挖掘.主要是针对Web中音频、视频、图形、图像数据进行相应的处理,采用改进的数据挖掘方法发现蕴含在里面的潜在的、有意义的信息和模式的过程.212　Web结构挖掘(Web Structure Mining)Web结构包括不同网页之间的链接结构和一个网页内部的可以用HT M L、X M L表示成的树状乃至图状结构,以及文档UR L中的目录结构等.Web结构挖掘是从WWW的组织结构和链接关系中推导出潜在的知识和模式.主要是通过对Web站点的结构进行分解、变形和归纳,将页面进行分类,以利于信息的搜索.因为存在超文本之间的连接,所以Web页面信息远比它所包含的文本内容的信息要多.利用这些我们可以对所找到的Web页面进行排序,找出最重要的页面.文档之间的连接反映了文档之间的引用关系,一个页面被引用的次数体现了该页面的重要性.Brin等人提出用Page-rank方法.Hub是指一个或多个Web页面,它提供了指向权威页面的连接集合,Hub页面本身可能并不突出,或者说没有几个连接指向他们,但是, Hub页面却提供了指向某个突出站点的连接.如何利用Hub页面来发现权威页面呢?下面笔者介绍一下HITS(Hyperlink-Induced T opic Search)算法[5].首先,HITS通过搜索查询关键字,生成初始页面集合,称为根集合.由于根集合中有些页面包含指向权威页面的连接,因此,对根集合进行页面扩展生成基集合,其中包括根集合指向的页面以及连接到根集合的页面.其次,给基集合中的每个页面赋一个Hub 权值h p 和一个权威值a p ,初始值为同一个非负常数,然后对权值h p 和权威值a p 进行计算:a p =∑h p ,其中页面q 指向页面p ,h p =∑a p,其中页面q 指向页面p . 设页面编号为{1,2,3,…,n},定义邻接矩阵A ,如果页面i 连接j ,则A [i ,j ]=1,否则A [i ,j ]=0,定义页面的权威向量a =(a 1,a 2,a 3,…,a N ),Hub 向量h =(h 1,h 2,h 3,…,h n ),则有h =A ×a ,a =A T×h ,展开这两个表达式,得:h =A ×a =A ×A T ×h =(A ×A T )×h =(A ×A T )2×h =…=(A ×A T )n ×h ,a =A T ×h =A T ×A ×a =(A T×A )×a =(A T ×A )2×a =…=(A T ×A )n ×a . 最后,HITS 算法输出与给定主体对应的一些具有较大Hub 权值的页面和具有较大权威值的页面,即“权威”页面.213　Web 访问信息(Web 日志)的挖掘(Web Usage Mining )Web 访问信息的挖掘就是对用户访问Web 服务器时留下的日志进行挖掘,也称之为Web 日志挖掘.Web 日志的挖掘就是要在海量的日志数据中发现用户的访问模式.如用户频繁访问的页面、访问路径等.3　Web 数据模型[5]Web 页面是通过HT M L 、X M L 语言来定义的,Web 页面之间可以相互连接,从而构成一个相互联接的超媒体系统.此处我们给出一种理想状态的Web 数据模型.我们可以用一个有向图G =(V ,E )来表示Web ,其中V 表示页面的集合,E 表示页面之间的超链接集合.如图2所示.页面抽象成图中的节点,而页面之间的超链接抽象为图中的有向边.节点的入边表示对该页的链接,而节点的出边表示该页链接其他的页面.每个节点都有一个UR L ,其中包含了关于该节点所位于Web 站点和目录路径的结构信息.所有非叶结点是HT M L 文档,叶结点可以是HT M L 文档,也可以是其他格式的文档,例如图形、图像、音频等媒体文件.图2　WE B 的数据模型第1期周　涛,等:WE B 数据挖掘技术研究89　90　汉中师范学院学报(自然科学)2004年第22卷定义1　页面节点用三元组(PI D,P,time)表示,其中PI D唯一表示一个页面节点,time 用来记录该节点最近被访问的时间,P是属性集,P={p|p i为属性,i=1,2,…}.i定义2　页面中的连接点用一个三元组(LI D,string,target-n ode-id)表示,LI D唯一表示一个连接点,string描述该连接的展示信息,target-n ode-id是LI D所指向的目标页面节点的PI D.定义3　Web数据模型可以用三元组{Page-node-set,Page-Linknode-set,Link-set}表示, Page-node-set为页面节点集合,Page-Linknode-set为连接点集合,Link-set为连接集合.4　Web挖掘的方向目前,在国内外Web挖掘的研究仍然处于刚刚起步的阶段,是前沿性的研究领域,将来几个有价值的研究方向是:(1)Web数据挖掘的内在机制的研究及其实现;(2)Web知识库的动态维护、更新;(3)半结构、结构的文本数据、图形图像数据、多媒体数据的高效挖掘算法;(4)Web挖掘算法在海量数据挖掘时的适应性和时效性;(5)研究专门用于知识发现的数据挖掘语言及其标准化;(6)关联规则和序列模式在构造自组织站点的研究[2];(7)分类在电子商务中、市场智能提取中的研究[2].[参考文献][1]王继成,潘金贵,张福炎,等.Web文本挖掘技术研究[J].计算机研究与发展,2000,37(5):513—520.[2]王实,高文,李锦涛.Web数据挖掘[J].计算机科学,2000,27(4):89—93.[3]陈新中,李岩,谢永红,等.Web数据挖掘[J].计算机工程与应用,2002,38(13):42—44.[4]邹涛,王继成,朱华宇,等.WWW上的信息挖掘技术及其实现[J].计算机研究与发展,1999,36(8):1029—1034.[5]吉根林,孙志辉.Web挖掘技术研究[J].计算机工程,2002,28(10):16—17.[6]Jiawei Han,Micheline K amber.Data Mining:C oncept and T echniques[M].Massachusetts:M organ K au fmannPublishers,2000.[7]David Hand,Heikki Mannila,Padhraic Smyth.Principles of Data Mining[M].San Francisco:MIT Press,2001.The R esearch of Web Data Mining T echnologyZH OU T ao,　LI Jun,　LU Hui-ling(Department of M athsam tics and C om puter S cience,Shaanxi University of T echn ology,H anzh ong723000,Shaanxi,China) Abstract:In this paper,Web data mining is discussed com pletely and its class fication and the application.Then the popular techniques based on Web data mining is described and the Web data m odel is presented,At last point out the developing direction and trend of Web data mining.K ey w ords:data mining;Web data mining;Web data m odel。