上一篇简单介绍了关联规则的基本概念，继续这个部分，这篇来说一些稍微优化的算法，最后以“挖掘”我们的文具系统为例收尾。
上篇的“啤酒尿布”事件中，我们如果要算频繁三项集，使用的是“蛮力法”，即产生C(6,3) ＝20个 所有的三项集，再每个去判断它是不是频繁的。但数据集的项只有6个时，这不算什么，假设有400个时，如果要把全部三项集都算出来，那么要计算C(400,3) = 10586800 个，然后再去查每个是否是频繁的。有没有更快的方法，减少这么大的计算量？
在上一个例子中，我们可以发现，鸡蛋在5个事务中，只出现了一次，而包含了鸡蛋的所有三项集的支持度计数都不会超过1，如果按上一篇，我们要求支持度为0.4，也就是要求在5个事务中，至少出现2次，所以这就意味着“所有包含了鸡蛋的三项集必然不符合要求”。这就意味着，我们可以先计算“频繁1项集”，对于不符合条件的1项集就直接减掉，不再在它的基础上产生3项集了。这样就大大减少了最后产生项集的个数。
这个就是先验原理啦：
如果一个项是，频繁的，则它的所有子集也一定是频繁的。相反，如果一个项集{a,b}是非频繁的，则它的所有超集也一定是非频繁的。
Apriori算法中计算支持度计数，即是基于这个原理进行的剪枝：初始，每个项都被看作候选1项集。对它们的支持度计数后，候选项集的{鸡蛋}被丢弃，因为它的出现少于2个。在下一次迭代，仅使用频繁1项集来产生候选的2项集，因为先验原理保证所有的非频繁1项集的超级都是非频繁的。
再进一步，如何产生频繁3项集？有几种方法，这里只介绍F(k-1) * F1 的方法，它最容易理解。以产生频繁3项集为例，先产生频繁1项集，然后使用F1 * F1 （交叉相乘扩展）的方法产生频繁2项“候选集”，通过这层过滤，得到频繁2项集F2，然后使用F2 * F1的方法来产生频繁3项“候选集”，再过滤产生F3，这样就产生了频繁3项集。这种方法不但每次过滤可以减掉很多不符合条件的分支，而且可以保证产生的频繁3项集是完全的，不会拉掉。因为每一个频繁k项集都是由一个频繁k-1项集和一个频繁1项集组成的。因此，所有产生的频繁k项集是这种方法所产生的候选k项集的一部分。
好，这一步产生了频繁3项集，而上一篇介绍了，产生关联规则要两步，1，产生频繁项集，2，根据置信度条件产生规则。
假设现在产生的频繁3项集是{a,b,c}，那么由它产生的规则可能由pow(2, k) -2 = pow(2, 3) – 2= 6 个，我们可以把这6个都列出来，例如 {a, b} -> c ，然后每个根据上一篇提到的计算置信度的方法判断它的置信度是否符合条件。同样，3个还好，全部列出来也才6个，4个时就是14个，有没有更快的方法？
Apriori的置信度剪枝基于这样的定理：
如果规则 x -> y – x 不满足置信度阈值，则形如 x’ -> y – x’ 的规则也一定不满足置信度阈值，其中x’是x的子集。
举个例子就明白了，定理永远那么拗口。以 {a, b, c, d｝是个频繁4项集为例，如果{b c d} -> {a} 这条规则具有低置信度（即不符合置信度规定的阈值），（我们暂称{b c d}为前件，{a}为后件），则可以丢弃后件包含a的所有规则，包括{cd}->{ab}，{bd} -> {ac}，{bc} -> {ad} 和 {d} -> {abc}。
明白了吧，基于两种剪枝（支持度剪枝和置信度剪枝）我们大大减少了计算量，得到了最后的规则。
来实践下，接下来这个例子是我们内部的文具订购系统的数据，感谢陈总导数据出来给我～ haha ～
我们的文具订购系统从导出的数据上看，文具类型有将近400种（ps：我们每次订购的时候没有400种啊，可能是一些历史文具添加重复了，jiong～），导出的订购数据是从08年10月到10年10月左右，以每个人一次订购n个文具为一个事务的话，有将近8000个事务。
先算一个，频繁2项集规则，把支持度设置为0.001（因为事务本身就有8000个了，所以0.001相当于要出现8次，置信度设置为0.4）这两个参数调的比较低，主要是为了多产生一些：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 Concalate Support 签字笔 啫喱笔 ==> 0.00543066430917 透明胶 透明胶座 ==> 0.00101035615054 裁纸刀 签字笔 ==> 0.00101035615054 啫喱笔 笔记本 ==> 0.00151553422581 回形针 回形针盒 ==> 0.001389239707 双头小记号笔 荧光笔 ==> 0.00101035615054 笔记本 拍纸本 ==> 0.00101035615054 笔记本 橡皮 ==> 0.00113665066936 签字笔 裁纸刀 ==> 0.001389239707 签字笔 固体胶 ==> 0.00113665066936 圆珠笔 签字笔 ==> 0.00239959585754 啫喱笔 手写标签 ==> 0.00113665066936 透明胶 啫喱笔 ==> 0.00252589037636 啫喱笔 笔刨 ==> 0.00113665066936 单页文件套 钮扣文件袋 ==> 0.00113665066936 网易logo报事贴 网易logo报事贴 ==> 0.0035362465269 啫喱笔 杂志筐 ==> 0.00126294518818 签字笔 双面胶 ==> 0.00113665066936 订书针 订书机 ==> 0.00290477393281 圆珠笔 笔记本 ==> 0.00101035615054 订书机 订书针 ==> 0.00126294518818 啫喱笔 固体胶 ==> 0.00113665066936 啫喱笔 自动铅笔 ==> 0.00151553422581 笔记本 透明胶 ==> 0.00101035615054 啫喱笔 钮扣文件袋 ==> 0.00113665066936 多用途笔筒 剪刀 ==> 0.00101035615054 铅笔 笔刨 ==> 0.00202071230109 白板笔 啫喱笔 ==> 0.00113665066936 圆珠笔 透明胶 ==> 0.00126294518818 透明胶 荧光笔 ==> 0.00101035615054 笔刨 橡皮 ==> 0.00126294518818 啫喱笔 橡皮 ==> 0.00164182874463 拉链文件袋 拉链文件袋 ==> 0.00126294518818 啫喱笔 网易logo报事贴 ==> 0.00113665066936 笔记本 啫喱笔 ==> 0.00101035615054 双头小记号笔 双头大记号笔 ==> 0.00113665066936 签字笔 无线装订本 ==> 0.00101035615054 裁纸刀 啫喱笔 ==> 0.00101035615054 签字笔 拍纸本 ==> 0.00113665066936 签字笔 圆珠笔 ==> 0.001389239707 双头小记号笔 手写标签 ==> 0.00101035615054 签字笔 报事贴 ==> 0.00126294518818 啫喱笔 双面胶 ==> 0.00239959585754 封箱胶 透明胶 ==> 0.00126294518818 封箱胶 剪刀 ==> 0.00126294518818 笔记本 自动铅笔 ==> 0.00164182874463 签字笔 自动铅笔 ==> 0.00126294518818 双头小记号笔 啫喱笔 ==> 0.00239959585754 啫喱笔 拍纸本 ==> 0.00164182874463 铅笔 橡皮 ==> 0.00189441778227 拉链文件袋 笔记本 ==> 0.00101035615054 啫喱笔 报事贴 ==> 0.00101035615054 单页文件套 啫喱笔 ==> 0.00101035615054 双头小记号笔 签字笔 ==> 0.00126294518818 笔记本 荧光笔 ==> 0.00126294518818 双头小记号笔 笔记本 ==> 0.00113665066936 多用途笔筒 啫喱笔 ==> 0.00113665066936 啫喱笔 透明胶 ==> 0.00227330133872 自动铅笔 橡皮 ==> 0.00151553422581 啫喱笔 海绵双面胶 ==> 0.00126294518818 裁纸刀 剪刀 ==> 0.00101035615054 签字笔 封箱胶 ==> 0.001389239707 笔记本 钮扣文件袋 ==> 0.00101035615054 双头小记号笔 拍纸本 ==> 0.00113665066936 啫喱笔 自动铅笔芯 ==> 0.00151553422581 自动铅笔 拍纸本 ==> 0.00101035615054 啫喱笔 铅笔 ==> 0.00164182874463 签字笔 荧光笔 ==> 0.00189441778227 啫喱笔 直尺 ==> 0.00101035615054 回形针 啫喱笔 ==> 0.00126294518818 笔记本 铅笔 ==> 0.00101035615054 网易logo普通便条纸 网易logo报事贴 ==> 0.00340995200808 签字笔 透明胶 ==> 0.00227330133872 笔记本 报事贴 ==> 0.00126294518818 啫喱笔 啫喱笔 ==> 0.00113665066936 双面胶 固体胶 ==> 0.00126294518818 双头大记号笔 啫喱笔 ==> 0.00189441778227 钮扣文件袋 拉链文件袋 ==> 0.00164182874463 签字笔 橡皮 ==> 0.001389239707 圆珠笔 双头小记号笔 ==> 0.00101035615054 啫喱笔 双头大记号笔 ==> 0.001389239707 封箱胶 啫喱笔 ==> 0.00164182874463 订书针 啫喱笔 ==> 0.00113665066936 笔记本 自动铅笔芯 ==> 0.00151553422581 封箱胶 钮扣文件袋 ==> 0.00101035615054 自动铅笔 自动铅笔芯 ==> 0.00227330133872 笔记本 笔记本 ==> 0.00113665066936 反尾夹 钮扣文件袋 ==> 0.00113665066936 签字笔 自动铅笔芯 ==> 0.00126294518818 签字笔 双螺笔记本 ==> 0.00151553422581 裁纸刀 封箱胶 ==> 0.00176812326345 笔记本 剪刀 ==> 0.00101035615054 圆珠笔 啫喱笔 ==> 0.00227330133872 双螺笔记本 圆珠笔 ==> 0.00101035615054 啫喱笔 网易logo普通便条纸 ==> 0.00126294518818 啫喱笔 荧光笔 ==> 0.00315736297045 剪刀 裁纸刀 ==> 0.00101035615054 签字笔 笔记本 ==> 0.00101035615054 报事贴 啫喱笔 ==> 0.00113665066936 自动铅笔芯 橡皮 ==> 0.00176812326345 回形针 固体胶 ==> 0.00113665066936 啫喱笔 封箱胶 ==> 0.00164182874463 双头小记号笔 剪刀 ==> 0.00151553422581 签字笔 剪刀 ==> 0.00113665066936 啫喱笔 剪刀 ==> 0.00265218489518 直尺 剪刀 ==> 0.00113665066936 荧光笔 固体胶 ==> 0.00101035615054 透明胶 双面胶 ==> 0.00202071230109 拉链文件袋 钮扣文件袋 ==> 0.00164182874463 笔记本 杂志筐 ==> 0.00101035615054 透明胶 固体胶 ==> 0.00113665066936 签字笔 直尺 ==> 0.00101035615054 Concalate Confidence 71 订书机 ==> 72 订书针 [Conf :0.741935483871 ]72 订书针 ==> 71 订书机 [Conf :0.560975609756 ]357 网易logo报事贴 ==> 356 网易logo报事贴 [Conf :0.736842105263 ]356 网易logo报事贴 ==> 357 网易logo报事贴 [Conf :0.8 ]356 网易logo报事贴 ==> 355 网易logo普通便条纸 [Conf :0.8 ]355 网易logo普通便条纸 ==> 356 网易logo报事贴 [Conf :0.8 ]264 笔记本 ==> 280 签字笔 [Conf :0.5 ]38 笔刨 ==> 35 铅笔 [Conf :0.551724137931 ]57 回形针盒 ==> 56 回形针 [Conf :0.6875 ]37 自动铅笔芯 ==> 36 自动铅笔 [Conf :0.758620689655 ]36 自动铅笔 ==> 37 自动铅笔芯 [Conf :0.709677419355 ]65 裁纸刀 ==> 63 剪刀 [Conf :0.408163265306 ]357 网易logo报事贴 ==> 355 网易logo普通便条纸 [Conf :0.710526315789 ]355 网易logo普通便条纸 ==> 357 网易logo报事贴 [Conf :0.771428571429 ]287 自动铅笔芯 ==> 286 自动铅笔 [Conf :0.642857142857 ]286 自动铅笔 ==> 287 自动铅笔芯 [Conf :0.75 ]324 订书针 ==> 323 订书机 [Conf :0.5 ]323 订书机 ==> 324 订书针 [Conf :0.588235294118 ]34 双头大记号笔 ==> 43 啫喱笔 [Conf :0.428571428571 ]59 透明胶座 ==> 58 透明胶 [Conf :0.727272727273 ]38 笔刨 ==> 43 啫喱笔 [Conf :0.413793103448 ]
上面有两个部分，第一个部分是计算支持度，第二个部分是计算置信度，因为文具很多是重名的，为了区分，在它们前面加了文具的id，从产生的规则上看，还是能看出来一些有意思的，比如前两个，买了钉书机的用户有74% 的概率去买订书针，而反过来，买了订书针的用户只有56%的概率买钉书机。这也符合我们的习惯：如果第一次买钉书机很有会买订书针，而当我们的订书针用完时，因为我们已经有订书机了，所以可能只需要购买订数针即可。
再post一个频繁3项集规则的，支持度阈值同样为0.001，置信度规则为0.4：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 Concalate Support 笔记本 啫喱笔 啫喱笔 ==> 0.00101035615054 啫喱笔 啫喱笔 剪刀 ==> 0.00126294518818 圆珠笔 签字笔 啫喱笔 ==> 0.00101035615054 啫喱笔 自动铅笔 自动铅笔芯 ==> 0.001389239707 签字笔 透明胶 啫喱笔 ==> 0.00101035615054 啫喱笔 啫喱笔 双面胶 ==> 0.00113665066936 签字笔 啫喱笔 啫喱笔 ==> 0.00227330133872 网易logo普通便条纸 网易logo报事贴 网易logo报事贴 ==> 0.00303106845163 笔记本 自动铅笔 自动铅笔芯 ==> 0.001389239707 自动铅笔 自动铅笔芯 橡皮 ==> 0.00126294518818 啫喱笔 啫喱笔 透明胶 ==> 0.00151553422581 铅笔 笔刨 橡皮 ==> 0.00101035615054 啫喱笔 网易logo普通便条纸 网易logo报事贴 ==> 0.00113665066936 Concalate Confidence 43 啫喱笔 62 剪刀 ==> 42 啫喱笔 [Conf :0.47619047619 ]42 啫喱笔 62 剪刀 ==> 43 啫喱笔 [Conf :0.588235294118 ]42 啫喱笔 63 剪刀 ==> 43 啫喱笔 [Conf :0.47619047619 ]37 自动铅笔芯 39 橡皮 ==> 36 自动铅笔 [Conf :0.714285714286 ]36 自动铅笔 39 橡皮 ==> 37 自动铅笔芯 [Conf :0.833333333333 ]43 啫喱笔 60 双面胶 ==> 42 啫喱笔 [Conf :0.473684210526 ]42 啫喱笔 60 双面胶 ==> 43 啫喱笔 [Conf :0.818181818182 ]282 啫喱笔 356 网易logo报事贴 ==> 355 网易logo普通便条纸 [Conf :1.0 ]282 啫喱笔 355 网易logo普通便条纸 ==> 356 网易logo报事贴 [Conf :0.9 ]43 啫喱笔 37 自动铅笔芯 ==> 36 自动铅笔 [Conf :0.75 ]43 啫喱笔 36 自动铅笔 ==> 37 自动铅笔芯 [Conf :0.75 ]58 透明胶 43 啫喱笔 ==> 42 啫喱笔 [Conf :0.6 ]42 啫喱笔 58 透明胶 ==> 43 啫喱笔 [Conf :0.666666666667 ]3 笔记本 43 啫喱笔 ==> 42 啫喱笔 [Conf :0.461538461538 ]42 啫喱笔 3 笔记本 ==> 43 啫喱笔 [Conf :0.48 ]41 签字笔 43 啫喱笔 ==> 42 啫喱笔 [Conf :0.418604651163 ]41 签字笔 42 啫喱笔 ==> 43 啫喱笔 [Conf :0.5625 ]356 网易logo报事贴 357 网易logo报事贴 ==> 355 网易logo普通便条纸 [Conf :0.857142857143 ]355 网易logo普通便条纸 357 网易logo报事贴 ==> 356 网易logo报事贴 [Conf :0.888888888889 ]355 网易logo普通便条纸 356 网易logo报事贴 ==> 357 网易logo报事贴 [Conf :0.857142857143 ]357 网易logo报事贴 ==> 355 网易logo普通便条纸 356 网易logo报事贴 [Conf :0.631578947368 ]356 网易logo报事贴 ==> 355 网易logo普通便条纸 357 网易logo报事贴 [Conf :0.685714285714 ]355 网易logo普通便条纸 ==> 356 网易logo报事贴 357 网易logo报事贴 [Conf :0.685714285714 ]42 啫喱笔 37 自动铅笔芯 ==> 36 自动铅笔 [Conf :0.6875 ]42 啫喱笔 36 自动铅笔 ==> 37 自动铅笔芯 [Conf :0.733333333333 ]2 笔记本 37 自动铅笔芯 ==> 36 自动铅笔 [Conf :0.916666666667 ]2 笔记本 36 自动铅笔 ==> 37 自动铅笔芯 [Conf :0.846153846154 ]40 圆珠笔 42 啫喱笔 ==> 41 签字笔 [Conf :0.470588235294 ]40 圆珠笔 41 签字笔 ==> 42 啫喱笔 [Conf :0.421052631579 ]38 笔刨 39 橡皮 ==> 35 铅笔 [Conf :0.8 ]35 铅笔 39 橡皮 ==> 38 笔刨 [Conf :0.533333333333 ]35 铅笔 38 笔刨 ==> 39 橡皮 [Conf :0.5 ]58 透明胶 43 啫喱笔 ==> 41 签字笔 [Conf :0.4 ]41 签字笔 58 透明胶 ==> 43 啫喱笔 [Conf :0.444444444444 ]
这里同样可以发现有意思的规则，例如第5条，买了自动铅笔和橡皮的，有83%的概率会买自动铅笔芯。
总之利用这些规则，我们可以做些什么呢，当用户选了一个文具时，如果在我们的规则前件中，我们可以实时的把规则后件的文具的推荐给他，猜测他下一步有可能买的文具，这个听起来似乎还不错。^_^