一般決策形式背景的屬性約簡

謝業(yè)海, 高秀巍

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

定義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)}。對于任意(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)為形式背景,對于?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)細于L(U,A2,I2),記為L(U,A1,I1)≤L(U,A2,I2)。

若L(U,A1,I1)≤L(U,A2,I2),那么對于任意(X2,B2)∈L(U,A2,I2),總存在(X1,B1)∈L(U,A1,I1)使得X1=X2。

設(shè)(U,A,I)為形式背景,?≠B?A,那么不難驗證有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中的一致決策形式背景即是文獻[13]中定義的強協(xié)調(diào)決策形式背景。

2 一般決策形式背景的廣義約簡

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

設(shè)(U,A,I,T,J)為決策形式背景,對于?≠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) 對于任意?≠C?B,那么VC≠VA,

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

特別地,若(U,A,I,T,J)為一致決策形式背景,那么VA=LU(U,T,J),則VA=VB等價于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) 對于?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)為決策形式背景,對于任意?≠B?A,條件1)和2)等價:

1)VA=VB;

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

證明1)?2):若VA=VB,對于?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。當X∈VA且X=U時,顯然有X∈VB。當?X∈VA且X≠U時,由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)的約簡,當且僅當B是A的滿足定理1中2)的極小子集。

在決策形式背景(U,A,I,T,J)中,對于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可得計算一般決策形式背景約簡的算法。

算法1一般決策形式背景的約簡算法

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

輸出: 全部約簡。

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

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

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

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

下面用一個例子對算法1進行說明。

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

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

在決策形式背景Γ中,L(U,A,I)和L(U,T,J)的哈斯圖分別如圖1、圖2所示。可以看到,形式背景(U,A,I)共有10個概念,形式背景(U,T,J)共有7個概念。由于(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

約簡的具體計算過程如下。

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

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

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

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

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

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

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

第五步 得到所有約簡為{a,c,d}和{d,e}。

令B={a,c,d},約簡后的概念格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,約簡后有VB=VA。B={a,c,d}是一個約簡。

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

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

1)VA=VB;

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

證明由于(U,A,I,T,J)為強協(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)為強協(xié)調(diào)決策形式背景,則使用算法1和使用文獻[13]中的算法對(U,A,I,T,J)進行約簡,得到的結(jié)果一致。下面引用文獻[13]中的例子對定理2進行說明。

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

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

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

約簡的具體計算過程如下。

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

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

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

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

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

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

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

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

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

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

第五步 得到所有約簡為{a,b,c}和{b,c,e}。

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

3 結(jié)論

本文研究一般決策形式背景的屬性約簡方法,提出一般決策形式背景的屬性約簡的定義,并給出可計算所有約簡的算法。未來,我們將從信息損失、計算效率等方面對比約簡前、后決策形式背景在不同應用場景中的區(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