Apriori algorithm是关联规则里一项基本算法。是由Rakesh Agrawal和Ramakrishnan Srikant两位博士在1994年提出的关联规则挖掘算法。关联规则的目的就是在一个数据集中找出项与项之间的关系,也被称为购物蓝分析 (Market Basket analysis),因为“购物蓝分析”很贴切的表达了适用该算法情景中的一个子集。

关于这个算法有一个非常有名的故事:"尿布和啤酒"。故事是这样的:美国的妇女们经常会嘱咐她们的丈夫下班后为孩子买尿布,而丈夫在买完尿布后又要顺 手买回自己爱喝的啤酒,因此啤酒和尿布在一起被购买的机会很多。这个举措使尿布和啤酒的销量双双增加,并一直为众商家所津津乐道。

 

【1】一些概念和定义

  • 资料库(Transaction Database):存储着二维结构的记录集。定义为:D 
  • 所有项集(Items):所有项目的集合。定义为:I。
  • 记录 (Transaction ):在资料库里的一笔记录。定义为:T,T ∈ D
  • 项集(Itemset):同时出现的项的集合。定义为:k-itemset(k项集),k-itemset ? T。除非特别说明,否则下文出现的k均表示项数。
  • 支持度(Support):定 义为 supp(X) = occur(X) / count(D) = P(X)。
   1. 解释一:比如选秀比赛,那个支持和这个有点类似,那么多人(资料库),其中有多少人是选择(支持)你的,那个就是支持度;
   2. 解释二:在100个人去超市买东西的,其中买苹果的有9个人,那就是说苹果在这里的支持度是 9,9/100;
   3. 解释三:P(X),意思是事件X出现的概率;
   4. 解释四:关联规则当中是有绝对支持度(个数)和相对支持度(百分比)之分的。
  • 置信度(Confidence/Strength): 定义为 conf(X->Y) = supp(X ∪ Y) / supp(X) = P(Y|X)。
在历史数据中,已经买了某某(例如:A、B)的支持度和经过挖掘的某规则(例如:A=>B)中A的支持度的比 例,也就是说买了A和B的人和已经买了 A的人的比例,这就是对A推荐B的置信度(A=>B的置信度)< /span>
  • 候选 集(Candidate itemset):通过向下合并得出的项集。定义为C[k]。
  • 频繁集(Frequent itemset):支持度大于等于特定的最小支持度(Minimum Support/minsup)的项集。表示为L[k]。注意,频繁集的子集一定是频繁集。
  • 提升比率(提升度Lift):lift(X -> Y) = lift(Y -> X) = conf(X -> Y)/supp(Y) = conf(Y -> X)/supp(X) = P(X and Y)/(P(X)P(Y))
经过关联规则分析后,针对某些人推销(根据某规则)比盲目推销(一般来说是整个数据)的比率,这个比率越高越好,我们称这个规则为强规则;
  • 剪枝步
只有当子集都是频繁集的候选集才是频繁集,这个筛选的过程就是剪枝步;

 

【2】Apriori优化:Fp-tree 算法

 

  • 关键点:以树形的形式来展示、表达数据的形态;可以理解为水在不同河流分支的流动过程;
  • 生成Fp-tree的几个点:
  1. 扫描原始项目集;
  2. 排列数据; 
  3. 创建ROOT节点;
  4. 按照排列的数据进行元素的流动;
  5. 节点+1; 
  •  更多内容请自行学习

 

【3】Apriori优化:垂直数据分布

  •  关键点:相当于把原始数据进行行转列的操作,并且记录每个元素的个数
  •   更多内容请自行学习

 

【4】摘要:数据挖掘中关联规则算法的研究

Apriori核心算法过程如下:

  1. 过单趟扫描数据库D计算出各个1项集的支持度,得 到频繁1项集的集合。
  2. 连接步:为了生成,预先生成,由2个只有一个项不同的属于的频集做一 个(k-2)JOIN运算得到的。
  3. 剪枝步:由于是的超集,所以可能有些元素不是频繁的。在 潜在k项集的某个子集不是中的成员是,则该潜在频繁项集不可能是频繁的可以从中移去。
  4. 通过 单趟扫描数据库D,计算中各个项集的支持度,将中不满足支持度的项集去掉形成。

 

通过迭代循环,重复步骤2~4,直到有某个r值使得为空,这时算法停止。在剪枝步中的每个元 素需在交易数据库中进行验证来决定其是否加入,这里的验证过程 是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库。可能产生大量的候选集,以及可能需要重复扫描数据库,是Apriori算法的两大缺 点。

目前,几乎所有高效的发现关联规则的并行数据挖掘算法都是基于Apriori算法 的,Agrawal和Shafer 提出了三种并行算法:计数分发(Count Distribution)算法、数据分发(Data Distribution)算法和候选分发(Candidate Distribute)算法。

 

【5】总结

  1. 例子就暂时不举例,因为网上的这些例子也是比较多的;
  2. 度量标准还有很多很多很多,如:Lift/Interest、All-confidence、Consine、Conviction、Jaccard、Leverage、Collective strength等等。
  3. 频繁数据模型的分类比较多,需要慢慢理解;

 

参考文献

两位博士的论文下载:《Fast Algorithms for Mining Association Rules》

一篇不错的文章下载:在交易数据库中发现关联规则

Blog:关联规则(apriori algorithm)(1) 

 

Blog:数据挖掘中关联规则算法的研究

Blog:Fp-tree 算法

7.混合高斯模型(Mixtures of Gaussians)和 EM 算法

这篇讨论使用期望最大化算法(Expectation-Maximization)来进行密度估计(density estimation)。 与k-means 一样,给定的训练样本是{x (1), … ,x (m)},我...

阅读全文

6. K-means聚类算法

K-means也是聚类算法中最简单的一种了,但是里面包含的思想却是不一般。聚类属于无监督学习,以往的回归、朴素贝叶斯、SVM等都是有类别标签y的,也就是说样例...

阅读全文

欢迎留言