数据挖掘算法基础-关联规则

数据挖掘中，被常拿来说的啤酒尿布的例子就是一个很典型的运用关联算法来做购物来分析的例子。常被用于交易数据、关系数据的分析，发现数据集中隐藏的频繁模式，这些频繁模式可以用关联规则的形式表示，有效的关联规则对商家的商品进出货摆放都有很大的指导意义。

设 是项的集合，数据集D是事务的集合，每项事务T是一个非空项集，且T是I的非空子集。每项事务都有一个唯一标识符，定义为TID，A和B均为事务T中的非空子集，并且A和B无交集。则规则 成立，支持度s是D中同时包含A和B的事务所占的百分比，置信度c是包含A的事务中包含B的事务的百分比。如下：

频繁模式中同时满足最小支持度阈值和最小置信度阈值的为强关联规则。

综上，关联规则挖掘主要分为两步：

1.      找出所有频繁项集。每个项集出现频次大于最小支持计数。

2.      由频繁项集得到强关联规则。这些规则同时满足最小支持度阈值和最小置信度阈值。

Apriori

Apriori先验算法，基于先验性质：频繁项集的所有非空子集也一定是频繁的。

针对水平数据{TID:item_set}

发现频繁集的过程

1.      扫描找出候选项集（初始扫描D得到候选项集 ）

2.      计算支持度计数，与最小支持度计数比较得到频繁项集

3.       自连接产生候选项集

4.      重复2-3的过程，直到得到最大频繁项集 。

由频繁项集得到强关联规则的过程

1.      对中每一项L，取其所有非空子集

2.      若对于L的某一非空子集S，若置信度大于最小支持度阈值

3.      则产生强规则：

以下截图为《数据挖掘：概念与技术》中第六章Apriori获取频繁集过程示例。

Apriori算法的缺陷：可能产生大量候选集，可能需要重复扫描整个数据库匹配检查一个很大的候选集合。空间时间的花费会很大。

FP-Growth

频繁模式树增长算法，产生FP数，由树递归推演得到频繁模式。

针对水平数据{TID:item_set}

发现频繁集的过程

1.      第一次扫描D，并对比最小支持度计数，取1项频繁集L

2.      1项频繁集L按支持度计数降序排列

3.      创建数的根节点，用null标记

4.      第二次扫描D，D中每一项事务中的想都按L中的次序处理，为每个事务创建一个分支

5.      结点不存在时，新建结点，结点计数赋值为1；结点已存在时，结点计数加1

6.      从频繁集L的最后一项开始，对其每一项找到所有含该项的分支路径。

7.      路径中的结点计数即为该路径下所有节点所组成的项集，在该分支的计数

8.      合并每一分支的项集，获取频繁集

以下截图为《数据挖掘：概念与技术》中第六章FP-Growth获取频繁集过程示例。

Eclat

等价类变换

垂直数据格式{item:TID_set}

发现频繁集的过程

1.      对每频繁项的TID集取交集

2.      重复上述过程直至没有更大频繁集

以下截图为《数据挖掘：概念与技术》中第六章Eclat获取频繁集过程示例。

判断规则的有效性

提升度：

Lift=1，A和B独立不相关，lift<1，A和B负相关，lift>1，A和B正相关。

相关性分析：

全置信度：

最大置信度：

Kulczynski(Kulc)：

余弦：

后面四项度量值取值范围都是0~1，并且值越大A和B的联系越紧密。