基于屬性質量度的變精度鄰域粗糙集屬性約簡

李 冬，蔣 瑜，鮑楊婉瑩

（成都信息工程大學軟件工程學院，四川成都610000）

Pawlak[1]提出的經典粗糙集是一種有效地處理模糊和不確定知識的工具.由于在處理知識系統不需要數據的附加信息或先驗知識，粗糙集在某些領域的應用都取得了不錯的效果[2-5].然而，經典粗糙集對于數值型的數據不能直接處理，需要事先進行離散化，但是離散化后的屬性值由于沒有完整的保留決策表屬性值的差異，導致數據信息的缺失[6]，這就限制了粗糙集的應用范圍.

針對這個問題，Zadeh[7]提出了知識粒化和粒度計算的概念，Lin[8]在知識粒化、粒度計算的基礎上提出了鄰域模型.此后，Hu等[9]將鄰域引入粗糙集，提出了基于鄰域粒化和粗糙逼近的鄰域粗糙集，將其應用到數值型數據的屬性約簡，并且提出一種快速屬性約簡，加快計算正域的速度.自鄰域粗糙集被提出以來，眾多學者也對其相關的改進與應用進行了研究[10-14].

但是，鄰域粗糙集的下近似，只允許樣本嚴格包含，這種苛刻的劃分條件使得鄰域粗糙集對噪聲容忍能力差，對于誤分類的情況過于敏感.此后，Hu等將Ziarko提出的變精度[15]引入鄰域粗糙集，提出了一種變精度鄰域粗糙集[9].

然而，本文發現文獻[9]中變精度鄰域粗糙集，其精度的變化會影響正域的劃分和屬性重要度的可信度，如果以屬性重要度作為度量標準來選擇屬性，可能會將分類能力較差的屬性先歸入約簡集合.針對這個問題，本文定義了屬性質量度，以正域作為度量基礎，鄰域內的平均正確分類率作為正域的質量因子，并提出一種基于正域的增量和平均正確分類率的增率相結合的度量函數，通過實驗分析比較，驗證了算法的有效性.

1 鄰域粗糙集

1.1 鄰域的粒化給定決策信息系統IS=〈U，A，V，f〉，其中：U 是非空有限的對象集合｛x1，x2，…，xn｝；A是非空的有限屬性集合，A=C∪D，C∩D=?，C是條件屬性集，D是決策屬性集；V是值域，表示在屬性集合下的所有可能取值；f：U×A→V是一個映射函數，表示對象與其屬性取值的映射關系.

定義1[9]（δ-鄰域） 給定決策信息系統IS=〈U，A，V，f〉，對于?x∈U，鄰域 δ（x）定義為

其中，Δ是距離函數，且對于?x1，x2，x3∈U，Δ應滿足以下條件：

1）Δ（x1，x2）≥0，當且僅當 x1=x2時等號成立；

2）Δ（x1，x2）=Δ（x2，x1）；

3）Δ（x1，x3）≤Δ（x1，x2）+Δ（x2，x3）.

對于N維的特征空間，距離函數通常用P范數表示

1.2 鄰域決策系統

定義2[9]（鄰域決策系統） 給定非空的有限集合 U=｛x1，x2，…，xn｝，C 是描述 U 的實數型特征集合，D是決策屬性.如果C是生成U上的一族鄰域關系，則稱NDT=〈U，C，D〉為一個鄰域決策系統.

定義3[9]給定鄰域決策系統 NDT=〈U，C，D〉，D 將 U 劃分為 n 個等價類｛X1，X2，…，Xn｝，對于?B?C，決策屬性D關于屬性子集B的上下近似定義為：

其中

則鄰域粗糙集的正域、邊界域和負域依次定義為：

定義4[9]給定鄰域決策系統 NDT=〈U，C，D〉，對于?B?C，決策屬性D對屬性子集B的依賴度定義為

定義5[9]給定鄰域決策系統 NDT=〈U，C，D〉，若有?B?C，?a∈C，但 a?B，a相對于屬性子集B關于決策屬性D的屬性重要度定義為

結合定義4分析可知，屬性重要度取決于依賴度的變化，而依賴度取決于屬性子集所劃分的正域，則屬性重要度可定義為

由定義4和（11）式可得

且｜U｜表示樣本對象總數，所以屬性重要度可定義為（12）式，即表示為正域的增量.

如果 Sig（a，B，D）＞0，說明當添加屬性 a，生成新的屬性子集B∪｛a｝所劃分正域的覆蓋范圍增大，各類的重疊區域減小，就可以依靠這個新的屬性子集，更加準確地進行分類.

2 變精度鄰域粗糙集

2.1 變精度鄰域粗糙集的上下近似

定義6[16]給定鄰域決策系統 NDT=〈U，C，D〉，D 將 U 劃分為 n 個等價類｛X1，X2，…，Xn｝，對于?B?C，引入變精度的正確率閾值β（0.5≤β≤1），定義可變精度β-上近似和下近似為：

其中

由定義6易知，變精度鄰域粗糙集的上下近似是基于β的容錯劃分，允許一定的錯誤分類，β的大小決定了上下近似的樣本覆蓋度.

2.2 變精度鄰域粗糙集的屬性約簡改進

2.2.1 基于屬性重要度的度量方式分析 以往屬性約簡的研究中，大多數是以屬性重要度作為啟發因子的前向搜索算法[9-11，16-18]，其中，基于變精度鄰域粗糙集的屬性約簡也是采用這種思想[9，16]，但是由于變精度的引入，基于屬性重要度的屬性約簡存在一定的弊端.

由定義6可知，變精度鄰域粗糙集以改變閾值β來調整正域的劃分，最終影響約簡結果：變精度閾值β（0.5≤β≤1）越小，正域的劃分條件越放松，正域的覆蓋度也越大，屬性約簡個數越少；變精度閾值β越大，正域的劃分條件越嚴格，正域的覆蓋度也越小，屬性約簡個數越多.對于不同數據集，要取得最優的約簡，往往變精度閾值β取值是不確定的，在實驗過程中需要不停調整閾值β，找到最適合的值，但在此后屬性重要度的計算中，卻忽略了閾值β對正域的影響，所以需要對（11）式屬性重要度進行改進.

總的來說，在文獻[9]的變精度鄰域粗糙集中，對屬性重要度的計算忽略了β對正域的影響，使得屬性重要度的可信度降低，可能導致分類能力差的屬性先劃入約簡集合.所以，如何在引入變精度提高容錯能力，同時又能避免變精度對正域的影響是本文要解決的問題.

2.2.2 一種基于屬性質量度的度量函數 本文在Hu等所提出的屬性重要度[9]基礎上進行改進，將鄰域內平均正確分類率的增率作為屬性重要度的質量因子，定義了屬性質量度，并提出一種基于正域的增量和平均正確分類率的增率相結合的屬性選擇方法，優先選擇分類能力更好的屬性.

定義7給定鄰域決策系統NDT=〈U，C，D〉，若有?B?C，?x∈PosB（D），X∈U/D，且 x∈X，則正域內樣本鄰域的正確分類率定義為

K（x）度量了正域中任一樣本的鄰域正確分類率，表示為鄰域中所包含樣本是同類別的比例，且β≤K（x）≤1.

定義8給定鄰域決策系統NDT=〈U，C，D〉，若有?B?C，?a∈C，但 a?B，且

則a相對于屬性子集B的平均正確分類率的增率定義為

1）當 Inc（a，B，D）＜0，所添加屬性 a使得正域的質量度下降；

2）當 Inc（a，B，D）=0，使得平均增益持平，正域質量不變；

3）當Inc（a，B，D）＞0，所添加屬性 a提高了正域的質量度，是最理想的結果.

那么Inc（a，B，D）可以作為正域的質量因子，監督正域的變化情況.

定義9（屬性質量度） 給定鄰域決策系統NDT=〈U，C，D〉，若有?B?C，?a∈C，但 a?B，則a相對于屬性子集B的屬性質量度定義為

Q（a，B，D）是屬性本身、屬性相對的屬性子集以及決策變量三者構成的一個函數.在同等情況下，屬性質量度的大小可以作為屬性選擇的評價指標.

本文提出的度量函數有以下幾點改進：

1）引入正域內樣本領域的正確分類率作為正域的質量因子；

2）定義屬性質量度，將正域的增量和平均正確分類率的增率相結合.

定義10[9]給定鄰域決策系統 NDT=〈U，C，D〉，稱B?C是C的一個約簡，B需滿足：

1）?a?B，γB-｛a｝＜ γB；

2）γB（D）=γC（D）.

條件1）要求在一個約簡中不存在多余的屬性，所有的屬性都應該是必不可少的；

條件2）要求約簡不能降低系統的區分能力，約簡應該與全部條件屬性具有相同的分辨能力.

2.2.3 計算示例鄰域決策信息系統的論域

條件屬性集合 C=｛a，b，c｝，決策屬性集合 D=｛d｝，d將樣本劃分為 small、medium、large等 3 個類別，簡記為 S、M、L，見表1.

表1 歸一化的決策表Tab.1 Normalized decision table

由于數據集的每個條件屬性具有不同的分布特征，本文采用屬性的標準差作為鄰域，為每個屬性設定基于自身分布特征的鄰域.這里選用屬性標準差的1/2作為鄰域，如表2所示.

表2 鄰域半徑的取值Tab.2 The neighborhood radiuses

距離度量采用曼哈頓距離（P=1）計算所有屬性子集的鄰域，本文做如此簡寫｛x1，2，3，4｝，如表 3所示.

表3 所有屬性組合的鄰域Tab.3 Neighborhoods of all attribute combinations

根據表1，決策屬性將論域劃分為3個等價類：X1=｛x1，x2，x3｝，X2=｛x4，x5，x6｝，X3=｛x7，x8，x9｝，設定正確率閾值β=0.7，約簡集合red=?.

對于表3，根據（4）式和定義9可以求得：

1）屬性｛a｝、｛b｝、｛c｝的下近似和屬性質量度分別為：

因此，選取最大屬性質量度的屬性為c，red=｛c｝.

2）在選取屬性 c的基礎上，屬性子集｛a，c｝、｛b，c｝的下近似和屬性質量度分別為：

因此，選取最大屬性質量度的屬性為a，red=｛c，a｝.

3）對全集 C：Posc（D）=｛x1，x2，x3，x4，x6，x7，x8，x9｝，則有 Posc（D）=Pos｛a｝∪｛c｝（D），約簡集合red=｛c，a｝.

3 基于屬性質量度的屬性約簡算法

3.1 算法依賴于新提出的屬性選擇度量函數，構造變精度鄰域粗糙集前向搜索屬性約簡算法，具體算法步驟如下：

輸入：歸一化后的鄰域決策信息系統NDT=〈U，C，D〉，變精度閾值 β，正域的增量下限 Sig＿ctrl，平均正確率的增率下限Inc＿ctrl.

輸出：屬性約簡集合red.

第一步：?ai∈C，通過定義1對樣本劃分鄰域.

第二步：初始化red=?.

第三步：?ai∈C-red：

（Ⅰ）通過定義8，計算平均正確分類率的增率Inc（ai，B，D）；

如果 Inc（ai，B，D）=0，

Inc（ai，B，D）=Inc＿ctrl；

（Ⅱ）通過（12）式，計算ai相對于red的屬性重要度（正域的增量）Sig（ai，red，D）；

（Ⅲ）通過定義9，計算ai相對于red的屬性質量度 Q（ai，B，D）.

第四步：找出屬性質量度 Q（ai，B，D）最大的屬性ai.

第五步：如果 Sig（ai，red，D）≥｜U｜×Sig＿ctrl：

red=red∪｛ai｝，

轉到第三步；

否則，輸出red.

Step 6：算法結束.

上述算法中，Sig＿ctrl是為了確保選出的屬性能有效提高當前屬性子集對知識的表達能力；Inc＿ctrl是為了避免當平均正確分類率持平，而出現屬性質量度 Q（ai，B，D）=0 的情況.

3.2 算法時間復雜度分析該算法的計算主要集中在第一步對所有樣本的鄰域計算和第三步～第五步每次迭代求取最優的屬性子集所需的正域計算次數.

假設鄰域決策系統NDT=〈U，C，D〉，其中有n個條件屬性，約簡后有k個屬性.在第一步中需要計算每個樣本在不同屬性下的鄰域集，其度量計算次數為｜U｜2n次，所以時間復雜度為 O（｜U｜2n）.在第三步～第五步中，通過每次循環找出最優的屬性子集，直到得出約簡結果，其正域的判定次數為

所以該步驟的時間復雜度為O（｜U｜2n）.因此，該算法的時間復雜度最終為O（｜U｜2n）.

4 實驗分析

4.1 實驗環境與方案為了驗證本文算法的有效性，在UCI數據集中選取如表4所示的8個數值型的數據集，其中Diabetic Retinopathy Debrecen簡寫為DRD.所有實驗都在PC機上運行，配置為：Inter（R）Core（TM）i5-7300HQ CPU ＠ 2.5 GHz，8 GB內存，Windows10操作系統，Python實驗平臺.

本文算法和文獻[9]中Hu提出的NFARNRS算法做對比，主要是比較不同變精度閾值下的屬性約簡、分類精度以及樣本錯分數.為了比較不同算法所選屬性的分類能力，本文選擇當前廣泛使用的C4.5和SVM分類學習算法，以10折交叉驗證的平均分類精度來衡量所選擇屬性的分類能力.

表4 數據集Tab.4 Data sets

在鄰域的取值中，都采用屬性標準差（Std/2.6）作為鄰域半徑，距離度量采用曼哈頓距離，并且設定正域的增量下限Sig＿ctrl=0.01，平均正確率的增率下限Inc＿ctrl=0.01.在本文的實驗中，變精度閾值β取值為0.6～0.9，以0.1為步長，在每個閾值下進行實驗比較.

4.2 實驗結果對比

4.2.1 屬性約簡結果對比 表5和表6記錄了在不同閾值下本文算法和NFARNRS算法的屬性約簡集合.分析可知，對于不同的閾值β，2種算法得到的屬性約簡個數是基本一致，但是所選屬性存在差異，這說明本文算法在不增加約簡個數的基礎上，改變了屬性選擇的優先度（表中屬性按照選擇順序從左到右排列），這符合2.2.1的分析.而且，在個別閾值下本文的屬性約簡個數更少，這說明本文算法在精度變化時的屬性約簡效果要更優.

4.2.2 不同分類算法下的分類精度對比 表7記錄了原始數據集在C4.5和SVM下的分類精度.

表5 不同閾值（β=0.6，0.7）下的約簡對比Tab.5 Reduction comparison under different thresholds（β =0.6，0.7）

表6 不同閾值下（β=0.8，0.9）的約簡對比Tab.6 Reduction comparison under different thresholds（β =0.8，0.9）

表8～11是在不同閾值和分類器下，2種算法對數據集約簡后的分類精度和樣本錯分數的對比（樣本錯分數能直觀的體現分類精度的差異）.分析可知，當閾值β在區間變化時，本文算法所取得的分類精度在不同的分類器下總體上都更優（√：本文算法高于NFARNRS算法；--：二者持平.），且本文算法取得的最優分類精度同表7原始數據集的分類精度對比可知，在不同的分類器下，本文算法的約簡都能夠保持或者有效提高分類精度，這表明本文算法在2.2.2小節所提出的屬性度量函數是正確有效的.圖1和圖2為所有數據集在C4.5和SVM的平均分類精度曲線.

表7 原始數據集的分類精度Tab.7 Classification accuracy of original data sets

表8 變精度β=0.6的分類精度Tab.8 Classification accuracy with variable precision β=0.6

表9 變精度β=0.7的分類精度Tab.9 Classification accuracy with variable precision β=0.7

表10 變精度β=0.8的分類精度Tab.10 Classification accuracy with variable precision β=0.8

表11 變精度β=0.9的分類精度Tab.11 Classification accuracy with variable precision β=0.9

圖1 所有數據集在C4.5的平均分類精度Fig.1 Average classification accuracy of all data sets in C4.5

圖2 所有數據集在SVM的平均分類精度Fig.2 Average classification accuracy of all data sets in SVM

分析圖1和圖2的曲線可知，從總體的平均數據來看，測試數據集在本文算法下所得的平均分類精度在NFARNRS算法的曲線之上，表明基于本文算法的屬性約簡效果更優.而且，當β＜0.9，本文算法的提升效果十分顯著；而在β≥0.9時，由于分類率的平均增益變化減小，此時屬性質量度主要由正域主導，本文算法和NFARNRS算法的差異就會逐漸變小，所以二者結果將會達到一致.但是本文算法對β的適應性更強，能在不同閾值下都得到更優的屬性約簡，表明本文提出的屬性度量方式更適用于變精度鄰域粗糙集的屬性約簡.

4.3 閾值參數的取值分析不失一般性，分類精度會隨 β的增大而增大，且在本研究中，當 β∈｛0.8，0.9｝時，所取得的分類精度最好.但是，不同數據集的差異性，使得β的取值是無法普遍在此范圍取值，由表8～11就可看出，個別數據集在β∈｛0.6，0.7｝就能取得不錯的分類精度，這也是圖1和圖2中曲線跳躍的原因.

且由表5和表6可知，閾值β的改變使得約簡個數呈線性變化，隨閾值β取值的增大而增多.

綜上，一般來說，調高β的取值可得到好的分類精度，但約簡個數會稍多一點；調低β的取值可以取得更少的約簡個數，但分類精度會略低.

4.4 實驗結論由以上實驗分析對比可知，本文算法相比于NFARNRS算法，在保持所選屬性個數基本一致，甚至更少的情況下，本文算法提出的屬性度量函數在不同閾值和不同分類器下基本都能得到最優的分類精度.而且，本文算法降低了閾值β對正域的影響，提高了對屬性的度量能力，使得本文提出的屬性度量方式更適合于變精度鄰域粗糙集.

5 結束語

本文介紹了鄰域粗糙集和變精度鄰域粗糙集的基本概念，分析了以往變精度鄰域粗糙集采用屬性重要度作為度量標準的缺點，改進了屬性的度量方式.相比于NFARNRS算法，本文算法通過引入鄰域內正確分類率作為正域的質量因子，降低了變精度對正域的影響，在改變閾值的情況下，都能得到更優的約簡.

但與以往的屬性約簡相比，時間復雜度仍然沒有改變，如何讓本文算法具有較少的時間開銷，這個問題將在未來的工作中進行研究.

致謝成都信息工程大學青年學術帶頭人科研基金項目（J201609）對本文給予了資助，謹致謝意.