（计算机应用技术专业论文）基于项缩减的关联规则挖掘算法研究.pdf

大连理工大学硕士学位论文 摘要 近年来，随着信息技术的不断发展，人们积累的信息量不断增加，传统的统计方法 已经不能满足人们从大规模数据存储中获取知识的迫切需求。作为数据挖掘领域中的一 个非常重要的研究课题，关联规则反映了一个事物与其他事物之间的相互依赖性或者相 关性，它既可以检验行业内长期形成的知识模式，也能够发现隐藏的新规律。因此如何 有效地挖掘关联规则具有重要的理论价值和现实意义。 本文重点针对数据本身对关联规则挖掘的影响进行了研究，并取得了一定的成果。 首先针对a l m o r i 算法的不足，提出了改进方案。a p r i o r i 算法是关联规则挖掘中的经 典算法，当最小支持度阕值较小时，a p r i o r i 算法将产生大量候选项集，对这些候选项集 进行支持度计数将耗费大量时间。本文针对这个问题，提出项事务和项缩减操作的概念， 并在此基础上提出一种基于项缩减的a 研o r i 算法一a 皿鲥i r 。该算法通过对事务进行 完全项缩减操作，能够有效减少候选项集个数并减少候选项集支持度计数时间，从而提 高了a p r i o 打算法的效率。本文不仅从理论上分析了a p r i o r i 瓜算法能够减少连接和剪枝次 数降低支持度计数时间，还通过在不同浓密性和模式长度的数据集上进行实验，表明了 a 研o r i 瓜算法的有效性。 为了进一步研究项缩减操作对关联规则挖掘算法的影响，本文对经过完全项缩减操 作处理的数据利用f p g r o w t h 算法进行挖掘，提出了f p g i r 算法。同样本文不但从理 论上分析了f p g i r 算法能够降低f p g r o w m 算法的空间消耗，还通过不同数据集的实 验验证了算法的有效性。最后，通过利用f p 仃e e 的结构特点，提出了一种基于f p 仃c e 的完全项缩减操作算法f p t r e e i r 算法，该算法降低了进行完全项缩减操作所需要的系 统消耗。 关键词：关联规则；频繁项集；项缩减；f p t r e e 大连理工大学硕士学位论文 r e s e a r c ho na s s o c i a t i o nr u l e sm i n i n ga 1 9 0 r i t h mb a s e do ni t e m r e d u c t i o n a b s t r a c t h lr e c e n ty e a r s ，w i mt l l er a p i dd e v e l o p m e n to fi n f o 珊a t i o nt e c l l l l o l o g ya n dm ei n c r e a s i n g 锄o u n to fi n f o m a t i o n ，仃a d i t i o n a ls t a t i s t i c a lm e t h o d sc a i ln 0l o n g e rm e e tp e o p l e sn e e d a s a i li n l p o r t a n tr e s e a r c ht o p i c 试t l l ef i e l do fd a t am i n i n a s s o c i a t i o nm l e sr e n e c t st 1 1 e i n t e r d 印e n d e n c eo rr e l e v 觚c eb e 咐e e i lo b j e c t s t h er e s e a r c ho n h o wt 0m i i l i n gm ea s s o c i a t i o n m l e sm o r ee f ! f i c i e n t l yi so f 伊e a tt h e o r e t i c a lv a l u ea 1 1 dp r a c t i c a ls i 弘m c a n c e t h em a i nt a s ko fm i sd i s s e r t a t i o ni st h er e s e a r c ho nm er e l a t i o n s h i pb e 撕e e na s s o c i a t i o n r u l e sa i l d 1 ed a t ai t s d w ea l s oh a v ea c h i e v e dc e r t a i l li i l i l o v a t i v ec o n t r i b l i t i o n s t h em a i l l r e s e a r c hw o r ko ft h ed i s s e r t a t j o nc a nb es l 】m i l l a r i z e d 硒m ef o l l o w s ： 加m i n ga t 1 es h o r t c o m i n go f c u 仃e n ta p r o i r ia l g o r i 廿1 1 1 1 ，an e w s o l u t i o ni sp r o p o s e di nm e d i s s e r t a t i o n t h ea p r i 砸a l g o r i 也mi sac l a s s i cm e t h o df o rm i n i n ga s s o c i a t i o nm l e s h o w e v e r w h e l lt l l es u p p o r t 吐鹏s h o l di sl o w ah u g es e to fc 锄d i d a t e sw i l lb eg e i l e r a t e d 砌l ea1 a r g e 锄o u n to ft i m ew i ub ec o m 沁【i l e dt oc o u 】哦t h e i rs u p p o r t s a c c o r d i n gt ot l l ep r o b l e i i l ，n l i s d i s s 鲥a t i o np r e s e n t san e wc o n c 印t i o no fi t 锄t r a n s a c t i o na n d a l la p r i o r ia l g o r i t 量1 1 nb a s e do n i t e m 删i o n ( a p r i o r i i r ) t h en e wa 1 9 0 r i t h mc a l li m p r o v em ed e 6 c i e n c y a i l dm ee m c i e l l c y o fa p r i o r ia l g o r i t l l n lb yu s i n gi t 锄r e d u c t i o no p e r a t i o i l s t t l ed i s s e r t a t i o np r o v e sm a t a p r i o r i i rc a nr e d u c em et n e so fj o i i l i n ga 1 1 dp m l l i n g ，a l s o i tc a nc u td o w nm e 缸eo f c a l l d i d a t e sc o u n t i n g t h ee x p 嘶m e n t a lr e s u l t ss h o wt h ef e a s i b i l i 够a 1 1 de 日 e c t i v e l l e s so ft h e a l g o r i m m f o r 如r t h e rr e s e a r c ho nm ee f f e c t so fm ei t e mr e d u c t i o no nm ea s s o c i a t i o n1 1 l l e sm i l l i n g a l g o r i t l l 】皿，f p 黟o w ma l g o r i t l l 】 i li su s e dt om i 疵喀m ed a t ap r o c e s s e db yt l l ei t e mr e d u c t i o n o p 酬i o n ，a i l dn l ef p g i ra l g o r i 伽：1 1 ( a i lf p g r o w l l la 1 9 0 r i t l l 】 1 1b a s e do ni t 锄f e d u c t i o n ) i s p r o p o s e d i ti sp r o v e dt h a tm ef p - g i ra l g o r i t h mc a i lr e d u c et l l ec 0 i l s u m p t i o n so fm et i m e s p a c ea n dm e m o r ys p a c e t h ef e 嬲i b i l i t ya 1 1 de 行e c t i v e i l e s so f t h ea l g o d 皿c 锄b es h o w r i li i l n l ee x p e m e n t a lr e s u l t so nd i 矗e r e n td a t a s e t s af p - t r e e i ra l g o r i t i l mb a s e do nf p t i - e e s 仃u c t l _ l r ei sp u tf 0 肿a r da tl 嬲t 舢s ot l l ec x p 耐m e n t ss h o wm a tt l l ea l g o r i t h mc a i lr 酣u c et l l e c o n s u m p t i o no ft h et i m es p a c e k e yw o r d s ：a s s o c i a t i o nr u i e s ；f r e q u e n ti t e m s e t s ；i t e mr e d u c t i o n ；f p t r e e i i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目壅i 亟蕴这亟皇董篮垫型丝垫篁墨叠塑 作者签名： 茎：蠡日期：丝! !年三月j l 日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：薹量塑塑煎蔓皇羞壁垫型亟垫蔓丛堑鱼 作者签名：蕉盘鱼日期：兰! ! !年监月l 日 导师签名： 盘盈 日期： 鲨罕年匕月巫日 导师签名： 叟垒 日期： 鲨覃年匕月巫日 大连理工大学硕士学位论文 1 绪论 1 1 课题背景及研究意义 随着信息技术的不断发展，人们积累的信息量不断增加，传统的人工智能和统计方 法已经不能满足人们从大规模数据存储中获取知识的迫切需求。伴随着条形码技术的发 展以及商场p o s 机的设置使得超级市场存储了数以万计的数据记录，这些记录详细记录 了每个客户每次交易的时间、商品、数量和价格等信息，从而为关联规则挖掘提供了数 据基础。a 乎a w a i 等人于1 9 9 3 年针对市场的购物篮问题( m a r k e tb a s k e ta n a l y s i s ) 进行分 析，提出了关联规则挖掘的概割。通过发现数据集中所有的频繁模式和强关联规则， 从大量的数据中挖掘出有价值的描述数据项之间相互联系的有关知识，来指导商家科学 地安排进货、库存以及货架设计等。关联规则挖掘则可以发现用传统的人工智能和统计 方法无法发现的数据库中项与项或属性与属性间的预先未知和被隐藏关系规律，帮助人 们进行决策分析【2 j 。 随着关联规则技术的不断成熟和发展，其应用范围也越来越广，从最初的购物篮分 析逐渐扩展到网络路径优化、网络入侵检测、电信网络管理、w 曲日志挖掘、关联分类、 交通事故模式分析、基因表达分析、基因调控网络、中医药药物关联分析、设备故障诊 断蛋白质结构分析、软件b u g 挖掘、金融业务分析、个性化推荐! x m l 数据挖掘等多个 数据挖掘领域。 关联规则作为数据挖掘领域中的一个非常重要的研究课题【3 】，既可以检验行业内长 期形成的知识模式，也能够发现隐藏的新规律。有效地发现、理解、运用关联规则是完 成数据挖掘任务的重要手段，因此对关联规则的研究具有重要的理论价值和现实意义。 1 2 国内外研究现状 由于关联规则技术具有良好的理论基础和非常广泛的应用背景，使得该技术在不同 情境和实际需要的推动下，得到了持续而深入的研究。近年来，世界上知名大学的研究 机构和各大i t 公司的研究部门都投入了大量精力对关联规则挖掘进行了研究，并取得了 诸多研究成果，如美国斯坦福大学智能数据库系统实验室开发出的商用数据挖掘系统 d b m i n e r 挖掘系统，i b m 的舢m a d e i l 实验室所进行的q u e s t 项目，美国宾西法尼亚大学的 数据挖掘研究小组从多家医院的病人数据库中发现可以提高医疗质量和降低医疗费用 的模式等。加拿大s i m o nf r 2 l s e r 大学的j i a w e ih a n 教授、比利时赫尔辛基大学的m a n l l i l a 教授、t o i v 0 皿朗教授等享誉世界的数据挖掘研究的顶尖学者，为该领域的发展作出了 重要贡献。而在国内，复旦大学、浙江大学、吉林大学、中科院、大连理工大学、南京 基丁项缩减的关联规则的挖掘算法研究 大学等科研单位对关联规则挖掘算法优化以及相关领域的进行了深入研究，取得了一定 的成果，并推动了关联规则在中国的发展和应用。 在数据挖掘技术得到迅猛发展的大背景下，关联规则挖掘技术也取得了蓬勃发展。 自从关联规则挖掘问题提出至今，人们相继提出了大量的关联规则挖掘算法。 a 伊a w a l 等人于1 9 9 4 年提出a 鲫o n 算法【4 】，该算法是使用频繁项集的先验知识，通过 逐层搜索的迭代方法，利用频繁缸项集探索频繁( 斛1 ) 项集。首先，找出频繁1 项集的 集合三，然后利用三，探索频繁2 项集的集合厶，厶探索j ，如此下去，直到不能找到频繁 肛项集为止。而探索每个厶需要对数据库进行一次扫描。a p r i 嘶算法利用频繁项集的所 有非空子集都必需是频繁的这一性质，来压缩搜索空间，提高频繁项集逐层产生的效率。 此后，许多学者针对a 研o r i 算法的不足，提出了许多的改进和扩展方法，形成了一系列 以a 州o r i 算法为基础的a 研o r i 类算法。 h a l l 等人于2 0 0 0 年提出f p g r o w t h 算法【5 】，该算法是一种不产生候选模式而采用频繁 模式增长的方法挖掘频繁模式的算法【6 】。它首先通过扫描事务数据库d 产生一个紧凑的、 包含d 中频繁模式全部信息的频繁模式树( f p _ t r e ef r e q u e n tp a t t e mt r e e ) ，然后通过对 f p t r e e 的挖掘获得频繁模式。该算法只需通过两次扫描数据库，就可以挖掘所有频繁项 集，进而挖掘关联规则。许多学者在f p g r o w t h 算法的基础上，提出了大量以f p t r e e 数 据结构为核心的算法【7 。3 1 。 韩敏教授于2 0 0 7 年提出b i t t a b l e f i 算法【l4 1 ，该算法利用二进制对数据库事务进行压 缩，节省了内存空问，提高了挖掘效率。在此基础上，s o n g 等人提出了i n d e x 。b i t t a b l e f i i j ， 该算法降低了b i t t a b l e f i 算法挖掘频繁项集的代价。 随着研究的深入丌展，关联规则挖掘理论不断丰富，其研究内容已经从最初的频繁 模式挖掘不断扩展到最大模式挖掘、闭合模式挖掘、扩展型关联规则、衍生型关联规则、 关联规则隐私保护、增量挖掘、挖掘后处理、规则主观兴趣度度量、相关模式、数据流 等多种类型数据上的关联规则挖掘等等。近十年来，国际上发表的关于关联规则挖掘方 面的论文数量多达上万篇，并且在每年的数据挖掘领域顶尖国际会议，如：s i g k d d 、 i c d m 、p a l d ，以及顶尖国际期刊中，均有不少最新的相关文献涌现，而在国内与之 相关论文也有数干篇之多，这充分表明该技术仍处于继续深入探索和研究的过程当中。 1 3 本文的主要工作 本文主要的工作是研究数据本身对关联规则挖掘的影响。首先，本文对a p r i o 算法 的性能进行了分析与实验。通过分析和实验，得出a o r i 算法的时间开销主要由数据库 大连理工大学硕士学位论文 扫描时间、连接时间、剪枝时间和扫描支持度计数时间四部分构成的结论。由于已有算 法对数据库扫描、连接和剪枝产生得到候选项集进行了不同程度的优化，结合a p r i o r i 算法的实现过程，得出以下结论：扫描支持度计数是影响a p r i o r i 算法性能的主要因素。 在此基础上提出了项缩减的概念，并结合a p 打o r i 算法的特点提出了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 瓜算法、a 研o r i n i r 算法( 按照字典顺序进行项缩减 的a p r i o 订算法) 和a 研谢d i r 算法( 按照支持度升序进行项缩减的a 皿嘶算法) 进行了 对比实验。实验结果表明，a p r i o r i i r 算法能够有效降低连接时间、剪枝时间和扫描支持 度计数时间，提高频繁模式的挖掘效率。 为了进一步研究项缩减操作对关联规则挖掘算法的影响，本文对已经经过完全项缩 减操作处理的数据利用f p ，印w 也算法进行挖掘，并提出f p g i r 算法。然后对f p g i r 算 法进行了对比实验，实验结果表明在运行总时间相差不大的基础上，经过完全项缩减操 作，f p g i r 算法可以显著降低f p 黟o 、t h 算法的空间消耗。 最后，本文对项缩减操作进行了分析，结合f p t r e e 的压缩数据的结构特点，提出 了一种基于f p 们e 的f p 。t r e e i r 算法。该算法通过构建f p 仃e e ，然后将频繁1 项集的 前缀路径及其支持度计数输出到一个数据文件中，避免了每一个项事务数据库对应一个 数据文件的问题，降低了系统开销。 1 4 本文组织结构 第l 章为概述部分。首先对关联规则的研究背景和研究意义进行了介绍，然后分析 了关联规则的国内外研究现状，最后对本文的主要工作和组织结构进行了说明。 第2 章是关联规则概述。首先介绍关联规则挖掘中的相关概念、关联规则的挖掘步 骤和算法，然后从不同的角度出发对关联规则进行了分类，接着对关联规则挖掘的扩展 进行了说明，最后介绍了关联规则的具体应用。 第3 章是基于项缩减的a p r i o r i 算法研究。首先详细介绍了a p r i o r i 算法，并对现有 a p r i o d 算法进行了分析和实验，然后提出了完全项缩减操作的概念，并在此基础上提出 了a p r i o r i i r 算法，最后进行了对比实验。 第4 章是基于项缩减的f p g r o w c l l 算法研究。首先介绍了f p 一伊o w t h 算法，然后提 出了f p 。g 瓜算法，接着对f p g i r 算法进行了实验说明。最后提出了基于f p - 仃e e 的 f p t r e e m 算法，并对该算法进行了实验。 最后对本文的研究工作进行总结并给出了后续工作的展望。 基于项缩减的关联规则的挖掘算法研究 2 关联规则概述 2 1关联规则相关概念 关联规则的概念最早由a 伊a w a l 等人于1 9 9 3 年提出。关联规则的相关概念【1 6 】如下： ( 1 ) 数据项 数据项( i t e m ) ，也称为项目或者项，它是一个标识，是事务数据库中的一个属性 字段，具有一定的取值范围。 在交易数据库中，代表一类商品；在分类和聚类中，代表一个属性值。 ( 2 ) 数据项集 由若干个数据项组成的集合瓣为数据项集，简称项集( i t e m s e t ) 或者模式( p a t t e m ) 。 通常把包含所有数据项的项集记为，卢 f ，屯，如) ，其中挖为所有数据项的个数。把一个 数据项集所包含的项的个数称为该数据项集的长度，把长度为尼的数据项集称为肛项集 ( 肛i t 锄s e t ) 。 ( 3 ) 事务与事务数据库 事务丁( t r a j l s a c t i o n ) 是所有数据项集合肭子集，即互。对于每一个事务都有一 个唯一的事务标识符t i d ( t r a n s a c t i o ni d ) 与之相关联。不同事务的全体构成的集合称为 事务数据库d ，d 中包含的事务的个数记为| d i 。 ( 4 ) 项集的支持度计数和支持度 对于项集，爿，如牌事务厶的一个子集，则称事务包含项集x ( 或者项集x 覆盖事务以) 。事务数据库d 中包含项黼事务的个数，称为项黼事务数据库d 中的 支持度计数( s u p p o nc o u n t ) ，简称为支持数，记为x s 印。彳在d 中的支持计数与d 中事 务总数l d l 之比称为项集臃d 中的支持度( s u p p o r t ) ，记为s u p p o r t ( x ) ，即： 砌印。刀( z ) ：竺里 idi ( 1 1 ) 从统计的角度来看，朋拘支持度就跳d 中出现的概率，它描述了项黼肿的重 要程度。 ( 5 ) 项集的最小支持度和频繁项集 挖掘关联规则要求项集必须满足的最小的支持度阈值，该最小支持度阈值称为项集 的最小支持度( m i n i m u ms u p p o r t ) ，记为朋f ，u 印。从统计的意义上讲，项集的最小支 持度表示项集在统计意义下的最低重要性，只有满足最小支持度的项集才可能在关联规 大连理工大学硕士学位论文 则中出现。在实际的应用中，如果事务数据库的事务量是固定的，常用最小的支持数来 代替最小支持度。支持度大于或者等于最小支持度的项集称为频繁项集或者强项集，简 称频集；反之，则称为非频繁项集或者弱项集。 ( 6 ) 关联规则 关联规则( a s s o c i a t i o nr u l e ) 可以表示为一个蕴涵式： r ：xjy ( 1 2 ) 其中：x ，】，并且z n y = 。它表示如果项黼某一个事务中出现， 则会导致项集地会在同一事务中按照某一概率出现。徘为规则的先决条件 ( a m e c e d 饥t ) ；啉为规则的结果( c o n s e q 懈l t ) 。关联规则r ? x 】，反映了肿的数 据项出现时，冲的数据项也跟着出现的规律。 ( 7 ) 关联规则的支持度 对于关联规则r jx 】，彳，y z ，并且x n 】，= 西，规则r 的支持度是事务 数据库中同时包含x 和y 的事务数与事务总数之比，记为即d 力j 矽，即： 泐。力j 】，) ：堕等业 i j ( 1 3 ) 关联规则尺jx j y 的支持度反应了斯口冲所包含的项在事务数据库中同时出现的 概率，由于关联规则必须由频繁项集产生，所有规则的支持度本质上就是频繁项集 彳u 】，的支持度，即： 跏。州石jy ) - 泐州zu y ) ：紫 j ( 1 4 ) ( 8 ) 关联规则的置信度 对于关联规则r j x y ，x j ，】，s j ，并且x n y = 中，规则r 的置信度 ( c o n f i d e n c e ) 是事务数据库中同时包御m 事务数与包俐事务数之比，记为 ，l 万，l 如n c e 习) ，即： c o 彻似舻訾。鬻 n5 ， 五，“po 扰矽矽d ，7 ( 五j，1瓦、 从统计的意义上讲，关联规则尺? x y 的置信度表示为在事务数据库d 中的那些 包黼事务中，地同时出现的概率，即条件概率p ( yx ) ，它描述了规则值得信任的 可靠程度。 ( 9 ) 关联规则的最小支持度和最小置信度 通常，用户为了达到一定的要求，都需要指定规则必须满足的支持度和置信度的阈 基于项缩减的关联规则的挖掘算法研究 值，分别称其为最小支持度，记为m i ns u p ，最小置信度，记为m i nc o n f 。 关联规则的最小支持度也就是衡量频繁项集的最小支持度，它用于衡量规则需要满 足的最低重要性。最小置信度衡量规则所要满足的最低可靠性。 ( 1 0 ) 强关联规则 如果关联规则尺j jy ，j ，】，并且z ny = ，满足 观印d 力( x y ) m i n - s u p 且妒比门c e ( xj 】，) m i n c d 矿，则称关联规则尺j xjy 为强关联规则，否则称关联规则尺jx y 为弱关联规则。 2 2 关联规则挖掘的步骤 关联规则挖掘问题可以形式化描述为： 给定事务数据库d ，以及用户指定的最小支持度阈值所f ，zj 印和最小置信度阈值 垅加c d 以 在d 中找到所有关联规则尺? 义jy ，其中勋阳d 耵矽朋现s 印， c i d ，z 疗出，z c p j 矽优砌c d 矿。而判断一条规则是否满足最小支持度阈值m 觑j 印和最 小置信度阈值历切c d 刀 必须先知道该规则的支持度和置信度，而计算这两个数据都离 不开计算规则中项集的支持度。因此大多数关联规则挖掘算法通常将关联规则挖掘过程 分解为如下两个步骤：首先，找出事务数据库d 中所有大于或者等于用户指定的最小支 持度阈值脚加s 印的频繁项集；然后，利用频繁项集生成所有的关联规则，并根据用户 指定的最小置信度阈值所觑c d 刀触行取舍，得到所有置信度大于或者等于研拥c d 船，1 均强 关联规则。 在上述两个步骤中，第二步相对比较容易，因为它只需要在第一步即己经找出的频 繁项集的基础上列出所有可能的关联规则，然后用支持度阈值和置信度阈值来衡量这些 关联规则。事实上，由于所有的关联规则都是在频繁项集的基础上产生的，因此它们就 己经自动满足了支持度阈值的要求，从而只需要考虑置信度阈值即可。由于在第一步中 产生的频繁项集数量巨大，挖掘关联规则的总体性能由第一个步骤决定。因此，目前大 多数关联规则挖掘算法都是着重于研究第一个步骤，即频繁模式挖掘算法。 频繁模式挖掘算法按照挖掘方式可以分为宽度优先算法、深度优先算法、宽度和深 度相结合的混合算法【1 7 】。 ( 1 ) 宽度优先算法 r a 留a w a l 等人提出的a 研o r i 算法是一种最具影响的挖掘布尔型关联规则的算法。 该算法是使用频繁项集的先验知识，通过逐层搜索的迭代方法，产生频繁项集。a 研o r i 的不足之处是需要多次扫描数据库，并且当最小支持度阈值较小时，a p r i o r i 算法将产生 大连理工大学硕士学位论文 大量候选项集，甚至出现组合爆炸的问趔1 8 】，另外对这些候选项集进行支持度计数将耗 费大量时间。 许多学者针对a p r i o r i 算法的不足，提出了优化方法。r a 黟a w a l 在a 州o r i 算法基础上 提出了a 研o r i t i d 算法。与使用原始数据库中的数据不同，该算法内部用每个事务当前 所包含的候选项集来表示该事务。在早期扫描时，a 研砸算法要优于a 埘o r i t i d 算法； 在扫描后期，当候选项集小于原始数据库中的项数并完全容纳于主存时，a p r i 耐t i d 算 法要优于a p d o r i 算法。而其后的a 研。打h y b d 算法则结合a 研。打算法和a 研o r i t i d 算法两 个算法的优点，在挖掘早期用a p r i o r i 算法扫描，后期用a p r i o r i t i d 算法扫描，提高了挖 掘效率。t o i v o n e n 的抽样算法【1 9 】、s a v a s e r e 的分区算法【2 0 j 有效减少了候选项集的数量和 扫描数据库的次数，p a r k 等人利用h a s h 树结构【2 1 】和b o d o n 等人利用t i e 结构【2 2 】改变了存储 候选项集的数据结构，陈耿等人提出基于二进制形式的候选频繁项集生成和相应的支持 度计数算法 2 3 】，有效减少了支持度计数时间，提高了算法效率。 这类算法都以伽o r i 算法为基础，通过改善a p r i 砸算法的不足，形成了一系列以 a p r i o r i 算法为基础的挖掘算法，这类算法统称为a 研o r i 类算法。本文将在第3 章进一 步介绍这类算法。 ( 2 ) 深度优先算法 z a k i 等人提出的e c l a t 算法f 2 4 】使用垂直数据库结构，利用深度优先的策略挖掘频繁项 集。所谓垂直数据库就是事务数据库中的每个项目郦与包含它的事务t i d 的集合联系起 来，定义事务t i d 的集合为t i d l i s t c 的，而项集的支持度计数直接是项集的t i d 集的长度。 该算法首先扫描一次数据库找出所有的频繁1 。项集，然后通过扫描数据库将水平数据库 转换成垂直格式。然而，当数据库中事务较多时，t i d 集合就会很长，需要大量的空间， 同时求长集合的交运算也需要大量的计算时间。为了降低存储长t i d 集合的空间开销和 求交运算的计算开销，e c l a t 算法采用差集的计数，仅记录( 斛1 ) 项集的t i d 与之对应的 卜项集的t i d 集之差。该算法由于缺乏用于剪枝的必要的项集信息，算法没有剪枝步骤。 因此算法有大量的时间消耗用于额外的候选集的产生及支持度的计算。针对这一个问 题，宋长新等人提出了e c l a t 算法的改进算法e c l a t + 算法【2 5 1 。该算法自右向左挖掘频集， 在挖掘( 肛1 ) 项集时候把惦1 ) 项频集的信息记录下来，在挖掘珏项集的时候利用频繁 似1 ) 项集对候选集进行剪枝。和e c l a t 相比，在计算候选集的支持度前，e c l a t + 算法先对 其进行检测，若候选集是潜在的频繁项集，则执行交集操作，否则，则不执行。因此， 避免了额外的候选集的产生及支持度的计算，提高了算法的效率。 h a i l 等人提出的f p g r o w m 算法是种不产生候选频繁项集而采用模式增长的方式 挖掘频繁模式的算法。该算法将数据库中有关频繁项集的信息压缩到一棵频繁项目树 基于项缩减的关联规则的挖掘算法研究 f p 骶e 中，该频繁项目树能够有效保留项集之间的关联信息，然后将这种压缩后的 f p t r e e 分成多组条件f p 仃e e ，每个条件f p 骶e 关联一个频繁项集，然后通过挖掘每个条 件f p 仃e e ，递归地发现一些短模式，然后通过连接后缀的方法来构成频繁项集。f p 印w m 算法的主要问题是：在挖掘频繁模式时，它需要递归地生成条件f p t r e e ，并且每产生一 个频繁模式就要生成一个条件f p t r e e ，在支持度阈值较小时，即使对于很小的数据库， 也将产生数以十力计的频繁模式。动态的生成和释放数以十力计的条件f p t r e e ，将耗费 大量时间和空间。因此在f p g r o w t h 算法的基础上，出现了大量以f p t r e e 数据结构为核 心的算法。如范明教授提出了一种基于被约束子树挖掘频繁项集的有效算法，该算法通 过引入被约束子树，在挖掘频繁模式时不生成条件f p t r e e 。该算法还改进的f p t r e e 结构， 每个节点只保留指向父节点的指针，这大约节省了三分之一的树空间，从而大大提高了 频繁模式挖掘的时空效率。 h a j l 等人建立了h s t m c t 结构，并提出了h m i n e 算法【2 6 】。h m i n e 首先寻找全局频 繁模式集，在挖掘划分数据集时，h m i n e 只考察全局频繁的数据。因为在划分子数据 集中，有很多局部频繁的模式，所以h m i n e 将不再花费代价计算，能够有效地避免生 成实际的数据库投影，从而提高算法效率。l i u 等人在h m i n e 算法的基础上将f p 一伊o w t h 和h m i n e 算法相结合，提出了0 p 算法【2 7 】，该算法综合采用了自底向上虚拟投影技术 和自顶向下的投影技术两种策略。当数据库稠密时采用f p 铲o w t h 算法，当数据库稀疏 时利用h m i n e 算法代替f p g r o 州h 算法进行挖掘。该算法同时针对f p 伊o w t h 算法递 归地构造条件f p t r e e 时要占用大量内存的这一问题，通过改变指针的方式而不是依靠 生成物理投影的方式来达到同样的效果。 ( 3 ) 混合算法 宽度优先算法的主要缺点是：要存放候选项集和部分频繁项集，消耗内存较大；要 先删减候选项集再读入数据库确定频繁项集，消耗时间较大。而深度优先算法正好相反。 因此，有学者考虑将两种搜索方式相结合，提出了宽度优先和深度优先相结合的混合算 法。 a g r a w a l 等人提出的t r e e p r o j e c t i o n 算法【2 8 】将频繁项集挖掘转化为逐步构造一种模式 字典树的过程，同时将一个大型数据库投影为一系列子库。该算法宏观上是宽度优先搜 索，因为同时产生第f 层的频繁项集。但是为了能够对数据库删减，微观上采用了深度优 先搜索方法。算法的基本思想是当结束对棍的挖掘之后，对( 缸1 ) 至0 层的每个节点重新 确定可扩展项集。然后，利用深度优先搜索，每到一个节点，就利用该点的可扩展项集 删去没有用的数据项。到达第( 肛1 ) 层时，构造矩阵统计第( 斛1 ) 层的频繁项集，避免了 大连理工大学硕士学位论文 对第据进一步删减，提高了算法效率。 刘君强等人提出的h y b r i d p r o j e c t i o n 算法【2 9 1 ，使用基于树表示的虚拟投影进行事务子 集投影，利用适用于稀疏型事务子集的基于数组的表示形式进行项集的存储，通过综合 使用宽度优先搜索和深度优先搜索来达到空间可伸缩性的最大化。 宽度优先算法的缺点就是对含有长模式的密集数据库挖掘效率比较低下，深度优先 算法的缺点就是不能把深度优先的潜力很好地扩展到大型稀疏数据库的挖掘中去。两者 的简单结合也肯定不能适应各种事务数据库特点，产生万能的算法。但是，将两者有机 地结合起来应该能够适合更多情况下的事务数据库。 2 3 关联规则分类 从不同的角度出发，可以对关联规则进行不同的分类。 ( 1 ) 基于规则中处理的变量的类别，可以分为布尔关联规则和量化关联规则。 若所考虑的关联规则是项的在与不在，则它是布尔关联规则。布尔关联规则表明了 离散对象之间的联系。如果规则所描述的是量化的项或属性之间的关联，则它是量化关 联规则。在量化关联规则中，项和属性的量化值划分为区间，涉及动态离散化的数值属 性，也可能涉及分类属性。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 单层关联规则是指在给定的规则集中，规则挖掘只涉及相同抽象层的项或属性。在 现实生活中的许多概念之间存在着层次性，例如，联想笔记本电脑是笔记本电脑的一种， 笔记本电脑又是电脑的一种等，同样对于事务或关系数据库来说，一些项或属性所隐含 的概念也是有层次的。而在许多实际应用中，由于数据稀疏性，在最底层或原始层的数 据项之间，可能很难找出强关联规则和有趣的模式。引入概念分层使得人们能够在较高 的概念层次上进行数据挖掘，发现新颖的、有价值的强关联规则。根据规则涉及到的层 次，多层关联规则可以分为同层关联规则和层间关联规则。同层关联规则考虑相同概念 层次上的项之间的关系，而层间关联规则中出现的项可以属于不同的概念层次。 ( 3 ) 基于规则中涉及到的数据的维数，可以分为单维关联规则和多维关联规则。 单维关联规则是处理单个属性中的一些关系，只涉及到数据的一个维，如用户购买 的物品；多维关联规则是处理各个属性之间的某些关系，要处理的数据将会涉及到多个 维。对于多维关联规则，根据是否允许同一个维重复出现，可以又细分为维内的关联规 则和混合维关联规则。 ( 4 ) 根据数据的存储方式，可以分为单关系关联规则和多关系关联规则。 基于项缩减的关联规则的挖掘算法研究 单关系关联规则是基于关系数据库中的单个表上的数据实现的。而多关系关联规则 的数据存储在关系数据库的多个表中。目前，多关系关联规则的概念还没有统一的严格 定义。有的学者认为，直接在一个关系数据库的多个表中寻找有意义的模式，不需要将 多个表转换为单个表的技术称为多关系数据挖掘【3 0 1 。持这种观点的学者强调多关系数据 挖掘不应该是通过将多个表转换为单个表后对数据进行分析；也有的学者则致力于将多 个关系的数据进行一定的归纳、汇总，通过创建新的属性等方法将多个关系的信息集中 到一个表，然后处理。中国人民大学的何军老师给出的定义为：通过分析一个关系数据 库的多个表中的数据发现存在于单个表以及多个表的属性值之问的关联规则的过程称 为多关系关联规则挖掘【3 1 1 。而将传统的单表关联规则挖掘算法进行扩展，用于挖掘多表 关联规则时会遇到性能降低、统计偏斜和信息丢失等问题。 2 4 关联规则扩展 ( 1 ) 基于约束的关联规则 对于给定的事务数据库，利用关联规则挖掘可以发现数以万计甚至数以百万千万计 的规则，但并不是所有的规则都是有用的。而在实际应用中，用户可能只对关联规则的 部分集合感兴趣，如果在进行数据挖掘时考虑某些约束条件，则所得结果对用户更有价 值。为此n g 等人提出了基于约束的关联规则【3 2 1 。由于基于约束的挖掘允许用户根据其 关注的目标进行挖掘，这样不仅能提高用户在挖掘过程中的主导性，而且能提高挖掘 的效率。此外，可以使用复杂的挖掘查询优化程序以便利用用户指定的约束，使得挖掘 过程更有效率。基于约束的挖掘促进交互式探查挖掘与分析。 ( 2 ) 加权关联规则 一般意义上的关联规则挖掘存在两大前提假设：数据库中各项目具有相同的性 质和作用，即重要性相同；数据库中各项目的分布是均匀的，即出现频率相同或相 似。也就是说，只考虑数据库中的各个数据项出现的频率，而不考虑项在记录中数量， 并认为每个数据项在挖掘过程中具有同样重要性。然而，这种假设在现实世界往往很难 成立。比如在商城的交易数据库中，一次交易记录中某种商品数量并不止一个，而商城 中的各种商品利润也是不相同的，有些商品的虽然在交易数据库中出现次数较少但却能 够带来丰厚利润等等，而从决策者角度出发，人们往往会优先考虑获取利润较大的商品， 而忽略利润较小的商品。当数据库中数据项分布不均匀出现频率相差较大时，设置关联 规则的最小支持度阈值，就会出现如下的两难的情况：如果最小支持度阈值设置的太高， 所发现的关联规则将就不能挖掘到出现频率较小的数据项；而设置的太低，就会挖掘出 大连理工大学硕士学位论文 太多没有意义的甚至是虚假的关联规则，甚至导致组合爆炸的问题，严重降低算法挖掘 效率。针对这一问题，c a i 等人通过为每一个数据项分配一个反映其重要程度的权值， 提出了加权关联规则的概念【3 3 1 ，并给出了布尔型加权关联规则中加权支持度和加权置信 度的计算公式。 ( 3 ) 负关联规则 数据库中存在许多的隐式模式，这些重要的隐式模式之一便是负关联规则1 3 4 1 ，它具 有低频率、强相关的性质，表现了数据项目集间的不易直接觉察到的强相关性质，这种 隐式规则告诉我们哪些数据项目较少地一起发生，但它们之间有着相当强的相关性，包 含了非常有价值的信息。负关联规则的一个简单应用例子是超市中的商品摆设问题，显 然，对于两个高频率商品肺y ，如果新艮少跟】，同时发生，僦应尽量摆放在远离y 的货 架上。此外，在投资分析和竞争分析等许多领域的决策制订过程中，负关联规则的作用 也发挥着重要作用。例如在房地产业，投资者将会面临到环境质量问题、自然资源利用 问题以及许多经济和政治问题。对于引起环境问题、资源利用冲突、以及可能解决这些 问题和冲突的政治方案极其重要的环境状况分析报告的制订，不仅要依靠从历史数据中 得到的正关联规则，而且要依靠负关联规则。 b 血，m o 觚a i l i 和s i l v e r s t e i n 等人1 9 9 7 年首次提到了两个项集间的相关性，在关联规 则中考虑了否定属性。s a v a s e r e ，o m i e c i n s l ( i ，和n a v a m e 阐述了负关联规则问题，提出 了挖掘负关联规则的算法，该算法将特定领域知识与以前发现的正关联结合起来，以分 类法的形式来挖掘关联规则。n d o n g 、h ，c h e n g q iz h a l l g 和s 1 l i c h a oz h a l l g 给出了一个 p r 模型，它不需要特定领域知识，并且给出了一个能够同时挖掘正关联规则和负关联规 则的算法，该算法以传统的a 研甜算法为基础来挖掘频繁项集和非频繁项集，在挖掘频 繁项集中正关联规则的同时，能够清楚地挖掘非频繁项集中的负关联规则。从系统的完 整性角度来看，负关联规则与正关联规则一起为正确决策提供更加全面的信息，正因为 如此，负关联规则的