基于不一致近鄰的模糊粗糙集特征選擇

趙潔，葉文浩，梁周揚，陳建新，董振寧

（廣東工業(yè)大學管理學院，廣東 廣州 510520）

0 引言

近年來，隨著技術(shù)進步和電子存儲信息的爆發(fā)式增長，各領(lǐng)域的大量數(shù)據(jù)信息得到有效存儲，大數(shù)據(jù)成為研究熱點［1］，超高維屬性常見于大數(shù)據(jù)分析。冗余或不相關(guān)特征會增大計算的時間復雜度，引發(fā)“維數(shù)災害”問題［2］，甚至會干擾學習算法，降低算法性能。因此，在提取重要特征的同時去除冗余特征是十分必要的。特征選擇可有效選擇有用特征，從而提高分類器性能和數(shù)據(jù)的可解釋性，已廣泛應用于各個領(lǐng)域，例如機器學習、圖像處理、異常檢測和醫(yī)學分析等［3-5］。

在粗糙集理論中，特征選擇又稱屬性約簡。為評估處理數(shù)據(jù)表中條件屬性和決策屬性的不一致性問題，文獻［6］提出經(jīng)典粗糙集理論，可有效適用于離散型數(shù)據(jù)，而現(xiàn)實世界中，符號值和連續(xù)型特征（即混合異構(gòu)數(shù)據(jù)）通常共存，例如醫(yī)學分析和故障診斷中存在的屬性［7］、商業(yè)數(shù)據(jù)［8］等。同時，離散化通常導致信息丟失［9］。針對該問題，文獻［10］提出模糊粗糙集模型，引入模糊等價關(guān)系，結(jié)合模糊集和粗糙集，對模糊概念進行相似刻畫，解決了粗糙集在處理數(shù)據(jù)上的局限性。模糊粗糙集發(fā)展至今，不僅可處理包含連續(xù)型和離散型數(shù)據(jù)的混合數(shù)據(jù)集，而且擴展到多種數(shù)據(jù)類型，包括集合型、區(qū)間值以及非結(jié)構(gòu)化特征等［11-12］。近年來，眾多學者已把模糊粗糙集推廣到多個領(lǐng)域，如規(guī)則提取［13］、分類樹歸納［14］、醫(yī)學分析［15］等。文獻［16］將模糊粗糙集模型正式引入特征選擇。

模糊粗糙集特征選擇方式可分為基于模糊正域［17］、熵的不確定性度量［18-20］和基于辨識關(guān)系［21-23］。其中，基于辨識關(guān)系雖然可得到多組解，但是其占用內(nèi)存大且時間復雜度高。熵的不確定性度量和基于模糊正域雖然可快速計算，但是在特征選擇過程中仍須反復計算，成為模糊粗糙集特征選擇算法的瓶頸。針對此問題的改進算法有很多，但是在處理大規(guī)模數(shù)據(jù)集時仍存在計算效率低的問題，模糊粗糙集特征選擇算法難以投入到實際應用中。

針對計算低效問題，多種算法被提出以提高計算效率，其中包括并行計算［24］、正域刪減［25］和壓縮決策表［26］。雖然并行計算在一定程度上縮短算法的時間，但是在計算過程中仍須在整個論域U上反復計算。壓縮決策表策略可把論域從U壓縮至U/C，但是該策略難以在模糊粗糙集上實施。

在計算過程中，縮減計算域的策略可有效提高計算效率，文獻［27］在經(jīng)典粗糙集約簡過程中，逐步刪除正域中的記錄，從而不斷縮減論域，并在理論上證明，實施該策略后計算得到的約簡與經(jīng)典算法計算結(jié)果一致，并且效率提升較為明顯。文獻［28］繼續(xù)將該策略應用于模糊粗糙約簡算法，有效提升算法效率，但其加速策略在基于信息熵的算法上存在信息丟失問題，同時，信息熵中連乘計算魯棒性較低，少量數(shù)據(jù)可能會導致其產(chǎn)生巨大的變化和偏差。文獻［29］采用一種K-近鄰（KNN）算法計算模糊相似關(guān)系，只計算相近的k個樣本相似度，可避免交集運算帶來隸屬度判別小的問題，但該算法在高維數(shù)據(jù)集的分類效果表現(xiàn)欠佳，且計算效率低。文獻［30］基于相對辨識關(guān)系的增量計算研究屬性在動態(tài)增加和刪除下的策略，設計2 種模糊粗糙集屬性約簡的增量策略，但是2 種策略仍存在耗時嚴重的問題。文獻［31］提出一種適用于廣義模糊粗糙集模型的加速算法，通過選擇關(guān)鍵實例集，去除冗余樣本，避免對整個論域進行運算，為模糊粗糙加速算法進行補充，并結(jié)合增量學習理論，適用于大樣本數(shù)據(jù)集。

在現(xiàn)有模糊集特征選擇方法中，基于模糊正域可減少搜索空間，但屬性重要度難以精確評估屬性辨別能力；熵的不確定性度量極大地保留原始信息，但易受噪聲數(shù)據(jù)干擾；基于辨識矩陣的方法可得到多組解，但是在計算模糊等價關(guān)系時，需要的時間和空間復雜度很高。因此，現(xiàn)有方法在計算時間復雜度上仍有改進空間，現(xiàn)有加速策略雖然可提升小數(shù)據(jù)集的計算效率，但是處理大規(guī)模和高維數(shù)據(jù)集仍耗時嚴重，且未能保證較優(yōu)的分類精度。

本文結(jié)合模糊集的水平截集，提出一種基于不一致模糊近鄰關(guān)系的加速策略，可簡化模糊近鄰的計算過程，不斷縮減對象的模糊近鄰及論域，簡化并加速現(xiàn)有模糊相似算子的計算過程。同時，設計一種基于不一致近鄰信息遞減效應衡量屬性重要度的方式，有效選擇具有高辨識能力的屬性，基于此設計快速特征選擇算法，在提升算法效率的同時保證較高的分類精度。

1 模糊粗糙集特征選擇

1.1 基本理論知識

定義1（模糊集）［32］設U為1 個非空有限論域，μX是論域U到區(qū)間［0，1］的1 個映射，即：μX：U→[0,1]，x→μX(x)，稱X是論域U上的1 個模糊集X={μX(x)|x?U}，其中，μX(x)為x屬于模糊集X的隸屬度。

定義2（模糊等價關(guān)系）［25］設U為1 個論域，R：U×U→［0，1］為論域U上的模糊二元關(guān)系，對于任意的x，y，z∈U，R滿足如下條件，則稱R是U上的1 個模糊等價關(guān)系：1）自反性，R(x,x)=1；2）對稱性，R(x,y)=R(y,x)；3）傳遞性，R(x,z)≥T(R(x,y),R(y,z))。

設B1?B2?…?Bn，{RB1,RB2,…,RBn}則為1 組模糊二元關(guān)系集合，并且滿足對于任意的x，y∈U，由屬性集合B?C所引導的模糊等價關(guān)系RB滿足

定義3（模糊決策表）［31］給定1 個決策表DDT=(U,C∪D)，其中，U={x1,x2,…,xn}為論域，是1 個非空有限集合，C為實值條件屬性集合，D為決策屬性，滿足C∩D=?，條件屬性集B?C，可導出1 個模糊等價關(guān)系RB。

對于多屬性集合B?C，對于任意的x，y∈U，由屬性集合B所引導的模糊關(guān)系RB滿足如下條件：

定義4［28］論域U由模糊等價關(guān)系RB劃分如下：

其中：[x]B是U上的1 個模糊集。對于每個x?U屬于[x]B的隸屬度表示[x]B(y),y?U，又可表示RB(x,y)，那么每個x?U的基數(shù)如下：

1.2 α-截集模糊粗糙集

模糊粗糙集特征選擇算法效率有較大提升空間。針對該問題，本文結(jié)合α-截集模糊粗糙集進行研究，可有效縮減論域中模糊鄰域空間。此外，本文基于不一致近鄰遞減效應，設計屬性重要度。

定義5（α-水平截集）［32-33］設DDT=(U,C∪D)是模糊決策表，B?C，任意x，y∈U，Ra(x,y)?[0,1]。設α∈［0，1］，[x]a的α-水平截集定義如下：

定義6［32］設DDT=(U,C∪D)為模糊決策表，X是論域U的模糊子集，那么X在U的下近似集和上近似集X定義如下：

定義7（α-模糊正域）［34］設DDT=(U,C∪D)為模糊決策表，為X在U的下近似集，特征子集B?C的模糊正域定義如下：

2 研究方法

2.1 基于不一致近鄰的模糊粗糙集模型

本節(jié)首先基于模糊等價關(guān)系計算，提出模糊不一致近鄰遞減策略，進而提出改進的加速算法FSINO。根據(jù)式（1），在約簡過程中，須多次比較x與y在各屬性下的等價關(guān)系以更新RB。當a?B不斷加入，Ra(x,y)單調(diào)遞減，說明x和y會被新加入屬性a區(qū)分。因該過程需要反復進行，導致算法效率降低。

針對此，本文提出模糊不一致近鄰集遞減策略，旨在有效提高效率。基于定義5 的α-水平截集，進一步劃分α-截集，RB下x的不一致模糊近鄰集（N-近鄰集）記為：

定理1設DDT=(U,C∪D)是模糊決策表，其中B?C，RB為1 個模糊等價關(guān)系，設Y?U/D，若x∈U關(guān)于RB模糊近鄰集中的N-近鄰集為空，則

證明

定理2設B={R1,R2,…,Rn}是一族模糊二元關(guān)系，其中，U/D={Y1,Y2,…,Yr}，若Bi={R1,R2,…,Ri}，則：

綜合上述分析，證畢。

文獻［35］提出基于信息熵的重要度，可有效衡量屬性對決策屬性的分辨能力，由于熵連乘的特性，因此該重要度極易受到個別對象的影響，從而影響屬性約簡結(jié)果。本文設計合適的屬性重要度，可選擇優(yōu)質(zhì)特征，避免冗余特征入選，不僅可提升算法效率，還可以獲得高分類精度。針對此，本文研究基于定義的不一致近鄰及其性質(zhì)，根據(jù)模糊近鄰的遞減效應，提出一種新的屬性重要度衡量方式。

定義8設DDT=(U,C∪D) 為模糊決策表，UD={d1,d2,…,dn}，B?C，RB為1 個模糊等價關(guān)系，基于不一致模糊近鄰的屬性重要度衡量如下：

2.2 數(shù)值算例

給定決策表DDT=(U,C∪D)，如表1 所示，U=｛x1，x2，…，xn｝，C=｛a1，a2，…，am｝，D=｛yes，no｝。

表1 決策表信息Table 1 Information of decision table

設at?C,t={1,2,3}，模糊等價關(guān)系為Rat(xi,xj)=1-|at(xi)-at(xj)|。

本文方法根據(jù)定義5 和上述模糊等價關(guān)系計算式，設δ=0.5 劃分模糊近鄰集，可得{x1,x2,x3}，再根據(jù)式（5）可得：

基于上面計算結(jié)果，根據(jù)定義8 可得：

現(xiàn)有方法計算屬性重要度，論域中每個對象x的模糊近鄰集的計算空間大小為|U|，因此時間復雜度為O(|U|2)。本文計算屬性重要度，論域中每個對象的模糊近鄰集大小可通過2 個策略縮減，第1 個策略是通過水平截集中的α參數(shù)，可有效刪減相似關(guān)系低的近鄰，第2 個策略是本文研究僅使用對象模糊近鄰集中的不一致近鄰，時間復雜度為O(|U||Nm|)，Nm表示最大N-近鄰集的近鄰個數(shù)。上述數(shù)值算例中|Nm|=3，則時間復雜度可從62下降至6×3。基于不一致近鄰設計，本文所提算法可有效降低時間和空間復雜度。

2.3 FSINO 算法

本文在FA-FSCE 的正域刪減策略基礎上改進，提出基于α-水平截集不一致近鄰的模糊粗糙集特征選擇算法。FA-FSCE 使用模糊正域作為屬性重要度，論域中的每個對象是否屬于模糊正域僅有｛0，1｝2 種狀態(tài)。FSINO 根據(jù)式（11）中的不一致性，把對象屬于模糊正域映射到［0，1］區(qū)間，當|NαB(x)|=0 時，則判斷x進入模糊正域。同時，F(xiàn)A-FSCE 在論域和論域?qū)ο蟮哪：徏芯鶆h除正域，但后者會影響基于熵的屬性重要度的正確性，可能影響后續(xù)學習算法的精度。本文僅在論域中刪減進入模糊正域的對象x，在有效縮減計算空間的同時保證了計算的準確性。

算法1FSINO 算法

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)

為驗證本文所提算法的有效性，本文將FSINO算法與現(xiàn)有算法比較，依據(jù)模糊正域、熵的不確定性度量和基于辨識關(guān)系3 種模糊粗糙集特征選擇方式依次選擇代表性算法：1）文獻［29］提出的AVDP 算法，該算法是一種K-近鄰距離度量算法；2）文獻［28］提出的FA-FSCE 算法，是一種正域刪減加速算法；3）文獻［30］提出的IV-FS-FRS-2 算法，是基于模糊辨識關(guān)系的增量模糊粗糙集特征選擇算法。由于AVDP 算法需要對每個數(shù)據(jù)集調(diào)整停止條件的閾值(δ=0.001～0.030)，步長設置為0.005，最終綜合7 種參數(shù)結(jié)果，取δ=0.01，該結(jié)果的平均分類精度最優(yōu)。本文選取UCI 機器學習和scikit 特征選擇數(shù)據(jù)庫中的9 個數(shù)據(jù)集進行實驗分析，數(shù)據(jù)集基本信息如表2 所示。所有算法均使用Java 語言編寫程序執(zhí)行，并在Intel?CoreTMi5-6300HQ CPU@2.30 GHz 和12 GB 內(nèi)存的硬件環(huán)境下運行，所有數(shù)據(jù)集樣本依次隨機運行10 次特征選擇算法，通過支持向量機（SVM）和K-近鄰算法2 種分類器得出分類精度，其中每個數(shù)據(jù)集采用10 折交叉驗證，即每個數(shù)據(jù)集被隨機劃分為10 等份，選擇其中9 個樣本子集作為訓練集，剩下1 個作為測試集。

表2 UCI 和scikit 數(shù)據(jù)集描述Table 2 Description of UCI and scikit datasets 單位：個

對于數(shù)值型特征，須對數(shù)據(jù)進行歸一化處理，從而使?a?C,a′(xi)?[0,1]：

其中：xi?U。表2 中數(shù)據(jù)集每個歸一化后特征a的模糊相似關(guān)系定義如下［30］：

圖1 閾值α 在不同水平下約簡的長度和分類精度結(jié)果Fig.1 Length and classification accuracy results reduced by threshold α at different levels

基于上述分析，可確定α的取值范圍。在與所給3 個算法的對比實驗中，設置α=0.7,δ=0.001。

3.2 對比實驗

為驗證該算法的有效性，本文通過3 個指標評估對比實驗性能。

1）運行時間是每個特征選擇算法在數(shù)據(jù)集上10 次運行結(jié)果的平均時間，為清晰展示FSINO 算法效率，使用如下時間比率作為指標：

其中：AAl為FSINO 算法在數(shù)據(jù)集上的平均運行時間；為每個對比算法的平均運行時間。顯然，AARR?[0,100%]。

2）入選特征數(shù)量是每個算法在數(shù)據(jù)集上10 次運行結(jié)果的平均特征數(shù)量。

3）分類精度通過SVM 和KNN（k=5）2 種分類器求出約簡后數(shù)據(jù)集的平均分類精度。

圖2所示為FSINO、FA-FSCE、AVDP和IV-FS-FRS-2算法在每個數(shù)據(jù)集上迭代前5次的平均運行時間。因IV-FS-FRS-2 算法在數(shù)據(jù)集Wave、EGSS 上無法運行，所以在Wave、EGSS 數(shù)據(jù)集上沒有顯示結(jié)果。上述4 個算法的停止條件不同，求約簡的迭代次數(shù)不同，為方便比較，采用前5 次運行時間作為參考。從圖2 可以看出，本文所提的FSINO 運行效率明顯優(yōu)于其他算法。FSINO 算法雖然前5 次計算時間下降并非最快，但是每輪計算時間較短，并呈現(xiàn)線性遞減趨勢。IVFS-FRS-2算法迭代時間下降速率最快，但是在迭代起始須基于辨識關(guān)系形成每個特征可辨識的樣本對，耗費大量時間。

圖2 所有算法在9 種數(shù)據(jù)集上前5 次的迭代時間Fig.2 Time of the first five iterations for all algorithms on the nine datasets

FSINO 算法計算空間如表3 所示。FSINO 算法中的計算域為不包含正域的U′以及最大N-近鄰個數(shù)Nm。FSINO 算法的計算域遠低于模糊粗糙集中所需要的|U|2，在數(shù)據(jù)集CLL 上最優(yōu)情況可降低至4.93%，在數(shù)據(jù)集EGSS 上也可達到45.81%。

表3 FSINO 算法計算空間Table 3 The computational domain of the FSINO algorithm

在數(shù)據(jù)集上不同算法前5 次的迭代時間如表4所示，F(xiàn)SINO 算法在每個數(shù)據(jù)集上的運行時間均低于其他3 個算法。在普通類數(shù)據(jù)集Libras 上，F(xiàn)SINO算法的運行時間是FA-FSCE 的15.65%，是AVDP 算法的4.32%，是IV-FS-FRS-2 算法的1.92%，在高維數(shù)據(jù)集CLL 上，F(xiàn)SINO 算法的運行時間是FA-FSCE 的38.99%、AVDP 算法的0.46%、IV-FS-FRS-2 算法的15.12%。在大規(guī)模數(shù)據(jù)集EGSS 上，F(xiàn)SINO 算法的運行時間是FA-FSCE 的28.22%、AVDP 算法的12.6%。上述實驗結(jié)果表明，與其他3 個算法相比，F(xiàn)SINO 算法可更快速獲得最佳特征子集。該實驗驗證FSINO算法通過正域和近鄰刪減策略可有效縮減樣本搜索空間和α-截集模糊集[x]αB的計算空間。從圖2 和表3可以看出，F(xiàn)SINO 算法縮減計算空間的方式可有效提升算法效率。

表4 不同算法的運行時間Table 4 Computational time among different algorithms

表5 和表6 所示為FSINO 與3 個對比算法在數(shù)據(jù)集上所選特征數(shù)以及分類精度。由于IV-FS-FRS-2在數(shù)據(jù)集Wave 和EGSS 上無法在合理時間內(nèi)完成計算，因此采用原始數(shù)據(jù)集特征個數(shù)和分類精度結(jié)果計算IV-FS-FRS-2 在Wave 和EGSS 數(shù)據(jù)集上的平均結(jié)果。從入選特征數(shù)可以看出，F(xiàn)SINO 算法在9 個數(shù)據(jù)集上的平均入選特征數(shù)為8.8 個，明顯低于原始數(shù)據(jù)集上的平均特征數(shù)1 315.3 個，也小于FA-FSCE 算法入選特征數(shù)19.1 個、AVDP 算法的54.9、IV-FS-FRS-2 算法的131.6 個。該實驗結(jié)果表明FSINO 算法可去除更多冗余特征。為驗證FSINO算法對分類器性能的有效性，本文采用SVM 和KNN 2 種分類器預測分類精度，在SVM 的結(jié)果中，F(xiàn)SINO、FA-FSCE、AVDP、IV-FS-FRS-2 算法的平均分類精度分別為0.887 0、0.868 9、0.870 4、0.868 9。從表6 可以看出，在KNN 的結(jié)果中，F(xiàn)SINO、FA-FSCE、AVDP、IV-FS-FRS-2 算法的平均分類精度分別為0.865 4、0.834 1、0.837 0、0.823 0。所有算法在每個數(shù)據(jù)集上的分類精度對比如圖3 所示，F(xiàn)SINO算法的分類精度優(yōu)于其他算法。

圖3 所有算法在9 個數(shù)據(jù)集上的分類精度對比Fig.3 Comparison of classification accuracy of all algorithms on nine datasets

表5 不同算法約簡特征個數(shù)和SVM 分類精度的比較Table 5 Comparison of the number of features reduced and SVM classification accuracy by different algorithms

表6 不同算法約簡特征個數(shù)和KNN 分類精度的比較Table 6 Comparison of the number of features reduced and KNN classification accuracy by different algorithms

3.3 結(jié)果分析

本文所提的FSINO 算法在普通、高維和大規(guī)模數(shù)據(jù)集上均可快速選擇最佳特征子集。FSINO 算法在每次約簡迭代中，基于刪減模糊近鄰策略，計算空間大小最高縮減至原始空間的4.93%；在運行時間上，相比對比算法，可減少9.44%～99.54%，尤其在高維和大規(guī)模數(shù)據(jù)集上，分別可減少61.01%和66.42%及以上；基于不一致近鄰的屬性重要度衡量方式，在入選的特征數(shù)上，平均減少原始特征數(shù)的76.13%；分類精度上，相比對比算法，SVM 和KNN 的分類精度最高可分別提升11.20%和19.95%，表明FSINO 算法所選特征可提高學習算法的分類性能。上述結(jié)果證實，基于不一致近鄰的加速策略和屬性重要度衡量方式是一種有效的啟發(fā)式模糊粗糙集特征選擇加速算法。

4 結(jié)束語

模糊粗糙集特征選擇算法耗時嚴重，且未能保證較高分類精度。為此，本文提出基于不一致近鄰的模糊粗糙集特征選擇算法FSINO。首先，引入模糊集的水平截集理論，可縮減對象的模糊近鄰空間；其次，運用模糊近鄰在特征選擇下的遞減效應，從2 個方面不斷縮減計算空間；最后，使用一致與不一致近鄰占比，設計新的屬性重要度衡量方式，抑制冗余特征并選擇具有高分辨能力的特征，從而減少特征選擇迭代次數(shù)，進一步提高運行效率。實驗結(jié)果表明，該算法可有效縮短運行時間并減少冗余特征入選，提高分類精度。研究中還探討水平截集中不同閾值對分類結(jié)果的影響，從而選擇合適閾值提高分類精度。下一步將增量學習和群智能算法融入到不一致近鄰集的特征選擇算法中，從而擴大該算法的適用范圍，發(fā)揮該算法的實際應用價值。