不完備決策系統下的多特定類廣義決策約簡

唐玉凱，張楠，童向榮，張小峰

（1.煙臺大學 數據科學與智能技術山東省高校重點實驗室，山東 煙臺 264005; 2.煙臺大學 計算機與控制工程學院，山東 煙臺 264005; 3.魯東大學 信息與電氣工程學院，山東 煙臺 264025）

粗糙集理論[1-5]是于1982 年由波蘭科學家Pawlak 提出的一種用于分析和處理不確定或不精確數據的數學工具。目前，粗糙集理論正被廣泛應用于人工智能、機器學習、模式識別、數據挖掘等領域，并取得了豐碩的研究成果。屬性約簡[6-12]是粗糙集理論的核心研究內容之一。屬性約簡的本質是在保持原決策系統某種分辨能力不變的前提下，刪除冗余屬性，獲取最小屬性子集。

在決策系統中，若某個條件屬性值存在缺失，則稱該決策系統為不完備決策系統。目前，國內外相關學者針對不完備決策系統做了大量的研究工作。2002 年，Liang 等[13]提出了基于粗糙熵的不完備決策系統約簡算法。2010 年，周獻中等[14]介紹了在不完備決策系統下基于相容關系和相似關系的粗糙集模型及其拓展模型，通過引入相容矩陣和相似矩陣，系統研究了相應的粗計算、屬性約簡以及決策規則提取的矩陣算法。2010 年Qian 等[15]提出了基于極大相容塊的不協調不完備決策系統下的上下近似約簡概念并給出構造相應差別矩陣方法。2014 年，Shu 等[16]提出了不完備決策系統下基于候選屬性重要度的快速求屬性約簡方法。2015 年，Qian 等[17]提出了基于緊湊差別矩陣的動態不完備決策系統下的特征選擇方法。2018 年，Xie 等[18]提出了不完備決策系統下不協調度的概念，證明了基于不協調度與基于正域的屬性約簡等價。

在不完備決策系統中，具有相同條件屬性的對象可能決策出多個不同的決策值，每個對象所有可能決策出的決策值稱為該對象的廣義決策值，廣義決策約簡旨在保持約簡前后每個對象的廣義決策值不變。1993 年，Skowron[19]提出了廣義決策的概念。1998 年，Kryszkiewicz[20]討論了不完備決策系統下的廣義決策約簡問題，給出相關決策規則的提取方法，并提出了基于差別矩陣[21]的廣義決策約簡方法。上述研究考慮決策屬性的所有決策類，而在實際應用中，決策者往往只關注部分決策類。為此相關學者針對局部約簡即特定類約簡做了大量研究。尹繼亮等[22]討論了區間值系統下的局部屬性約簡。Qian 等[23]為解決經典粗糙集無法處理具有有限標記的大數據集的問題，引入了局部粗糙集的概念。Liu 等[24]提出了第l決策類下近似約簡概念并提出相應差別矩陣構造方法。

綜合上述研究，文獻[20]研究討論了不完備決策系統所有決策類的廣義決策約簡，文獻[22]只在區間值系統下對局部約簡進行了研究，文獻[24]在完備系統下對單特定類的正域約簡進行了研究。然而，基于多特定類的不完備決策系統下廣義決策約簡未見報道。為此，本文提出基于多特定類的不完備決策系統廣義決策約簡的理論框架，定義了單特定類的不完備決策系統廣義決策約簡的相關概念，提出并證明相關定理，構造相應差別矩陣和區分函數，并將單特定類推廣到多特定類，提出基于差別矩陣的多特定類不完備決策系統廣義決策約簡算法并通過實驗驗證了算法的有效性。

1 基本概念

為方便進一步研究基于多特定類的不完備決策系統廣義決策約簡，本節將給出不完備決策系統及廣義決策約簡的相關基本概念。

1.1 不完備決策系統及其上下近似

定義1[16]四元組 D S=(U,AT=C∪D,V,f) 為一個決策系統，其中U表示所有對象的非空有限集合，稱之為論域；C表示條件屬性的非空有限集合；D表示決策屬性的非空有限集合，C∩D=?；表示屬性a∈AT 的值域；f:U×AT →V是一個信息函數，它使得任意對象的任意一個屬性都有一個信息值，f(x,a) 表示對象x∈U在屬性a∈AT 上的取值。

定義2[16]四元組 D S=(U,AT=C∪D,V,f) 為一個決策系統，對任意非空屬性集B?AT 導出論域U上的不可區分關系 I ND(B) 定義為

不可區分關系是一個滿足自反性、對稱性和傳遞性的等價關系。由不可區分關系 IN D(B) 導出對論域U的劃分為U/IND(B)={[x]B|x∈U}，簡記為U/B，其中 [x]B表示包含x的等價類。

定義3[16]四元組 D S=(U,AT=C∪D,V,f) 為一個決策系統，若存在條件屬性c∈C使得Vc含有缺失值，則稱該決策系統為不完備決策系統，用 I DS=(U,AT=C∪D,V,f) 表示，Vc中的缺失值使用 *表示。

在不完備決策系統 I DS 中，決策屬性d∈D的值域Vd不含有缺失值。若決策屬性集D中決策屬性數目為1，則稱 I DS 為不完備單決策系統；若D中決策屬性數目大于1，則稱 I DS 為不完備多決策系統。為表述方便，本文只考慮不完備單決策 系 統 的 情 況 ， 即 IDS=(U,AT=C∪g0gggggg,V,f) 的情況。

定義4[20]四元組IDS=(U,AT=C∪g0gggggg,V,f)為一個不完備決策系統，對任意條件屬性集A?C，定義其相容關系為

其中f(x,a) 表示對象x∈U在屬性a∈A上的取值。

相容關系 S IM(A) 具有以下性質：

性質1[20]四元組IDS=(U,AT=C∪g0gggggg,V,f)為一個不完備決策系統，對 ?A?C，有：

性質2四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，對 ?A?C，S IM(A) 滿足：

1) 自反性，對 ?x∈U，有 (x,y)∈SIM(A)；

2) 對稱性，對 ?x,y∈U，若 (x,y)∈SIM(A)，則(y,x)∈SIM(A)；

3) 非傳遞性，對 ?x,y,z∈U，若(x,y)∈SIM(A)且 (y,z)∈SIM(A)，(x,z)∈SIM(A) 不一定成立。

設SA(x)={y∈U|(x,y)∈SIM(A)}，其中條件屬性集A?C，SA(x) 表示通過條件屬性集A與x可能不可區分的對象的最大集合。設DA(x)={y∈U|(x,y)?SIM(A)} ， 其 中 條 件 屬 性 集A?C，DA(x) 表示通過條件屬性集A與x可能可區分的對象的最大集合。對 ?x∈U，有SA(x)∩DA(x)=?且SA(x)∪DA(x)=U。

在 I DS 中，對 ?A?C，有U/SIM(A) 表示分類且U/SIM(A)={SA(x)|x∈U} 。U/SIM(A) 中的每 一個元素SA(x)(x∈U) 被稱為相容類，且滿足 ∪U/SIM(A)=U。

根據相容類，可得到對象集X?U有關于條件屬性集A?C的下近似集和上近似集。

定義5[20]四元組IDS=(U,AT=C∪g0gggggg,V,f)為一個不完備決策系統，對 ?X?U， ?A?C，X關于條件屬性集A的下近似集和上近似集分別定義為

例1不完備決策系統 IDS 如表1 所示，論域U={x1,x2,x3,x4,x5,x6}，C={a1,a2,a3,a4} 為條件屬性集 ，決策屬性集為 g0gggggg。

表1 不完備決策系統Table 1 An incomplete decision system

由定義4 得 I DS 在條件屬性集C上相容類集合

1.2 不完備決策系統廣義決策約簡

定義6[20]四元組IDS=(U,AT=C∪g0gggggg,V,f)為一個不完備決策系統，對 ?x∈U，關于條件屬性集A?C的廣義決策值定義為

在 I DS 中， ?A(x) 表示對象x關于條件屬性集A的所有可能決策值的集合。

屬性約簡旨在保證決策系統的某種分類能力不變的情況下，刪除冗余屬性，獲得最小屬性子集。給出不完備決策系統的廣義決策約簡定義如下。

定義7[20]四元組IDS=(U,AT=C∪g0gggggg,V,f)為一個不完備決策系統，若條件屬性集A?C為屬性集C的一個廣義決策約簡，當且僅當滿足以下兩個條件：

1)對 ?x∈U，有 ?A(x)=?C(x)；

2)對 ?A′?A， ?x′∈U，有 ?A′(x′)≠ ?A(x′)。

條件 1)保證了條件屬性聯合的充分性，即約簡前后決策系統廣義決策值的一致性；條件 2)保證了條件屬性個體的必要性，即缺少任意一個必要屬性，則無法保持決策系統的廣義決策值不變。

由廣義決策約簡定義可以構造相應的差別矩陣及區分函數，定義如下。

定義8[20]四元組IDS=(U,AT=C∪g0gggggg,V,f)為一個不完備決策系統，U={x1,x2,···,xn}， ?x,y∈U，IDS 廣義決策約簡的差別矩陣為n×n的矩陣，記為MGEN=(MGEN(x,y))n×n， 其中矩陣元素MGEN(x,y) 為

定義9[20]四元組IDS=(U,AT=C∪g0gggggg,V,f)為一個不完備決策系統，MGEN為 I DS 廣義決策約簡的差別矩陣，若MGEN(x,y)={a1,a2,···,ak}≠ ?，其中k表示MGEN(x,y) 中屬性的數量，用 ∨MGEN(x,y)表示布爾函數a1∨a2∨···∨ak，對 ?MGEN(x,y)≠ ?，IDS 廣義決策約簡的區分函數為

例2不完備決策系統 IDS 如表1 所示，論域U={x1,x2,x3,x4,x5,x6}，C={a1,a2,a3,a4} 為條件屬性集，決策屬性集為 g0gggggg。

由定義6 得 I DS 在條件屬性集C上廣義決策值 ?C(U)={?C(x1),?C(x2),?C(x3),?C(x4),?C(x5),?C(x6)}，其 中 ?C(x1)={1,2}， ?C(x2)={1,3}， ?C(x3)={1,2} ，?C(x4)={2}，?C(x5)={1,3}，?C(x6)={3} 。 I DS 中所有決策類的廣義決策約簡差別矩陣為

根據 I DS 所有決策類的廣義決策約簡的差別矩陣MGEN可得對應的區分函數為

因此, IDS 的所有決策類的廣義決策約簡為{a1,a3,a4}。

2 多特定類廣義決策約簡

在實際應用中，相較經典廣義決策約簡中關注全部決策類，決策者往往只關注決策屬性中的一種或者幾種決策類。因此，對于某些特定決策類的約簡可能更有意義。本節將討論不完備決策系統下多特定類的廣義決策約簡。

2.1 基于差別矩陣的單特定類的廣義決策約簡

定義10四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決 策 類 集 合 ， 對 ?Di∈U/g0gggggg,i=1,2,···,|U/g0gggggg|，?A?C，?x∈{z∈U|Di∩SC(z)≠ ?}， 若滿足 ?A(x)=?C(x)，則稱條件屬性集A為單特定類Di的廣義決策協調集。

定義11四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決 策類 集 合 ， 對 ?Di∈U/g0gggggg，i=1,2,···,|U/g0gggggg|， 若?A?C為單特定類Di的廣義決策約簡當且僅當滿足以下兩個條件：

2) ?A′?A， ?x′∈{z∈U|Di∩SC(z)≠ ?} ， 使 得 ?A′(x′)≠ ?C(x′)。

定理1四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決策類集合，對 ?Di∈U/g0gggggg，i=1,2,···,|U/g0gggggg|，條件屬性集A?C為單特定類Di的廣義決策協調集當且僅當Di∩SC(x)≠ ? 且f(y,d)? ?C(x) 時，有(x,y)?SIM(A)。

證明：

充分性：因條件屬性集A是 I DS 單特定類Di的廣義決策協調集，對 ?x∈{z∈U|Di∩SC(z)≠ ?}，有 ?A(x)=?C(x) 。當Di∩SC(x)≠ ? 且f(y,d)? ?C(x)，即f(y,d)? ?A(x)， 即 (x,y)?SIM(A)。

必要性：當Di∩SC(x)≠ ? 且f(y,d)? ?C(x) 時，有 (x,y)?SIM(A)， 所以有f(y,d)? ?A(x) 成立。當滿足Di∩SC(x)≠ ? 且f(y,d)? ?C(x) 時，必有f(y,d)??A(x) ， 即 ?C(x)? ?A(x) ， 又 因 為A?C， ?A(x)? ?C(x)，所以當 ?x∈{z∈U|Di∩SC(z)≠ ?} 時，有 ?A(x)=?C(x)。因此條件屬性集A?C為單特定類Di∈U/g0gggggg 的廣義決策協調集。證畢。

定義12四組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決策類集合，U={x1,x2,···,xn}， ?x,y∈U,I DS 單特定類Di∈U/g0gggggg 廣義決策約簡的差別矩陣為n×n的矩陣，記為Mi=(Mi(x,y))n×n，其中矩陣元素Mi(x,y) 為

Πi={(x,y)|x,y∈U,Di∩SC(x)≠ ?∧f(y,d)??C(x)}

i=1,2,···,|U/g0gggggg|

其中， ，。IDS=(U,AT=C∪g0gggggg,V,f)U/g0gggggg={D1,D2,···,D|U/g0gggggg|}U={x1,x2,···,xn} ?Di∈U/g0ggggggi=1,2,···,|U/g0gggggg|A?CDi?(x,y)∈Πi A∩Mi(x,y)≠?

定理2四元組 為一個不完備決策系統， 為決策類集合，論域 ，對 ，

，條件屬性集 是單特定類的廣義決策協調集當且僅當 時，有。

證明：

充分性：設條件屬性集A是單特定類Di的廣義決策協調集，對于 ?(x,y)∈ Πi，若Di∩SC(x)≠ ?且f(y,d)? ?C(x) ，則有 (x,y)?SIM(A)，所以一定存在a∈A使 得 (x,y)?SIM({a}) ， 故a∈Mi(x,y)， 所 以A∩Mi(x,y)≠?。

必要性：設 ? (x,y)∈ Πi， 使得A∩Mi(x,y)=?，則有 (x,y)∈SIM(A) 成 立 ， 又 因 為 對 ?x∈U， 當Di∩SC(x)≠ ? 且f(y,d)? ?C(x) 時，必有 (x,y)?SIM(A)，這與 (x,y)∈SIM(A) 矛盾。證畢。

定義13四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決策類集合，對 ?Di∈U/g0gggggg，i=1,2,···,|U/g0gggggg|，Mi為 I DS 單特定類Di的廣義決策約簡的差 別 矩陣，若Mi(x,y)={a1,a2,···,ak}≠ ?， 其中k表示Mi(x,y) 中屬性的數量，用 ∨Mi(x,y) 表 示布爾函數a1∨a2∨ · · · ∨ak，對 ?Mi(x,y)≠ ?， IDS 單特定類Di的廣義決策約簡的區分函數為

定理3四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決策類集合，對 ?Di∈U/g0gggggg，i=1,2,···,|U/g0gggggg|，IDS單特定類Di的廣義決策約簡區分函數DF(Mi)=∧(∨Mi(x,y)) 的極小析取范式為表示 D F′(Mi) 中的析取項數目，qk表示 D F′(Mi) 中第k個析取項中屬性數目。記Ak={as|s=1,2,···,qk}，則 {Ak|k=1,2,···,t} 是單特定類Di∈U/g0gggggg 的所有廣義決策約簡形成的集合。

證明：

對 ?k≤t， ? (x,y)∈ Πi，由極小析取范式定義可知Ak∩Mi(x,y)≠ ? ，由定理2 可知Ak是廣義決策協調集。若在Ak中刪除一個元素形成則故不是廣義決策約簡，因此Ak是廣義決策約簡。因為區分函數中包含所有Mi(x,y)，故不存在其余廣義決策約簡。證畢。

2.2 基于差別矩陣的多特定類的廣義決策約簡

根據以上討論，將單特定類的不完備決策系統廣義決策約簡擴展得到多特定類的不完備決策系統廣義決策約簡。給出多特定類的廣義決策約簡相關定義如下。

定義14四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統為決策類集合，則多特定類Dmcs定義為

由多特定類的定義可知，多特定類Dmcs至少含有一個單特定類至多含有 |U/g0gggggg| 個互不相同的單特定類。

定義15四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決 策 類 集 合 ， 對 ?Dmcs?U/g0gggggg ， ?A?C，?x∈{z∈U|∪Dmcs∩SC(z)≠ ?} ，若 ?A(x)=?C(x)，則稱條件屬性集A為多特定類Dmcs的廣義決策協調集。

定義16四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決策類集合，對 ?Dmcs?U/g0gggggg ，條件屬性集A?C為多特定類Dmcs的廣義決策約簡當且僅當滿足以下兩個條件：

1) 對 ?x∈{z∈U|∪Dmcs∩SC(z)≠ ?}， 都有 ?A(x)=?C(x)；

2) ?A′?A， ?x′∈{z∈U|∪Dmcs∩SC(z)≠ ?}，使得

由定義16 可知，當 |Dmcs|=1 時， IDS 多特定類的廣義決策約簡將退化為單特定類的廣義決策約簡；當 |Dmcs|=|U/g0gggggg| 時 ， IDS 多特定類的廣義決策約簡將退化為全決策類的廣義決策約簡。

定理4四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決策類集合，條件屬性集A?C為多特定類Dmcs?U/g0gggggg 的廣義決策協調集當且僅當 ∪Dmcs∩SC(x)≠ ? 且f(y,d)? ?C(x) 時，有 (x,y)?SIM(A)。

證明：

充分性：因屬性集A是 I DS 多特定類Dmcs的廣義決策協調集，對 ?x∈{z∈U|∪Dmcs∩SC(z)≠?}有 ?A(x)=?C(x) 。 ∪Dmcs∩SC(x)≠ ? 且f(y,d)? ?C(x)時，必有f(y,d)? ?A(x) 成立，所以 (x,y)?SIM(A)。

必要性：當 ∪Dmcs∩SC(x)≠ ? 且f(y,d)? ?C(x)時，有 (x,y)?SIM(A) ，所以f(y,d)? ?A(x) 成立。因為 當 ∪Dmcs∩SC(x)≠ ? 且f(y,d)? ?C(x) 時 ， 必 有f(y,d)??A(x) 成立 ， 即 ?C(x)??A(x)。 又 因 為當A?C時，必有 ?A(x)? ?C(x) 成立，所以對 ?x∈{z∈U|∪Dmcs∩SC(z)≠ ?} ，有 ?A(x)=?C(x)。因此條件屬性集A?C為多特定類Dmcs?U/g0gggggg 的廣義決策協調集。證畢。

定義17四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決策類集合，U={x1,x2,···,xn} ， ?x,y∈U,I D S 多特定類Dmcs?U/g0gggggg 廣義決策約簡的差別矩陣為n×n的矩陣，記為Mmcs=(Mmcs(x,y))n×n，其中矩陣元素Mmcs(x,y) 為

其中，Πmcs={(x,y)|x,y∈U,∪Dmcs∩SC(x)≠?∧f(y,d)??C(x)}。

定理5四元組 IDS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決策類集合，對多特定類Dmcs?U/g0gggggg，條件屬性集A?C是多特定類Dmcs的廣義決策協調集當且僅當 ? (x,y)∈ Πmcs時，有A∩Mmcs(x,y)≠ ?。

證明：

充分性：設條件屬性集A是多特定類Dmcs的廣 義 決 策 協 調 集 ， 對 ?(x,y)∈Πmcs， 當 ∪Dmcs∩SC(x)≠ ? 且f(y,d)? ?C(x) 時，則有 (x,y)?SIM(A)，所 以 一定存 在a∈A使 得 (x,y)?SIM({a})， 故a∈Mmcs(x,y) ，所以A∩Mmcs(x,y)≠ ? 。

必要性：設 ? (x,y)∈ Πmcs， 使A∩Mmcs(x,y)=? 成立，則有 (x,y)∈SIM(A) ， 又因對 ?x∈U，當f(y,d)??C(x) 且 ∪Dmcs∩SC(x)≠ ? 時 ， 必 有 (x,y)?SIM(A)，這與 (x,y)∈SIM(A) 矛盾。證畢。

定義18四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，Dmcs?U/g0gggggg 為多特定類，Mmcs為 I DS 多特定類Dmcs的廣義決策約簡的差別矩陣，若Mmcs(x,y)={a1,a2,···,ak}≠ ? ，其中k表示Mmcs(x,y) 中屬性的數量，用 ∨Mmcs(x,y) 表示布爾函數a1∨a2∨ ···∨ak，對 ?Mmcs(x,y)≠ ?， I DS 多特定類Dmcs的廣義決策約簡的區分函數為

定理6四元組 I DS=(U,AT=C∪g0gggggg,V,f) 為一個不完備決策系統，U/g0gggggg={D1,D2,···,D|U/g0gggggg|} 為決策類集合，多特定類Dmcs?U/g0gggggg 的廣義決策約簡區分函數 DF(Mmcs)=∧(∨Mmcs(x,y)) 的極小析取范式為 DF′(Mmcs)=k∨=t

1(s∧q=k1as)，t表示 D F′(Mmcs) 中 的析取項數目，qk表示 D F′(Mmcs) 中第k個析取項中屬性數目。設Ak={as|s=1,2,···,qk}，{Ak|k=1,2,···,t}是多特定類Dmcs?U/g0gggggg 的所有廣義決策約簡形成的集合。

證明：

對 ?k≤t， ? (x,y)∈ Πmcs，由極小析取范式定義可知Ak∩Mmcs(x,y)≠ ?， 由定理5 可知Ak是 I DS 多特定類的廣義決策協調集。若在Ak中刪除一個元素得使，故不是廣義決策約簡，因此Ak是廣義決策約簡。因為區分函數中包含所有Mmcs(x,y)，故不存在其余廣義決策約簡。證畢。

根據不完備決策系統單特定類以及多特定類廣義決策約簡的相關定義，可依據相應的差別矩陣以及區分函數進行廣義決策約簡的求解，現給出實例如下。

例3不完備決策系統 I DS 如表1 所示，論域為條件屬性集，決策屬性集為 g0gggggg。

由例1 易得，IDS在屬性集C上的相容類集合U/SIM(C)={{x1,x3},{x2,x5},{x1,x3},{x4},{x2,x5,x6}，{x5,x6}} 。決策屬性d對論域U劃分決策類為U/g0gggggg={{x1,x2},{x3,x4},{x5,x6}}。 廣義決策值為 ?C(U)={?C(x1),?C(x2),?C(x3),?C(x4),?C(x5),?C(x6)}， 其中 ?C(x1)={1,2}，?C(x2)={1,3}，?C(x3)={1,2}，?C(x4)={2}，?C(x5)=

對于單特定類D1={x1,x2}，依據定義12 構造IDS 單特定 類D1的差 別矩陣為

根 據 IDS 單 特 定 類D1的 廣 義 決 策 約 簡 的 差別矩陣M1可得對應的區分函數為

因此 I DS 的單特定類D1的廣義決策約簡為 {a3}。

對多特定類Dmcs={D1,D2}={{x1,x2},{x3,x4}}，依據定義17 構造 I DS 多特定類Dmcs的差別矩陣為

根據 I DS 多特定類Dmcs的廣義決策約簡的差別矩陣Mmcs可得對應的區分函數為

因此 I DS 的多特定類Dmcs的廣義決策約簡為{a3,a4}。

因單特定類廣義決策約簡為多特定類廣義約簡的特例，所以僅給出多特定類的不完備決策系統廣義決策約簡算法如下。

算法1基于差別矩陣的多特定類不完備決策系統廣義決策約簡(multi-class-specific generalized decision preservation reduction based on discernibility matrix in incomplete decision systems, MGDRDM)

輸入一個不完備決策系統IDS=(U,AT=C∪g0gggggg,V,f) ，多特定類Dmcs。

輸出多特定類Dmcs的不完備決策系統廣義決策約簡。

1) 依據條件屬性集C計算論域U中每個對象的相容類SC(xi)(xi∈U)， 根據決策屬性d計算決策類集合U/g0gggggg；

2) 依據相容類SC(xi) 計算每個對象的廣義決策值 ?C(xi)；

3) 依據決策系統中每個對象的廣義決策值?C(xi) 和多特定類Dmcs構造相應差別矩陣Mmcs；

4) 依據差別矩陣Mmcs構造相應多特定類的廣義決策約簡區分函數DF(Mmcs)；

5) 利用吸收律和分配律將多特定類區分函數 D F(Mmcs) 轉變為極小析取范式 D F′(Mmcs)；

6) 依據極小析取范式 D F′(Mmcs) 輸出多特定類Dmcs的廣義決策約簡，算法結束。

算法1 中，步驟1) 的時間復雜度為O(|C||U|2)，步驟2) 的時間復雜度為O(|U|2)，步驟3) 、步驟4)的時間復雜度為O(|C||U|2)，步驟5) 的過程是一個NP-hard 問題，該步驟的時間復雜度為O(|C||U|2)，因此算法1 的整體時間復雜度為O(|C||U|2)。

3 實驗結果與分析

針對本文提出的多特定類不完備決策系統廣義決策約簡算法進行實驗驗證與分析。本節實驗選擇與經典不完備決策系統廣義決策約簡針對約簡結果、占用空間以及約簡效率進行比較。

本節采用6 組標準UCI 數據集進行實驗，數據集從http://archive.ics.uci.edu/ml/datasets.php 處下載。數據集使用WEKA3.6 進行等頻率離散化預處理，因某些原始數據中存在缺失數據數量極少，無法直接作為實驗使用，所以針對缺失數據使用相應屬性下出現頻率最高屬性值作為替換，針對名詞性數據使用整數作為替換。數據集詳細信息如表2 所示。表2 中，ID 表示數據集編號，“數據集”表示數據集名稱， |U|表示數據集中對象數目， |C| 表示數據集中條件屬性數目， |U/g0gggggg| 表示數據集中決策類數目。本節實驗環境：操作系統Windows7-64 bit；CPU Intel Core i5-6500(3.2 GHz)；內存4 GB；運行環境Python 3.6；開發工具Py Charm。

表2 數據集Table 2 Data Sets

因本節采用UCI 標準數據集，預處理之后數據集所表示的決策系統為完備決策系統，所以需要將其轉為不完備決策系統。采用文獻[16]中的方法對完備決策系統進行處理，具體處理方式為：除決策屬性之外，每個條件屬性對應列選取10%的屬性值進行缺失處理，缺失值使用*表示。

3.1 約簡結果對比

兩種約簡算法所得平均約簡長度對比如表3所示。表3 中，“全決策類”表示經典全決策類約簡算法所得約簡結果，“單特定類”表示MGDRDM 算法選定一個特定類時所得約簡結果，“多特定類”表示MGDRDM 算法選定多個特定類時所得約簡結果，“決策值”表示對應算法選取的一個或多個特定類所表現決策值，“平均約簡長度”表示對應算法所得約簡的平均約簡長度。

由表3 可知，相比全部決策類，當選定特定類數量較少時，平均約簡長度往往會比全決策類所得平均約簡長度要短。若多特定類選擇為所有決策類，則算法將退化為全決策類約簡，平均約簡長度不會縮短。

表3 平均約簡長度Table 3 Average reduct length

3.2 占用空間對比

本節通過比較兩種算法生成的差別矩陣中非空屬性集占比進而比較兩種算法占用空間大小。兩種算法生成差別矩陣中非空屬性集占比如表4所示，其中“占比(%)”表示對應不同算法構造差別矩陣中非空屬性集所占比例。

由表4 可知，當選定一個或者幾個特定類，特定類數量相對全部決策類數量較少時，MGDRDM 算法所構造差別矩陣中非空屬性集占比要小于經典算法構造差別矩陣中的非空屬性集占比。因此，在保證約簡目標不變的前提下，MGDRDM 算法所構造差別矩陣占用空間要小于經典算法構造差別矩陣占用空間。除此之外，利用差別矩陣中非空屬性集構造區分函數以及求取極小析取范式時，MGDRDM 算法也將占用更小空間。當選定特定類為全部決策類時，MGDRDM算法將退化為全決策類約簡，占用空間不會減小。

表4 差別矩陣非空屬性集占比Table 4 The proportion of non-empty attribute sets in the discernibility matrix

3.3 約簡效率對比

本節將6 組數據集，依據隨屬性數目遞增的時間消耗進行經典不完備決策系統廣義決策約簡與MGDRDM 算法之間約簡效率對比。約簡效率如圖1 所示，其中“全決策類”表示經典全類不完備決策系統廣義決策約簡算法隨屬性數目增加的約簡耗時變化曲線，“單特定類”和“多特定類”則表示MGDRDM 算法分別選定一個和多個特定類隨屬性數目增加的約簡耗時變化曲線，“決策值”表示選定特定類所表現的決策值。

由圖1 可知，選取特定類數量相對全部決策類數量較少時，約簡效率相較對比算法會有明顯的提升，這是由于多特定類廣義決策約簡的差別矩陣中非空屬性集的數目小于全決策類廣義決策約簡的差別矩陣中非空屬性集的數目，所以MGDRDM 算法在構造差別矩陣時耗時會有所減少。另外，因多特定類廣義決策約簡的差別矩陣中非空屬性集數目偏少，所以構造區分函數以及求取極小析取范式耗時相對較少，因此約簡效率更高。除此之外，隨著屬性數目的增加，算法之間耗時差距越發明顯，這是由于隨著屬性數目的增加，差別矩陣也愈加復雜，使得構造區分函數以及計算極小析取范式時計算量增大，而且MGDRDM 算法構造差別矩陣中非空屬性集數目較少，所以耗時增長緩慢，兩個算法之間耗時差距越明顯。當多特定類選擇為所有決策類時，算法退化為全類約簡，此時約簡效率并無明顯提升。

某些情況下，添加屬性求解約簡反而會使耗時減少，這可能是因為在添加屬性之后構造差別矩陣的過程中產生了較添加屬性之前更短的非空屬性集，這使得構造區分函數以及求取極小析取范式的過程耗時減少，所以在某些情況添加屬性反而求解更快。

圖1 約簡效率Fig.1 Reduction efficiency

4 結束語

屬性約簡作為數據分析預處理的重要手段之一，能夠提取更加泛化的規則，壓縮數據規模，使得數據分析更加準確、高效，具有重要意義。

本文提出了基于多特定類的不完備決策系統廣義決策約簡基本理論框架，定義了多特定類的不完備決策系統廣義決策約簡基本定義，并構造相應差別矩陣以及區分函數，提出基于差別矩陣的約簡算法并通過6 組UCI 數據集驗證了算法的有效性。本文提出約簡算法是基于差別矩陣求取所有約簡，為提升算法效率，差別矩陣優化是將來研究的重要問題。