多核CPU環境下的并行KNN算法設計

潘峰 蘇浩辀 段艷 閔云霄

關鍵詞：并行KNN算法；多線程；二維數組；最佳近鄰

0 引言

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

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

1 并行計算環境

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

1.1 并行KNN 算法的思想

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

1.2 KNN 分類問題的易并行性

一個問題的求解方案評估一般包含主要兩個指標，一個是速度，另一個是精度，本工作的KNN 算法的并行化主要是解決速度的問題。分析易知，KNN 算法是易于實現并行化的算法。我們用Xnew表示一個新數據，D（Xa，Xb）表示數據Xa，Xb的距離，不妨設為歐式距離，距離越小則相似度越高，訓練集為Y={X1，X2，...，XN}，于是KNN 算法轉化為一個最優化問題：求解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 的最近鄰。厘清上述問題，技術上實現并行KNN 算法的思路就清晰了。

1.3 并行計算環境的結構

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

從圖1 結構可以分析，多核CPU 解決了硬件并行的問題，操作系統（OS）在硬件與軟件開發環境之間搭建了橋梁，實現并行算法的關鍵只需要利用軟件開發環境提供的API 接口實現問題并行求解的設計。Java、Python 等開發環境為并行算法的設計提供了一系列軟件包，可以充分利用多線程技術實現并行算法。

2 問題建模及解決方案

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

2.1 單線程的KNN 算法

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

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

2.2 多線程KNN 算法

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

2.3 數據結構設計

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

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

2.4 多線程的創建

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

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

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

3 實驗仿真

3.1 實驗環境

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

3.2 實驗結果

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

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

3.3 分析與討論

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

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

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

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

4 結論

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