陳世保，吳國鳳

一種改進的Apriori算法在試卷評估中的應用研究

*陳世保1，吳國鳳2

（1.安徽財貿(mào)職業(yè)學院，安徽，合肥 230601；2.合肥工業(yè)大學，安徽，合肥 230009）

試卷評估是教學工作中非常重要的一部分，針對傳統(tǒng)試卷評估方法中僅僅是對試卷進行宏觀整體的分析與評價,缺乏對試卷的微觀分析。文章將一種高效的改進的Apriori算法應用在試卷分析中，挖掘出知識點之間的關(guān)聯(lián)，得到的結(jié)論對于教師改進教學方法、優(yōu)化教學效果，提高命題水平和試卷質(zhì)量對有巨大的指導作用，對于學生有針對性的學也具有巨大的指導作用，同時對于教學管理部門的決策提供了理論依據(jù)。

Apriori算法；試卷評估；關(guān)聯(lián)規(guī)則；數(shù)據(jù)挖掘

0 引言

試卷評估是考試閱卷完畢后對學生試卷進行的綜合分析，是教學過程中的一個必不可少的環(huán)節(jié)。試卷評估是評估教學質(zhì)量的一個重要依據(jù)，它是科學地修訂、篩選和調(diào)取使用試題的重要理論基礎(chǔ)，同時也是檢查學生掌握課程綜合知識能力的重要途徑，更是檢驗教師教學質(zhì)量和教學效果的具體體現(xiàn)。試卷評估所反饋的信息能為教學工作提供更有效的幫助，可以指導老師有針對性地調(diào)整教學計劃，調(diào)整教學策略以及改進教學方法，提高教學質(zhì)量。教學管理部門也可以依據(jù)上述數(shù)據(jù)做出決策，讓學校的決策建立在科學的基礎(chǔ)之上。

現(xiàn)有的試卷評估方法通過統(tǒng)計方法得到一些常用的指標，如試卷的期望值、最高得分、最低得分、全距、平均成績、標準偏差、難度系數(shù)、及格率以及分數(shù)段人數(shù)分布等，這些指標是對試卷進行了宏觀整體的分析和評價，雖然基本上能反映學生對課程的掌握程度，但是缺乏對具體考題的評價。

關(guān)聯(lián)規(guī)則挖掘是從大量的數(shù)據(jù)中挖掘出有價值的、描述數(shù)據(jù)項之間相互關(guān)聯(lián)的有關(guān)知識。最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法是Apriori算法，它是一種挖掘單維、單層、布爾關(guān)聯(lián)規(guī)則的算法[1]。該算法無論在處理的數(shù)據(jù)量還是處理效率上都有很大的局限性。本文討論了Apriori算法存在的不足以及改進的基本思想，并將其應用在試卷分析中。

1 試卷分析中的關(guān)聯(lián)規(guī)則問題描述

關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫中數(shù)據(jù)項之間存在的潛在關(guān)系的規(guī)則,形式為“A1∧A2∧…∧Am=>B1∧ B2∧…∧Bn”,其中Ai(i=1,2,…,m),Bj(j=1,2,…,n)是數(shù)據(jù)庫中的數(shù)據(jù)項。數(shù)據(jù)項之間的關(guān)聯(lián)規(guī)則即根據(jù)一個事務(wù)中某些項的出現(xiàn)，可推導出另一些項在同一事務(wù)中也出現(xiàn)。

在給定的數(shù)據(jù)庫D，關(guān)聯(lián)規(guī)則挖掘問題就是產(chǎn)生支持度和置信度分別大于用戶給定的最小支持度(minsup) 和最小置信度(minconf) 的關(guān)聯(lián)規(guī)則。例如，在某門課程試卷得分情況的數(shù)據(jù)庫中，1000個學生中有600個學生答對第10題、第20題，而這600個學生中又有360個學生答對了第1題，則規(guī)則對答對第10題、第20題的學生同時又答對第1題的的支持度S=360/1000=0.36（答對第10題、第20題和第1題360人占總?cè)藬?shù)的比例），置信度C=360/600=0.6（答對第10題、第20題和第1題360人占答對第10題、第20題600人的比例）。

2 Apriori算法分析及其缺點

2.1 算法的基本原理和性質(zhì)

Apriroi 算法是一個基于兩階段頻繁項集的數(shù)據(jù)挖掘方法[2]，將關(guān)聯(lián)規(guī)則挖掘算法分為兩部分：一是找到所有支持度大于最小支持度的項集，二是使用第一步找到的頻繁項集產(chǎn)生期望的規(guī)則。

首先產(chǎn)生頻繁1-項集L1，然后是頻繁2-項集L2，直到有某個r 值使得Lr為空，算法停止。這里在第k 次循環(huán)中，過程先產(chǎn)生侯選k-項集的集合Ck，Ck中的每一個項集是對兩個只有一個項不同的屬于Lk-1的頻繁集做一個（k-2）連接來產(chǎn)生的。Ck中的項集是用來產(chǎn)生頻繁集的候選集，最后的頻繁集Lk必須是Ck的一個子集。如果Ck中某個候選集有一個（k-1）子集不屬于Lk-1，則這個項集可以被修剪掉不予考慮。

性質(zhì)1：一個頻繁項目集的任一非空子集必定也是頻繁項目集[2]；

性質(zhì)2：一個非頻繁項目集的任一超集必定也是非頻繁項目集[2]；

性質(zhì)3：若一個事務(wù)包含K個元素，則該事務(wù)不可能包含k+1-項集[2]；

性質(zhì)4：K維數(shù)據(jù)項集XK是頻繁項集的必要條件是它所有K-1維子項集也為頻繁項集，記為XK-1[6]

性質(zhì)5：若在k-維數(shù)據(jù)項目集X={i1,i2, …,ik}中，存在一個j∈X，使得|Lk-1(j)|

2.2 Apriori算法三個步驟

(1)連接步驟：連接(k-1)-頻繁項集生成k-項候選集?？梢赃B接的條件是2個(k-1)項的前(k-2)項相等并且第1個(k-1)項集的第(k-1)項比第2 個(k-1)項集的第(k-1)項小。記li[j]為li中的第j個項，則條件即為：

l1[1]=l2[1]∧l1[2]=l2[2]∧…∧l1[k-2]=l2[k-2]∧l1[k-1]

(2)刪除步驟：利用Apriori 性質(zhì)對k-項候選集進行剪枝。剪枝的規(guī)則是：若一個k-項候選集的任一子集((k-1)-項集)不屬于(k-1)-項頻繁集L，那么該候選k-項集就不可能成為一個頻繁k-項集，可以將其刪除。

(3)計數(shù)步驟：掃描數(shù)據(jù)庫，累加k-項候選集在數(shù)據(jù)庫中出現(xiàn)的次數(shù)。對于一條記錄和一個候選項集，若記錄包含該候選項集，則該候選項集出現(xiàn)的次數(shù)就加1。最后根據(jù)給定的最小支持度閾值(minsup)生成k-項頻繁集。

2.3 Apriori算法的缺點

(1) 由k-1階頻繁集生成K階候選頻繁集時，產(chǎn)生的候選項集太多，沒有排除不應該參與組合的元素

(2) 由k-1階頻繁集生成K階候選頻繁集時，在K階候選頻繁集中過濾掉非頻繁集的策略值得進一步改進。

(3) 連接程序中相同的項目重復比較太多，因而其效率值得進一步改進。

(4) 在回掃數(shù)據(jù)庫時有許多不必比較的項目或事務(wù)重復比較。

3 Apriori算法的改進和在試卷分析中的應用

3.1 改進的思想

針對以上提出的四點不足進行整改，在候選項集確定一個子項集是否頻繁時，需掃描整個數(shù)據(jù)庫。如果能將數(shù)據(jù)庫中一些不必要的事務(wù)事先刪除，則可減少掃描數(shù)據(jù)量。另外如果事先能過濾掉候選項集中的非頻繁子集，這樣也能減少計算量。同時在由LK-1組合成CK前，對將參與組合的元素進行計數(shù)處理，根據(jù)計數(shù)結(jié)果決定排除一些不符合組合條件的元素。本方法是將三者結(jié)合起來一起考慮。

3.2 在試卷分析中的應用

選取8名學生某門課程的試卷部分試題得分情況的數(shù)據(jù)，對改進的算法進行詳細的演示。假定支持度為2。數(shù)據(jù)表如表1：

表1 學生試卷得分情況表

注：Ii(i=1, 2，…,8)表示試題編號，Tj(j=1，2，…,8)表示學生編號，表中第i行第j列所對應得數(shù)值1表示第j個學生正確回答了第i題，SUM用來對事務(wù)中包含的項進行計數(shù)（即學生答對試卷中的題目數(shù)量），COUNT用來對表格中某列值為1的項進行計數(shù)（即某道試題被答對的學生數(shù)）。

從表1中，根據(jù)minsup =count≥2，得到1-頻繁項集{I1}{I2}{I3}{I4}{I5}{I6}。

約簡事務(wù)：從表1中可以看出TID為T4的事務(wù)只包含單項集{I6}，T4不可能包含任何一個鏈接后的2-項集或者K-項集（K≧2）(性質(zhì)3)，故T4事務(wù)在后面的高階頻繁項集中不再用到，刪除T4。得到表2：

表2 得到頻繁1-項集L1

根據(jù)Apriori算法：項之間作邏輯與運算構(gòu)成2-項集，結(jié)果如表3：

表3 由L1得到的候選2-項集C2

約簡事務(wù)：由表3可以求出頻繁2-項集，首先刪除count<2的列，另外由于T5、T6、T7三個事務(wù)只包含2個元素，故在以后的3-項集或更高階項集的鏈接中不再用到這些事務(wù)(性質(zhì)3)，將其刪除。得到的頻繁2-項集：{I1I2}{I1I3}{I1I4}{I1I5}{I2I3}{I2I4} {I2I5}{I3I4}{I4I5}{I5I6}。得到表4：

表4 由C2得到的頻繁2-項集L2

根據(jù)Apriori算法的：項之間作邏輯與運算構(gòu)成3-項集，結(jié)果如表5：

表5 由L2得到的候選3-項集C3

約簡事務(wù)：由表5可以求出頻繁3-項集，首先刪除count<2的列，另外由于T8三個事務(wù)只包含3個元素，故在以后的4-項集或更高階項集的鏈接中不再用到這些事務(wù)(性質(zhì)3)，將其刪除。得到頻繁3-項集{I1I2I3}{I1I2I4}{I1I215}{I1I4I5}{I2I3I5}{I2I4I5}。得到表6：

表6 由C3得到的頻繁3-項集L3

在由L3產(chǎn)生C4前進一步約簡：根據(jù)性質(zhì)5，在第k步中，根據(jù)k-1步生成的k-1維頻繁項目集來產(chǎn)生k維候選項目集，產(chǎn)生k-1維頻繁項目集時，對該集中出現(xiàn)元素的個數(shù)進行計數(shù)處理，因此對某元素而言，若它的計數(shù)個數(shù)不到k-1的話，可以事先刪除。根據(jù)頻繁3-項集得到的元素計數(shù)：｛I1:4, I2:5, I3:2, I4:3, I5:3｝，故可以刪除包含I3元素的頻繁3-項集。然后進行邏輯與運算得到4-項集，如表7：

表7 由L3得到的修選4-項集C4

由表7可以看出，最終產(chǎn)生頻繁4-項集｛I1I21415｝。

3.3 算法評估

為了證實對Apriori算法的改進效果，對Apriori算法和改進的算法進行了測試。數(shù)據(jù)來源于我校2010年《計算機基礎(chǔ)》課程中的數(shù)據(jù)，將1000人的答題情況轉(zhuǎn)換為布爾型事務(wù)數(shù)據(jù)庫，然后進行測試。

圖1 算法效率對比

圖1為改進的算法和傳統(tǒng)的Apriori算法在不同的支持度下找出所有頻繁項集所用的時間對比圖。實驗結(jié)果表明在支持度比較大的時候兩個算法性能差異不大，當支持度比較小也就是產(chǎn)生的頻繁項集比較多的時候，則性能差異比較大。

4 規(guī)則產(chǎn)生

以上通過關(guān)聯(lián)規(guī)則算法挖掘出了頻繁項集后，再對頻繁項集進行分析，找出教師或者教學管理部門感興趣的模式或規(guī)則，得到試卷中試題之間有用的強關(guān)聯(lián)規(guī)則。假定給定置信度90%，則產(chǎn)生的部分強關(guān)聯(lián)規(guī)則如表8：

表8 由頻繁項集產(chǎn)生的強關(guān)聯(lián)規(guī)則

5 關(guān)聯(lián)規(guī)則結(jié)果分析

在對試卷的難度及每道題的知識點全面分析后，再根據(jù)挖掘結(jié)果進行分析，并以{I4，I5}→ {I1}[25%，100%]強關(guān)聯(lián)規(guī)則為例進行分析，不再逐一進行分析。該強關(guān)聯(lián)規(guī)則表明：25%的學生答對了I4、I5題，但是答對I4和I5題的學生全部答對了I1題。這表明I1題和I4、I5題具有很強的關(guān)聯(lián)聯(lián)系，從試卷的質(zhì)量上來說I1題和I4、I5題在知識點上可能重合，或者該知識點非常重要所以有意的強化該知識點；從教學上面來說，教師可以重點講授I4題和I5題的知識點，而不是I1的知識點，掌握了I4題和I5題的知識點后，自然就理解或掌握了I1，這樣對于教師有針對性的授課和改進教學方法都提供了理論依據(jù)。從教學內(nèi)容的組織上來說，教師應該先講授I4題和I5題的知識點；對于學生而言，將學習的重點放在I4、I5題，指導學生有側(cè)重點的學習和復習，達到學習效率更高效，學習效果更好。以上的信息對教學具有非常好的指導作用，為相關(guān)部門決策提供理論依據(jù)，有促于教學大綱的制定以及學生復習計劃的執(zhí)行。

6 結(jié)論

試卷評估是每個學校教學中的重要環(huán)節(jié)，我們要充分利用試卷中的信息，挖掘出有意義、有價值的信息，就可以為教師有針對性地調(diào)整教學計劃，調(diào)整教學策略以及改進教學方法提供科學依據(jù)，進而提高教學質(zhì)量。文章是對學生答對的題目重點進行關(guān)聯(lián)分析，也還可以對學生失分的題目進行關(guān)聯(lián)分析[5]，進而幫助老師有側(cè)重點的教，也幫助學生有側(cè)重點的學。

[1] Tan Pangning, Steinbach M, Kumar V. Introduction to Data Mining[M]. 北京: 人民郵電出版社, 2006.

[2] Han Jiawei, Kamber M. Data Mining. Concepts and Techniques[M].北京: 機械工業(yè)出版社, 2001.

[3] 賈文,臧明相,周鴻．基于數(shù)據(jù)挖掘的課程相關(guān)性研究與分析[J].計算機技術(shù)與發(fā)展,2006,16(12):178-180.

[4] 趙輝.數(shù)據(jù)挖掘技術(shù)在學生成績分析中的研究及應用[D].大連:大連海事大學,2007.

[5] 張瑤, 陳高云, 王鵬．數(shù)據(jù)挖掘技術(shù)在試卷分析中的應用[J].西南民族大學學報:自然科學版,2008,34(4)：839-842.

[6] 錢光超,賈瑞玉,張然,等．Apriori算法的一種優(yōu)化方法[J].計算機工程,2008,34(23):196 -198.

Design and Implementation of News Gathering System Based on Web Structure

*CHEN Shi-bao1，WU Guo-fen2

(1.Anhui Finance and Trade Vocational College, Hefei, Anhui 230601, China;2.Hefei University of Technology, Hefei,Anhui 230009, China )

Examination paper evaluation is a very important part of the traditional assessment methods in the teaching work. According to the macroscopic analysis on the examination paper and the lack of microscopic analysis, we improves the Apriori algorithm of the examination paper analysis which excavates the knowledge correlation, improves their teaching methods, optimizes the effect of teaching and the quality of the proposition. It also has a huge role in guiding students learning and theoretical basis for the decision provided for teaching management.

apriori algorithm; examination paper evaluation; association rules; data mining

TP274

A

10.3969/j.issn.1674-8085.2012.02.015

1674-8085(2012)02-0058-05

2012-01-08；

2012-02-21

*陳世保(1981-)，男，安徽合肥人，工程師，研究生，主要從事數(shù)據(jù)庫技術(shù)研究(E-mail:Chenshibao@189.cn);

吳國鳳(1964-)，女，安徽合肥人，副教授，碩士生導師，主要從事計算機網(wǎng)絡(luò)技術(shù)、網(wǎng)絡(luò)安全研究(E-mail:guofen@163.com).