单变量树的初始化与遗传算子详解

# 单变量树的初始化与遗传算子详解 ## 1. 初始化 在开始实际的进化过程之前，需要创建一个初始种群。个体应该具有多样性，并覆盖所有可能的解决方案范围，这样可以提高进化过程中探索的效率。 ### 1.1 决策树初始化的挑战 通常，初始个体是随机创建的，但对于决策树这种复杂的层次结构，从完全随机（且往往无用）的树开始是没有意义的。即使是中等规模的训练数据集，所有可能的决策树的搜索空间也非常巨大。特别是对于大数据应用，不恰当的初始化必然会显著减慢搜索速度，并可能导致进化方法的失败。此外，初始树生成算法的计算复杂度应该较低（或最多是可接受的）。 ### 1.2 简单偶极初始化方法 一种生成合理初始树的理性方法是使用自顶向下的方案，其中一个简单的变体是偶极初始化。偶极子是一对对象，如果这对对象中至少有一个特征的值不同，就可以用它来找到一个有效的测试，即分裂偶极子。 #### 1.2.1 递归过程步骤 1. 基于节点中可用的训练实例随机选择一个偶极子，并尝试生成一个测试。 2. 识别具有不同值的特征，并随机选择一个特征。 - 如果是标称特征，直接创建一个相等性测试（每个可能的特征值对应一个单独的测试结果）。 - 如果是连续值特征，创建一个不等式测试，需要额外抽取一个阈值来分裂偶极子，阈值范围从两个对象对应的特征值中得出。 #### 1.2.2 分类和回归问题的偶极子选择 - **分类问题**：只关注所谓的混合偶极子，即对象属于不同类别的偶极子。第一个对象可以完全随机选择，第二个对象则排除与第一个对象属于同一类别的对象。 - **回归问题**：情况稍微复杂一些，倾向于分裂预测目标值差异较大的偶极子。第一个对象随机选择，第二个对象根据目标值的计算差异对可用对象进行排序，然后应用类似于排名线性选择的机制来抽取，优先选择较长的偶极子。 递归分区在训练对象数量低于固定值（默认：五个）时停止，或者当节点中的所有对象属于同一类（分类）或具有相同或非常相似的目标值（回归）时停止。 ### 1.3 防止资源浪费的机制 由于快速但简化的方法生成的树可能会过度生长，特别是对于大型数据集，因此引入了最大初始树深度参数（默认：五），以避免广泛的决策树修剪并减慢进化归纳的第一阶段。 #### 1.3.1 子样本选择 为了防止在训练数据庞大时浪费资源，可以仅使用训练数据的小子集进行初始化。对于每个个体，随机选择训练数据的一个子样本，默认子样本大小为数据集的百分之十，但不超过 500 个实例。子样本的抽取采用分层方式，以确保子样本的代表性： - **分类数据**：保留全量训练数据集中的类别分布，通过按比例抽取每个类别的对象来实现。 - **回归数据**：尝试模仿因变量的分布。将原始训练数据集按目标值排序，分成固定数量的等份（默认：十份），然后从每份中随机选择相同数量的对象包含在子样本中。 #### 1.3.2 特征限制 类似地，当特征数量较多时，可以对每个个体考虑的特征集进行随机限制，默认限制为原始特征的百分之五十。 ### 1.4 多种优化准则初始化 为了提高进化算法的效率，不仅希望初始个体具有多样性，还希望它们合理。可以使用各种优化准则生成的树来初始化进化归纳： - **分类树**：可以使用以下局部分裂优度准则构建初始种群的一部分： - Gini 多样性指数 - 信息增益 - 增益比 除了构建所有测试基于同一准则的同质树，还可以构建每个节点选择测试的方法随机选择的初始树。对于上述所有准则，给定节点中的最佳测试是从为每个特征计算的最高评分测试中选择的。 - **回归树**：引入了类似的分裂优度准则概念，但需要优化其他度量： - 最小二乘法（LS） - 最小绝对偏差（LAD） 同样，初始种群可以包含同质和异质树。 - **模型树**：初始化时需要在所有叶子节点拟合模型。对于叶子节点中的简单线性模型，可以随机选择一个特征并使用该叶子节点中的可用训练实例拟合模型，也可以遍历所有特征选择使优化度量最小化的最佳模型。当允许使用多个线性模型时，可以将用于拟合模型的特征集限制为从根节点到叶子节点路径上测试中使用的特征，以降低计算复杂度。 ### 1.5 初始树修剪 生成的初始树可能会过度生长，这不利于进化，因为需要浪费大量计算资源来显著减小树的大小。因此，进行初始修剪以最大化初始适应度更为经济。在某些系统中，还可以采用受 M5 初始化启发的方法来初始化最复杂的模型树，即先生成未修剪的回归树，然后在所有节点中使用相应子树测试中的特征拟合多个线性模型，最后从叶子节点开始递归修剪树，直到估计误差不再减小。 以下是初始化过程的 mermaid 流程图： ```mermaid graph LR A[开始] --> B[创建初始种群] B --> C{是否使用偶极初始化} C -- 是 --> D[选择偶极子] D --> E{特征类型} E -- 标称特 ```