連續型數據的辨識矩陣屬性約簡方法

馮丹，黃洋，石云鵬，王長忠

(1. 國網葫蘆島供電公司 信息通信分公司，遼寧 葫蘆島 125000； 2. 渤海大學 數理學院，遼寧 錦州 121000)

連續型數據的辨識矩陣屬性約簡方法

馮丹1, 2，黃洋2，石云鵬2，王長忠2

(1. 國網葫蘆島供電公司 信息通信分公司，遼寧 葫蘆島 125000； 2. 渤海大學 數理學院，遼寧 錦州 121000)

屬性約簡是粗糙集理論在數據處理方面的重要應用，已有的針對連續型數據的屬性約簡算法主要集中在基于正域的貪心算法, 該方法只考慮了一致樣本和其他樣本的可辨識性，而忽略了邊界樣本點間可區分性。為了克服基于正域算法的缺點，提出了連續型數據的辨識矩陣屬性約簡模型，該模型不但考慮了正域樣本的一致性，同時考慮了邊界樣本的可分性。基于該模型，分析了屬性約簡結構，定義了辨識矩陣來刻畫特征子集的分類能力，構造了實值型數據的屬性約簡啟發式算法,并利用UCI標準數據集進行了驗證。理論分析和實驗結果表明,提出的算法能夠有效地處理連續型數據，提高了數據的分類精度。

鄰域關系；粗糙集；屬性約簡；辨識矩陣；啟發式算法

中文引用格式：馮丹，黃洋，石云鵬,等.連續型數據的辨識矩陣屬性約簡方法[J]. 智能系統學報， 2017, 12(3): 371-376.

英文引用格式：FENG Dan， HUANG Yang， SHI Yunpeng， et al. A discernibility matrix-based attribute reduction for continuous data[J]. CAAI transactions on intelligent systems, 2017, 12(3): 371-376.

粗糙集理論是由波蘭數學家Z.Pawlak[1]于1982年提出的，它是一種處理不確定性知識的數據分析理論。目前粗糙集理論已被廣泛應用于人工智能、過程控制、數據挖掘、決策支持以及知識發現等領域。屬性約簡是粗糙集理論的研究內容之一，它是利用粗糙集進行數據挖掘、規則抽取的理論基礎。其主要思想是在確保信息表的分類能力不變的情況下，刪除掉不必要屬性，保留必要屬性，從而導出問題的分類規則。屬性約簡無疑是在獲取規則的過程中最重要的核心問題，歷來受到大家的關注。

傳統的粗糙集理論[1-3]是基于等價關系來描述的, 由等價關系粒化樣本空間形成信息粒子, 構造論域上的上、下近似算子, 進而研究知識約簡與知識獲取問題。但是經典粗糙集只適用于離散型的數據，對于連續型數據，必須通過離散化才能處理。然而，數據的離散化會導致大量信息丟失，從而使計算的結果不能準確地反映分類信息。為此，經典粗糙集理論被進行了多角度的推廣，其中包括鄰域粗糙集模型[4-11]、優勢粗糙集模型[12-13]、覆蓋粗糙集模型[14-16]、模糊粗糙集模型[17-22]等。鄰域粗糙集模型是重要的推廣模型之一，基于此模型，許多學者研究了不同的依賴度函數，并設計了相應的屬性約簡算法[4-11]。例如，Hu[5]利用鄰域的概念定義了樣本空間的決策正域，構造了鄰域依賴度函數來刻畫屬性的分類能力，用于處理混合數據的屬性約簡；Zhao[7]根據數據精度設計了一個自適應性的鄰域粗糙集模型，并給出了基于該模型的代價敏感屬性約簡算法;Chen[8]利用鄰域粗糙集模型和信息測度為腫瘤分類進行特征選擇；Zhu[9]對鄰域粗糙集模型的邊界進行分布優化，從而為粒度的選取和組合提供了新方法。然而，鄰域粗糙集模型中的決策正域只考慮了一致性樣本與其他樣本的可辨識性，忽略了邊界樣本的可分性。因此，基于正域的依賴度函數不能正確地刻畫一個屬性子集的分類能力。為了克服基于正域算法的缺點，本文提出了基于辨識矩陣的屬性約簡算法。該算法克服了依賴度算法的局限性。

1 鄰域關系決策表的屬性約簡

設(U,A,F)為信息表，其中，U={x1,x2,…,xn}為樣本集合，A={a1,a2,…，am}是屬性集合，F={fj:j≤m}為U和A的關系集，fj:U→Vj，j≤m，Vj為屬性aj的值域。

定義1 設U={x1,x2,…,xn}為樣本集，B?A，令

則稱MB為U上的鄰域關系，稱(U,A,F)為基于鄰域關系的信息系統，簡稱鄰域信息表，ε表示相似度閾值。對于任意xi∈U，令

δB(xi)={xj∈U:(xi,xj)∈MB}

則稱δB(xi)為xi關于MB的鄰域。

鄰域關系可以用一個關系矩陣來表示。設屬性al∈A，對于任意xi,xj∈U，如果xj∈δal(xi)，那么記Nl(i,j)=1，否則記Nl(i,j)=0。因此，一個屬性al唯一地對應一個關系矩陣Nl。而屬性集合A的關系矩陣可以由公式NA=∩al∈ANl計算。

定義2 設(U,A,F,D=g0gggggg)為決策表，其中(U,A,F)為信息表，A={a1,a2,…am}，D為決策屬性。對于任意x∈U，令

同理，決策等價關系MD可以用關系矩陣ND來表示。即對于任意xi,xj∈U，如果xj∈[xi]D，那么記ND(i,j)=1，否則記ND(i,j)=0。

設ai∈B?A，如果POSB(D)=POSB-{ai}(D)，則稱ai相對于D是B中不必要的屬性；否則，稱ai是B中必要的屬性。如果POSB(D)=POSA(D)且B中每一個屬性相對于D都是B中必要的，則稱B是A的一個屬性約簡。

定理1 設(U,A,F,D=g0gggggg)為決策表,B?A，則POSB(D)=POSA(D)的充要條件是: 對于任意xi,xj∈U，如果滿足以下條件之一，即

1)xi∈POSA(D),xj?POSA(D)∧d(xi)≠d(xj);

2)xi,xj∈POSA(D)∧[xi]D∩[xj]D=?；

則有xj?δA(xi)?xj?δB(xi)。

證明 充分性證明。設?xi,xj∈U，如果xi∈POSA(D)和xj?POSA(D)且d(xi)≠d(xj)，則?X0∈U/D使得xi∈A(X0)以及xj?X0，于是δA(xi)?X0，從而xj?δA(xi)。由于POSB(D)=POSA(D)，所以對于任意Xk∈U/D，都有B(Xk)=A(Xk)，當然也有A(X0)=B(X0)。 由xi∈A(X0)，可得xi∈B(X0)，于是δB(xi)?X0，因此xj?δB(xi)。

如果xi,xj∈POSA(D)且[xi]D∩[xj]D=?,則存在X0和X1∈U/D使得X0≠X1且滿足xi∈A(X0)以及xj?X0。由xi∈A(X0)可得δA(xi)?X0，從而xj?δA(xi)。類似地，由于POSB(D)=POSA(D)，所以A(X0)=B(X0)。由xi∈A(X0)，可得xi∈B(X0)。從而δB(xi)?X0，因此xj?δB(xi)。

必要性證明。設xi∈POSA(D)，所以存在X0∈U/D使得δA(xi)?X0。對于滿足xj?POSA(D)且d(xi)≠d(xj)的任意xj∈U，有xj?X0，因此xj?δA(xi)。由于xj?δA(xi)?xj?δB(xi)，所以δB(xi)?X0，從而xi∈POSB(D)。于是POSA(D)?POSB(D),而POSB(D)?POSA(D)顯然成立,因此POSB(D)=POSA(D)。

根據定理1可以定義如下的辨識矩陣。

定義3 設(U,A,F,D=g0gggggg)為決策表，U={x1,x2,…,xn}，A={a1,a2,…am}，令

POSA(D)∧[xi]D∩[xj]D=?}

則稱DIS為決策表(U,A,F,D)的可辨識域。對于任意的樣本對(xi,xj)∈DIS，記

則稱DM(i,j)為xi,xj的辯識集合，稱DM為基于鄰域關系的辨識矩陣。

定理2 設DM為決策表(U,A,F,D=g0gggggg)的辨識矩陣，B?A，則B是決策表的一個約簡的充要條件是：B滿足B∩DM(i,j)≠?，?xi,xj∈U的最小子集。

定理2說明通過辨識矩陣可以等價地刻畫決策表的屬性約簡。下面給出決策表的屬性約簡的辨識公式。通過析取和合取運算可以獲得決策表的全部約簡。

定義4 設DM為決策表(U,A,F,D)的辨識矩陣，U={x1,x2,…,xn}，辨識函數定義為

定理3 設f(U,A,F,D)為決策表(U,A,F,D)的辨識函數，如果通過析取和合取運算，有

A的所有約簡組成的集類記為REDD(A)={Bk:k≤l}。

下面通過一個具體的實例來說明應用辨識矩陣方法如何求解鄰域決策表的屬性約簡。

例1 表1是具有4種癥狀a1、a2、a3、a4的某些病例信息，具體描述如表1所示。

表1 病例決策信息表

取ε=0.25，根據定義1和定義2，計算關系矩陣Nl(i≤4)、NA以及決策關系矩陣ND分別為

說明NA?ND。由以上計算知，POSA(D)= {x1,x3,x5,x6}。 根據定義3，得到辨識矩陣如表2所示。

表2 病例決策信息表的辨識矩陣

所以，可得決策表的辨識函數為

f=(a1∨a4)∧(a1∨a2∨a4)∧a2=

(a1∧a2)∨(a2∧a4)

因此{a1,a2}和{a2,a4}是病例決策表的兩個約簡。

2 屬性約簡算法

經典粗糙集算法是以等價關系作為聚類標準的。對于數值型數據集，首先進行離散化并構造等價關系。若兩個樣本在所有屬性上取值一樣，那么這兩個樣本就為一類，否則不是一類。而在離散化過程中，避免不了信息流失，而這恰恰是當今研究的熱點。本算法通過定義一個距離參數，考慮某兩個樣本在屬性上的相似程度。如果兩個樣本之間距離小于閾值，則這兩個樣本就可以聚為一類，這比經典粗糙集的理論顯然更多地考慮了樣本之間的聯系，避免大量信息的流失，從而提高了屬性約簡的精度。由于利用定理3去搜索決策表的全部約簡是一個NP問題，因此利用本文提出的辨識矩陣的概念來構造一個啟發式算法。

算法 辨識矩陣屬性約簡算法(DISRS)。

輸入 (U,A,D=g0gggggg)，閾值θ//θ是用于算法停止搜索的閾值。

輸出 約簡RED。

1)計算正域POSA(D)。

2)計算出關系矩陣ND，即對于任意的樣本xi,xj∈U,若d(xi)≠d(xj),令ND(i,j)=0, 否則，令ND(i,j)=1。

4)計算NA=∪Nl，RED←A。

5)?al∈A，計算N{red-al}和sum(N{red-al})，其中sum(N{red-al})表示對矩陣N{red-al}的行列求和。

了更好地理解所提出的算法，下面給出該算法的流程圖，如圖1。

圖1 屬性約簡算法流程圖Fig. 1 Flow chart of attribute reduction

3 實驗分析

為了驗證算法的有效性，從一些文獻中選出4個相關的屬性約簡方法與本文所提的算法作比較。這4個算法分別是經典粗糙集算法(FCMRS)[1]、鄰域粗糙集算法(NBRS)[5]、鄰域粗糙信息測度算法(NBIM)[8]以及自適應鄰域粗糙集模型(APTNB)[7]。 本實驗主要從算法選擇的屬性數目和相應的分類精度兩個方面進行比較。計算機運行的環境參數為：奔騰雙核，CPU E5200 1.90 GHz，RAM 4.0 GB，軟件為 MATLAB 2007。

本實驗采用K近鄰(KNN,K=3)和支持向量機(RBF-SVM)分類器來評估這些屬性約簡算法的優劣，RBF-SVM分類器中參數采用默認值。數據的分類精度是基于十折交叉驗證方法計算的。從UCI數據集中選擇了5個數值型的數據集，其屬性和分類信息描述如表3所示。在本文所提的算法(DISRS)中，停止搜索的閾值θ設置為θ=0.005。為了說明該算法的有效性和可行性，首先對各個數據集進行了屬性約簡，選取約簡數據的最高分類精度所對應的屬性數目進行比較，具體結果如表4所示，其中ε列表示對應數據約簡后所取得的最高分類精度的相似度閾值的取值。表5和表6分別給出了各個數據集屬性約簡前后的分類精度。

表3 數據描述

從表4中可以看出，這5種屬性約簡方法都能夠有效地對數據集進行屬性約簡。FCMRS算法選取的屬性數目最少，DISRS算法次之。表5和表6表明，DISRS算法的分類精度最高，FCMRS算法的分類精度最低。同時，DISRS算法所對應的分類精度明顯好于其他方法。10次分類任務，DISRS算法獲得了8次最高分類精度，APTNB獲得了2次，NBIM獲得了1次，而FCMRS和NBRS算法沒有獲得最高分類精度。但是NBRS算法的性能要比FCMRS方法好很多。這說明鄰域粗糙集模型在處理連續型數據時比經典粗糙集方法具有更大的優勢。造成FCMRS算法選擇的屬性數目少、分類精度低的原因，可能是由于FCMRS算法固有的離散化步驟破壞了原有數據的分類信息。而NBRS、NBIM和APTNB算法避免了離散化步驟，直接利用相似關系粒化數據空間，構造分類目標的依賴度函數用于分類，因此屬性約簡后的數據分類精度明顯高于FCMRS算法。然而，NBRS、NBIM和APTNB算法只考慮一致樣本和其他樣本的可辨識性，忽略了邊界樣本點間可區分性，因此這3種算法的分類精度低于DISRS算法精度。而DISRS算法克服了NBRS、NBIM和APTNB算法的缺點，因此，在數據實驗分析中取得了較好的性能，即DISRS算法的分類精度不僅高于其他算法，而且有效地刪減了屬性。根據數據實驗分析表明，本文提出的算法是行之有效的，達到了理論預期的效果。

表4 屬性約簡的結果

表5 約簡數據的SVM后的分類精度

表6 約簡數據的3NN分類精度

4 結束語

鄰域粗糙集中基于正域的貪心算法只考慮了區分一致性樣本和異類樣本，忽略了邊界樣本間的區分性。事實上，一個屬性子集的分類能力不僅與一致樣本有關，也與邊界樣本有關。而辨識矩陣的概念正好反映了一組特征的區分能力。本文研究了基于鄰域辨識矩陣的屬性約簡方法，設計了啟發式屬性約簡的算法，并通過UCI數據集驗證了該算法的有效性。未來的工作將討論該方法在分類決策中的應用。

[1]PAWLAK Z. Rough sets [J]. International journal of computer and information sciences, 1982, 11(5): 341-356.

[2]SKOWRON A，RAUSZER C. The discernibility matrices and functions in information systems[C]// Slowinski R. (Ed.), Intelligent Decision Support. Dordrecht, Kluwer Academic Publishers, 1992: 331-362.

[3]MI J S, WU W Z, ZHANG W X. Approaches to knowledge reduction based on variable precision rough sets model [J]. Information sciences, 2004, 159(3/4): 255-272.

[4]WU W Z, ZHANG W X. Neighborhood operator systems and approximations [J]. Information sciences, 2002, 144(1/4): 201-217.

[5]HU Q H, YU D, LIU J F, et al. Neighborhood-rough-set based heterogeneous feature subset selection [J]. Information sciences, 2008, 178(18): 3577-3594.

[6]KIM D. Data classification based on tolerant rough set [J]. Pattern recognition, 2001, 34(8): 1613-1624.

[7]ZHAO H, WANG P, HU Q H. Cost-sensitive feature selection based on adaptive neighborhood granularity with multi-level confidence [J]. Information sciences, 2016, 366: 134-149.

[8]CHEN Y, ZHANG Z, ZHENG J, et al. Gene selection for tumor classification using neighborhood rough sets and entropy measures [J]. Journal of biomedical informatics, 2017, 67:59-68

[9]ZHU P, HU Q H. Adaptive neighborhood granularity selection and combination based on margin distribution optimation [J]. Information sciences, 2013, 249:1-12.

[10]鮑麗娜,丁世飛, 許新征, 等. 基于鄰域粗糙集的極速學習機算法[J]. 濟南大學學報，2015, 29(5): 367-371. BAO Lina, DING Shifei, XU Xinzheng, et al. Extreme learning machine algorithm based on neighborhood rough sets[J]. Journal of jinan university, 2015, 29(5): 367-371.

[11]謝娟英, 李楠, 喬子芮. 基于鄰域粗糙集的不完整決策系統特征選擇算法[J]. 南京大學學報，2016, 47:384-390. XIE Juanying, LI Nan, QIAO Zirui. A feature selection algorithm based on neighborhood rough sets for incomplete information systems[J]. Journal of Nanjing university, 2016, 47:384-390.

[12]徐偉華. 序信息系統與粗糙集[M]. 北京: 科學出版社, 2013.

[13]GRECO S, MATARAZZO B, SLOWINSKI R. Rough sets methodology for sorting problems in presence of multiple attributes and criteria[J]. European journal of operational research, 2002, 38:247-259.

[14]WANG C, HE Q, CHEN D G, et al. A novel method for attribute reduction of covering decision tables[J]. Information sciences, 2014, 254: 181-196.

[15]WANG C, SHAO M, SUN B, et al. An improved attribute reduction scheme with covering based rough sets[J]. Applied soft computing, 2015, 26(1): 235-243.

[16]ZHU W, WANG F Y. Reduction and maximization of covering generalized rough sets[J]. Information sciences, 2003, 152: 217-230.

[17]DUBOIS D, PRADE H. Rough fuzzy sets and fuzzy rough sets[J]. International journal of general systems, 1990, 17: 191-208.

[18]WANG C, QI Y, HU Q, et al. A fitting model for feature selection with fuzzy rough sets[J]. IEEE transaction on fuzzy systems, 2016,99: 1-1.

[19]WANG C,SHAO M, QIAN Y. Feature subset selection based on fuzzy neighborhood rough sets[J]. Knowledge-based systems, 2016, 111(1): 173-179.

[20]CHEN D G, ZHANG L, ZHAO S Y, et al. A novel algorithm for finding reducts with fuzzy rough sets[J]. IEEE transaction on fuzzy systems, 2013, 20(2): 385-389.

[21]WANG X Z, ZHAI J H, LU S X. Induction of multiple fuzzy decision trees based on rough set technique[J]. Information sciences, 2008, 178(16): 3188-3202.

[22]ZHAO S Y, TSANG C C, CHEN D. Building a rule-based classifier by using fuzzy rough set technique[J]. IEEE transaction on knowledge and data engineering, 2010, 22(5): 624-638.

A discernibility matrix-based attribute reduction for continuous data

FENG Dan1,2， HUANG Yang2， SHI Yunpeng2， Wang Changzhong2

(1. Information and Communication Branch, State Grid Power Supply Company of Huludao, Huludao 125000, China; 2. College of Mathematics and Physics, Bohai University, Jinzhou 121000, China)

In data processing, attribute reduction is an important application of rough set theory. The existing methods for continuous data mainly concentrate on the greedy algorithms based on the positive region. These methods take account of only the identifiability between consistent samples and other samples while ignoring distinguishability among the boundary samples. To overcome the disadvantage based on the positive domain algorithm, this paper proposed a new method for attribute reduction using a discernibility matrix. The model considers not only the consistency of samples in the positive region but also the reparability of boundary samples. On this basis, this paper analyzes the structure of attribute reduction and defines a discernibility matrix to characterize the discernibility ability of a subset of attributes. Next, an attribute reduction algorithm was designed based on the discernibility matrix. The validity of the proposed algorithm was verified using UCI standard data sets and theoretical analysis.

neighborhood relation; rough set; attribute reduction; discernibility matrix; heuristic algorithm

10.11992/tis.201704032

http://kns.cnki.net/kcms/detail/23.1538.TP.20170703.1854.016.html

2017-04-23. 網絡出版日期：2017-07-03.

國家自然科學基金項目(61572082, 61673396, 61473111，61363056)；遼寧省教育廳項目(LZ2016003)；遼寧省自然科學基金項目(2014020142)；遼寧省高校創新團隊計劃項目(LT2014024).

王長忠.E-mail：changzhongwang@126.com.

TP391；TP274

A

1673-4785(2017)03-0371-06

馮丹，女，1977年生，高級工程師，主要研究方向為計算機信息管理、數據挖掘。已發表學術論文10余篇。

黃洋，女，1994年生，碩士研究生，主要研究方向為粒計算與數據挖掘。

石云鵬，男，1994年生，碩士研究生，主要研究方向為粒計算與數據挖掘。