基于map和redule并行的svm分類算法

基于map和redule并行的svm分類算法

0svm分類算法的特點(diǎn)云計算是互聯(lián)網(wǎng)發(fā)展的產(chǎn)物。大多數(shù)基于網(wǎng)絡(luò)統(tǒng)計和分析的數(shù)據(jù)都是大規(guī)模和有限的數(shù)據(jù)。面對如此龐大且不斷增長的數(shù)據(jù)信息,如何高效、準(zhǔn)確地組織和分類這些數(shù)據(jù)信息是當(dāng)代信息科學(xué)技術(shù)領(lǐng)域的一大難題。傳統(tǒng)平臺在數(shù)據(jù)分類時效率低下,有2個主要原因:傳統(tǒng)平臺在很大程度上受到了計算力伸縮性的制約,平臺的計算力不易得到擴(kuò)展和伸縮;分類算法大多以串行的方式運(yùn)行,很少被并行化處理,分類過程不能高效并行化進(jìn)行。SVM(supportvectormachine,支持向量機(jī))分類算法有很好的泛化能力與學(xué)習(xí)能力。該算法是以結(jié)構(gòu)風(fēng)險最小化為目標(biāo),所求得的解是全局最優(yōu)解。該算法可以解決“維數(shù)災(zāi)難”問題。但SVM分類算法的分類準(zhǔn)確度易受到數(shù)據(jù)集、分類器及訓(xùn)練參數(shù)的影響,傳統(tǒng)的支持向量機(jī)模型參數(shù)及其核函數(shù)參數(shù)的取值大多都是隨機(jī)值或經(jīng)驗值,隨機(jī)性和主觀經(jīng)驗性過強(qiáng),這導(dǎo)致分類的準(zhǔn)確度不高。筆者在云計算環(huán)境下為數(shù)據(jù)分類提供彈性的集群計算力來滿足計算的需求,使平臺的計算力得到擴(kuò)展,并在其平臺下對分類算法進(jìn)行MapReduce并行化處理和運(yùn)行,利用基于優(yōu)化理論的遺傳算法對支持向量機(jī)模型參數(shù)和核函數(shù)參數(shù)進(jìn)行優(yōu)化,對數(shù)據(jù)進(jìn)行實驗仿真,與未優(yōu)化的SVM算法進(jìn)行了對比以驗證算法的有效性。1麥擦模型和應(yīng)用1.1map+rin-pcr的算法組成、特點(diǎn)MapReduce采用“分而治之”的思想,把對大規(guī)模數(shù)據(jù)集的操作,分發(fā)給一個主節(jié)點(diǎn)管理下的各分節(jié)點(diǎn)共同完成,通過整合各分節(jié)點(diǎn)的中間結(jié)果而得到最終結(jié)果。包括Map、Partition、Shuffle、Combine、Sort、Reduce這幾個過程。中間過程的功能可以合并到Map、Reduce中,主要用于實現(xiàn)對Map、Reduce兩個過程的性能優(yōu)化。上述處理過程能被高度抽象為2個函數(shù),即Map和Reduce:Map負(fù)責(zé)把任務(wù)分解成多個任務(wù);Reduce負(fù)責(zé)把分解后多任務(wù)處理的結(jié)果匯總起來。在Map階段,MapReduce框架將任務(wù)的輸入數(shù)據(jù)分割成固定大小的片段(Splits),隨后將每個Split進(jìn)一步分解成一批鍵值對<K1,V1>。Hadoop為每個Split創(chuàng)建一個Map任務(wù),用于執(zhí)行用戶自定義的Map函數(shù),并將對應(yīng)Split中的<K1,V1>對作為輸入,得到計算的中間結(jié)果<K2,V2>。接著將中間結(jié)果按照K2進(jìn)行排序,并將Key值相同的Value放在一起形成一個新的列表,形成<K2,list(V2)>元組。最后再根據(jù)Key值的范圍對這些元組進(jìn)行分組,對應(yīng)不同的Reduce任務(wù)。在Reduce階段,Reduce把從不同Map接收來的數(shù)據(jù)整合在一起并進(jìn)行排序,然后調(diào)用用戶自定義的Reduce函數(shù),對輸入的<K2,list(V2)>對進(jìn)行相應(yīng)的處理,得到鍵值對<K3,V3>并輸出到HDFS(hadoopdistributedfilesystem)上(圖1)。1.2子測試分類結(jié)果在svm算法相比傳統(tǒng)的單機(jī)進(jìn)行SVM數(shù)據(jù)分類來說,單機(jī)要完成對整個數(shù)據(jù)集的運(yùn)算,但在Hadoop平臺上計算力容易得到擴(kuò)展和伸縮,根據(jù)MapReduce的并行計算特點(diǎn),可以利用Map操作和Reduce操作在多個子計算節(jié)點(diǎn)(DataNode)上同時進(jìn)行數(shù)據(jù)處理。根據(jù)SVM算法數(shù)據(jù)分類的原理可知,在分類之前必須先求出分類模型,也就是要用Map操作找出所有子訓(xùn)練數(shù)據(jù)里面的子支持向量SVs(supportvectors),然后利用Reduce操作再將各個子計算節(jié)點(diǎn)上的子支持向量進(jìn)行合并,匯總成關(guān)于數(shù)據(jù)集的完整的支持向量AllSVs(allsupportvectors),這些完整的支持向量才能唯一確定數(shù)據(jù)的分類超平面,即通過支持向量而得到最終的分類器;然后再利用分類器對每個子計算節(jié)點(diǎn)上的子測試數(shù)據(jù)進(jìn)行Map操作,得出子分類測試結(jié)果Rs(results),進(jìn)一步利用Reduce操作將這些子計算節(jié)點(diǎn)上的子測試分類結(jié)果進(jìn)行合并匯總,得到最終的分類結(jié)果AllRs(allresults)。具體的流程如圖2所示。2采用遺傳統(tǒng)計法優(yōu)化svm模型參數(shù)和選定核函數(shù)參數(shù)2.1參數(shù)的最優(yōu)化處理在開源云計算平臺Hadoop下基于SVM的大規(guī)模數(shù)據(jù)分類的過程可以描述成下述步驟:(1)首先要將其數(shù)據(jù)進(jìn)行預(yù)處理(清理、規(guī)范化),然后再將數(shù)據(jù)分塊成為滿足HDFS要求的數(shù)據(jù)塊,并存儲在集群的各個機(jī)器上;(2)SVM分類器模型以及相關(guān)核函數(shù)的選取。本文選取的SVM模型為帶懲罰參數(shù)的模型和分類準(zhǔn)確度比較高的徑向基核函數(shù)(RBF);(3)參數(shù)的最優(yōu)化處理。本文利用遺傳算法來尋找SVM模型參數(shù)和核函數(shù)參數(shù)的最優(yōu)參數(shù)值;(4)對樣本數(shù)據(jù)進(jìn)行訓(xùn)練和預(yù)測。利用步驟(3)得到的最優(yōu)化參數(shù)對訓(xùn)練數(shù)據(jù)進(jìn)行訓(xùn)練,將訓(xùn)練得到的分類模型用于測試數(shù)據(jù)的測試。2.2基于ga的svm模型優(yōu)化遺傳算法(geneticalgorithm,GA)是一種基于生物遺傳和進(jìn)化機(jī)制的,適合復(fù)雜系統(tǒng)、多目標(biāo)問題優(yōu)化的自適應(yīng)概率優(yōu)化技術(shù)。它具有較強(qiáng)的實用性、高效性,魯棒性強(qiáng)、全局尋優(yōu)以及內(nèi)在的隱并行性的特點(diǎn),并且它沒有傳統(tǒng)搜索算法的函數(shù)連續(xù)性和求導(dǎo)的局限性,已經(jīng)在很多領(lǐng)域得到了廣泛的應(yīng)用。利用GA對SVM模型參數(shù)和核函數(shù)參數(shù)進(jìn)行優(yōu)化的過程如圖3所示。圖3中利用GA對SVM模型參數(shù)c和核函數(shù)參數(shù)g進(jìn)行優(yōu)化的具體步驟如下所示:(1)輸入經(jīng)過預(yù)處理后的訓(xùn)練數(shù)據(jù)樣本;(2)GA相關(guān)參數(shù)及SVM模型參數(shù)和核函數(shù)參數(shù)的初始化;(3)利用隨機(jī)函數(shù)初始化種群,以SVM算法所求得的準(zhǔn)確度作為個體適應(yīng)度函數(shù);(4)確定適應(yīng)度的標(biāo)準(zhǔn);(5)判斷當(dāng)前的個體極值是否為種群的全局最優(yōu)解,如果是,就確定最優(yōu)解;若不是,則種群代數(shù)增加進(jìn)行循環(huán)操作,對GA的個體進(jìn)行選擇、變異、交叉操作,產(chǎn)生新個體,并計算出新個體的適應(yīng)度值;(6)確定最終的最優(yōu)解,并輸出相應(yīng)的最優(yōu)解(Bestc&g)。3參數(shù)優(yōu)化后分類準(zhǔn)確度c=0.75,Pm=0.25;SVM模型參數(shù)c取值范圍為1~100,核函數(shù)參數(shù)g取值范圍為0~800?；谶z傳算法對SVM模型參數(shù)c和核函數(shù)參數(shù)g尋優(yōu)的結(jié)果如圖4所示。由圖4得出,GA算法在進(jìn)化代數(shù)為75代時停止進(jìn)化,并在此找到了基于全局最優(yōu)的SVM模型參數(shù)c值為40.005,核函數(shù)參數(shù)g值為0.073242。數(shù)據(jù)分類模型訓(xùn)練的優(yōu)良與否和分類準(zhǔn)確度的高低都與數(shù)據(jù)樣本質(zhì)量有著密切的關(guān)系,因此在此實驗之前本文已經(jīng)對數(shù)據(jù)進(jìn)行了去噪、規(guī)范化、降維等前期預(yù)處理。表1是由實驗得出的參數(shù)優(yōu)化前后分類準(zhǔn)確度的對比。經(jīng)實驗對比可見,通過對SVM模型參數(shù)和核函數(shù)參數(shù)運(yùn)用GA算法進(jìn)行優(yōu)化處理后,前兩個數(shù)據(jù)集分類的準(zhǔn)確度都有明顯的提高,第3個數(shù)據(jù)集測試集樣本數(shù)比訓(xùn)練集樣本數(shù)要大一些,導(dǎo)致一定程度的欠學(xué)習(xí),從而導(dǎo)致訓(xùn)練的模型精度不高,所以經(jīng)過尋優(yōu)處理后分類精度提高的不是十分明顯?？傮w而言,經(jīng)優(yōu)化后的分類準(zhǔn)確度比傳統(tǒng)未優(yōu)化的分類準(zhǔn)確度效果更好,該方法具有一定的實用性。為了衡量數(shù)據(jù)在開源云計算平臺Hadoop集群上運(yùn)行的效率,本文定義一個加速度比的變量:加速度比(speedup)=傳統(tǒng)單機(jī)平臺運(yùn)行時間/Hadoop集群平臺運(yùn)行時間。3個數(shù)據(jù)集分類加速度比的實驗運(yùn)行結(jié)果見圖5。可以看到,單機(jī)的運(yùn)行效率比單個Hadoop計算節(jié)點(diǎn)運(yùn)行的效率要高一些,這是因為單個Hadoop節(jié)點(diǎn)需要額外加載一些Hadoop平臺運(yùn)行相關(guān)的系統(tǒng)資源,這樣就導(dǎo)致了計算分類的資源減少了,從而效率沒有單機(jī)速度快。由于集群節(jié)點(diǎn)之間有相互的網(wǎng)絡(luò)通信、數(shù)據(jù)的傳輸以及同步開銷,所以分類的加速度比不會隨著節(jié)點(diǎn)個數(shù)的增加而達(dá)到絕對的線性增加。但總體而言,SVM數(shù)據(jù)分類經(jīng)過MapReduce處理后,隨著Hadoop集群上節(jié)點(diǎn)數(shù)的動態(tài)伸縮性的增加,加速度比也在呈現(xiàn)較為平緩的增加,因此,該方法對提高數(shù)據(jù)分類效率有一定的實用性和可行性。4svm分類算法的優(yōu)化分析了傳統(tǒng)平臺進(jìn)行數(shù)據(jù)分類時的平臺計算力伸縮性的瓶頸和分類算法未并行化執(zhí)行的局限性,并從SVM的原理出發(fā),討論了SVM分類算法在分類模型和相關(guān)核函數(shù)在參數(shù)選擇上的不足,因此,本文利用普通PC機(jī)器組成Hadoop集群平臺來滿足計算力伸縮性需求,在此平臺上發(fā)揮MapReduce并行性的優(yōu)勢,使分類算法的執(zhí)行能在較短時間內(nèi)完成分類任務(wù),并運(yùn)用GA算法對SVM模型參數(shù)和核函數(shù)參數(shù)取值進(jìn)行了優(yōu)化處理,從局部上改善了SVM