【正文】 量單位，而分?jǐn)?shù)的初始點(diǎn)、終點(diǎn)及平均分相差懸殊情況下的學(xué)生比較，其計(jì)算公式如下式: 事務(wù)分割因?yàn)閺目荚嚪?wù)器中得到的是學(xué)生答卷的所有情況，所以第一步總是分割算法。我用到的事務(wù)識(shí)別分割算法是最大答對(duì)題目算法，該算法能識(shí)別語(yǔ)義上有意義的事務(wù)。第一步: 數(shù)據(jù)獲取:考試數(shù)據(jù)服務(wù)器上的考試資源包括了原始考試試卷、學(xué)生答卷等。在考試系統(tǒng)中，考試試卷和學(xué)生答卷采用流格式文件，網(wǎng)絡(luò)考試系統(tǒng)中的改卷模塊對(duì)流文件進(jìn)行格式轉(zhuǎn)換，并將考試及學(xué)生的相關(guān)信息、試卷和學(xué)生答卷的具體情況入庫(kù)。第二步: 事務(wù)識(shí)別:利用分割算法將學(xué)生答卷情況轉(zhuǎn)化為粒度較小的事務(wù)以方便后面使用數(shù)據(jù)挖掘算法進(jìn)行數(shù)據(jù)分析。從某個(gè)角度來(lái)講，考試資源挖掘?qū)嶋H上是協(xié)調(diào)教師對(duì)學(xué)生答卷模式的認(rèn)識(shí)和學(xué)生實(shí)際答卷模式的過(guò)程。教師根據(jù)自己的教學(xué)情況將自己對(duì)學(xué)生答題情況的認(rèn)知表現(xiàn)在試卷的試題結(jié)構(gòu)上，而學(xué)生則通過(guò)答卷來(lái)反映其知識(shí)點(diǎn)的掌握情況。所以考試資源挖掘至少要包含兩個(gè)輸入:教師對(duì)于學(xué)生的認(rèn)知和學(xué)生實(shí)際考試的結(jié)果，這兩個(gè)輸入分別來(lái)自考試系統(tǒng)數(shù)據(jù)服務(wù)器上的考試資源，包括原始考試試卷、學(xué)生答卷等信息。(1) 教師認(rèn)知學(xué)生答卷模式教師認(rèn)知學(xué)生答卷模式指從教師的角度認(rèn)知學(xué)生的答卷情況，教師認(rèn)知學(xué)生答卷模式是隱含在試卷的試題結(jié)構(gòu)中的，每種試題的類(lèi)型都表現(xiàn)了一定的本質(zhì)特性，對(duì)學(xué)生測(cè)試的側(cè)重點(diǎn)、知識(shí)點(diǎn)、考點(diǎn)均有所反映，代表了教師出題的觀點(diǎn)。教師在出題過(guò)程中對(duì)題目類(lèi)型、知識(shí)點(diǎn)、章節(jié)、難度等參數(shù)的選取就體現(xiàn)了對(duì)學(xué)生答卷模式的認(rèn)知。因此，從考試試卷的試題結(jié)構(gòu)就可以確立教師認(rèn)知學(xué)生答卷模式。(2) 學(xué)生實(shí)際答卷模式為了發(fā)現(xiàn)學(xué)生實(shí)際答卷模式，需要將考試資源中學(xué)生信息組成有意義的事務(wù)。學(xué)生實(shí)際答卷模式是關(guān)于學(xué)生在考試系統(tǒng)中答卷的模式，它通過(guò)考試系統(tǒng)實(shí)現(xiàn)學(xué)生的網(wǎng)上答題、試卷的自動(dòng)評(píng)判，以及將詳細(xì)的信息入庫(kù)，并根據(jù)相關(guān)的特征找出其答卷模式來(lái)。在教師認(rèn)知學(xué)生答卷模式中不同類(lèi)型的試題具有公共特征。類(lèi)似地，不同的學(xué)生答卷的情況也具有相似的特征，他們的共同點(diǎn)是都答對(duì)了{(lán)1, 2, 5, 8}題。 不同學(xué)生答卷情況舉例 課程代號(hào) 試卷代號(hào) 試卷名稱(chēng) 學(xué)生考號(hào) 答對(duì)題目題號(hào)0001 ceshi0001 0001 200467001 1,2,4,5,7,8,1,00001 ceshi0001 0001 200467002 1,2,3,5,6,8,9 (3) 一般模型事務(wù)識(shí)別的目的是為每個(gè)學(xué)生建立有意義的試題、試卷組合，所以事務(wù)識(shí)別的任務(wù)就是將一個(gè)大的事務(wù)分成多個(gè)小的事務(wù)，或者將多個(gè)小的事務(wù)合并為少數(shù)的大事務(wù)，因此事務(wù)識(shí)別的方法主要有分割和合并兩種。這兩種方法的輸入都是事務(wù)列表和一些參數(shù)，輸出是新的事務(wù)列表，同樣這些輸出又可以作為挖掘算法中某個(gè)函數(shù)的輸入。輸入和輸出事務(wù)的格式一致，允許將算法以任何順序相結(jié)合。設(shè)L是學(xué)生答卷情況中的項(xiàng)的集合，一個(gè)答卷情況項(xiàng)KIEL)包含學(xué)生代號(hào)、試題題號(hào)、課程代號(hào)、試卷代號(hào)、考場(chǎng)代號(hào)、得分，分別記為1. ExamID,1. CourseID,1. PaperID,① StudentID, LID. 1. Score。學(xué)生答卷情況中還有其它的字段，但是在此事務(wù)模型中不需要。② 事務(wù)分割方法最大答對(duì)題目方法是基于Chen等人最大向前引用的工作，最大答對(duì)題目是在學(xué)生答題信息中找出所有學(xué)生答對(duì)題目的最大題目集合。在使用最大答對(duì)題目算法之前，對(duì)學(xué)生的答卷信息進(jìn)行了一些處理，以學(xué)生答卷信息表為基本表提取出相關(guān)的指標(biāo)。最大答對(duì)題目算法中，作為事務(wù)分割算法輸入的是學(xué)生答卷情況，輸出的是包含了學(xué)生答題情況的事務(wù)數(shù)據(jù)庫(kù)，這個(gè)數(shù)據(jù)庫(kù)也是后面挖掘算法的輸入數(shù)據(jù)。 改進(jìn)的數(shù)據(jù)挖掘算法頻繁答對(duì)題目挖掘算法是借鑒DHP算法中使用Hash技術(shù)提高算法效率的思想，以經(jīng)典算法Apriori為基礎(chǔ)，尋找學(xué)生答對(duì)題目序列中頻繁答對(duì)題目集的方法。由于答對(duì)題目集中題目已根據(jù)在試卷中位置升序排列，所以在原有算法的基礎(chǔ)上只需簡(jiǎn)化修改便可應(yīng)用于題目序列的挖掘。下面詳細(xì)說(shuō)明頻繁答對(duì)題目算法中的改進(jìn)之處。 修改1: 在關(guān)聯(lián)規(guī)則挖掘中，只要有兩個(gè)k1維最大項(xiàng)集有k2個(gè)元素相同就可以合并成一個(gè)k維候選項(xiàng)。但在挖掘頻繁答對(duì)題目序列時(shí)，答對(duì)題目序列中的題目是有序的，因此不能簡(jiǎn)單地“有k2個(gè)元素相同”就行了，需要作如下的修改:Lk。中任意兩個(gè)不同的(k1)一答對(duì)題目集S1: S2: 39。.., Sk:和rh r2, , , rk_1，如果r1, r2, ***, rk_，包含Sl, s2,…，Sk，或者SI) S2)…，$k_，包含rl, r2,…，rkI 去掉第一元素，另一個(gè)去掉最后一個(gè)元素后完全相等。即這兩個(gè)(k1)一答對(duì)題目集中一個(gè)去則這兩個(gè)(ki)一答對(duì)題目集可以合并成一個(gè)k一答對(duì)題目集。修改2: Apriori算法利用apriori_gen函數(shù)產(chǎn)生新的候選項(xiàng)集。該函數(shù)有一個(gè)參數(shù)Lk_1,即所有頻繁(k1)項(xiàng)集的集合，返回所有頻繁k一項(xiàng)集的超集。第一步，對(duì)Lk_1自連接操作生成Ck；第二步，剪除，即對(duì)任意的C} CECk，刪除Ck中所有那些其(k1)一子集不在Lk，中的項(xiàng)集，得到候選項(xiàng)集Ck。在第一步將Lk，自連接生成Ck中，因?yàn)榇饘?duì)題目序列中是按順序排列的，所以若通過(guò)使用類(lèi)SQL語(yǔ)言的where條件，可以避免很多重復(fù)項(xiàng)的出現(xiàn)，減少C、的大小，從而提高了效率。修改3: Apriori算法中，函數(shù)apriori_gen在從Lk_:中求出所有的候選k一項(xiàng)集后還要進(jìn)行修剪，修剪的原則是:如果一個(gè)k一項(xiàng)集的某一個(gè)(k1)維子集不在Lk、中，則該k一項(xiàng)集就需要從Ck中刪除。例如Lk1= { 12, 231，則根據(jù)求候選項(xiàng)集的算法，Ck=1123}，然后進(jìn)行修剪，發(fā)現(xiàn)123的一個(gè)2維子集13不在Lk_i中，將123從C、中刪除。但是在挖掘頻繁k一答對(duì)題目集時(shí)，一個(gè)k一答對(duì)題目集ri, r2, .., r、只有兩個(gè)(k1)一子答對(duì)題目集ri, r2, .., rk_:和r2, ..., rk, rk，當(dāng)且僅當(dāng)這兩個(gè)(k1)一子答對(duì)題目集都在Lk_、時(shí)r, r2, *..r，才可能從Lk_。選出來(lái)，即凡是在c中存在的k一項(xiàng)集，它的(k1)維子集一定在Lk_。中，因此在這里就沒(méi)有必要用修剪這一步驟。修改4:算法中關(guān)鍵的部分是在每個(gè)事務(wù)中尋找候選項(xiàng)集，為此引入了一種哈希樹(shù)結(jié)構(gòu)。候選項(xiàng)集Ck就存放在一棵哈希樹(shù)上。哈希樹(shù)的結(jié)點(diǎn)分為兩種:一種是葉結(jié)點(diǎn)，另一種是內(nèi)部結(jié)點(diǎn)。葉結(jié)點(diǎn)用于存放項(xiàng)集，當(dāng)增加一個(gè)項(xiàng)集c時(shí)，從根結(jié)點(diǎn)開(kāi)始沿樹(shù)向下搜索直到到達(dá)一個(gè)葉結(jié)點(diǎn)。內(nèi)部結(jié)點(diǎn)存放哈希表。在一個(gè)內(nèi)部結(jié)點(diǎn)中，哈希表的每一個(gè)哈希單元都指向另外一個(gè)結(jié)點(diǎn)。哈希樹(shù)的根結(jié)點(diǎn)的深度定義為1，深度為d的內(nèi)部結(jié)點(diǎn)指向深度為d+l的結(jié)點(diǎn)。在深度為d的內(nèi)部結(jié)點(diǎn)，對(duì)項(xiàng)集的第d個(gè)項(xiàng)施以哈希函數(shù)以決定走哪條樹(shù)枝。所有的結(jié)點(diǎn)創(chuàng)建時(shí)都初始化為葉結(jié)點(diǎn)。 Subset函數(shù)的參數(shù)是候選項(xiàng)集C，和某一事務(wù)t，結(jié)果返回這一事務(wù)t中包含的候選項(xiàng)集。它的作用是找到包含在事務(wù)t中所有的候選項(xiàng)集。流程如下:對(duì)Ck中任意項(xiàng)集c，從根結(jié)點(diǎn)開(kāi)始，對(duì)c中的每個(gè)項(xiàng)進(jìn)行Hash，如果是在一個(gè)葉結(jié)點(diǎn)上，就尋找該葉結(jié)點(diǎn)中哪(幾)個(gè)項(xiàng)集被包含在t中，并將他們的引用添加到引用集。若是通過(guò)Hash項(xiàng)i到達(dá)一個(gè)內(nèi)部結(jié)點(diǎn)，就對(duì)t中位于i之后的每一個(gè)項(xiàng)目進(jìn)行Hash。反復(fù)地給相應(yīng)的Hash單元中的結(jié)點(diǎn)運(yùn)用此過(guò)程。對(duì)于事務(wù)t中的任何項(xiàng)集c, c中的第一個(gè)項(xiàng)一定在t中。在根結(jié)點(diǎn)，通過(guò)哈希t中的每個(gè)項(xiàng)，可以保證僅僅忽視那些己不在t中的項(xiàng)開(kāi)頭的項(xiàng)集。深度較低的結(jié)點(diǎn)處情況類(lèi)似。唯一額外的因素是，因?yàn)轫?xiàng)集匯總的項(xiàng)是按順序排列的，如果通過(guò)Hash項(xiàng)i到達(dá)當(dāng)前結(jié)點(diǎn)，僅需要考慮t中i之后出現(xiàn)的項(xiàng)。改進(jìn)的算法、子程序及函數(shù)描述如下://Partl。得到頻繁1一項(xiàng)集，為2一項(xiàng)集構(gòu)造一張哈希表s=a minimum support。set all the buckets of H2 to zero。//Hash tableforall transaction t E D do begin insert and count 1一items occurrences in a Hash tree。 forall 2subsets x of t do H2 [h2(x)〕=H2 [h2 (x)」+1。 end。L,={, c exists in the leaf node of the Hash tree)//Part2。確定大數(shù)據(jù)項(xiàng)集合large kitemsets//基于先前掃描過(guò)程中生成的哈希表(Hk)產(chǎn)生候選項(xiàng)集Ck，確定頻繁k一項(xiàng)集Lk,//減少數(shù)據(jù)庫(kù)的大小，并且給候選頻繁(k+1)一項(xiàng)集構(gòu)造一張哈希表k=2。Dk=D。while(一{x一Hk [x] , s}})LARGE) do//建立哈希表 gen_candidate (Lk_l, Hk, Ck)。//基于Hash表Hk產(chǎn)生侯選項(xiàng)集Ckset all the buckets of Hk+l to zero。 count_ support (t, Ck, k, t)。//t if(}t{k) then do begin maketo Hasht(t，Hk, k, HktI, t )。//建立(k+l)itemsets哈希表 if()t}k) then Dk+,=Dk+, U {t}。 end。 end。k十十。//Part3基本同part2，只是不再使用Hash技術(shù)gen_ candidate (Lk_, Hk, q)。while(}Ck}0) do beginDk+l=o。count_ support (t, Ck, k, t)。if(}t}k) then Dk+,=Dk+I U {t}end。if(}Dk+1{=0) then break。if (c. counts)then//根據(jù)哈希表中的計(jì)數(shù)器生成位矢量c. bit_ vector=l。//計(jì)數(shù)器的值不小于最小支持度s，則位失量為1else c. bit_ vector=0。if (c. bit_ vector=1)//否則置為0thenCk*,=apriori_gen (Lk) 。//與Apriori算法相同之處K=k十1。//以下是三個(gè)主要的子程序:Procedure gen_ candidate (Lk,1, K, q)//生成候選項(xiàng)集，并插入HashCk= 0。forall c=cP[1]，... C, [k2] c, [k1，CPI c, E Lk1, 1 c, n c,}=k2 do if then C,C, U。/八nsert c into a Hash treeend Procedure//Procedure count_ support (t, Ck, k, t)//計(jì)算支持度，某個(gè)k一項(xiàng)集既是//事務(wù)t的子集，又是C中的元素，該項(xiàng)集的支持度會(huì)加1 j=0。//a[i]用來(lái)記錄事務(wù)t的第i項(xiàng)的出現(xiàn)頻率 forall j=k do begin//當(dāng)包含該第i個(gè)項(xiàng)的k一子集是C、中的元素時(shí) a[i。]=a[i]+l 。//根據(jù)每個(gè)項(xiàng)在k一子集中的索引給a[i]增加1 j=j+1。 end。 i=0。 j=0。 forall i一t一do begin if (a[i] }:k) then do begin//所有的候選項(xiàng)集處理完后判斷每個(gè) t。=t。// a[i]的大小，若a[ilk，則修剪掉事務(wù)中的第i個(gè)項(xiàng) j二j+1。 end。 i=i+l。 end。end Procedure//Procedure make Hasht(i，14, k, H4+1, t)//生成Hash表，要將事務(wù)t的一個(gè)(k+l)一子集哈希到哈希表中，//需要檢測(cè)這個(gè)(k+1)一子集的所有k一子集在H、中相應(yīng)哈希單元的值。focal l (k+0subsets x (=t 。1t 。k) oft do//檢測(cè)后加入Hash表，if (focal l ksubsets y of x, Hk [hk (y)〕)s) then do beginHk+, [h，十，(x)」=R+1 [hk+l (x)]+1。//Hash過(guò)濾 j=1。 forall k+l do begin a[i。]=a[i。]+1。 j二j+1。 end。 end。i=0。j=0。forall iIt一do begin if (a[i]0) then do beginend。end Procedure//Apriori_gen函數(shù):第一步，對(duì)Lk_1自連接(Join)操作生成Ckinsert into Ckselect p. item, p. item2, p. itemk_l, q. itemk_,from Lk_,p,qwherep. item,=q. item, ..p. itemk_,=q. itemk 2, p. itemkq. itemk_,，c. bit ve