第8章 關聯分析 王海.

Presentation on theme: "第8章 關聯分析 王海."— Presentation transcript:

1 第8章 關聯分析 王海

2 關聯關係： 沃爾瑪啤酒與尿布 一個來自沃爾瑪超市的真實案例，尿布與啤酒這兩種風馬牛不相及的商品居然擺在一起。但這一奇怪的舉措居然使尿布和啤酒的稍量大幅增加了。這可不是一個笑話，而是一直被商家所津津樂道的發生在美國沃爾瑪連鎖超市的真實案例。原來，美國的婦女通常在家照顧孩子，所以她們經常會囑咐丈夫在下班回家的路上為孩子買尿布，而丈夫在買尿布的同時又會順手購買自己愛喝的啤酒。這個發硯為商家帶來了大量的利潤，但是如何從浩如煙海卻又雜亂無章的數據中，發現啤酒和尿布銷售之間的聯繫呢？這又給了我們什麼樣的啟示呢？

3 “啤酒和尿布”的故事是行銷屆的神話！ 關聯分析應用：購物籃分析
“啤酒”和“尿布”兩個看上去沒有關係的商品擺放在一起進行銷售、並獲得了很好的銷售收益，這種現象就是賣場中商品之間的關聯性，研究“啤酒與尿布”關聯的方法就是購物籃分析，購物籃分析是沃爾瑪秘而不宣的獨門武器，購物籃分析可以幫助我們在門店的銷售過程中找到具有關聯關係的商品，並以此獲得銷售收益的增長！   “啤酒和尿布”的故事是行銷屆的神話！

4 定義:關聯分析（Association Analysis）
關聯分析用於發現隱藏在大型數據集中的令人感 興趣的聯繫，所發現的模式通常用關聯規則或頻 繁項集的形式表示。 關聯分析可以應用於生物資訊學、醫療診斷、網 頁挖掘、科學數據分析等 Rules Discovered: {Diaper} --> {Beer}

5 定義: 頻繁項集（Frequent Itemset）
包含0個或多個項的集合 例子: {Milk, Bread, Diaper} k-項集 如果一個項集包含k個項 支持度計數（Support count ）() 包含特定項集的事務個數 例如： ({Milk, Bread,Diaper}) = 2 支持度（Support） 包含項集的事務數與總事務數的比值 例如： s({Milk, Bread, Diaper}) = 2/5 頻繁項集（Frequent Itemset） 滿足最小支持度閾值（ minsup ）的所 有項集

6 定義: 關聯規則（Association Rule）
關聯規則是形如 X  Y的蘊含運算式, 其中 X 和 Y 是不相交的項集 例子: {Milk, Diaper}  {Beer} 關聯規則的強度 支持度 Support (s) 確定項集的頻繁程度 置信度 Confidence (c) 確定Y在包含X的事 務中出現的頻繁程度 Example:

7 關聯規則挖掘問題 關聯規則挖掘問題：給定事務的集合 T, 關聯規則 發現是指找出支持度大於等於 minsup並且置信度 大於等於minconf的所有規則, minsup和minconf是 對應的支持度和置信度閾值 挖掘關聯規則的一種原始方法是：Brute-force approach: 計算每個可能規則的支持度和置信度 這種方法計算代價過高，因為可以從數據集提取的規則 的數量達指數級 從包含d個項的數據集提取的可能規則的總數R=3d- 2d+1+1，如果d等於6，則R=602

8 For rule A  C: Min. support 50% Min. confidence 50%
Transaction-id Items bought 10 A, B, C 20 A, C 30 A, D 40 B, E, F Frequent pattern Support {A} 75% {B} 50% {C} {A, C} For rule A  C: support = support({A}{C}) = 50% confidence = support({A}{C})/support({A}) = 66.6%

9 挖掘關聯規則（Mining Association Rules）
大多數關聯規則挖掘演算法通常採用的一種策略 是，將關聯規則挖掘任務分解為如下兩個主要的 子任務: 頻繁項集產生（Frequent Itemset Generation） 其目標是發現滿足最小支持度閾值的所有項集，這些項集稱 作頻繁項集。 規則的產生（Rule Generation） 其目標是從上一步發現的頻繁項集中提取所有高置信度的規 則，這些規則稱作強規則（Strong Rule）。

10 頻繁項集產生（Frequent Itemset Generation）
格結構（Lattice Structure）

11 頻繁項集產生（Frequent Itemset Generation）
Brute-force 方法: 把格結構中每個項集作為候選項集 將每個候選項集和每個事務進行比較，確定每個候選項集 的支持度計數。 時間複雜度 ~ O(NMw)，這種方法的開銷可能非常大。

12 降低產生頻繁項集計算複雜度的方法 減少候選項集的數量 (M) 減少比較的次數 (NM) 先驗(Apriori)原理
替代將每個候選項集與每個事務相匹配，可以使用更高 級的數據結構，或存儲候選項集或壓縮數據集，來減少 比較次數

13 先驗原理（ Apriori principle）
先驗原理: 如果一個項集是頻繁的，則它的所有子集一定也是頻繁 的 相反，如果一個項集是非頻繁的，則它的所有超集 合也一定是非頻繁的: 這種基於支持度度量修剪指數搜索空間的策略稱為基於 支持度的剪枝（Support-based pruning） 這種剪枝策略依賴於支持度度量的一個關鍵性質，即一 個項集的支持度決不會超過它的子集的支持度。這個性 質也稱為支持度度量的反單調性（Anti-monotone）。

14 先驗原理的圖示 發現是非頻繁的 被剪枝的超集合

15 Apriori演算法的頻繁項集產生

16 Apriori演算法的頻繁項集產生 支持度閾值=60% 最小支持度計數 = 3 Items (1-itemsets)
Pairs (2-itemsets) 支持度閾值=60% 最小支持度計數 = 3 Triplets (3-itemsets) 枚舉所有項集將產生 C61+ C62 + C63 = 41個候選 而使用先驗原理，將較少為 = 13

17 Apriori偽代碼（一） 演算法：Apriori。使用逐層反覆運算方法基於候選產生找出頻繁項集。 return L=UkLk； 輸入：
D:實物數據庫； Min_sup:最小支持度計數閾值。 輸出：L：D中的頻繁項集。 方法： L1=find_frequent_1-itemsets(D); for(k=2;Lk-1 !=￠；k++){ Ck=apriori_gen(Lk-1); For each 事務 t∈D{//掃描D用於計數 Ct=subset(Ck,t);//得到t的子集，它們是候選 for each候選c∈C; C.count++; } Lk={c∈C|c.count>=min_stp} return L=UkLk；

18 Apriori偽代碼 Procedure apriori_gen(Lk-1:frequent(k-1)-itemsets)
for each項集l1∈Lk-1 for each項集l2∈Lk-1 If (l1[1]=l2[1]) ^ (l1[2]=l2[2]) ^… (l1[k-2]=l2[k-2]) ^ (l1[k-1]=l2[k-1]) then{ c=l1∞l2//連接步：產生候選 if has_infrequent_subset(c,Lk-1)then delete c;//剪枝部；刪除非頻繁的候選 else add c to Ck； } return Ck； procedure has_infrequent_subset (c:candidate k-itemset; Lk-1：frequent (k-1)-itemset)//使用先驗知識 for each(k-1)-subset s of c If s∉ Lk-1then return TRUE; return FALSE;

19 Apriori 演算法 Apriori演算法的頻繁項集產生的部分有兩個重要的 特點：
它是一個逐層演算法。即從頻繁1-項集到最長的頻繁項 集，它每次遍歷項集格中的一層 它使用產生-測試策略來發現頻繁項集。在每次反覆運 算，新的候選項集由前一次反覆運算發現的頻繁項集產 生，然後對每個候選的支持度進行計數，並與最小支持 度閾值進行比較。 該演算法需要的總反覆運算次數是kmax+1，其中kmax是 頻繁項集的最大長度

20 候選的產生與剪枝(構造apriori-gen函數)
蠻力方法 蠻力方法把所有的k-項集都看作可能的候選，然後使用 候選剪枝除去不必要的候選 第k層產生的候選項集的數目為 雖然候選產生是相當簡單的，但是候選剪枝的開銷極大 ，因為必須考察的項集數量太大。 設每一個候選項集所需的計算量為O（k），這種方法 的總複雜度為

21 候選的產生與剪枝 候選產生 項 圖 產生候選3-項集的蠻力方法 項集 {啤酒、麵包、可樂} {啤酒、麵包、尿布} {啤酒、麵包、牛奶} 項集
{啤酒、麵包、雞蛋} {啤酒、可樂、尿布} {啤酒、可樂、牛奶} {啤酒、可樂、雞蛋} {啤酒、尿布，牛奶} {啤酒、尿布、雞蛋} {啤酒、牛奶、雞蛋} {麵包、可樂、尿布} {麵包、可樂、牛奶} {麵包、可樂、雞蛋} {麵包、尿布、牛奶} {麵包、尿布、雞蛋} {麵包、牛奶、雞蛋} {可樂、尿布、牛奶} {可樂、尿布、雞蛋} {可樂、牛奶、雞蛋} {尿布、牛奶、雞蛋} 項 項 啤酒 麵包 可樂 尿布 牛奶 雞蛋 候選剪枝 項集 {麵包、尿布、牛奶} 圖 產生候選3-項集的蠻力方法

22 候選的產生與剪枝 這種方法用其他頻繁項來擴展每個頻繁（k-1）-項集
這種方法將產生 個候選k-項集，其中|Fj|表示頻繁j-項 集的個數。這種方法總複雜度是 這種方法是完全的，因為每一個頻繁k-項集都是由一個頻繁（k-1 ）-項集和一個頻繁1-項集組成的。因此，所有的頻繁k-項集是這 種方法所產生的候選k-項集的一部分。 然而，這種方法很難避免重複地產生候選項集。 如：{麵包，尿布，牛奶}不僅可以由合併項集{麵包，尿布}和{牛奶 }得到，而且還可以由合併{麵包，牛奶}和{尿布}得到，或由合併{ 尿布，牛奶}和{麵包}得到。

23 候選的產生與剪枝 圖 通過合併頻繁（k-1）-項集和頻繁1-項集生成和剪枝候選k-項集。 注意：某些候選是不必要，因為它們的子集是非頻繁的
頻繁2-項集 項 {啤酒、尿布} {麵包、尿布} {麵包、牛奶} {尿布、牛奶} 候選產生 項集 {啤酒、尿布、麵包} {啤酒、尿布、牛奶} {麵包、尿布、牛奶} {麵包、牛奶、啤酒} 候選剪枝 項集 {麵包、尿布、牛奶} 頻繁1-項集 項 啤酒 麵包 尿布 牛奶 圖 通過合併頻繁（k-1）-項集和頻繁1-項集生成和剪枝候選k-項集。 注意：某些候選是不必要，因為它們的子集是非頻繁的

24 候選的產生與剪枝 避免產生重複的候選項集的一種方法是確保每個頻繁項集中的項 以字典序存儲，每個頻繁（k-1）-項集X只用字典序比X中所有的 項都大的頻繁項進行擴展 如：項集{麵包，尿布}可以用項集{牛奶}擴展，因為“牛奶”（ Milk）在字典序下比“麵包”（Bread）和“尿布”（Diapers）都 大。 儘管這種方法比蠻力方法有明顯改進，但是仍然產生大量不必要 的候選。 例如，通過合併{啤酒，尿布}和{牛奶}而得到的候選是不必要的。 因為它的子集{啤酒，牛奶}是非頻繁的。

25 候選的產生與剪枝 這種方法合併一對頻繁（k-1）-項集，僅當它們的前k-2 個項都相同。
如頻繁項集{麵包，尿布}和{麵包，牛奶}合併，形成了 候選3-項集{麵包，尿布，牛奶}。演算法不會合併項集 {啤酒，尿布}和{尿布，牛奶}，因為它們的第一個項不 相同。 然而，由於每個候選都由一對頻繁（k-1）-項集合並而 成，因此，需要附加的候選剪枝步驟來確保該候選的 其餘k-2個子集是頻繁的。

26 候選的產生與剪枝 圖 通過合併一對頻繁（k-1）-項集生成和剪枝候選k-項集 項 {啤酒、尿布} {麵包、尿布} 頻繁2-項集
{麵包、牛奶} {尿布、牛奶} 候選剪枝 候選產生 項集 {麵包、尿布、牛奶} 項集 {麵包、尿布、牛奶} 頻繁2-項集 項 {啤酒、尿布} {麵包、尿布} {麵包、牛奶} {尿布、牛奶} 圖 通過合併一對頻繁（k-1）-項集生成和剪枝候選k-項集

27 支持度計數 支持度計數過程確定在apriori-gen函數的候選項剪 枝步驟保留下來的每個候選項集出現的頻繁程度。 計算支持度的主要方法:
一種方法是將每個事務與所有的候選項集進行比較，並且更新包 含在事務中的候選項集的支持度計數。這種方法是計算昂貴的， 尤其當事務和候選項集的數目都很大時。 另一種方法是枚舉每個事務所包含的項集，並且利用它們更新對 應的候選項集的支持度。

28 枚舉事務t的所有包含3個項的子集

29 產生Hash樹 Hash函數h(p)=p mod 3 假設有15個候選3-項集: {1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8} 2 3 4 5 6 7 1 4 5 1 3 6 1 2 4 4 5 7 1 2 5 4 5 8 1 5 9 3 4 5 3 5 6 3 5 7 6 8 9 3 6 7 3 6 8 1,4,7 2,5,8 3,6,9 Hash function

30 Hash樹結構 Hash Function Candidate Hash Tree 1 5 9 1 4 5 1 3 6 3 4 5 3 6 7 3 6 8 3 5 6 3 5 7 6 8 9 2 3 4 5 6 7 1 2 4 4 5 7 1 2 5 4 5 8 1,4,7 3,6,9 2,5,8 Hash on 1, 4 or 7

31 Hash樹結構 Hash Function Candidate Hash Tree 1 5 9 1 4 5 1 3 6 3 4 5 3 6 7 3 6 8 3 5 6 3 5 7 6 8 9 2 3 4 5 6 7 1 2 4 4 5 7 1 2 5 4 5 8 1,4,7 3,6,9 2,5,8 Hash on 2, 5 or 8

32 Hash樹結構 Hash Function Candidate Hash Tree 1 5 9 1 4 5 1 3 6 3 4 5 3 6 7 3 6 8 3 5 6 3 5 7 6 8 9 2 3 4 5 6 7 1 2 4 4 5 7 1 2 5 4 5 8 1,4,7 3,6,9 2,5,8 Hash on 3, 6 or 9

33 使用Hash樹進行支持度計數 1 2 3 5 6 1 + 2 3 5 6 3 5 6 2 + 5 6 3 + transaction
1,4,7 2,5,8 3,6,9 Hash Function transaction 1 + 3 5 6 2 + 1 5 9 1 4 5 1 3 6 3 4 5 3 6 7 3 6 8 3 5 6 3 5 7 6 8 9 2 3 4 5 6 7 1 2 4 4 5 7 1 2 5 4 5 8 5 6 3 +

34 使用Hash樹進行支持度計數 1,4,7 2,5,8 3,6,9 Hash Function transaction 1 + 3 5 6 2 + 3 5 6 1 2 + 5 6 3 + 5 6 1 3 + 2 3 4 6 1 5 + 5 6 7 1 4 5 1 3 6 3 4 5 3 5 6 3 5 7 3 6 7 3 6 8 6 8 9 1 2 4 1 2 5 1 5 9 4 5 7 4 5 8

35 使用Hash樹進行支持度計數 1,4,7 2,5,8 3,6,9 Hash Function transaction 1 + 3 5 6 2 + 3 5 6 1 2 + 5 6 3 + 5 6 1 3 + 2 3 4 6 1 5 + 5 6 7 1 4 5 1 3 6 3 4 5 3 5 6 3 5 7 3 6 7 3 6 8 6 8 9 1 2 4 1 2 5 1 5 9 4 5 7 4 5 8 15個項集中的9個與事務進行比較

36 使用Hash樹進行支持度計數 存放在被訪問的葉結點中的候選項集與事務進行比 較，如果候選項集是該事務的子集，則增加它的支 持度計數；
在該例子中 ，訪問了9個葉子結點中的5個； 15個項集中的9個與事務進行比較。

37 計算複雜性 支持度閾值 項數 事務數 事務的平均寬度 降低支持度閾值通常將導致更多的項集是頻繁的。計算複雜度增加
隨著支持度閾值的降低，頻繁項集的最大長度將增加，導致演算法 需要掃描數據集的次數也將增多 項數 隨著項數的增加，需要更多的空間來存儲項的支持度計數。如果頻 繁項集的數目也隨著數據項目數增加而增長，則由於演算法產生的 候選項集更多，計算量和I/O開銷將增加 事務數 由於Apriori演算法反復掃描數據集，因此它的執行時間隨著事務數 增加而增加 事務的平均寬度 頻繁項集的最大長度隨事務平均寬度增加而增加 隨著事務寬度的增加，事務中將包含更多的項集，這將增加支持度 計數時Hash樹的遍歷次數

38 規則產生 忽略那些前件或後件為空的規則，每個頻繁k-項集 能夠產生多達2k-2個關聯規則
關聯規則的提取：將一個項集 Y劃分成兩個非空的 子集 X 和Y-X，使得X  Y–X滿足置信度閾值。 如果 {A,B,C,D} 是頻繁項集, 候選項集為: ABC D, ABD C, ACD B, BCD A, A BCD, B ACD, C ABD, D ABC AB CD, AC  BD, AD  BC, BC AD, BD AC, CD AB, 這樣的規則必然已經滿足支持度閾值，因為它們是 由頻繁項集產生的。

39 規則產生 怎樣有效的從頻繁項集中產生關聯規則?
一般，計算關聯規則的置信度並不需要再次掃描交易數 據集。規則{A,B,C} {D}的置信度為σ(ABCD)/ σ(ABC)。 因為這兩個項集的支持度計數已經在頻繁項 集產生時得到，因此不必再掃描整個數據集 如果規則X Y-X不滿足置信度閾值，則形如X‘Y-X’ 的規則一定也不滿足置信度閾值，其中X‘是X的子集。 例如：c(ABC  D)  c(AB  CD)  c(A  BCD) 因為σ(AB) σ(ABC)，則σ(ABCD)/ σ(ABC)  σ(ABCD)/ σ(AB) ，則c(ABC  D)  c(AB  CD)

40 規則產生的Apriori演算法 規則格 剪掉的規則 低置信度規則

41 Apriori偽代碼（三） H1 = ∅ //Initialize
foreach; frequent k-itemset fk , k ≥ 2 do begin A = (k − 1)-itemsets ak−1 such that ak−1 ⊂ fk ; foreach ak−1 ∈ A do begin con f = support( fk)/support(ak−1); if (con f ≥ mincon f ) then begin output the rule ak−1 ⇒ ( fk − ak−1) with confidence = conf and support = support( fk ); add ( fk − ak−1) to H1; end call ap-genrules( fk , H1);

42 Apriori偽代碼（四）

43 設定minsup=3/7，misconf=5/7。
關聯分析：舉例 假如有項目集合I={1，2，3，4，5}，有事務集T： Tid Items 1 1,2,3 2 1,2,4 3 1,3,4 4 1,2,3,5 5 1,3,5 6 2,4,5 7 1,2,3,4 設定minsup=3/7，misconf=5/7。

44 關聯分析：舉例 首先：生成頻繁項目集： 1-頻繁項目集：{1}，{2}，{3}，{4}，{5} 生成2-頻繁項目集：
　　1-頻繁項目集：{1}，{2}，{3}，{4}，{5} 　　生成2-頻繁項目集： 　　根據1-頻繁項目集生成所有的包含2個元素的項目集：任意取兩個只有最後一個元素不同的1-頻繁項目集，求其並集，由於每個1-頻繁項目集元素只有一個，所以生成的項目集如下： 　　{1，2}，{1，3}，{1，4}，{1，5} 　　{2，3}，{2，4}，{2，5} 　　{3，4}，{3，5} 　　{4，5} 　　計算它們的支持度，發現只有{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{2，5}的支持度滿足要求，因此求得2-頻繁項目集： 　　{1，2}，{1，3}，{1，4}，{2，3}，{2，4} 　　生成3-頻繁項目集： 　　因為{1，2}，{1，3}，{1，4}除了最後一個元素以外都相同，所以求{1，2}，{1，3}的並集得到{1，2，3}， {1，2}和{1，4}的並集得到{1，2，4}，{1，3}和{1，4}的並集得到{1，3，4}。但是由於{1，3，4}的子集{3，4}不在2-頻繁項目集中，所以需要把{1，3，4}剔除掉。然後再來計算{1，2，3}和{1，2，4}的支持度，發現{1，2，3}的支持度為3/7 ，{1，2，4}的支持度為2/7，所以需要把{1，2，4}剔除。同理可以對{2，3}，{2，4}求並集得到{2，3，4} ，但是{2，3，4}的支持度不滿足要求，所以需要剔除掉。 　　因此得到3-頻繁項目集：{1，2，3}。

45 關聯分析：舉例 到此頻繁項目集生成過程結束。注意生成頻繁項目集的時候，頻繁項目集中的元素個數最大值為事務集中事務中含有的最大元素個數，即若事務集中事務包含的最大元素個數為k，那麼最多能生成k-頻繁項目集，這個原因很簡單，因為事務集合中的所有事務都不包含（k+1）個元素，所以不可能存在（k+1）-頻繁項目集。在生成過程中，若得到的頻繁項目集個數小於2，生成過程也可以結束了。 　　現在需要生成強關聯規則： 　　這裡只說明3-頻繁項目集生成關聯規則的過程： 　　對於集合{1，2，3} 　　先生成1-後件的關聯規則： 　　（1，2）—>3，   置信度=3/4 　　（1，3）—>2，　置信度=3/5 　　（2，3）—>1      置信度=3/3 　　（1，3）—>2的置信度不滿足要求，所以剔除掉。因此得到1後件的集合{1}，{3}，然後再以{1，3}作為後件        2—>1，3       置信度=3/5不滿足要求，所以對於3-頻繁項目集生成的強關聯規則為：（1，2）—>3和（2，3）—>1。

46 R實戰-Apriori library(arules) data(Groceries) library(arulesViz)
rules = apriori(Groceries,parameter = list(support = 0.01,confidence = 0.2)) inspect(sort(rules,by="support")[1:6]) #按支持度查看前6條規則 inspect(sort(rules,by="confidence")[1:6]) #按置信度查看前6條規則 itemFrequencyPlot(Groceries,support = 0.05,cex.names =0.8) #數據畫頻繁項的圖 plot(rules, shading="order", control=list(main = "Two-key plot")) plot(rules, method="grouped") plot(rules, method="graph") lhs rhs support confidence lift 1 {} => {whole milk} 151 {other vegetables} => {whole milk} 152 {whole milk} => {other vegetables} 149 {rolls/buns} => {whole milk} 150 {whole milk} => {rolls/buns} 145 {yogurt} => {whole milk}

47 謝 謝！

48 附：產生頻繁項集的其他方法 交易數據庫的表示 水準數據佈局 vs 垂直數據佈局

49 FP增長演算法 使用交易數據庫的緊湊數據結構 － FP樹 一旦FP樹構建完成，該演算法使用一個遞迴的分 而治之的方法挖掘頻繁項集

50 FP樹的構建 null 讀入 TID=1 後: A:1 B:1 讀入 TID=2 後: null B:1 A:1 B:1 C:1
交易數據庫中已經去掉非頻 繁的項，並且事務中餘下的 項已按照支持度遞減排序 D:1

51 FP樹的構建 null B:3 A:7 B:5 C:3 C:1 D:1 D:1 C:3 E:1 D:1 E:1 D:1 E:1 D:1
交易數據庫 null B:3 A:7 B:5 C:3 C:1 D:1 頭指針表 D:1 C:3 E:1 D:1 E:1 D:1 E:1 D:1 指針用於輔助頻繁項集生成

52 FP增長過程 從D開始開始直到A逐個處理條件模式庫 關於D的條件模式庫是D的所有首碼路徑的集合：
P = {(A:1,B:1,C:1), (A:1,B:1), (A:1,C:1), (A:1), (B:1,C:1)} 對P遞迴應用FP增長過程 發現頻繁項集 (sup > 1): AD, BD, CD, ACD, BCD null A:7 B:1 B:5 C:1 C:1 D:1 D:1 C:3 D:1 D:1 D:1

53 ECLAT演算法 使用垂直數據佈局：對於每個項，保存事務ID列 表 (TID列表) TID列表

54   ECLAT演算法 通過計算兩個k-1子集的TID列表的交集，決定k-項集的TID 列表 三種遍歷方法: 優點: 計算支持度很快
自頂向下、自底向上和混合方法 優點: 計算支持度很快 缺點: 計算過程產生的TID清單可能佔用很大記憶體  