Web挖掘研究

计算机研究与发展

JOU RNAL O F COM PU T ER R ESEA RCH&D EV ELO PM EN T

V o l138,N o14

A p r.2001

原稿收到日期:2001202201

W eb挖掘研究

韩家炜①　孟小峰②　王　静③　李盛恩③

①(加拿大西蒙弗雷泽大学智能数据库系统研究实验室　加拿大)

②(中国人民大学信息学院　北京　100872)

③(中国科学院计算技术研究所　北京　100080)

(xfm eng@public.bta.net.cn)

摘　要　因特网目前是一个巨大、分布广泛、全球性的信息服务中心,它涉及新闻、广告、消费信息、金融管理、教育、、电子商务和许多其它信息服务.W eb包含了丰富和动态的超链接信息,以及W eb页面的访问和使用信息,这为数据挖掘提供了丰富的资源.W eb挖掘就是从W eb文档和W eb活动中抽取感兴趣的潜在的有用模式和隐藏的信息.对W eb挖掘最新技术及发展方向做了全面分析,包括W eb结构挖掘、多层次W eb数据仓库方法以及W eb L og挖掘等.

关键词　数据挖掘,W eb挖掘,W eb仓库,W eb L og挖掘,W eb使用记录挖掘

中图法分类号　T P311

RESEARCH ON W EB M IN ING:A SURVEY

HAN J ia2W ei①,M EN G X iao2Feng②,W AN G J ing,and L I Sheng2En③

①(In tellig en t D a tabase S y ste m s R esea rch L abora rtory,S i m on F raser U n iversity,Canad a)

②(S chool of Inf or m a tion,R enm in U n iversity of Ch ina,B eij ing100080)

③(Institu te of Co mp u ting T echnology,Ch inese A cad e my of S ciences,B eij ing100080)

Abstract　T he W o rld W ide W eb serves as huge,w idely distribu ted,global info r m ati on service cen ter fo r vari ou s app licati on s.W eb con tain s a rich and dynam ic co llecti on of hyperlink info r m ati on and W eb p age access and u sage info r m ati on,p roviding rich sou rces fo r data m in ing. T he goal of W eb m in ing is to discover the access pattern and h idden info r m ati on from the huge co llecti on of docum en ts p lu s hyperlink info r m ati on,access and u sage info r m ati on.Given in th is pap er is an overview of W eb m in ing techn iques and new trends,m ain ly invo lving W eb structu re m in ing,a m u ltilayered W eb info r m ati on base bu ilding,and W eb L og m in ing.

Key words　data m in ing,W eb m in ing,W eb w arehou se,W eb L og m in ing,W eb u sage m in ing

1　引　　言

60年代,大的物理流伴随着大信息流.传统的文件方式不能适应信息处理的需求,因此出现了数据库技术.90年代,人类积累的数据量以高于每月15%(或每年513倍)的速度增加,数据海洋不能产生决策意志,为了进行决策,人们不断地扩大数据库能力,搜集海量数据,但这使得决策者更难于决策,因此出现了数据挖掘技术,以便从数据库中发现知识.数据挖掘技术包括特征、分类、关联、聚类、偏差、时间序列、趋势分析等[1～3].

近年来,In ternet正以令人难以置信的速度在飞速发展,越来越多的机构、团体和个人在In ternet上发布信息、查找信息.虽然In ternet上有海量的数据,但由于W eb是无结构的、动态的,并且W eb页面的复杂程度远远超过了文本文档,人们要想找到自己想要的数据犹如大海捞针一般.信息检索界开发了许多搜索引擎[4],但其覆盖率有限,因此查全率低,一般的搜索引擎是基于关键字的查询,命中率较低,另外不能针对特定的用户给出特殊的服务,因为每个人感兴趣的东西是不一样的,因此不具有个性化.

解决这些问题的一个途径,就是将传统的数据挖掘技术和W eb结合起来,进行W eb挖掘[5～13]. W eb挖掘就是从W eb文档和W eb活动中抽取感兴趣的潜在的有用模式和隐藏的信息[10,14,15].W eb挖掘可以在很多方面发挥作用,如对搜索引擎的结构进行挖掘,确定权威页面[16～19],W eb文档分类[20,21],W eb L og挖掘[22,23]、智能查询,建立M eta2 W eb数据仓库等.

万维网目前是一个巨大、分布广泛、全球性的信息服务中心,它涉及新闻、广告、消费信息、金融管理、教育、、电子商务和许多其它信息服务.W eb 还包含了丰富和动态的超链接信息,以及W eb页面的访问和使用信息,这为数据挖掘提供了丰富的资源.然而从以下的分析可以看出,对W eb进行有效的资源和知识发现具有极大的挑战性.

(1)对有效的数据仓库和数据挖掘而言,W eb 似乎太庞大了.W eb的数据量目前以兆兆字节(terabytes)计算,而且仍然在迅速地增长.许多机构和社团都在把各自大量的可访问信息置于网上.这使得几乎不可能去构造一个数据仓库来复制、存储或集成W eb上的所有数据.最近,有一些工作在致力于存储或集成W eb上的所有数据.例如,在h ttp: www.arch ive.o rg index1.h tm l下,可访问到一个巨大的数十兆兆字节的因特网存档.

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

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

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

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

这些挑战已经推动了如何高效且有效地发现和利用因特网上资源的研究工作.W eb挖掘是一个更具挑战性的课题,它实现对W eb存取模式、W eb结构、规则和动态的W eb内容的查找.

2　W eb挖掘的分类

我们可以将W eb挖掘一般地定义为:从与WWW相关的资源和行为中抽取感兴趣的、有用的模式和隐含信息.一般地,W eb挖掘可分为3类: W eb内容挖掘(W eb con ten t m in ing)、W eb结构挖掘(W eb structu re m in ing)和W eb使用记录的挖掘(W eb u sage m in ing).图1给出了W eb挖掘的分类图.

(1)W eb内容挖掘

W eb内容挖掘是从文档内容或其描述中抽取知识的过程.W eb文档文本内容的挖掘,基于概念索引的资源发现,以及基于代理的技术都属于这一类.W eb内容挖掘有两种策略:直接挖掘文档的内容,或在其它工具搜索的基础上进行改进.采用第1种策略的有针对W eb的查询语言W eb L og, W ebOQL等,利用启发式规则来寻找个人主页信息的A hoy,等等.采用第2种策略的方法主要是对搜索引擎的查询结果进行进一步的处理,得到更为精确和有用的信息.属于该类的有W ebSQL,及对搜索引擎的返回结果进行聚类的技术等.

(2)W eb结构挖掘

W eb结构挖掘是从WWW的组织结构和链接关系中推导知识.由于文档之间的互连,WWW能够

604计算机研究与发展2001年

提供除文档内容之外的有用信息.利用这些信息,可以对页面进行排序,发现重要的页面.这方面工作的代表有PageR ank [24]和CL EV ER [25].此外,在多层次W eb 数据仓库(M LDB )中也利用了页面的链接结构.

(3)W eb 使用记录的挖掘

W eb 使用记录挖掘的主要目标则是从W eb 的

访问记录中抽取感兴趣的模式[26].WWW 中的每个

服务器都保留了访问日志(W eb access log ),记录了

关于用户访问和交互的信息.分析这些数据可以帮

助理解用户的行为,从而改进站点的结构,或为用户提供个性化的服务.这方面的研究主要有两个方向:一般的访问模式追踪和个性化的使用记录追踪.一般的访问模式追踪通过分析使用记录来了解用户的访问模式和倾向,以改进站点的组织结构.而个性化的使用记录追踪则倾向于分析单个用户的偏好,其目的是根据不同用户的访问模式,为每个用户提供定制的站点.

图1　W eb 挖掘的分类

3　W eb 结构挖掘

W eb 结构是可以挖掘的

[1,14,15]

.挖掘W eb 结构的目的是发现页面的结构和W eb 的结构,在此基础

上对页面进行分类和聚类从而找到权威页面.有关这方面的研究提出了如下的方法.

3.1　Page -rank 方法(Br i n and Page ,1998)[18]假设要搜索某一给定话题的W eb 页面,例如金融投资方面的页面.这时我们除了希望得到与之相关的W eb 页面外,还希望所检索到的页面具有较高质量和权威性.

这里基于了一个有意思的发现,即权威性(au tho rity )可由W eb 页面链接来反映.W eb 不仅由页面组成,而且还包含了从一个页面指向另一个页面的超链接.超链接包含了大量人类潜在的语义,它有助于自动分析出权威性语义.当一个W eb 页面的作者建立指向另一个页面的指针时,这可以看做是作者对另一页面的注解.把对一个页面的来自不同作者的注解收集起来,就可以用来反映该页面的重要性,并可以很自然地用于权威W eb 页面的发现.因此,大量的W eb 链接信息提供了丰富的关于

W eb 内容相关性、

质量和结构方面的信息,这对W eb 挖掘是可以利用的一个重要资源

.基于以上考虑,人们提出了如下的权威页面识

别算法.

首先W eb 可以用一个有向图来表示,G =(V ,

E ),V 是页面的集合,E 是页面之间的超链接集合.页面抽象为图中的顶点,而页面之间的超链接抽象

为图中的有向边.顶点v 的入边表示对v 的引用,出边表示v 引用了其它的页面.所以W eb 页面之间的超链接揭示了W eb 结构.链接文本(ancho r tex ts )可以用来对被引用的页面进行索引(例如W ebo r ,WWWW ,Google ).超链接可以用来计算页面的rank ing sco re ,通过超链接可以将一个页面的rank ing sco re 传递到相邻的页面

.Page 2rank 的基本思想是:一个页面被多次引

用,则这个页面很可能是重要的;一个页面尽管没有

被多次引用,但被一个重要页面引用,则这个页面很可能是重要的;一个页面的重要性被均分并被传递到它所引用的页面.定义1.u 是一个W eb 页面,F u 是u 引用的页面集合,B u 是引用u 的页面集合,N u = F u ,则u 的重要性为

R (u )=

∑v ∈B u

(R (v )

N v

).

7

044期韩家炜等:W eb 挖掘研究

rank ing score(q,d)=w13si m(q,d)+w23R(d),计算每个页面的重要性,然后进行排名.这里,w1, w2∈[0,1],w1+w2=1,si m(q,d)是相似函数, si m(q,d),R(d)∈[0,1].

3.2　Hub author ity方法(Kle i nberg,1998)[19]

在WWW出现之前,引用分析在信息获取领域已经进行了长时间的研究.Garfield’s i m pact facto r (1972)对杂志的引用采用了数值化的评价方法, P in sk i and N arin(1976)对此提出了重要的改进,他们观察到并不是所有的引用都有相同的重要性,一个有影响的杂志是递归地被其它的有影响的杂志大量引用,一个杂志j的影响力等于所有引用它的杂志的影响力之和再根据引用j的杂志的数量对该和进行加权.

然而,与杂志的引用率不同,W eb链接结构具有特殊的特征.首先,不是每一个超链接都具有注解性.有些链接是为其它目的而创建的,如为了导航或为了付费广告.总体上,若大部分超链接具有注解功能,就可以用于权威判断.其次,基于商业或竞争的考虑,很少有W eb页面会指向其竞争领域的权威页面.例如,可口可乐不会链接到其竞争对手百氏可乐的W eb页面.第3,权威页面很少具有特别的描述.如Yahoo!主页面不会明确给出“W eb搜索引擎”之类的自描述信息.

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

算法H IT S(hyp erlink2induced top ic search)是利用hub au tho rity方法的搜索算法,其内容如下:将查询q提交给普通的基于相似度的搜索引擎,搜索引擎返回很多页面,从中取前n个页面作为根集(root set),用S表示.

通过向S中加入被S引用的页面和引用S的页面将S扩展成一个更大的集合T.

以T中的hub页为顶点集V1,以au tho rity页为顶点集V2,V1中的页面到V2中的页面的超链接为边集E,形成一个二分有向图S G=(V1,V2,E).对V1中的任一个顶点v,用h(v)表示页面v的hub 值,对V2中的顶点u用a(u)表示页面u的au tho rity值.开始时a(u)=h(v)=1,对u执行I操作修改它的a(u),对v执行O操作修改它的h(v): I操作:a(u)=∑

v∶(v,u)∈E

h(v),(1)

O操作:h(v)=∑

v∶(v,u)∈E

a(u).(2)每次迭代后对a(u)和h(v)进行规范化处理:

a(u)=

a(u)

∑

q∈V2

[a(q)]2

,h(v)=h

(v)

∑

q∈V1

[h(q)]2

.

式(1)反映了若一个页面由很多好的hub所指,则其au tho rity权重会相应增加(即权重增加为所有指向它的页面的现有hub权重之和).式(2)反映了若一个页面指向许多好的权威页,则hub权重也会相应增加(即权重增加为该页面链接的所有页面的au tho rity权重之和).

H IT S算法输出一组具有较大hub权重的页面和具有较大au tho rity权重的页面.许多实验表明,该算法对许多查询具有非常良好的搜索结果.

在实际应用中,由S生成T的代价可能是很昂贵的.为了找出S所引用的页面,需要将S中的所有页面下载,为了找出引用S的页面,对S中的页面需要搜索引擎能根据给出的U RL能找出引用该U RL的页面,另外需要排除重复的页面.一般情况下 S =200,而 T 可能达到5000.因此根据T生成有向图S G可能是昂贵的.

虽然基于链接的算法可以带来很好的结果,但这种方法由于忽略文本内容,也遇到一些困难.例如当hub页包含多个话题的内容时,H IT S有时会发生偏差.这一问题可以按如下的方法加以克服,即将式(1)和式(2)置换为相应权重的和,降低同一站点内多链接的权重,使用ancho r文本(W eb页面中与超链接相连的文字)调整参与au tho rity计算的链接的权重,将大的hub页面为小的单元.

基于H IT S的系统包括CL EV ER.Google也基于了同样的原理.这些系统由于纳入了W eb链接和文本内容信息,查询效果明显优于基于词类索引引

804计算机研究与发展2001年擎产生的结果(如A lta V ista)和基于本体论生成的结果(如Yahoo!).

4　W eb使用记录的挖掘

除了W eb内容和W eb链接结构,W eb挖掘的另一个重要任务是W eb使用记录挖掘,它通过挖掘W eb日志记录来发现用户访问W eb页面的模式[14,15,27].通过分析和探究W eb日志记录中的规律,可以识别电子商务的潜在客户,增强对最终用户的因特息服务的质量和交付,并改进W eb服务器系统的性能和结构.目前研究较多的W eb使用记录挖掘技术和工具可分为两大类:模式发现和模式分析. 4.1　W eb使用记录中的模式发现

用户访问模式的发现采用了来自人工智能、数据挖掘、信息论等领域的成熟技术,从W eb使用记录中挖掘知识.但在新的环境中,有许多新的问题需要考虑和研究.

在模式发现中,首先要解决的问题就是数据的预处理,它主要包括如下两个部分:数据清洗(data clean ing)包括无关记录的剔除、判断是否有重要的访问没有被记录、用户的识别等问题;事务识别(tran sacti on iden tificati on)是指将页面访问序列划分为代表W eb事务或用户会话的逻辑单元.

在对事务进行了划分后,就可以根据具体的分析需求选择访问模式发现的技术,如路径分析、关联规则挖掘、时序模式以及聚类和分类技术.路径分析(path analysis)可以用来发现W eb站点中最经常被访问的路径,从而可以调整站点的结构.在W eb使用记录挖掘的环境下,关联规则挖掘的目标是发现用户对站点各页面的访问之间的关系,这对于电子商务是非常有用的.时序模式的发现,各种聚类和分类技术的采用对于W eb使用记录中的模式发现都有其各自的作用.

现有30多种商用的W eb L og挖掘工具[24],大部分速度慢,并且做了一些假设以便减少要分析的L og文件的大小.这些工具的性能、包容性和分析的深度还有一定的.一般包含一些经常使用的报告:点击数和传输字节数的汇总报告、排名靠前的被请求的U RL、引用者以及最常用的浏览器列表、每个互联网域的点击次数、出错报告、目录树报告等. 4.2　模式的分析

如果没有合适的技术和工具来辅助分析人员的理解,采用各种技术挖掘出来的模式将不能得到很好的利用.所以开发各种分析技术和工具也是非常必要的.目前这个领域的工作还不是很多,是一个较新的领域.

可视化技术在其它领域中的应用已经取得了巨大的成功,因此对于理解W eb用户的行为模式来讲也是一个自然的选择.P itkow等人已经开发了W ebV iz系统来将WWW的访问模式可视化.此外,联机分析处理(OLA P)技术也可以应用到模式的分析中来[28].在W EBM I N ER[29]系统中还提出了类似于SQL的形式化的查询机制.

由于W eb L og可以提供很多关于W eb的信息,通过对日志文件的分析,可以提供各种各样的统计报告,完成日常管理工作,发现潜在的客户、用户和市场等.计划挖掘(p lan m in ing)挖掘通常的存取规律,可以调整W eb连接,改善性能;相关 序列存取模式分析,可以对服务器的缓存、预取和交换参数进行调整;趋势分析,可以了解W eb正在发生的变化;用户的个性化分析可以为用户提供定制的服务.

下面给出一个系统的例子.V irtual2U是一个基于服务器的软件系统,它具有个性化的设计、交付和增强通过WWW发布的教育和训练课程的功能,由V group,U2chat,assignm en t subm issi on,cou rse structu ring,teach ing suppo rting,w o rk sp ace,file up load,grade book和sys adm in子系统组成. V irtual2U的日志不记录如客户使用了浏览器哪些功能,像页面内的回退、页面的翻滚等,对存放在缓存中页面的请求,对存放在代理服务器上页面的请求信息.V irtual2U日志文件也有一些特殊情况:不同的用户调用相同的CG I脚本,相同的用户动作在不同的时间可能调用不同的CG I脚本,同一个用户有时使用不止一个浏览器.V irtual2U有两个日志文件,一个日志文件包含浏览器的类型和请求的页面,另一个的格式如下:

dd232125.com pu serve.com　rhu ia　[01 A p r 1997:00:03:2520800]　“GET SFU cgib in V G V G dspm sg.cgi?ci=40154&m i=49H T T P 1.0”200417904

4期韩家炜等:W eb挖掘研究　　根据日志文件提供的信息,一个是做联机分析(OLA P),对一些常用的数据进行汇总,如统计由用户、域和会话发出的单一动作的频率,统计各种不同错误的频率,将用户发出的动作划分为行为,例如reading m essages in a conference.通过联机分析可以回答诸如哪个部件或特征被经常 不经常引用,哪个事件是经常发生的,不同领域用户的分布情况,不同领域或不同地区用户的存取方式是否不同,有什么不同等问题.另一个是做联机挖掘(OLAM),包括模式分析和趋势分析.前者分析当增加或修改V irtual2 U的featu res时,不同用户之间、不同课程之间、in structi onal design s和m aterials之间的关系,后者分析用户行为随时间的变化趋势,网络流量随时间的变化趋势.通过联机挖掘可以回答一些深层次上的问题,例如各种部件和特征在什么上下文中使用,什么是典型的事件序列,在不同的用户中对资源的使用和存取模式有什么不同,针对课程的使用和存取模式有什么不同,对一个给定的环境全部的使用模式是什么,用户的行为随着时间是怎样变化的,随着服务质量(速度的快或慢)的变化,使用模式是怎样变化的,网络流量随时间的分布是什么.

4.3　W eb使用记录挖掘的基本流程

对W eb L og进行分析和挖掘要经过一系列的数据准备工作和建模工作.一个基本的流程如图2所示.

(1)首先要对W eb L og进行清洗、过滤和转换,从中抽取感兴趣的数据.处理过程如图3所示

.

图2　W eb L og

挖掘的过程

图3　W eb L og的清洗、过滤和转换

　　(2)将U RL、动作、资源的类型、资源的大小、

请求的时间、在资源上停留的时间、请求者的

In ternet域名、用户、服务器状态作为D ata Cube的

维变量,将对模块、页面和文件请求次数、来自不同

In ternet域请求次数、事件、会话、带宽、错误次数、

不同浏览器种类、用户所在组织作为度量变量建立

D ata Cube.

通过对D ata Cube的切块、切片分析可以回答:

哪些成分或特色被经常或偶尔使用,网络流量随时

间的变化规律(按时、日、月等),用户在不同

In ternet域的分布情况,来自不同地区的用户在存

取方式上是否有 有什么差异.

(3)利用成熟的数据挖掘技术(如特征、分类、

关联、预测、时间序列分析、趋势分析)进行W eb流

量分析、典型的事件序列和用户行为模式分析、事务

分析,可以回答成分和特色在什么上下文中被使用;

014计算机研究与发展2001年

什么是典型的事件序列;在用户中是否有共同的行为模式,是什么;不同用户群在使用和行为上有什么差异;用户的行为是否随时间变化,怎么变化等问题.

通过分析W eb存取日志能帮助理解用户的行为和W eb结构,因此,可以改进W eb页面的设计和W eb应用程序,发现潜在的电子商务客户.目前的日志并没有收集足够的信息.在分析过程中对数据清洗和转换是非常重要的,并且经常需要站点结构知识(元数据).OLA P从不同的视角不同的概念层次提供了数据视图,而W eb L og数据挖掘提供了深层次的报告,像时间序列分析、相关、分类等.

通过使用这类W eb L og文件,可以进行一些研究工作,如系统性能分析,通过W eb缓存改进系统设计、W eb页面预取、W eb页面交换(s w app ing);认识W eb信息访问的本质;理解用户的反映和动机.例如,有些研究提出了可适应站点(adap tive site)的概念:即可以通过用户访问模式的学习改进其自身的W eb站点.W eb L og分析还有助于建立针对个体的个性化W eb服务.

由于W eb L og数据提供了用户访问W eb页面的信息,因此W eb L og信息可以与W eb内容和W eb链接结构挖掘集成起来,用于W eb页面的等级划分、W eb文档的分类和多层次W eb信息库的构造.

5　多层次W eb数据仓库的建立与操作:MLD B与W EB ML

W eb是一个没有标准、没有结构、异构的系统,并且在以很快的速度增长、变化,造成为进行搜索而建的索引很快不能反映真实情况而失效.如何对一个巨大的、分布的、高度异构的、半结构的、支持超文本和超媒体、经过网络互相连接的不断变化的信息库进行查询和挖掘?建立一个多层数据库(m u lti p le layered database,M LDB),用数据库技术来管理W eb的元数据(M eta2W eb)是其中的一个方法[30].它是一个分层的数字图书目录,其作用类似于电话号码本中的黄页.由于W eb上信息的多样性、多变性和巨大的数量,对原始信息进行结构化处理,再利用数据库技术进行管理和查询是非常困难的,也是不实际的.多层数据库的主要思想是概括(generalizati on),即根据经常出现的查询模式,对W eb上的原始信息进行概括归纳,形成多层次的结构化的数据库.

5.1　MLD B

一个M LDB由3个主要部分构成:{S,H,D},各部分的定义如下:

(1)S:一个数据库模式,它包含了关于分层数据库结构的元信息;

(2)H:概念层次的集合;

(3)D:M LDB各层中数据库关系的集合.

数据库模式描述了M LDB的全局结构,存储了包括结构、数据类型、取值范围等在内的通用信息.此外,它还描述了从低层关系得到高层关系的路径图,以及所采用的归纳方法.概念层次的集合是预先定义的,可以协助系统向高层概括低层信息,以及将查询映射到相应的层次.D不仅包括原始的全局信息库,而且包括经过概括归纳的各层次的数据库关系.

我们可以将W eb上的原始信息作为M LDB的最底层L ayer20,该层信息的多样性和海量使得对其的管理是非常困难的.基于全局信息的访问模式和访问频率,L ayer21可以被组织为多个关系表,如docum en t,p erson,o rgan izati on,i m ages,sounds, softw are,comm ercial data等.L ayer21是对最底层信息的抽象或描述,它是数据库系统可管理的最底层信息.该层信息由各个站点分别构建和存储,每个站点对自己的文档进行综合以后在每个站点形成L ayer21.在L ayer21的基础上构建更高层的数据库需要采用概括归纳技术,这种概括归纳可能在多个方向上进行,例如根据不同的分类原则进行划分,或者进一步概括某些属性,合并相同的元组,形成汇总表,或者对两个或多个关系进行连接,形成新的关系表等等.在进行抽象时,需要领域专家提供一个概念层次,然后利用面向属性的综合方法自动完成综合工作.下面用一个例子来说明信息组织的这种层次关系.

例1.

(1)假设L ayer21由2个关系组成:docum en t 和person,一种可能的结构如下:

docum en t(file addr,au tho rs,title,pub licati on, p ub licati on date,ab stract,language,tab le of con ten ts,catego ry descri p ti on,keyw o rds,index, m u lti m edia attached,num pages,fo r m at,first p aragraph s,size doc,ti m estam p,access frequency, link s in,link s ou t,…)

p erson(last nam e,first nam e,hom e page addr,po siti on,p ictu re attached,phone,e2m ail,

office address ,educati on ,research in terests ,

p ub licati on s ,size of hom e p age ,ti m estam p ,access frequency ,…)

以docum en t 为例,关系中的一个元组是L ayer 20中一个文档的抽象,file addr 表示了存放文档的文件名和U RL ,size doc 是文件的大小,ti m estam p 是文件的最后一次修改时间,access frequency 记录了存取频率,它或者是该元组的存取

次数,或者是从W eb L og 中统计出来的文档的存取次数等等.

(2)将上面的L ayer 21经过简化得到L ayer 22:doc b rief (file addr ,au tho rs ,title ,p ub licati on ,p ub licati on

date ,ab stract ,language ,catego ry

descri p ti on ,key w o rds ,m ajo r index ,num p ages ,fo r

m at ,size doc ,access frequency ,link s ou t )

person b rief (last nam e ,first nam e ,pub lica 2

ti on s ,affiliati on ,e 2m ail ,research in terests ,size hom e p age ,access frequency )

(3)对第2层采用多种技术概括归纳,可能得

到如下的L ayer 23:

cs doc (file addr ,au tho rs ,title ,pub licati on ,p ub licati on date ,ab stract ,language ,catego ry descri p ti on ,keyw o rds ,num p ages ,fo r m ,size doc ,link s ou t )

doc summ ary (affiliati on ,field ,pub licati on year ,coun t ,first au tho r list ,file addr list )

doc

au tho r

b rief

(file

addr ,

au tho rs ,

affiliati on ,title ,pub licati on ,p ub date ,catego ry descri p ti on ,keyw o rds ,num pages ,fo r m at ,size doc ,link s ou t )

p erson summ ary (affiliati on ,research in terest ,year ,num p ub licati on s ,coun t )

图4　多层次W eb 数据仓库的建立

　　建立多层数据库的第1步是实现L ayer 21,即从原始的无结构的信息向具有较好结构的可管理的数据转换和归纳.首先要解决异构问题,因为不同的站点可能采用不同的数据库管理系统,可以采用将不同数据库中的数据以XM L 文档的形式来表现,目前很多商用数据库都提供该功能.XM L 文档利用D TD 来对文档使用的标签(tag ),标签的顺序、标签之间的嵌套关系进行自我描述,从而达到描述文档结构的目的,但由于XM L 允许用户自由定义标签(tag ),不同的W eb 维护者对同一个事物可能采用不同的标签来描述,不利于信息的共享.自1995年以来,为了方便W eb 上的信息查询,D ub lin Co re w o rk shop 集中了来自世界各地的相关领域的专家,提出了一套描述符用以描述文档的内容、表现形式和相关属性,目前共有15个描述符:T ITL E ,CR EA TOR ,SUBJECT ,D ESCR IPT I ON ,PUBL ISH ER ,CON TR I BU TOR ,DA T E ,T YPE ,FORM A T ,

I D EN T IF IER ,SOU RCE ,LAN GU 2

A GE ,R ELA T I ON ,COV ERA GE ,R IGH T S .可以将

这套描述符作为第1层的标准描述符,就像数学领域

采用M ath M L 作为交换数学信息的标准描述符一样,这样就解决了结构的问题.对于目前大量H TM L 语言的站点,可以采用专门的抽取和转换工具逐步过渡到XM L .

各站点通过各种转换工具,形成自己的L ayer 1数据库,这些数据库通过In ternet 构成了一个巨大的全局L ayer 1数据库.虽然可以在L ayer 1数据库上完成查询,但对于涉及大量站点的查询,其效率一定是低下的.因此,有必要通过抽象和综合形成更高层的数据库,由于这些数据库的体积相对较小,可以在主干网的站点上或本地服务器上存放多个副本,从而提高查询响应速度.5.2　W EB ML

W EBM L

[31]

是采用类似SQL 语法的查询语言,

它针对的是W eb 资源查询和W eb 知识挖掘.因为在M LDB 中概念是按层次综合的,查询条件不一定与当前抽象层次一致,可能更抽象或更特例化,因此

covers　=　覆盖;

covered2by　<　包容;

like　≈　同义词;

close2to　～　近似.

这些操作符可以完成对不同层次概念的互操作.

下面是W EBM L的顶层语法:

〈W EBM L〉∷=〈M ine H ead er〉from rela tion list

[related2to nam e list][in loca tion list]

w here w here clause

[o rder by a ttribu tes nam e list]

[rank by{inw a rd ou t w a rd access}]

〈M ine H ead er〉∷={{select list}{a ttribu te nam e list 3}

〈D escribe H ead er〉 〈C lassif y H ead er〉}

〈D escribe H ead er〉∷=m ine descri p ti on

in2relevance2to{a ttribu te nam e list 3}

〈C lassif y H ead er〉∷=m ine classificati on

acco rding2to a ttribu te nam e list

in2relevance2to{a ttribu te nam e list 3}

W EBM L在许多方面借鉴了数据挖掘语言DM QL,提供了对抽象概括数据的查询和知识挖掘能力.

随着结构化标记语言XM L越来越流行,被人们接受和采纳,可以预期未来将会有大量的W eb页面用XM L书写,并遵循一组好的文档类型说明(docum en t typ e declarati on s,D TD).类似XM L的标准化语言,可以有利促进不同W eb站点间的信息交换和方便构造多层次W eb信息库的信息提取.而且更便于设计和实现基于W eb的信息搜索和知识发现语言.

总之,基于以上讨论,构造多层次W eb信息库应该是可能的,它可以方便因特网上的资源发现、分析和数据挖掘.可以预期基于W eb的分析和数据挖掘将成为因特网上信息服务的重要部分.

6　结束语

万维网目前是一个巨大、分布广泛、全球性的信息服务中心,它包含了丰富和动态的超链接信息以及W eb页面的访问和使用信息,这为数据挖掘提供了丰富的资源.本文重点介绍了用于识别权威页面的W eb链接结构挖掘、多层次W eb信息库的建立以及W eb L og挖掘的技术和方法.

W eb挖掘是一个较新的研究领域,还有许多问题有待于进一步的研究和深化.在这里我们给出一些W eb使用记录挖掘的未来研究方向.首先,在数据的预处理方面,开发更好的数据收集机制和技术是非常必要的,可以为分析提供更丰富的信息.此外,多种信息(如W eb使用记录、用户注册信息等)的智能集成也值得进一步的研究.在挖掘处理方面,已有的挖掘方法的性能有待于进一步的改进;针对W eb使用记录的增量变化和分布特性,可以开发新的模型.开发能够协助理解挖掘出的知识的智能工具也是该领域的一个重要方向.

未来随着XM L的兴起,W eb页面会蕴涵更多的结构化和语义信息,这会使W eb挖掘工作变得更为有效,也更为容易.同时W eb文档的自动分类、多层次W eb信息库的建立以及W eb L og挖掘仍然会是W eb挖掘的主题.

参考文献

1H an J,Kam ber M.D ata M ining:Concep ts and T echniques.

San M ateo,CA:M o rgan Kaufm ann,2000

2I m ielinsk i T,M annila H.A database perspective on know ledge discovery.Comm unicati ons of A CM,1996,39(11):58～ 3M eo R,P saila G,Ceri S.A new SQL2like operato r fo r m ining associati on rules.In:VLDB’96.Bom bay,India,1996.122～133

4Jones K S,W illett P et a l.R eadings in Info r m ati on R etrieval, 3rd ed.San M ateo,CA:M o rgan Kaufm ann,1997

5E tzi oni O.T he W o rld W ide W eb:Q uagm ire o r go ld m ine.

Comm unicati ons of A CM,1996,39(11):65～68

6Fayyad U M,P iatetsky2Shap iro G,Sm yth P et a l.A dvances in Know ledge D iscovery and D ata M ining.AAA I M IT P ress, 1996

7Faloutso s C.A ccess m ethods fo r text.A CM Computer Surv, 1985,17(1):49～74

8Feldm an R,D agan I.Know ledge discovery in textual databases(KD T).In:P roc of1st Int’l Conf on Know ledge

D iscovery and D ata M ining.M ontreal,Canada,1995

9Chak rabarti S.D ata m ining fo r hypertext:A tuto rial survey.

S IGKDD Exp lo rati on,2000,1(2):1～11

10Gravano L,Garcia2M o lina H,Tom asic A.T he effectiveness of gi o ss fo r the text database discovery p roblem.In: S IG M OD’94.M inneapo lis,M N,1994.126～137

11Salton G.A utom atic T ext P rocessing.R eading,M A:

A ddison2W esley,19

12Salton G,A llen J,Buck ley C et a l.A utom atic analysis,them e generati on,and summ arizati on of m ach ine2readable texts.Science,1994,2:1421～1426

13Coo ley R,M O basher B,Srivastava J.W eb m ining: Info r m ati on and pattern discovery on theW o rld W ideW eb.In:

P roc of the9th Int’l Conf on Too ls w ith A rtificial Intelligence

(I CTA I’97).CA,1997.558～567

14Perkow itz M,E tzi oni O.A dap tive sites:A utom atically learning from user access patterns.In:P roc of6th Int’lW o rld W ide W eb Conf.Santa C lara,Califo rnia,1997

15P itkow J.In search of reliable usage data on the WWW.In: P roc of6th Int’l W o rld W ide W eb Conf.Santa C lara,

Califo rnia,1997

16Chak rabarti S,Dom B E et a l.M ining the W eb’s link structure.Computer,1999,32(18):60～67

17K leinberg J M,Tom k ins A.A pp licati on of linear algebra in info r m ati on retrieval and hypertext analysis.In:P roc of18th

A CM Symp.Ph iladelph ia,PA,1999.185～193

18B rin S,Page L.T he anatom y of a large2scale hypertextualw eb search engine.In:P roc of7th W o rld W ide W eb Conf

(WWW’98).B risbane,A ustralia,1998

19K leinberg J M.A utho ritative sources in a hyperlinked environm ent.Journal of A CM,1999,46(5):604～632

20Chak rabarti S,Dom B E,Indyk P.Enhanced hypertext classificati on using hyper2link s.In:P roc of A CM2S I O G M OD

Int’l Conf on M anagem ent of D ata(S IG M OD’98).Seattle, W A,1998.307～318

21W ang K,Zhou S,L iew S C.Building h ierarch ical classifiers using class p roxi m ity.In:P roc of VLDB’97.Edinburgh,U K,

1999.363～374

22Backm an D,R ubbin J.W eb log analysis:F inding a reci pe fo r success.1997.h ttp: techw eb.comp.com nc 811 811cn2.

h tm l

23Zaiane O R,X in M,H an J.D iscovering W eb access patterns and trends by app lying OLA P and data m ining techno logy on W eb L ogs.In:P roc of A dvances in D igital L ibraries Conf

(ADL’98).Santa Barbara,CA,1998.19～29

24Stabin T,Glasson C E.F irst i m p ressi on:7comm ercial log p rocessing too ls slice&dice logs your w ay.1997.h ttp: www.netscapewo rld.com netscapewo rld nw20821997 nw2082 loganalysis.h tm l

25Sullivan T.R eading reader reacti on:A p ropo sal fo r inferential analysis of W eb server log files.In:P roc of3rd Conf on

H um an Facto rs&the W eb.D enver,Co lo rado,1997

26Srivastava J et a l.W eb usage m ining:D iscovery and app licati on of usage patterns from W eb data.S IGKDD

Exp lo rati ons,2000,1(2):12～2327Graham2Cumm ing J.H its and m iss2es:A year w atch ing the W eb.In:P roc of6th Int’l W o rld W ide W eb Conf.Santa

C lara,Califo rnia,1997

28Gaede V,Gunther O.M ultdi m ensi onal access m ethods.A CM Computer Surv,1998,30(1):170～231

29M obasher B,Jain N,H an E et a l.W eb m ining:Pattern discovery from W o rld W ide W eb transacti ons.U niversity of M inneso ta,T ech R ep:TR962050,1996

30Zaiane O R,H an J.R esource and know legde discovery in global info r m ati on system s:A p reli m inary design and experi m ent.In:P roc of KDD’95.M ontreal,Canada,1995.

331～336

31Zaiane O R,H an J.W eb M L:Q uerying the W o rld2W ide W eb fo r resources and know ledge.In:P roc of Int’lW o rk shop W eb Info r m ati on and D ata M anagem ent(W I DM’98).Bethesda, M D,1998.9～

12

　　韩家炜　男,1948年生,博士,教授,主

要研究方向为数据库、数据挖掘、数据仓

库

.

　　孟小峰　男,19年生,博士,副教

授,主要研究方向为数据库系统、W eb数

据管理、移动数据管理等

.

　　王　静　女,1975年生,博士研究生,

主要研究方向为数据库系统、W eb数据管

理等

.

　　李盛恩　男,1963年生,副教授,博士

研究生,主要研究方向为数据仓库和数据

挖掘.