特征选择方法中三种度量的比较研究

宋智超　康健　孙广路　何勇军

摘要：不同类型数据中特征与类别以及特征与特征之间存在一定的线性和非线性相关性。针对基于不同度量的特征选择方法在不同类型数据集上选取的特征存在明显差别的问题，本文选择线性相关系数、对称不确定性和互信息三种常用的线性或非线性度量，将它们应用于基于相关性的快速特征选择方法中，对它们在基因微阵列和图像数据上的特征选择效果进行实验验证和比较。实验结果表明，基于相关性的快速特征选择方法使用线性相关系数在基因数据集上选取的特征集往往具有较好分类准确率，使用互信息在图像数据集上选取的特征集的分类效果较好，使用对称不确定性在两种类型数据上选取特征的分类效果较为稳定。

关键词：特征选择；线性相关系数；对称不确定性；互信息；基于相关性的快速特征选择方法

DOI：10.15938/j.jhust.2018.01.020

中图分类号： TM391.1

文献标志码： A

文章编号： 1007-2683（2018）01-0111-06

Abstract：It has been known that either linear correlation or nonlinear correlation might exist between featuretofeature and featuretoclass in datasets. In this paper， we study the differences of selected feature subset when different kinds of measures are applied with same feature selection method in different kinds of datasets. Three representative linear or nonlinear measures， linear correlation coefficient， symmetrical uncertainty， and mutual information are selected. By combining them with the fast correlationbased filter （FCBF） feature selection method， we make the comparison of selected feature subset from 8 gene microarray and image datasets. Experimental results indicate that the feature subsets selected by linear correlation coefficient based FCBF obtain better classification accuracy in gene microarray datasets than in image datasets， while mutual information and symmetrical uncertainty based FCBF tend to obtain better results in image datasets. Moreover， symmetrical uncertainty based FCBF is more robust in all datasets.

Keywords：feature selection；linear correlation coefficient；symmetrical uncertainty；mutual Information；fast correlationbased filter

0引言

數据挖掘方法能够从数据中获取到潜在的有效信息，在金融预测、模式识别等多个领域得到了广泛应用。随着互联网和生物信息学技术的不断进步，数据朝着更大规模的方向发展，并带来了“维度灾难”等问题[1]。解决上述问题的有效方法之一是降低数据集中特征的维数。特征选择作为数据挖掘和机器学习中的重要研究内容，其通过删除数据集中的无关和冗余特征，达到有效的降低特征维数，提高分类的准确率和效率的目的，并且具有去噪、防止机器学习模型过拟合的作用[2]。

现有的特征选择方法主要可以分为过滤方法、封装方法和嵌入方法[3]。封装方法使用预先选定的机器学习方法作为评价特征集优劣的准则，存在时间复杂度高的问题。嵌入方法则将特征选择和机器学习算法的训练过程相结合。过滤方法不依赖特定的机器学习方法，具有运行效率高的特点，适用于解决高维数据中的特征选择问题。本文主要针对过滤方法进行研究。

搜索策略和度量的选取是过滤方法的两个重要研究内容。学者们提出了基于一致性、基于距离、基于信息论等多种度量，并据此提出了多种评价函数[4-6]。当前研究者们重点关注特征选择方法的设计，实验常用数据集主要有基因生物数据、图像数据和文本数据等[7]。据作者调研，目前尚无针对不同度量在不同类型数据上可能存在的效果差异性的研究。本文选取常用的三种度量——线性相关系数、对称不确定性和互信息，并结合经典的特征选择方法，对这3种度量应用到不同类型数据集上的效果进行研究。

基于相关性的快速特征选择方法是一种经典的特征选择方法，其在多种数据集上都具有较好的效果，并且对于高维数据具有较快的运行效率。本文将上述不同的度量应用于基于相关性的快速特征选择方法中，通过实验验证对不同度量在基因生物数据和图像数据上效果的差异，并对度量和数据类型之间的关系进行研究。

本文第二节为相关工作，对目前影响较大的特征选择方法和度量的应用进行介绍；第三节描述特征选择中的3种度量和基于相关性的快速特征选择方法；第四节是实验数据集和实验结果，第五节为总结。

1相关工作

变量间的相关关系在机器学习和模式识别领域得到了广泛的研究。研究者们提出了多种度量对变量间的相关性进行挖掘，目前而言，变量之间的相关关系主要分为线性相关和非线性相关两类。早期的特征選择方法一般应用马氏距离、相关系数等线性度量[8]。文[9]使用相关系数、Wilcoxon秩和检验两种度量对基因数据中的特征关系进行挖掘。文[10]提出了最小乘方错误和最大信息压缩指数两种线性度量并应用于无监督的特征选择方法中，取得了较好的效果。然而，现实世界中的数据并不总是满足线性关系，对数据间线性关系的假设并不完备[11]。针对这种情况，学者们提出了多种非线性相关的度量，其中基于信息论的度量被认为是最有前景的度量，信息增益[12]、互信息[13]、归一化互信息[14]和条件互信息[15]等被应用到特征选择中，取得了不错的效果。

基于上述度量可以构建特征选择方法进行最优特征子集的选取。早期的特征选择方法只考虑特征与类别之间的相关性，如信息增益、Relief[16]和ReliefF[17]等。随着特征维数的增加，该类方法的时间复杂度呈线性增长并且能够适用于高维数据的特征选择。但是由于没有考虑冗余特征的影响，该类方法选取特征子集的分类效果往往不理想。

冗余特征的存在不仅增加了机器学习模型的时间复杂度，而且对最后的分类任务有干扰作用，也应该被去除。基于相关性的特征选择[18]、最小冗余最大相关[19]等方法可以对冗余特征进行处理，然而其使用的贪心序列搜索、最优搜索等搜索策略的时间复杂度为O（n2），使得这些方法很难应用到高维数据的特征选择中。

针对上述问题，马尔科夫毯首次被Koller等人应用到特征选择中，取得了很好的效果[20]。随后的学者们对马尔科夫毯方法进行了广泛的研究[7，11，21]。其中，论文[11]提出一种基于相关性的快速特征选择方法，并对特征选择中的基本问题进行了定义。后续研究者在此基础上进行改进并应用到不同的特征选择任务中[7，22]。从算法效率和选取的特征子集的分类效果两方面来看，基于相关性的快速特征选择方法具有一定的优势。

2特征选择中的度量和方法

3实验结果与分析

3.1实验设置

为了验证本文提出的3种度量在基因和图像数据上选取特征的分类效果是否存在差异，选取8个数据集进行实验研究。由于对选取的数据集无法事先得知最优特征子集，同时为了增强实验的说服性、避免实验结果的偏置，在不同数据集上应用本文提出的3种特征选择方法FSCC、FSSU和FSMI分别选取10，20，30，40维特征，对3种不同特征选择方法选取特征差异性进行比较。由于对数据集我们没有先验知识，当前特征选择工作一般使用分类器的准确率对最终选取的特征集优劣进行评价。本文使用常用的朴素贝叶斯（Nave Bayes， NB）和支持向量机（Support Vector Machine， SVM）分类器，统一使用10fold交叉验证得到3种特征选择方法选取不同维数特征的分类准确率。

实验中将数据随机均等分成2份，1份为训练集，1份为测试集，使用本文提出的3种特征选方法从训练集中选取预先设定维数的特征，然后根据选取的特征子集重新构造测试集，并应用NB和SVM分类器，采用10折交叉验证得到不同特征选择方法选取的特征集在测试集上的分类准确率。为了使得最后的实验结果更具统计意义，重复上述实验过程10次，并对10次实验的结果取平均值得到最终的分类准确率。

3.2数据集

实验中使用基因和图像两类数据集，对3种度量的效果进行实验分析。每类数据选取四个不同的数据集，有二分类也有多分类数据集，特征维数从280维到19993维，具体数据信息如表1所示。

3.3实验处理和结果

本文算法1为两阶段特征选择方法，算法第一阶段通过对FSCC、FSSU和FSMI3种方法设定不同的阈值θ，选取预期维数的特征。表2为3种特征选择方法分别选取不同维数特征在NB分类器上的实验结果。表3为3种特征选择方法选取的特征在SVM分类器上的实验结果。

图1和图2为3种特征选择方法选取不同维数特征在NB和SVM两个分类器上的准确率均值。从表2和图1中实验结果来看，FSCC在SMKCAN、TOX171和Leukemia 3个基因类型数据集上的分类准确率最高，而在四个图像类型数据上的分类准确率较FSSU和FSMI方法有明显的差距。在Arrhythmia数据集上与FSMI分类准确率相近。FSMI在4个图像数据上的分类效果最好，但在四个基因类型的数据集上的分类效果较差。FSSU在Arrhythmia数据上的分类效果最好，在TOX171数据集上的分类准确率最差，在其余的六个数据集上的效果与分类效果最好的方法效果相近。因此，从最终的分类结果来看，FSMI效果最好，并且其更适合处理图像类型数据。而FSCC更适合处理基因数据，并且FSCC在图像数据上的分类效果明显差于FSMI和FSSU方法。尽管FSSU方法只在Arrhythmia数据上的分类准确率最高，但是从所有八个数据集上的分类准确率来看，FSSU选取的特征在不同数据集上的分类效果更加稳定。

图2和表3中在SVM分类器上的实验结果与图1和表2中实验结果类似，FSCC方法仍然在SMKCAN、TOX171和Leukemia 3个基因数据上的分类准确率最高，FSSU在Arrhythmia、PIE10P和PIX10P 3个数据集上的效果最好，FSMI在其他两个图像数据上的效果最好。

由上述实验结果可得，线性相关系数适合基因类型数据的特征选择工作，而在图像类型数据上选取特征的分类准确率较差。互信息和对称不确定性更适合处理图像类型的数据，对称不确定性在两种类型的数据上选取特征的分类效果较为稳定。

4结语

本文选取基因和图像两种特征选择常用类型数据集，对特征选择常用的3种度量——线性相关系数、对称不确定性和互信息在不同数据集上的效果进行研究。为了加快特征选择的效率，同时保证选取特征的分类效果，将3种度量应用到基于相關性的快速特征选择方法中，并提出FSCC、FSSU和FSMI 3种不同的特征选择方法。使用朴素贝叶斯和SVM两种分类器评价3种不同特征选择方法选取的特征。在选取的8个数据集上的实验表明，线性相关系数更适合于处理基因类型数据，选择的特征能够取得较好的分类效果，而在图像数据集上的效果较差；互信息在图像类型数据上的效果较在基因类型数据上更为突出。对称不确定性在两种类型的数据上的效果较为稳定，且效果较好。

参 考 文 献：

[1]CHANDRASHEKAR G， SAHIN F. A Survey on Feature Selection Methods[J]. Computers & Electrical Engineering， 2014， 40（1）： 16-28.

[2]DESSI N， PES B. Similarity of Feature Selection Methods： An Empirical Study Across Data Intensive Classification Tasks[J]. Expert Systems with Applications， 2015， 42（10）： 4632-4642.

[3]ZHAO Z， LIU H. Searching for Interacting Features[C]// Proceedings of the 20th International Joint Conference on Artificial Intelligence. Hyderabad， India， 2007：1156-1161.

[4]DASH M， LIU H，MOTODA H. Consistency Based Feature Selection[C]// PacificAsia Conference on Knowledge Discovery and Data Mining， Current Issues and New Applications. SpringerVerlag， 2000：98-109.

[5]ZHANG J G， DENG H W. Gene Selection for Classification of Microarray Data Based on the Bayes Error[J]. BMC bioinformatics， 2007， 8（1）： 370.

[6]SOTOCA J M， PLA F. Supervised Feature Selection by Clustering Using Conditional Mutual Informationbased Distances[J]. Pattern Recognition， 2010， 43（6）： 2068-2081.

[7]SONG Q， NI J， WANG G. A Fast Clusteringbased Feature Subset Selection Algorithm for Highdimensional Data[J].IEEE Transactions on Knowledge and Data Engineering， 2013， 25（1）： 1-14.

[8]GUYON I， ELISSEEFF A. An Introduction to Variable and Feature Selection[J]. The Journal of Machine Learning Research， 2003， 3： 1157-1182.

[9]谢娟英， 高红超. 基于统计相关性与 Kmeans 的区分基因子集选择算法[J]. 软件学报， 2014， 25（9）： 2050-2075.

[10]MITRA P， MURTHY C A， PAL S K. Unsupervised Feature Selection Using Feature Similarity[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2002， 24（3）： 301-312.

[11]YU L， LIU H. Efficient Feature Selection Via Analysis of Relevance and Redundancy[J]. The Journal of Machine Learning Research， 2004（5）： 1205-1224.

[12]PEREIRA R B， PLASTINO A， ZADROZNY B， et al. Information Gain Feature Selection for MultiLabel Classification[J]. Journal of Information and Data Management， 2015， 6（1）： 48.

[13]HOQUE N， BHATTACHARYYA D K， KALITA J K. MIFSND： A Mutual Informationbased Feature Selection Method[J]. Expert Systems with Applications， 2014， 41（14）： 6371-6385.

[14]LEE S， PARK Y T，dAuriol B J. A Novel Feature Selection Method Based on Normalized Mutual Information[J]. Applied Intelligence， 2012， 37（1）： 100-120.

[15]FLEURET F. Fast Binary Feature Selection with Conditional Mutual Information[J]. The Journal of Machine Learning Research， 2004， 5： 1531-1555.

[16]KIRA K， RENDELL L A. The Feature Selection Problem： Traditional Methods and a New Algorithm[C]// Tenth National Conference on Artificial Intelligence. AAAI Press， 1992：129-134.

[17]KONONENKO I. Estimating Attributes： Analysis and Extensions of RELIEF[C]// European Conference on Machine Learning on Machine Learning. SpringerVerlag New York， Inc.， 1994：356-361.

[18]HALL M A. Correlationbased Feature Selection for Discrete and Numeric Class Machine Learning[C]// Seventeenth International Conference on Machine Learning. Morgan Kaufmann， 2000：359-366.

[19]DING C， PENG H. Minimum Redundancy Feature Selection from Microarray Gene Expression Data[J]. Journal of bioinformatics and computational biology， 2005， 3（2）： 185-205.

[20]KOLLER D. Toward Optimal Feature Selection[C]// Proceedings of 13th International Conference on Machine Learning. Morgan Kaufmann， 2000：284-292.

[21]崔自峰， 徐寶文， 张卫丰，等. 一种近似Markov Blanket最优特征选择算法[J]. 计算机学报， 2007， 30（12）：2074-2081.

[22]W Xindong， Y Kui， D Wei， et al. Online Feature Selection with Streaming Features[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2013， 35（5）：1178-1192.

（编辑：关毅）