转：数据挖掘十大经典算法之apriori算法&源代码<转>
2012-05-12 19:05阅读：
原文
http://blog.csdn.net/liema2000/article/details/6118423
数据挖掘十大经典算法之apriori算法&源代码
The Apriori algorithm
兄弟童车精品店
https://weidian.com/s/1027221606?wfr=c
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于
两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规
则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。
VC 界面的源代码见
http://download.csdn.net/source/2963738
由Agrawal等人提出的Apriori是经典的关联规则和频繁项集挖掘算法，围绕着它的改进和实现有大量的文献。该算法是挖掘产生布尔关联规则频繁项目集的经典算法，从其产生到现在对关联规则挖掘方面的研究有着很大的影响。
为了提高频繁项目的挖掘效率，Apriori算法利用了两个重要的性质，用于压缩搜索的空间。
【1】若X为频繁项目集，则X的所有子集都是频繁项目集。
【2】若X为非频繁项目集，则X的所有超集均为非频繁项目集。
Apriori算法的处理流程为：宽度优先搜索整个项集空间，从k=0开始，迭代产生长度为k+1的候选项集的集合Ck+1。候选项集是其所有子集都是频繁项集的项集。C1由I0中所有的项构成，在第k层产生所有长度为k+1的项集。这由两步完成：第一步，Fk自连接。将Fk中具有相同(k-1)-前缀的项集连接成长度为k的候选项集。第二步是剪枝，如果项集的所有长度为k的子集都在Fk中，该项集才能作为候选项集被加入Ck+1中。为了计算所有长度为k的候选项集的支持度，在数据库水平表示方式下，需要扫描数据库一遍。在每次扫描中，对数据库中的每条交易记录，为其中所包含的所有候选k-项集的支持度计数加1。所有频繁的k-项集被加入Fk中。此过程直至Ck+1等于空集时结束。
算法
Apriori
Input:
Transaction
DataBase
D，Minimum
support threshold
minsup。
Output：
Frequent
pattern L
(1) L1=search_frequent_1-itemsets(
D );
(2)
for(k=2;Lk-1≠φ;k++)
do
(3) begin
(4)
Ck=apriori-gen(Lk-1);
(5) for all
transactions t
D
do
(6)
begin
(7)
Ct=subset(Ck，t);
(8)
for all candidates c
Ct
do
(9)
c.count++;
(10)
end
(11) Lk
={c
Ck|c.count≥minsup}
(12) end
(13) Answer
L=∪kLk;
Procedure Search_frequent_1-itemsets( D
)
(1) begin
(2) for all
transactions t
D
do
(3) begin
(4) for each item
ik
t
do
(5)
ik.count++;
(6) end
(7) L1 ={
i
I
|
i.count≥minsup}
(8) return
L1;
(9) end
Procedure
apriori_gen(Lk)
(1) begin
(2) for
each itemset
l1
Lk
do
(3)
for each
itemset
l2
Lk
do
(4)
begin
(5)
if (
l1[1]=l2[1])
(
l1[2]=l2[2])
… (
l1[k-1]=l2[k-1])
(
l1[k]<<em>l2[k])
then
(6)
begin
(7)
c= l1
l2;
(8)
if
Is_include_infrenquent_subset(c,Lk)
then
(9)
delete
c;
(10)
else add
c to
Ck+1
;
(11)
end
(12)
end
(13) return
Ck+1 ;
(14) end
Procedure
Is_include_infrenquent_subset(c,Lk)
(1)begin
(2) for each k-subset
s of c
(3)
if s
Lk
then
(4)
reture TURE;
(5) return FALSE
;
(6)end
在主程序中，第一步首先扫描整个交易数据库D，统计每个项目(item)的支持数，计算其支持度，将支持度大于等于最小支持度minsup的项目构成的集合放入到L1
中；从第2步到第11步，用k-1频繁项目集构成的Lk-1生成候选集的集合Ck，以便从中生成Lk，其中apriori_gen函数(第4步)用来从Lk-1中生成Ck，然后对数据库进行扫描(第
