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

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

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