《机器学习》笔记（第四部分：聚类、降维与度量学习）

9 聚类

9.1 聚类任务

  假设有一个无标记样本集 $\{\boldsymbol x^{(i)}\}_{i=1}^m$, 每个样本 $\{\boldsymbol x^{(i)} = x^{(i)}_u\}_{u=1}^n$ 是一个 $n$ 维向量. 聚类算法将样本集分为不重不漏的 $k$ 个簇 (cluster) $\mathcal C = \{C_\ell\}_{\ell=1}^k$. 假设 $\lambda _i$ 是样本 $i$ 所属类别 (即簇标记, cluster label) $\boldsymbol x^{(i)} \in C_{\lambda _i}$.

9.2 性能度量

  从直观上, 我们希望聚类结果的簇内相似度高, 且簇间相似度低.

外部指标 基于一个已知参考簇划分的性能度量指标称为外部指标. 若聚类器给出一个簇划分 $\mathcal C = \{C_k\}_k$, 而已知一个参考的簇划分 $\mathcal C^* = \{C_\ell^*\}_\ell$, 则考虑所有 $m(m-1)/2$ 个样本对 $\{(\boldsymbol x^{(i)}, \boldsymbol x^{(j)})\}_{i<j}$, 假设它们的簇标记是 $\lambda _i, \lambda _j$ 与 $\lambda _i^*, \lambda _j^*$, 则有混淆矩阵

	$\lambda _i = \lambda _j$	$\lambda _i \neq \lambda _j$
$\lambda _i^* = \lambda _j^*$	$a$	$b$
$\lambda _i^* \neq \lambda _j^*$	$c$	$d$

常见的外部指标包括:

$$\mathrm{JC} = \frac{a}{a + b + c}, \quad \mathrm{FMI} = \sqrt{\frac{a}{a + b} \cdot \frac{a}{a + c}}, \quad \mathrm{RI} = \frac{2(a + d)}{m(m - 1)}$$

这些指标结果均在 $[0, 1]$ 区间, 值越大越好.

内部指标 若无参考簇, 则可以定义

• 簇 $C_\ell$ 内样本平均距离: $\mathop{\mathrm{avg}}C_\ell = \frac{2}{|C_\ell|(|C_\ell| - 1)} \sum _{\boldsymbol x^{(i)}, \boldsymbol x^{(j)} \in C_\ell} d(\boldsymbol x^{(i)}, \boldsymbol x^{(j)})$;
• 簇 $C_\ell$ 内样本最远距离: $\mathop{\mathrm{diam}}C_\ell = \max _{\boldsymbol x^{(i)}, \boldsymbol x^{(j)} \in C_\ell} d(\boldsymbol x^{(i)}, \boldsymbol x^{(j)})$;
• 簇 $C_i, C_j$ 最近样本间的距离 $d_{\mathrm{min}}(C_i, C_j) = \min _{\boldsymbol x^{(i)} \in C_i, \boldsymbol x^{(j)} \in C_j} d(\boldsymbol x^{(i)}, \boldsymbol x^{(j)})$;
• 簇 $C_i, C_j$ 重心距离 $d_{\mathrm{min}}(C_i, C_j) = d(\boldsymbol \mu ^{(i)}, \boldsymbol \mu ^{(j)})$, 其中 $\boldsymbol \mu ^{(i)}$ 是重心.

常见的内部指标包括:

$$\mathrm{DBI} = \frac 1k \sum _i \max _{j \neq i} \left( \frac{\mathop{\mathrm{avg}}C_i + \mathop{\mathrm{avg}}C_j}{d_{\mathrm{cen}(\boldsymbol \mu ^{(i)}, \boldsymbol \mu ^{(j)})}} \right), \quad \mathrm{DI} = \frac{\min _{i, j} d_{\mathrm{min}}(C_i, C_j)}{\max _\ell \mathop{\mathrm{diam}}C_\ell}$$

DBI 的值越小越好, DI 的值越大越好.

9.3 距离计算

  最常用的是 Minkovski 距离:

$$d_{\mathrm{mk}}(\boldsymbol x^{(i)}, \boldsymbol x^{(j)}) = \sqrt[p]{\sum _u |x^{(i)}_u - x^{(j)}_u|^p} =: ||\boldsymbol x^{(i)} - \boldsymbol x^{(j)}||_p$$

取 $p=2$ 即得 Euclid 距离 $d_{\mathrm{ed}}$, 取 $p=1$ 即得 Manhattan 距离 $d_{\mathrm{man}}$. Minkovski 距离也可以加权:

$$d_{\mathrm{mk}}'(\boldsymbol x^{(i)}, \boldsymbol x^{(j)}) = \sqrt[p]{\sum _u w_u |x^{(i)}_u - x^{(j)}_u|^p}$$

  对于分类变量, 可使用 VDM (Value Difference Metric). 对于属性 $u$ 上的两个离散值 $a, b$, 定义其距离为

$$\mathrm{VDM}^p(a, b) = \sum _i \left| \frac{\#\{\boldsymbol x^* \in C_i: x^*_u = a\}}{\#\{\boldsymbol x^*: x^*_u = a\}} - \frac{\#\{\boldsymbol x^* \in C_i: x^*_u = b\}}{\#\{\boldsymbol x^*: x^*_u = b\}} \right| ^p$$

  Minkowski 距离和 VDM 距离可以混合使用.

$$\mathrm{MinkovDM}_p(\boldsymbol x^{(i)}, \boldsymbol x^{(j)}) = \sqrt[p]{ \sum _{\text{$u$ numerical}} |\boldsymbol x^{(i)}_u - \boldsymbol x^{(j)}_u| ^p + \sum _{\text{$u$ categorical}} \mathrm{VDM}^p(\boldsymbol x^{(i)}_u, \boldsymbol x^{(j)}_u) }$$

9.4 原型聚类

9.4.1 $k$-均值算法

  给定目标类别数 $k$, $k$-均值 ($k$-means) 算法尝试最小化平方误差

$$E = \sum _i \sum _{\boldsymbol x \in C_i} ||\boldsymbol x - \boldsymbol \mu _i||_2^2 = \min$$

这是一个 NP 难问题. $k$-均值算法使用贪心策略解决:

• 输入: 样本 $D = \{\boldsymbol x^{(i)}\}_{i=1}^m$, 聚类簇数 $k$.
• 过程:
  1. 从 $D$ 中随机选取 $k$ 个样本作为初始均值 $\{\boldsymbol \mu _1, \dots, \boldsymbol \mu _k\}$
  2. repeat
  3.   定义簇 $C_i \gets \varnothing, \forall i$
  4.   计算每一个样本离哪个均值向量最近, 将其加入对应的簇
  5.   更新每一个均值向量为对应簇的重心
  6. until 所有均值向量均未更新
• 输出: 簇划分 $\mathcal C = \{C_i\}_{i=1}^k$

9.4.2 学习向量量化 LVQ

  学习向量量化 (LVQ, Learning Vector Quantization) 用于学习带有类别标记的样本 $\{(\boldsymbol x^{(j)}, y^{(j)})\}_{j=1}^m$. 假设 $\mathcal Y = \{1, \dots, q\}$ 是类别标记, 则 LVQ 算法希望习得一组原型向量 $\{\boldsymbol p_i\}_{i=1}^q$ 作为聚类中心, 使得样本空间根据“该点距离哪一个原型向量最近”分为 $q$ 个区域 (称为 Voronoi 剖分, Voronoi tessellation).

• 输入: $D = \{\boldsymbol x^{(j)}, y^{(j)}\}_{j=1}^m$, 类别数 $q$, 学习率 $\eta \in (0, 1)$
• 过程:
  1. 初始化一组原型向量 $\{\boldsymbol p_i\}_{i=1}^q$, 可随机选取该类别的一个样本作为原型
  2. repeat
  3.   随机选择一个样本 $(\boldsymbol x^{(j)}, y^{(j)})$
  4.   找出与 $\boldsymbol x^{(j)}$ 最近的原型向量 $\boldsymbol p_{i^*}$
  5.   if $y^{(j)} = i^*$ then $\delta \gets +1$ else $\delta \gets -1$
  6.    $\boldsymbol p_{i^*} \gets \boldsymbol p_{i^*} + \delta \eta (\boldsymbol x^{(j)} - \boldsymbol p_{i^*})$
  7. until 满足停止条件, 例如原型向量更新很小
• 输出: 原型向量 $\{\boldsymbol p_i\}_{i=1}^q$

9.4.3 Gauss 混合聚类

  Gauss 混合聚类用概率模型表达聚类原型. 给定均值 $\boldsymbol \mu_i$ 和方差 $\Sigma_i$, 多元 Gauss 分布 $X_i \sim N(\boldsymbol \mu_i, \Sigma_i)$ 的密度是

$$\varphi(\boldsymbol x_i \mid \boldsymbol \mu_i, \Sigma_i) = \frac{1}{(2\pi)^{n/2} \sqrt{\Sigma_i}} \exp -\frac 12(\boldsymbol x_i - \boldsymbol \mu_i)^T \Sigma_i ^{-1} (\boldsymbol x_i - \boldsymbol \mu_i)$$

如果有一系列均值、方差和混合参数 (mixture coefficient) $\boldsymbol \theta = \{(\boldsymbol \mu _i, \Sigma _i, \alpha _i)\}_{i=1}^k$ 满足 $\sum \alpha _i = 1$, 就可以定义 Gauss 混合分布

$$X \sim \mathrm{Mix}N(\boldsymbol \theta) = \begin{cases} X_1 \sim N(\boldsymbol \mu_1, \Sigma_1), \quad & \text{with probability $\alpha _1$}\\ \cdots \\ X_k \sim N(\boldsymbol \mu_k, \Sigma_k), \quad & \text{with probability $\alpha _k$}\\ \end{cases}$$

它的密度是

$$p(\boldsymbol x \mid \boldsymbol \theta) = \sum _i \alpha _i \varphi(\boldsymbol x \mid \boldsymbol \mu _i, \Sigma _i)$$

Gauss 混合分布的密度函数会很像一个包含若干丘陵的地图, 每一个丘陵代表一个独立的 Gauss 分布. 这些丘陵都是椭圆形, 从侧面看它会是一条钟形曲线. 丘陵的椭圆方向受方差影响, 地理位置受均值影响, 最高点海拔受方差和混合参数影响.

  我们假设样本 $D = \{\boldsymbol x^{(j)}\}_{j=1}^m$ 互相独立地服从 Gauss 混合分布

$$\boldsymbol x^{(j)} \overset{\text{ind}}{\sim} MN(\boldsymbol \theta)$$

此时聚类问题化为了一个一般的参数估计问题, 就可以利用 EM 算法迭代获取参数的数值解了. 另外, 若有一个新样本 $\boldsymbol x$ 我们还要考虑这个样本属于混合分布的具体哪一个分支. 假设样本来自第 $z$ 个分支, 则

$$\Pr(z = i \mid \boldsymbol x) = \frac{\Pr(z = i) \Pr(\boldsymbol x \mid z = i)}{p(\boldsymbol x)} = \frac{\alpha _i \varphi(\boldsymbol x \mid \boldsymbol \mu _i, \Sigma _i)}{\sum _\iota \alpha _\iota \varphi(\boldsymbol x \mid \boldsymbol \mu _\iota, \Sigma _\iota)}$$

然后取那一个概率最大的分支作为预测类标签

$$y = \argmax _{i \in \{1, \dots, k\}} \Pr(z = i \mid \boldsymbol x)$$

9.5 密度聚类

  密度聚类 (density-based clustering) 假设聚类结构能通过样本分布的紧密程度确定. DBSCAN 是一种著名的密度聚类算法. 它定义如下概念:

• $\boldsymbol x$ 的 $\varepsilon$-邻域 (neighborhood): $N_\varepsilon(\boldsymbol x) := \{\boldsymbol x_0: d(\boldsymbol x, \boldsymbol x_0) \leq \varepsilon\}$.
• 核心对象 (core object): 若 $\boldsymbol x$ 的 $\varepsilon$-邻域至少包含 $\mathrm{MinPts}$ 个样本, 则 $\boldsymbol x$ 是一个核心对象.
• 密度直达 (directly density-reachable): 若 $\boldsymbol x'$ 位于 $\boldsymbol x$ 的 $\varepsilon$-邻域中, 且 $\boldsymbol x$ 是核心对象, 则称 $\boldsymbol x$ 密度直达 $\boldsymbol x'$. 密度直达关系通常不满足对称性.
• 密度可达 (density-reachable): 若 $\boldsymbol x_1, \dots, \boldsymbol x_n$ 是一条密度直达链 (即从前往后相邻两项密度直达), 则称 $\boldsymbol x_1$ 密度可达 $\boldsymbol x_n$. 密度可达关系通常不满足对称性.
• 密度相连 (density-connected): 若 $\boldsymbol x$ 密度直达 $\boldsymbol x'$ 和 $\boldsymbol x''$, 则称 $\boldsymbol x', \boldsymbol x''$ 密度相连.

DBSCAN 算法定义一个簇 $C$ 为密度可达和密度相连导出的最大样本集合. $D$ 中不属于任何簇的样本被认为是噪声或异常样本.

• 输入: 样本集 $D = \{\boldsymbol x^{(j)}\}_{j=1}^m$, 邻域参数 $(\varepsilon, \mathrm{MinPts})$
• 过程:
  1. 遍历所有样本, 将所有核心对象加入核心对象集合 $\Omega$
  2. 初始化聚类簇数 $k \gets 0$ 和未访问样本集合 $\Gamma \gets D$
  3. while $\Omega \neq \varnothing$ do
  4.   记录当前未访问样本集合 $\Gamma _0 \gets \Gamma$
  5.   初始化队列 $Q$, 随机选取一个核心对象 $\boldsymbol x_0$ 加入队列
  6.   $\Gamma \gets \Gamma \setminus \{\boldsymbol x_0\}$
  7.   while $Q \neq \varnothing$ do
  8.     取出队列 $Q$ 的首个样本 $\boldsymbol q$
  9.     if $\boldsymbol q$ 是一个核心对象 then
  10.       $\Delta \gets N_\varepsilon(\boldsymbol q) \cap \Gamma$
  11.       将 $\Delta$ 中的样本加入队列 $Q$
  12.       $\Gamma \gets \Gamma \setminus \Delta$
  13.     end if
  14.   end while
  15.   $k \gets k + 1$, 生成聚类簇 $C_k \gets \Gamma _0 \setminus \Gamma$
  16.   $\Omega \gets \Omega \setminus C_k$
  17. end while
• 输出: 簇划分 $\mathcal C = \{C_i\}_{i=1}^k$

9.6 层次聚类

  层次聚类 (hierarchical clustering) 可以形成树形的聚类结构. AGNES 是一种自底而上的聚类算法. 它先将数据集中每一个样本看作一个初始聚类簇, 然后每次找出距离最近的两个聚类簇进行合并. 不断重复, 直到到达预设的聚类簇数. 簇距离可以定义为最小或最大距离

$$d_{\mathrm{min}}(C', C'') := \min _{\boldsymbol x' \in C', \boldsymbol x'' \in C''} d(\boldsymbol x', \boldsymbol x''), \quad d_{\mathrm{max}}(C', C'') := \max _{\boldsymbol x' \in C', \boldsymbol x'' \in C''} d(\boldsymbol x', \boldsymbol x'')$$

或平均距离

$$d_{\mathrm{max}}(C', C'') := \frac{1}{|C'||C''|} \sum _{\boldsymbol x' \in C'} \sum _{\boldsymbol x'' \in C''} d(\boldsymbol x', \boldsymbol x'')$$

10 降维与度量学习

10.1 $k$-近邻学习 $k$-NN

  给定数据集 $\{\boldsymbol x^{(i)}, y^{(i)}\}_{i=1}^m$ 和待预测样本 $\boldsymbol x$. 在 $k$-NN 算法中, 直接收集距离 $\boldsymbol x$ 最近的 $k$ 个样本的标签, 再用平均法等作为 $\boldsymbol x$ 的预测输出.

  下面对 $k$-NN 的性能做简单讨论. 以 $1$-NN 在二分类问题上的性能为例, 令待预测样本 $\boldsymbol x$ 最近的样本点为 $\boldsymbol z$, 令 $f: \mathcal X \to \mathbb B$ 为真实函数, 则泛化误差为

$$\begin{aligned} E & = 1 - \Pr(f(\boldsymbol x) = f(\boldsymbol z) = +1) - \Pr(f(\boldsymbol x) = f(\boldsymbol z) = -1)\\ & \approx 1 - \Pr(f(\boldsymbol x) = +1) ^2 - \Pr(f(\boldsymbol x) = -1) ^2\\ & \leq 1 - \Pr(c^* \mid \boldsymbol x) ^2\\ & = (1 + \Pr(c^* \mid \boldsymbol x))(1 - \Pr(c^* \mid \boldsymbol x))\\ & \leq 2 \times (1 - \Pr(c^* \mid \boldsymbol x)) \end{aligned}$$

其中约等号假设了 $\boldsymbol x$ 和 $\boldsymbol z$ 很近以至于 $f(\boldsymbol x) = f(\boldsymbol z)$. 而

$$c^* = \begin{cases} +1, \quad & \Pr(f(\boldsymbol x) = +1) \geq \Pr(f(\boldsymbol x) = -1)\\ -1, \quad & \text{Otherwise} \end{cases}$$

是 Bayes 最优分类器的结果. 上面不等式显示, 虽然 $1$-NN 二分类器的泛化错误率不会低于 Bayes 最优分类器, 但也不会高于 Bayes 最优分类器的两倍.

10.2 多维缩放 MDS

  高位情形下容易出现样本稀疏, 称为维数灾难 (curse of dimensionality). 多维缩放 (MDS, Multiple Dimensional Scaling) 是一种降维方法, 使得原始空间中样本间距在地位空间中得以保持.

  假设原始空间有 $d$ 维, 希望降到 $d'$ 维. 假设样本集合 $\{\boldsymbol x_i \in \mathbb R^d\}_{i=1}^m$ 降维后的坐标是 $\{\boldsymbol z_i \in \mathbb R^{d'}\}_{i=1}^m$ 并构成矩阵 $Z \in \mathbb R^{d' \times m}$. 不妨令 $Z$ 是中心化的, 即 $\sum \boldsymbol z_i = 0$.

   假设 $m$ 个样本的距离矩阵是 $D = (d_{ij})_m = (|\boldsymbol x_i - \boldsymbol x_j|)_m$, 我们希望降维操作保持距离矩阵不变, 即 $|\boldsymbol z_i - \boldsymbol z_j| = d_{ij}$. 令 $B = Z^TZ = (b_{ij})_m = (\boldsymbol z_i^T \boldsymbol z_j)_m \in \mathbb R^{m \times m}$ 是降维后样本的内积矩阵. 显然它的行和及列和都为零. 可以整理出 $b_{ij}$ 与 $d_{ij}$ 的关系

$$b_{ij} = -\frac 12\left( d_{ij}^2 - \frac 1m \sum _j d_{ij}^2 - \frac 1m \sum _i d_{ij}^2 + \frac 1{m^2} \sum _i \sum _j d_{ij}^2 \right)$$

  则内积矩阵必可以 (正交相似) 对角化 $\lambda = V^T B V$. 考虑只保留前 $d'$ 个特征值 $\lambda ^* \in \mathbb R^{d' \times d'}$ 和特征向量 $V ^* \in \mathbb R^{m \times d'}$, 则 $Z = \sqrt \lambda V ^T \in \mathbb R^{d' \times m}$ 是降维后的样本坐标.

10.3 主成分分析 PCA

  给定一个样本集 $\{\boldsymbol x_i\}_{i=1}^m$ 构成矩阵 $X_{d \times m}$, 不妨假设 $\sum \boldsymbol x_i = \boldsymbol 0$. 主成分分析 (PCA, Principle Component Analysis) 希望找到一个超平面, 这个超平面有以下两种等价的描述方法:

• 最近重构性: 样本点到超平面距离尽可能近;
• 最大可分性: 样本点在超平面上的投影尽可能分开.

  考虑投影变换后的新标准正交基 $\{\boldsymbol w_i\}_{i=1}^d$. 考虑丢弃一些维度, 仅保留前 $d'$ 维, 即前 $d'$ 个新基构成矩阵 $W_{d \times d'}$. 假设新基下样本 $\boldsymbol x_i$ 投影到了 $\boldsymbol z_i$, 则投影后的样本矩阵 $Z_{d' \times m} = W^T X$, $z_{ij} = \boldsymbol w_j^T \boldsymbol x_i$. 基于投影还原的旧基坐标是 $\hat{\boldsymbol x}_i = \sum _{j=1}^{d'} z_{ij} \boldsymbol w_j = \sum _{j=1}^{d'} \boldsymbol w_j^T \boldsymbol x_i \boldsymbol w_j$.

  考虑最近重构性. 优化目标是寻找一个正交矩阵 $W$ 使得

$$\sum _i |\hat{\boldsymbol x}_i - \boldsymbol x_i|^2 = -\mathop{\mathrm{tr}}W^TXX^TW = \min$$

考虑最大可分性. 优化目标是寻找一个正交矩阵 $W$ 使得

$$\mathop{\mathrm{tr}}W^TXX^TW = \max$$

两种解释的优化目标是等价的. 考虑 Lagrange 乘子法,

$$X^TXW = \lambda W$$

于是只需对协方差矩阵进行谱分解, 仅取前 $d'$ 个特征值对应的特征向量构成 $W_{d \times d'}$ 就是 PCA 的解.

  $d'$ 的值可以通过交叉验证确定, 也可以考虑重构阈值

$$\sum _{i \leq d'} \lambda _i \Big/ \sum _{i \leq d} \lambda _i \geq t$$

其中 $t$ 是一个重构阈值, 例如 $t = 95\%$.

10.4 核主成分分析 KPCA

  假设高维空间是由真实 (称为本真, intrinsic) 低维空间中的样本通过一个非线性升维函数 $\varphi: \mathbb R^{d'} to \mathbb R^d$ 得到的. 在一般的线性 PCA 中, 有

$$\left(\sum _i \boldsymbol z_i \boldsymbol z_i^T\right)W = \lambda W \quad \iff \quad W = \sum _i \boldsymbol z_i \underbrace{\frac{\boldsymbol z_i^T W}{\lambda}}_{\boldsymbol \alpha _i} =: \sum _i \boldsymbol z_i \boldsymbol \alpha _i$$

这是因为在线性 PCA 中直接有 $\boldsymbol z_i = W^T \boldsymbol x_i$, 此处 $\varphi: \boldsymbol x_i \mapsto W^T \boldsymbol x_i$. 一般地,

$$\left(\sum _i \varphi(\boldsymbol x_i) \varphi(\boldsymbol x_i)^T\right)W = \lambda W \quad \iff \quad W = \sum _i \varphi(\boldsymbol x_i) \underbrace{\frac{\varphi(\boldsymbol x_i)^T W}{\lambda}}_{\boldsymbol \alpha _i} =: \sum _i \varphi(\boldsymbol x_i) \boldsymbol \alpha _i$$

引入核函数 $\kappa(\boldsymbol x_i, \boldsymbol x_j) = \varphi(\boldsymbol x_i)^T \varphi(\boldsymbol x_j)$, 此时 Lagrange 乘子法即

$$K\alpha = \lambda \alpha, \qquad K = (\kappa(\boldsymbol x_i, \boldsymbol x_j))_{m \times m}$$

问题转化为求 $K$ 的前 $d'$ 个特征值和特征向量. 对于新样本 $\boldsymbol x$, 其投影后的坐标是

$$\boldsymbol z = \sum _i \boldsymbol \alpha _i \kappa(\boldsymbol x_i, \boldsymbol x)$$

10.5 流形学习

  通过非线性升维函数升维后的样本空间虽是高维的, 但样本实际上仅出现在高维空间的一个 $d'$-流形中, 即 $\mathop{\mathrm{Im}} \varphi$. $\mathop{\mathrm{Im}} \varphi$ 作为流形, 在局部上仍有 Euclid 空间的性质.

10.5.1 等度量映射 Isomap

  等度量映射 (Isomap, Isometric Mapping) 将高维空间内的样本距离定义为像集流形上的测地线 (geodesic) 距离. Isomap 定义每个样本与自己的 $k$-近邻之间的距离为 Euclid 距离, 与其它样本的距离通过 Dijkstra 或 Floyd 算法计算得到. Isomap 输出的距离矩阵可以引入 MDS, 从而把高维像集“展平”为低维平面.

  如何将新样本映射到低维空间? 除了训练一个以高维坐标作为输入、低维坐标作为输出的回归学习器之外, 目前没有更好的办法.

  对近邻图的构建有两种做法:

• $k$-近邻: 选择高维下最近的 $k$ 个点作为近邻点;
• $\varepsilon$-近邻: 选择高维下 $\varepsilon$-邻域内的所有点作为近邻点.

近邻范围指定过大会出现“短路”问题, 过小会出现“断路”问题.

10.5.2 局部线性嵌入 LLE

  Isomap 尝试保持样本距离, 而局部线性嵌入 (LLE, Locally Linear Embedding) 尝试保持邻域内样本之间的线性关系. 即假设样本 $\boldsymbol x_i$ 的近邻下标集合是 $Q_i$, 则 LLE 希望

$$\boldsymbol x_i = \sum _{j \in Q_i} w_{ij} \boldsymbol x_j$$

这一线性关系在低维空间中得以保持. 其中不妨 $\sum _{j \in Q_i} w_{ij} = 1$.

  LLE 的优化目标是

$$\sum _i \left| \boldsymbol x_i - \sum _{j \in Q_i} w_{ij} \boldsymbol x_j \right|^2 = \min$$

它的解是

$$w_{ij} = \sum _{k \in Q_i} \frac{1}{(\boldsymbol x_i - \boldsymbol x_j)^T(\boldsymbol x_i - \boldsymbol x_k)} \Big/ \sum _{s \in Q_i} \sum _{t \in Q_i} \frac{1}{(\boldsymbol x_i - \boldsymbol x_s)^T(\boldsymbol x_i - \boldsymbol x_t)}$$

  样本 $\boldsymbol x_i$ 在低维空间下的投影 $\boldsymbol z_i$ 构成的矩阵 $Z$ 的转置 $Z^T$ 可以通过对矩阵 $M = (I - W)^T (I - W)$ 进行谱分解并取前 $d'$ 个特征向量得到.

10.6 度量学习

  降维的主要目的是寻找一个合适的低维空间, 而一个空间对应了一个距离度量 $d(\cdot, \cdot)$. 度量学习试图直接学习这个度量函数. 考虑一般的平方 Euclid 距离:

$$d^2_{\text{ed}}(\boldsymbol x_i, \boldsymbol x_j) = |\boldsymbol x_i - \boldsymbol x_j|^2 = (\boldsymbol x_i - \boldsymbol x_j)^T (\boldsymbol x_i - \boldsymbol x_j)$$

给定权重 $\boldsymbol w \in \mathbb R^d$ 后, 也可以定义加权 Euclid 距离, 此时各轴的尺度不同:

$$d^2_{\text{wed}}(\boldsymbol x_i, \boldsymbol x_j) = (\boldsymbol x_i - \boldsymbol x_j)^T W (\boldsymbol x_i - \boldsymbol x_j), \qquad W = \mathop{\mathrm{diag}} \boldsymbol w$$

甚至给定一个半正定对称矩阵 $M \geq 0$ 后, 可以定义 Mahalanobis 距离, 此时各轴不一定正交:

$$d^2_{\text{mah}}(\boldsymbol x_i, \boldsymbol x_j) = (\boldsymbol x_i - \boldsymbol x_j)^T M (\boldsymbol x_i - \boldsymbol x_j) =: |\boldsymbol x_i - \boldsymbol x_j|^2_{\mathrm M}$$

对于半正定矩阵一定存在正交基 $P$ 使得 $PP^T = M$. 所以 Mahalanobis 距离也可以写成

$$d^2_{\text{mah}}(\boldsymbol x_i, \boldsymbol x_j) = (\boldsymbol x_i - \boldsymbol x_j)^T PP^T (\boldsymbol x_i - \boldsymbol x_j) = d^2_{\text{ed}}(P^T \boldsymbol x_i, P^T \boldsymbol x_j)$$

近邻成分分析 近邻成分分析 (NCA, Neighborhood Component Analysis) 将 $k$-NN 中的简单投票法替换为概率投票法. 在对样本 $\boldsymbol x_i$ 预测时, 另一样本 $\boldsymbol x_j$ 持有的票数为

$$p_{ij} = \frac{\exp - |\boldsymbol x_i - \boldsymbol x_j|^2_{\mathrm M}}{\sum _\iota \exp - |\boldsymbol x_i - \boldsymbol x_\iota|^2_{\mathrm M}}$$

距离越远的样本, 票数以指数级减小. 此时优化目标可以取每一个样本的分类正确率之和

$$\sum _i \sum _j p_{ij} \mathit 1_{y_i = y_j} = \max$$

必连与勿连 如果在模型以外已知某些样本相似、某些样本不相似, 则可定义必连 (must-link) 约束集合 $\mathcal M$ 与勿连 (cannot-link) 约束集合 $\mathcal C$. 其中 $(\boldsymbol x_i, \boldsymbol x_j) \in \mathcal M$ 表示样本相似, $(\boldsymbol x_i, \boldsymbol x_j) \in \mathcal C$ 则表示不相似. 我们希望相似样本距离尽量小, 不相似样本距离尽量大. 比如寻找半正定矩阵 $M \geq 0$ 使得

$$\sum _{(\boldsymbol x_i, \boldsymbol x_j) \in \mathcal M} |\boldsymbol x_i - \boldsymbol x_j|^2_{\mathrm M} - \sum _{(\boldsymbol x_i, \boldsymbol x_j) \in \mathcal C} |\boldsymbol x_i - \boldsymbol x_j|^2_{\mathrm M} = \min$$

  度量学习方法得到了一个半正定对称度量矩阵 $M$, 然后仅需对其进行谱分解, 仅留下特征值最大的 $d'$ 维即可.