支持向量機(jī)算法的研究

支持向量機(jī)算法的研究

現(xiàn)在，許多搜索算法已經(jīng)被分解。WEKA1支持向量機(jī)算法序列最小化算法即SMO算法是支持向量機(jī)（SupportVectorMachine）算法中的一種，而支持向量機(jī)是分類算法中的一種，它在解決小樣本、非線性及高位模式識別問題中表現(xiàn)出許多特有的優(yōu)勢，主要用來解決二值分類的模式識別問題。1.1svm訓(xùn)練算法支持向量機(jī)（SVM）方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折衷，以期獲得最好的推廣能力。SVM是從線性可分情況下的最優(yōu)分類面發(fā)展而來的。最優(yōu)分類面是指分類面不但能將兩類正確分類，而且使分類間隔最大。設(shè)樣本集：此時分類間隔等于2/||W||。滿足條件(1)且使2/||W||在該條件下對αα式中的求和實(shí)際上只對支持向量。b為分類閾值，可以通過任一個支持向量求出或通過兩類中任意一對支持向量取中值求得。通過對對偶問題的最優(yōu)解推導(dǎo)可以求出：上式為KKT條件。由于KKT條件是最優(yōu)解應(yīng)滿足的充要條件-公式(3)，所以目前提出的一些算法幾乎都是以是否違反KKT條件作為迭代策略的準(zhǔn)則。由于SVM方法有較好的理論基礎(chǔ)，它在一些領(lǐng)域的應(yīng)用中表現(xiàn)出來了優(yōu)秀的推廣性能，但是該算法在計(jì)算上存在著一些問題，包括訓(xùn)練算法速度慢、算法復(fù)雜而難以實(shí)現(xiàn)以及檢測階段運(yùn)算量大等等。SVM訓(xùn)練算法慢的主要原因首先是它需要計(jì)算和存儲核函數(shù)矩陣，當(dāng)樣本點(diǎn)數(shù)目較大時，需要很大的內(nèi)存，其次它在尋優(yōu)過程中要進(jìn)行大量的矩陣運(yùn)算，多數(shù)情況下，尋優(yōu)算法是占用算法時間的主要部分。因而，近年來提出的許多算法來解決對偶尋優(yōu)問題。大多數(shù)算法的一個共同思想就是循環(huán)迭代：將原問題分解為若干子問題，通過反復(fù)求解子問題，構(gòu)成原問題的近似解，并且使該近似解逐漸收斂到原問題的最優(yōu)解。代表的算法有選塊算法（chunking）1.2基于smo算法的乘子協(xié)同優(yōu)化SMO算法將原問題分解為若干子問題，而且子問題的規(guī)模最小-兩個樣本，即每次迭代過程中只調(diào)整相應(yīng)于兩個樣本點(diǎn)，它只求解一個具有兩個變量的最優(yōu)化問題假定工作集B={i,j}，每一步選擇出來優(yōu)化的兩個Lagrange乘子分別為α只要變動其中一個乘子，就必須同時調(diào)整另外一個乘子來保證不違反該約束。因而α假定選擇α然后將α其中：然后根據(jù)(4)式可以得出另外一個乘子更新后的值：SMO算法使用雙層循環(huán)這樣一種啟發(fā)式方法來選擇乘子進(jìn)行優(yōu)化。外層循環(huán)用來挑選第一個用于優(yōu)化的乘子，內(nèi)層循環(huán)用來挑選與第一個乘子協(xié)同優(yōu)化的第二個乘子。外層循環(huán)主要在界內(nèi)樣本（0<α其中：根據(jù)更新后的乘子以及閾值來更新Еi的值，從而完成了一次優(yōu)化過程。1.3訓(xùn)練大規(guī)模數(shù)據(jù)集子問題的規(guī)模和整個算法需要迭代的次數(shù)是矛盾的，SMO算法將工作集的規(guī)模減到最小，一個直接的后果就是迭代次數(shù)的增加。雖然該算法的優(yōu)點(diǎn)在于通過兩個變量的最優(yōu)化問題來解析求解，得到這兩個變量的最優(yōu)值，然后來改進(jìn)相應(yīng)的向量的分量，但是好的算法卻難在實(shí)現(xiàn)手法上。實(shí)現(xiàn)的手法不一樣，達(dá)到的效果不同甚至是差別巨大。事實(shí)上，SMO算法對二進(jìn)制數(shù)據(jù)以及稀疏數(shù)據(jù)比較敏感，比較適用于多值分類，在二值分類時，訓(xùn)練大規(guī)模數(shù)據(jù)集時效率低下。在WEKA中用SMO訓(xùn)練大規(guī)模數(shù)據(jù)集時由于訓(xùn)練樣本的線性增加，迭代次數(shù)增加，用于搜索乘子以及更新乘子和相應(yīng)值的時間花費(fèi)巨大，而且所需的內(nèi)存空間劇增，常常要經(jīng)過多次嘗試后才能確定一個適合當(dāng)前樣本集的JavaHeap。以48842個樣本集為例，經(jīng)過實(shí)驗(yàn)，采用十折交叉驗(yàn)證1.4利用五個工作集提供大量的空間在WEKA中，SMO算法主要通過以下方式來實(shí)現(xiàn)對整個訓(xùn)練集和界內(nèi)樣本中違反KKT條件的乘子的查找：采取五個工作集這樣一種策略：I算法實(shí)現(xiàn)的主要步驟如表1所示：更新函數(shù)的主要步驟如表2所示：在這種策略下，當(dāng)訓(xùn)練樣本集規(guī)模大時，最直接的后果就是需要為這五個工作集開辟大量的存儲空間，每次搜索違反KKT條件的樣本需要遍歷五個工作集，而更新一對乘子后需要將更新后的值分別放入五個工作集中，浪費(fèi)了大量的時間和空間。綜上所述，用五個工作集來分別存放樣本并不是最好的方式。因而，可以嘗試用另外的三個工作集來代替五個工作集：分別是I這樣做的好處有如下幾點(diǎn)：初始化時節(jié)省了40%的存儲空間；在搜索乘子和更新乘子時大量的減少了判斷次數(shù)，大大降低了算法的復(fù)雜度，節(jié)省了時間；在能保持原算法的分類效果不變的情況下，提高了訓(xùn)練效率，從而使算法的性能得到優(yōu)化。在另外一方面，又使得WEKA軟件的運(yùn)用更加廣泛。2實(shí)驗(yàn)數(shù)據(jù)集與分析本實(shí)驗(yàn)采用改進(jìn)前后的SMO算法分類效果以及效率的對比來得出相關(guān)結(jié)論。在進(jìn)行該實(shí)驗(yàn)時，為了有對比性，采用公共數(shù)據(jù)集，并且在相同的軟硬件環(huán)境下，使實(shí)驗(yàn)結(jié)果更可靠。Adult數(shù)據(jù)集是美國埃威爾分校UCI官網(wǎng)分享的一個數(shù)據(jù)集，該數(shù)據(jù)集有48842個實(shí)例。在進(jìn)行預(yù)處理后，為了證明改進(jìn)后的算法對小樣本有同樣的效果，隨機(jī)挑選了796個樣本以及3215個樣本共同實(shí)驗(yàn)，采用十折交叉驗(yàn)證的方法評價(jià)算法的好壞，選擇Poly核函數(shù)，下表為算法改進(jìn)前后對比的實(shí)驗(yàn)結(jié)果。從表3可知，改進(jìn)后的算法在時間上比標(biāo)準(zhǔn)版的SMO算法相比，減少了一半以上，在分類正確率上與原來相比相差無幾。而且，改進(jìn)后的算法在內(nèi)存上，比原來的要求低得多。以48842個樣本為例，改進(jìn)后的算法跟原來的相比，存儲空間的要求降低了40%。3改進(jìn)的smo算法的對比本文通過對SMO分類算法的研