大数据应用-基于大数据的推荐算法研究13886.pptx

《大数据应用-基于大数据的推荐算法研究13886.pptx》由会员分享，可在线阅读，更多相关《大数据应用-基于大数据的推荐算法研究13886.pptx（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基于大数据的推荐算法研究基于大数据的推荐算法研究 论文框架论文框架 2 2TopKS算法3 3基于项目层次结构相似性的推荐算法4 4矩阵分解并行化5 5总结与展望1 1课题背景与研究意义图书推荐图书推荐新闻推荐亚马逊亚马逊当当当当网网淘淘宝宝网网央广网央广网课题背景l启发式的协同过滤 代表的方法：KNNl基于模型的协同协同过滤 代表的方法：矩阵分解课题背景l余弦距离l皮尔逊相关系数luser1(3,2,?,4)user2(2,3,?,?)user3(?,?,4,3)user4(4,?,?,1)user5(?,5,5,?)课题背景.X21*y21+x22*y22+x23*y23 3u2v2.=l

2、交替下降l梯度下降研究意义l用户量猛增l项目（商品、新闻等）数量猛增l推荐算法的可扩展性不强TopkS算法l采用余弦距离和皮尔逊相关公式累加性特点l引入倒排索引数据结构l结合TopK思想TopKS是Top K Similarity的简写，即最大的前K个相似度。主要包含以下三部分：TopkS算法余弦距离余弦距离皮尔逊相关系数皮尔逊相关系数TopkS算法倒排索引倒排索引TopkS算法计算u1和其他用户的相似度 TopkS算法 假设查找用户ui的最近邻用户，当前计算到用户ui和uj第k1个共同项目（i!=j），而ui和uj有k个共同评分项目,则分为两种情况：1.如果uj已经在最近邻列表LS中，则直接

3、更新列表中的相似度；2.如果uj不在最近邻列表LS中，则计算用户ui和uj可能的最大值，下面是余弦距离和皮尔逊相关系数可能的最大值：余弦距离TopkS算法皮尔逊相关系数计算出 之后，是从LS中剔除最小值，插入uj把uj加入黑名单否TopkS算法不同稀疏度对近邻计算的影响 TopkS算法不同规模用户数量上的比较实验 TopkS算法不同K值对执行时间的影响 基于项目层次结构相似性的推荐算法基于项目层次结构相似性的推荐算法相似度度量节点之间的距离度量：然后利用最短路径算法Dijkstra结合TopK思想找到最相近的项目；基于项目层次结构相似性的推荐算法三种算法效果对比矩阵分解并行化目标函数采用梯度下

4、降方法，V的更新公式通常是：这里注意：是一个常数，对因子矩阵中的每个元素都一样矩阵分解并行化同理，用户因子矩阵U也可以近似为矩阵乘除的形式.,V的更新公式变为：这里 把步长修改为因子矩阵中每个元素一个值，如下：矩阵分解并行化MapReduce编程模型程模型矩阵分解并行化a11a12a13a21a22a23a31a32a33a41a42a43左矩左矩阵Ab11b12b13b14b21b22b23b24b31b32b33b34右矩右矩阵B1.内内积法法2.外外积法法3.分分块矩矩阵乘法乘法c11c12c13c14c21c22c23c24c31c32c33c34c41c42c43c44结果矩果矩阵C

5、C=AB介介绍矩矩阵的分布式乘法的分布式乘法时，假，假设：左矩左矩阵A是是ms右矩右矩阵B是是sn结果矩果矩阵C是是mn矩阵分解并行化.内内积法法矩阵分解并行化内积法数据流程图内积法数据流程图 内积法中内积法中Reduce任务与数据的对应关系任务与数据的对应关系注：R_i_j表示Reduce任务的编号并并发粒度：粒度：mns中中间shuffle数数据量：据量：n个个A矩矩阵，m个个B矩矩阵，即，即2s个个C矩矩阵矩阵分解并行化+=外外积法法矩阵分解并行化外积法数据流程图外积法数据流程图 外积法中外积法中Reduce任务与数据的对应关系任务与数据的对应关系注：R_i_j表示Reduce任务的编号

6、并并发粒度：粒度：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 并并发粒度：粒度：MNS中中间数数据量：据量：N个个A矩矩阵和和M个个B矩矩阵矩阵分解并行化矩阵规模与运行时间的关系矩阵规模与运行时间的关系 矩阵分解并行化矩阵稀疏度与运行时间的关系矩阵稀疏度与运行时间的关系矩阵分解并行化分块策略与运行时间的关系分块策略与运行时间的关系分块策略与中间数据量的大小关系分块策略与中间数据量的大小关系 矩阵分解并行化工作节点数量与运行时间的关系工作节点数量与运行时间的关系 总结与展望本文工作1.对传统的相似度度量方法进行改进 2.提出基于项目标签层次结构的相似度度量方法3.矩阵分解算法并行化未来展望1.利用MPI分布式模型并行化矩阵分解模型；2.实现通过构造传统推荐算法的近似算法把传统推荐算法并行化谢谢!