一种适应关系型数据库的多维关联规则挖掘的算法
Agrawal等在1993年设计了一个基本算法Apriori,提出了挖掘关联规则的一个重要
方法一这是一个基于两阶段频集思想的方法,关联规则挖掘算法的设计可以分解为两个子
问题:
1) 找到所有支持度大于最小支持度的项集(Itemset),这些项集称为频集(Frequent
Itemset)。
2) 使用第1步找到的频集产生期望的规则。
其算法的实现过程可以描述如下:首先,Apriori算法求出项数为一项的频繁集L
1
-set,然后,
再由L
1
-set产生项数为二的候选集C
2
-set,扫描事务数据库D计算支持度求出L
2
-set,依次类
推产生C
k
-set扫描D求出L
k
-set。一旦从数据库中产生了频繁集,则可以从中直接产生强关联
规则(所谓的强关联规则是指既满足最小支持度又满足最小可信度的关联规则)。但是,
当项集的个数|l|和数据库的尺寸很大时,如果每一次寻找频繁项集都需要遍历数据库,查
找数据库的开销会很大,算法的性能也就不容乐观。
一 AprioriTid 算法
AprioriTid算法对Apriori算法做了调整,它的特点是在第一次遍历数据库D之后,就
不再使用数据库来计算支持度,而是用集合C
k
来完成。集合C
k
每个成员的形式为(TID,
{X
k
}),其中每个X
k
都是一个潜在的大型k项集,在标识符为TID的事务中。对于
k=1,C1对应与数据库D,虽然在概念上每个项目i由项目集{l}代替。对于k>1,有算法
产生C
k
(步骤(10))。与事务t相应的C
k
的成员是(t.TID,{c∈C
k
|t中包含的c})。若某
个事务不包含任何候选k项目集,那么C
k
对于这个事务就没有条目(Entry)。这样,C
k
中
条目数量比数据库中的事务数量少,尤其对于大值的k而言。另外,对于大值的k,每个条
目比相应的事务要小,这是因为几乎没有什么候选能包含在此事务中。但是,对于小值的
k,每个条目比相应的事务要大,因为Ck中的一个条目包括了此事务中的所有候选k项目集。
算法步骤如下:
(1) L
1
={large l-itemsets}
(2) C
1
=数据库D;
(3) For (k=2; L
k-1
≠ø; k++) do begin
(4) C
k
= apriori-gen(L
k-1
); //新的候选集
(5) C
k
’= ø;
(6) for 所有条目t∈C
k-1
’do begin
(7) //确定事务t。TID中包含的候选
C
t
={ c∈C
k
|(c-c[k]) ∈t.项目集的集合∧(c-c[k-1])∈t.项目集的集合};
(8) for 所有候选c∈C
t
do
(9) c.count ++;
(10) if(C
t
≠ø) then C
k
’+=<t.TID, C
t
>;
(11) end
(12) L
k
={c∈C
k
|c.count≥min.supp}
(13) end