• 研究动机
• 文章贡献
• 预备知识
• 本文方法
  • MCIFC：一种多类无关的特征构建方法
  • CDFC：一种多类相关特征构建方法
• 实验结果
  • 数据集和实验设置
  • 多特征构造与单特征构造对比
  • 多树 GP 对比单树 GP
  • filter 对比混合方法
  • 类依赖对比类独立
  • 非 GP 对比基于 GP 的特征构建
• 优点和创新点

作者单位：
School of Engineering and Computer Science, Victoria University of Wellington, PO Box 600, Wellington 6140, New Zealand

研究动机

在机器学习中，数据表示是影响机器学习和模式识别方法性能的关键因素。随着数据采集技术的进步，数据集的特征维度越来越高，从这些数据集中归纳模式对于许多学习算法来说具有挑战性。此外可能存在大量不相关和冗余的特征，可能会掩盖相关特征对显示数据隐藏模式的影响，从而减少整个特征集的表示。因此，对数据进行自动转换以获得更小、更有鉴别性的特征集成为有效的机器学习和模式识别的重要过程。
遗传规划(GP)是一种进化计算算法，其进化原理与遗传算法(GAs)的原理相同，但 GP 可以处理如树或图之类的更灵活的表示。基于树的表示为 FC 提供了一种自然的表示，构造的特征可以表示为树，在不需要预定义模型和大量训练数据的情况下，可以有效地自动构建更具判别性的特征，同时 GP 构造的特征比神经网络构造的特征具有更好的可解释性。在高维数据的情况下，增加单个构造特征不能获得不同的性能，另一方面，如何创建一组能够显著提高数据识别能力的少量构造特征仍然是一个挑战。为了深入了解这一任务，需要对使用GP构建多特征的不同方法进行研究。

文章贡献

本文旨在研究构建多特征的不同方法，并分析它们的有效性、效率和潜在行为，以揭示在高维数据上使用 GP 构建多特征的洞察力。本研究研究了三种多特征构建方法，包括两种使用多树表示的方法，即类独立 MCIFC 和类依赖 CDFC，以及 Neshatian 等提出的一种使用单树表示的方法 1TGPFC 构建类依赖特征。将使用常用的学习算法(包括 KNN、朴素贝叶斯和决策树 DT)对三种方法构建的特征的性能进行比较。结果表明多特征构建的性能明显优于单特征构建，类依赖的构造特征比类独立的构造特征具有更好的性能。

预备知识

下图给出了采用多树表示构造 m 个新特征的标准 GP 多特征构造算法的伪代码。

本文方法

MCIFC：一种多类无关的特征构建方法

MCIFC 使用多树GP来构建少量特征，这些特征与数据集的类别数成比例。这种设计是考虑到类的数量越多的问题就越复杂，可能需要更多的特征来表示数据。设 r 为构造比(例如 2 或 3)，在给定 c 为类数的情况下，使用 M=r×c 计算构造特征的总数 M。例如 r=2 时 MCIFC 为一个二类问题构建了 4 个特征，如下图所示。

为了从现有个体中创建新的个体，MCIFC 使用如下伪代码中描述的子树交叉和突变算子，每个遗传操作符被设计为只在亲本中改变或交叉一个构造特征。在一个操作符中操作多个特征可以增加搜索，但是具有较低的收敛性。GP 搜索空间大于 2^N，因为 GP 不仅要选择特征子集，还要用算子来组合它们。

MCIFC 使用权值 α 将分类精度和距离度量结合起来作为适应度函数，如下公式所示。

其中 Bal_Accuracy 是对转换后的训练集进行 K-fold CV(K=3) 得到的平衡精度的平均值。在不同的数据分割下 K-fold CV 重复 L(L=3) 次，因此建立 K × L，即 9 个模型来评价每个个体。这种评估方案用于避免过拟合，尽管它有点昂贵，但需要构造的特征数量很少。以 c 为类数，TP_i 为正确识别的实例数，S_i 为 i 类的总实例数，根据下面的公式计算平衡精度。

Distance 测度基于公式(4)计算，它用于最大化类之间的实例距离(Db)，最小化同一类内的实例距离(Dw)。设 S 为训练集，D_b 和 D_w 分别根据等式(5)和(6)进行近似。

其中 Dis(V_i, V_j) 为两个向量 V_i 和 V_j 之间的距离，用切卡诺夫斯基测度近似表示，如下公式所示。

CDFC：一种多类相关特征构建方法

CDFC 的表示与 MCIFC 类似，不同在于 CDFC 构造的每个特征都是类相关的，每个特性都与一个类相关联。下图展示了 r=1 的三分类问题的 CDFC 个体示例，CDFC 中从与 cf 所关联的类相关的原始特征的子集构建新特征 cf。CF1 可以将 Class1 的实例与其他类区分开来，CF2 和 CF3 分别关注 Class2 和 Class3。

t 检验用于衡量特征 f 与类别 c 的相关性，首先将 f 的值分为两组，一组属于类别 c，另一组不属于类别 c。然后使用如下公式来衡量其与c类的相关性，Rel_f,c 它不仅考虑两组均值之间的差异(t 值)，还考虑该差异的置信度(p 值)。若两组间差异不显著(p ≥0.05)则设为 0，否则取 t 值除以 p 值的绝对值。因此 Rel_f,c 的值越大，特征 f 与 c 类的相关性越强。对于每个 c 类，特征根据其 Rel_f,c 的值进行排序，将排名靠前的一半特征组成 c 类的终端集。

CDFC 的交叉操作符只能交换与同一类相关的特征的子树，因为 CDFC 中构造的特征依赖于类。为了加快适应度评估过程，CDFC 用信息增益(IG)代替 MCIFC 的分类精度(Bal_Accuracy)如下公式所示。AvgIG 是所有构建特征的平均 IG，GP 个体的大小 indSize 使用非常小的权重(10⁻⁷)添加进适应度函数中，以限制其对两个个体具有相同信息增益和距离的情况的影响。

AvgIG 基于如下计算，其中 f_max 是 m 个构造特征中 IG 最高的特征，加入 f_max 的 IG 来区分两个具有相同 IG 平均值的候选解。

特征 f 的 IG 根据如下公式中的无条件熵和条件熵 H 计算。

MCIFC 和 CDFC 在许多方面是不同的，体现在算法目标、适应度函数等方面。MCIFC 从整个原始特征集中选择特征来创建新特征，CDFC 从比 MCIFC 更小的特征集中选择特征，因此 CDFC 的搜索空间比 MCIFC 小。

实验结果

数据集和实验设置

实验使用了 8 个具有数千个特征到数万个特征的基因表达数据集，数据集的基本信息如下表所示。特征被标准化然后离散为 -1、0、1，分别表示基因的低表达状态、基线状态和过表达状态。如果特征值在[-0.5,0.5]区间内则设置为 0，如果分别位于区间的左侧和右侧则设置为 -1 或 1。由于每个数据集中的实例数量较少，使用 10 折交叉验证来生成训练集和测试集，每种方法在每个训练集上分别运行 50 次具有不同随机种子的运行。采用 Wilcoxon 统计显著性检验对各方法的结果进行比较，显著性水平为 0.05。

下表描述了实验中所有基于 GP 的方法的参数设置，函数集由 3 个算术运算符 (+,−,x) 和 max、if 函数组成。为简单起见，在终端集中没有使用常数值。使用系数 β 将总体大小设置为与问题的维度成比例，用于确定所构建特征数量的构建比 r=2，MCIFC 和 CDFC 的适应度权值 α 均设置为 0.8。

多特征构造与单特征构造对比

该实验用于验证构造多个特征比构造单个特征更好，由于基于聚类的 CGPFC 比标准 GP 更好，因此 CDFC 将与 CGPFC 进行比较。下表展示了使用 CDFC 50 次独立运行获得的构建特征与使用原始特征集和 CGPFC 构建的单个特征，在 KNN、NB 和 DT 上的平均测试精度，“+”或“−”表示对应的方法明显优于或差于 CDFC。

结果表明：

1. CDFC 构建的 4 个特征的识别能力远远高于原始的数千个特征，CDFC 可以构建数量很少且具有很高的判别能力的特征。
2. 与 CGPFC 构造的单个特征相比，CDFC 构造的四个特征也有助于获得更好或相似的分类性能。

多树 GP 对比单树 GP

CDFC 与 1TGPFC 进行比较，1TGPFC 使用单树GP来构建多个特征。实验中 CDFC 构建与 1TGPFC 相同数量的特征，两种方法使用相同的终端集和 GP 参数设置。下图显示了 50 次 1TGPFC 和 CDFC 的平均结果，可见使用 CDFC 构建的特征都明显优于使用 1TGPFC 构建的特征。

接着从 CDFC 和 1TGPFC 中选择在一次运行中的最差特征集进行比较，然后选择的构造特征集来转换数据集，基于两种方法的 7 个数据集的转换数据如下图所示。可以看出两种方法构建的特征都能很好地将不同类别的实例分组到单独的区域中，CDFC 在每个图产生的数据云比 1TGPFC 的数据云更紧凑，彼此分离。

filter 对比混合方法

此实验比较了不同的评价方法对 GP 性能的影响，MCIFC 使用 CDFC 的类相关特征的组合集，但仍然采用原来的混合评估方法，将这种变体称为 hMCIFC。从分类精度方面，下图为构建比为 2 的 hMCIFC 和 CDFC 50 次运行的平均结果。结果表明，使用由与特定类别相关的特征组成的终端集 CDFC 比 hMCIFC 取得了更好的结果。

从运行时间方面，下图展示了 hMCIFC 和 CDFC 完成单次运行的平均运行时间，可见 CDFC 的运行时间要快得多，证实了 filter 措施的有效性。

下图显示了两种方法的 GP 个体的平均大小，结果表明 CDFC 在 8 个数据集中有 6 个比 hMCIFC 具有更大的个体，这将需要更长的 CDFC 处理时间。然而 CDFC 在所有数据集上的运行时间都比 hMCIFC 短得多，说明每个构造特征的平均 IG 的计算时间仍然要短得多。

类依赖对比类独立

该实验将 CDFC 与 fMCIFC 进行比较，fMCIFC 与 hMCIFC 的方法相同，只是两者使用了相同的适应度函数。下图展示了 fMCIFC 和 CDFC 50 次运行的平均结果，可见 CDFC 构建的特征有助于获得比 fMCIFC 更好或相似的分类性能。表明 CDFC 只针对相应的类评估每个构造的特征，就可以构造出具有更强判别能力的特征。

为了进一步解释 CDFC 的有效性，对构建的特征进行了调查，下图显示了白血病数据集上 CDFC 进化的一个相对较小的GP个体。个体有三棵树，代表由 11 个特征组成的三个特征，使用这三个构造的特征集合的三种学习算法都获得了 100% 的测试准确率。

下图展示了使用该个体的白血病数据集的 11 个选定特征和 3 个构建特征的数据，从图中可以看出 feature X1999 有两个主要的值范围，分别对应于 class3 和其他两个类的实例。这证实了它的重要性，并解释了为什么 CDFC 选择它作为树 CF1 中的第一个特性。类似的 CF2 中出现的两个特性 X571 和 X3051 对于属于第 2 类的实例具有特殊的值范围。结合这些特征，CDFC构建的特征比原有的特征更加纯粹，如图中 CF1、CF2、CF3 三列所示，算法更容易从这些特征中生成一个好的模型。

非 GP 对比基于 GP 的特征构建

本节将 CDFC 与一些流行的非 GP 的方法进行比较，包括 PCA、LDA 和自编码器(AE)。为了更好地研究 CDFC 的性能，本实验添加了的四个数据集。下图展示了使用 CDFC 构建的特征的最佳结果与 PCA、LDA 和 AE 的结果。结果表明在所有数据集上，CDFC 的结果均优于 PCA、LDA 和 AE。

优点和创新点

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

1. 针对特征构造的问题，本文分别提出了一种类别相关和类别无关的基于 GP 的基础性的方法，值的基于该工作进行改进；
2. 对于类别相关的多树 GP 特征构造问题，本文使用信息增益来设计适应度函数，不仅分类性能更加，运行效率也很高；
3. 实验数据丰富有力，并从 5 个不同的方面来评价本文提出的算法的优势，说服力强。