張呈玲，李進(jìn)金+，林藝東,2

1.閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，福建 漳州363000

2.廈門大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，福建 廈門361005

1 引言

形式概念分析（formal concept analysis）是由德國數(shù)學(xué)家Wille[1-2]提出的一種分析數(shù)據(jù)的有效工具。它的核心是形式背景和概念格。形式背景是由對象集、屬性集以及對象和屬性之間的二元關(guān)系構(gòu)成的。而概念格是將形式背景里的對象子集和屬性子集以一種概念層次體現(xiàn)出來。近年來，形式概念分析已被廣泛應(yīng)用于概念認(rèn)知[3]、知識提取[4]等領(lǐng)域。

決策形式背景是形式背景的一個延伸。其中，屬性約簡是決策形式背景的一個研究熱點。目前，研究工作者已獲得了多種屬性約簡方法[4-16]。它旨在尋找極小的屬性子集使得決策形式背景的決策分析更加簡潔。而決策形式背景分為兩類：一類決策形式背景是協(xié)調(diào)的；另一類決策形式背景是不協(xié)調(diào)的。針對第一類，魏玲等[8]給出了強協(xié)調(diào)和弱協(xié)調(diào)決策形式背景的定義，以及相應(yīng)的協(xié)調(diào)集的判定定理。針對強協(xié)調(diào)決策形式背景研究了保持概念外延不變的屬性約簡的問題。而弱協(xié)調(diào)決策形式背景借助蘊含映射刻畫了屬性約簡。陳秀[9]從等價關(guān)系的角度給出了協(xié)調(diào)決策形式背景的定義。并且通過構(gòu)造等價關(guān)系的辨識矩陣，提出了屬性約簡的方法。裴鐸等在文獻(xiàn)[10]中針對協(xié)調(diào)決策形式背景，從并不可約元角度給出了irr-型協(xié)調(diào)集的概念。李仲玲等[11]借助集合交集討論了協(xié)調(diào)決策形式背景下的交約簡方法，并說明了概念格協(xié)調(diào)集與交協(xié)調(diào)集是等價的。然而，由于辨識矩陣和辨識函數(shù)的約簡方法的時間復(fù)雜度較大，在實際中不容易實現(xiàn)。李金海等[4,12-14]針對決策形式背景提出了必要屬性和不必要屬性的等價刻畫，并設(shè)計出了保持決策規(guī)則的屬性約簡的啟發(fā)式算法。

然而，屬性約簡同樣是不協(xié)調(diào)決策形式背景里的重要研究課題。其目的是刪除冗余、不必要屬性，進(jìn)而獲得較為簡潔的知識表達(dá)。文獻(xiàn)[7,15-21]已對屬性約簡的問題取得了重要的結(jié)果。郭松濤等[15]基于文獻(xiàn)[4]的屬性約簡的框架，考慮一般決策形式背景的屬性約簡問題。給出了一個屬性是否是必要的等價刻畫，進(jìn)而設(shè)計出了適用一般決策形式背景的屬性約簡的啟發(fā)式算法。王亞麗等[16-17]針對下近似函數(shù)提出了保持條件屬性子集在每個決策類不變的近似約簡的問題，并給出了約簡方法?；趯ο髢缂耐嚓P(guān)系，文獻(xiàn)[18,21]給出了不協(xié)調(diào)決策形式背景下的屬性約簡方法。Wang 等[18]從同余關(guān)系的角度討論了上、下近似的屬性約簡問題。在此基礎(chǔ)上，通過構(gòu)造辨識矩陣可以得到所有的約簡集。Li 等[21]基于文獻(xiàn)[18]約簡的框架，提出了分布屬性約簡和極大分布屬性約簡的概念。接著，討論了兩者之間的關(guān)系，并給出了計算約簡集的方法。Huang 等[7]在吳偉志等[5]研究的基礎(chǔ)上，考慮了決策形式背景是不協(xié)調(diào)時，從信息粒角度，利用條件信息熵刻畫了屬性重要度，進(jìn)而設(shè)計了計算一個極小近似約簡的啟發(fā)式算法。但此約簡方法依賴信息粒之間的關(guān)系，并且在約簡過程中計算量大。本文在文獻(xiàn)[7]的基礎(chǔ)上，借助布爾矩陣的運算，刻畫不協(xié)調(diào)決策形式背景的屬性重要度，并設(shè)計出更為簡便的屬性約簡的啟發(fā)式算法。

本文首先給出不協(xié)調(diào)決策形式背景下廣義矩陣協(xié)調(diào)集的定義；然后通過矩陣刻畫出屬性之間的相似度；接著給出一個屬性是否是核心屬性的充要條件；最后提出一種比Huang 等[7]的約簡算法時間復(fù)雜度更低的約簡方法。

2 預(yù)備知識

本章主要介紹形式概念分析的基本定義和矩陣的運算等。為下文討論方便，假設(shè)論域U是一個非空有限集合。

定義1[1]設(shè)F=(U,A,I)是形式背景，其中U={x1,x2,…,xn}為對象集，A={a1,a2,…,am}為屬性集，I是U和A之間的二元關(guān)系，且I?U×A。若(x,a)∈I，表示對象x具有屬性a；若(x,a)?I，表示對象x不具有屬性a。

對于X?U,B?A，Wille 給出形式背景F下的一對算子：

X?={a∈A:?x∈X,(x,a)∈I}

B?={x∈U:?a∈B,(x,a)∈I}

對于論域U={x1,x2,…,xn}，X?U，那么X的特征向量為λ(X)=(λX(x1),λX(x2),…,λX(xn))。其中：

通常，形式背景是以0-1 數(shù)值表呈現(xiàn)。1 是指對象具有x屬性a，即(x,a)∈I；0 是指對象x不具有屬性a，即(x,a)?I。為表述方便，因此形式背景可看成布爾矩陣MI=(cij)n×m，稱MI是F的一個關(guān)系矩陣。其中：

?xi∈U,?aj∈A，矩陣MI的第i行是的特征向量的第j行是的特征向量

注本文中，MI(i,:) 指矩陣MI的第i行；MI(:,j)指MI矩陣的第j列；MI(i,j)指矩陣MI的第i行第j列。

定義2[5]設(shè)F=(U,A,I)是形式背景，Q?A，IQ=I?(U×Q)，則FQ=(U,Q,IQ)稱為F的一個子背景。

與形式背景F類似，也可給出在子背景FQ(U,Q,IQ)中的一對算子：

引理1A=(aij)n×m,B=(bij)n×m,C=(cij)m×p是布爾矩陣，有以下運算性質(zhì)：

接著，通過上面的矩陣的運算給出對象的粒矩陣描述。

定義3[6]設(shè)F=(U,A,I)是形式背景，MI是I的關(guān)系矩陣，令矩陣M的第i行為對象xi內(nèi)涵的外延的特征向量，稱M為對象粒矩陣。

從定義3可以得出，對象粒矩陣M的第i行M(i,:)=

定義4[8]設(shè)(U,A,I)和(U,D,J)是兩個形式背景，并且A?D=?。A和D分別是條件屬性集和決策屬性集，稱S=(U,A,I,D,J)是決策形式背景。

吳偉志等在文獻(xiàn)[5]中提出了決策形式背景是粒協(xié)調(diào)的定義。然而，現(xiàn)實中不協(xié)調(diào)的決策形式背景要比協(xié)調(diào)決策形式背景出現(xiàn)的可能性要大。那應(yīng)當(dāng)如何定義協(xié)調(diào)性的程度，Huang 等在文獻(xiàn)[7]中給出如下說明。

設(shè)S=(U,A,I,D,J)是一個決策形式背景，B?A，定義POSB(D)={x∈U:x?B?B?x?D?D}，正域是由子背景(U,B,I)的對象粒含在(U,D,J)的對象粒構(gòu)成的。而子背景(U,B,IB,D,J)的協(xié)調(diào)性的程度是

定義5[7]設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，B?A，若τB(D)=τA(D)，則B稱為S的一個廣義粒協(xié)調(diào)集。如果B是S的一個廣義粒協(xié)調(diào)集，且B的任意真子集都不再是S的廣義粒協(xié)調(diào)集，則B稱為是S的一個粒約簡。

3 基于布爾矩陣的不協(xié)調(diào)決策形式背景的屬性約簡

在文獻(xiàn)[5]中，吳偉志等給出決策形式背景協(xié)調(diào)性的定義?；诖?，本文利用矩陣的表達(dá)形式給出決策形式背景的相關(guān)概念。在決策形式背景S=(U,A,I,D,J)中，與定義3 類似，MI是I的條件關(guān)系矩陣，MJ是J的決策關(guān)系矩陣，則是S的條件對象粒矩陣，是S的決策對象粒矩陣。若?B?A，令RB是任意一行均為λ(B)的 |U|× |A|的矩陣。那么，在子背景SB=(U,B,IB,D,J)中有MB=～((MI∧RB)?(～(MI∧RB)T)) 。根據(jù)條件對象粒矩陣MA和決策對象粒矩陣MD，可給出S協(xié)調(diào)的定義。

定義6設(shè)S=(U,A,I,D,J)是決策形式背景，MA和MD分別是S的條件對象粒矩陣和決策對象粒矩陣，若MA≤MD，則稱S是協(xié)調(diào)的；否則S是不協(xié)調(diào)的。

例1 表1 為一決策形式背景，其中對象集、條件屬性集、決策屬性集分別為U={x1,x2,x3,x4,x5}，A={a1,a2,a3,a4,a5,a6}和D={d1,d2,d3,d4}。

Table 1 Decision formal context S=(U,A,I,D,J)表1 決策形式背景S=(U,A,I,D,J)

從表1 中可知，決策形式背景S的條件關(guān)系矩陣和決策關(guān)系矩陣分別為：

那么，S的條件對象粒矩陣和決策粒矩陣分別為：

可以看出MA≤MD不成立。由定義6 可知，S是不協(xié)調(diào)的。

設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，B?A，定義當(dāng)MB(i,:)≤MD(i,:),1 ≤i≤n時，那么有：

從上述等式可以看出，在MB的每行小于等于MD對應(yīng)行的情況下，VB(D)是由MB和MD共有的0的基數(shù)構(gòu)成的。因此，可以給出在決策形式背景S下的協(xié)調(diào)性程度的定義。

定義7設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，B?A。定義子背景SB=(U,B,IB,D,J)的協(xié)調(diào)性程度為

定義8設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，B?A，若ΓB(D)=ΓA(D)，B稱為S的一個廣義矩陣協(xié)調(diào)集。若B是S的一個廣義矩陣協(xié)調(diào)集且?C?B,C都不再是S的廣義矩陣協(xié)調(diào)集，那么B稱為S的一個約簡集。記Bt(t≤r)是S所有的約簡集，且有是S的核心。

定理1設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，C?B?A，則ΓC(D)≤ΓB(D)。

證明由C?B?A，則MA≤MB≤MC。要說明ΓC(D)≤ΓB(D)，只需證明VC(D)≤VB(D) 。由于當(dāng)MC(i,:)≤MD(i,:),i=1,2,…,n時，一定會有MB(i,:)≤MD(i,:)。那么|(～MC(i,:))∧(～MD(i,:)) |≤|(～MB(i,:))∧(～MD(i,:)) |，故有VC(D)≤VB(D)，因此ΓC(D)≤ΓB(D)。 □

從定理1 可以看出，S中的條件屬性集越小，它所對應(yīng)的協(xié)調(diào)性的程度越低。為了獲得不協(xié)調(diào)決策形式背景下的一個約簡集，下面給出條件屬性子集的相似度的概念。

定義9設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，B?A，稱為屬性B關(guān)于A的D的相似度。

定理2設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，B?A，B是廣義矩陣協(xié)調(diào)集的充要條件是E(B|A,D)=1。

證明(?)由于B是S的廣義矩陣協(xié)調(diào)集，則ΓB(D)=ΓA(D) 。從定義7 可得，VB(D)=VA(D) 。因此E(B|A,D)=1。(?) 由E(B|A,D)=1 可知，VB(D)=VA(D)。根據(jù)定義7 和定義8 可知，B是S的一個廣義矩陣協(xié)調(diào)集。 □

例2（續(xù)例1）不妨設(shè)B1={a1,a3,a5}，B2={a1,a2,a5,a6}。有下面結(jié)果：

同樣地，也能得到：

定義10 設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，B?A，?a∈B，則a關(guān)于B的內(nèi)重要度為：

從定義10 可以看出，a∈B的重要度是通過E(B|A,D)和E(B-{a}|A,D)之間的差異得到的。換句話說，當(dāng)a從B中刪去時，a在B中的重要度是通過MB和MB-{a}對MD之間的相似度變化大小來衡量的。

利用定義10 可得如下核心判定定理，為下面設(shè)計啟發(fā)式算法提供了簡單的方法。

定理3設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，a∈A是核心屬性的充要條件是Sig(A|a)>0，或者a∈A不是核心屬性的充要條件是Sig(A|a)=0。

證明(?)因為a∈A是核心屬性，則A-{a}不是廣義矩陣協(xié)調(diào)集，即ΓA-{a}(D)≠ΓA(D) 。根據(jù)A-{a}?A，由定理1 知，ΓA-{a}(D)≤ΓA(D)，故ΓA-{a}(D)<ΓA(D)。由定義10 得：

(?)由Sig(A|a)>0 知，E(A-{a}|A,D)<1。假設(shè)a不是核心屬性，則至少存在一個約簡集Q，使得a?Q且Q?A-{a}。由定理1 知，ΓQ(D)≤ΓA-{a}(D)，即VQ(D)≤VA-{a}(D)。則E(Q|A,D)≤E(A-{a}|A,D)<1，與Q是一個約簡集矛盾。因此a是核心屬性。 □

推論1設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，則Core(S)={a∈A:Sig(A|a)>0}。

證明由定理3 可直接得到。 □

定理4設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，B?A，若E(B|A,D)=1 并且?b∈B，Sig(B|b)>0，則B是S的一個約簡集。

證明由E(B|A,D)=1 及定理2 可知，B是S的一個廣義矩陣協(xié)調(diào)集。?E?B，?b0∈BE，使得E?B{b0}。由定理1 可以得到ΓE(D)≤ΓB{b0}(D)≤ΓA(D)。同樣有VE(D)≤VB{b0}(D)≤VA(D)。由假設(shè)?b∈B，Sig(B|b)=。由 上述可知b0∈B，故VB(D)>，從而就可以得到VE(D)≤VB{b0}(D)

定義11 設(shè)S=(U,A,I,D,J)是一個不協(xié)調(diào)決策形式背景，B?A，?a∈A-B，則a關(guān)于B的外重要度為：

根據(jù)上述討論，可以設(shè)計一個啟發(fā)式算法尋找不協(xié)調(diào)決策形式背景下的一個極小約簡。

算法1不協(xié)調(diào)決策形式背景S=(U,A,I,D,J)的一個約簡集的啟發(fā)式算法。

此算法第1 步的時間復(fù)雜度為O(|U|2|A|+|U|2|D|)；第2 步用于找出所有的核心屬性，此時間復(fù)雜度為O(|U|2|A|2)；在第4、5 步的過程中，時間復(fù)雜度不超過O(|U|2|A|2)，故算法1 的時間復(fù)雜度為O(|U|2|A|2)。相較于文獻(xiàn)[7]的時間復(fù)雜度O(|U|2(|A|3+|D|))更低。

例3（續(xù)例1）從例1 中可知，S是不協(xié)調(diào)決策形式背景以及S的協(xié)調(diào)性程度為

根據(jù)算法1 計算?a∈A的重要度根據(jù)推論1 知

根據(jù)定義11，{a3,a4,a5,a6}關(guān)于Core(S)的外重要度分別為Sig(ai|Core(S))=0(i=3,4,5)，以及從而有P={a1,a2,a6}。由定理4 可以得到E(P|A,D)=1且Sig(P|a)>0，?a∈P。故而有P={a1,a2,a6}是S的一個約簡集。可以看出，把a3、a4、a5從不協(xié)調(diào)決策形式背景S的條件屬性集A中刪去，子背景(U,P,IP,D,J)的協(xié)調(diào)性程度仍為

4 結(jié)束語

屬性約簡是決策形式背景的重要研究熱點之一。本文針對不協(xié)調(diào)決策形式背景的屬性約簡給出了相應(yīng)的啟發(fā)式算法。首先通過布爾矩陣的運算刻畫屬性之間的相似度。接著討論了判斷廣義矩陣協(xié)調(diào)集和核心屬性的等價條件。在此基礎(chǔ)上，提出了啟發(fā)式的約簡算法，并通過實例說明該算法的有效性。值得注意的是，此方法的提出，為借助矩陣研究形式概念分析拓寬了新視角。本文下一步要考慮的是，借助矩陣運算考慮模糊形式背景的屬性約簡問題。