大数据存储与处理

大数据存储与运用

降维课程主页：/?page_id=397陈一帅chenyishuai@gmail引见为什么要降维？找出规律，紧缩数据量几维？降维看起来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=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稀疏求UW是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线性投影非线性方法/‎AGlobalGeometricFrameworkforNonlinearDimensionalityReduction.J.B.Tenenbaum,V.deSilvaandJ.C.Langford.Science290(5500):