第2卷第4期 智能系统学报 Vol.2 No 4 2007年8月 CAAI Transactions on Intelligent Systems Aug.2007 基于克隆选择的模糊分类规则提取算法 左瑞娟，武永华 (福建师范大学软件学院，福建福州350007) 摘要：分类是许多研究领域的关键问题，模糊规则的提取质量对分类器的性能又有着极大影响.所提取的规则不 仅在分类能力上要达到最优，同时在规则数量上也不能太多，否则会影响规则搜索和匹配的速度.结合人工免疫的 克隆选择原理，采用克隆选择算法，提取通过多精度模糊分割产生的大量模糊f。ten规则中的少数精华规则，从而 建立了模糊分类所需要的有效规则集合，同时还对优化目标函数进行了改进.经仿真实验证明，该方法所提取的模 糊规则具有分类准确率高，规则数目较少等特点 关键词：模糊规则提取：模糊分割：克隆选择算法 中图分类号：TP18文献标识码：A文章编号：1673-4785(2007)04-0074-06 Extracting fuzzy classification rules using clonal selection algorithm ZUO Rui-juan,WU Yong-hua (Faculty of Software,Fujian Normal University,Fuzhou 350007,China) Abstract:Classification is crucial for many research domains,but the quality of extracted fuzzy rules has a great influence on the performance of classifiers.It is not only necessary that extracted rules have optimal performance in classification,but also the number of rules must be as small as possible,otherwise,rule searching and matching becomes slow.In this paper,using the clone selection algorithm,the best rules were extracted from massive sets of fuzzy if-then rules generated from multiple precision fuzzy partitions. Thus a set of effective rules for fuzzy classification were developed.Also the optimal objective function was improved.Test results prove that the proposed method uses fewer rules and has high classification preci- sion. Key words:fuzzy rules extraction;fuzzy partition;clonal selection algorithm. 目前关于模糊规则自动提取的方法非常多，如 最大缺陷，就是产生了大量的模糊规则，尤其是对于 利用神经网络1)、粗糙集倒等，最新的方法还有基 高维模式空间的分类问题，从而增加规则搜索的时 于基因表达的模糊规则提取，.但用于解决分类问 间.同时一些低效规则对于高效规则的分类能力还 题的比较有代表性的仍然是由Ishibuchi等人在文产生一定的干扰，影响了分类精度.因此Shibuchi 献[5]中提出的模糊规则的分布式表达方法.在文献 等人又在此基础上采用遗传算法对由多分割精度 [s]中，考虑到基于模糊if-then规则的模糊分类系 下产生的模糊规则SL进行了优化提取高效紧凑 统的执行效果有赖于模糊子空间分割精度的选择， 的分类规则集OPTS,从而大大减少了规则数量 分割过于“模糊”或者“精确”都会影响模糊分类系统 但是，该方法仍然存在着收敛速度慢，收敛效果不佳 的分类效果，而且只按一种分割精度进行模式空间 的缺点).文章正是在此基础上对其优化函数进行 分割是不够的.因而采用几个分割精度下所产生的 了改进，加入了更能反应规则分类能力的确信度 模糊规则并应用于模糊推理，见图1.该方法解决了 CF,并采用了克隆选择算法I来实现高效模糊规则 如何确定合适的分割精度和不同类别的学习样本分 的提取。 布交叠的难题，从而提高了分类精度.然而该方法的 1 多精度模糊分割的规则产生 收稿日期：200611-23. 由文献[5]可以得到多分割精度下各模糊子空 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 4 期 智 能 系 统 学 报 Vol. 2 №. 4 2007 年 8 月 CAAI Transactions on Intelligent Systems Aug. 2007 基于克隆选择的模糊分类规则提取算法 左瑞娟 ,武永华 (福建师范大学 软件学院 ,福建 福州 350007) 摘 要 :分类是许多研究领域的关键问题 ,模糊规则的提取质量对分类器的性能又有着极大影响. 所提取的规则不 仅在分类能力上要达到最优 ,同时在规则数量上也不能太多 ,否则会影响规则搜索和匹配的速度. 结合人工免疫的 克隆选择原理 ,采用克隆选择算法 ,提取通过多精度模糊分割产生的大量模糊 if - then 规则中的少数精华规则 ,从而 建立了模糊分类所需要的有效规则集合 ,同时还对优化目标函数进行了改进. 经仿真实验证明 ,该方法所提取的模 糊规则具有分类准确率高 ,规则数目较少等特点. 关键词 :模糊规则提取 ;模糊分割 ;克隆选择算法 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0420074206 Extracting fuzzy classification rules using clonal selection algorithm ZUO Rui2juan ,WU Yong2hua ( Faculty of Software , Fujian Normal University , Fuzhou 350007 , China) Abstract :Classification is crucial for many research domains , but t he quality of extracted f uzzy rules has a great influence on t he performance of classifiers. It is not only necessary t hat extracted rules have optimal performance in classification , but also t he number of rules must be as small as possible , ot herwise , rule searching and matching becomes slow. In t his paper , using t he clone selection algorit hm , t he best rules were extracted from massive sets of f uzzy if2t hen rules generated from multiple precision f uzzy partitions. Thus a set of effective rules for f uzzy classification were developed. Also t he optimal objective f unction was improved. Test results prove t hat the proposed met hod uses fewer rules and has high classification preci2 sion. Keywords :f uzzy rules extraction ; f uzzy partition ; clonal selection algorithm. 收稿日期 :2006211223. 目前关于模糊规则自动提取的方法非常多 ,如 利用神经网络[1 - 2 ] 、粗糙集[3 ]等 ,最新的方法还有基 于基因表达的模糊规则提取[4 ] . 但用于解决分类问 题的比较有代表性的仍然是由 Ishibuchi 等人在文 献[ 5 ]中提出的模糊规则的分布式表达方法. 在文献 [5 ]中 ,考虑到基于模糊 if - t hen 规则的模糊分类系 统的执行效果有赖于模糊子空间分割精度的选择 , 分割过于“模糊”或者“精确”都会影响模糊分类系统 的分类效果 ,而且只按一种分割精度进行模式空间 分割是不够的. 因而采用几个分割精度下所产生的 模糊规则并应用于模糊推理 ,见图 1. 该方法解决了 如何确定合适的分割精度和不同类别的学习样本分 布交叠的难题 ,从而提高了分类精度. 然而该方法的 最大缺陷 ,就是产生了大量的模糊规则 ,尤其是对于 高维模式空间的分类问题 ,从而增加规则搜索的时 间. 同时一些低效规则对于高效规则的分类能力还 产生一定的干扰 ,影响了分类精度. 因此 Shibuchi 等人又在此基础上采用遗传算法[6 ]对由多分割精度 下产生的模糊规则 SALL 进行了优化提取高效紧凑 的分类规则集 OPT _ S ,从而大大减少了规则数量. 但是 ,该方法仍然存在着收敛速度慢 ,收敛效果不佳 的缺点[ 7 ] . 文章正是在此基础上对其优化函数进行 了改进 ,加入了更能反应规则分类能力的确信度 CF ,并采用了克隆选择算法[7 ]来实现高效模糊规则 的提取. 1 多精度模糊分割的规则产生 由文献[5 ]可以得到多分割精度下各模糊子空
第4期 左瑞娟，等：基于克隆选择的模糊分类规则提取算法 ·75· 2 基于克隆选择的模糊规则提取 克隆选择算法是近年来提出的基于免疫学中的 克隆选择原理的一种人工免疫算法，该方法对具有 输出 类 较高亲和力的抗体（可行解）进行克隆，以贪婪搜索 为特征，通过高频变异和受体编辑·11方法，前者 微观调控，后者宏观控制，不断的保持抗体的多样 性，从而更有利于产生复杂优化问题的最优解.与遗 传算法相比具有更快的收敛速度和更好、更稳定的 寻优能力 图1多精度模糊分割 由上述可知最关键的工作是如何从SL中提 Fig.1 Multiple fuzzy partition 取高效紧凑规则集OPT_S.这就是这一节采用克 间所确定的类及其确定度.表1给出二维模式空间 隆选择算法所要解决的问题.为了提高算法的执 下分割精度K=2的模糊子空间所确定的类及其确 行速度，首先将无效规则即CF=0或CF≈0的 定度.其中r为规则号，(i,)确定模糊分割后的模 规则剔除，从而只剩余有效规则集，用S表示 糊子空间，根据文献51r和i,j有如下对应关系： 2.1亲和力函数的建立 2(i-1)+j, K=2. 要想从有效规则集S中提取紧凑规则集 K.1 ●1) +K(i-)+j,K≥3 OPTS,首先要确定其所应满足的目标和约束 考虑到OPTS之所以是判断各类的最佳规则 r、i,)、C、C的关系数据结构见表1，r和 正是因为通过样本学习他们能够确定的正确分类样 ij的对应关系见表1(a)、(b) 本个数及其确定度与其他规则相比要高，也即这些 表1r、(i,j)、C、C℉的关系数据结构 规则空间不仅包含了大部分的该类样本，表明该类 Table 1 Relation data structure about r,(i,j),Cand CF 样本在这些子空间出现频率比较高，同时这些空间 也能更有效地将该空间所代表的样本类别和其他种 C 类的样本分离，因而由这些空间所确定的判断某类 CFi 的规则基本或完全能够涵盖该类样本的出现范围， 2 C 具有较高的分类能力；另外在保证其正确分类的基 C 础上，还希望规则数要尽量少，以减少规则搜索匹配 12 1333 2 m C 的时间，提高分类效率.因此优化目标确定如下： (a)K=2 (b)K=3 (c)K=2 max (NCP(R))XCF) C℉表示最终确定的模糊子空间(1，)所代表 R点OP_s CFK ECF 的类别m:,当不能肯定模糊子空间所代表的类时令 min|OPTSI. (2) CF矿=0：CF表示当模糊子空间确定为类CF时的 OPTS∈S∈SAL 确定度，见表1(C).CF是一个非常重要的指标，它 这里NCP(P)XCFm是指OPT_S中规则 反映了对应规则的类别判定肯定程度：当落入模糊 R=r能够正确分类的学习样本个数与其确定度 子空间(i,)中的所有样本都属于同一类，那么 的乘积，反映规则的正确分类能力；OPTS是指 CF=1(最大确定度).在这种情况下，可以肯定，落 OPT_S中包含的模糊规则总个数.引入正权值 入在该模糊子空间中的任何判别样本的类别都与该 WNcp和Ws,对式2)作如下修改： 子空间确定的类一致.而当落入模糊子空间(i,)的 maxf(OPT_Sy=(Wcp·∑(NCP(R)X 样本中包含不同类别的样本且各类样本的联合隶属 R&EOPT_S 度值基本相等时CF矿≈0（最小确定度）.在这种情 CFm)·(Ws1OPT_S|), 况下，对于落入该子空间中的任何判别样本就不能 OPT_S∈S∈SAL. (3) 肯定其类别.由此可以看出，CF暗对于规则的提取及 般地，一个分类系统的分类能力与其包含的 判定起着至关重要的作用 规则总数相比，前者更重要，不应为了得到一个精练 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 1 多精度模糊分割 Fig. 1 Multiple fuzzy partition 间所确定的类及其确定度. 表 1 给出二维模式空间 下分割精度 K = 2 的模糊子空间所确定的类及其确 定度. 其中 r 为规则号 , ( i , j) 确定模糊分割后的模 糊子空间 ,根据文献[5 ]r 和 i , j 有如下对应关系 : r = 2 ( i - 1) + j , K = 2 , ∑ K- 1 h = 2 h 2 + K( i - 1) + j , K ≥3. (1) r、( i , j) 、C k ij 、CF k ij 的关系数据结构见表 1 , r 和 i 、j 的对应关系见表 1 (a) 、(b) . 表 1 r、(i , j) 、C K ij 、CF K ij 的关系数据结构 Table 1 Relation data structure about r , (i , j) , C K ij and CF K ij r i j 1 1 1 2 1 2 3 2 1 4 2 2 (a) K = 2 r i j 5 1 1 6 1 2 7 1 3 8 2 1 9 2 2 10 2 3 11 3 1 12 3 2 13 3 3 (b) K = 3 r i j C 2 ij C 2 ij 1 1 1 m1 CF 2 11 2 1 2 m2 CF 2 12 3 2 1 CF 2 21 4 2 2 mi CF 2 22 (c) K = 2 CF K ij 表示最终确定的模糊子空间 ( i , j) 所代表 的类别 mi ,当不能肯定模糊子空间所代表的类时令 CF K ij = 0 ; CF K ij 表示当模糊子空间确定为类 CF K ij 时的 确定度 ,见表 1 (c) . CF K ij 是一个非常重要的指标 ,它 反映了对应规则的类别判定肯定程度 :当落入模糊 子空间 ( i , j) 中的所有样本都属于同一类 , 那么 CF K ij = 1 (最大确定度) . 在这种情况下 ,可以肯定 ,落 入在该模糊子空间中的任何判别样本的类别都与该 子空间确定的类一致. 而当落入模糊子空间( i , j) 的 样本中包含不同类别的样本且各类样本的联合隶属 度值基本相等时 CF K ij ≈0 (最小确定度) . 在这种情 况下 ,对于落入该子空间中的任何判别样本就不能 肯定其类别. 由此可以看出 , CF K ij 对于规则的提取及 判定起着至关重要的作用. 2 基于克隆选择的模糊规则提取 克隆选择算法是近年来提出的基于免疫学中的 克隆选择原理的一种人工免疫算法 ,该方法对具有 较高亲和力的抗体(可行解) 进行克隆 ,以贪婪搜索 为特征 ,通过高频变异和受体编辑[8 - 10 ] 方法 ,前者 微观调控 ,后者宏观控制 , 不断的保持抗体的多样 性 ,从而更有利于产生复杂优化问题的最优解. 与遗 传算法相比具有更快的收敛速度和更好、更稳定的 寻优能力. 由上述可知最关键的工作是如何从 SALL 中提 取高效紧凑规则集 OPT _ S . 这就是这一节采用克 隆选择算法[2 ]所要解决的问题. 为了提高算法的执 行速度 ,首先将无效规则即 CF K ij = 0 或 CF K ij ≈0 的 规则剔除 ,从而只剩余有效规则集 ,用 S 表示. 2. 1 亲和力函数的建立 要想 从 有 效 规 则 集 S 中 提 取 紧 凑 规 则 集 OPT _ S ,首先要确定其所应满足的目标和约束. 考虑到 OPT _ S 之所以是判断各类的最佳规则 正是因为通过样本学习他们能够确定的正确分类样 本个数及其确定度与其他规则相比要高 ,也即这些 规则空间不仅包含了大部分的该类样本 ,表明该类 样本在这些子空间出现频率比较高 ,同时这些空间 也能更有效地将该空间所代表的样本类别和其他种 类的样本分离 ,因而由这些空间所确定的判断某类 的规则基本或完全能够涵盖该类样本的出现范围 , 具有较高的分类能力 ;另外在保证其正确分类的基 础上 ,还希望规则数要尽量少 ,以减少规则搜索匹配 的时间 ,提高分类效率. 因此优化目标确定如下 : max R K ∑mn ∈OPT _ S CF K mn ∈CF K ij ( (NCP( R K mn ) ) ×CF K mn ) , min | OPT _ S | , (2) OPT _ S Α S Α SALL . 这里(NCP( P K mn ) ) ×CF k mn是指 OPT _ S 中规则 R K mn = r 能够正确分类的学习样本个数与其确定度 的乘积 ,反映规则的正确分类能力;| OPT _ S| 是指 OPT _ S 中包含的模糊规则总个数. 引入正权值 W NCP和 W S ,对式(2) 作如下修改 : maxf (OPT _S) = (WNCP · R K ∑mn ∈OPT _S ((NCP( R K mn ) ) × CF K mn ) ) - (W S ·| OPT _ S | ) , OPT _ S Α S Α SALL . (3) 一般地 ,一个分类系统的分类能力与其包含的 规则总数相比 ,前者更重要 ,不应为了得到一个精练 第 4 期 左瑞娟 ,等 :基于克隆选择的模糊分类规则提取算法 ·75 ·
·76· 智能系统学报 第2卷 的规则集，而一味的减少规则的个数，而牺牲其分类 体，因此涉及到抗体亲和力的计算 能力.因此只能在保证OPT_S具有较高的分类能 ①NCP(R)和CF的确定：NCP(R)是OPT 力的基础上使规则的个数尽可能少，这就与WxCp和 S中规则能正确分类的样本个数，即落入模糊子 Ws的取值比例有着密切的关系，其具体的比例关 空间的学习样本类型与该子空间确定的类相符的样 系可以根据实际需要通过实验仿真确定 本个数.由表1的数据结构可以确定该模糊子空间所 2.2抗体编码及解码 代表的类及其规则的确定度.由此可以确定 在克隆选择算法中，有效规则集S就构成了一 NCP(R)和CF 条抗体的基本结构，其基因位就是S的各有效规 ②OPTS1的确定：即计算OPT_S中所有1 则，而各基因位的标号是相应有效规则的规则号，二 的个数 者在抗体中是一一对应且位置固定的.抗体的长度 这样，由式3)可以计算出各抗体和抗原的亲和 设为1，由S中有效规则的个数决定.对于确定的学 力，并将这条抗体按亲和力大小降序排列，并取出其 习样本，所得到的有效规则是确定的并且是可知的 中亲和力较大的n条抗体，这里取n=N. 因此一条抗体的具体结构可以表示为 3)克隆：对以上所选择的n个抗体进行克隆，即 SS1s2…5m/m∈(r=1,2,:L,L=2+32++ 复制.每个抗体需克隆的抗体个数由式(4确定： 2,m为有效规则号，r为S中所有规则号) number =Bxy i (4) 在抗体中包含满足优化目标的规则集OPTS 式中：B为克隆因子，ì为将各抗体亲和力按降序排序 为此这里随机的为抗体中的基因位赋值1或-1，加 后的序号.这样n个抗体克隆总数用Nc表示： 以区别，即sm=-1:表示规则m属于S但不属于 Nc OPT_S,sm=1:表示规则m属于S同时又属于 >round(number) ) OPT_S,这样，就可得到一条类似于图2的一条抗体 式中：round为取整运算，并且亲和力越高的抗体其克 编码形式 隆的抗体个数越多 4)高频变异：克隆后的抗体以某一变异率发生变 1-1-1-1 11 异，抗体的变异率不仅和亲和力有关，还与进化代数 5 5n S Sr Ss Srm-1 Sm 有关，因此计算相应于某代的不同亲和力的抗体的变 异率a为 a exp(-p xf(OPT S)). 6) 图2抗体编码 式中：P为衰减系数，这里取p=Nsm,Nn为进化代 Fig.2 Antibody code 数.∫为抗体和抗原之间的亲和力.由变异率计算式 抗体优化的最终结果中基因位为1所对应的有 可以看到亲和力越大的抗体其变异率越小：进化代数 效规则即为OPTS. 越大变异率也越小.这里抗体的变异机制为sm= 为了计算抗体与抗原即亲和力函数的亲和力以 smX(-1),即对于克隆后的抗体按以上的变异率随 及确定OPTS中包含的规则，还需要对抗体进行解 机使抗体中的某些基因位上的值发生变化，通过改变 码，即将基因位值为1所对应的规则还原出来.首先 其符号来实现.其过程如图3所示 确定抗体中“1”所对应的规则号sm=r,然后根据规 1- -11 则号与模糊子空间的关系表（如表1(a)、(b)可以确 4 - 11 定对应的模糊子空间及规则 S Sn Sn Srs Si 444 Srm 1 Srm 2.3克隆选择算法的操作 基于克隆选择算法的模糊f-then规则提取过 程如下 图3抗体变异 1)初始抗体种群产生：产生一个包含N条抗体 Fig.3 Antibody mutation 的初始种群.每条抗体生成时，随机为其基因位分配 克隆后大量的抗体群发生变异，该过程使抗体亲 1、-1.在此根据抗体的长度分别以60%和40%为基 和力在局部不断提高起到微观寻优调控的作用，有利 因位赋值1和-1，从而随机产生N条抗体 于最优解的出现 2)选择：从当前种群选择n个亲和力较高的抗 5)再选择：该过程类似于2的选择过程，只是该 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
的规则集 ,而一味的减少规则的个数 ,而牺牲其分类 能力. 因此只能在保证 OPT _ S 具有较高的分类能 力的基础上使规则的个数尽可能少 ,这就与 W NCP和 W S 的取值比例有着密切的关系 ,其具体的比例关 系可以根据实际需要通过实验仿真确定. 2. 2 抗体编码及解码 在克隆选择算法中 ,有效规则集 S 就构成了一 条抗体的基本结构 , 其基因位就是 S 的各有效规 则 ,而各基因位的标号是相应有效规则的规则号 ,二 者在抗体中是一一对应且位置固定的. 抗体的长度 设为 l ,由 S 中有效规则的个数决定. 对于确定的学 习样本 ,所得到的有效规则是确定的并且是可知的. 因此一条抗体的具体结构可以表示为 S = sr1 sr2 …srm l ( rm ∈( r = 1 ,2 , …, L) , L = 2 2 + 3 2 + …+ K 2 , rm 为有效规则号, r为 SALL中所有规则号) . 在抗体中包含满足优化目标的规则集 OPT _ S 为此这里随机的为抗体中的基因位赋值 1 或 - 1 ,加 以区别,即 srm = - 1 :表示规则 rm 属于 S 但不属于 OPT _ S , srm = 1 :表示规则 rm 属于 S 同时又属于 OPT _S ,这样,就可得到一条类似于图 2 的一条抗体 编码形式. 图 2 抗体编码 Fig. 2 Antibody code 抗体优化的最终结果中基因位为 1 所对应的有 效规则即为 OPT _S. 为了计算抗体与抗原即亲和力函数的亲和力以 及确定 OPT _S 中包含的规则,还需要对抗体进行解 码,即将基因位值为 1 所对应的规则还原出来. 首先 确定抗体中“1”所对应的规则号 srm = r,然后根据规 则号与模糊子空间的关系表(如表 1 (a) 、(b) ) 可以确 定对应的模糊子空间及规则. 2. 3 克隆选择算法的操作 基于克隆选择算法的模糊 if - then 规则提取过 程如下: 1)初始抗体种群产生:产生一个包含 N 条抗体 的初始种群. 每条抗体生成时 ,随机为其基因位分配 1、- 1. 在此根据抗体的长度分别以 60 %和 40 %为基 因位赋值 1 和 - 1 ,从而随机产生 N 条抗体. 2)选择 :从当前种群选择 n 个亲和力较高的抗 体,因此涉及到抗体亲和力的计算. ①NCP( R K mn ) 和 CF K mn的确定 :NCP( R K mn )是 OPT _ S 中规则 R K mn能正确分类的样本个数,即落入模糊子 空间的学习样本类型与该子空间确定的类相符的样 本个数. 由表 1 的数据结构可以确定该模糊子空间所 代表 的 类 及 其 规 则 的 确 定 度. 由 此 可 以 确 定 NCP( R K mn )和 CF K mn . ②| OPT _ S| 的确定:即计算 OPT _ S 中所有 1 的个数. 这样,由式(3) 可以计算出各抗体和抗原的亲和 力,并将这条抗体按亲和力大小降序排列 ,并取出其 中亲和力较大的 n条抗体,这里取 n = N. 3) 克隆:对以上所选择的 n 个抗体进行克隆,即 复制. 每个抗体需克隆的抗体个数由式(4)确定: number = β×N i . (4) 式中:β为克隆因子, i 为将各抗体亲和力按降序排序 后的序号. 这样 n个抗体克隆总数用 NC 表示: NC = ∑ n i =1 round(number) . (5) 式中:round 为取整运算,并且亲和力越高的抗体其克 隆的抗体个数越多. 4) 高频变异 :克隆后的抗体以某一变异率发生变 异,抗体的变异率不仅和亲和力有关,还与进化代数 有关,因此计算相应于某代的不同亲和力的抗体的变 异率α为 α= exp ( - ρ×f (OPT _S) ) . (6) 式中:ρ为衰减系数,这里取ρ= Ngen , Ngen 为进化代 数. f 为抗体和抗原之间的亲和力. 由变异率计算式 可以看到亲和力越大的抗体其变异率越小;进化代数 越大变异率也越小. 这里抗体的变异机制为srm = srm ×( - 1) ,即对于克隆后的抗体按以上的变异率随 机使抗体中的某些基因位上的值发生变化,通过改变 其符号来实现. 其过程如图 3 所示. 图 3 抗体变异 Fig. 3 Antibody mutation 克隆后大量的抗体群发生变异 ,该过程使抗体亲 和力在局部不断提高起到微观寻优调控的作用 ,有利 于最优解的出现. 5) 再选择 :该过程类似于 2) 的选择过程,只是该 ·76 · 智 能 系 统 学 报 第 2 卷
第4期 左瑞娟，等：基于克隆选择的模糊分类规则提取算法 ·77· 选择是在经过高频变异后的种群中进行的.抗体再选 有很好的收敛效果：随着循环代数的增加，亲和力收 择的过程，是从变异的抗体群中找出变异较成功的n 敛达到最大值时，而规则个数也收敛至最小值，并且 个抗体，构成一个扩增抗体种群 收敛速度较快，其达到收敛的总循环代数N只需 6)新种群生成：在该过程中，将第5)步所得到的 80代.由此说明，文中所建立的目标函数（亲和力函 扩增抗体种群加入到1)中由N个抗体构成的种群 数)是合理的且适当的 中，并重新按亲和力降序排列找出其中亲和力最低的 表2亲和力及规则个数收敛情况 d个抗体.再随机产生d个抗体，替换上面的d个最 Table 2 Convergence about affinity and rules number 低亲和力的抗体，进行受体编辑，从而得到下一代的 代数 5 20 60 80 100 初始种群 亲和力 101.35135.16238.91253.93253.93 由5)6)可见克隆选择算法使每代的种群总是 朝着优良的变异方向进化，并采用受体编辑的手段有 规则个数 92 80 48 42 42 效地阻止局部寻优停滞的发生，从而更加有利于最优 3.2算法分类准确率及其稳定性 解的出现 以进化代数作为克隆选择的中止条件，当克隆选 表3是各循环代数下所得OPTS中的规则所 择的过程结束，抗体抗原亲和力达到稳定收敛后，可 确定的总分类准确率及其分类稳定性的统计.其中 以得到一个与初始种群相比平均亲和力高得多的抗 分类稳定性的统计采用的指标是分类准确率的标准 体种群.提取基因值为1的基因位对其进行解码得到 方差，反应了在随机情况下生成的规则集OPT_S 的分类稳定性】 对应的规则，考察该规则集的正确分类能力，并从多 次算法收敛后的抗体中找出正确分类能力最高的一 表3相应代数下所选规则的总分类正确率及 组构成最终的最优规则集OPT_S,从而完成克隆选 其分类稳定性统计 择算法对模糊f-then规则的提取 Table 3 Statistics a bout the classification correctness ratio and sta bility under different generations 3仿真结果 代数 5 20 60 80 100 经过多次实验，确定克隆选择算法中各参数设置 总分类 94 95 97.2 98.2 98.2 如下： 准确率/% 初始种群大小：N=6; 分类稳定性0.0230.0320.01160.00360.0036 克隆扩增种群大小：n=5; 循环代数：Nm; 由表3可以很清楚地看到：在收敛的情况下， 抗体变异率：a=exp(-p×f(OPT_S)),p= OPTS具有较高且较稳定的分类能力 Ngen 表4是在收敛的情况下最终确定的OPTS规 抗体中1与-1个数比例为：0.6：0.4： 则集合（共42条）的一部分，表4是通过Matlab编 正确分类能力与规则个数权值比值：WcP: 制程序的最终结果，每行为一条规则 Ws=1 :4 表4收敛情况下部分识别规则 Wcp:Ws的比值设定，经多次实验证明，当Ws Table 4 Part recognition rules in convergence 越大时，OPTS中包含的规则数就越多，经多次实验 1 23 4 5 678910 证明，在此二者比例选择为1：4时，所得规则的分类 111125.244500.627711111 能力较有保障，且分类性能比较稳定， 22220.247911.0000-11112 分类数据采用Matlab中自带的数据RIS,其包含 33250.64102 1.000011121 的数据类型为3类，共150个样本，每类50个样本. 44391.802000.33688-11122 以下是分别取Nm=10、20、30、50、80、100代 5513814.979001.000011211 分别进行10次仿真运算的平均结果 68220.232581.0000-11222 3.1算法收敛性效果 711210.109661.0000-12121 表2是抗体亲和力和规则个数的收敛情况.由 8123287.062900.6696512122 此可以很明显地看出该算法中亲和力和规则个数具 9163133.684300.8745612222 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
选择是在经过高频变异后的种群中进行的. 抗体再选 择的过程,是从变异的抗体群中找出变异较成功的 n 个抗体,构成一个扩增抗体种群. 6)新种群生成:在该过程中,将第 5) 步所得到的 扩增抗体种群加入到 1) 中由 N 个抗体构成的种群 中,并重新按亲和力降序排列找出其中亲和力最低的 d 个抗体. 再随机产生 d 个抗体 ,替换上面的 d 个最 低亲和力的抗体,进行受体编辑,从而得到下一代的 初始种群. 由 5) 、6) 可见克隆选择算法使每代的种群总是 朝着优良的变异方向进化,并采用受体编辑的手段有 效地阻止局部寻优停滞的发生,从而更加有利于最优 解的出现. 以进化代数作为克隆选择的中止条件,当克隆选 择的过程结束 ,抗体抗原亲和力达到稳定收敛后 ,可 以得到一个与初始种群相比平均亲和力高得多的抗 体种群. 提取基因值为 1 的基因位对其进行解码得到 对应的规则 ,考察该规则集的正确分类能力,并从多 次算法收敛后的抗体中找出正确分类能力最高的一 组构成最终的最优规则集 OPT _ S ,从而完成克隆选 择算法对模糊 if - then 规则的提取. 3 仿真结果 经过多次实验 ,确定克隆选择算法中各参数设置 如下: 初始种群大小: N = 6 ; 克隆扩增种群大小: n = 5 ; 循环代数: Ngen ; 抗体变异率:α= exp ( - ρ×f (OPT _ S) ) ,ρ= Ngen ; 抗体中 1 与 - 1 个数比例为:0. 6 :0. 4 ; 正确分类能力与规则个数权值比值: WNCP ∶ W S = 1 ∶4. WNCP ∶W S 的比值设定 ,经多次实验证明 ,当 W S 越大时,OPT _S 中包含的规则数就越多,经多次实验 证明,在此二者比例选择为 1 ∶4 时 ,所得规则的分类 能力较有保障 ,且分类性能比较稳定. 分类数据采用 Matlab 中自带的数据 IRIS,其包含 的数据类型为 3 类 ,共 150 个样本 ,每类 50 个样本. 以下是分别取 Ngen = 10、20、30、50、80、100 代 分别进行 10 次仿真运算的平均结果. 3. 1 算法收敛性效果 表 2 是抗体亲和力和规则个数的收敛情况. 由 此可以很明显地看出该算法中亲和力和规则个数具 有很好的收敛效果 :随着循环代数的增加 ,亲和力收 敛达到最大值时 ,而规则个数也收敛至最小值 ,并且 收敛速度较快 ,其达到收敛的总循环代数 Ngen只需 80 代. 由此说明 ,文中所建立的目标函数(亲和力函 数) 是合理的且适当的. 表 2 亲和力及规则个数收敛情况 Table 2 Convergence about affinity and rules number 代数 5 20 60 80 100 亲和力 101. 35 135. 16 238. 91 253. 93 253. 93 规则个数 92 80 48 42 42 3. 2 算法分类准确率及其稳定性 表 3 是各循环代数下所得 OPT _ S 中的规则所 确定的总分类准确率及其分类稳定性的统计. 其中 分类稳定性的统计采用的指标是分类准确率的标准 方差 ,反应了在随机情况下生成的规则集 OPT _ S 的分类稳定性. 表 3 相应代数下所选规则的总分类正确率及 其分类稳定性统计 Table 3 Statistics about the classification correctness ratio and stability under different generations 代数 5 20 60 80 100 总分类 准确率/ % 94 95 97. 2 98. 2 98. 2 分类稳定性 0. 023 0. 032 0. 011 6 0. 003 6 0. 003 6 由表 3 可以很清楚地看到 :在收敛的情况下 , OPT _ S 具有较高且较稳定的分类能力. 表 4 是在收敛的情况下最终确定的 OPT _ S 规 则集合(共 42 条) 的一部分 ,表 4 是通过 Matlab 编 制程序的最终结果 ,每行为一条规则. 表 4 收敛情况下部分识别规则 Table 4 Part recognition rules in convergence 1 2 3 4 5 6 7 8 9 10 1 1 1 12 5. 244 50 0. 627 7 1 1 1 1 1 2 2 2 2 0. 247 91 1. 000 0 - 1 1 1 1 2 3 3 2 5 0. 641 02 1. 000 0 1 1 1 2 1 4 4 3 9 1. 802 00 0. 336 88 - 1 1 1 2 2 5 5 1 38 14. 979 00 1. 000 0 1 1 2 1 1 6 8 2 2 0. 232 58 1. 000 0 - 1 1 2 2 2 7 11 2 1 0. 109 66 1. 000 0 - 1 2 1 2 1 8 12 3 28 7. 062 90 0. 669 65 1 2 1 2 2 9 16 3 13 3. 684 30 0. 874 56 1 2 2 2 2 第 4 期 左瑞娟 ,等 :基于克隆选择的模糊分类规则提取算法 ·77 ·
·78 智能系统学报 第2卷 现将其结构介绍如下： 表7WWs的不同比值对提取规则个数及分类 第1列表示所提取的规则号：第2列表示对应 能力的影响 规则的判定类别；第3列为规则所能正确分类的个 Table 7 Rules number and classification correctness ratio 数：第5列为规则的确定度；第6列值为1的规则 in different ratio of Wo,Ws 即所提取的规则OPT_S;第7、8、9、10列共同确定 WNCP Ws 1:1 1:4 18 1:10 规则的模糊子空间」 规则个数 125 2 17 10 利用该规则集对原始数据的识别情况如表5. 总体正确 95.3 982 92.7 86 分类能力/% 表5OPT_S对原始数据的识别情况 Table 5 Recognition rate on original data using OPT S 可以看出，随着Ws所占比重的增加，算法收敛 判定类别 判别情况 后所提取的规则个数不断减少，但是所得到的规则 1类 2类 3类 集合OPTS的分类能力并没有提高，这是由于在 拒识率/% 0 0 0 这种情况下，部分有效规则丢失，从而造成分类准确 错识率/% 0 率下降；另外，Ws所占的比重过小时，所提取的规 各分类正确率/% 100 98 96 则量增加，所得到的规则集合中包含很多低效规则 这些规则对于实际起作用的高效规则会造成干扰 综上可知，模糊空间经过分割精度分别为K= 因而也会影响到分类能力.所以对于WCp与Ws的 1,3,4,5,6的分割后，共可以产生2+3+4+ 比值的选取必须要经过多次调试，慎重选取，才能得 5+6=2274,去除无效规则共得到155条有效规 到规则个数适中、分类能力较强的规则集OPTS. 则，而最终提取的OPTS中规则总数仅42条，占 4结束语 总规则数的1.8%，占有效规则的27%.由表5可以 看出，总分类正确率为98%，该方法在保证了分类 将克隆选择算法用于模糊规则提取来解决分类 效果的基础上有效减少了规则的数量 问题，通过仿真实验检验，该算法具有较快的收敛速 另外将原始的IRIS数据略作改动，作为测试数 度和很好的收敛效果，并且该算法的分类准确率和 据，其识别效果见表6 稳定性非常高，该算法在分类问题上是合理有效的 表6OPT_S对新检验样本数据的识别情况 参考文献： Table 6 Recognition on ne w test data using OPT S [1]URSZULA M K.WOJCIECH T.Extraction of fuzzy 判定类别 判别情况 rules from trained neuarl network using evolutionary al- 1类 2类 3类 gorithm[A].ESANN'2003 Proceedings[C].Brussels, 拒识率！% 0 0 0 2003. 错识率/% 0 3.0 5.0 [2]TO KINA GA S,LU Jianjun,IKEDA Y.Neural network 各分类正确率/% 100.0 97.0 96.0 rule extraction by using the genetic programming and its applications to explanatory classifications [J ]Funda- 由表6可以看出，总分类正确率，97.7%，该分 Mentals,2005,88(10):2627.2635. 类规则集仍然能够以较高的分类能力对新样本进行 [3]康胜武.基于粗糙集理论的属性处理方法和模糊规则提 分类，说明文中所提出的这种新的基于克隆选择的 取及其应用研究[D].厦门：厦门大学，2001 模糊f-then规则的提取方法所提取的模糊规则具 KANG Shengwu.Attribute treatment fuzzy rules ex- 有较为理想的分类能力及容错能力 traction and application research based on rough set theo- 3.3WNP的Ws比值对于规则提取个数及分类能 ry[D].Xiamen:Xiamen University,2001. 力的影响 (4]MARGHN Y M H,EL-SEMMAN I E.Extracting fuzzy 表7讨论的是关于目标函数（亲和力函数）中， classification rules with gene expression programming 反映正确分类能力和提取规则个数的权值取值比例 [A].AIML'05 Conference [C].Cairo,Egypt,2005. [5]ISHIBUCHI H,NOZA KI K,TANA KA H.Distributed 对于算法中最终提取的规则个数及分类能力的影 representation of fuzzy rules and its application to pattern 响 classification[J ]Fuzzy Sets and Syst,1994,52(4):21 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
现将其结构介绍如下 : 第 1 列表示所提取的规则号 ;第 2 列表示对应 规则的判定类别 ;第 3 列为规则所能正确分类的个 数 ;第 5 列为规则的确定度 ;第 6 列值为 1 的规则 , 即所提取的规则 OPT _ S ;第 7、8、9、10 列共同确定 规则的模糊子空间. 利用该规则集对原始数据的识别情况如表 5. 表 5 OPT _S 对原始数据的识别情况 Table 5 Recognition rate on original data using OPT _S 判别情况 判定类别 1 类 2 类 3 类 拒识率/ % 0 0 0 错识率/ % 0 2 4 各分类正确率/ % 100 98 96 综上可知 ,模糊空间经过分割精度分别为 K = 1 ,3 ,4 , 5 , 6 的分割后 ,共可以产生 2 4 + 3 4 + 4 4 + 5 4 + 6 4 = 2 274 ,去除无效规则共得到 155 条有效规 则 ,而最终提取的 OPT _ S 中规则总数仅 42 条 ,占 总规则数的 1. 8 % ,占有效规则的 27 %. 由表 5 可以 看出 ,总分类正确率为 98 % ,该方法在保证了分类 效果的基础上有效减少了规则的数量. 另外将原始的 IRIS 数据略作改动 ,作为测试数 据 ,其识别效果见表 6. 表 6 OPT _S 对新检验样本数据的识别情况 Table 6 Recognition on new test data using OPT _S 判别情况 判定类别 1 类 2 类 3 类 拒识率/ % 0 0 0 错识率/ % 0 3. 0 5. 0 各分类正确率/ % 100. 0 97. 0 96. 0 由表 6 可以看出 ,总分类正确率 ,9717 % ,该分 类规则集仍然能够以较高的分类能力对新样本进行 分类 ,说明文中所提出的这种新的基于克隆选择的 模糊 if - t hen 规则的提取方法所提取的模糊规则具 有较为理想的分类能力及容错能力. 3. 3 W NCP的 W S 比值对于规则提取个数及分类能 力的影响 表 7 讨论的是关于目标函数 (亲和力函数) 中 , 反映正确分类能力和提取规则个数的权值取值比例 对于算法中最终提取的规则个数及分类能力的影 响. 表 7 WNCP 、WS 的不同比值对提取规则个数及分类 能力的影响 Table 7 Rules number and classification correctness ratio in different ratio of WNCP ,WS W NCP ∶W S 1 ∶1 1 ∶4 1 ∶8 1 ∶10 规则个数 125 42 17 10 总体正确 分类能力/ % 9513 9812 9217 86 可以看出 ,随着 W S 所占比重的增加 ,算法收敛 后所提取的规则个数不断减少 ,但是所得到的规则 集合 OPT _ S 的分类能力并没有提高 ,这是由于在 这种情况下 ,部分有效规则丢失 ,从而造成分类准确 率下降;另外 , W S 所占的比重过小时 ,所提取的规 则量增加 ,所得到的规则集合中包含很多低效规则 , 这些规则对于实际起作用的高效规则会造成干扰 , 因而也会影响到分类能力. 所以对于 W NCP与 W S 的 比值的选取必须要经过多次调试 ,慎重选取,才能得 到规则个数适中、分类能力较强的规则集 OPT _S. 4 结束语 将克隆选择算法用于模糊规则提取来解决分类 问题 ,通过仿真实验检验 ,该算法具有较快的收敛速 度和很好的收敛效果 ,并且该算法的分类准确率和 稳定性非常高 ,该算法在分类问题上是合理有效的. 参考文献 : [1 ] URSZULA M K , WOJCIECH T. Extraction of fuzzy rules from trained neuarl network using evolutionary al2 gorithm[ A ]. ESANN’2003 Proceedings[ C]. Brussels , 2003. [ 2 ] TO KINA GA S , LU Jianjun , IKEDA Y. Neural network rule extraction by using the genetic programming and its applications to explanatory classifications [J ]. Funda2 Mentals , 2005 ,88 (10) :2627 - 2635. [3 ]康胜武. 基于粗糙集理论的属性处理方法和模糊规则提 取及其应用研究[D]. 厦门 :厦门大学 ,2001. KAN G Shengwu. Attribute treatment & fuzzy rules ex2 traction and application research based on rough set theo2 ry[D]. Xiamen :Xiamen University ,2001. [4 ]MARGHN Y M H , EL2SEMMAN I E. Extracting fuzzy classification rules with gene expression programming [ A ]. AIML’05 Conference [C]. Cairo , Egypt , 2005. [ 5 ]ISHIBUCHI H , NOZA KI K , TANA KA H. Distributed representation of fuzzy rules and its application to pattern classification[J ]. Fuzzy Sets and Syst , 1994 , 52 (4) :21 ·78 · 智 能 系 统 学 报 第 2 卷
第4期 左瑞娟，等：基于克隆选择的模糊分类规则提取算法 ·79· .32 作者简介： [6]ISHIBUCHI H,NOZAKI K,YAMAMOTO N,et al. 左瑞娟，女，1975年生，讲师，主要 Selecting fuzzy if-then rules for classification problems u 研究方向为人工智能、计算智能、专家系 sing genetic algorithms [J].IEEE Trasactions on Sys 统、模式识别 tems,1995,3(3):260.270. Email :zuoruijuan200002 @163.com. [7]CASTRO L N,ZUBEN F J.Learning and optimization using the clonal selection principle[J ]IEEE Transactions on Evolutionary Computation,Special Issue on Artificial mmune Systems,2002,6(3):239.251. 武永华，男，1975年生，讲师，主要研 [8]GEORGE A J T,GRA Y D.Receptor editing during af- 究方向为模式识别、单片机与嵌入式系 finity maturation[J ]Imm Today,1999,20(4):196. 统 [9]BEREK C.ZIEGN ER M.The maturation of the immune response[J ]Imm Today,2002,14(8):400-402. [10]NUSSENZWEIG M C.Immune receptor editing,revise and select[U].Cell,1998,95(1):875.878. 第五届中国通信学术年会 The 5th china's Annual Conference on Communication 由中国通信学会主办，中国通信学会学术工作委员会承办，《通信学报》协办的“第五届中国通信学术年 会将于2007年12月在北京召开。中国通信学术年会是涵盖通信类各专业领域的综合性的学术会议，也是 全国通信界学术水平最高的盛会。本届学术年会将以我国即将进入移动通信3G时代，迎接2008奥运信息 通信为契机，以“迎接3G和奥运，构建和谐社会”为主题进行一次高水平的学术交流和讨论。年会将就现代 通信理论与技术的最新研究进展和发展趋势开展深入广泛的学术交流，并特邀著名专家、学者作专题报告。 本次年会的学术论文集拟由专业出版社正式出版，同时还将从到会宣读的论文中遴选出会议优秀论文 分别在《通信学报》正刊或专刊上发表。为保证本次会议的学术质量，吸引更多的高水平学术论文，现向广大 通信科技工作者公开征稿。 本次会议的主要征文范围包括（但不限于）以下领域：信息通信网络技术通信管理、光通信、无线及移动 通信、卫星通信P应用与增值业务通信软件通信理论与信号处理、通信专用集成电路、国防通信、通信安 全、电磁兼容通信设备制造、通信建设工程、通信线路通信电源、无线电应用及资源管理。 重要日期： 1)征文截止日期：2007年10月10日； 2)录用通知日期：2007年11月10日： 3)作者提交论文印刷版截止日期：2007年11月20日 投稿及联络方式： 1)投稿请通过电子信箱cicmeeting@om.com提交，邮件标题请注明“年会投稿”； 2)联系人：雷玲，E-amil:cicmeeting@tom.com,薄，E-amil:register@china-cic.org; 3)联系电话：01081787489,66061551,13269103820； 4)网址：http://meeting.china-cic.org.cn. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
- 32. [6 ] ISHIBUCHI H , NOZA KI K , YAMAMO TO N , et al. Selecting fuzzy if2then rules for classification problems u2 sing genetic algorithms [J ]. IEEE Trasactions on Sys2 tems , 1995 , 3 (3) :260 - 270. [7 ]CASTRO L N , ZUBEN F J. Learning and optimization using the clonal selection principle[J ]. IEEE Transactions on Evolutionary Computation , Special Issue on Artificial Immune Systems ,2002 ,6 (3) :239 - 251. [8 ] GEORGE A J T , GRA Y D. Receptor editing during af2 finity maturation[J ]. Imm Today , 1999 ,20 (4) : 196. [9 ]BEREK C. ZIEGN ER M. The maturation of the immune response[J ]. Imm Today , 2002 ,14 (8) :400 - 402. [10 ]NUSSENZWEIG M C. Immune receptor editing , revise and select[J ]. Cell , 1998 , 95 (1) :875 - 878. 作者简介 : 左瑞娟 ,女 , 1975 年生 ,讲师 ,主要 研究方向为人工智能、计算智能、专家系 统、模式识别. E2mail :zuoruijuan200002 @163. com. 武永华 ,男 ,1975 年生 ,讲师 ,主要研 究方向为模式识别、单片机与嵌入式系 统. 第五届中国通信学术年会 The 5th china ’ s Annual Conference on Communication 由中国通信学会主办 ,中国通信学会学术工作委员会承办《, 通信学报》协办的“第五届中国通信学术年 会”将于 2007 年 12 月在北京召开。中国通信学术年会是涵盖通信类各专业领域的综合性的学术会议 ,也是 全国通信界学术水平最高的盛会。本届学术年会将以我国即将进入移动通信 3 G时代 ,迎接 2008 奥运信息 通信为契机 ,以“迎接 3 G和奥运 ,构建和谐社会”为主题进行一次高水平的学术交流和讨论。年会将就现代 通信理论与技术的最新研究进展和发展趋势开展深入、广泛的学术交流 ,并特邀著名专家、学者作专题报告。 本次年会的学术论文集拟由专业出版社正式出版 ,同时还将从到会宣读的论文中遴选出会议优秀论文 分别在《通信学报》正刊或专刊上发表。为保证本次会议的学术质量 ,吸引更多的高水平学术论文 ,现向广大 通信科技工作者公开征稿。 本次会议的主要征文范围包括(但不限于) 以下领域 :信息通信网络技术、通信管理、光通信、无线及移动 通信、卫星通信、IP 应用与增值业务、通信软件、通信理论与信号处理、通信专用集成电路、国防通信、通信安 全、电磁兼容、通信设备制造、通信建设工程、通信线路、通信电源、无线电应用及资源管理。 重要日期 : 1) 征文截止日期 : 2007 年 10 月 10 日 ; 2) 录用通知日期 : 2007 年 11 月 10 日 ; 3) 作者提交论文印刷版截止日期 :2007 年 11 月 20 日. 投稿及联络方式 : 1) 投稿请通过电子信箱 cicmeeting @tom. com 提交 ,邮件标题请注明“年会投稿”; 2) 联系人 : 雷玲 ,E2amil :cicmeeting @tom. com ,薄 ,E2amil :register @china2cic. org ; 3) 联系电话 : 010281787489 ,66061551 ,13269103820 ; 4) 网址 :http :/ / meeting. china2cic. org. cn. 第 4 期 左瑞娟 ,等 :基于克隆选择的模糊分类规则提取算法 ·79 ·
