粒子群优化算法(PSO)之基于离散化的特征选择(FS)（一）

作者：Geppetto

在机器学习中，离散化(Discretization)和特征选择(Feature Selection,FS)是预处理数据的重要技术，提高了算法在高维数据上的性能。由于许多FS方法需要离散数据，所以通常的做法是在FS之前对数据进行离散化。此外，为了提高效率，特征通常单独（或单变量）离散。这种方案的原理是基于假定每个特征都是独立的，但是当特征之间存在交互时，这种方案可能不成立。因此，单变量离散化可能会降低FS的性能，因为在离散化过程中可能会因为特征之间存在交互而丢失部分信息。

在生物信息学、基因组学、图像处理、文本分类等不同领域的机器学习应用中，越来越多的高维数据集具有成千上万的特性。这些数据集通常有大量的冗余特征和不相关的特征，我们可以称之为噪声，这是对学习算法的新能有负面影响的。因此，特征选择(Feature Selection,FS)通常是一个关键的预处理步骤，用于选择许多机器学习任务的相关特性，例如分类和聚类。在本文中，我们将重点放在FS的分类问题上。尽管许多研究已经证明了在高维数据中使用特征选择的有效性，但是由于大的搜索空间和特征交互的存在，这任然是一个具有挑战性的研究。

除了特征选择，离散化也是对高维数据预处理的关键。首先，许多学习算法只适用于离散的数据。此外，通过离散化，可以忽略数据中一些微小的波动或可能的噪声。这样，离散化就有助于提高学习算法的有效性和效率。最后，因为离散数据比联系数据更紧凑，那么需要的内存就相对较少，从而提高了学习算法的效率。因此，特征选择和离散化通常用于提高分类性能，同时也对优化计算时间和存储空间方面有提升。

虽然目前有很多离散化的方法，但是最常用的离散化方法是单变量法。在一个时间内对某一个特征离散，当不存在特征交互时，这个方法是非常有效的。但是当这个假设不成立时，我们需要同时对多个特征进行离散化。然而，对变量离散化的时间复杂度会高很多，因此，我们需要一个更强大的搜索技术用于多变量离散化，尤其是在高维数据上。

此外，在实际应用中，通常将单变量离散化应用于FS是许多FS方法的要求。然而，单变量的离散化可能会破坏特征交互的信息。因此，可以通过将离散化和特征选择两个过程合并为一个单独的过程来获得更好的效果。粒子群优化(PSO)是由Eberhart and Kennedy提出的一种元启发式算法。PSO模仿鸟群中发现的社会行为。许多FS方法已经被提出使用不同类型的PSO算法，如上一篇所介绍的连续PSO和二进制PSO(BPSO)。这些方法的结果显示了PSO在那些领域的潜力，然而，PSO还并没有被用于离散化。

在最近的一种方法[evolve particle swarm optimization(EPSO)]中，我们推荐使用一种被称为“bare-bones” PSO (BBPSO)的PSO派生方法来同时离散和特征选择，原因如下：在PSO中，PSO通常是一个N维向量，对应于N个特征，每个值的范围都是[0,1]。如果它大于一个预定的阈值，则选择相信的特征，反之亦然，而不去管它与阈值相比有多大或者多小。因此，两个不同的进化向量可能会产生相同的特征子集。另一方面，在离散化中，一个稍微不同的进化点可能会导致一个不同的离散特征。因此，找到一个好的切点需要一个微调的搜索机制，可以在BBPSO中找到。在这个派生的PSO版本中，使用一个高斯随机发生器对新位置进行采样，中心是个体最佳位置(pbest)和它的邻居的最佳位置(gbest)和它们之间的距离的标准偏差。

EPSO使用了BBPSO来实现离散化和FS。每个特征都有一个转折点。由于一个切点可以是特征范围内的任何值，离散化的可能解决方案的数量要比FS大得多。因此，从中得到的基于熵的切割点被用作缩小搜索空间的初始或潜在的切割点。该方法已取得了良好的效果。但是，由于这种表示方法，搜索空间对于BBPSO来说仍然太大，无法获得更好的性能。为了缩小搜索空间，本文提出了一种利用BBPSO的潜在粒子群优化算法，该方法可以在潜在的好算法中选择合适的分界点。提出了一种新的适应度函数和缩放机制，以提高该方法的性能。

（一）研究目标

本文针对高维连续数据，提出了一种将离散化和FS相结合的新方法。为实现这一目标，提出了一种新的粒子在BBPSO中的表示方法。虽然EPSO使用BBPSO直接为每个特性发现了一个切点，但新的方法称为PPSO，它允许BBPSO自动为离散化和FS选择潜在的良好的切点。与使用全特征集、离散化和FS的两阶段方法和高维数据的EPSO进行了比较。我们的具体研究目标包括以下内容：

• 如何在单个过程中进行多变量的离散化和特征选择，提高特征集的识别能力。
• 与使用全特征集相比，PPSO所选择的特征是否能得到更好的分类精度。
• 在精度、特征子集大小和计算时间方面，PPSO是否比相应的“两过程”方法表现得更好。
• PPSO是否比EPSO更有效。
• 是否PPSO的分类性能都优于传统方法。
• PPSO的结果是否适用于其他的学习算法，而不是包装方法(wrapped method)。

虽然本文提出的新方法(PPSO)和现有的方法(EPSO)是通过离散化来解决FS的，但它们的主要组成部分，即表示方法和评价方法，都是非常不同的。在进化计算(EC)技术中，表征在方法的有效性和效率方面起着重要的作用。一个好的表示可以减少搜索空间的大小，这在EC方法中通常是非常大的。仅FS问题的搜索空间已经非常大，因此将其与离散化相结合会导致更大的空间。因此，本文提出了一种新的表示方法，使搜索过程更加有效。本文的另一个贡献是一种新的适应度函数，它结合了包装(wrapped)和过滤(filter)措施，以综合两种方法的优点。然而，提出的混合方法是为了更好地评估候选方案，而不需要使用基于相同距离度量的包装器和过滤方法来支付更多的计算成本。