大数据计算方法 课件 chap10-基于矩阵分解的数据挖掘与分析

1大数据计算方法Chap10：基于矩阵分解的数据挖掘与分析PCA与降秩最小二乘随机化矩阵低秩分解非负矩阵分解Outline2PCA与降秩最小二乘PCA不满秩最小二乘问题主分量回归3主成分分析(PCA)数据矩阵特征间有相关性(数据有误差),可用少量独立特征(主成分)刻画找一组特征的主成分z1…,zk,使n个特征近似为它们的组合4第1次观测数据第m次观测数据第i

次观测数据特征1特征nA秩

k主成分

即A的前几个左奇异向量怎么求主成分?

normalizedfirstprincipalcomponent低秩近似(分解)主成分分析(PCA)一组高度与重量的数据两列数据是非常有关联的近似表示高度与重量有一个潜在的主要成分>>[U,S,V]=svd(A,0);>>sigma=diag(S)sigma= 156.4358 8.7658>>E1=sigma(1)*U(:,1)*V(:,1)'第一主成分是：5V(:,1)'=[0.9468,0.3219]主成分方向principalcomponentdirections主成分分析(PCA)

6

(居中化)主成分分析(PCA)非负矩阵的第一对奇异向量矩阵A的各行数据到其距离平方和

最小的过原点直线,一定如图穿过

这堆数据点根据之前的结论,该该直线方向沿

右奇异向量v1所在方向若A为非负矩阵,则向量v1中元素全非负,或全非正若取v1为非负向量,则,即左奇异向量u1也非负对非负矩阵,其第一个左/右奇异向量可同时为非负向量!PCA用途降维(分类、聚类的预处理,可视化),嵌入表达,LSI,…70101010(第一主方向)若A还对称呢?主特征值一定是正数通常要先对数据矩阵做“列居中”AA-

(sumofentriesineachcolumniszero)

降秩最小二乘

(线性回归的最小范数解)Ax

b>>x=pinv(A)*b;最小化要求是范数最小的最优解解求最小范数解比基本解计算量大些2-范数相同最小范数解Rank(A)=r,列不满秩(SVD分解)(QRCP分解)8降秩最小二乘(ReducedRankLS)Ax

b由于数据误差,精确求解往往不好很多时候，x代表模型，或是中间结果分类问题:测试数据b,关心或的值回归分析:9特征1

特征nAb因变量解得到，代表模型若A的各列近似相关,这个问题很敏感新观测怎样让预测结果准确/合理?应将A近似为一个低秩模型再做拟合！overfitting第1次观测数据第m次观测数据第i

次观测数据降秩最小二乘(ReducedRankLS)

10计算很准确>>A0=[101111];>>A=[A0,A0*[1;0.5]+1e-7*randn(3,1)];>>b=A*[1;1;1]+1e-4*randn(3,1);>>x=A\b

与扰动差不多这个结果好得多!

抑制过拟合降秩最小二乘(ReducedRankLS)Ax

b在某个子空间Zk中搜索最优x,该子空间基为{z1,z2,…,zk}求解主成分回归如果A是低秩矩阵，则精确(最小范数)解x是{v1,v2,…,vr}的线性组合11解残差平方为即对A做秩k近似再求解!基于截断SVD的近似保留了A中数据的主成分!取前k个右奇异向量形成Zk?主成分回归主成分回归(PrincipalComponentRegression)选择适当的k,解例10.4:文档-关键词矩阵查询向量,与文档库的匹配度q1:“排名”,“网页”,“万维网”q2:“中国队”,“国际足联”12若解原始LLS问题,即k=5,两个残差区别不大但显然q1与文档库内容更相符若考虑k=1~3,两个残差相差很大；例如k=2,3时…解q1q2应用:文档自动归类？随机化矩阵低秩分解子空间嵌入固定秩参数的随机化低秩分解自适应的随机化低秩分解少遍历与单遍历算法有关应用与发展13子空间嵌入(subspaceembedding)

14接近最优，时间短/易并行=

m

nm

k

k

n

m

nn

l标准高斯m

l或

(离散余弦变换)(随机取列)(1/-1)固定秩参数的随机化低秩分解

15=

正交化

m

nm

l

l

n

幂迭代/同步迭代

奇异值衰减更快正交化减少数值误差

~

固定秩参数的随机化低秩分解

16

m

nm

l

l

n

~

l

l

l

l

l

n近似的k-SVD这可以提高结果的近似程度

（无幂迭代）

固定秩参数的随机化低秩分解基础的随机化SVD算法例10.517>>U=orth(randn(4000,2000));>>V=orth(randn(2000,2000));>>S=diag(1./(1:2000).^2);>>A=U*S*V';>>tic;[Us,Ss,Vs]=svds(A,100);toc;历时2.569249秒。>>tic;[Ub,Sb,Vb]=basic_rSVD(A,100,105,2);toc;历时0.092135秒。>>norm(diag(Ss)-diag(Sb))ans= 8.0063e-06奇异值为的矩阵构造奇异值按平方规律衰减的矩阵,比较随机化算法与svds快28倍计算出的奇异值的误差很小

自适应的随机化低秩分解

18

m

nm

k

k

n

我们发现残差的Frobenius范数可以增量计算!

[1]P.-G.Martinsson,S.Voronin,Arandomizedblockedalgorithmforefficientlycomputingrank-revealingfactorizationsofmatrices,SIAMJ.Sci.Comput.,2016.svds是标准做法；随机化算法randQB在准确度要求不高、要求数据遍历少的场景下有很大优势W.Yu,Y.GuandY.Li,"Efficientrandomizedalgorithmsforthefixed-precisionlow-rankmatrixapproximation,"

SIAMJournalonMatrixAnalysisandApplications,39(3):1339-1359,Aug.2018自适应的随机化低秩分解randQB_EI算法(cont’d)19

m

nm

k

k

n数学上与randQB算法等价适合于稀疏的A节省内存用量与计算时间

>>helpsvdsketch

自适应的随机化低秩分解randQB_EI的实验结果20

自适应的随机化低秩分解randQB_EI的实验结果(不用看红色的线)21w/opowerschemew/powerscheme对于稀疏矩阵(0.3%稠密度)，比randQB_b算法最多快22倍，节省79倍内存对于稠密矩阵，有超过2倍的时间与内存节省自适应的随机化低秩分解randQB_EI的自适应分解风景图片(3168x4752)10%近似准确度7X矩阵元素压缩,比SVD快12X对用TD-IDF模型得到的关键词/

作者矩阵(8300x100000)，也得

到近似最优k值,比svds快10X

更快的farPCA算法22randQB_EISVDRangeFinderimageP=2441AMinerP=1244021158018P=22229确定出的秩k

少遍历与单遍历算法

23DDR4内存：~50GB/sSDD硬盘：~3GB/sSATA硬盘:~300MB/s

少遍历与单遍历算法PerSVD算法动态位移技术，

提高近似质量用奇异值分解代

替QR做正交化用特征值分解来

加速计算如果p=0，则得

单遍历PCA算法24使用加速技巧的动态位移技术处理硬盘上大的稠密矩阵，达到很好的速度-准确度平衡少遍历与单遍历算法任意流单遍历算法在流数据场景，PerSVD(p=0)假设数据逐行到达，未必成立实际上，可能每次数据更新为任意位置矩阵元素(任意流)Tropp算法:用随机投影建三个草图矩阵[1]JTropp,etal.,“Streaminglow-rankmatrixapproximation...,”SIAMJ.Sci.Comput.,2019

有关应用与发展dashSVD+奇异值门限(SVT)算法，用于矩阵补全利用信息冗余/低秩SVT算法使用dashSVD算法26迭代求解过程：多次截断

奇异值分解SVT+dashSVD

SVT+rSVD-BKI1218在含两个8核IntelXeonCPU@2.10GHz的Ubuntu

服务器上

SVT+svds(算法8)8有关应用与发展randQB_EI与协同过滤结合用于评分估计User/item矩阵A,基于SVD的协同过滤(CF)评分估计:计算item之间相关性,已知数据加权求和隐式因子个数k如何自动选取?randQB_EI算法+验证集数据稀疏矩阵rSVD的加速技巧测试结果接近最优,计算量非常小27(item隐式因子矩阵)最优有关应用与发展超大规模网络的嵌入(networkembedding)NetMF算法核心挑战在于第2、第3步Tropp算法+sparse-sign随机嵌入可以实现不构建M矩阵，

将计算复杂度降为线性(对节点数n、边数m)实验结果:对网络Hyperlink2012(3.5B节点、225B边),在仅含CPU的单机上仅需1小时即完成嵌入，得到高质量边预测28非负矩阵分解非负矩阵分解交替非负最小二乘算法基于乘法的算法算法改进技巧29非负矩阵分解

30(由于正交性)

(D为对角元为正数的对角阵)像基于聚类的低秩近似，但不同非负矩阵分解ANLS算法(Alternatingnonnegativeleastsquares)无法保证得到全局最优计算速度慢前述例子：

用lsqnonneg解非负最小二乘(变种:做无约束LLS,再将解中负数置0)0.340900.176500.17650