AprioriTidList

AprioriTidList是基於弱點資料庫的多維關聯規則算法，比Apriori算法有很大的改善，並且適用於大型資料庫。

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賦不同的值，以適應實際問題的處理需求。