K-means算法及其應用實踐

摘要：機器學習分為監(jiān)督學習和無監(jiān)督學習，無監(jiān)督學習一個非常重要的用途就是對數(shù)據(jù)進行聚類。聚類算法則是在完全沒有標簽的情況下，算法“猜測”哪些數(shù)據(jù)應該聚為一類。K-means算法是被廣泛應用的一種聚類算法，K-means算法的關鍵是選擇合適的k值，文章通過鳶尾花聚類展示K-means算法應用。

關鍵詞：K-means算法;聚類;無監(jiān)督學習;機器學習

一、何為聚類

聚類（Clustering）是一種典型的“無監(jiān)督學習”。聚類算法是對大量未知標記的數(shù)據(jù)集，根據(jù)數(shù)據(jù)之間的距離或者說是相似性（親疏性）將數(shù)據(jù)集劃分為多個簇（Cluster），使簇內(nèi)的數(shù)據(jù)相似度盡可能大，而簇間的數(shù)據(jù)相似度盡可能小。

聚類的目的是把數(shù)據(jù)分類，但是事先我們不知道如何劃分，即聚類的類別和數(shù)目沒有預先的定義，是根據(jù)數(shù)據(jù)點的相似性（即數(shù)據(jù)點之間的距離）來劃分的。

聚類與分類最大的區(qū)別是：聚類為無監(jiān)督學習，待處理數(shù)據(jù)沒有任何先驗知識，而分類是有監(jiān)督學習，即存在先驗知識的訓練數(shù)據(jù)集。

二、K-means聚類算法原理

K-means算法也稱為k均值算法，由于其簡潔和效率，成為所有聚類算法中應用最為廣泛的一種聚類算法。對于給定的樣本集，按照樣本之間距離的大小，將樣本集劃分成k個簇，讓簇內(nèi)的數(shù)據(jù)點盡量緊密地連接，而簇與簇之間的距離盡量大。k是簇的個數(shù)，k由用戶指定，每個簇中所有點的中心稱為質心，k均值算法根據(jù)某個距離函數(shù)反復把數(shù)據(jù)分入k個簇中。

K-means聚類算法的工作原理是：先隨機選取k個點作為初始的聚類中心，然后針對每個數(shù)據(jù)點，計算每個點與各個聚類中心之間的距離，把每個點歸為距離它最近的聚類中心代表的簇類。一次迭代結束之后，重新計算每個簇類的中心點，然后針對每個點，重新尋找距離自己最近的中心點。如此循環(huán)，直到前后兩次迭代的簇類沒有變化。

終止條件可以是以下任何一個：

（1）沒有（或最小數(shù)目）對象被重新分配給不同的聚類。

（2）沒有（或最小數(shù)目）聚類中心再發(fā)生變化。

（3）誤差平方和局部最小。

三、K-means算法流程

K-means算法是一個反復迭代的過程，算法的基本步驟為：

步驟1：選定要聚類的類別數(shù)目k，隨機選擇k個中心點（質心）。

步驟2：針對每個樣本點，找到距離其最近的中心點（尋找組織），距離同一中心點最近的點為一個類，這樣完成了一次聚類。

步驟3：判斷聚類前后的樣本點的類別情況是否相同，如果相同，則算法終止，否則進入步驟4。

步驟4：針對每個類別中的樣本點，計算這些樣本點的中心點，當做該類的新的中心點（即將每個類別中所有對象所對應的均值作為該類別的聚類中心點），繼續(xù)步驟2。

上述步驟的關鍵兩點是：1. 找到距離自己最近的中心點。2. 更新中心點。

常用的距離度量標準是歐幾里得距離的平方：

四、K-means算法中K值的選擇

K-means算法中的k值需要預先確定，k值設為幾即聚幾類。在實際應用中k值是非常難以選擇的，通常的做法是多嘗試幾個k值，看聚成幾類的結果更好解釋，更符合分析目的等。

還可以采用“肘”方法（Elbow method）確定k值。該方法的原理就是最小化點到聚類中心的距離。

“肘”方法的步驟：

（1）對于n個點的數(shù)據(jù)集，迭代計算k from 1 to n，每次聚類完成后計算每個點到其所屬的簇中心的距離的平方和;

（2）平方和是會逐漸變小的，直到k==n時平方和為0，因為每個點都是它所在的簇中心本身;

（3）在這個平方和變化過程中，會出現(xiàn)一個拐點也即“肘”點，下降率突然變緩時即認為是最佳的k值。

一般來說，手肘圖都會展現(xiàn)出一個肘部輪廓，下降率突然變緩時即認為是最佳的k值。

隨著聚類數(shù)k的增大，樣本劃分會更加精細，每個簇的聚合程度會逐漸提高，那么簇內(nèi)距離平方和自然會逐漸變小。并且，當k小于真實聚類數(shù)時，由于k的增大會大幅增加每個簇的聚合程度，故簇內(nèi)距離平方和的下降幅度會很大，而當k到達真實聚類數(shù)時，再增加k所得到的聚合程度回報會迅速變小，所以簇內(nèi)距離平方和的下降幅度會驟減，然后隨著k值的繼續(xù)增大而趨于平緩，也就是說簇內(nèi)距離平方和和k的關系圖是一個手肘的形狀，而這個肘部對應的k值就是數(shù)據(jù)的真實聚類數(shù)。

五、K-means算法實現(xiàn)鳶尾花數(shù)據(jù)的聚類

任務目標：使用scikit-learn內(nèi)置的鳶尾花數(shù)據(jù)集，該數(shù)據(jù)集每條記錄都有4個特征：花萼長度（calyx length）、花萼寬度（calyx width）、花瓣長度（petal length）、花瓣寬度（petal width），通過這4個特征可以預測鳶尾花屬于哪一品種。我們選取數(shù)據(jù)的后兩個特征，即花瓣長度和花瓣寬度作為訓練數(shù)據(jù)，首先根據(jù)繪制的鳶尾花數(shù)據(jù)分布圖查看數(shù)據(jù)分分布情況，然后繪制出手肘圖，進一步輔助確定合理的k值。

步驟一：選取鳶尾花數(shù)據(jù)集的后兩個特征即花瓣長度和寬度，繪制出鳶尾花數(shù)據(jù)分布圖，如圖1所示。

從鳶尾花數(shù)據(jù)分布圖可以大致看出鳶尾數(shù)據(jù)的分布情況。

步驟二：繪制出分類數(shù)1到7時，分類數(shù)（k）和簇內(nèi)距離和inertia的對應關系圖，即手肘圖，如圖2所示。

觀察圖中各點的曲率可以看到，k=3之后，簇內(nèi)距離平方和inertia的下降變得很緩慢了，因此最佳的k值為3。

步驟三：選擇最佳k值，k=3時繪制聚類效果圖，如圖3所示。

3個類別的鳶尾花數(shù)據(jù)分別用綠色的五角星、紅色的圓點和藍色的+號表示，可以看到k=3時的聚類效果很好。

六、總結

聚類用于數(shù)據(jù)集內(nèi)種類屬性不明晰，希望通過數(shù)據(jù)挖掘或自動歸類出有相似特點的對象的場景。K-means算法可用于維數(shù)、數(shù)值都很小且連續(xù)的數(shù)據(jù)集，比如在市場營銷領域，建立合理的客戶價值評估模型，對客戶進行分群，分析不同客戶群的客戶價值，從而制定相應的營銷策略，對不同的客戶群提供個性化的服務等。

K-means算法原理比較簡單，實現(xiàn)也很容易，收斂速度快，聚類效果也比較好，算法的可解釋度比較強，主要需要調(diào)參的參數(shù)是簇數(shù)k。但k值的選取不好把握，本文采用繪制手肘圖的方法輔助選取最佳的k值。

參考文獻

[1] 鐘志峰，李明輝，張艷.機器學習中自適應k 值的k 均值算法改進[J].計算機工程與設計，2021，42（1）：136-141.

[2] 李玥.機器學習的分類、聚類研究[J].電腦知識與技術，2020，16（4）：161-162.

[3] 季杰，陳強仁，朱東.基于機器學習的航空客戶價值分析[J].電腦知識與技術，2020，16（14）：238-239.

作者簡介：張松慧（1980-），女，湖北武漢人，武漢軟件工程職業(yè)學院副教授/信息系統(tǒng)項目管理師，碩士，研究方向人工智能技術應用。