1. 关联
关联, 指的是关联分析, 这里引用百度百科的定义.
关联分析又称关联挖掘，就是在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。
通过关联分析, 可以挖掘出"由于某些事件的发生而引起另外一些事件的发生"之类的规则, 比如说"面包=>牛奶", 其中面包被称为规则的前项, 而牛奶则被称为规则的后项.
常用于关联分析的算法有Apriori算法, FP-growth算法, Eclat算法, 灰色关联法等, 下面将着重介绍Apriori算法.
2. Apriori算法
在介绍Apriori算法之前, 我们先来了解几个概念:
1.事务: 一条交易记录称为一个事务
2.项: 交易中的每一个物品称为一个项
3.项集: 包含0个或多个项的集合
4.支持度计数: 项集在所有事务中出现的次数.
5.支持度: 支持度计数除于总的事务数.
6.频繁项集: 支持度大于等于某个阀值的项集.
关联规则的挖掘通常分为两步: 第一步, 找出所有的频繁项集; 第二步, 由频繁项集产生强关联规则. 而Apriori算法则是挖掘频繁项集的基本算法.
Apriori算法的过程大致可以描述为: 首先, 根据最小支持度扫描所有候选项集, 从而找出频繁1-项集的集合. 然后, 再使用频繁1-项集的集合找出频繁2-项集的集合, 如此下去, 直到不能找出频繁k-项集.
可以看到以上每个过程均需要扫描一次数据, 为了提高频繁项集逐层迭代产生的效率, 需要利用一条重要性质, 其称为先验性质:
先验性质: 频繁项集的所有非空子集也一定是频繁的.
当然, 非频繁项集的所有超集也一定是非频繁的.
将先验性质应用到Apriori算法中就是将之前的过程分为两大部分, 连接步和剪枝步.
连接步: 连接步的目的是产生候选项集.
剪枝步: 应用先验性质对候选项集进行筛选, 将不满足先验性质的候选项集剔除, 再进而根据最小支持度找出频繁项集, 这样可以有效缩短计算量.
关联分析的目标是找出强关联规则, 因此这里的关联规则是指强关联规则, 我们把满足最小支持度和最小置信度的规则称为强关联规则.
对于规则A=>B, 置信度的计算公式就是项集{A, B}的支持度计数除于项集{A}的支持度计数.
3. 优缺点
优点: 简单, 易理解, 对数据要求低
缺点: 容易产生过多的候选项集, I/O负载大.
