改进 GA-SVM 在冠状动脉疾病诊断中的应用

卢春红;顾晓峰

【摘 要】改进的遗传算法（ GA）自动优化支持向量机（ SVM）参数，同步决策最优特征子集。新颖的分组多基因交叉技术保留了基因小组中的信息，而且允许后代继承更多的来自染色体的遗传信息。该算法促进可行解集中的高质量染色体信息交换，提高了解空间的搜索能力。实验结果说明：改进GA-SVM不仅可决策出与疾病相关的重要特征变量、优化SVM参数，而且可提升分类性能。与前馈BP神经网络及自适应模糊推理系统两种学习算法的比较表明，改进GA-SVM具有更好地表现。%An improved genetic algorithm can automatically determine and simultaneously optimize the feature subsets , parameters of support vector machines (SVM) in coronary artery disease (CAD) diagnosis.A novel partitioned multi-gene crossover technique pre-serves the information in the each gene component and makes offspring to obtain gene information from more than a pair of parent chro -mosome.The proposed algorithm promotes the information exchange among multiple chromosomes of top ranked solutions , and im-proves the search ability of the potential region .Experiments results showed that the improved GA can not only determine the critical features related to the CAD , but also improve the classification rate .Comparisons demonstrate that the improved GA-SVM scheme ex-hibit better performance than the approaches based on the feed forward back -propagation artificial neural network and adaptive neuro-fuzzy inference systems .

【期刊名称】《生物学杂志》 【年(卷),期】2014(000)004 【总页数】5页(P90-94)

【关键词】冠状动脉疾病诊断;支持向量机;遗传算法;前馈BP神经网络;自适应模糊推理系统

【作 者】卢春红;顾晓峰

【作者单位】江南大学轻工过程先进控制教育部重点实验室，无锡214122;江南大学轻工过程先进控制教育部重点实验室，无锡214122 【正文语种】中 文 【中图分类】TP182;R319

冠状动脉疾病(CAD)包含与心脏及心血管系统相关的一系列疾病，是当前世界各国引发死亡的主要原因之一。据统计，西方国家死亡人数中有30%可归因于该疾病。CAD的诱发与环境、生活习惯、身体状况、基因等内外因素有关，不仅治疗费用昂贵，而且诊断困难，特别是在没有症状显现的情况下，医师仅凭自身专业知识及经验很难作出正确及时的诊疗决策。

随着计算机辅助智能诊断技术在医疗领域的应用越来越广泛，研究人员开发了一些机器学习算法来帮助诊断CAD。例如，Tsipouras等[1]提出了基于模糊规则的四阶段决策系统来诊断CAD，得到了65%的分类精度；Setiwan等[2]提出了一种模糊决策支持系统，可获得比医师单独诊断更好的CAD预测率。另外，一些基于人工智能的诊断系统也被广泛用于诊断各种复杂疾病[3-5]。支持向量机(SVM)作为

一种非常有效的统计学习方法[6]，近年来受到了医疗界的广泛关注[7, 8]。然而，高维的CAD数据集增加了计算复杂度及过度拟合的风险[9]，同时SVM的参数也影响SVM的分类精度。因此，去除高维数据集中的不相关特征以及同步优化SVM参数成为此类智能诊断系统中的一个重要步骤。

遗传算法(GA)基于达尔文自然选择理论，属于使用最广泛的优化工具之一。不像其他的启发式搜索算法易于局部收敛，GA可在复杂的搜索空间大概率地找到全局最优解，而且对初始化条件不敏感，GA可应用于医疗决策系统[10-11]。然而，GA不能很好的调整可行解空间的范围，而且容易产生过早收敛现象[12]。 本文提出了基于改进GA-SVM的CAD诊断方法，自动优化SVM参数，同步决策最优特征子集，最终改善了医疗诊断的分类精度。该算法提出新的分组多基因交叉技术，将杰出染色体分成3个基因小组，每个小组保存了更好的基因信息。不像传统的GA通过交换1对父辈染色体信息进行交叉操作，分组多基因交叉技术产生携带更多基因信息的染色体。最后将改进GA-SVM算法与前馈BP神经网络(BPNN)和Takagi-Sugeno型自适应模糊推理系统(ANFIS)进行了比较，进一步验证了该算法的有效性。 1 支持向量机

SVM是Vapnik等人在统计学习理论基础上提出的一种学习方法[6]，拥有强大的泛化能力。设有N个训练样本，每个输入样本的类标为yi，则训练集可表示为：{xi, yi}, i = 1…N, x ∈ Rd (d是维数)，yi ∈ {-1, 1}。

对于线性可分的数据，存在一个超平面来分割两类数据。超平面可描述为： x·w-b=0 (1)

为使该平面能正确分类所有样本，并具备一定的分类间隔，需满足下面的约束： yi(w·xi-b)≥1

(2)

最大化分类间隔，构造最优超平面，求解下面的约束问题： ≥1 (3)

对于线性不可分的数据，在式(3)中增加一个松弛变量ξi≥0,目标函数变为：

s.t. yi(w·xi-b)≥1-ξi (4)

其中C为惩罚因子，用来平衡错分样本数和最大分类间隔。 引入Lagrange乘子αi > 0，该二次规划问题转化为对偶问题： ≥ai≥0 (5)

根据求得的Lagrange乘子，可得到决策函数： (6)

对于线性不可分的数据，通过核函数将低维空间的数据变换到高维特征空间，使之成为线性可分，然后在新的空间寻找最优超平面。点积xi·xj可由非线性核函数替换。本文使用分类能力强的径向基核函数(RBF)作为映射函数[13]，k(xi,xj)=exp(-β‖xi-xj‖)，β>0。

尽管在机器学习中，SVM算法可以达到优异的分类性能，但是它的最终结果同时受到最优特征子集以及SVM 参数(C, β)的影响。 2 遗传算法

GA是基于达尔文进化理论来模拟自然选择和生物遗传的一种随机优化技术，包含

适应度函数，选择、交叉和变异操作[12]，可用来解决很多传统的梯度优化方法难以解决的问题(如非线性的、离散的、随机的目标求解问题等)。GA把问题的解表示成“染色体”或个体，即通常用二进制编码0或1来表示的编码串。

随机产生初始种群中的染色体，也即假设解集，置于后代的遗传进化中。根据计算的每个染色体的适应度，选择优秀的父辈染色体遗传到下一代种群中。根据精英策略，一些顶级排行的优秀染色体可以直接复制，成为下一代种群中的染色体；而剩下的优秀染色体经过交叉、变异操作后，遗传到下一代。对新一代种群重新评价选择、交叉和变异操作，不断循环，使种群中优秀染色体的适应度值不断提高，则迭代过程收敛，进化过程结束。最后一代的染色体解码，即为给定问题的最优解。 3 方法 3.1 提出的算法

提出的算法利用GA在遗传进化过程中，自动地决策特征子集和同步优化SVM的参数(惩罚因子C和核参数β),其流程如图1所示。主要步骤如图1。

1)算法首先初始化初始种群。如图2所示，每个染色体分为3个基因小组(S1, S2, S3)，每个小组由一段基因组成，分别是：惩罚因子、核参数和特征子集。 图1 提出算法的流程图Fig 1 Architecture of the proposed algorithm 图2 染色体描述Fig 2 The chromosome representation

2)对种群中的所有染色体进行解码。二进制的惩罚因子和核参数转换为十进制，去除数据集中未被选中的特征。

3)第(2)步中获得的参数作为SVM输入，使用训练集构建SVM模型。

4)计算测试集的适应度函数值。算法提出的适应度函数不仅体现了SVM的泛化能力，而且通过第二项来惩罚GA所选择的特征数。 (7)

其中：w为权重系数(0< w <1)，F为总特征数，Ff为染色体中1的个数(相当于所选子集中的特征数)。w值越大，适应度函数中分类精度的贡献越大，而加于所选特征数的惩罚也越大。GA需要尽可能地减少所选的特征数，w用来控制这两项的平衡。acc为SVM的分类精度，表示为： (8)

其中：N为总的测试集中的总样本数，Nc为正确分类的测试样本数。

5)选择t个顶级排行的优秀染色体作为杰出染色体群。该杰出染色体群生成r个分组多基因交叉染色体，如图3所示，每个杰出基因小组通过轮盘选择策略生成各自的基因小组。假设杰出基因小组的适应度与它们对应的染色体的适应度相等。由于促进了可行解中的高质量的信息交换，该算法更有效地增强了搜索解空间的能力。适应度越高的染色体，它相应的基因小组被遗传的概率越大。分组多基因交叉染色体形成新的可行解集合。再重新评价适应度及选择操作，产生杰出父辈池。 图3 分组多基因交叉技术Fig 3 Partitioned multi-gene crossover technique 6)第(5)步中选出最杰出的染色体作为精英，不需要经过交叉与变异操作，直接复制到下一代中。

7)杰出父辈池中的染色体与普通父辈池中的染色体进行配对，经过交叉(如图4所示)和变异，产生新生代的个体。 图4 交叉算子Fig 4 Crossover operator

8)重复步骤(2)～(7)直到产生最大的代数。最后一代中具有最佳适应度值的染色体被选为最优解。 3.2 数据集

CAD的早期诊疗非常重要，研发CAD自动诊断系统可帮助医师准确预诊，使患者得到及时治疗。本文中的数据集来自于UCI机器学习仓[13]中的Cleveland数

据集，包含14个特征属性：Chest pain type (Cp)，Age，Sex，Resting blood pressure (Restbps)，Serum cholesterol in mg/dl (Chol)，Fasting blood sugar (Fbs)，Resting electrocardiographc results (Restescg)，maximum heart rate achieved (Thalach)，Exercise induced angina (Exang)，ST depression induced by exercise relative to rest (Oldpeak)，slope of the peak exercise ST segment (Slope), number of major vessels colored by fluoroscopy (Ca)，Thalium (Thal)及diagnosis of heart disease。本文主要使用前13个特征，其属性用特征ID描述(ID分别为1～13)，其数值用一个0～4的整数表征，0代表正常无疾病，数值1～4依次表示疾病的严重程度。在Cleveland数据集中去除6个缺失的样本值，剩下的297个样本记录中，54%属于正常的样本状态，余下46%属于有病理的样本状态。 3.3 实验参数设置

基于SVM的Cleveland数据分类在MATLAB上进行，随机地将数据集中的正常样本和疾病样本分别以1∶1的比例分入训练和测试集中，组合成新的训练和测试集。SVM的分类表现很大程度上取决于合适的参量C和β， 图2中的基因小组S1和S2对应惩罚因子和核函数的范围分别为{2-8, 28}, {2-4, 24}，将它们编码为二进制串。基因小组S3自动的设置为数据集的13个特征的二进制编码串，具有1值的基因说明S3选中了对应的特征。改进的GA的参数设置如表1中所述。 表1 改进GA参数Table 1 The improved GA parametersGA参数值种群40最大代数100杰出染色体5分组多基因交叉染色体15杰出父辈池10普通父辈池10精英2交叉概率0.8变异概率0.1w0.85 4 仿真结果分析与讨论

改进GA可以去除不相关的特征，保存与CAD状态最相关的特征，增强SVM的分类性能。受交叉算子的影响，改进GA的空间搜索能力加强。同时，变异算子引

进了搜索的随机行为，可发现新的搜索空间，并防止GA过早收敛。图5显示了目标问题求解过程中，改进GA的适应度函数值随代数增加而不断变化。可以看出，种群中的个体朝着近似最优解的方向进化，新生代的染色体含有比父辈更好的基因，而且收敛速度比传统的GA更快，在第35代的时候收敛。

图5 两种方法的适应度函数变化过程Fig 5 The evolution of fitness function using the conventional and improved GA

由于GA的寻优空间非常复杂，算法每次运行不一定找到相同的最优特征子集；或者，所选的多个特征子集都可得到SVM的最佳分类精度。因此，判断哪些特征有助于评价样本的状态很重要。在不同样本上运行100次改进GA，每个特征被选择的次数如图6所示，水平线为y=70. 其中7个特征被选择的概率至少为0.7，使用GA寻找到含有这7个特征的子集分类时，SVM达到最佳分类效果。最佳特征子集包含特征Cp，Age，Exang，Oldpeak，Slope，Ca，Thal。改进GA不仅将Cleveland数据集的特征数从13减至7，优化了SVM参数，因而增强了SVM的分类性能。

图6 运行改进GA100次过程中每个特征被选中的次数Fig 6 Number of times features are selected during 100 different runs of the improved GA 表2列出了SVM对应的分类率。应用完整的特征集时，训练集中的正常和疾病样本分类率分别为86.4%和84.3%，测试集中的正常和疾病样本分类率分别为83.7%和82.1%。应用GA优化的特征子集时，训练集中的正常和疾病样本分类率分别提高了1.2%和1.6%，测试集中的正常和疾病样本分类率分别提高了2.1%、1.2%。然而，利用改进的GA获得优化后的特征集，其分类结果最佳，测试集中的正常和疾病样本分类率分别达到87.2%和85.4%。可见，与采用特征全集及传统的GA优化得到的结果相比，基于改进GA优化的特征子集可得到更好的分类率。如果医师将健康人误诊为CAD患者，这种错误的决策由于不会置人于危险状态下，是可

容忍的。反之，如果将CAD患者误诊健康人群，可能导致延误治疗甚至引发死亡，必须尽可能避免这种情况。

表2 SVM对应的分类率(%)Table 2 Summary of the SVM classification rates (%)方法训练集正常样本疾病样本测试集正常样本疾病样本特征全集

86.484.383.782.1GA优化的特征子集87.685.985.883.3改进GA优化的特征子集88.586.787.285.4

表3 改进GA-SVM与其他3种方法的分类结果比较(%)Table 3 Comparison of the proposed schemewith other three methods (%)分类方法测试集正常样本疾病样本GA-SVM85.883.3改进GA-SVM87.285.4BPNN82.980.5ANFIS84.282.5

将本文提出的方法与传统的GA-SVM、BPNN及ANFIS 3种方法进行比较。BPNN是人工神经网络(ANN)中常用的分类器[14-15]。经过测试后，单神经网络中包含2个隐含层的结构是最好的分类器。第1个隐含层中含有5个神经元，第2个隐含层中含有3个神经元。隐含层使用Sigmoid函数，输出层应用线性变换函数。整个神经网络应用Levenberg Marquardt (LM)算法。ANFIS是神经网络与模糊理论结合的产物[16]，该算法应用减聚类，聚类半径为0.7。后两种分类器也利用MATLAB来仿真，使用相同的训练和测试集并应用了全特征集。几种方法的分类结果列于表3。测试结果表明，BPNN和ANFIS分类器在正常样本上可分别获得82.9%和84.2%的正确分类率，在CAD疾病样本上则为80.5%和82.5%，而本文提出的方法具有优于这两种分类器的表现，同时也比传统的GA-SVM分类结果好。这表明基于改进GA特征选择的SVM诊断是一种有效的CAD诊断评估方法。 5 结论

提出了一种基于改进GA-SVM的CAD疾病诊断方法。该算法的主要贡献在于自

动决策最优的特征子集并同步优化SVM参数，增加了SVM的分类精度。改进的GA应用新的分组多基因交叉技术，促进了顶级排行的优秀染色体的基因交换。与BPNN及ANFIS两种算法相比，提出的算法具有更好的表现。 参考文献：

[1]Tsipouras M G, Exarchos T P, Fotiadis D I, et al. Automated diagnosis of coronary artery disease based on data mining and fuzzy modeling [C]. IEEE Trans on Information Technology in Biomedicine, 2008, 12 (4): 447-458. [2]Setiawan N A, Venkatachalam P A, Hani A M. Diagnosis of coronary artery disease using artificial intelligence based decision support system [C]. Proceedings of the International Conference on Man-Machine Systems, BatuFerringhi, Penang, 2009.

[3]Anooj P K. Clinical decision support system: risk level prediction of heart disease using weighted fuzzy rules [J]. Journal of King Saud University Computer and Information Sciences, 2012, 24(8): 27-40.

[4]Ahmad F A, Isa A M, Hussain Z, et al. Intelligent medical disease diagnosis using improved hybrid genetic algorithm multilayer perceptron network [J]. Journal of Medical Systems, 2013, 37(2): 1-8.

[5]Mokeddem S, Atmani B, Mokeddem M. Supervised feature selection for diagnosis of coronary artery disease based on genetic algorithm [C]. Proceedings of International Conference on Computer Science & Information Technology, 2013: 41-51.

[6]Vapnik V N. Statistical learning theory [M]. New York: Wiley, 1989. [7]Abibullaev B, An J. Decision support algorithm for diagnosis of AD/HD using electroencephalograms [J]. Journal of Medical Systems, 2012, 36(2):

2675-2688.

[8]黄瑞梅，杜守洪，陈子怡，等. 基于支持向量机的癫痫脑电信号模式识别研究[J]. 生物医学工程学杂志，2013, 30(5)：919-924.

[9]Zcift A, Guelten A. Gentic algorithm wrapped Bayesian network feature selection applied to differential diagnosis of erythemato-squmous diseases [J]. Digital Signal Processing, 2013, 23(1): 230-237.

[10]Kocer S, Canal M R. Classifying epilepsy diseases using artificial neural networks and genetic algorithm [J]. Journal of Medical Systems, 2011, 35(4): 489-498.

[11]Elveren E, Yumusak N. Tuberculosis disease diagnosis using artificial neural network trained with genetic algorithm [J]. Journal of Medical Systems, 2011, 35(7): 329-332.

[12]张 梅，胡跃明，汪 涛，等. 基于改进遗传神经网络的优化预测方法及其在腹膜透析中的应用[J]. 生物医学工程学杂志，2009, 26(6): 1186-1190.

[13]Keerthi S S, Lin C J. Asymptotic behaviors of support vector machines with Gaussian kernel [J]. Neural Computation, 2003, 15(7): 1667-1689. [14]王多点，邱国庆，戴婷婷，等. 基于改进BP神经网络的围岩自稳能力评估模型[J]. 计算机应用， 2012, 32(4): 1056-1059.

[15]董传亮，史仲平. 基于自联想神经网络的谷氨酸发酵故障诊断[J]. 生物学杂志，2009, 26(3): 33-37.

[16]韩宝如，邢益良，刘瑶利. 基于Takagi-Sugeno型自适应模糊神经网络的模拟电路故障诊断[J]. 电子质量, 2013, 3(5): 31-35.