Unsupervised Learning

CS › Machine Learning

1. Distance Measures

目的: 我们通过刻画不同形式的距离度量, 来表征同类样本间的相似性和不同样本间的差异性

1.1. Metric Space

Formally, Metric Space (度量空间) 是一个有序数对 $(X,d)$, 其中 $X$ 是一个集合, $d$ 是定义在 $X$ 上的函数 ($d:X^2\to \mathbb R$). 度量空间满足如下的四条公理:

$$\left\{ \begin{align} &d(\boldsymbol{x}, \boldsymbol{y}) \geq 0\\ &d(\boldsymbol{x}, \boldsymbol{y})=0 \leftrightarrow \boldsymbol{x}=\boldsymbol{y}\\ &d(\boldsymbol{x}, \boldsymbol{y})=d(\boldsymbol{y}, \boldsymbol{x})\\ & d(\boldsymbol{x}, \boldsymbol{z}) \leq d(\boldsymbol{x}, \boldsymbol{y})+d(\boldsymbol{y}, \mathbf{z})\quad (\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z} \in {X}) \end {align} \right. $$

1.2. Common Metric Functions

  • $\text{Euclidean}$ Distance:
$$d\left(\boldsymbol x_{i},\boldsymbol x_{j}\right)=\sqrt{\left(\boldsymbol x_{i}-\boldsymbol x_{j}\right)^{\mathsf T}\left(\boldsymbol x_{i}-\boldsymbol x_{j}\right)} ==\left\|\boldsymbol x_{i}-\boldsymbol x_{j}\right\|_{2} $$
  • Cosine Similarity:
$$\displaystyle s\left(\boldsymbol x_{i}, \boldsymbol x_{j}\right)=\frac{\boldsymbol x_{i}^{\mathsf T} \boldsymbol x_{j}}{\left\|\boldsymbol x_{i}\right\|\left\|\boldsymbol x_{j}\right\|} \\ $$
  • $\text{Manhattan}$ Distance:
$$d\left(\boldsymbol x_{i}, \boldsymbol x_{j}\right)=\left\|\boldsymbol x_{i}-\boldsymbol x_{j}\right\|_{1} $$
  • $\text{Chebyshev}$ Distance:
$$d\left(\boldsymbol x_{i}, \boldsymbol x_{j}\right)=\left\|\boldsymbol x_{i}-\boldsymbol x_{j}\right\|_{\infty} $$
  • $\text{Mahalanobis}$ Distance:
$$d\left(\boldsymbol x_{i}, \boldsymbol x_{j}\right)=\sqrt{\left(\boldsymbol x_{i}-\boldsymbol x_{j}\right)^{\mathsf T} M\left(\boldsymbol x_{i}-\boldsymbol x_{j}\right)} $$

其中, 欧式距离, 曼哈顿距离和车比雪夫距离都可以算是特殊的 $\text{Mincowski}$ 距离:

$$d\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left(\sum_{u=1}^{n}\left|x_{i u}-x_{j u}\right|^{p}\right)^{\frac{1}{p}} $$

2. Clustering Criteria

聚类有了模式的相似性度量/距离度量, 还需要一种基于数值的聚类准则, 才能将相似的样本分在同一类, 相异的
样本分在不同的类. 判別聚类结果好坏的一般标准:

  • 类内距离小, 类间距离大
  • 或者, 簇内相似度 (intra-cluster sinilarity)高, 簇间相似低 (inter-cluster similarity)

需要一个能对聚类过程或聚类结果的优劣进行评估的准则函数. 如果聚类准则函数选择得好, 聚类质量就会高.

  • 试探方法: 凭直观感觉或经验，针对实际问题定义一种距离度量的阈值, 然后按最近邻规则指定某些样本属于某一个聚类类别. 例如对欧氏距离, 它反映了样本间的近邻性, 但将一个样本分到不同类别中的哪一个时, 还必须规定一个距离度量的阈值作为聚类的判别准则.
  • 聚类准则函数方法: 由于聚类是将样本进行分类以使类别之间的分离性尽可能大，因此聚类准则应是反映类别间相似性或分离性的函数; 每个类別都是由一系列样本组成的, 因此一般来说类别(sample sets) 的可分离性和样本 (samples) 的可分离性是直接相关的; 可以定义聚类准则函数为样本集 $\{\boldsymbol x\}$ 和类别 $\{S_j\mid j=1,2,\ldots,c\}$ 的函数, 从而使聚类分析转化为寻找准则函数极值的最优化问题.

但是值得注意的是, 聚类的好坏不存在绝对标准, “The goodness of clustering depends on the opinion of the user”

3. Clustering Methods

3.1. Exploration-based Method

基于试探的聚类搜索算法

是一种基于贪心策略的聚类算法, 它通过不断试探和调整聚类中心来实现聚类.

该算法首先随机选择一些数据点作为初始聚类中心, 然后将所有数据点分配到这些聚类中心中最近的一个中心. 接着, 该算法会对每个聚类中心进行试探, 即在该聚类中心的周围随机选择一些点作为备选聚类中心, 并将该聚类中心替换成备选聚类中心. 如果替换后聚类效果变得更好, 则保留该替换, 否则还原聚类中心。

该算法重复以上步骤，直到聚类效果不再提高或者达到最大迭代次数为止。最终，该算法会输出聚类中心和每个数据点所属的聚类标签。

基于试探的聚类搜索算法的优点是能够避免局部最优解，并且对于初始聚类中心的选择不敏感。缺点是算法需要进行大量的随机试探，因此效率较低，同时在处理大规模数据时，算法的性能可能会受到影响。

3.2. Systematic Methods

2.3. Dynamic Methods

4. Clustering Evaluation

聚类结果的评估 (验证) 与聚类本身一样困难。 流行的方法包括:

  • “内部”评估，其中聚类被总结为一个单一的质量分数
  • “外部”评估，其中聚类与现有的“基准真相(ground truth)”分类进行比较
  • 由人类专家进行“手动”评估，
  • “间接”通过评估聚类在其预期应用中的效用来进行评估。

内部评估措施存在一个问题，即它们代表的功能本身可以被视为聚类目标。 例如，可以通过 Silhouette 系数对数据集进行聚类； 除了没有已知的有效算法之外。 通过使用这种内部衡量指标进行评估，人们更愿意比较优化问题的相似性, 而不一定是聚类的有用程度.

外部评估也有类似的问题：如果我们有这样的“ground truth”标签，那么我们就不需要聚类了； 而在实际应用中我们通常没有这样的标签。 另一方面，标签仅反映了数据集的一种可能分区，这并不意味着不存在不同的甚至更好的聚类。

因此，这两种方法都不能最终判断聚类的实际质量，但这需要人工评估，这是非常主观的。 尽管如此，这样的统计数据在识别不良聚类方面可能非常有用， 但不应忽视主观的人为评估。

4.1. 内部评估指标

1. $\small \text{Silhouette Coefficient}$

2. $\small \text{Calinski-Harabaz Index}$

3. $\small \text{Davies-Bouldin Index}$

4.2. 外部评估指标

聚类分析有如下常见的评估指标, 用来衡量聚类算法的优与劣。

1. Purity

在聚类结果的评估标准中，一种最简单最直观的方法就是计算它的聚类纯度 ($\text{Purity}$). 聚类分析的聚类纯度 $P$ 有如下的定义:

$$P( \Omega ,C):= \frac {1}{N} \sum_k \max_j | \omega _ {k} \cap c_ {j} | $$

其中:

  • $N$ 表示样本的总数
  • $\Omega=\{\omega_1, \omega_2, ..., \omega_K\}$ 表示聚类后的簇的集合, $\omega_k$ 表示第 $k$ 个簇, $K$ 表示聚类后的簇的总数
  • $C=\{c_1, c_2, ..., c_J\}$ 表示正确的类别, $c_j$ 表示第 $j$ 个类别中的真实的样本, $J$ 表示真实样本的总数

更优雅地可以写成这样:

$$P( \Omega ,C):= \frac {1}{N} \sum_{\omega \in \Omega} \max_{c\in C} | \omega \cap c | $$

不难发现, 最好的情况是 $P=1$, 最差的情况是 $P=0$. 越大表示效果越好.

2. Rand Index & $\small \text F \mbox-value$

注意到, 任取两个样本点, 得到的结果总是只有四种情况, 即:

  • $TP$: 表示两个同类样本点在同一个簇中的情况数量
  • $FP$: 表示两个非同类样本点在同一个簇中的情况数量
  • $TN$: 表示两个非同类样本点分别在两个簇中的情况数量
  • $FN$: 表示两个同类样本点分别在两个簇中的情况数量

兰德指数 ($\text{Rand Index}$) 有如下的定义:

$$\begin{align} \text{RI} &:=\sum\limits_{\omega\in \Omega, c\in C} \frac{|\omega\cap c|}{C_n^2} =\frac{TP + TN}{TP + FP + FN + TN}\\ F_{\beta} &:=(1+\beta^2)\frac{\text{Precision}\times \text{Recall}}{\beta^2\times \text{Precision} + \text{Recall}} \end{align} $$
$$\begin{align} \text{Precision} &:=\frac {TP}{TP + FP}\\ \text{Recall} &:=\frac{TP}{TP+FN}\\ \end{align} $$

3. Adjusted Rand Index

调整兰德系数 ($\small \text{Adjusted Rand Index}$) 是兰德系数的一个改进版本，因为对于随机划分的聚类, $\text{RI}$ 无法保证接近于 $0$ 。假设 $X$ 表示聚类算法认为的结果, $Y$ 表示我们认为正确标签标记后的结果. 根据聚类得到的结果和真实标签, 我们有如下的列联表 (contingency table):

其中, $X=\{X_1, X_2, ..., X_r\}$ 表示聚类得到的 $r$ 个簇的集合, $Y=\{Y_1, Y_2, ..., Y_s\}$ 表示据正确标签对聚类结果修正后的集合, $n_{ij}=|X_i\cap Y_j|$. 在这样的基础上, $\text{ARI}$ 的定义如下:

$$\text{ARI} :=\frac{\text{RI}-\mathbb E\{\text {RI}\}}{\max (\text{RI})-\mathbb E\{\text{RI}\}} =\frac{\sum\limits_i\sum\limits_jC_{n_{ij}}^2 - (\sum\limits_iC_{a_i}^2)(\sum\limits_jC_{b_j}^2)/ C_n^2}{\frac1 2 (\sum\limits_iC_{a_i}^2 + \sum\limits_jC_{b_j}^2) - (\sum\limits_iC_{a_i}^2)(\sum\limits_jC_{b_j}^2)/ C_n^2} $$

其中,

$$\begin {align} a_i &=\sum_{Y_j\in Y} |X_i\cap Y_j|=\sum_{j=1}^{s}n_{ij}\\ b_j &=\sum_{X_i\in X} |X_i\cap Y_j|=\sum_{j=1}^{s}n_{ij}\\ \end{align} $$

根据平凡的初等代数推导, 可以得到 $\text{ARI}$ 的范围是 $[-1, 1]$, 同时发现对于充分大的样本, 考虑中心极限定理, $\text{ARI}$ 可以接近于 $0$ . $\text{ARI}<0$ 表示聚类的结果比随机选择的结果还要差. 只有当 $\text{ARI}>0$ 时, 聚类才开始发挥作用.

可以得到 $\text{ARI}$ 的等价表达式如下:

$$\text{ARI} := \frac{2·(TP·TN-FP·FN)}{(TP+FN)·(FN+TN)+(TP+FP)·(FP+TN)} $$

如果是高中的时候, 我高低得露两手, 但是现在大二了算不出来了

4. Normalized Mutual Information

$\text{NMI}$ ($\text{Normalized Mutual Information}$) 即归一化互信息. 对于聚类后的簇的集合 $\Omega$ 和正确的集合 $C$, $\text{NMI}$ 有定义如下:

$$\text{NMI}(\Omega, C):=\frac{2· I(\Omega;C)}{H(\Omega)+H(C)} $$

其中, $I$ 表示互信息(Mutual Information), $H$ 为熵 (详细的定义可以查看 第十一章 信息与熵 ). 注意这里的均值并不规定, 也可以为几何均值或任意幂均值. 更具体地说 (其中概率的替换则是由概率的极大似然估计推导而来):

$$\begin{align} I(\Omega; C):&=\sum_{\omega \in \Omega}\sum_{c\in C}p(\omega\cap c) \log\frac{p(\omega\cap c)}{p(\omega)p(c)}\\ &=\sum_{\omega \in \Omega}\sum_{c\in C}\frac {|\omega\cap c|}N \log\frac{N·|\omega\cap c|}{|\omega| ·|c|}\\ H(\Omega):&=-\sum_{\omega\in\Omega}p(\omega)\log p(\omega)\\ &=-\sum_{\omega\in\Omega}\frac {|\omega|} N \log {\frac {|\omega|} N }\\ \end{align} $$

其中,

  • $p(\omega)$ 表示样本属于聚类簇 $\omega$ 的概率
  • $p(c)$ 表示样本属于类别 $c$ 的概率
  • $p(\omega\cap c)$ 表示样本同时属于聚类簇 $\omega$ 和类别 $c$ 的概率

直观地,互信息还可以写成这样的形式: $I(\Omega; C)=H(\Omega)-H(\Omega|C)$.

实际上, $\text{NMI}$ 是对互信息的一些优化. 由互信息的定义不难发现, 当 $\Omega$ 和 $C$ 独立时, 两者的互信息为 $0$, 当 $\Omega$ 完整地复现了 $C$ 时, 互信息取得了最大值, 为 $1$ . 但是当 $|\Omega|=N$ 时, $\text{MI}$ 也能取到最大值, 这是非常不好的, 即它并不对簇数目较大的聚类结果进行惩罚, 因此也不能在其他条件一样的情况下, 对簇数目越小越好的这种期望进行形式化. $\text{NMI}$ 则可以解决上述问题,因为熵会随着簇的数目的增长而增大。当 $|\Omega|=N$ 时, $H(\Omega)$ 会达到其最大值 $\log N$ , 此时就能保证 $\text{NMI}$ 的值较低.

用一些分析的手段可以证明, $\text{NMI}\in [0,1 ]$.

5. Adjusted Mutual Information

$\text{AMI}$ ($\text{Adjusted Mutual Information}$) 即调整互信息. 对于聚类后的簇的集合 $\Omega$ 和正确的集合 $C$, $\text{AMI}$ 有定义如下:

$$\text{AMI}(\Omega, C):=\frac{I(\Omega;C)-\mathbb E \{I(\Omega; C)\}}{(H(\Omega)+H(C))/2 - \mathbb E \{I(\Omega; C)\}} $$

同样, 这里的均值也不规定, 也可以为几何均值或任意幂均值. 值得一提的是, 互信息的期望的计算方法如下:

仍然考虑这样的列联表

$$ \mathbb E \{I(X; Y)\}=\sum_{i=1}^r\sum_{j=1}^s\sum_{k=\max\{1, a_i+b_j-N\}}^{\min\{a_i, b_j\}}\frac k N \log(\frac{N · k}{a_i·b_j})\frac{C_{a_i}^{k}·C_{b_j}^{k}·C_{k}^{a_i+b_j-N}}{C_{N}^{a_i}·C_N^{b_j}·C_{a_i+b_j}^{N}}·C_{a_i+b_j}^{a_i} $$

可喜可贺, 上式为笔者自己推导得出