大数据存储与处理-降维45

大数据存储与应用降维课程主页：@gmail.com介绍•为什么要降维？•找出规律，压缩数据量几维？降维看起来2维，其实1维看起来3维，其实2维内容•特征值与特征向量•PCA（主元素分析）Principal-ComponentAnalysis•SVD（奇异值分解）Singular-ValueDecomposition•CUR分解特征值与特征向量特征值与特征向量•定义•计算方法•PowerIteration寻找特征对（Eigenpairs）•特征向量矩阵定义•M矩阵，λ常数，e非零列向量•Me=λe•唯一确定一个e•e为unitvector•第一个非零元素为正一般计算方法•要，的行列式等于0•求得λ•然后通过Me=λe求e•计算复杂度O(n3)PowerIteration方法•任选一个向量X0•递归•误差Frobeniusnorm足够小时，停止•这个Xk就是M的主特征向量•然后通过Mx=λx求λ•x是一个单位向量：X-1=XTPowerIteration方法•再找第二个特征对•在M中去掉第一个主特征向量的因素•然后类似计算特征向量矩阵•特征向量是单位向量•特征向量之间正交•特征向量矩阵E的特点PCAPCA•事例•使用特征向量进行降维•距离矩阵原理•将矩阵与一个正交单位向量矩阵相乘，意味着在欧式空间上的旋转•求的特征矩阵E，对高维数据进行旋转•原数据变成在新的坐标上的投影。•新的坐标上，第一维是主特征向量指向的那个方向，能量最强•以后依次递减•使降维成为可能原始数据按虚线旋转逆时针45度旋转对称阵在新坐标系上的位置•第一维的能量第二维的能量，而且它们正交•所以，如果要降到一维，无疑，应该保留第一维，把第二维去掉•PCASVDSVD•定义•降维•应用•计算定义•r是A的Rank（秩）•U：左奇异向量Leftsingularvectors单位正交矩阵•：奇异值Singularvalues对角阵，•V：右奇异向量Rightsingularvectors单位正交矩阵例•二维•M的秩r=2科幻浪漫用户–概念矩阵概念强度矩阵电影–概念矩阵科幻浪漫科幻浪漫SVD用户电影观看矩阵科幻浪漫用户–概念矩阵概念强度矩阵电影–概念矩阵科幻浪漫科幻浪漫在实际中，U，V中没有这么多0概念分得没有这么清SVD的理解•V是把电影按照用户进行概念分类后的结果•五部电影，投影到“科幻”“浪漫”两个概念上SVD的理解•是将用户按照电影进行概念分类后的结果•7个用户，投影到“科幻”“浪漫”两个概念上基于SVD的降维•降概念强度最低那一维用户–概念矩阵概念强度矩阵电影–概念矩阵降维结果误差评估降维证明•为什么去掉最小的那一维，误差最小？•需要证明两点•如果M=PQR是M的SVD，有•qii是Q对角线上的值，也就是实践中•保持80～90%的能量•计算复杂度•看哪个小•LINPACK,Matlab,SPlus,Mathematica都有实现和特征向量的关系•是的特征值对角阵•U是的特征向量矩阵•V是的特征向量矩阵•就是PCA的那个旋转矩阵E就可以用PowerIteration的方法解应用•已知：赵老师喜欢Matrix，给它评分为5，•问：赵老师喜欢什么类型的片?•qV计算，把赵老师投影到概念空间上应用•给赵老师推荐什么片？•把赵老师的概念向量qV，乘视频的概念向量VT，得到推荐的视频向量=[1.641.641.64-0.16-0.16]•给他推荐《异形》应用•寻找和赵老师兴趣相同的人•他们虽然看的是不同的片，但发现了他们的兴趣相同•通过UI矩阵发现的SVD的问题•结果难以解释•为什么这么多维？•U和V很Dense！•占空间多CURCUR•正确地选择行/列•构造中间矩阵•消除冗余的行/列缘起•克服SVD的问题•M=CUR•随机找c行，组成C•选行j的概率P(j)=其能量（值的平方和）/A的总能量•选出后，除它可能被挑上的次数的开方•好处：好理解，C稀疏求U•W是C和R的交集•对它SVD：••Z+伪反（pseudoinverse）•Z中的元素，如果是0，保持不变；如果非0，取倒数性能•[Drineasetal.]•取行，列，就能在O(m*n)时间内，以概率获得•Drineasetal.,FastMonteCarloAlgorithmsforMatricesIII:ComputingaCompressedApproximateMatrixDecomposition,SIAMJournalonComputing,2006.冗余行/列的处理•K列相同•扔掉K-1列，保留1列•对这一列中的所有值，乘比较实验•DBLP作者数据•作者–会议矩阵，论文数•428K作者（行），3659会议（列）•做降维•CPU时间•准确度•存储空间：输出矩阵中数值个数/输入矩阵中数值个数性能比较•Sun,Faloutsos:LessisMore:CompactMatrixDecompositionforLargeSparseGraphs,SDM’07.扩展•SVD•线性投影•非线性方法isomap.stanford.edu/‎•AGlobalGeometricFrameworkforNonlinearDimensionalityReduction.J.B.Tenenbaum,V.deSilvaandJ.C.Langford.Science290(5500):2319-2323,•给你698张人脸的图像（64×64灰度），通过isomap降维方法将每张脸当做一个点映到二维平面上，使得横坐标恰好反映人脸左右看的程度，纵坐标反映人脸上下看的程度。••11.3.2