数据仓库与项目管理

基于大数据的推荐算法研究论文框架2TopKS算法3基于项目层次结构相似性的推荐算法4矩阵分解并行化5总结与展望1课题背景与研究意义图书推荐新闻推荐亚马逊当当网淘宝网央广网课题背景启发式的协同过滤代表的方法：KNN基于模型的协同协同过滤代表的方法：矩阵分解课题背景余弦距离皮尔逊相关系数………user1(3,2,?,4)user2(2,3,?,?)user3(?,?,4,3)user4(4,?,?,1)user5(?,5,5,?),,,,eiejeijeieRR课题背景≈.X21*y21+x22*y22+x23*y23≈3u2v2.=2,min()ijijijfruv交替下降梯度下降22||||||||uivjuv研究意义用户量猛增项目（商品、新闻等）数量猛增推荐算法的可扩展性不强TopkS算法采用余弦距离和皮尔逊相关公式累加性特点引入倒排索引数据结构结合TopK思想TopKS是TopKSimilarity的简写，即最大的前K个相似度。主要包含以下三部分：22,,sim(,)||||||||ijiji,sj,ssRijijikjkkRkRrruuijuurrTopkS算法余弦距离皮尔逊相关系数,,22,,()()sim(,)()()ijijisijsjsSikijkjkRkRrrrrijrrrrmaxmax22,,ijijsRikjkkRkRrrrrmaxmax22,,()()()()ijijijsRikijkjkRkRrrrrrrrrTopkS算法u1u3u2u4u5v13v224v4v12v23v34v43v14v41v25v35倒排索引v1v3v2v4u13u224u4u12u23u34u55u14u335u51u4TopkS算法u1u3u2u4u5v13v224v4v12v23v34v43v14v41v25v35v1v3v2v4u13u224u4u12u23u34u55u14u335u51u4计算u1和其他用户的相似度u1v13v224v4v1u13u224u4v2u12u235u5TopkS算法假设查找用户ui的最近邻用户，当前计算到用户ui和uj第k1个共同项目（i!=j），而ui和uj有k个共同评分项目,则分为两种情况：1.如果uj已经在最近邻列表LS中，则直接更新列表中的相似度；2.如果uj不在最近邻列表LS中，则计算用户ui和uj可能的最大值，下面是余弦距离和皮尔逊相关系数可能的最大值：余弦距离2max_11_22,,(kk1)ijijijkij_kmaxikjkkRkRrsimsimsimrrTopkS算法_k1_maxijsimmaxmax_1_k1_max22,,(kk1)()()()()ijijijijkijikijkjkRkRrrrrsimsimsimrrrr皮尔逊相关系数计算出之后，_k1_max_ijsimLSminmum是从LS中剔除最小值，插入uj把uj加入黑名单否TopkS算法不同稀疏度对近邻计算的影响TopkS算法不同规模用户数量上的比较实验TopkS算法不同K值对执行时间的影响基于项目层次结构相似性的推荐算法歌曲专辑歌手风格ajihbgfedcmlk基于项目层次结构相似性的推荐算法相似度度量1212(,)1/min(,,)psimccwtcpc()1wt(,)((1))()()()(,)()()EdpcpICcICpTcpEpdp节点之间的距离度量：然后利用最短路径算法Dijkstra结合TopK思想找到最相近的项目；基于项目层次结构相似性的推荐算法三种算法效果对比矩阵分解并行化目标函数RjijiijVUvurf),(2,)(minarg采用梯度下降方法，V的更新公式通常是：/*/iiiVVfV这里()ijijiiifruvuV注意：是一个常数，对因子矩阵中的每个元素都一样矩阵分解并行化])()[(ijTijTijijijUVUURVVUVUURVVTTjij同理，用户因子矩阵U也可以近似为矩阵乘除的形式.,V的更新公式变为：UVUVT这里把步长修改为因子矩阵中每个元素一个值，如下：矩阵分解并行化MapReduce编程模型矩阵分解并行化a11a12a13a21a22a23a31a32a33a41a42a43左矩阵Ab11b12b13b14b21b22b23b24b31b32b33b34右矩阵B1.内积法2.外积法3.分块矩阵乘法c11c12c13c14c21c22c23c24c31c32c33c34c41c42c43c44结果矩阵CC=AB介绍矩阵的分布式乘法时，假设：左矩阵A是m×s右矩阵B是s×n结果矩阵C是m×n矩阵分解并行化a13a12a11a13a12a11b31b21b11b31b21b11.=c11=a11*b11+a12*b21+a13*b31a13a12a11a13a12a11b32b22b12b32b22b12.=c12=a11*b12+a12*b22+a13*b32ai3ai2ai1ai3ai2ai1b3jb2jb1jb3jb2jb1j.=cij=ai1*b1j+ai2*b2j+ai3*b3ja43a42a41a43a42a41b34b24b14b34b24b14.=c44=a41*b14+a42*b24+a43*b34….….31ijckkjikba内积法矩阵分解并行化i,Tiaj,jbMapReduce[i,1],Tia[i,2],Tia…[i,n],Tia[1,j],…1b[2,j],1b…[m,j],1bShuffle[1,1],],[11baT[1,2],],[21baT…[1,n],],[1nTba[2,1],],[12baT[2,2],],[22baT…[m,n],],[nTmba[1,1],11c[1,2],12c…[1,n],nc1[2,1],21c[2,2],22c…[m,n],mncBA1b2b…nbTa1Ta2…TmaR_1_1R_1_2…R_1_nR_m_1R_m_2…R_m_nR_2_1R_2_2…R_2_n…………内积法数据流程图内积法中Reduce任务与数据的对应关系注：R_i_j表示Reduce任务的编号并发粒度：m×n×s中间shuffle数据量：n个A矩阵，m个B矩阵，即2s个C矩阵矩阵分解并行化a41a31a21a11a41a31a21a11b14b13b12b11b14b13b12b11×=a41*b14a41*b13a41*b12a41*b11a31*b14a31*b13a31*b12a31*b11a21*b14a21*b13a21*b12a21*b11a11*b14a11*b13a11*b12a11*b11a41*b14a41*b13a41*b12a41*b11a31*b14a31*b13a31*b12a31*b11a21*b14a21*b13a21*b12a21*b11a11*b14a11*b13a11*b12a11*b11a42a32a22a12a42a32a22a12b24b23b22b21b24b23b22b21×=a42*b24a42*b23a42*b22a42*b21a32*b24a32*b23a32*b22a32*b21a22*b24a22*b23a22*b22a22*b21a12*b24a12*b23a12*b22a12*b21a42*b24a42*b23a42*b22a42*b21a32*b24a32*b23a32*b22a32*b21a22*b24a22*b23a22*b22a22*b21a12*b24a12*b23a12*b22a12*b21a43a33a23a13a43a33a23a13b34b33b32b31b34b33b32b31×=a43*b34a43*b33a43*b32a43*b31a33*b34a33*b33a33*b32a33*b31a23*b34a23*b33a23*b32a23*b31a13*b34a13*b33a13*b32a13*b31a43*b34a43*b33a43*b32a43*b31a33*b34a33*b33a33*b32a33*b31a23*b34a23*b33a23*b32a23*b31a13*b34a13*b33a13*b32a13*b31++=a41*b14+a42*b24+a43*b34a41*b13+a42*b23+a43*b33a41*b12+a42*b22+a43*b32a41*b11+a42*b21+a43*b31a31*b14+a22*b24+a33*b34a31*b13+a32*b23+a33*b33a31*b12+a32*b22+a33*b32a31*b11+a32*b21+a33*b31a21*b14+a22*b24+a23*b34a21*b13+a22*b23+a23*b33a21*b12+a22*b22+a23*b32a21*b11+a22*b21+a23*b31a11*b14+a12*b24+a13*b34a11*b13+a12*b23+a13*b33a11*b12+a12*b22+a13*b32a11*b11+a12*b21+a13*b31a41*b14+a42*b24+a43*b34a41*b13+a42*b23+a43*b33a41*b12+a42*b22+a43*b32a41*b11+a42*b21+a43*b31a31*b14+a22*b24+a33*b34a31*b13+a32*b23+a33*b33a31*b12+a32*b22+a33*b32a31*b11+a32*b21+a33*b31a21*b14+a22*b24+a23*b34a21*b13+a22*b23+a23*b33a21*b12+a22*b22+a23*b32a21*b11+a22*b21+a23*b31a11*b14+a12*b24+a13*b34a11*b13+a12*b23+a13*b33a11*b12+a12*b22+a13*b32a11*b11+a12*b21+a13*b31外积法矩阵分解并行化BATb1Tb2…Tsb1a2a…saR_1_1R_s_sR_2_2…i,iaj,TjbMapReduceShuffle1,],[11Tba2,],[22Tba…3,],[33Tbas,],[Tssbai,iaj,TjbMap1,],[11Tba2,],[22Tba…3,],[33Tbas,],[TssbaShuffle,...],...,[...,,1/1/1TjTicc…,...],...,[...,,2/2/2TjTicc,...],...,[...,,3/3/3TjTicc,...],...,[...,,//TmjTmiccm/,Tixci/,Tjxcj………/,TmscmReduce1,Tc12,Tc2…3,Tc3m,TmcJob1Job2外积法数据流程图外积法中Reduce任务与数据的对应关系注：R_i_j表示Reduce任务的编号并发粒度：s中间数据量：Job1的shuffle数据量：一个A矩阵和一个B矩阵Job1到Job2的IO数据量：s个C矩阵Job2的shuffle数据量：远小于s个C矩阵矩阵分解并行化把左矩阵划分为m1×s1等大小的矩阵，右矩阵划分为s1×n1的等大小矩阵，则有：A=…......…11A1AMS1AMSAB=…......…11B1SBN1BSNBM=(m-1)/m1+1S=(s-1)/s1+1N=(n-1)/n1+1NjMiBASkkjik,C1ij其中并发粒度：M×N×S中间数据量：N个A矩阵和M个B矩阵矩阵分解并行化33.540246矩阵维数(log10)运行时间(log10)单机算法分块法矩阵规模与运行时间的关系矩阵分解并行化矩阵稀疏度与运行