一种用于乳腺癌诊断的免疫分类算法

邓泽林^{1, 2}，谭冠政¹，叶吉祥^{1, 2}，范必双^{1, 2}

(1. 中南大学 信息科学与工程学院，湖南 长沙，410083；

2. 长沙理工大学 计算机与通信工程学院，湖南 长沙，410076)

摘  要：基于人工免疫识别系统AIRS(Artificial immune recognition system)和核函数提出免疫分类算法Kernel-AIRS。Kernel-AIRS遵循AIRS算法框架，利用核函数将输入空间投影到高维核空间，以核空间距离来度量抗体-抗原的亲和度，提高算法对非线性可分问题的分类准确率。采用Kernel-AIRS定义核空间距离测量方法和规一化方法，分析抗体刺激度和核函数参数与分类准确率之间的关系，研究属性缺失样本对算法分类准确率的影响，并应用Kernel-AIRS算法诊断乳腺癌，分类准确率采用10次交叉验证评价。研究结果表明：Kernel-AIRS算法对排除属性缺失样本数据集分类的准确率为97.3%，对包含属性缺失样本数据集分类的准确率为96.9%，分类准确率较高，适用于乳腺癌的诊断。

关键词：人工免疫识别系统；核函数；分类算法；医疗诊断；乳腺癌

中图分类号：TP301          文献标志码：A         文章编号：1672-7207(2010)04-1485-06

An immune classification algorithm for breast cancer diagnosis

DENG Ze-lin^{1, 2}, TAN Guan-zheng¹, YE Ji-xiang^{1, 2}, FAN Bi-shuang^{1, 2}

 (1. School of Information Science and Engineering, Central South University, Changsha 410083, China;

2. School of Computer and Communication Engineering, Changsha University of Science and Technology,
 Changsha 410076, China)

Abstract: Based on an artificial immune recognition system (AIRS) and a kernel function, Kernel-AIRS algorithm was proposed, which followed the AIRS algorithm framework. Using Kernel function to project input space into high dimensional kernel space, the affinity of antibody and antigen was calculated in the kernel space to improve the classification accuracy for the non-linear problems. Kernel space distance computation method and normalization method were defined by Kernel-AIRS, the relationship between the parameters of simulation level and kernel function and classification accuracy was analyzed, and the effect on the classification accuracy of missing attribute samples was discussed. Kernel-AIRS was applied to diagnosis breast caner samples in Wisconsin breast cancer dataset (WBCD), and the classification accuracy was assessed by 10 fold cross validation. The results show that, using this algorithm, the accuracy rates are 97.3% and 96.9% for excluding missing attributes samples and including missing attributes samples respectively, and the classification accuracy is high and applicable for breast cancer diagnosis.

Key words: artificial immune recognition system; kernel function; classification algorithm; medical diagnosis; breast cancer

快速确定乳腺癌肿瘤是良性肿瘤还是恶性肿瘤，对于及时采取正确的医疗手段是至关重要的，应用分类算法对乳腺癌快速进行诊断已经成为当前机器学习的热点。人工免疫系统是一种自适应系统，遵循免疫理论、原理和模型，是针对问题求解的软计算技术^[1]。由于它具备强大的学习能力和信息处理能力，已被广泛应用于遥感图像分类、函数优化、无监督分类与识别等^[2-6]。基于免疫的分类算法具有良好的分类性能，已被应用于乳腺癌的诊断。Watkins等^[7]提出分类算法AIRS(Artificial immune recognition system)，对乳腺癌数据集WBCD(Wisconsin breast cancer dataset)诊断的准确率为97%(采用10次交叉验证，记为10?CV，Weka 2004)。AIRS直接在输入空间中对样本进行分类，对于线性不可分问题的分类准确率不高；Kevin等^[8]基于免疫进化提出了精简分类器算法(SAIS)，对乳腺癌的诊断准确率为96.6%(10?CV，2007)。SAIS利用克隆、变异等操作来调整抗体在样本空间的位置，利用抗体对训练集的分类准确率作为目标函数，算法需要执行大量的克隆变异操作和求解分类准确率来评价分类器，算法执行效率较低。其他机器学习分类算法也被大量应用于乳腺癌的诊断，其诊断准确率得到逐步提高。Lukasz等^[9]利用区分模式的多平面方法，获得了93.5%(50%训练、50%测试)和95.9%(67%训练、33%测试)的准确率；Zhang^[10]利用典型样本来进行学习分类，获得了93.7%(55%训练、45%测试)的准确率；Hamilton等^[11]使用规则推导方法(RIAC)获得96%(10?CV)的准确率；Ster等^[12]利用线性判别分析 (LDA)获得96.8%(10?CV)的准确率；Goodman等^[13]利用优化学习量化方法(Optimized-LVQ)获得了96.7% (10?CV)的准确率，利用Big-LVQ获得96.8%(10?CV)的准确率；Abonyi等^[14]利用有监督模糊聚类(SFC)获得95.57%(10?CV)的准确率；Bennett等^[15]利用支持向量机(SVM)获得了97.2%(5?CV)的准确率。

但是，当前基于免疫原理的分类算法存在共同的缺点：抗体-抗原的亲和度是通过在形状空间计算抗体-抗原距离得到的，即抗原模式的识别是在输入样本空间中进行的，这样会限制算法解决非线性可分问题的能力。本文作者在AIRS算法框架内引入核函数，通过核函数将输入空间投影到高维核空间，并在核空间中计算抗体-抗原的亲和度，避免了AIRS直接在输入空间中计算抗体-抗原的距离，增强了算法对于非线性可分问题的分类能力，使诊断结果更加可靠。

1  免疫分类算法

1.1  AIRS算法框架

Watkins等^[7]认为AIS(Artificial immune system)是一种有监督分类器，基于RLAIS(Resource limited AIS)提出了分类算法AIRS。AIRS由人工识别球ARB (Artificial recognition ball)组成，ARB需根据它们的刺激程度来确定B细胞，没有B细胞的则被清除，这样可以减少网络的复杂性和抑制网络规模。对训练集中的每个抗原，AIRS都进行一次式(one-shot)训练，当所有的抗原训练完毕时，可得到记忆细胞池，该记忆细胞池即为免疫分类器。最后，用该分类器对测试集进行kNN(k nearst neighbor)分类。AIRS算法如下^[16]。

步骤1  加载抗原{g}，随机初始化ARB池P和记忆细胞池M；

步骤2  对每一个抗原g_i，计算与M中的每一个抗体b_j的刺激度；

步骤3  确定刺激度最大的抗体m，克隆并变异，将变异的细胞放入P中；

步骤4  根据刺激度，在P中执行资源竞争；

步骤5  对P中的抗体对执行克隆、变异操作，使P进化；

步骤6  抗体g_i的训练结束，确定对g_i刺激度最大的抗体b_m，并将b_m放入M中，并确定是否需要移出m，以此来使M进化；

步骤7  所有抗原训练完毕，执行步骤(8)，否则，跳至步骤(2)；

步骤8  应用M对测试集中的样本进行kNN分类。

1.2  免疫分类算法Kernel-AIRS原理与流程

1.2.1  核函数

AIRS通过Euclidean距离来决定抗体-抗原的亲和度，由此来识别抗原样本，决定样本的类标签。该过程仅依靠输入特征空间来进行计算，这限制了算法解决非线性问题的能力。对于非线性问题，通过将输入特征投影到高维空间，使样本在高维空间线性可分，从而提高算法分类准确率。可以通过应用核函数将输入样本投影到高维空间。

定义1  对"x，y?X，核函数定义为^[17]：

             (1)

其中：表示内积；是将输入特征空间向高维核空间转换的映射。常用的核函数如下^[18]。

(1) Guass径向基核函数(RBF)：

         (2)

(2) 多项式核函数：

，     (3)

(3) S形核函数：

       (4)

本文算法选择常用的Guass径向基核函数(RBF)，即式(2)所示的核函数。

1.2.2  核空间距离及规一化

在核空间中，不需知道其特征结构，只需要利用核空间内积来表示决策规则即可。在AIRS中，距离是计算亲和度、刺激度进而决定决策规则的重要标准，因此，定义2个输入样本x和y在核空间中距离是算法的关键。定义输入样本x和y在核空间中的距离为：

         (5)

利用AIRS算法框架进行训练，抗体的刺激度必须保证在区间[0，1]，即抗体-抗原的距离应该保证在区间[0，1]，因此，需要将核空间距离规一化。

利用工作数据集构造2个向量v_min和v_max。其中：v_min中每个属性值是所有样本中对应属性值的最小值；同样，v_max中每个属性值是所有样本中对应属性值的最大值。故v_min和v_max间的距离是所有样本对距离的最大值d_max，其表达式为：

   (6)

则任意2个输入向量x和y在核空间中的规一化距离d_norm为：

d_norm(x，y)=d(x，y)/d_max         (7)                         

通过式(7)的转换，可以保证任意2个向量的核空间规一化距离d_norm?[0，1]。抗体-抗原之间的亲和   度为：

f(g，b)=1-d_norm(g，b)           (8)

1.2.3  Kernel-AIRS算法流程

通过在AIRS框架中使用式(7)来计算距离，使得算法可以在核空间中进行模式匹配和识别，记此改进算法为Kernel-AIRS，算法参照AIRS^[7]步骤。其主要步骤描述如下。

步骤1  初始化。加载数据，得到抗原集合{g_i}，规范化所有抗原样本，根据下式计算亲和度阀值：

            (9)

其中：n为抗原的个数。算法随机创建记忆细胞池M和ARB池P，选取1个抗原为当前抗原g。

步骤2  抗原表示。对当前抗原模式g，按如下步骤执行：

(1) 克隆扩展。对于M中的每一个细胞，若该细胞与g有相同的类标签，则算出其与该抗原的亲和度，选择亲和度最高的记忆细胞c_m进行克隆。

(2) 亲和度成熟。对于每一个c_m克隆的后代细胞，执行变异，并放入P中。变异方法是对表示细胞的向量的每个分量产生1个随机数r，若r小于算法定义的变异率，则用新的随机值替代该分量，否则，该分量的值不变。这样，可以使细胞在一定的概率内变异，防止新细胞与老细胞间的差异过大。

(3) 资源竞争。按照下式为每个ARB分配资源。

         (10)

其中：a_res为ARB的资源数；a_c为ARB的类标签；r_total为算法定义的总资源数；n_c为类的个数。通过竞争，回收刺激度低的ARB的资源，没有分配到资源的ARB将会消亡，最终达到控制细胞群体规模。按式(11)计算P中每个B细胞b的刺激度b_stim。

           (11)

同时，b_stim需要按式(12)进行规一化：

         (12)

其中：b_c和g_c分别表示抗体b细胞所属的分类和抗原g所属的分类；s_min和s_max分别为所有抗体的最小刺激度和最大刺激度。根据式(13)计算第i类抗体的平均刺激度：

            (13)

其中：B_i表示i类B细胞集合。

(4) 克隆扩展和亲和度成熟。根据刺激度，随机选择P的子集来进行克隆和变异。

(5) 循环。若所有的类的抗体细胞的平均刺激度满足式(14)，则说明所有的抗体细胞都得到了足够的刺激，针对该抗原g的训练结束(其中，s_t为用户定义的抗体刺激度阀值)。

s_i≥s_t, 1≤i≤n_c                (14)

如果每个类的B细胞的平均刺激度小于指定的s_t，则从步骤2的第(3)步重复执行。

(6) 记忆细胞竞争。循环完毕后可以得到与g同类且亲和度最高的抗体，记为b_best，如果d_norm(b_best，g)＜d_norm(c_m，g)，则M=M?{b_best}，如果d_norm(b_best，c_m)＜a_t，则M=M-{c_m}。

步骤3  确定下一个抗原为当前抗原，重复步骤2，直到所有的抗原表示完毕为止，最终的M为免疫分类器。

步骤4  利用记忆细胞池M进行kNN分类，用式(7)计算距离。

2  实验结果与讨论

乳腺癌的数据集WBCD^[10]来自于UCI机器学习实验室，由Wisconsin大学Madison医学院的Wolberg博士收集。

WBCD共有699个样本，9个属性，2个类。其中，一个类有458个样本(65.5%)，另一个类有241个样本(34.5%)。在这些样本中有16个样本存在属性缺失，属性完整的样本有683个。对于诊断结果准确性的比较有2种方案：排除属性缺失样本数据集的分类准确率和包含属性缺失样本数据集的分类准确率。

2.1  分类评价方法

Kernel-AIRS采用式(15)来度量数据集T的分类准确率A(T)：

                (15)

式中：S_c为正确分类样本个数；S为样本总个数。为使分类结果更加客观，消除因为随机选取训练集带来的偏差，大多数研究者采用k次交叉验证方法来评价分类效果。

k次交叉验证需要将整个数据集T划分为k个大小相等的集合T_i，满足：

且         (16)

其中：；1≤i≤k；1≤j≤k。

在此划分基础上，运行算法k次，每次运行时挑选其中未组合的k-1个子集作为训练集来进行训练，剩下的1个子集作为测试集。每次训练完毕得到相应的分类器，用该分类器对测试集进行分类测试得到相应的分类结果。k次交叉验证的结果是k次分类结果的均值。Kernel- AIRS采用10次交叉验证来评价分类准确率。

2.2  参数设定

使用Kernel-AIRS需设置算法运行参数，主要包括亲和度阀值、变异概率、资源数、刺激度阀值s_t和核函数参数c。其中：s_t与c对于提高分类准确率是至关重要的。刺激度越大，抗体与抗原间的距离越小，训练集的匹配度越高，但可能造成过适应，降低分类预测能力；刺激度越小，则距离越大，抗体的识别能力越弱，影响分类准确率；在s_t一定的条件下，c的调整会显著影响分类准确率。参数设置如表1所示。

取s_t?[0.8，0.9]，c的取值为[10，30]。s_t从0.8开始每次增加0.1，c从10开始每次增加1的方式来进行组合，不同的组合与分类准确率之间的关系见  表2。

由于Kernel-AIRS算法需要测试排除有缺失属性样本和包含有缺失属性样本2种情况，因此，相应地选择不同的参数组合(s_t，c)，分别是(0.89，18)和(0.89，23)。

表1  Kernel-AIRS使用参数

Table 1  Used parameters of Kernel-AIRS

表2  c与s_t和分类准确率的关系

Table 2  Relationship between c, s_t and classification accuracy

2.3  算法比较

2.3.1  排除缺失属性的样本

排除WBCD中属性缺失的样本，保留683个样本，用10次交叉验证，比较结果如表3所示。

表3  不包括缺失属性的样本时Kernel-AIRS与其他算法^[19]准确率的比较

Table 3  Comparison between Kernel-AIRS and other algorithms excluding missing attribute samples

2.3.2  包含属性缺失的样本

由于WBCD中缺失属性的样本很少，只占总样本数的2.3%，故考虑最简单的处理方法，即忽略缺失的属性。算法采用10次交叉验证，结果见表4。

表4  包括缺失属性的样本时Kernel-AIRS与其他算法^[8]准确率的比较

Table 4  Comparison between Kernel-AIRS and other algorithms including missing attribute samples

2.4  讨论

从表3和表4所示的算法比较结果可知： Kernel- AIRS算法取得了较高的分类准确率，特别是对于排除属性缺失的数据集的分类准确率达到了97.3%，是参与比较的算法中性能最好的，而对于包含属性缺失样本的数据集，分类准确率则有所下降，为96.9%，其主要原因是对缺失属性的处理不当，忽略了缺失属性。由此可见：少数几个样本的处理不当可以影响到整个分类准确率，因此，采取有效措施来处理缺失的属性以提高分类预测的准确率是必要的，这对于存在大量属性缺失的数据集是非常重要的。

从表2可知：刺激度与核函数的参数的设定对于提高分类准确率也有很大的影响。一般地，刺激度的设定为0.85左右，而c的选取为20左右是比较好的，这样可以有效地减少搜索范围。刺激度对于改善算法性能是重要的，刺激度设置较高，抗体-抗原间距离较近，使得抗体细胞池规模较大，容易造成过适应。为了进一步提高分类准确率，需要减少抗体细胞数量，使抗体细胞间的距离变大，从而在刺激度较小的情况下依然能够保持抗体细胞较强的识别能力。

Kernel-AIRS算法没有采取相应的特征选取、属性权值等预处理方法，而有效的数据预处理方法对于提高算法分类准确率有显著影响。Kernel-AIRS算法通过结合数据预处理方法，可以进一步提高算法分类准确率。

3  结论

(1) 为了提高免疫分类算法对于非线性问题的分类准确率，基于核函数和AIRS算法提出了免疫分类算法Kernel-AIRS。

(2) 通过高斯径向基核函数把输入空间投影到高维核空间，使得输入空间中的线性不可分样本变成线性可分样本。

(3) 通过修改AIRS算法中距离的计算方法，利用核空间距离来计算抗体-抗原亲和度，增强了算法对非线性可分问题的分类能力，提高了算法的分类准  确率。

(4) 利用Kernel-AIRS算法对乳腺癌数据集进行诊断，并将诊断结果与其他算法进行比较，结果表明该算法在同类算法中具有良好的性能，适用于乳腺癌的诊断。

参考文献：

[1] Timmis J, Hone A, Stibor T, et al. Theoretical advances in artificial immune systems[J]. Theoretical Computer Science, 2008, 403(1): 11-32.

[2] 钟燕飞, 张良培, 李平湘. 基于多值免疫网络的多光谱遥感影像分类[J]. 计算机学报, 2007, 30(12): 2181-2188.

ZHONG Yan-fei, ZHANG Liang-pei, LI Ping-xiang. Classification of multi-spectral remote sensing image based on multiple-valued immune network[J]. Chinese Journal of Computers, 2007, 3(12): 2181-2188.

[3] 赵云丰, 付冬梅, 尹怡欣, 等. 一种改进的人工免疫网络优化算法及其性能分析[J]. 自然科学进展, 2009, 19(4): 434-444.

ZHAO Yun-feng, FU Dong-mei, YIN Yi-xing, at el. An improved artificial immune network optimized algorithm and its performance analysis[J]. Progress in Natural Science, 2009, 19(4): 434-444.

[4] 龚涛, 蔡自兴, 夏洁, 等. 分布式人工免疫系统的鲁棒性归约模型[J]. 中南大学学报: 自然科学版, 2007, 38(5): 956-961.

GONG Tao, CAI Zi-xing, XIA Jie, at el. Reduction model of robustness for distributed artificial immune system[J]. Journal of Central South University: Science and Technology, 2007, 38(5): 956-961.

[5] 公茂果, 焦李成, 马文萍, 等. 基于流形距离的人工免疫无监督分类与识别算法[J]. 自动化学报, 2008, 34(3): 367-375.

GONG Mao-guo, JIAO Li-cheng, MA Wen-ping, at el. Unsupervised classification and recognition using an artificial immune system based on manifold distance[J]. Acta Automatica Sinica, 2008, 34(3): 367-375.

[6] 彭凌西, 刘晓洁, 李涛, 等. 一种基于免疫的监督式分类算法[J]. 四川大学学报: 工程科学版, 2008, 40(2): 101-106.

PENG Ling-xi, LIU Xiao-jie, LI Tao, et al. An immune based supervised classifier[J]. Journal of Sichuan University: Engineering Science, 2008, 40(2): 101-106.

[7] Watkins A, Timmis J, Boggess L. Artificial immune recognition system (AIRS): An immune-inspired supervised learning algorithm[J]. Genetic Programming and Evolvable Machines, 2004, 5(3): 291-317.

[8] Kevin L, France C, Christopher C, et al. Generating compact classifier systems using a simple artificial immune system[J]. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, 2007, 37(5): 1344-1356.

[9] Lukasz J, Thomas F, Adam K. Classification of breast cancer malignancy using cytological images of fine needle aspiration biopsies[J]. Applied Image Processing, 2008, 18(1): 75-83.

[10] ZHANG Jian-pin. Selecting typical instances in instance-based learning[C]//Proceedings of the Ninth International Machine Learning Conference, Aberdeen: Morgan Kaufmann Publishers, 1992: 470-479.

[11] Hamilton H J, Shan N, Cercone N. Riac: A rule induction algorithm based on approximate classification[R]. Saskatchewan: University of Regina, 1996: 1-10.

[12] Ster B, Dobnikar. Neural networks in medical diagnosis: Comparison with other methods[C]//Proceedings of the International Conference on Engineering Application of Neural Networks. Turku: Syst Eng Assoc, 1996: 427-430.

[13] Goodman D E, Boggess L, Watkins A. Artificial immune system classification of multiple-class problems[C]//Proceedings of the Artificial Neural Networks in Engineering. New York: ASME Press, 2002: 179-184.

[14] Abonyi J, Szeifert F. Supervised fuzzy clustering for the identification of fuzzy classifiers[J]. Pattern Recognition Letters, 2003, 24(14): 2195-2207.

[15] Bennett K P, Blue J A. A support vector machine approach to decision trees[C]//Proceedings of the IEEE International Joint Conference on Neural Networks, Anchorage: IEEE, 1998: 2396-2401.

[16] Sadik K, Bekir H A, Halife K, et al. Medical application of information gain-based artificial immune recognition system (IG-AIRS): Classification of microorganism species[J]. Expert Systems with Applications, 2009, 36(1): 5168-5172.

[17] Seral O, Salih G, Sad?k K, et al. Use of kernel functions in artificial immune systems for the nonlinear classification problems[J]. IEEE Transactions on Information Technology in Biomedicine, 2009, 13(4): 621-628.

[18] Muller K R, Mika S, Ratsch G, et al. An introduction to kernel-based learning algorithms[J]. IEEE Transactions on Neural Networks, 2001, 12(2): 181-201.

[19] Wlodzislaw D. Datasets used for classification: Comparison of results[EB/OL]. [2009-10]. http://www.is.umk.pl/projects/data- sets.html.

收稿日期：2010-04-10；修回日期：2010-06-20

基金项目：国家自然科学基金资助项目(60874070)；湖南省自然科学基金资助项目(06J50109)

通信作者：邓泽林(1977-)，男，湖南临澧人，博士研究生，讲师，从事人工免疫、进化计算等研究；电话：0731-85258463；E-mail: zl_deng@sina.com

(编辑 赵俊)