Apriori算法

AprioriTid算法

Apriori算法

一种适应关系型数据库的多维关联规则挖掘的算法

Agrawal等在1993年设计了一个基本算法Apriori，提出了挖掘关联规则的一个重要方法一这是一个基于两阶段频集思想的方法，关联规则挖掘算法的设计可以分解为两个子问题:

1) 找到所有支持度大于最小支持度的项集(Itemset)，这些项集称为频集(Frequent Itemset)。

2) 使用第1步找到的频集产生期望的规则。

其算法的实现过程可以描述如下：首先，Apriori算法求出项数为一项的频繁集L1-set，然后，再由L1-set产生项数为二的候选集C2-set，扫描事务数据库D计算支持度求出L2-set，依次类推产生Ck-set扫描D求出Lk-set。一旦从数据库中产生了频繁集，则可以从中直接产生强关联规则（所谓的强关联规则是指既满足最小支持度又满足最小可信度的关联规则）。但是，当项集的个数|l|和数据库的尺寸很大时，如果每一次寻找频繁项集都需要遍历数据库，查找数据库的开销会很大，算法的性能也就不容乐观。

AprioriTid算法

AprioriTid算法对Apriori算法做了调整，它的特点是在第一次遍历数据库D之后，就不再使用数据库来计算支持度，而是用集合Ck来完成。集合Ck每个成员的形式为（TID, {Xk}），其中每个Xk都是一个潜在的大型k项集，在标识符为TID的事务中。对于k=1，C1对应与数据库D，虽然在概念上每个项目i由项目集{l}代替。对于k>1，有算法产生Ck（步骤（10））。与事务t相应的Ck的成员是（t.TID,{c∈Ck|t中包含的c}）。若某个事务不包含任何候选k项目集，那么Ck对于这个事务就没有条目（Entry）。这样，Ck中条目数量比数据库中的事务数量少，尤其对于大值的k而言。另外，对于大值的k，每个条目比相应的事务要小，这是因为几乎没有什么候选能包含在此事务中。但是，对于小值的k，每个条目比相应的事务要大，因为Ck中的一个条目包括了此事务中的所有候选k项目集。算法步骤如下：

（1） L1={large l-itemsets}

（2） C1=数据库D;

（3） For (k=2; Lk-1≠?; k++) do begin

（4） Ck = apriori-gen(Lk-1); //新的候选集

（5） Ck’= ?;

（6） for 所有条目t∈Ck-1’do begin

（7） //确定事务t。TID中包含的候选

Ct={ c∈Ck |(c-c[k]) ∈t.项目集的集合∧（c-c[k-1]）∈t.项目集的集合}；

（8） for 所有候选c∈Ct do

（9） c.count ++;

（10） if(Ct≠?) then Ck’+=<t.TID, Ct>;

（11） end

（12） Lk={c∈Ck |c.count≥min.supp}

（13） end

（14） 答案= ;