聚類就是將某個數(shù)據(jù)集中的樣本按照之間的某些區(qū)別劃分為若干個不相交的子集，我們把每個子集稱為一個“簇”。劃分完成后，每個簇都可能對應(yīng)著某一個類別；需說明的是，這些概念對聚類算法而言事先是未知的，聚類過程僅能自動形成簇結(jié)構(gòu)，簇對應(yīng)的概念語義由使用者來把握和命名。

有關(guān)聚類的算法很多，下面這張表格引用自Scikit-learn 官方文檔，從這張表中可以看到各個聚類算法之間的不同以及對不同數(shù)據(jù)及劃分時的匹配程度，和優(yōu)劣性。我們在選擇聚類算法的時候，首先一定要熟悉自己的數(shù)據(jù)，大概了解自己的數(shù)據(jù)是怎樣的一個分布和結(jié)構(gòu)。這樣，有利于我們選擇合適的算法，從而得到優(yōu)秀的聚類結(jié)果。這篇文章僅僅介紹K-means聚類算法，以及它的推廣版K-mean++算法。

k-means算法是使用最廣泛的聚類算法之一。聚類的目的是把相似的樣本聚到一起，把不相似的樣本分開。對于給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內(nèi)的點盡量緊密的連在一起，而讓簇間的距離盡量的大。

K-means算法旨在選擇一個質(zhì)心, 能夠最小化慣性或簇內(nèi)平方和的標準:

$$\sum{i=0}^{n} \min _{\mu{j} \in C}\left(\left|x{i}-\mu{j}\right|^{2}\right)$$

K-means算法原理分析

k-means算法是聚類分析中使用最廣泛的算法之一。它把n個對象根據(jù)它們的屬性分為k個簇以便使得所獲得的簇滿足：同一簇中的對象相似度較高；而不同簇中的對象相似度較小。 k-means算法的基本過程如下所示：

1. 首先隨機選取K個初始質(zhì)心，最基本的方法是從數(shù)據(jù)集$X$中選擇$K$個樣本。
2. 將每個樣本分配到其最近的質(zhì)心。通過取分配給前一個質(zhì)心的所有樣本的平均值來創(chuàng)建新的質(zhì)心。
3. 計算新舊質(zhì)心之間的差值，算法重復最后兩個步驟，直到該值小于閾值。換句話說，算法重復這個步驟，直到質(zhì)心不再明顯移動。

下圖是Scikit-learn具體實現(xiàn)代碼：

print(__doc__) # Author: Phil Roth  # License: BSD 3 clause import numpy as np import matplotlib.pyplot as plt

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs

plt.figure(figsize=(12, 12)) n_samples = 1500 random_state = 170 
X, y = make_blobs(n_samples=n_samples, random_state=random_state) # Incorrect number of clusters 
y_pred = KMeans(n_clusters=2, random_state=random_state).fit_predict(X) plt.subplot(221)
plt.scatter(X[:, 0], X[:, 1], c=y_pred) plt.title("Incorrect Number of Blobs") # Anisotropicly distributed data 
transformation = [[0.60834549, -0.63667341], [-0.40887718, 0.85253229]] 
X_aniso = np.dot(X, transformation) y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_aniso) 
plt.subplot(222)
plt.scatter(X_aniso[:, 0], X_aniso[:, 1], c=y_pred) 
plt.title("Anisotropicly Distributed Blobs") # Different variance 
X_varied, y_varied = make_blobs(n_samples=n_samples,                                
cluster_std=[1.0, 2.5, 0.5],                     
random_state=random_state) y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_varied) 
plt.subplot(223)
plt.scatter(X_varied[:, 0], X_varied[:, 1], c=y_pred) plt.title("Unequal Variance") # Unevenly sized blobs 
X_filtered = np.vstack((X[y == 0][:500], X[y == 1][:100], X[y == 2][:10])) 
y_pred = KMeans(n_clusters=3,                
random_state=random_state).fit_predict(X_filtered) plt.subplot(224)
plt.scatter(X_filtered[:, 0], X_filtered[:, 1], 
c=y_pred) plt.title("Unevenly Sized Blobs")

plt.show()

K-means算法的優(yōu)缺點

優(yōu)點：簡單，易于理解和實現(xiàn)；收斂快，一般僅需5-10次迭代即可，高效

缺點：

• 對K值得選取把握不同對結(jié)果有很大的不同（初始化不同質(zhì)心的計算通常會進行幾次。幫助解決這個問題的一種方法是 k-means++ 初始化方案，它已經(jīng)在 scikit-learn 中實現(xiàn)（使用 init='k-means++' 參數(shù)）。 這將初始化質(zhì)心（通常）彼此遠離，相對隨機初始化得到更好的結(jié)果）
• 對于初始點的選取敏感，不同的隨機初始點得到的聚類結(jié)果可能完全不同
• 對于不是凸的數(shù)據(jù)集比較難收斂
• 對噪點過于敏感，因為算法是根據(jù)基于均值的
• 結(jié)果不一定是全局最優(yōu)，只能保證局部最優(yōu)
• 對球形簇的分組效果較好，對非球型簇、不同尺寸、不同密度的簇分組效果不好。

K-means算法的優(yōu)缺點

優(yōu)點：簡單，易于理解和實現(xiàn)；收斂快，一般僅需5-10次迭代即可，高效

缺點：

• 對K值得選取把握不同對結(jié)果有很大的不同（初始化不同質(zhì)心的計算通常會進行幾次。幫助解決這個問題的一種方法是 k-means++ 初始化方案，它已經(jīng)在 scikit-learn 中實現(xiàn)（使用 init='k-means++' 參數(shù)）。 這將初始化質(zhì)心（通常）彼此遠離，相對隨機初始化得到更好的結(jié)果）
• 對于初始點的選取敏感，不同的隨機初始點得到的聚類結(jié)果可能完全不同
• 對于不是凸的數(shù)據(jù)集比較難收斂
• 對噪點過于敏感，因為算法是根據(jù)基于均值的
• 結(jié)果不一定是全局最優(yōu)，只能保證局部最優(yōu)
• 對球形簇的分組效果較好，對非球型簇、不同尺寸、不同密度的簇分組效果不好。