关联规则算法Apriori 学习笔记

Apriori简介

集体智慧(Collective Intelligence)

单一个体所做出的决策往往会比起多数决的决策来的不精准,集体智慧是一种共享的或者群体的智能,以及集结众人的意见进而转化为决策的一种过程。它是从许多个体的合作与竞争中涌现出来的。通常含义为:为了创造新的想法而将一群人的行为、偏好或思想组合在一起,从独立的数据提供者(用户)中总结规律、经验从而得到新的结论。随着通信技术的发展,互联网重构了知识体系,让每一个用户在享受知识的同时,也在默默贡献着知识。信息的价值不由任何一个个体所决定,而是由群体的行为来确定的。

关联规则(Association rule

关联规则分析也称为购物篮分析,最早是为了发现超市销售数据库中不同的商品之间的关联关系。关联规则是反映一个事物与其他事物之间的关联性,若多个事物之间存在着某种关联关系,那么其中的一个事物就能通过其他事物预测到。例如,从销售数据中发现的规则 {洋葱, 土豆}→{汉堡} 会表明如果顾客一起买洋葱和土豆,他们也有可能买汉堡的肉。此类信息可以作为做出促销定价或产品植入等营销活动决定的根据。除了上面购物篮分析中的例子以外,关联规则如今还被用在许多应用领域中,包括网络用法挖掘、入侵检测、连续生产及生物信息学中。与序列挖掘相比,关联规则学习通常不考虑在事务中、或事务间的项目的顺序。

频繁项集Frequent Itemset

经常一起出现的item集合称为频繁项集。常用的频繁项集的评估标准有支持度、置信度和提升度:

支持度

支持度就是几个关联的数据在数据集中出现的次数占总数据集的比重。或者说几个数据关联出现的概率。如果我们有两个想分析关联性的数据X和Y,则对应的支持度为:

$$Support(X,Y) = P(XY) = \frac{number(XY)}{number(All Samples)}$$

以此类推,如果我们有三个想分析关联性的数据X,Y和Z,则对应的支持度为:

$$Support(X,Y,Z) = P(XYZ) = \frac{number(XYZ)}{number(All Samples)}$$

一般来说,支持度高的数据不一定构成频繁项集,但是支持度太低的数据肯定不构成频繁项集。

置信度

置信度体现了一个数据出现后,另一个数据出现的概率,或者说数据的条件概率。如果我们有两个想分析关联性的数据X和Y,X对Y的置信度为:

$$Confidence(X \Leftarrow Y) = P(X|Y)=\frac{P(XY)}{P(Y)}$$

也可以以此类推到多个数据的关联置信度,比如对于三个数据X,Y,Z,则X对于Y和Z的置信度为:

$$Confidence(X \Leftarrow YZ) = P(X|YZ)=\frac{P(XYZ)}{P(YZ)}$$

提升度

提升度表示含有Y的条件下,同时含有X的概率,与X总体发生的概率之比,即:

$$Lift(X \Leftarrow Y) = \frac{P(X|Y)}{P(X)} = \frac{Confidence(X \Leftarrow Y)}{P(X)}$$

提升度体先了X和Y之间的关联关系, 提升度大于1则$X \Leftarrow Y$是有效的强关联规则, 提升度小于等于1则$X \Leftarrow Y$是无效的强关联规则 。一个特殊的情况,如果X和Y独立,则有$Lift(X \Leftarrow Y) = 1$,因为此时$P(X|Y) = P(X)$。

支持度和可信度是用来量化关联分析是否成功的方法。关联分析的目的包括两个:发现频繁项集和发现关联规则。首先我们要找到频繁项集,然后根据频繁项集找出关联规则。一般来说,要选择一个数据集合中的频繁数据集,则需要自定义评估标准。最常用的评估标准是用自定义的支持度,或者是自定义支持度和置信度的一个组合。

Apriori 算法简介

支持度和可信度是用来量化关联分析是否成功的一个方法。假设想找到支持度大于 0.8 的所有项集,应该如何去做呢? 一个办法是生成一个物品所有可能组合的清单,然后对每一种组合统计它出现的频繁程度。确实可以通过遍历所有组合就能找出所有频繁项集,但问题是遍历所有组合花的时间太多,效率太低,假设有N个物品,那么一共需要计算$2^N-1$次。每增加一个物品,数量级是成指数增长。而Apriori就是一种找出频繁项集的高效算法。了解Apriori算法推导之前,我们先介绍一些基本概念:

  • K项集(K-itemset):同时购买的K项集合。
  • 频繁K项集(frequent itemset):满足最小支持度阈值的K项集合。
  • 候选K项集(candidate itemset):通过连接形成的K项集合。

Apriori的核心就是下面这句话:某个项集是频繁的,那么它的所有子集也是频繁的。这句话看起来是没什么用,但是反过来就很有用了。如果一个项集是非频繁项集,那么它的所有超集也是非频繁项集。

如图所示,我们发现{A,B}这个项集是非频繁的,那么{A,B}这个项集的超集,{A,B,C},{A,B,D}等等也都是非频繁的,这些就都可以忽略不去计算。运用Apriori算法的思想,我们就能去掉很多非频繁的项集,大大简化计算量。

Apriori算法是经典的挖掘频繁项集和关联规则的数据挖掘算法。A priori在拉丁语中指”来自以前”。当定义问题时,通常会使用先验知识或者假设,这被称作”一个先验”(a priori)。Apriori算法的名字正是基于这样的事实:算法使用频繁项集性质的先验性质,即频繁项集的所有非空子集也一定是频繁的。Apriori算法使用一种称为逐层搜索的迭代方法,其中k项集用于探索(k+1)项集。首先,通过扫描数据库,累计每个项的计数,并收集满足最小支持度的项,找出频繁1项集的集合。该集合记为L1。然后,使用L1找出频繁2项集的集合L2,使用L2找出L3,如此下去,直到不能再找到频繁k项集。每找出一个Lk需要一次数据库的完整扫描。Apriori算法使用频繁项集的先验性质来压缩搜索空间,其核心思想是通过连接产生候选项及其支持度,然后通过剪枝生成频繁项集。。与朴素贝叶斯分类器一样都是用到先验知识,但是贝叶斯是多个概率推断 True/False,关联规则是解决A→Who 的问题。

Apriori的优点:

  • 适合稀疏数据集。
  • 算法原理简单,易实现。
  • 适合事务数据库的关联规则挖掘。
  • 易编码实现

Apriori的缺点

  • 可能产生庞大的候选集。
  • 算法需多次遍历数据集,算法效率低,耗时。
  • 在大数据集上可能较慢

Apriori算法能够有效发现频繁项集并获取关联规则,但是每次计算频繁项集的支持度(主要是指:项集所构成的超集的支持度)都要遍历整个数据库,因此造成过多的时间开销,无法高效处理大规模数据集。为了克服Apriori算法这一缺点,包括FP-Growth等算法应运而生,FP-Growth算法则需扫描原始数据两遍,通过FP-tree数据结构对原始数据进行压缩,效率较高。现在一般很少直接用Aprior算法来挖掘数据了,但是理解Aprior算法是理解其它Aprior类算法的前提,同时算法本身也不复杂,因此值得好好研究一番。

Apriori 代码实现

其他实现方式:MLxtend包的使用。

参考链接:http://www.jasongj.com/ml/associationrules/

微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

时间序列趋势判断

判断时间序列数据是上升还是下降是我们常见的问题。比如某个股票在过去一年整体趋势是上升还是下降。我们可以通过画图

聚类算法之Affinity Propagation(AP)

Affinity Propagation算法简介 AP(Affinity Propagation)通常被翻译为

机器学习算法之朴素贝叶斯

贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。而朴素贝叶斯分类是贝叶斯分类

发表评论

电子邮件地址不会被公开。 必填项已用*标注