1268 字
6 分钟
PCA/核PCA/谱聚类--关于《矩阵计算与优化》第一次组作业

这周的矩阵计算通识课,上来就给我们当头一棒,面对不熟悉陌生的词语,以及半懂不懂的术语

我们又该怎么应对?/(ㄒoㄒ)/~~

具体方案介绍#

这次我想设计的任务很简单,以Olivetti faces数据集,做一个简单的人脸分类工作

以PCA/核PCA => kmeans聚类/谱聚类 共四种组合,对比其性能

不好理解? 开始名词解释#

olivetti数据集是什么?#

olivetti数据集是一个很经典的人脸数据集

  • 40 个人
  • 每个人 10 张照片
  • 一共 400 张人脸图
  • 每张图是灰度图(黑白),大小 64×64
  • 所以每张图片有 4096 个像素(因为 64×64=4096)

我要做什么?#

通过无监督学习(不给人工智能答案),让人工智能通过四种不同方案,分别对人脸进行分类,对比ARI(adjusted rand index)正确率

先解释一下标准操作流程#

64*64的图片已经很小了,但即使是这样,数据也有4096个(每个0-255之间)

我们首先要将其展平成4096维向量

那么问题来了,输入这么大,怎么提取出关键信息呢?

PCA/核PCA这时候就来了((kernel)Principal component analysis)

PCA/核PCA#

我们要找出这个矩阵的主要成分,那有什么和矩阵相关的工具可以用呢🤔

特征值将整个向量空间分成特征子空间的直和

每个特征子空间都反映了这个空间在某个方向上的缩放,我们选取前k个,反映了这个矩阵的主要成分

这就是主要成分分析

首先是PCA,分为三步

1.我们先把矩阵去中心化,也就是把这些人脸平均出来的平均脸减去,这样才能反映各个矩阵的差异

也即

X~=X−1μ⊤\tilde X = X - \mathbf{1}\mu^\top

2.我们要提取主成分,有两种方式

  • 我们进行奇异值分解,这个方法对所有矩阵通用
X~=UΣV⊤\tilde X = U\Sigma V^\top
  • 还记得上学期的线性代数吗,我们把矩阵及其转置矩阵相乘得到的是一个实对称矩阵,而实对称具有非常优良的性质:具有n个特征值,且每个特征值对应的特征向量正交! 那么这就可以得到n个特征子空间

3.我们选取其中数值最大的k个作为基,将每个向量对应与这k个基做内积,得到一个k维的向量,这个时候我们成功提取出了主成分!

核PCA与这个类似,但是他是把空间映射到无穷维空间上(函数)

因为PCA只能对成分进行线性组合,提取出k个主成分,但是非线性的成分似乎就不行了(例如一个环形的成分)

这个时候映射到无穷维空间就有效果了

但是无穷维怎么计算呢?

我们考虑一个隐式的无穷维空间,用连续而非离散的函数将其映射到有限维

例如:

常用的是 RBF 核(高斯核):

k(xi,xj)=exp⁡(−γ∥xi−xj∥2)k(x_i,x_j)=\exp(-\gamma\|x_i-x_j\|^2)

再通过gram矩阵(内积空间基底转换)

Kij=k(xi,xj)K_{ij}=k(x_i,x_j)

来反映每个向量之间的联系

其实步骤差不多,都是去中心化->提取主成分k维->将原向量映射到k维

kmeans聚类/谱聚类#

现在可以开始聚类了,我们去除了原数据中可能的无关成分,得到了k个最精简的成分

什么是kmeans?

我们对选择K(这里K=40)个簇

  • 先随便放 40 个“中心点”,然后每张脸归到最近的中心点;
  • 再把每一组的中心点更新成那组的平均值;
  • 重复直到稳定。

这就实现了聚类

什么是谱聚类?

这块是我最不了解的地方,因为涉及到图论

谱聚类很像:

  1. 我把每张脸当作一个点(节点)

  2. 我用相似度把点连接成一张“图”(graph)
    相似的脸连得更“紧”(边权更大)

    边权:

Wij=exp⁡(−∥zi−zj∥22σ2)W_{ij}=\exp\left(-\frac{\|z_i-z_j\|^2}{2\sigma^2}\right)
  1. 我想把这张图切成 40 块,让:
    • 同一块里面的边权尽量大(彼此相似)
    • 不同块之间的连接尽量小(彼此不相似)
  2. 怎么切?
    它会算一个叫“拉普拉斯矩阵”的东西,然后做特征分解(又是矩阵特征值那一套)
  3. 最后在特征向量空间里再用 KMeans 分组

这个拉普拉斯矩阵我还要再学习一下() 贴一下

Lsym=I−D−1/2WD−1/2L_{\text{sym}}=I-D^{-1/2}WD^{-1/2}

激动人心!!#

这时候我们终于得到了 40类人脸

我们通过ARI(Adjusted Rand Index),把我们分类出来的序号0-39 和原图标注的0-39一一对应,计算正确率

最后#

这是我想的一个比较贴近的方式()

讲述什么的我不太擅长

我希望大家能通过这个markdown了解名词,并且强烈推荐一下我想的这套工作模式