基于異構大數據平臺的并行化K-means算法設計與實現

摘要：K-means算法是數據挖掘和機器學習中用于聚類分析的基礎工具，廣泛應用于文檔聚類、異常值檢測等多個領域。然而，隨著大數據時代的來臨，傳統方法難以滿足大規模數據聚類分析的處理需求。為此，文章基于Spark 和 GPU 構建異構大數據平臺，對K-means算法進行并行化設計與實現，以提高K-means算法的數據處理效率和資源利用率。文章在4個公開的真實數據集上驗證了該方法的有效性，與傳統的并行化K-means方法進行對比，實驗結果證明該方法相較傳統方法具備更好的性能。

關鍵詞：并行計算；異構計算；大數據技術；數據挖掘；K-means算法；聚類分析

中圖分類號：TP311.13 "文獻標志碼：A

0 引言

K-means算法［1］是聚類分析的基礎工具，廣泛應用于推薦系統、異常檢測和文檔聚類等領域。然而，面對大數據時代產生的海量數據，傳統聚類方法難堪重任。盡管已有基于分布式計算或GPU的加速方案被提出，但它們在異構大數據平臺上的支持和性能仍有限，不能針對任務特點充分利用CPU和GPU的設備優勢且并行計算的過程中容易產生大量的網絡傳輸。

例如，在借助分布式技術引擎加速K-means算法方面，張波等［2］借助并行計算引擎Spark實現了并行化K-means算法。李召鑫等［3］借助并行計算引擎Flink對K-means算法進行了并行化，這類方法能夠通過增加CPU設備的數量來提升數據處理任務的并行度，以此來提升程序性能，但該類方法僅支持CPU設備，不支持GPU設備，不能利用異構設備的特點進一步加速處理性能。此外，該類方法并行計算時存在大量跨節點通信，會降低處理性能。在借助GPU設備加速K-means算法方面，方玉玲等［4］和劉端陽等［5］通過計算統一設備架構（Computer Unified Device Architecture， CUDA）編程使用GPU設備實現并行化的K-means算法，該類方法與僅使用CPU設備的方法相比取得了較大的性能提升且不會產生多個計算節點間的大規模網絡傳輸。但該類方案的橫向擴展能力受限且未整合CPU設備，因此，該類方案仍不能利用異構設備的特點進行任務劃分和程序優化。

為解決這些問題，本文提出一種基于異構大數據平臺的并行化K-means算法，設計了一種任務劃分方法，結合K-means、Spark和CUDA的特點，按計算任務的類型將任務分配到合適的硬件設備上計算。此外，該方法通過數據扁平化和統一索引，降低了Spark與GPU間的通信成本。本文還引入了K-means++［6］以及Yinyang K-means算法［7］，優化處理流程，減少無效計算。最后，在一個配備了2個GPU和32 個CPU的異構大數據平臺上，使用4個公開的真實數據集進行實驗，驗證了方案的有效性。

1 技術路線

本節包括2部分：K-means并行化流程設計和CUDA并行算法設計。K-means并行化流程設計部分將深入探討K-means算法、CUDA編程和Spark編程的特點，討論算法流程中每個步驟使用的設備和并行計算的方法以及設備間通信的方式等。

1.1 K-means并行化流程設計

與僅使用CPU設備或GPU設備的并行計算平臺相比，異構計算平臺的優勢在于可充分利用不同類型的處理器設備，結合任務特點劃分計算任務。例如，將控制流和序列任務劃分給CPU，將計算密集型的任務劃分給GPU。

K-means 算法的作用是將數據集中的所有樣本點劃分為k個類簇，算法流程包括4個步驟：Step1，初始化k個中心點；Step2，計算每個數據點與k個中心點的距離，納入最近中心點的類簇；Step3，根據每個簇的數據點重新計算生成每個簇的中心點；Step4，重復步驟Step2和Step3，直到收斂或達到最大迭代次數。上述過程中，計算最為密集的步驟為Step2和Step3，這是因為在收斂或達到最大迭代次數之前，這2個步驟會被反復執行，迭代次數多。每次迭代應遍歷所有樣本點，每個樣本點須與k個簇的中心點計算距離，單個輪次的計算量也略大。

基于上述分析，本文設計并實現了如圖 1所示的基于異構計算平臺的K-means算法流程。處理流程包括數據加載、數據預處理、數據挖掘（即執行K-means算法）和知識獲取。其中，數據預處理和數據挖掘階段的任務是GPU更擅長的計算密集型任務（包含Step2和Step3），因此，針對這2個階段，使用CUDA編寫并行計算程序來調用GPU進行處理，其余部分使用Spark并行計算引擎調度多個CPU進行處理。

由于Spark的編程環境是Java，CUDA編程的環境是C語言，且兩者調度的設備也不一致，因此，使用JNI技術進行數據傳輸。具體過程如下：首先，Spark端在數據預處理和數據挖掘階段將CPU設備中的數據進行序列化，傳輸到CUDA端。之后，CUDA端用GPU設備加速K-means算法流程中的Step2和Step3。最后，CUDA端將計算得的結果進行序列化，再通過JNI技術傳輸回Spark端。

因為通過JNI技術傳輸基本數據類型的效率要優于封裝數據類型的傳輸效率，所以在序列化數據之前，將多維向量構成的矩陣展開為一維數組，將封裝數據類型在本地轉化為基本數據類型再進行序列化和傳輸，數據扁平化如圖 2所示。該方法可以有效地減少Spark端CPU設備與CUDA端GPU設備間的通信開銷。

此外，本文在Spark端和CUDA端都采用了統一索引排列數據，在返回的結果中只須回傳每個數據點對應的簇中心下標，將傳輸數據的空間復雜度從O（d×n）下降至O（n） 。

1.2 CUDA并行算法設計

為了提升CUDA并行計算程序的性能，本文首先用K-means++算法初始化k個類簇的中心點，基于更合理的初始化方式減少算法迭代次數。其次，使用CUDA對Yinyang K-means中可并行化執行的步驟進行編程實現，以此提升K-means算法在GPU中的執行效率。

為了方便描述經本文優化的K-means算法，此處對一些必要的符號和公式進行解釋。設X為包含n個樣本點的數據集，x為數據集X中的一個樣本點，x的特征維度為d維。令k為聚類標簽類別的數量（即簇數），將k個簇的中心點所構成的集合稱為C，c為集合C中的一個簇類中心點，此時x與c之間的距離定義為d（x，c）。每輪迭代中，x會與C中的所有中心點計算距離，取距離最短的中心點b（x）作為標簽。令下一輪次的C、c、b（x）為C′、c′、b′（x），則迭代過程中，中心點c相較下一輪次中心點c′的偏移量為d（c，c′），定義為δ（c）。之后定義ub（x）為邊界上限，lb（x）為邊界下限，用于過濾無效計算，其定義如式（1）所示：

ub（x）gt;d（x，b（x））

lb（x）lt;d（x，c），c∈C-b（x）（1）

本文參考Yinyang K-means實現了優化的過濾方法以及簇中心更新方式。在過濾時，組過濾是全局過濾的擴展，組過濾首先將k個簇中心點分成t個組，即G={G1，G2，...，Gt}，在初次分組后，在組內實施全局過濾，具體如式（2）所示：

lb（x，Gi）lt;d（x，c），c∈Gi-b（x）

lb（x，Gi）-maxc∈Giδ（c）≥ub（x）+δ（b）（2）

中心點更新方式如式（3）所示，V和V′表示2次迭代的中心點集合，OV=V∩V′。

c′=c×|V|-（∑y∈V-OVy）+∑y′∈V′-OVy|V′|（3）

將下邊界集合L和上邊界集合U定義為輔助數據結構，具體如式（4）所示：

L=｛lb（x1，G1），lb（x2，G2），…，lb（xn，Gn）｝

U=｛ub（x1），ub（x2），…，ub（xn）｝（4）

結合上述公式符號的定義，基于CUDA實現的K-means算法流程如下。

Step1：傳入參數n、d、k、X，基于K-means++生成k個中心點，初始化中心點集合C和組集合G。

Step2：使用CUDA并行地將X中的所有樣本點劃分到最近的簇中，初始化簇標簽集合P、上下邊界集合L和U。

Step3：使用CUDA并行地遍歷X中的每個樣本點，根據上下邊界集合L和U以及過濾規則，重新匹配C中與x最匹配的簇，得到新的聚類標簽集合P。

Step4：根據新的聚類標簽集合P，使用CUDA并行地遍歷每個簇的樣本點，更新每個簇的中心點，得到新的中心集合C。

Step5：使用CUDA并行地檢查是否達到收斂條件，若是則取P為最終計算結果。若否，則判斷是否達到最大迭代次數，若未達到則跳轉到Step3進行新一輪的迭代；若達到最大迭代次數則取P為最終計算結果。

2 實驗

2.1 數據集

本文用UCI Machine Learning Repository公開的4個真實數據集MSD、Census、SuSy和Higgs進行實驗驗證，證明本文方法在不同規模和復雜度的數據集上的有效性。具體而言，MSD、Census、SuSy和Higgs的樣本點數量依次為5.2萬個、25萬個、50萬個和110萬個，對應的特征維度依次為90、68、18和28。

2.2 實驗結果與分析

為驗證本文方法相較傳統方法Spark MLib庫并行化K-means的有效性，本文采用32個CPU核心，20 GB的內存在前文提及的4個真實數據集上進行測試，調整k值進行多組實驗。比較2種方法的執行時間，計算加速比作為性能評估指標。此處的加速比（S）定義為傳統方法執行時間（T1）與本文方法執行時間（T2）的比值，即S=T1/T2。實驗結果如表 1所示。

從表 1中可發現，本文方法除了在Census數據集上，當k=4時，表現弱于傳統方法，其他場景下都優于傳統方法，且k值越大，本文方法相較傳統方法的優勢越顯著，特別是當k=10000時，本文方法在Higgs數據集上達到了最顯著的提升，是傳統方法加速比的247倍。

產生上述現象的原因是當數據集的計算量和k值較小時，本文方法的數據通信開銷大于并行計算帶來的加速，反而降低了性能。而在較大數據集和大k值的場景下，本文方法相較傳統方法能夠更有效地穩定提升聚類分析的性能。

為了探究數據集大小對本文方法聚類性能的影響，本文從Higgs數據集中隨機抽取了不同大小的子集，從0.25 M到8.00 M，共6個，使用與前文一致的硬件配置進行實驗，聚類簇數量k設置為1024，數據集大小對算法耗時與加速比的影響如圖 3所示。

由圖3可知，盡管2種方法的執行時間隨著數據負載的增加而增加，但任意負載下，本文方法相較傳統方法都表現出了更好的性能和穩定性，加速比在 "3.48～7.41，這證明了本文方法相較傳統方法的有效性和優越性。

3 結語

本研究針對大數據時代下K-means算法的性能瓶頸，提出了一種基于異構大數據平臺的并行化方法。該方法能夠對K-means算法、Spark編程和CUDA編程的特點進行任務劃分，將數據扁平化和統一索引應用于數據傳輸中，優化了K-means算法的計算流程。實驗結果表明，該方案相較傳統方法有效地提升了計算性能并減少了通信開銷。未來筆者會嘗試在更多異構計算節點上的并行化，進一步提升方法的可擴展性。

參考文獻

［1］WONG J A .Algorithm AS 136： a K-means clustering algorithm［J］.Journal of the Royal Statistical Society， 1979（1）：100-108.

［2］張波.基于Spark的K-means算法的并行化實現與優化［D］.武漢：華中科技大學，2015.

［3］李召鑫，孟祥印，肖世德，等.基于Flink框架的K-means算法優化及并行計算策略［J］.計算機與數字工程，2023（10）：2231-2235.

［4］方玉玲，那麗春.一種基于CUDA的K-means多級并行優化方法［J］.小型微型計算機系統，2021（7）：1547-1553.

［5］劉端陽，鄭江帆，沈國江，等.基于CUDA的K-means算法并行化研究［J］.計算機科學，2018（11）：292-297.

［6］ARTHUR D， VASSILVITSKII S .K-means++： the advantages of careful seeding［C］//Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms， SODA 2007， New Orleans， Louisiana， USA， January 7-9， 2007.

［7］TAYLOR C， GOWANLOCK M . Accelerating the Yinyang K-means algorithm using the GPU［C］//2021 IEEE 37th International Conference on Data Engineering （ICDE），April 19-22，2021，Chania，Greece，New York： IEEE， 2021.

（編輯 王雪芬編輯）

Design and implementation of parallelized K-means based on heterogeneous

big data platform

ZHANG" Shixian， HUANG" Wanbing， XIONG" Wen*

（School of Information，Yunnan Normal University， Kunming 650000， China）

Abstract： "The K-means algorithm is a fundamental tool in data mining and machine learning for cluster analysis and is widely used in various fields such as document clustering and anomaly detection. However， with the advent of the big data era， traditional methods struggle to meet the processing demands of large-scale data clustering analysis. To address the problems， the article presents a parallelized design and implementation of the K-means algorithm based on a heterogeneous big data platform constructed with Spark and GPU， aiming to enhance the data processing efficiency and resource utilization of the K-means algorithm. The methods are validated in this article on four publicly available real-world datasets and compared them with traditional parallelized K-means methods. The experimental results demonstrate that our approach outperforms traditional methods in terms of performance.

Key words： parallel computing; heterogeneous computing; big data technology; data mining; K-means algorithm; cluster analysis