(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州310023)

隨著當(dāng)今互聯(lián)網(wǎng)的飛速發(fā)展，與此相關(guān)的數(shù)據(jù)也在不斷增長并表現(xiàn)出新的特點(diǎn)[1]。支持向量機(jī)(Support vector machine)對(duì)數(shù)據(jù)分類有著明顯優(yōu)勢(shì)，通過對(duì)收集的數(shù)據(jù)(包括有標(biāo)簽樣本數(shù)據(jù)和無標(biāo)簽樣本數(shù)據(jù))進(jìn)行學(xué)習(xí)和分類，發(fā)現(xiàn)數(shù)據(jù)樣本中的內(nèi)在信息，根據(jù)這些信息實(shí)現(xiàn)對(duì)未知樣本的預(yù)測(cè)。

支持向量機(jī)(SVM)分類方法因其對(duì)簡單樣本分類精度高、速度快而受到廣泛的關(guān)注。而對(duì)高維樣本進(jìn)行直接分類則存在分類較為困難的情況，因此利用PCA算法對(duì)SVM進(jìn)行改進(jìn)的方法也層出不窮。在PCA-SVM的基礎(chǔ)之上，提出了一種基于局部線性嵌入的SVM增量學(xué)習(xí)算法。通過流形降維方法，對(duì)高維數(shù)據(jù)進(jìn)行特征提取，以簡化分類器訓(xùn)練的復(fù)雜度，在讀入數(shù)據(jù)之后首先對(duì)數(shù)據(jù)進(jìn)行降維處理，隨后再以降維后得到的低維空間數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)送入SVM分類器以實(shí)現(xiàn)初次訓(xùn)練，在后續(xù)增量學(xué)習(xí)的過程，對(duì)新增數(shù)據(jù)利用流形方法降維后，先獲取新增數(shù)據(jù)降維之后在低維空間上的對(duì)應(yīng)數(shù)據(jù)，隨后利用低維空間的SV集尋找SV集附近的新增數(shù)據(jù)，其他距離SV集較遠(yuǎn)的新增數(shù)據(jù)，即可視為對(duì)本次增量訓(xùn)練過程的新SV影響很小的新增數(shù)據(jù)，因此僅將本次增量學(xué)習(xí)需要參與訓(xùn)練的新增數(shù)據(jù)與SV集進(jìn)行增量學(xué)習(xí)過程訓(xùn)練得到新的SV集。

1 算法實(shí)現(xiàn)

1.1 算法描述

降低數(shù)據(jù)維數(shù)的方法主要分為線性降維和非線性降維，其共同特點(diǎn)是從已知樣本數(shù)據(jù)中學(xué)習(xí)到一個(gè)映射矩陣，然后通過與映射矩陣的線性運(yùn)算將樣本降維到低維特征空間之中。線性降維計(jì)算方法較為簡便，降維方法主要包括主成分分析(PCA)[2]、多尺度分析(MDS)[3]和線性判別分析(LDA)[4]。非線性降維主要以等距映射算法(ISOMAP)[5]、局部線性嵌入算法(LLE)[6]為代表。

因PCA降維方法與SVM分類器結(jié)合的過程快速準(zhǔn)確，被廣泛應(yīng)用于SVM分類過程，而基于PCA的改進(jìn)算法也層出不窮。非線性降維方法就是一種可行的方法，可分為全局降維和局部降維兩種，經(jīng)典的全局算法為等距映射(ISOMAP)，而局部線性嵌入(LLE)、拉普拉斯映射(LM)[7]、局部切空間對(duì)準(zhǔn)(LTSA)[8]和黑森特征映射(HE)[9]等都是經(jīng)典的局部算法。

基于PCA-SVM分類過程的特性研究，提出了支持向量機(jī)的LLE-ISVM的增量學(xué)習(xí)方法，并在此基礎(chǔ)上提出了一種利用SV集選取附近新增訓(xùn)練樣本進(jìn)行增量訓(xùn)練的方法。該算法首先對(duì)每一輪當(dāng)前增量訓(xùn)練的訓(xùn)練樣本進(jìn)行LLE降維得到低維特征向量，并在增量訓(xùn)練之前利用低維特征空間SV集對(duì)新增訓(xùn)練樣本進(jìn)行篩選和約減，保留了最有可能成為支持向量的訓(xùn)練樣本集進(jìn)行增量訓(xùn)練，隨后以SV集與篩選后的新增樣本進(jìn)行訓(xùn)練，保證了算法的準(zhǔn)確率以及速率。算法大體流程如圖1所示。

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

1.2 支持向量機(jī)(SVM)原理

支持向量機(jī)[10-11]可以理解為是一個(gè)二分類器，它對(duì)于給定的包含正負(fù)樣本的訓(xùn)練樣本集，尋找出一個(gè)分類超平面，如圖2所示，使得分開的兩個(gè)類別具有最大的分類間隔，即使得分類超平面H和兩類的支持向量H1，H2所組成的超平面距離最大，這樣就得到了一個(gè)對(duì)于給定數(shù)據(jù)樣本的分類超平面H。對(duì)于線性可分問題，可直接利用現(xiàn)有數(shù)據(jù)進(jìn)行分類。而對(duì)于線性不可分問題，則需將數(shù)據(jù)集利用核函數(shù)映射，得到線性可分?jǐn)?shù)據(jù)后再進(jìn)行分類。

圖2 支持向量機(jī)分類超平面Fig.2 Thehyperplane of SVM classifier

假設(shè)現(xiàn)有數(shù)據(jù)集T={(xi,yi)}，i為初始訓(xùn)練集的數(shù)據(jù)點(diǎn)個(gè)數(shù)，xi為數(shù)據(jù)的特征，yi為對(duì)應(yīng)數(shù)據(jù)的標(biāo)簽，取值正樣本為+1，負(fù)樣本為-1。對(duì)于分類超平面而言，其表達(dá)式為

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

因此，最大分類間隔的求解便轉(zhuǎn)化為求取以下最優(yōu)化問題。對(duì)以下問題求解得到最優(yōu)的(w，b)，可得到對(duì)于該訓(xùn)練樣本的分類超平面，即

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

1.3 局部線性嵌入(LLE)

局部線性嵌入和傳統(tǒng)的PCA，LDA等關(guān)注樣本方差的降維方法相比，更關(guān)注降維時(shí)保持樣本局部的線性特征，由于LLE在降維時(shí)保持了樣本的局部特征，它廣泛地被用于圖像識(shí)別、高維數(shù)據(jù)可視化等領(lǐng)域。

LLE算法大致可分為如下步驟：每個(gè)樣本點(diǎn)的k個(gè)近鄰點(diǎn)選擇[13]、構(gòu)造局部重建權(quán)值矩陣、低維嵌入向量計(jì)算。假設(shè)有訓(xùn)練集T={(xi,yi)}，i為初始訓(xùn)練集的數(shù)據(jù)點(diǎn)個(gè)數(shù)，xi為數(shù)據(jù)的特征，yi為對(duì)應(yīng)數(shù)據(jù)的標(biāo)簽，低維空間為d維，計(jì)算步驟為

近鄰點(diǎn)選擇。算法的第一步是計(jì)算出每個(gè)樣本點(diǎn)的k個(gè)近鄰點(diǎn)。把相對(duì)于所求樣本點(diǎn)距離最近的k個(gè)樣本點(diǎn)規(guī)定為所求樣本點(diǎn)的k個(gè)近鄰點(diǎn)。

構(gòu)造局部權(quán)值矩陣W。對(duì)每個(gè)樣本點(diǎn)xi與其k個(gè)近鄰點(diǎn)的局部重建權(quán)值矩陣，求出局部協(xié)方差矩陣，即

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

(4)

定義重構(gòu)誤差，即

(5)

低維嵌入向量計(jì)算。利用局部權(quán)值矩陣將樣本降至低維，通過求解使得降維損失函數(shù)最小化的過程，通常特征值按從小到大排列，選取第2個(gè)到(d+1)個(gè)特征值所對(duì)應(yīng)的特征向量作為輸出結(jié)果。

1.4 算法步驟

假設(shè)初始訓(xùn)練樣本集為A0，新增樣本集為B0，SV集的原數(shù)據(jù)樣本為S01，對(duì)初始樣本降維之后訓(xùn)練得到的SV集為S11，增量學(xué)習(xí)后得到的SV集為S12，新增樣本B0與S01降維后得到B0在低維空間中的對(duì)應(yīng)數(shù)據(jù)集為B1，并將B1與S11比對(duì)篩選之后獲取到低維樣本集T1和對(duì)應(yīng)原樣本集T0。LLE-ISVM算法的詳細(xì)描述為

1) 利用LLE對(duì)A0降維后進(jìn)行SVM訓(xùn)練，得到一個(gè)分類超平面H，原始數(shù)據(jù)SV集S01，低維數(shù)據(jù)SV集為S11。

2) 將S01與新增樣本集B0一同進(jìn)行LLE降維，得到新的低維空間中的原SV集的低維表達(dá)S11(此處已經(jīng)對(duì)S11進(jìn)行更新)和新增樣本的低維表達(dá)B1。

3) 計(jì)算B1到兩個(gè)SV集對(duì)應(yīng)的兩個(gè)超平面H1，H2的距離L1，L2，將保留下列不等式的樣本記為B1t，式中K為一給定的實(shí)數(shù)，即

4) 如果B1t為空集，則本次增量學(xué)習(xí)過程結(jié)束，SV集保持不變，最優(yōu)分類面保持不變，否則，繼續(xù)下一步驟。

5) 將S11和B1t合為一個(gè)訓(xùn)練集進(jìn)行SVM的分類器訓(xùn)練過程，得到新的分類面和新的SV集。

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

2 實(shí)驗(yàn)數(shù)據(jù)及結(jié)論

2.1 測(cè)試數(shù)據(jù)

實(shí)驗(yàn)測(cè)試分別在手寫數(shù)字?jǐn)?shù)據(jù)集MNIST和標(biāo)準(zhǔn)數(shù)據(jù)集Steel，Waveform上進(jìn)行。主要以MNIST數(shù)據(jù)庫來說明，因?yàn)樗惴ㄖ饕轻槍?duì)較大規(guī)模數(shù)據(jù)，一般為非線性，所以采用核函數(shù)(RBF)的SVM分類器，以tic和toc對(duì)測(cè)試過程進(jìn)行計(jì)時(shí)。實(shí)驗(yàn)所使用的PC機(jī)主頻為2.4 GHz，內(nèi)存為4 G，處理器為i5-2430M，所用的軟件為Matlab R2012a。實(shí)驗(yàn)將樣本數(shù)據(jù)集隨機(jī)分成初始樣本集、增量樣本集和測(cè)試集。數(shù)據(jù)集個(gè)數(shù)、特征個(gè)數(shù)和增量詳情如表1所示。

表1 數(shù)據(jù)集和增量參數(shù)Table 1 Dataset and incremental parameters 個(gè)

以MNIST手寫數(shù)據(jù)庫為例作為測(cè)試，選取了其中兩組手寫數(shù)字為“0”和“1”以及“0”和“8”的兩類圖片為例實(shí)現(xiàn)二分類過程，主要以“0”“1”二分類來描述，如圖3所示。

圖3 手寫數(shù)據(jù)庫的“0”和“1”Fig.3 The number “0”and “1” of MNIST dataset

將手寫數(shù)字“0”標(biāo)簽為“-1”，手寫數(shù)字“1”標(biāo)簽為“+1”。一共獲取到9 000張手寫數(shù)字“0”“1”的28×28圖片，將其中2 000張圖像作為初始訓(xùn)練樣本，6 000張作為增量樣本，每次增量選取其中2 000張圖像作為新增樣本集，1 000張用于測(cè)試。圖4為對(duì)所獲取的其中各200張“0”“1”圖像使用LLE降至2維的分布效果圖，圓形與菱形則代表兩類不同的數(shù)據(jù)的低維表示。

圖4 圖像“0”“1”的LLE降維的低維空間分布Fig.4 Low dimensional subspace distribution of LLE

在精度方面，主要將LLE-ISVM方法與其他兩個(gè)方法進(jìn)行比較：一個(gè)是傳統(tǒng)的非增量的支持向量機(jī)(SVM)，另一個(gè)是利用PCA降維的增量SVM方法。對(duì)于MNIST手寫數(shù)據(jù)庫，利用LIBSVM，選取RBF高斯核函數(shù)，多項(xiàng)式核函數(shù)的參數(shù)為3，懲罰函數(shù)為0.5，對(duì)手寫數(shù)字“0”“1”進(jìn)行二分類。對(duì)于純SVM的分類方法，直接對(duì)獲取到的二值化圖像像素值進(jìn)行歸一化，隨后將28×28矩陣按行展開成1×784維的行向量，即以一行作為一個(gè)樣本，將獲取到的8 000張訓(xùn)練樣本轉(zhuǎn)換成8 000×784維的矩陣形式送入SVM進(jìn)行分類。對(duì)于PCA-ISVM而言，利用主成分分析降低至20維，獲取到其前20個(gè)特征值所對(duì)應(yīng)的特征向量，隨后在20維空間上獲取其在該低維空間上的映射，以1×20維的行向量作為一個(gè)樣本數(shù)據(jù)，選取2 000×20維的矩陣作為初次分類訓(xùn)練樣本，隨后將6 000個(gè)增量樣本分3 次進(jìn)行增量訓(xùn)練。對(duì)于LLE-ISVM而言，在LLE降維過程需要選取k個(gè)近鄰點(diǎn)，k設(shè)置為10，同樣降低至20維空間。選取20維作為特征空間得到初始訓(xùn)練集數(shù)據(jù)在20維空間上的LLE映射，對(duì)2 000×20維初始樣本集進(jìn)行初次分類，隨后將6 000×20維的增量訓(xùn)練集進(jìn)行新的LLE映射，與前一次訓(xùn)練所得的SV集進(jìn)行比對(duì)篩選之后，將所得新增訓(xùn)練集與SV集進(jìn)行新的SVM分類器訓(xùn)練。由表2可知：增量學(xué)習(xí)過程能夠提升分類算法的精度。

表2 增量學(xué)習(xí)后的精度對(duì)比

Table 2 The comparison of accuracy after incremental learning

%

為便于對(duì)同一組數(shù)據(jù)分類進(jìn)行對(duì)比，對(duì)MNIST的“0”“1”分類以及“0”“8”分類計(jì)時(shí)，同時(shí)也包括對(duì)圖像的讀取、歸一化、展開成行向量的過程。得到的最終精度和時(shí)間如表3，4所示。

從表3，4可知：由于所選取的測(cè)試數(shù)據(jù)分布規(guī)律較為簡單，因此LLE-ISVM方法和SVM訓(xùn)練方法在精度上差異不大，但LLE-ISVM方法能有效地提高訓(xùn)練的速率。對(duì)比PCA-ISVM過程可以發(fā)現(xiàn)：MNIST數(shù)據(jù)庫的二分類過程中兩種算法訓(xùn)練精度較為接近，速度上LLE-ISVM方法較PCA-ISVM有小幅提升。實(shí)驗(yàn)數(shù)據(jù)表明：LLE-ISVM作為一種類比PCA-ISVM的方法，能較好地適應(yīng)MNIST數(shù)據(jù)的分類，相比SVM有較大提升，同時(shí)在參數(shù)(分類模型、k近鄰個(gè)數(shù)、新增樣本距離SV集的距離等)選取恰當(dāng)時(shí)，在保證訓(xùn)練精度的前提下，LLE-ISVM在訓(xùn)練速度上相比PCA-ISVM有小幅提升。

表3 不同算法分類精度

Table 3 The comparison of different algorithm classification accuracy

%

表4 不同算法訓(xùn)練總時(shí)間Table 4 The time of different algorithms training process s

2.2 測(cè)試結(jié)果

將LLE-ISVM算法應(yīng)用于瓷片表面缺陷檢測(cè)過程，由于所獲得的原始圖像維數(shù)較高，因此首先對(duì)圖像進(jìn)行分割后得到48×48維的分割圖像，選取其中500張圖像進(jìn)行測(cè)試。部分樣例圖片見圖5。

圖5 缺角瓷片和完好瓷片F(xiàn)ig.5 The defective pictures and normal pictures

最終以其中200張圖像進(jìn)行首次訓(xùn)練，200張圖像分4次進(jìn)行增量學(xué)習(xí)過程，其中100張作為測(cè)試圖像。最終得到PCA-ISVM方法正確率為71%，LLE-ISVM方法正確率為75%，雖然LLE方法相對(duì)于PCA降維算法復(fù)雜度較高，但由于該方法對(duì)新增樣本進(jìn)行篩選而非全部樣本進(jìn)行計(jì)算，因此時(shí)間消耗差異不大。但由于LLE分類方法應(yīng)用于瓷片缺陷檢測(cè)過程中時(shí)準(zhǔn)確率較低，目前該算法并不適應(yīng)當(dāng)前環(huán)境的瓷片缺陷檢測(cè)過程，后續(xù)需對(duì)算法進(jìn)行修正并加以提升后才可運(yùn)用于實(shí)際過程。

2.3 實(shí)驗(yàn)結(jié)果分析

1) 通過對(duì)比MNIST數(shù)據(jù)庫的“0”“1”降維效果，PCA與LLE均能對(duì)MNIST數(shù)據(jù)庫的“0”“1”圖像進(jìn)行較好的分離，但LLE的分類效果要優(yōu)于PCA降維。

2) 對(duì)SVM引入增量過程，可以有效地降低訓(xùn)練時(shí)間，同時(shí)對(duì)分類精度有一定的提升。

3) 對(duì)“0”“1”分類和“0”“8”分類進(jìn)行對(duì)比，由于LLE降維過程復(fù)雜度高于PCA，若以新增分類樣本直接進(jìn)行LLE-ISVM訓(xùn)練，訓(xùn)練時(shí)間會(huì)明顯高于PCA-ISVM過程。與PCA降維算法相比，由于LLE降維過程比PCA降維復(fù)雜度高，因此直接使用LLE降維會(huì)使訓(xùn)練時(shí)間變長，而LLE-ISVM選用的對(duì)新增樣本進(jìn)行篩選的策略能有效地提升運(yùn)算速度，因此總體上來看LLE-ISVM對(duì)運(yùn)算速率是有一定提升的。同時(shí)LLE算法對(duì)高維圖像進(jìn)行降維時(shí)能更好地保留圖像的原始特征，因此也能有足夠高的判別準(zhǔn)確率。綜上所述，在維數(shù)較低時(shí)PCA-ISVM與LLE-ISVM大體上均有較好的分類準(zhǔn)確率與速率。

4) 當(dāng)利用LLE-ISVM算法對(duì)較高維度的瓷片圖像進(jìn)行測(cè)試時(shí)，該算法的準(zhǔn)確率比PCA-ISVM要高出4%。在訓(xùn)練時(shí)間基本一致的前提下，LLE-ISVM能較好地處理高維數(shù)據(jù)的分類。由于LLE-ISVM并沒有對(duì)圖像進(jìn)行特征提取，因此所得到的準(zhǔn)確率整體偏低，仍存在訓(xùn)練時(shí)間較長的問題，在對(duì)實(shí)際瓷片缺陷檢測(cè)過程中實(shí)用性較低。因此利用LLE-ISVM對(duì)瓷片圖像進(jìn)行分類的應(yīng)用仍需要改進(jìn)。

3 結(jié) 論

通過對(duì)比實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn)：LLE降維方法對(duì)手寫圖像的簡單降維分類效果要優(yōu)于PCA降維方法，而LLE在計(jì)算復(fù)雜度上相對(duì)于PCA較高，如果對(duì)全部樣本進(jìn)行降維后分類，會(huì)存在耗時(shí)較長的問題，因此引入對(duì)SVM分類器的增量學(xué)習(xí)過程?？梢园l(fā)現(xiàn)LLE-ISVM增量算法對(duì)新增樣本的篩選能有效地降低算法的運(yùn)算時(shí)間，在完成分類過程的同時(shí)有較高的準(zhǔn)確度和速度，能實(shí)現(xiàn)完整增量學(xué)習(xí)過程。由于對(duì)新增樣本點(diǎn)篩選對(duì)算法速度的提升較為有限，其本質(zhì)是由于LLE的計(jì)算復(fù)雜度比PCA高，因此未來計(jì)劃對(duì)LLE降維算法進(jìn)行改進(jìn)，以提升LLE算法的分類精度和計(jì)算速度。由于LLE降維過程能更好地獲取和保留數(shù)據(jù)的原有流形結(jié)構(gòu)，在保證速度的同時(shí)，LLE-ISVM相較于PCA-ISVM方法能更為準(zhǔn)確地實(shí)現(xiàn)磁片表面的缺陷檢測(cè)分類過程。但在實(shí)際的瓷片缺陷分類過程中，由于所獲取數(shù)據(jù)的分類精度較低，暫時(shí)不能用于瓷片缺陷檢測(cè)，算法還待改進(jìn)，筆者所使用的SVM方法是傳統(tǒng)的監(jiān)督學(xué)習(xí)過程，該算法的泛化能力較弱，同時(shí)實(shí)際應(yīng)用之中，更多的是少部分有標(biāo)簽、大部分無標(biāo)簽的數(shù)據(jù)，監(jiān)督學(xué)習(xí)過程是較為低效的，后續(xù)需要采用LLE降維方法對(duì)樣本進(jìn)行篩選，對(duì)樣本進(jìn)行半監(jiān)督學(xué)習(xí)過程，以更好地提升該算法，使之能更好地應(yīng)用于瓷片表面缺陷檢測(cè)過程。