大数据存储与应用大数据存储与应用介绍为什么要降维？找出规律，压缩数据量几维？降维看起来2维，其实1维看起来3维，其实2维内容特征值与特征向量PCA（主元素分析）Principal-Component AnalysisSVD（奇异值分解）Singular-Value DecompositionCUR分解特征值与特征向量特征值与特征向量定义计算方法Power Iteration寻找特征对（Eigenpairs）特征向量矩阵定义M 矩阵， 常数，e非零列向量Me = e唯一确定一个ee为unit vector第一个非零元素为正一般计算方法要 ， 的行列式等于0求得然后通过Me = e求e计算复杂度O(n3)Power Iteration方法任选一个向量X0递归误差 Frobenius norm 足够小时，停止这个Xk就是M的主特征向量然后通过 Mx = x 求 x是一个单位向量：X-1 = XTPower Iteration方法再找第二个特征对在M中去掉第一个主特征向量的因素然后类似计算特征向量矩阵特征向量是单位向量特征向量之间正交特征向量矩阵 E 的特点PCAPCA事例使用特征向量进行降维距离矩阵原理将矩阵与一个正交单位向量矩阵相乘，意味着在欧式空间上的旋转求 的特征矩阵E，对高维数据进行旋转原数据变成在新的坐标上的投影。新的坐标上，第一维是主特征向量指向的那个方向，能量最强以后依次递减使降维成为可能原始数据原始数据按虚线旋转按虚线旋转逆时针逆时针45度旋转度旋转对称阵对称阵在新坐标系上的位置第一维的能量 第二维的能量，而且它们正交所以，如果要降到一维，无疑，应该保留第一维，把第二维去掉PCASVDSVD定义降维应用计算定义r 是 A 的 Rank （秩）U：左奇异向量 Left singular vectors 单位正交矩阵 ：奇异值 Singular values对角阵，V：右奇异向量 Right singular vectors 单位正交矩阵例二维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就可以用就可以用Power Iteration的方法解的方法解应用已知：赵老师喜欢Matrix，给它评分为5，问：赵老师喜欢什么类型的片?qV计算，把赵老师投影到概念空间上应用给赵老师推荐什么片？把赵老师的概念向量qV，乘视频的概念向量VT，得到推荐的视频向量 = 1.64 1.64 1.64 -0.16 -0.16给他推荐异形 应用寻找和赵老师兴趣相同的人他们虽然看的是不同的片，但发现了他们的兴趣相同通过UI矩阵发现的SVD的问题结果难以解释为什么这么多维？U和V很Dense！占空间多CURCUR正确地选择行/列构造中间矩阵消除冗余的行/列缘起克服SVD的问题M = CUR随机找c行，组成C选行j的概率P(j) = 其能量（值的平方和）/A的总能量选出后，除它可能被挑上的次数的开方好处：好理解，C稀疏求UW是C和R的交集对它SVD： Z+ 伪反 （pseudoinverse）Z中的元素，如果是0，保持不变；如果非0，取倒数性能Drineas et al. 取 行， 列，就能在O(m*n)时间内，以概率 获得Drineas et al., Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition, SIAM Journal on Computing, 2006.冗余行/列的处理K列相同扔掉K-1列，保留1列对这一列中的所有值，乘比较实验DBLP作者数据作者 会议 矩阵，论文数428K 作者（行），3659会议（列）做降维CPU时间准确度存储空间：输出矩阵中数值个数/输入矩阵中数值个数性能比较Sun, Faloutsos: Less is More: Compact Matrix Decomposition for Large Sparse Graphs, SDM 07.扩展SVD线性投影非线性方法 isomap.stanford.edu/A Global Geometric Framework for Nonlinear Dimensionality Reduction. J. B. Tenenbaum, V. de Silva and J. C. Langford. Science 290 (5500): 2319-2323,给你698张人脸的图像（6464灰度），通过isomap降维方法将每张脸当做一个点映到二维平面上，使得横坐标恰好反映人脸左右看的程度，纵坐标反映人脸上下看的程度。http:/blog.csdn.net/littlestonelj/article/details/7534382练习11.3.2