LearnLog

ML西瓜书第九章的学习笔记. 内容主要是对一些已有方法的推导介绍, 涉及到大量数学相关的知识.

聚类任务

无监督学习中, 由于没有一个给定的标签信息, 我们只能够以"物以类聚"的原则进行学习.

形式化地, 我们对于样本集

X∈Rm×nX \in R^{m \times n}

我们给出一个划分, 使得它成为k个不相交的簇

∀j,∃λj,xj∈Cλj\forall j, \exists \lambda_j, x_j \in C_{\lambda_j}

性能度量

有多种划分方式:

  1. 簇内相似度 vs 簇间相似度
  2. 外部指标 vs 内部指标

假定已经有了一个参考模型, 给出了一个标记向量 λ∗∈[S]m\lambda * \in [S]^m, 其中划分结果为S个簇;
需要评估的模型的标记向量为 λ∗∈[K]m\lambda * \in [K]^m, 其中划分结果为K个簇

那么, 对于m个样本, 我们考虑它们的样本对 {(xi,xj)∣i<j,xi,xj∈X}\{(x_i, x_j) | i < j, x_i, x_j \in X\}, 其中约有平方个样本对.

接着, 我们将这些样本对分为四类考虑:

  • a=∣SS∣,SS={(xi,xj)∣λi=λj,λi∗=λj∗,i<j}a = |SS|, SS =\{(x_i, x_j) | \lambda_i = \lambda_j, \lambda_i* = \lambda_j*, i < j\}
  • b=∣SD∣,SD={(xi,xj)∣λi=λj,λi∗≠λj∗,i<j}b = |SD|, SD =\{(x_i, x_j) | \lambda_i = \lambda_j, \lambda_i* \neq \lambda_j*, i < j\}
  • c=∣DS∣,DS={(xi,xj)∣λi≠λj,λi∗=λj∗,i<j}c = |DS|, DS =\{(x_i, x_j) | \lambda_i \neq \lambda_j, \lambda_i* = \lambda_j*, i < j\}
  • d=∣DD∣,DD={(xi,xj)∣λi≠λj,λi∗≠λj∗,i<j}d = |DD|, DD =\{(x_i, x_j) | \lambda_i \neq \lambda_j, \lambda_i* \neq \lambda_j*, i < j\}

显然, 我们直观上肯定希望考察的模型"更类似于"给定的标准模型, 即, 我们希望a, d尽可能大, 同时b, c尽可能小.
通过某些公式, 我们可以将 (a,b,c,d)(a, b, c, d)处理为一个实数, 然后根据这个实数的大小来构建序关系, 从而对模型的性能进行评估.

常见的外部指标为

  • Jaccard系数: JC=aa+b+cJC = \frac{a}{a + b + c}
  • FM指数: FMI=aa+baa+cFMI = \sqrt{\frac{a}{a + b}\frac{a}{a+c}}
  • Rand指数: RI=a+dm(m−1)RI = \frac{a + d}{m(m-1)}

同样的, 我们可以根据簇内距离和簇间距离, 考虑一些内部度量指标

  • avg(C)=2∣C∣(∣C∣−1)∑1≤i<j≤∣C∣dist(xi,xj)avg(C) = \frac{2}{|C|(|C| - 1)} \sum_{1 \leq i < j \leq |C|} dist(x_i, x_j)
  • diam(C)=max⁡1≤i<j≤∣C∣dist(xi,xj)diam(C) = \max_{1 \leq i < j \leq |C|} dist(x_i, x_j)
  • dmin(Ci,Cj)=min⁡xi∈Ci,xj∈Cjdist(xi,xj)d_{min}(C_i, C_j) = \min_{x_i\in C_i, x_j\in C_j} dist(x_i, x_j)
  • dcen(Ci,Cj)=dist(μi,μj)d_{cen}(C_i, C_j) = dist(\mu_i, \mu_j)

上面的各种定义都是比较直观的. 它们具备一些数学上的性质, 使得它们能够作为性能指标, 指导我们构建起序的关系.

  • DB指数: 1k∑i=1kmax⁡i≠j(avg(Ci+Cj)dcen(Ci,Cj))\frac{1}{k} \sum_{i=1}^{k}\max{i\neq j}(\frac{avg(C_i + C_j)}{d_{cen}(C_i, C_j)})
  • Dunn指数: min⁡i≠j(dmin⁡(Ci,Cj))max⁡1≤l≤kdiam(Cl)\frac{\min_{i\neq j} (d_{\min} (C_i, C_j))}{\max_{1 \leq l \leq k}diam(C_l)}

其中, DB指数只考虑均值, 要求均值意义下, 最小化"簇内 / 簇间"的最大值;
Dunn指数只考虑最值, 要求使得最小值意义下的簇间距离最大, 同时最大值意义下的簇内距离最小

同样的, 我们也可能在不同的时候考虑均值 / 最值, 从而得到许多不同的性能指标. 这些指标应该根据具体应用场景来具体地选择.

距离计算

在数学上, 我们给出距离度量 / 范数的定义:

类比于之前的定义, 我们为了得到一个实数域上的价值定义, 从原始的, 很复杂高维的簇出发, 先将其转换为范数, 再将其转换为价值:

(x,i)∈X×[K]→范数dist(xi,xj)∈R∣X∣×∣X−1∣/2→价值指数R(x, i) \in X\times [K] \rightarrow^{\text{范数}} dist(x_i, x_j) \in R^{|X| \times |X - 1| / 2} \rightarrow ^{\text{价值指数}} R

当然, 对于外部指标而言, 转换过程也是类似的.

具体而言, 我们一般考虑"闵可夫斯基距离", 或者称为p-范数.

distmk(xi,xj)=(∑k=1n(xi,k−xj,k)p)1/pdist_{mk}(x_i, x_j) = ({\sum_{k=1}^{n}(x_{i,k} - x_{j, k})^p})^{1/p}

其中, p=1p=1时退化为曼哈顿距离, p=2p=2时为欧式距离, p=∞p=\infty时为切比雪夫距离

同时, 我们发现, 闵可夫斯基距离比较适合用于"有序距离"上, 即适用于"属性值本身可以计算"的情况; 对于属性值本身就不可计算的情况, 我们此时显式地比较"属性值是否相等", 并通过这个结果定义其相似性.

具体而言, 对于某个属性下的两个属性取值a, b, 我们显式地将其映射为"类间占比"之类的值, 如 (0.1,0.3,0.6)(0.1, 0.3, 0.6)和 (0.4,0.2,0.4)(0.4, 0.2, 0.4), 然后算这些"占比向量"的p距离.

[!attention]
某种程度上, 这种方法是有偏的. 因为它使用了模型的输出: “分类结果”, 来将样本点映射为占比向量, 然后又用这个占比向量来评估模型.

原型聚类

此类方法中, 我们假定不同类别的样本, 有一个"原型"作为其中心点. 这一类的样本都可以通过这个原型来刻画.

K-mean K均值算法

此时, 算法选择最小化平方误差:

E=∑i=1k∑x∈Ci∥x−μi∥22E = \sum_{i=1}^{k} \sum_{x\in C_i} \|x - \mu_i\|_2^2

  • 此时, 我们只考虑每个簇内部的紧密程度, 最小化类的选取使得簇"最紧"

求解这个最优化问题是NP难的, 因此, 我们采用贪心的策略, 对其进行迭代求解.

  • 对于这个算法而言, 它在某些时刻下无法收敛至最优解. 例如考虑一个长方形, K=2K=2的情况, 将初始点设为其短边上的两点, 算法最终收敛至两长边的中点, 而这不是最优的
  • 但是大部分情况下, 它都表现得不错

Learning Vector Quantization 学习向量量化

在给定初始的类别标记信息[K][K]的前提下, 将样本划分为[Q][Q]类.

采用了胜者为王的策略, 大致工作过程如下:

  1. 初始化向量
  2. 随机选择样本点及其归属向量. 当前归属向量向样本点靠近; 其余归属向量向样本点远离
  3. 重复直至收敛

  • 采用了和SOM类似的"赢家通吃"思想, 可以看做是SOM的监督学习扩展
  • SOM(Self-Organizing Map自组织映射)网络, 将高维输入映射到低维空间. 一种竞争学习型的无监督神经网络.

高斯混合聚类

不采用均值向量作为"代表向量", 而是显式地建模K个高斯模型, 并将整体的样本集视为一个高斯混合分布. 不断地迭代达到最优的系数.

[!todo]
具体的数学推导过程; 后续的相关内容.

backtop