（计算机应用技术专业论文）高效用项集挖掘算法的研究.pdf

硕l ：学化论文 摘要 关联规则挖掘作为数据挖掘的一个重要研究领域，通过各事务项集之间的相 关联系，给用户提供感兴趣的规则，在商业、科学和其它应用方面得到了广泛应 用。但是，传统的关联规则挖掘基于“支持度置信度”框架产生强关联规则，只 考虑了项集的频繁度，因此用户未必对挖掘产生的规则感兴趣，而且很可能会丢 失那些支持度1 高、但效用值高的规则。基于效用的关联规则挖掘弥补了这一缺 陷。它用效用值来衡量项集的重要性，反映了用户偏好，更好地满足决策需求。 本文从提高高效用项集挖掘性能的角度出发，主要工作有： 分析了目前高效用项集挖掘算法的优点和不足，设计了一种新的快速高效用 挖掘算法f u i m i n e 。f u l m i n e 将原数据集进行分类存储，显著减少搜索时间， 不需要重复扫描原数据集。同时构造一种新的数据结构f u l t r e e ，按分类后的项 集分别构造f u l t r e e 并独立进行挖掘，只需要扫描叶子结点就可得到高效用项 集，避免了递归地对f u i t r e e 进行搜索。实验证明，该算法在挖掘项集最大值相 对较小的数据集时，执行效率上要明显优于同类算法t w o p h a s e 和c t u m i n e 。 f u i m i n e 算法能快速得到数据集中的长模式效用集，但短模式效用集的挖掘 成了其挖掘效率的瓶颈，因此提出一种结合f u i m i n e 算法和列枚举分别挖掘长 模式和短模式的混合挖掘算法h y b i r d m i n e 。列枚举挖掘采用垂直数据格式通过 事务的交集运算，直接得到短项集。同时本文给山项集的后续补集对列枚举方法 进行优化，最人程度上减少了项集的相交次数和存储空间。事务权重向下闭属性 剪枝策略同样适用于列枚举，提前将不满足最小效用阀值的项集剪枝，减少了搜 索空问。实验证明，混合算法h y b i r d m i n e 弥补了f u i m i n e 算法的缺陷，提高了 挖掘短模式的效率。 当前高效用挖掘算法都是挖掘出完全的高效用项集，当最小效用阀值m i n u t i l 设置较低或数据集中存在长模式，会产生大量数目的效用项集。因此，本文分析 效用挖掘的现实意义，通过结合支持计数和效用的数学特性，将闭模式约束引入 到高效用项集挖掘中。在不影响决策者的分析知识下，减少高效用项集挖掘所产 生的项集模式数量。最后给出基于枚举的闭模式约束的项集挖掘算法c h u m i n e 。 实验证明c h u m i n e 算法显著地减少了效用项集挖掘数量，并提高了项集产生的 效率。 关键词：数据挖掘；关联规则；高效用项集；列枚举；闭模式 高效用项集挖掘算法的研究 a b s t r a c t t h ea s s o c i a t i o nr u l e m i n i n g ( a r m ) a i m sa ta n a l y z i n g t h e i n t e r e s t i n g c o r r e l a t i o n sb e t w e e ni t e m sa n de x t r a c t i n gr ui e sf o ru s e r s a r mi so n eo ft h em o s t i m p o r t a n tr e s e a r c hf i e i d so fd a t am i n i n ga n dh a st r e m e n d o u sa p p l i c a t i o n si nb u s i n e s s ， s c i e n c ea n do t h e rd o m a i n s h o w e v e r ，t h et r a d i t i o n a la r mw h i c hg e n e r a t e ss t r o n g a s s o c i a t i o nr u l e sb a s e do n ”s u p p o r t c o n n d e n c e ”m o d e l ，o n l yc o n s i d e r st h ef t e q u e n c y o fi t e m s e t s ，s ot h eu s e rm a yn o tb ei n t e r e s t e di nt h er e s u l t s ，a n dc a nn o td i s c o v e rs o m e r u i e st h a th a v eal o ws u p p o r tb u tah i g hu t i l i t y u t i l i t y - b a s e da s s o c i a t i o nr u l em i n i n g h a sd e 疥n e dt om a k eu pf b rt h i sd e f i c i e n c y i tu s e su t i l i t yt om e a s u r et h ei m p o r t a n c eo f i t e m s e t s ，r e f i e c t st h eu s e r p r e f c r e n c e s ，a n db e t t e rm e e tt h en e e d so fd e c i s i o n - m a k i n g t bi m p r o v et h ee f f i c i e n c yo fh i g hu t i l i t yi t e m s e t sm i n i n gi st h ep u r p o s eo fo u rs t u d y t h em a i nw o r k so ft h ep a p e ri n c l u d e ： a n a l y z e dt h ea d v a n t a g ea n ds h o r t c o m i n go ft h ec u r r e n th i g hu t i l t ym i n i n g a i g o r i t h m s ，a n dp r e s e n t a ne f n c i e n t a 培o r i t h m ，t h e f a s t u t i l i t y i t e m s e t s m i n i n g ( f u i - m i n e ) i ti sa ni m p r o v e dw a yt op a r t i t i o nt h eo r i g i n a ld a t a b a s e ，w h i c hr e s u l t s f o mc l u s t e r i n gt r a n s a c t i o n s ，n o to n l ys i g n i f i c a n t l yr e d u c et h es e a r c ht i m e ，b u td o e s n o tn e e dt or e p e a tt h es c a n t h e ni tc o n s t r u c t san e wd a t as t r u c t u r en a m e df u i - t t e e ， w h i c hi sf o rc o m p r e s s e ds t o r a g ea n dm i n i n gi n d e p e n d e n t a hh i g hu t i l i t yi t e m s e t sa r e g e n e r a t e db yc h e c k i n gt h el e a v e so fe a c hf u i - t r e e ， w i t h o u tt r a v e r s i n gt h et r e e r e c u r s i v e l y e x p e r i m e n t a lr e s u i t ss h o wt h a t ，w h e nt h e n u m b e ro ft h ei o n g e s to ft h e i t e m s e t si nt h ed a t as e t si ss m a li e r ，t h ee 踊c i e n c yo ft h ea l g o r i t h mi ss i g n i n c a n t l y p r e f c c tt o i w o - p h a s ea n dc t u m i n e ，w h i c ha r er e p r e s e n t a t i v eo n e si nc u r r e n th i g h u t 1 i t yi t e m s e t sm i n i n ga i g o r i t h m s f u i - i i n ea i g o r i t h mc a nq u i c k l yg e tt h el o n g e ru t i l i t yp a t t e r n s ，b u tt h es h o r t e r u t i l i t yp a t t e r n sm i n i n gi st h eb o t t l e n e c kf o rw h o i em i n i n ga l g o r i t h m s oah y b r i d a l g o r i t h mn a m eh y b i r d - m i n e i s p r o p o s e dt os o l v ei t t h eh y b r i d - m i n ea l g o r i t h m c o m b i n et h ef u i - m i n ea n dt h ec o i u m ne n u m e r a t i o nm e t h o d ，w h i c ht h ef o r m e rt om i n e t h el o n g e rp a t t e r n sa n dt h eo t h e ru s e dt om i n et h es h o r t e ro n e s i nt h ec o l u m n e n u m e r a t i o nm e t h o d ，i tm a k e st h ed a t as e tt ov e r t i c a ld a t af o r m a t ，a n di n t e r s e c t st h e t r a n s a c t i o nt og e tt h ea l ls h o r ti t e m s e t sd i r e c t l y t h e nt h eb a c k - c o m p i e m e n ti sd e n n e d i nt h ep a p e rt oa c h i e v et h eo p t i m i z a t i o no ft h ec o l u m ne n u m e r a t i o nm e t h o d ，a n d m i n i m i z et h en u m b e ro fi n t e r s e c t i o no ft h ei t e m s e ta n ds t o r a g es p a c e t h et h e o r yo f i i 硕i ：学位论文 t r a n s a c t i o nu t i l i t yc l o s e dd o w na l s oa p p l e st ot h em e t h o da n dc a np r u n ea m o u n to f t h ei t e m s e t s ，w h i c ht h et r a n s a c t i o nw e i g h t e du t i l i t yi si o w e rt h em i n i m u mu t i l i t y ，a n d r e d u c e st h es e a r c hs p a c e e x p e r i m e n t ss h o wt h a tt h eh y b i r d - m i n ea l g o r i t h mp e r f e c t s t h ef u i - m i n ea n di m p r o v e st h em i n i n ge 衔c i e n c yo fs h o r tp a t t e r n s c u r r e n t i y ，t h eh i g hu t i i i t ya l g o r i t h m sp r o p o s e d a r ed e s i g n e dt oe x t r a c tt h e c o m p l e t ep a t t e r n s i tw i l la c h i e v ea m o u n to fu t i l i t yi t e m s e t sw h e nt h et h r e s h o l d s e t t o ol o wo re x i s t s i o n gp a t t e r n i nd a t as e t t h e r e f 6 r et h r o u g ha n a l y z e st h er e a li t y m e a n i n ga n dt h em a t h e m a t i c a lf e a t u r eo ft h es u p p o r tc o u n ta n du t i i t y ，ah i g hu t i li t y i t e m s e tm i n i n gm e t h o dc o m b i n i n gw i t ht h ec i o s e dp a t t e r nc o n s t r a i n ti sp r o p o s e d i n t h i sp a p e r 1 tc u t sb a c kt h en u m b e ro fh i g hu t i l i t yi t e m s e t sw i t h o u tr e d u c et h ee f 代c t d e c i s i o nf 0 ru s e r s f i n a l l y ，ah i g hu t 1 i t yi t e m s e t sm i n i n ga l g o r i t h mb a s e do nc l o s e d c o n s t r a i n t ( c h u m i n e ) w i t hs o m ee x p e r i m e n t si sp r e s e n t i tp r o v e st h a tc t u m i n e a i g o r i t h me f n c i e n t i y d e c r e a s e st h eq u a n t i t yo fm i n i n gr e s u l t s ， a n ds i m u i t a n e o u s i y i m p r o v e st h ea l g o r i t h me f 托c i e n c 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 ；h i g h u t i l i t yi t e m s e t ；c o l u m n e n u m e r a t i o n ；c i o s e dp a t t e r n l i l 高效用项集挖掘算法的研究 插图索引 2 1a p r i o r i 算法核心部分9 2 2t w o p h a s e 算法描述17 2 3c t u m i n e 算法描述j 1 9 3 1 通过划分数据进行挖掘2 l 3 2 快速高效用挖掘算法2 3 3 3 子过程k u i t e m s e t sg e n 2 3 3 4 子过程k - f u i - t r e e g e n 2 4 3 5 高效用k 项集挖掘2 5 3 6 划分后的分类2 6 3 7 实例分析图2 7 3 8 三种算法在t l o i l 0 d l o k 数据集的执行时间2 9 3 9 三种算法在t l o l 5 d 1 0 0 k 数据集的执行时问2 9 3 1 0f u i m i n e 算法在m a xp l a n 值不同时的执行时间3 0 4 1 列枚举树3l 4 2 混合挖掘算法3 3 4 3 项目交集完全图3 4 4 4 优化后的项目交集完全图3 5 4 5 、f 均模式长对长度阀值的选取影响3 6 4 6 两种算法在t 1 0 1 1 0 d 1 0 k 的执行效率比较3 6 4 7 两种算法在t l o l 5 d l o o k 的执行效率比较3 7 5 。1 闭模式挖掘结果示意图3 9 5 2c h u m i n e 算法4 2 5 3 两种算法在t l o l 5 d 2 0 0 k 的执行效率比较4 3 5 4i 种算法在t 5 1 5 d 2 0 0 k 的执行效率比较4 4 v i 图图图图图图图图图图图图图图图图图图图图图图图图 硕 ：学位论文 附表索引 表2 1o o a 挖掘结果示例1 3 表2 2 某文具店事务数据1 5 表2 3 商品利润表15 表5 1 项集效用值与支持度比较表4 l 表5 2t w o p h a s e 和c h u m i n e 算法效用值数量比较4 3 v u 硕i ：学化论文 1 1 研究背景及意义 第1 章绪论 随着数据库技术和网络技术的广泛应用，人们可跨越时空在互联网上随意交 换数据信息和协同工作。这样，人们所拥有的数据量不再局限于本部门、本单位 和本行业的范围，而是浩瀚无垠的信息海洋。面对激增的数据，人们亟需一种技 术从数据汪洋中将存储数据转换成有用信息，给决策者提供有价值的知识。传统 的数据库技术虽然可以较好地实现数据的录入、查询和统计等功能，但无法发现 数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势，从而导致 “数据丰富，知识贫乏”【1 】的现象。在这种背景下，知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，简称k d d ) 及其核心技术数据挖掘( d a t am i n i n g ，简称d m ) 便应运而 生j 并得以蓬勃发展。 数据挖掘于2 0 世纪8 0 年代后期发展至今，是解决当今时代所面临的“数据 爆炸而信息贫乏”问题的一种有效方法，它从大量的、不完全的、有噪声、模糊 的、随机的实际应用数据中，发现并提取隐含在其中未知的、可信的、有用的模 式的过程。数据挖掘能够智能地、自动地把数据转换成决策者需要的信息，不仅 可以帮助人们从数据库和数据仓库存储的相关数据中提取感兴趣的知识、规律或 更高层次的信息，而且可以从不同角度上去分析它们，从而更有效地利用数据。 目前，数据挖掘技术在货篮数据分析、金融风险预、产品质量分析、电信、分子 牛物学、基因丁程研究、i n t e m e t 站点访问模式发现以及信息搜索等领域得到了广 泛的应用。 关联规则( a s s o c i a t i o nr u i e ) 是数据挖掘三入领域( 关联规则，聚类，分类) 之一， 是分析数据并从中发现有用信息的一种手段。它通过分析数据库各事务之间的联 系，从中得到令人感兴趣的规则。a g r a w a l 【2 】等于1 9 9 3 年首次提出在顾客交易数 据库中挖掘项集间的关联规则问题，对用户购物篮进行分析，发现不同商品之间 的联系，通过这砦规则找出顾客购买行为模式，有利于商场管理者对商品进行货 架设计、存货安排以及根据购买模式对用户分类。以后诸多的研究人员从不同角 度对关联规则的挖掘问题进行了大量的研究。 在现实中，数据库中事务的项集根据不同用户的兴趣爱好具有不同的属性特 征。但存传统的关联规则挖掘中，为简化关联规则的挖掘，这些属性特征往往被 忽略。近年来，基于效用数据挖掘( u t i l i t y i b a s e dd a t am i n i n g ，简称u b d m ) 将项 集的特征因素引入到挖掘的事务集中，提升所发现知识的效用度，引起广泛学者 高效用项集挖掘算法的研究 的研究兴趣。人们开始重视对关联规则的效用研究，而不仪仪针对挖掘算法效率 的提高。本文对高效用关联规则挖掘进行详细研究，使用户在挖掘过程中可以根 据自己的兴趣爱好设置项集的属性值，最终产生的挖掘结果具有语义特征，让用 户得到真正自己感兴趣的知识。 1 2 关联规则研究概况 1 2 1 数据挖掘研究现状 1 9 9 8 年8 月，在美国底特律召开的第1 1 届国际联合人工智能学术会议上， 首次提出数据库中的知识发现( k d d ) 概念，接着在1 9 9 1 、19 9 3 、19 9 4 年分别举行 k d d 专题讨论会。随着k d d 在学术界和工业界的影响越来越大，国际k d d 组 委会于1 9 9 5 年将专题讨论会更名为国际会议。在加拿大蒙特利市召开的第l 届 k d d 国际学术会议上，正式提出数据挖掘这一术语。迄今为止，由美国人工智能 协会主办的k d d 国际研讨会已经召开了1 5 次，规模由原来的专题讨论会发展成 为国际学术顶级会议。k d d 与数据挖掘已成为当前计算机科学界的一大研究热 点，不仅在其他内容的专题会议将其列为议题之一，同时在数据库、人工智能、 信息处理、知识工程等领域的国际学术刊物也分别开辟了k d d 专题或专刊，如 在l e e e ( 1 n s t i t u t eo fe l e c t r i c a l a n de l e c t r o n i ce n g i n e e r s ) ，a c m ( a s s o c i a t i o no f c o m p u t i n gm a c h i n e r y ) 等著名学会中列有会议议题或出版专刊。 目前，数据挖掘与k d d 研究重点从当初的理论研究方法逐渐转向系统应用， 并且结合了多种发现策略和技术，以及多种学科之间的相互渗透【3 4 】。一些同际性 大公司如i b m 、g t e 、s a s 和m i c r o s o f t 等，相继开发出一些实用的数据挖掘商 业系统和原型系统，如市场分析用的b e h a v i o r s c a n 、e x p l o r e r 、m d t ( m a n a g e m e n t d i s c o v e r yt 0 0 1 ) ，金融投资领域的s t o c ks e i e c t o r ，欺诈预警用的f a l e o n 等。在我 国，数据挖掘技术的研究也引起了学术界的高度重视，并逐步成为科学界的热点 研究课题。与国外相比，国内对数据挖掘和知识发现的研究稍晚，没有形成整体 力量。1 9 9 3 年国家自然科学基金首次支持了对该领域的研究项口，接着国内的科 研单位和高等院校相继对知识发现的基础理论及其应用展开研究。如今，数据挖 掘技术正朝着应用化方向迅速发展，涌现了许多新的研究方向，本文研究的高效 用项集挖掘就是其中之一。 1 2 2 关联规则挖掘算法研究 采用关联规则对大型数据库进行模式挖掘是数据挖掘的一个重要研究内容。 关联规则挖掘的对象一般是事务数据库，这种数据库主要应用在零售业，比如超 级市场的销售管理。关联规则挖掘目的为发现事务数据库中不同商品之间的某种 关联关系。通过这些规则找出顾客购买行为模式，为决策者提供有效信息，从而 硕f ：学化论文 提高销售利润。 目前关联规则挖掘算法的研究主要集中在如何快速有效地提取频繁模式，其 中频繁模式是指在数据中频繁出现的模式。研究的关键点在于对属性集进行充分 地剪枝，尽最大可能减少候选项集数量，另外最少次数地扫描事务数据库，从而 提高算法的效率。在早期的关联规则挖掘研究中，有学者提出a i s 【z j 及s e t m 【5 l 算法，但是它们在挖掘中生成大量不必要的候选集，性能不佳。凶此，研究者对 关联规则问题进行了大量研究，提出了许多更有效的挖掘算法，典型的有 a p r i o r i l 6 】、f p g r o w t h i7 。其中a p r i o r i 算法采用逐层搜索的迭代方法，不断产生、 测试候选项集，直到所有候选项集被检验完。a p r i o r i 算法采用频繁集向下封闭的 特性剪枝，在进行下一次迭代产生频繁项集时，大量的非频繁候选项集被剪除， 其性能较a i s 及s e t m 有明显提升。为进一步提升a p r i o r i 挖掘效率，随之提出 了许多a p r i o r i 算法的变形。例如，s a v a s e r e 等人提出了基于划分技术的算法i 8 1 ， p a r k 等提出了利用散列技术压缩候选集【9 1 ，b r i n 等人提出了对候选项目集进行动 态支持度计数的d i c 算法f l o 】，文献 1 l ，1 2 】提出了基于a p r i o r i 框架的并行关联规 则挖掘。 a p i r o r i 的候选产生检查方法显著压缩了候选集的大小，但也存在一些缺陷： ( i ) 它口j 能产生大量候选项集。例如，当长度为l 的频繁属性集有1 0 4 个的时候， 长度为2 的候选集个数将会超过1 0 7 个；( 2 ) 在进行长模式挖掘时，需要对数据集 进行多次扫描以进行各候选模式的支持度计算。针对这些问题，研究者提出了不 产生候选集的f p g r o w t h 、m a x m i n e r 【l3 1 、t r e e p r o i e c t i o n 【1 4 】及d e p t h p r 0 i e c t 【1 5 】等算 法。f p g r o w t h 采用如下分治策略：将提供频繁属性集的数据库压缩到一棵频繁 模式树( f p t r e e ) ，但仍保留项集关联信息；然后将这种压缩后的数据库分成一组 条件数据库，每个关联一个频繁项，并分别挖掘每个条件数据库。由于使用了压 缩的数据表达，同时不需要生成候选集，f p g r o w t h 对不同长度的规则都有很好 的适应性，同时在效率上比a p r i o r i 算法有显著提高。 不同于以卜两种经典的挖掘算法，研究学者还提出了许多其他的方法来提高 关联规则挖掘算法的性能。例如，文献 16 】提出了同时利用自底而上( b o t t o m u p ) 和自顶而下( t o p d o w n ) 两种搜索方法进行挖掘的p i n s 9 卜s e a r c h 算法，z a k i 等提出 的m a x c i i q u e t 和m a x e c l a t 算法【 j 不但采用混合搜索方法，还采取垂直的数据存 储方式。文献 1 8 ，19 】提出了分布式关联规则挖掘，文献 2 0 】提出了利用采样方法 减少数据库扫描次数的有效算法。 1 2 3 多种扩展形式的关联规则研究 除了对关联规则算法性能上的提升研究外，许多新的方法被提出来扩充关联 规则的挖掘。主要工作集中在如下几个方面： 高效用项集挖掘算法的研究 ( 1 ) 挖掘压缩模式的关联规则挖掘 由于完全频繁项集产生大量的冗余模式，因此不少学者提出各种形式的压缩 挖掘。如闭频繁项集挖掘【2 卜2 5 】只产生闭模式项集，指不被任何其他具有相同支持 率的频繁模式所包含的频繁模式，极大频繁模式挖掘【2 6 ，2 7 】只挖掘出不被任何其他 频繁模式所包含的频繁模式。 ( 2 ) 不同模式类型的关联规则挖掘 除了对事务集的挖掘产生频繁模式项集外，不同类型的模式挖掘被提出，如 文献【2 8 】提出含有负模式的关联规则挖掘，文献 2 9 】描述了针对序列数据类型的序 列模式挖掘，挖掘数据与时间相关的周期关联规则挖掘在文献 3 0 】给m 等。 ( 3 ) 属性扩展的关联规则挖掘 对于许多应用，在低层或原始抽像层的数据项之间很难找出强关联规则。因 此将关联规则从概念层次上进行扩展，提出多层关联规则【3 i 】挖掘来发现较高层的 强关联规则。另外从属性维度上进行扩展，可以得到多维关联规则挖掘1 3 2 】，如数 据仓库的数据集属于多维的。 ( 4 ) 基于约束的关联规则挖掘 数据挖掘可以从给定的数据集中发现大量的规则，但并不是所有的规则都与 用广相关。因此让用户的直觉或期望作为限制搜索空间的约束，提出基于约束的 关联规则挖掘【3 3 】。约束的条件包括知识类型约束、数据约束、维层约束、兴趣度 约束、规则约束等。 ( 5 ) 其他方面研究 其他对关联规则的扩展方面有对已发现的关联规则有效地进行维护的增量更 新算法【3 4 1 、关联规则挖掘和查询语言的研究【3 引、关联规则的可视化【3 6 】及事务间 的关联规则( i n t e r t r a n s a c t i o n ) 的研究1 3 7 】等。 1 2 4 基于效用的关联规则挖掘 传统关联规则基于“支持度置信度 框架产牛强关联规则反映事务问的相关 性，但在挖掘时只考虑了项集的频繁度，忽略了项集本身固有的属性，凶此用户 未必对挖掘产生的规则感兴趣，而且会让一些支持度不高、但效用很高的模式丢 失。近年来，文献【3 8 】对效用挖掘模型进行了定义，提出基于效用关联规则的挖 掘( u t i l i t y - b a s e da s s o c i a t i o nr u l em i n i n g ，简称u b a r m ) ，引起了广泛学者的研究， 已有不少算法提出对高效用项集进行挖掘【3 9 。5 1 。2 0 0 5 年在芝加哥举办了首届 u b a r m 研讨会，将效用因素引入到数据挖掘中的各个领域。u b a r m 根据项集 的效用值来衡量项集的重要性，认为只有那些带来高效用的规则才是用户真正感 兴趣的，打破了传统关联规则中频繁集模式的“支持度置信度”框架。由于效用 表达了项集的语义特性，能较好反映用户的需求，基于效用的关联规则在购物篮 硕l ：学化论文 分析、网页分析等各方面得到了很好的应用。 目前已有的高效用项集的挖掘算法中，u m i n i n g 【3 9 】和t w o p h a s e 【4 0 1 采用了类 似a p r i o r i 的候选集“产生检测”的方法，前者通过计算效用值的期望值对非高 效用项集进行剪枝，后者提出事务权重向下闭属性，减少候选项集的数目。文献 【4 1 】提出在高维大数据集的高效用项集挖掘算法，文献【4 2 】的压缩事务模式挖掘 c t u m i n e 算法，使用模式增长方法来挖掘高效用项集，自顶向下搜索全部高效 用项集。针对c t u m i n e 不能很好的在稀疏数据集进行挖掘，c t u p r o 【4 3 】采用自 底向上的搜索方式，构造映射树得到挖掘结果。文献【4 4 】提出快速效用- 频繁挖掘 算法f u f m ，以效用值和支持度两者兴趣度度量项集挖掘的结果。在文献【4 5 】中 对效用挖掘的有关模型进行了总结。 1 3 论文的工作 从上文的关联规则挖掘概况可知，传统的支持度关联规则由于过度简化项集 的意义，挖掘结果从很大程度上无法真正满足用户的需求。不少研究者从各个方 面对关联规则进行不同方面的扩展，以提升用户对关联规则挖掘结果的兴趣度。 其中，高效用关联规则将效用凶素引入到关联规则中，挖掘结果体现了项集的语 义特性，更好地反映用户的需求。因此本文对高效用项集挖掘进行详细研究，将 关联规则挖掘按项集效用进行分类描述，同时介绍高效用挖掘的基本概念和两种 应用最广泛的挖掘算法，给m 了一种快速的高效用项集挖掘算法及混合挖掘算法， 提出了基于闭频繁约束的项集挖掘问题及算法，主要工作如下： ( 1 ) 提出一种新的快速的基于效用关联规则挖掘算法。现有的基于效用关联 规则挖掘算法如u m i n i n g 和t w o p h a s e 采用了类似a p r i o r i 的候选集“产生测试 的方法，需要多次扫描数据集，并产生大量的候选项集，影响挖掘算法的效率。 c t u m i n e 和c t u p r o 算法采用类似于f p t r e e 结构，分别以自顶而下和自底而 上的方法进行高效用值挖掘。它对项集进行压缩存缩，不需要第二次对数据库进 行扫描。但其结点信息存储量大，挖掘过程中需要递归遍历树结构进行挖掘。因 此本文提出一种新的高效用挖掘算法f u i m i n e ，它将原数据集进行分类存储，大 量减少搜索时间。同时分类后的事务以f u i - t r e e 结构存储项集信息，只需要扫描 树中的叶子结点即可得到高效用项集。 ( 2 ) f u i 算法能快速得到数据集中的长模式效用项集，但短模式项集的挖掘严 重影响了f u i m i n e 挖掘性能。因此提出一种将f u i m i n e 算法和列枚举分别挖掘 长模式和短模式的混合挖掘算法。在列枚举挖掘短模式项集时，与频繁集挖掘类 似，采用垂直数据格式通过事务的交集运算，直接得到短项集。但是，随着模式 长度的增加，项集间两两相交产生越来越多的重复项集，浪费了大量的时间和存 储空间。因此本文提出项集的后续补集的定义，将项集与其后续补集进行相交， 高效用项集挖掘算法的研究 最大程度上减少了项集的相交次数和存储空间。同时，采用新的交集方法后，事 务权重向下闭属性剪枝策略同样适用于列枚举，提前将不满足最小效用阀值的项 集剪枝，减少了搜索空间。 ( 3 ) 当前高效用挖掘算法都是挖掘出完全的高效用项集，当最小效用阀值 m i n u t l i 设置较低或数据集中存在长模式，会产生大量数日的效用项集。用户往往 需要花费大量时间从挖掘结果中得到有效的信息。因此，本文分析效用挖掘的现 实意义，通过结合支持计数和效用的数学特性，将闭模式约束引入到高效用项集 挖掘中。在不影响决策者的分析知识下，减少高效用项集挖掘所产生的项集模式 数量。最后给出一种闭模式约束的项集挖掘算法。 1 4 论文组织结构 本文的论文组织结构如下： 第一章，绪论，分析关联规则挖掘的研究背景意义和国内外相关研究现状， 介绍了本论文的主要工作内容和目的，最后给出了组织结构。 第二章，介绍了关联规则挖掘的背景知识，对关联规则按其效用的不同进行 分类，描述了这些不同关联规则挖掘的基本思想。接下来重点阐述了基于效用的 关联规则基本描述和性质，并介绍了两种高效用项集挖掘算法。 第三章，设计了一种快速的高效用挖掘算f u l m i n e ，利用项集长度对总事务 集进行分类，减少挖掘搜索空间，同时提mf u i t r e e 结构存储项集信息进行挖掘， 并通过实验证明了算法的有效性。 第四章，提出了一种基于f u i m i n e 算法和列枚举方法分别挖掘长模式和短模 式项集的混合算法h y b i r d m i n e ，给出列枚举方法的优化策略，提高算法总体的 挖掘效率，并通过实验证明了算法的有效性。 第五章，将闭模式约束引入到高效用项集挖掘中，通过支持度的比较去掉冗 余的项集，大量的减少了挖掘结果，并采用列枚举实现了基于闭模式约束的高效 用项集挖掘算法。实验证明，加入约束的高效用挖掘能快速的产牛更简洁的项集。 最后给出了论文的结论部分，总结了本文的主要内容，并提出对未来高效用 挖掘的展望。 1 5 小结 本章主要介绍了课题的相关研究背景和意义，分析了目前国内外关联规则挖 掘的相关研究现状，给出本文的主要研究内容，最后介绍了论文的结构。 6 硕l ：学似论文 第2 章关联规则与效用的挖掘研究 本章简单地介绍了关联规则与效用的概念，对各种不同效用划分的关联规则 挖掘算法进行描述，并重点介绍了两种典型的高效用项集挖掘算法。 2 1 关联规则的基本概念 关联规则是从事务数据集中挖掘用户感兴趣的模式，分析其相关性。有关基 本概念如下：设任务相关的数据d = 瓴，如，f 。 是一个事务( 交易) 数据库，其中 f ，表示第个事务( 交易) ，其是由中的某些项目的所构成的集合，即f ，s ，。其 中，= i ，屯，f m 代表m 个不同类型属性的集合。 定义2 1，的任意子集x 称为d 中的项目集( i t e m s e t s ) ，简称为项集x ，i x i = i | ， 即项集x 中项目个数，称为项集x 的长度，包含七个项的项集称为七项集。如果 x ，称事务包含项集x 。每一个事务都有一个标识符t i d 。 定义2 2关联规则是形如彳jb 的蕴涵式，其中彳c ，bc ，并且 彳厂、召= g 。a ，b 分别称为关联规则彳jb 的前提和结论。 支持度( s u p p o r t ) 和置信度( c o n n d e n c e ) 是规则兴趣度的两种度量。它们分别反 映所发现的规则的有用性和确定性。其定义如下： 定义2 3 设甜肼( x uj ，) 是包含项集x u 】，的事务数，i d i 为数据库中的事务总 数，则支持度s 地即( u y ) 定义为x 和y 这两个项集在事务数据库t 中同时出现 的舱叭即州扎y ) - 气产。置信度删柏y ) - 鬻， 即在出现项集的事务数据库t 中，项集j ，也同时出现的概率。 关联j i ! l | 则的挖掘就是生成所有满足用户给定的最小支持度和最小信任度的关 联规则，即这些规则的支持度和信任度分别不小于最小支持度和最小信任度。满 足最小支持度和最小信任度的关联规则称为有意义的关联规则( 强关联规则) 。 关联规则的挖掘分为两个阶段： ( 1 ) 根据最小支持率找出数据集d 中所有的频繁项目集( f r e q u e n ti t e m s e t s ) ，频 繁是指某一项目组出现的频率相对于所有记录而言，必须满足用户给定的最小值。 若项集x 支持度犬于等于所设定的最小支持度( m i n i m u ms u p p o r t ) 阈值时，则x 称 为频繁项目集。一个满足最小支持度的k i t e m s e t ，则称为频繁k 项目集( f r e q u e n t k - i t e m s e t ) 。 ( 2 ) 利用频繁属性集生成所需的关联规则。对于每一个频繁属性集兄找出x 的所有非空子集】，如果刀厂( x jn 朋咖d 矿，就生成强关联规则。 高效用项集挖掘算法的研究 在关联规则挖掘中，第一阶段的任务是迅速高效地找出dr l 全部频繁项口集， 是关联规则挖掘的中心问题，是衡量关联规则挖掘算法的标准：第二阶段的工作 可以直接由公式求解。目前关联规则挖掘算法都足针对第一阶段工作而提出的。 2 2 关联规则的分类 关联规则挖掘按不同的划分标准有不同的形式的关联规则，如根据挖掘的模 式的完全性分为挖掘频繁项集的完全集、闭频繁项集和极大频繁项集，按规则集 所涉及的抽像层分为单层和多层关规则等等。本章中重点介绍按项集的不同效用 对关联规则进行分类，这里的效用指关联规则有用程度的一种度量。由于效用与 用户的兴趣相关( 主观的和客观的) ，不同的关联规则对效用不同的处理方法往往 决定了产生的规则能在多大程度上满足用户需求。 2 2 1 布尔型关联规则 文献【2 】提出最简单的关联规则挖掘算法，产生的频繁模式是争维、单层、布 尔频繁项集。它只处理项集是否在事务集中出现，整个数据集中只有“o ”和“1 数据，“0 ”表示项目没有出现在该事务中，“1 表示项目出现在该事务中。因此， 又被称为布尔型关联规则。它基于支持度和置信度产生关联规则，支持度的计数 即项集出现的次数。典型的布尔型关联规则挖掘有a pr i o r i 【6 】算法、f p - g r o w t h 【7 l 算法，两者都利用了频繁集向下封闭的特性，即频繁项集的所有非空子集也必须 是频繁的。其中a p r i o r i 算法的核心部分如图2 1 所示。 布尔型关联规则挖掘的主要任务是找出所有频繁集，再从这些项集模式中发 现有趣的规则，给用户提供数据之问的关联、相关和其他有趣的联系。它假设频 繁出现的项集就是用户感兴趣的，事实上，这种假设容易导致布尔型关联规则丢 失一些重要模式。例如，