簡單閉包空間與形式背景的聯系

張文娟

（閩南師范大學數學與統計學院,福建漳州363000）

1985年，Doignon 等[1]提出知識空間理論(Knowledge space theory,簡稱“KST”)[1],深受眾多學者的關注.該理論通過分析學生對一系列問題的回答來確定學生的認知水平,因此在測評學生知識和個性化學習中起著舉足輕重的作用.隨后,眾多學者對該理論進行了拓展.孫波等[2]提出了包含技能結構、技能空間以及技能層次等相關概念的擴展知識空間理論,Heller等[3-4]證明了一類特殊的CDMs(認知診斷模型)等價于概率知識空間模型論;Luca等[5-6]將二分知識空間的理論推廣到了多分知識空間理論.

1982年，Wille[7]提出形式概念分析(FCA)理論,該理論是處理數據分析與規則提取的一種有效工具.屬性約簡作為其重要研究內容之一,它探討了保持形式概念所有概念外延集不變的情況下，剔除冗余屬性.針對屬性約簡的方式,張文修等[8]引入保持格結構不變的屬性約簡,Wu等[9]設計了形式背景的粒約簡方法,Wang 等[10]研究了基于交(并)不可約元的概念格屬性約簡方法.通過對上述4 類約簡理論的研究,Li等[11]指出了保持格結構不變與保持交不可約元的等價性.

1996年，Rusch 等[12]首次建立了知識空間理論與形式概念分析之間的聯系.Spoto 等[13]以合取技能映射為研究對象,構建了合取技能映射與形式背景的聯系.而后,李進金等[14]通過知識基構建了知識空間與形式背景的聯系.Nicotra等[15]系統地分析了形式概念分析,知識空間理論與認知診斷理論的聯系與區別.在此基礎上,周銀鳳等[16]探討了形式背景下的技能約簡與評估,

本文旨在深入研究簡單閉包空間和形式概念分析之間的聯系,根據知識基的對偶集A 與形式背景中交不可約元的等價性,論證了合取模型下技能約簡的實質是保持形式背景最小交式生成組不變的理論,而后給出了一種技能約簡的方法,豐富了形式概念分析在知識空間中的應用.

1 預備知識

1.1 知識空間基本理論

定義1[17]設Q為非空問題集,K為Q的K一些子集構成的集族,若K包含?,Q與其它知識狀態.則稱（Q,K）為知識結構,這里知識狀態指的是個體在理想狀態下能夠正確答對問題集Q中的問題所構成集合.在問題域Q確定的情況下,可簡稱K為知識結構.

所謂理想狀態指的是學生在沒有受到外部壓力或任何躁動情緒干擾的情況,沒有因粗心導致的錯誤或僥幸猜對的情況.

定義2[17]設（Q,K）為知識結構,若K 有限,且對任意K1,K2∈K,有K1?K2∈K,則稱（Q,K）為知識空間,或簡稱K為知識空間.

定義3[18]若G′是由G中所有有限個元素并構成的集合,則稱集族G張成(span)G′,記為S（G）=G′.

由定義3 知,S（G）滿足“并”封閉. 且一個“并”封閉集族F 的基是可張成F 的極小子集族B, 其中,B ?F.由于基的極小性,故??B.類似地,知識基B 可張成K.需要注意的是:若K 為有限的知識空間,則K 有且只有一個知識基,對偶地L 也是有限的.基于上述知識,本文僅對有限條件下的知識空間與簡單閉包空間進行研究.

定義4[18]設F是非空的集族,對于任意的q∈?F,稱F中包含q的極小集為問題q的原子,記為σ(q).若對于某個q∈?F,X為q的原子,則稱集合X∈F為一個原子.

通過定義4可知,問題的原子不唯一,在有限知識結構中,每個問題q至少有一個原子.若B是知識空間K的知識基,則B是由K中所有原子構成的集族[19].

定義5[19]設Q為非空問題集,S為非空技能集,τ:Q→2S{ ?}.則稱三元組（Q,S,τ）是一個技能映射.其中,對于任意的q∈Q,S的子集τ(q) 是與問題q求解相關的技能集.

事實上,對于給定的技能映射,主要有析取模型與合取模型兩類.針對上述技能映射,在析取模型下有如下定義:若T為S的非空子集,則技能集T可確定的知識狀態顯然該模型表現為“或”的形式,即若T中存在某個與問題q求解相關的技能s∈T,則問題q屬于技能集T確定的知識狀態中.對偶地,合取模型下,技能集T可確定的知識狀態此模型表現為“且”的形式,即技能集T只有包含與問題q求解相關的所有技能時,才有問題q屬于技能集T確定的知識狀態.

遍歷S的全部子集分別可得析取模型與合取模型確定的知識結構,且在析取模型下確定的知識結構為知識空間,合取模型下確定的知識結構為簡單閉包空間,二者是對偶結構.

1.2 形式背景基本理論

定義6[20]稱三元組(U,A,I)為形式背景,其中是對象集,是屬性集,I?U×A是U和A的二元關系.對于任意x∈U,m∈A,若(x,m)∈I則表示對象x有屬性m;(x,m)?I則表示對象x不具有屬性m.

對任意X?U,B?A,記X*={m∈A:(x,m)∈I,?x∈X};B*={x∈U:(x,m)∈I,?m∈B}為Wille 定義的一對算子.

若二元組(X,B)滿足X*=B和B*=X,則稱(X,B)為(U,A,I)的形式概念.其中X和B分別稱為形式概念的外延和內涵.所有形式概念的集合記為L(U,A,I),稱為概念格.

定義7[21]若對于任意(X1,B1),(X2,B2)∈L(U,A,I), 引入二元關系“≤”定義兩個概念間的偏序關系:(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(U),A,I是完備格.

1.3 形式背景與簡單閉包空間的聯系

定義8[12]設Q={q1,q2,…,qm} 為非空問題集,qi∈Q為一個問題;S={s1,s2,…,sn} 為非空技能集,si∈S為一個技能,R為Q和S之間的二元關系,R?Q×S,則稱三元組(Q,S,R)為(合取)技能映射(Q,S,f)相應的一個形式背景.且滿足?(q,s)∈R?s?f(q),即技能s不能解決問題q,其中,f(q)表示析取技能映射下與問題q求解相關的技能集.

注由定義8可知,在合取模型下誘導的形式背景是一個反背景,其主要研究對象為問題和技能.特別地,本文稱上述形式背景為技能背景.

定義9設(Q,S,R)是技能背景, 在問題集X?Q和技能集Y?S上定義如下運算:X*={s|s∈S,?q∈X,s?f(q)};Y*={q|q∈Q,?s∈Y,f(q)?SY} .其中X*表示與X中所有問題求解無關的技能集,Y*表示與Y中所有技能都不能解決的問題集.

推論1若LQ(Q,S,R)為技能背景的全體外延集, 則LQ(Q,S,R)為簡單閉包空間, 且有知識空間K={(QL)∈2Q|L∈LQ(Q,S,R)} .

證明由技能背景中概念的定義顯然有?,Q∈LQ(Q,S,R),任意(X1,B1),(X2,B2),其外延屬于簡單閉包空間,而概念本身滿足交運算封閉,因此全體外延滿足交運算封閉,即LQ(Q,S,R)為簡單閉包空間.故知識空間K={(QL)∈2Q|L∈LQ(Q,S,R)} .

2 在簡單閉包空間中知識基的對偶集A的構建

Spoto 等構建了合取模型與形式概念分析之間的聯系,但并未對二者的聯系進行深入的研究.基于上述研究,本文主要結合概念格中交不可約元的概念深入探討二者的聯系.

在已有的析取模型下,技能約簡的核心是保持知識基不變,且若某個極小技能映射可確定知識空間當且僅當知識基的基數與極小技能集的基數相同.由簡單閉包空間與知識空間的對偶性,首先探討知識基對偶集A的構建.

推論2若（Q,L）是知識空間（Q,K）的對偶空間(即簡單閉包空間),則對于任意q∈Q,問題q的原子可以表示為L中不包含問題q的極大知識狀態集族的補集.

證明任意q∈Q,σ(q)為K 中包含問題q的極小狀態集族, 根據對偶性有此時q不在的任何子集中且中任何子集均為不包含q的極大知識狀態集族.故而問題q的原子可以表示為L中不包含問題q的極大知識狀態集族的補集.

定義10設（Q,L）是簡單閉包空間,對任意q∈Q,記δ(q)為L中不包含問題q的極大知識狀態集族.

推論3若B為知識空間（Q,K）的知識基,記A={δ(q)|q∈Q} ,則有｜A｜=｜B｜,這里 |?|代表基數.

證明由于知識基可由Q中所有的σ(q)構成,而任意σ(q)?B,由推論2知存在δ(q)?A,滿足σ(q)=遍歷所有的問題q,根據對偶性顯然有｜B｜=｜A｜.

定理1[19]若知識空間可由某個極小技能映射所確定當且僅當該知識空間有基,且知識基的個數與極小技能集的基數相同.此外,確定同一個知識空間的任意兩個極小技能映射是同構的.同樣地,可由任意技能映射所確定的有基的知識空間在其極小技能映射下仍可確定此空間.

定理2設（Q,L）與（Q,K）是同一個極小技能映射確定的簡單閉包空間與知識空間,則（Q,L）可由該極小技能映射確定當且僅當A的基數與極小技能集的基數相同.

證明設技能映射為(Q,S,τ),任意s∈S,記K(s)為析取模型下技能{s} 確定的知識狀態,L(s)為合取模型下技能{s} 確定的知識狀態.則q∈K(s)?s∈τ(q)滿足析取模型,q∈L(s)?s=τ(q)滿足合取模型.對于任意L∈L,記T為S中可確定知識狀態L的技能集,則對于任意問題q,有q∈L?τ(q)?T??s∈ST:且B ={K(s)|s∈ST} 為知識基.A={K′(s)|s∈ST} 恰為不包含問題的極大集.而由定理1 與推論3 可得A的基數與極小技能映射的基數相同.

例1設Q1={a,b,c,d,e} ,S1={s,t,u,v} ,定義技能映射為τ:Q1→2S1,其中τ(a)={s,t} ,τ(c)={v} ,τ(b)={t,u} ,τ(d)={s,v} ,τ(e)={t,u,v} .

經過計算可得:知識空間K={{a,d} ,{b,e} ,{a,b,e} ,{c,d,e} ,{a,b,d,e} ,{a,c,d,e} ,{b,c,d,e} ,Q1,?},簡單閉包空間L={{b,c,e} ,{a,c,d} ,{c,d} ,{a,b} ,{c} , ,{a} ,Q1,?}. 此時知識基B ={{a,d} ,{b,e} ,{a,b,e} ,{c,d,e} }, A={{b,c,e} ,{a,c,d} ,{c,d} ,{a,b} }. 取L={c,d} , 則T={s,v} , 即其對偶其中,{a,b,e} ,{b,e} ∈B,{c,d} ,{a,c,d} ∈A.

3 交不可約元與知識基的對偶集的聯系

由推論1 可知技能背景全體外延集構成了簡單閉包空間,且簡單閉包空間滿足交封閉性.又因為基于知識基理論可探討知識空間的技能約簡問題.對偶地,本文考慮在簡單閉包空間中尋找知識基的對偶集,在此基礎上探討簡單閉包空間約簡問題.實際上,文獻[11]中提出保持交不可約元的概念格約簡與保持格約簡的結果一致.因此可從形式概念分析理論中交不可約元的概念出發,探討A的構建問題.

2014年，李進金等[22]從交運算封閉性的角度提出了一種形式背景屬性約簡理論.形式背景(U,A,I)產生概念格L(U,A,I), 每個形式概念(X,B)的外延X構成集合:LU(U,A,I)={X|X?U,X**=X}, 同樣地,LA(U,A,I)={B|B?A,B**=B}, 即LU(U,A,I)是不同的B?的集合(B?A). 又因此,LU(U,A,I)又是{a?|a∈A}經交運算形成的集合,于是{a?|a∈A}可以看成是LU(U,A,I)的生成組.

命題1{s*|s∈S}是LQ(Q,S,R)的交式生成組,對任意L∈LQ(Q,S,R),存在S′?S,使得

定義11設(Q,S,R)為技能背景,若對于s∈S,存在s′∈S,使得s*=(s′)*,則稱s與s′為同等技能.

事實上,同等技能在技能背景中的作用相同,因此將同等技能剔除后仍不影響A的構建.不妨記剔除后的技能集為S′,此時技能集中同等技能只保留一個.在此基礎上,可探討A的構造.

定義12設(Q,S,R)為技能背景,{s*|s∈S′}是LQ(Q,S,R)的交式生成組. 對任意s∈S′, 存在S″?S′,s?S″,且則稱s*為{s*|s∈S′} 的交可約元,否則稱s*為交不可約元.

注意若s*為交可約元,則表示技能s是可約的.

性質1若s*為交可約元.記則有s*?(s′)*.

定理3設(Q,S,R)為技能背景,s*為{s*|s∈S′} 的交可約元,則對任意q∈Qs*,s*均不是不包含問題q的極大集.

證明s*為交可約元,由性質1 知任意q∈Q(s)*,存在s′∈S′s,使得q∈Q(s′)*?Q(s)*,s*?(s′)*,即s*均不是不包含Q中某個問題q的極大集.

定理4設(Q,S,R)為技能背景,si*為{s*|s∈S′} 中的交不可約元,則si*可表示為不含某個問題q的極大集.

證明對于任意si*為{s*|s∈S′} 交不可約元,存在某個問題q∈Qsi*且滿足si*是不包含某個問題q的極大集.假設存在s1*為交不可約元使得對任意q∈Qs1*滿足s1*不是不包含問題q的極大集.先證其中某個q∈Qs1*,至少存在一個si*,i≠1,且i≤ |S′|滿足si*是不包含問題q的極大集.不妨假設存在技能s2∈S′,滿足q∈Qs2*?Qs1*,s2*為不包含問題q的極大集.但此時有s1*?s2*,由交不可約元定義有s2*為{s*|s∈S′}的交不可約元.即s2*是交不可約元且是不包含問題q的極大集.類似地取遍Qs1*中所有元素,可得不包含問題的極大集必定為交不可約元.而Q不屬于交不可約元,故在所有包含s1*的si*中,有如下情況成立:1)對于一切包含s1*的si*,有s1*?s2*?…?si*成立,其中2,…,i的次序依集合的包含關系排列,則對于任意但由真包含關系,必存在某個qi∈Q(s1)*,但qi?Q(si)*,i≠1,也即(s1)*必是不包含某個問題qi的極大集.2)若對所有包含s1*的si*不存在真包含的關系,也即si*之間是不可比較的,則必有故對任意則有q∈Qs1*,但由真包含關系,必存在某個但故可表示為不含Q中某個問題的極大集.綜上所述,即任意si*為{s*|s∈S′} 的交不可約元,則存在某個問題q∈Qsi*且滿足si*是不包含某個問題q的極大集.

推論4設(Q,S,R)為技能背景,si*為{s*|s∈S′} 中的交不可約元,則Q(si)*均可表示含Q中包含某個問題的極小集.

圖1 概念格L(Q,S2,R)Fig.1 The concept lattice L(Q,S2,R)

證明由推論2與定理4可得.

定理5設(Q,S,R)為技能背景,中的交不可約元,則技能映射在析取模型下確定的知識基B={Qsi*|si*}為交不可約元.

證明因為知識基可由所有包含問題的極小集構成,而由推論4知Q(s)*均可表示含Q中包含某個問題的極小集.而知識基由全體包含問題的極小集構成,遍歷{s*|s∈S′} 中的全體交不可約元可得,知識基}為交不可約元.

例2設(Q2,S2,R2)是技能背景,其中Q2={a,b,c,d,e} ,S2={r,s,t,u,v,w} ,則由此技能背景構造的概念格如表1和圖1.

記技能映射為τ(a)={r,t,u,v} ,τ(b)={s,u,v,w} ,τ(c)={t} ,τ(d)={t,u} ,τ(e)={u} ,從而得閉包空間L ={?,{c} ,{e} ,{c,d,e} ,{b,e} ,{a,c,d,e} ,{b,c,d,e} ,Q2} , K={Q2,{a,b,d,e} ,{a,b,c,d} ,{a,b} ,{a,c,d} , ,{a} ,?} 為與之相對應的知識空間.則知識基B ={{a} , ,{a,c,d} ,{a,b,d,e} },A={{b,c,d,e} ,{a,c,d,e} ,{b,e} ,{c} }.

技能概念如下:(r*,r**)=(b cd e,r),(t*,t**)=(be,rt),(s*,s**)=(w*,w**)=(a cd e,sw),(u*,u**)=(c,rsuvw),(v*,v**)=(cd e,rsvw).由上述知識知計算A 需要剔除技能s或者w,不妨假設剔除技能w后的技能集為S′2.此時有s*?r*=v*,故v*為交可約元.并且可驗證對于a,b∈Q(v)*,有r*是不包含問題a的極大集,s*是不包含問題b的極大集.從而也知交可約元必定是不包含問題的極大狀態集.剔除同等技能集后的交不可約元分別為r*,s*,t*,u*,顯然r*為不含問題a的極大集,經過計算可得,{r*,s*,t*,u*} 均為不含某個問題的極大集.且其對偶B ={{a} , ,{a,c,d} ,{a,b,d,e} }恰為知識空間的基.

表1 技能背景(Q2,S2,R2)Tab.1 A skill context(Q2,S2,R2)

由推論4及知識基的定義知,知識基可由剔除同等技能后交不可約元的補集構成,但剔除同等技能后求交不可約元的方法比較繁瑣.由于同等技能蘊含相同的信息,因此極小技能集的求解可轉化為技能背景中的最小交式生成組的求解,也即極小技能集的求解可轉化為形式背景中最小交式生成組的求解.

例3續例2,根據文獻[22]所提方法求解極小技能集.

顯然交式生成組為{r*,s*,t*,u*,v*,w*} ,且s*=w*;S2/R={[r*],[s*],[t*],[u*],[v*]};取等價類中代表元組成屬性集S2′={r,s,t,u,v} ;對{s?|s∈S2′} 中的s?依 |s?|由大到小排序為r*,s*,v*,t*,u*,且v*=s*?r*,故刪去v.從而有最小交式生成組為{r*,s*,t*,u*} ,與例2結果一致.

4 技能約簡

定義13設(Q,S,R)為技能背景,對于“↙”“↗”和“”,作出如下定義:q↗s表示(q,s)?R并且s*是不包含q的極大集.q↘s表示(q,s)?R并且q*是不包含s的極大集.qs表示同時滿足q↗s與q↘s.

例4設(Q3,S3,R3)是技能背景,其中Q3={1,2,3,4,5,6} ,S3={a,b,c,d,e,f} ,則由此技能背景構造的概念格如表2和圖2-圖3.

表2 技能背景(Q3,S3,R3)Tab.2 A skill context(Q3,S3,R3)

圖2 概念格L(Q3,S3,R3)Fig.2 The concept lattice L(Q3,S3,R3)

圖3 概念格L(Q3,S3,R3)Fig.3 The concept lattice L(Q3,S3,R3)

圖2與圖3分別表示從技能出發構造的概念格與從問題出發構造的概念格,根據上述知識,技能約簡保持交不可約元的外延集不變,類似地,問題約簡是保持交不可約元的內涵集不變.而所在的行、列恰好為不包含某個技能的極大問題集與不包含某個問題的極大技能集,由第三部分知識可知,二者對應于問題集的最小交式生成組與技能集的最小交式生成組,因此剔除不含所在行、列恰好是保持問題集的最小交式生成組與技能集的最小交式生成組不變,故下面給出其約簡方式，如表3-表4.

由于b與f所在列完全相同,故而刪除其中之一對結果沒有影響,故技能約簡集為{a,b,c,d} .

由第3 部分知識,交式生成組{a*,b*,c*,d*,e*,f*} ,且b*=f*;S3/R={[a*],[b*],[c*],[d*],[e*]};取等價類中代表元組成屬性集S3′={a,b,c,d,e} ; 對{a?|a∈S3′} 中的a?依 |a?|由大到小排序為a*,b*,c*,d*,e*, 且e*=b*?d*,故刪去e.最小交式生成組{a*,b*,c*,d*} ,即技能約簡集為{a,b,c,d} .與利用的結果一致.

5 結束語

定義了知識基的對偶集A ,基于保持交不可約元外延集不變的屬性約簡理論,建立交不可約元外延集與A 的等價性.給出合取模型下技能約簡的原理與概念格保持最小交式生成組不變的理論相同.進一步給出了技能約簡的方法,但如何進一步將形式概念分析方法應用到知識空間,以及如何更深次挖掘它們之間的聯系有待在將來的工作中不斷完善.

表3 轉化后的技能背景Tab.3 skill context after coverted

表4 約簡后的技能背景Tab.4 skill context after reduction