基于多特定決策類的不完備決策系統正域約簡

孔賀慶 張楠 岳曉冬 童向榮 于天佑

摘 要：現有的屬性約簡方法大部分關注決策系統中的所有決策類，而在實際決策過程中決策者往往僅關注決策系統中的一種或幾種決策類。針對上述問題，提出基于多特定決策類的不完備決策系統正域約簡的理論框架。首先，給出不完備決策系統單特定決策類正域約簡的概念;第二，將單特定決策類正域約簡推廣到多特定決策類，構造了相應的差別矩陣及區分函數;第三，分析并證明了相關定理，提出基于差別矩陣的不完備決策系統多特定決策類正域約簡算法（PRMDM）;最后，選取4組UCI數據集進行實驗。在數據集Teachingassistantevaluation、House、Connectionistbench和Cardiotocography上，基于差別矩陣的不完備決策系正域約簡算法（PRDM）的平均約簡長度分別為4.00、13.00、9.00和20.00，PRMDM算法（多特定決策類中決策類數目為2）的平均約簡長度分別為3.00、8.00、8.00和18.00。實驗結果驗證了PRMDM算法的有效性。

關鍵詞：粗糙集;不完備決策系統;多特定決策類;正域約簡;差別矩陣

中圖分類號：TP181

文獻標志碼：A

英文標題

Abstract： The existing attribute reduction algorithms mostly focus on all decision classes in decision systems， but in actual decision process， decision makers may only focus on one or several decision classes in the decision systems. To solve this problem， a theoretical framework of positive region preservation reduction based on multispecific decision classes in incomplete decision systems was proposed. Firstly， the positive region preservation reduction for single specific decision class in incomplete decision systems was defined. Secondly， the positive region preservation reduction for single specific decision class was extended to multispecific decision classes， and the corresponding discernibility matrix and function were constructed. Thirdly， with related theorems analyzed and proved， an algorithm of Positive region preservation Reduction for Multispecific decision classes reduction based on Discernibility Matrix in incomplete decision systems （PRMDM） was proposed. Finally， four UCI datasets were selected for experiments. On Teachingassistantevaluation， House， Connectionistbench and Cardiotocography dataset， the average reduction length of Positive region preservation Reduction based on Discernibility Matrix in incomplete decision systems （PRDM） algorithm is 4.00， 13.00， 9.00 and 20.00 respectively while that of the PRMDM algorithm （with decision classes in the multispecific decision classes is 2） is 3.00， 8.00， 8.00 and 18.00 respectively. The validity of PRMDM algorithm is verified by experimental results.

英文關鍵詞Key words： rough set; incomplete decision system; multispecific decision classes; positive region preservation reduction; discernibility matrix

0 引言

1982年由波蘭科學家Pawlak提出的粗糙集理論[1-6]是一種重要的知識推理工具，作為一種求取集合近似的方法，該理論現已應用于機器學習、數據挖掘、模式識別、智能信息處理等領域。屬性約簡[7-13]是粗糙集理論的重要研究內容之一，屬性約簡通過刪除冗余屬性得到保持原決策系統某種分類信息不變的最小屬性子集。

在決策系統中，若決策系統中條件屬性值存在缺失，則稱該決策系統為不完備決策系統。在現實生活中，存在一定數量的不完備信息。目前，相關學者對不完備決策系統下的屬性約簡進行了大量的研究，并將經典Pawlak粗糙集模型進行推廣，取得了一系列成果： 1998年，Kryszkiewicz[14]在不完備決策系統下引入廣義決策保持約簡，介紹了相關決策規則的提取，并提出了基于差別矩陣[15]的廣義決策保持約簡方法; 2002年，Liang等[16]基于粗糙熵提出不完備決策系統的知識約簡的啟發式算法。2003年，周獻中等[17]100-104在不完備決策系統下提出分配約簡; 2005年，黃兵等[17]52-56提出不完備決策系統的上下近似約簡，并給出求解所有決策類約簡的差別矩陣方法; 2010年，Qian等[18]基于極大相容塊在不協調不完備決策系統下提出上下近似約簡的概念，并構造了相應的差別矩陣;2014年，Shu等[19]在不完備決策系統下提出通過評估候選屬性重要度快速求取屬性約簡的方法;2015年，Qian等[20]提出動態不完備決策系統下基于緊湊差別矩陣的特征選擇方法。

在屬性約簡中，正域約簡針對所有決策屬性的決策類，約簡結果保證了整個決策系統約簡前后正域不變。在實際應用中，決策者往往僅關注于決策系統中的一種或幾種決策類。例如，在醫療診斷中，多種癥狀構成條件屬性集，不同類型的疾病構成不同的決策值，醫生通常建議根據不同類型的疾病尋找不同的發病原因。2005年，Chen等[21]提出決策系統中局部約簡的概念，與定義決策系統所有決策類的約簡不同，局部約簡只定義部分決策類的約簡; 2017年，Yao等[22]在完備決策系統下定義了特定決策類的正域約簡，提出特定決策類正域約簡的判定定理，并討論了特定決策類正域約簡與所有決策類正域約簡的關系; 2017年，Liu等[23]在完備系統下提出第l決策類約簡和β約簡的概念，并給出了基于差別矩陣的約簡算法。

基于上述研究，文獻[17]對不完備決策系統的所有決策類的約簡進行了討論，文獻[22-23]在完備決策系統下對單特定決策類的正域約簡進行了研究。由于在實際應用中存在大量的不完備數據，且決策者往往傾向于關注部分決策類，現有的不完備決策系統的正域約簡方法針對上述情況討論較少。另外，基于差別矩陣的約簡方法可以求取所有約簡，用戶可以根據個人偏好選擇具有自身偏好的約簡，并且通過所有約簡可以求取最短約簡。為此，本文提出了基于多特定決策類的不完備決策系統正域約簡的理論框架，當選取的多特定決策類中決策類數目為1時，基于多特定決策類的不完備決策系統正域約簡退化為不完備決策系統單特定決策類的正域約簡;當選取的多特定決策類為決策系統中所有決策類時，基于多特定決策類的不完備決策系統正域約簡退化為不完備決策系統所有決策類的正域約簡。首先，本文介紹了不完備決策系統的相關概念;然后，定義了不完備決策系統的多特定決策類的正域約簡，構造了相應的差別矩陣及區分函數，提出了基于差別矩陣的不完備決策系統多特定決策類正域約簡算法（Positive region preservation Reduction for Multispecific decision classes reduction based on Discernibility Matrix in incomplete decision systems， PRMDM）;最后，實驗驗證了PRMDM算法的有效性。

由于實驗采用標準UCI數據集，預處理后數據集中的決策系統是完備決策系統，所以需要將完備決策系統轉換為不完備決策系統。本文采用文獻[19]中的方式對數據集進行處理，具體處理方式為：數據集中除決策屬性外，每一列隨機缺失10%的屬性值，缺失值在決策系統中用表示。處理后的數據集詳見https：//github.com/KInfinite/datasets。

3.1 約簡結果對比

選取4組UCI數據集進行約簡結果對比，約簡結果如表3所示。其中，表3中“所有決策類約簡”對應PRDM算法的約簡結果，“單特定決策類約簡”對應多特定決策類中決策數目為1時PRMDM算法的約簡結果，“多特定決策類約簡”對應多特定決策類中決策類數目為2 時PRMDM算法的約簡結果。表4列出了約簡數目及平均約簡長度，其中，表4中“所有決策類約簡”和“特定決策類約簡”分別對應PRDM算法和PRMDM算法的約簡數目和平均約簡長度。

由表4可知，對于數據集Teachingassistantevaluation、House、Connectionistbench和Cardiotocography，當所選多特定決策類中決策類數為1或2時，PRMDM算法的平均約簡長度小于PRDM算法的平均約簡長度。

3.2 約簡效率對比

本節選取4組UCI數據集分別按照對象個數遞增和屬性個數遞增的方式進行約簡效率對比。約簡效率如圖1和圖2所示，其中，圖1和圖2中“所有決策類”的約簡耗時曲線對應PRDM算法的約簡耗時，圖1和圖2中“決策類1”“決策類2”和“決策類：1，2”的約簡耗時曲線對應PRMDM算法的約簡耗時。在數據集按照對象個數遞增的方式進行約簡效率對比的實驗中，對于每個數據集，將數據集分成10等份，第1份構成1號數據集，第1份和第2份構成2號數據集，以此類推，10號數據集即為完整的數據集。

圖1是各數據集隨對象數目增加約簡耗時的變化曲線，隨著對象數目的增加，約簡耗時逐漸增加。圖2是各數據集隨屬性數目增加約簡耗時的變化曲線，隨著屬性數目的增加，約簡耗時逐漸增加。由于在屬性數目較少時，區分函數相對簡單，求解區分函數所需的時間較少，所以在屬性增加的前期階段約簡耗時無明顯增加，在屬性增加的后期階段，由于區分函數相對復雜，求解區分函數所需的時間逐漸增加，所以約簡耗時不斷增加。

雖然PRDM算法及PRMDM算法的時間復雜度均為O（|C||U|2），但通過圖1和圖2可以發現，當選取的多特定決策類中決策類的數目遠少于決策系統中所有決策類的數目時，PRMDM算法在約簡效率上高于PRDM算法。例如，數據集Connectionistbench和Cardiotocography中的所有決策類的數目分別為11和10，對于每個數據集，當選取的多特定決策類中決策類的數目分別為1和2時，PRMDM算法在約簡效率上高于PRDM算法，這是由于當選取的多特定決策類中決策類的數目遠少于決策系統中所有決策類的數目時，多特定決策類正域約簡的差別矩陣中非空差別屬性集的數目小于所有決策類正域約簡的差別矩陣中非空差別屬性集的數目，所以PRMDM算法在構造差別矩陣的耗時上少于PRDM算法。另外，由于多特定決策類正域約簡的差別矩陣中非空差別屬性集的數目小于所有決策類正域約簡的差別矩陣中非空差別屬性集的數目，所以多特定決策類正域約簡的區分函數中合取項的數目小于所有決策類正域約簡的區分函數中合取項的數目，從而PRMDM算法在將區分函數轉化為極小析取范式的耗時上少于PRDM算法。需要注意的是，只有當選取的多特定決策類中決策類的數目遠少于決策系統中所有決策類的數目時，PRMDM算法在約簡效率上才能高于PRDM算法;當PRMDM算法中選取的多特定決策類為決策系統中的所有決策類時，PRMDM算法退化為PRDM算法，此時PRMDM算法相比PRDM算法在約簡效率上并無提升。

4 結語

本文提出了基于多特定決策類的不完備決策系統正域約簡的理論框架，定義了不完備決策系統單特定決策類正域約簡，構造了相應的差別矩陣及區分函數，提出了基于差別矩陣的不完備決策系統多特定決策類正域約簡算法。本文選取4組UCI數據集進行實驗，實驗結果驗證了本文所提算法的有效性。由于本文提出的算法是基于差別矩陣的約簡算法，為提高算法的約簡效率，下一步將研究差別矩陣的優化問題。

參考文獻 （References）

[1] PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Sciences， 1982， 11（5）： 341-356.

[2] 王國胤，姚一豫，于洪.粗糙集理論與應用研究綜述[J].計算機學報，2009，32（7）：1229-1246.（WANG G Y， YAO Y Y， YU H. A survey on rough set theory and applications [J]. Chinese Journal of Computers， 2009， 32（7）： 1229-1246.）

[3] 于洪，王國胤，姚一豫.決策粗糙集理論研究現狀與展望[J].計算機學報，2015，38（8）：1628-1639.（YU H， WANG G Y， YAO Y Y. Current research and future perspectives on decisiontheoretic rough sets [J]. Chinese Journal of Computers， 2015， 38（8）： 1628-1639.）

[4] LIANG D C， LIU D， PEDRYCZ W， et al. Triangular fuzzy decisiontheoretic rough sets [J]. International Journal of Approximate Reasoning， 2013， 54（8）： 1087-1106.

[5] ZHANG Q H， ZHANG P， WANG G Y. Research on approximation set of rough set based on fuzzy similarity [J]. Journal of Intelligent and Fuzzy Systems， 2017， 32（3）： 2549-2562.

[6] QIN K Y， YANG J L， PEI Z. Generalized rough sets based on reflexive and transitive relations [J]. Information Sciences， 2008， 178（21）： 4138-4141.

[7] MIAO D Q， ZHAO Y， YAO Y Y， et al. Relative reducts in consistent and inconsistent decision tables of the Pawlak rough set model [J]. Information Sciences， 2009， 179（24）： 4140-4150.

[8] WANG F， LIANG J Y， QIAN Y H. Attribute reduction： a dimension incremental strategy [J]. KnowledgeBased Systems， 2013， 39： 95-108.

[9] WU W Z， Q Y H， LI T J， et al. On rule acquisition in incomplete multiscale decision tables [J]. Information Sciences， 2017， 378： 282-302.

[10] CHEN H M， LI T R， CAI Y， et al. Parallel attribute reduction in dominancebased neighborhood rough set [J]. Information Sciences， 2016， 373： 351-368.

[11] LIU D， LI T R， ZHANG J B. Incremental updating approximations in probabilistic rough sets under the variation of attributes[J]. KnowledgeBased Systems， 2015， 73： 81-96.

[12] MIN F， ZHANG Z H， DONG J. Ant colony optimization with partialcomplete searching for attribute reduction [J]. Journal of Computational Science， 2018， 25： 170-182.

[13] ZHU W， WANG F Y. Reduction and axiomization of covering generalized rough sets[J]. Information Sciences， 2003， 152（2）： 217-230.

[14] KRYSZKIEWICZ M. Rough set approach to incomplete information systems [J]. Information Sciences， 1998， 112（1/2/3/4）： 39-49.

[15] SKOWRON A， RAUSZER C. The discernibility matrices and functions in information systems [M]// SLOWINSKI R. Intelligent Decision Support： Handbook of Applications and Advances of the Rough Sets Theory. Dordrecht： Kluwer Academic Publishers， 1992： 331-362.

[16] LIANG J Y， XU Z B. The algorithm on knowledge reduction in incomplete information systems [J]. International Journal of Uncertainty， Fuzziness and KnowledgeBased Systems， 2002， 10（1）： 95-103.

[17] 周獻中，黃兵，李華雄，等.不完備信息系統知識獲取的粗糙集理論與方法[M].南京：南京大學出版社，2010：52-104.（ZHOU X Z， HUANG B， LI H X， et al. Rough Set Theory and Method of Knowledge Acquisition in Incomplete Information Systems [M]. Nanjing： Nanjing University Press， 2010： 52-104.）

[18] QIAN Y H， LIANG J Y， LI D Y， et al. Approximation reduction in inconsistent incomplete decision tables [J]. KnowledgeBased Systems， 2010， 23（5）： 427-433.

[19] SHU W H， QIAN W B. A fast approach to attribute reduction from perspective of attribute measures in incomplete decision systems[J]. KnowledgeBased Systems， 2014， 72： 60-71.

[20] QIAN W B， SHU W H， XIE Y H， et al. Feature selection using compact discernibility matrixbased approach in dynamic incomplete decision system [J]. Journal of Information Science and Engineering， 2015， 31（2）： 509-527.

[21] CHEN D G， TSANG E C C. On the local reduction of information system [C]// Proceedings of the 2005 International Conference on Advances in Machine Learning and Cybernetics. Heidelberg： SpringerVerlag， 2006： 588-594.

[22] YAO Y Y， ZHANG X Y. Classspecific attribute reducts in rough set theory [J]. Information Sciences， 2017， 418/419： 601-618.

[23] LIU G L， HUA Z， ZOU J Y. Local attribute reductions for decision tables[J]. Information Sciences， 2017， 422： 204-217.