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

r e s e a r c ho nm i n i n gh i g hu t i l i t yi t e m s e t sa l g o r i t h m at h e s i ss u b m i t t e df o r t h ed e g r e eo fm a s t e r c a n d i d a t e ：z h a n gj i e s u p e r v i s o r ：a s s o c i a t ep r o f m ac h u a n x i a n g h u b e iu n i v e r s i t y w u h a n ，c h i n a 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 论文作者签名：姆 日期：3 - 6 i v 年石月卢日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家有关 部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学校可以允 许采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目的的前 提下，学校可以公开学位论文的部分或全部内容。( 保密论文在解密后遵守此规定) 作者签名：张l 指导教师签名： 白锄 日期：渺长夕 日期：- ，多- 尸 摘要 关联规则挖掘是数据挖掘领域一个重要的研究课题，传统的关联规则挖掘中只考虑 项目在事务中出现与否。然而，在一条事务中，顾客可能购买同一种商品多个，而每件 商品的利润也不尽相同。单纯基于支持度的数据挖掘可能会导致一些重要的项集因为支 持度低而不被发现。为解决这个问题，学者们提出了基于价值的项集挖掘。 通过对已有的高价值项集挖掘算法研究，发现现有的算法都是基于候选项集生成一 剪枝一检验方法，这些算法存在着与a p r i o r i 1 i k e 算法类似的不足之处：数据库扫描次数 太多，特别是当挖掘长模式高价值项集时弊端更为明显；另外产生的候选集过大，测试 候选集是否为可能高价值项集及计算项集的价值需要花费大量的时间。为此，本文提出 了一种新的数据结构：p h u i t r e e ( p o s s i b l eh i g hu t i l i t yi t e mt r e e ，简称p h u i t r e e ) 。利 用模式增长方法，提出了一种基于p h u i t r e e 的高价值项集挖掘算法d h u i 。在p h u i t r e e 中直接挖掘高价值项集，而不需要产生候选项集；计算项集的价值时不需要重复扫描数 据库。实验表明，d h u i 算法是一个高效的高价值项集挖掘算法。 最后，考虑到d h u i 算法是基于内存的一种挖掘算法，特别是在信息高度膨胀的今 天，许多企业的数据仓库已经达到千兆规模。很可能存在由于数据库过大而不能将数据 完全放入内存的情况，为了解决这个问题，本文采用数据库分离思想，提出了一种基于 d h u i 算法的高价值挖掘分布式算法d h u i d p 。 关键词：数据挖掘；关联规则；高价值挖掘；模式增长 a b s t r a c t a s s o c i a t i o nr u l e sm i n i n gi sa ni m p o r t a n tr e s e a r c ht o p i ci nd a t am i n i n ga r e a ，t r a d i t i o n a l m e t h o d so fa s s o c i a t i o nr u l em i n i n go n l yc o n s i d e rt h ea p p e a r a n c eo fa l li t e mi nat r a n s a c t i o n h o w e v e r ，c u s t o m e r sm a yp u r c h a s em o r et h a no n eo ft h es a m ei t e mi nat r a n s a c t i o n ，a n dt h e p r i c eo ft h ei t e m sm a yd i f f e r e n t d e r i v i n gi n t e r e s t i n gi t e m s e t sf r o mo n l ys u p p o r tv a l u e sm a y l e a ds o m ei m p o r t a n ti t e m s e t sn o tf o u n dd u et ot h e i rs u p p o r td e g r e ei sl o w s c h o l a r sp r o p o s e t h eu t i l i t ym i n i n ga t t e m p tt oo v e r c o m et h i sp r o b l e m t h r o u g ht h ee x i s t i n gh i g hu t i l i t yi t e m s e t sm i n i n ga l g o r i t h m sa n df o u n dt h a tt h e ya r e b a s e do nc a n d i d a t es e tg e n e r a t i o n - p r u n i n g - t e s t ，t l l e ya l lh a v et h es i m i l a rs h o r t a g ew i t h a p r i o r i l i k ea p p r o a c h ：t h o s ea l g o r i t h ms c a nt h e d a t a b a s et om a n y ，t h i sa b u s ei sm o r eo b v i o u s e s p e c i a l l yi nm i n i n gl o n gp a t t e r nh i g hu t i l i t yi t e m s e t s ：i na d d i t i o n ，t h es e to fc a n d i d a t e s g e n e r a t e di st o ol a r g et ot e s tw h e t h e rt h ec a n d i d a t es e ti sap o s s i b l eh i 曲u t i l i t yi t e m s e t sa n d c a l c u l a t et h eu t i l i t yo fi t e m s e t sn e e dt os p e n dal o to ft i m e t ot h i se n d ，t h i sp a p e rp r e s e n t sa n e wd a t as t r u c t u r en a m e dp h u i - t r e e ，u s i n gp a t t e r ng r o w t ha p p r o a c h , w ep r o p o s ea l l a l g o r i t h mb a s eo np h u i t r e e ( p o s s i b l eh i g l lu t i l i t yi t e mt r e e ，s h o r tf o rp h u i t r e e ) m i n i n g h i 曲u t i l i t yi t e m s e t sn a m e dd h u i m i n i n gh i g hu t i l i t yi t e m s e t s i np h u i - t r e ew i t h o u t c a n d i d a t eg e n e r a t i o n ，a n dc a l c u l a t et h eu t i l i t yo fi t e m s e t sw i t h o u tr e p e a ts c a nt h ed a t a b a s e e x p e r i m e n t ss h o wt h a td h u ii sa ne f f i c i e n ta l g o r i t h mi nm i n i n gh i g hu t i l i t yi t e m s e t s f i n a l l y ，t a k i n gi n t oa c c o u n tt h a tt h ed h u ia l g o r i t h mi sa k i n do fm e m o r y - b a s e dm i n i n g a l g o r i t h m s ，e s p e c i a l l yi ni n f o r m a t i o nh i g h l yi n f l a t e dt o d a y , m a n yc o m p a n i e sh a v er e a c h e d g i g a b i ts c a l ed a t aw a r e h o u s e i ti sp r o b a b l ye x i s td u et ot h ed a t a b a s ei st o ol a r g ea n dn o tb e a b l et oc o m p l e t es t o r et h ed a t ai n t ot h em e m o r y ，i no r d e rt os o l v et h i sp r o b l e m ，t h i sa r t i c l e u s e sad a t a b a s es e p a r a t ei d e a s ，p r o p o s e dah i g hu t i l i t ym i n i n gd i s t r i b u t e da l g o r i t h md h u i - d p b a s e do nd h u ia l g o r i t h m k e yw o r d s ：d a t am i n i n g ；a s s o c i a t er o l e ：h i g l lu t i l i t ym i n i n g ；p a t t e r ng r o w t h i i 目录 第一章绪论1 1 1 研究背景1 1 2 研究现状2 1 3 本文的主要工作3 1 4 本文的组织结构3 第二章数据挖掘及关联规则算法5 2 1 数据挖掘概述5 2 1 1 数据挖掘定义5 2 1 2 数据挖掘的发展现状6 2 1 3 数据挖掘流程7 2 2 关联规则挖掘概述8 2 2 1 基本概念9 2 2 2 关联规则挖掘过程9 2 3 关联规则经典挖掘算法1 0 2 3 1a p r i o r i 算法1 0 2 3 2f p g r o w t h 算法1 3 ， 2 4 本章小结1 7 第三章高价值项集挖掘介绍1 8 3 1 高价值挖掘相关定义1 8 3 2f u m 算法简介2 0 3 2 1f u m 算法过程2 0 3 2 2f u m 算法举例2 2 3 2 3f u m 算法分析2 3 3 3 本章小结2 4 第四章d h u i 算法2 5 4 1p h u i - t r e e 2 5 4 1 1p h u i - t r e e 数据结构2 5 4 1 2p h u i - t r e e 构建过程2 7 i i i 4 1 3p h u i t r e e 构建算法 4 2d h u i 算法 4 2 1d h u i 算法相关定理 4 2 2d h u i 算法过程 4 2 3d h u i 算法描述3 5 4 vd h u i d p 算法3 6 4 4 实验3 7 4 5 本章小结3 9 总结4 0 参考文献4 l 致 射4 5 攻读硕士学位期间发表的论文4 6 i v 第一章绪论 1 1 研究背景 第一章绪论帚一早硒y 匕 近年来，数据挖掘引起了信息产业界和整个社会的极大关注，其主要原因是伴随信 息化程度的不断推进，各种应用积累了大量的历史数据，并保存于大型数据库中，如果 没有强有力的工具，而对这种海量数据的理解已超出我们的能力，结果，重要的决策常 常不是基于数据储存库中信息丰富的数据，而是基于决策者的直觉。因此，研究数据挖 掘算法成为解决这一问题的迫切需求。大量的学者对数据挖掘进行了广泛的研究，针对 数据挖掘应用的几个方面，学者们提出大量优秀的算法。作为数据挖掘一个重要的研究 分支，频繁模式和关联规则挖掘一直以来是各学者研究的重点。 关联规则口一1 是由a g r a w a l 等人首先提出来的一个重要的数据挖掘研究课题，它反映 了大量数据中项目集之间有趣的关联或相关联系。频繁项集挖掘是关联规则挖掘应用中 的关键技术和步骤。诸多的研究人员对关联规则的挖掘问题进行了大量的研究。关联规 则的发现是找出支持度大于或者等于m i n s u p 并且置信度大于或者等于m i n c o n f 的所有 规则，其中m i n s u p 和m i n c o n f 是对应的支持度和置信度阈值。 在传统的频繁项集挖掘中，项集x 是否频繁只看其支持度是否大于支持度阈值。大 量高效的算法相继被研究者提出，例如：基于l e v e l - w i s e 算法“ 4 5 们和p a t t e r n g r o w t h 方法他一8 9 一训。但是，定义在频繁项集基础上的支持度，只关心项目在交易项中出现与 否，而不考虑其个数。为此，h j h a m i l t o n 等于1 9 9 7 年提出了s h a r ef r e q u e n t n u 挖掘， 这方面的算法主要有：f s m n 2 1 算法、s h f s m n 3 1 和d c g n 4 1 算法等。s h a r ef r e q u e n t 挖掘在频 繁项集挖掘的基础上考虑了项目在交易项中出现的个数，项目的单价这个重要的因素被 忽略。例如，在一个交易数据库中，经理的目标是从中发现所有利润大于或者等于阈值 的项集。在现实的零售业中，高价值的或者利润高的产品往往售出的比较少，而单纯基 于支持度的数据挖掘可能会导致一些利润高的项集因为支持度低而不被发现。而s h a r e f r e q u e n t 挖掘则只考虑了项目在交易项中出现的个数。仍不能满足客户的需要，因此， y a o 等明确提出了高价值项集挖掘。综合考虑项目在交易项中出现的个数和单价。本文 着重研究高价值项集挖掘算法。高价值项集挖掘就是从数据库中挖掘出所有价值大于一 定阈值的项集。 湖北大学硕士学位论文 1 2 研究现状 深入研究高价值项集挖掘有着重要的理论价值和现实意义。高价值项集挖掘研究尚 处于起步阶段，目前对高价值项集挖掘主要集中在串行算法的研究，一个可行的高价值 项集挖掘算法，必须具有如下特点：尽可能的加大剪枝力度，减少候选集的产生；尽可 能的减少扫描数据库的次数。 由于高价值项集挖掘与s h a r ef r e q u e n t 挖掘存在一定的数理关系，即将高价值项集 挖掘考虑的项目在交易项中出现的个数和单价当作项目在交易项中的权重处理。这样大 部分s h a r ef r e q u e n t 挖掘算法只用对数据库进行一定的处理就可以适用于高价值项集 挖掘。在本文中，将这类算法n 1 2 1 3 一毛埔一7 一吼憎瑚3 当作现有高价值项集挖掘算法的 一部分。在现有可用于高价值项集挖掘的算法中，y a o 等提出了u m i n i n g 及u m i n i n g _ h 算法乜，这种算法是基于数学理论的价值约束，并详细阐述了高价值项集挖掘的各种 特性，对高价值项集挖掘进行了完整的定义，频繁项集的先验知识并不适用于高价值项 集挖掘，但是该算法并不能找出所有的高价值项集。各研究者相继提出了各种算法，y l i u 等提出了t p 呦3 算法。y uc h i a n gl i 等提出了一系列的算法，f s m 算法是其早期算 法。后期y uc h i a n gl i 等提出了s h f s m 。之后，y uc h i a n gl i 等优化了s h f s m 的连接 步骤提出了d c g 算法。最近，y uc h i a n gl i 等利用i i d s 嘲方法，对s h f s m 和d c g 算法 进行了改进，提出了f u m 和d c g + 算法。以上这些算法都基于项目集生成一剪枝一检验方法。 即首先产生候选集q ，利用一定的剪枝策略缩减g 得到可能高价值项集p c k ，再通过 扫描数据库计算各可能高价值项集的价值，然后通过p c k 的自连接产生候选集c k + l ，重 复这个过程直到候选项集q 为空为止。 现行的高价值项集挖掘算法都是基于项目集生成一剪枝一检验方法，这些算法都是在 剪枝策略方面做了局部的改进。总的来说这些算法都是基于l e v e l - w i s e 方法，这些算 法都存在以下不足之处：候选项集产生的代价很高，尤其是在存在大量强模式或长模式 的时候。例如，当有1 0 4 个l 项集时，将会产生1 0 8 1 个长度为2 的候选项集。如果数 据库中存在一个长度为1 0 0 的高价值项集，这将一共产生2 啪一1 个侯选项。在检测阶段， 通过模式匹配的方式，重复扫描数据库计算候选项集价值，花费大量时间。 1 3 本文的主要工作 2 第一章绪论 在已有的高价项集算法中，均是l e v e l - w i s e 算法，针对基于l e v e l - w i s e 算法的不 足之处，本文主要进行了以下研究： 首先，本文以a p r i o r i 算法和f p g r o w t h 算法为例介绍二种重要的项集挖掘思想： l e v e l - w i s e 和p a t t e r n g r 0 w t h 。并且分析了这二种思想进行了优劣分析。 其次，本文对已有的高价值项集挖掘算法进行了详细的分析，以f u m 算法为例描述 了已有算法的过程，分析了已有算法的不足之处。 再次，针对已有算法的不足之处，本文设计新的数据结构p h u i - t r e e ，利用 p a t t e r n g r 0 w t h 方法，开发一种树形的高价值项集挖掘算法d h u i 。 最后，考虑到现在许多企业的数据仓库已经达到千兆规模。而本文提出的d h u i 算法 是一种基于内存的算法。可能存在所建的p h l r l t r e e 不能全部放入内存中的问题。为解 决这个问题，本文采用数据库分离思想，提出了一种基于d h u i 算法的高价值挖掘分布 式算法d h u i d p 1 4 本文的组织结构 ， 本文共分五章。 第一章为绪论，简要介绍了高价值项集挖掘的起源、发展及现状，分析了已有高价 值项集挖掘算法的不足之处，并简述了本文的研究内容。 第二章介绍了数据挖掘的相关概念，介绍二种有代表性的频繁项集挖掘算法： a p r i o r i 和f p - g r o w t h 算法。重点介绍了这二种算法上思想的差别，并分析了这二种算 法各自的优势和劣势。 第三章介绍了高价值项集挖掘算法的相关定义及概念，对已有的算法进行较为详细 的介绍，并以f u m 算法为例详细介绍了现有算法的过程及思想。分析了这类算法的优势 和劣势。 第四章提出了一种新的数据结构p h u l - t r e e ，在此树形结构上提出了一种新的高价值 项集挖掘算法d h u i 。详细的描述了算法的过程及相关理论。另外，根据d h u i 算法的特 点，提出了一种基于数据库分离的算法d h u i - d p 。此外，通过实验，针对本章提出的d h u i 算法，与已有的高价值项集挖掘算法进行了简要的对比。 湖北大学硕士学位论文 文章最后是对本文的工作进行了总结，并指出研究中存在的不足，并对进一步的研 究做了简要的展望。 4 第二章数据挖掘及关联规则算法 第二章数据挖掘及关联规则算法 2 1 数据挖掘概述 随着数据库技术的快速发展以及数据库管理系统的广泛应用，全球范围内的数据存 储量急剧上升。激增的数据里面隐含了很多重要信息，人们为了更好的使用这些数据， 需要对这些数据做深入地分析。然而，目前的数据库系统只能对信息进行简单的查询、 统计，而无法有效的发现隐藏于数据背后的信息，无法通过这些数据来预测未来的趋势。 由于没有有效的分析手段，导致虽然有较丰富的数据却不能获得有效的知识，数据挖掘 技术就是在这种需求和挑战下产生的，并得到了迅速的发展。 2 1 1 数据挖掘定义 数据挖掘是人们多年来对数据库技术、统计学、人工智能等进行大量研究和开发的 成果，在2 0 世纪8 0 年代末有了很大的发展。数据挖掘是指从数据库或数据仓库的大量 数据中揭示出隐含的、先前未知的、潜在有用的信息的非平凡过程【2 3 1 。它作为知识发现 过程中一个特定的步骤，是对大规模数据及数据间关系进行考察和建模的方法集。它的 目标是将大规模数据转化为有用的知识和信息。数据挖掘【2 4 】是- f - j 交叉学科，它把人们 对数据的应用从低层次的简单查询，提升到从数据中挖掘知识并提供决策支持。在这种 需求指引下，汇聚了大量不同领域的研究者，如人工智能、机器学习、统计学、模式识 别、数据可视化等方面的研究人员，投身于数据挖掘这个研究领域，形成新的技术热点。 2 1 2 数据挖掘的发展现状 数据挖掘的历史虽然较短，但却发展迅速，1 9 8 9 年8 月，在美国底特律召开的第1 l 届国际人工智能会议上【1 1 ，首次提出数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) 概念。随后，它引起了国际人工智能和数据库等领域的专家的广泛关 注。1 9 9 5 年，在加拿大蒙特利尔召开的首届知识发现和数据挖掘国际学术会议上，学术 界正式提出数据挖掘【2 】这一术语。目前数据挖掘的研究重点也逐渐从发现方法转向系统 应用，注重多种发现策略和技术的集成，以及多学科之间的相互渗透。i e e e 的k n o w l e d g e a n dd a t ae n g i n e e r i n g m l 会刊率先出版了k d d 技术专刊。并行计算、计算机网络和信息 工程等其它领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论。 5 湖北大学硕士学位论文 经过十几年的努力，数据挖掘领域已取得大量成果，很多软件公司也已研发出自己 的软件产品，并在一些发达国家率先应用。例如，i b m 公司开发的q u e s t 1 7 】和i n t e l l i g e n t m i n e r ；a d v a n c e ds o f t w a r ea p p l i c a t i o n 开发的基于人工神经网络的d bp r o f i l e ；a n g o s s s o f t w a r e 开发的基于规则和决策树的k n o w l e d g es e e k e r ；s g i 公司开发的m i n e s e t ；加 拿大s i m o nf r a s e r 大学开发的d b m i n e r 等。与国外相比，国内对数据挖掘和知识发现 的研究稍晚，没有形成整体力量。在我国，1 9 9 3 年国家自然科学基金首次支持了对该领 域的研究项目 2 4 o 随后，数据挖掘技术的研究引起了学术界的高度重视，并逐步成为业 界的研究热点课题。目前，国内的许多科研单位和高校也在进行本领域的基础理论和应 用方面的研究。 2 1 3 数据挖掘流程 数据挖掘过程一般由确定挖掘对象、数据准备、数据挖掘、结果分析、挖掘应用等 几个主要的阶段组成( 3 3 1 0 数据挖掘可以描述为这几个阶段的反复过程。 ( 1 ) 确定挖掘对象 数据挖掘中重要的一步是明确定义要解决的问题及数据挖掘的目的。其最后结果一 般不可预测的，但对挖掘的目的或要解决的问题应有预见，盲目的进行数据挖掘，是不 会成功的。 ( 2 ) 数据准备 数据准备阶段一般可分为4 个步骤n 1 ：数据集成、数据选择、数据预处理和数据转 换。数据集成是将多个文件或多数据库运行环境中的数据进行整合处理，如不同格式数 据的转换及各个部门数据的汇总。数据选择是根据数据挖掘目标，找出与业务对象有关 的数据信息，并从中找出适用于我们的应用需要的数据。数据预处理是为了提高数据质 量，对数据进行清理，为进一步的分析做准备。其目的是为了克服目前数据挖掘工具的 局限性。数据转换的一个重要工作是对数据进行编码，将数据转换成一个分析模型。另 外，数据库中属性的不同取值转换成数码形式将极大的提高搜索效率。 ( 3 ) 数据挖掘 这个阶段利用统计分析、数据挖掘算法等进行实际的操作，从而从数据库中找出有 用的知识。使用如机器学习、统计分析、人工神经元方法和模式识别方法等，选择高效 6 第二章数据挖掘及关联规则算法 的数据挖掘算法，如a p r i o r i 算法、f p - g r o w t h 算法等；数据挖掘，找出有用的知识和 模式；除了完善选择合适的挖掘算法以外，其余的一切工作都可自动完成。 ( 4 ) 结果分析 这个阶段主要是对挖掘结果进行分析h 1 ，尽可能直观的表达挖掘结果，以便用户理 解，可将结果以图表等直观的形式输出。通过定义兴趣指标，考查结果的简单性和正确 性，把信息从输出中过滤出来。利用可视化方法帮助用户理解所提出知识的有效性或对 基本的数据或现象做出结论；根据最终用户的目的对提取的信息进行评估分析，把有价 值的信息找出来并交给决策者。因此，这一步的任务是把结果表达出来，同时对挖掘出 的模式进行评价和过滤处理。上述处理数据挖掘阶段可以根据用户的目的重新进行某些 处理过程，并且在处理的任意阶段都可以返回以前的阶段进行再处理。 ( 5 ) 挖掘应用 将把挖掘出的信息应用到执行系统中，证明挖掘出的信息的价值。用预先知道且可 信的信息来验证挖掘出的信息的有效性，解决可能存在的矛盾。当然，在有些情况下， 也可以简单记录所挖掘出的信息并把它报告给用户，由用户自己来做下一步分析。 2 2 关联规则挖掘概述 关联规则挖掘【1 1 问题是r a g r a w a l 等人于1 9 9 3 年首先提出来的。关联规则是描述数 据库中一组数据项之间的某种潜在关联或规则。它是对某个事物与别的事物相互关系的 一种描述。 针对数据而言，关联规则是发现数据中项集之间潜在的关联或依赖联系【2 1 。关联规 则最初产生于零售业中。在超市中，顾客根据自己的需要一次购买自己所需要的产品， 伴随着条形码技术的广泛应用，使商家非常容易收集和存储大量销售数据。一条销售数 据记录通常包括与某个顾客相关的交易时间、交易中所购买的物品等等。通过对以往的 大量交易数据进行分析，就能获得有关顾客购买模式的知识或有用信息，从而便于进行 商业决策。一个典型的关联规则例子璐1 是：在超市中，9 0 的顾客在购买面包和黄油的同 时也会购买牛奶。其直观的意义是顾客在购买某种商品时同时也有某种程度的可能性去 购买另外的一些商品。找出所有类似这样的规则，对于企业制定生产销售策略、产品摆 放、市场调查分析以及市场营销策略等方面都有相当重要的意义。 7 湖北大学硕士学位论文 2 2 1 基本概念 关联规则是当前数据挖掘研究的主要方向之一，侧重于确定数据中不同领域之间的 联系，找出满足给定条件下，多个领域之间的依赖关系。 下面介绍一下关联规则挖掘领域中的一些基本概念叭2 3 ： ( 1 ) 数据项与数据项集 设i = f l i 2 ，“ 是m 个不同项目的集合，每个矗( k = l ，2 ，m ) 称为数据项( i t e m ) ， 数据项的集合i 称为数据项集( i t e m s e t ) ，简称项集，其元素个数称为数据项集的长度。 长度为k 的数据项集称为k 维数据项集，简称为k 一项集( k i t e m s e t ) 。 ( 2 ) 事务 事务t ( t r a n s a c t i o n ) 是数据项集i 上的一个子集，使得t i 。每个事务均有唯一 的标识符t i d 与之关联，不同事务的全体构成了全体事务集d b ( 即事务数据库) 。 ( 3 ) 数据项集的支持度 t i 为数据项集，b 为事务集d b 中包含x 的事务的数量，a 为事务集d b 中所包含 的所有事务的数量，数据项集x 的支持度( s u p p o r t ) 定义为：s u p p o r t ( x ) = 旱。项集x 的 支持度s u p p o r t ( x ) 描述项集x 的重要性。 ( 4 ) 关联规则 关联规则( a s s o c i a t i o nr u l e ) 可以表示为：r ：xjy ，其中：x i ，y i ， 并且x n y = a ，它表示如果项集x 在某一事务中出现，则必然会导致项集y 也在同一 事务中出现。x 称为规则的先决条件，y 称为规则的结果。 ( 5 ) 关联规则的置信度 对于关联规则r ：x y ，其中：x i ，y i ，并且x n y = 囝。规则r 的置信 度( c o n f i d e n c e ) 定义为： 8 第二章数据挖掘及关联规则算法 c 。n f i d e n c e ( r ：x = ，y ) 2 璺鬻 置信度描述了规则的可靠程度。 ( 6 ) 最小支持度与频繁项集 最小支持度( m i n i m u ms u p p o r t ) 表示发现关联规则要求数据项必须满足的最小支持 阈值，记为m i n s u p ，对于项集x ，x i ，若是有s u p p o r t ( x ) m i n s u p ，则称x 为频繁 项集。 ( 7 ) 最小置信度 最小置信度( m i n i m u mc o n f i d e n c e ) 表示关联规则所必须满足的最小可信度，记为 m i n c o n f ，它表示了关联规则的最低可靠性。 2 2 2 关联规则挖掘过程 给定一个事务数据库d b ，关联规则的挖掘过程一般可分以下两个步骤： ( 1 ) 挖掘出事务数据库中的所有频繁项集，即找出所有支持度不低于用户给定的最 小支持度的项目集。 ( 2 ) 基于频繁项目集生成所有的规则，即从第一步得到的频繁集中找出置信度不小 于用户规定的最小置信度的规则。 相对第一步而言，第二步的执行在内存、i o 以及算法效率上都比较容易，第一步 决定了关联规则挖掘的总体性能。大量的研究集中在如何快速的挖掘出数据库中所有的 频繁项集。为了解决挖掘关联规则的第一个子问题，必须对数据库进行扫描，计算候选 项集的支持度和置信度。而通常待挖掘的数据库中有很多属性或字段，且记录数量巨大， 因此，减少数据库扫描的次数及读取数据库的i o 次数成为解决这个问题的有效方法。 而更为重要的是，在挖掘频繁项目集时，待验证的项目集的数量可达到2 - _ 1 个( m 为项 目的个数) ，几乎是不可能对所有的项目都进行支持度的计算。目前有关关联规则的发 现算法主要是集中在研究如何能快速有效地挖掘频繁项目集，其研究热点主要集中在二 个方面：一是能对项目集进行更加充分地剪枝，尽最大可能最小化候选项目集；二是尽 最大可能减少扫描交易数据库的次数，从而提高算法的效率。关联规则挖掘的基本模型 9 湖北大学硕士学位论文 如图2 1 所示： 图2 1 关联规则挖掘模型 2 3 关联规则挖掘的经典算法 关于关联规则挖掘的算法比较多，主要分为基于l e v e l - w i s e 算法n 一 5 阳和 p a t t e r n - g r o w t h 方法口一乳9 1 。3 两大类。其中a p r i o r i 与f p - g r o w t h 阻1 是两个最具代表性的 不同类型的关联规则挖掘算法，这二个算法的思想和实现方式不同，各有自己的优势与 劣势，但是都是优秀的算法思想，之后的许多优秀的关联规则挖掘算法都是基于这两个 算法所进行的优化和改进。 2 3 1a p r i o r i 算法 a p r i o r i 算法是r a g r a w a l 等于1 9 9 4 年提出的为布尔关联规则挖掘频繁项集的原创 性算法，a p r i o r i 1 2 1 是一种宽度优先算法，通过对数据库d b 进行多次扫描，发现所 有频繁项集，在每趟扫描中只考虑具有同一长度k ( 即项目集中所含项目的个数) 的所有 k - i t e m s e t ，计算其支持度。在第一趟扫描中，a p r i o r i 算法计算数据库d b 中所有单个 项目的支持度，生成所有长度为l 的频繁项目集( 记为三- ) ，然后利用三一来挖掘三z ，即 频繁2 - i t e m s e t ：如此不断地循环，直至不能找到频繁k - i t e m s e t 为止，其中在发现每 个厶的过程中需要对整个数据库d b 扫描一遍。为提高频繁项集每一层产生的效率，使 用h p r i o r i 性质【1 1 对候选项集进行剪枝，压缩搜索空间，提高算法效率。 2 3 1 1 a p r i o r i 性质 定理2 - 1 ：对于项集x ，x i ，如果x 是频繁项集，则x 的所有非空子集也是频繁 的。 由定理2 - 1 可知，如果项集x 不是频繁项集，则x 的所有超集都不是频繁项集。 2 3 1 2a p tio ri 算法过程 l o 第二章数据挖掘及关联规则算法 根据以上的定理2 - 1 ，考察如何通过厶一- 找厶，其中k 2 ，这个过程由连接步和 剪枝步组成。 ( 1 ) 连接步：为找出所有的厶，通过厶一l 与自身连接产生候选k - i t e m s e t 的集合。 该候选项集合记作d 。 ( 2 ) 剪枝步：q 是厶的超集，也就是说，q 中的有些项集可能是非频繁的，但所 有的频繁k - i t e m s e t 都包含在q 中。可以通过扫描数据库，来确定g 中每个候选的支 持度，从而确定厶。然而，通过厶一l 与自身连接产生的候选q 可能会很大，这样所涉 及的计算量也就非常大。这就需要压缩g ，否则q + 1 将会以指数级增长，a p r i o r i 算法 通过使用a p r i o r i 性质对候选项集g 进行有效的剪枝。根据a p r i o r i 性质，任何非频繁 的( k 1 ) 项集都不是频繁k - i t e m s e t 的子集。因此，如果存在候选k - i t e m s e t 的( k - 1 ) 项子集不在厶一1 中，则该候选项集也不可能是频繁的，从而可以将该项集从g 中删除。 这种子集测试可以使用所有频繁项集的h a s h 散列树口1 来快速地完成。把每个事务中所 包含的k 维项目集存储到h a s h 树中，然后对每个候选项目集查找该树结构，如果某个 候选项目集包含在树中，则对其进行计数。a p r i o r i 算法的相关过程描述如下。 算法a p r i o r i ( 挖掘频繁项集) 输入：交易数据库d b ( 设t 为交易数据库中的事务集) ，最小支持度m i n s u p 。 输出：d b 中的频繁项目集l 。 其核心程序简要描述如下： ( 1 ) 三l = l a r g c l i t e m s c t s ： ( 2 ) f o r ( k = 2 ；厶一, n u l l ；l 卅) d 0b e g i n ( 3 ) c k = a p r i o d _ _ g e n ( l k 一1 ) ；新的候选集 ( 4 ) ( 5 ) ( 6 ) ( 7 ) f o ra l lt r a n s a c t i o n st td ob e g i n g = s u b s e t ( c k ，f ) ；事务t 中包含的候选集 f o ra l lc a n d i d a t e sc gd o c c o u n t + + ： 湖北大学硕士学位论文 ( 8 )e n d ( 9 )e n d ( 1 0 ) 厶= c c kic c o u n t m i n s u p ) 七 ( 1 2 ) r e t u r n 三= u 厶； 2 3 1 3a p rio ri 算法分析 a p r i o r i 算法的优势：a p r i o r i 具备思想清晰简单，执行过程循序渐进的优点，该算 法应用了频繁项集的先验知识，使用此性质能对候选项集有效地过滤，尤其是对短模式 数据有很好的挖掘效果。 a p r i o r i 算法的劣势凹1 ：虽然a p r i o r i 算法能够有效地产生所有关联规则，但在效 率上还是有一些问题： ( 1 ) 数据库扫描次数太多，对k - i t e m s e t s 计算的每个支持度，都需要扫描一次数 据库，特别是在对长模式进行挖掘时，该弊端更为明显。 ( 2 ) 产生的候选集过大，例如，如果有1 0 4 个频繁l 项集，则a p r i o r i 算法需要产 生多达1 0 8 个候选2 项集，检查其频繁性。此外，为发现长度为1 0 0 的频繁模式，如 i l , i 2 ，d l o o ，它必须产生多达2 啪1 0 个候选集，虽然采取了一定的剪枝策略，但候选 项集仍会很大。 ( 3 ) 由于候选集的庞大，测试候选项集是否为频繁项集需要花费大量的时间。 2 3 2f p - g r o w t h 算法 针对a p r i o r i 算法的不足，h a n 等人提出了著名的f p - g r o w t h 聃3 算法。在f p - g r o w t h 算法中分而治之的策略，将一个问题分解为多个较小的子问题，从而发现以某个特定后 缀结尾的所有频繁项集。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 分成一组条 1 2 第二章数据挖掘及关联规则算法 件f p - t r e e ，并通过递归调用f p - g r o w t h 的方法来直接产生频繁项集，因此在整个发现 过程中也不需产生候选项目集。f p - g r o w t h 算法克服了a p r i o r i 算法中存在的问题，并 在执行效率上也明显好于a p r i o r i 算法。下面将对与f p t r e e 相关的概念及f p g r o w t h 算法进行介绍。 2 3 2 1f p t r e e 结构 频繁模式树f p t r e e 的定义如下： 由h a n 等人定义的f p t r e e 中的每个节点由4 个域组成阳3 ，如表2 一l 所示： 表2 1f p t r e e 结点结构 其中n o d e - n a m e 域用于记录该节点的项目名，n o d e - c o u n t 域用于记录到达该节点的 子路径数量，n o d e p a r e n t 域用于记录指向父节点的指针，如果父节点不存在，则值为 n u l l ，n o d e - 1 i n k 域用于链接树中的同名节点，可以快速的访问树中与其同名的所有节 点，如果不存在同名节点，则值为n u l l 。 另外，为便于树遍历，f p 树还用一张表来存储每个频繁项目结点的头指针。创建一 个频繁项目头表( h e a dt a b l e ，简称为h t a b l e ) ，项目头表中的每个结点由二个域组成阻1 ， 如表2 - 2 所示： 表2 - 2f p t r e e 头结点结构 其中n o d e - n a m e 域用于存放频繁项节点名，在整个h t a b l e 中频繁项目按照支持度降 序存放，n o d e - h e