決策蘊涵上的推理規則和推理過程研究*

賈 楠，張少霞，翟巖慧，2+，李德玉，2

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

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

1 引言

形式概念分析是由德國Wille教授于1982年提出的一種從形式背景進行數據分析、知識表示和規則提取的強有力工具[1]。形式背景和形式概念是形式概念分析的兩個基本概念，概念格是從形式背景上提取的形式概念的集合，本質上是描述對象和屬性之間的關系，并通過Hasse圖來可視化概念之間的泛化和例化關系。目前，形式概念分析已經被廣泛應用于信息檢索[2]、軟件工程[3]、機器學習[4]、社會網絡[5]、基于認知的概念學習[6-10]和知識約簡[11-17]。

形式概念分析中對知識獲取的研究就是對蘊涵的研究[18-21]。蘊涵表示為形如A→B的公式，其含義是任意具有屬性集A的對象集同時也具有屬性集B。但是，從形式背景中得到的蘊涵的數量往往很龐大[19]。

引入決策蘊涵是減少蘊涵數量的一種方法，決策蘊涵是在決策情形下的蘊涵，也是決策背景下的知識表示形式，反映了條件屬性和決策屬性之間的決策關系[21-22]。從邏輯角度對決策蘊涵的研究分為語義和語構兩方面[22]，其中語義部分的研究包括以下幾方面[22-25]：

決策蘊涵的合理性：怎樣判斷決策蘊涵是否合理？或者說，決策蘊涵在什么情況下是成立的？

決策蘊涵集的封閉性：決策蘊涵集是否包含所有合理的決策蘊涵？

決策蘊涵集的完備性：如何在不損失信息的前提下生成一個決策蘊涵集？

決策蘊涵集的冗余性：一個決策蘊涵集是否是緊致的?即，是否存在某些決策蘊涵可以從決策蘊涵集中的其他決策蘊涵推導出來？

在語構方面，首先給定一個決策蘊涵集和一些推理規則，然后研究如何應用這些推理規則從給定的決策蘊涵集中推導出新的決策蘊涵。這個方面的研究需要回答下列問題[21-22]：

推理規則的合理性：是否推理規則推導出的任何決策蘊涵都是合理的？

推理規則集的完備性：是否可以由給定的推理規則集推導出所有合理的決策蘊涵？

推理規則集的無冗余性：推理規則之間是否是緊致的？即，是否某些推理規則可以由其他推理規則導出？

近年來，針對語構上的推理規則已經開展了一些研究工作。Qu等[21]考慮了一種特殊的推理規則——α-推理規則。該規則通過擴大決策蘊涵的前件和減少決策蘊涵的后件來得到新的決策蘊涵，但是該推理規則并不是完備的。Li等[26-30]研究了決策背景、不完備決策背景和實決策背景中的推理規則。Zhai等[22]提出了兩種推理規則——擴增推理規則和合并推理規則，并證明了它們的完備性，即給定一個完備集，可以通過擴增推理規則和合并推理規則從完備集中推導出對應的封閉集。雖然文獻[22]從理論上證明了擴增推理規則和合并推理規則的合理性和完備性，但并沒有具體研究如何使用推理規則推導出封閉集。本文提出了一種更簡單的推理規則——后件合并推理規則。后件合并推理規則是特殊的合并推理規則，它只對前件相同的決策蘊涵進行合并，證明了后件合并推理規則是合理的，并且該推理規則與擴增推理規則組成的推理規則集是完備的、無冗余的；進一步，研究了擴增推理規則和后件合并推理規則的性質，最后給出了使用這兩條推理規則從完備集推導其對應封閉集的有效方法。

2 基本概念和性質

本章給出形式概念分析中的基本概念和性質。

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

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

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

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

性質1[19]設K=(G,M,I)為形式背景，對于集合A,A1,A2?G和B,B1,B2?M有：

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

所有概念在該偏序下構成格，稱為概念格。

3 決策蘊涵

決策蘊涵有兩種研究方式：一種是決策蘊涵的邏輯研究；另一種是決策蘊涵的數據研究。決策蘊涵的邏輯研究包括語義和語構研究；決策蘊涵的數據研究主要指決策背景上的決策蘊涵研究。首先介紹決策蘊涵的邏輯研究。

3.1 決策蘊涵邏輯

3.1.1 決策蘊涵邏輯的語義

首先給出決策蘊涵邏輯中決策蘊涵的定義。

定義5[22]設C是條件屬性集，D是決策屬性集，其中C?D=?。若A?C且B?D，則稱A→B是一個決策蘊涵。此時，A為該決策蘊涵的前提，B為該決策蘊涵的結論。

定義6[22]設C是條件屬性集，D是決策屬性集，L和L1是決策蘊涵集。定義：

（1）對于屬性集T?C?D和決策蘊涵A→B，若A?T?C或B?T?D，則稱T滿足A→B（或稱T是A→B的一個模型），記為T╞A→B。若T滿足L中的任意一個決策蘊涵，則T是L的一個模型，記為T╞L。

（2）若對于任意的T?C?D T╞L蘊含T╞A→B，則稱A→B可以從L語義導出，記為L├A→B。若任意的A1→B1∈L1都可以從L語義導出，則稱L1可以從L中語義導出，記為L├L1。

（3）若任意的A→B∈L都不能從L中其他的決策蘊涵語義導出，即L{A→B}?/{A→B}，則稱L是無冗余的。

（4）若任意可以從L中語義導出的決策蘊涵都包含在L中，則稱L是封閉的。

（5）對于封閉的決策蘊涵集L，若L1?L且L├1L，則稱L1相對于L是完備的。

定義7[22]設C是條件屬性集，L是決策蘊涵集，A?C在L上的閉包為：

可以證明[22]，AL是A相對于L得到的最大結論。

定理1[22]設L為決策蘊涵集，A→B是一個決策蘊涵，則L├A→B當且僅當B?AL。

3.1.2 決策蘊涵邏輯的語構

決策蘊涵邏輯的語構研究包括推理規則的合理性、完備性和無冗余性。文獻[22]提出兩條推理規則：

擴增推理規則：

合并推理規則：

定理2[22]（合理性）擴增推理規則和合并推理規則是合理的，即：

（1）A→B是一個決策蘊涵，且有A1?A和B1?B，則A→B?A1→B1；

（2）A→B和A1→B1是決策蘊涵，則{A→B,A1→B1}?A?A1→B?B1。

定理3[22]（完備性）擴增推理規則和合并推理規則是完備的，即對任意封閉的決策蘊涵集L及其完備集L1?L，A→B∈L當且僅當A→B可以使用擴增推理規則和合并推理規則從L1推出。

定義8令L為決策蘊涵集：

（1）使用推理規則φ在L上得到的所有決策蘊涵的集合記為Lφ；

（2）使用推理規則集Φ在L上得到的所有決策蘊涵的集合記為LΦ。

推理規則集的無冗余性意味著推理規則之間不能互相導出，這說明每個推理規則在進行推理時都是不可替代的。

定義9[22]令Φ為推理規則集，φ為某一推理規則且φ?Φ。稱推理規則φ相對于Φ是無冗余的，若存在決策蘊涵集L，使得Lφ?LΦ。稱推理規則集Φ是無冗余的，若對任意的φ∈Φ，φ相對于Φφ是無冗余的。

定理4[22]（無冗余性）擴增推理規則和合并推理規則是無冗余的。

下面的例子說明了定理4的正確性。

例1令L={{a1}→{d1},{a1a2}→{d2}}。使用擴增推理規則從L可得{a1a2}→{d1}，顯然該決策蘊涵不能由合并推理規則得到。同樣地，對{a1}→{d1}和{a1a2}→{d2}使用合并推理規則得到{a1a2}→{d1d2}，顯然該決策蘊涵也不能只通過擴增推理規則得到。

這里，用{a1a2}表示{a1,a2}，后文類似。

3.2 決策背景中的決策蘊涵

下面給出決策蘊涵的數據研究，即決策背景上的決策蘊涵，并將決策蘊涵邏輯的研究運用到決策背景中的決策蘊涵上。

首先引入決策背景的概念。

定義10[21]決策背景為三元組K=(G,C?D,IC?ID)，其中G為對象集，C為條件屬性集，D為決策屬性集，且C?D≠?，IC?G×C為條件關聯關系，ID?G×D為決策關聯關系。對于g∈G m∈C?D(g,m)∈IC或(g,m)∈ID表示“對象g具有屬性m”。

決策背景K=(G,C?D,IC?ID)通常用一個二維表表示，在表中行列的交點處為1表示這個對象含有這個屬性。

例2表1給出決策背景K=(G,C?D,IC?ID)，其中，G={g1,g2,g3,g4,g5,g6,g7,g8}C={a1,a2,a3,a4,a5,a6}D={d1,d2}。

Table 1 Decision context表1 決策背景

定義11[21]設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。

顯然，性質1也適用于定義11的算子。例如，對于A1?A2?C，若。

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

例3以表1所示的決策背景為例，令A={a2a3}，則AC={g5g7} 令B={d2} 則BD={g2g5g7} 顯然，AC?BD，則A→B是一個決策蘊涵。

4 決策蘊涵上的推理規則和推理過程

4.1 決策蘊涵上的推理規則

3.1.2 小節引入了擴增推理規則和合并推理規則。在此基礎上，提出一條新的推理規則——后件合并推理規則：

顯然，后件合并推理規則是一種特殊的合并推理規則，它只對前件相同的決策蘊涵的后件進行合并。因此，后件合并推理規則在形式上更簡潔。

因為合并推理規則是合理的，因此后件合并推理規則也是合理的。

定理5（合理性定理）后件合并推理規則是合理的，即：若A→B1和A→B2是決策蘊涵，則{A→B1,A→B2}├A→B1?B2。

證明顯然。 □

下面證明擴增推理規則和后件合并推理規則是無冗余的。

首先，根據定義8，定義：

定義13令L為決策蘊涵集：

（1）使用擴增推理規則在L上得到的所有決策蘊涵的集合記為LA；

（2）使用后件合并推理規則在L上得到的所有決策蘊涵的集合記為；

（3）使用合并推理規則在L上得到的所有決策蘊涵的集合記為LC；

（4）先使用擴增推理規則得到LA，再使用后件合并推理規則得到，簡記為。

定理6（無冗余性定理）后件合并推理規則和擴增推理規則是無冗余的。

證明根據定義9，只需證明：

（1）存在決策蘊涵集L有；

（2）存在決策蘊涵集L有LCα?LA。

下面證明（1）。令L1={A1→B1}，其中B1≠?，令A2?A1，B2?B1，則由擴增推理規則可以得到決策蘊涵A2→B2。顯然，決策蘊涵A2→B2不能由后件合并推理規則推出。

下面證明（2）。令L2={A→B1,A→B2}，其中B1?B2且B2?B1，由后件合并推理規則可從L得到決策蘊涵A→B1?B2。顯然，決策蘊涵A→B1?B2不能由擴增推理規則推出。

綜上所述，后件合并推理規則和擴增推理規則是無冗余的。 □

例4令L={{a1}→{d1}{a1}→{d2}}。使用擴增推理規則從{a1}→{d1}可得{a1a2}→{d1}，顯然該決策蘊涵不能由后件合并推理規則推出。同樣地，對{a1}→{d1}和{a1}→{d2}使用后件合并推理規則得到{a1}→{d1d2}，顯然該決策蘊涵也不能只通過擴增推理規則得出。

進一步，可以得到：

性質2合并推理規則相對于擴增推理規則和后件合并推理規則是冗余的。

證明根據定義9，只需證明對任意的決策蘊涵集L若A→B∈LC那么A→B也可以通過擴增推理規則和后件合并推理規則得到。

因為A→B∈LC所以A→B必然可以通過L中的若干條決策蘊涵使用合并推理規則得到，即必存在P?L使得：

接下來證明通過擴增推理規則和后件合并推理規則可以從P得到A→B。

因為?{A1|A1→B1∈P}=A，所以對任意的A1→B1∈P有A1?A，進而可以對P中所有的決策蘊涵使用擴增推理規則得到集合：

又因為?{B1|A1→B1∈P}=B，使用后件合并推理規則，將P1中決策蘊涵的前件和后件分別進行合并即可得到A→B。 □

例5令L={{a1}→{d1},{a2a3}→{d2}}。使用合并推理規則可以從{a1}→{d1}和{a2a3}→{d2}得到{a1a2a3}→{d1d2}。事實上，也可以分別對{a1}→{d1}和{a2a3}→{d2}使用擴增推理規則得到{a1a2a3}→{d1}和{a1a2a3}→{d2}，然后再對{a1a2a3}→{d1}和{a1a2a3}→{d2}使用后件合并推理規則得到{a1a2a3}→{d1d2}。

事實上，性質2和例5也說明，在推導過程中，后件合并推理規則可以替代合并推理規則，因此擴增推理規則和后件合并推理規則也是完備的。

定理7（完備性定理）擴增推理規則和后件合并推理規則是完備的，即對任意封閉的決策蘊涵集L及其完備集L1?L A→B∈L當且僅當A→B可以使用擴增推理規則和后件合并推理規則從L1推出。

證明（充分性）根據定理2和定理5，擴增推理規則和后件合并推理規則是合理的，因此L1├A→B；而又因為L是封閉的，因此A→B∈L。

（必要性）因為A→B∈L根據定理3知道A→B可以使用擴增推理規則和合并推理規則從L1推出，因此A→B也可以使用擴增推理規則、合并推理規則和后件合并推理規則從L1推出；又根據性質2，合并推理規則相對于擴增推理規則和后件合并推理規則是冗余的，因此A→B可以只使用擴增推理規則和后件合并推理規則從L1推出。 □

4.2 決策蘊涵的推理過程研究

通過決策蘊涵的語構研究，可以使用推理規則集從決策蘊涵集導出新的決策蘊涵。4.1節中已證明了擴增推理規則和后件合并推理規則相對于決策蘊涵的語義是完備的，即從任意的決策蘊涵集開始，重復應用這兩條推理規則，可以得到給定決策蘊涵集的封閉集。在本節，將討論推理規則的性質，并將其應用在推理過程中，以便更有效地從決策蘊涵集得到封閉集。

下面，首先定義推理過程中的一些算子。

定義14令L為一決策蘊涵集，記：

（1）LA為對L中所有的決策蘊涵均使用一次擴增推理規則得到的所有決策蘊涵的集合，即：

方便起見，規定：

（1）對L中的決策蘊涵先進行一次A運算，再進行一次Cα運算記為，其余類似；

（2）從L開始，連續進行n次A運算記為，其余類似。

例6以表1中的決策背景為例，L={{a2a4a5a6}→{d1}{a1a3a4a5}→{d1}{a1a3a4a5}→{d2}}是它的一個決策蘊涵集。決策蘊涵集LA和分別如下所示：

根據定理7，對于完備集L，可以交替進行A運算和Cα運算，直至不再產生新的決策蘊涵即可得到，但是這樣的推導方式效率并不高。

下面，首先研究擴增推理規則和后件合并推理規則的性質以及如何通過A運算和Cα運算得到LA和（LA和分別是使用擴增推理規則和后件合并推理規則在L上得到的所有的決策蘊涵的集合，見定義13）。

性質3令L為一決策蘊涵集，則：

（1）L?LA

（2）LA=LAA

（3）LA=LA

證明

（1）對于任意的A→B∈L，因為A?A且B?B，因而A→B∈LA，因此有L?LA。

（2）根據（1），顯然有LA?LAA只需證明LAA?LA。令A→B∈LAALA，此時必存在A1→B1∈LA，并由此得到A→B，即有A?A1且B?B1。因為A1→B1∈LA，所以必存在A2→B2∈L，并由此得到A1→B1，即有A1?A2且B1?B2。因此得到A?A2且B?B2，結合A2→B2∈L可知A→B∈LA。

（3）因為LA是使用擴增推理規則在L上得到的所有的決策蘊涵的集合，所以必存在n使得LA=（一般都假設條件屬性集和決策屬性集為有限集，因此L也必為有限集，后文情況類似）。又因為LA=LAA，所以LA=LA。 □

例7以例6中的決策蘊涵集L為例，根據性質3可知，LA即為例6中的LA。

性質3和例7說明，在推導過程中，只需要對L中的所有決策蘊涵都進行一次A運算，即可得到通過擴增推理規則生成的所有決策蘊涵。

性質4令L為一決策蘊涵集，則：

證明

（1）對于任意的A→B∈L由因此。

共有兩種情況：

①m≤n。此時，由（1）和題設可得：

②m＞n因為所以：

例8以例6中的決策蘊涵集L={{a2a4a5a6}→{d1}{a1a3a4a5}→{d1}{a1a3a4a5}→{d2}}為例，對L多次進行Cα運算可得到集合LCα：

性質5令為封閉的決策蘊涵集且，則

證明顯然，因此只需證明。對任意的A→B∈，令P={A1→B1∈L|A1?A}，因為對于任意的A1→B1∈P，都有A1?A和B1?B?B1，所以可使用擴增推理規則得到A→B1?B，進而可推理得到集合P1={A→B1?B|A1→B1∈P} 此時，根據LA的定義有P1?LA。

接下來證明B=?{B1?B|A1→B1∈P}。

根據定義7可知AL=?{B1|A1→B1∈P} 因為且A→B∈根據定理1可知B?AL即B??{B1|A1→B1∈P} 則B?{B1|A1→B1∈P}=B而根據集合的分配律有B?(?{B1|A1→B1∈P})=?{B?B1|A1→B1∈P} 因此有?{B?B1|A1→B1∈P}=B此時，使用后件合并推理規則可以將P1中所有的決策蘊涵合并為A→B因而有A→B∈又因為P1?LA所以A→B∈。

綜上所述，對任意的A→B∈有A→B∈，因此。 □

性質5表明了生成封閉集不僅可以通過交替使用這兩條推理規則，也可以先使用擴增推理規則得到LA再對LA使用后件合并推理規則得到封閉集。

定理8令為封閉的決策蘊涵集且，則。

證明根據性質3可知LA=LA，因此

定理8在性質5的基礎上又進一步簡化了生成封閉集的過程，在推導過程中，僅對決策蘊涵集中所有的決策蘊涵應用一次擴增推理規則即可。

5 結論與展望

本文基于已有的擴增推理規則和合并推理規則，提出了后件合并推理規則。該推理規則不僅簡化了合并推理規則，而且具有合理性，與擴增推理規則組成的推理規則集也具有完備性和無冗余性;在此基礎上，研究了擴增推理規則和后件合并推理規則的性質，并應用于推導過程，提出具體的推導方法。在實際問題中會遇到各種不同的需求，而不同的推導方法有可能滿足不同的需求，因此也豐富了從決策蘊涵集得到封閉集的方法理論。

另外，這一研究也引出了一些新的問題，例如：不論使用擴增推理規則和合并推理規則，還是使用擴增推理規則和后件合并推理規則，都需要交替使用才能推導出所有的決策蘊涵，這樣勢必會增加推理的復雜度，因此是否存在更簡單有效的推理規則，即只需一條推理規則便足以完成該推理過程?是否可以將本文的工作推廣到可變決策蘊涵[31]和模糊決策蘊涵[20，32]上？這也是接下來需要進一步研究的問題。