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

潘峰 蘇浩辀 段艷 閔云霄

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

0 引言

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

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

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

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

1.1 并行KNN 算法的思想

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

1.2 KNN 分類問題的易并行性

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

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

1.3 并行計(jì)算環(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)境之間搭建了橋梁，實(shí)現(xiàn)并行算法的關(guān)鍵只需要利用軟件開發(fā)環(huán)境提供的API 接口實(shí)現(xiàn)問題并行求解的設(shè)計(jì)。Java、Python 等開發(fā)環(huán)境為并行算法的設(shè)計(jì)提供了一系列軟件包，可以充分利用多線程技術(shù)實(shí)現(xiàn)并行算法。

2 問題建模及解決方案

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

2.1 單線程的KNN 算法

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

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

2.2 多線程KNN 算法

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)仿真

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)在一臺(tái)聯(lián)想移動(dòng)工作站上實(shí)現(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 實(shí)驗(yàn)結(jié)果

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

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

3.3 分析與討論

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

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

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

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

4 結(jié)論

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