多核CPU環(huán)境下的并行KNN算法設(shè)計

潘峰 蘇浩辀 段艷 閔云霄

關(guān)鍵詞：并行KNN算法；多線程；二維數(shù)組；最佳近鄰

0 引言

以數(shù)據(jù)驅(qū)動的機器學習，已成為當前處理大數(shù)據(jù)的主要技術(shù)，KNN 算法是機器學習中的主要算法之一。該算法應用很廣，在機器學習中可用于回歸、分類等監(jiān)督學習，也可與遺傳算法、粒子群優(yōu)化算法等結(jié)合用于特征優(yōu)化工作。KNN 算法簡單易懂，不足之處是隨數(shù)據(jù)規(guī)模的增加，其計算量也增大。為此，眾多學者都嘗試改進KNN 算法[1-5]，提高KNN 算法的應用廣度、速度及精度。文獻[6，7]將KNN 算法與智能算法結(jié)合，用于進行特征選擇；文獻[8-13]對KNN 算法進行并行化，以此提高KNN 算法的速度；文獻[14，15]通過數(shù)據(jù)集的約簡來改進KNN 算法速度，文獻[16，17]提出學習特征權(quán)重向量，增加KNN 算法的精度。

本文研究一種快速的并行KNN 算法，以該算法為評估特征權(quán)值向量的適度值函數(shù)，并通過演化計算，搜索最優(yōu)的特征權(quán)值向量。由于適度值函數(shù)處理較為龐大的數(shù)據(jù)集時其計算速度成為群體演化計算的瓶頸，因此研究高速并行KNN 算法很有價值。

1 并行計算環(huán)境

在單核單線程的計算環(huán)境中只能實現(xiàn)并發(fā)，不能實現(xiàn)真正意義上的并行計算。當前個人電腦的體系結(jié)構(gòu)已經(jīng)發(fā)生重大變化，硬件主要是多核CPU 架構(gòu)及核數(shù)更多的多核GPU，Java、Python 等軟件開發(fā)環(huán)境很容易構(gòu)造并行程序[18，19]，這為并行計算提供了可行性條件，本工作主要依托于多核CPU 環(huán)境使用Java 實現(xiàn)并行計算。

1.1 并行KNN 算法的思想

本文立足于現(xiàn)在的多核CPU 計算環(huán)境，利用Java軟件開發(fā)環(huán)境設(shè)計多線程分解計算任務(wù)，將訓練集分割為多個訓練子集，每個線程獨立地計算新數(shù)據(jù)在自己訓練子集中的最近鄰，主程序歸并所有線程返回的最近鄰，最終確定所有最近鄰中的最佳近鄰的類型為新數(shù)據(jù)類型。

1.2 KNN 分類問題的易并行性

一個問題的求解方案評估一般包含主要兩個指標，一個是速度，另一個是精度，本工作的KNN 算法的并行化主要是解決速度的問題。分析易知，KNN 算法是易于實現(xiàn)并行化的算法。我們用Xnew表示一個新數(shù)據(jù)，D（Xa，Xb）表示數(shù)據(jù)Xa，Xb的距離，不妨設(shè)為歐式距離，距離越小則相似度越高，訓練集為Y={X1，X2，...，XN}，于是KNN 算法轉(zhuǎn)化為一個最優(yōu)化問題：求解Xi，使得D（Xnew，Xi）最小，即min{D（Xnew，Xi）}，其中Xi∈Y，Xi 的類型即是Xnew的類型。

顯然，上述需求等價于把訓練集Y 分割為若干個不相交的子集Yi，即Y = ∪i = 1m Yi，Yi ∩ Yj = ?，i ≠ j。每個線程獨立地完成在Y 的所有不相交子集中查找Xnew 的最近鄰就等價于一個線程在Y 中查找Xnew 的最近鄰。厘清上述問題，技術(shù)上實現(xiàn)并行KNN 算法的思路就清晰了。

1.3 并行計算環(huán)境的結(jié)構(gòu)

多核CPU 的硬件環(huán)境為并行算法提供了基本條件，如何依托于硬件開發(fā)并行程序，是一件具有挑戰(zhàn)意義的工作。在硬件和問題之間存在一定的鴻溝，厘清這種關(guān)系是解決問題的關(guān)鍵，我們可以通過圖1 來理解這種關(guān)系。

從圖1 結(jié)構(gòu)可以分析，多核CPU 解決了硬件并行的問題，操作系統(tǒng)（OS）在硬件與軟件開發(fā)環(huán)境之間搭建了橋梁，實現(xiàn)并行算法的關(guān)鍵只需要利用軟件開發(fā)環(huán)境提供的API 接口實現(xiàn)問題并行求解的設(shè)計。Java、Python 等開發(fā)環(huán)境為并行算法的設(shè)計提供了一系列軟件包，可以充分利用多線程技術(shù)實現(xiàn)并行算法。

2 問題建模及解決方案

本工作以KNN 算法對數(shù)據(jù)集分類為例進行分析，其總體解決思路是：首先將訓練集Y 分割為多個訓練子集Yi（i=1，2，…，n），任何兩個子集之間不存在重復元素，且所有子集的并為Y；其次使用n 個線程1：1 對應n個訓練子集，每個線程只使用分配給自己的訓練子集為新數(shù)據(jù)計算最近鄰；最后，每個線程向主程序返回新數(shù)據(jù)的k 個最近鄰，k*n 個最近鄰構(gòu)成最近鄰集合P，從P 中選擇k 個最近鄰為最佳近鄰P，以最佳近鄰P中類別數(shù)最多的為新數(shù)據(jù)的類別。

2.1 單線程的KNN 算法

基本的KNN 算法描述為：新數(shù)據(jù)與訓練集Y 中的每一個數(shù)據(jù)進行距離計算，返回與新數(shù)據(jù)距離最小的數(shù)據(jù)，該數(shù)據(jù)稱為新數(shù)據(jù)的最近鄰，最近鄰的類別即新數(shù)據(jù)的類別。

這里我們選擇最近鄰數(shù)k 取值為1，若k 值大于1，則上述返回為最近鄰集合，以下同樣處理。k 取不同的值可以改善分類的準確率，本文不考慮準確率問題，取k 為1 簡化程序設(shè)計，不影響并行架構(gòu)，故不進行討論k 的其他取值。

2.2 多線程KNN 算法

多線程的KNN 算法描述：每一個線程進行新數(shù)據(jù)與訓練子集Yi中的每一個數(shù)據(jù)進行距離計算，返回與新數(shù)據(jù)距離最小的數(shù)據(jù)給主程序，主程序收集的各個線程返回的最近鄰構(gòu)成最近鄰集合，以最近鄰集合的最佳近鄰類別作為新數(shù)據(jù)的類別。

2.3 數(shù)據(jù)結(jié)構(gòu)設(shè)計

數(shù)據(jù)結(jié)構(gòu)是算法設(shè)計的基礎(chǔ)，使用二維數(shù)組存儲訓練集是算法設(shè)計的關(guān)鍵。二維數(shù)組可以看作是以一維數(shù)組為元素的一維數(shù)組，不妨用A 表示二維數(shù)組，則A0，A1，...，An-1是A 的元素，每一個Ai本身是一個一維數(shù)組。Aij 則表示A 的第i 個元素Ai 的第j 個元素。Ai只提供給一個線程使用，作為該線程計算新數(shù)據(jù)最近鄰的訓練集。

采用多個線程并行計算新數(shù)據(jù)在各個訓練子集的最近鄰中，所有訓練集都讀入二維數(shù)組中，由線程數(shù)決定二維數(shù)組的行數(shù)。若訓練集數(shù)M 是線程數(shù)T的整數(shù)倍，則二維數(shù)組行數(shù)是T，列數(shù)是M/T（M 整除以T 的商）；若訓練集M 數(shù)不是線程數(shù)T 的整數(shù)倍，則二維數(shù)組行數(shù)是T，前T-1 行列數(shù)是M/T，最后一行的列數(shù)是M/T+M%T（M 對T 取余數(shù)）。

2.4 多線程的創(chuàng)建

KNN 算法需要返回最近鄰，帶返回值的線程可以通過Java 的接口Callable 定義，并使用接口Future 獲得線程的返回值。其定義的一般形式為：

接口Future 的常用方法是使用FutureTask 包裝器，它封裝了接口Runnable 和Callable，可以便捷的對Callable 對象進行封裝并轉(zhuǎn)換為Future 對象。若用于計算一個新數(shù)據(jù)在訓練子集中的最近鄰，則TypeData是一個數(shù)據(jù)對象；若用于計算一組新數(shù)據(jù)在訓練子集中的最近鄰，則TypeData 設(shè)計為封裝了一組數(shù)據(jù)對象的類。

創(chuàng)建多少線程依據(jù)是計算機CPU 核數(shù)，一般不超過CPU 的最大核數(shù)。程序設(shè)計中使用Runtime.getRuntime（）.availableProcessprs（）方法獲取CPU 最大核數(shù)。

3 實驗仿真

3.1 實驗環(huán)境

實驗在一臺聯(lián)想移動工作站上實現(xiàn)，CPU：為Intel（R） Core（TM） I7-8750H，2.2GHz，6 核12 線程，內(nèi)存為32GB；操作系統(tǒng)及軟件開發(fā)環(huán)境為：Windows11+JDK1.8+IntelliJ IDEA，沒有使用其他額外的開發(fā)包。

3.2 實驗結(jié)果

實驗中采用具有較大訓練集和測試集的數(shù)據(jù)集進行測試，以此對比并行KNN 算法與串行KNN 算法的效能。數(shù)據(jù)集使用的是MNIST 手寫數(shù)據(jù)庫，它的訓練集是60000 張28×28 像素圖片，測試集是10000 張28×28 像素圖片。本實驗使用經(jīng)過優(yōu)化處理的MNIST 數(shù)據(jù)集，圖片像素為20×20，并使用3×3 卷積核提取特征，所以訓練集與測試集特征維數(shù)均為324。

本實驗數(shù)據(jù)集一的訓練集為60000，測試集為10000；數(shù)據(jù)集二的訓練集為4000，測試集為10000，其中訓練集是通過對每一類的所有訓練集進行聚類，每一類的聚類中心400 個，十類就是4000 個聚類中心為訓練集。兩個數(shù)據(jù)集的特征維數(shù)都是324 維。在不同線程數(shù)下構(gòu)建的KNN 分類器對數(shù)據(jù)集進行分類的時間如表1 所示。

3.3 分析與討論

⑴ 從表1 可看出，數(shù)據(jù)集1 的訓練集是數(shù)據(jù)集2的訓練集的12 倍，在不同線程數(shù)情況下，對應的耗費時間比穩(wěn)定在12 倍。

⑵ 對于數(shù)據(jù)集1 和數(shù)據(jù)集2 而言，通過圖2 可以直觀看出，在線程倍增初期具有較好的加速比，中期后加速并不明顯。通過在命令行使用wmic 激活環(huán)境，使用cpu get *命令查看，CPU 核數(shù)為6，過多的線程只能是并發(fā)執(zhí)行，線程切換會增加消耗，加速效果降低，但很明顯的是采用不超過核數(shù)的多線程構(gòu)建并行KNN 算法能夠顯著提高計算速度。

⑶ 實驗中取k 值為1，擁有60000 個訓練集的分類準確率為97.55%，擁有4000 個訓練集的分類準確率為97.22%，所以通過減少訓練集數(shù)量提高速度的代價是分類效果的減弱。若要既提高速度，又提高精度，就需要進行特征優(yōu)化，如文獻[6，7]所述進行智能算法實現(xiàn)特征選擇或者文獻[16，17]的特征權(quán)重向量學習，評估特征選擇結(jié)果又需要使用KNN 算法作為適度值函數(shù)，此時KNN 算法的計算速度尤為關(guān)鍵。

⑷ 上述數(shù)據(jù)集2（訓練集4000）評價一次特征權(quán)重所需時間若優(yōu)化為8 秒，則使用種群規(guī)模為100 的演化計算方法迭代1000次時間T大約是8*100*1000秒，實驗時間是約9 天，這個時間基本上可以接受；如果是對數(shù)據(jù)集1（訓練集60000）進行特征選擇，同樣規(guī)模的種群和迭代次數(shù)，則需要12*9=108 天，可能這個實驗不能接受。通過實驗可得出計算數(shù)據(jù)集特征權(quán)重的時間復雜度為O（t*m*n），在m 和n 確定的情況下，只有盡量使用較小的t 才能使智能算法優(yōu)化特征權(quán)重有實際意義。

4 結(jié)論

本工作為了提高KNN 算法的計算速度，系統(tǒng)分析了構(gòu)建并行KNN 算法所需要的條件，并采用Java 編程實現(xiàn)了并行KNN 算法，通過對手寫數(shù)字數(shù)據(jù)集的測試，KNN 算法構(gòu)建的KNN 分類器速度顯著提高，為處理大數(shù)據(jù)提供一種高效的可實踐實驗方法。該方法簡單透明，不需搭建如Hadoop 等復雜計算架構(gòu)，使得用戶只需要解決問題本身，而無需被復雜的計算環(huán)境困擾。同時，該工作為智能算法進行特征選擇提供了一個案例的實驗時間，為數(shù)據(jù)集特征優(yōu)化實驗提供了對比與數(shù)據(jù)集規(guī)模和特征數(shù)所用時間的參照。