Apache Mahout基于商品的协同过滤算法流程分析

最近使用mahout的itemBase协同过滤算法，研究了下他的源码，记录如下，以备后忘……

其算法实现大致分四个主要的部分：

1.将输入数据转化成矩阵

2.计算相似性

3.还是转化数据格式，为计算预测、推荐做准备

4.预测评分并做推荐

下面分别详细介绍：

1. PreparePreferenceMatrixJob

1.1 itemIDIndex

input：启动计算时指定的--input路径 output：***/preparePreferenceMatrix/itemIDIndex

mapper:ItemIdIndexMapper,将输入中的userID，itemID，pref分隔后，将Long型itemID转化成int型 的index。输出类型(new VarIntWritable(index), new VarLongWritable(itemID));

reducer：ItemIDIndexReducer,index为key聚合itemID取出最小的itemID输出。输出类型同mapper

1.2 toUserVectors

input：启动计算时指定的--input路径 output：***/preparePreferenceMatrix/userVectors

mapper:ToEntityPrefsMapper,输出类型(new VarLongWritable(userID), new EntityPrefWritable(itemID, prefValue))

reducer:ToUserVectorsReducer,将map输出中的itemID转成index，通过userID聚合<itemID，pref>，输出类型:VarLongWritable,VectorWritable

注：在此job的reducer中会累加计数user的数量到一个变量中。然后在此job完成后将用户数写到numUsers.bin中，便于后续job读取用户数。

1.3 toItemVectors

input：1.2的输出 output：***/preparePreferenceMatrix/ratingMatrix

mapper：ToItemVectorsMapper，将1.2中<userID,VectorWritable<index,pref>……>,遍历Vector输出成<index,VectorWritable<userID,pref>……>

reducer:ToItemVectorsReducer,由于map中key是不知道是不是到下一个key的，所以map中写文件的方式是map中每一个userID（是key）的每个评分（是VectorWritable）都写一次，并以index作为key，并将此时的userID,pref给set到Vector中这样同一个index中的vector在reduce聚合到一起中必有重复的，所以此处reduce就是做merge的。

至此准备工作就已经完成了

2. 计算相似度RowSimilarityJob

2.1 normsAndTranspose

input：1.3的输出(***/preparePreferenceMatrix/ratingMatrix) output：***/weights

mapper:VectorNormMapper,将ratingMatrix中的<itemID,<userID,pref>……>形式的数据，再转化成<userID,<itemID,pref>……>的形式，同时记录每个item的norms（double类型，如欧氏距离的话就是平方和），如果需要过滤最小评分的话会记录item的评分数量和最大评分。最后将norms，nonZeroEntries，maxValues输出

reducer：MergeVectorsReducer

同1.3mapper中输出的vector会有重复的，在此进行merge输出，并将map中norms，nonZeroEntries，maxValues的输出写入相应的hdfs文件中。

这个job同时有一个MergeVectorsCombiner，只是为了merge的。

2.2 pairwiseSimilarity

input：2.1的输出(***/weights) output：***/pairwiseSimilarity

mapper：CooccurrencesMapper

由于2.1的输出是<userID,<itemID,pref>……>形式的，所以一个人同时对某两个商品的评分就很容易得到，so，两个循环遍历每个用户的评分列表，计算评分商品两两间的相似（多种相似度算法），输出：<itemID,<itemID,aggregateValue>……> (aggregateValue取的是乘积，[X1-X2]2=X1²-2*X1X₂+X2²，此处计算乘积是为了便于reducer计算两两之间的相似度）

reducer：SimilarityReducer

同样是先mager，但么有调用Vectors中的方法，而是从新写了一个不知道为什么？

然后调用相应的相似度算法计算两两之间的相似度，以欧氏距离为例（较简单）会调用norms中计算好的平方和。输出为两两间的相似度<itemID,<itemID,pref>……>

2.3 asMatrix

input：2.2的输出(***/pairwiseSimilarity) output：***/similarityMatrix

mapper:UnsymmetrifyMapper

2.2中输出的两两之间的相似度，此处取出topK个输出，但这只是整个相似度矩阵的一半，所以需要输出另一半，在此是和上面的一样，每一个item都会输出一个vector出来，这样reducer必要做merge，当然另一半是输出全部的，topK要到reducermerge后做。

reducer：MergeToTopKSimilaritiesReducer

同mapper中所说，此处完成merge和取topK，实际上就一半的矩阵需要处理。

至此相似度就已经算完了

3 下面开始为推荐做准备

3.1 prePartialMultiply1

input：2.3的输出(***/similarityMatrixPath) output：***/prePartialMultiplyPath1

mapper：SimilarityMatrixRowWrapperMapper，直接输出，只是添加了自身的相似度为NAN，输出类型VectorOrPrefWritable，这里是前者Vecotr

reducer：Reducer，hadoop自身的，没啥说的，正常聚合。

3.2 prePartialMultiply2

input：1.2的输出(***/preparePreferenceMatrix/userVectors) output：***/prePartialMultiplyPath2

mapper：UserVectorSplitterMapper

在此只是如果有usersToRecommendFor的话就只输出usersToRecommendFor中的用户的评分向量，没有的话默认是输出全部的用户评分向量。还有过滤下每个用户的评分数量，默认是去10个评分，来预测。

reducer：Reducer，同上

其实prePartialMultiply1和prePartialMultiply2只是将数据稍做处理，然后输出相同的数据类型，这样便于下步将评分数据和item的相似数据聚合。

3.3 partialMultiply

input：3.1和3.2的输出(***/prePartialMultiplyPath1、2) output：***/prePartialMultiplyPath

mapper：Mapper

reducer：ToVectorAndPrefReducer，将聚合在一起的VectorOrPrefsWritable类型，封装成VectorAndPrefsWritable类型。

4 预测并推荐

4.1 itemFiltering 推荐商品过滤

input：启动时指定的路径(***/filterFile) output：***/explicitFilterPath

mapper：ItemFilterMapper

reducer：ItemFilterAsVectorAndPrefsReducer

较简单，只是最后聚合输出成VectorAndPrefsWritable类型，跟3.3保持一致

4.2 aggregateAndRecommend 聚合推荐（关键的一步）

input：3.3的输出(***/prePartialMultiplyPath) output：启动时指定的路径

mapper：PartialMultiplyMapper

VectorAndPrefsWritable保存的是对同一个item评过分的用户的评分及此item的相似矩阵，此map输出以userID为key，以PrefAndSimilarityColumnWritable<pref,simiMartixVactor>类型为value,这样同一个user评过分的商品评分及相似矩阵都可以聚到一起，供reducer做预测评分。

reducer：AggregateAndRecommendReducer

reduce声明了Vector numerators（分子） 和Vector denominators（分母),numerators使用相似向量乘以评分，得到多个向量，再将向量相加得到，denominators是直接将多个评分得到的向量相加得到，预测评分是用numerators/denominators

最后通过writeRecommendedItems(userID, recommendationVector, context)采用优先队列取到topK的推荐数据