基于技能映射的知识结构和推测关系研究

韩光明,赵 青

（闽南师范大学数学与统计学院，福建漳州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 结论

知识结构是比知识空间更为一般的数学概念，在实际应用中也更常见.在特定的前提下，知识结构可以转化为知识空间.研究发现，技能映射和知识结构的推测关系之间也存在着较为直接的联系，这为研究和探索知识空间的理论及其应用提供了一种新的思路和方向.