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

(1.莆田學(xué)院 信息工程學(xué)院，福建 莆田 351100； 2.東方地球物理公司 遼河物探處，遼寧 盤(pán)錦 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分類(lèi)方法直接從訓(xùn)練樣本集的角度出發(fā)，通過(guò)從原始樣本集中抽取或聚類(lèi)選擇具有一定代表性的樣本來(lái)降低訓(xùn)練樣本的規(guī)模，從而提升SVM的訓(xùn)練效率。隨機(jī)下采樣SVM方法[9]與聚類(lèi)SVM方法[10-12]是兩種典型的下采樣SVM方法，隨機(jī)下采樣SVM方法的不足在于當(dāng)采樣個(gè)數(shù)較少時(shí)，采樣的隨機(jī)性導(dǎo)致所獲取的樣本往往不能反映原始樣本集的空間分布特征；聚類(lèi)SVM方法將訓(xùn)練樣本聚類(lèi)所得的聚類(lèi)中心作為SVM新的訓(xùn)練集，該方法的聚類(lèi)個(gè)數(shù)需要預(yù)先確定，盡管可以極大程度降低訓(xùn)練樣本集的規(guī)模，但是這些聚類(lèi)中心往往會(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ù)聚類(lèi)的優(yōu)化下采樣SVM分類(lèi)方法。與已有聚類(lèi)SVM方法不同，本文所提勢(shì)函數(shù)聚類(lèi)方式所得的下采樣集合直接來(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)確定聚類(lèi)個(gè)數(shù)，克服了聚類(lèi)SVM方法中的聚類(lèi)個(gè)數(shù)需要手動(dòng)調(diào)整和聚類(lèi)子空間覆蓋范圍尺度不一致的問(wèn)題。相對(duì)于GSVM，本文所提勢(shì)函數(shù)聚類(lèi)方式所得的下采樣集合來(lái)源于原始樣本空間的各個(gè)局部子區(qū)域，在生成下采樣集合的過(guò)程中，將樣本空間的全局分布信息和局部區(qū)域信息結(jié)合在一起，有效地克服了數(shù)據(jù)分布的差異性，從而保證了學(xué)習(xí)器的泛化能力。

但是，相對(duì)于原始樣本集所直接訓(xùn)練出的SVM決策曲面，由于下采樣特性引起的樣本空間稀疏性問(wèn)題，可能導(dǎo)致下采樣訓(xùn)練所得的SVM分類(lèi)邊界仍然會(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分類(lèi)器。

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

1 SVM算法原理

(1)

式中:優(yōu)化所得的非零拉格朗日乘子αi對(duì)應(yīng)的樣本項(xiàng)稱(chēng)為支持向量;C為選定的正參數(shù)。該方法可以通過(guò)將輸入樣本x非線(xiàn)性映射到高維特征空間φ(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ù)密度聚類(lèi)的優(yōu)化下采樣SVM方法

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

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

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

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

(4)

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

借助勢(shì)函數(shù)的定義，本文將勢(shì)函數(shù)的數(shù)學(xué)模型引入訓(xùn)練樣本空間，設(shè)計(jì)了勢(shì)函數(shù)密度聚類(lèi)的學(xué)習(xí)機(jī)制以實(shí)現(xiàn)對(duì)訓(xùn)練樣本空間的密度度量，然后將聚類(lèi)所得各個(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)練集中的相同模式類(lèi)別樣本集合為基礎(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í)其他的模式類(lèi)別，直到所有模式類(lèi)別學(xué)習(xí)完畢，并最終構(gòu)建新的訓(xùn)練樣本集合S′。

以上所提勢(shì)函數(shù)密度聚類(lèi)來(lái)增量構(gòu)建下采樣訓(xùn)練集的過(guò)程中，考慮每一類(lèi)樣本的標(biāo)簽信息，通過(guò)統(tǒng)計(jì)樣本空間中每個(gè)樣本點(diǎn)的勢(shì)值，可以建立各樣本的勢(shì)值度量，其中勢(shì)值較大的樣本點(diǎn)所在的樣本區(qū)域較為密集，反之較為稀疏，以此視為對(duì)樣本空間的密度聚類(lèi)學(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ù)聚類(lèi)的優(yōu)化下采樣方法運(yùn)行完畢，即可利用已有SVM算法對(duì)下采樣得到的集合S′中的樣本進(jìn)行訓(xùn)練，以得到相應(yīng)的SVM決策邊界。

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

結(jié)合以上描述，本文所提的勢(shì)函數(shù)聚類(lèi)的優(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類(lèi)中樣本的學(xué)習(xí)進(jìn)程結(jié)束。轉(zhuǎn)向?qū)W習(xí)其他模式類(lèi)別集合，直到所有模式類(lèi)別集合學(xué)習(xí)完畢。

End If

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

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

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

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

(1)使用勢(shì)函數(shù)密度聚類(lèi)的方式在增量構(gòu)造下采樣訓(xùn)練集。設(shè)初始訓(xùn)練集S中的個(gè)數(shù)為N，經(jīng)過(guò)下采樣所得S′中的個(gè)數(shù)為M，本文所提勢(shì)函數(shù)密度聚類(lèi)來(lái)增量構(gòu)建下采樣訓(xùn)練集的過(guò)程中，考慮了每一類(lèi)樣本的標(biāo)簽信息，樣本勢(shì)值的計(jì)算需要遍歷當(dāng)前模式類(lèi)別中所有其他樣本，這里設(shè)定初始訓(xùn)練樣本集包含2個(gè)模式類(lèi)別，其樣本個(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ù)聚類(lèi)的優(yōu)化下采樣SVM分類(lèi)方法的整個(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]、聚類(lèi)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ù)聚類(lèi)核寬參數(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)練邊界門(mén)限值為ξ=0.05。實(shí)驗(yàn)環(huán)境為 Intel 2.8 GHZ CPU，4 G RAM。表1所示為分類(lèi)數(shù)據(jù)集的信息描述。

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

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

圖3所示為勢(shì)函數(shù)聚類(lèi)的優(yōu)化下采樣SVM訓(xùn)練和分類(lèi)效果圖。圖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ù)聚類(lèi)的下采樣方法可以完成對(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ù)聚類(lèi)的下采樣方法對(duì)樣本空間具有較好的自適應(yīng)性。表2所示為雙月數(shù)據(jù)集下本文方法與LIBSVM的性能對(duì)比，由表2可知，在所提初始下采樣樣本方法有效的前提下，本文的二次篩選樣本方式進(jìn)一步確保了學(xué)習(xí)器的分類(lèi)性能。圖5所示為本文所提方法與LIBSVM訓(xùn)練時(shí)間對(duì)比。從圖5可以看出，隨著訓(xùn)練樣本個(gè)數(shù)的增加，本文所提方法的訓(xùn)練時(shí)間明顯少于直接對(duì)原始樣本集進(jìn)行訓(xùn)練的LIBSVM方法，因此尤其適用于大樣本集下的SVM訓(xùn)練和分類(lèi)。

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

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

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

表3～表5分別給出在Occupancy、Record和ljcnn1基準(zhǔn)數(shù)據(jù)集下，本文所提方法與其他方法的性能對(duì)比?？梢钥闯?，相對(duì)于LIBSVM，本文方法在保持分類(lèi)器良好泛化性能的前提下，訓(xùn)練時(shí)間得到極大程度的降低。相對(duì)于隨機(jī)采樣SVM、聚類(lèi)SVM以及GSVM方法，本文方法的訓(xùn)練時(shí)間和分類(lèi)精度均有不同程度的改善。在ljcnn1數(shù)據(jù)集上(如表5)，本文方法的訓(xùn)練時(shí)間與S_GSVM和APG_SVM相當(dāng)；在Record數(shù)據(jù)集上(如表4)，本文方法的訓(xùn)練時(shí)間稍高于APG_SVM。在分類(lèi)精度上，本文方法的分類(lèi)性能高于S_GSVM和APG_SVM。一方面，本文所提勢(shì)函數(shù)聚類(lèi)的方法有效結(jié)合了樣本空間的全局分布信息和局部區(qū)域信息，通過(guò)統(tǒng)計(jì)樣本空間每個(gè)樣本點(diǎn)的勢(shì)值，建立不同的高斯核實(shí)現(xiàn)對(duì)樣本空間不同區(qū)域的覆蓋來(lái)自適應(yīng)生成聚類(lèi)個(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ù)聚類(lèi)核寬參數(shù)σ，對(duì)原始樣本空間的覆蓋尺度發(fā)生變化，所得下采樣集也隨之改變，但是總體上維持相對(duì)穩(wěn)定的分類(lèi)性能，表明本文所提勢(shì)函數(shù)聚類(lèi)的下采樣方法對(duì)樣本空間具有良好的適應(yīng)性。當(dāng)核寬過(guò)小，例如當(dāng)σ=0.1時(shí)，此時(shí)對(duì)高維樣本空間的覆蓋范圍有限，下采樣所得樣本集與原始訓(xùn)練樣本集相同，此時(shí)本文所提勢(shì)函數(shù)聚類(lèi)的下采樣SVM方法直接蛻化為L(zhǎng)IBSVM。因此，在實(shí)際應(yīng)用中，為保證本文所提方法的有效性，要求勢(shì)函數(shù)聚類(lèi)核寬參數(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)練和分類(lèi)問(wèn)題，研究了一種勢(shì)函數(shù)密度聚類(lèi)的優(yōu)化下采樣SVM分類(lèi)方法。該方法考慮了原始樣本空間不同區(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)器決策曲面附近的邊界樣本來(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í)的方式，適用于離線(xiàn)學(xué)習(xí)，但是實(shí)際問(wèn)題中的訓(xùn)練樣本往往不可能一次性得到，后續(xù)將關(guān)注在線(xiàn)序列學(xué)習(xí)問(wèn)題，構(gòu)建合適的基于增量學(xué)習(xí)的SVM。