基于樣本鄰域保持的代價(jià)敏感特征選擇*

余勝龍　趙　紅

(閩南師范大學(xué)粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室,漳州,363000)

引　　言

在當(dāng)前的數(shù)據(jù)時(shí)代，無論在數(shù)量還是在維度上，數(shù)據(jù)的產(chǎn)生都是多種多樣的，而且數(shù)據(jù)也越來越大。如在醫(yī)學(xué)、天文和文本等領(lǐng)域，高維數(shù)據(jù)給數(shù)據(jù)分析帶來了諸多挑戰(zhàn)。因此，數(shù)據(jù)降維[1]成為機(jī)器學(xué)習(xí)中一個(gè)必不可少的過程，而特征選擇是主要的降維技術(shù)之一。特征選擇是通過選取能表示所有特征的一個(gè)較小的特征子集。從數(shù)據(jù)是否帶有標(biāo)簽來看，特征選擇可以分為有監(jiān)督和無監(jiān)督兩種。有監(jiān)督的特征選擇是利用標(biāo)簽信息評(píng)價(jià)特征的重要度來進(jìn)行選擇，運(yùn)用比較廣泛的有監(jiān)督特征選擇算法有Fisher Score[2]，Relief和ReliefF[3]。無監(jiān)督的特征選擇算法[4]是根據(jù)自己數(shù)據(jù)特征的關(guān)系來進(jìn)行特征選擇。

一部分有監(jiān)督特征選擇算法以追求高精度為目的，卻忽略了誤分類代價(jià)或默認(rèn)誤分類代價(jià)相同。然而，在現(xiàn)實(shí)應(yīng)用中，不同的誤分類通常會(huì)導(dǎo)致不同的誤分類代價(jià)。例如，在交易過程中存在兩種類型的誤分類。類型Ⅰ定義為將正常交易誤分為欺騙交易；類型Ⅱ定義為將欺騙交易誤分為正常交易。類型Ⅰ的錯(cuò)誤代價(jià)是工作人員重新審查交易；類型Ⅱ的錯(cuò)誤代價(jià)是造成了巨大的金錢損失。顯然，類型Ⅰ導(dǎo)致的錯(cuò)誤代價(jià)要小于類型Ⅱ?qū)е碌腻e(cuò)誤代價(jià)。另一部分有監(jiān)督特征選擇算法以選擇有益的特征為目標(biāo)，假設(shè)不同類別的樣本具有相等的權(quán)重，這種認(rèn)為數(shù)據(jù)本身有均衡樣本類別的想法會(huì)導(dǎo)致在數(shù)據(jù)具有不均衡的樣本類別時(shí)，有監(jiān)督特征選擇算法的效果大打折扣。因此在現(xiàn)實(shí)應(yīng)用中必須考慮數(shù)據(jù)類別不均衡問題。

20世紀(jì)90年代，代價(jià)信息被考慮到算法中，因而提出了代價(jià)敏感學(xué)習(xí)，它是機(jī)器學(xué)習(xí)領(lǐng)域十大研究熱點(diǎn)之一[5]。至今，眾多研究人員提出了許多代價(jià)敏感學(xué)習(xí)算法[6-8]來解決代價(jià)敏感問題和類不均衡問題，并在不同研究領(lǐng)域證實(shí)了算法的有效性[9-11]?，F(xiàn)實(shí)應(yīng)用中的代價(jià)主要分為兩類：誤分類代價(jià)和測(cè)試代價(jià)。其中，誤分類代價(jià)可分為：基于樣本的誤分類代價(jià)[12]和基于類別的誤分類代價(jià)[13]。本文的算法主要是在基于類別的誤分類代價(jià)基礎(chǔ)上再引入鄰域?qū)崿F(xiàn)的[14-16]。

鄰域在特征選擇中有著廣泛的應(yīng)用。文獻(xiàn)[17]提出一種基于鄰域粗糙集的測(cè)試代價(jià)屬性約簡，但其代價(jià)設(shè)置未考慮與鄰域大小的關(guān)系。本文利用鄰域可以保持樣本局部結(jié)構(gòu)的性質(zhì)，同時(shí)引入代價(jià)敏感，提出一種新的基于樣本鄰域保持的代價(jià)敏感特征選擇算法(Cost sensitive feature selection based on sample neighborhood preserving,CSFN-SNP)。首先，根據(jù)鄰域保持局部結(jié)構(gòu)的性質(zhì)得出鄰域矩陣[18]；其次，引入代價(jià)矩陣和樣本重要度，在鄰域矩陣上計(jì)算每個(gè)特征的分?jǐn)?shù)，并對(duì)每個(gè)特征分?jǐn)?shù)使用排序算法進(jìn)行排序，從而返回特征排序。實(shí)驗(yàn)結(jié)果表明，提出的代價(jià)敏感特征選擇算法具有很好的性能。

1　相關(guān)工作

在現(xiàn)實(shí)應(yīng)用中，不同的誤分類通常會(huì)導(dǎo)致不同的誤分類代價(jià)?，F(xiàn)假設(shè)有c類數(shù)據(jù)樣本，并且，假設(shè)將第i類(i∈{1,2,…,c-1})數(shù)據(jù)樣本誤分類為第c類數(shù)據(jù)樣本造成的代價(jià)要高于將第c類數(shù)據(jù)樣本誤分類為第i類數(shù)據(jù)樣本的代價(jià)。基于該假設(shè)，將第1類到第c-1類設(shè)為“組內(nèi)”類，將第c類設(shè)為“組外”類。根據(jù)文獻(xiàn)[9]，這樣的誤分類代價(jià)可分為3類:

(1) 誤識(shí)別代價(jià)CII：將“組內(nèi)”類中某一類的數(shù)據(jù)樣本誤分類為“組內(nèi)”類中另一類數(shù)據(jù)樣本產(chǎn)生的代價(jià)；

表1　代價(jià)矩陣

(2) 誤接受代價(jià)COI：將“組外”類數(shù)據(jù)樣本誤分類“組內(nèi)”類數(shù)據(jù)樣本所產(chǎn)生的代價(jià);

(3) 誤拒絕代價(jià)CIO：將“組內(nèi)”類數(shù)據(jù)樣本誤分類“組外”類數(shù)據(jù)樣本所產(chǎn)生的代價(jià)。

由常識(shí)可知，代價(jià)CIO，CII和COI的值一般不相等。令Cost(i,j)(i,j∈{1,2,…,c})為將第i類樣本誤分為第j類樣本的代價(jià)，可以構(gòu)建如表1所示的代價(jià)矩陣C。正確預(yù)測(cè)則沒有代價(jià)，即對(duì)角元素全是0。但在現(xiàn)實(shí)應(yīng)用中，代價(jià)矩陣通常由用戶或該領(lǐng)域的專家給出。根據(jù)代價(jià)矩陣，定義函數(shù)f(α)來衡量第α(1≤α≤c)類樣本的重要度，即

(1)

2　基于鄰域的代價(jià)敏感特征選擇

本節(jié)提出了一種基于樣本鄰域保持的代價(jià)敏感特征選擇算法CSFN-SNP，該算法是在代價(jià)敏感信息的基礎(chǔ)上引入鄰域，使得每個(gè)樣本的鄰域內(nèi)存在k個(gè)節(jié)點(diǎn)的鄰接矩陣，并且每個(gè)樣本的每個(gè)特征都在其自己的鄰域上討論，保持了樣本的局部結(jié)構(gòu)，可以得到較優(yōu)的特征子集。

首先對(duì)數(shù)據(jù)集進(jìn)行正規(guī)化處理，其次構(gòu)造鄰域矩陣G={G1,G2,…,Gn}，其中Gi表示第i個(gè)樣本。構(gòu)造鄰域矩陣G有兩種方法：(1)K近鄰(Knearest neighbor,KNN): 如果xi和xj是K近鄰。(2)ε近鄰(εneighborhood):如果第i個(gè)樣本和第j個(gè)樣本之間滿足‖xi-xj‖≤ε。

在實(shí)際應(yīng)用中，第2種方法很少用，因?yàn)楹茈y找到一個(gè)好的ε。本文使用第1種方法KNN來構(gòu)造鄰域矩陣G。在此基礎(chǔ)上再引入代價(jià)，第r個(gè)特征的CSFN得分Cr(Cr越小越好)，即有

(2)

(3)

Cr=Sr-Hr

(4)

式中:定義M={(xi,xj)|xi,xj屬于同一類別}，C={(xi,xj)|xi,xj屬于不同類別}；λ為一權(quán)重參數(shù)，用以調(diào)節(jié)樣本誤分類代價(jià)矩陣的權(quán)重。

本文提出的CSFN-SNP算法的時(shí)間復(fù)雜度為O(nm2+nc)，其算法步驟表述如下。

算法1基于樣本鄰域保持的代價(jià)敏感特征選擇

輸入：數(shù)據(jù)集Xn×m，標(biāo)簽Y=[y1,y2, …,yn]，參數(shù)k和λ

(1) 計(jì)算每個(gè)樣本之間的相互距離，根據(jù)鄰域的性質(zhì)，找到每個(gè)樣本的k近鄰(包括樣本自己)，得到每個(gè)樣本的鄰域矩陣Gi(1≤i≤n)；

(2) 根據(jù)表1和式(1)分別得出代價(jià)矩陣C和樣本重要度f(α)；

(3) 在每個(gè)鄰域矩陣Gi的基礎(chǔ)上，根據(jù)式(4)逐一計(jì)算出每個(gè)特征的得分Cr(1≤r≤m)；

(4) 對(duì)得到的Cr進(jìn)行排序，并返回特征排序，選取前d個(gè)特征。

3　算法性能對(duì)比實(shí)驗(yàn)

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

為了驗(yàn)證本文算法的有效性，將其和現(xiàn)有的代價(jià)敏感特征選擇算法在UCI數(shù)據(jù)集上做了相關(guān)的對(duì)比實(shí)驗(yàn)。這8個(gè)UCI數(shù)據(jù)集分別是Heart，Australian，German，Wpbc，Vehicle，Glass，Landsat和Segment。為了準(zhǔn)確反映CSFN算法在類不均衡情況下的性能，Vehicle，Glass，Landsat和Segment數(shù)據(jù)集的類別數(shù)是不均衡的。表2給出了數(shù)據(jù)集的詳細(xì)信息。所有實(shí)驗(yàn)均在MATLAB平臺(tái)上實(shí)現(xiàn)。選取的現(xiàn)有代價(jià)敏感特征選擇算法包括

(1) Baseline:選擇所有的特征。

(2) 基于最大方差的代價(jià)敏感特征選擇算法(Cost-sensitive variance score,CSVS)[19]:目標(biāo)是找到組內(nèi)樣本距離樣本中心盡可能比組外樣本距離樣本距離中心近的特征。

(3) 基于約束保持的代價(jià)敏感特征選擇算法(Cost-sensitive constraint score,CSCS)[19]:利用同一類別樣本間距小于不同類別樣本間距的特征進(jìn)行逐一打分。

表2　數(shù)據(jù)集信息

對(duì)于算法CSFN-SNP和CSCS，用網(wǎng)絡(luò)搜索策略來調(diào)節(jié)參數(shù)λ，設(shè)定參數(shù)集合為{1 000，100，10，1，0.1，0.01，0.001}。CSFN-SNP算法的近鄰參數(shù)k設(shè)置為5。設(shè)置CII，COI和CIO的值分別為1，2和20。對(duì)選擇的特征子集使用1-NN來分類，同時(shí)將得到的誤分類代價(jià)和分類精度作為參考指標(biāo)。實(shí)驗(yàn)結(jié)果為5次5折交叉驗(yàn)證結(jié)果的平均值。結(jié)合特征選擇數(shù)和參數(shù)，將每個(gè)算法的最佳實(shí)驗(yàn)結(jié)果分別在表3和表4中列出，表3列出了最小誤分類代價(jià)和所對(duì)應(yīng)的特征數(shù)，表4列出了分類精度，并且在表3和表4中最佳結(jié)果使用粗體來標(biāo)出，次好的結(jié)果用下劃線標(biāo)出，代價(jià)旁邊括號(hào)內(nèi)表示對(duì)應(yīng)最小代價(jià)的特征數(shù)。圖1顯示了4種算法在8個(gè)數(shù)據(jù)集上隨特征數(shù)變化而得到的誤分類代價(jià)的對(duì)比結(jié)果。

表3　不同特征選擇算法的誤分類代價(jià)

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

Tab.4　Accuracy of different feature selection algorithms

%

圖1　4種算法在8個(gè)數(shù)據(jù)集上的誤分差代價(jià)對(duì)比Fig.1　Misclassification cost contrast for four algorithoms on eight datasets

3.2　結(jié)果分析

從表3可以看出，算法CSCS和CSVS在特征選擇時(shí)，有較小的誤分類代價(jià)和與之對(duì)應(yīng)的特征數(shù)。而本文提出的CSFN-SNP算法使得每個(gè)樣本保持局部的結(jié)構(gòu)，可以比CSCS和CSVS算法在8個(gè)數(shù)據(jù)集上獲得更小的誤分類代價(jià)，且CSFN-SNP算法在獲得最小誤分類代價(jià)時(shí)所需要的特征數(shù)大部分小于CSCS和CSVS算法在達(dá)到最優(yōu)性能時(shí)所需的特征個(gè)數(shù)。結(jié)合表3和表4，可以得出誤分類代價(jià)和分類精度有些關(guān)聯(lián)，但并不是誤分類代價(jià)越小，分類精度就會(huì)越高。說明本文的算法是使誤分類代價(jià)盡可能小的情況下而得出盡可能高的分類精度，也說明了誤分類代價(jià)是更重要的評(píng)價(jià)指標(biāo)。從表3和圖1可以得出，CSFN-SNP與對(duì)比算法能較快地選出誤分類代價(jià)最低時(shí)的特征數(shù)。

4　結(jié)束語

在現(xiàn)實(shí)世界中誤分類代價(jià)一般是不相同的。本文在考慮到誤分類代價(jià)的同時(shí)引入鄰域，并且通過鄰域保持局部幾何結(jié)構(gòu)的性質(zhì)，提出了基于樣本鄰域保持的代價(jià)敏感特征選擇算法CSFN-SNP，引入的鄰域矩陣在降維時(shí)既能用來保持原始數(shù)據(jù)的局部幾何結(jié)構(gòu)，又能充分利用其類別信息。為了驗(yàn)證該算法的有效性，將其與已有的代價(jià)敏感特征選擇算法與CSCS，CSVS和Baseline作對(duì)比，實(shí)驗(yàn)結(jié)果表明CSFN-SNP具有更優(yōu)的性能。下一步工作將同時(shí)考慮測(cè)試代價(jià)和誤分類代價(jià)，以建立更好的模型應(yīng)用于實(shí)際生活中。

參考文獻(xiàn):

[1]Liu H,Motoda H. Feature selection for knowledge discovery and data mining[M]. Netherlands:Springer Science & Business Media,2012.

[2]Duda R O,Hart P E,Stork D G. Pattern classification[M].New Jersey:John Wiley & Sons,2012:117-120.

[3]Robnik-Sikonja M,Kononenko I. Theoretical and empirical analysis of Relief and ReliefF[J]. Machine Learning,2003,53(1/2): 23-69.

[4]Mitra P,Murthy C A,Pal S K. Unsupervised feature selection using feature similarity[J]. Pattern Analysis and Machine Intelligence,IEEE Transactions on,2002,24(3): 301-312.

[5]Saitta L,Geibel P. Machine learning: A technological roadmap[M]. Netherlands:Department of Social Science Informatics,University of Amsterdam,2001.

[6]Chawla N V,Bowyer K W,Hall L O,et al. SMOTE: Synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research,2002,16: 321-357.

[7]Kubat M,Matwin S. Addressing the curse of imbalanced training sets: One-sided selection[C]∥Proceedings of the Fourteenth International Conference on Machine Learning. Nashville, Tennessee, USA:Morgan Kaufmann,1997:253-259.

[8]Ting K M. An empirical study of MetaCost using boosting algorithms[J]. Lecture Notes in Computer Science,2000,1810:413-425.

[9]Zhang Y,Zhou Z H. Cost-sensitive face recognition[J]. Pattern Analysis and Machine Intelligence,IEEE Transactions on,2010,32(10): 1758-1769.

[10] Zhou Zhihua,Liu Xuying. On multi-class cost-sensitive learning[J]. Computational Intelligence,2010,26(3): 232-257.

[11] Liu Xuying,Zhou Zhihua. Learning with cost intervals[C]∥ Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington:ACM,2010:403-412.

[12] Zadrozny B,Elkan C. Learning and making decisions when costs and probabilities are both unknown[C]∥ Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. America San Francisco:ACM, 2001:204-213.

[13] Domingos P. MetaCost: A general method for making classifiers cost-sensitive[C]∥Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego:ACM,1999:155-164.

[14] Wang Fei,Zhang Changshui. Label propagation through linear neighborhoods[J]. Knowledge and Data Engineering,IEEE Transactions on,2008,20(1): 55-67.

[15] 徐久成,李濤,孫林,等. 基于信噪比與鄰域粗糙集的特征基因選擇方法[J]. 數(shù)據(jù)采集與處理,2015,30(5): 973-981.

Xu Jiucheng,Li Tao,Sun Lin,et al. Feature gene selection based on SNR and neighborhood rough set[J]. Journal of Data Acquisition and Processing,2015,30(5): 973-981.

[16] 葉鑫晶,李潔,王穎,等. 基于邊緣鄰域的乳腺腫塊特征提取算法[J]. 數(shù)據(jù)采集與處理,2015,30(5): 993-1002.

Ye Xinjing,Li Jie,Wang Ying,et al. Mammographic mass feature extraction algorithm based on edge of neighborhood[J]. Journal of Data Acquisition and Processing,2015,30(5): 993-1002.

[17] Zhao Hong,Min Fan,Zhu William. Test-cost-sensitive attribute reduction based on neighborhood rough set[C]∥ Granular Computing (GrC),2011 IEEE International Conference on. Tsukuba, Japan:IEEE,2011: 802-806.

[18] Yang Yi,Xu Dong,Nie Feiping,et al. Image clustering using local discriminant models and global integration[J]. Image Processing,IEEE Transactions on,2010,19(10): 2761-2773.

[19] Miao Linsong,Liu Mingxia,Zhang Daoqiang. Cost-sensitive feature selection with application in software defect prediction[C]∥ Pattern Recognition (ICPR),2012 21st International Conference on. Kaohsiung, China:IEEE,2012: 967-970.