theme: cyanosis

「这是我参与2022首次更文挑战的第2天，活动详情查看： 2022首次更文挑战」。

推荐系统是什么

每个系统发展到后期，都有这样的需求， 怎么给用户推荐他最感兴趣的内容。为了解决这一问题而提出来的“推荐系统”应运而生。协同过滤是基于“集体智慧”的思想，认为：人们倾向某种人群共性的部分。例如，你想看一部电影，但不知道看哪部，大部分人都会问问周围的人，并倾向选择与自己爱好口味比较类似的人的推荐。

本文会从推荐系统应该怎么建模谈起，主要介绍怎么使用 GridSearch建模、输入数据和算法并进行算法和评估的过程。

GridSearch网格搜索

推荐系统的建模

输入数据集、测试集数据，通过用户对物品的评分数据，

• user cf:得出用户和用户之间的相似度，给用户推荐其他用户好评的物品。
• item cf:得出物品和物品之间的相似度，把物品推荐给其他邻居物品好评的用户。

然后拿出测试集，看看预测数据和实际数据是否一致，评估算法和模型。

网格搜索架构

从推荐系统建模可以看出，GridSearch的基本流程如下：

但是GridSearch会对一系列算法和超参数进行评估，选出效果最好的几个算法和参数用于实际情况。

协同推荐算法

协同推荐算法方向已经做了非常多的工作。主要是分成3个方向

• k近邻算法KNN

  • jaccard算法
  • pip算法
  • cosine算法

• 基于矩阵分解的算法

  • PMF 概率矩阵分解

• 深度学习-基于神经网络算法的推荐

推荐系统是怎么运作的

demo:UserKNNGridSearch

这是一个基于UserKNN协同算法的GridSearch

  public class UserKNNGridSearch {
    public static void main(String[] args) throws IOException {
        DataModel datamodel = BenchmarkDataModels.MovieLens100K();
        ParamsGrid grid = new ParamsGrid();
        grid.addParam("numberOfNeighbors", new int[] {25, 50, 75, 100,200,300});
        grid.addParam(
                "metric",
                new UserSimilarityMetric[] {
                        new Correlation(),
                        new Cosine(),
                        new Jaccard()
                });
        grid.addFixedParam("aggregationApproach", UserKNN.AggregationApproach.DEVIATION_FROM_MEAN);
        Map<String, Object> precisionParams = new HashMap<>();//精度参数
        precisionParams.put("numberOfRecommendations", 3);
        precisionParams.put("relevantThreshold", 4.0);
        GridSearch gs =
                new GridSearch(datamodel, grid, UserKNN.class, Precision.class, precisionParams);
        gs.fit();
        gs.printResults(5, false);
    }
}

• BenchmarkDataModels.MovieLens100K()是Netflix的用户和电影评分（约100K评分）的数据集
• 向GridSearch输入了三种UserSimilarityMetric：Correlation、Cosine和Jaccard
• 设置了邻居个数numberOfNeighbors{25, 50, 75, 100,200,300}作为预测的超参数
• 预测方法选用DEVIATION_FROM_MEAN，也就是 平均值偏差法，下面会详细介绍到
• 适应Precision作为评估算法
• 最后输出了3个最好的算法+参数组合

效果

  0.805357 for {metric=Jaccard, numberOfNeighbors=200, aggregationApproach=DEVIATION_FROM_MEAN}
0.804167 for {metric=Jaccard, numberOfNeighbors=300, aggregationApproach=DEVIATION_FROM_MEAN}
0.786310 for {metric=Jaccard, numberOfNeighbors=75, aggregationApproach=DEVIATION_FROM_MEAN}

GridSearch工作原理

可以看到，GridSearch工作的入口是fit函数。如下：

  public void fit() {

  Iterator<Map<String, Object>> iter = grid.getDevelopmentSetIterator(true, seed);

  int i = 0;
  while (i < this.numIters && iter.hasNext()) {
    Map<String, Object> params = iter.next();
    i++;

    Recommender recommender = null;

    try {
      recommender =
          this.recommenderClass
              .getConstructor(DataModel.class, Map.class)
              .newInstance(this.datamodel, params);
    } 

    if (recommender != null) {
      recommender.fit();
    }

    QualityMeasure qm = null;

    try {
      if (this.qualityMeasureParams == null || this.qualityMeasureParams.isEmpty()) {
        qm = this.qualityMeasureClass.getConstructor(Recommender.class).newInstance(recommender);
      } else {
        qm =
            this.qualityMeasureClass
                .getConstructor(Recommender.class, Map.class)
                .newInstance(recommender, this.qualityMeasureParams);
      }
    } 
    if (qm != null) {
      double score = qm.getScore();
      results.add(new Pair<>(params.toString(), score));
    }
  }
}

主要是一个while循环，在这个循环里面做这样的事情：

• 选定一个超参数和算法作为recommender
• recommender计算出 相关度矩阵和 邻居矩阵
• 构造成员为recommender的QualityMeasure对象
• QualityMeasure对象内部会会测试集进行 预测，并和实际数据对比， 评估计算出得分

怎么计算

recommender和QualityMeasure对象的计算和预测都需要大量的计算，一般都会采用并行计算，充分利用系统的core数量。

UserKNN的过程如下：

  @Override
public void fit() {
  System.out.println("\nFitting " + this.toString());
  Parallelizer.exec(this.datamodel.getUsers(), this.metric);
  Parallelizer.exec(this.datamodel.getUsers(), new UserNeighbors());
}

• 首先并行的计算用户的相似度矩阵。
• 然后并行的计算用户的neighbors矩阵。

计算用户的相似度矩阵

UserSimilarityMetric计算用户的相似度矩阵，如下：

  @Override
public void run(User user) {
  int userIndex = user.getUserIndex();

  for (int u = 0; u < datamodel.getNumberOfUsers(); u++) {
    User otherUser = datamodel.getUser(u);
    if (userIndex == otherUser.getUserIndex()) {
      similarities[userIndex][u] = Double.NEGATIVE_INFINITY;
    } else {
      similarities[userIndex][u] = this.similarity(user, otherUser);
    }
  }
}

run计算所有用户的相似度，像上面提到的那样，Jaccard算法是其中计算相似度的一种算法，具体如下：

  
public class Jaccard extends UserSimilarityMetric {

  @Override
  public double similarity(User user, User otherUser) {

    int i = 0, j = 0, common = 0;
    while (i < user.getNumberOfRatings() && j < otherUser.getNumberOfRatings()) {
      if (user.getItemAt(i) < otherUser.getItemAt(j)) {
        i++;
      } else if (user.getItemAt(i) > otherUser.getItemAt(j)) {
        j++;
      } else {
        common++;
        i++;
        j++;
      }
    }

    // If there is not items in common, similarity does not exists
    if (common == 0) return Double.NEGATIVE_INFINITY;

    // Return similarity
    return (double) common
        / (double) (user.getNumberOfRatings() + otherUser.getNumberOfRatings() - common);
  }
}

jaccard算法公式就是： $$ \frac{a \bigcap\limits_a^b b} { a \bigcup\limits_a^b b} $$ jaccard用两个用户是否对同一个物品评分来比较两个用户之间的相似度，两个用户对同一个物品的评价越多，则认为两个用户越相似。

计算用户的neighbors矩阵

这个任务主要是跑出邻居，用于真正的预测。如下

  private class UserNeighbors implements Partible<User> {

  @Override
  public void beforeRun() {}

  @Override
  public void run(User user) {
    int userIndex = user.getUserIndex();
    double[] similarities = metric.getSimilarities(userIndex);
    neighbors[userIndex] = Search.findTopN(similarities, numberOfNeighbors);
  }

  @Override
  public void afterRun() {}
}

这个过程很简单，就是找出user相似度topN的邻居放到neighbors矩阵里面。 numberOfNeighbors是超参数，则demo里面配置的。

预测方法

UserKNN.AggregationApproach提供了多种预测方法来预测一个用户对物品的rating：

• MEAN均值：将用户邻居对该物品的评分求平均值

• WEIGHTED_MEAN，使用带权重的均值，将用户邻居对该物品的评分按相似度加权求平均值

• 平均值偏差： DEVIATION_FROM_MEAN

  private double predictDeviationFromMean(int userIndex, int itemIndex) {
  User user = this.datamodel.getUser(userIndex);
  double[] similarities = metric.getSimilarities(userIndex);

  double num = 0;
  double den = 0;

  for (int neighborIndex : this.neighbors[userIndex]) {
    if (neighborIndex == -1)
      break; // Neighbors array are filled with -1 when no more neighbors exists

    User neighbor = this.datamodel.getUser(neighborIndex);

    int pos = neighbor.findItem(itemIndex);
    if (pos != -1) {
      double similarity = similarities[neighborIndex];
      double rating = neighbor.getRatingAt(pos);
      double avg = neighbor.getRatingAverage();

      num += similarity * (rating - avg);
      den += similarity;
    }
  }

  return (den == 0) ? Double.NaN : user.getRatingAverage() + num / den;
}

上面的过程：

• 首先从用户获得该用户的相似度向量
• 然后，从该用户的邻居们这里获得一些信息
  • 如果邻居有对这个物品的评分（获得这个评分rating和用户的平均评分avg），先找到用户和邻居的相似度similarity

    • 则 $num+=（rating-avg）*similarity$

    • $den += similarity$

• 按照上述规则，遍历完该用户的所有邻居
  • 一共有n个邻居，如果有邻居曾经对这样的物品打过分，则预测值为: $$ user.getRatingAverage() + \frac{\sum\limits_1^n (rating-avg) \times similarity} {\sum\limits_1^n similarity} $$
  • 否则为该用户预测不了

这样的算法就叫做DEVIATION_FROM_MEAN 聚合法，是上面的demo使用的预测算法。

评估方法

评估方法的入口是QualityMeasure类的getScore方法： 会并行的执行下面的run方法：

  public void run(TestUser testUser) {
  int testUserIndex = testUser.getTestUserIndex();
  double[] predictions = recommender.predict(testUser);
  usersScores[testUserIndex] = getScore(testUser, predictions);
}

@Override
public void afterRun() {
  double sum = 0;
  int count = 0;
  for (double us : usersScores) {
    if (!Double.isNaN(us)) {
      sum += us;
      count++;
    }
  }
  score = sum / count;
}

先并行跑出每个用户的分数，再计算平均值，就是这个算法的得分。

那每个用户的分数是怎么计算出来的呢？是在Precision类的getScore方法，如下：

  protected double getScore(TestUser testUser, double[] predictions) {

  // Items that has been recommended and was relevant to the active user

  int[] recommendations = Search.findTopN(predictions, this.numberOfRecommendations);

  int recommendedAndRelevant = 0, recommended = 0;

  for (int pos : recommendations) {
    if (pos == -1) break;

    double rating = testUser.getTestRatingAt(pos);
    if (rating >= this.relevantThreshold) {
      recommendedAndRelevant++;
    }

    recommended++;
  }

  return (double) recommendedAndRelevant / (double) recommended;
}

• top N : this.numberOfRecommendations是输入的超参数
• 选出Top N的预测，如果对于这些物品，用户的真实评价大于relevantThreshold4分，则认为这个是有效的推荐
• 该测试用户得分就是:$recommendedAndRelevant / recommended$。其中：
  • recommendedAndRelevant是评分大于超参数relevantThreshold的个数
  • recommended是有效的可测试评估的推荐个数

参考

本文是参考了cf4j的实现：https://github.com/ferortega/cf4j