聚类的基本概念¶
距离的重要性¶
在聚类算法中，距离的定义是非常重要的。
常用的几种距离度量¶
1. 闵可夫斯基距离（Minkowski Distance）
$$d_{ij} = \left(\sum_{k=1}^{m}|x_{ki}-x_{kj}|^{p}\right)^{\frac{1}{p}}\quad(p\geq 1)$$
- 当 $p=1$ 时，为曼哈顿距离：$d_{ij}=\sum_{k=1}^{m}|x_{ki}-x_{kj}|$
- 当 $p=2$ 时，为欧几里得距离：$d_{ij}=\sqrt{\sum_{k=1}^{m}(x_{ki}-x_{kj})^2}$
2. 马氏距离（Mahalanobis Distance）
$$d_{ij}=\sqrt{(x_i-x_j)^T S^{-1}(x_i-x_j)}$$
其中 $S$ 是样本协方差矩阵
3. 曼哈顿距离（Manhattan Distance）
$$d_{ij}=\sum_{k=1}^{m}|x_{ki}-x_{kj}|$$
4. 相关系数（Correlation Coefficient）
$$r_{ij}=\frac{\sum_{k=1}^{m}(x_{ki}-\bar{x}_i)(x_{kj}-\bar{x}_j)}{\sqrt{\sum_{k=1}^{m}(x_{ki}-\bar{x}_i)^2}\sqrt{\sum_{k=1}^{m}(x_{kj}-\bar{x}_j)^{2}}}$$
其中 $\bar{x}_i=\frac{1}{m}\sum_{k=1}^{m}x_{ki}$，$\bar{x}_j=\frac{1}{m}\sum_{k=1}^{m}x_{kj}$
5. 余弦相似度（Cosine Similarity）
$$s_{ij}=\frac{\sum_{k=1}^{m}x_{ki}x_{kj}}{\sqrt{\sum_{k=1}^{m}x_{ki}^{2}}\sqrt{\sum_{k=1}^{m}x_{kj}^{2}}}$$
类的定义和评价形式¶
类的定义¶
如果类之间的交集为空，则称硬聚类；否则称软聚类。本章主要关注硬聚类。
类的评价形式¶
设 $n$ 为样本数，将集合 $X$ 中任意两个样本 $x_i,x_j\in X$，若 $d_{ij}\in T$，则称 $C$ 为一个类（Cluster）。
类间关系的距离有多种评价方式，类内之间的距离包括：
- 最短距离：$D_{st}=\min_{x_i\in C_p,x_j\in C_q}d_{ij}$
- 最长距离：$D_{lg}=\max_{x_i\in C_p,x_j\in C_q}d_{ij}$
- 平均距离：$D_{av}=\frac{1}{n_p n_q}\sum_{x_i\in C_p}\sum_{x_j\in C_q}d_{ij}$
- 中心距离：$D_{ce}=\|\bar{x}_p-\bar{x}_q\|^2$，其中 $\bar{x}_p$ 和 $\bar{x}_q$ 分别是类 $C_p$ 和 $C_q$ 的中心
层次聚类¶
概念¶
层次聚类是根据样本间的相似性或距离，构建聚类层次结构的方法。
类型¶
层次聚类有凝聚（自下而上）和分裂（自上而下）两种：
- 凝聚聚类：从每个样本作为一个单独的类开始，逐步合并最相似的类，直到满足某个停止条件
- 分裂聚类：从所有样本属于一个类开始，逐步将样本分成更小的类，直到每个样本成为一个独立的类或满足某个停止条件
K均值聚类¶
基于距离的聚类（硬聚类）¶
- 原理：以欧氏距离平方表示样本间距离（相似度）
- 目标：最小化样本与其所属类的中心之间的距离总和（即优化目标）
- 公式：
$$J=\sum_{i=1}^{k}\sum_{x_j\in C_i}\|x_j-m_i\|^{2}$$
其中 $k$ 是类的数量，$x_j$ 是属于类别 $C_i$ 的样本，$m_i$ 是类别 $C_i$ 的中心
迭代算法¶
$n$个样本分到$k$类中的可能性有 $SC(n,k)=\frac{1}{k!}\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}i^n$，是一个组合问题，指数级复杂度，使用迭代算法求解
算法步骤：¶
- 初始化：首先选择$k$个点作为初始聚类中心 $m_1,m_2,\ldots,m_k$
- 分配样本：将每个样本分配到与其最近的聚类中心所对应的类中
- 更新中心：计算每个类的样本均值，作为新的聚类中心
- 重复迭代：重复步骤2和3，直到收敛（聚类中心不再发生变化或变化很小）
目标函数：¶
$$\min_{C_1,C_2,\ldots,C_k}\sum_{i=1}^{k}\sum_{x\in C_i}\|x-m_i\|^{2}$$
时间复杂度¶
K均值算法的时间复杂度是 $O(mnkI)$：
- $m$：样本维度
- $n$：样本数量
- $k$：类的数量
- $I$：迭代次数
初始分类的选择¶
选择初始中心，会得到不同的聚类结果。可以使用层次聚类，在得到上述几个类时，从每个类中选择与中心距离最近的点，作为初始中心。
聚类结果的质量可以用类的平均直径来衡量。一般地，类别越多，平均直径越小，但类别个数超过某个值时，平均直径会保持不变。实验时，可以使用二分法查找 $k$。
聚类评价指标¶
- 类内差异：$\downarrow$（越小越好）
- 类间差异：$\uparrow$（越大越好）
常用的聚类评价指标还包括：
- 轮廓系数（Silhouette Coefficient）：衡量样本与其自身聚类的相似度与其他聚类的不相似度
- Calinski-Harabasz指数：类间离散度与类内离散度的比率
- Davies-Bouldin指数：类内距离与类间距离的比率
总结¶
通过上述内容，我们了解了聚类分析中常用的距离度量方法及其应用场景，层次聚类的基本概念和类型，以及K均值聚类算法的原理和实现。这些知识对于理解和应用聚类算法至关重要。
注：本文使用Qwen转换自本人的统计学习方法笔记。
