Apriori算法和FP

Apriori算法和FP

来源于《数据挖掘概念与技术》

Apriori

输入：事务数据库D；最小支持度阈值。

输出：D中的频繁项集L。

方法：  L1 = find_frequent_1_itemsets(D); //找出频繁1-项集的集合L1

           for(k = 2; Lk-1 ≠ ∅; k++) { //产生候选，并剪枝

         Ck = aproiri_gen(Lk-1,min_sup);

       for each transaction t∈D{ //扫描D进行候选计数

         Ct = subset(Ck,t); //得到t的子集

          for each candidate c∈Ct

         c.count++; //支持度计数

         }

          Lk={c∈Ck| c.count ≥min_sup} //返回候选项集中不小于最小支持度的项集

        }

     return L = ∪kLk；//所有的频繁集

第一步（连接 join）

Procedure apriori_gen(Lk-1: frequent (k-1)-itemset; min_sup: support)

1) for each itemset l1∈Lk-1

2) for each itemset l2∈Lk-1

3) if(l1[1]=l2[1])∧...∧(l1[k-2]=l2[k-2])∧(l1[k-1]<l2[k-1]) then{

4) c = l1 l2; //连接步：l1连接l2 //连接步产生候选，若K-1项集中已经存在子集c，则进行剪枝

5) if has_infrequent_subset(c,Lk-1) then

6) delete c; //剪枝步：删除非频繁候选

7) else add c to Ck;

8) }

9) return Ck;

第二步：剪枝（prune）

Procedure has_infrequent_subset(c:candidate k-itemset; Lk-1:frequent (k-1)-itemset) //使用先验定理

1) for each (k-1)-subset s of c

2) if c∉Lk-1 then

3) return TRUE;

4) return FALSE;
 

FP-growth

输入：

D：事务数据库。

min_sup：最小支持度阈值。

输出：

频繁模式的完全集。

方法：

1.按照以下步骤构造FP树：

（a）扫描事务数据库D一次。收集频繁项的集合F和他们的支持度。对F按照支持度计数降序排序，结果为频繁项集L。

（b）创建FP树的根节点，以“null”标记它。对于D中每一个事务trans，执行：

选择trans中的频繁项集，并且按照L中的次序排序。设trans排序后的频繁项集列表为[p|P]，其中p是第一个元素，而P是剩余元素的列表。调用insert_tree（[p|P],T）。该过程执行情况如下。如果T有子女N使得N.item-name = p.item-name，则N的计算加一；否则，创建一个新节点N，把它的计算设置为一，连接到它的父节点T，并且通过节点链结构把它连接到具有相同item-name的节点。如果P非空，则递归调用insert_tree（P,N）。

2.FP树的挖掘通过调用FP-growth（FP_tree，null）实现。过程如下：

Procedure FP_growth（tree，α）

（1）if tree包含单个路径P then；

（2）for路径P中结点的每个组合（记作β）；

（3）产生模式β Uα，其支持度计数support_count等于β中的结点的最小支持度计数；

（4）else for Tree的头表中的每个ai {
（5）产生一个模式β  = aiUα，其支持度计数support_count = ai，support_count；

（6）构造β的条件模式基，然后构造β的条件FP树Treeβ；

（7）If Treeβ ≠Øthen

（8）调用FP_growth（Treeβ，β）；}