Apache Mahout之协同过滤原理与实践
Apache Mahout之协同过滤原理与实践
读书时期,选课是令人怀念的,因为自由,学生可以挑选自己喜爱的课程和老师!然而,过程并不是很美好,“系统繁忙,稍后重试!”屡有发生,于是大伙开心地约定今夜不战不休。西门的七彩路,和网吧名一样,我们从门口路过,进的却是右旁的可媛。这里网页同样坚持“系统繁忙,稍后重试!”!去的人多了,也就组了局。痛并快乐着应该如此!那以后,我们这堆人中出了一批又一批的高手,操作极限,走位妖娆,那都不是事儿!
戏后,一场深思悄然浮现:如果系统可以收罗大量数据,如学生性格特征、性别籍贯、课程成绩、兴趣爱好、喜爱书籍、历史课表等等,然后消化这些数据原料,最后为每个学生呈现一份个性化的定制课表!多么美好!譬如,对于经常清晨借阅或阅读历史书籍的L,就可以推荐G老师上午时间讲授的《清帝漫谈》课程,对L来说,学习效果更佳!
如今,智能推荐无所不在。在亚马逊买过书籍的朋友,可能会注意到,当在网站上买过几次书籍后,下次再次购买一些新书籍时,网站会主动推荐一些你可能感兴趣的书籍,等你来购!
当然,应用比较广泛的推荐方法之一便是协同过滤(Collaborative Filter,简称CF)。今天,就和大家一起来揭秘她的神秘面纱。
一、什么是协同过滤
协同过滤基于的基本思想:如果用户在过去有相同的偏好(比如他们浏览了相同的网页信息或买过相同的书),那么他们在未来也会有相似的偏好(所谓江山易改,本性难移)。例如,如果用户A和用户B过去都购买过书籍a、b和c,而且用户A最近新买了一本用户B还不知道的书籍d,如表所示:
用户 |
书籍 |
|||
A |
a |
b |
c |
d |
B |
a |
b |
c |
? |
那么我们基本的逻辑是向B推荐书籍d。而且我们还能看到用户A和用户B可能会成为很好的朋友。当然,如果他们性别相异,年龄相当,我推荐他们考虑建立成恋爱关系(具有相似偏好的人成为恋人的成功率更高,更何况他们看的书籍都那么的一致)。
向用户B推荐可能感兴趣的书籍涉及从大量的书籍集合中过滤出用户B最可能感兴趣的书籍,而且用户A和用户B的这种关系是一种协同,所以称为协同过滤。
二、如何寻找与当前用户具有相似偏好的用户
1、用户相似度度量
假设数据库中存储了用户-物品-评分的数据alice.txt,格式如下:
1,101,5 1,102,3 1,103,4 1,104,4 2,101,3 2,102,1 2,103,2 2,104,3 2,105,3 3,101,4 3,102,3 3,103,4 3,104,3 3,105,5 4,101,3 4,102,3 4,103,1 4,104,5 4,105,4 5,101,1 5,102,5 5,103,5 5,104,2 5,105,1
第一列表示用户ID={1,2,3,4,5},
第二列表示物品ID={101,102,103,104,105},
第三列表示用户给物品的评分Score={1,2,3,4,5},
例如第一行数据表示的含义是用户1给物品101的评分是5(最高分)。然而,数据库有时只存储了某个用户交易了某个物品,或者浏览过某个物品,或者收藏过某个物品,我们通过这些数据同样可以计算出用户-物品-评分数据。为了清晰,我们将用户-物品-评分数据转换成用户-物品-评分矩阵(本例是5*5大小的矩阵),如下表:
用户/物品 |
101 |
102 |
103 |
104 |
105 |
1 |
5 |
3 |
4 |
4 |
? |
2 |
3 |
1 |
2 |
3 |
3 |
3 |
4 |
3 |
4 |
3 |
4 |
4 |
3 |
3 |
1 |
5 |
4 |
5 |
1 |
5 |
5 |
2 |
1 |
现在的问题是:是否应当向用户1推荐物品105?我们先假设:如果用户1给物品105评5分,那么应当推荐给用户1,如果是1分,那么最好不要推荐!如何预测用户1会给物品105评多少分呢?我们的逻辑是:参考那些与用户1相似的用户给物品105的评分,例如与用户1相似的用户都给105评5分,那么我们预测用户1可能会给物品105评5分,也就当然将物品105推荐给用户1了。所以,我们就需要寻找与用户1具有相似偏好的那些用户,那么究竟如何度量两个用户之间的相似度呢?比如用户1和用户2。事实上,用户对所有物品的评分构成了一个n维向量(矩阵的每一行),例如,用户1对应一个5维向量v1=(5,3,4,4,?),用户2对应一个5维向量v2=(3,1,2,3,3),那么问题就转换成如何度量这两个向量的相似度,大家立即想到的是欧几里得空间距离:
上式表示了用户1和用户2的欧几里得空间距离,注意到用户1对物品105没有评分,计算时我们舍弃没有数据的维数(向量降维),如下计算即可:
基于距离越近,用户越相似的思想,用户1和用户2的相似度:
其中4表示向量维数,计算结果小数位舍弃。同理可以计算出用户1分别与用户3、4和5的相似度分别为:
所以与用户1相似度按从高到低的用户排序依次是:用户3、用户2、用户4和用户5。这里欧几里得相似度只是提供了一种相似度度量方式。是否还有其他的度量方式呢?我们知道,在二维空间中,两个向量v1和向量v2的夹角余弦计算如下:
那么,这个余弦值是否可以用来度量两个用户的相似度呢?如图:
图中展示了两个向量的三种位置关系:
第一个图表示一般情况:两个向量有个夹角;
第二个图表示两个向量重合的情况;
第三个图表示两个向量垂直的情况。
我们先考虑两个物品,如下:
用户/物品 |
物品1 |
物品2 |
用户1 |
3 |
4 |
用户2 |
3 |
4 |
用户1和用户2对物品的评分一样,我们认为这两个用户是非常相似的,甚至一样,他们对应的向量为v1=(3,4),v2=(3,4),余弦值:
这种情况余弦值1确实可以作为用户1和用户2的相似度度量。
当用户给物品的评分情况如下时:
用户/物品 |
物品1 |
物品2 |
用户1 |
5 |
0 |
用户2 |
0 |
5 |
实际来看,两个用户截然不同,用户1给物品1评5分高分时,用户2却给相同物品评低分,对物品2也是如此,他们对应的向量为v1=(5,0),v2=(0,5),余弦值:
这种情况余弦值0也可以作为用户1和用户2的相似度度量。我们的基本逻辑是:当两个向量的夹角越小时,用户相似度越高,反之,用户相似度越低。所以我们可以直接使用余弦值作为用户的相似度度量,称为余弦相似度(记作CosineSimilarity)。我们使用案例数据计算出用户1与其他用户的相似度如下:
所以与用户1相似度从高到低的用户排序依次是:用户3、用户2、用户4和用户5,与欧几里得相似度值虽然相差甚多,但结果却一致。当然相似度度量还有很多方法,例如皮尔森相关系数,公式如下:
其中P表示所有物品的集合,例如案例中P={101,102,103,104,105},表示用户a给物品p的评分,和分别表示用户a和用户b对所有物品的平均评分,例如用户1给所有物品的平均评分是:
那么,用户1和用户2的相似度:
用户1与其他用户的相似度为:
所以与用户1相似度从高到低的用户排序依次是:用户2、用户3、用户4和用户5。与前面两种度量方式结果不完全一致,这里用户2与用户1更相似一些。如果只选择两个最相似的用户,那么结果却是一致的。还有其他很多相似度度量方法,我们不再一一说明。到这里用户相似度的度量问题已经得到解决。
2、用户的最近邻(k-最近邻)
所谓某个用户的k-最近邻是指与该用户最相似的k个用户(不包括该用户本身)。例如我们前面形成了用户1的4-最近邻 ={用户3,用户2,用户4,用户5}。如果我们只选择两个最相似用户,那么就构成了用户1的2-最近邻 ={用户3,用户2},从2-最近邻来看,前面的三种度量方式,结果是一致的。
我们已经找到了与当前用户相似的那些用户了,接下来就要参考这些用户给物品105的评分来预测当前用户给105的评分了。
三、预测评分
如何预测用户1给物品105的评分?这就关系到该重视哪些近邻的评分,如何重视?例如通过皮尔森相关系数,计算出的用户1与其他用户的相似度:用户1和用户2、用户3相似度分别为0.85和0.70,相关性最大,与用户4相似度值0,可以认为无关,与用户五的相关系数值是-0.79,是个负值,可以认为两个用户可能偏好截然相反。所以我们应当选择用户2和用户3作为用户1的2-最近邻来评分。下面公式考虑了用户a的N近邻与用户a平均评分的偏差,预测用户a对物品p的评分:
其中sim(a,b)表示用户a和用户b的相似度。所以用户1给物品105的预测评分是:
当然,Apache Mahout中并不是这样实现的,它未考虑平均评分,而是采用了如下简化的预测公式:
计算出的预测评分为
四、推荐
无论用户1给物品105的预测评分是4.87,还是3.90,都是一个比较高的分数,应当将物品105推荐给用户1。
五、代码实现
1、pom.xml
导入Hadoop Mahout算法库,如下:
<?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> <modelVersion>4.0.0</modelVersion> <groupId>com.leboop</groupId> <artifactId>mahout</artifactId> <version>1.0-SNAPSHOT</version> <properties> <!-- mahout版本号 --> <mahout.version>0.13.0</mahout.version> <!-- scala版本号 --> <scala.version>2.10</scala.version> </properties> <dependencies> <!-- mahout --> <dependency> <groupId>org.apache.mahout</groupId> <artifactId>mahout-math</artifactId> <version>${mahout.version}</version> </dependency> <dependency> <groupId>org.apache.mahout</groupId> <artifactId>mahout-integration</artifactId> <version>${mahout.version}</version> </dependency> <!-- mahout-scala --> <dependency> <groupId>org.apache.mahout</groupId> <artifactId>mahout-math-scala_${scala.version}</artifactId> <version>${mahout.version}</version> </dependency> <!-- mahout-spark --> <dependency> <groupId>org.apache.mahout</groupId> <artifactId>mahout-spark_${scala.version}</artifactId> <version>${mahout.version}</version> </dependency> </dependencies> </project>
2、推荐程序
程序中,我们使用皮尔森系数计算用户相似度,如下:
package com.leboop.recommendation; import org.apache.mahout.cf.taste.impl.common.LongPrimitiveIterator; import org.apache.mahout.cf.taste.impl.model.file.FileDataModel; import org.apache.mahout.cf.taste.impl.neighborhood.NearestNUserNeighborhood; import org.apache.mahout.cf.taste.impl.recommender.GenericUserBasedRecommender; import org.apache.mahout.cf.taste.impl.similarity.PearsonCorrelationSimilarity; import org.apache.mahout.cf.taste.model.DataModel; import org.apache.mahout.cf.taste.neighborhood.UserNeighborhood; import org.apache.mahout.cf.taste.recommender.RecommendedItem; import org.apache.mahout.cf.taste.recommender.Recommender; import org.apache.mahout.cf.taste.similarity.UserSimilarity; import java.io.File; import java.util.Arrays; import java.util.List; /** * 推荐思路 * 1、读取用户-物品-评分数据,转换成推荐数据模型 * 2、基于用户相似度计算用户N-最近邻 * 3、使用推荐引擎推荐物品 */ public class BasedUserRecommendationTest { public static void main(String[] args) { //用户-物品-评分数据文件 String filePath = "data\\alice.txt"; //数据模型 DataModel dataModel = null; try { //文件数据转换成数据模型 dataModel = new FileDataModel(new File(filePath)); /** * 用户相似度定义 */ //余弦相似度 // UserSimilarity userSimilarity= new UncenteredCosineSimilarity(dataModel); //欧几里得相似度 // UserSimilarity userSimilarity= new EuclideanDistanceSimilarity(dataModel); //皮尔森相似度 UserSimilarity userSimilarity = new PearsonCorrelationSimilarity(dataModel); //定义用户的2-最近邻 UserNeighborhood userNeighborhood = new NearestNUserNeighborhood(2, userSimilarity, dataModel); //定义推荐引擎 Recommender recommender = new GenericUserBasedRecommender(dataModel,userNeighborhood, userSimilarity); //从数据模型中获取所有用户ID迭代器 LongPrimitiveIterator usersIterator = dataModel.getUserIDs(); //通过迭代器遍历所有用户ID while (usersIterator.hasNext()) { System.out.println("================================================"); //用户ID long userID = usersIterator.nextLong(); //用户ID LongPrimitiveIterator otherusersIterator = dataModel.getUserIDs(); //遍历用户ID,计算任何两个用户的相似度 while (otherusersIterator.hasNext()) { Long otherUserID = otherusersIterator.nextLong(); System.out.println("用户 " + userID + " 与用户 " + otherUserID + " 的相似度为:" + userSimilarity.userSimilarity(userID, otherUserID)); } //userID的N-最近邻 long[] userN = userNeighborhood.getUserNeighborhood(userID); //用户userID的推荐物品,最多推荐两个 List<RecommendedItem> recommendedItems = recommender.recommend(userID, 2); System.out.println("用户 "+userID + " 的2-最近邻是 "+ Arrays.toString(userN)); if (recommendedItems.size() > 0) { for (RecommendedItem item : recommendedItems) { System.out.println("推荐的物品"+ item.getItemID()+"预测评分是 "+ item.getValue()); } } else { System.out.println("无任何物品推荐"); } } } catch (Exception e) { e.printStackTrace(); } } }
执行上述程序,结果如下:
================================================
用户 1 与用户 1 的相似度为:0.9999999999999998
用户 1 与用户 2 的相似度为:0.8528028654224417
用户 1 与用户 3 的相似度为:0.7071067811865475
用户 1 与用户 4 的相似度为:0.0
用户 1 与用户 5 的相似度为:-0.7921180343813393
用户 1 的2-最近邻是 [2, 3]
推荐的物品105预测评分是 3.9065998
================================================
用户 2 与用户 1 的相似度为:0.8528028654224417
用户 2 与用户 2 的相似度为:1.0
用户 2 与用户 3 的相似度为:0.4677071733467446
用户 2 与用户 4 的相似度为:0.4899559349388647
用户 2 与用户 5 的相似度为:-0.9001487972234673
用户 2 的2-最近邻是 [1, 4]
无任何物品推荐
================================================
用户 3 与用户 1 的相似度为:0.7071067811865475
用户 3 与用户 2 的相似度为:0.4677071733467422
用户 3 与用户 3 的相似度为:1.0
用户 3 与用户 4 的相似度为:-0.16116459280507703
用户 3 与用户 5 的相似度为:-0.466569474815843
用户 3 的2-最近邻是 [1, 2]
无任何物品推荐
================================================
用户 4 与用户 1 的相似度为:0.0
用户 4 与用户 2 的相似度为:0.489955934938866
用户 4 与用户 3 的相似度为:-0.16116459280507558
用户 4 与用户 4 的相似度为:1.0
用户 4 与用户 5 的相似度为:-0.6415029025857746
用户 4 的2-最近邻是 [2, 1]
无任何物品推荐
================================================
用户 5 与用户 1 的相似度为:-0.7921180343813393
用户 5 与用户 2 的相似度为:-0.9001487972234682
用户 5 与用户 3 的相似度为:-0.466569474815843
用户 5 与用户 4 的相似度为:-0.6415029025857751
用户 5 与用户 5 的相似度为:1.0
用户 5 的2-最近邻是 [3, 4]
无任何物品推荐
Process finished with exit code 0
到这,我们已经成功为用户1推荐了物品105。
六、基于物品的协同过滤推荐
1、基本思想
尽管基于用户的协同过滤的方法已经成功应用在了不同领域,但在有着数以百万计甚至上亿用户和物品的大型电子商务网站(例如亚马逊Amazon)还是会存在很多严峻挑战。这种方法很难做到实时推荐。下面谈谈与基于用户协同过滤类似的另外一种推荐方法——基于物品的协同过滤推荐。
基于物品的协同过滤推荐主要思想是利用物品间相似度,而不是用户间相似度来计算预测值。我们看用户-物品-评分矩阵的某一列,得到物品101对应的向量v1=(5,3,4,3,1)和物品105对应的向量v5=(?,3,5,4,1),舍弃向量的第一个分量,通过余弦相似度计算出他们的相似度如下:
我们通过计算用户1对所有与物品105相似物品的加权评分总和来预测用户1对物品105的评分,公式如下:
N表示物品p的k-最近邻,同用户的k-最近邻类似,实际中需要选择k值,sim(t,p)表示物品t与物品p的相似度,表示用户a给物品t的评分。Apache Mahout实现时,N采用与物品p相似的所有物品。所以,用户1对物品105的预测评分为:
2、代码实现
程序中,我们使用物品余弦相似度,如下:
package com.leboop.recommendation; import org.apache.mahout.cf.taste.impl.common.LongPrimitiveIterator; import org.apache.mahout.cf.taste.impl.model.file.FileDataModel; import org.apache.mahout.cf.taste.impl.neighborhood.NearestNUserNeighborhood; import org.apache.mahout.cf.taste.impl.recommender.GenericItemBasedRecommender; import org.apache.mahout.cf.taste.impl.recommender.GenericUserBasedRecommender; import org.apache.mahout.cf.taste.impl.similarity.EuclideanDistanceSimilarity; import org.apache.mahout.cf.taste.impl.similarity.PearsonCorrelationSimilarity; import org.apache.mahout.cf.taste.impl.similarity.UncenteredCosineSimilarity; import org.apache.mahout.cf.taste.model.DataModel; import org.apache.mahout.cf.taste.neighborhood.UserNeighborhood; import org.apache.mahout.cf.taste.recommender.RecommendedItem; import org.apache.mahout.cf.taste.recommender.Recommender; import org.apache.mahout.cf.taste.similarity.ItemSimilarity; import org.apache.mahout.cf.taste.similarity.UserSimilarity; import java.io.File; import java.util.Arrays; import java.util.List; /** * 推荐思路 * 1、读取用户-物品-评分数据,转换成推荐数据模型 * 2、定义物品相似度(余弦相似度、皮尔森相似度等) * 3、预测评分 * 4、使用推荐引擎推荐物品 */ public class BasedItemRecommendationTest { public static void main(String[] args) { //用户-物品-评分数据文件 String filePath = "data\\alice.txt"; //数据模型 DataModel dataModel = null; try { //文件数据转换成数据模型 dataModel = new FileDataModel(new File(filePath)); /** * 物品相似度定义 */ //余弦相似度 ItemSimilarity itemSimilarity = new UncenteredCosineSimilarity(dataModel); //欧几里得相似度 // ItemSimilarity itemSimilarity= new EuclideanDistanceSimilarity(dataModel); // //皮尔森相似度 // ItemSimilarity itemSimilarity = new PearsonCorrelationSimilarity(dataModel); //定义推荐引擎 Recommender recommender =new GenericItemBasedRecommender(dataModel, itemSimilarity); //获取物品迭代器 LongPrimitiveIterator itemIDIterator = dataModel.getItemIDs(); //遍历所有物品 while(itemIDIterator.hasNext()){ System.out.println("=================================================="); Long itermID=itemIDIterator.next(); LongPrimitiveIterator otherItemIDIterator=dataModel.getItemIDs(); //打印物品相似度 while (otherItemIDIterator.hasNext()){ Long otherItermID=otherItemIDIterator.next(); System.out.println("物品 "+itermID+" 与物品 "+otherItermID+" 的相似度为: "+itemSimilarity.itemSimilarity(itermID,otherItermID)); } } //获取用户迭代器 LongPrimitiveIterator userIDIterator =dataModel.getUserIDs(); //遍历用户 while(userIDIterator.hasNext()){ //获取用户 Long userID=userIDIterator.next(); //获取用户userID的推荐列表 List<RecommendedItem> itemList= recommender.recommend(userID,2); if(itemList.size()>0){ for(RecommendedItem item:itemList){ System.out.println("用户 "+userID+" 推荐物品 "+item.getItemID()+",物品评分 "+item.getValue()); } }else { System.out.println("用户 "+userID+" 无任何物品推荐"); } } } catch (Exception e) { e.printStackTrace(); } } }
执行上述程序,结果如下:
==================================================
物品 101 与物品 101 的相似度为: 0.9999999999999999
物品 101 与物品 102 的相似度为: 0.7802595923450996
物品 101 与物品 103 的相似度为: 0.8197822947299412
物品 101 与物品 104 的相似度为: 0.9433700705169152
物品 101 与物品 105 的相似度为: 0.9941002434954168
==================================================
物品 102 与物品 101 的相似度为: 0.7802595923450996
物品 102 与物品 102 的相似度为: 1.0
物品 102 与物品 103 的相似度为: 0.9420196895802699
物品 102 与物品 104 的相似度为: 0.8479844150302361
物品 102 与物品 105 的相似度为: 0.7388505791113108
==================================================
物品 103 与物品 101 的相似度为: 0.8197822947299412
物品 103 与物品 102 的相似度为: 0.9420196895802699
物品 103 与物品 103 的相似度为: 1.0
物品 103 与物品 104 的相似度为: 0.7840250892042882
物品 103 与物品 105 的相似度为: 0.7226101216384172
==================================================
物品 104 与物品 101 的相似度为: 0.9433700705169152
物品 104 与物品 102 的相似度为: 0.8479844150302361
物品 104 与物品 103 的相似度为: 0.7840250892042882
物品 104 与物品 104 的相似度为: 0.9999999999999999
物品 104 与物品 105 的相似度为: 0.9395584757365169
==================================================
物品 105 与物品 101 的相似度为: 0.9941002434954168
物品 105 与物品 102 的相似度为: 0.7388505791113108
物品 105 与物品 103 的相似度为: 0.7226101216384172
物品 105 与物品 104 的相似度为: 0.9395584757365169
物品 105 与物品 105 的相似度为: 0.9999999999999999
用户 1 推荐物品 105,物品评分 4.0751815
用户 2 无任何物品推荐
用户 3 无任何物品推荐
用户 4 无任何物品推荐
用户 5 无任何物品推荐
Process finished with exit code 0
七、协同过滤推荐基本步骤
1、基于用户的协同过滤
(1)采集用户与物品之间的关联数据,如浏览、购买或交易记录,形成初始数据;
(2)分析用户与物品的关联数据形成用户-物品-评分数据;
(3)依据用户-物品-评分数据计算所有用户间的相似度;
(4)选择与当前用户最相似的k个用户,也就是用户k-最近邻。
(5)将这k个用户加权评分最高且当前用户没有浏览过的n个物品推荐给当前用户。
2、基于物品的协同过滤
(1)采集用户与物品之间的关联数据,如浏览、购买或交易记录,形成初始数据;
(2)分析用户与物品的关联数据形成用户-物品-评分数据;
(3)依据用户-物品-评分数据计算所有物品间的相似度;
(4)对当前用户没浏览过的某个物品,选择最相似的k个物品(k-最近邻)
(5)基于这k个物品评分预测当前物品评分;
(6)将评分最高的n个物品推荐给当前用户。
八、协同过滤之MapReduce
当用户或者物品数以亿计时,之前的程序是远远不够的,此时,我们需要使用MapReduce来进行协同过滤推荐。
1、数据
准备用户-物品-评分数据itemdata.data,如下:
将数据文件上传至HDFS文件系统/input/mahout-demo/目录下,如图:
2、执行协同过滤MapReduce任务
在命令窗口执行如下命令,
hadoop jar mahout-examples-0.13.0-job.jar org.apache.mahout.cf.taste.hadoop.item.RecommenderJob -i /input/mahout-demo/itemdata.data -o /output/cf/item -s SIMILARITY_LOGLIKELIHOOD --tempDir /tmp/cf/item
部分执行过程如图:
参数说明:
(1)-i:指定输入数据文件路径
(2)-o:指定最终输出数据文件路径
(3)-s:指定相似度度量方法,这里使用的是对数似然相似度
(4)–tempDir:指定任务执行的中间数据文件保存目录
任务执行结束,推荐结果如下:
例如,第4行数据表明:优先推荐物品577给用户1917281441163686119。