基于模糊鄰域粗糙集的啟發式屬性約簡算法

任曉霞，薛 凡

REN Xiaoxia1,XUE Fan2，3

1.張家口學院 理學院，河北 張家口 075000

2.武漢大學 計算機學院 軟件工程國家重點實驗室，武漢 430072

3.黃淮學院 創新創業學院，河南 駐馬店 463000

1.College of Science,Zhangjiakou University,Zhangjiakou,Hebei 075000,China

2.State Key Laboratory of Software Engineering,School of Computer,Wuhan University,Wuhan 430072,China

3.School of Innovation and Entrepreneurship,Huanghuai University,Zhumadian,Henan 463000,China

1 引言

屬性約簡即特征選擇，是粗糙集理論中一項重要的應用[1]，由于現實中很多的數據集存在著大量的冗余屬性，屬性約簡其主要思想是在保持已有知識的分類能力不變的情形去消除那些冗余屬性，這樣可以降低數據集的規模，從而提高知識發現的效率。目前，如何構造出優越的啟發式函數對數據集中的屬性進行重要度評估是目前屬性約簡研究的重點[2-5]。

粗糙集理論[1]是波蘭學者Pawlak提出的一種處理不確定性數據的數學方法，由于它不需要數據之外的任何先驗信息，因此目前已廣泛運用于數據的屬性約簡[2-5]中。傳統的粗糙集理論建立在等價關系基礎上，僅適用于離散型屬性。為了解決這個問題，近年來，學者們提出了多種改進的模型，使得粗糙集理論可以很好地處理數值型數據。例如，運用鄰域關系取代等價關系，鄰域粗糙集模型[6-7]是目前處理數值型數據的一種常用模型，Dubois等[8]學者將模糊集融入粗糙集理論中，提出了模糊粗糙集模型。這兩種模型都是處理數值型數據常用且有效的方法，基于這兩種模型的屬性約簡算法也被大量提出。例如，Hu等[3]學者運用屬性依賴度作為啟發式函數提出了基于鄰域粗糙集模型的混合屬性約簡算法。段潔等[9]學者提出了鄰域粗糙集的多標記屬性約簡。Wang[10-13]等學者運用屬性依賴度提出了基于改進模糊粗糙集的特征選擇算法等。對于目前這些眾多的算法，它們大多是以依賴度為啟發式函數來度量屬性。

在文獻[13]中，Wang將鄰域粗糙集與模糊粗糙集結合，提出了模糊鄰域粗糙集模型，并根據依賴度度量構造出了相應的屬性約簡算法。徐風等[14]學者證明了模糊鄰域粗糙集模型對信息系統具有更好的不確定性度量效果。由于依賴度是通過近似逼近的角度對屬性進行評估，但是這種方法顯得過于單一，并不能對屬性有著更精確的度量。因此本文在此基礎上重新定義了依賴度，并且提出了模糊鄰域粒度的概念，然后將這兩種方法用于屬性重要性的評估，提出相應的屬性約簡算法。最后進行一系列實驗來比較本文所提出的算法與目前已有算法的屬性約簡性能，從而驗證本文算法的有效性和優越性。

2 基本理論

在機器學習和數據挖掘等領域中，結構化的數據表示成信息系統IS=(U,AT,V)的形式，其中U被稱為論域，AT為屬性集，V為屬性的值域。若信息系統中屬性集AT=C?D，且C?D=?，其中C,D分別被稱為條件屬性和決策屬性，那么稱這個信息系統為決策信息系統(DIS)。

模糊集理論[15]是在傳統明確集基礎上的推廣，定義論域U 上的函數映射(?):U→[0,1]，被稱為U 上的模糊集，(x)稱為對象x關于模糊集的模糊隸屬度，U上的所有的模糊集組成的全集表示為F(U)。

設鄰域信息系統NIS=(U,AT,V)，U為論域，AT為全體屬性集且均為數值型數據，V為屬性的值域。由B?AT在U上誘導的模糊相似關系R滿足?x∈U，R(x,x)=1 ，并且對于?a∈AT ，由 a 誘導的模糊相似關系為，并且 R與之間滿足對象 x 在 U 上關于 B 的模糊信息粒定義為 [x](y)=R(x,y)。

定義1[12-13]設鄰域決策信息系統NDIS=(U,C?D,V,f)，決策屬性劃分為，R是由B在U上誘導的模糊相似關系，那么?x∈U的模糊決策定義為：

定義2[13-14]設鄰域信息系統NIS=(U,AT,V,f)，R是由B?AT在U上誘導的模糊相似關系，?x∈U關于R的模糊鄰域定義為：

這里的δ被稱為模糊鄰域的鄰域半徑，滿足0≤δ≤1。通過模糊相似關系R和鄰域半徑δ就可以確定?x∈U的模糊鄰域。

定義3[13-14]對于鄰域決策信息系統NDIS=(U,C?D,V,f)，B?C，決策屬性劃分為D2,…,Dm}，其對應的模糊決策為是由B在U上誘導的模糊相似關系，令鄰域半徑為δ，那么決策類Di關于R的模糊鄰域粗糙集的下近似和上近似分別定義為：

3 依賴度與模糊鄰域粒度

在粗糙集理論中，屬性依賴度[2-5]是一個非常重要的概念，它反映了條件屬性與決策屬性之間的關系程度，是構造基于粗糙集理論屬性約簡算法的關鍵[3，5]。本文這里定義基于模糊鄰域粗糙集模型的依賴度。

定義4對于鄰域決策信息系統NDIS=(U,C?D,V,f)，B?C，決策劃分為是由B在U上誘導的模糊相似關系，設鄰域半徑δ，那么決策屬性集D關于B的依賴度定義為：

依賴度表示的是包含在正區域的對象占論域對象的比例，因而可以作為條件屬性與決策屬性之間的關系程度的度量[6]。根據定義3可以看出，模糊相似關系RB和鄰域半徑δ對依賴度有著很重要的影響。

下文中，將適當地省略鄰域半徑δ的標記。

性質1對于鄰域決策信息系統NDIS=(U,C?D,V,f)，B1?B2?C ，那么屬性依賴度滿足 DE(D)≤DE(D)。

證明 由于 B1?B2?C ，那么顯然有根據定義2可以得到，所以根據定義3可推出滿足，因此，即滿足關系證畢。

性質2對于鄰域決策信息系統NDIS=(U,C?D,V,f)，B?C ，鄰域半徑 δ1,δ2滿足 δ1≤δ2，那么屬性依賴度滿足

證明 由于 δ1≤δ2，根據定義2有，所以對于滿足，因而，即 滿 足 關 系證畢。

粒計算理論[16]是智能信息處理中一種很重要的研究方法，其中粒結構模型[17-18]是該理論的一種重要表現形式，同時也是評價信息系統分類能力的一個重要的指標。目前學者們提出了多種粒結構模型[14，17-18]，本文這里在模糊相似關系的基礎上提出一種新的粒結構模型。

定義5對于鄰域決策信息系統NDIS=(U,C?D,V,f)，B?C，鄰域半徑為δ，由U在模糊相似關系R上誘導的模糊鄰域粒結構定義為：

類似于模糊粗糙集中信息粒度[18]的定義，這里給出基于模糊鄰域粒結構的知識粒度。

性質3對于鄰域決策信息系統NDIS=(U,C?D,V,f)，B1?B2?C，那么模糊鄰域粒度滿足GK(B2)≤GK(B1)。

證明 由于 B1? B2? C ，那么 R? R，根據定義2可以得到 ?x∈U ，[x]?[x]，所以由定義6可以容易得到GK(B2)≤GK(B1)。證畢。

性質4對于鄰域決策信息系統NDIS=(U,C?D,V,f)，B?C ，鄰域半徑 δ1,δ2滿足 δ1≤δ2，那么模糊鄰域粒度滿足GKδ1(B)≤GKδ2(B)。

證明 由于 δ1≤δ2，根據定義2有那么由定義6可以容易得到GKδ1(B)≤GKδ2(B)。

在定義4中，依賴度是通過近似逼近的視角去對條件屬性集進行評估，而定義6中的模糊鄰域粒度可以體現出條件屬性集對系統的分類性能，這兩種方法表現出了對屬性集的不同視角評估，因此將它們結合起來可以更為全面的評估屬性，達到更好的屬性重要度度量，同時可以體現出兩種方法的優越性[15，18]。

定義7對于鄰域決策信息系統NDIS=(U,C?D,V,f)，B?C，R是由B在U上誘導的模糊相似關系，設鄰域半徑δ，定義基于模糊鄰域粗糙集的依賴度和知識粒度混合度量為：

一般情況下，信息系統的論域非空，因此模糊鄰域粒度GKδ(B)≠0。結合性質1～4，可以發現，當鄰域半徑δ不變，隨著屬性集B的逐漸增大，Hδ(B)也是逐漸增大的。當屬性集B不變時，隨著鄰域半徑δ的逐漸增大，Hδ(B)是逐漸減小的。特別的，當B=?時，Hδ(B)=0 。

本文依據定義7的混合度量給出信息系統的屬性約簡如定義8所示。

定義8對于鄰域決策信息系統NDIS=(U,C?D,V,f)，若B?C是該信息系統的一個屬性約簡集當如下兩點同時成立：

定義9對于鄰域決策信息系統NDIS=(U,C?D,V,f)，B?C，R是由B在U上誘導的模糊相似關系，設鄰域半徑δ，對于?a∈B在D下關于B的第一種屬性重要度定義為：

定義10對于鄰域決策信息系統NDIS=(U,C?D,V,f)，B?C，R是由B在U上誘導的模糊相似關系，設鄰域半徑δ，對于?a∈C-B在D下關于B的第二種屬性重要度定義為：

這兩種屬性重要度的定義表示了兩種不同的含義，定義9表示的是屬性子集B中內部屬性a關于B的屬性重要度，而定義10表示的是屬性子集B的外部屬性a關于B的屬性重要度。

4 啟發式屬性約簡算法

屬性約簡作為粗糙集理論的一個重要的應用而得到學者的廣泛關注，如何對信息系統中屬性進行更精準的重要度評估一直是該方向的研究重點[2-5]。借助定義9和定義10的兩種屬性重要度作為啟發式函數，這里給出一種基于模糊鄰域粗糙集的啟發式屬性約簡算法。

對于鄰域決策信息系統NDIS=(U,C?D,V,f)，B?C，鄰域半徑δ，算法1給出的是模糊鄰域粗糙集的模糊粒度度量計算方法。

算法1基于模糊鄰域粗糙集的依賴度和模糊鄰域粒度混合度量Hδ(B)。

輸入：NDIS=(U,C?D,V,f)，B?C，鄰域半徑δ。

輸出：Hδ(B)。

步驟5根據定義7返回結果Hδ(B)。

算法2基于模糊鄰域粗糙集的啟發式屬性約簡算法。

輸入：NDIS=(U,C?D,V,f)，鄰域半徑δ。

輸出：屬性約簡red。

步驟1初始化red=?，Hδ(?)=0。

步驟2對于?a∈C-red，根據定義10計算每個屬性重要度，選擇屬性重要度最大的那個屬性，記為′。

步驟4對于?a∈red，找出所有使Hδ(red-{a})=Hδ(C)成立的屬性，記Π←?，將這些屬性添加入Π中，如果Π為空集，輸到步驟6，否則轉到步驟5。

步驟6返回red，算法終止。

步驟2和步驟3通過屬性重要度函數對數據集的屬性集進行啟發式搜索，是一個不斷迭代的過程，算法剛開始時候，red=?，Hδ(red)=0，然后通過啟發式函數每次迭代選擇出一個屬性，并將這個屬性添加入約簡集red中，根據定義7，當約簡集red逐漸增大時，其Hδ(red)的值也是增大的，經過不斷迭代直到滿足Hδ(red)=Hδ(C)，此時達到收斂條件。正是由于 Hδ(?)函數的單調性，因此算法2肯定是收斂的。在步驟2中，算法每次讓屬性重要度達到最大的屬性加入red中，這樣就加速了算法2的收斂速度。算法2收斂時，得到的集合red是全集C的一個約簡，但不一定是一個最優的約簡，因為集合red內部可能存在屬性之間的依賴導致某些屬性冗余[3]，因此該算法在步驟4中進行了進一步的屬性剔除，從而得到最終的約簡結果，這個結果既保持了原度量結果的收斂性，又保證了約簡集red的極小性。

根據算法1的時間復雜度和文獻[3]，算法2的時間復雜度為 O(c2?n2)。

5 實驗分析

為了驗證本文所提出的啟發式屬性約簡算法具有一定的優越性，本實驗將所提出的算法與其他的相關算法對同一組數據集進行實驗，然后通過實驗結果的約簡集、約簡耗時和約簡集的分類精度來比較算法的優越性。參與實驗的數據集均選取自UCI標準數據集庫，具體信息如表1所示。

表1 UCI數據集

實驗中選取參與比較的相關算法分別為：一種相對決策熵度量的高效特征選擇算法（算法1）[5]，基于改進模糊粒化的模糊粗糙集屬性約簡算法（算法2）[12]，基于鄰域組合測度的屬性約簡算法（算法3）[19]，基于改進模糊粗糙集的一種模糊條件熵的特征選擇算法（算法4）[20]，基于鄰域屬性區分度量的屬性約簡算法（算法5）[21]，基于改進鄰域粒化的模糊熵特征選擇算法（算法6）[22]，記本文所提出的算法為算法7。

在這些算法中，算法2、算法4、算法5和算法6是基于單一度量方法對屬性進行度量，而算法1、算法3和算法7是通過多種方法進行組合來度量屬性。在實驗開始之前，為了消除屬性量綱的影響，所有數據集的屬性值均被歸一化到[0，1]區間。算法1是針對離散型數據集的特征選擇算法，因此在運用算法1前需將連續數據進行離散化處理。在實驗分析過程中，需要運用分類器來評估約簡結果的優劣，本實驗采用支持向量機（SVM）分類器和分類決策樹（CART）分類器。各個算法采用Matlab2014b進行編程實現，實驗運行的硬件環境為Intel i3 7500 3.40 GHz的處理器，內存為8 GB的個人主機。

對于本文所提出的屬性約簡算法，在開始之前需要確定鄰域半徑δ的值，并且該值的選取對最終的屬性約簡結果有著很重要的影響，因此為了得到最優的實驗結果，本實驗嘗試通過取多個值分別進行實驗來選擇最優結果，即讓鄰域半徑從區間[0，1]按0.05的間隔分別取值，并對每個鄰域半徑分別進行實驗，然后運用SVM分類器對每個鄰域半徑下的屬性約簡結果進行分類訓練，從而得到對應實驗結果的分類精度，本文所提出的算法最終約簡結果選取為分類精度最高的屬性子集。表2所示的是7種算法約簡結果集合基數的大小比較。

表2 7種算法的約簡集大小比較

觀察表2可以看出，7種算法得到的約簡結果均小于原數據集的屬性總數，部分數據集遠小于原數據集，這說明了現實中很多數據集普遍存在著很多的冗余屬性，從而體現出屬性約簡在數據預處理中的重要性，同時也說明這7種算法的有效性。對比這7種算法的屬性約簡結果，可以看出算法3和本文所提出的算法7約簡得到的屬性子集大小整體比其他算法要小一些，例如數據集wdbc、sonar、move和gerbox。這主要是由于這兩種算法是基于多種度量方法的啟發式屬性約簡，在約簡過程中對候選屬性具有更好的度量效果，降低了度量偏差，因此能夠得到更小的約簡集。這表明，多種度量方法的結合能對屬性達到更好的評估，從而鑒別出信息系統更為關鍵的屬性。同時，本文所提出的算法7在多數數據集具有更小的約簡結果，這說明了基于模糊集的模糊粒化比傳統的明確集具有更好的集合隸屬關系表達，屬性的度量效果更佳。另外觀察表2還可以發現，算法1在多數數據集的約簡結果較大，這主要是由于算法1在屬性約簡前數據集經過了離散化處理，離散化的過程可能導致了連續型數據集分類信息的丟失，這樣不利于數據集的屬性約簡。通過屬性約簡結果，證明了組合度量方法具有更好的屬性評估性能，能夠搜索到更優的屬性子集，并且基于模糊集的方法具有更精準的度量結果。

接下來將比較各個算法所選擇出約簡集的優越性。本實驗利用SVM和CART兩種分類器分別對7種算法的屬性約簡結果運用十折交叉的方法對樣本數據進行分類學習訓練，然后計算出樣本數據的分類精度，其結果如表3和表4所示。

在表3和表4中，用“*”標記的分類精度為7種算法中的最大值。觀察表3和表4可以發現，7種算法的分類精度結果差別不是很大，均接近原始數據集的分類精度，并且有一些算法在部分數據集的分類精度高于原始數據集的分類精度，這便體現了屬性約簡算法的有效性。仔細比較分析可以看出，算法1、算法3和算法7約簡結果對應的分類精度在整體上同樣比其他算法約簡結果的分類精度要高一些，這說明了，通過多種度量方法結合后約簡出來的屬性子集能夠達到更好的分類效果，從而進一步證明了組合度量對屬性評估的優越性。同時，算法7在部分數據集得到的約簡結果具有更高的分類精度，說明本文所提出的屬性約簡算法在約簡結果方面具有更好的約簡性能。

表3 7種算法約簡結果在SVM下的分類精度比較%

表4 7種算法約簡結果在CART下的分類精度比較 %

圖1 算法效率比較

算法的時間復雜度是評估算法優劣的一項重要指標，因此接下來將比較7種算法的約簡效率。在實驗中，為了防止偶然性，讓每種算法分別對每個數據集重復約簡多次，取多次屬性約簡時間開銷的平均值作為對應數據集屬性約簡的時間結果，具體結果如圖1所示。觀察圖1可以發現，在各個數據集的屬性約簡時間開銷結果中，算法1、算法3和算法7結果略多于其他算法，這主要是由于這三種算法的評估函數是多種方法的結合，在進行計算方法無疑會增加時間的開銷，但是這三種算法都經過了優化，多種度量的計算都避免了重復計算，尤其是本文所提出的屬性約簡算法，其中依賴度和模糊鄰域粒度的計算都需要計算出每個對象的模糊鄰域粒，因此可以將依賴度和模糊鄰域粒度進行同時計算，這樣可以大大降低計算量，因此所提出的算法同樣具有較高的時間效率。

綜合以上算法的約簡結果和算法的運行效率，可以看出，本文所提出的算法通過多個度量方法可以對信息系統的屬性達到更好的度量效果，其約簡結果優于單一度量的啟發式屬性約簡，同時本文所提出的算法是運用模糊集的視角去構造兩種度量，同樣具有更佳的評估效果。此外實驗結果也表明本文所提出的算法具有較高的約簡效率。另一方面，本文所提出的算法在進行實驗時，鄰域半徑是一個需要設定的參數，這里是通過重復實驗多次才能得到最優的結果，很難直接快速地得到合適的鄰域半徑取值，因此這也是本文所提出算法的一個的不足之處。

由于鄰域半徑δ對實驗結果有著很重要的影響，因此接下來將探究鄰域半徑δ對實驗結果是如何影響的，并且分析其取值問題，為以后的研究提供參考。圖2給出了數據集屬性約簡集大小、SVM分類精度和鄰域半徑之間的關系。觀察可以發現，隨著鄰域半徑的逐漸增大，算法約簡出的屬性子集大小是逐漸增大的，而分類精度剛開始逐漸增大，但是當鄰域半徑達到0.2～0.3時，其分類精度開始趨于穩定或略有降低，這主要是由于，剛開始時候約簡集較小，未能達到最佳的分類效果，所以分類精度較低，但是當屬性子集較大時，較多的屬性可能會帶來噪聲數據的干擾，反而會不利于數據的分類，從而出現了分類精度降低的情形。根據圖2的實驗結果，本文所提出的屬性約簡算法中鄰域半徑可以取[0.2，0.3]之間較為適宜。

6 結語

屬性約簡是一項重要的數據預處理技術，如何構造有效的屬性評估方法一直是目前研究的重點，在基于粗糙集理論的屬性約簡算法中，本文針對目前屬性評估單一性的問題，在模糊鄰域粗糙集模型中定義屬性依賴度的概念，并基于此提出了模糊鄰域粒度度量，由于依賴度和模糊鄰域粒度是兩種不同視角的屬性評估方法，因此本文將兩種方法結合提出一種新的啟發式屬性約簡算法。最后UCI實驗結果證明了所提出算法的適用性和優越性。由于本文提出的算法只適用于數值型數據，因此接下來探索可以適用混合型數據的屬性約簡算法。

圖2 各個數據集實驗結果

參考文獻：

[1]Pawlak Z.Rough sets[J].International Journal of Computer and Information Sciences，1982，11（5）：341-356.

[2]Shao Mingwen，Li Kewen.Attribute reduction in generalized one-sided formal contexts[J].Information Sciences，2016，378：317-327.

[3]Hu Qinghua，Yu Daren，Liu Jinfu，et al.Neighborhood rough set based heterogeneous feature subset selection[J].Information Sciences，2008，178（18）：3577-3594.

[4]陳昊，楊俊安，莊鎮泉，等.變精度粗糙集的屬性核和最小屬性約簡算法[J].計算機學報，2012，35（5）：1011-1017.

[5]Jiang Feng，Sui Yuefei，Zhou Lin.A relative decision entropy-based feature selection approach[J].Pattern Recognition，2015，48（7）：2151-2163.

[6]D’Eer L，Restrepo M，Cornelis C，et al.Neighborhood operators for covering-based rough sets[J].Information Sciences，2016，336：21-44.

[7]徐怡，楊宏健，紀霞.基于雙重粒化準則的鄰域多粒度粗糙集模型[J].控制與決策，2015，30（8）：1469-1478.

[8]Dubois D，Prade H.Rough fuzzy sets and fuzzy rough sets[J].International Journal of General Systems，1990，17（2/3）：191-208.

[9]段潔，胡清華，張靈均，等.基于鄰域粗糙集的多標記分類特征選擇算法[J].計算機研究與發展，2015，52（1）：56-65.

[10]Wang Changzhong，Cui Xinhua，Bao Wenying，et al.Attribute reduction of decision table based on similar relation[C]//2012 International Conference on Machine Learning and Cybernetics，2012.

[11]Wang Changzhong，Qi Yali，He Qian.Attribute reduction using distance-based fuzzy rough sets[C]//International Conference on Machine Learning and Cybernetics，Guangzhou，2015：860-865.

[12]Wang Changzhong，Qi Yali，Shao Minweng，et al.A fitting model for feature selection with fuzzy rough sets[J].IEEE Transactions on Fuzzy Systems，2016：1-13.

[13]Wang Changzhong，Shao Minweng，He Qian，et al.Feature subset selection based on fuzzy neighborhood rough sets[J].Knowledge-Based Systems，2016，111：173-179.

[14]徐風，姚晟，紀霞，等.基于模糊鄰域粗糙集的信息系統不確定性度量方法[J].南京大學學報：自然科學版，2017，53（5）：926-936.

[15]Zadeh L A.Fuzzy sets[J].Information&Control，1965，8（3）：338-353.

[16]Zadeh L A.Some reflections on soft computing，granular computing and their roles in the conception，design and utilization of information/intelligent systems[J].Soft Computing，1998，2（1）：23-25.

[17]Pedrycz W，Succi G，Sillitti A，et al.Data description：A general framework of information granules[J].Knowledge-Based Systems，2015，80：98-108.

[18]Zhang Xianyong，Miao Duoqian.Three-layer granular structures and three-way informational measures of a decision table[J].Information Sciences，2017，412：67-86.

[19]何松華，康嬋娟，魯敏，等.基于鄰域組合測度的屬性約簡方法[J].控制與決策，2016，31（7）：1225-1230.

[20]Zhang Xiao，Mei Changlin，Chen Degang et al.Feature selection in mixed data：A method using a novel fuzzy rough set-based information entropy[J].Pattern Recognition，2016，56（1）：1-15.

[21]Wang Changzhong，Hu Qinghua，Wang Xizhao，et al.Feature selection based on neighborhood discrimination index[J].IEEE Transactions on Neural Networks and Learning Systems，2017（99）：1-14.

[22]姚晟，徐風，趙鵬，等.基于改進鄰域粒的模糊熵特征選擇算法[J].南京大學學報：自然科學版，2017，53（4）：802-814.