蘊涵的決策蘊涵表示研究

王亞麗，翟巖慧,2+，張少霞，賈 楠，李德玉,2

1.山西大學 計算機與信息技術學院，太原 030006

2.山西大學 計算智能與中文信息處理教育部重點實驗室，太原 030006

形式概念分析（formal concept analysis，F(xiàn)CA）是由德國Wille 教授于1982 年提出的一種通過形式背景建立概念格來對數(shù)據(jù)進行分析和提取規(guī)則的一個強有力的工具。它可以根據(jù)形式背景中對象和屬性之間的相互關系來得到數(shù)據(jù)與數(shù)據(jù)之間隱含的概念并建立它們之間的代數(shù)結構，即概念格[1-2]。目前，F(xiàn)CA 已被廣泛地應用到機器學習、社會網絡、軟件工程、信息檢索、基于認知的概念學習、知識約簡等相關領域[3-14]。

形式概念分析（概念格）中對知識獲取的研究就是對蘊涵的研究[15-20]，但由于蘊涵數(shù)目龐大，無法滿足用戶的需求，因此如何獲取完備無冗余的蘊涵規(guī)則集仍是研究的熱點[16]。文獻[16]從邏輯方面對完備性和無冗余性進行了討論，其中Ganter等已經討論了蘊涵的語義特征和語構特征，提出了三條蘊涵推理規(guī)則，而且證明了這三條推理規(guī)則相對于蘊涵的語義是完備的，并給出了源于文獻[21]的一個蘊涵基（完備無冗余的蘊涵集合）。已經證明，該蘊涵基在所有蘊涵基中所含的蘊涵個數(shù)最少。Qu 等進一步討論蘊涵和邏輯的關系，提出了一種新的蘊涵基，并給出一種有效的方法來生成該蘊涵基[22]。

為了減少蘊涵的數(shù)目，Qu 等提出了決策背景及決策蘊涵的概念[23]，并討論了一種直觀的推理規(guī)則（α推理規(guī)則），該推理規(guī)則通過增加決策蘊涵的前提或者減小決策蘊涵的結論來導出新的決策蘊涵[19]。文獻[19]還討論了基于該推理規(guī)則的完備性和冗余性，并提出了一種基于最小生成子[24]的決策蘊涵規(guī)范基生成算法。另外，文獻[25]提出了一種基于真前提的決策蘊涵規(guī)范基生成算法，實驗結果表明該算法效率更高。

研究發(fā)現(xiàn)，α推理規(guī)則在語構特征上并非是完備的，因此文獻[23]提出了合并推理規(guī)則，并證明合并推理規(guī)則和α推理規(guī)則（擴增推理規(guī)則）是完備的推理規(guī)則集。在此基礎上，文獻[26]又給出一條新的推理規(guī)則——后件合并推理規(guī)則，它只對前件相同的決策蘊涵的后件進行合并。因此，后件合并推理規(guī)則在形式上更簡潔。文獻[26]也證明了擴增推理規(guī)則和后件合并推理規(guī)則是合理的、完備的并且是無冗余的。

此外，文獻[27]給出了一個決策蘊涵基（稱為決策蘊涵規(guī)范基）。該規(guī)范基基于決策前提[28]，即由決策前提作為該決策蘊涵集的前提，由決策前提相對于決策子背景的閉包作為該決策蘊涵集的結論。文獻[27]還證明了該決策蘊涵規(guī)范基是完備的、無冗余的，并且在所有完備的決策蘊涵集中所含的決策蘊涵最少，因而決策蘊涵規(guī)范基是最精簡的和最優(yōu)的。研究結果表明，決策蘊涵規(guī)范基是蘊涵規(guī)范基[16]在決策背景下的對應概念，并且具有蘊涵規(guī)范基的所有優(yōu)點。

事實上，決策蘊涵是一種特殊的蘊涵，因此，決策蘊涵的研究就是在蘊涵中建立并研究一個/多個封閉的子系統(tǒng)（包括決策蘊涵子系統(tǒng)及相應的語義和語構子系統(tǒng)），其中，不同的條件/決策屬性劃分決定了不同的封閉子系統(tǒng)。因此，蘊涵與決策蘊涵的研究本質上就是封閉系統(tǒng)與封閉子系統(tǒng)的研究。

本文將從語構方面深入研究由這些子系統(tǒng)（決策蘊涵）能不能得到整個系統(tǒng)（所有的蘊涵）。如果蘊涵可以由決策蘊涵推出，那么關于蘊涵的研究就可以轉化為決策蘊涵的研究。這樣就可以由決策蘊涵來生成蘊涵，甚至可以由決策蘊涵規(guī)范基生成蘊涵規(guī)范基。因此，蘊涵是否能由決策蘊涵表示是一個值得研究的問題。事實上，這種研究對于進一步厘清和發(fā)展蘊涵和決策蘊涵都是非常必要的。

1 FCA 基本概念

本章簡要介紹形式概念分析中的一些基本概念。

定義1[16]形式背景是一個三元組K=(G,M,I)，其中G是對象集，M是屬性集，I?G×M是對象和屬性之間的二元關系。對于g∈G，m∈M，(g,m)∈I表示“對象g具有屬性m”。

定義2[16]設K=(G,M,I)是一個形式背景，對于集合A?G，記：

相應地，對于集合B?M，記：

對于g∈G，為了簡單起見，將{g}I記為gI。

定義3[16]設K=(G,M,I)是一個形式背景，對于集合A?G和B?M，若AI=B且BI=A，則稱二元組(A,B)為形式概念，簡稱概念。其中A為該概念的外延，B為該概念的內涵。?(K)稱為K的所有概念的集合。

定義4[16]設K=(G,M,I)是一個形式背景，C1=(A1,B1)和C2=(A2,B2)是K的兩個概念，定義偏序：

其中，C2是C1的超概念，C1是C2的子概念，所有概念在該偏序下構成格，稱為概念格。

2 蘊涵

在形式概念分析中，屬性之間的依賴可以通過蘊涵來描述。M中屬性之間的蘊涵是M的一對子集，記為A→B，集合A是蘊涵A→B的前提，B是A→B的結論[16]。下面給出蘊涵相關的一些定義。

定義5[16]設K=(G,M,I)是一個形式背景，A,B?M，如果每一個具有屬性集A的對象都具有屬性集B，則A→B叫作形式背景K下的一個蘊涵。

定義6[16]設K=(G,M,I)是一個形式背景，T?M且A→B是形式背景K下的一個蘊涵。如果屬性子集A?T或B?T，則稱T是蘊涵A→B的一個模型，記為T╞(A→B)。設Θ為一蘊涵集，如果對每一個(A→B)∈Θ都有T╞(A→B)，則稱T是Θ的一個模型，記為T╞Θ。

定義7[16]設K=(G,M,I)是一個形式背景，Θ為K的一個蘊涵集，若對于任意的T?M，T╞Θ蘊含T╞A→B，則稱A→B可以從Θ語義導出，記為Θ├A→B。若任意的A→B∈Θ且(Θ(A→B))├(A→B)，則稱A→B相對于Θ是冗余的。

定義8[16]設K=(G,M,I)是一個形式背景，Θ為K的一個蘊涵集，若對任意的A→B，Θ├A→B均成立，則稱Θ是K的一個完備集。

以上是對蘊涵語義方面的研究，事實上，除了語義特征，蘊涵也有語構特征。通過蘊涵的語構特征，可以使用推理規(guī)則集從蘊涵集Θ導出新蘊涵[16]：

（1）X→X，X?M（自反性推理規(guī)則）；

（2）若X→Y∈Θ，則X?Z→Y∈Θ，X，Y，Z?M（增廣性推理規(guī)則）；

（3）若X→Y∈Θ且Y?Z→W∈Θ，則X?Z→W∈Θ，W，X，Y，Z?M（偽傳遞性推理規(guī)則）。

文獻[29]已經證明這三條推理規(guī)則相對于蘊涵的語義是完備的，即從Θ中導出的任意蘊涵都可以重復使用上述三條推理規(guī)則從Θ中推出。

3 決策蘊涵

決策蘊涵可以從兩個角度進行研究：邏輯角度和數(shù)據(jù)角度。本章主要介紹決策蘊涵的邏輯研究，分為語義特征和語構特征兩部分。

3.1 決策蘊涵的語義特征

首先給出決策背景及決策蘊涵的定義。

定義9[19]設K=(G,M,I)是一個形式背景，如果令M=C?D，I=IC?ID，其中C是條件屬性集，D是決策屬性集，C?D=?，IC=G×C是條件關系，ID=G×D是決策關系，此時K=(G,C,D,I) 為一個以C為條件，D為決策的決策背景。反過來，如果以D為條件屬性集，C為決策屬性集，ID=G×D為條件關系，IC=G×C為決策關系，此時K=(G,D,C,I)是一個以D為條件，C為決策的決策背景。

定義10[19]設K=(G,C?D,IC?ID)是一個決策背景，對于集合A1?C，A2?D和B?G，記：

對于g∈G和A?C，將{g}C、{g}D和(AC)D簡記為gC、gD和ACD。

定義11[19]設K=(G,C?D,IC?ID)是一個決策背景，若A?C且B?D，則稱A→B是一個決策蘊涵。此時，A為該決策蘊涵的前提，B為該決策蘊涵的結論。

3.2 決策蘊涵的語構特征

本文只關注決策蘊涵的語構，語義方面的研究請參考文獻[23]。

決策蘊涵的語構方面主要研究推理規(guī)則的合理性、完備性和無冗余性。文獻[23]提出兩條推理規(guī)則：

擴增推理規(guī)則：

合并推理規(guī)則：

并且證明這兩條推理規(guī)則是合理的、完備的且是無冗余的。

文獻[26]在此基礎上又提出了一條新的推理規(guī)則——后件合并推理規(guī)則：

后件合并推理規(guī)則是一種特殊的合并推理規(guī)則，它只對前件相同的決策蘊涵的后件進行合并。因此，后件合并推理規(guī)則在形式上更簡潔。文獻[26]也證明了擴增推理規(guī)則和后件合并推理規(guī)則是合理的、完備的并且是無冗余的。

4 決策蘊涵表示蘊涵

首先從邏輯的角度來解釋決策蘊涵表示蘊涵的含義。邏輯角度的分析可以從語義和語構兩方面進行，為了簡潔，本文主要使用語構的方式來分析這個問題。從語構上看，如果將決策蘊涵看作蘊涵的一個子系統(tǒng)，那么決策蘊涵可以表示蘊涵就意味著可以在一個/多個決策蘊涵集上應用蘊涵上的三條推理規(guī)則得出整個蘊涵系統(tǒng)。同時，因為決策蘊涵上的推理規(guī)則（簡稱決策推理規(guī)則）是蘊涵上推理規(guī)則（簡稱蘊涵推理規(guī)則）的特例，因此，使用決策推理規(guī)則可以推導出的蘊涵必然也可以使用蘊涵推理規(guī)則推導出。另一方面，蘊涵上的推理規(guī)則并不僅僅只有第2 章中描述的三條蘊涵推理規(guī)則，還可能存在其他的推理規(guī)則。但是，文獻[29]已經證明這三條推理規(guī)則是完備的，因此在這里只考慮這三條推理規(guī)則；換句話說，如果蘊涵不能由這三條推理規(guī)則歸結為決策蘊涵，那么其他推理規(guī)則也必然不能將蘊涵歸結為決策蘊涵。

4.1 蘊涵表示的邏輯簡化

為了使用決策蘊涵表示蘊涵，先引入下面的引理對需要表示的蘊涵進行簡化。

引理1設A→B是形式背景K下的一個蘊涵，則蘊涵A→B成立，當且僅當?bi∈B，A→bi均成立。

證明（必要性）因為bi∈B，所以有B={bi}?(B-{bi}) 。又因為A→B成立，所以A→{bi}?(B-{bi}) 。由自反性推理規(guī)則可知{bi}→{bi}成立，再由增廣性推理規(guī)則可知{bi}?(B-{bi})→{bi}成立，最后由偽傳遞性推理規(guī)則及A→{bi}?(B-{bi})且{bi}?(B-{bi})→{bi}成立可知A→bi成立。

（充分性）先證明A→{b1}?{b2}成立。由自反性推理規(guī)則可知{b1}?{b2}→{b1}?{b2}成立，因為A→bi成立，由偽傳遞性推理規(guī)則及A→b1且{b1}?{b2}→{b1}?{b2} 成立可知A?{b2}→{b1}?{b2} 成立，即A→{b1}?{b2}成立，因為A?{b2}=A。接下來，令B1?{b1}?{b2}，按照上述方法可證明A→B1?{b3}成立。以此類推，可證明A→B成立。

由引理1 可知，如果所有的A→bi均可由決策蘊涵表示，則A→B可由A→bi合并得出，因此也可由決策蘊涵表示，故只討論后件中只有一個屬性的蘊涵即可。

進一步，蘊涵的前件也可以被簡化。

引理2設A→b是形式背景K下的一個蘊涵，A1?A。若A1→b成立，則A→b成立。

證明由增廣性推理規(guī)則可知結論成立。

引理2 說明只要求出b成立的最小前件A1，就可以得到蘊涵A→b，因此，只要A1→b可由決策蘊涵表示，則A→b可由A1→b通過增廣性推理規(guī)則得出，進而也可由決策蘊涵表示。故只討論前件最小的蘊涵A→b即可。顯然，此時有b?A，因為A→b成立當且僅當A→b，這與A是最小前件矛盾。

綜合引理1 和引理2 的結論可知，形如A→b(b?A)的蘊涵可由決策蘊涵表示，則所有的蘊涵都可由決策蘊涵表示。

4.2 蘊涵表示的幾種情況

接下來，具體分析形如A→b(b?A)的蘊涵。

在形式背景K=(G,M,I) 中，如果令M=C?D，I=IC?ID，即K=(G,C?D,IC?ID)，則蘊涵A→b在K中存在六種情形：

（1）A?C，b∈D；

試驗固定鮮花椒的添加量為 150 g，菜籽油添加量為 650 g，考察十三香添加量對“貢椒魚”火鍋品質的影響，結果見圖2。

（2）A?D，b∈D；

（3）A?C≠?，A?D≠?，b∈D；

（4）A?C，b∈C；

（5）A?D，b∈C；

（6）A?C≠?，A?D≠?，b∈C。

情形（1）、（2）、（3）可綜合表示為A2?A3→b，其中A2?C，A3?D，b∈D，A2?A3=A；情形（4）、（5）、（6）可綜合表示為A2?A3→b，其中A2?C，A3?D，b∈C，A2?A3=A。

顯然，情形（1）為K=(G,C,D,I)上的決策蘊涵，情形（5）為K=(G,D,C,I) 上的決策蘊涵；情形（2）為K=(G,D,I) 上的蘊涵，情形（4）為K=(G,C,I) 上的蘊涵。這說明，情形（1）和（5）已經歸結為決策蘊涵；情形（2）和（4）已經歸結為子背景上的蘊涵，因此可以按照后述方法，進一步將（2）和（4）歸結為子背景上的決策蘊涵。

需要判斷形如情形（3）和（6）的蘊涵是否能由決策蘊涵表示出來。在語義上，若形如情形（3）、（6）的蘊涵能由形如情形（1）、（2）、（4）、（5）的蘊涵通過蘊涵推理規(guī)則得出，則形如情形（3）、（6）的蘊涵是冗余的。另外，注意到互換情形（3）中C和D即可得到情形（6），反之亦然。這說明，如果情形（3）是冗余的，則情形（6）必然也是冗余的；如果情形（3）不是冗余的，需要一些特殊的方法才能生成，則互換方法中C和D，即可生成情形（6）的蘊涵。因此，只需考慮情形（3）即可。

現(xiàn)在考慮情形（3）中蘊涵A→b的表示。首先，有下面的結論。

引理3設K=(G,C?D,IC?ID)是一個決策背景，A→b是K上的一個蘊涵，其中A?C≠?，A?D≠?，b∈D。如果A→b可以被決策蘊涵表示，則A→b最后一步必然是使用偽傳遞性推理規(guī)則推導出的。

證明如果A→b可以被表示，那么A→b必然是由三條蘊涵推理規(guī)則推導出來的。如果利用自反性推理規(guī)則，因為該推理規(guī)則具有自反性，顯然不能說明A→b可以被決策蘊涵表示。因此，不能使用該推理規(guī)則推導出A→b。

對于增廣性推理規(guī)則，若X?Z→Y可應用于A→b，則X?Z=A和Y=。由于A為能使蘊涵b成立的最小前件，因此對于任何N?A，N→均不成立。顯然，為了使推理規(guī)則有意義，Z≠?，此時仍有X?A。當X?A時，X→不成立，即不能由X→得到A→b；當X=A時，X→即為A→b，這表示A→b依賴于A→b。因此，增廣性推理規(guī)則不能說明A→b可以被決策蘊涵表示，不能使用該推理規(guī)則推導出A→b。

下面考慮偽傳遞性推理規(guī)則。顯然，如果A→b可以使用偽傳遞性推理規(guī)則推導出，則必有

成立。此時有X?Z=A。顯然，當X→Y或Y?Z→b等于A→b時，該推理事實上是無效的。同時，若X→Y或Y?Z→b依賴于A→b時，則A→b也不能用偽傳遞性推理規(guī)則推導出；其中，X→Y依賴于A→b是指滿足條件b∈Y且A?X，因為X→Y依賴于X→b，而X→b可由A→b使用增廣性推理規(guī)則推得；類似地，Y?Z→b依賴于A→b是指A?Y?Z。進一步，有下面的結論。

定理1設K=(G,C?D,IC?ID)是一個決策背景，A→b是K上的一個蘊涵，其中A?C≠?，A?D≠?，b∈D。A→b可以使用偽傳遞性推理規(guī)則推導出，當且僅當存在X,Y,Z?C?D，滿足X≠?，Y≠?，b?Y，Y?Z?A，A?Y?Z，X?Z=A且使式（1）成立。

證明（必要性）若X=?，則Z=A，而要使?→Y成立，Y只能為?，從而Y?Z→b即 為A→b，因此X≠?。

現(xiàn)證Y≠?。由于A為能使蘊涵b成立的最小前件，因此對于任何N?A，N→均不成立。由X?Z=A可知Z?A；當Z?A時Z→不成立，為使Y?Z→b成立，有Y≠?；當Z=A時，Z→即為A→b，若Y=?，則Y?Z→b即為A→b，這表示A→b依賴于A→b，因此A→b不能用偽傳遞性推理規(guī)則推導出，仍有Y≠?。

現(xiàn)假設b∈Y，因為X→Y成立，由引理1 可知X→b成立。此時，由X?Z=A可 知X?A，因 為X?Z為能使蘊涵X?Z→b成立的最小前件，所以，當X?A時X→b不成立，矛盾；當X=A時，X→b即為A→b，因此X→Y依賴于A→b，這表示A→b不能用偽傳遞性推理規(guī)則推導出。因此有b?Y。

現(xiàn)假設Y?Z?A。因為A為能使蘊涵A→b成立的最小前件，所以，當Y?Z?A時Y?Z→b不成立，矛盾。因此有Y?Z?A。

現(xiàn)假設A?Y?Z，由增廣性推理規(guī)則可知，Y?Z→b可以由A→b推得，這表示Y?Z→b依賴于A→b。因此有A?Y?Z。

（充分性）因為A為能使蘊涵A→b成立的最小前件，所以對于任何N?A，N→ 均不成立，Y?Z?A保證了Y?Z→b的可成立性。由題設可知，為證明A→b可以使用偽傳遞性推理規(guī)則推導出，只需證X→Y和Y?Z→b不等于且不依賴 于A→b即可。

由b?Y可知X→Y不等于且不依賴于A→b。

由A?Y?Z可知，Y?Z→b不等于且不依賴于A→b。

在定理1 中，因為X,Y,Z?C?D，所以X→Y和Y?Z→b均可能屬于情形（3）或情形（6），換句話說，情形（3）又依賴于情形（3）或情形（6）。因此，可將定理1 進一步分為兩種情況：一種情況是可以使用偽傳遞性推理規(guī)則由情形（1）、（2）、（4）、（5）推導出情形（3），稱為直接表示；另一種情況是情形（3）必須依賴于情形（3）或（6）才能推導出，稱為間接表示。

由于蘊涵推理的復雜性，目前暫未發(fā)現(xiàn)需要間接表示的蘊涵，因此本文只考慮直接表示。首先給出直接表示A→b的判定條件。

定理2設K=(G,C?D,IC?ID)是一個決策背景，A→b是K上的一個蘊涵，其中A?C≠?，A?D≠?，b∈D。A→b可以使用偽傳遞性推理規(guī)則直接表示當且僅當存在X≠?，Y≠?，b?Y，Y?Z?A，A?Y?Z，X?Z=A且滿足以下條件之一：

（1）X=A2，Z=A3，且存在Y?D使式（1）成立；

（2）X=A3，Z=A2，且存在Y?C使式（1）成立。

證明根據(jù)題設，A→b屬于情形（3）中的蘊涵。

（必要性）若情形（3）中A→b可以使用偽傳遞性推理規(guī)則直接表示，則必滿足定理1 所給條件；進一步，X→Y和Y?Z→b均不屬于情形（3）或（6）的蘊涵。因此，X必不滿足X?C≠?且X?D≠?，Z必不滿足Z?C≠?且Z?D≠?，此時有X=A2,Z=A3或X=A3,Z=A2。當X=A2,Z=A3時，X→Y必不屬于情形（3）或（6），Y?Z→b不屬于情形（3）或（6）時Y需滿足Y?C=?，即Y?D；當X=A3,Z=A2時，X→Y必不屬于情形（3）或（6），Y?Z→b不屬于情形（3）或（6）時Y需滿足Y?D=?，即Y?C。

（充分性）由假設和定理1 可知，A→b可以使用偽傳遞性推理規(guī)則表示。

現(xiàn)分別假設條件（1）、（2）成立時來證X→Y和Y?Z→b必不屬于或依賴于情形（3）或（6）。

（1）當X=A2，Z=A3且存在Y?D時，顯然，X→Y屬于情形（1），Y?Z→b屬于情形（2）。

（2）當X=A3，Z=A2且存在Y?C時，顯然，X→Y屬于情形（5），Y?Z→b屬于情形（1）。

定理1 雖然給出了情形（3）中A→b冗余的充要條件，但仍不能確定情形（3）的冗余性。下面給出一個例子，來說明情形（3）不是冗余的，換句話說，存在情形（3）所示的蘊涵不能被決策蘊涵表示。

例1一個決策背景如表1 所示，其中{x1,x2,x3,x4}代表4個對象，{a}是條件屬性集，{b,d}是決策屬性集。

Table 1 Decision context表1 決策背景

顯然，{a}?g0gggggg→b是該決策背景的蘊涵，令A2{a}，A3g0gggggg，則{a}?g0gggggg→b屬于情形（3）。接下來，利用偽傳遞性推理規(guī)則來推導該蘊涵。由定理1，首先假設X≠?，Y≠?。

首先考慮Z=?的情況。此時，需要找到Y使

成立。Y所有可能的取值為{a,b,d,ab,ad,bd,abd} 。當Y取{a,d}中的任意一個時，Y→b均不成立；當Y取{b,ab,ad,bd,abd}中的任意一個時，用到{a}?g0gggggg→b本身。因此，當Z=?時，不存在Y使{a}?g0gggggg→b可以由其他蘊涵推導出，即{a}?g0gggggg→b不冗余。

接下來考慮Z≠?的情況。此時需要找到Y使

成立。Y所有可能的取值為{a,b,d,ab,ad,bd,abd} 。當Y取{b,d,ab,ad,bd,abd}中的任意一個時，{a}→Y不成立；當Y取{ }a時，用到{a}?g0gggggg→b本身。類似地，當Y取{a,b,ab,ad,bd,abd}中的任意一個時，g0gggggg→Y不成立；當Y取g0gggggg 時，Y?{a}→b不成立。因此，當Z≠?時，不存在Y使{a}?g0gggggg→b可以由其他蘊涵推導出，即{a}?g0gggggg→b不冗余。

4.3 蘊涵表示的具體方法

例1 表明，某些蘊涵確實不可直接歸結為決策蘊涵和子背景的蘊涵。因此，需找到蘊涵不可以被直接表示時Y應滿足的條件，并生成相應的蘊涵。為此，首先討論決策屬性只有一個屬性的情形下，Y存在或不存在的情況。有下面的結論。

引理4設K=(G,C?D,IC?ID)是一個決策背景，A→b是K上的一個蘊涵，其中A?C≠?，A?D≠?，b∈D。若決策屬性D中只有一個屬性，則A→b是冗余的。

證明根據(jù)題設，A→b屬于情形（3）中的蘊涵。若決策屬性D中只有一個屬性，由于b∈D，因此有A3=，故A→b是冗余的。事實上，由自反性推理規(guī)則可知→b成立，再由增廣性推理規(guī)則可知A→b成立。

接下來，分析當決策屬性D中只有一個屬性時，情形（6）中的蘊涵是否可以被直接表示。基于該情形的分析，可以將形式背景分為只含有一個決策屬性的決策背景，然后生成該決策背景中的決策蘊涵，因為情形（3）的蘊涵是冗余的，因此不需要生成，如果情形（6）中的蘊涵是不可以被直接表示的，則可以生成不可以被直接表示的蘊涵；接下來，就可以考慮去掉該決策屬性之后的形式背景；以此類推，可以生成所有的蘊涵集。

容易證明，定理1、定理2對于情形（6）也是成立的。

推論1設K=(G,C?D,IC?ID)是一個決策背景，A→b是K上的一個蘊涵，其中A?C≠?，A?D≠?，b∈C。A→b可以使用偽傳遞性推理規(guī)則推導出，當且僅當存在X,Y,Z?C?D，滿足X≠?，Y≠?，b?Y，Y?Z?A，A?Y?Z，X?Z=A且使式（1）成立。

推論2設K=(G,C?D,IC?ID)是一個決策背景，A→b是K上的一個蘊涵，其中A?C≠?，A?D≠?，b∈C。A→b可以使用偽傳遞性推理規(guī)則直接表示當且僅當存在X≠?，Y≠?，b?Y，Y?Z?A，A?Y?Z，X?Z=A且滿足以下條件之一：

（1）X=A2，Z=A3，且存在Y?D使式（1）成立；

（2）X=A3，Z=A2，且存在Y?C使式（1）成立。

下面的例子表明，當決策屬性D中只有一個屬性時，對于推論2 所示的兩種情況，情形（6）中的蘊涵不總是可以被直接表示的。

例2對于表1 中的決策背景，令{a,b}是條件屬性集，g0gggggg 是決策屬性集，則{a}?g0gggggg→b為蘊涵。令A2?{a}，A3?g0gggggg，則{a}?g0gggggg→b屬于情形（6）。接下來，利用偽傳遞性推理規(guī)則來推導該蘊涵。

首先考慮推論2 中（1）。此時，需要找到Y?D使式（1）成立。由表1 可知Y只能取g0gggggg，由g0gggggg→b不成立可知{a}?g0gggggg→b不可以被直接表示。

接下來考慮推論2 中（2）。此時，需要找到Y?C使式（1）成立。Y所有可能的取值為{a,b,ab}。無論Y取何值，g0gggggg→Y均不成立，因此{a}?g0gggggg→b不可以被直接表示。

由例2 可知，需找出當決策屬性D中只有一個屬性時，對于推論2 所示的兩種情況，情形（6）中的蘊涵A→b不可以被直接表示的充要條件及發(fā)現(xiàn)算法。

對于推論2 中（1），有下面的結論。

引理5設K=(G,C?D,IC?ID)是一個決策背景，A→b是K上的一個蘊涵，其中A?C≠?，A?D≠?，b∈C。若決策屬性D中只有一個屬性，則X=A2，Z=A3，Y?D時，A→b不可以被直接表示。

證明當D中只有一個屬性d時，由Y≠?和Y?D可 知Y=g0gggggg，由Z=A3?D可 知Z=g0gggggg，由A?D≠?和A?C≠?可知Y?Z?A，再由A為能使蘊涵b成立的最小前件可知Y?Z→b不成立，從而A→b必不可以被直接表示。

由引理5 可知，當決策屬性D中只有一個屬性時，對于推論2 中（1），情形（6）中的蘊涵A→b是不可以被直接表示的，由于A→b可以被直接表示時只需滿足推論2 條件之一，因此，若對于推論2 中（2），A→b也不可以被直接表示，那么情形（6）中的蘊涵A→b必不可以被直接表示。接下來給出對于推論2中（2）情形（6）中的蘊涵A→b也不可以被直接表示的判定條件。

定理3設K=(G,C?D,IC?ID)是一個決策背景且D中只有一個屬性d。A→b是K上的一個蘊涵，其中A?C≠?，A?D≠?，b∈C。蘊涵A→b不可以被直接表示，當且僅當任意的Y?C均滿足以下條件之一：

（1）Y=?；

（2）b∈Y；

（3）Y?A2?A；

（4）A?Y?A2；

（5）存在g滿足gD=g0gggggg且Y?gC；

（6）存在g滿足(Y?A2)?gC且b?gC。

其中A=A3?A2,A3?D,A2?C,b∈C,g∈G。

證明根據(jù)題設，A→b屬于情形（6）中的蘊涵。由推論2 可知，情形（6）中的蘊涵A→b不可以被直接表示當且僅當條件（1）～（4）之一成立或推論2 中（1）和（2）皆不成立。若D中只有一個屬性d時，由引理5 可知，推論2 中（1）必不成立；因此，若D中只有一個屬性d時，情形（6）中的蘊涵A→b不可以被直接表示當且僅當條件（1）～（4）之一成立或推論2 中（2）不成立。現(xiàn)只需證推論2 中（2）不成立當且僅當條件（5）或（6）成立即可。

因為D中只有一個屬性d，所以A3=g0gggggg。因此，只需證不存在Y?C使式（2）成立

當且僅當條件（5）或（6）成立。這是顯然的，因為不存在Y?C使式（2）成立當且僅當不存在Y?C使g0gggggg→Y或Y?A2→b成立，當且僅當（存在g滿足gD=g0gggggg且Y?gC）或（存在g滿足(Y?A2)?gC且b?gC），當且僅當條件（5）或（6）成立。

當D中只有一個屬性d時，由引理5 可知，情形（3）中的蘊涵都是冗余的，因此不必生成；對于情形（6），定理3 事實上給出了不可被直接表示的蘊涵的生成方法。

對于形式背景K=(G,M,I)，令D=g0gggggg，C=MD，I=IC?ID，即得到只含一個決策屬性的決策背景KC|D=(G,C?D,IC?ID)和只含一個條件屬性的決策背景KD|C=(G,D?C,ID?IC)。生成形式背景K的具體步驟如下：

（1）生成決策背景KC|D的決策蘊涵。

（2）生成決策背景KD|C的決策蘊涵。

（3）生成K不可被直接表示的蘊涵：

①對于任意的A2?C和任意的b∈C執(zhí)行②和③。

②令A3=g0gggggg?D，A=A3?A2，根據(jù)定理3檢查是否存在Y?C滿足定理3 條件（1）～（6）之一。若滿足，則執(zhí)行步驟③，否則執(zhí)行①。

③判斷A→b是否成立。若成立，則生成蘊涵A→b。

（4）從K中移除屬性d，并記Kd=(G,Mg0gggggg,II{}d)，對Kd重新執(zhí)行該算法。

顯然，上述算法的復雜度較高，因此難以應用于具體的數(shù)據(jù)集中。

5 結論與展望

本文首先對蘊涵進行了邏輯簡化，然后使用蘊涵推理規(guī)則研究蘊涵是否可以由決策蘊涵表示，首先給出了蘊涵可以被直接表示時應滿足的條件。實例表明，不是所有的蘊涵都可以直接歸結為決策蘊涵，因此找出了不可以直接歸結為決策蘊涵的蘊涵應滿足的充要條件，并給出了不可以直接歸結為決策蘊涵的蘊涵的生成方法。

文中提到了蘊涵的間接表示，但由于蘊涵推理的復雜性，暫未對其進行深入研究。另外，即使不能被直接表示的蘊涵的生成算法也有較大的復雜度，因此難以應用于具體的數(shù)據(jù)。這些都是下一步需要研究的問題。

另外可以發(fā)現(xiàn)，存在一些蘊涵可以由決策蘊涵表示，那么決策蘊涵規(guī)范基與蘊涵規(guī)范基、決策蘊涵推理規(guī)則與蘊涵推理規(guī)則以及決策背景上的概念格與形式背景上的概念格之間又存在怎樣的聯(lián)系?進一步，本文的研究是否可以推廣到模糊決策蘊涵[17-18，30]以及可變決策蘊涵[31]？這些問題也是接下來需要研究的。