略论关联规则挖掘算法综述

《略论关联规则挖掘算法综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、略论关联规则挖掘算法综述本文先容了关联规则的基本概念和分类方法，列举了一些关联规则挖掘算法并扼要分析了典型算法，展看了关联规则挖掘的未来探究方向。1引言关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛探究。关联规则挖掘的一个典型例子是购物篮分析。关联规则探究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存布置以及根据购买模式对用户进行分类。Agra}是项集，其中ik(k=1,2,…,m)可以是购物篮中的物品，也可以

2、是保险公司的顾客。设任务相关的数据D是事务集，其中每个事务T是项集，使得TÍI。设A是一个项集，且AÍT。关联规则是如下形式的逻辑蕴涵：AÞB，AÌI,AÌI，且A∩B=F。关联规则具有如下两个重要的属性：支持度:P(A∪B)，即A和B这两个项集在事务集D中同时出现的概率。置信度:P(B｜A)，即在出现项集A的事务集D中，项集B也同时出现的概率。同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。给定一个事务集D，挖掘关联规则新题目就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联

3、规则，也就是产生强规则的新题目。3关联规则种类1)基于规则中处理的变量的种别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。数值型关联规则可以和***关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。2)基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的。在多层关联规则中，对数据的多层性已经进行了充分的考虑。3)基于规则中涉及到的数据的维数，

4、关联规则可以分为单维的和***的。在单维关联规则中，我们只涉及到数据的一个维，如用户购买的物品在***关联规则中，要处理的数据将会涉及多个维。4算法综述4.1经典的频集算法Agrawal即是1994年提出了一个挖掘顾客交易数据库中项集间的关联规则的重要方法[AS94a,AS94b]，其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。所有支持度大于最小支持度的项集称为频繁项集，简称频集。4.1.1算法的基本思想首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小

5、可信度。挖掘关联规则的总体性能由第一步决定，第二步相对轻易实现。4.1.2Apriori核心算法分析为了天生所有频集，使用了递推的方法。其核心思想扼要描述如下：(1)L1={large1-itemsets};(2)for(k=2;Lk-1¹F;k)dobegin(3)Ck=apriori-gen(Lk-1);//新的候选集(4)foralltransactionstÎDdobegin(5)Ct=subset(Ck,t);//事务t中包含的候选集(6)forallcandidatescÎCtdo(7)c.count;(8)end(9)Lk

6、={cÎCk

7、c.count³minsup}(10)end(11)Ansannila等引进了修剪技术来减小候选集Ck的大小[MTV94]，由此可以明显地改进天生所有频集算法的性能。算法中引进的修剪策略基于这样一个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，假如Ck中某个候选项集有一个(k-1)-子集不属于Lk-1，则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候选集的支持度的代价。4.2改进的频集算法4.2.1散列该算法由Park等在1995年提出[PCY95b]。通过实验发现寻找频繁项集的主要计算是在天生频繁2项集L

8、2上，Park就是利用这个性质引进散列技术来改进产生频繁2项集的方法。其基本思想是：当扫描数据库中每个事务，由C1中的候选1项集产生频繁1项集L1时，对每个事务产生所有的2项集，将它们散列到散列表结构的不同桶中，并增加对应的桶计数，在散列表中对应的桶计数低于支持度阈值的2项集不可能是频繁2项集，可从候选2项集中删除，这样就可大大压缩了要考虑的2项集。4.2.2事务压缩Agraannila等先考虑了这一点[MTV94]，他们以为采样是发现规则的一个有效途径。随后又由Toivonen进一步发展了这个思想[Toi96]，先使用从数据库中抽取出来