Slope one推荐算法原理

推荐算法Slope one的原理

Slope One的基本概念很简单, 例子1, 用户X, Y和A都对Item1打了分. 同时用户X,Y还对Item2打了分, 用户A对Item2可能会打多少分呢?

User	Rating to Item 1	Rating to Item 2
X	5	3
Y	4	3
A	4	?

根据SlopeOne算法, 应该是:4 - ((5-3) + (4-2))/2 = 2.5. 
解释一下. 用户X对Item1的rating是5, 对Item2的rating是3, 那么他可能认为Item2应该比Item1少两分. 同时用户Y认为Item2应该比Item1少1分. 据此我们知道所有对Item1和Item2都打了分的用户认为Item2会比Item1平均少1.5分. 所以我们有理由推荐用户A可能会对Item2打(4-1.5)=2.5分;

很简单是不是? 找到对Item1和Item2都打过分的用户, 算出rating差的平均值, 这样我们就能推测出对Item1打过分的用户A对Item2的可能Rating, 并据此向A用户推荐新项目.
这里我们能看出Slope One算法的一个很大的优点, 在只有很少的数据时候也能得到一个相对准确的推荐, 这一点可以解决Cold Start的问题.

加权算法
接下来我们看看加权算法(Weighted Slope One). 如果有100个用户对Item1和Item2都打过分, 有1000个用户对Item3和Item2也打过分. 显然这两个rating差的权重是不一样的. 因此我们的计算方法是
(100*(Rating 1 to 2) + 1000(Rating 3 to 2)) / (100 + 1000)

上面讨论的是用户只对项目的喜好程度打分.还有一种情况下用户也可以对项目的厌恶程度打分. 这时可以使用双极SlopeOne算法(BI-Polar SlopeOne).         

以上是Slope one的原理，接下来看看它在Mahout中是如何设计与实现的。

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

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

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

CREATETABLEtaste_preferences (
    user_idBIGINTNOTNULL,
    item_idBIGINTNOTNULL,
    preferenceFLOATNOTNULL,
    PRIMARYKEY(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中实现）

privatevoidbuildAverageDiffs() throwsTasteException {
   log.info("Building average diffs...");
   try{
     buildAverageDiffsLock.writeLock().lock();
     averageDiffs.clear();
     longaverageCount = 0L;
     LongPrimitiveIterator it = dataModel.getUserIDs();
     while(it.hasNext()) {
       averageCount = processOneUser(averageCount, it.nextLong());
     }

     pruneInconsequentialDiffs();
     updateAllRecommendableItems();

   }finally{
     buildAverageDiffsLock.writeLock().unlock();
   }
 }

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

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

privatelongprocessOneUser(longaverageCount,longuserID)throwsTasteException {
    log.debug("Processing prefs for user {}", userID);
    // Save off prefs for the life of this loop iteration
    PreferenceArray userPreferences = dataModel.getPreferencesFromUser(userID);
    intlength = userPreferences.length();
    for(inti = 0; i < length - 1; i++) {
      floatprefAValue = userPreferences.getValue(i);
      longitemIDA = userPreferences.getItemID(i);
      FastByIDMap<RunningAverage> aMap = averageDiffs.get(itemIDA);
      if(aMap == null) {
        aMap = newFastByIDMap<RunningAverage>();
        averageDiffs.put(itemIDA, aMap);
      }
      for(intj = i + 1; j < length; j++) {
        // This is a performance-critical block
        longitemIDB = 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);
    }
    returnaverageCount;
  }

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

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

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

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

MySQLJDBCDiffStorage中实现的，计算后的值也存于其中，它是DiffStorage接口的实现），所以

取得的流程很简单，这里不贴代码了

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

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

privatefloatdoEstimatePreference(longuserID,longitemID)throwsTasteException {
    doublecount = 0.0;
    doubletotalPreference = 0.0;
    PreferenceArray prefs = getDataModel().getPreferencesFromUser(userID);
    RunningAverage[] averages = diffStorage.getDiffs(userID, itemID, prefs);
    intsize = prefs.length();
    for(inti = 0; i < size; i++) {
      RunningAverage averageDiff = averages[i];
      if(averageDiff != null) {
        doubleaverageDiffValue = averageDiff.getAverage();
        if(weighted) {
          doubleweight = averageDiff.getCount();
          if(stdDevWeighted) {
            doublestdev = ((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);
      returnitemAverage == null? Float.NaN : (float) itemAverage.getAverage();
    }else{
      return(float) (totalPreference / count);
    }
  }

         Slope one 的源码已分析完毕。

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

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

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

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