AprioriTidList是基于弱点数据库的多维关联规则算法，比Apriori算法有很大的改善，并且适用于大型数据库。

AprioriTidList算法

算法应用于多维关联规则的挖掘

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算法中只需结合步骤。

算法应用于多维关联规则的挖掘

现实生活中，我们遇到的很多问题都需要挖掘多维属性之间的关联规则，例如寻找年龄和职业对于购买力的影响：

Age(X, “20…29”) ∧Occupation(X, “student”)=>Buys(X, “taptop”)

对于这类n维关联规则的查找，现有的比较流行的做法是建立数据立方体存储多维数据，每维共有|di|+1个值,其中|di|是指第i维中互不相同的属性值,每维中再加上一个″Any″值,共|di|+1个不同值。假设存在一个n维空间,由每一维中各取一个具体的属性值,则可对应一个n维空间中的点,这个点我们称之为方格,每个方格内存贮了与其对应的各属性的值同时出现的次数,用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赋不同的值，以适应实际问题的处理需求。