数据挖掘|关联规则Apriori算法

01

—

关联规则挖掘背景和基本概念

如下所示的数据集，表中的每一行代表一次购买清单，注意我们只关心记录出现与否，不关心某条记录购买了几次，如购买十盒牛奶也只计一次。

数据记录的所有项的集合称为总项集，上表中的总项集：

S={牛奶,面包,尿布,啤酒,鸡蛋,可乐}

关联规则

就是有关联的规则，形式是这样定义的：两个不相交的非空集合X、Y，如果有

X->Y，就说X-->Y是一条关联规则，例如，{啤酒}-->{尿布}就是一条关联规则。

关联规则的强度用支持度(support)和自信度(confidence)来描述。

支持度

support(X-->Y) = 集合X与集合Y中的项在一条记录中同时出现的次数 / 数据记录的个数。例如：support({啤酒}-->{尿布}) = 啤酒和尿布同时出现的次数 / 数据记录数 = 3/5=60%

自信度

confidence(X-->Y) = 集合X与集合Y中的项在一条记录中同时出现的次数 / 集合X出现的个数 。例如：confidence({尿布}-->{啤酒}) = 啤酒和尿布同时出现的次数 / 尿布出现的次数 = 3/4 = 75%。

总结

支持度和自信度越高，说明规则越强，关联规则挖掘就是挖掘出满足一定强度的规则。

02

—

关联规则挖掘的之穷举算法

关联规则挖掘

给定一个交易数据集T，找出其中所有支持度 support >= min_support、自信度confidence >= min_confidence的关联规则。

穷举算法

找出所需要的规则就是穷举项集的所有组合，并测试每个组合是否满足条件，一个元素个数为n的项集所需要的时间复杂度为O(2^N)。上表的总项集 S={牛奶,面包,尿布,啤酒,鸡蛋,可乐}，元素的个数为6，所有的组合个数为63 。

为了简单起见，已知一个商品编号的总项集为：{1, 2, 3}，那么所有可能的组合为：

{1},{2} {1},{3} {2},{3} {1},{2,3} {2},{1,3} {3},{1,2} {1,2,3}

共有7项（2^3 - 1），分别检查以上各种组合，在每一种组合上找出满足支持度和自信度要求的关联规则。

对于普通的超市，其商品的项集数也在1万以上，用指数时间复杂度的算法不能在可接受的时间内解决问题。

怎样快速挖出满足条件的关联规则是关联挖掘的需要解决的主要问题。

03

—

关联规则挖掘优化算法之Apriori算法

关联规则挖掘分两步进行：

　　1）生成频繁项集

这一阶段找出所有满足最小支持度的项集，找出的这些项集称为频繁项集。

　　2）生成规则

　　在上一步产生的频繁项集的基础上生成满足最小自信度的规则，产生的规则称为强规则。

关联规则挖掘所花费的时间主要是在第一步：生成频繁项集上。因为找出的频繁项集往往不会很多，所以2）相对1）耗时少。

为了减少 1）：频繁项集的生成时间，应该尽早的消除一些完全不可能是频繁项集的集合，Apriori算法主要通过两个规律减少频繁项集。

两个定律

1. 高级到低级。如果一个集合是频繁项集，则它的所有子集都是频繁项集。假设一个集合{A,B}是频繁项集，则它的子集{A}, {B} 都是频繁项集。
2. 低级到高级。如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。假设集合{A}不是频繁项集，则它的任何超集如{A,B}，{A,B,C}必定也不是频繁项集。

具有实际应用价值的还是第2条，从低级的频繁项集到高级的频繁项集的演化，试想，如果二级项集 {A,B}支持度都没有大于阈值，即不是频繁项集，三级{A,C,B}或更高级怎么可能是频繁项集呢？如果是的话，{A,B}就一定是频繁项集了，这不和原来的条件矛盾了吗？

首先统计一级候选项集，清除不满足条件的候选集，得到满足条件的一级项集，在生成一级项集的基础上，生成二级项集，得到满足条件的二级项集，在生成三级项集时，再次根据定律2的思想，如，{牛奶,啤酒}不是频繁项集，所以{牛奶，啤酒，尿布}，{牛奶，啤酒，面包}都不是频繁项集。

Apriori算法

属于候选消除算法，是一个根据定律2生成候选集、根据支持度和可信度的预置消除不满足条件的候选集，并不断循环直到不再产生候选集的过程。

算法的伪代码：

public void Apriori() { // 获取原始数据记录 record = getRecord(); // 获取第一次的候选集 List<List<String>> candidateItemset = findFirstCandidate(); // 获取候选集candidateItemset 满足支持的集合 List<List<String>> lItemset = getSupportedItemset(candidateItemset ); // 只要能继续挖掘 while (endTag != true) { // 获取下一次的候选集 List<List<String>> ckItemset = getNextCandidate(lItemset); // 获取候选集ckItemset 满足支持的集合 List<List<String>> lkItemset = getSupportedItemset(ckItemset); //得到这一级别的频繁项集 save(IkItemset) // 保存数据，为下次迭代准备 lItemset = lkItemset; }

总结了关联规则挖掘的经典算法Apriori算法，这个算法利用了一个定律：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集，自下而上，挖掘出满足支持度和可信度阈值的所有级别的频繁项集。