协同过滤（Collaborative Filtering， CF）是推荐系统广泛使用的一种技术，它主要通过考虑用户（User）与用户之间、物品（Item）与物品之间的相似度（Similarity），来向用户推荐物品，常被用在电商网站中。其中，在推荐系统中最常使用的协同过滤方法，有如下 4 种：

• 基于用户的协同过滤推荐
• 基于物品的协同过滤推荐
• 基于模型的协同过滤推荐
• 混合协同过滤推荐

上面 4 种方法中，基于用户的协同过滤推荐、基于物品的协同过滤推荐都是基于内存的协同过滤推荐，一般在数据量较小的应用场景下，可以直接在线使用的实时推荐方法；基于模型的协同过滤推荐一般用于离线计算，它采用机器学习的方法，一般首相将用户偏好行为数据分成 2 个数据集（有时可能会将数据集分成 k 个子集，采用交叉验证的方式来提高模型精度），一个为训练集，一个为测试集，使用训练集数据来训练出推荐模型，然后使用测试集数据来评估模型的精度，当满足特定精度时，可以将得到的推荐模型应用于实际线上环境；混合协同过滤推荐，是综合基于内存的协同过滤（基于用户的协同过滤推荐、基于物品的协同过滤推荐）、基于模型的协同过滤推荐这两类方法，克服每一种协同过滤方法本身的缺点，比如基于内存的协同过滤推荐方法不适用于大量数据的推荐应用场景，而基于模型的协同过滤推荐方法由于所基于的数据多是大量历史记录，训练模型时间较长，它不适用于在线推荐场景，综合各种协同过滤推荐方法，取长补短，这样的推荐方法更适合实际复杂的推荐需求。

对象相似性度量

在介绍4种协同过滤推荐方法之前，我们先介绍一下有关相似性度量的问题：
基于协同过滤推荐方法，通过计算用户相似度、物品相似度来进行个性化推荐，那么我们结合 Mahout 机器学习库来说明各种相似性度量的计算方法，Mahout 提供了分别针对用户、物品给出了一些相似性度量计算实现，有些是用户、物品可以共同使用的，如下类图所示：

上图中，绿色表示计算用户之间相似度、物品之间相似度都可以使用的相似性度量，而 SpearmanCorrelationSimilarity 只能用于计算用户的相似度。各种相似度说明如下所示：

• EuclideanDistanceSimilarity

欧几里德距离，又称欧氏距离，在 n 维欧式空间中，计算欧几里德距离的公式，如下所示：

其中，x、y 表示两个点的坐标，d(x,y) 表示点 x 和 y 之间的距离。

• PearsonCorrelationSimilarity

对于两个数据集 X、Y，他们的相关性可以使用皮尔逊相关系数来表达，计算皮尔逊相关系数的公式，如下所示：

其中，n 分别表示两个数据集 X 与 Y 中数据点的个数，xi 表示数据集X中第 i 个数据点，yi 表示数据集 Y 中第 i 个数据点。

• UncenteredCosineSimilarity

余弦相似度通过计算两个向量的夹角的余弦值，来表示两个向量的相似性，它的计算公式，如下所示：

其中，A和B表示两个向量。

• LogLikelihoodSimilarity

Mahout 采用了 log-likelihood ratio（LLR）的方法计算相似度，对于事件 A 和事件 B，我们考虑两个事件发生的次数，具有如下事件矩阵：

	Event A	Everything but A
Event B	k11	k12
Everything but B	k21	k22

其中：
k11：事件 A 与事件 B 同时发生的次数
k12：B 事件发生，A 事件未发生
k21：A 事件发生，B 事件未发生
k22：事件 A 和事件 B 都未发生
那么，计算 LLR 的公式如下：

其中，H表示香农熵。
在Mahout中给出的实现，如下代码所示：

  public static double logLikelihoodRatio(long k11, long k12, long k21, long k22) {
    Preconditions.checkArgument(k11 >= 0 && k12 >= 0 && k21 >= 0 && k22 >= 0);
    // note that we have counts here, not probabilities, and that the entropy is not normalized.
    double rowEntropy = entropy(k11 + k12, k21 + k22);
    double columnEntropy = entropy(k11 + k21, k12 + k22);
    double matrixEntropy = entropy(k11, k12, k21, k22);
    if (rowEntropy + columnEntropy < matrixEntropy) {
      // round off error
      return 0.0;
    }
    return 2.0 * (rowEntropy + columnEntropy - matrixEntropy);
  }

具体可以查阅相关资料。

• TanimotoCoefficientSimilarity

Tanimoto 相关系数来源于 Jaccard 距离，它表示两个数据集的相异度，即不相似度量。
计算 Tanimoto 相关系数的公式，如下所示：

其中，A 和 B 表示两个向量。

• CityBlockSimilarity

曼哈顿距离有很多种叫法：城市街区距离、L1 距离、L1 范数、曼哈顿长度、Taxicab 距离（出租车距离）。计算曼哈顿距离的公式，如下所示：

其中，x 和 y 表示两个 n 维向量。

• SpearmanCorrelationSimilarity

Spearman 相关系数的计算公式，如下所示：

其中，di=xi-yi，n 表示数据集的大小，xi 与 yi 分别是数据集 X、Y 中的数据点。

下面，我们会对上面提到的4种协同过滤方法进行详细说明，其中会结合 Apache Mahout，并给出相应的实现代码，以求能够更好地理解各种协同过滤方法。

基于用户的协同过滤推荐

基于用户的协同过滤推荐，不考虑用户、物品的属性（特征）信息，它主要是根据用户对物品的偏好（Preference）信息，发掘不同用户之间口味（Taste）的相似性，使用这种用户相似性来进行个性化推荐。基于用户的协同过滤推荐，它是以用户为中心，观察与该用户兴趣相似的一个用户的群体，将这个兴趣相似的用户群体所感兴趣的其他物品，推荐给该用户。下面我们通过一个例子来说明，如下图所示：

如上图，以用户 U1 为中心，用户 U1 对物品 I12、I13、I14 有偏好行为，用户 U3 对物品 I12、I13、I14、I31、I32、I33 有偏好行为，而物品 I12、I13、I14 是用户 U1 和用户 U3 共同有偏好行为的物品，那么可以将用户 U3 有偏好行为但是用户 U1 没有的物品 I31、I32、I33 推荐给用户 U1。
下面通过使用 Mahout 机器学习库实现，基于用户的协同过滤推荐，来了解计算用户相似度的方法，代码如下所示：

        final DataModel model = new FileDataModel(new File("src/main/resources/u.data"));
        UserSimilarity similarity = new PearsonCorrelationSimilarity(model);
        int n = 20;
        UserNeighborhood neighborhood = new NearestNUserNeighborhood(n, similarity, model);

        final UserBasedRecommender recommender = new GenericUserBasedRecommender(model, neighborhood, similarity);
        long userID = 200;
        int topN = 10;
        List<RecommendedItem> recommendations = recommender.recommend(userID, topN);
        for (RecommendedItem recommendation : recommendations) {
            System.out.println(recommendation.getItemID() + ": " + recommendation.getValue());
        }

对于编号为 200 的用户，使用皮尔逊相关系数（PearsonCorrelationSimilarity ）和 NearestNUserNeighborhood 计算用户相似度，得到的 Top 10 推荐物品及其评分列表，如下所示：

316: 5.0
895: 4.6441307
100: 4.6418004
315: 4.564026
896: 4.5467043
285: 4.5023627
344: 4.475635
346: 4.4689593
272: 4.4235177
750: 4.297509

基于用户的协同过滤推荐，比较适合于用户数量少于物品数量的应用，这样，通过更多的用户对物品的偏好行为历史数据，维护用户的相似关系，能够更好地计算出用户的相似性。

基于物品的协同过滤推荐

基于物品的协同过滤推荐，也不考虑用户、物品的属性（特征）信息，它也是根据用户对物品的偏好（Preference）信息，发掘不同物品之间的相似性。基于物品的协同过滤推荐，是以物品为中心，通过观察用户对物品的偏好行为，将相似的物品计算出来，可以认为这些相似的物品属于特定的一组类别，然后根据某个用户的历史兴趣计算其所属的类别，然后看该类别是否属于这些成组类别中的一个，最后将属于成组类别所对应的物品推荐给该用户。下面我们也通过一个例子来说明，如下图所示：

上图中，用户 U1 对物品 I5 和 I6 有偏好行为，用户 U3 对物品 I1 和 I6 有偏好行为，那么我们可以向 U1 推荐用户 U3 所感兴趣的物品 I1。同样，用户 U7 对物品 I3、I4、I7 有偏好行为，用户 U9 对物品 I4、I5、I7 有偏好行为，那么我们可以向用户 U7 推荐用户 U9 所感兴趣的物品 I5，因为用户 U7 和用户 U9 都对 I4、I7 有过偏好行为；可以向用户 U9 推荐用户 U7 感兴趣的物品 I3，这个 2 个用户可能对彼此其他感兴趣的物品也都会发生偏好行为。
基于用户的协同过滤推荐，使用 Mahout 机器学习库计算，来了解计算物品相似度的方法，代码如下所示：

        final DataModel model = new FileDataModel(new File("src/main/resources/u.data"));
        ItemSimilarity similarity = new LogLikelihoodSimilarity(model);

        final ItemBasedRecommender recommender = new GenericItemBasedRecommender(model, similarity);
        long userID = 200;
        int topN = 10;
        List<RecommendedItem> recommendations = recommender.recommend(userID, topN);
        for (RecommendedItem recommendation : recommendations) {
            System.out.println(recommendation.getItemID() + ": " + recommendation.getValue());
        }

对于编号为 200 的用户，使用对数似然（PearsonCorrelationSimilarity ）计算物品相似度，得到的 Top 10 推荐物品及其评分列表，如下所示：

1431: 4.6409993
1156: 4.494837
1127: 4.4886928
1234: 4.481482
1294: 4.442889
1122: 4.442692
1654: 4.419746
1593: 4.419684
1595: 4.392633
1596: 4.392633

基于物品的协同过滤推荐，比较适合于物品远远少于用户的应用，这样可以更好地维护物品之间的相似关系。

基于模型的协同过滤推荐

基于模型的协同过滤推荐，是采用机器学习的方法，通过离线计算实现推荐的，通常它会首先根据历史数据，将数据集分成训练集和测试集两个数据集，使用训练集进行训练生成推荐模型，然后将推荐模型应用到测试集上，评估模型的优劣，如果模型到达实际所需要的精度，最后可以使用训练得到的推荐模型进行推荐（预测）。可见，这种方法使用离线的历史数据，进行模型训练和评估，需要耗费较长的时间，依赖于实际的数据集规模、机器学习算法计算复杂度。有关推荐模型的计算方法，通过机器学习算法实现，我们简单说明一下。
对于我们的用户历史行为数据，我们关注的是用户与物品之间的关系，可以生成一个用户-物品矩阵，矩阵元素表示用户对物品的偏好行为（或者是评分），如果用户和物品的数量都很大，那么可见这是一个超大稀疏矩阵，因为并不是每用户都对所有的物品感兴趣，只有每个用户感兴趣的物品才会有存在对应的偏好值，没有感兴趣的都为空缺值，最终我们是要从这些空缺值对应的物品中选择出一些用户可能会感兴趣的，推荐给用户，这样才能实现个性化推荐。
下面，我们假设使用用户-物品的评分矩阵来实现推荐，定义评分矩阵为 R，那么通过将 R 分解为另外两个低秩矩阵 U 和 M，由于R是稀疏矩阵，很多位置没有值，只能通过计算使用 U 与 M 的乘积近似矩阵 R，那么只要最终得到的误差尽量小，能满足实际需要即可，一般使用均方根误差（Root mean square error，RMSE）来衡量，那么就要计算一个目标函数的最小值，如下函数公式所示：

如果计算该目标函数的最小值，可能需要大量的迭代计算，甚至是不可行的，在满足实际需要精度的前提下，那么我们可以允许一定的误差，通过设定多个参数来控制计算。计算矩阵分解有很多方法，如：随机梯度下降（Stochastic gradient descent，SGD）、交替最小二乘法（Alternating Least Squares，ALS）、加权交替最小二乘法（ALS with Weighted-λ-Regularization，ALS-WR），有关实际计算的理论，可以参考相关资料。
Mahout 采用了 ALS-WR 方法实现矩阵分解，目标函数如下公式所示：

其中：

这里，alpha 表示的是置信参数，在 Mahout 中使用隐式反馈（Implicit Feedback ）选项时，需要指定该参数；lambda 表示的是正则化参数，为了防止求解得到的模型过拟合（Overfitting），在目标函数上，加上一个正则项。
我们可以通过它提供的 API 来实现一个离线的基于模型的协同过滤推荐，下面我们基于 MovieLens 数据集，介绍具体使用过程：

• 准备训练集和测试集

我们选择使用 MovieLens 数据集，2 亿的评分数据（大约有 500 多 MB），首先将数据集进行分割：80% 用作训练集，20% 用作测试集，Mahout 提供分割数据集的工具，分割执行如下命令：

bin/mahout splitDataset -i /test/shiyj/data/ml-20m/ratings.csv -o /test/shiyj/data/splitDS -t 0.8 -p 0.2 --tempDir /tmp/mahout/

这样，生成2个数据集：/test/shiyj/data/splitDS/probeSet和/test/shiyj/data/splitDS/trainingSet。

• 训练推荐模型

使用训练集 /test/shiyj/data/splitDS/trainingSet 来训练推荐模型，执行如下命令：

bin/mahout parallelALS -i /test/shiyj/data/splitDS/trainingSet -o /test/shiyj/data/output/als --lambda 0.1 --implicitFeedback true --alpha 0.065 --numFeatures 10 --numIterations 10 --numThreadsPerSolver 2 --tempDir /tmp/mahout

上面命令执行结果，数据会在 /test/shiyj/data/output/als/ 目录下面，可以看到生成如下目录：

/test/shiyj/data/output/als/U
/test/shiyj/data/output/als/M
/test/shiyj/data/output/als/userRatings

这些目录下的文件就是推荐模型对应的数据文件，可以用于后面步骤中的评估和最终推荐。

• 评估模型

评估模型使用 Mahout 的 evaluateFactorization 命令，需要输入上一步生成的模型文件，如下所示：

bin/mahout evaluateFactorization -i /test/shiyj/data/splitDS/probeSet -o /test/shiyj/data/output/als/rmse --userFeatures /test/shiyj/data/output/als/U --itemFeatures /test/shiyj/data/output/als/M --tempDir /tmp/mahout/rmse

可以看到，最后输出了 RMSE，在文件 /test/shiyj/data/output/als/rmse/rmse.txt 中。

• 推荐

如果我们训练得到的模型在评估以后，误差能够满足实际推荐业务需要，则可以直接用于实际的推荐系统。Mahout提供了一个基于命令行的推荐方式，可以使用recommendfactorized命令，如下所示：

bin/mahout recommendfactorized -i /test/shiyj/data/output/als/userRatings -o /test/shiyj/data/output/als/recommendations --userFeatures /test/shiyj/data/output/als/U --itemFeatures /test/shiyj/data/output/als/M --numRecommendations 10 --maxRating 5

上面指定了，为每个用户选择 Top 10 个物品作为推荐，并计算出了评分，执行上述命令，得到推荐结果，在目录 /test/shiyj/data/output/als/recommendations 中，该目录下的文件内容，示例如下所示：

1    [2571:0.65515196,1214:0.63967377,1210:0.5870833,1206:0.58017606,750:0.53064054,1270:0.52714694,1527:0.492824,5952:0.4770518,480:0.4517607,1580:0.43877804]
2    [1196:0.22062394,1210:0.21882197,1198:0.19199324,1240:0.1805339,2571:0.17224884,1200:0.16999668,1291:0.15613373,858:0.14950913,1097:0.14854312,1197:0.1480078]
3    [1196:0.8909414,1214:0.8081364,1270:0.6871423,924:0.64723164,858:0.6388401,1136:0.6263018,1291:0.58192265,1036:0.56856805,750:0.55387926,296:0.5497311]
4    [457:0.34563774,592:0.3424035,150:0.32874095,590:0.32829174,349:0.3071443,153:0.29904938,316:0.29723072,110:0.28530872,344:0.28501293,434:0.27692935]
5    [1:0.64543045,356:0.55862373,733:0.48568383,32:0.48033717,588:0.46519792,62:0.46215564,590:0.4575655,110:0.44682676,597:0.420567,95:0.41918993]
6    [648:0.45023045,736:0.4386352,95:0.34667525,786:0.3351175,1073:0.32370603,32:0.31021506,1210:0.30251333,608:0.2933381,7:0.28936782,36:0.28653657]
7    [1198:0.52251583,2028:0.51249886,1210:0.5006326,1197:0.48272145,1291:0.46804646,2571:0.45988122,1784:0.45771137,2797:0.4538604,1610:0.45373544,1704:0.4534099]
8    [480:0.86542463,318:0.7133561,434:0.6677318,185:0.6504521,208:0.6451925,161:0.64106977,253:0.6124166,34:0.5435114,586:0.5240867,288:0.50809836]
9    [2858:0.16401465,2762:0.12627697,2571:0.123330824,2997:0.11046047,296:0.10837068,2028:0.10639984,2329:0.103341825,1704:0.10107514,1089:0.100894466,50:0.098862514]
10    [1270:0.32084247,2571:0.2983431,608:0.29643345,1291:0.29354194,780:0.2851402,1036:0.27120706,1214:0.2681493,1197:0.26402688,1097:0.2634927,1200:0.24816594]

实际应用中，为了加快在线上推荐系统的检索，这些结果，可以考虑将数据存储到 ElasticSearch 或者 SolrCloud 系统中，方便搜索查询。

混合协同过滤推荐

我们前面已经了解到，各种推荐方法都有其优点和缺点，那么对于实际复杂的需求，没有一种推荐方法能解决所有的问题，所以根据不同的需求采用组合多种推荐方法，共同来完成实际的推荐需求。
我们引用 IBM Developerworks 上一篇文章中介绍的，基于混合协推荐的实现方法，常用的有如下几种：

1. 加权的混合（Weighted Hybridization）: 用线性公式将几种不同的推荐按照一定权重组合起来，具体权重的值需要在测试数据集上反复实验，从而达到最好的推荐效果。
2. 切换的混合（Switching Hybridization）：其实对于不同的情况（数据量，系统运行状况，用户和物品的数目等），推荐策略可能有很大的不同，那么切换的混合方式，就是允许在不同的情况下，选择最为合适的推荐机制计算推荐。
3. 分区的混合（Mixed Hybridization）：采用多种推荐机制，并将不同的推荐结果分不同的区显示给用户。
4. 分层的混合（Meta-Level Hybridization）: 采用多种推荐机制，并将一个推荐机制的结果作为另一个的输入，从而综合各个推荐机制的优缺点，得到更加准确的推荐。

我们可以想到，根据前面介绍的基本协同过滤推荐方法，作为入门，可以这样实现一个混合协同过滤系统：

• 根据用户的历史行为数据，离线计算推荐模型，得到模型 A；
• 为了使推荐满足实时行要求，可以选择使用基于用户的协同过滤推荐/基于物品的协同过滤推荐，基于实时用户行为数据，得到模型 B；
• 对于用户的冷启动问题，可以考虑采用统计的方式，找到热门的物品推荐给新用户，得到模型 C；
• 对于老用户，可以将模型 A 和 B 的结果进行一个排序筛选，得到一个新的 Top N 推荐列表。

这样，得到的推荐系统，就是一个混合推荐系统。

参考资料

• https://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy1/
• https://en.wikipedia.org/wiki/Collaborative_filtering
• http://www.fuqingchuan.com/2015/03/812.html
• https://en.wikipedia.org/wiki/Spearman%27s_rank_correlation_coefficient
• https://en.wikipedia.org/wiki/Taxicab_geometry
• https://en.wikipedia.org/wiki/Jaccard_index#Tanimoto_similarity_and_distance
• https://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient
• http://blog.csdn.net/fansy1990/article/details/12259975
• http://www.statlect.com/normal_distribution_maximum_likelihood.htm
• http://tdunning.blogspot.jp/2008/03/surprise-and-coincidence.html
• http://tech.meituan.com/mt-recommend-practice.html
• http://grouplens.org/datasets/movielens/
• Apache Mahout Essentials
• Large-scale Parllel Collaborative Filtering for the Netflix Prize
• 项亮：《推荐系统实践》