張 玨,田建學(xué)

(榆林學(xué)院 信息工程學(xué)院,陜西 榆林 719000)

當(dāng)將全部特征直接用于構(gòu)建分類器,不但耗時(shí),而且會(huì)降低分類性能。因此,需要引入特征選擇方法,對(duì)原始屬性進(jìn)行裁剪,進(jìn)而依據(jù)分類的要求篩選出最有效特征子集用于構(gòu)建分類器。具體的說,引入特征選擇對(duì)算法性能提升主要表現(xiàn)在以下四個(gè)方面:(1)經(jīng)過特征選擇獲得的數(shù)據(jù)表達(dá),能夠增強(qiáng)學(xué)習(xí)模型在絕大多數(shù)實(shí)際場(chǎng)景中泛化能力;(2)可以有效克服由維數(shù)增加所引發(fā)的“維數(shù)災(zāi)難”和“過擬合”等問題;(3)采用降低維度后的特征構(gòu)建學(xué)習(xí)模型,可以在有效提高算法的分類性能的同時(shí)降低算法的計(jì)算復(fù)雜度;(4)通過特征選擇后獲得的知識(shí)表達(dá)式,可以降低研究人員對(duì)問題理解和解釋的難度。特征選擇方法可以改進(jìn)分類器預(yù)測(cè)性能,提高計(jì)算速度并減少內(nèi)存開銷。

不平衡數(shù)據(jù)是指某一種分類的數(shù)量多余另一種分類的數(shù)量。不平衡分類問題在多個(gè)領(lǐng)域存在,在這些領(lǐng)域中,人們對(duì)少數(shù)類更感興趣,少數(shù)類的樣本也往往更具有價(jià)值。面向不平衡數(shù)據(jù)進(jìn)行特征選擇時(shí),少數(shù)類的存在增大了尋找最優(yōu)特征子集的難度,傳統(tǒng)的以最大分類正確率為準(zhǔn)則的特征選擇算法往往不能選擇出有效的特征子集。Ogura等[1]指出傳統(tǒng)的特征選擇算法對(duì)不平衡數(shù)據(jù)進(jìn)行特征選擇時(shí)的不適應(yīng)性,提出應(yīng)該設(shè)計(jì)是適應(yīng)于不平衡數(shù)據(jù)的特征選擇算法。因此,對(duì)于不平數(shù)據(jù)集分類,特征選擇有時(shí)比分類算法更重要[2, 3]。

拉普拉斯Laplacian是由He和Cai于2006年提出的,算法基于拉普拉斯特征圖[4]和局部保留投影算法[5],算法的基本思想是計(jì)算每個(gè)特征的Laplacian分?jǐn)?shù),通過拉普拉斯分?jǐn)?shù)來反映它的局部保持能力。因?yàn)樵诤芏鄬?shí)際的分類問題中,數(shù)據(jù)的局部空間比全局結(jié)構(gòu)更為重要。然而,在不平衡分類這個(gè)問題背景下,以最大化分類精度為主要目標(biāo)的拉普拉斯特征選擇算法往往效果較差,因?yàn)樗惴ㄆ蛴诙鄶?shù)類而忽略少數(shù)類,傳統(tǒng)的評(píng)估指標(biāo)不能準(zhǔn)確地評(píng)估分類器的性能。

因此,本文在分析傳統(tǒng)特征選擇算法不足的基礎(chǔ)上,針對(duì)二類不平衡分類問題對(duì)拉普拉斯特征選擇算法進(jìn)行改進(jìn),提出基于改進(jìn)的Laplacian特征選擇算法LP(Laplacian)。算法主要包括四個(gè)步驟:(1)根據(jù)拉普拉斯分?jǐn)?shù)對(duì)特征進(jìn)行排序。(2)構(gòu)建若干個(gè)特征子集,由最高拉普拉斯分?jǐn)?shù)的特征組成。(3)通過聚類后的標(biāo)簽和真實(shí)的標(biāo)簽值來計(jì)算每個(gè)特征子集的歸一化值,有著最高歸一化值的特征子集為最優(yōu)特征子集。實(shí)驗(yàn)結(jié)果表明,算法具有一定的競(jìng)爭(zhēng)力。

1 Laplacian特征選擇算法

算法描述:Lr代表第r個(gè)特征的拉普拉斯分?jǐn)?shù)。Fri代表了第i個(gè)樣本的r個(gè)特征,i=1,…,m。

(1)構(gòu)造一個(gè)有m個(gè)結(jié)點(diǎn)的圖G。xi代表第i個(gè)結(jié)點(diǎn),如果xi是xj的K近鄰樣本,或者xj是xi的K近鄰樣本,那么就認(rèn)為xi,xj是近鄰。當(dāng)標(biāo)簽樣本是可得到的,那么就在xi,xj之間放置一條邊,并且共享標(biāo)簽。

2 改進(jìn)的拉普拉斯特征選擇算法

常用的特征選擇算法以分類準(zhǔn)確度為度量標(biāo)準(zhǔn),也取得了不錯(cuò)的效果。在不平衡數(shù)據(jù)的情況下,傳統(tǒng)的特征選擇方法所選擇的特征更加偏向于多數(shù)類,然而實(shí)際生活中,人們往往更關(guān)注少數(shù)類。由于數(shù)據(jù)的不平衡性,傳統(tǒng)的分類評(píng)估指標(biāo)并不能準(zhǔn)確評(píng)估分類器的性能。為此研究者引入新的分類評(píng)價(jià)指標(biāo)馬修斯相關(guān)系數(shù)(Matthews correlation coefficient, MCC)。

馬修斯相關(guān)系數(shù)考慮到真和假陽性和假陰性,通常被視為一種平衡的措施,即時(shí)數(shù)據(jù)的規(guī)模大小不同也可以使用。MCC本質(zhì)上是觀察到的和預(yù)測(cè)的二元分類之間的相關(guān)系統(tǒng),值介于-1和+1之間,+1表示完美預(yù)測(cè),-1表示預(yù)測(cè)和觀察之間的完全不一致。馬修斯相關(guān)系數(shù)的定義為:

公式中,TP代表真陽性,TN代表真陰性,FP代表假陽,FN代表假陰。當(dāng)FP=FN=0也就是預(yù)測(cè)完全正確時(shí)MCC=1,當(dāng)完全預(yù)測(cè)錯(cuò)誤時(shí)MCC=-1,當(dāng)MCC=0時(shí)表明模型和隨機(jī)預(yù)測(cè)性能類似。

傳統(tǒng)的以最大化分類準(zhǔn)確度為目標(biāo)的特征選擇研究中,以拉普拉斯為代表的算法表明能明顯的改善算法的性能。受此啟發(fā),本文提出一種改進(jìn)的以最大化MCC為目標(biāo)的拉普拉斯特征選擇算法。改進(jìn)的拉普拉斯特征選擇算法,選擇使用MCC評(píng)價(jià)指標(biāo)來衡量算法性能,從而提高不平衡數(shù)據(jù)的分類性能。具體的說,算法在構(gòu)建最近鄰圖的時(shí)候,使用MCC評(píng)價(jià)指標(biāo)來尋找近鄰參數(shù)k值,在原始的應(yīng)用中,k值取常數(shù),但是常數(shù)不能提供令人滿意的性能,而且k的值對(duì)于圖構(gòu)建也非常敏感。以MCC為評(píng)價(jià)指標(biāo)計(jì)算每個(gè)特征的Laplacian分?jǐn)?shù),接下來構(gòu)建特征子集,第一個(gè)特征子集由有著最高Laplacian分?jǐn)?shù)的一個(gè)特征構(gòu)成,第二個(gè)特征子集由有著最高Laplacian分?jǐn)?shù)的前兩個(gè)特征構(gòu)成,第n個(gè)特征子集由有著最高Laplacian分?jǐn)?shù)的前n個(gè)特征構(gòu)成。最后計(jì)算每個(gè)特征子集的歸一化值,有著最優(yōu)歸一化值的特征子集為最優(yōu)特征子集。

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

為了驗(yàn)證本文所提出算法的性能,在公開的不平衡數(shù)據(jù)集WDBC上進(jìn)行測(cè)試,這個(gè)數(shù)據(jù)集來自于UCI數(shù)據(jù)庫乳腺癌標(biāo)準(zhǔn)數(shù)據(jù)集,威斯康星大學(xué)醫(yī)院麥迪遜分校,由Mangasarian等人收集。表1列出了這個(gè)數(shù)據(jù)集的詳細(xì)信息。對(duì)于數(shù)據(jù)集,采用保持方法使用80%的樣本進(jìn)行訓(xùn)練,20%的樣本進(jìn)行測(cè)試。算法使用Matlab 2016a 和R3.5.1平臺(tái)上進(jìn)行對(duì)比驗(yàn)證。仿真實(shí)驗(yàn)在Intel(R) Core (TM) I5-8400 CPU, 8GB內(nèi)存,2.80GHz CPU和windows 64位操作系統(tǒng)的個(gè)人電腦上運(yùn)行。實(shí)驗(yàn)中采用有著線性核函數(shù)的SVM作為分類器,來驗(yàn)證特征選擇的效果。SVM算法使用R中的“kernlab”包來實(shí)現(xiàn),其它參數(shù)采用默認(rèn)設(shè)計(jì)。

圖1 WDBC數(shù)據(jù)集上每個(gè)特征對(duì)應(yīng)的LS分?jǐn)?shù)

表1 實(shí)驗(yàn)數(shù)據(jù)集

為了評(píng)估本文提出的LP-SVM算法的有效性,將LP-SVM的結(jié)果與局部投影算法(Locality Preserving Projection, LPP)和SVM分類組成LPP-SVM進(jìn)行比較。LP-SVM與LPP-SVM算法對(duì)比,為了說明拉普拉斯特征選擇算法的有效性。為了進(jìn)一步評(píng)估算法的有效性,表2顯示了本文提出的LP-SVM算法在WDBC上的結(jié)果以及各種不同文獻(xiàn)方法的對(duì)比。Accuracy分類準(zhǔn)確度、Sensitivity靈敏度和MCC用作性能指標(biāo)進(jìn)行比較。表中的符號(hào)“～”代表對(duì)應(yīng)的文獻(xiàn)中沒有相關(guān)數(shù)據(jù)。

根據(jù)表2所示,本文提出的LP-SVM取得了97.48%的精度、100%的敏感度、96.17%的特異性、94.8%的MCC值。通過分類精度可以看到,LP-SVM算法優(yōu)于大部分的算法,同時(shí)本文的算法優(yōu)于LPP-SVM。本文算法優(yōu)于LPP-SVM,說明改進(jìn)的LP特征選擇算法優(yōu)于經(jīng)典的局部投影算法LPP。雖然部分文獻(xiàn)的方法略微優(yōu)于本文算法,但是本文提出的LP-SVM算法有著和文獻(xiàn)類似的性能,和文獻(xiàn)方法沒有顯著差異。綜合分析,本文算法有著和經(jīng)典算法LPP-SVM以及其它流行算法類似甚至更好的預(yù)測(cè)能力。

4 結(jié)論

在不平衡分類這個(gè)問題背景下,傳統(tǒng)的以最大化分類精度為主要目標(biāo)的特征選擇算法往往效果較差。基于此本文提出一種基于改進(jìn)LP拉普拉斯特征選擇算法,用MCC取代精度來衡量特征子集的分類性能。實(shí)驗(yàn)結(jié)果表明,LP-SVM算法具有一定的競(jìng)爭(zhēng)力。該算法也存在一些不足,比如算法效率低、參數(shù)設(shè)定困難等。因此,如何改進(jìn)算法效率以及對(duì)特征選擇算法中某些參數(shù)設(shè)置問題,摒棄經(jīng)驗(yàn)值,引入算法實(shí)現(xiàn)對(duì)參數(shù)的自動(dòng)尋優(yōu),是將來重要的研究方向。