数据聚类：从单特征到多特征的深入解析

### 数据聚类：从单特征到多特征的深入解析 #### 1. 单特征数据聚类 在单特征数据聚类中，我们首先关注两个函数 $\phi(x)$ 和 $\psi(x)$ 的关系。有如下性质： - $x_0 \in \arg \min_{x\in\mathbb{R}} \phi(x)$ 当且仅当 $x_0 \in \arg\max_{x\in\mathbb{R}} \psi(x)$。 - $\min_{x\in\mathbb{R}} \phi(x) = \kappa - \max_{x\in\mathbb{R}} \psi(x)$，即 $\phi(x_0) = \kappa - \psi(x_0)$。 例如，对于 $\phi(x) = x^2 - 1$ 和 $\psi(x) = -x^2 + 3$，我们可以检查它们是否满足上述性质，并在同一坐标系中绘制它们的图像。 接下来是一个重要定理：存在一个划分 $\mathcal{P}^* \in P(A; k)$ 使得： - $\mathcal{P}^* \in \arg \min_{\mathcal{P}\in P(A;k)} F_{LS}(\mathcal{P}) = \arg\max_{\mathcal{P}\in P(A;k)} G(\mathcal{P})$。 - $\min_{\mathcal{P}\in P(A;k)} F_{LS}(\mathcal{P}) = F_{LS}(\mathcal{P}^*)$ 且 $\max_{\mathcal{P}\in P(A;k)} G(\mathcal{P}) = G(\mathcal{P}^*)$，其中 $G(\mathcal{P}^*) = \sum_{i=1}^{m} (c - a_i)^2 - F_{LS}(\mathcal{P}^*)$。 这意味着为了找到最小二乘（LS）最优划分，我们可以最大化对偶函数 $G$，而不是最小化 $F_{LS}$。LS 最优划分具有簇元素分散度最小，同时簇质心尽可能远离的特点，从而实现最佳的内部紧凑性和簇间分离度。 ##### 1.1 最小绝对偏差原则 设 $\mathcal{P} = \{\pi_1, \ldots, \pi_k\}$ 是集合 $A \subset \mathbb{R}$ 的一个 $k$ - 划分，$\ell_1$ 度量函数 $d_1(x, y) = |x - y|$。簇 $\pi_1, \ldots, \pi_k$ 的中心 $c_1, \ldots, c_k$ 由下式确定： $c_j = \text{med}(\pi_j) \in \text{Med}(\pi_j) = \arg \min_{x\in\mathbb{R}} \sum_{a\in\pi_j} |x - a|$，$j = 1, \ldots, k$。 目标函数定义为： $F_1(\mathcal{P}) = \sum_{j=1}^{k} \sum_{a\in\pi_j} |c_j - a|$。 如果使用练习中的公式（3.20），计算目标函数 $F_1(\mathcal{P})$ 时无需知道簇的中心，从而加快计算过程。 例如，对于集合 $A = \{2, 4, 8, 10, 16\}$，其所有满足特定定义且簇依次排列的 3 - 划分有 6 种，如下表所示： | $\pi_1$ | $\pi_2$ | $\pi_3$ | $c_1$ | $c_2$ | $c_3$ | $F_1(\mathcal{P})$ | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | $\{2\}$ | $\{4\}$ | $\{8,10,16\}$ | 2 | 4 | 10 | 8 | | $\{2\}$ | $\{4,8\}$ | $\{10,16\}$ | 2 | 6 | 13 | 10 | | $\{2\}$ | $\{4,8,10\}$ | $\{16\}$ | 2 | 8 | 16 | 6 | | $\{2,4\}$ | $\{8\}$ | $\{10,16\}$ | 3 | 8 | 13 | 8 | | $\{2,4\}$ | $\{8,10\}$ | $\{16\}$ | 3 | 9 | 16 | 4 | | $\{2,4,8\}$ | $\{10\}$ | $\{16\}$ | 4 | 10 | 16 | 6 | 其中，$\ell_1$ 最优 3 - 划分是 $\mathcal{P}^* = \{\{2, 4\}, \{8, 10\}, \{16\}\}$，因为目标函数 $F_1$ 在该划分下达到最小值。 ##### 1.2 加权数据聚类 对于单特征加权数据，设 $A = \{a_1, \ldots, a_m\} \subset \mathbb{R}$ 是实数数据集，每个数据 $a_i \in A$ 对应一个权重 $w_i > 0$。目标函数变为： $F(\mathcal{P}) = \sum_{j=1}^{k} \sum_{a_i\in\pi_j} w_i d(c_j, a_i)$，其中 $c_j \in \arg \min_{x\in\mathbb{R}} \sum_{a_i\in\pi_j} w_i d(x, a_i)$，$j = 1, \ldots, k$。 当应用 LS 距离函数时，簇 $\pi_j$ 的中心 $c_j$ 是 $\pi_j$ 中数据的加权算术平均值： $c_j = \frac{1}{\kappa_j} \sum_{a_i\in\pi_j} w_i a_i$，$\kappa_j = \sum_{a_i\in\pi_j} w_i$。 当应用 $\ell_1$ 度量函数时，簇 $\pi_j$ 的中心 $c_j$ 是 $\pi_j$ 中数据的加权中位数。 例如，对于集合 $A = \{1, 4, 5, 8, 10, 12, 15\}$，除最后一个数据权重为 3 外，其余数据权重为 1，LS 最优 3 - 划分是 $\mathcal{P}^* = \{\{1, 4, 5\}, \{8, 10, 12\}, \{15\}\}$，质心分别为 $\frac{10}{3}, 10, 15$，目标函数值 $F(\mathcal{P}^*) = \frac{50}{3} \approx 16.667$。 #### 2. 多特征数据聚类 当数据具有两个或多个特征时，设 $A$ 是一个包含 $m \geq 2$ 个元素且具有 $n \geq 2$ 个特征的集合，可将其视为 $\mathbb{R}^n$ 的子集，即 $A = \{a_i = (a_{i1}, \ldots, a_{in}) \in \mathbb{R}^n : i = 1, \ldots, m\}$。我们要将集合 $A$ 按照特定定义划分为 $1 \leq k \leq m$ 个不相交的非空簇。 给定一个距离函数 $d : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}^+$，每个簇 $\pi_j \in \mathcal{P}$ 的中心 $c_j$ 由下式确定： $c_j \in \arg \min_{x\in\mathbb{R}^n} \sum_{a\in\pi_j} d(x, a)$，$j = 1, \ldots, k$。 目标函数定义为： $F(\mathcal{P}) = \sum_{j=1}^{k} \sum_{a\in\pi_j} d(c_j, a)$。 我们通过求解以下全局优化问题（GOP）来寻找最优 $k$ - 划分： $\arg \min_{\mathcal{P}\in P(A;k)} F(\mathcal{P})$。 最优 $k$ - 划分具有簇元素到其中心的 $d$ - 距离之和最小的性质，从而实现簇的最佳内部紧凑性。 ##### 2.1 最小二乘原则 对于 LS 距离函数 $d_{LS}(a, b) = \|a - b\|^2$，簇 $\pi_1, \ldots, \pi_k$ 的中心 $c_1, \ldots, c_k$ 称为质心，由下式得到： $c_j = \arg \min_{x\in\mathbb{R}^n} \sum_{a\in\pi_j} \|x - a\|^2 = \frac{1}{|\pi_j|} \sum_{a\in\pi_j} a = (\frac{1}{|\pi_j|} \sum_{a\in\pi_j} a_1, \ldots, \frac{1}{|\pi_j|} \sum_{a\in\pi_j} a_n)$，$j = 1, \ldots, k$。 目标函数定义为： $F_{LS}(\mathcal{P}) = \sum_{j=1}^{k} \sum_{a\in\pi_j} \|c_j - a\|^2$。 例如，对于集合 $A = \{(1, 1), (3, 1), (3, 2), (2, 2)\}$，其 2 - 划分有 7 种，如下表所示： | $\pi_1$ | $\pi_2$ | $c_1$ | $c_2$ | $F_{LS}(\mathcal{P})$ | $G(\mathcal{P})$ | | ---- | ---- | ---- | ---- | ---- | ---- | | $\{(1, 1)\}$ | $\{(2, 2), (3, 1), (3, 2)\}$ | $(1, 1)$ | $(2.67, 1.67)$ | 1.33 | 2.42 | | $\{(3, 1)\}$ | $\{(1, 1), (2, 2), (3, 2)\}$ | $(3, 1)$ | $(2.00, 1.67)$ | 2.67 | 1.08 | | $\{(3, 2)\}$ | $\{(1, 1), (2, 2), (3, 1)\}$ | $(3, 2)$ | $(2.0, 1.3)$ | 2.67 | 1.08 | | $\{(2, 2)\}$ | $\{(1, 1), (3, 1), (3, 2)\}$ | $(2, 2)$ | $(2.3, 1.3)$ | 3.33 | 0.42 | | $\{(1, 1),