描述：本节整理聚类与无监督学习、距离度量、K-Means、无序和混合属性的 VDM 距离，以及原型、密度、层次三类聚类方法。

9.1 聚类基本概念

聚类是无监督学习中研究和应用最广泛的任务之一。
它把数据样本划分为若干个通常互不相交的簇（cluster），使簇内样本较相似、簇间样本较不同。
聚类不需要样本类别标记，算法根据数据本身的结构分组。
聚类既可作为独立的数据探索过程，也可作为分类等监督学习任务的前置步骤。
例如可先把通信软件用户按行为聚成若干群组，再在各群组中建立有监督模型。

源资料作了如下类比：

有监督学习	无监督学习中的对应任务
分类：预测离散类别	聚类：发现离散群组
回归：预测连续值	密度估计：学习连续概率结构

这只是任务形式上的类比；聚类得到的簇没有预先定义的类别语义，不能直接等同于真实标签。

9.2 相似性、簇与距离

判断两个样本是否属于同一簇，需要先定义相似性。
数值空间中常用距离表示不相似程度：距离越小，通常认为越相似。
距离度量 $\operatorname{dist}$ 一般满足四个性质。

非负性：

$$ \operatorname{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j)\geq0. $$

同一性：

$$ \operatorname{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j)=0 \iff \boldsymbol{x}_i=\boldsymbol{x}_j. $$

对称性：

$$ \operatorname{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j)

\operatorname{dist}(\boldsymbol{x}_j,\boldsymbol{x}_i). $$

三角不等式：

$$ \operatorname{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j) \leq \operatorname{dist}(\boldsymbol{x}_i,\boldsymbol{x}_k) + \operatorname{dist}(\boldsymbol{x}_k,\boldsymbol{x}_j). $$

某些任务会使用不满足全部性质的相似度或不相似度，此时严格说不再是数学意义上的距离。

9.3 K-Means

K-Means 是基于原型的无监督聚类方法，使用每个簇的均值向量作为中心。

9.3.1 算法过程

选择 $K$ 个初始中心 $\boldsymbol{\mu}_1,\ldots,\boldsymbol{\mu}_K$；实践中常从样本中选取（如 K-Means++），但数学上初始中心不必强制等于某个样本。
对每个样本，计算到各中心的平方欧氏距离，并分到最近中心对应的簇。
对每个簇重新计算样本均值，作为新中心。
重复分配与更新，直到中心不再改变、簇分配稳定或目标函数变化小于阈值。

典型目标是最小化簇内平方误差：

$$ J

\sum_{k=1}^{K} \sum_{\boldsymbol{x}\in C_k} |\boldsymbol{x}-\boldsymbol{\mu}_k|_2^2. $$

在分配固定时，均值是使簇内平方距离最小的中心：

$$ \boldsymbol{\mu}_k

\frac{1}{|C_k|} \sum_{\boldsymbol{x}\in C_k} \boldsymbol{x}. $$

均值更新与上述平方欧氏距离目标配套；若改用任意距离或不相似度，最优原型通常不再是算术均值，应改用 K-Medoids 或与该距离相匹配的原型更新。

$K$ 值对结果非常敏感，需要结合任务知识或聚类评价选择。
初始化不同可能收敛到不同局部最优解，常需多次随机初始化。
K-Means 关注整个数据集的全局簇结构。

9.4 聚类与 KNN 的区别

对比	K-Means	KNN
学习类型	无监督	有监督
是否需要标记	不需要	需要
关注范围	全局簇结构	待测点局部邻域
$K/k$ 含义	簇的数量	参与预测的邻居数量
输出	簇划分与中心	类别或回归值

两者名称都含 $K$，但参数意义和学习任务完全不同。

9.5 常见数值距离

闵可夫斯基距离为

$$ \operatorname{dist}_{\mathrm{mk}} (\boldsymbol{x}_i,\boldsymbol{x}_j)

\left( \sum_{u=1}^{n} |x_{iu}-x_{ju}|^p \right)^{1/p}, \qquad p\geq1. $$

当 $p=2$ 时是欧氏距离：

$$ \operatorname{dist}_2 (\boldsymbol{x}_i,\boldsymbol{x}_j)

\left( \sum_{u=1}^{n} |x_{iu}-x_{ju}|^2 \right)^{1/2}. $$

当 $p=1$ 时是曼哈顿距离：

$$ \operatorname{dist}_1 (\boldsymbol{x}_i,\boldsymbol{x}_j)

\sum_{u=1}^{n} |x_{iu}-x_{ju}|. $$

不同距离对应不同几何形状和归纳偏好；若特征量纲差异很大，应先标准化，否则大尺度特征会主导距离。

9.6 无序属性与 VDM

对无序属性，数值差没有自然意义，可使用 Value Difference Metric（VDM）。

令：

$m_{u,a}$：属性 $u$ 取值为 $a$ 的样本数。
$m_{u,a,i}$：第 $i$ 类样本中，属性 $u$ 取值为 $a$ 的样本数。
$k$：类别数。

属性 $u$ 上两个离散取值 $a,b$ 的 VDM 为

$$ \operatorname{VDM}_p(a,b)

\sum_{i=1}^{k} \left| \frac{m_{u,a,i}}{m_{u,a}}

\frac{m_{u,b,i}}{m_{u,b}} \right|^p. $$

若 $a,b$ 在各类别中的条件分布相近，VDM 较小。
若二者与类别的关联方式差异很大，VDM 较大。
VDM 使用类别频率，因此严格说适合有类别统计可用的混合属性距离设计；纯无监督场景需要改用其他类别无关的离散相似度或迭代估计。

9.7 混合属性距离

若前 $n_c$ 个属性为连续属性，后面的属性为无序离散属性，可组合闵可夫斯基距离与 VDM：

$$ \operatorname{MinkovDM}_p (\boldsymbol{x}_i,\boldsymbol{x}_j)

\left( \sum_{u=1}^{n_c} |x_{iu}-x_{ju}|^p + \sum_{u=n_c+1}^{n} \operatorname{VDM}p(x{iu},x_{ju}) \right)^{1/p}. $$

连续与离散部分的数值范围可能不同，实践中常需归一化或设置权重。

9.8 聚类方法概述

9.8.1 原型聚类

假设聚类结构可由一组原型刻画。
先初始化原型，再反复分配样本和更新原型。
代表方法包括 K-Means、学习向量量化（LVQ）和高斯混合聚类。

9.8.2 密度聚类

假设簇可通过样本分布的紧密程度确定。
从密度角度考察样本的可连接性，并不断扩展连通区域。
代表方法包括 DBSCAN、OPTICS、DENCLUE。

9.8.3 层次聚类

在不同层次上对数据集进行划分，形成树状聚类结构。
AGNES 采用自底向上的凝聚过程。
DIANA 采用自顶向下的分裂过程。

9.9 聚类质量没有绝对标准

聚类结果的好坏依赖用户目标、距离定义、簇形状假设和评价指标。
同一数据可以按颜色、形状、密度或业务价值形成不同但合理的聚类。
只要更换任务标准，就可能出现让既有算法失效的新数据结构，因此不能脱离用途宣称某种聚类算法绝对最好。
源资料引用的观点是：“The goodness of clustering depends on the opinion of the user.”

9.10 易错点

聚类不是分类：聚类没有预先给出的类别标签，簇编号本身没有固定语义。
K-Means 的 $K$ 是簇数，KNN 的 $k$ 是邻居数。
K-Means 每轮必须先分配样本，再按簇内均值更新中心。
K-Means 只保证目标函数单调不增并收敛到局部最优，不保证得到全局最优。
欧氏距离对量纲敏感，使用前应检查标准化。
VDM 的对象是无序属性取值的类别分布差异，不是把类别编码后直接做欧氏距离。
密度聚类能处理非球形簇；K-Means 更偏好由均值和平方距离描述的近似凸形簇。
聚类质量取决于任务定义，内部指标好不等于业务上有意义。

9.11 本节复盘

聚类是不依赖标签的无监督分组，可独立探索结构，也可作为监督学习的前置过程。
合法距离通常满足非负、同一、对称和三角不等式。
K-Means 反复执行最近中心分配与均值更新，最小化簇内平方误差。
K-Means 的簇数 $K$、初始化和距离尺度都会显著影响结果。
闵可夫斯基距离在 $p=1$ 时为曼哈顿距离，$p=2$ 时为欧氏距离。
无序属性可用 VDM 描述类别条件分布差异，混合属性可组合数值距离与 VDM。
聚类方法可分为原型、密度和层次三类，不存在脱离任务目标的绝对最优算法。

Lecture 9：聚类