自动化学报  2017, Vol. 43 Issue (1): 132-141   PDF    
一种基于全局代表点的快速最小二乘支持向量机稀疏化算法
马跃峰1, 梁循1, 周小平1     
1. 中国人民大学信息学院 北京 100872
摘要: 非稀疏性是最小二乘支持向量机(Least squares support vector machine,LS-SVM)的主要不足,因此稀疏化是LS-SVM研究的重要内容.在目前LS-SVM稀疏化研究中,多数算法采用的是基于迭代选择的稀疏化策略,但是时间复杂度和稀疏化效果还不够理想.为了进一步改进LS-SVM稀疏化方法的性能,文中提出了一种基于全局代表点选择的快速LS-SVM稀疏化算法(Global-representation-based sparse least squares support vector machine,GRS-LSSVM).在综合考虑数据局部密度和全局离散度的基础上,给出了数据全局代表性指标来评估每个数据的全局代表性.利用该指标,在全部数据中,一次性地选择出其中最具有全局代表性的数据并构成稀疏化后的支持向量集,然后在此基础上求解决策超平面,是该算法的基本思路.该算法对LS-SVM的非迭代稀疏化研究进行了有益的探索.通过与传统的迭代稀疏化方法进行比较,实验表明GRS-LSSVM具有稀疏度高、稳定性好、计算复杂度低的优点.
关键词: 最小二乘支持向量机     稀疏化     全局代表点     局部密度     全局离散度    
A Fast Sparse Algorithm for Least Squares Support Vector Machine Based on Global Representative Points
MA Yue-Feng1, LIANG Xun1, ZHOU Xiao-Ping1     
1. School of Information, Renmin University of China, Beijing 100872
Received: 2015-11-05, Accepted: 2016-05-23.
Foundation Item: Supported by National Natural Science Foundation of China(71531012, 71271211), Natural Science Foundation of Beijing (4132067), Brand Project of Renmin University (10XNI029), E-commerce Research Project of Jingdong Mall (413313012)
Author brief: MA Yue-Feng Ph. D. candidate at the School of Information, Renmin Uni-versity of China. He received his bach-elor degree from Xi0an Jiaotong Univer-sity in 1997. His research interest covers machine learning and pattern recognition.);
ZHOU Xiao-Ping Ph. D. candi-date at the School of Information, Ren-min University of China. He received his bachelor degree from Beijing Infor-mation Science and Technology University in 2006. His re-search interest covers data mining, machine learning, and social computation.
Corresponding author. LIANG Xun Professor at the School of Information, Renmin Uni-versity of China. His research interest covers neural network, big data, and social network. Corresponding author of this paper.
Abstract: For lack of sparseness on least squares support vector machine (LS-SVM), the study on sparsity of LS-SVM is an important topic. Currently, most of the sparse LS-SVM methods are based on the iteration selection strategy. Consequently, they do not perform well in computation complexity and sparsity. To improve the performance of sparse LS-SVM method, a fast method, global-representation-based sparse least squares support vector machine (GRS-LSSVM), is proposed based on the selection of global representative points in this paper. To evaluate datum's representation, an index is given based on local density and global discrete degree. In the algorithm, firstly, the top global representative data are selected from all data in one step using the index to construct the support vector set of sparse LS-SVM, and then the set is used to compute the decision hyperplane of sparse LS-SVM. This algorithm explores the non-iteration on sparse LS-SVM. Experimental results show that the proposed method has higher sparseness degree, more stability, and lower computational complexity than the traditional iteration algorithms.
Key words: Least squares support vector machine (LS-SVM)     sparseness     global representative point     local density     global discrete degree    

分类问题是机器学习的一个主要领域,其目标是通过对于给定数据集的学习,获得能够对未来数据进行有效分类的分类器 [1]. 基于不同的构造思路,已经有很多分类学习方法得到了深入的研究和广泛的应用,如贝叶斯方法、决策树方法、神经网络等.其中,支持向量机(Support vector machine,SVM) [2] 作为其中比较好的分类方法,得到了广泛的关注和应用. SVM将数据空间的数据通过映射到高维的特征空间,并在特征空间里面利用超平面作为决策平面,因此具有了稀疏性、效率高、准确性高等特点 [1-3].

最小二乘支持向量机(Least squares support vector machine,LS-SVM) [4]作为SVM的一种主要变形,通过将SVM中的罚函数替换为二次函数并将约 束条件转化为等式约束,使得LS-SVM的解可以通过求解一个线性系统来得到,简化了求解过程.实验表明,LS-SVM在实际应用中具有和SVM相类似的泛化能力,因此在很多领域取得广泛的应用 [5]. 但是,随着训练集数据量的增加,LS-SVM的弱点也越来越突出地表现出来.由于LS-SVM的支持向量几乎包含了全 部训练集的数据,随着数据量的增加,计算用时也会大量增加,从而限制了LS-SVM的进一步应用.因此,对LS-SVM进行支持向量数量的消减,继续保持SVMs的稀疏性特征,是LS-SVM适应新的要求必须要研究的问题 [6-8].

在LS-SVM稀疏化的研究中,基于迭代过程形成稀疏LS-SVM的支持向量集是目前研究的主要思路,可以分为删除式稀疏化方法和增量式稀疏化方法. 2000年,Suykens 等 [6]首先利用删除式稀疏化方法对LS-SVM进行稀疏化.在稀疏化过程中,每一步将支持向量集中最靠近当前决策超平面的若干个支持向量进行消减. 但是由于每次都要根据当前支持向量集进行求解线性系统,因此,在数据量较大的时候,其计算复杂性会非常高.随后,Suykens等 [7]在支持向量的选择中不仅考虑了LS-SVM模型的最优化,同时考虑了泛化能力. 在文献 [8]中,选择被消减支持向量的准则变为寻找并消减具有最小偏差的点,进一步提高了消减后的准确性. Hoegaerts等 [9]在文献[6]的基础上提出了一种轻量级变种稀疏化算法并改进了原算法的性能. 文献 [10] 在序列最小优化求解LS-SVM算法基础上,在每一步迭代中,将影响对偶目标函数值最小的数据点进行消减,从而达到稀疏化的目标. Carvalho等 [11]给出了一个两阶段消减算法,在已知LS-SVM决策超平面的前提下,利用碎片化指标度量每个支持向量的可消减性,进而进行稀疏化. de Brabanter等 [12]使用基于熵核频带宽度选择策略和快速交叉验证方法,对LS-SVM进行消减. Kars-makers等 [13]利用过决定线性系统的稀疏共轭方向寻踪稀疏化方法来对LS-SVM进行支持向量集的消减并取得了良好的效果. Lopez等 [14]在文献 [15]对$L_0$范式进行迭代优化的基础上,将分类LS-SVM和回归LS-SVM都统一在一个稀疏化算法中. Liu等 [16]和Wei等 [17]在引入适应性Lp LS-SVM的基础上,用进化算法对其求解以实现LS-SVM的稀疏化.增量式稀疏化LS-SVM的研究也出现了许多成果. Jiao等 [18]在建立基于核的支持向量词典基础上,每次都将一个基本支持向量加入到支持向量集合中,在控制计算复杂度的前提下取得了良好的效果. Zhao等 [19]在假设后增加支持向量不影响当前支持向量的前提下,构造了一个增量式LS-SVM稀疏化算法,从空集开始,每一次都将剩余数据点中使得目标函数增长最少的点作为支持向量加入支持向量集中. Yang等 [20]利用迭代方法,在尽量保持信息不损失的情况下,交替使用增加和减少支持向量数量的方法,达到对LS-SVM的稀疏化的目标. Zhao等 [21]在文献[19]的基础上考虑到支持向量集变化对非支持向量的影响,通过重新计算剩余数据点对目标函数下降的贡献,选择其中使得目标函数下降最大的数据点进入支持向量集.除了传统稀疏化方法以外,数据压缩传感理论也被应用到了LS-SVM 的稀疏化上. Yang等 [22]提出了使用正交匹配追踪算法对训练数据集进行压缩,从而实现LS-SVM 的稀疏化. Yang等 [23]在上述研究的基础上,用非随机矩阵代替原有的随机高斯矩阵,进一步提高了算法的效率.从目前的研究来看,基于迭代的算法依然是主要研究的方向,但是存在计算复杂性较高,在数据量大的时候,其表现不能满足实际要求的情况.综上所述,LS-SVM的稀疏化是从原来几乎包含所有训练数据点的支持向量集中选择若干数据点,并通过计算使得基于选择数据点的决策超平面具有类似于未稀疏化LS-SVM的泛化能力. 因此,LS-SVM的稀疏化可以看作是数据点抽取并求解近似决策超平面的过程.基于数据 点抽取的思路,在本文中我们给出了一种非迭代的LS-SVM稀疏化方法.

在本文中,我们首先给出了基于支持向量数量约束的LS-SVM稀疏化优化模型.在此基础上,提出基于数据特征空间全局代表性的支持向量集非迭代选择策略,并提出了基于全局代表点的LS-SVM稀疏化算法(Global-representation-based sparse least squares support vector machine,GRS-LSSVM).该算法的主要思路是,首先计算特征空间中数据点之间的距离,在此基础上计算每个数据点的全局代表性,然后按照给定的稀疏化后LS-SVM支持向量集的数量约束,一次性选择最具代表性的数据点并构成稀疏化后的支持向量集,最后在该支持向量集的基础上,求得稀疏化后的LS-SVM的决策超平面.实验表明,GRS-LSSVM具有稀疏度高、稳定性好、计算复杂度低等优点.

本文下文组织如下:首先,对LS-SVM的相关模型进行回顾和总结;其次,给出基于全局代表性的稀疏化算法;然后,给出相关算法的实验结果,并对结果进行分析;最后,对本文加以总结,并进一步提出工作的方向.

1 LS-SVM 模型

LS-SVM是在SVM的基础上通过改变其罚函数而得到的.简单起见,设$({ x},y)$,$x \in {R^d}$ 为给定的一个数据及其标号或者函数值,如果是标号,对应的就是分类问题,如果是函数值,对应的就是回归问题. N个已知数据形成的集合$X=\{{ x}_i\}$$Y=\{y_i\}$共同构成了训练集. SVM的目标是通过对训练集的学习,获得如下形式的决策超平面:

$f( x):\quad { \omega}^{\rm T}\cdot\phi({ x})+b=0 $ (1)

其中,$\phi (\cdot)$是从Rd到特征空间$H$的映射函数,ω是特征空间中的一个向量,b是一个实数. LS-SVM通过求解如下优化模型得到决策超平面:

$\matrix{ {\mathop {\min }\limits_{\omega ,b,e} {\rm{ }}J = {1 \over 2}{{\left\| \omega \right\|}^2} + {C \over 2}\sum\limits_{i = 1}^N {e_i^2} } \hfill \cr {s.t.{\omega ^{\rm{T}}} \cdot \phi ({x_i}) + b = {y_i} - {e_i},i = 1, \cdots ,N} \hfill \cr } $ (2)

其中,C是惩罚参数.

通过构造式(2)所对应的拉格朗日函数,并根据KKT (Karush-Kuhn-Tucker)条件,可得下式:

$\omega = \mathop \sum \limits_{i = 1}^N {\alpha _i}\phi ({x_i})$ (3)
$\left[ {\matrix{ {K\left( {X,Y} \right)} & {\overline 1 } \cr {{{\overline 1 }^T}} & 0 \cr } } \right]\left[ \matrix{ \alpha \hfill \cr b \hfill \cr} \right] = \left[ \matrix{ Y \hfill \cr 0 \hfill \cr} \right]$ (4)

其中$K(\Omega ,\Lambda ) = {[k({x_i},{x_j})]_{|\Omega | \times |\Lambda |}},{x_i} \in \Omega ,{x_j} \in \Lambda ,k( \cdot , \cdot )$是预先确定的核函数,1=(1,…,1)N×1,IN阶单位矩阵.

由式(4)可以看出,决策超平面的系数通过求解线性系统获得,并且,求得的决策超平面是式(2)的最优解.因此,相对于SVM,LS-SVM的求解比较简单.但是,由于几乎全部αi都不为零,LS-SVM也失去了SVMs的稀疏性.在实际应用中,LS-SVM的非稀疏性妨碍了其进一步的应用和推广.因此,对LS-SVM进行稀疏化是扩展LS-SVM应用的必然选择.

2 基于全局代表性的 LS-SVM稀疏化算法

LS-SVM稀疏化是在尽可能保持LS-SVM原有泛化能力的前提下,将大量支持向量进行消减的过程.在本节讨论基于全局代表性的非迭代稀疏化算法.

2.1 LS-SVM 稀疏化模型

LS-SVM稀疏化的目标就是用如下函数g(x)代替f(x)并尽量保持原有决策超平面的性质:

$g({ x}): \overline{{ \omega}}^{\rm T}\cdot\phi({ x})+b=y $ (5)

其中$\overline{{ \omega}}=\sum_{i=1}^L\beta_i\phi({ s}_i)$,${s_i} \in X,L < N$,L是稀疏化后支持向量的个数.

$S=\{{ s}_1,\cdots,{ s}_L\}$为稀疏化后LS-SVM的支持向量集.由于通过式(4)求解的决策超平面f(x)是式(2)的最优解.因此,在给定稀疏化后支持向量个数L的前提下,用g(x)代替f(x)进行LS-SVM稀疏化的优化模型为如下形式:

$\eqalign{ & \mathop {\min }\limits_S \quad {J_g} - {J_f} \cr & s.t.|S| \le L,\quad S \subset X \cr} $ (6)

其中,JfJg分别表示用f(x)g(x)作为决策超平面时的J函数值.

由于Jf为一定值,因此,式(6)等价于如下模型:

$\begin{align} & {{\min }_{S}}\quad {{J}_{g}} \\ & s.t.\quad |S|\le L,\quad S\subset X \\ \end{align}$ (7)

其中,目标函数经过整理并省略常数部分后可得如下形式:

$\eqalign{ & {J_g} = {1 \over 2}{\left\| {\bar \omega } \right\|^2} + {C \over 2}\sum\limits_{i = 1}^N {{{({y_i} - {{\bar \omega }^{\rm{T}}} \cdot \phi ({x_i}) - b)}^2}} = \cr & {1 \over 2}({\beta ^{\rm{T}}}K(S,S)\beta ) + \cr & {C \over 2}\sum\limits_{i = 1} N ({\mu ^{\rm{T}}}\left[ \matrix{ K(S,{x_i})K({x_i},S){\rm{ }}K(S,{x_i}) \hfill \cr K({x_i},S){\rm{ 1}} \hfill \cr} \right]\mu - \left[ {2{y_i}K({x_i},S{\rm{ }}2{y_i})} \right]\mu ) = \cr & {1 \over 2}{\mu ^{\rm{T}}}A\mu - B\mu \cr} $ (8)

其中

$A = \left[ {\matrix{ {K(S,S)(1 + C\sum\limits_{i = 1}^N k ({x_i},{x_i})} & {C\sum\limits_{i = 1}^N K (S,{x_i})} \cr {C\sum\limits_{i = 1}^N K ({x_i},S)} & {CN} \cr } } \right]$ (9)
$B=\left[ \begin{align} & C\sum\limits_{i=1}^{N}{{{y}_{i}}}K(S,{{x}_{i}}) \\ & \sum\limits_{i=1}^{N}{C{{y}_{i}}} \\ \end{align} \right]$ (10)
$\mu =\left[ \begin{matrix} \begin{align} & \beta \\ & b \\ \end{align} \\ \end{matrix} \right]$ (11)

S确定时,式(7)在如下情况下达到最小值:

$\mu ={{A}^{-1}}B$ (12)

由上面的讨论可知,对于任意给定的一组向量S,只要S使得式(9)满秩,则存在唯一的一组系数值为式(8)的最优解.因此,选择S集合是LS-SVM进行稀疏化的根本问题.

2.2 基于全局代表性的 S 集选取

由于从X中选取S集的问题是一个组合优化问题,很难找到全局最优解. 因此,当给定L的前提下,我们希望通过对LS-SVM特征进行分析,得到一种快速S集合选取方法.为了方便讨论,我们首先给出密度和离散度的定义.

由于在特征空间中,任意两点间的距离可以通过下式进行计算:

$d({{x}_{1}},{{x}_{2}})=\sqrt{k({{x}_{1}},{{x}_{1}})+k({{x}_{2}},{{x}_{2}})-2k({{x}_{1}},{{x}_{2}})}$ (13)

数据点x的密度大小可以用数据点特定邻域内点的个数来进行衡量.

定义 1  (数据密度). 特征空间中任一点xθ邻域内的密度ρ定义为:

$\rho =\sum\limits_{j=1}^{N}{\delta }(d(x,{{x}_{j}}))$ (14)

其中

$\delta (z)=\left\{ \begin{array}{*{35}{l}} \begin{align} & 1,\quad z\le \theta \\ & 0,\quad 其他 \\ \end{align} \\ \end{array} \right.$ (15)

数据点x的离散度大小ζ采用文献[24]的相关公式进行衡量.

定义 2 (离散度). 任一点xi的离散度ζ定义为该点到比该点密度更大的其他点的最小距离,即:

${\zeta _i} = \mathop {\min }\limits_{{\rho _{{x_i}}} < {\rho _{{x_j}}}} d({x_i},{x_j}),\forall {x_j} \in X$ (16)

可以看出,两个指标中,密度具有局部性,离散度具有全局性.下面给出利用这两个指标对数据集进行LS-SVM消减的基本思路.

图 1给出了利用密度和离散度进行LS-SVM稀疏化的支持向量集选择示意图. 其中,图 1 (a)为原始LS-SVM的决策超平面f(x)(图中细实线)及两个类中心超平面(f(x)=+1及 f(x)=-1,图中长划线),图 1 (b)为稀疏化后LS-SVM的决策超平面g(x) (图中点划线)及两个类中心超平面(g(x)=+1及g(x)=-1,图中双点划线).由于决策超平面由两个类中心超平面决定,因此,只要找到可以确定两个中心超平面的数据点并将其纳入到S集合中,就可以实现LS-SVM的稀疏化.由于稀疏化后需要的支持向量数量比较少,因此将高密度点作为支持向量可以使得类中心超平面的定位更具有精确性.所以,尽量选取高密度点(如黑色数据点)进入S集合是很合理的思路.但是,若仅考虑密度,则容易造成集中在某个高密度区域的点(如灰色点)大量进入S集合从而使得S集合丧失全局性.与之对应,如果选取密度虽然较小但是在离散度上更大的点(如条纹点)代替灰色点,就能够使得稀疏化后的决策超平面更接近原始超平面.因此,同时考虑密度和离散度是选择S集合元素的关键依据.若将同时具有高密度和离散度的点称为全局代表点,则选择全局代表点作为S集合元素的算法是本文的主要贡献之一.

图 1 稀疏化LS-SVM的支持向量选择示意图 Figure 1 Description of support vector selection of sparse LS-SVM

若将ρζ看作两个维度,那么全部数据在该二维空间中主要分布在3块区域. 图 2给出了一个二维数据在ρ-ζ空间中的分布示意图. 其中,图 2 (a)表示的是数据在原始空间中的分布,图 2 (b)表示的是数据在ρ-ζ 空间中的分布.明显地,分布在I区的数据点的特征是密度和离散度都比较大,是具有全局代表性的数据点.分布在II区的数据点的特征是密度很小离散度很高,一般是离群点或者是噪声点.在III区的数据点,其特征是密度比较高,但是离散度较低,一般是在全局代表性点附近的点.因此,合理划分3个区域并且尽量将I区的数据点选择出来作为S集是下面要讨论的问题.

图 2 全局代表性数据点 Figure 2 Description of global representative data

图 2可以看出,全局代表性点比较稀疏,可以采用离群点发现算法进行获取. 但是,相应算法的时间复杂性较高,很难适应大数据量的要求.为此,我们通过设计全局代表性指标τ来进行全局代表点的选取.

由于ρζ的单位不同,因此首先进行归一化处理,即将ρζ映射到预先给定的区间 $[\eta_{\min},\eta_{\max}] (\eta_{\min},\eta_{\max}>0)$,并设映射后的值为 ρζ.则任一点xi 的全局代表性指标τi 可以按照如下两式之一进行计算:

${{\tau }_{i}}=\min ({{{\bar{\rho }}}_{i}},{{{\bar{\zeta }}}_{i}})$ (17)
${{\tau }_{i}}={{{\bar{\rho }}}_{i}}\times {{{\bar{\zeta }}}_{i}}$ (18)

可知,τi越大,对应的xi的全局代表性就越高.在此基础上,我们给出全局代表点选取算法(Global representative point selection,GFPS),具体过程描述如算法1所示.

算法 1. GFPS

输入:数据集X,核函数k,阈值θ,数量L;

输出:选出的代表点集合S;

1) 根据式(13)计算$d({ x}_i,{ x}_j)$;

2) 根据式(14),(16)计算ρ,ζ;

3) 归一化ρ,ζ;

4) 根据式(17)或(18)计算τ;

5) 按照从大到小对τ排序;

6) 取前L个数据形成S;

7) return S.

可以看出,算法GFPS的计算过程是一个非迭代过程,其主要过程包括3个顺序步骤:一是计算特征空间中任意两个点之间的距离,时间复杂度为${\rm O}(N^2)$;二是计算每个点的ρζ,时间复杂度为${\rm O}(N^2)$;三是对序列τ进行排序,并一次性地抽取序列中最前面L个数据点形成支持向量集,在使用快速排序等较快的排序算法的情况下,其时间复杂度是${\rm O}(N{\rm log}N)$.因此,算法GFPS的时间复杂度是${\rm O}(N^2)$.

2.3 GRS-LSSVM 算法

在分类问题的LS-SVM稀疏化过程中,由于各类数据的分布差异较大,为了防止出现S集中仅包含某一类数据的情况,我们按照训练集全部数据的类别比例来分配S集合中各类代表点的数量.具体计算公式如下:

$L_i=\max(1,\text{round}(L\times \frac{N_i}{N})) $ (19)

其中,Li表示第i类数据中选择的代表点的数量,$\text{round}(\cdot)$表示四舍五入函数,Ni表示第i类数据的数量,N表示全体训练集的数量.

综合上面的讨论,我们给出基于全局代表性点选取的LS-SVM消减算法,具体过程描述如 算法2所示.

算法 2. GRS-LSSVM

输入:训练集X,Y,参数C,核函数k,阈值θ+,θ-,稀疏化后的支持向量集的大小L;

输出:消减后的支持向量集S,对应的系数β,b;

1) 根据式(19)计算两类数据点在S集中的数据量L+,L-;

2) $S_+=\text{GFPS}(X_+,k,L_+,\theta_+)$;

3) $S_-=\text{GFPS}(X_-,k,L_-,\theta_-)$;

4)$S=S_+\cup S_-$ ;

5) 根据式(12)计算β,b;

6) return S,β,b.}

算法2中,X+,X-分别是训练集中属于正负类的数据集,θ+,θ-是分别用于正负类的距离阈值.明显地,虽然GRS-LSSVM算法没有采用迭代方式来构造S集合,但随着L的增加,S集合包含的重要数据点的数量将逐步增加最终包含全部数据点从而收敛于LS-SVM.

从计算复杂度来看,该算法的主体是2次GFPS算法的调用和1次求解支持向量系数.由上述分析知,GFPS算法的时间复杂度为${\rm O}(N^2)$.求解支持向量系数主要是进行1次矩阵逆计算,时间复杂度是${\rm O}(L^3)$. 由于L<<N,这部分的计算对总体时间复杂度的影响很小,可以忽略不计.因此,GRS-LSSVM算法的总体时间复杂度为${\rm O}(N^2)$.

3 实验结果及分析

为了测试本文提出的算法性能,我们利用UCI中的真实数据集对各种算法进行测试并对结果进行分析.

3.1 数据集的选取

我们使用表 1中来自UCI (University of California Irvine machine learning repository)的4个数据集作为实验分析的数据集.这4个数据集的数据都来自真实数据,具有实际应用背景.其中,由于LR数据集包含多类数据,因此在本文中,采用一对多的分类方式,取字母B作为一类,其他数据作为另一类进行测试.

表 1 数据集描述表 Table 1 Description of datasets
3.2 评价指标

在分析对照的指标上,我们选择运行时间(Time)和错误率(Error ratio)作为算法性能的衡量指标.其中,运行时间是指全部计算数据加载入内 存到算法给出稀疏化后的支持向量集S及对应的系数βb的时间跨度,单位为秒(s).错误率是指分类错误的数据 数量占全部数据量的百分比,在本文中采用10- 折交叉确认误差来进行衡量.稀疏度也是衡量一个算法的重要指标,其定义为稀疏化后的支持向量的个数与训练集大小的比值.当训练集大小固定时,稀疏度和文中使用的稀疏化后保留的支持向量的个数L具有等价性.因此,为了方便比较不同算法在各种稀疏度要求下的性能,将L作为算法的控制参数对各个算法进行试验测试.

3.3 对照算法

在本文的实验中,我们使用SLS-SVM (Sparse LS-SVM) [6]和RR-LSSVR (Recursive reduced least squares support vector regression) [12]以及ISLS-SVM (Iterative sparse LS-SVM) [14]作为对照算法. 同时,为了进一步分析算法的特点,我们使用SVM及LS-SVM作为稀疏支持向量机及非稀疏支持向量机的基准算法,进行对照分析. 其中,SLS-SVM算法中每一步消减的支持向量的数量设为1 %,RR-LSSVR中ε=0.00001.

3.4 实验设计

为了正确衡量各个算法的性能,对所有数据集都采用了10- 折交叉验证方法进行测试. 核函数采用RBF kernel.各个参数针对不同的算法进行了优化调整,以便比较不同算法在最优情况下的性能特点.由于每个数据集包含的数据量相差很大,同时考虑到计算机的内存容量限制及对照方便,在将数据集划分为训练集和测试集后,从训练集中按照等概率原则抽取预定数量的数据形成计算时的训练集.其中,BCW的预定数量为500,BA为1 000,MK为2 000,LR为4 000.针对每一个数据集都进行10次10- 折交叉验证并使用各个指标的平均值作为结果进行对比.

全部算法在Matlab 2010a环境中编程实现,并运行在一台内存为4 GB,CPU为i5 3270的机器上.

3.5 实验结果分析

图 3给出了不同算法在不同数据集上的错误率,图 4给出了错误率的标准差,图 5是各个算法的运行时间结果,由于各个算法的时间差异比较大,为了能够显示在一张图中,我们使用了对数坐标,图 6是每个算法运行时间的标准差.在各图中,(a) ~ (d)分别对应数据集BCW、BA、MK和LR.

图 3 错误率比较 Figure 3 Comparison of error ratio
图 4 错误率标准方差比较 Figure 4 Comparison of standard deviation of error ratio
图 5 运行时间比较 Figure 5 Comparison of run time
图 6 运行时间标准方差比较 Figure 6 Comparison of standard deviation of run time

SVM和LS-SVM在各个数据集上的实验结果如表 2所示,其中NS是指算法获得的决策超平面包含的支持向量的个数.从表 2可知,SVM和LS-SVM的泛化能力基本相同,对于同一数据集的错误率基本保持一致.在运行时间上虽然LS-SVM比SVM略长,但是基本还保持在同一数量级.但是,支持向量个数差别很大,LS-SVM包含了训练集的全部向量,SVM包含的支持向量的个数相对比较稀疏.虽然SVM具有稀疏性,但是稀疏度也基本维持在20 %至40 %左右.

表 2 SVM和LS-SVM结果 Table 2 Results of SVM and LS-SVM

首先,从稀疏度来看各个算法的特征. SLS-SVM,RR-LSSVR以及GRS-LSSVM都可以根据给定的L进行稀疏化,使得稀疏化后的支持向量的个数达到任意指定的值. 但是ISLS-SVM不具有这种能力,当给定的L小于某一阈值时,该算法不能给出结果.换句话说,ISLS-SVM具有最大稀疏度限制,该限制使得该算法在稀疏度要求比较高的情况下不能使用.观察算法到达稳定错误率时所需要的稀疏度大小,一般来讲,其需要的稀疏度大小为GRS-LSSVM < ISLS-SVM < SLS-SVM < RR-LSSVR.这说明GRS-LSSVM在一个非常小的稀疏度要求时就可以达到其稳定状态,即该算法稳定时的稀疏度阈值要小于其他算法.在实际应用中给定的稀疏度要求非常高的情况下,该算法能最先达到其稳定值.虽然该算法在稳定时的错误率并不是最小,但是其错误率的大小也已经在一个可以接受的范围内.这表明,GRS-LSSVM算法的稀疏化能力比较出色.在很多的实际应用中,对于错误率的要求不是那么强烈,但是对于稀疏化后的支持向量集的大小要求比较高,这种情况下,尤其是要求稀疏度特别大的情况下,其他算法往往不能胜任,而GRS-LSSVM还可以满足要求.出现这种情况的原因在于,该算法选取的是最具有全局代表性的数据点作为支持向量,即便稀疏度要求比较高,由于选择的点具有全局代表性,因此依然能够达到较好的效果.

其次,从错误率方面来看各个算法的特征.全部算法首先表现出几个共同的特征.首先,当给定的支持向量的个数达到某个阈值时,全部算法都能下降到一个非常低的接近LS-SVM的错误率水平.其次,在达到该阈值后,即便支持向量的个数增加,每个算法在错误率上也没有很大的提高,并保持在一个非常稳定的错误率上.最后,错误率标准差的变化和错误率的变化相类似,在达到并超过阈值后,将维持在一个非常小的范围内并保持稳定. 在未达到稳定值之前,SLS-SVM的错误率最高,RR-LSSVR次之,GRS-LSSVM最小,且比较接近稳定值.这表明即便要求的稀疏度高于算法的稀疏度阈值,GRS-LSSVM也可以提供具有相对较好错误率的决策函数. ISLS-SVM由于在高稀疏度下不能计算,所以不参与比较.当达到稳定值后,4个算法的错误率的排序一般保持SLS-SVM < ISLS-SVM < GRS-LSSVM < RR-LSSVR.虽然GRS-LSSVM的错误率不是最低,但是其错误率也已经接近LS-SVM的错误率,并且和其他算法的错误率相差不大.总体来讲,当稀疏度要求比较低的时候,该算法在错误率的表现上并不突出,但是当稀疏度要求比较高时,尤其是稀疏度要求的值不能满足其他算法达到稳定性值的情况下,该算法达到的错误率要比其他方法要好.原因在于GRS-LSSVM用最具有全局代表性的数据点构成支持向量集,在稀疏度高的情况下,可以通过较少的数据点来达到相对较好的分类效果,但是在达到稳定后,新增的节点对其决策超平面的改变贡献会很小,所以相比较其他算法,效果相对稍弱.

最后,从计算复杂性上来进行分析.明显的,4个算法的表现完全不同. SLS-SVM总体上呈现出随稀疏度下降,计算时间缓慢降低的趋势.原因是SLS-SVM采用的是向量消去方法,稀疏度下降,说明最终的支持向量集包含的向量数量比较多,被消减的向量比较少.因此,所需要的计算时间也会减少. RR-LSSVR的计算时间随着稀疏度的下降,时间呈爆炸式增长.原因在于RR-LSSVR采用的是增量式稀疏化模式,由于每次只能向支持向量集添加一个向量,导致其计算复杂度随着训练集的增长而增长,同时,稀疏度的下降,也导致其计算复杂度的增长. 对于ISLS-SVM,其计算时间会随着稀疏度的下降而降低,其主要原因是该算法本质上是一种删除式稀疏化方法,在稀疏度要求比较高的时候,需要删除的向量数量比较大,这样迭代的次数会比较多,同时,在迭代中矩阵运算出现奇异矩阵的可能性也比较大,这些都会让运算时间比较长. 对于GRS-LSSVM,其运算时间表现出3个特征: 1)在训练集固定的情况下,其运算时间并没有随稀疏度的变化而发生变化; 2)不同数据集的数据量虽然差别很大,但是,该算法的运算时间并没有巨大的变化; 3)该算法的时间稳定性比较好,计算时间的标准差比较小.具有这3个特征的原因在于该 算法没有采用迭代方式进行支持向量的选择,而是在计算出全部数据点的全局代表性值后,一 次性地根据代表性的大小选择支持向量集,因此其计算时间会比较短.

4 总结

在本文中,我们针对LS-SVM稀疏化问题,提出了一种基于全局代表点提取的稀疏化算法. 该算法的思想是通过数据点的局部密度和全局分布性来确定数据的代表性,然后按照代表性的大小直接选择稀疏化后的支持向量,并在这些支持向量的基础上计算稀 疏化后的决策超平面.由于不需要迭代选择支持向量,因此,该方法具有计算复杂性低、 性能稳定、稀疏度高等特点.对LS-SVM稀疏化研究提供了新的思路.实验研究也证明了该算法的特点.

参考文献
1 Han J W, Kamber M, Pei J. Data Mining:Concepts and Techniques (Third edition). San Francisco: Morgan Kaufmann, 2011: 327-330.
2 Vapnik V N. Statistical Learning Theory. New York:Wiley, 1998. 421-426
3 Theodoridis S, Koutroumbas K. Pattern Recognition (Forth edition). San Diego: Academic Press, 2008: 81-90.
4 Suykens J A K, Vandewalle J. Least squares support vector machine classifiers. Neural Processing Letters, 1999, 9 (3): 293–300. DOI:10.1023/A:1018628609742
5 van Gestel T, Suykens J A K, Baesens B, Viaene S, Vanthienen J, Dedene G, de Moor B, Vandewalle J. Benchmarking least squares support vector machine classifiers. Machine Learning, 2004, 54 (1): 5–32. DOI:10.1023/B:MACH.0000008082.80494.e0
6 Suykens J A K, Lukas L, Vandewalle J. Sparse approximation using least squares support vector machines. In:Proceedings of the 2000 IEEE International Symposium on Circuits and Systems. Geneva, Switzerland:IEEE, 2000. 757-760
7 Suykens J A K, De Brabanter J, Lukas L, Vandewalle J. Weighted least squares support vector machines:robustness and sparse approximation. Neurocomputing, 2002, 48 (1-4): 85–105. DOI:10.1016/S0925-2312(01)00644-0
8 de Kruif B J, de Vries T J A. Pruning error minimization in least squares support vector machines. IEEE Transactions on Neural Networks, 2003, 14 (3): 696–702. DOI:10.1109/TNN.2003.810597
9 Hoegaerts L, Suykens J A K, Vandewalle J, de Moor B. A comparison of pruning algorithms for sparse least squares support vector machines. In:Proceedings of the 11th International Conference on Neural Information Processing:Springer. Calcutta, India, 2004. 1247-1253
10 Zeng X Y, Chen X W. SMO-based pruning methods for sparse least squares support vector machines. IEEE Transactions on Neural Networks, 2005, 16 (6): 1541–1546. DOI:10.1109/TNN.2005.852239
11 Carvalho B P R, Braga A P. IP-LSSVM:a two-step sparse classifier. Pattern Recognition Letters, 2009, 30 (16): 1507–1515. DOI:10.1016/j.patrec.2009.07.022
12 12de Brabanter K, deBrabanter J, SuykensJ A K, deMoor B. Optimized fixed-size kernel models for large data sets. Computational Statistics and Data Analysis, 2010, 54 (6): 1484–1504.
13 Karsmakers P, Pelckmans K, de Brabanter K, van Hamme H, Suykens J A K. Sparse conjugate directions pursuit with application to fixed-size kernel models. Machine Learning, 2011, 85 (1-2): 109–148. DOI:10.1007/s10994-011-5253-8
14 López J, De Brabanter K, Dorronsoro J R, Suykens J A K. Sparse LS-SVMs with L0-norm minimization. In:Proceedings of the 19th European Symposium on Artificial Neural Networks. Bruges, Belgium, 2011. 189-194
15 Huang K Z, Zheng D N, Sun J, Hotta Y, Fujimoto K, Naoi S. Sparse learning for support vector classification. Pattern Recognition Letters, 2010, 31 (13): 1944–1951. DOI:10.1016/j.patrec.2010.06.017
16 Liu J L, Li J P, Xu W X, Shi Y. A weighted L_q adaptive least squares support vector machine classifiers--robust and sparse approximation. Expert Systems with Applications, 2011, 38 (3): 2253–2259. DOI:10.1016/j.eswa.2010.08.013
17 Wei L W, Chen Z Y, Li J P. Evolution strategies based adaptive L_p LS-SVM. Information Sciences, 2011, 181 (14): 3000–3016. DOI:10.1016/j.ins.2011.02.029
18 Jiao L C, Bo L F, Wang L. Fast sparse approximation for least squares support vector machine. IEEE Transactions on Neural Networks, 2007, 18 (3): 685–697. DOI:10.1109/TNN.2006.889500
19 Zhao Y P, Sun J G. Recursive reduced least squares support vector regression. Pattern Recognition, 2009, 42 (5): 837–842. DOI:10.1016/j.patcog.2008.09.028
20 Yang X W, Lu J, Zhang G Q. Adaptive pruning algorithm for least squares support vector machine classifier. Soft Computing, 2010, 14 (7): 667–680. DOI:10.1007/s00500-009-0434-0
21 Zhao Y P, Sun J G, Du Z H, Zhang Z A, Zhang Y C, Zhang H B. An improved recursive reduced least squares support vector regression. Neurocomputing, 2012, 87 : 1–9. DOI:10.1016/j.neucom.2012.01.015
22 Yang J, Bouzerdoum A, Phung S L. A training algorithm for sparse LS-SVM using compressive sampling. In:Proceedings of the 2010 International Conference on Acoustics, Speech and Signal Processing. Dallas, Texas, USA:IEEE, 2010. 2054-2057
23 Yang L X, Yang S Y, Zhang R, Jin H H. Sparse least square support vector machine via coupled compressive pruning. Neurocomputing, 2014, 131 : 77–86. DOI:10.1016/j.neucom.2013.10.038
24 Rodriguez A, Laio A. Clustering by fast search and find of density peaks. Science, 2014, 344 (6191): 1492–1496. DOI:10.1126/science.1242072