劉曉瑩，楊寶華

一種改進(jìn)的SMO分類算法

劉曉瑩，楊寶華

摘要:針對序列最小優(yōu)化(SMO)算法對大規(guī)模數(shù)據(jù)集訓(xùn)練速度慢、分類精度不夠高的問題，提出了一種改進(jìn)方法。該方法對SMO算法的核函數(shù)進(jìn)行改進(jìn)，通過增大二次項(xiàng)系數(shù)的絕對值提高分類正確率，并結(jié)合網(wǎng)格搜索法優(yōu)化基于核函數(shù)改進(jìn)的SMO算法的有關(guān)參數(shù)。實(shí)驗(yàn)結(jié)果表明，該算法顯著提高了分類的正確性，縮短了算法的建模時間。

關(guān)鍵詞:支持向量機(jī)；SMO算法；核函數(shù)；參數(shù)尋優(yōu)

隨著人類社會的快速發(fā)展，信息技術(shù)、互聯(lián)網(wǎng)、云計算、物聯(lián)網(wǎng)等諸多領(lǐng)域的突破，使大量的數(shù)據(jù)在急劇膨脹，因此迫切需要更加快速、精確的方法對收集到的海量數(shù)據(jù)進(jìn)行分類，以便從中提取出有效的、新穎的、精煉的、可理解的知識。現(xiàn)有的分類算法[1]有很多種，比如經(jīng)典的有決策樹、人工神經(jīng)網(wǎng)絡(luò)、貝葉斯、支持向量機(jī)等方法。

近年來，SMO算法[2]已經(jīng)受到越來越多研究者的關(guān)注。項(xiàng)堃[3]等人提出一種運(yùn)用刪減部分支持向量，提前結(jié)束循環(huán)條件的策略；王越[4]等人選取優(yōu)化步長最大的違反KKT條件的樣本和其配對樣本；王朝輝[5]等人通過改變存儲策略，將算法中的五個工作集替換成三個工作集；駱世廣[6]等人提出將算法的終止條件改為目標(biāo)函數(shù)值的改變量，并改變SMO后期迭代循環(huán)條件。

上述算法僅在縮短訓(xùn)練時間方面已經(jīng)取得了一定的改進(jìn)，但當(dāng)訓(xùn)練大規(guī)模數(shù)據(jù)集時，SMO分類效果還不夠明顯，分類正確率也需要進(jìn)一步的提高。本文提出一種改進(jìn)方法，通過增大二次項(xiàng)系數(shù)的絕對值提高分類正確率，通過實(shí)驗(yàn)結(jié)果驗(yàn)證，該方法可以大幅度降低建模時間，提高分類精度。

1序列最小優(yōu)化算法

1.1支持向量機(jī)概述

式中：αi為拉格朗日乘子，C為懲罰因子。

根據(jù)上述問題得到的對偶問題為

(1)

分類決策函數(shù)為：

(2)

式中：α*為最優(yōu)解；b*為閾值，它由任一個支持向量求出也可通過兩類中任意一對支持向量取中值求得。

1.2SMO算法

SMO算法[8]是目前SVM處理大數(shù)據(jù)集十分有效的方法。整個SMO算法包括兩個步驟：

步驟一：求解兩個變量的二次規(guī)劃的解析方法

經(jīng)過推導(dǎo)可得：

(3)

其中：

經(jīng)過修剪后的α2

(4)

步驟二：選擇變量的啟發(fā)式方法。

SMO選擇第一個變量的過程稱為外層循環(huán)，外層循環(huán)在訓(xùn)練樣本中選取違反KKT條件最為嚴(yán)重的樣本點(diǎn)，并將其對應(yīng)的變量作為第一個變量。具體地，檢驗(yàn)訓(xùn)練樣本點(diǎn)是否滿足KKT條件，即

SMO算法的優(yōu)點(diǎn)在于通過兩個變量的二次規(guī)劃問題的解析來求解，不需要進(jìn)行巨大的矩陣運(yùn)算，但其在面對大規(guī)模數(shù)據(jù)時，出現(xiàn)訓(xùn)練速度慢、分類正確率不夠高的問題。

SMO算法的大部分訓(xùn)練時間主要集中在最有可能違反KKT條件的非邊界樣本上。該算法訓(xùn)練速度慢的主要原因在于它需要計算和存儲核函數(shù)矩陣，隨著數(shù)據(jù)樣本的增加，所需的內(nèi)存空間也增大。因此，可通過減少計算核函數(shù)矩陣的方法來加快算法的速度。

1.3核函數(shù)

核函數(shù)的基本思想就是通過一個非線性變換將輸入空間映射到一個高維特征空間，在這個特征空間中求解最優(yōu)分類面。每個中間節(jié)點(diǎn)對應(yīng)一個支持向量，輸出的決策函數(shù)是中間節(jié)點(diǎn)的線性組合。

不同的核函數(shù)及其參數(shù)的選擇對于SMO算法具有重要的影響。核函數(shù)的引入避免了“維數(shù)災(zāi)難”，大大減小了特征空間的計算量，無需知道非線性變換函數(shù)φ的形式和參數(shù)。核函數(shù)可以和不同的算法相結(jié)合，形成多種不同的基于核函數(shù)技術(shù)的方法[9]。目前常用的核函數(shù)[10]主要有三類：

1)多項(xiàng)式核函數(shù)：

(5)

2)高斯核函數(shù)：

(6)

3)Sigmoid核函數(shù)：

(7)

2SMO算法的改進(jìn)

2.1核函數(shù)的改進(jìn)

Vapnik等人提出測試樣本分類誤差率的期望上界

(8)

選取SMO算法的某個核函數(shù)與系數(shù)(1+m)(m>0)相乘，以高斯核函數(shù)為例，如(9)式：

(9)

由(9)式可知，核函數(shù)與一個系數(shù)(1+m)(m>0)相乘可增大LD中二次項(xiàng)系數(shù)的絕對值，從而減小了αi的最優(yōu)值及支持向量個數(shù)，減少分類誤差率，提高支持向量機(jī)的分類精度和推廣能力。

2.2參數(shù)尋優(yōu)

在核函數(shù)改進(jìn)方法中，參數(shù)m的取值直接影響了基于核函數(shù)改進(jìn)的SMO算法的分類性能，因此選擇合適的參數(shù)也是非常重要的。本文選用網(wǎng)格搜索法[11]優(yōu)化核函數(shù)的參數(shù)m和懲罰因子C。用基于核函數(shù)改進(jìn)的SMO算法計算整體的分類精度，直到得到滿意的分類結(jié)果為止。其具體步驟如圖1所示。

圖1結(jié)合網(wǎng)格搜索法的SMO參數(shù)尋優(yōu)步驟

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

3.1實(shí)驗(yàn)一

為驗(yàn)證本文方法的有效性，在加州大學(xué)厄文分校(UCI)的機(jī)器學(xué)習(xí)數(shù)據(jù)庫中選用兩組數(shù)據(jù)集Labor和Sensor_reading_4進(jìn)行測試，Labor數(shù)據(jù)集包含57個實(shí)例，16個屬性，2個類別，屬于小數(shù)據(jù)集。Sensor_reading_4數(shù)據(jù)集包含5458個實(shí)例，4個屬性，4個類別，屬于大數(shù)據(jù)集。本文方法用Java語言實(shí)現(xiàn)，在實(shí)驗(yàn)中，選用RBF核函數(shù)，利用十折交叉驗(yàn)證法評價分類器，對于Labor數(shù)據(jù)集，C取1，m取111；對于Sensor_reading_4數(shù)據(jù)集，C取1，m取147。實(shí)驗(yàn)結(jié)果如表1所示。

表1　RBF核函數(shù)改進(jìn)前后實(shí)驗(yàn)結(jié)果對比

表1顯示了基于核函數(shù)改進(jìn)的SMO算法和SMO算法分類結(jié)果比較，從表中可以看出，以Sensor_reading_4大數(shù)據(jù)集為例，在建模時間上，基于核函數(shù)改進(jìn)的SMO算法差不多只用了21.15s，大幅度降低了建模時間，其分類正確率為81.8732%，與SMO相比，提高了近30%。實(shí)驗(yàn)結(jié)果表明，基于核函數(shù)改進(jìn)的SMO算法，具有更高的分類正確率，且大大縮減了算法的建模時間，尤其是對大規(guī)模數(shù)據(jù)集而言，效果更顯著，同時也驗(yàn)證了本文方法的可行性和有效性。在Sensor_reading_4數(shù)據(jù)集上，基于核函數(shù)改進(jìn)的SMO算法的誤分可視化結(jié)果如圖2所示。

圖2Sensor_reading_4數(shù)據(jù)集的誤分可視化結(jié)果

Sensor_reading_4數(shù)據(jù)集包含四個類別屬性：Slight-right-turn、Sharp-right-turn、Move-forward、Slight-left-turn。X軸為實(shí)際類別，Y軸為預(yù)測類別，圖中方塊表示分類錯誤的樣本，叉表示分類正確的樣本。

3.2實(shí)驗(yàn)二

為尋找上述實(shí)驗(yàn)中參數(shù)m的最優(yōu)值，本文采用網(wǎng)格搜索法優(yōu)化基于核函數(shù)改進(jìn)的SMO算法的參數(shù)m和懲罰因子C。以Sensor_reading_4數(shù)據(jù)集為例，實(shí)驗(yàn)過程如下：

(1)選定一組C，m的取值范圍和搜索步長，設(shè)C的初始范圍為[1，8]，步長為1；m的初始范圍為[0，50]，步長為1。

(2)用基于核函數(shù)改進(jìn)的SMO算法計算整體的分類正確率和搜索時間，實(shí)驗(yàn)結(jié)果得到使分類正確率最高的最優(yōu)參數(shù)C=1，m=45。

(3)根據(jù)得到的最優(yōu)參數(shù)，在其附近選擇不同的取值范圍進(jìn)行二次尋優(yōu)，并計算出搜索時間和分類正確率，比較不同的取值范圍對分類正確率的影響，實(shí)驗(yàn)結(jié)果如表2所示。

從表2可以看出，第三組的搜索時間最短，且分類正確率最高，選擇此組參數(shù)作為最優(yōu)參數(shù)，即最優(yōu)值C=1，m=147。同樣，對于Labor數(shù)據(jù)集，采用網(wǎng)格搜索法得到的最優(yōu)參數(shù)C=1，m=111。

表2　不同取值范圍內(nèi)參數(shù)尋優(yōu)結(jié)果對比

4結(jié)束語

本文在對Vapnik等人提出測試樣本分類誤差率的期望上界的分析的基礎(chǔ)上，通過減少支持向量數(shù)的方法來減小分類誤差率，提出了核函數(shù)改進(jìn)方法，提高了分類正確率，且大幅度降低了建模時間。結(jié)合網(wǎng)格搜索法，優(yōu)化基于核函數(shù)改進(jìn)的SMO算法的有關(guān)參數(shù)。實(shí)驗(yàn)結(jié)果證明，在大數(shù)據(jù)情況下，該方法能有效的克服SMO算法的缺陷，并獲得較好的分類效果。

網(wǎng)格搜索法對于大數(shù)據(jù)集的搜索時間過長，該方法需要進(jìn)一步的改進(jìn)研究，參數(shù)的尋優(yōu)方法可作為今后的研究方向。

[參考文獻(xiàn)]

[1]羅可,林睦綱,郗東妹.數(shù)據(jù)挖掘中分類算法綜述[J].計算機(jī)工程,2005,31(1):3-5.

[2]Platt J C. Fast training of support vector machines using sequential minimal optimization[C]//Advances in Kernel Methods-Support Vector Learning. Cambridge, MA: MIT Press, 1999: 185-208.

[3]項(xiàng)堃,喻瑩.一種改進(jìn)序貫最小優(yōu)化算法的方法[J]. 現(xiàn)代電子技術(shù), 2013, 36( 8) : 17-19.

[4]王越,呂奇峰,王泉等.一種改進(jìn)的支持向量機(jī)序列最小優(yōu)化算法[J].重慶理工大學(xué)學(xué)報(自然科學(xué)),2013,27(3):76-79.[5]駱世廣,駱昌日,周業(yè)明.針對大規(guī)模樣本集的SMO訓(xùn)練策略[J].廣東技術(shù)師范學(xué)院學(xué)報,2008,9:30-33.

[6]王朝輝,黎鑫.基于WEKA的序列最小化算法的改進(jìn)研究[J].工業(yè)控制計算機(jī),2012,25(8):81-84.

[7]顧亞祥,丁世飛.支持向量機(jī)研究發(fā)展[J].計算機(jī)科學(xué),2011,38(2):14-17.

[8]張宏灝.準(zhǔn)線性支持向量機(jī)及序列最小優(yōu)化算法[D].西安:西安電子科技大學(xué),2013.

[9]張倩,楊耀權(quán).基于支持向量機(jī)核函數(shù)的研究[J].電子科學(xué)與工程,2012,28(5):42-45.

[10]鄔嘯,魏延,吳瑕.基于混合核函數(shù)的支持向量機(jī)[J].重慶理工大學(xué)學(xué)報(自然科學(xué)),2011,25(10):66-70.

[11]王健峰,張磊,陳國興等.基于改進(jìn)的網(wǎng)格搜索法的SVM參數(shù)優(yōu)化[J].應(yīng)用科技,2012,39(3):28-31.

責(zé)任編輯：王與

中圖分類號：TP301.6

文獻(xiàn)標(biāo)識碼：A

文章編號：1673-1794(2016)02-0030-03

作者簡介：劉曉瑩，安徽農(nóng)業(yè)大學(xué)信息與計算機(jī)學(xué)院碩士研究生；通信作者：楊寶華，農(nóng)業(yè)部農(nóng)業(yè)物聯(lián)網(wǎng)技術(shù)集成與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，安徽農(nóng)業(yè)大學(xué)信息與計算機(jī)學(xué)院副教授(合肥 230036)。

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61203217)，安徽農(nóng)業(yè)大學(xué)學(xué)科骨干培育項(xiàng)目(2014XKPY-62)

收稿日期：2015-11-15