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

降维（Dimensionality Reduction）

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

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

SVD 示例

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

压缩/降低尺寸

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

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

矩阵的秩

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

$$A=\left[\begin{array}{ccc}1& 2& 1\\ -1& -3& 1\\ 3& 5& 0\end{array}\right]Rank(A)=2$$

秩是可以降维

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

降维的目的

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

降维的描述

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

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

SVD

奇异值的值必然为正

SVD 的分类

标准 SVD（无失真）	近似 SVD

SVD 的介绍

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

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

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

降维方法汇总

特征值与特征向量

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

$$|A-\lambda I|=0⟺\left|\begin{array}{cccc}{a}_{11}& a_{12}& ...& a_{1n}\\ a_{21}& a_{22}& ...& a_{2n}\\ .& .& ...& .\\ a_{n1}& a_{n2}& ...& a_{nn}\end{array}\right|=0$$

降维方法

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

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

$$A_{[m\ast n]}=U_{[m\ast r]}\ast {\mathrm{\Sigma }}_{[r\ast r]}(V_{[n\ast r]{)}^T}$$

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

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

SVD 图示

奇异值求解

$$\begin{array}{}\text{(1-1)}& A{A}^T=U\mathrm{\Sigma }{V}^{T}V{\mathrm{\Sigma }}^T{U}^T=U\mathrm{\Sigma }{\mathrm{\Sigma }}^T{U}^T\end{array}$$$$\begin{array}{}\text{(1-2)}& A^{T}A=V\mathrm{\Sigma }{U}^{T}U\mathrm{\Sigma }{V}^T=V{\mathrm{\Sigma }}^T\mathrm{\Sigma }{V}^T\end{array}$$

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

1. 我们利用上面的（1-1）式来进行特征值分解，得到的特征矩阵就是 U
2. 通过上面的（1-2）式来进行特征值分解，得到的特征矩阵就是 V
3. 对 $\mathrm{\Sigma }{\mathrm{\Sigma }}^T$ 或者 ${\mathrm{\Sigma }}^T\mathrm{\Sigma }$ 中的特征值开方，可以获得所有的奇异值

SVD 计算示例

$$A=\left[\begin{array}{cc}0& 1\\ 1& 1\\ 1& 0\end{array}\right]A^T=\left[\begin{array}{ccc}0& 1& 1\\ 1& 1& 0\end{array}\right]$$

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

矩阵名	矩阵值	特征值	特征矩阵
$U$	$U=A\ast A^T=\left[\begin{array}{ccc}1& 1& 0\\ 1& 2& 0\\ 0& 1& 1\end{array}\right]$	${\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$	$\left[\begin{array}{ccc}\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{array}\right]$
$V$	$V=A^T\ast A=(\begin{array}{cc}2& 1\\ 1& 2\end{array})$	${\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$	$\left[\begin{array}{cc}\frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right]$

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

SVD 的性质

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

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

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

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

SVD 的向量理解

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

最小化 reconstruction errors

SVD 目标：最小化 reconstruction errors

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

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

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

SVD 向量理解例子：Users to Movies

SVD - 最低秩近似

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

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

引理

1. $||M|{|}_F=\sum _i(q_{ii}{)}^2$ 当 M = P Q R 是 M 的 SVD 的时候
2. $U\mathrm{\Sigma }{V}^T-US{V}^T=U(\mathrm{\Sigma }-S)V^T$

引理的证明

$$\begin{array}{l}\parallel M\parallel =\sum _i\sum _j{\left(m_{ij}\right)}^2=\sum _i\sum _j{\left(\sum _k\sum _l{p}_{ik}{q}_{kl}{r}_{lj}\right)}^2\\ \parallel M\parallel =\sum _i\sum _j\sum _k\sum _l\sum _n\sum _m{p}_{ik}{q}_{kl}{r}_{lj}{p}_{in}{q}_{nm}{r}_{mj}\end{array}$$

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

$$\begin{array}{l}A=U\mathrm{\Sigma }{V}^T,B=US{V}^T\\ \\ \underset{B,rank(B)=K}{min}||A-B|{|}_F\\ =min||\mathrm{\Sigma }-S|{|}_F=\underset{s_i}{min}\sum _{i=1}^r({\delta }_i-s_i{)}^2\end{array}$$

• 我们想要的是最小化 $\underset{s_i}{min}\sum _{i=1}^r({\theta }_i-s_i{)}^2$
• 解决方案就是令 $s_i={\delta }_i(i=1...k)$ 并且其他 $s_i=0$

$$\begin{array}{l}\underset{s_i}{min}\sum _{i=1}^k({\delta }_i-s_i{)}^2+\sum _{i=k+1}^r{\delta }^2\\ =\sum _{i=k+1}^r{\delta }^2\end{array}$$

定理的说明

为什么将 ${\delta }_i$ 设置为 0 是正确的做法？

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

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

SVD 算法的复杂度

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

SVD 和特征分解的关系

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

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

1. A 是对称的
2. $U,V,X$ 都是正交矩阵
3. $\mathrm{\Lambda },\mathrm{\Sigma }$ 都是对角的

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

案例：如何查询

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

1. user q：$q_{concept}=qV$
2. user d：$d_{concept}=dV$

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

SVD 的效果

CUR 分解

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

选择行和列的方式

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

CUR 对列（行）进行取样

以列为例，行也是相似的

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

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

算法过程：

1. 对于 $\mathrm{\forall }x\in [1,n]，P(x)=\frac{\sum _{i}A(i,x{)}^2}{\sum _{i,j}A(i,j{)}^2}$
2. 对于 $\mathrm{\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\ast \frac{\sum _{i}A(i,k{)}^2}{\sum _{i,j}A(i,j{)}^2}}}$

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

计算 U

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

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

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

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

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

1. 非零奇异值的倒数：${\mathrm{\Sigma }}_{ii}^{+}=1/{\mathrm{\Sigma }}_{ii}$
2. $W^{+}$ 是伪逆

为什么伪逆是有效的

$$\begin{array}{c}W=X\mathrm{\Sigma }Y\\ W^{-1}=X^{-1}\ast {\mathrm{\Sigma }}^{-1}\ast Y^{-1}\\ \because X^{-1}=X^T,Y^{-1}=Y^T\\ {\mathrm{\Sigma }}^{-1}=\frac{1}{{\mathrm{\Sigma }}_{ii}}\end{array}$$

• X、Y 正交矩阵，$\mathrm{\Sigma }$ 是对角矩阵
• 因此，如果 W 是非奇异矩阵，伪逆矩阵是真的逆矩阵

CUR 是可以被证明是 SVD 的一个很好近似

CUR 的优点和缺点

优点

1. 很好计算：由于基向量是实际的列和行
2. 稀疏矩阵：由于基向量是实际的列和行

缺点

1. 重复的列和行：大量的列将被多次采样

如何避免重复

1. 方案一：直接抛弃
2. 方法二：用重复项的平方根缩放（乘）列/行

SVD 和 CUR

简单的实验

DBLP bibliographic data

1. Author-to-conference 的大稀疏矩阵
2. $A_{ij}$：作者 i 在会议 j 上发表的论文数量
3. 428k 个作者（列），3659 会议（行）
4. 非常稀疏

DBLP 的结果

线性假设

SVD 只能用于线性投影：低维线性投影，保持欧式距离

非线性方法：Isomap

1. 数据位于一个低维的非线性曲线
2. 使用距离度量对应的形状