本文将讲解关联规则的相关概念、处理相关规则的一般算法、改进的大数据处理关联规则的Apriori算法以及进一步优化的PCY算法。
啤酒和尿布的故事已经广为人晓。很多年轻的父亲买尿布的时候会顺便为自己买一瓶啤酒。亚马逊通过用户购买数据，使用关联规则，使用大数据的处理手段得出了尿布和啤酒的关系。
除了啤酒和尿布，现实生活中存在很多类似的关联关系，一般归纳为：
A事件发生，B事件很可能也会发生。
注意这里存在“很可能”这个概率问题。也就是说A事件发生，B事件是有可能不发生的。正如顾客买了尿布之后有可能不买啤酒。那就下来就是如何寻找这样的关系，也就是怎么知道尿布和啤酒存在这样的关系。所有的处理和分析都是建立在大量的用户购买数据的基础之上。为了讲解物品或者事物之间的关联规则，需要认识三个概念。
下面是用户的购买历史记录，只列出了5条。
1、 Bread, Coke, Milk
2、 Beer, Bread
3 、Beer, Coke, Diaper, Milk
4 、Beer, Bread, Diaper, Milk
5 、Coke, Diaper, Milk
、、、
如果总共有n条用户购买记录，每一条购买记录中的物品都不会重复出现，m（item）表示某物品存在的次数，那么：
1 支持度suport = m（item）/n；
可以理解为支持度就是某物品的出现次数占所有记录条数的比例。比例越高表示该物品被购买的次数越多。比如上面的历史记录中，n = 5， m（Beer） = 3， 所以Beer的支持度为3/5.
2 自信度confidence：A事件出现的次数为m1， A和B事件同时出现的次数为m2， 那么A事件发生之后，B事件也有可能发生的自信度为：m2/m1。
如果自信度越高，表示两者的关联性越强。也就是A事件发生，B事件也很可能也会发生。
单单的找到不同物品或者事物之间的关联度是不够的，因为生活中太多的东西之间具有很强的关联性。比如鸡蛋和牛奶。也就是说很多东西的强关联性已经是一种常识，我们并不需要挖掘就可以知道。我们希望找到一些“不为人知”的隐藏着的关联关系，就像n年前的啤酒和尿布。所以，我们应该从中剔除掉那些“众所周知”的强关联关系。如何剔除呢？就是下面将要讲到的概念。
兴趣度interest：关联规则有 A -> B, 表示A事件发生，B事件也发生的情况。它们的自信度为c， B事件的支持度为s，那么B事件的兴趣度为（c - s）.
可以看出，B相对于A的自信度很高，表示两者的关联性很强，s很低，表示产品B在购物清单中不常见，也就是字形度和支持度相差越大，insterest的值就越大。A和B之间的关联性很可能就是我们所感兴趣的。如果A表示牛奶，B表示面包，那么他们的自信度c会很大，B的s也很大，所以（c-s）的值相差不大，因此就不会是我们所感兴趣的了。
举一个栗子：
B1 = {m, c, b} B2 = {m, p, j}
B3 = {m, b} B4 = {c, j}
B5 = {m, p, b} B6 = {m, c, b, j}
B7 = {c, b, j} B8 = {b, c}
设置两个阈值：支持度阈值为s = 3， 自信度阈值为c = 0.75
那么频繁的item为 {b,m} {b,c} {c,m} {c,j} {m,c,b}
相关关联规则下的自信度为：
b→m: c=4/6
b→c: c=5/6
m→b: c=4/5
b→c,m: c=3/6
、、、
从而可以从中剔除不符合条件的item。
现在我们已经知道如何通过计算事物的兴趣度来确定某些事物的关联性。计算机所要做的工作是遍历和统计，同时还需要对不同的项进行组合，组合之后再遍历和统计，最后得到不同的项在各种组合下的自信度和支持度。对于组合问题，如果两两一组，n个物品就会有n*(n-1)/2种组合。如果n等于10亿，每一项用一个整数表示，那么组合之后需要的内存为1.8* 10^9 Gb，单台计算机是无法容纳的。
上面这张图片表示的是不同项之间的组合。
下面有两种最原始的方法，用来计算和保存两个不同项之间同时出现的次数。
第一种是使用二维数组表示，其中横坐标和纵坐标一样，因为是对称的，所以可以只取上三角或者下三角。
第二种方法是三字段组合的方式，（item1， item2， count），这样的话当两个项之间的count为0的时候就可以不用表示出来。一个三字段组合所需要的空间为12byte（使用整型）。
第二种方法比第一种方法的优越性在于当不同项之间的关联性很少时，也就是很多项之间同时出现的数量为0时，使用第二种方法就无需申请过多的空间来存储他们之间同时出现的次数。如果项之间关联性很强，那么第一种方法就比第二种方法好一点，因为它保存一个统计数只需要4byte的空间。
上面两种方法都存在单台机器内存不够用的问题。下面是改进的算法。
Apriori算法
Apriori算法的思想很简单，那就是，如果某个项不是频繁项，那么所有包含它的项都不是频繁项。什么意思？举一个栗子：比如{A}, {A, B}, 如果{A}的支持度为0.4， 那么{A, B}的支持度不可能大于0.4.所以，如果A不是频繁项，那么{A，B}这两个元素所构成的项也不是频繁项。
如上面图片所示，如果项AB不是频繁项，那么所有包含它的项都不是频繁项，如上图红色虚线所示。
相反，只有上一级是频繁项的情况下，下一级的项才有可能是频繁项。如上面图片虚线部分所示。
Apriori算法根据这一点，避免计算所有包含非频繁项的项集。所有的工作只是在子集为频繁项中进行。
下面是Apriori算法的具体伪代码：
假设有一个购物清单，分别是{A, B, C}, 那么k = 1表示只有一个商品的项，也叫项的大小为1（个人定义的，目的是便于说明），k=2表示两两组合的项，也叫项的大小为2，依次类推。其中Ck表示项的大小为k的待选项，Lk表示项的大小为k的频繁项。需要注意，此处的待选项中有可能不是频繁项。
1. k = 1, C1 = 所有的项
2. While C1 不为空
3. 扫描找到所有大小为Ck的项，如果Ck是频繁项，就将它加入Lk中。
4. 使用Lk中的项产生新的待选项Ck+1。
5. k = k + 1;
详细的计算过程如上图所示。当前的所有项都是上一步的频繁项的组合。
相比于前面的普通算法，Apriori算法能够根据前面的计算大量减少了内存空间的消耗。但是它不是很完善的。如果当k = 1的时候，如上图所示的C1，如果此步骤所产生的频繁项集C1很多，假设为m个，那么当k = 2的时候的C2的个数会是m(m-1)/2个。很可能会撑爆内存。
上面图片指的是使用Apriori算法计算的时候项的个数。开始的时候，也就是k = 1的时候项的个数为820， 到第二步也就是k = 2的时候项的个数约等于820*(820-1)/2。当k>2的时候，项的个数就很少。所以，我们应该研究，寻找一种方法，避免第二步可能撑爆内存的问题。这也是接下来将要讲到的PCV算法。
PCV算法
PCV算法是三个人名字的第一个字母。它是在Apriori算法的基础之上进行的。它使用到了bitmap。为了顺利讲解，先讲一讲什么是bitmap。
在计算机中数字是以二进制的形式存储和运算的。在32为系统中，一个整型数字可以存储成32位的二进制数，如下图所示：
上面图片所示的二进制数转换为十进制数为3. 每一个位置的数只能是0或者1。一个整型的二进制长度为32。bitmap这种数据结构利用了计算机这样的数据存储形式。具体怎么做呢？如果一个bitmap的长度为32，也就是上图的长度。下标表示具体的数字，对应下标的值，0表示不存在，1表示存在.
上图中下标为31、30和28所对应的值都为1，所以该bitmap表示整数31、30和28是存在的，0到27和29这些整数都不存在。
如果bitmap的长度超过32呢，比如需要表示36个数，那么就使用两个整型的空间。如上图所示，数字32在第二个整数的最右边被表示出来了。
总结一下：bitmap中，数组的下标表示的是具体的数字，该下标下所对应的值为0或者1，0表示不存在，1表示存在。
下面简单讲一下hash函数。
简单地理解哈希函数就是输入不同的哈希文本，能够得到等长的字符串或者数字。一般情况下，不同的输入所对应的输出是不一样的，但是也不是百分之百。其中（y = x mod n）就是最简单的哈希函数。
把哈希函数应用到本文所讲的PCY算法中，就是不同的项经过哈希计算会得到一个整数，这个整数就是bitmap的下标（index）值。然后把该下标所对应的值由0变成1。但是，不同的项通过哈希算法所得到的下标可能是一样的，这叫bitmap的冲突，如果出现这种情况，就无法辨别出到底是哪个项改变bitmap的了。pcy算法考虑到了这个因素。除此之外，我们还需要计数的变量，计数的变量个数等于bitmap的长度，也就是需要统计每一个bitmap位变为1出现的次数。即使存在冲突的情况，也照样让计数变量加1.
比如『A，B，C』三个项，如果A和B项通过哈希函数的下标都为1，那么统计的数就是2。
所以，bitmap有多长就需要多少个统计变量。如果原始购买清单中有2.5亿个项，那么我们来计算一下存放这么多个统计变量和bitmap需要多大的内存空间：
一个只有2Gb的空间完全可以存放2.5亿个整数以及长度为2.5亿d的bitmap。因为：
一个整型4字节，那么1G的内存可以存放2.5x10^8个整数，也就是2.5亿一个整数，具体计算为：
1Gb = 1000Mb = 1000 000Kb = 1000 000 000 Byte = 4 * 2.5x10^8(2.5x10^8个整数)
一个长度为2.5亿的bitmap，只需要内存3.125Mb，具体计算为：
250 000 000 bit = 250 000 000/8 byte = 3.125 x 10^4 Kb = 31.25 Mb.
可以看出，bitmap所需要的内存空间是很少很少的。
所以，PCY思路：
1. 当k = 1的时候，也就是每一个项中只有一个物品，有10亿个项，表示为C1。统计出10亿个项的个数，排除掉非频繁的项。
2. 使用嵌套的两个for循环，遍历第1步所得到的频繁项，两两组合，得到C2。分别把C2用过哈希函数得到bitmap的下标，把该下标下的bitmap的值置为1，同时计数。这里把每一个下标表示为一个桶。
3. 过滤掉个数小于阈值的桶，得到的便是k = 2的时候的频繁项。
4. 重复进行下去，直到上一步结果中的频繁项为0.
从上面的算法可以看出，需要存储的只是bitmap和统计的变量。所以，PCY方法就不存在内存撑爆的问题。
上面是Apriori算法和PCY算法的运算对比图。注意到红色圈出来的地方，在C2 的时候，使用PCY算法不需要存储那么多个项。所以，在计算时间上面就比Apriori算法有优势。
再次改进
我们发现，PCY算法中的哈希函数的结果是存在有冲突问题的。也就是说如果三个不同的项通过哈希函数都映射到了相同的bitmap下标上。他们总的统计数不小于阈值，那么PCY算法就把他们都当成了频繁项进入下一轮的计算环节。而事实上，他们三者中可能不全都是频繁项。我们希望能够改进这一点。
在PCY算法中我们引进了一个bitmap和相应的统计变量，同时哈希函数表示为hash1. 相同的，我们也可以使用两个bitmap以及他们对应的统计变量，但是，哈希函数不相同。
遍历所有的项，分别把他们哈希到不同的bitmap上面。最后的频繁项便是在两个bitmap中的统计数都大于阈值的项。
这里的关键点是两个哈希函数是不一样的，那么相同的输入通过不同的哈希函数所得到的结果基本上是不一样的，也就是bitmap的下标不一样。
完结！ 转载请标明出处，感谢！
参考论文：
R. Agrawal, R. Srikant: “Fast Algorithms for Mining Association Rules”, Proc. of the 20th Int’l Conference on Very Large Databases , 1994.
Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami:Mining Association Rules between Sets of Items in Large Databases. SIGMOD Conference 1993: 207-216
参考书籍：
http://www.mmds.org/