F-鄰域粗糙集及其約簡

鄧志軒 鄭忠龍 鄧大勇

大數據時代下，數據快速擴展，在生產實踐中獲得的屬性越來越多.一部分屬性可能是冗余的或與分類任務無關，在進行任何進一步數據處理之前都需要將它們刪除.屬性約簡(或特征選擇) 是一種用于減少屬性的技術.其目的是找到最佳屬性子集來預測樣本類別.屬性約簡還可以促進數據可視化和數據理解[1].

屬性約簡過程中存在一個關鍵問題:屬性評估.如何有效地評估屬性是最重要的步驟之一，它直接影響分類器的性能.迄今為止已經提出了許多屬性評估準則，例如信息熵[2]、依賴性[1]、相關性[3]和一致性[4]等.通常，不同的評估標準可能導致不同的最佳特征子集.但是，每項措施都旨在確定特征子集的區(qū)分能力.

粗糙集理論[5-6]是一種有效屬性約簡工具，產生了增量式約簡[7]、動態(tài)約簡[8]、多決策表約簡[9]和并行約簡[10-11]等屬性約簡方法.但是，傳統(tǒng)粗糙集模型僅適用于非數值型數據.需要對數值型特征進行離散化，而離散化會帶來信息損失.

研究者們通過拓展粗糙集模型來解決這一問題，如鄰域粗糙集[12-21]、模糊粗糙集[22-25]等.文獻[13-14]基于鄰域信息粒子逼近，提出了鄰域信息決策模型和數值型屬性的選擇算法，能夠無須離散化而直接處理數值型屬性，解決了離散化帶來的信息損失問題，使粗糙集模型得以更方便地處理現實生活中大量存在的數值型變量.后繼的研究者引入加權依賴度[15]、局部粗糙集[16]、模糊鄰域與模糊決策[17]、Fish swarm 算法[12，18]等豐富了鄰域粗糙集理論，并將其應用推廣于多標記數據的特征選擇[19]、并行屬性約簡[20]、動態(tài)圖像分類[21]等方面.但并未考慮如何處理包含多個領域數據的數據集，而不同類型數據的處理準則和要求有所不同，如果放在同一個信息表中處理，處理結果往往不盡如人意.

F-粗糙集[26-29]是第一個動態(tài)粗糙集模型，其子集可以很好地表示不同情況下的概念，從而解決處理包含多個領域數據的動態(tài)屬性約簡問題.其后研究結合了模糊粗糙集[28]，初步應用于非數值型數據.F-粗糙集比較突出的應用在于概念漂移探測[29]，但相對較缺少非數值型數據處理方面的應用.

為了更好地解決鄰域粗糙集和F-粗糙集所遇到的問題.本文結合鄰域粗糙集和F-粗糙集的優(yōu)勢，提出了一種新的粗糙集模型—F-鄰域粗糙集.首先定義F-鄰域粗糙集的鄰域關系，使用鄰域決策子系統(tǒng)來表示不同情況.然后，使用F-屬性依賴度和屬性重要度矩陣來評估屬性.充分考慮了在多種情況下同一概念的不同，同時克服了鄰域粗糙集模型和F-粗糙集模型的缺陷.最后設計了兩個屬性約簡算法，證明了約簡結果的等價性，并說明了它們的適用范圍.實驗結果表明，相對于鄰域粗糙集、F-粗糙集和主成分分析(Principal component analysis，PCA)，本文算法能獲得更好的分類準確率.

1 基礎知識

本節(jié)簡單介紹鄰域粗糙集[13-14]和F-粗糙集[26-27]的基本概念.

1.1 鄰域粗糙集

在信息系統(tǒng)IS=(U，A) 中，U={x1，x2，···，xn}為實數空間上的非空有限集合.如果A為條件屬性，d為決策屬性，則稱(U，A，d) 為一個決策系統(tǒng).

定義1[13].對于xk ∈U，定義xk的鄰域為

1.2 F-粗糙集

F-粗糙集是一個擁有多個信息表(或決策表)的粗糙集模型，它與其他粗糙集模型具有很好的兼容性.下面介紹F-粗糙集的基本概念.用FIS={ISi:ISi=(Ui，A)，i=1，2，···，n}表示信息系統(tǒng)簇，與其對應的決策系統(tǒng)簇用F表示，其中，ISi=(Ui，A)，而DTi=(Ui，A，d).

圖1 概念X 在FIS 中的上近似、下近似、邊界區(qū)域、負區(qū)域Fig.1 Concept X in the FIS upper approximation，lower approximation，boundary region，and negative region

2 F-鄰域粗糙集

本節(jié)結合鄰域粗糙集和F-粗糙集，定義了F-鄰域粗糙集的基本概念，包括F-鄰域上下近似、邊界區(qū)域等;提出F-鄰域依賴度并證明其單調性，提出屬性重要度矩陣.

注2.數據類型為數值型，或者混合數據類型，即有些是數值型，另一些是非數值型.

2.1 F-鄰域粗糙集的基本概念

F-鄰域粗糙集繼承了F-粗糙集的動態(tài)性.不同的信息子系統(tǒng)包含的信息是不一樣的，隨著時間或空間的變化而變化，F-鄰域粗糙集與F-粗糙集一樣包含了這些變化信息，而且可以研究這些變化.

例1.設F={NDT1，NDT2}，鄰域決策系統(tǒng)NDTi=(Ui，A，d)，a，b，c是條件屬性，d是一個決策屬性，f(x，a) 表示樣本在屬性a上的取值，具體各個樣本在屬性a，b，c，d上的取值如表1 和表2所示.

概念X的鄰域δ(x) 在NDT1和NDT2中是不同的，當指定鄰域大小為0.5 時(為了方便計算采用歐氏距離)，x在條件屬性{a，b，c}下的鄰域計算式為

表1 鄰域決策子系統(tǒng)NDT1Table 1 A neighborhood decision subsystem NDT1

表2 鄰域決策子系統(tǒng)NDT2Table 2 A neighborhood decision subsystem NDT2

2.2 F-鄰域并行約簡

F-鄰域粗糙集的屬性約簡，結合了鄰域粗糙集處理連續(xù)型數據和F-粗糙集的動態(tài)性的優(yōu)點，可以對數值型數據和動態(tài)變化的數據進行約簡.

通過定義7 將并行約簡的概念擴展到鄰域決策系統(tǒng)中，定義8 和定義9 是對鄰域決策系統(tǒng)屬性重要度的擴展，假設F中只含有一個鄰域決策系統(tǒng)，那么，F-鄰域屬性重要度即為該決策系統(tǒng)的鄰域屬性重要度.F-鄰域粗糙集的屬性重要度有以下性質:

性質1.B1是鄰域決策子系統(tǒng)NDT ∈F的一個約簡，則存在一個F-鄰域并行約簡B2使得B1?B2.

性質2.如果a為一個鄰域決策子系統(tǒng)NDT ∈F的核屬性，則a為F-鄰域并行約簡的核屬性.

性質3.如果a為F-鄰域并行約簡的核屬性，則存在一個鄰域決策子系統(tǒng)NDT ∈F，使得a為NDT的核屬性.

性質1～3 可以根據F-鄰域并行約簡、核屬性的定義直接得出.

定理1.在一個鄰域決策系統(tǒng)簇F中，F-鄰域依賴度γ(F，B，d) 具有單調性，如果B1?B2?··· ?A，則γ(F，B1，d)≤γ(F，B2，d)≤··· ≤γ(F，A，d).

因為γ(F，B，d) 的單調性，根據文獻[30]中的定律1，γ(F，B，d) 可以作為屬性約簡準則，由此可得到定理2.

定理2.在一個鄰域決策系統(tǒng)簇F中，B ?A是F的鄰域并行約簡，當且僅當B ?A滿足下面兩個條件:

2) 證明確保F-鄰域并行約簡的最小性.

假設存在S ?B，使得γ(F，S，d)=γ(F，A，d).根據1) 可知:POS(F，S，d)=POS(F，A，d)，即S是F的F-鄰域并行約簡，與B ?A是F的F-鄰域并行約簡矛盾. □

根據以上性質和定理，還可以得到以下兩個命題:

命題1.給定一個鄰域決策子系統(tǒng)簇F，a ∈B?A.如果σ(B，a)=0，則屬性a可以被約簡.

σ(B，a)=0 表明，如果屬性a被約簡，F的所有決策子系統(tǒng)也能保持正域不變.

命題2.給定一個鄰域決策子系統(tǒng)簇F，a ∈A，若σ(A，a)＞0，則屬性a為F-鄰域并行約簡的核屬性.

σ(A，a)＞0 表明，如果屬性a被約簡，至少有一個鄰域決策子系統(tǒng)不能保持正區(qū)域不變，所以屬性a為F-鄰域并行約簡的核屬性.

2.3 屬性重要度矩陣

第2.1 節(jié)已經構建了F-鄰域并行約簡的概念.本小節(jié)引入屬性重要度矩陣并證明F-鄰域屬性重要度和屬性重要度矩陣構建的約簡準則等價.

文獻[27]所提出的屬性重要度矩陣是求并行約簡的一種方法，基于此我們構造了F-鄰域并行約簡，屬性重要度矩陣的定義如下:

定義11.F是一個鄰域決策系統(tǒng)簇，NDTi=(Ui，A，d)∈F，i=1，2，···，n，B ?A，B關于F的屬性重要度矩陣定義為

其中，σij=σ(aj，Ui)=γi(Ui，B，d)－γi(Ui，B－{aj}，d)，aj ∈B，n表示F中鄰域決策子系統(tǒng)的個數，m表示條件屬性的個數.矩陣H[B，F]的行表示不同的屬性在同一鄰域決策子系統(tǒng)下的屬性重要度，列表示相同的屬性在不同鄰域決策子系統(tǒng)下的屬性重要度.

定理3.在一個鄰域決策系統(tǒng)簇F中，B ?A是F的F-鄰域并行約簡，當且僅當B ?A滿足下面兩個條件:

i)POS(F，B，d)=POS(F，A，d);

ii) 屬性重要度矩陣H[B，F]中沒有全零的列.

證明.條件i) 確保了F-鄰域正區(qū)域保持不變;條件ii) 確保了F-鄰域并行約簡的最小性.

1) 條件i) 由定義9 直接得出;

2) 證明確保F-鄰域并行約簡的最小性.

反設:屬性重要度矩陣H[B，F]中有全零的列，使得B ?A是F的F-鄰域并行約簡.由于σij=γi(Ui，B，d)－γi(Ui，B－{aj}，d)，σij=0 說明屬性aj在Ui中對依賴度無影響，若aj所對應的列元素全為零，表明σj=γ(F，B，d)－γ(F，B－{aj}，d)=0，則有B－{aj} ?B，γ(F，B－{aj}，d)=γ(F，B，d)，與定理2 矛盾.

定理2 的約簡準則等價于定理3 的約簡準則，定理2 中第1 部分的證明已得出定理2 與定理3 的條件i) 等價;H[B，F]中沒有全零的列，由定理3可知B中所有屬性對γ(F，B，d) 都有影響，則有任意S ?B，γ(F，S，d)(F，B，d)?γ(F，S，d)/=γ(F，A，d).

因為定理2 和定理3 的約簡準則等價，所以可以用F-鄰域屬性重要度和鄰域屬性重要度矩陣來求得F-鄰域并行約簡，兩種方法求得的約簡結果是相同的，具體算法可見第3.2 節(jié).

為了求屬性約簡，需要定義H的改進矩陣H′，改進矩陣H′定義如下.

定義12.F是一個鄰域決策系統(tǒng)簇，NDTi=(Ui，A，d)∈F，i=1，2，···，n，B ?A，B關于F的改進屬性重要度矩陣定義為

H′是H的改進矩陣，若aj ∈B，則σ′ij=0，這意味著隨著B中包含的屬性越多，H′就越稀疏.如果B中的屬性隨時間變化而增多，直到POS(F，B，d)=POS(F，A，d)，也就是H′為零矩陣為止，這就是一個增量式約簡過程.

3 約簡算法

屬性約簡是粗糙集理論最重要的應用之一，而并行約簡是屬性約簡的一個重要延伸.并行約簡是在若干個信息子系統(tǒng)(或決策子系統(tǒng)) 中尋找穩(wěn)定的、泛化能力強的條件屬性約簡.基于屬性重要度，有以下F-鄰域并行約簡算法(算法1)，本算法借鑒了文獻[27]算法的思想，根據屬性集A中各元素在鄰域決策子表簇F中的屬性重要度找到屬性核，然后通過屬性重要度找到其他屬性.

算法1 首先從局部的鄰域決策子表中計算出決策屬性對條件屬性的依賴度和條件屬性的屬性重要度，得出各個子表的核屬性，然后，從鄰域決策子表簇整體出發(fā)，計算出條件屬性的屬性重要度，最后，得出原屬性集的一個F-鄰域并行約簡.

算法1 的時間復雜度主要由F-鄰域屬性重要度和步驟4 的時間復雜度決定.其中計算一個條件屬性的F-鄰域屬性重要度的時間復雜度為U代表決策子表中數據的個數，m代表條件屬性的個數.在最壞的情況下，步驟4 需計算次F-鄰域屬性重要度.因此算法1 的時間復雜度為

基于屬性重要度矩陣，有以下F-鄰域并行約簡算法(算法2)，根據屬性重要度矩陣H(A，F) 找到屬性核B，然后通過建立B的改進屬性重要度矩陣H′找到其他屬性，直到H′(P，F) 為零矩陣為止.

算法2 是根據定義13 和定義14 構造F-鄰域并行約簡算法.鄰域并行約簡P先從空集開始，通過計算不同(相同) 的屬性在同一(不同) 鄰域決策子系統(tǒng)下的屬性重要度建立屬性重要矩陣，先從中選出所有子系統(tǒng)中屬性重要度都不為零(即矩陣H中沒有零元素的列) 所對應的屬性加入P中，然后計算改進屬性重要度矩陣H′把非零元素個數最多的列所對應的屬性加入P中，直到H′為零矩陣.該算法保證了對正區(qū)域有影響的屬性不會被刪除.

算法2 的時間復雜度主要是由建立矩陣以及改進矩陣組成，使用與算法1 相同的方法計算屬性重要度，它的時間復雜度為O(mUlogU)，其中，U代表決策子表中數據的個數，m代表條件屬性的個數，那么建立一個屬性重要度矩陣的時間復雜度為O(nm2U′logU′)，其中，U′代表F中最大子表的數據個數，n代表子表個數.在最壞的情況下，改進的矩陣的個數為m，因此算法2 的時間復雜度為O(nm3U′logU′)，略高于算法1.

算法1 和算法2 的約簡結果是相同的，所以在大部分情況下使用算法1 或算法2 并沒有區(qū)別.算法1 使用的F-鄰域屬性重要度表明屬性對鄰域決策系統(tǒng)簇整體的影響;算法2 使用的屬性重要度矩陣表明屬性對鄰域決策系統(tǒng)簇中各個子系統(tǒng)的影響.當實驗需要測量屬性對鄰域決策系統(tǒng)簇的影響時應該使用算法1，實驗需要測量屬性對各個決策子系統(tǒng)的影響時應該使用算法2，實驗對以上兩個數據都需要時應該同時使用算法1 和算法2.

4 實驗結果

本節(jié)在UCI 數據集、真實數據集以及MATLAB 生成數據集上進行實驗，通過對比實驗，驗證了相對于鄰域粗糙集、F-粗糙集和PCA，F-鄰域粗糙集在分類準確率上都具有優(yōu)勢.

4.1 數據集

本節(jié)設計了一些實驗來測試所提出的F-鄰域粗糙模型的性能，使用UCI 數據庫(http://archive.ics.uci.edu/ml/datasets.html) 中Iris 等9 個數據集;兩個真實數據集Cevaluation，Rapequality;一個MATLAB 生成數據集Generated data.Cevaluation 數據集來自于國內某高校研二、研三的研究生綜合測評數據，包含240 個樣本和26 個屬性，其中研二和研三的綜合測評計分規(guī)則不同.Rapequality數據集用于描述油菜加工品質，包含138 個樣本和26 個屬性.如表3 所示.

4.2 實驗設置

實驗的目的是驗證F-鄰域粗糙集約簡的有效性，并通過對比約簡后屬性子集的分類質量揭示它的可行性.由于本次實驗使用算法1 與算法2的約簡結果的等價性，在實驗中使用的算法為算法2.實驗的評估是使用決策樹模型中比較穩(wěn)定的CART 分類器，以10 折交叉驗證計算分類準確率，以分類準確率的高低為標準.同時為了構造鄰域決策系統(tǒng)簇F，對每個數據集進行了分塊，每一塊都作為一個鄰域決策系統(tǒng).實驗選取δ=0.1，δ=0.05，δ=0.01 三個鄰域參數進行驗證，所有算法在MATLAB R2018a 上實現.

表3 數據集描述Table 3 Description of datasets

4.3 實驗結果與分析

先與NRS 進行比較，目的是為了比較NRS 與NPRMS 的約簡質量.因此，計算兩種算法基于CART 分類器在δ=0.1，δ=0.05，δ=0.01 下的分類準確率，如表4～6 所示.

從表4～6 中可以發(fā)現，在3 個參數下，除了abalone 數據集在鄰域0.1 和0.05 下沒有約簡，其他情況下兩種方法都能有效地減少屬性.雖然在除soy，Iris，wine 和Cevaluation 之外的數據集上，F-鄰域并行約簡(NPRMS) 的約簡屬性子集數目要高于NRS，但是在wpbc，sonar，debrecen，EEGEye和Generated data 數據上，NPRMS 僅僅多出了一個屬性，在分類準確率上則提升了5～17.5 個百分點不等.其在這些數據集上分類準確率的大幅提升可以表明，NPRMS 在這些數據集上的性能要優(yōu)于NRS.值得注意的是在Rapequality 數據集上，當參數為0.1 和0.5 時，NPRMS 和NRS 的約簡完全相同;當參數為0.01 時，NPRMS 的約簡子集還是沒有變化，NRS 則減少了兩個屬性，降低了3個百分點的分類準確率.在Rapequality 數據集上，NPRMS 有效地保留了決策子系統(tǒng)中的有效信息，而NRS 約簡掉兩個屬性時分類準確率出現了明顯降低，說明NRS 在參數為0.01 的約簡中丟失了有效信息，NPRMS 的表現符合我們?yōu)榱擞行У乇Ａ粲行畔⒍袴-粗糙集引入鄰域粗糙集的初衷.

表4 δ=0.1 時兩種算法約簡的結果Table 4 Results of two algorithm reductions when δ=0.1

表5 δ=0.05 時兩種算法約簡的結果Table 5 Results of two algorithm reductions when δ=0.05

由于F-粗糙集并行約簡(OPRMAS)[29]不能直接處理數值型數據，先把數據進行離散化處理，再通過OPRMAS 算法約簡，根據約簡結果從原數據中挑選出這些屬性數據，經過CART 分類器判別得到最后結果.我們選取鄰域參數δ=0.01 時，NRS與NPRMS 的結果與之進行比較.PCA 是經典的特征選擇方法，其對于條件屬性的特征選擇不需要決策屬性，所以我們在使用PCA 進行降維時，去除了數據中的決策屬性，在判別分類準確率時，再將決策屬性加入已降維的數據進行判別;其還可以控制保留屬性的數目，為了方便比較，將PCA 保留屬性的數目設置為與NPRMS 相同.

從表7 和圖2 中可以看出，在NRS 和NPRMS選擇合理的鄰域參數的情況下，NRS，OPRMAS，PCA，NPRMS 四種方法的屬性數目和分類準確率比較.NPRMS 較于NRS 分類準確率有所提升，且約簡子集數目并未顯著增加，特別是在Cevaluation 上，由于其研一、研二兩部分測評規(guī)則的不同，NRS 表現得并不好，而OPRMAS 和NPRMS 的約簡效果明顯優(yōu)于NRS 和PCA;雖然OPRMAS在sonar，spambase 和EEGEye 上分類準確率要高于NPRMS，但其在sonar 和spambase 上的約簡子集中屬性數目多于NPRMS，在EEGEye 上更是并未減少數據集原本的屬性數目，而在Cevaluation 上兩種方法雖然約簡結果相同，但NPRMS 比OPRMAS 少了離散化的步驟，因此具有一定優(yōu)勢.

表6 δ=0.01 時兩種算法約簡的結果Table 6 Results of two algorithm reductions when δ=0.01

表7 在各個數據集中三種算法約簡的結果Table 7 Results of three algorithmic reductions in each dataset

圖2 在各個數據集中算法的分類準確率Fig.2 Classification accuracy of algorithms in each dataset

造成以上實驗結果的原因有:1) NRS 算法由于鄰域半徑造成的信息丟失等原因，所得的并不是最優(yōu)約簡，而NPRMS 是動態(tài)約簡，可以有效地減少信息損失;2) 在樣本數量多屬性數目少的數據集中，離散化帶來信息損失尤為明顯，使OPRMAS 在這類數據集上的約簡效果較差，甚至可能并無約簡效果，而NPRMS 不需要離散化，保留了必要的信息，從而可以實現較好的約簡;3) 在有的數據集中包含多種規(guī)則，NRS 等大部分算法并沒有考慮這種情況，只是把其當作一般的數據集一樣約簡，所以其約簡后的分類準確率并不理想;而OPRMAS 正是基于這種情況而誕生的算法，這種數據集下它的約簡效果較好是可以預見的;NPRMS 結合了OPRMAS這方面的優(yōu)點，也能較好地適用于該類數據集的約簡.

NPRMS (或 NPRAS) 相 較 于 NRS 和OPRMAS，準確率有所提升，其性質又決定了其具有更廣泛的適用范圍，因此F-鄰域并行約簡更具優(yōu)勢.

5 結論與展望

減少冗余屬性可以提高分類性能并降低分類成本.在本文中，首先介紹了兩種粗糙集模型:F-粗糙集和鄰域粗糙集.由于兩種粗糙集模型都具有自身的優(yōu)勢，但雙方都未考慮對方的優(yōu)點，因此提出了F-鄰域粗糙集.該模型結合了兩個粗糙集模型的優(yōu)勢，是一個無需離散化處理數值型數據的動態(tài)粗糙集模型.最后，用F-屬性重要度和屬性重要度矩陣來評估屬性，使用它們來設計屬性約簡算法，并說明兩種算法的相同點和不同點.實驗結果表明兩種算法能獲得較高的分類準確率.實驗中還發(fā)現決策子系統(tǒng)的劃分對所提出的兩種屬性約簡算法的性能的影響較大.應該根據屬性數目和數據項數目為每個數據集選擇合適的決策子系統(tǒng)劃分.

未來的工作可能包括:1) 如何將所提出的模型應用于具有不確定性的分類學習和推理領域;2) 在所提出的模型中，在數據集中劃分決策子系統(tǒng)對所提出算法的性能具有重要影響.它需要由用戶提前劃分.如何為每個數據集自動自動劃分決策子系統(tǒng)的最佳解決方案也是一項有意義的工作.