加权光滑投影孪生支持向量回归算法
2022-12-13徐奔业顾斌杰潘丰熊伟丽
徐奔业，顾斌杰，潘丰，熊伟丽
（江南大学 物联网工程学院，江苏 无锡 214122）
0 概述
支持向量机（Support Vector Machine，SVM）是20世纪90 年代由VAPNIK［1-2］提出的一种机器学习算法。与传统的以降低经验风险为目标的神经网络相比，SVM的主要思想是最小化结构风险，这使得SVM 具有良好的泛化性能［3-4］。目前，SVM在入侵检测［5］、图像处理［6］、故障诊断［7］、干扰识别［8］等领域得到广泛应用。然而，SVM 在训练大规模数据集时，存在时间复杂度高导致训练速度慢的问题［9］。KHEMCHANDANI等［10］提出孪生支持向量机（Twin Support Vector Machine，TSVM）。与SVM 相比，TSVM 仅需求解两个较小规模的二次规划问题，因此训练时间仅为SVM 的1/4 左右。CHEN等［11］提出投影孪生支持向量机（Projection Twin Support Vector Machine，PTSVM）。PTSVM 通过为每个类寻找一个最优投影轴使投影点类内方差最小化，构建分类模型。
PENG［12］把TSVM 的思想用于回归领域，提出孪生支持向量回归（Twin Support Vector Regression，TSVR）算法。TSVR 通过求解两个较小规模的二次规划问题寻求回归函数，与传统SVR 相比，TSVR 具有更好的泛化性能和更快的训练速度。CHEN等［13］引入Sigmoid光滑函数，对TSVR 的目标函数进行光滑处理，提出光滑孪生支持向量回归（Smooth Twin Support Vector Regression，STSVR）算法。STSVR 通过求解一对无约束优化问题，获得了比TSVR 更快的训练速度。PENG等［14］基于PTSVM 的思想，提出投影孪生支持向量回归（Projection Twin Support Vector Regression，PTSVR）算法，包括双边移位投影孪生支持向量回归（Pair-shifted PTSVR，PPTSVR）算法和单边移位投影孪生支持向量回归（Single-shifted PTSVR，SPTSVR）算法。PTSVR将训练集中的每个训练点进行上下移位得到两个新的移位集，从而利用PTSVM 的思想求解两个最优超平面的法向量。PPTSVR 和SPTSVR 的主要区别在于，PPTSVR 在两个移位集上构建回归函数，而SPTSVR 则是在原始集和一个移位集上构建回归函数。实验结果表明，PTSVR 有着比TSVR 更好的预测性能。
然而，PPTSVR 在寻找最优超平面的过程中，将所有训练样本对超平面的作用视为相同，没有反映数据在空间中的分布情况，当训练样本中存在异常点时，会削弱算法的拟合性能。本文采用孤立森林法赋予每个训练样本不同的权值，通过赋予潜在的异常点很小的权值，削弱异常点对超平面构造的影响，从而提高算法的拟合性能。同时，为了避免在对偶空间中求解二次规划问题，引入正号函数，将有约束优化问题转化为不光滑的无约束优化问题，并采用Sigmoid 光滑函数进行光滑处理，提出一种加权光滑投影孪生支持向量回归（Weighted Smooth Projection Twin Support Vector Regression，WSPTSVR）算法，以证明其任意阶光滑且全局收敛的特性，并采用牛顿迭代法进行求解。
1 WSPTSVR 算法
本节首先采用孤立森林法判断样本中的潜在异常点，并通过异常分数机制赋予每个样本不同的权值；其次引入Sigmoid 光滑函数，提出WSPTSVR 算法，并证明其具有全局唯一最优解；最后在原空间中使用牛顿迭代法进行求解。
1.1 基于孤立森林法的加权系数确定
孤立森林法能够有效地检测出样本中的潜在异常点，即使样本中没有异常点，也能够根据异常分数赋予每个样本相应的权值，从而提高算法的拟合性能［15-17］。孤立森林法首先递归地分割给定样本集，直到每个样本都被单独分离出来，然后根据每个样本分离的路径长度计算其异常分数，根据异常分数大小判断样本是否为异常点并赋予每个样本点相应的权值。通过孤立森林法确定加权系数共分为以下3 个步骤：
1）通过训练样本的子集构建t棵孤立树，建立孤立森林。
2）在训练后的孤立森林中，根据每个样本点分离所需的路径长度赋予其相应的异常分数Si，Si的取值范围为0～1，且取值越大，该点为异常点的可能性越大，异常分数Si计算如下：
其中：h(i)为样本i的路径长度，即从根节点到叶子节点的边数，而异常点更容易被孤立，因此h(i)较小；E(h(i))为样本i在一组孤立森林中路径长度的均值；c(n)是样本数为n时路径长度的均值，用来标准化样本i的路径长度h(i)。c(n)计算如下：
其中：H(n-1)=ln(n-1)+0.577 215 664 9 为调和数。
3）通过孤立森林法中的异常分数机制为每个样本点赋予相应的权值：
其中：ρi表示第i个样本的权值。
文献［15］的研究表明，当样本点的异常分数Si>0.60 时，即视该样本点为潜在异常点，应赋予很小的权值，则样本点的权值矩阵可表示为对角矩阵：
1.2 线性情况
假设训练集用D={(xi；yi)，i∈Ι={1，2，…，n}}表示，其中，xi∈Rm为输入，yi∈R为输出，I为指标集，n为样本个数，m为样本特征数。为了后续表示简单起见，分别用矩阵X=[x1，x2，…，xn]T∈Rn×m和向量Y=[y1，y2，…，yn]T∈Rn表示输入和输出，用矩阵J=[X，Y]∈Rn×(m+1)表示训练样本，分别用矩阵Aε=[X，Y+εe]和Bε=[X，Y-εe]∈Rn×(m+1)表示上移和下移训练样本，其中ε>0 为不敏感因子，e为全1 的列向量。
在双边移位投影孪生支持向量回归算法的目标函数中引入权值矩阵Wij，构造如下最优化问题：
然而，式（5）和式（6）需要在对偶空间中求解二次规划问题，训练速度较慢。为了加快训练速度，采用正号函数将其转化为无约束优化问题，在原空间中直接进行求解。
由Karush-Kuhn-Tucker（KKT）条件可得：
式（5）和式（6）可改写为如下无约束优化问题：
定理1［18］无约束优化问题式（9）和式（10）连续但不光滑。
定理1 表明式（9）和式（10）不光滑，因此无法使用牛顿迭代法等梯度优化方法求解。为此，采用Sigmoid 光滑函数逼近正号函数(x1)+和(x2)+。
Sigmoid 光滑函数p(x，α)定义如下：
其中：α为正常数。
据此可得正号函数(x1)+和(x2)+的Sigmoid 光滑函数分别如下：
将式（12）和式（13）分别代入式（9）和式（10），得到线性情况下加权光滑投影孪生支持向量回归算法的两个无约束优化问题，如式（14）、式（15）所示：
引理1［19］若矩阵A∈Rn×n是实对称矩阵，则A是正定矩阵当且仅当存在矩阵B∈Rm×n使得A=BTB。
定理2式（14）中的P1和式（15）中的P2是严格凸函数。
证明对任意的正常数α，P1显然是连续可微的，以下证明其是严格凸函数：
考虑到权值矩阵和对角矩阵都是正定阵，两者可以分别分解为PTP和QTQ的形式，其中P和Q分别为两者的平方根矩阵。因此，∇2P1(u1)可以分解如下：
其中：C1，C3和α都是正标量；I为正定矩阵。由 引理1 可得∇2P1(u1)是正定的，因此P1是严格凸函数。同理可证P2也是连续可微的严格凸函数。
式（14）和式（15）二阶可微，因此可以使用具有快速收敛能力的牛顿迭代法进行求解［20-21］。由定理2 可知式（14）和式（15）是严格凸的，因此使用牛顿迭代法求解可以全局收敛，并得到唯一最优解。牛顿迭代法可表示如下：
然后，通过求解式（23）和式（24）两个无约束最小化问题，可得两个最优超平面的偏置分别如式（25）、式（26）所示：
在通常情况下，δ1，δ2≠0［14，21］，可得移位函数f1(x)=-(+b1)/δ1和f2(x)=-(+b2)/δ2。
最终，可得回归函数如下：
1.3 非线性情况
在非线性情况下，利用核技巧，构造加权光滑投影孪生支持向量回归算法的两个无约束优化问题如下：
其中：φ(·)表示从实空间R到核特征空间H的映射。
定理2 同样适用于非线性加权光滑投影孪生支持向量回归算法，即式（28）和式（29）是连续可微的严格凸函数，亦可采用具有快速收敛能力的牛顿迭代法进行求解。
1.4 算法步骤
在线性情况下，采用牛顿迭代法训练加权光滑投影孪生支持向量回归算法的过程如下：
输入惩罚参数C1和C2，正则化参数C3和C4，不敏感损失参数ε，精度ttol，最大迭代次数imax和训练数据集矩阵J
输出回归函数f(x)
步骤1通过式（4）计算权值矩阵Wij。
步骤2给定任意初始点和，并令迭代步骤i=0。
步骤3基于和，通过式（19）和式（20）分别计算和直到
步骤4通过式（27）计算f(x)。
非线性情况跟线性情况类似，此处省略。
1.5 时间复杂度分析
本节将WSPTSVR 算法的时间复杂度与TSVR［12］、STSVR［13］、PTSVR［14］以及快速聚类加权孪生支持向量回归（Fast Clustering-based Weighted Twin Support Vector Regression，FCWTSVR）算法［9］进行对比。由于加法的时间复杂度远小于乘法的时间复杂度，因此本文只考虑矩阵乘法运算的次数。另外，核矩阵的求解是所有算法都不可避免的，因此也不作考虑。
PPTSVR、SPTSVR 与TSVR一样，在对偶空间中求解二次规划问题，其时间复杂度为O(n3)。而WSPTSVR 与STSVR 一样，在原空间中采用牛顿迭代法进行求解，由于迭代过程中均为对角矩阵相乘和对角矩阵求逆，因此一次迭代的时间复杂度为O(n)，而牛顿迭代法具有快速收敛能力，因此STSVR与WSPTSVR 算法的时间复杂度要小于TSVR及PPTSVR。另外，由于WSPTSVR 算法在目标函数中加入了加权项，因此时间复杂度比STSVR 稍大。对于FCWTSVR，其时间复杂度虽然也为O(n3)，但是还采用了快速聚类的方法剔除异常点，因此时间复杂度要大于PPTSVR、SPTSVR 和TSVR。
2 实验结果与分析
2.1 实验设计与参数选择
为了验证WSPTSVR 算法的有效性，将其与TSVR、STSVR、PPTSVR、SPTSVR 以及FCWTSVR分别在基准测试数据集和人工测试函数上进行比较。首先对数据集进行归一化处理，然后采用标准的五折交叉验证法将数据集划分为训练集和测试集。采用RMSE、MAE、ET 这3 个性能指标来综合评价回归算法的性能：
通常地，RMSE 的值越小，算法的预测性能越好；MSE 的值越小，算法的预测误差越小；ET 的值越小，表明预测值与真实值的一致性越好。一个好的回归算法应该综合考量RMSE、MAE 和ET 的值。
此外，还分别统计了各算法的CPU 运行时间。所有实验都是在MATLAB 2019a 平台上用Intel i5-9400F@2.90 GHz 处理器、16 GB 内存的计算机完成的，并且所有的实验结果均取20 次独立运行结果的平均值。
参数选择与算法性能密切相关，实验采用网格搜索法选取最优参数。由于ε1和ε2的设置对预测性能不会产生很大影响［13，22-23］，因此将ε1和ε2的值都设置为0.01。在TSVR 中，令C1=C2并且在集合{2i|i=-8，…，0，…，8}中进行寻优。为了保证算法对比的公平性［9，24］，令STSVR、PPTSVR、SPTSVR 和WSPTSVR 算法中C1=C2、C3=C4，且在集合{2i|i=-8，…，0，…，8}中进行寻优。此外，在STSVR 和WSPTSVR 算法中，设置精度ttol=10-6，最大迭代次数imax=50。在非线性实验中，核函数统一采用高斯径向基函数K(xi，xj)=参数σ在集合{2i|i=-5，…，0，…，5}中进行寻优。
2.2 基准测试数据集
为了对比各个算法的综合性能，将其在7 个基准测试数据集上进行测试，使用的基准测试数据集如表1 所示，其中样本数最小为103，最大为9 568，它们可以从UCI 机器学习库下载。
表1 实验中使用的7 个基准测试数据集Table 1 Seven benchmark datasets used in the experiments
表2 统计了各个算法在7 个基准测试数据集上的实验结果，为了清楚起见，最优结果加粗表示。
由表2 可以看出：1）与PPTSVR 相比，WSPTSVR算法在大多数数据集上有着相似或者更小的RMSE、MAE 和ET，这是由于WSPTSVR 算法采用孤立森林法赋予样本中的异常点很小的权值，并通过异常分数赋予每个样本点不同的权值，能够有效地降低潜在噪声或异常点对回归超平面的影响，从而提升算法的预测性能；2）与采用聚类方法去除异常点的FCWTSVR 相比，WSPTSVR 算法在4 个数据集上的RMSE 值最优，在3个数据集上的MAE值最优，而FCWTSVR的RMSE、MAE 和ET 值均在3 个数据集上最优，表明WSPTSVR算法的预测性能与当前提出的回归算法相比具有可比性。
在算法的训练时间方面，WSPTSVR 算法的时间复杂度要小于TSVR、PPTSVR 以及SPTSVR，实验结果也表明，WSPTSVR 算法的训练速度快于TSVR、PPTSVR 以及SPTSVR。但是由于WSPTSVR 算法在目标函数中引入了权值矩阵，因此与STSVR 相比，训练速度稍慢。而FCWTSVR 由于采用了快速聚类算法剔除异常点，其时间复杂度在6 种算法中是最大的，实验结果也表明，FCWTSVR 的训练速度最慢。
2.3 人工测试函数
为了进一步验证WSPTSVR 算法在非线性情况下的拟合性能，在sinc(x)函数上进行实验，并且人为添加两种不同类型的噪声。sinc(x)函数的具体形式如下：
其中：xi表示输入；yi表示对应于xi的输出；ni表示噪声。两种不同类型噪声的具体形式如下：
其中：U[-0.1，0.1]表示在闭区间[-0.1，0.1]内服从均匀分布；N[0，0.12]表示服从均值为0、方差为0.12的高斯分布。
随机生成47 个混入噪声的独立样本作为训练样本和150 个混入噪声的独立样本作为测试样本。另外，在训练样本中人为加入3 个异常点。
表3 给出了2 种不同类型噪声下6 种回归算法的平均RMSE、MAE、ET 以及CPU 运行时间，最优结果加粗表示。
表3 6 种回归算法在人工测试函数上的实验结果Table 3 Experimental results of six regression algorithms on artificial test function
从表3 可以看出：当样本中没有异常点时，FCWTSVR 和WSPTSVR 的RMSE、MAE 以及ET 值要小于其他4 种回归算法，表明FCWTSVR 和WSPTSVR 算法具备更好的预测性能和抗噪声能力；当样本中存在异常点时，WSPTSVR 算法的RMSE、MAE 和ET 值均明显小于PPTSVR，以RMSE为例，WSPTSVR 算法比PPTSVR 平均约小44.2%，表明本文算法在样本中存在异常点时，有着更好的预测性能。这是由于本文算法采用孤立森林法赋予异常点很小的权值，因此受异常点的影响较小。另外，FCWTSVR 采用聚类的方法剔除样本中的异常点，同样获得了较好的预测性能。在训练时间方面，由于WSPTSVR 算法直接在原空间中采用牛顿迭代法进行求解，训练速度比TSVR、PPTSVR 和SPTSVR 更快，而与STSVR 相比，由于目标函数中添加了权值矩阵，因此训练速度稍慢。
图1 给出了高斯分布噪声下不同回归算法在sinc(x)函数上的拟合曲线。从图1 可以看出，与PPTSVR 相比，WSPTSVR 算法在噪声和异常点的干扰下更接近真实曲线，拟合效果更好。这是由于WSPTSVR 算法采用孤立森林法判断样本中的异常点，并利用样本的异常分数赋予噪声和异常点很小的权值，从而获得较好的拟合效果。反观TSVR、STSVR、PPTSVR 和SPTSVR 在异常点处的拟合曲线扭曲较为明显，受异常点的影响较大，拟合效果较差。原因是这4 种回归算法赋予所有样本点相同的权值，而异常点的存在迫使拟合曲线偏向异常点，从而使得拟合效果变差。另外，FCWTSVR 采用聚类的方法确定并剔除异常点，因此在异常点处也获得了较好的拟合效果。
图1 高斯分布噪声下6 种回归算法的拟合曲线Fig.1 Fitting curves of six regression algorithms under noise with Gaussian distribution
4 结束语
本文提出一种加权光滑投影孪生支持向量回归算法。采用孤立森林法判断样本中潜在的异常点，并通过赋予潜在的异常点很小的权值，有效地削弱了其对超平面构造的影响。引入Sigmoid 光滑函数，通过在原空间中采用牛顿迭代法求解无约束优化问题，获得了比双边移位投影孪生支持向量回归算法更快的训练速度。实验结果表明，与其他代表性回归算法相比，该算法受异常点的影响更小，拟合效果更佳。下一步将从寻找逼近能力更优的光滑函数入手，使WSPTSVR 算法获得更好的拟合性能。
