聚类问题的基本概念

【簇】

通过聚类得到的类或簇，本质是样本的子集，其有若干种定义方式，下面给出几个常见的定义

1）定义方式一

给定一个正数 $T$，对集合 $C$ 中任意两个样本 $\mathbf{x}_i,\mathbf{x}_j$，记 $d_{ij}$ 为 $\mathbf{x}_i$ 和 $\mathbf{x}_j$ 的距离，若有：

$$d_{ij} \leq T$$

则称 $C$ 为一个簇（Cluster）

2）定义方式二

给定一个正数 $T$，若对集合 $C$ 中任意一个样本 $\mathbf{x}_i$，一定存在 $C$ 中的另一个样本 $\mathbf{x}_j$，满足：

$$d_{ij}\leq T$$

则称 $C$ 为一个簇（Cluster），其中，$d_{ij}$ 为 $\mathbf{x}_i$ 和 $\mathbf{x}_j$ 的距离

3）定义方式三

给定一个正数 $T$，若对集合 $C$ 中任意一个样本 $\mathbf{x}_i$，$C$ 中的另一个样本 $\mathbf{x}_j$ 满足：

$$\frac{1}{|C|-1} \sum_{\mathbf{x}_j\in C} d_{ij}\leq T$$

则称 $C$ 为一个簇（Cluster），其中，$d_{ij}$ 为 $\mathbf{x}_i$ 和 $\mathbf{x}_j$ 的距离

4）定义方式四

给定两个正数 $T,V$，若对集合 $C$ 中任意两个样本 $\mathbf{x}_i,\mathbf{x}_j$，满足：

$$\begin{gather*} \frac{1}{|C|\cdot(|C|-1)} \sum_{\mathbf{x}_i\in C} \sum_{\mathbf{x}_j\in C} d_{ij} \leq T \\ d_{ij}\leq V \end{gather*}$$

则称 $C$ 为一个簇（Cluster），其中，$d_{ij}$ 为 $\mathbf{x}_i$ 和 $\mathbf{x}_j$ 的距离

对于以上四种簇的定义方式，第一种是最常用的，并且可从其推出其他三个定义

此外，关于两个样本 $\mathbf{x}_i$ 和 $\mathbf{x}_j$ 的距离 $d_{ij}$，有多种计算方式，具体采用哪一种根据实际应用情况决定，详见：机器学习中的距离度量

【簇的特征】

簇的均值

簇的均值即簇的中心点，故也称为簇的中心

对于簇 $C$，有：

$$\overline{\mathbf{x}}_C = \frac{1}{|C|} \sum_{i=1}^{|C|} \mathbf{x}_i$$

簇的直径

簇的直径是簇 $C$ 中任意两个样本 $\mathbf{x}_i$ 和 $\mathbf{x}_j$ 间的最大距离，即：

$$\text{diameter}(C) = \max_{\mathbf{x}_i,\mathbf{x}_j} d_{ij}$$

簇的样本平均距离

簇的样本平均距离是簇 $C$ 中样本间的平均距离，即：

$$\text{avg}(C) = \frac{2}{|C|\cdot (|C|-1)} \sum_{\mathbf{x}_i\in C} \sum_{\mathbf{x}_j\in C} d_{ij}$$

簇的样本散布矩阵与样本协方差矩阵

对于簇 $C$，其样本散布矩阵为：

$$A_G = \sum_{i=1}^{|C|} (\mathbf{x}_i-\overline{\mathbf{x}}_C) (\mathbf{x}_i-\overline{\mathbf{x}}_C)^T$$

其中，$\overline{\mathbf{x}}_C$ 为簇 $C$ 的中心

簇 $C$ 的样本协方差矩阵为：

$$\begin{align*} S_G &= \frac{1}{m-1} A_G \\ &= \frac{1}{m-1} \sum_{i=1}^{|C|} (\mathbf{x}_i-\overline{\mathbf{x}}_C) (\mathbf{x}_i-\overline{\mathbf{x}}_C)^T \end{align*}$$

其中，$m$ 为样本的维数

形式上来看，将散布矩阵乘以 $\frac{1}{m-1}$ 就得到了协方差矩阵，两者的作用其实是一样的，它们之间只有一个系数差而已

【簇与簇间的距离】

对于簇 $C_i$ 和簇 $C_j$ 之间的距离 $D(C_i,C_j)$，常被称为连接（Linkage）

最短距离

最短距离也被称为单连接（Single Linkage），是将簇 $C_i$ 的样本和簇 $C_j$ 的样本间的最短距离，作为两个簇的距离

$$D_{\min}(C_i,C_j) = \min \{ d_{ij}| \mathbf{x}_i\in C_i,\mathbf{x}_j\in C_j \}$$

最长距离

最长距离也被称为完全连接（Complete Linkage），是将簇 $C_i$ 的样本和簇 $C_j$ 的样本间的最长距离，作为两个簇的距离

$$D_{\max}(C_i,C_j) = \max \{ d_{ij}| \mathbf{x}_i\in C_i,\mathbf{x}_j\in C_j \}$$

中心距离

中心距离是将簇 $C_i$ 的中心 $\overline{\mathbf{x}}_{C_i}$ 与簇 $C_j$ 的中心 $\overline{\mathbf{x}}_{C_j}$ 的距离作为两个簇的距离

$$D_{\text{cen}}(C_i,C_j) = d_{\overline{\mathbf{x}}_{C_i}\overline{\mathbf{x}}_{C_j}}$$

平均距离

平均距离是将簇 $C_i$ 与簇 $C_j$ 任意两个样本间距离的平均值作为两个簇的距离

$$D_{\text{avg}} = \frac{1}{|C_i|\cdot|C_j|} \sum_{\mathbf{x}_i \in C_i} \sum_{\mathbf{x}_j \in C_j} d_{ij}$$