机器学习VI - 无监督学习

9. 无监督学习

9.1 K-Means 算法

随机选择$K$个中心点(Centroid) $\mu_1, \mu_2, …, \mu_K \in \mathbb{R}^n$

$\begin{aligned} &重复 \{ \\ & for\ \ i=1\ \ to \ \ m \\ & \quad c^{(i)} := x^{(i)}最近的中心点的坐标(1\ to \ K) \\ & for \ \ k=1 \ \ to \ \ K \\ & \quad \mu_k := 分配到k簇的平均值 \\ &\} \end{aligned}$

9.1.1 代价函数

$c^{(i)}$ = $x^{(i)}$目前被分配的簇

$\mu_k$ = 第$k$簇的中心点

$J(c^{(1)}, ..., c^{(m)}, \mu_1, ...,\mu_K) = \frac{1}{m}\sum_{i=1}^{m}||x^{(i)}-\mu_{c^{(i)}}||^2$

9.1.2 选择簇的数量

在模型代价的拐点，选择簇的数量

根据业务需求来选择簇的数量

9.1.3 随机初始化(Random Initialization)

首先需要$K<m$，这样会确保不会有一个簇中没有样本，其次从$x^{(i)}$中随机选择$K$个样本作为初始簇的重点。

另外为了防止模型进入局部最优，我们需要执行50～1000次算法，从中选取最优的结果（最小的模型代价）。

9.2 数据降维 - 主成份分析(Principle Component Analysis)

数据降维的本质是将多个特征放入多项式中，合并为一个特征。而PCA则是以最小化映射误差(Projection Error)为思想，将高纬的数据映射到低纬度。

PCA和线性回归有所区别：PCA是最小化映射误差，而线性回归是最小化误差$(y-y_{predicton})^2$

PCA应用步骤如下：

例如我们想将$m$纬度的数据降到$k$纬

首先将数据标准化，再计算出协方差矩阵(Covariance Matrix)

$\Sigma = \frac{1}{m}\sum_{i=1}^n (x^{(i)})(x^{(i)})^T$

接着通过奇异值分解(Single Value Decomposition)计算出协方差矩阵的特征向量(Eigenvectors)，$U$

$U = \begin{bmatrix} | & | & & | \\ u^{(1)} & u^{(2)} & \dots &u^{(n)} \\ | & | & & | \end{bmatrix} \in \mathbb{R}^{n \times n}$

然后选择矩阵$U$中的前$k$列，转制后乘以$x$，得到降维后的矩阵$Z$

$Z = \begin{bmatrix} | & | & & | \\ u^{(1)} & u^{(2)} & \dots &u^{(k)} \\ | & | & & | \end{bmatrix}^Tx^{(i)}$

9.1.2 选择$k$

在介绍如果选择$k$之前，我们先思考一下降为后的数据该如何回到原来的维度。

假设现在有$x$，我们经过PCA降维之后，得到了$z$，则

$z = U^T_{reduce}x$

其中$x\in\mathbb{R}^{n\times m}$，$U^T_{reduce} \in \mathbb{R}^{k \times n}, z \in \mathbb{R}^{k \times m}$ 而

$x_{approx}^{(i)} = U_{reduce}.z^{(i)}$

则回到了降维前的数据。因为PCA是一种有损失的降维方法，所以其实升维后的数据，仍然是在映射的超平面上。

例如：

降维前的数据

降维又升维后的数据

$k$是满足如下规则的最小值

$\frac{ \frac{1}{m}\sum_{i=1}^{m}||x^{(i)} - x^{(i)}_{projection}||^2 } { \frac{1}{m}\sum_{i=1}^{m}||x^{(i)}||^2 } \leq 1\%$

其中$1\%$是一个可变化的值，比如$5\%,10\%…$，这个值所代表的意义为信息的损失程度。

如果是运用了上边所说的SVD方法，也等同于

$\frac{ \sum_{i=1}^{k}S_{ii} } { \sum_{i=1}^{n}S_{ii} } \geq 99\%$

本文使用 Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 许可协议，转载请注明出处。