戴建國

(廣州大學 數學與信息科學學院， 廣東 廣州 510006)

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

戴建國

(廣州大學 數學與信息科學學院， 廣東 廣州 510006)

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

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

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

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

1 特征的相關性度量標準

不同的特征與類別屬性的相關強弱是不一樣的，一個好的分類特征，應該是與類別屬性有強的相關性，并且與其他特征不相關或者弱相關，即是非冗余的，因而也需要一個合適度量相關性強弱的指標。

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

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

定義相關系數矩陣

其中Tij=Tji=ρXiXj。

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

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

由公式可得

說明兩者的相關性大小為0.1216。

2 特征選取的方法與過程

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

2.1 S-相關分析

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

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

2.2 T-相關分析

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

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

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

綜合上面兩步分析，下面給出數據特征選取的完整過程：

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

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

(3)計算W1中特征的T-相關系數矩陣，選取T(max(W1)，Xj)<δ2的特征，其中max(W1)表示W1中S-相關系數最大的特征，Xj∈W1-max(W1)。將選出的特征又按S-相關系數的大小排序構成子集W2。

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

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

3 實驗結果與分析

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

表2 固定訓練集/測試集下的分類結果

表3 十交叉驗證下的分類結果

注：其中準確率是十交叉驗證準確率的平均值。

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

4 結束語

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

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

[責任編輯：謝 平]

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

戴建國(1992—)，男，江西省撫州市人，廣州大學碩士研究生，主要研究方向為概率統(tǒng)計、數據挖掘。

O212

A