---
sidebar_position: 2
tags: [AI, ML, Unsupervised, Clustering, PCA, GAN, VAE]
---

# Unsupervised Learning

## Clustering

### Distance

1. 非负性:
   $\text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) \geqslant 0$
2. 同一性:
   $\text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) = 0$ 当且仅当 $\boldsymbol{x}_i = \boldsymbol{x}_j$
3. 对称性:
   $\text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) = \text{dist}(\boldsymbol{x}_j, \boldsymbol{x}_i)$
4. 直递性:
   $\text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) \leqslant \text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_k) + \text{dist}(\boldsymbol{x}_k, \boldsymbol{x}_j)$

$$
\text{dist}_{\text{mk}} (\boldsymbol{x}_i, \boldsymbol{x}_j) = \left( \sum\limits_{u=1}^{n} |x_{iu} - x_{ju}|^p \right)^{\frac{1}{p}}
$$

$$
\text{VDM}_p(a, b) = \sum\limits_{i=1}^{k} \left| \frac{m_{u, a, i}}{m_{u, a}} - \frac{m_{u, b, i}}{m_{u, b}} \right|^p
$$

其中, 明可夫斯基距离常用于离散有序/连续距离度量,
数值差异度量 (Value Difference Metric) 常用于离散无序距离度量.

### K-Means

最小化数据点到其所属簇中心的距离平方和 (即组内误差平方和 `WCSS`):

1. 初始化: 随机选择 $k$ 个质心 (初始聚类中心)
2. 分配 (Assignment): 分配数据点给距离最近的质心所在的簇 $d_{ji} = ||\boldsymbol{x}_j - \mu_i||_2$
3. 更新 (Update): 计算各簇的数据点的均值, 设为新的质心
4. 重复: 交替执行第 2 步和第 3 步, 直到收敛

### `DBSCAN`

密度聚类 (Density-Based Clustering) 基于样本分布紧密程度来确定聚类结构.
通过考察样本之间的可连接性, 将具有足够高密度的区域划分为簇:

1. $\epsilon$-邻域 ($\epsilon$-Neighborhood):
   距离不超过 $\epsilon$ 的样本集合
2. 核心对象 (Core Object):
   $\epsilon$-邻域内至少包含 $\text{MinPts}$ 个样本
3. 密度直达 (Directly Density-Reachable):
   位于核心对象 $x_i$ 的 $\epsilon$-邻域内, $x_i \to x_j$
4. 密度可达 (Density-Reachable):
   $x_i \to p_1 \to p_2 \to \dots \to p_n \to x_j$
5. 密度相连 (Density-Connected):
   如上序列任意两点密度相连

## Principal Component Analysis

主成分分析 (`PCA`) 是一种常用的数据降维方法,
将 $m$ 个 $n$ 维向量降为 $k$ 维, 保证低维子空间对样本具有**最大的可分性**.
其目标是选择 $k$ 个单位 (模为 $1$) 正交基, 使得原始数据变换到这组基上后,
各字段两两间协方差为 $0$ (各字段完全独立), 各字段的**方差最大** (每维特征分散),
即在正交的约束下, 取最大的 $k$ 个方差:

$$
\begin{equation}
  C=\frac{1}{m}XX^T=\frac{1}{m}\begin{bmatrix}
    \sum\limits_{i=1}^m(x_i^1)^2&\sum\limits_{i=1}^m{x_i^1x_i^2}&\dots&\sum\limits_{i=1}^m{x_i^1x_i^n}\\
    \sum\limits_{i=1}^m{x_i^2x_i^1}&\sum\limits_{i=1}^m(x_i^2)^2&\dots&\sum\limits_{i=1}^m{x_i^2x_i^n}\\
    \vdots&\vdots&\ddots&\vdots\\
    \sum\limits_{i=1}^m{x_i^nx_i^1}&\sum\limits_{i=1}^m{x_i^nx_i^2}&\dots&\sum\limits_{i=1}^m(x_i^n)^2
  \end{bmatrix}
\end{equation}
$$

协方差矩阵 $C$ 是一个对称矩阵, 其对角线分别为各字段的方差,
其第 $i$ 行 $j$ 列和第 $j$ 行 $i$ 列元素相同, 表示 $i$ 和 $j$ 两个字段的协方差.
将协方差矩阵对角化, 得到基于矩阵运算的 `PCA` 算法如下:

- 将原始数据按列组成 $n$ 行 $m$ 列矩阵 $X$.
- 将 $X$ 的每一行 (代表一个属性字段) 进行零均值化, 即减去这一行的均值,
  使得 $\bar{x}=0$, 方便方差与协方差的计算.
- 求出协方差矩阵 $C=\frac{1}{m}XX^T$ 的特征值及对应的特征向量.
- 将特征向量按对应特征值大小从上到下按行排列成矩阵, 取前 $k$ 行组成矩阵 $P$.
- $Y=PX$ 即为降维到 $k$ 维后的数据.

:::tip[Normalization]

$$
x'_i=\frac{x_i-\mu}{\sigma}
$$

:::

## Variational Auto-Encoders

变分自编码器 (`VAE`) 是一种生成模型, 通过学习数据的潜在分布来生成新的数据:

$$
\begin{split}
  Z&=\text{Encoder}(X) \\
  X'&=\text{Decoder}(Z) \\
  L&=\text{Min Loss}(X',X)
\end{split}
$$

变分自动编码器学习的是隐变量 (特征) $Z$ 的概率分布, $z\sim N(0, I), x|z\sim N\big(\mu(z), \sigma(z)\big)$,
通过深度网络来学习 $q(z|x)$ 的参数, 一步步优化 $q$ 使其与 $p(z|x)$ 十分相似, 便可用它来对复杂的分布进行近似的推理:

- Feature disentangle:
  voice conversion.
- Discrete representation:
  unsupervised classification, unsupervised summarization.
- Anomaly detection:
  face detection, fraud detection, disease detection, network intrusion detection.
- Compression and decompression.
- Generator.

![Variational Auto-Encoders](./figures/variational-auto-encoders.webp 'Variational Auto-Encoders')

## Generative Adversarial Networks

生成对抗网络 (GANs) 由两个网络组成: 生成器 (Generator) 和判别器 (Discriminator).
生成器的目标是生成尽可能逼真的数据, 判别器的目标是尽可能准确地区分真实数据和生成数据.
两个网络相互对抗, 生成器生成数据 (decoder in `VAE`), 判别器判断数据真伪 ($1/0$ classification neural network),
生成器根据判别器的判断结果调整生成数据的策略, 不断提升生成数据的逼真程度.

$$
\begin{split}
  G^*&=\arg\min_G\max_DV(G,D)\\
  D^*&=\arg\max_DV(D,G)
\end{split}
$$

![Generative Adversarial Networks](./figures/generative-adversarial-networks.png 'Generative Adversarial Networks')
