不協(xié)調(diào)決策形式背景的矩陣型屬性約簡(jiǎn)*

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

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

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

1 引言

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

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

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

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

2 預(yù)備知識(shí)

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

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

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

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

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

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

通常，形式背景是以0-1 數(shù)值表呈現(xiàn)。1 是指對(duì)象具有x屬性a，即(x,a)∈I；0 是指對(duì)象x不具有屬性a，即(x,a)?I。為表述方便，因此形式背景可看成布爾矩陣MI=(cij)n×m，稱(chēng)MI是F的一個(gè)關(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)稱(chēng)為F的一個(gè)子背景。

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

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

接著，通過(guò)上面的矩陣的運(yùn)算給出對(duì)象的粒矩陣描述。

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

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

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

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

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

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

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

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

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

例1 表1 為一決策形式背景，其中對(duì)象集、條件屬性集、決策屬性集分別為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的條件對(duì)象粒矩陣和決策粒矩陣分別為：

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

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

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

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

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

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

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

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

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

定理2設(shè)S=(U,A,I,D,J)是一個(gè)不協(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的一個(gè)廣義矩陣協(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)是一個(gè)不協(xié)調(diào)決策形式背景，B?A，?a∈B，則a關(guān)于B的內(nèi)重要度為：

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

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

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

證明(?)因?yàn)閍∈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不是核心屬性，則至少存在一個(gè)約簡(jiǎn)集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是一個(gè)約簡(jiǎn)集矛盾。因此a是核心屬性。 □

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

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

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

證明由E(B|A,D)=1 及定理2 可知，B是S的一個(gè)廣義矩陣協(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)是一個(gè)不協(xié)調(diào)決策形式背景，B?A，?a∈A-B，則a關(guān)于B的外重要度為：

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

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

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

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

根據(jù)算法1 計(jì)算?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的一個(gè)約簡(jiǎn)集?？梢钥闯觯補(bǔ)3、a4、a5從不協(xié)調(diào)決策形式背景S的條件屬性集A中刪去，子背景(U,P,IP,D,J)的協(xié)調(diào)性程度仍為

4 結(jié)束語(yǔ)

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