（计算机应用技术专业论文）客观兴趣度模型及其在关联分类中的应用研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着信息技术的高速发展，数据库应用的不断深化，数据挖掘已成为当今研究的热 点之一。其中，关联规则挖掘和分类规则挖掘是应用范围较为广泛的两个分支。由于关 联规则具有因果特性，当关联规则的后件表示为某种类别时，关联规则就具有了分类规 则的特性。因此，关联规则挖掘可以与分类规则挖掘技术相结合，继而得到了一种新的 分类方法基于关联规则的分类。 传统的关联分类挖掘算法主要采用基于一般频繁项的关联规则算法，往往会产生大 量的分类关联规则，并且其中存在大量的冗余规则，不利于分类器的建立和使用。虽然 目前已提出了一些高效的关联分类算法，但仍存在一些不足之处。 本文在现有的兴趣度模型及关联分类挖掘算法的研究基础上，提出了一种新的客观 兴趣度模型和一种改进的关联分类算法，论文的主要工作如下： ( 1 ) 对关联分类挖掘的基本理论进行了总体的研究，包括关联规则挖掘和分类规则 挖掘的基本概念，挖掘过程，并介绍了两种经典的关联分类挖掘算法，在此基础上指出 了关联分类挖掘的研究方向。 ( 2 ) 如何从大量的关联模式中筛选出用户感兴趣且有价值的规则，是算法研究的重 要内容之一。由于支持度置信度框架模型有一定的局限性，本文在总结分析已有的兴趣 度模型下，提出了一种新的客观兴趣度模型，用来修剪无趣的规则，从而筛选出真正有 价值的规则。并通过实例和实验证明该兴趣度模型的有效性和实用性。 ( 3 ) 针对现有的经典关联分类算法的不足，提出一种基于d m i n e r 的关联分类算法， 该算法在产生分类关联规则时只需要扫描事务数据库一次，通过生成频繁闭项集，大大 减少分类关联规则的产生数量。此外，新算法结合置信度、兴趣度模型以及数据库覆盖 策略对规则修剪进行改进，占用的存储空间相对减少。理论分析和测试实验证明了新算 法在性能上的优越性。 关键词：数据挖掘；关联分类；客观兴趣度模型；频繁闭项集；d m i n e r ； 西南交通大学硕士研究生学位论文 第1 i 页 a b s t r a c t w i t ht h e r a p i d l yd e v e l o p m e n to fi n f o r m a t i o ni n d u s t r i a l i z a t i o n ，a n dw i t hq u i c k l y d e e p e n i n go ft h ea p p l i c a t i o nd a t a b a s e ，d a t am i n i n gh a sr e c e n t l yb e c o m et h eh o t s p o t ，i nw h i c h a s s o c i a t i o nr u l em i n i n ga n dc l a s s i f i c a t i o nr u l em i n i n ga r et w oo ft h ea c t i v eb r a n c h e s 、析m b o a r da p p l i c a t i o n b e c a u s ea s s o c i a t i o nr u l e sh a v et h ef e a t u r e so fc a u s ea n de f f e c t ，w h i c h m e a n st h a tw h e nt h ec o n s e q u e n c eo fa s s o c i a t i o nr u l e sr e p r e s e n t st h ec l a s sl a b e l ，a s s o c i a t i o n r u l e sc o n t a i nc l a s s i f i c a t i o n r u l e s f e a t u r e s ，a s s o c i a t i o nr u l e m i n i n gc o m b i n i n g w i t h c l a s s i f i c a t i o nr u l e m i n i n gc a ng e n e r a t ean o v e lc l a s s i f i c a t i o nm e t h o d ，i e ，a s s o c i a t i v e c l a s s i f i c a t i o n h o w e v e r , t h et r a d i t i o n a la s s o c i a t i v ec l a s s i f i c a t i o nm e t h o d sa r eb a s e do nf r e q u e n ti t e m s e t s t h e ys u f f e rf r o mo n em a j o rd e f i c i e n c y , t h a ti s ，t h e yo f t e no b t a i nah u g es e to fc l a s s i f i c a t i o n r u l e sf r o mt h et r a i n i n gd a t as e t , m a n yo fw h i c ha r er e d u n d a n t a l s o ，i ti sc h a l l e n g i n gt ob u i l d a n du s et h ec l a s s i f i e r a l t h o u g hs o m ei m p r o v e da l g o r i t h m sh a v eb e e np r o p o s e d ，t h e ys t i l lh a v e s o m ed i s a d v a n t a g e s i nt h i st h e s i s ，a f t e rc u r r e n ta s s o c i a t i v ec l a s s i f i c a t i o n m i n i n ga l g o r i t h m sa n d i n t e r e s t i n g n e s sm e a s u r e sa r es y s t e m i c a l l ya n a l y z e da n dr e s e a r c h e d ，an o v e lo b j e c t i v e i n t e r e s t i n g n e s sm e a s u r ea n do n ei m p r o v e da l g o r i t h m sa r ep r o p o s e d t h em a i nt a s k si nt h e t h e s i sa r ea sf o l l o w s ： ( 1 ) t h eb a s i ct h e o r i e s f o ra s s o c i a t i v ec l a s s i f i c a t i o nr u l e m i n i n g a r ed i s c u s s e d s y s t e m a t i c a l l yi nt h i st h e s i s ，i n c l u d i n gt h eb a s i cc o n c e p t sa n dm i n i n gp r o c e s so fa s s o c i a t i o n r u l em i n i n ga n dc l a s s i f i c a t i o nr u l em i n i n g ，a n dt w oc l a s s i c a la s s o c i a t i v ec l a s s i f i c a t i o nm i n i n g m e t h o d s t h e n ，t h ef u t u r er e s e a r c h e so fa s s o c i a t i o nr u l em i n i n ga r ep o i n t e do u t ( 2 ) h o w t os e l e c tt h ei n t e r e s t e da n dv a l u a b l er u l e sf r o mal a r g en u m b e ro fa s s o c i a t i o n r u l e si so n eo ft h ei m p o r t a n tc o n t e n t si n s t u d yo fm i n i n ga l g o r i t h m b e c a u s et h e r ei sa l i m i t a t i o ni nm o d e lb a s e do ns u p p o r ta n dc o n f i d e n c em e a s u r e ，t h ea u t h o ro ft h i st h e s i s a n a l y z e sa n dr e s e a r c h e ss o m ec u r r e n ti n t e r e s t i n g n e s sm e a s u r e s ，a n dp u t sf o r w a r dan o v e l o b je c t i v ei n t e r e s t i n g n e s sm e a s u r ew h i c hi su s e dt op r u n et h en o n i n t e r e s tr u l e si no r d e rt o d i s c o v e rt h er e a li n t e r e s t e dr u l e s ，t h ei n s t a n c ea n de x p e r i m e n t a lt e s t ss h o wt h a tt h eh o v e l i n t e r e s t i n g n e s sm e a s u r ei se f f e c t i v ea n dp r a c t i c a l ( 3 ) t h ea u t h o ro ft h i st h e s i sa d d r e s s e ss o m ed i s a d v a n t a g e so ft h ep o p u l a ra s s o c i a t i v e c l a s s i f i c a t i o nm e t h o d sa n dp r o p o s e san o v e la s s o c i a t i v ec l a s s i f i c a t i o na l g o r i t h mb a s e do n d m i n e r t h en o v e la l g o r i t h ms c a n sd a t a b a s eo n l yo n c et om i n ef r e q u e n tc l o s e di t e m s e t s 西南交通大学硕士研究生学位论文第1 i i 页 w h i c hw o u l dh e l pr e d u c et h en u m b e ro fc l a s s i f i c a t i o nr u l e s a l s ot h en o v e la l g o r i t h ma p p l i e s t h ei n t e r e s t i n g n e s sm e a s u r et op r u n er u l e s ，w h i c ht a k e sm u c hl e s ss t o r a g es p a c e t h e t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lt e s t ss h o wt h a tt h en o v e la l g o r i t h mi ss u p e r i o ri nt h e p e r f o r m a n c e 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 v ec l a s s i f i c a t i o n ；o b j e c t i v ei n t e r e s t i n g n e s sm e a s u r e s ； c l o s e df r e q u e n ti t e m s e t s ；d m i n e r ； 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西 南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密囹，使用本授权书。 ( 请在以上方框内打“) 学位论文作者签名： 森论 日期：2 0 1 0 年6 月1 日 指导老师签名：蝈纵 7 日期：2 0 1 0 年钿f 日 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： ( 1 ) 基于支持度和置信度的框架模型有一定的局限性，本文在总结分析已有的兴趣 度模型下，提出了一种新的客观兴趣度模型，用来修剪无趣的规则，从而筛选出用户真 正感兴趣的规则模式。并通过实验证明该兴趣度模型的有效性和实用性。 ( 2 ) 针对现有的经典关联分类算法的不足，提出一种基于d m i n e r 的关联分类算法， 该算法在产生分类关联规则时只需要扫描事务数据库一次，通过生成频繁闭项集，大大 减少分类关联规则的产生数量。此外，新算法结合了本文提出的兴趣度模型对规则修剪 进行改进，占用的存储空间相对减少。理论分析和测试实验证明了新算法在性能上的优 越性。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。 除文中已经注明引用的内容外，本论文不包含任何其他个入或集体已经发表或撰写过的 研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。本人完全 了解违反上述声明所引起的一切法律责任将由本人承担。 学位论文作者签名： 公诠 日期：如；9 t 7 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 研究背景与意义 随着互联网技术的不断应用，人们利用信息技术生产和搜索数据的能力大幅度提高， 各种大型数据库不断应用于各个领域。由于数据量呈指数增长，因此从大量的数据中快 速有效地获得有价值的信息资源在当今具有重大意义。目前的数据库系统虽然可以实现 高效的数据增删改、查询、统计等功能，却无法发现数据间存在的联系和规则，也无法 根据现有的数据预测未来的发展趋势。在这样的背景下，数据挖掘( d a t am i n i n g ) 技术 应运而生。数据挖掘的处理对象是大量的日常业务数据，目的是为了从这些数据中抽取 一些有价值的信息【l 】。目前，数据挖掘主要的研究领域集中在数据总结、分类、聚类、 关联规则等方面。 分类规则的挖掘和关联规则的挖掘是两种重要的数据挖掘技术。分类规则挖掘的目 标是建立一个精确且有效的分类器，然后预测那些未知类别的数据对象。关联规则的挖 掘就是找出数据库中满足最小支持度与最小置信度阈值的规则【2 】。由于关联规则挖掘的 算法、技术等研究比较成熟，因此将成熟的关联规则方法应用于分类将会得到一种解决 分类任务的新方法一基于关联规则的分类p j 。 在基于关联规则的分类算法中，除了建立精确的分类器，对产生的关联规则的质量 也是迫切要求的。对关联规则的度量通常使用支持度置信度框架，然而这一框架的弊端 也非常明显，即可能产生大量的无意义的关联规则。如何定义和确定好度量标准，识别 出用户感兴趣的并且有用的规则有着至关重要的作用。因此，对关联规则的兴趣度研究 的重要意义就显而易见了。 此外，目前关联分类算法已经产生了一些成熟算法，主要包括c b a ( c l a s s i f i c a t i o n b a s e do na s s o c i a t i o n ) t 3 1 、c m a r ( c l a s s i f i c a t i o nb a s e do nm u l t i p l ec l a s s a s s o c i a t i o nr u l e s ) 1 4 1 、 c p a r ( c l a s s i f i c a t i o nb a s e do np r e d i c t i v ea s s o c i a t i o nr u l e s ) 瞪】等，这些算法在分类的准确率 上比诸如c 4 5 【7 】等传统的分类算法有所提高。但这些算法均是基于一般频繁项产生大量 的候选规则，其庞大的规模不利于修剪、排序和存储。并且其中还存在一些冗余和效率 低的规则，降低了分类器的可理解性，继而影响到分类准确率。因此，针对以上描述的 关联分类挖掘算法的缺点，希望能提出更好、更有效的基于关联规则的分类算法是非常 具有现实意义的。 本文在通过研究分析已有的兴趣度模型，经典的关联分类算法及其已有的相关改进 措施的基础上，针对如何产生高质量的分类关联规则，以及如何使用有意义的分类关联 规则对未知数据集进行分类，提出了一种新的客观兴趣度模型及一种新的基于d m i n e r 西南交通大学硕士研究生学位论文第2 页 的关联分类算法，较好地改善了经典算法中存在的瓶颈问题，同时提高了分类精度。 1 2 国内外研究现状 1 2 1 国外研究现状 与传统的分类算法相比，由于关联分类算法具有分类预测准确度高的特点，因此诸 多国内外学者、研究人员对关联分类算法进行了深入的研究。其中一方面是对原有算法 的改进、优化以提高算法的分类精度；另一方面就是提出新的算法，拓宽算法的使用范 围。这方面的研究成果主要包括c b a t 3 1 、c m a r 4 1 、c p a r t 5 1 和a d t l 6 1 等。 b i n gl i u 掣3 】在1 9 9 8 年率先提出了基于分类关联规则的分类算法c b a ，该算法使用 类似于a p r i o r i 的算法( 称为类a p r i o r i 算法) 产生分类关联规则，实验结果与决策树算 法c 4 5 【7 1 进行比较，取得了较好的分类效果。在此之后，m e n n i s 等【8 】研究了c b a 算法 在空间时态数据挖掘中的应用。d a v y 等【9 】对c b a 算法进行改进，提出一个新的分类关 联规则后件选择框架，并提出一个暗示强度( i m p l i c i t l ys t r e n g t h ) 的指标来评价分类关 联规则质量，以提高分类预测准确度。 2 0 0 0 年，w a n g 等【6 】结合关联分类算法和决策树算法各自的长处，提出了关联决策 树( a s s o c i a t i o nd e c i s i o nt r e e ，a d t ) 方法。a d t 方法完全放弃支持度闽值，仅依据置 信度阈值从分类关联规则中选择分类规则，以此构建准确度驱动的决策树，采用自底向 上的闭包运算生成可信的关联规则。该算法的缺点是对噪声特别敏感，在实际应用中， 由于存在噪声，很难达到试验取得的准确率。 为了避免类a p r i o r i 算法产生频繁项集的一些缺陷，2 0 0 1 年，w l i 等【4 j 提出了一种 基于多关联规则的分类算法c m a r ，该算法使用改进的频繁模式增长法f p g r o w t h t l 0 j 算 法来发现满足最小支持度和最小置信度阈值的规则完全集，并根据置信度、相关度和数 据库覆盖率对规则剪枝，使用基于权重的多个强关联规则来确定新实例的类标签，实验 结果表明分类准确度优于c b a 算法。尽管该算法采用基于类f p g r o w t h 的算法挖掘分类 关联规则的效率较高，但不适合高维、大型的数据库。 b a r a l i s 等【1 2 】在2 0 0 2 年提出一种懒的( l a z y ) 分类关联规则剪枝方法，该方法通过 两遍分类迭代地去除产生错误分类的所有规则，实验结果表明该方法提高了分类精度。 2 0 0 3 年，y i n 等【5 j 提出一个基于f o i l ( f i r s to r d e ri n d u c t i v el e a r n e r ) 的分类规则产生算 法c p a r 。该算法的优点在于采用贪婪算法直接从训练数据集中挖掘分类关联规则，避 开了使用资源消耗大的关联规则算法，并采用基于信息熵的方法选择最优的5 个规则用 来分类一个实例。实验证明，c p a r 分类准确度与c m a r 算法相当。 w a n g 等【1 3 j 在2 0 0 5 年提出h a r m o n y 算法，该算法采用一种成为中心实例的方法发现 支持度最高的规则，并将所有的规则根据他们的结论分为k 个组，k 是整个项目集中类 属性的数目。在同一组中，h a r m o n y 采用c b a 方法选取规则。试验证明，h a r m o n y 方 西南交通大学硕士研究生学位论文第3 页 法比c p a r 拥有更高的准确度和更快的效率。 t h a b t a h 等【1 4 】在2 0 0 7 年提出r m r ( r a n k e dm u l t i p l i a b l er u l e ) 算法。r m r 算法在扫 描训练数掘集后，找出所有可能的规则，利用启发式修剪方法保证潜在规则中类别的顺 序。在重复学习时，r m r 从余下的未分类的对象中，找到满足最小支持度和最小置信度 阈值的规则，直到没有更频繁的项集出现。在每一次重复学习过程中找到的规则将被合 并形成一个多标签的分类器。最后，用测试数据集对多标签分类器进行评估。试验证明， r m r 算法比c b a 拥有更高的分类准确度。但是它的不足之处在于，如果数据记录较多， 记录标签将消耗大量空间，占用大量计算时间，且在属性较多时，生成的待评估规则较 多。 k e i v a nk i a r m e h r 等【l5 】在2 0 0 8 年提出c a r s v m 算法，该算法结合了c a r ( c l a s s a s s o c i a t i o nr u l e ) 和s v m ( s u p p o r tv e c t o rm a c h i n e ) 分类机的优点，来提高分类规则的准 确度。试验结果显示，基于规则的特征向量可以从训练数据集中提取高质量的分类关联 规则。但是，这种方法要求实验室数据库的数据必须完整，而且挖掘速度有待提高。 1 2 2 国内研究现状 目前，国内的关联分类算法的研究主要集中于算法的研究、关联分类挖掘的实际应 用等，并朝着追求高的分类精确度、有效的剪枝、减少冗余规则等方面发展，这类研究 一直比较活跃。 2 0 0 3 年，邹晓峰等f 1 6 】研究了模糊分类关联规则的挖掘算法。该算法采用模糊c 均值 ( f u z z yc m e a n s ，f c m ) 算法【1 7 】将记录在数量型属性上的取值划分成若干个用三角模糊 数表示的模糊集，挖掘出的模糊分类关联规则更符合人类的思维方式。然后采用遗传优 化算法，构造基于模糊分类关联规则的分类系统，通过比较每个类的判别函数决定分类 结果。该算法能适合含有大量数量型属性的大型数据库。通过实例分析，证明了该算法 具有较好的精度和解释性。 许孝元等【1 8 】提出了基于置信度和支持度加权的分类关联规则质量评价函数。该函数 显著优于基于灵敏度和选择性乘积的传统分类规则的质量评价函数，因此将它应用于基 于遗传算法的关联分类算法中取得了较好的效果。此外，许孝元还提出了利用原子型分 类关联规则构建分类器的思想，该算法分类准确度高，执行速度快，适合大规模的数据 库。 尹世群等【l9 】提出了一种基于粗糙集的分类关联规则挖掘算法。该算法结合了粗糙集 和分类关联规则挖掘，运用属性约简将关系数据库按属性值分为若干类；然后，约简冗 余属性及依赖属性；最后，根据数据约简后的目标关系表求取强类中的强特征决策关联 规则。试验表明，该算法对数据的分类是有效的，可得到较高的分类精度。 目前，关联分类算法的基本思想绝大多数是通过产生一般频繁项目集构造分类器。 西南交通大学硕士研究生学位论文第4 页 由于关联规则考虑了多属性之间的高置信度关联，避免了经典分类算法考虑单一属性的 缺点，使得关联分类算法取得了更好的分类效果。但当挖掘任务有长模式或支持度阈值 较低时，这些算法存在以下不足： 算法必须耗费大量时间处理规模巨大的候选项集； 算法必须多次扫描训练数据库，对候选项目集进行模式匹配，因此效率较低； 对于大型数据库，f p t r e e 较大，无法一次全部装入内存； 产生大量无意义的规则，消耗内存等等。 1 3 本论文研究内容及章节安排 1 。3 。1 本论文研究内容 本文在以上研究背景下，展开了对兴趣度模型和关联分类挖掘算法的研究。对已有 的兴趣度模型进行了研究和分析，并针对现有的兴趣度模型的缺陷，提出了一种新的客 观兴趣度模型，并证明它的有效性；此外，本文亦对现有的经典关联分类算法进行了分 析和研究，针对目前存在的效率瓶颈问题，提出一种基于d m i n e r 的关联分类算法，并 证明了该算法的有效性。主要工作包括以下一些内容： ( 1 ) 将深入研究关联分类经典算法c b a 、c m a r ，并对这两种算法进行分析和总 结。 ( 2 ) 介绍和分析已有的兴趣度模型，针对a r 兴趣度模型无法对正相关和负相关规 则判定等不足，结合可信度模型的优势，提出一种新的客观兴趣度模型l s a ，并证明它 的有效性。 ( 3 ) 针对经典关联分类算法中挖掘一般频繁项产生大量冗余的候选规则，不利于规 则的修剪、排序和存储的缺陷，提出一种基于d m i n e r 的关联分类算法，通过生成频繁 闭项集，大大减少分类关联规则的产生数量，并结合置信度、l s a 兴趣度模型以及数据 库覆盖策略对规则进行修剪，使算法挖掘到有意义的规则，最后用实验证明了算法的效 率和准确性。 1 3 2 本论文章节安排 全文分五章，各章节安排如下： 第1 章：绪论。阐明本文选题的研究背景及意义，并对题目相关领域的国内外研究 现状进行了综述，引出论文的研究内容和论文的结构安排。 第2 章：相关理论的概述。介绍关联规则挖掘及分类规则挖掘的基本概念，并分析 了具有代表性的挖掘频繁项集和频繁闭项集的算法，以及几种经典的分类算法，最后介 绍关联规则挖掘与分类规则挖掘的区别与联系。 第3 章：关联分类挖掘算法。介绍关联分类挖掘算法的相关概念和研究重点，对两 西南交通大学硕士研究生学位论文第5 页 种经典的关联分类算法进行研究，并分析了基于一般频繁项的关联分类算法的不足。 第4 章：一种新的客观兴趣度模型的引入及研究。从客观和主观两方面研究了各种 兴趣度模型的特点及研究现状，通过分析现有的兴趣度模型的不足，提出一种新的客观 兴趣度模型l s a ，最后通过实例和实验进行验证。 第5 章：一种新的基于d m i n e r 的关联分类算法。介绍了该算法产生的背景以及涉 及到的相关概念，详细论述了基于d m i n e r 提取分类关联规则的主要思想，并结合置信 度、兴趣度模型以及数据库覆盖策略来修剪规则，以及对分类器进行规则匹配的优化， 最后用实验验证了新算法的准确性和效率。 最后是本论文的结论和展望。 西南交通大学硕士研究生学位论文第6 页 第2 章相关理论概述 关联规则挖掘的目的是发现数据库中大量项集之间的关联关系，它是数据挖掘中一 个重要的研究方向。分类规则挖掘也是数据挖掘中应用领域较为广泛的重要技术之一。 所谓分类，就是把给定的数据划分到一定的类别中。本章首先对关联规则挖掘的过程以 及频繁项集算法和频繁闭项集算法进行分析、总结，然后阐述了分类规则挖掘算法的内 容、步骤以及几种经典的分类算法，最后讨论了关联规则挖掘与分类规则挖掘的区别与 联系。 2 1 关联规则挖掘概述 2 1 1 基本概念和性质 关联规则是一组简单、实用的分析规则，它根据寻找到的存在于大量数据集中的关 联性或相关性，从而描述了一个事务中某些属性同时出现的规律和模式。 关联规则的基本模型如下： 设卢 礼i 2 ，i m ) 是所有项目的集合，数据库d 为全体事务的集合，事务丁是一个 项目子集合，使得t c _ l o 每个事务有一个标识符 r i d 。设彳是一个由项目构成的集合， 称其为项集。事务r 包含项集彳，当且仅当彳丁。关联规则是形如x 一】，的蕴含式，其 中x c i , y c i ，并且x n 净o 。x 称为前项项集，】，称为后项项集。 定义2 - 1 ：包含x 的事务数目在数据库d 中所占的百分比称为x 的支持度，记为 s u p p o r t ( x ) 。 s u p p 。r t ( x ) ：c 0 1 u n r t ( x ) 卑1 0 0 i u i 式中 c o u n t ( x ) 表示数据库d 中包含x 事务的数目 定义2 - 2 ：支持度大于或等于给定最小支持度阈值的项集称为频繁项集。本文将最 小支持度阈值记为m i ns u p 。规则应该满足的最低置信度定义为最小置信度阈值，用 m i nc o n f 表示。前者描述了关联规则的最低重要程度，后者规定了关联规则必须满足的 最低可靠性。 定义2 - 3 ：在数据库d 中，包含项集x u 】，事务的数目所占的百分比称为规则x _ 】， 的支持度，记为s u p p o r t ( xj y ) 。 s u p p o r t ( x y ) ：p ( xu 】，) ：c o u n t 两( x wy ) 木1 0 0 l i 式中 c o u n t ( xuj ，) 一数据库d 中包含u 】，事务的数目 定义2 - 4 ：在数据库d 支持的事务里，包含y 事务的数目所占的百分比称为规则 西南交通大学硕士研究生学位论文第7 页 彳专】，的置信度，记为c o n f i d e n c e ( x n c o n f i d e n c e ( x y ) = p ( y ix ) = s u p p o r t ( x u y ) 一c o u n t ( x u 】，1 s u p p o r t ( x )c o u n t ( x ) 1 0 0 定义2 - 5 ：满足给定的最小支持度和最小置信度阈值的规则称为强规则。关联挖掘 的目的就是从数据集中发现所有的强规则。 定义2 - 6 如果项集x 满足：( 1 ) s u p ( x ) m i ns u p ；( 2 ) 不存在y c _ i ，使得 x cy n s u p ( x ) = s u p ( y ) ，则称项集x 为闭频繁项集，或称为频繁闭项集。 由定义2 6 可知，所谓频繁闭项集就是支持度大于其任意超集的项集。 性质2 - 1 ：将从数据库d 中挖掘出来的频繁项集、频繁闭项集的集合依次记为f i d 、 c f i o ，那么有：c f i d c _ f i d 。 例如，假设一个数据库仅包含2 个交易， ( 口1 ，口2 ，口1 0 0 ) ，( 口1 ，口2 ，a s o ) ，给定最小 支持度计数为l ，最小置信度为5 0 ，按照传统方法，将产生f o o 1 0 3 0 个频繁项集。然 而，采用闭项集方法，在该数据库上仅产生2 个频繁闭项集： ( 口l ，g 2 , - - , a l o o ) ，( a l ，口2 ，口5 0 ) ) 和一个关联规则“( a 1 , a 2 ，口l o o ) 一( 口1 ，口2 ，口5 0 ) ”，其他关联规则均可以由此得到。显然 有c f i d c _ f i d 。 2 1 2 关联规则的挖掘过程 关联规则挖掘是数据挖掘中最常用的方法之一。关联规则挖掘就是在给定的数据库 d 中挖掘出满足用户设定的最小支持度和最小置信度阈值的强关联规则。整个挖掘过程 可以分解为以下两个步骤【2 l j ： ( 1 ) 找出数据库d 中所有支持度大于等于用户设定的最小支持度的项集，即生成 频繁项集。 ( 2 ) 利用频繁项集生成所需要的关联规则，再根据用户设定的最小置信度进行修剪， 最后得到强关联规则。 由于现实数据库的规模通常是非常庞大的，为了在产生候选集并统计其支持度时减 少消耗的时间，因此，寻找产生频繁项集的高效算法成为关联规则挖掘算法研究的关键。 对此，p a s q u i e r 等【2 2 1 提出了使用频繁闭项集代替频繁项集挖掘关联规则的思想。由 于频繁闭项集产生的数量远远小于频繁项集产生的数量，并且保存了频繁项集的完整信 息。因此，通过频繁闭项集产生的关联规则也能得到频繁项集产生的所有规则。这样， 不但不会丢失信息，还能大大地提高挖掘效率。 2 1 3 频繁项集算法概述 自a g r a w a l 等【1 l 】于1 9 9 4 年提出挖掘频繁模式的a p r i o r i 算法以来，国内外许多研究 人员取得了大量的研究成果。这些研究成果大致可以分为产生候选频繁集的算法和不产 西南交通大学硕士研究生学位论文第8 页 生候选频繁集的算法两类。当前，最具影响的经典频繁项集算法主要是a p r i o r i ! l 和 f p g r o 砒h 【l o 】。 1 a p r i o r i 算法 a p r i o r i 算法是挖掘产生布尔关联规则频繁项集的经典算法。该算法基于两阶段生 成频繁项集的思想，并采用逐层搜索的迭代方法，通过频繁如项集来挖掘频繁( 抖1 ) 项 集，其中在发现每个频繁缸项集的过程中需要对整个事务数据库扫描一遍。 为了提高频繁项集逐层产生的效率，a p r i o r i 算法利用了著名的a p r i o r i 性质以压 缩搜索的空间。产生频繁项集主要分为连接和剪枝两步组成。连接就是通过三柚与自己 连接产生候选肛项目集的集合，找到厶( “频繁项集的集合) 。该候选项目集的集合记作 g ；剪枝就是对g 进行剪枝，从g 中删除所有( k - 1 ) 子集不全包含在k 1 中的项集， 得到了舡频繁项集的集合七1 2 3 】。 a p r i o r i 算法作为经典的关联规则算法，在处理稀疏数据时表现出良好的性能和可伸 缩性。但是，在处理稠密的高相关性的数据时，它可能产生大量的候选项目集，并且由 于反复扫描事务数据库，导致算法效率降低。除此之外，由于该算法产生太多冗余规则， 导致用户很难区分有用的规则。因此，国内外众多学者通过大量的研究工作，相继提出 了一些优化的方法。例如引入了散列2 4 1 、事务压缩闭、划分等相关技术，在一定程度 上提高了a p r i o r i 算法的效率。 2 f p g r o w t h 算法 针对a p r i o r i 算法以及a p r i o r i 的改进算法需要产生大量候选项集的缺陷，h a n 等在 2 0 0 0 年提出一种基于f p t r e e 的频繁模式增长算法，简称f p g r o w t h ( f r e q u e n tp a t t e r n g r o w t h ) 算法【l0 1 。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 算法的缺陷，在执行效率上较 a p r i o r i 算法有明显提高。 f p g r o w t h 算法的优势在于利用f p t r e e 结构来压缩存储数据库中的每条事务，在频 繁模式的挖掘过程中仅需在f p t r e e 中遍历，从而减少了扫描数据库的时间消耗。此外， 由于该算法不需要维护一个候选模式的集合，因此也降低了算法的空间复杂度。但 f p g r o 蚍h 算法在挖掘过程中需要频繁地构造和释放条件频繁模式树，对计算机的内存 有颇高的要求。 鉴于a 研耐算法和f p g r o w t h 算法各自的缺陷，后面提到的挖掘频繁闭项集算法是 解决这类问题的有效途径之一。 2 1 4 频繁闭项集算法概述 针对a p r i o r i 算法产生大量频繁项集这一问题，p a s q u i e r 等提出了频繁闭合项集的概 西南交通大学硕士研究生学位论文第9 页 念 2 2 l 。它唯一地决定了所有频繁模式的准确支持度，其数量介于最大频繁项集与频繁项 集之间，同时记录了所有频繁项集的支持度。目前，最具影响的频繁闭项集算法有： a c l o s e t 2 2 1 、2 7 1 、m a f i a l 2 、c h a r m t 2 9 1 、d c i c l o s e d l ac l o s e tc l o s e t t a t 2 8d c i 1 5 0 l 等。这些算法都是 “j 、 川j 、j 、删j 、 等。这些算法都是 在已有的频繁项集挖掘算法的基础上加入剪枝和闭合检测策略而得到的。其中，被广泛 应用的剪枝策略有以下两种。 引理2 1 【2 1 】项合并：如果包含频繁项集x 的每个事务都包含项集】，但不包含y 的 任何真超集，则xu 】，形成一个闭频繁项集，并且不必再搜索包含x 但不包含】，的任何 项集。 引理2 2 t 2 l 】子项集剪枝：如果频繁项集x 是一个已经发现的闭频繁项集】，的真子集， 并且s u p p o r t f n，则x和x在集合枚举树中的所有后代都不可能pount(30=supporc o , l i l t ( 是闭频繁项集，因此可以剪枝。 由于挖掘过程本身不能确保所产生的每个频繁项集都是闭合的，因此，当一个新的 频繁项集导出后，必须进行两种闭包检查i 2 l 】：( 1 ) 超集检查，检查这个新的频繁项集是 否是某个具有相同支持度的已经发现的闭项集的超集；( 2 ) 子集检查，检查新发现的项 集是否是某个具有相同支持度的已经发现的闭项集的子集。 由于频繁闭项集是一个具有最小冗余的精确结果集，通过频繁闭项集可以得到所有 的频繁项集，因此，对于挖掘频繁闭项集的研究具有重要的意义。p a s q u i e r 等1 2 2 j 提出的 a c l o s e 算法以a p r i o r i 为基础，采用自底向上、宽度优先的搜索策略，通过构造“生 成子”集合，逐层求出所有的频繁闭项集。虽然它在剪裁后，减小了搜索范围，但还是 没有解决模式匹配时高c p u 开销和重复扫描数据库的高i o 开销。p e i 等1 27 j 提出的 c l o s e t 算法以f p g r o w t h 为基础，采用f p t r e e 来表示模式支持集，通过深度优先搜 索来挖掘频繁闭项集。但是该算法仍然具有f p g r o w t h 算法的缺陷，并且在检查局部频 繁闭项集的全局闭合性和频繁性的过程中开销较大。z a k i 等1 2 9 j 提出的c h a r m 算法是现 有算法中性能最好的，它采用垂直格式的事务标识集来表示模式支持集，对项目集与事 务标识集进行双向搜索，剪裁效率较高。其困难在于，事务标识集无论采用t i d s e t 还是 d i 凰e t 表示，存储开销都非常大，并且投影操作效率不高，对于密集型或存在特别长模 式的数据集，c h a i w 效率与可伸缩性较差。 根据以上分析，频繁闭项集算法大致可以分为两类，一类是基于a p r i o r i 算法思想的 频繁闭项集挖掘算法，它们具有和a p r i o r i 算法同样的不足；另一类是不产生候选集而直 接生成频繁闭项集的挖掘算法，它们首先构造一棵树，然后在树上进行相关的操作来发 现数据库中的频繁闭项集。而这类算法有一个明显不足，就是当项目比较平衡或支持度 阈值较低的时候，树结构将无法一次性全部装入内存中。 西南交通大学硕士研究生学位论文第1 0 页 2 2 分类规则挖掘概述 2 2 1 分类算法的概述 分类是一种重要的数据挖掘技术。分类的目的就是根据数据集的特点构造一个分类 模型或分类器，该分类器能将未知类别的样本数据映射到给定类别中的某一个。构造分 类器的过程一般分为两个阶段：训练和测试。在构造分类器之前，将数据集随机地分为 训练数据集和测试数据集。在训练阶段，分析训练数据集中的数据来构造分类模型；在 测试阶段，采用测试数据集中的数据来评估模型的分类准确率【3 。 分类可以描述为：给定一个训练数据集兀丁中的元素记录由若干个属性组成。在 属性中有且仅有一个属性作为类别属性。属性集合用条件属性胙趣，疋) 表示，其 中x 对应条件属性，具有不同的值域。用c 表示类别属性，c _ c l ，q ，靠 ，即数据集 有k 个不同的类别。那么，分类就是确定一个从条件属性集x n 类别属性c 的映射函数 凰凡的一c ，分类的目的就是采用某种方法将该隐含的函数日表示出来【3 2 】。 2 2 2 分类算法的步骤 数据分类操作通常有以下两个步骤【2 l 】： 第一步，创建分类模型。给定一个训练数据集，选择一个合适的分类算法。并利用 该分类算法对训练数据集进行分析，然后构造出描述该训练数据集的映射函数h ： 脚一c 。该映射可以用分类规则、决策树或者数学方程的形式来提供。 第二步，使用模型分类。首先，用一定的方法估计分类模型的准确率。在这里，可 以通过剪枝或者调整以提高分类模型的准确率。再用达到一定准确率的分类模型对类型 未知的测试数据集进行分类。 由于训练集的类别是确定的，而类别未知的测试集是基于训练