聚类

聚类是一种无监督的机器学习方法，它能使类似的对象从其他对象中分离出来。它是无监督的，因为我们没有给模型任何标签；它只是检查特征并确定哪些样本是相似的并属于一个群组。

常见的聚类算法有：

  • 分层聚类算法（Hierarchical Cluster Analysis, HCA）
  • K-means
  • Expectation Maximization
  • DBSCAN

分层聚类

分层聚类被分成两种类型：聚合型和分类型。

  • 聚合型：这是一种自下而上的方法，每个观测值都从它自己的聚类开始，随着层次的上升，成对的聚类被合并。
    最初，每个数据点被认为是一个单独的聚类。在每次迭代中，相似的聚类与其他聚类合并，直到形成一个聚类或 K 个聚类。聚合型聚类的流程如下：

    1. 在开始时，让每个数据点成为一个聚类
    2. 计算距离/邻近矩阵
    3. 重复步骤 4 和 5，直至只剩一个聚类
    4. 合并最近的两个聚类
    5. 更新距离/邻近矩阵以反映新聚类与原始聚类之间的类似程度

  • 分类型：这是一种自上而下的方法，所有的观测值都从一个聚类中开始，当人们向下移动层次时，会递归地进行拆分。

Figure 1 分层聚类

距离/邻近矩阵

距离的计算方式有很多种。平时在空间坐标系中，我们常使用的距离是欧几里得距离（Euclidean Distance），除此之外，还有曼哈顿距离、马哈拉诺比斯距离等。不同的距离计算方式会影响聚类的结果，常见公式如下：

  • 欧几里得距离 (Euclidean distance)
\|a - b\|_2 = \sqrt{\sum_i (a_i - b_i)^2}
  • 平方欧几里得距离 (Squared Euclidean distance)
\|a - b\|_2^2 = \sum_i (a_i - b_i)^2
  • 曼哈顿距离 (Manhattan distance)
\|a - b\|_1 = \sum_i |a_i - b_i|
  • 切比雪夫距离 (Maximum distance)
\|a - b\|_\infty = \max_i |a_i - b_i|
  • 马哈拉诺比斯距离 (Mahalanobis distance)
\sqrt{(a - b)^\top S^{-1} (a - b)}

其中 S 为协方差矩阵 (Covariance matrix)。

合并的标准

公式中的 d 是所使用 metric 计算的距离，常见的链接方法如下：

  • 全链接聚类 (Maximum or complete linkage clustering)
\max \{ d(a,b) : a \in A, b \in B \}
  • 单链接聚类 (Minimum or single linkage clustering)
\min \{ d(a,b) : a \in A, b \in B \}
  • 非加权平均链接聚类 (Unweighted average linkage clustering)
\frac{1}{|A| \cdot |B|} \sum_{a \in A} \sum_{b \in B} d(a,b)
  • 加权平均链接聚类 (Weighted average linkage clustering, WPGMA)
d(i \cup j, k) = \frac{d(i, k) + d(j, k)}{2}
  • 质心链接聚类 (Centroid linkage clustering, UPGMC)
\|c_s - c_t\|

其中 c_s 和 c_t 分别为聚类 s 和 t 的质心 (centroid)。

  • 最小能量聚类 (Minimum energy clustering)
\frac{2}{nm} \sum_{i,j=1}^{n,m} \|a_i - b_j\|_2 - \frac{1}{n^2} \sum_{i,j=1}^{n} \|a_i - a_j\|_2 - \frac{1}{m^2} \sum_{i,j=1}^{m} \|b_i - b_j\|_2

Min（单链接）

Figure 2 Min of Distance

相似性（C_1，C_2，C_3）= 分属两个聚类的点 P_i 和 P_j 之间距离的最小值。因为 C_1 与 C_2 之间的最小距离小于 C_1 与 C_3 之间的最小距离，所以 C_1 和 C_2 被合并。

只要两个聚类之间的差距不是非常大，这种方法就能分离出非椭圆形状。但是如果聚类之间存在噪音，MIN 方法不能正确分离聚类。

Max（全链接）

Figure 3 Max of Distance

相似性（C_1，C_3）= 分属两个聚类的点 P_i 和 P_j 之间的最大距离。C_3 和 C_1 合并到 C_4 中，因为 P_i 和 P_j 的距离最远。

如果聚类之间存在噪音，Max 方法在分离聚类方面表现良好，因为它找的是最远的点。然而 Max 方法偏向于球状聚类，并且总是倾向于打破大的聚类。

组平均和 Ward 方法

Figure 4 组平均和 Ward 方法

组平均法：

D(C_1, C_2) = \frac{1}{|C_1| \cdot |C_2|} \sum_{p_i \in C_1} \sum_{p_j \in C_2} \text{dist}(p_i, p_j)

Ward 法：

D(C_1, C_2) = \frac{|C_1| \cdot |C_2|}{|C_1| + |C_2|} \|\mu_{C_1} - \mu_{C_2}\|^2

中心距离法

Figure 5 中心距离法

计算两个聚类 C_1 和 C_2 的中心点，将两个中心点之间的相似度作为两个聚类的相似度。

分层聚类的复杂度

  • 空间复杂度：O(n^2)
  • 时间复杂度：O(n^3)（朴素实现）；使用优先队列等优化后可降至 O(n^2 \log n)

n 为点的数量。

K-means

K-means 聚类的目的是将 n 个观测值分为 k 个聚类，其中每个观测值都属于平均值最近的聚类。

Figure 6 K-means

  1. 给定初始 k 值
  2. 赋值：将每个观测值（每个圆圈）分配到平均数的欧几里得距离最小的聚类中，这在直觉上就是距离最近的质心
  3. 更新：计算新聚类中观测值的新平均值（中心点）
  4. 重复：直到中心值不再变化（收敛）

不同的初始中心点会明显地影响聚类结果，因为 K-means 也是一种贪心算法。

K 的确定

一般基于一些先验知识或常识。要是没有相关经验，可以设定多个 K 值，并评估聚类的结果。