黃藝坤

傳統(tǒng)的考試從古至今一直以“筆試”為主,考試過程都需要人工來完成各項工作.傳統(tǒng)考試的出題、改卷、試卷管理、分數(shù)登記等環(huán)節(jié)不僅需要安排大量工作人員,還要花很多時間和勞務費,除此之外,考務工作也是考試過程中一項煩瑣的工作.隨著信息化發(fā)展,傳統(tǒng)考試的形式出現(xiàn)了越來越多的問題,缺點顯而易見,無紙化考試系統(tǒng)正是在這種環(huán)境下顯得很有優(yōu)勢.

高校的無紙化考試系統(tǒng)對學校課程建設、題庫建設都有著重要意義,通過無紙化考試系統(tǒng)數(shù)據(jù)的采集和功能設置,即可完成試卷組裝.在試卷自動組裝過程中,通常只考慮了知識點范圍,無法顧及試題的難易程度,因此組卷后,試卷總體難度系數(shù)無法準確把握.本文通過對無紙化考試系統(tǒng)數(shù)據(jù)倉庫進行分析,使用關聯(lián)規(guī)則的Apriori算法進行研究和改進,在挖掘中通過刪除無關集合突出高頻集合使挖掘中快速找出有價值數(shù)據(jù),使得組卷效率高,知識分布更科學,為高校教育與考試管理提供更好的服務.

1 數(shù)據(jù)挖掘技術

1.1 數(shù)據(jù)挖掘技術概述

數(shù)據(jù)挖掘是對數(shù)據(jù)倉庫中的海量數(shù)據(jù)進行數(shù)據(jù)提取、分類、轉(zhuǎn)換、分析和建模處理,提取出隱藏在數(shù)據(jù)中具有意義的信息和知識的過程.數(shù)據(jù)挖掘技術是當今數(shù)據(jù)庫領域研究中一個新興的領域,融合了數(shù)理統(tǒng)計、智能技術以及數(shù)據(jù)庫等多方面知識.數(shù)據(jù)挖掘的三個主要步驟分別為數(shù)據(jù)準備、數(shù)據(jù)挖掘、結(jié)果表達與解釋[1].數(shù)據(jù)準備可利用高性能的T-SQL語句在數(shù)據(jù)源中把需要挖掘的數(shù)據(jù)抽出形成新的數(shù)據(jù)集,系統(tǒng)對已提取的數(shù)據(jù)進行二次分析,如檢查重復數(shù)據(jù)、拼寫錯誤、補齊數(shù)據(jù)等等,最終形成符合數(shù)據(jù)挖掘需求的模式;數(shù)據(jù)挖掘的一個重要過程就是在數(shù)據(jù)庫中發(fā)現(xiàn)有價值的信息,通過定義業(yè)務問題,使用一種挖掘算法進行數(shù)據(jù)處理的過程,最后對是否存在冗余或者存在無關信息等進行評估,數(shù)據(jù)挖掘結(jié)果最終使用的是客戶,因此還要把結(jié)果轉(zhuǎn)化為客戶易懂方式.

1.2 Apriori算法

Apriori算法是一種數(shù)據(jù)挖掘關聯(lián)規(guī)則[2]中的典型算法.該算法通過多次迭代來統(tǒng)計數(shù)據(jù)庫中的頻繁項集,通過頻繁項集產(chǎn)生強關聯(lián)規(guī)則.在生成頻繁項集[3]時經(jīng)常會對數(shù)據(jù)倉庫進行頻繁迭代操作,尤其在低維度頻繁項集到高緯度項集時,會因頻繁項集的維數(shù)高導致笛卡爾積后生成許多候選項集,導致查找效率低下.針對以上提出的問題,筆者對Apriori算法進行改進,最后將新的算法在無紙化考試系統(tǒng)中使用.

2 組卷方法

2.1 組卷策略

自動組卷功能是無紙化考試系統(tǒng)的核心功能,通過自動組卷程序要求系統(tǒng)生成科學性、隨機性的試題.傳統(tǒng)無紙化考試系統(tǒng)的組卷方式有以下兩種,一是專業(yè)教師在系統(tǒng)后臺選擇相應科目的考試題型,根據(jù)考試范圍選擇相應的考試題目組成試卷,這種方式組卷對機器的壓力比較小,但每位學生試卷題目都一樣,學生作弊的可能性也比較大;另一種方式是考試時對題庫試題進行自動抽取,通過事先設置的難易系數(shù)隨機生成試卷,這種方式每個學生所做的試題可能都不一樣,難以作弊,但對機器的負荷比較大.

每個學校無紙化考試系統(tǒng)的自動組卷形式都不一樣,無論用哪種辦法,最主要是如何研究出更科學、更高效的自動組卷方式.

2.2 Apriori在組卷中的應用

為了使試題在自動組卷中能夠讓知識點分布更加均衡、更加科學,筆者采用關聯(lián)規(guī)則中的Apriori算法對考試系統(tǒng)數(shù)據(jù)倉庫進行挖掘.首先在數(shù)據(jù)倉庫中可把優(yōu)等生都不得分和差等生都得分的題目放在頻繁項集里,無紙化系統(tǒng)自動組卷之后把頻繁項集作為一個評價標準,如頻繁項集越多則該份試卷越差.挖掘工作中利用N-項集來生成(N+1)-項集,產(chǎn)生候選項集CN后,利用CN找頻繁項集LN,以此類推直至找出所有的頻繁項集[4],APRIORI常用算法如下:

(1)設置相應的最小支持度閾值Minimum_Threshold

(2)找出數(shù)據(jù)集中的高頻集L1=FIND_FREQUENT_1-ITEMSETS(D)

(3)循環(huán)處理L-項目集對應的鏈表,并獲得最大頻繁項目集

FOR(N=2;LN-1≠Φ;N++)

{ CN=APRIORI_GEN(LN-1,Minimum_Threshold);

(4)FOR_EACH TRANSACTION Y∈D

CY=SUBSET(CN,Y);

FOR_EACH CANDIDATE c∈CY

c.COUNT++;}

(5)KN={c∈CN| c.COUNT＞=Minimum_Threshold}

}

(6)RETURN L=∪NLN;

2.3 Apriori算法改進

通過對Apriori算法進行研究比較,發(fā)現(xiàn)在CN候選項集查找頻繁項集LN時,候選項集需要對數(shù)據(jù)庫掃描N次,數(shù)據(jù)庫越大掃描所用的時間也越大,機器所承受的壓力也越大,顯然隨著無紙化系統(tǒng)數(shù)據(jù)的增加,該算法所表現(xiàn)出來的工作效率就越來越低.要解決以上問題的方法有兩種,一是縮小需要掃描數(shù)據(jù)庫的規(guī)模,二是候選項集在查找頻繁項集LN時只掃描數(shù)據(jù)庫中的部分數(shù)據(jù).針對這些問題,筆者提出了Apriori算法改進.

系統(tǒng)后臺在輸入題庫時,可根據(jù)試題基本信息對試題的難易系數(shù)進行初步評價,如把試題評價成一級、二級、三級,其中三級試題最難,那么搜索與優(yōu)等生相關的頻繁項集時只要在三級試題的數(shù)據(jù)庫中搜索,搜索與差等生相關的頻繁項集時只要在一級試題的數(shù)據(jù)庫中搜索,這樣就大大縮小搜索范圍.另外,在生成頻繁項集過程中,如果某項事務不包含N-項集,那么該事務也不可能包含任何頻繁(N+1)-項集[5],把這樣的事務找出來并刪除即可縮小數(shù)據(jù)倉庫大小.經(jīng)過挖掘可以得知學生對知識點的掌握程度以及對試題的初步評價重新進行評價調(diào)整,這對教學質(zhì)量把控以及質(zhì)量評估有著重要意義.經(jīng)過以上分析,文章對Apriori算法提出了改進設計,改進后的算法如下:

(1)設置相應的最小支持度閾值Minimum_Threshold

(2)在數(shù)據(jù)集DATASET中找出高頻集N1=FIND_ONE_ITEM(DATASET);

(3)FOR(N=2;LN-1≠Φ;N++)

{CN=APRIORI_GEN(LN-1,Minimum_Threshold);

(4)FOR_EACH TRANSACTION Y∈D{

(5)FOR each(N-1)-SUBSET S OF C{

IF s?LN-1Then

Delete Y;

}

(6)IF(|Y|＜N)THEN{

delete Y; }

CY=SUBSET(CK,Y);

}

(7)FOR_EACH CANDIDATE c∈MY

(8)m.Count+=GETSCORE(c,Y);

}

(9) NX={m∈MX| m.COUNT＞=Minimum_Threshold}

}

(10)RETURN N=∪XNX;

因任何頻繁項集的全部非空子集也是頻繁項集,非頻繁項集的超集也是非頻繁項集,同時支持頻繁項集LN的任意一個事物也至少支持LN-1中的N個N-1項集[6].經(jīng)過算法改進,當對數(shù)據(jù)倉庫進行挖掘時,先確定挖掘數(shù)據(jù)范圍和最小支持閾值,通過不斷刪除與生成頻繁項集條件不符合的事務,使數(shù)據(jù)挖掘在迭代過程中逐漸減少迭代規(guī)模,從而減少了系統(tǒng)的負載.通過GETSCORE函數(shù)來獲取數(shù)據(jù)的正確性并對高頻集合數(shù)據(jù)進行加權,對不同的試卷類型給予系數(shù)校對,最終通過系數(shù)權加值來判斷和獲取目標試卷.

為了測試算法工作情況,筆者對某學校的無紙化考試系統(tǒng)數(shù)據(jù)庫進行測試,測試工作在CPU為I3 3.4 GHz,內(nèi)存4 G的Windows 7操作系統(tǒng),配置了VC++和SQL2005的環(huán)境下進行,數(shù)據(jù)量共有6 600條數(shù)據(jù),把數(shù)據(jù)分別分為1 500,3 000,4 500,6 000,7 500,使用DBminer2工具合成數(shù)據(jù),設置事務平均長度為15,項集的平均長度為4,使用原來的Apriori算法和改進后的Apriori算法對數(shù)據(jù)進行測試,發(fā)現(xiàn)隨著數(shù)據(jù)規(guī)模變大,改進后的算法執(zhí)行效率不會大幅度降低,幾乎呈線性增長(見圖1).這體現(xiàn)了改進后的算法具有良好的穩(wěn)定性.

3 結(jié)束語

本文針對現(xiàn)有Apriori算法的瓶頸問題進行分析,通過減少事務、壓縮數(shù)據(jù)、縮減比較和迭代次數(shù)的方法從而增加了算法的運行效率.本文提出的算法除了使用在無紙化考試系統(tǒng)的組卷,還可以使用在對學生成績進行分析和統(tǒng)計等其他方面.數(shù)據(jù)挖掘是一個新興學科,通過多年的研究,目前也已經(jīng)運用在各個領域.筆者的研究結(jié)論可以促進高校傳統(tǒng)教學方法的改革,可以更科學地指導教學.

圖1 Apriori算法改進前后效率對比圖

參考文獻:

[1]李亮.視頻點播系統(tǒng)中的數(shù)據(jù)挖掘技術應用[D].江蘇:揚州大學,2009.

[2]王月行,馬垣,胡志宇.基于概念格的關聯(lián)規(guī)則挖掘方法[J].計算機工程與設計,2009,30(22):5062-5064.

[3]張文靜,馬冬來,么煒.基于改進Apriori算法的決策推導過程[J].河北農(nóng)業(yè)大學學報,2013,36(2):122-124.

[4]徐嘉莉,石琳,付平.改進的Apriori算法在基于J2EE架構的網(wǎng)絡考試系統(tǒng)中的應用[J].成都大學學報:自然科學版,2007,26(03):254-256.

[5]劉興濤,石冰,解英文.挖掘關聯(lián)規(guī)則中Apriori算法的一種改進[J].山東大學學報:理學版,2008,43(11):67-71.

[6]陳安娜.Apriori優(yōu)化算法在臨床數(shù)據(jù)挖掘中的應用分析[J].長春師范學院學報,2013,32(02):45-48.