楊桃麗 李進(jìn)金,2 李招文 金 銘 周銀鳳 林藝東,2

知識空間理論(Knowledge Space Theory, KS-T)[1-3]是一種用于評估個(gè)體知識水平和指導(dǎo)進(jìn)一步學(xué)習(xí)的數(shù)學(xué)心理框架,目前，已應(yīng)用在ALEKS系統(tǒng)和自適應(yīng)輔導(dǎo)系統(tǒng)[4]，并在其它領(lǐng)域具有潛在的應(yīng)用價(jià)值[2]．

知識狀態(tài)是KST的基本概念之一．在非空有限的問題域中，個(gè)體的知識狀態(tài)表示為個(gè)體在理想狀態(tài)下能正確解決問題的集合[1-2]．在很多情況下，可從個(gè)體對不同問題的回答中推斷個(gè)體的知識狀態(tài)，即通過檢測個(gè)體對問題的回答情況，評估個(gè)體的知識掌握情況．知識結(jié)構(gòu)是評估個(gè)體知識水平的重要工具，表示為序?qū)?Q,K).其中K是至少包含?和全集Q的知識狀態(tài)的集合，一般地，習(xí)慣直接使用K表示知識結(jié)構(gòu)．

構(gòu)建一個(gè)準(zhǔn)確的知識結(jié)構(gòu)的方法是知識空間理論的重要研究內(nèi)容.圍繞這一問題，學(xué)者們結(jié)合其它學(xué)科以構(gòu)建知識結(jié)構(gòu)．形式概念分析(Formal Con-cept Analysis, FCA)可與KST結(jié)合.Rusch等[5]討論由形式背景構(gòu)建知識結(jié)構(gòu)的方法，為概念知識的獲取提供一種新的途徑．李進(jìn)金等[6]基于知識基，提出由形式背景構(gòu)建知識結(jié)構(gòu)的方法，進(jìn)一步加強(qiáng)FCA與KST之間的聯(lián)系．受粗糙集近似思想的啟發(fā)，Yao等[7]利用粗糙集理論(Rough Set Theory, RST)中的近似思想構(gòu)建知識結(jié)構(gòu)，有效地在同一環(huán)境下研究RST與KST．

但是，上述方法僅停留在獲得個(gè)體可能的知識狀態(tài)，并未評價(jià)個(gè)體的知識掌握情況.針對這一問題，已有多位研究者將KST推廣到基于能力的知識空間理論(Competency-Based KST, Cb-KST)[8-11].在一般的KST中，構(gòu)建知識狀態(tài)和知識結(jié)構(gòu)常用的方法是分析問題和技能之間的關(guān)系[12-14]，而技能概念的引入為個(gè)體知識評價(jià)提供一種切入手段.Doignon[15]提出技能映射的析取模型和合取模型及技能多映射的能力模型，并討論由其誘導(dǎo)的知識結(jié)構(gòu)，但忽視個(gè)體掌握與解決問題有關(guān)的技能個(gè)數(shù)情況.周銀鳳等[16]給出技能背景的概念，討論由技能背景構(gòu)建知識結(jié)構(gòu)及技能評估等問題，考慮個(gè)體技能的評價(jià)問題，在教育教學(xué)方面具有一定的參考性意義，但未考慮技能函數(shù)等技能評估問題.Stefanutti等[11]和周銀鳳等[17]就技能函數(shù)與技能評估的問題，研究個(gè)體能力水平與表現(xiàn)水平,建立一一對應(yīng)的條件問題，但要實(shí)現(xiàn)兩者的一一對應(yīng)，還有待進(jìn)一步改進(jìn)條件.

特別地，在Doignon[15]提出的析取模型、合取模型和能力模型中，由技能映射誘導(dǎo)知識結(jié)構(gòu)的條件過于寬松或苛刻.這是因?yàn)?，在析取模型中，一旦個(gè)體掌握與解決問題有關(guān)的某個(gè)技能，便足以解決該問題，這將導(dǎo)致無論個(gè)體掌握多少個(gè)與解決問題相關(guān)的技能，最終個(gè)體的知識結(jié)構(gòu)都是相同的.在合取模型中，個(gè)體需掌握與解決問題有關(guān)的所有技能，才能解決該問題.實(shí)際上，個(gè)體不一定要掌握所有技能才有能力解決相應(yīng)的問題.在能力模型中，對于解決問題的所有能力，個(gè)體掌握其中某個(gè)能力就足以解決該問題，而一個(gè)能力是由多種技能形成的，即個(gè)體需掌握這個(gè)能力中的所有技能才能解決此問題.因此，這些評價(jià)個(gè)體知識情況的方法都集中于個(gè)體所能解決的問題，無法解釋不同個(gè)體解決相同問題背后卻有不同知識結(jié)構(gòu)的現(xiàn)象.

然而，在解決問題的所有方法中，可能會存在冗余的技能．為此，Düntsch等[8]研究技能多映射的極小形式，定義技能函數(shù)和問題函數(shù)的概念.孫曉燕等[18]基于項(xiàng)目狀態(tài)轉(zhuǎn)移函數(shù)，將問題空間推廣到多分情形.Xu等[19]結(jié)合粗糙集屬性約簡的方法，尋找極小技能集.Sun等[20]提出極小模糊技能映射的概念.Heller等[9]指出技能函數(shù)具有兩種特殊的情形，即析取技能函數(shù)和合取技能函數(shù)．在現(xiàn)實(shí)生活中，不同的個(gè)體具有不同的技能或能力，不同的技能或能力可能解決相同的問題，于是出現(xiàn)等價(jià)的技能或能力．基于上述考慮的問題，可根據(jù)個(gè)體的知識狀態(tài)規(guī)劃其下一步需要學(xué)習(xí)的技能．

總之，由技能映射或技能函數(shù)構(gòu)建知識結(jié)構(gòu)是KST的熱點(diǎn)研究問題，在教育教學(xué)方面具有較大的應(yīng)用前景和理論研究價(jià)值．因此，本文引入技能包含度和能力包含度的概念，建立構(gòu)建知識結(jié)構(gòu)的變精度α-模型和變精度α-能力模型.再討論誘導(dǎo)良級知識結(jié)構(gòu)時(shí)技能映射需滿足的條件，得到良好技能映射誘導(dǎo)的知識結(jié)構(gòu)均為良級知識結(jié)構(gòu)的結(jié)果.然后，針對技能映射和技能函數(shù)存在等價(jià)技能子集的情況，分別考慮保持知識結(jié)構(gòu)不變的技能子集約簡及學(xué)習(xí)路徑選擇的問題，并給出獲取極小技能子集族和知識結(jié)構(gòu)的算法.最后，在6個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證本文算法的可行性和有效性.

1 基礎(chǔ)知識

本文僅在理想狀態(tài)下考慮非空有限的問題域和非空有限的技能域. 這里的理想狀態(tài)是指個(gè)體在回答問題時(shí)沒有粗心答錯或僥幸答對的情況.

知識結(jié)構(gòu)是KST的重要概念之一.個(gè)體知識狀態(tài)的集合是一個(gè)知識結(jié)構(gòu)(Q,K)．若知識結(jié)構(gòu)K保持并封閉，即對K中的任意兩個(gè)元素Ki和Kj，有Ki∪Kj∈K，則稱K是一個(gè)知識空間．若知識結(jié)構(gòu)K保持交封閉，即對K中的任意兩個(gè)元素Ki,Kj，有Ki∩Kj∈K，則稱K是一個(gè)簡單閉包空間．若知識結(jié)構(gòu)K同時(shí)保持交、并封閉，則稱K是一個(gè)擬序空間.

設(shè)(Q,K)是一個(gè)知識結(jié)構(gòu)，對q∈Q，Kq是知識結(jié)構(gòu)K中包含問題q的所有知識狀態(tài)的集合．對q∈Q，

[q]={p∈Q|Kq=Kp}

表示與q同時(shí)出現(xiàn)在某些知識狀態(tài)中的問題集合．若對?q∈Q，[q]為單點(diǎn)集，則稱(Q,K)是一個(gè)可辨識的知識結(jié)構(gòu)．若一個(gè)擬序空間(Q,K)是可辨識的，則稱(Q,K)是一個(gè)序空間.

定義1[2]三元組(Q,S,τ)稱為一個(gè)技能映射，其中,Q為非空有限問題集，S為非空有限技能集，τ為由Q到2S{?}的映射.

在問題集和技能集給定的情況下，直接稱τ為一個(gè)技能映射.

設(shè)(Q,S,τ)為一個(gè)技能映射，對T?S，定義

K={q∈Q|τ(q)∩T≠?}，

稱K是由T通過析取模型誘導(dǎo)的知識狀態(tài)．當(dāng)T取遍S的所有子集時(shí)，所得知識狀態(tài)的集合K稱為由技能映射τ通過析取模型誘導(dǎo)的知識空間．對T?S，定義

K={q∈Q|τ(q)?T}，

稱K是由T通過合取模型誘導(dǎo)的知識狀態(tài)．當(dāng)T取遍S的所有子集時(shí)，所得知識狀態(tài)的集合K稱為由技能映射τ通過合取模型誘導(dǎo)的簡單閉包空間.

定義2[8]三元組(Q,S,μ)稱為一個(gè)技能多映射，其中，Q為非空有限問題集，S為非空有限技能集，μ為由Q到22S{?}{?}的映射．

在技能多映射(Q,S,μ)中，對?q∈Q，若滿足

1)μ(q)≠?,

2)對?M∈μ(q),M≠?,

3)μ(q)中的能力關(guān)于集合的包含關(guān)系兩兩不可比較，

則稱(Q,S,μ)為一個(gè)技能函數(shù)．

在問題集和技能集給定的情況下，直接稱μ為一個(gè)技能函數(shù)．此時(shí)，對?q∈Q，稱C∈μ(q)為解決問題q的一個(gè)極小能力．

對T?S，定義

K={q∈Q|?C∈μ(q)∶C?T}，

稱K是由T通過技能函數(shù)μ誘導(dǎo)的知識狀態(tài)．當(dāng)取遍S的所有子集時(shí)，所得知識狀態(tài)的集合K稱為由μ誘導(dǎo)的知識結(jié)構(gòu)．

技能函數(shù)有兩種特殊的類型，即析取技能函數(shù)和合取技能函數(shù).

設(shè)(Q,S,μ)為一個(gè)技能函數(shù)，若對?q∈Q，有μ(q)={M}，其中??M?S，則稱(Q,S,μ)為一個(gè)合取技能函數(shù)．若對?q∈Q，有

μ(q)={{s}∶s∈M}，

其中??M?S，則稱(Q,S,μ)為一個(gè)析取技能函數(shù)．合取技能函數(shù)為每個(gè)問題分配一個(gè)非空的技能子集，誘導(dǎo)的知識結(jié)構(gòu)保持交封閉，是一個(gè)簡單閉包空間.析取技能函數(shù)為每個(gè)問題分配單點(diǎn)的技能子集，誘導(dǎo)的知識結(jié)構(gòu)保持并封閉，是一個(gè)知識空間.

定義3[2]設(shè)F是一個(gè)有限的集族，若對

?K∈F,L∈F，

存在有限序列

K=K0,K1,…,Kn=L，

使得

d(Ki,Ki+1)=|Ki△Ki+1|=
|(KiKi+1)∪(Ki+1Ki)|=1，

其中，i∈[0,n-1]，d(K,L)=n，則稱F是良級的．

滿足定義3的有限序列

K=K0,K1,…,Kn=L

稱為由K到L的緊路徑．

2 技能包含度與能力包含度

定義4設(shè)(Q,S,τ)為一個(gè)技能映射．對q∈Q，T?S，稱

為τ的技能包含度集．對q∈Q，將

稱為關(guān)于問題q的技能包含度集．

推論1設(shè)(Q,S,τ)為一個(gè)技能映射．對q∈Q，

為關(guān)于問題q的技能包含度集，則有

由技能包含度的定義可知，對于兩個(gè)不相交的技能子集Ti?S,Tj?S和T?S，不難驗(yàn)證它們的技能包含度滿足可加性和互補(bǔ)性，即

對α∈(0,1]，根據(jù)定義5，顯然有

遍歷S的子集T,通過變精度α-模型誘導(dǎo)的所有知識狀態(tài)的集合構(gòu)成知識結(jié)構(gòu)

為了方便起見，不妨將技能包含度集記為

D(τ)={β1,β2,…,βn}，

其中

0=β1<β2<…<βn=1．

假設(shè)

α∈(βi,βi+1],i=1,2,…,n-1，

在βi和βi+1之間沒有別的技能包含度，所以技能映射在這樣一個(gè)區(qū)間誘導(dǎo)的知識結(jié)構(gòu)就是在區(qū)間右端點(diǎn)誘導(dǎo)的知識結(jié)構(gòu)，即Kα=Kβi+1．

若一個(gè)技能映射(Q,S,τ)確定的技能包含度集為D(τ)={β1,β2,…,βn}，除了β1以外，對于β2,β3,…,βn，技能映射(Q,S,τ)通過變精度α-模型可誘導(dǎo)n-1個(gè)知識結(jié)構(gòu)．容易驗(yàn)證，對α∈(β1,β2]，變精度α-模型為析取模型，技能映射(Q,S,τ)通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)是一個(gè)知識空間．對α∈(βn-1,βn]，變精度α-模型為合取模型，技能映射(Q,S,τ)通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)是一個(gè)簡單閉包空間．

下面考慮更一般的情形，即結(jié)合技能函數(shù)與包含度，討論構(gòu)建知識結(jié)構(gòu)的另一種方法．

定義6設(shè)(Q,S,μ)為一個(gè)技能函數(shù)．對q∈Q，C∈μ(q)，T?S，稱

稱為μ的能力包含度集．對q∈Q，

稱為關(guān)于問題q的能力包含度集．

推論2設(shè)(Q,S,μ)為一個(gè)技能函數(shù)．對q∈Q，

為關(guān)于問題q的能力包含度集，則有

同樣地，由能力包含度的定義可知，對于兩個(gè)不相交的技能子集Ti?S,Tj?S和T?S，它們的能力包含度滿足可加性和互補(bǔ)性．于是可得如下命題 1．

命題1設(shè)(Q,S,μ)為一個(gè)技能函數(shù)．對?q∈Q，C∈μ(q)，T1?S,T2?S，T1∩T2=?，則有

證明由定義6，對q∈Q，C∈μ(q)，T1?S,T2?S，T1∩T2=?，有

命題2設(shè)(Q,S,μ)為一個(gè)技能函數(shù)，則有如下性質(zhì)：

證明由定義6和命題1即證．

由于D(μ)為一個(gè)有限集，為了方便起見，不妨將能力包含度集表示為D(μ)={β1,β2,…,βn}，其中

0=β1<β2<…<βn=1,βi+βn-i+1=1．

即

命題3設(shè)(Q,S,μ)為一個(gè)技能函數(shù)，其中Q={q1,q2,…,qm}．設(shè)D(μ)={β1,β2,…,βn}為能力包含度集，則下述成立：

3)對?qi∈Q，i=1,2,…,m，若|D(μqi)|為偶數(shù)，則

為偶數(shù)；

4)若存在qi∈Q，i=1,2,…,m，使得|D(μqi)|為奇數(shù)，則

為奇數(shù)．

證明先證1).對qi∈Q，設(shè)

D(μqi)={ε1,ε2,…,εn}．

若|D(μqi)|為偶數(shù)，由

εj+εn-j+1=1，j=1,2，…,n，

即

這與假設(shè)矛盾，因此|D(μqi)|為偶數(shù)．

再證2).類似于1)，容易證明2)是成立的．

于是有

故D(μ)為奇數(shù)．

注意到,因?yàn)?/p>

定義8設(shè)(Q,S,μ)為一個(gè)技能函數(shù)．對α∈ (0,1]，稱

為由μ通過變精度α-能力模型誘導(dǎo)的知識結(jié)構(gòu)．

定理1設(shè)(Q,S,μ)為一個(gè)技能函數(shù)．

D(μ)= {β1,β2,…,βn}

為μ的能力包含度集．對α∈(βi,βi+1]，i=1,2，…,n-1，有Kα=Kβi+1.

證明對α∈(βi,βi+1]，設(shè)Kα為由技能函數(shù)μ通過變精度α-能力模型誘導(dǎo)的知識結(jié)構(gòu)．對?T?S，有

由于βi與βi+1之間不存在其它的能力包含度，因此

故Kα=Kβi+1．

定理2設(shè)(Q,S,μ)為一個(gè)技能函數(shù)，

D(μ)= {β1,β2,…,βn}

為μ的能力包含度集．對α∈(βn-1,βn]，由μ通過變精度α-能力模型誘導(dǎo)的知識結(jié)構(gòu)是由μ通過能力模型誘導(dǎo)的知識結(jié)構(gòu)．

因?yàn)?/p>

所以有C?T，即

于是Kβn事實(shí)上是由技能函數(shù)(Q,S,μ)通過能力模型誘導(dǎo)的知識結(jié)構(gòu)．

由于技能函數(shù)具有析取技能函數(shù)和合取技能函數(shù)兩種特殊情形，可對這兩種特殊情形進(jìn)行討論．

推論3設(shè)(Q,S,μ)為一個(gè)析取技能函數(shù)，則D(μ)={0,1}．對α∈(0,1]，技能函數(shù)μ通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)是由μ通過能力模型誘導(dǎo)的知識結(jié)構(gòu)．

當(dāng)(Q,S,μ)為合取技能函數(shù)時(shí)，此時(shí)變精度α-能力模型退化為變精度α-模型．需要注意的是在技能映射(Q,S,τ)中，

τ(q)=C∈μ(q)，

于是有定理3.

定理3設(shè)(Q,S,μ)為一個(gè)合取技能函數(shù)，(Q,S,τ)為一個(gè)技能映射，且對q∈Q，

μ(q)={C|??C?S}，τ(q)=C．

對α∈(βi,βi+1]，由μ通過變精度α-能力模型誘導(dǎo)的知識結(jié)構(gòu)是由技能映射(Q,S,τ)通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)．

證明設(shè)(Q,Kα)是由μ通過變精度α-能力模型誘導(dǎo)的知識結(jié)構(gòu)．對?T?S，由定義7可得

由于合取技能函數(shù)中只為每個(gè)問題q分配一個(gè)能力且τ(q)=C，于是

變精度α-模型包括析取模型和合取模型，而技能函數(shù)的變精度α-能力模型包含能力模型和變精度α-模型，于是本文的變精度α-能力模型比文獻(xiàn)[15]中的能力模型適用性更廣．下面繼續(xù)討論合取技能函數(shù)下變精度α-能力模型誘導(dǎo)的知識結(jié)構(gòu)的一些性質(zhì)．

定理4設(shè)(Q,S,μ)為一個(gè)合取技能函數(shù)，D(μ)={β1,β2,…,βn}為μ的技能包含度集,則由μ通過變精度α-能力模型誘導(dǎo)的知識結(jié)構(gòu)Kβi+1與Kβn-i+1(i=1,2，…,n-1)互為對偶．

證明設(shè)(Q,Kβi+1)為由μ通過變精度α-能力模型誘導(dǎo)的知識結(jié)構(gòu)．對?T?S，α=βi+1，i=1,2，…,n-1，知識結(jié)構(gòu)Kβi+1中的元素

由于μ為合取技能函數(shù)，于是

由于在能力包含度1-βi+1和1-βi之間不存在其它的能力包含度，從而

又

βi+βn-i+1=1，

則

于是知識結(jié)構(gòu)Kβi+1與Kβn-i+1(i=1,2，…,n-1)互為對偶．

例1設(shè)(Q,S,μ)為一個(gè)合取技能函數(shù)，其中

Q={q1,q2,q3,q4}，S={s1,s2,s3}，
μ(q1)={{s1,s2}}，μ(q2)={{s3}}，
μ(q3)={{s2,s3}}，μ(q4)= {{s2}}．

表1 例1中能力包含度

由表1可得，能力包含度集

表2 例1中知識狀態(tài)

3 良級的知識結(jié)構(gòu)

一個(gè)技能映射通過變精度α-模型誘導(dǎo)的所有知識結(jié)構(gòu)中不一定存在擬序空間．如例1中的兩個(gè)知識結(jié)構(gòu)都不能同時(shí)滿足交、并封閉．本節(jié)討論在滿足什么條件下，技能映射通過變精度α-模型誘導(dǎo)的所有知識結(jié)構(gòu)都是擬序空間．

Spoto等[21]指出在技能函數(shù)中，對某個(gè)問題存在專屬技能和專屬能力．

定義9[22]設(shè)(Q,S,τ)為一個(gè)技能映射．對q∈Q，若如下條件成立：

1)對所有p∈Q{q}，有s?τ(p)，

2)s∈τ(q)，

則技能s∈S稱為一個(gè)專屬技能．

定義10設(shè)(Q,S,τ)為一個(gè)技能映射．對q∈Q，若s為問題q的專屬技能，則記為s?q．

命題4設(shè)(Q,S,τ)為一個(gè)技能映射．對不同的q∈Q,q′∈Q，若τ(q)?τ(q′)，則不存在s?q．若

τ(q)?τ(q′)，τ(q′)?τ(q)，

則存在

t∈τ(q)τ(q′)，u∈τ(q′)τ(q)，

使得t?q,u?q′．

證明由定義10顯然得證．

定義11設(shè)(Q,S,τ)為一個(gè)技能映射．若τ滿足下面兩個(gè)條件：

1)至少存在一個(gè)q∈Q，有s?q，

2)存在q∈Q,q′∈Q，有

τ(q)?τ(q′)， |τ(q′)τ(q)|=1，

則稱τ為良好的技能映射．

例2設(shè)(Q,S,τ)為一個(gè)技能映射，其中

Q= {q1,q2,q3,q4,q5}，S={s1,s2,s3,s4,s5}，

τ(q1)={s2}，τ(q2)={s4}，τ(q3)={s1,s2}，

τ(q4)={s3,s4}，τ(q5)={s1,s2,s5}．

根據(jù)定義11，對?q∈Q，有s3?q4，s5?q5，且有

τ(q1)?τ(q3)?τ(q5),τ(q2)?τ(q4)．

可發(fā)現(xiàn)

|τ(q3)τ(q1)|=|τ(q5)τ(q3)|=

|τ(q4)τ(q2)|=1，

于是τ為一個(gè)良好的技能映射．

定理5設(shè)(Q,S,τ)為一個(gè)技能映射．對α∈ (0,1]，(Q,Kα)為由(Q,S,τ)通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)．(Q,Kα)為擬序空間，當(dāng)且僅當(dāng)τ為一個(gè)良好的技能映射．

于是T1∪T2誘導(dǎo)的知識狀態(tài)為

T1∩T2誘導(dǎo)的知識狀態(tài)為

若T1?T2，則

T1∩T2=?， |(T1∪T2)(T1∩T2)|>1．

若T1?T2，則

|(T1∪T2) (T1∩T2)|≥1.

不妨設(shè)

τ(q)=T1∩T2，τ(q′)=T1∪T2，

存在s∈τ(q′)τ(q),使得

|τ(q′)τ(q)|=|s|=1，

于是s?q′．

反過來，令

誘導(dǎo)的知識狀態(tài)為

于是對?K?Kα，有

∩K∈Kα, ∪K∈Kα，

故Kα為一個(gè)擬序空間．

推論4[2]任意有限的序空間是學(xué)習(xí)空間，而學(xué)習(xí)空間是良級的知識結(jié)構(gòu)．

由推論3，有如下定理6．

定理6設(shè)(Q,S,τ)為一個(gè)技能映射．對α∈ (0,1]，(Q,Kα)是由(Q,S,τ)通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)，(Q,Kα)為擬序空間當(dāng)且僅當(dāng)(Q,Kα)是良級的．

證明因?yàn)閷?τ(q)?τ(q′)，有

|τ(q′)τ(q)|=1，

則有Kq≠Kq′，于是由技能映射(Q,S,τ)通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)均是可辨識的，即(Q,Kα)是序空間．故由定理5和推論3可知，(Q,Kα)是良級的．

反之，由定理5顯然得證．

定理7設(shè)(Q,S,τ)為一個(gè)技能映射．對α∈(0,1]，(Q,Kα)是由(Q,S,τ)通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)，(Q,Kα)是良級的當(dāng)且僅當(dāng)τ是一個(gè)良好的技能映射．

證明由定理5和定理6可證．

例3設(shè)

Q={q1,q2,q3,q4}，S={s1,s2,s3,s4,s5}
τ(q1)={s2,s3}，τ(q2)={s3,s5}，
τ(q3)={s1,s2,s3}，τ(q4)={s3,s4,s5}．

通過計(jì)算可得到τ的技能包含度集為

且由技能映射(Q,S,τ)通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)分別為

K1={?,{q1},{q2},{q1,q2},{q1,q3},{q2,q4},
{q1,q2,q3},{q1,q2,q4},Q}．

可發(fā)現(xiàn)所有的知識結(jié)構(gòu)都是滿足交并封閉的，于是為良級的知識結(jié)構(gòu)．

例4設(shè)

Q={q1,q2,q3}，S={s1,s2,s3,s4,s5}，

定義技能映射τ:

τ(q1)={s1,s2,s5}，τ(q2)={s1,s3,s4}，
τ(q3)={s2,s4}．

τ的技能包含度集為

顯然，τ不滿足良好技能映射的條件2)．對α∈(βi,βi+1]，i=1,2，3,4，由τ通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)分別為

{q2,q3},Q}，

{q2,q3},Q}，

K1={?,{q1},{q2},{q3},{q1,q3},{q2,q3},Q}．

通過上述知識結(jié)構(gòu)可發(fā)現(xiàn)，由τ誘導(dǎo)的所有知識結(jié)構(gòu)中至少有一個(gè)不為擬序空間．

4 極小技能子集族與學(xué)習(xí)路徑

在現(xiàn)實(shí)生活中，不同個(gè)體具有不同的技能或能力，不同的技能或能力可能解決相同問題，于是出現(xiàn)等價(jià)的技能或能力，可根據(jù)個(gè)體的知識狀態(tài)對其下一步需要學(xué)習(xí)的技能進(jìn)行規(guī)劃．從概念認(rèn)知[23，25]的角度上看，個(gè)體學(xué)習(xí)技能是一種概念認(rèn)知更新的過程，即使在學(xué)習(xí)某個(gè)技能的過程中沒有使個(gè)體的知識狀態(tài)發(fā)生改變，但個(gè)體的認(rèn)知是有細(xì)微更新的．因此，若要對個(gè)體的學(xué)習(xí)進(jìn)行指導(dǎo)，對其技能學(xué)習(xí)的縮減和學(xué)習(xí)路徑的規(guī)劃尤為重要．

4.1 基于技能映射τ的極小技能子集族

是T的一個(gè)等價(jià)類．對任意[T]，任取一個(gè)T′∈[T]，所有T′構(gòu)成的集族Y被稱為關(guān)于技能映射τ的一個(gè)極小技能子集族．

對于技能映射(Q,S,τ)，對?q∈Q，取遍Y中元素計(jì)算得到的技能包含度集記為

對q∈Q的技能包含度集記為

顯然

D′(τ)=∪D′(τq)．

例5設(shè)(Q,S,τ)為一個(gè)技能映射，其中

Q={q1,q2,q3}，S={s1,s2,s3,s4,s5}，
τ(q1)={s1,s2}，τ(q2)={s4,s5}，τ(q3)={s2,s3}．

表3 例5中技能包含度

由表3和定義4可知，技能包含度集

對?q∈Q，有

根據(jù)定義12和表3，顯然可將2S分為21個(gè)等價(jià)類，從而關(guān)于τ的一個(gè)極小技能子集族為

Y={?,{s1},{s2},{s3},{s4},{s1,s2},{s1,s4},
{s2,s3},{s2,s4},{s3,s4},{s4,s5},{s1,s2,s3},
{s1,s2,s4},{s1,s4,s5},{s2,s3,s4},{s2,s4,s5},
{s3,s4,s5},{s1,s2,s3,s4},{s1,s2,s4,s5},
{s2,s3,s4,s5},S}．

由表4可知,技能包含度集

因此約去冗余的技能子集，對技能包含度集并不產(chǎn)生影響．根據(jù)表4和定義2，對α=βi+1,i=1,2，由技能映射τ通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)分別為

表4 例5中極小技能子集族的技能包含度

定理8設(shè)(Q,S,τ)為一個(gè)技能映射，Y為關(guān)于τ的一個(gè)極小技能子集族. 若對q∈Q，取遍Y中元素計(jì)算得到的技能包含度集為D′(τ)，則

D′(τ)=D(τ)．

即

定理9設(shè)(Q,Kα)為由技能映射(Q,S,τ)通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)，

D′(τ)={β1,β2,…,βn}

為Y的技能包含度集，其中Y為關(guān)于τ的一個(gè)極小技能子集族．對于α∈(βi,βi+1]，i=1,2，…,n-1，由τ通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)為(Q,Kα)．

于是對任意[T]，任取一個(gè)T′∈[T]，Y是由所有的T′構(gòu)成的技能子集族，α∈(βi,βi+1]，技能映射(Q,S,τ)通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)為Kα．

推論5設(shè)(Q,S,τ)為一個(gè)技能映射，則保持Kα不變的技能子集的約簡必是保持D(τ)不變的技能子集的約簡．

下面討論保持技能包含度集不變的技能子集的約簡是否是保持知識結(jié)構(gòu)不變的技能子集的約簡，二者之間是否存在一一對應(yīng)的關(guān)系．給定技能映射(Q,S,τ)，對于q∈Q，由于

于是可保持D(τq)不變，進(jìn)而保持D(τ)不變．

例如，在例5中，

[?,{s3},{s4},{s3,s4},{s4,s5},{s3,s4,s5}]，

[{s1},{s2},{s2,s4},{s2,s3},{s2,s4},{s1,s4,s5},

{s2,s3,s4},{s2,s4,s5},{s2,s3,s4,s5}]，

[{s1,s2},{s1,s2,s3},{s1,s2,s4},{s1,s2,s3,s4},

{s1,s2,s4,s5},S]，

則對任意[T]，任取一個(gè)T′∈[T]，計(jì)算所得技能包含度集的極小技能子集族為

Y1={?,{s1},{s1,s2}}，

于是

{?,{s1},{s2},{s4},{s1,s2},{s1,s3},{s4,s5}}．

因?yàn)閅中沒有包含全集S，遍歷Y中的元素，由τ確定的并不是知識結(jié)構(gòu),從而保持技能包含度集不變的技能子集的約簡并不一定是保持知識結(jié)構(gòu)不變的技能子集的約簡．

根據(jù)上述結(jié)果，下面給出尋找極小技能子集族及獲取知識結(jié)構(gòu)的算法．

算法1基于技能映射，獲取極小技能子集族及知

識結(jié)構(gòu)

輸入技能映射(Q,S,τ)

輸出關(guān)于τ的極小技能子集族Y,

知識結(jié)構(gòu)(Q,Kα)

step 1 令D(τ)=?,Y=?,Kα=?,ta=?；

step 2 計(jì)算B=2S，其中B為S的冪集；

step 3 遍歷問題集Q的問題q和S的冪集B中的元素T；

對D(τ)進(jìn)行去重并按從小到大排列；

step 5 遍歷問題集Q的問題q和S的冪集B中的元素T；

Y←Y∪(B-B(t))；

step 7 令β=D(τ)(2∶end)；

step 8 遍歷β中的元素α和Y中的元素T′；

step 10 根據(jù)上述獲得鄰接表ta并生成知識結(jié)構(gòu)圖.

算法1尋找技能映射的極小技能子集族的步驟是一個(gè)啟發(fā)式搜索過程．step 3和step 4為找到技能包含度集，step 5和step 6為獲取一個(gè)極小技能子集族，step 8～step 10為生成知識結(jié)構(gòu)．step 3和step 4的時(shí)間復(fù)雜度及空間復(fù)雜度最大為O(|Q||2S|)，step 5和step 6的時(shí)間復(fù)雜度及空間復(fù)雜度最大為O(|Q||2S|)，step 8～step 10的時(shí)間復(fù)雜度及空間復(fù)雜度最大為O(|Q||2S||Y|)．因此，算法1的最大時(shí)間復(fù)雜度和空間復(fù)雜度均為

O(|Q||2S||Y|)．

4.2 基于技能函數(shù)μ的極小技能子集族

是T的一個(gè)等價(jià)類．對任意[T]，任取一個(gè)T′∈[T]，所有T′構(gòu)成的集族M稱為關(guān)于技能函數(shù)μ的一個(gè)極小技能子集族．

設(shè)(Q,S,μ)為一個(gè)技能函數(shù)，對每個(gè)qi∈Q，取遍M中元素計(jì)算得到的能力包含度集記為

對某個(gè)問題qi∈Q的能力包含度集記為

顯然

定理10設(shè)(Q,S,μ)為一個(gè)技能函數(shù)，M為一個(gè)極小技能子集族．若對q∈Q，取遍M中元素計(jì)算得到的技能包含度集為D′(μ)，則D′(μ)=D(μ)．

證明類似于定理8即證．

定理11設(shè)(Q,Kα)是由技能函數(shù)(Q,S,μ)通過變精度α-能力模型誘導(dǎo)的知識結(jié)構(gòu)，

D′(μ)= {β1,β2,…,βn}

為M的能力包含度集，其中M為關(guān)于μ的一個(gè)極小技能子集族．對α∈(βi,βi+1]，i=1,2， …,n-1，由μ通過變精度α-能力模型誘導(dǎo)的知識結(jié)構(gòu)為(Q,Kα)．

證明類似于定理9即證．

推論6設(shè)(Q,S,μ)為一個(gè)技能函數(shù)，則保持Kα不變的技能子集的約簡必是保持D(μ)不變的技能子集的約簡，反之不成立．

基于上述結(jié)論，下面給出獲取極小技能子集族和知識結(jié)構(gòu)的算法．

算法2基于技能函數(shù)，獲取極小技能子集族和知

識結(jié)構(gòu)

輸入技能函數(shù)(Q,S,μ)

輸出關(guān)于μ的極小技能子集族M,

知識結(jié)構(gòu)(Q,Kα)

step 1 令D(μ)=?,M=?,Kα=?,ta=?；

step 2 計(jì)算B=2S，其中B為S的冪集；

step 3 遍歷每個(gè)μ(q)中的能力C和B中的元素T；

對D(μ)進(jìn)行去重并按從小到大進(jìn)行排列；

step 5 遍歷每個(gè)μ(q)中的能力C和B中的元素T；

M←M∪(B-B(U))；

step 7 令β=D(μ)(2∶end)；

step 9 根據(jù)上述步驟獲得鄰接表ta并生成知識結(jié)構(gòu)圖．

算法2尋找技能函數(shù)的極小技能子集族的步驟也是一個(gè)啟發(fā)式搜索過程．step 3和step 4為獲得一個(gè)能力包含度集，step 5和step 6為獲得一個(gè)極小技能子集族，step 8和step 9為生成知識結(jié)構(gòu)．step 3和step 4的時(shí)間復(fù)雜度及空間復(fù)雜度最大為

O(|Q′||μ(q)||2S′|)，

step 5和step 6的時(shí)間復(fù)雜度及空間復(fù)雜度最大為

O(|Q′||μ(q)||2S′|)，

step 8和step 9的時(shí)間復(fù)雜度及空間復(fù)雜度最大為

O(|Q′||μ(q)||2S′||M|)．

因此，算法2的最大時(shí)間復(fù)雜度和空間復(fù)雜度均為

O(|Q′||μ(q)||2S′||M|)．

例6設(shè)(Q,S,μ)為一個(gè)技能函數(shù)，其中，

Q= {q1,q2,q3}，S={s1,s2,s3,s4}，
μ(q1)={{s2,s4}}，μ(q2)={{s1,s3},{s2,s4}}，
μ(q3)={{s1,s2,s3},{s2,s4}}．

由表5可發(fā)現(xiàn)，

表5 例6中能力包含度

于是由step 3從2S中刪去技能子集{s3},{s2,s3},{s3,s4},{s2,s3,s4}，得到一個(gè)極小技能子集族

M={?,{s1},{s2},{s4},{s1,s2}, {s1,s3},{s1,s4},

{s2,s4},{s1,s2,s3},{s1,s2,s4},{s1,s3,s4},S}．

由M計(jì)算得到的技能包含度集

根據(jù)step 4，對于

α=βi+1,i=1,2,3,4，

技能函數(shù)μ通過變精度α-能力模型誘導(dǎo)的知識結(jié)構(gòu)分別為

4.3 技能與學(xué)習(xí)路徑選擇

定義14給定技能映射(Q,S,τ)或技能函數(shù)(Q,S,μ)．對?[Ti],[Tj]，取T′∈[Ti]，T″∈[Tj]且T′?T″，則稱T′?T″?…為有效技能學(xué)習(xí)鏈．

若個(gè)體在[{s1},{s3}]中選擇學(xué)習(xí){s1}，則在[{s1,s2},{s2,s3}]中選擇學(xué)習(xí){s1,s2}，依此類推．

根據(jù)定義14，針對個(gè)體的學(xué)習(xí)情況，可規(guī)劃個(gè)體的學(xué)習(xí)路徑，即從?到Q的一條學(xué)習(xí)路徑所需學(xué)習(xí)的技能子集都具有包含關(guān)系.

例7對于例5中的知識結(jié)構(gòu)，

K1={?,{q1},{q2},{q3},{q1,q2},{q1,q3},
{q2,q3},Q}．

根據(jù)上述描述規(guī)劃個(gè)體的學(xué)習(xí)路徑，如圖1所示.在圖中：將知識狀態(tài){q1}簡記為q1，其它知識狀態(tài)也是如此；箭頭表示知識狀態(tài)之間的包含關(guān)系，一個(gè)把知識狀態(tài)K和K′連接起來并指向K′的箭頭表示K?K′，并且不存在K″,使得K?K″?K′成立．當(dāng)從圖的左邊往右看時(shí)，它表示一種學(xué)習(xí)路徑：一個(gè)個(gè)體開始時(shí)什么都不知道，即知識狀態(tài)為?，通過某一條學(xué)習(xí)路徑可從某一狀態(tài)向另一個(gè)狀態(tài)轉(zhuǎn)移，最終可達(dá)到知識狀態(tài)Q．

(b)K1

由圖1可發(fā)現(xiàn)，同一知識結(jié)構(gòu)不管個(gè)體選擇哪條學(xué)習(xí)路徑學(xué)習(xí)，其知識狀態(tài)從?到Q所需學(xué)習(xí)的技能都是一樣的，只是學(xué)習(xí)的先后順序不一樣．因此，根據(jù)個(gè)體的學(xué)習(xí)路徑圖，可通過個(gè)體知識狀態(tài)的變化趨勢指導(dǎo)下一步需要學(xué)習(xí)的技能．

5 實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證本文兩種算法的有效性，在6個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)分析．

所有實(shí)驗(yàn)運(yùn)行環(huán)境為Windows 7操作系統(tǒng)，硬件環(huán)境為Inter(R)Core(TM) i7-6700 CPU @3.40 GHz和8.00 GB內(nèi)存，軟件環(huán)境為MATLAB(R2013a)和RStudio(1.1.463)．

5.1 實(shí)驗(yàn)數(shù)據(jù)集

從UCI數(shù)據(jù)庫(http://archive.ics.uci.edu/ml/

datasets.php)中選取Shuttle-landing-control、Adult、Lenses、StoneFlakes、Hayes、Post這6個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，具體如表6所示．

表6 實(shí)驗(yàn)數(shù)據(jù)集

表7 技能映射(Q1,S1,τ1)

表8 技能映射(Q2,S2,τ2)

表9 技能映射(Q3,S3,τ3)

表10 技能函數(shù)

表11 技能函數(shù)

表12 技能函數(shù)

5.2 實(shí)驗(yàn)結(jié)果

根據(jù)算法1，可求出每個(gè)技能映射的技能包含度和知識結(jié)構(gòu)，如表13所示．根據(jù)算法2，可求出每個(gè)技能函數(shù)的能力包含度和知識結(jié)構(gòu)，如表14所示．

表13 不同技能映射的技能包含度和知識結(jié)構(gòu)

表14 不同技能函數(shù)的能力包含度和知識結(jié)構(gòu)

由表13和表14可知，根據(jù)本文算法，技能子集得到明顯縮減．技能映射和技能函數(shù)通過極小技能子集族獲得知識結(jié)構(gòu)，相對于遍歷所有技能子集，分別減少32,4,28,32,4,88個(gè)技能子集.這不僅為求解知識結(jié)構(gòu)的過程提供很大的便利，還可根據(jù)個(gè)體的自身情況幫助其縮小學(xué)習(xí)范圍，降低大腦的存儲成本．

對于技能映射(Qi,Si,τi):當(dāng)α=β2時(shí)，由τi通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)與由τi通過析取模型誘導(dǎo)的知識結(jié)構(gòu)對應(yīng)；當(dāng)α=βn時(shí)，由τi通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)與由τi通過合取模型誘導(dǎo)的知識結(jié)構(gòu)對應(yīng)．而當(dāng)α≠β1,β2,βn時(shí)，在由τi通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)中，至少存在一個(gè)知識結(jié)構(gòu)包含Kβ2，且至少存在一個(gè)知識結(jié)構(gòu)包含于Kβn．注意，這里所說的包含均指集族之間的包含關(guān)系．例如，由τ2通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)為：

{q21,q22,q24,q25,q26,q28},{q21,q23,q24,q25,q27,q28},{q21,q24,q25,q26,q27,q28},{q22,q23,q24,q26,q27,q28},

{q23,q24,q25,q26,q27,q28},{q21,q22,q24,q25,q26,q27,q28},{q21,q23,q24,q25,q26,q27,q28},

{q22,q23,q24,q25,q26,q27,q28},Q2}，

{q22,q23,q24,q26,q27},{q21,q23,q24,q25,q27,q28},{q21,q24,q25,q26,q27,q28},{q22,q23,q24,q26,q27,q28},

{q23,q24,q25,q26,q27,q28},{q21,q22,q24,q25,q26,q27,q28},{q21,q23,q24,q25,q26,q27,q28},

{q22,q23,q24,q25,q26,q27,q28},Q}，

K1={?,{q21},{q22},{q23},{q21,q22},{q21,q25},{q22,q23},{q22,q26},{q23,q27},{q21,q23,q24},

{q21,q22,q23,q24},{q21,q22,q25,q26},{q22,q23,q26,q27},{q21,q23,q24,q25,q27,q28},Q}.

因此，變精度α-模型和變精度α-能力模型均克服誘導(dǎo)知識結(jié)構(gòu)過于寬松或苛刻的條件，使得對于不同的個(gè)體，知識結(jié)構(gòu)更合理．

為了使結(jié)果更可觀，使用(a)～(c)表示技能映射的變精度α-模型與析取模型和合取模型的關(guān)系，(d)～(f)表示技能函數(shù)的變精度α-能力模型與能力模型的關(guān)系．

由圖2可知，變精度α-模型既包含析取模型，又包含合取模型，并具有析取模型和合取模型不能誘導(dǎo)的知識結(jié)構(gòu).而變精度α-能力模型包含能力模型，并具有能力模型不能誘導(dǎo)的知識結(jié)構(gòu)．由此說明本文算法可解決文獻(xiàn)[15]中存在條件過于寬松或苛刻的問題．

圖2 不同模型下誘導(dǎo)的知識結(jié)構(gòu)中知識狀態(tài)個(gè)數(shù)

在圖3和圖4中，節(jié)點(diǎn)均表示知識狀態(tài)．圖3中節(jié)點(diǎn)“1”表示知識狀態(tài)為?，節(jié)點(diǎn)“31”表示知識狀態(tài)為Q．圖4中節(jié)點(diǎn)“1”也表示知識狀態(tài)為?，節(jié)點(diǎn)“21”表示知識狀態(tài)為Q．連接2個(gè)節(jié)點(diǎn)的邊表示大的節(jié)點(diǎn)包含小的節(jié)點(diǎn)．

圖3 τ1通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)圖

圖4 μ1通過變精度α-能力模型(α=1)誘導(dǎo)的知識結(jié)構(gòu)圖

6 結(jié) 束 語

本文將技能映射和技能函數(shù)與包含度結(jié)合，研究技能映射和技能函數(shù)誘導(dǎo)知識結(jié)構(gòu)的另一種方法,還討論技能映射在滿足什么條件時(shí)，通過變精度α-模型可誘導(dǎo)擬序空間．為了降低構(gòu)建知識結(jié)構(gòu)的復(fù)雜度，考慮對技能子集進(jìn)行約簡，得到技能集S的一個(gè)極小技能子集族．遍歷極小技能子集族中的元素，技能映射(技能函數(shù))通過變精度α-模型(變精度α-能力模型)誘導(dǎo)的知識結(jié)構(gòu)保持不變．本文提出兩種算法：1)基于技能映射，尋找極小技能子集族和生成知識結(jié)構(gòu)的算法;2)基于技能函數(shù)，尋找極小技能子集族和生成知識結(jié)構(gòu)的算法．UCI數(shù)據(jù)集上的實(shí)驗(yàn)表明對技能子集的約簡算法是可行的，這不僅使誘導(dǎo)知識結(jié)構(gòu)的復(fù)雜度得以降低，還涉及到個(gè)體技能選擇和知識評估的問題．Sun等[20]將模糊集的思想融入技能映射中，研究個(gè)體技能的熟練程度，為評估個(gè)體的知識掌握情況提供另一種思路．因此，在今后的研究中:一方面考慮把文獻(xiàn)[20]中模糊技能映射結(jié)合到本文考慮的問題中，繼續(xù)研究個(gè)體的技能選擇與知識評估的問題；另一方面將考慮技能映射通過變精度α-模型誘導(dǎo)的知識結(jié)構(gòu)中至少存在一個(gè)擬序空間的條件．