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

1、大数据存储与应用大数据存储与应用降维降维课程主页：http:/ 为什么要降维？ 找出规律，压缩数据量几维？降维看起来2维，其实1维看起来3维，其实2维内容 特征值与特征向量 PCA（主元素分析）Principal-Component Analysis SVD（奇异值分解）Singular-Value Decomposition CUR分解特征值与特征向量特征值与特征向量 定义 计算方法 Power Iteration寻找特征对（Eigenpairs） 特征向量矩阵定义 M 矩阵， 常数，e非零列向量 Me = e 唯一确定一个e e为unit vector 第一个非零元素为正一般计算方法 要

2、， 的行列式等于0 求得 然后通过Me = e求e 计算复杂度O(n3)Power Iteration方法 任选一个向量X0 递归 误差 Frobenius norm 足够小时，停止 这个Xk就是M的主特征向量 然后通过 Mx = x 求 x是一个单位向量：X-1 = XTPower Iteration方法 再找第二个特征对 在M中去掉第一个主特征向量的因素 然后类似计算特征向量矩阵 特征向量是单位向量 特征向量之间正交 特征向量矩阵 E 的特点PCAPCA 事例 使用特征向量进行降维 距离矩阵原理 将矩阵与一个正交单位向量矩阵相乘，意味着在欧式空间上的旋转 求 的特征矩阵E，对高维数据进行旋

3、转 原数据变成在新的坐标上的投影。 新的坐标上，第一维是主特征向量指向的那个方向，能量最强 以后依次递减 使降维成为可能原始数据原始数据按虚线旋转按虚线旋转逆时针逆时针45度旋转度旋转对称阵对称阵在新坐标系上的位置 第一维的能量 第二维的能量，而且它们正交 所以，如果要降到一维，无疑，应该保留第一维，把第二维去掉 PCASVDSVD 定义 降维 应用 计算定义 r 是 A 的 Rank （秩） U：左奇异向量 Left singular vectors 单位正交矩阵 ：奇异值 Singular values对角阵， V：右奇异向量 Right singular vectors 单位正交矩阵例

4、二维 M的秩 r = 2科幻科幻浪漫浪漫用户用户 概念概念 矩阵矩阵概念强度矩阵概念强度矩阵电影电影 概念概念 矩阵矩阵科幻科幻 浪漫浪漫科幻科幻浪漫浪漫SVD用户电影观看矩阵科幻科幻浪漫浪漫用户用户 概念概念 矩阵矩阵概念强度矩阵概念强度矩阵电影电影 概念概念 矩阵矩阵科幻科幻浪漫浪漫科幻科幻 浪漫浪漫在实际中，在实际中，U，V中没有这么多中没有这么多0概念分得没有这么清概念分得没有这么清SVD的理解 V是把电影按照用户进行概念分类后的结果 五部电影，投影到“科幻”“浪漫”两个概念上SVD的理解 是将用户按照电影进行概念分类后的结果 7个用户，投影到“科幻”“浪漫”两个概念上基于SVD的降维

5、 降概念强度最低那一维用户用户 概念概念 矩阵矩阵概念强度矩阵概念强度矩阵电影电影 概念概念 矩阵矩阵降维结果误差评估误差评估降维证明 为什么去掉 最小的那一维，误差最小？ 需要证明两点 如果M = PQR 是M的SVD，有 qii是Q对角线上的值，也就是实践中 保持8090%的能量 计算复杂度 看哪个小 LINPACK, Matlab, SPlus, Mathematica都有实现和特征向量的关系 是 的特征值对角阵 U是 的特征向量矩阵 V是 的特征向量矩阵 就是PCA的那个旋转矩阵E就可以用就可以用Power Iteration的方法解的方法解应用 已知：赵老师喜欢Matrix，给它评分

6、为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的总能量 选出后

7、，除它可能被挑上的次数的开方 好处：好理解，C稀疏求U W是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列相同

8、扔掉K-1列，保留1列 对这一列中的所有值，乘比较实验 DBLP作者数据 作者 会议 矩阵，论文数 428K 作者（行），3659会议（列） 做降维 CPU时间 准确度 存储空间：输出矩阵中数值个数/输入矩阵中数值个数性能比较 Sun, Faloutsos: Less is More: Compact Matrix Decomposition for Large Sparse Graphs, SDM 07.扩展 SVD 线性投影 非线性方法 / A Global Geometric Framework for Nonlinear Dimensionality Reduction. J. B. Tenenbaum, V. de Silva and J. C. Langfor