基于Hadoop平臺(tái)的SVM_KNN分類算法的研究

李正杰，黃 剛

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

基于Hadoop平臺(tái)的SVM_KNN分類算法的研究

李正杰，黃 剛

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

數(shù)據(jù)的變革帶來(lái)了前所未有的發(fā)展，對(duì)豐富且復(fù)雜的結(jié)構(gòu)化、半結(jié)構(gòu)化或者是非結(jié)構(gòu)化數(shù)據(jù)的監(jiān)測(cè)、分析、采集、存儲(chǔ)以及應(yīng)用，已經(jīng)成為了數(shù)據(jù)信息時(shí)代發(fā)展的主流，分類和處理海量數(shù)據(jù)包含的信息，需要有更好的解決方法。傳統(tǒng)的數(shù)據(jù)挖掘分類方式顯然已經(jīng)不能滿足需求，面對(duì)這些問(wèn)題，這里對(duì)數(shù)據(jù)挖掘的一些分類算法進(jìn)行分析和改進(jìn)，對(duì)算法進(jìn)行結(jié)合，提出了改進(jìn)的SVM_KNN分類算法。在這個(gè)基礎(chǔ)上，利用Hadoop云計(jì)算平臺(tái)，將研究后的分類算法在MapReduce模型中進(jìn)行并行化應(yīng)用，使改進(jìn)后的算法能夠適用于大數(shù)據(jù)的處理。最后用數(shù)據(jù)集對(duì)算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，通過(guò)對(duì)比傳統(tǒng)的SVM分類算法，結(jié)果表明改進(jìn)后的算法達(dá)到了高效、快速、準(zhǔn)確、低成本的要求，可以有效地進(jìn)行大數(shù)據(jù)分類工作。

數(shù)據(jù)挖掘；Hadoop；并行化；SVM_KNN

0 引 言

當(dāng)下的時(shí)代是一個(gè)急需對(duì)數(shù)據(jù)進(jìn)行高效快速挖掘的時(shí)代，而分類是數(shù)據(jù)挖掘的一項(xiàng)首要任務(wù)和技術(shù)。分類可以看成是數(shù)據(jù)庫(kù)到一組類別的映射，需要構(gòu)造一個(gè)分類器，輸入一個(gè)樣本數(shù)據(jù)集，通過(guò)在訓(xùn)練集中的數(shù)據(jù)表現(xiàn)出來(lái)的特性，為每一個(gè)類找到一種準(zhǔn)確的描述或者模型[1]，從而利用分類對(duì)未來(lái)的數(shù)據(jù)進(jìn)行預(yù)測(cè)。SVM算法非常適合解決結(jié)構(gòu)復(fù)雜的數(shù)據(jù)，而針對(duì)SVM算法的缺點(diǎn)，KNN算法可以簡(jiǎn)單有效地彌補(bǔ)。文中結(jié)合這兩種算法，并對(duì)其加以改進(jìn)，來(lái)對(duì)數(shù)據(jù)進(jìn)行更精確的分類。龐大而復(fù)雜的數(shù)據(jù)對(duì)數(shù)據(jù)分類處理的準(zhǔn)度和精度有著極高的需求，互聯(lián)網(wǎng)和計(jì)算機(jī)技術(shù)的發(fā)展產(chǎn)生了云計(jì)算技術(shù)，Hadoop則是其中的優(yōu)秀代表。Hadoop是可由大量低成本計(jì)算機(jī)構(gòu)成的，能夠可靠地分布式處理大數(shù)據(jù)的軟件框架，是一個(gè)可以進(jìn)行云計(jì)算應(yīng)用和研究的平臺(tái)。云計(jì)算技術(shù)的出現(xiàn)為數(shù)據(jù)挖掘的發(fā)展提供了強(qiáng)大的推動(dòng)力，將Hadoop應(yīng)用于數(shù)據(jù)挖掘技術(shù)中，對(duì)數(shù)據(jù)挖掘分類算法進(jìn)行并行化處理后，在Hadoop云平臺(tái)上運(yùn)行，可以極大提高數(shù)據(jù)挖掘分類的準(zhǔn)確性和效率。

1 Hadoop平臺(tái)

Hadoop以HDFS[2]和MapReduce[3]為核心。HDFS參照了谷歌的分布式文件系統(tǒng)(GFS)，是Hadoop的分布式文件系統(tǒng)，為分布式的計(jì)算提供了底層的支持。它的機(jī)制和以前的分布式文件系統(tǒng)有很多相似之處，但是HDFS以大數(shù)據(jù)、大文件和低成本等要求進(jìn)行了設(shè)計(jì)，而且容錯(cuò)率比較高，適合布置在低成本的計(jì)算機(jī)上，能夠提供非常大的系統(tǒng)吞吐量并處理一些非常大的文件。而MapReduce是Hadoop的技術(shù)核心，它是為大數(shù)據(jù)處理提供的可以利用底層分布式環(huán)境的編程模型，在不用關(guān)心底層細(xì)節(jié)的情況下為用戶提供接口，這讓它顯得非常簡(jiǎn)單，而且具有強(qiáng)大的可擴(kuò)展性和可伸縮性。MapReduce編程模型的計(jì)算過(guò)程分為兩部分：Map階段和Reduce階段，即映射與規(guī)約。Map階段就是將一個(gè)任務(wù)分解成多個(gè)任務(wù)，Map把原始的數(shù)據(jù)通過(guò)函數(shù)定義的映射過(guò)程進(jìn)行轉(zhuǎn)換和過(guò)濾，獲得中間的數(shù)據(jù)作為Reduce階段的輸入，然后對(duì)生成的中間數(shù)據(jù)也按照函數(shù)定義的處理過(guò)程進(jìn)行規(guī)約處理，Reduce會(huì)獲得最終的結(jié)果。Hadoop可以充分利用集群中的節(jié)點(diǎn)進(jìn)行大規(guī)模數(shù)據(jù)存儲(chǔ)和高速運(yùn)算[4]。

Hadoop具有可靠、可擴(kuò)展、高效、高可用性、低成本和具有完備的容錯(cuò)機(jī)制等優(yōu)點(diǎn)。基于這些優(yōu)點(diǎn)，Hadoop被諸如IBM、亞馬遜、雅虎、百度、騰訊和阿里巴巴等企業(yè)大量運(yùn)用和改善，用以開(kāi)發(fā)更完善的云計(jì)算平臺(tái)[5-6]。

2 數(shù)據(jù)挖掘分類方法的基本原理

對(duì)數(shù)據(jù)進(jìn)行合理有效的分類在數(shù)據(jù)挖掘的整個(gè)過(guò)程中顯得十分重要。分類的目的是構(gòu)造出一個(gè)分類器，分類器再把數(shù)據(jù)庫(kù)中的數(shù)據(jù)項(xiàng)和給定類別中的某一個(gè)類別對(duì)應(yīng)起來(lái),實(shí)現(xiàn)分類的目的，然后進(jìn)行預(yù)測(cè)分析。分類是否有效準(zhǔn)確將會(huì)直接影響到數(shù)據(jù)挖掘最終結(jié)果的有效性和準(zhǔn)確性[7]。分類在醫(yī)療、模式識(shí)別、信息等領(lǐng)域應(yīng)用廣泛。

數(shù)據(jù)挖掘分類一般分成兩個(gè)步驟：建立模型和使用模型。要對(duì)數(shù)據(jù)進(jìn)行有效的挖掘，首先需要通過(guò)分析數(shù)據(jù)庫(kù)中元組來(lái)構(gòu)造一個(gè)模型，用來(lái)對(duì)預(yù)定的數(shù)據(jù)類集進(jìn)行描述。這些數(shù)據(jù)庫(kù)元組被稱為訓(xùn)練數(shù)據(jù)集，訓(xùn)練集中的單個(gè)元組被稱為樣本，每個(gè)樣本有一個(gè)特定的類標(biāo)簽和它對(duì)應(yīng)。一般情況下，學(xué)習(xí)的模型可以由分類規(guī)則、決策樹(shù)或者等式、不等式等形式提供，這些規(guī)則可以為后面的數(shù)據(jù)樣本進(jìn)行分類，即第二步使用模型進(jìn)行分類。在使用之前，首先需要評(píng)估模型的預(yù)測(cè)準(zhǔn)確率，評(píng)估過(guò)后如果認(rèn)為可以接受模型的準(zhǔn)確率，那么就可以開(kāi)始使用模型對(duì)未知的數(shù)據(jù)進(jìn)行分類。

目前來(lái)說(shuō)，分類模型的構(gòu)造主要有以下方法：統(tǒng)計(jì)、機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)等。統(tǒng)計(jì)方法主要包括貝葉斯法、一些常見(jiàn)的近鄰算法和基于事例的學(xué)習(xí)[8]等。機(jī)器學(xué)習(xí)方法包括規(guī)則歸納法，如決策表、產(chǎn)生式規(guī)則和決策樹(shù)法(如決策樹(shù)、判別樹(shù))。而神經(jīng)網(wǎng)絡(luò)方法主要?jiǎng)t是BP算法，一種非線性的判別函數(shù)[9]。一些如粗糙集等方法也可以用來(lái)構(gòu)造分類器。大體上，分類的方法主要有基于距離的分類方法、貝葉斯分類方法、決策樹(shù)分類方法、規(guī)則歸納方法等。具體則有許多不同的算法，像支持向量機(jī)算法、K-近鄰算法、樸素貝葉斯算法、C4.5算法、AQ算法等。

3 SVM_KNN分類算法

3.1 SVM算法

支持向量機(jī)(Support Vector Machine,SVM)算法是在1995年由Vapnik提出的[10]，一種基于統(tǒng)計(jì)學(xué)習(xí)理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論的機(jī)器學(xué)習(xí)方法[11]。它是針對(duì)兩種類別分類的算法，具有優(yōu)秀的泛化能力，適合于解決那些維度高的非線性數(shù)據(jù)的問(wèn)題，因此在分類、識(shí)別、檢索等方面得到了非常廣泛的應(yīng)用。

SVM算法的基本思想在于：找到一個(gè)最優(yōu)分類超平面，它能滿足分類的要求和精度，并且超平面的兩側(cè)空白空間能夠最大。如圖1和圖2所示，兩幅圖中的

圖1 一般分類超平面

圖2 最優(yōu)分類超平面

超平面均能起到分類的效果，但是圖2中超平面兩側(cè)空白的空間最大，所以它是最優(yōu)分類超平面，而分隔邊界如L1,L2上的樣本點(diǎn)稱為支持向量。

(1)

(2)

(3)

構(gòu)造拉格朗日函數(shù)即可求得最終的決策函數(shù)為：

(4)

其中:ai是拉格朗日系數(shù);b*是分類閾值。

如果訓(xùn)練樣本線性不可分，那么則需要引入非負(fù)松弛變量εi,i=1,2,…,n，則其最小化函數(shù)為：

(5)

其中,C是一個(gè)懲罰參數(shù)。

對(duì)于非線性的樣本集，需要通過(guò)一種非線性的映射將輸入向量映射到一個(gè)高維特征空間，在這個(gè)空間里構(gòu)造出最優(yōu)分類超平面。這種非線性的變化可以通過(guò)核函數(shù)來(lái)轉(zhuǎn)變[12]。

3.2 KNN算法

KNN(K-NearestNeighbor)算法是由Cover和Hart于1968年提出的[13]，一種基于距離、基于實(shí)例的非參數(shù)方法。KNN算法是一種懶惰的學(xué)習(xí)算法，它的基本思想比較容易理解：空間中的每一個(gè)訓(xùn)練數(shù)據(jù)都作為一個(gè)點(diǎn)，給出一個(gè)需要測(cè)試的數(shù)據(jù)，在這個(gè)空間中通過(guò)相似度算法找出與這個(gè)待測(cè)試數(shù)據(jù)最相似的K個(gè)最近鄰點(diǎn)，統(tǒng)計(jì)出這K個(gè)最近鄰點(diǎn)中哪個(gè)類的個(gè)數(shù)最多，則認(rèn)為測(cè)試數(shù)據(jù)屬于該類,如圖3所示。

當(dāng)K=4時(shí)，4個(gè)最近鄰點(diǎn)中有3個(gè)I類點(diǎn)，一個(gè)II類點(diǎn)，所以認(rèn)為待測(cè)數(shù)據(jù)屬于I類；當(dāng)K=7時(shí)，7個(gè)最近鄰點(diǎn)中有3個(gè)I類點(diǎn)，4個(gè)II類點(diǎn)，所以此時(shí)認(rèn)為待測(cè)數(shù)據(jù)屬于II類。

3.3 SVM_KNN分類算法原理及其改進(jìn)

KNN算法雖然簡(jiǎn)單有效，但是仍然存在很多不足。在KNN算法中，對(duì)于每一個(gè)待測(cè)數(shù)據(jù)都需要計(jì)算它與空間中每個(gè)樣本的相似度后，才能進(jìn)行比較，得到K個(gè)最近鄰點(diǎn)，因此KNN算法的計(jì)算量比較大。另外，由于算法對(duì)每個(gè)樣本都賦予了相同的權(quán)重，認(rèn)為每個(gè)特征對(duì)分類的作用都是一樣的[14]，所以當(dāng)樣本的分布不是很平均時(shí)，可能會(huì)導(dǎo)致輸入的待測(cè)數(shù)據(jù)被分到樣本容量大的那一方，造成錯(cuò)誤分類的情況。

圖3 KNN算法示例

而對(duì)于SVM算法，Vapnik通過(guò)分析指出，在對(duì)兩個(gè)類別進(jìn)行分類時(shí)，SVM算法在兩個(gè)類別的邊界區(qū)域或重疊區(qū)域的樣本會(huì)存在一定的分類錯(cuò)誤[10]，經(jīng)過(guò)對(duì)誤分樣本的分布情況進(jìn)行研究后，可以發(fā)現(xiàn)SVM算法一般誤分都發(fā)生在最優(yōu)分類面的附近[15]。

SVM分類器可以看作是每個(gè)類只有一個(gè)代表點(diǎn)的最近鄰分類器[15]，所以可以考慮將SVM算法和KNN算法結(jié)合起來(lái)產(chǎn)生一種新的算法，即SVM_KNN算法，在這個(gè)基礎(chǔ)上，對(duì)SVM算法選取合適的懲罰參數(shù)和核函數(shù)，文中采用的核函數(shù)為徑向基核函數(shù)。對(duì)KNN算法采取加入權(quán)重系數(shù)的方式，權(quán)重系數(shù)可以通過(guò)某個(gè)類的樣本數(shù)占所有樣本數(shù)的比重來(lái)求得，在計(jì)算待測(cè)數(shù)據(jù)到某個(gè)類樣本的距離時(shí)，用這個(gè)類的權(quán)重系數(shù)乘以距離，所得的結(jié)果作為比較依據(jù)，使得樣本容量大的一類占的權(quán)重變小，樣本容量小的一類占的權(quán)重變大，來(lái)盡可能避免樣本分布不均所帶來(lái)的分類影響。同時(shí)，還可以使用效果更穩(wěn)定的向量空間余弦相似度來(lái)代替KNN算法中的歐氏距離相似度。改進(jìn)后的SVM_KNN算法對(duì)原來(lái)的兩種算法進(jìn)行了優(yōu)劣互補(bǔ)，在性能上進(jìn)行了優(yōu)化，也不需要KNN算法進(jìn)行大量的計(jì)算，提高了分類的準(zhǔn)確性。

圖4 SVM_KNN算法

SVM_KNN算法的主要實(shí)現(xiàn)步驟如下：

(1)采用樣本訓(xùn)練集對(duì)SVM算法進(jìn)行訓(xùn)練，求出分類決策函數(shù)(式(4))中的系數(shù)w和常數(shù)b，得到支持向量集Dsv，給定閾值ξ，并對(duì)測(cè)試數(shù)據(jù)集D進(jìn)行預(yù)處理；

(2)若D為空，則停止步驟的進(jìn)行，若D不為空，則從D中取出待分類數(shù)據(jù)x；

(4)若dis>ξ，則選定好合適的核函數(shù)，用SVM算法進(jìn)行分類，最后輸出式(4)的f(x)；

(5)若dis<ξ，則使用KNN算法進(jìn)行分類，選定好K的值，輸入待分類數(shù)據(jù)x，用支持向量集Dsv作為樣本點(diǎn)，在距離計(jì)算中加入權(quán)重系數(shù)平衡樣本，輸出最后的結(jié)果；

(6)從測(cè)試數(shù)據(jù)集D去除已分類好的數(shù)據(jù)x，返回步驟(2)繼續(xù)執(zhí)行。

3.4 SVM_KNN分類算法的并行化處理

從上文可知，首先需要用樣本訓(xùn)練集對(duì)SVM算法進(jìn)行訓(xùn)練，而SVM算法主要是找出支持向量，稀疏性是支持向量的特性，即支持向量在訓(xùn)練樣本集中占的比例很小。利用這個(gè)特性，可以先對(duì)數(shù)據(jù)量大的訓(xùn)練數(shù)據(jù)集進(jìn)行分塊處理，因?yàn)楦鱾€(gè)分塊一般來(lái)說(shuō)具有獨(dú)立性，可以將其并行化處理，分塊處理進(jìn)行訓(xùn)練可以減少SVM算法的訓(xùn)練時(shí)間。

對(duì)于分好的小數(shù)據(jù)集，可以采用SMO算法[16]進(jìn)行訓(xùn)練以加快效率得到每個(gè)小數(shù)據(jù)集的支持向量集，當(dāng)然不能簡(jiǎn)單地通過(guò)疊加每個(gè)小數(shù)據(jù)集的支持向量集得出最后整個(gè)訓(xùn)練數(shù)據(jù)集的支持向量集，這樣可能導(dǎo)致得到的支持向量集有著明顯的偏差。因此在對(duì)大數(shù)據(jù)集進(jìn)行分塊時(shí)，應(yīng)保持分塊的均衡性，使得每個(gè)分塊不同類別的比例和原有比例相近，對(duì)每個(gè)分塊進(jìn)行訓(xùn)練，過(guò)濾非支持向量點(diǎn)，保留支持向量點(diǎn)，然后兩個(gè)分塊的訓(xùn)練結(jié)果經(jīng)過(guò)整合后作為下一個(gè)輸入。就這樣一直迭代直到剩下最后一個(gè)支持向量集，然后判斷這個(gè)集合是不是達(dá)到了迭代精度，如果達(dá)到了，則輸出最后得到的支持向量集、系數(shù)w和常數(shù)b。通過(guò)對(duì)初始數(shù)據(jù)集進(jìn)行分塊處理，可以極大提高SVM算法的訓(xùn)練速度，也使訓(xùn)練準(zhǔn)確度有一定的保證。

訓(xùn)練好SVM分類器之后，對(duì)測(cè)試數(shù)據(jù)同樣進(jìn)行分塊處理。在均分了測(cè)試數(shù)據(jù)后，從測(cè)試數(shù)據(jù)分塊中依次取出數(shù)據(jù)在各自節(jié)點(diǎn)上進(jìn)行計(jì)算，得到3.3小節(jié)中的dis，再與給定的閾值ξ進(jìn)行比較，從而讓各節(jié)點(diǎn)選擇使用SVM算法或使用KNN算法進(jìn)行分類。所有測(cè)試數(shù)據(jù)分類完成后，對(duì)各節(jié)點(diǎn)的分類結(jié)果進(jìn)行統(tǒng)一處理和分析。

以上就是SVM_KNN分類算法并行化處理的基本思路，可以將并行化后的SVM_KNN分類算法稱之為hSVM_KNN分類算法。根據(jù)這個(gè)思路，實(shí)現(xiàn)hSVM_KNN分類算法需要4對(duì)MapReduce函數(shù)，分別是迭代訓(xùn)練產(chǎn)生支持向量集、系數(shù)w和常數(shù)b的函數(shù)：IterationMapper函數(shù)和IterationReducer函數(shù)；求出dis的函數(shù)：DisMapper函數(shù)和DisReducer函數(shù)；SVM分類算法的函數(shù)：SVMMapper函數(shù)和SVMReducer函數(shù)；KNN分類算法的函數(shù)：KNNMapper函數(shù)和KNNReducer函數(shù)。hSVM_KNN分類算法的并行化算法偽代碼如下：

FunctionIteration//訓(xùn)練迭代算法

Begin

//將樣本訓(xùn)練集分塊，放入各節(jié)點(diǎn)中處理

Split();

While(不止有一個(gè)支持向量集)do

//求出各分塊的支持向量集

IterationMapper函數(shù);

//對(duì)IterationMapper函數(shù)傳來(lái)的key/value形式的支持向量集兩兩進(jìn)行合并處理

IterationReducer函數(shù);

If最后的支持向量集達(dá)到迭代精度then

//返回最后的支持向量集Dsv，系數(shù)w和常數(shù)b

ReturnDsv，w，b;

Else

//如果不滿足迭代精度，則進(jìn)行迭代處理

CallIteration;

Endif

End

FunctionDis//求出dis的函數(shù)

Begin

//對(duì)測(cè)試數(shù)據(jù)集進(jìn)行分塊，放入各節(jié)點(diǎn)中處理

Split_dis();

For分塊中的測(cè)試數(shù)據(jù)集D′do

//求得各分塊中的dis

DisMapper函數(shù);

//對(duì)DisMapper函數(shù)傳來(lái)的key/value形式的dis進(jìn)行處理

DisReducer函數(shù);

Returndis;

End

Ifdis大于給定的閾值ξthen使用SVM分類算法進(jìn)行分類;

FunctionSVM//SVM分類算法

Begin

//對(duì)dis大于閾值ξ的進(jìn)行分塊，放入各節(jié)點(diǎn)處理

Split_SVM();

For分塊中的每個(gè)disdo

//使用SVM算法進(jìn)行分類

SVMMapper函數(shù);

//對(duì)SVMMapper函數(shù)傳來(lái)的key/value形式的結(jié)果進(jìn)行處理

SVMReducer函數(shù);

End

Ifdis小于給定的閾值ξthen使用KNN分類算法進(jìn)行分類;

FunctionKNN//KNN分類算法

Begin

//對(duì)dis小于閾值ξ的進(jìn)行分塊，放入各節(jié)點(diǎn)處理

Split_KNN();

For分塊中的每個(gè)disdo

//使用KNN算法進(jìn)行分類

KNNMapper函數(shù)(計(jì)算距離時(shí)加入權(quán)重系數(shù)對(duì)樣本進(jìn)行處理);

//對(duì)KNNMapper函數(shù)傳來(lái)的key/value形式的結(jié)果進(jìn)行處理

KNNReducer函數(shù);

End

4 實(shí)驗(yàn)結(jié)果與分析

為了檢驗(yàn)算法的準(zhǔn)確性和效率，對(duì)算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)選取的數(shù)據(jù)集是來(lái)自UCI數(shù)據(jù)庫(kù)中的PokerHand數(shù)據(jù)集，整個(gè)數(shù)據(jù)集包含11個(gè)屬性，10個(gè)類別和1 025 010個(gè)實(shí)例，其中訓(xùn)練實(shí)例有25 010個(gè)，測(cè)試實(shí)例有1 000 000個(gè)。對(duì)于多分類的SVM算法，這里采取一對(duì)一分類方法[17]，訓(xùn)練10*(10-1)/2=45個(gè)SVM分類器。實(shí)驗(yàn)中設(shè)定懲罰參數(shù)C=5，給定閾值ξ=0.6，KNN算法中的K=5。為了使實(shí)驗(yàn)結(jié)果有效、全面，實(shí)驗(yàn)會(huì)在測(cè)試數(shù)據(jù)隨機(jī)抽取的1萬(wàn)、5萬(wàn)、10萬(wàn)、25萬(wàn)、50萬(wàn)、75萬(wàn)、100萬(wàn)個(gè)實(shí)例上對(duì)SVM分類算法和hSVM_KNN分類算法進(jìn)行比較，對(duì)測(cè)試數(shù)據(jù)集多次實(shí)驗(yàn)后取平均值作為結(jié)果。

圖5與圖6分別顯示了傳統(tǒng)的串行SVM算法和hSVM_KNN算法在處理時(shí)間和準(zhǔn)確性上面的對(duì)比。

如圖5所示，隨著測(cè)試實(shí)例的數(shù)量不斷增大，hSVM_KNN算法的處理時(shí)間逐漸由劣勢(shì)變成巨大的優(yōu)勢(shì)。當(dāng)測(cè)試實(shí)例比較少時(shí)，由于hSVM_KNN算法的并行化需要進(jìn)行傳輸文件、分配節(jié)點(diǎn)和節(jié)點(diǎn)之間的通信，這些操作占用了大量時(shí)間，所以hSVM_KNN算法在處理時(shí)間上要比SVM慢或者接近于相等。當(dāng)測(cè)試實(shí)例逐漸增大以后，并行化的優(yōu)勢(shì)便體現(xiàn)了出來(lái)，傳統(tǒng)的SVM算法顯然難以適應(yīng)大型數(shù)據(jù)的運(yùn)算，所以處理時(shí)間要遠(yuǎn)遠(yuǎn)慢于hSVM_KNN算法。

圖5 串行SVM與hSVM_KNN算法測(cè)試處理時(shí)間對(duì)比

圖6 串行SVM與hSVM_KNN準(zhǔn)確性對(duì)比

從圖6可以看出，hSVM_KNN算法在準(zhǔn)確性上要高于SVM算法，這是由于hSVM_KNN算法組合了SVM和KNN兩種算法，在最優(yōu)分類面附近的數(shù)據(jù)分類上比SVM算法有優(yōu)勢(shì)，因此hSVM_KNN算法在準(zhǔn)確性上也有保證。另外，因?yàn)閔SVM_KNN算法采用的是并行化處理，所以在處理大數(shù)據(jù)方面對(duì)于每個(gè)節(jié)點(diǎn)的計(jì)算機(jī)性能要求也不高，使得算法的成本較低。

5 結(jié)束語(yǔ)

文中在分析了SVM算法和KNN算法的優(yōu)缺點(diǎn)后，將SVM和KNN算法進(jìn)行結(jié)合，形成了一種效率、準(zhǔn)確度更高的SVM_KNN算法，對(duì)算法進(jìn)行改進(jìn)后將其在Hadoop平臺(tái)上進(jìn)行并行化處理，得到hSVM_KNN分類算法，從而滿足對(duì)大數(shù)據(jù)高速、高效的處理。通過(guò)實(shí)驗(yàn)可以發(fā)現(xiàn)，并行化后的SVM_KNN算法相比于傳統(tǒng)的SVM算法在大數(shù)據(jù)分類的準(zhǔn)確性、速度、成本和效率等方面有了明顯提升，對(duì)核函數(shù)的選取也不是很敏感，而且算法的穩(wěn)定性很好，具有很好的使用價(jià)值。

[1] 毛國(guó)君,段立娟,王 實(shí),等.數(shù)據(jù)挖掘原理與算法[M].第2版.北京:清華大學(xué)出版社,2007.

[2]BorathakurD.Thehadoopdistributedfilesystem:architectureanddesign[EB/OL].2012-01-20.http://hadoop.apache.org/core/docs/r0.16.4/hdfsdesign.html/.

[3]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[J].CommunicationsoftheACM,2008,51(1):107-113.

[4] 武 霞,董增壽,孟曉燕.基于大數(shù)據(jù)平臺(tái)hadoop的聚類算法K值優(yōu)化研究[J].太原科技大學(xué)學(xué)報(bào),2015,36(2):92-96.

[5] 楊宸鑄.基于HADOOP的數(shù)據(jù)挖掘研究[D].重慶:重慶大學(xué),2010.

[6] 張奕武.基于Hadoop分布式平臺(tái)的SVM算法優(yōu)化及應(yīng)用[D].廣州:中山大學(xué),2012.

[7] 王明星.數(shù)據(jù)挖掘算法優(yōu)化研究與應(yīng)用[D].合肥:安徽大學(xué),2014.

[8]AhaDW,KiblerD,AlbertMK.Instance:basedlearningalgorithms[J].MachineLearning,1991,6(1):37-66.

[9] 劉振巖.數(shù)據(jù)挖掘分類算法的研究與應(yīng)用[D].北京:首都師范大學(xué),2003.

[10] 郭明瑋,趙宇宙,項(xiàng)俊平,等.基于支持向量機(jī)的目標(biāo)檢測(cè)算法綜述[J].控制與決策,2014,29(2):193-200.

[11]PengNanbo,ZhangYanxia,ZhaoYongheng.ASVM-kNNmethodforquasar-starclassification[J].ScienceChina-Physics,Mechanics&Astronomy,2013,56(6):1227-1234.

[12] 章 兢,張小剛.數(shù)據(jù)挖掘算法及其工程應(yīng)用[M].北京:機(jī)械工業(yè)出版社,2006.

[13]CoverT,HartP.Nearestneighborpatternclassification[J].IEEETransonInformationTheory,1967,13(1):21-27.

[14] 侯玉婷,彭進(jìn)業(yè),郝露微,等.基于KNN的特征自適應(yīng)加權(quán)自然圖像分類研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(3):957-960.

[15] 李 蓉,葉世偉,史忠植.SVM-KNN分類器一一種提高SVM分類精度的新方法[J].電子學(xué)報(bào),2002,30(5):745-748.

[16] 李麗萍.并行支持向量機(jī)[J].計(jì)算機(jī)光盤(pán)軟件與應(yīng)用,2013,24:107-109.

[17]BelUK.Pairwiseclassificationandsupportvectormachines[M].Cambridge,MA:MITPress,1999:255-268.

Research on SVM_KNN Classification Algorithm Based on Hadoop Platform

LI Zheng-jie,HUANG Gang

(School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

The reform of data has brought the unprecedented development,to monitor,analyze,collect,store and apply to the rich and complex structured,semi-structured or unstructured data has become the mainstream of the development of the information age.To classify and deal with the information contained in mass data,it’s needed to have a better solution.The traditional data mining classification method cannot meet the demand any longer.To face these problems,it analyzes and improves the classification algorithm in data mining in this paper.Combined with the algorithms,an improved SVM_KNN classification algorithm is proposed.Then on this basis,by utilizing Hadoop cloud computing platform,the new classification algorithm is put into MapReduce model for parallelization application,so the improved algorithm can be applied to large data processing.Finally,data set is used to conduct experimental verification on the algorithm.By comparing with traditional SVM classification algorithm,the results show that the improved algorithm has become more efficient,fast,accurate and cost-effective,which can effectively carry out large data classification.

data mining;Hadoop;parallelization;SVM_KNN

2015-06-12

2015-09-18

時(shí)間：2016-02-18

國(guó)家自然科學(xué)基金資助項(xiàng)目(61171053)

李正杰(1991-)，男，碩士研究生，研究方向?yàn)樾畔⒕W(wǎng)絡(luò)與通信軟件、海量數(shù)據(jù)管理；黃 剛，教授，研究生導(dǎo)師，研究方向?yàn)橛?jì)算機(jī)在通信中的應(yīng)用、海量數(shù)據(jù)管理、移動(dòng)商務(wù)平臺(tái)設(shè)計(jì)開(kāi)發(fā)。

http://www.cnki.net/kcms/detail/61.1450.TP.20160218.1630.040.html

TP301.6

A

1673-629X(2016)03-0075-05

10.3969/j.issn.1673-629X.2016.03.