基于技能构建知识结构的两种变精度模型与技能子集约简

杨桃丽 李进金,2 李招文 金 铭 周银凤 林艺东,2

知识空间理论(Knowledge Space Theory, KS-T)[1-3]是一种用于评估个体知识水平和指导进一步学习的数学心理框架,目前，已应用在ALEKS系统和自适应辅导系统[4]，并在其它领域具有潜在的应用价值[2]．

知识状态是KST的基本概念之一．在非空有限的问题域中，个体的知识状态表示为个体在理想状态下能正确解决问题的集合[1-2]．在很多情况下，可从个体对不同问题的回答中推断个体的知识状态，即通过检测个体对问题的回答情况，评估个体的知识掌握情况．知识结构是评估个体知识水平的重要工具，表示为序对(Q,K).其中K是至少包含Ø和全集Q的知识状态的集合，一般地，习惯直接使用K表示知识结构．

构建一个准确的知识结构的方法是知识空间理论的重要研究内容.围绕这一问题，学者们结合其它学科以构建知识结构．形式概念分析(Formal Con-cept Analysis, FCA)可与KST结合.Rusch等[5]讨论由形式背景构建知识结构的方法，为概念知识的获取提供一种新的途径．李进金等[6]基于知识基，提出由形式背景构建知识结构的方法，进一步加强FCA与KST之间的联系．受粗糙集近似思想的启发，Yao等[7]利用粗糙集理论(Rough Set Theory, RST)中的近似思想构建知识结构，有效地在同一环境下研究RST与KST．

但是，上述方法仅停留在获得个体可能的知识状态，并未评价个体的知识掌握情况.针对这一问题，已有多位研究者将KST推广到基于能力的知识空间理论(Competency-Based KST, Cb-KST)[8-11].在一般的KST中，构建知识状态和知识结构常用的方法是分析问题和技能之间的关系[12-14]，而技能概念的引入为个体知识评价提供一种切入手段.Doignon[15]提出技能映射的析取模型和合取模型及技能多映射的能力模型，并讨论由其诱导的知识结构，但忽视个体掌握与解决问题有关的技能个数情况.周银凤等[16]给出技能背景的概念，讨论由技能背景构建知识结构及技能评估等问题，考虑个体技能的评价问题，在教育教学方面具有一定的参考性意义，但未考虑技能函数等技能评估问题.Stefanutti等[11]和周银凤等[17]就技能函数与技能评估的问题，研究个体能力水平与表现水平,建立一一对应的条件问题，但要实现两者的一一对应，还有待进一步改进条件.

特别地，在Doignon[15]提出的析取模型、合取模型和能力模型中，由技能映射诱导知识结构的条件过于宽松或苛刻.这是因为，在析取模型中，一旦个体掌握与解决问题有关的某个技能，便足以解决该问题，这将导致无论个体掌握多少个与解决问题相关的技能，最终个体的知识结构都是相同的.在合取模型中，个体需掌握与解决问题有关的所有技能，才能解决该问题.实际上，个体不一定要掌握所有技能才有能力解决相应的问题.在能力模型中，对于解决问题的所有能力，个体掌握其中某个能力就足以解决该问题，而一个能力是由多种技能形成的，即个体需掌握这个能力中的所有技能才能解决此问题.因此，这些评价个体知识情况的方法都集中于个体所能解决的问题，无法解释不同个体解决相同问题背后却有不同知识结构的现象.

然而，在解决问题的所有方法中，可能会存在冗余的技能．为此，Düntsch等[8]研究技能多映射的极小形式，定义技能函数和问题函数的概念.孙晓燕等[18]基于项目状态转移函数，将问题空间推广到多分情形.Xu等[19]结合粗糙集属性约简的方法，寻找极小技能集.Sun等[20]提出极小模糊技能映射的概念.Heller等[9]指出技能函数具有两种特殊的情形，即析取技能函数和合取技能函数．在现实生活中，不同的个体具有不同的技能或能力，不同的技能或能力可能解决相同的问题，于是出现等价的技能或能力．基于上述考虑的问题，可根据个体的知识状态规划其下一步需要学习的技能．

总之，由技能映射或技能函数构建知识结构是KST的热点研究问题，在教育教学方面具有较大的应用前景和理论研究价值．因此，本文引入技能包含度和能力包含度的概念，建立构建知识结构的变精度α-模型和变精度α-能力模型.再讨论诱导良级知识结构时技能映射需满足的条件，得到良好技能映射诱导的知识结构均为良级知识结构的结果.然后，针对技能映射和技能函数存在等价技能子集的情况，分别考虑保持知识结构不变的技能子集约简及学习路径选择的问题，并给出获取极小技能子集族和知识结构的算法.最后，在6个数据集上的实验验证本文算法的可行性和有效性.

1 基础知识

本文仅在理想状态下考虑非空有限的问题域和非空有限的技能域. 这里的理想状态是指个体在回答问题时没有粗心答错或侥幸答对的情况.

知识结构是KST的重要概念之一.个体知识状态的集合是一个知识结构(Q,K)．若知识结构K保持并封闭，即对K中的任意两个元素Ki和Kj，有Ki∪Kj∈K，则称K是一个知识空间．若知识结构K保持交封闭，即对K中的任意两个元素Ki,Kj，有Ki∩Kj∈K，则称K是一个简单闭包空间．若知识结构K同时保持交、并封闭，则称K是一个拟序空间.

设(Q,K)是一个知识结构，对q∈Q，Kq是知识结构K中包含问题q的所有知识状态的集合．对q∈Q，

[q]={p∈Q|Kq=Kp}

表示与q同时出现在某些知识状态中的问题集合．若对∀q∈Q，[q]为单点集，则称(Q,K)是一个可辨识的知识结构．若一个拟序空间(Q,K)是可辨识的，则称(Q,K)是一个序空间.

定义1[2]三元组(Q,S,τ)称为一个技能映射，其中,Q为非空有限问题集，S为非空有限技能集，τ为由Q到2S{Ø}的映射.

在问题集和技能集给定的情况下，直接称τ为一个技能映射.

设(Q,S,τ)为一个技能映射，对T⊆S，定义

K={q∈Q|τ(q)∩T≠Ø}，

称K是由T通过析取模型诱导的知识状态．当T取遍S的所有子集时，所得知识状态的集合K称为由技能映射τ通过析取模型诱导的知识空间．对T⊆S，定义

K={q∈Q|τ(q)⊆T}，

称K是由T通过合取模型诱导的知识状态．当T取遍S的所有子集时，所得知识状态的集合K称为由技能映射τ通过合取模型诱导的简单闭包空间.

定义2[8]三元组(Q,S,μ)称为一个技能多映射，其中，Q为非空有限问题集，S为非空有限技能集，μ为由Q到22S{Ø}{Ø}的映射．

在技能多映射(Q,S,μ)中，对∀q∈Q，若满足

1)μ(q)≠Ø,

2)对∀M∈μ(q),M≠Ø,

3)μ(q)中的能力关于集合的包含关系两两不可比较，

则称(Q,S,μ)为一个技能函数．

在问题集和技能集给定的情况下，直接称μ为一个技能函数．此时，对∀q∈Q，称C∈μ(q)为解决问题q的一个极小能力．

对T⊆S，定义

K={q∈Q|∃C∈μ(q)∶C⊆T}，

称K是由T通过技能函数μ诱导的知识状态．当取遍S的所有子集时，所得知识状态的集合K称为由μ诱导的知识结构．

技能函数有两种特殊的类型，即析取技能函数和合取技能函数.

设(Q,S,μ)为一个技能函数，若对∀q∈Q，有μ(q)={M}，其中Ø⊂M⊆S，则称(Q,S,μ)为一个合取技能函数．若对∀q∈Q，有

μ(q)={{s}∶s∈M}，

其中Ø⊂M⊆S，则称(Q,S,μ)为一个析取技能函数．合取技能函数为每个问题分配一个非空的技能子集，诱导的知识结构保持交封闭，是一个简单闭包空间.析取技能函数为每个问题分配单点的技能子集，诱导的知识结构保持并封闭，是一个知识空间.

定义3[2]设F是一个有限的集族，若对

∀K∈F,L∈F，

存在有限序列

K=K0,K1,…,Kn=L，

使得

d(Ki,Ki+1)=|Ki△Ki+1|=
|(KiKi+1)∪(Ki+1Ki)|=1，

其中，i∈[0,n-1]，d(K,L)=n，则称F是良级的．

满足定义3的有限序列

K=K0,K1,…,Kn=L

称为由K到L的紧路径．

2 技能包含度与能力包含度

定义4设(Q,S,τ)为一个技能映射．对q∈Q，T⊆S，称

为τ的技能包含度集．对q∈Q，将

称为关于问题q的技能包含度集．

推论1设(Q,S,τ)为一个技能映射．对q∈Q，

为关于问题q的技能包含度集，则有

由技能包含度的定义可知，对于两个不相交的技能子集Ti⊆S,Tj⊆S和T⊆S，不难验证它们的技能包含度满足可加性和互补性，即

对α∈(0,1]，根据定义5，显然有

遍历S的子集T,通过变精度α-模型诱导的所有知识状态的集合构成知识结构

为了方便起见，不妨将技能包含度集记为

D(τ)={β1,β2,…,βn}，

其中

0=β1<β2<…<βn=1．

假设

α∈(βi,βi+1],i=1,2,…,n-1，

在βi和βi+1之间没有别的技能包含度，所以技能映射在这样一个区间诱导的知识结构就是在区间右端点诱导的知识结构，即Kα=Kβi+1．

若一个技能映射(Q,S,τ)确定的技能包含度集为D(τ)={β1,β2,…,βn}，除了β1以外，对于β2,β3,…,βn，技能映射(Q,S,τ)通过变精度α-模型可诱导n-1个知识结构．容易验证，对α∈(β1,β2]，变精度α-模型为析取模型，技能映射(Q,S,τ)通过变精度α-模型诱导的知识结构是一个知识空间．对α∈(βn-1,βn]，变精度α-模型为合取模型，技能映射(Q,S,τ)通过变精度α-模型诱导的知识结构是一个简单闭包空间．

下面考虑更一般的情形，即结合技能函数与包含度，讨论构建知识结构的另一种方法．

定义6设(Q,S,μ)为一个技能函数．对q∈Q，C∈μ(q)，T⊆S，称

称为μ的能力包含度集．对q∈Q，

称为关于问题q的能力包含度集．

推论2设(Q,S,μ)为一个技能函数．对q∈Q，

为关于问题q的能力包含度集，则有

同样地，由能力包含度的定义可知，对于两个不相交的技能子集Ti⊆S,Tj⊆S和T⊆S，它们的能力包含度满足可加性和互补性．于是可得如下命题 1．

命题1设(Q,S,μ)为一个技能函数．对∀q∈Q，C∈μ(q)，T1⊆S,T2⊆S，T1∩T2=Ø，则有

证明由定义6，对q∈Q，C∈μ(q)，T1⊆S,T2⊆S，T1∩T2=Ø，有

命题2设(Q,S,μ)为一个技能函数，则有如下性质：

证明由定义6和命题1即证．

由于D(μ)为一个有限集，为了方便起见，不妨将能力包含度集表示为D(μ)={β1,β2,…,βn}，其中

0=β1<β2<…<βn=1,βi+βn-i+1=1．

即

命题3设(Q,S,μ)为一个技能函数，其中Q={q1,q2,…,qm}．设D(μ)={β1,β2,…,βn}为能力包含度集，则下述成立：

3)对∀qi∈Q，i=1,2,…,m，若|D(μqi)|为偶数，则

为偶数；

4)若存在qi∈Q，i=1,2,…,m，使得|D(μqi)|为奇数，则

为奇数．

证明先证1).对qi∈Q，设

D(μqi)={ε1,ε2,…,εn}．

若|D(μqi)|为偶数，由

εj+εn-j+1=1，j=1,2，…,n，

即

这与假设矛盾，因此|D(μqi)|为偶数．

再证2).类似于1)，容易证明2)是成立的．

于是有

故D(μ)为奇数．

注意到,因为

定义8设(Q,S,μ)为一个技能函数．对α∈ (0,1]，称

为由μ通过变精度α-能力模型诱导的知识结构．

定理1设(Q,S,μ)为一个技能函数．

D(μ)= {β1,β2,…,βn}

为μ的能力包含度集．对α∈(βi,βi+1]，i=1,2，…,n-1，有Kα=Kβi+1.

证明对α∈(βi,βi+1]，设Kα为由技能函数μ通过变精度α-能力模型诱导的知识结构．对∀T⊆S，有

由于βi与βi+1之间不存在其它的能力包含度，因此

故Kα=Kβi+1．

定理2设(Q,S,μ)为一个技能函数，

D(μ)= {β1,β2,…,βn}

为μ的能力包含度集．对α∈(βn-1,βn]，由μ通过变精度α-能力模型诱导的知识结构是由μ通过能力模型诱导的知识结构．

因为

所以有C⊆T，即

于是Kβn事实上是由技能函数(Q,S,μ)通过能力模型诱导的知识结构．

由于技能函数具有析取技能函数和合取技能函数两种特殊情形，可对这两种特殊情形进行讨论．

推论3设(Q,S,μ)为一个析取技能函数，则D(μ)={0,1}．对α∈(0,1]，技能函数μ通过变精度α-模型诱导的知识结构是由μ通过能力模型诱导的知识结构．

当(Q,S,μ)为合取技能函数时，此时变精度α-能力模型退化为变精度α-模型．需要注意的是在技能映射(Q,S,τ)中，

τ(q)=C∈μ(q)，

于是有定理3.

定理3设(Q,S,μ)为一个合取技能函数，(Q,S,τ)为一个技能映射，且对q∈Q，

μ(q)={C|Ø⊂C⊆S}，τ(q)=C．

对α∈(βi,βi+1]，由μ通过变精度α-能力模型诱导的知识结构是由技能映射(Q,S,τ)通过变精度α-模型诱导的知识结构．

证明设(Q,Kα)是由μ通过变精度α-能力模型诱导的知识结构．对∀T⊆S，由定义7可得

由于合取技能函数中只为每个问题q分配一个能力且τ(q)=C，于是

变精度α-模型包括析取模型和合取模型，而技能函数的变精度α-能力模型包含能力模型和变精度α-模型，于是本文的变精度α-能力模型比文献[15]中的能力模型适用性更广．下面继续讨论合取技能函数下变精度α-能力模型诱导的知识结构的一些性质．

定理4设(Q,S,μ)为一个合取技能函数，D(μ)={β1,β2,…,βn}为μ的技能包含度集,则由μ通过变精度α-能力模型诱导的知识结构Kβi+1与Kβn-i+1(i=1,2，…,n-1)互为对偶．

证明设(Q,Kβi+1)为由μ通过变精度α-能力模型诱导的知识结构．对∀T⊆S，α=βi+1，i=1,2，…,n-1，知识结构Kβi+1中的元素

由于μ为合取技能函数，于是

由于在能力包含度1-βi+1和1-βi之间不存在其它的能力包含度，从而

又

βi+βn-i+1=1，

则

于是知识结构Kβi+1与Kβn-i+1(i=1,2，…,n-1)互为对偶．

例1设(Q,S,μ)为一个合取技能函数，其中

Q={q1,q2,q3,q4}，S={s1,s2,s3}，
μ(q1)={{s1,s2}}，μ(q2)={{s3}}，
μ(q3)={{s2,s3}}，μ(q4)= {{s2}}．

表1 例1中能力包含度

由表1可得，能力包含度集

表2 例1中知识状态

3 良级的知识结构

一个技能映射通过变精度α-模型诱导的所有知识结构中不一定存在拟序空间．如例1中的两个知识结构都不能同时满足交、并封闭．本节讨论在满足什么条件下，技能映射通过变精度α-模型诱导的所有知识结构都是拟序空间．

Spoto等[21]指出在技能函数中，对某个问题存在专属技能和专属能力．

定义9[22]设(Q,S,τ)为一个技能映射．对q∈Q，若如下条件成立：

1)对所有p∈Q{q}，有s∉τ(p)，

2)s∈τ(q)，

则技能s∈S称为一个专属技能．

定义10设(Q,S,τ)为一个技能映射．对q∈Q，若s为问题q的专属技能，则记为s▷q．

命题4设(Q,S,τ)为一个技能映射．对不同的q∈Q,q′∈Q，若τ(q)⊂τ(q′)，则不存在s▷q．若

τ(q)⊄τ(q′)，τ(q′)⊄τ(q)，

则存在

t∈τ(q)τ(q′)，u∈τ(q′)τ(q)，

使得t▷q,u▷q′．

证明由定义10显然得证．

定义11设(Q,S,τ)为一个技能映射．若τ满足下面两个条件：

1)至少存在一个q∈Q，有s▷q，

2)存在q∈Q,q′∈Q，有

τ(q)⊂τ(q′)， |τ(q′)τ(q)|=1，

则称τ为良好的技能映射．

例2设(Q,S,τ)为一个技能映射，其中

Q= {q1,q2,q3,q4,q5}，S={s1,s2,s3,s4,s5}，

τ(q1)={s2}，τ(q2)={s4}，τ(q3)={s1,s2}，

τ(q4)={s3,s4}，τ(q5)={s1,s2,s5}．

根据定义11，对∀q∈Q，有s3▷q4，s5▷q5，且有

τ(q1)⊂τ(q3)⊂τ(q5),τ(q2)⊂τ(q4)．

可发现

|τ(q3)τ(q1)|=|τ(q5)τ(q3)|=

|τ(q4)τ(q2)|=1，

于是τ为一个良好的技能映射．

定理5设(Q,S,τ)为一个技能映射．对α∈ (0,1]，(Q,Kα)为由(Q,S,τ)通过变精度α-模型诱导的知识结构．(Q,Kα)为拟序空间，当且仅当τ为一个良好的技能映射．

于是T1∪T2诱导的知识状态为

T1∩T2诱导的知识状态为

若T1⊄T2，则

T1∩T2=Ø， |(T1∪T2)(T1∩T2)|>1．

若T1⊂T2，则

|(T1∪T2) (T1∩T2)|≥1.

不妨设

τ(q)=T1∩T2，τ(q′)=T1∪T2，

存在s∈τ(q′)τ(q),使得

|τ(q′)τ(q)|=|s|=1，

于是s▷q′．

反过来，令

诱导的知识状态为

于是对∀K⊆Kα，有

∩K∈Kα, ∪K∈Kα，

故Kα为一个拟序空间．

推论4[2]任意有限的序空间是学习空间，而学习空间是良级的知识结构．

由推论3，有如下定理6．

定理6设(Q,S,τ)为一个技能映射．对α∈ (0,1]，(Q,Kα)是由(Q,S,τ)通过变精度α-模型诱导的知识结构，(Q,Kα)为拟序空间当且仅当(Q,Kα)是良级的．

证明因为对∀τ(q)⊂τ(q′)，有

|τ(q′)τ(q)|=1，

则有Kq≠Kq′，于是由技能映射(Q,S,τ)通过变精度α-模型诱导的知识结构均是可辨识的，即(Q,Kα)是序空间．故由定理5和推论3可知，(Q,Kα)是良级的．

反之，由定理5显然得证．

定理7设(Q,S,τ)为一个技能映射．对α∈(0,1]，(Q,Kα)是由(Q,S,τ)通过变精度α-模型诱导的知识结构，(Q,Kα)是良级的当且仅当τ是一个良好的技能映射．

证明由定理5和定理6可证．

例3设

Q={q1,q2,q3,q4}，S={s1,s2,s3,s4,s5}
τ(q1)={s2,s3}，τ(q2)={s3,s5}，
τ(q3)={s1,s2,s3}，τ(q4)={s3,s4,s5}．

通过计算可得到τ的技能包含度集为

且由技能映射(Q,S,τ)通过变精度α-模型诱导的知识结构分别为

K1={Ø,{q1},{q2},{q1,q2},{q1,q3},{q2,q4},
{q1,q2,q3},{q1,q2,q4},Q}．

可发现所有的知识结构都是满足交并封闭的，于是为良级的知识结构．

例4设

Q={q1,q2,q3}，S={s1,s2,s3,s4,s5}，

定义技能映射τ:

τ(q1)={s1,s2,s5}，τ(q2)={s1,s3,s4}，
τ(q3)={s2,s4}．

τ的技能包含度集为

显然，τ不满足良好技能映射的条件2)．对α∈(βi,βi+1]，i=1,2，3,4，由τ通过变精度α-模型诱导的知识结构分别为

{q2,q3},Q}，

{q2,q3},Q}，

K1={Ø,{q1},{q2},{q3},{q1,q3},{q2,q3},Q}．

通过上述知识结构可发现，由τ诱导的所有知识结构中至少有一个不为拟序空间．

4 极小技能子集族与学习路径

在现实生活中，不同个体具有不同的技能或能力，不同的技能或能力可能解决相同问题，于是出现等价的技能或能力，可根据个体的知识状态对其下一步需要学习的技能进行规划．从概念认知[23，25]的角度上看，个体学习技能是一种概念认知更新的过程，即使在学习某个技能的过程中没有使个体的知识状态发生改变，但个体的认知是有细微更新的．因此，若要对个体的学习进行指导，对其技能学习的缩减和学习路径的规划尤为重要．

4.1 基于技能映射τ的极小技能子集族

是T的一个等价类．对任意[T]，任取一个T′∈[T]，所有T′构成的集族Y被称为关于技能映射τ的一个极小技能子集族．

对于技能映射(Q,S,τ)，对∀q∈Q，取遍Y中元素计算得到的技能包含度集记为

对q∈Q的技能包含度集记为

显然

D′(τ)=∪D′(τq)．

例5设(Q,S,τ)为一个技能映射，其中

Q={q1,q2,q3}，S={s1,s2,s3,s4,s5}，
τ(q1)={s1,s2}，τ(q2)={s4,s5}，τ(q3)={s2,s3}．

表3 例5中技能包含度

由表3和定义4可知，技能包含度集

对∀q∈Q，有

根据定义12和表3，显然可将2S分为21个等价类，从而关于τ的一个极小技能子集族为

Y={Ø,{s1},{s2},{s3},{s4},{s1,s2},{s1,s4},
{s2,s3},{s2,s4},{s3,s4},{s4,s5},{s1,s2,s3},
{s1,s2,s4},{s1,s4,s5},{s2,s3,s4},{s2,s4,s5},
{s3,s4,s5},{s1,s2,s3,s4},{s1,s2,s4,s5},
{s2,s3,s4,s5},S}．

由表4可知,技能包含度集

因此约去冗余的技能子集，对技能包含度集并不产生影响．根据表4和定义2，对α=βi+1,i=1,2，由技能映射τ通过变精度α-模型诱导的知识结构分别为

表4 例5中极小技能子集族的技能包含度

定理8设(Q,S,τ)为一个技能映射，Y为关于τ的一个极小技能子集族. 若对q∈Q，取遍Y中元素计算得到的技能包含度集为D′(τ)，则

D′(τ)=D(τ)．

即

定理9设(Q,Kα)为由技能映射(Q,S,τ)通过变精度α-模型诱导的知识结构，

D′(τ)={β1,β2,…,βn}

为Y的技能包含度集，其中Y为关于τ的一个极小技能子集族．对于α∈(βi,βi+1]，i=1,2，…,n-1，由τ通过变精度α-模型诱导的知识结构为(Q,Kα)．

于是对任意[T]，任取一个T′∈[T]，Y是由所有的T′构成的技能子集族，α∈(βi,βi+1]，技能映射(Q,S,τ)通过变精度α-模型诱导的知识结构为Kα．

推论5设(Q,S,τ)为一个技能映射，则保持Kα不变的技能子集的约简必是保持D(τ)不变的技能子集的约简．

下面讨论保持技能包含度集不变的技能子集的约简是否是保持知识结构不变的技能子集的约简，二者之间是否存在一一对应的关系．给定技能映射(Q,S,τ)，对于q∈Q，由于

于是可保持D(τq)不变，进而保持D(τ)不变．

例如，在例5中，

[Ø,{s3},{s4},{s3,s4},{s4,s5},{s3,s4,s5}]，

[{s1},{s2},{s2,s4},{s2,s3},{s2,s4},{s1,s4,s5},

{s2,s3,s4},{s2,s4,s5},{s2,s3,s4,s5}]，

[{s1,s2},{s1,s2,s3},{s1,s2,s4},{s1,s2,s3,s4},

{s1,s2,s4,s5},S]，

则对任意[T]，任取一个T′∈[T]，计算所得技能包含度集的极小技能子集族为

Y1={Ø,{s1},{s1,s2}}，

于是

{Ø,{s1},{s2},{s4},{s1,s2},{s1,s3},{s4,s5}}．

因为Y中没有包含全集S，遍历Y中的元素，由τ确定的并不是知识结构,从而保持技能包含度集不变的技能子集的约简并不一定是保持知识结构不变的技能子集的约简．

根据上述结果，下面给出寻找极小技能子集族及获取知识结构的算法．

算法1基于技能映射，获取极小技能子集族及知

识结构

输入技能映射(Q,S,τ)

输出关于τ的极小技能子集族Y,

知识结构(Q,Kα)

step 1 令D(τ)=Ø,Y=Ø,Kα=Ø,ta=Ø；

step 2 计算B=2S，其中B为S的幂集；

step 3 遍历问题集Q的问题q和S的幂集B中的元素T；

对D(τ)进行去重并按从小到大排列；

step 5 遍历问题集Q的问题q和S的幂集B中的元素T；

Y←Y∪(B-B(t))；

step 7 令β=D(τ)(2∶end)；

step 8 遍历β中的元素α和Y中的元素T′；

step 10 根据上述获得邻接表ta并生成知识结构图.

算法1寻找技能映射的极小技能子集族的步骤是一个启发式搜索过程．step 3和step 4为找到技能包含度集，step 5和step 6为获取一个极小技能子集族，step 8～step 10为生成知识结构．step 3和step 4的时间复杂度及空间复杂度最大为O(|Q||2S|)，step 5和step 6的时间复杂度及空间复杂度最大为O(|Q||2S|)，step 8～step 10的时间复杂度及空间复杂度最大为O(|Q||2S||Y|)．因此，算法1的最大时间复杂度和空间复杂度均为

O(|Q||2S||Y|)．

4.2 基于技能函数μ的极小技能子集族

是T的一个等价类．对任意[T]，任取一个T′∈[T]，所有T′构成的集族M称为关于技能函数μ的一个极小技能子集族．

设(Q,S,μ)为一个技能函数，对每个qi∈Q，取遍M中元素计算得到的能力包含度集记为

对某个问题qi∈Q的能力包含度集记为

显然

定理10设(Q,S,μ)为一个技能函数，M为一个极小技能子集族．若对q∈Q，取遍M中元素计算得到的技能包含度集为D′(μ)，则D′(μ)=D(μ)．

证明类似于定理8即证．

定理11设(Q,Kα)是由技能函数(Q,S,μ)通过变精度α-能力模型诱导的知识结构，

D′(μ)= {β1,β2,…,βn}

为M的能力包含度集，其中M为关于μ的一个极小技能子集族．对α∈(βi,βi+1]，i=1,2， …,n-1，由μ通过变精度α-能力模型诱导的知识结构为(Q,Kα)．

证明类似于定理9即证．

推论6设(Q,S,μ)为一个技能函数，则保持Kα不变的技能子集的约简必是保持D(μ)不变的技能子集的约简，反之不成立．

基于上述结论，下面给出获取极小技能子集族和知识结构的算法．

算法2基于技能函数，获取极小技能子集族和知

识结构

输入技能函数(Q,S,μ)

输出关于μ的极小技能子集族M,

知识结构(Q,Kα)

step 1 令D(μ)=Ø,M=Ø,Kα=Ø,ta=Ø；

step 2 计算B=2S，其中B为S的幂集；

step 3 遍历每个μ(q)中的能力C和B中的元素T；

对D(μ)进行去重并按从小到大进行排列；

step 5 遍历每个μ(q)中的能力C和B中的元素T；

M←M∪(B-B(U))；

step 7 令β=D(μ)(2∶end)；

step 9 根据上述步骤获得邻接表ta并生成知识结构图．

算法2寻找技能函数的极小技能子集族的步骤也是一个启发式搜索过程．step 3和step 4为获得一个能力包含度集，step 5和step 6为获得一个极小技能子集族，step 8和step 9为生成知识结构．step 3和step 4的时间复杂度及空间复杂度最大为

O(|Q′||μ(q)||2S′|)，

step 5和step 6的时间复杂度及空间复杂度最大为

O(|Q′||μ(q)||2S′|)，

step 8和step 9的时间复杂度及空间复杂度最大为

O(|Q′||μ(q)||2S′||M|)．

因此，算法2的最大时间复杂度和空间复杂度均为

O(|Q′||μ(q)||2S′||M|)．

例6设(Q,S,μ)为一个技能函数，其中，

Q= {q1,q2,q3}，S={s1,s2,s3,s4}，
μ(q1)={{s2,s4}}，μ(q2)={{s1,s3},{s2,s4}}，
μ(q3)={{s1,s2,s3},{s2,s4}}．

由表5可发现，

表5 例6中能力包含度

于是由step 3从2S中删去技能子集{s3},{s2,s3},{s3,s4},{s2,s3,s4}，得到一个极小技能子集族

M={Ø,{s1},{s2},{s4},{s1,s2}, {s1,s3},{s1,s4},

{s2,s4},{s1,s2,s3},{s1,s2,s4},{s1,s3,s4},S}．

由M计算得到的技能包含度集

根据step 4，对于

α=βi+1,i=1,2,3,4，

技能函数μ通过变精度α-能力模型诱导的知识结构分别为

4.3 技能与学习路径选择

定义14给定技能映射(Q,S,τ)或技能函数(Q,S,μ)．对∀[Ti],[Tj]，取T′∈[Ti]，T″∈[Tj]且T′⊂T″，则称T′⊂T″⊂…为有效技能学习链．

若个体在[{s1},{s3}]中选择学习{s1}，则在[{s1,s2},{s2,s3}]中选择学习{s1,s2}，依此类推．

根据定义14，针对个体的学习情况，可规划个体的学习路径，即从Ø到Q的一条学习路径所需学习的技能子集都具有包含关系.

例7对于例5中的知识结构，

K1={Ø,{q1},{q2},{q3},{q1,q2},{q1,q3},
{q2,q3},Q}．

根据上述描述规划个体的学习路径，如图1所示.在图中：将知识状态{q1}简记为q1，其它知识状态也是如此；箭头表示知识状态之间的包含关系，一个把知识状态K和K′连接起来并指向K′的箭头表示K⊂K′，并且不存在K″,使得K⊂K″⊂K′成立．当从图的左边往右看时，它表示一种学习路径：一个个体开始时什么都不知道，即知识状态为Ø，通过某一条学习路径可从某一状态向另一个状态转移，最终可达到知识状态Q．

(b)K1

由图1可发现，同一知识结构不管个体选择哪条学习路径学习，其知识状态从Ø到Q所需学习的技能都是一样的，只是学习的先后顺序不一样．因此，根据个体的学习路径图，可通过个体知识状态的变化趋势指导下一步需要学习的技能．

5 实验及结果分析

为了验证本文两种算法的有效性，在6个数据集上进行实验分析．

所有实验运行环境为Windows 7操作系统，硬件环境为Inter(R)Core(TM) i7-6700 CPU @3.40 GHz和8.00 GB内存，软件环境为MATLAB(R2013a)和RStudio(1.1.463)．

5.1 实验数据集

从UCI数据库(http://archive.ics.uci.edu/ml/

datasets.php)中选取Shuttle-landing-control、Adult、Lenses、StoneFlakes、Hayes、Post这6个数据集进行实验，具体如表6所示．

表6 实验数据集

表7 技能映射(Q1,S1,τ1)

表8 技能映射(Q2,S2,τ2)

表9 技能映射(Q3,S3,τ3)

表10 技能函数

表11 技能函数

表12 技能函数

5.2 实验结果

根据算法1，可求出每个技能映射的技能包含度和知识结构，如表13所示．根据算法2，可求出每个技能函数的能力包含度和知识结构，如表14所示．

表13 不同技能映射的技能包含度和知识结构

表14 不同技能函数的能力包含度和知识结构

由表13和表14可知，根据本文算法，技能子集得到明显缩减．技能映射和技能函数通过极小技能子集族获得知识结构，相对于遍历所有技能子集，分别减少32,4,28,32,4,88个技能子集.这不仅为求解知识结构的过程提供很大的便利，还可根据个体的自身情况帮助其缩小学习范围，降低大脑的存储成本．

对于技能映射(Qi,Si,τi):当α=β2时，由τi通过变精度α-模型诱导的知识结构与由τi通过析取模型诱导的知识结构对应；当α=βn时，由τi通过变精度α-模型诱导的知识结构与由τi通过合取模型诱导的知识结构对应．而当α≠β1,β2,βn时，在由τi通过变精度α-模型诱导的知识结构中，至少存在一个知识结构包含Kβ2，且至少存在一个知识结构包含于Kβn．注意，这里所说的包含均指集族之间的包含关系．例如，由τ2通过变精度α-模型诱导的知识结构为：

{q21,q22,q24,q25,q26,q28},{q21,q23,q24,q25,q27,q28},{q21,q24,q25,q26,q27,q28},{q22,q23,q24,q26,q27,q28},

{q23,q24,q25,q26,q27,q28},{q21,q22,q24,q25,q26,q27,q28},{q21,q23,q24,q25,q26,q27,q28},

{q22,q23,q24,q25,q26,q27,q28},Q2}，

{q22,q23,q24,q26,q27},{q21,q23,q24,q25,q27,q28},{q21,q24,q25,q26,q27,q28},{q22,q23,q24,q26,q27,q28},

{q23,q24,q25,q26,q27,q28},{q21,q22,q24,q25,q26,q27,q28},{q21,q23,q24,q25,q26,q27,q28},

{q22,q23,q24,q25,q26,q27,q28},Q}，

K1={Ø,{q21},{q22},{q23},{q21,q22},{q21,q25},{q22,q23},{q22,q26},{q23,q27},{q21,q23,q24},

{q21,q22,q23,q24},{q21,q22,q25,q26},{q22,q23,q26,q27},{q21,q23,q24,q25,q27,q28},Q}.

因此，变精度α-模型和变精度α-能力模型均克服诱导知识结构过于宽松或苛刻的条件，使得对于不同的个体，知识结构更合理．

为了使结果更可观，使用(a)～(c)表示技能映射的变精度α-模型与析取模型和合取模型的关系，(d)～(f)表示技能函数的变精度α-能力模型与能力模型的关系．

由图2可知，变精度α-模型既包含析取模型，又包含合取模型，并具有析取模型和合取模型不能诱导的知识结构.而变精度α-能力模型包含能力模型，并具有能力模型不能诱导的知识结构．由此说明本文算法可解决文献[15]中存在条件过于宽松或苛刻的问题．

图2 不同模型下诱导的知识结构中知识状态个数

在图3和图4中，节点均表示知识状态．图3中节点“1”表示知识状态为Ø，节点“31”表示知识状态为Q．图4中节点“1”也表示知识状态为Ø，节点“21”表示知识状态为Q．连接2个节点的边表示大的节点包含小的节点．

图3 τ1通过变精度α-模型诱导的知识结构图

图4 μ1通过变精度α-能力模型(α=1)诱导的知识结构图

6 结 束 语

本文将技能映射和技能函数与包含度结合，研究技能映射和技能函数诱导知识结构的另一种方法,还讨论技能映射在满足什么条件时，通过变精度α-模型可诱导拟序空间．为了降低构建知识结构的复杂度，考虑对技能子集进行约简，得到技能集S的一个极小技能子集族．遍历极小技能子集族中的元素，技能映射(技能函数)通过变精度α-模型(变精度α-能力模型)诱导的知识结构保持不变．本文提出两种算法：1)基于技能映射，寻找极小技能子集族和生成知识结构的算法;2)基于技能函数，寻找极小技能子集族和生成知识结构的算法．UCI数据集上的实验表明对技能子集的约简算法是可行的，这不仅使诱导知识结构的复杂度得以降低，还涉及到个体技能选择和知识评估的问题．Sun等[20]将模糊集的思想融入技能映射中，研究个体技能的熟练程度，为评估个体的知识掌握情况提供另一种思路．因此，在今后的研究中:一方面考虑把文献[20]中模糊技能映射结合到本文考虑的问题中，继续研究个体的技能选择与知识评估的问题；另一方面将考虑技能映射通过变精度α-模型诱导的知识结构中至少存在一个拟序空间的条件．