数据挖掘方法——关联规则(自己整理)

Copyright©2009,MANAGEMENTSCIENCEASSOCIATES,INC.1一、关联规则概念二、关联规则应用领域三、关联规则挖掘的过程四、关联规则的分类五、关联规则挖掘的相关算法六、关联规则的优缺点Copyright©2009,MANAGEMENTSCIENCEASSOCIATES,INC.2一、关联规则概念关联分析（Associationanalysis）：就是从给定的数据集发现频繁出现的项集模式知识（又称为关联规则，associationrules）。两个或两个以上变量的取值之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、可被发现的知识。关联分为简单关联、时序关联和因果关联。关联分析的目的：找出数据库中隐藏的关联网。一般用Support(支持度)和Confidence(可信度)两个阀值来度量关联规则的相关性，引入lift(提高度或兴趣度）、相关性等参数，使得所挖掘的规则更符合需求。Copyright©2009,MANAGEMENTSCIENCEASSOCIATES,INC.3一、关联规则概念规则就是一个条件和一个结果的和：Ifconditionthenresult。1.Support（支持度）：是一个元组在整个数据库中出现的概率。Support=P(conditionandresult)。(1)如：ifAthenB。则它的支持度Support=P(AandB)2.Confidence（可信度）：它是针对规则而言的。Confidence=p(conditionandresult)/p(condition)。(2)如：IfBandCthenA。则它的可信度Confidence=p(BandCandA)/p(BandC)。把满足最小支持度阈值和最小置信度阈值的规则成为强规则。项的集合称为项集（itemset），包含K个项集称为K－项集，如果项集满足最小支持度，则称它为频繁项集。3.Lift（提高率或兴趣度）:使得所挖掘的规则更符合需求。Lift=p(conditionandresult)/(p(condition)*p(result))。(3)当Lift大于1的时候，这条规则就是比较好的；当Lift小于1的时候，这条规则就是没有很大意义的。Lift越大，规则的实际意义就越好。Copyright©2009,MANAGEMENTSCIENCEASSOCIATES,INC.4二、关联规则应用领域目前，关联技术的主要应用领域是商业，它的主要挖掘对象是事务数据库。利用关联技术从交易数据库发现规则的过程称为购物篮分析（MarketBasketAnalysis）。通过对商业数据库中的海量销售记录进行分析，提取出反映顾客购物习惯和偏好的有用规则（或知识），可以决定商品的降价、摆放以及设计优惠券等。当然也可以把得到的信息应用到促销和广告中，例如，关联规则中所有后项为“DietCoke”的规则可能会给商店提供出信息：什么会促使DietCoke大量售出。另外，关联规则也可以服务于Cross-sale。服务业的激烈竞争使得公司留住老顾客和吸引新顾客一样重要。通过分析老顾客的购买记录，了解他们的产品消费偏好，给他们提供其它产品的优惠及服务，这样不但能留住他们还可以使他们逐渐熟悉另外的产品，公司从而以尽快的速度获得利润。Cross-sale就是试图让一种产品的固定购买客户购买另一种产品。但大公司的顾客购买数据库很大，人工分析是很难的，关联规则挖掘技术可以结合专家从大型数据库中发现有用知识，来帮助领域专家做出决策。关联技术不但在商业分析中得到了广泛的应用，在其它领域也得到了应用，包括工程、医疗保健、金融证券分析、电信和保险业的错误校验等。Copyright©2009,MANAGEMENTSCIENCEASSOCIATES,INC.5三、关联规则挖掘的过程关联规则的挖掘可以发现大量数据中数据项集之间有趣的关联。而核心就是识别或发现所有频繁项目集。关联规则的挖掘是一个两步的过程：1、找出所有频繁项集(FrequentItemsets);2、由频繁项集产生强关联规则(AssociationRules)，根据定义，这些规则必须满足最小支持度和最小置信度。关联规则挖掘的第一阶段必须从原始资料集合中，找出所有高频项目组(LargeItemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一水平。一项目组出现的频率称为支持度(Support)，以一个包含A与B两个项目的2-itemset为例，我们可以经由公式(1)求得包含{A,B}项目组的支持度，若支持度大于等于所设定的最小支持度(MinimumSupport)门槛值时，则{A,B}称为高频项目组。一个满足最小支持度的k-itemset，则称为高频k-项目组(Frequentk-itemset)，一般表示为Largek或Frequentk。算法并从Largek的项目组中再产生Largek+1，直到无法再找到更长的高频项目组为止。Copyright©2009,MANAGEMENTSCIENCEASSOCIATES,INC.6三、关联规则挖掘的过程关联规则挖掘的第二阶段是要产生关联规则(AssociationRules)。从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小信赖度(MinimumConfidence)的条件门槛下，若一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。例如：经由高频k-项目组{A,B}所产生的规则AB，其信赖度可经由公式(2)求得，若信赖度大于等于最小信赖度，则称AB为关联规则。注：关联规则挖掘通常比较适用与记录中的指标取离散值的情况。如果原始数据库中的指标值是取连续的数据，则在关联规则挖掘之前应该进行适当的数据离散化（实际上就是将某个区间的值对应于某个值），数据的离散化是数据挖掘前的重要环节，离散化的过程是否合理将直接影响关联规则的挖掘结果。Copyright©2009,MANAGEMENTSCIENCEASSOCIATES,INC.7四、关联规则的分类按照不同情况，关联规则可以进行分类如下：1.基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。例如：性别=“女”=职业=“秘书”，是布尔型关联规则；性别=“女”=avg（收入）=2300，涉及的收入是数值类型，所以是一个数值型关联规则。2.基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例如：IBM台式机=Sony打印机，是一个细节数据上的单层关联规则；台式机=Sony打印机，是一个较高层次和细节层次之间的多层关联规则。3.基于规则中涉及到的数据的维数，关联规则可以分为单维关联规则和多维关联规则。在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。例如：啤酒=尿布，这条规则只涉及到用户的购买的物品；性别=“女”=职业=“秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。Copyright©2009,MANAGEMENTSCIENCEASSOCIATES,INC.8五、关联规则挖掘的相关算法1.Apriori算法：使用候选项集找频繁项集Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。Apriori算法可以产生相对较小的候选项目集，扫描数据库的次数由最大频繁项目集的项目数决定。因此，该算法适合于最大频繁项目集相对较小的数据集中的关联规则挖掘问题。Apriori算法的两大缺点:1.可能产生大量的候选集；2.可能需要重复扫描数据库。Copyright©2009,MANAGEMENTSCIENCEASSOCIATES,INC.9五、关联规则挖掘的相关算法2.FP-growth算法针对Apriori算法的固有缺陷，FP-growth算法是一种不产生候选挖掘频繁项集的方法，弥补了Apriori算法中的固有缺陷，是大型数据库挖掘频繁项集的一个有效的算法。FP-growth算法采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有巨大的提高。小结：Apriori算法可以分为频繁项集的生成和关联规则的生成两大步骤；FP-Growth算法可以分成FP-Tree的生成，频繁项集的生成和关联规则的生成3大步骤。Copyright©2009,MANAGEMENTSCIENCEASSOCIATES,INC.10五、关联规则挖掘的相关算法3.多层关联规则挖掘算法对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强关联规则。当我们引入概念层次后，就可以在较高的层次上进行挖掘。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在多个层次上进行挖掘的功能。多层关联规则的分类：根据规则中涉及到的层次，多层关联规则可以分为同层关联规则和层间关联规则。多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框架。不过，在支持度设置的问题上有一些要考虑的东西。4.多维关联规则挖掘算法对于多维数据库而言，除维内的关联规则外，还有一类多维的关联规则。例如：年龄（X，“20…30”）职业（X，“学生”）==购买（X，“笔记本电脑”）在这里我们就涉及到三个维上的数据：年龄、职业、购买。根据是否允许同一个维重复出现，可以又细分为维间的关联规则（不允许维重复出现）和混合维关联规则（允许维在规则的左右同时出现）。如：年龄（X，“20…30”）购买（X，“笔记本电脑”）==购买（X，“打印机”）这个规则就是混合维关联规则。在挖掘维间关联规则和混合维关联规则的时候，还要考虑不同的字段种类：种类型和数值型。对于种类型的字段，原先的算法都可以处理。而对于数值型的字段，需要进行一定的处理之后才可以进行。Copyright©2009,MANAGEMENTSCIENCEASSOCIATES,INC.11六、关联规则的优缺点优点：它可以产生清晰有用的结果。它支持间接数据挖掘。可以处理变长的数据。它的计算的消耗量是可以预见的。缺点：当问题变大时，计算量增长得厉害。难以决定正确的数据。容易忽略稀有的数据。