知識基的布爾矩陣求解方法

謝小賢, 李進金, 陳東曉, 林榮德

(1. 華僑大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 福建 泉州 362021；2. 華僑大學(xué) 計算科學(xué)福建省高校重點實驗室, 福建 泉州 362021；3. 閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 福建 漳州 363000)

知識空間理論(KST)是美國數(shù)學(xué)心理學(xué)家Doignon等[1]提出的，通過分析學(xué)生對不同水平的一系列有關(guān)問題的解答情況，獲得學(xué)生的認知水平和學(xué)習(xí)路徑，進而指導(dǎo)學(xué)生學(xué)習(xí)和教師教學(xué)，為教育教學(xué)提供有效的評價方法.Koppen等[2]用專家問詢系統(tǒng)生成知識空間;Albert等[3]用問題系統(tǒng)構(gòu)建知識空間;Dowling[4]在有限知識空間中提出一種構(gòu)建知識基的方法；Falmagne等[5]對Dowling生成知識空間的算法進行改進，提高了效率.KST作為自適應(yīng)教學(xué)和測試系統(tǒng)中最有效的知識表示理論[6-7]，已應(yīng)用到教育領(lǐng)域中，例如，計算機知識診斷系統(tǒng)ALEKS[8]的開發(fā)與應(yīng)用.文獻[9-10]用知識空間理論分析學(xué)習(xí)路徑等問題，并應(yīng)用于化學(xué)教學(xué).

形式概念分析(FCA)是德國數(shù)學(xué)家Wille[11]提出的，刻畫對象與屬性之間的概念層次結(jié)構(gòu)，以及概念之間的泛化和特化關(guān)系，主要研究屬性約簡[12-20]、粒約簡[21-22]、概念約簡[23-25]和規(guī)則提取[13-14]等，作為一種有力的數(shù)據(jù)分析工具，已廣泛應(yīng)用于機器學(xué)習(xí)、知識評價等領(lǐng)域.Rusch等[26]建立了知識空間與形式背景之間的聯(lián)系；Spoto等[27]將KST與FCA相結(jié)合，分析知識結(jié)構(gòu)的有效性；李進金等[28]分析知識空間和形式概念分析之間的聯(lián)系，以及知識基和知識空間的構(gòu)建方法.

知識基是知識空間的核心,是知識空間的最小生成組，蘊含了知識空間的所有信息.因此，研究知識基具有非常重要的意義.由于知識空間與形式背景關(guān)系密切，而形式背景可看作一個布爾關(guān)系矩陣，可用矩陣方法解決形式背景中的屬性約簡[17-20]和概念約簡[24-25]等問題.因此，本文將用矩陣方法研究知識空間中的原子和知識基.首先，通過KST和FCA的聯(lián)系，導(dǎo)出反知識背景和知識背景；其次，利用布爾矩陣運算，研究(反)知識背景的關(guān)系矩陣、對象關(guān)系矩陣及其相關(guān)性質(zhì);最后，從知識狀態(tài)、算子、布爾向量和布爾矩陣等角度，討論知識空間中原子和知識基的特征，并給出求解方法.

1 預(yù)備知識

1.1 知識空間

設(shè)qi(1≤i≤m)表示問題，則稱Q={q1,q2,…,qm}為所討論知識的問題域.文中只考慮論域Q有限的情形.

定義1[1]學(xué)生在理想條件下能正確回答問題域Q中的問題所構(gòu)成的集合稱為知識狀態(tài)，記為K.

定義2[2]設(shè)Q為問題域，K是Q的知識狀態(tài)集族，并且K至少包含了空集?和全集Q，稱(Q,K)為知識結(jié)構(gòu)，記

K={?,K1,K2,…,Q}，

其中，每一個Ki?Q.

對知識結(jié)構(gòu)(Q,K)，若K對有限并封閉，即

?Ki,Kj∈K?Ki∪Kj∈K,

則稱(Q,K)為知識空間，或稱K為知識空間.

當Q有限時，稱知識結(jié)構(gòu)(Q,K)是有限的.當K有限時，稱知識結(jié)構(gòu)(Q,K)是實質(zhì)有限的.

定義3[5]若G′包含G中所有有限個元素的并組成的集合，則稱集族G′是G的張成，記為S(G)=G′，或稱G張成G′.

由S(G)的定義可知，S(G)是并封閉的.

定義4[5]設(shè)集族F是并封閉的，若B是張成F的最小子集族，且B中的任何一個集合K，均不能由B中其他集合的并集表示，則稱B為F的基，即S(B)=F.

定義4中最小子集族是指對于任意H?B且S(H)=F，有H=B.稱知識空間的基為知識基，并約定??B.另外，對知識空間(Q,K)，文中僅討論Ki=Kj?i=j(Ki,Kj∈K)的情形.

引理1[5]任何實質(zhì)有限的知識空間有知識基.

知識基B可生成唯一的知識空間(Q,K)，知識空間(Q,K)可確定唯一的知識基B，兩者一一對應(yīng).

1.2 形式概念分析

設(shè)X?P，B?Q，形式背景(P,Q,I)上的算子：X*={q∈Q|?p∈X,pIq}，B*={p∈P|?q∈B,pIq}，若滿足X*=B,B*=X，則稱(X,B)為形式背景(P,Q,I)上的一個形式概念(簡稱概念)，稱X為概念的外延，B為概念的內(nèi)涵.所有的概念構(gòu)成的集合叫概念格，記為L(P,Q,I).一般地，對p∈P，q∈Q，記{p}*=p*，{q}*=q*.

若(X1,B1)和(X2,B2)是概念，其上的偏序關(guān)系定義為(X1,B1)≤(X2,B2)?X1?X2(B1?B2).定義下確界為(X1,B1)∧(X2,B2)=(X1∩X2,(B1∪B2)**)，上確界為(X1,B1)∨(X2,B2)=((X1∪X2)**,B1∩B2)，二者也是概念，從而L(P,Q,I)是完備格，稱為(P,Q,I)的概念格.

1.3 知識空間與形式背景的聯(lián)系

文獻[26]建立了知識空間與形式背景的聯(lián)系，由知識空間(Q,K)可構(gòu)造出對應(yīng)的反知識背景(P,Q,Ic)和知識背景(P,Q,I).

定義6[26]設(shè)有限集P={p1,p2,…,pn}，其中,pi(1≤i≤n)是被測試的對象，Q是問題集，I是P和Q之間的二元關(guān)系，pIq表示對象p不能解決問題q，稱三元組(P,Q,I)是知識背景.

定義7[26]設(shè)有限集P={p1,p2,…,pn}，其中,pi(1≤i≤n)是被測試的對象，Q是問題集，Ic是P和Q之間的二元關(guān)系，pIcq表示對象p能解決問題q，則稱三元組(P,Q,Ic)是相對于(P,Q,I)的反知識背景.

由知識空間(Q,K)構(gòu)造知識背景(P,Q,I)的過程如下.

設(shè)K={K1,K2,…,Kn}，其中,K1=?，Kn=Q，Ki(1≤i≤n)表示對象pi對應(yīng)的知識狀態(tài)，由此就將知識空間中的每一個狀態(tài)和被測試的對象之間建立一一對應(yīng)關(guān)系.于是有引理2.

引理2[26]知識背景(P,Q,I)與形式背景(K,Q,?)是同構(gòu)的,其中，K是知識狀態(tài)集族，Q是問題集，?是K×Q上的二元關(guān)系，表示某個問題q?K，其中，q∈Q,K∈K.

設(shè)知識背景為(P,Q,I)，且X?P,B?Q,算子X*={q∈Q|?p∈X,pIq}，B*={p∈P|?q∈B,pIq}，若X*=B并且B*=X，則稱二元組(X,B)是一個知識概念，簡稱概念，X是概念的外延，B是概念的內(nèi)涵.

1.4 布爾矩陣的運算規(guī)律

定義在B0={0,1}上的向量稱為布爾向量，記n維布爾行向量為Vn，記n維布爾列向量為Vn.通常把分量全為0的向量(0,0,…,0)或(0,0,…,0)T記作0，稱為布爾零向量(簡稱零向量);否則,稱為布爾非零向量(簡稱非零向量).記m×n階布爾矩陣為Bm×n.

設(shè)α=(x1,x2,…,xn),β=(y1,y2,…,yn)∈Vn，則定義兩個運算“ + ”與“ · ”為：1)α+β=(x1+y1,x2+y2,…,xn+yn)；2)α·β=(x1·y1,x2·y2,…,xn·yn)，其中，“ + ”表示取最大值，“ · ”表示數(shù)量乘積，取最小值.

對于行向量α和β，對于i∈{1,2,…,n}，若xi=1?yi=1，則記α≤β.如果α≤β且α≠β， 則記α<β.列向量相關(guān)內(nèi)容可類似定義[29].

定義8[29]設(shè)子空間W?Vn，W的一個無關(guān)的子集合V稱為W的一個基,當且僅當W=〈V〉(向量集合V的生成空間).

設(shè)A∈Bm×n.BR(A)表示由A的所有行構(gòu)成的集合生成的空間R(A)的唯一基底,稱為A的行基底,其基數(shù)稱為A的行秩,用ρR(A)表示.類似地,BC(A)表示由A的所有列構(gòu)成的集合生成的空間C(A)的唯一基底,稱為A的列基底,其基數(shù)稱為A的列秩,用ρC(A)表示[29].

設(shè)A=(ai,j)m×n,B=(bi,j)m×n,C=(ci,j)n×l為布爾矩陣，用AT表示矩陣A的轉(zhuǎn)置.規(guī)定矩陣運算律如下：

1)A≤B當且僅當ai,j≤bi,j,i=1,2,…,m；j=1,2,…,n；

2)A∨B=(ai,j∨bi,j)m×n；

3)A∧B=(ai,j∧bi,j)m×n；

4)A-B=(ai,j∧(1-bi,j))m×n；

5) ～A=(1-ai,j)m×n；

6)A·C=(di,j)m×l，其中,di,j=∨1≤k≤n(ai,k∧ck,j)，∨表示取最大值，∧表示取最小值，則稱A·C是布爾矩陣A與C的乘積[29].

2 原子的特征和知識基

知識基是知識空間的核心，是知識空間的最小生成組，可生成知識空間，而且知識基還能反應(yīng)學(xué)生掌握的最基本的問題集族，為刻畫知識空間和尋找學(xué)習(xí)路徑提供依據(jù).文獻[4,5，28]對此作了一些研究.下面從知識狀態(tài)、算子、布爾向量和布爾矩陣等角度討論原子的特征和知識基.

2.1 基于知識狀態(tài)的原子特征和知識基

定義10[4]設(shè)(Q,K)為知識空間，設(shè)F是問題域Q的非空子集族，q∈∪F,F中包含q的最小集合,稱為元素q的一個原子.

引理4[4]如果知識空間(Q,K)的知識基B存在，則B可由所有的原子組成的集族構(gòu)成.

因此，尋找知識基的過程就是找出知識空間的所有問題的原子.

定理1[5]設(shè)(Q,K)為知識空間，設(shè)F是問題域Q的任意非空子集族，知識狀態(tài)K∈F是一個原子,當且僅當K∈F,其中,K=∪F∈FF.

推論1設(shè)(Q,K)為知識空間，設(shè)F是問題域Q的非空子集族，若對知識狀態(tài)K∈K，滿足K=∪F∈FF，則F?K.

推論2設(shè)(Q,K)為知識空間，則知識狀態(tài)K∈K是一個原子,當且僅當K≠∪?≠F?KF.

證明:充分性.若K∈K是一個原子，設(shè)K=∪?≠F?KF.則對任意q∈K，必存在Fq≠?，使q∈Fq?K，則K不是q∈K的原子，與條件矛盾，則K≠∪?≠F?KF.

必要性.若K≠∪?≠F?KF.取F={F|?≠F?K}∪{K},則僅當K∈F時,有K=∪F∈FF，由定理1得知識狀態(tài)K∈K是一個原子.

推論3設(shè)(Q,K)為知識空間，則知識狀態(tài)K∈K不是一個原子,當且僅當K=∪?≠F?KF.

例1在知識空間

K={?,{a},{a,b},{b,c},{a,b,c}}

中，{a,b,c}={a}∪{a,b}∪{b,c}，則由推論3得{a,b,c}不是原子.而{a,b}不能由其非空真子集的并表示，由推論2得{a,b}是原子;同理,{a},{b,c}都是原子.因此，該知識空間的知識基B={{a},{a,b},{b,c}}.或者由Dowling[4]算法也可得出,問題a只有一個原子{a}，問題b有兩個原子{a,b}和{b,c}，問題c的原子為{b,c}，該算法[4]的計算復(fù)雜度為O(|K|2|Q|).

2.2 在反知識背景中的原子特征和知識基

定義11設(shè)(P,Q,Ic)為反知識背景，p∈P，若滿足

則稱p為并可約元;否則,稱p為并不可約元.

由知識空間(Q,K)滿足并封閉，可得性質(zhì)2.

定理2設(shè)(Q,K)為知識空間，(P,Q,Ic)為其反知識背景，知識狀態(tài)?≠K∈K與p∈P對應(yīng).則

1) 知識狀態(tài)K不是一個原子,當且僅當p是并可約元;

2) 知識狀態(tài)K是一個原子，當且僅當p是并不可約元.

由推論2和推論3易證.

推論4設(shè)LJ(P,Q,Ic)={p*|p∈P}{?}，OJ(P,Q,Ic)={p*|p是并可約元}，則LJ(P,Q,Ic)

表1 由K導(dǎo)出的反知識背景Tab.1 Anti-knowledge context derived by K

OJ(P,Q,Ic)是原子的全體，即為知識空間(Q,K)的知識基.

例2由知識空間

K={?,{a},{a,b},{b,c},{a,b,c}}

性質(zhì)4設(shè)(Q,K)為知識空間，(P,Q,Ic)為其反知識背景.對于?αi,αj∈RIc，則?αk∈RIc,得αk=αi+αj.

由定義2可知，知識空間(Q,K)滿足K對有限并封閉，易得性質(zhì)4，則RIc滿足對加法封閉.找出集合RIc的一個基，就可得到知識空間的原子和知識基.

性質(zhì)5設(shè)(Q,K)為知識空間，(P,Q,Ic)為其反知識背景.對于α∈RIc，假設(shè)α=∑αi∈RIcαi，則α≥αi.

定理3設(shè)(Q,K)為知識空間，(P,Q,Ic)為其反知識背景，知識狀態(tài)?≠K∈K與α≠0∈RIc對應(yīng).則

1) 知識狀態(tài)K不是一個原子，當且僅當α是并可約元；

2) 知識狀態(tài)K是一個原子，當且僅當α是并不可約元.

推論5設(shè)RJ={α|α∈RIc是并可約元}，則由RIcRJ可找出所有原子，即知識空間(Q,K)的知識基.

定理4設(shè)(Q,K)為知識空間，(P,Q,Ic)為其反知識背景及其關(guān)系矩陣MIc，則知識基所含元素的個數(shù)(即原子的總個數(shù))為矩陣MIc的行秩.

2.2.3 基于布爾矩陣的原子特征和知識基 由知識空間(Q,K)滿足并封閉，則其對應(yīng)的反知識背景(P,Q,Ic)中，{p*|p∈P}也滿足并封閉.此時，反知識背景不是節(jié)1.2意義上的形式背景，但仍然沿用其中的一些名稱和記號，例如，關(guān)系矩陣和對象關(guān)系矩陣等.從布爾矩陣的角度獲取原子的特征，有兩種方式.結(jié)合定義12和定理3，給出第一種矩陣運算方法，具體過程如下.

定理5設(shè)(Q,K)為知識空間，(P,Q,Ic)為其反知識背景，G為其對應(yīng)的知識狀態(tài)真包含關(guān)系矩陣，S為其對應(yīng)的知識狀態(tài)線性表示矩陣，Sd為其對應(yīng)的原子的特征矩陣，則

2)S中的第i個行向量為α(pi)；

算法1在反知識背景(P,Q,Ic)中獲取原子和知識基的矩陣算法1

輸入：反知識背景(P,Q,Ic)，二元關(guān)系矩陣MIc，并且|P|=n，|Q|=m.

輸出：原子和知識基.

步驟1： 計算對象關(guān)系矩陣Mn×n.

步驟2： 計算矩陣S和Sd.

因為問題q的原子是在包含關(guān)系下的狀態(tài)集族的極小集，而這種關(guān)系也可用布爾矩陣運算實現(xiàn)，即第二種矩陣方法，具體過程如下.

表2 由表1更新得到 的極小關(guān)系矩陣Tab.2 Minimal matrix obtained by updating Table 1

算法2在反知識背景(P,Q,Ic)中獲取原子和知識基的矩陣算法2

輸入：形式背景(P,Q,Ic)，二元關(guān)系矩陣MIc，并且|P|=n， |Q|=m.

輸出：形式背景的所有原子和知識基.

步驟1： 計算對象關(guān)系矩陣Mn×n.

步驟2： 計算知識狀態(tài)集族的極小集

forj= 1:|Q|

end for

Mmin=MIc.

2.3 在知識背景中的原子特征和知識基

類似地，在知識背景中也可從算子和布爾矩陣的角度刻畫原子特征，構(gòu)建知識基.

2.3.1 基于算子的原子特征和知識基

定義15設(shè)(P,Q,I)為形式背景，p∈P，若滿足

則稱p為交可約元；否則，稱p為交不可約元.

定理7設(shè)(Q,K)為知識空間，(P,Q,I)為其知識背景，知識狀態(tài)?≠K∈K與p∈P對應(yīng).則

1) 知識狀態(tài)K不是一個原子，當且僅當p是交可約元；

2) 知識狀態(tài)K是一個原子，當且僅當p是交不可約元.

推論6設(shè)LM(P,Q,I)={p*|p∈P}{Q}，OM(P,Q,I)={p*|p是交可約元}，則LM(P,Q,I)OM(P,Q,I)是原子的全體，即為知識空間(Q,K)的知識基.

2.3.2 基于布爾矩陣的原子特征和知識基 在知識背景(P,Q,I)中，可通過算子 “”,“”和“”獲取原子[26].

定義16[26]在知識背景(P,Q,I)中，定義算子“”,“”和“”.其中，pq表示pIcq并且p*是不包含q的極大集;pq表示pIcq并且q*是不包含p的極大集;pq表示同時滿足pq和pq.

定理8設(shè)(Q,K)為知識空間，(P,Q,I)為其知識背景.在(P,Q,I)中,每一個問題q∈Q對應(yīng)的“”的知識狀態(tài)就是它的原子.

證明：若pq，則pIcq，且p*是不包含q的極大集.因此，Qp*是包含q∈Q的知識狀態(tài)中的極小集.故Qp*為q的一個原子.

定理9[26]設(shè)(Q,K)為知識空間，(P,Q,I)為其知識背景.在(P,Q,I)中,每一個問題q∈Q對應(yīng)的“”的知識狀態(tài)是一個原子.

例7由知識空間

K={?,{a},{a,b},{b,c},{a,b,c}}

表3 由K導(dǎo)出的知識背景Tab.3 Knowledge context derived by K

例8Korossy[26]選取了初等幾何學(xué)中與畢達哥拉斯定理有關(guān)的5個問題，記為Q={1,2,3,4,5}，通過實驗測試并分析得到知識空間(Q,K)，其中，

由該知識空間導(dǎo)出的知識背景,如表4所示.

表4 由K導(dǎo)出的知識背景Tab.4 Knowledge context derived by K

利用定理10對知識背景的關(guān)系矩陣MI中的所有列進行對象內(nèi)涵的極大運算，最后,可以得到的新的布爾矩陣，記為Mmax.Mmax中所有二元對(取值為零)對應(yīng)著pq關(guān)系下的極大集，在二元對取值為零處的問題q對應(yīng)的知識狀態(tài)K=Qp*為問題q的原子，所有原子組成該知識背景所對應(yīng)的知識空間的知識基.由Mmax可得出例7中知識空間的所有原子對應(yīng)的二元對(取值為零)和原子，如表5所示.所以,該知識空間(Q,K)的知識基為

B={{1},{3},{1,2},{2,3},{1,4},{3,4},{1,2,3,5}}.

表5 問題q對應(yīng)的二元對及其原子Tab.5 Pairs and atom of question q

算法3在知識背景(P,Q,I)中獲取原子和知識基的矩陣算法

輸入： 知識背景(P,Q,I)，二元關(guān)系矩陣MI，并 且|P|=n，|Q|=m.

輸出： 知識背景的所有原子和知識基.

步驟1： 計算對象關(guān)系矩陣Mn×n.

步驟2： 計算對象內(nèi)涵的極大集

forj=1:|Q|

end for

Mmax=MI.

文中提出的矩陣算法1、算法2和算法3都可以得到知識空間的原子和知識基，計算的時間復(fù)雜均為O(|Q||K|2).

3 結(jié)束語

先建立知識空間與反知識背景、知識背景之間的關(guān)系，再從并不可約元、交不可約元、集合的包含關(guān)系等方面判定原子特征，進而從知識狀態(tài)、算子、布爾向量和布爾矩陣等不同角度，獲取原子和知識基.在3種矩陣算法中，算法1通過矩陣方法計算并不可約元，獲得原子和知識基，該算法還可以得到并可約元的并式表達式；算法2用矩陣方法計算出集合在包含關(guān)系下的極小集，從而得到各個問題的原子，構(gòu)建知識基；算法3用矩陣方法計算出集合在包含關(guān)系下的極大集，從而獲得pq，進而得到各個問題的原子和知識基.文中提出的矩陣方法為知識空間的研究拓展了計算方法，后續(xù)可進一步研究形式背景與知識空間的關(guān)系，并將它們相互結(jié)合應(yīng)用到教育教學(xué)等領(lǐng)域.