（计算机应用技术专业论文）频繁项双向挖掘算法的研究与实现.pdf

摘要 数据挖掘是帮助人们在海量数据中发现信息和知识的工具。近年来数据挖掘技 术成了商业智能的核心技术，被广泛应用到了诸多领域，引起了学术界极大的关注， 如何提高数据挖掘的效率成为学术界热门的研究课题。 在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研究课题， 目前，关联规则挖掘在商业等领域得到了成功应用，使它成为了数据挖掘中最成熟、 最重要、最活跃的研究内容。关联规则侧重于确定数据中不同领域之间的联系，即 寻找给定数据集中的有趣联系。通过描述数据库中数据项之间所存在的潜在关系的 规则，找出满足给定支持度和置信度阀值的多个域之间的依赖关系。 r a g r a w a l 等人提出的a p r i o r i 算法是最著名的、最有影响的关联规则挖掘算 法，它按项目集从小到大的顺序寻找频繁项集。其核心技术为其它各类布尔关联规 则挖掘算法所广泛采用。a p r i o r i 算法已被广泛用于商业决策、银行贷款、金融保 险等领域。 但在实践中，人们也发现该方法是在挖掘长频繁项( 如1 0 0 个项目) 时，会遇到 非常耗时的巨大计算问题。并相继提出了一些优化算法，如基于划分的方法、基于 h a s h 的方法、基于采样的方法，目的在于减少候选集生成的规模和数量，提高算法 的使用效率。 自顶向下挖掘算法( t o p _ d o w n ) ，利用事务项目关联信息表、关键项目、项目约 简、投影数据库等新概念和投影、约简等新方法，在候选集生成过程中及时修剪重 复分支，使算法的实际效率大为提高，较好的解决了长频繁项的挖掘问题，通过计 算机实验和算法分析，证明了这种方法的有效性和完备性。但在实验中，我们也发 现，在支持度较大，频繁项长度较短时却是利用a p r i o r i 方法的有利时机。 本文提出了一种结合自顶向下和自底向上的双向挖掘算法，把t o p _ d o w n 算法 和a p r i o r i 算法结合起来使用。主挖掘方向是自顶向下挖掘策略，同时利用自底向 上方法生成的非频集来及时修剪候选集，减少候选集生成的规模和数量，有效的提 高了算法的实际效率，较好的解决了长、短频繁项的挖掘问题。 关键词自顶向下，自底向上，关联规则，项目约简，频繁项 a b s t r a c t d a t am i n i n gi sag o o dm e t h o dw h i c hc o u l dh e l pp e o p l et of i n dv a l u a b l e i n f o r m a t i o na n dk n o w l e d g ei nt h em a g n i t u d eo fd a t a i nr e c e n ty e a r s ，t h e t e c h n o l o g yo fd a t a _ m i n i n gh a sb e c o m et h ec o r eo f c o m m e r c i a li n t e l l i g e n c ea n d b e e nw i d e l ya p p l i e di nm a n yf i e l d s i th a sd r a wg r e a ta t t e n t i o ni nt h ea c a d e m i c c i r c l e h o wt oi m p r o v et h ee f f i c i e n c yo fd a t am i n i n gh a sb e e nt h ev e r yh o tt o p i ci n t h i sc i r c l e m i n i n ga s s o c i a t i o nr u l e si nt h et r a n s a c t i o nd a t a b a s ei st h ev e r yi m p o r t a n t t h e s i so fd a t am i n i n g n o w a d a y s 。m i n i n ga s s o c i a t i o nr u l e sh a sb e e ns u c c e s s f u l l yi n t h ec o m m e r c i a lf i e l d sa n db e c o m et h em o s tm a t u r e ，i m p o r t a n ta n da c t _ er e s e a r c h c o n t e n t m i n i n ga s s o c i a t i o nr u l e sp u tt h ee m p h a s i so nt h er e l a t i o n s h i po fc e r t a i n d a t ai nd i f f e r e n tf i e l d s ，t h a ti s ，i tf i n dt h ei n t r e s t i n gr e l a t i o n s h i pi nt h eg i v e nd a t as e t t h r o u g hd e s c r i b i n gt h er u l e so fp o t e n tr e l a t i o n s h i pe x i s t e di nt h ed a t ai t e m sf r o m d a t a b a s e ，i tf i n dt h ed e p e n d e n tr e l a t i o n s h i pi nm u l t i - f i e l d sw h i c hc o u l ds a t i s f yt h e g i v e ns u p p o r ta n d c o n f i d e n c e t h ea p r i o r ia l g o r i t h mp r o s e db yr a g r a w a l ，e t a l i st h em o s tf a m o u sa n d i n f l u e n t i a la l g o r i t h mo fm i n i n ga s s o c i a t i o nr u l e s i ts e a r c ht h ef r e q u e n ti t e m s e t f r o mt h es m a l li t e mt ol a r g eo n e a n dh a sb e c o m et h eb a s eo fh i b e r a c h y a l g o r i t h m sa n dt h em o s tc l a s s c i c a lh i b e r a c h ya l g o r i t h m t o d a y ii t sc o r ea l g o t i t h mi s w i d e l yu s e db y o t h e ra l g o t i t h m so fb o o l e a na s s o c i a t i o nr u l e s t h e a p r i o r i a l g o r i t h mi sw i d e l ya p p l i e dt ov a r i o u sf i e l d ss u c ha st r a d ed e c i s i o n _ m a k i n g ，b a n k e v a l u a t i n gc r e d i t ，f i n a n c ei n s u r a n c e ，e t c h o w e v e r , i np r a c t i c ei tw i l lc o m ea c r o s st i m e _ c o n s u m i n gh u g ec o m p u t i n g p r o b l e m si nm i n i n gl o n gp a t t e mf r e q u e n ti t e m s e t s ( e g 1 0 0i t e m s ) s o m e o p t i m i z a t i o n a la l g o r i t h m ss u c ha sp a r t i t i o n b a s e dm e t h o d ，h a s h _ b a s e dm e t h o d a n ds a m p l i n g b a s e dm e t h o d sa r ep m p o s e do n ea f t e ra n o t h e r t h e s ea l g o r i t h m s a i ma tr e d u c i n gt h es c a l ea n da m o u n to fc a n d i d a t es e t sa n di m p r o v i n gt h e p r a c t i c a le f f i c i e n c yo fa l g o r i t h m t h et o p _ d o w na l g o r i t h mo fm i n i n gf r e q u e n ti t e m s e t s ，w h i c ha d o p t ss o m e n e wc o n c e p t sa n dm e t h o ds u c ha st r a n s a c t i o na n di t e m s e ta s s o c i a t i o n i n f o r m a t i o nt a b l e s ，k e y _ i t e m sa n dr e d u c t i o ni t e m s ，p r o j e c t i o nd b ，e t c s oa st o i l p r u n et h ei t e r a t i v eb r a n c hi nt h ec a n d i d a t e _ g e n e r a t e dp r o c e s s ，a n d m a k et h e a l g o r i t h mm o r ee f f e c t i v e i ti sv e r ye f f e c t i v e ，e s p e c i a l l yw h e nb e i n gu s e dt om i n e l o n g i t e m s t h ev a l i d i t y o ft h i s a l g o r i t h m i s p r o v e dt h r o u g h t h e c o m p u t i n g e x p e r i e n ta n da n a l y s i so fc o m p u t i n gc o m p l e x i t y b u ti nt h ee x p e r i m e n ti ti sf o u n d t h a tw h e nt h em i n _ s u p p o ni si n c r e a s e d ，i ti ss u i t a b l ef o ru s i n gt h ea p r i o r i a l g o r i t h m t h i s p a p e rp r o p o s e dad o u b l e _ s e a r c ha l g o r i t h m w h i c hc o m b i n et h e t o p _ d o w na n db o t t o m _ u pm e t h o d s t h em a i nm i n i n gd i r e c t i o ni st h et o p _ d o w n ，b u t n o n _ f r e q u e n ti t e m sg e n e r a t e db yt h eb o t t o m u pm e t h o da r eu s e dt op r u n et h e c a n d i d a t es e t si nt i m e t h i sc o u l dr e d u c et h et h es c a l ea n da m o u n to fc a n d i d a t e s e t s ，e f f e c t i v e l yi m p r o v et h ep r a c t i c a le f f i c i e n c e o fa l g o r i t h m ，b e t t e rs o l v et h e p r o b l e mo fm i n i n gl o n ga n ds h o r if r e q u e n ti t e m s 。 z h a n gs o n g y u n ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g ” k e y w o r d st o p _ d o w n ，b o t t o m _ u p ，a s s o c i a t i o nr u l e ，i t e mr e d u c t i o n ，f r e q u e n t s i l l 论文独创性声明 本论文是我个人在导师悉心指导下进行的研究工作及取 得的成果。论文中除了加以标注和致谢的地方外，不包含其 他人或其他机构已经发表或撰写过的研究成果。其他同志对 本研究的启发和所作的贡献已在本论文中作了明确的声明并 表示了谢意和感激。 作者签名：拯扭簋日期：兰竺! ：! 垒：堡 论文使用授权声明 本人同意上海海事大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文复印件，允许论文被查阅和借阅； 学校可以上网公布论文的全部和部分内容，可以采用影印、 缩印或者其他复制手段保存论文。保密的论文在解密后遵守 此规定。 日期：坦业盟? 频繁项取向挖掘算法的研究与实现 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 ，k d d ) 及其 核心技术数据挖掘( d a t am i n i n g ，d m ) 便应运而生了，这里所指的“知识”就是数 据中隐含的信息。 数据挖掘技术是面向数据库系统建立的对大型数据库进行更为抽象的、深层次 的、二次开发的一项实用性很强的技术，同时数据挖掘也是一门很广义的交叉学科， 涉及到人工智能、统计学、机器学习、知识库系统、高性能计算和数据可视化等学 科领域。简单地说，数据挖掘就是从大量的数据中提取或“挖掘”出知识。一种比 较公认的技术定义是，数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、 模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是 潜在有用的信息和知识的过程。目前数据挖掘的研究己经和数据仓库( 或数据集市) 结合起来，数据仓库( 或数据集市) 的出现为数据挖掘技术提供了新的应用领域，也 对数据挖掘技术提供了有利的支撑。数据仓库( 或数据集市) 把传统数据库中大量 的历史数据重新提取，生成一个集中的、面向主题组织的、随时间变化的、内容相 对稳定的数据集合。数据仓库( 或数据集市) 完成了数据的收集、集成、存储、管理 等工作，为数据挖掘过程提供了规范的、海量的数据，使得数据挖掘能够能专注于 知识的发现。 数据挖掘的目标是从数据库中发现隐含的、有意义的知识，所发现的知识最常 见的有以下五类：广义知识( g e n e r a l i z a t i o n ) 、关联知识( a s s o c i a t i o n ) 、分类知识 ( c l a s s i f i c a t i o n & c l u s t e r i n g ) 、预测型知识( p r e d i c t i o n ) 和偏差型知识 ( d e v i a t i o n ) 。其中，数据关联是数据库中存在的一类重要的可被发现的知识。若两 个或多个变量的取值之间存在某种规律性，就称为关联。它反映一个事件和其他事 件之间依赖或关联的规律，如果两项或多项属性之间存在关联，那么其中一项的属 性值就可以依据其他属性值进行预测。关联可分为简单关联、时序关联和因果关联。 关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联 函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。 最为著名的关联规则发现方法是r a g r a w a 提出的a p r i o r i 算法。根据其思想， 关联规则的发现可分为两步：第一步是迭代识别所有的频繁项目集，要求频繁项目集 频繁项双向挖掘算法的研究与实现 的支持率不低于用户设定的最低值；第二步是从频繁项目集中构造可信度不低于用 户设定的最低值的规则。识别或发现所有频繁项目集是关联规则发现算法的核心， 也是计算量最大的部分。 目前，关联规则挖掘中的经典算法a p r i o r i 算法已被广泛用于商业决策、银 行贷款、金融保险等领域。该方法是一种自底向上的有效挖掘方法，但对于长频繁 项( 如l o o 个项目) ，该方法会遇到非常耗时的巨大计算问题。自顶向下挖掘算法 ( t o p _ d o w n ) 是一种优秀的长频繁项挖掘算法，它利用了事务项目关联信息表、关键 项目、项目约简、投影数据库等新概念和投影、约简等新方法，在候选集生成过程 中及时修剪重复分支，使算法的实际效率大为提高，较好的解决了长频繁项的挖掘 问题，通过计算机实验和算法分析，证明了这种方法的有效性和完备性。但在实验 中，我们也发现，在支持度较大，频繁项长度较短时却是利用a p r i o r i 方法的有利 时机。 本文提出了一种结合自顶向下和自底向上的双向挖掘算法( d o u b l e ，_search) 较好的解决了长、短频繁项的挖掘问题。主挖掘方向是是利用自顶向下挖掘策略， 但通过白底向上方法生成的非频集来及时修剪候选集，减少候选集生成的规模和数 量，有效的提高了算法的实际效率。 1 2 国内外研究现状综述 数据挖掘( d a t a mi n i n g ) 一词首次出现是在1 9 8 9 年8 月于美国底特律市举办的 第十一届国际联合人工智能学术会议上，到目前为止，该研讨会已经召开了八次， 研究重点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及 多种学科之间的相互渗透。目前，国外在数据挖掘领域中的研究内容十分广泛，取 得了明显的成果。 2 0 0 0 年7 月，i d c 发布了有关信息存取工具市场的报告。报告指出，1 9 9 9 年数据 挖掘市场大概约为7 5 亿美元。至u 2 0 0 2 年，该市场会发展到2 2 亿美元。据国外专家预 测，随着数据量的日益积累和计算机的广泛应用，在今后的5 至1 0 年内，数据挖掘将 在中国形成一个新型的产业。目前，许多数据挖掘工具原型己经开发出来，一些系 统已经投入商业化使用。比如i b m 公司的q u e s t 系统、加拿大s i m o nf r a s e r 大学开发 的d b m i n e r ，s a s 的s a se n t e r p r i s em i n e r 等等，它们无一例外都提供了在数据仓库 中进行数据挖掘的功能。 自从r a g r a w a l 等人提出关联规则的挖掘问题以后，诸多的研究人员对关联规 刚的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，提出各 种变体，对数据挖掘进行并行化，对关联规则的应用进行推广等等。现在，关联规 则的挖掘已经从单一概念层次关联规则的发现发展到多概念层次关联规则的发现， 并把研究的重点放在提高算法的效率和规模可收缩性上。到目前为止，其主要的研 究方向可归纳为如下6 个方面： 2 频繁项双向挖掘算法的研究与实现 ( 1 ) 多循环方式的挖掘算法 此类算法包括a g r a w a l 等人提出的a i s 1 ，a p r i o r i ，a p r i o r i t i d 和 a p r i o r i h y b r i d 3 ，p a r k 等人提出的d h p 5 3 ，s a v a s e r e 等人的p a r t i t i o n 7 以及 t o i v o n e n 提出的抽样算法s a m p l i n g 1 4 等。其中最有效和有影响的算法 为：a p r i o r i ，d h p ，p a r t i t i o n 。 ( 2 ) 并行挖掘算法 目前已经提出的并行挖掘关联规则的算法有：a g r a w a l 等人提出的c d ( c o u n t d i s t r i b u t i o n ) ，c a d ( c a n d i d a t ed i s t r i b u t i o n ) ，d d ( d a t ad i s t r i b u t i o n ) 4 ，p a r k 等人提出的p d m 6 1 ，c h u e n g 等人提出的基于分布式数据库的挖掘算法d m a 和f d m 。 ( 3 ) 挖掘一般或多层关联规则 挖掘一般或多层关联规则的成就主要有：h a n 等人的m l t 2 l 1 及其变种 m l t i l a ，m l t m l i ，m l t 2 l a 5 1 和r s r i k a n t 等人的c u m u l a t e ，s t r a t i f y 及其变种 e a t i m a t e ，e s t m c r g e 等。 ( 4 ) 挖掘多值属性关联规则 多值属性关联规则挖掘问题首先在文献e 1 1 中提出。目前提出的挖掘多值属性 关联规则的算法大多是将多值属性关联规则挖掘问题转化为布尔型关联规则挖掘问 题，即将多值属性的值划分为多个区间，每个区间算作一个属性，将类别属性的每 一个类别当作一个属性。 文 5 6 用“偏完整性度量( p a r t i a lc o m p l e t e n e s sm e a s u r e ) ”原则将数量属性 划分为相等的几个区段，当某一区段的支持数小于用户给定的最小支持数时，就将 其与领近的区段进行合并。为了使发现的关联规则更具有趣性，文中采用了“大于 期望的值( g r e a t e rt h a ne x p e c t e dv a l u e ) ”准则。 文 5 6 认为文 5 5 3 中的属性划分方法不能很好地表示数据的分布，尤其是属性 值分布不均匀的时候，于是提出了一个聚类算法，根据数据库中数据的分布情况决 定属性值如何划分区段，并可将相关的区段进行合并。在此基础上发现的多值关联 规则更具有效性和可理解性。 ( 5 ) 基于约束的关联规则挖掘 基于约束的关联规则挖掘的主要目的是发现更有趣的、更实用的和更特别的关 联规则，这方面的研究主要有 5 6 - 6 3 。文 6 3 研究了在提供布尔表达式约束情况 下的关联规则发现问题，并给出了三种不同的算法：m u l t i p l e j o i n s 、r e o r d e r 、 d i r e c t 。文 5 6 提出并分析了用户所给出的约束的两个对发现算法的剪枝步骤非常 重要的属性：反单调性( a n t i m o n o t o n i c i t y ) 和简洁性( s u c c i n c t n e s s ) s s ) ，提出了 一个高效的基于约束的关联规则挖掘算法c a p 。 另一种类型的基于约束的关联规则挖掘方法是元模式制导的关联规则挖掘算 法 6 0 6 2 ，这种类型的发现算法首先由用户给定要发现的关联规则的元模式或模 板，然后根据这些模板在数据库中发现与模板相适应的实际存在的关联规则。文 7 2 就是基于这种模式提出了两个相应的算法：大谓词增长算法( 1 a r g e 3 频繁项双向挖掘算法的研究与实现 p r e d i c t g r o w i n g ) 和直接p 一谓词测试算法( d i r e c t p r e d i c tt e s t i n g ) 。 ( 6 ) 其它方向 除了以上列举的比较常见的研究方向外，还有其他一些研究方向，比如：发现 关联规则的语言，挖掘长模式和密集数据集，挖掘相关性和因果关系，发现比例规 则，发现周期和日历关联规则，挖掘多维关联规则等等。 1 3 论文研究的主要内容及组织 本文采用一种双向挖掘策略。主挖掘方向是自顶向下搜索，结合信息系统约简， 直接把事务数据库的项目集作为候选项目集，寻找满足最小支持度的最大项目集。 如果当前的大项目不满足最小支持度要求，那么，去掉某影响支持度的关键项目， 形成新候选项目集，再判断该项目集是否满足给定的最小支持度，如不满足，再去 掉一个关键项目，直到找到频繁项。在搜索过程中，利用自顶向下挖掘方法， 把大数据库投影到小数据库上，利用约简项作为启发和约束信息，压缩频繁项搜索 空间；同时，利用自底向上方法及时修剪候选集，减少候选集的规模和数量，较好 的解决了长、短频繁项的挖掘问题。 1 4 小结 本章介绍了本论文的选题及其研究意义，分析了f ( d d 当前国内外的研究现状， 对论文的主要研究内容及组织作了介绍。 4 频繁项双向挖掘算法的研究与实现 第二章数据挖掘及关联规则技术 2 1 数据挖掘技术简介 2 1 1 数据挖掘的定义 数据挖掘的历史虽然较短，但从2 0 世纪9 0 年代以来，它的发展速度很快，加之 它是多学科综合的产物，迄今还没有一个完整的定义。目前对数据挖掘技术一种比 较公认的定义是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 s ) ，规律( r e g u l a r i t i e s ) 等形式。这种定义把数据挖掘的对象定义为数据库。 而更广义的说法是：数据挖掘意味着在一些事实或观察数据的集合中寻找模式 的决策支持过程。模式是一个用语言l 来表示的一个表达式e ，它可以用来描述数据 集合f 中数据的特性，e 所描述的数据是集合f 的一个子集f e ，e 作为一个模式要求它 比列举数据子集f e 中所有元素的描述方法简单。数据挖掘的对象不仅是数据库，也 可以是文件系统，或其它任何组织在一起的数据集合，例如w 唧信息资源。 目前发展的热点是数据挖掘技术和数据仓库技术的结合。数据仓库中包含了大 量历史数据，这些数据是经过了规范化并且面向主题组织的，对数据仓库中数据进 行数据挖掘是最容易的。 2 1 2 数据挖掘的分类及相关技术 数据挖掘是一个以数据库、人工智能、数理统计、可视化四大支柱技术为基础， 多学科交叉、渗透、融合形成的新的交叉学科，其研究内容十分广泛。由于数据挖 掘源于多个学科，因此数据挖掘研究就产生了大量的、各种不同类型数据挖掘方法， 为帮助用户区分数据挖掘系统，确定最适合其需要的数据挖掘系统，有必要对这些 方法进行一个清楚的分类。 一般的，描述或说明一个算法涉及三个部分：输入、输出和处理过程。数据挖 掘算法的输入是数据库，算法的输出是要发现的知识或模式，算法的处理过程则涉 及具体的搜索方法。从算法的输入、输出和处理过程三个角度分，可以确定这样几 种分类标准：挖掘对象、挖掘任务和挖掘方法。 根据挖掘对象分，有如下若干种数据库或数据源：关系数据库、面向对象数据 库、空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据库、历史( 1 e g a c y ) 数据库，以及万维网( w e b ) 。 频繁项双向挖掘算、法的研究与实现 根据挖掘方法分，可粗分为：统计方法、机器学习方法、神经网络方法和数据 库方法。统计方法可细分为：回归分析、判别分析、聚类分析、探索性分析等。机器 学习可细分为：归纳学习方法、基于范例学习、遗传算法等。神经网络方法可细分为： 前向神经网络、自组织神经网络等。数据库方法主要是多维数据分析或o l a p 方法， 另外还有面向属性的归纳方法。 根据挖掘任务分，数据挖掘主要发现以下五类知识： ( 1 ) 广义型知识( g e n e r a l i z a t i o n ) ：根据数据的微观特性发现其表征的、带有 普遍性的、较高层次概念的、中观或宏观的知识。 ( 2 ) 分类型知识( c l a s s i f i c a t i o n & c l u s t e r i n g ) ：反映同类事物共同性质的特征 型知识和不同事物之间差异型特征知识。用于反映数据的汇聚模式或根据对象的属 性区分其所属类别。 ( 3 ) 关联型知识( a s s o c i a t i o n ) ：反映一个事件和其它事件之间依赖或关联的知 识，又称依赖( d e p e n d e n c y ) 关系。这类知识可用于数据库中的归一化，查询优化等。 ( 4 ) 偏差型知识( d e v i a t i o n ) ：通过分析标准类以外的特例，数据聚类外的离群 值，实际观测值和系统预测值问的显著差别，来对差异和极端特例进行描述。 ( 5 ) 预测型知识( p r e d i c t i o n ) ：通过时间序列型数据，由历史的和当前的数据去 预测未来的情况。它实际上是一种以时间为关键属性的关联知识。 2 1 3 数据挖掘的实施过程 数据挖掘是一个多种专家合作的过程，也是一个在资金上和技术上高投入的过 程，这一过程要反复进行，并在反复过程中，不断地趋近事物的本质，不断地优化 问题的解决方案，数据挖掘过程一般可大体分为以下几个步骤： 1 、确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的 最后结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘丽数据挖掘 则带有盲目性，是不会成功的。 2 、数据准备 1 ) 数据的选择：搜索所有与业务对象有关的内部和外部数据信息，并从中选择 出适用于数据挖掘应用的数据。 2 ) 数据的预处理：研究数据的质量，为进一步的分析作准备，并确定将要进行 的挖掘操作的类型。 3 ) 数据的转换：将数据转换成一个分析模型。这个分析模型是针对挖掘算法建 立的，建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 3 、数据挖掘 对所得到的经过转换的数据进行挖掘。除了完善从选择合适的挖掘算法外，其 余一切工作都能自动地完成。 6 频繁项双向挖掘算法的研究与实现 4 、结果分析 解释并评估结果。其使用的分析方法一般应作数据挖掘操作而定，通常会用到 可视化技术。 5 、知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。以上的步骤不是一 次完成的，可能其中某些步骤或者全部要反复进行。如图2 1 描述了数据挖掘的基本 过程和主要步骤 图2 1 数据挖掘的基本过程和主要步骤 以上步骤，总的来说，应该根据不同的问题环境和应用层面来选择合适的方法， 并且灵活应用来解狭数据挖掘中遇到的难题。 2 1 4 数据挖掘的应用现状 目前，数据挖掘的应用领域包括以下八个方面，而每个领域又都有自己的应用 领域和应用背景。 ( 1 ) 金融：金融事务需要收集和处理大量的数据，通过对这些数据进行分析， 发现其数据模式及特征，然后可能发现某个客户、消费群体或组织的金融和商业兴 趣，也可观察金融市场的变化趋势。数据挖掘在金融领域的应用广泛，包括数据清 理、金融市场分析预测、帐户分类、信用评估等。 ( 2 ) 医疗保健：医疗保健业有大量的数据需要处理，但这个行业的数据由不同 的信息管理系统管理，数据以不同的格式保存，从总体看，数据是无组织的。在这 个行业中，数据挖掘的关键任务是进行数据清理、预测医疗保健的费用。例如g t e 实验室开发的k e f i r ，它能进行多维分析，用于分析g t e 的医疗保健数据，对比数据 和预测数据，在定量范围内解释偏差，生成超文本报表。 ( 3 ) 市场业：市场业应用数据挖掘技术进行市场定位、消费者分析、辅助制定 市场营销策略等。 ( 4 ) 零售业：零售业是最早运用数据挖掘技术的行业。目前，主要运用于销售 预测、库存需求、零售点的选择、价格分析等。 ( 5 ) 制造业：制造业应用数据挖掘技术进行零部件故障诊断、资源优化、生产 过程分析等。 7 频繁项双向挖掘算法的研究与实现 ( 6 ) 司法：数据挖掘也可应用于案件调查、诈骗检测、犯罪行为分析等方面， 这些都可以给司法工作带来巨大的利益。 ( 7 ) 工程和科学：在信息量极为庞大的天文、气象、生物技术等领域中，所获 得的大量实验和观察数据用靠传统的数据分析工具难以应付，因此对功能强大的智 能化自动分析工具要求迫切，这种需求推动了d m 技术在科学研究领域的应用发展， 目前己获得了一些重要的研究成果，例如：j e t p ro p u l s i o n 实验室利用决策树方法对 上百万天体数据进行分析，帮助天文学家发现了1 6 个星的星体，效果要比人工更快， 更准确。 ( 8 ) 保险业：对受险人员的分类将有助于确定适当的保险金额度。通过数据挖 掘可以得到对不同行业、不同年龄段、不同社会层次的人，他们的险金应该如何确 定。另外，还可进行险种关联分析，分析购买了某种保险的人是否又同时购买另一 种保险，也可预测什么样的顾客将会购买新险种。 2 2 关联规则的相关介绍 关联规则挖掘问题，最早是由a g r a w a l 等人在1 9 9 3 年于文献中 1 首次提出，现 在从事务数据库中发现关联规则己经发展成为数据挖掘领域中一个非常重要的研究 课题。 关联规则的挖掘问题可以形式化描述如下： 1 3 设i = i ，i ：，i 。) 是由m 个不同的项目组成的集合，其中i 。( k = l ，2 ，i n ) 是项目 集。给定一个事务数据库d ，其中每个事务t 是i 中一组项目的集合，即t i ，t 有一 个唯一的标识符t i d 。设a 是一个项集，且a c _ t 。 关联规则就是如下形式的逻辑蕴涵式：a j b ，其中a c i ，b c i ，且a n b = 刃。关 联规则a b 要成立，还必须具备如下两个重要的条件： 1 、支持度s ：p ( a u b ) ，即a 和b 这两个项集在事务集d 中同时出现的概率。 2 、置信度c ：p ( b a ) ，即在出现项集a 的事务集d 中，项集b 也同时出现的概率。 同时满足最小支持度闽值和最小置信度阀值的规则称为强规则。关联规则的挖 掘问题就是在事务数据库d 中找出满足用户给定的最小支持度m i n s u p 和最小置信度 m i n c o n f 的关联规则，也就是产生强规则的问题。 挖掘关联规则过程可以分解为以下两个子过程： 1 、找出存在于事务数据库中的所有频繁项集。项集x 的支持度s u p p o r t ( x ) 不小 于用户给定的最小支持度m i n s u p ，则称x 为频繁项集( f r e q u e n ti t e m s e t ) 。 2 、利用频繁项集生成关联规则。对于每个频繁项集a ，若b c a ，b 乃，且 s u p p o r t ( a ) s u p p o r t ( b ) 兰m i n c o n f ，则关联规则bj ( a b ) 。 第二个子问题比较容易，其生成算法可参见文献 3 。目前大多数研究集中在 第一个子问题上。所有的关联规则挖掘算法不论采用什么数据结构，其基本过程都 可以分为如下几个步骤： 频繁项双向挖掘算法的研究与实现 l 、 预处理与挖掘任务有关的数据。根据具体问题的要求对数据库进行相应的 操作，从而构成规格化的数据库d 。 2 、 针对d ，求出所有满足最小支持度的项集，即频繁项集。由于一般情况下 我们所面临的数据库都比较大，所以此步是算法的核心。 3 、生成满足最小置信度的规则，形成规则集r 。 4 、解释并输出r 。 本章在介绍数据挖掘的定义、分类及相关技术、应用现状的同时，也对其中的 关联规则作了初步介绍。 9 频繁项_ 双向挖掘算法的研究与实现 第三章a p tj o rj 算法及已有的改进 3 1 标准a p r i o r i 算法 3 1 1a p t i o r i 算法的思想 a g r a w a l 等人于1 9 9 4 年提出了一个挖掘顾客交易数据库中项目集间关联规则 的算法一a p r i o r i ，该关联规则在分类上属于单维、单层、布尔型关联规则。时至 今日，a p r i o r i 算法仍然是挖掘布尔型关联规则频繁项集最有影响的方法，这里所有 支持度大于最小支持度的项集被称为频繁项集。 a p r i o r i 算法核心是基于两阶段频繁项集的递推思想，使用一种称作逐层搜索 的迭代方法，k 一项集用于探索( k 十1 ) 一项集。首先，找出频繁卜项集的集合。该集合 记作l 。l 。用于找频繁2 一项集的集合l 。，而l 。用于找l 3 ，如此下去，直到不能找到频 繁k 一项集。找每个l 。需要一次数据库扫描。 为了提高算法的效率，m a n n i l a 等人引入了修剪技术来减小候选集c 。的大小，以 此压缩搜索空间。算法中引入的修剪策略基于这样一个性质：频繁项集的所有非空子 集都必须是频繁的。根据定义，如果项集i 不满足最小支持度阐值m i n s u p ，则i 不是频 繁的，即p ( i ) m i n s u p 。如果项a 添加到i 。则结果项集( r p l u a ) 不可能比i 更频繁出 现。因此，p ( i u a ) 也不是频繁的，1 1 1 1 p ( i u a ) m i n s u p 。该性质属于一种特殊的分 类，称作反单调( a n t i - m o n o t o n e ) ，意指如果一个集合不能通过测试，则它的所有超 集也都不能通过相同的测试。 l - , - 项集用于探索l k 项集，由连接和剪枝两个过程组成，下面分别介绍： 1 、连接步：为找h ，通过l k - l 与自己连接产生候选k 一项集的集合。该候选项集的 集合记作c 。设1 。和l ：是l k _ l 中的项集。记号1 。 j 表示l 。的第j 项，( 例如，l 。表示 1 的倒数第3 项) 。为方便计，假定事务或项集中的项按字典次序排序。执行连接k 。 j o i nl 。其中l k _ 1 的元素是可连接的，如果它们前( k 一2 ) 个项相同。即是l 。，的元素 1 。和1 ：是可连接的，如果( 1 ， 1 = l ： 1 ) ( 1 ， 2 = 1 。 2 ) ( 1 。 k 一2 = l 。f k - 2 ) a ( 1 。 k 1 y 在事务数据库d 中 的支持度( s u p p o r t ) 是事务数据库中包含x 和y 的事务数与所有事务数之比，记为 s u p p o r t ( x = y ) ，目 s u p p o r t ( x y ) = | x n y i i d l ，规则x = y 在事务数据库d 中的可 信度( c o n f i d e n c e ) 是指包含x 和y 的事务数与包含x 的事务数之比，记为 1 4 频繁项双向挖掘算法的研究与实现 c o n f i d e n c e ( x y ) ，即：c o n f i d e n c e ( x = y ) = | x n y i i x f ，给定一个事务数据库d 。 挖掘关联规则就是产生支持度和可信度分别大于用户给定最小支持度和最小可信度 的关联规则。 需要注意的是： 1 、这里，x ，y 是事务的集合而不是商品集，所以一般x n y a 。 2 、因为x ，y 本身又代表具体的商品，是一种或几种商品构成的符号串，x s p y 不重复。例如，x = x l x 2 代表标识符为x 。，x 。的两种商品，从集合上说是x 又是x ，x 。两 个事务集的并集。 比较关于支持度和信任度定义和本节定义不难发现，虽然表面上看两种定义不 一样，但从定义的含义( 逻辑结果) 上看，其本质是一样的。两种定义的主要差别在 于支持度、信任度的计算过程，比如支持度计算，在前者包含x 和y 的事务数的统计 是按集合的定义计算的，在后者包含x 和y 的事务数是以两个集合的交集形式给出来 的，但最终结果完全一样。 4 2 关联知识和分类知识挖掘方法的结合 当信任度改用集合形式表示后，比较r o u g hs e t s o ”关于精度( a c c u r a c ym e a s u r e ) 的定义，不难发现两者竟是那么一致。在r o u g hs e t s 中，给定等价关系r 和非空集合 x ，则x 的精度为：h 。( x ) = iu y e u r ：y c _ x ) l fu y e u r ：y n x g ) i ，其中，u