羅擁軍， 羅云芳

(廣西職業(yè)技術(shù)學(xué)院　計(jì)算機(jī)與電子信息工程系， 廣西　南寧 　530226)

?

關(guān)聯(lián)規(guī)則挖掘算法FP-Growth在高職網(wǎng)絡(luò)技術(shù)專業(yè)學(xué)生成績(jī)分析中的應(yīng)用

羅擁軍， 羅云芳

(廣西職業(yè)技術(shù)學(xué)院計(jì)算機(jī)與電子信息工程系， 廣西南寧 530226)

從大量的成績(jī)數(shù)據(jù)中進(jìn)行數(shù)據(jù)挖掘并從中獲得有價(jià)值的信息，是一件非常有意義的研究。以計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)專業(yè)學(xué)生10年的成績(jī)作為數(shù)據(jù)源，運(yùn)用基于關(guān)聯(lián)規(guī)則的FP-Growth算法，研究5門課程之間的關(guān)聯(lián)，為制訂該專業(yè)人才培養(yǎng)方案提供參考和借鑒。

關(guān)聯(lián)規(guī)則；FP-Growth算法；成績(jī)分析

0　引言

在學(xué)校，歷年的教學(xué)實(shí)踐產(chǎn)生了大量的成績(jī)數(shù)據(jù)。如何更好地利用和分析這些數(shù)據(jù)，從而為教學(xué)管理服務(wù)，這是非常重要的科學(xué)研究。為了讓海量規(guī)模的成績(jī)數(shù)據(jù)能夠真正發(fā)揮巨大的作用，需要將這些數(shù)據(jù)轉(zhuǎn)換為有用的信息和知識(shí)，即從傳統(tǒng)的數(shù)據(jù)統(tǒng)計(jì)向數(shù)據(jù)挖掘和分析進(jìn)行轉(zhuǎn)換。

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域中活躍的一個(gè)分支。關(guān)聯(lián)規(guī)則主要是描述數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)之間某種潛在關(guān)系的規(guī)則，目前它在教育方面的研究與應(yīng)用主要體現(xiàn)在課堂教學(xué)評(píng)價(jià)、試題分析、學(xué)生管理等方面[1-3]。

本文基于FP-Growth算法[4]，對(duì)廣西職業(yè)技術(shù)學(xué)院2003～2012級(jí)計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)專業(yè)學(xué)生的計(jì)算機(jī)應(yīng)用基礎(chǔ)等5門課程的成績(jī)進(jìn)行分析，主要研究各課程之間的內(nèi)在聯(lián)系，并給出詳細(xì)的分析，為學(xué)校以及教師的教學(xué)決策提供幫助。

1　關(guān)聯(lián)規(guī)則及其挖掘的過程

1993年，R. Agrawal等人在文獻(xiàn)[5]中首先提出關(guān)聯(lián)規(guī)則分析問題。關(guān)聯(lián)規(guī)則的相關(guān)概念如下：設(shè)項(xiàng)集I={i1,i2,…,in}，其中in稱為項(xiàng)；交易集D={T1,T2,…,Tp}，其中Tp稱為交易，它是項(xiàng)的集合，并且T?I。

關(guān)聯(lián)規(guī)則：設(shè)X、Y是某些項(xiàng)組成的非空集合，則形如X?Y(其中X?I,X≠φ,Y?I,Y≠φ，并且X∩Y≠φ)的邏輯蘊(yùn)涵關(guān)系稱為關(guān)聯(lián)規(guī)則。X稱為關(guān)聯(lián)規(guī)則的前件或先決條件，Y稱為關(guān)聯(lián)規(guī)則的后件或結(jié)果。

關(guān)聯(lián)規(guī)則的支持度：交易集D中包含項(xiàng)集X和Y交易數(shù)的與交易總數(shù)之比，稱為規(guī)則X?Y在交易集D中的支持度，計(jì)算公式如下：

關(guān)聯(lián)規(guī)則的置信度：交易集D中包含X和Y的交易數(shù)與包X的交易數(shù)之比，稱為規(guī)則X?Y在交易集D的置信度，記作confidence(X?Y)，計(jì)算公式如下：

對(duì)關(guān)聯(lián)規(guī)則X?Y，其置信度表示X和Y同時(shí)出現(xiàn)的概率有多大。

支持度是對(duì)關(guān)聯(lián)規(guī)則重要性的衡量，用以說明該規(guī)則在所有事務(wù)中的代表性有多大，支持度越大，該關(guān)聯(lián)規(guī)則越重要；置信度則是對(duì)關(guān)聯(lián)規(guī)則可靠性的衡量，置信度越大，則說明該關(guān)聯(lián)規(guī)則越可靠。

關(guān)聯(lián)規(guī)則必須滿足的支持度的最小值，稱為最小支持度，用min_sup表示。關(guān)聯(lián)規(guī)則必須滿足的置信度的最小值，稱為最小置信度，用min_conf表示。

對(duì)于交易集D和關(guān)聯(lián)規(guī)則X?Y，若同時(shí)滿足sup(X?Y)≥min_sup和confidence(X?Y)≥min_conf則關(guān)聯(lián)規(guī)則X?Y稱為強(qiáng)規(guī)則，否則關(guān)聯(lián)規(guī)則X?Y稱為弱規(guī)則。強(qiáng)關(guān)聯(lián)規(guī)則表示該規(guī)則是既重要又可靠的關(guān)聯(lián)規(guī)則。

項(xiàng)集支持度：設(shè)X是由某些項(xiàng)目組成的非空集合，即X?I且X≠φ，則X在交易集D中的支持度是交易集D中包含項(xiàng)集X的交易數(shù)與所有交易數(shù)之比，記為sup(X)，計(jì)算公式如下：

如果項(xiàng)集X的支持度sup(X)≥min_sup，則稱X為頻繁項(xiàng)集。

關(guān)聯(lián)規(guī)則挖掘問題就是產(chǎn)生支持度和置信度分別大于用戶給定的最小支持度和最小置信度的強(qiáng)關(guān)聯(lián)規(guī)則[4]。

2　FP-Growth算法

2000年，J. Han 等人提出了頻繁模式增長(zhǎng)算法——FP-Growth算法。該算法是一種不產(chǎn)生候選項(xiàng)集的挖掘頻繁項(xiàng)集的方法，采用的是分而治之的策略，它通過2次數(shù)據(jù)庫掃描，把每個(gè)事務(wù)所包含的頻繁項(xiàng)集壓縮存儲(chǔ)到頻繁模式樹FP-Tree中，然后利用這棵樹生成關(guān)聯(lián)規(guī)則。

算法的第一步，構(gòu)造頻繁模式樹FP-Tree。參見圖1，首先第一次掃描數(shù)據(jù)庫D，得到頻繁1-項(xiàng)集的集合F和每個(gè)頻繁項(xiàng)的支持?jǐn)?shù)(即項(xiàng)目在D中出現(xiàn)的次數(shù))。按照支持?jǐn)?shù)的大小降序排列，構(gòu)建頻繁項(xiàng)目表L。

圖1　生成頻繁模式樹

之后創(chuàng)建頻繁模式樹FP-Tree的根結(jié)點(diǎn)，用null標(biāo)記。再次掃描數(shù)據(jù)庫D，從每個(gè)事務(wù)T中選取頻繁項(xiàng)，而從事務(wù)T中把非頻繁項(xiàng)刪除，并按照L中的次序排列。并對(duì)每個(gè)事務(wù)T創(chuàng)建一個(gè)分支，構(gòu)建頻繁模式樹時(shí)，每個(gè)節(jié)點(diǎn)用項(xiàng)目名和支持?jǐn)?shù)來標(biāo)識(shí)。事務(wù)T1中的第一個(gè)頻繁項(xiàng)鏈接到根，第二個(gè)鏈接到第一個(gè)，依此類推。如果T2的分支與原來的路徑共享前綴時(shí)，則沿共同前綴的每個(gè)節(jié)點(diǎn)數(shù)加1；并為跟隨共享前綴之后的項(xiàng)創(chuàng)建結(jié)點(diǎn)并鏈接。同樣插入其他分支，直至全部事務(wù)插入完畢，最終生成FP-Tree。

第二步，頻繁模式樹FP-Tree調(diào)用FP-Growth(Tree,null)來完成挖掘。其流程示意如圖2。

圖2　FP-Growth的調(diào)用

簡(jiǎn)而言之，F(xiàn)P-Growth算法的執(zhí)行過程如下：

(1)在FP-Growth遞歸調(diào)用的第一層，模式前后a=null，得到的其實(shí)就是頻繁1-項(xiàng)集。

(2)對(duì)每一個(gè)頻繁1-項(xiàng)集，遞歸調(diào)用FP-Growth()，從而獲得多元頻繁項(xiàng)集。

3　FP-Growth算法在成績(jī)分析中的應(yīng)用

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

我們收集了廣西職業(yè)技術(shù)學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)專業(yè)計(jì)算機(jī)應(yīng)用基礎(chǔ)、計(jì)算機(jī)安裝和維護(hù)技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)、服務(wù)器配置與管理技術(shù)、網(wǎng)絡(luò)設(shè)計(jì)與配置技術(shù)的2003～2012共10個(gè)年級(jí)的成績(jī)，并對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。數(shù)據(jù)主要來源于學(xué)院教務(wù)科研處。

(1)對(duì)缺少成績(jī)的處理。個(gè)別學(xué)生因?yàn)橥藢W(xué)、沒有參加考試等原因造成無成績(jī)記錄，為不影響數(shù)據(jù)挖掘，將此類記錄逐一刪除。

(2)對(duì)補(bǔ)考成績(jī)的處理。在原始數(shù)據(jù)中，同時(shí)記錄有不及格成績(jī)和補(bǔ)考成績(jī)的，我們只保留最初考試的成績(jī)分?jǐn)?shù)，而將補(bǔ)考成績(jī)?nèi)サ簟?/p>

經(jīng)過數(shù)據(jù)清理后，共得到有效記錄1 048條(見表1)。

表1　2003～2012年級(jí)部分學(xué)生成績(jī)表

注： L1為計(jì)算機(jī)應(yīng)用基礎(chǔ)；L2為算機(jī)安裝與維護(hù)技術(shù)；L3為計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)；L4為服務(wù)器配置與管理技術(shù)；L5為網(wǎng)絡(luò)設(shè)計(jì)與配置技術(shù)。

(3)數(shù)據(jù)離散化

在對(duì)學(xué)生試卷成績(jī)進(jìn)行關(guān)聯(lián)分析挖掘時(shí)，需進(jìn)行離散化處理，為簡(jiǎn)單起見，將成績(jī)劃分成≥75分為學(xué)習(xí)良好，用“1”表示；以下則用“0”表示，如表2所示。

表2　學(xué)習(xí)成績(jī)離散化(部分)

3.2數(shù)據(jù)挖掘及結(jié)果分析

我們?cè)O(shè)定最小支持度為30%，置信度為20%，挖掘得到項(xiàng)集支持度和置信度見表3～6。

表3　計(jì)算機(jī)應(yīng)用基礎(chǔ)與其他課程成績(jī)項(xiàng)集的支持度和置信度

從表3可以看出計(jì)算機(jī)應(yīng)用基礎(chǔ)學(xué)習(xí)成績(jī)良好者，計(jì)算機(jī)安裝與維護(hù)技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)、服務(wù)器安裝與管理技術(shù)及網(wǎng)絡(luò)設(shè)計(jì)與配置技術(shù)都有可能取得良好的成績(jī)。

表4　專業(yè)基礎(chǔ)課與其他課程成績(jī)項(xiàng)集的支持度和置信度

從表4可以看出計(jì)算機(jī)安裝與維護(hù)技術(shù)學(xué)習(xí)成績(jī)良好者，網(wǎng)絡(luò)設(shè)計(jì)與配置技術(shù)可能取得良好的成績(jī)；計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)學(xué)習(xí)成績(jī)良好者，服務(wù)器安裝與管理技術(shù)也成績(jī)良好。

表5　專業(yè)基礎(chǔ)課與其他課程成績(jī)項(xiàng)集的支持度和置信度

從表5可以看出計(jì)算機(jī)應(yīng)用基礎(chǔ)與計(jì)算機(jī)安裝與維護(hù)技術(shù)學(xué)習(xí)成績(jī)均良好者，網(wǎng)絡(luò)設(shè)計(jì)與配置技術(shù)取得良好成績(jī)的可能性達(dá)68.24%；計(jì)算機(jī)應(yīng)用基礎(chǔ)與計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)學(xué)習(xí)成績(jī)均良好者，服務(wù)器安裝與管理技術(shù)成績(jī)也相當(dāng)好，其可能性達(dá)87.69%。計(jì)算機(jī)網(wǎng)絡(luò)學(xué)習(xí)成績(jī)好，網(wǎng)絡(luò)設(shè)計(jì)和配置技術(shù)也取得良好成績(jī)還說得過去，但內(nèi)容以偏硬件為主的計(jì)算機(jī)安裝與維護(hù)技術(shù)成績(jī)良好，在內(nèi)容以理論為主的計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)和操作以軟件為主的服務(wù)器配置和管理技術(shù)也取得好成績(jī)，在關(guān)聯(lián)上似乎顯得牽強(qiáng)。

表6　先導(dǎo)課程與網(wǎng)絡(luò)設(shè)計(jì)與配置技術(shù)成績(jī)項(xiàng)集的支持度和置信度

表6說明，作為一門綜合性的課程，網(wǎng)絡(luò)設(shè)計(jì)與配置技術(shù)其先導(dǎo)課程學(xué)習(xí)成績(jī)良好，那么本門課程也容易獲得較好成績(jī)，其可能性達(dá)78.57%。

4　結(jié)論

數(shù)據(jù)挖掘結(jié)果表明，這5門課程安排的順序是合理的，即第1個(gè)學(xué)期安排計(jì)算機(jī)應(yīng)用基礎(chǔ)，第2學(xué)期安排計(jì)算機(jī)安裝與維護(hù)技術(shù)，第3學(xué)期安排計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)，第4學(xué)期安排服務(wù)器與管理技術(shù)，第5學(xué)期安排網(wǎng)絡(luò)設(shè)計(jì)與配置技術(shù)，這也說明了專業(yè)基礎(chǔ)課的重要性。

[1]譚慶. 關(guān)聯(lián)規(guī)則Apriori算法在試卷成績(jī)分析中的應(yīng)用研究[J]. 信陽師范學(xué)院學(xué)報(bào)(自然科學(xué)版),2009,22(2):300-303.

[2]崔學(xué)文. 關(guān)聯(lián)規(guī)則挖掘算法Apriori在學(xué)生成績(jī)分析中的應(yīng)用[J]. 河北北方學(xué)院學(xué)報(bào)(自然科學(xué)版),2011,27(1):44-47.

[3]陳偉蓮. 基于數(shù)據(jù)挖掘技術(shù)的某學(xué)院成績(jī)分析應(yīng)用[D]. 華南理工大學(xué),2012.

[4] R Agrawal, R Srikant. Fast Algorithms for Mining Association Rules in Large Database[C]∥Proceedings of the 20th International Conference on Very Large Data bases.San Francisco, CA, USA：Santiago，1994:487-499.

[5] R Agrawal, T Imielinski, A Swami. Mining Association Rules Between Sets of Items in Large Databases[J].Acm Sigmod Record,1993,22(2):207-216.

[6]J Han , J Pei, Y Yin. Mining frequent patterns without candidate generation[J].Acm Sigmod Record, 2000, 29(2):1-12.

[Abstract]Data mining from a large number of performance data and getting valuable information is a very meaningful research.Taking the 10-year scores of students majoring in computer network technology as a source of data, using the FP-Growth algorithm based on association rules, the association between five courses was studied. It can provide reference for formulating the professional talent training scheme.

[Key words]association rules; FP-Growth algorithm; score analysis

[責(zé)任編輯劉景平]

Application of Association Rule Mining Algorithm FP-Growth in the Score Analysis of Students from Network Technology Specialty in Polytechnics

LUO Yong-jun, LUO Yun-fang

(Department of Computer and Electronic Information Engineering,Guangxi Polytechnic, Nanning, Guangxi 530226, China)

TP311；TP391

A

1672-9021(2016)02-0067-06

羅擁軍(1964-)，男，廣西全州人，廣西職業(yè)技術(shù)學(xué)院計(jì)算機(jī)與電子信息工程系高級(jí)實(shí)驗(yàn)師，主要研究方向：計(jì)算機(jī)應(yīng)用與教學(xué)。

2015-11-25