謝業(yè)海, 高秀巍

(北京語言大學(xué) 信息科學(xué)學(xué)院 北京 100083)

0 引言

1982年,德國學(xué)者Wille[1]提出了形式概念分析理論,也被稱作概念格理論。形式概念分析理論通過構(gòu)建一個(gè)概念完備格,直觀地刻畫出概念之間的層次結(jié)構(gòu),因而成為一種有效的數(shù)據(jù)處理工具,被廣泛應(yīng)用于信息檢索、數(shù)據(jù)挖掘等領(lǐng)域[2-3]。

面對(duì)海量數(shù)據(jù),如何去除冗余信息,保留核心信息,降低數(shù)據(jù)的維度和計(jì)算復(fù)雜度,對(duì)于數(shù)據(jù)處理來說十分重要,因此屬性約簡(jiǎn)[4-5]一直受到廣泛的關(guān)注。概念格的屬性約簡(jiǎn)本質(zhì)上是在保持概念格某個(gè)特性不變的基礎(chǔ)上,尋找最小屬性集,使約簡(jiǎn)后的概念格比原概念格更加簡(jiǎn)潔,因而概念格的屬性約簡(jiǎn)一直都是熱點(diǎn)研究問題。Zhang等[6]首先提出保持概念格結(jié)構(gòu)不變的約簡(jiǎn),即約簡(jiǎn)后的概念格與原概念格同構(gòu),并基于辨識(shí)矩陣給出獲得所有約簡(jiǎn)的算法。Qi[7]對(duì)文獻(xiàn)[6]中的辨識(shí)矩陣加以改進(jìn),獲得了計(jì)算效率更高的約簡(jiǎn)算法。Wu等[8]從粒計(jì)算的角度定義了概念格的對(duì)象粒,并用對(duì)象粒去定義形式背景的粒約簡(jiǎn),同時(shí)給出獲得相應(yīng)約簡(jiǎn)的方法。許多學(xué)者研究粗糙集的屬性約簡(jiǎn)和形式背景的屬性約簡(jiǎn)之間的關(guān)系。Wei等[9]將形式背景當(dāng)作一個(gè)屬性值為0和1的信息系統(tǒng),并研究了形式背景屬性約簡(jiǎn)和信息系統(tǒng)絕對(duì)約簡(jiǎn)之間的關(guān)系。Liu等[10]研究了面向?qū)ο蟮母拍罡竦膶傩约s簡(jiǎn)與信息系統(tǒng)的屬性約簡(jiǎn)之間的關(guān)系。Li等[11]定義了形式背景的不可約簡(jiǎn)屬性類,并用不可約簡(jiǎn)屬性類刻畫了形式背景的核心屬性集、相對(duì)必要屬性集和冗余屬性集,同時(shí)給出了約簡(jiǎn)的判定定理。Ren等[12]研究了三支概念格的屬性約簡(jiǎn)問題,在對(duì)象導(dǎo)出三支概念格和屬性導(dǎo)出三支概念格中分別定義了4種約簡(jiǎn),并研究了約簡(jiǎn)之間的關(guān)系,同時(shí)給出了其中7種約簡(jiǎn)的計(jì)算方法。魏玲等[13]研究了強(qiáng)協(xié)調(diào)決策形式背景和弱協(xié)調(diào)決策形式背景的約簡(jiǎn)定義和約簡(jiǎn)方法。決策形式背景的提出,進(jìn)一步豐富了形式概念分析的理論,得到了學(xué)術(shù)界的廣泛關(guān)注。Li等[14]面向規(guī)則提取,定義了決策形式背景的約簡(jiǎn),并給出計(jì)算所有約簡(jiǎn)的算法。在文獻(xiàn)[8]中,Wu等定義了一致決策形式背景的粒約簡(jiǎn)并給出相應(yīng)約簡(jiǎn)算法。Wang等[15]基于辨識(shí)矩陣,給出了計(jì)算廣義一致決策形式背景約簡(jiǎn)的算法。

相對(duì)一致決策形式背景而言,不一致決策形式背景在實(shí)際應(yīng)用中更為常見,因此研究一般決策形式背景的屬性約簡(jiǎn)更具有現(xiàn)實(shí)意義?；诖?本文給出一般決策形式背景的屬性約簡(jiǎn)的定義,并利用辨識(shí)函數(shù)給出計(jì)算所有約簡(jiǎn)的算法。該算法可應(yīng)用于一致決策形式背景和不一致決策形式背景。特別地,文獻(xiàn)[13]中的強(qiáng)協(xié)調(diào)決策形式背景的約簡(jiǎn)是我們算法的特例。

1 形式概念分析的基本定義及性質(zhì)

本節(jié)介紹形式概念分析的基礎(chǔ)知識(shí),包括形式背景、決策形式背景、概念、概念格的定義及相關(guān)性質(zhì)。

定義1[1]形式背景是一個(gè)三元組(U,A,I),U是非空有限對(duì)象集,A是非空有限屬性集,I是U和A之間的二元關(guān)系,即I?U×A。

對(duì)于一個(gè)形式背景(U,A,I),可在對(duì)象集和屬性集上定義兩個(gè)運(yùn)算[16],

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

?B?A,B*={x∈U|?b∈B,xIb},

設(shè)(U,A,I)為一個(gè)形式背景,對(duì)于B?A,令I(lǐng)B=I∩(U×B),則(U,B,IB)也是一個(gè)形式背景[6]。為了區(qū)分不同形式背景下的“*”運(yùn)算,我們分別用“*A”和“*B”表示形式背景(U,A,I)和(U,B,IB)中的“*”運(yùn)算。對(duì)于C?B?A,容易證明有C*A=C*B[8]。

設(shè)(U,A,I)為一個(gè)形式背景,其中對(duì)象集為U={x1,x2,…,xm},屬性集為A={a1,a2,…,an}。將(U,A,I)視為一張m行n列的信息表,其中信息表中元素的值域?yàn)閧0,1}。若信息表中第i行第j列的元素為1,則表示(xi,aj)∈I,即對(duì)象xi具有屬性aj,反之則表示(xi,aj)?I,即對(duì)象xi不具有屬性aj。若形式背景(U,A,I)對(duì)應(yīng)的信息表的每行每列既有0又有1,則稱(U,A,I)是正則的[6]。本文研究的形式背景在約簡(jiǎn)前均為正則的。

定義2[16]假設(shè)(U,A,I)為形式背景,?X?U,?B?A,若X*A=B且B*A=X,則稱二元組(X,B)為形式背景(U,A,I)的概念,稱X為概念(X,B)的外延,B為概念(X,B)的內(nèi)涵。

記形式背景(U,A,I)的全體概念為L(U,A,I),即L(U,A,I)={(X,B)|X?U,B?A,X*A=B,B*A=X};記全體概念的外延集為LU(U,A,I),即LU(U,A,I)={X?U|B?A,(X,B)∈L(U,A,I)}。對(duì)于任意(X1,B1),(X2,B2)∈L(U,A,I),定義L(U,A,I)上的偏序關(guān)系為

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

若(X1,B1),(X2,B2)∈L(U,A,I),在L(U,A,I)上分別定義上、下確界為

(X1,B1)∧(X2,B2)=(X1∩X2,(B1∪B2)*A*A),

(X1,B1)∨(X2,B2)=((X1∪X2)*A*A,B1∩B2),

則L(U,A,I)為完備格,稱之為形式背景(U,A,I)的概念格。

性質(zhì)1假設(shè)(U,A,I)為形式背景,對(duì)于?X,X1,X2?U和?B,B1,B2?A,容易證明有性質(zhì)1)～5)[16]:

1)X1?X2?X1*A?X2*A,B1?B2?B1*A?B2*A;

2)X?B*A?B?X*A;

3)X?X*A*A,B?B*A*A;

4)X*A=X*A*A*A,B*A=B*A*A*A;

5)(X*A*A,X*A)∈L(U,A,I),

(B*A,B*A*A)∈L(U,A,I)。

定義3[6]設(shè)(U,A1,I1)和(U,A2,I2)為形式背景,若LU(U,A2,I2)?LU(U,A1,I1),則稱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),那么對(duì)于任意(X2,B2)∈L(U,A2,I2),總存在(X1,B1)∈L(U,A1,I1)使得X1=X2。

設(shè)(U,A,I)為形式背景,?≠B?A,那么不難驗(yàn)證有L(U,A,I)≤L(U,B,IB)[6]。

定義4令(U,A,I)和(U,T,J)為形式背景,則稱五元組(U,A,I,T,J)為決策形式背景[13]。其中,A是條件屬性集,T是決策屬性集。若L(U,A,I)≤L(U,T,J),則稱(U,A,I,T,J)為一致的決策形式背景,反之則稱(U,A,I,T,J)為不一致的決策形式背景。

定義4中的一致決策形式背景即是文獻(xiàn)[13]中定義的強(qiáng)協(xié)調(diào)決策形式背景。

2 一般決策形式背景的廣義約簡(jiǎn)

對(duì)一般決策形式背景,定義一種新的約簡(jiǎn),該約簡(jiǎn)是強(qiáng)協(xié)調(diào)決策形式背景的約簡(jiǎn)的擴(kuò)展。需要指出的是,作為一個(gè)特例,用本節(jié)提出的約簡(jiǎn)算法,可獲得強(qiáng)協(xié)調(diào)決策形式背景的所有約簡(jiǎn)。

設(shè)(U,A,I,T,J)為決策形式背景,對(duì)于?≠B?A,記VB=LU(U,B,IB)∩LU(U,T,J),于是VA=LU(U,A,I)∩LU(U,T,J)。

定義5令(U,A,I,T,J)為決策形式背景,?≠B?A,若B滿足

1)VA=VB,

2) 對(duì)于任意?≠C?B,那么VC≠VA,

則稱B為決策形式背景(U,A,I,T,J)的約簡(jiǎn)。

特別地,若(U,A,I,T,J)為一致決策形式背景,那么VA=LU(U,T,J),則VA=VB等價(jià)于L(U,B,IB)≤L(U,T,J)。

引理1假設(shè)(U,A,I)為形式背景,則有

1)?a∈A,(a*A,a*A*A)∈L(U,A,I);

證明1) 對(duì)于?a∈A,根據(jù)性質(zhì)1中的4)有a*A=a*A*A*A,那么有(a*A,a*A*A)∈L(U,A,I)。

定理1設(shè)(U,A,I,T,J)為決策形式背景,對(duì)于任意?≠B?A,條件1)和2)等價(jià):

1)VA=VB;

2)對(duì)于?X∈VA且X≠U,存在C?B,使得X=C*A。

證明1)?2):若VA=VB,對(duì)于?X∈VA且X≠U,有X∈VB,也就是?C?B使(X,C)∈L(U,B,IB)。由定義2可知有X=C*B,又C*A=C*B,所以X=C*A。

2)?1):由?≠B?A,有L(U,A,I)≤L(U,B,IB),也就是LU(U,B,IB)?LU(U,A,I),所以VB?VA。

下面證VA?VB。當(dāng)X∈VA且X=U時(shí),顯然有X∈VB。當(dāng)?X∈VA且X≠U時(shí),由2)可知存在C?B使得X=C*A,又由C*A=C*B可推出X=C*B,由引理1中3)可推出X∈LU(U,B,IB),即X∈VB,所以有VA?VB。綜上可得VA=VB。

推論1設(shè)(U,A,I,T,J)為決策形式背景,?≠B?A,則B是(U,A,I,T,J)的約簡(jiǎn),當(dāng)且僅當(dāng)B是A的滿足定理1中2)的極小子集。

在決策形式背景(U,A,I,T,J)中,對(duì)于X∈VA且X≠U,記(X)={C?A|X∈VA,X≠U,X=C*A},min(X)={D∈(X)|?C∈(X),C≠D,C?D}。由推論1可得計(jì)算一般決策形式背景約簡(jiǎn)的算法。

算法1一般決策形式背景的約簡(jiǎn)算法

輸入: 一般決策形式背景(U,A,I,T,J)。

輸出: 全部約簡(jiǎn)。

步驟1 計(jì)算VA=LU(U,A,I)∩LU(U,T,J)。

步驟2 對(duì)于?X∈VA且X≠U,計(jì)算min(X)。

算法1中的辨識(shí)函數(shù)是一個(gè)由辨識(shí)矩陣誘導(dǎo)的單調(diào)布爾函數(shù)。辨識(shí)矩陣和辨識(shí)函數(shù)最初由Skowron等[17]應(yīng)用于粗糙集的屬性約簡(jiǎn)中。設(shè)M=(Cij)m×n為一個(gè)辨識(shí)矩陣,其中矩陣中的元素Cij為屬性的集合,那么M可誘導(dǎo)一個(gè)辨識(shí)函數(shù)f=∧{∨(Cij):1≤i≤m,1≤j≤n,Cij≠?}。將辨識(shí)函數(shù)f由合取范式轉(zhuǎn)換為最小析取范式后,其中任意一個(gè)質(zhì)蘊(yùn)涵項(xiàng)中的所有屬性組成的集合即為一個(gè)約簡(jiǎn),所有質(zhì)蘊(yùn)含項(xiàng)對(duì)應(yīng)的約簡(jiǎn)組成的集合即為所有約簡(jiǎn)的集合。在算法1中,根據(jù)定理1可知,對(duì)于X∈VA且X≠U,(X)={C?A|X∈VA,X≠U,X=C*A}是辨識(shí)函數(shù)f對(duì)應(yīng)的辨識(shí)矩陣中的非空元素。由于在將辨識(shí)函數(shù)f轉(zhuǎn)換為最小析取范式的過程中會(huì)使用吸收率,所以取min(X)以簡(jiǎn)化計(jì)算過程。

算法1中的步驟2是構(gòu)造辨識(shí)函數(shù)的基礎(chǔ),也是本文的主要研究成果,所以僅討論步驟2的時(shí)間復(fù)雜度。設(shè)(U,A,I,T,J)為一般決策形式背景,X∈VA且X≠U,(X,B)∈L(U,A,I),記B的冪集為P(B),步驟2計(jì)算min(X)時(shí),首先要計(jì)算(X)={C?A|X∈VA,X≠U,X=C*A}。為了計(jì)算出(X),對(duì)于?C∈P(B),要計(jì)算C*A并判斷C*A是否等于X,若C*A=X,則將C作為元素加入集合(X)中,這也是步驟2中時(shí)間復(fù)雜度最高的環(huán)節(jié),所以步驟2的時(shí)間復(fù)雜度為O(|U||A|2|A|)。用文獻(xiàn)[13]中的約簡(jiǎn)方法對(duì)一致決策形式背景進(jìn)行約簡(jiǎn)時(shí),計(jì)算辨識(shí)矩陣的時(shí)間復(fù)雜度為O((|U|+|A|)|A||L(U,T,J)|)[18],低于算法1中步驟2的時(shí)間復(fù)雜度。但是算法1可應(yīng)用于不一致決策形式背景的屬性約簡(jiǎn),因此比文獻(xiàn)[13]中的方法應(yīng)用范圍更廣。

下面用一個(gè)例子對(duì)算法1進(jìn)行說明。

例1設(shè)決策形式背景Γ=(U,A,I,T,J)如表1所示,其中:對(duì)象集U={1,2,3,4,5};條件屬性集A={a,b,c,d,e};決策屬性集T={f,g,h}。

表1 一個(gè)不一致決策形式背景Table 1 An inconsistent decision formal context

在決策形式背景Γ中,L(U,A,I)和L(U,T,J)的哈斯圖分別如圖1、圖2所示?？梢钥吹?形式背景(U,A,I)共有10個(gè)概念,形式背景(U,T,J)共有7個(gè)概念。由于(145,h)∈L(U,T,J)但{1,4,5}?LU(U,A,I),所以Γ是不一致決策形式背景。

圖1 例1中概念格L(U,A,I)的哈斯圖Figure 1 The Hasse diagram of L(U,A,I) in example 1

圖2 例1中概念格L(U,T,J)的哈斯圖Figure 2 The Hasse diagram of L(U,T,J) in example 1

約簡(jiǎn)的具體計(jì)算過程如下。

第一步 計(jì)算得到VA={?,{2,4},{3,5},U}。

第二步 對(duì)于?X∈VA且X≠U,計(jì)算min(X)得

min(?)={{a,d},{d,e}},

第三步 構(gòu)造辨識(shí)函數(shù)

f=((a∧d)∨(d∧e))∧(e∨(a∧c))∧d。

第四步 將辨識(shí)函數(shù)轉(zhuǎn)換為最小析取范式

f=(a∧c∧d)∨(d∧e)。

第五步 得到所有約簡(jiǎn)為{a,c,d}和{d,e}。

令B={a,c,d},約簡(jiǎn)后的概念格L(U,B,IB)的哈斯圖如圖3所示。由圖1～3可以看到,LU(U,A,I)={?,{2},{1,2},{2,4},{3,5},{1,2,4},{2,3,5},{1,2,3,5},{2,3,4,5},U},LU(U,T,J)={?,{4},{5},{2,4},{3,5},{1,4,5},U},LU(U,B,IB)={?,{2,4},{3,5},{1,2,4},{2,3,4,5},U},那么VB=LU(U,B,IB)∩LU(U,T,J)={?,{2,4},{3,5},U}=VA,約簡(jiǎn)后有VB=VA。B={a,c,d}是一個(gè)約簡(jiǎn)。

假設(shè)(U,A,I,T,J)為強(qiáng)協(xié)調(diào)決策形式背景,那么VA=LU(U,T,J)。

定理2設(shè)(U,A,I,T,J)為強(qiáng)協(xié)調(diào)決策形式背景,對(duì)于任意?≠B?A,條件1)和2)等價(jià):

1)VA=VB;

2)L(U,B,IB)≤L(U,T,J)。

證明由于(U,A,I,T,J)為強(qiáng)協(xié)調(diào)決策形式背景,那么有VA=LU(U,T,J)。

1)?2):由VA=VB=LU(U,B,IB)∩LU(U,T,J)及VA=LU(U,T,J),有LU(U,T,J)=LU(U,B,IB)∩LU(U,T,J),可以推出LU(U,T,J)?LU(U,B,IB),即L(U,B,IB)≤L(U,T,J)。

2)?1):由L(U,B,IB)≤L(U,T,J)可得LU(U,T,J)?LU(U,B,IB),那么VB=LU(U,B,IB)∩LU(U,T,J)=LU(U,T,J),又由VA=LU(U,T,J),所以VA=VB。

若(U,A,I,T,J)為強(qiáng)協(xié)調(diào)決策形式背景,則使用算法1和使用文獻(xiàn)[13]中的算法對(duì)(U,A,I,T,J)進(jìn)行約簡(jiǎn),得到的結(jié)果一致。下面引用文獻(xiàn)[13]中的例子對(duì)定理2進(jìn)行說明。

例2設(shè)決策形式背景Γ=(U,A,I,T,J)如表2所示,其中對(duì)象集U={1,2,3,4,5},條件屬性集A={a,b,c,d,e},決策屬性集T={f,g,h}。

表2 一個(gè)一致決策形式背景Table 2 A consistent decision formal context

在決策形式背景Γ中,L(U,A,I)和L(U,T,J)的哈斯圖分別如圖4、圖5所示,可以看到(U,A,I)共有10個(gè)概念,(U,T,J)共有5個(gè)概念。不難看出,Γ為一致決策形式背景。

約簡(jiǎn)的具體計(jì)算過程如下。

第一步 計(jì)算得到VA={?,{2,3},{4,5},{1,4,5},U}。

第二步 對(duì)于?X∈VA且X≠U,計(jì)算min(X)得

min(?)={{a,b,c},{b,c,e},{c,d,e},{a,c,d}},

min(23)={{a,b},{b,e}},

第三步 計(jì)算辨識(shí)函數(shù)得到

f=((a∧b∧c)∨(b∧c∧e)∨

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

(b∧e))∧((b∧c)∨(c∧d))∧c。

第四步 將辨識(shí)函數(shù)轉(zhuǎn)換為最小析取范式

f=(a∧b∧c)∨(b∧c∧e)。

第五步 得到所有約簡(jiǎn)為{a,b,c}和{b,c,e}。

可以看到,算法1的約簡(jiǎn)結(jié)果與文獻(xiàn)[13]中的一致。令B={a,b,c},約簡(jiǎn)后的概念格L(U,B,IB)的哈斯圖如圖6所示,不難驗(yàn)證VB=VA。

3 結(jié)論

本文研究一般決策形式背景的屬性約簡(jiǎn)方法,提出一般決策形式背景的屬性約簡(jiǎn)的定義,并給出可計(jì)算所有約簡(jiǎn)的算法。未來,我們將從信息損失、計(jì)算效率等方面對(duì)比約簡(jiǎn)前、后決策形式背景在不同應(yīng)用場(chǎng)景中的區(qū)別。

圖3 例1中概念格L(U,B,IB)的 哈斯圖Figure 3 The Hasse diagram of L(U,B,IB) in example 1

圖4 例2中概念格L(U,A,I)的哈斯圖Figure 4 The Hasse diagram of L(U,A,I) in example 2

圖5 例2中概念格L(U,T,J)的 哈斯圖Figure 5 The Hasse diagram of L(U,T,J) in example 2

圖6 例2中概念格L(U,B,IB)的哈斯圖Figure 6 The Hasse diagram of L(U,B,IB) in example 2