（计算机应用技术专业论文）web使用挖掘方法的研究和实现.pdf

w e b 使用挖掘方法的研究和实现 摘要 w e b 挖掘是将数据挖掘和w w w 这两个领域中的多种技术和方法结合起 来的热门研究课题。一般来说，它的研究领域包括w e b 内容挖掘、w e b 结构挖 掘和w e b 使用挖掘。其中，w e b 使用挖掘的研究目的在于发现用户浏览网站的 行为规律，改善站点的结构和页面间超链接结构，提高站点服务质量以及在电 子商务中的客户关系管理方面的决策支持。本文在介绍w e b 使用挖掘发展概况 的基础上，详细论述了w e b 使用挖掘的整个过程和相关技术。本文所做的主要 工作和新见解如下： 详细论述了w e b 挖掘的定义、体系结构和分类，并且阐述了各个类别 的主要研究内容： 阐述w e b 使用挖掘的定义、过程，以及各个阶段的研究内客和相关技 术： 在w e b 使用挖掘的数据预处理阶段，提出了一种新的会话构造方法一 一基于时间和引用的启发式方法。该方法不仅利用了用户会话的时间 特性，而且考虑了用户的浏览特性。所以，这在一定程度上方便了用 户频繁访问模式的挖掘； 在第四章中，本文在修改f p ，t r e e 算法的基础上，提出一种发现用户 频繁访问模式的算法( f a p m i n i n g ) 。浚算法可以用于发现不同类型的 网站用户的访问模式，并且可以根据专家设定的支持度阈值发现用户 的频繁访问模式； 设计开发了w e b 使用挖掘实验系统( w e bu s a g em i n i n ge x p e r i m e n t a l s y s t e m ) 。此系统包含四个主要功能模块：数据清洗模块、会话构造模 块、流量分析模块和访问模式挖掘模块。会话构造模块中不仅实现了 基于时间和引用的会话构造方法，并且将它与其它流行的会话构造方 法进行了比较；流量分析模块从总体上分析网站的浏览情况；访问模 式挖掘模块实现了本文第四章提出的f a p m i n i n g 算法。 关键词：数据库知识发现、数据挖掘、w e b 挖掘、w e b 使用挖掘、会话构造、 频繁访问模式 t h er e s e a r c ha n di m p l e m e n to fm e t h o d so nw e b u s a g e m i n i n g a b s t r a c t w e bm i n i n gi st h eh o tr e s e a r c hi s s u ew h i c hc o m b i n e sv a r i o u st e c h n o l o g i e s a n dm e t h o d sb e t w e e nd a t am i n i n ga n dw w w i ng e n e r a l w e bm i n i n gi n c l u d e s t h r e er e s e a r c hd o m a i n ：w e bc o n t e n tm i n i n g 、w e bs t r u c t u r em i n i n ga n dw e bu s a g e m i n i n g i nt h e s e a r e a s ，w e bu s a g em i n i n ga i m sa t t h er u l ed i s c o v e r yo fs i t e s v i s i t o r sb r o w s i n gb e h a v i o r s ，t h ei m p r o v e m e n to fs i t e s s t r u c t u r ea n dt h el i n k a g e s t r u c t u r ea m o n gp a g e s ，t h ee n h a n c e m e n to nt h eq u a l i t y o fw e bs e r v i c e sa n dt h e d e c i s i o ns u p p o r to nc l i e n tr e l a t i o n s h i pm a n a g e m e n to ft h ee 。c o m m e r c e o nt h e b a s i so ft h ei n t r o d u c t i o no ft h ed e v e l o p m e n ts u r v e yo fw e bu s a g em i n i n g ，t h et h e s i s d i s c u s s e st h ep r o c e d u r eo fw e bu s a g em i n i n ga n ds o m et e c h n o l o g i e sr e l e v a n tt o e a c hp h r a s ei nw e bu s a g em i n i n g t h em a i nw o r ka n dn o v e li d e a so f t h et h e s i sa r e s h o w e da sf o l l o w i n g ： t h ed e s c r i p t i o no ft h ed e f i n i t i o n t a x o n o m ya n dc l a s s i f i c a t i o no fw e b m i n i n g ，a n dm a i n c o n t e n ti ne a c hr e s e a r c ha r e ao fw e b m i n i n g ； t h e d e s c r i p t i o no f t h ed e f i n i t i o n p r o c e d u r eo fw e b u s a g em i n i n g a n dt h e e x p l o r a t i o no ft h e r e s e a r c hc o n t e n ta n dr e l a t e dt e c h n o l o g i e si ne v e r y p h r a s eo f w e b u s a g em i n i n g ； w e g i v e an o v e ls e s s i o n c o n s t r u c t e dm e t h o d w h i c h i st h e t i m e a n d r e f e r r e r - b a s e dh e u r i s t i cm e t h o d i tn o to n l yu s e st h et i m e c h a r a c t e r i s t i co fs e s s i o nb e t w e e nu s e r sa n dw e bs i t e s ，b u ta l s oc o n s i d e r s t h e u s e r s b r o w s i n gc h a r a c t e r i s t i c t h u s ，i t f a c i l i t a t e st h e m i n i n g o f u s e r s f r e q u e n ta c c e s sp a t t e r n st os o m ee x t e n t ； i nc h a p t e rf o u r ，w e p u t f o r w a r dar e v i s e da l g o r i t h m ，w h i c hi s t h e f a p m i n i n ga l g o r i t h m ，b a s e d o nt h e f p - p a t t e r ng r o w t ha l g o r i t h m t o m i n ef r e q u e n ta c c e s sp a t t e r n s ；t h ea l g o r i t h mc a nb eu s e dt od i s c o v e r a c c e s s p a t t e r n s o fa l l t y p e s o fu s e r sa n d f r e q u e n t a c c e s s p a t t e r n s a c c o r d i n gt ot h es u p p o r t t h r e s h o l dv a l u ed e c i d e db ye x p e r t s ； t h e d e s i g na n dd e v e l o p m e n to f w e b u s a g em i n i n ge x p e r i m e n t a ls y s t e m t h i ss y s t e mc o n s i s t so ff o u rf u n c t i o nm o d u l e s ：d a t a c l e a n i n gm o d u l e 、 s e s s i o nc o n s t r u c t i o nm o d u l e 、w e bt r a f f i ca n a l y s i s ，a n da c c e s sp a t t e r n m i n i n g m o d u l e ，s e s s i o nc o n s t r u c t i o nm o d u l e i m p l e m e n t s t h e t i m e a n d - r e f e r r e r - b a s e dh e u r i s t i cm e t h o da n d c o m p a r e s i tt oo t h e r p o p u l a r s e s s i o n - c o n s t r u c t e dh e u r i s t i c m e t h o d s ；w e b t r a f f i cm o d u l e a n a l y s e st h eg e n e r a la c c e s sp r o f i l eo faw e bs i t e ；a c c e s sp a t t e r nm i n i n g m o d u l ef u l f i l l st h ef a p m i n i n ga l g o r i t h m k e yw o r d s ：k n o w l e d g ed i s c o v e r yi nd a t a b a s e s 、d a t am i n i n g 、w e bm i n i n g 、 w e b u s a g em i n i n g 、s e s s i o nc o n s t r u c t i o n 、f r e q u e n ta c c e s sp a t t e r n 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学 硕士学位论文质量要求。 答辩委员会签名：( 工作单位、职称) 揣耘飞缈b 咖卿耥交 委员： 导师： 殄伽 f 台肛锻钦 f l l曩蚤 万侈笔 娥旋 f4二川，i 彭1 眩 独创性声明 本人声明所呈交的学能论文是本人在导师指导f 进行的研究1 ：作及取得的研究成果。据 我所知，除了文中特别加以标志芹l l 致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果也不包含为获得盒胆1 ：、业厶堂 或其他教育机构的学位或证书而使用过的材 料。与我一同i ：作的同忠对本研究所做的任何贡献均已住论文中作了明确的说明井表示谢 意。 学位论文佧襁字：浮噼字吼怫彤月力日 学位论文版权使用授权书 本学位论文作者完全了解佥蜓：、业厶堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本入授权金 壁：! ：些厶堂可以将学位论文的全部或部分论文内容编入有关数据序进行检索，可以采削影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密厉适_ i _ j 本授权伸) 学 奇论文作者毕业厉去向： i 作单位： 通讯地划： 挪繇钟鲴一哆 签字日期：2 瞬6 月泸日 该偶电话 邮编 致谢 光阴似箭，日月如梭，充实而艰辛的三年硕士研究生学习生活就要结束了， 我即将开启人生新的旅程。回想这三年研究生期间的学习、研究和生活，我离 不开诸多良师益友的指导和帮助以及家人的鼓励和支持，在此我衷心地向他们 表示感谢! 首先感谢我的导师欧阳一鸣副教授三年期间对我的精心培养。他在课题的 选择、研究和论文撰写期间给了我悉心的指导，引领我步入w e b 挖掘的殿掌。 而且，他耐心地指导我解决f ； 进中的难题，使我独立科研的能力得到了锻炼和 提高，让我得以顺利地完成这篇论文。另外，欧阳老师渊博的知识、严谨的治 学态度和精益求精的求学精神，使我受益匪浅。他宽以待人、严于律己的工作 作风对我产生了深刻的影响。在此，我再次向欧阳一鸣老师表示我最诚挚的澍 意。 接下来我要感谢胡学钢教授以及人工智能和数据挖掘实验室的所有成员。 在实验室举办的研讨会中，老师和同学们的交流，让我获得更多更新的知识， 并且认识到自己正在研究的工作中的不足，加以改进。在这里，我尤其要感谢 我的师妹张炎和陈敏在日常学习和研究工作中给予我的极大帮助，感谢网络中 心的谢扬和陈源源同学在提供实验数据上给予我的帮助，以及王静秋同学在实 验编程中所做的工作。 此外，我还要感谢计算机学院的王新生、徐静两位老师为了我的学业和论 文所付出的辛勤工作。 最后，我要向我的父母和姐姐致以最衷心的感谢! 他们对我的无私关爱和 殷切期望是我前进的动力；他们的谆谆教诲让我学会了以乐观开朗的态度去迎 接学习和生活中的各种挑战。 谨以此文献给我的家人和所有关心支持我的老师、同学和朋友。 作者：汪曦东 2 0 0 4 年5 月 第一章绪论 1 1 数据库知识发现和数据挖掘 随着计算机技术的不断发展和信息量的快速膨胀，淹没在数据海洋中的人 们常常会因为寻找不到有用的信息而困惑不己。所以如何从“数据丰富而信息 贫乏( d a t a r i c ha n di n f o r m a t i o np o o r ) ”的窘境中解脱这一问题，引起全世界相 关领域专家学者们的广泛重视。 1 9 8 9 年在美国底特律市召丌的第1 1 届国际人工智能联合会议的专题讨论 会上首次出现数据库知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 这一专业名 词，简称k d d 。它泛指所有从源数据中发掘模式或联系的方法。目前大家公认 的k d d 严格定义是在1 9 9 6 年知识发现国际会议上由f a y y a d 、p i a t e s t s k y 、s h a p i r o 和s m y t h 提出： k n o w l e d g ed i s c o v e r yi nd a t a b a s e si st h en o n t r i v i a lp r o c e s so fi d e n t i f y i n g v a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a 数据库中的知识发现是从数据集中提取出有效的、新颖的、有潜在作用的、 可信的，并能最终可被理解的模式的非平凡过程”1 。 上面的定义中，有几个概念需要进一步解释： 数据集是一组事实f ( 如关系数据库中的电录) ； 模式是用语言l 来表示的一个表达式e ，它可用来描述数据集f 的某个子 集f e ，e 作为一个模式要求它比数据子集f e 的枚举要简单( 所用的描述 信息量要少1 ； 过程通常是指多阶段的一个过程，涉及数据准备、模式搜索、知识评价， 以及反复的修改求精。该过程要求是非平凡的，意思是要有一定程度的 智能性、自动性( 仅仅给出所有数据的总和不能算作是一个发现过程) ； 有效性是指发现的模式对于新的数据仍保持有一定的可信度； 新颖性要求发现的模式应该是新的； 潜在的可用性是指发现的知识将来有实际效用，如用于决策支持系统 里可提高经济效益； 最终可理解性要求发现的模式能被用户理解。目前它主要是体现在简洁 性上。有效性、新颖性、潜在有用性和最终可理解性综合在一起可称之 为兴趣性( i n t e r e s t i n g n e s s ) 。 知识发现过程由以下步骤组成2 1 ( o h 图1 1 所示) ： ( 1 1 数据清理( 消除噪声或不一致数据) ( 2 ) 数据集成( 多种数据源可以组合在一起) ( 3 ) 数据选择( 从数据库中检索与分析任务有关的数据) ( 4 1 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作) ( 5 ) 数据挖掘( 基本步骤，使用智能方法提取数据模式) ( 6 ) 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) ( 7 ) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘出的知识) 幽1 - 1 知t 5 l 发现的过群 k d d 是一门涉及非常多领域的交叉学科，不同领域的专家对其有不同的定 义。在人工智能和数据库领域，另外一个广泛使用的概念是“数据挖掘”。数 据挖掘是从大量数据中挖掘出隐含的、先前未知的、对决策有潜在价值的知识 和规则。从k d d 和数据挖掘的定义中我们可以看出：二者之间具有紧密的联系， 其中的概念都是相互对应或隐含的。对于二者之间的关系，学术界也存在两种 观点：一种观点认为k d d 和数据挖掘的含义相同，只是名称不同；而另一种观 点认为，数据挖掘是k d d 中专门发现知识的核心环节( 如图1 1 所示) ，而k d d 是一个交互式、循环反复的整体过程，除了包括数据挖掘外还包括数据准备和 发现结构解释评估等诸多环节。本文倾向于第二种观点，作为一个科学研究领 域，数据挖掘和k d d 的确有一定的重合度。但是数据挖掘也是一个多学科交叉 的研究领域，它包括数据库技术、人工智能、机器学习、神经网络、统计学、 模式识别、知识工程、信息检索、高性能计算和数据可视化等研究领域。 数据挖掘技术出现于2 0 世纪八十年代，在9 0 年代有了突飞猛进的发展。目 前，它所挖掘出来的知识可应用于金融、国防军事、医疗保健、市场营销、科 学研究等各个领域。尽管目前数据挖掘的产品还不够完善，但是我们有信心和 理由相信在广大研究人员的共同努力下数据挖掘技术能够在实际生产生活中 得到广泛的应用。 1 2w e b 挖掘产生的背景 伴随着网络和通信技术的飞速发展，作为全球最大的信息服务平台的 i n t e r n e t 正在以前所未有的速度渗入到人类的生产和生活的各个方面。据 i d g ( i n t e r n a t i o n a ld a t ag r o u p ) 近期公布的一项报告称，1 9 9 8 年全球使用i n t e r n e t 的人数己达到1 亿左右，到2 0 0 2 年会增加到3 2 亿。i n t e r n e t 的普及同时推动了 w w w ( w o r l dw i d ew e b 万维网) 的迅猛发展，据统计每2 个小时就有一个新的 w w w 服务器产生，1 9 9 8 年己经大约有3 2 0 ，0 0 0 ，0 0 0 个w e b 文档。w w w 作为信 息发布和交流的全球性媒体，它的内容涵盖了包括科研、教育、商业、会融、 军事等各个领域。正是由于w e b 上包含巨大的信息量使得越来越多的用户感觉 到在w w w 上寻找自己想要的信息犹如“大海捞针”一样困难。据说，9 9 的 w e b 信息相对9 9 的用户来说都是无用的【3 l 。用户关心的其实只是w e b 信息中 极少的一部分，而且大量的无关信息会干扰甚至淹没用户感兴趣的内容。所以 如何快速、准确且高效地从浩瀚的w e b 信息资源中搜寻和发现用户感兴趣的信 息和知识已经成为一个迫切需要解决的问题。而将传统的数据挖掘技术与w e b 有机地结合在一起，进行w e b 挖掘是解决这些问题的一个有效的途径。 另一方面，随着i n t e r n e t 技术的发展，各种基于w e b 的网络应用业务也如 雨后春笋般地发展起来，如网上商店，网上银行，远程教育，远程医疗和电子 政务等。尤其是方便、快捷、高效的电子商务正在悄悄的改变企业和商家们传 统的商务活动。从1 9 9 8 年至2 0 0 1 年，电子商务的发展速度超过3 0 。据美国商 务部统计显示，美国人2 0 0 3 年在网上购物消费的金额超过了5 0 0 亿美元，比上 一年增长2 6 3 。2 0 0 3 年，美国电子商务占总零售消费会额3 5 万亿美元的1 6 ， 而上一年为1 3 。在中国互联网实验室2 0 0 4 年第一季度的电子商务报告中指 出：2 0 0 4 年第一季度上海电子商务交易额完成5 0 4 4 亿元。2 0 0 4 年，上海信息 化建设的目标之一是新增一万个网上就业岗位。 从以上的统计数据，我们不难看出w w w 正在以前所未有的方式改变我们 的生活，同时也带给我们新的机遇。但是，对于每个从事电子商务的机构来说 挑战和机遇并存。为了能够给用户提供更优质的服务，为了能够给商业网站赚 取更多的利益，从事电子商务的机构和团体比传统的企业要做更复杂，更繁重 和更创新的工作。对于这些机构来说，首先要根据访问者的访问兴趣、访问频 率和访问时问等来发掘访问的浏览模式，进而调整网站的页面组织结构或推荐 给访问者感兴趣的内容，最终实现个性化的服务来满足访问者的需要。解决这 些需求的有效“武器”就是进行w e b 挖掘即将数据挖掘的思想、方法和技术应 用于w e b 上，进行w e b 挖掘。因为数据挖掘的强大功能就在于能够发现隐藏在 大量数据或事实之后的知识。 随着w e b 挖掘技术的不断成熟和应用范围的不断扩大，它将成为在w w w 上获取有用的信息和知识的重要手段和必然选择。 1 3 w e b 挖掘产生的概况 由于w w w 上可用信息资源的爆炸性增长，越来越有必要给用户提供某 种工具来帮助用户定位、分析和评价所需的信息。另一方面，随着电子商务等 网上交易的成功启用，商业机构也有必要追踪和分析用户的访问模式，以利于 更好地、更有针对性地进行一些宣传和促销活动。将数据挖掘和w w w 这两 个领域结合起来，就形成了当前的一个热门研究课题w e b 挖掘。广泛的说， 它是指从w o r l dw i d ew e b 上发现和分析出有用的信息。与数据挖掘一样，w e b 挖掘同样也是一门涉及多个学科领域的交叉性研究领域，它涉及了诸如w e b 技 术、信息检索、机器学习、自然语言理解和统计学等领域。前面两节着重介绍 了数据挖掘的概况和w e b 挖掘产生的背景，本节将讲述w e b 挖掘的概念和分 类。首先，我们有必要了解w e b 挖掘研究的对象。 1 3 1w e b 挖掘的研究对象 w e b 挖掘的研究对象是与w e b 有关的一切数据。这些w e b 数据包括w e b 页 面包含的数据和与w e b 活动有关的数据，w e b 数据的具体分类如下【4 】： w e b 页面包含的内容； w e b 页面内部的结构，包括h t m l 、x m l 代码： w e b 页面结构数据，即w e b 页面之间实际的联接结构； 描述用户如何访问w e b 页面的使用记录数据； 4 用户信息( 包括用户的注册信息和统计信息) 。 1 3 2 w e b 挖掘的定义 目前，w e b 挖掘的研究范围十分广泛，这主要归因于不同的研究团体和 人员有着不同的研究兴趣以及w e b 上的信息资源的爆炸性增长。当研究人员 在探讨w e b 挖掘的确切定义和比较相互之间的研究成果时，这种现象会给人 们带来一些困惑。在此，本文列出几个比较公认的w e b 挖掘定义： o e t z i o n i 是第一个提出w e b 挖掘术语的人。他指出w e b 挖掘是运用数 据挖掘技术从w e b 文档和服务中自动地发现和抽取信息口】。 w e b 挖掘可以宽泛地定义为从w o r l dw i d ew e b 中发现和分析有用的信 息6 1 。 w e b 挖掘是指从与w w w 相关的资源和行为中抽取感兴趣的、有用的 模式和隐含信息【”。 由上述关于w e b 挖掘的定义可以看出，w e b 挖掘是从w e b 数据中发现潜 在的有用信息和先前不知道的知识的整个过程。从这个意义上说，w e b 挖掘完 全包含了k d d 的标准过程【8 j ，而不同与数据挖掘是k d d 的一个阶段。 1 3 3 w e b 挖掘的分类 按照研究的w e b 数据对象，w e b 挖掘可以分为三类：w e b 内容挖掘( w e b c o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r e m i n i n g ) 和w e b 使用挖掘( w e b u s a g em i n i n g ) 1 7 ，9 ，10 1 ，如图1 2 所示。 ( 1 ) w e b 内容挖掘是从w e b 文档内容或其描述中抽取知识的过程【 。w e b 文档包含了不同种类的数据类型，例如：文本、图片、声音、视频、元数据( 是 指关于数据的数据，用以描述数据的属性1 和超链等。对于各种不同类型数据 的挖掘通常称之为多媒体数据挖掘】。从这个方面来说，w e b 内容挖掘是一 种多媒体数据挖掘。另外，w e b 内容数据是由非结构化数据( 例如：自由文本) 、 半结构化数据( 例如：h t m l 文档) 和结构化数据( 例如：由h t m l 页面生成数 据表) 构成。将数据挖掘的技术应用于非结构化数据的研究又称之为文本挖掘 d 2 1 。由此，我们可以看出w e b 内容挖掘的研究范围非常广泛。 w e b 内容挖掘的研究方法可以分为两类：基于智能体的方法( a g e n t b a s e d a p p r o a c h ) 秉i 数据库方法( d a t a b a s ea p p r o a c h ) 6 1 。基于智能体的方法是运用软件 系统( 或智能体) 执行w e b 内容挖掘的任务，例如：当前绝大多数搜索引擎都是 用这种方法。通常，基于智能体的w e b 挖掘系统分为以下三类： 图1 2w e b 挖掘的分类 智能化的搜索智能体( i n t e l l i g e n ts e a r c h a g e n t s ) 。这一类智能体通常是 使用领域特点和用户信息来组织和解释所发现的信息，例如 h a r v e s t 1 3 1 、f a q f i n d e r 1 4 1 和i n f o r m a t i o nm a n i d o l d 15 1 等； 信息过滤分类( i n f o r m a t i o nf i l t e r i n g c a t e g o r i z a t i o n ) 。这种信息过滤的 挖掘系统主要利用信息搜索技术、内嵌在联接结构中的语义信息等方 法来自动的检索、过滤和分类超文本w e b 文档，例如h y p u r s u i t u 6 和 b o o k m a r ko r g a n i z e r t l7 】： 个性化w e b 智能体( p e r s o n l i z e dw e ba g e n t s ) 。这类智能体根据用户的 喜好习惯来发现有用的w e b 信息资源，例如w e b w a t c h e r 【1 8 1 、 s y s k i l l & w e b e r t 1 9 】等。 另外一种适用于w e b 内容挖掘的数据库方法是运用适当的技术把半结构 化的w e b 数据组织成更加结构化的数据集合，并且使用标准的数据库查询机 制和数据挖掘技术来分析这些数据集。典型的数据库方法有多层次数据库 ( m u l t i p l el a y e r e dd a t a b a s e s ，m l d b ) 口o 23 】和w e b 查询系统( w e bq u e r ys y s t e m s l 。 多层次数据库方法的主要思想：数据库的最低层次包含的是存储在w e b 上的非结构化或半结构化数据( 如超文本文档) 。数据库中较高层次存储的数据 是从较低层次通过泛化或转换得到的更加结构化的数据集( 如关系型或面向对 象数据库) 。例如，a r a n e u s 系统1 2 1 1 就是通过从超文本文档中抽取相关信息， 然后借助于数据库中的泛化技术将这些有用信息整合成一种更高层次的，被称 为导出化的w e b 超文本( d e r i v e dw e bh y p e r t e x t ) 的数据集合。一个m l d b 有三 个主要部分构成： s ，h ，d ，各部分定义如下： s ：一个数据库模式，它包含了关于分层数据结构的元信息： h ：概念层次的集合； d ：m l d b 各层中数据库关系的集合。 数据库模式( s ) 描述了m d l b 的全局结构，存储了包括结构、数据类型、 取值范围等在内的通用信息。此外，它还描述了从低层关系得到高层关系的路 径图，以及所采用的归纳方法。概念层次集合( h ) 是预先定义的，可以协助系 统向高层概括底层信息，以及将查询映射到相应的层次。m l d b 各层中数据库 关系的集合( d ) 不仅包括原始的全局信息库，而且包括经过概括归纳的各层次 的数据库关系。 许多基于w e b 的查询系统和查询语言都是利用标准的数据库查询语言( 如 s q l ) ，根据w e b 文档的结构信息来执行查询操作，有些甚至运用自然语言理 解过程来完成w w w 上的查询请求。在【2 3 中，o r z a i a n e 和j h a n 提出一种 w e b 数据挖掘查询语。a ( w e b m l ) 。作为数据挖掘查询语言( d a t am i n i n gq u e r y l a n g u a g e ，d m q l ) 的一种延伸，w e b m l 采用的是类似s q l 语法的查询语言在 多层次数据库上对w e b 资源查询和w e b 知识挖掘。因为在多层次数据库中概 念是按层次综合的，查询条件不一定与当前抽象层次一致，可能更抽象或更特 例化，因此引入了四个的操作符( 如表l 一1 所示) 。这些操作符可以完成对不同 层次概念的互操作。 表1 - 1w e b m l 的操作符 w e b m l 原语操作符操作功能 c o v e r s覆盖 c o v e r e d - b yc包含 il i k e 同义词 l c l o s e t o 近似 ( 2 ) w e b 结构挖掘是从w w w 的组织结构和链接关系中推导知识的过程 川。它试图发现w e b 链接结构中潜在的模型，而这种模型是建立在超链拓扑结 构基础上的。同时，挖掘出的模型能够被用于w e b 页面分类，并且有助于生 成一些有用的信息( 例如w e b 站点之间的相似性和关系信息) 。值得一提的是， w e b 结构挖掘能够用于发现某个主题的权威网站和关于此主题的所有网站的 概貌。这方面工作的代表有p a g e r a n k l 24 1 、h i t s l 2 5 1 和c l e v e r l 2 6 1 。 p a g e r a n k 技术不仅提高了搜索引擎的有效性而且改善了它们的效率。 p a g e r a n k 被用于衡量某个页面的重要性，并且根据传统搜索引擎搜索返回的 页面的重要性来进行排序。这种方法有效性的一个撮好例证就是g o o g l e 的成 功。一个页面的p a g e r a n k 值是通过根据此页面的导入链接f b a c k l i n k ) 数目计算 得来的。导入链接是指指向此页面的链接，而不是由此页面发出的链接。 p a g e r a n k 方法并不是简单的计算导入链接的数目，而是根据来自不同重要性 页面的导入链接赋予不同的权值( w e i g h t i n g ) ，即来自越重要页面的导入链接的 权值越大。p a g e r a n k 的基本思想是：一个页面被多次引用，则这个页面很可 能是重要的；一个页面尽管没有被多次引用，但是被一个重要页面引用，则这 个页面也可能是重要的；一个页面的重要性被均分并被传递到它所引用的页 面。例如：给定某个页面p ，b 。表示页面p 的导入链接集合，f p 表示页面p 发出的链接集合，则页面p 的p a g e r a n k 可定义为： p r ( p 、：cy 型 q 一e b pn q 这罩n q = i f q i 。常数c ( o c 1 ) 用于标准化。一个页面的p a g e r a n k 被分配到 它指向的所有页面中，对所有指向它的导入链接所带来的p a g e r a n k 进行求和， 以得到它的新的p a g e r a n k 。该公式是一个递归公式，在计算时可以从任何一 个页面开始反复计算，直到其收敛。 对于搜索引擎的搜索结果来说，p a g e r a n k 是一个很好的评价结果的方法， 查询的结果可以按照p a g e r a n k 从大到小依次排列输出。c l e v e r 方法本质上和 p a g e r a n k 是一致的。 ( 3 ) w e b 使用挖掘是从w e b 使用数据或w e b 日志中抽取“感兴趣”的模 式的过程i ”。w e b 内容挖掘和结构挖掘使用的是w w w 上的主要数据，而w e b 使用挖掘的研究对象是来自用户与w e b 相互联系产生的数据。它包括w e b 服 务器访问日志、代理服务器r 志、浏览器同志、用户信息、注册数掘、用户会 话或事务数据等用户与w e b 两者之问联系产生的其他数据。w e b 使用挖掘的 步骤简单地说可以分为三步：数据预处理( d a t ap r e p r o c e s s i n g ) 、模式发现 ( p a t t e r nd i s c o v e r y ) 和模式分析( p a t t e r na n a l y s i s ) 。在下一章中，将详细讲述有 关w e b 使用挖掘的过程和各项技术。 在实际应用中，上述三种w e b 挖掘任务不是孤立的，而是相辅相成的。 尤其是w e b 内容挖掘和结构挖掘之问关系更为紧密，因为w e b 文档中也包含 有链接。有的时候，w e b 内容和使用挖掘相结合能够更好的完成某个应用任务。 例如：在【2 2 1 中，j o a c h i m s e ta 1 将w e b 内容和使用纪录相结合建立了一个软件 浏览智能体。这个智能体能够帮助用户更好地浏览网站。综上所述，w e b 挖掘 的这三个研究分支在实际应用过程中并不是孤立的，而是相互交叉、相互渗透 和相互联系的。 1 4 论文组织 第一章绪论：介绍w e b 挖掘产生的背景和概况； 第二章w e b 使用挖掘：论述w e b 使用挖掘的发展概况、体系结构、相关 技术和应用范围： 第三章w e b 使用挖掘数据预处理：论述数据预处理的步骤，重点论述会 话构造技术： 第四章w e b 使用挖掘中用户频繁访问模式的发现：提出一种改进的发现 用户频繁访问模式的算法； 第血章w e b 使用挖掘实验系统：实现第三、四章提出的方法，并对实验 结果进行分析； 第六章结束语：论文总结，下一步的研究工作和w e b 使用挖掘发展的前 景。 1 5 本章小结 本章首先介绍数据库知识发现、数据挖掘的定义和研究领域，分析了数 据库知识发现和数据挖掘的关系和区别；然后介绍了w e b 挖掘产生的背景： 最后重点讲述了w e b 挖掘的概况，w e b 挖掘的定义，w e b 挖掘的分类。在介 绍w e b 挖掘分类时，详细讲述了w e b 内容挖掘、w e b 结构挖掘和w e b 使用挖 掘的发展状况。 9 第二章w e b 使用挖掘概况 除了w e b 内容和w e b 结构挖掘，w e b 挖掘的另一个重要研究方向是w e b 使用挖掘，它通过挖掘w e b 日志记录来发现用户访问w e b 页面的模式 2 7 2 8 2 9 。 通过分析和研究w e b 日志记录中的规律，可以识别电子商务的潜在客户，提 高对最终用户的网络信息服务的质量，并改进w e b 服务器系统的性能和结构。 本章将主要介绍w e b 使用挖掘的现状，w e b 使用挖掘的过程和相关的技术及 其应用范围等。 2 1 w e b 使用挖掘的现状 w e b 挖掘乖在成为高效的、智能的w e b 应用的前提条件之一，而与用户 的喜好和期望等紧密联系的w e b 使用模式构成了w e b 服务的基础。这些w e b 服务通常要能够达到个性化、对用户友好以及能不断优化等标准。目前，国内 外w e b 使用挖掘的研究不仅仅局限于对w e b 日志的挖掘，从更广泛的意义上 说是从多方面对用户使用w e b 的行为规律的分析和研究。 w e b 使用挖掘主要有两个研究发展方向：般化的w e b 使用模式分析3 0 r 3 1 3 4 1 和个性化的w e b 使用模式的分析【3 2 1 。 一般化的w e b 使用模式分析是从w e b 日志中挖掘用户的访问模式和预测 用户的访问趋势。这些挖掘出来的模式和规则对w e b 站点的改进包括【3 3 】： 使用户所关心的页面更加容易访问； 使用户所关心的超链接更加醒目； 链接相关的页面； 聚合相似的页面； 增加缓冲预取机制、改善服务器响应时间； 合理设置广告： 个性化的w e b 使用模式分析是挖掘某一类或某几类用户( 甚至某个用户) 访问网站的行为规律，这使得网站能够动态地为用户提供个性化的服务以极大 的满足用户的需求。所谓的个性化服务是指w e b 站点为适应某一类或某一个 特定的用户的需要而实时地调整数据的组织和显示。一种实现个性化服务的方 法是允许用户手工定制w e b 站点显示选项，系统将记住每个用户的定制，并 在该用户再次进入该网站时进行相应的调整。例如微软的m s n 站点 1 0 ( h t t p ：w w w m s n c o r n ) 允许用户只看用户自己选择的新闻栏目。 当前国内外许多大学和研究机构针对w e b 使用挖掘的两个发展方向，将 理论研究和实际应用结合起来开展了大量的研究工作并且开发出了许多具有 代表性的w e b 使用挖掘的实际原型系统。 2 1 1国外系统 n )w u m 系统i ”1 w u m ( w e b u t i l i z a t i o nm i n e r ) 是一个序列模式挖掘系统。它的主要目标是 分析访问网站的用户们的浏览行为。w u m 发现的模式不一定是由相邻的浏览 事件组成的，同时这些模式也要满足用户的某种兴趣度标准。用户的兴趣度标 准能够通过w u m 使用的挖掘语言m i n t 提供的谓词逻辑动态的表达。作为一 种挖掘语言，m i n t 是用户和系统之间的接口。w u m 是一个可用于同志预处 理、查询和可视化的集成环境。它主要包括两个模块：聚合服务( a g g r e g a t i o n s e r v i c e ) 和m i n t 处理器( m i n t - p r o c e s s o r ) 。聚合服务模块的功能是准备用于挖 掘的w e b 日志数据。它从用户访问网站的活动中抽取信息，并把同一用户的 连续活动分组成一个事务，然后将这些事务转化成序列。聚合服务模块最主要 的任务就是把各种序列合并成树结构，并且把聚集的统计信息保留在树结构 中。m i n t - 处理器模块是w u m 的核心部分，它的功能是根据专家的指示从聚 合服务模块产生的聚合数据中抽取有用的信息，发现各种不同的浏览模式。 r 2 1w e b w a t c h e r 3 7 , 3 8 , 3 9 1 系统 w e b w a t c h e r 是由美国卡奈基梅隆大学研制的一个w e b 浏览向导智能体 ( w e b t o u r g u i d e a g e n t ) 。一旦你告诉它要搜寻的信息范围，它将在你浏览w e b 时一直陪伴你，帮助你查看或搜寻那些它认为你感兴趣的w e b 页面和超链。 它的学习策略主要是根据用户感兴趣的内容和用户浏览历史中反馈的信息，逐 步地改进访问者的访问模式，从而动态地提供用户感兴趣的内容。 f 3 )w e b m i n e r 4 0 1 系统 w e b m i n e r 是基于图2 1 所示框架模型的w e b 挖掘系统。此系统的主要贡 献是： 提出了一种灵活的w e b 挖掘体系结构( 图2 1 ) ； 提出一种由多个w e br 志条目组成的用户事务模型； 运用聚类算法将w e b 日志条目划分成事务； 采用关联规则和时间序列发现算法进行模式发现。 圈2 1w e b m i n e r 的体系结构 ( 4 ) w e b l o g m i n e r 4 1 】系统 w e b l o g m i n e r 是用于挖掘w e br 志文件的知识发现工具。在w e b l o g m i n e r 系统中，知识发现总共分为四个步骤： 第一阶段：根据w e b 服务器同志文件构建数据库。在此阶段中，从w e b 日志数据中过滤掉不相关的信息，将剩下的有意义信息经过数据转换后构造成 一个关系型数据库。这个数据库将有利于下一阶段的信息抽取和数据总结； 第二阶段：多维w