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

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

中圖分類號：TP 312" " " " " " 文獻標志碼：A

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

1 相關概念介紹

1.1 K-means聚類算法

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

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

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

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

1.2 加權K-means聚類算法

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

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

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

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

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

1.3 肘部法則

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

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

使用肘部法則確定的合理 K值不僅可以保持聚類精度，而且可以降低算法的復雜度，為加權聚類算法的應用提供重要的指導。

2 試驗結果和分析

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

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

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

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

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

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

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

由圖4可知，拐點在7。當數(shù)據(jù)集簇的個數(shù)定位7時，WWCSS的下降趨勢有了明顯的變化，即K值確定。測試集中數(shù)據(jù)點的加權聚類結果分布如圖5所示。

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

3 結論

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

參考文獻

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

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

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

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

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

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

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

[8]周愛武，于亞飛.K-Means聚類算法的研究[J].計算機技術與發(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.