第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 ·