基于核相似性的模糊多核最小二乘支持向量机

Kernel Similarity-Based Fuzzy Multi-Kernel Least Squares Support Vector Machine

摘要: 最小二乘支持向量机(Least Squares Support Vector Machine, LSSVM)由于同等对待所有样例，从而易受噪声干扰，影响分类性能。模糊LSSVM的提出一定程度上克服了以上问题。本文给出了一种新的样例隶属度计算方法，其在特征空间中，利用每一样例与其他样例核相似性获得隶属度，并将其应用于模糊多核LSSVM (Fuzzy Multi-Kernel LSSVM, FMK-LSSVM)，得到具有强鲁棒性的基于核相似性的模糊多核LSSVM。实验结果验证该方法的可行性与有效性。

Abstract: Least squares support vector machine (LSSVM) is vulnerable to noise and affects the classification performance because it treats all samples equally. Fuzzy LSSVM overcomes the above problems by introducing membership. In this paper, we develop a new method to compute membership. In the feature space, the membership degree is obtained by using the kernel similarity between each sample and other samples, and applied to fuzzy multi-kernel LSSVM (FMK-LSSVM) to obtain a strong robust FMK-LSSVM. Experimental results verify the feasibility and effectiveness of this method.

1. 引言

支持向量机(Support Vector Machine, SVM)以统计学理论为基础 [1] [2]，是一种性能良好的机器学习方法，有效地解决了局部极小值点、小样本、非线性等实际问题，目前已成功应用于模式识别、回归预测、聚类问题等诸多领域，有力地推动了机器学习理论与应用的发展。但是SVM由于需要求解二次优化问题，使其具有高时间复杂度。1999年Suykens等提出最小二乘支持向量机(LSSVM) [3]，通过求解线性方程组来得到决策模型，大大降低了算法计算量。LSSVM利用核技巧解决非线性可分性问题，但同时也带来了核选择难题，为解决这一问题，各类多核学习方法被引入LSSVM，即多核组合代替单核 [4] [5] [6] [7]，即多核LSSVM (Multi-Kernel LSSVM, MK-LSSVM) [8]。

由于同等对待每一样例，包括LSSVM在内的各类SVM算法都易受噪音数据影响。模糊隶属度的引入，得到模糊SVM (Fuzzy SVM, FSVM) [9]，一定程度上缓解了这一问题。当然这一思想同样适用于LSSVM，从而有了模糊LSSVM (Fuzzy LSSVM, F-LSSVM) [10]。对于FSVM与F-LSSVM来说，求得样例隶属度都是至关重要的。现有各类隶属度计算方法，都是基于对噪音的检测。一般而言，噪音应该被赋予较小的隶属度，从而降低其对最终决策函数的影响。有基于Kohonen自组织映射、模糊性指数和模糊c-maan算法等技术的隶属度计算方法 [9]。也有学者将隶属度设置为点与其类中心之间距离的函数 [11] [12] [13]。此外，通过考虑样例的属性和决策之间的不一致性，He等提出了一类基于模糊粗糙集的隶属度计算方法 [14]。上述隶属度的引入，一定程度上提高了SVM的鲁棒性。但所有隶属度计算方法都未结合SVM算法本身特点，只是在样例所在原始空间中度量其相似性程度，从而计算隶属度。然而SVM是在特征空间中实现对样例的分割。原始空间与特征空间的不一致可能造成传统隶属度并不能很好反映样例在特征空间中的重要性程度。本文中，针对MK-LSSVM，通过其组合核获得特征空间中的样例相似性，给出一种基于样本核相似性的隶属度计算方法。从而得到了基于核相似性的模糊MK-LSSVM (Kernel Similarity-Based FMK-LSSVM, KS-FMKLSSVM)。

本文后续内容安排如下，第2节介绍LSSVM、MK-LSSVM和FMK-LSSVM的相关知识；基于核相似性的隶属度计算方法和KS-FMKLSSVM算法在第3节中详细说明；第4节给出实验结果，第5节为结论。

2. 相关知识

2.1. 最小二乘支持向量机(LSSVM)

与经典SVM相同，LSSVM模型通过最优超平面解决分类问题，其主要思想是通过核函数实现在高维特征空间中对样例的线性分割。特征空间中的最优分割超平面对应于原始空间中的非线性分割函数。

设有训练集 $\{\left(x_1,y_1\right),\left(x_2,y_2\right),\cdots ,\left(x_N,y_N\right)\}$ ，其中 $x_i\in R^n,y_i\in \left\{1,-1\right\}$ 。 $\varphi (·)$ 为某非线性映射，将样本由原空间映入高维特征空间，SVM在特征空间中构造最优分割超平面 [1]。设 $\omega$ 与b为特征空间中分割超平面的法向量与偏置。超平面为 ${\omega }^{\text{T}}\varphi \left(x\right)+b=0$ 。LSSVM需要求解以下二次规划问题：

$\begin{array}{l}\underset{\omega ,b,\xi }{\min }\frac{1}{2}{\omega }^{\text{T}}\omega +\frac{1}{2}C{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\xi }_i^2}\\ \text{s}\text{.t}\text{.}{y}_i\left[{\omega }^{\text{T}}\varphi \left(x_i\right)+b\right]=1-{\xi }_i\\ i=1,2,\cdots ,N\end{array}$ (1)

其中C为惩罚系数、 ${\xi }_i$ 为松弛变量。引入拉格朗日乘子，可得对偶问题 [3]：

$(\begin{array}{cc}0& {\tilde{1}}^{\text{T}}\\ \tilde{1}& \Omega +\frac{I}{C}\end{array})\left(\begin{array}{c}b\\ \alpha \end{array}\right)=\left(\begin{array}{c}0\\ Y\end{array}\right)$ (2)

式中： $Y=\left[y_1,y_2,\cdots ,y_N\right]$ ， $\tilde{1}$ 是所有元素为1的列向量，I是N阶单位矩阵，其中 ${\Omega }_{i,j}=y_i{y}_j\varphi {\left(x_i\right)}^{\text{T}}\varphi \left(x_j\right)=y_i{y}_{j}k\left(x_i,x_j\right)$ ， $k\left(x_i,x_j\right)$ 为核函数 [2]。通过求解上述方程组得到LSSVM决策函数：

$f\left(x\right)=sign\left[{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\alpha }_i{y}_{i}k\left(x_i,x\right)}+b\right]$ (3)

2.2. 多核LSSVM

核函数度量了样本在特征空间中的相似性，但是单个核对样本相似性的刻画能力往往有限，核函数与核参数的选择对LSSVM性能有关键影响。然而，当前并不存核函数选择的通用方法，大多靠经验或试算，效果往往不理想且效率低下。作为核方法的重要成果，多核学习近年来已成为机器学习领域广大学者的研究热点 [4] [5] [6] [7]。多核的意义主要体现在通过多个核函数组合可以更准确地表达数据间的相似性，同时也克服了核函数选择这一难题。多核学习成果的引入将使我们可以通过使用多个核函数，而不是一个核函数来表达样本间的相似性，即通过多个核函数的融合来得到样本间最终的相似性 [15]。将多核学习引入到LSSVM，即得到多核LSSVM (MK-LSSVM)。有效避免了核函数及其参数选择难题。线性加权组合是最常用的多核组合方式：

$k_{\eta }\left(x_i,x_j\right)={\displaystyle \underset{l=1}{\overset{M}{\sum }}{\eta }_l{k}_l}\left(x_i,x_j\right),{\eta }_l\ge 0$ (4)

其中， $k_l,{\eta }_l,l=1,2,\cdots ,M$ 分别是基础核与核权重，本文采用该种加权求和的组合方式。在LSSVM模型中，用多核替代单核，得到MK-LSSVM决策函数为：

$f\left(x\right)=\text{sign}\left[{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\alpha }_i{y}_i{\displaystyle \underset{l=1}{\overset{M}{\sum }}{\eta }_l{k}_l\left(x_i,x\right)+b}}\right]$ (5)

MK-LSSVM性能很大程度上依赖于组合核，而其关键就是核权重。本文中，利用核对齐方法 [16] [17] [18]，通过求解以下优化问题来得到核权重 ${\eta }_l$ ：

$\begin{array}{l}\underset{\eta }{\max }A\left(K,y{y}^{\text{T}}\right)=\frac{\langle {{\displaystyle \underset{l=1}{\overset{M}{\sum }}{\eta }_l{k}_l},y{y}^{\text{T}}\rangle }_F}{\sqrt{\langle {{\displaystyle \underset{l=1}{\overset{M}{\sum }}{\eta }_l{k}_l},{\displaystyle \underset{k=1}{\overset{M}{\sum }}{\eta }_k{k}_l}\rangle }_F\langle {y{y}^{\text{T}},y{y}^{\text{T}}\rangle }_F}}=\frac{{\displaystyle \underset{l=1}{\overset{M}{\sum }}{\displaystyle \underset{i,j=1}{\overset{N}{\sum }}{\eta }_l{K}_{i,j}^l}}}{N\sqrt{{\displaystyle \underset{l,s=1}{\overset{M}{\sum }}{\eta }_l{\eta }_s\langle {K_l,K_s\rangle }_F}}}\\ \text{s}\text{.t}\text{.}{\eta }_l\ge 0,l=1,2,\cdots ,M\end{array}$ (6)

这里K是组合核矩阵， ${\langle ·,·\rangle }_F$ 是两个矩阵间的Frobenius内积，其中

${\langle K_1,K_2\rangle }_F={\displaystyle \underset{i=1}{\overset{N}{\sum }}{\displaystyle \underset{j=1}{\overset{N}{\sum }}{k}_1\left(x_i,x_j\right)k_2\left(x_i,x_j\right)}}$ (7)

显然，A越大，则组合核矩阵K与理想核矩阵 $y{y}^{\text{T}}$ 间的距离越小，即组合核对数据相似性刻画能力越强 [16]。为方便求解，(6)式可变形为下述优化问题 [17]：

$\begin{array}{l}\underset{\eta }{\max }{\displaystyle \underset{m=1}{\overset{P}{\sum }}{\displaystyle \underset{i,j=1}{\overset{l}{\sum }}{\eta }_m{k}_{ij}^m}}-{\displaystyle \underset{m,s=1}{\overset{P}{\sum }}{\eta }_m{\eta }_s{\langle K_m,K_s\rangle }_F}-\delta {\displaystyle \underset{m=1}{\overset{P}{\sum }}{\eta }_m^2}\\ \text{s}\text{.t}.{\eta }_m\ge 0,m=1,2,\cdots ,P\end{array}$ (8)

其中， $\delta >0$ 是正则项系数。

2.3. 模糊多核LSSVM

LSSVM继承了SVM的优点，实现了结构风险最小化，但也继承了对噪声敏感的缺点。为此，引入隶属度得到模糊LSSVM [10]，提升了LSSVM鲁棒性。设 $s_i$ 为样本 $x_i$ 的隶属度，则训练集可表示为 $\left\{\left(x_1,y_1,s_1\right),\left(x_2,y_2,s_2\right),\cdots ,\left(x_N,y_N,s_N\right)\right\}$ ，其中 $x_i\in R^n,y_i\in \left\{1,-1\right\},s_i\in \left[0,1\right]$ ，模糊多核LSSVM的模型为：

$\begin{array}{l}\underset{\omega ,b,\xi }{\min }\frac{1}{2}{\displaystyle \underset{l=1}{\overset{M}{\sum }}{\eta }_l}{\omega }_l^{\text{T}}{\omega }_l+\frac{1}{2}C{\displaystyle \underset{i=1}{\overset{N}{\sum }}{s}_i{\xi }_i^2}\\ \text{s}\text{.t}\text{.}{y}_i\left[{\displaystyle \underset{l=1}{\overset{M}{\sum }}{\eta }_l}{\omega }_l^{\text{T}}\varphi \left(x_i\right)+b\right]=1-{\xi }_i\\ i=1,2,\cdots ,N;{\eta }_l\ge 0,l=1,2,\cdots ,M\end{array}$ (9)

相应对偶问题为：

$(\begin{array}{cc}0& {\tilde{1}}^{\text{T}}\\ \tilde{1}& \Omega +\frac{I}{Cs}\end{array})\left(\begin{array}{c}b\\ \alpha \end{array}\right)=\left(\begin{array}{c}0\\ Y\end{array}\right)$ (10)

(10)式中， ${\Omega }_{i,j}=y_i{y}_j{\displaystyle {\sum }_{l=1}^M{\eta }_l{k}_l\left(x_i,x_j\right)}$ ， $s=\left\{s_1,s_2,\cdots ,s_N\right\}$ ，其他符号含义与(2)式相同。通过求解上述方程组得到LSSVM决策函数：

$f\left(x\right)=\text{sign}\left[{\displaystyle \underset{i=1}{\overset{N}{\sum }}{\alpha }_i{y}_i{\displaystyle \underset{l=1}{\overset{M}{\sum }}{\eta }_l{k}_l\left(x,x_i\right)+b}}\right]$ (11)

显然，当 $s_i=1,i=1,2,\cdots ,N$ 时，FMK-LSSVM模型退化为MK-LSSVM。

3. 基于核相似性的FMK-LSSVM

标准的LSSVM因为平等的对待每个样例，所以易受噪音影响而性能变差。为了缓解这种现象，模糊隶属度被引入，得到模糊LSSVM，使每一训练样例因为重要性不同而对分割超平面产生不同的影响，从而提升算法鲁棒性。模糊隶属度的计算是模糊LSSVM的关键。本节通过数据间的核相似性衡量每个样本的隶属度，为与其核相似性高的样例赋予较高的隶属度，为噪音赋予较低的隶属度，来降低噪音的影响。

SVM中的核函数不仅将原空间中的问题转换为特征空间的问题，还有效衡量了数据间的相似性。此处，使用FMK-LSSVM的组合核来度量样本间相似性，两个样例间的核函数值越大，则表明这两个样例间的相似性越高。对于某一样例，与其相似性大且标签一致的样例越多，则该样例越能代表此类数据的特征，应赋予较大的隶属度，反之亦然。基于上述思想，本节提出了一种基于核相似性的隶属度计算方法。主要过程如下。

首先利用组合核函数计算训练集俩俩样本之间的核函数值，并从大到小排序。通过参数 $\alpha \in \left[0,1\right]$ 确定衡量相似性大小的阈值 $\theta$ ，若两样例间核函数值大于 $\theta$ ，则认为其相似性大；从而可以得到每个样例与其相似度大的同类与异类样例数，最终通过S型函数计算得到每个样例的隶属度值 [19]。S型函数表达式为 $f\left(x\right)=1/\left(1+{\text{e}}^{-\tau x}\right)$ ，其可使正常样例与噪音的隶属度差异更大，最大程度降低噪音的干扰，其中S型函数中的参数 $\tau$ 用来控制这种差异性的程度。本文中，我们取 $\tau =10$ 。隶属度函数可被写为：

$s\left(x_i\right)=\frac{1}{1+\exp \left(-\tau y_i\left(\frac{p_i{u}_i}{PU}-\frac{q_i{v}_i}{QV}\right)\right)}$ (12)

其中 $u_i,v_i$ 分别是与样例 $x_i$ 类别相同且相似性达到阈值 $\theta$ 的样例个数， $p_i,q_i$ 分别为与样例 $x_i$ 类别相同且相似性达到阈值 $\theta$ 的核函数值的和，计算公式如下：

$p_i={\displaystyle \underset{y_j=y_i=+1,k_{ij}\ge \theta }{\sum }{k}_{ij}}$ (13)

$q_i={\displaystyle \underset{y_j=y_i=-1,k_{ij}\ge \theta }{\sum }{k}_{ij}}$ (14)

此外， $U=\underset{i}{\max }\left\{u_i\right\},V=\underset{i}{\max }\left\{v_i\right\},P=\underset{i}{\max }\left\{p_i\right\},Q=\underset{i}{\max }\left\{q_i\right\}$ 。

主要计算过程如算法1所示：

将基于核相似性引入FMK-LSSVM，即得到KS-FMKLSSVM。下节中，将通过实验验证KS-FMKLSSVM的可行性与有效性。

4. 实验

论文中的数据选自UCI中的二分类数据集。本节中将KS-FMKLSSVM与其他3类LSSVM方法进行对比。分别是普通MK-LSSVM、基于模糊粗糙集隶属度的模糊多核LSSVM (Fuzzy Rough Set Based FMK-LSSVM, FR-FMKLSSVM)和基于欧氏距离隶属度 [13] 的模糊多核LSSVM (Euclidean Distance Based FMK-LSSVM, ED-FMKLSSVM)。所选数据集的信息如表1所示。

Table 1. The information of UCI dataset in experiment

表1. 实验中的UCI数据集信息

实验中均是选择70%作为训练集，30%作为测试集，重复10次试验求平均得到最终结果。为检验算法鲁棒性，每次训练集中随机选取20%样例改变其标签，作为噪音放回训练集中。此外，本节中多核算法中组合核都由7个高斯核作为基本核组合而成，核参数分别为 $\left[2^{-3},2^{-2},2^{-1},1,2,4,8\right],\alpha =0.5,\tau =10$ 。各个算法测试经度与训练时间结果表2和表3所示。

Table 2. Testing accuracy (%) values of 4 algorithms

表2. 4种方法的测试精度(%)

Table 3. Training time (s) of 4 algorithms

表3. 4种方法的训练时间(s)

实验结果显示，本文提出的KS-FMKLSSVM在UCI的8个数据集上，分类精确都较其他算法有较明显提高，而时间消耗与其他方法相比并没有显著增加，尤其是与其他FMK-LSSVM算法相比，时间支出基本相当。这也验证了本文所提隶属度计算方法的可行性与有效性。

ROC曲线是机器学习常用的模型性能比较指标，曲线横纵坐标分别是假正例率和真正利率。A算法的ROC曲线被B算法的曲线“包住”，则B算法性能优于前者；如果曲线交叉，可以根据ROC曲线下面积大小进行比较，也即AUC值 [20]。图1是部分数据集上4中算法的ROC曲线。从图中我们可以看出，在各个数据集上，KS-FMKLSSVM算法的ROC曲线都“包住”了其他三种算法的曲线，即KS-FMKLSSVM的综合性能是最佳的，进一步验证了本文给出的隶属度计算方法的有效性。

为进一步检验所提KS-FMKLSSVM的鲁棒性，我们以sonar数据为例，展示不同噪声水平下，本文所提方法与其他方法的分类效果的变化情况，结果如图2所示。

从图2可以看出，随着噪音水平的升高，KS-FMKLSSVM的性能在所有四种算法中表现最佳，分类精度最高，且受噪音影响相对较小，这表明了本文提出的隶属度方法可以最大程度提高FMK-LSSVM的鲁棒性。

(a) bupa (b) Abalonel (c) Winequality(d) Wilt(e) Parkinsons (f) hepatitis

Figure 1. ROC graphs of some data sets

图1. 部分数据集的ROC曲线

Figure 2. Comparison of robustness of 4 algorithms on sonar

图2. Sonar数据集上4种算法鲁棒性比较

5. 结论

本文针对FMK-LSSVM，提出一种新的隶属度计算方法。该方法以MK-LSSVM中的组合核函数来度量样例间的相似性程度，通过每一样例附近与其相似的同类与异类样例比例的差值来获得该样例的隶属度，并引入到FMK-LSSVM。该隶属度区别于已有的各类隶属度计算方法，其直接以各样例在MK-LSSVM特征空间中的相似性来获得隶属度。LSSVM决策函数同样是在特征空间中构造产生，从而使得该隶属度与LSSVM保持一致性，仿真实验结果也验证了所提方法的有效性。

上述工作虽然取得了一定成果，但仍存在不完善之处，后续相关研究，拟从以下几个方面展开：

1) 模糊隶属度算法中的阈值仍是经验值，后续将进一步研究，设计启发式阈值选取方法，以进一步提高FMK-LSSVM的鲁棒性；

2) 可将线性加权求和的多核模型扩展到局部多核学习模型，使最终的分类器模型进一步利用到样本的信息，提升算法性能。

基金项目

国家自然科学基金(62072024，61473111)；北京市教委一般项目(KM202110016001)；北京建筑大学科学研究基金(KYJJ2017017，Y19-19，Y18-11，PG2021094)；住房和城乡建设部科学技术计划北京建筑大学北京未来城市设计高精尖创新中心开放课题(NO. UDC2019033324，UDC201703332)；北京建筑大学课程建设重点培育项目“高等数学ZDXX202008”。

NOTES

^*通讯作者。