（计算机应用技术专业论文）关联规则挖掘算法优化和概念格粗糙集理论研究.pdf

华中科技大学硕士学位论文 摘要 关联规则挖掘的主要任务是从大量的交易中得出规则，其关键是求出频繁项集。 著名的a p r i o r i 算法存在的主要问题是：当数据量较大时，运算效率降低。把整个 数据库理解成一个矩阵，如果每次运算前都根据上次运算结果及频繁项集的性质， 把矩阵中的某些行和列删去，使整个数据库动态地缩小，就能减少运算量，并且可 以大大提高后续运算的效率根据这种想法，对原来的方法进行了改进。 概念格和粗糙集作为数学工具，都可以用来研究关联规则。如何从形式背景对 应的概念格中寻求两个上下近似概念或者上下近似外延来近似给定的一个对象集， 关于这个问题，已有几种求法，它们各有特点。通过理论分析和比较，得到了内在 的联系和理论证明。研究得出：概念格的外延可以通过粗糙集方法来获得，它正是 粗糙集理论中的可定义集合。给定一个集合，它的上近似集合的上近似外延正好是 这个集合的公共属性集所对应的对象集合。对下近似外延提出了用拟合度方法作为 选择标准。经实例模拟，结果更清楚。 粗糙集理论在数据分析中有着独特的作用。对于一些不完整的数据库( 有些数 据不能完全确定) ，可以借用粗糙集方法即作为不完备信息系统来研究。对不完备信 息系统构造新的粗糙集，利用上下近似并引入模糊度来刻画不确定程度，从而得到 带有模糊度量的决策规则。同时证明了模糊度的一些性质。 粗糙集公理化从粗糙集实际问题中抽象出来，不必从原始的上下近似定义出发， 只要满足几条公理就能刻划相应的租糙集，因此其本质特征更为清楚。通过对各类 粗糙集的公理集独立性证明，去掉冗余的公理，可以保证公理集的独立性，得到经 典关系和模糊关系下的最小公理集。这对进一步研究粗糙集公理化问题提供了理论 保证。 关键词：关联规则，概念格，不完备信息系统，粗糙集，公理 华中科技大学硕士学位论文 a b s t r a c t t h em a i nt a s ki nd a t am i n i n go fa s s o c i a t i o nr u l e si st og e tr u l e sf r o mag r e a td e a lo f 仃锄1 s a c t i o n s t l l ek e yo fw h i c hi st of i n do u tt h ef r e q u e mi t e m ss e t s a l t h o u g ht h ea p f i o f i a l g o r i t h mi saf a m o u so n et of i n do u tt h ef r e q u e n ti t e m s ，t h ee f f i c i e n c yb e c o m e sl o w e r w i t ht h ed a t ai n c r e a s i n g t h ew h o l ed a t a b a s ec a nb et a k e na sam a t r i x i fs o m er o w sa n d c o l u m n si nt h em a t r i xa r ed e l e t e da c c o r d i n gt ot h ep r o p e r t yo ft h ef r e q u e n ti t e m ss e t b e f o r ew ed e a lw i t ht h ed a t a b a s e ，t h ed a t a b a s ew i l lb em a d ed y n a m i c a l l ys m a l la n d c a l c u l a t i o nw i l lb ed e c r e a s e d b a s e do nt h ea b o v et h o u g h t , s o m ei m p r o v e m e n t sa r em a d e o nt h eo r i g i n s ! m e t h o d b o t hc o n c e p tl a t t i c ea n dr o u g hs e t , a st o o l so fm a t h e m a t i c s ，a r eu s e dt os e a r c hf o rt h e a s s o c i a t i o nr u l e s t h e r ea r cs o m em e t h o d st oa p p r o x i m a t eag i v e ns e tw i t ht w oe x t e n t so f t h ec o n c e p ti nt h ef o r m a lc o n t e x t c o m p a r i n gw i t ht h e s em e t h o d sw eg e ts o m e a s s o c i a t i o n sa m o n gt h e mi nt h et h e o r e m s t h em a i nr e s u l t sa l ea sf o l l o w s ：t h ee x t e n to f c o n c e p tc a l lb eo b t a i n e db ym e a n so fr o u g hs e t i nf a c t , i ti sad e f i n a b l es e ti nr o u g hs e t t h e o r y t h eu p p e ra p p r o x i m a t i o ne x t e n to f u p p e ra p p r o x i m a t i o no f t h es e ti sa l lo b j e c t ss e t c o r r e s p o n d i n g t ot h ec o m m o na t t r i b u t i o n so f t h eg i v e ns e t r o u g hs e tt h e o r yp l a y sau n i q u er o l ei nt h ed a t aa n a l y s i s i n c o m p l e t ei n f o r m a t i o n s y s t e mi nt h er o u g hs e ti sa ne f f e c t i v em e t h o dt od e a lw i t hi n c o m p l e t ei n f o r m a t i o nw h i c h h a ss o m eu n c e r t 出d a m mi nt h ed a t a b a s e 。al l e wr o u g hs e ti sc o n s t r u c t e df o rt h e i n c o m p l e t ed a t a b a s e ；t h el o w e ra n du p p e ra p p r o x i m a t i o n sw i t hf u z z i n e s sa r ei n t r o d u c e dt o c h a r a c t e r i z e t h eu n c e r t a i n t y s o m er u l e sw i t hf u z z i n e s sa g ea l s of o u n do u ta n ds o m e p r o p e r t i e so ff i j z z i n e s sa r cp r o v e d r o u g hs e ta x i o m a t i z a t i o ni sa b s t r a c t e df r o mt h er o u g hs e td e f i n i t i o n , w h i c hm a k e st h e c h a r a c t e rn 加憷c l e a r l y t h er e d u n d a n ta x i o m sa r ed e l e t e da n dt h ei n d e p e n d e n c e so f i i 华中科技大学硕士学位论文 v a r i o u sr o u g hs e ta x i o m s 黜g o ta n dp r o v e d w eg e tt h em i n i m i z a t i o no f a x i o ms e t su n d e r t h ec l a s s i c a la n df u z z yr e l a t i o ne n v i r o n m e n t t h i sr e s u l tp r o v i d e st h e o r e t i c a ls u p p o r tt o f u r t h e rr e s e a r c ho nr o u g hs e ta x i o m s k e yw o r d s ：a s s o c i a t i o nr u l e s ，c o n c e p tl a t t i c e , i n c o m p l e t ei n f o r m a t i o ns y s t e m , r o u g hs e t , a x l o m s l n 独创性声明 y1 0 1 6 4 4 9 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担 学位论文作者签名：为哟 且期： 卯5 年f d 月，f 臼 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书 本论文属于 不保密圈。 ( 请在以上方框内打“，”) 学位论文作者签名：钐踢罕 日期：歹加5 年i ，月；7 日 指导教师签名崔t 习罕 日期：z 一二年，口月弓日 华中科技大学硕士学位论文 1 1 课题的研究背景 1 绪论 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信 息和知识的过程。 当前世界，计算机与信息技术高速发展，各领域的信息与数据急剧增加，需要 处理大量的信息。所收集的数据和信息中不确定部分越来越多，信息与数据中的关 系更加复杂。如何从大量的、不完整的、不确定的数据信息中挖掘出科学的、潜在 的、有利用价值的规律，是数据挖掘的主要任务，传统的方法已显得苍白无力，必 须寻找更好的方法。 关联规则挖掘、概念格与粗糙集理论都是数据挖掘的有力工具，它们已广泛用 于国民经济各行业，对它们的研究对于信息处理技术的发展，科学决策水平的提高， 社会经济的发展具有重要意义。 本文将对上述的几种方法进行综合分析，对某些方面进行探索性的研究，旨在 改进应用的方法或完善现有的理论。 1 2 国内外概况 关联规则挖掘是数据库知识发现的核心，大量的数据背后隐藏着许多重要信息， 这些信息往往可以用关联规则的形式来表示。比如超市中，从大量的顾客购买记录 中，往往可以发现多数顾客在购买面包的同时也会购买牛奶这样一个明显的规律， 我们用“购买面包j 购买牛奶”来表示。而有些男士在为自己的婴儿购买纸尿布的 同时，也顺便为自己带上一瓶啤酒。这样一个隐藏在数据背后的规律往往是在通过 大量的数据分析后才被发现的，我们用“购买纸尿布j 购买啤酒”来表示。如果把 面包和牛奶放在一起能增加购买量，把纸尿布与啤酒放在一起同样也能促销。 华中科技大学硕士学位论文 关联规则挖掘工作的一个主要任务是从大量的交易中得出一些规则。这些规则 提取的前提就是找出频繁项目集。由于交易量大，要求出频繁项目集需要大量的计 算。如何提高关联规则的挖掘效率是关联规则挖掘中的一个值得研究的方向。r a k e s h a g r a w a l l u 提出了a p r i o f i 算法以及它的改进a p r i o r i t i d 和a p r i o r i h y b r i d 算法，后来 许多学者在此基础上又作了改进，但总体上还是没有脱离a p r i o r i 算法的基本思想。 由于a p r i o r i 算法是一个多重搜索算法，对海量数据集合，内存不够，每扫描一 次，都要读取外存一次，使效率降低。目前的一些改进算法都是尽可能地减少搜索 次数。a p r i o r i 算法主要是为了找出频繁集，真正影响效率的是对项目集及其支持度 的计算。如果在交易数据库中包含不同项目的数量为以个，以a p r i o r i 为基础的频繁 项目集算法将要验算2 n 个项目集，显然，当疗较大时，会引起组合爆炸。 针对这些不足，后来学者又提出了一些a # o r i 算法的优化算法，j s p a r k 【2 】等 人提出了一个基于h a s h 技术的算法，利用h a s h 技术有效地改进了候选项目集的生 成过程；减少i o 的存取时间，提高了效率。a s a v a s e r e 3 】等人提出了交易数据库进 行分区( p a r a g o n ) 的算法。它把数据库分成几个小块，分别在每个小块上寻找频繁项 目集，最后得到整个数据库上的频繁集，h t o i v o n e n 【4 】等人提出了基于随机抽样 ( s a m p l i n g ) 的算法，从数据库中随机抽样出一部分数据寻找频繁集。这几种优化方法 虽然有了不同程度的改进，但有些牺牲了一些精度，有些增加了c p u 的负担因而 只有从本质上减少候选集。减少对项目集支持度的计算时间，才能大大减少频繁项 目集生成的数量和缩短数据挖掘时间。 另外一种经典的频繁集算法是由h a n l 5 】等人提出的频繁模式增长 ( f r e q u e n t - p a t t e r ng r o w t h ) 的思想，简称f p - g r o w t h 方法。它的优点是不需要产生大量 的候选集，将发现长频繁模式问题转化为用递归方法来发现一些模式，然后连接后 缀，这样大大降低了搜索开销。可当数据库很大时，构造基于内存的f p g r o w t h 方法 是不现实的。 国内也有学者对a p r i o r i 的算法进行了改进 6 - s ，有的也提出了关联规则增量式 算法1 9 , 埘，也就是在原来的数据库中增加一条记录，如何得到更新后的关联规则。也 有学者从不同角度把其他方法应用于规则挖掘，这些方法包括粗糙集理论 1 1 - 1 3 1 ，概 2 华中科技大学硕士学位论文 念格理论等1 1 4 - 1 6 1 ，这些知识的应用，大大丰富了关联规则的挖掘方法，提高了规则 挖掘效率 概念格是数据挖掘的一种有力工具概念格的每个节点是一个形式概念，由外 延和内涵两部分组成。另外概念格通过h a s s e 图生动和简洁地体现了这些概念之间 的泛化和特化关系。人们可以从频繁结点中提取关联规则，而在已建成的格上提取 关联规则是最方便的，由此引出了建格理论。常用的建格算法有批处理算法和增量 算法【l ”。批处理方法根据其构造格的不同方式，可分为3 类：即从项向下算法，自 底而上算法，枚举算法。增量算法的基本思想是将当前要插入的对象和格中所有的 概念的外延作交运算，根据交运算的结果采取不同的行动。 粗糙概念分析是一种结合粗糙集和概念格的理论，按照粗糙集的理论，任一个 集合在概念格中并不都是精确的，因此可以模仿粗糙集的方法，生成所谓的“上近 似概念和下近似概念”，近年来关于概念格的上下近似问剧1 鲫”已有不少学者进行了 研究f 2 l - 2 3 1 我们将从粗糙集角度研究概念格，得到相应的上下近似概念 基于粗糙集的关联规则挖掘的方法主要是依据决策信息表来进行的。粗糙集本 身是一种刻划不完整性和不确定性的数学工具，能有效地分析不精确，不完备信息， 还可以对数据进行分析和推理，从中发现隐含的知识。它无需提供所需处理的数据 集合之外的任何先验信息，“让数据自己说话”。但该方法也存在一些不足：由于基 于粗糙集方法产生的候选规则多，几乎是所有存在的关联，再加上规则产生过程时 要对信息表进行约简和规则提取，计算量大，并且规则约简过程中容易造成规则丢 失。针对这些不足，后人陆续提出了一系列关于属性约简和规则提取的改进方法。 如：基于可分辨矩阵进行约简和规则等1 2 4 1 。由于粗糙集的各种优点，人们对粗糙集 理论的研究越来越多，不完备信息系统是其中的一个研究方向，主要是研究在数据 不确定的情况下，如何得到决策规则。国内外学者已经进行了一些研列2 5 - 2 8 1 。本文 将引入模糊度定义，对不确定性作定量研究，主要想法是构造出新的粗糙集，根据 粗糙集理论，找到上下近似，然后对此作进一步的研究。 公理化方法是粗糙集理论中的另外一个研究方向。国内外学者从不同角度出发， 提出了各种公理集 2 9 3 ”，如y y y a o 3 2 1 和吴伟志等 3 3 - 3 5 1 ，系统地提出了经典关系 3 6 - 3 s 华中科技大学硕士学位论文 和模糊关系 3 9 - 4 1 1 下的各类公理集。但这些公理集的独立性并没有得到证明。本文将 研究这些公理集，系统地进行整理并且对经典关系和模糊关系下的各种公理集的独 立性作证明。从而更清楚地看到粗糙集的本质特征 1 3 本文的组织结构 第二章先讨论关联规则的概念，介绍经典a 面o f i 的算法，着重说明本人对此所 作的改进。第三章针对目前概念格在规则提取中的特殊作用，对概念格的上下近似 问题作深入研究，从理论上证明已有方法的合理性，并提出选择方法。第四章研究 不完备信息系统，提出构建新的粗糙集，利用模糊数学方法进行决策。第五章研究 粗糙集理论中公理化问题，从理论上证明经典环境和模糊环境下的最小公理化问题。 第六章对本文作总结并提出展望。 4 华中科技大学硕士学位论文 2 关联规则算法的优化 2 1关联规则挖掘的概念 关联规则( a s s o c i a t i o n r u l e s ) 模式是数据挖掘模式中比较重要的一种，我们先 对它的一些基本概念作介绍。关联规则是指在大量数据之间存在的人们感兴趣的关 联或相关联系，侧重于数据的不同领域之间的联系。随着数据的积累，各行业人士 对于他们从数据库中挖掘关联规则越来越重视，有的规则是明确为大家所知的，比 如购买面包的人多数会赠买牛奶，有的则是不易发现的，比如为婴儿购买纸尿布的 父亲经常会顺便为自己购买一瓶啤酒。 关联规则的最初发现是通过超市中顾客的购物篮分析而得到的。a g r a w a l 等人 于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集闻的关联问题。购物篮分析的典型 应用是通过发现顾客放入其购物篮的不同商品之间的联系，分析顾客的购买方法和 习惯，通过了解哪些商品频繁地被顾客同时购买，分析得到所购商品之间的关联， 这种关联的发现可以帮助销售商制定营销策略。购物篮分析的典型应用可以帮助商 家设计各种商品在商场中的布局。一种策略是：经常一块购买的商品可以摆放得近 一些，这样可以促进这些商品一起销售。例如，如果顾客购买计算机也倾向于购买 软件，那么如果将硬件和软件摆放得近一些，就有可能增加二者的销售。另一种策 略是：将硬件和软件分别摆放在购物架的两端比较明显的位置，这就有可能使顾客 从一端走向另一端时一路挑选其他商品而达到促销目的。 定义2 1 设i = f l 兄，) 是一组n 个不同项目的集合，d 为事务数据库。 x 互j ，x 表示某事务中涉及的项目集，t i d 为事务标识符，则d 中的每一个元素( 事 务) 都可以表示为 t i d ，柳。例如，一个数据库d 见表2 - l ，它包含l o 条事务。如事 务l 用t 1 表示，它包含项目一，口，c ，d ，e 。即可表示为仃1 ， 爿，b ，c ，d ，e ，其余类推。 华中科技大学硕士学位论文 定义2 2 如果项目集工中有七个项目，称x 的长度或大小为七，此时项目集x 称 为j 项集。显然，z ，。 定义2 3 设石j ，l ，x n y = ，则x j ，称为关联规则，j 称为关联 规则的前件，j ，称为关联规则的后件，j 称为关联操作。 表2 - 1 事务数据库 z 搿l t e m s e t力di t e m s e t t l a 。b ，c ，d e t 6 c d t 2 a ，b ，d ，e t 7 曰c t 3 b c e ，f t 8 e f t 4 c 。d ，f t 9 厶c 。d ，e t 5ft 1 0 彳，b ，c 定义2 4 如果事务数据库d 中，有j 的事务包含了x u y ，则称关联规则 z y 具有支持度g 。支持度描述了x 和】，这两个项集的并集x u y 在所有事务中 出现的概率。s u 删x = y ) j x v i 硎，8 驯表示数据库。中的事务总数，0 z u 硎表 示同时含有x 和y 的事务个数。 定义2 5 如果事务数据库d 包含j 的事务中有c 同时也包含j r ，则称) | f j y 的置信度为c 。置信度c 就是指在出现了项集x 的事务中，也同时出现项集y 的 概率大小也可以理解为条件概率j p ( j ，i 柳c 。i l f i d 蚰c c ( j r 户与高产j 眵。表 示含有x 的事务个数。 关联规则的挖掘问题就是在事务数据库d 中找出大于或等于用户给定的最小支 持度m i n s u p 和最小置信度m i n c o n f 的关联规则，称为满足最小支持度和最小置信度 的关联规则，这种规则称为强规则。 6 华中科技大学硕士学位论文 定义2 6 如果一个j - 项集，它的支持度 m i n s u p ，则称该七顼集为频繁七项集， 所有频繁七项集的集合记作厶 性质2 1 如果一个七项集不是频繁的，则它的所有超集( 包含它的集合) 不可 能是频繁的。如果一个七项集是频繁的，则它的所有子集都是频繁的。 利用该性质，在确定候选集时，可以事先去掉一些不可能构成频繁集的集合。 挖掘关联规则问题可以分解为以下两个子问题。 1 ) 找出所有频繁项集，显然这些频繁项集的支持度 m i n s u p 2 )从频繁项集中产生强关联规则，进一步使这些规则的置信度 m i n c o n f 2 2 a p f i o r i 算法及其思想 算法的基本思想1 1 是先找出所有频繁l - 项集，这些项集组成厶，然后由厶产生 频繁2 项集厶，然后用上2 求出厶，以此类推直到没有新的频繁项集产生。从，到 丘的实现方法：首先把丘。与自身连接生成候选七一项集合，记为q ，形成c i 连接的 过程是：从丘一i 中取出l l ，1 2 1 l 脚表示i i 的第j 项，如果两者的前七一2 项相同，则 进行链接形成七一项候选项集i i 1 i i 2 i i k - 1 h k - h ，加入到q 中，然后对q 中的数 据项集频度进行统计，丢弃低频度的数据项集。q 中的每个元素需在交易数据库中 进行验证来决定其是否加入丘，这里的验证过程是影响算法性能的一个瓶颈。每求 一个五需要对数据库扫描一遍。为了提高生成频繁项集的效率，用到了数据项集的 一个基本性质。根据性质2 1 ，一个项集是频繁项集当且仅当它的所有子集是频繁集， 那么如果q 中某个候选七一项集有一个( 七一1 ) - 项子集不属于一，则这个候选七一项集 可以被修剪，不再被考虑，这个修剪过程可以降低计算候选集支持度的代价。 a p r i o r i 算法： 华中科技大学硕士学位论文 i n p u t ( 1 ) 格式为( z 磁，i t e m s e t ) 篚j 事务数据库d ，其中t i d 为事务标识符，i t e m s e t 为该事务所对应的项目集；( 2 ) 最小用户支持度m i n _ s u p o u t p u t ：所有的频繁项目集。 ( 1 ) , 1 - - f m d _ f 嘲u e m _ l - i t 锄s 盹；( d ) ；，找出所有的频繁l - 项集 ( 2 ) f o r o f 2 ；厶一l ；l ( 3 ) c i = a p r i o r i _ g e n ( 厶- l m i n s u p ) ； ( 4 ) f o r e a c h t r a n s a c t i o nt e dd o 胭描d 以计数 ( 5 ) g - = s u b s 烈( q ， ) 取出事务t 中包含的候选集 ( 6 ) f o r e a c h c a n d i d a t ec g ( 7 ) c c o u n t + + ； ( 8 ) ， ( 9 ) 厶2 c e g lc c o u n t _ _ m i n s u p ( 1 0 ) ( 1 1 ) r e t u r n 工= 厶求丘的并 其中，a p d o r i - g e n 是以频繁( 七一1 ) 一项目序列集丘一为自变量的候选集生成函数。 该函数返回包含所有频繁k 项目集的超集，分链接和修剪两步执行： 第l 步：链接( i o i n ) p r o c e d u r e a p d o r ig e n ( 一l ：f 搠u e n t ( k 一1 ) i t e m s e t s ；m i n s u p ) ( 1 ) f o re a c hi t e m s e ti le 丘一l ( 2 ) f o re a c hi t e m s e t1 2 e 厶。l ( 3 ) i f ( ( 1 1 1 = 1 2 1 1 ) a ( 1 1 1 2 = 1 2 1 2 ) a ( 1 i k - 2 】= h k - 2 ) a ( 1 1 【l ( - 1 】1 2 k - 1 ) t h e n ( 4 ) c - 1 1u1 2 ；连接，产生候选集 8 华中科技大学硕士学位论文 ( 5 ) i f h a s _ i n f r e q u e n ts u b s e t ( c ，上i i ) t h e n ( 6 ) d e l e t ec 修剪，去掉无用的候选项 仍e l s e a d d c t oc | ； ( 8 ) ( 9 ) r e t u r ng ； 第2 步：修剪( p r u n e ) p | d c e d u h a s _ i n f r e q u e n t _ s u b s e t ( c ：c a n d i d a t eb i t e m s e t ；厶- l ：f i e q u e n t ( k - 1 ) - i t e m s e t s ) ； 使用先前的知识 ( 2 ) i fj 厶。1 t h e n ( 3 ) r e t u r nt r u e ； ( 4 ) r e t u r l lf a l s e ； 对g 中的任一候选集c ，如果c 中存在一个不属于上扣。的长度为七一l 的子序列， 那么就从c i 中删除该候选c 从a p i o r i r 算法中可以看到，它是利用性质2 1 在候选项集确定时，使候选项集 尽可能的少，也即删除不可能项。判断q 中的某个七- 项集是否可删除，需验证它的 每一个( 七一1 ) - 项子集是否在厶。中，若不在上h 中，则从g 中删除这个七- 项集而 每验证一个，就要扫描一遍厶。 9 华中科技大学硕士学位论文 2 3 改进的方法和算法优化 在候选集中确定一个集合是否频繁，需要扫描整个数据库如果当前数据库中 有一些不必要的事务能够事先删除，则可减少扫描工作量。另外如果候选集中的元 素能够尽量少，即在产生候选集前，把某属性先去掉，这样组合数就少多了，于是 能减少计算量。现把两者结合起来一起考虑，即在产生k 项频繁项集后，去掉一些 非频繁项集，以免再次组合成候选项。去掉某些以后运算不必要的事务记录，它们 在产生k + 1 项频繁项集时不再被考虑计数问题。简化的过程类似于在矩阵中逐步去 掉行和列的过程。 下面举例说明简化的详细过程。首先把表2 1 中的事务表转化成布尔型的表，见表 2 2 。 表2 - 2 事务表转化成布尔型表 n d彳口cd ef t 1ll11l0 t 2 1l 011 o t 30l101 l t 4ooll01 t 5000o01 t 600l1o0 t 7011 0 0o t 8 00 oo1 1 t 9l011lo t 1 011l0o0 取最小支持度为2 0 。为了求频繁1 项集，进行列向计数，算出每个l 项集出现的 次数，结果放在最后一行，见表2 3 。 从表2 - 3 中，我们得到频繁l 项集： 椰， 占) ， c ， d ) ， 研， f ) 。它们的支持度都大 于2 0 。 1 0 华中科技大学硕士学位论文 表2 - - 3 卜项集列向计数结果 t i d4丑cdef t ll111lo t 2 1loll0 1 3 0ll0ll t 4o0 1 lo 1 t 500000l t 6o0ll0o t 70llo0o t 8 0oo011 i 9 10l 110 t 1 0lll0oo 457554 接下来是约简事务；从表2 3 中看出，事务t 5 中只包含单项集 叼，”不可能 再包含任一个链接后的2 项集或者| i 一项集( 七2 ) ，t 5 在以后统计更高阶的频繁集 时不再用到，为了提高扫描速度，删去t 5 ，所得结果见表2 _ 4 。 表2 4 行简化后的数据库 力d bcde， t 1 11 11l 0 t 2llol l 0 t 30ll011 t 400l10 1 1 6 0 0 1 1oo t 7 0l1oo0 t 8000011 i 9l ， o11l 0 t 1 01ll00 0 作链接构成候选2 项集，然后扫描计数，求出2 项集的支持计数，放在表的最后一 行。结果见表2 5 。 华中科技大学硕士学位论文 表2 - 52 - 项集列向计数结果 t i d 一占 彳ca d彳ef 丑cb db e b fc dc ec f d e d fe f t lllllo ll 1 olloloo t 2 1o 1 l 00ll000010o t 300o001011o1lo01 t 4ooo00ooo0l01010 t 600o000000l000 o 0 t 70oo0 01oo 0 o0o00o t 8ooo00 0o o oooo o o1 i 9o1 l 1o0000110l00 t 1 01100o10o0oooo0o 3333 o42 3 l4 3 2312 由表2 5 求出频繁2 项集为 a b ，( 彳c “彳d ) ， 一毋， 同回， 肋 ， b e ) ， c d ， c e ) ， c b ， 幽， e f ) ，非频繁项集 为 a f ， 剧7 ， d f ，因以后的频繁3 - 项集及频繁七一项集( | 3 ) 不可能包含这些 非频繁项集，所以从表2 5 中删除它们各自所在的列，结果见表2 - 6 。 表2 - 6 列简化后的数据库 t i d 爿口 彳ca d彳eb cb db ec dc ec fd ee f t 11l11i1l1l010 他l0llolloool o t 3000ol 0 l 0 l lo1 t 4 0 0 0 o 0 0o1ol00 t 6000o0oo1o0o0 t 700o0l0000000 t 8 0 00oooo0oo01 t 901ll000110l o ， t 1 0110 0 1 0 o 0 0 0 0 0 约简事务：从表2 - 6 中，可以看出事务t 6 ，t 7 ，t 8 分别只包含一个2 - 项集，这些事 务不可能包含链接后的3 项集。以后扫描时也不再计数，所以删掉事务i 6 ，t 7 ，t 8 华中科技大学硕士学位论文 所在的行，以精减事务数据库，结果见表2 - 7 。 表2 7 行简化后的数据库 z 搿一bc d彳e曰cb db ec dc e c f d ee f t 1lll1ll111ol 0 t 21oll011 o0o 1 0 t 3 o o o0lolollol t 4o0 0 o o00l01o0 t 9 0 l 11o0ollo1o t 1 0 11oo1oo0000o 继续作链接，求出候选3 项集扫描数据库，计算结果放在最后一行，见表2 - 8 。 表2 - $ 3 - 项集列向计数结果 矗矗a b c母za 8 e4 c 三彳( 氇一d 君c b c eb d ec d 点c d fc e f t 111 1 ll 1 l 1110o t 20 1 lool0ol0o0 t 3 o00o000l0o0l t 4000000000o10 i 90o0l11oool00 t 1 010 0 00oo 0 0 0 0 0 22222312221l 从表2 - 8 ，得到频繁3 项集： a b c ， a b d ， a b e ， a c d ， a c e ， a b e ， b c e ， b d e ， o d e ， 同理删去非频繁项集： b c d ， c d f ， c e f ) ，结果见表2 - 9 。 因事务b 不含3 项集，t 4 ，t 1 0 只含一个3 项集，它们都不可能再包含链接 后的4 项集。所以t 3 ，i 4 ，t 1 0 都可去掉。精减后结果见表2 - 1 0 。 华中科技大学硕士学位论文 表2 - 9 列简化后的数据库 力da b c a b da b ec d彳c ea d eb c eb d ec d e t 1 l1lllllll t 2 o1100l01o t 30000o 0 ooo t 40o0o oo1oo t 9 00011100l t i oloooo0ooo 表2 1 0 行简化后的数据库 t 继a b ca b da 8 e4 c d( 氇a d e8 c e b d ec d e t 1l1l11l111 t 2o110o1olo t 9o00ll1o o 1 作链接，扫描数据库，计数结果见表2 - l l 最后一行。 表2 1 14 一项集列向计数结果 乃da b c da b c ea b d ea c d e t 1 l lll t 20o10 t 9oo0l 得到频繁4 - 项集： a b d e ， a c d e ) 。 22 去掉非频繁项： a b c d ， a b c e ，结果见表2 1 2 。 华中科技大学硕士学位论文 表2 1 2 列简化后的数据库 t i d a b d ec d e t 111 t 21o 3 9o1 约简事务：去掉亿，t 9 ，它们只包含一项4 _ 项集，同理可删除掉，结果见表2 1 3 。 表2 - 1 3 行简化后的数据库 因a b d e 和a c d e 无法链接成5 项集，所以频繁5 - 项集为空。( 即使可链接，也 肯定是非频繁集了因为计数最多只能是1 ) 。最后得到频繁4 - 项集： a b d e ， a c d e ，它们的所有子集都是频繁集。 最后得到的所有的频繁集如下； 频繁l 项集： 爿) ， b ) ， c ，( d ，怛) ， f ) 频繁2 项集： 彳b ， 彳c ， 彳d ) ， 一毋， 丑c ， 肋 ， 髓 ， c d ， c 毋， c ，) ， d 毋， 砑) ， 频繁3 - 项集： a s c ， a b d ， a b e ， a c d ， a c e ， a d e ， 战强 ， b d e ， c d e 频繁4 项集： a b d e ， a c d e 2 4 优化算法的伪代码及实验结果比较 以项集i 中的每一项为列，事务数据库d 中的每一个事务为行，构造关联矩阵 m m n 】，其中n 为i 中项目总数，m 为事务数据库d 中含有事务总数。对于第i 个事务，如果该事务中含有项目j ，则令m 【i j 】= l ，否则令m i j = 0 。 在关联矩阵m 中，行向量既表示每条事务所含的项目，也蕴涵了事务的相似性； 列向量既反映了每个项在事务中的访问情况，也蕴涵了列之间的相似性，可以通过 华中科技大学硕士学位论文 计算列向量的相似性来挖掘更长的频繁模式。 算法思想： 1 对关联矩阵m 的每一列进行求和，如果求和的结果超过给定的最小支持度 阈值，则该列为频繁项集所在的列，否则为非频繁项集所在的列。 2 剔除所有非频繁项集所在列，剔除后的关联矩阵中，若某行的元素值全为0 或最多只有一个是l ，则删除该行； 3 在约筒后的关联矩阵的每一列做如下处理： 1 ) 两列合并：设矩阵中每列的标识项都已按字母顺序排列，如果矩阵中的某两列 各自的标识项中只有最后一个不相同，则两个标识项可以合并成新的项。新标识项 的长度比原来多l ，其前面的公共部分不变，后面的两项分别取自原来两个标识项中 的各自的最后一个。如：原来的两个标识项为a b c d ，a b c g ，则合并成a b c d g 2 ) 新标识项的列元素为原来两个对应的列作逻辑与运算得到，形成新的列。 3 ) 继续找下一对进行合并，直到找不到为止。这样形成新的标识项矩阵仍称为 关联矩阵，每个标识项的长度为原来加1 。 4 重复步骤l 步骤3 ，直到关联矩阵为空或只含有一列。 为实现上述算法思想，特定义以下数据结构： # d e f i n e 砌删关联矩阵的最大行数 # d e f i n ec m a x 关联矩阵的最大列数 t y l e c l e f s t m c t i n t r o ws i z e ，c 邮协；r o w - - s i z c ：关联矩阵实际行数，e m l _ s i z c ：关联矩阵实际列数； i n tm r m a x + i c m a x + i ；关联矩阵 i n tc o l - i t e l i l s 【c m a ) q 【n 】；，关联矩阵的列标识，n 为项目总数； ) m a t r i x ； 根据以上算法思想，设计具体算法如下： 输入：初始关联矩阵m ，最小支持度c 输出：频繁模式 m a t r i x r o ws i z e = 事务总数； m a t r i x c o ls i z e - i 中所含项总数： 1 6 华中科技大学硕士学位论文 初始化m a t r i x m ；初始化m a t r i x c o l _ i t e m s ； 姻l 蜘= o 全局变量，用于记录当前要求的频繁项集的长度，即频繁集中含的频繁 项个数； w h i l e ( m a t r i x m 至少含有两列以上) c o u n t - - - 0 d 频繁项集计数 f r e q _ l e n + + ； c t e m p + 】= o ； f o rk = lt om a t r i x c o l _ s i z ed o f o r j = lt om a t r i x r o w _ s i z ed o c t e m p k = c t e m p 啕+ m a t r i x m 吲 i f c t e m p k 弦c m a l r i x c o l _ s i z e t h e n c 0 删1 什+ ； 输出第k 列所含的项标识集以及支持度c t e m p 啕； ) e l s e f o ri ：4 【+ lt om a t r i x c o ls i z ed 删除第k 列 m a t r i x m r 】【j - 1 = m a t r i x m 【】d 】； m a t r i x c o l s i z e - ； f o rk = - it om a t r i x r o ws i z ed o n o n z e r o = 0 ； f o r j = lt om a t r i x c o l _ s i z ed o f f m a t r i x m 啕圃! ；ot h e n n o n z e r o + + ； i f n o n z e r o ) 2 0 ( 4 ，6 ，l o ， e ，k ) ) 2 l ( 4 ，5 ，6 ，8 ，1 0 ，1 2 ，1 3 ， e ，f ) ) 2 2 ( 1 1 ，2 ，3 ，4