基于改进的遗传算法的特征选择方法在冠心病检测中的应用

李 勇， 秦彩杰

（三明学院信息工程学院，福建三明365004）

冠心病是由冠状动脉器质性狭窄或阻塞引起的心肌缺血缺氧或心肌坏死的心脏病[1].冠心病具有较高的发病率和致死率，并呈现年轻化趋势，现已成为全球范围内威胁人类生命和健康的高危病种.因此早期的筛查诊断对于冠心病的有效治疗非常关键[2].常用的冠心病临床检测方法包括心电图检测（常规心电图、运动负荷心电图、动态心电图等），生化检测，超声检测，多排的螺旋CT，冠脉造影等[3].其中冠脉造影是全球医学界公认的诊断冠心病的“金标准”，但其检测费用昂贵，是一种有创诊断技术，且具有副作用[4].而其他一些常用的冠心病诊断技术受到费用、技术条件以及主观依赖检查者的经验等方面的局限[5].近年来，越来越多的研究热度集中在利用机器学习的方法探究与冠心病相关的危险因素，以及通过无创无损的方式进行冠心病的早期诊断筛查.

Patidar等[6]基于心率信号，采用最小二乘支持向量机检测冠心病，算法取得了较好的分类性能.Sridhar等[7]从心电信号中提取特征，经过离散小波变换和排序筛选后，输入到机器学习分类模型中，实验结果取得了较高的分类精度.Wiharto等[8]提出了采用C4.5决策树模型结合临床结果的冠心病分类方法.Liliana等[9]采用集成学习模型，通过SPECT图像对冠心病进行分类，获得了优于单一分类器的实验结果.Acharya等[10]提出了基于心电信号的卷积神经网络模型，实验结果表明该算法有助于冠心病的早期诊断.

然而，无论是通过医学的手段还是通过算法的方式挖掘出来的大量特征，对各种各样的机器学习方法来说是一个严峻的挑战.因此特征选择是机器学习过程中不容忽视的一个环节.特征选择算法可以有效地去除冗余特征和不相关特征，提高学习算法的泛化性能和运行效率，得到简单和容易理解的学习模型，特征选择本质上是一个组合优化问题.遗传算法是模拟自然界生物进化过程的一种随机搜索与优化算法，已广泛应用于自动控制、模式识别、工程设计、故障诊断、管理科学等领域[11].Joans等[12]提出了采用遗传算法进行特征选择，并结合随机森林分类器的算法，所提出的算法在MRI上进行脑部肿瘤分类.结果显示，该特征选择方法有助于提高分类器的准确度.Zelenkov等[13]采用基于遗传算法的集成模型进行破产预测.在集成过程中采用遗传算法进行特征选择，并采用遗传算法确定每个分类器的权重.与很多已有的算法相比，该算法表现出了卓越的分类性能.Wang等[14]提出了利用自适应遗传算法与本地搜索相结合的方法，解决多仓库车辆路径问题.该算法采用fitness-scaling技术，并能够根据适应度值自适应调整遗传算法.实验结果表明，该算法在性能和计算时间上优于传统的优化算法.Kumar等[15]提出了一种结合遗传算法和支持向量机的DOS攻击检测方法，该方法应用在PMU2017数据集上，获得了较高的检测准确度和较低的错误预警率.Bolan~os等[16]采用非支配排序遗传算法解决多个旅行商问题，该算法在真实实例上取得了不错的实验结果.

尽管遗传算法在很多领域都存在成功的应用，但其自身仍然存在收敛速度慢、容易陷入局部最优解等问题.因此本文提出一种基于改进的遗传算法的特征选择方法，并将其应用在冠心病的自动诊断中.

1 方法

1.1 数据集

Z-AlizadehSani数据集[17]包括303例病人，每例病人信息包括54个特征，包括病史，体格检查指标、实验室数据指标、ECG指标和超声波心动图指标.这些特征的离散化操作参照布朗的书[18]进行.

1.2 遗传算法简介

遗传算法是一种求解问题的高效并行的全局搜索方法，其主要特点是群体搜索策略和群体中个体之间的信息交换，它能在搜索过程中自动获取和积累有关搜索空间的知识，自适应地控制搜索过程以求得最优解或近似最优解.遗传算法所涉及的五大要素：参数编码形式、初始群体的生成、适应度函数的设计、遗传参数的设计（选择算子、交叉算子、变异算子）和控制参数等[19，20].

1.3 模拟退火

遗传算法中容易出现迭代前期快速收敛，而导致后期多样性降低，进化变慢，从而陷入局部最优解的困境.模拟退火算法局部搜索能力强，能有效弥补遗传算法的缺陷.模拟退火算法是模拟晶体退火过程所得到的一种算法，它在搜索过程中具有概率突变的能力[21].它在退火过程中不但接收好的解，还可以以一定的概率来接受一个比当前解要差的解，从而有效地避免在搜索过程中陷入局部最优解.

1.4 F-ScoreF-Score

是度量特征在不同类别间的区分度的一种指标，F-Score的值越大，代表该特征在不同类别之间的区分度越强[22].假设xk代表数据集中的样本，k=1，2…，N.n+和n-为正类和负类样本的数量，则数据集中第i个特征的F-Score由以下公式计算所得：

1.5 算法的评价指标

为了验证算法的有效性，本文采用准确率，召回率和综合评价指标F1-measure三个指标对算法进行评价.准确率和召回率是统计分类领域常用的一对度量指标，而F1-measure可以综合考虑前面两者.计算公式为：

1.6 本文算法

为了改进传统遗传算法早熟、多样性退化、以及搜索效率不高等问题，本文提出了基于改进的遗传算法的特征选择方法（MGA）.相较于传统的遗传算法，MGA算法在种群初始化时，采用F-score的特征评价值引导种群的初始化，为遗传算法搜索过程提供优秀的搜索起始点.并且在遗传操作过程中，当进化过程变慢时，采用类模拟退火的方式进行刺激，尽可能使算法跳出局部最优解，避免算法早熟收敛.算法的具体步骤如下：

（1）编码：二进制编码方式简单易行，因此文中采用二进制编码形式对特征进行编码，如下图所示，每条染色体都是一个定长的二进制串.如果第i位为1，表示第i个特征处于被选中的状态，为0表示没有被选中.

（2）种群初始化：遗传算法在大规模离散空间内随机搜索，其性能受到初始种群的影响.因此本文采用基于F-score的特征评价值引导种群的初始化，为遗传算法提供优秀的搜索起点.具体步骤为：

①利用公式1计算特征的F-score值并进行排序，排序越靠前表示该特征与类别的相关性越大.

②根据特征的排序结果，设定特征被选择的概率.特征的F-Score值排在前面，那么在染色体中该特征被选择的概率就会大一些，反之被选中的概率就会小一些.假设排序最靠前的特征被选中的概率为P0，排序最后的特征被选择的概率为P1，在P0和P1之间形成等差数列即为其余特征被选择的概率.文中P0，P1人为设定为0.8和0.4.

③根据步骤2设定好的特征被选择的概率，生成n个染色体，即为初始种群.

（3）遗传操作：进化过程是通过遗传操作来完成的，最主要的遗传操作包括选择、交叉和变异，并且当进化过程变慢时，采用类模拟退火的方式进行刺激，尽可能使算法跳出局部最优解.

①交叉操作：交叉操作是遗传算法中产生新一代染色体的主要方法，通过预先设定的交叉概率随机选择两个染色体交换部分基因，从而生成两个新的染色体.文中采用单点交叉实现交叉操作.

②变异操作：变异操作可以使染色体的某些基因位按照较小的概率发生突变，决定了遗传算法的局部随机搜索能力，文中采用基本位变异操作.

③选择操作：选择操作的基础是个体的适应度评价，适应度值高的染色体更有机会遗传下一代，充分体现了优胜劣汰的规则.文中对父代群体采用交叉变异操作，生成同样规模的子代群体.然后父代群体和子代群体共同竞争，选择出精英群体进行下一代进化.

④类模拟退火操作：当进化变慢时，例如连续5次最优解值不变，文中采用类模拟退火的方式重新生成一组群体加入，增加种群的多样性.实验中采用类模拟退火方式加入的种群规模为初始群体规模的1/2，生成的群体中一半是在最优解上增加扰动所得，另一半是随机生成的种群.这一组种群按照一定的概率加入到当代群体中：适应度值大于最优解的，必然要留在当代群体中，适应度值小于最优解的但是大于当代群体适应度值平均值的也会加入到群体中，并淘汰群体中适应度值排在后面的劣势基因，即：

本文提出的改进的遗传算法具体的实现步骤如下：

（1）根据特征的F-score的排序结果，构建等差数列，以此作为特征的初始分布权重引导种群初始化.

（2）根据适应度函数，计算父代群体的适应度值.

（3）对父代群体进行选择、交叉和变异操作，生成同样种群大小的子代群体，并计算子代群体的适应度值.

（4）对父代中n个染色体和子代中的n个染色体的适应度值进行统一排序，排序最靠前的n个染色体形成新一代群体.

（5）进化过程变慢时，采用类模拟退火的方式生成新的一组群体加入，增加种群多样性，摆脱局部最优解的困境.

（6）重复步骤2，3，4，直到满足终止条件.

2 实验结果

文中基于GA的特征选择方法参数设置：初始种群40，迭代次数100，交叉概率0.8，变异算子0.01，类模拟退火产生的种群规模20，以支持向量机的分类结果作为遗传算法的适应度函数.

2.1 分类效果实验

支持向量机基于最大间隔分离原理，在最小化模型复杂度和训练误差的前提下最小化结构风险，在人工智能医学领域被广泛使用.为了验证算法的效果，将文中所提出的算法与SVM算法，传统的遗传算法，以及基于F-Score与序列前向搜索策略的算法相比较.实验中采用十折交叉验证来验证算法的性能.由于遗传算法是一种随机搜索策略，所以将十折交叉验证重复十次，用十次交叉验证的结果来增加算法的置信度.分类实验结果图如图1所示，具体的数值结果如表1所示.可以看出，文中所提出的MGA算法准确率、召回率以及F1-Measure指标分别为93.36 0.88%、96.64 1.05%、94.90 0.94%.该算法在准确率、召回率以及F1-Measure指标上优于其他三种算法，说明MGA算法对于冠心病的自动分类效果较好.相对于传统的GA来说，MGA算法的标准差更小，说明算法的稳定性更好.

图1 分类实验结果图

表1 分类实验结果

2.2 特征维数约减效果比较

几种对比方法在特征维数约减方面的表现如表2所示，几种方法都对特征维数约减做出了贡献，基于F-Score+SFS方法的特征约减效果最好.但是序列前向搜索算法的局限性在于特征一旦加入无法剔除，没有充分考虑特征之间的关联，有时候会得到局部最优解.传统的遗传算法和文中所提出的MGA也明显减少了特征维数.这对于降低模型复杂度，减少过拟合风险存在很大的帮助.

表2 特征维数约减结果

2.3 初始种群分布

文中所提出的算法，采用基于特征加权的概率分布进行种群初始化操作.采用特征的F-Score评价值为先验知识，指导种群的初始化，使得遗传算法有较好的搜索起始点.文中记录了20次算法执行过程的起始点与传统的遗传算法起始点的对比，对比结果如下图2所示.相对于传统的遗传算法，基于先验知识生成的初始种群中的最优解的分布更集中.这说明了采用基于先验知识对特征加权指导种群初始化，遗传算法的搜索起始点更高，使得后续算法在一个初步优化了的子集中搜索.

图2 初始种群分布实验

2.4 类模拟退火算法效果

针对遗传算法后期多样性变差，进化速度变慢，容易陷入局部最优解的问题，文中采用类模拟退火的方法进行刺激.以随机选择的一次算法的运行时间为例，下图3描画了一次算法运行的过程中迭代次数与算法F1-Mesure的对应曲线图.算法经过52次收敛到最优解，其中星号点表示在执行类模拟退火方法时产生的优于当代最优解的解.可以看出类模拟退火能够在算法陷入局部最优解时进行刺激，增加种群多样性，使算法尽可能趋于全局最优解.

图3 类模拟退火实验结果

3 结论

文中采用了多种举措改进遗传算法的局限性，并采用基于改进的遗传算法进行特征选择，结合支持向量机进行冠心病分类.实验结果表明该方法很好地改善了遗传算法的多样性，有效地解决了传统遗传算法的早熟收敛局限性.并且该算法能够有效地降低特征维数，并能够进一步提高算法的分类效果.该方法可以辅助临床医生进行冠心病的早期筛查，为患者的有效治疗争取时间.