一種具有缺失數(shù)據(jù)的無(wú)監(jiān)督ReliefF特征選擇算法

薛露宇,宋 燕

1(上海理工大學(xué) 理學(xué)院,上海 200093) 2(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

1 引 言

近年來(lái),數(shù)據(jù)呈爆發(fā)式增長(zhǎng),同時(shí)伴隨著標(biāo)簽缺失,高維稀疏等問(wèn)題.因此,數(shù)據(jù)挖掘技術(shù)成為研究者們的熱門話題,其中聚類和特征降維是非常受歡迎的數(shù)據(jù)處理方法,廣泛應(yīng)用于機(jī)器學(xué)習(xí)、模式識(shí)別和圖像處理等領(lǐng)域[1,2].

在眾多聚類算法中,K均值算法(K-means)[3]作為典型的方法被廣泛用于現(xiàn)實(shí)生活應(yīng)用中,如市場(chǎng)調(diào)研[4]和數(shù)據(jù)挖掘[5,6]等.算法K-means屬于硬劃分,即樣本屬于一個(gè)簇的情況非0及1.但在現(xiàn)實(shí)中樣本屬于某一個(gè)簇的程度是不同的,因而導(dǎo)致簇之間存在模糊邊界.據(jù)此在聚類中引入模糊劃分的概念,由Bezdek[7]提出的模糊C均值算法(FCM,Fuzzy C Means)被應(yīng)用于各個(gè)領(lǐng)域[8-10],其通過(guò)“簇內(nèi)距離平方和最小化”準(zhǔn)則來(lái)實(shí)現(xiàn)對(duì)隸屬度的模糊化,隸屬度取值范圍在0～1之間.通常,FCM算法考慮的特征對(duì)數(shù)據(jù)的影響是同等重要的.然而,在大多數(shù)情況下,無(wú)關(guān)特征會(huì)影響聚類效果,導(dǎo)致產(chǎn)生錯(cuò)誤的聚類結(jié)果.因此,利用特征權(quán)重在FCM 中嵌入特征降維對(duì)改進(jìn)FCM有很大優(yōu)勢(shì).特征權(quán)重技術(shù)已經(jīng)應(yīng)用于聚類算法中[11-16],其中包括K-means和FCM的變體,如:加權(quán)K均值算法[11](WKM,Feature-Weighted K-means),基于熵加權(quán)的K-means[12](EWKM,entropy-weighted K-means),基于特征加權(quán)學(xué)習(xí)的加權(quán)FCM[13](WFCM,weighted FCM using feature-weighted learning)和特征降維的FCM[14](FRFCM,feature-reduction FCM).盡管以上算法考慮了特征信息,但是將特征降維過(guò)程嵌入聚類中的算法僅有WKM和FRFCM.算法FRFCM通過(guò)加權(quán)特征和消除權(quán)重小的特征來(lái)改進(jìn)模型,減少了特征數(shù)量的同時(shí)也減少了計(jì)算時(shí)間.但是,每一次迭代將移除權(quán)重小的特征,并未考慮特征的最終權(quán)重,導(dǎo)致在迭代前期時(shí)刪除比較重要的特征.同時(shí)計(jì)算特征權(quán)重的方式簡(jiǎn)單,導(dǎo)致特征權(quán)重計(jì)算存在不準(zhǔn)確性.

特征權(quán)重計(jì)算,并對(duì)特征進(jìn)行排序是特征選擇中比較常見(jiàn)的一種方法[17,18],其為了解決特征選擇的最佳搜索策略是組合優(yōu)化問(wèn)題,即一個(gè)NP-hard問(wèn)題而被提出.在目前存在的特征加權(quán)的算法中,Relief[19]算法因其簡(jiǎn)單性和高效性而被廣泛使用.因Relief只能處理二分類問(wèn)題,所以ReliefF[20]被提出用于多分類問(wèn)題中,并廣泛應(yīng)用于航空電子[21]、醫(yī)學(xué)[22]等領(lǐng)域[23,24].考慮到最近鄰在原始空間與權(quán)重空間中的定義不同,從而提出了iterative Relief(I-Relief)[25]和locally hyperplane Relief(LH-Relief)[26].其中,I-Relief中的最近鄰由k個(gè)近鄰的概率加權(quán)得到,而LH-Relief的最近鄰由局部線性超平面得到.對(duì)于以上兩種Relief的改進(jìn),僅考慮了最近鄰的分布特點(diǎn),并未考慮全局的數(shù)據(jù)分布,導(dǎo)致權(quán)重計(jì)算不準(zhǔn)確.同時(shí),Relief考慮特征之間的相似性移除無(wú)關(guān)特征,但缺乏對(duì)冗余特征的處理,冗余特征的存在會(huì)增強(qiáng)學(xué)習(xí)過(guò)程的負(fù)擔(dān)等問(wèn)題.ReliefF在計(jì)算特征權(quán)重的過(guò)程中,最重要的步驟之一是尋找樣本的同類最近鄰和異類最近鄰,當(dāng)類別的標(biāo)簽缺失時(shí),如何尋找最近鄰將成為一大難題.

此外,由于數(shù)據(jù)采集環(huán)境的復(fù)雜多變和儀器測(cè)量能力的限制等因素,不僅存在標(biāo)簽缺失的問(wèn)題,采集的數(shù)據(jù)大多存在缺失的情況.在面對(duì)這樣的數(shù)據(jù)集時(shí),大多聚類算法和特征選擇算法是無(wú)效的.因此對(duì)缺失數(shù)據(jù)的處理是非常有必要的[27,28].簡(jiǎn)單常見(jiàn)的填補(bǔ)缺失的方法有:均值填補(bǔ)[29]、K近鄰填補(bǔ)[30]和回歸算法填補(bǔ)[31]等.然而,由于這些算法沒(méi)有充分特征和分布特點(diǎn),對(duì)于缺失值估計(jì)的準(zhǔn)確性較低.為充分利用已知信息,非負(fù)潛在因子模型[28]被提出,該模型將Tikhonov正則化項(xiàng)整合到基于單元素法的非負(fù)矩陣分解當(dāng)中,使得模型的估計(jì)進(jìn)度更高,收斂速度更快.所以,我們選擇基于整合Tikhonov正則化和單元素法的非負(fù)矩陣分解模型[32](RSNMF,regularized single-element-based non-negative matrix factorization)來(lái)填補(bǔ)缺失值.

基于對(duì)以上方法的不足,針對(duì)無(wú)標(biāo)簽且缺失的數(shù)據(jù),在特征選擇算法中如何充分利用已知信息尋找樣本的近鄰和去除冗余特征,同時(shí)考慮原始空間與加權(quán)后的空間的不同如何有效聚類成為挑戰(zhàn),為解決這一系列問(wèn)題,本文提出了基于加權(quán)FCM的ReliefF方法,該方法的主要貢獻(xiàn)如下:

1)將每次迭代得到的最新的特征信息加入到FCM聚類中,并基于聚類結(jié)果尋找近鄰樣本,充分考慮特征信息并減小原始空間變化的影響;

2)在利用ReliefF計(jì)算特征權(quán)重時(shí),不僅考慮到了基于類與類中心距離的數(shù)據(jù)分布,還合理加入互信息,在移除無(wú)關(guān)特征的同時(shí)去除冗余信息;

3)在多個(gè)數(shù)據(jù)集上驗(yàn)證了所提出的算法在聚類效果、分類精度和誤差填補(bǔ)的效果對(duì)比其他算法有較為明顯的改善.本文所提出的算法在不同數(shù)據(jù)集上的最優(yōu)結(jié)果占75%以上,同時(shí),算法具有顯著性.

最后,通過(guò)對(duì)比實(shí)驗(yàn)證明了本文提出的特征選擇算法不僅能有效聚類,還能處理無(wú)標(biāo)簽數(shù)據(jù)的特征選擇問(wèn)題.

2 相關(guān)工作

2.1 FCM算法及FRFACM聚類算法

FCM算法是通過(guò)最小化如下所示目標(biāo)函數(shù),將一個(gè)由有限的數(shù)據(jù)組成的集合X={x1,…,xn}劃分為c個(gè)模糊聚類[6]:

(1)

其中,xi∈表示原始數(shù)據(jù)集X的第i列;n和c表示樣本數(shù)和聚類個(gè)數(shù);cg表示第個(gè)g聚類中心;U?{ugi},i=1,…,n,j=1,…,c是一個(gè)隸屬度矩陣;m是模糊因子,通常取m≥1.

通過(guò)運(yùn)用拉格朗日乘子法,可以得出隸屬度和聚類中心的迭代公式如下:

(2)

(3)

算法FRFCM通過(guò)將特征權(quán)重和特征權(quán)重熵加入到FCM中,從而改進(jìn)FCM,對(duì)其損失函數(shù)求導(dǎo),更新得到隸屬度uig,類中心cg和特征權(quán)重wj.因其特征權(quán)重的方式簡(jiǎn)單,導(dǎo)致特征權(quán)重計(jì)算存在不準(zhǔn)確性.

2.2 ReliefF算法

Relief是現(xiàn)有特征選擇加權(quán)算法中經(jīng)典的算法之一,以其簡(jiǎn)單有效而著稱.由于Relief只針對(duì)二元分類任務(wù)設(shè)計(jì),因此提出了針對(duì)多類分類任務(wù)的ReliefF.設(shè)有特征集合A={A1,A2,…,Ad},ReliefF算法的權(quán)重更新公式如下:

(4)

其中,t為迭代次數(shù),xi為在第i次迭代時(shí)隨機(jī)選擇的樣本,k為樣本xi的最近鄰的個(gè)數(shù).Hj被稱為nearest hit,為xi同類里的最近鄰,相反,Mj(C)被稱為nearest miss,為xi不同類里的最近鄰.class(xi)為xi的所在類別.P(C)為C類的先驗(yàn)概率.同時(shí)diff(Aa,x1,x2)為不同樣本x1,x2的同一特征A之間的不同,當(dāng)特征為名詞屬性時(shí),函數(shù)diff(Aa,x1,x2)的定義如下:

(5)

當(dāng)特征A是數(shù)值屬性時(shí),diff(Aa,x1,x2)定義為如下:

(6)

2.3 基于單元素和Tikhonov正則化的非負(fù)矩陣分解(RSNMF)

基于矩陣分解算法,一種結(jié)合單元素法和Tikhonov正則化項(xiàng)的方法被提出,在保證稀疏狀態(tài)下的非負(fù)性的同時(shí)準(zhǔn)確填補(bǔ)缺失值.首先,設(shè)有項(xiàng)目集合I和用戶集合U,其目標(biāo)設(shè)為dT并最小化目標(biāo)dT,其損失函數(shù)可表示為:

s.t.E,F≥0

(7)

基于目標(biāo)矩陣R已知值的單元素框架下的最小化問(wèn)題如下:

s.t.eu,k≥0,fk,i≥0

(8)

其中,RK表示由R的已知元素組成的集合;h是潛在因子空間的維數(shù),并滿足h?|U|和h?|I|;eu,k,fk,i,ru,i分別是矩陣E,F,R里面的元素.利用傳統(tǒng)的梯度下降(BGD)的方法更新參數(shù),公式(8)沒(méi)有非負(fù)約束的更新規(guī)則如下:

(9)

(10)

根據(jù)公式(10)的更新規(guī)則,項(xiàng)目潛在因子矩陣和用戶潛在因子矩陣將得到更新至收斂,缺失值將快速準(zhǔn)確地得到填補(bǔ).

3 基于加權(quán)FCM的ReliefF算法

文獻(xiàn)[14]通過(guò)加入特征信息,改進(jìn)FCM算法.但其計(jì)算特征權(quán)重的方式較為簡(jiǎn)單并且在每一次迭代時(shí)都會(huì)消除一些權(quán)重較小的特征,并未考慮特征的最終權(quán)重,導(dǎo)致在迭代前期時(shí)刪除比較重要的特征.同時(shí)傳統(tǒng)的ReliefF在計(jì)算特征權(quán)重時(shí)沒(méi)有考慮冗余特征的影響,導(dǎo)致模型學(xué)習(xí)的難度增大.此外,目前沒(méi)有基于缺失數(shù)據(jù)的聚類和特征選擇算法,因此基于上述已有的相關(guān)工作及其缺陷,本文提出一種基于加權(quán)FCM的ReliefF算法.

3.1 加入特征信息的FCM算法

考慮到原始空間與特征加權(quán)后的空間的不同,將更新的特征信息加入到FCM算法中,減少原始空間對(duì)聚類的影響.首先假設(shè)數(shù)據(jù)集D由樣本集合X={x1,…,xn}組成,特征為d維A={A1,A2,…,Ad},考慮加入特征權(quán)重向量的目標(biāo)函數(shù)為:

(11)

其中,xi為樣本,w=[w1,w2,…,wd]T∈d為特征權(quán)重向量,n為樣本個(gè)數(shù),c為聚類個(gè)數(shù);cg表示第g個(gè)聚類中心.通過(guò)對(duì)目標(biāo)函數(shù)J對(duì)隸屬度ugi和類中心cg求導(dǎo)得到其更新公式分別如下:

(12)

(13)

針對(duì)無(wú)標(biāo)簽數(shù)據(jù),根據(jù)聚類后的隸屬度uig,樣本xi在類別g的隸屬度大小,在隸屬度大的一類為樣本xi貼上標(biāo)簽.

3.2 基于改進(jìn)ReliefF的特征權(quán)重更新

在計(jì)算特征權(quán)重時(shí),本文并沒(méi)有已最小化目標(biāo)函數(shù)(11)來(lái)得到權(quán)重,而是根據(jù)ReliefF算法得到.因?yàn)镽eliefF計(jì)算權(quán)重時(shí)是根據(jù)類間距離和類內(nèi)距離的差異,此時(shí)得到的特征權(quán)重對(duì)于聚類和分類更具準(zhǔn)確性.針對(duì)無(wú)標(biāo)簽數(shù)據(jù)的特征選擇,根據(jù)上述聚類方法得到樣本所在類,尋找近鄰樣本.對(duì)于ReliefF計(jì)算特征權(quán)重首先需要定義邊界向量如下:

(14)

xRHm和xRMm(C)分別為樣本xi的同類最近鄰和異類(C類)最近鄰.為減少反常樣本的影響,本文根據(jù)聚類后的簇,找到與xi同類的k近鄰xRH和異類的k近鄰xRM.將總邊界向量設(shè)為z,定義如下:

(15)

z為d維向量,ReliefF算法最大化預(yù)期邊界:

s.t.wj≥0,j=1,2,…,d

(16)

對(duì)于經(jīng)典的ReliefF,去除了無(wú)關(guān)特征,但未考慮存在相似度極高的特征,即冗余特征,造成模型學(xué)習(xí)過(guò)程中的負(fù)擔(dān).所以本文中通過(guò)利用互信息Ij來(lái)測(cè)量特征之間的相似度,去除相似度過(guò)高的冗余特征.同時(shí),為充分考慮數(shù)據(jù)分布,在邊界函數(shù)ρ中引入基于類與類中心的距離的權(quán)重,強(qiáng)調(diào)邊界樣本的影響.首先假設(shè)互信息的集合為I={I1,I2,…,Id},第j個(gè)特征與其余特征的信息熵的和表示為:

(17)

同時(shí),引入距離權(quán)重的邊界函數(shù)重新定義為:

×|xi-xRMm(C)|-|xi-xRHm|)

(18)

其中,Cclass(xi)和Cc分別為xi所在類的中心和C類的中心,d(Cclass(xi),Cc)是其對(duì)應(yīng)的歐氏距離.其余的參數(shù)設(shè)置與公式(4)、公式(14)中相同.總邊界向量定義與公式(15)定義相同.考慮信息熵與距離權(quán)重,并同時(shí)引入特征權(quán)重向量的0范數(shù),改進(jìn)的ReliefF算法的目標(biāo)為最大化邊界函數(shù)并最小化非零特征權(quán)重的個(gè)數(shù),即目標(biāo)函數(shù)定義如下:

s.t.wj≥0,j=1,2,…,m

(19)

其中,w=[w1,w2,…,wd]T∈d為特征權(quán)重向量,wj為特征j的權(quán)重,λ>0為正則化項(xiàng)系數(shù).雖然0范數(shù)保證了稀疏性,但公式(19)因?yàn)?范數(shù)存在難以優(yōu)化.所以將1范數(shù)引入替換0范數(shù),1范數(shù)不僅保證了稀疏性,而且分段可微,較易優(yōu)化.同時(shí)用logistic regression表現(xiàn)特征估計(jì),目標(biāo)函數(shù)變換為如下:

s.t.wj≥0,j=1,2,…,d

(20)

為優(yōu)化更簡(jiǎn)便,指定一個(gè)新的變量v=[v1,v2,…,vd]T∈d,并令則公式(20)變換為:

s.t.vj≥0,j=1,2,…,d

(21)

(22)

其中,1為元素全部為1的一列向量,η為學(xué)習(xí)速率并且有η>0.在已知ρi的情況下,特征權(quán)重向量通過(guò)公式(22)解得.

3.3 改進(jìn)算法的算法流程

基于加權(quán)FCM的ReliefF算法(WFCM-IReliefF,Improved ReliefF Based on WFCM)的基本流程如下:

輸入:數(shù)據(jù)集D,類別個(gè)數(shù)c,迭代次數(shù)maxlter,閾值θ,學(xué)習(xí)速率η,正則化系數(shù)λ

輸出:特征權(quán)重向量w

2.whilet

3. 通過(guò)公式(13)計(jì)算類中心;

4. 根據(jù)cg和特征權(quán)重,通過(guò)公式(12)更新隸屬度;

5. 根據(jù)公式(17)計(jì)算互信息向量I;

6. fori=1 to n do

7. 通過(guò)隸屬度ugi得到簇,在相應(yīng)簇內(nèi)找到近鄰樣本xRH和xRM;

8. 通過(guò)公式(18)計(jì)算xi的邊界向量ρi;

9. end for

10. 通過(guò)目標(biāo)函數(shù)(21),得到解v;

13. break;

14. else

15.t=t+1;

16. end if

17.end while

18.返回目前的特征權(quán)重向量wt.

經(jīng)過(guò)ReliefF后得到的特征權(quán)重降序排列,選擇權(quán)重大的特征表示此特征為重要且具代表性的特征.所選出的特征子集擁有此數(shù)據(jù)集的特性,達(dá)到了降維的效果.此時(shí),缺失值存在,造成預(yù)測(cè)誤差.因此利用RSNMF模型填補(bǔ)缺失,傳統(tǒng)的梯度下降(BGD)的方法更新模型,會(huì)造成巨大的計(jì)算成本.隨機(jī)梯度下降算法(SGD)有較慢的收斂速度的問(wèn)題.因此,本文運(yùn)用小批量梯度下降(MGDB)的方法,提高更新更新速率的同時(shí)降低了陷入局部最優(yōu)的風(fēng)險(xiǎn).本文方法的流程圖如圖1所示.

圖1 方法流程圖Fig.1 Flow chart of method

3.4 算法復(fù)雜度計(jì)算

首先,算法復(fù)雜度計(jì)算分為兩部分,一是特征選擇部分,二是矩陣分解部分.假設(shè)樣本數(shù)為n,類別數(shù)為c,特征數(shù)為d,迭代次數(shù)為t,潛在因子為h,|RK|為已知元素個(gè)數(shù).特征選擇的時(shí)間復(fù)雜度為O((nc2d+nc)(n(c-1)+d)),將其化簡(jiǎn)得到O(n2c3d-n2c2d+nc2d2+n2c2-n2c+ncd),保留其最高項(xiàng),則特征選擇的時(shí)間復(fù)雜度最終為O(n2c3d+nc2d2).接下來(lái),矩陣分解部分的時(shí)間復(fù)雜度為O(|RK|×t×h).將兩部分的時(shí)間復(fù)雜度相加得到算法的最終復(fù)雜度O(n2c3d+nc2d2+th|RK|).最后,在矩陣分解模型中有緩存矩陣E,F,RK和4個(gè)輔助矩陣,其空間復(fù)雜度為O(|U|×h+h×|I|+|RK|).所以本文算法的空間復(fù)雜度為O(n+c+d+|U|×h+h×|I|+|RK|).

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

4.1 數(shù)據(jù)集與數(shù)據(jù)集預(yù)處理

數(shù)據(jù)集:實(shí)驗(yàn)采用的數(shù)據(jù)集選自UCI數(shù)據(jù)庫(kù)中的Wine、WDBC(Wisconsin (Diagnostic) of Breast Cancer data set)、Spectfhear、Sonar、Libras movement、Hill-valley、Madelon數(shù)據(jù)集,具體的信息,如表1所示.實(shí)驗(yàn)環(huán)境:操作系統(tǒng)為Ubuntu 16.04,配置為2.10GZ,24Inter(R) Xeon(R),2塊TITAN,在Python 3平臺(tái)開(kāi)發(fā).

表1 實(shí)驗(yàn)數(shù)據(jù)集信息Table 1 Details of datasets

數(shù)據(jù)集預(yù)處理:1)本文將數(shù)據(jù)映射到0～5的區(qū)間內(nèi),有利于加快模型的收斂;2)隨機(jī)缺失:本文將每個(gè)數(shù)據(jù)集進(jìn)行隨機(jī)缺失,缺失率為30%,每個(gè)實(shí)驗(yàn)重復(fù)10次,取平均值作為最后的結(jié)果;3)數(shù)據(jù)集劃分:將數(shù)據(jù)集劃分為80%的訓(xùn)練集和20%的測(cè)試集,并使用5折交叉驗(yàn)證尋找最優(yōu)參數(shù).

4.2 評(píng)價(jià)指標(biāo)和參數(shù)設(shè)置

評(píng)價(jià)指標(biāo):本文針對(duì)聚類,特征選擇和矩陣分解分別設(shè)置三類評(píng)價(jià)指標(biāo),分別評(píng)估聚類精度,分類精度和填補(bǔ)誤差效果.首先,聚類效果的評(píng)價(jià)指標(biāo)為調(diào)整蘭德指數(shù)(ARI)和調(diào)整互信息(AMI),其值在-1～1之間,值越大表示聚類效果與真實(shí)情況越吻合.其次,對(duì)于特征選擇,本文采用支持向量機(jī)(SVM)、隨機(jī)森林(RF)和AdaBoost 3個(gè)分類器來(lái)檢驗(yàn)其效果,評(píng)價(jià)指標(biāo)為準(zhǔn)確率(ACC).最后,針對(duì)矩陣分解任務(wù),本文采用均方根誤差(RMSE)和平均絕對(duì)誤差(MAE)來(lái)測(cè)量其誤差.誤差越小表示填補(bǔ)數(shù)據(jù)越準(zhǔn)確.

參數(shù)設(shè)置:本文采用5折交叉驗(yàn)證尋找最優(yōu)超參數(shù).首先,在改進(jìn)的ReliefF算法中,最近鄰個(gè)數(shù)k根據(jù)經(jīng)驗(yàn)設(shè)置為5.其次,在矩陣分解中,小批量梯度下降中的參數(shù)c根據(jù)經(jīng)驗(yàn)設(shè)置為0.9,根據(jù)文獻(xiàn)[32]本文將迭代次數(shù)設(shè)置為1000,同時(shí)為加速參數(shù)尋優(yōu)的進(jìn)程將正則化系數(shù)設(shè)置為相等λE=λF.對(duì)于通過(guò)交叉驗(yàn)證尋找的最優(yōu)參數(shù)互信息的閾值g,潛在因子h和正則化系數(shù)λE=λF,由于文章篇幅的限制,本文將列舉method11在數(shù)據(jù)集Libras Movement上的參數(shù)設(shè)置過(guò)程作為參考.如圖2所示,method11在數(shù)據(jù)集Libras Movement上不同參數(shù)g,h和λE=λF的RMSE,展示了當(dāng)g=4.9,h=30,λE=λF=0.001,得到最小的RMSE為0.2700,因此將method11在數(shù)據(jù)集Libras Movement上的參數(shù)設(shè)置為g=4.9,h=30,λE=λF=0.001.所有算法的參數(shù)根據(jù)相同的方式,具體設(shè)置如表2所示.

圖2 method11在不同參數(shù)g,h,λE=λF上的RMSE結(jié)果Fig.2 RMSE result of method11 with values of g, h, λE=λF

表2 參數(shù)設(shè)置Table 2 Parameter setting

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

為了測(cè)試本文提出算法的性能,采用表1所示的數(shù)據(jù)集,在數(shù)據(jù)集的缺失度為30%的情況下,本文在比較聚類效果時(shí),對(duì)比4種聚類算法,分別為K-means,FCM,WKM和FRFCM算法.對(duì)于存在的缺失先進(jìn)行均值填補(bǔ).因?yàn)镵-means和FCM算法沒(méi)有特征選擇的功能,所以在進(jìn)行分類效果比較時(shí),只選擇WKM和FRFCM算法.同時(shí)在誤差比較時(shí),均值填補(bǔ)并不準(zhǔn)確,所以需要通過(guò)矩陣分解算法對(duì)缺失值進(jìn)行精確填補(bǔ).即本文采用組合形式.算法具體信息如表3所示.

表3 所有測(cè)試算法Table 3 All tested methods

表3中Method5和Method9-11為本文中提出的方法,Method9是將傳統(tǒng)ReliefF計(jì)算得到的特征權(quán)重嵌入FCM,Method10是在ReliefF中加入了距離權(quán)重,為解決傳統(tǒng)ReliefF不能移除冗余特征的問(wèn)題,Method11將互信息嵌入ReliefF,以此來(lái)改進(jìn)的特征選擇的效果.實(shí)驗(yàn)結(jié)果如表4～表10所示.此外,本文對(duì)結(jié)果進(jìn)行了顯著性驗(yàn)證.原假設(shè)H0為算法結(jié)果與原標(biāo)簽結(jié)果之間不存在顯著性差異,在顯著性水平α=0.05的情況下,p>0.05接受原假設(shè),p≤0.05則拒絕原假設(shè).實(shí)驗(yàn)結(jié)果如表11所示.

表4 聚類算法ARI指標(biāo)比較Table 4 Performance of ARI of different algorithms

表5 聚類算法AMI指標(biāo)比較Table 5 Performance of AMI of different algorithms

表6 在分類器SVM上的分類精度比較Table 6 Performance of classification accuracy on SVM

表7 在分類器RF上的分類精度比較Table 7 Performance of classification accuracy on RF

表8 在分類器AdaBoost上的分類精度比較Table 8 Performance of classification accuracy on AdaBoost

表9 填補(bǔ)缺失值誤差RSME比較Table 9 Errors of imputation missing data on RSME

表10 填補(bǔ)缺失值誤差MAE比較Table 10 Errors of imputation missing data on MAE

表11 所有算法顯著性檢驗(yàn)結(jié)果Table 11 Significance test results of different algorithms

上述表4～表10實(shí)驗(yàn)結(jié)果,均是算法運(yùn)行10次取平均值.算法的最好結(jié)果用黑體顯示.為更清晰地表達(dá)算法的優(yōu)勢(shì),圖3～圖5描繪了不同的數(shù)據(jù)集上每個(gè)算法在不同的分類器上的分類精度.

首先從表4和表5可以看出,本文提出的基于改進(jìn)ReliefF的加權(quán)FCM算法在兩個(gè)聚類指標(biāo)下的聚類準(zhǔn)確性在大多數(shù)數(shù)據(jù)集上都很高,除了特殊情況,Method4在數(shù)據(jù)集Sonar上的ARI最高為0.6548和Metohd1在Wine數(shù)據(jù)集上的AMI最高為0.4810.Method5在14個(gè)聚類結(jié)果中有12個(gè)聚類結(jié)果是最優(yōu)的.說(shuō)明本文提出的方法在聚類效果上有較大提升.

其次,通過(guò)表6～表8不同的分類器的分類效果來(lái)看,最高分類精度總體集中在Method9-Method11,其中Method11在不同數(shù)據(jù)集上的21個(gè)分類結(jié)果有16個(gè)分類結(jié)果是最好的,說(shuō)明本文提出的算法與WKM和FRFCM相比,能在數(shù)據(jù)缺失的情況下找到最優(yōu)的特征子集,同時(shí)說(shuō)明加入數(shù)據(jù)分布信息和互信息的ReliefF相比傳統(tǒng)的ReliefF能有效去除無(wú)關(guān)特征和冗余特征,保留關(guān)鍵特征.此外,Method11在不同的分類器下的分類精度占大部分的最高分類精度,也說(shuō)明改進(jìn)的特征選擇算法具有普遍性,不依賴分類器.

此外,表9和表10記錄了進(jìn)行特征選擇后的填補(bǔ)缺失值的誤差.首先,Method6對(duì)比其他方法并未進(jìn)行特征選擇,從表中可以看出RSME和MAE的值普遍較大,即誤差較大,說(shuō)明在填補(bǔ)誤差之前的有必要進(jìn)行特征選擇,特征選擇為矩陣分解減少了無(wú)關(guān)特征和冗余特征的影響,降低了填補(bǔ)缺失值的誤差.同時(shí),在14個(gè)誤差比較的結(jié)果中Method11的最小誤差占了12個(gè),再次說(shuō)明了本文提出的特征選擇算法能選擇最優(yōu)的特征子集,同時(shí)能降低在缺失值填補(bǔ)時(shí)的誤差.通過(guò)三類評(píng)價(jià)指標(biāo)的評(píng)估,本文提出的方法不僅在聚類和分類效果上具有優(yōu)秀的表現(xiàn),而且在填補(bǔ)誤差填補(bǔ)上有較優(yōu)的 效果.同時(shí)從表11可以看出,通過(guò)對(duì)聚類,分類和填補(bǔ)缺失的結(jié)果進(jìn)行顯著性檢驗(yàn),絕大多數(shù)都能接受原假設(shè).

5 結(jié)束語(yǔ)

針對(duì)缺失數(shù)據(jù)的特征選擇方法仍存在無(wú)法有效判斷樣本近鄰,缺乏對(duì)特征信息的充分考慮,冗余信息影響缺失值填補(bǔ)等問(wèn)題.本文通過(guò)聚類、特征選擇和矩陣分解算法,提出了針對(duì)缺失數(shù)據(jù)基于改進(jìn)ReliefF的加權(quán)FCM算法.該方法首先在FCM算法中加入特征權(quán)重來(lái)減小原始空間和特征空間的不同造成的影響,同時(shí)生成聚類標(biāo)簽,為ReliefF尋找最近鄰時(shí)提供有效的依據(jù),同時(shí)每次迭代更新的特征權(quán)重由ReliefF計(jì)算得到.為移除數(shù)據(jù)集中存在的冗余特征,在ReliefF中加入距離分布信息和互信息來(lái)減少冗余信息的影響.最后,為精確填補(bǔ)缺失值,利用矩陣分解算法來(lái)填補(bǔ)缺失,并利用小批量梯度下降進(jìn)行模型學(xué)習(xí),減少計(jì)算成本.通過(guò)對(duì)多個(gè)數(shù)據(jù)集在不同的評(píng)價(jià)指標(biāo)下的評(píng)估,本文提出的一種具有缺失數(shù)據(jù)的無(wú)監(jiān)督ReliefF特征選擇算法具有較高的聚類、分類精度和較小的填補(bǔ)誤差.本文的算法為無(wú)監(jiān)督的特征選擇領(lǐng)域提供了新的方法,同時(shí)為具有缺失數(shù)據(jù)的特征選擇提供了新的思路.然而,本文存在一定的缺陷,如計(jì)算復(fù)雜度較高等問(wèn)題,這也將是未來(lái)工作努力的方向.