（计算机软件与理论专业论文）关联规则挖掘算法的研究(1).pdf

山东科技大学硕士学位论文摘要 摘要 关联规则的发现是数据挖掘中最成功和最重要的一项任务，也是当今数据挖掘中一 个非常活跃的研究领域。 针对a p f i o r i 算法中c 2 通常是最大的，算法的绝大部分时间消耗在生成频繁2 一项集 上的问题，论文提出了一种基于矩阵的m a t ( m a t r i x ) 算法。基本思想是：扫描数据库， 根据项目集在事务中的出现，采用矩阵计数。把小于最小支持度的元素删去，从而得出 频繁1 项集和频繁2 一项集。这种算法减少了数据库扫描的遍数，从而提高了效率。 针对在a p r i o r i 算法中第k 似 2 ) 轮的递推中，数据库中的每个事务t 的所有k 阶子 项集都要判断其是否在k 阶候选项集中的问题，论文提出了一种基于事务剪枝和分区查 找的p p s ( p r u n i n g p a r t i t i o ns e a r c h i n g ) 算法，进一步提高了效率。事务剪枝基于以下策 略：若要在事务t 中保留项目t i ，那么至少出现在0 ( - 1 ) 个频繁1 ) 一项集中，否则在求 频繁k - 项集的迭代中b 被剪枝。分区查找基于以下策略：建立一种可快速搜索定位的数 据结构，将频繁1 ) - 项集序列划分为若干连续的分区( p a r t i t i o n ) ，形成噼1 ) 阶频繁项目 集的若干不相交的子集。划分的依据是( k - 1 ) 阶频繁项目集的前两项。第一个数组存放有 序的候选项集频度计数器；第二个数组记录各分区开始的位置，则任何前两项相同的项 目子集将存在于一个连续的区间内。 论文对提出的两种改进算法与a p f i o r i 算法在实验数据集上进行测试。实验证明，在 测试数据集相同的情况下，m a t 呻p s 算法运行时间明显低于a p r i o r i 算法，运行过程中 占用最大内存少于a p r i o f i 算法，效率得到了有效的提高。 在多层关联规则挖掘研究中，论文提出一种基于f p 树的f p c h 改进算法。f p c h 算法在挖掘同层关联规则过程中，在不同层上建立各自的f p 树；在进行交叉层的关联 规则挖掘过程中，对已挖掘的同层关联规则中的频繁项，找出其相应的事务集，挖掘出 跨层间的关联规则。改善了传统的m l - c h 算法挖掘过程中，可能丢失低层项之间关联 的缺陷。f p c h 算法是一种自底向上的挖掘算法，能够避免频繁项的丢失，克服了m l - c h 算法产生的缺陷。 论文在最后指出了上述算法存在的不足和进一步需要研究的内容。 关键词：关联规则；挖掘算法：事务剪枝：分区查找；f p 一树 山东科技大学硕士学位论文 摘要 a b s t r a c t a tp r e s e n t ，a s s o c i a t i o nr u l e ，0 1 3 eo ft h em o s ts 1 l i c ：c e , s s f u la n dc r u c i a ld i s c o v e r i e si nd a t a m i n i n g , h a sb e e na l la c t i v er e s e a r c ha r e a mt h ea p r i o r ia l g o r i t h m c 2i sg e n e r a l l yt h eg r e a t e s to n e , w a s t i n gm o s to ft h e 廿m eo i l g e n e r a t i n gf r e q u e n c yb i n o m i a ls e t t h i sp a p e rp r o p o s e sa na l g o r i t h mb a s e do nm a t ( m a t r i x ) t os o l v et h i sp r o b l e m t h em a i ni d e ai st os c a nt h ed a t a b a s ea n dd om a t r i xc o u n t i n ga c c o r d i n g t ot h ea p p e a r a n c eo fi t e m s e ti nt h et r a n s a c t i o n d e l e t el e s st h a nl e a s ts u p p o r te l e m e n ta n d r e a c ht h ef r e q u e n c y1 - s e ta n d2 - s e t t h ea l g o r i t h mr e d u c e st h en u m b e ro ft i m e sf o rd a t a b a s e s c a n n i n ga n di n c r e a s e sw o r ke f f i c i e n c y i nt h ek t h ( k 2 ) r e c u l t e n c eo fa p r i o r ia l g o r i t h m , a l lt h ek t ho r d e rs u b s e t so fe a c h t r a n s a c t i o nti nt h ed a t a b a s eh a v et od e t e r m i n ew h e t h e rt h e ya r ei nt h ek t l ao r d e rc a n d i d a t e i t e m s e t t h i sp a p e rp r e s e n t sai r a n s a e t i o np r u n ea n dp a r t i t i o ns e a r c hb a s e dp p s ( p r t m i n g p a r t i t i o n s e a r c h i n g ) a l g o r i t h m f o r e f f i c i e n c y t r a n s a c t i o np r t m ef o l l o w st h es u b s e q u e n t s t r a t e g y ：i fi t e mt i i sr e s 日v e di nt r a n s a c t i o nt t h e ni tm u s ta tl e a s ta p p e a ri nt h e ( k - 1 ) t h f i e q u e n c yi t e m s e tf o r ( k 1 ) t i m e s ；o t h e r w i s e ，i tw i l lb ec u ti nt h ei t e r a t i o no fr e a c h i n gt h e f r e q u e n c yk t hi t e m s e t p a r t i t i o ns e a r c hf o l l o w st h i ss t r a t e g y ：c o n s t r u c ta d a t as t r u c t u r ef o r q u i c ks e a r c ha n dl o c a t i o n , a n dd i v i d et h e ( k - 1 ) t l af r e q u e n c yi t e m s e ts e q u e n c ei n t oa n u m b e ro f c o n t i n u o u sp a r t i t i o n st oo b t a i nan u m b e ro fd i s j o i a ts u b s e t so f 暇一1 ) l ho r d e rf r e q u e n c y i t e m s e t t h ep a r t i t i o ng o e su p o nt h ef i r s tt w oi t e m so f t h e 限一1 ) t hf r e q u e n c yi t e m s e t t h ef i r s t a r r a ys t o l - e st h eo r d e r e dc a n d i d a t ei t e m s e tf r e q u e n c yc o u n t e r t h es e c o n da r r a yr e c o r d st h e l o c a t i o no fe a c hp a r t i t i o na n de v e r yi t e m s e tw i t ht h e8 a 1 3 1 ef i r s tt w oi t e m sw i l lb es t o r e di na c o n t i l l l l o l l si n t e r v a l e x p e r i m e n t sa n dt e s t sh a v eb e e nc a r r i e do u tb a s e d o i lt h ei m p r o v e da l g o r i t h ma n da p r i o r i a l g o r i t h m i ti sp r o v e ni nt h ee x p e r i m e n t st h a tt h eo p e r a t i o np e r i o do fm a t - p p sa l g o r i t h mi s f 缸l e s st h a nt h a to ft h ea p r i o r ia l g o r i t h m ，a n dt h es p a e eo fm e m o r ym a d eu s eo fi sl e s st h a n a p r i o r ia l g o r i t h m t h u s ，e f f i e i e n c yh a sb e e ng r e a t l yi m p r o v e d i nt h er e s e a r c ho fm u l t i - a s s o c i a t i o nr u l e ，t h i sp a p e ri n t r o d u c e sa ni m p r o v e df p c h a l g o r i t h mb a s e do nf p t r e e i nt h e $ a m l 。l a y e rd a t am i n i n go f f p - c ha l g o r i t h m ，i tc o n s t r u c t s 2 望查整茎查堂璧主兰垒堡塞 塑薹 f p t r e ei nt h ed i f f e r e n tl a y e r ss e p a r a t e l y i nt h ed a t am i n i n go f c r o s s e dl a y e ra s s o c i a t i o nr u l e s ， f o rt h ea l r e a d ym i n e df r e q u e n c yi t e m so ft h es a l t l el a y e ra s s o c i a t i o nm l e s ，i tf i n d so u tt h e r e l a t e dt r a n s a c t i o ns e ta n dm i n e st h ea s s o c i a t i o nr u l eb e t w e e nl a y e r s ，i th a si m p r o v e d t r a d i t i o n a lm l - c ha l g o r i t h mt h a tm a yl o s et h ea s s o c i a t i o nb e t w e e nt o w l a y e r s f p - c h a l g o r i t h mi sak i n do fb o t t o m - t o - t o pm i n i n ga l g o r i t h m ，a v o i d i n gt h el o s so ff r e q u e n c yi t e m s a n do v e r e o m l n gt h ed e f i c i e n c y o f m l - c ha l g o r i t t m x f i n a l l y , t h i sp a p e rp o i n t so u tm e d e f i c i e n c i e sa n da s p e c t st h a tn e e df u r t h e ti m p r o v e m e n t s k e y w o r d s ：a s s o c i a t i o nr u l e ；m i n i n ga l g o r i t h m ；t r a n s a c t i o np r u n i n g ；p a r t f f i o ns e a r c h i n g ； 狰- t r e e 3 声明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所 公认的文献外，全都都是本人在导师指导下的研究成果，该论文尚未呈交于其 他任何学术机关作鉴定。 研究生签名：；芬南栖 日 期： 山咖s 、6 ； a f f i r m 【a i i o n 1d e c l a r et h a tt h i sd i s s e r t a t i o n ，s u b m i t t e di nf u l f i l l m e n to ft h er e q u i r e m e n tf o r t h ea w a r do fm a s t e ro fp h i l o s o p h yi ns h a n d o n gu n i v e r s i t yo fs c i e n c ea n d t e c h n o l o g y , i sw h o n ym yo w nw o r ku n l e s sr e f e r e n c e do fa c k n o w l e d g e t h e d o c u m e n th a sn o tb e e ns u b m i t t e df o rq u a l i f i c a t i o na ta n yo t h e ra c a d e m i c i n s 廿t u t e s 咖。碾最植 d 甜8 a s 0 ； 山东科技大学磺士学位论文 绪论 1 绪论 1 1 数据挖掘技术的发展 近年来，数据挖掘引起了信息产业界的极大关注，其主要原因是存在的大量数据， 可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识 可以广泛用于各种应用，包括商务管理、生产控制、市场分析、工程设计和科学探索等。 数据挖掘是从数据中发现隐含有用的信息或知识的技术，是随着人类进入信息社会以来 对信息价值的认识的不断提高而不断发展的，是为满足和解决当前“数据太多，信息不 足”的问题而产生的技术。 数据挖掘从八十年代提出到现在，不到二十年的时间，在国外的应用已经非常广泛。 尤其是在银行、电信、保险、交通、零售( 如超市) 等领域。数据挖掘所能解决的经典商 业问题包括数据库营销( d a t a b a s em a r k e t i n g ) 、客户群体划分( c u s t o m e rs e g m e n t a t i o n c l a s s i f i c a t i o n ) 、背景分析( p r o f i l e a n a l y s i s ) 、交叉销售( c r o s s s e l l i n g ) 等市场分析行为，以 及客户流失分析( c h u ma n a l y s i s ) 、客户信用记分( c r e d i ts c o r i n g ) 、欺诈发现( f r a u d d e t e c t i o n ) 等等。实际上，数据挖掘技术从一开始就是面向应用的。 我国的数据挖掘始于9 0 年代中期，到9 0 年代后期，初步形成了知识发现和数据挖 掘的基本框架。1 9 9 3 年国家自然科学基金首次支持对该领域的研究项目目前国内的 许多科研单位和高等院校竞相开展知识发现的基础理论和应用研究。研究重点正由发现 方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科闻的相互渗透。 但基本以学术研究为主，实际应用仍处于起步阶段。 数据挖掘被公认为“最富有成效的计算成果”和解决信息爆炸的有效方法。1 9 9 8 年， 数据挖掘被世界著名的g a r t n e r g r o u p 公司评为当前十大关键技术。 1 , 2 关联规则挖掘的研究现状 1 2 1 关联规则的发展现状 由于关聪规则挖掘可以发现用传统的人工智能和统计方法无法发现的项与项或属 性与属性间的关系规律，因此具有重要的研究价值。同时它满足了人们从大规模数据存 储中获取知识的迫切需求。 目前世界上知名大学的研究机构和各大公司的研究部门都投入了大量精力对其 目前世界上知名大学的研究机构和各大公司的研究部门都投入了大量精力对其 坐查型垄查兰婴主兰壁笙苎 堕笙 进行研究，并取得了诸多研究成果。美国斯坦福大学智能数据库系统实验室开发出了大 量的商用化数据挖掘系统，如d b m i n e r 挖掘系统，它包含了许多先进的挖掘算法，用 户无需具有高级的统计知识和培训即可利用它挖掘出包含关联规则、序列模式、分类等 在内的多种类型的知识；该系统可以在多种平台上运行，并与许多主流的数据库管理系 统( 如s q l s e r v e r 、o r a c l e 等) 结合紧密；同时还引入了在线分析挖掘技术，使得系统更 能充分发挥数据仓库的分析优势。m 公司的a l m a d e n 实验室所进行的q u e s t 项目同 样也是数据挖掘研究领域中的佼佼者，该项目包含了对关联规则、序列模式、分类及时 间序列聚类的研究，其代表性的产品有：d b 2i n t e l l i g e n tm i n e rf o rd a t a ，该产品在m 的d b 2 平台上应用，也有w i n d o w s n t 下的类似产品。除了以上提及的世界知名的公司 和科研机构外，还有许多大学的研究机构和学者对该领域的发展做出了重要贡献，如加 拿大s i m o n f r a s e r 大学的j i a w e i h a n ，比利时赫尔辛基大学的m a n n i l a 、t o i v o n n e n 等都 是数据挖掘研究的著名专家，他们的许多工作在该领域中都是奠基性的。 近年来，国内的关联规则挖掘研究也正逐渐掀起高潮，出现了一批相关的科研项目， 在算法和应用方面取得了一些具有扩展性或突破性的研究成果。论文就关联规则挖掘技 术在实际中的应用、挖掘算法和相关扩展等方面加以介绍。 1 2 2 关联规则存在的主要问题 关联规则挖掘所面临的问题主要有以下几个方面： ( 1 ) 关联规则算法 以前基于支持度置信度框架的关联规则挖掘算法。“2 “2 ”都是先用支持度作为阈 值对搜索结果进行剪枝，产生频繁集，再对频繁集产生关联规则。以a p r i o r i 为代表的 传统的关联规则挖掘算法，其效率在实际应用中存在一些问题。如何提高算法效率是当 前关联规则挖掘算法研究的重要问题。 ( 2 ) 多层关联规则 对于许多应用，由于多维数据空间数据的稀疏性，在低层或原始层的数据项之间很 难找出强关联规则。在较高的概念层发现的强关联规则可能提供普遍意义的知识。目前 的多层关联规则研究中所使用的同层关联规则的算法效率不高，交叉层关联规则的挖掘 过程中，容易丢失频繁项集，算法的准确度相对较低。 2 山东科技大学硕士学位论文 1 3 论文的主要研究内容 数据挖掘的目标是采用有效的算法，从大量现有的数据集合中发现并找出最初未知 的但最终可理解的有用知识，并用简明的方式表示出来。是否能够达到预期的目的在很 大程度上与数据挖掘的算法有关。因此，算法研究在数据挖掘上起了至关重要的作用。 论文主要对数据挖掘中关联规则的挖掘算法进行了研究。关联规则用于发现大量数 据中项集之间有意义的关联，寻找出给定数据集中项之间的有趣关系。论文第二章介绍 了数据挖掘和关联规则的基本概念、讨论了数据挖掘的功能、分类以及关联规则的性质 及求解过程。第三章介绍了关联规则的经典算法、改进算法，提出了基于矩阵的m a t 算法与基于事务剪枝和分区查找的p p s 改进算法。第四章，实现了m a t - p p s 算法，通 过实验比较了m a t - p p s 算法相对于a p r i o r i 算法在运行时间，内存占用情况等方面的改 迸。第五章介绍了多层关联规则的基本算法，提出了一种针对m l - c h 算法的改进算法 f p c h 算法，并将两种算法做了比较。第六章对所做的工作进行了总结，并展望了论文 中有待于进一步解决的问题。 山东科技大学硕士学位论文基础知识 2 基础知识 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来 越多。面对海量的存储数据，如何从中发现有价值的信息或知识是一项非常艰巨的任务。 数据挖掘就是为了满足这种要求而迅速发展起来的。数据挖掘是指从大型数据库或数据 仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则。数据挖掘是人工智 能和数据库发展相结合的产物，是目前国际上数据库和信息决策系统最前沿的研究方向 之一，已引起了学术界和工业界的广泛关注。 2 1 数据挖掘 数据挖掘是从大量数据中提取或“挖掘”知识，或者说，数据挖掘是从数据中发现 隐含有用的信息或知识的技术。数据挖掘具有两个方面的含义： 技术上，是从大量的、模糊的、随机的实际数据中提取隐含在其中的，人们不可 能直接看到的重要信息和知识。 商业上，人们可以利用数据挖掘提取辅助商业决策的关键知识，即从数据库中自 动发现相关商业的模式。 可以说，数据挖掘是信息技术发展到一定阶段的必然产物，是拥有大规模数据库、 高效的计算能力、经营管理的压力和有效的计算方法后的产物，是从存放在数据库、数 据仓库或其他信息库大量数据中挖掘有用知识的一个过程。 2 1 1 数据挖掘的功能 数据挖掘用于指定挖掘任务中要找的模式类型。数据挖掘任务般可以分为两类： 描述和预测。描述性挖掘任务刻画数据库中数据的一般特性，而预测性挖掘任务则在当 前数据上进行推断，以进行预测。 在很多情况下，用户并不知道什么样的模式是有趣的，因此可能想探索多种不同的 模式，以从中选择自己感兴趣的模式。这就要求数据挖掘系统应该能够挖掘多种类型的 模式，以适应不同的要求。此外，数据挖掘系统应该能够发现各种粒度( 即不同的抽象 层) 的模式，应当允许根据用户给出的提示，指导或聚焦有趣模式的搜索。 2 1 2 数据挖掘的分类 数据挖掘是一个交叉学科领域，受多个学科影响( 如图2 1 ) ，包括数据库系统、统计 4 山东科技大学硕士学位论文垂j 出知识 学、机器学习、可视化和信息科学。此外，依赖于所用的数据挖掘方法，以及可以使用 的其他学科的技术，如神经网络、模糊和或粗糙集理论、知识表示、归纳逻辑程序设 计或高性能计算。依赖于所挖掘的数据类型或给定的数据挖掘应用，数据挖掘系统也可 能集成空间数据分析、信息检索、模式识别、图像分析、信号处理、计算机图形学、w e b 技术、经济、商业、生物信息学或心理学领域的技术。由于数据挖掘源于多个学科，因 此产生了大量的、各种不同类型的数据挖掘系统，主要包括根据模式类型的分类和根据 使用技术的分类。 图2 1 数据挖掘受多学科的影响 f i g 2 1d a m m i n m gi sm a p a c t e di nm a n ys u b j e c t 根据发现的知识类型( 或数据挖掘所产生的模式类型分类) ，主要有以下几种： 概念类描述：特征化和区分 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类和概念可 能是有用的。这种类或概念的描述称为概念类描述。这种描述可以通过以下方法得到： 数据特征化：是目标数据的一般特征或特性的汇总。 数据区分：将目标类对象的一般特性与一个或多个对比类对象的一般特性比较。 数据特征化和区分：同时应用数据特征化和数据区分进行描述。 关联分析 关联分析( a s s o c i a f i o na n a l y s i s ) 的目的是发现关联规则，这些规则展示了属性 值频繁的在给定数据集中一起出现的条件。关联分析广泛应用于购物篮或事务数据分析 中。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分 类设计、交叉购物等。 分类和预测 5 山东科技大学硕士学位论文基础知识 分类是这样的过程，它找出描述并区分数据类或概念的模型( 或函数) ，以便能够使 用模型预测类标记未知的对象类。预测的目的是从历史数据中自动推导出给定数据的推 广描述，从而能对未来数据进行预测。分类和预测之间的区别在于，分类是预测类标号 ( 或离散值) ，而预测是建立连续值函数模型。例如可以建立一个分类模型，对银行贷款 的安全或风险进行分类；同时可以建立预测模型，给定潜在顾客的收入和职业，预测他 们在计算机设备上的花费。 聚类 与分类和预测不同，聚类是在预先不知道目标数据库包含多少类的情况下，力求将 所有的记录归并不同的类。通常对数据进行聚类或分组要根据“最大化类内相似度，最 小化类间相似度”的原则进行。 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这些数据 对象是孤立点( o u t l i o r ) 。大部分数据挖掘将孤立点视为噪音或异常而简单丢弃。然而， 在一些应用中，罕见的事件可能比正常出现的更有价值。例如，在医疗分析中，某些对 多种治疗方式的不同寻常的反应数据可能成为孤立点，但是这些数据对于治疗却非常重 要。对孤立点数据进行分析称为孤立点分析。 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 是描述行为随时间变化的对象的规律或趋势，并 对其建模。这种分析除包括时间相关数据的特征化、区分、关联、分类或聚类，还包括 时间序列数据分析、序列或周期模式匹配和基于类似型的数据分析。 2 1 3 数据挖掘的过程 数据挖掘过程一般需要经历确定挖掘对象、准备数据、建立模型、数据挖掘、结果 分析与知识应用这样几个阶段，这些阶段在具体实施中可能需要重复多次。为完成这些 阶段的任务，需要不同专业人员参与其中，这些专业人员主要是业务分析人员、数据分 析人员和数据管理人员。 1 确定挖掘对象 定义清晰的挖掘对象，认清数据挖掘的目标是数据挖掘的第一步。数据挖掘的最后 结果往往是不可预测的，但要探索的问题应是有预见性的、有目标的。 2 准备数据 ( 1 ) 数据的选择 6 山东科技大学硕士学位论文基础知识 在确定数据挖掘的业务对象后，需要搜索所有与业务对象有关的内部和外部数据， 从中选出适合于数据挖掘应用的数据。 ( 2 ) 数据的预处理 在选择数据后，还需要对数据进行预处理，对数据进行清洗，解决数据中的缺值、 冗余、数据值的不一致、数据定义的不一致、过时的数据等问题。在数据预处理中，有 时还需要对数据进行分组，以提高数据挖掘的效率、降低模型的复杂程度。 3 挖掘模型的构建 将数据构建成一个分析模型，这个分析模型是针对挖掘算法建立的。建立一个真正 适合挖掘算法的分析模型，是数据挖掘成功的关键。模型的建立必须从数据的分析开始， 为模型选择变量。然后从原始数据中构建新的预示值。从数据中选取一个子集或样本建 立分析模型。最后，通过转化变量，使之和选定用来建立模型的算法一致。 4 数据挖掘 对所得到的经过转化的数据进行挖掘，除了完善与选择合适的算法需要人工干预 外，数据挖掘工作都由挖掘工具自动完成。 5 结果分析 当数据挖掘出现结果后，要对挖掘结果进行解释并且评估。具体的解释与评估方法 一般根据数据挖掘操作结果所制定的决策成败来定。在许多情况下，利用可视化技术可 将数据挖掘结果表现得更清楚，更有利于对数据挖掘结果的分析。 6 知识的应用 数据挖掘的结果经过业务决策人员的认可，才能实际利用。为使数据挖掘结果能在 实际中得到应用，需要将分析所得到的知识集成到业务信息系统的组织机构中去，使这 些知识在实际的管理决策分析中得到应用。 2 2 关联规则 关联规则的发现是数据挖掘中最成功和最重要的一项任务，它的目标是发现数据集 中所有的频繁模式。关联规则可用于发现交易数据库中不同商品( 项) 之间的联系，这些 规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。这样的规则可 以应用于商品货架设计、存货安排以及根据购买模式对用户进行分类。 2 2 1 关联规则的基本概念 设i - i l ，i 2 ，i m ) 是二进制文字的集合，其中的元素称为项( i t e m ) 。记d 为事务t 的集 7 山东科技大学硕士学位论文基础知识 合，这里事务t 是项的集合，并且t c i 。对应每一个事务有唯一的标志，如事务号，记 作t i d 。设x 是一个i 中项的集合，如果x c - t ，那么称事务t 包含x 。 一个关联规则是形如x j y 的蕴涵式，这里x - - i ，y c i ，并且x iy = 巾。规则x j y 在事务集d 中的支持度( s u p p o r t ) 是事务集中包含x 和y 的事务数与所有事务数之比，记 为s u p p o r t ( ： ( j y l ，即 s u p p o r t ( xy ) = i t ：x u y c 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 j y ) = i t ：x u y - - t ，t e d ) 川 t ：x c - t ，t d i 项的集合称作项集( i t e m s e t ) 。包含k 个项的项集称为k 一项集。如集合 c o m p u t e r , f i n a n c i a l _ m a n a g e m e n t _ s o f t w a r e 是一个2 一项集。项集的出现频率是包含项集的事务数， 简称为项集的频率、支持计数或计数。如果项集的出现频率大于或等于r a i n _ s u p 与d 中事务总数的乘积，则称项集满足最小支持度r a i n _ s u p 。如果项集满足最小支持度，则 称它为频繁项集( f r e q u e n ti t e m s e 0 。频繁k 一项集的集合通常记作l k 。 给定一个事务集d ，挖掘关联规则问题就是产生支持度和置信度分别大于用户给定 的最小支持度和最小置信度的关联规则。动态地看，d 中含x u y 的事务越多 时，s u p ( x jy ) 越大，且s u p ( x jy ) 0 ，1 ；d 中含x 的事务且同时含y 的越多时， c o n f ( xy ) 越大，且c o n f ( xy ) 【0 ，1 。根本任务是给出i 和d 后，找出所有x 和y ， 它们具备关系x ；y ，且s u p jy ) s o 和c o n f ( x j y ) t c o 。这里s o 和c o 为事先设定 的两个阀值，即最小界限。 2 2 2 关联规则的性质 性质1 ：子集支持 设a 和b 是两个不同的项目集，如果a - - b ，则s u p p o r t ( a ) s u p p o r t ( b ) ，因为d 中 所有支持b 的交易也一定支持a 。 性质2 ：非频繁项目集的超集也一定是非频繁的 如果a 在d 中不满足最小支持度，即s u p p o r t ( a ) m i n _ s u p ，a 的每个超集b 也不 是频繁的。由关联规则性质1 可得s o p p o r t ( b ) - 一- 一m i n _ s u p ，因此 a 也是频繁的。特别的，如果a = “2 ，i k ) 是频繁的，则它的k 个基数为( k - 1 ) 的子集都 是频繁的。 性质4 ：一个项集是频集当且仅当它的所有子集都是频集。 根据常用的a p f i o f i 性质，可以引出结论：任何非频繁的( k 一1 ) 一项集都不可能是频繁 k 项集的子集。这是a 事r i o f i 算法遵循的规则。在找出频繁k - 项集时，( k - 1 ) 一项集不是频 繁项集的就不必考虑了。由此引出a p d o f i 的另一个性质：一个k 项集是频繁项目集， 当且仅当其所有的( k 一1 ) 子项集是频繁的。 2 2 3 关联规则的求解过程 为挖掘有效的关联规则，必须给定最小支持度和最小置信度。关联规则总是在d 中求解，求出所有支持度和置信度分别超过m i t l _ s u p 和n f i n _ c o n f 的关联规则，即求解 满足s u p p o r t ( x t 3 y ) ，m i n _ s u p ，c o n f i d e n c e ( x w y ) m i n _ c o n f 的规则x j y 。这种挖掘 过程一般可分为两个方面： ， 第一，求解事务数据库d 节的所有频繁项目集，即所有支持度不低于用户给定的 最小支持度m i ns u p 的项目集。 第二，基于上述已求解得到的频繁项集来生成所有关联规则，对每一个频繁项目集 a ，找到a 的所有非空子集a ，如果比率s u p p o r t ( a ) s u p p o a ( a ) m i n _ s u p ，就生成关联规 则。即从第一步得到的频繁集中开采置信度不小于用户规定的最小置信度m i n c o n f 的 规则。 2 2 4 关联规则的分类 根据不同的标准，关联规则有多种分类方法： ( 1 ) 根据规则中所处理的值的类型可以分为布尔关联规则和量化关联规则。布尔关 联规则( b o o l e a n a s s o c i a t i o nr u l e ) 处理的值都是离散的、种类化的，它所考虑的是项的在 与不在。例如，下面的规则是布尔关联规则： 购买面包j 购买牛奶 s u p p o r t = 5 ，c o m f i d e n c e = 7 5 】 量化关联规贝u ( q u a n f i t n i v ea s s o c i a t i o nr u l e ) 也是多值关联规则，所描述的是量化的 项或属性之间的关联。例如，下面的规则是量化关联规n - 年龄( “3 0 ，3 9 ) 收入( “2 万，4 万”) j 购买面包 ( 2 ) 根据规则中涉及的数据维可以分为单维关联规则和多维关联规则。单维关联规 贝, 1 ( s i n g l e d i m e n s i o n a la s s o c i a t i o nr u l e ) 中，只涉及到数据的一个维，例如，下面的规则 0 些查型垫查堂堡主兰垡丝苎 量型塑望 贝l j ( s i n g l e d i m e n s i o n a la s s o c i a t i o nr u l e ) 中，只涉及到数据的一个维，例如，下面的规则 只涉及一个维“购买”维： 购买面包j 购买牛奶 在多维关联规贝i j c m u l t i d i m e n s i o n a la s s o c i a t i o nr u l e ) 中，要处理的数据将会涉及多 个维。例如，下面的规则涉及到三个维“购买”维，“年龄”维，“收入”维： 年龄( “3 0 ，3 9 ，) 收入( 2 万，4 万，) j 购买面包 一句话，单维关联规则是处理单个属性中的一些关系，多维关联规则是处理多个属 性之间的某些关系。 ( 3 ) 根据规则集所涉及的抽象层可以分为单层关联规则和多层关联规则。单层关联 规贝l ( s i n g l e l e v e la s s o c i a t i o nr u l e ) 在给定的规则集中，不涉及不同抽象层的项或属性。 例如，下面的规则是单层关联规则： 年龄( “3 0 ，3 9 ”) j 购买面包 多层关联规则( m u h i a s s o c i a t i o nm l l l e ) 在给定的规则集中，涉及不同抽象层的项或 属性。例如，下面的规则是上下层关联规则： 年龄( “3 0 ，3 9 ”) j 购买面包年龄( “3 0 ，3 9 ，) j 购买全麦面包 自东辩鼓大学壤士学在论文关联援臻l 握篝法的改遘 3 关联规则挖掘算法的改进 3 1 a p r i o r i 经典算法 a f i o f i 算法是种最有影响的挖掘布尔关联规则频繁项集的算法。 3 1 1 算涤步骧 a p r i o r i t l 9 蕊甜乳蚓算法使用一种逐层搜索的迭代方法，使用k 项集搜索取 1 ) 项 集。首先，找出频繁1 ，项集的集合l 1 。l 。用于找频繁2 一项集的集合l 2 ，黼b 用于找 王e ，麴霓下去，壹裂不耱找至l 频繁鏊，壤襄。确定每令珐均薏要翔疆一次数攒痒。a p r i o r l 算法的主袋步骤分为两步： 一、连接 为我玟，逶过l 与鑫己连接产生候选k - 矮集蕊集合。该娱选顼集熬粲会记薅。 设1 1 和1 2 鼹l k 1 中的项集。记号k 【j 】裘示l 的第j 项( 例如，1 1 【k 一2 】表示1 l 的倒数笫3 项) 。 为方便计，假定事务或项集中的项按字典次序排序。执行l b l l k - l ，其中l k 1 的元素 是可连接瓣，如果它裁籍( 珏2 ) 个瑷鞠霾。帮是，k 1 靛元素l l 秘1 2 是霹逡犊豹，热采 0 1 【1 - 1 2 【1 ) ( 1 1 2 1 2 1 ) 八 ( 1 1 k - 2 = l k 2 】) 八( 1 l k - 1 】h k - 1 ) 。祭件( 1 1 【k - 1 m i n s u p r e t u r nl ；u 蠢越 产擞候选项集过程a p r i o r i g e n ( f r e q u e n t ( k 1 ) - i t c m s e t sk i ；m i l l i n n l r as u p p o r tt h r e s h o l d m i as u p ) ： f o re a c hi t e m s e t l i 专l k - i f o r e a e hi t e m s e t 毛i e - 1 i f ( 氇 1 1 - - - = 1 2 1 1 ) a o l 2 1 一- - - 1 2 1 2 ) a 。a 氇f l ( - 2 】一1 2 黔2 】) a o l 鹜l 】k 隆l 】) ) e _ l l ”耘 i f h a si n f r e q u e n t _ s u b s e t ( c ，1 4 ) d e l e t e 糖授劳：蘩 | 臻无效淹羧 e l s e a d dc t o c k ； r e t u r nc 捡裂。黪氆一1 ) - z 耍爨建雾羲繁：h 数她鲻噬冀酬d i d 盐喀删f t e q u e n t ( k - t ) - i t s e tk 0 f o re a c h 取1 ) 一飘a b s e tgo f o i f s 诺l k i f e h mt r u e ； r e t m nf a l s e ； a 两o r i 蹩一稀宽度优先算法，遴邋对数据瘁d 懿多越稳攒采发瑷所鸯熬颓繁褒蠢 集，在每一趟扫描中只考虑具有同一长度k ( 即项瞄熊中所含项踺的个数) 的所有k - 项目 集。在第一髓挡摇中，a p r i o r i 霎法诗黪数摇痒蚤中掰舂孳令磷臻鹣支持覆，垒成爨寄长 度为i 静频繁项曩集。在屠续酶每趟扫描中，蓠先戳前一趟中掰发瑷静掰霄频繁顼蠢 榘为基础，生成所有薪盼候选项目黛( c a n d i d a t er e m s e t s ) ，即潜饪的频繁项网窳，然后扫 捶数攥痒魏诗雾这整壤逸矮翼集鹣支撩发，最嚣确定羧遮褒嚣然中褥一些翼委藏蠢菝繁 项目集羹笈上述过程赢戮再也发现不。r 新的频繁项霹集。葬法静关键在于生成较套懿 候选项目攘，也就是尽可始不生成和计搏那些不可能成为频繁颁瞬集的候选项目集。它 爨覆了这样一个基奉我痰：鬻一令凝繁壤霆集静经一予囊努霆瞧蹩蒺繁项爨爨。 出末事 技大学籁士学霞论文 关联囊刘掩援算法熬改迸 3 2 a p r i o r i 算法的改进 3 2 1 基苄潮努戆改进穷法翻3 s a v a s e r e 等设计了一个基于划分的算法，这个算法先把数据库从逻辑上分成几个互 不相交的绫，每次单独考虑一个分块并对它生成掰有的频集，然后把产生的频集合并， 蔫来生藏掰有可能静频集，最后计算这些项集豹赢持度。这墨分块静丈小选择要使得每 个分块可以被放入主存，每个阶段只需被扫描一次。而算法的磁确性是由每一个可能的 频集至少农萦一个分块中是频集保诞的。上面魇讨论的算法是阿以嘉度并行熬，可以把 每一分块