大数据分析-05-数据降维

降维（Dimensionality Reduction）

我们假设数据能够在低维空间被表示

高维数据在低维空间的表示是更加高效的。

SVD 示例

r 表示保留的特征值的数量

压缩/降低尺寸

$10^6$行，$10^3$列，不更新
随机访问一行数据，很少的错误时可以接受的

如下的矩阵其实是个二维矩阵，我们通过缩放 $[1,1,1,0,0]$ 或 $[0,0,0,1,1]$ 可以重建所有的行。

矩阵的秩

什么是矩阵 A 的秩？A 的线性独立列数
例子：

$$
A = \begin{bmatrix}
1 & 2 & 1 \
-1 & -3 & 1 \
3 & 5 & 0 \
\end{bmatrix}\ Rank(A) = 2
$$

秩是可以降维

我们可以通过 $[1,2,1][-2,-3,1]$ 两个向量来重写矩阵 A，A 的新坐标为：$[1,0][0,1][1,-1]$。

降维的目的

数学上是发现数据中的轴
发现隐藏的联系和主题：比如经常一同出现的单词等
移除相似和噪声特征：并不是所有单词都是有用的
数据解释和可视化
更容易处理和存储数据：（找到规律，压缩数据量）

降维的描述

与用两个坐标表示每一个点不同，我们用轴上的坐标表示每一个点（对应红线上点的位置）。

通过这样做，我们会产生一些错误，因为这些点并不完全在直线上（信息损失），需要我们考虑我们是否可以接受这部分信息损失。

SVD

奇异值的值必然为正

SVD 的分类

标准 SVD（无失真）	近似 SVD

SVD 的介绍

变量（维数）较多，增加了分析问题的复杂性。

数据丰富但知识贫乏：实际问题中，变量之间可能存在一定的相关，因此，多变量中可能存在资讯的重叠。

人们自然希望通过克服相关、重叠性，用较少的变量来代替原来多的变量，而这种代替可以反映原来多个变量的大部分资讯，这实际上是一种“降维”的思想。

降维方法汇总

特征值与特征向量

设 $A$ 是 $n$ 阶矩阵，如果数 $\lambda$ 和 n 维非零列向量使关系式$Ax = \lambda x$成立
则称$\lambda$是方阵 A 的特征值，非零向量 x 称为 A 的对应特征值的特征向量。
一般求解方法

$$
|A - \lambda I| = 0 \iff
\begin{vmatrix}
a_{11} & a_{12} & … & a_{1n} \
a_{21} & a_{22} & … & a_{2n} \
. & . & … & . \
a_{n1} & a_{n2} & … & a_{nn} \
\end{vmatrix} = 0
$$

降维方法

PCA（主成分分析，Principal-Component Analysis）
LDA（线性判别分析）
因子分析
SVD（奇异值分解，Singular-Value Decomposition）
CUR 分解

SVD（奇异值分解，Singular-Value Decomposition）

$$
A_{[m * n]} = U_{[m * r]} * \Sigma_{[r * r]} (V_{[n * r])^T}
$$

矩阵符号	矩阵名称	矩阵描述
$A$	输入数据矩阵	m * n 维
$U$	左奇异矩阵	m * r 维，正交矩阵，$UU^T = I$
$\Sigma$	奇异值对角矩阵	r * r 维，r 是矩阵 A 的秩，只有对角线上有值，其他元素均为 0
$V$	右奇异矩阵	n * r 维，正交矩阵，$V^TV = I$

Notes：奇异值分解的信息下降是非常快的，基本上前 100 个奇异值就可以表征大多数的数据。

SVD 图示

奇异值求解

$$
AA^T = U\Sigma V^TV\Sigma^TU^T = U\Sigma\Sigma^TU^T \tag{1-1}
$$

$$
A^TA = V\Sigma U^TU\Sigma V^T = V\Sigma^T\Sigma V^T \tag{1-2}
$$

我们通过简单分析可以知道 $AA^T$ 和 $A^TA$ 是对称矩阵

我们利用上面的（1-1）式来进行特征值分解，得到的特征矩阵就是 U

通过上面的（1-2）式来进行特征值分解，得到的特征矩阵就是 V

对 $\Sigma\Sigma^T$ 或者 $\Sigma^T\Sigma$ 中的特征值开方，可以获得所有的奇异值

SVD 计算示例

$$
A = \begin{bmatrix}
0 & 1 \
1 & 1 \
1 & 0
\end{bmatrix}
A^T = \begin{bmatrix}
0 & 1 & 1 \
1 & 1 & 0
\end{bmatrix}
$$

求解特征值要从大到小排列

矩阵名	矩阵值	特征值	特征矩阵
$U$	$U = A * A^T = \begin{bmatrix} 1 & 1 & 0 \ 1 & 2 & 0 \ 0 & 1 & 1\end{bmatrix}$	$\lambda_1 = 3, u_1 = (\frac{1}{\sqrt{6}},\frac{2}{\sqrt{6}},\frac{1}{\sqrt{6}})^T$ $\lambda_2 = 1, u_2 = (\frac{1}{\sqrt{2}}, 0, -\frac{1}{\sqrt{2}})^T$ $\lambda_3 = 0, u_3 = (\frac{1}{\sqrt{3}}, -\frac{1}{\sqrt{3}}, \frac{1}{\sqrt{3}})^T$	$\begin{bmatrix} \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{3}} \ \frac{2}{\sqrt{6}} & 0 & -\frac{1}{\sqrt{3}} \ \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{3}} \end{bmatrix}$
$V$	$V = A^T*A = (\begin{matrix} 2 & 1 \ 1 & 2\end{matrix})$	$\lambda_1 = 3,v_1 = (\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}) ^ T$ $\lambda_2 = 1,v_2 = (-\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}}) ^ T$	$\begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix}$

求解奇异值为：$\sqrt{3}$ 和 1

SVD 的性质

我们通常可以将一个实数矩阵 A 按照分解为$A = U\Sigma V^T$

$U,\Sigma,V$：唯一
U,V：列正交
1. $U^TU = I,V^TV = I$，I 是单位矩阵
2. 列是正交单位向量
$\Sigma$：对角矩阵：对角值（奇异值）为正，并以降序排列

SVD 的例子的解释（Users to Movies）

U：“User to Concept”相似度矩阵
- 第一列：SciFi-concept
- 第二列：Romance-concept
$\Sigma$：
- 第一对角值：“strength” of the SciFi-concept
- 对角值：“strength” of each concept
V：“movie-to-concept”相似度矩阵

SVD 的向量理解

不使用二维（x, y）来描述一个点,而是使用一个点 z 来描述这个点。
点的位置是在向量 v1 上的
如何选择 v1：最小化 reconstruction errors（我们选择使用欧氏距离）

最小化 reconstruction errors

SVD 目标：最小化 reconstruction errors

$$
\sum\limits_{i = 1}\limits^{N}\sum\limits_{j = 1}\limits^D||x_{ij} - z_{ij}||^2 \to 0
$$

如何被认为是没有了，下降结束了？设置最小的奇异值为 0

得到 SVD 后的近似矩阵（将最小的奇异值设置为 0 和 U、V 中对应的行和列置为 0，重新做乘法得到新的矩阵）

SVD 向量理解例子：Users to Movies

SVD - 最低秩近似

定理：如果 $A = U\Sigma V^T$ 并且 $B = U S V^T$，并且 S 是一个对角 r * r 的矩阵，并且 $s_i = \delta_i(i = 1…k)$，并且其他的 $s_i=0$，那么 B 是 A 的最合适的近似矩阵，并且 $rank(B) = k$

什么是最好?B 在$rank(B) = k$的时候是$\min\limits_B||A-B||_F$的解
$||A-B||F = \sqrt{\sum\limits{ij}(A_{ij} - B_{ij})^2}$

引理

$||M||F = \sum\limits_i(q{ii})^2$ 当 M = P Q R 是 M 的 SVD 的时候
$U\Sigma V^T - USV^T = U(\Sigma - S)V^T$

引理的证明

$$
\begin{array}{l}
|M|=\sum\limits_i\sum\limits_j\left(m_{i j}\right)^{2}=\sum\limits_i \sum\limits_j\left(\sum\limits_k \sum\limits_lp_{i k} q_{kl} r_{lj}\right)^{2} \
|M|=\sum\limits_i\sum\limits_j\sum\limits_k\sum\limits_l \sum\limits_n\sum\limits_m p_{ik} q_{kl} r_{lj} p_{in} q_{nm} r_{mj}
\end{array}
$$

$\sum\limits_ip_{ik}p_{in}$ 是 1，如果 k=n，不然为 0
P 是列正交矩阵，R 是正交矩阵，Q 是对角矩阵

$$
\begin{array}{l}
A = U \Sigma V^T, B = U S V^T \
\
\min\limits_{B, rank(B)=K}||A-B||F \
= \min ||\Sigma - S||F = \min\limits{s_i}\sum\limits{i=1}\limits^r(\delta_i-s_i)^2
\end{array}
$$

我们想要的是最小化 $\min\limits_{s_i}\sum\limits_{i=1}^r(\theta_i-s_i)^2$
解决方案就是令 $s_i = \delta_i(i = 1…k)$ 并且其他 $s_i=0$

$$
\begin{array}{l}
\min\limits_{s_i}\sum\limits_{i=1}\limits^k(\delta_i-s_i)^2 + \sum\limits_{i = k + 1}\limits^r\delta^2 \
= \sum\limits_{i = k + 1}\limits^r\delta^2
\end{array}
$$

定理的说明

为什么将 $\delta_i$ 设置为 0 是正确的做法？

向量 $u_i$ 和 $v_i$ 是单位长度，所以 $\delta_i$ 是用来调整他们的
所以让 $\delta_i$ 成为 0 可以导致更少的损失

我们应该保持多少 $\delta_s$，拇指原则：$\sum\limits_i\delta_i^2$ 的和在 80%-90%，保证信息损失不太多

SVD 算法的复杂度

计算 SVD 的复杂度：$\min(O(nm^2), O(n^2m))$
但是如果我们只想知道奇异值或者前 k 个奇异值，或者矩阵是稀疏矩阵，那么复杂度会大大下降

SVD 和特征分解的关系

SVD 角度：$A = U \Sigma V^T$

特征分解的角度：$A = X \Lambda X^T$

A 是对称的
$U,V,X$ 都是正交矩阵
$\Lambda,\Sigma$ 都是对角的

$$
\begin{array}{l}
AA^T \
= U\Sigma V^T (U\Sigma V^T)^T \
= U\Sigma V^T (V\Sigma^TU^T) \
= U\Sigma\Sigma^TU^T(X \Lambda^2 X^T )\
\
A^TA \
= V(\Sigma^TU^T)(U\Sigma V^T) \
= V\Sigma\Sigma^TV^T(X \Lambda^2 X^T )
\end{array}
$$

案例：如何查询

查找类似这个矩阵的用户：将查询映射到“概念空间”中-怎么做？

user q：$q_{concept} = q V$
user d：$d_{concept} = d V$

观察：被评级为“Alien”，“Serenity”的用户 d 与被评级为“Matrix”的用户 q 相似，尽管 d 和 q 的共同点为零！

SVD 的效果

CUR 分解

目标：将矩阵 A 解释为 C，U，R，使得 $||A - CUR||_F$ 最小

选择行和列的方式

尽管我们是随机的选择行和列，但是我们还是保留了对于重要的行和列的权重
行和列的权重计算：$f=\sum\limits_{i,j}a_{ij}^2$
我们按照概率 $p_i = \sum\limits_{j}\frac{a_{ij}^2}{f}$ 选择行
我们按照概率 $q_j = \sum\limits_{i}\frac{a_{ij}^2}{f}$
归一化处理：将所有的元素都是除以 $\sqrt{rq_j}$（行）、$\sqrt{rp_i}$（列）

CUR 对列（行）进行取样

以列为例，行也是相似的

输入：矩阵 $A \in R^{m * n}$，样例数 c

输出：$C_d \in R^{m * c}$

算法过程：

对于 $\forall x \in [1, n]，P(x) = \frac{\sum\limits_iA(i, x)^2}{\sum\limits_{i,j}A(i,j)^2}$
对于 $\forall i \in [1, c]$，以一列为例
1. 选择 $k \in [1, n]$ 满足分布 $P(x)$
2. 计算 $C_d(:,i) = \frac{A(:,k)}{\sqrt{cP(k)}} = \frac{A(:, k)}{\sqrt{c * \frac{\sum\limits_iA(i, k)^2}{\sum\limits_{i,j}A(i,j)^2}}}$

请注意，这是一种随机算法，同一列可以多次采样

计算 U

U 是一个 $r*r$ 的矩阵，所以是比较小的，并且如果他是高密度、难计算的也是可以的。

首先计算 W，我们让 W 是列 C 和行 R 的交集，并且计算出 W 的 SVD 表示为 $W = X \Sigma Y^T$

然后计算 $\Sigma$ 的 Moore-Penorse inverse（伪逆矩阵）：$\Sigma$

$\Sigma$ 是一个对角矩阵
他的 Moore-Penorse inverse 满足：
1. $\frac{1}{\sigma}$ 如果 $\sigma \neq 0$
2. 0 如果 $\sigma=0$

然后：$U = W^+ = Y(\Sigma^+)^2X^T$

非零奇异值的倒数：$\Sigma_{ii}^{+} = 1/\Sigma_{ii}$
$W^+$ 是伪逆

为什么伪逆是有效的

$$
\begin{matrix}
W = X \Sigma Y \
W^{-1} = X^{-1} * \Sigma^{-1} * Y^{-1} \
\because X^{-1} = X^T, Y^{-1} = Y^T \
\Sigma^{-1} = \frac{1}{\Sigma_{ii}} \
\end{matrix}
$$