基于FP—Growth的高校學(xué)業(yè)預(yù)警系統(tǒng)設(shè)計與實現(xiàn)

陳玲萍

摘 要：文章提出了一種基于FP-Growth算法的高校學(xué)生學(xué)業(yè)預(yù)警系統(tǒng)，能夠根據(jù)以往的學(xué)生成績信息挖掘出不及格課程間的關(guān)聯(lián)規(guī)則，以提前給學(xué)生發(fā)出課程預(yù)警。首先從現(xiàn)有的學(xué)生成績系統(tǒng)中篩選并構(gòu)造出學(xué)生不及格課程事務(wù)數(shù)據(jù)庫；然后運用FP-Growth算法進(jìn)行課程關(guān)聯(lián)規(guī)則挖掘；最后利用關(guān)聯(lián)規(guī)則，自動發(fā)現(xiàn)學(xué)生將來可能存在危險的課程，并結(jié)合現(xiàn)在的學(xué)習(xí)成績發(fā)出學(xué)業(yè)預(yù)警。經(jīng)驗證，本方法對學(xué)生成績的預(yù)警有較高的準(zhǔn)確率，并可推廣應(yīng)用到學(xué)生工作的其他方面。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；學(xué)業(yè)預(yù)警；FP-Growth

高等教育進(jìn)入大眾化階段，學(xué)生的學(xué)業(yè)狀況關(guān)系到個人發(fā)展、家庭和諧及社會安全。通過學(xué)業(yè)預(yù)警系統(tǒng)對學(xué)生課程成績進(jìn)行分析，能及時發(fā)現(xiàn)學(xué)生課程上存在的問題和困難，有效地預(yù)防學(xué)生留級、退學(xué)事件的發(fā)生，是加強學(xué)生學(xué)業(yè)管理，提高人才培養(yǎng)質(zhì)量的重要手段，是構(gòu)建和諧校園、和諧社會的重要途徑。

普通的學(xué)業(yè)預(yù)警系統(tǒng)通常只統(tǒng)計學(xué)生的學(xué)分，當(dāng)所欠學(xué)分達(dá)到一定程度就發(fā)出預(yù)警。這種方法及設(shè)計存在預(yù)見性不足問題。當(dāng)系統(tǒng)發(fā)出預(yù)警時，學(xué)生已經(jīng)失去了采取措施的先機。本文提出采用數(shù)據(jù)挖掘的方法來設(shè)計學(xué)業(yè)預(yù)警系統(tǒng)，通過以往學(xué)生的課程成績發(fā)現(xiàn)課程間隱藏的關(guān)系，預(yù)測未來可能發(fā)生的不及格課程，并對學(xué)生及時發(fā)出預(yù)警，以提示學(xué)生對預(yù)警課程的學(xué)習(xí)更加重視、更加努力，達(dá)到學(xué)業(yè)預(yù)警的目的。

1 關(guān)聯(lián)規(guī)則挖掘的應(yīng)用

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

2 基于FP-Growth關(guān)聯(lián)規(guī)則挖掘的學(xué)業(yè)預(yù)警系統(tǒng)

2.1 關(guān)聯(lián)規(guī)則相關(guān)定義

2.1.3 頻繁項的定義

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

2.2 FP-Growth算法基本思想

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

2.2.1 構(gòu)建FP-Tree

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

創(chuàng)建原始FP-Tree，以“NULL”為根節(jié)點。

2.2.2 創(chuàng)建表頭

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

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

2.2.3 提取頻繁項集

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

3 學(xué)業(yè)預(yù)警系統(tǒng)構(gòu)建

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

3.1 樣本抽取

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

3.2 關(guān)聯(lián)規(guī)則挖掘

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

3.3 將測試數(shù)據(jù)集輸入進(jìn)行驗證

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

3.4 統(tǒng)計當(dāng)前不及格課程的學(xué)分之和

作為本學(xué)業(yè)預(yù)警系統(tǒng)輸出結(jié)果之一，學(xué)生當(dāng)前不及格課程的學(xué)分更能準(zhǔn)確反映該同學(xué)的學(xué)業(yè)狀態(tài)，并通過訓(xùn)練大量樣本得到學(xué)生在后續(xù)學(xué)習(xí)中容易不及格課程的列表清單。

4 實驗及分析

4.1 實驗方法及結(jié)果

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

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

4.2 實驗結(jié)果分析

實驗結(jié)果驗證該預(yù)測系統(tǒng)能夠準(zhǔn)確反映學(xué)生當(dāng)前的成績狀態(tài)并且對以后的特定的課程的學(xué)習(xí)有明確的指導(dǎo)效果。本系統(tǒng)的預(yù)警信息主要受訓(xùn)練數(shù)據(jù)集的影響，不同的訓(xùn)練數(shù)據(jù)集得到的結(jié)果會不相同，不同學(xué)校的老師評分標(biāo)準(zhǔn)不同也可能會導(dǎo)致不同的訓(xùn)練數(shù)據(jù)集，因此，本系統(tǒng)在實際應(yīng)用中應(yīng)輸入符合自己需求的訓(xùn)練數(shù)據(jù)集，這樣得到的結(jié)果才能更符合預(yù)期結(jié)果。

5 結(jié)語

本學(xué)業(yè)系統(tǒng)能夠準(zhǔn)確地反映出學(xué)生現(xiàn)階段的學(xué)習(xí)狀態(tài)，同時也能對其將來的學(xué)習(xí)給予一定的提醒，學(xué)生能通過本系統(tǒng)制定更加符合自己特點的學(xué)習(xí)計劃。同時本系統(tǒng)也能夠幫助老師及時了解學(xué)生的學(xué)習(xí)狀態(tài)，并在必要的時候給同學(xué)合理的指導(dǎo)和幫助，對提高本校的教學(xué)質(zhì)量和提高大學(xué)生的綜合素質(zhì)都有很大的作用。

[參考文獻(xiàn)]

[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]吳暾華，王萍，劉婷.基于支持向量機的大學(xué)生學(xué)業(yè)動態(tài)預(yù)警研究[J].中國教育信息化，2017（17）：65-67.

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

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

[6]王華，劉萍.改進(jìn)的關(guān)聯(lián)規(guī)則算法在學(xué)生成績預(yù)警中的應(yīng)用[J].計算機工程與設(shè)計，2015（3）：679-682，752.