Apriori 算法
最近上课讲到这个啤酒尿布的问题，说实话，这个事情是在大一的时候看那个魔鬼经济学里面看到的一个故事，但是没有想到里面居然有这么复杂的算法知识。。。。长见识了
啤酒和尿布就是一个相关问题，那么我们如何在实际生活中发现这样的相关关系呢？这就需要我们去设置一些指标去筛选。
两个商品具有比较强的相关关系的时候具有以下两个特点，其一：这两个产品同时出现的概率比较高，第二：在A产品出现的情况下，B产品出现的概率也比较高。
这两个指标分别为：支持度和置信度（support rate and confidence rate） \(support\ \ rate(A=>B) = P(A\cap{B}) \\ confidence\ \ rate(A=>B) = P(B\ | \ A)\) 实际上如果我们就是先去计算support rate的时候，我们按照最笨蛋的方法去计算一个个情况出现的概率那么计算的困难程度会超乎我们的想象。 \(C^1_n + C^2_n + C^3_n + ··· + C^n_n = 2^n\) 这个问题是所有可能的组合，对于一个超市而言，这个数据是很难以想象的，那么我们如何去计算超市里面所有的可能的满足条件组合呢？那么问题就使用了Apriori算法。
先验定理
如果一个项集是频繁的，则它的所有子集都是频繁的。
Apriori就是利用k-1项频繁项集去计算k项频繁项集。计算过程中有两个比较重要的步骤分别为连接和剪枝。
连接过程：为了得到k+1项频繁项集，对k项中的前k-1项相同的进行合并。
剪枝过程：假设上一过程中得到的集合为C，那么C中的每一项的所有子集都应该在K项频繁项集中，若不在则删去。
然后再去将这个剪枝过的C去计算每一个的出现频率.得到K+1项频繁项集
改进
上说过程对于K项的遍历可以说是非常多次,因为C中的每一项都有好多个子集.
那么对于K项中每一项,去C中每一项计算(设为i项)是否为其子集,如果为子集,则count_K_1[i] += 1
最后遍历完之后去统计每一个C中的count_K_1 是否都为 K +1,如果不为,则删除该项.
- hash 可以对更大范围的商品类型进行划分。
- transaction reduction 在一组合中，没有出现，那么下一次中就可以删除了。
- partition 对数据库进行划分，可以利用并行进行计算可以增加计算效率
- simpling 对于部分进行抽样，然后在此基础上进行计算的话。
关联规则基于 t-检验
