基于Python的加權(quán)K-means聚類算法研究

摘 要：本文針對(duì)K均值聚類算法在現(xiàn)實(shí)問題中的復(fù)雜性提出一種加權(quán)的聚類算法。K-means算法是一種經(jīng)典的聚類算法，針對(duì)這種算法中的問題，目前有很多處理方法，例如確定初始聚類數(shù)K值、選擇初始聚類中心點(diǎn)、數(shù)據(jù)點(diǎn)的權(quán)重影響以及孤立點(diǎn)的處理方式等。在實(shí)際問題中，坐標(biāo)數(shù)據(jù)點(diǎn)的權(quán)重不同，本文將權(quán)值附加在數(shù)據(jù)點(diǎn)中，再使用肘部法則計(jì)算聚類數(shù)K值的最佳選擇，分析數(shù)據(jù)點(diǎn)歸屬的簇。在數(shù)據(jù)集中進(jìn)行比較，試驗(yàn)結(jié)果表明，與原算法相比，本文算法更接近實(shí)際數(shù)據(jù)分布，輪廓系數(shù)更接近1，聚類效果更好。

關(guān)鍵詞：加權(quán)K-means算法；肘部法則；輪廓系數(shù)

中圖分類號(hào)：TP 312" " " " " " 文獻(xiàn)標(biāo)志碼：A

21世紀(jì)是信息時(shí)代，大量數(shù)據(jù)利用聚類算法挖掘有效的信息，聚類算法在各個(gè)方面得到了新的發(fā)展。例如其與深度學(xué)習(xí)結(jié)合，利用深度學(xué)習(xí)來提高聚類性能，成為無監(jiān)督學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)。再例如其與圖像識(shí)別領(lǐng)域結(jié)合，有研究提出一種基于余弦定理和K-means的識(shí)別方法[1]。將聚類算法應(yīng)用于大規(guī)模數(shù)據(jù)集，探索在串行計(jì)算環(huán)境中基于樣例選擇、增量學(xué)習(xí)、特征子集和特征轉(zhuǎn)換的聚類算法[2]。K-means算法在確定算法中聚類數(shù)目 K值、初始聚類中心選取、離群點(diǎn)的檢測(cè)與去除以及距離與相似性度量等方面有一定的局限性[3]。針對(duì)初始點(diǎn)問題，可以使用粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法，收斂速度較快[4]。在全局搜索能力提升的基礎(chǔ)上，優(yōu)化局部搜索策略，使其在進(jìn)化過程中始終保持勘探能力最佳[5]?；诿芏人惴▋?yōu)化初始聚類中心，這種方法能夠優(yōu)化聚類結(jié)果[6]，根據(jù)距離和的思想消除聚類分析結(jié)果中的孤立點(diǎn)的影響[7-8]。

1 相關(guān)概念介紹

1.1 K-means聚類算法

K-means算法是一種基于劃分的無監(jiān)督學(xué)習(xí)的聚類算法，采用歐式距離作為衡量數(shù)據(jù)對(duì)象間相似度的指標(biāo)，相似度與數(shù)據(jù)對(duì)象間的距離成反比，相似度越大，距離越小。K-means算法預(yù)定義K的值[4]，指定K個(gè)初始聚類中心，并將給定數(shù)據(jù)集劃分為K個(gè)簇，經(jīng)過多次迭代不斷降低類簇的誤差平方和（Sum of Squared Error，SSE），最小化簇內(nèi)平方和（Within-Cluster Sum of Squares，WCSS），當(dāng)簇中心點(diǎn)以及數(shù)據(jù)所屬簇趨于穩(wěn)定時(shí)，聚類結(jié)束，得到最終結(jié)果。

給定一個(gè)數(shù)據(jù)集X={x1，x2，...，xn}，每個(gè)xi屬于d維空間，預(yù)定義簇的數(shù)量 K，K-means的作用是找到使以下目標(biāo)函數(shù)最小化的簇中心μ={μ1，μ2，...，μK}，如公式（1）所示。

數(shù)據(jù)點(diǎn)至其所屬簇的中心點(diǎn)的距離的平方和，其值越小，聚類效果越好。

該算法計(jì)算數(shù)據(jù)集中每個(gè)數(shù)據(jù)點(diǎn)至所有初始數(shù)據(jù)中心的距離的最小值，將其分配至最近的中心點(diǎn)所屬的簇中，并不斷更新簇中心點(diǎn)的坐標(biāo)，迭代計(jì)算數(shù)據(jù)點(diǎn)所屬的新簇，直至算法收斂為止，將數(shù)據(jù)分割為誤差平方和最小的K個(gè)簇。

1.2 加權(quán)K-means聚類算法

在傳統(tǒng)的K-means聚類算法中，每個(gè)數(shù)據(jù)點(diǎn)對(duì)聚類的貢獻(xiàn)都是相同的。但是，在實(shí)際問題中，有許多要素對(duì)數(shù)據(jù)點(diǎn)有加成或削弱作用。為了解決這個(gè)問題，采用數(shù)據(jù)點(diǎn)加權(quán)的聚類算法。一種常見的加權(quán)聚類算法是加權(quán)K-means算法，這種加權(quán)距離能夠同時(shí)捕捉數(shù)據(jù)點(diǎn)之間的全局空間關(guān)聯(lián)和局部變化趨勢(shì)。在這個(gè)算法中[9]，每個(gè)目標(biāo)數(shù)據(jù)點(diǎn)都賦予1個(gè)權(quán)值，這個(gè)權(quán)值反映了數(shù)據(jù)點(diǎn)在聚類過程中的重要程度，將權(quán)值附加在計(jì)算K-means算法過程中，得到更具有代表性的聚類結(jié)果。

具體來說，假設(shè)數(shù)據(jù)點(diǎn)X={x1，x2，...，xn}，每個(gè)點(diǎn)xi都有一個(gè)相應(yīng)的權(quán)重wi，那么加權(quán)K-means算法的目標(biāo)函數(shù)如公式（2）所示。

加權(quán)K-means算法的基本步驟如下。輸入：數(shù)據(jù)集為X，數(shù)據(jù)點(diǎn)權(quán)重為W，預(yù)定義的簇?cái)?shù)量為K。輸出：簇中心為μ，數(shù)據(jù)點(diǎn)所屬簇為C。

采用加權(quán) K-means 算法可以有效地將數(shù)據(jù)點(diǎn)分配至最佳的簇中。該算法有以下5個(gè)核心步驟。1）隨機(jī)選擇K個(gè)點(diǎn)作為初始簇中心μ0。2）計(jì)算數(shù)據(jù)集X中的每個(gè)數(shù)據(jù)點(diǎn)xi至每個(gè)簇中心點(diǎn)μi的加權(quán)距離，將該數(shù)據(jù)點(diǎn)分配至與其加權(quán)距離最短的簇中心點(diǎn)所對(duì)應(yīng)的簇Ci。3）計(jì)算每個(gè)簇Ci中所有數(shù)據(jù)點(diǎn)的加權(quán)平均值，將其作為新的簇中心點(diǎn)μi。4）重復(fù)步驟2、3，直至目標(biāo)函數(shù)G不再變化，算法收斂。5）輸出結(jié)果，返回簇中心μ和數(shù)據(jù)集中所有數(shù)據(jù)點(diǎn)所屬簇C。

加權(quán)聚類算法在計(jì)算過程中考慮了數(shù)據(jù)點(diǎn)差異性，提高了聚類結(jié)果的準(zhǔn)確性和可信度，在實(shí)際生產(chǎn)中應(yīng)用前景廣闊。

1.3 肘部法則

在聚類算法中，確定簇的個(gè)數(shù)K值是一個(gè)重要的研究方向。常用的方法包括經(jīng)驗(yàn)法則、肘部法則和輪廓系數(shù)等。經(jīng)驗(yàn)法則是基于經(jīng)驗(yàn)或知識(shí)來確定個(gè)數(shù)的一種常用方法，在準(zhǔn)確性要求不高的情景中可以采用。當(dāng)使用加權(quán)聚類算法時(shí)，將每個(gè)數(shù)據(jù)點(diǎn)按照重要程度賦予不同的權(quán)值，問題分析的緯度更多，對(duì)K的確定要求更高，因此肘部法則是一個(gè)很好的選擇。

在通常情況下，隨著K值遞增，WWCSS會(huì)逐漸降低，當(dāng)?shù)竭_(dá)某一點(diǎn)后，誤差幅度會(huì)顯著降低，出現(xiàn)1個(gè)肘部拐點(diǎn)，整條曲線呈現(xiàn)為肘部形狀。這個(gè)肘部對(duì)應(yīng)的點(diǎn)的K值即最佳K值。在后續(xù)加權(quán)聚類算法中，根據(jù)K值進(jìn)行計(jì)算，得到的聚類效果最好，呈現(xiàn)的簇的區(qū)分最明顯，也更符合實(shí)際情況。

使用肘部法則確定的合理 K值不僅可以保持聚類精度，而且可以降低算法的復(fù)雜度，為加權(quán)聚類算法的應(yīng)用提供重要的指導(dǎo)。

2 試驗(yàn)結(jié)果和分析

本文將傳統(tǒng)K-means算法應(yīng)用于實(shí)際聚類問題中，將數(shù)據(jù)點(diǎn)用特征值進(jìn)行加權(quán)，分析聚類效果。本文采用的測(cè)試數(shù)據(jù)集是Yelp平臺(tái)在美國賓夕法尼亞州所有餐廳的數(shù)據(jù)。在數(shù)據(jù)集中共有514條餐廳數(shù)據(jù)，每條數(shù)據(jù)包括餐廳的15個(gè)屬性信息：'business_id'， 'name'，'neighborhood'，'address'， 'city'，'state'，'postal_code'，'latitude'，'longitude'，'stars'，'review_count'，'is_open'，'attributes'，'categories'，'hours'。其中星級(jí)評(píng)價(jià)分為1～5級(jí)，由用戶給出，該評(píng)價(jià)是1個(gè)餐廳非常重要的信息，決定后根據(jù)餐廳星級(jí)，用戶是否會(huì)去這個(gè)餐廳就餐，因此可以將這個(gè)參數(shù)作為每行數(shù)據(jù)的權(quán)重。計(jì)算這個(gè)地區(qū)哪個(gè)范圍內(nèi)的餐廳密度最高，基于城市聚集效應(yīng)，以此作為推薦后續(xù)新餐廳的選址依據(jù)。為解決這個(gè)問題，采用K-means算法計(jì)算坐標(biāo)點(diǎn)的聚類結(jié)果，并比較傳統(tǒng)K-means算法與加權(quán)聚類算法在聚類效果方面的差異，本文主要比較輪廓系數(shù)的值。

當(dāng)比較2個(gè)聚類方法的問題時(shí)，通常比較2個(gè)算法的聚類誤差，誤差越小，聚類效果越好。但是本文比較的是加權(quán)聚類和傳統(tǒng)聚類的聚類效果，在加權(quán)的情況下考慮了每個(gè)數(shù)據(jù)點(diǎn)的權(quán)重，自然加權(quán)聚類誤差的WWCSS應(yīng)該大于傳統(tǒng)聚類誤差的WCSS，因此，比較2種聚類的輪廓系數(shù)（Silhouette Coefficient）來判斷效果。輪廓系數(shù)是一種常用的聚類效果評(píng)估指標(biāo)，其作用是衡量聚類的緊密度和分離度。輪廓系數(shù)的取值范圍為[-1，1]，其值越接近1，聚類效果越好；其值越接近-1，聚類效果越差，值接近0表示聚類效果不明顯?；趥鹘y(tǒng)K-means算法，采用肘部法則計(jì)算這514個(gè)數(shù)據(jù)的聚類數(shù)K值，數(shù)據(jù)點(diǎn)使用'latitude'，'longitude'這2個(gè)參數(shù)作圖，聚類數(shù)K值與WCSS的變化曲線如圖1所示。

由圖1可知，曲線肘部的取值為k=6，即當(dāng)聚類數(shù)為6時(shí)，聚類的效果最好。當(dāng)聚類數(shù)K=6時(shí)，測(cè)試集中數(shù)據(jù)點(diǎn)的聚類結(jié)果分布如圖2所示。

由圖2可知，Cluster 的數(shù)據(jù)點(diǎn)最多，當(dāng)經(jīng)緯度為[40.40～40.47， -80.11～-79.94]時(shí)，可以作為后續(xù)新餐廳的選址推薦。在傳統(tǒng)K-means算法中，WCSS為0.632，輪廓系數(shù)為0.518。

基于加權(quán)K-means算法，先統(tǒng)計(jì)測(cè)試集中每個(gè)數(shù)據(jù)點(diǎn)的權(quán)重分布情況，星級(jí)評(píng)價(jià)等級(jí)頻數(shù)統(tǒng)計(jì)如圖3所示。利用肘部法則計(jì)算這些數(shù)據(jù)的最佳聚類數(shù)K值。

餐廳星級(jí)評(píng)價(jià)等級(jí)為1～5。由圖3可知，顧客星級(jí)評(píng)價(jià)等級(jí)主要集中在3.0、3.5和4.0，等級(jí)兩端的出現(xiàn)頻率最低。也就是說514個(gè)數(shù)據(jù)點(diǎn)的權(quán)值分布在1～5的離散數(shù)中，3.0、3.4和4.0的出現(xiàn)頻率最高。

采用肘部法則計(jì)算這514個(gè)數(shù)據(jù)當(dāng)使用加權(quán)聚類算法時(shí)的最佳K值，K值與WWCSS的變化曲線如圖4所示。其中橫坐標(biāo)為聚類數(shù)K的值，縱坐標(biāo)為加權(quán)的WWCSS。

由圖4可知，拐點(diǎn)在7。當(dāng)數(shù)據(jù)集簇的個(gè)數(shù)定位7時(shí)，WWCSS的下降趨勢(shì)有了明顯的變化，即K值確定。測(cè)試集中數(shù)據(jù)點(diǎn)的加權(quán)聚類結(jié)果分布如圖5所示。

由圖5可知，Cluster2的數(shù)據(jù)點(diǎn)最多，當(dāng)經(jīng)緯度為[40.41～40.54，-79.98～-79.88]時(shí)餐廳的密集度最高，可以作為后續(xù)新餐廳的選址推薦。在加權(quán)K-means算法中，WWCSS為1.669，輪廓系數(shù)為0.523。

3 結(jié)論

本文采用特征值加權(quán)的聚類方法處理坐標(biāo)數(shù)據(jù)點(diǎn)，將聚類問題應(yīng)用于復(fù)雜因素影響的數(shù)據(jù)集中。使用肘部法則確定最佳簇個(gè)數(shù)K值，最后完成數(shù)據(jù)點(diǎn)集合。與傳統(tǒng)K-means算法得到的輪廓系數(shù)相比，加權(quán)K-means得到的輪廓系數(shù)更大，更接近1，因此聚類效果更好，更符合實(shí)際情況。在實(shí)際問題中，數(shù)據(jù)點(diǎn)的信息是復(fù)雜的，下一步的研究重點(diǎn)是基于多維度給數(shù)據(jù)點(diǎn)加權(quán)。

參考文獻(xiàn)

[1]姬強(qiáng)，孫艷豐，胡永利，等.深度聚類算法研究綜述[J].北京工業(yè)大學(xué)學(xué)報(bào)，2021，47（8）：912-924.

[2]朱顥東，申圳.基于余弦定理和K-means的植物葉片識(shí)別方法[J].華中師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，48（5）：650-655.

[3]何玉林，黃哲學(xué).大規(guī)模數(shù)據(jù)集聚類算法的研究進(jìn)展[J].深圳大學(xué)學(xué)報(bào)（理工版），2019，36（1）：4-17.

[4]楊俊闖，趙超.K-means聚類算法研究綜述[J].計(jì)算機(jī)工程與應(yīng)用，2019，55（23）：7-14，63.

[5]劉靖明，韓麗川，侯立文.基于粒子群的K均值聚類算法[J].系統(tǒng)工程理論與實(shí)踐，2005（6）：54-58.

[6]陶新民，徐晶，楊立標(biāo)，等.一種改進(jìn)的粒子群和K均值混合聚類算法[J].電子與信息學(xué)報(bào)，2010，32（1）：92-97.

[7]傅德勝，周辰.基于密度的改進(jìn)K均值算法及實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2011，31（2）：432-434.

[8]周愛武，于亞飛.K-Means聚類算法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（2）：62-65.

[9]NING" Z" L，CHEN" J，HUANG" J" J ，et al.WeDIV -An improved"k-means clustering algorithm with a weighted distance and a novel"internal validation index[J].Egyptian Informatics Journal，2022，23（4）：133-144.