鄰域決策錯誤率的局部約簡方法研究

王長寶，楊習貝，2，竇慧莉，陳向堅，王平心

1.江蘇科技大學計算機科學與工程學院，江蘇鎮江212003

2.南京理工大學經濟管理學院，南京210094

3.江蘇科技大學數理學院，江蘇鎮江212003

鄰域決策錯誤率的局部約簡方法研究

王長寶1，楊習貝1，2，竇慧莉1，陳向堅1，王平心3

1.江蘇科技大學計算機科學與工程學院，江蘇鎮江212003

2.南京理工大學經濟管理學院，南京210094

3.江蘇科技大學數理學院，江蘇鎮江212003

CNKI網絡出版：2017-02-28,http://kns.cnki.net/kcms/detail/11.2127.TP.20170228.1820.002.html

1 引言

眾所周知，粗糙集[1-2]從數據自身出發，不依賴于其他先驗知識，利用下、上近似集之差所刻畫的邊界區域來描述不確定性。經典粗糙集是建立在等價關系基礎上的，可被用于處理符號型數據。但現實世界中廣泛存在著類型復雜、結構迥異的數據[3-6]，鑒于此，為了將粗糙集推向實用，已有很多學者提出了諸如模糊粗糙集[7]、鄰域粗糙集[8]、決策粗糙集[9]、多粒度粗糙集[10]等擴展模型。

在眾多的擴展粗糙集模型中，關于鄰域粗糙集理論與方法的研究近年來得到了眾多學者的廣泛關注[6，8，11-15]。鄰域粗糙集借助距離的概念構建鄰域信息粒，其主要特點表現在：（1）因為使用了距離技術，所以鄰域粗糙集既可以用來分析連續型數據，也可以用于處理連續和符號型并存的混合數據；（2）利用半徑來控制鄰域信息粒的大小，隨著半徑的變化，鄰域信息粒的大小亦隨之變化，因而勢必引起諸如近似集、不確定性度量等相關變化，從而自然地形成了一個多粒度[12，16]動態變化趨勢。

無論研究何種粗糙集方法，屬性約簡都是一個核心內容，各類研究的區別在于不同的粗糙集可能會產生不同的度量標準，因而可以給出不同的屬性約簡定義。在鄰域粗糙集的理論研究中，除了可以探討關于近似質量、條件熵、近似分布等經典粗糙集下的約簡形式，亦可從分類學習的視角研究屬性約簡：例如Hu等人[4]將鄰域分類器與近鄰分類器的性能進行了對比分析，驗證了鄰域分類相比于近鄰分類的優勢，并在此基礎上，給出了基于鄰域決策錯誤率的約簡定義[6]；朱鵬飛等人[17]依據集成學習理論，通過隨機化鄰域約簡，產生一簇分類學習規則，并且驗證了該方法具有較強的魯棒性。

經過梳理與分析，不難發現以往關于鄰域粗糙集約簡的研究大多是從全局的角度來考慮問題的，如基于鄰域決策錯誤率所設計的約簡，其目的就是為了提升鄰域分類模型的總體分類精度。但值得注意的是，這一理念往往會帶來局部信息的丟失，如造成單個類別的分類精度提升程度不足，甚至是分類精度有所降低。為解決這一問題，筆者在文獻[18-19]所示工作的基礎上，從單個類別標記[20]的視角，定義了局部鄰域決策錯誤率及相應的屬性約簡概念，并給出了求解局部鄰域決策錯誤率約簡的算法。

2 鄰域粗糙集

類似于經典粗糙集方法，鄰域粗糙集的處理對象依然可以表示為信息系統。不失一般性，一個決策信息系統可以記為一個二元組DS=＜U,AT?{}d＞，其中U是論域，表示一個非空有限的對象集合；AT描述了所有條件屬性集合，而d是決策屬性且滿足AT?{}d=?。

在決策信息DS中，Δ:U×U→R為一距離度量函數，?x,y∈U,Δ(x,y)表示對象x與y之間的距離。若假定鄰域半徑為σ，則可以定義如下所示的0-1函數：

函數f(x,y)用以判斷x與y之間的距離是否大于給定半徑σ，據此，對于決策信息系統中的任意對象x，不難得到的鄰域鄰域系統是決策信息系統中所有對象的鄰域所構成的集合。記錄了所有與x之間的距離小于給定半徑σ的對象，可以認為是所有與x在半徑σ下相似的對象集合，以粒計算的視角來看，是一種信息粒的表現形式，因而也可稱為鄰域信息粒。顯然，若則有成立，也就是說半徑越大，鄰域中所包含的對象也越多。利用鄰域信息粒，可構建如下所示的近似集。

定義1[4]令DS=＜U,AT?{}d＞為一決策信息系統，?A?AT，根據屬性集合A可得到距離度量ΔA，?X?U,X的鄰域下近似集與上近似集分別定義如下：

3 屬性約簡

3.1 全局和局部約簡

屬性約簡是粗糙集理論的核心研究內容。因為在分類學習研究中，往往期望通過刪除冗余的屬性或特征以得到較高的分類精度，所以文獻[6]在鄰域決策錯誤率的基礎上，提出了用以降低鄰域決策錯誤率的屬性約簡定義。

定義2[6]令DS=＜U,AT?{}d＞為一決策信息系統，，A被稱為一個鄰域錯誤分類率約簡當且僅當：

由定義2可以看出，基于鄰域決策錯誤率的約簡實際上是使得決策信息系統中鄰域決策錯誤率能夠被降低的最小屬性子集。值得注意的是，定義2所示約簡考慮的是U中所有對象被錯誤分類的程度，從而忽視了數據中各個類別的分類情況。如果僅僅追求式（3）所示的鄰域決策錯誤率降低，那么有可能造成某些類中對象被錯分的可能性增加。所以一種合理的考慮應該是將每一類別的決策錯誤率單獨分析，由此可以定義如下所示公式：

公式（4）描述的是在決策信息系統中，第i類對象的鄰域決策錯誤率，即第i類對象中被錯分的百分比，這是一種基于類別標記的局部錯誤率。借助公式（4），可以定義如下所示的局部約簡。

定義3令DS=＜U,AT?{}d＞為一決策信息系統，?A?AT，針對第i個類別標記，A被稱為一個局部鄰域決策錯誤率約簡當且僅當：

定義3所示約簡，其目的不是為了降低由全體對象所得到的鄰域決策錯誤率，而是為了降低具有第i類標記的對象的鄰域決策錯誤率，這是一種局部約簡的定義形式，與此對應的，定義2所示的約簡可稱為全局約簡。

3.2 啟發式算法

示將屬性a加入到條件屬性集A中后鄰域決策錯誤率的變化情況，即：

式（5）所示的屬性重要度是針對由全體對象所得到的鄰域決策錯誤率而設計的，是一種全局重要度，類似地，針對第i個類別標記，可以給出如下所示的局部屬性重要度Sig()a,A,i：

根據上述屬性重要度的定義，不難給出如下所示的兩個啟發式算法，分別用于求解定義2和定義3所示的約簡。

算法1啟發式算法求解全局約簡

輸入：決策信息系統DS。

輸出：一個全局約簡red。

步驟1利用交叉驗證計算ErrorAT；

步驟2令

步驟3若Errorred≤ErrorAT，則轉步驟4，否則執行以下循環；

（1）?a∈AT-red，計算屬性a的重要度Sig()a,red；

（3）利用交叉驗證計算Errorred；

步驟4輸出red。

算法2啟發式算法求解局部約簡

輸入：決策信息系統DS，類別標記i。

輸出：一個針對第i類標記的局部約簡red。

步驟1利用交叉驗證計算

步驟2令

步驟3若則轉步驟4，否則執行以下循環；

（1）?a∈AT-red，計算屬性a的重要度Sig()a,red,i；

步驟4輸出red。

4 實驗分析

為了對比全局約簡及局部約簡對于分類性能所產生的影響以及驗證筆者所提出局部約簡的有效性，選取了8組UCI數據集進行實驗分析，數據信息的基本描述如表1所列。實驗環境為PC機，雙核2.60 GHz CPU，16 GB內存，Windows10操作系統，MATLAB R2010a實驗平臺。

在算法1和算法2中計算鄰域所采用的距離度量為歐式距離，計算鄰域決策錯誤率時均采用了十倍交叉驗證。表2列出了鄰域分類器在各個類別標記上所求得的分類精度，這些分類精度分別是在原始數據、根據算法1所求得的全局約簡和根據算法2所求得局部約簡的基礎上，利用十倍交叉驗證方式求得。受篇幅所限，鄰域的大小σ選取了3個不同的參數，分別是0.1、0.2和0.3。

表1 數據集描述

觀察表2可以發現，在絕大多數的類別標記上，相較于原始數據和全局約簡來說，利用局部約簡所求得的屬性子集可以獲得較高的分類精度。除此以外，局部約簡還能夠在一定程度上緩解由全局約簡引起的某一類別精度下降問題。例如，考慮Forest數據集的類別X1，當σ=0.1時，原始數據下該類別的分類精度為0.936 8，而根據全局約簡，該類別的分類精度僅為0.883 0，明顯低于原始精度，利用局部約簡，分類精度可以提升至0.995 7。每一個數據集都有至少一個類別標記出現了類似的情形，這反映了全局約簡對于單個類別上的分類性能提升存在不盡人意之處；而相較于全局約簡來說，局部約簡所追求的目標是使得單個類別的分類精度盡可能地有所提高，故具有良好的表現力。

進一步的，圖1展示了不同σ參數下根據全局約簡得到的總體分類精度、各類別分類精度的平均值以及根據局部約簡得到的各類別分類精度平均值。

通過觀察圖1，不難得出如下結論。

（1）在各個鄰域半徑σ下，相較于原始數據，根據全局約簡所得到的總體分類精度能夠有所提升，這符合定義2中全局約簡的追求目標。

（2）根據全局約簡所得到各類別分類精度均值的提升效果不夠明顯，有時甚至低于原始數據下各類別分類精度的均值，如Contraceptive Method數據中當σ=0.1至σ=0.5都出現了這一情形，這說明全局約簡在針對單獨某一類別時性能有所欠缺。

（3）根據局部約簡所得到的各類別分類精度均值要高于由原始數據和全局約簡所得到的各類別分類精度的均值，這一結果說明了在提升局部分類效果時，局部約簡相比于全局約簡來說，具有更為明顯的優勢。

圖1 鄰域分類器的類別精度和總體精度

5 結束語

針對基于鄰域決策錯誤率的屬性約簡僅考慮提升數據的總體分類精度而忽視了對具體類別分類精度的考慮這一不足之處，引入了基于局部鄰域決策錯誤率的屬性約簡，并利用啟發式算法求解這種局部約簡。與傳統全局約簡的側重點不同，局部約簡更加關注如何對某一具體類別的分類效果進行提升，從而有助于解決由全局約簡所引起的局部精度提升不足甚至下降的問題。

本文僅僅考慮了如何利用約簡提升局部鄰域粗糙分類器的分類精度，而沒有對約簡本身的性能進行分析，筆者下一步將就局部約簡的魯棒性問題進行進一步的探討，以期能夠進一步完善局部屬性約簡理論與方法。

表2 鄰域分類器分類精度對比

[1] Pawlak Z.Rough sets-theoretical aspects of reasoning about data[M].Dordrecht，Boston，London：Kluwer Academic Publishers，1991.

[2] Pawlak Z.Rough sets[J].International Journal of Computer&Information Sciences，1982，11（5）：341-356.

[3] Zhang X，Mei C L，Chen D G，et al.Feature selection in mixed data：A method using a novel fuzzy rough setbased information entropy[J].Pattern Recognition，2016，56：1-15.

[4] Hu Q H，Zhang L，Zhang D，et al.Measuring relevance between discrete and continuous features based on neighborhood mutual information[J].Expert System with Applications，2011，38：10737-10750.

[5] Wang X，Tsang E C C，Zhao S，et al.Learning fuzzy rules from fuzzy samples based on rough set technique[J].Information Sciences，2007，177（20）：4493-4514.

[6] Hu Q H，Pedrycz W，Yu D R，et al.Selecting discrete and continuous features based on neighborhood decisionerrorminimization[J].IEEETransactionsonSystems，Man，and Cybernetics，Part B，2010，40：137-150.

[7] Dubois D，Prade H.Rough fuzzy sets and fuzzy rough sets[J].International Journal of General Systems，1990，17：191-209.

[8] 胡清華，于達仁.應用粗糙計算[M].北京：科學出版社，2012.

[9] Yao Y Y.Three-wang decisions and cognitive computing[J].Cognitive Computing，2016，8：543-554.

[10] Liang J Y，Wang F，Dang C Y，et al.An efficient rough feature selection algorithm with a multi-granulation view[J].InternationalJournalof ApproximateReasoning，2012，53：912-926.

[11] Lin Y J，Hu Q H，Liu J H，et al.Multi-label feature selection based on neighborhood mutual information[J].Applied Soft Computing，2016，38：244-256.

[12] Zhu P F，Hu Q H，Zuo W M，et al.Multi-granularity distance metric learning via neighborhood granule margin maximization[J].Information Sciences，2014，282：321-331.

[13] Yang X B，Chen Z H，Dou H L，et al.Neighborhood system based rough set：Models and attribute reductions[J].International Journal of Uncertainty，Fuzziness and Knowledge-Based Systems，2012，20（3）：399-419.

[14] 段潔，胡清華，張靈均，等.基于鄰域粗糙集的多標記分類特征選擇算法[J].計算機研究與發展，2015，52：56-65.

[15] 張維，苗奪謙，高燦，等.鄰域粗糙協同分類模型[J].計算機研究與發展，2014，51：1811-1820.

[16] Yang X B，Qian Y H，Yang J Y.Hierarchical structures on multigranulation spaces[J].Journal of Computer Science and Technology，2012，27：1169-1183.

[17] 朱鵬飛，胡清華，于達仁.基于隨機化屬性選擇和鄰域覆蓋約簡的集成學習[J].電子學報，2012，40：273-279.

[18] Chen D G，Zhao S Y.Local reduction of decision system with fuzzy rough sets[J].Fuzzy Sets and Systems，2010，161：1871-1883.

[19] 王宇，楊志榮，楊習貝.決策粗糙集屬性約簡：一種局部視角方法[J].南京理工大學學報：自然科學版，2016，40：444-449.

[20] 楊習貝，徐蘇平，戚湧，等.基于多特征空間的粗糙數據分析方法[J].江蘇科技大學學報：自然科學版，2016，30：370-373.

[21] Wu X D，Kumar V，Quinlan J R，et al.Top 10 algorithmsindatamining[J].KnowledgeandInformation Systems，2008，14（1）：1-37.

WANG Changbao,YANG Xibei,DOU Huili,et al.Research on local attribute reduction approach via neighborhood decision error rate.Computer Engineering and Applications,2018,54（6）：95-99.

WANG Changbao1,YANG Xibei1，2,DOU Huili1,CHEN Xiangjian1,WANG Pingxin3

1.School of Computer Science and Engineering,Jiangsu University of Science and Technology,Zhenjiang,Jiangsu 212003,China
2.School of Economics&Management,Nanjing University of Science and Technology,Nanjing 210094,China
3.School of Mathematics and Physics,Jiangsu University of Science and Technology,Zhenjiang,Jiangsu 212003,China

Traditional criteria of attribute reduction for neighborhood decision error rate is designed for improving overall classification accuracy,it does not take the variation of accuracy of each class into consideration when reduction finding is executed.From this point of view,the concepts of local neighborhood decision error rate and local attribute reduction are introduced for improving the classification accuracy of single class.Furthermore,a heuristic algorithm to compute local neighborhood decision error rate based reduction is presented.The experimental results on 8 UCI data sets show that the local reduction can not only improve the classification accuracy of single class,but also overcome the limitation of accuracy’s decreasing for single class,which may be caused by global reduction.

attribute reduction;global reduction;heuristic algorithm;local reduction;neighborhood rough set

傳統基于鄰域決策錯誤率的屬性約簡準則是針對總體分類精度的提升而設計的，未能展現因約簡而引起的各類別精度變化情況。針對這一問題，引入局部鄰域決策錯誤率以及局部屬性約簡的概念，其目的是提升單個類別的分類精度。在此基礎上，進一步給出了求解局部鄰域決策錯誤率約簡的啟發式算法。在8個UCI數據集上的實驗結果表明，局部約簡不僅是提高各個類別精度的有效技術手段，而且也解決了因全局約簡所引起的局部分類精度下降問題。

屬性約簡；全局約簡；啟發式算法；局部約簡；鄰域粗糙集

2016-10-11

2016-12-01

1002-8331（2018）06-0095-05

A

TP18

10.3778/j.issn.1002-8331.1610-0109

國家自然科學基金（No.61572242，No.6150316，No.62502211）；江蘇省高校哲學社會科學基金（No.2015SJD769）；中國博士后科學基金（No.2014M550293）；江蘇省青藍工程人才項目。

王長寶（1963—），男，實驗師，主要研究方向為智能信息處理；楊習貝（1980—），通訊作者，男，博士（后），副教授，主要研究方向為粗糙集理論、粒計算、機器學習，E-mail：zhenjiangyangxibei@163.com。