不協調決策形式背景的矩陣型屬性約簡*

張呈玲，李進金+，林藝東,2

1.閩南師范大學 數學與統計學院，福建 漳州363000

2.廈門大學 數學科學學院，福建 廈門361005

1 引言

形式概念分析（formal concept analysis）是由德國數學家Wille[1-2]提出的一種分析數據的有效工具。它的核心是形式背景和概念格。形式背景是由對象集、屬性集以及對象和屬性之間的二元關系構成的。而概念格是將形式背景里的對象子集和屬性子集以一種概念層次體現出來。近年來，形式概念分析已被廣泛應用于概念認知[3]、知識提取[4]等領域。

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

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

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

2 預備知識

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

定義1[1]設F=(U,A,I)是形式背景，其中U={x1,x2,…,xn}為對象集，A={a1,a2,…,am}為屬性集，I是U和A之間的二元關系，且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 數值表呈現。1 是指對象具有x屬性a，即(x,a)∈I；0 是指對象x不具有屬性a，即(x,a)?I。為表述方便，因此形式背景可看成布爾矩陣MI=(cij)n×m，稱MI是F的一個關系矩陣。其中：

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

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

定義2[5]設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是布爾矩陣，有以下運算性質：

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

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

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

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

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

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

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

3 基于布爾矩陣的不協調決策形式背景的屬性約簡

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

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

例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的條件關系矩陣和決策關系矩陣分別為：

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

可以看出MA≤MD不成立。由定義6 可知，S是不協調的。

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

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

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

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

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

證明由C?B?A，則MA≤MB≤MC。要說明ΓC(D)≤ΓB(D)，只需證明VC(D)≤VB(D) 。由于當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中的條件屬性集越小，它所對應的協調性的程度越低。為了獲得不協調決策形式背景下的一個約簡集，下面給出條件屬性子集的相似度的概念。

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

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

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

例2（續例1）不妨設B1={a1,a3,a5}，B2={a1,a2,a5,a6}。有下面結果：

同樣地，也能得到：

定義10 設S=(U,A,I,D,J)是一個不協調決策形式背景，B?A，?a∈B，則a關于B的內重要度為：

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

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

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

證明(?)因為a∈A是核心屬性，則A-{a}不是廣義矩陣協調集，即ΓA-{a}(D)≠ΓA(D) 。根據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。假設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設S=(U,A,I,D,J)是一個不協調決策形式背景，則Core(S)={a∈A:Sig(A|a)>0}。

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

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

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

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

根據上述討論，可以設計一個啟發式算法尋找不協調決策形式背景下的一個極小約簡。

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

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

例3（續例1）從例1 中可知，S是不協調決策形式背景以及S的協調性程度為

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

根據定義11，{a3,a4,a5,a6}關于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從不協調決策形式背景S的條件屬性集A中刪去，子背景(U,P,IP,D,J)的協調性程度仍為

4 結束語

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