Apriori算法：使用候选项找频繁项集
Apriori算法是关联分析中一种基本算法，用于挖掘布尔关联规则频繁项集。原理：利用频繁项集的先验知识，使用逐层搜索的迭代方法，使用k项集探索(k+1)项集。这里先看哈二维Apriori算法。（一般数据库都是二维的嘛。。hehe）
Apriori性质：频繁项集的所有非空子集都必须也是频繁的。（一种反单调性质）
算法描述：
1、链接步：通过L<k-1>自连接产生候选k项集C<k>。
2、剪枝步：C<k>是L<k>的超集。利用Apriori性质，如果一个k项集的(k-1)项集不在L<k-1>中，则该k项集从C<k>中删除。（这种子集测试可以使用所有频繁项集的散列树快速完成）
上Pseudo Code：
Apriori输入：事务数据D；最小支持度阀值min_sup。输出：D中的频繁项集L。L<1> = find_frequent_1-itemset(D);For (k = 2; L<k-1> != empty; k++) { C<k> = apriori_gen(L<k-1>, min_sup); For each transaction t in D { C<t> = subset(C<k>, t); //找出t中是候选集的所有C<k>的子集 For each candidate c in C<t> c.count++; } L<k> = {c in C<k> | c.count >= min_sup}}Return L = set of L<k>Procedure apriori_gen(L<k-1>, min_sup) For each itemset l1 in L<k-1> For each itemset l2 in L<k-1> If (l1[i] = l2[1]) && (l1[2] = l2[2]) && … && (l1[k-2] = l2[k-2]) && (l1[k-1] < l2[k-1]) then { c = l1 * l2; //union if has_infrequent_subset(c, L<k-1>) then delete c; else add c to C<k>; } Return C<k>;Procedure has_infrequent_subset(c, L<k-1>) For each (k-1)-subset s of c If s not in L<k-1> thenReturn TRUE; Return FALSE;
由频繁项集产生关联规则：
Confidence(A => B) = P(A | B)
= support(AB) / support(B) = support_count(AB) / support_count(B)
对于前面Apriori找出的每个频繁项集l，产生l的非空子集；（记得Apriori性质哦)
对于每个非空子集s，如果 support_count(l) / support_count(s) >= min_conf，则输出“s => (l – s)”（为什么用support_count(l)不用(l-s)？）
提高Apriori的有效性？数据结构的改进，扫描次数的降低等。
1、散列项集计数，增加效率。
一个土一点的比喻：在Java里面用HashMap<Key, Val>来存。。还有种用trie树的，等我补习过Algorithms in C++再说。。
2、事务压缩：不包含k项集的事务不可能包含(k+1)项集。这样，可以给事务加删除标记，下次迭代不考虑之。
3、划分（Er。。不是等价类，是看程序设计的方便乱划，比如一次能装入内存多少就划多少）
两次扫描。第一次，将D中事务划分为n个非重叠部分，如果D中事务最小支持阀值为min_sup，则每个部分最小支持计数为(min_sup * 该部分事务数)。对每一部分，找出局部频繁项集。
局部频繁项集可能不是整个数据库D的频繁项集，但D的任何频繁项集必是局部频繁项集（WHY？）。所有局部频繁项集合并为全局候选项集。第二次扫描D，评估每个候选的实际支持度。
4、选样：就是抽样+检测手段，以精度换速度。
5、动态项集计数：不像Apriori仅在每次完整扫描前确定新的候选，现在在任何开始点添加候选集。（编程怎么实现比较好？）