余勝龍　趙　紅

(閩南師范大學(xué)粒計算及其應(yīng)用重點實驗室,漳州,363000)

引　　言

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

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

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

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

1　相關(guān)工作

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

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

表1　代價矩陣

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

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

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

(1)

2　基于鄰域的代價敏感特征選擇

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

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

在實際應(yīng)用中，第2種方法很少用，因為很難找到一個好的ε。本文使用第1種方法KNN來構(gòu)造鄰域矩陣G。在此基礎(chǔ)上再引入代價，第r個特征的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é)樣本誤分類代價矩陣的權(quán)重。

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

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

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

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

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

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

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

3　算法性能對比實驗

3.1實驗設(shè)置

為了驗證本文算法的有效性，將其和現(xiàn)有的代價敏感特征選擇算法在UCI數(shù)據(jù)集上做了相關(guān)的對比實驗。這8個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ì)信息。所有實驗均在MATLAB平臺上實現(xiàn)。選取的現(xiàn)有代價敏感特征選擇算法包括

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

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

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

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

對于算法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。對選擇的特征子集使用1-NN來分類，同時將得到的誤分類代價和分類精度作為參考指標(biāo)。實驗結(jié)果為5次5折交叉驗證結(jié)果的平均值。結(jié)合特征選擇數(shù)和參數(shù)，將每個算法的最佳實驗結(jié)果分別在表3和表4中列出，表3列出了最小誤分類代價和所對應(yīng)的特征數(shù)，表4列出了分類精度，并且在表3和表4中最佳結(jié)果使用粗體來標(biāo)出，次好的結(jié)果用下劃線標(biāo)出，代價旁邊括號內(nèi)表示對應(yīng)最小代價的特征數(shù)。圖1顯示了4種算法在8個數(shù)據(jù)集上隨特征數(shù)變化而得到的誤分類代價的對比結(jié)果。

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

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

Tab.4　Accuracy of different feature selection algorithms

%

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

3.2　結(jié)果分析

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

4　結(jié)束語

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

參考文獻:

[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.