«上一篇
文章快速检索     高级检索
下一篇»
  智能系统学报  2019, Vol. 14 Issue (6): 1121-1126  DOI: 10.11992/tis.201905025
0

引用本文  

李景灿, 丁世飞. 基于人工鱼群算法的孪生支持向量机[J]. 智能系统学报, 2019, 14(6): 1121-1126. DOI: 10.11992/tis.201905025.
LI Jingcan, DING Shifei. Twin support vector machine based on artificial fish swarm algorithm[J]. CAAI Transactions on Intelligent Systems, 2019, 14(6): 1121-1126. DOI: 10.11992/tis.201905025.

基金项目

国家自然科学基金项目(61672522,61379101).

通信作者

丁世飞. E-mail:dingsf@cumt.edu.cn

作者简介

李景灿,男,1995年生,硕士研究生,主要研究方向为支持向量机和机器学习;
丁世飞,男,1963年生,教授,博士生导师,主要研究方向为人工智能、机器学习、模式识别、数据挖掘。主持国家重点基础研究计划(973计划)课题1项、国家自然科学基金面上项目2项。出版专著4部,发表学术论文200余篇

文章历史

收稿日期:2019-05-13
网络出版日期:2019-07-22
基于人工鱼群算法的孪生支持向量机
李景灿 1,2, 丁世飞 1,2     
1. 中国矿业大学 计算机科学与技术学院 江苏 徐州 221116;
2. 矿山数字化教育部工程研究中心,江苏 徐州 221116
摘要:孪生支持向量机(twin support vector machine, TWSVM)是在支持向量机的基础上产生的机器学习算法,具有训练速度快、分类性能优越等优点。但是孪生支持向量机无法很好地处理参数选择问题,不合适的参数会降低分类能力。人工鱼群算法(artificial fish swarm algorithm, AFSA)是一种群智能优化算法,具有较强的全局寻优能力和并行处理能力。本文将孪生支持向量机与人工鱼群算法结合,来解决孪生支持向量机的参数选择问题。首先将孪生支持向量机的参数作为人工鱼的位置信息,同时将分类准确率作为目标函数,然后通过人工鱼的觅食、聚群、追尾和随机行为来更新位置和最优解,最后迭代结束时得到最优参数和最优分类准确率。该算法在训练过程中自动确定孪生支持向量机的参数,避免了参数选择的盲目性,提高了孪生支持向量机的分类性能。
关键词孪生支持向量机    人工鱼群算法    模式分类    参数优化    准确率    群体智能    二次规划    并行处理    全局优化    
Twin support vector machine based on artificial fish swarm algorithm
LI Jingcan 1,2, DING Shifei 1,2     
1. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China;
2. Mine Digitization Engineering Research Center of Minstry of Education of the People's Republic of China, Xuzhou 221116, China
Abstract: Twin support vector machine (TWSVM) is a machine learning algorithm based on the support vector machine. It has the advantages of fast training speed and superior classification performance. However, the algorithm cannot handle the parameter selection problem effectively, and the inappropriate parameters will reduce the classification ability. The artificial fish swarm algorithm (AFSA) is a group intelligent optimization algorithm with a strong global optimization ability and parallel processing capability. In this paper, TWSVM and AFSA are combined to solve the parameter selection problem of the TWSVM. First, the parameters of the support vector machine are taken as the position information of the artificial fish, and the classification accuracy is taken as the objective function. Then, the position and the optimal solution are updated by the artificial fish’s preying, swarming, following, and random behavior. At the end of the iterations, the optimal parameters and the optimal classification accuracy are obtained. The algorithm automatically determines the parameters of the TWSVM in the training process, avoiding the blindness of parameter selection, and improves the classification performance of the TWSVM
Key words: twin support vector machine    artificial fish swarm algorithm    pattern classification    parameter optimization    accuracy    swarm intelligence    quadratic programming    parallel processing    global optimization    

支持向量机(support vector machine, SVM) [1]是一种基于统计学习理论的VC维和结构风险最小化原理的机器学习方法,由Cortes和Vapik[2]于1995年提出。其在解决小样本、非线性和高维模式识别问题中有许多优势,目前已被应用到很多领域,例如文本分类、时间序列分析、模式识别和图像处理等[3-7]。为了提高支持向量机的性能,学者们提出了许多改进算法。例如最小二乘支持向量机[8]、近似支持向量机[9]和基于广义特征值的近似支持向量机[10]等。2007年,基于广义特征值近似支持向量机的思想,Jayadeva等[11]提出了孪生支持向量机。和SVM不同,TWSVM是生成两个非平行的分类超平面,使得其中一个超平面尽量接近一类样本,并且尽可能的远离另一类样本。TWSVM[12-13]将单个大型二次规划问题转化为两个较小的二次规划问题,明显缩短了运行时间。虽然孪生支持向量机的发展时间较短,但由于其坚实的理论基础和出色的性能表现,已经成为机器学习领域的一个研究热点。许多学者对TWSVM的研究做出了贡献,并取得了很多成果。例如光滑孪生支持向量机[14]、最小二乘孪生支持向量机[15-17]、模糊孪生支持向量机[18]和投影孪生支持向量机[19-20]等。

尽管近年来对TWSVM的研究在算法改进及其应用方面取得了很大的进展,但是仍有不足之处,其中之一就是TWSVM无法很好地处理参数选择问题。参数对分类结果有很大的影响,一个好的参数将直接提升TWSVM的性能。网格搜索[21]是最普遍的参数选择方法,但是这种方法很耗时。Ding等[22-23]采用粒子群算法和量子粒子群算法对TWSVM的参数进行优化。Zhai等[24]将粒子群算法与局部搜索算法结合,提出了一种混合粒子群算法来优化小波孪生支持向量机的参数。随后,Sartakhti等[25]将最小二乘孪生支持向量机与模拟退火算法结合来提高分类准确率。

人工鱼群算法(artificial fish swarm algorithm, AFSA)[26]是一种基于动物行为的群体智能优化算法。该算法具有收敛速度快、灵活性强、容错性强、准确率高等优点。本文将人工鱼群算法与孪生支持向量机进行结合,以分类准确率作为适应度值,来对惩罚参数和核参数进行优化,提高算法的有效性。

1 相关理论 1.1 孪生支持向量机

假设在n维实空间Rn中有m个训练样本,其中属于+1类的有m1个,属于−1类的有m2个。令 ${{A}} \in {{\rm{R}}^{{m_1} \times n}}$ 表示+1类的训练样本, ${{B}} \in {{\rm{R}}^{{m_2} \times n}}$ 表示−1类的训练样本。TWSVM的训练过程是要在Rn中找到两个非平行的超平面:

$K({{{x}}^{\rm{T}}},{{{C}}^{\rm{T}}}){{w}}{}_1 + {b_1} = 0,{\rm{ }}K({{{x}}^{\rm{T}}},{{{C}}^{\rm{T}}}){{w}}{}_2 + {b_2}{\rm{ = 0}}$ (1)

其中K为核函数, C=[A;B]代表所有的训练样本, ${{{w}}_i}(i = 1,2)$ 是分类超平面的法向量, ${b_i}(i = 1,2)$ 为偏置。

通过求解下面两个二次规划问题可以得到这两个超平面:

$\begin{gathered} \mathop {\min }\limits_{{{w}_1},{{b}_1},{{\xi }_1}} \frac{1}{2}{\left\| {K({A},{{C}^{\rm{T}}}){{w}_1} + {{e}_1}{b_1}} \right\|^2} + {c_1}{e}_2^{\rm{T}}{{\xi }_2} \\ {\rm{s}}{\rm{.t}}{\rm{.\;- (}}K({B},{{C}^{\rm{T}}}){{w}_1} + {{e}_2}{b_1}) \geqslant {{e}_2} - {{\xi }_2},{{\xi }_2} \geqslant 0 \\ \end{gathered} $ (2)
$\begin{gathered} \mathop {\min }\limits_{{{w}_2},{{b}_2},{{\xi }_2}} \frac{1}{2}{\left\| {K({B},{{C}^{\rm{T}}}){{w}_2} + {{e}_2}{b_2}} \right\|^2} + {c_2}{e}_1^{\rm{T}}{{\xi }_1} \\ {\rm{s}}{\rm{.t}}{\rm{. \;(}}K({A},{{C}^{\rm{T}}}){{w}_2} + {{e}_1}{b_2}) \geqslant {{e}_1} - {{\xi }_1},{{\xi }_1} \geqslant 0 \\ \end{gathered} $ (3)

其中c1c2是惩罚参数,e1e2是两个全1列向量, ${{ \xi} _1}$ ${{ \xi} _2}$ 是松弛变量。

测试样本离哪个超平面近,就属于哪一类别,若

$K({{x}^{\rm{T}}},{{C}^{\rm{T}}}){w}{}_r + {b_r} = \mathop {\min }\limits_{i = 1,2} \left| {K({{x}^{\rm{T}}},{{C}^{\rm{T}}}){w}{}_i + {b_i}} \right|$ (4)

x属于第r类,其中 $r \in \left\{ {1,2} \