基于技能映射的知識結構和推測關系研究

韓光明,趙 青

（閩南師范大學數學與統計學院，福建漳州363000）

美國心理學家Doignon等[1]提出的知識空間理論（KST）是一套用于教育學和心理學的數學理論，它與粗糙集理論[2-4]的聯系十分緊密，也可以用于測試學生水平、發現教育規律、評價教學水平等各個方面.

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

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

技能映射刻畫的是問題和技能之間的對應關系，同時也是導出知識結構的依據.技能映射常見的模式有兩種——析取模式和合取模式.同一個技能映射，由于映射模式的不同，可以導出兩種不同知識結構，這兩種知識結構是對偶的.

本文從技能映射的兩種不同模式出發，在深入分析知識結構和推測關系的基礎之上，提出了從技能映射導出推測關系的方法，并設計了相關的算法.

1 知識結構和推測關系

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

定義1[1]設Q 為問題域，K 是由Q 的一些子集構成的知識狀態集族，并且含有空集和Q，則稱(Q,K)為知識結構.特別地，當K滿足并封閉的條件時，稱(Q,K)為知識空間.

知識結構是知識空間里最基本的概念，在知識結構的基礎上，定義的推測關系如下：

定義2[2]設(Q,K)為知識結構，?r,q ∈Q，若滿足

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

推測關系可以理解為，凡是含有問題q 的知識狀態里，都含有問題r，也可以理解為問題r 是比問題q更基礎的知識，要掌握問題q必須先掌握問題r.

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

命題1[1]設(Q,K)為知識結構，?r,q ∈Q，若對于?K ∈K，都有

q ∈K ?r ∈K

成立，則r?q.

由一個確定的知識結構，可以得出其中各個元素之間的推測關系，并畫出其對應的哈斯圖.但是并不能由一個具體的推測關系（或者哈斯圖）得到一個確定的知識結構，因為不同的知識結構可能會導出相同的推測關系[3].

2 知識結構與技能映射

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

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

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

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

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

由式（2）得到的知識狀態的集合構成的知識結構記作K1，由式（3）得到的知識狀態的集合構成的知識結構記作K2，J P Doignon和J C Falmagne曾經指出他們之間存在著對偶關系.

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

例1 某公司有5個工作崗位，它們和5種技能之間的對應關系如表1.

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

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

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

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

可以明顯看出，這兩個知識結構是對偶的，而這兩個知識結構所確定的推測關系可以根據定義2 得到，分別用哈斯圖表示，如圖1所示.

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

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

定理1 設K1,K2是對偶的知識結構，則它們的推測關系的排序是相反的，即對任意的q1,q2∈Q，若在K1中存在推測關系q1?q2，則在K2中存在推測關系q2?q1.

證明 對于任意的q1,q2∈Q，在K1中存在推測關系q1?q2，根據命題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中存在推測關系q2?q1.

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

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

3 技能映射導出的推測關系與相關算法研究

從技能映射出發，構造出知識結構，進而得到問題域中各元素之間的推測關系，從而可以更加直觀了解問題域中各元素之間的強弱性、重要性、順序性等.但是，過程比較復雜而且繁瑣.

3.1 技能映射導出的推測關系

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

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

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

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

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

同理可證2）.

定理2 可以直接從技能映射函數之間的包含關系得出知識點之間的推測關系，省去了由技能映射導出知識結構的復雜計算過程，只需要確定映射模式即可，確定了推測關系，就可以進行學習路徑的探討.

事實上，定理2的逆命題也是成立的，這里不再贅述，因為在實際應用中，人們往往需要由技能映射得到推測關系而不是相反.

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

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

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

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

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

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

3.2 技能映射導出推測關系的算法

定理2給出了從技能映射得到推測關系的思路，根據這個思路可以設計出如下的推測關系算法（以析取模式為例），

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

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

步驟3：重復步驟2，直至結束.

根據以上思路設計算法1.

輸入Q，S，τ，并根據τ將Q中元素排序

例3 用算法1計算前面例1在析取模式下的推測關系，步驟如表1.

表1 推測關系的計算步驟Tab.1 Calculation steps of surmise relation

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

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

4 結論

知識結構是比知識空間更為一般的數學概念，在實際應用中也更常見.在特定的前提下，知識結構可以轉化為知識空間.研究發現，技能映射和知識結構的推測關系之間也存在著較為直接的聯系，這為研究和探索知識空間的理論及其應用提供了一種新的思路和方向.