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

李 冬，蔣 瑜，鮑楊婉瑩

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

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

針對這個問題，Zadeh[7]提出了知識?；土６扔嬎愕母拍睿琇in[8]在知識?；⒘６扔嬎愕幕A(chǔ)上提出了鄰域模型.此后，Hu等[9]將鄰域引入粗糙集，提出了基于鄰域?；痛植诒平泥徲虼植诩?，將其應(yīng)用到數(shù)值型數(shù)據(jù)的屬性約簡，并且提出一種快速屬性約簡，加快計算正域的速度.自鄰域粗糙集被提出以來，眾多學(xué)者也對其相關(guān)的改進(jìn)與應(yīng)用進(jìn)行了研究[10-14].

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

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

1 鄰域粗糙集

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

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

其中，Δ是距離函數(shù)，且對于?x1，x2，x3∈U，Δ應(yīng)滿足以下條件：

1）Δ（x1，x2）≥0，當(dāng)且僅當(dāng) x1=x2時等號成立；

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

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

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

1.2 鄰域決策系統(tǒng)

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

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

其中

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

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

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

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

由定義4和（11）式可得

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

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

2 變精度鄰域粗糙集

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

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

其中

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

2.2 變精度鄰域粗糙集的屬性約簡改進(jìn)

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

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

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

2.2.2 一種基于屬性質(zhì)量度的度量函數(shù) 本文在Hu等所提出的屬性重要度[9]基礎(chǔ)上進(jìn)行改進(jìn)，將鄰域內(nèi)平均正確分類率的增率作為屬性重要度的質(zhì)量因子，定義了屬性質(zhì)量度，并提出一種基于正域的增量和平均正確分類率的增率相結(jié)合的屬性選擇方法，優(yōu)先選擇分類能力更好的屬性.

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

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

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

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

1）當(dāng) Inc（a，B，D）＜0，所添加屬性 a使得正域的質(zhì)量度下降；

2）當(dāng) Inc（a，B，D）=0，使得平均增益持平，正域質(zhì)量不變；

3）當(dāng)Inc（a，B，D）＞0，所添加屬性 a提高了正域的質(zhì)量度，是最理想的結(jié)果.

那么Inc（a，B，D）可以作為正域的質(zhì)量因子，監(jiān)督正域的變化情況.

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

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

本文提出的度量函數(shù)有以下幾點(diǎn)改進(jìn)：

1）引入正域內(nèi)樣本領(lǐng)域的正確分類率作為正域的質(zhì)量因子；

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

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

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

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

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

條件2）要求約簡不能降低系統(tǒng)的區(qū)分能力，約簡應(yīng)該與全部條件屬性具有相同的分辨能力.

2.2.3 計算示例鄰域決策信息系統(tǒng)的論域

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

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

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

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

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

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

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

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

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

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

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

因此，選取最大屬性質(zhì)量度的屬性為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 基于屬性質(zhì)量度的屬性約簡算法

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

輸入：歸一化后的鄰域決策信息系統(tǒng)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的屬性質(zhì)量度 Q（ai，B，D）.

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

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

red=red∪｛ai｝，

轉(zhuǎn)到第三步；

否則，輸出red.

Step 6：算法結(jié)束.

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

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

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

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

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

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

本文算法和文獻(xiàn)[9]中Hu提出的NFARNRS算法做對比，主要是比較不同變精度閾值下的屬性約簡、分類精度以及樣本錯分?jǐn)?shù).為了比較不同算法所選屬性的分類能力，本文選擇當(dāng)前廣泛使用的C4.5和SVM分類學(xué)習(xí)算法，以10折交叉驗(yàn)證的平均分類精度來衡量所選擇屬性的分類能力.

表4 數(shù)據(jù)集Tab.4 Data sets

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

4.2 實(shí)驗(yàn)結(jié)果對比

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

4.2.2 不同分類算法下的分類精度對比 表7記錄了原始數(shù)據(jù)集在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種算法對數(shù)據(jù)集約簡后的分類精度和樣本錯分?jǐn)?shù)的對比（樣本錯分?jǐn)?shù)能直觀的體現(xiàn)分類精度的差異）.分析可知，當(dāng)閾值β在區(qū)間變化時，本文算法所取得的分類精度在不同的分類器下總體上都更優(yōu)（√：本文算法高于NFARNRS算法；--：二者持平.），且本文算法取得的最優(yōu)分類精度同表7原始數(shù)據(jù)集的分類精度對比可知，在不同的分類器下，本文算法的約簡都能夠保持或者有效提高分類精度，這表明本文算法在2.2.2小節(jié)所提出的屬性度量函數(shù)是正確有效的.圖1和圖2為所有數(shù)據(jù)集在C4.5和SVM的平均分類精度曲線.

表7 原始數(shù)據(jù)集的分類精度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 所有數(shù)據(jù)集在C4.5的平均分類精度Fig.1 Average classification accuracy of all data sets in C4.5

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

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

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

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

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

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

5 結(jié)束語

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

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

致謝成都信息工程大學(xué)青年學(xué)術(shù)帶頭人科研基金項(xiàng)目（J201609）對本文給予了資助，謹(jǐn)致謝意.