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

一种适应关系型数据库的多维关联规则挖掘的算法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代替。对于k1，有算法产生Ck（步骤（10）。与事务t相应的Ck的成员是（t.TID,cCk|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 所有条目tCk-1do begin（7） /确定事务t。TID中包含的候选Ct= cCk |(c-ck) t.项目集的集合（c-ck-1）t.项目集的集合；（8） for 所有候选cCt do （9） c.count +;（10） if(Ct) then Ck+=;（11） end（12） Lk=cCk |c.countmin.supp（13） end（14） 答案=;二 AprioriTidList算法AprioriTid算法比Apriori算法有了很大的改善,且适用于大型数据库，但是它必须通过多次搜索交易数据集得到所有的候选项集的支持度。虽然数据都是在本地内存中存储，但如果数据集的数量很大的话，运算量还是很大，而且对于每一个候选项都要通过搜索所有的事务条目来计算支持度，搜索的结果不能重复利用，造成资源的浪费。AprioTidList算法通过链表结构，存储包含每个候选项的所有条目的ID，计算K层候选项的支持度时，只要比较k-1层候选项链表中有几个相同的条目ID就可以得到结果，算法描述如下：(1) L1 = 1-itemsets along with their tidlist(2) L1=large l-itemsets(3) For(k=2; Lk-1; k+) do begin(4) Lk= ; Lk= (5) For all itemsets l1Lk-1 do begin(6) for all itemsets l2Lk-1 do begin(7) if l11=l21 l12=l22 l1k-1Buys(X, “taptop”)对于这类n维关联规则的查找，现有的比较流行的做法是建立数据立方体存储多维数据，每维共有+1个值,其中是指第维中互不相同的属性值,每维中再加上一个值,共+1个不同值。假设存在一个维空间,由每一维中各取一个具体的属性值,则可对应一个维空间中的点,这个点我们称之为方格,每个方格内存贮了与其对应的各属性的值同时出现的次数,用count表示。然后采用Apriori算法分别求出各个维的频繁项集，支持度直接使用立方体中的统计信息来计算，小于最小支持度的项集被剪枝，然后依次求的维间的频繁项集，得到最终结果。这种基于立方体的算法虽然可以在求频繁项集的支持度的时候使用立方体的统计信息而不用去检索数据库，但是构建立方体的代价却是昂贵的，一个n维属性的数据集，如果每维属性中的不同值是k的话，那么构建一个数据立方体需要检索数据库的次数是（k+1）的n次方，所以这种算法只能适用于多维数据库的挖掘，对于关系型数据库，计算成本太高。AprioriTidList算法的链式结构可以很好的解决这个问题，同样是n维属性的数据集，每个属性中不同值的个数为k，只需要n*k次数据库访问就可以了。下面，我们把AprioriTidList算法进行改进，使它适用于关系数据库的多维关联规则的挖掘。可以首先把数值维度进行量化，然后针对每一个维度使用AprioriTidList算法找出所有得1-itemsets频繁项集L1，然后陆续找出k-itemsets频繁项集Lk。算法通过对Lk-1维间连接产生k-itemsets的候选集Ck。对于每一个k-itemsets候选ICk, 检查它的支持度是否大于最小支持度，将符合要求的放入Lk中。算法如下：(1) k=1; C1=; C1=;(2) /对于每一维，生成1-itemsetsFor each dimense do begin(3) C1.di=1-itemsets along with their tidlist(4) C1.di=1-itemsets(5) if(C1.count minsup1)(6) C1= C1C1.di; C1= C1C1.di;(7) End(8) L1=C1; L1=C1;(9) For(k=2; Lk-1; k+) do begin(10) Lk=; Lk=;(11) for each item I1Lk-1 do begin(12) for each item I2Lk-1 do begin(13) /only itemsets in different dimense would be joined if(l11=l21 l12=l22 l1k-1l2k-1) ANDl1k-2 dil2k-2 dj|ij then (14) C.itemsets = l1.l2lk-1.lk(15) C.tidlist = l1.tidlistl2.tidlist(16) C.count = C.tidlist(17) If(C.count minsupk) then (18) Lk = Lk C(19) C.itemsets = C.itemsets(20) C.count = C.count(21) End(22) End(23) End(24) 答案=