用纠错编码改进Mry支持向量机多类分类算法

1、用纠错编码改进的 M-ry 支持向量机多类分类算法摘要：针对m-ary支持向量机(svm)多类分类算法结构简单，但泛 化能力较弱的特点 , 提出了与纠错编码理论相结合的改进的 m-ary svm算法。首先，将原始类别信息编码作为信息码；然后结合纠错编 码理论及期望的纠错能力 , 产生一定程度上性能最佳的编码 , 作为 分类器训练的依据 ； 最后, 对于识别阶段输出编码中的错误分类利 用检错纠错原理进行校正。实验结果表明 , 改进的算法通过引入尽 可能少的冗余子分类器增强了标准 m-ary svm 多类分类算法的性 能。关键词:m-ary;支持向量机;纠错编码；多类分类;最小码间距离；输 出校正

2、码enhanced m-ary support vector machine byerror correction coding for multi-category classification 英文作者名 bao jian, liu ran* 英文地址 (school of computer science, hangzhou dianzi university, hangzhou zhejiang 310018, china) abstract: m-ary support vector machine (m-ary svm) for multi-category classificat

3、ion has the advantage of simple structure, but the disadvantage of weak generalization ability. this paper presented an enhanced m-ary svm algorithm in combination with error correction coding theory. the main idea of the approach was to generate a group of best codesbased on information codes deriv

4、ed from the original category flags information, then utilize such codes as the basis for training the classifier, while in the final feed-forward phase the output codes composedof each sub-classifier could be corrected by error detection and correction principle if there exists any identifying erro

5、r. the experimental results confirm the effectiveness of the improved algorithm brought about by introducing as few sub-classifiers as possible. key words: m-ary; support vector machine (svm); error correction coding; multi-category classification; minimum code distance; output correction code0 引言 作

6、为机器学习实现方法之一的统计学习理论 (statistical learning theory, slt), 以及基于此理论的支持向量机 1-2(support vector machine, svm) 凭借其显著的性能优势 , 近 年来得到广大研究人员的关注 ,并已取得了大量的研究成果 , 而此 前作为研究热点的人工神经网络 (artificial neural networks, ann)虽然在工程实践中得到广泛的应用，但由于其建立在大数定理 的渐近理论之上 , 要求学习样本足够多 , 且容易陷入局部极值或过 学习的困境 ,并且在实际应用中隐含层的层数及每层神经元数目如 何确定仍无规律可循

7、 , 只能凭借使用者的经验进行实验试凑。正是 由于神经网络自身存在的这些不足 , 导致了支持向量机算法研究的兴起标准支持向量机是针对两类分类问题提出的 , 根据有限样本信息在 模型复杂性和学习能力之间寻求最佳折中 , 即通过最大化分类间隔 得到最大的泛化能力 , 但是现实中的大多数模式识别问题都是多类 分类问题 , 对此, 通常的解决方法主要有 4 种: 一类对一类 (one-against-one, oao) 、一类对其余 (one-against-rest, oar) 、 有向无环图 svm3(decision directed acyclic graph svm,ddagsvm)和m-a

8、ry svm4。此外，一些学者研究了其他一些针 对特定多类分类问题的解决方法 , 如针对多类分类情况下可能会出 现不可分区域及训练样本中存在噪声的情况，李广丽等5在svm的 输入端通过引入模糊隶属度函数对输入数据进行转换并对利用改 进的序列最小优化算法求解模糊多类分类支持向量机 , 从而获得较 好的性能；于清等提出了一种被称作2_a_2的多类分类方法，将 最少数量的子分类器结合在一起并分利用每个子分类器的识别结 果来实现多类分类，但是 , 这些算法通常存在着针对性强、泛化能 力弱、训练速度慢等不足。文献 7 对 oao、oar 和 dagsvm 3 种多 分类svm模型结构和性能进行了分析比较

9、，并且指出第一种和第三 种方法更加实用；文献8对5种多类分类svm方法(oao、oar、二 叉树法、纠错输出编码 (error correction output code, ecoc)法和ddagsvm)的原理和实现方法进行了介绍和分析，从速度和精度两 方面对这些方法的优缺点进行了归纳和总结，研究如何用精简的结 构模型充分发挥支持向量机算法的优势对于工程实践应用有着深刻的意义。嵌入式系统近年来得到广泛的普及 , 但是由于其小存储容量、低功 耗以及软硬件精简等限制 , 如何将高效的算法应用于嵌入式系统也 成为研究的一大热点 , 支持向量机作为最新且较有潜力的机器学习 算法, 在嵌入式系统中的理

10、论研究和应用也已有了一定的发 展,anguita等9-10将普通支持向量机算法中的参数表示利用分 枝定界法转化为整型 , 从而使得在资源有限的嵌入式系统中能够实 现svm算法,并对经典算法实现时又引入了区间算术法，简化了搜索 空间的上下界，并且提出了硬件友好型svm的实现方法。国内也有 不少这方面探索研究，文献11对bp神经网络和支持向量机的优化 过程进行了详细的研究 ,并给出了两种算法在嵌入式系统中实现的 改进措施, 并采用基于迭代的选择策略 12 逐步减小问题规模以利 于在嵌入式系统下训练svm；文献13-15针对不同的平台将支持向 量机应用于解决具体的模式识别问题，这些研究和实现对支持向

11、量 机在嵌入式系统中的应用有着指导意义。本文以 m-ary 支持向量机算法为基础 , 结合检错纠错理论提出了改 进的具有纠错能力的 m-ary 支持向量机算法 , 分析了其原理和实现 方法, 并以 pc 和嵌入式系统为平台 , 以手写数字识别程序来验证其 性能。第3期 包健等: 用纠错编码改进的 m-ary 支持向量机多类分类算法计算机应用 第 32 卷 1m-ary svm 模型1.1 标准 m-ary svm 算法m-ary 支持向量机是在 2000 年由 sebald 和 buchlew 等提出的 , 由 于精简的结构模型和较少的子分类器数量 , 使得问题求解规模得到 较大的简化。标准

12、m-ary 支持向量机的结构如图 1 所示。 与其他多类分类方法相比 , 此算法大大减少了子分类器数量 ,因此 简化了求解模型 , 但是其最大的缺陷就是容错性较差 , 若在计算过 程中,某个子分类器的判别失误造成符号取反 , 则会导致整个判别 结果错误 , 因此其泛化能力受到了较大影响 ,这也是影响其实际应 用的主要因素 ,关于该算法的应用研究及改进方案 , 也在逐渐被研 究人员所关注 16-18 。1.2m-ary svm 的性能研究和应用较多的 oao 和 oar 多类分类支持向量机算法 , 主要缺点 是需要构造较多的子支持向量机 ,不仅浪费了较多的系统资源 , 而 且增加了训练时间 ,

13、因此对于软硬件条件要求苛刻的嵌入式系统并 不适用 , 而对于性能相对优越的 m-ary svm 的性能分析的文献不多 , 从直观上来分析，假设训练集t中共有p个不同的类别和n个训练 样本, 按照上述多分类支持向量机的构造方法 , 各算法应有的子 svm 数目(nclass)、需训练的参数数量(nparam)以及训练时间(ntime) 如表1所示,其中m为子分类器数量,r是与训练算法有关的系数， 如采用smo算法时,r 2。表格(有表名)表14种多类分类器性能比较-p (p-1)/svmnclassnparamntimeoaop(p-1)/2(p-1)no(2n/p)r2) oarp-1p no

14、(p nr)ddagp(p-1)/2(p-1)no(2r-1 p2-r nr)m-arylb pn lb po(m n2)从表 1 可看出： m-ary svm 仅需要构造对数级数量的子分类器 , 不 仅使求解规模得到简化 ,同时大大降低了问题的复杂性 , 且训练速 度得到较大的提高，使得其成为最快的svm算法,从理论上讲，只要 对其子分类器的参数选择得当 , 其整体性能会有较大的改进。2 改进的 m-ary 算法2.1 改进算法的提出一些学者提出的纠错输出编码 (error correcting output code, ecoc) 支持向量机 19-20, 将常规的支持向量机算法与纠错编码

15、相 结合, 通过纠错编码来对子分类器的输出进行纠错 , 从而增强了模 型的泛化性 , 通常的 ecoc svm 是利用某种纠错码构造方法 ( 如文献 19 中提到的详尽编码法、列选择法、爬山法等 )得到合适的码字 , 然后将不同的码字分配给不同的类别作为训练的依据 , 每个子分类 器分别对应码字的不同位 , 也就是码字的位数对应于分类器中子分 类器的数量 ,这种方法不仅充分利用了支持向量机的两类特性 , 同 时也降低了问题的复杂性 , 但是并没有将原始信息码作为构造码字 的依据,选取的码字直接影响了分类器的性能。针对这一问题 ,本文 提出了改进的 m-ary 支持向量机算法。以手写数字识别程序

16、为目标 , 待识别的目标类也因此有 10类(即待 识别的10个数字：0,1，,9),则所使用的m-ary子分类器数目应为lb 10=4,根据上面所提到的子svm类别划分规则,4个分类器中的类别标识如表2所示。2.2输出校正m-ary算法本文以标准m-ary svm类别划分编码为信息码，采用纠错能力可控 的编码方法，加入适当的校验位，共同构成码字，称为校验码。训练 后通过检错纠错原理对实际输出进行校验，进而对出错的分类模式 进行校正，可把该算法称为输出校正 m-ary支持向量机(output correcting m-ary svm, oc-msvm),将其应用于 pc禾口嵌入式系统下的多类模式

17、识别问题，并用手写数字识别程序来验证该实现。此处 将m-ary svm与纠错编码相结合，使其校验法能够检测模型中子分 类器输出中的错误分类并纠正该错误，以期获得比标准算法更高的 泛化能力。限于具体的应用要求，以及简化解码的复杂性要求，可比较分析线 性循环码中的系统码的码长及设计最小距离在m-ary svm性能改进方面的影响，进而设计能够满足性能要求的输出校正m-ary svm模型。由纠错编码原理可知，当设计编码的最小码间距离为 dmin时： 若dmine+1,则码组内可检出不多于 e个错误；若dmin2t+1,则 码组内可纠正不多于t个错误;若dmint+e+1,其中e>t,则码组内 可

18、纠正不多于t个错误，同时检测e个错误。由于bch码是纠错能力可控的循环码，能够纠正多个随机错误，并且可以根据期望纠错的个数构造出理想码字。本文选用bch编码方法进行校正m-ary svm的输出,针对l,m,d码(l为码长,m为信息 位长,d为编码的最小距离）,设计具有不同纠错能力的码字t,并作 为训练m-ary svm的输入特征分类向量，则原信息码对应于纠错编 码的高m位。假设原训练样本为（xi,yi）, 其中xi为样本特征向量,yi为类标签（即yi=O,9）,并表示为表3所示的编码，利用纠错编码方法编码 后码字的二进制位数为I,则输出校正m-ary算法描述如下：1）利用式（1）和式类别划分规

19、则及2.1节中类别编码方法将yi 编码为表3所示码字ci,其中ci 0,14。2）以ci为信息码,利用选定的编码规则进行编码，生成对应码长为l、最小码距为d的码字ci*,其中ci* 0,1l, 高4位即为ci; 为提高训练过程计算效率，在算法实现时引入了掩码技术，即为每 个子分类器svmj分配掩码maskj二2j-1,其中j=1,2,l。3）将编码后的训练样本即（xi,ci*）输入各个子分类器svmj（其中j=1,2，,l）进行训练：将该训练样本的类别编码ci*与maskj进行 位与操作，即ci* maskj,若结果为0,则将该样本作为负类样本； 否则,若结果为非0,则将该样本作为正类样本，用

20、输入的样本训练 该两类分类svm。4）将待识别样本输入已训练好的分类器模型中各个子分类器svmj,并得到其输出yj,按照子分类器编号组成编码ti,即ti=ylyl-1 y1, 其中 yj 0,1。5）利用检错原理检查编码ti是否合法,如果合法，则可直接利用所 得编码的高k位得到分类结果ci*:此处可直接将ti右移l-4位得 到4位信息码，即ci* = ti >> (1-4); 否则，利用纠错原理对ti进 行校正,然后再对ti右移1-4位得到分类结果。因此,在预测新的样本时，第5)步对实际分类器分类编码利用检错 纠错原理进行必要的检错纠错后得到其所属类别，该算法可在一定 程度上克服标

21、准m-ary支持向量机容错性较差的缺点。从上述过程可以看出，由于生成的码字长度直接决定分类器的复杂 度,因此输出纠错m-ary支持向量机算法的目标明确，即把长度为lb k的原贻类别编训作为信息码，根据选定的编码方法编码为具有最小距离可控的码字，因此得到的类别编码不论是在编码难易 程度方面还是追求最小码间距离方面，实际是在一定程度上最优的 文献19中提到的ecoc编码方法如详尽编码法和列选择法由于是 针对长度为指数级的编码进行操作的，在类别稍多时工作量太大而 不再实用，爬山法追求的是编码矩阵的行最小距离与列最小距离之 和最大,虽然可以码字长度可控，但码间最小距离并不能保证是最 优的,且其中的随机

22、性较大。在下面的实验中将用爬山法与bch法获得等长的码字，并对两者的性能进行比较。3实验设计及分析本实验中用到的训练样本为28X 28像素的手写数字图片经过预处 理、二值化、去除边界像素并按照灰度级进行规范化后 ，从中提取 12X 12个的特征,按照一行一行首尾相连形成一个 144维的输入向 量,实验的样本如图2所示。图片图 2 实验中样本示例 在此基础上 , 对于实际输出的分类编码进行解码后 ,通过纠错程序 对输出进行必要的纠错 ,然后用编码的高 k 位信息码获得实际的类 别输出。实际用到的模型如图 3 所示。图片图 3 改进的 m-ary svm 模型结构图3中:x为输入训练样本，yj为子

23、分类器svmj的输出（j=1,2,1 且yj=0或I）,ylyl-1yl为各个子分类器分类输出按照子分类器 序号递减顺序组成的二进制码串。从 10000个图片中随机选取 5 组数据作为训练样本和测试样本 （ 每 组数据包括 2000个训练样本和 1000 个测试样本 ）, 在 pc 上对标准 m-ary 算法和本文提出的输出纠错 m-ary 算法进行实验 , 并以 5次实 验的平均值作为结果。同时 , 为进一步比较分析输出纠错 m-ary svm 算法的性能 , 实验中对随机编码法 ecoc svm 进行了实验 , 得出两种 算法的性能比较结果 , 如表 4 所示, 其中 oc 代表输出纠错

24、m-ary svm,ecoc 代表 ecoc svm, dmin 为对应码长码组的最小距离 ,prec 为各组 1000 个测试样本分类正确率的平均值 ,ttime 为各组测试样 本的总的分类时间的平均值。表格（有表名）表4pc上oc_msvm与 ecoc svm 性能比较码长oc-msvmdminprec/%ttime/secoc-svmdminprec/%ttime/s4188.565 .77188.577.347392.2010.78290.4312.918391.8812.04391.2514.7312594.2217.83593.3722.5114796.5622.78593.252

25、7.03! 根据情 况左右加注：码长为4时的oc-msvm为标准 m-ary svm。从表 4 容易看出 : 无论是 oc-msvm 还是 ecoc svm, 随着纠错编码码 长的增加,分类器的分类精度都有不同程度的提高。同时 ,由于所需 要的子分类器数量的增加 , 所需要的分类时间也会明显的增加，并 且在相同的条件下本文提出的输出纠错 m-ary svm 的性能要优于随 机编码法 ecoc svm。由于此研究的目标是支持向量机能够在嵌入式系统下的应用实现 , 因此在嵌入式系统环境中对两者的性能进行了相同的实验 , 得到的 性能结果如表 5 所示（参数含义同表 4）。表格（有表名）表5嵌入式系

26、统下oc-msvm与ecoc svm性能比较 码长 oc-msvmdminprec/%ttime/secoc-svmdminprec/%ttime/s4185.107 .34185.047.387387.3213.66286.2613.548387.0615.82386.7215.8812589.7223.04589.3623.1614792.5427.41588.9227.43! 根据情 况左右加注：码长为4时的oc-msvm为标准 m-ary svm。同样，在嵌入式系统下，本文提出的输出校正m-ary svm的性能比标 准 m-ary svm 性能有了一定的改善。在训练速度方面 , 由于

27、m-ary 算法的时间复杂度为o（m n2）,而对于各种码长的svm训练过程中 训练样本数量n均相同,不同的是子分类器数量 m,因此随着码长I 的增加,相应的子分类器数量增加 , 因此算法的训练时间也就相应 地增加 , 从实验结果中不难看出这一结论。此外, 与编码相关的因素即最小码距 dmin 也反映在了上述数据中 最小码距直接影响分类器的性能 ,表 45中码长为 7,12,14 的码字 最小距离分别为 3,5,7, 其分类精度随最小距离的增加依次提高 , 但 同时可以看出 , 对于长度相同的编码 , 由随机编码法得到的码字并 不是最佳的 , 两种方法对于长度为 7 和 14 的编码的最小距离

28、不同 , 因此其性能也就存在一定的差别 , 并且改进算法的性能要优于 ecoc svm;另外,oc-msvm中码长为7和8的码字最小码距均为3,虽然后 者增加了一位的码长 , 这也增加了判错的概率 , 可以看出后者的分 类精度较前者略低，对于ecoc svm,由于最小距离相同，码长为12和 14 的编码对应的分类器分类精度并不随码长增加而增加 , 反而随码 长增加其精度下降 , 因此码长越长并非意味着分类器的性能越好。4 结语本文针对m-ary svm泛化性不足的缺陷，利用纠错编码原理，充分结 合了支持向量机二类分类问题的特点 , 将训练样本的初始类别利用 纠错编码技术编码为二进制码串 , 使

29、得标准 m-ary 支持向量机算法 通过引入适当的冗余子分类器来达到提高该算法泛化性的目的。本 文详细地阐述了输出纠错 m-ary svm 算法实现过程 , 并从实验结果 验证了此改进算法的可行性 ,同时也得到在性能改进方面的一些结 论, 码长和最小码距成为 m-ary svm 算法改进方面两个必须考虑的 因素, 这也成为分类精度和分类时间两者折中考虑的结合点。进一 步的工作是定量分析码长及码间最小距离在 m-ary svm 性能改进上 的影响,从而寻求码长及最小距离在算法改进上的最佳折中。 参考文献 :1 vapnik v n.统计学习理论的本质m.张学工，译.北京：清华大学出版社，2000

30、.2 cortesc, vapnik v n. support vector networksj.machinelearni ng,1995,20(3):273-297.3 platt j c, cristia nini n, taylor j s. large margin dagsfor multiclass classificati on c n ips99: proceedi ngsof neural informationprocessing systems. cambridge, ma: mitpress,2000:547-553.4 sebald d j,bucklew j a.

31、 support vector mach ines and themultiple hypothesis test problemj. ieee tran sacti ons onsig nal process ing, 2001,49(11): 2865-2872.5 李广丽,崔广顺.一种改进的模糊多类支持向量机算法j. 计算机测量与控制,2011,19(4):908-914. 于清,赵晖.一种2_a_2支持向量机多类分类新方法j. 计算 机工程与应用,2008,44(25):186-188.7 hsu c,l in c. a comparis on of methods for multi

32、classsupport vector machi nesj. ieee tran sacti ons on n euraln etworks,2002, 13(2):415-425.8 苟博,黄贤武.支持向量机多类分类方法j.数据采集与处理,2006, 21(3):334-339.9 anguitad, ghio a, pischiutta s. a support vector machine with in teger parametersj. n eurocomput ing, 2008,72(1/2/3):480-489.10 anguita d, ghio a,pischiutta s. a hardware-friendlysupport vector machine for embedded automotive applicationsc/ proceedings of internat