首页 > 代码库 > Apriori算法

Apriori算法

Apriori算法是一种发现频繁项集的基本算法,算法的思想主要就是使用一种称为逐层搜索的迭代方法,K项集用于探索(K+1)项集。

算法的伪代码如下:(具体实现正在进行中……)

输入:

  • D:事务数据库
  • min_sup:最小支持度阈值

输出:

  • L,D中的频繁项集

方法:

  1.      L1 =find_frequent_1-itemsets(D);   
  2.      For(k=2;Lk-1 !=null;k++){  
  3.         Ck =apriori_gen(Lk-1 );   
  4.         For each 事务t  in D{   
  5.             Ct =subset(Ck,t);
  6.             For each 候选 c 属于 Ct  
  7.                 c.count++;  
  8.         }  
  9.         Lk ={c 属于 Ck | c.count>=min_sup}  
  10. }  
  11. Return L= UkLk;  
  12. Procedure apriori_gen (Lk-1 :frequent(k-1)-itemsets)  
  13.       For each 项集 l1 属于 Lk-1  
  14.          For each 项集 l2 属于 Lk-1  
  15.             if( (l1 [1]=l2 [1])&&( l1 [2]=l2 [2])&& ……&& (l1 [k-2]=l2 [k-2])&&(l1 [k-1]<l2 [k-1]) )   
  16.            {  
  17.                     c = l1 连接 l2    // 连接步:产生候选  
  18.              
  19.                    if has_infrequent_subset(c, Lk-1 ) then  
  20.                        delete c; // 剪枝步:删除非频繁候选  
  21.                    else add c to Ck;  
  22.              }  
  23.           Return Ck;  
  24. //使用先验知识
  25.  Procedure has_infrequent_sub (c:candidate k-itemset; Lk-1 :frequent(k-1)-itemsets)  
  26.          For each (k-1)-subset s of c  
  27.             If s 不属于 Lk-1 then  
  28.                Return true;  
  29.         Return false; 

Apriori算法