Apriori算法乃是关联规则挖掘的经典算法，尽管是94年提出的算法，然而至今也有着旺盛的生命力。在互联网科学领域，也有着广泛的应用，因此还是值得大家都对此学习一下。
一、术语
1.支持度：support，所有实例中覆盖某一项集的实例数。
2.置信度：confidence。对于X→Y这个规则，如果数据库的包含X的实例数的c%也包含Y，则X→Y的置信度为c%。
3.频繁项集：也称large itemsets，指支持度大于minsup（最小支持度）的项集
二、思想
1.Apriori算法思想与其它关联规则挖掘算法在某些方面是相同的。即首先找出所有的频繁项集，然后从频繁项集中抽取出规则，再从规则中将置信度小于最小置信度的规则剃除掉。
2.若项集i为频繁项集，则其所有子集必为频繁项集。因此，Apriori算法思想在于从频繁的k-1项集中合并出k项集，然后剃除掉子集有不是频繁项集的k项集。
3.先从数据库中读出每条实例，对于设定阈值，选出频繁1项集，然后从频繁1项集中合并，并剃除掉包含非频繁1项集子集的2项集……
4.符号说明：
L
k:Set of large(frequent) k-itemsets
C
k:Set of candidate k-itemsets
apriori-gen()函数通过合并k-1的频繁项集，生成C
k
三、算法描述
1) Apriori基本算法
1
L1={large 1-itemsets};
2
for(k=2;Lk-1!=Φ;k++)
3{
4
Ck=apriori-gen(Lk-1);
5 for(all transaction t∈D)
6
{
7 Ct=subset(Ck,t);
8 for(all candidates c∈Ct)
9 c.count++;
10
}
11 Lk={c∈Ck|c.count>=minsup}
12
}
13Answer=∪k Lk; 2)apriori-gen()函数
这个函数将L
k-1（即所有k-1频繁项集的集合）作为参数，返回一个L
k的超集（即C
k）
算法如下：
1insert into Ck
2select p.item1, p.item2, 
,p.itemk-1,q.itemk-1
3from Lk-1 p, Lk-1 q
4where p.item1=q.item1, p.item2=q.item2, , p.itemk-1<q.itemk-1 然后通过剪枝，剃除掉C
k中某些子集不为频繁k-1项集的项集，算法如下：
1for(all items c∈C
k)
3)从频繁项集中生成规则
1
for(all l∈Answer)
2
{
3
A=set of nonempty-subset(l);
4 for(all a∈A)
5
{
6 output a→(l-a);
7
}
8
} 四、举例（这里将minsup=1，mincof=0.5）
L3={{1 2 3}{1 2 4}{1 3 4}{1 3 5}{2 3 4}}
在合并步骤时，选取L3中，前两个项都相同，第三个项不同的项集合并，如{1 2 3}与{1 2 4}合并、{1 3 4}与{1 3 5}合并成{1 2 3 4}和{1 3 4 5}。因此，C4={{1 2 3 4}{1 3 4 5}}，但是由于{1 3 4 5}中某子集{3 4 5}并未在L3中出现，因此，将{1 3 4 5}剃除掉，所以L4={{1 2 3 4}}。
然后以L4为例，选取出关联的规则：
L4中{1 2 3 4}项集中抽取出（这里只列出左边为3项的情况）：
{1 2 3}→4
{1 2 4}→3
{1 3 4}→2
{2 3 4}→1
显然，因为只有一个4项集，因此，这四条规则的置信度都为100%。因此，全数为关联规则。
五、Apriori变体
有些Apriori变体为追求时间效率，不是从L
1→C
2→L
2→C
3→....的步骤产生，而是从L
1→C
2→C
3'..产生。
参考文献：
Agrawal, Rakesh, Srikant, Ramakrishnan. Fast algorithms for mining association rules in large databases. Very Large Data Bases, International Conference Proceedings, p 487, 1994 posted on 2012-02-27 13:08
Seraphi 阅读(770)
评论(0) 编辑 收藏