第14卷第5期 智能系统学报 Vol.14 No.5 2019年9月 CAAI Transactions on Intelligent Systems Sep.2019 D0:10.11992/tis.201809022 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20181227.1144.002.html 利用MSA多目标优化的置信规则库分类算法 林锦，胡家琛，刘莞玲，吴英杰 (福州大学数学与计算机科学学院，福建福州350116) 摘要：现有基于置信规则库的分类系统的分类准确率和效率受到系统参数设置以及规则库结构合理性的影 响。为了寻找到最佳的参数值和最优的规则库结构，本文结合多目标免疫系统算法(multiobjective immune sys- tem algorithm,MISA)提出利用MISA多目标优化的置信规则库分类算法。该方法融合特征属性约简思想和差 分进化算法思想建立训练模型，采用多目标免疫系统算法对系统复杂度和分类准确率进行多目标优化，从而寻 找到分类模型的最优解。在实验分析中，首先将本文提出的置信规则库多目标分类系统MSA-BRM和置信规 则库分类系统的实验结果进行对比，从复杂度和准确率两个维度说明本文方法的有效性。同时还将本文方法 与现有的其他分类方法进行比较，验证本文方法的可行性和有效性。实验结果表明，本文方法能够有效地对基 于置信规则库的分类系统的准确率和复杂度进行多目标优化。 关键词：置信规则库：分类系统：多目标优化；多目标免疫系统算法：帕累托优化：差分进化；自适应网格：特征 属性约减 中图分类号：TP18文献标志码：A文章编号：1673-4785(2019)05-0982-09 中文引用格式：林锦，胡家琛，刘莞玲，等.利用MISA多目标优化的置信规则库分类算法.智能系统学报，2019,14(5)： 982-990. 英文引用格式：LINJin,,HUJiachen,LIU Wanling,.etal.Belief rule base classification algorithm using MISA multi--objective op- timization[JI.CAAI transactions on intelligent systems,2019,14(5):982-990. Belief rule base classification algorithm using MISA multi-objective optimization LIN Jin,HU Jiachen,LIU Wanling,WU Yingjie (College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350116,China) Abstract:The efficiency and accuracy of a belief rule base(BRB)classification system are limited to the determination of the systematic parameters and the structure of the rule base.In this study,we propose the usage of a BRB classifica- tion algorithm,i.e.,the multi-objective immune system algorithm(MISA),along with multi-objective optimization to determine the optimal parameters and the structure of the rule base.This method simplifies the characteristic attributes using a differential evolution algorithm to develop a training model and subsequently uses MISA to optimize the system- atic complexity and the classification accuracy for identifying an optimal solution for the classification model.In the ex- periment,we initially compare the results of the BRM-based MISA (MISA-BRM)and those of the BRB classification system with respect to their complexity and accuracy to present the benefits of our method.Further,we compare the res- ults with those of the existing classification methods to verify the feasibility and availability of the proposed method. The experimental results denote that the proposed method can effectively optimize the accuracy and complexity of the BRB classification system. Keywords:belief rule base(BRB);classification system;multi-objective optimization;MISA;Pareto optimal;differen- tial evolution;adaptive mesh;feature attribute reduction 收稿日期：2018-09-13.网络出版日期：2018-12-28 数据分类研究是数据挖掘领域的一个重要分 基金项目：国家自然科学基金项目(71501047,61773123)：福建 支，它主要通过已知类别的数据集构建出各类别 省自然科学基金项目(2015J01248). 通信作者：刘莞玲.E-mail:380509981@qq.com, 的特征空间，再将未知类别的数据映射到该特征
DOI: 10.11992/tis.201809022 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20181227.1144.002.html 利用 MISA 多目标优化的置信规则库分类算法 林锦，胡家琛，刘莞玲，吴英杰 （福州大学 数学与计算机科学学院，福建 福州 350116） 摘 要：现有基于置信规则库的分类系统的分类准确率和效率受到系统参数设置以及规则库结构合理性的影 响。为了寻找到最佳的参数值和最优的规则库结构，本文结合多目标免疫系统算法 (multiobjective immune system algorithm, MISA) 提出利用 MISA 多目标优化的置信规则库分类算法。该方法融合特征属性约简思想和差 分进化算法思想建立训练模型，采用多目标免疫系统算法对系统复杂度和分类准确率进行多目标优化，从而寻 找到分类模型的最优解。在实验分析中，首先将本文提出的置信规则库多目标分类系统 MISA-BRM 和置信规 则库分类系统的实验结果进行对比，从复杂度和准确率两个维度说明本文方法的有效性。同时还将本文方法 与现有的其他分类方法进行比较，验证本文方法的可行性和有效性。实验结果表明，本文方法能够有效地对基 于置信规则库的分类系统的准确率和复杂度进行多目标优化。 关键词：置信规则库；分类系统；多目标优化；多目标免疫系统算法；帕累托优化；差分进化；自适应网格；特征 属性约减 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)05−0982−09 中文引用格式：林锦, 胡家琛, 刘莞玲, 等. 利用 MISA 多目标优化的置信规则库分类算法 [J]. 智能系统学报, 2019, 14(5): 982–990. 英文引用格式：LIN Jin, HU Jiachen, LIU Wanling, et al. Belief rule base classification algorithm using MISA multi-objective optimization[J]. CAAI transactions on intelligent systems, 2019, 14(5): 982–990. Belief rule base classification algorithm using MISA multi-objective optimization LIN Jin，HU Jiachen，LIU Wanling，WU Yingjie (College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China) Abstract: The efficiency and accuracy of a belief rule base (BRB) classification system are limited to the determination of the systematic parameters and the structure of the rule base. In this study, we propose the usage of a BRB classification algorithm, i.e., the multi-objective immune system algorithm (MISA), along with multi-objective optimization to determine the optimal parameters and the structure of the rule base. This method simplifies the characteristic attributes using a differential evolution algorithm to develop a training model and subsequently uses MISA to optimize the systematic complexity and the classification accuracy for identifying an optimal solution for the classification model. In the experiment, we initially compare the results of the BRM-based MISA (MISA–BRM) and those of the BRB classification system with respect to their complexity and accuracy to present the benefits of our method. Further, we compare the results with those of the existing classification methods to verify the feasibility and availability of the proposed method. The experimental results denote that the proposed method can effectively optimize the accuracy and complexity of the BRB classification system. Keywords: belief rule base (BRB); classification system; multi-objective optimization; MISA; Pareto optimal; differential evolution; adaptive mesh; feature attribute reduction 数据分类研究是数据挖掘领域的一个重要分 支，它主要通过已知类别的数据集构建出各类别 的特征空间，再将未知类别的数据映射到该特征 收稿日期：2018−09−13. 网络出版日期：2018−12−28. 基金项目：国家自然科学基金项目 (71501047，61773123)；福建 省自然科学基金项目 (2015J01248). 通信作者：刘莞玲. E-mail：380509981@qq.com. 第 14 卷第 5 期 智 能 系 统 学 报 Vol.14 No.5 2019 年 9 月 CAAI Transactions on Intelligent Systems Sep. 2019
第5期 林锦，等：利用MISA多目标优化的置信规则库分类算法 ·983· 空间中，从而来确定其所属类别口。目前，数据分 共测试数据集来验证本文方法的有效性。 类主要应用于机器学习、模式识别、遗传算法、神 1相关概念 经网络、统计学、数据库、专家系统等领域。模糊 规则分类系统(fuzzy rule-based classification sys- 1.1 基于DE的置信规则库分类方法 tem,FRBCS)2.1广泛地用于求解分类问题。 置信规则库分类系统(BRBCS)由模糊规则库 FRBCS能够建立清晰的语义模型，具有良好的可 分类系统(FRBCS)在置信函数框架上扩展得来， 解释性，能够定性定量地处理专家信息。此后， 采用数据驱动方式构建规则库，规则库的规则条 Yang等提出了基于证据推理的置信规则库推 数即结构复杂度取决于前提属性个数和模糊区间 理方法，该方法以F-THEN规则库、模糊理论、D- 划分数。BRBCS的置信规则结构： S证据理论和决策理论等为基础，有效地利用不 (If x is AgAx is AgA...Axp is Ag, 精确或不完整的信息对复杂决策问题进行建模； (1) then Ca={(ω1，)，(w2,),…,(wm,a)月 Jiao等在置信函数框架上扩展模糊规则库分类 式中：X=(,,…,x)表示P维模式特征向量； 系统(FRBCS),提出置信规则库分类系统(belief rule base classification system,BRBCS)。置信规则 A9=(A,A?,…,A)表示前提属性，将第p个特征划 分为n个模糊子集，A号表示模糊子集， 库分类系统采用数据驱动方式由数据集自动生成 置信规则，建立特征空间与类空间之间的不确定 Ag∈{A.1,Ap2,…,Apm,}。规则权重0≤伊≤1， 关系，利用基于置信函数理论的置信推理方法 q=1,2,…,Q;Q是规则的总数；61,62，…，6p表示属 (belief reasoning method,BRM)对查询模式进行分 性权重，0≤6,62，…，6。≤1；表示第m个评价结 类推理。但是传统的置信规则库分类系统的推理 果的置信度，当∑<1时，表示评价结果可能是 性能极为依赖于内部参数取值，因此刘莞玲等四 不完整，本文规则的结果置信度和为1。 在BRBCS的基础上提出基于差分的置信规则库 传统基于置信规则库参数学习的分类系统 分类方法(DEBRM)。该方法能够有效解决BRBCS (BRBCS)准确率受参数值约束，因此Liu等II提 中参数优化的问题，使分类系统不需要依赖于增 出基于DE的置信规则库推理的分类方法(DEBRM, 加模糊区间划分数量来提高分类准确度。但该方 该方法主要包括基于DE的参数训练和置信推理 法随着前提属性个数的增加，规则数量呈指数式 过程。 增长，就会导致置信规则库复杂度增加。因此本 1.2多目标优化基本原理 文针对Liu等提出的DEBRM分类方法存在无法 一个具有n个决策变量，m个目标函数，k个 兼顾准确率和复杂度的问题进行改进，提出置信 约束条件的多目标优化问题可以描述为 规则库分类系统的多目标优化模型。 miny=f(x)=(f(x),f5(x),…,fm(x)】 多目标优化问题(multi--criterion optimization 8(x)≤0，j=1,2,…,1 (2) problems)涉及多个目标的极大化或极小化，同时 h,(x)≤0，j=1+1,1+2,…,k 这些目标之间往往是互相冲突的，一个目标性 式中：x=(x,x2,…,xn)为n维决策向量，x∈X,X 能的优化可能导致另一个目标性能的下降。多目 表示决策空间，XcR;m维目标向量y=(f(x) 标的最优解不是一个特定的解，而是一组 fi(x),…,fm(x》∈YcRm,Y为目标集合；f:R→Rm Pareto最优解，这些解没有优劣之分9-1o。目前用 表示映射函数。 于解决多目标优化问题的智能优化算法有：传统 定义1 Pareto支配。若a,beXr满足约束 遗传算法、群集智能算法（粒子群、蚁群）、人工免 条件的可行解，当且仅当ie{1,2,…,m,f(a)≤ 疫算法、神经网络等。本文拟在DEBRM分类 f(b)且3i∈{1,2，…，m,f(a)<(b),则称a支配b, 系统中，结合多目标免疫系统算法(MISA),提出 记作a<b。 利用MISA的置信规则库分类方法，通过特征属 定义2 Pareto最优解。当且仅当3b∈X 性约简来降低复杂度并使得准确率尽可能高；通 使得b<a,决策向量aeX,被称为X上的Pareto 过对系统的分类准确率和复杂度进行多目标优 最优解。 化，从而得到一组均衡解供决策者选择。在实验 定义3 Pareto最优解集。即包含所有最优 中选用Iris、Wine、Cancer、Glass这4个经典的公 解的集合，定义为P={a-beX,b<ao
空间中，从而来确定其所属类别[1]。目前，数据分 类主要应用于机器学习、模式识别、遗传算法、神 经网络、统计学、数据库、专家系统等领域。模糊 规则分类系统 (fuzzy rule-based classification system, FRBCS)[ 2 - 4 ] 广泛地用于求解分类问题。 FRBCS 能够建立清晰的语义模型，具有良好的可 解释性，能够定性定量地处理专家信息。此后， Yang 等 [5] 提出了基于证据推理的置信规则库推 理方法，该方法以 IF-THEN 规则库、模糊理论、DS 证据理论和决策理论等为基础，有效地利用不 精确或不完整的信息对复杂决策问题进行建模； Jiao 等 [6] 在置信函数框架上扩展模糊规则库分类 系统 (FRBCS)，提出置信规则库分类系统 (belief rule base classification system, BRBCS)。置信规则 库分类系统采用数据驱动方式由数据集自动生成 置信规则，建立特征空间与类空间之间的不确定 关系，利用基于置信函数理论的置信推理方法 (belief reasoning method，BRM) 对查询模式进行分 类推理。但是传统的置信规则库分类系统的推理 性能极为依赖于内部参数取值，因此刘莞玲等[7] 在 BRBCS 的基础上提出基于差分的置信规则库 分类方法 (DEBRM)。该方法能够有效解决 BRBCS 中参数优化的问题，使分类系统不需要依赖于增 加模糊区间划分数量来提高分类准确度。但该方 法随着前提属性个数的增加，规则数量呈指数式 增长，就会导致置信规则库复杂度增加。因此本 文针对 Liu 等提出的 DEBRM 分类方法存在无法 兼顾准确率和复杂度的问题进行改进，提出置信 规则库分类系统的多目标优化模型。 多目标优化问题 (multi-criterion optimization problems) 涉及多个目标的极大化或极小化，同时 这些目标之间往往是互相冲突的[8] ，一个目标性 能的优化可能导致另一个目标性能的下降。多目 标的最优解不是一个特定的解，而是一 组 Pareto 最优解，这些解没有优劣之分[9-10]。目前用 于解决多目标优化问题的智能优化算法有：传统 遗传算法、群集智能算法 (粒子群、蚁群)、人工免 疫算法、神经网络等[11]。本文拟在 DEBRM 分类 系统中，结合多目标免疫系统算法 (MISA)，提出 利用 MISA 的置信规则库分类方法，通过特征属 性约简来降低复杂度并使得准确率尽可能高；通 过对系统的分类准确率和复杂度进行多目标优 化，从而得到一组均衡解供决策者选择。在实验 中选用 Iris、Wine、Cancer、Glass 这 4 个经典的公 共测试数据集来验证本文方法的有效性。 1 相关概念 1.1 基于 DE 的置信规则库分类方法 置信规则库分类系统 (BRBCS) 由模糊规则库 分类系统 (FRBCS) 在置信函数框架上扩展得来， 采用数据驱动方式构建规则库，规则库的规则条 数即结构复杂度取决于前提属性个数和模糊区间 划分数。BRBCS 的置信规则结构： { If x1 is A q 1 ∧ x2 is A q 2 ∧ ··· ∧ xp is A q p , then Cq = {(ω1, βq 1 ) , ( ω2, βq 2 ) ,··· , ( ωm, βq m )} (1) X = ( x1, x2,··· , xp ) P A q = ( A q 1 ,A q 2 ,··· ,A q p ) A q p A q p ∈ {Ap,1,Ap,2,··· ,Ap,np } 0 ⩽ θ q ⩽ 1, q = 1,2,··· ,Q Q δ1,δ2,··· ,δp 0 ⩽ δ1,δ2,··· ,δp ⩽ 1 β q m m ∑m i=1 β q i < 1 式中： 表示 维模式特征向量； 表示前提属性，将第 p 个特征划 分 为 n 个模糊子集， 表示模糊子集， 。规则权重 ； 是规则的总数； 表示属 性权重， ； 表示第 个评价结 果的置信度，当 时，表示评价结果可能是 不完整，本文规则的结果置信度和为 1。 传统基于置信规则库参数学习的分类系统 (BRBCS) 准确率受参数值约束，因此 Liu 等 [7] 提 出基于 DE 的置信规则库推理的分类方法 (DEBRM)， 该方法主要包括基于 DE 的参数训练和置信推理 过程。 1.2 多目标优化基本原理 一个具有 n 个决策变量，m 个目标函数， k 个 约束条件的多目标优化问题可以描述为 min y = f (x) = (f1 (x), f2 (x),··· , fm (x)) gj(x) ⩽ 0, j = 1,2,··· ,l hj(x) ⩽ 0, j = l+1,l+2,··· , k (2) x = (x1, x2,··· , xn) n x ∈ X X X ⊂ R n m y = (f1 (x), f2 (x),··· , fm (x)) ∈ Y ⊂ R m f : R n → R m 式中： 为 维决策向量， ， 表示决策空间， ； 维目标向量 ，Y 为目标集合； 表示映射函数。 a, b ∈ Xf ∀i ∈ {1,2,··· ,m}, fi(a) ⩽ fi(b) ∃i ∈ {1,2,··· ,m}, fi(a) < fi(b) a ≺ b 定义 1 Pareto 支配。若 满足约束 条件的可行解，当且仅当 且 ，则称 a 支配 b， 记作 。 ¬∃b ∈ Xf b ≺ a a ∈ Xf X 定义 2 Pareto 最优解。当且仅当 使得 ，决策向量 被称为 上的 Pareto 最优解。 P ∗ = { a|¬∃b ∈ Xf , b ≺ a } 定义 3 Pareto 最优解集。即包含所有最优 解的集合，定义为 。 第 5 期 林锦，等：利用 MISA 多目标优化的置信规则库分类算法 ·983·
·984· 智能系统学报 第14卷 2MISA-BRM分类系统 复制4个个体；所处网格密度等于平均网格密度， 等级为3，最多可复制3个个体；所处网格密度大 在分类系统中，增加前提属性个数可以提高 于平均网格密度，等级为2；个体被支配且被选为 系统推理的准确率，但同时也增加了分类系统的 待克隆抗体则等级为1，最多可复制1个个体。 复杂度，所以复杂度和准确率是一组相互冲突的 2)确定待克隆抗体的复制个数 目标。如何从训练数据集中找到使准确率尽可能 抗体群设置最多可容纳个体数。将抗体群可 大、复杂度尽可能小的折中方案具有重要意义， 容纳个体数视为复制名额个数，具体过程如下： 因此本文提出利用MSA多目标优化的置信规则 ①待克隆抗体按照优先级：被支配数少>所处 库分类方法。该方法对数据集进行特征属性约 网格密度小>支配其他个体数多排成一列纵队； 减，并采用差分进化方法进行参数学习来获取最 ②从队头到队尾依次查看待克隆抗体的等 优结构参数，同时对经典的MISA算法进行适应 级，当待克隆抗体等级大于0且抗体群可容纳个 性改进，对分类系统的准确率和复杂度进行多目 体数大于0时，待克隆抗体获得1个复制名额，每 标优化，从而保证分类系统的规则数尽可能少 分配出1个名额，获得名额的待克隆抗体等级减 (即系统结构复杂度尽可能低)的同时，又能保证 1,抗体群可容纳数减1；当抗体群可容纳个体数 系统分类的准确率尽可能高。 等于0时结束分配： 最大化分类准确率即最小化分类错误率，所 ③走到队尾整个抗体群的抗体等级累加和大 以本文的两个目标函数为分类错误率f()和置 于0，返回执行②。 信规则库规则条数3(0,0代表置信规则库中的 除了待克隆抗体的克隆个体数确定方式不同 参数：前提属性个数、模糊区间划分数、前提属性 外，改进型MSA采用二进制染色体编码，抗体长 权重、规则权重、结果置信度，中参数涉及以上 度等于最大前提属性个数，取值为0代表删除这 所列参数，方中参数涉及前提属性个数、模糊区 个前提属性，取值为1代表选中这一前提属性。 间划分数。因此本文的多目标优化问题描述为 确定前提属性后构建规则库，规则库编码采用实 miny=f()=(f (),() 数编码，一个规则库作为一个个体；无交叉操作， 2.1改进型MISA多目标优化算法 变异操作包括单点变异和接种疫苗，具体的提取 MSA算法是Coello等回根据免疫系统中抗 疫苗和接种疫苗方法说明如下。 体的克隆选择原则提出的。 1)提取疫苗：疫苗群体限制最大个数，抗体 2.1.1改进型MSA算法原理 被选为疫苗的条件为被支配数为0，支配数大于 改进型MSA算法将群体中的所有个体均视 O。根据Pareto的定义，能够支配其他个体的个体 作“抗体”。依据克隆选择原则，选择群体中的非 不是属性最少也不是属性最多的个体，而是属性 支配解进行克隆，根据它们在解空间的拥挤程度 个数居中的个体，如选取的特征属性个数为5，受 来决定克隆的数目，并对克隆的个体进行高概率 它支配的解是属性个数大于5且分类错误率大于 变异和交叉操作，生成新的抗体群1。本文对 它的个体，这一定程度上说明这5个属性中可能 Coello等提出的MISA针对基于置信规则库分类 具有区分性较高的特征属性或特征属性组合。 问题做适应性改进，并在个体变异中增加接种疫 2)接种疫苗操作：随机从免疫群体中随机选 苗的变异操作。改进型MISA与原始型MISA的 取一个个体，从疫苗染色体中所有值为1的染色 一个主要区别在于确定待克隆抗体的复制个体数 体单位中随机选取1个单位，再从所有值为0的 的方法不同，改进型MISA根据待克隆抗体所处 染色体单位中随机选取1个单位，将这2个单位 网格密度及支配情况确定最大可复制数，再根据 植入个体中。植入个体后，有4种可能情况：个体 抗体群所能容纳的最大个体数确定最终的复制数 特征属性减少或增加一个；个体特征属性完全不 量，确定待克隆抗体复制个体数的具体方法 变；个体属性特征个数不变但选取的特征属性改 如下： 变；有可能使个体具有高区分性的特征属性，或 1)确定待克隆抗体最大可复制个数 删除不必要的属性。 按照个体在外部种群（外部种群中个体互为 2.1.2外部种群及自适应网格算法 非支配解)中所处网格的密度及支配关系分配等 外部种群用于保存Pareto非劣解，外部种群 级，按照等级确定最大的克隆数。分4个等级：所 中的个体两两之间不存在支配与被支配关系。为 处网格密度小于平均网格密度，等级为4，最多可 了使非支配解尽可能均匀地分布于Pareto前沿
2 MISA-BRM 分类系统 在分类系统中，增加前提属性个数可以提高 系统推理的准确率，但同时也增加了分类系统的 复杂度，所以复杂度和准确率是一组相互冲突的 目标。如何从训练数据集中找到使准确率尽可能 大、复杂度尽可能小的折中方案具有重要意义， 因此本文提出利用 MISA 多目标优化的置信规则 库分类方法。该方法对数据集进行特征属性约 减，并采用差分进化方法进行参数学习来获取最 优结构参数，同时对经典的 MISA 算法进行适应 性改进，对分类系统的准确率和复杂度进行多目 标优化，从而保证分类系统的规则数尽可能少 (即系统结构复杂度尽可能低) 的同时，又能保证 系统分类的准确率尽可能高。 f 1 (θ) f 2 (θ) θ f 1 f 2 最大化分类准确率即最小化分类错误率，所 以本文的两个目标函数为分类错误率 和置 信规则库规则条数 ， 代表置信规则库中的 参数：前提属性个数、模糊区间划分数、前提属性 权重、规则权重、结果置信度， 中参数涉及以上 所列参数， 中参数涉及前提属性个数、模糊区 间划分数。因此本文的多目标优化问题描述为 miny = f(θ) = (f 1 (θ), f 2 (θ)) 2.1 改进型 MISA 多目标优化算法 MISA 算法是 Coello 等 [12] 根据免疫系统中抗 体的克隆选择原则提出的。 2.1.1 改进型 MISA 算法原理 改进型 MISA 算法将群体中的所有个体均视 作“抗体”。依据克隆选择原则，选择群体中的非 支配解进行克隆，根据它们在解空间的拥挤程度 来决定克隆的数目，并对克隆的个体进行高概率 变异和交叉操作，生成新的抗体群[ 1 2 ]。本文对 Coello 等提出的 MISA 针对基于置信规则库分类 问题做适应性改进，并在个体变异中增加接种疫 苗的变异操作。改进型 MISA 与原始型 MISA 的 一个主要区别在于确定待克隆抗体的复制个体数 的方法不同，改进型 MISA 根据待克隆抗体所处 网格密度及支配情况确定最大可复制数，再根据 抗体群所能容纳的最大个体数确定最终的复制数 量，确定待克隆抗体复制个体数的具体方法 如下： 1) 确定待克隆抗体最大可复制个数 按照个体在外部种群 (外部种群中个体互为 非支配解) 中所处网格的密度及支配关系分配等 级，按照等级确定最大的克隆数。分 4 个等级：所 处网格密度小于平均网格密度，等级为 4，最多可 复制 4 个个体；所处网格密度等于平均网格密度， 等级为 3，最多可复制 3 个个体；所处网格密度大 于平均网格密度，等级为 2；个体被支配且被选为 待克隆抗体则等级为 1，最多可复制 1 个个体。 2) 确定待克隆抗体的复制个数 抗体群设置最多可容纳个体数。将抗体群可 容纳个体数视为复制名额个数，具体过程如下： ①待克隆抗体按照优先级：被支配数少>所处 网格密度小>支配其他个体数多排成一列纵队； ②从队头到队尾依次查看待克隆抗体的等 级，当待克隆抗体等级大于 0 且抗体群可容纳个 体数大于 0 时，待克隆抗体获得 1 个复制名额，每 分配出 1 个名额，获得名额的待克隆抗体等级减 1，抗体群可容纳数减 1；当抗体群可容纳个体数 等于 0 时结束分配； ③走到队尾整个抗体群的抗体等级累加和大 于 0，返回执行②。 除了待克隆抗体的克隆个体数确定方式不同 外，改进型 MISA 采用二进制染色体编码，抗体长 度等于最大前提属性个数，取值为 0 代表删除这 个前提属性，取值为 1 代表选中这一前提属性。 确定前提属性后构建规则库，规则库编码采用实 数编码，一个规则库作为一个个体；无交叉操作， 变异操作包括单点变异和接种疫苗，具体的提取 疫苗和接种疫苗方法说明如下。 1) 提取疫苗：疫苗群体限制最大个数，抗体 被选为疫苗的条件为被支配数为 0，支配数大于 0。根据 Pareto 的定义，能够支配其他个体的个体 不是属性最少也不是属性最多的个体，而是属性 个数居中的个体，如选取的特征属性个数为 5，受 它支配的解是属性个数大于 5 且分类错误率大于 它的个体，这一定程度上说明这 5 个属性中可能 具有区分性较高的特征属性或特征属性组合。 2) 接种疫苗操作：随机从免疫群体中随机选 取一个个体，从疫苗染色体中所有值为 1 的染色 体单位中随机选取 1 个单位，再从所有值为 0 的 染色体单位中随机选取 1 个单位，将这 2 个单位 植入个体中。植入个体后，有 4 种可能情况：个体 特征属性减少或增加一个；个体特征属性完全不 变；个体属性特征个数不变但选取的特征属性改 变；有可能使个体具有高区分性的特征属性，或 删除不必要的属性。 2.1.2 外部种群及自适应网格算法 外部种群用于保存 Pareto 非劣解，外部种群 中的个体两两之间不存在支配与被支配关系。为 了使非支配解尽可能均匀地分布于 Pareto 前沿， ·984· 智 能 系 统 学 报 第 14 卷
第5期 林锦，等：利用MISA多目标优化的置信规则库分类算法 ·985· 外部种群采用Knowles等)提出的自适应网格法 算法3加入接种疫苗的多目标变异算法 进行更新，详见算法1。 输入被选中将要进行克隆的个体： 算法1自适应网格算法 输出经过变异/接种疫苗生成新抗体群。 输入抗体群中所有非支配解Q,外部种群 1)将待克隆抗体按照可克隆个数进行克隆， EP(external population); 生成新的初始抗体群 输出Pareto最优前沿。 2)循环遍历V; 1)输入抗体群中所有非支配解组成的集 3)随机选取[0,1]的一个值r 合0： 4)如果r<pc,那么进行变异：对x∈V的个 2)循环遍历Q: 体随机选取一位进行翻转： 3)判断Q,是否被外部种群中任一一个个体 5)否则进行疫苗接种：随机选取一个疫苗； 支配：如果3aa∈EP:aa<Q(aa表示EP中支配Q 随机选取w中染色体单位值为0的片段w:随机 的个体)，那么删除Q,否则执行4)： 选取w中染色体单位值为1的片段w;对x∈V的 4)判断Q是否支配EP中任一解：如果 个体植入o、w1; 3 aaEEP:Q:<au(au表示EP中所有被Q支配的个 6)循环结束。 体)，那么删除a4,将Q加入EP,否则执行5)： 利用MISA多目标优化的置信规则库分类算 5)判断外部种群个体数是否达到最大值：如 法有机融合了算法1、2、3、MISA和DE参数训练 果外部种群个体数达到所能容纳的最大值，那么 方法。多目标免疫系统算法的选择进化机制是整 执行6)，否则将Q:加入EP; 个算法的核心，使得差分训练规则库参数和特征 6)按照所给划分数构建自适应网格：如果 属性选择组合两个优化过程相互促进，最终获得 We+1≥maxN(Wa表示2所在网格未加入Q 一组Pareto最优解。DE参数训练方法对根据抗 的密度，maxW表示所有网格的密度最大值，这里 体构建的规则库进行参数优化，得到不同的特征 所说的密度其实是指网格包含的个体数)，那么删 属性选择组合构建的置信规则库的近似最优分类 性能，进而采用MISA的选择机制和自适应网格 除Q,否则去掉档案中密度最大的网格中的任意 进行抗体选择，将分类性能好的特征属性组合保 一个解，加入Q: 留在外部种群中，同时也将区分性高的特征属性 7)循环结束。 保留下来，在抗体进化的时候，采用变异增加抗 2.1.3改进型MISA算法流程 体群的多样性，疫苗提取、更新和接种疫苗算法 改进型MISA算法的算法流程的主要部分和 使得区分性高的特征属性在抗体群中扩散，让抗 原始MSA算法相同：生成抗体群，更新自适应网 体能够得到更优的分类性能，迭代更新外部种 格，选择待克隆抗体，确定待克隆抗体的复制数 群，不断优化外部种群中抗体的特征属性选择组 量。但改进型MSA在变异操作中加入了接种疫 合、分类性能。 苗操作，因此增加了疫苗提取的过程，具体流程 算法4利用MISA多目标优化的置信规则 如算法2~4所示。 库分类算法 算法2疫苗提取及更新算法 输入无； 输入抗体群； 输出Pareto最优前沿。 输出更新后的疫苗群体。 1)初始化抗体群，初始化外部种群为空； 1)选取出抗体群中被支配数为0，支配数大 2)对由每个抗体构建得来的置信规则库采 于0的个体，将选出的个体按照支配个体数降序 用DE参数训练方法进行参数训练： 排列形成群体P; 3)计算每个抗体的适应值，进而判断每个抗 2)疫苗提取及更新：如果疫苗群体为空，在 体是否是Pareto解； 符合群体P个体数和疫苗群体个体数最大值的约 4)将得到的非支配个体复制到外部种群（调 束条件下，按队列先后顺序将群体P中个体复制 用算法1)： 到疫苗群体中；否则，将群体P中个体和疫苗群 5)按一定的标准选取待克隆抗体： 体中个体合并起来，并按照支配个体数降序排列 6)按一定的标准确定待克隆抗体的复制数量： 形成群体P',在符合群体P个体数和疫苗群体个 7)抽取并更新疫苗（调用算法2）： 体数最大值的约束条件下，按队列先后顺序将群 8)如果达到MISA算法最大迭代次数则end, 体P中个体复制到疫苗群体中。 否则进行9)：
外部种群采用 Knowles 等 [13] 提出的自适应网格法 进行更新，详见算法 1。 算法 1 自适应网格算法 输入 抗体群中所有非支配解 Q ，外部种群 EP(external population)； 输出 Pareto 最优前沿。 Q 1) 输入抗体群中所有非支配解组成的集 合 ； 2) 循环遍历 Q； Qi ∃and ∈ EP and ≺ Qi and Qi Qi 3) 判断 是否被外部种群中任一一个个体 支配：如果 : ( 表示 EP 中支配 的个体)，那么删除 ，否则执行 4)； Qi ∃ad ∈ EP Qi ≺ ad ad Qi ad Qi 4 ) 判 断 是否支 配 EP 中任一解：如果 : ( 表示 EP 中所有被 支配的个 体)，那么删除 ，将 加入 EP，否则执行 5)； Qi 5) 判断外部种群个体数是否达到最大值：如 果外部种群个体数达到所能容纳的最大值，那么 执行 6)，否则将 加入 EP； NQi +1 ⩾ maxN NQi Qi Qi maxN Qi Qi 6) 按照所给划分数构建自适应网格：如果 ( 表示 所在网格未加入 的密度， 表示所有网格的密度最大值，这里 所说的密度其实是指网格包含的个体数)，那么删 除 ，否则去掉档案中密度最大的网格中的任意 一个解,加入 ； 7) 循环结束。 2.1.3 改进型 MISA 算法流程 改进型 MISA 算法的算法流程的主要部分和 原始 MISA 算法相同：生成抗体群，更新自适应网 格，选择待克隆抗体，确定待克隆抗体的复制数 量。但改进型 MISA 在变异操作中加入了接种疫 苗操作，因此增加了疫苗提取的过程，具体流程 如算法 2~4 所示。 算法 2 疫苗提取及更新算法 输入 抗体群； 输出 更新后的疫苗群体。 1) 选取出抗体群中被支配数为 0，支配数大 于 0 的个体，将选出的个体按照支配个体数降序 排列形成群体 P； 2) 疫苗提取及更新：如果疫苗群体为空，在 符合群体 P 个体数和疫苗群体个体数最大值的约 束条件下，按队列先后顺序将群体 P 中个体复制 到疫苗群体中；否则，将群体 P 中个体和疫苗群 体中个体合并起来，并按照支配个体数降序排列 形成群体 P'，在符合群体 P'个体数和疫苗群体个 体数最大值的约束条件下，按队列先后顺序将群 体 P'中个体复制到疫苗群体中。 算法 3 加入接种疫苗的多目标变异算法 输入 被选中将要进行克隆的个体； 输出 经过变异/接种疫苗生成新抗体群。 1) 将待克隆抗体按照可克隆个数进行克隆， 生成新的初始抗体群 V； 2) 循环遍历 V ； 3) 随机选取 [0, 1] 的一个值 r； 4) 如果 r < pc ，那么进行变异：对 x ∈ V 的个 体随机选取一位进行翻转； w0 w1 x ∈ V w0 w1 5) 否则进行疫苗接种：随机选取一个疫苗 w； 随机选取 w 中染色体单位值为 0 的片段 ；随机 选取 w 中染色体单位值为 1 的片段 ；对 的 个体植入 、 ； 6) 循环结束。 利用 MISA 多目标优化的置信规则库分类算 法有机融合了算法 1、2、3、MISA 和 DE 参数训练 方法。多目标免疫系统算法的选择进化机制是整 个算法的核心，使得差分训练规则库参数和特征 属性选择组合两个优化过程相互促进，最终获得 一组 Pareto 最优解。DE 参数训练方法对根据抗 体构建的规则库进行参数优化，得到不同的特征 属性选择组合构建的置信规则库的近似最优分类 性能，进而采用 MISA 的选择机制和自适应网格 进行抗体选择，将分类性能好的特征属性组合保 留在外部种群中，同时也将区分性高的特征属性 保留下来，在抗体进化的时候，采用变异增加抗 体群的多样性，疫苗提取、更新和接种疫苗算法 使得区分性高的特征属性在抗体群中扩散，让抗 体能够得到更优的分类性能，迭代更新外部种 群，不断优化外部种群中抗体的特征属性选择组 合、分类性能。 算法 4 利用 MISA 多目标优化的置信规则 库分类算法 输入 无； 输出 Pareto 最优前沿。 1) 初始化抗体群，初始化外部种群为空； 2) 对由每个抗体构建得来的置信规则库采 用 DE 参数训练方法进行参数训练； 3) 计算每个抗体的适应值，进而判断每个抗 体是否是 Pareto 解； 4) 将得到的非支配个体复制到外部种群 (调 用算法 1)； 5) 按一定的标准选取待克隆抗体； 6) 按一定的标准确定待克隆抗体的复制数量； 7) 抽取并更新疫苗 (调用算法 2)； 8) 如果达到 MISA 算法最大迭代次数则 end， 否则进行 9)； 第 5 期 林锦，等：利用 MISA 多目标优化的置信规则库分类算法 ·985·
·986· 智能系统学报 第14卷 9)克隆抗体，并对个体进行变异或疫苗接种 Windowl0操作系统。 (调用算法3)： 3.2数据集参数设置 10)返回到2)。 3.2.1实验数据集 2.2MISA-BRM分类模型 在实验部分本文选用University of Galifornia 在MISA-BRM分类方法中，将前提属性的选 at Irvine分校网页中获取的公共测试集来验证算 取编码作为抗体，根据抗体构建出初始的规则 法有效性。数据集主要包括鸢尾花特征数据 库，将置信推理方法BRM作为推理机，结合差分 Iris、红酒化学成分特征数据Wine、乳腺癌数据 进化算法对待优化参数进行学习矫正，进而计算 Cancer和玻璃类型数据Glass。表1列举了这 抗体在复杂度、分类错误率两个目标函数上的适 4个测试数据集中前提属性数量、类别数量和数 应值，然后采用MSA的选择进化机制，在系统的 据集大小的信息。 复杂度、分类错误率两个维度上寻找Pareto解。 其中Cancer原数据集中存在缺失数据，实验 算法的流程如图1所示。 中将缺失的16条数据删除，保留683条数据。 初始化抗体群。初始化外部种群为空：=0 表1测试数据的基本信息 Table 1 Basic information regarding the test data 为抗体群中每个 个体构建BRB 数据集 前提属性数量 类别数量 数据量 Iris 150 个体DE参数训练 Wine 13 3 178 Cancer 9 683 计算个体适应值 Glass 9 6 214 比较抗体群个体之间的支配关系。 3.2.2参数设置 标记每个个体的支配个体数和 本文置信规则库的模糊区间划分数K=3。 被支配个体数 本文所采用的数据集的数据量及前提属性个数不 克隆个体，对克隆 将抗体群中 个体进行变异接种 外部种前 非支配解复制 同，因此实验中针对不同数据集设置不同的参 疫苗操作 是否为空 到外部种群 数，表2、表3列举了4个测试数据集实验的参数 设置信息。 比较抗体群中的非支配解 和外部种群中解的支配关系】 表2 DEBRM参数设置信息 利用自适应网格法更新外部种群 Table 2 The parameter setting information for DEBRM 数据集 选出待克隆抗体、计算待克隆 DEBRM参数 抗体的克隆数：从抗体群中 Iris Wine Cancer Glass 抽取疫苗 F 0.5 0.5 0.5 0.5 计+ CR 0.9 0.9 0.9 0.9 种群大小个 100 50 50 50 =m或 迭代次数 3000 3000 3000 3000 表3MISA参数设置信息 Table 3 The parameter setting information for MISA 循环结束 停止运行 数据集 MISA参数 Iris Wine Cancer Glass 图1MISA-BRM模型 Fig.1 MISA-BRM model diagram 变异概率 0.5 0.5 0.5 0.5 接种疫苗概率 0.5 0.5 0.5 0.5 3实验分析 疫苗群最大值 3 7 5 5 外部种群大小 20 3.1实验环境 20 场 20 抗体群最大值 15 15 15 实验环境的基本信息：Intel(R)Core(TM)i7 15 迭代次数 8 8 8 8 6700CPU@3.40GHz处理器，8核，16GB内存
9) 克隆抗体，并对个体进行变异或疫苗接种 (调用算法 3)； 10) 返回到 2)。 2.2 MISA-BRM 分类模型 在 MISA-BRM 分类方法中，将前提属性的选 取编码作为抗体，根据抗体构建出初始的规则 库，将置信推理方法 BRM 作为推理机，结合差分 进化算法对待优化参数进行学习矫正，进而计算 抗体在复杂度、分类错误率两个目标函数上的适 应值，然后采用 MISA 的选择进化机制，在系统的 复杂度、分类错误率两个维度上寻找 Pareto 解。 算法的流程如图 1 所示。 初始化抗体群，初始化外部种群为空：i=0 为抗体群中每个 个体构建 BRB 个体 DE 参数训练 比较抗体群个体之间的支配关系， 标记每个个体的支配个体数和 被支配个体数 克隆个体，对克隆 个体进行变异/接种 疫苗操作 比较抗体群中的非支配解 和外部种群中解的支配关系， 利用自适应网格法更新外部种群 选出待克隆抗体、计算待克隆 抗体的克隆数；从抗体群中 抽取疫苗 i++ i=m或 克隆后的抗体 群大小为 0 循环结束， 停止运行 Y Y N N 计算个体适应值 将抗体群中 非支配解复制 到外部种群 外部种群 是否为空 图 1 MISA-BRM 模型 Fig. 1 MISA-BRM model diagram 3 实验分析 3.1 实验环境 实验环境的基本信息：Intel(R) Core(TM) i7- 6700 CPU @3.40 GHz 处理器，8 核，16 GB 内存， Window10 操作系统。 3.2 数据集参数设置 3.2.1 实验数据集 在实验部分本文选用 University of Galifornia at Irvine 分校网页中获取的公共测试集来验证算 法有效性。数据集主要包括鸢尾花特征数据 Iris、红酒化学成分特征数据 Wine、乳腺癌数据 Cancer 和玻璃类型数据 Glass。表 1 列举了这 4 个测试数据集中前提属性数量、类别数量和数 据集大小的信息。 其中 Cancer 原数据集中存在缺失数据，实验 中将缺失的 16 条数据删除，保留 683 条数据。 表 1 测试数据的基本信息 Table 1 Basic information regarding the test data 数据集 前提属性数量 类别数量 数据量 Iris 4 3 150 Wine 13 3 178 Cancer 9 2 683 Glass 9 6 214 3.2.2 参数设置 本文置信规则库的模糊区间划分数 K = 3。 本文所采用的数据集的数据量及前提属性个数不 同，因此实验中针对不同数据集设置不同的参 数，表 2、表 3 列举了 4 个测试数据集实验的参数 设置信息。 表 2 DEBRM 参数设置信息 Table 2 The parameter setting information for DEBRM DEBRM参数 数据集 Iris Wine Cancer Glass F 0.5 0.5 0.5 0.5 CR 0.9 0.9 0.9 0.9 种群大小/个 100 50 50 50 迭代次数 3 000 3 000 3 000 3 000 表 3 MISA 参数设置信息 Table 3 The parameter setting information for MISA MISA参数 数据集 Iris Wine Cancer Glass 变异概率 0.5 0.5 0.5 0.5 接种疫苗概率 0.5 0.5 0.5 0.5 疫苗群最大值 3 7 5 5 外部种群大小 20 20 20 20 抗体群最大值 15 15 15 15 迭代次数 8 8 8 8 ·986· 智 能 系 统 学 报 第 14 卷