潘峰 蘇浩辀 段艷 閔云霄
關(guān)鍵詞:并行KNN算法;多線程;二維數(shù)組;最佳近鄰
0 引言
以數(shù)據(jù)驅(qū)動的機器學(xué)習(xí),已成為當(dāng)前處理大數(shù)據(jù)的主要技術(shù),KNN 算法是機器學(xué)習(xí)中的主要算法之一。該算法應(yīng)用很廣,在機器學(xué)習(xí)中可用于回歸、分類等監(jiān)督學(xué)習(xí),也可與遺傳算法、粒子群優(yōu)化算法等結(jié)合用于特征優(yōu)化工作。KNN 算法簡單易懂,不足之處是隨數(shù)據(jù)規(guī)模的增加,其計算量也增大。為此,眾多學(xué)者都嘗試改進KNN 算法[1-5],提高KNN 算法的應(yīng)用廣度、速度及精度。文獻[6,7]將KNN 算法與智能算法結(jié)合,用于進行特征選擇;文獻[8-13]對KNN 算法進行并行化,以此提高KNN 算法的速度;文獻[14,15]通過數(shù)據(jù)集的約簡來改進KNN 算法速度,文獻[16,17]提出學(xué)習(xí)特征權(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)真正意義上的并行計算。當(dāng)前個人電腦的體系結(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ù),將訓(xùn)練集分割為多個訓(xùn)練子集,每個線程獨立地計算新數(shù)據(jù)在自己訓(xùn)練子集中的最近鄰,主程序歸并所有線程返回的最近鄰,最終確定所有最近鄰中的最佳近鄰的類型為新數(shù)據(jù)類型。
1.2 KNN 分類問題的易并行性
一個問題的求解方案評估一般包含主要兩個指標,一個是速度,另一個是精度,本工作的KNN 算法的并行化主要是解決速度的問題。分析易知,KNN 算法是易于實現(xiàn)并行化的算法。我們用Xnew表示一個新數(shù)據(jù),D(Xa,Xb)表示數(shù)據(jù)Xa,Xb的距離,不妨設(shè)為歐式距離,距離越小則相似度越高,訓(xùn)練集為Y={X1,X2,...,XN},于是KNN 算法轉(zhuǎn)化為一個最優(yōu)化問題:求解Xi,使得D(Xnew,Xi)最小,即min{D(Xnew,Xi)},其中Xi∈Y,Xi 的類型即是Xnew的類型。
顯然,上述需求等價于把訓(xùn)練集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ù)集分類為例進行分析,其總體解決思路是:首先將訓(xùn)練集Y 分割為多個訓(xùn)練子集Yi(i=1,2,…,n),任何兩個子集之間不存在重復(fù)元素,且所有子集的并為Y;其次使用n 個線程1:1 對應(yīng)n個訓(xùn)練子集,每個線程只使用分配給自己的訓(xùn)練子集為新數(shù)據(jù)計算最近鄰;最后,每個線程向主程序返回新數(shù)據(jù)的k 個最近鄰,k*n 個最近鄰構(gòu)成最近鄰集合P,從P 中選擇k 個最近鄰為最佳近鄰P,以最佳近鄰P中類別數(shù)最多的為新數(shù)據(jù)的類別。
2.1 單線程的KNN 算法
基本的KNN 算法描述為:新數(shù)據(jù)與訓(xùn)練集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ù)與訓(xùn)練子集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ù)組存儲訓(xùn)練集是算法設(shè)計的關(guān)鍵。二維數(shù)組可以看作是以一維數(shù)組為元素的一維數(shù)組,不妨用A 表示二維數(shù)組,則A0,A1,...,An-1是A 的元素,每一個Ai本身是一個一維數(shù)組。Aij 則表示A 的第i 個元素Ai 的第j 個元素。Ai只提供給一個線程使用,作為該線程計算新數(shù)據(jù)最近鄰的訓(xùn)練集。
采用多個線程并行計算新數(shù)據(jù)在各個訓(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 對T 取余數(shù))。
2.4 多線程的創(chuàng)建
KNN 算法需要返回最近鄰,帶返回值的線程可以通過Java 的接口Callable 定義,并使用接口Future 獲得線程的返回值。其定義的一般形式為:
接口Future 的常用方法是使用FutureTask 包裝器,它封裝了接口Runnable 和Callable,可以便捷的對Callable 對象進行封裝并轉(zhuǎn)換為Future 對象。若用于計算一個新數(shù)據(jù)在訓(xùn)練子集中的最近鄰,則TypeData是一個數(shù)據(jù)對象;若用于計算一組新數(shù)據(jù)在訓(xùn)練子集中的最近鄰,則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é)果
實驗中采用具有較大訓(xùn)練集和測試集的數(shù)據(jù)集進行測試,以此對比并行KNN 算法與串行KNN 算法的效能。數(shù)據(jù)集使用的是MNIST 手寫數(shù)據(jù)庫,它的訓(xùn)練集是60000 張28×28 像素圖片,測試集是10000 張28×28 像素圖片。本實驗使用經(jīng)過優(yōu)化處理的MNIST 數(shù)據(jù)集,圖片像素為20×20,并使用3×3 卷積核提取特征,所以訓(xùn)練集與測試集特征維數(shù)均為324。
本實驗數(shù)據(jù)集一的訓(xùn)練集為60000,測試集為10000;數(shù)據(jù)集二的訓(xùn)練集為4000,測試集為10000,其中訓(xùn)練集是通過對每一類的所有訓(xùn)練集進行聚類,每一類的聚類中心400 個,十類就是4000 個聚類中心為訓(xùn)練集。兩個數(shù)據(jù)集的特征維數(shù)都是324 維。在不同線程數(shù)下構(gòu)建的KNN 分類器對數(shù)據(jù)集進行分類的時間如表1 所示。
3.3 分析與討論
⑴ 從表1 可看出,數(shù)據(jù)集1 的訓(xùn)練集是數(shù)據(jù)集2的訓(xùn)練集的12 倍,在不同線程數(shù)情況下,對應(yīng)的耗費時間比穩(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 個訓(xùn)練集的分類準確率為97.55%,擁有4000 個訓(xùn)練集的分類準確率為97.22%,所以通過減少訓(xùn)練集數(shù)量提高速度的代價是分類效果的減弱。若要既提高速度,又提高精度,就需要進行特征優(yōu)化,如文獻[6,7]所述進行智能算法實現(xiàn)特征選擇或者文獻[16,17]的特征權(quán)重向量學(xué)習(xí),評估特征選擇結(jié)果又需要使用KNN 算法作為適度值函數(shù),此時KNN 算法的計算速度尤為關(guān)鍵。
⑷ 上述數(shù)據(jù)集2(訓(xùn)練集4000)評價一次特征權(quán)重所需時間若優(yōu)化為8 秒,則使用種群規(guī)模為100 的演化計算方法迭代1000次時間T大約是8*100*1000秒,實驗時間是約9 天,這個時間基本上可以接受;如果是對數(shù)據(jù)集1(訓(xùn)練集60000)進行特征選擇,同樣規(guī)模的種群和迭代次數(shù),則需要12*9=108 天,可能這個實驗不能接受。通過實驗可得出計算數(shù)據(jù)集特征權(quán)重的時間復(fù)雜度為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 等復(fù)雜計算架構(gòu),使得用戶只需要解決問題本身,而無需被復(fù)雜的計算環(huán)境困擾。同時,該工作為智能算法進行特征選擇提供了一個案例的實驗時間,為數(shù)據(jù)集特征優(yōu)化實驗提供了對比與數(shù)據(jù)集規(guī)模和特征數(shù)所用時間的參照。