算法原理
背景知识
Apriori算法是Agrawal等于1994年提出的一个挖掘顾客交易数据库中项集间的关联规则的重要方法，是迄今最有影响挖掘布尔关联规则频繁项集的关联规则算法。该关联规则在分类上属于单维、单层、布尔关联规则。
算法原理
Apriori算法主要分成两步：首先找出数据中所有的频繁项集，这些项集出现的频繁性要大于或等于最小支持度。然后由频繁项集产生强关联规则，这些规则必须满足最小支持度和最小置信度。算法的总体性能由第一步决定，第二步相对容易实现。
第一步主要是基于Apriori性质：频繁项集的所有非空子集都必须也是频繁的。因此这一步主要由连接和剪枝两个过程组成。连接：频繁项集Lk-1与自己连接产生候选k-项集的集合Ck。假定事务和项集都按字典次序排序。连接Lk-1Lk-1，Lk-1中的l1和l2项是可连接的，如果(l1[1]=l2[1] )∧(l1[2]=l2[2] )∧…∧(l1[k-2]=l2[k-2] )∧(l1[k-1]<l2[k-1] )，连接的结果项集为l1[1] l1[2]…l1[k-1]l2[k-1]。剪枝：若一个候选k-项集的(k-1)-子集不在Lk-1中，则该候选集不可能是频繁的，可由Ck中删除。
Ck可存在hash-tree中。
发现频繁项集的Apriori算法的伪码如下：
输入：事务数据库D；最小支持度阈值min_sup。
输出：D中的频繁项集L。
(1) L1 = find_frequent_1-itemsets(D); //找出频繁1-项集
(2) for (k = 2; Lk-1 ¹ F; k++)
(3) {
(4) Ck= apriori_gen(Lk-1, min_sup); //产生新的候选集
(5) for all transactions tÎD
(6) {
(7) Ct=subset(Ck, t); //事务t中包含的候选集
(8) for all candidates cÎ Ct
(9) c.count++;
(10) }
(11) Lk = {c Î Ck | c.count³min_sup}
(12) }
(13) return L = ∪k Lk;
procedure apriori_gen(Lk-1,min_sup)
(1) for all l1∈Lk-1
(2) {
(3) for all l2∈Lk-1
(4) {
(5) if (l1[1]=l2[1] )∧(l1[2]=l2[2] )∧…∧(l1[k-2]=l2[k-2] )∧(l1[k-1]<l2[k-1])
(6) then
(7) {
(8) c = l1 ∞ l2; //连接
(9) if has_infrequent_subset(c, Lk-1) then
(10) delete c; //剪枝
(11) else add c to Ck;
(12) }
(13) }
(14) }
(15) return Ck;
procedure has_infrequent_subset(c,Lk-1)
(1) for all (k -1)-subset s of c
(2) {
(3) if sLk-1 then
(4) return TRUE;
(5) }
(6) return FALSE
第二步由频繁项集产生关联规则如下：
l 对每个频繁项集l，产生l的所有非空子集。
l 对l的每个非空子集s，如果，则产生规则“s（l-s）”。min_conf是最小置信度。
限制条件
算法只能处理单维、单层的种类字段。
这个方法要求多次扫描可能很大的交易数据库，这需要很大的I/O负载，因此处理的数据量不能太大。
输出结果
算法输出事务数据库中的关联规则，规则形如AB。
算法优点和缺点
优点：
l 提出了利用Apriori性质挖掘频繁项集产生关联规则的思想，对以后的关联规则算法有深远的影响。
l 提出的Apriori性质大幅压缩了候选项集的大小，提高了性能。
l 可用来提高冰山查询的效率。
缺点：
l 只能处理单维、单层的种类字段
l 可能产生大量的候选集,
l 可能需要重复扫描数据库，I/O负担大。
改进：
对Apriori算法的改进已有许多方法，如散列，事务压缩，划分和选样等，都是基于减少数据扫描次数的思想。但都不如FP-Tree的改进彻底，有效。
|
例子
处理：假定最小支持计数为2。
|
|
第一步：产生频繁项集
|
|||||
|
|||||
得到频繁项集：{{1};{2};{3};{5};{1, 3};{2, 3};{2, 5};{3, 5};{2, 3, 5}}
第2步：由频繁项集产生关联规则，假定最小置信度为70％
1) 对频繁项集{1, 3},它的非空子集为{1}，{3}。
对{1}，；所以输出规则1→3；
对{3}，；所以不输出规则；
2) 对频繁项集{2, 3},它的非空子集为{2}，{3}。
对{2}，；所以不输出规则；
对{3}，；所以不输出规则；
3) 对频繁项集{2, 5},它的非空子集为{2}，{5}。
对{2}，；所以输出规则2→5；
对{5}，；所以输出规则5→2；
4) 对频繁项集{3, 5},它的非空子集为{3}，{5}。
对{3}，；所以不输出规则；
对{5}，；所以输出规则；
5) 对频繁项集{2,3, 5},它的非空子集为{2}，{3}，{5}，{2, 3},{2, 5},{3, 5}。
对{2}，；所以不输出规则；
对{3}，；所以不输出规则；
对{5}，；所以输出规则；
对{2,3}，；所以输出规则2∧3→5；
对{2,5}，；所以不输出规则；
对{3,5}，；所以输出规则3∧5→2；
得到关联规则1→3；2→5；5→2；2∧3→5；3∧5→2。
□
|
|||||||||||
|
|||||||||||