Apache Mahout中推薦算法Slope one源碼分析

關于推薦引擎

        如今的互聯網中，無論是電子商務還是社交網絡，對數據挖掘的需求都越來越大了，而推薦引擎正是數據挖掘完美體現；通過分析用戶歷史行為，將他可能喜歡內容推送給他，能產生相當好的用戶體驗，這就是推薦引擎。

推薦算法Slope one的原理

        首先Slope one是一種基于項目的協同過濾算法（Item-based Recommendation），簡單介紹這種算法（若理解有誤，歡迎大家更正，I am just a beginner）：根據用戶們對產品的喜好程度，來將產品分類；舉個簡單例子：比如有10個用戶，其中有9個人即喜歡產品A，也喜歡產品B，但只有2個人喜歡產品C；于是可以推斷產品A和產品B是屬于同類的，而產品C可能跟它們不是一類。

        好了話不多講，讓我們看看Slope one吧！

        Slope one是通過用戶們對每個產品的評分，來計算產品間的一個差值；這種計算是通過 線性回歸 f(x) = ax + b得到的，其中a = 1，正如它的名字Slope one（斜率為一）；另外用戶的評分，在Slope one中是必不可少的。這里舉

例看看它的計算方式：下面是一張用戶對書籍的評分表

        書1是否適合推薦給用戶C，需要通過Slope one 計算出一個值來判定：首先得到書1和書2之間的平均差值X = （（5-3）+（3-4））/ 2 = 0.5，然后通過用戶C對書2的打分得到相應的推薦值 2+0.5 = 2.5 （推薦引擎會通過推薦值的高低來選擇要推薦的物品），這里只是通過書2來計算用戶C對書1的推薦值，實際的Slope one算法中若要得到用戶C對書1的推薦值，會把用戶C評分過的所有書按此方法依次對書1（為評分的書）算推薦值，然后取平均值得到，放到表中如下：

（（（5-3）+（3-4））/ 2 +2 + （5 - 2）/ 1 + 5 ）/ 2 = 5.25 

實際應用中你還可以設權值，這里就不深入了。

        以上是Slope one的原理，接下來看看它在Mahout中是如何設計與實現的。

Mahout中Slope one的設計思路以及代碼實現

        首先我們需要基礎數據，即用戶對產品的評分，這部分數據可以來自數據庫也可以來自文件，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;
  }

 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 源代碼