R语言大数据分析与挖掘 课件 第九章 关联算法

第9章

关联算法内容要点1、了解关联算法的相关理论。2、掌握R语言中Apriori算法建模的方法。3、掌握R语言中ECLAT算法建模的方法。关联算法概述Apriori算法ECLAT算法123关联算法概述关联是指一个事件和其他事件之间的联系，这些联系蕴含在交易数据、关系数据或其他信息载体中。在用户设定的条件下利用算法查找存在于数据中的项目集合或对象集合之间的频繁模式、关联、相关性或因果结构就是关联分析。不同项集间的联系就是关联规则，在设定条件时一般要设定支持度及信任度。关联分析的相关概念如图9-1所示。在用户设定的条件下利用算法查找存在于数据中的项目集合或对象集合之间的频繁模式、关联、相关性或因果结构就是关联分析。不同项集间的联系就是关联规则，在设定条件时一般要设定支持度及信任度。关联分析的相关概念如图9-1所示。关联算法概述在一家超市中，人们发现了一个特别有趣的现象：尿布与啤酒这两种风马牛不相及的商品居然摆在一起。但这一奇怪的举措居然使尿布和啤酒的销量大幅增加了。这可不是一个笑话，而是一直被商家所津津乐道的发生在美国沃尔玛连锁超市的真实案例。原来，美国的妇女通常在家照顾孩子，所以她们经常会嘱咐丈夫在下班回家的路上为孩子买尿布，而丈夫在买尿布的同时又会顺手购买自己爱喝的啤酒。这个发现为商家带来了大量的利润，但是如何从非常多数据中，发现啤酒和尿布销售之间的联系呢？这就需要对数据中的啤酒和尿布进行关联分析找到它们的关联规则。示例：表9-1是一个超市几名顾客的交易信息。对此数据集进行关联分析，可以找出关联规则{Diaper}→{Beer}。它代表的意义是购买了Diaper的顾客会购买Beer。这个关系不是必然的，但是可能性很大。这就已经足够用来辅助商家调整Diaper和Beer的摆放位置了，如摆放在相近的位置进行捆绑促销来提高销售量。关联算法概述相关名词关联算法概述关联规则及频繁项集的产生关联规则：形如X→Y这样的蕴含关系称为关联规则，X和Y均是项集。关联规则有两个属性：支持度和置信度。（1）关联规则的支持度(见右),N是事务的总数。（2）关联规则的置信度(见右)。由此可以定义关联分析问题：在给定的事务集中，找到（支持度，置信度）大于给定阈值(sS0,C0)的所有关联规则。普通的方法是遍历所有的关联规则，其复杂度为(见右)。好一点的方法是使用剪枝，因为关联规则的支持度只与项集有关，可以首先筛选出支持度大于阈值s0的所有项集，这样的项集叫作频繁项集。给定频繁项集，可以从中选出置信度大于阈值c0的所有关联规则，这样的规则叫作强规则。关联规则的支持度关联规则的置信度复杂度Apriori算法Apriori算法是常用于挖掘数据关联规则的算法，能够发现事务数据库中频繁出现的项集，这些联系构成的规则可帮助用户找出某些行为特征，以便进行企业决策。Apriori算法概述Apriori算法是一种最有影响的挖掘布尔关联规则（规则形如X→Y的蕴涵式）频繁项集的算法，其核心思想是通过候选项集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。而且算法已经被广泛地应用到商业、网络安全等各个领域。很多的挖掘算法是在Apriori算法的基础上进行改进的，如基于散列（Hash）的方法、基于数据分割（Partition）的方法及不产生候选项集的FP-growth算法等。因此要了解关联规则算法首先要了解Apriori算法。Apriori算法先验原理为降低产生频繁项集的计算复杂度，利用支持度对候选项集进行剪枝，这也是Apriori算法所利用的第一条先验原理。Apriori定律1：若一个集合是频繁项集，则它的所有子集都是频繁项集。例如，假设一个集合{A,B}是频繁项集，即A、B同时出现在一条记录的次数大于或等于最小支持度min_support，则它的子集{A},{B}出现次数必定大于或等于min_support，即它的子集都是频繁项集。Apriori定律2：若一个集合不是频繁项集，则它的所有超集都不是频繁项集。例如，假设集合{A}不是频繁项集，即A出现的次数小于min_support，则它的任何超集如{A,B}出现的次数必定小于min_support，因此其超集必定也不是频繁项集。当发现{A,B}是非频繁项集时，就代表所有包含它的超集也是非频繁的，即可以将它们都剪除，如图9-2所示。Apriori算法连接步和剪枝步1．连接步若有两个(k-1)-项集，每个项集按照“属性-值”（一般按值）的字母顺序进行排序。若两个(k-1)-项集的前(k-2)个项相同，而最后一个项不同，则证明它们是可连接的，即这个(k-1)-项集可以联姻，即可连接生成k-项集。即为找出Lk（所有的频繁k-项集的集合），通过将Lk-1（所有的频繁(k-1)-项集的集合）与自身连接产生候选k-项集的集合，候选项集合记作Ck。设l1和l2是Lk-1中的成员。记li[j]表示li中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于(k-1)-项集li，li[1]<li[2]<…<li[k-1]。将Lk-1与自身连接，如果(l1[1]=l2[1])&&(l1[2]=l2[2])&&…&&(l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那认为l1和l2是可连接的。连接l1和l2产生的结果是{l1[1],l1[2],…,l1[k-1],l2[k-1]}。例如，有两个3项集｛a,b,c｝和{a,b,d}，这两个3项集就是可连接的，它们可以连接生成4项集｛a,b,c,d｝。又如两个3项集｛a,b,c｝｛a,d,e｝，这两个3项集显示是不能连接生成3项集的。Apriori算法连接步和剪枝步2．剪枝步Ck是Lk的超集，也就是说，Ck的成员可能是也可能不是频繁的。通过扫描所有的事务（交易），确定Ck中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。若一个项集的子集不是频繁项集，则该项集肯定也不是频繁项集。例如，若存在3项集｛a,b,c｝，它的2项子集｛a,b｝的支持度，即同时出现的次数达不到阈值，则｛a,b,c｝同时出现的次数显然也是达不到阈值的。因此，若存在一个项集的子集不是频繁项集，那么该项集就应该被无情的舍弃。Apriori算法Apriori算法流程Apriori算法流程如下。（1）扫描数据库D，计算出各个1项集的支持度，得到频繁1项集的集合。（2）从2项集开始循环，由频繁(k-1)-项集生成频繁k-项集。①连接步：先生成频繁(k-1)-项集，频繁(k-1)-项集是由两个只有一个项不同的频繁项集做一个(k-2)JOIN运算得到的。②剪枝步：由于是超集，所以可能有些元素不是频繁的。舍弃掉子集不是频繁项集的(k-1)-项集。③扫描数据库，计算②、③步中过滤后的(k-1)-项集的支持度，舍弃掉支持度小于阈值的项集，生成频繁k-项集。（3）当前生成的频繁k-项集中只有一个项集时循环结束。假设数据库里有4条交易，分别为{A,C,D}、{B,C,E}、{A,B,C,E}、{B,E}，使用min_support=2作为支持度阈值，最后筛选出来的频繁项集为{B,C,E}，筛选过程如图9-3所示。Apriori算法Apriori算法实例arules包的Groceries数据集中包含了大量的购物清单数据，可用于关联分析。安装并加载R包，代码如下：加载数据集并查看数据集Groceries，代码如下：输出结果为：Apriori算法Apriori算法实例（续）apriori(X,parameter=list(support=0.001,confidence=0.05))可计算所有的规则，是关联规则分析的核心函数。parameter是用来设定计算频率（支持度）和置信度的关联规则。上面即求所有支持度大于0.001和置信度大于0.05的关联规则。代码如下：Apriori算法Apriori算法实例（续）查看模型，代码如下：输出结果为：Apriori算法Apriori算法实例（续）模型共找到了37937个关联规则，查看支持度前10的规则，代码如下：输出结果为：支持度排名第1的规则为{othervegetables}=>{wholemilk}，两者同时被购买的概率约为7%。Apriori算法是通过频繁(k-1)-项集找到频繁k-项集的，虽然可以通过Apriori性质进行减枝，去掉一部分子集为非频繁项集的候选项集，但还是需要不断地扫描数据集，不断地求候选项集的支持度计数从而判断它是否是频繁项集。如果数据集足够大，这种算法就不再具有优势。ECLAT算法ECLAT算法是一种深度优先算法，采用垂直数据表示形式，在概念格理论的基础上利用基于前缀的等价关系将搜索空间（概念格）划分为较小的子空间（子概念格）。ECLAT算法概述ECLAT算法不同于关联规则中的Apriori算法和FP-growth算法，后两者所采用的是从TID集格式的事物集中挖掘频繁项集的水平数据结构的方式，而ECLAT算法采用了垂直数1．ECLAT算法优缺点（1）优点：采用了与传统挖掘算法不同的垂直数据库结构，由于这样只要扫描两次数据库，大大减少了挖掘规则所需要的时间，从而提高了挖掘关联规则的效率。（2）缺点：该算法没有对产生的候选项集进行删减操作，若项目出现的频率非常高，频繁项集庞大，进行交集操作时会消耗系统大量的内存，影响算法的效率。ECLAT算法2．ECLAT算法原理由两个频繁k-项集求并集得到候选(k+1)-项集，对候选(k+1)-项集的事务集做交集操作，生成频繁(k+1)-项集，以此迭代直到项集归一，算法结束。ECLAT算法加入了倒排的思想，具体就是将事务数据中的项作为key，每个项对应的事务ID作为value。原输入数据为：转换后为：通过转换后的倒排表可以加快频繁项集生成速度。根据上述数据的情况，具体计算过程如下。（1）计算频繁1-项集，结果为：（2）由频繁1-项集生成频繁2-项集，结果为：（3）由频繁2-项集生成频繁3-项集，结果为：频繁k-项集生成频繁(k+1)-项集的过程与由1-项集生成2-项集的过程完全一致。ECLAT算法ECLAT算法流程通过扫描一次数据集，把水平格式的数据转换成垂直格式；根据分析的要求，设定项集的支持度计数；从k=1开始，可以根据先验性质，使用频繁k-项集来构造候选(k+1)-项集；通过取频繁k-项集的TID（TID集格式即｛TID：itemset｝，其中TID是事务标识符，而itemset是事务TID中购买的商品）集的交，计算对应的(k+1)-项集的TID集；重复该过程，直到不能再找到频繁项集或者候选项集。12345ECLAT算法ECLAT算法实例这里还是使用“Groceries”数据集进行分析。代码如下：输出结果为：ECLAT算法ECLAT算法实例共有13335个关联规则符合条件，查看关联规则，代码如下：输出结果为：查看支持度排名前10的关联规则，代码如下：输出结果为：支持度最高的频繁二项集为：{othervegetables,wholemilk}，支持度约为7%，在相同的设定条件下得到的结果与apriori算法相同。ECLAT算法ECLAT算法实例（续）arules包为itemset实现了一些可视化方法，这些方法是ECLAT算法的返回类型。创建一个新的item较少的数据集，做可视化展示，代码如下：结果如图9-4所示。