基于FP—Growth的高校學業預警系統設計與實現

陳玲萍

摘 要：文章提出了一種基于FP-Growth算法的高校學生學業預警系統，能夠根據以往的學生成績信息挖掘出不及格課程間的關聯規則，以提前給學生發出課程預警。首先從現有的學生成績系統中篩選并構造出學生不及格課程事務數據庫；然后運用FP-Growth算法進行課程關聯規則挖掘；最后利用關聯規則，自動發現學生將來可能存在危險的課程，并結合現在的學習成績發出學業預警。經驗證，本方法對學生成績的預警有較高的準確率，并可推廣應用到學生工作的其他方面。

關鍵詞：關聯規則；學業預警；FP-Growth

高等教育進入大眾化階段，學生的學業狀況關系到個人發展、家庭和諧及社會安全。通過學業預警系統對學生課程成績進行分析，能及時發現學生課程上存在的問題和困難，有效地預防學生留級、退學事件的發生，是加強學生學業管理，提高人才培養質量的重要手段，是構建和諧校園、和諧社會的重要途徑。

普通的學業預警系統通常只統計學生的學分，當所欠學分達到一定程度就發出預警。這種方法及設計存在預見性不足問題。當系統發出預警時，學生已經失去了采取措施的先機。本文提出采用數據挖掘的方法來設計學業預警系統，通過以往學生的課程成績發現課程間隱藏的關系，預測未來可能發生的不及格課程，并對學生及時發出預警，以提示學生對預警課程的學習更加重視、更加努力，達到學業預警的目的。

1 關聯規則挖掘的應用

關聯規則挖掘是數據挖掘領域中的一個重要分支，其應用已經滲透到社會生活的各個領域。關聯規則挖掘起源于對購物籃問題的分析，該問題是在現有的商品貨物交易記錄基礎上，對消費者購買習慣進行分析，從而挖掘出消費者的消費模式。在這些一般性消費模式指導下能夠更加合理地擺放貨物，制定符合消費者消費行為的促銷活動，以達到提高銷量的目的。Agrawal等[1]提出的基于頻繁項集的Apriori算法是經典關聯規則算法，在此之后涌現了大量的關聯規則挖掘方面的研究，其中包括關聯規則問題衍生出了對Apriori算法的優化問題、關聯規則的并行化問題以及關聯規則在實際工程中應用問題等。Han等[2]提出的FP-Growth算法是比Apriori效率更高的頻繁項集挖掘算法。該算法將事務集壓縮到FP-Tree上，將壓縮后的事務數據庫采用分治的策略劃分到條件數據集中，再從各個條件數據集中挖掘出關聯規則。由于FP-Growth算法只需遍歷數據集兩次就能夠完成頻繁模式發現。因此，本文在學業預警系統中采用FP-Growth算法進行課程關系的挖掘。

2 基于FP-Growth關聯規則挖掘的學業預警系統

2.1 關聯規則相關定義

2.1.3 頻繁項的定義

設X是由某些項目組成的非空集合，即XI且X≠Φ，Minsup為給定的最小支持度，也稱為支持度最小門限[3]。如果S（X）≥Minsup，X屬于頻繁項。由頻繁項組成的集合稱為頻繁項集。此外，若X是由K個項目構成的，則X又稱為K-維頻繁項；所有K-頻繁項構成的集合稱為K-維頻繁項集。

2.2 FP-Growth算法基本思想

FP-Growth算法是利用樹結構來描述項之間的關系，該算法最大的優勢在于將事務之間相同的項進行壓縮，從而降低了算法的空間復雜度。它和經典的Apriori算法的不同點在于它不是先產生后驗證的思想，而是通過構建一種頻繁模式樹的緊湊型數據結構，并且不需要產生候選頻繁項集直接從樹結構中提取頻繁項集。算法的主要思想是將事務型數據庫中的每條事務映射到FP-Tree中，但是不改變項集之間的關聯關系。FP-Growth算法的重點在于對FP-Tree的構建，構建FP-Tree需要對數據庫進行兩次遍歷，第一次遍歷事務集得到頻繁1-項集及其支持度，根據其對應的支持度的大小對其進行排序；第二次遍歷事務集，通常以“NULL”為根節點，在第一次遍歷得到的頻繁1-項集合的基礎上構建FP-Tree。為了更快地在提取頻繁項集時能夠對FP-Tree進行遍歷，需要構建一個包含所有頻繁項元素的項表頭，表中的每個項元素都有一個指針指向該元素項在FP-Tree對應的節點位置，具體算法如下。

2.2.1 構建FP-Tree

遍歷事務數據庫T，找出所有滿足大于最小支持度的所有項并統計這些項的頻度，這些項就被稱為頻繁1-項集合L[4]，根據其對應的支持度的大小對其進行排序L_First。

創建原始FP-Tree，以“NULL”為根節點。

2.2.2 創建表頭

為了方便提取FP-子樹需構建一個包含所有頻繁項元素的項表頭，表中的每個項元素都有一個指針指向該元素項在FP-Tree對應的節點位置。

遍歷一次事物數據庫T，將T中每個事務的項次序根據L_First進行調整，其中頻度越高的項越靠近樹的根部，將每個事務看作為樹的分支，依次將每個事務添加到樹中。如果分支中有前n項事務與樹中其他事務相同，則認為該事務能夠與其他事務進行路徑合并，但要在這些相同各個節點上計數加一，剩余沒有的項則在該枝干上分出一條包含剩余其他項的枝干。路徑合并需要將新事務合并在樹中重復度最大的事務上，依次將所有事務壓縮到樹中。

2.2.3 提取頻繁項集

查找出單個項的條件模式基，條件模式基是以所查找元素項為結尾的路徑的集合。統計條件模式基中各個元素的頻度，將其中頻度小于最小支持度的元素刪除。將剩余元素進行全排即頻繁項集。

3 學業預警系統構建

本學業預警系統是根據FP-Growth算法找出課程之間存在的隱形規則，找出學生在有課程不及格的時候其他課程中比較危險的課程[5]。由于FP-Growth算法是無監督的機器學習算法，因此，需要提供訓練樣本以提取出普適的規則。可以選擇已畢業大學生在其大學期間的學習情況作為訓練樣本。

3.1 樣本抽取

從已經畢業的大學生本科階段成績單中篩選出學生曾經不及格的課程，作為訓練樣本集，同時需要統計對應課程的學分。每個學生的不及格課程看作一個事務，其中的課程作為項。為了在接下來設置支持度時更符合實際情況，需要刪除一部分課程，例如大學校級公選課。由于這些課程每個學生選修的都不相同，同時可選課程數量范圍較大，因此，這些課程中的每個課程的頻度之和都不會太大，為了提高算法的運算量可以將這些課程刪除。

3.2 關聯規則挖掘

將提取后的訓練數據集輸入設置好支持度的算法中。最小支持度一般設置為數據集的5%[6]。對數據集需要劃分為3個部分進行訓練。首先需要對大學期間掛科學分低于20學分的數據集進行關聯規則挖掘，得出這個分段容易不及格課程之間的關聯規則。同樣找出掛科在20～30學分和30學分以上同學容易出現不及格課程之間的關聯規則。

3.3 將測試數據集輸入進行驗證

將第二步得到的關聯規則作為判決條件，根據樣本中項與規則中的項進行匹配，找出與樣本匹配度最高的規則作為輸出結果，規則里樣本沒有的項即為在以后需要多加關注的課程。匹配度最高的規則中未出現的課程為更容易不及格的課程，將這些課程作為預警結果之一輸出。

3.4 統計當前不及格課程的學分之和

作為本學業預警系統輸出結果之一，學生當前不及格課程的學分更能準確反映該同學的學業狀態，并通過訓練大量樣本得到學生在后續學習中容易不及格課程的列表清單。

4 實驗及分析

4.1 實驗方法及結果

實驗環境基于Win10+i5-6300HQ 2.30GHz四核環境，利用Python3.6軟件仿真。首先將原始數據集進行清洗，篩選出500個樣本，其中400是訓練樣本集，100是驗證樣本集，構建成事務型數據庫。其次對FP-Growth算法進行編程。將訓練樣本數據集導入算法得出課程間的關聯規則。然后輸入測試樣本集驗證預警課程得正確度。最后根據學生當前不及格課程得學分之和以及預測課程給出預警結果。

根據測試集的驗證課程的預測準確率很高。例如：學號為“1252100121”電子信息工程專業的學生，他在學生成績系統中顯示有一門“大學英語I”不及格，根據關聯規則得出他需要注意的課程有“專業英語（電子信息類）”“EDA技術及應用”“電子線路CAD及仿真”“數據結構”“VC程序設計”等。預測的課程中基本包含了該同學在大學期間所有不及格課程，由于現階段只有一門不及格的課程，因此得到的成績狀態是“黃”。

4.2 實驗結果分析

實驗結果驗證該預測系統能夠準確反映學生當前的成績狀態并且對以后的特定的課程的學習有明確的指導效果。本系統的預警信息主要受訓練數據集的影響，不同的訓練數據集得到的結果會不相同，不同學校的老師評分標準不同也可能會導致不同的訓練數據集，因此，本系統在實際應用中應輸入符合自己需求的訓練數據集，這樣得到的結果才能更符合預期結果。

5 結語

本學業系統能夠準確地反映出學生現階段的學習狀態，同時也能對其將來的學習給予一定的提醒，學生能通過本系統制定更加符合自己特點的學習計劃。同時本系統也能夠幫助老師及時了解學生的學習狀態，并在必要的時候給同學合理的指導和幫助，對提高本校的教學質量和提高大學生的綜合素質都有很大的作用。

[參考文獻]

[1]AGRAWAL R，TOMASZ I，ARUN S.Mining association rule between sets of items in large databases[J].ACM Sigmod Record，1993（5）：302-313.

[2]HAN J，PEI J，YIN Y.Mining frequent patterns without candidate generation[C].Dallas：2000 ACM Sigmod International Conference on Management，2000：1-12.

[3]吳暾華，王萍，劉婷.基于支持向量機的大學生學業動態預警研究[J].中國教育信息化，2017（17）：65-67.

[4]陳建成，屠昂燕，許雪貴.基于遺傳算法的學生信息關聯規則挖掘研究[J].電腦知識與技術，2008（34）：1747-1748，1754.

[5]張體芳.克隆遺傳算法在學生成績分析中的應用[J].計算機時代，2012（8）：18-19，23.

[6]王華，劉萍.改進的關聯規則算法在學生成績預警中的應用[J].計算機工程與設計，2015（3）：679-682，752.