基于大数据的推荐算法研究.ppt

1、基于大数据的推荐算法研究,报告人：孙远帅 E-mail : sunyuan_,论文框架,矩阵分解并行化,总结与展望,图书推荐,新闻推荐,亚马逊,当当网,淘宝网,央广网,课题背景,启发式的协同过滤 代表的方法：KNN 基于模型的协同协同过滤 代表的方法：矩阵分解,课题背景,余弦距离 皮尔逊相关系数 ,user1(3, 2, ?, 4) user2(2, 3, ?, ?) user3(?, ?, 4, 3) user4(4, ?, ?, 1) user5(?, 5, 5, ?),课题背景,.,X21*y21 + x22* y22 + x23 * y23 3,u2,v2,.,=,交替下降 梯度下降,

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

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

4、,采用梯度下降方法，V的更新公式通常是：,这里,注意： 是一个常数，对因子矩阵中的每个元素都一样,矩阵分解并行化,同理，用户因子矩阵U也可以近似为矩阵乘除的形式., V的更新公式变为：,这里,把步长修改为因子矩阵中每个元素一个值，如下：,矩阵分解并行化,MapReduce编程模型,矩阵分解并行化,左矩阵A,右矩阵B,内积法 外积法 分块矩阵乘法,结果矩阵C,C = AB,介绍矩阵的分布式乘法时，假设： 左矩阵A是ms 右矩阵B是sn 结果矩阵C是mn,矩阵分解并行化,.,.,内积法,矩阵分解并行化,内积法数据流程图,内积法中Reduce任务与数据的对应关系,注：R_i_j表示Reduce任务的

5、编号,并发粒度：mns 中间shuffle数据量： n个A矩阵，m个B矩阵，即2s个C矩阵,矩阵分解并行化,+,+,=,外积法,矩阵分解并行化,外积法数据流程图,外积法中Reduce任务与数据的对应关系,注：R_i_j表示Reduce任务的编号,并发粒度：s 中间数据量： Job1的shuffle 数据量：一个A矩阵和一个B矩阵 Job1到Job2的IO数据量：s个C矩阵 Job2的shuffle数据量：远小于s个C矩阵,矩阵分解并行化,把左矩阵划分为m1s1等大小的矩阵，右矩阵划分为s1n1的等大小矩阵，则有：,M = (m - 1)/m1 + 1 S = (s - 1)/s1 + 1 N = (n - 1)/n1 + 1,并发粒度：MNS 中间数据量：N个A矩阵和M个B矩阵,矩阵分解并行化,矩阵规模与运行时间的关系,矩阵分解并行化,矩阵稀疏度与运行时间的关系,矩阵分解并行化,分块策略与运行时间的关系,分块策略与中间数据量的大小关系,矩阵分解并行化,工作节点数量与运行时间的关系,总结与展望,本文工作,对传统的相似度度量方法进行改进 提