发帖
雷达卡
使用进化算法实现大数据集的高效特征选择
towardsdatascience.com/efficient-feature-selection-via-genetic-algorithms-d6d3c9aff274?source=collection_archive---------5-----------------------#2024-01-12本文是探讨特征选择方法的系列文章的第二部分。若想了解前情，可参考第一篇内容。
在构建模型时，我们通常不会直接使用数据集中所有的特征，而是有选择地挑选出一部分子集。这种做法背后有多重原因——比如减少过拟合、提升模型解释性或加快训练速度。然而，当特征数量 N 非常庞大时，寻找最优特征组合会变得极其复杂。即使你有一个明确的目标函数来衡量组合优劣，暴力枚举所有可能的子集也几乎不可行，尤其当 N 超过几十个时。因此，我们需要依赖启发式搜索策略，如进化类算法，以更高效地逼近理想解。
问题的形式化如下：给定 N 个特征，目标是找到一个长度为 N 的二进制向量
[1, 1, 0, 0, 0, 1, ...]其中每个元素取值于
{0, 1}每一个分量代表对应特征是否被选中：0 表示剔除，1 表示保留。我们的任务就是找出使目标函数（或成本函数）最小化的那个向量。
在上一篇文章中，我们对比了传统方法序列前向选择（SFS）与一种高效的进化算法 CMA-ES。实验基于 Kaggle 房价预测数据集，经预处理后包含 213 个特征和 1453 条样本。所用模型为
statsmodels.api.OLS()优化目标为贝叶斯信息准则（BIC），其值越低表示模型拟合效果越好且惩罚了复杂度，因此需最小化该指标。
本篇将继续沿用相同的数据背景、模型设定与评估标准，转而介绍另一种强大的进化计算技术——遗传算法（Genetic Algorithms, GA）。
遗传算法简介
遗传算法的设计灵感源自生物界的自然选择与进化机制。在自然界中，个体能否生存并繁衍后代，取决于其基因对环境的适应程度。类似地，在特征选择问题中，我们可以将每一个可能的特征子集看作一个“个体”，其基因即为向量中的每一位（0 或 1）。
设想这样一个过程：从随机生成的一组初始个体开始，通过不断迭代“评估—选择—交叉—突变”的循环，逐步演化出越来越适应目标函数的个体群体，最终逼近全局最优解。
具体步骤如下：
- 初始化种群：首先创建一组固定规模的个体，每个个体是一个长度为 N 的二进制向量，各基因位随机设为 0 或 1。例如下图展示了一个 N=12、种群大小为 8 的初始种群结构：
[1, 0, 0, 1, 1, 1, ...]- 适应度评估：利用目标函数（如 BIC）对每个个体进行评分，这个分数称为“适应度”。适应度越高（或成本越低），说明该特征组合越优。
- 选择操作：根据适应度决定哪些个体可以进入下一代。常见的策略包括轮盘赌选择、锦标赛选择等。值得注意的是，虽然看似直观的排名选择法容易陷入局部收敛，但像随机锦标赛这类带有一定随机性的方法反而能在长期运行中保持良好的探索能力。遗传算法的核心优势之一正是在于维持足够的多样性以支持广泛搜索。
以下是一些常用的选择机制简述（详细资料见文末链接）：
- 轮盘赌选择（Roulette Wheel Selection）
- 锦标赛选择（Tournament Selection）
- 精英保留策略（Elitism）——确保最佳个体自动传入下一代
- 交叉（Crossover）：模拟生物交配过程，两个父代个体按照某种规则交换部分基因片段，生成新的子代。这一过程有助于组合已有优良基因块，促进优质特征模式的传播。如下图所示：
[1, 1, 0, 0, 0, 1, ...]- 突变（Mutation）：为了防止种群过早收敛并增加多样性，会在某些个体的基因位上引入随机变化。例如以很小的概率将某个 0 变为 1，或反之。这一步相当于自然界中的基因突变，能够帮助跳出局部最优陷阱。示意图如下：
{0, 1}完成上述流程后，新种群形成，算法重新回到评估阶段，开启下一轮迭代。整个过程持续若干代，直到满足终止条件（如达到最大迭代次数、适应度不再显著改善等）。
在整个演化过程中，关键在于平衡“探索”与“开发”——既要尝试新的特征组合（探索），也要充分利用已发现的优质结构（开发）。设计不当的选择与变异参数可能导致过早收敛或搜索效率低下。
综上所述，遗传算法提供了一种灵活且鲁棒的方式来处理高维特征空间下的组合优化问题。尽管它不保证找到绝对最优解，但在实际应用中往往能快速获得高质量的近似解，尤其适用于传统方法难以应对的大规模特征选择场景。
结合前文提到的 CMA-ES 与其他启发式方法，我们可以看到，进化类算法正在成为现代机器学习流程中不可或缺的工具之一，特别是在自动化建模与特征工程领域展现出巨大潜力。
在遗传算法中，可以采用多种停止准则来控制迭代过程。例如，当目标函数在连续若干代中未出现优化时，算法可自动终止；也可以设定一个固定的代数上限作为硬性停止条件；此外，基于时间的限制或等待外部触发信号等方式同样可行。无论采用哪种方式，最终应将历史上目标值最优的个体视为问题的近似解。
关于精英保留策略的一些说明：尽管使用锦标赛选择等随机选择方法时，当前代中最优个体因随机性而被淘汰的概率较低，但这种情况仍有可能发生。精英策略通过强制保留每一代中最优个体，确保其能够传递到下一代，从而避免了这一风险。这种机制虽然提升了收敛速度，但也可能使算法过早陷入局部最优，削弱全局搜索能力。需要再次强调的是，遗传算法的核心优势在于探索解空间。根据有限的实践经验来看，过度偏向利用（exploitation）往往不利于整体性能提升。不过，用户完全可以根据实际需求进行调整——如果你倾向于尝试不同的算法变体，遗传算法本身提供了丰富的可定制性和实验空间。
towardsdatascience.com/efficient-feature-selection-via-genetic-algorithms-d6d3c9aff274?source=collection_archive---------5-----------------------#2024-01-12遗传算法包含多个可调节的超参数，主要包括：
- 种群规模（即每代个体的数量）
- 变异概率（作用于每个个体的各个基因位）
- 交叉概率
- 选择策略（如轮盘赌、锦标赛等）
为了找到合适的超参数组合，一种常见做法是手动调试不同取值并观察效果。另一种更自动化的方式是将整个遗传算法流程嵌入到超参数优化框架（如 Optuna）中，由该框架负责搜索最优配置。然而，这种方法计算开销较大，适用于资源充足且追求极致性能的场景。
用于特征选择的遗传算法实现示例
以下是一个基于遗传算法进行特征选择的简单实现代码，使用了 deap 库。该库功能强大，但初学者可能需要一定学习成本。本示例力求结构清晰，便于理解与修改。
# to maximize the objective
# fitness_weights = 1.0
# to minimize the objective
fitness_weights = -1.0
# 复制原始数据为本地变量，避免外部干扰
X_ga = X.copy()
y_ga = y.copy()
# 排除常数列 'const'（非真实特征）
X_features = X_ga.columns.to_list()[1:]
# 清除之前定义的类，防止重复注册错误
try:
del creator.FitnessMax
del creator.Individual
except Exception as e:
pass
# 定义适应度和个体类型
creator.create("FitnessMax", base.Fitness, weights=(fitness_weights,))
creator.create("Individual", array.array, typecode='b', fitness=creator.FitnessMax)
# 清除旧的工具箱实例
try:
del toolbox
except Exception as e:
pass
toolbox = base.Toolbox()
# 属性生成器：生成布尔型基因（0 或 1）
toolbox.register("attr_bool", random.randint, 0, 1)
# 个体与种群初始化
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, len(X_features))
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
适应度函数的设计如下：
def evalOneMax(individual):
# 构建特征选择掩码：True 表示选中
cols_select = [True] + [i == 1 for i in list(individual)]
# 使用选定特征拟合线性模型
lin_mod = sm.OLS(y_ga, X_ga.loc[:, cols_select], hasconst=True).fit()
return (lin_mod.bic,) # 返回 BIC 值作为适应度（越小越好）
# 注册评估函数
toolbox.register("evaluate", evalOneMax)
# 注册遗传操作
toolbox.register("mate", tools.cxTwoPoint) # 两点交叉
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05) # 位翻转变异
toolbox.register("select", tools.selTournament, tournsize=3) # 锦标赛选择
# 设置随机种子以保证可复现性
random.seed(0)
# 初始化种群
pop = toolbox.population(n=300)
[1, 1, 0, 0, 0, 1, ...]代码实现了遗传算法（GA）的基本流程，包括个体与种群的定义，并集成了评估函数（即目标函数）、交叉、变异以及选择等操作策略。初始种群由300个个体组成，随后调用一个简化的进化循环——
eaSimple()该过程仅运行10代以简化演示。算法中设置了一个容量为1的名人堂（Hall of Fame），用于保存迄今为止发现的最佳个体，防止其在后续的选择或变异过程中被意外替换或丢失。
需要注意的是，名人堂机制并不等同于精英保留策略（elitism）。名人堂仅存储最优个体的一个非活跃副本，不参与后续演化；而真正的精英策略则会将最优个体直接带入下一代，确保其持续存在。
尽管上述实现逻辑清晰、易于理解，但其效率较低。在相关项目仓库中的Jupyter笔记本里，提供了一个更复杂且经过优化的GA版本，本文不再重复列出。但从该笔记本中执行优化后的完整代码，在经历1000代演化后，获得了如下结果：
best objective: 33705.569572544795
best generation: 787
objective runs: 600525
time to best: 158.027 sec
作为对比，特征选择前的基准BIC值为：
baseline BIC: 34570.166173470934
下图展示了在整个1000代演化过程中，各特征被选中的频率变化情况——热图从左至右表示代数演进，颜色越亮表示某特征在该代中被使用的概率越高。可以观察到部分特征始终受到青睐，一些特征很快被淘汰，还有一些特征的受欢迎程度随时间波动上升或下降。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/618e229be67fc6a6d949c05e038e3ff2.png
GA 优化历史
方法比较
我们对三种不同的特征选择技术进行了测试：SFS（序列前向选择）、CMA-ES（协方差矩阵自适应进化策略）和GA（遗传算法），并在目标值优化效果和计算效率方面进行对比。
实验环境为搭载AMD Ryzen 7 5800X3D处理器（8核16线程）的机器，操作系统为Ubuntu 22.04，Python版本为3.11.7。其中，SFS与GA通过启用16个工作线程的多进程池并行执行目标函数；而CMA-ES采用单进程运行——尝试并行化未带来显著性能提升，尽管理论上若进一步投入精力实现算法级并行，可能有所改善。
以下是各项指标的对比结果：
运行时间（越短越好）：
SFS: 42.448 sec
GA: 158.027 sec
CMA-ES: 48.326 sec
目标函数调用次数（越少越好）：
SFS: 22791
GA: 600525
CMA-ES: 20000
最佳目标值（BIC，越小越好）：
baseline BIC: 34570.1662
SFS: 33708.9860
GA: 33705.5696
CMA-ES: 33703.0705
分析可知，GA虽然在目标函数表现上优于SFS，并充分利用了多核资源来加速评估，但整体耗时最长，且目标函数调用次数远超其他两种方法，达到数量级以上的差距。通过进一步调整超参数，或许可提升其效率。
SFS运行速度快，得益于全CPU核心并行处理，算法结构简单，适合快速估算较优特征集合，是一种实用性强的轻量级方案。
若追求最优的目标函数值，CMA-ES表现最为出色，在精度上略胜一筹，同时保持相对合理的运行时间，是三者中综合性能最佳的选择。
本篇为关于特征选择系列的第二部分，也是最终章。如需了解背景与基础方法，请参阅第一部分内容。
说明与补充
所有图表均由作者原创制作。
完整代码示例可通过项目代码库获取。
房价数据集（MIT 许可证）：
github.com/FlorinAndrei/fast_feature_selectiondeap 库相关信息：
www.kaggle.com/c/house-prices-advanced-regression-techniques/data提供的一份免费遗传算法教程：
github.com/DEAP/deap相关资源展示：
www.tutorialspoint.com/genetic_algorithms/index.htm
京公网安备 11010802022788号
