一种支持向量机预处理方法的研究

Research on a Preprocessing Method of Support Vector Machine

摘要: 支持向量机(Support Vector Machine, SVM)在处理大规模数据集时，随着样本维度增高，样本数量增多会出现训练时间显著增多的问题。为了解决该问题，文章提出了一种基于主成分分析(Principal Component Analysis, PCA)和K边界近邻法(K Nearest Bound Neighbor, KNBN)的SVM预处理方法；先用PCA对训练数据降维消除训练数据中的冗余信息，然后利用KNBN预选取训练数据中的支持向量来减少训练数据量。数值实验结果表明，与PCA-SVM、KNBN-SVM和无数据预处理的SVM方法相比，采用本文提出的SVM预处理方法既保持了良好的分类预测精度，又缩短了大量训练时间。

Abstract: When the large-scale data set with higher dimension and larger number of samples is processed by the Support Vector Machine (SVM), the training time will increase significantly. In order to solve this problem, based on Principal Component Analysis (PCA) and K Nearest Bound Neighbor (KNBN), a preprocessing method of SVM is proposed. Firstly, PCA is used to reduce the dimension of the training data to eliminate the redundant information in the training data, and then KNBN is used to preselect the support vectors in the training data to reduce the amount of training data. The numerical experiment results show that SVM preprocessing method proposed in this paper, compared with PCA-SVM, KNBN-SVM and SVM without data preprocessing, can not only keep good classification prediction accuracy, but also save a lot of training time.

1. 引言

支持向量机(Support Vector Machine, SVM)最早在1964年被Vapnik和Cortes等人提出的，它是一个有监督学习的二分类模型 [1] [2] [3]。在上世纪90年代SVM得到快速发展并衍生出一系列改进和扩展的算法。它被广泛应用在人像识别 [4] 和文本分类 [5] 等模式识别问题中。

SVM的学习策略是求解能够将训练数据集按照类别正确划分并且使几何间隔最大化的分离超平面，可转化为求解一个凸二次规划问题 [3]。一般情况下，随着训练样本规模的扩大，即样本维度升高和样本数量增多，会导致SVM的训练时间延长，分类精度可能下降，存储空间也有所增加。如何对SVM数据进行预处理来提高SVM分类效率成为近年来的一个研究热点。

对SVM数据降维消除其中的冗余特征信息，可以起到提高SVM分类精度和减少SVM计算量的效果。PCA通过提取最能代表原始数据本质特征的特征因子来实现数据降维。目前有关PCA和SVM结合方面的研究有很多。2018年，余金澳 [6] 等人提出一种面向方位敏感性的PCA-SVM分类识别方法，与传统的SVM分类方法相比，该方法对SAR图像的地面目标具有较高的分类识别率和运行效率。2018年，Anis Ben Aicha [7] 等人利用PCA提取最关键、最相关的特征，采用SVM作为分类技术，实现正常肿瘤和癌前肿瘤的鉴别，此方法具有较好的敏感性、特异性、精密度和准确性。2019年，汪雯琦 [8] 等人提出基于PCA和SVM分类的跨年龄人脸识别方法，该方法具有速度快和准确度高的优点。2019年，Wang [9] 等人提出基于机器视觉的有色金属报废车辆分离系统的分类算法及运行参数优化研究，其中利用了PCA-SVM使得识别精度较高，计算速度足够快。

SVM的最优分离超平面由只占全体训练数据集一小部分的支持向量来确定 [10]，通过预选取有可能成为支持向量的样本，舍弃非支持向量来减少训练样本数量，进而大幅度缩短SVM训练时间。从几何方面来看，线性可分情况下支持向量主要分布在两类样本的边界上且彼此之间靠的很近的那些样本 [11]，因此可以提取那些异类样本之间离得很近的边界向量作为支持向量候选集，最后将其作为训练样本集进行SVM训练，可以减少计算量，提升训练速度。一些学者在支持向量预选取方面进行了研究。2008年，Zhang [10] 提出基于KNN法的支持向量预选取方法，计算距离每个样本最近的k个样本，若k个样本中至少有一个异类样本，则这k个样本是边界向量。2009年，徐红敏 [11] 等人提出一种支持向量机快速分类算法，在两类样本中选取与每类样本中每个样本最近的异类样本作为边界向量。2013年，胡志军 [12] 等人提出基于距离排序的快速支持向量机分类算法，先计算每类样本与异类样本类中心的距离，再按照距离大小排序选取一定比例的小距离样本作为候选支持向量。2013年，李庆 [13] 等人提出K边界近邻法支持向量预选取方法，在两类样本中选取与每类样本中每个样本最近的k个异类样本作为边界向量。

上述研究是从降低样本的维度方面或是从减少样本数量方面解决问题，比较片面性，不适用于同时维度高和数量多的大规模数据集预处理。为了克服这个问题，本文首先选用PCA对SVM大规模数据集降维，然后用KNBN在降维后的数据集上预选取支持向量得到一个约简集，称该方法为基于PCA和KNBN的SVM预处理方法。该SVM预处理方法能够结合PCA和KNBN的优点，拥有较高的分类预测精度，而且其训练时间大量缩短。

本文接下来第2节是主成分分析法的简介，第3节是K边界近邻法支持向量预选取方法的描述，第4节介绍基于PCA和KNBN的SVM预处理方法，第5节是数值实验结果及比较。

2. 主成分分析法简介

主成分分析的基本原理是将原来变量重新组合成一组新的线性无关的几个变量，同时根据实际需要从中可以取出几个较少的变量尽可能多地反映原来变量的信息的统计方法，即在原有样本的M维空间内，用M个标准正交基进行重新映射，然后选取其中最重要的D个正交基进行保留，而在这D个正交基坐标轴上的坐标值就是原有样本映射到低维后的坐标。设原始样本矩阵为 $X={\left[\begin{array}{cccc}{x}_1& x_2& \cdots & x_N\end{array}\right]}^{\text{T}}$，其中 $x_i\in R^M$，M是样本的维度， $i=1,2,\cdots ,N$，矩阵X是一个N行M列矩阵。

下面是PCA降维的详细步骤：

1) 原始样本中心化，形成矩阵Y。Y中每个元素为：

$y_{ij}=x_{ij}-{\bar{x}}_j\in Y$， (1)

其中 ${\bar{x}}_j$ 是样本各维分量的平均值， $j=1,2,\cdots ,M$，矩阵Y是N行M列矩阵。

2) 计算协方差矩阵R：

$R=\frac{1}{N-1}{Y}^{\text{T}}Y$， (2)

其中 $Y^{\text{T}}$ 是Y的转置矩阵，矩阵R是M行M列矩阵。

3) 求协方差矩阵R的特征值和特征向量，并将特征值按大小进行排序得：

${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_M\ge 0$， (3)

排序之后的特征值对应的特征向量为：

$e_1,e_2,\cdots ,e_M$， (4)

其中 $e_j\in R^M$， $j=1,2,\cdots ,M$。

4) 计算特征值累计贡献率 $\eta$，

$\eta =\frac{{\displaystyle \underset{i=1}{\overset{D}{\sum }}{\lambda }_i}}{{\displaystyle \underset{i=1}{\overset{M}{\sum }}{\lambda }_i}}\times 100\%$， (5)

其中 $0\le \eta \le 100\text{\%}$， $0\le D\le M$，D为正整数。选取使得特征值累计贡献率大于 $\eta$ 时的最小整数D，这时将前D个较大特征值对应的特征向量作为标准正交基矩阵E，

$E=\left[\begin{array}{cccc}{e}_1& e_2& \cdots & e_D\end{array}\right]$， (6)

矩阵E是M行D列矩阵。原始样本在标准正交基下的投影，即降维过后的样本矩阵 $X^{\text{*}}$ 为：

$X^{*}=XE$， (7)

矩阵 $X^{*}$ 是N行D列矩阵，原始样本便从M维降至D维。

3. K边界近邻法支持向量预选取方法简介

K边界近邻法支持向量预选取的基本思想是通过选取距离每个样本最近的k个异类样本来构造支持向量候选集。已知训练样本集分为两类，正类样本 $T_1$ 和负类样本 $T_2$，

$T_1=\left\{x_1^{+},x_2^{+},\cdots ,x_{N_1}^{+}\right\}$， (8)

$T_2=\left\{x_1^{-},x_2^{-},\cdots ,x_{N_2}^{-}\right\}$， (9)

其中 $x_i^{+},x_j^{-}\in R^M$， $i=1,2,\cdots ,N_1$， $j=1,2,\cdots ,N_2$， $N_1$ 是正类样本的个数， $N_2$ 是负类样本的个数，M是样本的维度。

3.1. 样本距离

当两类样本线性可分时，两类样本之间距离可用欧氏距离来表示：

$d\left(x_i^{+},x_j^{-}\right)={\Vert x_i^{+}-x_j^{-}\Vert }_2$， (10)

当两类样本非线性可分时，通过映射函数 $\varphi (\cdot )$ 将原输入空间映射到高维的特征空间中，样本在高维空间中变得线性可分，这时的样本距离被称为非线性距离：

$d\left(x_i^{+},x_j^{-}\right)=\sqrt{K\left(x_i^{+},x_i^{+}\right)-2K\left(x_i^{+},x_j^{-}\right)+K\left(x_j^{-},x_j^{-}\right)}$， (11)

其中 $K\left(\cdot ,\cdot \right)$ 是核函数。高斯核函数是一种常用的核函数：

$K\left(x_i^{+},x_j^{-}\right)=\exp \left(-{\Vert x_i^{+}-x_j^{-}\Vert }^{\text{2}}/2{\sigma }^2\right)$， (12)

其中 $\sigma$ 是一个常数，采用高斯核函数时，非线性距离变为：

$d\left(x_i^{+},x_j^{-}\right)=\sqrt{2-2K\left(x_i^{+},x_j^{-}\right)}$。 (13)

3.2. KNBN支持向量预选取方法

下面是KNBN方法的具体步骤：

1) 从正类样本中选择一个样本，求其与所有负类样本之间的距离，保留最近的k个负类样本，将他们放入边界向量集当中。

2) 返回步骤(1)，直至遍历所有的正类样本截止。

3) 将所有负类样本按照步骤(1)和步骤(2)操作，保留离每个负类样本最近的k个正类样本，将他们也放入支持向量候选集当中。

4) 把上面得到的边界向量集当中的相同样本删去，进行唯一化处理，最终得到支持向量候选集。

如图1所示，其中有两类样本，当 $k=4$ 时使用KNBN支持向量预选取方法得到边界向量集，适当选取k值，边界向量集一定能包含所有的支持向量，这样便构造出一个支持向量候选集。

Figure 1. Diagram of KNBN support vector preselection

图1. KNBN支持向量预选取示意图

4. 基于PCA和KNBN的SVM预处理方法

4.1. 基于PCA和KNBN的SVM预处理方法介绍

根据PCA降维的特征和KNBN支持向量预选取的特性，本文提出基于PCA和KNBN的SVM预处理方法。为了尽可能保存数据的原有结构信息，所以该数据预处理方法先将训练数据集进行PCA降维处理，再把降维过后的训练数据集进行KNBN支持向量预选取，最终得到一个SVM大规模数据集的约简集。本文所提算法的流程图如图2所示。

下面是基于PCA和KNBN的SVM预处理算法的具体描述。

算法：基于PCA和KNBN的SVM预处理算法。

输入：原始训练数据集 $T=\left\{\left(x_1,y_1\right),\left(x_2,y_2\right),\cdots ,\left(x_N,y_N\right)\right\}$，其中 $x_i\in R^M$， $y_i\in \left\{-1,1\right\}$， $i=1,2,\cdots ,N$，PCA的特征值累计贡献率 $\eta$，KNBN的参数值k。

输出：原始训练数据集经PCA和KNBN处理过后的约简集S。

Step 1. 将原始训练数据集T进行PCA降维。

1) 将T去掉类别特征，形成训练样本矩阵X。

2) 根据X构建中心化矩阵Y，Y中的每个元素如式(1)所示。

3) 按照式(2)构建协方差矩阵R。

4) 求协方差矩阵R的特征值及对应的特征项量，并对特征值按照从大到小的顺序进行排序。

5) 按照公式(5)计算特征值累计贡献率 $\eta$，确定D值，将这D个最大特征值对应的特征向量构成新基矩阵E，将训练样本矩阵X乘以E，即可得到降维后训练样本样本矩阵 $X^{*}$，添上正负类别属性后形成降维后的训练数据集 $T^{*}$。

Step 2. 在降维后的训练数据集 $T^{*}$ 进行KNBN支持向量预选取。

1) 将数据集 $T^{*}$ 分为正类数据集 $T_1$ 和负类数据集 $T_2$。

2) 从 $T_1$ 中选取一个样本，求其与所有负类样本间的距离，保留与其最近的k个负类样本作为在正类样本约束下的负类边界向量，直至遍历 $T_1$，形成负类边界向量集 $S_2$。

3) 同样，从 $T_2$ 中选取一个样本，求其与所有正类样本间的距离，保留与其最近的k个正类样本作为在负类样本约束下的正类边界向量，直至遍历 $T_2$，形成正类边界向量集 $S_1$。

4) 将 $S_1$ 和 $S_2$ 合并， $S^{\text{*}}=S_1\cup S_2$，并对 $S^{\text{*}}$ 进行唯一化处理，即删除相同的样本，可得到 $T^{*}$ 的支持向量候选集为S，即得到原始训练数据集T的约简集S。

Figure 2. Flow chart of SVM preprocessing method based on PCA and KNBN

图2. 基于PCA和KNBN的SVM预处理方法流程图

4.2. 算法复杂度分析

设原始训练样本数量为N，样本维度为M， $M<N$。经PCA降维后样本维度为D， $D<M$，样本数量不变，其中正类样本数量为 $N_1$，负类样本数量为 $N_2$， $N_1+N_2=N$ ；降维后的训练样本经KNBN支持向量预选取之后得到的约简集中样本数量为l，一般情况下， $l\ll N$。基于PCA和KNBN的SVM预处理算法复杂度是由PCA，KNBN和约简集进行SVM训练的时间复杂度共同决定的。

1) 该预处理方法Step 1的PCA降维过程中，去掉类别特征形成训练样本矩阵的运算次数可以忽略不计，构建中心化矩阵时需要计算2MN次，计算协方差矩阵时需要运算M²N次，协方差矩阵的特征值分解时需要M³次运算 [14]，构建新基矩阵需要将特征值按大小进行排序，排序 [15] 时需要 $M\log M$ 次运算，计算累计贡献率 $\eta$ 和确定D值需要 $\left(M+3D-2\right)$ 次运算，构造降维后的新矩阵需要进行 $\left(2DMN-DN\right)$ 次运算。综合上述过程，PCA的总运算次数为：

$M^{2}N+2DMN+2MN-DN+M^3+M\log M+M+3D-2$，(14)

其中 $D<M$，则PCA的时间复杂度为 $O\left(M^{2}N\right)$。

2) 该预处理方法Step 2的KNBN支持向量预选取过程中，正负类数据集的分开需要进行N次运算，构造边界向量集这一过程中，对一个正类样本求其与所有负类样本之间距离，通常情况下需使用非线性距离，其中核函数采用高斯核函数，则需要 $\left(3D+9\right)N_2$ 次运算，再将求得的 $N_2$ 个距离进行排序时需要 $N_2\log N_2$ 次运算，直至遍历所有正类样本后截止，则构造负类样本边界向量集需要运算 $\left(N_1{N}_2\log N_2+3D{N}_2+9N_2\right)$ 次，按照上述过程在构造正类样本边界向量集时则需要运算 $\left(N_1{N}_2\log N_1+3D{N}_1+9N_1\right)$ 次，下面唯一化处理过程的运算次数可忽略不计。KNBN过程总运算次数为：

$N_1{N}_2\log N_1{N}_2+\left(3D+9\right)\left(N_1+N_2\right)$， (15)

其中 $N_1+N_2=N$， $N_1{N}_2\le N^2/4$，则KNBN的时间复杂度为 $O\left(N^2\log N\right)$。

3) 一般情况下，标准SVM的时间复杂度 [16] 是 $O\left(N^3\right)$。原始训练样本经PCA-KNBN预处理后的得到的约简集有l个样本，所以约简集进行SVM训练的时间复杂度为 $O\left(l^3\right)$。

综上所得，基于PCA和KNBN的SVM预处理算法复杂度为 $O\left(N^2\log N+M^{2}N+l^3\right)$，所以在某种情况下，如原始训练数据集经过PCA-KNBN处理过后的约简集规模很小时，则SVM训练的时间是可以缩短的。

5. 与现有方法的数值实验

PCA-KNBN-SVM表示基于PCA和KNBN预处理的标准SVM，PCA-SVM [8] 表示只进行PCA降维预处理的标准SVM，KNBN-SVM [13] 表示只进行KNBN支持向量预选取预处理的标准SVM。为了验证基于PCA和KNBN的SVM预处理算法的有效性，将PCA-KNBN-SVM与PCA-SVM，KNBN-SVM和无数据预处理的标准SVM进行比较。实验采用Matlab R2018a，在2.3 GHz，Pentium，Dual CPU，4 GB内存的硬件平台上进行。SVM训练选用Libsvm-3.24函数包，其中核函数采用高斯核函数，取 $\sigma =1.3$。

5.1. 数据介绍

实验采用UCI数据库中的Polish companies bankruptcy data数据集 [17]。该数据集有5个适合二分类的数据样本，分别是1 year，2 year，3 year，4 year和5 year数据，每个数据都有64个特征属性和1个类别属性。每个数据集的训练样本数量和测试样本数量具体情况如表1所示。

Table 1. Polish company bankruptcy data set

表1. 波兰公司破产数据集

5.2. 数值实验

本文分别采用无预处理的标准SVM，PCA-SVM，KNBN-SVM和PCA-KNBN-SVM对5个数据集进行训练和测试，其中KNBN算法中使用的样本距离为非线性距离式(12)所示，其中核函数参数值 $\sigma =1.3$。PCA降维过程中，特征值累计贡献率设置为 $\eta =99.5\text{\%}$，由此确定的5个数据集中的PCA参数值D如表2所示。KNBN支持向量预选取的参数值 [13] 设置为 $k=4$。

Table 2. Numerical experiment parameter value list

表2. 数值实验参数值列表

实验结果记录的是各算法对应各数据集的训练时间和预测准确度。其中训练时间包括数据预处理时间和SVM训练的时间。数值实验结果如表3所示，其中数值结果是100次独立数值实验结果的平均值。

Table 3. List of numerical experiment results

表3. 数值实验结果列表

从表3中可以观察出，各算法在训练时间和分类准确度方面具有差异性，下面对它们进行分析比较。

在训练时间方面，使用PCA-SVM算法对每个数据集进行实验，其训练时间比无数据预处理的标准SVM要低很多，平均低了51%左右；KNBN-SVM算法的训练时间相对于无数据预处理的标准SVM也下降了很多，平均下降41%左右；本文提出的PCA-KNBN-SVM算法训练时间相对于无数据预处理的标准SVM平均下降了86%左右，相对于PCA-SVM平均下降了63%左右，相对于KNBN-SVM平均下降了69%左右。

在分类准确度方面，PCA-SVM算法要比无数据预处理的标准SVM稍高一些，平均高了0.06%左右；KNBN-SVM算法要比无数据预处理的标准SVM偏低一些，平均低了0.13%左右；PCA-KNBN-SVM算法相对于PCA-KNBN平均下降了0.15%左右，相对于KNBN-SVM平均升高了0.18%左右，而相对于无数据预处理的标准SVM在1 year，2 year和3 year数据中有些许降低，但在4 year和5 year数据有些许升高。

综合来看，PCA-KNBN-SVM算法相对于无预处理的SVM，PCA-SVM和KNBN-SVM，其训练时间缩短效果很明显；在分类准确度方面相对于PCA-SVM有所下降，相对于KNBN-SVM却有所提高，而相对于无预处理的SVM在某些数据中分类准确度稍高或稍低一些，总而言之，PCA-KNBN-SVM算法相对于其他算法在训练时间方面缩短效果很明显，而在分类准确度方面变化不大。

6. 结语

本文为了解决SVM在遇到大规模的数据集时出现训练时间增多和分类精度可能下降的问题，提出了一种基于PCA和KNBN的SVM预处理方法。通过选取UCI数据库中的Polish companies bankruptcy data 数据集进行数值实验，从数据实验结果观察得出在该预处理方法下的SVM相对于无预处理的SVM，只进行PCA预处理的SVM和只进行KNBN预处理的SVM有大幅度缩减训练时间的效果，在分类准确度方面相对于其他算法变化不大。结果表明基于PCA和KNBN的SVM预处理方法是可以在保持良好分类精度下提高训练速度的一种SVM预处理好方法。

NOTES

^*第一作者。

^#通讯作者。