（计算机应用技术专业论文）数据挖掘中的关联规则技术研究.pdf

摘要 摘要 关联规则挖掘作为数据挖掘领域的一个重要研究内容，它揭示了项集之间有 趣的相关关系，可广泛应用于购物篮分析、相关分析、分类、网络个性化服务等 领域。自1 9 9 3 年r a g r a w a l 等首次提出该问题以来，一直是数据挖掘研究和应用 领域活跃的前沿。典型的关联规则发现算法是由r a g r a w a l 等提出的a p r i o r i 算法， 其核心技术为其它各类关联规则挖掘算法所广泛采用。 然而，随着分布式环境的日益普及，采用传统的集中式关联规则挖掘方法不 能高效地发现存在于分布式信息系统中的关联规则，设计高效的分布式关联规则 挖掘算法就成为关联规则研究的一个重要内容。本文在研究已有的分布式关联规 则挖掘算法的基础上，针对其不足，给出了一种高效的分布式关联规则挖掘算法 ( e d - a r m - - e f f i c i e n td i s t r i b u t e da s s o c i a t i o nr u l e sm i n i n g ) ，以快速地发现存在于 分布式事务数据库系统中的全局频繁项目集。对该算法所进行的分析和试验结果 证明，该算法是高效可行的。 另外，当数据库或挖掘参数发生变化时，如何高效地对频繁项目集进行更新 是关联规则挖掘研究的另一个重要内容。本文就频繁项目集的更新问题进行研究， 给出了一种基于频繁模式树的频繁项目集增量式更新算法( h u p f r e q u e n t i t e m s e t si n c r e m e n t a lu p d a t i n g ) 。该算法充分利用已有挖掘结果，有效解决了最小 支持度和事务数据库同时发生变化时相应频繁项目集的更新问题，其中事务数据 库的变化同时包括增加和减少两种情况，并对其性能进行分析与测试，结果证明， 该算法是有效的、可行的。 关键词：数据挖掘，关联规则，频繁项集，增量式更新，频繁模式树 a b s t r a c t i _ _ 一 a b s t r a c t a s s o c i a t i o nr u l e sm i n i n g ，a so n eo ft h em o s ti m p o r t a n tc o n t e n t si nd a t am m m g ， r e v e a l st h ec o r e l a t i o n sb e t w e e ni t e m s e t sa n dc a n b ew i d e l ya p p l i e dt om a n yf i e l d ss u c h a sm a r k e tb a s k e ta n a l y s i s ，c o r e l a t i o na n a l y s i s ，c l a s s i f i c a t i o n ，w e b 。c u s t o m i s e ds e r v i c e ， e t c a s s o c i a t i o nr u l e sm i n i n gw a sf i r s t l yp r o p o s e db yr a g r a w a li n 19 9 3 ，i nt h el a s t v e a r st h ed a t am i n i n gr e s e a r c ha n dt h ea p p l i c a t i o nd o m a i na c t i v ef r o n t t h et y p i c a l a s s o c i a t i o nr u l e sm i n i n ga l g o r i t h mi sb yr a g r a w a la n ds oo na p r i o r ia l g o r i t h m ，i t s c o r et e c h n o l o g yf o ro t h e re a c hk i n do fa s s o c i a t i o nr u l e sm i n i n ge x c a v a t i o na l g o r i t h m w i d e s p r e a d u s e h o w e v e r , w i t ht h ed i s t r i b u t e ds y s t e mb e i n ge x i s tw i d e l y , u s i n gt h et r a d i t i o n a l c e n t r a l i z e da s s o c i a t i o nr u l em i n i n gt o d i s c o v e ru s e f u lp a t t e r n s i nd i s t r i b u t e d i n f o r m a t i o ns y s t e mi sn o ta l w a y sf e a s i b l e d i s t r i b u t e da s s o c i a t i o nr u l e sm i n i n gh a s t h u se m e r g e da sa l la c t i v es u b a r e ao fa s s o c i a t i o nr u l e sm i n i n gr e s e a r c h b a s e do nt h e a n a l y s i so ft h ee x i s t i n gd i s t r i b u t e da l g o r i t h m sf o rm i n i n g a s s o c i a t i o nr u l e s ，a l le f f i c i e n t d i s t r i b u t e da s s o c i a t i o nr u l e sm i n i n ga l g o r i t h m ( e d - a r m ) i sp r e s e n t e dt of a s tf i n dt h e l a r g ei t e r e s e t so v e rt h ed i s t r i b u t e dt r a n s a c t i o nd a t a b a s es y s t e m t h ep e r f o r m a n c es t u d y a n dt h et e s tr e s u l t ss h o wt h a te d - a r ma l g o r i t h mi se f f i c i e n ta n df e a s i b l e i na d d i t i o n ，a s s o c i a t i o nr u l e su p d a t i n g ，a sa n o t h e ri m p o r t a n tc o n t e n to ft h es t u d y o fa s s o c i a t i o nr u l e sm i n i n g ，f o c u s e so i lh o w t oe f f i c i e n t l yu p d a t et h ef r e q u e n ti n t e m s e t s 0 nt h ec h a n g i n go fd a t a b a s eo rt h em i n i n gp a r a m e t e r s t h ep r o b l e mo fi n c r e m e n t a l u p d a t i n go ff r e q u e n t i t e m s e t si si n t r o d u c e db yt h en u m b e r sa n dc o r r e s p o n d i n g a l g o r i t h mf i u p ( f r e q u e n ti t e m s e t si n c r e m e n t a lu p d a t i n g ) i sp r e s e n t e dt o h a n d l et h e c h a n g i n go ft h em i n i m u ms u p p o r tt o g e t h e rw i t h t h et r a n s a c t i o nd a t a b a s ei n c l u d i n g i i l s e r t i n ga n dd e l e t i n gt h et r a n s a c t i o n si i lt h ed a t a b a s e t h ea l g o r i t h mm a k e s f u l lu s eo f t h ep r e v i o u sm i n i n gr e s u l tt oc u td o w nt h ec o s to fu p d a t i n gf r e q u e n ti t e m s e t s a tt h e e n do ft h ep a p e r ，s o m ea n a l y s e sa n dt e s t st ot h ea l g o r i t h ma r eo f f e r e d ，w h i c hs h o w s t h a tt h ea l g o r i t h mi se f f i c i e n ta n df e a s i b l e k e y w o r d ：d a t am i n i n g ，a s s o c i a t i o nr u l e s ，f r e q u e n ti t e m s e t s ，i n c r e m e n t a ln p d a t i n g , l 巾t r e e 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作过的同志对本研究所 做的任何贡献已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名： 导师签名： 日期巡：墨：多 日期 窜、拿聋 第一章绪论 第一章绪论 1 1课题背景 随着网络和计算机技术突飞猛进的发展、数据管理技术的成功应用以及企业 内部信息化程度的不断提高，大量的数据被积累起来，并存放于大型数据库系统 中。然而，面对这些堆积如山且处于迅速增长中的海量数据，无论在时间意义上 还是在空间意义上，传统的数据分析手段都难以应付。人们无法有效地理解并使 用这些数据，由此导致越来越严重的“数据灾难”，造成大量数据资源的浪费。因 此，面对“数据丰富而知识匮乏”的挑战，数据挖掘( d a t am i n i n g ，d m ) 1 1 j 技术应运 而生，并得到蓬勃发展，越来越显示出强大的生命力。 数据挖掘是数据库知识发现( k n o w l e d g ed i s c o v e ri nd a t a b a s e ，k d d ) i 】的核 心，是指从数据库的大量数据中提取人们感兴趣的、事先未知的、有用的或潜在 有用的信息的非平凡过程，是目前人工智能、数据库和信息决策领域研究的热点 问题。另外，数据挖掘是一种决策支持过程，它主要基于人工智能、机器学习、。 模式识别、统计学、数据库、可视化技术等，高度自动化地分析企业的数据，做 出归纳性的推理，从中挖掘出潜在的模式，应用于决策支持、市场分析和经济预 测等方面，帮助决策者调整市场策略，减少风险，做出正确的决策。因此，数据 挖掘技术引起了国内外学术界和工商界的广泛关注。 基于关联规则的数据挖掘是k d d 研究中的一个重要课题。关联规则挖掘就是 从大量的数据中挖掘出有价值的、描述数据项之间相互联系的有关知识。随着收 集和存储在数据库中的数据规模越来越大，人们对从这些数据中挖掘相应的关联 知识越来越有兴趣。 关联规则挖掘是由a g r a w a l 等人在进行市场购物篮分析( m a r k e tb a s k e t a n a l y s i s ) 时首先提出的i 训，用以发现商品销售中的顾客购买模式。关联规则可以发 现存于数据库的项目( i t e m s ) 或属性( a t t r i b u t e s ) f h 的有趣的关系，这些关系是预先未 知的和隐藏的，也就是说不能通过数据库的逻辑操作( 例如表的连接) 或统计的方法 得出。这说明他们不是基于数据库本身的固有属性( 如函数依赖关系) ，而是基于数 据库中数据项目同时出现的特征，所发现的关联规则可以辅助人们进行市场运作， 决策支持，及商业管理和网站设计等等。 目前，关联规则挖掘问题己经引起了数据库、人工智能、统计学、信息检索、 可视化及信息科学诸多领域的广大学者及研究机构的格外重视，并取得不少的研 2 数据挖掘中的关联规则技术研究 究成果。由于关联规则形式简洁、易于解释和理解并可以有效捕捉数据问的重要 关系，因此从大型数据库中挖掘关联规则的问题已经成为近年来数据挖掘领域的 一个热点。 1 2国内外研究现状 数据挖掘是数据库研究、开发和应用最活跃的分支之一。在注重理论研究的 同时，也重视将挖掘方法转变为实际的应用系统，注重多种发现策略和技术的集 成，以及多种学科之间的相互渗透。目前，世界上比较有影响的数据挖掘系统有： s a s 公司的e n t e r p r i s em i n e r ，i b m 公司的i n t e l l i g e n tm i n e r ，s g i 公司的m i n e s e t ， s p s s 公司的c l e m e n t i n e ，o r a c l e 公司的d a r w i n ，s y b a s e 公司的w a r e h o u s es t u d i o ， r u l eq u e s tr e s e a r c h 公司的s e e 5 ，由加拿大s i m o nf r a s e 大学“智能数据库系统研 究实验室 与d bm i n e rt e c h n o l o g y 公司共同开发的产品d bm i n e r l 5 j 等。这些系统 基本都提供多种数据挖掘方法，关联规则就是其中一种重要的挖掘方法。另外， 还有专门针对关联规则的挖掘系统c b a ，它是由新加坡国立大学开发的，用于从 关系数据库或者交易数据库中挖掘关联规则，从而使用发现的关联规则进行分类 和预测。 与国外相比，国内对数据挖掘的研究稍晚，还没有形成整体力量。目前，国 内己有一些科研单位和高等院校开展了知识发现和数据挖掘的基础理论及其应用 研究，这些单位包括清华大学、中科院计算技术研究所、复旦大学、空军第三研 究所、海军装备论证中心等。 目前，对数据挖掘的理论研究主要集中在分类、聚类、关联规则挖掘、序列 模式发现、异常和趋势发现等方面。关联规则挖掘用于发现大量数据中项集之间 有趣的关联或相关联系，其在商业等领域中的成功应用使它成为数据挖掘中最重 要、最活跃和最成熟的研究方向。 关联规则首先由a g r a w a l 等人于1 9 9 3 年在a c ms i g m o d 会议上提出并给出 了关联规则挖掘算法m s 引，但性能较差，a g r a w a l 等人又于1 9 9 4 年提出了著名的 a p r i o d 算法1 6 j 。自a p r i o r i 算法之后，许多研究学者在此算法的基础上，就如何减 少扫描次数以及在内存一定的情况下，如何减少读取数据库的i o 次数上进行了深 入的研究【7 - 1 碉。其中具有代表性的算法有：p a r k 等人提出的d h p 算法1 1 4 1 ，s a v a s e r e 等人提出的p a r t i t i o n 算法【1 5 】，s e r g e yb r i n 等人提出的动态数据项计算算法 。 ( d i c ) 【1 6 1 ，以及h a r t 等人提出的f p g r o w t h 算法【1 7 1 等。 传统的关联规则挖掘研究主要是在集中式数据库系统中，随着远程通信基础 设施的迅速发展，特别是i n t e r n e t 与w e b 技术的发展以及分布式数据库的不断增加， 使用上述传统的集中式关联规则挖掘方法对分布在不同地理位置的、甚至是不同 第一章绪论 3 应用领域的分布式数据库进行关联分析变得很不现实。针对这种情况，国内外的 学者对分布式数据库环境下关联规则挖掘进行了大量的研列1 8 彩l 。其中主要的算 法有：a g r a w a l 和s h a f e r 提出的并行算法1 d 和d d 算法【1 引，c h e u n g 等人提 出的f d m 算法【1 9 1 以及d m a 算法【2 0 1 ，以及杨明等人提出的f m a g f 算法【2 3 1 等。 效率问题是分布式关联规则研究的热点，已有的方法基本上都是基于这一点而提 出的。这些方法虽然在一定程度上提高了分布式系统的挖掘效率，但在实际的应 用中仍然存在效率低下的问题，因此提高效率仍然是当前分布式关联规则的研究 重点。 由于进行关联规则挖掘的数据库一般都很庞大，为了减少对数据库的访问次 数，c h e u n g 等人首先提出了关联规则的增量更新方法。此后，国内许多学者对关 联规则的增量更新算法进行了广泛的研究。针对集中式数据库系统，研究人员提 出了相应的关联规则更新算法【2 5 。3 1 】。例如：c h e u n g 等人提出的用于数据库发生变 化( 只考虑数据库中事务增加的情况) 时关联规则更新的f u p 算法【矧，以及冯玉才 等人提出的用于支持度发生变化时关联规则更新的i u a 算法【2 剐。目前，对于关联 规则更新的研究主要围绕以下两种情况进行： 1 ) 在给定的最小支持度和最小置信度情况下，当数据库变化后，如何生成 数据库中的关联规则； 2 ) 给定一个数据库，在最小支持度和最小置信度发生变化时，如何生成数 据库中的关联规则。 当前，对于数据库和最小支持度两者同时发生变化时关联规则更新问题的研 究却比较少。然而，随着关联规则技术在各领域的广泛应用和深入发展，研发针 对这种情况下关联规则更新的有效方法就成为关联规则研究中的一个不容忽视的 问题。 1 3课题的研究内容 本文的主要工作是根据国内外已有的关联规则技术研究现状及其最新发展动 态，研究分布式关联规则的挖掘以及关联规则的更新问题，针对已有算法的不足 提出相应的改进算法。论文主要研究内容包括以下几个方面： ( 1 ) 探讨了关联规则挖掘算法及理论，重点介绍了基于频繁项目集的关联规则发现 算法及其优化方法，并对一些典型算法进行了分析和评价，这是本文研究内容 的基础。 ( 2 ) 研究影响分布式环境下关联规则挖掘效率的因素，从降低网络通信量和减少局 部站点频繁项集计算的时间开销两个方面考虑，分别采用引入全局站点、事务 压缩和哈希过滤技术等来改进以往方法所存在的不足，并由此提出相应的分布 4数据挖掘中的关联规则技术研究 式关联规则挖掘方法以高效地发现存在于分布式事务数据库中的频繁项目集。 ( 3 ) 对关联规则更新所解决的问题以及已有的更新方法进行研究，针对因已有的更 新算法所考虑的变化情况单一或较简单而不能适应复杂情况下关联规则的更 新这一问题，提出了一种在最小支持度和数据库同时发生变化情况下的频繁项 目集的增量式更新方法。 1 4论文的组织结构 本文的组织结构如下： 第一章是绪论，论述了本课题的研究背景及研究意义，分析了其国内外研究 现状及不足，概括了本文的主要研究内容以及章节安排。 第二章阐述了数据挖掘理论的基本概念，以及数据挖掘的过程和用到的方法。 第三章介绍了关联规则挖掘的基础知识、相关理论和挖掘方法。主要是对经 典的关联规则挖掘方法a p r i o r i 算法，a p r i o r i 算法的优化方法以及不生成候选频繁 项集的f p g r o w t h 算法进行了详细的介绍和分析。 第四章在对已有的分布式关联规则挖掘方法研究的基础上，针对其不足，提 出了一种高效的分布式关联规则挖掘方法，并对该算法进行性能分析和测试，验 证了该算法是高效可行的。 第五章主要是对关联规则的更新方法问题进行研究。针对最小支持度和事务 数据库同时发生变化，且数据库的变化既有增加又有减少的情况，提出了一种频 繁项目集的增量式更新算法，并对算法进行分析和验证，结果证明该算法是有效 的、可行的。 第六章对本文的研究工作的进行总结，并提出针对相关问题的未来研究方向。 第二章数据挖掘理论与技术5 第二章数据挖掘理论与技术 2 1引言 随着数据库技术的成熟和计算机应用的普及，各行各业积累的数据迅速增长。 进入二十世纪末，伴随着网络的出现和发展，使得整个世界变成一个地球村，人 们可以跨越时空地在网上交换数据信息和协同工作。这样，展现在人们面前的已 不是局限于本部门，本单位和本行业的庞大数据库，而是浩瀚无垠的信息海洋。 当数据量越来越大时，使用传统或经典的方法，即便是使用计算机来提取有用信 息和知识，人们也会在面对海量的数据时感到无能为力。因此，如何有效地解决 数据获取的快捷与数据分析困难之间的矛盾，成为计算机科学技术中的一个重要 问题，而数据挖掘就是解决这一矛盾的一种手段。 2 2数据挖掘综述 2 2 1 数据挖掘的基本概念 所谓数据挖掘，是从海量的数据中，抽取出潜在的、有价值的知识( 模式或规 则l 的过程。也就是根据预定义的商业目标，对大量的企业数据进行探索和分析， 揭示其中隐含的商业规律，并进一步将其模式化的先进有效技术过程。数据挖掘 是一门交叉学科，它集成了许多学科中成熟的工具和技术，包括数据库技术、统 计学、机器学习、模式识别、人工智能、神经网络等等。 许多人把数据挖掘视为另一个常用的术语：数据库中的知识发现或k d d 的 同义词。而另一些人只是把数据挖掘视为数据库中知识发现过程的一个基本步骤。 知识发现过程由以下步骤组成： 1 ) 数据清理( 消除噪声或者不一致的数据) 2 ) 数据集成( 多种数据源可以组合在一起) 3 ) 数据选择( 从数据库中检索与分析人物相关的数据) 4 ) 数据变换( 数据变换或统一成适合挖掘的形势) 5 ) 数据挖掘( 使用智能方法提取数据模式) 6 ) 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) 7 ) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 广义的数据挖掘是从存放在数据库、数据仓库或者其它信息库中的大量数据 6数据挖掘中的关联规则技术研究 中挖掘有趣知识的过程。因此，数据挖掘系统具有以下主要成分【1 】：数据库、数 据仓库或其他信息库、数据库或数据仓库服务器、知识库、数据挖掘引擎、模式 评估模块和图形用户界面。数据挖掘系统组成结构如图2 1 所示： 图，髟用户界面 j1 厂j 1 心一 数i 据挖掘! 一一 、竺霉苎， i1 一 。一。二7 ( 数据库或数据仓库服务器) 、，、， 誓嚣鍪鬟i 过滤 清理上集成l 一 | 孑f 幸 i 数据库ff 数据仓库f 图2 1 数据挖掘系统组成结构 2 2 2 数据挖掘的特点 数据挖掘不同于人工智能。数据挖掘强调针对数据库中实际存储的数据进行 概念、规律、模式的发现，重点在于高效率的实现技术研究。人工智能的研究更 强调准确、高精度的方法研究，效率问题考虑的较少。 数据挖掘不同于统计分析。统计分析通常基于一个假设，通过数据去验证假 设成立或不成立。而数据挖掘直接从实际的数据中获得结论，因此结论也更可靠 和更实用。 数据挖掘不同于联机分析处理( o l 廿一o nl i n ea n a l y s i sp r o c e s s i n g ) ，数据挖 掘主要是用来发现大量数据中潜在的关系、模式、概念和规律。而数据仓库技术 中的联机分析处理主要提供给用户一个方便的图形查询方式，可以使用户从多个 角度对关心的数据进行考察，重点在于聚集操作的预处理技术。 数据挖掘能从大量数据中抽取出隐藏在数据之中的有用信息，从而为决策者 进行决策提供重要的依据，大大提高决策的科学性和减小决策的盲目性。数据挖 掘系统可以帮助商业管理者更好地理解用户的行为，制订相应的用户服务政策， 从而增加商业机会。 数据挖掘的任务是发现大量数据中尚未被发现的知识、从系统内部自动获得 知识。对于那些决策者明确了解的信息，可以用查询、联机分析处理或其它工具 第二章数据挖掘理论与技术7 直接获取。而隐藏在大量数据中的关系、趋势等，即使管理这些数据的专家也没 有能力发现这些信息，而这对于决策可能又是至关重要的，就需要利用数据挖掘 进行知识获取。 2 2 3 数据挖掘过程 数据挖掘过程一般包括以下三个部分：数据的准备、模型的建立、模型的验 证和评价【3 2 】，数据挖掘的过程如图2 2 所示。各主要组成部分的功能详述如下。 图2 2 数据挖掘过程的步骤 ( 1 ) 数据的准备 数据的准备包括数据取样、数据特征探索、分析和预处理，同时要明确问题， 选择合适的数据，必要时要进行调整。例如计算统计变量( 譬如平均值、均方差等) ， 再用图表或图片直观地表示出来，进而可以看出一些变量之间的相关性( l l 如有一 些值，经常一起出现) 。选择正确的数据源对整个数据挖掘项目的成败至关重要。 数据取样要把好数据的质量关，在任何时候都不要忽视数据的质量，即使是 从一个数据仓库中进行数据取样，也不要忘记检查其质量如何。因为数据挖掘的 目的是要探索企业运作的规律性的，如果原始数据有误，则还谈什么从中探索规 律性? 若你真的从中还探索出来了什么“规律性 ，再依此去指导工作，则很可能 是在进行误导。若你是从正在运行着的系统中进行数据取样，则更要注意数据的 完整性和有效性。 ( 2 ) 模型的建立 这一步是数据挖掘工作的核心环节。对建立模型来说，最重要的就是它是一 个反复的过程。需要仔细考察不同的模型以判断哪个模型对你的问题最有用。在 寻找好的模型的过程中学到的东西会启发你修改你的数据，甚至改变你最初对问 题的定义。 一旦决定了挖掘类型之后，就需要选择模型的类型。模型的类型可能是一棵 决策树、神经网络、甚至是传统的数学统计。选择什么样的模型决定了你需对数 据做哪些预处理工作。如神经网络需要做数据转换，有些数据挖掘工具可能对输 入数据的格式有特定的限制等。一旦所有的数据准备好了之后，就可以开始训练 8数据挖掘中的关联规则技术研究 你的模型了。 就目前的技术发展水平而言，数理统计方法还是数据挖掘工作中最常用的主 流技术手段。市场上很多的软件供应商和数据挖掘咨询公司一般都提供了很多的 软件包，包含有很多实用的数理统计方法。而在你的数据挖掘模型中使用哪一种 方法，具体用软件包中的什么方法来实现，主要取决于数据集的特征和要实现的 商业目标。实际上，这种选择也不一定是唯一的，可以多试几种方法，从具体的 实践中选出最合适的方法和软件。 ( 3 ) 模型的验证和评价 从上述过程中将会得到一系列的分析结果、模式和模型，评价的方法之一是 直接使用原来建立模型的样板数据来进行检验。假如这一关就通不过的话，那么 决策支持信息的价值就大打折扣了。一般来说，如果在这一步得到了较好的评价 结果，就说明确实从这批数据样本中挖掘出了符合实际的规律性。 另一种方法是另外找一批数据，已知这些数据反映了客观实际的规律性。这 次的检验效果可能会比前一种差。差多少是要注意的。若是差到不能容忍的程度， 那就要考虑第一次构建的样本数据是否具有充分的代表性或是否是模型本身不够 完善。这时候可能要对前面的工作进行反思了。若这一步也得到了肯定的结果， 那么数据挖掘应该能得到很好的评价了。 再一种办法是在实际运行的环境中取出新鲜数据进行检验。如在一个应用实 例中，则可以再进行一段时间的现场实际检验。 一般来说，如果使用模型得到的是一个直接的结论，固然是好。但是，实际 上这种情况非常的少，更多的时候得出的是对目标问题多侧面的描述，这时就要 能很好地总结它们的规律性，提供合理的决策支持信息。所谓合理，实际上往往 是需要在所付出的代价和要达到的预期目标的可靠性上做出选择。假如在数据挖 掘过程中，就预见到最后要进行这样的选择的话，那么最好把这些平衡的指标尽 可能地量化，以利于综合抉择。 在实际应用中，随着应用数据的不同，模型的准确率肯定会有所变化。更重 要的是，准确度自身并不一定是选择最好模型的正确评价方法，需要进一步了解 错误的类型以及由此所带来的相关费用。在实际应用中，如果每种不同的预测错 误所需付出的代价( 金钱) 也不同的话，那么代价最小的模型( 而小一定是错误率最 小的模型) 就是我们所要选择的。 ( 4 ) 模型的实施 模型建立并经过验证之后，可以有两种主要的使用方法。第一种是提供给业 务人员或分析人员做参考，通过察看和分析这个模型之后提出行动方案建议。比 如，可以把模型检测到的聚集、模型中蕴含的规则或表明模型效果的图表拿给分 第二章数据挖掘理论与技术9 析人员看。另一种是把此模型应用到不同的数据集上。模型可以用来标识一个事 例的类别，给一项申请打分等。还可以用模型在数据库中选择符合特定要求的记 录，并用o l a p 工具做进一步的分析。 这里需要指出的是，上面的各个步骤按顺序排列，要注意数据挖掘过程并不 是线性的，要取得好的结果就要不断重复这些步骤。比如在“建立模型”时，你 可能觉得在“数据预处理”时做得不够好，或者是要往罩面添加一些新的数据等。 当提交一个复杂的应用时，数据挖掘可能只是整个产品的- d , 部分，但却可 能是最关键的一部分。例如，在欺诈检测系统中，我们常常把数据挖掘得到的知 识与领域专家的知识结合起来，然后应用于数据库中的数据。 2 2 4 数据挖掘的应用 由于数据挖掘能分析出数据中的有用信息，给企业带来显著的经济效益，这 就使得数据挖掘技术越来越普及。 英国电信需要发布一种新的产品，需要通过直邮的方式向客户推荐这种产品， 使用数据挖掘技术使直邮的回应率提高了1 0 0 ；g u s 日用品零售商店需要准确 的预测未来的商品销售量，降低库存成本，使用数据挖掘技术使库存成本比原来 减少了3 8 ；汇丰银行需要对不断增长的客户群进行分类，对每种产品找出最有 价值的客户，使用数据挖掘技术使营销费用减少了3 0 ；美国国防财务部每年需 要从上百万笔的军火交易中发现可能存在的欺诈现象，使用数据挖掘技术可以发 现可能存在欺诈的交易，然后再进行深入调查，大大的节约了调查成本。 许多企业都在利用数据挖掘技术帮助管理客户生命周期的各个阶段，包括争 取新的客户和保持住好的客户。另外还可以用其分析潜在客户，根据挖掘出的客 户特点，为客户提供针对性的服务。 许多公司已将数据挖掘产品化，两个大型统计软件公司s a s 和s p s s 也推出 了各自的数据挖掘工具e n t e r p r i s em i n e r 和c l e m e n t i n e 。 从事数据挖掘研究与开发的还有微软、i b m 等，i b m 公司的i n t e l l i g e n tm i n e 具有典型数据集自动生成、关联发现、序列规律发现、概念性分类和可视化显示 等功能。它可以自动实现数据选择、数据转换、数据挖掘和结果显示。若有必要， 对结果数据集还可以重复这一过程，直至得到满意结果为止。 数据挖掘在医疗应用领域具有广阔的前景，数据挖掘可以用来预测外科手术、 医疗试验和药物治疗的效果。零销商使用数据挖掘来决定每种商品在不同地点的 库存，通过数据挖掘更灵活的使用促销和优惠卷手段。制药公司通过挖掘巨大的 化学物质和基因对疾病的影响的数据库来判断哪些物质可能对治疗某种疾病产生 效果。 1 0数据挖掘中的关联规则技术研究 在农业生产方面，农业生产与气候、气象有着密切的关系，我国是一个农业 大国，农业生产关系到国家经济命脉和人民生活，数据挖掘在农业气象预报中的 应用是比较有意义的工作。 人们普遍认为数据挖掘的未来是美好的。m e t ag r o u p 曾做出这样的评论： “全球重要的企业、组织会发现，到2 1 世纪数据挖掘技术将是他们商业成功与否 的至关重要的影响因素”，国际知名调查机构g a r t n e rg r o u p 在高级技术调查报告 中，将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响的五大 关键技术”之首，还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大 新兴技术前两位。g a r t n e r 的调查报告预计：到2 0 1 0 年，数据挖掘在相关市场的 应用将从目前少于5 增加到超过8 0 。美国银行家协会预测数据仓库和数据挖 掘技术在美国商业银行的应用增长率是1 4 9 【3 3 】。 2 3数据挖掘方法 数据挖掘中采用的方法综合了数据库、人工智能、统计学、模式识别、机器 学习、数据分析等领域的研究成果。现有的数据挖掘方法主要有以下几种【3 4 】：人 工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ) 、遗传算法( g e n e t i ca l g o r i t h m s ) 、决策树方 法( d e c i s i o nt r e e s ) 、关联分析( a s s o c i a t i o n s ) 、序列模式分析( s e q u e n t i a lp a t t e r n s ) 、 分类分析( c l a s s i f i e r s ) 、聚类分析( c l u s t e r i n g ) 。 2 3 1 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ) 神经网络为解决大复杂度问题提供了一种相对来说比较有效的简单方法。神 经网络可以很容易的解决具有上百个参数的问题( 当然实际生物体中存在的神经 网络要比我们这里所说的程序模拟的神经网络要复杂的多) 。神经网络常用于两类 问题：分类和回归。 在结构上，可以把一个神经网络划分为输入层、输出层和隐含层。输入层的 每个节点对应一个个的预测变量。输出层的节点对应目标变量，可有多个。在输 入层和输出层之间是隐含层( 对神经网络使用者来说不可见) ，隐含层的层数和每 层节点的个数决定了神经网络的复杂度。 除了输入层的节点，神经网络的每个节点都与很多它前面的节点( 称为此节 点的输入节点) 连接在一起，每个连接对应一个权重，此节点的值就是通过它所 有输入节点的值与对应连接权重乘积的和作为一个函数的输入而得到，我们把这 个函数称为活动函数或挤压函数训练周期。要完成神经网络的训练可能需要很多 个训练周期，经常是几百个。训练完成之后得到的神经网络就是在通过训练集发 第二章数据挖掘理论与技术 现的模型，描述了训练集中响应变量受到预测变量影响的变化规律。 神经元网络和统计方法在本质上有很多差别。神经网络的参数可以比统计方 法多得多。参数通过各种各样的组合方式来影响输出结果，以至于很难对一个神 经网络表示的模型做出直观的解释。实际上神经网络也正是当作“黑盒 来用的， 不用去管“盒子”里面是什么，只管用就行了。在大部分情况下，这种限制条件 是可以接受的。比如银行可能需要一个笔迹识别软件，但它没必要知道为什么这 些线条组合在一起就是一个人的签名，而另外一个相似的则不是。在很多复杂度 很高的问题如化学试验、机器人、金融市场模拟以及语言图像识别等领域神经网 络都取得了很好的效果。 神经网络的另一个优点是很容易在并行计算机上实现。可以把它的节点分配 到不同的c p u 上并行计算。 2 3 2 遗传算法( g e n e t i ca l g o r i t h m s ) 遗传算法是模拟生物进化过程的算法，由三个基本算子( 或过程) 组成： 1 ) 繁殖( 选择) ：即从一个旧种群( 父代) 选出生命力强的个体，产生新的种 群( 后代) 的过程。 2 ) 交叉( 重组) ：即对选择两个不同的个体( 染色体) 的部分( 基因) 进行交换， 形成新个体的过程。 3 ) 变异( 突变) ：对某些个体的某些基因进行变异( 0 变1 ，或1 变0 ) ，形成 新个体的过程。 这种遗传算法可起到产生优良后代的作用。这些后代需满足适应值，经过若 干代的遗传，将得到满足要求的后代( 也就是问题的解) 。遗传算法已在优化计算 和分类机器学习方面发挥了显著作用。 2 3 3 决策树( d e c i s i o nt r e e s ) 决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。比 如，在贷款申请中，要对申请的风险大小做出判断，决策树的基本组成部分：决 策节点、分支和叶子。决策树中最上面的节点称为根节点，是整个决策树的开始。 决策树的每个节点子节点的个数与决策树采用的算法有关。如c a r t 算法得到的 决策树的每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节 点的树，称为多叉树。 每个分支要么是一个新的决策节点，要么是树的结尾( 也称为叶子) 。在沿着 决策树从上到下遍历的过程中，在每个节点都会遇到一个问题，对每个节点上的 1 2数据挖掘中的关联规则技术研究 问题的不同回答导致不同的分支，最后会到达一个叶子节点。这个过程就是利用 决策树进行分类的过程，利用几个变量( 每个变量对应一个问题) 来判断所属的类 别，最后每个叶子会对应一个类别。 建立决策树的过程，即树的生长过程是不断的把数据进行切分的过程，每次 切分对应一个问题，也对应着一个节点。对每个切分都要求分成的组之间的“差 异”最大。 2 3 4 关联分析( a s s o c i a t i o n s ) 从用户指定的数据库中挖掘出满足一定条件的依赖性关系。关联规则形如 “4j 以，支持度( s u p p o r t ) = s ，置信度( c o n f i d e n c e ) = c ”，其中s 和c 是用户 指定的支持度和置信度的阈值。这种关联规则挖掘可以在不同的抽象概念层次上 进行。例如r l ：“尿布专啤酒，支持度= 5 ，置信度= 5 0 与r ，：“婴儿用品类号 饮料类，支持度= 2 5 ，置信度= 8 0 相比，足在更高的抽象层次上，更为宏观， 因而有较大的支持度和置信度，更适合高层决策需要。 2 3 5 序列模式分析( s e q u e n t i a lp a t t e r n s ) 序列模式分析和关联分析法相似，其目的也是为了挖掘出数据之间的联系， 但序列模式分析的侧重点在于分析数据间的前后( 因果) 关系。它能发现数据库中 形如“在某一段时间内，顾客购买商品a ，接着购买商品b ，而后购买商品c ， 即序列a b - - - , c 出现的频度较高”之类的知识，序列模式分析描述的问题是： 在给定交易序列数据库中，每个序列是按照交易时间排列的一组交易集，挖掘序 列函数作用在这个交易序列数据库上，返回该数据库中出现的高频序列。在进行 序列模式分析时，同样也需要由用户输入最小置信度c 和最小支持度s 。关联规 则中采用的a p r i o r i 算法也可以用于序列模式的挖掘，因为若长度为k 的序列模式 是非频繁的，其超集( 长度为k + 1 ) 不可能是频繁的。因此序列模式挖掘的大部分方 法都采用了类a p d o r i 算法的变种，只是所考虑的参数设置和约束有所不同。 2 3 6 分类分析( c l a s s i f i e r s ) 设有一个数据库和一组具有不同特征的类别( 标记) ，该数据库中的每一个记 录都赋予一个类别的标记，这样的数据库称为示例数据库或训练集。分类分析就 是通过分析示例数据库中的数据，为每个类别做出准确的描述或建立分析模型或 挖掘出分类规则，然后用这个分类规则对其它数据库中的记录进行分类。 第二章数据挖掘理论与技术1 3 2 3 7 聚类分析( c l u s t e r i n g ) 聚类与分类不同，在分类模块中，对于目标数据库中存在哪些类这一信息我 们是知道的，在那罩我们要做的就是将每一条记录分别属于哪一类标记出来；与 此相似但又不同的是，聚类是在预先不知道目标数据库到底有多少类的情况下， 希望将所有的纪录组成不同的类。在这种分类情况下，使得以某种度量为标准的 相似性在同一聚类之间最小化而在不同聚类之间最大化。事实上，聚类算法中有 一大类算法所采用的相似性都是基于距离的，而且由于现实数据库中数据类型的 多样性，关于如何度量两个含有非数值型字段的记录之间的距离的讨论有很多， 并提出了相应的算法。在很多应用中，由聚类分析得到的每一个聚类中的成员都 可以被统一看待。聚类分析的算法可以分为以下几大类：分裂法、层次法、基于 密度的方法、基于网格的方法和基于模型的方法等。 聚类分析作为数据挖掘中的一个模块，它既可以作为一个单独的工具以发现 数据库中数据分布的一些深入的信息，从而概括出每一类的特点，或者把注意力 放在某一个特定的类上以作进一步的分析；它又可以作为数据挖掘算法中其他分 析算法的一个预处理步骤。 2 4本章小结 本章论述了数据挖掘的一些基本概念，介绍了数据挖掘的国内外现状，以及 数据挖掘的应用，并且具体阐述了数据挖掘的步骤和其中用到的技术和方法。 第三章关联规则挖掘理论 1 5 第三章关联规则挖掘理论