Apriori算法详解
本文将介绍：
关联分析
Apriori算法
Apriori算法详解
学习一个算法，我们最关心的并不是算法本身，而是一个算法能够干什么，能应用到什么地方。
很多的时候，我们都需要从大量数据中提取出有用的信息，从大规模数据中寻找物品间的隐含关系叫做关联分析(association analysis)，或者关联规则学习(association rule learning)。比如，在平时的购物中，哪些商品一起捆绑购买销量会比较好，又比如购物商城中的那些推荐信息，都是根据用户平时的搜索或者是购买情况来生成的。如果是暴力搜索的话代价太高了，所以Apriori就出现了，就是为了解决这类问题的。
关联分析
关联分析，顾名思义的就可以联想到，所谓关联，就是两个东西之间存在的某种联系
概念
项与项集：设 $I$ = {item$_1$, item$_2$, …, item$_m$} 是所有项的集合，其中，item$_k$ (k=1, 2, …, m) 称为 项。项的集合称为项集（itemset），包含k个项的项集称为k项集 (k-itemset)
关联规则：关联规则是形如$A\Rightarrow B$的蕴涵式
支持度（support）
数据集中包含该项集的记录所占的比例
$$
support(X, Y) = P(X, Y) = \frac{number(X, Y)}{number(all\ sample)}
$$置信度（confidence）
置信度体现了一个数据出现后，另一个数据出现的概率，或者说数据的条件概率
$$
confidence(X \Rightarrow Y) = P(Y | X) = \frac{P(X,Y)}{P(X)} =\frac{number(X,Y)}{number(X)}
$$
注意，支持度 / 前件（即$X$）的支持度
频繁集（frequent set）
表示经常一起出现的特征有哪些
- “经常”：支持度 > 最小支持率
关联规则 (association rule)
表示频繁项集中特征之间是否存在关联
- 比如出现p，则出现q的概率有多大
- 当设置最小置信度之后，“存在关联”：置信度 > 最小置信度
关联分析的目的
- 发现频繁项集
- 发现关联规则
首先我们要找到频繁项集，然后根据频繁项集找出关联规则
例子
| Number | Item |
|---|---|
| 1 | p, q, r |
| 2 | q |
| 3 | r, s |
| 4 | p, s, t |
| 5 | p, q, r |
$$
S(p) =\frac{3}{5}
$$
$$
S(q,p) = \frac{2}{5}
$$
$$
C(p\rightarrow q) = \frac{S(p,q)}{S{(p)}}=\frac{\frac{2}{5}}{\frac{3}{5}}=\frac{2}{3}
$$
Apriori算法原理
Apriori是什么
Apriori算法是经典的挖掘频繁项集和关联规则的数据挖掘算法
A priori在拉丁语中指”来自以前”。当定义问题时，通常会使用先验知识或者假设，这被称作”一个先验”（a priori）
Apriori算法的名字正是基于这样的事实：算法使用频繁项集性质的先验性质，即频繁项集的所有非空子集也一定是频繁的。Apriori算法使用一种称为逐层搜索、自底向上的迭代方法
适用范围
- 优点：易编码实现
- 缺点：在大数据集上可能较慢
- 适合数据类型：数值型或者标称型数据
步骤
通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；
- 找出频繁1-项集，记为L1；
- 利用L1来产生候选项集C2，对C2中的项进行判定挖掘出L2，即频繁2-项集；
- 不断如此循环下去，直到无法发现更多的频繁k-项集为止。
利用频繁项集，构造出满足用户最小信任度的规则
注意：每挖掘一层Lk就需要扫描整个数据库一遍。
例子
设：数据库D，其中有4个事务记录
最小支持度minSupport = 2
步骤：
扫描D，对每个候选项进行支持度计数得到表C1
比较候选项支持度计数与最小支持度minSupport，产生1-项集 L1
由L1产生候选项集C2
扫描D，对每个候选项集进行支持度计数
比较候选项支持度计数与最小支持度minSupport，产生2-项集 L2
由L2产生候选项集C3
比较候选项支持度计数与最小支持度minSupport，产生3-项集 L3
由于L3中只有一个项集，无法再进行合并，算法终止