一种改进的免疫算法及其在文本分类中的应用课件.ppt

1、一种改进的免疫算法及一种改进的免疫算法及其在文本分类中的应用其在文本分类中的应用张启蕊广东药学院分类算法分类算法lKNNlNave BayeslSVMl决策树l神经网络l免疫应答免疫应答l初次免疫应答l当抗原第一次入侵生物体时，引发初次免疫应答，免疫系统通过学习产生记忆细胞 l二次免疫应答l当相同类型的抗原再次入侵时，引发二次免疫应答，免疫系统通过记忆细胞识别抗原l二次免疫应答的时间远远小于初次免疫应答的时间免疫算法免疫算法l从广义的角度而言，凡是基于生物学免疫原理的算法都可以称为免疫算法。l免疫算法具有免疫系统的学习、记忆、识别和动态平衡等特点。l已得到成功应用的免疫算法有很多，例如独特性网

2、络、B细胞网络、否定选择算法、免疫Agent算法、克隆选择算法、免疫遗传算法等。免疫与分类的关系免疫与分类的关系l免疫的本质是对“己”与“非己”进行区分，实际上相当于两类分类。l对分类而言，借鉴了免疫系统的学习记忆和识别的功能。l文本分类的训练过程相当于初次免疫应答，分类过程相当于二次免疫应答，对“本类”和“非本类”进行识别。基于克隆选择原理的免疫算法基于克隆选择原理的免疫算法lDe Castro和Von Zuben提出了一种基于克隆选择原理的免疫算法（Clonal Selection Algorithm,CSA）l其基本思想是只有那些与抗原有较高亲和度的细胞才获得增殖分化，具有低亲和度的细胞

3、将退化。l在问题求解过程中，抗原对应训练样本，B细胞对应可能解，包括一般细胞、新生细胞和记忆细胞。l一般细胞用来储存多样化的解；新生细胞用来对一般细胞进行替换，防止陷入局部收敛；记忆细胞用来记录最优解。基于抗体浓度的克隆选择算法基于抗体浓度的克隆选择算法（Clonal Selection Algorithm Based on Antibody Density,CSABAD）l浓度控制是免疫系统赖以保持抗体多样性的重要机制。在抗原侵入生物体，产生免疫应答的过程中，T细胞起着控制和调节抗体浓度的作用。l抗体浓度指的是与某一抗体相同或相近的抗体在抗体群中所占的比例，亲和度相同的抗体被看作同一抗体。通

4、过抗体浓度控制机制，浓度高的抗体被抑制，浓度低的抗体被促进，以此来避免免疫系统被同种抗体所垄断，保证抗体种类的多样性。CSABAD算法流程图算法流程图参数设置参数设置l定义B细胞xi与某一抗原dj的亲和度函数f(xi,dj)为：(1)lB细胞与N个抗原的亲和度f(xi)为：(2)22),(jkikjkikjijidxdxdxdxfNdxfxfNjjii1),()(lB细胞群对应的M个抗体构成一个非空集合Q，规定抗体f(xi)在集合Q上的矢量距为 (3)l则抗体浓度D(xi)可由下式表示：(4)l抗体选择概率P(xi)为 (5)Mjjiixfxfx1|)()(|)(MjjiiixfxfxxD1|

5、)()(|1)(1)(MiMjjiMjjiMiiiixfxfxfxfxxxP1111|)()(|)()(|)()()(l把l个免疫反应细胞按照亲和度大小降序排列，那么第i个细胞的克隆数目Ni为 (6)l为了增进记忆细胞群的全局优化能力，对B细胞进行变异操作，采取各特征等概率变异的方式，变异概率PM由下式计算 (7)本文实验中，和分别取0.05和0.01。ilNi/2)()()(iixfxPMCSABAD在文本分类中的实现在文本分类中的实现l第一步：从训练集中随机抽取M个训练文本作为初始B细胞群，根据(2)式计算每个B细胞与全体训练文本的亲和度，取亲和度最高的n个B细胞作为记忆细胞群；l第二步：

6、计算一般B细胞群中每个训练文本与全体训练文本的亲和度，所有亲和度作为一个向量Fj保存，此处的亲和度即为抗体；l第三步：根据(5)式计算抗体的选择概率，浓度低的抗体具有较高的选择概率；l第四步：根据抗体选择概率从一般B细胞群中选取l个免疫反应细胞（即训练样本），组成集合S，作为克隆变异的基础；l第五步：对l个细胞（训练样本）进行克隆操作，形成新的B细胞群S1，克隆数目由式(6)决定，亲和度大的细胞获得较多的克隆数目；l第六步：对S1中的每个细胞进行变异操作，形成B细胞群S2，每个基因的变异概率由式(7)决定，可以看出变异概率与亲和度成反比，此时的细胞经过变异操作后，已不同于原始训练样本；l第七步

7、：若S2中B细胞的最高亲和度高于记忆细胞群中的最低亲和度，则用前者替代后者作为记忆细胞，对记忆细胞群进行更新；l第八步：随机生成r个细胞，取代一般B细胞群中具有最低亲和度的r个细胞，以提高全局优化能力，避免陷入局部最优；l第九步：判断是否满足结束条件，如不满足，转到第二步重复执行。实验设置实验设置l用CSABAD方法构建一个分类器以验证该方法的文本分类性能。l实验数据集采用卡内基梅隆大学的20_newsgroups中的四个类别comp.graphics、misc.forsale、rec.sport.baseball和sci.electronics，每个类别包含1000篇文本，随机取其中700篇

8、作为训练文本，其余300篇作为测试文本。l文本用向量空间模型表示，特征权重使用TFIDF公式计算，分类性能采用综合性能指标F1来衡量。实验设置实验设置l在训练阶段，设定B细胞群含100个细胞，其中15个为记忆细胞，其余85个为一般细胞。l免疫反应细胞取10个，每一代完成时随机生成10个B细胞取代原来B细胞群中亲和度最低的10个细胞，作为下一代种群的进化基础。l记忆细胞进化的最大代数取100。实实验验结结果果l随着种群代数增加，各类别F1逐渐增长，当增长到一定代数时，F1达到最大。l随着代数的继续增长，F1趋于平稳，并稍微呈现下降的趋势。之所以出现性能下降，主要是因为随着种群代数持续增加，分类器

9、对训练文本过分依赖，导致训练过度。l类别comp.graphics、misc.forsale、rec.sport.baseball和sci.electronics分别在61代、48代、53代和50代时F1值达到最大，为84.35、79.25、78.62和80.29l由此可以看出，CSABAD方法可以快速收敛于最佳解。l另外，本次实验中类别comp.graphics在刚开始初始化时，保留的记忆细胞群的分类性能很差，但是，使用CSABAD算法，仍然可以快速收敛，在30代时性能就已趋于稳定。l事实上，基于抗体浓度的克隆选择算法中记忆细胞的替代是基于细胞亲和度的基础上进行的，只有S2中B细胞的最高亲和度高于记忆细胞群中的最低亲和度时，才用前者细胞替代后者作为记忆细胞，对记忆细胞群进行更新。因此，最能反应记忆细胞进化速度的是记忆细胞群的平均亲和度，而能达到最优性能的记忆细胞群也是在平均亲和度发生变化的转折点取得的。l上图反映了类别comp.graphics的亲和度随进化代数的变化情况。性能比较性能比较实验结果显示，CSABAD的整体分类结果优于Rocchio和Nave Bayes方法，和SVM的性能相当，CSABAD在文本分类中表现出良好的分类性能。