数据挖掘算法之-关联规则挖掘（AssociationRule）
⼀、关联规则的定义和属性
考察⼀些涉及许多物品的事务：事务1 中出现了物品甲，事务2 中出现了物品⼄，事务3 中则同时出现了物品甲和⼄。那么，物品甲和⼄在事务中的出现相互之间是否有规律可循呢？在数据库的知识发现中，关联规则就是描述这种在⼀个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量化的数字描述物品甲的出现对物品⼄的出现有多⼤的影响。
现实中，这样的例⼦很多。例如超级市场利⽤前端收款机收集存储了⼤量的售货数据，这些数据是⼀条条的购买事务记录，每条记录存储了事务处理时间，顾客购买的物品、物品的数量及⾦额等。这些数据中常常隐含形式如下的关联规则：在购买铁锤的顾客当中，有70 ％的⼈同时购买了铁钉。这些关联规则很有价值，商场管理⼈员可以根据这些关联规则更好地规划商场，如把铁锤和铁钉这样的商品摆放在⼀起，能够促进销售。
有些数据不像售货数据那样很容易就能看出⼀个事务是许多物品的集合，但稍微转换⼀下思考⾓度，仍然可以像售货数据⼀样处理。⽐如⼈寿保险，⼀份保单就是⼀个事务。保险公司在接受保险前，往往需要记录投保⼈详尽的信息，有时还要到医院做⾝体检查。保单上记录有投保⼈的年龄、性别、健康状况、⼯作单位、⼯作地址、⼯资⽔平等。这些投保⼈的个⼈信息就可以看作事务中的物品。通过分析这
些数据，可以得到类似以下这样的关联规则：年龄在40 岁以上，⼯作在A 区的投保⼈当中，有45 ％的⼈曾经向保险公司索赔过。在这条规则中，“年龄在40 岁以上”是物品甲，“⼯作在A 区”是物品⼄，“向保险公司索赔过”则是物品丙。可以看出来，A 区可能污染⽐较严重，环境⽐较差，导致⼯作在该区的⼈健康状况不好，索赔率也相对⽐较⾼。
设R= { I1,I2 ……Im} 是⼀组物品集，W 是⼀组事务集。W 中的每个事务T 是⼀组物品，T R。假设有⼀个物品集A，⼀个事务T，如果A T，则称事务T ⽀持物品集A。关联规则是如下形式的⼀种蕴含：A→B，其中A、B 是两组物品，A I，B I，且A ∩B= 。⼀般⽤四个参数来描述⼀个关联规则的属性：
1 ．可信度（Confidence）
设W 中⽀持物品集A 的事务中，有c ％的事务同时也⽀持物品集B，c ％称为关联规则A→B 的可信度。简单地说，可信度就是指在出现了物品集A 的事务T 中，物品集B 也同时出现的概率有多⼤。如上⾯所举的铁锤和铁钉的例⼦，该关联规则的可信度就回答了这样⼀个问题：如果⼀个顾客购买了铁锤，那么他也购买铁钉的可能性有多⼤呢？在上述例⼦中，购买铁锤的顾客中有70 ％的⼈购买了铁钉, 所以可信度是70 ％。
2 ．⽀持度(Support)
发成语接龙
排骨玉米汤的做法设W 中有s ％的事务同时⽀持物品集A 和B，s ％称为关联规则A→B 的⽀持度。⽀持度描述了A 和B 这两个物品集的并集C 在所有的事务中出现的概率有多⼤。如果某天共有1000 个顾客到商场购买物品，其中有100 个顾客同时购买了铁锤和铁钉，那么上述的关联规则的⽀持度就是10 ％。
3 ．期望可信度(Expected confidence)
设W 中有e ％的事务⽀持物品集B，e ％称为关联规则A→B 的期望可信度度。期望可信度描述了在没有任何条件影响时，物品集B 在所有事务中出现的概率有多⼤。如果某天共有1000 个顾客到商场购买物品，其中有200 个顾客购买了铁钉，则上述的关联规则的期望可信度就是20 ％。
4 ．作⽤度(Lift)
作⽤度是可信度与期望可信度的⽐值。作⽤度描述物品集A 的出现对物品集B 的出现有多⼤的影响。因为物品集B 在所有事务中出现的概率是期望可信度；⽽物品集B 在有物品集A 出现的事务中出现的概率是可信度，通过可信度对期望可信度的⽐值反映了在加⼊“物品集A 出现”的这个条件后，物品集B 的出现概率发⽣了多⼤的变化。在上例中作⽤度就是70 ％/20 ％=3.5。
可信度是对关联规则的准确度的衡量，⽀持度是对关联规则重要性的衡量。⽀持度说明了这条规则在所有事务中有多⼤的代表性，显然⽀持度越⼤，关联规则越重要。有些关联规则可信度虽然很⾼，但⽀持度却很低，说明该关联规则实⽤的机会很⼩，因此也不重要。
期望可信度描述了在没有物品集A 的作⽤下，物品集B 本⾝的⽀持度；作⽤度描述了物品集A 对物品集B 的影响⼒的⼤⼩。作⽤度越⼤，说明物品集B 受物品集A 的影响越⼤。⼀般情况，有⽤的关联规则的作⽤度都应该⼤于1，只有关联规则的可信度⼤于期望可信度，才说明A 的出现对B 的出现有促进作⽤，也说明了它们之间某种程度的相关性，如果作⽤度不⼤于1，则此关联规则也就没有意义了。
⼆、关联规则的挖掘学习永无止境
在关联规则的四个属性中，⽀持度和可信度能够⽐较直接形容关联规则的性质。从关联规则定义可以看出，任意给出事务中的两个物品集，它们之间都存在关联规则，只不过属性值有所不同。如果不考虑关联规则的⽀持度和可信度，那么在事务数据库中可以发现⽆穷多的关联规则。事实上，⼈们⼀般只对满⾜⼀定的⽀持度和可信度的关联规则感兴趣。因此，为了发现有意义的关联规则，需要给定两个阈值：最⼩⽀持度和最⼩可信度，前者规定了关联规则必须满⾜的最⼩⽀持度；后者规定了关联规则必须满⾜的最⼩可信度。⼀般称满⾜⼀定要求的（如较⼤的⽀持度和可信度）的规则为强规则（Strong rules）。
在关联规则的挖掘中要注意以下⼏点：
1、充分理解数据。
2、⽬标明确。
机不可失3、数据准备⼯作要做好。能否做好数据准备⼜取决于前两点。数据准备将直接影响到问题的复杂度及⽬标的实现。
4、选取恰当的最⼩⽀持度和最⼩可信度。这依赖于⽤户对⽬标的估计，如果取值过⼩，那么会发现⼤量⽆⽤的规则，不但影响执⾏效率、浪费系统资源，⽽且可能把⽬标埋没；如果取值过⼤，则⼜有可能找不到规则，与知识失之交臂。
5、很好地理解关联规则。数据挖掘⼯具能够发现满⾜条件的关联规则，但它不能判定关联规则的实际意义。对关联规则的理解需要熟悉业务背景，丰富的业务经验对数据有⾜够的理解。在发现的关联规则中，可能有两个主观上认为没有多⼤关系的物品，它们的关联规则⽀持度和可信度却很⾼，需要根据业务知识、经验，从各个⾓度判断这是⼀个偶然现象或有其内在的合理性；反之，可能有主观上认为关系密切的物品，结果却显⽰它们之间相关性不强。只有很好的理解关联规则，才能去其糟粕，取其精华，充分发挥关联规则的价值。
发现关联规则要经过以下三个步骤：
1、连接数据，作数据准备；
2、给定最⼩⽀持度和最⼩可信度，利⽤数据挖掘⼯具提供的算法发现关联规则；
3、可视化显⽰、理解、评估关联规则。
星期六早晨三、关联规则挖掘的过程
关联规则挖掘过程主要包含两个阶段：紫质症
第⼀阶段必须先从资料集合中找出所有的⾼频项⽬组(Frequent Itemts)，
第⼆阶段再由这些⾼频项⽬组中产⽣关联规则(Association Rules)。
关联规则挖掘的第⼀阶段必须从原始资料集合中，找出所有⾼频项⽬组(Large Itemts)。⾼频的意思是指某⼀项⽬组出现的频率相对于所有记录⽽⾔，必须达到某⼀⽔平。⼀项⽬组出现的频率称为⽀持度(Support)，以⼀个包含A与B两个项⽬的2-itemt为例，我们可以经由公式(1)求得包含{A,B}项⽬组的⽀持度，若⽀持度⼤于等于所设定的最⼩⽀持度 (Minimum Support)门槛值时，则{A,B}称为⾼频项⽬组。⼀个满⾜最⼩⽀持度的k-itemt，则称为⾼频k-项⽬组(Frequent k-itemt)，⼀般表⽰为Large k或Frequent k。算法并从Large k的项⽬组中再产⽣Large k+1，直到⽆法再找到更长的⾼频项⽬组为⽌。
关联规则挖掘的第⼆阶段是要产⽣关联规则(Association Rules)。从⾼频项⽬组产⽣关联规则，是利⽤前⼀步骤的⾼频k-项⽬组来产⽣规则，在最⼩信赖度(Minimum Confidence)的条件门槛下，若⼀规
则所求得的信赖度满⾜最⼩信赖度，称此规则为关联规则。
从上⾯的介绍还可以看出，关联规则挖掘通常⽐较适⽤与记录中的指标取离散值的情况。如果原始数据库中的指标值是取连续的数据，则在关联规则挖掘之前应该进⾏适当的数据离散化（实际上就是将某个区间的值对应于某个值），数据的离散化是数据挖掘前的重要环节，离散化的过程是否合理将直接影响关联规则的挖掘结果。
四、关联规则的分类
按照不同情况，关联规则可以进⾏分类如下：
1.基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。
布尔型关联规则处理的值都是离散的、种类化的，它显⽰了这些变量之间的关系；⽽数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进⾏处理，将其进⾏动态的分割，或者直接对原始的数据进⾏处理，当然数值型关联规则中也可以包含种类变量。例如：性别=“⼥”=>职业=“秘书” ，是布尔型关联规则；性别=“⼥”=>avg（收⼊）=2300，涉及的收⼊是数值类型，所以是⼀个数值型关联规则。
2.基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。
在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；⽽在多层的关联规则中，对数据的多层性已经进⾏了充分的考虑。例如：IBM台式机=>Sony打印机，是⼀个细节数据上的单层关联规则；台式机=>Sony打印机，是⼀个较⾼层次和细节层次之间的多层关联规则。
3.基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。
在单维的关联规则中，我们只涉及到数据的⼀个维，如⽤户购买的物品；⽽在多维的关联规则中，要处理的数据将会涉及多个维。换成另⼀句话，单维关联规则是处理单个属性中的⼀些关系；多维关联规则是处理各个属性之间的某些关系。例如：啤酒=>尿布，这条规则只涉及到⽤户的购买的物品；性别= “⼥”=>职业=“秘书”，这条规则就涉及到两个字段的信息，是两个维上的⼀条关联规则。
5. 关联规则挖掘的相关算法
1.Apriori算法：使⽤候选项集找频繁项集
Apriori算法是⼀种最有影响的挖掘布尔关联规则频繁项集的算法。其核⼼是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这⾥，所有⽀持度⼤于最⼩⽀持度的项集称为频繁项集，简称频集。
该算法的基本思想是：⾸先找出所有的频集，这些项集出现的频繁性⾄少和预定义的最⼩⽀持度⼀样。
然后由频集产⽣强关联规则，这些规则必须满⾜最⼩⽀持度和最⼩可信度。然后使⽤第1步找到的频集产⽣期望的规则，产⽣只包含集合的项的所有规则，其中每⼀条规则的右部只有⼀项，这⾥采⽤的是中规则的定义。⼀旦这些规则被⽣成，那么只有那些⼤于⽤户给定的最⼩可信度的规则才被留下来。为了⽣成所有频集，使⽤了递推的⽅法。
可能产⽣⼤量的候选集，以及可能需要重复扫描数据库，是Apriori算法的两⼤缺点。
2.基于划分的算法
Savare等设计了⼀个基于划分的算法。这个算法先把数据库从逻辑上分成⼏个互不相交的块，每次单独考虑⼀个分块并对它⽣成所有的频集，然后把产⽣的频集合并，⽤来⽣成所有可能的频集，最后计算这些项集的⽀持度。这⾥分块的⼤⼩选择要使得每个分块可以被放⼊主存，每个阶段只需被扫描⼀次。⽽算法的正确性是由每⼀个可能的频集⾄少在某⼀个分块中是频集保证的。该算法是可以⾼度并⾏的，可以把每⼀分块分别分配给某⼀个处理器⽣成频集。产⽣频集的每⼀个循环结束后，处理器之间进⾏通信来产⽣全局的候选k-项集。通常这⾥的通信过程是算法执⾏时间的主要瓶颈；⽽另⼀⽅⾯，每个独⽴的处理器⽣成频集的时间也是⼀个瓶颈。
3.FP-树频集算法
篮球社>最美的雪景
针对Apriori算法的固有缺陷，J. Han等提出了不产⽣候选挖掘频繁项集的⽅法：FP-树频集算法。采⽤分⽽治之的策略，在经过第⼀遍扫描之后，把数据库中的频集压缩进⼀棵频繁模式树（FP-tree），同时依然保留其中的关联信息，随后再将FP-tree分化成⼀些条件库，每个库和⼀个长度为1的频集相关，然后再对这些条件库分别进⾏挖掘。当原始数据量很⼤的时候，也可以结合划分的⽅法，使得⼀个FP-tree可以放⼊主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有巨⼤的提⾼。
五、关联规则发掘技术在国内外的应⽤
就⽬前⽽⾔，关联规则挖掘技术已经被⼴泛应⽤在西⽅⾦融⾏业企业中，它可以成功预测银⾏客户需求。⼀旦获得了这些信息，银⾏就可以改善⾃⾝营销。现在银⾏天天都在开发新的沟通客户的⽅法。各银⾏在⾃⼰的ATM机上就捆绑了顾客可能感兴趣的本⾏产品信息，供使⽤本⾏ATM机的⽤户了解。如果数据库中显⽰，某个⾼信⽤限额的客户更换了地址，这个客户很有可能新近购买了⼀栋更⼤的住宅，因此会有可能需要更⾼信⽤限额，更⾼端的新信⽤卡，或者需要⼀个住房改善贷款，这些产品都可以通过信⽤卡账单邮寄给客户。当客户打电话咨询的时候，数据库可以有⼒地帮助电话销售代表。销售代表的电脑屏幕上可以显⽰出客户的特点，同时也可以显⽰出顾客会对什么产品感兴趣。
同时，⼀些知名的电⼦商务站点也从强⼤的关联规则挖掘中的受益。这些电⼦购物⽹站使⽤关联规则
中规则进⾏挖掘，然后设置⽤户有意要⼀起购买的捆绑包。也有⼀些购物⽹站使⽤它们设置相应的交叉销售，也就是购买某种商品的顾客会看到相关的另外⼀种商品的⼴告。
但是⽬前在我国，“数据海量，信息缺乏”是商业银⾏在数据⼤集中之后普遍所⾯对的尴尬。⽬前⾦融业实施的⼤多数数据库只能实现数据的录⼊、查询、统计等较低层次的功能，却⽆法发现数据中存在的各种有⽤的信息，譬如对这些数据进⾏分析，发现其数据模式及特征，然后可能发现某个客户、消费群体或组织的⾦融和商业兴趣，并可观察⾦融市场的变化趋势。可以说，关联规则挖掘的技术在我国的研究与应⽤并不是很⼴泛深⼊。
近年来关联规则发掘技术的⼀些研究
由于许多应⽤问题往往⽐超市购买问题更复杂，⼤量研究从不同的⾓度对关联规则做了扩展，将更多的因素集成到关联规则挖掘⽅法之中，以此丰富关联规则的应⽤领域，拓宽⽀持管理决策的范围。如考虑属性之间的类别层次关系，时态关系，多表挖掘等。近年来围绕关联规则的研究主要集中于两个⽅⾯，即扩展经典关联规则能够解决问题的范围，改善经典关联规则挖掘算法效率和规则兴趣性。
