多分类孪生支持向量机研究进展-丁世飞 , 张健 , 张谢锴 , 安悦瑄.pdf

上善若水

139

20页

0次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2018,29(1):89108 [doi: 10.13328/j.cnki.jos.005319] http://www.jos.org.cn

多分类孪生支持向量机研究进展





丁世飞

1,2

张

健

张谢锴

安悦瑄

(中国矿业大学计算机科学与技术学院,江苏徐州 221116)

(中国科学院计算技术研究所智能信息处理重点实验室,北京 100190)

通讯作者: 安悦瑄, E-mail: 1187360089@qq.com

摘要: 孪生支持向量机因其简单的模型、快速的训练速度和优秀的性能而受到广泛关注.该算法最初是为解决

二分类问题而提出的,不能直接用于解决现实生活中普遍存在的多分类问题.近年来,学者们致力于将二分类孪生支

持向量机扩展为多分类方法,并提出了多种多分类孪生支持向量机.多分类孪生支持向量机的研究已经取得了一定

的进展.主要工作是回顾多分类孪生支持向量机的发展,对多分类孪生支持向量机进行合理归类,分析各个类型的多

分类孪生支持向量机的理论和几何意义.以多分类孪生支持向量机的子分类器组织结构为依据,将多分类孪生支持

向量机分为:基于“一对多”策略的多分类孪生支持向量机、基于“一对一”策略的多分类孪生支持向量机、基于“一

对一对余”策略的多分类孪生支持向量机、基于二叉树结构的多分类孪生支持向量机和基于“多对一”策略的多分

类孪生支持向量机.基于有向无环图的多分类孪生支持向量机训练过程与基于“一对一”策略的多分类孪生支持向

量机类似,但其决策方式有其特殊的优缺点,因此将其也独立为一类.分析和总结了这 6 种类型的多分类孪生支持向

量机的算法思想、理论基础.此外,还通过实验对比了分类性能.为各种多分类孪生支持向量机之间建立了联系比较,

使得初学者能够快速理解不同多分类孪生支持向量机之间的本质区别,也对实际应用中选取合适的多分类孪生支

持向量机起到一定的指导作用.

关键词: 多分类;孪生支持向量机;多生支持向量机;支持向量机

中图法分类号: TP18

中文引用格式: 丁世飞,张健,张谢锴,安悦瑄.多分类孪生支持向量机研究进展.软件学报,2018,29(1):89 108 . http://www.jos.

org.cn/1000-9825/5319.htm

英文引用格式: Ding SF, Zhang J, Zhang XK, An YX. Survey on multi class twin support vector machines. Ruan Jian Xue Bao/

Journal of Software, 2018,29(1):89108 (in Chinese). http://www.jos.org.cn/1000-9825/5319.ht m

Survey on Multi Class Twin Support Vector Machines

DING Shi- Fei

1,2

, ZHANG Jian

, ZHANG Xie-Kai

, AN Yue-Xuan

(School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116 , China)

(Key Laboratory of Intelligent Information Processsing, Institut e of Computing Technology, The Chinese Academy of Sciences, Beijing

100190, China)

Abstra ct : Twin support vector machines have drawn extensive attention for their simple model, high training speed and good

performance. The initial twin support vector machine is designed for binary classification. However, multi class classification problems

are also common in practice. In recent years, researchers have devoted themselves to the study of multi class twin support vector machines.

Various mulit class twin support vector machines have been proposed. The study of multi class twin support vector machines has made

 基金项目: 国家自然科学基金(61672522, 61379101); 国家重点基础研究发展计划(973)(2013CB329502)

Foundation item: National Natural Science Foundation of China (61672522, 61379101); National Key Basic Research Program of

China (973) (2013CB329502)

收稿时间: 2017-01-19; 修改时间: 2 017-02-25, 2017-04-16; 采用时间: 2 017-06-16; jo s 在线出版时间: 2017 -07-12

CNKI 网络优先出版: 2017-07-12 16:16:57, http://kns.cnki.net/kcms/d etail/11.2560.TP.20170712.1616.017.html

Journal of Software 软件学报 Vol.29, No.1, January 2018

great progress. This paper aims to review the develop ment of multi class twin support v ector machines, cl assify and analyze th em with the

respect to the basic theories and geometric meanings. According to the structures, the paper divides the machines into the following

groups: “one-versus-all” strategy based multi class twin support vector machines, “one-versus-one” strategy based multi class twin

support vector machines, binary tree based multi class twin support vector machines, “one-versus-one-versus-rest” strategy based multi

class twin support vector machines, and “all-versus-one” strategy based multi class twin support vector machines. Although the training

processes of direct acyclic graph based multi class twin support vector machines are much similar with that of “one-versus-one” based

approachs, the decision processes have their own characteristics and disadvantages, and therefore they are divided into a separate group.

This paper analyzes and summarizes the ideas and theories of different multi class twin support vector machines, and presents

experimental results to compare the performances. This review can make it easy for novices to understand the essential differences and

help to choose the suitable multi class t win support v ector machin e for a practical probl em.

Key words: multi classs classification; t win support vector machine; multiple birth support v ector machin e; support v ector machine

孪生支持向量机(twin support vector machine,简称 TWSVM)是在传统支持向量机(support vector machine,

简称 SVM)

[1,2]

的基础上发展而来的一种新型机器学习算法.为了解决二分类问题,TWSVM 为每一类样本构造

一个超平面,使每类样本尽可能离本类的超平面更近,而尽可能地远离另一类的超平面

[3]

.TWSVM 的两个超平

面通过求解两个二次规划问题(quadratic programming problems,简称 QPPs)得到,每个 QPP 的约束条件都只与

一类样本有关.TWSVM 不但保持了 SVM 的优点,而且训练速度比传统 SVM 要快 4 倍

[4]

.为了进一步提升

TWSVM 的性能,学者们已经提出了不少改进算法

[521]

,例如,Kumar 等人提出了 TWSVM 的最小二乘模型,称作

最小二乘孪生支持向量机(least squares twin su pport vector mac hine,简称 LSTSVM)

[5]

.LSTSVM 的训练过程中仅

需求解线性方程组,因此训练速度远快于 TWSVM.丁世飞等人根据样本点的位置为每个训练样本赋予不同的

重要性,以降低异常点对非平行超平面的影响,并使用基于 CHKS 函数的光滑算法快速求解二次规划问题,得到

了训练速度更快、鲁棒性更强的加权光滑 CHKS TWSVM

[11]

.此外,TWSVM 的应用研究也已经取得了不少成

果

[2225]

TWSVM 最初是为解决二分类问题而提出来的,不能直接用于多分类问题.现实问题中,更加普遍的是多分

类问题,因此,多分类孪生支持向量机(multi class twin support vector machines,简称 MTWSVMs) 的研究具有现实

意义

[26]

.除了将 TWSVM 与多分类支持向量机中常用策略结合得到相应的 MTWSVMs 外,为了进一步提升分类

能力和训练速度,学者们还提出了不少新颖的改进算法.目前,MTWSVMs 的研究已经取得了比较丰富的成果,

但是针对 MTWSVMs 的相关综述性研究并不多,已有的综述性工作也没有给出全面的总结和分析.Tomar 和

Agarwal 仅对基于 LSTSVM 的多分类算法进行了比较

[26]

.Ding 等人在他们的 TWSVMs 综述中初步分析了偏二

叉树 MTWSV M 和 Boosting MTWSVM 算法.Tomar 等人介绍了 Twin KVC、多生支持向量机(multiple birth

support vector machine,简称 MBSVM) 、决策树 TWSVM、优化的有向无环图最小二乘孪生支持向量机和最小

二乘 Twin KSVC

[27]

,但没有对它们进行归类总结,也没有分析它们的基本思想.不同于已有工作,本文根据

MTWSV Ms 的子分类器的组织结构将它们分为基于“一对多”策略的 MTWSVMs、基于“一对一”策略的

MTWSV Ms、基于“一对一对余”策略的 MT W SV Ms、基于二叉树的 MTWSVMs、基于“多对一”策略的

MTWSV Ms. 虽然基于有向无环图(directed acyclic graph, 简称 DAG) 结构的 MTWS VMs 具有与“ 一对

一”MTWSVMs 类似的训练过程,但其决策过程比较特殊,因此也单独作为一类而加以分析.本文在分类基础上

对比各种 MT W S VMs 模型的同时,在各个类型的 MTWSV Ms 中又将改进模型与对应的原 MT W SV Ms 模型进

行对比.因此,本文从多方面综合性地综述了 MTW SV Ms, 较已有工作更全面地总结了 MTWSVMs 的研究发展

状况.本文称文献[4]中最初的 TWSVM 为标准 TWSVM,TWSVMs 包括标准 TWSVM 以及所有 TWSVM 的改进

算法,MTWSVMs 是指基于 TWSVM 及其改进算法的所有多分类算法.

1 二分类孪生支持向量机简介

本节介绍 TWSVM 的数学模型.假设在 R

的空间中有 m 个训练样本,它们都有 n 个属性,其中有 m

个样本

属于正类,m

个样本属于负类,它们分别用矩阵 A 和矩阵 B 来表示.矩阵 A 的每行各代表一个属于正类的样本点.

of 20

免费下载

软件学报计算机技术

关注

评论