大数据存储与处理降维

大数据存储与应用降维,课程主页：,介绍,为什么要降维？找出规律，压缩数据量,几维？,降维,看起来2维，其实1维,看起来3维，其实2维,内容,特征值与特征向量PCA（主元素分析）Principal-ComponentAnalysisSVD（奇异值分解）Singular-ValueDecompositionCUR分解,特征值与特征向量,特征值与特征向量,定义计算方法PowerIteration寻找特征对（Eigenpairs）特征向量矩阵,定义,M矩阵，常数，e非零列向量Me=e唯一确定一个ee为unitvector第一个非零元素为正,一般计算方法,要，的行列式等于0求得然后通过Me=e求e计算复杂度O(n3),PowerIteration方法,任选一个向量X0递归误差Frobeniusnorm足够小时，停止这个Xk就是M的主特征向量然后通过Mx=x求x是一个单位向量：X-1=XT,PowerIteration方法,再找第二个特征对在M中去掉第一个主特征向量的因素然后类似计算,特征向量矩阵,特征向量是单位向量特征向量之间正交特征向量矩阵E的特点,PCA,PCA,事例使用特征向量进行降维距离矩阵,原理,将矩阵与一个正交单位向量矩阵相乘，意味着在欧式空间上的旋转求的特征矩阵E，对高维数据进行旋转原数据变成在新的坐标上的投影。新的坐标上，第一维是主特征向量指向的那个方向，能量最强以后依次递减使降维成为可能,原始数据,按虚线旋转,逆时针45度旋转,对称阵,在新坐标系上的位置,第一维的能量第二维的能量，而且它们正交所以，如果要降到一维，无疑，应该保留第一维，把第二维去掉PCA,SVD,SVD,定义降维应用计算,定义,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对角线上的值，也就是,实践中,保持8090%的能量计算复杂度看哪个小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！占空间多,CUR,CUR,正确地选择行/列构造中间矩阵消除冗余的行/列,缘起,克服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,SDM07.,扩展,SVD线性投影非线性方法/AGlobalGeometricFrameworkforNonlinearDimensionalityReduction.J.B.Tenenbaum,V.deSilvaandJ.C.Langford.Scien