基于偽標簽局部集成投票屬性約簡*

王東杰

（江蘇科技大學 鎮江 212003）

1 引言

Pawlak［1］提出的粗糙集理論是經典粗糙集的延伸。它已被證明在數據挖掘［2～3］，人工智能［4］等學科中具有重要作用。

盡管如此，粗糙集理論在實踐中仍有許多局限性需要解決。例如基于等價關系的經典粗糙集僅適用于離散數據，而數值數據［5～6］在實際應用中隨處可見。基于此，作為廣義粗糙集模型的一個重要組成部分，Hu等［7］提出的鄰域粗糙集模型在粗糙集理論中取得了巨大成功。

眾所周知，屬性約簡作為粗糙集核心內容之一，在鄰域粗糙集中也獲得了廣泛關注。屬性約簡就是根據給定的度量準則去除不相關屬性，以滿足相應的約束條件。廣泛接受的屬性約簡策略包括窮舉式算法和啟發式算法［8～9］，然而很多窮舉式算法和啟發式算法將所有樣本作為一個整體，忽視了不同樣本具有的決策類別不同這一情況。為解決這一問題，Qian等［10］提出的局部鄰域粗糙集屬性約簡算法考慮了不同決策類對不同關鍵屬性的需求。

然而，局部鄰域粗糙集屬性約簡算法仍然面臨著以下兩個問題：1）經典鄰域粗糙集沒有關注到半徑變化對樣本標簽的影響，以致于不同標簽樣本被劃分到相同鄰域；2）傳統的屬性約簡算法只有一個約束條件，缺乏適用性［11］。為了能夠同時解決上述兩個問題，筆者利用楊等［12］提出的偽標簽策略，設計了一種基于偽標簽局部集成投票的約簡算法。基于偽標簽局部集成投票的約簡算法主要步驟：首先，利用k-means聚類計算出偽標簽加入到決策系統中；其次，利用啟發式算法計算出每個決策類屬性重要度，并選取屬性重要度最大的屬性；最后，利用集成投票機制將合適的屬性添加到約簡集中［13～20］。

2 基礎知識

2.1 領域粗糙集

在粗糙集理論中，一個決策系統可以表示為一個二元組DS=＜U，AT∪｛d｝＞，其中U是所有樣本的集合，AT是條件屬性的集合，d是決策屬性。此外，?x∈U，d｛x｝表示樣本x的標簽。給定決策系統DS，當DS中的所有決策值都是離散時，可以定義不可分辨關系INDd為

顯然，INDd是一種等價關系。通過INDd可以獲得樣本U上的劃分：

?Xj∈U/INDd，Xj稱為第j個決策類。?x∈U，包含樣本x的決策類表示為［x］d。在傳統粗糙集理論中，等價類僅適用于處理離散數據，并不適用于處理連續型數據。為填補這一空白，Hu等［15］提出了鄰域粗糙集。鄰域粗糙集優勢在于：1）鄰域可以用數值數據表征樣本之間相似性距離；2）通過使用不同的半徑可以獲得不同的鄰域尺度，從而形成多粒度結構。鄰域粗糙集中鄰域關系的概念可以用條件屬性來定義。

定義1給定一個決策系統DS，?B?AT，鄰域關系可以定義為

其中ΔB(x,y)指通過B中的條件屬性表示樣本x和y之間的歐幾里德距離，δ是給定半徑，且δ≥0。遵循定義1，可以得到如下鄰域：

鄰域概念不僅可以用于構建粗糙集，還可以用于構建分類器。不同于近鄰分類方法，鄰域分類器并不指定待測樣本的鄰居個數，而是采用設定半徑的方式找到滿足約束條件的待測樣本的鄰居。可以設計如算法1所示的鄰域分類器。

算法1鄰域分類器（NEC）

輸入：訓練數據構成的數據表DS=＜U，AT∪｛d｝＞，B?AT，半徑δ，待測樣本y。

輸出：y的預測分類標簽：Pre（By）。

步驟1：?x∈U，計算樣本之間距離D（Bx，y）；

步驟2：計算測試樣本的鄰域δ（By）；

步驟4：Xk=arg max{Pr(Xi|δ(y)):?Xi∈U/INDd}；

步驟5：根據Xk找到對應的標簽，并賦值給Pre（By）；

步驟6：輸出Pre（By）。

通過比較真實標簽與鄰域分類器分得的結果，鄰域決策錯誤率可以定義如下。

定義2對于決策系統DS，?B?AT，鄰域決策錯誤率可定義為

顯然，鄰域決策錯誤率的值越小，算法的分類性能越好。

2.2 偽標簽鄰域粗糙集

經典鄰域粗糙集沒有關注到半徑變化對樣本標簽的影響，以致于不同標簽樣本被劃分到相同鄰域。為解決這一難題，楊等［12］提出偽標簽策略。與鄰域決策系統類似，偽標簽鄰域決策系統可以表示為DSP=＜U，AT∪｛d｝∪dP＞，dP是偽標簽屬性。?x∈U，d（Px）表示樣本x的偽標簽值。

定義3給定一個偽標簽決策系統DSP，?B?AT，偽標簽鄰域關系定義為

根據定義5，可以得到如下偽標簽鄰域：

3 屬性約簡

屬性約簡也稱為特征選擇，其目的是通過某些給定約束刪除冗余屬性。通過這一策略，能夠大大降低學習的難度和時間消耗。近年來，根據實際需求，已有大量學者提出了多種度量準則，例如近似質量［15］、鄰域決策錯誤率［16］等，筆者選擇鄰域決策錯誤率作為屬性約簡的約束條件。

3.1 傳統啟發式屬性約簡

在啟發式屬性約簡中，給定一個決策系統DS，?B?AT和?a∈AT-B，如果NDER（B，d）＞NDER（AT，d），屬性a對分類精度的提高沒有貢獻；如果NDER（B，d）≤NDER（AT，d），屬性a提高了分類精度。因此根據鄰域決策錯誤率，可以得到如下屬性重要度：

以下算法2給出了一個求解啟發式約簡的具體描述。

算法2啟發式算法

輸入：決策系統DS=＜U，AT∪d｝＞，半徑δ。

輸出：一個鄰域決策錯誤率約簡red。

步驟1：計算NDER（AT，d）；

步驟2：red←?；

步驟3：WhileNDER（B，d）≤NDER（AT，d）

1）?ai∈AT-B，計算屬性ai的重要度SigNDER（ai，B，d）；

2）選出一個重要度最大的屬性b，令red=red∪｛b｝；

3）計算NDER（B，d）；

End While；

步驟4：返回red。

算法2的時間復雜度為O（|U|2×|AT|2），|U|為論域中樣本數目，|AT|為條件屬性數目。

3.2 偽標簽局部集成投票屬性約簡

經典鄰域粗糙集沒有關注到半徑變化對樣本標簽的影響，以致于不同標簽樣本被劃分到相同鄰域。另外，傳統局部算法只有一個適應度函數，導出的約簡僅考慮一個約束，致使約簡結果缺乏通用性。為了同時應對上述難題，筆者提出了一種基于偽標簽局部集成投票的約簡算法。以下給出偽標簽局部集成投票鄰域決策錯誤率的定義。

定義4給定一個偽標簽決策系統DSP，?B?AT，決策類Xi的偽標簽鄰域決策錯誤率定義如下：

給定一個決策系統DS，?B?AT，?Xj∈U/INDd，?a∈AT-B，可以得到如下屬性重要度：

以下算法3給出了一個求解偽標簽局部集成投票屬性約簡的具體描述。

算法3偽標簽局部集成投票算法

輸入：決策系統DSP=＜U，AT∪｛d｝∪dP＞，半徑δ。

輸出：約簡R。

步驟1：計算NDERP（AT，d）；

步驟2：R←?；

步驟3：For d=1 toq//q為決策類個數

1）?ai∈AT-B，計算屬性ai的重要度；

2）根據每個決策類Xi選出一個重要度最大的屬性b并記錄每個屬性的出現次數。

End For

步驟4：投票選擇頻率最高的屬性：c；

步驟5：R=R∪｛c｝；

步驟6：WhileNDERP（B，d）≤NDERP（AT，d）

Go to step 3；

End While

步驟4：返回R。

算法3的時間復雜度為O（q×|U|2×|AT|2），其中q為決策類的數目。

4 實驗分析

為了驗證上述所提偽標簽局部集成投票算法的有效性，筆者從UCI數據集中選取了五組數據，數據的基本描述如表1所列。

表1 數據集描述

實驗采用了5折交叉驗證的方法，并且選取了十個不同的半徑δ，其值分別為0.05，0.10，…，0.5。試驗過程中將實驗數據中的樣本平均分成5份，即U1，U2，…，U5。第一次使用U2∪U3…∪U5作為訓練集，使用U1作為測試集；第二次使用U1∪U3…∪U5作為訓練集，使用U2作為測試集；依次類推，第五次使用U1∪U2…∪U4作為訓練集，使用U5作為測試集。本組實驗選取了鄰域決策錯誤率作為約簡的度量準則。實驗結果如圖1所示。

圖1 分類精度對比

在以下的結果圖中，用“NDER”，“NDER local”，“NDER pl”，“NDER pl local”分別表示鄰域決策錯誤率約簡、局部鄰域決策錯誤率約簡、偽標簽集成投票鄰域決策錯誤率約簡、偽標簽局部集成投票鄰域決策錯誤率約簡。

4.1 鄰域決策錯誤率（NDER）上約簡結果的分類精度對比

觀察圖1可以發現，在10個半徑下，不難得出如下結論。

1）與傳統約簡相比，偽標簽局部集成投票的約簡算法的分類性能更好；

2）在四種算法的比較中，偽標簽局部集成投票算法的分類精度最高。

4.2 鄰域決策錯誤率（NDER）下約簡的時間消耗對比

通過觀察圖2可以發現：

圖2 時間消耗對比

1）在四種約簡算法中，利用局部約簡求解總體上需要更多的時間消耗。這主要是因為相較于傳統算法，局部算法需要考慮每一個決策類的變化；

2）與傳統局部算法相比，偽標簽局部集成投票算法明顯降低了時間消耗。

通過觀察表2可以發現：與補加偽標簽集成投票的算法相比，加上偽標簽集成投票的算法大體上降低了時間消耗。

表2 平均約簡求解時間消耗對比（單位：s）

5 結語

為了防止不同標簽樣本落入相同鄰域以及增強約簡求解的通用性，筆者提出了一種偽標簽局部集成投票算法。通過實驗分析表明，相較于傳統算法，偽標簽局部集成投票算法可以明顯提高分類性能，并且降低時間消耗。在此基礎上，筆者將進一步討論以下問題。

1）文中算法的時間消耗仍然較高，今后可以嘗試進一步降低時間消耗。

2）文中算法模型僅使用在鄰域粗糙集，今后可以嘗試使用在模糊粗糙集等模型。