526互联

Paper Reading: A pareto-based ensemble of feature selection algorithms

发布时间 2023-08-14 21:41:05作者: 乌漆WhiteMoon

目录

Paper Reading 是从个人角度进行的一些总结分享，受到个人关注点的侧重和实力所限，可能有理解不到位的地方。具体的细节还需要以原文的内容为准，博客中的图表若未另外说明则均来自原文。

论文概况 详细
标题 《A pareto-based ensemble of feature selection algorithms 》
作者 Amin Hashemi, Mohammad Bagher Dowlatshahi, Hossein Nezamabadi-pour
发表期刊 Expert Systems with Applications
发表年份 2021
期刊等级 中科院 SCI 期刊分区(2022年12月最新升级版）1 区，CCF-C
论文代码 未公开

作者单位：

  1. Department of Computer Engineering, Faculty of Engineering, Lorestan University, Khorramabad, Iran
  2. Department of Electrical Engineering, Shahid Bahonar University of Kerman, Kerman, Iran

研究动机

很多真实数据集中往往包含不相关和冗余的特征，这些不提供有益的信息，而且使得机器学习算法效率降低、性能变差。特征选择是处理该问题的有效方法，原理是从数据集中选择有用的特征子集，去除不相关和冗余的特征。现有的特征选择方法有监督和搜索两种策略，其中监督的方法可以分为监督、无监督和半监督三种，搜索策略可以分为：过滤、包装和嵌入三种。最近还有一种称为集成特征选择的新方法，该方法将几种特征选择方法的输出结合，得到最终的特征子集。每一种特征选择算法都可以在特征子集空间中找到被认为是局部最优的特征子集，不同方法的多样性使得集成方法比只使用单一方法更好。

文章贡献

本文将集成特征选择问题建模为具有两个目标的帕累托优化问题，提出一种类型的异构集成特征选择算法 PEFS。首先采用两种聚合方法对四种不同 FS 方法得到的结果进行组合，接着使用双目标优化来评估这些结果，最后根据非优势特征在双目标空间中的拥挤距离进行排序。该方法平衡了关联度和冗余性两种不同的 FS 方法，对相关性最大、冗余最少的特征给出更高的排序。实验使用了 7 个真实的数据集，将 PEFS 与一些基本的 FS 算法和集成 FS 算法进行比较，结果表明本文提出的方法在 acc、F1 和运行时间上比其他方法更好。

相关概念

集成特征选择

集成特征选择是组合多个模型进行特征选择，通过不同方法的多样性来提高特征选择的效果。集成 FS 方法可以分为同构集成和异构集成两种。同构集成将数据划分为多个分区进行特征选择，将所有分区的选出的特征子集合并，得到最终的特征子集。异构集成是对相同的数据执行多种特征选择方法，并将它们的结果汇总以找到最佳特征子集。

帕累托最优

在多目标优化 MOP 问题中，从不同目标之间的冲突种得到的一组权衡解称为帕累托最优集。多目标优化问题可以由如下公式所示，其中 n(n≥2) 为优化的目标个数，x=(x1,…,xk) 为决策变量向量，S 表示可能解的集合，F(x)=(f1(x),f2(x),⋯,fn(x)) 为需要优化的目标向量。当目标空间包含两个目标时为双目标优化问题，具有三个以上目标的优化问题称为多目标优化问题。本文将 MOP 设置为最小化问题，因此 F 可以定义为估算每个解决方案质量的效益函数。

帕累托优势由如下公式所示，对于目标向量 u=(u1,……,un) 和占主导地位的向量 v=(v1,…,vn)，当且仅当 v 的任何分量都小于 u 的对应元素且至少一个元素严格小于 u。帕累托优势是衡量 MOP 的一种方法，用于说明一个解决方案何时优于另一个解决方案。

帕累托最优集是上述公式中的一个解 x∈S，若 x'∈S没有解满足 x'<x，则 x* 是最优解。所有满足该条件的解都是帕累托最优集的成员，帕累托最优前沿是将帕累托最优集在目标空间上的投影。

非支配排序

每个解基于优势关系在空间中被分配到不同的前沿，接着使用非支配排序寻找帕累托最优解。设解的数量为 P，则这些解可以被分类到 K 个前沿上，下图展示了使用非支配排序将 13 个解排序到双目标最小化问题的 4 个前沿的例子。首先所有的非支配解分配在 F1 上，P−F1 中的非支配解分配给 F2，重复这个过程直到所有的解都被分配到对应的前沿上。

本文使用的非支配排序算法为高效非支配排序顺序策略(ENS-SS)，该算法所有解的前沿数不是作为一个整体确定的，而是将可行解逐一应用于后续的可行解。ENS-SS 排序的优点是可以避免重复比较，从而降低计算复杂度。
首先将第一个解分配给前沿 1，将下面的解与第一个解进行比较。如果它们不相互支配，则它也被分配到前面 1，否则分配到前沿 2 上。如果第二个解优于第一个，那么第一个解决方案被移到前沿 2 上，第二个解决方案分配到前沿 1 上，反之亦然第二个解决方案被分配给前沿 2。下面的伪代码给出了 ENS-SS 的算法流程：

拥挤距离

一个解的拥挤距离表示其周围其他解的密度，每个目标取该点两侧的最近点的平均距离，构成的几何体中不包括其他店。例如下图所示，点 s 与 s-1、s+1 构成一个长方形，而 a 和 b 两点由于不是靠近的，所以距离为无穷大。将计算距离归一化，取同一个帕累托前沿上的最大距离和最小距离之差作为拥挤距离。

本文方法

FS 方法在特征子集空间中找到可以被认为是局部最优的特征子集，通过 FS 算法的集成输出可以提高鲁棒性和学习精度。本文提出的算法是一种 filter 类型的异构集成特征选择算法，通过使用四种 FS 方法的集合来将集成 FS 问题建模为基于帕累托的优化过程。算法的流程如下伪代码所示：
首先定义一个空向量 w 作为特征排序向量，接着对数据集使用四种 FS 方法 Fisher-Score、MIC、LLCFS、CFS 应用于数据集，得到 4 个特征排序向量（R1~R4）。选择这些方法是基于冗余和基于相关性的 FS 方法组合的思想，实现相关度最高、冗余度较低的特征子集。使用 CFS 和 LLCFS 方法作为基于冗余的方法，使用其他 FS 方法作为基于相关性的方法，每个排序向量表示基于以下 FS 方法的特征的排序，如下公式所示：

接着构造 P 矩阵作为决策矩阵，其中每一列表示从上述方法获得的向量，行表示特征。然后计算 P 矩阵大小，其中 m 为行数(特征)，n 为列数(FS方法)，使用如下公式所示：

然后根据 P 矩阵为每个特征分配其相应的秩，以构建如下公式所示的决策矩阵 D。例如如果特征 8 是根据 R1 的最高秩特征，则 d18＝1 表示特征 8 已经由 FS1 分配了排为第 1。

将优化问题的目标函数定义为最小化方法，目标函数有均值、最小值两个。将每个特征的平均秩值为的第一个目标，按照如下公式计算 D 矩阵每行的平均值：

使用每个特征的最小秩值作为第二个目标，按照如下公式计算 D 矩阵每行的最小值：

计算出两个目标的值后，执行双目标的非支配排序，并为每个特征分配帕累托数。使用第二个度量来对具有相同帕累托数的特征进行排序，在双目标空间中计算每个特征的拥挤距离，并将其存储在向量 d 中。最后将特征的拥挤距离归一化到区间 [0,1]，然后基于以下公式为每个特征设置分数：

完成后就可以根据 R 中的值按升序对特征进行排序，将结果存储在 w 向量中，用户可以据此选择所需数量的特征。下图展示了一个具有 20 个特征和 3 个实例的样本数据集展示算法的步骤：

实验结果

数据集和实验设置

将本文方法与使用的四种 FS 方法 Fisher-Score、MIC、LLCFS、CFS 进行比较，评价指标为 accuracy 和 F1。使用 7 个真实数据集来测量这些方法的性能，下表为数据集的详细信息。

所有比较方法都使用最优的参数，使用 KNN 分类器比较算法的分类性能，近邻数量设置为 5。数据集按照 6:4 分为训练集和测试集，每种方法重复运行 30 次计算评价指标平均值。

与 FS 方法比较

下面两张图显示了几种 FS 方法的 accuracy 和 F1 比较情况，图中的横轴表示选定特征的数量，纵轴表示比较标准。


下表最后一行显示了 7 个数据集上 PEFS 与其他方法的 Friedman 检验结果：

根据检验结果，将本文方法与其他方法的总体胜利/平局/失败次数在下表中展示，结果表明本文方法在各评价指标上均优于其他方法。

与集成 FS 方法比较

对与集成 FS 方法的比较数据使用 Friedman 检验，结果汇总于下表中，结果表明本文方法在各评价指标上均优于其他方法。

和各个集成算法的运行时间如下表所示，可见本文算法的效率相比于其他集成 FS 算法高。

优点和创新点

个人认为，本文有如下一些优点和创新点可供参考学习：

  1. 通常 FS 使用单一的算法，本文的研究聚焦于多种 FS 方法的集成，取得了比单一方法更好的效果；
  2. 将 4 种不同的 FS 方法使用两种不同的目标函数进行聚合，使用帕累托优化对特征进行排序，提供了一种对特征选择进行优化的思路；
  3. 算法简洁而高效，文中对算法的说明、公式和图例也都很清晰。