利用一致性分析的高維類別不平衡數(shù)據(jù)特征選擇

曾海亮，林耀進(jìn)，王晨曦，陳祥焰

(閩南師范大學(xué) 計(jì)算機(jī)學(xué)院，福建 漳州 363000) (數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，福建 漳州 363000)

E-mail：zzlinyaojin@163.com

1 引 言

在文本分類[1]、圖像識(shí)別[2]、醫(yī)學(xué)診斷[3]等研究領(lǐng)域，數(shù)據(jù)呈現(xiàn)出高維小樣本特點(diǎn)，即特征空間顯示高維性，而樣本數(shù)量過少.此外，該類數(shù)據(jù)通常伴隨著類別不平衡問題，如某一類的樣本數(shù)量遠(yuǎn)大于另一類的樣本數(shù)量，易引發(fā)分類學(xué)習(xí)過程中大類樣本覆蓋小類樣本現(xiàn)象，而實(shí)際中小類樣本往往是關(guān)鍵的樣本[4].例如，信用記錄欺詐用戶的數(shù)量明顯低于正常用戶；常規(guī)體檢中重疾患者占極小比例.因此，如何提高高維類別不平衡數(shù)據(jù)中小類樣本的分類學(xué)習(xí)精度具有重要意義.

眾所周知，在高維類別不平衡數(shù)據(jù)分類建模任務(wù)中存在著小類樣本難以正確分類問題.為了提高小類樣本的預(yù)測(cè)精度，研究人員提出了眾多的類不平衡特征選擇算法[5-8].文獻(xiàn)[5]通過組合預(yù)先分別選擇的正特征和負(fù)特征，以期改善文本分類中類不平衡數(shù)據(jù)的分類性能.文獻(xiàn)[6]使用五種微陣列表達(dá)數(shù)據(jù)集對(duì)九種過濾技術(shù)進(jìn)行了系統(tǒng)比較與分析，研究了抽樣技術(shù)在特征選擇中的應(yīng)用，發(fā)現(xiàn)特征選擇有利于處理類不平衡數(shù)據(jù).文獻(xiàn)[7]通過重構(gòu)鄰域粗糙集下近似算子，提出了基于特征和標(biāo)記之間依賴關(guān)系的在線特征選擇框架，旨在處理流特征環(huán)境下的類不平衡問題.文獻(xiàn)[8]運(yùn)用了基于小類依賴度的在線流式特征選擇模型，并改進(jìn)了鄰域粗糙集的依賴度計(jì)算公式.

在高維類別不平衡數(shù)據(jù)多分類學(xué)習(xí)任務(wù)中，若數(shù)據(jù)中類別分布傾斜得十分明顯時(shí)，特征選擇技術(shù)可以將所有樣本都分到大類從而獲得很高的分類精度.然而，卻忽略了至關(guān)重要的小類樣本，失去了實(shí)際意義.另外，有些特征選擇方法[9]將數(shù)據(jù)集某一類設(shè)置成小類樣本，其余類別樣本設(shè)置成大類樣本，這種人為設(shè)置大小類具有一定主觀性，很難體現(xiàn)數(shù)據(jù)的多樣性與復(fù)雜性.

從認(rèn)知角度出發(fā)，樣本在論域空間的分布隨特征的變化而變化，具有高可分離性的特征應(yīng)使樣本類內(nèi)分散度盡量小，類間分散度盡量大.基于此，選擇好的特征能顯著提高高維類別不平衡數(shù)據(jù)的分類性能.基于最近鄰思想，相同特征空間下越相近的樣本其類別往往比較一致.于是，本文通過定義樣本一致性概念來構(gòu)建高維類別不平衡數(shù)據(jù)特征選擇模型.首先，通過樣本在特征與類別標(biāo)記的信息定義樣本的近鄰，并設(shè)計(jì)面向高維類別不平衡數(shù)據(jù)的一致性分析模型；其次，根據(jù)特征重要度公式構(gòu)造前向貪婪搜索算法進(jìn)行特征選擇；最后，通過實(shí)驗(yàn)表明該模型的有效性.

綜上，本文內(nèi)容安排如下：第二節(jié)設(shè)計(jì)利用一致性分析的高維類別不平衡數(shù)據(jù)特征選擇的模型與算法；第三節(jié)對(duì)所提算法進(jìn)行實(shí)驗(yàn)驗(yàn)證與結(jié)果分析；第四節(jié)總結(jié)全文.

2 利用一致性分析的高維類別不平衡數(shù)據(jù)特征選擇

在實(shí)際應(yīng)用場(chǎng)景中，數(shù)據(jù)的樣本類別呈現(xiàn)多類及類別比例差異大等特點(diǎn)，而且小類樣本在眾多樣本中占據(jù)著舉足輕重的地位.為此，本文通過定義樣本的一致性來進(jìn)行高維類別不平衡數(shù)據(jù)的特征選擇.首先，基于特征空間的樣本距離來定義目標(biāo)樣本的近鄰，并根據(jù)目標(biāo)樣本所在類別的數(shù)量來定義近鄰的大?。黄浯?，定義目標(biāo)樣本近鄰空間內(nèi)類別一致的近鄰與論域中所有同類樣本的比例稱為包含度，包含度反應(yīng)特征對(duì)樣本的區(qū)分與類別空間對(duì)樣本區(qū)分的一致性，而且能有效地避免小類樣本被大類樣本覆蓋的情況.基于該一致性，可以定義特征對(duì)類別標(biāo)記的重要度，并設(shè)計(jì)相關(guān)的前向貪婪搜索算法.

表1 高維類別不平衡數(shù)據(jù)示例表Table 1 Example of high-dimensional class-imbalanced data

定義1.給定論域空間內(nèi)決策系統(tǒng)，U={x1，x2，…，xn}，標(biāo)記L將U劃分為N個(gè)類別：L={X1，X2，…，XN}.?S?F，對(duì)于?Xj?L，nj是第j類樣本的數(shù)量，?xi∈Xj，定義xi在S下的κ-近鄰為

κS(xi)={x|x∈Minnj{ΔS(x，xi)}，x∈U}

(1)

其中，ΔS(x，xi)表示樣本xi與任意樣本的距離，Minnj{ΔS(x，xi)}表示與樣本xi距離最近的前nj個(gè)樣本的集合，如圖1所示.

例1.由表1所示，給定特征f1，樣本x1，因x1∈X1，有n1=|X1|=3，則Min3{Δf1(x，x1)}={x1，x3，x5}，所以目標(biāo)樣本x1的近鄰空間為κf1(x1)={x1，x3，x5}.

圖1 實(shí)數(shù)空間中樣本的近鄰關(guān)系Fig.1 Near neighbor relationship of sample in real spaces

定義2.給定論域空間內(nèi)決策系統(tǒng)，U={x1，x2，…，xn}，標(biāo)記L將U劃分為N個(gè)類別：L={X1，X2，…，XN}.?S?F，對(duì)于?Xj?L，nj是第j類樣本的數(shù)量，?xi∈Xj，定義包含度函數(shù)為：

(2)

其中，κS(xi)表示樣本xi在特征子集S條件下的近鄰，Xj表示第j類樣本的集合，I(κS(xi),Xj)表示樣本xi的包含度.表明樣本xi由特征子集S誘導(dǎo)出的近鄰空間與類別誘導(dǎo)出的類別空間的包含程度.

例2.由表1所示，給定特征f1，樣本x1，因x1∈X1，有n1=|X1|=3，則x1的近鄰空間κf1(x1)={x1，x3，x5}，而κf1(x1)∩X1={x1，x3}，故I(κf1(x1)，X1)=2/3.

定義3.給定論域空間內(nèi)的決策系統(tǒng)，對(duì)?S?F，定義特征子集S與標(biāo)記L的一致性函數(shù)為:

(3)

定義4.給定論域空間內(nèi)的決策系統(tǒng)，S?F，?f∈F-S在特征子集S條件下，特征f的重要度為:

sig(f，S，L)=CONS∪f(L)-CONS(L)

(4)

標(biāo)記對(duì)特征的包含度函數(shù)定義了特征對(duì)分類的貢獻(xiàn)，因此，可以作為特征集合重要性的評(píng)價(jià)指標(biāo).

根據(jù)定義4的特征重要度函數(shù)利用前向貪婪搜索算法依次對(duì)特征空間迭代直至終止條件得到的特征選擇結(jié)果即為最終選擇的特征.因此，本文將基于一致性函數(shù)，構(gòu)造一種前向貪婪搜索特征選擇算法.該算法以空集為起點(diǎn)，每次計(jì)算全部剩余特征的特征重要度，從中選擇特征重要度值最大的特征加入特征選擇集合中，直到所有剩余特征的重要度為0，即加入任何新的特征，系統(tǒng)的一致性函數(shù)值不再發(fā)生變化為止.

根據(jù)以上分析，利用一致性分析的高維類別不平衡數(shù)據(jù)特征選擇算法具體描述如算法1所示.

算法1.利用一致性分析的高維類別不平衡數(shù)據(jù)特征選擇(Feature Selection of High-dimensional class-imbalanced data using Consistency analysis，簡(jiǎn)稱FSHC)

輸入：

輸出：約簡(jiǎn)后red

1. ?→red

2. ?f∈F-red/*計(jì)算樣本距離關(guān)系矩陣Nred和Nred∪f，若Nred=?，則不計(jì)算*/

3. fori=1，2，…，ndo/*n為總樣本數(shù)，即|U|=n*/

4.xi∈Xj，nj=|Xj|

5.κ(xi)=(x|x∈Minnj{Δ(x，xi)}，x∈U}

6.I(κ(xi)，Xj)=|κ(xi)∩Xj|/|κ(xi)|

7. end for

9. 計(jì)算sig(f，red，L)=CONred∪f(L)-CONred(L)

10. 選擇f′滿足sig(f′，red，L)=maxsig(f，red，L)

11. ifsig(f′，red，L)> 0 then

12.red∪f′→red

13. go to step 2

14. else

15. returnred

16. end if

算法1中第3-8步計(jì)算特征與標(biāo)記的一致性值，第9-12步利用前向貪婪搜索策略對(duì)特征進(jìn)行選擇.假設(shè)論域空間有n個(gè)樣本，f個(gè)特征，則該算法的時(shí)間復(fù)雜度為O(n·f2).

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

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

為了驗(yàn)證FSHC算法的有效性，選取12個(gè)高維數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，包括9個(gè)類別不平衡數(shù)據(jù)集和3個(gè)常規(guī)數(shù)據(jù)集，其中，brain、car、dlbcl、DrivFace、glioma、lung、lung2、lymphoma、srbct為類別不平衡數(shù)據(jù)集，colon、mll、prostate為常規(guī)數(shù)據(jù)集，描述信息見表2.對(duì)多類別數(shù)據(jù)集而言，由于類別存在對(duì)立的關(guān)系，當(dāng)類別足夠多樣時(shí)，遍歷到某一類樣本即可視為小類樣本，假設(shè)為正類，其余類樣本即為異類，同理，遍歷其余類別樣本亦如此.

表2 類別不平衡數(shù)據(jù)集和常規(guī)數(shù)據(jù)集Table 2 Class-imbalanced data sets and routine data sets

為了更直觀地呈現(xiàn)數(shù)據(jù)集的相關(guān)信息，采用相關(guān)矩陣圖可視化高維數(shù)據(jù)的標(biāo)記信息，矩陣圖用灰度刻畫類別及樣本數(shù)量，右邊細(xì)縱軸刻度代表類別，一種灰度表示一個(gè)類別，類別自下而上有序排列，左邊縱軸刻度代表樣本數(shù)量，樣本數(shù)自下而上遞增，一個(gè)色塊表示該類別擁有的樣本數(shù)量，詳見圖2.

3.2 評(píng)價(jià)指標(biāo)

在高維小樣本數(shù)據(jù)的分類學(xué)習(xí)過程中，對(duì)分類精度而言，即使類別不平衡問題造成小類樣本的誤判，無法區(qū)分小類樣本的算法依然可以有比較高的精度，因此，本文實(shí)驗(yàn)結(jié)果的評(píng)價(jià)指標(biāo)采用F-Score、G-Mean、分類精度，其中，F(xiàn)-Score和G-Mean是兩個(gè)評(píng)價(jià)算法對(duì)于類別不平衡數(shù)據(jù)集小類樣本分類性能的重要指標(biāo).關(guān)于F-Score和G-Mean評(píng)價(jià)指標(biāo)的正負(fù)例樣本的劃分，本文算法采用依次遍歷數(shù)據(jù)的樣本類別.假設(shè)當(dāng)前遍歷到的類別為正類，則其余類別為異類，屬于正類的樣本為正例樣本，屬于異類的樣本為負(fù)例樣本.然后分別求各類別的F-Score值和G-Mean值，再求均值作為最終的F-Score值和G-Mean值.

設(shè)TP為真正例，TN為真負(fù)例，F(xiàn)P為假正例，F(xiàn)N為假負(fù)例，則查準(zhǔn)率為P=TP/(TP+FP)，查全率為R=TP/(TP+FN)，F(xiàn)-Score定義為:

(5)

圖2 高維數(shù)據(jù)集的相關(guān)矩陣圖Fig.2 Correlation matrix of high-dimensional data sets

G-Mean定義為:

(6)

為了顯示算法的統(tǒng)計(jì)顯著性，使用基于算法排序的Friedman檢驗(yàn)，假定在N個(gè)數(shù)據(jù)集上比較k個(gè)算法，令ri表示第i個(gè)算法的平均序值，定義Friedman統(tǒng)計(jì)量為:

(7)

其中，

(8)

若“所有算法的性能相同”的假設(shè)被拒絕，則表明算法的性能顯著不同，此時(shí)以Nemenyi后續(xù)檢驗(yàn)進(jìn)一步區(qū)分，Nemenyi檢驗(yàn)計(jì)算出平均序值差別的臨界值域?yàn)?

(9)

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

本文實(shí)驗(yàn)全部運(yùn)行在3.10GHz處理器，4.00GB內(nèi)存，windows 7系統(tǒng)及Matlab 2013的實(shí)驗(yàn)平臺(tái)上.為減少因各特征量綱不一致對(duì)實(shí)驗(yàn)結(jié)果造成影響，采用離差標(biāo)準(zhǔn)化將所有數(shù)據(jù)的屬性值歸一化到[0，1]區(qū)間.

表3 平均F-Score值Table 3 Average F-Score value

為了檢驗(yàn)算法的有效性，實(shí)驗(yàn)采用mRMR[10]、DISR[11]、NRS[12]等經(jīng)典特征選擇算法，以及OSFS[13]、Fast-OSFS[13]、K-OFSD[7]、OFS[8]等在線特征選擇算法作為對(duì)比算法.基分類器為RBF-SVM，且采用5折交叉驗(yàn)證.由于mRMR、DISR算法的特征選擇結(jié)果為特征排序，NRS、OSFS、Fast-OSFS、OFS、K-OFSD、FSHC算法的特征選擇結(jié)果為特征子集.為了公平比較，排序法算法mRMR、DISR特征排序中的特征數(shù)量設(shè)置為子集法算法NRS、OSFS、Fast-OSFS、OFS、K-OFSD、FSHC特征選擇結(jié)果中特征數(shù)最多的數(shù)目，并從第一個(gè)開始取.NRS的鄰域參數(shù)δ設(shè)置為0.1.OSFS和Fast-OSFS采用Fisher′s Z test方法度量特征的相關(guān)性，顯著性水平的參數(shù)α設(shè)置為0.01[14].K-OFSD和OFS中的近鄰參數(shù)k取7，特征與標(biāo)記的相關(guān)性閾值β設(shè)置為0.5，OFS中參數(shù)n取4，以類別包含數(shù)量最少的樣本為小類樣本[7，8].

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

3.4.1 預(yù)測(cè)精度分析

實(shí)驗(yàn)數(shù)據(jù)表3-表5分別給出了各算法在各數(shù)據(jù)集上特征選擇子集的平均F-Score值、平均G-Mean值以及平均分類精度和標(biāo)準(zhǔn)差.其中，標(biāo)注黑體部分代表該算法在此數(shù)據(jù)集上的性能最優(yōu).

表4 平均G-Mean值Table 4 Average G-Mean value

由表3和表4可見，在類不平衡數(shù)據(jù)集brain上算法FSHC的分類性能遜于K-OFSD、OFS，在類不平衡數(shù)據(jù)集lymphoma上算法FSHC的分類性能遜于Fast-OSFS. 除以上兩個(gè)數(shù)據(jù)集外，算法FSHC的分類性能均優(yōu)于對(duì)比算法.表5給出了特征選擇子集的平均分類精度和標(biāo)準(zhǔn)差，分類精度越高說明樣本分類越準(zhǔn)確，標(biāo)準(zhǔn)差越小說明分類穩(wěn)定性越高.不難看出，在平均分類精度方面，除了在類別不平衡數(shù)據(jù)集brain上算法FSHC的分類精度略遜于算法K-OFSD、OFS外，F(xiàn)SHC的分類精度均優(yōu)于對(duì)比算法.

F-Score和G-Mean是兩個(gè)評(píng)價(jià)算法對(duì)小類樣本分類性能的重要指標(biāo)，F(xiàn)SHC算法在這兩個(gè)評(píng)價(jià)指標(biāo)上都獲得了很高的值，由此可見，利用一致性分析的高維類別不平衡數(shù)據(jù)特征選擇算法，相對(duì)于經(jīng)典特征選擇算法或者在線流特征選擇算法在處理高維小樣本數(shù)據(jù)分類學(xué)習(xí)任務(wù)中的類不平衡問題方面具有更高效的表現(xiàn)能力.

表5 平均分類精度和標(biāo)準(zhǔn)差Table 5 Average classification accuracy and standard deviation

3.4.2 統(tǒng)計(jì)性分析

序值表6中的子表(a)-(c)分別根據(jù)表3-表5的測(cè)試結(jié)果給出了多數(shù)據(jù)集多算法在F-Score、G-Mean和分類精度評(píng)價(jià)指標(biāo)上的算法比較序值表，各算法在每個(gè)數(shù)據(jù)集上根據(jù)測(cè)試性能由好到壞排序，并賦予序值，若算法的測(cè)試性能相同，則平分序值.表6橫軸的數(shù)字對(duì)應(yīng)表3的表頭橫軸代表的算法，縱軸的數(shù)字對(duì)應(yīng)表3的表頭縱軸代表的數(shù)據(jù)集，其中，最后一行表示各算法的平均序值.對(duì)表F檢驗(yàn)參數(shù)alpha取0.05的常用臨界值表可知，8個(gè)算法12個(gè)數(shù)據(jù)集的臨界值為2.131，根據(jù)Friedman統(tǒng)計(jì)量公式，計(jì)算F-Score、G-Mean、分類精度的τF值分別為7.934、6.998、9.299，均大于F檢驗(yàn)臨界值2.131，拒絕“所有算法性能相同”的假設(shè)，進(jìn)行Nemenyi后續(xù)檢驗(yàn).對(duì)表Nemenyi檢驗(yàn)參數(shù)alpha取0.05的常用qα值表可知，8個(gè)比較算法的qα值為3.031，根據(jù)Nemenyi檢驗(yàn)的臨界值域公式，計(jì)算得到臨界值域CD為3.031.

由表6的平均序值可知，子表(a)、(b)、(c)算法FSHC與算法Fast-OSFS 、OFS的差距均未超過臨界值域，說明算法FSHC與算法Fast-OSFS 、OFS的性能沒有顯著差別.而算法FSHC顯著優(yōu)于算法mRMR、DISR、NRS、OSFS、K-OFSD，因?yàn)樗惴‵SHC與算法mRMR、DISR、NRS、OSFS、K-OFSD的差距超過了臨界值域.

上述比較檢驗(yàn)可以直觀地用弗里德曼檢驗(yàn)圖顯示，圖3中的子圖(a)-(c)的弗里德曼檢驗(yàn)圖分別由表6中的子表(a)-(c)導(dǎo)出，橫軸表示各算法的平均序值，縱軸表示算法，對(duì)應(yīng)表6的算法序號(hào)，其中，第8號(hào)純黑線表示算法FSHC的平均序值和臨界值域.對(duì)每個(gè)算法，用圓點(diǎn)顯示其平均序值，以圓點(diǎn)為中心的橫線段表示臨界值域的大小，于是可從圖中觀察，若兩個(gè)算法的橫線段有交疊，說明這兩個(gè)算法的分類性能沒有顯著差別，否則說明其性能有顯著差別.也可以用灰度區(qū)分算法的性能，第8號(hào)純黑線為算法FSHC，對(duì)比其余算法，對(duì)比算法為深灰線，說明性能顯著不同，對(duì)比算法為淺灰線，說明性能沒有顯著差別.由圖3可見，子圖(a)、(b)、(c)純黑線8號(hào)算法FSHC與淺灰線5號(hào)算法Fast-OSFS 、7號(hào)算法OFS沒有顯著差別，因?yàn)樗鼈兊臋M線段有交疊區(qū)域，對(duì)比算法灰度為淺灰，而算法FSHC顯著優(yōu)于余下的算法，因?yàn)樗鼈兊臋M線段沒有交疊區(qū)域，余下對(duì)比算法灰度為深灰.顯然，算法FSHC的平均序值均高于對(duì)比算法，說明FSHC的分類性能均優(yōu)于對(duì)比算法.

表6 算法比較序值表Table 6 Ordinal table of algorithm comparison

(b)G-Mean index

(c)Accuracy index

圖3 FSHC算法與對(duì)比算法的Friedman檢驗(yàn)圖Fig.3 Friedman test diagram of FSHC algorithm and comparison algorithms

圖4 FSHC算法與對(duì)比算法的蜘蛛網(wǎng)圖Fig.4 Spider diagram of FSHC algorithm and comparison algorithms

3.4.3 穩(wěn)定性分析

為了驗(yàn)證不同算法的穩(wěn)定性[15]，繪制蜘蛛網(wǎng)圖來表示多數(shù)據(jù)集多算法在各個(gè)評(píng)價(jià)指標(biāo)上的穩(wěn)定性指數(shù).圖4中的子圖(a)-(c)分別給出了算法在F-Score、G-Mean和分類精度評(píng)價(jià)指標(biāo)上的穩(wěn)定性指數(shù)，其中，純黑直線代表算法FSHC的穩(wěn)定性值.由圖4可見，對(duì)于F-Score和G-Mean而言，算法FSHC在6個(gè)數(shù)據(jù)集上接近穩(wěn)定解，在類別不平衡數(shù)據(jù)集brain、DrivFace、glioma、lymphoma上穩(wěn)定性較弱.

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

在高維類別不平衡數(shù)據(jù)特征選擇過程中，為了獲得在小類樣本中具有高可分離性的特征，通過定義樣本的近鄰關(guān)系，計(jì)算樣本分布與類別空間的包含度，進(jìn)而導(dǎo)出特征與標(biāo)記的一致性，由此提出一致性分析模型，并構(gòu)建了面向高維類別不平衡數(shù)據(jù)的貪婪搜索算法.實(shí)驗(yàn)結(jié)果表明，本文所提的方法是有效的.