K-means++聚類算法研究與實現

摘要：聚類分析作為數據挖掘領域的一個關鍵研究熱點，主要涉及數據分組技術。K-means算法作為一種經典的聚類方法，由于其簡潔性和高效率而被廣泛應用。然而，該算法存在一些明顯的缺陷，如聚類中心的隨機選擇和較慢的收斂速度。文章在分析傳統聚類算法的基礎上，對K-means++算法進行了深入探討。K-means++算法的核心思想是在選定后續聚類中心時，綜合考慮當前已有聚類中心的分布，從而減少中心點的重疊。實驗結果表明，K-means++通過選擇更為分散的聚類中心，有效提高了聚類的準確性和算法的收斂速度，在改善聚類效率和精度方面具有顯著優勢。

關鍵詞：聚類算法；K-means；K-means++；數據挖掘

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2024）17-0078-04 開放科學（資源服務）標識碼（OSID） ：

0 引言

聚類是一種關鍵的無監督學習方法，用于將相似數據點分類并探索數據的內在結構[1]。通過揭示數據集中的密集和稀疏區域，聚類分析幫助研究人員識別全局分布模式和復雜數據屬性關聯，這不僅有助于理解數據的基本結構，還能在市場細分、社會網絡和生物信息學等領域中發揮重要作用。作為數據預處理步驟，聚類通過特征提取和分類操作，提高了數據分析的精確度和效率。在處理大規模數據集時，這種方法可簡化數據結構并明確研究方向。聚類算法在統計學、模式識別、計算幾何、生物信息學、優化及圖像處理等多個領域得到廣泛應用，并在過去十年中取得了顯著進展。

K-means聚類算法是數據挖掘領域中極受歡迎的一種算法。盡管由于其簡單和高效而廣泛應用，但該算法存在一些明顯的局限性，如聚類中心的隨機選擇和較慢的收斂速度。為應對這些問題，改進版的K-means++算法應運而生，并成為本研究的焦點。Kmeans++通過更精細的初始聚類中心選擇方法優化了標準K-means 算法，減少了算法收斂所需的迭代次數，并提高了聚類的最終質量。本文將詳細探討Kmeans++算法的原理、實現和優勢，并通過實驗驗證其在實際應用中相較于傳統K-means算法的改進效果。

1 聚類分析

聚類算法通過將數據實例分組，形成一系列被稱為“簇”的相似組合。在這些簇內，數據實例通常在特征上表現出高度的相似性，而不同簇之間的數據實例則呈現出顯著的差異。通過定義合適的距離度量或相似性系數，可以有效量化數據之間的相似性，從而實現數據的精確分類。

聚類不僅促進了數據的自動分類，還能將相似的數據集中處理，這對許多數據分析任務而言至關重要。本文主要研究利用聚類算法的這一功能，探索其在自動分類和數據分組中的應用效果，尤其聚焦于提升算法性能和數據處理效率方面的潛力。

1.1 聚類分析方法

劃分方法是聚類分析中的一項核心技術，通過創建互斥的簇確保每個數據對象唯一地屬于一個簇。這種方法主要基于距離度量，并且在開始之前需確定簇的數量k。初始劃分完成后，劃分方法采用迭代的重定位技術進行優化，即通過將數據對象從一個簇移動到另一個簇來改進分組效果。優化目標是確保簇內對象在特征上盡可能相似，而簇間對象盡可能不同，從而達到清晰的分類目的。這種方法不僅簡化了數據結構，還增強了數據處理的有效性，使其能夠在多種應用場景中提供有力支持。

劃分聚類方法在對數據進行分組的同時進行分區，以提升數據管理和分析的效率。常見的劃分聚類算法包括K-means、K-Medoids和K-Modes，各自適用于不同類型的數據和需求。

K-means：作為最廣泛使用的劃分聚類算法之一，適用于處理大規模數據集。該算法通過最小化簇內距離之和來優化簇的質心位置，適合處理連續數據。

K-Medoids：類似于K-means，但在選擇簇中心時使用數據中實際存在的點（即medoids） ，增強了對異常值的魯棒性，適合減少異常值影響的應用場景。

K-Modes：專為分類數據設計，使用模式（即數據中最頻繁出現的點）而非平均值來定義簇中心，通過最小化不匹配的類別屬性來形成簇，適合處理分類屬性的數據集。

這些算法的效果依賴于預先定義的簇數量k，正確選擇k值對于實現良好的聚類效果至關重要。通過這些方法，可以有效地將數據分為具有內部相似性和外部差異性的多個組或簇，從而使數據分析更加精確和高效。

1.2 K-Means 聚類算法

K-Means算法通過迭代計算簇中心的平均位置來重新定位這些中心，其經典算法流程包括以下步驟：

步驟1：初始化。算法從數據集中隨機抽取k個數據點作為初始的聚類中心[2]。

步驟2：分配數據點。對于數據集中的每個點，根據其與各個聚類中心之間的距離進行分類。距離的度量方式可以根據數據的性質選擇，例如歐氏距離、曼哈頓距離或余弦相似性。每個數據點被分配到最近的聚類中心所在的簇中。

步驟3：更新簇中心。完成數據點的分配后，下一步是更新每個簇的中心。使用歐氏距離時，新的簇中心是該簇內所有點的坐標平均值；若使用曼哈頓距離，則選擇各維度的中位數；對于余弦相似性度量，則更新為簇內點的方向均值。

步驟4：迭代優化。算法重復執行分配和更新步驟，直至聚類中心的位置穩定下來或達到預定的迭代次數，這標志著算法已經收斂。

這個過程的核心目標是最小化簇內距離總和，從而優化簇中心的位置。K-Means算法以其簡潔和高效性而被廣泛應用于多種數據聚類任務，盡管它對初始中心選擇敏感且可能陷入局部最優。

1.3 K-Means 聚類算法優缺點

K-means是一種廣泛使用的聚類方法，具有以下顯著優點和一些限制[3]，如表1所示。

盡管K-means算法存在這些局限性，但通過適當的預處理和算法改進（如采用K-means++等方法），可以有效緩解這些問題，從而提高其在實際應用中的有效性。

2 K-means++聚類算法

2.1 K-means++聚類思想

K-means++的核心思想在于改進了初始化過程，通過更精細的策略選擇初始聚類中心，以解決傳統K-means算法中因隨機初始化可能導致的聚類結果不穩定和質量不高的問題。

逐步選擇聚類中心：

第一步：K-means++首先采用隨機方法從數據集中選擇一個點作為第一個聚類中心[4]。

后續步驟：對于選擇后續聚類中心，算法計算每個尚未選為中心的點被選擇為新中心的概率，這個概率與點到已選中心點的距離平方成正比。

這種方法顯著減少了算法對隨機初始聚類中心的依賴，降低了陷入局部最優解的風險，并能有效提高聚類的質量。此外，它也減少了算法運行時的迭代次數，從而提高了整體的效率和性能。

2.2 K-means++算法流程

K-means++聚類的算法流程如圖1所示。

3 實驗與分析

3.1 實驗環境

本算法實現與測試的軟硬件環境如表2所示。

3.2 實驗數據

本文的實驗數據來自sklearn 機器學習庫中的make_blobs（）函數自動模擬生成，make_blobs（）函數常被用來生成聚類算法的測試數據，直觀地說，make_blobs 會根據用戶指定的特征數量、中心點數量、范圍等來生成幾類數據，這些數據可用于測試聚類算法的效果[5]。

#導入產生模型數據的方法

From sklearn.dataset import make_blobs

K=5 #確定聚類數量

X，Y= make_blobs（n_samples=5000，n_features=2，centers=k，random_state=1）

其中，n_samples是待生成的樣本的總數，n_fea?tures是每個樣本的特征數，centers表示類別數，clus?ter_state 表示每個類別的方差。當希望生成2 類數據，其中一類比另一類具有更大的方差，可以將clus?ter_std設置為[1.0，3.0]，10組樣例數據如圖2所示。

3.3 實驗測試及結果

分別使用2 000、5 000、20 000三個不同數量的測試數據和劃分為5、8、10三種簇共9個實驗組來測試K-means++聚類算法的效果，為更清晰地展現實驗測試數據，現將實驗測試數據列表如表3所示。各組對應的聚類處理前后對比如圖3所示，其中聚類用時保留小數點后3位，用時單位秒。

觀察結果表明，K-means++算法不僅提高了聚類的效率，而且通過優化初始聚類中心的選擇，提升了聚類結果的質量。

為了探究不同初始數據對K-means++算法的聚類效果，將make_blobs（）中的參數random_state作為變量，測試該算法的聚類效果。

做出實驗數據測試表如表4所示，實驗結果如圖4 所示，其中聚類用時保留小數點后3 位，用時單位秒。

從分析的6組圖表結果來看，初始數據的特性對K-means++算法的運行時間產生顯著影響。具體來說，當random_state參數較小，即各類別內的數據方差較小時，簇內數據點更加緊密，這使得K-means++算法需要更長的時間來進行聚類。相反，隨著ran?dom_state參數的增大，即每個類別的方差增加，數據點更加分散，算法的運行時間相應減少。

這一現象的原因在于K-means++算法的核心步驟之一是計算每個點到所有聚類中心的距離，以確定數據點的簇歸屬。當數據點相對集中時，這些距離較小且差異不顯著，因此算法需要進行更精細的操作來區分細微的距離差異，以實現簇的優化分割。而當數據點較為分散時，算法在初次迭代后就更容易形成明確的簇邊界，這有助于減少迭代次數，從而加快收斂速度。

4 結論

綜上所述，對初始數據進行適當的預處理是確保K-means++聚類算法成功應用及最大化效率和效果的關鍵。這一方法論在數據科學領域的各個方面均有廣泛應用，且對提升算法性能有直接且顯著的貢獻。

參考文獻：

[1] 李博.基于聚類分析的強化學習方法研究[D].成都：電子科技大學，2020.

[2] 李硯君.酒類電商精準營銷研究[D].深圳：深圳大學，2017.

[3] 李偉，黃鶴鳴，張會云，等.基于深度多特征融合的CNNs圖像分類算法[J].計算機仿真，2022，39（2）：322-326.

[4] 傅彥銘，李振鐸. 基于拉普拉斯機制的差分隱私保護kmeans++聚類算法研究[J].信息網絡安全，2019（2）：43-52.

[5] 孫立煒，王夢仙，黃澤.一種基于Logistic回歸分析的藥物篩選方法[J].科技資訊，2020，18（23）：214-216.

【通聯編輯：謝媛媛】

基金項目：第五期江蘇省職業教育教學改革研究課題：五年制高職創新創業教育課程體系構建的實踐研究（以江蘇聯合職業技術學院揚州分院為例）（項目編號：ZYB376）