Python机器学习笔记（十三、k均值聚类）

聚类（clustering）是将数据集划分成组的任务，这些组叫作簇（cluster）。其目标是划分数据，使得一个簇内的数据点非常相似且不同簇内的数据点非常不同。与分类算法类似，聚类算法为每个数据点分配（或预测）一个数字，表示这个点属于哪个簇。

k均值聚类

k均值聚类是最简单也最常用的聚类算法之一。它试图找到代表数据特定区域的簇中心（cluster center）。算法交替执行以下两个步骤：将每个数据点分配给最近的簇中心，然后将每个簇中心设置为所分配的所有数据点的平均值。如果簇的分配不再发生变化，那么算法结束。下面在一个模拟数据集上对这一算法进行示例学习：

import matplotlib.pyplot as plt
import mglearnmglearn.plots.plot_kmeans_algorithm()
plt.show()

输出图形：

上图输出了：输入数据与 k 均值算法的三个步骤。簇中心用三角形表示，而数据点用圆形表示。颜色表示簇成员。我们指定要寻找三个簇，所以通过声明三个随机数据点为簇中心来将算法初始化（上图中“Initialization”/“初始化”）。然后开始迭代算法。首先，每个数据点被分配给距离最近的簇中心（上图中 “Assign Points (1)”/“分配数据点（1）”）。接下来，将簇中心修改为所分配点的平均值（上图中“Recompute Centers (1)”/“重新计算中心（1）”）。然后将这一过程再重复两次。在第三次迭代之后，为簇中心分配的数据点保持不变，因此算法结束。给定新的数据点，k均值会将其分配给最近的簇中心。下面的代码示例展示了上图中学到的簇中心的边界：

import matplotlib.pyplot as plt
import mglearnmglearn.plots.plot_kmeans_boundaries()
plt.show()

输出结果：

上图输出k均值算法找到的簇中心和簇边界。

下面我们使用 scikit-learn 库来应用k均值聚类算法。我们将其应用于上图中的模拟数据，将KMeans 类实例化，并设置我们要寻找的簇个数3（如果不指定n_clusters，它的默认值是 8）。然后对数据调用 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)
# 算法运行期间，为 X 中的每个训练数据点分配一个簇标签。可以在 kmeans.labels_ 属性中找到这些标签
print("Cluster memberships:\n{}".format(kmeans.labels_))

输出结果：

Cluster memberships:
[0 2 2 2 1 1 1 2 0 0 2 2 1 0 1 1 1 0 2 2 1 2 1 0 2 1 1 0 0 1 0 0 1 0 2 1 2
2 2 1 1 2 0 2 2 1 0 0 0 0 2 1 1 1 0 1 2 2 0 0 2 1 1 2 2 1 0 1 0 2 2 2 1 0
0 2 1 1 0 2 0 2 2 1 0 0 0 0 2 0 1 0 0 2 2 1 1 0 1 0]

因为我们要找的是3个簇，所以簇的编号是0到2。也可以用predict方法为新数据点分配簇标签。预测时会将最近的簇中心分配给每个新数据点，但现有模型不会改变。对训练集运行predict会返回与 labels_相同的结果：

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)
# 算法运行期间，为 X 中的每个训练数据点分配一个簇标签。可以在 kmeans.labels_ 属性中找到这些标签
print("Cluster memberships:\n{}".format(kmeans.labels_))
print(kmeans.predict(X))

输出相同结果：

可以看到，聚类算法与分类算法有些相似，每个元素都有一个标签。但并不存在真实的标签，因此标签本身并没有先验意义。我们回到之前讨论过的人脸图像聚类的例子。聚类的结果可能是，算法找到的第3个簇仅包含Bela的面孔。但只有在查看图片之后才能知道这一点，而且数字3是任意的。算法给的唯一信息就是所有标签为3的人脸都是相似的。

对于上面我们在二维玩具数据集上运行的聚类算法，意味着我们不应该为其中一组的标签是0、另一组的标签是1这一事实赋予任何意义。再次运行该算法可能会得到不同的簇编号，原因在于初始化的随机性质。下面绘制这个数据的图像，簇中心被保存在cluster_centers_ 属性中，用三角形表示它们：

import matplotlib.pyplot as plt
import mglearn
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)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)
plt.show()

输出图像：

上图是：3个簇的k均值算法找到的簇分配和簇中心。我们也可以使用更多或更少的簇中心：

import matplotlib.pyplot as plt
import mglearn
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans# 生成模拟的二维数据
X, y = make_blobs(random_state=1)
fig, axes = plt.subplots(1, 2, figsize=(10, 5))
# 使用2个簇中心：
kmeans = KMeans(n_clusters=2)
kmeans.fit(X)
assignments = kmeans.labels_
mglearn.discrete_scatter(X[:, 0], X[:, 1], assignments, ax=axes[0])
# 使用5个簇中心：
kmeans = KMeans(n_clusters=5)
kmeans.fit(X)
assignments = kmeans.labels_
mglearn.discrete_scatter(X[:, 0], X[:, 1], assignments, ax=axes[1])
plt.show()

输出结果：

上图是：使用2个簇（左）和5个簇（右）的k均值算法找到的簇分配。

k均值的失败案例

即使知道给定数据集中簇的“正确”个数，k均值可能也不是总能找到它们。每个簇仅由其中心定义，这意味着每个簇都是凸形（convex）。因此，k均值只能找到相对简单的形状。k均值还假设所有簇在某种程度上具有相同的“直径”，它总是将簇之间的边界刚好画在簇中心的中间位置。有时这会导致令人惊讶的结果，如下：

import matplotlib.pyplot as plt
import mglearn
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeansX_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.ylabel("Feature 1")
plt.show()

输出结果：

上图是：簇的密度不同时，k均值找到的簇分配。可能会认为，左下方的密集区域是第一个簇，右上方的密集区域是第二个，中间密度较小的区域是第三个。事实上，簇0和簇1都包含一些远离簇中其他点的点。 k均值还假设所有方向对每个簇都同等重要。下面的示例显示了一个二维数据集，数据中包含明确分开的三部分。但是这三部分被沿着对角线方向拉长。由于k均值仅考虑到最近簇中心的距离，所以它无法处理这种类型的数据：

import numpy as np
import matplotlib.pyplot as plt
import mglearn
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans# 生成一些随机分组数据
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)
# 将数据聚类成3个簇
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, linewidth=2, cmap=mglearn.cm3)
plt.xlabel("Feature 0")
plt.ylabel("Feature 1")
plt.show()

输出结果：

上图是：k均值无法识别非球形簇。如果簇的形状更加复杂，比如之前学习用到的two_moons数据，那么k均值的表现也很差，如下：

import matplotlib.pyplot as plt
import mglearn
from sklearn.cluster import KMeans
from sklearn.datasets import make_moons# 生成模拟的two_moons数据（这次的噪声较小）
X, y = make_moons(n_samples=200, noise=0.05, random_state=0)
# 将数据聚类成2个簇
kmeans = KMeans(n_clusters=2)
kmeans.fit(X)
y_pred = kmeans.predict(X)
# 画出簇分配和簇中心
plt.scatter(X[:, 0], X[:, 1], c=y_pred, cmap=mglearn.cm2, s=60)
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], marker='^', c=[mglearn.cm2(0), mglearn.cm2(1)], s=100, linewidth=2)
plt.xlabel("Feature 0")
plt.ylabel("Feature 1")
plt.show()

输出结果：

上图是：k均值无法识别具有复杂形状的簇。

这里我们希望聚类算法能够发现两个半月形。但利用k均值算法是不可能做到这一点的。

矢量量化（将k均值看作分解）

k均值是一种聚类算法，但在k均值和分解方法（比如之前的PCA和NMF）之间存在一些有趣的相似之处。PCA 试图找到数据中方差最大的方向，而NMF试图找到累加的分量，这通常对应于数据的“极值”或“部分”。两种方法都试图将数据点表示为一些分量之和。与之相反，k均值则尝试利用簇中心来表示每个数据点。可以将其看作仅用一个分量来表示每个数据点，该分量由簇中心给出。这种观点将k均值看作是一种分解方法，其中每个点用单一分量来表示，被称为矢量量化（vector quantization）。下面来并排比较 PCA、NMF 和k均值，分别显示提取的分量，以及利用 100 个分量对测试集中人脸的重建。对于 k 均值，重建就是在训练集中找到的最近的簇中心：

import numpy as np
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.decomposition import PCA
from sklearn.datasets import fetch_lfw_people
from sklearn.decomposition import NMF
from sklearn.cluster import KMeanspeople = fetch_lfw_people(min_faces_per_person=20, resize=0.7)
image_shape = people.images[0].shape
mask = np.zeros(people.target.shape, dtype=np.bool_)
for target in np.unique(people.target):mask[np.where(people.target == target)[0][:50]] = 1
X_people = people.data[mask]
y_people = people.target[mask]
# 将灰度值缩放到0到1之间，而不是在0到255之间
# 以得到更好的数据稳定性
X_people = X_people / 255.X_train, X_test, y_train, y_test = train_test_split(X_people, y_people, stratify=y_people, random_state=0)
nmf = NMF(n_components=100, random_state=0)
nmf.fit(X_train)
pca = PCA(n_components=100, random_state=0)
pca.fit(X_train)
kmeans = KMeans(n_clusters=100, random_state=0)
kmeans.fit(X_train)
X_reconstructed_pca = pca.inverse_transform(pca.transform(X_test))
X_reconstructed_kmeans = kmeans.cluster_centers_[kmeans.predict(X_test)]
X_reconstructed_nmf = np.dot(nmf.transform(X_test), nmf.components_)# 绘图
fig, axes = plt.subplots(3, 5, figsize=(8, 8), subplot_kw={'xticks': (), 'yticks': ()})
fig.suptitle("Extracted Components")
for ax, comp_kmeans, comp_pca, comp_nmf in zip(axes.T, kmeans.cluster_centers_, pca.components_, nmf.components_):ax[0].imshow(comp_kmeans.reshape(image_shape))ax[1].imshow(comp_pca.reshape(image_shape), cmap='viridis')ax[2].imshow(comp_nmf.reshape(image_shape))
axes[0, 0].set_ylabel("kmeans")
axes[1, 0].set_ylabel("pca")
axes[2, 0].set_ylabel("nmf")fig, axes = plt.subplots(4, 5, subplot_kw={'xticks': (), 'yticks': ()}, figsize=(8, 8))
fig.suptitle("Reconstructions")
for ax, orig, rec_kmeans, rec_pca, rec_nmf in zip(axes.T, X_test, X_reconstructed_kmeans, X_reconstructed_pca, X_reconstructed_nmf):ax[0].imshow(orig.reshape(image_shape))ax[1].imshow(rec_kmeans.reshape(image_shape))ax[2].imshow(rec_pca.reshape(image_shape))ax[3].imshow(rec_nmf.reshape(image_shape))
axes[0, 0].set_ylabel("original")
axes[1, 0].set_ylabel("kmeans")
axes[2, 0].set_ylabel("pca")
axes[3, 0].set_ylabel("nmf")plt.show()

输出以下两个图形：

此图是：对比 k 均值的簇中心与 PCA 和 NMF 找到的分量

此图是：利用 100 个分量（或簇中心）的 k 均值、PCA 和 NMF 的图像重建的对比——k 均值的每张图像中仅使用了一个簇中心。

利用k 值做矢量量化的一个有趣之处在于，可以用比输入维度更多的簇来对数据进行编。让我们回到 two_moons 数据。利用 PCA 或 NMF，我们对这个数据无能为力，因为它只有两个维度。使用 PCA 或 NMF 将其降到一维，将会完全破坏数据的结构。但通过使用更多的簇中心，我们可以用 k 均值找到一种更具表现力的表示，看如下代码：

import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_moonsX, y = make_moons(n_samples=200, noise=0.05, random_state=0)
kmeans = KMeans(n_clusters=10, random_state=0)
kmeans.fit(X)
y_pred = kmeans.predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred, s=60, cmap='Paired')
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s=60, marker='^', c=range(kmeans.n_clusters), linewidth=2, cmap='Paired')
plt.xlabel("Feature 0")
plt.ylabel("Feature 1")
print("Cluster memberships:\n{}".format(y_pred))
plt.show()

输出结果和图形：

Cluster memberships:
[8 4 6 3 1 1 5 2 8 4 9 2 1 4 7 5 0 2 0 7 1 2 0 4 9 6 1 1 6 0 8 9 2 6 8 1 2
5 3 6 2 7 8 6 4 9 5 7 6 2 7 2 1 3 4 8 0 4 0 9 2 3 1 8 4 3 9 4 9 3 2 3 2 6
2 3 6 8 0 2 1 9 2 1 6 9 5 9 2 1 0 5 1 7 1 1 4 2 3 6 4 1 9 5 3 6 3 7 4 0 7
9 9 3 8 4 8 1 2 8 8 7 6 9 6 7 5 6 4 1 5 7 3 6 4 4 4 3 1 8 6 6 0 9 7 5 6 4
0 6 2 4 8 0 2 9 4 2 0 0 6 4 0 4 2 1 0 2 4 2 0 3 3 7 6 2 1 7 7 0 4 3 1 4 1
0 9 2 3 7 3 0 8 5 6 7 1 6 9 4]

上图是：利用 k 均值的许多簇来表示复杂数据集中的变化

我们使用了10个簇中心，也就是说，现在每个点都被分配了 0 到 9 之间的一个数字。可以将其看作10个分量表示的数据（有10个新特征），只有表示该点对应的簇中心的那个特征不为 0，其他特征均为 0。利用这个10维表示，现在可以用线性模型来划分两个半月形，而利用原始的两个特征是不可能做到这一点的。将到每个簇中心的距离作为特征，还可以得到一种表现力更强的数据表示。可以利用kmeans的transform方法来完成这一点：

from sklearn.cluster import KMeans
from sklearn.datasets import make_moonsX, y = make_moons(n_samples=200, noise=0.05, random_state=0)
kmeans = KMeans(n_clusters=10, random_state=0)
kmeans.fit(X)distance_features = kmeans.transform(X)
print("Distance feature shape: {}".format(distance_features.shape))
print("Distance features:\n{}".format(distance_features))

输出结果：

Distance feature shape: (200, 10)
Distance features:
[[0.53664613 1.15017588 0.93237626 ... 1.48034956 0.002907 1.07736639]
[1.74138152 0.60592307 1.00666225 ... 2.52921971 1.20779969 2.23716489]
[0.75710543 1.93145038 0.91586549 ... 0.78321505 0.87573753 0.71838465]
...
[0.9274342 1.73811046 0.57899268 ... 1.11471941 0.83358544 1.04125672]
[0.3227627 1.97647071 1.47861069 ... 0.81425026 0.84551232 0.28446737]
[1.63322944 0.47226506 1.02289983 ... 2.46626118 1.09767675 2.14812753]]

k均值是非常流行的聚类算法，因为它不仅相对容易理解和实现，而且运行速度也相对较快。k均值可以轻松扩展到大型数据集，scikit-learn甚至在MiniBatchKMeans类中包含了一种更具可扩展性的变体，可以处理非常大的数据集。

k均值的缺点之一在于，它依赖于随机初始化，也就是说，算法的输出依赖于随机种子。默认情况下，scikit-learn用10种不同的随机初始化将算法运行10次，并返回最佳结果。k均值还有一个缺点，就是对簇形状的假设的约束性较强，而且还要求指定所要寻找的簇的个数（在现实世界的应用中可能并不知道这个数字）。后面再学习两种改进的聚类算法。