改進的APRIORI算法在試卷系統數據挖掘中的應用

黃藝坤

（福建師范大學協和學院 福建 350117）

0 引言

試卷系統有利于高校建立課程題庫，現在各個高校都在倡導題庫建設，通過試卷系統就可以把題庫信息采集在數據庫里，要查詢歷史題庫只要打開后臺就可以查到相關試卷，考試也只要通過自動組卷和隨機排序組成相同難度，不同序列的題目給考生，避免了學生作弊。

很多試卷系統在自動組卷時，往往只考慮考試范圍而忽略了考試難度，因此每次組卷時，試卷的難度很難把控。本文通過對Apriori算法進行改進，利用計算機容量大、計算速度快等優點，考慮各種因素和關聯，實現數據分析和數據挖掘，通過改進，可以隨機組成更科學、更有難度梯度的試卷，這樣也有利于課程的建設和發展。

1 數據挖掘技術

1.1 數據挖掘技術概述

數據挖掘是對存在大量數據的數據倉庫進行數據分析，通過分析找出數據與數據之間的關聯關系，從而挖出更有價值的信息。數據準備、數據挖掘和結果表達與解釋是數據挖掘的主要三個步驟。數據準備是把需要進行挖掘的數據從數據庫中抽出，并整合成數據集；規律尋找是使用特定的算法把數據中存在的某種規律找出；規律表示是用用戶看得懂的方法表示出數據之間的規律，這個規律即是有價值的線索。普遍認為數據挖掘是數據庫中發現有價值信息的一個重要環節。它一般分為以下幾個階段：選擇數據集、數據預處理、數據形式轉變、實施數據挖掘以提取模式和關系、結果表達和解釋。

1.2 Apriori算法

Apriori算法是一種數據挖掘關聯規則中的典型算法。該算法在生成頻繁項集時會有頻繁的數據庫掃描操作，并且在由低維頻繁項集連接生成高維候選項集時，如果頻繁項集維數過大，笛卡爾積后就會產生大量的候選項集，從而影響算法的效率。針對上述2個方面對Apriori算法進行改進，并將改進后的算法應用在試卷分析系統中。經過系統測試，改進后的算法具有較高的效率和較強的穩定性。

2 組卷方法

2.1 Apriori在組卷中的應用

為了使試題在自動抽取過程中能夠使試題在知識點分布上更均衡、更廣泛，同時使試題的難度系數有一定梯度抽取，本文采用數據挖掘中的關聯規則法對數據進行挖掘分析，在分析中采用了改進型的Apriori算法，使挖掘效率更好，數據更準確。

在Apriori使用過程中，系統先對全局數據集進行檢查，如在答題庫中，把考生作答時同一章節的考題同時作對或同時做錯的題型記錄到高頻集，如果優等生同時做錯的題目和差等生同時做對的題目分別放在兩個高頻集里，在自動組卷之后，可以通過高頻集來判斷試卷的質量，同一份試卷里，高頻集出現的越多，則試卷質量越差，這樣在自動組卷過程中，可以利用高頻集來評價。Aprior篩選高頻集的方法是先把篩選出的高頻集并記錄在N1集合，再把N1作為參考集合對數據庫進行挖掘，找出M2集合，再由M2產生N2，以此類推，直到找出所有的頻繁項集，Apriori算法如下：

（1）設置相應的最小支持度閾值Minimum_Threshold

（2）在數據集 DATASET中找出高頻集N1=FIND_ONE_ITEM（DATASET）；

（3）FOR（X =2；NX-1≠Φ；X＋＋）{

MX=APRIORI_GEN（NX-1，Minimum_Threshold）；

（4）FOR_EACH TRANSACTION Y∈D

{ MY=SUBSET（MX，Y）；

FOR_EACH CANDIDATE c∈MY

m.COUNT＋＋；}

（5）NX=｛m∈MX｜ m.COUNT>=Minimum_Threshold｝

}

（6）RETURN N=∪XNX；

2.2 改進Apriori算法

通過對Apriori算法進行研究，發現雖然該算法和其他算法比起來在查找最優解上具有很強的優勢，但在實際操作中每次生成單個N集合都要對數據庫進行循環篩查數據庫一次，這樣是會給服務器的運行帶來壓力，運行效率低等問題，針對以上問題，本文對Apriori算法進行了改良。

在數據挖掘中，我們還可以把差生（小于60分的考生）同時作對的題目或優等生（大于80分的考生）同時做錯的題目作為高頻集，記錄為MK（K=1）或LK（K=1），通過把高頻集M和L作為參考集使用改進型Apriori算法進行數據挖掘，可以分析出題庫中，差生容易掌握的題型和優等生中不容易掌握的題型，這些題型對于數據分析中具有重要作用，通過挖掘出來的數據，我們可以重新對這些題型的難易系數加以評級，對學生能掌握的知識點和不能掌握的知識點進行總結分析，這對今后的教學質量評估具有重要意義.

針對Apriori算法存在的問題，本文提出了改良型Apriori算法，改良后對數據集進行遍歷掃描時，去除一些非同源高頻集，增強了挖掘效率。改良的算法還針對自動組卷組成的試卷進行優化，通過高頻集篩選出優秀的試卷。經過改良后的算法如下：

（1）設置相應的最小支持度閾值Minimum_Threshold

（2）在數據集 DATASET中找出高頻集N1=FIND_ONE_ITEM（DATASET）；

（3）FOR（X =2；NX-1≠Φ；X＋＋）{

MX=APRIORI_GEN（NX-1，Minimum_Threshold）；

（4）FOR_EACH TRANSACTION Y∈D{

MY=SUBSET（MX，Y）；

（5）IF GET_JUDGE（MY，"約束條件"）THEN

（6）{ DELETE MY；

Continue；}

（7）FOR_EACH CANDIDATE c∈MY

（8）m.Count+=GETSCORE（c，Y）；}

（9）NX=｛m∈MX｜ m.COUNT>=Minimum_Threshold｝}

（10）RETURN N=∪XNX；

改良后的Apriori算法在對數據集操作中，在挖掘數據時，刪除非高頻集數據即把不在約束條件范圍內，不用再次查找的有效數據刪除，不斷減少數據量，挖掘的目標范圍也逐漸縮小，服務器的運行速度變快。改良后的算法會把抽取的數據和高頻集數據進行比較，通過 GETSCORE函數判斷數據的吻合程度然后對高頻集進行加權處理，不同的學校和不同的教學方案對此都有不同要求，如非很好`或很差的試卷返回分值1；優等卷中包含差生同時作對的試題，那么函數返回 0；優等卷中包含優等生同時做錯的題目，那么函數返回 2；在劣等卷中含差等生同時作對的題目，那么函數返回 0；在劣等卷中含有優等生同時作錯的題目，那么函數返回 1，以此類推，最后通過判斷閾值來生成最優試卷。

3 結束語

本文研究了數據挖掘技術在試卷系統自動組卷中的應用。數據挖掘技術除了用在自動組卷上，還可以用在學生成績分析上，由于難度系數的設置是由出題者設置的，考生所學知識點與試題所設置的難度系數不一定吻合，因此，本文還可以嘗試使用數據挖掘的關聯規則法，把考生答題庫和題庫兩個數據表作為原始數據，對某道題考生在答題過程中對錯概率進行挖掘分析，如某道題考生出現的錯誤率超過標準值那么教師就得知學生掌握知識點程度，在下次命題或者教學中就會做出相應的改變。

[1] 王金龍.全局和局部相結合的數據挖掘算法及應用研究[博士學位論文].浙江：浙江大學，2007.

[2] 黃玥.高校無紙化考試系統新探索.科技創新導報，2012，21：56.

[3] 薛樂，于建軍.淺談高校在線考試系統的設計與實現.科技資訊，2012，26：219.

[4] William J.Tastle.Data Mining Applications Using Artificial Adaptive Systems.Springer Science.2013.70-103.

[5] 呂健.試論計算機自動組卷的常用算法.電腦知識與技術，2011，08：1802-1803.