基于F-score的特征选择算法在多分类问题中的应用

秦喜文, 王 芮, 于爱军， 董小刚*, 张斯琪

(1.长春工业大学 数学与统计学院， 吉林 长春 130012;2.北京首钢国际工程技术有限公司， 北京 100043)

0 引 言

为了提高机器学习在分类问题上的准确性和效率，一些研究者已经开始将特征选择算法与机器学习算法相结合。通过选择重要的相关特征来降低计算成本，使得计算过程更加准确和易于理解。

特征选择可以通过过滤器、包装器或嵌入方法进行。过滤器方法为每个特征分配一个重要值以构建一个排名，得分最高的特征是与数据类最密切相关的。这种方法可以使用与算法无关的技术，如F-score[1]，以及基于信息度量的数据驱动变量选择方法，如联合互信息和正则化互信息等[2-3]。包装器方法根据搜索算法确定的给定特征子集中分类器的性能来选择特征。选择分类器后，若干特征子集将用作分类器的输入数据，然后选择精度最高的特征子集。嵌入式方法将特征选择融合在模型训练的过程中，比如决策树在分枝的过程中，就是使用嵌入式特征选择方法，其内在还是根据某个度量指标对特征进行排序。 同时，随机森林中的特征重要性排序也是嵌入式方法的一种。

机器学习已有近70年的发展历史，随着信息技术的不断发展完善，机器学习也被广泛应用于各个领域。计算机利用机器学习算法，通过模拟人类的行为不断提高机器的工作效率。自1949年，Hebb开启机器学习的第一步后，机器学习经历数十年的发展不断进步。1984年，Breiman L L[4]提出了一个著名CART算法，也就是通常所说的决策树(回归树)算法，该方法通过使用简单的规则可以在现实生活中找到更多的应用。支持向量机(SVM)方法最初由Vapnik V等[5]提出用于二值分类，其基本思想是寻找两个并行支持向量之间具有最大裕度的最优分离超平面。2001年,Brianman L[6]提出随机森林模型，随机森林在大量应用中证明了其在理论和实验上对过拟合的抵抗性。2013年,Anaissi A等[7]提出迭代随机森林，能够识别出特征的高阶交互作用,同时能够保证迭代随机森林有很好的预测能力[8]。

文中利用Márcio Dias de Lima等[9]提出的新的基于F-score的特征选择方法，将其与多个机器学习算法相结合用于多分类问题中，使用分类误差为评价指标验证它的鲁棒性。

1 机器学习方法

1.1 决策树算法

决策树(CART)算法通过简单的图像表达，就像树一样，所以被称为决策树。一个决策树在构建时，通过将数据划分为具有相似值的子集来构建出一个完整的树。决策树上每一个非叶节点都是一个特征属性的测试，经过每个特征属性的测试，会产生多个分支，而每个分支就是对于特征属性测试中某个值域的输出子集。决策树上每个叶子节点就是表达输出结果的连续或者离散的数据。

1.2 支持向量机

支持向量机(SVM)方法最初由Vapnik V等[5]提出用于二值分类，与其他机器学习方法相比，它是一种很有前途的机器学习技术。SVM在统计学理论中有其基础，该方法是基于结构风险最小化原则(SRM)。支持向量机解决了一个二次规划问题，确保一旦得到最优解，它就是唯一(全局)解。

1.3 随机森林

随机森林(RF)算法将大量决策树聚集在一起，并将它们一起用于预测最终结果。随机森林中每棵树都按照规则自由生长，并且不需要对决策树进行剪枝。随机森林作为Bagging的改进方法，拥有极强的泛化能力。

1.4 迭代随机森林

迭代随机森林(iRF)的基本思想是在随机森林基础上,通过对选定的特征进行“迭代重新赋权”，得到一个带有特征权重的随机森林，然后利用泛化的随机交叉树作用于带有特征权重的随机森林上，进而识别出特征的高阶交互作用，同时保证迭代随机森林也有很好的预测能力。

2 特征选择

2.1 随机森林计算变量重要性

R软件中的importance()函数可以被用于随机森林算法中，用于度量变量的重要性。Mean Decrease Accuracy(平均减少度)表示在没有该对应特征的条件下分类准确度下降的程度，即数值越大，说明该特征在分类效果中起到的作用越大;反之数值越小，表示该特征在分类效果中起到的作用越小。

2.2 条件互信息

基于互信息的特征选择算法是通过使用互信息寻找与类高度相关而特征之间低冗余的特征。其中，条件互信息(CMI)测量给定第三个变量时,两个变量之间的条件依赖性[10]。

设

X=(x1,x2,…,xn),

Y=(y1,y2,…,yn),

Z=(z1,z2,…,zn)

是三组离散随机变量。条件互信息(CMI)测量给定第三个变量时，两个变量之间的条件依赖性。给定Z的变量X和Y的CMI定义为

I(X;Y|Z)=

(1)

式中：I(X;Y|Z)----变量X和Y给定变量Z共享的信息量。

2.3 基于F-score的特征选择算法

F-score作为一种简单的方法，由Chen Y W等[1]于2006年提出，该方法用来衡量两类数据的区别。给定特征向量xi,i=1,2,…,k，如果正负实例的数目分别为n+和n-，则第i个特征的F分数定义为

F(i)=

(2)

分子----正负集合之间的差异；

分母----两个集合。

F值越大，该特征越有可能具有区别性。

F-score的一个缺点是不能揭示特征之间的相互关系。因此，Márcio Dias de Lima等[9]在此基础上提出了一种新的变量选择方法，分别求因变量标签的平方距离之和除以对应实例的样本方差，揭示了特征在不同标签数据集下的重要性。

同样给定特征向量xi,i=1,2,…,k，如果正负实例的数目分别为n+和n-，则以下方程定义第i个特征的正负样本排序,

(3)

等式的分子是正负样本第i个特征均值与总体样本第i个特征均值之间的平方距离，而分母分别表示正负样本的样本方差。

特征排序(FR)由下式获得，其中分数越高，特征越重要,

(4)

文中将该方法拓展应用于多分类问题中。给定一个特征向量xi,i=1,2,…,k，因变量xj,j∈i,j≠i，假设因变量的所有标签用m∈R表示,则由以下方程定义第i个特征的标签样本排序,

(5)

注意，上述式子的分子是第i个特征中属于m类的均值和第i个特征总体均值之间的平方距离，分母分别匹配因变量标签的样本方差。

特征总体排序由下式获得，其中分数越高，特征越重要,

(6)

3 实证分析

3.1 数据来源

文中以UCI数据库中的5个公开数据为例来验证方法的可行性，为提高分类精度，在进行实验之前对部分数据预处理，包括对Whitewine-quality数据集第3类～第5类数据划分为bad类，第6类数据划分为mid类，第7类～第9类数据划分为bad类,以及对Waveform中某些无意义的变量进行删除，最终剩余21个变量用于实验。数据集的具体描述见表1。

表1 数据集基本信息

3.2 交叉验证

在建模过程中,为了避免追求高准确率而产生过拟合的情况，通常将原始数据集划分为训练集和测试集，从而使得模型在样本外的数据上预测准确率也有不错的精度。但是，划分出的训练集、测试集的不同会使得模型准确率产生明显的变化。因此,为了保证输出结果的可靠性，使用k(k=10)折交叉验证来评估算法性能。文中为保证数据的平衡性，对每个特征的数据采取k折随机分割，每个特征选取一个子集组成具有n个随机特征子集的训练集。这样既保证了数据的平衡性，又保证了模型训练效果的准确性。

文中所使用的十折交叉验证数据分割方法如图1所示(每次选择的测试集数据由深色部分标出)。

图1 交叉验证流程

通过十次交叉验证所得结果的平均值报告了所提出变量选择方法与一些机器学习算法相结合的测试精度。

用于获得最佳精度的参数见表2(文中使用的特征选择方法简写为Fs)。

表2 模型参数配置及分类结果

从测试分类误差角度来看，基于F-score的特征排序方法与其他机器学习方法相结合，在多分类问题中能够在选择较少变量的情况下达到与未进行变量选择或与其他变量选择方法相差无异，甚至更好。

3.3 结果分析

从表2可以得到以下分析结果：

针对Iris数据集，分类精度最好的方法为Importance+iRF和Fs+iRF，分类误差为0.026 7，其次为Importance+RF和Fs+RF，分类误差为0.033 3。分类最佳与次佳的误差相差0.006 6。

针对Wine数据集，分类精度最好的方法为Importance+SVM和Importance+RF，分类误差为0.016 7，但相比于Importance+RF方法，Importance+SVM只使用了5个变量便达到了最佳分类效果。其次为iRF、Importance+RF和Fs+iRF，分类误差为0.017 0，但相比于其他两种方法，Fs+iRF只使用了7个变量以及一次迭代，分类最佳与次佳的误差相差0.000 3。

针对Glass数据集，分类精度最好的方法为CMI+iRF，误差为0.207 0，其次为iRF、Importance+iRF和Fs+iRF，分类误差为0.214 0，分类最佳与次佳的误差相差0.007 0。

针对Whitewine-quality数据集，分类精度最好的方法为基于iRF的四种方法，误差为0.259 0，其次为RF和CMI+iRF，分类误差为0.263 0，分类最佳与次佳的误差相差0.004 0。

针对Waveform数据集，分类精度最好的方法为Fs+SVM，误差为0.132 4，其次为SVM方法，分类误差为0.137 4，然而结合Fs的SVM方法只使用了16个变量,即达到了最佳效果。

通过对比不同特征选择方法与决策树结合的分类效果可以看到，虽然基于F-score的特征排序方法在部分数据集的表现不如使用随机森林计算变量重要性的方法，但两种方法的分类误差差距不是很大。

通过对比不同特征选择方法与SVM结合的分类效果可以看到，虽然基于F-score的特征排序方法在Iris、Wine和Whitewine-quality数据集的表现不如使用随机森林计算变量重要性的方法和CMI方法，但针对这些数据集而言，其与最优方法之间的差距仅为0.006 7、0.000 7和0.005 7，可以说方法之间的分类误差差距极小。换个角度可以观察到，同样的数据集，基于F-score的方法在Iris和Whitewine-quality数据集上所使用的特征数相对较少。可以说该方法能够与其他方法相媲美。

通过对比不同特征选择方法与RF结合的分类效果可以看到，基于F-score的特征排序方法在Iris和Waveform数据集上的表现优于其他方法，在 Wine、Glass和Whitewine-quality数据集上的表现虽然不是最好的，但分类误差与其他方法相差不大。尤其在Whitewine-quality数据集，该方法与最优方法之间的差距仅为0.005 7，且使用的特征数比全变量方法要少。

通过对比不同特征选择方法与支持向量机结合的分类效果可以看到，基于F-score的特征排序方法在Iris、Wine、Whitewine-quality和Waveform数据集的表现最佳，在Glass数据集上的表现稍逊色于条件互信息方法，但分类效果相差甚微。反观Whitewine-quality数据集，模型的精度都是在全变量条件下达到最优，可以断定这两个数据集之间的特征相关系数较小，特征区分度较大。

综上所述，与支持向量机、随机森林和迭代随机森林相结合的特征选择方法都优于与决策树相结合的方法，尤其是基于F-score和基于随机森林计算变量重要性特征选择方法。特征选择与迭代随机森林方法相结合时能够显著提高模型精度。同时基于F-score的特征选择方法与机器学习方法相结合能够达到较好的分类效果，可以在选择少数变量的同时达到与传统方法无异的效果，甚至是更好的分类精度。F-score通过分别计算每个特征在各个类别标签下的分数，然后计算这些分数之间的平均值，揭示了特征之间的相互关系。相比之下，条件互信息特征选择方法在低维小样本数据中的表现就没有那么出色。

4 结 语

利用Márcio Dias de Lima等[9]提出的新的基于F-score的特征选择方法，将其与多个机器学习算法相结合用于多分类问题中，使用分类误差作为评价指标验证它的鲁棒性。该变量选择算法的每个特征得分都是相对于因变量的标签分别计算的。然后，计算标签对应分数的平均值，提供最终排名用于机器学习模型中。主要研究内容包括以下几个方面。

1)将该方法与未进行变量选择的模型(CART、SVM、RF、iRF)使用随机森林importance函数所选特征相结合的机器学习模型,以及使用条件互信息(CMI)方法选特征相结合的机器学习模型相比较，验证了该变量选择方法在多分类问题中的有效性。

2)文中使用十折交叉验证数据筛选框架用于模型效果对比，这样既保证了数据的平衡性，又保证了模型训练效果的准确性。

3)实验结果表明，该方法能够使用比原始数据集更少特征，并产生良好分类结果，尤其在与迭代随机森林方法相结合的情况下，能够显著提高模型分类精度。

F-score方法是一种过滤器方法，能够为每个特征分配一个得分，以构建特征排名，这种包括特征排序的方法是特别吸引人的。得分最高的特征是与因变量最密切相关的特征，反之，得分较低的特征则表示与因变量关系较小。这种过滤器方法使用与算法无关的技术比较简单，易于运行和理解。

文中仍存在一些不足与值得改进的地方，如文中所使用的基于F-score的特征选择方法是一种单变量特征选择方法，需要使用穷举方法测试每个所选择的特征子集的分类效果，虽然难度不高，但十分费时耗力。一种自适应的特征子集选择方法有待被开发应用于基于F-score的特征选择算法中。其次，文中只选用了四种机器学习方法，更多的方法有待被发掘与应用。针对不同的数据特征，选择合适的分类方法也是分类问题的关键。