描述
聚类（clustering）是将数据集划分成组的任务，这些组叫作簇（cluster）。其目标是划分数据，使得一个簇内的数据点非常相似且不同簇内的数据点非常不同。与分类算法类似，聚类算法为每个数据点分配（或预测）一个数字，表示这个点属于哪个簇。
K均值聚类
k 均值聚类是最简单也最常用的聚类算法之一。它试图找到代表数据特定区域的簇中心（cluster center）。算法交替执行以下两个步骤：将每个数据点分配给最近的簇中心，然后将每个簇中心设置为所分配的所有数据点的平均值。如果簇的分配不再发生变化，那么算法结束。
用 scikit-learn 应用 k 均值相当简单。将KMeans 类实例化，并设置要寻找的簇个数 ，然后对数据调用fit方法：
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
X,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_moons
X,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 AgglomerativeClustering
X,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,ward
X,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 DBSCAN
X,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 StandardScaler
X,Y = make_moons(random_state=0,noise=0.05,n_samples=200)
scaler = StandardScaler()
scaler.fit(X)
X_scaled = scaler.transform(X) # 将数据缩放成均值为0，方差为1
scan = 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_score
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("{}:{:.2f}".format(algorithm.__class__.__name__,silhouette_score(X_scaled,clusters)))
k 均值的轮廓分数最高。DBSCAN 的结果最好，但得分不高。对于评估聚类，稍好的策略是使用基于鲁棒性的（robustness-based）聚类指标。这种指标先向数据中添加一些噪声，或者使用不同的参数设定，然后运行算法，并对结果进行比较。其思想是，如果许多算法参数和许多数据扰动返回相同的结果，那么它很可能是可信的。