鄰域決策的隨機約簡與集成分類研究

余思成，楊習貝，2，陳向堅，竇慧莉，王平心

1(江蘇科技大學 計算機學院，江蘇 鎮江 212003)

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

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

1 引 言

為了使得粗糙集[1]方法能夠處理連續型數據以及混合型數據，Hu等人提出了鄰域粗糙集的概念[2，3].鄰域粗糙集以其簡單直觀的建模手段且靈活的尺度表示方式，受到了眾多學者的廣泛關注，近年來相關領域研究取得了豐碩的成果[4-11].

在鄰域粗糙集理論中，鄰域決策錯誤率是一個重要的概念[12].所謂鄰域決策錯誤率，實際上是借助留一驗證的技術，描述鄰域分類器在樣本集中發生錯誤判斷的程度.與傳統粗糙集方法中基于近似質量、條件熵等約簡形式[13-16]不同，鄰域決策錯誤率為從分類學習的視角研究屬性約簡問題提供了一種度量標準.利用基于鄰域決策錯誤率的屬性約簡，可以獲得使得鄰域決策錯誤率能夠被降低的屬性子集.然而利用啟發式算法求解基于鄰域決策錯誤率的約簡，得到的僅僅是一個局部最優屬性子集，考慮到樣本集中可能存在多個滿足鄰域決策錯誤率降低這一約束條件的屬性子集，因此可以借助集成的思想來研究鄰域分類問題，其目的是期望充分利用多個約簡所提供的信息，提升鄰域分類器的性能.

集成學習的初衷是把若干個基分類器的分類結果通過一定的方法融合起來，從而取得比單個基分類器更好的性能[17-19].文獻[20]的研究表明集成分類器取得良好效果的一個關鍵在于基分類器的差異性，因而如何獲取具有較大差異的基分類器已然成為集成學習研究中的一個熱點問題.傳統的集成學習通常利用Bagging[21-23]，Boosting[24-26]等調整樣本的方法來獲得有差異性的基分類器.此外亦可以從屬性的角度出發，通過抽取不同的屬性子集分別加以訓練，其目的是獲得基于不同屬性空間下的一組基分類器[27].顯然，后者與粗糙集理論中屬性約簡問題是有著密切關聯的，若能充分利用多個不同約簡所提供的信息，則將有助于在粗糙集理論中使用集成策略以提升學習性能.鑒于此，筆者首先設計了一種基于鄰域決策錯誤率的隨機屬性約簡算法，利用該算法可以從原始屬性集中提取多個滿足鄰域決策錯誤率降低這一約束條件的屬性子集，其次利用這些屬性子集構造一組鄰域分類器，最后通過對測試樣本在這些分類器上給出的類標記投票得到最終的分類結果.由于隨機約簡方法[28]可以獲取多個屬性子集，因此包含了比單個屬性子集更充分的信息，從而可以對鄰域分類器的性能產生正面影響.

2 鄰域分類器與鄰域決策錯誤率

鄰域粗糙集是Hu等人[2，3]提出的一種擴展粗糙集模型，它提升了粗糙集理論對于數值型數據的處理能力.鄰域粗糙集的處理對象依然是一個決策系統DS=(U，AT∪D)，其中U是所有樣本構成的集合，稱其為論域，AT是所有條件屬性的集合，D是決策屬性，U/IND(D)={X1,X2,…，Xn}表示根據決策屬性D所誘導的論域上的劃分.

定義1[2]. 稱二元組是一個非空度量空間，?x∈U，?σ>0，稱點集δ(x)={y|δ(x,y)≤σ,y∈U}為x的σ鄰域.其中δ(x,y)為距離函數，若δ(x，y)為歐氏距離，則σ鄰域為以x為中心為半徑的超球體，此時σ亦可稱為鄰域半徑.

在決策系統中，借助鄰域的概念，可以構造鄰域分類器[3]如算法1所示：

算法1. 鄰域分類器

輸入：決策系統DS=(U,AT∪D)，測試樣本y，鄰域半徑σ.

輸出：測試樣本類標記L(y).

步驟1. ?x∈U，計算δ(y,x)；

步驟2. 計算δ(y)；

步驟4.Xj=arg max{Pr(Xi,δ(y)):?Xi∈U/IND(D)}；

步驟5.L(y)=j，輸出L(y).

在利用鄰域分類器進行分類學習的基礎上，Hu等人進一步提出了鄰域決策錯誤率(NDER)的概念[12].其核心思想是利用留一驗證得到鄰域分類器在U中的分類錯誤率，這個分類錯誤率即是鄰域決策錯誤率.

定義2. 給定一個決策系統DS=(U,AT∪D)，其鄰域決策錯誤率為：

(1)

其中L(x)為鄰域分類器輸出的類標記，D(x)是x的真實類標記.

由定義2可以看出，鄰域決策錯誤率是樣本集中鄰域分類器發生錯誤判斷的程度.

3 鄰域決策錯誤率隨機約簡

利用鄰域決策錯誤率，Hu等人給出了相應的屬性約簡描述[12].

定義3. 給定一個決策系統DS=(U，AT∪D)，?A?AT，A被稱為一個鄰域決策錯誤率約簡(NDERR)，當且僅當NDERA≤NDERAT，且對于任意B?A，都有NDERB>NDERAT.

大家都知道的，當年美國總統尼克松訪華時用的那雙筷子，現在值多少錢了？十萬不止。但也不是所有的附加上的東西都值錢，一張宣紙，齊白石在上面涂了幾筆，這張紙就值大錢了。同樣一張宣紙，隔壁張三抹了幾筆，這張紙就廢了。同樣是幾筆，差距咋就這樣大呢？在于附加值。附加值有正數，也有負數。

由上述定義可以看出，利用鄰域決策錯誤率的概念定義約簡，其目的是使鄰域分類器對約簡后的樣本集發生錯誤判斷的程度降低.

在粗糙集理論中，貪心算法是求解約簡的典型方法，若將鄰域決策錯誤率降低作為約簡條件，則通過貪心策略也可以求得一個局部最優屬性子集[12].然而實際數據中可能存在多個滿足鄰域決策錯誤率降低這一約束條件的屬性子集.為了獲取并盡可能利用這些屬性子集所提供的信息，需要通過恰當的途徑求解盡可能多的滿足條件的屬性子集.文獻[27]提出了一種基于鄰域隨機約簡的方法：該方法放寬了貪心策略每一步選擇最佳屬性的要求，而采用隨機選取前F個最佳屬性中的一個添加到約簡中，多次執行算法可以得到多個滿足約簡約束條件并且有一定差異的屬性子集.將鄰域決策錯誤率約簡與鄰域隨機約簡的方法結合，可以設計一種基于鄰域決策錯誤率的隨機屬性約簡方法如算法2所示.

算法2. 基于鄰域決策錯誤率的隨機屬性約簡

輸入：鄰域決策系統DS=(U,AT∪D)，鄰域半徑σ，隨機參數F.

輸出：一個鄰域隨機約簡red.

步驟1.red=?；

步驟2. 計算NDERAT

步驟3. 若AT-red=?則轉至步驟 8；

步驟4. ?a∈AT-red，計算NDER[a]∪red，并按照NDER[a]∪red值從小到大排序記為a1，a2，…，an；

步驟5. 從a1，a2，…，an的前F個，即a1，a2，…，aF中隨機選取一個記為ak；

步驟6.red=red∪{ak}；

步驟7. 若NDERred>NDERAT則轉至步驟3；

步驟8. 輸出red.

基于鄰域決策錯誤率的隨機屬性約簡算法經過多次運行，即可得到多個滿足鄰域決策錯誤率降低這一約束條件并且有一定差異的屬性子集.

4 鄰域分類器集成

利用鄰域決策錯誤率隨機約簡，可以得到多個有一定差異的屬性子集，通過這些屬性子集可以構造多個鄰域分類器，對給定的新樣本在不同的鄰域分類器上可能得到不同的類別，通過投票的方式對這些鄰域分類結果加以集成，得到最終的輸出類別，從而達到利用不同屬性子集進行分類的目的.圖1給出了一種借助鄰域決策錯誤率隨機約簡獲得多個屬性子集并利用鄰域分類器進行集成分類的方法.

圖1 NDER隨機約簡分類策略Fig.1 NDER based randomized reduction and neighborhood classification strategy

由圖1可以看出，基于NDER隨機約簡的鄰域分類方案能夠在滿足鄰域決策錯誤率降低這一約束條件的多個屬性子集上產生多個分類結果，并對所得的結果進行投票，有望獲得比單個屬性子集更高的分類性能.同時該方案可以采用并行計算的方法進行優化，從而降低時間消耗.

5 實驗分析

為了驗證基于NDER隨機約簡集成算法的有效性，選取了12組UCI數據進行實驗分析.數據集基本信息如表1所示.

實驗環境為PC機，雙核1.10GHz CPU，8G內存，windows10 操作系統 ，matlab R2012a 實驗平臺.

在本組實驗中，設置隨機屬性約簡的隨機參數F=3，求得鄰域決策錯誤率降低的屬性子集數量為40個，即用40個基分類器集成(采用鄰域分類器)，并使用Kappa統計量[28，29]描述分類結果的一致性，選取了十個不同的鄰域半徑參數值，分別是0.05，0.1，… ，0.5.圖2給出了上述12個數據集在十折交叉驗證下，原始數據下的分類精度，利用傳統啟發式算法求鄰域決策錯誤率約簡(NDERR)得到的分類精度、鄰域決策的一致性度量，利用鄰域決策錯誤率隨機約簡集成(ELNDERR)的分類精度、鄰域決策的一致性度量.

表1 數據集描述Table 1 Data sets description

圖2 分類精度及一致性在不同約簡下的對比Fig.2 Comparisons for classification accuracies and agreements among different reducts

從實驗數據中可以看出，在絕大多數半徑下，利用ELNDERR得到的分類結果，分類精度和分類結果的一致性都明顯優于利用NDERR得到的結果，這表明ELNDERR方法從分類精度和魯棒性兩方面上對鄰域分類器的性能有提升作用.此外，個別半徑下約簡后的鄰域分類器分類精度低于原始屬性的分類精度，例如，Seeds數據集在鄰域半徑參數0.25和0.3下原始屬性的分類精度高于屬性約簡后的分類精度，又如Wine數據集在鄰域半徑參數0.15下原始屬性的分類精度也高于屬性約簡后的分類精度，這主要是因為文中屬性約簡的目的是提高鄰域決策的留一驗證精度，而非十折交叉驗證的精度.

6 結 論

鄰域決策錯誤率約簡，求取的是滿足鄰域決策錯誤率降低這一約束條件的屬性子集，目的是通過降低鄰域分類器的發生錯誤判斷的程度提升鄰域分類器的性能.通過構造基于鄰域決策錯誤率的隨機屬性約簡算法，利用求解得到的多個約簡形成基分類器，對分類結果進行投票集成，旨在進一步提升鄰域分類器性能.實驗表明，在絕大多數半徑下，基于鄰域決策錯誤率隨機約簡的集成分類方法可以有效地提高鄰域分類器的分類精度和分類魯棒性.

在本文工作的基礎上，筆者將就以下工作進行深入探討：

1)提高約簡效率，尋求更高效快速的求解算法；

2)利用鄰域半徑變化構造基分類器的集成策略；

3)基于隨機屬性約簡的選擇性集成方法.

：

[1] Pawlak Z.Rough set[J].International Journal of Computer & Information Sciences，1982，11(5)：341-356.

[2] Hu Q，Yu D，Liu J，et al.Neighborhood rough set based heterogeneous feature subset selection[J].Information Sciences，2008，178(18)：3577-3594.

[3] Hu Q，Yu D，Xie Z.Neighborhood classifiers[J].Expert Systems with Applications，2008，34(2)：866-876.

[4] Chen H，Li T，Cai Y，et al.Parallel attribute reduction in dominance-based neighborhood rough set[J].Information Sciences，2016，373：351-368.

[5] Lin Y，Li J，Lin P，et al.Feature selection via neighborhood multi-granulation fusion[J].Knowledge-Based Systems，2014，67(3)：162-168.

[6] Liu Y，Huang W，Jiang Y，et al.Quick attribute reduct algorithm for neighborhood rough set model[J].Information Sciences，2014，271(7)：65-81.

[7] Xu J，Xu T，Sun L，et al.An efficient gene selection technique based on fuzzy C-means and neighborhood rough set[J].Applied Mathematics & Information Sciences，2014，8(6)：3101-3110.

[8] Yang X，Zhang M，Dou H，et al.Neighborhood systems-based rough sets in incomplete information system[J].Knowledge-Based Systems，2011，24(6)：858-867.

[9] Bao Li-na，Ding Shi-fei，Xu Xin-zheng，et al.Extreme-learning machine algorithm based on neighborhood rough sets[J].Journal of University of Jinan，2015，29(5)：367-371.

[10] Tang Chao-hui，Chen Yu-ming.Neighborhood system uncertainty measurement approaches.[J].Control & Decision，2014，29(4)：691-695.

[11] Zhang Wei，Miao Duo-qian，Gao Can，et al.A neighborhood rough sets-based Co-training model for classification[J].Journal of Computer Research & Development，2014，51(8)：1811-1820.

[12] Hu Q，Pedrycz W，Yu D，et al.Selecting discrete and continuous features based on neighborhood decision error minimization[J].IEEE Transactions on Systems，Man，and Cybernetics-Part B：Cybernetics，2010，40(1)：137-150.

[13] Duan Jie，Hu Qing-hua，Zhang Ling-jun，et al.Feature selection for multi-label classification based on neighborhood rough sets[J].Journal of Computer Research & Development，2015，52(1)：56-65.

[14] Liang Hai-long，Xie Jun，Xu Xing-ying，et al.New attribute reduction algorithm of neighborhood rough set based on distinguished object set[J].Journal of Computer Applications，2015，35(8)：2366-2370.

[15] Jia H，Ding S，Ma H，et al.Spectral clustering with neighborhood attribute reduction based on information entropy[J].Journal of Computers，2014，9(6)：1316-1324.

[16] Yang Xi-bei，Xu Su-ping，Qi Yong，et al.Rough data analysis method based on multi feature space[J].Journal of Jiangsu University of Science and Technology (Natural Science Edition)，2016，30(4)：370-373.

[17] Li Y，Si J，Zhou G，et al.FREL：a stable feature selection algorithm[J].IEEE Transactions on Neural Networks & Learning Systems，2014，26(7)：1388-1402.

[18] Wang X，Xing H，Li Y，et al.A study on relationship between generalization abilities and fuzziness of base classifiers in ensemble learning[J].IEEE Transactions on Fuzzy Systems，2014，23(5)：1638-1654.

[19] Sun Bo，Wang Jian-dong，Chen Hai-yan，et al.Diversity measures in ensemble learning[J].Control & Decision，2014，29(3)：385-395.

[20] Zhou Z，Yu Y.Ensembling local learners through multimodal perturbation[J].IEEE Transactions on Systems，Man，and Cybernetics-Part B：Cybernetics，2005，35(4)：725-735.

[22] Breiman L.Bagging predictors[J].Machine Learning，1996，24(2)：123-140.

[23] Bi Kai，Wang Xiao-dan，Yao Xu，et al.Adaptively selective ensemble algorithm based on bagging and confusion matrix[J].Acta Electronica Sinica，2014，42(4)：711-716.

[24] Korytkowski M，Rutkowski L，Scherer R.Fast image classification by boosting fuzzy classifiers[J].Information Sciences，2016，327：175-182.

[25] Schapire R E.The strength of weak learnability[J].Machine Learning，1990，5(2)：28-33.

[26] Trzcinski T，Christoudias M，Lepetit V.Learning image descriptors with boosting[J].IEEE Transactions on Pattern Analysis & Machine Intelligence，2015，37(3)：597-606.

[27] Valentini G，Masulli F.Ensembles of learning machines[M].Neural Nets，Springer Berlin Heidelberg，2002.

[28] Zhu Peng-fei，Hu Qing-hua，Yu Da-ren.Ensemble learning based on randomized attribute selection and neighborhood covering reduction[J].Acta Electronica Sinica，2012，40(2)：273-279.

[29] Sim J，Wright C C.The Kappa statistic in reliability studies：use，interpretation，and sample size requirements[J].Physical Therapy，2005，85(3)：257-268.

[30] Yang Chun，Yin Xu-cheng，Hao Hong-wei，et al.Classfier ensemble with diversity：effectiveness analysis and ensemble optimization[J].Acta Automatica Sinica，2014，40(4)：660-674.

附中文參考文獻：

[9] 鮑麗娜，丁世飛，許新征，等.基于鄰域粗糙集的極速學習機算法[J].濟南大學學報自然科學版，2015，29(5)：367-371.

[10] 唐朝輝，陳玉明.鄰域系統的不確定性度量方法[J].控制與決策，2014，29(4)：691-695.

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

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

[14] 梁海龍，謝 珺，續欣瑩，等.新的基于區分對象集的鄰域粗糙集屬性約簡算法[J].計算機應用，2015，35(8)：2366-2370.

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

[19] 孫 博，王建東，陳海燕，等.集成學習中的多樣性度量[J].控制與決策，2014,29(3)：385-395.

[23] 畢 凱，王曉丹，姚 旭，等.一種基于Bagging和混淆矩陣的自適應選擇性集成[J].電子學報，2014，42(4)：711-716.

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

[30] 楊 春，殷緒成，郝紅衛，等.基于差異性的分類器集成：有效性分析及優化集成[J].自動化學報，2014，40(4)：660-674.