推荐系统：个性化推荐-协同过滤

问题导读：
1. 什么是协同过滤？
2. UserCF主要思想是什么？
3. 用户相似度的度量方法有哪些？
4. UserCF存在的问题有哪些？如何改进？
5. ItemCF的主要思想是什么？
6. ItemCF如何实现？
7. ItemCF如何进行改进？
8. UserCF和ItemCF的相比较各自的特点是什么？

（个性化）推荐系统构建三大方法：基于内容的推荐content-based，协同过滤collaborative filtering，隐语义模型(LFM, latent factor model)推荐。这几种方法都是个性化推荐，非个性化推荐参考。这篇博客主要讲个改化推荐中的协同过滤。

协同过滤Collaborative Filtering

协同过滤Collaborative Filtering：使用某人的behavior来预测其它人会做什么。协同过滤就是基于邻域的算法，分为基于用户的协同过滤算法UserCF和基于物品的协同过滤算法ItemCF。

基于用户的协同过滤算法UserCF

User-user collaborative filtering主要思想

对于一个用户x，首先找到与其相似的一个用户集，这个相似是通过它们的评分rating来判定的，likes和dislikes越相似，他们就越相似。然后推荐这些相似用户集喜欢的items并且预测x评分最高的items给用户x。

UU：兴趣相投的用户可能带来新颖的东西

UserCF的两个假设

Assumption: Our past agreement predicts our future agreement
Base Assumption #1: Our tastes are either individually stable or move in sync with each other. 也就是个人品味稳定或者和品味相同的人同步迁移。
Base Assumption #2: Our system is scoped within a domain of agreement(e.g Politics, humor, technology). UserCF推荐系统中的item要是同一个领域中的，不然虽然喜欢同样的两个东西，但是不在同一领域，实际上也是没有什么关联的？

UserCF要解决的问题

已知用户评分矩阵Matrix R
R_{ui}: the rating from user u on item I
A very sparse matrix（一般都是稀疏的）
Question
To infer the values in the empty cells

非个性化方法的解决思路

1 直接使用对item i评分过的所有用户的平均评分作为user a对item i的评分

2 考虑到给分偏颇，计算评分均值时都减去每个单独用户的评分均值。
给分者的偏颇问题：tough raters:给分相对较小的，不慷慨的。easy raters:给分总是比较高的，慷慨的（不同用户的给分程序是不一样的（如有的用户很mean，给分都很低，有的很generous，给分都很高，所以所有用户减去其给分的均值比较好）。

Note: 1 这个评分可能超出评分最大值May be out of the rating scale，但是我们是要做推荐，只要计算最大topk个item推荐出去就可以了，超出范围没关系。

2 易知做推荐时，user a对item i的评分pai可以不加上bar(ra)，加上只是在后面的评估模型中有用。

个性化推荐的解决思路
改进上面的非个性化思路，计算均分时只考虑与当前user a相似的用户对item i的评分，这样对item i的评分都有一个权重（正比于user u和user a的相似度）。

Note: 1 \bar{r}_u is the average value over all the ratings of u
2 Remove the neighbors with negative agreement values . wa,u如果是负值，则去掉（或者等价设置为0？）。

How to select the neighborhoods用户相似的度量方法

用户-电影矩阵

Note: 这里A喜欢TW讨厌SW1，而C喜欢SW1讨厌TW。

Jaccard Similarity

jaccard相似度没有考虑评分，导致相似度计算错误。

Spearman rank correlation

Hasn't been found to work as well here

Cosine Similarity

这里将不知道的值设置为0

但是由于将缺失值设为0(从上节可以看出评分为0（最小的评分值）实际上是评分为负[参考上节：基于内容的推荐Content-based System-用户profile建立示例])，也没有揭示出A,B相似度远大于A,C相似度的直觉知识。

Centered Cosine(Pearson Correlation) 1

这里归一化时减去的是user所有评分的均值，考虑所有的items。（这里就相当于空值填充为了每行user的均值，这样空值就不会影响两个向量点积）

注意现在行和都为0了，也就是用户评分均值为0，>0表示喜欢，＜0表示不喜欢。缺失值当然也就设置为0，表示既不like也不dislike。

皮尔逊相关系数将缺失值设置为均值，符合没打分的要求；同时也解决了给分者的偏颇问题。tough raters:给分相对较小的，不慷慨的。easy raters:给分总是比较高的，慷慨的。

Pearson Correlation Coefficient 2

这里归一化时user减去的是和当前uesr a都打过分的分数均值，计算相似度时只考虑in common的items（港真，lz觉得这个不合理，毕竟和别人对比应该拿自己和别人相似和不相似处的一起比）。

Note: Here, \bar{r}_u is the average value over the ratings of u on the items both u and a have rated 且m是user a和user u共同打分过的items数目。

[距离和相似性度量方法]

U-U CF算法

For a user a
Compute its similarity values to all the other users, Identify its nearest neighbors
With the nearest neighbors, for each item i
Predict r_{ai}

UserCF存在的问题及issues改进

理论问题Low coverage
For a new user, which has only few ratings. 这样就找不到邻居用户。
For an item, on which all the nearest neighbors have few ratings.

实现时候的问题Implementation Issues
Given m users and n items
Computation can be a bottleneck
      Correlation between two users is O(n)
      All correlations for a user is O(mn)
      All pairwise correlations is O(m^2n)
      Recommendations at least O(mn)
Lots of ways to make more practical
      More persistent neighborhoods
      Cached or incremental correlations

改进User-User Variations and Tuning

改进方法：
Similarities
Significance weighting
Variance weighting
Selecting neighborhoods
Normalizing ratings

1 Similarities

相似度计算最好使用Pearson Correlation Coefficient，或者Spearman ranking correlation。

2 Significance weighting

Consider the number of co-rated items, multiply by min(n,50)/50
n is the number of common ratings, 50 is the cutoff number
共同打分多的两个用户相似的可能性更高。

3 Variance weighting（然并卵）

Considering the rating variance for an item. 原因是，对某个item如果其评分波动大，也就是不同人有不同意见，这样item对应的评分对于比较两个用户的差异更重要（如一个大家都喜欢的评分都高的Titanic相对于一部评分波动大的恐怖片的重要性可能小些，因为喜欢恐怖片的用户和不喜欢恐怖片的用户其打分肯定相差大）。

Variance weighting

Z-score based

然而实验表明，这个在UserCF中并没有什么卵用。

4 Normalizing ratings

why?
Users rate differently
Some rate high, others low, 也就是前面说的给分者的偏颇问题
Averaging ignores these differences
Normalization compensates for them

4.1 Rating Normalization: Mean-centering

May be out of the rating scale

4.2 Rating Normalization: z-score normalization

实际上这样对数据进行转换之后，就不用Pearson Correlation Coefficient来计算相似度了，这时的cosine相似度就和Pearson Correlation Coefficient一样的了。lz建议直接对数据进行这种变换，后面就不用考虑复杂了。

5 Selecting neighborhoods

Threshold similarity：设置一个阈值，相似度大于这个阈值就作为nerghborhoods
Top-N neighbors by similarity: 一般Top 30
Combined：这个更好吧
选择How Many Neighbors?的问题

In theory, the more the better
If we have a good similarity measure
In practice, noise from dissimilar neighbors decreases usefulness
Between 25 and 100 is often used
Fewer neighbors → lower coverage
Use the same group of neighbors for different items
Give up personalized recommendation if the neighbors do not have enough ratings on the target item

评分预测

迭代求出与x最相似的k个用户，预测x对这k个用户也评分过的items i 的评分

[1999_SIGIR An Algorithmic Framework for Performing Collaborative Filtering.pdf]

基于物品的协同过滤算法ItemCF

ItemCF的Motivation和Idea

User-User CF的问题
Issues of Sparsity
Amazon: millions of items, each user rates hundreds of items
With large item sets, small numbers of ratings, too often there are points where no recommendation can be made
Many solutions proposed here, including item-item, and dimensionality reduction
Computational performance
With millions of users (or more), computing all-pairs correlations is expensive
Even incremental approaches were expensive
And user profiles could change quickly – needed to compute in real time to make users happy

The Item-Item Insight

Item-Item similarity is fairly stable …
This is dependent on having many more users than items. Average item has many more ratings than an average user
Intuitively, items don’t generally change rapidly – at least not in ratings space (special case for time-bound items)
Item similarity is a route to computing a prediction of a user’s item preference

基于物品的协同过滤算法Item-item collaborative filtering（简称ItemCF）给用户推荐那些和他们之前喜欢的物品相似的物品。
比如，该算法会因为你购买过《数据挖掘导论》而给你推荐《机器学习》。不过，ItemCF算法并不利用物品的内容属性计算物品之间的相似度，它主要通过分析用户的行为记录计算物品之间的相似度。基于物品的协同过滤算法可以利用用户的历史行为给推荐结果提供推荐解释，比如给用户推荐《天龙八部》的解释可以是因为用户之前喜欢《射雕英雄传》。

ItemCF的假设和限制Core Assumptions/Limitations

Item-item relationships
Your taste obeys that of most people
Main limitation/complaint: lower serendipity新奇新颖性不够。
Compared with the UU CF, 因为UU算法中兴趣相投的用户可能带来新颖的东西，II算法更能选出特别相似的items，更个性化。

优点Benefits of Item-Item

It actually works quite well
Good MAE performance on prediction; good rank performance on top-N
Efficient implementation
At least in cases where |U| >> |I|
Benefits of pre-computability. 提前计算出item之间的相似度保存着。
Item-item is efficient and straightforward
A few parameters need tuning for specific data, domain

复杂度Complexity
Pre-compute similarities for all pairs of items
Item stability makes similarity pre-computation feasible
Naïvely: O(|I|)2
If symmetric: only need to compute one direction
[Hui Xiong, Wenjun Zhou, Mark Brodie, and Sheng Ma (2008). TOP-K Φ Correlation Computation. INFORMS Journal on Computing (JOC). Volume 20, Number 4, pp. 539-552.]

ItemCF算法

Pre-compute item similarities over all pairs of items
Look for items similar to those the user likes Or has purchased Or has in their basket
也就是Two step process:
Compute similarity between pairs of items. 计算items之间的相似度，3种方法
      Correlation between rating vectors
         co-rated cases only (only useful for multi-level ratings)
      Cosine of item rating vectors
         can be used with multi-level or unary ratings
      Adjusted cosine (normalize each user’s ratings)
         to adjust for differences in rating scales
Predict user-item rating
Weighted sum of rated “item-neighbors” (examples)

简单来说，就是预先计算好items之间的相似度，通过user u评分过的items和某个要评分的item i的相似度加权（下面公式）计算预测的评分。

物品相似度度量Item Similarity

For two item rating vectors
Cosine similarity
Normalization first: subtract user mean
For two unary vectors (buy or not, click or not)
Jaccard index

邻居选择策略Neighborhood selection strategy: Picking Neighbors

邻居的选择
为了预测user u对item i的打分，要知道下面这些
To predict the rating of user u on item i
For a user u
R_u: the set of items user u has rated
For item i
Neighbor_i: the set of items which are in the top k similar item set to item i
Item j is in the intersection of R_u and Neighbor_i

也就是如果item i的邻居和user u打分过的items越相似，user u对item i的打分就会更高。
但是如果item i的邻居和user u打分过的items几乎没有重叠，那预测会相当差，就没必要推荐了，放弃。
The intersection of R_u and Neighbor_i
Two small: give up prediction

邻居数目的选择

Good value of k important
k too small → inaccurate scores
k too large → too much noise (low-similarity items)
k = 20 often works well

评分预测Item score aggregation function

For each item to score
Find the similar items the user has rated
Compute the weighted average of user’s ratings

ItemCF调参Tuning the model

Tune using cross-validation
Need to find good values for
Similarity function (normalization or not)
Neighborhood size k

Item-Item CF示例

estimate rating of movie 1 by user 5

ItemCF算法的改进和拓展extensions to Item-item Collaborative Filtering

UserCF的改进也可以应用到ItemCF中来，不过其中的
significant weight可能没用，因为item对应的数目一般较多

variance weight：某个user的variance很小，打分基本不变，对结果贡献可能小
normalization：没必要了？ unary data才有必要。

1 惩罚流行度，提高覆盖率和新颖度

原始ItemCF算法的覆盖率和新颖度都不高，这是由于哈利波特效应：

上面的问题换句话说就是，两个不同领域的最热门物品之间往往具有比较高的相似度。这个时候，仅仅靠用户行为数据是不能解决这个问题的，因为用户的行为表示这种物品之间应该相似度很高。此时，我们只能依靠引入物品的内容数据解决这个问题，比如对不同领域的物品降低权重等。这些就不是协同过滤讨论的范畴了。

2  Item-item on unary data

ItemCF also works well on unary data (implicit feedback): clicks, plays, purchases

数据表示
Need some matrix to represent data
Logical (1/0) user-item ‘purchase’ matrix
      Not ‘purchase’: 0
Purchase count matrix
      Log function on counts
Normalize user vectors to unit vectors
Intuition: users who like many items provide less information about any particular pair

Similarities and Aggregating Scores
Cosine similarity
Aggregating scores
For count matrix: weighted average（也就是上面普通的ItemCF算法的评分预测）
For binary matrix: sum of neighbor similarities（对应下面的公式）

3 Incorporating user importance: User Trust

Goal: incorporate user trustworthiness into item relatedness computation
User's global reputation, not per-user trust
Solution
weight users by trust before computing item similarities. 也就是在预先计算items之间的相似度时，对应的打分乘上用户的trust，代表这个打分的重要性。
High-trust users have more impact

[Massa and Avesani. 2004. ‘Trust-Aware Collaborative Filtering for Recommender Systems’. ]
ItemCF参考文献：

[Mukund Deshpande, George Karypis:Item-based top-N recommendation algorithms. ACM Trans. Inf. Syst. 22(1): 143-177 (2004)]
[Hui Xiong, Wenjun Zhou, Mark Brodie, and Sheng Ma (2008). TOP-K Φ Correlation Computation. INFORMS Journal on Computing (JOC). Volume 20, Number 4, pp. 539-552.]

UserCF和ItemCF两种算法的比较
UU CF: Getting information from the subset of people who most share your tastes
II CF: To getting information from potentially everybody in the community, but filtered so that it's the information that's relevant to the items that you have in common with them

In fact, in practice item-item collaborative filtering hugely outperforms user-user collaborative filtering for most use cases.

UserCF的推荐结果着重于反映和用户兴趣相似的小群体的热点，而ItemCF的推荐结果着重于维系用户的历史兴趣。换句话说，UserCF的推荐更社会化，反映了用户所在的小型兴趣群体中物品的热门程度，而ItemCF的推荐更加个性化，反映了用户自己的兴趣传承。

个性化新闻推荐更加强调抓住新闻热点，热门程度和时效性是个性化新闻推荐的重点，而个性化相对于这两点略显次要。因此，UserCF可以给用户推荐和他有相似爱好的一群其他用户今天都在看的新闻，这样在抓住热点和时效性的同时，保证了一定程度的个性化。UserCF适合用于新闻推荐的另一个原因是从技术角度考量的。因为作为一种物品，新闻的更新非常快，每时每刻都有新内容出现，而ItemCF需要维护一张物品相关度的表，如果物品更新很快，那么这张表也需要很快更新，这在技术上很难实现。绝大多数物品相关度表都只能做到一天一次更新，这在新闻领域是不可以接受的。而UserCF只需要用户相似性表，虽然UserCF对于新用户也需要更新相似度表，但在新闻网站中，物品的更新速度远远快于新用户的加入速度，而且对于新用户，完全可以给他推荐最热门的新闻，因此UserCF显然是利大于弊。

但是，在图书、电子商务和电影网站，比如亚马逊、豆瓣、Netflix中，ItemCF则能极大地发挥优势。首先，在这些网站中，用户的兴趣是比较固定和持久的。一个技术人员可能都是在购买技术方面的书，而且他们对书的热门程度并不是那么敏感，事实上越是资深的技术人员，他们看的书就越可能不热门。此外，这些系统中的用户大都不太需要流行度来辅助他们判断一个物品的好坏，而是可以通过自己熟悉领域的知识自己判断物品的质量。因此，这些网站中个性化推荐的任务是帮助用户发现和他研究领域相关的物品。因此，ItemCF算法成为了这些网站的首选算法。此外，这些网站的物品更新速度不会特别快，一天一次更新物品相似度矩阵对它们来说不会造成太大的损失，是可以接受的。

从技术上考虑，UserCF需要维护一个用户相似度的矩阵，而ItemCF需要维护一个物品相似度矩阵。从存储的角度说，如果用户很多，那么维护用户兴趣相似度矩阵需要很大的空间，同理，如果物品很多，那么维护物品相似度矩阵代价较大。

在实际的互联网中，用户数目往往非常庞大，而在图书、电子商务网站中，物品的数目则是比较少的。此外，物品的相似度相对于用户的兴趣一般比较稳定，因此使用ItemCF是比较好的选择。当然，新闻网站是个例外，在那儿，物品的相似度变化很快，物品数目庞大，相反用户兴趣则相对固定（都是喜欢看热门的）。

要指出的是，离线实验的性能在选择推荐算法时并不起决定作用。首先应该满足产品的需求，比如如果需要提供推荐解释，那么可能得选择ItemCF算法。其次，需要看实现代价，比如若用户太多，很难计算用户相似度矩阵，这个时候可能不得不抛弃UserCF算法。最后，离线指标和点击率等在线指标不一定成正比。而且，这里对比的是最原始的UserCF和ItemCF算法，这两种算法都可以进行各种各样的改进。一般来说，这两种算法经过优化后，最终得到的离线性能是近似的。

ref: 海量数据挖掘Mining Massive Datasets(MMDs) -Jure Leskovec courses学习笔记推荐系统Recommendation System*

机器学习Machine Learning - Andrew NG courses学习笔记
ICT Luoping's recsys lessons, summer 2016*

《推荐系统实践》-项亮