楊燕燕，張 曉，李翔宇，杜晨曦，李懿恒

(1.北京交通大學 軟件學院，北京 100044；2.西安理工大學 理學院，西安 710048)

0 引 言

隨著信息與通信技術的迅猛發(fā)展，人們收集、存儲、傳輸和管理數(shù)據(jù)的能力日益提高，使得各行各業(yè)積累了大量高維、海量數(shù)據(jù)[1]。這些高維海量數(shù)據(jù)中往往存在大量的冗余特征，這不僅增加了計算機的存儲成本，還對傳統(tǒng)機器學習算法的性能和效率帶來了嚴峻挑戰(zhàn)。特征選擇[2-3]是機器學習和數(shù)據(jù)挖掘中處理高維數(shù)據(jù)的主流技術之一，其主要操作是通過特定的特征估計度量和搜索策略，移除冗余以及不相關的特征為構建好的預測模型選擇一個緊湊的、有信息量的特征子集[4-6]。理論和實踐表明，在執(zhí)行分類任務之前，對高維數(shù)據(jù)進行特征選擇可有效提高學習算法的可解釋性、縮短學習算法的訓練時間，并通過降低過擬合來提高學習算法的泛化性能[7]。目前，特征選擇已經(jīng)成為機器學習和數(shù)據(jù)挖掘領域中的一個研究熱點，引起了學術界和企業(yè)界的廣泛關注，并已成功應用于圖像識別[8]、圖像檢索[9]、文本挖掘[10]、生物數(shù)據(jù)分析[11]、故障診斷[12]等眾多應用領域。

模糊粗糙集[13-14]通過模糊信息粒化的方式為特征選擇提供了一種有效的方法[15-16]。作為經(jīng)典粗糙集模型[17]的推廣，它是一種處理數(shù)值集中樣本之間的不可辨識性和模糊性的有力數(shù)學工具。模糊粗糙集利用模糊相似關系來描述樣本之間的相似性，刻畫了數(shù)值數(shù)據(jù)中條件屬性(特征)與決策標簽之間的不一致性。這種不一致性表現(xiàn)為2個樣本具有相同或相似的條件屬性取值，卻有不同的決策標簽，其可通過模糊粗糙集的下近似對每個樣本關于其決策標簽指派一個隸屬度來進行度量[18]。通過保持每個樣本的這一隸屬度不變，模糊粗糙集特征選擇，也叫屬性約簡，就能刪去冗余或者不相關的條件特征以獲取一個有信息量的特征子集。

近年來，模糊粗糙集特征選擇的研究已經(jīng)取得了豐碩的成果，出現(xiàn)了各種各樣的模糊粗糙集特征選擇算法[19-23]。這些算法可分為基于測度的啟發(fā)式算法和基于區(qū)分能力的結構化方法。其中，基于區(qū)分能力的結構化方法以辨識矩陣的方法為典型代表，從樣本之間的區(qū)分能力的角度構造了屬性約簡方法。模糊粗糙集辨識矩陣的思想首次由文獻[15]引入，其利用辨識矩陣的方法研究了屬性約簡的本質，設計了計算一個約簡的辨識矩陣算法。然而，該辨識矩陣的方法需要占據(jù)大量的內存，并不適用于大規(guī)模數(shù)據(jù)。鑒于此，文獻[24]提出了基于極小元素的模糊粗糙集特征選擇算法，該算法極大減少了運行時間同時節(jié)省了大量的內存空間。利用文獻[24]中的相對辨識關系的定義，文獻[25-26]構造了基于相對辨識關系的模糊粗糙集特征選擇算法。

基于測度的啟發(fā)式算法主要借助前向搜索的方式，通過保持數(shù)據(jù)集的模糊依賴函數(shù)或模糊信息熵等特征估計測度不變來獲取該數(shù)據(jù)集的最優(yōu)特征子集。比如，最早提出模糊粗糙集屬性約簡概念的文獻[27]將經(jīng)典粗糙集中保持依賴函數(shù)不變的思想平移到模糊粗糙集的框架中，設計了一個模糊粗糙集特征選擇的快速算法。然而，文獻[15]指出，文獻[27]所提算法是不收斂的，這對特征選擇的執(zhí)行帶來了諸多問題。文獻[28-29]用模糊熵的概念刻畫了特征的重要性，進而提出了基于模糊熵的特征選擇算法。通過改進文獻[28]中模糊條件熵的定義，文獻[30]定義了λ-條件熵，并提出了基于該模糊熵的filter-wrapper算法。文獻[31]在所提出的擬合模糊粗糙集模型下定義了模糊依賴函數(shù)，并設計了一個擬合模糊粗糙集特征選擇的前向啟發(fā)式算法。文獻[32]定義了特征子集的鄰域區(qū)分索引，基于此度量設計了一個數(shù)值數(shù)據(jù)的特征選擇算法。文獻[33]定義了模糊粗糙集自信息，并設計了一個基于模糊自信息的特征選擇算法。

上述2類模糊粗糙集特征選擇算法不僅具有豐富的理論，也在實踐中表現(xiàn)出了良好的性能。但是，在確定每一個最優(yōu)候選特征的過程中，它們都需要遍歷數(shù)據(jù)集的所有樣本來計算每個候選特征加入后的特征估計測度，如依賴函數(shù)、信息熵等。事實上，并不需要借助數(shù)據(jù)集的所有樣本來確定一個最佳候選特征，這便需要借助樣本篩選策略，文獻[34-35]已經(jīng)研究過樣本篩選的機制，但是它們卻致力于增量特征選擇算法，這不是本文的研究范疇。另外，在每次迭代過程中，上述算法也都需要遍歷所有剩余的候選特征來確定一個最佳候選特征。事實上，有些候選特征可能是冗余的，對特征選擇過程不起任何作用。通過這2方面的分析，上述2類模糊粗糙集特征選擇算法還不夠高效?；谶@2個動機，本文通過研究樣本篩選機制和特征搜索準則，在每次確定一個最佳候選特征后，縮小樣本和特征的搜索范圍，構造一個新的模糊粗糙集特征選擇算法。在UCI機器學習數(shù)據(jù)集上的實驗結果也表明該算法的有效性和時間高效性。

1 基于依賴函數(shù)的模糊粗糙集特征選擇

本節(jié)簡要介紹基于TM-相似關系的模糊粗糙集模型、正域、依賴函數(shù)及其特征選擇等相關概念。

1.1 模糊粗糙集

設U是一個非空論域，F(xiàn)(U×U)是U×U上的模糊冪集。R∈F(U×U)是U×U上的模糊二元關系。如果對任意x,y,z∈U，R是自反、對稱、TM傳遞的，則稱R是U上的一個模糊等價關系。

文獻[13]首次定義了如下模糊粗糙集的概念。

定義1[13]設U是非空論域，R是U上的一個模糊等價關系，X∈F(U)。對任意x∈U，X的模糊下、上近似算子分別定義為

基于上述模糊粗糙集，學者們構造了幾類廣義模糊粗糙集模型，有興趣的學者可參閱文獻[36-37]。本文的研究工作是在定義1的基礎上展開的。

1.2 模糊粗糙集特征選擇

本文用模糊決策表(U,A∪D)來表示一個數(shù)值或者混合數(shù)據(jù)集，其中U={x1,…,xn}是數(shù)據(jù)集中所有樣本的集合，A是數(shù)據(jù)集中描述樣本的所有特征構成的集合，D=p3xlrnl是決策特征的集合，用于確定數(shù)據(jù)中樣本的標簽或者類別。因此，U中的每個樣本x可由特征集合A描述，d(x)是樣本x的標簽。

性質1[38]設(U,A∪D)是模糊決策表，B?A。任意x∈U對其自身決策類[x]D的下、上近似隸屬度可簡化為

樣本x屬于其自身決策類下近似的隸屬度取值為[0,1]，它與x屬于模糊正域的隸屬度之間有下列關系。

樣本x屬于B的模糊正域的隸屬度實質上是x對其自身決策類下近似的隸屬度。

依賴函數(shù)取值于[0,1]，它的幾何含義可解釋為論域中所有樣本到其異類樣本最小距離的平均。模糊依賴函數(shù)也表明特征子集B對決策的擬合程度。

定義4[28,39]設(U,A∪D)是模糊決策表，P?A是決策表的一個約簡或最優(yōu)特征子集，若它滿足：

定義4中的條件1)表明約簡能保持決策表的依賴函數(shù)；條件2)表明約簡是保持決策表依賴函數(shù)不變的極小特征子集，即從約簡中刪去任何一個特征都不能保持決策表的依賴函數(shù)不變。

性質2[39]設(U,A∪D)是模糊決策表，B?C?A，則有

性質2表明隨著特征集合的增加，模糊決策表的正域和依賴函數(shù)單調遞增。這一結論是構造特征選擇算法的理論基礎。文獻[39-40]，已經(jīng)給出基于模糊依賴函數(shù)的特征選擇算法的具體形式，為了便于實驗比較，本文重新闡述基于依賴函數(shù)的模糊粗糙集特征選擇算法(用DFFS表示)。該算法從空集開始，逐步選擇一個使得依賴函數(shù)增加最大的候選特征，并將其加入當前所選特征子集中，直至數(shù)據(jù)集的模糊依賴函數(shù)保持不變。該算法的偽代碼如下。

算法1DFFS算法

輸入：決策表(U,A∪D)。

輸出：約簡P。

For eachai∈A-P

End for

End while

④輸出約簡P并終止算法。

在每次迭代過程中，該算法的步驟③都需遍歷數(shù)據(jù)集的所有樣本來計算每個可能的候選特征加入后的依賴函數(shù)，進而從所有剩余候選特征中確定一個最佳特征。這種搜索模式必須借助于數(shù)據(jù)集的所有樣本和當前所有剩余特征。當處理海量高維數(shù)據(jù)時，這種搜索模式常常需要花費大量運行時間。因此，為節(jié)省計算模糊粗糙集特征選擇的計算成本，本文進行了深入研究。

2 基于樣本和特征搜索空間不斷縮減的模糊粗糙集特征選擇算法

本節(jié)提出了一種基于樣本和特征搜索空間不斷縮減的模糊粗糙集特征選擇算法(用SSFFS表示該算法)。首先，基于性質2中樣本對其自身決策類下近似隸屬度單調遞增的特性，構造樣本篩選機制，用以篩除決策類下近似已被當前所選特征子集保持的樣本，這些樣本將不參與后續(xù)特征選擇過程中依賴函數(shù)的計算。其次，定義特征冗余性的概念，設計特征搜索準則，用以移除已被判定為冗余的特征，在后續(xù)特征選擇的過程中將不再搜索這些特征。最后，通過融合樣本篩選機制和特征搜索準則，相應的模糊粗糙集特征選擇算法得以設計。

根據(jù)性質2，有下列結論。

該定理表明，若當前所選特征子集B能保持樣本x對其自身決策類下近似的隸屬度，則在特征選擇的后續(xù)過程中，可不用再計算該樣本對正域的隸屬度，這樣的操作可節(jié)省樣本空間的搜索范圍。于是，就有了樣本篩選機制。

定義5表明，若加入候選特征a到B不能使依賴函數(shù)增加，則a相對于B是冗余的。

類似上述的推導，有

該引理表明在特征選擇過程中，若一個候選特征的加入不增加樣本的正域，則在后續(xù)特征選擇過程中，該候選特征的加入依然不增加該樣本的正域。

定理2對于a∈A-B，若a關于特征子集B是冗余的，則對任意C?B，a關于特征子集C也是冗余的。

該定理表明，在特征選擇的早期過程，已經(jīng)被判定為冗余的特征在后續(xù)特征選擇的過程中仍然是冗余的。因此，在特征選擇的過程中，可不搜索這些冗余特征，從而能節(jié)省特征選擇的運行時間?；诙ɡ?，本文給出如下特征搜索準則。

通過上述樣本篩選機制和特征搜索準則，本文設計了基于樣本和特征空間搜索范圍不斷縮減的模糊粗糙集特征選擇算法，簡記作SSFFS算法。

算法的思路如下：從空集P開始，將剩余特征集合left中的每個特征加入P中，計算每個候選特征加入后的依賴函數(shù)；將依賴函數(shù)增加最多的特征選作最佳的候選特征，并將其放入P中；計算最佳候選特征加入后的冗余樣本集合fs(P)和冗余特征集合rf(P)；在確定下一個最佳特征時，只需計算剩余候選特征集合A-P-rf(P)(而不是A-P)中每個特征加入后，U-fs(P)(而不是U中每個樣本的正域)中每個樣本的正域。通過重復上述步驟，當剩余樣本的個數(shù)為0或者剩余特征個數(shù)為0，算法就終止，從而得出數(shù)據(jù)集的一個約簡。

具體算法如算法2。

算法2SSFFS算法

輸入：決策表(U,A∪D)。

輸出：約簡P。

//*集合S是篩除冗余樣本后所剩樣本的集合；集合left是刪去冗余特征和最佳候選特征后所剩特征的集合。*/

③WhileS≠φandleft≠φdo

For eachai∈left

For eachxj∈S

//*計算集合S中每個樣本的正域*/

End for

End for

End while

④輸出約簡P并終止算法。

算法2能快速計算一個數(shù)據(jù)集的約簡。步驟②與算法1的步驟②一樣，都是計算U中每個樣本的正域，并計算依賴函數(shù)，其復雜度為O(|U|2|A|)。步驟③每次將已刪去冗余特征后的特征集合left中每個特征加入P，計算篩除冗余樣本后的集合S中每個樣本的正域，進而確定一個最佳候選特征，這種方式可有效縮減樣本和特征空間的搜索范圍，其復雜度為O(|left|(|P|+1)|S||U|)。而算法1中步驟②的復雜度為O(|A-P|(|P|+1)|U||U|)。顯然，|S|<|U|，|left|<|A-P|，故O(|left|(|P|+1)·|S||U|)

3 實驗結果與分析

為了驗證本文所提出的SSFFS算法的有效性和時間高效性，本節(jié)在8個UCI數(shù)據(jù)集上比較SSFFS算法與DFFS算法、RDRAR算法[25]、HANDI算法[32]。下面給出具體的實驗設置與結果分析。

3.1 實驗設置

實驗所用的具體運行環(huán)境配置如下：Intel(R)Core(TM)i7-7700 CPU @ 3.60GHz 3.60GHz(2 processors), 64.0GB。運行的軟件環(huán)境為：Matlab R2018b。實驗選取的8個數(shù)據(jù)集均來源于UCI機器學習數(shù)據(jù)庫(1)http://archive.ics.uci.edu/ml/index.php，詳見表1。

表1 實驗數(shù)據(jù)集

對表1中的每個數(shù)據(jù)集，采用十折交叉驗證法得到實驗結果。具體地，所有樣本被均分為10份，每份輪流作為測試集，剩下的9份作為訓練集。對任意一個訓練集中的特征，定義一個模糊等價關系Ra(xi,xj)=1-|a(xi)-a(xj)|，其中，xi和xj是該訓練集中的樣本。

在每個訓練數(shù)據(jù)集上，使用特征選擇算法得到相應的最有特征子集。在約簡后的訓練集上使用Matlab自帶的KNN訓練分類器，其中分類器的參數(shù)均為默認設置。將訓練好的分類器作用于約簡后的測試集，得到相應的分類精度。這個過程對每一對訓練集和測試集都執(zhí)行一次，因而最終報告的實驗結果是10次實驗結果的平均值。

本實驗將比較如下指標。

2)所選特征個數(shù)。每個特征選擇算法在10個訓練數(shù)據(jù)集上所選特征的平均個數(shù)。

3)分類精度。KNN分類器在約簡后的測試數(shù)據(jù)集上的平均分類精度。

3.2 實驗結果

首先給出SSFFS算法、DFFS算法、HANDI算法和RDRAR算法在每個數(shù)據(jù)集上的平均運行時間、所選特征個數(shù)、平均KNN分類精度；接著，證實SSFFS算法確實在特征選擇的每次迭代過程中都能刪去冗余的樣本和冗余的特征，從而說明它確實在幾乎每次迭代時都能減少樣本和特征的搜索空間。

表2列出了4個算法SSFFS、DFFS、HANDI和RDRAR在每個數(shù)據(jù)集上的平均運行時間，即每個特征選擇算法在每個數(shù)據(jù)集對應的10個訓練數(shù)據(jù)子集上的平均運行時間。從表2可以看出，在每個所選數(shù)據(jù)集上，SSFFS算法都比DFFS算法、HANDI算法和RDRAR算法快。具體地，在數(shù)據(jù)集Anneal上，SSFFS算法的運行時間分別是DFFS算法的運行時間的7.198 3%、HANDI算法的24.15%、RDRAR算法的31.19%。在高維數(shù)據(jù)集Gearbox上，SSFFS算法的運行時間僅是DFFS算法的運行時間的2.4%、HANDI算法的10.71%、RDRAR算法的28.74%。在大規(guī)模數(shù)據(jù)集Thyroid上，SSFFS算法的運行時間下降至DFFS算法的3.8%、HANDI算法的7.91%、RDRAR算法的4.26%。這些事實表明，與DFFS算法、HANDI算法和RDRAR算法相比，SSFFS算法可在最短的時間內獲取一個最佳特征子集。其主要原因在于，所提SSFFS算法的核心在于能在每次迭代的過程中縮小樣本空間和特征空間的搜索范圍，這種雙向縮小范圍的搜索模式可極大提高特征選擇的計算效率。

表2 不同特征選擇算法的運行時間

表3列出了4個特征選擇算法在每個數(shù)據(jù)集上所選特征的個數(shù)，其中Raw data表示原始數(shù)據(jù)集中特征的個數(shù)。從表3可看出，所提SSFFS算法在8個數(shù)據(jù)集上所選特征的平均個數(shù)僅為8，明顯小于原始數(shù)據(jù)集的平均特征個數(shù)39.6。SSFFS算法所選特征的平均個數(shù)也小于算法HANDI算法(平均個數(shù)為8.7)、DFFS算法(平均個數(shù)為26.4)以及RDRAR(平均個數(shù)為33.8)。這些實驗結果表明，所提SSFFS算法能刪去更多冗余特征。為了說明SSFFS算法對分類器性能的有效性，表4列出了每個數(shù)據(jù)集的KNN預測精度，其中Raw是KNN分類器在原始數(shù)據(jù)集上的分類精度。從表4可看出，SSFFS算法具有最高的平均分類精度0.908，其次是RDRAR算法的分類精度0.906 6，接著是DFFS算法的分類精度0.905 4，最后是HANDI算法的分類精度0.889 7。它們都比原始數(shù)據(jù)集的平均分類精度高(為0.874 8)。這一結果說明特征選擇確實可以改進學習算法的性能。

表3 不同特征選擇算法的所選特征的個數(shù)

表4 不同特征選擇算法的KNN平均分類精度

表2—表4表明，本文所提SSFFS算法不僅能快速地從數(shù)據(jù)集中選擇最有特征子集，也能有效減少冗余特征并能改善學習算法的分類性能。

圖1給出了SSFFS算法在每次迭代的時候，刪去冗余樣本和冗余特征的個數(shù)。從圖1能看出，SSFFS算法幾乎在每次迭代時都能移除冗余樣本和特征。比如在數(shù)據(jù)集Anneal上，一共執(zhí)行了4次迭代，每次迭代時分別移除了7，24，3，0個特征，同時每次迭代時分別移除了108，90，63，85個樣本。在數(shù)據(jù)集Park上，一共執(zhí)行了2次迭代，第1次迭代時移除了2個特征，324個樣本，第2次迭代時移除了24個特征，298個樣本。在大規(guī)模數(shù)據(jù)集Thyroid上，SSFFS算法一共執(zhí)行2次循環(huán)，第1次循環(huán)時刪去了20個特征和28個樣本，第2次循環(huán)時刪去了7個特征和880個樣本。這些結果證實，所提SSFFS算法確實在幾乎每次迭代過程中都能移除冗余樣本和冗余特征，能有效地減少樣本和特征的搜索范圍，從而極大地提高了特征選擇的計算效率。

圖1 每次迭代時SSFFS算法移除樣本和特征的個數(shù)

4 結 論

本文提出了一種基于樣本和特征空間搜索范圍不斷縮減的模糊粗糙集特征選擇算法，該算法的核心思想是樣本篩選機制和特征搜索準則的構造。具體地，本文首先利用每個樣本的正域隨特征單調遞增的性質，構造了樣本篩選機制，用以篩去正域已能被當前所選特征子集保持的樣本。其次，本文采用特征冗余的概念，構造了特征搜索準則，用以刪去不能使當前所選特征子集依賴函數(shù)增加的特征。接著，將樣本篩選機制和特征搜索準則相融合，提出了SSFFS算法。實驗結果表明SSFFS算法的有效性和高效性，SSFFS算法在每次迭代的過程中都能有效減少樣本和特征的搜索范圍。

本文的研究工作在基于TM-模糊粗糙集模型的基礎上展開的，下一步可以在廣義模糊粗糙集模型上作進一步驗證和研究。具體如下：①將本文的研究思想推廣至廣義粗糙集模型，構建廣義粗糙集模型特征選擇的快速算法；②本文的研究集中于數(shù)值數(shù)據(jù)集或者混合數(shù)據(jù)集的處理，并未涉及更復雜的數(shù)據(jù)集，諸如缺失數(shù)據(jù)、集合值數(shù)據(jù)、文本數(shù)據(jù)、圖片數(shù)據(jù)等，因此，后續(xù)研究也可以把本文的核心思想用于處理更加復雜的數(shù)據(jù)集，從而建立新的特征選擇快速算法；③特征選擇算法的穩(wěn)定性并未涉及，未來對其展開研究，將形成特征選擇穩(wěn)定性的豐富理論。