基于map和redule并行的svm分類(lèi)算法

基于map和redule并行的svm分類(lèi)算法

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