基于Hadoop平臺的改進KNN分類算法并行化處理

馬 瑩， 趙 輝， 崔 巖

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

0 引 言

隨著科技的快速發展和大數據時代的到來，各領域的社交媒體都在時刻產生大量的數據，而這些數據都存在著潛在的價值[1]。當前，數據挖掘作為發現數據庫中有價值數據的關鍵技術，引起了廣大學者的高度關注[2]。數據挖掘是指從龐大的數據量中發現隱藏在其中有價值的數據信息的過程，在市場分析、信息統計、科學探索等方面都得到了廣泛應用。常用的傳統分類算法有：支持向量機(Support Vector Machine， SVM)、K-最近鄰(K-Nearest Neighbors， KNN)、樸素貝葉斯(Naive Bayes， NB)等。其中KNN分類算法有著思想簡單、理論成熟、易于實現、準確度高等優點，因此被廣泛應用于各領域的數據挖掘中。但是傳統的KNN分類算法也存在著以下缺點：

1)傳統的KNN分類算法作為文本分類中被廣泛應用的算法之一，在分類過程中，要計算每一個測試樣本與訓練樣本集中每一個點相似度或距離，因此，在此過程中會由于計算量龐大而耗費大量的時間，最后導致分類速度減慢，算法的時間復雜度增高，分類效率降低。

2)如果訓練樣本集處于不均勻狀態，那么最終會導致分類的結果不準確。然而，隨著各領域的數據量不斷增加，傳統分類算法已經不能滿足當前的數據分析需求，因此，提高算法的分類時間和分類準確性是當前數據分類至關重要的問題。

如今，已有很多研究者對KNN分類算法進行了相關的探究和分析。任朋啟等[3]通過對訓練樣本集高密度的部分進行了剪裁，并對剪裁后的訓練樣本集進行了投影尋蹤理論，提出了一種改進的KNN分類算法----IKNN分類算法，從而提高了分類的準確性。鄧振云等[4]通過引入重構和局部保持投影技術，提出了基于局部相關性的KNN分類算法，從而提升了KNN分類算法的分類效率。涂敬偉等[5]通過將KNN分類算法與MapReduce框架相結合，提出了一種在MapReduce框架上實現KNN分類并行化計算的研究，研究結果表明，此方案有著良好的加速比和可擴充性。

傳統的KNN分類算法存在著在分類過程中會耗費大量的時間去計算樣本間相似度或距離的情況，為了解決此問題，文中首先使用K-medoids聚類算法對訓練樣本集進行了剪裁，去除了樣本中相似度較低的部分；然后結合Hadoop平臺中的MapReduce框架實現數據的并行化處理，使其在多個節點上進行運算，從而降低了算法的時間復雜度，提升了算法的運行速度。

1 Hadoop平臺

Hadoop平臺最核心的設計是HDFS(Hadoop Distributed File System)[6]和MapReduce[7]。HDFS是Hadoop的一個子項目，是數據分布式操作的基礎，它是以流數據訪問模式來存儲超大文件，適合運行在通用硬件上[8],具有高可靠性、高可擴展性等特征。而MapReduce是Hadoop平臺中一個并行計算的框架模型，為大量的數據提供并行化模式。它具有數據分類、計算工作調度、系統優化等主要功能[9]。MapReduce編程模型的計算過程分為兩部分：Map函數和Reduce函數，用戶只要實現Map函數和Reduce函數，就可以完成分布式計算[10]。具體分為以下幾部分：

1)用戶提交數據信息后，MapReduce首先讀取HDFS中的數據信息，并將其分割成M個split，然后將劃分的信息傳送給JobTacker，并通過Fork創建master和worker。

2)在Map階段，Map任務數量是由片段M決定的，與split是一一對應的，并且每個Map任務之間是相互獨立的。

3)Map函數和Reduce函數都是以鍵值對的方式進行輸入和輸出，Map函數從得到的數據信息中提取出鍵值對作為輸入，然后進行操作得出以鍵值對方式的中間結果，Map函數產生的中間結果被緩存在內存中。

4)在Reduce函數階段，將獲取的中間結果按照key值進行遍歷排序，使得同一key值所對應的value值在一起。

5)將中間結果以鍵值對的方式傳遞給Reduce函數操作，并且將中間結果的value值進行歸并，最終以鍵值對的方式進行輸出。MapReduce編程模型如圖1所示。

2 KNN算法描述

KNN分類算法是在1968年由Cover和Hart提出的，是數據挖掘中最簡單的方法之一，在語言處理、圖像分析、信息檢索等方面都得到了廣泛的研究和應用[11]。它的基本原理是：

首先對待測試樣本集與訓練樣本集中的每一個點進行相似度或距離計算，然后找出與測試樣本距離最近或是相似度最高的K個訓練樣本，并以此作為待測試樣本的K個近鄰，最后根據K個近鄰所屬的類別對待測試樣本進行劃分歸類，找到最終屬于哪一類別。

圖1 MapReduce編程模型

KNN分類算法具體實現步驟：令D代表訓練樣本集，其中N代表D的樣本類別個數，表示形式為{C1，C2，…，CN}，M代表訓練樣本集數量，n代表特征向量的維度閾值，di代表D中的一個樣本的特征向量，表示形式為{xi1，xi2，…，xij，…，xin}(0

(1)

計算出待分類樣本與訓練樣本集中每一個點的相似度后，通過式(1)找到了待分類樣本的相似度最高的K個最近鄰樣本，再通過下式計算出待分類樣本歸屬于每一個類別的權重，最后將待分類樣本按照權重大小進行劃分，分配到權重最大的類別中。

(2)

其中，y(dj，Cj)為類別屬性函數，如下式：

(3)

3 KNN分類算法的改進

KNN分類算法雖然易于理解，計算簡單，但是也存在著一定的缺點，文獻[12]指出在分類過程中需要計算待測試樣本與訓練樣本集所有點的距離，這樣浪費了大量的分類時間，從而減少了KNN分類算法的分類效率。針對傳統KNN分類算法在分類過程中存在計算量較大的問題，文中將K-medoids聚類算法引入到訓練樣本集中進行聚類剪裁，從而降低相似度的冗余計算。

K-中心聚類算法，即K-medoids聚類算法，是一種被廣泛應用于數值統計、統計學、數據探索、醫學診斷等重要領域的傳統聚類方法，它具有數據簡潔、計算簡單、高健壯性等特性。

令訓練樣本集為D，其中D的樣本類別數為N{C1，C2，…，CN}，訓練集中共包含的樣本數為M，訓練樣本集剪裁方式如下：

1)K-medoids初始簇心的選擇和優化。

①對訓練樣本集D進行劃分，將其分為m個簇，其中m=3*N。

②為每一個簇隨機選擇一個點作為簇心Oi(0

③計算出訓練樣本集D中所有點到簇心Oi的相似度，并按照相似程度對其進行分配。

④在每一個簇內，首先令簇內的每一個點作為簇心，然后計算簇心到其他簇的相似距離和，最終選擇相似距離和最小的簇心作為簇內新的簇心Oi。

2)對替換簇心搜索進行優化。

①選擇一個未被選取的簇心Oi替換簇心集A，從而不再使用全局的非簇心集，而是使用距離簇心Oi最近的j(j代表迭代次數，0

②計算出在簇心集A中選取的沒有被選擇過的非簇心Qi與簇心Oi之間的平方誤差之差，并將計算結果寫在集合Q中，直至簇心集A中的所有非簇心都對比過。

③如果集合Q最小值小于0，用集合Q中最小值所對應的非簇心替換原簇心，替換后得到新的簇心集合。然后把剩下的文本分給對應的簇內，其中此簇的簇心相似度最大。最后從步驟①重新開始進行計算。

④如果集合Q的最小值大于或等于0，那么停止計算，最終取得m個聚類簇心。

3)訓練樣本集剪裁。

統計待分類樣本與m個聚類簇心的相似度，如果Sim(D,Oi)小于Ti(其中，Ti代表第i個簇的簇內閾值，即簇內樣本與簇心的最小相似度)，表示待分類樣本與簇內樣本的相似程度比較低，因此可以把該簇內包含的樣本進行剪裁，否則把該簇內包含的樣本添加到新的訓練樣本集中。

4 改進KNN算法的并行化處理

4.1 基于Hadoop平臺的改進KNN分類算法并行化處理

KNN分類算法主要是獲取k個最近鄰，要實現這一過程必須通過大量的距離計算。設計并行計算可以明顯地減少分類時間，提高分類效率。基于Hadoop改進的KNN分類算法實現MapReduce框架并行計算的基本思路是：首先將訓練樣本集分配給不同的節點進行Map函數操作計算形成鍵值對的形式，完成數據記錄到訓練樣本距離的相似度計算以及相關的排序操作，相似度計算采用的是標準的歐式距離計算度量，結果存入到Context集合中，在此過程中每一個Map函數之間操作過程是沒有關聯的;然后將Map函數操作的計算結果作為中間結果是以鍵值對的方式輸入給Reduce函數;最后Reduce函數接受傳入的各個Map節點的操作結果，其中輸入數據的方式是鍵值對的形式，根據用戶指定的最近鄰樹k進行排序，最終歸并輸出。

文中的Map函數和Reduce函數的相關偽代碼如下：

Map函數的偽代碼：

Input:Text key,Vector value

Output: Context context

Begin:

For i=0 to n (training dataset) do

t=FindCatalog(i);

For all k∈testfile do

Distance=EuclideanDistance(k,ji);

Context,write(key,vector(t,Distance));

End For

End For

End

Reduce函數的偽代碼：

Input:Text key,Vector value

Output:Text key,Vector value,Context context

Begin:

For all key and value do

Array List(vcetor(t,value));

Sort(Array List);

New ArrayList result;

If k

For i=0 to k do

result.add(key,ArrayList.get(i));

Else

System.out.println(“no sufficient training samples”);

Context.write(key.Tradition KNN(result))

End for

End for

End

4.2 時間復雜度分析

傳統的KNN分類算法的時間復雜度為O(r1r2)，r1為訓練集樣本數量，r2為測試集樣本數量。文中對訓練集數據進行了聚類剪裁，降低了相似度的冗余計算，從而生成新的訓練集，數目為r3,此時時間復雜度為O(r2r3)，在改進的KNN分類算法之上并結合MapReduce框架對KNN算法實現了并行化處理，時間復雜度為O(r2r3/n)，n為節點個數。由于r1>r3,所以基于Hadoop平臺改進的KNN分類算法的時間復雜度與傳統的KNN分類算法的時間復雜度關系為O(r2r3/n)

5 實驗結果與分析

5.1 實驗環境與數據集

實驗平臺為12臺虛擬機構成的集群，CPU型號為Intel(R) Core(TM) i7-4790 CPU @ 3.60 GHz，內存為8 G,Hadoop版本為2.6.0。

文中采用微博文本作為實驗數據進行分類，語料中分為正向情感和負向情感兩個類別，每個類別中有5 000篇文本，共計10 000篇文本。根據需求從每個文本類別中隨機抽取1 000篇文本，共計2 000篇文本作為訓練集。為了實驗的有效性和全面性，將剩余的數據分為不同規模的測試集，見表1。

表1 測試集

5.2 實驗及結果

針對算法性能方面的評價指標，比較加速比、正確率P與運行時間t，其中加速比公式為：

(4)

正確率公式為：

(5)

實驗1：在單一節點上，以正確率P與運行時間t作為評價指標，對傳統的KNN分類算法、基于K-medoids改進的KNN分類算法二者之間進行了比較。比較結果如表2和圖2所示。

表2 兩種算法的比較

圖2 兩種算法的運行時間的比較

從表1和表2可以看出，測試樣本集A1中的信息數據量比較少，文中基于K-medoids改進的KNN分類算法的正確率比傳統的KNN分類算法降低了0.6個百分點，這是由于通過K-medoids聚類算法剪裁后的算法為近似算法，當數據信息量較少時，會對分類結果的正確率產生一定的影響；但是在時間方面上，由圖2可以明顯看出，基于K-medoids改進的KNN分類算法比傳統的KNN分類算法縮短了13%～22%，而且隨著數據量的增大，計算時間也縮短的越為明顯，這是由于剪裁之后，降低了相似度的冗余計算。

實驗2：加速比主要是用來權衡一個系統的可擴充性。在基于Hadoop平臺改進的KNN分類算法下，針對節點個數不同時，對不同規模的測試樣本集之間的加速比進行了比較,結果見表3。

表3 基于Hadoop平臺的改進KNN分類算法

根據表3可以看出，基于Hadoop平臺改進的KNN分類算法的加速比隨著節點個數的增加而保持著線性上升，并在節點個數增加到30個時，加速比明顯升高。多個節點可以明顯縮減分類過程中所需要的時間，這表明在操作KNN分類算法時Hadoop平臺上具有較好的加速比。由此可見，當節點個數逐漸增加時，加速比增長的速度也會更快。

5.3 實驗結果分析

文中主要研究基于Hadoop平臺的改進KNN分類算法的并行化處理，首先通過K-medoids聚類算法對傳統的KNN分類算法進行剪裁，然后通過Hadoop平臺中的MapReduce框架實現數據并行化計算。從表1和表2中可以看出,在選擇完整的測試集時，基于K-medoids改進的KNN分類算法比傳統的KNN分類算法在運行時間上縮短了150 s；從表3可以看出,加速比隨著節點個數的增加而快速增長，特別是節點個數在30～50之間的時候，產生以上原因是因為Hadoop平臺的關鍵技術之一----MapReduce框架，在此框架上實現數據的并行化計算，提高了在分類過程中的運行時間。

6 結 語

在大數據時代通過對傳統KNN分類算法的分析和研究，文中提出了基于Hadoop平臺改進的KNN分類算法的并行化處理。首先將K-medoids聚類算法引入到傳統的KNN分類算法中，對KNN分類進行剪裁，去除了相似程度較低的文本，然后運用Hadoop平臺中的MapReduce框架對文本數據實現并行化計算，在分類過程中減少了算法的時間復雜度，提高了分類速度。實驗結果表明，選擇基于Hadoop平臺的改進KNN分類算法對文本分類在時間復雜度方面取得了良好的分類效果，提高了分類效率，并且能夠適用于當前的大數據環境。