鄰域粗糙集屬性約簡方法研究

傅 凡，李京政，竇慧莉

（1.江蘇省光電子技術中心江蘇鎮江212000；2.江蘇科技大學計算機學院，江蘇鎮江212003）

經典Pawlak粗糙集模型是建立在等價關系基礎上的，適用于處理離散型數據，不適用于直接處理現實中廣泛存在的數值型數據，而將數值型數據離散化會導致數據信息的丟失。鑒于此，眾多學者提出了多種粗糙集拓展模型[2-6]，例如模糊粗糙集，鄰域粗糙集等，其中，鄰域粗糙集從使用距離構建鄰域的角度出發，其直觀簡潔的形式以及廣泛的應用范圍得到了很多學者的關注。

在粗糙集的研究進程中，屬性約簡[7-13]一直是重要研究內容。所謂屬性約簡，就是依據粗糙集理論中的某種評價函數設置一個約束條件，使得刪除數據中的無關/冗余屬性后能夠滿足這一約束，其目的是簡化后續問題處理、加速問題求解或提升學習模型的泛化性能。目前在粗糙集理論中常用的評價函數有近似質量[14]、條件熵、近似分布[15]等，約束條件一般有保持度量不變或使得度量指標的變化在給定閾值范圍內?？梢灾?，基于一種評價函數的屬性約簡求解出的屬性子集可以保證對應的度量指標在約束條件內。從多準則，多視角考慮，評價函數的多樣性會對約簡結果產生的影響也是研究的主要問題，基于一種評價函數的屬性約簡求解出的屬性子集是否能滿足其它度量指標的約束條件，這也為考慮多個評價函數的屬性約簡提供一個新的方向。

1 鄰域粗糙集與鄰域分類器

在鄰域粗糙集中，一個決策系統可以表示為二元組DS=＜U，AT∪D＞，其中U是非空有限的樣本集合，AT是所有條件屬性集合，D=g0gggggg表示決策屬性的合集且AT∩D=?。?xi∈U，d（xi）是樣本xi的類別標記。鄰域是通過給定半徑考察樣本的鄰居。不妨假設M=（rij）n×n為論域上的距離矩陣，rij表示樣本xi與xj之間的某一種距離度量，給定參數δ∈[0，1]，?xi∈U，xi的鄰域半徑為：

δA（xi）表示在樣本xi鄰域半徑內的所有樣本。

定義1 令DS=＜U，AT∪g0gggggg＞為一決策系統，?A?AT，根據屬性集合A可以得到所有樣本之間的距離矩陣，?xi∈U，?X?U，X的鄰域下近似集與上近似集分別定義如下：

定義2給定一個決策系統DS，?A?AT，?X?U，X相對于A的近似質量為：

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

在鄰域粗糙集的基礎上，文獻[16]設計出鄰域分類器進行分類學習研究，算法1給出了鄰域分類器的詳細流程。

算法1：鄰域分類器

輸入：決策系統DS，待預測樣本xi，鄰域半徑參數δ。

輸出：樣本的預測類別標記PAT(xi)。

步驟1：?xj∈U，計算δAT(xi)；

步驟 2：?Xp?U/IND(g0gggggg)，計算Pr(Xp,δAT(xi))=；

步 驟 3：Xq=arg max{Pr(Xp,δAT(xi))| ?Xp∈U/IND(g0gggggg)}；

步驟4：PAT(xi)=q，輸出ρAT(xi)。

利用鄰域分類器，相應的，文獻[16]進一步給出了鄰域決策錯誤率的概念，以下是鄰域決策錯誤率的形式化定義。

定義3令DS為一決策系統，決策系統的鄰域決策錯誤率為：

顯然，這是一種留一驗證方法。從分類學習的視角來看，鄰域決策錯誤率越低，表明分類性能越好。

2 屬性約簡

定義4給定一決策系統DS，?A?AT，A被當作約簡當且僅當f（A，D）=f（AT，D）且?B?A，f（B，D）≠f（AT，D）。

定義4所示的屬性約簡定義是一個能夠保持決策系統中某種度量不發生變化的最小屬性子集，其中，f（A，D）表示利用屬性集合A的評價函數，以此求得在屬性子集上的某種度量指標，這種度量指標可以是近似質量，鄰域決策錯誤率等。進一步考察屬性的重要度，?B∈AT且對于任意的a∈AT-B，如果f（B∪{a}，D）=f（B，D），那么就表明屬性a對于計算某種度量沒有帶來任何貢獻，a是冗余的；如果f（B∪{a}，D）≠f（B，D），那么就表示加入屬性a后對于計算這種度量產生了影響?？蓸嫿ㄈ缦滤镜膶傩灾匾龋?/p>

根據上述屬性重要度，算法2構建了一個啟發式求解屬性約簡的過程，其目標是獲得以定義4為依據的約簡。

算法2：啟發式算法

輸入：鄰域決策系統DS=＜U,AT∪D＞。

輸出：約簡red。

步驟1：令red←?；

步驟2：若f(red,D)≠f(AT,D)，則執行以下循環，否則執行步驟3；

(1)?ai∈AT-red，計算 Sig(ai,red,D)；

(2)選擇aj，滿足 Sig(aj,red,D)=max{Sig(ai,red,D)|?ai∈AT-red}，令red=red∪{aj}，返回步驟 2；

(3)計算f(red,D)；

步驟3輸出red。

3 實驗分析

利用算法2，在求解屬性約簡的過程中使用了近似質量與鄰域決策錯誤率兩種度量準則，分別記為近似質量約簡（AQR），鄰域決策錯誤率約簡（NDERR）。實驗中選取了6組UCI數據集，表1列出了它們的基本信息。使用歐氏距離構造樣本之間的距離矩陣，鄰域半徑參數δ分別設定為0.1、0.2、0.3。在此基礎上進行了2組實驗，分別比較了利用算法AQR與NDERR求得的近似質量和鄰域決策錯誤率。

表1 實驗數據的基本信息

表2列出了利用近似質量約簡與鄰域決策錯誤率約簡求得的近似質量的對比；表3列出了利用近似質量約簡與鄰域決策錯誤率約簡求得的鄰域決策錯誤率的對比。

表2 兩種約簡在近似質量的對比

觀察表2與表3可以得到如下結論，在大多數數據集上，由近似質量約簡求得的近似質量都要高于由鄰域決策錯誤率約簡求得的近似質量，平均要高0.09左右。相應的，由鄰域決策錯誤率約簡求得的鄰域決策錯誤率要低于由近似質量約簡求得的鄰域決策錯誤率，平均要低0.03左右，除了在數據Diabetic Retinopathy Debrecen上兩者相等以外。也就是說，近似質量約簡并不能保證約簡結果在鄰域決策錯誤率上能夠滿足約束條件，鄰域決策錯誤率約簡也不能保證約簡結果在近似質量上能夠滿足約束條件。

4 結 論

在鄰域粗糙集上考慮基于一種評價函數的屬性約簡結果可以滿足相應度量指標的約束條件，不能夠保證在其他度量指標的約束條件。一方面，我們證實了傳統屬性約簡的有效性；另一方面，由于基于一種評價函數的屬性約簡在度量指標的單一性，考慮多個評價函數的屬性約簡方法也成為一個新的研究方向。