描述

聚類（clustering）是將數據集劃分成組的任務，這些組叫作簇（cluster）。其目標是劃分數據，使得一個簇內的數據點非常相似且不同簇內的數據點非常不同。與分類算法類似，聚類算法為每個數據點分配（或預測）一個數字，表示這個點屬于哪個簇。

K均值聚類

k 均值聚類是最簡單也最常用的聚類算法之一。它試圖找到代表數據特定區域的簇中心（cluster center）。算法交替執行以下兩個步驟：將每個數據點分配給最近的簇中心，然后將每個簇中心設置為所分配的所有數據點的平均值。如果簇的分配不再發生變化，那么算法結束。

用 scikit-learn 應用 k 均值相當簡單。將KMeans 類實例化，并設置要尋找的簇個數 ，然后對數據調用fit方法：

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeansX,Y = make_blobs(random_state=1)
kmeans = KMeans(n_clusters=3) # 構建模型
kmeans.fit(X)print('Cluster memberships:\n{}'.format(kmeans.labels_))

通過n_clusters參數設置KMeans模型的簇個數。

也可以用 predict 方法為新數據點分配簇標簽。預測時會將最近的簇中心分配給每個新數據點，但現有模型不會改變。對訓練集運行 predict 會返回與 labels_ 相同的結果：

print(kmeans.predict(X))

可以看到，聚類算法與分類算法有些相似，每個元素都有一個標簽。但并不存在真實的標簽，因此標簽本身并沒有先驗意義。

簇中心被保存在 cluster_centers_ 屬性中，用三角形表示它們：

mglearn.discrete_scatter(X[:,0],X[:,1],kmeans.labels_,markers='o')
mglearn.discrete_scatter(kmeans.cluster_centers_[:,0],kmeans.cluster_centers_[:,1],[0,1,2],markers='^',markeredgewidth=2)

也可以使用更多或更少的簇中心:

fig,axes=plt.subplots(1,2,figsize=(10,5))kmeans = KMeans(n_clusters=2)
kmeans.fit(X)
assigments = kmeans.labels_
mglearn.discrete_scatter(X[:,0],X[:,1],assigments,ax=axes[0])kmeans = KMeans(n_clusters=5)
kmeans.fit(X)
assigments = kmeans.labels_
mglearn.discrete_scatter(X[:,0],X[:,1],assigments,ax=axes[1])

K均值的失敗案例

即使知道給定數據集中簇的“正確”個數，k 均值可能也不是總能找到它們。k 均值只能找到相對簡單的形狀。k 均值還假設所有簇在某種程度上具有相同的“直徑”，它總是將簇之間的邊界剛好畫在簇中心的中間位置。

如果遇到一個簇是凸形的，這時K均值分類會導致令人疑惑的結果。

X_varied,Y_varied=make_blobs(n_samples=200,cluster_std=[1.0,2.5,0.5],random_state=170)
y_pred = KMeans(n_clusters=3,random_state=0).fit_predict(X_varied)mglearn.discrete_scatter(X_varied[:,0],X_varied[:,1],y_pred)
plt.legend(['cluster 0','cluster 1','cluster 2'],loc='best')
plt.xlabel('feature 0')
plt.xlabel('feature 1')

k 均值還假設所有方向對每個簇都同等重要。數據中包含明確分開的三部分。但是這三部分被沿著對角線方向拉長。由于 k 均值僅考慮到最近簇中心的距離，所以它無法處理這種類型的數據：

X,Y = make_blobs(random_state=170,n_samples=600)
rng = np.random.RandomState(74)transformation = rng.normal(size=(2,2))X = np.dot(X,transformation)kmeans = KMeans(n_clusters=3)
kmeans.fit(X)
y_pred = kmeans.predict(X)plt.scatter(X[:,0],X[:,1],c=y_pred,cmap = mglearn.cm3)
plt.scatter(kmeans.cluster_centers_[:,0],kmeans.cluster_centers_[:,1],marker='^',c=[0,1,2],s=100,linewidths=2,cmap=mglearn.cm3)
plt.xlabel('feature 0')
plt.xlabel('feature 1')

如果簇的形狀更加復雜，例如two_moons這樣的數據，k均值表現得會更差

from sklearn.datasets import make_moonsX,Y = make_moons(random_state=0,noise=0.05,n_samples=200)
kmeans = KMeans(n_clusters=3)
kmeans.fit(X)
y_pred = kmeans.predict(X)plt.scatter(X[:,0],X[:,1],c=y_pred,cmap = mglearn.cm3)
plt.scatter(kmeans.cluster_centers_[:,0],kmeans.cluster_centers_[:,1],marker='^',c=[0,1,2],linewidths=1,cmap=mglearn.cm3)
plt.xlabel('feature 0')
plt.xlabel('feature 1')

矢量化

雖然 k 均值是一種聚類算法，但在 k 均值和分解方法（PCA、NMF）之間存在一些有趣的相似之處。PCA 試圖找到數據中方差最大的方向，而NMF 試圖找到累加的分量，這通常對應于數據的“極值”或“部分”。兩種方法都試圖將數據點表示為一些分量之和。與之相反，k 均值則嘗試利用簇中心來表示每個數據點。

可以將其看作僅用一個分量來表示每個數據點，該分量由簇中心給出。這種觀點將 k 均值看作是一種分解方法，其中每個點用單一分量來表示，這種觀點被稱為矢量量化（vector quantization）。（簡單得來說就是增大n_clusters值，把簇細化）

在看two_moons這樣的數據，把分簇提高到10：

X,Y = make_moons(random_state=0,noise=0.05,n_samples=200)
kmeans = KMeans(n_clusters=10)
kmeans.fit(X)
y_pred = kmeans.predict(X)plt.scatter(X[:,0],X[:,1],c=y_pred,cmap = mglearn.cm3)
plt.scatter(kmeans.cluster_centers_[:,0],kmeans.cluster_centers_[:,1],marker='^',c=range(kmeans.n_clusters),linewidths=1,cmap=mglearn.cm3)
plt.xlabel('feature 0')
plt.xlabel('feature 1')

k 均值是非常流行的聚類算法，因為它不僅相對容易理解和實現，而且運行速度也相對較快。k 均值可以輕松擴展到大型數據集，scikit-learn 甚至在 MiniBatchKMeans 類中包含了一種更具可擴展性的變體，可以處理非常大的數據集。

k 均值的缺點之一在于，它依賴于隨機初始化，也就是說，算法的輸出依賴于隨機種子。默認情況下，scikit-learn 用 10 種不同的隨機初始化將算法運行 10 次，并返回最佳結果。4 k 均值還有一個缺點，就是對簇形狀的假設的約束性較強，而且還要求指定所要尋找的簇的個數

凝聚聚類

凝聚聚類（agglomerative clustering）指的是許多基于相同原則構建的聚類算法，這一原則是：算法首先聲明每個點是自己的簇，然后合并兩個最相似的簇，直到滿足某種停止準則為止。

scikit-learn 中實現的停止準則是簇的個數，因此相似的簇被合并，直到僅剩下指定個數的簇。還有一些鏈接（linkage）準則，規定如何度量“最相似的簇”。這種度量總是定義在兩個現有的簇之間。

scikit-learn 中實現了以下四種選項：

• ward：默認選項。挑選兩個簇來合并，使得所有簇中的方差增加最小。這通常會得到大小差不多相等的簇。
• average：鏈接將簇中所有點之間平均距離最小的兩個簇合并。
• complete：（也稱為最大鏈接）將簇中點之間最大距離最小的兩個簇合并。
• single：單次使用兩組所有觀測值之間的最小距離。

ward 適用于大多數數據集。如果簇中的成員個數非常不同（比如其中一個比其他所有都大得多），那么 average 或 complete 可能效果更好。如果簇形狀不規則且有明顯得分界可以考慮single。

from sklearn.cluster import AgglomerativeClusteringX,Y = make_blobs(random_state=1)agg = AgglomerativeClustering(n_clusters=3)
assigments = agg.fit_predict(X)mglearn.discrete_scatter(X[:,0],X[:,1],assigments)
plt.xlabel("Feature 0")
plt.xlabel("Feature 1")

在看two_moons這樣的數據，使用single可以完美分開：

X,Y = make_moons(random_state=0,noise=0.05,n_samples=200)
agg = AgglomerativeClustering(n_clusters=2,linkage='single')
assigments = agg.fit_predict(X)mglearn.discrete_scatter(X[:,0],X[:,1],assigments)
plt.xlabel("Feature 0")
plt.xlabel("Feature 1")

層次聚類與樹狀圖

凝聚聚類生成了所謂的層次聚類（hierarchical clustering）。聚類過程迭代進行，每個點都從一個單點簇變為屬于最終的某個簇。每個中間步驟都提供了數據的一種聚類（簇的個數也不相同）。有時候，同時查看所有可能的聚類是有幫助的。雖然這種可視化為層次聚類提供了非常詳細的視圖，但它依賴于數據的二維性質，因此不能用于具有兩個以上特征的數據集。

另一個將層次聚類可視化的工具，叫作樹狀圖（dendrogram），它可以處理多維數據集。可以利用 SciPy 輕松生成樹狀圖。SciPy 提供了一個函數，接受數據數組 X 并計算出一個鏈接數組（linkage array），它對層次聚類的相似度進行編碼。然后可以將這個鏈接數組提供給 scipy 的 dendrogram 函數來繪制樹狀圖：

from scipy.cluster.hierarchy import dendrogram,wardX,Y = make_blobs(random_state=0,n_samples=12)
linkage_array = ward(X)
dendrogram(linkage_array)ax = plt.gca()
bounds = ax.get_xbound()
ax.plot(bounds,[7.25,7.25],'--',c='k')
ax.plot(bounds,[4,4],'--',c='k')ax.text(bounds[1],7.25,'two clusters',va='center',fontdict={'size':15})
ax.text(bounds[1],4,'three clusters',va='center',fontdict={'size':15})
plt.xlabel('sample index')
plt.ylabel('cluster distance')

DBSCAN

另一個非常有用的聚類算法是 DBSCAN（具有噪聲的基于密度的空間聚類應用）。DBSCAN 的主要優點是它不需要用戶先驗地設置簇的個數，可以劃分具有復雜形狀的簇，還可以找出不屬于任何簇的點。DBSCAN 比凝聚聚類和 k 均值稍慢，但仍可以擴展到相對較大的數據集。

DBSCAN 的原理是識別特征空間的“擁擠”區域中的點，在這些區域中許多數據點靠近在一起。這些區域被稱為特征空間中的密集（dense）區域。DBSCAN 背后的思想是，簇形成數據的密集區域，并由相對較空的區域分隔開。

在密集區域內的點被稱為核心樣本（core sample，或核心點）。

DBSCAN 有兩個參數：min_samples 和 eps。如果在距一個給定數據點 eps 的距離內至少有 min_samples 個數據點，那么這個數據點就是核心樣本。DBSCAN 將彼此距離小于 eps 的核心樣本放到同一個簇中。

算法首先任意選取一個點，然后找到到這個點的距離小于等于 eps 的所有的點。如果距起始點的距離在 eps 之內的數據點個數小于 min_samples，那么這個點被標記為噪聲（noise），也就是說它不屬于任何簇。與核心點的距離在 eps 之內的點叫作邊界點（boundary point）。

X,Y = make_blobs(random_state=0,n_samples=12)
scan = DBSCAN()
clusters = scan.fit_predict(X)
print("Cluster memberships:\n{}".format(clusters))

所有數據點都被分配了標簽 -1，這代表噪聲。這是 eps 和 min_samples 默認參數設置的結果，對于小型的玩具數據集并沒有調節這些參數。min_samples 和 eps 取不同值時的簇分類如下所示：

mglearn.plots.plot_dbscan()

屬于簇的點是實心的，而噪聲點則顯示為空心的。核心樣本顯示為較大的標記，而邊界點則顯示為較小的標記。增大 eps（在圖中從左到右），更多的點會被包含在一個簇中。這讓簇變大，但可能也會導致多個簇合并成一個。增大 min_samples（在圖中從上到下），核心點會變得更少，更多的點被標記為噪聲。

參數 eps 在某種程度上更加重要，因為它決定了點與點之間“接近”的含義。將 eps 設置得非常小，意味著沒有點是核心樣本，可能會導致所有點都被標記為噪聲。將 eps 設置得非常大，可能會導致所有點形成單個簇。

在看two_moons這樣的數據，設置eps=0.3（默認0.5），min_samples=10（默認5）：

from sklearn.cluster import DBSCANX,Y = make_moons(random_state=0,noise=0.05,n_samples=200)
scan = DBSCAN(eps=0.3,min_samples=10)
assigments = scan.fit_predict(X)mglearn.discrete_scatter(X[:,0],X[:,1],assigments)
plt.xlabel("Feature 0")
plt.xlabel("Feature 1")

通過StandardScaler縮放two_moons數據，同樣可以達到上面得效果：

from sklearn.preprocessing import StandardScalerX,Y = make_moons(random_state=0,noise=0.05,n_samples=200)
scaler = StandardScaler()
scaler.fit(X)
X_scaled = scaler.transform(X) # 將數據縮放成均值為0，方差為1scan = DBSCAN()
assigments = scan.fit_predict(X_scaled)mglearn.discrete_scatter(X_scaled[:,0],X_scaled[:,1],assigments)
plt.xlabel("Feature 0")
plt.xlabel("Feature 1")

在使用 DBSCAN 時，你需要謹慎處理返回的簇分配。如果使用簇標簽對另一個數據進行索引，那么使用 -1 表示噪聲可能會產生意料之外的結果。

聚類算法得對比與評估

在應用聚類算法時，其挑戰之一就是很難評估一個算法的效果好壞，也很難比較不同算法的結果。在討論完 k 均值、凝聚聚類和 DBSCAN 背后的算法之后，下面將在一些現實世界的數據集上比較它們。

用真實值評估聚類

有些指標可以用于評估聚類算法相對于真實聚類得結果，其中最重要得是調整rand指數（ARI）和歸一化互信息（NMI），兩者都給出了定量的度量，其最佳值為1，0表示不相關的聚類（ARI可以取負值）

ARI

使用 ARI 來比較 k 均值、凝聚聚類和 DBSCAN 算法：

import numpy as np
import matplotlib.pyplot as plt
import mglearn
from sklearn.datasets import make_moons
from sklearn.cluster import KMeans,DBSCAN,AgglomerativeClustering
from sklearn.preprocessing import StandardScaler
from sklearn.metrics.cluster import adjusted_rand_score # (ARI 評分函數)X,Y = make_moons(n_samples=200,noise=0.05,random_state=0)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
fig,axes = plt.subplots(1,4,figsize=(15,3),subplot_kw={'xticks':(),'yticks':()})
algorithms = [KMeans(n_clusters=2),AgglomerativeClustering(n_clusters=2),DBSCAN()]
random_state = np.random.RandomState(seed=0) # 創建一個隨機的簇分配，作為參考
random_clusters = random_state.randint(low=0,high=2,size=len(X))
axes[0].scatter(X_scaled[:,0],X_scaled[:,1],c=random_clusters,cmap = mglearn.cm3,s=60)
axes[0].set_title("Random assignment - ARI:{:.2f}".format(adjusted_rand_score(Y,random_clusters)))
for ax,algorithm in zip(axes[1:],algorithms):clusters = algorithm.fit_predict(X_scaled) # 獲取算法推算結果ax.scatter(X_scaled[:,0],X_scaled[:,1],c=clusters,cmap=mglearn.cm3,s=60)ax.set_title("{} - ARI:{:.2f}".format(algorithm.__class__.__name__,adjusted_rand_score(Y,clusters)))#adjusted_rand_score(Y,clusters) # 對比實際結果與算法推算結果（打分）

用這種方式評估聚類時，一個常見的錯誤是使用 accuracy_score 而不是 adjusted_rand_score、normalized_mutual_info_score 或其他聚類指標。使用精度的問題在于，它要求分配的簇標簽與真實值完全匹配。但簇標簽本身毫無意義。

from sklearn.metrics import accuracy_score# 這兩種點標簽對應于相同的聚類
clusters1=[0,0,1,1,0]
clusters2=[1,1,0,0,1]
# 精度為0，因為二者標簽完全不同
print("Accuracy:{:.2f}".format(accuracy_score(clusters1,clusters2)))
# 調整rand分數為1，因為二者聚類完全相同
print("ARI:{:.2f}".format(adjusted_rand_score(clusters1,clusters2)))

NMI

使用 NMI 來比較 k 均值、凝聚聚類和 DBSCAN 算法（用法與ARI基本一致）：

from sklearn.metrics import normalized_mutual_info_score # (NMI 評分函數)fig,axes = plt.subplots(1,4,figsize=(15,3),subplot_kw={'xticks':(),'yticks':()})
algorithms = [KMeans(n_clusters=2),AgglomerativeClustering(n_clusters=2),DBSCAN()]axes[0].scatter(X_scaled[:,0],X_scaled[:,1],c=random_clusters,cmap = mglearn.cm3,s=60)
axes[0].set_title("Random assignment - ARI:{:.2f}".format(adjusted_rand_score(Y,random_clusters)))
for ax,algorithm in zip(axes[1:],algorithms):clusters = algorithm.fit_predict(X_scaled)ax.scatter(X_scaled[:,0],X_scaled[:,1],c=clusters,cmap=mglearn.cm3,s=60)ax.set_title("{} - NMI:{:.2f}".format(algorithm.__class__.__name__,normalized_mutual_info_score(Y,clusters)))

在沒有真實值的情況下評估聚類

在應用聚類算法時，通常沒有真實值來比較結果。如果知道了數據的正確聚類，那么可以使用這一信息構建一個監督模型（比如分類器）。因此，使用類似 ARI和 NMI 的指標通常僅有助于開發算法，但對評估應用是否成功沒有幫助。

有一些聚類的評分指標不需要真實值，比如輪廓系數（silhouette coeffcient）。但它們在實踐中的效果并不好。輪廓分數計算一個簇的緊致度，其值越大越好，最高分數為 1。雖然緊致的簇很好，但緊致度不允許復雜的形狀。

利用輪廓分數在 two_moons 數據集上比較 k 均值、凝聚聚類和 DBSCAN：

from sklearn.metrics.cluster import silhouette_scorefig,axes = plt.subplots(1,4,figsize=(15,3),subplot_kw={'xticks':(),'yticks':()})
algorithms = [KMeans(n_clusters=2),AgglomerativeClustering(n_clusters=2),DBSCAN()]axes[0].scatter(X_scaled[:,0],X_scaled[:,1],c=random_clusters,cmap = mglearn.cm3,s=60)
axes[0].set_title("Random assignment - ARI:{:.2f}".format(adjusted_rand_score(Y,random_clusters)))
for ax,algorithm in zip(axes[1:],algorithms):clusters = algorithm.fit_predict(X_scaled)ax.scatter(X_scaled[:,0],X_scaled[:,1],c=clusters,cmap=mglearn.cm3,s=60)ax.set_title("{}:{:.2f}".format(algorithm.__class__.__name__,silhouette_score(X_scaled,clusters)))

k 均值的輪廓分數最高。DBSCAN 的結果最好，但得分不高。對于評估聚類，稍好的策略是使用基于魯棒性的（robustness-based）聚類指標。這種指標先向數據中添加一些噪聲，或者使用不同的參數設定，然后運行算法，并對結果進行比較。其思想是，如果許多算法參數和許多數據擾動返回相同的結果，那么它很可能是可信的。