This is an old revision of the document!
主成分分析,即principal components analysis, 简称PCA,也被翻译成“主分量分析”或“主元分析”。PCA旨在利用降维的思想,把多指标转化为少数几个综合指标。在统计学中,主成分分析是一种简化数据集的技术。它是依赖于数据的线性变换。这个变换把数据变换到一个新的坐标系统中,使得任何数据投影的第一大方差在第一个坐标(称为第一主成分)上,第二大方差在第二个坐标(第二主成分)上,依次类推。主成分分析经常用减少数据集的维数,同时保持数据集的对方差贡献最大的特征。这是通过保留低阶主成分,忽略高阶主成分做到的。这样低阶成分往往能够保留住数据的最重要方面。但是,这也不是一定的,要视具体应用而定。
主成分分析法是一种降维的统计方法,它借助于一个正交变换,将其分量相关的原随机向量转化成其分量不相关的新随机向量,这在代数上表现为将原随机向量的协方差阵变换成对角形阵,在几何上表现为将原坐标系变换成新的正交坐标系,使之指向样本点散布最开的p个正交方向,然后对多维变量系统进行降维处理,使之能以一个较高的精度转换成低维变量系统,再通过构造适当的价值函数,进一步把低维系统转化成一维系统。
概括起来说,主成分分析主要由以下几个方面的作用。
奇异值分解是线性代数中一种重要的矩阵分解,在信号处理、统计学等领域有重要应用。奇异值分解在某些方面与对称矩阵或Hermite矩阵基于特征向量的对角化类似。然而这两种矩阵分解尽管有其相关性,但还是有明显的不同。对称阵特征向量分解的基础是谱分析,而奇异值分解则是谱分析理论在任意矩阵上的推广。奇异值分解在统计中的主要应用为主成分分析(PCA),它是一种数据分析方法,用来找出大量数据中所隐含的“模式”,它可以用在模式识别,数据压缩等方面。PCA算法的作用是把数据集映射到低维空间中去。 数据集的特征值(在SVD中用奇异值表征)按照重要性排列,降维的过程就是舍弃不重要的特征向量的过程,而剩下的特征向量张成空间为降维后的空间。
只适用于一般的离散数据集,对于非线性数据集不适用。
LLE算法针对非线性降维问题利用线性重构的局部对称性找出高维数据空间中的非线性结构并在保持各数据点临近位置关系情况下把高维空间数据点映射为低维空间对应的数据点其计算步骤包括计算寻找数据点或邻居数据点构造数据点及计算权值矩阵并通过权值矩阵计算低维向量。
相同点:都是降低维度的算法。可把相距很远的数据点映射在一个平面的临近位置。 不同点:PCA和MDS都是对高维空间中的可变因素的线性建模。LLE则是非线性的降维问题,不会涉及局部最小值问题。映射后,PCA和MDS无法保留流形的基本结构,而LLE则可以保证两点之间的测量距离不会改变。
(1)寻找每个样本点的k-近邻点。把相对于所求样本点距离最近的k个样本点规定为所求样本点的k-近邻点,这里k是一个预先给定值。由Sam T. Roweis 和 Lawrence K. Saul等人所提出的LLE算法中,采用了欧氏距离以减轻计算的复杂度。然而,若假定高维空间中的数据是非线性分布的,也可采用Diijstra距离。Dijkstra距离是一种图上的测地距离,它能够保持样本点之间的曲面特性。这一度量在ISOMAP算法中有广泛的应用。针对样本点多的情况,普通的Dijkstra算法不能满足LLE算法的要求。 (2)由每个样本点的近邻点计算出该样本点的局部重建权值矩阵W使得
(3) 由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。
寻找X空间中的邻点
For i=1:N compute the distance from Xi to every other point Xj find the K smallest distances assign the corresponding points to be neighbors of Xi end
重构权重W
for i=1:N create matrix Z consisting of all neighbors of Xi subtract Xi from every column of Z compute the local covariance C=Z'*Z solve linear system C*w = 1 for w set Wij=0 if j is not a neighbor of I set the remaining elements in the ith row of W equal to w/sum(w); end
计算输出矩阵Y
create sparse matrix M = (I-W)'*(I-W) find bottom d+1 eigenvectors of M (corresponding to the d+1 smallest eigenvalues) set the q-th ROW of Y to be the q+1 smallest eigenvector (discard the bottom eigenvector [1,1,1,1...] with eigenvalue zero)
ISOMAP是近年来用于非线性降维的一个重要算法,它是对经典MDS的扩展,也是寻求保持数据点之间距离的低维表示。算法的基本思想是利用样本向量之间的欧氏距离Dist(i,j)计算出样本之间的测地距离DG(i,j),然后使用经典MDS算法来获得相应的低维投影。这样能够减少样本之间的欧式距离Dist(i,j)与DG(i,j)的误差,最大程度上保持高维数据内在的非线性(等距)几何结构,通过低维数据的分析来获得相应的高维数据特性,从而达到简化分析、获取数据有效特征以及可视化数据的目标。
(1)选取邻域构造邻域图G。
计算每个样本点同其余样本点之间的欧氏距离。当Xj是Xi的最近的k个点中的一个时,认为它们是相邻的,即图G有边XjXi(这种邻域称为k-邻域)。设边XjXi的权为d(Xj,Xi),对P=1,……,N有
(2)计算任意两个样本向量之间的最短路径。
当图G有边XjXi时,设最短路径如dG(Xi,Xj)=d(Xj,Xi),否则设dG(Xi,Xj)=\infty。对k=1,2,…,N,
dG(Xi,Xj)=min {dG(Xi,Xj),dG(Xi,Xk)+dG(Xk,Xj)}
(3)计算D维映射
将经典MDS应用到距离矩阵DG。
令
嵌入(Embedding)被描述为一个机器学习任务,AdaBoost方法用来把多个简单的1维嵌入结合成为一个d维的嵌入;按照与一个查询对象的相似程度获得所有DB对象的排序。
要点:D可能计算复杂;D可能不满足三角不等式。
嵌入被看做分类器,如果a与b或c接近,给出对a,b,c的估计。其中X为对象集,D\le x 为距离函数。