在生活中，我们常常会对事物进行分组，以便更好地理解甚至简化它们。例如，你和朋友想要对电子游戏进行分类。你的朋友可能想按游戏类型来分类，从而将所有游戏整齐地划分成一个个小类别；而你则可能根据游戏开发商来分类，最终得到的集合就会与你朋友的不同。

注意：这两个集合都源自相同的数据池（电子游戏），并且都从数据中学习到了一些有趣的信息。

在机器学习中，我们也做类似的事情：让机器自动对数据进行分组，以获取有意义的信息。这种对无标签数据的分组称为聚类。该分组基于数据点之间的相似性。聚类完成后，同一簇内的数据点应尽可能相似，不同簇之间的数据点则应尽可能不同。

如下图所示，我们有一组数据点：

如果我们把点之间的距离视为“不相似程度”，那么可以明显看出存在三个不同的簇。但对于机器而言，要自动发现这些簇，需要一个稳健的算法支持。

上图中的数据分布清晰、边界明确，并且是二维展示的。但在现实世界中，数据远没有这么干净，而且当特征超过三个时，就几乎无法用图形直观展示了。

注意：聚类算法的效果高度依赖于其所使用的相似性或不相似性函数。

什么是相似性和不相似性函数？

相似性函数用于衡量任意两个数据点之间共享的相似程度，是一种量化两个对象相似度的数值指标。也就是说，只要有两个数据点，我们就可以计算它们彼此有多相似。
不相似性函数则用于计算任意两个数据点之间的差异程度，是衡量两个数据对象差异性的数值指标。

欧氏距离

两点 $\bold x=(x_1, x_2, \dots, x_d)$ 和 $\bold y=(y_1, y_2, \dots, y_d)$ 之间的欧氏距离 $E$ 可表示为： $E(\bold x, \bold y) = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2+\dots+(x_d - y_d)^2}$

注意：欧氏距离是不相似性的一个典型例子。

我们可以使用以下公式计算上图中两点之间的欧氏距离：

欧氏\hspace{1mm}距离\hspace{1mm}(d)=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}

下面代码实现了欧氏距离的计算：

1import numpy as np
2from numpy.linalg import norm
3
4def E(x, y):
5  return norm(x-y)
6
7x, y = np.random.rand(10), np.random.rand(10)
8print(E(x,y))

注意：在聚类框架中，选择何种相似性或不相似性函数是一个超参数。

余弦相似度

考虑在 $d$ 维特征空间中，两个数据点 $\bold x=(x_1,x_2,\dots,x_d)$ 和 $\bold y=(y_1,y_2,\dots,y_d)$ 之间的相似性。一种定义方式是使用点积。更常用的方法是归一化的点积，也被称为余弦相似度。

下面代码实现了余弦相似度的计算：

1import numpy as np
2from numpy.linalg import norm
3
4def cosine_similarity(x, y):
5  return x.dot(y)/(norm(x)*norm(y))
6
7x, y = np.random.rand(10), np.random.rand(10)
8print(cosine_similarity(x,y))

上述代码中，x.dot(y) 表示 x 和 y 的点积，norm(x) 表示向量 x 的欧氏范数（即 L2 范数），相关内容已在正则化课程中学过。

注意：不同的相似性或不相似性函数可能导致聚类算法产生不同的结果。

记住：相似性与不相似性呈反比关系。

聚类的实际局限性

直观上看，聚类似乎是一项简单的任务。例如，观察下面两幅图：

图 A 和图 B 的边界非常清晰，很容易区分。这种情况在现实中确实存在，但我们需要智能的聚类算法才能让机器自动识别出来。别担心，这类算法有很多。现在来看一个连人类都可能难以判断的例子：

观察上图，这个数据集很难被明确划分为簇。类似地，有些数据只能由特定算法成功聚类，其他算法则会失败。即使是图 A 和图 B 中的数据，也可能被错误分类。请看下面的 A2 和 B2 图：

因此，我们必须先了解所面对的是哪一类聚类问题，才能有效解决这些问题。

聚类的类别

聚类算法主要分为三类：

• 划分式聚类（如 $k$-均值、PAM、CLARA）
• 基于密度的聚类（如 DBSCAN）
• 层次聚类（如 BIRCH、CURE）

聚类算法的代码示例

下面我们结合代码示例，深入了解几种常用的聚类算法：

$K$-均值（K-means）

划分式聚类算法将数据划分为 $k$ 个子集，使得总体方差（各簇方差之和）最小。$K$-均值是最典型的划分式聚类算法之一。

1# 导入所需包
2import numpy as np
3import matplotlib.pyplot as plt
4from sklearn import cluster, datasets
5from sklearn.cluster import KMeans
6
7
8# 创建包含3个簇的合成数据集
9X, Y = datasets.make_blobs(
10    n_samples=100, cluster_std=[0.5, 1, 2], random_state=1
11)
12
13# 使用K-Means将数据划分为3个簇
14kmeans = KMeans(n_clusters=3)
15kmeans.fit(X)
16y_kmeans = kmeans.predict(X)
17
18# 并排绘制原始数据集与聚类结果
19fig, axs = plt.subplots(1, 2)
20axs[0].scatter(x=X[:,0], y=X[:,1])
21axs[0].set_title("实际数据集")
22axs[1].scatter(x=X[:, 0], y=X[:, 1],  c=y_kmeans)
23axs[1].set_title('K-Means聚类结果')
24plt.show()

DBSCAN

DBSCAN 是一种基于密度的聚类算法，它通过统计每个数据点在一定半径内的邻居数量来评估其密度。然后在低密度区域切割高密度区域，形成簇。

注意：定义“邻居”时可采用任意相似性或距离度量方法，最常用的是欧氏距离。

1# 导入所需包
2import numpy as np
3import matplotlib.pyplot as plt
4from sklearn import cluster, datasets
5from sklearn.cluster import DBSCAN
6
7# 创建包含3个簇的合成数据集
8data_points_count = 100
9X, Y = datasets.make_blobs(
10    n_samples=data_points_count, cluster_std=[0.5, 0.5, 0.5], random_state=4
11)
12
13# 使用DBSCAN进行聚类
14dbscan = DBSCAN(eps=1, min_samples=3)
15db_y = dbscan.fit_predict(X)
16
17# 并排绘制原始数据集与聚类结果
18fig, axs = plt.subplots(1, 2)
19axs[0].scatter(x=X[:,0], y=X[:,1])
20axs[0].set_title("实际数据集")
21axs[1].scatter(x=X[:, 0], y=X[:, 1],  c=db_y)
22axs[1].set_title('DBSCAN聚类结果')
23plt.show()

凝聚层次聚类（Agglomerative Clustering）

在层次聚类算法中，每一步都会合并（凝聚式）或分裂（分裂式）初始簇。在分裂式聚类中，初始将整个数据集视为一个簇，每步将其拆分为多个子簇以最小化总方差；而在凝聚式聚类中，初始每个数据点自成一簇，每步将最近的两个簇合并。两种方法均在形成 k 个簇后停止。

1# 导入必要包
2import numpy as np
3import matplotlib.pyplot as plt
4from sklearn import cluster, datasets
5from sklearn.cluster import AgglomerativeClustering
6
7# 生成合成数据集
8data_points_count = 100
9X, Y = datasets.make_blobs(
10    n_samples=data_points_count, cluster_std=[1.3, 0.6, 1.5], random_state=4
11)
12
13# 使用凝聚层次聚类进行聚类
14clustering_model = AgglomerativeClustering(n_clusters=3, linkage="ward")
15agglo_y = clustering_model.fit_predict(X)
16
17# 并排绘制原始数据集与聚类结果
18fig, axs = plt.subplots(1, 2)
19axs[0].scatter(x=X[:,0], y=X[:,1])
20axs[0].set_title("实际数据集")
21axs[1].scatter(x=X[:, 0], y=X[:, 1],  c=agglo_y)
22axs[1].set_title('凝聚层次聚类结果')
23plt.show()