聚類——K-Means與DBSCAN原理和應用（附Python代碼）
1 K-Means原理
K-Means演算法是一種基於距離的聚類演算法，K-Means演算法的思想很簡單，對於給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大。假設有訓練樣本 ，每個
，但沒有類標籤
，K-Means演算法描述如下：
2 K-Means中 K值的選擇
「手肘法」是利用誤差平方和（sum of the squared errors，SSE）的變化趨勢來作為選擇K值的指標。
其中 是第i個簇，p是
中的樣本點，
是
的質心，SSE是所有樣本的聚類誤差，可以表示聚類效果的好壞。舉一個例子：
# 手肘法選擇K值
# 生成隨機點數據
X, y = make_blobs(n_samples=400, centers=4, random_state=23, cluster_std=0.8)
SSE = [] #存放每次的誤差平方和
for k in range(1,9):
estimator = KMeans(n_clusters=k)
estimator.fit(X)
SSE.append(estimator.inertia_)
x = range(1,9)
plt.figure(figsize=(5,5))
plt.xlabel(k)
plt.ylabel(SSE)
plt.plot(x,SSE,o-)
plt.show()
隨著聚類數K的增大，樣本劃分會更加精細，每個簇的聚合程度會逐漸提高，那麼誤差平方和SSE自然會逐漸變小。並且，當K小於真實聚類數時，由於K的增大會大幅增加每個簇的聚合程度，故SSE的下降幅度會很大，而當K到達真實聚類數時，再增加K所得到的聚合程度回報會迅速變小，所以SSE的下降幅度會驟減，然後隨著K值的繼續增大而趨於平緩，也就是說SSE和K的關係圖是一個手肘的形狀，這也是該方法被稱為手肘法的原因，而這個肘部對應的K值就是數據的真實聚類數，這裡可以看出K等於4的時候最好。聚類效果如下：
3 DBSCAN原理
基於距離的聚類演算法比如K-Means有一個缺陷，就是對雜訊特別敏感，而且往往聚類簇的形狀是球狀簇。而DBSCAN（Density-Based Spatial Clustering of Application with Noise）演算法是一種基於密度的演算法，它可以發現任意形狀的聚類，這對於帶有噪音點的數據起著重要的作用。
該演算法涉及以下幾個概念：
-鄰域：對
其
-鄰域，包含樣本集D中與
的距離不大於
的樣本，即
。
- 核心對象：若
的
-鄰域至少包括MinPts個樣本，即
，則
為一個核心對象。
- 密度直達：若
位於
的
-鄰域中，且
是核心對象，則稱
由
密度直達。
- 密度可達：對
與
若存在樣本序列
，其中
且
由
密度直達，則稱
由
密度可達。
- 密度相連：對
與
若存在
使得
與
，均由
密度可達，則稱
由
密度相連。
基於這些概念，DBSCAN將「簇」定義為：由密度可達關係導出的最大的密度相連的樣本集合。形式化地說，給定鄰域參數 ，簇
是滿足以下性質的非空樣本集：
- 連接性：
由
密度相連。
- 最大性：
，
由
密度可達
。
4 二維數據聚類
4.1 K-means聚類實例
實驗中，採用隨機函數生成了4簇高斯樣本點，共400個，樣本中心分別為[-7,-2.5],[-8,5],[0,7],[5,0]，使用K-Means進行聚類，當數據標準差為0.8時，得到的結果如圖1所示，聚類評價如表1所示，聚類評價如表1。
Python代碼：
centers = np.array([[-7,-2.5],[-8,5],[0,7],[5,0]])
X, y = make_blobs(n_samples=400, centers=centers, random_state=23, cluster_std=0.8)
estimator = KMeans(init=random,n_clusters=4, algorithm=full)
y_pred = estimator.fit_predict(X)
clusters_centers = estimator.cluster_centers_
# 校正標籤
y_pred = unify_label(clusters_centers, centers, centers.shape[0], y_pred)
performance_evaluation(X, y, y_pred)
plt.figure(figsize=(10,5))
plt.subplot(121)
plt.scatter(X[:, 0], X[:, 1], s=20, c=y, marker=o)
plt.title("origin clusters (cluster_std:{})".format(str(cluster_std)))
plt.subplot(122)
plt.scatter(X[:, 0], X[:, 1], s=20, c=y_pred, marker=o)
plt.scatter(clusters_centers[:, 0], clusters_centers[:, 1], s=90, c=r, marker=*)
plt.title("KMeans clusters")
plt.show()
4.2 雜訊對聚類的影響
K-Means一個很大的缺陷就是對雜訊或者離羣點比較敏感，它無法區分出哪些是雜訊或者離羣點，只能給每一個數據點都判斷出一個類別來，這樣就會導致樣本質心偏移，導致誤判或者聚類緊密程度降低。於是本小節實驗中，在標準差為1的4簇高斯樣本點（400個）中添加了20個雜訊點。實驗對比了有雜訊和無雜訊情況下聚類結果，結果如圖2所示，聚類評價如表2所示。
DBSCAN是一種基於密度的演算法，它能夠將雜訊點找出來，所以在抗幹擾能力上具有一定優勢，其聚類結果如圖3所示，其中紫色的點被標為雜訊點：
小結：結果很明顯，加了雜訊以後，雜訊點也被加上了標籤，導致聚類評價下降。一方面表現在，雜訊點的標籤是錯的，另一方面表現在現有簇的緊密程度很低，這也是聚類效果不好的一種表現。DBSCAN由於其基於密度的演算法的優勢，對於雜訊點不那麼敏感。
Python代碼：
# 生成隨機點數據
centers = np.array([[-7,-2.5],[-8,5],[0,7],[5,0]])
X, y = make_blobs(n_samples=400, centers=4, random_state=23, cluster_std=1)
# 聚類
estimator = KMeans(init=random,n_clusters=4, algorithm=full)
y_pred = estimator.fit_predict(X)
clusters_centers = estimator.cluster_centers_
# 校正標籤
y_pred = unify_label(clusters_centers, centers, centers.shape[0], y_pred)
# 評估
performance_evaluation(X, y, y_pred)
plt.figure(figsize=(15,5))
plt.subplot(131)
plt.scatter(X[:, 0], X[:, 1], s=20, c=y_pred, marker=o)
plt.scatter(clusters_centers[:, 0], clusters_centers[:, 1], s=90, c=r, marker=*)
plt.title("clusters without noise")
# 生成[-5,10)的隨機雜訊點
noise = 15*np.random.random_sample((20,2))-5
noise_class = np.random.randint(4, size=20)
# 合併數據
X = np.r_[X, noise]
y = np.r_[y, noise_class]
# 聚類
estimator = KMeans(init=random,n_clusters=4, algorithm=full)
y_pred = estimator.fit_predict(X)
clusters_centers = estimator.cluster_centers_
# 校正標籤
y_pred = unify_label(clusters_centers, centers, centers.shape[0], y_pred)
# 評估
performance_evaluation(X, y, y_pred)
plt.subplot(132)
plt.scatter(X[:, 0], X[:, 1], s=20, c=y_pred, marker=o)
#plt.scatter(noise[:, 0], noise[:, 1], s=10, c=k, marker=s)
plt.scatter(clusters_centers[:, 0], clusters_centers[:, 1], s=90, c=r, marker=*)
plt.title("clusters with noise")
# DBSCAN演算法
X = StandardScaler().fit_transform(X)
db = DBSCAN(eps=0.2).fit(X)
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
labels = db.labels_
plt.subplot(133)
plt.scatter(X[:, 0], X[:, 1], s=20, c=labels, marker=o)
plt.title("DBSCAN clusters")
plt.show()
4.3 樣本點形狀對聚類的影響
K-Means演算法對於凸性數據具有良好的效果，能夠根據距離來講數據分為球狀類的簇，但對於非凸形狀的數據點，就無能為力了，比如環形數據等等，此時基於密度的演算法DBSCAN就更令人滿意了。圖4和圖5兩個例子。
Python代碼：
# 生成月亮形狀的隨機點數據
X, y = make_moons(n_samples=400, noise=0.05, random_state=23)
# 生成圓形的隨機點數據
#X, y = make_circles(n_samples=400, noise=0.05, factor=0.5, random_state=23
# 聚類
estimator = KMeans(init=random,n_clusters=2, algorithm=full)
y_pred = estimator.fit_predict(X)
clusters_centers = estimator.cluster_centers_
plt.figure(figsize=(10,5))
plt.subplot(121)
plt.scatter(X[:, 0], X[:, 1], s=20, c=y_pred, marker=o)
plt.title("k-means clusters")
X = StandardScaler().fit_transform(X)
db = DBSCAN().fit(X)
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
labels = db.labels_
plt.subplot(122)
plt.scatter(X[:, 0], X[:, 1], s=20, c=labels, marker=o)
plt.title("DBSCAN clusters")
plt.show()
5 圖像分割
圖像分割是圖像處理中的一種方法，圖像分割是指將一幅圖像分解成若干互不相交區域的集合，其實質可以看成是一種像素的聚類過程。
本實驗將圖A作為研究對象，在不同的K值下，使用K-Means進行聚類分析。每次聚類以後，都將同一類別下的像素點的RGB值設為該類質心取整後的值，圖B-E分別展示了K=2,4,8,12時的聚類效果圖。
小結：隨著K值的增大，圖像分類越來越細緻，值得注意的是，圖片中左邊女孩衣服上的口袋輪廓，直到K=12以後才比較明顯。另外，對色彩的表達也更接近原圖，但在處理陰影漸變的位置時就不那麼精準了，比如女孩裙子下擺的位置等。
Python代碼：
# RGB圖像聚類
data, row, col = load_data("k-on.jpg")
for k in range(2,15):
t0 = time()
estimator = KMeans(n_clusters=k)
label = estimator.fit_predict(data)
centroids = estimator.cluster_centers_.astype(int)
pic_new = Image.new("RGB",(row, col))
for i in range(row):
for j in range(col):
# 像素點RGB設為質心
pic_new.putpixel((i, j), tuple(centroids[label[col*i+j]]))
print(K-Means: K = {} time: {}s.format(k, (time()-t0)))
pic_new.save(kmeans_k_{}.jpg.format(k))
display(Image.open(kmeans_k_{}.jpg.format(k)))
參考
[1] 李航 《統計學習方法》
[2] K-means聚類最優k值的選取
[3] sklearn - Clustering
推薦閱讀：
