聚类

聚类（Clustering） 是一种无监督学习方法，相比于分类、回归等监督学习算法，聚类的特点是不需要预先定义类别标签。聚类的目标是将数据集中的对象分成若干组（簇），使得同一组内的对象相似度较高，而不同组之间的对象相似度较低。其中有三种典型聚类方法：原型聚类、密度聚类、层次聚类。

一、距离计算

在做距离的计算时，判断样本的有序、无序属性是非常重要的。有序属性是指属性值之间存在自然顺序或等级关系，但它们之间的间隔不一定相等。而无序属性是指属性值之间没有自然顺序关系，只是不同的类别或名称。

1. 有序距离属性

给定两个 $d$ 维向量 $x = (x\_1, x\_2, ..., x\_d)$ 和 $y = (y\_1, y\_2, ..., y\_d)$，最常用的是闵可夫斯基距离：

$$D(x, y) = \left( \sum_{i=1}^{d} |x_i - y_i|^p \right)^{1/p}$$

其中：

• $p$ 是一个正数，称为阶数（order）
• 不同的 $p$ 值代表不同的距离度量方式

$p$ 值	名称	距离公式	特点说明
$p = 1$	曼哈顿距离	$\sum_{i=1}^{d}|x_i-y_i|$
$p = 2$	欧氏距离	$\sqrt{ \sum_{i=1}^{d} |x_i - y_i|^2 }$	最常用的“直线距离”

不同的聚类算法或任务场景会选择不同的$p$ 值。一般情况下：

• K-Means 默认为 $p = 2$（欧氏距离）
• K-Medoids 可使用 $p = 1$​（曼哈顿距离）
• DBSCAN 可选任意 $p$ 值，自由度较高（尤其是高维空间中）

2. 无序距离属性

VDM（Value Difference Metric） ：

$$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$$

其中，$m_{u,a}$ 表示在属性 $u$ 上取值为 $a$ 的样本数，$m_{u,a,i}$ 表示在第 $i$ 个样本簇中再属性 $u$ 上取值为 $a$ 的样本数，$k$ 为样本簇数，则属性 $u$ 在两个离散值 $a$、$b$ 之间的 VDM 距离如上式。

3. 混合属性

将闵可夫斯基距离和 VDM 结合即可处理混合属性，假设有 $n_c$ 个有序属性、$n - n_c$ 个无序属性，则：

$$MinkovDM_p(x_i, x_j) = \left( \left( \sum_{u=1}^{n_c} |x_{iu} - x_{ju}|^p \right) + \sum_{u=n_c+1}^{n} VDM_p(x_{iu}, x_{ju}) \right)^{\frac{1}{p}}$$

二、原型聚类

原型聚类即“基于原型的聚类”，它假设聚类结构能通过一组原型刻画。我将以 K-Means 为例，进行说明。

K-means核心思想：

将数据划分为 $K$ 个簇，每个簇有一个中心点（原型），使得簇内数据点到中心的距离最小。它采用了贪心策略，通过迭代优化来近似求解。

数学目标（优化函数）：

目标是最小化簇内平方误差之和（Within-cluster sum of squares，WCSS）：

$$\text{minimize} \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2_2$$

其中：

• $x\_i$ 是第 $i$ 个数据点
• $C\_k$ 是第 $k$ 个簇
• $\mu_k$ 是第 $k$ 个簇的质心（均值）

算法步骤：

1. 初始化：随机选择 $K$​ 个中心点（$\mu_1, ..., \mu_K$）

2. 分配：把每个数据点分配到最近的中心点（使用欧氏距离）：

   $$C_i = \{x_j : \|x_j - \mu_i\|^2_2 \leq \|x_j - \mu_l\|^2_2, \forall l\}$$

3. 更新：重新计算每个簇的中心点为当前簇内点的平均值：

   $$\mu_i = \frac{1}{|C_i|} \sum_{x_j \in C_i} x_j$$

4. 不断重复第 2-3 步直到收敛（中心不再变化或达到迭代次数）

特点：

• 聚类数 $K$ 需手动设定
• 对球状、等方差、均匀密度分布的数据效果好
• 对初始值敏感，容易陷入局部最优
• 不擅长处理非凸簇或含噪声数据

三、密度聚类

密度聚类又被称为“基于密度的聚类”，它假设聚类结构能通过样本分布的紧密程度确认。我将以 DBSCAN进行说明。

DBSCAN核心思想：

根据数据点的密度连通性定义簇：簇是点的高密度区域，簇与簇之间被低密度区域隔开。

两个重要参数：

• $\epsilon$（epsilon）：邻域半径，定义一个点的“邻居”范围：

$$N_\varepsilon(x) = \{ y \in D \mid \text{dist}(x, y) \leq \varepsilon \}$$

• $MinPts$：最小邻居数，一个点的 $\epsilon$ 邻域内至少有 MinPts 个点，才被认为是“核心点”

定义：

• 核心点（Core Point)：若点 $x$ 的邻域中至少有 $\text{MinPts}$ 个点（包括它自己），即$x$为它的核心点：

$$|N_\varepsilon(x)| \geq \text{MinPts}$$

• 密度可达（Density-Reachable）：从某点出发，可以通过一系列核心点“跳过去”的点
• 噪声点（Noise）：既不是核心点，也不是任何核心点的密度可达点

算法步骤：

1. 对每个点计算 $\epsilon$ 邻域
2. 如果该点是核心点，从它开始扩展，找到所有密度可达的点组成一个簇
3. 重复这个过程直到所有核心点都被访问
4. 未被归入任何簇的点为噪声

特点：

• 不需要提前设定聚类数
• 能发现任意形状的簇
• 可识别噪声
• 对参数敏感，$\epsilon$ 和 $MinPts$ 的选取影响结果显著

四、层次聚类

层次聚类试图在不同层次上对数据集进行划分，从而形成树形的聚类结构。数据集可以采用“自底向上”或者“自顶向下”的分拆策略。我将以 AGNES为例进行说明。

AGNES核心思想：

AGNES 是一种层次聚类算法，属于自底向上的方式。它的全称是：AGglomerative NESting

它从每个样本点开始，各自为一个簇，然后逐步将最近的两个簇合并，直到满足终止条件（如簇的数量达到设定值）。

簇间距离定义

AGNES 聚类中，关键是如何计算两个簇之间的距离。常见的有四种方法（称为“链接准则”）：

1. 最短距离（Single Linkage）

$$\text{dist}(C_i, C_j) = \min_{x \in C_i, y \in C_j} \text{dist}(x, y)$$

只看两簇中最近的两点之间的距离，容易形成“链式结构”。

2. 最长距离（Complete Linkage）

$$\text{dist}(C_i, C_j) = \max_{x \in C_i, y \in C_j} \text{dist}(x, y)$$

只看两簇中最远的两点，会导致簇尽量紧凑。

3. 平均距离（Average Linkage）

$$\text{dist}(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{x \in C_i} \sum_{y \in C_j} \text{dist}(x, y)$$

计算簇间所有点对的平均距离，适中。

4. 重心距离（Centroid Linkage）

$$\text{dist}(C_i, C_j) = \left\| \mu_i - \mu_j \right\|$$

其中 $\mu\_i$ 是簇 $C\_i$​ 的质心（平均向量）。这种方法可能在某些距离度量下不满足“距离递增性”。

算法步骤：

1. 初始化：
   将每个样本看作一个独立的簇，即初始时有 $n$个簇，每个簇中只有一个样本点。

2. 计算初始簇间距离：
   对任意两个簇，计算它们之间的距离。选择一种簇间距离计算方法（例如：最小距离、最大距离、平均距离或质心距离）。

3. 寻找最近簇对：
   在当前的所有簇对中，找到距离最近的一对簇 $C_i$ 和 $C_j$​。

4. 合并最近簇对：
   将 $C_i$ 和 $C_j$ 合并成一个新的簇 $C_{ij}$。

5. 更新距离矩阵：
   根据所选的簇间距离计算方式，更新新簇 $C_{ij}$ 与其他所有簇之间的距离。

6. 重复步骤 3 到 5：
   持续合并最近的两个簇，直到满足终止条件：

   • 达到预设的聚类个数 $k$；
   • 或所有样本合并为一个簇为止（构建完整的树状结构）。

特点

• 不需要提前指定簇的数量（可以通过树图选择）

• 适用于层次结构强的聚类任务

• 计算复杂度高：$O(n^2 log n)$​（主要是距离更新）

• 对噪声和离群点敏感

• 不适合大规模数据（可以用 BIRCH 或近似法改进）

总结比较

方法	是否需指定簇数	能否识别非凸簇	是否抗噪声	适合场景
原型聚类	是	否	否	球形、均匀分布
密度聚类	否	是	是	任意形状、有噪声数据
层次聚类	否（后期裁剪）	是（某些情况）	否	小规模、高解释性