关联模式挖掘 张莫.pptVIP

关联挖掘 (按姓氏拼音) 陈广新 阮艳琴 张莫 关联规则 一个被传诵了千百遍的例子： 沃尔玛超市号称拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其他门店的购买习惯，沃尔玛对其顾客购物行为进行购物篮分析，以期知道顾客经常一起购买的东西有哪些。在对统计出来的数据进行分析和挖掘后，一个意外的发现是：和尿布在一起购买的最多的竟然是啤酒。自习想想也不难理解，商家给出的解释是，美国太太经常叮嘱丈夫在下班后先去超市买尿布，而父亲们买尿布的同时顺手就给自己买了啤酒。这种关联超出了我们的正常思维模式，而正是得益于数据挖掘技术，我们才能发现这一潜在关联关系。 数据关联是数据库中存在一类的可被发现的重要知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可以分为简单、时序、因果关联。 关联分析的目的是找出数据库中隐藏的关系网。有时并不知道数据库中数据的关联函数，即是知道也是不确定的，因此关联分析生成的规则带有可信度。最终得到有趣的关联或相关联系。 关联规则挖掘的过程 第一阶段：先从资料集合中找出所有的高频项目组 关联规则挖掘的第一阶段必须从原始资料集合中，找出所有高频项目组(Large Itemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一水平。一项目组出现的频率称为支持度(Support)，以一个包含A与B两个项目的2-itemset为例，我们可以求得包含{A,B}项目组的支持度，若支持度大于等于所设定的最小支持度(Minimum Support)门槛值时，则{A,B}称为高频项目组。一个满足最小支持度的k-itemset，则称为高频k-项目组(Frequent k-itemset)，一般表示为Large k或Frequent k。算法并从Large k的项目组中再产生Large k+1，直到无法再找到更长的高频项目组为止。 第二阶段：再从这些高频项目组中产生关联规则 关联规则挖掘的第二阶段是要产生关联规则(Association Rules)。从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小信赖度(Minimum Confidence)的条件门槛下，若一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。例如：经由高频k-项目组{A,B}所产生的规则AB，求得其信赖度，若信赖度大于等于最小信赖度，则称AB为关联规则。 就沃尔马案例而言，使用关联规则挖掘技术，对交易资料库中的纪录进行资料挖掘，首先必须要设定最小支持度与最小信赖度两个门槛值，在此假设最小支持度min_support=5% 且最小信赖度min_confidence=70%。因此符合此该超市需求的关联规则将必须同时满足以上两个条件。若经过挖掘过程所找到的关联规则「尿布，啤酒」，满足下列条件，将可接受「尿布，啤酒」的关联规则。用公式可以描述Support(尿布，啤酒)=5%且Confidence(尿布，啤酒)=70%。其中，Support(尿布，啤酒)=5%于此应用范例中的意义为:在所有的交易纪录资料中，至少有5%的交易呈现尿布与啤酒这两项商品被同时购买的交易行为。Confidence(尿布，啤酒)=70%于此应用范例中的意义为:在所有包含尿布的交易纪录资料中，至少有70%的交易会同时购买啤酒。因此，今后若有某消费者出现购买尿布的行为，超市将可推荐该消费者同时购买啤酒。这个商品推荐的行为则是根据「尿布，啤酒」关联规则，因为就该超市过去的交易纪录而言，支持了“大部份购买尿布的交易，会同时购买啤酒”的消费行为。 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。　　 该算法的基本思想是：频繁项集的任何子集也是频繁的。首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。 挖掘多层关联规则 自上而下，深度优先的方法： 先找高层的“强”规则： 牛奶 ? 面包 [20%, 60%]. 再找他们底层的“弱”规则： 酸奶 ? 黄面包 [6%, 50%]. 多层关联规则的变种 层次交叉的