勢(shì)函數(shù)聚類的優(yōu)化下采樣SVM分類方法

聞 輝， 賈冬順，嚴(yán) 濤，陳德禮，林元模

(1.莆田學(xué)院 信息工程學(xué)院，福建 莆田 351100； 2.東方地球物理公司 遼河物探處，遼寧 盤錦 124010)

0 引言

支持向量機(jī)(Support Vector Machine,SVM)[1-4]是一種核機(jī)器學(xué)習(xí)算法，在工業(yè)診斷、圖像識(shí)別、醫(yī)療診斷等領(lǐng)域均有非常廣泛的應(yīng)用。通過(guò)使用核技巧和邊緣最大化準(zhǔn)則， SVM可以建立最優(yōu)的決策曲面，在解決小樣本學(xué)習(xí)以及高維模式識(shí)別等方面表現(xiàn)出了優(yōu)越的網(wǎng)絡(luò)泛化性能。然而，由于SVM的訓(xùn)練是一個(gè)二次規(guī)劃(Quadratic Program, QP)問(wèn)題，其訓(xùn)練計(jì)算量與訓(xùn)練樣本的個(gè)數(shù)呈指數(shù)關(guān)系，這導(dǎo)致其在大樣本集下的訓(xùn)練過(guò)程非常耗時(shí)。

為改善大樣本SVM的訓(xùn)練效率問(wèn)題，Vapnik[5]提出基于分塊的SVM優(yōu)化算法，通過(guò)分解大規(guī)模的QP問(wèn)題以逐次排除非支持向量，降低訓(xùn)練過(guò)程中的存儲(chǔ)要求，然而當(dāng)支持向量的個(gè)數(shù)較多時(shí)，分塊的數(shù)據(jù)量也會(huì)增大，從而影響算法的訓(xùn)練速度。Osuna等[6]在分塊SVM算法的基礎(chǔ)上提出基于分解的SVM算法，通過(guò)迭代選取工作集的方式將QP問(wèn)題分解成若干較小規(guī)模的QP問(wèn)題，該算法所選取的工作集的優(yōu)劣直接影響算法的收斂性能。序貫最小優(yōu)化算法(Sequential Minimum Optimization, SMO)[7]所選取的工作集每次只有2個(gè)樣本，通過(guò)啟發(fā)式的嵌套循環(huán)來(lái)尋找待優(yōu)化樣本，但是在最優(yōu)條件的判別上計(jì)算代價(jià)過(guò)高。劉等[8]提出將原始樣本空間劃分為不同子集后與并行SVM算法相結(jié)合，但不同的子集劃分對(duì)SVM的泛化能力仍會(huì)產(chǎn)生一定影響。與以上方法不同，下采樣SVM分類方法直接從訓(xùn)練樣本集的角度出發(fā)，通過(guò)從原始樣本集中抽取或聚類選擇具有一定代表性的樣本來(lái)降低訓(xùn)練樣本的規(guī)模，從而提升SVM的訓(xùn)練效率。隨機(jī)下采樣SVM方法[9]與聚類SVM方法[10-12]是兩種典型的下采樣SVM方法，隨機(jī)下采樣SVM方法的不足在于當(dāng)采樣個(gè)數(shù)較少時(shí)，采樣的隨機(jī)性導(dǎo)致所獲取的樣本往往不能反映原始樣本集的空間分布特征；聚類SVM方法將訓(xùn)練樣本聚類所得的聚類中心作為SVM新的訓(xùn)練集，該方法的聚類個(gè)數(shù)需要預(yù)先確定，盡管可以極大程度降低訓(xùn)練樣本集的規(guī)模，但是這些聚類中心往往會(huì)改變?cè)加?xùn)練集合的空間結(jié)構(gòu)分布，學(xué)習(xí)器的泛化能力也會(huì)受到影響。文獻(xiàn)[13-15]提出的粒度SVM模型(Granular SVM, GSVM)將粒度計(jì)算和SVM相結(jié)合，通過(guò)粒劃分的方式來(lái)獲取具有代表性的信息粒，再在這些信息粒上進(jìn)行學(xué)習(xí)，以獲取最終的決策函數(shù)。該方法在SVM的訓(xùn)練效率方面有顯著改善，但是所劃分的數(shù)據(jù)?？赡軐?dǎo)致數(shù)據(jù)分布的差異，降低了學(xué)習(xí)器的泛化能力。為改善這一不足，郭虎升等[16]提出基于粒度偏移因子的SVM(GSVM based on Shift parameter, S_GSVM)學(xué)習(xí)算法，通過(guò)在核空間中對(duì)映射所得樣本進(jìn)行粒劃分，計(jì)算出不同的超平面偏移因子,以重新構(gòu)造SVM的凸二次優(yōu)化問(wèn)題；程鳳偉等[17]提出基于近鄰傳輸?shù)牧６萐VM(GSVM based on Affinity Propagation,APG_SVM)算法，將k近鄰算法用于篩選訓(xùn)練樣本集，再結(jié)合粒樣本混合度及粒中心到超平面的距離對(duì)訓(xùn)練集進(jìn)行優(yōu)化篩選，這些方法在有效改善SVM訓(xùn)練效率的同時(shí)，也在不同程度上改善了GSVM的泛化能力。

基于以上研究，本文提出一種勢(shì)函數(shù)聚類的優(yōu)化下采樣SVM分類方法。與已有聚類SVM方法不同，本文所提勢(shì)函數(shù)聚類方式所得的下采樣集合直接來(lái)源于原始的訓(xùn)練集，并未改變?cè)紭颖炯系姆植冀Y(jié)構(gòu)。通過(guò)對(duì)原始樣本空間不同區(qū)域的樣本進(jìn)行密度度量，有效地將樣本空間的全局分布信息利用起來(lái)，并建立不同參數(shù)的高斯核完成對(duì)樣本空間不同區(qū)域的有效覆蓋，每次覆蓋增量生成一個(gè)采樣樣本，在樣本空間的不同局部區(qū)域可以挑選出具有代表性的訓(xùn)練樣本集合。相對(duì)于原始訓(xùn)練樣本集合，所得樣本集合規(guī)模極大降低。按照這種方式，所篩選出的訓(xùn)練樣本集合可以根據(jù)樣本空間的分布情況自適應(yīng)確定，克服了隨機(jī)采樣SVM方法中樣本采樣不足導(dǎo)致的樣本空間結(jié)構(gòu)失真問(wèn)題，可以以相對(duì)少量的訓(xùn)練樣本來(lái)逼近原始樣本空間結(jié)構(gòu)分布。而且，該方式可以根據(jù)樣本空間分布來(lái)自動(dòng)確定聚類個(gè)數(shù)，克服了聚類SVM方法中的聚類個(gè)數(shù)需要手動(dòng)調(diào)整和聚類子空間覆蓋范圍尺度不一致的問(wèn)題。相對(duì)于GSVM，本文所提勢(shì)函數(shù)聚類方式所得的下采樣集合來(lái)源于原始樣本空間的各個(gè)局部子區(qū)域，在生成下采樣集合的過(guò)程中，將樣本空間的全局分布信息和局部區(qū)域信息結(jié)合在一起，有效地克服了數(shù)據(jù)分布的差異性，從而保證了學(xué)習(xí)器的泛化能力。

但是，相對(duì)于原始樣本集所直接訓(xùn)練出的SVM決策曲面，由于下采樣特性引起的樣本空間稀疏性問(wèn)題，可能導(dǎo)致下采樣訓(xùn)練所得的SVM分類邊界仍然會(huì)有一定程度的偏離。為改善這一不足，本文將所提優(yōu)化下采樣方法所建立起的訓(xùn)練集用于初始的SVM訓(xùn)練，在以相對(duì)少數(shù)量的訓(xùn)練樣本來(lái)逼近原始樣本空間結(jié)構(gòu)分布的前提下，通過(guò)下采樣方法訓(xùn)練所得SVM的決策曲面上尋找原始訓(xùn)練集中邊界附近的樣本，以此作為二次訓(xùn)練樣本集合，隨后來(lái)訓(xùn)練出一個(gè)新的SVM分類器。

為驗(yàn)證本文所提方法的特性，分別在人工數(shù)據(jù)集及基準(zhǔn)數(shù)據(jù)集上與其他方法進(jìn)行了實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)表明，在大樣本數(shù)據(jù)集分類問(wèn)題上，本文方法在有效提升SVM訓(xùn)練效率的同時(shí)，可以保證良好的泛化性能。

1 SVM算法原理

(1)

式中:優(yōu)化所得的非零拉格朗日乘子αi對(duì)應(yīng)的樣本項(xiàng)稱為支持向量;C為選定的正參數(shù)。該方法可以通過(guò)將輸入樣本x非線性映射到高維特征空間φ(x)進(jìn)行拓展。然后使用如下核技巧：

K(xi,x)=φ(xi)T·φ(x)。

(2)

相應(yīng)的SVM決策邊界可以通過(guò)下式來(lái)實(shí)現(xiàn)：

(3)

式中Ns為支持向量的個(gè)數(shù)。

2 勢(shì)函數(shù)密度聚類的優(yōu)化下采樣SVM方法

本文所提方法的一個(gè)關(guān)鍵任務(wù)是如何實(shí)現(xiàn)對(duì)原始訓(xùn)練樣本集的下采樣優(yōu)化選取，這里所提的下采樣指的是從原始樣本集中抽取或聚類選擇具有一定代表性的樣本，以達(dá)到訓(xùn)練樣本規(guī)模的降低。

2.1 算法實(shí)現(xiàn)原理

為了能有效降低原始訓(xùn)練樣本集的規(guī)模并保證SVM的分類性能，本文首先使用勢(shì)函數(shù)密度聚類的方式從原始的訓(xùn)練樣本集中篩選出新的樣本集合，以此構(gòu)造下采樣訓(xùn)練集來(lái)訓(xùn)練SVM分類器。在此基礎(chǔ)上，尋找分類器邊界的錯(cuò)分樣本及距離邊界較近的樣本點(diǎn)，以此構(gòu)成二次訓(xùn)練樣本集合來(lái)訓(xùn)練出一個(gè)新的SVM分類器。

勢(shì)函數(shù)[18]反映的是空間中兩個(gè)向量隨距離變化的影響程度。設(shè)x，y分別表示模式空間的兩個(gè)向量，γ(x,y)表示由這兩個(gè)向量建立的勢(shì)函數(shù)。根據(jù)文獻(xiàn)[18]的描述，一類常用的勢(shì)函數(shù)模型給定如下：

(4)

式中：T為常數(shù)，可以視為距離加權(quán)因子；d(x,y)表示x與y之間的距離。

借助勢(shì)函數(shù)的定義，本文將勢(shì)函數(shù)的數(shù)學(xué)模型引入訓(xùn)練樣本空間，設(shè)計(jì)了勢(shì)函數(shù)密度聚類的學(xué)習(xí)機(jī)制以實(shí)現(xiàn)對(duì)訓(xùn)練樣本空間的密度度量，然后將聚類所得各個(gè)中心樣本作為下采樣所得的SVM訓(xùn)練樣本集合，這一過(guò)程主要通過(guò)建立不同參數(shù)的高斯核對(duì)樣本空間進(jìn)行覆蓋來(lái)完成。每一次覆蓋增量生成一個(gè)采樣樣本，依照該方式來(lái)完成對(duì)原始樣本空間不同區(qū)域樣本的抽取。為提高樣本空間不同區(qū)域覆蓋的準(zhǔn)確性，在本文所提利用勢(shì)函數(shù)來(lái)度量樣本空間區(qū)域的密度的過(guò)程中，考慮訓(xùn)練樣本集的標(biāo)簽信息，即樣本勢(shì)值的度量是以訓(xùn)練集中的相同模式類別樣本集合為基礎(chǔ)來(lái)完成的。

(5)

其中u,v=1,2,…Ni且u≠v

(6)

(7)

v=1,2,…Ni,v≠p。

(8)

(9)

則為尋找下一個(gè)具有代表性的訓(xùn)練樣本做好準(zhǔn)備，其中δ為閾值。通過(guò)這種方式逐次完成對(duì)Si所在樣本空間的有效覆蓋；否則，轉(zhuǎn)向?qū)W習(xí)其他的模式類別，直到所有模式類別學(xué)習(xí)完畢，并最終構(gòu)建新的訓(xùn)練樣本集合S′。

以上所提勢(shì)函數(shù)密度聚類來(lái)增量構(gòu)建下采樣訓(xùn)練集的過(guò)程中，考慮每一類樣本的標(biāo)簽信息，通過(guò)統(tǒng)計(jì)樣本空間中每個(gè)樣本點(diǎn)的勢(shì)值，可以建立各樣本的勢(shì)值度量，其中勢(shì)值較大的樣本點(diǎn)所在的樣本區(qū)域較為密集，反之較為稀疏，以此視為對(duì)樣本空間的密度聚類學(xué)習(xí)。這種勢(shì)值的度量考慮到了當(dāng)前樣本與其他樣本之間的距離信息，可以將訓(xùn)練樣本空間的全局分布信息有效利用起來(lái)。通過(guò)將學(xué)習(xí)所得的最大勢(shì)值所對(duì)應(yīng)的樣本作為各個(gè)高斯核的中心，可以建立不同參數(shù)的高斯核完成對(duì)樣本空間不同區(qū)域的有效覆蓋，每一次覆蓋對(duì)應(yīng)生成一個(gè)相應(yīng)的下采樣樣本?？紤]到高斯核具有良好的局部特性，該下采樣樣本可以視為在原始樣本空間中某個(gè)局部區(qū)域的表征；同時(shí)，建立起相應(yīng)的勢(shì)值更新機(jī)制，以消除被某個(gè)已建立起的高斯核所覆蓋區(qū)域的樣本勢(shì)值，為生成下一個(gè)下采樣樣本做準(zhǔn)備。按照該方式，本文所提方法可以根據(jù)原始樣本空間的分布情況自適應(yīng)生成下采樣樣本集，這些生成的下采樣樣本直接來(lái)自于原始樣本空間各個(gè)不同的局部區(qū)域，可以有效逼近原始樣本空間的結(jié)構(gòu)分布，從而確保了學(xué)習(xí)器的泛化能力。設(shè)初始訓(xùn)練集S中的個(gè)數(shù)為N，經(jīng)過(guò)下采樣所得S′中的個(gè)數(shù)為M，當(dāng)N較大時(shí)，只要所設(shè)定的覆蓋原始樣本空間的初始核寬有效，總能保證M?N。當(dāng)本文所提基于勢(shì)函數(shù)聚類的優(yōu)化下采樣方法運(yùn)行完畢，即可利用已有SVM算法對(duì)下采樣得到的集合S′中的樣本進(jìn)行訓(xùn)練，以得到相應(yīng)的SVM決策邊界。

盡管如此，相對(duì)于原始樣本集所直接訓(xùn)練出的SVM決策曲面，由于下采樣特性引起的樣本空間稀疏性問(wèn)題，可能導(dǎo)致所得的SVM分類邊界仍然會(huì)有一定程度的偏離。為進(jìn)一步改善該問(wèn)題，在所建立的SVM決策邊界尋找原始訓(xùn)練樣本集中邊界附近的樣本。相對(duì)于其他樣本，分類器邊界附近的樣本顯然擁有更多分類信息，以此構(gòu)成一個(gè)新的二次訓(xùn)練樣本集S″。如圖1所示為本文所提方法的原理示意圖。圖中每個(gè)圓圈表示一個(gè)不同參數(shù)的高斯核，用以實(shí)現(xiàn)對(duì)樣本空間局部區(qū)域的覆蓋，這種覆蓋按照樣本空間的密度從密集到稀疏，以增量學(xué)習(xí)的方式逐次進(jìn)行，每個(gè)高斯核的中心即為抽取的下采樣樣本。

結(jié)合以上描述，本文所提的勢(shì)函數(shù)聚類的優(yōu)化下采樣SVM學(xué)習(xí)算法如下：

1.使用式(5)和式(6)計(jì)算每個(gè)樣本勢(shì)值。

2.使用式(7)來(lái)確定最大勢(shì)值對(duì)應(yīng)的樣本。

4.使用式(8)來(lái)更新Si中每一個(gè)樣本勢(shì)值。

5.設(shè)置迭代終止條件

返回第2步繼續(xù)執(zhí)行。

Else

當(dāng)前Si類中樣本的學(xué)習(xí)進(jìn)程結(jié)束。轉(zhuǎn)向?qū)W習(xí)其他模式類別集合，直到所有模式類別集合學(xué)習(xí)完畢。

End If

6. 使用SVM學(xué)習(xí)庫(kù)(Libary SVM, LIBSVM)[16]算法對(duì)樣本集合S′中的樣本進(jìn)行訓(xùn)練，得到SVM初始分類曲面。

8.使用LIBSVM算法對(duì)樣本集合S″進(jìn)行二次訓(xùn)練，得到最終的SVM決策曲面。

2.2 計(jì)算復(fù)雜度分析

本文首先通過(guò)使用勢(shì)函數(shù)密度聚類的方式來(lái)構(gòu)造下采樣樣本集，然后在所獲取的下采樣集上進(jìn)行SVM初始訓(xùn)練，通過(guò)尋找原始訓(xùn)練集中的邊界樣本，以進(jìn)行SVM二次優(yōu)化。其計(jì)算復(fù)雜度分析如下：

(1)使用勢(shì)函數(shù)密度聚類的方式在增量構(gòu)造下采樣訓(xùn)練集。設(shè)初始訓(xùn)練集S中的個(gè)數(shù)為N，經(jīng)過(guò)下采樣所得S′中的個(gè)數(shù)為M，本文所提勢(shì)函數(shù)密度聚類來(lái)增量構(gòu)建下采樣訓(xùn)練集的過(guò)程中，考慮了每一類樣本的標(biāo)簽信息，樣本勢(shì)值的計(jì)算需要遍歷當(dāng)前模式類別中所有其他樣本，這里設(shè)定初始訓(xùn)練樣本集包含2個(gè)模式類別，其樣本個(gè)數(shù)分別為N1和N2，則N1+N2=N，同時(shí)考慮到建立不同參數(shù)的高斯核來(lái)覆蓋樣本子空間的勢(shì)值更新過(guò)程，計(jì)算復(fù)雜度為O((N1-1)2+(N2-1)2+M)，整理后為O(N2-2N1N2-2N+M)。

(2)使用下采樣集進(jìn)行SVM初始訓(xùn)練并尋找原始訓(xùn)練集中的邊界樣本，以進(jìn)行SVM二次優(yōu)化。設(shè)二次優(yōu)化SVM的訓(xùn)練樣本個(gè)數(shù)為L(zhǎng)，結(jié)合SVM的初始訓(xùn)練過(guò)程，計(jì)算復(fù)雜度為O(M3+L3)。

結(jié)合以上分析，計(jì)算本文所提勢(shì)函數(shù)聚類的優(yōu)化下采樣SVM分類方法的整個(gè)計(jì)算復(fù)雜度為O(N2-2N1N2-2N+M+M3+L3)。當(dāng)設(shè)定的覆蓋原始樣本空間的初始核寬有效，可以保證經(jīng)過(guò)下采樣抽取所得下采樣樣本數(shù)M?N；SVM的二次訓(xùn)練樣本來(lái)源于原始訓(xùn)練集中使用下采樣集進(jìn)行SVM訓(xùn)練的邊界附近樣本，其樣本個(gè)數(shù)L?N。這里需要指出的是，直接使用原始樣本集進(jìn)行SVM訓(xùn)練的計(jì)算復(fù)雜度為O(N3)，對(duì)于大樣本集，當(dāng)N很大時(shí)，相對(duì)于直接使用原始樣本集進(jìn)行SVM訓(xùn)練的方法，本文所提方法的訓(xùn)練效率可以得到很大程度的提升。

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

為驗(yàn)證本文所提方法的性能，分別在雙月人工數(shù)據(jù)集[19]、Occupancy基準(zhǔn)數(shù)據(jù)集[20]、Record基準(zhǔn)數(shù)據(jù)集[20]以及l(fā)jcnn1[21]基準(zhǔn)數(shù)據(jù)集上，將本文所提方法分別與LIBSVM[21]、隨機(jī)下采樣SVM[9]、聚類SVM[12]、GSVM[13]、S_GSVM[16]以及APG_SVM[17]學(xué)習(xí)算法進(jìn)行了實(shí)驗(yàn)對(duì)比，其中使用人工數(shù)據(jù)集是為了對(duì)本文所提方法進(jìn)行圖形化的驗(yàn)證，圖2所示為雙月人工數(shù)據(jù)集示意圖。實(shí)驗(yàn)中所有樣本都?xì)w一化到[-1,1]之間。本實(shí)驗(yàn)設(shè)置實(shí)驗(yàn)參數(shù)T=1，勢(shì)函數(shù)聚類核寬參數(shù)σ取值在0.1～0.6之間，勢(shì)函數(shù)學(xué)習(xí)閾值δ=0.001。SVM中選用的核函數(shù)為徑向基函數(shù)，核寬參數(shù)取自集合[0.25,0.5,1,2]，懲罰參數(shù)設(shè)置為C=1000，仿真算法為當(dāng)前流行的LIBSVM，實(shí)驗(yàn)中設(shè)定二次訓(xùn)練邊界門限值為ξ=0.05。實(shí)驗(yàn)環(huán)境為 Intel 2.8 GHZ CPU，4 G RAM。表1所示為分類數(shù)據(jù)集的信息描述。

表1 分類數(shù)據(jù)集信息描述

3.1 雙月人工數(shù)據(jù)集分類問(wèn)題

圖3所示為勢(shì)函數(shù)聚類的優(yōu)化下采樣SVM訓(xùn)練和分類效果圖。圖3中選定訓(xùn)練樣本個(gè)數(shù)為3 000，測(cè)試樣本個(gè)數(shù)為4 000。圖4所示為訓(xùn)練樣本個(gè)數(shù)以及核寬參數(shù)σ改變時(shí)下采樣與篩選邊界樣本效果對(duì)比。圖4a～圖4c對(duì)應(yīng)取值為σ=0.1，圖4d～圖4f對(duì)應(yīng)取值為σ=0.2。相對(duì)于原始樣本集，采用本文所提的下采樣方法所得的訓(xùn)練樣本的個(gè)數(shù)得到很大程度的下降，并完成原始訓(xùn)練樣本集的下采樣優(yōu)化篩選。相對(duì)于LIBSVM，本文所提勢(shì)函數(shù)聚類的下采樣方法可以完成對(duì)原始樣本空間的有效逼近，其訓(xùn)練效率得到了很大改善。通過(guò)對(duì)下采樣訓(xùn)練所得的SVM決策曲面附近尋找原始訓(xùn)練集中的邊界樣本，可以訓(xùn)練出一個(gè)新的學(xué)習(xí)器，這種采樣優(yōu)化和學(xué)習(xí)器優(yōu)化相結(jié)合的策略在有效提高訓(xùn)練效率的同時(shí)保證了學(xué)習(xí)器具有良好的泛化性能。

由圖4選定訓(xùn)練樣本個(gè)數(shù)為1 000可以看出，相對(duì)于圖3，當(dāng)訓(xùn)練樣本個(gè)數(shù)發(fā)生變化時(shí)，本文所提方法依然可以在樣本空間的不同子區(qū)域篩選出具有代表性的不同下采樣樣本集合，而隨著核寬參數(shù)的增加，對(duì)原始樣本空間的不同的局部區(qū)域覆蓋范圍增大，盡管下采樣所得的樣本個(gè)數(shù)減少，但整體上依然可以逼近原始樣本空間的結(jié)構(gòu)分布，從而進(jìn)一步表明本文所提勢(shì)函數(shù)聚類的下采樣方法對(duì)樣本空間具有較好的自適應(yīng)性。表2所示為雙月數(shù)據(jù)集下本文方法與LIBSVM的性能對(duì)比，由表2可知，在所提初始下采樣樣本方法有效的前提下，本文的二次篩選樣本方式進(jìn)一步確保了學(xué)習(xí)器的分類性能。圖5所示為本文所提方法與LIBSVM訓(xùn)練時(shí)間對(duì)比。從圖5可以看出，隨著訓(xùn)練樣本個(gè)數(shù)的增加，本文所提方法的訓(xùn)練時(shí)間明顯少于直接對(duì)原始樣本集進(jìn)行訓(xùn)練的LIBSVM方法，因此尤其適用于大樣本集下的SVM訓(xùn)練和分類。

表2 雙月數(shù)據(jù)集下本文所提方法與LIBSVM的性能對(duì)比

注：[a]表示勢(shì)函數(shù)聚類篩選的下采樣集合中的樣本個(gè)數(shù)與二次優(yōu)化篩選的邊界樣本個(gè)數(shù)；[b]代表從勢(shì)函數(shù)聚類篩選下采樣訓(xùn)練集到二次優(yōu)化訓(xùn)練SVM分類器的時(shí)間。

3.2 基準(zhǔn)數(shù)據(jù)集分類問(wèn)題

表3～表5分別給出在Occupancy、Record和ljcnn1基準(zhǔn)數(shù)據(jù)集下，本文所提方法與其他方法的性能對(duì)比?？梢钥闯觯鄬?duì)于LIBSVM，本文方法在保持分類器良好泛化性能的前提下，訓(xùn)練時(shí)間得到極大程度的降低。相對(duì)于隨機(jī)采樣SVM、聚類SVM以及GSVM方法，本文方法的訓(xùn)練時(shí)間和分類精度均有不同程度的改善。在ljcnn1數(shù)據(jù)集上(如表5)，本文方法的訓(xùn)練時(shí)間與S_GSVM和APG_SVM相當(dāng)；在Record數(shù)據(jù)集上(如表4)，本文方法的訓(xùn)練時(shí)間稍高于APG_SVM。在分類精度上，本文方法的分類性能高于S_GSVM和APG_SVM。一方面，本文所提勢(shì)函數(shù)聚類的方法有效結(jié)合了樣本空間的全局分布信息和局部區(qū)域信息，通過(guò)統(tǒng)計(jì)樣本空間每個(gè)樣本點(diǎn)的勢(shì)值，建立不同的高斯核實(shí)現(xiàn)對(duì)樣本空間不同區(qū)域的覆蓋來(lái)自適應(yīng)生成聚類個(gè)數(shù)，可以根據(jù)樣本空間的分布情況自適應(yīng)篩選出具有代表性的下采樣樣本集合，這些下采樣樣本直接來(lái)自原始的訓(xùn)練集，由于可以有效逼近原始樣本空間分布結(jié)構(gòu)，保證了所得下采樣訓(xùn)練集的有效性。相對(duì)于原始訓(xùn)練集，在下采樣集合極大降低的情況下，本文方法的訓(xùn)練效率得到了很大的改善；另一方面，本文方法通過(guò)對(duì)所建立的SVM決策曲面尋找原始訓(xùn)練樣本集中的邊界附近樣本，用以完成對(duì)SVM邊界的二次優(yōu)化，進(jìn)一步改善了學(xué)習(xí)器的泛化能力。

表3 Occupancy基準(zhǔn)數(shù)據(jù)集下本文方法與其他方法性能對(duì)比

表4 Record基準(zhǔn)數(shù)據(jù)集下本文方法與其他方法性能對(duì)比

表5 ljcnn1基準(zhǔn)數(shù)據(jù)集下本文方法與其他方法性能對(duì)比

表6～表8分別給出在Occupancy、Record和ljcnn1基準(zhǔn)數(shù)據(jù)集下，本文方法不同核寬參數(shù)的性能對(duì)比。從表6～表8可以看出，通過(guò)改變勢(shì)函數(shù)聚類核寬參數(shù)σ，對(duì)原始樣本空間的覆蓋尺度發(fā)生變化，所得下采樣集也隨之改變，但是總體上維持相對(duì)穩(wěn)定的分類性能，表明本文所提勢(shì)函數(shù)聚類的下采樣方法對(duì)樣本空間具有良好的適應(yīng)性。當(dāng)核寬過(guò)小，例如當(dāng)σ=0.1時(shí)，此時(shí)對(duì)高維樣本空間的覆蓋范圍有限，下采樣所得樣本集與原始訓(xùn)練樣本集相同，此時(shí)本文所提勢(shì)函數(shù)聚類的下采樣SVM方法直接蛻化為L(zhǎng)IBSVM。因此，在實(shí)際應(yīng)用中，為保證本文所提方法的有效性，要求勢(shì)函數(shù)聚類核寬參數(shù)σ不應(yīng)過(guò)低，從而保證所建立高斯核覆蓋原始樣本空間不同局部區(qū)域的有效性。

表6 Occupancy基準(zhǔn)數(shù)據(jù)集下本文方法不同核寬參數(shù)下的性能對(duì)比

表7 Record基準(zhǔn)數(shù)據(jù)集下本文方法不同核寬參數(shù)下的性能對(duì)比

續(xù)表7

表8 ljcnn1基準(zhǔn)數(shù)據(jù)集下本文方法不同核寬參數(shù)下的性能對(duì)比

4 結(jié)束語(yǔ)

本文針對(duì)大樣本集SVM訓(xùn)練和分類問(wèn)題，研究了一種勢(shì)函數(shù)密度聚類的優(yōu)化下采樣SVM分類方法。該方法考慮了原始樣本空間不同區(qū)域的稀疏程度，通過(guò)引入勢(shì)函數(shù)對(duì)樣本空間的各樣本進(jìn)行密度度量，建立了不同的高斯核完成對(duì)樣本空間不同區(qū)域的覆蓋，將每個(gè)核中心對(duì)應(yīng)的樣本作為采樣樣本，以此來(lái)增量構(gòu)建下采樣訓(xùn)練集，可以根據(jù)樣本空間的分布自適應(yīng)生成訓(xùn)練集的個(gè)數(shù)，并有效逼近原始樣本空間結(jié)構(gòu)分布。然后通過(guò)尋找分類器決策曲面附近的邊界樣本來(lái)進(jìn)行SVM二次優(yōu)化。通過(guò)在1個(gè)人工數(shù)據(jù)集和3個(gè)基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文所提方法在有效改善SVM訓(xùn)練效率的同時(shí)保證了良好的泛化性能。由于本文所提方法采用的是批量學(xué)習(xí)的方式，適用于離線學(xué)習(xí)，但是實(shí)際問(wèn)題中的訓(xùn)練樣本往往不可能一次性得到，后續(xù)將關(guān)注在線序列學(xué)習(xí)問(wèn)題，構(gòu)建合適的基于增量學(xué)習(xí)的SVM。