李静星，杨有龙

西安电子科技大学 数学与统计学院，西安 710126

在生物信息学[1]、基因组学[2]、图像处理和文本分类等许多机器学习应用中[3]，越来越多的具有成千上万个特征的高维数据集成为普遍存在的事实[4]。高维数据集中的不相关和冗余特征会导致较高的计算复杂度[5]，严重降低分类精度。同时，高维数据集可能会导致“维数灾难”[6]。因此，处理实际问题中产生的大量高维数据集是一个重大的挑战。为解决这个问题，更好地提取高维数据中有效信息的主要方法是特征选择（Feature Selection，FS）。FS 通过某一准则从原始特征集中选出部分子集组成最优特征子集，然后再应用机器学习算法对数据进行分类分析。其目的是在不造成大量信息丢失的情况下，尽可能多地识别和删除不相关和冗余特征[7]。

传统的特征选择算法是基于信息衡量的单变量特征选择方法，一般是通过信息增益、信息增益率[8]、对称不确定性[9]等信息度量准则计算特征与类属性之间的相关性权值，然后对其进行排序，根据用户定义或给定的阈值选择前K个特征[10]。但是这里K的取值是很难确定的，并且这个方法不能排除冗余特征。近几年，经过国内外学者的研究表明，从本质上来讲，特征选择方法就是一个搜索最优子集的优化问题[11-12]。针对高维数据集的研究，改进后的特征选择算法分为两大部分，首先对原始特征集进行相关冗余分析，然后对输出的子集进行搜索评价得到最优特征子集，其流程图如图1所示。……