（计算机软件与理论专业论文）关联规则挖掘算法研究(1).pdf

关联规则挖铡算法研究 摘要 数据露中豁知诞发域( k n o w l e d g e d i s c o v e r y i n d a t a b a s e s ，k d d ) 是当 前涉及人工智能、数据库等学科的一门非常活跃的研究领域。数据挖掘( d a t a m i n i n g ，d m ) 佟为k d d 道程中波一个羹要懿步骤，耀予扶数攥中提取大镪 感必趣的、潜在的、可用的知识，并表示成用户可理解的形式，常被猎作是 k d d 的秘义词。 关联舰则挖掘是数粥挖掘的一个萋疆分支，用以发观所有满足最小支持 皮葶珏最小鬻信度鲍强关联趣懋。涯年来，关联裁慰挖掇磷究戏为鼗撂挖拯中 的一个热点，并被广泛应用于市炀营销、事务分析等成用领域。关联斌娜挖 撼簿法楚关联规则挖掘磷究的主器内容，迄今为止已提燃了许多裹效的关联 躐刚挖掘算法。本文对经典关联瀚则挖掘算法进行了系统的研究和全面的总 结，在此基础上掇出了耨的关联规则挖掘算法，并应爆于分布式数据撼握。 本文新骰酌稍新往的工作主疆如下： 1 对传统荚联规则挖掘鲍檄念进行了扩餍，g l 入交易黪长度、交易戆 支持诗数、交易之蕊的包吉关系、频繁交易以及频繁予项集等概念。 2 在对经典关联规则挖掘黧法研究的基础，e ，提出种憋于交翁的关 鼗掇粼拣掇算法c s r 。箨法c s r 基予交易长波，霹数据库进行了压缩，整 个挖掘过程对原数据库进行1 次扫描，对压缩数据库进行2 次扫描。与关联 瓣鼹挖掇舞法a p r i o r i 跑羧，减少了季j 撼次数，提高了挖掘效率。 3 对c s r 算法作了进一步的分析鞠改进，提出其改进算法c r ，并通 过实验分褥其毪黥。与c s r 摇魄，冀法c r 能够缩，j 、频繁矮爨翁候选集鹁 规模，从而提高算法的效率，并且算法c r 中的压缩数据库的结构也较算法 c s r 中压镶数据蓐懿结掬更惫餐练，节鸯了空勰。 4 将c r 算法与a g e n t 技术相结合，提出一种分布式关联规则挖掘系 统的框架m a r m s 。该系统缝构褥单、努于实戮，弱舜舆备移动a g e n t 赣多 a g e n t 系统的优点，能有效完成分布式关联规则挖掘 壬务。 荚键词：数耀挖掘关联规劂交辩交易畿度 t h er e s e a r c ho nt h ea l g o r i t h m so f m i n i n g a s s o c i a t i o nr u l e s a b s t r a c t 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 ) i s 基m u l t i d i s c i p l i n a r yf i e l d ， d r a w i n gw o r kf r o ma r e a si n c l u d i n gd a t a b a s et e c h n o l o g y ，a r t i f i c i a li n t e l l i g e n c e ， m a c h i n el e a r n i n g ，s t a t i s t i c s ，n e u r a ln e t w o r k s ，a n dp a t t e r nr e c o g n i t i o n d a t a m i n i n gi sak e ys t e po fk d d ，o f t e nr e g a r d e da st h es y n o n y m o fk d d i ti st h e p r o c e s so fm i n i n g t h ei n t e r e s t i n g ，p o t e n t i a l l yu s e f u l ，v a l i da n du n d e r s t a n d a b l e k n o w l e d g e i nd a t a a s s o c i a t i o nr u l e m i n i n gi s a n i m p o r t a n ts u b b r a n c ho fd a t am i n i n g ， w h i c hm i n e si n t e r e s t i n ga s s o c i a t i o no rc o r r e l a t i o nr e l a t i o n s h i p sa m o n gal a r g e s e to fd a t ai t e m s a s s o c i a t i o nr u l e sa r ec o n s i d e r e di n t e r e s t i n gi ft h e ys a r i s f yb o t h am i n i m u m s u p p o r t t h r e s h o l da n dam i n i m u mc o n f i d e n c et h r e s h o l d 。a s s o c i a t i o n r u l em i n i n gh a sb e c o m eah o tr e s e a r c ht o p i ci nr e c e n ty e a r s a n di th a sb e e nu s e d w i d e l y i ns e l e c t i v em a r k e t i n g ，d e c i s i o n a n a l y s i s a n db u s i n e s s m a n a g e m e n t a s s o c i a t i o nr u l em i n i n ga l g o r i t h m sa r et h ec o r ec o n t e n t si nt h ea r e a ，a n dt h e r e a r es e v e r a lf a m o u st y p i c a la l g o r i t h m s 。t h i sd i s s e r t a t i o nd o e ss o m er e s e a r c ho r l t h e s ea l g o r i t h m s ，p r o p o s e san e wa l g o r i t h ma n da p p l i e si tt od i s t r i b u t e dd a t a m i n i n g t h e r ea r eo r i g i n a lm a i ni d e a si nt h ep a p e ra sf o l l o w s ： t t h ed i s s e r t a t i o ne x t e n d s 瞧ec o n c e p to ft r a n d i t i o n a la s s s o c i a f i o nr u l e m i n i n g ，a n di n t r o d u c e ss o m ec o n c e p t s ，s u c ha st h el e n g t ho ft r a n s a c t i o n ，t h e s u p p o r t c o u n to ft r a n s a t i o n ，t h ei nr e l a t i o nb e t w e e n t r a n s a c t i o n s ，f r e q u e n t t r a n s a c t i o na n df r e q u e n ts u bi t e ms e t s 。 2 。c s r ( c o m p r e s s _ s c a n _ r e a s o n ) i s an e wa s s o c i a t i o nr u l em i n i n g a l g o r i t h m b a s e do nt r a n s a c t i o n ，i ts c a n st h eo r i g i n a ld a t a b a s eo n l yo n c e ，c o m p r e s s e st h e d a t a b a s eb yt h el e n g t ho ft r a n s a c t i o na n ds c a n st h ec o m p r e s s e dd a t a b a s et w i c e c o m p a r e d , w 4 t ha p r i o r i ，c s rd e c r e a s e st h ec o u n t so f s c a n n i n ga n d i n c r e a s e st h e e f f i e n c yo fm i n i n g 3 c ri s 黥i m p r o v e d a l g o r i t h mo f c s r i th a sm o r ee f f i c i e n c y , f o ri th a sa b e t t e rs t r u c t u r ei nt h ec o m p r e s s e dd a t a b a s e ，a n dr e d u c e st h es c a l eo ff r e q u e n t i t e ms e 转。 4 t h ed i s s e r t a t i o n i n t e g r a t e s c ra l g o r i t h ma n d a g e n tt e c h n o l o g y , a n d p r o p o s e s af r a m e w o r ko f m u l t i a g e n t a s s o c i a t i o nr u l e s m i n i n gs y s t e m ( m a r m s ) ，w h i c h h a s s i m p l e s t r u c t u r ea n di s e s a y t ob er e a l i z e d i tc a l l a c c o m p l i s h t h et a s ko fd i s t r i b u t e da s s o c i a t i o nr u l e m i n i n g ，f o r i th a st h e a d v a n t a d g c so f b o t hm o b i l ea g e n ta n d m u l t i a g e n ts y s t e m k e y w o r d s ：d a t am i n i n g ，a s s o c i a t i o nr u l e ，t r a n s a c t i o n ，t r a n s a c t i o nl e n g t h 独创性声明 本人卢叫所呈交的学位论文是本人在导师指导下进行的研究丁作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得金壁王、业盔堂或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文 中作了明确的说明并表示谢意。 学位论文作者签名= 甸枉瓦 签字隰二畔年月z 日 学位论文版权使用授权书 本学位论文作者完全了解盒胆王些友堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本 人授权盒魍王些盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 叫桂瓦 签字日期：力雄年6 月2 - 日 学位论文作者毕业后去向 工作单位： 通讯地址： 新虢q 硼 签字日期：巧年月1 日 电话 邮编 致谢 褒就论文宪或之黼，菲謦感谢我豹导帮麓学锯教授，谨囱我的导筛稿 学钢教授表示嫩真诚的谢意! 胡老师知识广博，治学严谨认真，对科研问题 商敏锐鲍洞察力。我在矮期阕骺取缮瞧成绩，枣不开胡老耀翡悉心攘导帮 鼓励。我的硕士论文也是在胡老师的精心修改和反复提炼下完成的。 惑谢王浩麓筛曾给我工作和学习上的许多帮助，王老师对科学研究的 执著追求给我留下了深刻的印象，是德得我学习的。 同时十分朦谢吴共庆老师和我的师兄王德兴，以及我的同学张玉红、 张晶、潮红鹗、倪羲亵扬静等，大家一起对数据挖掘潆题遂孬瑟讨，集惑广 益，这对我的论文有很大的启发。 感谢计算机学院的王新生老师和徐静老师! 感潦我豹父母，德们一鸯给我精神上韵鼓励和生活上的关怀，给了我 克服困难的信心和不断进取的渤力。感谢我的爱人李凯，在我的论文完成期 润，毽绘了我缀多生活主懿帮麓，著巍瓣论文本身也疆出了一些葑懿建议。 感泌赝鸯辫经给予我裁助鞠关心豹人 第一章知识发现概述 本章介绍了数据挖掘的定义及其研究现状和发展趋势，对数据挖掘的过 程、数据挖掘中的常用方法和技术以及数据挖掘的任务作了概要性的说明。 1 1 引言 随着计算机硬件和软件的飞速发展，尤其是数据库及数据仓库技术与应 用的日益普及，人们面临着快速扩张的数据海洋。然而，与日益成熟的数据 管理技术和软件工具相比，人们所依赖的数据分析工具却无法有效地为决策 者提供决策支持所需要的相关知识，从而形成了“信息丰富而知识贫乏”的 窘境。因此，如何有效利用这些数据逐渐成为计算机科学领域的一个重要的 研究课题，并受到广泛的关注。 随着数据库技术、人工智能、统计、并行计算和机器学习等技术的发展 和相互融合，数据库知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e s ，k d d ) z j 】 便酝酿生成。知识发现就是从数据中发现有用知识的整个过程，一般认为数 据挖掘( d a t a m i n i n g ，d m ) 4 1 是k d d 过程中的一个特定步骤，它用专门算法 从数据中抽取模式，然后再通过k d d 中的解释和评价模块转换成用户最终可 以理解的知识【5 】。从狭义上讲，数据挖掘是k d d 中从数据中抽取模式的特定 步骤；从广义上讲，数据挖掘又可以看作是数据准备、模式抽取、知识表示 等一系列步骤组成的k d d 的全过程，将二者看作同一概念【6 】。 本章首先介绍数据挖掘的定义及其研究现状和发展趋势，接着对数据挖 掘的过程、数据挖掘中的常用方法和技术以及数据挖掘的任务作了概要性的 说明，最后对本章进行了简要地总结。 1 2 k d d 的定义及其发展 下面对数据挖掘给出一个被普遍采用的定义描述： 数据挖掘( d m ) ，又称为数据库知识发现( k d d ) ，它是一个从大量数 据中抽取出未知的、有价值的模式或规律等知识的复杂过程刀。 数摒挖掘豹结暴必须是事先未知的，并璺对决策雨潜存的价德。例如， 从超市的大羹交易数据中发现，购买面包的顾客通常会同时购买牛奶，如果 将这鹾种食品放在列一货絮氏则为客户提供了懂剥，肯定会提高二者的销 售量。通过数据挖掘，能够从数据库中抽取出来有价值的知识，并从彳i 同角 度表示出柬，从而使大型数据库这种丰富可器的资源真正为人们所用。 数据挖耩还有一些其他中文译名，铡如：数据开采、数据采撅、知识采 掘、知识抽取、知识考察和资料挖掇等【8 j 。 k d d 与d m 是人工智能、梳器学习与数据库等接术捐结合的产物。k d d 一词是在1 9 8 9 年于美国底特律召开的国际人工智能会议中的知识发现专题讨 谂会上正式形成静。嚣蓠最畜影魂静有关k d d 酌学术会议楚k d d 强际会议， 其前身是k d d 专题讨论会( w o r k s h o p ) 。随着k d d 在学术界和工业界的影 璃越窳邃大，k d d 缀委会予1 9 9 5 年把专嚣讨论会燮名为潜际会议，著改为 大会代表自愿报名参加。1 9 9 5 年在加拿大的蒙特利尔市召开了第一届k d d 莺舔学零会议。由予数据瘁戆数据被影象遗比睃残矿床，飘此数据挖掘( d m ) 一词很快流传开来。k d d 国际学术会议以后每年召开一次【9 j 。第一本关于k d d 的国际学术杂志 d a , a m i n i n ga n d k n o w l e d g e d i s c o v e r y ) ) 逛于1 9 9 7 年3 舅创 刊发行。亚太地区于1 9 9 7 年在新加坡首次召开tk d d 国际学术研讨会 ( p a k d d ) 。 诗前，在i j c m 、a a a i 、v l d b 、a c m s i g m o d 等代袭人工智能与数据 库技术研究最高水平的国际学术会议上，对k d d 的研究都占有较大的比例， k d d 已经成为当今计算祝科学与技术研究、应用的热点领域之一。目前醋内 许多学术会议，如数据库学术会议、机器学习会议等，也都将k d d 列为重要 静繇究方 每挎j 。 此外，数据库、人工智能、信息处理、知识工程等领域的学术刊物也纷 绣开辟了k d d 专题袋专列。i e e e 瓣k n o w l e d g ea n dd a t ae n g i n e e r i n g 会列领 先在1 9 9 3 年出版了k d d 技术专刊。 1 9 9 8 霉a c m ( a s s o c i a t i o nf o rc o m p u t i n gm a c h i n e r y ) 正式藏立了k d d 的特别兴趣小组s i g k d d ( s p e c i ni n t e r e s tg r o u po nk n o w l e d g ed i s c o v e r vi n d a t aa n dd a t am i n i n g ) ，其宗旨就楚要综合蚤握关璐究领城载共圈兴趣茅【l 努 力，迎接从大型数据库中开采有用知识的挑战。 i n t e r n e t 上也荫不少k d d 电子出版物，其中以半月刊k n o w l e d g e d i s c o v e r y n u g g e t s 最为权威。另外从i n t e m e t 也可强下载各种各样的数据挖掘 工具软件和欺型的样本数据库，供人q n 试和评价。 2 1 3k d d 的处理过程 数据挖掘是k d d 巾的一个熏要的组成部分，同前时k d d 的研究主要集 中在对数据挖掘的研究上，丽忽视了其他方面的研究。零实上k d d 整个处 理过程的各阶段应该是一个有机的整体，如果仅仅着踅于数攒挖掘，就会影 响k d d 的效率及结果的准确性，因此，对k d d 的整个处理过程的研究也非 常有必蛩。 对k d d 整个处理过程的划分方式有很多种，比较热型的k d d 处理过程 摸登有翔下三静 ”j ： 第一种是u s a m a m f a y y a d 等人给出的多处理阶段模型； 第二耱是g e o r g e 疆j o h n 绘整懿多建瑾浍簸模鍪； 第三种是b r a c h m a n & a n a n d 提出的以用户为中心的处理模型。 下瓣簿单会缨第一耪楚理避疆模型，鞋滋馥k d d 主要基援款步骤1 - 1 5 见图1 。1 。 数据准智数据挖掘结果亵达和评价 一卜l i 数据源 k 。一一“一一。一一一j 图1 1 知识发现的一般步骤 数据准备由图1 1 可见，数据准备是知识发现的一个重要的子过程，它 包括3 个子步骤：数据集成、数据选择蕊数据颈处理。数据蒙成垮多文传或 多数据瘁运行环境中的数据合并处理，解决语义模糊性、处理数据中的遗漏 和清洗数据等。当建立模型所需要的数据集成以后，就需要为每个模型选择 侩当的数据。当数据库特鄹大时，选撵样本数据不失为一个好的方法，但样 本的选择必须合理，它对于大多数业务问题来说起码不会损失信息。数据预 处理主要对数据选择输敬产生豹数据遂行再加工，检查数据的完整经和一致 性，利用统计方法对丢失的数据进行填补，去除噪音数据和空白数据域，考 3 虑时间顺序和数据变化等。 数据挖掘此阶段主要完成以f3 个任务：( 1 ) 根据用户的要求，确定 k d d 发现的知识类酗，对k d d 的不 司要求，会在数据挖捌的过程中采用个 剐的算法。让数据挖掘系统为用户产生假设称为发现型的数据挖掘；用户自 己对数据库中可能包含的知识提出强泼称为验旺型的数据挖掘。( 2 ) 选择合 适的方法和技术。在1 4 节将对数据挖掘中常用的方法和技术进行总结介绍。 ( 3 ) 挖弼知识的操 乍，朝选择矮俸韵数裾挖擒簿法，包括选择合适的模墅和 参数，并运用此算法搜索或产生一个特定的感兴趣的模式或数据集，从数据 中提取蹴蠲户所需要静知谖，这些知识可以璃菜享孛特定戆方式表示或使霜一 些常用的表示方式，如产生式规则等。文献 1 6 1 对目前的数据摭掘算法进行了 谮徐。 结果表达和评价根据用户最终决策目的对提取的信息进行分析，去掉 多余的不切题慧懿模式，把最舂徐僮的售患区分出寒，著且遴过决繁支持工 具提交给决策者。此步骤不仅要把结果表达出来，还要对信息进行过滤处理， 为了取褥更有效的知识，可能会返回到藏匿处理魄某些步骤，以便反复提取， 从而提敬出更有效的知识。 1 4 k d d 的常闲方法和技术 数据挖掘的技术基础是人工智能( a i ，a r t i f i c i a li n t e l l i g e n c e ) 但又不仅 限于此。数据挖掘仅利用了人工智能中的部分已经成熟的算法和技术，其问 题静复杂住和难度都毖入工智能有所降低。下蕊对数掭挖掘领域中常用的方 法和技术做介绍。 1 4 1 统计分析方法 统计分析方法利用统计学、概率论的原理对关系中各属性及相互之间的 关系进行统计分辑，从枣甥铃巍数量上的表瑗去雄凝可能懿娥搏性。绞诗分 析方法怒最基本的数据挖掘技术方法之一【 】。因科学的规律性一般总是隐藏 的比较滚，最初总是从其数量寝现上邋过统计分板方法寻求初步线索，然后 提出一定的假说，作避一步的溪论研究。也就是说，溺理论研究提出一定的 结论时，往往逐需要在实践中加以验证【1 8 1 。 常掰的统计分祈方法有【掊，挣1 ：翔翔分析、因子分析、相关分析、多元回 归分析、偏最小二乘回归方法等。判别分析就是建立一个或多个判别函数， 劳确定一个粪爨标准，然后嚣未翘藩幢的对象，根据溺定的躐察值，将其划 归为已知类别中的一类；因子分析是用较少的综合变量来表达多个观察变量， 4 l = | 圣搌榴关恁太小把变篷分组，使褥备缝内蕊变量之阚榴荚鞍赢，不同组受避 m 的相关较低：相关分析是梢相关系数米度馈变量问的年h 荧程度；回门分析 是崩数学方程来表示变量溺鹣数量关系，方法有线性圄归弱j # 线性回归；缡 最小二乘回归是一种新型的多元统计数据分析方法，主要研究的是多囚变髓 对多巍变量的回归建模，特别当各变量内部麓度线_ | ! j 蔓棚关时，用此方法更加 有效，另外，偏最小二乘回归比较好的解决了样本个数少于变量个数等问题。 1 4 。2 遗传算法( g e n e t i ch l g o r i t h m s ) 大篷然懿佐琏劣汰镬餐器嵇宝物形箴了琴j 于吾爨存话翁行惫弱镞，这些 行为习惯为自然科学包括计箨机科学的发展提供了许多好的思路。遗传算法 裁是搂缀生甥避诧过疆兹算法，在浚诗中搜羯蒴象予生镑逡纯过稼豹、墓予 自然选择和生物遗传机制的优化技术。遗传算法是种基于生物进化过程的 组合优诧方法，是生物学和诗舆极稳结合静产物，幽美国窭蘧攫丈学熬d 。j h o l l a n d 教授和他的同事们在1 9 7 5 年首次提出的。 遗传算法主要出三个基本算子i a l 组成：( 1 ) 繁臻 y ”形式的蕴含式，表示数据库中满足x 中条件的记录也一定满足y 中的条件；其中x 亡i ，y c i ，并且x n y = 。x 称为关联规则的前件或前提，y 称为关联规则的后件或结果。 关联规则挖掘就是要发现所有满足最小支持度和最小置信度的关联规 则。关联规则挖掘技术被广泛应用于市场营销、事务分析等应用领域。 近年来，关联规则挖掘研究成为数据挖掘中的一个热点，提出r 许多高 效的关联规则挖掘算法。本论文的主要工作就是对关联规则展开讨论和研究， 论文第二章将对经典的关联规则挖掘算法作一介绍，第三章提出一种新的关 联规则挖掘算法c s r 及其改进算法c r ，第四章将算法c r 应用于分布式关联 规则挖掘，设计了一种分布式关联规则挖掘系统框架m a r m s 。 1 5 2 分类分析 分类( c l a s s i f i c a t i o n ) 就是找出一组能够描述数据集合典型特征的模型( 或 函数) ，以便能够分类识别未知数据的归属或类别，即将未知事例映射到某种 离散类别之一。 分类需使用一个分类函数或分类模型( 也称作分类器) ，该模型能把数据 库中的数据项映射到给定类别中的某一个。给定一训练数据集( 类别已知的 客体集) ，以及基于训练集中数据的特性建立的分类模型，目标是从该分类模 型中生成系列的分类规则，这些分类规则可用于对其他未来的数据进行分 类，从而可以更好地理解数据库中的每一类。如一个银行客户的信用等级是 属于a 级、b 级还是c 级。另外，在一些情况下需要对连续数值进行分类， 称之为预测。 分类器的构造方法主要有统计方法【3 3 】、机器学习方法”1 、神经网络方 法【3 6 】等。 9 1 5 3 聚类分析 聚类( c i u s t e r i n g ) ：是根据客体属性对一系列未分类客体进行类别的u 别，把一组个体按照相似性，分成若干类别，即“物以类聚”。其目的是使类 内相似件最大，而类问相似性最小。例如，一系列的新疾病可以根据其症状 的相似性进行分组，从而形成基本类别，同一类别中各疾病的共同症状便呵 用于描述该组疾病。 聚类分析与分类分析的不同之处在于，后者所使用的数据是己知类别归 属，属于监督学习方法，而聚类分析无论是在学习还是在归类测试所分析处 理的数据均无事先确定类别归属，即类别归属在聚类分析处理的数据集中是 不存在的，所以属于无监督学习方法。 聚类分析的技术大体可分为两类：分区( p a r t i t i o n a l ) 和分层( h i e r a r c h i c a l ) 。 分区就是给出一个对象集和聚类标准，然后将对象分区，每一区是一个类。 分区的典型算法有：p a m 3 7 1 、c l a r a 3 7 1 、b i r c h 【3 8 1 和d b s c a n l 3 9 等。分 层实际上是一种多层嵌套分区的方式，又分为聚集和分裂，聚集是将一个对 象看作一个类，然后逐层合并类，直到所有的对象都在一个类中，分类的过 程与聚集恰恰相反。分层算法主要有：c l i q u e 4 ”、b u b b l e 4 2 1 等。 l - 5 4 序列模式分析 序列模式发t g ( s e q u e n t i a lp a t t e r n sm i n i n g ) ：是指在多个数据序列中发现共 同的行为模式，其侧重点在于发现数据之间的前后( 因果、顺序) 关系模式。 例如，对于某顾客，在序列数据库d 中，序列模式发现问题就是在该数据库 中寻找所有的频繁序列或所有的最长频繁序列。典型的序列模式分析算法有： a p r i o r i s o m e t 4 、g s p 4 4 】等。 1 6 k d d 的应用及研究重点 1 6 1 k d d 的应用 数据挖掘虽然出现较晚，但由于其具有巨大的潜在使用价值，使得其逐 渐深入到许多领域，并出现许多成功的产品。数据挖掘技术在商业方面应用 较早，因为可增强企业的竞争优势，缩短销售周期，降低生产成本，有利于 制订市场计划和销售策略，数据挖掘技术已经成为电子商务的关键技术之一。 由于数据挖掘在开发信息资源方面的优越性，所以在保险、医疗、制造业等 1 0 各个行业也被人们所关注。下箍就应用最集中的几个领域进行简要的说明e 一、市场鬻销 零售业是数据挖掘应用较为活跃的一个领域。了解客户的购买习性和趋 势，对于零售商青l 订销售策略是至关麓要的。管理僖怠系统军鞋p o s 系统在零 售业中的广泛使用，特别是条形码技术的使用，使得收集用户购买商品的交 易数撵交褥楣鲞客荔。逶过关联藏剩蠡冬挖掘，分褥骞户对离箍翡霭滚状嚣， 发现顾客的潜在需求特征，有目的性的开展广告和销售业务。例如，通过分 辑链黉终数据记录，毽蘸主要应爱予键售预测、库存嚣求、零售点选择帮价 格分析，分析客户的购买行为和习惯，分析商场的销售商品的构成，使商晶 戆选择与搭配煲为科学。 二、医学应用 医学信息系统为医务人员收集到大量豹数据，邋过对这些数撂的挖撼， 分析病历和病人的行为特征，以及用于药方管理，对疑难病症的攻关和研究， 安排漕疗方案，判断药方的有效性，预测医疗保健赞用，缝合数据挖掘，建 立各种医疗数据模型，透过瑷象，将利于发现数据本质上的联系，推动医学 研究的进展。例如，挖掘某毖疾病之间的隐含关系，疾病和季节、环境以及 逢区帮饮食习惯静关系，研究久西分布、年龄构成秘身体状况等特征，有嗣 于开展药品的销售、医疗设施的配置和医院的布局等。美国i m s 公司在医药 方覆萼| 入数据挖掘技术，哥疆帮韵毽生写嚣莼处方，评价骜晶锖售效采以及 建立行为预测模型；英国的牛津移植中心也采用基于决策树方法的k n o w l e d g e s e e k e r 辏蘩缝翻蕊磅爨工 乍。 三、金融投资 接统熬驳鬃分毒厅欺转一般是专家定鬏对黢票交易颈测，然嚣，人工懿镞 测一般是根据自己的经验再结合对股票数据的分析得到的，所以很难对大艟 豹数撂进行分掇。采用数据挖握技术，通过分扳市场波动因素，建立预测摸 型，进行投资分析和预测，能够改进预测市场波动的能力，为投资者提供决 策的科学依据。由于金融业中的数据相对比较完整，质量较高，因此，数据 挖掘夜这一领域中的应用较为成熟，也取得较好的预期效粜和经济效益。例 如h n c 公司开发了应用金融领域的数据挖掘产品，美国第银行、f c c 国家 镶行、w e l lf a r g o 银抒稿讹学银行等采蠲数摄挖箍技术开发金融领域的数据捻 掘产晶。 金溢授瓷决策建立在怼数据分繇翡基麓之上。数据挖撼技术遥过对己瓷 数据的处理，找到数据对象之间的关系，然后利用学习得到的模式进行合理 戆羲测。透过怼售爱欺诈建横窝颈溅、嚣陵译售、羧盏分掇，絮黢疆雩亍发魏 具有潜在欺诈的事件，开展欺诈侦察和其他鑫融犯罪行为的分析，预防资盎 菲法流失。接察不寻鬻兹售耀卡约经溺，确定援羲露户秘溺费牙为。在证券 l l 交易中，帮助股票预测、证券市场的分析镰，可以发现“利润超邋”和“财 穆蕊骰”等溪象，避免遭黧熏大抟经济损失。 心、现代制造业 现代割选遂已不再是传统熬测淹盘郡诺鼹手工劳凌，丽是豢戚多耱巍遘 科技的流水作业。缬现代制造业中，数据挖掘广泛地应用于控制生产流程和 技术溪楚方罄。分褥产品串蚤释拯拣参数黪关系，镱 皂爨瓣靛搭醚，秀袋瑟 的产晶类型。根据市场信慰数据库中居民密度的分布、收入状况和相应的城 枣籁矧等蘩慧，金照濯此可臻戳开鼹产品糟求量豹镶盎等。 例如汽车制造商挖掘信虑库中人口分布、区域购买力状况级公路交溜等 售惑，根据分辑结果，决囊产器靛销售渠邋、总 奉嬲是部销售网终躲翅划等， 对商晶网络避行部潜，荠藏时调懿产品的嫩产导向和生产结构，这对予企业 和公司豹经蘩状况葶n 发展游景具有首要豹影响。黑外，在产品的控制和捻测 方藤，孤立点分丰厅可以用于检验产晶质量，谖剐裣瓣编慧，遂行零部件故障 诊断、资源忧化、生产过程分析、以及生产过程的忧化等。 聂、萁铯方瑟 在科学研究的计算科学中，数据挖掘技术能够帮助计算科学工作者分析 夫爨翡实验鼹瓣数攥。舔始，数据稼蕹技零瘟恩在生馨学巾基因工程酶磷究 上。 银行或鬻遂孛瀚靛诲行舞会绘镶幸亍爱鬻韭孳位豢亲基六豁经济撰失。秘 用数据挖掘技术能够总结砸常行为和欺诈行为之间的关系，减少欺诈的机会。 隧羞诗算规网终嚣普及，弼络安全越来越受到入粕黢羹规。溺络入侵为 网络上的倍患、资源带来了严重的安全威胁。在众多入僚检测授术中，数据 挖掘技术显示出箕优点。鏊予数擐挖掘豹入侵检测系统具有智能性好、爨动 纯程度高、检测效率高、裔适应熊力强、虑警率低等优势嘲。 另外，数据挖掘技术在语音合成、客户关系餐理、企事业部门等方斑都 有广泛翡皮焉。 1 6 。2 k d d 蔚硬究重点 熟识笈凝孛鸯关瓣挖掇方法、用户交互、毪藏帮番耱数据类鍪是k d d 懿 研究重点。 一、燕擦方法嬲霸户交嚣蘑题 与传统的数据分析方法相比，数据挖掘必须能够有效地处瑗大量数掇， 两且尽可糍使交互的，所以挖撼方法霸矮户交互婀题是k d d 鹃个礤究重 点。 1 ) 根据用户特定需要，在数撰库中挖掘不同类型的知识： 1 2 由于不同的用户可能对不同类型的知识感兴趣，数据挖掘系统应当覆盖 很广的范围，数据分析和知识发现任务包括数据特征化、区分、关联、分类、 聚类、趋势和偏差以及类似性分析，这些任务以不同方式使用不同的数据库， 需要开发大量数据挖掘技术。 2 ) 多个抽象层的交互知识挖掘： 由于很难准确地知道能够在数据库中发现什么，数据挖掘过程应当是交 互的。对于包含大量数据的数据库，应当使用适当的抽样技术，进行交互式 挖掘，允许用户聚焦搜索模式，根据返回的结果，提出和精炼数据挖掘的请 求。特殊地，类似于o l a p 在数据立方体上做的那样，应当通过交互地在数 据空间和知识空间下钻、上卷和转轴来挖掘知识，用这种方法，用户可以与 数据挖掘系统交互，以不同的粒度和从不同的角度观察数据和发现模式。 3 ) 数据挖掘查询语言和特定的数据挖掘： 关系查询语言( 如s q l ) 允许用户提出特定的数据检索查询，类似地， 需要开发高级的数据挖掘语言，用户通过说明与分析任务相关的数据集、领 域知识、所挖掘数据类型、被发现的模式必须满足的条件和约束，描述特定 的数据挖掘任务，该语言应当与数据库或数据仓库查询语言集成，并且对有 效的、灵活的数据挖掘是经过优化的。 4 ) 数据挖掘结果的表达和可视化： 发现的知识应当用高级的语言、可视化表示或其他形式表示，使知识易 于理解，能够直接被人们所使用。如果数据挖掘是交互的，这一点尤为重要， 这要求系统采用有表达能力的知识表示技术，例如树形、表、规则、图、图 表、矩阵或曲线等。 5 ) 处理噪音和不完整数据： 存放在数据库中的数据对象可能存在噪音、异常情况或不完全等情况， 会导致发现的模式精确性等差，需要处理噪音的数据清理方法，以及发现和 分析异常情况的孤立点挖掘方法。 6 ) 模式评估及兴趣度的描述： 数据挖掘系统可能有数以千计的模式，对于给定的用户，许多模式不是 有趣的，例如，表示公共知识或缺乏新颖性等原因。关于开发兴趣度评估技 术，特别是对于特定的用户，给出其所期望、评估模式价值的主观度量目前 仍是难以解决的问题。 二、性能问题 这包括数据挖掘算法的有效性、可伸缩性和并行处理性。 1 ) 数据挖掘算法的有效性和可伸缩性： 为了有效地从数据库的大量数据中提取信息，数据挖掘算法必须是有效 的和可伸缩的，即对于大型的数据库，数据挖掘算法的运行时间必须是可接 受的和可预计的，从数据库角度看，有效性和可伸缩性是数据挖掘系统实现 的关键问题，上面讨论的挖掘算法和用户交互的大多数问题，也必须考虑有 效性和可伸缩性。 2 ) 并行、分布式和增量挖掘算法： 许多数据库的大容量、数据的广泛分布和一些数据库挖掘算法的计算复 杂性是促使开发并行和 分布式数据挖掘算法，这些算法将数据划分为各个部 分，这些部分可以并行处理，然后合并各部分挖掘的结果。此外，有些数据 挖掘过程的代价高导致了对增量数据挖掘算法的需要，增量算法与数据库更 新结合在一起，而不必重新挖掘全部数据，这种算法渐进地进行知识更新， 修正和加强先前已经发现的知识。 三、关于数据库类型的多样性问题 1 ) 关系的和复杂类型数据的处理： 由于关系数据库和数据仓库已经广泛使用，对于开发有效的数据挖掘系 统是重要的，然而其他数据库可能包含复杂的数据对象、超文本、多媒体数 据、空间数据、时间数据、或事务数据等，由于数据类型的多样性和数据挖 掘的目标不同，指望一个系统挖掘所有类型的数据是不现实的。为挖掘指定 类型的数据，应当构造特定的数据挖掘系统，这样，对于不同类型的数据， 可能有不同的数据挖掘系统。 2 ) 异构数据库和全球信息系统的信息挖掘： 局域网和广域网( 如i n t e m e t ) 连接了许多数据源，形成了庞大的、分布 式的和异构的数据库。从具有不同数据语义的、结构化的、半结构化和非结 构化的不同数据源发现知识，对数据挖掘提出了巨大的挑战，数据挖掘可以 帮助发现数据库中的数据规律，这些规律多半难以被简单的查询系统发现， 因此，基于w e b 挖掘发现关于w e b 内容、w e b 使用和w e b 动态情况的有趣 知识，己经成为数据挖掘的一个非常具有挑战性的领域。 1 7 本文的课题来源和内容组织 1 7 1 本文课题来源 来源于国家自然科学基金项目( 编号6 9 9 8 5 0 0 4 ) 一“基于粗糙集合理论的 概念格模型研究”和安徽省教委重点科研项目一“大规模数据库中知识发现 系统的研究”( 项目编号2 0 0 0 j 1 1 6 8 z d ) 。 1 4 1 7 2 本文的内容组织 本文主要研究关联规则挖掘中的常用算法，提出一种改进算法，并将之 应用于分布式关联规则挖掘，结合a g e n t 技术构造了一个分布式关联规则挖 掘系统框架。 全文由五章组成： 第一章介绍数据挖掘的定义及其研究现状和发展趋势，对数据挖掘的过 程、数据挖掘中的常用方法和技术以及数据挖掘的任务作了概要性的说明。 第二章主要介绍关联规则中的有关概念，然后对经典的关联规则挖掘算 法如a p r i o r i 、p a r t i t i o n 等算法进行了介绍和总结。其中a p r i o r i 算法是挖掘关 联规则的经典算法，目前常见的关联规则挖掘算法大多是在该算法的基础上 加以改进的。另外，h e a l 等人提出一种不产生候选的算法，即f p - g r o w t h ( f r e q u e n t p a t t e r ng r o w t h ) 算法，或简称f p 增长算法，通过三个方面的改进 与创新 5 4 1 ，回避a p r i o r i 算法的先天性弱点，彻底脱离了传统的产生频繁项 集候选的方式，开辟了关联规则挖掘的新思路。 第三章首先对传统关联规则挖掘的概念进行了扩展，引入交易的长度、 交易的支持计数、交易之间的包含关系、频繁交易以及频繁子项集等概念， 接着基于对交易的扫描和推理，提出一种新的关联规则挖掘算法c s r ( c o r n p r e s s s c a nr e a s o n ) ，并通过实例分析c s r 的工作原理。算法c s r 基于 交易长度，对数据库进行压缩，整个挖掘过程对原数据库进行了1 次扫描， 对压缩数据库进行了2 次扫描。与关联规则挖掘算法a p r i o r i 比较，减少了扫 描次数，提高了挖掘效率。最后并对c s r 算法进一步改进，提出其改进算法 c r 算法，与c s r 相比，算法c r 能够缩小频繁项集的候选集的规模，从而提 高算法的效率，并且算法c r 中的压缩数据库的结构也较算法c s r 中压缩数 据库的结构更为简练，节省了空间。 第四章首先对分布式关联规则挖掘算法进行了回顾，接着将算法c r 应用 于分布式关联规则挖掘，并结合多a g e n t 和移动a g e n t 技术提出一种分布式 关联规则挖掘系统框架m a r m s ，它结构简单、易于实现，同时具备移动a g e n t 和多a g e n t 系统的优点，能有效完成分布式关联规则挖掘任务。 第五章是全文的总结，对本文的主要研究工作进行简要的阐述、说明， 并对本文尚需要进一步解决的问题进行了探讨和展望。 1 8 小结 本章介绍了数据库中的知识发现，其内容包括定义、过程、方法、模式、 发展和原型系统；数据挖掘的定义、知识的表现形式、方法等，其实质是挖 掘出用户所感兴趣的、潜在嬲知识或模式。广义的数据挖掘是指从大量的数 据中发现隐藏的、内在的和裔用的知识或信怠的过程；狭义的数据挖掘是指 知识发现中的一个关键步骤，是一个挖掘有用模式域建立模式的重要环节。 数据挖掘是在对数据禁全面丽深骝认谈酶蒸疆上，对数据肉在帮本蔟的高度 抽象与概括，也是对数据的认识从感性认识到理性认识的升华。此外简要说 葫了k d d 帮数据挖藏翡应嗣领域和缎震蘸豢，进一步对未来数据稳瓣蘸方两 和挑战进行了展望。 1 6 第二章关联规则挖掘基础 本章主要介绍关联规则中的有关概念，然后对经典的关联规则挖掘算法如 a p r i o r i 、p a r t i t i o n 等算法进行介绍和总结。 2 1 引言 关联规则是数据中的一种重要的模式。关联规则挖掘首先由a g r a w a l 5 q 等人 提出，用来处理事务型数据库，后来又推广到关系型数据库，现已成为数据挖掘 领域中一个非常重要的研究课题【5 。 关联规则最初应用于交易数据库时，用来发现超市中用户购买的商品之间的 隐含关系，以便为商场的决策提供依据。例如：关联规则可以表示为“购买了面 包的用户中有9 0 的人又买了牛奶”，商场决策者可以根据关联规则提供的信息 优化商场布置，将面包和牛奶摆放在一块以便于用户购买，从而提高商场的销售 业绩。 本章首先介绍了关联规则中的有关术语和定义，然后对经典的关联规则挖掘 算法作概括性的介绍和总结。 2 2 关联规则定义及术语 下面首先介绍一些常用的关联规则术语： 项目( i t e m ) ：交易数据库中的一个字段，对超市的交易来说一般是指一次 交易中的一个物品。例如，客户在某次交易中购买了“面包”和“牛奶”，则“面 包”和“牛奶”代