知識(shí)空間、形式背景和知識(shí)基

李進(jìn)金,孫 文

(1.閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 漳州 363000;2.汕頭大學(xué) 理學(xué)院, 汕頭 515000)

知識(shí)空間理論(knowledge space theory,簡(jiǎn)稱“KST”)[1]是由美國(guó)數(shù)學(xué)心理學(xué)家J P Doignon和J C Falmagne于1983年首先提出的一種數(shù)學(xué)理論。其通過(guò)分析學(xué)生對(duì)不同水平的一系列有關(guān)問(wèn)題解答情況來(lái)確定學(xué)生在不同知識(shí)中的認(rèn)知水平?；诮逃龑W(xué)和心理學(xué)等理論,KST建立了一套數(shù)學(xué)理論來(lái)反映教育規(guī)律,為教育評(píng)價(jià)提供了一種有效的科學(xué)方法,也是一種測(cè)試學(xué)生知識(shí)水平和構(gòu)建學(xué)生知識(shí)結(jié)構(gòu)的理論。1990年Koppen和Doignon研究了基于專家問(wèn)詢生成知識(shí)空間的方法[2]。1993年Dowling在有限知識(shí)空間中提出了一種構(gòu)建知識(shí)基的方法,同時(shí)研究了根據(jù)有限狀態(tài)族生成知識(shí)空間的另一種不同方法[3]。1994年，Albert提出了一種由問(wèn)題系統(tǒng)構(gòu)建知識(shí)空間的方法[4-5],隨后Albert和Lukas又從理論到應(yīng)用系統(tǒng)地研究了知識(shí)空間[6]。發(fā)展至今,KST已經(jīng)成為了自適應(yīng)教學(xué)和測(cè)試系統(tǒng)中最有效的知識(shí)表示理論[7],并在計(jì)算機(jī)輔助教學(xué)中得到了廣泛應(yīng)用。例如,基于網(wǎng)頁(yè)在線學(xué)習(xí)和評(píng)估的計(jì)算機(jī)知識(shí)診斷系統(tǒng)ALEKS(assessment and learning in knowledge space的簡(jiǎn)稱)已使得美國(guó)數(shù)百萬(wàn)學(xué)生受益(https://www.aleks.com/)[8]。

知識(shí)基是知識(shí)空間的核心要素, 其元素個(gè)數(shù)通常遠(yuǎn)小于知識(shí)空間元素個(gè)數(shù)。知識(shí)基可生成知識(shí)空間, 它蘊(yùn)含了知識(shí)空間的所有信息。事實(shí)上,知識(shí)基是知識(shí)空間的最小生成組,它反應(yīng)了學(xué)生能掌握的最基本的問(wèn)題集族,為刻畫整個(gè)知識(shí)空間以及尋找學(xué)習(xí)路徑都提供了依據(jù)。因此,研究知識(shí)基具有豐富的理論和現(xiàn)實(shí)意義。對(duì)于知識(shí)基生成知識(shí)空間的算法,Dowling的算法對(duì)選擇狀態(tài)的順序比較敏感[3]。2011年Falmagne和Doignon改進(jìn)了Dowling的算法,使得算法效率提高10%～30%[9]。

形式概念分析(formal concept analysis,簡(jiǎn)稱“FCA”)是由德國(guó)數(shù)學(xué)家R Wille于1982年提出的一種數(shù)學(xué)理論[10]。它作為一種知識(shí)發(fā)現(xiàn)的有力工具已被廣泛地應(yīng)用于信息檢索,知識(shí)評(píng)價(jià)等領(lǐng)域。在FCA中,概念是一個(gè)由外延和內(nèi)涵構(gòu)成的二元組,其中外延是對(duì)象集,描述概念所涵蓋的對(duì)象; 內(nèi)涵是屬性集,描述概念所具有的特征。在某種偏序關(guān)系確定下,所有概念組成的集合稱概念格[11]。概念結(jié)構(gòu)如何表征與存儲(chǔ),概念格如何構(gòu)建以及知識(shí)約簡(jiǎn)等是形式概念分析研究的熱點(diǎn)問(wèn)題。值得注意的是,1996年Rusch和Wille建立了知識(shí)空間與概念格之間的聯(lián)系,提出了另一種由知識(shí)基生成知識(shí)空間的方法[12]。這為FCA在教育與心理學(xué)等領(lǐng)域的應(yīng)用奠定了基礎(chǔ)。形式概念分析在數(shù)學(xué)教育和心理學(xué)等領(lǐng)域中也有著廣泛的應(yīng)用[9,13]。

本文旨在闡述知識(shí)空間理論和形式概念分析之間的聯(lián)系,進(jìn)一步豐富形式概念分析理論及其在知識(shí)空間中的應(yīng)用,以及為通過(guò)知識(shí)基建立知識(shí)空間和形式背景之間的聯(lián)系提供一種思路。

1 知識(shí)空間的基

1.1 基本概念和結(jié)果

定義1[1]設(shè)某個(gè)領(lǐng)域的知識(shí)都能通過(guò)一些問(wèn)題來(lái)反應(yīng),將這些問(wèn)題組成的集合稱為問(wèn)題域,簡(jiǎn)稱為域(domain),用符號(hào)Q表示。

通常,令Q={q1,q2,…,qn}為所討論知識(shí)的問(wèn)題域,其中qi表示問(wèn)題,i≤n。

值得注意的是:

1) 知識(shí)由問(wèn)題來(lái)刻畫,學(xué)生能夠解決某個(gè)問(wèn)題表示其掌握了相應(yīng)的知識(shí)。因此,問(wèn)題的選擇需具有代表性。

2) 一般情況下只考慮論域Q有限的情形。

例1若要測(cè)試某中學(xué)生關(guān)于一元二次方程αx2+βx+γ=0求解的知識(shí)掌握情況,則只需采用如下3個(gè)問(wèn)題,其中

q1:x2-3x+2=0 (Δ>0),

q2:x2-2x+1=0 (Δ=0),

q3:x2-2x+3=0 (Δ<0),

這3個(gè)問(wèn)題分別代表了解一元二次方程的3種情形。因此,問(wèn)題域?yàn)镼={q1,q2,q3}。

定義2[1]學(xué)生在理想條件下能夠正確回答問(wèn)題域Q中的問(wèn)題所構(gòu)成的集合稱為知識(shí)狀態(tài)(knowledge state),記為K。

所謂理想狀態(tài)即指學(xué)生在沒(méi)有受到外部壓力或任何躁動(dòng)情緒干擾的情況下,沒(méi)有由粗心導(dǎo)致的錯(cuò)誤和由對(duì)問(wèn)題沒(méi)有真正理解而幸運(yùn)猜對(duì)的情況。

定義3[1]設(shè)Q為問(wèn)題域,K是由Q的一些子集構(gòu)成的知識(shí)狀態(tài)集族,并且K至少包含了空集?和全集Q,稱(Q,K)為知識(shí)結(jié)構(gòu)(knowledge structure),記為

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

其中每一個(gè)Ki?Q。

在問(wèn)題域Q明確的情況下，有時(shí)也只用K表示知識(shí)結(jié)構(gòu)。

例2續(xù)例1，若K1={?,Q},則(Q,K1)為Q上最粗的知識(shí)結(jié)構(gòu); 令K2=P(Q)表示取Q的全冪集,則(Q,K2)為Q上最細(xì)的知識(shí)結(jié)構(gòu); 令K3={?,{q1,q2},Q},則(Q,K3)為Q上通常的知識(shí)結(jié)構(gòu)。顯然有:

(Q,K1) ?(Q,K3)?(Q,K2)。

定義4[14]設(shè)(Q,K)為知識(shí)結(jié)構(gòu),若K對(duì)有限并封閉,即

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

則稱(Q,K)為知識(shí)空間(knowledge space),或直接稱K為知識(shí)空間。

定義5[9]若G′包含G中所有有限個(gè)元素的并組成的集合,則稱集族G′是G的張成(span),記為S(G) =G′,或稱G張成G′。

由S(G)的定義知S(G)是并封閉的。

定義6[9]設(shè)集族F是并封閉的,若B是張成F的最小子集族,則稱B為F的基(base),即S(B) =F。

通常，?可看作是B中空子集族的并,因此約定??B。其次,定義6中最小子集族是指關(guān)于包含關(guān)系“?”的最小子集族:即對(duì)于任意H?B且S(H) =F,則有H=B。此外B中的任何一個(gè)集合K,均不能由B中其它集合的并集表示。

本文稱知識(shí)空間的基為知識(shí)基(knowledge base)。

一般來(lái)講,我們考慮的對(duì)象是K,即包含空集?和全集Q的知識(shí)狀態(tài)集族,因此,即使Q取無(wú)限問(wèn)題域,只要K取有限的知識(shí)狀態(tài)集族,這樣的知識(shí)結(jié)構(gòu)也是我們考慮的重要對(duì)象。

定義7[9]當(dāng)Q有限時(shí),稱知識(shí)結(jié)構(gòu)(Q,K)是有限的(finite)。當(dāng)K有限時(shí),稱知識(shí)結(jié)構(gòu)(Q,K)是實(shí)質(zhì)有限的(essentially finite)。

由定義7可知: 若知識(shí)結(jié)構(gòu)(Q,K)是有限的,則它也是實(shí)質(zhì)有限的,反之不然。如取Q=Z,Z是全體非負(fù)整數(shù)的集合,取K={?, {2k:k∈Z},Q},則(Q,K)是實(shí)質(zhì)有限的,但不是有限的知識(shí)結(jié)構(gòu)。

定理1[9]任何實(shí)質(zhì)有限的知識(shí)空間有知識(shí)基。

定理2[9]設(shè)B為知識(shí)空間(Q, K)的知識(shí)基,則對(duì)任意張成K的集族F,都有B?F。

由定理1和定理2可知: 有限知識(shí)空間和實(shí)質(zhì)有限知識(shí)空間都存在唯一的知識(shí)基。然而,下面例3說(shuō)明了并非所有知識(shí)空間都存在知識(shí)基。

例3實(shí)數(shù)R中所有的開子集構(gòu)成的集族K是一個(gè)知識(shí)空間。K可由所有端點(diǎn)為有理數(shù)的開區(qū)間所構(gòu)成的集族F1張成,也可由所有端點(diǎn)為無(wú)理數(shù)的開區(qū)間所構(gòu)成的集族F2張成。若K有知識(shí)基B,則由定理2知B?F1且B?F2,則B?F1∩F2=?,矛盾。故知識(shí)空間K沒(méi)有知識(shí)基。

定理3設(shè)B為知識(shí)空間(Q, H)和(Q,H ′)的一個(gè)知識(shí)基,則H=H′。

證明設(shè)K∈H,因?yàn)锽為知識(shí)空間(Q, H)的一個(gè)基,所以存在B的子集族F使得K=∪F。又因?yàn)锽同時(shí)也為知識(shí)空間(Q, H′)的一個(gè)基,所以K=∪F∈H′,故H=H′。

由定理3知，當(dāng)知識(shí)基B確定時(shí),由該知識(shí)基可生成唯一的知識(shí)空間(Q, K),這為下文由知識(shí)基生成知識(shí)空間提供了理論依據(jù)。

定義8[3]設(shè)F是問(wèn)題域Q的非空子集族,q∈∪F，F(xiàn)中包含q的最小集合稱為元素q的一個(gè)原子(atom)。

例4在知識(shí)空間

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

中,知識(shí)狀態(tài){b,c}是元素b的一個(gè)原子,同時(shí)也是元素c的一個(gè)原子。元素b有兩個(gè)原子:{a,b}和{b,c}。元素a只有一個(gè)原子{a}(雖然a也屬于原子{a,b},但知識(shí)狀態(tài){a,b}不是元素a的原子)。

然而,對(duì)于知識(shí)空間的知識(shí)基B,問(wèn)題域的每個(gè)問(wèn)題在B中不一定有原子。

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

由此可知,尋找知識(shí)基的過(guò)程就是找出知識(shí)空間的所有問(wèn)題的原子。

1.2 在知識(shí)空間中尋找知識(shí)基

本子節(jié)介紹1993年Dowling[3]提出的計(jì)算知識(shí)基的方法。如下所述:

第1步記知識(shí)空間為(Q, K),其中

Q={q1,q2,…,qm}

有m個(gè)問(wèn)題,K={K1,K2, …,Kn}有n個(gè)知識(shí)狀態(tài),按下標(biāo)從小到大的順序列出所有問(wèn)題元素q1,…，qm作為矩陣的列,列出所有的知識(shí)狀態(tài)K1，…，Kn作為矩陣的行,且滿足:當(dāng)Ki?Kk時(shí)有i≤k對(duì)任意i,k∈{1, …,n}成立(根據(jù)包含關(guān)系按照單調(diào)不減的順序列出知識(shí)狀態(tài),狀態(tài)之間沒(méi)有包含關(guān)系的,可以隨機(jī)排列),這樣形成一個(gè)n×m的矩陣,記為T=(Tij)(1 ≤i≤n,1 ≤j≤m)。

第2步初始化,若qj∈Ki,則Tij取“*”;否則,Tij取“-”。

第3步對(duì)于第二步中得到的值T=(Tij),若存在一個(gè)p,1≤p

第4步取至少包含一個(gè)“*”的行對(duì)應(yīng)的知識(shí)狀態(tài)Ki作為構(gòu)成知識(shí)基的一個(gè)元素,所有這樣的Ki構(gòu)成的集族就是知識(shí)基,每一個(gè)Ki都是原子。

例6設(shè)知識(shí)空間

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

其中Q={a,b,c}。

初始化形成的矩陣如表1所示。

表1 初始化得到矩陣TTab.1 The initial values of the array T

根據(jù)算法的第3步: 從a這一列來(lái)看,有{a} ?{a,b}和{a} ?{a,b,c},所以把T31和T51的值由“*”變?yōu)椤?”。而對(duì)于b這一列來(lái)看,有{a,b}?{a,b,c}({b,c}?{a,b,c}),所以把T52的值由“*”變?yōu)椤?”,因{a,b}與{b,c}之間沒(méi)有包含關(guān)系,所以T32,T42的值“*”保持不變。從c這一列來(lái)看,有{b,c}?{a,b,c},所以把T53的值由“*”變?yōu)椤?”。

表2 最終得到矩陣TTab.2 The final values of the array T

根據(jù)算法的第4步至少包含一個(gè)“*”的知識(shí)狀態(tài)Ki作為構(gòu)成知識(shí)基的一個(gè)元素,如表2所求的知識(shí)基是

B={{a}, {a,b}, {b,c}}。

1.3 由知識(shí)基生成知識(shí)空間

本節(jié)我們總結(jié)由Doignon給出的一個(gè)由知識(shí)基生成知識(shí)空間的算法。該算法受到Dowling[15]的啟發(fā),Doignon[7]改進(jìn)了思想并提高了效率。

設(shè)B是某個(gè)知識(shí)空間(Q, K)的知識(shí)基,B包含n個(gè)知識(shí)狀態(tài),記作

B={B1,B2, …,Bn}。

該算法由一系列的步驟生成關(guān)于包含關(guān)系單調(diào)遞增的狀態(tài)序列的集族,最后得到相應(yīng)的知識(shí)空間。

第1步把這些知識(shí)狀態(tài)按照其元素個(gè)數(shù)由小到大排序,若狀態(tài)中元素個(gè)數(shù)相同則可以任意排列。

第2步設(shè)G0={?},對(duì)于i=1, …,n,取Gi為Gi-1∪{Bi}生成的知識(shí)空間,重復(fù)出現(xiàn)的知識(shí)狀態(tài)只保留一個(gè)。

第3步經(jīng)過(guò)n次歸納得到Gn為B={B1,B2, …,Bn}所生成的知識(shí)空間。

例7設(shè)B={{a}, , {a,c}, {b,d}}為某個(gè)知識(shí)基。下表給出知識(shí)空間G的值。如表3經(jīng)過(guò)上述3步我們得到:由基

{{a}, , {a,c}, {b,d}}

生成的知識(shí)空間是

G={{?}, {a}, ,{a,b}, {a,c}, {b,d}, {a,b,c},{a,b,d}, {a,b,c,d}}

還有一種方式在具體操作過(guò)程中每一步只需保存與上一步的不同集合,最后再把所有狀態(tài)放在一起構(gòu)成知識(shí)基,這樣就避免重復(fù)存儲(chǔ)[9]。

表3 G值的連續(xù)變化表Tab.3 The successive values of G

2 形式背景中的知識(shí)基

1999年B Ganter和R Wille[16]從減少行與列的角度提出了概念的約簡(jiǎn)理論。2005年張文修[17]等提出了概念格的屬性約簡(jiǎn)理論。約簡(jiǎn)就是尋找最小的屬性子集,它能夠完全確定原始形式背景上的概念及其層次結(jié)構(gòu),概念格約簡(jiǎn)使得形式背景中隱含知識(shí)的發(fā)現(xiàn)變得更容易,也使得這些知識(shí)的表示變得更簡(jiǎn)潔。這樣最小的屬性子集可看作形式背景的最小生成組(知識(shí)基)。

2.1 形式背景的基本知識(shí)

形式概念與形式背景是形式概念分析的兩個(gè)基本定義,概念的基本觀點(diǎn)是從哲學(xué)中發(fā)展而來(lái)。

定義9[10]稱三元組(U,A,I)為一個(gè)形式背景,其中U={x1,x2, …,xn}為對(duì)象集,A={a1,a2, …,am}為屬性集,每一個(gè)xi(i≤n)稱為一個(gè)對(duì)象,每個(gè)aj(j≤m)稱為一個(gè)屬性,I為U和A之間的二元關(guān)系,I?U×A,若(x,a)∈I,則稱x具有屬性a,記為xIa。

定義10[10]設(shè)(U,A,I)為形式背景,在對(duì)象集X?U和屬性集B?A上分別定義運(yùn)算

X*={a|a∈A, ?x∈X,xIa};

B*={x|x∈U, ?a∈B,xIa}。

如果一個(gè)二元組(X,B)滿足X*=B且X=B*,則稱(X,B)是一個(gè)形式概念,簡(jiǎn)稱概念,其中X稱為概念的外延,B稱為概念的內(nèi)涵。

定義11[10]形式背景(U,A,I)上的所有概念可以用“≤”來(lái)定義它們之間的偏序關(guān)系:

(X1,B1)≤(X2,B2)?X1?X2(B1?B2)

形式背景(U,A,I)的所有概念的集合記為L(zhǎng)(U,A,I)，稱為概念格,其上下確界定義如下:

(X1,B1)∧(X2,B2)=((X1∧X2), (B1∨B2)**)，

(X1,B1)∨(X2,B2)=((X1∨X2)**, (B1∧B2))。

容易驗(yàn)證概念格L(U,A,I)是完備格。

2.2 基于知識(shí)基的概念格屬性約簡(jiǎn)方法

定義12[17]設(shè)L(U,A1,I1)和L(U,A2,I2)是兩個(gè)概念格,如果(X,B)∈L(U,A2,I2),總存在(X′,B′)∈L(U,A1,I1),使得X=X′,則稱L(U,A1,I1)細(xì)于L(U,A2,I2),記作L(U,A1,I1)≤L(U,A2,I2)。

如果L(U,A1,I1)≤L(U,A2,I2)且

L(U,A2,I2)≤L(U,A1,I1),那么這兩個(gè)概念格同構(gòu),記作L(U,A2,I2)?L(U,A1,I1)。

注1)L(U,A1,I1)≤L(U,A2,I2)當(dāng)且僅當(dāng)LU(U,A1,I1)?LU(U,A2,I2)；

2)L(U,A2,I2)?L(U,A1,I1)當(dāng)且僅當(dāng)LU(U,A1,I1)=LU(U,A2,I2)。

定義13[17]對(duì)于形式背景(U,A,I),如果存在屬性集D?A使得

L(U,D,ID) ?L(U,A,I),

則稱D是(U,A,I)的協(xié)調(diào)集。若進(jìn)一步?d∈D,有

L(U,D-j5i0abt0b,ID-j5i0abt0b) ≠L(U,A,I),

則稱D是(U,A,I)的約簡(jiǎn)。

形式背景(U,A,I)的所有約簡(jiǎn)為{Di|i∈τ},τ為指標(biāo)集,可將屬性A分為3類[17]:

絕對(duì)必要屬性 (核心屬性)

相對(duì)必要屬性

絕對(duì)不必要屬性

需要注意的是:任何形式背景(U,A,I),其約簡(jiǎn)集一定存在且不一定唯一。2005年張文修[17]等給出了概念格約簡(jiǎn)的判定定理,并通過(guò)構(gòu)造辨識(shí)矩陣給出了約簡(jiǎn)的方法。

定義14[17]設(shè)(U,A,I)為形式背景,(Xi,Bi)，(Xj,Bj)∈L(U,A,I)，稱DISFC((Xi,Bi), (Xj,Bj))=Bi∪Bj-Bi∩Bj為(Xi,Bi)與(Xj,Bj)的可辨識(shí)屬性集。稱

ΛFC={DISFC((Xi,Bi), (Xj,Bj)) |

(Xi,Bi),(Xj,Bj) ∈L(U,A,I)}

為形式背景(U,A,I)的可辨識(shí)屬性矩陣。

定理5[17]設(shè)(U,A,I)為形式背景,?D?A，D≠?,若(Xi,Bi)≠(Xj,Bj),且

(Xi,Bi), (Xj,Bj)∈L(U,A,I),

則下列命題等價(jià):

1)D是協(xié)調(diào)集;

2)Bi∩D≠Bj∩D;

3)D∩DISFC((Xi,Bi), (Xj,Bj)) ≠?(?DISFC((Xi,Bi), (Xj,Bj)) ≠?);

4) 任意B?A,若B∩D=?,則B?ΛFC。

由形式背景的可辨識(shí)屬性矩陣ΛFC,可找出所有的核心屬性[17]。

定理6[17]設(shè)(U,A,I)為形式背景,對(duì)于a∈A,a為核心屬性當(dāng)且僅當(dāng)存在

(Xi,Bi), (Xj,Bj)∈L(U,A,I),

使得

DISFC((Xi,Bi), (Xj,Bj))={a}。

以上辨識(shí)矩陣約簡(jiǎn)理論可具體參考張文修等關(guān)于概念格的屬性約簡(jiǎn)理論[17]。2014年李進(jìn)金、 張燕蘭等[18]從交運(yùn)算封閉性角度提出了一種基于知識(shí)基的約簡(jiǎn)理論。

由形式背景(U,A,I)產(chǎn)生的概念格L(U,A,I),首先是作為概念集合

{(X,B)|X*=B,B*=X,X?U,B?A}，

然后又具有偏序關(guān)系,在此基礎(chǔ)上引入交、并運(yùn)算而形成格。為了確定L(U,A,I),可先確定LU(U,A,I)即每個(gè)形式概念(X,B)的外延X(jué)的集合:

LU(U,A,I)={X|X?U,X**=X},

還可將LU(U,A,I)描述成

LU(U,A,I)={B*|B?A,B**=B},

下面我們考慮基于知識(shí)基的概念格屬性約簡(jiǎn)方法。

定義15[18]設(shè)(U,A,I)為形式背景,a∈A,若存在D?A,a?D使得

則稱a為交式可約元。

關(guān)系R={(a,b) ∈A×A|a*=b*}是A上的等價(jià)關(guān)系,由此得到A上的一個(gè)劃分:其中

A/R={[a]R|a∈A},

[a]R={b∈A|(a,b) ∈R}。

定理7[18]設(shè)(U,A,I)是形式背景,a∈A,若[a]R不是單元素集合,則[a]R中元素皆為交式可約元,而且(A-[a]R) ∪ {a}為協(xié)調(diào)集。

定理8[18]設(shè)(U,A,I)是形式背景,對(duì)任意a,b∈A,若a*=b*,則

{B*|B?A}={B*|B?A-{a}}。

推論1[18]設(shè)(U,A,I)是形式背景,若a1,a2,…,ak∈A且a1*=a2*=…=ak*。記

A1={a1,a2,…,ak},

則(A-A1) ∪ {ai} (1 ≤i≤k)皆為協(xié)調(diào)集。

推論2[18]設(shè)(U,A,I)是形式背景,則核心屬性是A/R中等價(jià)類為單元集的屬性。

定理10[13]設(shè)(U,A,I)為形式背景,若A/R={[ai1], [ai2], …, [aik]}的等價(jià)類皆為單元素集(從而k=|A|),則形式背景(U,A,IA)的屬性約簡(jiǎn)集唯一。

根據(jù)前面得到的結(jié)果,可以給出求形式背景(U,A,I)約簡(jiǎn)集的一種方法:

1) 求出{a*|a∈A};

2) 求出A/R={[ai1], [ai2], …, [aik]};

3) 從[ait]中選一個(gè)代表元ait(1 ≤t≤k)組成屬性集A′={ai′| 1 ≤t≤k}。從{a*|a∈A}中找出{a*|a∈A′}。

4)對(duì){a*|a∈A′}中的a*依|a*|由大到小排序,|a*|相等的次序可隨意。排在后面的可由排在前面的經(jīng)交運(yùn)算生成反之不一定成立。

6)如果前面若干個(gè)a*的交生成后面某個(gè)b*,則將b從A′中刪去,將b*從

{a*|a∈A′}

中刪去。

總之,在通過(guò){a*|a∈A′}交運(yùn)算生成{B*|B?A′}的過(guò)程中,發(fā)現(xiàn)可約元而約去,得到LU(U,A,I)的最小交式生成組D(知識(shí)基),即是(U,A,I)的屬性約簡(jiǎn)集,并可由它得到所有屬性約簡(jiǎn)集。這就是基于知識(shí)基的概念格屬性約簡(jiǎn)方法。

對(duì)偶地,可以討論形式背景(U,A,I)導(dǎo)出的概念格L(U,A,I)的所有形式概念的內(nèi)涵組成的集合,記為L(zhǎng)A(U,A,L),則

LA(U,A,I)={B?A|B**=B}=

{X*|X?U, |X**=X}。

LA(U,A,I)作為交封閉系統(tǒng)有交式生成組{x*|x∈U},討論LA(U,A,I)的對(duì)象約簡(jiǎn)問(wèn)題,亦即探討LA(U,A,I)的交式最小生成組問(wèn)題,引入U(xiǎn)上的等價(jià)關(guān)系

R*={(x,y) ∈U×U|x*=y*},

其中

U/R*={[xi]R*|xi∈U},

[xi]R*={y∈U|(x,y) ∈R*}。

則稱x′是可約對(duì)象,去掉可約對(duì)象的過(guò)程也是一種約簡(jiǎn)過(guò)程。

{x*|x∈U}構(gòu)成A的覆蓋,{a*|a∈A}構(gòu)成U的覆蓋,{x*|x∈U}是LA(U,A,I)的交式生成組,{a*|a∈A}是LU(U,A,I)的交式生成組。

借助于粗糙集中的上、下近似算子概念,用□表示下近似,用◇表示上近似,對(duì)于X?U及B?A有

X□={a∈A|a*?X},

X={a∈A|a*∩X≠?},

B□={x∈U|x*?B},

B={x∈U|x*∩B≠?}。

定義16[19]設(shè)(U,A,I)為形式背景,若X=B,B=X□,稱(X,B)為面向?qū)ο蟾拍?若X=B□，B=X,稱 (X,B)為面向?qū)傩愿拍睢?/p>

更多有關(guān)面向?qū)ο蟾拍罡?面向?qū)傩愿拍罡竦膮f(xié)調(diào)集、約簡(jiǎn)集、基于知識(shí)基的約簡(jiǎn)方法等可參考有關(guān)文獻(xiàn)[20-22]。

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

Rusch和Wille[12]指出知識(shí)空間理論和形式概念分析之間可以建立有效的聯(lián)系。2010年Spoto和Stefanutti[13]在此基礎(chǔ)上繼續(xù)將KST與FCA相結(jié)合,通過(guò)一個(gè)病人診斷的實(shí)際例子來(lái)闡明已獲得的知識(shí)結(jié)構(gòu)有效性的方法。并引入BLIM(基本局部依賴模型)來(lái)估計(jì)已獲知的知識(shí)結(jié)構(gòu),提出對(duì)于BLIM參數(shù)新的解釋,適用于測(cè)試的可靠性和有效性。2017年Wild[23]通過(guò)對(duì)比Doignon關(guān)于學(xué)習(xí)空間的構(gòu)造和D Gainer關(guān)于最小問(wèn)題的形成[24],強(qiáng)化形式概念分析在學(xué)習(xí)問(wèn)詢方法中的應(yīng)用,將Wille等人關(guān)于構(gòu)建知識(shí)空間的方法加強(qiáng)到學(xué)習(xí)空間中[23]。J P Doignon和J C Falmagne從教學(xué)方法論觀點(diǎn)出發(fā)提出學(xué)習(xí)空間的概念[25],這是對(duì)知識(shí)空間的一種特殊化處理,Doignon接著又研究了怎樣構(gòu)造學(xué)習(xí)空間[26]。Eppstein研究了具有良級(jí)性質(zhì)的并封閉集族[27],Cosyn和Uzun從良好級(jí)配性對(duì)學(xué)習(xí)空間進(jìn)行性質(zhì)研究[28]。

按照FCA的相關(guān)理論,在形式背景(P,Q,I)中,為保持形式上的對(duì)應(yīng),稱P為對(duì)象集,Q為屬性集,只要二元關(guān)系I確定,那么就能由知識(shí)空間(Q, K)構(gòu)造出形式背景(P,Q,I)即(Q, K) →(P,Q,I) 。由于形式背景內(nèi)涵是交封閉的,形式背景內(nèi)涵的補(bǔ)集總是并封閉的,那么對(duì)形式背景(P,Q,I),內(nèi)涵的補(bǔ)集形成Q上的一個(gè)知識(shí)空間,即(P,Q,I) →(Q, K)。本文的形式背景又稱為知識(shí)背景,它是賦予教育意義下一種特殊的形式背景?，F(xiàn)只需闡明知識(shí)背景中概念、外延和內(nèi)涵的表現(xiàn)形式,就可以由知識(shí)背景(P,Q,I)誘導(dǎo)出知識(shí)空間(Q, K)。

3.1 由知識(shí)空間構(gòu)造形式背景

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

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

Rusch和Wille在此定義了一種特殊的形式背景。接下來(lái)的問(wèn)題是如何通過(guò)知識(shí)空間(Q, K)轉(zhuǎn)化成知識(shí)背景(P,Q,I),并且這樣的轉(zhuǎn)化恰好使得該知識(shí)空間(Q, K)的知識(shí)狀態(tài)由所形成的知識(shí)背景(P,Q,I)的所有概念內(nèi)涵的補(bǔ)集組成。為了解決這一問(wèn)題,需假設(shè)知識(shí)空間(Q, K)中的每一個(gè)知識(shí)狀態(tài)代表某個(gè)測(cè)試對(duì)象能解決的問(wèn)題集,這樣就建立了K的所有知識(shí)狀態(tài)與測(cè)試對(duì)象集P之間的一一對(duì)應(yīng)。由知識(shí)空間(Q, K)構(gòu)造知識(shí)背景(P,Q,I)的過(guò)程為:

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

定理11[12]知識(shí)背景(P,Q,I)與形式背景(K,Q, ?)是同構(gòu)的。其中K是知識(shí)狀態(tài)集族,Q是問(wèn)題集,?是K×Q上的二元關(guān)系,表示某個(gè)問(wèn)題q?K,其中q∈Q,K∈K。

定義19[12]設(shè)知識(shí)背景為(P,Q,I),且A?P,B?Q算子A*={q∈Q|pIq,?p∈A},B*={p∈A|pIq,?q∈B},若A=B*并且B=A*,則稱二元組(A,B)是一個(gè)知識(shí)概念(knowledge concept),簡(jiǎn)稱概念,A是概念的外延,B是概念的內(nèi)涵。

對(duì)于由知識(shí)空間構(gòu)造的形式背景,還可對(duì)其進(jìn)行約簡(jiǎn),這里舉一個(gè)例子說(shuō)明。1993年Korossy[29]通過(guò)實(shí)際測(cè)試,選取了初等幾何學(xué)中與畢達(dá)哥拉斯定理有關(guān)的五個(gè)問(wèn)題,記為Q={1, 2, 3, 4, 5},這里不對(duì)這五個(gè)問(wèn)題的具體內(nèi)容闡述,1999年Korossy從能力和技能方面對(duì)知識(shí)空間進(jìn)行研究[30]。Korossy通過(guò)實(shí)驗(yàn)驗(yàn)證分析得到知識(shí)空間(Q, K),其中

K={?, {1}, {3}, {1, 2}, {1, 3}, {1,4}, {2, 3}, {3,4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4},{1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 3, 4, 5}}

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

表4 由K導(dǎo)出的知識(shí)背景Tab.4 The knowledge context of K

定義20[12]對(duì)于“”、“”和“”，pq表示pIcq并且{p}*是不包含q的極大集。

pq表示pIcq并且{q}*是不包含p的極大集。

例如,在上述知識(shí)背景表4中,滿足(p21):

{p1}*={1, 2, 3, 4, 5}

{p2}*={2, 3, 4, 5}

{p3}*={1, 2, 4, 5}

{p4}*={3, 4, 5}

?

{p14}*={4}

{p15}*=?

滿足 (p21):

{1}*={P1,P3,P7,P8,P12}

{2}*={P1,P2,P3,P5,P6,P8,P11}

{3}*={P1,P2,P4,P6,P10}

{4}*={P1,P2,P3,P4,P5,P7,P9,P14}

{5}*={P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,P12,P13}

表5 約簡(jiǎn)后的知識(shí)背景Tab.5 The reduced knowledge context

顯然,為了獲得知識(shí)空間(Q, K)所對(duì)應(yīng)的知識(shí)背景,只需要對(duì)p2,p3,p4,p6,p7,p8,p14進(jìn)行測(cè)試。這樣由知識(shí)空間(Q, K)構(gòu)造出知識(shí)背景(P,Q,I)與約簡(jiǎn)后的知識(shí)背景有同樣的概念格結(jié)構(gòu)。

3.2 由形式背景構(gòu)建知識(shí)空間

Rusch和Wille指出:在知識(shí)背景(P,Q,I)中,“”、“”和“”運(yùn)算不僅可以對(duì)知識(shí)背景約簡(jiǎn),還可以結(jié)合知識(shí)空間中原子的定義,通過(guò)原子構(gòu)造知識(shí)基,進(jìn)而生成知識(shí)空間。

通過(guò)專家問(wèn)詢學(xué)生作答[31-32]而形成的知識(shí)背景(P,Q,I)中問(wèn)題q的原子可定義為不包含q的最大內(nèi)涵的補(bǔ)集,記為σ(q) ={Q{p}*|p∈P,q∈Q,pq}。那么,知識(shí)背景(P,Q,I)可以由所有原子σ(q)來(lái)描述。

在上述知識(shí)空間(Q, K)中,由KST知問(wèn)題2的原子是{1, 2}和{2, 3}。由表4知在知識(shí)背景(P,Q,I)中p42，{p4}*={3, 4, 5}和p72，{p7}*={1, 4, 5},因此2的原子是p4與p7分別對(duì)應(yīng)的知識(shí)狀態(tài),也即是{1, 2}和{2, 3}。由此可總結(jié)出:知識(shí)空間的所有原子構(gòu)成的知識(shí)基可以在對(duì)應(yīng)的知識(shí)背景下通過(guò)運(yùn)算“”，“”和“”完全決定。反之,如果所有原子σ(q),q∈Q構(gòu)成的知識(shí)基已經(jīng)確定,那么對(duì)應(yīng)的約簡(jiǎn)知識(shí)背景可由與(P,Q,I)同構(gòu)的形式背景Q, ?)完全確定[33]。表6是由Korossy通過(guò)測(cè)試所得的知識(shí)背景為例。

表6 由知識(shí)背景導(dǎo)出原子Tab.6 The knowledge context derive atoms

σ(1) ={1}

σ(2) ={{1, 2}, {2, 3}}

σ(3) ={3}

σ(4) ={{1, 4}, {3, 4}}

σ(5) ={{1, 2, 3, 5}}

由此構(gòu)成的集族

{{1},{3},{1,2},{2,3},{1,4},{3,4},{1,2,3,5}}

就是所生成知識(shí)空間的知識(shí)基。由此知識(shí)背景構(gòu)造的知識(shí)空間是:

K={?, {1}, {3}, {1, 2}, {1, 3}, {1,4}, {2, 3}, {3,4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4},{1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 3, 4, 5}}

4 結(jié) 語(yǔ)

本文介紹了尋找知識(shí)空間的基和由給定的基生成知識(shí)空間的方法，基于知識(shí)基的概念格屬性約簡(jiǎn)理論,以及通過(guò)知識(shí)基建立了形式背景與知識(shí)空間的一些聯(lián)系。如何進(jìn)一步將形式概念分析方法應(yīng)用到知識(shí)空間,以及如何進(jìn)一步挖掘它們之間更深遠(yuǎn)的聯(lián)系有待將來(lái)的工作中不斷完善。