一種基于近鄰區(qū)的支持向量機(jī)樣本約減算法

【摘 要】支持向量機(jī) （Support Vector Machine，SVM）以實(shí)現(xiàn)結(jié)構(gòu)風(fēng)險(xiǎn)最小化為原則，成功避免了傳統(tǒng)機(jī)器學(xué)習(xí)基于無窮樣本數(shù)量的假設(shè)，以及推廣能力差、“過學(xué)習(xí)”、局部最優(yōu)值、“維數(shù)災(zāi)難”等問題。對(duì)分類起作用的支持向量只存在于樣本分界處，其他對(duì)分類不起作用的樣本會(huì)增加構(gòu)造支持向量的時(shí)間，導(dǎo)致分類速度較慢。本文提出了一種基于近鄰區(qū)的樣本約減算法，將異類樣本中離得最近（特征空間中離得近意為相似性高）的聚類區(qū)域內(nèi)的樣本集合作為SVM新的訓(xùn)練樣本集合，從而有效減少訓(xùn)練樣本數(shù)量和構(gòu)造支持向量的時(shí)間，在保證分類準(zhǔn)確度的前提下提高分類速率。

【關(guān)鍵詞】SVM，分類，樣本約減，近鄰區(qū)

一、引言

SVM是在小樣本情況下發(fā)展起來的統(tǒng)計(jì)機(jī)器學(xué)習(xí)理論，基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則[1]，可以解決分類、回歸等問題。結(jié)構(gòu)風(fēng)險(xiǎn)最小化就是指在保證分類精度的同時(shí)，降低學(xué)習(xí)機(jī)器的VC維，使學(xué)習(xí)機(jī)器在整個(gè)樣本集上期望風(fēng)險(xiǎn)得到控制。

SVM最初以成功解決二分類問題著稱，其分類準(zhǔn)確性高、受“噪音”樣本干擾小、穩(wěn)定性好，通過在樣本之間尋找一個(gè)最優(yōu)分類面分隔異類樣本。尋找最優(yōu)分類面的問題最終轉(zhuǎn)換成凸二次優(yōu)化問題的求解過程，樣本數(shù)量及樣本的維數(shù)都將直接影響分類性能。因此，在數(shù)據(jù)分類中減少樣本數(shù)量不僅可以減少SVM分類時(shí)間，而且可以實(shí)現(xiàn)結(jié)構(gòu)風(fēng)險(xiǎn)最小化。

二、SVM[2]

三、SVM樣本約減算法研究現(xiàn)狀

為了提高分類性能，有效優(yōu)化SVM的樣本訓(xùn)練效率，目前已經(jīng)提出了一些方法。文獻(xiàn)[3]提出采用聚類方法尋找代表 k 個(gè)簇的聚類中心作為約簡(jiǎn)集，該方法只能表現(xiàn)為超球面的形狀，以單一的點(diǎn)代替整個(gè)不規(guī)則的聚類簇很不合適。

也有的方法將主動(dòng)學(xué)習(xí)策略用于 SVM 的樣本選擇[4]，以及在特征空間中將樣本做分離，將高維二次凸優(yōu)化問題分化成多個(gè)低維凸優(yōu)化問題的組合[5]。

張金澤[6]等人提出模糊超球支持向量機(jī)，將樣本空間劃分成有限個(gè)超球子空間，超球球心作為新的訓(xùn)練集。

文獻(xiàn)[7]提出的算法通過計(jì)算樣本與類中心點(diǎn)的夾角進(jìn)行樣本約減，該方法有一定錯(cuò)選或多選，達(dá)不到最佳效果。

四、基于近鄰區(qū)的SVM樣本約減算法

對(duì)SVM分類起作用的只有位于樣本集合交界處支持向量，而其它非支持向量對(duì)分類沒有任何貢獻(xiàn)。本文提出的基于“近鄰區(qū)”的SVM樣本約減算法將兩類樣本中離得最近（特征空間中離得近意為相似性高）聚類區(qū)域內(nèi)的樣本作為SVM新的訓(xùn)練樣本集合，從而減少構(gòu)造支持向量的時(shí)間，提高分類速率。

（一）相關(guān)定義

（二）基于近鄰區(qū)的樣本約減算法過程

在樣本的特征空間中，每一個(gè)聚類都占據(jù)一定的區(qū)域，聚類區(qū)域內(nèi)的樣本可以用該聚類的聚類中心近似代表。本文基于近鄰區(qū)的樣本約減算法具體過程描述如下：

注意，采用樣本約減算法后的樣本數(shù)量與異類子近鄰區(qū)中的值選取有關(guān)，值越大，約減算法處理后的樣本所包含的支持向量可能更多、更全面，但樣本訓(xùn)練時(shí)間隨之增加。因此，在實(shí)際應(yīng)用中應(yīng)當(dāng)從SVM訓(xùn)練樣本時(shí)間、分類準(zhǔn)確性等多方面進(jìn)行考慮與權(quán)衡。

本文提出的基于“近鄰區(qū)”的SVM樣本約減算法將那些分布于樣本分界處附近、處于自身所在類別邊界處的帶狀區(qū)域內(nèi)的樣本作為新的樣本集合，從而保證約減后得到的樣本集合與支持向量出現(xiàn)的位置相同，大大降低了計(jì)算量，減少了構(gòu)造支持向量的時(shí)間。因此，本文提出的樣本約減算法在保證分類準(zhǔn)確度的同時(shí)有效減少了分類時(shí)間。

參考文獻(xiàn)：

[1]Hou Jinbiao.Design and implementation of a system of video image capture of camera based on JMF[C]. MultiMedia and Information Technology，International Conference，2008：201-204.

[2]G. Song， J. Guo， Y. Nie. An Intrusion Detection Method Based on Multiple Kernel Support Vector Machine [C]. International Conference on Network Computing and Information Security. 2011， 119–123.

[3]李曉黎， 劉繼敏， 史忠植，基于支持向量機(jī)與無監(jiān)督聚類相結(jié)合的中文網(wǎng)頁(yè)分類器，

計(jì)算機(jī)學(xué)報(bào)，2001，24（1）： 62～68.

[4]Schohn G，Cohn D.Less is more：Active learning with support vector machines[C]. Proceedings of the 17th International Conference on Machine Learning. IEEE Press，2000：839-846.

[5]王勇. 基于特征空間中樣本選取與分離的 SVM 簡(jiǎn)化方法 [J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2008， 29（5）：486-491.

[6]張金澤，單甘霖，模糊支持向量機(jī)，軍械工程學(xué)院學(xué)報(bào)，2005，17（3）：65～67.

[7]羅瑜，易文德.大規(guī)模數(shù)據(jù)集下支持向量機(jī)訓(xùn)練樣本的縮減策略[J].計(jì)算機(jī)科學(xué)， 2007， 34（10）：211-213.