【人工智能】基于能量的结构化最小二乘孪生支持向量机

第15卷第5期 智能系统学报 Vol.15 No.5 2020年9月 CAAI Transactions on Intelligent Systems Sep.2020 D0:10.11992/tis.201906030 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20200320.0956.006.html 基于能量的结构化最小二乘孪生支持向量机 史颂辉2，丁世飞2 (1.中国矿业大学计算机科学与技术学院，江苏徐州221116,2.矿山数字化教育部工程研究中心，江苏徐州 221116) 摘要：针对最小二乘李生支持向量机对噪声和离群值非常敏感的问题，本文提出了一种基于能量的结构化最 小二乘孪生支持向量机。首先对每个类进行聚类分析，然后计算类中各个簇的协方差矩阵并将其引入到目标 函数中。其次，为了降低噪声和离群值对算法的影响，本文为每个超平面引入能量因子，在最小二乘的基础上 将等式约束转换为基于能量的形式。最后采用“多对一”的策略将提出的算法用于处理多分类问题。研究结果 表明：本文提出的基于能量的结构化最小二乘李生支持向量机具有良好的分类性能。 关键词：孪生支持向量机；最小二乘；结构信息；聚类；协方差矩阵；能量因子；“多对一”策略：多分类问题 中图分类号：TP391文献标志码：A 文章编号：1673-4785(2020)05-1013-07 中文引用格式：史颂辉，丁世飞.基于能量的结构化最小二乘李生支持向量机J.智能系统学报，2020,15(5)：1013-1019. 英文引用格式：SHI Songhui,DING Shifei..Energy-based structural least square twin support vector machine[J]..CAAI transac- tions on intelligent systems,2020,15(5):1013-1019. Energy-based structural least square twin support vector machine SHI Songhui2,DING Shifei (1.School of Computer Science and Technology,China University of Mining and Technology,Xuzhou 221116,China;2.Engineer- ing Research Center (Ministry of Education)of Mine Digitization,Xuzhou 221116,China) Abstract:The least square twin support vector machine(TWSVM)is very sensitive to noise and outlier.To solve this problem,we propose an energy-based structured least square TWSVM(ES-LSTWSVM).First,we perform a cluster analysis on each class,then compute the covariance matrix of each cluster in the classes,and introduce it into the object- ive function.To reduce the influence of noises and outliers on the algorithm,an energy factor is introduced to each hy- perplane,and the equality constraint is converted into an energy-based form on the basis of least squares.Finally,we ad- opt the"all-versus-one"strategy to apply the proposed algorithm in solving a multi-class classification problem.The ex- perimental results show that ES-LSTWSVM has good classification performance. Keywords:twin support vector machine;least square;structural information;cluster;covariance matrix;en- ergy factor;"all-versus-one"strategy;multi-class classification problem 支持向量机(support vector machine, 2007年，Jayadeva等提出了孪生支持向量 SVM)W是由Vapnik提出的基于结构风险最小化 机(twin support vector machine,TWSVM),它为每 原理的二分类分类器。其基本思想是在2个平行 一类构造一个超平面，使每一类样本尽可能距离 支持超平面之间找到最大化边界。与此同时，对 本类的超平面近，而尽可能地远离另一类的超平 于非线性分类问题，内核技巧也可以应用到 面。TWSVM的2个非平行的超平面是通过求解 SVM中。然而，SVM的计算复杂度却很高。 2个二次规划问题(quadratic programming prob- 收稿日期：2019-06-18.网络出版日期：2020-03-20 lems,QPPs)得到的，每个QPP的约束条件都只与 基金项目：国家自然科学基金项目(61672522,61976216， 61379101). 一类样本有关。TWSVM不但保持了SVM的优 通信作者：丁世飞.E-mail:dingsf@cumt.edu.cn 点，而且训练速度比传统SVM要快4倍。为了进

DOI: 10.11992/tis.201906030 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20200320.0956.006.html 基于能量的结构化最小二乘孪生支持向量机 史颂辉1,2，丁世飞1,2 （1. 中国矿业大学 计算机科学与技术学院，江苏 徐州 221116; 2. 矿山数字化教育部工程研究中心，江苏 徐州 221116） 摘 要：针对最小二乘孪生支持向量机对噪声和离群值非常敏感的问题，本文提出了一种基于能量的结构化最 小二乘孪生支持向量机。首先对每个类进行聚类分析，然后计算类中各个簇的协方差矩阵并将其引入到目标 函数中。其次，为了降低噪声和离群值对算法的影响，本文为每个超平面引入能量因子，在最小二乘的基础上 将等式约束转换为基于能量的形式。最后采用“多对一”的策略将提出的算法用于处理多分类问题。研究结果 表明：本文提出的基于能量的结构化最小二乘孪生支持向量机具有良好的分类性能。 关键词：孪生支持向量机；最小二乘；结构信息；聚类；协方差矩阵；能量因子；“多对一”策略；多分类问题 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2020)05−1013−07 中文引用格式：史颂辉, 丁世飞. 基于能量的结构化最小二乘孪生支持向量机 [J]. 智能系统学报, 2020, 15(5): 1013–1019. 英文引用格式：SHI Songhui, DING Shifei. Energy-based structural least square twin support vector machine[J]. CAAI transac￾tions on intelligent systems, 2020, 15(5): 1013–1019. Energy-based structural least square twin support vector machine SHI Songhui1,2 ，DING Shifei1,2 (1. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China; 2. Engineer￾ing Research Center (Ministry of Education) of Mine Digitization, Xuzhou 221116, China) Abstract: The least square twin support vector machine (TWSVM) is very sensitive to noise and outlier. To solve this problem, we propose an energy-based structured least square TWSVM (ES-LSTWSVM). First, we perform a cluster analysis on each class, then compute the covariance matrix of each cluster in the classes, and introduce it into the object￾ive function. To reduce the influence of noises and outliers on the algorithm, an energy factor is introduced to each hy￾perplane, and the equality constraint is converted into an energy-based form on the basis of least squares. Finally, we ad￾opt the “all-versus-one” strategy to apply the proposed algorithm in solving a multi-class classification problem. The ex￾perimental results show that ES-LSTWSVM has good classification performance. Keywords: twin support vector machine; least square; structural information; cluster; covariance matrix; en￾ergy factor; “all-versus-one” strategy; multi-class classification problem 支持向量 机 (support vector machine, SVM)[1] 是由 Vapnik 提出的基于结构风险最小化 原理的二分类分类器。其基本思想是在 2 个平行 支持超平面之间找到最大化边界。与此同时，对 于非线性分类问题，内核技巧也可以应用 到 SVM 中。然而，SVM 的计算复杂度却很高。 2007 年，Jayadeva 等 [2] 提出了孪生支持向量 机 (twin support vector machine, TWSVM)，它为每 一类构造一个超平面，使每一类样本尽可能距离 本类的超平面近，而尽可能地远离另一类的超平 面。TWSVM 的 2 个非平行的超平面是通过求解 2 个二次规划问题 (quadratic programming prob￾lems,QPPs) 得到的，每个 QPP 的约束条件都只与 一类样本有关。TWSVM 不但保持了 SVM 的优 点，而且训练速度比传统 SVM 要快 4 倍。为了进 收稿日期：2019−06−18. 网络出版日期：2020−03−20. 基金项目：国家自然科学基金项 目 (61672522， 61976216， 61379101). 通信作者：丁世飞. E-mail：dingsf@cumt.edu.cn. 第 15 卷第 5 期 智 能 系 统 学 报 Vol.15 No.5 2020 年 9 月 CAAI Transactions on Intelligent Systems Sep. 2020

·1014· 智能系统学报 第15卷 一步提升TWSVM的性能，学者们已经提出了不 twin support vector machine,S-LSTWSVM)）进行改 少改进算法，例如：孪生有界支持向量机(twin 进，提出了一种基于能量的结构最小二乘孪生支 bounded support vector machine,.TBSVM)、最小二 持向量机(energy-based structural least square twin 乘孪生支持向量机(least square twin support vec-- support vector machin,ES-LSTWSVM)。为每个超 tor machine,LSTWSVM)、非平行支持向量机s例 平面引入能量因子，将等式约束条件转换为基于 (nonparallel support vector machine,NPSVM)。具体 能量的形式。最后采用“多对一”的策略1解决 来说，LSTWSVM使用平方损失函数将TWS 多分类问题。 VM中的凸二次规划问题转化为解线性方程组， 本文的主要贡献如下： 从而实现极快的训练速度。但是，LSTWSVM对 1)提出了一种基于能量的结构化最小二乘孪 噪声很敏感，因为它要求超平面与其他类的点距 生支持向量机； 离恰好为1。近些年来出现了许多改进的算法。 2)采用“多对一”的策略将提出的算法扩展到 Nasiri等6I提出了一种基于能量的LSTWSVM 多分类问题中： (energy-based least square twin support vector ma- 3)选择几种有代表性的相关算法进行对比实 chine,.ELS-TWSVM)模型，该模型为每一类引入 验，在UCI数据集上的实验结果表明提出的算法 一个能量因子以减少噪声的影响。马跃峰等)提 具有良好的分类性能。 出了一种基于全局代表点的快速最小二乘支持向 量机稀疏化算法(global--representation-based sparse 1相关工作 least squares support vector machine,GRS-LSSVM), 本节介绍TWSVM和S-TWSVM的数学模 利用数据全局代表性指标，在全部数据中，一次 型。假设在R”空间中训练数据集定义为T= 性地选择出其中最具有全局代表性的数据并构成 {(,y)i=1,2,…,m,其中：是输入，∈(+1，-1 稀疏化后的支持向量集，然后在此基础上求解决 是对应的输出。它们共有m个训练样本，每个样 策超平面。吴青等提出了一种最小二乘大间隔 本有n个属性，其中有m个样本属于正类，m个 孪生支持向量机(least squares large margin twin 样本属于负类，分别用矩阵A、B来表示。 support vector machine,LSLMTSVM),该方法在 1.1 TWSVM TWSVM的目标函数中引入间隔均值和间隔方差， TWSVM通过训练数据集寻找2个不平行的 通过优化间隔分布来获得具有更强泛化能力的 分离超平面： 模型。 xw1+b1=0,xw2+b2=0 实际上，在大多数分类问题中，不同的类可能 它们一般通过求解下面2个二次规划问题来 有不同的结构信息。然而，传统的SVM和TWS 得到： VM都没有完全应用类中样本的分布信息。最流 行的方法之一是基于假设的聚类算法四，利用聚 2(Aw+eb)(Aw+eb)+ce- S.t. (Bw1+e2b1)≥e2-52,52≥0 类算法提取类中的结构信息。例如，结构化最大 边缘机(structured large margin machine,SLMM)o min (Bw:+e:b2(Bw2+e:b2)+cze!E 2,1 最小最大概率机(minimax probability machine,. s.t.(Aw2+e1b2)≥e1-51,51≥0 MPM)u和最大最小边缘机(maxi-min margin ma- 式中：c、c2>0是2个惩罚参数；e1、e2是元素全为 chine,Ma。但是，这些方法的计算复杂度高于 1的列向量；5、52是松弛变量。 经典的SVM。因此，Xue等]提出了一种结构正 TWSVM通过如下的决策函数判定新样本的 则化支持向量机(structural regularized SVM,SRS- 类别标签： VM)。此方法将集群粒度导人到获得数据结构的 Label(x)=arg minxw+b -12 正则化项。遵循SLMM和SRSVM的策略，Qi 1.2 S-TWSVM 等提出了一种新的结构化的TWSVM(structural 首先，S-TWSVM通过“沃氏链接”(ward's twin support vector machine,S-TWSVM)。与SRS- linkage)聚类算法i6提取类内的结构信息。然后 VM类似，S-TWSVM使用聚类算法提取每个类的 它使用2个非平行超平面来判定新数据的类别， 结构信息，并将得到的结构信息引入到S-TWS- 其中每个超平面尽可能离本类数据点近，并且在 VM模型中。 目标函数中只考虑该类的结构信息，而约束条件 在本文中，受文献[6]的启发，首先对结构化 规定该超平面要离其他类数据点至少距离为1个 的最小二乘孪生支持向量机(structural least square 单位。假设通过聚类之后正类中有C个簇，负类

一步提升 TWSVM 的性能，学者们已经提出了不 少改进算法，例如：孪生有界支持向量机[3] (twin bounded support vector machine, TBSVM)、最小二 乘孪生支持向量机[4] (least square twin support vec￾tor machine, LSTWSVM)、非平行支持向量机[5] (nonparallel support vector machine，NPSVM)。具体 来说，LSTWSVM 使用平方损失函数将 TWS￾VM 中的凸二次规划问题转化为解线性方程组， 从而实现极快的训练速度。但是，LSTWSVM 对 噪声很敏感，因为它要求超平面与其他类的点距 离恰好为 1。近些年来出现了许多改进的算法。 Nasiri 等 [6] 提出了一种基于能量的 LSTWSVM (energy-based least square twin support vector ma￾chine, ELS-TWSVM) 模型，该模型为每一类引入 一个能量因子以减少噪声的影响。马跃峰等[7] 提 出了一种基于全局代表点的快速最小二乘支持向 量机稀疏化算法 (global-representation-based sparse least squares support vector machine, GRS-LSSVM)， 利用数据全局代表性指标，在全部数据中，一次 性地选择出其中最具有全局代表性的数据并构成 稀疏化后的支持向量集，然后在此基础上求解决 策超平面。吴青等[8] 提出了一种最小二乘大间隔 孪生支持向量机 (least squares large margin twin support vector machine, LSLMTSVM)，该方法在 TWSVM 的目标函数中引入间隔均值和间隔方差， 通过优化间隔分布来获得具有更强泛化能力的 模型。 实际上，在大多数分类问题中，不同的类可能 有不同的结构信息。然而，传统的 SVM 和 TWS￾VM 都没有完全应用类中样本的分布信息。最流 行的方法之一是基于假设的聚类算法[9] ，利用聚 类算法提取类中的结构信息。例如，结构化最大 边缘机 (structured large margin machine, SLMM)[10] 、 最小最大概率机 (minimax probability machine， MPM)[11] 和最大最小边缘机 (maxi-min margin ma￾chine，M 4 ) [12]。但是，这些方法的计算复杂度高于 经典的 SVM。因此，Xue 等 [13] 提出了一种结构正 则化支持向量机 (structural regularized SVM，SRS￾VM)。此方法将集群粒度导入到获得数据结构的 正则化项。遵循 SLMM 和 SRSVM 的策略，Qi 等 [14] 提出了一种新的结构化的 TWSVM(structural twin support vector machine, S-TWSVM)。与 SRS￾VM 类似，S-TWSVM 使用聚类算法提取每个类的 结构信息，并将得到的结构信息引入到 S-TWS￾VM 模型中。 在本文中，受文献 [6] 的启发，首先对结构化 的最小二乘孪生支持向量机 (structural least square twin support vector machine, S-LSTWSVM) 进行改 进，提出了一种基于能量的结构最小二乘孪生支 持向量机 (energy-based structural least square twin support vector machin, ES-LSTWSVM)。为每个超 平面引入能量因子，将等式约束条件转换为基于 能量的形式。最后采用“多对一”的策略[15] 解决 多分类问题。 本文的主要贡献如下： 1) 提出了一种基于能量的结构化最小二乘孪 生支持向量机； 2) 采用“多对一”的策略将提出的算法扩展到 多分类问题中； 3) 选择几种有代表性的相关算法进行对比实 验，在 UCI 数据集上的实验结果表明提出的算法 具有良好的分类性能。 1 相关工作 R n T = {(xi , yi)|i = 1,2,··· ,m} xi yi ∈ {+1,−1} m n m1 m2 A B 本节介绍 TWSVM 和 S-TWSVM 的数学模 型。假设在 空间中训练数据集定义为 ，其中 是输入， 是对应的输出。它们共有 个训练样本，每个样 本有 个属性，其中有 个样本属于正类， 个 样本属于负类，分别用矩阵 、 来表示。 1.1 TWSVM TWSVM 通过训练数据集寻找 2 个不平行的 分离超平面： x Tw1+b1 = 0, x Tw2+b2 = 0 它们一般通过求解下面 2 个二次规划问题来 得到： min w1 ,b1 ,ξ2 1 2 (Aw1 +e1b1) T (Aw1 +e1b1)+c1e T 1 ξ2− s.t. (Bw1 +e2b1) ⩾ e2 −ξ2, ξ2 ⩾ 0 min w2,b2 ,ξ1 1 2 (Bw2 +e2b2) T (Bw2 +e2b2)+c2e T 1 ξ1 s.t. (Aw2 +e1b2) ⩾ e1 −ξ1, ξ1 ⩾ 0 e1 e2 ξ1 ξ2 式中：c1、c2>0 是 2 个惩罚参数； 、 是元素全为 1 的列向量； 、 是松弛变量。 TWSVM 通过如下的决策函数判定新样本的 类别标签： Label(x) = argmin l=1,2   x Twl +bl    1.2 S-TWSVM CP 首先，S-TWSVM 通过“沃氏链接”(ward’s linkage) 聚类算法[16] 提取类内的结构信息。然后 它使用 2 个非平行超平面来判定新数据的类别， 其中每个超平面尽可能离本类数据点近，并且在 目标函数中只考虑该类的结构信息，而约束条件 规定该超平面要离其他类数据点至少距离为 1 个 单位。假设通过聚类之后正类中有 个簇，负类 ·1014· 智 能 系 统 学 报 第 15 卷

第5期 史颂辉，等：基于能量的结构化最小二乘孪生支持向量机 ·1015· 中有Cw个簇。那么S-TWSVM的优化问题可以 min 表述为 -b-月 Bw+ear+号0gt w6+)+∑n (2) 如 2 lAw,+eb+cies+ca()+ s.t.Aw-+e,b+n=E, 9w∑0. 1 式中：c(i=1,2,…,6)是惩罚参数；5、7是松弛变 + s.L-(Bw+e_b)+5≥e-,≥0 量；E,和E是超平面的能量因子：∑， min ++∑：∑=∑%++∑：∑，和 b_月 2 Bw-+eb-+caecs(l)+ 1 w∑n 分别是对应于2个类中的第i个簇和第广个 s.t.(Aw-+e,b)+n≥e+,7≥0 簇的协方差矩阵，i=1,2,…,Cp,j=1,2,…,Cn0 式中：c≥0(i=1,2…,6)是惩罚参数；专、刀是松弛 将等式约束条件代入目标函数式(1)中得到： 变量：，、。.是元素全为1的列向量：∑ Aw.+e.b.lP+SlBw.+e.b.+E+ 1 政 ∑++∑∑=∑、+∑∑和∑ 号0，后+的+∑ C3 2 是2类中的每一个簇的相应协方差矩阵，其中 (3) i=1,2,…,Cp,j=1,2,…,Cwo 分别对式(3)中w+和b求导，并且由 新的数据点被分配给正类还是负类取决于得 KKT条件得： 到的2个超平面wx+b+=0和wx+b.=0中它 AT(Aw.+e.b.)+cBT(Bw.+e_b.+E_)+ 距离哪一个超平面更近，即 cw,+c∑.w,=0 (4) Label(x)argminwix+b..wIx+b_ e:(Aw:+e:b+)+cie(Bw:+e_b.+E_)+c2b.=0 (5) 将式(4)、（⑤）整理成矩阵的形式为 2 ES-LSTWSVM 在本节中，提出了一种基于能量的结构化孪 生支持向量机(ES-LSTWSVM)。该算法主要分 gle+o =0 为2步：1)用某种聚类方法提取类内的结构信息； 2)最小化每个类中各个簇之间的紧密度并将其嵌 入到目标函数中。此外，利用核技巧使模型能够 解决非线性可分问题。在下面的小节中，将具体 讨论这些步骤。 使P=[Ae,],2=[Be.】,并且 2.1线性ES-LSTWSVM 0 。则解可表示为 有很多聚类方法可被用于提取类内的结构信 W+ 息，例如：k均值算法7、模糊聚类和密度聚类82刘。 z1= b+】 =-c1(Pp+c0'0+cI+c∑，)'gE. 使用拐点图2来确定最佳聚类数目。聚类之后， 同理，式(2)可表示为 通过计算类中各个簇的协方差矩阵将结构信息引 w- 入到优化问题中。因此，聚类之后的簇应该是紧 3= b =c(OTQ+caPTP+csI+c>PE. 凑的并且是球形的。鉴于此，采用Ward's link- 是适当维数的单位 age聚类算法，这是一种层次聚类方法，为协方差 矩阵的计算提供了基础。 矩阵。 假设从正类和负类中分别得到了C。和Cm个 ES-LSTWSVM通过如下的决策函数判定新 簇，即A=PU...UP;U...UPc,B=N1UUNU 样本的类别标签： UWc.。对于线性可分的二分类问题，ES-LSTWS Label(x)= (xw.+b.x"w-+b- w_‖ VM模型可表示为 hw,l 1 2.2非线性ES-LSTWSVM min Aw,+e.bP+号55+ 对于非线性分类问题，利用核技巧进行处 el6+的)+号∑m C2 (1) 理。首先将原始特征空间中的数据映射到希尔伯 -(Bwt+e_b)+5=E. 特空间中：Φ：Rm→H。类似于线性情形，决策函

中有 CN 个簇。那么 S-TWSVM 的优化问题可以 表述为 min w+,b+,ξ 1 2 ∥Aw+ +e+b+∥ 2 2 +c1e T − ξ + 1 2 c2(∥w+∥ 2 2 +b 2 + )+ 1 2 c3w T + ∑ + w+ s.t. −(Bw+ +e−b+)+ξ ⩾ e−, ξ ⩾ 0 min w−,b−,η 1 2 ∥Bw− +e−b−∥ 2 2 +c4e T +η+ 1 2 c5(∥w−∥ 2 2 +b 2 − )+ 1 2 c6w T − ∑ − w− s.t. (Aw− +e+b−)+η ⩾ e+,η ⩾ 0 ci ⩾ 0(i = 1,2,··· ,6) ξ η e+ e− ∑ + = ∑ P1 +···+ ∑ PCP ∑ − = ∑ N1 +···+ ∑ NCN ∑ Pi ∑ Nj i = 1,2,··· ,CP, j = 1,2,··· ,CN 式中： 是惩罚参数； 、 是松弛 变量； 、 是元素全 为 1 的列向量； ； ； 和 是 2 类中的每一个簇的相应协方差矩阵，其中， 。 w T + x+b+ = 0 w T − x+b− = 0 新的数据点被分配给正类还是负类取决于得 到的 2 个超平面 和 中它 距离哪一个超平面更近，即 Label(x) = argmin +,− {  w T + x+b+   ,   w T − x+b−    } 2 ES-LSTWSVM 在本节中，提出了一种基于能量的结构化孪 生支持向量机 (ES-LSTWSVM)。该算法主要分 为 2 步：1) 用某种聚类方法提取类内的结构信息; 2) 最小化每个类中各个簇之间的紧密度并将其嵌 入到目标函数中。此外，利用核技巧使模型能够 解决非线性可分问题。在下面的小节中，将具体 讨论这些步骤。 2.1 线性 ES-LSTWSVM 有很多聚类方法可被用于提取类内的结构信 息，例如：k 均值算法[17] 、模糊聚类和密度聚类[18-21]。 使用拐点图[22] 来确定最佳聚类数目。聚类之后， 通过计算类中各个簇的协方差矩阵将结构信息引 入到优化问题中。因此，聚类之后的簇应该是紧 凑的并且是球形的。鉴于此，采用 Ward’s link￾age 聚类算法，这是一种层次聚类方法，为协方差 矩阵的计算提供了基础。 Cp Cn A = P1 ∪ ··· ∪ Pi ∪ ··· ∪ PCp B = N1 ∪ ··· ∪Ni ∪ ··· ∪NCn 假设从正类和负类中分别得到了 和 个 簇，即 ， 。对于线性可分的二分类问题，ES-LSTWS￾VM 模型可表示为 min w+,b+,ξ 1 2 ∥Aw+ +e+b+∥ 2 + c1 2 ξ T ξ+ c2 2 (∥w+∥ 2 2 +b 2 + )+ c3 2 w T + ∑ + w+ s.t. −(Bw+ +e−b+) +ξ = E− (1) min w−,b−,η 1 2 ∥Bw− +e−b−∥ 2 + c4 2 η Tη+ c5 2 (∥w−∥ 2 2 +b 2 − )+ c6 2 w T − ∑ − w− s.t. Aw− +e+b− +η = E+ (2) ci(i = 1,2,··· ,6) ξ η E+ E− ∑ + = ∑ P1 +···+ ∑ PCP ∑ − = ∑ N1 +···+ ∑ NCN ∑ ∑ Pi Nj i = 1,2,··· ,CP, j = 1,2,··· ,Cn 式中： 是惩罚参数； 、 是松弛变 量 ； 和 是超平面的能量因子； ； ； 和 分别是对应于 2 个类中的第 i 个簇和第 j 个 簇的协方差矩阵， 。 将等式约束条件代入目标函数式 (1) 中得到： min w+,b+ 1 2 ∥Aw+ +e+b+∥ 2 + c1 2 ∥Bw+ +e−b+ + E−∥ 2+ c2 2 (∥w+∥ 2 2 +b 2 + )+ c3 2 w T + ∑ + w+ (3) 分别对 式 ( 3 ) 中 w+ 和 b+ 求导，并且 由 KKT 条件得： A T (Aw+ +e+b+)+c1B T (Bw+ +e−b+ + E−)+ c2w+ +c3 ∑ + w+ = 0 (4) e T + (Aw+ +e+b+)+c1e T − (Bw+ +e−b+ + E−)+c2b+ = 0 (5) 将式 (4)、(5) 整理成矩阵的形式为 [ A TA AT e+ e T +A eT + e+ ] [ w+ b+ ] +c1 [ B TB B T e− e T −B eT − e− ] [ w+ b+ ] + c1 [ B T e T − ] E− +c2 [ w+ b+ ] +c3   ∑ + w+ 0   = 0 [ A T e T + ] [ A e+ ] [ w+ b+ ] +c1 [ B T e T − ] [ B e− ] [ w+ b+ ] + c2 [ w+ b+ ] +c3   ∑ + w+ 0   = −c1 [ B T e T − ] E− P = [ A e+ ] Q = [ B e− ] ∑ 1 =   ∑ + 0 0 0   使 ， ，并且 。则解可表示为 z1 = [ w+ b+ ] = −c1(P T P+c1Q TQ+c2I +c3 ∑ 1 ) −1Q TE− 同理，式 (2) 可表示为 z2 = [ w− b− ] = c4(Q TQ+c4P T P+c5I +c6 ∑ 2 ) −1P TE+ ∑ 2 =   ∑ − 0 0 0   式中：  ； I 是适当维数的单位 矩阵。 ES-LSTWSVM 通过如下的决策函数判定新 样本的类别标签： Label(x) =      x Tw+ +b+    ∥w+∥ ,   x Tw− +b−    ∥w−∥    2.2 非线性 ES-LSTWSVM Φ : R m → H 对于非线性分类问题，利用核技巧进行处 理。首先将原始特征空间中的数据映射到希尔伯 特空间中： 。类似于线性情形，决策函 第 5 期 史颂辉，等：基于能量的结构化最小二乘孪生支持向量机 ·1015·

·1016· 智能系统学报 第15卷 数可表示为f4(x)=(w,(x)+b+和f(x)=(w.中 孪生支持向量机(I-v-r LSTWSVM)、改进的最小 (x))+b-o 二乘孪生多分类支持向量(improvements on 由希尔伯特空间理论21知： least squares twin multi-class classification support m ",=∑)=ML vector machine,.LST-KSVC),多生最小二乘支持 1 向量机2sl(multiple birth least squares support vector w.=∑)，)=ML machine,.MBLSSVM)与本文算法进行比较。实验 结果为10折交叉验证的平均值。在非线性情形 ES-LSTWSVM构造如下2个基于核函数的 下，使用高斯核函数K(x,x)=exp(-:-x/2σ2)。 超平面： 3.1实验结果 K(x,M)A,+b,=0,K(x",MT)+b=0 在本节中，使用UCI数据集中的Iris、Wine 式中：M=ATBT:K(xx)=((x)(x》。 Vowel、Balance、Vehicle、Zoo和Segment。.这些数 在非线性情形下，ES-LSTWSVM可表示为 据集的特征如表1所示。 2Ka,MrL+e.b.f+号55+ 表1数据集的具体特征 Table 1 The detail features of the datasets 号L6+)+号(a0r∑L (6) 数据集 样本个数 特征维数 类别数 S.t. -(K(B,M)L+e_b+)+5=E. Iris 150 4 3 吗5lKB.ML+e.b+气rn+ Wine 178 3 Vowel 528 10 11 号L后+的)+号M∑ML (7 Balance 625 ? 3 s.t.(K(A,M)+e,b_)+n=E. Vehicle 846 18 式∑∑++∑∑-∑++∑ Z00 101 16 7 Segment 2310 18 7 ∑和∑分别是由核Ward's linkage聚类算 法得到的2个类中第i个簇和第广个簇对应的协 表2列出了上述算法在使用线性核的情况下 方差矩阵，i=1,2,…,Cpj=1,2…,Cn0 的分类结果。表3给出了上述算法在使用高斯核 类似于线性情形，式(6)、(7的解可表示为 的情况下的分类结果。从表2可以看出，提出的 W+ 算法在Wine、Balance、Vehicle、Zoo这4个数据集 21=b. 上有最高的分类精度，并且在其他数据集上也有 (8) -c(prP+c2。'o+cl+e∑ 不错的表现。从表3可以看出，所提出的算法在 Iris、Vowel、Balance、Vehicle、Zoo、Segment这 6个数据集上的分类准确率最高，并且在Wine数 cdQQ.+cPP.+e+cPE. 据集上也有较高的准确率。图1是对实验结果更 直观的表示。 式中：P=[K(A,Me+}O=[K(B,Me.月 表2线性核函数下精确度的比较 M∑M Table 2 Comparison of accuracies using linear kernel 0 1-v-1 1-v-r ILST- 本文 数据集 MBLSSVM M0r∑M00 LSTWSVMLSTWSVM KSVC 算法 0 0 Iris 95.35 91.63 76.67 85.73 90.45 Wine 97.26 97.67 97.90 98.80 98.99 3实验结果与分析 Vowel 80.66 44.12 50.00 47.38 49.60 使用“多对一”的策略将ES-LSTWSVM模型 Balance 86.39 85.87 88.47 86.63 88.65 扩展到多类分类中。为了证明该算法的有效性， Vehicle 80.04 77.18 45.80 78.70 81.14 给出了该算法在多个UCI数据集上的实验结 Z00 94.87 92.02 92.85 96.51 98.23 果。在实验中，选择了“一对一”最小二乘孪生支 Segment 94.32 90.51 60.60 89.72 90.45 持向量机(I-v-1 LSTWSVM)、“一对多”最小二乘

f+(x) = (w+Φ(x))+b+ f−(x) = (w−Φ (x))+b− 数可表示为 和 。 由希尔伯特空间理论[23] 知： w+ = m∑1+m2 i=1 (λ+)iΦ(xi) = Φ(M)λ+ w− = m∑1+m2 i=1 (λ−)iΦ(xi) = Φ(M)λ− ES-LSTWSVM 构造如下 2 个基于核函数的 超平面： K(x T , MT )λ+ +b+ = 0 K(x T , MT ， )λ− +b− = 0 M = [ A T B T ] 式中： ； K(xixj) = (Φ(xi)Φ(xj))。 在非线性情形下，ES-LSTWSVM 可表示为 min w+,b+,ξ 1 2 K(A, MT )λ+ +e+b+ 2 + c1 2 ξ T ξ+ c2 2 (∥λ+∥ 2 2 +b 2 + )+ c3 2 λ T +Φ(M) T∑Φ + Φ(M)λ+ s.t. −(K(B, MT )λ+ +e−b+)+ξ = E− (6) min w−,b−,η 1 2 K(B, MT )λ− +e−b− 2 + c4 2 η Tη+ c5 2 (∥λ−∥ 2 2 +b 2 − )+ c6 2 λ T −Φ(M) T∑Φ − Φ(M)λ− s.t. (K(A, MT )λ− +e+b−) +η = E+ (7) ∑Φ + = ∑Φ P1 +···+ ∑Φ PCp ∑Φ − = ∑Φ N1 +···+ ∑Φ ∑ NCn Φ Pi ∑Φ Nj i = 1,2,··· ,Cp, j = 1,2,··· ,Cn 式中： ； 。 和 分别是由核 Ward’s linkage 聚类算 法得到的 2 个类中第 i 个簇和第 j 个簇对应的协 方差矩阵[13-14] ， 。 类似于线性情形，式 (6)、(7) 的解可表示为 z1 = [ w+ b+ ] = −c1 ( P T Φ PΦ +c1QΦ TQΦ +c2 I+c3 ∑Φ 1 )−1 QΦ TE− (8) z2 = [ w− b− ] = c4 ( QΦ TQΦ +c4PΦ T PΦ +c5 I+c6 ∑Φ 2 )−1 PΦ TE+ PΦ = [ K(A, MT ) e+ ] QΦ = [ K(B, MT ) e− ] 式中： ； ， ∑Φ 1 =   Φ(M) T∑Φ + Φ(M) 0 0 0   ∑Φ 2 =   Φ(M) T∑Φ − Φ(M) 0 0 0   3 实验结果与分析 使用“多对一”的策略将 ES-LSTWSVM 模型 扩展到多类分类中。为了证明该算法的有效性， 给出了该算法在多个 UCI 数据集上的实验结 果。在实验中，选择了“一对一” 最小二乘孪生支 持向量机 (1-v-1 LSTWSVM)、 “一对多”最小二乘 K(xi , xj) =exp(− xi − xj 2 /2σ 2 ) 孪生支持向量机 (1-v-r LSTWSVM)、改进的最小 二乘孪生多分类支持向量[24] ( improvements on least squares twin multi-class classification support vector machine， ILST-KSVC)，多生最小二乘支持 向量机[25] (multiple birth least squares support vector machine，MBLSSVM) 与本文算法进行比较。实验 结果为 10 折交叉验证的平均值。在非线性情形 下，使用高斯核函数 。 3.1 实验结果 在本节中，使用 UCI 数据集中的 Iris、Wine、 Vowel、Balance、Vehicle、Zoo 和 Segment。这些数 据集的特征如表 1 所示。 表 1 数据集的具体特征 Table 1 The detail features of the datasets 数据集 样本个数 特征维数 类别数 Iris 150 4 3 Wine 178 13 3 Vowel 528 10 11 Balance 625 4 3 Vehicle 846 18 4 Zoo 101 16 7 Segment 2310 18 7 表 2 列出了上述算法在使用线性核的情况下 的分类结果。表 3 给出了上述算法在使用高斯核 的情况下的分类结果。从表 2 可以看出，提出的 算法在 Wine、Balance、Vehicle、Zoo 这 4 个数据集 上有最高的分类精度，并且在其他数据集上也有 不错的表现。从表 3 可以看出，所提出的算法在 Iris、Vowel、Balance、Vehicle、Zoo、Segment 这 6 个数据集上的分类准确率最高，并且在 Wine 数 据集上也有较高的准确率。图 1 是对实验结果更 直观的表示。 表 2 线性核函数下精确度的比较 Table 2 Comparison of accuracies using linear kernel 数据集 1-v-1 LSTWSVM 1-v-r LSTWSVM ILST￾KSVC MBLSSVM 本文 算法 Iris 95.35 91.63 76.67 85.73 90.45 Wine 97.26 97.67 97.90 98.80 98.99 Vowel 80.66 44.12 50.00 47.38 49.60 Balance 86.39 85.87 88.47 86.63 88.65 Vehicle 80.04 77.18 45.80 78.70 81.14 Zoo 94.87 92.02 92.85 96.51 98.23 Segment 94.32 90.51 60.60 89.72 90.45 ·1016· 智 能 系 统 学 报 第 15 卷

第5期 史颂辉，等：基于能量的结构化最小二乘李生支持向量机 ·1017· 表3径向基核函数下精确度的比较 的分类准确率高达86.96%。图2(b)显示当E+: Table 3 Comparison of accuracies using RBF kernel E.=4:3时，算法在Liver数据集上的分类准确率 1-v-l 1-V-r ILST- 本文 数据集 MBLSSVM 高达71.15%。图2(c)显示当E+=0.8,E_=0.7时， LSTWSVM LSTWSVM KSVC 算法 算法在Breast数据集上的分类准确率高达77.38%. Iris 95.03 96.1280.00 94.87 98.00 图2(d)显示当E,:E_=1:1时，算法在Ionosphere Wine 74.34 76.69 91.89 71.77 75.17 数据集上的分类准确率高达88.68%。由此可知， Vowel 97.86 98.64 98.28 96.09 98.93 可以通过寻找最优能量参数来确定最优超平面。 Balance 88.91 90.12 91.06 87.81 91.40 Vehicle 80.79 80.25 58.77 75.71 81.20 Z00 96.93 97.11 96.72 95.61 97.62 0.9 Segment 84.54 85.32 75.76 93.31 93.79 0.8 100 0.7 0.6 90 80 0的 70 246810 0 E+ 60 (a)Heart 50 0 Balance Segmen 07 0 -1mL TWSVM---r LSTWSVM-▲，LS-KsVC-t-MBLSSVM-◆OURs 0.5 (a)线性核函数下精确度的比较 100 10 6 8 90 024 E+ (b)Liver 80 0.8 10 0.7 60 0.6 Vow Balance 0.5 Segment 0行 -l-ILSTWSVM--r STWSVM▲，LST-KSVC-.M1SSVM-◆OURs (b)径向基核函数下精确度的比较 0246810 图1算法精确度的比较 (c)Breast Fig.1 Comparison of algorithm accuracies 3.2能量参数E,和E对算法性能的影响 0.90 为了分析能量参数E.和E对ES-LSTWS- 0.85 盟0.80 VM的分类性能的影响，在Heart、Liver、.Breast和 是0.75 Ionosphere数据集上进行了实验。通过引入可变能 0.70 量参数，所提出的分类器将做出相应的调整以减少 噪声干扰。并使用网格搜索对参数进行选择。为 5 了只考虑能量参数对实验结果的影响，将E$- 0246810 LSTWSVM中的其他参数设置为固定值。图2显 (d)Ionosphere 示了分类性能在Australian、Heart和Diabetes数据 图2能量参数E+和E-对ES-LSTWSVM性能的影响 集上随能量参数E,和E_的变化而变化。图2(a) Fig.2 Effect of energy parameters(E,andE_)on the per- 显示当E+=0.7,E_=1.0时，算法在Heart数据集上 formance of the ES-LSTWSVM

表 3 径向基核函数下精确度的比较 Table 3 Comparison of accuracies using RBF kernel 数据集 1-v-1 LSTWSVM 1-v-r LSTWSVM ILST￾KSVC MBLSSVM 本文 算法 Iris 95.03 96.12 80.00 94.87 98.00 Wine 74.34 76.69 91.89 71.77 75.17 Vowel 97.86 98.64 98.28 96.09 98.93 Balance 88.91 90.12 91.06 87.81 91.40 Vehicle 80.79 80.25 58.77 75.71 81.20 Zoo 96.93 97.11 96.72 95.61 97.62 Segment 84.54 85.32 75.76 93.31 93.79 Iris Wine Vowel Balance Vehicle Zoo Segment 100 90 80 70 60 50 40 1-v-1 LSTWSVM 1-v-r LSTWSVM ILST-KSVC MBLSSVM OURS (a) 线性核函数下精确度的比较 Iris Wine Vowel Balance Vehicle Zoo Segment 100 90 80 70 60 1-v-1 LSTWSVM 1-v-r LSTWSVM ILST-KSVC MBLSSVM OURS (b) 径向基核函数下精确度的比较 准确率/% 准确率/% 图 1 算法精确度的比较 Fig. 1 Comparison of algorithm accuracies 3.2 能量参数 E+ 和 E− 对算法性能的影响 E+ E− E+ E− E+ = 0.7, E− = 1.0 为了分析能量参数 和 对 ES-LSTWS￾VM 的分类性能的影响，在 Heart、Liver、Breast 和 Ionosphere 数据集上进行了实验。通过引入可变能 量参数，所提出的分类器将做出相应的调整以减少 噪声干扰。并使用网格搜索对参数进行选择。为 了只考虑能量参数对实验结果的影响，将 ES￾LSTWSVM 中的其他参数设置为固定值。图 2 显 示了分类性能在 Australian、Heart 和 Diabetes 数据 集上随能量参数 和 的变化而变化。图 2(a) 显示当 时，算法在 Heart 数据集上 E+ : E− = 4 : 3 E+ = 0.8,E− = 0.7 E+ : E− = 1 : 1 的分类准确率高达 86.96%。图 2(b) 显示当 时，算法在 Liver 数据集上的分类准确率 高达 71.15%。图 2(c) 显示当 时， 算法在 Breast 数据集上的分类准确率高达 77.38%。 图 2(d) 显示当 时，算法在 Ionosphere 数据集上的分类准确率高达 88.68%。由此可知， 可以通过寻找最优能量参数来确定最优超平面。 0.9 0.8 0.7 0.6 0.5 10 5 0 2 4 6 8 10 E- E+ E+ 准确率 (a) Heart 0.8 0.7 0.6 0.5 0.4 10 5 0 2 4 6 8 10 准确率 (b) Liver 0.8 0.7 0.6 0.5 0.4 10 5 0 2 4 6 8 10 准确率 (c) Breast 0.90 0.85 0.80 0.75 0.70 0.65 10 5 0 2 4 6 8 10 准确率 (d) Ionosphere E- E+ E+ E- E- 图 2 能量参数 E+ 和 E− 对 ES-LSTWSVM 性能的影响 Fig. 2 Effect of energy parameters ( E+and E−) on the per￾formance of the ES-LSTWSVM 第 5 期 史颂辉，等：基于能量的结构化最小二乘孪生支持向量机 ·1017·