基于免疫算法的柔性制造单元动态调度研究
李东+卢虹冰
摘 要： 提出了一套结合特征筛选及参数设定的方法，使用支持向量机来辨别肿瘤良恶性，并利用人工免疫算法进行特征筛选及决定支持向量机的参数。针对由PHILIPS ATL HDI 3000超声波扫描仪获得的220幅图片的处理结果显示，在此所提出的方法能使乳房肿瘤的分类正确率达到95.71%，并大幅缩短支持向量机的训练时间。
关键词： 乳腺肿瘤； 人工免疫算法； 特征提取； 支持向量机； 计算机辅助诊断
中图分类号： TN919?34 文献标识码： A 文章编号： 1004?373X（2014）04?0108?04
Breast tumor image recognition based on artificial immune system algorithm
LI Dong1，2， LU Hong?bing1
（ 1. Biomedical Engineering Department， Fourth Military Medical University， Xian 710032， China；
2. Information Department， Second People's Hospital of Linfen City， Linfen 041000， China）
Abstract： An approach combining the feature selection and parameter setting is proposed， in which SVM is adopted to recognize whether a tumour is malignant or not， and the AIS algorithm is utilized to select the tumor features and determin the parameters of SVM. The experimental results indicate that the approach can make the classification accuracy of the breast tumour reach to 94.63%， improve the correctness of adjusting the quale of a breast tumour， and shorten training time of the computer?aided diagnosis system based on ultrasound breast image.
Keywords： breast tumour； AIS algorithm； feature extraction； SVM； computer?aided diagnosis
0 引 言
乳癌属于较易在早期发现征兆的癌症，如果能及早诊断与治疗，不但有机会保留完整的乳房，存活率也大为提高。目前较常见的乳癌图像检测方法有乳房X光造影、乳房超声波造影及核磁共振造影等[1]。其中乳房超声波造影具有操作便利，无放射性，非侵入性及价格相对较低廉等优势，广为各医疗机构所采用。
本文验证了将人工免疫算法结合支持向量机应用于超声波乳房肿瘤图像诊断上的效果，希望可以通过人工免疫算法所具有的抗体复制、变异以及与抗原间的亲和力提升等功能，来提高乳房肿瘤识别的成功率。
1 乳腺超声波图像处理
在超声波肿瘤图像中，良性肿瘤和恶性肿瘤在形状上往往会有很大的差异[2]。如图1所示，良性肿瘤的轮廓多半较为平滑且规则， 恶性肿瘤的轮廓则通常较破碎且不规则，因此可通过形状特征来识别肿瘤的良恶性。目前常用的乳房超声波图像特征包含形状、音波回音性、肿瘤边缘和音波衰减等。
图1 乳腺超声波图像处理图示
1.1 乳腺超声波图像预处理
原始的超声波图像因为其有大量的噪声，对于在检测一些细节特征时敏感度较低，所以在提取特征前，需先使用一系列的图像预处理方法才能获取比较精确的良恶性肿瘤外形；预处理结果将直接影响被测数据的特征值，进一步决定了分类的效果[3?4]。
首先，根据文献[5]中使用方法，将每张原始的超声波图像先以混合噪声图像滤波算法去除其噪声及斑点，为了取得更精准的肿瘤外形，采用边缘检测方法提取图像中的肿瘤边界信息，提高肿瘤轮廓与背景之间的对比度，最后，以水平集Level set方法将肿瘤的形状从图像中分割出来，以计算特征值。处理结果如图2所示。
图2 超声波图像处理结果
1.2 乳腺超声波图像特征提取
肿瘤的形状特征与纹理相对不易因为设备的变化而产生较大差异，因此，肿瘤的几何形状与纹理比其他特征属性稳定。本文主要研究乳房超声波图像中肿瘤的形状和纹理特征，纹理特征主要有Huang等提出的auto?covariance coefficient[6?7]，以及Garra 等提出的contrast of grey level[8?9]，几何特征主要有有Stavros等提出的spiculation特征以及Sehgal等提出的margin sharpness特征[10?12]。参考图3，图中：白色虚线表示最大直径（图3（a），（b）），红色线为最小包裹多边形和矩形（见图3（b），（c））。本文采用六种几何特征：
图3 超声波图像中肿瘤的形状和纹理特征
几何特征定义如下：
[E1=π?SP2，E2=SM_D2，E3=MD/SDE4=CSCP，E5=CS-SN，E6=SS]
如图3所示，式中S为肿瘤面积（stick算法得到区域包裹的总像素点）；P为肿瘤周长（stick算法得到区域包裹曲线的总像素点），MD和SD分别为最大直径最小直径，如图3所示，CS和CP是最小包裹凸多边形面积和周长；N为最小包裹凸多边形的边数量；SS为包裹最小矩形面积。
纹理特征采用李晓峰等[1]提出的归一化自相关系数的纹理特征：
[AΔm，Δn=1M-ΔmN-Δn· i=0M-Δm-1 j=0N-Δn-1fi，j-ffi+Δm，j+Δn-f]
纹理特征共计24个，加上6个几何特征，构成一个30维特征向量。
2 人工免疫算法原理
人工免疫系统的模型最早出现于1986年，由Farmer等人所提出的免疫网络动态模型，开启了生物免疫学说与人工智能结合的研究议题。接着在1996年12月由日本所举办的免疫系统国际专题研讨会上，正式提出并确立人工免疫系统（Artificial Immune System）的概念。1997年，IEEE System， Man and Cybernetics 成立了人工免疫系统及应用的分会，此后以人工免疫系统为主题的国际会议陆续在世界各地举办，显示这门领域的研究开始受到重视。
由于人工免疫系统的兴起，近年来，基于各项生物免疫机制而开发出的人工免疫算法纷纷被提出，以下将针对基于免疫学基本原理 所设计出的3种典型人工免疫算法，包含了阴性选择算法、复制选择算法以及人工免疫网络做介绍：
抗体的多样性对于提高遗传算法（IGA）的全局搜索能力同时保证不陷于局部最优解，同时自我调节机构可提高遗传算法（IGA）的局部搜索能力，并且免疫记忆功能可以加快搜索速度，提高遗传算法的总体搜索能力。具体的说就是用2个免疫操作来优化遗传算法：抵抗；免疫选择。
抵抗：假设个体[x]，抗体操作的意思是基于先前的信息在某些位上修改基因来最大可能的获得高的适应度。假设一个群体为[c=x1，x2，…，xn0]，在[c]上的抗体操作即是[nα=αn]个体是从先前知识按比例[α]选择出来的。这个操作的数量和有效性在IGA中有着重要的角色。如图4所示。
免疫选择：先是检查抗生物，如果比父辈的适应度小，则表示在交叉变异时出现了严重的基因损坏，这样就将父辈来进行下一次竞争。然后是退火选择[4]：从先前的后代中选择个体时引入概率：[Pxi=efxiTki=1n0efxiTk]，其中：[fxi]是个体[xi]的适应度，[Tk]是温度控制序列趋于0。
IGA算法步骤：
（1） 创建初始群体[A1]；
（2） 判断是否符合条件，符合则停止；
（3） 对当前群体执行交叉、变异操作得到下一代；
（4） 执行抗体、免疫操作，跳转到（2）。
图4 初始抗体表示
3 基于人工免疫优化的SVM乳腺肿瘤识别
李晓峰提出了采用支持向量机（SVM）对肿瘤图像进行识别，取得了较好的结果，但是支持向量机本身对于噪声和训练集的极端值非常敏感，且多个特征值如果未经适当筛选也可能会导致支持向量机对肿瘤分类的正确率降低，因此本文利用人工免疫算法来筛选特征值，以及决定支持向量机中 用来将数据转换到更高维度空间之径向基核函数（Radial Basis Kernel，RBF）的参数C与参数γ。
算法流程图如图5所示，参考上诉第2节免疫算法原理介绍具体过程如下：
（1） 人工免疫算法首先会产生出数组采用二进制编码的初始抗体， 示意如图6所示。抗体中每n个位决定一个参数。由于每组初始抗体需决定支持向量机的两个参数及30个特征筛选结果，因此一组抗体的总长度为32n。
（2） 二进制初始抗体中所有的值皆是由随机随机数来决定。每段参数的值都产生后，会先将原本二进制的参数转换成十进制。
（3） 所有初始抗体以二进制编码分别进行复制及变异的动作，其中保留住亲和力最高的抗体以进行下个阶段的循环。整个人工免疫演算法的循环会持续直到亲和力达到预设的目标或是执行到设定的循环次数为止。
4 实验及结果分析
本文共采用了 220个超声波乳房肿瘤图像样本，其中包含120 个良性肿瘤及100个恶性肿瘤的确定病例，病患的年龄分布为18～64岁。所有的超声波图像样本均摄自于PHILIPS ATL HDI 3000超声波扫描仪，扫描频率为5～10 MHz，扫描宽度为38 mm。220个被测的超声波乳房肿瘤图像样本以随机的方式分成5组，并轮流选择其中一组样本进行测试，其余四组则用来作为SVM的训练集。
图5 人工免疫算法优化SVM流程图
计算机配置为Intel Core i5?2400处理器，频率2.6 GHz。内存容量4 GB。操作系统为64 位Microsoft Windows 7 SP1。人工免疫算法参数：人工免疫算法预设的初始抗体数目为5组。一般抗体的复制率为10倍，具有最佳亲和力的抗体则会复制30倍。在二进制抗体中每8个位决定一个实验参数。整个人工免疫算法运算的循环次数为400次。支持向量机的参数C及y之范围分别为1～1 000及0.001～0.999。待筛选的特征共30个，特征筛选的比例为20%。实验结果如表1所示。
表1 实验结果
由于原始的支持向量机仅靠参数C与参数γ的排列组合使用网格搜寻法（Grid Search），最多可能执行999 000次（C的范围介于1～1 000，每次增加1 ； γ的范围介于0.001～0.999，每次增加0.001），再加上使用30纬特征使得执行次数较大。而本文提出的方法在较少的循环数量级上就找到了合适参数，并且将参数与特征联合进行优化，与文献[1]相比使用较少特征取得了较好的效果。筛选出的特征数量在5～7个之间，同时免疫算法设置的合适C和γ参数保证了SVM在较低执行次数下就取得较好结果。
如图6所示，在特征筛选准确度与效率方面，通过与常用的PCA降纬方法相比，采用统一的分类器?支持向量机，分别使用以下3种方法，采用本文提出的免疫算法筛选特征；采用PCA算法对特征数据降纬；不降纬，直接将特征数据送入分类器。从以下常用的评价指标做了对比[1]，ROC曲线图见图6。
[Accuracy=TP+TN/TP+TN+FP+FNSenitivity=TP/TP+FNSpecificity=TN/TN+FPPositivePredictiveValue=TP/TP+FPNegativePredictiveValue=TN/TN+FN]
图6 本文方法与PCA及本文方法ROC曲线图
5 结 论
本文使用了人工免疫算法结合支持向量机对超声波乳房肿瘤图像进行分类。通过人工免疫算法进行特征筛选并获取支持向量机的最优参数，使支持向量机在不影响正确率前提下降低分类时所花费的时间。由实验结果数据可知，利用人工免疫演算法先筛选特征的步骤能大幅降低支持向量机因计算冗余特征值所耗费的时间。而用来决定径向基核函数的参数C与γ可以大幅缩短支持向量机的执行次数。除了本文方法外，未来可以考虑采用由其他生物免疫系统概念发展出来的方法，如免疫算法与其他著名算法相结合的应用，如与基因算法结合的免疫基因演算法（Immune Genetic Algorithm）、与粒子群算法结合的免疫粒子群演算法（Immune Particle Swarm Algorithm）和与蚁群算法结合的免疫蚁群算法（Immune?ant Colony Algorithm）等。
参考文献
[1] 李晓峰.基于支持向量机的超声乳腺肿瘤图像计算机辅助诊断系统[J].光电子·激光，2008（1）：65?67.
[2] CHANG Ruey?feng， WU Wen?jie， MOON W K， et al. Support vector machines for diagnosis of breast tumors on US images [J]. Academic Radiology， 2003， 10（2）： 189?197.
[3] 李晓峰.基于超声图像的乳腺癌计算机辅助诊断关键技术研究[D].哈尔滨：哈尔滨工业大学，2008.
[4] 高超，须文波，孙俊.新的强高斯噪声自适应滤波方法[J].计算机工程与应用，2011（28）：10?12.
[5] CHANG Ruey?feng， WU Wen?jie， MOON W K， et al. Improvement in breast tumor discrimination by support vector machines and speckle?emphasis texture analysis [J]. Ultrasound in Medicine & Biology， 2003， 29（5）： 679?686.
[6] HUANG Yu?len， CHEN Dar?ren， LIU Ya?kuang. Breast cancer diagnosis using image retrieval for different ultrasonic systems [C]// Proceedings of 2004 International Conference on Image Processing. [S.l.]： ICIP， 2004， 5： 2957?2960.
[7] GARRA B S， KRASNER B H， HORII S C， et al. Improving the distinction between benign and malignant breast lesions： the value of sonographic texture analysis [J]. Ultrasonic Imaging， 1993， 15（4）： 267?285.
[8] KUO W?J， CHANG R?F， LEE C C， et al. Retrieval technique for the diagnosis of solid breast tumors on sonogram [J]. Ultrasound in Medicine & Biology， 2002， 28（7）： 903?909.
[9] 莫宏伟，郭茂祖，毕晓君.人类免疫系统仿真与建模研究综述[J].计算机仿真，2008（1）：6?9.
[10] TARAKANOV A O， NICOSIA G. Foundations of immuno?computing [C]// Proceedings of First IEEE Symposium on Foundations of Computational Intelligence. [S.l.]： FOCI， 2007： 210?221.
[11] PARSHANI R， CARMI S， HAVLIN S. Epidemic threshold for the SIS model on random networks [J]. Physical Review Letters， 2010， 122： 112?114.
[12] 李男.基于PCA的乳腺肿块辅助诊断方法研究[D].沈阳：沈阳工业大学，2013.
表1 实验结果
由于原始的支持向量机仅靠参数C与参数γ的排列组合使用网格搜寻法（Grid Search），最多可能执行999 000次（C的范围介于1～1 000，每次增加1 ； γ的范围介于0.001～0.999，每次增加0.001），再加上使用30纬特征使得执行次数较大。而本文提出的方法在较少的循环数量级上就找到了合适参数，并且将参数与特征联合进行优化，与文献[1]相比使用较少特征取得了较好的效果。筛选出的特征数量在5～7个之间，同时免疫算法设置的合适C和γ参数保证了SVM在较低执行次数下就取得较好结果。
如图6所示，在特征筛选准确度与效率方面，通过与常用的PCA降纬方法相比，采用统一的分类器?支持向量机，分别使用以下3种方法，采用本文提出的免疫算法筛选特征；采用PCA算法对特征数据降纬；不降纬，直接将特征数据送入分类器。从以下常用的评价指标做了对比[1]，ROC曲线图见图6。
[Accuracy=TP+TN/TP+TN+FP+FNSenitivity=TP/TP+FNSpecificity=TN/TN+FPPositivePredictiveValue=TP/TP+FPNegativePredictiveValue=TN/TN+FN]
图6 本文方法与PCA及本文方法ROC曲线图
5 结 论
本文使用了人工免疫算法结合支持向量机对超声波乳房肿瘤图像进行分类。通过人工免疫算法进行特征筛选并获取支持向量机的最优参数，使支持向量机在不影响正确率前提下降低分类时所花费的时间。由实验结果数据可知，利用人工免疫演算法先筛选特征的步骤能大幅降低支持向量机因计算冗余特征值所耗费的时间。而用来决定径向基核函数的参数C与γ可以大幅缩短支持向量机的执行次数。除了本文方法外，未来可以考虑采用由其他生物免疫系统概念发展出来的方法，如免疫算法与其他著名算法相结合的应用，如与基因算法结合的免疫基因演算法（Immune Genetic Algorithm）、与粒子群算法结合的免疫粒子群演算法（Immune Particle Swarm Algorithm）和与蚁群算法结合的免疫蚁群算法（Immune?ant Colony Algorithm）等。
参考文献
[1] 李晓峰.基于支持向量机的超声乳腺肿瘤图像计算机辅助诊断系统[J].光电子·激光，2008（1）：65?67.
[2] CHANG Ruey?feng， WU Wen?jie， MOON W K， et al. Support vector machines for diagnosis of breast tumors on US images [J]. Academic Radiology， 2003， 10（2）： 189?197.
[3] 李晓峰.基于超声图像的乳腺癌计算机辅助诊断关键技术研究[D].哈尔滨：哈尔滨工业大学，2008.
[4] 高超，须文波，孙俊.新的强高斯噪声自适应滤波方法[J].计算机工程与应用，2011（28）：10?12.
[5] CHANG Ruey?feng， WU Wen?jie， MOON W K， et al. Improvement in breast tumor discrimination by support vector machines and speckle?emphasis texture analysis [J]. Ultrasound in Medicine & Biology， 2003， 29（5）： 679?686.
[6] HUANG Yu?len， CHEN Dar?ren， LIU Ya?kuang. Breast cancer diagnosis using image retrieval for different ultrasonic systems [C]// Proceedings of 2004 International Conference on Image Processing. [S.l.]： ICIP， 2004， 5： 2957?2960.
[7] GARRA B S， KRASNER B H， HORII S C， et al. Improving the distinction between benign and malignant breast lesions： the value of sonographic texture analysis [J]. Ultrasonic Imaging， 1993， 15（4）： 267?285.
[8] KUO W?J， CHANG R?F， LEE C C， et al. Retrieval technique for the diagnosis of solid breast tumors on sonogram [J]. Ultrasound in Medicine & Biology， 2002， 28（7）： 903?909.
[9] 莫宏伟，郭茂祖，毕晓君.人类免疫系统仿真与建模研究综述[J].计算机仿真，2008（1）：6?9.
[10] TARAKANOV A O， NICOSIA G. Foundations of immuno?computing [C]// Proceedings of First IEEE Symposium on Foundations of Computational Intelligence. [S.l.]： FOCI， 2007： 210?221.
[11] PARSHANI R， CARMI S， HAVLIN S. Epidemic threshold for the SIS model on random networks [J]. Physical Review Letters， 2010， 122： 112?114.
[12] 李男.基于PCA的乳腺肿块辅助诊断方法研究[D].沈阳：沈阳工业大学，2013.
表1 实验结果
由于原始的支持向量机仅靠参数C与参数γ的排列组合使用网格搜寻法（Grid Search），最多可能执行999 000次（C的范围介于1～1 000，每次增加1 ； γ的范围介于0.001～0.999，每次增加0.001），再加上使用30纬特征使得执行次数较大。而本文提出的方法在较少的循环数量级上就找到了合适参数，并且将参数与特征联合进行优化，与文献[1]相比使用较少特征取得了较好的效果。筛选出的特征数量在5～7个之间，同时免疫算法设置的合适C和γ参数保证了SVM在较低执行次数下就取得较好结果。
如图6所示，在特征筛选准确度与效率方面，通过与常用的PCA降纬方法相比，采用统一的分类器?支持向量机，分别使用以下3种方法，采用本文提出的免疫算法筛选特征；采用PCA算法对特征数据降纬；不降纬，直接将特征数据送入分类器。从以下常用的评价指标做了对比[1]，ROC曲线图见图6。
[Accuracy=TP+TN/TP+TN+FP+FNSenitivity=TP/TP+FNSpecificity=TN/TN+FPPositivePredictiveValue=TP/TP+FPNegativePredictiveValue=TN/TN+FN]
图6 本文方法与PCA及本文方法ROC曲线图
5 结 论
本文使用了人工免疫算法结合支持向量机对超声波乳房肿瘤图像进行分类。通过人工免疫算法进行特征筛选并获取支持向量机的最优参数，使支持向量机在不影响正确率前提下降低分类时所花费的时间。由实验结果数据可知，利用人工免疫演算法先筛选特征的步骤能大幅降低支持向量机因计算冗余特征值所耗费的时间。而用来决定径向基核函数的参数C与γ可以大幅缩短支持向量机的执行次数。除了本文方法外，未来可以考虑采用由其他生物免疫系统概念发展出来的方法，如免疫算法与其他著名算法相结合的应用，如与基因算法结合的免疫基因演算法（Immune Genetic Algorithm）、与粒子群算法结合的免疫粒子群演算法（Immune Particle Swarm Algorithm）和与蚁群算法结合的免疫蚁群算法（Immune?ant Colony Algorithm）等。
参考文献
[1] 李晓峰.基于支持向量机的超声乳腺肿瘤图像计算机辅助诊断系统[J].光电子·激光，2008（1）：65?67.
[2] CHANG Ruey?feng， WU Wen?jie， MOON W K， et al. Support vector machines for diagnosis of breast tumors on US images [J]. Academic Radiology， 2003， 10（2）： 189?197.
[3] 李晓峰.基于超声图像的乳腺癌计算机辅助诊断关键技术研究[D].哈尔滨：哈尔滨工业大学，2008.
[4] 高超，须文波，孙俊.新的强高斯噪声自适应滤波方法[J].计算机工程与应用，2011（28）：10?12.
[5] CHANG Ruey?feng， WU Wen?jie， MOON W K， et al. Improvement in breast tumor discrimination by support vector machines and speckle?emphasis texture analysis [J]. Ultrasound in Medicine & Biology， 2003， 29（5）： 679?686.
[6] HUANG Yu?len， CHEN Dar?ren， LIU Ya?kuang. Breast cancer diagnosis using image retrieval for different ultrasonic systems [C]// Proceedings of 2004 International Conference on Image Processing. [S.l.]： ICIP， 2004， 5： 2957?2960.
[7] GARRA B S， KRASNER B H， HORII S C， et al. Improving the distinction between benign and malignant breast lesions： the value of sonographic texture analysis [J]. Ultrasonic Imaging， 1993， 15（4）： 267?285.
[8] KUO W?J， CHANG R?F， LEE C C， et al. Retrieval technique for the diagnosis of solid breast tumors on sonogram [J]. Ultrasound in Medicine & Biology， 2002， 28（7）： 903?909.
[9] 莫宏伟，郭茂祖，毕晓君.人类免疫系统仿真与建模研究综述[J].计算机仿真，2008（1）：6?9.
[10] TARAKANOV A O， NICOSIA G. Foundations of immuno?computing [C]// Proceedings of First IEEE Symposium on Foundations of Computational Intelligence. [S.l.]： FOCI， 2007： 210?221.
[11] PARSHANI R， CARMI S， HAVLIN S. Epidemic threshold for the SIS model on random networks [J]. Physical Review Letters， 2010， 122： 112?114.
[12] 李男.基于PCA的乳腺肿块辅助诊断方法研究[D].沈阳：沈阳工业大学，2013.
