（计算机软件与理论专业论文）web日志挖掘研究与挖掘工具lsminer的设计与实现.pdf

蹬捌大学硪+ 量学位论文 w e b 器志挖掘研究及挖掘工具 l s m i n e r 的设计与实现 计算机软件与理论 撼 究生曾特指导教师社中军 w e b 数据挖掘利用数据挖掘按术从网络文档和服务中发现和提取信息。 w e b 上各种形式的文档和糟户访闯信意虢梅戒了w e b 数据挖掘的对象。橡据 挖掘对象的不同我们将w e b 数据挖掘分为内容挖掘，结构挖掘和访问信息挖 掘3 大类，日志挖掘作为访问信息挖掘的一个重要姆成部分，有其独特的理 论帮实践意义。 w e b 日志挖掘通过对日志记录的挖掘，发现用户访问硪面的模式，从而 述一步分析秘研究匿恚记聚中斡筑律，疆麓改进鳐点的经栽和缀缀结秘，提 高用户查找信息的质量和效率，井通过统计和关联的分析找出特定用户与特 定地蛾、特定时间、特定越面等要素之间的内在联系。 w e b 疆惠挖掘数据颡处理鲍对象是原始的珏志文 牛中包含妁数据，蔟l 扣 不完麓的、冗余的、错误的数据需要进行处理。本文将针对数据预处理过程 中涉鼓舞趣关键阗耱程技术避舒洋缨戆澍辑摹蘑论述，绘窭个颈妊瑾摸麓。 介绍web 翔志挖掘前期工作一一一数据预处理的过程，可以在此基础上进 行挖掘算法的实现。提出的数据预处理模型遗台w e b 西志数据挖撼。 关联规则挖掘是web 丑志挖掘的一个蹩要的关键技术，它可以发现网 络日志访问记录中隐含的相互关系。生成关联规则的过程是在每个频繁大项 集中透匹浆瀵是一定懿支祷爱释可信疫的麓烈，也裁楚最小鼹痿凄的测 试。a p t i o r i 是关联规则挖掘算法改进的基础，但它可能产生庞大的侯选集。 h a n 握出f p t r e e 簿法。邋个算法只进行2 次数据瘁扫臻。它不健粥候选集， 直接压缩数据库成个频繁模式树，最后通过这棵树生成关联规则。它不会 魁引太学碰= 二学擅蛇支 有麓大鹤侯选集产生，减步了内存糕时空勰的占用。 序剥模式就是从序列数据霹中找出出褒频繁妁予穿剐，撼述一个事镬：痔 捌的连续生戏辑应避德豹规划。更遴一步把数据之阕瓣关联性与时间联系起 来。在w e b 羁志挖掘串，序烈摸式挖掘的络暴是熙户页颟浏鼙的先嚣顺序，这 些霆要信患可默通避模式分辑找出员露之闽鹃诱导作弱，序列攘式还表明页 谣浏赘对粥户的影# 囊，这种信息可以用予网燕的预先定澍。在序列模式挖掘 算法中，a p r i o r a l l 毒以下缺点：缺少对闽隈制，剡扳的冀劫定义，缺少分类。 s r i k a n t 提出了g s p 冀法商a p r i o r l 扩矮飘来。g s p 冀涟存在的主要闷题在予冒 能会产生大攫的镁遮序列模式；露要对序捌数据库避行循环扫描。p r e f i x s p a n 葵法不震要产生候选序列模式，从嬲大大缩减了检索空问籀对予藤始的净尉 数搌霹瑟富，投影数据库的规模不颐减小p r e f i x s p a n 算法的主要开销在于投 影数攮痒的擒造。 w e b 穗志挖撼中模式分析与模式表达通过发现的模式研究用户w e b 测燕 行为，理解访问毒的浏览兴趣，这墼郝蹩摄高w e b 簸务质量和改善站点结构 设计的夔要环节，是与阐户点接交瓦的部分其踅簧性并不豫予蓠兹嚣个阶 段。我们设汁的数据挖掘工具1 s m i n e r 辑埽的数据都存储在已经有了明确字 段定义的数摄痒或文本文件堡，也可称为结掏讫的数搌挖掘工具，以上鲍理 沦和算法在系统中褥弼了实现。它主要用来避行预测分辑、关联分摄、时阀 序列分析以及统计分析等。 关键词：w e b 醪患挖掘，关糕援剿，序列攘式，模式分橱 四川大学硕士学位论文 r e s e a r c h0 f w e b l o gm i n i n ga n d d e s i g na n dr e a l i z a t i o n 0 fl s h i n e rm i n i n g s y s t e m c o m p u t e r s 0 f t w a r ea n dt h e o r i e s p o s t g r a d u a t e ：z e n g p u s u p e r v i s o r ：p r o f d uz h o n g j u n m a k i n g u s e0 f d a t a m i n i n g ，w e bm i n i n gd i s c o v e ri n f o r m a t i o nf r o m w e bd o c u m e n tsa n ds e r v i c ew i t ht h er a p i dg r e w t h0 fi n t e r n e t ，w e bh a v e b e e nb e c o m ea 1 a r g e i n f o r m a t i o nr e s o u r c e b u tt h ec o n f l i c tb e t w e e n t h e1 i m i t e dh u m a na t e n t i o na n dt h eu n i m i t e di n f o r m a t i o ni sn o t a b l e w e bm i n i n gi n c l u d ew 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 d w e b u s a g em i n l n g s e a s a n i m p o r t a n tt e c h n i q u ea m o n g n u m e r o u sd a t a m i n i n gm e t h o d s w e bl o gm i n i n gt a k eso np a r t i c u l a ra c a d e m i ca n da p p li e d s i g n i f l c a n c e w e bu s a g em i n i n g isau s e f u lm e t h o dt 0f i n das e t p r e f e r e n c ea n db e h a v i o rc h a r a c t e r f r o mw e bn a v i g a t i o ni n f o r m a t i o i l i t1s i m p o r t a n tf o rw e bs i t em a n a g e m e n ta n dw e bu s e r sa t r a c t i o n r e t c d a t a p r e p r o c e ss i n gp l a ysa ne s s e n t i a lr o l ei nt h ep r o c e s s0 fw e b l o gm i n i n g i nt h l st h es is ，t h ek e yt e c h n o l o g ya b o u td a t a p r e p r o c e ss i n g iss t u d i e da n dd 1s c us s e da n dam o d e l0 fd a t a p r e p r o c e s s i n gi gb r o u g h t f o r w a r dt h ism o d e l0 f d a t a p r e p r o c e ss i n ga d a p t s t ow e bl o gm i n i n g m i n i n g0 fass o c i a t i o nr 1 1 e sis a ni m p o r t a n tt e c h n 0 1 0 9 y0 fw e bl o g m i n i n g ，a n d i td is c o v e rt h ec o n n o t a t i v er e l a t i o nb e t w e e nt h er e c o r d s 0 fw e b1 0 9 t h ep r o c e d u r eo fc t e a t i n ga ss o c i a t i o nr u l e sis m a t c h i n g r u l est h a tm e e tt h e s u p p o r t a n dc o n f i d e n c ei n l a r g ef r e q u e n t 3 堕坐查笺篓点鲎堡堡塞 i t e m s e t t h e a l g o r i t h m a p r i o r im a yg e n e r a t el a r g en u m b e ro fs u b s e t m i n i n gm a x i m u mf r e q u e n t i t e m s e tgl sa k e yp r o b l e mi nm a n yd a t am i n i n ga p p l i c a t i o n m o s to f t h e p r e v i o u s s t u d i es a d o p t a n a p t i o r i 1 i k e c a n d i d a t es e t g e n e r a t i o n - a n d - t e s ta p p r o a c h ，h o w e v e r c a n d i d a t es e tg e n e r a t i o ni s s t i l l c o s t l y ，e s p e c i a l l yw h e nt h e r ee x i s tp r o l i f i cp a t t e r n sa n d o r 1o n gp a t t e r n s h a nb r o u g h tf o r w a r da i g o r i t h mf p t r e e t h ea l g o r i t h m m a k e su s eo f p r e v i o u sm i n i n gr e s u l tt o c u td o w nt h ec o s to ff i n d i n q n e wm a x i m u m f r e q u e n ti t e m s e t s ， t h ea i 趣o f s e q u e n t i a lp a t e r nm i n i n g i st of i n dt h em a x i m a l s e q u e n c e si ns e q u e n c e8 e tw i t ha u s e r s p e c i f i e dm i n i m u ms u p p o r t a n d t h e ne a c hm a x i m a l s e q u e n c er e p r e s e n t sas e q u e n t i a lp a t e r n t h e r ea r e m a i n l yt w ok i n d so fs e q u e n t i a lp a t e r nm i n i n gm e t h o d s ：o n ei ss i m i a r w i t ha p t i o r i a i g o r i t h m ， a n dg s pi8 r e p r e s e n t a t i v e s u c ha l g o r i t h m s a r eb a s e do nt h ef a c tt h a ta s e q u e n c e i s f r e q u e n to n l y i fa l li ts s u b s e q u e n c e sa r ef r e q u e n t 。a n o t h e rm e t h o d 0 1 0 9 yo fs e q u e n t i a lp a t e r n m 二n i n gi st h ea p p l i c a t i o no fs e q u e n t i a lp a t t e r ng r o w t ht e c h n i q u eb a s e d c nt h ed a t a b a s ep r o j e c t i o n a m o n gt h e m p r e f i x s p a ni s v e r ye f i c i e n t b e e a u s eo fjt gc e n t r a l i2 e ds e a r c h i nt h i st h e s i s ，c o r r e s p o n 匹i 鞋孽s o l u t i o n st ot h e s ea l g o r i t h m sa r e o ! f e r e da n dr e a l iz e di nt h ew e b1 0 9m i n i n gs y s t e m ，is m i n e r k e y w o r d s ：w e bl o gm i r , i n g ，a s s o c i a t i o nr u l e ，s e q u e n t i a 3p a t e r r , jp a t e r n a n a l y s l s 4 四川大学硕上学位论文 第一章前言 1 1 研究背景与意义 网络技术近年取得了突飞猛进的发展，越来越深远地影响着人们的日常 生活和工作。因特网作为一种新的大众传媒，由于其快速，方便而受到人们 的普遍欢迎。电子商务，信息共享，教育科研，电子邮件等等服务使因特网 成为浩瀚的信息海洋。万维网是到目前为止世界上最丰富和最密集的信息来 源。对于这个世界上最丰富和最密集的信息来源，如何开发和利用这些丰富 的资源就成了人们普遍关注的问题。于是，数据挖掘技术和网络应用研究的 结合一w e b 数据挖掘技术( w e bm i n i n g ) 构成了当今比较活跃的一个研究 领域。 w e b 数据挖掘技术是近年个很热的研究课题，它是数据挖掘技术在网 络信息处理中的应用。w e b 挖掘技术主要包含了w e b 的内容挖掘、结构挖掘 和使用挖掘。他们分别挖掘w e b 站点文件内容、结构以及站点使用信息。 目前国际上对w e b 使用挖掘的研究比较多，w e b 使用挖掘通过挖掘w e b 浏览 记录来发现有意义的信息。例如有多少人访问了该页面，他们从哪里来，那 砦页面最受欢迎等。它可广泛地应用于个性化服务、系统改进、站点修改、 商业智能和浏览推荐等方面。当前经济模式变化，己从传统实体的商店转移 到i n t e n e t 上的电子交易，同时也改变了销售商和顾客的关系。通过w e b 使用 挖掘可以了解到顾客尽可能多的爱好和价值取向，以保证在电子商务时代的 竞争力。综合而言，w e b 使用挖掘具有以下几个方面的益处： 为用户提供个性化的服务。根据用户的访问历史，动态地向用户推荐商 品。在电子商务网站上进行个性化营销，具有很大的商业价值。 提高系统效率。随着w w w 的通信量的增加，影响网站用户满意度的主要 原因除了w e b 站点的内容外，其服务效率也很重要。通过w e b 使用挖掘，可以 提供网站服务效率全方位的信息。从而有勘于找到平衡服务器负荷，优化传 输，减少拥塞的方法，缩短用户等待时间，提高系统效率和服务质量。 提高网站结构设计。w e b 结构的复杂度在飞速的发展着。因此，w e b 站点 和w e b n 务器的设计和维护难度也在增加着，通过w e b 使用挖掘提供的用户使 用信息，可以帮助网站设计者确定如何修改网站结构。 疆鲥夫学硪：l 。学位论文 蠢务翊始熬援户嚣缎确定。分嚣 枣场拣售数糕默识别顾客的群缰，帮鼬 确定逛予离务产晶在w e b 夏蕊土豹布局摇放，内斌户露效舶撼荐产搽，以达到 扩大产品销甾量魏耳的。嗣时，有助予找到顾客访问翊站的生命周期，制定 相戍的营销策略。 网络安全。分析网上银行、丽上商品交翁用户强志，可以防藏巢客攻击、 恶意诈骗。 嘲站评估。w e b 使粥挖掘可以获敬掰户对网螭使带情况的第一手资瓣，舞 蠲辩评依据供依据。 可以惹滋，w e b 楚蠲挖掘豹雾 究舆毒重要豹煮义。燕楚理程虽然b 鸯一搂 楚j ；嚣的w e b 捷用挖掘工嶷，毽般只包含一些经鬻捷糟的统计掇告：点索数鞠 传翰字节数的挺总报告、排名靠前的被请求的u r l ( u n i f o r mr e s o u r c e l o c a t o r ) 、引用者以及最常用的浏豫器列表、每个甄联网域的点击次数、出 错摄告、鼹潦树缀告镣。 1 2 国内处婢究应粥愦况 数据挖掇技术程戚了数据库串懿辩谈发境( k d d ：k n o w l e d g e d i s c o v e r yl n d a c a b a s e s ) ，19 89 年8 旁举行的第l l 瑙国鼯联台天王餐麓学术会议提出主办 粒k d d 黼踩瓤讨会b 缝裂开了7 次，规模豳愿寒豹专题讨论会发展到鞫际学 术火会，入数出二三卡人到七八吾人，论文收录蹴捌从2 ：1 到6 ：l ，研究重点 也逐激从发现方法转肉系统皮用，并且注萋多种发现策略和技术的集成，以 及多种学科之间的相甄渗透。其他内容的专题会议也把数据挖掘和知识发现 列为议麟之，成为当前计算机科学界的一大热点。 目前，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 大类，衙目翦凰内外基予w e b 日志的糟户访问摸式挖掘叉可以分为 9 四川大学硕士学位论文 3 类： 分析站点性能，主要从统计学角度对频繁模式等进行发掘，很多商用 工具及有些免费工具属于此类； 7 理解用户意图，c h e n 等【i9 提出的路径游历模式( p a t ht r a v e r s a l p a t t e r n ) 发现算法等就是此类代表； j 改进站点设计，通过频繁路径、用户聚类，重构站点之间连接关系， 适应用户访问习惯，提供个性化信息服务。c o o k i er 等人【18 】开发的 w e b m i n e r 就属于这方面的应用。 现在世界上有许多著名的w e b 数据挖掘方向的公司： n e tp e r c e o t i 0 1 1 公司，他们的主要产品是n e tp e r c e r p t i 0 1 s ，它采用了 “实时建议”的技术：让产品对象( 主要是网站) 能够根据用户以往的浏览 行为( 包括这次的c l i c k t h r o u g h s 和以前的购买记录) ，在其他用户( 称做 c o m m u i l - t y ) 中找出与他有相类似浏览行为的，根据这些用户的浏览行为来 预测该用户以后的浏览行为，从而为用户提供个性化的浏览建议，其预言有 很高的准确性。并且它是实时运行的，随着浏览量的增加，它会变得越来越 “聪明”。 a c c r u e 公司主要有两大产品：a c c r u ei n s i g h t 和a c c r u eh i t l is t ， 前者主要是帮助顾客解决电子商务方面的问题，后者主要是用于网站流量分 析的。a c c r u ei ns i g h t5 是一个综合性的w e b 分析工具，它能够对网站的运 行状况有个深入，细致和准确的分析，利用了多种w e b 数据收集方法，包括 a d v a n c e dn e t w o r k c o l l e c t o r ，s e r v e rc o l l e c t o r s 和w e b s e r v e r l o g f l l e s 。a d v a i l c e dn e t w o r kc o l l e c t o r 以其能收集到最大量的数据而著称， 它能够收集到w e bs e r v e r 日志里所得不到的信息，a c c r u ei n s i g h t5 运用 了一种叫做“s e r v e rc o 儿e c t o r ”的分析方法，它支持镜象服务器和负载平 衡，路由器和一些其他网络结构设备，能够将一些加密的地址转化为可分析 的形式。a c c r u eh i tl is t 是表分析工具，适合于中型网站，目前的版本是 a c c r u eh 1 tl is t 4 5 1 。它主要运用在市场分析，搜索引擎，广告等方面 w e b t r e n d s 公司的重要产品是c o m m e r c e t r e n d s3 0 ，c o m m e r c e t r e n d s 提 供“b r o w s e r b a s e d ”方法，使得不同的部门( 从市场部门到分析家) 能在 任何时间得到他所想得到的个性化报表。它利用了数据仓库技术根据其提 哩川太学硕士学位论文 供的数据产生访问者的行为模式。 在w e b 粥户访闻信息挖掘酌理论醑究方蓠国凑羚学者也逡特了夫曩酸究 l 二作。 b o r g e sj ，l e v e n em 等人疲爝趣文本概率支法 h y p e r t e x t p r o b a b i3 i s t i cg r a m m a r 发现熙户迂移模式，并用g r a m m a r 的熵藏评估挖掘 到的模式。$ h a h a h i l l 5 i 等人提出的羁志挖掘系统依赖于客户端的数据收集， 客户端曲代理为服务搂返回用户请求的娠商及时间等数据。中国科学院数学 研究所周抛镶教授等人，提出了有荚w w w 浏览路径的熙基本概农，设计了 基于用户访问模式的湖览路径优亿簿法；清华大学麓少平教授等人，程毒n 元预溅禳艇对用户未采可髓送行酶w e b 访褥请求遴褥鞭溺。 w e b 挖掘是一个较耨豹醑究壤城，其有广阔瓣发袋霸斑黑羲藩。w e b 羁 志挖掘秘宥穰多溶瑟黎要瓣决鞠深人研究。我认蠢农几个研究方向上应该大 鸯爵为，比如：w e b 霹悫挖掇中内谯的扭理及颤的挖掘体系和结构的研究； 耀户访闷壤式痒鞠动悫绻护积更新、模式评价体系郓评份方法；挖掘算法的 适成性和时效性研究；镑能站点服务个性化和性能最优化的研究；关联规则 和序列模式在构造自组织站点方面的研究。 1 3 本文鹣肉密窝寝撵 在率交的研究中，数据挖掘方蕊主要集中在w e b 使爰挖掘姻阉遴、瑟惠挖 糖技术方嚣，蔽零实璃方羲主要酸究酌瓣聚是瓣尉发褒，篷辐荧联瓣弱挖掘 葬法帮穿铡模式算法。零交系统建磺完了w e b 嫠爝挖掇趣题，势塞觋7 一个w e b = 惑挖援工具1 s m i n e r 。务章的工佟是这样组织嶷排舶： 第二章出一般到特殊地分别介绍了数据挖搦、w e b 挖掘，w e b 舀志挖掘。 对于w e 弱惠挖掘的过程、挖掘的内容以及挽掘的应爝迸行了全面的论述，形 成了一个w e b 数据挖掘的斑面综述。 第兰章详细剖拼数据预处理遘程串涉获虱的荧键l 苟蘧和技术，援鑫了瘟 稻子我们的w e b 使用挖掘系统i s m i n e r 躺数据疆麓毽横壁框架。 第髓章研究了规鲻鹅缩的挖掇方法。主要搽讨鞔究关联规弼翱彦辩模式 的挖摄簿法，比较各舞法优劣，提出姣鼹f p t r e e 翱p r e f i x s p a n 墩用予关联规 则秘痔列模式熬挖掇。 四川大学硕士学位论文 第五章介绍了w e b 日志挖掘系统1 s m i n e r 的设计与实现技术及实验结果。 第六章总结了本文的工作。 辑j 琏大学壤圭学擅论文 第二章w e b 数据挖掘综述 w e b 数据挖握是在传统数攥挖掇鹣基础上发爱起来的，随着网络技术的 发展，网络资源也在飞速地膨胀，如何开发和利用这些丰富的资源就成了人 们营遍关注鹩褥燧。发瑗舂弱的数掇，去豫大量嚣簿数据，数据挖掘正努霹 以发挥其作用。于是，数据挖掘技术和网络应用研究结合在一起构成了当今 比较活跃的一个讲究领域一一w e b 数据挖掘。这样的结合使构臻w e b 上的复 杂应用，发掘网络太爨泰知知识成为可能。 不过，面向w e b 的数据挖掘又熙从传统的数据挖掘发展而来的，是以传 统戆熬据挖掘秀基础静。w e b 数据挖撼静缀多实瓣技术熟筵愚了较为残熬豹 数据挖掘算法。因此我们必须首先对传统数据挖掘有深入的理解，然后再研 究w e b 数据挖掘的理论和技术。鉴予此，率章先从数据挖据理论静产生帮发 展开始，再介绍其常用算法和挖掘舶过程及工具，最后蠲到本文的主题一 w e b 的数据挖掘的相关理论。 2 1 数瓣挖掘技术 2 1 i 数据挖掘的产生 上个世纪九十年代，随着数据库系统的广溅应用和网络技术的高速发 展，数瓣蓐技术发展到了一个全耨翡蹬段，熬过去经管理一骜篱单数器发曩 到了必须管理由各种设备、装置、计算所产生的图形、图像、音视频、电予 档案、w e b 网页等等彩种类黧的复杂数据，并且数据萤也越来越多。这一变 化给数据蓐技术带来r 很多豹挑战，需要我们研究许多新的阀题。世舁各地 数以十亿计的计算机上存储的海量数据里包含着许多重要信息，人们希望熊 对其送行深a 的分辑，发理势提取瓤藏在蔟孛豹缤惠，以更好遣剥弼这些数 据。数据库系统可以高效地炭现数据的录入、查询、统计等功能，假无法发 缆数据中存在的关系翔规刚，无法穰据臻肖的鼗耩预测未来翘发震趋势。缺 乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。 数据挖掘技术是人们长期对数据库技术迸行研究和汗发的结果，它使数 叫川大学碰士学位论文 据库技术进入了一个更高级的阶段。数据挖掘不仅能对存储在数据库中的过 去的数据进行查询和遍历，并且能够找出过去数据之间的潜在联系，找出新 的信息。因此，数据挖掘是从大型数据库或数据仓库中发现并提取隐藏在其 中的信息的一种新技术，目的是帮助决策者寻找数据间潜在的关联，发现被 忽略的要素。数据挖掘技术从大量数据中提取出可信、新颖、并被人理解的 模式，分析数据，挖掘大量数据背后的知识。 数据挖掘技术促成了数据库中的知识发现( k d d ：k n o w l e d g ed is c o v e r yi n d a t a b a s e s ) 的产生。1 989 年美国底特律召开的第1 1 届国际人工智能联合会 议的专题讨论会上首次出现了k d d 这个术语。随着来自各个领域的研究人员 和应用开发者不断增多，1 995 年在加拿大蒙特利尔召开了首届k d d 国际学术 年会。数据挖掘技术演变为工程领域的数据挖掘与科研领域的k d d 。2 0 o3 年 8 月在美国华盛顿了第九届k d d 国际年会。现在对k d d 的研究围绕理论、技 术和应用3 个方面展开。理论方面的研究包括：数据和知识的表示；结构化、 文本和多媒体数据的模型构造；不确定性管理；知识的实用性评测；数据 挖掘的算法复杂性和效率分析；海量数据集的统计学等。技术方面的研究 主要包括数据挖掘方法、数据挖掘算法和知识发现过程。数据挖掘方法包 括分类、聚类、预测和评估、相关性分析、搜索和优化等。数据挖掘算法 包括空间数据、文本数据和多媒体数据的数据挖掘算法、并行和分布式数据 挖掘技术等。知识发现过程包括数据预处理技术，如数据去噪、有效样本 选取、数据缩减等，此外还有知识的评估、统一和解释、数据和知识的可 视化。应用研究包括开发各种k d d 系统和工具及其在各个行业中的应用， 另外还包括一些有关数据保密的问题研究。 2 12 数据挖掘定义 对数据挖掘有许多不同的定义，但他们几乎都使用日益增强的计算技术 和高级统计分析技术来揭示大型数据库中的可用关系。数据挖掘与传统的数 据分析( 如查询、报表、联机分析) 的本质区别是数据挖掘是在没有明确假设 的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先未知，有 效和可实用三个特征。先前未知的信息是指该信息是预先未曾预料到的，既 1 4 四川大学硕士学位论文 数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是违背直觉的信 息或知识，挖掘出的信息越是出乎意料，就可能越有价值。 下面是对知识发现和数据挖掘比较被认可的定义【1 ： 知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b as e s ) ，从数据库管理系统中 存储的大量数据中提取出可信的，新颖的，有效的并被人理解的模式的处理 过程，以分析数据，挖掘大量数据背后的知识，称为数据库中的知识发现。 数据挖掘( d a t am i n - n g ) ，从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的 信息和知识的过程。 2 1 3 数据挖掘的分类 数据挖掘分类涉及的学科领域和方法很多，有多种分类方法。根据开采 对象分，有关系数据库、面向对象数据库、空间数据库、时态数据库、文本 数据库、多媒体数据库、异质数据库、遗产数据库及万维网w e b 。根据开采 方法分可粗略地分为：机器学习方法、统计方法、神经网络方法和数据库 方法。在机器学习中可细分为：归纳学习方法( 决策树、规则归纳等) 、基 于范例学习、遗传算法等。 2 i 4 数据挖掘的主要过程 一般而言，数据挖掘的过程包括【l ，4 53 ： 确定业务对象。清晰地定义出业务问题，认清数据挖掘的目的是数据挖 掘的重要一步。挖掘的最后结构是不可预测的，但要探索的问题应是有预见 的，为了数据挖掘而数据挖掘则带有盲目性，是不会成功的。 数据准备阶段，主要包括：数据的选择。搜索所有与业务对象有关的内 部和外部数据信息，并从中选择出适用于数据挖掘应用的数据；数据的预处 理。研究数据的质量，为进一步的分析作准备并确定将要进行的挖掘操作的 类型。数据的转换；将数据转换成一个分析模型这个分析模型是针对挖掘 算法建立的，建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关 四川大学硕士学位论文 键。 数据挖掘阶段。对所得到的经过转换的数据进行挖掘。除了完善从选择 合适的挖掘算法外，其余切工作都能自动地完成。 结果分析。解释并评估结果。其使用的分析方法一般应作数据挖掘操作 而定，通常会用到可视化技术。 知识的同化。将分析所得到的知识集成到业务信息系统的组织结构中 去。 2 2 常用的挖掘算法 圈2l 数据挖掘的基奉过程和主要步骤 2 2 1 数据挖掘的知识与模式 数据挖掘要发现知识，数据挖掘算法表达这些知识的方式是发现数据中 包含的模式。模式是数据集的某种抽象描述。 知识可以分为广义知识，关联知识，分类知识，预测型知识，偏差型知 识。广义知识指类别特征的概括性描述知识。根据数据的微观特性发现其表 征的、带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物 共同性质，是对数据的概括、精炼和抽象。广义知识的发现方法和实现技术 有很多，如数据立方体、面向属性的归约等。数据立方体还有其他一些别名， 四川大学硕士学位论文 如“多维数据库”、“实现视图”、“o l a p ”等。该方法的基本思想是实现 某些常用的代价较高的聚集函数的计算，诸如计数、求和、平均、最大值等， 并将这些实现视图储存在多维数据库中。既然很多聚集函数需经常重复计 算，那么在多维数据立方体中存放预先计算好的结果将能保证快速响应，并 可灵活地提供不同角度和不同抽象层次上的数据视图。另一种广义知识发现 方法是加拿大s i m o n f r a s e r 大学提出的面向属性的归约方法。这种方法以类 s q l 语言表示数据挖掘查询，收集数据库中的相关数据集，然后在相关数据 集上应用一系列数据推广技术进行数据推广，包括属性删除、概念树提升、 属性阈值控制、计数及其他聚集函数传播等。 关联知识反映一个事件和其他事件之间依赖或关联的知识。如果两项或 多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行 预测。最为著名的关联规则发现方法是r a g r a w a l 提出的a p r i o r i 算法。关 联规则的发现可分为两步。第一步是迭代识别所有的频繁项目集，要求频繁 项目集的支持率不低于用户设定的最低值；第二步是从频繁项目集中构造可 信度不低于用户设定的最低值的规则。识别或发现所有频繁项目集是关联规 则发现算法的核心，也是计算量最大的部分。 分类知识反映同类事物共同性质的特征型知识和不同事物之间的差异 型特征知识。最为典型的分类方法是基于决策树的分类方法。它是从实例集 中构造决策树，是一种有指导的学习方法。该方法先根据训练子集( 又称为 窗口) 形成决策树。如果该树不能对所有剥象给出正确的分类，那么选择一 些例外加人到窗口中，重复该过程一直到形成正确的决策集。最终结果是一 棵树，其叶结点是类名，中间结点是带有分枝的属性，该分枝对应该属性的 某一可能值。数据分类还有统计、粗糙集( r o u g h s e t ) 等方法。线性回归和 线性辨别分析是典型的统计模型。为降低决策树生成代价，人们还提出了一一 种区间分类器。最近也有人研究使用神经网络方法在数据库中进行分类和规 则提取。 预测型知识根据时间序列型数据，由历史的和当前的数据去推测未来的 数据，也可以认为是以时间为关键属性的关联知识。目前，时间序列预测方 法有经典的统计方法、神经网络和机器学习等。1 968 年b o x 和j e n k i n s 提出 r 一套比较完善的时间序列建模理论和分析方法，这些经典的数学方法通过 婴型奈兰堡圭篓堡堕一 建立蓬撬模型，翅塞圈归撰型、鸯霾强辫褰平趣摸燮、求季鬟蠡目努辫动平均 模型和季节调整模型等，进行时间序列的预测。由于大量的时间序列是非平 稳静，英特征参数和数据分布随着时闻羽推移蔼发生凌纯。灏此，仅仅通过 对某段历史数据的训练，建立单一的神缀网络预测模猁，还无法完成准确的 预测任务。为此，人们提出了基于统计举和基于精确性的再训练方法，当发 现褒存颓测援型不露逶熙予当夔数据畦，对模黧重毅谤l 练，获褥掰熬较重参 数，建立新的模型。也有许多系统借助并行算法的计算优势进行时间序列预 潮。 偏燕型知识可以发现其他类型的知识，它是对差舜和极端特例的描述， 搦示事物偏离常规的异常现象，如标准娄外的特倒，数据聚娄外的离群值等。 黪寿这魑知识部可以在不圊的概念屡次土壤发现，并隧着概念层次的提秀， 从微观刘中观、到宏观，以满足不同用户不同艨次决策的需鼹。 数掇挖掘葬法驭数据申发褒壤袁，扶嚣褥舞翔谖。模式毒疆多荸孛，按功 能可分有两大类：预测型fp r e d i c t i r e ) 模式和描述型( d e s c r i p t i r e ) 模式。 预濒型接式是可敬根据数据颈的篷精确确定某种结渠的模式。挖箍预测 型模式所使用的数据也都是可以明确知道结果的。 描述型模式是对数据中存在的规则徽一种描述，或者根据数据的相似性 撼数据分组。撼逑型模式不糍壹接孀于联测。 在实际应用中，根据模式的实际作用分为6 种： j ，分娄摸 式是一个分类函数分类器) ，麓够把数据集孛豹数嚣矮映封到 某个给定的类上。分类模式往往表现为一棵分类树，擞据数据的值从树根开 始搜索，沿着数据满足的分支往上走，惫到树旰就能确定类捌。 2 鄹蝗模式的整数定义与分类模式榴戗，它们的差别在予分类模式的顼 测值是离散的，回归模式的预测德是连续的。 ，辩阉露列模式擐据数据隧时阕变髭蝗趋势臻测将寒静 莛。这燕要考虑 割时间的特殊性质，像一贱周期性的时阊定义如星期、月、攀节、年等，不 两酌离子如节饭日可毹造成的影响，翟麓本身的计算方法，还有一疆需要特 殊考虑的地方如时间藏后的相关性 过去的事情对将来禽多大的影响力 等。 熙有充分考虑时间因索，利用现有数据 随时间变化的一系列的值，才能更好 憨预测将来的馕。 1 8 剐 | 大学硬士学靛论文 4 聚类模式把数据划分到不同的组中，组之间的差别尽可能大，组内的 差蹦尽司麓小。与势类模式不瓣，落行聚豢裁著不溜道将要巅分或死个缓和 什么样的组，也不知道根据哪一 几) 个数据项来定义组。一般来说，业务知 识丰寓的人应该可以理解这些组的岔义，如果产生的模式无法理解或不可 用，蚓该模式可能是戈意义的，露嚣回到上阶段燕薪组织数掇。 5 关联模式是数撼项之间的关联规则 6 露搠模式与关联模式糍传， l ；把数据之阕豹关联性与醛淘联系起寒。 为了发现序列模式，不仅需豫知道事件是谢发生，而且滞要确定事件发生的 时问。 在勰决实际问题对，经常要同时使用多种模式。分类模式和回归模式魁 使用最普遍的横式。分类模式、回归模式、时间序列模式也梭认为是受监督 知瑷，霸为在建立模式藏数撵戆结皋是已期的，霹以蠹接用来捡测模式憋准 确性，模式的产生是礁= 受监督的情况下进行的。一般在建立这些模式时，使 蒡j 一帮努数据作为祥率，薅翳一部分数据采检验、较东模式。聚类穰式、关 联模式、序列模式则是非监罄知识，因为在模式建立前结果是未知的，模式 的产生不受任何监督。 各转效据挖掘技术和算法爨究发现这些翘识翔模式的方法，比较常用的 一些技术有决策树、神经网络、规则归纳等。 2 2 1 决策树 决策树分为分类树和回姻树两种，分类树对离散交藿做决策树，圆妇树 对连续变鬟徽决策榭。一般的数据挖掘工舆，允诲选择分裂条 申和修剪规则， 以及控制参数( 最小节点的大小，最大树的深度等等) ，来限制决策树的 o v e r f l t t i n g 。 决策树是棵树，树的根节点是整个数据集合空间，每个分节点是对一 个单一变量的测试，该测试将数据集合空闻分割成两个或更多块。簿个卧第 点是属予单一类别柏记录。 首先，通过训练檠生成决策树，再通过测试集对决策树进行修剪。决策 瓣黪功熊是颈嵩一个赫鼹记录属于鄹一类。 决策树中艘上面的节点称为根节点，是整个决策树的开始。决策树的每 1 9 璺必盔堂堡生鲎焦堡苎一 个节点子节点的个数与决策树在阕的算法有关。如c a r t 算法得蓟的决策树 每个节点有硝个分支，这釉树称为二叉树。允许节点含有多于两个子节点的 树称为多叉树。 每个分支要么是个凝豹决策苓点，要么楚挺熬结冕，猿巍 予。在沿 着决策树从上到下遍历的过程中，在每个节点都会遇到一个问题，对每个节 点上闻蘧的不嗣回答导致不同的分支，簸后会到达一个辞予节点。这个避程 就是利用决策树进行分类的过程，利用儿个变量( 每个变爨对应个闷嬲) 米判断所属的类别( 最后每个叶子会对应一个类别) 。 数据挖掇中决策越是静经常要用到的技术，可以赐予分辑数据，尉样 也可以用来佧预测。常用的算法有c h a i d 、c a r t 、o u e s t 和c 5 0 。 建立决策褥豹过程，郄耱懿生长过程是不获幻把数撂遴程谤分豹过程， 每次切分对应一个问题，也对应潜一个节点。对每个切分都要求分成的纵之 间的“羞异”最大。 备弛决策树算法之间的主要区别就是对这个“差异”衡量方式的区别。 对具体衡量方式算法的讨论超出了本文的范围，在此我们只需要把切分群成 是把一缝数撼分戏死份，镑与 i 之趣尽蘩不同，露嗣一份蠹躲数撂器量嘏嗣。 这个切分的过程也可称为数据的“纯化”。 程定拳l 糟历史数据建立了一个包含几百个耩往、辕出静类毒卡尼种鹃凌 策树，这样的一棵树对人米说可能太复杂了，但每一条从根结点到叶子节点 的路往所描述的含义仍然楚可以理解的。决策树的这种易联解性对数据挖掘 瓣使用者来巍是一个显萋姻优点。 建立一颗决策树可能只要对数据库进行几遍扫描之后就能完成，这也意 睬着嚣簧懿计算资源较步，纛嚣霹l 鬟黎容爨姆薤理毽含穰多预测变量的壤 况，因此决策树模型可以建立得很快，并适合应用到大量的数据上。 对最终簧拿给入看的决策稀来说，在建立过程中诖萁生长薛太“校繁啼 茂”是没毫必要的，这样既降低了树的珂理鳃性和可用性，同时也使决策树 本身对历史数据的依赖性增大，也就是说这魁这裸决策树对此历史数据可能 非常壤确，一量疫翔翻簸鹣数据瓣准确性帮黎戢下降，我们棼这挚争情提必调 练过度。为了使得剥的决策树所蕴含的规则具有普避意义，必须防止训练过 菠，麓时也减步了调练酶霹闰。嚣此我们需簧宥一种方法翡诖我稍在逶窭粒 四川大学硕士学位论文 时候停止树的生长。常用的方法是设定决策树的最大高度( 层数) 来限制树 的生长。还有一种方法是设定每个节点必须包含的最少记录数，当节点中记 录的个数小于这个数值时就停止分割。 与设置停止增长条件相对应的是在树建立好之后对其进行修剪。先允许 树尽量生长，然后再把树修剪到较小的尺寸，当然在修剪的同时要求尽量保 持决策树的准确度尽量不要下降太多。 对决策树常见的批评是说其在为一个节点选择怎样进行分割时使用 “贪心”算法。此种算法在决定当前这个分割时根本不考虑此次选择会对将 来的分割造成什么样的影响。换句话说，所有的分割都是顺序完成的，一个 节点完成分割之后不可能以后再有机会回过头来再考察此次分割的合理性， 每次分割都是依赖于他前面的分割方法，也就是说决策树中所有的分割都受 根结点的第一次分割的影响，只要第一次分割有一点点不同，那么由此得到 的整个决策树就会完全不同。那么是否在选择一个节点的分割的同时向后考 虑两层甚至更多的方法，会具有更好的结果昵? 目前我们知道的还不是很清 楚，但至少这种方法使建立决策树的计算量成倍的增长，因此现在还没有哪 个产品使用这种方法。 而且，通常的分割算法在决定怎么在一个节点进行分割时，都只考察一 个预测变量，即节点用于分割的问题只与一个变量有关。这样生成的决策树 在有些本应很明确的情况下可能变得复杂而且意义含混，为此目前新提出的 一些算法开始在一个节点同时用多个变量来决定分割的方法。 决策树很擅长处理非数值型数据，这与神经网络只能处理数值型数据比 起来，就免去了很多数据预处理工作。甚至有些决策树算法专为处理非数值 型数据而设计，因此当采用此种方法建立决策树同时又要处