Apriori算法
2018-07-22 本文已影响32人
heaker
Apriori算法
1.定义：一种用于关联规则挖掘的代表性算法
2.一些基本的概念：
2.1 数据挖掘可以视为数据库、机器学习和统计学三者的交叉。第一者提供了数据管理技术；后两者提供了数据分析技术。
2.2关联规则是形如 X→Y 的蕴涵表达式，其中X和Y是不相交的项集【包含0个或多个项的集合被称为项集（itemset）】，即 X∩Y=∅。关联规则的强度可以用以下两个指标来衡量：
- 支持度（support）:持度确定规则可以用于给定数据集（全局）的频繁程度
- 置信度（confidence）:确定Y在包含X的交易中出现的频繁程度
两者的公式如下：
两个公式
2.3 用一个简单的例子来解释该概念:
一个超市的收银数据
[图片上传失败...(image-a983f3-1532249865361)]
2.4 因此，大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务：
- 频繁项集产生：其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集（frequent itemset）。
- 规则的产生：其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。
- ps：常常频繁项集产生所需的计算开销远大于产生规则所需的计算开销。寻找频繁项集最容易想到的方法是暴力法（Brute-Force），但此方法通常不可行。
3.先验原理
3.1 Apriori 两条定律：
-
定律1：如果一个集合是频繁项集，则它的所有子集都是频繁项集。
- 例如：假设一个集合{A,B}是频繁项集，即A、B同时出现在一条记录的次数大于等于最小支持度min_support，则它的子集{A},{B}出现次数必定大于等于min_support，即它的子集都是频繁项集。
-
定律2：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。
- 举例：假设集合{A}不是频繁项集，即A出现的次数小于 min_support，则它的任何超集如{A,B}出现的次数必定小于min_support，因此其超集必定也不是频繁项集。
3.2 运用定理的一个例子：
下图表示当我们发现{A,B}是非频繁集时，就代表所有包含它的超级也是非频繁的，即可以将它们都剪除。
image
4.Apriori算法与实例【核心】
4.1 算法的形式化描述：
image
4.2 算法的实例：
image
4.3 上条C集生成策略的解释：
image
-
首先是self-joining部分。例如，假设我们有一个L3={abc, abd, acd, ace, bcd}（注意这已经是排好序的}。选择两个itemsets，它们满足条件：前k-1个item都相同，但最后一个item不同，把它们组成一个新的Ck+1的项集c。如下图所示，{abc}和{abd}组成{abcd}，{acd}和{ace}组成{acde}。
-
生成策略的第二部分是pruning。对于一个位于Ck+1中的项集c，s是c的大小为k的子集，如果s不存在于Lk中，则将c从Ck+1中删除。如下图所示，因为{acde}的子集{cde}并不存在于L3中，所以我们将{acde}从C4中删除。最后得到的C4，仅包含一个项集{abcd}。
image
