APP下载

一种基于局部线性嵌入的SVM增量学习方法

2019-05-13

浙江工业大学学报 2019年3期
关键词:超平面降维增量

(浙江工业大学 信息工程学院,浙江 杭州310023)

随着当今互联网的飞速发展,与此相关的数据也在不断增长并表现出新的特点[1]。支持向量机(Support vector machine)对数据分类有着明显优势,通过对收集的数据(包括有标签样本数据和无标签样本数据)进行学习和分类,发现数据样本中的内在信息,根据这些信息实现对未知样本的预测。

支持向量机(SVM)分类方法因其对简单样本分类精度高、速度快而受到广泛的关注。而对高维样本进行直接分类则存在分类较为困难的情况,因此利用PCA算法对SVM进行改进的方法也层出不穷。在PCA-SVM的基础之上,提出了一种基于局部线性嵌入的SVM增量学习算法。通过流形降维方法,对高维数据进行特征提取,以简化分类器训练的复杂度,在读入数据之后首先对数据进行降维处理,随后再以降维后得到的低维空间数据作为训练数据送入SVM分类器以实现初次训练,在后续增量学习的过程,对新增数据利用流形方法降维后,先获取新增数据降维之后在低维空间上的对应数据,随后利用低维空间的SV集寻找SV集附近的新增数据,其他距离SV集较远的新增数据,即可视为对本次增量训练过程的新SV影响很小的新增数据,因此仅将本次增量学习需要参与训练的新增数据与SV集进行增量学习过程训练得到新的SV集。

1 算法实现

1.1 算法描述

降低数据维数的方法主要分为线性降维和非线性降维,其共同特点是从已知样本数据中学习到一个映射矩阵,然后通过与映射矩阵的线性运算将样本降维到低维特征空间之中。线性降维计算方法较为简便,降维方法主要包括主成分分析(PCA)[2]、多尺度分析(MDS)[3]和线性判别分析(LDA)[4]。非线性降维主要以等距映射算法(ISOMAP)[5]、局部线性嵌入算法(LLE)[6]为代表。

因PCA降维方法与SVM分类器结合的过程快速准确,被广泛应用于SVM分类过程,而基于PCA的改进算法也层出不穷。非线性降维方法就是一种可行的方法,可分为全局降维和局部降维两种,经典的全局算法为等距映射(ISOMAP),而局部线性嵌入(LLE)、拉普拉斯映射(LM)[7]、局部切空间对准(LTSA)[8]和黑森特征映射(HE)[9]等都是经典的局部算法。

基于PCA-SVM分类过程的特性研究,提出了支持向量机的LLE-ISVM的增量学习方法,并在此基础上提出了一种利用SV集选取附近新增训练样本进行增量训练的方法。该算法首先对每一轮当前增量训练的训练样本进行LLE降维得到低维特征向量,并在增量训练之前利用低维特征空间SV集对新增训练样本进行筛选和约减,保留了最有可能成为支持向量的训练样本集进行增量训练,随后以SV集与筛选后的新增样本进行训练,保证了算法的准确率以及速率。算法大体流程如图1所示。

图1 LLE-ISVM算法流程Fig.1 The algorithm of LLE-ISVM

1.2 支持向量机(SVM)原理

支持向量机[10-11]可以理解为是一个二分类器,它对于给定的包含正负样本的训练样本集,寻找出一个分类超平面,如图2所示,使得分开的两个类别具有最大的分类间隔,即使得分类超平面H和两类的支持向量H1,H2所组成的超平面距离最大,这样就得到了一个对于给定数据样本的分类超平面H。对于线性可分问题,可直接利用现有数据进行分类。而对于线性不可分问题,则需将数据集利用核函数映射,得到线性可分数据后再进行分类。

图2 支持向量机分类超平面Fig.2 Thehyperplane of SVM classifier

假设现有数据集T={(xi,yi)},i为初始训练集的数据点个数,xi为数据的特征,yi为对应数据的标签,取值正样本为+1,负样本为-1。对于分类超平面而言,其表达式为

H:g(x)=wTx+b=0

(1)

H1:y=wTx+b=1

(2)

H2:y=wTx+b=-1

(3)

其中:w为分类超平面的法向量;b为分类超平面的偏置[12]。

wTxi+b≥+1,yi=+1

wTxi+b≤-1,yi=-1

因此,最大分类间隔的求解便转化为求取以下最优化问题。对以下问题求解得到最优的(w,b),可得到对于该训练样本的分类超平面,即

Subject towTxi+b≥+1yi=+1
wTxi+b≤-1yi=-1

1.3 局部线性嵌入(LLE)

局部线性嵌入和传统的PCA,LDA等关注样本方差的降维方法相比,更关注降维时保持样本局部的线性特征,由于LLE在降维时保持了样本的局部特征,它广泛地被用于图像识别、高维数据可视化等领域。

LLE算法大致可分为如下步骤:每个样本点的k个近邻点选择[13]、构造局部重建权值矩阵、低维嵌入向量计算。假设有训练集T={(xi,yi)},i为初始训练集的数据点个数,xi为数据的特征,yi为对应数据的标签,低维空间为d维,计算步骤为

近邻点选择。算法的第一步是计算出每个样本点的k个近邻点。把相对于所求样本点距离最近的k个样本点规定为所求样本点的k个近邻点。

构造局部权值矩阵W。对每个样本点xi与其k个近邻点的局部重建权值矩阵,求出局部协方差矩阵,即

Zi=(xi-xj)T(xi-xj)

(4)

定义重构误差,即

(5)

低维嵌入向量计算。利用局部权值矩阵将样本降至低维,通过求解使得降维损失函数最小化的过程,通常特征值按从小到大排列,选取第2个到(d+1)个特征值所对应的特征向量作为输出结果。

1.4 算法步骤

假设初始训练样本集为A0,新增样本集为B0,SV集的原数据样本为S01,对初始样本降维之后训练得到的SV集为S11,增量学习后得到的SV集为S12,新增样本B0与S01降维后得到B0在低维空间中的对应数据集为B1,并将B1与S11比对筛选之后获取到低维样本集T1和对应原样本集T0。LLE-ISVM算法的详细描述为

1) 利用LLE对A0降维后进行SVM训练,得到一个分类超平面H,原始数据SV集S01,低维数据SV集为S11。

2) 将S01与新增样本集B0一同进行LLE降维,得到新的低维空间中的原SV集的低维表达S11(此处已经对S11进行更新)和新增样本的低维表达B1。

3) 计算B1到两个SV集对应的两个超平面H1,H2的距离L1,L2,将保留下列不等式的样本记为B1t,式中K为一给定的实数,即

4) 如果B1t为空集,则本次增量学习过程结束,SV集保持不变,最优分类面保持不变,否则,继续下一步骤。

5) 将S11和B1t合为一个训练集进行SVM的分类器训练过程,得到新的分类面和新的SV集。

6) 更新支持向量集S01,得到新的分类超平面。

2 实验数据及结论

2.1 测试数据

实验测试分别在手写数字数据集MNIST和标准数据集Steel,Waveform上进行。主要以MNIST数据库来说明,因为算法主要是针对较大规模数据,一般为非线性,所以采用核函数(RBF)的SVM分类器,以tic和toc对测试过程进行计时。实验所使用的PC机主频为2.4 GHz,内存为4 G,处理器为i5-2430M,所用的软件为Matlab R2012a。实验将样本数据集随机分成初始样本集、增量样本集和测试集。数据集个数、特征个数和增量详情如表1所示。

表1 数据集和增量参数Table 1 Dataset and incremental parameters 个

以MNIST手写数据库为例作为测试,选取了其中两组手写数字为“0”和“1”以及“0”和“8”的两类图片为例实现二分类过程,主要以“0”“1”二分类来描述,如图3所示。

图3 手写数据库的“0”和“1”Fig.3 The number “0”and “1” of MNIST dataset

将手写数字“0”标签为“-1”,手写数字“1”标签为“+1”。一共获取到9 000张手写数字“0”“1”的28×28图片,将其中2 000张图像作为初始训练样本,6 000张作为增量样本,每次增量选取其中2 000张图像作为新增样本集,1 000张用于测试。图4为对所获取的其中各200张“0”“1”图像使用LLE降至2维的分布效果图,圆形与菱形则代表两类不同的数据的低维表示。

图4 图像“0”“1”的LLE降维的低维空间分布Fig.4 Low dimensional subspace distribution of LLE

在精度方面,主要将LLE-ISVM方法与其他两个方法进行比较:一个是传统的非增量的支持向量机(SVM),另一个是利用PCA降维的增量SVM方法。对于MNIST手写数据库,利用LIBSVM,选取RBF高斯核函数,多项式核函数的参数为3,惩罚函数为0.5,对手写数字“0”“1”进行二分类。对于纯SVM的分类方法,直接对获取到的二值化图像像素值进行归一化,随后将28×28矩阵按行展开成1×784维的行向量,即以一行作为一个样本,将获取到的8 000张训练样本转换成8 000×784维的矩阵形式送入SVM进行分类。对于PCA-ISVM而言,利用主成分分析降低至20维,获取到其前20个特征值所对应的特征向量,随后在20维空间上获取其在该低维空间上的映射,以1×20维的行向量作为一个样本数据,选取2 000×20维的矩阵作为初次分类训练样本,随后将6 000个增量样本分3 次进行增量训练。对于LLE-ISVM而言,在LLE降维过程需要选取k个近邻点,k设置为10,同样降低至20维空间。选取20维作为特征空间得到初始训练集数据在20维空间上的LLE映射,对2 000×20维初始样本集进行初次分类,随后将6 000×20维的增量训练集进行新的LLE映射,与前一次训练所得的SV集进行比对筛选之后,将所得新增训练集与SV集进行新的SVM分类器训练。由表2可知:增量学习过程能够提升分类算法的精度。

表2 增量学习后的精度对比

Table 2 The comparison of accuracy after incremental learning

%

为便于对同一组数据分类进行对比,对MNIST的“0”“1”分类以及“0”“8”分类计时,同时也包括对图像的读取、归一化、展开成行向量的过程。得到的最终精度和时间如表3,4所示。

从表3,4可知:由于所选取的测试数据分布规律较为简单,因此LLE-ISVM方法和SVM训练方法在精度上差异不大,但LLE-ISVM方法能有效地提高训练的速率。对比PCA-ISVM过程可以发现:MNIST数据库的二分类过程中两种算法训练精度较为接近,速度上LLE-ISVM方法较PCA-ISVM有小幅提升。实验数据表明:LLE-ISVM作为一种类比PCA-ISVM的方法,能较好地适应MNIST数据的分类,相比SVM有较大提升,同时在参数(分类模型、k近邻个数、新增样本距离SV集的距离等)选取恰当时,在保证训练精度的前提下,LLE-ISVM在训练速度上相比PCA-ISVM有小幅提升。

表3 不同算法分类精度

Table 3 The comparison of different algorithm classification accuracy

%

表4 不同算法训练总时间Table 4 The time of different algorithms training process s

2.2 测试结果

将LLE-ISVM算法应用于瓷片表面缺陷检测过程,由于所获得的原始图像维数较高,因此首先对图像进行分割后得到48×48维的分割图像,选取其中500张图像进行测试。部分样例图片见图5。

图5 缺角瓷片和完好瓷片Fig.5 The defective pictures and normal pictures

最终以其中200张图像进行首次训练,200张图像分4次进行增量学习过程,其中100张作为测试图像。最终得到PCA-ISVM方法正确率为71%,LLE-ISVM方法正确率为75%,虽然LLE方法相对于PCA降维算法复杂度较高,但由于该方法对新增样本进行筛选而非全部样本进行计算,因此时间消耗差异不大。但由于LLE分类方法应用于瓷片缺陷检测过程中时准确率较低,目前该算法并不适应当前环境的瓷片缺陷检测过程,后续需对算法进行修正并加以提升后才可运用于实际过程。

2.3 实验结果分析

1) 通过对比MNIST数据库的“0”“1”降维效果,PCA与LLE均能对MNIST数据库的“0”“1”图像进行较好的分离,但LLE的分类效果要优于PCA降维。

2) 对SVM引入增量过程,可以有效地降低训练时间,同时对分类精度有一定的提升。

3) 对“0”“1”分类和“0”“8”分类进行对比,由于LLE降维过程复杂度高于PCA,若以新增分类样本直接进行LLE-ISVM训练,训练时间会明显高于PCA-ISVM过程。与PCA降维算法相比,由于LLE降维过程比PCA降维复杂度高,因此直接使用LLE降维会使训练时间变长,而LLE-ISVM选用的对新增样本进行筛选的策略能有效地提升运算速度,因此总体上来看LLE-ISVM对运算速率是有一定提升的。同时LLE算法对高维图像进行降维时能更好地保留图像的原始特征,因此也能有足够高的判别准确率。综上所述,在维数较低时PCA-ISVM与LLE-ISVM大体上均有较好的分类准确率与速率。

4) 当利用LLE-ISVM算法对较高维度的瓷片图像进行测试时,该算法的准确率比PCA-ISVM要高出4%。在训练时间基本一致的前提下,LLE-ISVM能较好地处理高维数据的分类。由于LLE-ISVM并没有对图像进行特征提取,因此所得到的准确率整体偏低,仍存在训练时间较长的问题,在对实际瓷片缺陷检测过程中实用性较低。因此利用LLE-ISVM对瓷片图像进行分类的应用仍需要改进。

3 结 论

通过对比实验数据可以发现:LLE降维方法对手写图像的简单降维分类效果要优于PCA降维方法,而LLE在计算复杂度上相对于PCA较高,如果对全部样本进行降维后分类,会存在耗时较长的问题,因此引入对SVM分类器的增量学习过程。可以发现LLE-ISVM增量算法对新增样本的筛选能有效地降低算法的运算时间,在完成分类过程的同时有较高的准确度和速度,能实现完整增量学习过程。由于对新增样本点筛选对算法速度的提升较为有限,其本质是由于LLE的计算复杂度比PCA高,因此未来计划对LLE降维算法进行改进,以提升LLE算法的分类精度和计算速度。由于LLE降维过程能更好地获取和保留数据的原有流形结构,在保证速度的同时,LLE-ISVM相较于PCA-ISVM方法能更为准确地实现磁片表面的缺陷检测分类过程。但在实际的瓷片缺陷分类过程中,由于所获取数据的分类精度较低,暂时不能用于瓷片缺陷检测,算法还待改进,笔者所使用的SVM方法是传统的监督学习过程,该算法的泛化能力较弱,同时实际应用之中,更多的是少部分有标签、大部分无标签的数据,监督学习过程是较为低效的,后续需要采用LLE降维方法对样本进行筛选,对样本进行半监督学习过程,以更好地提升该算法,使之能更好地应用于瓷片表面缺陷检测过程。

猜你喜欢

超平面降维增量
混动成为降维打击的实力 东风风神皓极
一种改进的多分类孪生支持向量机
导弹增量式自适应容错控制系统设计
提质和增量之间的“辩证”
基于非线性核的SVM模型可视化策略
有限维Banach空间中完备集的构造
全现款操作,年增量1千万!这家GMP渔药厂为何这么牛?
Helicobacter pylori-induced inflammation masks the underlying presence of low-grade dysplasia on gastric lesions
降维打击
特大城市快递垃圾增量占垃圾增量93%