aprioriTid关联规则挖掘的算法

  aprioriTid

 

 

一种适应关系型数据库的多维关联规则挖掘的算法
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） 答案=  ;
二 AprioriTidList算法
AprioriTid算法比Apriori算法有了很大的改善,且适用于大型数据库，但是它必须通过多次搜索交易数据集得到所有的候选项集的支持度。虽然数据都是在本地内存中存储，但如果数据集的数量很大的话，运算量还是很大，而且对于每一个候选项都要通过搜索所有的事务条目来计算支持度，搜索的结果不能重复利用，造成资源的浪费。AprioTidList算法通过链表结构，存储包含每个候选项的所有条目的ID，计算K层候选项的支持度时，只要比较k-1层候选项链表中有几个相同的条目ID就可以得到结果，算法描述如下：
(1) L′1 = {1-itemsets along with their tidlist}
(2) L1={large l-itemsets}
(3) For(k=2; L＇k-1≠?; k++) do begin
(4)     Lk= ?; L＇k= ?
(5)     For all itemsets l1∈L＇k-1  do begin
(6)         for all itemsets l2∈L＇k-1  do begin
(7)             if l1[1]=l2[1] ∧l1[2]=l2[2] ∧…∧l1[k-1]<l2[k-1] then
(8)             C＇.itemsets = l[1].l[2]…l[k-1].l[k]
(9)             C＇.tidlist = l1.tidlist∩l2.tidlist
(10)             C＇.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可通过搜索交易数据集得到,候选k-项集的tidlist可由产生该候选k-项集的那两个(k-1)-项集的tidlist求交集得到。
AprioTidList与AprioriTid算法一样,只搜索交易数据集一次。它与AprioriTid算法有两个区别。一个区别是计算候选项集支持度所用数据结构（链表）存储的信息不同。在AprioriTid中,链表的每个节点为〈TID ,{Xk}〉,其中Xk是出现在标识为TID的交易中的高频k-项集；在算法AprioTidList中,链表的每个节点为〈l ,tidlist〉,通过对两个频繁项集的tidlist求交集,即可得到候选项集的支持度。在AprioriTid中,需要对整个链表进行搜索才能得到某个候选项集的支持度。因此,用算法AprioTidList得到频繁项集所需时间要比AprioriTid算法所需时间短。AprioTidList与AprioriTid算法的另一个区别在于候选项集的产生办法,在Apriori算法中,需要结合和修剪两个步骤,而在AprioTidList算法中只需结合步骤。
三 AprioriTidList算法应用于多维关联规则的挖掘
现实生活中，我们遇到的很多问题都需要挖掘多维属性之间的关联规则，例如寻找年龄和职业对于购买力的影响：
Age(X, “20…29”) ∧Occupation(X, “student”)=>Buys(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候选I∈Ck, 检查它的支持度是否大于最小支持度，将符合要求的放入Lk中。算法如下：
(1) k=1; C1=?; C＇1=?;
(2) //对于每一维，生成1-itemsets
For each dimense do begin
(3)     C＇1.di={1-itemsets along with their tidlist}
(4)     C1.di={1-itemsets}
(5)     if(C1.count≥ minsup1)
(6)         C1= C1∪C1.di; C＇1= C＇1∪C＇1.di;
(7) End
(8) L1=C1; L＇1=C＇1;
(9) For(k=2; L＇k-1≠?; k++) do begin
(10)     Lk=?; L＇k=?;
(11)     for each item I1∈L＇k-1 do begin
(12)         for each item I2∈L＇k-1 do begin
(13)             //only itemsets in different dimense would be joined
                if(l1[1]=l2[1] ∧l1[2]=l2[2] ∧…∧l1[k-1]<l2[k-1])
                AND{l1[k-2] ∈di∧l2[k-2] ∈dj|i≠j} then  
(14)                 C＇.itemsets = l[1].l[2]…l[k-1].l[k]
(15)                 C＇.tidlist = l1.tidlist∩l2.tidlist
(16)                 C＇.count = { C＇.tidlist}
(17)                 If(C＇.count ≥ minsupk) then 
(18)                     L＇k = L＇k ∪{ C＇}
(19)                     C.itemsets = C＇.itemsets
(20)                     C.count = C＇.count
(21)         End
(22)     End
(23) End
(24) 答案=  ;
其中，第（2）步对各个维求频繁项集，并且每个频繁项采用〈l ,tidlist〉存储，第（9）步开始维间求频繁项集，计算支持度的时候只需要把两个频繁项的tidlist求交集，而不用每次都从数据库中读取。我们可以为算法中每一次频繁项集的修剪制订不同的最小支持度，给各个minsupk赋不同的值，以适应实际问题的处理需求。