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

《一种适应关系型数据库的多维关联规则挖掘的算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一种适应关系型数据库的多维关联规则挖掘的算法Agrawal等在1993年设计了一个基本算法Apriori，提出了挖掘关联规则的一个重要方法一这是一个基于两阶段频集思想的方法，关联规则挖掘算法的设计可以分解为两个子问题:1)找到所有支持度大于最小支持度的项集(Itemset)，这些项集称为频集(FrequentItemset)。2)使用第1步找到的频集产生期望的规则。其算法的实现过程可以描述如下：首先，Apriori算法求出项数为一项的频繁集L1-set，然后，再由L1-set产生项数为二的候选集C2-set，扫描事务数据库D计算支持度求出L2-set，依次类推产生

2、Ck-set扫描D求出Lk-set。一旦从数据库中产生了频繁集，则可以从中直接产生强关联规则（所谓的强关联规则是指既满足最小支持度又满足最小可信度的关联规则）。但是，当项集的个数

3、l

4、和数据库的尺寸很大时，如果每一次寻找频繁项集都需要遍历数据库，查找数据库的开销会很大，算法的性能也就不容乐观。一AprioriTid算法AprioriTid算法对Apriori算法做了调整，它的特点是在第一次遍历数据库D之后，就不再使用数据库来计算支持度，而是用集合Ck来完成。集合Ck每个成员的形式为（TID,{Xk}），其中每个Xk都是一个潜在的大型k项集，在标识符为TID的事务中

5、。对于k=1，C1对应与数据库D，虽然在概念上每个项目i由项目集{l}代替。对于k>1，有算法产生Ck（步骤（10））。与事务t相应的Ck的成员是（t.TID,{c∈Ck

6、t中包含的c}）。若某个事务不包含任何候选k项目集，那么Ck对于这个事务就没有条目（Entry）。这样，Ck中条目数量比数据库中的事务数量少，尤其对于大值的k而言。另外，对于大值的k，每个条目比相应的事务要小，这是因为几乎没有什么候选能包含在此事务中。但是，对于小值的k，每个条目比相应的事务要大，因为Ck中的一个条目包括了此事务中的所有候选k项目集。算法步骤如下：（1）L1={largel-it

7、emsets}（2）C1=数据库D;（3）For(k=2;Lk-1≠ø;k++)dobegin（4）Ck=apriori-gen(Lk-1);//新的候选集（5）Ck’=ø;（6）for所有条目t∈Ck-1’dobegin（7）//确定事务t。TID中包含的候选Ct={c∈Ck

8、(c-c[k])∈t.项目集的集合∧（c-c[k-1]）∈t.项目集的集合}；（8）for所有候选c∈Ctdo（9）c.count++;（10）if(Ct≠ø)thenCk’+=;（11）end（12）Lk={c∈Ck

9、c.count≥min.supp}（13）end（

10、14）答案=;二AprioriTidList算法AprioriTid算法比Apriori算法有了很大的改善,且适用于大型数据库，但是它必须通过多次搜索交易数据集得到所有的候选项集的支持度。虽然数据都是在本地内存中存储，但如果数据集的数量很大的话，运算量还是很大，而且对于每一个候选项都要通过搜索所有的事务条目来计算支持度，搜索的结果不能重复利用，造成资源的浪费。AprioTidList算法通过链表结构，存储包含每个候选项的所有条目的ID，计算K层候选项的支持度时，只要比较k-1层候选项链表中有几个相同的条目ID就可以得到结果，算法描述如下：(1)L′1={1-ite

11、msetsalongwiththeirtidlist}(2)L1={largel-itemsets}(3)For(k=2;L＇k-1≠ø;k++)dobegin(4)Lk=ø;L＇k=ø(5)Forallitemsetsl1∈L＇k-1dobegin(6)forallitemsetsl2∈L＇k-1dobegin(7)ifl1[1]=l2[1]∧l1[2]=l2[2]∧…∧l1[k-1]

12、count={C＇.tidlist}(11)If(C＇.count≥minsup)then(12)L＇k=L＇k∪{C＇}(13)C.itemsets=C＇.itemsets(14)C.count=C＇.count(15)Lk=Lk∪{C}(16)End(17)End(18)End(19)答案=;该算法与Apriori和AprioriTid的不同之处在于计算候选项集支持度的方法不同:对每一个候选项集定义一个叫做tidlist的结构；项集l的tidlist由那些包含l的交易的TID组成,用l.tidlist表示项集l的tidlist。l-项集的tidlist可通过搜

13、索交易数据