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

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

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

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

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

1 基礎(chǔ)知識

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

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

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

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

因此，{NB(x)：?x∈U} 表示一個由條件屬性B誘導(dǎo)的鄰域粒化結(jié)果.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 共現(xiàn)鄰域

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

圖1 鄰域結(jié)構(gòu)Fig.1 Neighborhood structure

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

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

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

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

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

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

根據(jù)式（15），可以得到x關(guān)于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ì)可知，和鄰域關(guān)系相比，共現(xiàn)鄰域關(guān)系有更高的分辨能力.

定義8給定一個決策系統(tǒng)DS，U/IND(D)={X1，X2，…，XN}，?B?AT，D關(guān)于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，進(jìn) 而成立，即

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

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

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

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

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

2.2 偽標(biāo)記共現(xiàn)鄰域粗糙集在式（8）所示偽標(biāo)記鄰域關(guān)系的基礎(chǔ)之上，進(jìn)一步考慮樣本鄰域信息粒內(nèi)部不同樣本所對應(yīng)的鄰域之間的結(jié)構(gòu)關(guān)系，可以定義如下所示的偽標(biāo)記共現(xiàn)鄰域關(guān)系.

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗分析

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

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

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

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

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

觀察表2，不難得出以下結(jié)論：

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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