關(guān)系決策系統(tǒng)中相對不可區(qū)分和區(qū)分關(guān)系的約簡

李旭 榮梓景 阮曉曦

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

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

關(guān)鍵詞： 粗糙集;不可區(qū)分關(guān)系;區(qū)分關(guān)系;關(guān)系決策系統(tǒng);屬性約簡

中圖分類號：TP18

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

最初不可區(qū)分關(guān)系和區(qū)分關(guān)系兩者的屬性約簡研究是在等價關(guān)系的基礎(chǔ)上實現(xiàn)的。

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

因為很多類型決策表的數(shù)據(jù)不完備，還有數(shù)值型數(shù)據(jù)、混合型數(shù)據(jù)等問題，通常不能誘導(dǎo)出等價關(guān)系。因此需要考慮一般關(guān)系上的不可區(qū)分關(guān)系和區(qū)分關(guān)系。本文在文獻(xiàn)[14]概念的基礎(chǔ)上，提出了一般關(guān)系決策系統(tǒng)的相對不可區(qū)分關(guān)系及相對區(qū)分關(guān)系。

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

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

3 決策表中的相對區(qū)分關(guān)系的約簡

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

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

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

4 關(guān)系決策系統(tǒng)中相對不可區(qū)分關(guān)系的約簡

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

定義6 設(shè)（U，C）是關(guān)系系統(tǒng)，屬性集C由U上的關(guān)系RC構(gòu)成，對于任意（x， y）∈U×U，現(xiàn)定義如下4種關(guān)系：

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

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

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

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

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

由定義6知，當(dāng)存在a∈C時，關(guān)系Ra決定的相對不可區(qū)分關(guān)系為：

定義8 設(shè)（U，C∪D）為關(guān)系決策系統(tǒng)，當(dāng)BC時，若B滿足下列兩條件，稱B是C相對不可區(qū)分關(guān)系的約簡：

推論4 設(shè)（U，C∪D）為關(guān)系決策系統(tǒng)，BC，B是C相對不可區(qū)分關(guān)系約簡的充要條件是：B是C中滿足條件gij∩B≠的最小子集。

算法3 BIIND。

輸入 關(guān)系決策系統(tǒng)（U，C∪D）。

輸出 相對不可區(qū)分關(guān)系的全部約簡。

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

步驟2 構(gòu)造辨識函數(shù)f=∏（∑gij≠gij），并把辨識函數(shù)f從合取范式轉(zhuǎn)化為析取范式的形式;

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

1）根據(jù)算法3，構(gòu)建6×6的辨識矩陣：

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

5 關(guān)系決策系統(tǒng)中相對區(qū)分關(guān)系的約簡

在一般關(guān)系上，本章提出了相對區(qū)分關(guān)系的定義。為得到其約簡，證明了相應(yīng)的辨識矩陣。

定義11 設(shè)（U，C∪D）為關(guān)系決策系統(tǒng)，當(dāng)BC時，若B滿足下列兩條件，稱B是C相對區(qū)分關(guān)系的約簡：

1）根據(jù)算法4，構(gòu)建6×6的辨識矩陣：

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

6 實例分析

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

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

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

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

7 結(jié)語

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

參考文獻(xiàn)（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] 張文修， 梁怡， 吳偉志. 信息系統(tǒng)與知識發(fā)現(xiàn)[M]. 北京： 科學(xué)出版社， 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] 王超， 羅可. 不完備信息系統(tǒng)中基于限制容差關(guān)系的屬性約簡方法[J]. 計算機應(yīng)用， 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] 楊霽琳， 秦克云， 裴崢. 不完備信息系統(tǒng)中的不可區(qū)分關(guān)系[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] 陳鑫影， 邱占芝. 基于可分辨關(guān)系的知識約簡[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] 秦克云， 敬思惠. 決策系統(tǒng)基于不可區(qū)分關(guān)系及區(qū)分關(guān)系的約簡[J]. 計算機科學(xué)， 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] 榮梓景. 關(guān)系決策系統(tǒng)的分布約簡[J]. 計算機工程與應(yīng)用， 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.）