关联规则挖掘

这里的规则并不是放之四海而皆准的，而是这规则能满足大多数的情况，我们可以发现分类更侧重于科学研究，而这里规则已经显示出其商业价值。

下面我们用大家都熟悉的啤酒和尿布来说明问题，那{啤酒} ->{尿布}这条规律是怎么发现的呢

transaction表：事务表，表示每位顾客买的东西，比如甲顾客买了A,B，乙顾客买了B,D

candidate表：候选表，表示可能的食物组合，比如超市一共有100件商品，我们可以发现这个组合数是2^100

那我们的规则是这样的，集合A->集合B。因为我们的规则满足两条件，一是规则能适用于一定的范围，而是规则能有一定的准确性。

为了满足第一点，我们引进了Frequent Itermst频繁项集，即频率非常高的集合。那判断是否为频繁项集的标准自然是出现次数比较多，因此我们引入了Support Count支持计数。我们会发现支持计数是绝对的概念，而有时我们需要相对的概念，因此引入Support支持度，这个就更能说明问题了。而针对第二个条件，我们引入一定义Confident置信度，只要我们的Support大于某一阈值，置信度大于某一阈值，那就把它设为规则。

那我们会怎么做？最简单的办法是，把candidate表的每种组合去transaction表里面找，若其Support大于某一阈值，就提取出来。可行，但代价难以承受，我们知道，这个复杂度是O(Count(Candinate) * Count(transaction) * O(查找))。下面从各个角度来优化算法。

Apriori算法很好地减少Count(Candinate)，Apriori算法其实也来自一个很朴素的想法，那就是集合A是集合B的子集，如果集合B的Support都小于这个阈值，那么就集合A也肯定不满足条件，就不做考虑，因此，候选键大大减少了。

Hash储存transaction表，增加查找效率。一般情况下，我们是从候选表中选一个，再transaction表里面找，我们可以反一下，在transaction表里找一个，比如顾客买了标号为1,2,3,5,6的食品，那我们可以通过hash表找到所有三元的candidate，然后让这些计数加1，依次遍历。

未完待续。

每种算法都来自朴素的想法，而这些想法都是通过动手做实验发现的。