基于布爾矩陣的形式背景屬性約簡(jiǎn)

萬(wàn) 青,馬盈倉(cāng),楊小飛

(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

0 引 言

形式概念分析(Formal Concept Analysis, FCA)是德國(guó)數(shù)學(xué)家WILLE于1982年提出的一種數(shù)據(jù)分析理論[1]。該理論所研究的數(shù)據(jù)形式是一個(gè)二維的交叉表,表格中的數(shù)值僅有0和1,稱其為形式背景。在此基礎(chǔ)上WILLE通過(guò)一對(duì)伽羅瓦算子給出了形式概念的定義,這一命名方式是基于哲學(xué)中對(duì)概念的理解而產(chǎn)生的,通過(guò)所有概念而構(gòu)成的層次結(jié)構(gòu)被稱為概念格。該結(jié)構(gòu)作為形式概念分析的核心數(shù)據(jù)模型,簡(jiǎn)潔直觀的體現(xiàn)了概念之間泛化和例化關(guān)系。

面對(duì)繁雜的數(shù)據(jù)庫(kù),去除冗余知識(shí)是數(shù)據(jù)分析的一個(gè)重要過(guò)程。而在形式概念分析中,屬性約簡(jiǎn)就是解決數(shù)據(jù)分析中去除冗余信息的一個(gè)主要工具,故其一直是該領(lǐng)域?qū)W者關(guān)注和研究的熱點(diǎn)問(wèn)題之一,且已取得了一系列的研究成果。該問(wèn)題由WILLE與GANTER共同提出[1],后經(jīng)張文修,魏玲,祁建軍等做了進(jìn)一步的完善和補(bǔ)充[2-3]。該方法將粗糙集理論中的差別矩陣引入形式概念分析中,尋找可以保持形式背景的概念格的層次結(jié)構(gòu)不發(fā)生改變的最小屬性集(即保持格結(jié)構(gòu)不變的約簡(jiǎn)),從而達(dá)到簡(jiǎn)化概念格的目的。之后,關(guān)于形式背景的約簡(jiǎn),還有學(xué)者提出了保持概念格中某些特殊概念不發(fā)生變化的約簡(jiǎn)。例如,WANG[4]、李鴻儒等[5]研究了保持概念格中交不可約元外延集不變的屬性約簡(jiǎn); LI等[6]研究了保持概念格中并不可約元外延集不變的屬性約簡(jiǎn)問(wèn)題;WU等[7]在形式背景中提出了粒概念的定義并研究了基于粒概念外延不變的約簡(jiǎn)。

除此之外,在FCA中,WAN等[8]通過(guò)在形式背景中通過(guò)引入屬性直觀圖研究了保持概念格結(jié)構(gòu)不變的約簡(jiǎn);REN等[9]在三支概念格中討論了保持概念格結(jié)構(gòu)不變、交(并)不可約元不變以及粒約簡(jiǎn)等問(wèn)題。而對(duì)于不同的形式背景,SHAO等[10]研究了廣義單邊形式背景的屬性約簡(jiǎn);LI[11]和王振等[12]研究了不完備形式背景上的屬性約簡(jiǎn)。

在關(guān)于形式背景的保持格結(jié)構(gòu)不變的約簡(jiǎn)問(wèn)題中,有部分學(xué)者提出利用布爾矩陣的相關(guān)理論與方法進(jìn)行研究。例如,張清新[13]通過(guò)用關(guān)系矩陣表示形式背景中的二元關(guān)系,進(jìn)一步引入特征向量把FCA中的算子“*, ′”轉(zhuǎn)化為布爾矩陣的運(yùn)算,基于此研究了FCA的保持格結(jié)構(gòu)不變的約簡(jiǎn);由于形式背景可以表示為僅有0和1的二維表,這種描述方式與布爾矩陣非常相似,SHAO等[14]把由0和1表示的形式背景看作一個(gè)布爾矩陣,每個(gè)屬性對(duì)應(yīng)一個(gè)列向量,利用列向量的線性獨(dú)立性，通過(guò)依次刪除不必要屬性的方法獲取保持格結(jié)構(gòu)不變的約簡(jiǎn);李同軍等[15]將布爾向量和布爾矩陣應(yīng)用到FCA提出了布爾形式背景,通過(guò)定義布爾向量的蘊(yùn)含運(yùn)算提出布爾形式概念和布爾概念格?；诖朔椒?石慧[16]通過(guò)布爾矩陣中所有向量生成的與空間的性質(zhì)研究了保持格結(jié)構(gòu)不變的約簡(jiǎn)及屬性特征分析。

在文獻(xiàn)[2]的基礎(chǔ)上，王道林[17]通過(guò)把可辨識(shí)屬性矩陣轉(zhuǎn)化為布爾矩陣,利用布爾矩陣的初等行變換給出判斷屬性特征的方法,該方法比較簡(jiǎn)單直觀。然而2009年QI[3]在文獻(xiàn)[2]的基礎(chǔ)上,通過(guò)簡(jiǎn)化形式背景的可辨識(shí)屬性矩陣對(duì)屬性約簡(jiǎn)的方法進(jìn)行了改進(jìn)。因此,本文在文獻(xiàn)[3]的基礎(chǔ)上,仍以布爾矩陣為工具,把形式背景的可辨識(shí)屬性矩陣轉(zhuǎn)化為布爾矩陣,通過(guò)證明布爾矩陣的初等行變換與辨識(shí)函數(shù)等價(jià)從而給出求解保持格結(jié)構(gòu)不變的約簡(jiǎn)方法及相應(yīng)的屬性特征的判別方法。

1 預(yù)備知識(shí)

1.1 概念格

定義1[1]稱三元組(G,M,I)是一個(gè)形式背景,其中G={g1,g2,…,gp}為對(duì)象集,每個(gè)gi稱為一個(gè)對(duì)象,M={m1,m2，…,mq}為屬性集,每個(gè)mj稱為一個(gè)屬性,I?G×M是對(duì)象集G和屬性集M之間的二元關(guān)系集. 若(g,m)∈I, 則稱g具有屬性m.

設(shè)(G,M,I)是形式背景, 在對(duì)象集A?G和屬性集B?M上分別定義運(yùn)算

A*={m∈M|?g∈A,gIm}

B′={g∈G|?m∈B,gIm}

特別地, ?g∈G,m∈M, 記{g}*為g*, {m}′為m′.

若二元對(duì)(A,B)滿足A*=B且B'=A, 則稱(A,B)是一個(gè)形式概念, 簡(jiǎn)稱概念。其中A稱為概念的外延,B稱為內(nèi)涵. 用L(G,M,I)表示所有概念的集合,?(A1,B1),(A2,B2)∈L(G,M,I), 在偏序關(guān)系

(A1,B1)≤(A2,B2)?A1?A2(?B1?B2)

下,可以證明

(A1,B1)∧(A2,B2)=(A1∩A2,(B1∪B2)′*)

(A1,B1)∨(A2,B2)=((A1∪A2)*′,B1∩B2)

也是概念,從而L(G,M,I)是格,且是完備格,稱其為(G,M,I)的概念格。若(A1,B1)≤(A2,B2),且不存在(A,B) ∈L(G,M,I), 有(A,B) ≠(A1,B1), (A,B)≠(A2,B2),使得 (A1,B1)≤(A,B)≤(A2,B2),則稱 (A2,B2)是(A1,B1)的父概念,(A1,B1)是(A2,B2)的子概念。

1.2 概念格約簡(jiǎn)

設(shè)L(G,M1,I1)和L(G,M2,I2)為2個(gè)概念格, 若?(A2,B2)∈L(G,M2,I2),?(A1,B1)∈L(G,M1,I1), 使得A1=A2,則稱L(G,M1,I1)細(xì)于L(G,M2,I2), 記作L(G,M1,I1)≤L(G,M2,I2). 若L(G,M1,I1)≤L(G,M2,I2)且L(G,M2,I2)≤L(G,M1,I1),則稱2個(gè)概念格同構(gòu),記為L(zhǎng)(G,M1,I1)?L(G,M2,I2)。

下面先給出關(guān)于保持概念格結(jié)構(gòu)不變的約簡(jiǎn)的相關(guān)定義。

定義2[2]設(shè)(G,M,I)是形式背景,如果存在屬性子集D?M,使得L(G,D,ID)?L(G,M,I), 則稱D是(G,M,I)的協(xié)調(diào)集。若?d∈D,D-j5i0abt0b不是(G,M,I)的協(xié)調(diào)集, 則稱D是(G,M,I)的約簡(jiǎn)集. 其中ID=I∩(G×D)。

在概念格約簡(jiǎn)中,這3類屬性具有不同特點(diǎn)。若m是核心屬性,則不存在Cm? (M-{m}),有Cm′=m′;若m是相對(duì)必要屬性,則?a∈M且a≠m,有a′=m′; 若m是絕對(duì)不必要屬性,則?Cm? (M-{m}),有Cm′=m′。因此,可以依據(jù)不同屬性的特點(diǎn)構(gòu)造約簡(jiǎn)。

QI等[3]通過(guò)簡(jiǎn)化形式背景的可辨識(shí)屬性矩陣給出了概念格的約簡(jiǎn)方法如下。

?(Ai,Bi),(Aj,Bj)∈L(G,M,I),(Ai,Bi)與(Aj,Bj)的可辨識(shí)屬性集定義如下,

DIS((Ai,Bi),(Aj,Bj))=

形式背景的可辨識(shí)屬性矩陣為

ΛFC= (DIS((Ai,Bi),(Aj,Bj))|(Ai,Bi)

(Aj,Bj))

一般情況下,ΛFC被記為非空可辨識(shí)集的集合,即ΛFC={Bi-Bj|(Ai,Bi)(Aj,Bj)}。最后,通過(guò)辨識(shí)函數(shù)可以求得所有約簡(jiǎn)。

例1針對(duì)表1的形式背景,G={1, 2, 3, 4},M={a,b,c,d,e}, 其對(duì)應(yīng)的概念格為如圖1 所示。

表 1 形式背景(G, M, I)

圖 1 概念格L(G, M, I)

根據(jù)可辨識(shí)屬性矩陣的定義,表1形式背景的可辨識(shí)屬性矩陣如表2所示。從而可得,ΛFC={{c},j5i0abt0b,{a,b},{d,e},{a,b,d}}。

表 2 可辨識(shí)屬性矩陣

在此基礎(chǔ)上可得辨識(shí)函數(shù)為

φ(ΛFC)= (a∨b)∧c∧d∧

(d∨e)∧(a∨b∨e)=

(a∧c∧d)∨(b∧c∧d)

繼而得約簡(jiǎn)為D1={a,c,d}和D2={b,c,d}。進(jìn)一步還可判斷c與d是核心屬性,a與b是相對(duì)必要屬性,e是絕對(duì)不必要屬性。

1.3 布爾矩陣

定義3[17]設(shè)va,vb都是n維布爾向量,記va=(a1,a2, …,an),vb=(b1,b2, …,bn),若?i(i=1,2,…,n)都有ai=bi,則稱va與vb相等,記為va=vb;若?i(i=1,2,…,n)都有ai≤bi,則稱va是vb的子串。

定義4[18]以下兩種變換稱為布爾矩陣的初等行變換:

(1) 互換布爾矩陣的兩行;

(2) 如果第i個(gè)行向量不是零向量,并且是第j個(gè)行向量的子串,則把第j行改為零行。

定義5[17]滿足以下2個(gè)條件的布爾矩陣稱為最簡(jiǎn)布爾矩陣

(1) 非零行的行號(hào)小于零行(若存在)的行號(hào),即非零行在上方,零行在下方;

(2) 任意一個(gè)非零行不是另一個(gè)零行的子串。

對(duì)任意的布爾矩陣都可經(jīng)過(guò)一系列的初等行變換化為最簡(jiǎn)布爾矩陣。

2 基于概念格的布爾矩陣約簡(jiǎn)

2.1 基于概念格的布爾矩陣構(gòu)造

首先基于文獻(xiàn)[3]提出的可辨識(shí)屬性矩陣給出概念格的布爾矩陣定義。

定義6設(shè)L(G,M,I)是形式背景(G,M,I)的概念格,ΛFC={Bi-Bj|(Ai,Bi)(Aj,Bj)}為該形式背景的非空可辨識(shí)集,記ki=Bs-Bt,i=1, 2, …,|ΛFC|,KFC(L)=(kij)|ΛFC|×|M|,其中

mj∈M,j=1,2,…,|M|。稱KFC(L)為概念格L(G,M,I)的布爾矩陣。

布爾矩陣KFC(L)中kij=1表示用屬性mj可以辨識(shí)ki所對(duì)應(yīng)的父子概念(As,Bs)與(At,Bt);kij=0表示用屬性mj不可以辨識(shí)該對(duì)父子概念。

例2由例1可知,表1形式背景的非空可辨識(shí)集為ΛFC={{c},j5i0abt0b,{a,b},{d,e},{a,b,d}}。圖1概念格的布爾矩陣如表3所示。

表 3 布爾矩陣KFC(L)

下面給出布爾矩陣KFC(L)的列向量和行向量的相關(guān)定義。

?B?M,記λB為B的特征向量。例如,B={a,b}?M,則λB=(1,1,0,0,0)。

由于布爾矩陣KFC(L)的每一行對(duì)應(yīng)屬性集M的一個(gè)子集k,于是記行向量為屬性子集k的特征向量λk。因此表3所示的布爾矩陣的行向量分別記為

2.2 基于概念格的布爾矩陣的約簡(jiǎn)方法

引理1[3]設(shè)(G,M,I)是形式背景。?D?M,D≠?,則有

D是協(xié)調(diào)集??ki∈AFC,若ki≠?,則ki∩D≠?。

根據(jù)定義6與引理1可得如下基于概念格布爾矩陣的協(xié)調(diào)集的判斷方法。

接下來(lái)給出辨識(shí)函數(shù)與初等行變換之間的關(guān)系。

定理2設(shè)KFC(L)是概念格L(G,M,I)對(duì)應(yīng)的布爾矩陣。對(duì)于KFC(L)中的行向量λki,λkj有,λki≤λkj?ki∧kj=ki。

證明根據(jù)定義3和定義6可知,λki≤λkj?ki?kj。又由辨識(shí)函數(shù)中的運(yùn)算“∧”可得ki?kj?ki∧kj=ki,從而定理1得證。

定理1說(shuō)明了辨識(shí)函數(shù)的運(yùn)算“∧”與布爾矩陣的初等行變換是等價(jià)的。故可以通過(guò)對(duì)布爾矩陣KFC(L)進(jìn)行初等行變換獲取約簡(jiǎn)。

表 4 最簡(jiǎn)布爾矩陣

進(jìn)一步,通過(guò)表4可知,{a,b,c,d}為協(xié)調(diào)集。

2.3 基于概念格的布爾矩陣的屬性特征分析

在尋找概念格的約簡(jiǎn)過(guò)程中,不同類型的屬性所起的作用也不盡相同,下面基于布爾矩陣KFC(L)對(duì)屬性特征進(jìn)行分析。

引理2[2]設(shè)(G,M,I)是形式背景。?m∈M,則有

m是核心屬性 ? ?(Ai,Bi), (Aj,Bj) ∈L(G,M,I),有DIS((Ai,Bi), (Aj,Bj))={m}。

通過(guò)上述結(jié)論以及定義6,可得基于概念格布爾矩陣的核心屬性的判定方法。

推論1設(shè)KFC(L)是概念格L(G,M,I)對(duì)應(yīng)的布爾矩陣。?m∈M,λ{(lán)m}是屬性m的特征向量,m是核心屬性?λ{(lán)m}是KFC(L)中的行向量。

證明由核心屬性的性質(zhì)知,mj是核心屬性?M-{mj}不是協(xié)調(diào)集。進(jìn)一步,由定理1可得,M-{mj}不是協(xié)調(diào)集??在KFC(L)中存在行向量λki,ki≠?,則ki∩(M-{mj})=?。?ki={mj}。?λ{(lán)mj}是KFC(L)的行向量。

證明由辨識(shí)函數(shù)的運(yùn)算“∧”和“∨”可知,mj是絕對(duì)不必要屬性

??ki∈ΛFC,若mj∈ki,則?ks∈ΛFC,有ks∧ki=ks且mj?ks。

?對(duì)于KFC(L)中的任意行向量λki,若kij=1,則?λks有ksj=0且λks≤λki(定理2)。

例4針對(duì)表4,根據(jù)定理3、定理4和定理5可知,c,d是核心屬性,a,b是相對(duì)必要屬性,c是絕對(duì)不必要屬性。這與例1的結(jié)論一致。

3 結(jié) 語(yǔ)

基于父子概念得到的可辨識(shí)屬性矩陣提出了概念格的布爾矩陣的構(gòu)造方法,利用布爾矩陣中的初等行變換與辨識(shí)函數(shù)之間的關(guān)系,給出協(xié)調(diào)集及屬性特征的判定定理,為概念格的約簡(jiǎn)理論提供了一種新的方法,且證明該方法與辨識(shí)矩陣是等價(jià)的?；诖怂枷?在形式概念分析中,對(duì)于以辨識(shí)矩陣為基礎(chǔ)的約簡(jiǎn)都可類似地轉(zhuǎn)化為相應(yīng)的布爾矩陣進(jìn)行求解。因此后續(xù)將進(jìn)一步把利用布爾矩陣獲取約簡(jiǎn)的方法引入到形式概念分析的其他類型的約簡(jiǎn)之中。