陳世保，徐 峰，吳國鳳

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

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

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

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

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

1 問題提出的背景

數(shù)據(jù)挖掘是指從大量的數(shù)據(jù)中發(fā)現(xiàn)人們事先不知道的、有用的知識(shí)（模式）的處理過程，它是繼數(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)注，文獻(xiàn)[3]首次提出了經(jīng)典的Apriori算法，并成功應(yīng)用到商業(yè)中。

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

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

由于關(guān)聯(lián)規(guī)則挖掘算法針對(duì)的是事務(wù)數(shù)據(jù)庫，因此需對(duì)學(xué)生作答的試卷進(jìn)行轉(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個(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題的的支持度supp=360/1000=0.36（答對(duì)第10題、第20題和第1題360人占總?cè)藬?shù)的比例），置信度conf=360/600=0.6（答對(duì)第10題、第20題和第1題360人占答對(duì)第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-項(xiàng)集L1，然后是頻繁2-項(xiàng)集L2，直到有某個(gè)日r值使得Lr為空，算法停止。這里在第k次循環(huán)中，先產(chǎn)生侯選k-項(xiàng)集的集合Ck，Ck中的每一個(gè)項(xiàng)集是對(duì)兩個(gè)只有一個(gè)項(xiàng)不同的屬于L(k-1)的頻繁集做一個(gè)（k-2）連接來產(chǎn)生的。Ck中的項(xiàng)集是用來產(chǎn)生頻繁集的候選集，最后的頻繁集Lk必須是Ck的一個(gè)子集。如果Ck中某個(gè)候選集有一個(gè)（k-1）子集不屬于L（k-1），則這個(gè)項(xiàng)集可以被修剪掉不予考慮，這是基于算法的頻繁項(xiàng)集向下封閉的性質(zhì)：一個(gè)項(xiàng)集是頻繁的當(dāng)且僅當(dāng)它所有子集都是頻繁的[6]。

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

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

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

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

定義2 項(xiàng)目屬性ij的權(quán)是與項(xiàng)目難度系數(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ù)項(xiàng)集I的權(quán)是數(shù)據(jù)項(xiàng)集I中所有項(xiàng)目權(quán)值得均值。記作：W(I)

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

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

4 算法描述

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

算法的偽碼如下：

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

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

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

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

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

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

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

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

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

6 算法評(píng)估

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

圖1 算法挖掘效率比較

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

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

7 結(jié)論

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

[1] Han J, KamberM.數(shù)據(jù)挖掘:概念與技術(shù)[M].范明,孟小峰譯.北京:機(jī)械工業(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] 詹芹,張幼明.一種改進(jìn)的動(dòng)態(tài)遺傳Apriori挖掘算法[J].計(jì)算機(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é)報(bào),2001,12(1):612-619.

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

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

[10] 李成軍,楊天奇.一種改進(jìn)的加權(quán)關(guān)聯(lián)規(guī)則挖掘方法[J].計(jì)算機(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é)校重點(diǎn)教學(xué)研究項(xiàng)目(20101766)

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

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

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