技能映射下知识空间基的矩阵算法

韩光明，周银凤

（闽南师范大学数学与统计学院，福建漳州363000）

知识空间理论[1](Knowledge Space Theory，简称KST)是由比利时的数学心理学家Doignon 与美国数学家Falmagne 于1985年提出的一种数学理论，该理论用于评估学生对某一领域的知识的学习过程和认知水平，从而指导学生的学习过程和学习路径.

知识空间理论已经成为了测试系统和自适应教学中最有效的知识表示理论[2]，而且在计算机辅助教学中也得到了广泛应用，其中的Aleks软件系统是KST理论的一个影响较大的应用[3].Rusch等[4]将知识空间理论与形式概念分析相结合，并建立了有效的联系.

在国内知识空间理论也有一些应用，比如孙波等[5]研究的基于扩展知识空间理论的自适应测评过程并对测评过程进行了优化，周深等[6]提出了快速自适应测试过程，麦裕华等[7-8]将知识空间理论应用于化学教学.

知识空间的一个最重要的概念是它的基[9]，李进金等[10]称之为知识基，它包含了知识空间的所有信息，由知识基可以生成整个知识空间.1993年，Dowling[2]给出了由知识空间求知识基的方法.1999年，Doignon[9]受到该算法的启发，给出了由知识基计算知识空间的方法.2011年，Falmagne等[11]将Dowling 的算法进行了改进，计算效率提高了10%～30%.

根据知识空间理论，知识是用问题来表示的，将某学科领域问题的全体称为问题域[9].知识域中的问题可以通过某些技能来解决，技能映射刻画了问题和技能之间的对应关系，通过技能映射可以构造知识结构，特别的，一个给定的技能映射在析取模式下可以生成一个知识空间[9].

在保持知识空间不变的情况下，技能也可能会有冗余，此时可以对技能集进行约简，即在原技能集的基础上，约去一些不必要技能，在析取模式下可以生成同样的知识空间，也就是说在保持生成的知识空间不变的情况下，对技能集进行约简.约简后的技能集称为极小技能集，而极小技能集是不唯一的.高纯等[12]在极小技能集方面进行了一些研究.

本文以布尔矩阵为研究工具，提出了布尔向量的投影和知识状态的特征向量等概念，研究基于技能映射的知识空间的知识基及其算法.

1 知识空间、知识基与技能映射

在知识空间的理论中，问题域Q是要考虑的问题的全体，且Q是一个非空的集合.

定义1[2]学生在理想情况下能够正确回答问题域Q中的一些问题所构成的集合称为一个知识状态，记为K.显然，K⊆Q.

定义2[9]设Q为问题域，若知识状态的集族包含空集和全集Q，则称(Q，)为知识结构.特别地，当满足并封闭时，称二元组(Q，)为知识空间，或称为Q上的知识空间，在不引起歧义的情况下，简称为知识空间.

一般情况下，Q是有限的.本文所述的知识空间及其问题域均为有限的.

定义3[9]设为集族，若′是包含中所有有限个元素的并组成的集合，则称集族′是的扩张，记为S()=′，或称扩张成′.

在有限知识空间中，存在一组非空子集族，这些子集族通过并运算可以生成整个知识空间，我们把最小的这组子集族称为知识空间的基.

定义4[9]设为知识空间，若ℬ 是可以扩张的最小子集族，则称ℬ 为知识空间的基，简称知识基，把基中的知识状态称为原子.

特别需要说明的是，空集不是原子，另外，原子最开始的概念是基于问题的，即某个问题的原子，而所有问题的原子组成的集合就是知识基，这里把原子的定义推广到只要是基中的知识状态就是原子，而不再关心它是哪个问题的原子，这并不改变原子的内涵.

Falmagne 等[9]指出，有限知识空间的知识基存在且唯一.知识基的重要程度是显然的，它可以完全确定一个知识空间，也就是说，一个知识空间与它的基是一一对应的.

知识空间的构建方法有很多，1994年，Albert[13-14]提出了一种由问题系统构建知识空间的方法，随后Albert 等[15]又从理论出发到实际应用，系统地研究了知识空间.事实上，知识空间可以由领域专家给出，也可以由大数据分析得出，也可以由下面的技能映射导出.

定义5[9]假设Q为非空的问题域，S为非空技能域，τ：Q→2S{∅}，则称三元组(Q，S，τ)为一个技能映射.

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

Falmagne 等[11]指出，对于特定的一个技能映射，根据两种不同的映射模式（析取模式和合取模式）可以导出两种不同的知识结构，而且，在析取模式下导出的知识结构一定是知识空间.在此模式下，由S的子集T所确定的知识状态KT表示为：

当T取遍S所有的子集（包括空集和S），我们就获得了一个由技能映射在析取模式下导出的知识结构，记作K(Q，S，τ)，Falmagne等已经证明了这个知识结构是并封闭的，即K(Q，S，τ)为知识空间.在(Q，S，τ)明确的情况下，将该知识空间简记为.

例1设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表见表1.

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

根据定义5，(Q，S，τ)是一个技能映射，在析取模式下，S的每一个子集根据式（1）都可以得到一个知识状态，这些所有的知识状态就组成了一个满足并封闭且包括了空集和全集在内的知识空间，即

按照Dowling[2]的知识基的算法，可计算出该空间的知识基为：

2 技能映射的布尔矩阵、布尔向量

定义6向量的所有分量ai都取布尔值0或1，则称向量α为布尔向量.设α、β都是n维布尔向量，其中，，则它们的布尔和为：

可见，两个n维布尔向量的布尔和仍然是n维布尔向量.本文中布尔向量的加法均指的是布尔和.

定义7设n维列向量组α1，α2，…，αm，β，若存在一组不全为0的布尔值k1，k2，…，km，使得

则称β由α1，α2，…，αm布尔表示.若n维列向量组α1，α2，…，αm中任意一个向量不能由其他向量布尔表示，则称向量组α1，α2，…，αm布尔无关，否则称该向量组布尔相关.

n维列向量β可由向量组α1，α2，…，αm布尔表示当且仅当β可表示为向量组α1，α2，…，αm中若干个向量的布尔和.

定义8设(Q，S，τ)为技能映射，其中Q={q1，q2，…，qn}，S={s1，s2，…，sk}，则技能映射的布尔矩阵定义为：

根据技能映射的性质，在矩阵M里，没有零行和零列.把该矩阵的列向量记作α1，α2，…，αk，显然这些都是n维布尔向量，此时矩阵M可由列向量表示为：

我们把α1，α2，…，αk中所有不重复的向量取出来，组成一个布尔向量的集合，记作ΑM.显然，这里有|ΑM|≤|S|.

例2例1中的技能映射(Q，S，τ)的布尔矩阵为：

定义9 设问题域Q={q1，…，qn} ，n维布尔向量则向量α在Q上的投影Γ为：

在不引起歧义的情况下，ΓQ(α)可简记为Γ(α)，另外，这里引入记号ΓΑM，ΓΑM表示ΑM中所有布尔列向量在Q上的投影的集合，显然有ΓΑM⊆2Q，且|ΓΑM|≤|S|.

定义10 设问题域Q={q1，…，qn} ，对于∀K⊆Q，则K的特征向量定义为：

根据定义10，一个n维向量在Q上的投影，就是Q的一个子集.而Q的任意子集的特征向量是一个布尔向量，而且关系可以由定理1进行描述.

定理1设α，β都是任意的n维布尔向量，问题域Q={q1，…，qn} ，对∀K，L⊆Q，则有以下性质成立：

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

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

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

这些性质根据定义7-10很容易得到证明.

3 知识基的判定定理

由定理1可以看出求特征向量和投影是一对互逆的运算，下面将这两个运算加入到技能映射之中去，可以得出以下结论.

引理1设(Q，S，τ)是技能映射，T1，T2⊆S，则它们导出的知识状态满足

证明根据式（1），有

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

引理2设(Q，S，τ)为技能映射，M是(Q，S，τ)的布尔矩阵，ΑM是M的列向量的集合，则所有布尔列向量在Q上的投影都是由(Q，S，τ)导出的知识空间里的知识状态.即ΓΑM⊆.

证明对于∀α∈ΑM，显然∃s∈S，使得当T={s}时，有Γ(α)=KT∈K.

事实上，ΓΑM是由S的单点子集{si}按式（1）导出的所有知识状态的集合.可见，ΑM里每个向量的投影都是的一个知识状态，而中的知识状态不一定都是ΑM里向量的投影，它们的关系如引理3所述.

引理3设(Q，S，τ)为技能映射，则由(Q，S，τ)导出的知识空间里的任意一个知识状态K，都可由ΓΑM里的元素通过并运算得到.

证明根据式（1），对于任意的知识状态，存在一个T={st1，st2，…，stj}⊆S，使得

又因为T={st1}∪{st2}∪…∪{stj}，则根据引理1，有

根据定理1 的性质2，与引理3 等价的结论是：知识空间里的任意一个知识状态的特征向量，等于ΑM里的若干列向量的布尔和，即可由ΑM里的列向量布尔表示.

定理2设(Q，S，τ)是技能映射，M是(Q，S，τ)的布尔矩阵，ΑM是M的列向量的集合，若ℬ 是由(Q，S，τ)导出的知识空间的基，则ℬ ⊆ΓΑM.

证明根据引理3，知识空间里的任意一个知识状态，都可由ΓΑM里的元素通过并运算得到.根据引理2，ΓΑM⊆，又因为在有限知识空间中，基存在且唯一，则根据基的定义，对于任意Bϵℬ，有B∈ΓΑM成立.

定理2 表明，就技能映射导出的知识空间而言，其知识基的原子只存在于布尔矩阵列向量的投影中，这大大缩小了知识基的寻找范围，就效率而言，其意义是显然的.

根据定理2，我们有式（4）成立：

由于知识状态和它的特征向量是一一对应的关系，因此定理2也可以叙述如下.

定理2' 设(Q，S，τ)是技能映射，M是(Q，S，τ)的布尔矩阵，ΑM是M的列向量的集合，若ℬ 是由(Q，S，τ)导出知识空间的基，则对于基中任意原子Bϵℬ，有ΛB∈ΑM.

根据定理2，基的原子就存在于ΓΑM之中，那么ΓΑM中的知识状态是不是都是原子呢？答案是否定的，但是我们可以根据定理3来判断ΓΑM中哪些是原子，哪些不是原子.

定理3设(Q，S，τ)是技能映射，M是(Q，S，τ)的布尔矩阵，ΑM是M的列向量的集合，则ΓΑM中任意知识状态是基ℬ中的原子当且仅当它的特征向量不能由ΑM中其他列向量布尔表示.

证明在这里，只需证明其逆否命题即可，即证在ΓΑM中任意知识状态不是基ℬ 中的原子当且仅当它的特征向量能由ΑM中其他列向量布尔表示.

设∀B∈ΑM，存在一组原子B1，B2，…，Bt，若B∉ℬ，则有B=B1⋃B2⋃…⋃Bt，根据定理1 的性质2 和性质3，可得：

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

定理3 就是知识空间的基的判定定理.根据定理3，可以确定在布尔矩阵的列向量中，哪些是基中原子的特征向量，哪些不是基中原子的特征向量，这样就可以把知识基完全确定下来.

根据定理2，有 |ℬ |≤|ΓΑM|=|ΑM|≤|S|.

推论1设ℬ 是由技能映射(Q，S，τ)导出的知识空间的基，则ℬ 中原子的个数不超过技能的个数，即|ℬ|≤|S|.

4 知识基的算法

若一个由技能映射(Q，S，τ)导出的知识空间为，根据定理3，可由该技能映射的Q-S表得到它的布尔矩阵，并由此得出其布尔列向量集合，只需求出这个集合中布尔无关的向量组，就可以在不计算的情况下确定的知识基.

其计算步骤和流程图见图1.

算法1知识基的计算步骤

step1 输入Q、S和τ，根据定义8，计算该技能映射的布尔矩阵M，并求出该布尔矩阵的向量集ΑM；

step2 根据定义7，判断ΑM中所有布尔向量是否布尔无关，若不是，转向step 3，若是，转向step 4；

step3 从ΑM找到一个可以由其他向量布尔表示的向量，将该向量从ΑM中删除，转向step 2；

step4 此时的向量集ΑM已经变成一个布尔无关的向量集，记作Α′M.将Α′M中所有的向量一一投影到问题集Q上，所得到的知识状态的集合ℬ即为知识空间的基.算法结束.

例3在例2 中，ΑM={α1，α2，α3，α5}，其中α5=α1+α2，而α1，α2，α3是布尔无关的布尔向量，据此，我们可以判定Γ(α5)不是基中的原子，而Γ(α1)和Γ(α2)，Γ(α3)是基中的原子，而且是全部的原子.因此，由例1中的技能映射(Q，S，τ)所确定的知识空间的基为：

这个结果和例1 中的结果是相同的，因为知识基是唯一的，但是本算法的步骤和过程比例1 更为简便，如图1.

图1 知识基的算法流程图Fig.1 Algorithm flow diagram of knowledge

5 极小技能集

根据前文所述，技能映射(Q，S，τ)的布尔矩阵Mn×k和向量集AM之间，有｜ΑM｜≤｜S｜＝k成立，若M中没有完全相同的两列，则｜ΑM｜＝｜S｜.此时，执行算法1，会得到一个布尔无关的向量集A'M，而该向量集是原布尔矩阵M的列向量集的子集，此时找到A'M中每个列向量在矩阵M中的位置，进而找到其对应的技能s，这些技能s组成的集合即为极小技能集.其计算过程如算法2.

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

step 1 输入Q，S和τ，根据定义8，计算该技能映射的布尔矩阵M，将矩阵M用布尔列向量表示为：M=(α1，α2，…，αk)；

step 2 对数据进行预处理，比较αi是否存在两两相同的情况，若有，舍弃其中一个，直到M中所有列向量彼此不同，此时将这些列向量记作AM；

step 3 执行算法1里的step 2和step 3，得到布尔无关的向量组；

step 4此时将该向量组中的每个向量和原矩阵M进行逐一比较，对任意的αi∈AM，若αi∉A'M，则si为可约技能，将其从技能集S中约去；

step 5 最终得到的S为极小技能集.算法结束.

该算法可以求出极小技能集，且这里得到的极小技能集并不是唯一的.因为在step 2 的预处理时，对于相同的多个αi，只保留一个.而保留哪一个舍弃哪一个，在实际操作中，应该要根据其对应的技能的重要性来确定.

例4例1中的技能映射(Q,S,τ)的技能集S是否存在可约去的技能？我们将例1中的布尔矩阵列向量记作α1,α2,α3,α4,α5，通过例2 和例3 已经发现α1=α4，而且α5=α1+α2.因此，可以把α4和α5从AM中删除，AM中剩下布尔无关的向量α1,α2,α3.它们对应的技能为s1,s2,s3，因此可以说技能集{s1,s2,s3}为原技能映射的极小技能集.这里因为α1=α4，故技能集{s2,s3,s4}也是例1中技能映射在保存其知识空间不变的情况下的极小技能集.至于在实际操作中使用哪一个极小技能集，这要看这些技能所代表的具体技能，再兼顾方便和实用性进行取舍.

6 结语

本文对知识基的判定是建立在技能映射的基础之上，定理3不但可以用来对知识基进行判定，也可以在计算出知识基的情况下反过来对技能集进行约简.另外，本文所研究的算法也可以根据一个知识空间来导出某个技能映射，此时导出的技能映射的技能集可以是极小技能集，当然，也可以在保持知识基不变的前提下，适当添加满足实际需要的技能.