一種適應關係型資料庫的多維關聯規則挖掘的算法
Agrawal等在1993年設計了一個基本算法Apriori，提出了挖掘關聯規則的一個重要方法一這是一個基於兩階段頻集思想的方法。
基本介紹
- 外文名：AprioriTid
- 提出時間：1993年
- 提出人：Agrawal
- 學科：計算機
Apriori算法,AprioriTid算法,
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） 答案= ;
