Category Archives: Linear Algebra

SVD Dimension Reduction 奇异值分解 降维

降维的意义:

  1. 找出隐含的相关关系
  2. 去除无意义的特征
  3. 便于理解、可视化、存储

方法一:奇异值分解

可以参见以前的文章
A = USigma V^T

例子:

输入矩阵:

  • A_{[m times n]} 表示m篇文档和n个术语

分解获得:

  1. U_{[mtimes r]}表示m篇文档和r个概念
  2. Sigma_{[rtimes r]}, r的值等于矩阵A的rank
  3. V_{[ntimes r]}表示n个术语和r个概念

沿用之前TF-IDF时候的代码:

矩阵M4times 35的矩阵,表示4篇文章和35个术语

奇异值分解的几个属性:

  1. 实数矩阵A,总是可以进行奇异值分解的
  2. 分解后的U,Sigma ,V都是唯一的
  3. U,V都是列正交的(每一列都是相互垂直的单位向量)
  4. Sigma是一个对角矩阵,对角线上的元素是奇异值,且均为正数,并且从左上往下按照大小排列

测试一下U是否是列正交的

看一下U矩阵的具体内容:

这个矩阵每一行代表一篇文档,每一列代表一个概念。

  • 文档1和概念2,4相关性较高
  • 文档2和概念2,3相关性较高
  • 文档3和概念3相关性较高
  • 文档4和概念1相关性较高

看一下Sigma矩阵:

这个矩阵可以理解为4个概念的强度,揭示的是将数据投影到低维度空间中时,在各个坐标方向数据的方差。

看一下V^T矩阵:

每一行代表一个概念,每一列代表一个术语,每个元素代表的是术语与概念之间的相关关系,是将高位数据进行投影时所依据的坐标系。

验证一下分解的正确性:

奇异值降解SVD提供的是”最佳"低维度坐标系,“最佳”的含义是:将高维度数据投影到该低维度坐标系后损失的信息最少。

这个最佳的坐标系可以通过V^T矩阵获得,记得本例中的V矩阵的含义是:概念与术语之间的关系。

将原本表示“文档-术语"关系的矩阵M投影为"文档-概念",投影方法为:

QQ截图20150309182607

每一行代表一篇文档,每一列代表一个概念。

用SVD进行降维的方法:

  1. 进行SVD分解
  2. 若要降维至k维,用(U矩阵的前k列构成的矩阵)与(Sigma矩阵的前kk列构成的矩阵)进行点积
  3.  如果要将该低维度的数据表现恢复至高维度,则用2中结果与V^T矩阵的前k列所构成的矩阵进行点积

例如,投影到2维:

每一行代表一篇文章,每一列代表降至2维后,每篇文章在各个维度方向的投影。

将有损压缩的该低维度投影,恢复至原本的高维度:

原本数据是35维的,因而无法直接进行可视化。降至2维后,便可以了:

SVD_Plot

 

注意到,之前介绍过计算文档之间的相似程度,不妨用来验证一下,这个低维度的投影中,代表文档的点与点之间的距离,是否直觉上符合他们之间的相似度?

至于选择怎样的k来进行降维,通常会选择k使得,"能量"的损失在20%以内。

frac{sum_{i = 1}^{k}sigma_i^2}{sum_{i = 1}^{r}sigma_i^2} leq 0.8

Spectral Clustering 谱聚类

Notes on MMDS on Coursera

1 衡量聚类的“好坏”

什么样的聚集是好的聚集?

  1. 希望聚集内的相互连接尽量多
  2. 希望聚集内的节点与聚集外的节点之间连接尽量少

定义一个聚集的Cut指标(越低越好)为:网络内,只有一端节点在聚集内的边的数量。

先用AGM生成一个网络:

CutPlot1

假设现在有一个聚集A,包括三个节点[0,1,2],计算该聚集的cut指标:

Cut值并不是一个非常好的指标,如果包含度为1的节点,那么仅仅由节点一个节点构成的聚类,Cut值为1。

另一个可能的指标是Conductance(越低越好):

phi(A) = frac{text{cut(A)}}{min(vol(A), 2m-vol(A))}

其中:

  1. cut(A)是聚集A的cut分值
  2. vol(A)是聚集A的所有节点的度的和
  3. m 是网络内边的总数

2  图谱理论(Spectral Graph Theory)和谱聚类

分析表示网络的矩阵的“谱”。谱为按照对应特征值大小排列的矩阵特征向量。

CutPlot1

定义网络的拉普拉斯矩阵为网络的度矩阵与网络的邻接矩阵之差:

该矩阵有两个重要属性:

  1. 特征值都是非负实数
  2. 特征向量都是实数,并且相互垂直

一些通过线性代数可获得事实:

令拉普拉斯矩阵的特征值为lambda,特征向量为x

特征向量有两个重要属性:

  1. 是单位向量:sum_ix_i^2=1
  2. 与第一个特征向量垂直:sum_ix_icdot 1 = 0

特征值lambda _2是该表达式的最优解:

min_{x}frac{x^TMx}{x^Tx}=min_{x}sum_{i,j}(x_i-x_j)^2

因此上面的最小化问题的物理意义是将节点一部分放在<0出,另一部分放在>0处(sum_ixi=0)  ,并且使得连接两端的边尽量地小(min_{x}sum_{i,j}(x_i-x_j)^2

具体参见Rayleigh quotientFiedler vector,以及一个挺有帮助的slides

谱聚类步骤:

  1. 预处理:用拉普拉斯矩阵表示网络
  2. 分解:计算矩阵的特征值和特征向量,找到lambda_2对应的特征向量x(这样每一个节点就用一个值来表示了)
  3. 聚类:决定若干分割值,根据特征向量的值与分割值的关系,将各个节点归属到不同聚集

分割点的选择:

  1. 简单地选择0或者中位数
  2. 尝试最小化正则化的1维cut值

如果希望有多个聚集,方法有两类:

  1. 递归地进行2分聚类
  2. lambda_2lambda_3等后续特征值对应的特征向量进行K-means

奇异值分解 Singular Value Decomposition,SVD

用矩阵A乘以向量x,将获得一个新的向量y。其中,矩阵A对向量x可以进行两种变换:

  1. 旋转
  2. 伸缩

例如:

matrixtransformationofvectors

(a)中即旋转又伸缩,(b)中仅仅进行旋转,(c)中仅仅进行伸缩。

奇异值分解是对矩阵的一种因素分解,将一个矩阵分解成若干个各有其应用意义的成分。


以一个几何例子来讨论奇异值分解。

280px-Singular_value_decomposition

一个单位球在任何一个{m}times{n}矩阵下的投影都是一个超椭圆:

mathbb{R}^m下的超椭圆可以被看做是将mathbb{R}^m下的单位球沿着正交方向{u}_{1},{u}_{2},...,{u}_{m}inmathbb{R}^m进行以{sigma}_{1},{sigma}_{2},...,{sigma}_{m}inmathbb{R}^m为系数的伸缩后得到的结果。

为了方便讨论,假设{u}_{j}为单位向量,即{| {u}_{j} |}_{2}=1。则{sigma}_{j}{u}_{j}是超椭圆的主要半轴(principal semiaxes),而{sigma}_{j}为长度。

下图是一个mathbb{R}^2中的例子:

geometric example

通过矩阵A将单位圆Sinmathbb{R}^2变换为椭圆ASinmathbb{R}^2

其中{sigma}_{1},{sigma}_{2}为矩阵A的奇异值(singular values)。

注意:

  1. 如果矩阵A秩(rank)为r,则r个长度{sigma}_{j}不为0
  2. 如果矩阵Am times n矩阵,并且有m data-recalc-dims=n" />,则至多有n个长度{sigma}_{j}不为0
  3. 如果矩阵A满秩(full rank),则矩阵An个奇异值为矩阵AS中主要半轴的长度{sigma}_{j}
    通常将奇异值按照递减顺序排列,即{sigma}_{1}geq{sigma}_{2}geqldotsgeq{sigma}_{n} data-recalc-dims=0" />

一般地,在mathbb{R}^n中的该变换表示为:

A{v}_{j}={sigma}_{j}{u}_{j},1leq j leq n

一共有n个向量被A进行了变换。

更加紧凑的表达形式为:

AV=hat{U}hat{Sigma}

其中:

  1. A{m}times{n}
  2. V{n}times{n}的酉矩阵(unitary matrix)。
  3. hat{U}{m}times{n},其中列是标准正交(orthonormal)的。
  4. hat{Sigma}{n}times{n}的对角线矩阵(diagonal matrix )。如果A满秩,则 hat{Sigma}对角线值均为正。

因为V是酉矩阵,在上式两边同时乘以共轭矩阵(conjugate){V}^{*}获得:

A=hat{U}hat{Sigma}V^{*}

这个公式被称为简化奇异值分解(reduced SVD)

下图揭示了各个矩阵的维度:

dimension


通常对简化奇异值分解进行如下改进将其变为标准的奇异值分解:

  1. hat{U}矩阵中增加额外的m-nhat{U}中原有的列呈标准正交的列,构成矩阵U
    构建好的U{m}times{m},并且为酉矩阵
  2. hat{Sigma}矩阵中增加额外的m-n行0

上述过程是针对满秩矩阵而言的,对于秩亏矩阵,只需要将上述过程中的n用矩阵秩r代替即可。

得到的标准奇异值分解公式为:

A=U{Sigma}V^{*}

其中:

  1. Uinmathbb{C}^{{m}times{m}}为酉矩阵
  2. Vinmathbb{C}^{{n}times{n}}为酉矩阵
  3. Sigmainmathbb{R}^{{m}times{n}}为对角线矩阵

并且:

  • Sigma矩阵对角线上的值为非负且按照递减顺序排列
    {sigma}_{1}geq{sigma}_{2}geqldotsgeq{sigma}_{p}geq 0,p=min(m,n)

下图揭示了各个矩阵的维度:

dimension2

结合几何例子,将矩阵A的奇异值分解理解为:

  1. 首先,通过V^{*}矩阵进行酉变换,对例子中的单位球而言,该变换的效果只是旋转
  2. 然后,通过Sigma矩阵进行伸缩变换,本例中为将旋转后的单位球进行伸缩变换,形成超椭圆
  3. 最后,通过U矩阵进行酉变换,本例中为将上面形成的超椭圆进一步旋转

即,通过矩阵A进行的变换,可以视为上述3个变换的组合。


重要的定理:

  • 任何矩阵A{in}mathbb{C}^{{m}times{n}}均有一个奇异值分解,并且,奇异值{sigma}_{j}有唯一确定值。

计算奇异值分解

上面的定理确定了奇异值分解的存在,但是其值仍需要计算。

考虑如下矩阵乘法:

{A}^{T}{A} = {(U{Sigma}V^{*})}^{T}{(U{Sigma}V^{*})} ={V{Sigma}{U}^{*}}{U{Sigma}{V}^{*}} ={V}{Sigma}^{2}{V}^{*}

{A}{A}^{T} = {(U{Sigma}V^{*})}{(U{Sigma}V^{*})}^{T} ={U{Sigma}{V}^{*}}{V{Sigma}{U}^{*}} ={U}{Sigma}^{2}{U}^{*}

对上述两式分别在两边同时乘以VU有:

{A}^{T}AV = V{Sigma}^{2}

A{A}^{T}U = U{Sigma}^{2}

这样便将奇异值分解转换成了特征值的求解问题。

如果能针对这两个公式找到标准化的特征向量,则特征值的平方根即为奇异值。

在Matlab中,奇异值分解的语句为:[U,S,V]=svd(A)

Reference:

Nathan, Kutz. Computational Methods for Data Analysis Lecture Notes.