美文网首页
机器学习实战-10-Apriori关联分析

机器学习实战-10-Apriori关联分析

作者: nobodyyang | 来源:发表于2018-12-23 23:29 被阅读0次

    一、关联分析介绍

    商场的销售过程,涉及很多机器学习的应用,商品的陈列,购物卷的提供,用户忠诚度等等,通过对这些大量数据的分析,可以帮组商店了解用户的购物行为,进而对商品的定价、市场促销、存货管理等进行决策帮组。

    从大规模数据集中寻找物品间的隐含关系被称作关联分析(association analysis)或者关联规则学习(association rule learning)。这里的主要问题在于,寻找物品的不同组合是一项十分耗时的任务,所需的计算代价很高,蛮力搜索方法并不能解决这个问题,所以需要用更智能的方法在合理的时间范围内找到频繁项集。

    关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式:频繁项集或者关联规则。频繁项集(frequent item sets)是经常出现在一块的物品的集合,关联规则(association rules)暗示两种物品之间可能存在很强的关系。
    下图给出了某个杂货店的交易清单。

    频繁项集是指那些经常出现在一起的物品集合,上图中的集合{葡萄酒,尿布, 豆奶}就是频繁项集的一个例子。从下面的数据集中也可以找到诸如尿布➞葡萄酒的关联规则。这意味着如果有人买了尿布,那么他很可能也会买葡萄酒。使用频繁项集和关联规则,商家可以更好地理解他们的顾客。

    当寻找频繁项集时,什么样的数据才是频繁项集呢?频繁(frequent)的定义是什么?

    常用的频繁项集的评估标准有支持度,置信度两个。

    • 支持度:数据集中,包含该项集的记录出现的次数占总数据集的比重。
    • 可信度:也称为置信度,体现了一个数据出现后,另一个数据出现的概率,或者说数据的条件概率。针对一条关联规则来定义的。

    从上图交易清单中可以得到,{豆奶}的支持度为4/5。而在5条交易记录中有3条包含{豆奶,尿布},因此{豆奶,尿布}的支持度为3/5。

    针对一条诸如{尿布}➞{葡萄酒}的这条关联规则,这条规则的可信度被定义为“支持度({尿布, 葡萄酒})/支持度({尿布})”。由于{尿布, 葡萄酒}的支持度为3/5,尿布的支持度为4/5,所以“尿布➞葡萄酒”的可信度为3/4=0.75。这意味着对于包含“尿布”的所有记录,我们的规则对其中75%的记录都适用。

    因此,我们可以利用支持度和可信度是用来量化关联分析是否成功。但是,当数据量非常大的时候,物品成千上万时,按照上述方法生成一个物品所有可能组合的清单非常非常慢,统计每一种组合它出现的频繁程度也很非常慢。这催生了关联规则挖掘的算法Apriori,该原理会减少关联规则学习时所需的计算量。

    二、Apriori算法原理

    一杂货店有四种商品 0,1,2,3.这些商品的组合可能有一种,二种,三种,四种。我们的关注点:用户购买一种或者多种商品,不关心具体买的商品的数量。
    集合{0,1,2,3}中所有可能的项集组合如下图

    四种商品要遍历15次,随着物品数目的增加遍历次数会急剧增加。对于包含N种商品的数据集一共有2^N-1种项集组合。

    Apriori原理:

    • 如果某个项集是频繁的,那么它的所有子集也是频繁的。
    • 如果一个项集是非频繁集,那么它的所有超集也是非频繁的。

    根据Apriori原理,假设集合{2,3}是非频繁项集,则{0,2,3},{1,2,3},{0,1,2,3}也是非频繁的,它们的支持度就不需要计算了。

    Apriori算法采用迭代的方法,先搜索出候选1项集及对应的支持度,剪枝去掉低于支持度的1项集,得到频繁1项集。然后对剩下的频繁1项集进行连接,得到候选的频繁2项集,筛选去掉低于支持度的候选频繁2项集,得到真正的频繁二项集,以此类推,迭代下去,直到无法找到频繁k+1项集为止,对应的频繁k项集的集合即为算法的输出结果。

    第i次的迭代过程包括扫描计算候选频繁i项集的支持度,剪枝得到真正频繁i项集和连接生成候选频繁i+1项集三步。

    上面的数据集D有4条记录,分别是134,235,1235和25。现在用Apriori算法来寻找频繁k项集,最小支持度设置为50%。首先生成候选频繁1项集,包括所有的5个数据并计算5个数据的支持度,计算完毕后进行剪枝,数据4由于支持度只有25%被剪掉。最终的频繁1项集为1235,现在我们链接生成候选频繁2项集,包括12,13,15,23,25,35共6组。此时第一轮迭代结束。

    进入第二轮迭代,扫描数据集计算候选频繁2项集的支持度,接着进行剪枝,由于12和15的支持度只有25%而被筛除,得到真正的频繁2项集,包括13,23,25,35。现在链接生成候选频繁3项集,123, 125,135和235共4组,这部分图中没有画出。通过计算候选频繁3项集的支持度,发现123,125和135的支持度均为25%,因此接着被剪枝,最终得到的真正频繁3项集为235一组。由于此时无法再进行数据连接,进而得到候选频繁4项集,最终的结果即为频繁3三项集235。

    使用该原理就可以避免项集数目的指数增长,从而在合理时间内计算出频繁项集。

    三、算法实现

    算法伪代码:

    3.1 apriori算法辅助函数

    辅助函数有creat_c1、scan_d

    可以看出,支持度不小于0.5的项集被选中到L中作为频繁项集,可以根据不同的需求设定最小支持度的值,从而得到想要的频繁项集。

    3.2 组织完整的Apriori发现频繁项集

    3.3 从频繁项集中挖掘关联规则

    要找到关联规则,先从一个频繁集开始,我们想知道对于频繁项集中的元素能否获取其它内容,即某个元素或者某个集合可能会推导出另一个元素。从表1 可以得到,如果有一个频繁项集 {豆奶,莴苣},那么就可能有一条关联规则 "豆奶 --> 莴苣",意味着如果有人购买了豆奶,那么在统计上他会购买莴苣的概率较大。但是这一条反过来并不一定成立。

    一个频繁项集可以产生许多可能的关联规则,如果能在计算规则可信度之前就减少规则的数目,就会很好的提高计算效率。有一条规律就是:如果某条规则并不满足最小可信度要求,那么该规则的所有子集也不会满足最小可信度要求,例如下图的解释:

    结果中给出三条规则:{1} ➞ {3}、{5} ➞ {2}及{2} ➞ {5}。可以看到,后两条包含2和5的规则可以互换前件和后件,但是前一条包含1和3 的规则不行。下面降低可信度阈值之后看一下结果:

    一旦降低可信度阈值,就可以获得更多的规则。

    四、示例:发现毒蘑菇的相似特征

    首先看一下毒蘑菇的数据集:

    第一个特征表示有毒或者可食用。如果某样本有毒,则值为2。如果可食用,则值为1。下一个特征是蘑菇伞的形状,有六种可能的值,分别用整数3-8来表示。

    为了找到毒蘑菇中存在的公共特征,可以运行Apriori算法来寻找包含特征值为2的频繁项集。

    扩大范围到3个:

    接下来需要观察一下这些特征,以便知道了解野蘑菇的那些方面。

    五、小结

    关联分析是用于发现大数据集中元素间有趣关系的一个工具集,可以采用两种方式来量化这些有趣的关系。第一种方式是使用频繁项集,它会给出经常在一起出现的元素项。第二种方式是关联规则,每条关联规则意味着元素项之间的“如果……那么”关系。

    Apriori的方法简化了计算量,在合理的时间范围内找到频繁项集:Apriori原理是说如果一个元素项是不频繁的,那么那些包含该元素的超集也是不频繁的。

    Apriori算法从单元素项集开始,通过组合满足最小支持度要求的项集来形成更大的集合。支持度用来度量一个集合在原始数据中出现的频率。

    每次增加频繁项集的大小,Apriori算法都会重新扫描整个数据集。当数据集很大时,这会显著降低频繁项集发现的速度。下一篇会介绍FP-growth算法,和Apriori算法相比,该算法只需要对数据库进行两次遍历,能够显著加快发现繁项集的速度。

    相关文章

      网友评论

          本文标题:机器学习实战-10-Apriori关联分析

          本文链接:https://www.haomeiwen.com/subject/yilahqtx.html