共現(xiàn)鄰域關系下的屬性約簡研究

毛振宇 ,竇慧莉* ,宋晶晶,3 ,姜澤華 ,王平心

（1.江蘇科技大學計算機學院，鎮(zhèn)江，212003；2.江蘇科技大學理學院，鎮(zhèn)江，212003；3.數(shù)據(jù)科學與智能應用福建省高校重點實驗室，漳州，363000）

作為一種常用的粒計算方法，鄰域信息?；?-4］因其處理連續(xù)型甚至混合型數(shù)據(jù)的有效性受到廣大學者的關注與青睞.事實上鄰域信息?；暮诵臋C制就是從樣本之間的距離出發(fā)，通過給定一個半徑來約束樣本間的相似性程度，最終確立合適的鄰域關系.不難發(fā)現(xiàn)，該過程中指定的半徑對最終的信息?；Y果有不容忽視的影響，而不恰當?shù)陌霃皆O置往往造成負面的影響，譬如，指定半徑較大時不同類別的樣本極有可能落入同一鄰域，從而引起鄰域中信息的不精確或不一致.針對該現(xiàn)象，Yang et al［5］提出一種偽標記鄰域信息?；呗裕瑓⒖紭颖驹跅l件屬性上相似性程度的前提下，進一步對生成的樣本偽標記加以考慮，該策略能夠在一定程度上減緩半徑較大時鄰域中信息的不精確或不一致問題.

然而，不同的半徑會使鄰域關系或偽標記鄰域關系產(chǎn)生不同的區(qū)分能力，值得注意的是這兩種區(qū)分能力的產(chǎn)生僅僅依賴樣本間的距離以及半徑的大小，而忽視了鄰域信息粒內(nèi)部不同樣本所對應的鄰域之間的結構關系［6］.鑒于此，本研究引入鄰域之間的距離度量，提出一種新型的共現(xiàn)鄰域信息?；瘷C制，以期能夠深入挖掘鄰域信息粒之間的內(nèi)在關聯(lián)與隱含關系；在此基礎上分別給出兩種類型的上下近似算子，進而實現(xiàn)了共現(xiàn)鄰域粗糙集模型與偽標記共現(xiàn)鄰域粗糙集模型；此外，還利用前向貪心搜索策略［7-12］求解了兩種模型下的約簡結果.

1 基礎知識

1.1 鄰域粗糙集粗糙集理論中，一個決策系統(tǒng)可以表示為二元組，其中U是所有樣本組成的非空有限集合，即論域；AT是所有條件屬性集合；D是決策屬性且AT∩D=?.U/IND(D)={X1，X2，…，XN} 表示根據(jù)決策屬性D所誘導出的論域上的劃分，?Xi∈U/IND(D)，Xi表示第i個決策類且1≤i≤N.

定義1給定一個決策系統(tǒng)DS，?B?AT，對于一個鄰域半徑δ，鄰域關系可以定義為：

其中，disB(x，y)(?x，y∈U)表示利用條件屬性B所提供的信息計算得到樣本x與樣本y之間的距離.

?x∈U，根據(jù)式（1），不難得到樣本x關于B的鄰域如下：

因此，{NB(x)：?x∈U} 表示一個由條件屬性B誘導的鄰域?；Y果.

定義2給定一個決策系統(tǒng)DS，U/IND(D)={X1，X2，…，XN}，?B?AT，D關于B的上近似和下近似可以定義為：

其中，?Xi∈U/IND()D，決策類Xi的上近似和下近似可以定義為：

定義2 所示的上、下近似集刻畫了目標概念的粗糙性.從這一角度出發(fā)，可以進一步量化地描述數(shù)據(jù)中的目標概念的確定性程度.因此通過定義2，Pawlak 給出如下所示的近似質(zhì)量概念.

定義3給定一個決策系統(tǒng)DS，?B?AT，D關于B的近似質(zhì)量定義如下：

其中，|X|表示集合X的基數(shù).

顯然0 ≤γ(B，D)≤1 成立.γ(B，D)表示根據(jù)條件屬性B，確定屬于某一個決策類別的樣本占全部樣本的比例.

1.2 偽標記鄰域粗糙集在傳統(tǒng)鄰域模型中，鄰域粒化的結果和近似質(zhì)量度量與鄰域半徑是緊密相關的.當半徑較大時，不同決策類別的樣本可能會出現(xiàn)在同一鄰域范圍內(nèi)，這極有可能降低鄰域分類器的性能.針對這一問題，Yang et al［5］提出一種偽標記鄰域建模方法，在構造鄰域信息粒的過程中引入偽標記策略，通過樣本之間的距離和偽標記屬性來共同區(qū)分樣本.

定義4給定一個偽標記決策系統(tǒng)DSPL，?B?AT，對于一個鄰域半徑δ，偽標記鄰域關系可以定義為：

根據(jù)式（8），不難得到樣本x關于B的偽標記鄰域形如下：

對比式（1）和式（8），不難得到鄰域關系和偽標記鄰域關系之間存在形如的關系，即偽標記鄰域關系比鄰域關系更細；進一步，再通過式（2）和式（9），?x∈U，顯然成立，即偽標記鄰域比鄰域更小.

定義5給定一個偽標記決策系統(tǒng)DSPL，U/IND(D)={X1，X2，…，XN}，?B?AT，D關于B的偽標記鄰域上近似和下近似定義為：

其中，?Xi∈U/IND(D)，決策類Xi的偽標記鄰域上近似和下近似可以定義為：

類似鄰域決策系統(tǒng)中的近似質(zhì)量，根據(jù)定義5 可以得到偽標記鄰域近似質(zhì)量的定義如下所示.

定義6給定一個偽標記決策系統(tǒng)DSPL，?B?AT，D關于B的偽標記鄰域近似質(zhì)量定義如下：

顯然0≤γPL(B，D)≤1 成立.偽標記鄰域近似質(zhì)量的值越大，表示樣本的不確定程度越低.

2 共現(xiàn)鄰域

通過上節(jié)所示的兩種鄰域關系可以觀察到，不同的半徑會使鄰域關系或偽標記鄰域關系產(chǎn)生不同的區(qū)分能力，但這兩種區(qū)分能力的產(chǎn)生僅僅依賴于樣本間的距離以及半徑的大小，而忽視了鄰域信息粒內(nèi)部不同樣本所對應的鄰域之間的結構關系.具體描述如圖1 所示.

圖1 鄰域結構Fig.1 Neighborhood structure

觀察圖1，不難發(fā)現(xiàn)樣本y1與y2屬于同一個決策類別，且y2落入了y1的鄰域.但是，y1所示的鄰域中包含了大量的“方框”樣本，而y2所示的鄰域中卻包含了大量的“三角”樣本，因此這兩個鄰域在結構上是有顯著差異的；并且y2被囊括在y1的鄰域中，其合理性值得商榷.為解決這一問題，下文提出共現(xiàn)鄰域的概念.

2.1 共現(xiàn)鄰域粗糙集在式（1）所示鄰域關系的基礎上，進一步考慮鄰域信息粒內(nèi)部不同樣本所對應的鄰域之間的結構關系，可以定義如下所示的共現(xiàn)鄰域關系.

定義7給定一個決策系統(tǒng)DS，?B?AT，對于一個鄰域半徑δ，共現(xiàn)鄰域關系可以定義為：

其中，DIS(NB(x)，NB(y))表示樣本x的鄰域與樣本y的鄰域之間的距離，α為設定的閾值.

根據(jù)Jiang and Chen［6］提出的鄰域間距離的形式，DIS(NB(x)，NB(y))可表示為：

定義7 表示共現(xiàn)鄰域關系的兩個約束條件：（1）樣本間的距離小于或等于給定半徑；（2）樣本鄰域之間的距離小于或者等于給定閾值.

根據(jù)式（15），可以得到x關于B的共現(xiàn)鄰域：

性質(zhì)1給定一個決策系統(tǒng)DS，?B?AT，CNB?NB成立.

證 明根據(jù)式（1）和式（15）的表現(xiàn)形式，CNB的約束條件顯然比NB的約束條件更苛刻，因此CNB?NB顯然成立.

性質(zhì)2給定一個決策系統(tǒng)DS，?B?AT，CNB(x)?NB(x)成立.

證 明根據(jù)式（2）和式（17）的表現(xiàn)形式以及性質(zhì)1，CNB(x)的約束條件顯然比NB(x)的約束條件更苛刻，因此CNB(x)?NB(x)顯然成立.

從上述性質(zhì)可知，和鄰域關系相比，共現(xiàn)鄰域關系有更高的分辨能力.

定義8給定一個決策系統(tǒng)DS，U/IND(D)={X1，X2，…，XN}，?B?AT，D關于B的共現(xiàn)鄰域上近似和下近似可以定義為：

其中，?Xi∈U/IND(D)，決策類Xi的共現(xiàn)鄰域上近似和下近似可以定義為：

性質(zhì)3給定一個決策系統(tǒng)DS，?Xi∈U/成立.

證 明?x∈-NB()Xi，根據(jù)式（6）可以得到NB(x)?Xi，再通過性質(zhì)2，可知CNB(x)?NB(x)成 立，因 此 顯 然 有CNB(x)?Xi，進 而成立，即

定義9給定一個決策系統(tǒng)DS，?B?AT，D關于B的共現(xiàn)鄰域近似質(zhì)量定義如下：

顯然0 ≤γCN(B，D)≤1 成立.當?時，共現(xiàn)鄰域近似質(zhì)量會達到最小值0；當時，共現(xiàn)鄰域近似質(zhì)量會達到最大值1.

性質(zhì)4給定一個決策系統(tǒng)DS，?B?AT，有γCN(B，D)≥γ(B，D)成立.

證 明根據(jù)性質(zhì)3 所示的結果，性質(zhì)4 顯然成立.

上述命題表示與傳統(tǒng)鄰域相比較，采用共現(xiàn)鄰域的方法可以得到一個更高的近似質(zhì)量.

2.2 偽標記共現(xiàn)鄰域粗糙集在式（8）所示偽標記鄰域關系的基礎之上，進一步考慮樣本鄰域信息粒內(nèi)部不同樣本所對應的鄰域之間的結構關系，可以定義如下所示的偽標記共現(xiàn)鄰域關系.

定義10給定一個偽標記決策系統(tǒng)DSPL，?B?AT，對于一個鄰域半徑δ，則偽標記共現(xiàn)鄰域關系可以定義為：

定義10 表示了偽標記共現(xiàn)鄰域關系的三個約束條件：（1）樣本之間的距離小于或者等于給定半徑；（2）樣本之間的偽標記值相等；（3）樣本鄰域之間的距離小于或者等于給定閾值.

根據(jù)式（23），可以得到樣本x關于B的偽標記共現(xiàn)鄰域：

類似共現(xiàn)鄰域中的近似質(zhì)量，根據(jù)定義11，可以得到偽標記共現(xiàn)鄰域近似質(zhì)量的定義如下所示.

定義12給定一個偽標記決策系統(tǒng)DSPL，?B?AT，D關于B的偽標記共現(xiàn)鄰域近似質(zhì)量定義如下：

性質(zhì)8給定一個偽標記決策系統(tǒng)DSPL，?B?AT，有(B，D)成立.

證 明根據(jù)性質(zhì)7 所示的結果，性質(zhì)8 顯然成立.

上述命題表示與偽標記鄰域相比較，采用偽標記共現(xiàn)鄰域的方法可以得到一個更高的近似質(zhì)量.

2.3 共現(xiàn)鄰域求解算法由以上論述可知，共現(xiàn)鄰域與傳統(tǒng)鄰域相比，其所對應的二元關系更嚴格；類似地，偽標記共現(xiàn)鄰域與偽標記鄰域相比，其所對應的二元關系也更嚴格.以下給出一個具體的算法流程用于求解共現(xiàn)鄰域關系，偽標記共現(xiàn)鄰域關系的求解過程類似可得.

上述算法的時間復雜度為O(|U|2? |B|)，其中|U|為論域中樣本數(shù)目，|B|為使用的條件屬性數(shù)目，具體分析如下：

（1）步驟2 計算論域中每一個樣本的鄰域，此時需要求得論域中任意兩個樣本之間的距離，因而該步驟的時間復雜度為O(|U|2? |B|).

（2）步驟3 考慮了鄰域結構之間的關系，且通過利用鄰域距離來刻畫不同樣本的鄰域之間的相似性程度，該步驟的時間復雜度為O(|U|2).因為對于任意一個樣本x，在最壞的情況下，其鄰域囊括了論域U中的所有樣本且這些樣本的鄰域也都為U本身.

綜上，算法整體時間復雜度為O(|U|2? |B|).

3 實驗分析

為驗證共現(xiàn)鄰域方法的有效性，從UCI 數(shù)據(jù)集中選取12 組數(shù)據(jù)，基本信息如表1 所示.

表1 數(shù)據(jù)集的描述Table 1 Discription of datasets

為了對比分析四種不同方法：傳統(tǒng)鄰域關系（NR）、共現(xiàn)鄰域關系（CNR）、偽標記鄰域關系（PLNR）、偽標記共現(xiàn)鄰域關系（PLCNR），分別利用這些關系所構建的粗糙集依據(jù)近似質(zhì)量這一度量準則進行屬性約簡［13-19］的求解，約簡的求解進程都采用前向貪心搜索策略.實驗選取20 個不同的半徑δ，分別為0.025，0.05，0.075，…，0.5，采用五折交叉驗證的方法，用于對比各種方法下的約簡率以及約簡中屬性的分類準確率.

在共現(xiàn)鄰域關系的構造中，將閾值α設置為所有鄰域距離的平均值.在約簡的約束條件構造中，還設置了兩個不同的約束條件以實現(xiàn)近似約簡［20］的目的，即近似質(zhì)量保持不變（ε=1），近似質(zhì)量高于原始屬性近似質(zhì)量值的95%（ε=0.95）.

3.1 約簡率對比表2 展示了四種不同方法在不同閾值ε下的約簡率結果比較，表中下畫線表示相同閾值下，NR 方法與CNR 方法對比時較大的約簡率結果，PLNR 方法與PLCNR 方法對比時較大的約簡率結果.這些約簡結果是在20 個半徑下利用五折交叉驗證得到結果的均值.約簡率越高，表示刪除的冗余屬性就越多.

觀察表2，不難得出以下結論：

（1）無論ε取值為1 還是0.95，和傳統(tǒng)鄰域關系相比，采用共現(xiàn)鄰域關系的方式能夠得到較高的約簡率，這意味著采用共現(xiàn)鄰域的方法有助于刪掉更多的冗余屬性.類似地，與偽標記鄰域關系相比，采用偽標記共現(xiàn)鄰域關系的方式亦能夠得到較高的約簡率.

（2）當ε從1 降低為0.95 時，無論采用哪一種方法，約簡率都能得到提升.這主要是因為當ε降低時，屬性約簡中的約束條件會進一步放寬.例如，當采用NR 方法時，若ε=1，則12 個數(shù)據(jù)上的平均約簡率為0.4173，而ε=0.95 時，12 個數(shù)據(jù)上的平均約簡率為0.4940.

3.2 分類準確率對比在本組實驗中，采用KNN（K=3）分類器和SVM 分類器，利用約簡結果對測試集數(shù)據(jù)進行分類，并且計算分類準確率，最后求得分類準確率的平均值和最大值.分類準確率均值結果如表3 與表4 所示，分類準確率最大值結果如表5 與表6 所示.表中下畫線表示相同閾值下，NR 方法與CNR 方法對比時較大的分類準確率，PLNR 方法與PLCNR 方法對比時較大的分類準確率.

從表3 和表4 中可以看出，無論是采用KNN分類器還是SVM 分類器，利用傳統(tǒng)鄰域關系與共現(xiàn)鄰域關系所求得的約簡，其對應的平均分類準確率差異甚微，這一現(xiàn)象在偽標記情形下也依然存在.換言之，針對屬性約簡這一問題，雖然3.1 節(jié)的結果表明了共現(xiàn)鄰域方法能夠刪除較多的冗余屬性，但最終的結果在絕大部分情況下并不會降低平均分類準確率.

表2 四種方法在不同閾值下的約簡率Table 2 The reduction rate of four methods under different thresholds

表3 四種方法在不同閾值下的KNN 分類準確率均值Table 3 The average KNN classification accuracies of the four methods under different thresholds

從表5 和表6 可以看出，無論是采用KNN 分類器還是SVM 分類器，利用傳統(tǒng)鄰域關系與共現(xiàn)鄰域關系求得的約簡，其對應的最大分類準確率差異甚微，這一現(xiàn)象在偽標記情形下也依然出現(xiàn).換言之，針對屬性約簡這一問題，雖然共現(xiàn)鄰域方法能夠刪除較多的冗余屬性，但最終的結果在絕大部分情況下并不會降低最大分類準確率.

表4 四種方法在不同閾值下的SVM 分類準確率均值Table 4 The average SVM classification accuracies of the four methods under different thresholds

表5 四種方法在不同閾值下的KNN 分類準確率最大值Table 5 The maximum KNN classification accuracies of the four methods under different thresholds

4 結論

在粗糙集方法中，針對已有的鄰域關系和偽標記鄰域關系忽略不同樣本所對應的鄰域結構之間的差異性這一問題，提出一個共現(xiàn)鄰域的策略，并且定義了共現(xiàn)鄰域關系、偽標記共現(xiàn)鄰域關系，構建相應的粗糙集模型，繼而討論了不同關系下粗糙集模型之間的內(nèi)在聯(lián)系.實驗結果表明，相較于傳統(tǒng)鄰域關系與偽標記鄰域關系，采用共現(xiàn)鄰域關系與偽標記共現(xiàn)鄰域關系，計算約簡結果，可以獲得一個較高的約簡率，并且所得到的約簡并不會顯著降低分類的準確率.下一步的工作：

表6 四種方法在不同閾值下的SVM 分類準確率最大值Table 6 The maximum SVM classification accuracies of the four methods under different thresholds

（1）本研究僅僅選擇了近似質(zhì)量這一個度量準則，后續(xù)可以考慮鄰域決策錯誤率、條件熵等其他度量準則，從而可以得到更好的約簡結果來提高后續(xù)分類準確率.

（2）本研究從鄰域之間的結構關系出發(fā)，實現(xiàn)了共現(xiàn)鄰域求解方法，下一步還可以在模糊粒［21］結構框架下，設計共現(xiàn)模糊關系.