基于技能映射的知識結(jié)構(gòu)和推測關(guān)系研究

韓光明,趙 青

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

美國心理學(xué)家Doignon等[1]提出的知識空間理論（KST）是一套用于教育學(xué)和心理學(xué)的數(shù)學(xué)理論，它與粗糙集理論[2-4]的聯(lián)系十分緊密，也可以用于測試學(xué)生水平、發(fā)現(xiàn)教育規(guī)律、評價(jià)教學(xué)水平等各個(gè)方面.

Rusch 等[5]在知識空間理論和形式概念分析之間建立了有效的聯(lián)系.知識空間的研究在國外比較成熟，應(yīng)用也比較多，其中美國的在線學(xué)習(xí)和評估的計(jì)算機(jī)知識診斷系統(tǒng)ALEKS 是一個(gè)較為典型的代表.而知識空間在國內(nèi)的研究還在起步階段，高純等[6]給出在析取模式下最小技能集的生成算法，麥裕華等[7]將知識空間理論用于化學(xué)教學(xué)，李進(jìn)金等[8]綜述了知識空間和形式背景之間的聯(lián)系.

在知識空間理論中，把研究的對象的全體稱為問題域，問題域是某個(gè)領(lǐng)域里所有基本知識的集合，或者是待考察問題的全體.一個(gè)刻畫了學(xué)生當(dāng)前掌握的知識的集合被稱為知識狀態(tài)，它是問題域的子集.知識狀態(tài)表示被試個(gè)體在理想狀態(tài)下能夠完全掌握的問題集合.而知識結(jié)構(gòu)就是由知識狀態(tài)組成的，其中包括空集和全集.而推測關(guān)系是定義在知識結(jié)構(gòu)之上，它刻畫的是問題域中元素之間的一種偏序關(guān)系.

技能映射刻畫的是問題和技能之間的對應(yīng)關(guān)系，同時(shí)也是導(dǎo)出知識結(jié)構(gòu)的依據(jù).技能映射常見的模式有兩種——析取模式和合取模式.同一個(gè)技能映射，由于映射模式的不同，可以導(dǎo)出兩種不同知識結(jié)構(gòu)，這兩種知識結(jié)構(gòu)是對偶的.

本文從技能映射的兩種不同模式出發(fā)，在深入分析知識結(jié)構(gòu)和推測關(guān)系的基礎(chǔ)之上，提出了從技能映射導(dǎo)出推測關(guān)系的方法，并設(shè)計(jì)了相關(guān)的算法.

1 知識結(jié)構(gòu)和推測關(guān)系

根據(jù)知識空間理論，把要考慮的問題的全體稱為問題域，記作Q，這是一個(gè)非空的集合，知識結(jié)構(gòu)是建立在問題域Q之上的，如定義1.

定義1[1]設(shè)Q 為問題域，K 是由Q 的一些子集構(gòu)成的知識狀態(tài)集族，并且含有空集和Q，則稱(Q,K)為知識結(jié)構(gòu).特別地，當(dāng)K滿足并封閉的條件時(shí)，稱(Q,K)為知識空間.

知識結(jié)構(gòu)是知識空間里最基本的概念，在知識結(jié)構(gòu)的基礎(chǔ)上，定義的推測關(guān)系如下：

定義2[2]設(shè)(Q,K)為知識結(jié)構(gòu)，?r,q ∈Q，若滿足

其中κq={K ∈κ|q ∈K}，則稱r和q之間具有推測關(guān)系，即由q推測出r，或者r可由q推測出，記作r?q.

推測關(guān)系可以理解為，凡是含有問題q 的知識狀態(tài)里，都含有問題r，也可以理解為問題r 是比問題q更基礎(chǔ)的知識，要掌握問題q必須先掌握問題r.

顯然，知識結(jié)構(gòu)中的推測關(guān)系是一個(gè)自反，反對稱、傳遞的關(guān)系，因此，推測關(guān)系是一個(gè)偏序關(guān)系.在一個(gè)知識結(jié)構(gòu)中，任意兩個(gè)元素之間要么存在推測關(guān)系，要么不存在推測關(guān)系，可以用哈斯圖來表示元素之間的關(guān)系.可以用命題1進(jìn)一步理解推測關(guān)系.

命題1[1]設(shè)(Q,K)為知識結(jié)構(gòu)，?r,q ∈Q，若對于?K ∈K，都有

q ∈K ?r ∈K

成立，則r?q.

由一個(gè)確定的知識結(jié)構(gòu)，可以得出其中各個(gè)元素之間的推測關(guān)系，并畫出其對應(yīng)的哈斯圖.但是并不能由一個(gè)具體的推測關(guān)系（或者哈斯圖）得到一個(gè)確定的知識結(jié)構(gòu)，因?yàn)椴煌闹R結(jié)構(gòu)可能會(huì)導(dǎo)出相同的推測關(guān)系[3].

2 知識結(jié)構(gòu)與技能映射

有些情況下，知識結(jié)構(gòu)并不是直接得到的，而是由技能來刻畫的.待解決的問題也往往由一些技能來描述，如小學(xué)生掌握了乘法口訣和加法口訣，就能解決簡單的混合運(yùn)算的問題.一個(gè)程序員掌握了C 語言，或者Java語言，或者Python語言，就能解決一個(gè)編程問題.

在知識空間理論中，我們把掌握某個(gè)領(lǐng)域的知識所需技能的全體稱為技能域.技能映射可以定義如下：

定義3[2]設(shè)Q為非空問題域，S為非空技能域，τ是一個(gè)從Q到2S-{φ}的映射，則稱三元組(Q,S,τ)為一個(gè)技能映射.

技能映射有時(shí)可以用表格的形式給出，稱為Q-S表.對于特定的一個(gè)技能映射，根據(jù)兩種不同的映射模式，可以導(dǎo)出不同的知識空間，這是我們研究技能映射的目的.這兩種不同的映射模式分別為析取模式和合取模式.在析取模式中，由S的子集T確定的知識狀態(tài)K表示為

而在合取模式下，由S的子集T所確定的知識狀態(tài)K表示為

由式（2）得到的知識狀態(tài)的集合構(gòu)成的知識結(jié)構(gòu)記作K1，由式（3）得到的知識狀態(tài)的集合構(gòu)成的知識結(jié)構(gòu)記作K2，J P Doignon和J C Falmagne曾經(jīng)指出他們之間存在著對偶關(guān)系.

命題2[2]對于同一個(gè)技能映射，由析取模式所得到的知識結(jié)構(gòu)與合取模式所得到的知識結(jié)構(gòu)是對偶的.即對于任意一個(gè)K ∈K1，都有Q - K ∈K2，反之亦然.

例1 某公司有5個(gè)工作崗位，它們和5種技能之間的對應(yīng)關(guān)系如表1.

表1 某公司崗位技能的Q-S表Tab.1 Q-S table of a company working post

設(shè)Q ={a,b,c,d,e}，S ={1,2,3,4,5}，根據(jù)表1可得到映射函數(shù)τ為

顯然，此例中的(Q,S,τ)是一個(gè)技能映射.如果崗位所要求的技能是只要滿足一條即可勝任，則在生成知識結(jié)構(gòu)時(shí)應(yīng)使用析取模式，反之，如果崗位要求的每條技能都必須滿足才能勝任，則在生成知識結(jié)構(gòu)時(shí)應(yīng)使用合取模式.

根據(jù)式（2）和式（3）分別計(jì)算在析取模式下得到的知識結(jié)構(gòu)(Q,K1)和在合取模式下得到的知識結(jié)構(gòu)(Q,K2)如

可以明顯看出，這兩個(gè)知識結(jié)構(gòu)是對偶的，而這兩個(gè)知識結(jié)構(gòu)所確定的推測關(guān)系可以根據(jù)定義2 得到，分別用哈斯圖表示，如圖1所示.

圖1 兩種模式下技能映射得到的知識結(jié)構(gòu)的哈斯圖Fig.1 Hass diagram of the knowledge structure from skill mapping in two models

一個(gè)技能映射(Q,S,τ )，可能和另一個(gè)(Q,S′,τ′)具有相同的知識結(jié)構(gòu)，如果滿足S′?S，且對任意的t ∈Q，τ′(t)= τ(t)?S′，若(Q,S′,τ′)導(dǎo)出的知識結(jié)構(gòu)和(Q,S,τ)導(dǎo)出的知識結(jié)構(gòu)相同，則稱技能映射(Q,S′,τ′)為技能映射(Q,S,τ)的一個(gè)協(xié)調(diào)集，若不存在比S′更小的這樣的集合，則稱技能映射(Q,S′,τ′)為技能映射(Q,S,τ)的一個(gè)約簡，此時(shí)也稱S′為S的最小技能集[6].

定理1 設(shè)K1,K2是對偶的知識結(jié)構(gòu)，則它們的推測關(guān)系的排序是相反的，即對任意的q1,q2∈Q，若在K1中存在推測關(guān)系q1?q2，則在K2中存在推測關(guān)系q2?q1.

證明 對于任意的q1,q2∈Q，在K1中存在推測關(guān)系q1?q2，根據(jù)命題1，則對于任意的K ∈K1，若q2∈K，則q1∈K.因而，若q1?K，則q2?K.即若q1∈Q - K，則q2∈Q - K，由K 的任意性得，Q - K 也是任意的且Q - K ∈K2.由命題1可得，在K2中存在推測關(guān)系q2?q1.

推論1 設(shè)(Q,S,τ)是一個(gè)技能映射，對于任意的q1,q2∈Q，若在析取模式下有q1?q2，則在合取模式下必然有q2?q1成立.反之亦然.

推論1 表明，同一個(gè)技能映射在析取模式下得到的推測關(guān)系與其在合取模式下得到的推測關(guān)系的排序是相反的，其哈斯圖也是互相倒立的，正如圖1所示的效果.

3 技能映射導(dǎo)出的推測關(guān)系與相關(guān)算法研究

從技能映射出發(fā)，構(gòu)造出知識結(jié)構(gòu)，進(jìn)而得到問題域中各元素之間的推測關(guān)系，從而可以更加直觀了解問題域中各元素之間的強(qiáng)弱性、重要性、順序性等.但是，過程比較復(fù)雜而且繁瑣.

3.1 技能映射導(dǎo)出的推測關(guān)系

由命題2，在由技能映射導(dǎo)出一個(gè)知識結(jié)構(gòu)的同時(shí)，可以直接得到另一個(gè)知識結(jié)構(gòu)，這樣可能會(huì)減少一半左右的計(jì)算量，但在實(shí)際應(yīng)用中，可能只需要計(jì)算一種模式，因此這種計(jì)算量的減少顯得沒有意義，即使只在一種模式下導(dǎo)出知識結(jié)構(gòu)，其計(jì)算量也是相當(dāng)大的，如在技能映射(Q,S,τ)中，若|Q| = m，|S| = n，則在導(dǎo)出知識結(jié)構(gòu)時(shí)，其算法的時(shí)間復(fù)雜度為2nm，當(dāng)S的規(guī)模比較大時(shí)，計(jì)算量是相當(dāng)龐大的.但由于從技能映射導(dǎo)出知識結(jié)構(gòu)的算法比較復(fù)雜，因此如果要得到知識結(jié)構(gòu)并且分析知識結(jié)構(gòu)里各個(gè)問題之間的推測關(guān)系就更復(fù)雜了.而定理2 可以跳過生成知識結(jié)構(gòu)的步驟，直接由技能映射函數(shù)得到Q 中元素的推測關(guān)系.

定理2 設(shè)(Q,S,τ)是一個(gè)技能映射，

1)若(Q,K1)是其在析取模式下得到的知識結(jié)構(gòu)，則對于?p,q ∈Q，若τ(p)?τ(q)，則有q ?p;

2)若(Q,K2)是其在合取模式下得到的知識結(jié)構(gòu)，則對于?p,q ∈Q，若τ(p)?τ(q)，則有p ?q.

證明1）設(shè)T 為S 的任意一個(gè)非空子集，K 為T 在析取模式下得到對應(yīng)的知識狀態(tài)，若?p ∈K，由式（2）可得，τ(p)?T ≠φ，又因?yàn)棣?p)?τ(q)，故τ(q)?T ≠φ，因此q ∈K.根據(jù)命題1可得，q ?p.

同理可證2）.

定理2 可以直接從技能映射函數(shù)之間的包含關(guān)系得出知識點(diǎn)之間的推測關(guān)系，省去了由技能映射導(dǎo)出知識結(jié)構(gòu)的復(fù)雜計(jì)算過程，只需要確定映射模式即可，確定了推測關(guān)系，就可以進(jìn)行學(xué)習(xí)路徑的探討.

事實(shí)上，定理2的逆命題也是成立的，這里不再贅述，因?yàn)樵趯?shí)際應(yīng)用中，人們往往需要由技能映射得到推測關(guān)系而不是相反.

在同一個(gè)技能映射背景下，若有τ(p)?τ(q)關(guān)系成立，則在兩種不同的映射模式下得到排序完全相反的推測關(guān)系，這也是我們看到圖1的兩幅上下顛倒的圖的原因所在.在理論研究中，析取模式涉及的較多，但是在實(shí)際應(yīng)用中，合取模式更常見，招聘、招生、評委打分等各種情況使用的大多數(shù)都是合取模式.

例2 在例1 中，由映射函數(shù)可以直接發(fā)現(xiàn)Q 中元素的推測關(guān)系，如在合取模式下，由于τ(b)={1,2,4}，τ(d)={1,4}，很容易得到d ?b.

用同樣的方法可得，d ?c，d ?a，b ?a，b ?c，c ?a，e ?a 等推測關(guān)系的存在，然后根據(jù)這些推測關(guān)系，繪制出哈斯圖，其結(jié)果和例1中的圖1（2）完全一致.而在析取模式下，得到的是排序完全相反的結(jié)果，也與例1中的圖1（1）完全一致.

推論2 設(shè)(Q,S,τ)是一個(gè)技能映射，q1,q2∈Q,若τ(q1)= τ(q2),則q1= q2.

證明 根據(jù)τ(q1)= τ(q2)，即τ(q1)?τ(q2)和τ(q1)?τ(q2)同時(shí)成立，在兩種映射模式下，都有q1?q2和q2?q1同時(shí)成立，由推測關(guān)系的反對稱性可得q1= q2.

推論2說明，在確定的技能映射模式下，只要問題所要求的技能是一樣的，那么問題就是一樣的，或者說是等效的.反映在Q-S 表中，沒有完全相同的兩行，或者說，如果有完全相同的兩行，則應(yīng)該合并為一行.在實(shí)際應(yīng)用中，由于Q-S 表可能由人們根據(jù)經(jīng)驗(yàn)得來，也可能由一些數(shù)據(jù)分析得來，難免會(huì)出現(xiàn)完全相同的行，可以根據(jù)推論2 進(jìn)行初步的去冗余，即刪除或者合并相同的行.值得注意的是，在現(xiàn)代關(guān)系型數(shù)據(jù)庫中，也沒有完全相同的兩行（即元組），這和推論2的結(jié)論是一致的.

3.2 技能映射導(dǎo)出推測關(guān)系的算法

定理2給出了從技能映射得到推測關(guān)系的思路，根據(jù)這個(gè)思路可以設(shè)計(jì)出如下的推測關(guān)系算法（以析取模式為例），

步驟1：列出Q 中所有元素q 的映射函數(shù)τ(q)，并根據(jù)映射函數(shù)的值對Q 中元素進(jìn)行排序，即所含元素個(gè)數(shù)較多的排在前，較少的排在后面，一樣多的順序任意.

步驟2：從排序后的第2 個(gè)元素開始，每個(gè)元素與它前面的所有元素逐一比較它們的函數(shù)值，若有包含關(guān)系，則根據(jù)定理2，這兩個(gè)元素存在推測關(guān)系，將他們記錄下來.

步驟3：重復(fù)步驟2，直至結(jié)束.

根據(jù)以上思路設(shè)計(jì)算法1.

輸入Q，S，τ，并根據(jù)τ將Q中元素排序

例3 用算法1計(jì)算前面例1在析取模式下的推測關(guān)系，步驟如表1.

表1 推測關(guān)系的計(jì)算步驟Tab.1 Calculation steps of surmise relation

表1 右側(cè)就是由技能映射(Q,S,τ)得到的所有推測關(guān)系，由此也很容易畫出該推測關(guān)系的哈斯圖，與圖1完全一致.

該算法是基于析取模式的，稍作修改就可以作為合取模式下的算法.其算法的復(fù)雜度為排序時(shí)間復(fù)雜度和導(dǎo)出推測關(guān)系復(fù)雜度之和，即o(n2).

4 結(jié)論

知識結(jié)構(gòu)是比知識空間更為一般的數(shù)學(xué)概念，在實(shí)際應(yīng)用中也更常見.在特定的前提下，知識結(jié)構(gòu)可以轉(zhuǎn)化為知識空間.研究發(fā)現(xiàn)，技能映射和知識結(jié)構(gòu)的推測關(guān)系之間也存在著較為直接的聯(lián)系，這為研究和探索知識空間的理論及其應(yīng)用提供了一種新的思路和方向.