[原]Mahout 协同过滤 itemBase RecommenderJob源码分析

标签: | 发表时间:2013-02-26 03:19 | 作者:HEYUTAO007
出处:http://blog.csdn.net/heyutao007
Mahout支持2种 M/R 的jobs实现itemBase的协同过滤
I.ItemSimilarityJob
II.RecommenderJob

下面我们对RecommenderJob进行分析,版本是mahout-distribution-0.7

源码包位置:org.apache.mahout.cf.taste.hadoop.item.RecommenderJob


RecommenderJob前几个阶段和ItemSimilarityJob是一样的,不过ItemSimilarityJob 计算出item的相似度矩阵就结束了,而RecommenderJob 会继续使用相似度矩阵,对每个user计算出应该推荐给他的top N 个items。RecommenderJob 的输入也是userID, itemID[, preferencevalue]格式的。JobRecommenderJob主要由以下一系列的Job组成:


1 PreparePreferenceMatrixJob(同ItemSimilarityJob)
输入: (userId, itemId, pref) 
1.1 itemIDIndex 将Long型的itemID转成一个int型的index
1.2 toUserVectors 将输入的 (userId, itemId, pref) 转成user向量 USER_VECTORS (userId, VectorWritable<itemId, pref>)
1.3 toItemVectors 使用 USER_VECTORS  构建item向量 RATING_MATRIX (itemId,VectorWritable<userId,pref>)


2 RowSimilarityJob(同ItemSimilarityJob)
2.1 normsAndTranspose

计算每个item的norm,并转成user向量
输入:RATING_MATRIX 
(1)使用similarity.normalize处理每个item向量,使用similarity.norm计算每个item的norm,写到hdfs;
(2)根据item向量进行转置,即输入:item-(user,pref),输出:user-(item,pref)。这一步的目的是将同一个user喜欢的item对找出来,因为只有两个item有相同的user喜欢,我们才认为它们是相交的,下面才有对它们计算相似度的必要。


2.2 pairwiseSimilarity
计算item对之间的相似度
输入:2.1(2)计算出的user向量user-(item,pref)
map:CooccurrencesMapper
使用一个两层循环,对user向量中两两item,以itemM为key,所有itemM之后的itemN与 itemM的similarity.aggregate计算值组成的向量为value。
reduce:SimilarityReducer
(1)叠加相同的两个item在不同用户之间的aggregate值,得到itemM-(( item M+1,  aggregate M+1),( item M+2,  aggregate M+2),( item M+3,  aggregate M+3)。。。)
(2)然后计算itemM和之后所有item之间的相似度。相似度计算使用similarity.similarity,第一个参数是两个item的aggregate值,后两个参数是两个item的norm值,norm值在上一个Job已经得到。结果是以itemM为key,所有itemM之后的itemN与 itemM 相似度组成的向量为value,即itemM-(( item M+1,  simi M+1),( item M+2,   simi   M+2),( item M+3,   simi  M+ 3)。。。)
到这里我们实际上是得到了相似度矩阵的斜半部分。


2.3 asMatrix
构造完整的相似度矩阵(上面得到的只是一个斜半部分)
输入:2.2reduce(2)输出的以itemM为key,所有itemM之后的itemN与之相似度组成的向量
map:UnsymmetrifyMapper
(1)反转,根据item M-(item M+1,simiM+1)记录item M+1 -(item M,simiM+1)
(2)使用一个优先队列求出itemM的top maxSimilaritiesPerRow(可设置参数)个相似item,比如maxSimilaritiesPerRow =2时,可能输出
itemM-(( item M+1,  simi M+1),( item M+3,   simi   M+3))
reduce:MergeToTopKSimilaritiesReducer
(1)对相同的item M,合并上面两种向量,这样就形成了完整的相似度矩阵,itemM-(( item 1,  simi 1),( item 2,   simi   2))。。。,( item N,   simi   N))。
(2)使用Vectors.topKElements对每个item求top maxSimilaritiesPerRow(可设置参数)个相似item。可见map(2)中的求topN是对这一步的一个预先优化。
最终输出的是itemM-(( item A,  simi A),( item B,   simi   B))。。。,( item N,   simi   N)),A到N的个数是maxSimilaritiesPerRow。
至此RowSimilarityJob结束。下面就进入了和ItemSimilarityJob不同的地方。


3 prePartialMultiply1 + prePartialMultiply2 + partialMultiply
这三个job的工作是将1.2生成的user向量和2.3reduce(2)生成的相似度矩阵使用相同的item作为key聚合到一起,实际上是为下面会提到的矩阵乘法做准备。VectorOrPrefWritable是两种value的统一结构,它包含了相似度矩阵中某个item的一列和user向量中对应这个item的(userID,  prefValue )。


public final class VectorOrPrefWritable implements Writable {
  private Vector vector;
  private long userID;
  private float value;
}


下面依次介绍:
3.1 prePartialMultiply1 
输入:2.3reduce(2)生成的相似度矩阵。
以item为key,相似度矩阵的一行包装成一个VectorOrPrefWritable为value。矩阵相乘应该使用列,但是对于相似度矩阵,行和列是一样的。


3.2 prePartialMultiply2
输入:1.2生成的USER_VECTORS
对user,以每个item为key,userID和对应这个item的prefValue包装成一个VectorOrPrefWritable为value。


3.3 partialMultiply 
以3.1和3.2的输出为输入,聚合到一起,生成item为key,VectorAndPrefsWritable为value为value。VectorAndPrefsWritable包含了相似度矩阵中某个item一列和一个List<Long> userIDs,一个List<Float> values。


public final class VectorAndPrefsWritable implements Writable {
  private Vector vector;
  private List<Long> userIDs;
  private List<Float> values;
}




4 itemFiltering
用户设置过滤某些user,需要将user/item pairs也转成(itemID,VectorAndPrefsWritable)形式


5 aggregateAndRecommend
一切就绪后,下面就开始计算推荐向量了。推荐计算公式如下:
Prediction(u,i) = sum(all n from N: similarity(i,n) * rating(u,n)) / sum(all n from N: abs(similarity(i,n)))
u = a user
i = an item not yet rated by u
N = all items similar to i
可以看到,分子部分就是一个相似度矩阵和user向量的矩阵乘法。对于这个矩阵乘法,实现代码和传统的矩阵乘法不一样,其伪代码:


assign R to be the zero vector
for each column i in the co-occurrence matrix
multiply column vector i by the ith element of the user vector
add this vector to R


假设相似度矩阵的大小是N,则以上代码实际上是对某个user的所有item,将这个item在相似度矩阵中对应列和user对这个item的prefValue相乘,得到N个向量后,再将这些向量相加,就得到了针对这个用户的N个item的推荐向量。要实现这些,首先要把某个user对所有item的prefValue以及这个item在相似度矩阵中对应列聚合到一起。下面看实现:
输入:3.3和4的输出
map:PartialMultiplyMapper 
将(itemID,VectorAndPrefsWritable)形式转成以userID为key,PrefAndSimilarityColumnWritable为value。PrefAndSimilarityColumnWritable包含了这个user对一个item的prefValue和item在相似度矩阵中的那列,其实还是使用的VectorAndPrefsWritable中的vector和value。


public final class PrefAndSimilarityColumnWritable implements Writable {
  private float prefValue;
  private Vector similarityColumn;
}



reduce:AggregateAndRecommendReducer
收集到属于这个user的所有 PrefAndSimilarityColumnWritable 后,下面就是进行矩阵相乘的工作。
根据是否设置booleanData,有以下两种操作:
(1)reduceBooleanData
只是单纯的将所有的PrefAndSimilarityColumnWritable 中的SimilarityColumn相加,没有用到item-pref。
(2)reduceNonBooleanData
用到item-pref的计算方法,
分子部分,是矩阵相乘的结果,根据上面的伪代码,它是将每个PrefAndSimilarityColumnWritable 中的SimilarityColumn和 prefValue 的相乘,生成多个向量后再将这些向量相加;而分母是所有的SimilarityColumn和。下面看代码:

代码:


for (PrefAndSimilarityColumnWritable prefAndSimilarityColumn : values) {
      Vector simColumn = prefAndSimilarityColumn.getSimilarityColumn();
      float prefValue = prefAndSimilarityColumn.getPrefValue();




      //分子部分,每个SimilarityColumn和item-pref的乘积生成多个向量,然后将这些向量相加
      numerators = numerators == null
          ? prefValue == BOOLEAN_PREF_VALUE ? simColumn.clone() : simColumn.times(prefValue)
          : numerators.plus(prefValue == BOOLEAN_PREF_VALUE ? simColumn : simColumn.times(prefValue));


      simColumn.assign(ABSOLUTE_VALUES);
      //分母是所有的SimilarityColumn和
      denominators = denominators == null ? simColumn : denominators.plus(simColumn);
    }


两者相除,就得到了反映推荐可能性的数值。
之后还会使用writeRecommendedItems使用一个优先队列取top推荐,并且将index转成真正的itemID,最终完成。


在以上分析中,similarity是一个VectorSimilarityMeasure接口实现,它是一个相似度算法接口,主要方法有:
(1)Vector normalize(Vector vector);
(2)double norm(Vector vector);
(3)double aggregate(double nonZeroValueA, double nonZeroValueB);
(4)double similarity(double summedAggregations, double normA, double normB, int numberOfColumns);
(5)boolean consider(int numNonZeroEntriesA, int numNonZeroEntriesB, double maxValueA, double maxValueB,
      double threshold);
众多的相似度算法就是实现了这个接口,比如TanimotoCoefficientSimilarity的similarity实现就是:
public double similarity(double dots, double normA, double normB, int numberOfColumns) {
    return dots / (normA + normB - dots);
}

作者:HEYUTAO007 发表于2013-2-26 11:19:05 原文链接
阅读:389 评论:0 查看评论

相关 [mahout 协同过滤 itembase] 推荐:

[原]Mahout 协同过滤 itemBase RecommenderJob源码分析

- -
Mahout支持2种 M/R 的jobs实现itemBase的协同过滤. 下面我们对RecommenderJob进行分析,版本是mahout-distribution-0.7. 源码包位置:org.apache.mahout.cf.taste.hadoop.item.RecommenderJob. RecommenderJob前几个阶段和ItemSimilarityJob是一样的,不过ItemSimilarityJob 计算出item的相似度矩阵就结束了,而RecommenderJob 会继续使用相似度矩阵,对每个user计算出应该推荐给他的top N 个items.

使用Mahout实现协同过滤 spark

- - zzm
Mahout使用了Taste来提高协同过滤算法的实现,它是一个基于Java实现的可扩展的,高效的推荐引擎. Taste既实现了最基本的基 于用户的和基于内容的推荐算法,同时也提供了扩展接口,使用户可以方便的定义和实现自己的推荐算法. 同时,Taste不仅仅只适用于Java应用程序,它 可以作为内部服务器的一个组件以HTTP和Web Service的形式向外界提供推荐的逻辑.

协同过滤算法

- - CSDN博客推荐文章
今天要讲的主要内容是 协同过滤,即Collaborative Filtering,简称 CF.    关于协同过滤的一个最经典的例子就是看电影,有时候不知道哪一部电影是我们喜欢的或者评分比较高的,那.    么通常的做法就是问问周围的朋友,看看最近有什么好的电影推荐. 在问的时候,都习惯于问跟自己口味差不.

协同过滤 Collaborative Filtering

- - IT技术博客大学习
   协同过滤算法是推荐系统中最古老,也是最简单高效的推荐算法. 简单说协同过滤就是根据以往的用户产生的数据分析,对用户的新行为进行匹配分析来给用户推荐用户最有可能感兴趣的内容.    协同过滤算法是为了解决 长尾现象,也就是说推荐系统是为了解决长尾现象而诞生的. 因为在之前在有限的空间(如:书店的书架、服装店的衣架、商店的货架、网页的展示区域)只能摆有限的物品进行展示,造成大量的非热门物品很难进入人们的视野,也就无法产生任何价值.

协同过滤和推荐引擎

- - 刘思喆@贝吉塔行星
推荐系统在个性化领域有着广泛的应用,从技术上讲涉及概率、抽样、最优化、机器学习、数据挖掘、搜索引擎、自然语言处理等多个领域. 东西太多,我也不准备写连载,今天仅从基本算法这个很小的切入点来聊聊推荐引擎的原理. 推荐引擎(系统)从不同的角度看有不同的划分,比如:. 按照数据的分类:协同过滤、内容过滤、社会化过滤.

Spark MLlib中的协同过滤

- - JavaChen Blog
本文主要通过Spark官方的例子理解ALS协同过滤算法的原理和编码过程,然后通过对电影进行推荐来熟悉一个完整的推荐过程. 协同过滤常被应用于推荐系统,旨在补充用户-商品关联矩阵中所缺失的部分. MLlib当前支持基于模型的协同过滤,其中用户和商品通过一小组隐语义因子进行表达,并且这些因子也用于预测缺失的元素.

Mahout介绍

- - 互联网 - ITeye博客
Mahout 是机器学习和数据挖掘的一个分布式框架,区别于其他的开源数据挖掘软件,它是基于hadoop之上的; 所以hadoop的优势就是Mahout的优势. http://mahout.apache.org/ 上说的Scalable就是指hadoop的可扩展性. Mahout用map-reduce实现了部分数据挖掘算法,解决了并行挖掘的问题.

mahout部署实践

- - CSDN博客云计算推荐文章
一 下载mahout并解压. JAVA_HOME mahout运行需指定jdk的目录. MAHOUT_JAVA_HOME指定此变量可覆盖JAVA_HOME值. HADOOP_HOME  如果配置,则在hadoop分布式平台上运行,否则单机运行. HADOOP_CONF_DIR指定hadoop的配置文件目录.

Amazon.com的推荐:从商品到商品的协同过滤

- 小和尚 - 互联网的那点事
以下全文翻译的PDF点此下载. Amazon.com 的推荐. 推荐算法以其在电子商务网站的用途而著称1,它们利用有关一个顾客的兴趣作为输入,来产生一个推荐商品的列表. 很多应用仅仅使用顾客购买并明确表示代表其兴趣的商品,但它们也可以利用其他属性,包括已浏览的商品、人口统计特征数据、主题兴趣,以及偏爱的艺术家.