基于多参考点分解的多目标特征选择分类：静态和动态机制[通俗易懂]

原文题目：Multiple Reference Points-Based Decomposition for Multiobjective Feature Selection in Classifification: Static and Dynamic Mechanisms

摘要总结：

一、问题提出：

1高度不连续的帕累托前沿

2不平衡偏好

3部分冲突目标

二、使用方法：

在基于分解(MOEA/D)的多目标进化算法框架下，采用基于多个参考点的两种机制（静态和动态）分解方法，以解决上述特征选择的困难

三、两种机制的成就

静态机制减轻了分解对帕累托前沿形状的依赖性和不连续性的影响。动态的方法能够检测目标大多冲突的区域，并将更多的计算资源分配到检测到的区域。

四、实验比较和结论

与在12个不同分类数据集上的其他EMO算法相比，该分解方法发现了更多样化的特征子集，在超体积（度量帕累托前沿质量的一个指标）和反世代距离方面具有更好的性能。该动态机制成功地识别了冲突区域，并进一步提高了帕累托前沿的近似质量。

Introduction总结：

Pareto dominance-based算法：在有两个或三个目标的连续多目标问题上工作得很好，但在组合问题上却不行

decomposition-based EMO：工作原理是将一个多目标问题分解为许多单目标子问题，并重组结果。对组合问题有良好的搜索能力，多样性更好，更容易与局部搜索机制集成，并且可以更好地处理有许多目标或复杂的帕累托前沿的问题

基于分解的多目标进化算法(MOEA/D)：是基于分解的EMO算法的一个代表，标准的MOEA/D使用一组权向量将一个多目标问题分解为若干标量子问题。每个权向量定义了一个标量子问题，其最优解将是原问题的帕累托最优解。一组好的权向量可以产生合理的帕累托前沿近似。然而，在MOEA/D中定义一组适当的权重向量是一项困难的任务，因为它很大程度上依赖于帕累托前沿的形状。

研究目标：

本文的总体目标是开发一种新的MOEA/D策略来分解特征选择问题，期望获得不同的非支配特征子集，从而获得比使用所有特征更好的分类性能。在提出的分解策略中，使用多个参考点代替多个权向量。

1)MOEA/D-STAT和MOEA/D-DYN是否能够进化出特性子集，从而获得比使用所有特性更好的性能。

2)用多个参考点分解是否有助于MOEA/D提高解的质量，获得比多权向量分解更好的帕累托前沿近似。

3)新的分解策略是否能比四种基于帕累托优势的算法产生更多样化的特征子集。

4)动态策略是否能够识别冲突区域，进一步提高进化特征子集的质量。

Background总结：

A.多目标优化问题

多目标问题：

支配：

如果y优于z，即

称y支配z（假设值越小越好）

帕累托最优：如果一个解不被任何其他可行解所支配，则该解x*称为帕累托最优

帕累托前沿：所有帕累托最优解的集合在目标空间中形成了一个超平面（多目标为面，两个目标通常为线），即帕累托最优集的所有函数向量f（x）的集合

注：特征选择可以被认为是一个双目标最小化问题，其中特征的数量和分类错误率需要最小化。

B.MOEA/D

标准MOEA/D框架：

给o个目标问题，每个权向量有o个元素w = (w1,w2,…,wo)，且满足上述条件。其中N是预定义的正整数，权向量的个数为 $C_{N+o-1}^{o-1}$ (这里我不懂，希望大佬指点，应该是w有几种排列组合，但我不理解公式怎么来的)

可以应用其他策略来生成权向量。对于特征选择等双目标问题，N是子问题的数量，也是种群大小。有多种方法可以将多个目标聚合为单个标量函数，其中权重求和法、切比雪夫和基于惩罚的边界交叉法(PBI)是三种常见的方法（可参考下方链接）。在切比雪夫和PBI中，需要一个参考点来定义一个子问题的参考线。

多目标优化–MOEAD算法笔记_研行笔录的博客-CSDN博客_moead算法

C.特征选择的EMO相关工作

1.特征选择的第一个特征是其未知的帕累托前沿

帕累托前沿偏差对MOEA/D的影响。(a)平衡。朝向(b)f1和(c)f2。

图1的任务是最小化目标f1和f2，绿色的点表示权向量的最佳解。当帕累托前沿偏向于f1[图1(b)]或f2[图1(c)]时，使用一组均匀分布的权值向量不能很好地工作。在这两种情况下，一些权重向量都被浪费了，因为它们没有提供任何解决方案。如果浪费的权向量位于边缘附近，在帕累托前沿边缘可以得到更多的解。

一些研究试图基于区域密度更新权重向量，以保持种群多样性。然而，它们需要额外的计算成本来自适应地调整权重向量集。虽然它们在具有不规则帕累托前沿的数值问题上进行了测试，但没有一个问题像特征选择那样高度不连续。本文提出了一种新的权重向量，而不是自适应调整的特征选择分解机制，减少了对帕累托前沿形状的依赖，并很好地处理了前沿的不连续。

总结：权向量浪费问题

2.特征选择的另一个特征是其两个目标之间的复杂关系

两个目标：减少分类错误、减少选定特征数量

减少分类错误比减少选定特征的数量具有更高的优先级，这两个目标并不总是相互冲突的，在冲突区域上的帕累托前沿的某些部分比在非冲突区域上的其他部分更难近似

总结：分配资源问题

本文通过开发一种帮助MOEA/D处理特征选择特征的分解机制来解决上述局限性。该算法可以得到不同的非优势特征子集，具有更好的分类性能。

Proposed algorithm总结：

本节首先列出特征选择的特征，说明了将MOEA/D应用于特征选择时的困难。然后，它展示了如何使用多个参考点来分解一个特征选择问题。

A.特征选择的特征

分类错误率eRate=错误分类的实例数/实例总数（m），离散的，相邻值间隔为1/m

fRatio=所选特征数/原始特征数（n），离散的，相邻值间隔为1/n

因此，特征选择的帕累托前沿也是离散的

如果使用权值向量来分解特征选择，则必须仔细选择这些向量；否则，就会出现不对应于帕累托正面的任何解的向量，如图2(a)中的虚线所示

去除不相关或冗余的特征可以提高分类性能，这意味着这两个目标在某些区域并不相互冲突。但是，如果一个特征集中的所有特征都是相关的和互补的，那么删除任何特征都会降低分类性能删除了所有不相关/冗余的特性后，两个目标变得大多相互冲突。

也就是说，fRatio可能有一个阈值，超过这个阈值的两个目标是和谐的。图2(b)说明了每个点都是最好的解，具有相应的fRatio。可以看出，只有红点可以形成帕累托前沿，而所有绿点在阈值下都由解所支配。对于多目标算法来说，在fRatio低于阈值的区域分配更多的计算量将更有效。然而，这个阈值是依赖于问题的，并不容易识别。（我的理解是红色的点点是冲突较大区域，需要分配更多计算资源，绿色是两个目标的和谐区域）

B.具有多个参考点的分解

我们在fRatio轴上分配了一组R参考点。放置在fRatio轴上位置为refRatio的参考点代表一个精确使用（refRatio*n）特征的精度为100%(即0%eRate)的理想解，其中n是原始特征的总数。

上图蓝点点是一组参考点，利用多个参考点，将多目标特征选择问题分解为每个参考点的一个子问题，其大小最多为(nref=refRatio∗n)，每个子问题的搜索空间受nref的限制，都小于原问题。

在提出的分解中，具有较小nref(如n1)的子问题(S1)的搜索空间被具有较大nref(如n2)的子问题(S2)的搜索空间所覆盖。因此，这两个子问题s1和s2可能有相同的解决方案。然而，这不是一个问题，但实际上是有益的。另一方面，我们可以限制S2来考虑大小在范围(n1，n2]范围内的特征子集。这将分离S1和S2的搜索空间，所以它们不能有相同的解决方案。然而，对于分离的搜索空间，S2可能对近似的帕累托前沿没有任何解决方案，这可能会影响前沿的多样性。更重要的是，分离的搜索空间限制不同子问题之间的辅助，这是MOEA/D的一个基本属性。我们的分解并不能确保两个子问题有不同的解，但它满足上述两个理想的性质。

一个候选特征子集S对一个子问题的适应度函数设计如下：

|S|是所选特征的数量，该子问题的主要任务是最小化分类误差eRateS，这是多目标特征选择的第一个目标，由第一个分量表示，第二个分量是一个惩罚因素，以确保S中选定特征的数量不应超过nref，最后一个分量与减少所选特征数量这一目标有关。系数α用于控制第二个目标与第一个目标相比的优先级。α值越大，选择特征较少但分类精度较低。如果α设置为1，则这两个目标具有相同的优先级。由于减少分类误差是更重要的目标，所以α通常小于1。

在MOEA/D中使用多个参考点的想法已经在一些研究中得到了检验。然而，这些算法根据特定的机制，每一代都会更新参考点。我们的方法在进化过程之前将参考点放置在fRatio轴上。此外，该算法中不存在权值向量。这两个差异使得我们的算法比其他多参考点的EMO算法更简单。

C.参考点分配

1）静态分配：参考点被均匀地放置在fRatio轴上，并且在搜索过程中不会发生变化。具体来说，给定R个参考点，第i个参考点的位置为（i/R，0）。当邻居的数量为3时，（3/R，0）的邻域包括（2/R，0）、（3/R，0）和（4/R，0）。一般来说，我们期望相邻子问题的解是相似的

注：（0，0）位置上没有参考点

2）动态分配：fRatio轴被分成I个相同长度的间隔，即1/I。R参考点分为F个固定点和M个移动点(R=F+M)。F不动点在I区间上均匀分布，如图4中的绿色点所示。在开始时，M个移动点都位于第一个区间上，定位机制在扩展移动点的同时，尽可能避免两种参考点之间的重叠。

在由最大迭代次数和间隔次数之间的除法确定一定的迭代次数之后，移动点在下一个间隔上重新分配。例如，在图4中，在前十次迭代中，三个移动点位于第一个区间上。在接下来的十次迭代中，移动点将被重新分配到第二个区间，以此类推。第10、20、……迭代被称为边界迭代，因为在这些迭代中，移动点被重新分配。继续重新分配，直到算法检测到这两个目标可能不再冲突为止。

为了确定这两个目标在第i个区间内是否仍然存在冲突，我们将该区间内分类误差最小的解与前一个区间内的所有解进行比较。如果来自第i个区间的解被前一个区间的解所支配，则该算法假设这两个目标在第i个区间和任何区间内都不冲突。然后将移动点均匀地分配在第i个间隔之前的所有间隔上并且在进化过程完成之前，它们的位置不会被改变。如图4所示，在第三个区间内分配移动点后，算法发现第三个区间内由参考点获得的精度最好的解被第二个区间的一个解所支配，这表明，在第三个区间内，两个目标可能不会冲突。因此，该算法在第一和第二个间隔上分配所有移动点。

注：1.移动点被重新分配，要使其与固定点的重叠最小

2.当将一个参考点重新分配到fRatio轴上的一个新值时，该算法试图在参考点的先前位置为子问题找到的解决方案中保留尽可能多的信息。因此，该算法将参考点的特征子集尽可能接近前一个解决方案的特征子集。由于新位置需要不同数量的特性，因此必须将以前的解决方案中的特性子集“修复”（D中具体讲解）

D.修复机制

所有的进化算法都从当前的解决方案中创建新的候选解决方案。如果生成的候选对象是不可行的，搜索机制可能会浪费大量的搜索时间来探索搜索空间的无用部分。一种选择是识别和删除所有无效的候选人，但这可能会丢失候选人中包含的有价值的信息。另一种选择是通过将一个无效的候选人转换为一个紧密有效的解决方案来“修复”它，这具有保留候选人信息的优势，但如果修复机制不有效，可能会很昂贵。

当搜索机制创建一个大于nref的候选特征集S时，修复机制必须删除(|S|−nref)特征，以使其有效。该机制选择具有最低个体分类精度的(|S|−nref)特征（在算法开始时预先计算）。该过程如算法1所示。

在动态机制中重新分配参考点更容易创建无效的候选点，因为重新分配参考点意味着更改它的nref值。如果一个参考点被重新分配到一个较小的nref值，那么它当前的候选特征子集对于新的nref值来说可能太大，并且特征将通过上述相同的机制被删除。如果一个参考点重新分配到一个更大的nref，其候选特性子集仍然有效，但可能远小于新的nref值，这会限制多样性和探索新特征组合的能力。修复过程根据所有未选择的特征准确性对其进行排序，并依次将它们添加到候选特征子集，直到其大小达到nref，该过程如算法2所示。

E.修复重复的特征子集

重复的特征子集可能会导致低多样性和过早收敛。为了避免这种不希望出现的情况，将修复来自较大的参考点的所有重复集。由于在静态策略中，一个区间上的参考点密度不高，因此将未选择的特征随机添加到重复的子集中应该是非常有效的。然而，由于移动参考点的动态分配，在特定区间上的参考点更加密集。动态策略中重复的特征子集被随机生成的特征子集所取代。

F. 总体提出的算法

图5中，蓝色的部分是本算法与标准MOEA/D算法的主要不同之处，图5(b)中的绿色标记是动态和静态机制的区别，即移动参考点的重新分配。只有当算法尚未识别出阈值区间时才会执行重新分配。一旦找到阈值区间，M个移动参考点将被分配给冲突的间隔，并且不需要进一步的重新分配。这两种算法都使用了相同的差分进化(DE)交叉和突变算子，这是保持种群多样性的有效方法。

算法3显示了用于特征选择的静态多参考点MOEA/D(MOEA/D-stat)的伪代码。