机器学习入门|降维(一)(MIDS,PCA,KPCA)

简介: 机器学习领域中所谓的降维就是指采用某种映射方法,将原高维空间中的数据点映射到低维度的空间中。降维的原因,在周志华《机器学习》中用最近邻分类器给了一个解释——数据集需要满足密采样条件,以及高维计算下会有很多麻烦,甚至在尾数特别高的时候连计算内积都变的复杂,这种计算阻碍称为“维数灾难”。

机器学习领域中所谓的降维就是指采用某种映射方法,将原高维空间中的数据点映射到低维度的空间中。降维的原因,在周志华《机器学习》中用最近邻分类器给了一个解释——数据集需要满足密采样条件,以及高维计算下会有很多麻烦,甚至在尾数特别高的时候连计算内积都变的复杂,这种计算阻碍称为“维数灾难”。其他的原因还有过滤噪音等。

多维缩放(MIDS)

假设样本数m($X\in \mathbb{R}^{d*m}$),样本间的距离矩阵$D\in \mathbb{R}^{m*m}$,其第i行第j列的元素为$dist_{ij}$是$x_{i}$到$x_{j}$的距离

这里降维的目标是得到样本在$d'\leq d$的$d'$维空间里的表示:$Z\in \mathbb{R}^{d'*m}$且任意两个样本之间的欧氏距离不变。即($||z_{i}-z_{j}||=dist_{ij}$)

令内积矩阵$B=Z^{T}Z\in \mathbb{R}^{m*m}$,$b_{ij}=z_{i}^{T}z_{j}$有

$$ dist_{ij}^{2}=||z_{i}||^{2}+||z_{j}||^{2}-2z_{i}^{T}z_{j} $$

$$ =b_{ii}+b_{jj}-2b_{ij} $$

为便于计算,令Z被中心化,即质心在原点,则$\sum_{i=1}^{m}z_{i}=0$,则:

$$ \sum_{i=1}^{m}dist_{ij}^{2}=\sum_{i=1}^{m}b_{ii}+mb_{jj}-2\sum_{i=1}^{m}b_{ij} $$

$$ =tr(B)+mb_{jj} $$

$$ \sum_{j=1}^{m}dist_{ij}^{2}=tr(B)+mb_{ii} $$

$$ \sum_{i=1}^{m}\sum_{j=1}^{m}dist_{ij}^{2}=m tr(B)+m\sum_{j=1}^{m}b_{jj}=2m\ tr(B) $$

$$ dist_{i.}^{2}=\frac{1}{m}\sum_{i=1}^{m}dist_{ij}^{2} $$

$$ dist_{.j}^{2}=\frac{1}{m}\sum_{j=1}^{m}dist_{ij}^{2} $$

$$ dist_{..}^{2}=\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}dist_{ij}^{2} $$

则可以由上式得:

$$ b_{ij}=-\frac{1}{2}(dist_{ij}^{2}-dist_{i.}^{2}-dist_{.j}^{2}+dist_{..}^{2}) $$

由此就可以在保持样本距离矩阵不变并求出内积矩阵B。

接下来求矩阵Z:

可以把B特征值分解为$B=V\Lambda V^{T},\Lambda =diag(\lambda_{1},\lambda_{2},...,\lambda_{d} )$(这是写到现在为止学了线代唯一还记得的:))

特征值按从大到小排序,令$ \tilde{\Lambda}=diag(\lambda_{1},\lambda_{2},...,\lambda_{d'} ) $,因为降维后往往距离与原始距离尽可能接近,不必严格相等,所以只需取最大的$d'$个特征即可。而Z即可表达为:

$$ Z= \tilde{\Lambda}^{\frac{1}{2}}\tilde{V}^{T}\in \mathbb{R}^{d'*m} $$

求出Z矩阵后,MIDS也就结束了。如果Z满足$Z=W^{T}X,W\in\mathbb{R}^{d*d'}$,则此变换为线性变换。

主成分分析(PCA)

将d维的样本降维至d’维,相当于用一个d'维超平面让所有人样本点投影到这个超平面上。而为了使这个超平面尽可能完整的表达样本点的性质,被削减的维度部分的偏离程度必然要尽可能的小。

两个性质:

  • 最近重构性:样本点到这个超平面的距离尽可能近
  • 最大可分性:样本点在在这个超平面上的投影尽可能展开(方差尽可能大)

从这两个性质出发,都可以推导出同样的结果,从最大可分性出发:
$z_{i}=Wx_{i}$,则为了方差最大化,求:

$$ \underset{W}{max} \ \sum_{i}z_{i}z_{i}^{T}=max \sum_{i}W^{T}x_{i}x_{i}^{T}W $$

则,优化目标可以写成:

$$ \underset{W}{max} \ tr(W^{T}XX_{T}W) $$

因为不关心W大小,只关心超平面的方向,故默认W为单位矩阵
运用拉格朗日乘数法,得到

$$ XX^{T}\omega_{i}=\lambda_{i}\omega_{i} $$

最后,对协方差矩阵$XX^{T}$进行特征值分解,即可得到d'个按大小排序的特征值$\lambda_{1},...,\lambda_{d'}$以及对应的特征向量$W^{*}=(\omega_{1},...,\omega_{d'})$也就是主成分分析的解。

降维的个数由使用者决定。

多维缩放和主成分分析看上去方法还挺相似的,都是保留最大的d'个特征值,那么矩阵的秩也变为d',势必会舍弃一部分信息来做到降维,而这部分微量信息也往往和噪声有关,它们的舍弃一定程度上能达到去躁的效果。

李政轩老师的PCA和KPCA讲解视频,非常详细易懂http://www.powercam.cc/slide/6553
核化PCA(KPCA)
假设$z_{i}$是样本点$x_{i}$在高维空间的像,即通过映射$\phi$,即$z_{i}=phi(x_{i}),i=1,2,...,m$。

则由上述结果可得,新的式子为

$$ ZZ^{T}\omega_{i}=\lambda_{i}\omega_{i} $$

可得

$$ \omega_{j}=\frac{1}{\lambda_{j}}\left(\sum_{i=1}^{m}z_{i}z_{i}^{T}\right)\omega_{j}=\sum_{i=1}^{m}z_{i}\frac{z_{i}^{T}\omega_{j}}{\lambda_{j}} $$

$$ =\sum_{i=1}^{m}z_{i}\alpha_{i}^{j} $$

其中$\alpha_{i}^{j}=\frac{1}{\lambda_{j}}z_{i}^{T}\omega_{j}$
因为不清楚$\phi$的具体形式,于是引入核函数:

$$ \kappa(x_{i},x_{j})=\phi(x_{i})^{T}\phi(x_{j}) $$

由上式可以得到

$$ K\alpha^{j}=\lambda_{j}\alpha^{j} $$

$K$为$\kappa$对应的核矩阵

同样,这也是特征值分解问题,解出最大的d'个特征值对应的特征向量即可。

个人更推荐观看李政轩的讲解视频,推导过程也更为清晰,这里的过程是参考周志华《机器学习》的,矩阵的行列关系没有细说,看起来容易似懂不懂。

目录
相关文章
|
13天前
|
机器学习/深度学习 数据可视化 计算机视觉
【视频】机器学习交叉验证CV原理及R语言主成分PCA回归分析犯罪率|数据共享
【视频】机器学习交叉验证CV原理及R语言主成分PCA回归分析犯罪率|数据共享
|
13天前
|
机器学习/深度学习 算法 数据可视化
机器学习第11天:降维
机器学习第11天:降维
|
13天前
|
机器学习/深度学习 算法 数据可视化
Machine Learning机器学习之高维数据降维(主成分分析PCA、线性判别分析、自编码器超级无敌详细讲解)
Machine Learning机器学习之高维数据降维(主成分分析PCA、线性判别分析、自编码器超级无敌详细讲解)
|
13天前
|
机器学习/深度学习 人工智能 运维
【人工智能技术专题】「入门到精通系列教程」打好AI基础带你进军人工智能领域的全流程技术体系(机器学习知识导论)(二)
【人工智能技术专题】「入门到精通系列教程」打好AI基础带你进军人工智能领域的全流程技术体系(机器学习知识导论)
65 1
|
13天前
|
机器学习/深度学习 人工智能 自然语言处理
【人工智能技术专题】「入门到精通系列教程」打好AI基础带你进军人工智能领域的全流程技术体系(机器学习知识导论)(一)
【人工智能技术专题】「入门到精通系列教程」打好AI基础带你进军人工智能领域的全流程技术体系(机器学习知识导论)
89 1
|
8天前
|
机器学习/深度学习 数据采集 算法
2024年机器学习入门,2024年最新字节跳动视频面试一般多久会收到结果
2024年机器学习入门,2024年最新字节跳动视频面试一般多久会收到结果
2024年机器学习入门,2024年最新字节跳动视频面试一般多久会收到结果
|
11天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】K-means算法与PCA算法之间有什么联系?
【5月更文挑战第15天】【机器学习】K-means算法与PCA算法之间有什么联系?
|
13天前
|
机器学习/深度学习 算法 图计算
图机器学习入门:基本概念介绍
图机器学习是机器学习的分支,专注于处理图形结构数据,其中节点代表实体,边表示实体间关系。本文介绍了图的基本概念,如无向图与有向图,以及图的性质,如节点度、邻接矩阵。此外,还讨论了加权图、自循环、多重图、双部图、异构图、平面图和循环图。图在描述数据关系和特征方面具有灵活性,为机器学习算法提供了丰富的结构信息。
13 0
|
13天前
|
机器学习/深度学习
机器学习基础入门(二)(线性回归与成本函数)
已知一系列房子的大小以及其对应的价格的数据,要求是已知房子大小预测其房子的价格
|
13天前
|
机器学习/深度学习 自然语言处理 语音技术
【Python 机器学习专栏】Python 深度学习入门:神经网络基础
【4月更文挑战第30天】本文介绍了Python在深度学习中应用于神经网络的基础知识,包括神经网络概念、基本结构、训练过程,以及Python中的深度学习库TensorFlow和PyTorch。通过示例展示了如何使用Python实现神经网络,并提及优化技巧如正则化和Dropout。最后,概述了神经网络在图像识别、语音识别和自然语言处理等领域的应用,并强调掌握这些知识对深度学习的重要性。随着技术进步,神经网络的应用将持续扩展,期待更多创新。

热门文章

最新文章