改进的Ramp孪生支持向量机聚类

陈素根，刘玉菲

1.安庆师范大学 数理学院，安徽 安庆 246133

2.安徽省大别山区域复杂生态系统建模、仿真与控制重点实验室，安徽 安庆 246133

3.安徽省皖江流域种群生态模拟与控制国际联合研究中心，安徽 安庆 246133

聚类分析是无监督学习问题，它考虑无标签数据内部自身结构，将数据聚成若干类，被广泛应用于社区检测、图像处理和基因分析等方面[1-2]。K-means 算法[3]是经典的基于划分思想的聚类算法，它通过迭代寻找k个聚类中心点，使得总体误差最小。受K-means算法的启发，通过迭代寻找k个聚类中心平面。2000年，Bradley 等人[4]提出了k平面聚类算法（K-plane clustering，KPC），开启了基于平面聚类算法的新思路。然而，KPC通过二次函数度量类内散度，要求数据点尽可能接近聚类中心平面，仅仅考虑了类内的数据点对聚类效果影响，从而该算法聚类效果不佳。为了克服KPC存在的问题，Liu等人[5]提出了k近端平面聚类算法（K-proximal plane clustering，KPPC），KPPC同时考虑了类内数据点和类间数据点的影响，每类数据点更加接近该类中心平面而其他类数据点尽可能远离。为了提升KPC 和KPPC 的性能，2015年，Wang 等人[6]提出了孪生支持向量机聚类算法（twin support vector clustering，TWSVC），该算法需要求解一系列二次规划问题，计算相对复杂。同时，TWSVC 基于Hinge 损失函数度量类间离散程度，由于Hinge 损失函数是无界函数，导致TWSVC 算法对远离中心平面的数据点比较敏感。为了解决这个问题，2019 年，Wang 等人[7]利用有界的Ramp 损失函数代替Hinge 损失函数，提出了基于Ramp 损失的孪生支持向量机聚类算法（Ramp-based twin support vector clustering，RampTWSVC），该算法通过交替迭代求解非凸优化问题，对远离聚类中心平面的数据点相对鲁棒。然而，Ramp 损失函数是一种对称的函数，对聚类中心平面两边的数据点采用相同的惩罚，没有考虑数据分布的问题[8]。近年来，支持向量机损失函数方面的研究被广泛关注[9-11]，且非对称损失函数的孪生支持向量机聚类算法逐渐成为新的研究热点[12-13]。

综上分析，受RampTWSVC 和非对称损失函数的启发，本文首先构造了一个非对称Ramp 损失函数，并在此基础上提出了改进的Ramp损失孪生支持向量机聚类算法，简称IRampTWSVC。该算法有以下优点：（1）非对称Ramp损失函数继承了Ramp损失函数的有界性特点，可以有效降低远离聚类中心平面数据点对聚类中心平面的影响。同时，它又具有非对称损失函数的优点，对不同位置的数据点采用不同的惩罚，使得该算法更加鲁棒。（2）参数t可以灵活调节非对称的Ramp损失函数的表达式，以适应不同的数据分布，使得IRampTWSVC 具有更好的泛化性能。特别地，当参数t等于1 时，IRampTWSVC 退化为RampTWSVC。（3）多个UCI数据集和人工数据集上的实验结果表明本文所提IRampTWSVC算法的有效性。

1 相关工作

对于聚类问题，本文考虑m个n维数据点{x1,x2,…,xm}，用一个矩阵表示为X=(x1,x2,…,xm)∈Rn×m，第i簇数据点构成一个矩阵Xi，其余簇的数据点构成一个矩阵。设这m个数据点属于k簇，对应的标签为y∈{1,2,…,k}。

对于含有k簇的聚类问题，TWSVC 寻找k个聚类中心平面，设第i簇中心平面为：

它要求第i簇数据点尽可能聚集在这一簇中心平面周围，其余簇数据点尽可能远离这一簇中心平面。线性TWSVC优化问题[6]如下：

其中，c表示惩罚参数，ξi是松弛向量，e表示分量全为1的适当维数向量。

经过一系列推导，优化问题（2）转化为如下对偶问题：

受TWSVC 启发，Wang 等人[7]利用有界的Ramp损失函数代替Hinge 损失函数，提出了基于Ramp 损失的孪生支持向量机聚类算法（RampTWSVC）。Ramp损失函数定义如下：

其中，Δ∈[0,1)和s∈(-1,0]是用于控制损失函数形式的两个常量，|ρ|=x+bi|表示偏差，(ρ)表示类内损失函数，(ρ)表示类间损失函数。

对第i簇中心平面，线性RampTWSVC的优化问题为：

其中，f(xj;wi,bi)=+bi。

简单起见，记ui=(wi,bi)T，将每个数据点维数增加一维且取值为1。于是，第i簇数据点记为Zi=[Xi,e]，其余簇的数据点记为=[,e]。经过一系列代数运算，式（5）可转化为：

显然，式（6）是一个非凸优化问题，引入辅助向量p1∈{-1,0,1}mi和p2∈{-1,0,1}m-mi，其中mi表示第i簇数据点个数，优化问题式（6）等价于下面的混合整数规划问题：

其中，p1(j)和p2(j)分别表示p1和p2的第j个元素。

给定初始向量，通过式（7）的约束条件计算(t=1,2,…)固定时，式（7）转化为一个无约束凸优化问题，可以通过序列最小优化（sequential minimal optimization，SMO）等算法求解。当解出之后，再通过式（7）更新和，这样不断交替迭代下去，直到式（7）的目标函数值不下降，终止迭代并得到最优解。对任意数据点x，按照以下规则进行聚类：

利用核技巧可将线性RampTWSVC模型推广到非线性RampTWSVC模型，详细内容可见参考文献[7]。

2 IRampTWSVC

2.1 非对称Ramp损失函数

由Ramp损失函数的定义知道，它是一种对称的损失函数，对聚类中心平面两侧的数据点采用相同惩罚，没有考虑数据的分布。因此，本文对Ramp 损失函数进行改进，构造一种非对称的Ramp 损失函数，对不同位置的数据点采用不同的惩罚，具体定义如下：

其中，Δ∈[0,1)，s∈(-1,0]和t∈[0,1]是用于控制损失函数形式的3个常量，(ρ)表示类内损失函数，表示类间损失函数，|ρ|=+bi|表示偏差。

显然，由式（9）可知，非对称Ramp损失函数也是有界函数，保留了Ramp 损失函数有界的特性，继承了Ramp损失函数的优势，可以有效降低远离聚类中心平面的数据点对聚类中心平面的影响，从而对噪声或异常点具有较好的鲁棒性。特别地，当t=1 时，非对称Ramp 损失函数退化为Ramp 损失函数。同时，当参数t在[0,1)之间取值时，式（9）所定义的损失函数为非对称的，它对聚类中心平面两边的数据点采用不同的惩罚，有利于刻画数据的分布特征，使模型具有更好的泛化性能。

总之，式（9）所定义的非对称Ramp 损失函数是基于数据分布的，从类内损失和类间损失两个角度考虑给予数据点不同的惩罚。对于类内损失函数，损失函数值随数据点到第i簇聚类中心平面的距离线性增长，距离聚类中心平面越远，损失函数值越大，定义为ρ(xj)的一次函数。但是，当数据点到第i簇聚类中心平面的距离小于1-Δ或大于2-Δ-s时，损失函数值分别赋予常数。对于类间损失函数，距离第i簇聚类中心平面越远，损失函数值越小，也定义为ρ(xj)的一次函数，当数据点到第i簇聚类中心平面的距离小于-s或大于1+Δ时，损失函数值分别赋予常数。同时，对于类内损失函数和类间损失函数有一个原则，也就是类内数据点的损失值不会大于类间数据点的损失值，且都保持有界性特征。

图1分别给出了当Δ=0.3，s=-0.2，t=0,0.2 和0.4 的非对称Ramp 损失函数的示意图，其中图1（a）为类内损失函数，图1（b）为类间损失函数。从图1可以看出，参数t对损失函数有较大的调节作用，使得损失函数表达式更加丰富，以适应不同的数据分布。参数t控制着损失函数值变化的快慢和损失函数值的上下界，保证类内损失函数值不超过类间损失函数值。

图1 非对称Ramp损失函数的示意图Fig.1 Illustration of asymmetric Ramp loss function

2.2 线性IRampTWSVC

基于非对称Ramp 损失函数，本文提出改进的RampTWSVC，记为IRampTWSVC。类似于Ramp-TWSVC，对于第i簇聚类中心平面，线性IRampTWSVC的优化问题为：

在目标函数式（10）中：第一项表示正则项，控制模型的复杂性；第二项表示类内损失，最小化这一项使得第i簇中的数据点到第i簇聚类中心平面的距离|ρi(xj)|尽可能小，从而这些数据点尽可能聚集在该类的聚类中心平面周围；第三项表示类间损失，最小化这一项使得其余簇的数据点到第i簇聚类中心平面的距离|ρi(xj)|尽可能大，从而这些数据点尽可能远离第i簇聚类中心平面。根据非对称的Ramp损失函数的定义式（9）可知，类内损失函数和类间损失函数都是有界的分段函数，它们根据数据点的位置给予不同的惩罚，使得远离聚类中心平面的数据点不会对聚类中心平面产生更大的影响，从而增强了模型的鲁棒性。

简单起见，记ui=(wi,bi)T，将每个数据点维数增加一维且取值为1。于是，第i簇数据点记为Zi=[Xi,e]，其余簇的数据点记为=[,e]。类似于RampTWSVC的推导过程，经过一系列代数运算，式（10）可转化为：

其中，p1(j)和p2(j)分别对应的是p1和p2的第j个元素。

给定初始向量u(0)i，通过式（11）的约束条件计算(t=1,2,…)固定时，式（11）转化为一个无约束凸优化问题，将其转化为对偶问题：

Xi表示第i簇数据点，表示不属于第i簇的数据点。

显然，式（12）为有约束的二次规划问题，可以通过SMO算法求解出。当解出之后，再通过式（11）更新和，这样不断交替迭代下去，直到式（11）的目标函数值不下降，终止迭代并得到最优解。对任意数据点x，再按照以下规则聚类：

综上所述，给出线性IRampTWSVC 算法步骤如下：

算法1线性IRampTWSVC

实际上，算法1 是一个交替迭代优化算法，其求解过程与RampTWSVC类似，终止于有限步迭代，获得模型的局部最优解，相关理论证明可参考文献[7]。

2.3 非线性IRampTWSVC

对于非线性情形，首先选择合适的核函数K将数据映射到高维特征空间中，然后利用核技巧推广到非线性IRampTWSVC 模型。与线性情况类似，非线性IRampTWSVC优化问题如下：

其中，ρi(K(xj,X))=K(xj,X)Twi+bi且cw,cb>0 是参数。

类似地，记ui=(wi,bi)T，将每个数据点增加一维且取值为1。第i簇的数据点记为Ki=[K(Xi,X),e]，其余簇的数据点记为=[K(,X),e]。非线性IRamp-TWSVC模型的求解过程与线性IRampTWSVC 模型的算法步骤非常相似，唯一不同的是先选择合适的核函数K将数据映射到高维空间，此处不再赘述。

3 实验结果与分析

为了验证本文所提IRampTWSVC 算法的性能，选取8 个UCI 数据集Iris、Haberman、Zoo、Wine、Glass、Blood、Seeds 和Lenses（https://archive.ics.uci.edu/ml/datasets.php）以及5 个人工数据集Flame、Compound、Simplex、Spherical_4_3 和Spherical_5_2（https://github.com/deric/clustering-benchmark/tree/master/src/main/resources/datasets/artificial）进行实验。具体实验环境：MATLAB R2019b，硬件配置为Windows 11操作系统，16 GB内存，2.10 GHz主频CPU的计算机。选取KPC[4]、KPPC[5]、TWSVC[6]和RampTWSVC[7]作为实验对比算法，与IRampTWSVC 进行实验比较。实验中均采用网格寻优的方法为各算法选择最优参数，KPC、KPPC、TWSVC和RampTWSVC中的参数c、cw、cb范围为{2i|i=-5,-4,…,5}，IRampTWSVC中的参数t的范围设置为{0,0.1,0.2,…,1}。对于非线性情形，选择高斯核函数K(x,y)=e-||x-y||2/2μ2，核参数μ的范围为{2i|i=-5,-3,-1,…,5}。根据经验，Ramp-TWSVC 和IRampTWSVC 中的参数Δ和s分别设置为Δ=0.3 和s=-0.2，所有算法均采用近邻图（nearest neighbor graph，NNG）[14]初始化聚类中心平面法向量和。

为了对算法性能进行评价，使用准确率（Accuracy）来衡量聚类性能。给定聚类标签yi∈{1,2,…,k},i=1,2,…,m，其中m为数据点个数，k为簇数，计算相应的相似矩阵M∈Rm×m如下：

根据式（15），先利用数据集的真实聚类标签计算得到相似矩阵Mt，再利用预测聚类标签计算得到相似矩阵Mp。聚类算法的准确率定义为兰德统计量（Rand statistic）：

其中，n00是Mp和Mt中0的个数，n11是Mp和Mt中1的个数。

为了验证算法对噪声的鲁棒性，分别在无噪声数据集和有噪声的数据集上进行实验。对于每个数据集，分别加入均值为0、标准差σ为0.05 和0.10 的两种高斯噪声生成带有噪声的数据集，σ为0表示无噪声数据集。对于线性IRampTWSVC 算法，它在大多数数据集上均取得了较好的聚类准确率。以Spherical_5_2数据集的实验结果为例，在无噪声情形下，线 性KPC、KPPC、TWSVC、RampTWSVC 和IRampTWSVC的聚类准确率分别为80.20%、74.50%、85.07%、83.48%和85.58%；在标准差σ为0.05 的噪声情形下，聚类准确率分别为78.69%、74.15%、69.09%、81.99%和85.17%；在标准差σ为0.10 的噪声情形下，聚类准确率分别为77.59%、72.54%、75.77%、83.76%和86.44%。总体而言，线性IRampTWSVC算法在无噪声、标准差σ为0.05 和标准差σ为0.10 的噪声情形下，在13 个实验数据集上分别取得了12个、11个和10个最好的聚类准确率。另外，图2分别给出了Spherical_5_2 数据集的无噪声、标准差σ为0.05 和标准差σ为0.10 的有噪声数据集的真实簇类图，图3和图4分别给出了线性RampTWSVC和线性IRampTWSVC在这三种情形下的聚类效果图。图2～图4的效果图进一步验证了线性IRampTWSVC算法的性能，对噪声具有较好的鲁棒性。

图2 Spherical_5_2数据集的真实簇类图Fig.2 Actual clusters in dataset Spherical_5_2

图3 线性RampTWSVC在数据集Spherical_5_2上聚类效果图Fig.3 Formation of clusters by linear RampTWSVC on dataset Spherical_5_2

图4 线性IRampTWSVC在数据集Spherical_5_2上聚类效果图Fig.4 Formation of clusters by linear IRampTWSVC on dataset Spherical_5_2

表1 给出了非线性算法在所有数据集上的聚类准确率及次序，表中粗体数字表示最好的聚类准确率。从表1 的实验结果不难发现，非线性IRampTWSVC算法在大多数数据集上取得了较好的聚类性能。对于Haberman 数据集，无噪声情形下，非线性IRamp-TWSVC 的聚类准确率为72.57%，比KPC、KPPC、TWSVC 和RampTWSVC 分别高11.31 个百分点、11.62个百分点、11.93个百分点和6.51个百分点；在标准差σ为0.05 的噪声情形下，非线性IRampTWSVC的聚类准确率为67.58%，比KPC、KPPC、TWSVC 和RampTWSVC 分别高6.01 个百分点、5.37 个百分点、7.24 个百分点和2.62 个百分点；在标准差σ为0.10的噪声情形下，非线性IRampTWSVC 的聚类准确率为62.87%，比KPC、KPPC、TWSVC 和RampTWSVC分别高1.92 个百分点、1.92 个百分点、1.30 个百分点和0.98个百分点。这进一步说明了IRampTWSVC具有较好的鲁棒性。根据表1中的聚类准确率的次序，计算非线性KPC、KPPC、TWSVC、RampTWSVC 和IRampTWSVC 的平均次序分别为3.76、4.12、3.59、2.19 和1.35，可以发现非线性IRampTWSVC 算法取得了最高的平均次序。为了说明各算法之间性能的差异，本文分别采用Friedman test 和Nemenyi test 方法检验IRampTWSVC算法与现有算法是否具有显著性差异。根据Friedman test的定义[15]可得：

表1 非线性算法在所有数据集上的聚类准确率及次序Table 1 Clustering accuracy and rank of nonlinear algorithms on all datasets

其中，Ri是第i种算法在N个数据集上的平均排序，k表示算法的数量。于是，根据表1 知N=39,k=5，由式（17）和式（18）计算得≈87.651 7 和FF≈48.732 2。F分布的自由度为(k-1,(k-1)(N-1))=(4,152)，根据F分布临界值统计表知，当α=0.05 时F(4,152)=2.431。因为FF=48.732 2>2.431，说明非线性IRamp-TWSVC算法优于其他算法。根据Nemenyi test的定义[15]，可得：

当α=0.05 时，qα=2.728，根据式（19）计算可得到相应的CD值为0.976 8。非线性IRampTWSVC与KPC、KPPC 和TWSVC 之间的平均次序差分别是3.76-1.35=2.41，4.12-1.35=2.77 和3.59-1.35=2.24，它们都大于CD值，这表明非线性IRampTWSVC 的性能明显优于非线性KPC、KPPC和TWSVC；与非线性RampTWSVC 之间的平均次序差是2.19-1.35=0.84，它小于CD值，这表明非线性IRampTWSVC的性能虽然比非线性RampTWSVC 好，但它们之间的差异不够显著。

非对称Ramp损失函数与Ramp损失函数的区别就在于引入了参数t，使Ramp 损失函数转变为非对称的形式，对位于聚类中心平面两侧的数据点采用不同的损失进行计算，使得远离聚类中心平面的数据点对聚类中心平面的影响降低，并且通过调节参数t可以使模型具有更好的鲁棒性。为了进一步分析IRampTWSVC 中所有参数对算法性能的影响（如图5～图7 所示），以Wine 和Spherical_4_3 数据集为例，首先讨论参数t对线性IRampTWSVC 聚类性能的影响，固定参数cw和cb，参数t取值范围为{0,0.1,0.2,…,1.0}。图5 给出了参数t对线性IRamp-TWSVC 算法聚类准确率的影响，图5（a）为Wine 数据集上的结果，图5（b）为Spherical_4_3 数据集上的结果。从图5（a）中可看出，当参数t取0.9时，聚类准确率最高；从图5（b）中可看出，当参数t取0.6 时，聚类准确率最高。这表明了参数t对线性IRamp-TWSVC算法聚类准确率有较大的影响，充分体现了非对称损失函数的优越性。类似地，再讨论参数cw、cb对线性IRampTWSVC 算法聚类准确率的影响，此时固定参数t，参数cw和cb取值范围为{-5,-4,-3,…,5}。图6 给出了参数cw和cb对线性IRampTWSVC 算法聚类准确率的影响，图6（a）为Wine数据集上的结果，图6（b）为Spherical_4_3 数据集上的结果。实际上，参数t、cw和cb对非线性IRampTWSVC算法聚类准确率也有较大的影响，这里就不赘述了。最后，讨论核参数μ对非线性IRamp-TWSVC 算法聚类准确率的影响，此时固定参数cw、cb和t，核参数μ取值范围为{-5,-4,-3,…,5}。图7 给出了核参数μ对非线性IRampTWSVC聚类准确率的影响。根据图5、图6和图7 的结果，可以发现各参数对IRampTWSVC 聚类准确率都有较大的影响。本文采用了网格寻优的方法选择最优参数，效率相对低下。因此，如何有效地选择最优参数是值得进一步研究的问题。

图5 参数t 对线性IRampTWSVC算法聚类准确率的影响Fig.5 Influence of parameter t on clustering accuracy of linear IRampTWSVC

图6 参数cw、cb 对线性IRampTWSVC算法聚类准确率的影响Fig.6 Influence of parameter cw,cb on clustering accuracy of linear IRampTWSVC

图7 参数μ 对非线性IRampTWSVC算法聚类准确率的影响Fig.7 Influence of parameter μ on clustering accuracy of nonlinear IRampTWSVC

4 结束语

本文构造了一种非对称Ramp损失函数，并在此基础上提出了一种改进的Ramp 损失孪生支持向量机聚类（IRampTWSVC）。在多个UCI数据集和人工数据集上进行实验，实验结果验证了本文算法的有效性。非对称Ramp损失函数不仅继承了Ramp损失函数的优点，而且参数t的引入使模型更加灵活，增强了IRampTWSVC 算法对噪声的鲁棒性。然而，本文算法依然存在一些不足：（1）该算法有多个参数，构建有效的最优参数选择策略有待研究；（2）该算法通过交替迭代求解，每一个子问题都是一个二次规划问题，本文虽然利用了SMO求解算法，但是当数据集规模较大时模型求解依然较慢，如何构建模型的快速求解算法也值得进一步研究。