ML: Dimensionality Reduction

---

相关机器学习概念： 降维(dimensionality reduction) 主成分分析(principle component analysis)

---

1. Motivation

数据降维的目的：

数据压缩(Data Compression) 数据压缩减小了数据规模，因此占用更少的计算机内存，给算法提速。可视化(Visualization) 将数据的维度降到二维或三维后可画图表示，使其更加直观。 \quad

2. Principal Component Analysis

2.1 PCA Algorithm

主成分分析是最流行的降维算法，它可以将高维的数据通过线性变换投影到低维空间。其目标是在最小化原有数据的信息损失的前提下，找到最能代表原始特征的更低维度的新特征。 具体来说，如果要将n维特征降低到k维，我们需要找到k个向量$u^{(1)},u^{(2)},...,u^{(k)}$来对原有特征进行投影，并最小化投影误差(projection error).

运行PCA算法前首先需要数据预处理: feature scaling/mean normalization 对训练集$x^{(1)},x^{(2)},...,x^{(m)}$， $${\mu }_j=\frac{1}{m}\sum _{i=1}^m{x}_j^{(i)}$$， $$x_j^{(i)}=\frac{x_j^{(i)}-{\mu }_j}{s_j}$$

PCA算法分为三步： 1、计算协方差矩阵 $$\Sigma =\frac{1}{m}\sum _{i=1}^m{x}^{(i)}(x^{(i)}{)}^T$$

$\Sigma$是一个nxn矩阵。在Matlab中可写作：

Sigma = (1/m) * X' * X; % compute the covariance matrix

2、计算特征向量

[U,S,V] = svd(Sigma); % compute the projected directions

svd()是Matlab的内建函数，它全称奇异值分解 (sigular value decomposition)，是一种正交矩阵分解法。在输出的三个矩阵U,S,V中，我们需要用到的是U。它是一个nxn的矩阵，每一列是一个主成分。如果我们需要提取k个主成分，就选取U的前k列。

3、选取U矩阵的前k列并计算z $$z^{(i)}=U_{reduce}^T{x}^{(i)}$$

Ureduce = U(:,1:k); % take the first k directions Z = X * Ureduce; % compute the projected data points

z矩阵就是降维之后的数据，它的维度是mxk \quad

2.2 Reconstruction

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

压缩复原只能得到原始数据的近似值。

2.3 Choosing k (Number of Principal Components)

平均平方映射误差(average squared projection error): $$\frac{1}{m}\sum _{i=1}^m\Vert x^{(i)}-x_{approx}^{(i)}{\Vert }^2$$

数据总变差(total variation in the data): $$\frac{1}{m}\sum _{i=1}^m\Vert x^{(i)}{\Vert }^2$$

选择满足下式的最小的k，作为主成分个数： $$\frac{\frac{1}{m}{\sum }_{i=1}^m\Vert x^{(i)}-x_{approx}^{(i)}{\Vert }^2}{\frac{1}{m}{\sum }_{i=1}^m\Vert x^{(i)}{\Vert }^2}\le 0.01$$

不等式右边的数字也可以为0.05, 0.1等。当其为0.01时，该式可被解释为，k个主成分使得99%的差异性得到了保留。

在Matlab中，可以利用svd(Sigma)计算得到的S矩阵来实现k的选择。当需要保留99%的差异性时，k需要满足$$\frac{{\sum }_{i=1}^k{S}_{ii}}{{\sum }_{i=1}^m{S}_{ii}}\ge 0.99$$