（计算机系统结构专业论文）基于web日志挖掘的用户访问模式研究(1).pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重迭太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：乞磋签字日期：。加岁年岁月彳e t f 学位论文版权使用授权书 本学位论文作者完全了解重迭太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重庞太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：易循 签字日期：护f 年岁月即日 重庆大学硕士学位论文中文摘要 摘要 数据挖掘是数据库最活跃的领域之。由于其广泛的应用背景和现实意义， 数据挖掘技术的研究和应用都获得了突飞猛进的发展，在国内外的学术界和信息 产业界备受关注。 数据挖掘是从大量数据中发现人们感兴趣的、隐藏的、先前未知的知识。数 据挖掘技术主要研究结构化的数据挖掘，而w e b 数据的挖掘是应用于i n t e m e t 的 技术研究，是从半结构或无结构的w e b 页面中，抽取感兴趣的、潜在的模式。尽 管i n t e m e t 是个半结构化的系统，很难对它进行处理，但是w e b 服务器日志记录 具有良好的结构，非常有利于数据挖掘的进行。此外，w e b 臼志挖掘作为w e b 挖 掘的一个重要组成部分，具有独特的理论和实践意义。 本文系统地阐述了从数据挖掘、w e b 数据挖掘到w e b 日志挖掘整个过程，重 点讨论在w e b 日志的挖掘上。通过阅读文献对w e b 使用挖掘技术进行了分析和论 述，特别是对m a r k o v 模型预测方法进行了详细的讨论分析了其优缺点，通过对 已有的各种运用m a r k o v 模型进行w e b 浏览预测的方法的分析，我们发现这些预 测的方法单纯考虑浏览次数往往会得到多个概率相同的结果，预测精度不够高。 如果把时间因素加以考虑在内，在一定程度上就能解决这些问题。在此基础上本 文提出了一种带访问倾向权重的m a r k o v 模型预测方法，该方法的主要特点是： 在m a r k o v 模型中增加浏览时间参数，并利用值差分度量法对时间参数进行离散 化处理：引入访问倾向权重的概念，对转移概率计算方法加以改进：在此基础上 还引入新的预测算法。最后进行了模拟实验，说明该方法能获得较高的预测精度， 可以用于预测w e b 用户非常可能访问的页面。最后设计出一个w e b 用户访问模式 挖掘的原型系统。 关键词：w e b 使用挖掘，用户访问模式，m a r k o v 模型，访问倾向权重 重庆大学硕士学位论文 英文摘要 a b s t r a c t o n eo ft h em o s ti m p o r t a n tf i e l d si nd a t a b a s ei sd a t am i n i n g i nv i e wo fi t sw i d e a p p l i c a t i o na n dp r a c r i c a ls i g n i f i c a n c e ，t h et e c h n i q u ea n da p p l i c a t i o no fd a t am i n i n g d e v e l o p e dr a p i d l ya n da t t r a c t e dm u c hm o r ea t t e n t i n gb o t hi nf i e l d so fa c a d e m i cr e s e a r c h a n di n f o m l a t i o ni n d u s t r y d i s c o v e r i n gt h ei n t e r e s t e d , h i d d e na n du n k n o w nd a t af r o ml a r g ed a t as e t si st h e p u r p o s eo fd a t am i n i n g t h em a i nw o r ko fd a t am i n i n gi s t od e a lw i t ht h es t r u c t u r a l d a t a ，w h i l et h ew e bd a t am i n i n gi sb a s e do ni n t e m e tt og e tt h ei n t e r e s t i n ga n dp o t e n t i a l p a t t e mf r o mt h eh a l fs t r u t u a lo rn o ts t r u c t r a lw e bp a g e s d a t ai ni n t e m e ti sah a l f s t r u c t u r a ls y s t e m ，a n di ti sd i f f i c u l tt od i a lw i t ht h e m f o r t u n a t e l y , t h ew e bs e v e rl o gf i l e s h a v ean i c es t r u c t u r ea n di ti sv e r yc o n v e n i e n tf o rd a t am i n i n g f u r t h e r m o r e , w e bl o g m i n i n gi sab r a n c ho fw e bu s a g em i n i ga n dh a ss p e c i a lt h e o r ya n dp r a c t i c es i g n i f i c a n c e a sa ni m p o r t a n tp a r to f w e b m i n i n g i nt h i st h e s i s ，t h ep r e c e s so fd a t am i n i n g ，w e bd a t am i n i n ga n dw e bl o gm i n i n gw a s r e p o t e d ，f o c u s0 nt h ew e bl o gm i n i g ，t h em e t h o da n dt e c h n o l o g yo f w e bl o gm i n i n gw e r e d i s c u s s e di nt h i st h e s i s a n a l y s e da n de x p o u n d e dw e bl o gm i n i ge s p e c i a l l yd i s c u s s e d p r e d i c t i o nm e t h o do fm a r k o vm o d e l t h ee x s i s t i n gm e t h e d sh a v es o m ed i s a d v a n t a g e s s u c ha st h ep r e c i s i o ni sn o th i g ee n o u g h w ep r o m o t ean e wp r e d i c t i o nm e t h o dw h i c h a l s ou s em a r k o vm o d e lh a m e dp r e d i c t i o nm e t h o do fm a r k o vm o d e lw i t ha c c e s st r e n d w e i g h t w ed i s c o v e r e dt h a tt h o s ep r e d i c t i o nm e t h o d sj u s t c o n s i d e rt h ec o u n t so f b r o w s i n gp a g e , r e s u l t i n gi ns e v e r a lr e s u l t s ，w ec a ns a yt h a t t h ep r e c i s i o ni sn o th i 【g h e n o u g h i ft h et i m eo fb r o w s i n gp a g ei st a k e ni nc o n s i d e r a t i o n ，t h ep r o b l e mc a nb e r e s o l v e dt os o m ee x t e n d t h en e wp r e d i c t i o nm e t h o dh a st h ef o l l o w i n gf e a t u r e s ：t h e p a r a m e t e ro fb r o w e i n gt i m ei sp u ti nm a r k o vm o d e l ，a n dt h e yw e r ed i s c r e t e db yu s i n g v a l u ed i f f e r e n c em e t r i cm e t h o d , p r o p o s e dan e wd e f i n i t i o na c c e e s st r e n dw e i g h t ，a n d u s ei tt op r o m o t et h ec a c u l a t i n gm e t h o do ft r a n s a i t i o nm a t r i x ，an e wp r e d i c t i o na l g o r i t h m i sa l s ob e e np r o p o s e d ，t h e nt h em o t h o di sr e s l i z e db ye x p e r i m e n t ，i th a sb e e np r o v e dt h a t p r e d i c t i o nm e t h o do fm a r k o vm o d e lw i t ha c c e s s 仃e n dw e t 【g h th a sh i g h e rp r e d i c t i o n p r e c i s i o nt h a nt h ep r e v i o u so n e a tl a s t , w ec o m eu pw i t hal o g i cf r a m eo f aw e ba c c e s s m o d e l m i n i n gs y s t e m 儿 重庆大学硕士学位论文英文摘要 k e y w o r d s ：w e bu s a g em i n i n g ，u s e ra c c e s sp a t t e r n ，m a r k o vm o d e l ，a c c e s st r e n d w e i g h t n i 重庆大学硕士学位论文 1 绪论 1绪论 1 1 研究背景与意义 w w w ( w o r l dw i d ew e b ) 自从1 9 9 1 年诞生以来，已经发展成为拥有亿万用户和 上万站点的巨大分布式信息空间。随着i n t e r n e t i n t r a n e t 技术的广泛应用，使得w e b 上的信息无比丰富，但是如何在如此复杂数据类型的数据中找到需要的知识，就 提出了一个新的挑战。目前的许多数据库应用系统对数据库中的数据进行管理和 事务处理，而通过对这些数据进行分析得到进一步隐含知识的能力相对不足，因 此需要对数据进行较高层次的处理，从中找到隐含的规德和模式，来帮助用户更 好的利用数据进行决策和研究。数据挖掘就是在这样的背景下出现的，它结合了 数据库技术、人工智能、统计学和模式识别技术，利用数据库管理系统来存储数 据，用机器学习的方法来分析数据，挖掘历史数据背后的知识。利用数据挖掘技 术为解决w e b 上的知识发现带来了一线曙光。而通过数据挖掘在w e b 上的应用，即 w e b 挖掘技术，主要包含了w e b 的内容挖掘、结构挖掘和使用挖掘。他们分别挖掘 w c b 站点文件内容、结构以及站点使用信息。目前国际上对w e b 使用挖掘的研究比 较多，w e b 挖掘的国际权威会议w e b k d d 也把使用挖掘作为重点。 美国明尼苏达大学的w e b 使用挖掘专家b a m s h a dm o b a s h e r 着h r o b e r tc o o l y 将 w e b 使用挖掘定义为数据挖掘技术应用在大型w e b 资源中以分析w e b 站点的使用。 w e b 使用记录挖掘通过挖掘w e b 浏览记录来发现有意义的信息。例如有多少人访问 了该页面，他们从哪里来，那些页面最受欢迎等。它可广泛地应用于个性化服务、 系统改进、站点修改、商业智能和浏览推荐等方面。当前经济模式变化，己从传 统实体的商店转移至l j l m e m e t 上的电子交易，同时也改变了销售商和顾客的关系。 通过w e b 使用挖掘可以了解到顾客尽可能多的爱好和价值取向，以保证在电子商务 时代的竞争力。综合而言，w e b 使用挖掘具有以下几个方面的益处： 1 1 为用户提供个性化的服务 根据用户的访问历史，动态地向用户推荐商品。正如a n l a z o r l c o r n 所做的，在 电子商务网站上进行个性化营销，具有很大的商业价值。 2 1 提高系统效率 随着w w w 的通信量的增加，影响网站用户满意度的主要原因除t w e b 站点的 内容外，其服务效率也很重要。通过w e b 使用挖掘，可以提供网站服务效率全方位 的信息。从而有助于找到平衡服务器负荷，优化传输，减少拥塞的方法，缩短用 户等待时间，提高系统效率和服务质量。 3 ) 提高网站结构设计 重庆大学硕士学位论文 1 绪论 w e b 结构的复杂度在飞速的发展着。因此，w e b 站点和w e b 服务器的设计和维 护难度也在增加着，通过w e b 使用挖掘提供的用户使用信息，可以帮助网站设计者 确定如何修改网站结构。 4 ) 商务网站的顾客群类确定 分析市场销售数据以识别顾客的群类，帮助确定电子商务产品在w e b 页面上的 布局摆放，向用户有效的推荐产品，以达到扩大产品销售量的目的。同时，有助 于找到顾客访问网站的生命周期，制定相应的营销策略。 5 ) 网络安全 分析网上银行、网上商品交易用户日志，可以防范黑客攻击、恶意诈骗。 6 1 网站评估 w e b 使用挖掘可以获取用户对网站使用情况的第一手资料，为网站评估提供依 据。 从以上可以看出，w e b 使用挖掘的研究具有重要的意义。但是w e b 使用挖掘是 一个新鲜事物，在1 9 9 6 年才陆陆续续地有一些挖掘方法被提出，目前还很不系统、 成熟和完善。现在虽然己有一些商用的w e b 使用挖掘工具，但一般只包含一些经常 使用的统计报告：点击数和传输字节数的汇总报告、排名靠前的被请求的 u r l ( u n i f o r m r e s o u r c e l o c a t o r l 、引用者以及最常用的浏览器列表、每个互联网域 的点击次数、出错报告、目录树报告等。而且这些工具的速度、性能、兼容性和 分析的深度都有一定的局限性。本文系统地研究了w c b 数据挖掘技术，并在一些具 体挖掘方法上提出了一些新概念和新算法。并对其具体的应用进行了研究。 1 2 国内外有关用户模式发现的现状 目前，国内外有关用户模式挖掘的研究已经很多，主要集中在对用户浏览路 径的挖掘【7 t 8 9 , 1 0 i 。文献 7 1 5 b 提出了一个基于代理的s y s k i l l & w e b e r t 软件，该软件通过 分析用户用户访问日志预测哪些页面是用户感兴趣的页面。 1 2 1 用户访问模式的发现方法 目前国内外对用户访问模式的研究主要还是将数据挖掘技术应用于w e b 数据 中，或者是将w e b 数据经过一定的转换保存在数据库或数据仓库中，再直接利用数 据挖掘技术产生用户访问模式。主要的方法有以下几种： 统计分析 统计技术是最常用的获取用户访问模式的方法，可以通过统计计算得到访问 频率最高的网页、网页的平均浏览时间以及访问路径的平均长度等统计信息。虽 然这些统计信息不是很深刻的分析，但是在实际应用中可以很好地改善系统性能， 增强系统安全性，为网站拓扑结构的改造提供依据以及为电子商务的销售决策提 重庆大学硕士学位论文 1 绪论 供支持等。 关联规则 在w e b 挖掘领域中，关联规则指的是满足给定置信度的网页关系，这些网页往 往被同时浏览，即使它们之间并没有超链接存在。这些关联规则可以帮助网站设 计者改造网站的拓扑结构或是作为通过“提前取页”技术来减少网页的切换延迟 的启发依据。 聚类【1 2 i 聚类是指把具有相似性质的事物分在一组。在w e b 挖掘领域中，主要是对网站 的用户进行访问模式的聚类和对网页进行内容聚类。网站用户访问模式的聚类知 识可以应用于个性化网站中，为不同类别的用户动态生成针对该类用户个性的网 页。网页内容的聚类则多被用于搜索引擎的实现。 分类 分类是把一个事物按照预先定义好的分类方法分组。通过对网站现有用户进 行聚类所得到的类别特征的抽取与选择，可以得到用以判断新用户所属类别的分 类依据。 序列模式 序列模式的挖掘致力于发现用户与网站的会话内所浏览的网页之间在时间顺 序上的关联关系。利用已经发现的频繁序列模式可以预测用户未来的访问情况， 从而指导针对某一类用户的广告的安置。 2 2 现有用户模式挖掘系统的分类 从1 9 9 6 年以来己出现了许多针对不同目标的分析w e b 用户模式的研究项目 和商业软件以下作一个简单的分类。分类的标准很多，本文中采用了其中主要的 五种1 ：1 ) 获取输入的数据来源( 服务器代理服务器客产机) ；2 ) 输入数据的 类型( 结构，内容使用数据用户注册信息) ；3 ) 各数据集中包含的用户个数( 单 个多个) ；4 ) 各数据集中包含的网站个数( 单个多个) ；5 ) 该项目产品所针对 的应用领域类型( 通用型个性化服务型n 站修改型特性描述型和系统改进型) 。 具体的分类结果如图】1 所示。 重庆大学硕士学位论文 l 绪论 图1 1用户访问模式挖掘系统的分类 f i 9 1 1 t h ec l a s s i f i c a t i o no f u s a g em i n i n g 1 3 论文的工作和组织结构 随着i n t e r n e t 技术的发展，网络服务和电子商务蕴藏着巨大的商机。根据客 户的访问模式对客户进行分类，发现和吸引潜在客户；为客户提供个性化的定制 服务；动态合成符合用户兴趣的网页，改进w e b 空问的组织结构等等。本课题正 是基于这样的研究背景提出的。论文比较系统、完整地分析和论述了数据挖掘技 术以及w e b 挖掘技术。着重研究了w e b 使用模式挖掘过程中各环节的关键技术， 从数据准备到模式发现再到模式分析。针对传统m a r k o v 模型预测方法欠缺浏览 时间考虑的缺陷，认为其是导致预测不够准确的因素，于是本文提出了一种带访 问倾向权重的m a r k o v 模型预测方法来进行模式发现，最后进行了模拟实验，说 明该方法能获得较高的预测精度，可以用于预测w e b 用户非常可能访问的页面。 最后设计出一个w e b 用户访问模式挖掘的原型系统。全文组织如下： 第一章绪论：简要介绍了本论文的课题背景、研究现状、研究意义，以及论 文的主要工作。 第二章w e b 挖掘：在评述了数据挖掘的基础上，进一步地讨论了w e b 挖掘 的定义、难点以及应用。 第三章w e b 使用挖掘：指出t w e b 使用模式挖掘的困难，分析了相应的解决方 法，给出挖掘的过程和方法。 第四章m a r k o v 模型预测方法：阐述了利用m a r k o v 模型进行预测用户在w e b 站点上的访问模式的方法。 第五章带访问倾向权重的m a r k o v 模型预测方法：提出一种在构造预测模型 4 重庆大学硕士学位论文1 绪论 和利用模型进行预测时加入浏览时间考虑的新的预测方法。 第六章w e b 使用模式挖掘系统：提出了一种通用的w e b 使用模式挖掘的原型系 统，阐述了设计思想并说明了各模块的工作原理。 第七章总结：对论文的工作进行总结并提出进一步研究的方向。 1 4 本章小结 本章介绍了论文的选题背景，论述了论文选题的学术意义，介绍了国内外对 w e b 用户访问模式挖掘的研究现状以及论文的研究内容，最后阐述了本论文的主要 内容和各章节的内容安排。 重庆大学硕士学位论文2w e b 挖掘技术 2w e b 挖掘技术 2 1 数据挖掘概述 2 1 1 什么是数据挖掘 数据挖掘就是通过分析已经存在数据库中的数据解决问题。数据挖掘被定义 为发现数据模式的过程。这个过程必须是自动化的或者( 通常) 是半自动化的。 被挖掘出来的规则应该意味着某些方面的优势，特别是经济方面的优势。 另一种比较公认的定义是w j f r a w l e y ，g p i a t e t s k y ，s h a p i r o 等人提出的：数据 挖掘就是从大型数据库中的数据中提取人们感兴趣的知识。这些知识是隐含的、 事先未知的、潜在有用的信息，提取的知识表示为概念( c o n c e p t s ) 、规则( r u l e ) 、 规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。这种定义把数据挖掘的对象定义 为数据库，更广义的说法是：数据挖掘意味着在一些事实或观察数据的集合中寻 找模式的决策支持过程。数据挖掘的对象不仅仅是数据库，也可以是文件系统， 或其他任何组织在一起的数据集合，例如：w w w 信息资源，最新的对象是数据仓 库。 2 1 2 数据挖掘使用的各种方法 很多技术都可以用于数据挖掘。机器学习、模式识别、人工智能等领域的技 术、方法经过改进，大都可以应用于数据挖掘。常用的方法有决策树、粗糙集、 神经网络、遗传算法、概念树等。 决策树方法 利用信息论中的信息增益寻找数据库中具有最大信息量的字段，建立决策树 的一个结点，再根据字段的不同取值建立树的分支；在每个分支子集中重复建树 的下层结点和分支的过程，即可建立决策树。国际上最有影响和最早的决策树是 q u i u l a n 研制的i d 3 方法，数据库越大，这种方法运行的效果越好。在i d 3 方法的基 础上，又产生了许多决策树方法。 神经网络方法 它模拟人脑神经元的结构，以m p 模型和h e b b 规则为基础，建立了三大类多种 神经网络模型。 1 ) 前馈式网络，它以感知机、反向传播模型、函数网络为代表，可用于预测、 模式识别等方面。 2 ) 反馈式网络，它以h o p f i e l d 的离散模型和连续模型为代表，分别用于联想和 优化计算。 6 重庆大学硕士学位论文2w e b 挖掘技术 3 ) 自组织网络，它以a r t 模型、k o h o l o n 模型为代表，用于聚类。 神经网络的知识体现在网络连接的权值上，是一个分布式矩阵结构：神经网 络的学习体现在神经网络权值的逐步计算上( 包括反复迭代或累加计算) 。运用 神经网络的方法产生许多分类器。 覆盖正例排斥反例方法 它是利用覆盖所有的正例、排斥所有的反例的思想来寻找规则。比较典型的 有m i c h a l s k i 的a q i i 方法。a q l l 的主要思想是，在正例集中任选一个种子，到反例 集中逐个比较，对字段取值构成的选择子相容则舍去，相斥则保留。按此思想循 环所有的正例种子将得到正例集的规则( 选择子的合取式) 。 粗糙集( r o u g hs e t s ) 方法 在数据库中，将每个元组看成一个对象，列元素看成属性( 分为条件属性和 决策属性) 等价关系r 定义为不同对象在某个( 或几个) 属性上取值相同，这些满 足等价关系的对象组成的集合称为该等价关系r 的等价类。条件属性上的等价类e 与决策属性上的等价类y 之间有三种情况：1 、下近似：y 包含e ；2 、上近似：y 和 e 的交非空；3 、无关：y 和e 的交为空。对下近似建立确定性规则，对以上近似建 立不确定性规则( 含可信度) ，对无关的情况则不存在规则。 概念树方法 对数据库记录的属性字段按归类方式进行抽象，建立起来的层次结构称为概 念树。如：“城市”概念树的最下层是具体市名或县名( 如：南京、合肥等) ， 它的直接上层是省名( 如江苏、安微等) ，省名的直接上层是国家行政区( 如： 华东、华北等) ，再上层是国名( 如：中国、美国等) ，利用概念树提升的方法 可以大大地浓缩数据库中的记录。对多个属性字段的概念树进行提升，将得到高 度概括的知识基表，然后再将知识基表转换为规则。 遗传算法 这是模拟生物进化过程的算法，有三个算子组成： 1 ) 繁殖( 选择) 是从一个旧种群( 父代) 选出生命力强的个体，产生新种群 ( 后代) 的过程。 2 ) 交叉( 重组) 选择两个不同个体( 染色体) 的部分( 基因) 进行交换，形 成新个体。 3 ) 变异( 突变) 对某些个体的某些基因进行变异( i 变o 、0 变1 ) 。 这种遗传算法可起到产生优良后代的作用。这些后代需满足适应值，经过若 干代的遗传，将得到满足要求的后代( 问题的解) 。遗传算法己在优化计算和分 类机器学习方法方面发挥了显著的作用。 公式发现 重庆大学硕士学位论文 2 w e b 挖掘技术 在工程和科学数据库( 由试验数据组成) 中，对若干数据项( 变量) 进行一 定的数学运算，求得相应数学公式。比较典型的b a c o n 发现系统完成了对物理学 中大量定律的重新发现。其基本思想是，对数据项进行初等数学运算( 加、减、 乘、除等) ，形成组合数据项，若它的值为常数项，就得到了组合数据项等于常 数的公式。 统计分析方法 在数据库字段项之间存在两种关系；l 、函数关系( 能用函数公式表示的确定 性关系) ：2 、相关关系( 不能用函数公式表示，但仍是相关确定关系) 。对它们 的分析采用如下方法：回归分析、相关分析、主成分分析，从中可以发现有用的 关联规则。 模糊论方法 利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模 糊聚类分析。模糊性是客观存在的。系统的复杂性越高，精确化能力就越低，即 模糊性越强。这是z a d e h 总结出的互克性原理。 可视化技术 可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖析更清晰。 例如，把数据库中的多维数据变成多种图形，这对揭示数据的内涵、内在本质及 规律起了很大的作用。 2 1 3 数据挖掘的过程 数据挖掘一般由3 个主要的阶段组成：数据准备、模式发现( 建模) 、模型评 估及模型应用。 数据准备阶段：这个阶段又可分成3 个子步骤，数据集成、数据选择、数据预 处理。数据集成将多文件或数据库运行环境中的数据进行合并处理，解决语义模 糊性、处理数据中的遗漏和清洗脏数据等。数据选择的目的是辨别出需要分析的 数据集合，缩小处理范围，提高数据挖掘的质量。颈处理是为了克服目前数据挖 掘工具的局限性。 建模：包括挖掘算法的选择和算法参数的确定等。 模型评估：进行模型的训练和测试，对得出的模型进行评价。前三个阶段是 循环往复的过程，直到得到用户满意的模型为止。 模型应用：得到满意的模型后，就可以运用此模型对新数据进行解释。 2 1 4 数据挖掘的分类 目前对数据挖掘的研究活跃而杂乱。每年有大量的研究文献涌现，针对数据 挖掘的处理过程、功能模型、算法研究、应用等不同层面。本节尝试从数据挖掘 的功能模型和挖掘对象两个方面进行分类。 重庆大学硕士学位论文2w e b 挖掘技术 按照功能模型分类 数据挖掘的任务是从数据中发现模式。模式是一个用语言l 来表示的个表达 式e ，它町用来描述数据集f 中数据的特性，e 所描述的数据是集合f 的一个子集f e 。 e 作为个模式要求它比例举数据子集f e 中所有元素的描述方法简单。例如，“如 果成绩在8 1 9 0 之间，则成绩优良”可称为一个模式，而“如果成绩为8 1 、8 2 、 8 3 、8 4 、8 5 、8 6 、8 7 、8 8 、8 9 或9 0 ，则成绩优良”就不能称之为一个模式。 模式有很多种，按功能可分有两大类：预测型( p r e d i c t i v e ) 模式和描述型 ( d e s c r i p t i v e ) 模式。预测型模式是可以根据数据项的值精确确定某种结果的模式。 挖掘预测型模式所使用的数据也都是可以明确知道结果的。例如，根据各种动物 的资料，可以建立这样的模式：凡是胎生的动物都是哺乳类动物。当有新的动物 资料时，就可以根据这个模式判别此动物是否是哺乳动物。 描述型模式是对数据中存在的规则做一种描述，或者根据数据的相似性把数 据分组。描述型模式不能直接用于预测。例如，在地球上，7 0 的表面被水覆盖， 3 0 是土地。 在实际应用中，往往根据模式的实际作用细分为以下6 种： 1 1 分类模型( c l a s s i f i c a t i o nm o d e l ) 用于提取能代表群体的特征属性。在数据 挖掘中，分类模型通过对已知类别的个体进行归纳，找出各类的特征属性，即分 类模式。在有些情况下，领域专家先对个体进行分类，再通过分类模型提取分类 模式。 2 1 回归模型( r e g r e s s i o nm o d e l ) 用属性的历史数据预测未来趋势。在最简单 的情况下，可以用标准统计方法，如线性回归等。但现实中往往非线性问题居多， 如股票价格的涨跌、机械系统故障的发生等，由于受许多因素的影响，问题变得 非常复杂。回归模型的任务就是找出对这些变化的准确描述。有些技术既可以用 于分类，又可以用于回归，如：c a r t ( c l a s s i f i e d o na n d r e g r e s s i o n ) 。 3 1 时间序列模型( t i m es e r i e sm o d e l ) 用已有的数据序列预测未来。从这一点上 看，与回归模型根相似。但回归模型不强调数据问的先后顺序，而时间序列模型 要考虑时间特性，尤其要考虑时间周期的层次，如天、周、月、年等，有时还要 考虑日历的影响，如节假日等。这里要注意，时间序列模型和对时间序列数据的 挖掘是两个不同的概念。对时间序列数据的挖掘可以用到多种模型和方法。 4 1 聚类模型( c l u s t e r i n gm o d e l ) 是将一个群体分成多个类，使同类个体尽可能 相似而不同类间个体差异尽可能大。与分类模型不同的是，聚类模型从未知开始， 既不知道具体的分类标准，也不知道会有些什么类。按照给定的聚类参数( 如距 离等) 进行分解、合并。得到的结果由领域专家进行甄别，如果不满足目标，需 要改动聚类参数，重新聚类。一旦达到目标，分类规则也就通过聚类参数得到。 9 重庆大学硕士学位论文2w e b 挖掘技术 5 ) 关联模型( a s s o c i a t i o nm o d e l ) 用于发现事物间的关联规则，或称相关程度。 关联规则的一般形式是：如果a 发生，则b 有c 的可能发生，c 称为关联规则的支 持度( c o n f i d e n c e ) 。例如：如果i b m 的股票价格上升，有7 0 的可能微软的股票 要下降；买榔头的人有4 同时买钉子。 6 ) 序列模型( s e q u e n c em o d e l ) 与关联模型很相似，不同的是序列模型的对象 是按时域分布的，发现的规则与时问的先后顺序有关。例如关联模型发现的一条 规则可能是：如果机组发生油膜涡动。那么发生油膜振荡的可能是4 4 。而序列模 型发现的一条规则可能是：如果机组发生油膜涡动，那么3 0 分钟内发生油膜振荡 的可能是4 8 。 在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式是使用 最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督知识，因 为在建立模式前数据的结果是已知的，可以直接用来检测模式的准确性，模式的 产生是在受监督的情况下进行的。一般在建立这些模式时，使用部分数据作为 样本，用另一部分数据来检验、校正模式。聚类模式、关联模式、序列模式则是 非监督知识，因为在模式建立前数据的结果是未知的，模式的产生不受任何监督。 按照挖掘对象不同的数据类型分 数据挖掘可分为时间序列数据、空间数据、文本数据、多媒体数据等。 1 ) 时间序列数据( t e m p o r a l 或t i m es e r i e sd a t a ) 是与时间有关的一系列数据。 可以进一步分为时间相关数据和序列相关数据。时间相关数据与数据产生的绝对 时间有关，如股票价格、银行帐务、设备运行日志等；序列相关数据与数据产生 的绝对时间关系不大，而注重数据间的先后次序典型的序列相关数据是传感器 数据。对时间序列数据的挖掘主要是发现序列中事物出现的周期和规律，以及不 同时间序列间的同步关系。 2 1 空间数据( s p a t i a ld a t a ) 是与空间位置或地理信息有关的数据，如地理信息 系统g i s 的数据等。 3 ) 文本数据( t e x td a t a ) 就是一般的文字，如报刊杂志、设备维护手册、故障 描述等的内容。对文本数据的挖掘主要是发现某些文字出现的规律以及文字与语 义、语法间的联系当前一个十分活跃的研究领域是w e b 日志( w e bl o g ) 的挖掘， 目的是有效发现i n t e r n e t 用户访问站点的模式，从而提高服务的针对性。 4 1 多媒体数据( m u l t i m e d i a d a t a ) 是随着多媒体技术而日益涌现的声音、图形、 图像、超文本等数据。由于与传统的文本数据不同，因此必须采用新的挖掘手段 来发现内容和形式间的内在联系。 根据发现知识的种类分 数据挖掘是一个与应用相关的课题，不同的应用可能需要不同种的挖掘技术 重庆大学硕士学位论文 2w e b 挖掘技术 来处理。从数据库中发现的各种各样的知识主要可以分为如下几类： 1 ) 关联规则( a s s o c i a t i o nr u l e ) 从交易数据库中挖掘关联规则是近年来在数据挖掘领域研究的一种重要的方 向，引起了极大的关注。挖掘关联规则的任务是从与任务相关的数据集合中导出 一个强关联的公式( 具有高支持度和可信度的模式) ，如：a i a a 2 ，、 a m j b 1 a b 2 a a b m ，其中a i ( 1 i m ) 和b j ( 1 j n ) 是属性值集合，它们来自一个数据库中 相关的数据集合。例如，从交易数据库中一个集合中可以发现这样一个关联规则： 一个购买了某种商品的顾客，同时他也购买了另外一种商品，这种事件发生的可 能性很大。 2 ) 分类规则( c l a s s i f i c a t i o nr u l e ) 数据挖掘的另一个重要的研究方面是对大量的数据进行分类，就是从数据库 中挖掘出分类规则。数据分类是依据特定的标准来划分数据集。例如，根据客户 对汽车的偏好来对他们进行分类，这是汽车销售商所希望的，以致销售人员知道 新车型的产品介绍可以直接邮寄给哪一类顾客，可以获得最大的商业机会。 3 ) 特征规则( c h a r a c t e r i s t i cr u l e ) 大多数的数据挖掘系统都有一个特征提取器，它可以从与任务有关的数据集 合中归纳出一般化的关系，从中可以提取不同的特征规则或从不同的角度在多概 念层上观察数据。特别地，它可以推导出一组能概括与特定任务相关数据特征( 称 作目标类，t a r g e tc l a s s ) 的特征规则。例如，在医学数据库中，可以用一组特征 规则来表示一种疾病的特征。 2 2w e b 数据挖掘 2 2 1w e b 挖掘的定义 应用领域的需求是推动技术发展的源动力。i n t e m e t 的迅速发展使得w w w 上 的信息量飞快增长，怎样对这些数据进行复杂的应用成了现今数据库技术的研究 热点。因此，对强有力的w e b 数据分析处理工具提出了需求，而日趋成熟的数据挖 掘技术正好为w e b 挖掘提供了技术基础。w e b 挖掘是将数据挖掘技术应用于大规模 w e b 数据，以期发现有效的、新颖的、潜在有用的，以及最终可理解的模式规则的 过程。相对于w e b 数据而言，传统的数据库中的数据结构性很强，即其中的数据为 完全结构化的数据，而w e b 上的数据最大特点就是半结构化。所谓半结构化是相对 完全结构化的传统数据库的数据而言。显然，面向w 曲的数据挖掘要比面向单个数 据仓库的数据挖掘要复杂得多。下面我们首先对w e b 挖掘的基本概念进行简单介 绍。 w e b 挖掘的定义可以从数据挖掘的概念扩展而来。简单讲，w e b 挖掘指从w e b 重庆大学硕士学位论文2w e b 挖掘技术 服务器上的数据文件中提取人们感兴趣的知识。这里所谓的“兴趣”与前面讨论数据 挖掘时提到的含义相同。w e b 挖掘其实就是对文档的内容、可利用资源的使用以及 资源之间的关系进行分析。 2 2 2 w 曲挖掘的对象 w e b 数据挖掘对象包括曰志数据、电子商务数据、页面数据，以及其他一些数 据等。 i ) 服务器日志数据：个人浏览w e b 服务器时，服务器方将会产生几种类型的 文件：s e r v e rl o g s ，e r r o rl o g s 等，以记录用户的访问基本情况。其r 扣s e r v e rl o g s 记录 了用户的各种访问信息：e r r o rl o g s 为存取请求失败的数据，如：丢失连接，授权失 败，或超时。可以通过对这几种日志的分析和挖掘开展w e b 使用挖掘。 2 ) 市场数据：这种数据就是传统的关系数据库中存储的结构数据，用于存储 日常商务活动中的电子商务信息。 3 1w e b 页面数据：即满足h t m l 标准的w e b 页面。现有的w e b 数据挖掘方法很 多都是针对w e b 页面开展的。 4 ) 其他信息：这些信息主要包括用户注册、调查信息等一系列信息。为了更 好地实现挖掘任务，适当的附加信息( 如描述用户的基本情况和特征的信息) 是有必 要的。 2 2 3w e b 挖掘的难点 w e b 是一个巨大、分布广泛、全球性的信息服务中心，涉及经济、文化、教育、 新闻、广告、消费、娱乐、金融、保险、销售、电子商务等信息服务，内容极其 丰富。对w e b 进行有效的信息抽取和知识发现具有极大的挑战性，会面临很多具体 问题，主要有： 1 ) 目前，对感兴趣的信息仅限于利用各种搜索引擎进行查找。尽管业界开发 了很多的搜索引擎，但其检索性能和服务质量并不令人满意。主要表现在：检索 方式单一，检索时间长，检索结果质量差，难以精确表达用户需求，无法适应用 户群体的多样性；检索召回率和精度低。低查准率( 精度) 导致引擎返回的检索 结果中往往含有大量无关信息。有用信息匮乏，用户难以得到真正感兴趣或有用 的信息。低查全率( 召回率) 导致很多相关的文档查不到；搜索引擎的更新周期 较长，无法适应信息的快速增长：缺乏检索导航信息。用户无法顺利、快速地从巨 大的信息网络中找到目标信息：定制服务能力差。不能根据用户多样化的的需求， 自动地、最大程度地满足用户的需求；主动服务和个性化服务能力差。 2 ) w e b 页面以某种格式h t m l 或x m l 呈现的半结构化数据( s e m i s t r u c t u r e d d a t a ) ，其数据结构不规则或不完整，复杂程度远远高于普通的文本文档，其数据 结构隐含、模式信息量大、模式变化快。大量的文档无任何排列次序，无分类索 踅庆大学硕士学位论文 2w e b 挖掘技术 引。 3 ) w e b 是一个异质、分布、动态的信息源。w e b 及其数据的更新、增长速度 极快，也无固定的模式。w e b 上的信息几乎都是隐藏的、潜在的、未知的，从w e b 上发现这些未知的信息和有用的模式，仅用传统的基于关键字的检索方式很难实 现，现在的搜索引擎尚不具备这些功能。 4 ) 目前w e b 上的数据以t b 数量级计算，且在迅速地增长，能否或如何构建一 个庞大的数据仓库把w e b 上所有分布和异质的数据集成在一起。但这几乎是不可能 的。最近，有些研究工作在致力于存储和集成w e b 上的所有数据。 5 ) 不同的用户访问w e b 的兴趣、爱好和使用目的干差万别，面对一个非常广 泛的形形色色的用户群体，能否使用户根据自己的爱好兴趣定制网页，甚至w e b s e r v e r 能否根据发现的用户p r o f i l e 自动为用户定制网页，从而提供个性化的信息 检索和查询服务。 6 ) 网络上信息储备量极大且信息内容十分丰富，但信息的利用率很低。w e b 上的信息对用户个人而言，被使用到的只是极小的一部分，其余信息对用户来说 是不感兴趣的。 这些问题推动了如何有效且高效地发现和充分利用i n t e r n e t 上资源的研究工 作。万维网的分布、动态、海量、异质、变化、开放性的特点，网页内容的半结 构化特征决定t w e b 挖掘比传统的k d d 和以关键字搜索为主的信息检索问题更为复 杂和困难，很多问题甚至是n p - h a r dp h 题。解决w e b 挖掘问题需要有新的数据模型、 体系结构和算法等，在理论上、方法上要有新的突破，要求有更高级的w e b 信息处 理技术。 2 2 4w e b 挖掘的分类 我们可以将w e b 挖掘一般地定义为：从与w w w 相关的资源和行为中抽取感 兴趣的、有用的