程鳳偉 ,王文劍 ,張珍珍

（1.太原學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，太原，030032；2.計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西大學(xué)，太原，030006）

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，信息的多樣化及信息的產(chǎn)生速度有質(zhì)的飛躍，使數(shù)據(jù)呈爆發(fā)式增長(zhǎng)，數(shù)據(jù)挖掘［1］需要分析的對(duì)象也愈加復(fù)雜，如自然語(yǔ)言處理領(lǐng)域中的文本文檔數(shù)據(jù)［2］、計(jì)算機(jī)視覺領(lǐng)域中的圖像數(shù)據(jù)［3-4］和生物信息學(xué)領(lǐng)域中的基因表達(dá)數(shù)據(jù)等［5-7］，這些數(shù)據(jù)具有高維性和小樣本的共性，即特征維數(shù)遠(yuǎn)遠(yuǎn)高于樣本數(shù).這類數(shù)據(jù)通常有成百上千個(gè)特征，而且，隨著特征維度的急劇增加，冗余特征、噪聲特征以及無(wú)關(guān)的特征都降低了分類模型的性能，因此，降維是機(jī)器學(xué)習(xí)和模式分類中的一項(xiàng)重要任務(wù)，特征選擇是一種受到廣泛關(guān)注的降維手段［8］.

ReliefF 算法［9］是一種成功的特征選擇器，因簡(jiǎn)單有效而被廣泛研究，其前身為Relief 算法，1992 年由Kira and Rendell［10］提出，根據(jù)各個(gè)特征和類別的相關(guān)性賦予特征不同的權(quán)重來處理兩類數(shù)據(jù)的分類問題.ReliefF 算法是Relief 算法的多類擴(kuò)展，可以很好地增強(qiáng)對(duì)噪聲的容忍性.現(xiàn)有工作往往聚焦于對(duì)ReliefF 算法在近鄰表達(dá)［11-12］、樣本效率［13］、標(biāo)簽相關(guān)性［14-15］等方面的改進(jìn)，或試圖克服其在不同類型任務(wù)上面臨的挑戰(zhàn)，包括回歸問題［16］、數(shù)據(jù)缺失［17-18］以及數(shù)據(jù)非平衡［19-20］等.此外，ReliefF 算法已在入侵檢測(cè)［21］、醫(yī)療診斷［22-23］以及圖像分類［24］等實(shí)際領(lǐng)域中取得了成功應(yīng)用.傳統(tǒng)的ReliefF 算法雖然可以很好地對(duì)特征進(jìn)行排序，但無(wú)法去除特征冗余，即得到的特征子集中仍存在冗余項(xiàng)，這些冗余特征會(huì)影響分類的性能［25-27］.針對(duì)這一問題，陳平華等［28］將基于互信息特征選擇的手段與ReliefF 算法結(jié)合，利用ReliefF 算法得到特征權(quán)重，再通過計(jì)算特征與特征間的互信息來剔除冗余特征.但當(dāng)特征維數(shù)較高時(shí)，啟發(fā)式地計(jì)算特征與特征之間的互信息的代價(jià)巨大，這類方法變得不再適用.而高維小樣本數(shù)據(jù)的樣本量較少，本文針對(duì)數(shù)值型的微陣列基因數(shù)據(jù)，采用鄰域粗糙集理論來度量特征子集及特征的依賴度，從而剔除冗余信息，這比計(jì)算互信息的方法［26-29］更高效.

特征維數(shù)較高時(shí)，在分類任務(wù)中構(gòu)造特征子集通常采用“一刀切”的方式，即截取與標(biāo)記相關(guān)性較高的若干特征來進(jìn)行分類，但這種方式忽略了特征組合對(duì)分類結(jié)果的影響.在特征選擇中，將權(quán)重高的特征組合起來不一定有好的分類性能，因此前m個(gè)特征組成的子集不一定是分類性能最好的特征子集［30］.基于子空間的技術(shù)是一種很好的考慮全局信息的手段，劉景華等［31］提出基于局部子空間的特征選擇方法，根據(jù)重要性的不同程度在子空間中設(shè)定不同的采樣比例來進(jìn)行選擇，以提高算法的分類性能.然而，該方法基于互信息來剔除冗余特征，在特征維數(shù)較高時(shí)代價(jià)較高，且該方法按特征權(quán)重的大小排序后進(jìn)行采樣來選擇特征，沒有考慮不同的特征組合對(duì)分類性能的影響.

針對(duì)以上問題，本文提出基于層次子空間的ReliefF 特征選擇算法（Hierarchical Subspace-Based ReliefF，HS-ReliefF），其主要思想是，首先，將原始特征集劃分成具有兩層層次結(jié)構(gòu)的子空間，其中高層子空間利用隨機(jī)法劃分獲得，低層子空間按照ReliefF 算法對(duì)特征賦權(quán)的大小排序后進(jìn)行升序均勻劃分獲得；然后，利用鄰域粗糙集理論來度量低層子空間的局部依賴度，經(jīng)閾值篩選后批量地剔除冗余特征；最后，提出“局部領(lǐng)導(dǎo)力”的概念，保留部分無(wú)法直接剔除的子空間中“帶隊(duì)”能力較強(qiáng)的特征.重復(fù)多次以上過程來求取特征權(quán)重的均值，得到最終的特征權(quán)重向量，根據(jù)實(shí)際情況挑選特征子集進(jìn)行后續(xù)的分類任務(wù).

1 相關(guān)工作

1.1 ReliefFReliefF 算法［9］是Relief 算法的擴(kuò)展，其通過選取k個(gè)最近鄰樣本點(diǎn)來應(yīng)對(duì)不完備和噪聲數(shù)據(jù)，使特征選擇器更加魯棒.ReliefF 算法從訓(xùn)練集中隨機(jī)選擇一個(gè)樣本Ri，然后從和Ri同類的樣本中選取k個(gè)最近鄰樣本NHt(t=1，…，k)，同時(shí)，從和Ri不同類的樣本中尋找k個(gè)最近鄰樣本Mt(t=1，…，k).ReliefF 更新特征的權(quán)重如下：

其中，NMt(C)為第C個(gè)不同類的第t個(gè)最近鄰點(diǎn)，P(C)為類C的先驗(yàn)概率，以上過程重復(fù)m次.

1.2 鄰域粗糙集粗糙集理論中通常把特征稱為屬性，本文涉及的鄰域粗糙集的相關(guān)內(nèi)容均用屬性表示特征.本節(jié)主要介紹鄰域粗糙集下的正域、依賴以及屬性的重要度［32］.

定義1給定實(shí)數(shù)空間上的非空有限集合U={x1，x2，…，xn}，對(duì)于U上的任意樣本xi，定義δ-鄰域?yàn)椋?/p>

其中，dist(x，xi)為距離函數(shù)，δ≥0.

定義2給定一鄰域決策系統(tǒng)NDS=U，A，D，決策屬性D將論域U劃分為N個(gè)等價(jià)類(X1，X2，…，XN)，?B?A，則決策屬性D關(guān)于特征子集B的上、下近似分別為：

可得決策系統(tǒng)的正域?yàn)椋?/p>

定義3給定一鄰域決策系統(tǒng)NDS=U，A，D，?B?A，決策屬性D對(duì)條件屬性集B的依賴度為：

若γB-a(D)＜γB(D)，那么a對(duì)于B是必不可少的；否則，γB-a(D)=γB(D)，那么a是多余的，D對(duì)于子集B中的屬性a的依賴度為0.

2 基于層次子空間的ReliefF 特征選擇算法

簡(jiǎn)單地說，HS-ReliefF 算法主要包含兩部分：一是結(jié)合層次子空間技術(shù)與鄰域粗糙集理論來批量地剔除冗余特征；二是引入“局部領(lǐng)導(dǎo)力”考量特征對(duì)其所處子空間的相對(duì)依賴程度，保留部分較為重要的特征.

2.1 批量剔除冗余特征高維小樣本數(shù)據(jù)的特點(diǎn)之一是特征維數(shù)較高.子空間（Subspace）技術(shù)是一種有效的特征?；侄?，將原始的高維特征空間降低為多個(gè)低維的特征空間，這樣可以從局部角度處理數(shù)據(jù)，或使用契合分布式模型、集成模型等，提高計(jì)算效率與性能.劉景華等［31］提出局部子空間技術(shù)，即通過計(jì)算特征與標(biāo)記集合之間的互信息來對(duì)特征進(jìn)行排序，按特征權(quán)重的大小將原始特征集均勻地劃分為三個(gè)子空間，根據(jù)不同的重要程度在子空間中設(shè)定不同的采樣比例，進(jìn)一步在每個(gè)子空間中計(jì)算特征與特征之間的互信息來剔除冗余特征.顯然，此方法僅適用于特征維數(shù)較低的數(shù)據(jù)，因?yàn)樵诟呔S數(shù)據(jù)中啟發(fā)式地計(jì)算特征與特征之間的互信息的代價(jià)較大，且度量單個(gè)特征的重要度的過程在大部分情況下也是多余的，因此，批量地剔除冗余特征不失為一個(gè)較好的選擇.本文提出一種層次子空間的手段，將原始特征集劃分成具有兩層層次結(jié)構(gòu)的子空間，具體操作如下.

（1）利用隨機(jī)法將原始特征集劃分為K個(gè)子空間，這一層為兩層結(jié)構(gòu)中的高層，記為H level.與劉景華等［31］按照權(quán)重大小劃分子空間的方法相比，隨機(jī)法考慮了不同特征組合對(duì)分類性能的影響，且本文采取多次隨機(jī)劃分求取平均的方式來增強(qiáng)模型的魯棒性.

（2）高層中的每個(gè)子空間需要進(jìn)一步進(jìn)行劃分.在ReliefF 算法對(duì)特征排序的基礎(chǔ)上，按照權(quán)重大小對(duì)H level 的K個(gè)子空間依次進(jìn)行均勻劃分，得到K×N個(gè)子空間，這一層為兩層結(jié)構(gòu)中的低層，記為L(zhǎng) level.此過程是為接下來批量剔除冗余特征做準(zhǔn)備.

高維小樣本數(shù)據(jù)的另一個(gè)特點(diǎn)是樣本數(shù)量較少.和計(jì)算特征與特征之間互信息的方法相比，利用鄰域粗糙集來構(gòu)造數(shù)值型數(shù)據(jù)的特征重要度要簡(jiǎn)單得多，在劃分好的子空間的基礎(chǔ)上，依次度量低層子空間的依賴度，直接剔除依賴度小于閾值的子空間，便可以高效地批量剔除冗余特征.

定義5給定一鄰域決策系統(tǒng)NDS=，A為原始特征集，?B?A，B為其中任意一個(gè)H level 子空間，?R?B，R為子空間B下的任意L level 子空間，則在高層子空間B下，決策屬性D對(duì)低層子空間R的依賴度為：

定義6給定一鄰域決策系統(tǒng)NDS=，A為原始特征集，?B?A，B為其中任意一個(gè)H level 子空間，?R?B，R為子空間B下的任意L level 子空間，則在高層子空間B下，低層子空間R的重要度定義為：

定義5 和定義6 給出了低層子空間的局部依賴度和局部重要度，通過設(shè)置閾值來剔除重要度較小的子空間，達(dá)到批量剔除冗余特征的目的.

2.2 考慮局部領(lǐng)導(dǎo)力的特征加權(quán)方法高層子空間使用隨機(jī)法劃分獲得，經(jīng)過多次隨機(jī)劃分求取平均的方式可以增強(qiáng)模型的魯棒性.隨機(jī)劃分的另一個(gè)好處是可以對(duì)重要度不同的特征進(jìn)行隨機(jī)組合，結(jié)合局部與全局的角度給予特征更客觀的評(píng)價(jià).因?yàn)榈蛯幼涌臻g中特征的重要度是一個(gè)相對(duì)的概念，對(duì)于依賴度處于閾值邊緣的低層子空間，不僅要剔除其中的冗余特征，還要對(duì)保留的特征進(jìn)行進(jìn)一步的評(píng)價(jià).若子空間的整體依賴度很大且其中的冗余特征較多，則被保留的重要的特征“帶隊(duì)”能力越強(qiáng)，應(yīng)給予更高的權(quán)重.對(duì)此，本文提出“局部領(lǐng)導(dǎo)力”的概念，即結(jié)合特征在子空間中的表現(xiàn)以及其所在子空間的整體表現(xiàn)來共同評(píng)價(jià)該特征.

定義7給定一鄰域決策系統(tǒng)NDS=，A為原始特征集，?B?A，B為其中任意一個(gè)H level 子空間，?R?B，R為子空間B下的任意L level 子空間.?a?R，低層子空間R中屬性a的重要度為：

則該屬性a的“局部領(lǐng)導(dǎo)力”（Local Leadership，LLs）定義為：

其中，Softmax 函數(shù)為：

其中，zi表示第i個(gè)屬性的重要度，C為子空間R中的屬性個(gè)數(shù).Softmax 函數(shù)能體現(xiàn)子空間中每個(gè)屬性與其他屬性的“差距懸殊”程度，這種差距的懸殊即反映了屬性的“帶隊(duì)”能力；同時(shí)，結(jié)合當(dāng)前子空間R的整體依賴度，構(gòu)造屬性a的“局部領(lǐng)導(dǎo)力”，在高層子空間多次隨機(jī)劃分的前提下，同時(shí)從局部和全局的角度為屬性a額外增加更客觀的評(píng)價(jià)來更新屬性a的權(quán)重.更新公式為：

2.3 基于局部子空間的ReliefF 特征選擇方法前文介紹了層次子空間法以及考慮局部領(lǐng)導(dǎo)力的特征加權(quán)法.層次子空間法將原始特征集劃分為具有層次結(jié)構(gòu)的子空間，這樣可以批量地剔除冗余信息；考慮局部領(lǐng)導(dǎo)力的特征加權(quán)法構(gòu)造了“局部領(lǐng)導(dǎo)力”的評(píng)價(jià)標(biāo)準(zhǔn)，在保留部分重要特征的同時(shí)，可以給予特征更客觀的評(píng)價(jià).HS-ReliefF 算法的詳細(xì)步驟如下，示意圖如圖1 所示.由于無(wú)法確定數(shù)據(jù)集中實(shí)際存在的冗余特征個(gè)數(shù)，設(shè)定輸入?yún)?shù)T，表示在每個(gè)高層子空間中預(yù)設(shè)的剔除子空間的數(shù)量.

圖1 本文算法的示意圖Fig.1 The schematic diagram of our algorithm

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果

3.1 數(shù)據(jù)集及實(shí)驗(yàn)設(shè)置為了測(cè)試提出的算法的有效性，選取六個(gè)微陣列基因數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，表1 為所有數(shù)據(jù)集的詳細(xì)信息，所有數(shù)據(jù)均經(jīng)過歸一化處理.

表1 實(shí)驗(yàn)使用的數(shù)據(jù)集描述Table 1 Description of datasets used in experiments

由于數(shù)據(jù)樣本量較小，采取3 折交叉驗(yàn)證，用KNN 分類器對(duì)特征選擇結(jié)果進(jìn)行測(cè)試.對(duì)比算法為：特征選擇結(jié)果采用全部特征的ReliefF 算法（ReliefF）、特征選擇結(jié)果截取前I個(gè)特征（Cut I）的ReliefF 算法（ReliefF-CI）以及MFSLS 算法［31］.為公平起見，將MFSLS 算法利用計(jì)算特征與標(biāo)記集合的互信息得到的初始化特征權(quán)重改為利用ReliefF 算法得到的特征權(quán)重，且該算法的采樣比例直接選擇最好的結(jié)果[0.6，0.3，0.1]，即MFSLS-631.所有實(shí)驗(yàn)在3.6 GHz Intel Core 和16 G 內(nèi)存的電腦上完成，Windows 10，Matlab R2014a.

3.2 參數(shù)選擇實(shí)驗(yàn)中的一個(gè)主要參數(shù)為最終挑選出來用于分類任務(wù)的特征子集的特征數(shù)I.由于MFSLS-631 算法在構(gòu)造子空間時(shí)的特殊性，其最終挑選的特征子集的大小固定為數(shù)據(jù)集全部特征維數(shù)的1/3，對(duì)此，本文在高維的微陣列基因數(shù)據(jù)上也保持MFSLS-631 算法的參數(shù)設(shè)定.對(duì)于HS-ReliefF，ReliefF 以及ReliefF-CI 算法，設(shè)置I的大小占全部特征維數(shù)的比重的取值為[0.1，0.2，0.3，0.4，0.5]，這樣設(shè)置的目的是I較小時(shí)，可以體現(xiàn)特征選擇結(jié)果的好壞，I較大時(shí)可以體現(xiàn)冗余特征剔除結(jié)果的好壞.下文中I的取值直接用比重代替特征數(shù).

本文提出的HS-ReliefF 算法中，影響冗余剔除的參數(shù)主要是預(yù)設(shè)的剔除子空間的數(shù)量T、剔除子空間時(shí)的重要度閾值θ以及低層子空間保留重要特征的閾值δ.其中，與參數(shù)I直接相關(guān)的是T和δ.根據(jù)HS-ReliefF 算法中Step 4 所述，參數(shù)T決定了需要進(jìn)行篩選的特征的數(shù)量，即可能被剔除的特征的范圍.T越大，說明需要篩選的特征越多，得到的結(jié)果越準(zhǔn)確客觀.最終挑選的特征子集的特征數(shù)由I決定，因此將參數(shù)T設(shè)定為：

由于HS-ReliefF 算法采用多次隨機(jī)求取平均的方法，高層子空間及低層子空間的個(gè)數(shù)的設(shè)定對(duì)結(jié)果的影響不大，因此，實(shí)驗(yàn)中統(tǒng)一設(shè)定每個(gè)高層子空間包含100 個(gè)左右的特征(SB=100)，低層子空間包含10 個(gè)左右的特征(SR=10)，相應(yīng)地，設(shè)置參數(shù)K=A/SB，N=SB/SR.此外，子空間保留重要特征的閾值δ直接決定低層子空間中需要被剔除的冗余特征的數(shù)量，但由于無(wú)法準(zhǔn)確獲知冗余特征的具體數(shù)量，只能人為指定閾值δ，本文設(shè)定δ∈[0.1，0.4]，并在3.3 對(duì)閾值δ進(jìn)行實(shí)驗(yàn)分析，選取最佳結(jié)果.最后，對(duì)于剔除子空間時(shí)的重要度閾值θ，Praveena et al［22］指出θ應(yīng)設(shè)置為一個(gè)非常貼近0 的正數(shù)，本文設(shè)置θ=0.01，這樣可以保守地批量剔除冗余特征，盡可能避免誤刪有用的特征.

3.3 實(shí)驗(yàn)結(jié)果及分析為了保證實(shí)驗(yàn)對(duì)比的公平性，分別在挑選的特征子集維數(shù)相同和不同的情況下進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如表2 和表3 所示，表中黑體字表示在各數(shù)據(jù)集上最好的結(jié)果.

表2 特征子集維數(shù)相同時(shí)各算法平均精度對(duì)比(I=0.33)Table 2 The average accuracy of each algorithm with the same dimension of feature subset (I=0.33)

表3 特征子集維數(shù)不同時(shí)各算法平均最大精度的對(duì)比(I∈[0.1,0.2,0.3,0.4,0.5])Table 3 The average maximum accuracy of each algorithm with different dimension of feature subset (I∈[0.1，0.2，0.3，0.4，0.5])

表2 展示了在特征子集維數(shù)相同的情況下各算法用于分類任務(wù)的平均最大精度，其中特征子集的大小固定為數(shù)據(jù)集全部特征維數(shù)的1/3，即I=0.33.由表可知，在統(tǒng)一特征維數(shù)的情況下，本文的HS-ReliefF 算法能更有效地剔除冗余特征，提升分類性能；MFSLS-631 算法在這些高維數(shù)據(jù)上表現(xiàn)欠佳，因?yàn)樵撍惴ㄔ诓蓸訒r(shí)舍棄了部分特征，這些特征在高維數(shù)據(jù)中可能同樣是重要的，也正因如此，其性能表現(xiàn)不如“一刀切”的方法（ReliefF-CI）.

鑒于此，單獨(dú)分析ReliefF-CI 和HS-ReliefF算法在特征子集維數(shù)不同時(shí)表現(xiàn)出的性能差異，驗(yàn)證本文提出的方法在考慮特征組合方面的有效性，實(shí)驗(yàn)結(jié)果如表3 所示.表3 展示了在特征子集維數(shù)不同時(shí)ReliefF-CI 和HS-ReliefF 算法用于分類任務(wù)的平均最大精度對(duì)比，其中，ReliefF 算法為基準(zhǔn)算法，ReliefF-CI 和HS-ReliefF 算法在截取特征子集時(shí)保持相同的特征數(shù).由表可知，本文的HS-ReliefF 算法在大多數(shù)情況下都有最優(yōu)或相當(dāng)?shù)男阅?值得注意的是，當(dāng)I=0.1，0.2 和0.3 時(shí)，ReliefF-CI 和HS-ReliefF 算法在subramanian，tian 和yeoh 數(shù)據(jù)集上表現(xiàn)的性能相當(dāng)，而且都顯著優(yōu)于基準(zhǔn)算法.這是因?yàn)樯鲜鋈齻€(gè)數(shù)據(jù)集的特征維數(shù)都較高，I較小時(shí)選擇的特征質(zhì)量相當(dāng)，幾乎不受冗余特征的影響，因此，在增大I以后（I=0.4 和0.5 時(shí)），HS-ReliefF 算法在剔除冗余特征方面的優(yōu)勢(shì)得到了部分體現(xiàn).

此外，由于子空間保留重要特征的閾值δ決定了被剔除的冗余特征的數(shù)量，進(jìn)而影響不同特征子集維數(shù)下的分類性能，本文在三個(gè)代表數(shù)據(jù)集alon，subramanian 和tian 上分析了HS-ReliefF算法在選擇不同的δ時(shí)對(duì)分類性能的影響，實(shí)驗(yàn)結(jié)果如圖2 所示，圖中不同的I對(duì)應(yīng)的最高柱點(diǎn)與表3 的結(jié)果互相對(duì)照，顏色越淺，性能越好.由圖可見，當(dāng)I很?。↖=0.1，0.2 和0.3）時(shí)，該算法在三個(gè)數(shù)據(jù)集上的分類性能幾乎不受δ的影響，這是由于此時(shí)包含冗余特征的概率很小.I增大（I=0.4 和0.5）時(shí)，閾值δ的選擇會(huì)影響挑選特征子集的分類性能.在alon 數(shù)據(jù)集上，整體性能隨著I的增大呈下降趨勢(shì)，因此，δ較小時(shí)，算法可以保留有價(jià)值的特征，表現(xiàn)更好；在subramanian 和tian數(shù)據(jù)集上，算法的整體性能卻呈上升趨勢(shì)，因?yàn)棣妮^大時(shí)，算法更能剔除所選特征子集中的冗余特征，表現(xiàn)更好.

圖2 在不同維數(shù)的特征子集上HS-ReliefF 算法閾值δ 的選擇對(duì)其分類性能的影響Fig.2 Classification performance of HS-ReliefF with different threshold δ on different dimensional feature subsets

額外地，圖3 展示了各算法在六個(gè)數(shù)據(jù)集上的分類性能受特征子集維數(shù)的影響情況，其中，ReliefF 和MFSLS-631 算法始終保持固定的特征子集維數(shù)，在圖中用實(shí)心點(diǎn)和實(shí)心塊表示.根據(jù)分析，不同的數(shù)據(jù)集中包含的冗余特征數(shù)不同，當(dāng)特征子集維數(shù)較小時(shí)，分類性能受到特征對(duì)于標(biāo)記的分類信息影響，當(dāng)特征子集維數(shù)較大時(shí)，分類性能受到特征子集中冗余特征的數(shù)量影響.由圖可知，本文提出的算法無(wú)論在特征子集維數(shù)較小或較大時(shí)，都有不錯(cuò)的表現(xiàn).

圖3 不同維數(shù)的特征子集下各算法分類性能對(duì)比Fig.3 Accuracy of each algorithm on different dimension feature subsets

最后，對(duì)比MFSLS-631 和HS-ReliefF 算法處理數(shù)據(jù)的時(shí)間消耗，實(shí)驗(yàn)結(jié)果如表4 所示，表中黑體字表示耗時(shí)較少.由表可見，高維數(shù)據(jù)中，計(jì)算特征與特征之間互信息的代價(jià)十分大.對(duì)于給定的鄰域決策系統(tǒng)，其時(shí)間復(fù)雜度為O(|U|·|A|2)，而利用鄰域粗糙集理論處理數(shù)據(jù)的復(fù)雜度為O(|A|·|U|2)，由于高維小樣本數(shù)據(jù)的樣本數(shù)普遍很小，即|U|?|A|，因此，本文提出的HS-ReliefF 算法在處理數(shù)據(jù)的時(shí)間消耗方面有很大優(yōu)勢(shì).此外，HS-ReliefF 算法始終在RliefF 算法得到的初始特征權(quán)重向量上進(jìn)行權(quán)重調(diào)整，沒有增加額外的空間復(fù)雜度.

表4 各數(shù)據(jù)集上MFSLS-631 和HS-ReliefF 算法處理數(shù)據(jù)過程的平均時(shí)間(單位：s)對(duì)比Table 4 Average dealing time (unit：s) of MFSLS-631 and HS-ReliefF on each dataset

4 結(jié)論

現(xiàn)有的改進(jìn)ReliefF 算法在高維小樣本數(shù)據(jù)上通過計(jì)算特征與特征之間的互信息剔除冗余特征，代價(jià)較高，而且沒有考慮特征之間的組合對(duì)分類性能的影響.因此，本文提出基于層次子空間的ReliefF 特征選擇算法HS-ReliefF，將原始特征集劃分為具有層次結(jié)構(gòu)的子空間，利用鄰域粗糙集理論批量地剔除冗余特征，大大提高了算法的運(yùn)行效率；同時(shí)，引入“局部領(lǐng)導(dǎo)力”的概念，考慮不同特征組合對(duì)算法性能的影響，從局部和全局的角度共同給予特征更客觀的評(píng)價(jià).

在六個(gè)微陣列基因數(shù)據(jù)集上的實(shí)驗(yàn)表明，與現(xiàn)有算法相比，HS-ReliefF 更高效，且能保持良好的分類性能.值得說明的是，HS-ReliefF 算法同時(shí)也是一種處理高維小樣本數(shù)據(jù)的框架，可以很好地契合分布式、集成式等系統(tǒng)，更高效地完成任務(wù).

算法的不足之處在于控制剔除冗余特征的閾值仍須人為指定，不能確定最佳特征子集.如何自適應(yīng)地確定相關(guān)參數(shù)是下一步研究的重點(diǎn).