数据降维

第9节数据降维提纲特征选择PCA方法流形为什么进行数据降维有些特征具有相关性，因而在进行学习建模时具有冗余可视化高维数据监督特征选择问题描述假设学习f:X-Y，其中X=x1,x2,…,xd,其中并非每一维都有相关性降维是从X中选择一个子集，或者给每一个被选特征一个权重找到一个能够表达问题的最好的子集监督特征选择-选择特征集合一般做法Forwardselection:选择分类测试中得分最高的d个特征选择单个分值最高的特征Xk,在已选的特征的基础上，给剩余特征打分•E.g.,评估（Xi|Xk）=E(Xi,Y|Xk)•E.g.,评估（Xi|Xk）=Accuracy(PredictingYfromXiandXk)重复此过程得到特征集合监督特征选择例子提纲特征选择PCA方法流形主成份分析（PrincipalComponentAnalysis,PCA）是一种利用线性映射来进行数据降维的方法，并去除数据的相关性;且最大限度保持原始数据的方差信息。PCA一项著名的工作是美国的统计学家斯通(stone)在1947年关于国民经济的研究。他曾利用美国1929一1938年各年的数据，得到了17个反映国民收入与支出的变量要素，例如雇主补贴、消费资料和生产资料、纯公共支出、净增库存、股息、利息外贸平衡等等。在进行主成份分析后，以97.4％的精度，用三新变量就取代了原17个变量的方差信息。根据经济学知识，斯通给这三个新变量分别命名为总收入f1、总收入变化率f2和经济发展或衰退的趋势f3。PCA利用3维向量能够保持原始17维向量，97.4%的方差信息(是在低维空间能够尽可能多保持原始空间数据的方差)我们所讨论的问题中都有一个近似的假设，假定数据满足高斯分布或者近似满足高斯分布问题：高斯分布需要什么参数刻画？均值，方差（离散程度）22212xyexyμμ+2σμ+2σPCA的直观解释•2x1x1f2f••••••••••••••••••••••••••••••••••••主成份分析的几何解释平移、旋转坐标轴设有n个样本，每个样本有二维即xl和x2，在由xl和x2所确定的二维平面中，n个样本点所散布的情况如椭圆状。由图可以看出这n个样本点沿着fl轴方向有最大的离散性，这是第一个主成份为了去掉相关性，第二个主成份应该正交于第一个主成份如果只考虑fl和f2中的任何一个，那么包含在原始数据中的信息将会有损失。根据系统精度的要求，可以只选择flPCA的直观解释•2x1x1f••••••••••••••••••••••••••••••••••••主成份分析的几何解释主成份分析试图在力保数据信息丢失最少的原则下，去除数据的相关性，对高维空间的数据降维处理。假设我们所讨论的实际问题中，X是p维变量，记为X1，X2，…，Xp，PCA就是要把这p个变量的问题，转变为讨论p个变量的线性组合的问题这些新的分量f1，f2，…，fk(k≤p），按照保留主要信息量的原则充分反映原变量的信息，并且相互独立。PCA的计算11112121212122221122ppppkkkpkpfuxuxuxfuxuxuxfuxuxux两个线性代数的结论1、若A是p阶正定或者半正定实阵，则可以找到正交阵U，使pp12000000TpUAUpii.2.1,其中是A的特征根。PCA的计算2、若上述矩阵的特征根所对应的单位特征向量为ppppppuuuuuuuuu212222111211),,(p1uuU则实对称阵属于不同特征根所对应的特征向量是正交的，即有p1uu,,令ATTUUUUIPCA的计算()()()()12,12iiiipxxxxin，，，，，，()()11()()niiTxippxxxxn协方差矩阵PCA的计算第二步：求出协方差矩阵分别所对应的特征向量U1，U2，…，Up，第一步：由X的协方差阵Σx，求出其特征根，即解方程，可得特征根。021p0ΣIPCA的计算ppppppuuuuuuuuu212222111211),,(p1uuU第三步：任一个样本的正交变换PCA的计算11ppppffx111121212121222211221122ppppkkkpkpppppppfuxuxuxfuxuXuxfuxuxuxfuxuxux•2x1x1f2f••••••••••••••••••••••••••••••••••••主成份分析的几何解释平移、旋转坐标轴设有n个样本，每个样本有二维即xl和x2，在由xl和x2所确定的二维平面中，n个样本点所散布的情况如椭圆状。第四步：从所有变换成份中取K个主成分PCA的计算11112121212122221122ppppkkkpkpfuxuxuxfuxuxuxfuxuxux注：计算k个主成份之前。将原始数据的中心化值:()()iixxx11kkppfUxx1x22Ddata1Ddata3个点(1,1)(2,2)(3,3)，特征向量？特征值？PCA的计算的例子1）贡献率：第i个主成份的方差在全部方差中所占比重称为贡献率，反映了原来i个特征向量的信息，有多大的提取信息能力。piii12）累积贡献率：前k个主成份共有多大的综合能力，用这k个主成份的方差和在全部方差中所占比重来描述，称为累积贡献率。piikii11PCA的中主成分个数的选择进行主成份分析的目的之一是希望用尽可能少的主成分f1，f2，…，fk（k≤p）代替原来的P维向量。PCA给人脸数据降维计算过程为：计算样本均值m中心平移每个训练样本xi计算训练集合的样本协方差矩阵对协方差矩阵进行特征值分解取协方差矩阵的K个特征向量形成变换矩阵，进行降维PCA给人脸数据降维原始数据(p维)压缩（k维)从p维空间到k维空间的投影(kp)!PCA：用于人脸降维按照其所相应的特征值的大小对特征向量排序选择头k个对应最大特征值的特征向量构成变换矩阵Upxk原始数据(p维)压缩（k维)从p维空间到k维空间的投影(kp)!TyUx特征人脸原始数据的维数为64x64=4096数据降维到8个主成份的可视化表示PCA给人脸数据降维提纲特征选择PCA方法流形所谓流形（manifold）就是一般的几何对象的总称。流形包括各种维数的曲线曲面等。和一般的降维分析一样，流形学习把一组在高维空间中的数据在低维空间中重新表示。和以往方法不同的是，在流形学习中有一个假设，就是所处理的数据采样于一个潜在的流形上，或是说对于这组数据存在一个潜在的流形。流形（Manifold）降维特征选择:依据某一标准选择性质最突出的特征特征变换:经已有特征的某种变换获取约简特征数据可视化和数据挖掘分析也需要降维通常降到2维或3维流形降维来观测数据的内在形状流形（Manifold）线性方法:(PCA)PCA的目的：寻找能够表示采样数据的最好的投影子空间.PCA的求解：对样本的协方差矩阵进行特征值分解,所求子空间为过样本均值,以最大特征值所对应的特征向量为方向的子空间.Principalcomponent线性方法的不足数据特征并不具备简单性例如:PCA不能发现螺旋型数据，适合高斯分布KPCA或许能解决主曲线问题，但曲面，立体？-1-0.500.51-1-0.500.51051015201许多高维采样数据都是由少数几个隐含变量所决定的,如人脸采样由光线亮度,人离相机的距离,人的头部姿势,人的脸部肌肉等因素决定.2从认知心理学的角度,心理学家认为人的认知过程是基于认知流形和拓扑连续性的.R流形（Manifold）局部线性嵌入(LLE).S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.等距映射(Isomap).J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.拉普拉斯特征映射(LaplacianEigenmap).M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,Vol.15,Issue6,pp.1373–1396,2003.流形（Manifold）-几种方法前提假设：采样数据所在的低维流形在局部是线性的,即每个采样点可以用它的近邻点线性表示.学习目标：在低维空间中保持每个邻域中的权值不变,即假设嵌入映射在局部是线性的条件下,最小化重构误差.流形（Manifold）-LLE假设即策略采样数据所在的低维流形在局部是线性的,即每个采样点可以用它的近邻点线性表示.在低维空间中保持每个邻域中的权值不变。流形（Manifold）-LLE1.计算每一个点的近邻点,一般采用K近邻或者邻域.2.计算权值使得把用它的K个近邻点线性表示的误差最小,即通过最小化来求出.3.保持权值不变,求在低维空间的映射,使得低维重构误差最小.，ijWijW()()ijijxWxijW()ixiX()()2min||ijijixWx()()2min||ijijiyWy流形（Manifold）-LLE最小化重构误差()ix()iy1.计算每一个点的近邻点（可采用K-NN的方法）.2.对于点和它的近邻点的权值,最小化得到：iXiXijWCXX,X.Tjkjkk计算局部协方差矩阵＝（）（）为的近邻点流形（Manifold）-LLE求解11jkkjlmlmCwC()()ijijxWx3.求解低维流形嵌入)()(TWIWIM流形（Manifold）-LLE求解2()()()(),()TijiiijijiijYyWyMyy()0iiy()()1TiiiyyINMYY目标函数：中心化、归一化：转化为求特征值与特征向量的问题，用PCA求解，低维嵌入Y是M的最小k个特征值对应的特征向量.单位协方差矩阵流形（Manifold）-LLE最小化重构误差流形学习作为一种非线性降维或数据可视化的方法已经在图像处理如人脸图像,手写数字图像,语言处理方面得了利用.将其作为一种监督的学习方法用于模式识别,虽然有研究者涉足,但是目前在这方面的工作还很有限.流形（Manifold）Tenenbaum根本不是做与数据处理有关算法的人，他是做计算认知科学（computationalcognitionscience）的。在做这个方法的时候，他还在stanford，2年就去了MIT开创一派，成了掌门人，他的组成长十分迅速。但是有趣的,在Isomap之后，他包括他在MIT带的学生就从来再也没有做过类似的工作。他在参加UCLAAlanYuille组织的一个summerschool上说，我们经常忘了做研究的原始出发点是什么。他做Isomap就是为了找一个好的visualperception的方法，他还坚持了他的方向和信仰，computationalcognition，他没有随波逐流。而由他引导起来的manifoldlearning却快速的发展成了一个新的方向。流形（Manifold）相关的故事