（计算机应用技术专业论文）基于密度网格的关联规则开采及聚类算法.pdf

华中科技大学硕士学位论文 摘要 关联规则是数据挖掘的主要模式之一，用于发现满足给定支持度和置信度的 属性之间的依赖关系。目前已经存在很多挖掘布尔型关联规则的经典算法及改进 算法，由于布尔型属性值固有的“0 1 ”特性，这些算法开采出来的规则不会很多。 在挖掘数量关联规则时，虽然人们在数量属性的离散化方面做了大量工作， 使挖掘算法在时空性能方面有了很大提高，但由于数量类型属性值的连续性，算 法仍面临返回大量规则的问题。 为了解决规则过多难于理解的问题，本文在研究经典聚类算法的基础上，综 合了基于密度算法可以发现任意形状聚类和基于网格算法处理速度快的优点，提 出了密度和网格相结合实现关联规则开采和聚类的方法基于密度网格的关联 规则开采及聚类算法，实现对数量关联规则的开采，并在此基础上聚类近似的相 邻规则，得到更具概括性、更易于理解的一般规则。该算法以元组的形式读取源 数据，并对数量型连续属性值分段离散化，在提取关联规则集以后，聚类右部满 足分段标准的关联规则。算法在必要时检验关联规则的准确性，通过改变参数最 终获取更好的规则。 为了验证算法的正确性与有效性，构建了一个关联规则开采及聚类系统。在 对算法进行理论分析的基础上，对算法的性能和正确性进行了实验。理论分析与 实验结果表明，该算法大大提高了数量关联规则开采的速度，减小了最终得到的 关联规则的数目，在提高规则的可理解性方面取得了实际效果。 关键词：数据挖掘，数量关联规则，聚类，聚类关联规则，支持度，置信度 华中科技大学硕士学位论文 a b s t r a e t i ti so n eo ft h ei m p o r t a n t p a t t e r n si nd a t am i n i n gr e s e a r c ht om i n ea s s o c i a t i o nr u l e s ， w h i c hi su s e dt of i n do u tt h ed e p e n d e n c eb e t w e e nd i f f e r e n ta t t r i b u t e sf o r g i v e ns u p p o r t a n dc o n f i d e n c et h r e s h o l dv a l u e s m a n yc l a s s i c a la n di m p r o v e da l g o r i t h m sh a v eb e e n p r o p o s e df o rm i n i n gb o o l e a na s s o c i a t i o nr u l e s b u tt h en u m b e ro ft h er u l e sm i n e db y a l lt h e s ea l g o r i t h m si sn o tt o ol a r g eo w i n gt ot h ei n h e r e n t “0 - l ”p r o p e r t yo fb o o l e a n a t t r i b u t ev a l u e s w h e n q u a n t i t a t i v ea s s o c i a t i o nr u l e sm i n e d ，t h et r e m e n d o u sp r o b l e mo fs e a r c h i n g t i m ea n d s p a c e i sc e r t a i nt ob ef a c e dw i t h ，d u et ot h es u c c e s s i o no fq u a n t i t a t i v e a t t r i b u t ev a l u e s a g r e a td e a lo fw o r k h a sb e e nd o n et op a r t i t i o nq u a n t i t a t i v ea t t r i b u t e ， a n di m p r o v e d m i n i n ga l g o r i t h m sp e r f o r m a n c ei nt i m ea n ds p a c e h o w e v e r t h ep r o b l e m o fa l a r g en u m b e ro f a s s o c i a t i o nr u l e sr e t u r n e db y a l g o r i t h mh a s n o tb e e ns o l v e dw e l l i nt h i s p a p e r , o n t h eb a s eo fc l a s s i c a l c l u s t e r i n ga l g o r i t h m ，c o m b i n i n g t h e a d v a n t a g et h a td e n s i t y b a s e d m e t h o dc a nf i n do u tc l u s t e r si nr a n d o m s h a p e a n d g r i d - b a s e dm e t h o d h a st h ec a p a c i t yo f r a p i de x e c u t i o n ，ac l u s t e r i n ga l g o r i t h m b a s e do n g r i da n dd e n s i t yi sp r o p o s e dt op e r f o r mm i n i n ga n dc l u s t e r i n gq u a n t i t a t i v ea s s o c i a t i o n r u l e s b yc o m b i n i n gs i m i l a r ，a d j a c e n ta s s o c i a t i o nr u l e st of o r m af e w g e n e r a lr u l e s ，t h e c l u s t e r e da s s o c i a t i o nr u l e sf o u n da r e h e l p f u l i n r e d u c i n g t h e l a r g e n u m b e ro f a s s o c i a t i o nr u l e st h a ta r et y p i c a l l yc o m p u t e db ye x i s t i n ga l g o r i t h m ，t h e r e b yt e n d e r i n g t h ec l u s t e r e dr u l e sm u c he a s i e rt oi n t e r p r e ta n dv i s u a l i z e 。t h ea l g o r i t h mb e g i n sb y t a k i n gs o u r c ed a t ai nt u p l ef o r ma n dp a r t i t i o n i n gt h o s ea t t r i b u t e st h a tt a k ev a l u e sf r o m ac o n t i n u o u sd o m a i n t h e nt h ea l g o r i t h mp e r f o r m sas i n g l ep a s so v e rt h ed a t au s i n ga n a s s o c i a t i o nr u l ee n g i n et od e r i v eas e to fa s s o c i a t i o nr u l e s n e x t ，a l lt h o s et w o - a t t r i b u t e a s s o c i a t i o nr u l e sw h e r et h er i g h t h a n ds i d eo ft h er u l e ss a t i s f i e so u rs e g m e n t a t i o n c r i t e r i aa r ec l u s t e r e d t h es e g m e n t a t i o nf o ra c c u r a c yi st e s t e d ，a n di fn e c e s s a r yc e r t a i n s y s t e mp a r a m e t e r s a r em o d i f i e dt o p r o d u c e ab e t t e r s e g m e n t a t i o n a n dr e p e a tt h e p r o c e s s t ov e r i f yt h e v a l i d i t y a n dc o r r e c t n e s so ft h e a l g o r i t h m ，a n a s s o c i a t i o nr u l e s c l u s t e r i n gs y s t e mi sc o n s t r u c t e d ，i nw h i c h w e a p p l y t h en e wm e t h o db e s i d e sg i v i n gt h e r e l e v a n tt h e o r y a c c o r d i n gt ot h e 也e o r e t i c a la n a l y s i sa n dt h er e s u l to fe x p e r i m e n t ，t h e a l g o r i t h ma p p a r e n t l ys p e e d st h e e x e c u t i o no fm i n i n gq u a n t i t a t i v ea s s o c i a t i o nr u l e s ， r e d u c e st h en u m b e ro fa s s o c i a t i o nr u l e sw ef i n a l l yf i n d ，m a k i n gt h er u l e se a s i e rt o u n d e r s t a n d k e y w o r d s ：d a t a m i n i n g ，q u a n t i t a t i v ea s s o c i a t i o nr u l e ，c l u s t e r ，c l u s t e r e da s s o c i a t i o n r u l e ，s u p p o r t ，c o n f i d e n c e 1 1 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名：张嘎考 日期：妒i ；侔明j 上日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于不保密口。 ( 请在以上方框内打“”) 学位论文作者签名：张酋豸 日期：p 侔r 月，瑁 指导狮签名：g 猫 日期细中年朋俗日 华中科技大学硕士学位论文 1 1 课题背景 1 绪论 我国计算机在医院的应用正逐步朝以临床业务为主的方向发展，怎样设计适 应我国医院的临床信息系统是许多业内人士所关注的课题。研究怎样按 h l 7 ( h e a l t hl e v e ls e v e n ) 标准来设计应用软件之间界面，以允许各个医疗机构不同 的系统之间，进行一些重要资料的通讯，对于促进我国医疗机构和世界标准接轨， 具有十分重要的意义。 h l 7 是个以临床业务为基础的应用层标准协议，它是l 临床工作归纳、总结 和抽象的综合性成果。h e a l t hl e v e ls e v e n 组织成立于1 9 8 7 年，它主要目的是要发 展各类型医疗信息系统间，如临床、银行、保险、管理、行政及检验等各项电子 资料的标准。h e a l t hl e v e ls e v e n 组织参考了国际标准组织( i n t e r n a t i o n a ls t a n d a r d s o r g a n i z a t i o n s ，i s o ) ，采用开放式系统互联( o p e ns y s t e mi n t e r e o n n e c t i o n ，o s i ) 的通 讯模式，将h l 7 纳为最高的一层，也就是应用层。它的规范提供了如：关联性的 分类、有效检查的产生、结构性交换资料的机制与协商等功能。h l 7 标准的制定， 为系统之间的信息交换提供了接口，使得不同应用系统之间能够建立联结，达到 集成不同供应商提供的软件产品的目的。在我国，对远程医疗的研究应用已取得初 步成果，h l 7 标准也在积极推广，对电子病例中h l 7 标准的数据进行挖掘，曼是一 个全新的领域。 医院信息系统的广泛使用给医务人员带来了大量信息和数据。医院信息化的 迅速发展使医疗信息系统中积累了大量的电子病历，如何从电子病历数据庠中挖 掘出对医务工作人员有用的知识，是建立电子病历的重要目的。医生通过分析病 人的患病数据，可以发现隐藏在这些数据后的规律，例如：某些疾病之间的隐藏 关系，疾病和季节、环境以及饮食习惯等之间的关系；管理人员通过分析不同季 节各种疾病病人住院的人数，可以指定新的吸引病人住院的改进措施，改进医疗 机械和药品的采购计划等。 华中科技大学硕士学位论文 本课题正是来源于基于h l 7 标准的医疗信息系统中的决策支持系统。决 策支持系统的一个重要方面便是从大规模数据库中高效地发现未知的、对决策有 潜在价值的模式，数据开采技术便应运而生。在h l 7 的基础上进行的数据开采， 可以有效指导医院的业务开拓，优化医院资源配置，有效利用有限的人力物力，提 高医院的工作效率。在电子医疗系统逐渐普及的今天，具有特别重要的意义。 1 2 国内外当前研究概况 1 2 1 数据开采 数据开采可以定义为在大规模数据库中高效地发现隐含的、未知的、对决策 有潜在价值的模式( p a t t e r n s ) 或规月, l j ( r u l e s ) ，这些规则蕴含了数据库中一组对象之 间的特定关系，为经营决策、市场策划、政策法规制定等提供依据l z - 3 1 。数据开采 还有其他一些中文译名，如：数据采掘、数据挖掘、知识提取、知识采掘等。 随着数据开采研究的发展，数据开采的对象已经远远超过了数据库的范围， 数据源还可以是：数据仓库、文本数据集合、h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ) 数据集，w e b 文档或任意数据集合等【4 1 。由于k d d ( k n o w l e d g ed i s c o v e r y i n d a t a b a s e ) 处理的数据是从现实世界得来的，因此并不能保证所有数据都规范，一 般需要对数据进行预处理，使之适用于知识提取。数据开采的结果一般表现为模 式。模式可以是我们所说的知识，它给出了数据的特性和数据之间的关系，是对 数据包含的信息更抽象的描述。数据开采的结果必须能够被用户理解。数据开采 的目的就是将数据中隐含的模式提取出来，从而帮助人们更好地了解数据包含的 信息。但是般知识学习算法得到的模式对于用户来说很难理解，更不用说使用。 因此，数据开采不仅应该能够将知识提取出来，更应该将发现的知识以更直观易 用的方式呈现给用户。 数据开采是近年来随着数据库技术和人工智能技术的发展而出现的一种全新 信息技术【5 扫l ，也是计算机科学与技术，尤其是计算机网络的发展和普遍使用所提 出的而且迫切需要解决的重要课题。数据开采的技术基础是人工智能，但他仅仅 华中科技大学硕士学位论文 利用了人工智能中些已经成熟的算法和技术，如人工神经网络、决策树、规则 推理等，不过他们两者之间的主要区别还是数据挖掘是在海量数据的基础上进行 的。数据开采方法有很多种，其中比较典型的有关联分析、序列模式分析、分类 分析、聚类分析等。 1 关联分析：即利用关联规则进行数据挖掘，而关联规则是描述事物之阔 同时出现的规律的知识模式，关联分析的目的是为挖掘出隐藏在数据间的相互关 系。 2 序列模式分析：序列模式分析和关联分析相似，他把数据之间的关联性 与时间性联系起来，为了发现序列模式，不仅需要知道事件是否发生，而且需要 确定事件发生的时间。其目的也是为了挖掘数据之间的联系，但序列模式分析的 侧重点在于分析数据问的前后或因果关系。 3 分类分析：分类分析就是分析示例数据库中的数据，为每个类别做出准 确的描述建立分析模型或挖掘出分类规则，能够把数据集中的数据映射到某个给 定的类上，其输入集是一组记录集合和几种标记。 4 聚类分析：与分类分析不同，聚类分析法的输入集是一组未标定的记录， 也就是说此时输入的记录还没有进行任何分类。其目的是根据一定的规则，合理 地划分记录集合，使组之间的差别尽可能大，组内的差别尽可能小。 数据开采一般具有以下特点： 1 处理的数据规模十分巨大： 2 查询一般是用户提出的随机查询，通常不能形成精确的查询要求； 3 数据开采既要发现潜在规则，还要管理和维护规则，而规则是动态的， 当前的规则只能反映当前状态的数据特征，随着新数据的不断加入，规则要随之 更新： 4 数据开采中规则的发现主要是基于大样本的统计规律，发现的规则不必 适于所有的数据，当达到某一闽值时便可认为有此规律。 华中科技大学硕士学位论文 1 2 2 关联规则 从数据库中开采的规则可以有以下几种：特征规则、区分规则、聚类规则、 关联规则和进化规则等。关联规则是当前数据开采研究的主要模式之一【7 。 。它侧 重于确定数据库中不同领域之间的联系，找出满足给定支持度和置信度闽值的多 个属性之间的依赖关系。下面是一个直观的关联规则的例子：在计算机配件商店 中，7 0 的包含键盘的交易中包含鼠标，在所有交易中，有6 同时包含这两种物 品。规则表示为： 键盘j 鼠标( 置信度7 0 ，支持度6 ) 其中支持度和置信度是关联规则的度量标准。这条规则表示：同时购买键盘、 鼠标的事务占分析总事务的6 ；买键盘的顾客有7 0 同时会买鼠标。 这些关联规则可以提示商店的工作人员调整货架，比如，将可能被同时购买 的几种商品放得近一些，以方便和鼓励顾客同时购买这些商品，提高商店的营业 额。 除了购物篮分析外，关联规则挖掘广泛应用于市场规划、股市交易分析、分 类设计等商务决策，以及w e b 服务数据分析、网络故障分析等其它许多实际应用 中。 设i = i i ，i 2 ，i 。 是二进制文字的集合，其中的元素称为项( i t e m ) 。记d 为交 易( t r a n s a c t i o n ) t 的集合，这里交易t 是项的集合，并且t 三i 。对应每一个交易有 唯一的标识，如交易号，记作t i d 。设x 是一个i 中项的集合，如果x t ，那么 称交易t 包含x 。 个关联规则是形如x j y 的蕴涵式，这里x c i ，y d ，并且x n y = o 。规则 x j y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包含x 和y 的交易数与所 有交易数之比，记为s u p p o r t ( x j y ) ，即 s u p p o r t ( x j y ) = 1 t ：x u y t ，t e d i i d i 规则x j y 在交易集中的置信度( c o n f i d e n c e ) 是指包含x 和y 的交易数与包含x 的 交易数之比，记为c o n f i d e n c e ( x j y ) ，即 c o n f i d e n c e ( x = y ) = ：l t ：x u y c _ t ，t e d i t ：x t ，t e d ) 4 华中科技大学硕士学位论文 给定一个交易集d ，挖掘关联规则问题就是产生支持度和置信度分别大于用 户给定的最小支持度( m i n i m u ms u p p o r t ) 和最小置信度( m i n i m u mc o n f i d e n c e ) 的关联 规则。从概念上看，这一问题可以看作是从一个属性均为逻辑型的关系数据表中 发现“l ”值之间的关联。关系数据表中属性对应于项目，而记录对应于交易。如果 对应于一个属性a 的项目出现在对应于一个记录t 的交易中，那么记录t 中的属 性a 值为“1 ”，否则为0 。为了与下节所讨论的内容区别开来，称这类问题为布 尔关联规则挖掘问题。 开采布尔关联规则问题可以分为两个子问题： 1 寻找交易数据库中所有支持度超过用户给定的最小支持度的项的集合 ( i t e ms e 0 ，这个项的集合称为频繁集( f r e q u e n ti t e ms e t ) ，也叫大项集； 2 应用频繁集产生规则。一般的想法是，如果a b c d 和a b 是频繁集，那 么，可以通过计算置信度e o n f = s u p p ( a b c d ) s u p p ( a b ) 来确定规则a b j c d 是否成 立。当置信度c o n f _ 最小置信度时，规则成立，其中s u p p ( x ) 表示x 的支持度【l 叭。 目前的关联规则挖掘算法主要研究以下两个闯题： 1 减少y o 操作：关联规则挖掘的数据集有时高达g b 甚至t b 的数量级， 频繁的i o 操作将会影响关联规则的挖掘效率，减少i o 操作主要是减少扫描数据 集d 的次数； 2 降低需要计算支持度的项集数，使其与频繁项集的数量接近。候选项集 数量的降低可以节省为处理部分候选集所需的计算时间和存储空间1 1 ”。 关联规则开采的主要挑战性在于数据量巨大，因此算法的效率是关键。目前 研究的重点在第1 步，即找到l a r g ei t e ms e t ，因为第2 步相对来说较容易。围绕这 个问题人们进行了大量的研究。几年前r a g r a w a l 等人曾提出了关联规则的一些 挖掘算法，如a i s ( a s s o c i a t i o n f o ri n f o r m a t i o ns y s t e m ) j 手1 s t e m 8 , 9 1 ：t 9 9 4 年又提出 了改进的算法a p r i o r i 和a p r i o r i t i d 1 2 1 。这两类算法每步所产生的候选项集是不同 的：在a i s 和s t e m 中的候选项集是在读入数据，特别是在读入一个事务时产生 出来的，如果上一步所产生出来的频繁集出现在某一事务中，那么可以用该事务 中的项目扩展上一步的频繁项集以产生新的候选集；而a p r i o r i 和a p r i o r i t i d 算法 是借助上一步产生的频繁项集来产生候选项集，计算支持度，并不考虑在数据库 华中科技大学硕士学位论文 中的事务。在初始阶段，a p r i o r i 比a p r i o r i t i d 有效，因为有太多的k 一项目候选项 需要在这个过程的早期阶段处理。但在后期扫描中a p r i o r i t i d 较好1 3 】。原因如下： a p r i o r i 和a p r i o r i t i d 使用同样的候选集生成过程，因此对同样的项目集计数。在 后期扫描中候选减少了。 围绕着怎样精简备选集c k 的大小( 特别是c 2 的选择会大大影响采掘的性能) 和减少对数据库的扫描次数，又有不少改进方法。例如r a g r a w a l 提出的a p r i o r i h y b r i d 算法：它在初期扫描时用a p r i o r i ，而当c k 幸能放进内存时就转向a p r i o r i t i d 算法1 1 4 l 。p a r k 等人提出的d h p ( d i r e c th a s h i n g a n dp n i f l i n g ) 算法，使用h a s h 技术有 效地改进了备选集c k 的产生过程【1 5 l 。s a v a s e r e 等在1 9 9 5 年提出了一种把数据库 分块( p a r t i t i o n ) 处理的算法【1 6 】，降低了采掘过程中i o 操作的次数，减轻了c p u 的 负担。h t o i v o n e n 使用抽样( s a m p l i n g ) 的方法可以用较小的代价从大型数据库中找 出关联规则【1 7 1 。 以上介绍的均是串行挖掘算法。更进步的研究在分布和并行环境下采掘关 联规则f 1 8 _ 2 0 1 ，例如，d w c h e u n g 等提出了一种关联规则的快速分布式开采算法 ( f d m ，f a s td i s t r i b u t e dm i n i n g ) 2 1 , 2 2 。 在关联规则开采中，要注意以下几个问题： l充分理解问题； 2 目标明确： 3 数据准备工作要做好，它将直接影响到问题的复杂度和目标的实现： 4 ，选取恰当的最小支持度和最小置信度：这依赖于用户对目标的估计，如 果取值过小，那么会发现大量无用的规则，不但影响执行效率、浪费系统资源， 而且可能把目标埋没，如果取值过大，则又可能找不到规则，与知识失之交臂； 5 很好地理解关联规则。数据开采工具能够发现满足条件的关联规则，但 它不能确切表达关联规则的实际意义。对关联规则的理解需要熟悉业务背景，丰 富的业务经验对理解数据有很大帮助。在发现的关联规则中，可能有两个主观上 认为没有多大关系的物品，它们的关联规则支持度和置信度却很高，需要根据业 务知识、经验，从各个角度判定这是一个偶然现象或有其内在的合理性：反之， 可能有主观上认为关系密切的事物，结果却显示他们之间关联性不强。只有很好 华中科技大学硕士学位论文 地理解关联规则，才能去其糟粕，取其精华，充分发挥关联规则的价值。 1 2 3 数量关联规则 前面讨论了布尔关联规则的发现问题。简单地说，给定一个交易集合，其中 每个交易是一个项目的集合，关联规则的表达式为x j y ，其中x 及y 为项目的 集合。关联规则问题就是发现满足用户给定的最小支持度和最小置信度约束条件 的关联规则。 当前，由于关系型数据库技术的发展和完善，许多部门、企业的绝大多数数 据都以关系数据表的形式保存在大型关系数据库中。在实际应用中，关系数据库 中的属性不仅仅只有逻辑型一种取值类型，还可以有其它多种类型。属性可以是 数量属1 生( q u a n t i t a t i v ea t t r i b u t e ，又称为数值属性、定量属性，如年龄、价格等) ， 也可以是类别属性( c a t e g o r i c a la t t r i b u t e ，如品牌、制造商等) 。逻辑型属性可以看 作是类别属性的一个特例。本文将讨论大型数据库中数量属性及范畴属性上的关 联规则发现问题，称这类问题为数量关联规则开采【2 引。本文将就数量关联规则的 挖掘问题进行深入的研究和讨论。 数量关联规则和布尔关联规则的定义略有差别【2 3 1 。 定义1 设i 为属性集合，i = i i ，i 2 ，i m ) ，p 为正整数集合。i v = i x p ， i v 表示属性及其值v 。项的集合i r = f ( x ，l ，u i p x p i ，若x 为数量属性，琏u ；若x 为类别属性，i = u 。 i r 表示数量属性x 取值在i 和u 之间。对于任何x c - i r ， a t t r i b u t e ( x ) 2 x l ( x ，l ，u ) x 。 定义2 设d 为记录集，其中每个记录r 是属性值的集合，r i v 。假定每 个属性在一个记录中出现至多次。如果对任何的 x ，存在 r 且有 l v 曼u ，那么，称记录r i r d ) 支持x ( x g i r ) 。 定义3 数量关联规则是具有x y 这样形式的蕴涵式，其中x c i r ，y c l r ， 且a t t r i b u t e ( x ) f 7 a t t r i b u t e ( = m 。如果d 中有s 的交易支持x u y ，且c 的支持x 的交易也支持y ，则该规则的支持度和置信度分别为s 和c 。 定义4 发掘多值关联规则问题就是在给定的交易集合d 中产生所有满足最 华中科技大学硕士学位论文 小支持度和最小置信度的多值关联规则的过程。 目前已经提出了许多有效开采关联规则的算法f 2 ”，但这些算法绝大多数是针 对布尔属性的 2 5 - 2 7 1 。然而，除了布尔属性外，一般的数据集合中通常还包含数字 属性的数据，而数量关联规则的开采不能直接运用那些针对布尔属性提出的开采 算法。 对数量关联规则挖掘的处理过程主要是：对数量属性变量值进行分区，然后 分别映射到布尔型变量上，对类别属性的每个值分别映射到一个布尔型变量【2 弘3 0 】。 因而如何对数量属性进行分区、所分的区间范围多大为好，就成为挖掘数量关联 规则算法的关键问题【3 。数量属性关联规则挖掘算法首先要将类别属性以及数量 属性映射到组顺序递增的整数上，这样可以保证属性值的有序性；其次用聚类 等方法对数量属性值进行分段，同时考虑数据间相对距离、间隔的稠密度等因素 将其转化为布尔型数据库表：最后应用布尔型挖掘算法实现数量关联规则的挖掘。 1 3 本文主要研究工作 1 3 1 主要研究设想 在挖掘数量关联规则方面，人们已经作了大量的工作，但大多集中在确定划 分区间数的动态聚类算法的研究上【3 2 。4 1 。而对于关联规则的聚类少有涉及。划分 区间以后，因为区间的组合要远大予具体属性值的数量( 特别是范围很大的数字属 性，例如银行存款) ，因而将会返回大量的规则”】。如何进一步提高关联规则的开 采效率，减少冗余规则的产生，将是今后此领域研究的重点。 为解决该问题，本文引入一个新概念聚类关联规则( c l u s t e r e da s s o c i a t i o n r u l e ) ，来表示通过合并近似的“相邻”规则而得到的概括性的一般规则。聚类关联 规则有助于减少现存算法开采出来的关联规则的数量，使其更易于理解，更形象 化。 8 华中科技大学硕士学位论文 1 3 2 主要工作 虽然人们在数量属性的离散化方面做了大量工作，使挖掘数量关联规则的算 法在时空性能方面有了很大提高，但仍未很好地解决算法返回大量规则的问题。 为了解决规则过多难于理解的问题，本文在研究经典聚类算法的基础上，综 合了基于密度算法可以发现任意形状聚类和基于网格算法处理速度快的优点，提 出了一种密度和网格相结合的方法基于密度网格的关联规则开采聚类算法， 并给出了算法的详细步骤。 算法的关键是聚类关联规则。因为对海量数据集来说，算法所开采的关联规则 的数量仍然很大，且不直观，不易被用户理解。为此，需要聚类规则。算法的难点在 于如何确定聚类关联规则的位置，以及如何去除锯齿状边界和噪声。对于前一个 问题，能够通过4 a ，2 节中的算法实现定位。对于第二个问题，为了减小这些不规 则情况造成的影响，设置阈值过滤掉低密度网格，去除噪音。 本文在理论分析的基础上，构造了基于密度网格的关联规则开采及聚类系统。 该系统首先以元组的形式读取源数据，并对连续属性值分段。然后用关联规则引 擎对数据执行一趟遍历，提取关联规则集。接下来，聚类所有规则的右部满足分 段标准的二维关联规则。检验结果的准确性，如有必要，改变系统参数获取更好 的分段，重复该过程直至结束。 1 4 论文组织结构 本文首先回顾数据挖掘算法的一个分支关联规则开采算法。常见的关联 规则开采算法绝大多数是针对布尔属性的。然而，除了布尔属性外，一般的数据 集合中通常还包含数字属性的数据，而数量关联规则的开采不能直接运用那些针 对布尔属性提出的开采算法，必须首先将连续属性离散化，然后应用传统的布尔 型关联规则开采算法实现数量关联规则的开采。 如何对数量属性进行分区、所分的区间范围多大为好，就成为挖掘数量关联 规则算法的关键问题。本文第二章主要讨论数量关联规则开采的一般思路，尤其 华中科技大学硕士学位论文 是数量属性值域划分的几种方法，并对他们进行了比较。这些算法都有一个共同 特点：都必转化为布尔关联规则开采算法能够处理的情形，这将花费更多的空间， 还会返回大量的规则。 在第三章中将详细介绍基于密度和基于网格的聚类算法，基于密度算法可以 发现任意形状聚类，而基于网格算法处理速度快，在综合两者的基础上，提出基 于密度网格的聚类算法思想，正是本文中实现关联规则聚类的基础。接下来讨论 本文中用于关联规则开采的聚类算法的特点和必须考虑的几个问题，并给出相应 的分析。 第四章主要介绍算法的基本思想和理论基础，针对算法中的关键步骤进行细 致、深入、详细的阐述。 为了验证算法的有效性，验证算法是否达到预期目的，需要设计并且实现验 证系统，在第五章中详细介绍验证系统的总体结构、所使用的数据库以及系统结 构。随后给出部分实验资料以及实验结果，并且对算法性能进行分析，剖析了算 法的优缺点以及使用范围。 最后，对全文进行总结，并提出下一步的研究方向。 1 0 华中科技大学硕士学位论文 2 数量关联规则开采算法分析 本章主要对本课题的研究涉及到的现有数量关联规则开采的相关理论和实践 知识进行阐述，为后面的使用做准备。其组织如下：首先讨论数量关联规则开采 的一般思路和步骤；其次详细说明数量属性值域划分的几种方法；接下来介绍根 据划分方法不同而形成的不同数量关联规则开采算法，并对它们进行比较，分别 说明了它们的优缺点；最后总结了这些算法的一个共同特点：都必转化为布尔关 联规则开采算法能够处理的情形。 2 1 数量关联规则开采的一般思路 许多文献都讨论了发掘布尔型关联规则问题b a r p ( b o o l e a na s s o c i a t i o nr u l e s p r o b l e m ) ，它可以看作是发掘多值关联规则问题q a r p ( q u a n t i t a t i v ea s s o c i a t i o nr u l e s p r o b l e m ) 的基础和特例，是在属性值为布尔量的关系表中寻找属性值为“1 ”的属性 之间的关系。因此从理论上来看，数值关联规则问题可以通过映射关系转化为逻 辑( 布尔) 关联规则问题。如果所有的属性都是类别型属性，或是只有很少几个值的 数量型属性，这一转化过程很简单。对原始数据表中的每个属性来说，它的每个 属性值对应逻辑数据表中的一个属性。在原始数据中如果属性a 的值为a ，在逻 辑数据表中与 对应的属性值为1 ，否则为0 。如果原始数据表中某个数 量属性的值域很大，首先要把该属性的值域分成较小的区间，然后将每一个区间 映射成一个逻辑属性，。即项目。对这些映射后的逻辑属性，就可以应用逻辑关联 规则发现算法去发现数量属性关联规则。 2 2 数量关联规则开采的步骤 开采数量关联规则一般可以分为以下五个步骤： 1 划分区间：为每一个数量属性确定其区间划分数目。 2 映射：对于类别属性，将属性值映射到一个连续的整数集上。未划分区 华中科技大学硕士学位论文 间的数量属性，其值映射为连续整数，并保持该值的顺序。已划分区间的数量属 性，将区间跌射为连续整数，并保存持该区间的顺序。这个过程对于关联觌则开 采算法是透明的。 3 发现频繁集：对每个数量或类别属性，取得其支持度。只要数量属性的 支持度小于用户自定义的最大支持度，则合并相邻值。这样就锝到了每个具有最 小支持度的数量属性的所有划分域及其对应的值，这些构成了频繁集。 4 应用频繁集生成关联规则。般的想法是，如果a b c d 和a b 是频繁集， 那么，可以通过计算置信度c o n f = s u p p ( a b c d ) s u p p ( a b ) 来确定规则a b j c d 是 否成立。当置信度c o n f 最小置信度时，规则成立，其中s u p p ( x ) 表示x 的支持 度。 5 ，输出感兴趣的规则。 2 3 数量属性值域区间的划分 一般的数量关联规则的挖掘算法，都是首先对连续属性离散化，然后使用挖 掘布尔关联规则的算法找到感兴趣的规则f 3 5 ，3 引。对于连续属性的离散化处理，实 质上就是把属性域划分成区间。划分的方法对数量关联规则提取的质量起着决定 性作用。原因如下： 1 ，过小置信度问题：若区间的数目过少，则支持区间的元组数目增加，包含 区间的强项集的支持度上升，但在强项集的子集支持度不变的情况下，将导致右 端包含该子集的规则置信度下降，若不能达到置信度阚值，就会造成信息丢失； 2 过小支持度阿题：划分的区间数目过多，则区间的支持度下降，不能有 效地生成全部强项集。 对于第一个问题，可以采用增加区间数的方法解决信息丢失的问题。对于第 二个问题，可以采用合并相邻区闯的方法来解决最小支持度问题。然而，合并相 邻区间以增加区间数目的同时，又会产生两个新的问题：运行时间和大量规则。 如果一个数值属性的值域上有n 个区间，平均就会存在o ( n 2 ) 个包含某一特定区间 的域。这样在映射后的逻辑数据表中每条记录的项目数日就会呈爆炸式地增长 华中科技大学硕士学位论文 不可避免地会大大增加挖掘任务运行时间；如果一个数值属性的某个区间满足最 小支持度条件，包含这个区间的域也将具有最小支持度。因此，规则的数目就会 呈爆炸式的增加。而这些规则中的大部分是毫无意义的。 为了缓解运行时间问题，就需要减少区间数目，以部分信息丢失为代价；为 了缓解置信度问题，就需要尽可能地增加区间数目，此时就不得不以增加运行时 间及产生大量冗余规则为代价。 在存在连续属性和多值属性的数据库中，如果能够把连续属性和类别属性映 射为相应的布尔属性，就可以用布尔关联规则挖掘算法来解决数值关联规则的采 掘问题。连续属性和类别属性到布尔属性的映射可以通过下面的方法完成：对取 值较少的类别属性，每个属性值产生一个项目；对连续属性，属性值空间被离散 化为各个子区间，由各个子区间产生一个项目；对取值较多的多值属性，属性集 集合被划分为多个子集，每个属性值子集产生一个项目。 如：在表2 1 所示的数据库中，共有三个属性：工资、婚否和拥有电脑数， 其中工资为连续属性，婚否为布尔属性，拥有电脑数为多值属性。这样，将工资 属性的属性值空间划分为两个子区间：【8 0 0 ，9 0 0 】、( 9 0 0 ，l o 0 0 1 ，则工资属性产生两个 项目： 、 。对多值属性婚否和拥有电脑数， 根据他们的各个属性值产生项目。婚否属性： 、 ，拥有电脑 数属性： 、 、 。 表2 1 示范数据库 记录号工资婚否拥有电脑数 l o o8 0 0no 2 0 0 9 1 0y2 3 0 08 5 0y1 4 0 01 0 0 0y2 5 0 09 5 0n 1 经过上述处理后，对表2 1 的数据库转化为表2 2 中的形式，就可以采用一般的确 尔关联规则采掘算法进行数值关联规则的开采了。 华中科技大学硕士学位论文 表2 2 处理后的表21 中的数据库 工资工资婚否婚否拥有电 拥有电拥有电 记录号 8 0 0 ，9 0 0 ( 9 0 0 ，1 0 0 0 yn 脑数：0脑数：1脑数：2 1 0 0100 1100 2 0 0o1 1o0ol 3 0 0】ol 0o10 4 0 00 l1oo01 5 0 001 01o1o 2 4 几种常见的量化关联规则开采算法 根据属性划分方法的不同，有以下几种常见算法 3 7 ： 1 等深划分( e q u a ld e p t hp a r t i t i o n i n g ) 划分为n 个区间，每一个区间包含大致相同的样本个数。 f u k u d a 提出的等深度划分方法在一定程度上解决了过小支持度和过小置信度 问题。这种方法趋向于将支持度较高的区域划分为多个小区间，离散化后原本相 近的连续属性取值分散到不同的区间，降低了包含该属性峰值区域的项集的支持 度；当支持度降低到最小支持度以下时将导致信息丢失。当数据分布在某个点附 近达到峰值时，等深度划分这种机械的方法并不能反映出数据本身的特点，因此 对高偏度的数据效果不理想。 2 部分k 度完全方法( p a r t i a lk c o m p l e t e n e s s ) 当数据分布在某个点附近达到峰值时，等深度划分这种机械的方法并不能反 映出数据本身的特点，因此对高偏度的数据效果不理想。而另一方面，聚类方法 可以定量地确定对象之间的亲疏关系，对于给定的大样本，在没有己知的模式参 考情况下，聚类方法能够按照样本的本性将对象分类，在解决数量关联问题中， 应用聚类方法将属性值分类，得到的每一类，构成一个区间，可以解决等深度划 分不能解决的问题，能体现出数据的分布情况。 a g r a w a l 等人提出的基于支持度的部分k 度完全方法( p a r t i a lk - c o m p l e t e n e s s ) 的优越之处在于：所得到的区间支持度大于最小支持度，不会因过小支持度被忽 视。而同时给出了置信的降低程度，在一定程度