偽標簽鄰域粗糙集下的屬性約簡加速策略

饒先勝，宋晶晶,2+，楊習貝，于化龍，王平心

(1.江蘇科技大學 計算機學院，江蘇 鎮江 212003；2.閩南師范大學 數據科學與智能應用福建省 高校重點實驗室，福建 漳州 363000；3.江蘇科技大學 理學院，江蘇 鎮江 212003)

0 引 言

粗糙集理論[1]是由Pawlak教授提出的用于數據分析與處理的數學工具。近年來，粗糙集理論在數據挖掘[2]、模式識別[3]、機器學習[4-6]等領域都得到了實際的應用。為提高Pawlak粗糙集的適用性，Hu等提出了鄰域粗糙集[7,8]，且得到了國內外學者的廣泛關注[9-12]。值得注意的是在鄰域粗糙集中，所考慮的半徑對所得鄰域關系的分辨能力具有重要影響，過大的半徑會使鄰域關系的分辨能力較差。因此，為提高鄰域關系的分辨能力，Yang等[13]通過將偽標簽策略引入到鄰域和鄰域關系的構造過程中，提出了偽標簽鄰域粗糙集。

屬性約簡[14-17]作為粗糙集理論中備受關注的問題之一，已經得到眾多學者的重視。目前，有關約簡求解的方法主要有：窮舉法[18,19]和基于適應度函數的啟發式方法[14]。盡管窮舉法可用于求解所有的約簡，但過于復雜和耗時。這也是基于適應度函數的啟發式方法受到廣泛關注的原因。

基于偽標簽鄰域粗糙集的屬性約簡問題，可以使用啟發式方法來進行求解。但值得注意的是，在不同的半徑下進行屬性約簡時，往往會得到不同的約簡結果，而對于不同約簡結果，其意義或泛化性能也不盡相同。因此，在多個半徑下進行屬性約簡，有助于觀測約簡性能的變化趨勢和尋找具有較好泛化性能的約簡結果。為降低求解偽標簽鄰域粗糙集中一組半徑下約簡的時間消耗，本文在現有的啟發式算法基礎之上，通過考慮在屬性約簡過程中減少屬性的遍歷規模，來設計加速策略，以期加快屬性選擇的過程。

1 基礎知識

1.1 偽標簽鄰域粗糙集

在鄰域粗糙集中，鄰域決策系統可表示為3元組NDS=，其中U是非空有限的樣本集合，稱為論域；A是條件屬性集合，d是決策屬性。?x∈U，d(x) 是樣本x的標簽。

給定一個鄰域決策系統NDS，則U/INDd={X1,X2,…,Xp} 為決策屬性d在論域上誘導出的劃分，其中INDd是關于決策屬性d的等價關系，即有INDd={(x,y)∈U×U∶d(x)=d(y)}。?Xq∈U/INDd，Xq表示具有相同標簽樣本組成的第q個決策類。

定義1[7]給定一個鄰域決策系統NDS，?B?A，則任意樣本x∈U關于B的鄰域為

δB(x)={y∈U∶ΔB(x,y)≤σ}

(1)

其中，ΔB(x,y) 表示由條件屬性集合B計算得到的樣本x和樣本y之間的距離，σ為半徑。

在本文中，采用歐式距離進行計算ΔB(x,y)。此外，論域上關于B的一個鄰域關系可以表示為δB={(x,y)∈U×U∶ΔB(x,y)≤σ}。

由定義1可以看出，給定一個半徑可以得到論域中任意樣本的鄰域和論域上的一個鄰域關系。但值得注意的是，當給定的半徑過大時，兩個相似性程度較低的不同類別樣本仍可能具有鄰域關系，因而會導致在論域上得到的鄰域關系的分辨能力較差。因此，Yang等[13]在鄰域和鄰域關系的構造過程中添加偽標簽約束，提出了偽標簽鄰域粗糙集。

定義2[13]給定一個偽標簽鄰域決策系統NDSPL，?B?A，則任意樣本x∈U關于B的偽標簽鄰域為

(2)

定義3[13]給定一個偽標簽鄰域決策系統NDSPL，?B?A，則決策屬性d關于條件屬性集合B的偽標簽鄰域下近似和上近似分別為

(3)

(4)

其中，Xq∈U/INDd，且

(5)

(6)

定義4[13]給定一個偽標簽鄰域決策系統NDSPL，?B?A，則決策屬性d關于條件屬性集合B的偽標簽近似質量為

(7)

其中，|X| 表示集合X的基數。

1.2 屬性約簡

定義5表明A的一個偽標簽近似質量約簡是能夠使得該決策系統的偽標簽近似質量不會降低的最小屬性子集。因此，根據定義5中的屬性約簡定義和偽標簽近似質量，可以進一步設計如下用于評估候選屬性的重要度函數。

定義6 給定一個偽標簽鄰域決策系統NDSPL，?B?A，則?a∈A-B，a相對于B關于偽標簽近似質量的重要度為

(8)

在定義6中，SigPL是根據偽標簽近似質量來評估候選屬性重要度的函數。?a∈A-B，若SigPL(a,B,d) 的值越大，則屬性a對提高偽標簽近似質量作用越大，即屬性a越重要。因此，可以將定義6中的重要度函數應用于求解偽標簽近似質量約簡的啟發式算法中。詳細的算法過程如下所示。

算法1：計算偽標簽近似質量約簡的啟發式算法。

輸入：偽標簽鄰域決策系統NDSPL，半徑σ。

輸出：偽標簽近似質量約簡B。

步驟1B←?;

(1) ?a∈A-B，計算其屬性重要度 SigPL(a,B,d);

(2) 選擇屬性b，滿足SigPL(b,B,d)=max{SigPL(a,B,d)∶a∈A-B};

(3)B←B∪;

EndWhile

步驟4 輸出偽標簽近似質量約簡B。

由算法1的過程可知，算法1的主要時間消耗在于計算屬性的重要度。因此，算法1的時間復雜度為O(|U|2·|A|2)，其中 |U| 和 |A| 分別表示樣本和屬性的個數。顯然，若使用算法1求解一組半徑下的約簡時，則需要在每個半徑上遍歷所有屬性來尋找滿足約束條件的屬性子集。此時，隨著半徑個數增多，這一方法將會具有較高的時間消耗。

2 屬性約簡加速策略

為解決在1.2節中使用算法1在一組半徑上進行屬性約簡時，求解約簡的時間消耗會隨著半徑個數的增多而增長這一問題，本節將基于啟發式算法，考慮在前一個半徑下的約簡結果基礎之上，求解當前半徑下的約簡，通過減少屬性遍歷的規模，進行屬性約簡加速策略的設計，以降低在偽標簽鄰域粗糙集中求解一組半徑下約簡的時間消耗。進一步，根據半徑的變化趨勢設計基于正向和逆向的屬性約簡加速算法。

2.1 基于正向的屬性約簡加速策略

給定一個偽標簽鄰域決策系統NDSPL和一組半徑R={σ1,σ2,…,σn}。假設σ1<σ2<…<σn且在半徑σs(1≤s

算法2：基于正向的屬性約簡加速算法。

輸入：偽標簽鄰域決策系統NDSPL，半徑σs下求得的約簡Bs，半徑σs+1(1≤s

輸出：半徑σs+1下的偽標簽近似質量約簡Bs+1。

步驟1Bs+1←Bs;

(1) ?a∈A-Bs+1，計算其屬性重要度SigPL(a,Bs+1,d);

(2) 選擇屬性b，滿足SigPL(b,Bs+1,d)=max{SigPL(a,Bs+1,d)∶a∈A-Bs+1};

(3)Bs+1←Bs+1∪;

EndWhile

步驟4 輸出半徑σs+1下的偽標簽近似質量約簡Bs+1。

由算法2的過程可知，算法2與算法1的不同之處在于，當計算某一半徑下的約簡時，算法2不再是在A中選擇具有最大重要度的屬性，而是在Bs的基礎上，對A-Bs中的屬性根據重要度進行選擇。由此可知，算法2的時間復雜度為O(|U|2·|A-Bs|2)。

值得注意的是，在基于正向的屬性約簡加速策略中，當求解最小半徑下的約簡時，仍需要通過算法1來進行計算。

2.2 基于逆向的屬性約簡加速策略

給定一個偽標簽鄰域決策系統NDSPL和一組半徑R={σ1,σ2,…,σn}。假設σ1<σ2<…<σn且在半徑σs(1≤s

算法3：基于逆向的屬性約簡加速算法。

輸入：偽標簽鄰域決策系統NDSPL,半徑σs下求得的約簡Bs,半徑σs-1(1

輸出：半徑σs-1下的偽標簽近似質量約簡Bs-1。

步驟1Bs-1←Bs;

(1) ?a∈A-Bs-1，計算其屬性重要度 SigPL(a,Bs-1,d);

(2) 選擇屬性b，滿足SigPL(b,Bs-1,d)=max{SigPL(a,Bs-1,d)：a∈A-Bs-1};

(3)Bs-1←Bs-1∪；

EndWhile

步驟4 輸出半徑σs-1下的偽標簽近似質量約簡Bs-1。

由算法3可以看出，基于逆向的屬性約簡加速策略與基于正向的屬性約簡加速策略不同之處在于，前者計算一組半徑下的約簡結果時，是根據半徑由大到小的變化趨勢進行計算，并在較大半徑下的約簡基礎之上進行下一個半徑下的約簡求解，而后者與其相反。此外，由算法3的具體過程可知，算法3的時間復雜度為O(|U|2·|A-Bs|2)。

值得注意的是，在基于逆向的屬性約簡加速策略中，當求解最大半徑下的約簡時，仍需要通過算法1來進行計算。

3 實驗分析

為驗證所提加速策略的有效性，本節將從UCI數據集中選取8組數據進行實驗。數據的描述見表1。在實驗中選擇了30個半徑，它們的值為0.02,0.04,0.06,…,0.60。樣本的偽標簽是通過k-means聚類方法得到的，其中k的取值與所使用數據集的決策類數相同。此外，本節不僅將第2節所提的加速策略與算法1進行比較，還將與文獻[22]中的兩種加速算法進行對比。

表1 數據集描述

在本節實驗中，為了比較約簡結果的分類性能，采用了5折交叉驗證。但值得注意的是，由于交叉驗證的隨機性可能會導致訓練集或測試集中某一類樣本較少。此時，若根據訓練集和約簡結果對測試集進行預測，得到的預測結果可能會是不合理的。因此，可以通過對數據進行無偏采樣產生訓練集和測試集。進一步，5折交叉驗證可以通過如下過程進行實現。首先，根據數據中樣本的真實標簽，將數據分成X1,X2,…,Xp。其次，對任意Xi(1≤i≤p)，將其中數據隨機平均分成5份，即Xi1,Xi2,…,Xi5。記Tij=Xi-Xij，其中1≤j≤5。最后，在第一輪計算中，將T11∪T21∪…∪Tp1作為訓練集進行屬性約簡，X11∪X21∪…∪Xp1用作測試集，根據約簡結果和訓練集進行分類；在第二輪計算中，將T12∪T22∪…∪Tp2作為訓練集進行屬性約簡，X12∪X22∪…∪Xp2用作測試集，根據約簡結果和訓練集進行分類；類似地，在最后一輪計算中，將T15∪T25∪…∪Tp5作為訓練集進行屬性約簡，X15∪X25∪…∪Xp5用作測試集，根據約簡結果和訓練集進行分類。值得注意的是，本節中的實驗結果均為5折交叉驗證下所得度量的均值。

3.1 算法時間消耗的比較

在本小節實驗中，將使用文中所提及的3種算法和文獻[22]中兩種加速算法求解一組半徑下的約簡，并對這5種方法求解一組半徑下約簡的總時間消耗和平均時間消耗進行對比。詳細的實驗結果見表2和表3。

表2 約簡求解的總時間消耗/s

表3 約簡求解的時間消耗/s的均值和標準差

觀察表2和表3，可以得到如下結論：

(1)分別使用算法2和算法3以及文獻[22]中的兩種加速算法求解30個半徑下的約簡時，所消耗的總時間遠小于利用算法1求解該組半徑下的約簡消耗的時間總和。相較于文獻[22]中的算法2和算法3，利用文中所提的加速策略求解該組半徑下的約簡時，所消耗的總時間相對較高。這主要是因為在使用加速策略求解約簡的過程中，動態獲取樣本的偽標簽會帶來額外時間消耗，這是由偽標簽鄰域粗糙集模型本身的特性所決定的。

(2)利用文獻[22]中的算法2和算法3求解一組半徑下的約簡，其時間消耗的均值較小，且具有較小的標準差。相較于算法1，利用算法2和算法3求解約簡的消耗時間的平均值和標準差相對較小。由此可知，相較于算法1，所提加速策略和文獻[22]中加速算法均有助于降低求解一組半徑下約簡的時間消耗。

3.2 分類準確率的比較

在本小節實驗中，將利用文中3種不同算法和文獻[22]中的兩種加速算法求解一組半徑下的約簡，并比較這5種方法所得約簡在測試集上的分類性能。實驗中使用的分類器為KNN分類器，K的取值為3。詳細的實驗結果見表4和表5。值得注意的是，表4比較的是這5種方法在該組半徑下得到的分類準確率的最大值，而表5比較的是該組半徑下得到的分類準確率的均值和標準差。

表4 分類準確率的最大值比較

表5 分類準確率的均值和標準差比較

觀察表4和表5，可以得到如下結論：

(1)相較于算法1和文獻[22]中的兩種加速算法，利用算法2或算法3得到的約簡結果對測試集進行分類，能得到略高的分類準確率。而在多數數據集上利用算法1得到的分類準確率略高于或接近于利用文獻[22]中的算法2和算法3得到的分類準確率，這主要是因為偽標簽策略的引入，有助于提高鄰域關系的分辨能力，進而有利于得到具有較好分類能力的約簡。

(2)利用算法2求解的約簡結果對測試集進行分類，得到的分類準確率的均值高于利用算法1和文獻[22]中的兩種加速算法得到的分類準確率的均值，而利用算法3在多數數據集上得到的分類準確率的均值略高于利用算法1和文獻[22]中的算法3得到的分類準確率的均值。此外，利用算法2得到的分類準確率的標準差小于利用算法1和文獻[22]中的兩種加速算法得到的分類準確率的標準差，而通過算法3在多數數據集上得到的分類準確率的標準差略低于或接近于利用算法1和文獻[22]中的算法3得到的分類準確率的標準差。由此可知，相較于算法1和文獻[22]中兩種加速算法，所提加速策略不會降低約簡的分類能力，并且利用所得的約簡對測試集進行分類，能得到相對較穩定的分類結果。

3.3 G-mean比較

在本節實驗中，為比較約簡的分類性能，除分類準確率外，將采用G-mean對約簡結果提供的分類能力進行對比。因此，在實驗中將根據文中3種算法和文獻[22]中兩種加速算法在訓練集上得到的約簡結果對測試集中的樣本進行分類，并根據分類結果和樣本的真實標簽計算G-mean。類似于3.1節和3.2節，該組半徑下G-mean的最大值、均值以及標準差將用于最終比較。詳細的比較結果見表6和表7。

表6 G-mean的最大值比較

表7 G-mean的均值和標準差比較

觀察表6和表7，可以得到如下結論：

(1)利用算法2或算法3計算約簡，然后對測試集進行分類并計算G-mean，相較于表6中的其它3種算法，能得到略高的G-mean值。

(2)通過算法2得到的G-mean均值高于利用算法1和文獻[22]中的兩種加速算法得到的G-mean均值，且其標準差相對較小。而通過算法3在大多數數據集上得到的 G-mean 均值略高于利用算法1和文獻[22]中算法3得到的G-mean均值，并且其標準差相對較小。由此可知，相較于使用啟發式算法和文獻[22]中兩種加速算法，使用文中所提加速策略在計算一組半徑下的約簡時，所得約簡的分類性能并不會降低，且利用約簡結果進行分類，得到的分類結果相對較穩定。

4 結束語

在基于偽標簽鄰域粗糙集的多個半徑下進行屬性約簡時，往往需要在每個半徑上遍歷所有的屬性來尋找滿足約束條件的屬性子集。顯然，這一方法求解約簡的時間消耗會隨著半徑個數的增加而增長。鑒于此，基于啟發式方法的搜索過程，通過減少屬性遍歷的規模，設計了屬性約簡加速策略。這一策略通過在前一個半徑下的約簡結果之上求解當前半徑下的約簡，來減少求解約簡的時間消耗，進而提供加速的效果。此外，實驗結果表明所提加速策略可以減少求解一組半徑下約簡所消耗的時間，并且不會降低約簡提供的分類能力。在本文的基礎上，下一步的工作有：

(1)文中僅使用了偽標簽近似質量作為屬性約簡的度量，進一步將采用其它度量如偽標簽條件熵、偽標簽鄰域決策錯誤率等構造適應度函數，并進行相應的加速算法設計。

(2)文中僅使用了偽標簽鄰域粗糙集設計屬性約簡的加速策略，進一步將在其它粗糙集模型如K近鄰粗糙集[9]中考慮相應的加速策略。