基于FP-growth算法的學生成績分析系統(tǒng)的研究

韓睿鵬，雷立宏，丁巖

（長春理工大學 計算機科學與技術學院，長春 130022）

隨著高等教育的迅速發(fā)展，大多數(shù)高校教育信息化的應用，教務數(shù)字化信息數(shù)量飛速增長，給高校管理機構和教師的教學方法的改進帶了不少新課題[1]。教育行業(yè)的大數(shù)據(jù)處理已經(jīng)成為我們國家高?；A性和前沿性的技術需求，對學生的成績數(shù)據(jù)進行深度的處理和分析就是一個亟待解決的課題，大數(shù)據(jù)基礎上的數(shù)據(jù)分析可以有效處理這一課題[2]。當前，大部分高校都具有學生成績數(shù)據(jù)的海量存儲，隱含在這些海量成績數(shù)據(jù)后面是很重要的知識信息，學生成績的大數(shù)據(jù)分析能夠挖掘并利用隱藏的價值。

1 數(shù)據(jù)挖掘技術及關聯(lián)規(guī)則概述

1.1 數(shù)據(jù)挖掘技術概述

在互聯(lián)網(wǎng)+時代，大數(shù)據(jù)的開放、挖掘和應用已經(jīng)成為信息領域的發(fā)展趨勢。數(shù)據(jù)挖掘是在沒有確定目標下去發(fā)現(xiàn)潛在應用價值，數(shù)據(jù)挖掘與普通的數(shù)據(jù)處理不一樣，它把數(shù)據(jù)處理從簡單增添、刪除、查詢，提高到一個更高級的挖掘知識，智能決策階段[3，4]。數(shù)據(jù)挖掘的步驟如下圖1所示。數(shù)據(jù)挖掘任務實現(xiàn)的技術較多，從應用領域和科學研究方面考慮，數(shù)據(jù)挖掘的技術分為以下6種：關聯(lián)、預測、聚類、分類、回歸、診斷。

圖1 數(shù)據(jù)挖掘步驟

1.2 關聯(lián)規(guī)則概述

關聯(lián)規(guī)則分析方法是挖掘數(shù)據(jù)特征之間的彼此聯(lián)系，挖掘的目標是分析出數(shù)據(jù)之間隱藏的關系網(wǎng)[5]。關聯(lián)規(guī)則分析在許多領域獲得了良好的效果，例如商業(yè)、醫(yī)療保健、郵遞、金融證券等。關聯(lián)規(guī)則的基本概念如下：

定義1：關聯(lián)規(guī)則

關聯(lián)規(guī)則可表示為X?Y的公式，X，Y分別是項目集的真子集，X∩Y=?。X叫做X?Y的前提，Y叫做X?Y的結果。

定義2：關聯(lián)規(guī)則的支持度（Support）

關聯(lián)規(guī)則的支持度是交易集中同時包括X和Y的交易數(shù)與所有交易數(shù)之比，記為support（X?Y），即support（X?Y）=support（X∪Y）=P（XY）

支持度表明了同時包含X和Y的項集在事物數(shù)據(jù)庫中同時出現(xiàn)的概率。

定義3：關聯(lián)規(guī)則的置信度（Confidence）

關聯(lián)規(guī)則的置信度是事物數(shù)據(jù)庫中同時包含X和Y的事物數(shù)與所有包含X的事物數(shù)之比，記為confidence（X?Y），即：

定義4：最小支持度與最小置信度

最小支持度（min_sup）和最小可信度（min_conf）都是用戶自己定義的一個界限值。X?Y的支持度≥min_sup并且X?Y的可信度≥min_conf，此時認為X?Y是有趣的。最小支持度描述項目集統(tǒng)計上最低重要水平，最小置信度描述了項目集統(tǒng)計上必需的最低可信性。

2 頻繁增長模式FP-Growth算法

2.1 FP-Growth算法定義

FP-Growth算法是一種關聯(lián)規(guī)則分析方法，創(chuàng)造性地提出使用更適宜的數(shù)型結構，沒有候選項目集，提高了算法的速度。FP-Growth算法主要分兩步：一、建立FP樹；二、從FP樹中挖掘頻繁模式[6]。該算法主要有以下兩大優(yōu)點：一、不產生候選集；二、只需要2次搜索數(shù)據(jù)庫，效率很高。

該算法的具體描述如下：

第一步：FP-樹構造算法流程圖2所示。

圖2 FP-樹構造算法流程圖

第二步：挖掘FP-tree的頻繁模式，算法流程圖如下圖3所示。

圖3 挖掘FP-tree的頻繁項集算法流程圖

2.2 FP-growth算法實例演示

為了說明算法的實現(xiàn)過程，假設原始項目集如圖4所示。

步驟1：構建FP-樹：

搜索事物數(shù)據(jù)庫，結果為頻繁集1-項目集F，如圖5所示。

圖5 頻繁集1-項目集F

設定min_sup=2，對F重新排列，如圖6所示。

創(chuàng)建根節(jié)點和頻繁項目表如圖7所示。

圖7 根節(jié)點和頻繁項目表

加入第一個事物（I2，I1，I5）如圖8所示。

圖8 加入第一個事物的FP-樹

依次加入其它事物，一棵完整的FP-樹構建，如圖9所示。

圖9 完整的FP-樹

步驟2：根據(jù)FP-樹挖掘頻繁項集：

1）首先從I5開始，導出條件模式基：＜（I2，I1，I3：1）、（I2，I1：1）＞，并構造條件FP-樹如圖10所示。

圖10 I5條件FP-樹

得到 I5的頻繁項集：{I1，I5：3}、{I2，I5：2}、{I1，I3，I5：2}、{I2，I1，I5：2}。

同理，依次考慮，I1，I3，I4，得到的頻繁項集如下。

I1的頻繁項集：{I2，I1：4}。

I3的頻繁項集：{I1，I3：4}、{I2，I3：4}、{I2，I1，I3：2}。

i4的頻繁項集：{I2，I4：3}、{I1，I4：2}。

上面實例演示了FP-Growth算法的詳細實現(xiàn)過程，可以看出，按照FP-Growth算法查找頻項集，更直觀，更高速。

3 基于FP-Growth算法的課程成績分析

3.1 數(shù)據(jù)準備及預處理

數(shù)據(jù)幾乎都是不完善的，大部分原始業(yè)務數(shù)據(jù)具有不完全，自相矛盾或數(shù)據(jù)噪聲等的一系列問題。數(shù)據(jù)預處理可以對原始數(shù)據(jù)進行糾正、篩選、合并、去除不合理的數(shù)據(jù)，從而提高數(shù)據(jù)質量，為下一步的數(shù)據(jù)分析做好準備。因為數(shù)據(jù)質量的差異，挖掘類型的不同，原始數(shù)據(jù)預處理運用的技術也會相應變化。一般情況下，數(shù)據(jù)預處理包括數(shù)據(jù)清洗、數(shù)據(jù)集成、數(shù)據(jù)規(guī)約和數(shù)據(jù)變換等步驟，如圖11所示。

用于成績分析的樣本數(shù)據(jù)來源于長春理工大學教務管理系統(tǒng)中2012-2016級計算機科學技術專業(yè)7個班4個年級必修課成績數(shù)據(jù)。教師輸入數(shù)字化成績時，偶爾也會出現(xiàn)失誤，學生也會由于某種原因缺考或中途退學，去掉成績缺失和數(shù)據(jù)錯誤的記錄后，共有1200條成績記錄。成績單包括學號、姓名、學院、系、計算機導論、面向對象程序設計、數(shù)據(jù)結構與算法、數(shù)字邏輯、計算機網(wǎng)絡、計算科學與數(shù)值方法等多個屬性。首先將姓名、學院、系這幾個屬性刪掉，其余的全部用于挖掘分析成績的屬性。

在數(shù)據(jù)分析前經(jīng)常需要對連續(xù)型的數(shù)據(jù)進行轉換，數(shù)據(jù)離散化是創(chuàng)建數(shù)據(jù)挖掘算法最常使用的方法，而數(shù)據(jù)挖掘結果的可靠性是與數(shù)據(jù)離散化方法的選取息息相關的。數(shù)據(jù)離散化是把連續(xù)型數(shù)據(jù)劃分成若干區(qū)間，然后分別用不同符號來代替不同個區(qū)間。使用的是“自動調整寬度”的離散化方法。此方法的特點是充分照顧到不同數(shù)據(jù)特性，數(shù)值區(qū)間劃分的比例能夠調控，具有較強的靈活性[7]。

在針對學習成績的分析中，將分數(shù)制的成績數(shù)據(jù)離散化為等級制。由此把百分的成績分為優(yōu)秀、良好、中等、及格、不及格5個等級，下表1表示各等級在各門課程中所占百分比[8]。

表1 課程成績離散化數(shù)據(jù)比例

依照表1中對各門課程成績的百分率分段，將每個學生的成績轉換成A，B，C，D，E五個等級。

3.2 代碼轉換表制定

把參加挖掘的每門課程名稱轉換為編碼，計算機導論的編碼為1，面向對象程序設計的編碼為2，數(shù)據(jù)結構與算法的編碼為3，以此類推[9，10]。

同樣把成績等級轉換為編碼，優(yōu)秀為A，良好為B，中等為C，合格為D，不合格為E，則成績數(shù)據(jù)轉換后的代碼表如表2所示。

表2 代碼轉換表

3.3 學生成績表的轉換

學生成績數(shù)據(jù)庫如下表3，表中每一行是一個學生的成績信息，例如：第一行是學號S1的各門課成績，計算機導論、面向對象的程序設計、數(shù)據(jù)結構與算法、高等數(shù)學等分別是91、86、83、92、…。

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

依據(jù)FP-growth算法的要求，下面將學生成績數(shù)據(jù)庫（表3）轉換為對應的事務數(shù)據(jù)庫，使用區(qū)間映射方法，將學生表中對應的每一個的成績值由數(shù)值型映射成某個枚舉值，轉換結果如表4所示。

表4 事物數(shù)據(jù)庫

3.4 挖掘結果

為了數(shù)據(jù)挖掘的信息可信程度較高，設置min_sup=0.3，min_conf=0.6，執(zhí)行 FP-growth關聯(lián)分析算法，分析哪些課程之間具有較強的關聯(lián)性，挖掘出前期課程對后期課程成績的影響。挖掘出來的部分結果如表5所示，可以看出，滿足最小支持度0.3的包含3門課的項集如下：

{數(shù)字邏輯（良好），面向對象程序設計（優(yōu)秀），計算機網(wǎng)絡（優(yōu)秀）}

{電工電子技術（優(yōu)秀），數(shù)據(jù)結構（中等），計算機網(wǎng)絡（良好）}

{數(shù)據(jù)結構（良好），數(shù)字邏輯（良好），計算機網(wǎng)絡（良好）}

說明計算機網(wǎng)絡取得優(yōu)秀成績和數(shù)字邏輯的優(yōu)良程度且面向對象程序設計優(yōu)秀具有很大的關系。

設置目標課程T為“計算機網(wǎng)絡”，目標規(guī)則為關聯(lián)后件包含“計算機網(wǎng)絡”的關聯(lián)規(guī)則。得到的關聯(lián)規(guī)則如表5所示。

表5 部分挖掘結果示例

表5的規(guī)則表明如果數(shù)字邏輯成績優(yōu)秀，則計算機網(wǎng)絡成績也為優(yōu)秀的概率為90.1%，說明數(shù)字邏輯成績好的學生在學習計算機網(wǎng)絡課程時會有一定優(yōu)勢，原因在于數(shù)字邏輯作為計算機專業(yè)的基礎學科，為學生奠定了邏輯運算及硬件基礎，可為學習計算機網(wǎng)絡打好基礎。計算機導論成績優(yōu)秀，則計算機網(wǎng)絡成績也為優(yōu)秀的概率為85.9%，說明計算機導論成績突出對學習計算機網(wǎng)絡也有很大優(yōu)勢，計算機導論講述了有關計算機的基礎知識，基本理念，給予計算機網(wǎng)絡的學習很深厚的專業(yè)理論功底。同理，挖掘出的其他規(guī)則可以得到其他前期課程對計算機網(wǎng)絡成績的影響。

根據(jù)以上列出的具有較強關聯(lián)性的課程和推導出的關聯(lián)規(guī)則，教務管理人員可以預先了解學生學習有關課程的情況，有選擇性地制定教學計劃。例如，若計劃開設《計算機網(wǎng)絡》這門課程，則可使用《數(shù)字邏輯》這門課程學習成績對《計算機網(wǎng)絡》課程預先測評，對班級每個學生的學習狀況進行評估，根據(jù)不同的評估結果，分別對待，個別指導，繼而激發(fā)全班學生的學習潛力。學生們亦可根據(jù)挖掘出來規(guī)則，提高對某些課程的關注和努力。比如想要《計算機網(wǎng)絡》課程取得好的成績，從表5規(guī)則可看到，如果其先期課程《數(shù)字邏輯》成績良好及《面向對象程序設計》成績優(yōu)秀，學好《計算機網(wǎng)絡》課程的可能性就很高，從為學習做好先期準備，提升學習效果。

4 結束語

關聯(lián)規(guī)則分析是數(shù)據(jù)挖掘中最簡單、最實用、最重要一種知識模式，實驗證明，通過FP-growth頻繁增長模式算法能夠有效地對課程成績數(shù)據(jù)進行挖掘分析，得到理想的挖掘結果。挖掘出來的關聯(lián)規(guī)則在某種程度上顯示了課程之間時間安排順序的重要性，前期課程對后續(xù)課程教學效果的影響力。此外，教師可以根據(jù)前期課程的學習情況，有目標、有針對性地對不同學生關注和輔導。學生也可參照規(guī)則，對學習的科目進行評估和預測，以便在今后的學習中采取有效的措施，最終達到較好的教學效果。課程成績數(shù)據(jù)分析的有效成果為將數(shù)據(jù)挖掘技術逐步推廣開來，應用在教育領域的各個方面，具有重要的現(xiàn)實意義。