Apache Mahout中推荐算法Slope one源码分析

fmms 13年前

关于推荐引擎

如今的互联网中，无论是电子商务还是社交网络，对数据挖掘的需求都越来越大了，而推荐引擎正是数据挖掘完美体现；通过分析用户历史行为，将他可能喜欢内容推送给他，能产生相当好的用户体验，这就是推荐引擎。

Mahout中Slope one的设计思路以及代码实现

先简单介绍下，Mahout是Apache的一个开源项目，由Lucene项目组和Hadoop项目组分离出来，它实现了推荐引擎中的大部分经典算法，有兴趣的朋友可以研究研究

首先我们需要基础数据，即用户对产品的评分，这部分数据可以来自数据库也可以来自文件，Mahout中对此设计了一个简单的数据库表，SQL如下：

 CREATE TABLE taste_preferences (      user_id BIGINT NOT NULL,      item_id BIGINT NOT NULL,      preference FLOAT NOT NULL,      PRIMARY KEY (user_id, item_id),      INDEX (user_id),      INDEX (item_id)  )

其次，Mahout在启动时，会对这部分数据进行处理，算出每对产品间的平均评分差值，已Map<ItemId, Map<ItemId, Average>>的数据结构存放在内存中（当然这帮牛人没有用Java中Map的实现，自己写了一个叫FastByIDMap的类）。处理基础数据的计算代码如下：

1. 首先获取所有评过分的用户id （7，而dataModel就是用于存放我上面提到的基础）

2. 然后依次计算每个用户评分过的产品间的平均评分差值（9，具体在processOneUser中实现）

 private void buildAverageDiffs() throws TasteException {      log.info("Building average diffs...");      try {        buildAverageDiffsLock.writeLock().lock();        averageDiffs.clear();        long averageCount = 0L;        LongPrimitiveIterator it = dataModel.getUserIDs();        while (it.hasNext()) {          averageCount = processOneUser(averageCount, it.nextLong());        }                pruneInconsequentialDiffs();        updateAllRecommendableItems();              } finally {        buildAverageDiffsLock.writeLock().unlock();      }    }

3. 首先取出该用户所有评分过的项目和评分值（4）

4. 依次计算这些项目间的平均评分差值（6 ~ 26），并存储在内存中。

private long processOneUser(long averageCount, long userID) throws TasteException {      log.debug("Processing prefs for user {}", userID);      // Save off prefs for the life of this loop iteration      PreferenceArray userPreferences = dataModel.getPreferencesFromUser(userID);      int length = userPreferences.length();      for (int i = 0; i < length - 1; i++) {        float prefAValue = userPreferences.getValue(i);        long itemIDA = userPreferences.getItemID(i);        FastByIDMap<RunningAverage> aMap = averageDiffs.get(itemIDA);        if (aMap == null) {          aMap = new FastByIDMap<RunningAverage>();          averageDiffs.put(itemIDA, aMap);        }        for (int j = i + 1; j < length; j++) {          // This is a performance-critical block          long itemIDB = userPreferences.getItemID(j);          RunningAverage average = aMap.get(itemIDB);          if (average == null && averageCount < maxEntries) {            average = buildRunningAverage();            aMap.put(itemIDB, average);            averageCount++;          }          if (average != null) {            average.addDatum(userPreferences.getValue(j) - prefAValue);          }        }        RunningAverage itemAverage = averageItemPref.get(itemIDA);        if (itemAverage == null) {          itemAverage = buildRunningAverage();          averageItemPref.put(itemIDA, itemAverage);        }        itemAverage.addDatum(prefAValue);      }      return averageCount;    }

以上是启动时做的事，而当某个用户来了，需要为他计算推荐列表时，就快速许多了（是一个空间换时间的思想），下面的方法是某一个用户对其某一个他未评分过的产品的推荐值，参数UserId：用户ID；ItemId：为评分的产品ID

1. 再次取出该用户评分过的所有产品（4）：PreferenceArray prefs中保存着ItemID和该用户对它的评分

2. 取得上一步得到的prefs中的所有物品与itemID代表的物品之间的平均评分差值（5），其中DiffStorage diffStorage

对象中存放中每对产品间的平均评分差值（而上面启动时的计算都是在MySQLJDBCDiffStorage中实现的，计算后的

值也存于其中，它是DiffStorage接口的实现），所以取得的流程很简单，这里不贴代码了

3. 最后就是依次推算评分过的产品到未评分的产品的一个推荐值 = 平均评分差值（两者间的） + 已评分的分值（用

户对其中一个评分），然后将这些推荐值取个平均数（7 ~ 37），其中11行判断是否要考虑权重。

private float doEstimatePreference(long userID, long itemID) throws TasteException {      double count = 0.0;      double totalPreference = 0.0;      PreferenceArray prefs = getDataModel().getPreferencesFromUser(userID);      RunningAverage[] averages = diffStorage.getDiffs(userID, itemID, prefs);      int size = prefs.length();      for (int i = 0; i < size; i++) {        RunningAverage averageDiff = averages[i];        if (averageDiff != null) {          double averageDiffValue = averageDiff.getAverage();          if (weighted) {            double weight = averageDiff.getCount();            if (stdDevWeighted) {              double stdev = ((RunningAverageAndStdDev) averageDiff).getStandardDeviation();              if (!Double.isNaN(stdev)) {                weight /= 1.0 + stdev;              }              // If stdev is NaN, then it is because count is 1. Because we're weighting by count,              // the weight is already relatively low. We effectively assume stdev is 0.0 here and              // that is reasonable enough. Otherwise, dividing by NaN would yield a weight of NaN              // and disqualify this pref entirely              // (Thanks Daemmon)            }            totalPreference += weight * (prefs.getValue(i) + averageDiffValue);            count += weight;          } else {            totalPreference += prefs.getValue(i) + averageDiffValue;            count += 1.0;          }        }      }      if (count <= 0.0) {        RunningAverage itemAverage = diffStorage.getAverageItemPref(itemID);        return itemAverage == null ? Float.NaN : (float) itemAverage.getAverage();      } else {        return (float) (totalPreference / count);      }    }

Slope one 的源码已分析完毕。

其实Slope one推荐算法很流行，被很多网站使用，包括一些大型网站；我个人认为最主要的原因是它具备如下优势：

1. 实现简单并且易于维护。

2. 响应即时（只要用户做出一次评分，它就能有效推荐，根据上面代码很容易理解），并且用户的新增评分对推荐数据的改变量较小，应为在内存中存储的是物品间的平均差值，新增的差值只需累加一下，切范围是用户评分过的产品。

3. 由于是基于项目的协同过滤算法，适用于当下火热的电子商务网站，原因电子商务网站用户量在几十万到上百万，产品量相对于之则要小得多，所以对产品归类从性能上讲很高效。

分析至此，祝大家周末愉快。

参考资料：

1. Slope one http://zh.wikipedia.org/wiki/Slope_one

2. 探索推荐引擎内部的秘密，第 2 部分: 深入推荐引擎相关算法 - 协同过滤

http://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy2/index.html

3. Apache Mahout 源代码

	书 1	书 2	书 3
用户A	5	3	2
用户B	3	4	未评分
用户C	未评分	2	5

Apache Mahout中推荐算法Slope one源码分析

关于推荐引擎

推荐算法Slope one的原理

Mahout中Slope one的设计思路以及代码实现

相关经验

目录