Lecture 11:Unsupervised Learning:Linear Dimension Reduction

Clustering

K-means

算法步骤:

迭代更新使得最后聚类中心收敛。但事先需要定好有多少类。

Hierarchical Agglomerative Clustering (HAC)

自下而上,每次选两个最近的聚为一类,直到所有的都分成一类
最后选择一个阈值划分,如蓝色绿色和红色的线

Dimension Reduction

找到一个映射,使得x能够映射到低维z

Principle Component Analysis (PCA)

目的是找到一个维度,使得投影得到的variance最大,也即最大程度保留数据的差异性。

形式化可以写成(一维情形):

其中:

$\overline{z_1}$表示z的均值

假如我们要投影到多维,其他维度也有同样的目标。其中每个维度之间都应该是相互正交的。

如何做?

找到$ \frac{1}{N}∑(x−\overline{x} ) (x−\overline{x})^T$的前k个最大的特征值对应的特征向量,组合起来即是我们要找的$W$

证明

—-Warning of Math—-
目的:$Var(z_1 )=\frac{1}{N} ∑_{z_1}(z_1−\overline{z_1} )^2 $
其中 $\overline{z_1} =\frac{1}{N} ∑{z_1} = \frac{1}{N} ∑ w^1 \cdot x=w^1\cdot \overline{x}$

推导:

改变符号 $S=Cov(x)$

利用拉格朗日乘数法,有:
$Sw^1=αw^1$
等式两边各左乘$(w^1)^T$,有:
$(w^1 )^T Sw^1=α(w^1 )^T w^1=α$

也即,$α$是$S$的特征值,选择最大的特征值,就能够最大化我们的目标。

同理,我们要找$w^2$,最大化$(w^2 )^T Sw^2$,其中有:
$(w^2 )^T w^2=1$
$(w^2 )^T w^1=0$ (与第一维正交)

因此利用拉格朗日乘数法:

最终得到,w2对应第二大的特征值的特征向量。

以此类推,其他维也同理。
—-End of Math—-

PCA的其他

实际上最终得到的z,每一维之间的协方差都为0

证明如下:

PCA也可以用SVD来做:

U中保存了K个特征向量。

从另一种角度理解PCA,也可以认为PCA是一种autoencoder:

PCA的问题

PCA是无监督学习,如果有标签,则无法按照类别来进行正确降维,如:

第二就是PCA是线性变换,对于一些需要非线性变换的无能为力

Matrix Factorization

定义:矩阵分解,就是将一个矩阵D分解为U和V的乘积,即对于一个特定的规模为m*n的矩阵D,估计出规模分别为m*k和n*k的矩阵U和V,使得$UV^T$的值尽可能逼近矩阵D。常用于推荐系统。

思想:
假如有一个矩阵:

假设横轴和纵轴每一维都有一个向量代表该维,矩阵的每个元素就是横轴和纵轴对应维的点积。我们的目的是尽可能减小:

其中$r_i$ $r_j$就是向量表示,$n_{ij}$就是矩阵的内容。

可以使用SVD求解上式:

实际上,考虑每一行或列本身的特性,我们对Loss进行扩展:

使用SGD可以求解。