王長寶，楊習(xí)貝，2，竇慧莉，陳向堅(jiān)，王平心

1.江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇鎮(zhèn)江212003

2.南京理工大學(xué)經(jīng)濟(jì)管理學(xué)院，南京210094

3.江蘇科技大學(xué)數(shù)理學(xué)院，江蘇鎮(zhèn)江212003

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

王長寶1，楊習(xí)貝1，2，竇慧莉1，陳向堅(jiān)1，王平心3

1.江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇鎮(zhèn)江212003

2.南京理工大學(xué)經(jīng)濟(jì)管理學(xué)院，南京210094

3.江蘇科技大學(xué)數(shù)理學(xué)院，江蘇鎮(zhèn)江212003

CNKI網(wǎng)絡(luò)出版：2017-02-28,http://kns.cnki.net/kcms/detail/11.2127.TP.20170228.1820.002.html

1 引言

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

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

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

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

2 鄰域粗糙集

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

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

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

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

3 屬性約簡

3.1 全局和局部約簡

屬性約簡是粗糙集理論的核心研究內(nèi)容。因?yàn)樵诜诸悓W(xué)習(xí)研究中，往往期望通過刪除冗余的屬性或特征以得到較高的分類精度，所以文獻(xiàn)[6]在鄰域決策錯(cuò)誤率的基礎(chǔ)上，提出了用以降低鄰域決策錯(cuò)誤率的屬性約簡定義。

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

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

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

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

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

3.2 啟發(fā)式算法

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

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

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

算法1啟發(fā)式算法求解全局約簡

輸入：決策信息系統(tǒng)DS。

輸出：一個(gè)全局約簡red。

步驟1利用交叉驗(yàn)證計(jì)算ErrorAT；

步驟2令

步驟3若Errorred≤ErrorAT，則轉(zhuǎn)步驟4，否則執(zhí)行以下循環(huán)；

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

（3）利用交叉驗(yàn)證計(jì)算Errorred；

步驟4輸出red。

算法2啟發(fā)式算法求解局部約簡

輸入：決策信息系統(tǒng)DS，類別標(biāo)記i。

輸出：一個(gè)針對第i類標(biāo)記的局部約簡red。

步驟1利用交叉驗(yàn)證計(jì)算

步驟2令

步驟3若則轉(zhuǎn)步驟4，否則執(zhí)行以下循環(huán)；

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

步驟4輸出red。

4 實(shí)驗(yàn)分析

為了對比全局約簡及局部約簡對于分類性能所產(chǎn)生的影響以及驗(yàn)證筆者所提出局部約簡的有效性，選取了8組UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析，數(shù)據(jù)信息的基本描述如表1所列。實(shí)驗(yàn)環(huán)境為PC機(jī)，雙核2.60 GHz CPU，16 GB內(nèi)存，Windows10操作系統(tǒng)，MATLAB R2010a實(shí)驗(yàn)平臺。

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

表1 數(shù)據(jù)集描述

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

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

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

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

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

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

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

5 結(jié)束語

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

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

表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] 胡清華，于達(dá)仁.應(yīng)用粗糙計(jì)算[M].北京：科學(xué)出版社，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，F(xiàn)uzziness and Knowledge-Based Systems，2012，20（3）：399-419.

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

[15] 張維，苗奪謙，高燦，等.鄰域粗糙協(xié)同分類模型[J].計(jì)算機(jī)研究與發(fā)展，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] 朱鵬飛，胡清華，于達(dá)仁.基于隨機(jī)化屬性選擇和鄰域覆蓋約簡的集成學(xué)習(xí)[J].電子學(xué)報(bào)，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] 王宇，楊志榮，楊習(xí)貝.決策粗糙集屬性約簡：一種局部視角方法[J].南京理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2016，40：444-449.

[20] 楊習(xí)貝，徐蘇平，戚湧，等.基于多特征空間的粗糙數(shù)據(jù)分析方法[J].江蘇科技大學(xué)學(xué)報(bào)：自然科學(xué)版，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

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

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

2016-10-11

2016-12-01

1002-8331（2018）06-0095-05

A

TP18

10.3778/j.issn.1002-8331.1610-0109

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

王長寶（1963—），男，實(shí)驗(yàn)師，主要研究方向?yàn)橹悄苄畔⑻幚恚粭盍?xí)貝（1980—），通訊作者，男，博士（后），副教授，主要研究方向?yàn)榇植诩碚?、粒?jì)算、機(jī)器學(xué)習(xí)，E-mail：zhenjiangyangxibei@163.com。