李正杰，黃 剛

(南京郵電大學 計算機學院，江蘇 南京 210003)

基于Hadoop平臺的SVM_KNN分類算法的研究

李正杰，黃 剛

(南京郵電大學 計算機學院，江蘇 南京 210003)

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

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

0 引 言

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

1 Hadoop平臺

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

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

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

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

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

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

3 SVM_KNN分類算法

3.1 SVM算法

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

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

圖1 一般分類超平面

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

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

(1)

(2)

(3)

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

(4)

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

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

(5)

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

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

3.2 KNN算法

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

當K=4時，4個最近鄰點中有3個I類點，一個II類點，所以認為待測數(shù)據(jù)屬于I類；當K=7時，7個最近鄰點中有3個I類點，4個II類點，所以此時認為待測數(shù)據(jù)屬于II類。

3.3 SVM_KNN分類算法原理及其改進

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

圖3 KNN算法示例

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

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

圖4 SVM_KNN算法

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

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

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

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

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

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

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

從上文可知，首先需要用樣本訓練集對SVM算法進行訓練，而SVM算法主要是找出支持向量，稀疏性是支持向量的特性，即支持向量在訓練樣本集中占的比例很小。利用這個特性，可以先對數(shù)據(jù)量大的訓練數(shù)據(jù)集進行分塊處理，因為各個分塊一般來說具有獨立性，可以將其并行化處理，分塊處理進行訓練可以減少SVM算法的訓練時間。

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

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

以上就是SVM_KNN分類算法并行化處理的基本思路，可以將并行化后的SVM_KNN分類算法稱之為hSVM_KNN分類算法。根據(jù)這個思路，實現(xiàn)hSVM_KNN分類算法需要4對MapReduce函數(shù)，分別是迭代訓練產(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//訓練迭代算法

Begin

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

Split();

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

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

IterationMapper函數(shù);

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

IterationReducer函數(shù);

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

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

ReturnDsv，w，b;

Else

//如果不滿足迭代精度，則進行迭代處理

CallIteration;

Endif

End

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

Begin

//對測試數(shù)據(jù)集進行分塊，放入各節(jié)點中處理

Split_dis();

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

//求得各分塊中的dis

DisMapper函數(shù);

//對DisMapper函數(shù)傳來的key/value形式的dis進行處理

DisReducer函數(shù);

Returndis;

End

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

FunctionSVM//SVM分類算法

Begin

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

Split_SVM();

For分塊中的每個disdo

//使用SVM算法進行分類

SVMMapper函數(shù);

//對SVMMapper函數(shù)傳來的key/value形式的結果進行處理

SVMReducer函數(shù);

End

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

FunctionKNN//KNN分類算法

Begin

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

Split_KNN();

For分塊中的每個disdo

//使用KNN算法進行分類

KNNMapper函數(shù)(計算距離時加入權重系數(shù)對樣本進行處理);

//對KNNMapper函數(shù)傳來的key/value形式的結果進行處理

KNNReducer函數(shù);

End

4 實驗結果與分析

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

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

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

圖5 串行SVM與hSVM_KNN算法測試處理時間對比

圖6 串行SVM與hSVM_KNN準確性對比

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

5 結束語

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

[1] 毛國君,段立娟,王 實,等.數(shù)據(jù)挖掘原理與算法[M].第2版.北京:清華大學出版社,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ù)平臺hadoop的聚類算法K值優(yōu)化研究[J].太原科技大學學報,2015,36(2):92-96.

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

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

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

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

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

[10] 郭明瑋,趙宇宙,項俊平,等.基于支持向量機的目標檢測算法綜述[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ù)挖掘算法及其工程應用[M].北京:機械工業(yè)出版社,2006.

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

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

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

[16] 李麗萍.并行支持向量機[J].計算機光盤軟件與應用,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

時間：2016-02-18

國家自然科學基金資助項目(61171053)

李正杰(1991-)，男，碩士研究生，研究方向為信息網(wǎng)絡與通信軟件、海量數(shù)據(jù)管理；黃 剛，教授，研究生導師，研究方向為計算機在通信中的應用、海量數(shù)據(jù)管理、移動商務平臺設計開發(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.