一种新的有监督特征选择方法

戴建国

(广州大学 数学与信息科学学院， 广东 广州 510006)

一种新的有监督特征选择方法

戴建国

(广州大学 数学与信息科学学院， 广东 广州 510006)

针对高维数据中的特征选择问题，提出一种有监督的特征选择方法。首先基于非线性相关度量标准作为对离散型特征进行选择，先后做选相关、去冗余两种相关分析，并采用向前方式搜索，最后用邻近算法作为分类器对所选择的特征进行实验。结果表明，该方法能选出有用的特征来提高分类准确率，并降低数据的维度。

特征选择； 有监督； 非线性； 离散

在大数据时代，特征选择已成为机器学习和数据挖掘中的重要过程，如文本挖掘、基因表达、图像处理等，会对学习和挖掘效果产生重大的影响。特征选择主要目的是从原始特征中选出一些有效的特征，用部分特征的信息来反映总体特征的信息，以降低特征空间的维数和增强分类或者预测效果。当数据维数很大(多特征)时，势必会包含许多冗余(redundancy)特征[1]，所谓的特征冗余性是指特征之间的相关性，当两个特征完全相关，则它们互为冗余特征。甚至是与类别属性无关的特征，这都会降低分类的准确率，从而需要一些方法来选取最好的特征子集。当然，特征的类型也有很多，有离散型、连续型以及混合型。针对不同类型的特征许多学者或研究人员已经提出了相应的选择方法[2]，但主要分为三类：封装式(Wrapper)[3-5]，利用感兴趣的学习器作为一个黑盒根据他们的预测能力对特征子集进行评分；过滤式(Filter)[6-7]，利用特征的统计性质过滤掉一些包含很少信息的特征；嵌入式(Embedded)[8-9]，在模型构建中进行变量选择。

为了改善数据挖掘的效果，本文对离散型特征的选择提出一种Filter式有监督向前的特征选择方法(supervised and forward features selection)。该方法是基于τJ相关系数作为度量标准，先通过τJ相关系数去除与分类目标无相关或者弱相关的特征，再通过相关系数矩阵删除冗余特征进行降维，最后选出分类能力好的特征子集。

1 特征的相关性度量标准

不同的特征与类别属性的相关强弱是不一样的，一个好的分类特征，应该是与类别属性有强的相关性，并且与其他特征不相关或者弱相关，即是非冗余的，因而也需要一个合适度量相关性强弱的指标。

对于度量相关性强弱的的方法通常有线性和非线性两类，这里介绍一种新的度量离散型变量的非线性方法[10]τJ，它是由相关性度量指标[11]τ启发得到的。若给定两个离散型变量X，Y，各有类别数分别为I，J，则有

其中pij，p+j，pi+分别为联合概率与边缘概率，τJ代表在有联合分布信息下猜错概率减少的比例，从而用其来度量相关性。当τJ=0时意味着X，Y独立，当τJ=1时意味着X，Y完全相关。为了书写方便，下文用ρ来代替τJ。

定义相关系数矩阵

其中Tij=Tji=ρXiXj。

下面给出一个简单的例子来说明τJ。已知两个变量的联合分布如表1所示。

表1 变量的联合分布

由公式可得

说明两者的相关性大小为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关联性最大(即S-相关性最大)的那个特征出发，选出与该特征T-相关性小于δ2的特征，将这些选出的特征按与Y相关性(即S-相关性)的大小排序，又选出S-相关性最大的特征与其余T-相关小于δ2的特征，不断重复该过程，直到最后选出特征集T-相关小于δ2只包含一个特征时结束过程，最后将每一步选出的最大S-相关对应的特征构成一个特征集，即为要找的最优特征子集。

2.3 最优特征子集选取步骤

综合上面两步分析，下面给出数据特征选取的完整过程：

(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]中常用的数据集。现将3KNN作为分类器。在做S、T-相关分析时，都选用ρ作为相关性强弱的度量，两个阈值δ1=0.01，δ2=0.2。一般情况下δ1选的值比较小，δ2选的值比较大。以下表2、表3分别是对原始数据、S-相关分析后的数据和T-相关分析后的数据用3KNN分类器在固定训练集/测试集和十交叉验证分类后的结果，其中包括原始特征数、各关联后的特征数，以及它们对应的分类准确率。

表2 固定训练集/测试集下的分类结果

表3 十交叉验证下的分类结果

注：其中准确率是十交叉验证准确率的平均值。

从上面结果可知，在S-相关分析后特征数就有明显的减少，而且其分类准确率就有所提高，再进行T-相关分析后特征数又有所减少，分类准确率进一步提高了。对于数据集Letter，satisfaction在S-相关分析后再进行T-相关分析时，其特征数值并没有减少，说明在它们的特征子集W1中的特征之间几乎不存在冗余性，尤其对satisfaction数据集S-相关分析分类准确率就有很大的提高。在十交叉验证下，数据集mushrooms的分类准确类均达到100%，而在给定训练集/测试集的情况下分析后的准确率有所提高，但分类准确率均不是很高，这说明在测试集和训练集的选择上不是很合理，有可能类别属性在测试集和训练集上分配不均。这也启发我们最好使用交叉验证的方法。在Fdata数据集中两种方法的分类准确率相差不大，但在相关分析后维度有所减少，准确率有所提高。

4 结束语

大数据时代，特征提取对数据分析和数据挖掘有着重要的作用，一个好的特征选择方法能从高维数据中提取出有用信息的特征。文中基于离散型变量的相关性提出的特征选取算法，对机器学习中常用的几个数据集进行分析，先选择相关特征，然后去除冗余特征，最后将选择的特征用3KNN做为分类器进行试验。结果表明其不仅能降低维数，而且增强了分类效果，进而说明了该方法是有效的。同样，对于连续型变量也可先将其离散化，然后用该算法进行特征选取。

[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—)，男，江西省抚州市人，广州大学硕士研究生，主要研究方向为概率统计、数据挖掘。

O212

A