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

謝業海, 高秀巍

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

0 引言

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

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

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

1 形式概念分析的基本定義及性質

本節介紹形式概念分析的基礎知識,包括形式背景、決策形式背景、概念、概念格的定義及相關性質。

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

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

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

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

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

設(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]假設(U,A,I)為形式背景,?X?U,?B?A,若X*A=B且B*A=X,則稱二元組(X,B)為形式背景(U,A,I)的概念,稱X為概念(X,B)的外延,B為概念(X,B)的內涵。

記形式背景(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)上的偏序關系為

(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)的概念格。

性質1假設(U,A,I)為形式背景,對于?X,X1,X2?U和?B,B1,B2?A,容易證明有性質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]設(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。

設(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]中定義的強協調決策形式背景。

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

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

設(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假設(U,A,I)為形式背景,則有

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

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

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

算法1中的步驟2是構造辨識函數的基礎,也是本文的主要研究成果,所以僅討論步驟2的時間復雜度。設(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中時間復雜度最高的環節,所以步驟2的時間復雜度為O(|U||A|2|A|)。用文獻[13]中的約簡方法對一致決策形式背景進行約簡時,計算辨識矩陣的時間復雜度為O((|U|+|A|)|A||L(U,T,J)|)[18],低于算法1中步驟2的時間復雜度。但是算法1可應用于不一致決策形式背景的屬性約簡,因此比文獻[13]中的方法應用范圍更廣。

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

例1設決策形式背景Γ=(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}},

第三步 構造辨識函數

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

第四步 將辨識函數轉換為最小析取范式

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}是一個約簡。

假設(U,A,I,T,J)為強協調決策形式背景,那么VA=LU(U,T,J)。

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

1)VA=VB;

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

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

例2設決策形式背景Γ=(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}},

第三步 計算辨識函數得到

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

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

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

第四步 將辨識函數轉換為最小析取范式

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

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

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

3 結論

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

圖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