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

　　

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