黃宏濤 梁存良 李大鵬 葉海智

人工智能和認(rèn)知科學(xué)等領(lǐng)域的研究成果[1?3]正在不斷促進(jìn)教學(xué)方式向更加智能、高效和個(gè)性化的方向發(fā)展[4?6].個(gè)性化教學(xué)的核心問(wèn)題是通過(guò)計(jì)算機(jī)程序?qū)Ρ辉嚨闹R(shí)結(jié)構(gòu)[7]和能力水平進(jìn)行測(cè)試,并根據(jù)測(cè)試結(jié)果開(kāi)展資源推送和學(xué)習(xí)路徑規(guī)劃等計(jì)算機(jī)輔助教學(xué)活動(dòng).Tatsuoka[8]提出的規(guī)則空間模型(Rule space model,RSM)是對(duì)學(xué)生知識(shí)狀態(tài)進(jìn)行認(rèn)知診斷的有效方法之一.RSM 的主要特點(diǎn)是假設(shè)學(xué)生在解題過(guò)程中的錯(cuò)誤反應(yīng)是不確定的(可變的).因此,RSM 能夠有效處理學(xué)生作答過(guò)程中的可變性,更為準(zhǔn)確地把學(xué)生實(shí)際反應(yīng)模式轉(zhuǎn)換為認(rèn)知過(guò)程與技能的掌握概率,從而實(shí)現(xiàn)對(duì)被試認(rèn)知結(jié)構(gòu)的診斷[9].

RSM 在智能導(dǎo)師系統(tǒng)[10?12]和個(gè)性化學(xué)習(xí)系統(tǒng)[13?15]等領(lǐng)域中有著成功的應(yīng)用.Im 等[16]使用RSM 對(duì)學(xué)生的統(tǒng)計(jì)假設(shè)檢驗(yàn)知識(shí)和技能進(jìn)行了診斷,并能夠根據(jù)診斷結(jié)果對(duì)學(xué)生進(jìn)行教學(xué)指導(dǎo).這種方法同樣適用于在線教學(xué)或計(jì)算機(jī)輔助學(xué)習(xí).Xin等[17]使用RSM 對(duì)單一分?jǐn)?shù)在三個(gè)認(rèn)知屬性上進(jìn)行分類(lèi),并對(duì)教師水平和學(xué)生認(rèn)知技能間的關(guān)系進(jìn)行分析.Badaracco 等[18]在計(jì)算機(jī)自適應(yīng)診斷(Computerized adaptive test,CAT)中引入模糊語(yǔ)言建模的專(zhuān)家知識(shí)用于支持測(cè)試項(xiàng)目選擇,提高了RSM診斷結(jié)果的準(zhǔn)確性.Qin 等[19]提出對(duì)Q 矩陣的推理和有效性檢驗(yàn)的改進(jìn)算法,能夠產(chǎn)生更合理的Q矩陣規(guī)范,進(jìn)一步改善了RSM 診斷結(jié)果的有效性.

這些基于RSM 的方法雖然能夠?qū)Ρ辉囌J(rèn)知結(jié)構(gòu)進(jìn)行有效、準(zhǔn)確的診斷,但規(guī)則空間構(gòu)造需要全局知識(shí)依賴關(guān)系的支持,導(dǎo)致時(shí)間代價(jià)較高,不適合用于日常教學(xué)中對(duì)學(xué)生進(jìn)行小規(guī)模的單元診斷.而這種小規(guī)模的實(shí)時(shí)診斷是智能導(dǎo)師系統(tǒng)和個(gè)性化學(xué)習(xí)系統(tǒng)進(jìn)行知識(shí)結(jié)構(gòu)推理的關(guān)鍵環(huán)節(jié).為了提高RSM 的靈活性和可擴(kuò)展性,文獻(xiàn)[20?21]提出了一種使用BP 神經(jīng)網(wǎng)絡(luò)進(jìn)行認(rèn)知診斷建模的方法,使用期望反應(yīng)模式對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練,然后使用訓(xùn)練后的神經(jīng)網(wǎng)絡(luò)對(duì)被試觀察反應(yīng)模式進(jìn)行識(shí)別,克服了RSM 模型進(jìn)行參數(shù)估計(jì)時(shí)對(duì)大樣本數(shù)據(jù)的依賴,使基于RSM 的計(jì)算機(jī)自適應(yīng)測(cè)驗(yàn)應(yīng)用于課堂教學(xué)成為可能.然而,在小規(guī)模測(cè)試的前提下,屬性層級(jí)關(guān)系約束下的測(cè)試項(xiàng)目數(shù)量有限,基于神經(jīng)網(wǎng)絡(luò)的RSM 能夠使用的期望反應(yīng)模式規(guī)模也較小,無(wú)法保障總是獲得理想的訓(xùn)練誤差.

此外,基于神經(jīng)網(wǎng)絡(luò)的RSM 雖然能夠在一定程度上降低規(guī)則空間構(gòu)造代價(jià),但它沒(méi)有考慮領(lǐng)域內(nèi)所有知識(shí)之間的全局依賴關(guān)系.而在實(shí)際教學(xué)活動(dòng)中,領(lǐng)域內(nèi)知識(shí)間的依賴關(guān)系是客觀存在的,使用依賴保持子圖(Dependency preserving subgraph,DPS)[22]構(gòu)造規(guī)則空間的方式能夠在認(rèn)知診斷活動(dòng)涉及的測(cè)試項(xiàng)目確定后,根據(jù)領(lǐng)域知識(shí)圖中的依賴關(guān)系生成知識(shí)圖的相關(guān)子圖,再由子圖出發(fā)構(gòu)造規(guī)則空間,這種方法可以顯著降低規(guī)則空間規(guī)模以及預(yù)設(shè)知識(shí)圖時(shí)的人工參與度.但是,當(dāng)領(lǐng)域知識(shí)圖中依賴關(guān)系較為復(fù)雜時(shí),DPS 生成相關(guān)子圖的過(guò)程中會(huì)引入較多和測(cè)試項(xiàng)目無(wú)關(guān)的屬性,容易導(dǎo)致相關(guān)子圖規(guī)模過(guò)大.相對(duì)于DPS 方法,使用頂點(diǎn)導(dǎo)出子圖(Vertex derived subgraph,VDS)[23]構(gòu)造規(guī)則空間時(shí)不會(huì)引入與測(cè)試項(xiàng)目無(wú)關(guān)的屬性.這種特性能夠保證總是獲得規(guī)模足夠小的規(guī)則空間,從而提高RSM 的可擴(kuò)展性,但其代價(jià)是損失了部分領(lǐng)域知識(shí)圖中的傳遞依賴關(guān)系,會(huì)導(dǎo)致理想屬性模式集中大量不合理屬性模式無(wú)法被過(guò)濾,從而影響認(rèn)知診斷的效率和診斷結(jié)果的準(zhǔn)確率.

為了在保障診斷結(jié)果準(zhǔn)確率的前提下盡可能提高RSM 方法的可擴(kuò)展性,使其能夠適用于小規(guī)模的、及時(shí)的課堂教學(xué)認(rèn)知診斷,本文提出一種基于近似子圖的RSM 規(guī)則空間生成方法.該方法借鑒了文獻(xiàn)[24]中通過(guò)構(gòu)建守恒依賴圖計(jì)算質(zhì)量守恒集的方法,在守恒依賴圖構(gòu)建過(guò)程中忽略了狀態(tài)空間中的反應(yīng)狀態(tài),有效縮減了待檢查候選集的數(shù)量,達(dá)到了提高守恒集計(jì)算效率的目的;同時(shí)通過(guò)抽取反應(yīng)狀態(tài)和已連接組件間的依賴關(guān)系,保持了守恒狀態(tài)間的依賴關(guān)系.受文獻(xiàn)[24]的啟發(fā),本文通過(guò)構(gòu)建近似子圖實(shí)現(xiàn)對(duì)規(guī)則空間的壓縮,近似子圖的構(gòu)建不需要根據(jù)測(cè)試項(xiàng)目涉及的屬性集合從領(lǐng)域知識(shí)圖中計(jì)算先序依賴關(guān)系的傳遞子圖,而是通過(guò)忽略先序依賴關(guān)系中與測(cè)試項(xiàng)目無(wú)關(guān)的屬性來(lái)生成領(lǐng)域知識(shí)圖的近似子圖.生成的近似子圖能夠通過(guò)構(gòu)建虛擬邊模擬領(lǐng)域知識(shí)圖上的依賴關(guān)系,從而在不影響生成補(bǔ)救教學(xué)路徑的前提下顯著降低規(guī)則空間規(guī)模量級(jí),進(jìn)而提高RSM 的可擴(kuò)展性.

1 相關(guān)概念

在介紹近似子圖生成算法前先給出屬性、領(lǐng)域知識(shí)圖、初始路徑、路徑片段和劃分標(biāo)準(zhǔn)的概念.

屬性是對(duì)程序性知識(shí)或陳述性知識(shí)的描述,是構(gòu)成認(rèn)知結(jié)構(gòu)的基本元素,直接反映了被試的認(rèn)知技能.屬性及其內(nèi)部依賴關(guān)系是構(gòu)成規(guī)則空間的基礎(chǔ).本文使用領(lǐng)域知識(shí)圖[25]表示屬性及其聯(lián)系.

定義1.四元組G=(V,E,I)為一個(gè)領(lǐng)域知識(shí)圖,其中

1)頂點(diǎn)集合V是屬性的有限非空集合;

2)E ?V×V為邊的有限集合,(v1,v2)∈E表示知識(shí)點(diǎn)v2依賴于v1,其中v1∈V,v2∈V;

3)I ?V為初始狀態(tài)集合,對(duì)任意vi ∈V,vi∈I當(dāng)且僅當(dāng)不存在vj ∈V使得(vj,vi)∈E,ij.

頂點(diǎn)集合V為規(guī)則空間模型中的屬性集合,邊集E是定義在屬性集上的二元關(guān)系,反映了屬性間的先序依賴關(guān)系.因此,E是定義在V上的偏序關(guān)系,即E是自反、反對(duì)稱和傳遞的.在忽略自環(huán)的情況下可知G為有向無(wú)環(huán)圖(Directed acyclic graph,DAG).

定義2.稱領(lǐng)域知識(shí)圖G上的頂點(diǎn)序列p=v1v2···vn為連接v1和vn的路徑,當(dāng)且僅當(dāng)對(duì)任意vi和vi+1存在(vi,vi+1)∈E,其中,1≤i

路徑是先序依賴關(guān)系下的屬性序列,是合理的認(rèn)知技能學(xué)習(xí)序列.在圖1 所示的領(lǐng)域知識(shí)圖G中,頂點(diǎn)序列“角、三角形、三角形底”是連接“角”和“三角形底”的路徑,它說(shuō)明如果屬性“三角形底”已經(jīng)被掌握,則屬性“三角形”必然已經(jīng)被掌握;同理,屬性“角”也已經(jīng)被掌握.而頂點(diǎn)序列“相交線、角、三角形、三角形底”是初始路徑,它是可行的認(rèn)知技能序列,是理想屬性模式的構(gòu)成元素.

圖1 領(lǐng)域知識(shí)圖GFig.1 Domain knowledge graph

定理1.對(duì)于領(lǐng)域知識(shí)圖G=(V,E,I)上的任意點(diǎn)v,G上存在初始路徑p使得p經(jīng)過(guò)v.

證明.如果v不依賴于任何頂點(diǎn),由定義1 知v ∈I,于是由定義2 可得p=v為初始路徑;否則G上存在頂點(diǎn)v1使得v依賴于v1,則p=v1v為經(jīng)過(guò)v的路徑,如果v1不依賴于任何頂點(diǎn),同理可得p=v1v為初始路徑;否則G上存在頂點(diǎn)v2使得v1依賴于v2,此時(shí),如果v2不依賴于任何頂點(diǎn),則p=v2v1v為初始路徑.

進(jìn)行歸納可得,對(duì)于經(jīng)過(guò)v的路徑p=vn?1···v2v1v,當(dāng)n ?1=|V|?1 時(shí),如果vn?1不依賴于任何頂點(diǎn),則p=vn?1···v2v1v為初始路徑;否則必然存在頂點(diǎn)vn使得vn?1依賴于vn,此時(shí)p=vnvn?1···v2v1v的長(zhǎng)度大于|V|,這意味著路徑p上必然存在環(huán)路,這與G為DAG 圖矛盾.于是可得G上不存在頂點(diǎn)vn使得vn?1依賴于vn.

綜上所述,對(duì)于領(lǐng)域知識(shí)圖G上的任意點(diǎn)v,G上必然存在初始路徑p使得p經(jīng)過(guò)v且1≤|p|≤|V|.

定義3.va和vb為領(lǐng)域知識(shí)圖G上的兩個(gè)頂點(diǎn),如果G中存在頂點(diǎn)序列v0v1···vj,使得p=vav0v1···vjvb為G上的路徑,則G上存在從va到vb的路徑片段,此時(shí)va和vb是連通的,其中,a,b,j為自然數(shù).

頂點(diǎn)間的連通性反映了屬性間的先序依賴關(guān)系.為了從領(lǐng)域知識(shí)圖中選擇部分內(nèi)容開(kāi)展小規(guī)模測(cè)試,需要根據(jù)測(cè)試涉及的屬性及其依賴關(guān)系從領(lǐng)域知識(shí)圖中劃分出相關(guān)子圖,從而達(dá)到生成測(cè)試所需的小規(guī)模規(guī)則空間的目的.下面給出子圖劃分標(biāo)準(zhǔn)的定義.

定義4.Q為領(lǐng)域項(xiàng)目集合,Qsub?Q為測(cè)試項(xiàng)目集,對(duì)任意q ∈Qsub,k(q)?V表示項(xiàng)目q涉及的屬性集合,稱

為子圖劃分標(biāo)準(zhǔn),其中函數(shù)k的定義域?yàn)闇y(cè)試項(xiàng)目集Qsub,函數(shù)K的定義域?yàn)轭I(lǐng)域項(xiàng)目集Q的冪集,值域?yàn)轭I(lǐng)域知識(shí)圖頂點(diǎn)集V的冪集.

子圖劃分標(biāo)準(zhǔn)K(Qsub)直接決定了規(guī)則空間的規(guī)模.由于屬性模式依賴于屬性間的先序關(guān)系,所以在進(jìn)行小規(guī)模測(cè)試時(shí)需要從領(lǐng)域知識(shí)圖中抽取測(cè)試屬性集及其關(guān)系,也就是從子圖劃分標(biāo)準(zhǔn)出發(fā)計(jì)算領(lǐng)域知識(shí)圖的相關(guān)子圖.

2 基于近似子圖的規(guī)則空間生成算法

2.1 近似子圖生成

為了盡可能壓縮規(guī)則空間的規(guī)模,同時(shí)避免直接計(jì)算領(lǐng)域知識(shí)圖導(dǎo)出子圖出現(xiàn)孤立點(diǎn),本文通過(guò)計(jì)算領(lǐng)域知識(shí)圖的近似子圖生成規(guī)則空間.

定義5.Gsub=(Vsub,Esub,Isub)為G=(V,E,I)關(guān)于子圖劃分標(biāo)準(zhǔn)K(Qsub)的近似(Overapproximate)子圖,其中

1)Esub?E為近似子圖邊集合,(v1,v2)∈Esub當(dāng)且僅當(dāng)(v1,v2)∈E,其中v1∈K(Qsub),v2∈K(Qsub);

2)Vsub為頂點(diǎn)集合,如果(v1,v2)∈Esub,則有v1∈Vsub,v2∈Vsub;

3)對(duì)任意vi ∈K(Qsub),如果?vj ∈K(Qsub)使得G上存在從vi到vj(或vj到vi)的路徑片段,并且vi到vj(或vj到vi)的路徑片段上除vi和vj以外不存在其他頂點(diǎn)屬于K(Qsub),則(vi,vj)∈Esub或(vj,vi)∈Esub,其中vi和vj不同;

4)有限次應(yīng)用2)和3),直至Vsub和Esub不再變化;

5)Isub?Vsub為初始頂點(diǎn)集合,對(duì)任意vi ∈Vsub,vi ∈Isub,當(dāng)且僅當(dāng)不存在vj ∈Vsub,使得(vj,vi)∈Esub,ij.

上述定義給出了近似子圖的最小不動(dòng)點(diǎn)求解方法.下面以圖1 所示的領(lǐng)域知識(shí)圖G為例介紹近似子圖計(jì)算過(guò)程.如果測(cè)試項(xiàng)目集Qsub共有5 個(gè)項(xiàng)目,這些項(xiàng)目及其對(duì)應(yīng)的屬性集合如表1 所示.

圖2 G 關(guān)于K(Qsub)的近似子圖Fig.2 The approximate subgraph of G on division criteria K(Qsub)

表1 測(cè)試項(xiàng)目及其對(duì)應(yīng)的屬性Table 1 Test item and its attributes

根據(jù)定義4,子圖劃分標(biāo)準(zhǔn)K(Qsub)={相交線,三角形,三角形高,三角形面積}.由定義5 條件1)得,邊(三角形,三角形高)、(三角形高,三角形面積)屬于Esub,如圖2(a)所示;由條件2)可知,頂點(diǎn)“三角形”、“三角形高”、“三角形面積”屬于Vsub,如圖2(b)所示;由于G上存在由頂點(diǎn)“相交線”到頂點(diǎn)“三角形高”、由頂點(diǎn)“相交線”到頂點(diǎn)“三角形”以及由頂點(diǎn)“三角形”到頂點(diǎn)“三角形面積”的路徑片段,故根據(jù)條件3)可得,邊(相交線,三角形高)、(相交線,三角形)、(三角形,三角形面積)屬于Esub,雖然也存在“相交線”到“三角形面積”的路徑片段,但這條路徑需要經(jīng)過(guò)“三角形”或“三角形高”,不符合條件3)的要求,因此忽略該近似邊,圖2(c)給出了添加近似邊后的結(jié)果;再次應(yīng)用條件2)可得,Vsub={相交線,三角形,三角形高,三角形面積},如圖2(d)所示;再次應(yīng)用條件3)時(shí),(K(Qsub)?Vsub)=?,所以Esub不再變化,近似子圖求解結(jié)束,最后由條件5)可得,初始狀態(tài)集合Isub={相交線}.于是可得G=(V,E,I)關(guān)于子圖劃分標(biāo)準(zhǔn)K(Qsub)的近似子圖Gsub=(Vsub,Esub,Isub),如圖2(d)所示.

Gsub對(duì)應(yīng)于規(guī)則空間模型的鄰接矩陣,由鄰接矩陣可計(jì)算出可達(dá)矩陣.可達(dá)矩陣反映了屬性間的間接依賴關(guān)系,即Gsub上頂點(diǎn)間的可達(dá)關(guān)系.本文通過(guò)對(duì)近似子圖Gsub進(jìn)行可達(dá)性分析,計(jì)算鄰接矩陣的可達(dá)矩陣,其時(shí)間復(fù)雜度為O(ne),其中,n=|Vsub|,e=|Esub|.

2.2 期望反應(yīng)模式構(gòu)建

構(gòu)建規(guī)則空間的目的是通過(guò)模式匹配建立觀察反應(yīng)模式與期望反應(yīng)模式之間的映射,進(jìn)而通過(guò)期望反應(yīng)模式確定理想屬性模式.因此,構(gòu)建規(guī)則空間需要由近似子圖確定理想屬性模式、期望反應(yīng)模式及兩者間的關(guān)系.

屬性模式是一組認(rèn)知技能的集合,即知識(shí)狀態(tài).為了對(duì)被試的認(rèn)識(shí)結(jié)構(gòu)進(jìn)行分類(lèi),需要由Gsub的頂點(diǎn)集Vsub生成對(duì)應(yīng)的屬性模式.理論上屬性模式集合是屬性集合的冪集.下面給出屬性模式[3]的形式定義.

定義6.屬性模式是一個(gè)有序n元布爾序列m=b1b2···bn,其中n=|Vsub|,bi為布爾值,表示對(duì)應(yīng)屬性是否被掌握,bi為1 表示屬性i成立,0 表示不成立,1≤i≤n.

圖2 所示實(shí)例中,Vsub包含“相交線,三角形,三角形高,三角形面積”4 個(gè)屬性,可能的屬性模式有16 種.考慮到屬性之間的偏序關(guān)系,這16 種可能屬性模式中有一部分是不合理的,例如屬性模式(0100),它反映了被試掌握了屬性“三角形”卻未掌握屬性“相交線”,這種知識(shí)狀態(tài)是不可接受的.而屬性模式(1100)是合理的,它反映了被試同時(shí)掌握了屬性“相交線”和屬性“三角形”.這種合理的屬性模式為理想屬性模式[5],它是可行的認(rèn)知技能序列.

定義7.令M為理想屬性模式集合,L:M →為標(biāo)記函數(shù),任意m ∈M為理想屬性模式當(dāng)且僅當(dāng)

成立,其中pi為Gsub上的初始路徑,Γ(pi)表示pi上所有屬性的集合,n≥1.

上述定義給出了判斷一個(gè)屬性模式是否合理的標(biāo)準(zhǔn),根據(jù)定義7 可得Gsub生成的理想屬性模式集合M={0000,1000,1100,1010,1110,1111}.表2給出了理想屬性模式及其標(biāo)記的對(duì)應(yīng)關(guān)系.

表2 由Qsub生成的理想屬性模式Table 2 Ideal attribute pattern generated by Qsub

表2 列出的屬性模式反映了被試的潛在認(rèn)知結(jié)構(gòu).認(rèn)識(shí)診斷的最終目標(biāo)是建立觀察反應(yīng)模式和理想屬性模式之間的映射,從而產(chǎn)生對(duì)被試的認(rèn)知診斷.觀察反應(yīng)模式是指被試對(duì)測(cè)試項(xiàng)目的實(shí)際反應(yīng)結(jié)果,是在有噪音(存在失誤)情況下得出的測(cè)試結(jié)果序列.認(rèn)知診斷主要任務(wù)是在規(guī)則空間中對(duì)觀察反應(yīng)模式進(jìn)行模式識(shí)別,從而過(guò)濾噪音干擾并找出對(duì)應(yīng)的期望反應(yīng)模式(無(wú)噪音干擾下的反應(yīng)模式),最后由期望反應(yīng)模式獲取理想屬性模式映射,從而給出認(rèn)知診斷結(jié)果.因此,需要建立理想屬性模式與期望反應(yīng)模式間的對(duì)應(yīng)關(guān)系.下面給出期望反應(yīng)模式的定義.

定義8.對(duì)于給定測(cè)試項(xiàng)目集Qsub,稱n元布爾序列r=R(m)=B(q1|m)B(q2|m)···B(qn|m)為一個(gè)期望反應(yīng)模式,其中k(qi)?L(m)成立時(shí),B(qi|m)=1,否則B(qi|m)=0,n=|Qsub|,qi ∈Qsub,m ∈M,0≤i≤n,R(M)表示期望反應(yīng)模式集合.

由定義8 可知,期望反應(yīng)模式是理想屬性模式的函數(shù).表3 列出了期望反應(yīng)模式與理想屬性模式間的映射關(guān)系.第1 行中R(M)=00000 表示被試在5 個(gè)項(xiàng)目上的反應(yīng)結(jié)果全部錯(cuò)誤,對(duì)應(yīng)的理想屬性模式m=0000 說(shuō)明4 個(gè)屬性都沒(méi)有掌握,所以相應(yīng)的L(m)為空集.同理,第4 行R(m)=11101說(shuō)明被試掌握了項(xiàng)目q1,q2,q3和q5對(duì)應(yīng)的屬性,所以有m=1110 和L(m)={相交線,三角形,三角形高}.

表3 理想屬性模式與期望反應(yīng)模式的對(duì)應(yīng)關(guān)系Table 3 Expected response pattern corresponding to ideal attribute pattern

2.3 規(guī)則空間生成

規(guī)則空間是定義在觀察反映模式和期望反應(yīng)模式上的關(guān)系,是兩者笛卡爾積的子集.構(gòu)建規(guī)則空間的核心問(wèn)題是由理想屬性模式構(gòu)建期望反映模式,從而確定規(guī)則空間中的純規(guī)則點(diǎn),即分類(lèi)中心.在計(jì)算分類(lèi)中心之前,需要先由領(lǐng)域知識(shí)圖和測(cè)試項(xiàng)目集計(jì)算近似子圖(Approximate subgraph,AS),算法1 描述了AS 的計(jì)算過(guò)程.

算法1.AS 算法

輸入.領(lǐng)域知識(shí)圖G=(V,E,I)和測(cè)試項(xiàng)目集Qsub?Q

輸出.近似子圖Gsub=(Vsub,Esub,Isub)

AS 算法1～4 行由測(cè)試項(xiàng)目集Qsub生成子圖劃分標(biāo)準(zhǔn)K(Qsub),第6 行的是Vsub在K(Qsub)下的補(bǔ)集,初始為K(Qsub).第7～18 行的主要功能是生成近似子圖中的直接依賴關(guān)系,9～14行對(duì)中的每個(gè)頂點(diǎn)的直接關(guān)聯(lián)關(guān)系進(jìn)行處理,根據(jù)頂點(diǎn)的直接關(guān)聯(lián)關(guān)系生成近似子圖中相應(yīng)的邊(圖2(a)).15～17 行根據(jù)頂點(diǎn)是否存在直接關(guān)聯(lián)關(guān)系決定是否把該頂點(diǎn)加入近似子圖頂點(diǎn)集(圖2(b)).20～24 行的功能是判斷是否存在從Vsub中的頂點(diǎn)vi到中頂點(diǎn)vj的路徑片段,如果存在,說(shuō)明vj間接先行依賴于vi,這是一種近似依賴關(guān)系,所以在近似子圖中建立vi到vj的邊,同時(shí)把vj加入近似子圖的頂點(diǎn)集(圖2(c),2(d)).

近似子圖能夠模擬子圖結(jié)點(diǎn)在領(lǐng)域知識(shí)圖上的依賴關(guān)系,排除屬性模式中的不合理因素,縮減合理屬性模式集規(guī)模.算法2 給出了由近似子圖計(jì)算理想屬性模式(AS based ideal attribute mode,ASIAM)的過(guò)程.

算法2.ASIAM 算法

輸入.近似子圖Gsub=Vsub,Esub,Isub

輸出.理想屬性模式集合M

算法2 的核心思想是按照定義7 給出的標(biāo)準(zhǔn),從近似子圖的初始節(jié)點(diǎn)開(kāi)始,依次尋找頂點(diǎn)個(gè)數(shù)為1～|Vsub|的初始可達(dá)子圖的過(guò)程(4～17 行).這里初始可達(dá)子圖是近似子圖的子圖,且初始可達(dá)子圖中的任意頂點(diǎn)至少屬于一條初始路徑.算法第1 行的Γ1用于存儲(chǔ)上次迭代過(guò)程中找到的理想屬性模式,Γ2存儲(chǔ)當(dāng)前迭代找到的理想屬性模式.由于可能有多個(gè)初始結(jié)點(diǎn),為了把搜索問(wèn)題簡(jiǎn)化為單源路徑搜索,設(shè)置初始頂點(diǎn)E,使其能夠到達(dá)Isub中的所有頂點(diǎn).5～15 行依次從上一輪迭代產(chǎn)生的理想屬性模式中的頂點(diǎn)出發(fā)展開(kāi)搜索,如果能夠找到1 條新邊且能夠引入1 個(gè)新頂點(diǎn),則產(chǎn)生一個(gè)長(zhǎng)度增1 的理想屬性模式(8～13 行),將其存入Γ2(第9 行).一輪迭代結(jié)束,產(chǎn)生一組長(zhǎng)度增1 的理想屬性模式.算法2 最后返回集合M.注意到M中的元素實(shí)際上是理想屬性模式對(duì)應(yīng)的標(biāo)簽集合,可由定義7 直接導(dǎo)出理想屬性模式.

期望反映模式和理想屬性模式是一一對(duì)應(yīng)的,所以可以根據(jù)定義8 直接導(dǎo)出M對(duì)應(yīng)的期望反應(yīng)模式集合,從而生成規(guī)則空間中的純規(guī)則點(diǎn),完成規(guī)則空間的構(gòu)建.由于規(guī)則空間模型的重要假設(shè)是被試在進(jìn)行測(cè)試時(shí)會(huì)出現(xiàn)失誤,造成觀察反應(yīng)模式與期望反應(yīng)模式間的誤差.因此,如何把被試的觀察反應(yīng)模式映射到期望反應(yīng)模式是進(jìn)行認(rèn)知診斷的關(guān)鍵.可以通過(guò)計(jì)算被試實(shí)際規(guī)則點(diǎn)和純規(guī)則點(diǎn)的馬氏距離進(jìn)行模式識(shí)別,得出學(xué)生對(duì)知識(shí)的掌握情況,詳細(xì)計(jì)算過(guò)程見(jiàn)文獻(xiàn)[8,16?17].

2.4 算法分析

1)規(guī)則空間壓縮能力

壓縮規(guī)則空間的實(shí)質(zhì)是縮減理想屬性模式集的規(guī)模.當(dāng)測(cè)試項(xiàng)目集確定后,屬性模式涉及的屬性集合也就確定了.為了縮減理想屬性模式集的規(guī)模,需要從領(lǐng)域知識(shí)圖中提取屬性間的依賴關(guān)系.如果通過(guò)計(jì)算領(lǐng)域知識(shí)圖的依賴保持子圖提取屬性依賴關(guān)系,會(huì)引入和測(cè)試項(xiàng)目集無(wú)關(guān)的額外屬性,導(dǎo)致理想屬性模式集的規(guī)模呈指數(shù)級(jí)增長(zhǎng),如圖3(a)所示.直接計(jì)算頂點(diǎn)導(dǎo)出子圖能夠避免引入額外屬性,其對(duì)傳遞依賴關(guān)系的忽略會(huì)導(dǎo)致理想屬性模式集規(guī)模過(guò)大,因?yàn)榇罅坎缓侠韺傩阅Ｊ綗o(wú)法被過(guò)濾,如圖3(b)所示.本文通過(guò)計(jì)算領(lǐng)域知識(shí)圖關(guān)于測(cè)試項(xiàng)目集的近似子圖(Approximate subgraph,AS)生成屬性間的依賴關(guān)系,相對(duì)于VDS,計(jì)算近似子圖能夠在不引入額外屬性的前提下進(jìn)一步壓縮理想屬性模式集的規(guī)模,從而達(dá)到壓縮狀態(tài)空間規(guī)模的目的.以第3.1 節(jié)給出的測(cè)試項(xiàng)目集為例,圖3(a)是由測(cè)試項(xiàng)目集計(jì)算出的依賴保持子圖,圖3(b)為頂點(diǎn)導(dǎo)出子圖,圖3(c)為由測(cè)試項(xiàng)目集計(jì)算出的近似子圖.

圖3 測(cè)試項(xiàng)目集的導(dǎo)出子圖Fig.3 Subgraphs exported from test item set

由圖3 知,為了避免在傳遞依賴子圖中引入額外頂點(diǎn),頂點(diǎn)導(dǎo)出子圖只保留了領(lǐng)域知識(shí)圖中與測(cè)試項(xiàng)目直接相關(guān)的依賴關(guān)系,忽略了知識(shí)圖中的間接依賴關(guān)系.事實(shí)上,在領(lǐng)域知識(shí)圖上存在“相交線”通過(guò)“垂線”到“三角形高”路徑、“相交線”通過(guò)“角”到“三角形”的路徑以及“三角形”通過(guò)“三角形底”到“三角形面積”的路徑,也即“相交線”和“垂線”是“三角形高”的先行知識(shí)點(diǎn)、“相交線”和“角”是“三角形”的先行知識(shí)點(diǎn)以及“三角形”和“三角形底”是“三角形面積”的先行知識(shí)點(diǎn).頂點(diǎn)導(dǎo)出子圖對(duì)這種間接依賴關(guān)系的忽略是不合理的,同時(shí)也會(huì)導(dǎo)致理想屬性模式集規(guī)模膨脹,表4 給出了由VDS 導(dǎo)出的理想屬性模式集,其規(guī)模為8.而近似子圖保持了“相交線”到“三角形高”、“相交線”到“三角形”以及“三角形”到“三角形面積”的傳遞依賴關(guān)系,雖然還存在“相交線”到“三角形面積”的間接依賴關(guān)系,但需要通過(guò)“三角形高”或“三角形”實(shí)現(xiàn),根據(jù)定義5 條件3)近似子圖中不建立該依賴關(guān)系.近似子圖能夠在不引入額外屬性的前提下保持屬性間的間接依賴關(guān)系,從而實(shí)現(xiàn)對(duì)理想屬性模式規(guī)模的進(jìn)一步壓縮.本例中由近似子圖導(dǎo)出的理想屬性模式規(guī)模僅為5,如表2 所示.

通過(guò)上述實(shí)例可以看出,近似子圖能夠顯著縮減理想屬性模式集的規(guī)模,從而實(shí)現(xiàn)對(duì)規(guī)則空間的壓縮.相對(duì)于VDS 而言,這種壓縮能力是通過(guò)構(gòu)造領(lǐng)域知識(shí)圖中不存在的虛擬邊實(shí)現(xiàn)的.

表4 由VDS 導(dǎo)出的理想屬性模式集Table 4 Ideal attribute set exported from VDS

2)依賴關(guān)系保持能力

近似子圖中引入的虛擬邊描述了頂點(diǎn)間的間接依賴關(guān)系,目的是使近似子圖盡可能保持領(lǐng)域知識(shí)圖中知識(shí)間的依賴關(guān)系.近似子圖中引入的這些新的依賴關(guān)系是否能夠保持領(lǐng)域知識(shí)圖上的依賴關(guān)系是影響認(rèn)知診斷結(jié)果正確性的關(guān)鍵因素.為了證明近似子圖依賴關(guān)系保持能力,下面先參考文獻(xiàn)[26]給出的DAG 圖間模擬關(guān)系的定義.

定義9.令Gi=(Vi,Ei,Ii)為DAG 圖,其中i=1,2,V2?V1,模擬關(guān)系是定義在G1,G2上的二元關(guān)系R ?V1×V2當(dāng)且僅當(dāng)下列條件成立:

a)對(duì)任意v ∈I2,如果G1上存在路徑片段u1u2···un,其中,u1∈I1,un=v,n≥1,1≤i≤n,此時(shí)(ui,v)∈R;

b)對(duì)任意(v1,v2)∈R,如果存在直接依賴于v2,則G1上存在從v2出發(fā)的路徑片段u1∈I1,un=v,使得成立,其中,u1=v2,

如果存在定義在G1和G2上的模擬關(guān)系R,則稱G2模擬G1或G1被G2模擬,記為G1?ST G2.

定理2.如果Gsub=(Vsub,Esub,Isub)為G=(V,E,I)關(guān)于子圖劃分標(biāo)準(zhǔn)K(Qsub)的近似子圖,則有G ?ST Gsub成立.

證明.令R ?V×Vsub為定義在G和Gsub上的二元關(guān)系,由定義4 和定義5 可知,Isub?Vsub=K(Qsub)?V.

a)對(duì)任意v ∈Isub,由定義9 條件a)可知,如果v ∈I,則(v,v)∈R,否則,由定理1 可知,G上存在從初始節(jié)點(diǎn)到v的初始路徑u1u2···un,使得u1∈I,un=v成立,其中,1≤i≤n,于是可得(ui,v)∈R;

b)對(duì)任意(v1,v2)∈R,對(duì)任意v2的直接后繼節(jié)點(diǎn)由v2∈Vsub,可知,v2∈V,根據(jù)定義5 條件3)可得,G上存在從v2到的路徑片段u1u2···un,使得u1=v2,un=其中,n≥1,1≤i≤n,于是有

定理2 證明了領(lǐng)域知識(shí)圖G能夠被近似子圖Gsub模擬.但是近似子圖中引入了領(lǐng)域知識(shí)圖上不存在的間接依賴關(guān)系,這種模擬關(guān)系是否能夠使Gsub保持G上頂點(diǎn)間的依賴關(guān)系是影響規(guī)則空間正確性的決定因素.下面通過(guò)引入定義在路徑上的Stutter 等價(jià)關(guān)系來(lái)說(shuō)明這個(gè)問(wèn)題.

定義10.令Gi=(Vi,Ei,Ii)為兩個(gè)DAG圖,pi為Gi上的路徑,其中i=1,2.其中,p1=

p1Stutter 等價(jià)于p2當(dāng)且僅當(dāng)存在二元關(guān)系R?V1×V2,使得···成立,其中,1≤i1≤m1,1≤i2≤m2,1≤i3≤m3,···,1≤j1≤n1,1≤j2≤n2,1≤j3≤n3,···,p1Stutter 等價(jià)于p2記為p1p2.

定理3.如果Gsub=(Vsub,Esub,Isub)為G=(V,E,I)關(guān)于子圖劃分標(biāo)準(zhǔn)K(Qsub)的近似子圖,對(duì)于Gsub上的任意初始路徑psub,G上存在初始路徑p,使得ppsub.

證明.由定理2 可知,G ?ST Gsub,令R ?V×Vsub為定義在G和Gsub上的模擬關(guān)系,psub=v1v2v3···為Gsub上的初始路徑.由于v1∈Isub,根據(jù)定義9 條件1)可知,G上存在路徑片段u11u12···其中,u11∈I,=v1,n1≥1,1≤i1≤n1,此時(shí)有∈R成立.

假設(shè)vm為psub上的頂點(diǎn)(m≥1),且G上存在路徑片段其中,=vm,nm≥1,此時(shí)有∈R成立,1≤im≤nm.

對(duì)于psub上的頂點(diǎn)vm+1,由于vm+1直接依賴于vm,由定義9 條件b)可知,G上存在從vm出發(fā)的路徑片段使得(ui(m+1),vm+1)∈R成立,其中,u(m+1)1=vm,=vm+1,nm+1≥2,1≤im+1≤nm+1.

經(jīng)歸納可得,G上存在初始路徑p=v11v12······Stutter 等價(jià)于psub.

定理3 保證了近似子圖上的路徑在其生成知識(shí)圖上存在Stutter 等價(jià)路徑,說(shuō)明近似子圖保持了領(lǐng)域知識(shí)圖上的依賴關(guān)系,即近似子圖引入的額外依賴關(guān)系能夠模擬領(lǐng)域知識(shí)圖上的依賴關(guān)系.這個(gè)性質(zhì)保證了理想屬性模式及規(guī)則空間的合理性.也就是說(shuō),近似子圖不僅能夠有效壓縮規(guī)則空間的規(guī)模,而且能夠保持領(lǐng)域知識(shí)圖上的依賴關(guān)系.

3)算法性能分析

給定領(lǐng)域知識(shí)圖G=(V,E,I)和測(cè)試項(xiàng)目集Qsub.對(duì)于AS 算法,最壞情況是初始時(shí)K(Qsub)中頂點(diǎn)間不存在直接依賴關(guān)系,此時(shí)AS 算法需要探測(cè)Vsub中任意頂點(diǎn)到中頂點(diǎn)的路徑是否滿足定義5 第5)項(xiàng)的要求.因此,AS 算法的最壞時(shí)間復(fù)雜度為(|V|+|E|)×|K(Qsub)|.而DPS 算法為保持領(lǐng)域知識(shí)圖中與K(Qsub)相關(guān)的全部依賴關(guān)系,最壞時(shí)間復(fù)雜度也為(|V|+|E|)×|K(Qsub)|.由于VDS 算法只從領(lǐng)域知識(shí)圖中抽取與K(Qsub)中頂點(diǎn)相關(guān)的直接依賴關(guān)系,所以最壞時(shí)間復(fù)雜度為|V|+|E|.從消耗的存儲(chǔ)空間角度來(lái)看,AS,DPS和VDS 三種算法在計(jì)算過(guò)程中都需要存儲(chǔ)生成子圖的頂點(diǎn)集和邊集.由于AS 算法和VDS 算法生成的子圖都不引入K(Qsub)以外的頂點(diǎn),所以它們?cè)谧顗那闆r下的空間復(fù)雜度為|K(Qsub)|+|E|,DPS算法的最壞空間復(fù)雜度為|V|+|E|.

3 實(shí)驗(yàn)結(jié)果與分析

本文開(kāi)展了兩組實(shí)驗(yàn)分別用于驗(yàn)證基于近似子圖的規(guī)則空間生成算法的空間壓縮能力及其在實(shí)時(shí)課堂教學(xué)認(rèn)知診斷中的有效性.兩組實(shí)驗(yàn)使用基于認(rèn)知診斷的可編程教學(xué)輔助系統(tǒng)(Cognitive diagnosis based programmable teaching support system,CDPTSS)開(kāi)展教學(xué)認(rèn)知診斷,該系統(tǒng)在CETE(Center for educational testing and evaluation)實(shí)驗(yàn)室設(shè)計(jì)的認(rèn)知診斷評(píng)價(jià)工具提供的開(kāi)放接口上實(shí)現(xiàn)了基于近似子圖的規(guī)則空間生成算法,并提供實(shí)現(xiàn)規(guī)則空間壓縮的可編程接口.系統(tǒng)運(yùn)行操作系統(tǒng)為Ubuntu Server 14.04,處理器為Intel xeon e5-262,主頻2.0 GHz,內(nèi)存32 GB.

3.1 實(shí)驗(yàn)方案

第1 組實(shí)驗(yàn)的目的是對(duì)比DPS,VDS 和AS 算法在相同測(cè)試項(xiàng)目集下的子圖規(guī)模以及由這些子圖生成的理想屬性模式集的規(guī)模,從而驗(yàn)證近似子圖對(duì)規(guī)則空間的壓縮能力.使用的標(biāo)準(zhǔn)測(cè)試集為AAAS(American Association for the Advancement of Science)提供的數(shù)學(xué)知識(shí)圖1http://www.project2061.org/publications/bsl/online/index.php.實(shí)驗(yàn)數(shù)據(jù)僅涉及由該數(shù)學(xué)知識(shí)圖中知識(shí)間依賴關(guān)系構(gòu)成的DAG 圖.實(shí)驗(yàn)用測(cè)試項(xiàng)目集從知識(shí)圖配套單元測(cè)試集中抽取.為了滿足AS 算法的初始條件,在DAG圖中建立節(jié)點(diǎn)0 作為所有初始節(jié)點(diǎn)的依賴節(jié)點(diǎn).實(shí)驗(yàn)抽取10 組測(cè)試項(xiàng)目,在相同環(huán)境下使用DPS,VDS 和AS 算法由各組測(cè)試項(xiàng)目生成知識(shí)子圖,進(jìn)而應(yīng)用ASIAM 算法計(jì)算理想屬性模式.

第2 組實(shí)驗(yàn)通過(guò)開(kāi)展實(shí)際教學(xué)認(rèn)知診斷應(yīng)用分析DPS,VDS 和AS 的性能差異.評(píng)價(jià)指標(biāo)和實(shí)驗(yàn)過(guò)程與第一組實(shí)驗(yàn)相同.實(shí)驗(yàn)涉及的課程為《Java語(yǔ)言程序設(shè)計(jì)》,領(lǐng)域知識(shí)圖由該課程中的83 個(gè)相關(guān)知識(shí)點(diǎn)生成,測(cè)試項(xiàng)目庫(kù)規(guī)模為223.共開(kāi)展8 次認(rèn)知診斷測(cè)驗(yàn),根據(jù)實(shí)際教學(xué)單元涉及的知識(shí)點(diǎn)確定測(cè)試項(xiàng)目.為了評(píng)價(jià)三種算法在課堂教學(xué)認(rèn)知診斷應(yīng)用中的實(shí)際效果,每次測(cè)試項(xiàng)目的規(guī)模由所選教學(xué)小節(jié)的實(shí)際內(nèi)容確定.此組實(shí)驗(yàn)首先根據(jù)所選測(cè)試項(xiàng)目集分別由三種算法生成規(guī)則空間,并記錄相關(guān)結(jié)果數(shù)據(jù).進(jìn)一步選擇一個(gè)教學(xué)班共56 人作為實(shí)驗(yàn)對(duì)象,使用AS 算法生成的規(guī)則空間對(duì)學(xué)生知識(shí)狀態(tài)進(jìn)行診斷,并由實(shí)驗(yàn)對(duì)象對(duì)評(píng)價(jià)結(jié)果進(jìn)行評(píng)價(jià)反饋,以驗(yàn)證AS 算法生成的規(guī)則空間的合理性以及應(yīng)用該規(guī)則空間開(kāi)展認(rèn)知診斷的準(zhǔn)確率.

3.2 規(guī)則空間壓縮能力實(shí)驗(yàn)結(jié)果與分析

第1 組和第2 組實(shí)驗(yàn)生成的近似子圖及理想屬性模式規(guī)模分別如表5 和表6 所示.從表5 給出的子圖頂點(diǎn)集規(guī)模來(lái)看,AS 和VDS 算法沒(méi)有引入與測(cè)試項(xiàng)目集無(wú)關(guān)的頂點(diǎn),所以它們計(jì)算獲得的子圖頂點(diǎn)集只與測(cè)試項(xiàng)目集生成的劃分標(biāo)準(zhǔn)有關(guān).因此,AS 和VDS 算法計(jì)算得到的子圖頂點(diǎn)集相同.而DPS 算法計(jì)算得到的子圖頂點(diǎn)集規(guī)模依賴于測(cè)試項(xiàng)目集涉及的知識(shí)點(diǎn)間的依賴關(guān)系.測(cè)試項(xiàng)目集生成的劃分標(biāo)準(zhǔn)規(guī)模越大,知識(shí)點(diǎn)間的依賴關(guān)系就越復(fù)雜,DPS 生成的子圖引入的額外頂點(diǎn)越多,導(dǎo)致子圖頂點(diǎn)集規(guī)模迅速增大,導(dǎo)致DPS 算法計(jì)算得到的邊集規(guī)模顯著大于AS 和VDS 算法.而子圖規(guī)模的增長(zhǎng)會(huì)導(dǎo)致理想屬性模式集規(guī)模呈指數(shù)級(jí)增長(zhǎng),最終導(dǎo)致DPS 算法計(jì)算得到的理想屬性模式集規(guī)模與AS 和VDS 算法計(jì)算得到的理想屬性模式集不在一個(gè)量級(jí)上.從實(shí)驗(yàn)結(jié)果數(shù)據(jù)來(lái)看,AS 和VDS算法相較DPS 算法而言,能夠在計(jì)算子圖過(guò)程中忽略與測(cè)試項(xiàng)目無(wú)關(guān)的頂點(diǎn),從而實(shí)現(xiàn)對(duì)子圖規(guī)模的壓縮.從表5 給出的實(shí)驗(yàn)結(jié)果來(lái)看,AS 和VDS 最大的差別在于AS 計(jì)算得到的子圖邊集規(guī)模大于VDS 計(jì)算得到的邊集,原因是VDS 計(jì)算得到的頂點(diǎn)導(dǎo)出子圖只保留與劃分標(biāo)準(zhǔn)直接相關(guān)的知識(shí)依賴關(guān)系,這種方法能夠保證總是獲得最小化的子圖邊集,不足之處是忽略了知識(shí)點(diǎn)間存在的間接依賴關(guān)系.為了在壓縮子圖規(guī)模的同時(shí)盡可能保證知識(shí)點(diǎn)間依賴關(guān)系的完整性,AS 算法在VDS 算法基礎(chǔ)上,通過(guò)構(gòu)建頂點(diǎn)間的虛擬邊模擬知識(shí)點(diǎn)間的傳遞依賴關(guān)系,從而在保證子圖頂點(diǎn)集最小化的前提下保留了知識(shí)點(diǎn)間的間接依賴關(guān)系,這是AS 生成的子圖邊集規(guī)模大于VDS 生成的子圖邊集的原因.這些保留下來(lái)的間接依賴關(guān)系能夠在計(jì)算理想屬性模式集時(shí)縮減更多不合理屬性模式,從而使AS 算法計(jì)算得到的理想屬性模式集顯著小于VDS 算法計(jì)算得到的理想屬性模式集.從實(shí)驗(yàn)結(jié)果來(lái)看,相較于DPS 和VDS 算法,AS 算法能夠獲得規(guī)模更小的理想屬性模式集.

表5 第1 組實(shí)驗(yàn)中子圖及理想屬性模式規(guī)模Table 5 Scale of subgraphs and ideal attribute pattern in the first experiment

表6 第2 組實(shí)驗(yàn)中子圖及理想屬性模式規(guī)模Table 6 The scale of subgraphs and ideal attribute pattern in practical teaching cogonitive diagnosis in the second experiment

表6 給出了第2 組實(shí)驗(yàn)中依據(jù)實(shí)際教學(xué)內(nèi)容生成規(guī)則空間部分的實(shí)驗(yàn)結(jié)果數(shù)據(jù).從表6 可以看出,8 次測(cè)驗(yàn)涉及的測(cè)試項(xiàng)目集規(guī)模在6～8 之間,子圖劃分標(biāo)準(zhǔn)規(guī)模也在5～8 之間.DPS,VDS 和AS 對(duì)子圖規(guī)模的壓縮能力也與第一組實(shí)驗(yàn)一致.DPS 對(duì)子圖規(guī)模的壓縮能力最弱,但能夠精確地保持領(lǐng)域知識(shí)圖中的所有依賴關(guān)系;VDS 對(duì)子圖規(guī)模的壓縮能力最強(qiáng),但不能保持完備的知識(shí)依賴關(guān)系;AS 創(chuàng)建的子圖點(diǎn)集規(guī)模與VDS 相同,但邊集略大,總體上兩者創(chuàng)建的子圖規(guī)模處于同一水平,但AS 創(chuàng)建的子圖通過(guò)引入模擬間接依賴關(guān)系的虛擬邊使子圖保持了領(lǐng)域知識(shí)圖上的依賴關(guān)系.相對(duì)VDS 而言,由AS 創(chuàng)建的子圖能夠削減掉更多不合理的屬性模式,從而實(shí)現(xiàn)對(duì)規(guī)則空間最大限度的壓縮.

3.3 規(guī)則空間生成時(shí)間實(shí)驗(yàn)結(jié)果與分析

第1 組和第2 組實(shí)驗(yàn)生成的近似子圖及理想屬性模式規(guī)模分別如圖4 和圖5 所示.圖4 給出了ASIAM 算法使用三種算法生成的知識(shí)子圖構(gòu)建規(guī)則空間消耗的時(shí)間代價(jià).圖中方塊、實(shí)心圓點(diǎn)和三角分別表示由DPS,VDS 和AS 構(gòu)建的子圖生成規(guī)則空間所需時(shí)間代價(jià).從圖4 可以看出,在子圖規(guī)模較小的情況下,三者生成規(guī)則空間消耗的時(shí)間代價(jià)差異不明顯.隨著子圖規(guī)模的增長(zhǎng),由DPS 構(gòu)建的子圖生成規(guī)則空間所需時(shí)間代價(jià)呈指數(shù)級(jí)增長(zhǎng),原因是生成規(guī)則空間所需時(shí)間代價(jià)隨子圖規(guī)模呈指數(shù)級(jí)增長(zhǎng),這也是DPS 算法不適用于大規(guī)模認(rèn)知診斷的直接原因.

圖4 第1 組實(shí)驗(yàn)規(guī)則空間生成時(shí)間Fig.4 Time performance of rule space generation in the first experiment

圖5 第2 組實(shí)驗(yàn)規(guī)則空間生成時(shí)間Fig.5 Time performance of rule space generation in the second experiment

由于AS 和VDS 算法生成的子圖點(diǎn)集相同,區(qū)別僅在于邊集規(guī)模,它們生成的子圖規(guī)模處于同一量級(jí).但VDS 算法構(gòu)建的子圖邊集規(guī)模較小,導(dǎo)致計(jì)算合理屬性模式所需運(yùn)算量較小.因此,由VDS算法構(gòu)建的子圖生成規(guī)則空間所需時(shí)間代價(jià)略低于由AS 算法構(gòu)建的子圖生成規(guī)則空間所需時(shí)間代價(jià).總體上來(lái)看,兩者所需時(shí)間代價(jià)處于同一量級(jí).結(jié)合表5 實(shí)驗(yàn)結(jié)果來(lái)看,AS 算法能夠在不顯著降低時(shí)間性能的前提下,使構(gòu)建的子圖生成的理想屬性模式集規(guī)模更小,從而達(dá)到壓縮規(guī)則空間的目的.

圖5 給出了由三種算法創(chuàng)建的子圖生成規(guī)則空間的時(shí)間代價(jià).由于8 次教學(xué)認(rèn)知診斷涉及的測(cè)試項(xiàng)目集規(guī)則較小,三者時(shí)間性能在縱軸上的落差遠(yuǎn)小于圖4.總體來(lái)看,圖5 反映的時(shí)間性能與圖4 一致,由DPS 算法創(chuàng)建的子圖生成規(guī)則空間的時(shí)間性能最差;由AS 算法創(chuàng)建的子圖生成規(guī)則空間的時(shí)間代價(jià)略高于由VDS 算法創(chuàng)建的子圖生成規(guī)則空間的時(shí)間代價(jià),但兩者處于同一量級(jí).圖5 中在個(gè)別點(diǎn)上由三種算法創(chuàng)建的子圖生成規(guī)則空間的時(shí)間代價(jià)差異并不明顯,這是由于本次測(cè)驗(yàn)使用的測(cè)試項(xiàng)目涉及的知識(shí)點(diǎn)比較集中,DPS 創(chuàng)建子圖時(shí)沒(méi)有引入過(guò)多的額外頂點(diǎn),而VDS 和AS 創(chuàng)建子圖時(shí)不會(huì)引入無(wú)關(guān)頂點(diǎn),三者生成的子圖規(guī)則差異不大,所以由三個(gè)子圖生成規(guī)則空間時(shí)的時(shí)間性能也基本相當(dāng).

3.4 診斷結(jié)果準(zhǔn)確率實(shí)驗(yàn)結(jié)果與分析

上述實(shí)驗(yàn)通過(guò)標(biāo)準(zhǔn)測(cè)試集和實(shí)際教學(xué)認(rèn)知診斷應(yīng)用,對(duì)AS 算法的規(guī)則空間壓縮能力進(jìn)行驗(yàn)證和分析,證明AS 相較VDS 和DPS 具有更好的規(guī)則空間壓縮能力.為了進(jìn)一步觀察由AS 算法創(chuàng)建的近似子圖生成的規(guī)則空間的合理性,即使用該規(guī)則空間開(kāi)展認(rèn)知診斷時(shí)的準(zhǔn)確率,在第2 組實(shí)驗(yàn)中進(jìn)一步使用由AS 算法生成的規(guī)則空間對(duì)56 名實(shí)驗(yàn)對(duì)象開(kāi)展認(rèn)知診斷,診斷結(jié)束后由實(shí)驗(yàn)對(duì)象對(duì)診斷結(jié)果的準(zhǔn)確性進(jìn)行主觀評(píng)價(jià),評(píng)價(jià)結(jié)果由CDPTSS系統(tǒng)回收和統(tǒng)計(jì),如表7 所示.

表7 診斷結(jié)果準(zhǔn)確率Table 7 Accuracy of diagnostic results

表7 中Valid 表示有效評(píng)價(jià)結(jié)果數(shù)量,H,M,L分別表示診斷結(jié)果準(zhǔn)確率在91～100%、81～90%和0～80% 三個(gè)區(qū)間的實(shí)驗(yàn)對(duì)象比例.從實(shí)驗(yàn)對(duì)象的主觀評(píng)價(jià)結(jié)果來(lái)看,平均有90.26% 的實(shí)驗(yàn)對(duì)象的診斷結(jié)果準(zhǔn)確率在H區(qū)間,6.76% 的實(shí)驗(yàn)對(duì)象的診斷結(jié)果準(zhǔn)確率在M區(qū)間,2.98% 的實(shí)驗(yàn)對(duì)象的診斷結(jié)果準(zhǔn)確率在L區(qū)間.總體來(lái)看,使用AS 算法創(chuàng)建的近似子圖生成的規(guī)則空間能夠有效支持教學(xué)認(rèn)知診斷,診斷結(jié)果準(zhǔn)確率較高,從被測(cè)試對(duì)象的主觀角度反映了近似子圖的依賴關(guān)系保持能力.

4 結(jié)論

本文提出一種使用似子圖壓縮規(guī)則空間的方法.近似子圖能夠忽略與測(cè)試項(xiàng)目無(wú)關(guān)的屬性,同時(shí)通過(guò)構(gòu)建頂點(diǎn)間的虛擬邊模擬領(lǐng)域知識(shí)圖上的傳遞依賴關(guān)系.這種方法在有效縮減規(guī)則空間規(guī)模的同時(shí),使近似子圖保持了領(lǐng)域知識(shí)圖上的依賴關(guān)系.通過(guò)構(gòu)建DAG 圖上的模擬關(guān)系證明了近似子圖對(duì)依賴關(guān)系的保持能力.使用標(biāo)準(zhǔn)測(cè)試集驗(yàn)證了近似子圖構(gòu)建規(guī)則空間的時(shí)間代價(jià)與VDS 算法處于同一量級(jí),但近似子圖對(duì)依賴關(guān)系的保持能力使其能夠更為徹底地過(guò)濾不合理屬性模式,從而實(shí)現(xiàn)對(duì)規(guī)則空間規(guī)模的壓縮.近似子圖在實(shí)際教學(xué)認(rèn)知診斷中的應(yīng)用,進(jìn)一步驗(yàn)證了近似子圖能夠在不影響診斷結(jié)果準(zhǔn)確率的同時(shí),使規(guī)則空間模型有效支持小規(guī)模、實(shí)時(shí)教學(xué)認(rèn)知診斷.然而,使用近似子圖生成規(guī)則空間開(kāi)展認(rèn)知診斷產(chǎn)生的知識(shí)狀態(tài)圖中存在虛擬邊,如何從包含虛擬邊的知識(shí)狀態(tài)圖中生成補(bǔ)救教學(xué)路徑是影響診斷結(jié)果易用性的關(guān)鍵因素.文獻(xiàn)[27?30]提出的由抽象路徑生成具體路徑的方法為解決該問(wèn)題提供了可借鑒的思路,今后,將進(jìn)一步研究如何把包含虛擬邊的補(bǔ)救教學(xué)路徑在領(lǐng)域知識(shí)圖上具體化.