粒協調決策形式背景的屬性約簡與規則融合

張曉鶴，米據生，李美爭

（1.河北師范大學 數學與信息科學學院，河北 石家莊 050024; 2.河北師范大學 計算機與網絡空間安全學院，河北 石家莊 050024）

形式概念分析(FCA)[1]于1982 年由Wille 教授提出，它是在形式背景中進行數據分析與規則提取的一個重要工具，通過分析形式背景中概念的結構提出了概念格，從本質上對對象和屬性的內在聯系進行了描述。Ganter[2]在其專著中進一步總結了概念格相關知識。目前該理論已在信息檢索[3]、數據挖掘[4-5]，軟件工程[6]等多個領域取得了廣泛應用。

屬性約簡與規則提取是粗糙集理論中關鍵的研究方向，同樣也是FCA 中的重要問題。一個決策形式背景生成的全部形式概念，包括概念之間的關系都會儲存在概念格中，這使得概念格的分析過程變得極為困難。因此，決策形式背景研究的重要課題之一就是保持決策不變進行屬性約簡，從而使形式背景中的隱藏知識更容易被發掘，即更易獲取決策規則。越來越多的學者開始深入研究決策形式背景的屬性約簡與規則提取問題。

2009 年，Wu[6]研究了保持概念格的粒結構不變的屬性約簡與規則提取，并給出具體算法。Li 等[7-9]提出了一種新的決策形式背景知識約簡框架，給出約簡算法，且在決策形式背景研究了保持決策規則不變的屬性約簡。Li 等[10]研究了基于同余關系的不協調決策形式背景的屬性約簡。Li 等[11]提出了基于最大規則的決策形式背景中的新型屬性約簡。Chen[12-13]提出了一種大數據模型下的快速屬性約簡模型，并結合實例分析其算法復雜度。Yang[14]基于蘊涵映射對實數集決策形式背景中的屬性約簡和規則提取問題進行研究。Qi[15]從多角度討論了兩類三支概念格與傳統概念格之間的聯系, 并給出了在經典概念格基礎上構造三支概念格的算法。 Zhang 等[16]利用概念格提出了一種基于案例的層次化分類器。Zhang 等[17]研究了模糊決策格值信息系統上的近似約簡與規則提取。張[18-19]敘述了信息系統上的知識發現與知識約簡, 提出了協調近似表示空間上的規則融合方法。

目前在概念格領域已取得諸多成果，但仍存在眾多問題有待解決。比如基于等價關系的粒協調決策形式背景的屬性約簡問題，利用確定性規則獲取全部規則的具體途徑，本文將進一步討論這些問題。

1 預備知識

定義1[6]設三元組F=(U,A,I) 是形式背景，U={x1,x2,···,xn}，A={a1,a2,···,am}，I?U×A。如果(x,a)∈I， 則稱x具有屬性a。 用P(U) 表示U的冪集，P(A) 表示A的冪集。 ?X∈P(U)，B∈P(A)，定義：

定義2[6]對于形式背景F=(U,A,I)，若二元組 (X,B)∈P(U)×P(A) 滿足X?=B且B?=X，則(X,B) 稱為形式概念或概念。其中X是概念(X,B)的外延，B是概念 (X,B) 的內涵。

定義3[6]對于形式背景F=(U,A,I) ，C?A，可以得到形式背景FC=(U,C,IC)，FC稱為F的子背景，其中IC=I∩(U×C)。

則對X?U，定義映射?C:P(U)→P(C):X?C={a∈C:?x∈X,(x,a)∈I}。 特別地，當X={x}，C={a}時有

定義4[19]設Vl(l≤m) 是非空有限集，記

稱P為集合向量空間。對于P中的兩個集合向量E=(E1,···,Em)，S=(S1,···,Sm) ，如果 ?l≤m，均有El≤Sl，則記E≤S，且 (P,≤) 為偏序集。

定義5[19]設 (P,≤) 為偏序集，稱D:P2→[0,1]為集值向量包含度，滿足下列條件：

1) 0 ≤D(S/E)≤1；

2)E≤S時，D(S/E)=1；

3)E≤S≤G時，D(E/G)≤D(E/S)。

2 基于等價關系的粒協調決策形式背景的屬性約簡

以往對決策形式背景進行討論時通常會分別構造條件概念格與決策概念格，利用兩者的序關系來定義形式背景的協調性。本節利用等價關系對對象集進行劃分，從而得到對應的決策類，可以在保持對象的決策不變的前提下刪除冗余屬性。

設F=(U,A,I,D,G) 為一個決策形式背景，A為條件屬性集，D為決策屬性集，并且A∩D=?，I?U×A。 定義RD={(x,y)∈U×U:dl(x)=dl(y)(?dl∈D)} ，則由上述等價關系可產生U上的一個劃分：

其中

如果 ?x∈U， 均滿足x?A??[x]D，則稱決策形式背景F是粒協調的。

定義6設F=(U,A,I,D,G) 為粒協調決策形式背景，對B?A， 如果 ?x∈U，都有x?B??[x]D，則稱B是F的一個粒協調集。進一步，如果不存在C?B，使得 ?x∈U都有x?C??[x]D， 則B是F的粒約簡。

注：1)對粒協調決策形式背景F來說，必存在粒約簡。如用 {Bi:i≤l} 表示F所有的粒約簡，則為F的核心，B中的元素稱為核心元素或絕對必要屬性。

2) 對 于x，y∈Dj， ?dl∈D有dl(x)=dl(y)， 顯 然決策類中所有對象決策值相同，記為dl(Dj)。 稱Tj={d1(Dj),d2(Dj),···,d|D|(Dj)} 為決策類Dj的決策值。

設F=(U,A,I,D,G) 是一個粒協調決策形式背景，B?A，記

則容易證明：

定義7設F=(U,A,I,D,G) 是一個粒協調決策形式背景，x,y∈U，x與y的辨識屬性集定義如下：

由定義7 可知，以下性質顯然成立：

定理1設F=(U,A,I,D,G) 是一個粒協調決策形式背景，B?A。 則 ∩B是F的粒協調集，當且僅當Dd(x,y)≠ ? 時有BDd(x,y)≠ ?。

證明(?) 當Dd(x,y)≠ ? 時，由定義7 可知，?dl∈D均滿足dl(x)≠dl(y) ，即 (x,y)?RD。而B是F的粒協調集，則有RB?RD。因此 (x,y)?RB，故必存在b∈B使得x??y?。 所以b∈Dd(x,y)。因而

(?) 若Dd(x,∩y)≠ ? ， 則 ?dl∈D，dl(x)≠dl(y)， 即(x,y)?RD。故BDd(x,y)≠ ? ，一定存在b∈B, 使得b∈Dd(x,y)， 則有x??y?，從而 (x,y)?R。當

B(x,y)?RD時 (x,y)?RB， 故RB?RD。 綜 上 ，B是F的粒協調集。

定理2設F=(U,A,I,D,G) 是一個粒協調決策形式背景，a∈A， 則a是F的核心屬性，等價于存在x，y∈U使得Dd(x,y)={a}。

證明(?) 如 果條件屬性a∈A是F的核心屬性，則A-{a} 不可能是F的粒約簡，即RA-{a}?RD。故存在x，y∈U，使得 (x,y)?RD時有 (x,y)∈RA-{a}。此時dl(x)≠dl(y) 。 又易證x?{a}?y?{a}，由定義7 可知a∈Dd(x,y) ， 即 ?x,y∈U使 得Dd(x,y)={a}(事 實 上 ，如x?{a}?y?{a}， 則 由 (x,y)∈RA-{a}可 知 (x,y)∈RA。又F是一個粒協調決策形式背景，所以RA?RD，即 ?dl∈D均滿足dl(x)=dl(y) ，這與dl(x)≠dl(y) 矛盾，所以x?{a}?y?{a})。

(?) 如果Dd(x,y)={a} ，定義7 可知dl(x)≠dl(y)x?{a}?y?{a}并且任取b∈A-a, 必有x??y?。因此(x,y)?RD且 (x,y)∈RA-{a}。故可得RA-{a}?RD，即A-{a} 不是F的粒約簡，a是F的核心屬性。

定義8 設F=(U,A,I,D,G) 是一個粒協調決策形式背景，x,y∈U，Dd(x,y)≠?。記

稱為F的極小析取范式。Bk(k≤p) 是F的所有粒約簡的集合，具體算法如下：

算法 1粒協調決策形式背景的屬性約簡算法

輸入粒協調決策形式背景F=(U，A，I，D，G)

輸出B(粒約簡集)

例1表1 給出了一個決策形式背景，其中對象集U={x1,x2,x3,x4,x5,x6,x7}，D=g0gggggg 為決策 屬性集。為條件屬性集。

表1 決策形式背景F=(U,A,I,D,G)Table 1 A formal decision context：F=(U,A,I,D,G)

計算可知：

可知F為粒協調的，其辨識矩陣如表2 所示。由布爾方法可獲取F的所有粒約簡，具體過程如下：

故該形式背景存在兩個粒約簡，即B1= {a1,a3,a4,a6,a8} 與B2={a1,a4,a5,a6,a8}，F的核心屬性為a1,a4,a6與a8。

表2 F =(U,A,I,D,G) 的辨識矩陣Table 2 The discernibility matrix ofF=(U,A,I,D,G)

3 基于等價關系的粒協調決策形式背景上的規則融合

本節給出粒協調決策形式背景中決策規則及最優決策規則的定義，進一步討論粒協調決策形式背景上規則融合算法，并給出相關實例。

定義9設F=(U,A,I,D,G) 是一個粒協調決策形式背景，稱 (X,Y∈L(U,A,I) 為條件概念。決策類Dj與 其 決策值Tj構 成的二元 組 (Dj,Tj) 稱為決策概念。如果X≠ ? ，Y≠ ? ，并且有X?Dj，則稱 (X,Y)?(Dj,Tj) 為決策形式背景的粒決策規則。所有粒決策規則的集合記為 ? (F)。

對于粒協調決策形式背景來說，必有xi?A??[xi]D。于是可得到 |U| 條確定性規則。顯然還存在一些不確定性規則，下文給出用 |U| 條確定性規則得到全部規則的兩種規則融合方法。

設F=(U,A,I,D,G) 是一個粒協調決策形式背景， ?x∈U，al∈A，定義

定義10設 (P,≤) 是偏序集，對于P中的兩個集合向量E和S，定義包含度為

3.1 樂觀規則融合

1)由RD對U進行劃分，得到

2)對于決策類Dj(j≤r)，記

3)將Mj中的向量取并運算，即每個分量取并運算，得到

計算D(Sj/E)， 若則有：

算法 2粒協調決策形式背景中樂觀規則融合算法

例2接例1,F=(U,A,I,D,G) 中的所有條件概念計算如下：

為使討論更具實際意義，在下列討論中我們忽略 (U,?)、( ?,A)。

計算可知：

則所有決策概念計算如下：

記

則有

故

對于條件概念 ( {x1,x2,x3,x4},{a6}) 來說，有E=({0},{0},{0},{0},{0},{1},{0},{0})。

計算可知：

綜上可得規則“ {a6}?d=3(0.92)”，此處0.92為該方法中此條規則的可信度。由上述方式可獲取規則：

由定義9 可知，粒決策規則如下：

顯然粒決策規則在樂觀規則融合方法中同樣為確定性規則。

3.2 悲觀規則融合

1)由RD對U進行劃分，得到

2)對于決策類Dj(j≤r)，記

3)將Mj中的向量取最大值，即每個分量取最大值，得到

4)對于概念 (X,B)∈L(U,A,I)，記

計算D(Lj/E)， 若則有：

粒決策規則在該方法中可信度并不一定為1，且兩種規則融合方式獲取的規則并不一致。下面給出具體算法。

算法 3粒協調決策形式背景中悲觀規則融合算法

例3 通過悲觀融合方法同樣可以獲取F中的全部規則。

首先計算可知：

可得規則 “ {a6}?d=1(0.625)”，此處0.625 為該方法中此條規則的可信度。由該方式可規則如下：

4 結束語

形式概念分析中至關重要的兩個研究問題就是屬性約簡問題與規則提取問題，而這兩方面的研究都是為了更準確便捷地獲取決策。本文用對象集與決策屬性集之間的等價關系代替要求更為嚴格的伽羅瓦連接，使決策形式背景的模型更易獲取決策。

本文利用集值向量包含度給出兩種規則融合方法，獲取了決策形式背景的全部規則，其中包括確定性規則與大量不確定性規則。在現實生活，這些不確定性規則可能具有重要意義，如何在部分不確定性規則不變的前提下進行屬性約簡，將是未來研究的重要方向。