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$ 维后的数据.

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.

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}$$