【導(dǎo)讀】系可以用關(guān)聯(lián)規(guī)則或頻繁項集的形式表示。目前，關(guān)聯(lián)規(guī)則挖掘已經(jīng)得到了廣。本文針對Apriori算法的不足，提出了一種改進(jìn)算法，并將其應(yīng)用于。挖掘?qū)W生成績，從而對優(yōu)化課程設(shè)置起到一定的指導(dǎo)作用。思想及產(chǎn)生頻繁項集和關(guān)聯(lián)規(guī)則的相關(guān)技術(shù)。剪枝直接產(chǎn)生候選k項集等技術(shù)，在一定程度上提升了挖掘頻繁項集的效率。同時，通過理論和實驗對兩種算法進(jìn)行了性能比較，驗證了改進(jìn)算法的優(yōu)越性。將關(guān)聯(lián)規(guī)則挖掘應(yīng)用于學(xué)生成績管理。在原有的教務(wù)管理系統(tǒng)學(xué)生成?？児芾砟K的基礎(chǔ)上，應(yīng)用Apriori改進(jìn)算法，采用20xxVB作為系統(tǒng)開發(fā)工具，該系統(tǒng)包括獲取數(shù)。據(jù)，數(shù)據(jù)預(yù)處理，關(guān)聯(lián)規(guī)則挖掘和規(guī)則結(jié)果分析四個模塊。合理設(shè)置提供了決策支持。程有了明顯的改善，教學(xué)效果有所提高，學(xué)生的課程通過率有所上升。

　　

【正文】 性質(zhì) , 和 。 對于圖 31 所示的事務(wù)，假定最小支持度計數(shù)是 3，應(yīng)用 Apriori 算法來驗證基于支持度的剪枝策略大大降低了產(chǎn)生頻繁項集的計算復(fù)雜度。 圖 32 給出了 Apriori 算法產(chǎn)生頻繁項集的一個高層實例。假設(shè)min_sup=60%。初始時每個項都被看作是候選 1 項集，當(dāng)給每個項計數(shù)支持度時，發(fā)現(xiàn) }{I5 和 }{I6 的支持度計數(shù)均小于 3，故被刪除。算法在 只有 4 個頻繁 1項集的情況下，產(chǎn)生了 624?C 個候選 ?2 項集。對其進(jìn)行計數(shù)后發(fā)現(xiàn) }I,{I 41 和}I,{I 42 均小于 3，因此被刪除。然后在僅有 4 個頻繁 ?2 項集的情況下，產(chǎn)生了1 個候選 3 項集，其計數(shù)是 3，因此保留。 通過實例，降低產(chǎn)生頻繁項集計算復(fù)雜度具體表現(xiàn)在，在枚舉所有項集到3 項集的方法中將產(chǎn)生 4120xx6C 362616 ?????? CC 個候選，而使用 Apriori 時，將減少為 131661C 2416 ?????? C 個候選，數(shù)目降低了 %。實際應(yīng)用中數(shù)據(jù)集將更大，那么利用剪枝策略的有效性將更顯著。 13 圖 3 2 基于支持度的剪枝策略的實例 (3)支持度計數(shù)策略 確定在候選項剪枝步驟保留下來的每個候選項集出現(xiàn)的頻繁程度是支持度計 數(shù)的主要工作。 [16]圖 31 費(fèi)力策略中顯示了一種計數(shù)方法，就是每個事務(wù)與所有的候選項集進(jìn)行比較并且更新計數(shù)，顯然不可取，尤其是在事務(wù)和候選項集的數(shù)據(jù)都很大的情況下。 另外一種方法是利用前綴結(jié)構(gòu)，即通過從最左項到最右項依次指定項集的項的方式，將每個事務(wù)所包含的項集系統(tǒng)地枚舉出來，然后利用它們更新對應(yīng)的候選項集的支持度。 還有一種方法是利用 Hash 樹，即將包含在事務(wù)中的項集散列到相應(yīng)的桶中，只要將事務(wù)中的每個項集與同一桶內(nèi)的候選項集進(jìn)行匹配就可以了 。 以上幾種方法都是針對減少數(shù) 據(jù)庫的掃描 和 比較次數(shù)而設(shè)計的，我們還可以結(jié)合基于支持度的剪枝策略對事務(wù)數(shù)據(jù)庫進(jìn)行壓縮，這樣記錄減少，計數(shù)開銷也就少了。 (4) 利用 growthFP 算法 growthFP 算法在保留項集關(guān)聯(lián)信息的基礎(chǔ)上，利用 treeFP? 的緊湊數(shù)據(jù)結(jié)構(gòu)組織數(shù)據(jù)，不產(chǎn)生候選項集，直接從 treeFP? 中提取頻繁項集。 下面將用三步描述此算法： 掃描 D，對每個候選計數(shù) 項集 { I1 ,I2 } { I1 ,I3 } { I1 ,I4 } { I2, I3 } { I2 ,I4 } { I3 ,I4 } 支持度計 數(shù) 4 4 5 3 1 2 刪除候選支持度計數(shù)小于最小支持度計數(shù)的項集 C1 項集 I1 I2 I3 I4 支持度計 數(shù) 4 4 5 3 L1 由 L1 產(chǎn)生候選 C2 ，并對每個候選計數(shù) 項集 I1 I2 I3 I4 I5 I6 C2 支持度計 數(shù) 3 4 2 4 2 3 刪除候選支持度計數(shù)小于最小支持度計數(shù)的項集 項集 { I1 ,I2 } { I1 ,I3 } { I2, I3 } { I3 ,I4 } 支持度計 數(shù) 3 4 4 3 L2 由 L 2 產(chǎn)生候選 C3 ，并對每個候選計數(shù) 項集 { I1 ,I2,I3 } 支持度計 數(shù) 3 C3 項集 { I1 ,I2,I3 } 支持度計 數(shù) 3 L3 14 ① 已知 min_sup ，掃描數(shù)據(jù)庫 D，產(chǎn)生頻繁 1 項集，并按支持度計數(shù)遞減排序，生成結(jié)果集 L。 ② 構(gòu)造 treeFP? 。 首先創(chuàng)建并用 “nul ”標(biāo)記樹的根結(jié)點，然后掃描數(shù)據(jù)庫，并對每個事務(wù)中的項按 L 中的次序處理，并建立一個分枝 ； 如果要給一個事務(wù)增加分枝，首先將與此結(jié)點有共同前綴上的每個結(jié)點的計數(shù)都增加 1，然后為跟隨在前綴之后的項創(chuàng)建結(jié)點，并將其鏈接。 [17]為了遍歷樹方便，通常用項目頭，這樣每個項就可以通過一個結(jié)點鏈指向它在樹中的出現(xiàn)。 ③ treeFP? 的挖掘，即頻繁模式的挖掘。 從長度為 1 的頻繁模式開始，由 treeFP? 中與后綴模式一起出現(xiàn)的前綴路徑集構(gòu)造它的條件模式基 ； 然后構(gòu)造它的條件 treeFP? ，并遞歸地在該樹上進(jìn)行挖掘 ； 通過后綴模式與由條件 treeFP? 產(chǎn)生的頻繁模式連接，來實現(xiàn)模式增長。[1 8 ]下面圖 33 給出了 growthFP 算法。 圖 3 3 FPgrowth 算法偽代碼 15 例 已知事務(wù)數(shù)據(jù)庫 D， |D|=5， 60%min_sup ? ，并按字典次序存放事務(wù)中的項，利用 growthFP? 算法挖掘頻繁項集。 表 3 1 事務(wù)數(shù)據(jù)庫 D TID 項 ID 的列表 T1 a， b， f， m， p T2 a， b， c， f， m T3 a， c， e T4 c， d， f， p T5 a， b， d， f， m， p 第一步，如圖 34 所示，生成 L1 和結(jié)果集 L。 圖 3 4 FPgrowth 算法挖掘流程第一步 第 二 步 ， 掃 描 數(shù) 據(jù) 庫 D ， 對 事 務(wù) 中 的 每 個 項 按3]:p3,:m3,:c3,:b4,:f4,:[aL ? 中的次序排列，并構(gòu)造 treeFP? 。 表 3 2 按結(jié)果集 L 中的次序處理 D 中的每個事務(wù)的項 TID 項 ID 的列表 T1 a， f， b， m， p T2 a， f， b， c， m T3 a， c T4 f， c， p T5 a， f， b， m， p 具體 treeFP? 構(gòu)造如下： 首先，創(chuàng)建 treeFP? 的根結(jié)點，標(biāo)記為 “null”，然后根據(jù)表 32 中每個處理過的事務(wù)創(chuàng)建相應(yīng)的分枝，構(gòu)建 treeFP? ，這里處理過的事務(wù)是指只包括頻繁掃描 D，對每個候選計數(shù) 項集 a b c d e f m p 支持度計 數(shù) 4 3 3 2 1 4 3 3 刪除候選支持度計數(shù)小于最小支持度計數(shù)的項集 C1 項集 a b c f m p 支持度計 數(shù) 4 3 3 4 3 3 L1 頻繁項的集合按支持度計數(shù) 遞減排序 結(jié)果集 L 項集 a f b c m p 支持度計 數(shù) 4 4 3 3 3 3 16 項，且頻繁項已按結(jié)果集 L 排序。對于第一個事務(wù) pm,b,f,a,:T1 ，可構(gòu)造樹的第一個分枝 ?? 1):(p1) ,:(m1) ,:(b1) ,:(f1) ,:a( ，該分枝具有 5 個結(jié)點，其中， a 作為根的子女鏈接， f 鏈接到 a， b 鏈接到 f， m 鏈接到 b， p 鏈接到 m。 [18]對于第二個事務(wù) m,c,b,f,a:2T ， 由 于 它 與 treeFP? 的 第 一 個 分 枝?? 1):(p1) ,:(m1) ,:(b1) ,:(f1) ,:a( 有共享前綴 ?? bf,a, ，所以將共享前綴的計數(shù)均增加 1，此時第一個分枝變?yōu)??? 1):(p1) ,:(m2) ,:(b2) ,:(f2) ,:a( ，對于 T2 中剩余的頻繁項，按順序創(chuàng)建新的結(jié)點 1):(c 和 1):(m ，使 1):(c 作為 2):(b 的子女鏈接，m 鏈接到 c。對于第三個事務(wù) ca,:T3 ，創(chuàng)建的分枝應(yīng)當(dāng)與已存在的路徑共享前綴 ??a ，所以將結(jié)點 a 的計數(shù)加 1，并創(chuàng)建一個新的結(jié)點 1):(c ，使 1):(c 作為 3):(a的子女鏈接。對于第四個事務(wù) pc,f,:T4 ，由于不共享任何前綴，所以創(chuàng)建一個新的分枝 ?? 1):(p1) ,:(c1) ,:f( ，其中 f 作為根的子女鏈接， c 鏈接到 f， p 鏈接到c。對于第五個事務(wù) pm,b,f,a,:T5 ，由于它與 第一個事務(wù)相同，這條路徑被共享，直接將該路徑上的每個結(jié)點計數(shù)均加 1 就可以了。為方便樹的遍歷，通常需要創(chuàng)建一個項目頭，它由項 ID，對應(yīng)的支持度計數(shù)和結(jié)點鏈組成，每個項可以通過一個結(jié)點鏈指向它在樹中的出現(xiàn)。這樣就構(gòu)造出了 treeFP? ，并帶有相關(guān)的結(jié)點鏈，從而使挖掘數(shù)據(jù)庫頻繁模式的問題轉(zhuǎn)換成了挖掘 treeFP? 的問題。 圖 3 5 根據(jù)表 31 構(gòu)建的 FPtree 第三步，挖掘 treeFP? 。按項頭表從表尾到表頭的順序挖掘 treeFP? 生成條件模式基，構(gòu)造條件 treeFP? 。 對于圖 34 中構(gòu)建的 treeFP? ，從項頭表中最后一個頻繁項 p 開始，由項頭表中 p 的結(jié)點鏈，可知在圖 34 的 treeFP? 中 p 出現(xiàn)在兩個分枝上，分別為項 ID a f b c m p 支持度 計數(shù) 4 4 3 3 3 3 結(jié)點鏈 null{} a： 4 f： 3 b： 3 m： 2 p： 2 c： 1 c： 1 m： 1 f： 1 c： 1 p： 1 17 ?? 2):(p2) ,:(m3) ,:(b3) ,:(f4) ,:a( 和 ?? 1):(p1) ,:(c1) ,:f( ，考慮 p 作為后綴，它的兩個對應(yīng)前綴的路徑為 ?? 2):mb,f,a,( 和 ?? 1):cf,( ，構(gòu)成了 p 的條件模式基。由于最小支持度計數(shù)是 3，所以產(chǎn)生一個單結(jié)點的 p 的條件 treeFP? ?? 3:f ，并導(dǎo)出一個頻繁模式是 3:p f 。 對于項頭表中倒數(shù)第二個頻繁項 m，由項頭表中 m 的結(jié)點鏈，考慮 m 作為后綴，可知它的對應(yīng)前綴路徑為 ?? 2):bf,a,( 和 ?? 1):cb,f,a,( ，從而構(gòu)成了 m的條件模式基。 m 的條件 treeFP? 只包含單個路徑 ?? 3):b3,:f3,:(a ，不包含 c，因為它的支持度計數(shù)為 1，小于最小支持度計數(shù) ； 該單個路徑產(chǎn)生的頻繁模式的所有組合有 3:m b f a3,:m b f3,:m b a3,:m f a3,:m b3,:m f3,:m a 。 [17] 利用相同的分析方法，可以得到項頭表中其他頻繁項的條件模式基和條件treeFP? ，并導(dǎo)出相應(yīng)的頻繁模式。具體 treeFP? 的挖掘結(jié)果總結(jié)在表 33 中。 表 3 3 挖掘圖 34 的 FPtree 的結(jié)果 項 條件模式基 條件 treeFP? 產(chǎn)生的頻繁模式 p 1) }:c(f,2) ,:mb,f,{ ( a , ?? 3:f 3:p f m 1) }:cb,f,( a ,2) ,:bf,{ ( a , ?? 3:b3,:f3,:a 3,:m b3,:m f3,:m a 3,:m b f3,:m b a3,:m f a 3:m b f a c 1) }:bf,( a ,1) ,:(f1) ,:{ ( a ? ? b 3)}:f{(a, ?? 3:f3,:a 3:b f a3,:b f3,:b a f 3)}:{(a ?? 3:a 3:f a growthFP? 算法有其優(yōu)缺點，相對 Apriori 算法，優(yōu)點在于它避免產(chǎn)生大量的候選項集并減少了掃描數(shù)據(jù)庫的次數(shù)，尤其適合挖掘長的和短的頻繁模 式。缺點在于當(dāng)數(shù)據(jù)庫很大時，構(gòu)造基于內(nèi)存的 treeFP? 是不現(xiàn)實的并且生成的條件 treeFP? 是一棵滿前綴樹更會影響算法效率。 (5) 產(chǎn)生頻繁項集的其他方法 ① 遍歷項集格的策略主要包括以下幾種策略： “一般到特殊 ” 的遍歷策略，即合并兩個頻繁 ??1)(k 項集得到候選 ?k 項集， Apriori 算法使用的就是這個策略，它對于頻繁項集的最大長度不是太長的情況是有效的。 “特殊到一般 ”的遍歷策略是在發(fā)現(xiàn)更一般的頻繁項集之前，先尋找更特殊的頻繁項集，它對于發(fā)現(xiàn)稠密事務(wù)中的極大頻繁項集比較有用。 結(jié)合 “一般到特殊 ”和 “特殊到一般 ”的遍歷策略，它需要更多的空間存儲候選項集以便進(jìn)行雙向搜索，但有助于快速確定頻繁項集邊界。 還有一種方法是先將格劃分為兩個不相交的等價類，在每個等價類內(nèi)依次用頻繁項集產(chǎn)生算法搜索頻繁項集?？梢愿鶕?jù)項集的前綴或后綴來定義等價類。 另外，也可以采用寬度優(yōu)先或深度優(yōu)先的方法遍歷格，通常深度優(yōu)先遍歷 18 方法用于發(fā)現(xiàn)極大頻繁項集的算法，一旦發(fā)現(xiàn)就可以在它的子集上進(jìn)行剪 枝，它比寬度優(yōu)先能更快速地檢測到頻繁項集邊界，而且可以使用不同的基于項集支持度的剪枝方法。 ② 事務(wù)數(shù)據(jù)集的表示方法。它是影響候選項集支持度的計