基于改進(jìn)ReliefF的無(wú)監(jiān)督特征選擇方法①

丁雪梅, 王漢軍, 王炤光, 周心圓

1(中國(guó)科學(xué)院 沈陽(yáng)計(jì)算技術(shù)研究所,沈陽(yáng) 110168)

2(中國(guó)科學(xué)院大學(xué),北京 100049)

3(國(guó)家電網(wǎng)公司東北分部,沈陽(yáng) 110180)

4(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,長(zhǎng)春 130000)

特征選擇是指從原始特征集中選出一個(gè)使得評(píng)估標(biāo)準(zhǔn)達(dá)到最優(yōu)的特征子集的過程[1]. 對(duì)于一個(gè)概念學(xué)習(xí)問題,優(yōu)秀的學(xué)習(xí)樣本是訓(xùn)練分類器的關(guān)鍵,樣本中的不相關(guān)或冗余特征會(huì)使學(xué)習(xí)算法陷入混亂導(dǎo)致分類器過擬合[2],影響訓(xùn)練性能. 因此有效的特征選擇對(duì)于加速學(xué)習(xí)速度和提高概念質(zhì)量具有重要作用.

特征選擇根據(jù)是否包含類別信息分為有監(jiān)督的特征選擇和無(wú)監(jiān)督的特征選擇. 無(wú)監(jiān)督特征選擇的目的是根據(jù)一定的評(píng)判標(biāo)準(zhǔn),選擇出一個(gè)足夠簡(jiǎn)練又能夠充分描繪原始特征集的重要特性同時(shí)保障數(shù)據(jù)集原生分類性的特征子集. 針對(duì)無(wú)監(jiān)督特征選擇,已經(jīng)提出了一些方法,根據(jù)是否于后續(xù)的學(xué)習(xí)方法相關(guān),可分為過濾式(Filter) 和封裝式(Wrapper)兩種[3]. Filter模型獨(dú)立于學(xué)習(xí)算法,利用所有訓(xùn)練數(shù)據(jù)的統(tǒng)計(jì)性能,選取相關(guān)性評(píng)價(jià)準(zhǔn)則進(jìn)行特征評(píng)估. 文獻(xiàn)[4]引入核空間距離測(cè)度,通過計(jì)算兩類樣本點(diǎn)在核空間的距離度量相關(guān)性,有效提高了線性不可分?jǐn)?shù)據(jù)的特征選擇能力. 文獻(xiàn)[5]采用互信息來度量相關(guān)性,以此達(dá)到無(wú)監(jiān)督最小冗余最大相關(guān)(UmRMR)的特征選擇的標(biāo)準(zhǔn). 文獻(xiàn)[6]使用拉普拉斯分值評(píng)價(jià)特征的重要程度,以極大程度保留原始特征集和整體幾何結(jié)構(gòu)信息為原則選擇分值較小的部分特征形成特征子集. Tabakhi S[7]以特征作為結(jié)點(diǎn),特征間余弦相似度作為邊的權(quán)值建立圖模型; 使用蟻群算法,引入信息素的概念啟發(fā)式搜索相似度最小的路徑,所歷結(jié)點(diǎn)形成最終特征子集. 然而以上過濾式方法單純以數(shù)據(jù)本身的統(tǒng)計(jì)信息或關(guān)系作為依據(jù)進(jìn)行特征選擇,沒有考慮特征對(duì)于數(shù)據(jù)原生性分類的影響.特征選擇知識(shí)理論中分類性能也可作為所選特征子集的度量標(biāo)準(zhǔn). 在Wrapper模型中,特征選擇算法與學(xué)習(xí)算法耦合在一起,利用學(xué)習(xí)算法的分類準(zhǔn)確率評(píng)估特征子集. 針對(duì)無(wú)監(jiān)督問題則是以特定聚類算法的聚類結(jié)果的質(zhì)量來估量特征子集. 例如Yuan等人[8]對(duì)數(shù)據(jù)域進(jìn)行特征聚類,然后通過構(gòu)建熵測(cè)度來揭示不同特征子集的最優(yōu)值以此評(píng)估該特征子集的重要性.Zhu等人[9]提出了一種子空間聚類指導(dǎo)特征選擇的方法,該方法維持并迭代更新一個(gè)特征選擇矩陣,矩陣的列向量反饋每個(gè)子空間聚類的代表性特征. 但是該類方法計(jì)算量大,時(shí)間復(fù)雜度較高,無(wú)法適用于大規(guī)模數(shù)據(jù)的特征選擇.

ReliefF是公認(rèn)的效果較好的過濾式(Filter)特征評(píng)估方法[10],不同于上述過濾式方法,ReliefF利用特征對(duì)于分類的影響來評(píng)估特征權(quán)重,同時(shí)對(duì)數(shù)據(jù)類型沒有限制,運(yùn)行效率高,能夠應(yīng)對(duì)大規(guī)模的數(shù)據(jù). 針對(duì)其易忽略小類樣本、不能削減冗余特征等不足,本文提出了一種基于改進(jìn)ReliefF的無(wú)監(jiān)督特征選擇算法(UFS-IR),繼承ReliefF優(yōu)點(diǎn)的同時(shí)特征選擇結(jié)果更可靠、更準(zhǔn)確,獲得符合UmRMR標(biāo)準(zhǔn)的特征子集.

1 無(wú)監(jiān)督特征選擇

無(wú)監(jiān)督特征選擇是指按照某一評(píng)價(jià)準(zhǔn)則從原始高維特征集中篩選出部分特征形成最優(yōu)特征子集,使它對(duì)原始數(shù)據(jù)的自然分類效果的影響足夠小或者沒有.

定義已知包含n個(gè)特征X1,X2,…,Xn的數(shù)據(jù)集D,其中Xi=(S1,S2,S3,…,Sk),k∈N*(非零自然數(shù)); 給定方法Method,按照某一準(zhǔn)則J評(píng)價(jià)各個(gè)特征Xi,篩選出其中部分特征Xi,Xj,…,Xm(1≤i,j,m≤n且i,j,m∈N*)獲取最終的特征子集.

2 改進(jìn)ReliefF算法

2.1 ReliefF算法

Relief系列算法一種高效的過濾式特征選擇方法,最早于1992年由Kira和Rendell提出用于二分類問題的特征選擇算法[11]. 1994年Kononenko對(duì)Relief進(jìn)行分析和擴(kuò)展,使得ReliefF能夠用來處理噪聲、不完整和多類數(shù)據(jù)集[12].

ReliefF基于特征對(duì)各個(gè)類的近距離樣本的區(qū)分能力,賦予特征不同的權(quán)重來評(píng)估特征,特征權(quán)值越大意味著它更有助于區(qū)分類別. 當(dāng)特征與分類相關(guān)性極低時(shí),特征的權(quán)值將足夠小接近0; 特征權(quán)值計(jì)算結(jié)果可能出現(xiàn)負(fù)值,表示同類近鄰樣本的距離比不同類近鄰樣本的距離大,這也意味著該特征對(duì)于分類的影響是負(fù)面的.

對(duì)于樣本集Q,每次從中隨機(jī)選擇一個(gè)樣本S,然后S的同類樣本集中尋找k個(gè)S的近鄰樣本NH,同時(shí)每個(gè)與S不同類別的樣本集中各尋找k個(gè)近鄰樣本NM. 迭代更新每個(gè)特征的權(quán)重ω(x),更新公式為：

式中,m表示迭代次數(shù),NHj表示同類的第j個(gè)近鄰樣本,NM(C)j表示不同類的C類樣本的第j個(gè)近鄰樣本,P(C)表示第C類目標(biāo)的概率,Class(S)表示樣本S所屬的類別,diff(X,S,S')表示樣本S和S'關(guān)于特征X的距離.

2.2 改進(jìn)ReliefF算法

雖然ReliefF算法不限制數(shù)據(jù)類型為離散或是連續(xù)型,能應(yīng)對(duì)多類別的數(shù)據(jù),擁有較高的評(píng)估效率和有效性,但它仍存在以下不足.

(1) 算法隨機(jī)采樣的次數(shù)m將影響最終得出的各個(gè)特征的權(quán)值.

(2) 隨機(jī)采樣的策略使得小類樣本被選中的幾率很低甚至不被選中,如果忽略小類別樣本對(duì)更新特征權(quán)重的影響,那么最終的結(jié)果準(zhǔn)確性和合理性是不可靠的.

(3) 隨機(jī)采樣可能存在重復(fù)抽樣的情況,重復(fù)抽樣的樣本將對(duì)特征權(quán)值的更新產(chǎn)生無(wú)意義的重復(fù)影響,使得有限抽樣次數(shù)內(nèi)的有效抽樣率降低,從而降低了特征權(quán)值結(jié)果的有效性和可靠性.

(4) 算法得出的特征權(quán)值,只能評(píng)估特征對(duì)分類的貢獻(xiàn)值并不能幫助刪除冗余特征.

本文針對(duì)以上不足的(2)(3)(4)對(duì)ReliefF算法加以改善. 在抽樣的隨機(jī)性不變的前提下,控制每一類樣本被抽樣到的次數(shù),以各類樣本占所有有效樣本的比例ξ設(shè)置每一類樣本被抽樣的次數(shù)ξm,彌補(bǔ)ReliefF算法隨機(jī)選樣時(shí)小類別樣本被選中概率低的不足. 同時(shí)控制每一次抽樣的樣本不是重復(fù)抽樣,總是對(duì)特征權(quán)值更新賦予新的影響,充分發(fā)揮數(shù)據(jù)集在有限次數(shù)內(nèi)對(duì)特征評(píng)估的效用. 針對(duì)ReliefF算法無(wú)法刪除冗余特征,引進(jìn)調(diào)整的余弦相似度來衡量特征間的相關(guān)性,結(jié)合特征評(píng)估結(jié)果去除相關(guān)特征對(duì)中的一個(gè)元素.

2.3 調(diào)整的余弦相似度

余弦相似度通過計(jì)算兩個(gè)向量的夾角余弦值來評(píng)估他們的相似度. 余弦值的范圍在[-1,1]之間,值越趨近于1,代表兩個(gè)向量的方向越接近越相似; 越趨近于-1,他們的方向越相反; 接近于0,表示兩個(gè)向量近乎于正交.

向量X=(X1,X2,…,Xn)和Y=(Y1,Y2,…,Yn)的余弦相似度為：

余弦相似度衡量的是空間向量的夾角,僅僅從方向上區(qū)分向量的差異,而對(duì)絕對(duì)數(shù)值不敏感,向量數(shù)值的成比例縮放不改變余弦相似度計(jì)算結(jié)果. 余弦相似度對(duì)數(shù)值的不敏感導(dǎo)致了結(jié)果的誤差,調(diào)整的余弦相似度ACS修正了這種不合理性,在向量所有維度上的數(shù)值Xi都減去一個(gè)均值[13],也使得衡量向量的相似性轉(zhuǎn)變?yōu)楹饬肯嚓P(guān)性.

向量X=(X1,X2,…,Xn)和向量Y=(Y1,Y2,…,Yn)的調(diào)整余弦相似度為：

3 算法設(shè)計(jì)

3.1 基礎(chǔ)算法

傳統(tǒng)ReliefF算法的設(shè)計(jì)是針對(duì)于有監(jiān)督的特征選擇,數(shù)據(jù)的類別信息是算法的主要支撐. 引入ReliefF算法進(jìn)行無(wú)監(jiān)督特征選擇的首要任務(wù)就是獲知數(shù)據(jù)類別. 聚類是將樣本觀測(cè)值,數(shù)據(jù)項(xiàng)或特征向量劃分成簇的無(wú)監(jiān)督分類模式[14],能夠完成對(duì)無(wú)監(jiān)督樣本的分類. DBSCAN是一種基于密度聚類算法的典型代表,它能夠把具有足夠密度的區(qū)域劃分為簇,聚類速度快,對(duì)聚類簇的形狀毫無(wú)偏倚,能夠在具有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的簇,同時(shí)有效處理噪聲數(shù)據(jù)防止對(duì)有效樣本形成的評(píng)估結(jié)果產(chǎn)生干擾. 因此本文以DBSCAN聚類結(jié)果形成的簇定義數(shù)據(jù)的類別,以此支撐UFS-IR算法.

DBSCAN定義參數(shù)eps來表示每個(gè)對(duì)象的鄰域半徑,對(duì)象o的eps鄰域是以o為中心、以eps為半徑的空間. 鄰域的大小由參數(shù)eps確定,鄰域的密度用鄰域內(nèi)的對(duì)象數(shù)度量. 通過另一參數(shù)minPts,即指定稠密區(qū)域的密度閾值,來衡量鄰域是否稠密. 如果一個(gè)對(duì)象的eps鄰域至少包含minPts個(gè)對(duì)象,則稱該對(duì)象為核心對(duì)象. 通過連接核心對(duì)象及其鄰域內(nèi)其他核心對(duì)象的鄰域,形成稠密區(qū)域作為簇.

算法1. DBSCAN

輸入： 數(shù)據(jù)集D,半徑eps,核心點(diǎn)鄰域內(nèi)點(diǎn)最少數(shù)目

輸出： 所有簇集合

1. 標(biāo)記D中每一個(gè)點(diǎn)為unvisited

2. for eachainD

3. if (aisunvisited)

4. if (ois not核心點(diǎn)) 標(biāo)記點(diǎn)o為噪音;

5. else //ais核心點(diǎn)

6. 點(diǎn)o及其鄰域E內(nèi)的所有點(diǎn)形成一個(gè)新簇C;

7. for (eachpina的鄰域)

8. if (pisunvisited)

9. if (pis核心點(diǎn))

10. 將點(diǎn)p的鄰域內(nèi)的所有點(diǎn)加入簇C;

11. else

12. if (p沒有加入其它任何一個(gè)簇)

13. 將p加入簇C;

14. if (p被標(biāo)記為噪音) 取消標(biāo)記p為噪音;

15. end

3.2 基于改進(jìn)ReliefF的無(wú)監(jiān)督特征選擇算法UFS-IR

UFS-IR (Unsupervised Feature Selection based on Improved ReliefF)算法通過DBSCAN聚類算法給樣本標(biāo)注聚類標(biāo)簽來指定樣本數(shù)據(jù)的類別,為將ReliefF算法應(yīng)用到無(wú)監(jiān)督特征選擇提供數(shù)據(jù)基礎(chǔ). 采用DB INDEX (Davies Bouldin index,DBI)準(zhǔn)則來判斷DBSCAN聚類的有效性,選擇DBI值較小的一組(eps,minPts)參數(shù)對(duì)數(shù)據(jù)進(jìn)行聚類. 使用不同采樣策略控制每個(gè)類別樣本被抽樣總次數(shù)ξm,確保m次抽樣中不出現(xiàn)重復(fù)抽取樣本,彌補(bǔ)ReliefF算法隨機(jī)選樣時(shí)小類別樣本對(duì)更新特征權(quán)重的影響容易被忽略這一不足的同時(shí)充分發(fā)揮每一次采樣對(duì)特征評(píng)估的效用. 至此改進(jìn)的ReliefF算法得到分類相關(guān)的特征集合T保證最終得到的特征子集F的最大相關(guān)性,但是它仍舊無(wú)法保證特征子集內(nèi)部的低冗余度,在對(duì)含有類別信息的數(shù)據(jù)處理時(shí)有些學(xué)者使用分類器的正確率來篩選特征[15,16],但是無(wú)法適用無(wú)監(jiān)督特征選擇中. 所以本文改進(jìn)ReliefF使用ACS系數(shù)來衡量特征間的相關(guān)性,結(jié)合集合T保留強(qiáng)相關(guān)特征對(duì)中權(quán)值較大的特征來保障F的最小冗余性.

UFS-IR算法描述如下：

定義已知包含n個(gè)特征X1,X2,…,Xn的數(shù)據(jù)集D,其中Xi=(S1,S2,S3,…,Sk); 使用聚類算法DBSCAN,分別為D中k個(gè)樣本劃分類別指定標(biāo)簽Y,使用改進(jìn)ReliefF評(píng)價(jià)各個(gè)特征Xi對(duì)于這種分類的影響,計(jì)算ACS(Xi,Xj)衡量特征間的相關(guān)性,削減特征子集的冗余度,獲取最終特征子集.

輸入： 樣本數(shù)據(jù)集D,迭代次數(shù)n,鄰域半徑eps,樣本閾值minPts,抽樣次數(shù)m,最近鄰樣本的個(gè)數(shù)k,ACS閾值λ

輸出： 最優(yōu)特征子集

1. 初始化所有特征的權(quán)值為0,標(biāo)記所有樣本點(diǎn)為unvisited

2. 使用DBSCAN算法處理D,計(jì)算本次聚類的DBI

3. fori=2 ton

4. 調(diào)整(eps,minPts),計(jì)算DBI2

5. if (DBI2＜DBI)DBI=DBI2并記錄當(dāng)前(eps,minPts)

6. 以最終(eps,minPts)作為DBSCAN的參數(shù)對(duì)D進(jìn)行聚類,標(biāo)記聚類結(jié)果,刪除噪音得到數(shù)據(jù)集D'

7. 初始化每個(gè)聚類簇在m次抽樣中被抽中的次數(shù)n=ξm,其中ξ為各聚類簇樣本占D'中總樣本數(shù)的比例

8. fori=1 tom

9. 從D’中隨機(jī)抽取一個(gè)標(biāo)記為unvisited的樣本R;

10. 判斷R所屬類別允許抽中次數(shù)的剩余值n是否等于0;

11. if (R所屬類別的n==0) 回到(5);

12. else將R標(biāo)記為visited;

13. 從R的同簇樣本集中尋找k個(gè)最近鄰樣本NHj(j=1,2,…,k),從R的每一個(gè)不同簇樣本集中尋找k個(gè)最近鄰樣本NM(C)j(j=1,2,…,k);

14. forX=1 toN//N為特征總數(shù)

15. 根據(jù)公式(1)更新特征權(quán)值;

16. 刪除權(quán)值為負(fù)數(shù)或小于非負(fù)權(quán)值的均值的特征,將剩余特征按權(quán)值降序排列得到集合T;

17. 基于D,一個(gè)特征的所有值形成一個(gè)向量,計(jì)算T中特征兩兩間的ACS系數(shù);

18. 保留值大于等于閾值λ的特征對(duì)pairs集合Q;

19. for eachpairsinQ

20. if (pairs中的元素都在T中)

21. 保留權(quán)值較大的特征Y;

22. if(F不包含Y) 將Y加入集合F;

23. 輸出F,得到最優(yōu)特征子集;

24. end

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

為了體現(xiàn)算法的有效性,實(shí)驗(yàn)選擇了如表1所示來自UCI (University of California Irvin)機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)和多倫多大學(xué)Delve Datasets的四個(gè)不同規(guī)模數(shù)據(jù)集,數(shù)據(jù)質(zhì)量較高基本無(wú)量綱的影響. 使用支持向量機(jī)SVM對(duì)特征選擇后的數(shù)據(jù)進(jìn)行分類,以分類正確率來驗(yàn)證算法的有效性,使用10折交叉驗(yàn)證的結(jié)果作為最終分類正確率.

表1 數(shù)據(jù)集介紹

4.2 參數(shù)的設(shè)置

UFS-IR算法涉及眾多參數(shù),其中影響算法性能的主要包括ReliefF中的抽樣次數(shù)m和DBSCAN中的鄰域半徑eps、樣本閾值minPts. 如2.2節(jié)所述參數(shù)m將影響最終得出的各個(gè)特征的權(quán)值,理論上而言m的值增加,算法將獲得更多數(shù)據(jù)本身的結(jié)構(gòu)信息或統(tǒng)計(jì)信息等,使得特征評(píng)估結(jié)果更準(zhǔn)確. 事實(shí)上也是如此,實(shí)驗(yàn)改變對(duì)satimage數(shù)據(jù)集的抽樣次數(shù)m,當(dāng)m=100時(shí),UFS-IR-Accuracy為 0.895; 當(dāng)m=200時(shí),UFS-IRAccuracy為0.922,當(dāng)m=300時(shí),UFS-IR-Accuracy為0.931. 分類正確率隨m的增加而增加,但同時(shí)運(yùn)行時(shí)間也在增加. 出于實(shí)驗(yàn)?zāi)康氖球?yàn)證UFS-IR對(duì)ReliefF算法如2.2節(jié)所述其他三點(diǎn)的改進(jìn)可行性和有效性,本文對(duì)于參數(shù)m以保障最終分類結(jié)果優(yōu)良,運(yùn)行時(shí)間精煉為原則適當(dāng)選擇.

DBSCAN對(duì)輸入?yún)?shù)(eps,minPts)敏感,若參數(shù)選擇不當(dāng)將造成聚類質(zhì)量下降,并最終影響對(duì)特征評(píng)估的準(zhǔn)確性. DBSCAN參數(shù)的選擇通常依賴于經(jīng)驗(yàn),但當(dāng)數(shù)據(jù)內(nèi)部結(jié)構(gòu)較復(fù)雜時(shí),事先確定合適參數(shù)值是比較困難的. 針對(duì)這種情況,在聚類過程中使用DB INDEX評(píng)價(jià)聚類結(jié)果,并以此為依據(jù)適當(dāng)調(diào)整參數(shù).以satimage數(shù)據(jù)集的測(cè)試集為例,設(shè)置調(diào)整次數(shù)n=10(n是一個(gè)與聚類結(jié)果無(wú)關(guān)的變量,其值可適當(dāng)調(diào)整)分析不同(eps,minPts)參數(shù)值相應(yīng)的DB INDEX值以及最終使用UFS-IR算法的分類正確率,如表2所示DB INDEX對(duì)不同參數(shù)下聚類效果的評(píng)價(jià)值越低,對(duì)特征選擇的影響更積極使得相應(yīng)的分類正確率更高,說明使用DB INDEX方法來確定聚類的參數(shù)是有效準(zhǔn)確的.

表2 DBSCAN聚類評(píng)估情況

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

(1) 驗(yàn)證抽樣策略和ACS有效性

以splice數(shù)據(jù)集為基礎(chǔ),以原始類別信息作為類別標(biāo)簽,對(duì)比分析ReliefF算法和改進(jìn)抽樣策略的ReliefF算法對(duì)各特征的評(píng)估情況如圖1所示.

圖1 ReliefF和改進(jìn)ReliefF對(duì)splice中60個(gè)特征的評(píng)估情況

圖1中,橫坐標(biāo)代表splice的60個(gè)特征,縱坐標(biāo)代表兩個(gè)算法對(duì)每個(gè)特征的評(píng)估值. 從圖1可以看出,改進(jìn)的ReliefF對(duì)特征的評(píng)估各特征間的相對(duì)大小和整體趨勢(shì)與ReliefF的評(píng)估結(jié)果基本一致,因此改進(jìn)ReliefF算法不會(huì)改變特征對(duì)于分類的影響因子. 改進(jìn)抽樣策略的ReliefF對(duì)各特征的評(píng)估值明顯突出于ReliefF的評(píng)估結(jié)果,說明不重復(fù)抽樣充分發(fā)揮了每次抽樣樣本的使用價(jià)值,既定各類樣本的抽樣概率,也使得小類別樣本穩(wěn)定發(fā)揮作用,增加了結(jié)果準(zhǔn)確性和合理性的可靠程度,證明對(duì)ReliefF抽樣策略的改進(jìn)是有效的.

ReliefF家族算法對(duì)所有特征進(jìn)行評(píng)估計(jì)算相應(yīng)的權(quán)重然后以降序排列,選擇排序后特征的相應(yīng)比例作為特征子集. 以splice和satimage數(shù)據(jù)集的原始規(guī)模和類別信息分別訓(xùn)練各自的SVM分類模型model,對(duì)比分析使用ReliefF,改進(jìn)的ReliefF以及改進(jìn)的ReliefF結(jié)合ACS三種方法后,model對(duì)不同維度的數(shù)據(jù)集的分類正確率.

圖2和圖3中縱坐標(biāo)表示特征維度,即ReliefF體系算法對(duì)所有特征排序之后選取前百分之多少構(gòu)成最終特征選擇子集,橫坐標(biāo)表示分類正確率. 可以看出改進(jìn)的ReliefF相比ReliefF算法分類率有所提高,使用ACS刪除冗余特征后,分類率的提高更加明顯.實(shí)驗(yàn)說明改進(jìn)的抽樣策略和ACS的使用是有效的、可靠的.

圖2 Splice數(shù)據(jù)集各維度分類正確率

圖3 Satimage數(shù)據(jù)集各維度分類正確率

(2) 驗(yàn)證UFS-IR的有效性

UFS-IR算法對(duì)原始數(shù)據(jù)集的特征有兩個(gè)刪減過程,第1次是在完成改進(jìn)ReliefF算法之后,刪除特征評(píng)估權(quán)重為負(fù)值的特征,負(fù)值意味著該特征對(duì)于分類具備消極影響. 第2次是使用ACS對(duì)特征間相關(guān)性進(jìn)行衡量,刪減大于閾值λ特征對(duì)中特征評(píng)估權(quán)重較小的特征. 本文設(shè)定的閾值λ為0.75,相關(guān)性系數(shù)不小于0.75表示兩個(gè)特征是顯著相關(guān)關(guān)系. 圖4展示了各數(shù)據(jù)集原始特征維度Original,第1次刪減后特征維度First-cut以及第2次刪減后特征維度Second-cut的情況. 從圖4可以看出,UFS-IR顯著刪減了原始數(shù)據(jù)集中的特征數(shù),使得最終特征子集符合最大相關(guān)最小冗余準(zhǔn)則.

圖4 UFS-IR特征選擇前后維度對(duì)比

以各數(shù)據(jù)集的原始規(guī)模和類別信息分別訓(xùn)練各自的SVM分類模型model,并得到對(duì)原始數(shù)據(jù)集的分類正確率Accuracy. 為驗(yàn)證UFS-IR的有效性,忽略原始數(shù)據(jù)的類別信息作為UFS-IR的實(shí)驗(yàn)數(shù)據(jù)集. DBSCAN聚類迭代n=10次,選擇DB INDEX值較小的一組(eps,minPts)參數(shù)對(duì)數(shù)據(jù)進(jìn)行聚類,并以聚類結(jié)果指定數(shù)據(jù)的類別信息. 用與model相同的參數(shù)對(duì)UFS-IR特征選擇后數(shù)據(jù)集進(jìn)行訓(xùn)練和測(cè)試,得到分類正確率UFS-IR-Accuracy. 如表3所示4個(gè)不同數(shù)據(jù)集的UFSIR- Accuracy值明顯大于Accuracy,實(shí)驗(yàn)證明本文提出的UFS-IR無(wú)監(jiān)督特征選擇方法是合理的、有效的.

表3 特征選擇前后分類正確率

5 結(jié)論與展望

本文首先分析了無(wú)監(jiān)督特征選擇的基礎(chǔ)體系,然后介紹了ReliefF算法并對(duì)其不足進(jìn)行分析,基于此提出改進(jìn)方案. 本文將DBSCAN與改進(jìn)ReliefF加以融合,提出了基于改進(jìn)ReliefF的無(wú)監(jiān)督特征選擇方法UFS-IR,構(gòu)成無(wú)監(jiān)督特征選擇的基本結(jié)構(gòu)體系. 實(shí)驗(yàn)結(jié)果證明,使用DB INDEX準(zhǔn)則判定DBSCAN有效性并確定參數(shù)的方法是有效的,這也使得DBSCAN指導(dǎo)分類更加準(zhǔn)確和可靠,抽樣策略的改進(jìn)使得特征評(píng)估的結(jié)果更加可信和合理,調(diào)整的余弦相似度有效解決了改進(jìn)ReliefF算法無(wú)法辨識(shí)冗余特征的不足,方法間優(yōu)勢(shì)互補(bǔ)更提高了UFS-IR的有效性和可靠性.UFS-IR涉及眾多參數(shù),選擇更快速有效的方法確定DBSCAN的參數(shù),研究改進(jìn)ReliefF中的參數(shù)m對(duì)特征評(píng)估的影響以及參數(shù)m的選擇策略或準(zhǔn)則是今后工作的重點(diǎn).

1Liu H,Yu L. Toward integrating feature selection algorithms for classification and clustering. IEEE Transactions on Knowledge and Data Engineering,2005,17(4)： 491-502.

2Yu L,Liu H. Efficient feature selection via analysis of relevance and redundancy. The Journal of Machine Learning Research,2004,5(12)： 1205-1224.

3姚旭,王曉丹,張玉璽,等. 特征選擇方法綜述. 控制與決策,2012,27(2)： 161-166,192.

4蔡哲元,余建國(guó),李先鵬,等. 基于核空間距離測(cè)度的特征選擇. 模式識(shí)別與人工智能,2010,23(2)： 235-240.

5徐峻嶺,周毓明,陳林,等. 基于互信息的無(wú)監(jiān)督特征選擇.計(jì)算機(jī)研究與發(fā)展,2012,49(2)： 372-382.

6歐璐,于德介. 基于拉普拉斯分值和模糊C均值聚類的滾動(dòng)軸承故障診斷. 中國(guó)機(jī)械工程,2014,25(10)： 1352-1357.[doi： 10.3969/j.issn.1004-132X.2014.10.015]

7Tabakhi S,Moradi P,Akhlaghian F. An unsupervised feature selection algorithm based on ant colony optimization.Engineering Applications of Artificial Intelligence,2014,(32)： 112-123. [doi： 10.1016/j.engappai.2014.03.007]

8Yuan HN,Wang SL,Li Y,et al. Feature selection with data field. Chinese Journal of Electronics,2014,23(4)： 661-665.

9Zhu PF,Zhu WC,Hu QH,et al. Subspace clustering guided unsupervised feature selection. Pattern Recognition,2017,(66)： 364-374. [doi： 10.1016/j.patcog.2017.01.016]

10張麗新,王家廞,趙雁南,等. 基于Relief的組合式特征選擇. 復(fù)旦學(xué)報(bào) (自然科學(xué)版),2004,43(5)： 893-898.

11Kira K,Rendell LA. The feature selection problem：Traditional methods and a new algorithm. Proceedings of 10th National Conference on Artificial Intelligence. San Jose,CA,USA. 1992. 129-134.

12Kononenko I. Estimating attributes： Analysis and extensions of RELIEF. Proceedings of the European Conference on Machine Learning. Catania,Italy. 1994. 171-182.

13Sarwar B,Karypis G,Konstan J,et al. Item-based collaborative filtering recommendation algorithms.Proceedings of the 10th International Conference on World Wide Web. Hong Kong,China. 2001. 285-295.

14Jain AK,Murty MN,Flynn PJ. Data clustering： A review.ACM Computing Surveys,1999,31(3)： 264-323. [doi： 10.1145/331499.331504]

15譚臺(tái)哲,梁應(yīng)毅,劉富春. 一種ReliefF特征估計(jì)方法在無(wú)監(jiān)督流形學(xué)習(xí)中的應(yīng)用. 山東大學(xué)學(xué)報(bào)(工學(xué)版),2010,40(5)： 66-71.

16劉杰,金弟,杜惠君,等. 一種新的混合特征選擇方法RRK.吉林大學(xué)學(xué)報(bào)(工學(xué)版),2009,39(2)： 419-423.