技能映射下知識(shí)空間基的矩陣算法

韓光明，周銀鳳

（閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，福建漳州363000）

知識(shí)空間理論[1](Knowledge Space Theory，簡(jiǎn)稱KST)是由比利時(shí)的數(shù)學(xué)心理學(xué)家Doignon 與美國(guó)數(shù)學(xué)家Falmagne 于1985年提出的一種數(shù)學(xué)理論，該理論用于評(píng)估學(xué)生對(duì)某一領(lǐng)域的知識(shí)的學(xué)習(xí)過(guò)程和認(rèn)知水平，從而指導(dǎo)學(xué)生的學(xué)習(xí)過(guò)程和學(xué)習(xí)路徑.

知識(shí)空間理論已經(jīng)成為了測(cè)試系統(tǒng)和自適應(yīng)教學(xué)中最有效的知識(shí)表示理論[2]，而且在計(jì)算機(jī)輔助教學(xué)中也得到了廣泛應(yīng)用，其中的Aleks軟件系統(tǒng)是KST理論的一個(gè)影響較大的應(yīng)用[3].Rusch等[4]將知識(shí)空間理論與形式概念分析相結(jié)合，并建立了有效的聯(lián)系.

在國(guó)內(nèi)知識(shí)空間理論也有一些應(yīng)用，比如孫波等[5]研究的基于擴(kuò)展知識(shí)空間理論的自適應(yīng)測(cè)評(píng)過(guò)程并對(duì)測(cè)評(píng)過(guò)程進(jìn)行了優(yōu)化，周深等[6]提出了快速自適應(yīng)測(cè)試過(guò)程，麥裕華等[7-8]將知識(shí)空間理論應(yīng)用于化學(xué)教學(xué).

知識(shí)空間的一個(gè)最重要的概念是它的基[9]，李進(jìn)金等[10]稱之為知識(shí)基，它包含了知識(shí)空間的所有信息，由知識(shí)基可以生成整個(gè)知識(shí)空間.1993年，Dowling[2]給出了由知識(shí)空間求知識(shí)基的方法.1999年，Doignon[9]受到該算法的啟發(fā)，給出了由知識(shí)基計(jì)算知識(shí)空間的方法.2011年，F(xiàn)almagne等[11]將Dowling 的算法進(jìn)行了改進(jìn)，計(jì)算效率提高了10%～30%.

根據(jù)知識(shí)空間理論，知識(shí)是用問(wèn)題來(lái)表示的，將某學(xué)科領(lǐng)域問(wèn)題的全體稱為問(wèn)題域[9].知識(shí)域中的問(wèn)題可以通過(guò)某些技能來(lái)解決，技能映射刻畫(huà)了問(wèn)題和技能之間的對(duì)應(yīng)關(guān)系，通過(guò)技能映射可以構(gòu)造知識(shí)結(jié)構(gòu)，特別的，一個(gè)給定的技能映射在析取模式下可以生成一個(gè)知識(shí)空間[9].

在保持知識(shí)空間不變的情況下，技能也可能會(huì)有冗余，此時(shí)可以對(duì)技能集進(jìn)行約簡(jiǎn)，即在原技能集的基礎(chǔ)上，約去一些不必要技能，在析取模式下可以生成同樣的知識(shí)空間，也就是說(shuō)在保持生成的知識(shí)空間不變的情況下，對(duì)技能集進(jìn)行約簡(jiǎn).約簡(jiǎn)后的技能集稱為極小技能集，而極小技能集是不唯一的.高純等[12]在極小技能集方面進(jìn)行了一些研究.

本文以布爾矩陣為研究工具，提出了布爾向量的投影和知識(shí)狀態(tài)的特征向量等概念，研究基于技能映射的知識(shí)空間的知識(shí)基及其算法.

1 知識(shí)空間、知識(shí)基與技能映射

在知識(shí)空間的理論中，問(wèn)題域Q是要考慮的問(wèn)題的全體，且Q是一個(gè)非空的集合.

定義1[2]學(xué)生在理想情況下能夠正確回答問(wèn)題域Q中的一些問(wèn)題所構(gòu)成的集合稱為一個(gè)知識(shí)狀態(tài)，記為K.顯然，K?Q.

定義2[9]設(shè)Q為問(wèn)題域，若知識(shí)狀態(tài)的集族包含空集和全集Q，則稱(Q，)為知識(shí)結(jié)構(gòu).特別地，當(dāng)滿足并封閉時(shí)，稱二元組(Q，)為知識(shí)空間，或稱為Q上的知識(shí)空間，在不引起歧義的情況下，簡(jiǎn)稱為知識(shí)空間.

一般情況下，Q是有限的.本文所述的知識(shí)空間及其問(wèn)題域均為有限的.

定義3[9]設(shè)為集族，若′是包含中所有有限個(gè)元素的并組成的集合，則稱集族′是的擴(kuò)張，記為S()=′，或稱擴(kuò)張成′.

在有限知識(shí)空間中，存在一組非空子集族，這些子集族通過(guò)并運(yùn)算可以生成整個(gè)知識(shí)空間，我們把最小的這組子集族稱為知識(shí)空間的基.

定義4[9]設(shè)為知識(shí)空間，若? 是可以擴(kuò)張的最小子集族，則稱? 為知識(shí)空間的基，簡(jiǎn)稱知識(shí)基，把基中的知識(shí)狀態(tài)稱為原子.

特別需要說(shuō)明的是，空集不是原子，另外，原子最開(kāi)始的概念是基于問(wèn)題的，即某個(gè)問(wèn)題的原子，而所有問(wèn)題的原子組成的集合就是知識(shí)基，這里把原子的定義推廣到只要是基中的知識(shí)狀態(tài)就是原子，而不再關(guān)心它是哪個(gè)問(wèn)題的原子，這并不改變?cè)拥膬?nèi)涵.

Falmagne 等[9]指出，有限知識(shí)空間的知識(shí)基存在且唯一.知識(shí)基的重要程度是顯然的，它可以完全確定一個(gè)知識(shí)空間，也就是說(shuō)，一個(gè)知識(shí)空間與它的基是一一對(duì)應(yīng)的.

知識(shí)空間的構(gòu)建方法有很多，1994年，Albert[13-14]提出了一種由問(wèn)題系統(tǒng)構(gòu)建知識(shí)空間的方法，隨后Albert 等[15]又從理論出發(fā)到實(shí)際應(yīng)用，系統(tǒng)地研究了知識(shí)空間.事實(shí)上，知識(shí)空間可以由領(lǐng)域?qū)＜医o出，也可以由大數(shù)據(jù)分析得出，也可以由下面的技能映射導(dǎo)出.

定義5[9]假設(shè)Q為非空的問(wèn)題域，S為非空技能域，τ：Q→2S{?}，則稱三元組(Q，S，τ)為一個(gè)技能映射.

技能映射可以用Q-S表的形式給出，表1的元素一般用0和1表示.

Falmagne 等[11]指出，對(duì)于特定的一個(gè)技能映射，根據(jù)兩種不同的映射模式（析取模式和合取模式）可以導(dǎo)出兩種不同的知識(shí)結(jié)構(gòu)，而且，在析取模式下導(dǎo)出的知識(shí)結(jié)構(gòu)一定是知識(shí)空間.在此模式下，由S的子集T所確定的知識(shí)狀態(tài)KT表示為：

當(dāng)T取遍S所有的子集（包括空集和S），我們就獲得了一個(gè)由技能映射在析取模式下導(dǎo)出的知識(shí)結(jié)構(gòu)，記作K(Q，S，τ)，F(xiàn)almagne等已經(jīng)證明了這個(gè)知識(shí)結(jié)構(gòu)是并封閉的，即K(Q，S，τ)為知識(shí)空間.在(Q，S，τ)明確的情況下，將該知識(shí)空間簡(jiǎn)記為.

例1設(shè)Q={q1，q2，q3，q4}，S={s1，s2，s3，s4，s5}，定義映射τ:Q→2S{?} 為：τ(q1)={s2，s3，s5} ，τ(q2)={s1，s4，s5} ，τ(q3)={s2，s5} ，τ(q4)={s3} .

技能映射的Q-S表見(jiàn)表1.

表1 技能映射的Q-S表Tab.1 Q-S table of skill mapping

根據(jù)定義5，(Q，S，τ)是一個(gè)技能映射，在析取模式下，S的每一個(gè)子集根據(jù)式（1）都可以得到一個(gè)知識(shí)狀態(tài)，這些所有的知識(shí)狀態(tài)就組成了一個(gè)滿足并封閉且包括了空集和全集在內(nèi)的知識(shí)空間，即

按照Dowling[2]的知識(shí)基的算法，可計(jì)算出該空間的知識(shí)基為：

2 技能映射的布爾矩陣、布爾向量

定義6向量的所有分量ai都取布爾值0或1，則稱向量α為布爾向量.設(shè)α、β都是n維布爾向量，其中，，則它們的布爾和為：

可見(jiàn)，兩個(gè)n維布爾向量的布爾和仍然是n維布爾向量.本文中布爾向量的加法均指的是布爾和.

定義7設(shè)n維列向量組α1，α2，…，αm，β，若存在一組不全為0的布爾值k1，k2，…，km，使得

則稱β由α1，α2，…，αm布爾表示.若n維列向量組α1，α2，…，αm中任意一個(gè)向量不能由其他向量布爾表示，則稱向量組α1，α2，…，αm布爾無(wú)關(guān)，否則稱該向量組布爾相關(guān).

n維列向量β可由向量組α1，α2，…，αm布爾表示當(dāng)且僅當(dāng)β可表示為向量組α1，α2，…，αm中若干個(gè)向量的布爾和.

定義8設(shè)(Q，S，τ)為技能映射，其中Q={q1，q2，…，qn}，S={s1，s2，…，sk}，則技能映射的布爾矩陣定義為：

根據(jù)技能映射的性質(zhì)，在矩陣M里，沒(méi)有零行和零列.把該矩陣的列向量記作α1，α2，…，αk，顯然這些都是n維布爾向量，此時(shí)矩陣M可由列向量表示為：

我們把α1，α2，…，αk中所有不重復(fù)的向量取出來(lái)，組成一個(gè)布爾向量的集合，記作ΑM.顯然，這里有|ΑM|≤|S|.

例2例1中的技能映射(Q，S，τ)的布爾矩陣為：

定義9 設(shè)問(wèn)題域Q={q1，…，qn} ，n維布爾向量則向量α在Q上的投影Γ為：

在不引起歧義的情況下，ΓQ(α)可簡(jiǎn)記為Γ(α)，另外，這里引入記號(hào)ΓΑM，ΓΑM表示ΑM中所有布爾列向量在Q上的投影的集合，顯然有ΓΑM?2Q，且|ΓΑM|≤|S|.

定義10 設(shè)問(wèn)題域Q={q1，…，qn} ，對(duì)于?K?Q，則K的特征向量定義為：

根據(jù)定義10，一個(gè)n維向量在Q上的投影，就是Q的一個(gè)子集.而Q的任意子集的特征向量是一個(gè)布爾向量，而且關(guān)系可以由定理1進(jìn)行描述.

定理1設(shè)α，β都是任意的n維布爾向量，問(wèn)題域Q={q1，…，qn} ，對(duì)?K，L?Q，則有以下性質(zhì)成立：

1)ΛΓ(α)=α且Γ(ΛK)=K；

2)Γ(α+β)=Γ(α)?Γ(β)且ΛK?L=ΛK+ΛL；

3)α=β?Γ(α)=Γ(β)且K=L?ΛK=ΛL.

這些性質(zhì)根據(jù)定義7-10很容易得到證明.

3 知識(shí)基的判定定理

由定理1可以看出求特征向量和投影是一對(duì)互逆的運(yùn)算，下面將這兩個(gè)運(yùn)算加入到技能映射之中去，可以得出以下結(jié)論.

引理1設(shè)(Q，S，τ)是技能映射，T1，T2?S，則它們導(dǎo)出的知識(shí)狀態(tài)滿足

證明根據(jù)式（1），有

所以，KT1?KT2={q|τ(q)?T1≠?或τ(q)?T2≠?}.即KT1?KT2={q|τ(q)?(T1?T2≠?}=KT1?T2.

引理2設(shè)(Q，S，τ)為技能映射，M是(Q，S，τ)的布爾矩陣，ΑM是M的列向量的集合，則所有布爾列向量在Q上的投影都是由(Q，S，τ)導(dǎo)出的知識(shí)空間里的知識(shí)狀態(tài).即ΓΑM?.

證明對(duì)于?α∈ΑM，顯然?s∈S，使得當(dāng)T={s}時(shí)，有Γ(α)=KT∈K.

事實(shí)上，ΓΑM是由S的單點(diǎn)子集{si}按式（1）導(dǎo)出的所有知識(shí)狀態(tài)的集合.可見(jiàn)，ΑM里每個(gè)向量的投影都是的一個(gè)知識(shí)狀態(tài)，而中的知識(shí)狀態(tài)不一定都是ΑM里向量的投影，它們的關(guān)系如引理3所述.

引理3設(shè)(Q，S，τ)為技能映射，則由(Q，S，τ)導(dǎo)出的知識(shí)空間里的任意一個(gè)知識(shí)狀態(tài)K，都可由ΓΑM里的元素通過(guò)并運(yùn)算得到.

證明根據(jù)式（1），對(duì)于任意的知識(shí)狀態(tài)，存在一個(gè)T={st1，st2，…，stj}?S，使得

又因?yàn)門(mén)={st1}∪{st2}∪…∪{stj}，則根據(jù)引理1，有

根據(jù)定理1 的性質(zhì)2，與引理3 等價(jià)的結(jié)論是：知識(shí)空間里的任意一個(gè)知識(shí)狀態(tài)的特征向量，等于ΑM里的若干列向量的布爾和，即可由ΑM里的列向量布爾表示.

定理2設(shè)(Q，S，τ)是技能映射，M是(Q，S，τ)的布爾矩陣，ΑM是M的列向量的集合，若? 是由(Q，S，τ)導(dǎo)出的知識(shí)空間的基，則? ?ΓΑM.

證明根據(jù)引理3，知識(shí)空間里的任意一個(gè)知識(shí)狀態(tài)，都可由ΓΑM里的元素通過(guò)并運(yùn)算得到.根據(jù)引理2，ΓΑM?，又因?yàn)樵谟邢拗R(shí)空間中，基存在且唯一，則根據(jù)基的定義，對(duì)于任意B??，有B∈ΓΑM成立.

定理2 表明，就技能映射導(dǎo)出的知識(shí)空間而言，其知識(shí)基的原子只存在于布爾矩陣列向量的投影中，這大大縮小了知識(shí)基的尋找范圍，就效率而言，其意義是顯然的.

根據(jù)定理2，我們有式（4）成立：

由于知識(shí)狀態(tài)和它的特征向量是一一對(duì)應(yīng)的關(guān)系，因此定理2也可以敘述如下.

定理2' 設(shè)(Q，S，τ)是技能映射，M是(Q，S，τ)的布爾矩陣，ΑM是M的列向量的集合，若? 是由(Q，S，τ)導(dǎo)出知識(shí)空間的基，則對(duì)于基中任意原子B??，有ΛB∈ΑM.

根據(jù)定理2，基的原子就存在于ΓΑM之中，那么ΓΑM中的知識(shí)狀態(tài)是不是都是原子呢？答案是否定的，但是我們可以根據(jù)定理3來(lái)判斷ΓΑM中哪些是原子，哪些不是原子.

定理3設(shè)(Q，S，τ)是技能映射，M是(Q，S，τ)的布爾矩陣，ΑM是M的列向量的集合，則ΓΑM中任意知識(shí)狀態(tài)是基?中的原子當(dāng)且僅當(dāng)它的特征向量不能由ΑM中其他列向量布爾表示.

證明在這里，只需證明其逆否命題即可，即證在ΓΑM中任意知識(shí)狀態(tài)不是基? 中的原子當(dāng)且僅當(dāng)它的特征向量能由ΑM中其他列向量布爾表示.

設(shè)?B∈ΑM，存在一組原子B1，B2，…，Bt，若B??，則有B=B1?B2?…?Bt，根據(jù)定理1 的性質(zhì)2 和性質(zhì)3，可得：

由定理2'可知，ΛBi∈ΑM，故B的特征向量被ΑM中其他列向量布爾表示.

定理3 就是知識(shí)空間的基的判定定理.根據(jù)定理3，可以確定在布爾矩陣的列向量中，哪些是基中原子的特征向量，哪些不是基中原子的特征向量，這樣就可以把知識(shí)基完全確定下來(lái).

根據(jù)定理2，有 |? |≤|ΓΑM|=|ΑM|≤|S|.

推論1設(shè)? 是由技能映射(Q，S，τ)導(dǎo)出的知識(shí)空間的基，則? 中原子的個(gè)數(shù)不超過(guò)技能的個(gè)數(shù)，即|?|≤|S|.

4 知識(shí)基的算法

若一個(gè)由技能映射(Q，S，τ)導(dǎo)出的知識(shí)空間為，根據(jù)定理3，可由該技能映射的Q-S表得到它的布爾矩陣，并由此得出其布爾列向量集合，只需求出這個(gè)集合中布爾無(wú)關(guān)的向量組，就可以在不計(jì)算的情況下確定的知識(shí)基.

其計(jì)算步驟和流程圖見(jiàn)圖1.

算法1知識(shí)基的計(jì)算步驟

step1 輸入Q、S和τ，根據(jù)定義8，計(jì)算該技能映射的布爾矩陣M，并求出該布爾矩陣的向量集ΑM；

step2 根據(jù)定義7，判斷ΑM中所有布爾向量是否布爾無(wú)關(guān)，若不是，轉(zhuǎn)向step 3，若是，轉(zhuǎn)向step 4；

step3 從ΑM找到一個(gè)可以由其他向量布爾表示的向量，將該向量從ΑM中刪除，轉(zhuǎn)向step 2；

step4 此時(shí)的向量集ΑM已經(jīng)變成一個(gè)布爾無(wú)關(guān)的向量集，記作Α′M.將Α′M中所有的向量一一投影到問(wèn)題集Q上，所得到的知識(shí)狀態(tài)的集合?即為知識(shí)空間的基.算法結(jié)束.

例3在例2 中，ΑM={α1，α2，α3，α5}，其中α5=α1+α2，而α1，α2，α3是布爾無(wú)關(guān)的布爾向量，據(jù)此，我們可以判定Γ(α5)不是基中的原子，而Γ(α1)和Γ(α2)，Γ(α3)是基中的原子，而且是全部的原子.因此，由例1中的技能映射(Q，S，τ)所確定的知識(shí)空間的基為：

這個(gè)結(jié)果和例1 中的結(jié)果是相同的，因?yàn)橹R(shí)基是唯一的，但是本算法的步驟和過(guò)程比例1 更為簡(jiǎn)便，如圖1.

圖1 知識(shí)基的算法流程圖Fig.1 Algorithm flow diagram of knowledge

5 極小技能集

根據(jù)前文所述，技能映射(Q，S，τ)的布爾矩陣Mn×k和向量集AM之間，有｜ΑM｜≤｜S｜＝k成立，若M中沒(méi)有完全相同的兩列，則｜ΑM｜＝｜S｜.此時(shí)，執(zhí)行算法1，會(huì)得到一個(gè)布爾無(wú)關(guān)的向量集A'M，而該向量集是原布爾矩陣M的列向量集的子集，此時(shí)找到A'M中每個(gè)列向量在矩陣M中的位置，進(jìn)而找到其對(duì)應(yīng)的技能s，這些技能s組成的集合即為極小技能集.其計(jì)算過(guò)程如算法2.

算法2技能映射極小技能集算法

step 1 輸入Q，S和τ，根據(jù)定義8，計(jì)算該技能映射的布爾矩陣M，將矩陣M用布爾列向量表示為：M=(α1，α2，…，αk)；

step 2 對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，比較αi是否存在兩兩相同的情況，若有，舍棄其中一個(gè)，直到M中所有列向量彼此不同，此時(shí)將這些列向量記作AM；

step 3 執(zhí)行算法1里的step 2和step 3，得到布爾無(wú)關(guān)的向量組；

step 4此時(shí)將該向量組中的每個(gè)向量和原矩陣M進(jìn)行逐一比較，對(duì)任意的αi∈AM，若αi?A'M，則si為可約技能，將其從技能集S中約去；

step 5 最終得到的S為極小技能集.算法結(jié)束.

該算法可以求出極小技能集，且這里得到的極小技能集并不是唯一的.因?yàn)樵趕tep 2 的預(yù)處理時(shí)，對(duì)于相同的多個(gè)αi，只保留一個(gè).而保留哪一個(gè)舍棄哪一個(gè)，在實(shí)際操作中，應(yīng)該要根據(jù)其對(duì)應(yīng)的技能的重要性來(lái)確定.

例4例1中的技能映射(Q,S,τ)的技能集S是否存在可約去的技能？我們將例1中的布爾矩陣列向量記作α1,α2,α3,α4,α5，通過(guò)例2 和例3 已經(jīng)發(fā)現(xiàn)α1=α4，而且α5=α1+α2.因此，可以把α4和α5從AM中刪除，AM中剩下布爾無(wú)關(guān)的向量α1,α2,α3.它們對(duì)應(yīng)的技能為s1,s2,s3，因此可以說(shuō)技能集{s1,s2,s3}為原技能映射的極小技能集.這里因?yàn)棣?=α4，故技能集{s2,s3,s4}也是例1中技能映射在保存其知識(shí)空間不變的情況下的極小技能集.至于在實(shí)際操作中使用哪一個(gè)極小技能集，這要看這些技能所代表的具體技能，再兼顧方便和實(shí)用性進(jìn)行取舍.

6 結(jié)語(yǔ)

本文對(duì)知識(shí)基的判定是建立在技能映射的基礎(chǔ)之上，定理3不但可以用來(lái)對(duì)知識(shí)基進(jìn)行判定，也可以在計(jì)算出知識(shí)基的情況下反過(guò)來(lái)對(duì)技能集進(jìn)行約簡(jiǎn).另外，本文所研究的算法也可以根據(jù)一個(gè)知識(shí)空間來(lái)導(dǎo)出某個(gè)技能映射，此時(shí)導(dǎo)出的技能映射的技能集可以是極小技能集，當(dāng)然，也可以在保持知識(shí)基不變的前提下，適當(dāng)添加滿足實(shí)際需要的技能.