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

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

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

0 引 言

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

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

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

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

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

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

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

1.1 模糊粗糙集

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

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

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

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

1.2 模糊粗糙集特征選擇

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

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

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

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

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

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

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

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

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

算法1DFFS算法

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

輸出：約簡(jiǎn)P。

For eachai∈A-P

End for

End while

④輸出約簡(jiǎn)P并終止算法。

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

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

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

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

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

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

類似上述的推導(dǎo)，有

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

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

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

通過(guò)上述樣本篩選機(jī)制和特征搜索準(zhǔn)則，本文設(shè)計(jì)了基于樣本和特征空間搜索范圍不斷縮減的模糊粗糙集特征選擇算法，簡(jiǎn)記作SSFFS算法。

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

具體算法如算法2。

算法2SSFFS算法

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

輸出：約簡(jiǎn)P。

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

③WhileS≠φandleft≠φdo

For eachai∈left

For eachxj∈S

//*計(jì)算集合S中每個(gè)樣本的正域*/

End for

End for

End while

④輸出約簡(jiǎn)P并終止算法。

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 實(shí)驗(yàn)設(shè)置

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

本實(shí)驗(yàn)將比較如下指標(biāo)。

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

表2 不同特征選擇算法的運(yùn)行時(shí)間

表3列出了4個(gè)特征選擇算法在每個(gè)數(shù)據(jù)集上所選特征的個(gè)數(shù)，其中Raw data表示原始數(shù)據(jù)集中特征的個(gè)數(shù)。從表3可看出，所提SSFFS算法在8個(gè)數(shù)據(jù)集上所選特征的平均個(gè)數(shù)僅為8，明顯小于原始數(shù)據(jù)集的平均特征個(gè)數(shù)39.6。SSFFS算法所選特征的平均個(gè)數(shù)也小于算法HANDI算法(平均個(gè)數(shù)為8.7)、DFFS算法(平均個(gè)數(shù)為26.4)以及RDRAR(平均個(gè)數(shù)為33.8)。這些實(shí)驗(yàn)結(jié)果表明，所提SSFFS算法能刪去更多冗余特征。為了說(shuō)明SSFFS算法對(duì)分類器性能的有效性，表4列出了每個(gè)數(shù)據(jù)集的KNN預(yù)測(cè)精度，其中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)。這一結(jié)果說(shuō)明特征選擇確實(shí)可以改進(jìn)學(xué)習(xí)算法的性能。

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

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

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

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

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

4 結(jié) 論

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

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