保护私人版权，尊重他人版权。转载请注明出处并附带页面链接
前言
上一篇翻译并分享了一篇微软的推荐系统实践案例：SAR——推荐系统实践笔记，本篇翻译并分享sar原理，原文地址：SAR Deep Dive。
正文
在该案例中，我们将在单机执行Python脚本的条件下，描述 Simple Algorithm for Recommendation (SAR) 算法的每一个步骤。
SAR是基于用户操作历史的个性化推荐系统，具有快速、可扩展、自适应的特点。它基于物品间的相似度，向用户推荐与他们已有的喜好相似的物品。
1. SAR算法
接下来从高层次介绍SAR架构。
在这个较高的层次来说，SAR会创建下述两个中间矩阵，用于构造推荐评分：
- 基于物品间关联性构造的物品相似度矩阵 S。
- 基于用户-物品关联性构造的用户喜好矩阵 A。
物品关于用户的推荐评分即通过创建矩阵 A 与 S，并执行矩阵积运算 A x S求得。
其他可选项（如『时效性』和『移除已知物品』）在后文有详细描述。
名词对照
| 英文 | 中文 |
|---|---|
| Transaction data | 用户操作记录 |
| Item-Item similarity matrix | 物品相似度矩阵 |
| User-Item affinity matrix | 用户喜好矩阵 |
| time dacay | 时间衰减、时效性 |
| remove seen items | 移除可见物品、移除已知物品 |
1.1 计算物品共现度和物品相似度
SAR通过物品共现度确定物品间相似性，而两个物品间的共现度是它们共同出现在同一用户的次数。我们可以这样展示所有物品间的共现度：在一个 m x m 的矩阵 C 中，元素 c(i, j) 表示物品 i 与 j 共同出现的次数。
共现矩阵 C 具有如下属性：
- 对称性—— c(i, j) = c(j, i)
- 非负性—— c(i, j) ≥ 0
- 对角线值最大——两个物品的共现次数一定小于等于他们的出现次数，即 **c(i, j) ≤ c(i, i), (∀ j ≠ i)**。
当我们获得共现矩阵后，对共现矩阵作尺度变换，即可求得相似性矩阵，尺度变换的方式包括 Jaccard、lift**(1)**、或counts（不经过尺度变换，共现矩阵即作为相似度矩阵）。
lift，提升度：一种描述两个数据集之间关联性的度量，通常被用于评估模型。在这里被用于描述i、j的关联性。
如果 c(i, i) 和 c(j, j) 是对角线元素，则这三种变换的公式如下：
| Name | rescalling |
|---|---|
| Jaccard | s(i,j) = c(i,j) / [ c(i,i) + c(j,j) - c(i,j) ] |
| lift | s(i,j) = c(i,j) / [ c(i,i) + c(j,j) ] |
| counts | s(i,j) = c(i,j) |
一般而言，我们使用 counts 作为相似性度量可提高推荐结果的可预测性**(1)，即多数推荐结果都是用户最可能喜欢的结果。与之相比， lift 则倾向于发现性/偶然性(2)**:『虽然只有少数人喜欢，但喜欢的人评价都很高』的推荐结果。而 Jaccard 此时即作为他们二者的这种方案。
1&2：推荐系统有很多评价指标，包括：精度、覆盖度、置信度、信任度、新颖度、惊喜度、多样性、健壮性、稳定性、可扩展性等。其中，与文中所提 发现性/偶然性 相似的概念是 新颖度和惊喜度。值得注意的是，每个指标都不是越高越好，很多指标往往是对立的，我们需要视实际需要，灵活调整。
1.2 计算用户喜好
在SAR中，喜好矩阵存储每个用户与其操作过的物品之前的关联性。用户喜好受如下两个因素影响：
- 不同事件流具有不同的权重——比如，用户对某个物品的评价行为比用户浏览该物品具有更高的权重
- 用户关于某个物品的操作发生时间——比如，该操作记录发生时间较久远，则此时该记录对用户喜好的影响较少
考虑这两个因素后，可以得到关于用户-物品喜好的计算表达式：
用户 i 关于物品 j 的喜好 a(i, j) 是用户i关于物品j的所有事件的加权和，并使用 2 的幂运算来控制时效性（每个事件对结果的影响程度随时间衰减）。假定参数 T 具有半衰期，则用 (1/2)^n 作为计算模型：则在事件流T中，t_0 之前的一个事件对运算结果的影响只有 t_0 事件的一般 **(1)**。
- 这句话我可能翻译的不太好，原句是：The (1/2)^n scaling factor causes the parameter T to serve as a half-life: events T units before t_0 will be given half the weight as those taking place at t_0.
重复上述计算过程，得到所有n个用户关于m个物品的 n x m 喜好矩阵 A。此外，我们可以按实际需求选择一下两种方法简化这个表达式：
- 任何事件权值 w 都为1——忽略不同事件的差异。
- 半衰期参数T设置为无穷大——忽略喜好的时间衰减因素。
1.3 移除已知物品(Remove seen item)
我们可以选择删除已经存在于训练集中的物品，比如说：我们不可能向用户推荐他们已经买过的商品。
1.4 计算评分最高的k个物品(Top-k item calculation)
如前文所述，一组用户的个性化推荐是通过将用户喜好矩阵A 与 物品相似度矩阵 S 相乘得到的。输出结果是一个评分矩阵，行表示用户，列表示物品，每个元素表示了一个用户关于一个物品的评分（预测值/已知值），此时，分数越高，表明其越可能符合用户需求，则越优先向用户推荐。
top-k问题 是推荐系统中的常见问题，该问题提示我们，通常我们可以将更多的计算成本花费在更有价值的 用户/物品 上。与top-k问题常放在一起思考的还有 长尾效应。
译者小结
这篇文章脱离了代码，深入讲解SAR算法原理。实际上，在原文中，这篇文章还有两个部分，是代码实践，内容与我的另一篇译文内容基本一致《SAR——推荐系统实践笔记 》，甚至实践方面，那篇文章东西更多一些，因此这里不赘述了。
本篇用Jacarrd 系数作为相似度度量其实并不实用，我们在实践中会有更多问题，除了时效性、不同事件的权值，还包括：
- 某个物品被越多的用户使用，其评分可能越可靠
- 某个用户的数据记录越多，其对物品的评分可能越可靠
- 物品之间可能评分相似，但实际属性并不相似
and so on…
要解决这些问题，用 Jaccard系数 实现并不灵活，个人更倾向于选择 余弦相似度 / Pearson系数 的方式，这两者在基于用户的近邻搜索推荐和基于物品的近邻搜索推荐中，具有不同的特性，但共同点是，我们可以很容易的为各个参数加权来解决一些问题，且通过单一的计算模型，可以简化代码，这可能可以提升我们的程序性能、可扩展性等。但这目前译者没有可靠的数据证实这一想法，欢迎同学们提出意见/建议，交流学习。
