葉福蘭

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

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

1 Fp-growth算法概述

關(guān)聯(lián)規(guī)則是指對(duì)給定的數(shù)據(jù)庫(kù)集中的事務(wù)進(jìn)行挖掘，尋找內(nèi)在數(shù)據(jù)項(xiàng)之間的內(nèi)在關(guān)系，支持度與置信度是關(guān)聯(lián)規(guī)則挖掘的兩個(gè)重要指標(biāo)。對(duì)于形如“A=>B”的關(guān)聯(lián)規(guī)則，支持度是指事務(wù)數(shù)據(jù)集中同時(shí)包含A和B的概率，如公式(1)所示；置信度是指包含A和B的事務(wù)數(shù)占包含A的事務(wù)數(shù)的百分比，如公式(2)所示。關(guān)聯(lián)規(guī)則挖掘中最具代表性的算法是Apriori算法，Apriori算法是一種“產(chǎn)生-測(cè)試”型的關(guān)聯(lián)規(guī)則挖掘算法，通過不斷逐次迭代生成候選項(xiàng)集，結(jié)合最小支持度計(jì)數(shù)及先驗(yàn)原理，求出候選項(xiàng)集。先驗(yàn)原理：如果一個(gè)項(xiàng)集是頻繁，那么它的所有非空子集也是頻繁。[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算法中存在的缺陷而提出的一種改進(jìn)算法。FP-growth算法挖掘過程主要包括FP-tree構(gòu)建過程以及根據(jù)FP-tree挖掘頻繁模式兩大步驟。FP-growth算法與Apriori算法的主要區(qū)別如下：

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

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

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

2 FP-growth算法的改進(jìn)

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

2.1 算法改進(jìn)思路

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

1)掃描事務(wù)數(shù)據(jù)庫(kù)，用二維表存儲(chǔ)對(duì)應(yīng)的所有數(shù)據(jù)項(xiàng)及每個(gè)事務(wù)數(shù)據(jù)，行表示數(shù)據(jù)項(xiàng)，列表示對(duì)應(yīng)的事務(wù)，若數(shù)據(jù)項(xiàng)在某事務(wù)中存在，該數(shù)據(jù)項(xiàng)對(duì)應(yīng)行所在的事務(wù)列中對(duì)應(yīng)的值用1表示，否則用0表示；

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

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

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

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

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

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

Output：所有的頻繁項(xiàng)集。

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

Build_FP_tree(D,Minsup,T)

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

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

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

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

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

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

FOR P中每個(gè)三項(xiàng)以上的結(jié)點(diǎn)組合β DO

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

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

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

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

IF (Tβ≠Φ) THEN

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

2.2 改進(jìn)算法案例分析

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

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

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

表2 事務(wù)二維表

2)根據(jù)生成的事務(wù)二維表，對(duì)任意兩個(gè)數(shù)據(jù)項(xiàng)在同一事務(wù)中的值進(jìn)行邏輯“與”運(yùn)算，并將求得的邏輯“與”值進(jìn)行累加，求得兩個(gè)數(shù)據(jù)項(xiàng)的支持度計(jì)數(shù)，如數(shù)據(jù)項(xiàng)a與b同時(shí)出現(xiàn)的支持度計(jì)數(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的支持度計(jì)數(shù)分別為4,5,4,3,2，刪除支持度小于3的cd項(xiàng)，求得頻繁2項(xiàng)集為{ab,ac,ad,bc,bd}，非頻繁項(xiàng)集為{cd}。

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

圖1 FP-tree

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

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

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

3.1 實(shí)驗(yàn)環(huán)境介紹

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

3.2 數(shù)據(jù)準(zhǔn)備

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

表3 學(xué)生成績(jī)?cè)紨?shù)據(jù)

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

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

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

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

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

3.4 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

4 結(jié)語(yǔ)

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