陳世保，徐 峰，吳國鳳

基于難度系數(shù)的加權(quán)關(guān)聯(lián)規(guī)則在試卷評估中的應(yīng)用

*陳世保1，徐 峰1，吳國鳳2

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

針對傳統(tǒng)的關(guān)聯(lián)規(guī)則在試卷評估中應(yīng)用出現(xiàn)的問題：由于試題的難易程度不同，被答對的概率也不一樣，即數(shù)據(jù)集中數(shù)據(jù)項發(fā)生的概率不一樣，數(shù)據(jù)項具有傾斜支持度分布的特征，選擇合適的支持度閾值挖掘這樣的數(shù)據(jù)集相當棘手。文章提出了基于試題難度系數(shù)加權(quán)的關(guān)聯(lián)規(guī)則挖掘算法，從而解決因試題難度不同而導(dǎo)致數(shù)據(jù)項出現(xiàn)的概率不均的問題，發(fā)現(xiàn)更多有趣的關(guān)聯(lián)規(guī)則，并且理論上證明了基于難度系數(shù)的加權(quán)關(guān)聯(lián)規(guī)則算法保持頻繁項集向下封閉的重要特性。

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

1 問題提出的背景

數(shù)據(jù)挖掘是指從大量的數(shù)據(jù)中發(fā)現(xiàn)人們事先不知道的、有用的知識（模式）的處理過程，它是繼數(shù)據(jù)庫、人工智能等領(lǐng)域之后發(fā)展起來的一門重要學(xué)科[1]，是目前國際上數(shù)據(jù)庫和信息決策領(lǐng)域比較前沿的研究方向。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘重要的研究分支，Agrawal等人[2]于1993年首次提出關(guān)聯(lián)規(guī)則挖掘后，引起了國際上廣泛的關(guān)注，文獻[3]首次提出了經(jīng)典的Apriori算法，并成功應(yīng)用到商業(yè)中。

在試卷評估中更是如此，由于試題的難易程度不同，因此試題被答對的概率也不一樣，即試卷的事務(wù)數(shù)據(jù)庫中數(shù)據(jù)項出現(xiàn)的頻率不一樣：難度大的試題在數(shù)據(jù)庫中出現(xiàn)的概率低，即具有較低的支持度；難度小的試題在數(shù)據(jù)庫中出現(xiàn)的概率高，即具有較高的支持度。根據(jù)試卷評估中數(shù)據(jù)項出現(xiàn)的概率和試題的難易程度有關(guān)，故提出基于難度系數(shù)的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法，以解決此問題。

2 試卷評估中的關(guān)聯(lián)規(guī)則形式化描述

由于關(guān)聯(lián)規(guī)則挖掘算法針對的是事務(wù)數(shù)據(jù)庫，因此需對學(xué)生作答的試卷進行轉(zhuǎn)換，轉(zhuǎn)換成事務(wù)數(shù)據(jù)庫。

表1 學(xué)生試卷事務(wù)數(shù)據(jù)庫

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

3 基于難度系數(shù)的加權(quán)關(guān)聯(lián)規(guī)則

Apriori算法[5]是最經(jīng)典的關(guān)聯(lián)規(guī)則算法，Apriori算法是一種寬度優(yōu)先算法，采用逐層搜索的迭代方法[5]，其基本思想是重復(fù)掃描數(shù)據(jù)庫。首先，產(chǎn)生頻繁1-項集L1，然后是頻繁2-項集L2，直到有某個日r值使得Lr為空，算法停止。這里在第k次循環(huán)中，先產(chǎn)生侯選k-項集的集合Ck，Ck中的每一個項集是對兩個只有一個項不同的屬于L(k-1)的頻繁集做一個（k-2）連接來產(chǎn)生的。Ck中的項集是用來產(chǎn)生頻繁集的候選集，最后的頻繁集Lk必須是Ck的一個子集。如果Ck中某個候選集有一個（k-1）子集不屬于L（k-1），則這個項集可以被修剪掉不予考慮，這是基于算法的頻繁項集向下封閉的性質(zhì)：一個項集是頻繁的當且僅當它所有子集都是頻繁的[6]。

目前很多學(xué)者都在研究加權(quán)關(guān)聯(lián)規(guī)則算法[7]，加權(quán)關(guān)聯(lián)規(guī)則算法在關(guān)聯(lián)規(guī)則的挖掘過程中考慮了人們對項目的興趣（權(quán)值）。權(quán)值的賦予具有很大的主觀隨意性，很難把握；另一方面，由于權(quán)值的引入，破壞了頻繁項集的封閉性，即頻繁項集的任一子集不一定是頻繁的，因此不能再利用該性質(zhì)進行候選項集的剪枝。

本文引入基于難度系數(shù)的加權(quán)規(guī)則算法能有效解決由于試題難度不一而導(dǎo)致的數(shù)據(jù)項分布不均的問題，同時也不破壞關(guān)聯(lián)規(guī)則算法的頻繁項集的封閉性[8]。下面給出算法的相關(guān)定義：

定義1 難度系數(shù)也可以理解成“容易度系數(shù)”，是0~1之間的量值，難度系數(shù)越大，說明題目難度越小。難度系數(shù)一般分整卷難度系數(shù)和單題難度系數(shù)。文章中主要指單題難度系數(shù)，記作Pi。

Pi(第i題難度系數(shù))=Ai(第i題平均得分)/Ti(第i題滿分)

定義2 項目屬性ij的權(quán)是與項目難度系數(shù)有關(guān)的權(quán)，記作：W（ij）。在本文中被定義為試卷的邏輯事務(wù)數(shù)據(jù)庫D中該試題難度系數(shù)的倒數(shù)。

W（ij）=1/Pj

那么試題難度越大Pj越小，則W（ij）的值越大，也就是權(quán)重越大。

定義3 數(shù)據(jù)項集I的權(quán)是數(shù)據(jù)項集I中所有項目權(quán)值得均值。記作：W(I)

定義4 交易事務(wù)t的權(quán)重是指數(shù)據(jù)集D中某一條記錄的權(quán)值，記作：W（tk），是所有屬于tk的項目權(quán)值的均值。

該定理也說明了基于難度系數(shù)加權(quán)的關(guān)聯(lián)規(guī)則算法保持了Apriori算法的向下封閉性，非頻繁項集的超集也是非頻繁的。

4 算法描述

基于難度系數(shù)加權(quán)的關(guān)聯(lián)規(guī)則算法和Apriori算法很類似，都是首先根據(jù)指定的最小支持度（minsup）找出數(shù)據(jù)集D中所有的頻繁項目集。然后根據(jù)第一步挖掘出的頻繁項目集和指定的最小置信度（minconf）產(chǎn)生強關(guān)聯(lián)規(guī)則。

算法的偽碼如下：

1) W(ij)=scan(D) //掃描數(shù)據(jù)庫D，根據(jù)定義1獲得項目ij的權(quán)值。

2) L1= find_frequent_1_itemsets(D) //產(chǎn)生頻繁1-項集

3) for (k = 2; L(k-1)≠ ?; k++) {

4) Ck= aproiri_gen(L(k-1),min_sup)

5) for each transaction t∈D{

6) for each transaction t∈D{

7) Ct= subset(Ck,t)

8) for each candidate c∈Ct

9) c.wsp+=w(t) }

10) Lk={c∈Ck| c.wsp/w(D) ≥ min_sup}

11) return L = ∪Lk；

算法首先掃描數(shù)據(jù)庫scan(D)，根據(jù)定義1和定義2計算出各項的權(quán)值;然后算法步驟2再次掃描數(shù)據(jù)庫產(chǎn)生頻繁1-項集find_frequent_1_itemsets(D)：根據(jù)定義3和定義4計算出事務(wù)的權(quán)值w(tk)，整個數(shù)據(jù)庫D的所有事務(wù)的權(quán)值W(D)，項目的加權(quán)支持度，并根據(jù)用戶給定的最小支持度（minsup）獲得頻繁1-項集L1; aproiri_gen函數(shù)對L(K-1)頻繁項集進行聯(lián)合、剪枝，得到K-候選項集Ck，aproiri_gen函數(shù)的實現(xiàn)與Apriori算法中的一樣，在此不再贅述。

本算法比Apriori算法增加了一次掃描數(shù)據(jù)庫的過程，目的是得到數(shù)據(jù)項的權(quán)值、事務(wù)的權(quán)值。

5 加權(quán)算法在試卷評估中的挖掘過程

根據(jù)試卷轉(zhuǎn)化成事務(wù)數(shù)據(jù)庫的規(guī)則，結(jié)合事務(wù)和項集的權(quán)值的概念，對試卷進行轉(zhuǎn)化，如表2和表3。然后將基于難度系數(shù)的加權(quán)關(guān)聯(lián)規(guī)則應(yīng)用到該數(shù)據(jù)庫中，充分理解該算法在試卷評估中的挖掘過程。

表2 數(shù)據(jù)庫的事務(wù)記錄

表3 數(shù)據(jù)庫的項目的權(quán)

假定最小支持度minsup = 0.2，同時基于難度系數(shù)的加權(quán)最小支持度min-wsp = 0.2。由表2和表3看出使用難度系數(shù)加權(quán)的關(guān)聯(lián)規(guī)則能夠挖掘出包含低支持度項的模式，能夠發(fā)現(xiàn)更多的有趣的關(guān)聯(lián)規(guī)則。例如：表2中{I2，I3，I6}項集的支持度sup = 1/6<0.2，根據(jù)傳統(tǒng)的關(guān)聯(lián)規(guī)則，{I2，I3，I6}不是頻繁項集；而根據(jù)難度系數(shù)加權(quán)的關(guān)聯(lián)規(guī)則{I2，I3，I6}的加權(quán)支持度為min-wsp=3.5/12=0.291>0.2，{I2，I3，I6}是頻繁項集。這說明試卷中的I6的試題難度很大，答對的人少，若是傳統(tǒng)的關(guān)聯(lián)規(guī)則將會丟失包含I6試題的有趣的規(guī)則，而使用基于難度系數(shù)加權(quán)的關(guān)聯(lián)規(guī)則可以挖掘出來，克服了傳統(tǒng)的關(guān)聯(lián)規(guī)則在試卷評估應(yīng)用的缺陷。

6 算法評估

為了證實基于難度系數(shù)的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法的改進效果，對基于難度系數(shù)的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法進行了測試。數(shù)據(jù)來源于我校2010年《會計基礎(chǔ)》課程中的數(shù)據(jù)，將1000人的答題情況轉(zhuǎn)換為布爾型事務(wù)數(shù)據(jù)庫，然后分別用Apriori算法、一種改進的加權(quán)關(guān)聯(lián)規(guī)則算法[9]和基于難度系數(shù)的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法進行挖掘做出對比。如圖1和圖2：

圖1 算法挖掘效率比較

圖2 算法產(chǎn)生的規(guī)則數(shù)比較

從圖1和圖2中可以看出：1）由于采用了難度系數(shù)的加權(quán)之后，提升了難度較大試題的支持度，同時降低了難度較低試題的支持度，使各個項目的加權(quán)支持度趨向于平均，因此可以挖掘出了更多的規(guī)則；2）在試卷評估中使用難度系數(shù)確定權(quán)值是比較合理和理想的；3）由于基于難度系數(shù)加權(quán)的關(guān)聯(lián)規(guī)則算法仍然保持向下封閉性，因此本文中的算法和文獻[10]加權(quán)關(guān)聯(lián)規(guī)則算法基本保持一致，但是總體比Apriori算法性能優(yōu)越。

7 結(jié)論

試卷評估是學(xué)校教學(xué)中的重要環(huán)節(jié)，要充分利用試卷中的信息，挖掘出有意義、有價值的信息，為教師有針對性地調(diào)整教學(xué)計劃，調(diào)整教學(xué)策略以及改進教學(xué)方法提供科學(xué)依據(jù)，提高教學(xué)質(zhì)量。根據(jù)試卷質(zhì)量符合正態(tài)分布的特性，轉(zhuǎn)換后的事務(wù)數(shù)據(jù)庫具有傾斜支持度分布的特征，采用Apriori算法進行挖掘?qū)G失很多有價值的信息。文章采用基于難度系數(shù)的加權(quán)關(guān)聯(lián)規(guī)則能夠很好的解決這個問題，挖掘出更多的有趣的關(guān)聯(lián)規(guī)則，為教學(xué)提供更多的有意義的信息，為教師和相關(guān)部門決策提供理論依據(jù)。

[1] Han J, KamberM.數(shù)據(jù)挖掘:概念與技術(shù)[M].范明,孟小峰譯.北京:機械工業(yè)出版社,2001.

[2] Agrawal R, Imielinski T, Swami A N. Mining association rules between sets of items in large databases[C]. ACM SIGMOD, 1993:207-216.

[3] Fayyad U M,Smyth P. Advances in Knowledge Discovery and Data Mining[M].NewYork:MIT Press,1996.

[4] 詹芹,張幼明.一種改進的動態(tài)遺傳Apriori挖掘算法[J].計算機應(yīng)用研究,2010,27(8) :2929-2930,2935.

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

[6] 李剛,董祥軍.多支持度慣量規(guī)則的研究[J].廣西輕工業(yè),2007,10(5):60-62.

[7] 歐陽為民,鄭誠,蔡慶生.數(shù)據(jù)庫中加權(quán)規(guī)則的發(fā)現(xiàn)[J].軟件學(xué)報,2001,12(1):612-619.

[8] 尹群,王麗珍,田啟明.一種基于概率的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法[J].計算機應(yīng)用,2005,2(4):805-807.

[9] 陳世保,吳國鳳.一種改進的Apriori算法在試卷評估中的應(yīng)用研究[J]. 井岡山大學(xué)學(xué)報:自然科學(xué)版,2012,4(2): 58-62.

[10] 李成軍,楊天奇.一種改進的加權(quán)關(guān)聯(lián)規(guī)則挖掘方法[J].計算機工程,2010,36(7):55-57.

WEIGHTED ASSOCIATION RULES BASED ON THE COEFFICIENT OF DIFFICULTY IN THE ASSESSMENT OF PAPERS

*CHEN Shi-bao1，XU Feng1，WU Guo-feng2

（1. Anhui Finance & Trade Vocational College, Hefei, Anhui 230601; 2. HeFei University of Technology, Hefei, Anhui 230009, China）

With the wide range of data mining applications, the association rule mining algorithm is applied to the paper assessment in the literature. Traditional association rule data mining problems in the papers assessment, such as the degree of difficulty of questions is different, the probability of being correct answers are not the same, that is to say, the data set is not the same as the probability of data entry, data entry with a sloping support the distribution of the characteristics of mining such data sets is very difficult to select the appropriate support threshold. We present the association rules mining algorithm based on item difficulty coefficient weighted to solve the problem of uneven frequency of data items appear different item difficulty and find more interesting association rules. Furthermore, we prove theoretically that the weighted association rules based on the coefficient of difficulty to maintain the important features of the frequent item sets is downward closed.

Apriori algorithm; evaluation; association rule; data mining; difficulty coefficient

TP274

A

10.3969/j.issn.1674-8085.2013.01.015

1674-8085(2013)01-0070-05

2012-06-12；

2012-07-28

安徽省高等學(xué)校重點教學(xué)研究項目(20101766)

*陳世保(1981-），男，安徽合肥人，工程師，碩士，主要從事數(shù)據(jù)庫技術(shù)，數(shù)據(jù)庫應(yīng)用研究(E-mail: chenshibao@189.cn);

徐 峰(1967-），男，安徽合肥人，正高級工程師，碩士，主要從事軟件工程、計算機網(wǎng)絡(luò)研究(E-mail:xuf@163.com);

吳國鳳(1954-），女，安徽合肥人，合肥工業(yè)大學(xué)副教授，碩士生導(dǎo)師，主要從事計算機網(wǎng)絡(luò)技術(shù)、網(wǎng)絡(luò)安全研究(E-mail:wgf@126.com ).