数据挖掘十大经典算法之apriori算法&源代码

数据挖掘十大经典算法之apriori算法&源代码 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。由Agrawal等人提出的Apriori是经典的关联规则和频繁项集挖掘算法，围绕着它的改进和实现

快乐的霖霖

2103人浏览 · 2013-02-26 11:25:18

快乐的霖霖 · 2013-02-26 11:25:18 发布

数据挖掘十大经典算法之apriori算法&源代码

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。

由Agrawal等人提出的Apriori是经典的关联规则和频繁项集挖掘算法，围绕着它的改进和实现有大量的文献。该算法是挖掘产生布尔关联规则频繁项目集的经典算法，从其产生到现在对关联规则挖掘方面的研究有着很大的影响。

为了提高频繁项目的挖掘效率，Apriori算法利用了两个重要的性质，用于压缩搜索的空间。

【1】若X为频繁项目集，则X的所有子集都是频繁项目集。

【2】若X为非频繁项目集，则X的所有超集均为非频繁项目集。

Apriori算法的处理流程为：宽度优先搜索整个项集空间，从k=0开始，迭代产生长度为k+1的候选项集的集合C_k+1。候选项集是其所有子集都是频繁项集的项集。C₁由I₀中所有的项构成，在第k层产生所有长度为k+1的项集。这由两步完成：第一步，F_k自连接。将F_k中具有相同(k-1)-前缀的项集连接成长度为k的候选项集。第二步是剪枝，如果项集的所有长度为k的子集都在F_k中，该项集才能作为候选项集被加入C_k+1中。为了计算所有长度为k的候选项集的支持度，在数据库水平表示方式下，需要扫描数据库一遍。在每次扫描中，对数据库中的每条交易记录，为其中所包含的所有候选k-项集的支持度计数加1。所有频繁的k-项集被加入F_k中。此过程直至C_k+1等于空集时结束。

算法 Apriori

Input: Transaction DataBase D，Minimum support threshold minsup。

Output： Frequent pattern L

(1) L₁=search_frequent_1-itemsets( D );

(2) for(k=2;L_k-1≠φ;k++) do

(3) begin

(4) C_k=apriori-gen(L_k-1);

(5) for all transactions t D do

(6) begin

(7) C_t=subset(C_k，t);

(8) for all candidates c C_t do

(9) c.count++;

(10) end

(11) L_k ={c C_k|c.count≥minsup}

(12) end

(13) Answer L=∪_kL_k;

Procedure Search_frequent_1-itemsets( D )

(1) begin

(2) for all transactions t D do

(3) begin

(4) for each item i_k t do

(5) i_k.count++;

(6) end

(7) L₁ ={ i I | i.count≥minsup}

(8) return L₁;

(9) end

Procedure apriori_gen(L_k)

(1) begin

(2) for each itemset l₁ L_kdo

(3) for each itemset l₂ L_kdo

(4) begin

(5) if ( l₁[1]=l₂[1]) ( l₁[2]=l₂[2]) … ( l₁[k-1]=l₂[k-1]) ( l₁[k]<l₂[k]) then

(6) begin

(7) c= l₁ l₂;

(8) if Is_include_infrenquent_subset(c,L_k) then

(9) delete c;

(10) else add c to C_k+1;

(11) end

(12) end

(13) return C_k+1;

(14) end

Procedure Is_include_infrenquent_subset(c,L_k)

(1)begin

(2) for each k-subset s of c

(3) if s L_k 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，然后对数据库进行扫描(第5步)，对于数据库中的每一个交易，subset函数用来发现此交易包含的所有候选集(第7步)，并为这些候选集的计数器加1(第8-9步)。最后满足minsup的候选集被放入到Lk中。

apriori_gen过程完成两种操作：并(join)和剪枝(prune)。在并运算步骤中，Lk-1 与Lk-1 进行并运算生成潜在的候选集(2-7步)，条件l1[k-1]<l2[k-1]保证不会有重复的候选集生成(第5步)。在剪枝步骤中(8-10步)，利用性质2.1，删除那些存在子集不是频繁项目集的候选集，测试子集是否为频繁项目集由过程Is_include_infrenquent_subset完成。

为了清楚的阐述Apriori算法的挖掘过程，现举例如下：

【例1】设事务数据库D如表2.1所示，D中包含4个事务，即|D|=4，最小支持数mincount=2，即最小支持度minsup=2/4=50%。挖掘频繁项目集的具体过程如下所述：C₁={{A},{B},{C},{D},{F}}，第一次循环产生L₁={{A},{B},{C},{F}}，由Apriori_gen(L₁)生成C₂，扫描数据库，计算C₂中每个候选集得到L₂。依此循环，得到L₃。整个挖掘过程如图2.1所示。