• 无监督学习 (unsupervised learning) 的定义：训练样本的标记信息是未知的，通过对训练样本的学习来揭示数据的内在性质及规律，为进一步分析提供基础。
  • 无监督学习的常见任务有：聚类 (clustering)、密度估计 (density estimation)、异常检测 (anomaly detection)。

A 聚类任务

A1 聚类的概念

• 聚类 (clustering) 的定义：将数据及中的样本划分为若干个「通常不相交」的子集，每个子集称为一个「簇 (cluster)」。
• 聚类问题涉及的概念性定义：
  • 样本集与样本：样本集为 $X = \{ \boldsymbol x^{(1)}, \boldsymbol x^{(2)}, \cdots, \boldsymbol x^{(|X|)} \}$，每个样本 $\boldsymbol x^{(j)}$ 是一个 $d$ 维向量（一般用 $i$ 指代维度下标，用 $j$ 指代样本下标）。
  • 簇：求解目标是一共 $K$ 个簇 $C_k$：
    • 一般有不相交性 $C_i \cap C_j = \emptyset \ (i, j \in [1, K], \ i \neq j)$；
    • 一般有完全性 $\bigcup_{k=1}^K C_k = X$。
  • 簇标记：记 $\lambda[j] \ (j \in [1, K] \cap \Z)$ 为样本 $\boldsymbol x^{(j)}$ 对应的簇标记，那么 $\boldsymbol x^{(j)} \in C_{\lambda[j]}$。那么也可以说求解目标是求解出对整个样本集而言的簇标记向量 $\boldsymbol \lambda = [\lambda_1, \lambda_2, \cdots, \lambda_{|X|}]^{\rm T}$。

A2 聚类的性能度量

• 性能度量不仅可以用于评估结果的好坏，也可以作为过程本身的优化目标。一般分为「内部指标」和「外部指标」。
• 内部指标 (internal-index)：不引用其他参考模型或者标记数据，仅从得到的结果本身的分布进行分析。一般是基于如下的原则：
  • 「簇内相似度 (intra-cluster similarity)」越高越好；
  • 「簇间相似度 (inter-cluster similarity)」越低越好。
• 外部指标 (external-index)：通过外部的一个参考模型或者标记数据与结果进行比对。

A2a 聚类的外部指标

几种常见的聚类外部评价指标

i. 基于混淆矩阵的指标

• 如下图所示的例子。

  

• 如果定义三个大袋子是得到的聚类结果（对应簇标记为 $\lambda$），而图标 ○=1，◇=2，×=3 为参考模型结果或标记数据（对应簇标记为 $\pi$），那么发现一共有四种情况：

  1. 如果从同一袋子里取两个样本（$\lambda_i = \lambda_j$）：
     1. 发现是同一图标（$\pi_i = \pi_j$），那是好的；
     2. 如果是不同图标（$\pi_i \neq \pi_j$），那逝不好的。
  2. 如果从不同袋子里取两个样本（$\lambda_i \neq \lambda_j$）：
     1. 发现是同一图标（$\pi_i = \pi_j$），那逝不好的；
     2. 如果是不同图标（$\pi_i \neq \pi_j$），那是好的。

• 上述四种情况的全集，其实涉及了所有的样本无序对 $(\boldsymbol x^{(i)}, \boldsymbol x^{(j)}) \in X \times X$ 且 $i < j$，一共有 $PC = \frac {|X|(|X| - 1)}{2}$ 个无序对（暂称为 Pair Count）。

• 因而说统计一下所有的样本无序对，通过他们的 $\lambda_i, \lambda_j$ 和 $\pi_i, \pi_j$ 关系得到如下四种类别，构成一个混淆矩阵：

  真实＼预测	同簇 $\lambda_i = \lambda_j$	不同簇 $\lambda_i \neq \lambda_j$
  同簇 $\pi_i = \pi_j$	真正例 TP √	假负例 FN
  不同簇 $\pi_i \neq \pi_j$	假正例 FP	真负例 TN √

  • 当然 $TP + FP + FN + TN = PC$。

• 基于上述混淆矩阵，可以导出如下指标：

  • 兰德指标 (Rand Index, RI)，即为这个混淆矩阵的准确率，范围为 $[0, 1]$：

    $$ RI = \frac {TP + TN}{PC} $$

  • 混淆矩阵的 F1-score，范围为 $[0, 1]$：

    $$ P = \frac {TP}{TP+ FP}, \ \ \ R = \frac {TP}{TP+ FN}, \ \ \ F_1 = \frac {2PR}{P + R} $$

  • Jaccard 系数 (Coefficient)，范围为 $[0, 1]$：

    $$ JC = \frac {TP}{TP + FP + FN} $$

  • Fowlkes and Mallows 指标 (FMI)，范围为 $[0, 1]$：

    $$ FMI = \sqrt{P \cdot R} $$

ii. 基于纯度的指标

• 仍然是下例。

  

• 定义三个大袋子是得到的聚类结果（对应簇为 $C_k$，共 $K$ 个），而图标 ○=1，◇=2，×=3 为参考模型结果或标记数据（对应簇为 $B_l$，共 $L$ 个簇）。

• 认为对每个袋子 $C_k$ 而言，其中出现最多的图标为其对应的「正确簇」，正确簇编号记为 $Act[k]$，正确簇就为 $B_{Act[k]}$，有：

  $$ Act[k] = \argmax_{l=1}^L |C_k \cap B_l| $$

• 那么纯度 (purity) 就定义为所有袋子 $C_k$ 中属于其正确簇 $B_{Act[k]}$ 的样本占所有样本 $|X|$ 的比例。

  $$ P = \frac 1{|X|} \sum_{k=1}^K \max_{l=1}^L |C_k \cap B_l| $$

A2b 距离的定义

• 聚类的内部指标依赖于距离的定义。

i. 距离函数的定义

• 要定义内部指标，一般就得定义任意两个样本间的距离函数 ${\rm dist} ( \boldsymbol x, \boldsymbol y )$（注意 $\boldsymbol x , \boldsymbol y \in X$）。
• 距离函数 (distance function) 的基本要求：
  • 非负性：${\rm dist} ( \boldsymbol x, \boldsymbol y ) \ge 0$，当且仅当 $\boldsymbol x= \boldsymbol y$ 时 ${\rm dist} ( \boldsymbol x, \boldsymbol y ) = 0$。
  • 对称性：${\rm dist} ( \boldsymbol x, \boldsymbol y ) = {\rm dist} ( \boldsymbol y, \boldsymbol x )$。
  • 三角不等式（直递性）：${\rm dist} ( \boldsymbol x, \boldsymbol y ) \le {\rm dist} ( \boldsymbol x, \boldsymbol z ) + {\rm dist} ( \boldsymbol z, \boldsymbol y)$。
    • 有的需求唯独不满足三角不等式（比如需要 dist(人, 人马)=2、dist(人马, 马)=2，而 dist(人马, 马)=10），像这样的距离函数被称为「非度量距离 (non-metric distance)」。
    • 非度量距离在涉及复杂语义的应用中常会涉及，如模式识别、图像检索。

ii. 有序属性的距离度量

• 常用的有序属性（连续属性或有序离散属性）距离函数可以纳入闵可夫斯基距离 (Minkowski distance) $\| \boldsymbol x - \boldsymbol y \|_p$ 的范畴：

  • $p=1$ 时为曼哈顿 (Manhattan) 距离 $\| \boldsymbol x - \boldsymbol y \|_1$，或者叫街区距离。
  • $p=2$ 时为欧几里得 (Euclidean) 距离 $\| \boldsymbol x - \boldsymbol y \|_2$。
    • 一般用的是将各个维度分别作标准化后的欧氏距离，称为标准欧氏距离 (Standardized Euclidean Distance)。
  • $p \to \infin$ 时为切比雪夫 (Chebyshev) 距离 $\| \boldsymbol x - \boldsymbol y \|\infin = \max{i=1}^{d} |x_i - y_i|$。
    • 切比雪夫距离的一个很好的例子：国王可以直行、横行、斜行（一步可以走 8 个格之一），问从某格走到某格需要多少步。

• 余弦距离：对于高维属性，闵可夫斯基距离一般是无效的，因为样本之间距离随着维数增加而增加。这时候换用余弦衡量距离可能更好：

  $$ \cos (\boldsymbol x, \boldsymbol y) = \frac {\boldsymbol x^{\rm T} \boldsymbol y}{\| \boldsymbol x \|_2 \| \boldsymbol y \|_2} $$

iii. 无序属性的距离度量

• 一种无序属性的度量方法是 Value Difference Metric (VDM) 距离 [Stanfill and Waltz, 1986]。称对于属性 $u$ 而言的取值集合为 $U = \{ u_1, u_2, \cdots, u_{|U|} \}$，那么称任两个取值 $a=u_i, b=u_j$ 间的 VDM 距离为：

  $$ {\rm VDM}p (a, b) = \sum{k=1}^K \left| \frac {|X_{u=a}\cap C_k|}{|X_{u=a}|} - \frac {|X_{u=b}\cap C_k|}{|X_{u=b}|}\right|^p $$

  • 可见，取值在各个簇 $C_k$ 间的分布差异决定了两个取值的 VDM 距离。

iv. 综合距离和加权距离

• 综合距离：综合考虑 $d_0$ 个有序属性（使用闵可夫斯基距离）和 $d_1$ 个无序属性（使用 VDM 距离）：

  $$ {\rm dist} (\boldsymbol x, \boldsymbol y) = \left( \sum_{u=1}^{d_0} |x_{0, u} - y_{0, u}|^p + \sum_{v=1}^{d_1} {\rm VDM}p (x{1, v}, y_{1, v}) \right)^{\frac 1p} $$

• 维度加权距离：不同属性的重要性不同时，可以给维度赋予权重。通常权重之和为 1.