關系決策系統中相對不可區分和區分關系的約簡

李旭 榮梓景 阮曉曦

摘 要：針對相對不可區分和區分關系約簡的問題提出相應的算法。首先，考慮等價關系中相對不可區分關系的約簡，提出一種新的辨識矩陣，并在此基礎上得到了一種約簡算法，通過關系的補關系提出相對區分關系的約簡算法。然后，將相對不可區分關系等概念推廣到一般關系。對于關系決策系統的相對不可區分關系約簡給出了相應的辨識矩陣，并利用關系的補關系得到了相對區分關系約簡的辨識矩陣，從而得到了兩者的約簡算法。

最后，在選取的UCI數據集上，對提出的算法進行驗證。在等價關系上，基于絕對約簡的相對不可區分關系的約簡（EQIND）算法與相對不可區分一般關系的約簡（BIIND）算法所得約簡相同， 基于絕對約簡的相對區分關系的約簡（EQDIS）算法與相對區分一般關系的約簡（BIDIS）算法所得約簡相同;同時算法BIIND、BIDIS可以對不完備決策表進行約簡。實驗結果驗證了所提算法的可行性。

關鍵詞： 粗糙集;不可區分關系;區分關系;關系決策系統;屬性約簡

中圖分類號：TP18

文獻標志碼：A

Abstract： Corresponding reduction algorithms for relative indiscernibility and discernibility relation were proposed. Firstly， considering the reduction of the relative indiscernibility relation in equivalence relation， the corresponding discernibility matrix was proposed and a reduction algorithm was proposed based on the matrix. Then， a reduction algorithm for relative discernibility relation was proposed according to the complementary relationship of the relation. Secondly， the concepts such as relative indiscernibility relation were expanded to the general relation. The corresponding discernibility matrix was proposed for the relative indiscernibility relation reduction in the relation decision system， and the corresponding discernibility matrix for the relative discernibility relation reduction was obtained by using the complementary relationship of the relation， so the reduction algorithms for both relations were obtained. Finally， the proposed algorithms were verified on the selected UCI datasets. In the equivalence relation，

the algorithm of the relative EQuivalence INDiscernibility relation reduction based on absolute reduction （EQIND） and the algorithm of the relative BInary INDiscernibility relation reduction （BIIND） have the same results. The algorithm of the relative EQuivalence DIScernibility relation reduction based on absolute reduction （EQDIS） and the algorithm of the relative BInary DIScernibility relation reduction （BIDIS） have the same results. Meanwhile， BIIND and BIDIS are suitable for the incomplete decision table. The feasibility of the proposed algorithms were verified by the experimental results.

Key words：? rough set; indiscernibility relation; discernibility relation; relation decision system; attribute reduction

0 引言

粗糙集理論[1]作為處理不確定性、不一致問題的數據分析處理理論，在1982年由波蘭學者Pawlak提出。屬性約簡是粗糙集理論研究中的核心問題之一，其主要思想是根據某種特定規則，在保持論域中的對象分類不變的前提下，刪除冗余屬性?，F階段屬性約簡理論研究已取得了重大進展，例如，正域約簡[2-3]、變精度約簡[4]、分配約簡[5]、覆蓋約簡[6-7]、局部約簡[8]等。許多學者在等價關系的基礎上對屬性約簡進行了廣泛深入的討論，然而當數據存在不完備、不一致現象時，通常誘導不出等價關系，于是學者通過容差關系[9]、限制容差關系[10]、相似關系[11]等非等價的二元關系拓寬了屬性約簡的研究范圍。目前，文獻[12]根據條件（決策）屬性在論域中所決定的關系，給出了一般關系并在該關系下討論了屬性約簡。文獻[13]將正域約簡推廣至一般關系決策系統，并給出了嚴格證明。文獻[14]在決策表中提出了不可區分關系及區分關系的約簡，同時，在信息表中給出了關于區分和不可區分的4個關系，并研究了4個關系的相關性質。文獻[15]針對不完備信息系統給出了不可區分關系，但未提出約簡的概念。文獻[16]在信息表中運用啟發式約簡算法得到了區分關系的約簡。文獻[17]在決策表中進一步研究了不可區分關系和區分關系兩者的約簡，給出了相應的辨識矩陣，并得到了相應的約簡算法。許多學者采用啟發式算法，因為啟發式約簡算法能得到約簡，但并不能得到所有約簡;而關于辨識矩陣[18-19]得到約簡的方法雖然需要嚴密的數學論證，且計算復雜度較高，但能得到全部約簡。因此，本文使用基于辨識矩陣的約簡方法，即通過構建辨識矩陣將辨識函數從合取范式轉化為析取范式，從而得到全部約簡。

最初不可區分關系和區分關系兩者的屬性約簡研究是在等價關系的基礎上實現的。

基于決策約簡，本文提出了相對不可區分關系的約簡（EQuivalence INDiscernibility relation reduction based on absolute reduction， EQIND）算法和相對區分關系的約簡（EQuivalence DIScernibility relation reduction based absolute reduction， EQDIS）算法。

因為很多類型決策表的數據不完備，還有數值型數據、混合型數據等問題，通常不能誘導出等價關系。因此需要考慮一般關系上的不可區分關系和區分關系。本文在文獻[14]概念的基礎上，提出了一般關系決策系統的相對不可區分關系及相對區分關系。

將等價關系上的4個概念推廣到一般關系，同時在關系決策系統中，提出了相對不可區分關系約簡（BInary INDiscernibility Relation Reduction， BIIND）。利用關系的補關系作為關系的概念及相對不可區分關系約簡所對應的辨識矩陣，提出了相對區分關系約簡（BInary DIScernibility Relation Reduction， BIDIS）。此外，作為本文提出的約簡算法的應用，給出了不完備決策表中相對不可區分及區分關系的約簡。

算法適用于一致決策表，也適用于不一致決策表。若假設在步驟3中，絕對約簡集中存在{a1，a3，d}，{a1，a3，a4}，刪除g0gggggg后得{a1，a3}，{a1，a3，a4}，因為a1∧a3∧a4a1∧a3，所以在析取范式中刪除合取式{a1，a3，a4}。即在絕對約簡集中刪除{a1，a3，a4}后得相對不可區分關系的所有約簡。

3 決策表中的相對區分關系的約簡

在決策表中，現討論對象之間另一種重要的關系。相對不可區分的補關系就是相對區分關系，因而通過考慮關系的補關系的概念，提出本章的約簡相對應的辨識矩陣。

決策表（U，C∪D）中相對區分關系的約簡就是考慮把補關系作為新關系的相對不可區分約簡，即決策表（U，C′∪D′）中相對不可區分關系的約簡，其中，當a′∈C′，條件屬性a′在U上的等價關系為Ra′，它與Ra互補。當d′∈D′，決策屬性d′在U上的等價關系為Rd′，它與Rd互補。

設（U，C∪D）是決策表，為得到相對區分關系的約簡，現定義辨識矩陣為M"nn=（m"ij）n×n，其中：m"ij是矩陣的元素;n是論域中對象數。

4 關系決策系統中相對不可區分關系的約簡

在信息系統中，當將二元關系推廣為一般關系時，本章提出了4種關于關系的概念。同時，在關系決策系統中，給出了相對不可區分關系的定義及其約簡，并證明了其對應的辨識矩陣。

定義6 設（U，C）是關系系統，屬性集C由U上的關系RC構成，對于任意（x， y）∈U×U，現定義如下4種關系：

1）若有RC={（x， y）∈U×Ua∈C，（x， y）∈Ra}，稱RC是由C確定的不可區分關系。

2）若有WRC={（x， y）∈U×Ua∈C，（x， y）∈Ra}，稱WRC是由C確定的弱不可區分關系。

3）若有R′C={（x， y）∈U×Ua∈C，（x， y）Ra}，稱R′C是由C確定的區分關系。

4）若有WR′C={（x， y）∈U×Ua∈C，（x， y）Ra}，稱WR′C是由C確定的弱區分關系。

定義7 設（U，C∪D）為關系決策系統，條件屬性集C和決策屬性集D決定U上一般關系RC，RD，（x， y）∈U×U，RC∩RD={（x， y）a∈C，（x， y）∈Ra∧（x， y）∈RD}，稱RC∩RD是由條件屬性集C確定的相對不可區分關系。

由定義6知，當存在a∈C時，關系Ra決定的相對不可區分關系為：

定義8 設（U，C∪D）為關系決策系統，當BC時，若B滿足下列兩條件，稱B是C相對不可區分關系的約簡：

推論4 設（U，C∪D）為關系決策系統，BC，B是C相對不可區分關系約簡的充要條件是：B是C中滿足條件gij∩B≠的最小子集。

算法3 BIIND。

輸入 關系決策系統（U，C∪D）。

輸出 相對不可區分關系的全部約簡。

步驟1 對于任意對象，根據條件屬性集、決策屬性集，構建辨識矩陣Gnn=（gij）n×n;

步驟2 構造辨識函數f=∏（∑gij≠gij），并把辨識函數f從合取范式轉化為析取范式的形式;

步驟3 通過析取范式∑li=1（∏ Bi）得到B1，B2，…，Bl，算法結束。

1）根據算法3，構建6×6的辨識矩陣：

本章提所涉的關系是對文獻[14，17]中的進一步研究，文獻[17]中約簡基于的二元關系是等價關系，而本章中的相對不可區分關系不需要滿足自反性、對稱性、傳遞性中任何性質。例如，當（x，x）∈IndC（D）時，推廣后，（x，x）∈RC∩RD或（x，x）RC∩RD。文獻[17]中的約簡算法僅能處理決策表中誘導出的等價關系，無法處理決策表中誘導出的對稱關系、容差關系等二元關系。而算法3能夠處理決策表誘導出的上述所有二元關系，因此，基于等價關系的相對不可區分關系約簡是本章的特例。

5 關系決策系統中相對區分關系的約簡

在一般關系上，本章提出了相對區分關系的定義。為得到其約簡，證明了相應的辨識矩陣。

定義11 設（U，C∪D）為關系決策系統，當BC時，若B滿足下列兩條件，稱B是C相對區分關系的約簡：

1）根據算法4，構建6×6的辨識矩陣：

對于不可區分關系和區分關系，則僅需證兩者約簡中相應的任意一個辨識矩陣，同時引入補關系的概念，得另一約簡相應的辨識矩陣。本章中定義的相對區分關系是對概念的進一步推廣。同時，相較于文獻[17]算法僅能處理等價類，本章所提出的算法可以處理包括等價關系在內的二元關系。例如，在不完備決策表（見表2）中通常不能誘導出等價關系，因而文獻[17]算法不適用，通過使用本文所提的算法3、算法4可以解決該問題。

6 實例分析

從UCI數據集中選取了3個數據集（Zoo、Hepatitis和Statlog（Heart））（見表3）進行實驗，以驗證本文算法的有效性和可行性。程序運行環境：Intel Core i5-2440 CPU 3.10GHz，Windows10 64位，算法為Python代碼實現。

因Hepatitis數據集中的數據存在缺失現象，因而通常不能誘導出等價關系。算法1、算法2是基于等價關系對決策表進行得約簡，因而該表不適用。而對于算法3、算法4，已將等價關系推廣至一般關系（即不需要滿足自反性、對稱性、傳遞性的任意性質），因此可對數據集中所給出的決策表進行相對不可區分約簡和相對可區分約簡。

約簡結果如表4所示，從中可看出，算法1和算法3在完備數據集（Zoo、Statlog（Heart））上約簡結果相同，算法2和算法4在完備數據集上約簡結果相同。屬性個數為約簡結果的基，約簡集個數是在相同的基下約簡個數。例如，在Zoo數據集上，運用算法2得到375個約簡結果，其中：當約簡的基為2時有6個約簡;當約簡的基為3時有369個約簡。

數據集算法屬性個數約簡集個數約簡舉從實驗結果可看出：在決策表中，二元關系是等價關系時，本文所提出的算法1和算法2是可行的。在關系決策系統中，即二元關系是一般關系時，本文所提出的算法3和算法4是可行的。綜上所述，實驗結果驗證了本文所提出4個算法的可行性。

7 結語

本文在關系系統上，首先提出了弱不可區分關系、不可區分關系、弱區分關系及區分關系等4個概念。其次，在關系決策系統中，提出了相對不可區分一般關系、相對區分一般關系兩者的概念，及兩者約簡的定義，并證明了約簡對應的辨識矩陣。最后，通過舉例說明本文所提出的約簡是對文獻[14，17]所給出的約簡的推廣。

參考文獻（References）

[1] PAWLAK Z. Rough sets： theoretical aspect of reasoning about data[M]. Dordrecht： Kluwer Academic Publishers， 1991： 9-42.

[2] PAWLAK Z， SOWINSKI R. Rough set approach to multi-attribute decision analysis[J]. European Journal of Operational Research， 1994， 72（3）： 443-459.

[3] 張文修， 梁怡， 吳偉志. 信息系統與知識發現[M]. 北京： 科學出版社， 2003： 42-55. （ZHANG W X， LIANG Y， WU W Z. Information System and Knowledge Discovery[M]. Beijing： Science Press， 2003： 42-55.）

[4] INUIGUCHI M. Several approaches to attribute reduction in variable precision rough set model[C]// Proceedings of the 2005 International Conference on Modeling Decisions for Artificial Intelligence， LNCS 3558. Berlin： Springer， 2005： 215-226.

[5] LIU G. Assignment reduction of relation decision systems[C]// Proceedings of the 2017 International Joint Conference on Rough Sets， LNCS 10313. Cham： Springer， 2017： 384-391.

[6] CHEN D G， WANG C， HU Q. A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets[J]. Information Sciences， 2007， 177（17）： 3500-3518.

[7] WANG C， SHAO M， SUN B， et al. An improved attribute reduction scheme with covering based rough sets[J]. Applied Soft Computing， 2015， 26： 235-243.

[8] LIU G， HUA Z， ZOU J. Local attribute reductions for decision tables[J]. Information Sciences， 2018， 422： 204-217.

[9] FENG Q， LI R. Discernibility matrix based attribute reduction in intuitionistic fuzzy decision systems[C]// Proceedings of the 2013 International Workshop on Rough Sets， Fuzzy Sets， Data Mining， and Granular-Soft Computing， LNCS 8170. Berlin： Springer， 2013： 147-156.

[10] 王超， 羅可. 不完備信息系統中基于限制容差關系的屬性約簡方法[J]. 計算機應用， 2011， 31（12）： 3236-3239. （WANG C， LUO K. Attributes reduction method based on limited tolerance relation in incomplete information system[J]. Journal of Computer Applications， 2011， 31（12）： 3236-3239.）

[11] YANG X， YANG J， WU C， et al. Dominance-based rough set approach and knowledge reductions in incomplete ordered information system[J]. Information Sciences， 2008， 178（4）： 1219-1234.

[12] LIU G L. Attribute reduction approaches for general relation decision systems[J]. Pattern Recognition Letters， 2015， 65： 81-87.

[13] LIU G， HUA Z， CHEN Z. A general reduction algorithm for relation decision systems and its applications[J]. Knowledge-Based Systems， 2017， 119： 87-93.

[14] ZHAO Y， YAO Y Y， LUO F. Data analysis based on discernibility and indiscernibility[J]. Information Sciences， 2007， 177（22）： 4959-4976.

[15] 楊霽琳， 秦克云， 裴崢. 不完備信息系統中的不可區分關系[J]. 計算機工程， 2010， 36（13）： 4-6. （YANG J L， QIN K Y， PEI Z. Indiscernibility relation in incomplete information system[J]. Computer Engineering， 2010， 36（13）： 4-6.）

[16] 陳鑫影， 邱占芝. 基于可分辨關系的知識約簡[J]. 計算機工程， 2010， 36（4）： 53-55. （CHEN X Y， QIU Z Z. Knowledge reduction based on distinguishable relation[J]. Computer Engineering， 2010， 36（4）： 53-55.）

[17] 秦克云， 敬思惠. 決策系統基于不可區分關系及區分關系的約簡[J]. 計算機科學， 2018， 45（6）： 247-250. （QING K Y， JING S H. Attribute reduction of decision systems based on indiscernibility relation and discernibility relation[J]. Computer Science， 2018， 45（6）： 247-250.）

[18] SKOWRON A. Boolean reasoning for decision rules generation[C]// Proceedings of the 1993 International Symposium on Methodologies for Intelligent Systems. Berlin： Springer， 1993： 295-305.

[19] SKOWRON A， RAUSZER C. The discernibility matrices and functions in information systems [M]// SLOWINSKI R. Intelligent Decision Support. Berlin： Springer， 1992： 331-362.

[20] 榮梓景. 關系決策系統的分布約簡[J]. 計算機工程與應用， 2018， 54（17）： 62-66. （RONG Z J. Distribution reduction algorithms for relational decision systems[J]. Computer Engineering and Applications， 2018， 54（17）： 62-66.）