一種改進(jìn)的Apriori算法在試卷評(píng)估中的應(yīng)用研究

陳世保，吳國(guó)鳳

一種改進(jìn)的Apriori算法在試卷評(píng)估中的應(yīng)用研究

*陳世保1，吳國(guó)鳳2

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

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

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

0 引言

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

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

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

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

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

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

2 Apriori算法分析及其缺點(diǎn)

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

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

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

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

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

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

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

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

2.2 Apriori算法三個(gè)步驟

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

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

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

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

2.3 Apriori算法的缺點(diǎn)

(1) 由k-1階頻繁集生成K階候選頻繁集時(shí)，產(chǎn)生的候選項(xiàng)集太多，沒(méi)有排除不應(yīng)該參與組合的元素

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

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

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

3 Apriori算法的改進(jìn)和在試卷分析中的應(yīng)用

3.1 改進(jìn)的思想

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

3.2 在試卷分析中的應(yīng)用

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

表1 學(xué)生試卷得分情況表

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

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

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

表2 得到頻繁1-項(xiàng)集L1

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

表3 由L1得到的候選2-項(xiàng)集C2

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

表4 由C2得到的頻繁2-項(xiàng)集L2

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

表5 由L2得到的候選3-項(xiàng)集C3

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

表6 由C3得到的頻繁3-項(xiàng)集L3

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

表7 由L3得到的修選4-項(xiàng)集C4

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

3.3 算法評(píng)估

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

圖1 算法效率對(duì)比

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

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

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

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

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

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

6 結(jié)論

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

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

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

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

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

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

[6] 錢(qián)光超,賈瑞玉,張然,等．Apriori算法的一種優(yōu)化方法[J].計(jì)算機(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ù)庫(kù)技術(shù)研究(E-mail:Chenshibao@189.cn);

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