聚类方法

聚类的基本概念

约定

假设有\(n\)个样本，每个样本有\(m\)个属性的特征向量组成。样本集合可以用矩阵\(X\)表示。矩阵的第\(j\)列表示第\(j\)个样本，第\(i\)行表示第一个属性值。

相似度和距离

距离和相似度是聚类的核心概念，其选择是聚类的根本问题。

Minkowski Distance

就是\(p-\)度量

Mahalanobis Distance

Mahalanobis Distance

给定一个样本集合\(X\)，其协方差矩阵记为\(S\)。样本\(x_i\)与样本\(x_j\)之间的 Mahalanobis Distance 定义为

\[ d_{ij} = \left[ (x_i - x_j)^{T} S ^{-1} (x_i - x_j) \right]^{1/2} \]

相关系数

样本之间的相似度有时用相关系数来表示，相关系数的绝对值越接近\(0\)，表示样本越不相似。

夹角余弦

样本之间的相似度有时用夹角余弦来表示，夹角余弦越接近\(1\)，表示样本越相似。

类或簇

• 硬聚类（hard clustering）：一个样本只能属于一个类
• 软聚类（hard clustering）：一个样本可以属于多个类

本章中只考虑硬聚类方法

约定：用\(n_G\)表示\(G\)中样本的个数，用\(d_{ij}\)表示样本之间的距离，下面列一些类或簇的常见定义。

类或簇 \(1\)

设\(T\)为给定的正数，若集合\(G\)中任意两个样本\(x_i,x_j\),有

\[ d_{ij} \leq T \]

则称\(G\)为一个类或簇

类或簇 \(2\)

设\(T\)为给定的正数，若集合\(G\)中任意两个样本\(x_i\)，存在另一个样本\(x_j\)，使得

\[ d_{ij} \leq T \]

则称\(G\)为一个类或簇

类或簇 \(3\)

设\(T\)为给定的正数，若集合\(G\)中任意两个样本\(x_i\)，\(G\)中的另一个样本\(x_j\)，满足

\[ \frac{1}{n_G - 1} \sum_{x_j \in G} d_{ij} \leq T \]

则称\(G\)为一个类或簇

类或簇 \(4\)

设\(T,V\)为给定的正数，若集合\(G\)中任意两个样本\(x_i,x_j\)，有

\[ \frac{1}{n_G(n_G - 1)} \sum_{x_i \in G} \sum_{x_j \in G} d_{ij} \leq T\]

\[ d_{ij} \leq V \]

则称\(G\)为一个类或簇

第一个定义是最常用的，并且可以推出其他三个。

类的特征常用的有下面三种。

类的均值 \(\overline{x_G}\)，又称为类的中心

\[ \overline{x_G} = \frac{1}{n_G} \sum_{i = 1}^{n_G} x_i \]

类的直径 \(D_G\)，就是类中任意两个样本之间的最大距离

类的样本散布矩阵（scatter matrix）\(A_G\) 与样本协方差矩阵 \(S_G\)

\[ A_G = \sum_{i = 1}^{n_G} (x_i - \overline{x_G})(x_i - \overline{x_G})^T \]

\[ S_G = \frac{1}{n_G - 1} A_G \]

类与类之间的距离

考虑类\(G_p\)与类\(G_q\)之间的距离\(D(p,q)\)，也称为连接（linkage）

• 最短距离或单连接
• 最长距离或完全连接
• 中心距离
• 平均距离

层次聚类

层次聚类假设类别之间存在层次结构，将样本聚到层次化的类上。

大概有两种方法：

• 聚合或自下而上聚类
• 分裂或自上而下聚类

聚合聚类开始将每个样本各自分到一个类，之后将相距最近的两类合并，建立一个新的类。

分裂聚类开始将所有样本分到一个类，之后将已有类中相距最远的样本分到两个新的类。

聚合聚类需要确定下面三个要素

• 距离或相似度
• 合并规则
• 停止条件

k-mean 聚类

\(k\) 均值聚类将样本集合划分为 \(k\) 个子集，构成\(k\)个类，将 \(n\) 个样本分到 \(k\) 个类中，每个样本到其所属类的中心的距离最小。

策略

\(k\) 均值聚类归结为样本集合 \(X\) 的划分，或者从样本到类的函数的选择问题。\(k\) 均值聚类的策略是通过损失函数最小化选取最优的划分或函数 \(C^*\)。

定义样本与其所属类的中心之间的距离的总和为损失函数，即

\[ W(C) = \sum_{l = 1}^{k} \sum_{C(i) = l} \Vert x_i - \bar{x}_l \Vert\]

\(k\) 均值聚类就是求解最优化问题

\[C^* = \arg \max_C W(C)\]

\(n\) 个样本分到 \(k\) 类，所有可能分法的数目是 \(S(n,k)\)，这是指数级的。事实上，\(k\) 均值聚类的最优解求解是 NP-hard 问题，现实中往往用迭代方法求解。

算法

实际上的算法是这样的：首先（随机）选择 \(k\) 个类的中心，将样本逐步指派到与其最近的中心的类中，然后计算新的类中心，迭代计算直到收敛为止。