K-means++聚類算法研究與實(shí)現(xiàn)

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

關(guān)鍵詞：聚類算法；K-means；K-means++；數(shù)據(jù)挖掘

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2024）17-0078-04 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID） ：

0 引言

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

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

1 聚類分析

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

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

1.1 聚類分析方法

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

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

K-means：作為最廣泛使用的劃分聚類算法之一，適用于處理大規(guī)模數(shù)據(jù)集。該算法通過最小化簇內(nèi)距離之和來優(yōu)化簇的質(zhì)心位置，適合處理連續(xù)數(shù)據(jù)。

K-Medoids：類似于K-means，但在選擇簇中心時(shí)使用數(shù)據(jù)中實(shí)際存在的點(diǎn)（即medoids） ，增強(qiáng)了對異常值的魯棒性，適合減少異常值影響的應(yīng)用場景。

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

這些算法的效果依賴于預(yù)先定義的簇?cái)?shù)量k，正確選擇k值對于實(shí)現(xiàn)良好的聚類效果至關(guān)重要。通過這些方法，可以有效地將數(shù)據(jù)分為具有內(nèi)部相似性和外部差異性的多個(gè)組或簇，從而使數(shù)據(jù)分析更加精確和高效。

1.2 K-Means 聚類算法

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

步驟1：初始化。算法從數(shù)據(jù)集中隨機(jī)抽取k個(gè)數(shù)據(jù)點(diǎn)作為初始的聚類中心[2]。

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

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

步驟4：迭代優(yōu)化。算法重復(fù)執(zhí)行分配和更新步驟，直至聚類中心的位置穩(wěn)定下來或達(dá)到預(yù)定的迭代次數(shù)，這標(biāo)志著算法已經(jīng)收斂。

這個(gè)過程的核心目標(biāo)是最小化簇內(nèi)距離總和，從而優(yōu)化簇中心的位置。K-Means算法以其簡潔和高效性而被廣泛應(yīng)用于多種數(shù)據(jù)聚類任務(wù)，盡管它對初始中心選擇敏感且可能陷入局部最優(yōu)。

1.3 K-Means 聚類算法優(yōu)缺點(diǎn)

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

盡管K-means算法存在這些局限性，但通過適當(dāng)?shù)念A(yù)處理和算法改進(jìn)（如采用K-means++等方法），可以有效緩解這些問題，從而提高其在實(shí)際應(yīng)用中的有效性。

2 K-means++聚類算法

2.1 K-means++聚類思想

K-means++的核心思想在于改進(jìn)了初始化過程，通過更精細(xì)的策略選擇初始聚類中心，以解決傳統(tǒng)K-means算法中因隨機(jī)初始化可能導(dǎo)致的聚類結(jié)果不穩(wěn)定和質(zhì)量不高的問題。

逐步選擇聚類中心：

第一步：K-means++首先采用隨機(jī)方法從數(shù)據(jù)集中選擇一個(gè)點(diǎn)作為第一個(gè)聚類中心[4]。

后續(xù)步驟：對于選擇后續(xù)聚類中心，算法計(jì)算每個(gè)尚未選為中心的點(diǎn)被選擇為新中心的概率，這個(gè)概率與點(diǎn)到已選中心點(diǎn)的距離平方成正比。

這種方法顯著減少了算法對隨機(jī)初始聚類中心的依賴，降低了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，并能有效提高聚類的質(zhì)量。此外，它也減少了算法運(yùn)行時(shí)的迭代次數(shù)，從而提高了整體的效率和性能。

2.2 K-means++算法流程

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

3 實(shí)驗(yàn)與分析

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

本算法實(shí)現(xiàn)與測試的軟硬件環(huán)境如表2所示。

3.2 實(shí)驗(yàn)數(shù)據(jù)

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

#導(dǎo)入產(chǎn)生模型數(shù)據(jù)的方法

From sklearn.dataset import make_blobs

K=5 #確定聚類數(shù)量

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

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

3.3 實(shí)驗(yàn)測試及結(jié)果

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

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

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

做出實(shí)驗(yàn)數(shù)據(jù)測試表如表4所示，實(shí)驗(yàn)結(jié)果如圖4 所示，其中聚類用時(shí)保留小數(shù)點(diǎn)后3 位，用時(shí)單位秒。

從分析的6組圖表結(jié)果來看，初始數(shù)據(jù)的特性對K-means++算法的運(yùn)行時(shí)間產(chǎn)生顯著影響。具體來說，當(dāng)random_state參數(shù)較小，即各類別內(nèi)的數(shù)據(jù)方差較小時(shí)，簇內(nèi)數(shù)據(jù)點(diǎn)更加緊密，這使得K-means++算法需要更長的時(shí)間來進(jìn)行聚類。相反，隨著ran?dom_state參數(shù)的增大，即每個(gè)類別的方差增加，數(shù)據(jù)點(diǎn)更加分散，算法的運(yùn)行時(shí)間相應(yīng)減少。

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

4 結(jié)論

綜上所述，對初始數(shù)據(jù)進(jìn)行適當(dāng)?shù)念A(yù)處理是確保K-means++聚類算法成功應(yīng)用及最大化效率和效果的關(guān)鍵。這一方法論在數(shù)據(jù)科學(xué)領(lǐng)域的各個(gè)方面均有廣泛應(yīng)用，且對提升算法性能有直接且顯著的貢獻(xiàn)。

參考文獻(xiàn)：

[1] 李博.基于聚類分析的強(qiáng)化學(xué)習(xí)方法研究[D].成都：電子科技大學(xué)，2020.

[2] 李硯君.酒類電商精準(zhǔn)營銷研究[D].深圳：深圳大學(xué)，2017.

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

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

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

【通聯(lián)編輯：謝媛媛】

基金項(xiàng)目：第五期江蘇省職業(yè)教育教學(xué)改革研究課題：五年制高職創(chuàng)新創(chuàng)業(yè)教育課程體系構(gòu)建的實(shí)踐研究（以江蘇聯(lián)合職業(yè)技術(shù)學(xué)院揚(yáng)州分院為例）（項(xiàng)目編號：ZYB376）