基于改進的FP-growth算法的高校課程關(guān)聯(lián)度實證研究

葉福蘭

(福州外語外貿(mào)學院 理工學院， 福州 350202)

黨的十八大以來，我國高度重視高等教育的發(fā)展，習近平總書記指出：“高等教育是一個國家發(fā)展水平和發(fā)展?jié)摿Φ闹匾獦酥尽?。高等教育作為社會發(fā)展的動力之源，肩負著培養(yǎng)新時代社會主義事業(yè)建設(shè)者和接班人的重要使命。近些年來，我國相繼出臺了《教育信息化2.0行動計劃》等一系列相關(guān)政策法規(guī)，將數(shù)據(jù)挖掘技術(shù)應用于教學管理中有助于提升教學管理的質(zhì)量與水平。學生成績是衡量教學質(zhì)量的重要指標，然而多數(shù)研究側(cè)重從縱向角度針對單門課程開展研究，從橫向角度分析各課程之間的內(nèi)在關(guān)聯(lián)則少之又少。挖掘課程內(nèi)在關(guān)聯(lián)，合理設(shè)置課程開設(shè)學期，厘清課程前導與后續(xù)關(guān)系，優(yōu)化人才培養(yǎng)方案，對提高學生學習效果、提升學生專業(yè)知識系統(tǒng)化水平具有重要意義。

1 Fp-growth算法概述

關(guān)聯(lián)規(guī)則是指對給定的數(shù)據(jù)庫集中的事務進行挖掘，尋找內(nèi)在數(shù)據(jù)項之間的內(nèi)在關(guān)系，支持度與置信度是關(guān)聯(lián)規(guī)則挖掘的兩個重要指標。對于形如“A=>B”的關(guān)聯(lián)規(guī)則，支持度是指事務數(shù)據(jù)集中同時包含A和B的概率，如公式(1)所示；置信度是指包含A和B的事務數(shù)占包含A的事務數(shù)的百分比，如公式(2)所示。關(guān)聯(lián)規(guī)則挖掘中最具代表性的算法是Apriori算法，Apriori算法是一種“產(chǎn)生-測試”型的關(guān)聯(lián)規(guī)則挖掘算法，通過不斷逐次迭代生成候選項集，結(jié)合最小支持度計數(shù)及先驗原理，求出候選項集。先驗原理：如果一個項集是頻繁，那么它的所有非空子集也是頻繁。[1]

Sup(A=>B)=P(A∪B)

(1)

(2)

FP-growth算法是基于Apriori算法基礎(chǔ)上提出的另一種關(guān)聯(lián)規(guī)則挖掘算法，旨在解決關(guān)聯(lián)規(guī)則經(jīng)典算法Apriori算法中存在的缺陷而提出的一種改進算法。FP-growth算法挖掘過程主要包括FP-tree構(gòu)建過程以及根據(jù)FP-tree挖掘頻繁模式兩大步驟。FP-growth算法與Apriori算法的主要區(qū)別如下：

1)Apriori算法每生成一個候選項集均需要對數(shù)據(jù)庫進行掃描；而FP-growth算法只需掃描兩次數(shù)據(jù)庫，第一次掃描數(shù)據(jù)集生成1-頻繁項集，并按支持度計數(shù)降序原則存儲于Head表中，第二次掃描數(shù)據(jù)集，將所有的項集存儲于FP樹中。

2)Apriori算法形成大量的候選項集；而FP-growth算法利用類似樹形結(jié)構(gòu)來存儲數(shù)據(jù)庫集中的項集信息，通過樹的路徑來表示事務。

FP-growth算法中頻繁模式的挖掘過程是基于所構(gòu)造的FP-tree，從Head表中支持度計數(shù)最小的項開始，采用分而治之的策略，通過所有的前綴路徑，確定條件模式基，構(gòu)造FP-tree，生成頻繁項。FP-growth算法將數(shù)據(jù)庫集中的事務信息壓縮到FP-tree中存儲，減少了掃描數(shù)據(jù)庫所造成的巨大I/O開銷，在空間和時間上都提高了效率。

2 FP-growth算法的改進

在應用FP-growth算法進行挖掘較大規(guī)模數(shù)據(jù)庫時，所構(gòu)建的FP-tree會占用大量的存儲空間；同時，每生成一個頻繁模式也生成了一棵FP-tree，在時間和空間上影響了算法的效率。針對FP-growth算法存在的缺點，不少人提出了改進算法。文獻[2]利用鄰接矩陣存儲數(shù)據(jù)項的支持度計數(shù)，減少不相關(guān)的數(shù)據(jù)項，從而實現(xiàn)對FP-tree進行減枝；文獻[3]結(jié)合挖掘目標篩選出相關(guān)的特定數(shù)據(jù)項進行分析，減少頻繁模式挖掘的次數(shù)；文獻[4]通過引入權(quán)重來區(qū)別數(shù)據(jù)項在事務中的重要性程度；文獻[5]采用哈希頭表代表FP-growth算法中的項頭表，并通過合并最小支持度計數(shù)相同的節(jié)點實現(xiàn)壓縮FP-tree;文獻[6]采用有序樹代替?zhèn)鹘y(tǒng)FP-tree并采用列表記錄數(shù)據(jù)項的頻繁度，從而減少存儲空間及遍歷FP樹的次數(shù)。綜上，算法的改進主要從減少不相關(guān)的數(shù)據(jù)項和只對特定相關(guān)的數(shù)據(jù)項進行頻繁模式挖掘兩大方面著手。

2.1 算法改進思路

針對以上提出的FP-growth算法存在的不足，本文提出了基于二維表存儲事務數(shù)據(jù)的改進算法BTFP-growth。改進算法的主要原理描述如下：

1)掃描事務數(shù)據(jù)庫，用二維表存儲對應的所有數(shù)據(jù)項及每個事務數(shù)據(jù)，行表示數(shù)據(jù)項，列表示對應的事務，若數(shù)據(jù)項在某事務中存在，該數(shù)據(jù)項對應行所在的事務列中對應的值用1表示，否則用0表示；

2)對生成的二維表通過累加“和”的方法求各數(shù)據(jù)項的支持度計數(shù)，從而刪除不滿足最小支持度計數(shù)的數(shù)據(jù)項，并將二維表按照支持度計數(shù)降序排列；

3)運用邏輯“與”以及累加“和”運算求得任意兩項的支持度計數(shù)，求得頻繁2項集及非頻繁2項集；

4)根據(jù)生成的二維表創(chuàng)建FP-tree；

5)結(jié)合FP-growth算法挖掘頻繁項集，從項頭表的最后一項開始到倒數(shù)第3項結(jié)合先驗原理刪除包含非頻繁2項集的數(shù)據(jù)項，求包含3項以上的頻繁項集。

算法的偽代碼如下[7]：

Input:事務數(shù)據(jù)庫D以及最小支持度閾值Minsup；

Output：所有的頻繁項集。

FP-tree構(gòu)造算法:

Build_FP_tree(D,Minsup,T)

1)掃描事務數(shù)據(jù)庫D；

2)生成二維表，將事務數(shù)據(jù)庫中的每個事務存在二維表中，行表示數(shù)據(jù)項，列表示每個事務，分別用0和1表示數(shù)據(jù)項在事務中是否出現(xiàn)。對二維表求每個數(shù)據(jù)項的支持度計數(shù)，刪除低于最小支持度的項，并將二維表按照支持度計數(shù)調(diào)整行的順序，生成的二維表用AT表示；

3)根據(jù)生成的二維表AT，生成頻繁1項集與頻繁2項集的組合，同時生成非頻繁2項集；

4)創(chuàng)建T的根結(jié)點，根據(jù)二維表AT，調(diào)用經(jīng)典FP-growth算法中的insert_tree算法生成FP樹T。

改進的算法BTFP-growth(T,α)：

IF (T 包含單個路徑P) TEHN

FOR P中每個三項以上的結(jié)點組合β DO

產(chǎn)生模式β∪α，其支持度設(shè)為β中結(jié)點的最小支持度；

ELSE FOR each ai(項頭表H最后一項到倒數(shù)第3項) DO

{產(chǎn)生模式β=ai∪α，支持度support=ai·support

構(gòu)造β的條件模式基，若路徑包含非頻繁2項集，刪除另外一個數(shù)據(jù)項，同時只選擇包含3項數(shù)據(jù)項以上的路徑，構(gòu)建條件條件FP樹Tβ

IF (Tβ≠Φ) THEN

調(diào)用BTFP-growth(T,α)}

2.2 改進算法案例分析

設(shè)有如表1某事務數(shù)據(jù)，該數(shù)據(jù)庫包含9個事務，設(shè)最小支持度計數(shù)為3，改進算法挖掘事務數(shù)據(jù)庫頻繁項集過程如下：

表1 事務數(shù)據(jù)

1)掃描事務數(shù)據(jù)庫，生成二維表，二維表的行表示數(shù)據(jù)項，列表示某事務，1表示數(shù)據(jù)項在該事務中出現(xiàn)，0表示不出現(xiàn)，在生成的二維表中使用累加“和”求得各數(shù)據(jù)項的支持度計數(shù)分別為a:7,b:6,c:6,d:5,e:2。刪除支持度計數(shù)低于最小支持度計數(shù)3的數(shù)據(jù)項e，然后將二維表按照支持度計數(shù)降序原則重新排列元組，最后生成的二維表如表2所示。

表2 事務二維表

2)根據(jù)生成的事務二維表，對任意兩個數(shù)據(jù)項在同一事務中的值進行邏輯“與”運算，并將求得的邏輯“與”值進行累加，求得兩個數(shù)據(jù)項的支持度計數(shù)，如數(shù)據(jù)項a與b同時出現(xiàn)的支持度計數(shù)為：1&&0+0&&1+1&&1+0&&1+1&&0++1&&1+1&&1+1&&1+1&&0=4。同理，求得ac,ad,bc,bd,cd的支持度計數(shù)分別為4,5,4,3,2，刪除支持度小于3的cd項，求得頻繁2項集為{ab,ac,ad,bc,bd}，非頻繁項集為{cd}。

3)根據(jù)表2的事務二維表以及所求得的支持度計數(shù)，創(chuàng)建FP-tree，如圖1所示。

圖1 FP-tree

4)從支持度最低的d項開始，向上找出3項以上的路徑(因為頻繁1項集合、頻繁2項集已找到){a,c,d:1},{a,b,d:2},{a,b,c,d:1},得到的3項以上的集合有{a,c,d:2},{a,b,d:3},{b,c,d:1},{a,b,c,d:1}，結(jié)合最小支持度計數(shù)3及非頻繁2項集，得到3項以上的頻繁項集為{a,b,d:3}。

5)同理，挖掘項c的頻繁模式，3項以上的集合只有{a,b,c:2}，不滿足最小支持度計數(shù)要求。對項b和項a由于最多只得到頻繁1項集或者頻繁2項集，前面步驟中均已求出，因此結(jié)束頻繁模式挖掘過程。

3 改進算法在高校課程關(guān)聯(lián)度分析中的應用

3.1 實驗環(huán)境介紹

本實驗環(huán)境為Window 10操作系統(tǒng)的PC機，系統(tǒng)配置為CPU:Intet i7-7500U、內(nèi)存：4G、硬盤：1T；數(shù)據(jù)的預處理采用Excel與Weka相結(jié)合；數(shù)據(jù)的實驗過程采用Weka 3.8實現(xiàn)。Weka是新西蘭懷卡大學開發(fā)的數(shù)據(jù)挖掘軟件，采用JAVA語言編寫，除了自身具備強大的數(shù)據(jù)預處理功能外，最重要的一個特點是該軟件開源，用戶可以在原算法基礎(chǔ)上進行改進。Weka所支持的數(shù)據(jù)文件格式有：arff、csv、xls/xlsx及json等。Weka雖支持xls/xlsx格式，但需要將其轉(zhuǎn)換為csv格式后才能直接打開，本文的實驗數(shù)據(jù)源文件為xlsx格式，通過EXCEL基本處理后另存為csv格式。為了方便對設(shè)置各屬性的類型，通過Weka打開數(shù)據(jù)源后，將其轉(zhuǎn)為arff格式進行處理。

3.2 數(shù)據(jù)準備

本實驗數(shù)據(jù)從學校的教務管理系統(tǒng)導出，數(shù)據(jù)選擇某校近幾屆信息管理與信息系統(tǒng)畢業(yè)生的原始成績作為分析的數(shù)據(jù)源，鑒于本文只研究專業(yè)課程的內(nèi)在關(guān)聯(lián)，故過濾不相關(guān)的字段，只保留專業(yè)基礎(chǔ)課、限選課、任選課，由于集中性實踐環(huán)節(jié)一般緊跟某門專業(yè)課而開設(shè)，在此也不考慮。針對不同年級培養(yǎng)方案修訂導致課程差異問題，采取相似課程替換方法進行數(shù)據(jù)集成，整理后的數(shù)據(jù)如表3所示，考慮個人隱私問題，刪除學號與姓名列，用序號作為關(guān)鍵字。

表3 學生成績原始數(shù)據(jù)

3.3 數(shù)據(jù)預處理

1)數(shù)據(jù)清洗。從教務系統(tǒng)導出的數(shù)據(jù)存在缺失的情況，缺失的原因有：①學生中途轉(zhuǎn)入或轉(zhuǎn)出該專業(yè)，部分課程成績?nèi)笔?；②由于人才培養(yǎng)方案中設(shè)置了專業(yè)方向，學生修讀不同方向課程，導致其他方向課程成績?nèi)笔В虎廴瞬排囵B(yǎng)方案中設(shè)置了專業(yè)任選課，導致未選修的課程信息缺失。

針對①的情況，因數(shù)量不多，為了避免影響挖掘結(jié)果，故將該部分記錄直接刪除；針對②③兩種情況，由于不同方向的學生或不同選修課學生所選修的課程門數(shù)均相同，所以對課程進行合并，如將《Web高級編程》與《ERP原理與應用》兩門課進行合并。

2)數(shù)據(jù)離散化。受教師批改試卷標準、試卷難度等因素影響，學生的成績分布未必成正態(tài)分布，不具可比性，若直接進行轉(zhuǎn)換，則存在各課程之間不平衡問題影響挖掘結(jié)果。利用WEKA預處理功能中的Filters選項組中的無監(jiān)督數(shù)值標準化方法Standardizes對成績信息進行標準化轉(zhuǎn)換，進而按比例進行離散化處理：A:5%，B:25%，C:40%，D:25%，E:5%，轉(zhuǎn)換后的部分數(shù)據(jù)如表4所示。同時，將WEKA安裝包中RunWeka.ini文件中的fileEncoding參數(shù)改為utf-8，使其支持中文。

表4 離散化后的數(shù)據(jù)

3.4 實驗結(jié)果分析

實驗過程中設(shè)置minsup=10% ,mincon=80%，執(zhí)行改進的FP-growth關(guān)聯(lián)規(guī)則挖掘算法BTFP-growth后，部分挖掘結(jié)果如表5所示。

表5 部分挖掘結(jié)果示例

表5中的關(guān)聯(lián)規(guī)則表明前導與后續(xù)課程成績之間的關(guān)聯(lián)程度。通過所挖掘的關(guān)聯(lián)規(guī)則，得到各專業(yè)課程之間的內(nèi)在關(guān)聯(lián)，根據(jù)學生現(xiàn)有成績，分析預測后續(xù)課程成績，對學生提出預警，教師可以根據(jù)挖掘結(jié)果因材施教。同時，教務管理人員根據(jù)關(guān)聯(lián)規(guī)則設(shè)置課程開設(shè)學期，合理制定人才培養(yǎng)方案。

圖2 算法執(zhí)行效率比較

通過分別對改進前后的算法進行了實驗，改進前后的算法執(zhí)行效率比較情況如圖2所示。實驗表明當最小支持度越小，在同樣的最小支持度情況下，改進的算法能過濾較多的候選項集，算法所需的時間低于傳統(tǒng)算法，效率較高。

4 結(jié)語

本文基于二維表對傳統(tǒng)的FP-growth算法進行了改進，提出BTFP-growth算法，減少了遍歷數(shù)據(jù)庫的次數(shù)，應用二維表存儲事務，通過二維表計算數(shù)據(jù)項的支持度，并求出頻繁1項集、頻繁2項集和非頻繁2項集，減少遍歷FP-tree的次數(shù)，對FP-tree進行了減枝，減少了內(nèi)存開銷，提高了效率。結(jié)合學生成績數(shù)據(jù)驗證了改進算法的可行性，當需要分析的數(shù)據(jù)規(guī)模較大且最小支持度閾值較小時，改進算法具有較大優(yōu)勢。