·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 卷