一種新的有監(jiān)督特征選擇方法

戴建國(guó)

(廣州大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院， 廣東 廣州 510006)

一種新的有監(jiān)督特征選擇方法

戴建國(guó)

(廣州大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院， 廣東 廣州 510006)

針對(duì)高維數(shù)據(jù)中的特征選擇問(wèn)題，提出一種有監(jiān)督的特征選擇方法。首先基于非線性相關(guān)度量標(biāo)準(zhǔn)作為對(duì)離散型特征進(jìn)行選擇，先后做選相關(guān)、去冗余兩種相關(guān)分析，并采用向前方式搜索，最后用鄰近算法作為分類器對(duì)所選擇的特征進(jìn)行實(shí)驗(yàn)。結(jié)果表明，該方法能選出有用的特征來(lái)提高分類準(zhǔn)確率，并降低數(shù)據(jù)的維度。

特征選擇； 有監(jiān)督； 非線性； 離散

在大數(shù)據(jù)時(shí)代，特征選擇已成為機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中的重要過(guò)程，如文本挖掘、基因表達(dá)、圖像處理等，會(huì)對(duì)學(xué)習(xí)和挖掘效果產(chǎn)生重大的影響。特征選擇主要目的是從原始特征中選出一些有效的特征，用部分特征的信息來(lái)反映總體特征的信息，以降低特征空間的維數(shù)和增強(qiáng)分類或者預(yù)測(cè)效果。當(dāng)數(shù)據(jù)維數(shù)很大(多特征)時(shí)，勢(shì)必會(huì)包含許多冗余(redundancy)特征[1]，所謂的特征冗余性是指特征之間的相關(guān)性，當(dāng)兩個(gè)特征完全相關(guān)，則它們互為冗余特征。甚至是與類別屬性無(wú)關(guān)的特征，這都會(huì)降低分類的準(zhǔn)確率，從而需要一些方法來(lái)選取最好的特征子集。當(dāng)然，特征的類型也有很多，有離散型、連續(xù)型以及混合型。針對(duì)不同類型的特征許多學(xué)者或研究人員已經(jīng)提出了相應(yīng)的選擇方法[2]，但主要分為三類：封裝式(Wrapper)[3-5]，利用感興趣的學(xué)習(xí)器作為一個(gè)黑盒根據(jù)他們的預(yù)測(cè)能力對(duì)特征子集進(jìn)行評(píng)分；過(guò)濾式(Filter)[6-7]，利用特征的統(tǒng)計(jì)性質(zhì)過(guò)濾掉一些包含很少信息的特征；嵌入式(Embedded)[8-9]，在模型構(gòu)建中進(jìn)行變量選擇。

為了改善數(shù)據(jù)挖掘的效果，本文對(duì)離散型特征的選擇提出一種Filter式有監(jiān)督向前的特征選擇方法(supervised and forward features selection)。該方法是基于τJ相關(guān)系數(shù)作為度量標(biāo)準(zhǔn)，先通過(guò)τJ相關(guān)系數(shù)去除與分類目標(biāo)無(wú)相關(guān)或者弱相關(guān)的特征，再通過(guò)相關(guān)系數(shù)矩陣刪除冗余特征進(jìn)行降維，最后選出分類能力好的特征子集。

1 特征的相關(guān)性度量標(biāo)準(zhǔn)

不同的特征與類別屬性的相關(guān)強(qiáng)弱是不一樣的，一個(gè)好的分類特征，應(yīng)該是與類別屬性有強(qiáng)的相關(guān)性，并且與其他特征不相關(guān)或者弱相關(guān)，即是非冗余的，因而也需要一個(gè)合適度量相關(guān)性強(qiáng)弱的指標(biāo)。

對(duì)于度量相關(guān)性強(qiáng)弱的的方法通常有線性和非線性兩類，這里介紹一種新的度量離散型變量的非線性方法[10]τJ，它是由相關(guān)性度量指標(biāo)[11]τ啟發(fā)得到的。若給定兩個(gè)離散型變量X，Y，各有類別數(shù)分別為I，J，則有

其中pij，p+j，pi+分別為聯(lián)合概率與邊緣概率，τJ代表在有聯(lián)合分布信息下猜錯(cuò)概率減少的比例，從而用其來(lái)度量相關(guān)性。當(dāng)τJ=0時(shí)意味著X，Y獨(dú)立，當(dāng)τJ=1時(shí)意味著X，Y完全相關(guān)。為了書(shū)寫(xiě)方便，下文用ρ來(lái)代替τJ。

定義相關(guān)系數(shù)矩陣

其中Tij=Tji=ρXiXj。

下面給出一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明τJ。已知兩個(gè)變量的聯(lián)合分布如表1所示。

表1 變量的聯(lián)合分布

由公式可得

說(shuō)明兩者的相關(guān)性大小為0.1216。

2 特征選取的方法與過(guò)程

在數(shù)據(jù)中，假定特征與類別變量表示為(X1，X2，…，XN，Y)，N為特征總數(shù)，類別屬性為Y，其中X，Y均為離散型變量，為說(shuō)明特征的相關(guān)性和冗余性先做如下兩種定義。

2.1 S-相關(guān)分析

定義1 特征與類別之間的相關(guān)叫做S-相關(guān)，用S(Xi，Y)表示，且有S(Xi，Y)=ρXiY。

S-相關(guān)性的強(qiáng)弱會(huì)直接影響到分類的準(zhǔn)確性，S-相關(guān)性越強(qiáng)，對(duì)應(yīng)的特征對(duì)分類越有幫助，反之會(huì)降低分類的準(zhǔn)確性。因此，首先要從總的特征集中去除剩下的弱相關(guān)或者不相關(guān)的的特征。為了提高效率，需要預(yù)先給定閾值δ1，在計(jì)算S-相關(guān)時(shí)，如果某個(gè)特征的S-相關(guān)性大于給定的閾值時(shí)，即S(Xi，Y)>δ1，則該特征可以選出來(lái)進(jìn)行下一步的相關(guān)分析。

2.2 T-相關(guān)分析

定義2 特征與特征之間的相關(guān)叫做T-相關(guān)，用Tij(Xi，Xj)表示，且有Tij(Xi，Xj)=ρXiXj。

對(duì)于S-相關(guān)分析后的理想情況是所有的特征之間是不相關(guān)的，即不存在冗余性。但實(shí)際情況并非如此，特征與特征之間往往會(huì)存在一定的相關(guān)性，從而需要去除冗余特征，即做T-相關(guān)分析，在這步分析中先計(jì)算相關(guān)系數(shù)矩陣，該矩陣是對(duì)稱的，也就是說(shuō)兩個(gè)特征間的相關(guān)性是個(gè)定值，與兩者的順序無(wú)關(guān)。在S-相關(guān)分析后對(duì)選取的特征按相關(guān)性值的大小進(jìn)行排序，并計(jì)算這些特征的T-相關(guān)系數(shù)矩陣R=(Tij)=(ρXiXj)，其中i，j均為上述排序后特征對(duì)應(yīng)的下標(biāo)。給定閾值δ2，從與Y關(guān)聯(lián)性最大(即S-相關(guān)性最大)的那個(gè)特征出發(fā)，選出與該特征T-相關(guān)性小于δ2的特征，將這些選出的特征按與Y相關(guān)性(即S-相關(guān)性)的大小排序，又選出S-相關(guān)性最大的特征與其余T-相關(guān)小于δ2的特征，不斷重復(fù)該過(guò)程，直到最后選出特征集T-相關(guān)小于δ2只包含一個(gè)特征時(shí)結(jié)束過(guò)程，最后將每一步選出的最大S-相關(guān)對(duì)應(yīng)的特征構(gòu)成一個(gè)特征集，即為要找的最優(yōu)特征子集。

2.3 最優(yōu)特征子集選取步驟

綜合上面兩步分析，下面給出數(shù)據(jù)特征選取的完整過(guò)程：

(1)input(X1，X2，…，XN，Y)，δ1，δ2，其中X代表特征，Y代表分類屬性；

(2)計(jì)算S-相關(guān)系數(shù)，選出S-相關(guān)系數(shù)大于δ1的特征，并將其按大小排序后構(gòu)成特征子集W1={Xi|S(Xi，Y)>δ1}。

(3)計(jì)算W1中特征的T-相關(guān)系數(shù)矩陣，選取T(max(W1)，Xj)<δ2的特征，其中max(W1)表示W(wǎng)1中S-相關(guān)系數(shù)最大的特征，Xj∈W1-max(W1)。將選出的特征又按S-相關(guān)系數(shù)的大小排序構(gòu)成子集W2。

(4)將(3)中選出的子集重復(fù)步驟(3)，直到Wt只包含一個(gè)特征時(shí)停止。

(5)最后選出的子集為W={max(W1)，max(W2)，…，max(Wt)}。

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

本實(shí)驗(yàn)使用了數(shù)據(jù)Fdata，Letter，mushrooms，satisfaction。除了第一個(gè)數(shù)據(jù)集(它是一項(xiàng)加拿大調(diào)查數(shù)據(jù)[12]中的部分?jǐn)?shù)據(jù))，另外3個(gè)均是機(jī)器學(xué)習(xí)庫(kù)[13]中常用的數(shù)據(jù)集?，F(xiàn)將3KNN作為分類器。在做S、T-相關(guān)分析時(shí)，都選用ρ作為相關(guān)性強(qiáng)弱的度量，兩個(gè)閾值δ1=0.01，δ2=0.2。一般情況下δ1選的值比較小，δ2選的值比較大。以下表2、表3分別是對(duì)原始數(shù)據(jù)、S-相關(guān)分析后的數(shù)據(jù)和T-相關(guān)分析后的數(shù)據(jù)用3KNN分類器在固定訓(xùn)練集/測(cè)試集和十交叉驗(yàn)證分類后的結(jié)果，其中包括原始特征數(shù)、各關(guān)聯(lián)后的特征數(shù)，以及它們對(duì)應(yīng)的分類準(zhǔn)確率。

表2 固定訓(xùn)練集/測(cè)試集下的分類結(jié)果

表3 十交叉驗(yàn)證下的分類結(jié)果

注：其中準(zhǔn)確率是十交叉驗(yàn)證準(zhǔn)確率的平均值。

從上面結(jié)果可知，在S-相關(guān)分析后特征數(shù)就有明顯的減少，而且其分類準(zhǔn)確率就有所提高，再進(jìn)行T-相關(guān)分析后特征數(shù)又有所減少，分類準(zhǔn)確率進(jìn)一步提高了。對(duì)于數(shù)據(jù)集Letter，satisfaction在S-相關(guān)分析后再進(jìn)行T-相關(guān)分析時(shí)，其特征數(shù)值并沒(méi)有減少，說(shuō)明在它們的特征子集W1中的特征之間幾乎不存在冗余性，尤其對(duì)satisfaction數(shù)據(jù)集S-相關(guān)分析分類準(zhǔn)確率就有很大的提高。在十交叉驗(yàn)證下，數(shù)據(jù)集mushrooms的分類準(zhǔn)確類均達(dá)到100%，而在給定訓(xùn)練集/測(cè)試集的情況下分析后的準(zhǔn)確率有所提高，但分類準(zhǔn)確率均不是很高，這說(shuō)明在測(cè)試集和訓(xùn)練集的選擇上不是很合理，有可能類別屬性在測(cè)試集和訓(xùn)練集上分配不均。這也啟發(fā)我們最好使用交叉驗(yàn)證的方法。在Fdata數(shù)據(jù)集中兩種方法的分類準(zhǔn)確率相差不大，但在相關(guān)分析后維度有所減少，準(zhǔn)確率有所提高。

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

大數(shù)據(jù)時(shí)代，特征提取對(duì)數(shù)據(jù)分析和數(shù)據(jù)挖掘有著重要的作用，一個(gè)好的特征選擇方法能從高維數(shù)據(jù)中提取出有用信息的特征。文中基于離散型變量的相關(guān)性提出的特征選取算法，對(duì)機(jī)器學(xué)習(xí)中常用的幾個(gè)數(shù)據(jù)集進(jìn)行分析，先選擇相關(guān)特征，然后去除冗余特征，最后將選擇的特征用3KNN做為分類器進(jìn)行試驗(yàn)。結(jié)果表明其不僅能降低維數(shù)，而且增強(qiáng)了分類效果，進(jìn)而說(shuō)明了該方法是有效的。同樣，對(duì)于連續(xù)型變量也可先將其離散化，然后用該算法進(jìn)行特征選取。

[1] YU Lei，LIU Huan.Efficient Feature Selection via Analysis of Relevance and Redundancy[J].Journal of Machine Learning Research，2004，5(12)：1205-1224.

[2] GUYON I，ELISSEEFF A.An introduction to variable and feature selection[J].Journal of Machine Learning Research，2003，3(6)：1157-1182.

[3] MALDONADO S，WEBER R.A wrapper method for feature selection using Support Vector Machines[J].Information Sciences，2009，179(13)：2208-2217.

[4] KABIR M M，ISLAM M M，MURASE K.A new wrapper feature selection approach using neural network[J].Neurocomputing，2010，73(16-18)：3273-3283.

[5] KOHAVI R，JOHN G H.Wrappers for feature subset selection[J].Artificial Intelligence，1997，97(1-2)：273-324.

[6] YU Lei，LIU Huan.Feature Selection for High-Dimensional Data：A Fast Correlation-Based Filter Solution[C]//Washington：Proceedings of the Twentieth International Conference on Machine Learning，2003：856-863.

[7] DASH M，CHOI K，SCHEUERMANN P，et al.Feature Selection for Clustering-A Filter Solution[C]//IEEEInternational Conference on Data Mining，2002：115-122.

[8] PERALTA B，SOTO A.Embedded local feature selection within mixture of experts[J].Information Sciences，2014，269(8)：176-187.

[10] BISWAS A，PARK E.Measures of association for nominal categorical variables[J].Journal of the Korean Statistical Society，2009，38(3)：247-258.

[11] GOODMAN L A，KRUSKAL W H.Measures of Association for Cross Classifications Ⅱ：Further Discussion and References[J].Journal of the American Statistical Association，1959，54(285)：123-163.

[12] KDnuggets.Datasets for Data Mining and Data Science[DB].[2017-02-01].http：//www.kdnuggets.com/datasets/index.html.

[13] UC Irvine.Machine Learning Repository[DB].[2017-02-01].http：//archirve.ics.uci.edu/ml/index.php.

[責(zé)任編輯：謝 平]

A novel method for supervised feature selection

DAI Jian-guo

(Mathematics and Information Science Department, Guangzhou University, Guangzhou 510006, China)

Aiming at the problem of feature selection in high-dimensional data, a supervised feature selection method is proposed. It uses the nonlinear related metrics as criterion of the discrete feature selection and then relevancy and redundancy removal analysis is made. By using the forward search method, we have evaluated the selected features with adjacent algorithm as a classifier. The results show that this method can select useful feature to improve the classification accuracy, and reduce the dimension of data.

feature selection; supervision; nonlinear; discrete

2096-3998(2017)04-0089-04

2017-03-09

2017-04-16

戴建國(guó)(1992—)，男，江西省撫州市人，廣州大學(xué)碩士研究生，主要研究方向?yàn)楦怕式y(tǒng)計(jì)、數(shù)據(jù)挖掘。

O212

A