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

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

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