推荐星级：
- 1
- 2
- 3
- 4
- 5
基于免疫克隆选择的最优ECOC编码输出
资料介绍
纠错输出编码(Error Correcting Output Codes,ECOC)是解决模式识别领域多类分类问题的有效工具。在寻找最优编码输出的问题上,现有方法忽略了样本类别之间的相关性,导致学习效率和分类效果低下。为构造数据感知的编码矩阵,提出基于免疫克隆选择(Immune Clonal Selection Algorithm,ICSA)的最优纠错输出编码方法,将矩阵构造的多约束NP(Non-deterministic Polynomial,NP)难问题转换为优化搜索问题.首先基于分类精度和编码长度定义亲合度函数,然后结合样本知识改进变异交叉算子,根据约束性条件对矩阵进行搜索,从而快速有效地构建最优ECOC编码.实验表明该方法能够在提升多类分类精度的同时加快算法效率,而且输出的编码矩阵更加紧凑.
部分文件列表
| 文件名 | 大小 |
| 基于免疫克隆选择的最优ECOC编码输出.pdf | 2M |
部分页面预览
（完整内容请下载后查看）12
Vol． 46 No． 12
Dec． 2018
第
期
电
子
学
报
2018
12
ACTA ELECTRONICA SINICA
年
月
ECOC
基于免疫克隆选择的最优
编码输出
1
2
1
3
1
， ， ， ，
雷 蕾 余晓东 王晓丹 罗 玺 王艺菲
( 1．
，
空军工程大学防空反导学院 陕西西安
710051; 2．
，
空军研究院系统工程研究所 北京
100076;
3．
，
空军工程大学信息与导航学院 陕西西安
710077)
:
( Error Correcting Output Codes，ECOC)
。
是解决模式识别领域多类分类问题的有效工具
摘
要
纠错输出编码
， ， 。
在寻找最优编码输出的问题上 现有方法忽略了样本类别之间的相关性 导致学习效率和分类效果低下 为构造数据
，
感知的编码矩阵 提出基于免疫克隆选择
( Immune Clonal Selection Algorithm，ICSA)
，
的最优纠错输出编码方法 将矩阵
NP( Non-deterministic Polynomial，NP)
．
难问题转换为优化搜索问题 首先基于分类精度和编码长度定义
构造的多约束
， ， ，
亲合度函数 然后结合样本知识改进变异交叉算子 根据约束性条件对矩阵进行搜索 从而快速有效地构建最优
ECOC
． ，
编码 实验表明该方法能够在提升多类分类精度的同时加快算法效率 而且输出的编码矩阵更加紧凑
．
:
;
;
;
;
;
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
多类分类 纠错编码 免疫克隆选择 数据感知 编码矩阵 多约束优化
TP391 0372-2112 ( 2018) 12-3044-06
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 12． 031
:
:
A
:
文章编号
文献标识码
电子学报
An Optimization Strategy of ECOC Coding
Matrix-Based on Immune Clonal Selection Algorithm
1
2
1
3
1
LEI Lei ，YU Xiao-dong ，WANG Xiao-dan ，LUO Xi ，WANG Yi-fei
( 1. The Air and Missile Defense Institute，Air Force Engineering University，Xi’an，Shaanxi 710051，China;
2. The Systems Engineering Institute，AIR Force Research Institute，Beijing 10076，China;
3. The Information and Navigation Institute，Air Force Engineering University，Xi’an，Shaanxi 710077，China)
Abstract: Error correcting output codes ( ECOC) is a powerful tool to solve multi-classification problem． The exist-
ing methods of seeking the optimal coding matrix ignore the correlation between classes，which leads to bad performance in
learning speed and classification accuracy． In order to construct data-driven coding matrix，an optimization strategy of coding
matrix based on immune clonal selection algorithm ( ICSA) is presented． The strategy reduces the multiple constraints non-
deterministic polynomial problem ( NP) of finding the optimal coding matrix to a finite heuristic search problem． Firstly，the
affinity function based on accuracy and coding length is defined． Then，the mutation，crossover and selection operator are
modified respectively． Meanwhile，the validity constraints are combined to execute the quick search． The experiment results
based on UCI and traffic data prove that the proposed strategy can enhance the classification performance and accelerated the
speed． The output coding matrix is more compact as well．
Key words: multi-classification; ECOC; immune clonal selection algorithm; data driven; coding matrix; multiple con-
straints optimization
． ，
坏 由于事前编码忽略了样本数据包含的类别信息 分
1
引言
． ，
类性能无法达到最佳 因此 如何构造符合问题域的编
( Error Correcting Output Codes，
4 纠 错 输 出 编 码
．
码矩阵成为研究的重点
经典的数据感知编码方法有判别式纠错输出编码
［1］
ECOC)
，
作为一种分解策略 已成为解决多类分类问
．
题的第一方案 编码矩阵的构造作为纠错输出编码多
［2］
( Discriminate ECOC，DECOC)
，
基类子集再分割
方法
的编码方法
，
类分类的第一步 很大程度上决定了其分类性能的好
［3］
( Subclass ECOC，SECOC)
．
周进登提出基
: 2017-03-16;
: 2017-12-14; :
责任编辑 覃怀银
收稿日期
修回日期
:
基金项目 国家自然科学基金
( No． 61806219，No． 61876189，No． 61503407)
3045
12
: ECOC
蕾 基于免疫克隆选择的最优 编码输出
第
期
雷
，
于混淆矩阵的编码方法 利用混淆矩阵计算多类问题
．
性和有效性
，
中各类别的相关性 基于
Fisher
准则找出最有利于分类
3
ECOC
编码方
基于免疫克隆选择的最优
［4］
，
的类别组合 根据组合方案构建编码矩阵
． LEI
基于
—ICSA-ECOC
法
SVDD
对原始类别进行子类划分并利用二叉树构建层
［5］
3. 1
抗体编码及亲合度函数设计
． Bautista
次纠错输出编码
利用遗传算法来优化编码
ICSA-ECOC
，
采用结构体形式对抗体进行编码 表
，
矩阵的构造 将初始
ECOC
，
编码矩阵看作遗传个体 经
:
示为
．
过交叉和变异形成新的编码矩阵 新矩阵不仅具有较
struct I = { M，C，E，}
ε
( 1)
， ，
高的差 异 性 而 且 简 化 了 特 征 空 间 提 高 了 收 敛 速
［6］
M = ( m )
，m { 1，0，－ 1}
∈
ij
，
为编码矩阵 在生成初始
．
度
但如何设计编码矩阵使其在拥有优秀分类能力
ij N × l
［11］
，
种群时 令编码长度
l = Int「log N? ，N
． C
为类别数
l
为 个基分类器在验证集
．
的同时最大限度地减小编码长度仍是一个重要的难题
2
． E = ( e )
i
为多类混淆矩阵
，
鉴于此 本文提出基于免疫克隆选择算法的最优
1 × l
．
上的分类正确率 ε 为
M
在验证集上的多类分类错
ECOC ( the Optimal ECOC matrix based on Im-
编码方法
mune Clonal Selection Algorithm，ICSA-ECOC) ．
．
误率
该方法通
．
亲合度函数反映了各个抗体的优劣程度 通常来
，
过免疫克隆算法对初始编码矩阵进行编码 利用样本
，
数据先验知识设计亲合度函数 并对矩阵进行正确率
，
讲 衡量一个编码矩阵优劣程度最直观的指标就是分
、 、 ，
变异 扩展变异 交叉操作 结合约束性条件搜索最优个
，
类器正确率 而编码的纠错能力则受矩阵长度的影响
．
，
体 输出最优编码矩阵
．
，ICSA-ECOC
为综合衡量编 码性能
定义 亲 合 度 函 数
:
如下
2
ECOC
编码最优化设计
1
f( I ) =
k
( 2)
+ l
λ
Ik
数据感知编码矩阵通常是已知问题域和基分类器
ε
Ik
．
构造使分类错误率最小的编码矩阵 随着二类分类器
I
其中 ε 为抗体 对应的多类分类器在验证集上的分类
k
Ik
，
研究的深入 特别是基于结构风险最小化的支持向量
，l ， ．
错误率 为对应编码矩阵长度 λ 为一常数
Ik
，
机的提出 任何数据都可以找到与之对应的二类分类
3. 2
3. 2. 1
在生物免疫系统中 选择应答的抗体依据其亲合
克隆交叉变异操作
， N ， N
函数 即测试样本总能找到一个 维空间 在这 维空
克隆操作
． ，
间中线性可分 因此 构造数据感知的编码矩阵实质上
，
，
是一个多约束组合优化问题 然而这被证明是一个
NP
，
力进行一定规模的克隆 克隆的数目与其亲合力成正
［7］
．
NP
难问题提供了新
难完全问题
而进化算法为解决
． ，
比 基于这一原理 对每个抗体进行克隆操作
:
C
．
途径
T ( I ) = I
k
O
Θ
k
( 3)
c
k
人工免疫算法是模拟生物免疫系统功能和原理来
，O
1
q
，q
I
为抗体 克隆
k
其中
为元素值为
的
维向量
k
k
k
． 2002 ，Castro
年 首次
处理复杂优化问题的自适应系统
，
后的规模 其大小与亲合度函数相关
:
， 、
提出了克隆选择算法 并成功将其应用于组合优化 数
f( I )
k
n ×
c
［8］
n
q
= Int
( 4)
．
，
但在其算法实现过程中 克隆的父代
k
值优化等领域
[
]
f( I )
k
∑
，
和子代间只有单纯抗体的复制 没有不同抗体间的交
k = 1
n
，n
，n
为抗体规模
＞ n．
3. 2. 2
变异操作为抗体的迭代产生潜在的个体 实现全
． ICSA-ECOC
为克隆扩增后总的抗体种群规模
， ． ，
流 无法促进抗体种群自我进化 针对此问题 焦李成等
c
c
、 ，
构造了适用于人工智能的克隆 记忆及遗传算子等 并
［9，10］
变异操作
．
提出了基于柯西变异的免疫单克隆策略
，
ECOC
基于免疫克隆选择算法的最优
编码方法将
局搜索
变异操作
( 1)
方法基于样本数据设计了不同的
，
初始编码矩阵看作克隆个体 采用结构体形式对矩阵
．
， 、 ，
及其性能指标进行编码 改进克隆 变异和交叉操作 生
正确率变异操作
，
成新种群进行迭代 并从子种群中选择最优个体作为
A = ( a )
，a j
为第 列分类
ij
．
最终编码输出 通常一个有效的
ECOC
给定一个正确率矩阵
编码矩阵应满足
ij N × l
i ．
器对验证集中第 类样本的分类正确率 如果
m = 1，a
ij
，
矩阵中无重复行 无全
0、 1
全
， 、
列 无重复列 互补列三
ij
= 0，
意味着分类器
h
C
0，
类样本的分类正确率为
．
个基本约束性条件 在免疫克隆选择算法搜索最优编
对
j
i
。 ，
即分类完全错误 此时 应将码字
m
－ 1，
变为 其余码
， ，
码矩阵的过程中 由于变异交叉操作 编码矩阵中的码
ij
． 1
字维持不变 算法 给出了基于正确率变异 的具体
． ， ，
字会发生变化 因此 在每次对矩阵进行操作后 都要用
，
约束性条件进行逐一检验 保证输出编码矩阵的可用
．
步骤
全部评论(0)