關聯規則挖掘算法FP-Growth在高職網絡技術專業學生成績分析中的應用

羅擁軍， 羅云芳

(廣西職業技術學院　計算機與電子信息工程系， 廣西　南寧 　530226)

?

關聯規則挖掘算法FP-Growth在高職網絡技術專業學生成績分析中的應用

羅擁軍， 羅云芳

(廣西職業技術學院計算機與電子信息工程系， 廣西南寧 530226)

從大量的成績數據中進行數據挖掘并從中獲得有價值的信息，是一件非常有意義的研究。以計算機網絡技術專業學生10年的成績作為數據源，運用基于關聯規則的FP-Growth算法，研究5門課程之間的關聯，為制訂該專業人才培養方案提供參考和借鑒。

關聯規則；FP-Growth算法；成績分析

0　引言

在學校，歷年的教學實踐產生了大量的成績數據。如何更好地利用和分析這些數據，從而為教學管理服務，這是非常重要的科學研究。為了讓海量規模的成績數據能夠真正發揮巨大的作用，需要將這些數據轉換為有用的信息和知識，即從傳統的數據統計向數據挖掘和分析進行轉換。

關聯規則挖掘是數據挖掘領域中活躍的一個分支。關聯規則主要是描述數據庫中數據項之間某種潛在關系的規則，目前它在教育方面的研究與應用主要體現在課堂教學評價、試題分析、學生管理等方面[1-3]。

本文基于FP-Growth算法[4]，對廣西職業技術學院2003～2012級計算機網絡技術專業學生的計算機應用基礎等5門課程的成績進行分析，主要研究各課程之間的內在聯系，并給出詳細的分析，為學校以及教師的教學決策提供幫助。

1　關聯規則及其挖掘的過程

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

關聯規則：設X、Y是某些項組成的非空集合，則形如X?Y(其中X?I,X≠φ,Y?I,Y≠φ，并且X∩Y≠φ)的邏輯蘊涵關系稱為關聯規則。X稱為關聯規則的前件或先決條件，Y稱為關聯規則的后件或結果。

關聯規則的支持度：交易集D中包含項集X和Y交易數的與交易總數之比，稱為規則X?Y在交易集D中的支持度，計算公式如下：

關聯規則的置信度：交易集D中包含X和Y的交易數與包X的交易數之比，稱為規則X?Y在交易集D的置信度，記作confidence(X?Y)，計算公式如下：

對關聯規則X?Y，其置信度表示X和Y同時出現的概率有多大。

支持度是對關聯規則重要性的衡量，用以說明該規則在所有事務中的代表性有多大，支持度越大，該關聯規則越重要；置信度則是對關聯規則可靠性的衡量，置信度越大，則說明該關聯規則越可靠。

關聯規則必須滿足的支持度的最小值，稱為最小支持度，用min_sup表示。關聯規則必須滿足的置信度的最小值，稱為最小置信度，用min_conf表示。

對于交易集D和關聯規則X?Y，若同時滿足sup(X?Y)≥min_sup和confidence(X?Y)≥min_conf則關聯規則X?Y稱為強規則，否則關聯規則X?Y稱為弱規則。強關聯規則表示該規則是既重要又可靠的關聯規則。

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

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

關聯規則挖掘問題就是產生支持度和置信度分別大于用戶給定的最小支持度和最小置信度的強關聯規則[4]。

2　FP-Growth算法

2000年，J. Han 等人提出了頻繁模式增長算法——FP-Growth算法。該算法是一種不產生候選項集的挖掘頻繁項集的方法，采用的是分而治之的策略，它通過2次數據庫掃描，把每個事務所包含的頻繁項集壓縮存儲到頻繁模式樹FP-Tree中，然后利用這棵樹生成關聯規則。

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

圖1　生成頻繁模式樹

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

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

圖2　FP-Growth的調用

簡而言之，FP-Growth算法的執行過程如下：

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

(2)對每一個頻繁1-項集，遞歸調用FP-Growth()，從而獲得多元頻繁項集。

3　FP-Growth算法在成績分析中的應用

3.1數據預處理

我們收集了廣西職業技術學院計算機網絡技術專業計算機應用基礎、計算機安裝和維護技術、計算機網絡技術、服務器配置與管理技術、網絡設計與配置技術的2003～2012共10個年級的成績，并對數據進行預處理。數據主要來源于學院教務科研處。

(1)對缺少成績的處理。個別學生因為退學、沒有參加考試等原因造成無成績記錄，為不影響數據挖掘，將此類記錄逐一刪除。

(2)對補考成績的處理。在原始數據中，同時記錄有不及格成績和補考成績的，我們只保留最初考試的成績分數，而將補考成績去掉。

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

表1　2003～2012年級部分學生成績表

注： L1為計算機應用基礎；L2為算機安裝與維護技術；L3為計算機網絡技術；L4為服務器配置與管理技術；L5為網絡設計與配置技術。

(3)數據離散化

在對學生試卷成績進行關聯分析挖掘時，需進行離散化處理，為簡單起見，將成績劃分成≥75分為學習良好，用“1”表示；以下則用“0”表示，如表2所示。

表2　學習成績離散化(部分)

3.2數據挖掘及結果分析

我們設定最小支持度為30%，置信度為20%，挖掘得到項集支持度和置信度見表3～6。

表3　計算機應用基礎與其他課程成績項集的支持度和置信度

從表3可以看出計算機應用基礎學習成績良好者，計算機安裝與維護技術、計算機網絡技術、服務器安裝與管理技術及網絡設計與配置技術都有可能取得良好的成績。

表4　專業基礎課與其他課程成績項集的支持度和置信度

從表4可以看出計算機安裝與維護技術學習成績良好者，網絡設計與配置技術可能取得良好的成績；計算機網絡技術學習成績良好者，服務器安裝與管理技術也成績良好。

表5　專業基礎課與其他課程成績項集的支持度和置信度

從表5可以看出計算機應用基礎與計算機安裝與維護技術學習成績均良好者，網絡設計與配置技術取得良好成績的可能性達68.24%；計算機應用基礎與計算機網絡技術學習成績均良好者，服務器安裝與管理技術成績也相當好，其可能性達87.69%。計算機網絡學習成績好，網絡設計和配置技術也取得良好成績還說得過去，但內容以偏硬件為主的計算機安裝與維護技術成績良好，在內容以理論為主的計算機網絡技術和操作以軟件為主的服務器配置和管理技術也取得好成績，在關聯上似乎顯得牽強。

表6　先導課程與網絡設計與配置技術成績項集的支持度和置信度

表6說明，作為一門綜合性的課程，網絡設計與配置技術其先導課程學習成績良好，那么本門課程也容易獲得較好成績，其可能性達78.57%。

4　結論

數據挖掘結果表明，這5門課程安排的順序是合理的，即第1個學期安排計算機應用基礎，第2學期安排計算機安裝與維護技術，第3學期安排計算機網絡技術，第4學期安排服務器與管理技術，第5學期安排網絡設計與配置技術，這也說明了專業基礎課的重要性。

[1]譚慶. 關聯規則Apriori算法在試卷成績分析中的應用研究[J]. 信陽師范學院學報(自然科學版),2009,22(2):300-303.

[2]崔學文. 關聯規則挖掘算法Apriori在學生成績分析中的應用[J]. 河北北方學院學報(自然科學版),2011,27(1):44-47.

[3]陳偉蓮. 基于數據挖掘技術的某學院成績分析應用[D]. 華南理工大學,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

[責任編輯劉景平]

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-)，男，廣西全州人，廣西職業技術學院計算機與電子信息工程系高級實驗師，主要研究方向：計算機應用與教學。

2015-11-25