1、基于大数据的推荐算法研究基于大数据的推荐算法研究 论文框架论文框架 2TopKS算法3基于项目层次结构相似性的推荐算法4矩阵分解并行化5总结与展望1课题背景与研究意义图书推荐图书推荐新闻推荐亚马逊亚马逊当当当当网网淘淘宝宝网网央广网央广网课题背景l启发式的协同过滤 代表的方法：KNNl基于模型的协同协同过滤 代表的方法：矩阵分解课题背景l余弦距离l皮尔逊相关系数luser1(3,2,?,4)user2(2,3,?,?)user3(?,?,4,3)user4(4,?,?,1)user5(?,5,5,?),e ie jei je ieRR课题背景.X21*y21+x22*y22+x23*y23 3
2、u2v2.=2,min()ijiji jfru vl交替下降l梯度下降22|uivjuv研究意义l用户量猛增l项目（商品、新闻等）数量猛增l推荐算法的可扩展性不强TopkS算法l采用余弦距离和皮尔逊相关公式累加性特点l引入倒排索引数据结构l结合TopK思想TopKS是Top K Similarity的简写，即最大的前K个相似度。主要包含以下三部分：22,sim(,)|ijiji,sj,ss Rijiji kj kk Rk Rr ru ui juurr TopkS算法余弦距离余弦距离皮尔逊相关系数皮尔逊相关系数,22,()()sim(,)()()ijiji sij sjs Si kij kjk
3、Rk Rrrrri jrrrr max max22,ijijs Ri kj kk Rk Rrrrrmaxmax22,()()()()ijijijs Ri kij kjk Rk Rrr rrrrrrTopkS算法倒排索引倒排索引TopkS算法计算u1和其他用户的相似度 TopkS算法 假设查找用户ui的最近邻用户，当前计算到用户ui和uj第k1个共同项目（i!=j），而ui和uj有k个共同评分项目,则分为两种情况：如果uj已经在最近邻列表LS中，则直接更新列表中的相似度；如果uj不在最近邻列表LS中，则计算用户ui和uj可能的最大值，下面是余弦距离和皮尔逊相关系数可能的最大值：余弦距离2max_
4、 11_22,(k k1)ijijijkij_kmaxi kj kk Rk RrsimsimsimrrTopkS算法_k1_maxijsimmaxmax_ 1_k1_max22,(k k1)()()()()ijijijij kiji kij kjk Rk Rrr rrsimsimsimrrrr皮尔逊相关系数计算出 之后，_k1_max_ijsimLSminmum是从LS中剔除最小值，插入uj把uj加入黑名单否TopkS算法不同稀疏度对近邻计算的影响 TopkS算法不同规模用户数量上的比较实验 TopkS算法不同K值对执行时间的影响 基于项目层次结构相似性的推荐算法基于项目层次结构相似性的推荐算
5、法相似度度量1212(,)1/min(,)psim c cwt c p c()1wt(,)(1)()()()(,)()()Ed pc pIC cIC pT c pE pd p节点之间的距离度量：然后利用最短路径算法Dijkstra结合TopK思想找到最相近的项目；基于项目层次结构相似性的推荐算法三种算法效果对比矩阵分解并行化目标函数RjijiijVUvurf),(2,)(minarg采用梯度下降方法，V的更新公式通常是：/*/iiiVVfV这里()ijijiiifru v uV 注意：是一个常数，对因子矩阵中的每个元素都一样矩阵分解并行化)()(ijTijTijijijUVUURVVUVUUR
6、VVTTjij同理，用户因子矩阵U也可以近似为矩阵乘除的形式.,V的更新公式变为：UVUVT这里 把步长修改为因子矩阵中每个元素一个值，如下：矩阵分解并行化MapReduce编编程模型程模型矩阵分解并行化a11a12a13a21a22a23a31a32a33a41a42a43左矩左矩阵阵Ab11b12b13b14b21b22b23b24b31b32b33b34右矩右矩阵阵B内积内积法法外外积积法法分分块块矩矩阵阵乘法乘法c11c12c13c14c21c22c23c24c31c32c33c34c41c42c43c44结结果矩果矩阵阵CC=AB介介绍绍矩矩阵阵的分布式乘法的分布式乘法时时，假，假设
7、设：左矩左矩阵阵A是是ms右矩右矩阵阵B是是sn结结果矩果矩阵阵C是是mn矩阵分解并行化.31ijckkjikba内积内积法法矩阵分解并行化内积法数据流程图内积法数据流程图 内积法中内积法中Reduce任务与数据的对应关系任务与数据的对应关系注：R_i_j表示Reduce任务的编号并发并发粒度：粒度：mns中中间间shuffle数数据量：据量：n个个A矩矩阵阵，m个个B矩矩阵阵，即，即2s个个C矩矩阵阵矩阵分解并行化+=外外积积法法矩阵分解并行化外积法数据流程图外积法数据流程图 外积法中外积法中Reduce任务与数据的对应关系任务与数据的对应关系注：R_i_j表示Reduce任务的编号并发并发
8、粒度：粒度：s中中间数间数据量：据量：Job1的的shuffle 数数据量：一据量：一个个A矩矩阵阵和一和一个个B矩矩阵阵Job1到到Job2的的IO数数据量：据量：s个个C矩矩阵阵Job2的的shuffle数数据量：据量：远远小于小于s个个C矩矩阵阵矩阵分解并行化把左矩把左矩阵划阵划分分为为m1s1等大小的矩等大小的矩阵阵，右矩，右矩阵划阵划分分为为s1n1的等大小矩的等大小矩阵阵，则则有有：M=(m-1)/m1+1S=(s-1)/s1+1N=(n-1)/n1+1 NjMiBASkkjik,C1ij其中并发并发粒度：粒度：MNS中中间数间数据量：据量：N个个A矩矩阵阵和和M个个B矩矩阵阵矩阵
9、分解并行化33.540246矩阵维数(log10)运行时间(log10)单机算法分块法矩阵规模与运行时间的关系矩阵规模与运行时间的关系 矩阵分解并行化矩阵稀疏度与运行时间的关系矩阵稀疏度与运行时间的关系矩阵分解并行化分块策略与运行时间的关系分块策略与运行时间的关系分块策略与中间数据量的大小关系分块策略与中间数据量的大小关系 4567681012工作节点数量（个）运行时间(/100)矩阵分解并行化NoImage工作节点数量与运行时间的关系工作节点数量与运行时间的关系 总结与展望本文工作 对传统的相似度度量方法进行改进 提出基于项目标签层次结构的相似度度量方法 矩阵分解算法并行化未来展望 利用MPI分布式模型并行化矩阵分解模型；实现通过构造传统推荐算法的近似算法把传统推荐算法并行化谢谢!
