基于Hadoop平臺的KNN分類器的優化和實現

王江濤,陳鍛生,溫新竹

(1.仰恩大學 工程技術學院,福建 泉州 362014;2.華僑大學 計算機與技術學院,福建 廈門 361021)

?

基于Hadoop平臺的KNN分類器的優化和實現

王江濤1,陳鍛生2,溫新竹1

(1.仰恩大學 工程技術學院,福建 泉州 362014;2.華僑大學 計算機與技術學院,福建 廈門 361021)

分析了KNN分類算法的流程,然后在K值的動態獲取和分類加權兩個方面對分類算法進行改進；利用MapReduce編程思想完成KNN分類算法在Hadoop集群環境下的移植和實現。實驗數據證明，改進后的KNN分類算法在人臉識別精度、識別效率和穩定性3個方面得到了有效提高。

MapReduce;K-Neaurest Neighbor;歐式距離;Hadoop集群;加速比

KNN(K-Neaurest Neighbor)算法,分類決策簡單直觀,廣泛應用于人臉識別。大數據和云計算的不斷發展，為人臉識別技術的研究和應用提供了更新的思路，也帶來亟待解決的新課題。具體體現為：隨著人臉數據庫樣本數據海量化，對分類算法本身的性能優化和云環境下的運行進行研究更有意義。KNN分類算法本身時間復雜度較高,想立足于海量人臉數據背景之下完成高效、精準的人臉識別,至少也解決如下兩個方面的問題:

1) 人臉識別數據庫中的人臉樣本因地域、神情以及膚色等因素而導致人臉特征具備更多的屬性,會導致計算量變大,分類精度不理想。筆者從KNN分類算法的改進和優化著手,提高分類器本身的性能;

2) 人臉識別樣本數量規模的劇增而導致分類的效率急劇下降。本文解決方法是將KNN分類算法完成Hadoop集群環境下的移植,利用MapReduce[2]編程技術實現KNN算法的并行化,提高分類器的效率。

1 KNN算法[3]的分析和改進

1.1 K值的動態獲取

之前一些KNN 分類算法的研究和改進,通常從樣本訓練集和特征選擇兩個方面入手,一般不注重K值的選擇。但是K值的選擇也直接影響分類算法性能。如果K值選擇過大,數量多的樣本將主導分類結果,而數量有時候未必是分類集的主導指標,導致分類發生錯誤;反之會降低分類精度,放大噪聲干擾。

對于擁有M個樣本的樣本集,樣本類別數為N,每類樣本的數目不一,目標樣本向量與訓練樣本向量的相似度用歐式距離[4]表示:

(1)

式中：di為待分類樣本特征向量；dj為第j類樣本的特征向量；第k維特征分別用wik,wjk表示。KNN分類算法進行分類的度量如下式:

(2)

式中，j表示訓練集標號。將樣本集中各個樣本分類之間的相似度求平均值,最終達到消除各訓練集分類數目差異而造成的影響。相似度平均值表示如下:

(3)

將待分類對象與訓練樣本集中所有樣本的相似度[5]進行比較,以sim(avg)的作為閾值循環進行,直到目標樣本集每個待分類對象統計完畢,流程圖如圖1所示。

圖1 K值的動態獲取流程Fig.1 Dynamical acquisition process K-value

1.2 類別加權[6]

人臉數據庫的樣本特征屬性復雜化(膚色、種族、神情等)會導致分類算法的識別精度下降。本文提出一種解決思路:將特征屬性加權,盡可能弱化一些對人臉分類不重要的屬性,減少參與分類計算的特征向量,強化主要的特征屬性,最終提高KNN分類算法的效率和精度。

總數為M的訓練集有N類樣本,ri表示每類樣本的屬性,加權后的相似度公式:

(4)

wj表示第j類樣本的權值,其相似度公式:

(5)

1.3 KNN分類算法的MapReduce并行化

KNN分類器云平臺移植流程:首先節點從文件系統中將訓練樣本集和目標樣本集本地化；然后調用Map函數,計算目標樣本到訓練樣本的歐式距離,最后將Map函數的結果傳輸到Reduce節點生成輸出結果。

1.3.1 Map函數[7]

Map函數功能:訓練集的處理,匹配輸入數據的格式[8]。首先通過調用內置函數(Split)進行預處理,然后遍歷目標樣本集合,計算待分類對象與每個訓練樣本之間的相似度,最終將計算結果存入數據集。

1.3.2 Reduce函數[9]

Reduce函數主要的任務:目標樣本通過獲取K的值來標記樣本類別編號。后臺Reduce將獲取Map節點上的Key,進行排序、分類后輸出。

偽代碼如下：

Input: Text key, vector value

Output: Text key,vector value, Context context

Begin

For all key and value do

ArrayList(vector (t, value));

Sort (ArrayList);

New ArrayList result;

ifk

Fori=0 tokdo

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

Else

System.out.println("no sufficient trainning samples");

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

End for

End if

End

2 Hadoop集群環境下分類器的實現

KNN分類算法的分類精度[10]是評價分類器的主要指標,而分類效率也是分類算法性能的主要指標之一。隨著人臉數據庫樣本數量的急劇增加,分類算法分類效率降低,造成用戶體驗性差。本文的解決思路:如果能夠完成KNN分類算法的改進以及基于Hadoop集群環境下的移植[11],那么KNN分類器就可以利用云計算的強大計算能力,有效提高分類器的性能。圖2是基于MapReduce的KNN算法在Hadoop集群環境的流程圖。

圖2 基于MapReduce的KNN算法流程圖Fig.2 KNN algorithm flow chart based on Map Reduce

根據用戶的識別指令進行人臉圖像的讀取,然后提取待識別圖像的特征屬性值[12]和特征向量;在Split 階段將待分類樣本的特征作為數據分配給Hadoop集群中的數據節點;在Map階段結合特征屬性的加權進行相似度計算;在 Reduce 階段進行相似度的排序處理,獲取目標訓練集圖像作為輸出結果,改進后KNN分類器流程圖如圖3所示。

圖3 改進后KNN分類器流程圖Fig.3 Flow chart of the improved KNN classifier

3 實驗

3.1 實驗環境

構建Hadoop集群,使用Master/Slave[13]結構,進行分布式計算的任務。Master部署NameNode和JobTracker,NameNode負責文件數據塊處理[14]和節點存儲部署[15];JobTracker連接應用程序,Slave主要執行分布式計算，具體Hadoop集群如表1所示。

表1 Hadoop集群

3.2 實驗的人臉數據庫

Hadoop集群的構建為人臉識別系統提供了強大的運算平臺和環境,而人臉數據庫則提供了豐富的人臉數據資源。隨著人臉識別的不斷發展,對各種人臉數據庫的需求不斷擴大。本實驗所使用數據庫以及數據庫簡介見表2。

3個數據庫在人臉特征的復雜性和背景復雜性上有所差別,目的在于檢驗不同的分類器在不同數據庫中的表現差異。圖4-圖6分別是數據庫中部分的人臉數據資源。

表2 三種人臉數據庫信息

3.3 系統測試

3.3.1 改進的 KNN 分類算法與其它算法對比

文獻[4]提出的基于噪聲處理的ENN-KNN分類算法相比經典的KNN算法可以有效地提高算法的抗噪能力[16],總體上提高經典KNN分類算法的精度。而本實驗用改進后的KNN分類算法實現精度分類的提高。

圖4 人臉數據庫1Fig.4 Face database 1

圖5 人臉數據庫2Fig.5 Face database 2

圖6 人臉數據庫3Fig.6 Face database 3

三種KNN分類器均使用表2的人臉識別數據庫的人臉數據資源,實驗平臺為Hadoop集群,利用MapReduce的并行化思想實現。表3中體現的是經典KNN分類算法，ENN-KNN分類算法以及本文改進的KNN分類算法的實驗數據比較。

通過表3可以看出,不同分類算法對于不同的人臉數據庫所體現出來的分類性能是有差異的,甚至是明顯的。將表3的實驗數據用折線圖的形式展示KNN分類器在改進前后的分類精度變化，如圖7所示。

圖7 三種KNN分類器的性能折線圖Fig.7 Performance line chart of three kinds of KNN classifier

根據表3的數據和圖7可以得出：

1) 改進后KNN 分類器和ENN-KNN分類器的性能在3個人臉數據庫中的識別精度均高于經典的KNN分類器,而且本文的算法在3個數據庫里均比文獻[4]的算法分類精度略高,證明KNN分類器的改進是有效的;

2) 經典KNN 分類器應用在不同的數據庫中,體現出來的性能差異較大,說明分類算法穩定性不好。ENN-KNN分類器和本文改進后的 KNN 分類器在不同的人臉數據庫中都體現出分類精度差別較小,數據點所連接折線起伏不大的特點,具有較高的穩定性。但本文算法相比文獻[4]的ENN-KNN分類算法表現出更高的分類精度。

3.3.2 Hadoop集群下的MapReduce并行化對比

文獻[2]和文獻[3]分別把KNN分類算法進行Hadoop平臺下MapReduce并行化實現,MapReduce并行化效果明顯,實驗結果體現出文獻[2，3]的KNN分類算法的并行化效果達到預期,可以滿足分布式環境下大數據處理的要求,也表現出良好的擴展性。筆者將文獻[2，3]的并行化效果與改進后的KNN分類算法并行化效果進行比較，如圖8、圖9所示，分別從運行時間和加速比兩方面進行對比。

圖8 3種KNN分類器不同節點數的運行時間Fig.8 The number of different nodes running time in three kinds of classifiers

在海量人臉圖片樣本面前,分類器的效率是人臉識別系統的主要評價指標,主要體現為用戶從提交識別指令到獲得識別結果的相應時間。

在相同的云平臺環境下,三種KNN算法MapReduce并行化效果的直接體現為運行時間。如圖8所示，本文通過K值動態獲取和類別特征加權處理后的KNN分類算法在運行時間上相比文獻[2]和文獻[3]的KNN分類算法的MapReduce并行化效果要稍有優勢,體現本文對KNN分類算法的優化和改進是有效的。

圖9 3種KNN分類器的加速比Fig.9 Speed radio of three kinds of KNN classifiers radio

加速比是評價KNN分類算法擴展性的主要指標,描述的是單機運行時間和多個Slave同時運行的時間比值。如果加速比折線能夠隨著Slave節點的增多呈線性趨勢增長,證明分類算法的MapReduce并行化效果好,能夠在Hadoop集群環境之下提高了分類算法的效率。如圖9所示，通過與文獻[2]和文獻[3]的MapReduce并行化效果相比較:改進后的KNN分類器在運行時間上還是略占優勢,并且隨著Slave節點的增多,加速比折線呈線性規律增長,證明改進后KNN分類器具有良好的擴展性[17],能夠滿足分布式大數據的處理要求。

4 結論及展望

本文主要探討KNN分類算法以及對該分類算法做出兩個方面的改進,然后在基于MapReduce并行化編程思想在Hadoop集群下完成了實驗的實現。通過對實驗數據的統計和分析:一方面證明改進后的KNN分類算法在人臉識別方面,能夠有效提高人臉識別精度和穩定性;另一方面,基于Hadoop集群的KNN分類算法的實現,能夠極大提高分類器的效率。

目前的研究工作還有需要進一步改進的地方:

1) KNN分類算法尚有改進空間。K值的選擇會影響對分類器的維度[18],而維度變化又影響分類結果。如何進行K值的最優獲取,需要在以后的工作中進一步研究;

2) 云部署和構架還有待開展更深入的研究。基于MapReduce并行化的KNN分類算法移植到Hadoop集群中運行,如何能夠最充分地發揮云計算平臺的優勢,將直接決定分類算法移植是否成功,是否可達預期。

云計算的發展和廣泛應用,為人臉識別的研究和發展提供了發展良機,從而使得人臉識別技術和云計算技術的結合成為趨勢。

[1] 杜江,張錚,張杰鑫,等.MapReduce 并行編程模型研究綜述[J].計算機科學,2015,42(6A):537-541.

[2] 王睿.基于MapReduce的并行KNN分類算法研究[J].計算機與數字工程,2013,41(11):1738-1740.

[3] 閆永剛,馬廷淮,王建.KNN的MapReduce并行化實現[J].南京航空航天大學學報,2013,45(4):550-555.

[4] 陸廣泉,謝揚才,劉星,等.一種基于KNN的半監督分類檢測算法[J].廣西師范大學學報(自然科學版),2012,30(1):45-49.

[5] 趙玉丹,王倩,范九倫,等.基于模糊KNN的刑偵圖像場景分類[J].計算機應用研究,2013(10):3158-3164.

[6] 史佳,董昱,魏宏杰,等.基于近鄰決策域內局部分布密度的改進KNN算法[J].科學技術與工程,2014,14(30):57-60.

[7] 郝勝軒,宋宏,周曉鋒.基于近鄰噪聲處理的KNN 缺失數據填補算法[J].計算機仿真,2014,31(7):264-268.

[8] 王鵬,孟丹,詹劍鋒,等.數據密集型計算編程模型研究進展[J].計算機研究與發展,2010,47(11):1993-2002.

[9] 李玲娟,張敏.云計算環境下關聯規則挖掘算法的研究[J].計算機仿真,2014,31(7):264-268.

[10] CHUNG W C,LIN H P,CHEN S C.A framework for SQL to NoSQL translation using MapReduce[J].Automated Software Engineering,2014,21(4):489-508.

[11] QIAN J,MIAO D,ZHANG Z,et al.Parallel attribute reduction algorithms using MapReduce[J].Information Sciences,2014,279(1):671-690.

[12] ZHANG K,CHEN X W.Large-scale deep belief nets with MapReduce[J].Access IEEE,2014,2(2):395-403.

[13] HE Q,YAN J,JIN H.Quality-aware service selection for service-based systems based on iterative multi-attribute combinatorial auction[J].IEEE Transactions on Software Engineering,2014,40(2):192-215.[14] QI Y.ATHMAN BOUGUETTAYA.Efficient service skyline computation for composite service selection [J].IEEE Transactions on Knowledge and Data Engineering,2013,25(4):776-789.

[15] LI F,OOI B C,OZSU M T,et al.Distributed data management using mapreduce[J].ACM Computing Surveys(CSUR),2014,46(3):31-39.

[16] KANG G,LIU J,TANG M,et al.Web service selection algorithm based on principal component analysis [J].Journal of Electronics (China),2013,30(2):204-212.

[17] ZOU Q,LI X B,JIANG W R,et al.Survey of mapreduce frame operation in bioinformatics[J].Briefings in Bioinformatics,2014,15(4):637-647.

[18] ZHANG S C.Nearest neighbor selection for iteratively KNN imputation[J].The Journal of Systems and Software,2012,85(11):2541-2552.

[19] TENG F,YANG H,LI T,et al.Scheduling real-time workflow on mapreduce-based cloud[C]∥IEEE.Innovative Computing Technology(INTECH),Tokyo,Japan,2013:117-122.

[20] JONATHAN T,OVERPECK,GERALD A.Climate data challenges in the 21stCentury[J].Science,2011,331:700-702.

[21] FRANCA F O DE,COELHO G P.Predicting missing values with biclustering:A coherence-based approach[J].Pattern Recognition,2013,46:1255-1266.

(編輯：賈麗紅)

Optimization and Implementation of KNN Classifier Based on the Hadoop Platform

WANG Jiangtao1,CHEN Duansheng2,WEN Xinzhu1

(1.College of Engineering Technology,Yang-En University,Quanzhou 362014,China;2.CollegeofComputerScienceandTechnolgy,HuaqiaoUniversity,Xiamen361021,China)

KNN classification algorithm was analyzed with respect to its processes and then improved in dynamical acquisition and classified weighing of K value.MapReduce programming ideas were adopted to complete the transplant and implementation of KNN classification algorithm in the Hadoop cluster environment. KNN classification algorithm experimental data demonstrate the improved face recognition accuracy,efficiency and stability.

MapReduce;KNN;euclidean distance;hadoop cluster;speed-up ratio

1007-9432(2016)04-0513-05

2015-10-28

國家自然科學基金資助項目:融合視頻人臉及唇動密碼特性的身份鑒定關鍵技術研究(61300138)；福建省產業技術開發與應用計劃引導項目(2015H0042)；福建省科技計劃引導項目(2015H0025)

王江濤(1980-)，男，山東威海人，講師，碩士，主要從事圖形圖像與模式識別研究，(E-mail)14535325@qq.com

TP391

A

10.16355/j.cnki.issn1007-9432tyut.2016.04.015