（计算机应用技术专业论文）基于无向图的关联规则算法的研究与应用.pdf

摘要 摘要 近年来，数据挖掘( d a t am i n i n g ，简称d m ) 技术的发展已经引起了信息产业界的广 泛关注，这是快速增长的数据量和日益贫乏的信息量之间矛盾运动的必然结果。对数据 挖掘技术进行深入细致的研究是全球信息化发展的客观要求。 数据挖掘是数据库中知识发现( 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 ) 的核 心步骤，是指从大型的数据库中发现潜在的、新颖的、有价值的、可用的、能被用户理 解的模式和信息的过程。关联规则挖掘是数据挖掘的一个重要研究领域，有着极其重要 的应用价值。关联规则挖掘的目的是寻找在大量的数据项中隐藏着的联系或者相关性， 既数据库中的知识模式。 本文在广泛阅读了国内外文献的基础之上，提出了一种新的基于无向图的关联规则 最大频繁项集挖掘算法以及对挖掘出的关联规则进行聚类的研究。本文的创新点主要有 以下两个方面： ( 1 ) 为了挖掘事务数据库中局部关联性比较强的频繁项集，提出基于无向图的关联 规则最大频繁项集挖掘算法。首先将事务数据库由横向转为纵向，将其保存到一个邻接 矩阵中，其中边的权值表示任意二项集的支持度。然后，基于边的权值将整个无项完全 图拆分成若干完全子图。最后采用自底向上和自顶向下两种策略来挖掘频繁项集，根据 不同的最小支持度阀值比较两种策略的效率。实验结果表明，在支持度阀值比较低的时 候，本文提出的挖掘算法效率非常高。 ( 2 ) 为了从大量的规则中识别出有用的信息，必须对规则进行处理，删除冗余的规 则或对规则进行聚类或二者同时进行。本文提出一种改进的规则之间的距离定义方法， 基于此定义对关联规则进行聚类。首先确定项与项之间的距离，然后依据项与项的距离 得出规则之间的距离，最后基于此距离结合d b s c a n 算法的思想对关联规则进行聚类。分 析了聚类结果的合理性，并准确发现了孤立规则。 针对本文提出的算法编写程序，对来源于u c i 数据源的数据集进行验证，实验结果 表明算法是高效的和实用的。 关键词：数据挖掘；关联规则；频繁项集；无向图；聚类 大连交通大学工学硕十学何论文 a b s t r a c t i nr e c e n ty e a r s t h ed e v e l o p i n go fd a t am i n i n gt e c h n i q u e sh a sb e e np a i dw i d e l ya t t e n t i o n b yi n f o r m a t i o ni n d u s t r i e s w h i c hi st h en e c e s s a r yr e s u l to ft h ec o n f l i c t i n gm o v e m e n tb e t w e e n t h er a p i d i n c r e a s i n gd a t aa n dt h el a c k i n go fi n f o r m a t i o ni n c r e a s i n g l y d e e pr e s e a r c h i n go ft h e d a t a m i n i n gt e c h n i q u e s i sa no b j e c t i v er e q u i r e m e n ti nt h e d e v e l o p i n go ft h eg l o b a l i n f o r m a t i o n d a t am i n i n g ，t h ek e ys t e po fk 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 ，i st h ep r o c e s so f d i s c o v e r i n gi m p l i c i t ，n o n t r i v i a l ，p e r v i o u su n k n o w na n dp o t e n t i a l l yu s e f u li n f o r m a t i o nf r o m d a t a b a s e s a s s o c i a t i o nr u l e sm i n i n gi s 觚i m p o r t a n tf i e l di nd a t am i n i n ga n dh a si m p o r t a n t a p p l i c a t i o n si nd a t a b a s e s u c c e s s f u la p p l i c a t i o n so fa s s o c i a t i o nr u l e sm i n i n gh a v e b e e n d e m o n s t r a t e di nm a r k e t i n g ，b u s i n e s s ，m e d i c a la n a l y s i s ，p r o d u c tc o n t r o l ，e n g i n e e r i n gd e s i g n a n ds c i e n t i f i ce x p l o r a t i o n t h em a i np u r p o s eo fm i n i n ga s s o c i a t i o nr u l e si st of i n dt h e c o n n e c t i o n so rc o r r e l a t i o n sh i d d e ni ne n o r m o u si t e m sw h i c ha r ea l s o c a l l e dk n o w l e d g e p a u e m si nd a t a b a s e an e wa l g o r i t h mb a s e do nu n d i r e c t e dg r a p hi sp r o p o s e di nt h i sp a p e r w h i c hi st of i n dt h e m a x i m a lf r e q u e n ti t e m s e t si nt r a n s a c t i o nd a t a b a s e a n ds t u d y i n gc l u s t e r i n gm e t h o db a s e do n t h eg e n e r a t e da s s o c i a t i o nr u l e s t h ei n n o v a t i o n so ft h i sp a p e ra r ea sf o l l o w s ： ( 1 ) an e wa s s o c i a t i o nr u l e sa l g o r i t h mb a s e do nu n d i r e c t e dg r a p hi sp r o p o s e df o r d i s c o v e r i n gm a x i m a lf r e q u e n ti t e m s e t st of i n dl o c a l l ys t r o n g l yc o r r e l a t e df r e q u e n ti t e m s e t si n t r a n s a c t i o nd a t a b a s e f i r s t l y w et r a n s f o r mh o r i z o n t a lt r a n s a c t i o nd a t a b a s ei n t oav e r t i c a lo n e a n dt h e ns a v ei tt oa na d j a c e n tm a t r i xi nw h i c ht h ew e i g h to fe d g e sd e n o t e ss u p p o r to f 2 i t m s e t s e c o n d l y t h ew h o l eu n d i r e c t e dc o m p l e t eg r a p hi sd i v i d e di n t os e v e r a lc o m p l e t e s u b g r a p h sb a s e do nt h ew e i g h t f i n a l l y ，t h eu p d o w na n dt h eb o t t o m u ps t r a t e g i e sa r eu s e dt o f i n df r e q u e n ti t e m s e t sa n dc o m p a r ee f ：f i c i e n c yo ft h et w os t r a t e g i e sa c c o r d i n gt od i f f e r e n t m i n s u p p o r t e x p e r i m e n t ss h o wt h a tt h en e wa s s o c i a t i o nr u l e sa l g o r i t h mh a st h eg r e a t e s t e f f i c i e n c yw h e nt h em i n s u p p o r ti sl o w ( 2 ) a l la s s o c i a t i o nr u l e sm u s tb ep r u n e do rg r o u p e da n db o t ho ft h e mi no r d e rt oi d e n t i f y v a l u a b l ei n f o r m a t i o nf r o ml a r g eq u a n t i t i e so fd i s c o v e r e da s s o c i a t i o nr u l e s a ni m p r o v e d d i s t a n c em e t r i cm e t h o db e t w e e nr u l e si sp r e s e n t e da n dc l u s t e r i n gt h e s er u l e sb a s e do nt h en e w d i s t a n c e f i r s t ，c o m p u t i n gd i s t a n c eb e t w e e ni t e m s s e c o n d ，c o m p u t i n gd i s t a n c eb e t w e e nr u l e s l a s t ad e n s i t y b a s e dc l u s t e r i n ga l g o r i t h md b s c a ni su s e dt oc l u s t e rt h e s er u l e s t h er e s u l t s a r ed i s c u s s e da n dd i s c o v e r e do u t l i e r sa c c u r a t e l y e x p e r i m e n t sb a s e do nu c id a t a b a s e ss h o wt h a tt h en e wa s s o c i a t i o nr u l e sa l g o r i t h ma n d t h ei m p r o v e dd i s t a n c em e t h o da r eo fg r e a te 衔c i e n c ya n dp r a c t i c a b i l i t y k e yw 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 s ；f r e q u e n tl t e m s e t ；u n d i r e c t e dg r a p h ； c l u s t e r i n g 绪论 绪论 课题背景 我们的生活进入了一个网络化的时代，通信、计算机和网络技术正在改变人们的思 维方式和生活方式。在这些技术的推动下，人们产生和收集数据的能力在迅速地提高。 随着时间的推移，大量的原始数据被不断积累，随之而来产生一些新的问题：诸如信息 量巨大，难以处理消化；信息真假难以分辨；信息安全难以保障；信息的形式不一致， 难以统一处理等等。如何理解已有的历史数据并用于预测未来，如何从这些海量数据中 发现有用的信息，如何变被动的数据为主动的知识，如何快速、准确地获取有价值的信 息，指导企业决策，使企业利益最大化等，都迫使人们去寻找新的、更为有效的数据挖 掘手段对各种“数据宝藏 进行有效的挖掘，发现潜在的、有价值的信息。 数据挖掘( d a t am i n i n g ) 作为- f l 新兴的信息自动提取技术，正是在这种背景下产生。 它的出现为从大量的数据中智能地、自动地提取出有价值的信息和知识提供了有效的手 段。数据挖掘在其诞生后的十几年里得到了飞速的发展，数据挖掘的研究领域涉及机器 学习、数据库、模式识别、统计学、人工智能、管理信息系统、知识获取、数据可视化 等许多领域。数据挖掘的主要任务是发现隐藏在数据中的模式，包括：分类模式、聚类 模式、回归模式、关联模式、序列模式和偏差模式等。数据挖掘的常用方法有：模糊方 法、粗糙集理论、云理论、证据理论、人工神经网络、遗传算法和归纳学习等。 数据挖掘技术具有广泛的应用前景，因为数据挖掘产生的知识可以用于决策支持、 信息管理、生物制药等许多领域。p a r s a g e i l l 把决策支持空间从应用层上分成了数据空间 ( d a t as p a c e ) 、聚合空间( a g g r e g a t i o ns p a c e ) 、影响空间( i n f l u e n c es p a c e ) 和变化空间 ( v a r i a t i o ns p a c e ) 4 个子空间。在决策支持空间中数据空间是用于处理基于关键字的决策 查询，最典型的是联机事务处理( o l t p ) ；而对数据空间中的数据元素进行聚合运算( 如 s l i m ，a v e r a g e ，m a x ，m i n 等) 所形成的空间就是聚合空间，它主要用于联机分析处理 ( o l a p ) ；影响空间则用于处理逻辑性质的决策问题，比如回答“是什么原因影响了企业 的利润率? ”这样的问题，这些信息是通过数据挖掘得到的；变化空间用于处理某种变 化过程的速度问题。数据挖掘正是处于以上四个空间中的影响空间。 1 9 8 9 年8 月在美国底特律召开的第1 l 届国际人工智能会议上首先出现 k d d ( 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 ) 这个术语，随后引起了国际人工智能领域和数据 库领域专家的广泛关注。1 9 9 5 年在加拿大蒙特利尔召开了首届k d d & d a t am i n i n g 国际 学术会议，在此以后k d d & d a t am i n i n g 国际学术会议每年召开一次。经过1 0 多年的 努力，数据挖掘技术的研究已经取得了丰硕的成果，不少软件公司已开发出数据挖掘的 大连交通大学工学硕十学位论文 软件产品，并在北美、欧洲等国家得到应用。例如，i b m 公司开发的q u e s t 和i n t e l l i g e n t m i n e r ；a n g o s ss o f t w a r e 公司开发的基于规则和决策树的k n o w l e d g es e e k e r ；加拿大 s i m o nf r a s e r 大学开发的d b m i n e r ；a d v a n c e ds o f t w a r ea p p l i c a t i o n 公司开发的基于人工 神经网络的d b p r o f i l e ；s g i 公司开发的m i n e s e t ：新西兰w a i k a t o 大学开发的w e k a 等。 在我国数据挖掘技术的研究也引起了学术界和i t 界的广泛关注，已经成为信息科学界 的热点研究领域。 然而，目前的数据挖掘技术的研究还很不成熟，其应用还有较大的局限性，正是这 些局限性，促进数据挖掘研究进一步向前发展。下面列出了数据挖掘研究和应用所面临 的主要挑战： ( 1 ) 数据挖掘的性能问题。为了能够及时有效地从数据库大量的数据中抽取有价值 的模式知识，数据挖掘算法必须是高效和可扩展的。也就是说，一个数据挖掘算法在大 型数据库中的运行时间必须是可以预计和接受的。 ( 2 ) 多种形式的输入数据。目前数据挖掘工具能处理的数据形式有限。一般可以处 理数值型的结构化数据，但对于文本、图形、数学公式、图像或网络资源等这些半结构 或非结构的数据形式就变得无能为力。而且数据本身还伴随着缺损或噪声问题，特别是 在商业数据库中，对于这些数据，目前的挖掘工具不能有效处理。 ( 3 ) 用户参与和领域知识。有效的决策过程往往需要多次交互和多次反复，目前的 数据挖掘系统或工具很少能真正做到让用户参与到挖掘过程中。有用户的背景知识作指 导可以加快挖掘过程，并且保证所发现知识的有效性。将相关的领域知识融入数据挖掘 系统中是一个重要但至今还没有得到很好解决的问题。 ( 4 ) 知识的维护和更新。新数据的不断累积可能导致以前的知识失效，这些知识需 要动态维护和及时更新。目前研究采用增量更新的方法来维护已有的知识，例如 d w c h e u n g 等提出的维护关联规则的增量算法。 ( 5 ) 知识的表达和解释机制。在许多应用中，使用户能够理解所发现的知识是一个 重要问题，这要求知识的表达不能局限于数字或符号，而是用户更容易理解的描述形式， 比如图形、自然语言或可视化技术等。 ( 6 ) 隐私保护问题。新的数据挖掘技术的不断出现增加了隐私泄漏的风险，严重威 胁到人们的个人信息安全。为了使一个挖掘系统更安全，我们必须保证私人的敏感信息 已经被剪除出去，而且必须确保由其他数据推断出敏感数据的渠道也已经被堵塞。换句 话说，不仅数据本身，而且在数据中隐藏的知识都应该确保安全。 另外，数据挖掘系统和其他决策支持系统的有机集成也是一个挑战，特别是与一些 用户已经熟悉的系统相结合，这对于挖掘系统充分发挥作用是非常重要的。 绪论 关联规则 关联规贝j j ( a s s o c i a t i o nr u l e s ) 是数据挖掘的一个重要研究方向。关联规则挖掘最初的 形式是零售商的货篮分析，货篮分析是通过发现顾客放入货篮中的不同商品、即不同项 之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，分析商 品之间的关联，这种关联的发现可以帮助零售商制定营销策略。 r a 伊a w a l 【2 j 等人于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则问 题，其核心方法是基于频集理论的递推方法。此后人们对关联规则的挖掘问题进行了大 量研究，包括对a p d o r i 算法优化、多层次关联规则算法、多值属性关联规则算法和其 他关联规则算法等，以提高算法挖掘规则的效率。其基本原理描述为：设i = f 1 ，之，) 是坍个不同的项目组成的集合，给定一个事务数据库d ，其中的每一个事务丁是，中 一组项目的集合，即tci ，t 有一个唯一的标识符t i d 。若项集xc1 且xct ，则 事务集丁包含项集兄一条关联规则就是形如xjy 的蕴涵式，其中xci ，yc1 ， x 厂、y = a 。 关联规则挖掘的任务是在事务数据库d 中找出满足用户给定的最小支持度m i n s u p 阀值和最小置信度m i n c o n f 阀值以及用户感兴趣的、有用的关联规则。因此挖掘关联规 则时主要解决下面两个问题： 首先是算法的复杂性，目前大多数关联规则挖掘算法都是为解决这个问题而提出来 的。通常，算法从两个方面来考虑如何提高算法的效率：( 1 ) 减少i o 操作。关联规则 挖掘的数据库的规模有时可达g b 甚至t b 数量级，频繁的i o 操作势必会影响关联规 则的挖掘效率。减少扫描数据库d 的次数可以减少i o 操作，提高效率；( 2 ) 降低需要 计算支持度的候选项集的数量，使其与频繁项集的数量相接近，候选项集数量的减少可 以节省处理候选项所需要的计算时间和存储空间。 其次是必须从产生的规则集中选择用户感兴趣的和有用的规则。最小支持度和最小 置信度并不能确保挖掘出来的关联规则都是用户感兴趣的，其中可能包含许多冗余的、 无意义的规则，而且支持度和置信度高的关联规则又可能是常识性的知识，并不能称之 为信息。因此，制定好关联规则兴趣度衡量标准可以使挖掘出来的关联规则更能满足用 户的需求。 通过对关联规则的研究可以发现数据库中项集( 属性集) 间的一定的内在联系，有效 地提高了应用系统的决策支持能力，对市场策略、商业经营、目标设计、仓储规划等有 很大的现实意义。 大连交通大学工学硕十学位论文 聚类分析 聚类是数据挖掘领域最为常见的技术之一，用于发现数据库中的对象类。这种对象 划分的依据是“物以类聚”，即考察个体或数据对象间的相似性，将满足相似性条件的 个体或数据对象划分一组内，不满足相似条件的个体或数据对象划分在不同的组。通过 聚类过程形成的每一组称为一个类( c l u s t e r ) 。在数据挖掘之前，对象类划分的数量与 类型均是未知的，因此在数据挖掘之后一般需要对数据挖掘的结果进行合理的分析与解 释。 聚类是现实世界中普遍存在的现象，其应用也非常广泛。例如：在商务中，聚类能 够帮助市场分析人员从客户基本库中发现不同的客户群体。在生物学中，聚类能用于推 导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。在模式识别中， 可以用于语音识别、字符识别、雷达信号识别、文本识别等方面。聚类分析方法还可以 应用于机器自动化和工具状态检测，以及进行气候分类、食品检验和水质分析。在图像 处理、模糊控制等领域也取得了丰硕成果。同时，随着聚类分析理论的不断发展，混合 型聚类分析的理论和应用提上了日程。这一方面要求寻求综合型的聚类方法来实现聚类 问题，另一方面，也要求知识发现、文本聚类等新知识的引入。 通常聚类分析算法可以划分为以下几类： ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) 划分方法是一种基于原型( p r o t o t y p e ) 的聚类方法，其本质是首先从数据集中随机 地选择几个对象作为聚类的原型，然后将其他对象分别分配到由原型所代表的最相似， 也就是距离最近的类中。划分方法通过迭代控制策略对原型不断地进行调整，从而使整 个聚类得到优化。 根据所采用的原型的不同，划分方法主要包括k m e a n s p l 和k m e d o i d 两大类算法。 k - m e a n s 算法的思路。假设有刀个对象需要分成k 类，首先随机地选择阶对象代 表阶类，每一个对象作为一个类的原型，根据距离原型最近的原则将其他对象分配到 各个类中。在完成首次对象的分配之后，以每一个类所有对象的平均值作为该类新的原 型，迭代进行对象的再分配，直到没有变化为止，从而得到最终的七爪类。 4 绪论 k - m e d o i d 算法的思路。首先选择阶“m e d i a n ”作为各个类的原型，再根据距离 原型最近的原则将其他对象分配到各个类。比较著名的k - m e d o id 算法有p a m 4 l ( p a r t i t i o n i n ga r o u n dm e d o i d s ) 算法、c l a r a l 4 1 ( c l u s t e f i n gl a r g ea p p l i c a t i o n s ) 算法和c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o n sb a s e do nr a n d o m i z e ds e a r c h ) 1 5 1 算法。 总体来说，在聚类的形状为凸形、大小和密度相似，并且聚类的数目可以合理估计 的前提下，上述划分方法都是比较有效的，能够形成比较好的聚类划分。 ( 2 ) 层次方法( h i e r a r c h i c a lm e t h o d ) 层次聚类方法是采用“自顶向下”或“自底向上”两种策略在不同的层次上对对象 进行分组，形成一种树形的聚类结构。如果采用“自顶向下 的方法，则称为分解型层 次聚类法；如果采用“自底向上 的方法，则称为聚结型层次聚类法。 层次方法同划分方法的不同之处在于：对于划分方法而言，一般需要一种迭代控制 策略，使得整个聚类得到优化；而层次方法并不是试图寻找最佳的聚类结果，而是按照 一定的相似性判断标准，合并最相似的部分，或者分割最不相似的两部分。比较传统的 层次聚类算法有：a g n e s ( a g l o m e r a t i v en e s t i n g ) 1 4 1 算法和d i a n a ( d i v i s i v ea n a l y s i s ) 4 】 算法，分别是聚结型层次聚类算法和分解型层次聚类算法。近年来出现的一些新的属于 层次聚类方法的聚类算法，一般采用的是聚结型层次聚类策略，如b i r c h ( b a l a n c e d i t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) t 6 1 算法、c u r e ( c l u s t e r i n gu s i n g r e p r - e s e n t i t i v e s ) l t l 算、r o c k l 8 l 算法和c h a m e l e o n1 9 】算法。 层次方法的不足之处在于，一旦一个步骤( 聚结或分解) 完成，它就不能被撤消。这 个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较小。但是，该 技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果： 在每层划分中，仔细分析对象间的“联接”；综合层次凝聚和迭代的重定位方法。 首先用自底向上的层次算法，然后用迭代的重定位来改进结果。 ( 3 ) 基于密度的方法( d e n s it y - b a s e dm e t h o d ) 基于密度的方法是以局部数据特征作为聚类的判断标准，类被看作是一个数据区 域，在该区域内对象是密集的，对象稀疏的区域将各个类分割开来。多数基于密度的聚 类算法形成的聚类形状是任意的，并且一个类中对象的分布也是任意的。 大连交通大学工学硕十学位论文 基于密度的聚类方法研究是非常活跃的一个领域，近年来提出了许多新的算法，例 如：19 9 6 年提出的d b s c a n ( d e n s i t y b a s e ds p a t i a lc l u s t e r i n go f a p p l i c a t i o nw i t hn o i s e ) 0 0 】 算法、19 9 8 年提出的w a v e c l u s t e r l l l j 算法、d e n c l u e ( d e n s i t y b a s e dc l u s t e r i n g ) 1 1 2 1 算法 和1 9 9 9 年提出的o p t i c s ( o r d e r i n gp o i n t st oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) d 3 l 算法等。 ( 4 ) 基于网格的方法( g r i d - b a s e dm e t h o d ) 基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的 聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要优点是它的处理速 度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) 基于模型的方法为每个聚类假定了一个模型，寻找数据对给定模型的最佳拟合。一 个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于 标准的统计数据自动确定聚类数目，考虑“噪声 数据或孤立点，从而产生健壮的聚类 方法。 一些聚类算法集成了多种聚类方法的思想，所以有时将某个给定的算法划分为属于 某种聚类方法是困难的。此外，某些应用可能有特定的聚类标准要求综合多种聚类技术。 课题来源 关联规则挖掘是数据挖掘技术中非常重要和应用前景广阔的一种技术。由于关联规 则发现潜在的商业价值和学术价值，所以近年来它一直是数据挖掘研究和应用领域活跃 的f j 沿。虽然关联规则挖掘问题的提出不过只是十几年的时间，但在算法的研究上已经 积累的大量的成果。同时应当看到，数据库的规模仍然在不断膨胀，对进一步提高挖掘 算法效率的要求仍然十分紧迫。特别是在发现频繁集这一步上，由于它是整个流程最耗 时间和空间的环节，是关联规则挖掘的瓶颈。而且根据已有的关联规则算法会挖掘出大 量的规则，其中有很大一部分是无法理解的。为了使规则便于理解，有很多人提出对规 则进行约简，删除冗余的规则或者对规则进行聚类，或者二者同时进行。但是目前的约 简算法尚不能达到很好的效果，有待于进一步改进。 本课题就是在这样的背景下产生，着眼于现有算法的不足和缺陷进行改进，旨在进 一步提高关联规则的挖掘效率，使挖掘出的规则便于理解。 6 绪论 本文所做的工作及创新点 本文的研究工作源于上述背景，目的是对数据挖掘技术进行深入研究，主要探讨数 据挖掘中的关联规则挖掘问题，具体如下： ( 1 ) 论述了关联规则挖掘算法的理论，重点介绍了基于频繁项的关联规则挖掘算法， 并对一些经典算法进行了分析和评价。 ( 2 ) 为了挖掘事务数据库中局部关联性比较强的频繁项集，提出基于无向图的关联 规则的算法挖掘最大频繁项集。首先将事务数据库由横向转为纵向，将其保存到一个邻 接矩阵中，其中边的权值表示任意二项集的支持度。然后，基于边的权值将整个无向完 全图拆分成若干完全子图。最后分析“自底向上 和“自顶向下”两种策略来挖掘最大 频繁项集，根据不同的最小支持度阀值比较两种策略的效率。 ( 3 ) 为了从大量的规则中识别出有用的信息，必须对规则进行处理，删除冗余的规 则或对规则进行聚类或二者同时进行。提出一种改进的规则之间的距离定义方法，基于 此定义对关联规则进行聚类。首先确定项与项之间的距离，然后依据项与项的距离得出 规则之间的距离，最后选用适当的聚类算法对关联规则进行聚类，评价聚类结果。 ( 4 ) 实现了友好的用户界面与可视化的数据挖掘算法平台，方便用户了解挖掘过程， 将数据挖掘算法平台应用于零售业进行关联规则挖掘。 本文的组织结构 本文对关联规则的挖掘算法进行了深入而全面的研究，主要内容包括： 第一章，讲述了关联规则的基本概念，论述了与本文相关的研究工作，并详细分析 了多种经典关联规则算法。 第二章，是本文的重点，提出基于无向图的关联规则挖掘算法，分析了两种策略来 挖掘最大频繁项集，根据不同的最小支持度比较两种策略的挖掘效率。 第三章，提出一种改进的规则之间的距离定义方法，基于此定义对已经挖掘出的关 联规则进行聚类，并评价聚类结果。 第四章，实现了友好的用户界面与可视化的数据挖掘算法平台，便于用户了解关联 规则的挖掘过程。 第五章，将数据挖掘算法平台应用于超市数据集进行数据挖掘，分析评价挖掘结果。 总结全文。 7 大连交通大学工学硕十学位论文 第一章关联规则概述 关联规则是指大量数据中项集之间存在的有趣的关系或相互联系。关联规则挖掘是 数据挖掘研究的一个重要分支，关联规则挖掘的目的是寻找在大量的数据项中隐藏着的 联系或者相关性，即数据库中的知识模式，发现隐藏的规律。关联规则是由r a g r a w a l 等人首先提出的，它的一个典型实例就是：“9 0 的顾客在购买面包的同时也会购买牛 奶 ，其直观意义为顾客在购买某些商品的时候有多大倾向会购买另外一些商品。 1 1 关联规则的基本概念和问题描述 设i = ，f 2 ，) 是所有项的集合，其中i 。( k = 1 ，2 ，m ) 称为项。项的集合称为项集， 包含k 个项的项集称为肛项集。一个事务t ( t r a n s a c t i o n ) 是一个项集，它是，的一个子集， 每个事务丁有一个唯一标识符t d 。不同的事务组成事务集d ，它构成了发现关联规则 的事务数据库。如果项集x 丁，则称事务丁支持项集工也称事务丁包含项集兄关 联规则是如下形式的一种蕴含形式：xjy ，其中xci ，yci ，且xny = o 。 支持度( s u p p o r t ) ：设事务集d 中有s 的事务同时支持项集x 和y ，s 称为关联规 则x y 的支持度。支持度描述了x 和】，这两个项集的并集x u y 在所有事务中出现的 概率。用数学公式来描述，项集x 在d 中的支持度定义为： s u p p o r t ( x )：删堡絮掣 ( 1 1 ) lui 关联规则的支持度定义为： s u p p o r t ( x j ：! ! 三! 三! 望! 竺垡! 茎! ! 羔三三! ! ( 1 2 ) ld = s u p p o r t ( x u n 置信度( c o n a q d e n c e ) ：设事务集d 中支持项集x 的事务中，有揣的事务同时也支持 项集y ，c 称为关联规则x y 的置信度。换句话说，置信度就是指在出现项集x 的 事务丁中，项集】，也同时出现的概率有多大。关联规则x y 的置信度定义为： c o n f i d e n c e ( x ： y ) = r l t d a n d ( x u y ) t ) i i 丁it da n dx t i s u p p o r t ( xuy ) s u p p o r t ( x ) ( 1 3 ) 给定一个事务集d ，关联规则挖掘问题就是产生支持度和置信度分别大于用户定义 的最小支持度( 脚f 淞印) 和最小置信度( m i n c o 奶的关联规则。这种满足最小支持度和最小 置信度的关联规则，我们称之为强关联规则。 关联规则概述 1 2 关联规则的分类 我们将关联规则按不同的标准进行分类： ( 1 ) 基于规则中处理变量的类型，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系； 而数值型关联规则处理的是量化值，可以和多维关联规则或多层关联规则结合起来，对 数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数 值型关联规则中也可以包含种类变量。 例如：性别= “女j 职业= “护士”，是布尔型关联规则：性别= “女a v g ( 收 入) = 2 5 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次 的：而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：联想台式机j h p 打印机，是一个细节数据上的单层关联规则；台式机= h p 打印机，是一个较高层次和细节层次之间的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的各种商品；而在 多维的关联规则中，要处理的数据将会涉及多个维。换话说，单维关联规则是处理单个 属性中的一些关系：多维关联规则是处理各个属性之间的某些关系。 例如：啤酒j 尿布，这条规则只涉及到用户的购买的物品；性别= “女”职业 = “护士，这条规则就涉及到两个属性信息，是在两个维上的一条关联规则。 给出了关联规则的分类之后，在关联规则实际应用中，我们就可以考虑某个具体的 方法适用于哪一类规则的挖掘，某类规则又可以用哪些不同的方法进行处理。 1 3 关联规则挖掘算法 1 3 1 经典频繁集方法 r a g r a w a l 等人于1 9 9 3 年首次提出挖掘顾客交易数据库中项集间的关联规则问题， 其核心方法是基于频繁集理论的递推方法。以后又有很多研究人员对关联规则的挖掘问 题进行了大量的研究。他们的工作包括对原有算法进行优化，如引入随即采样、分割、 并行的思想、分布的思想等等，以提高算法的挖掘效率；提出各种变体，如泛化的关联 规则、周期关联规则等。 。 9 大连交通大学工学硕十学位论文 r a g r a w a l 等人2 1 在1 9 9 3 年设计了一个基本算法a p f i o f i ，提出了挖掘关联规则的一 个重要方法。该方法是一个基于两阶段频繁集的方法，将关联规则挖掘算法分为两个子 问题： ( 1 ) 找出数据库中满足最小支持度m i n s u p 的所有频繁集； ( 2 ) 利用频繁集挖掘出满足最小置信度m i n c o n f 的所有关联规则。 其中第一个问题是算法的核心，a p r i o d 算法基于频繁集理论的递推方法来解决这一 问题。其算法描述如下： 输入：事务数据库d ；最小支持度m i n s u p 输出：d 中的频繁项集 ( 1 ) l 。= 频繁1 - 项集) ； ( 2 ) f o r ( k = 2 ；l a ；k h ) d ob e g i n ( 3 ) c k = a p r i o r i _ g e n ( l ) ； 候选k - 项集 ( 4 ) f o ra l lt r a n s a c t i o n stedd ob e g i n ( 5 ) c r = s u b s e t ( c i ，t ) ； ( 6 ) f o ra l lc a n d i d a t e sc c r ( 7 )c c o u n t + + ； ( 8 ) e n d ( 9 ) l t = c e c ti c c o u n t m i n s u p ；频繁k - 项集 ( 1 0 ) e n d ( 1 1 ) = u 。厶 首先产生频繁1 项集，然后是频繁2 项集三：，直到有某个r 值使得三，为空，这 个算法停止。这里在第k 次循环中，过程先产生候选k 一项集的集合c 。，c 是对的 频繁集连接产生出来的。c 。中的项集是用来产生频繁集的候选集，最后的频繁集。必 须是c 。的一个子集。这个方法要求多次扫描事务数据库，即如果频繁集的长度为1 0 时， 那么就需要扫描1 0 次数据库，这是很大的i o 负载。 该算法能够快速、有效地挖掘出数据库中蕴含的用户感兴趣的频繁项集，进而产生 用户想要的关联规则，但它也存在以下缺陷： ( 1 ) 算法产生太多的冗余规则。当数据库规模太多或者支持度、置信度阀值太低时 产生的规则太多，用户很难对所有发现的规则做出区分和判断。 ( 2 ) 算法的效率和可扩展性还有待改进。经典的a p f i o f i 算法需要多次扫描数据库。 1 0 关联规则概述 当发现的最长频繁集的长度太长时，不但扫描数据库的次数会很多，所产生的候选项集 数量也十分巨大。尤其是2 项候选集，n 个1 频繁集可产生n ( n 0 2 个候选2 项集。 1 3 2 频繁集算法的几种优化方法 虽然a p f i o r i 算法自身已经进行了一定的优化，但是在实际应用中，还是存在不能 令人满意的地方，于是人们相继提出了一些优化方法。 ( 1 ) 基于划分的方法 s a v a s e r e 等人【h j 设计了一个基于划分( p a n i t i o n ) 的算法，这个算法先把数据库从逻辑 上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频繁集，然后把产 生的频繁集合并，用来生成所有可能的频繁集，最后计算这些项集的支持度。这里分块 的大小选择要使得每一分块都可以被放入主存，每个阶段只需扫描一个块，算法的正确 性是由每一个可能的频繁集至少在某一分块中是频繁集来保证的。上面所讨论的算法是 可以高度并行的，可以把所有分块分配给多个处理器生成频繁集。产生的频繁集的每一 个循环结束后，处理器之间进行通信来产生全局的候选k 项集。通常，处理器之间的通 信过程是算法执行时间的主要瓶颈：而另一方面，每个独立处理器生成频繁集的时间也 是一个瓶颈。其他的方法还有在多处理器之间共享一个哈希树( h a s ht r e e ) 来产生频繁集。 ( 2 ) 基于哈希( h a s h ) 的方法 一个高效产生频繁集的基于哈希( h a s h ) 的算法由p a r k 等人i ”1 提出的。通过实验我们 可以发现频繁集的计算过程中，主要的计算是在生成频繁2 项集上，p a r k 等人就是利用 了这个性质引入哈希技术来改进产生频繁2 项集的方法。 基于哈希的方法分为三个部分：第一部分得到频繁1 项集并构造哈希表，第二部分 在哈希表的基础之上构造候选项集c 。并确定频繁k 项集。，第三部分是不利用哈希表 并产生c 。和。 ( 3 ) 基于采样的方法 m a n n i l a 等人【1 6 】首先认为采样是发现规则的一个有效途径，随后又由t o i v o n e n l l 7 】进 一步发展这个思想：先使用从数据库中抽取出来的样本得到一些在整个数据库中可能成 立的规则，然后对数据库的剩余部分验证这个结果。t o i v o n e n 的算法相当简单并显著地 减少了i o 开销，但是