美国电商平台的个性化推荐算法实践及优化思路

本文介绍了手工艺品电商平台Etsy的个性化推荐算法实践及优化思路，计算过程分为基于历史数据建模和计算推荐结果两个阶段，采用的手段主要包括矩阵分解、交替最小二乘、随机SVD（奇异值分解）和局部敏感哈希等。

提供个性化推荐对网上购物市场非常重要。个性化推荐对买卖双方都是有利的：购买者不用自己去搜索就可以直接获得他们感兴趣的产品信息，卖家则可以以较小的市场营销代价获得更好的产品曝光度。在这篇文章中，我们将介绍我们在Esty（美国网络商店平台，以手工艺成品买卖为主要特色——译者注）中使用的一些推荐方法。所有这些方法的MapReduce实现都包含在我们的开源机器学习包“[Conjecture]”之中。

推荐的计算过程基本上由两个阶段组成。第一个阶段，我们基于历史数据矩阵建立一个用户兴趣模型。例如，他们的购买记录或他们的收藏清单。这个模型提供了用户和物品的特征向量，它们的内积给出了一个用户对于某个物品感兴趣的程度（较高的值代表更大的预估感兴趣程度）。第二个阶段，我们会计算出推荐结果，通过最大化兴趣度的估值，为每一位用户找出一组物品。

关于用户和物品的模型也可被用于其他方面，例如用于发现具有相同兴趣爱好的用户，从某一“品味”角度上看具有相似性的物品，以及可以一起购买的互补性物品等。

矩阵分解

产生推荐结果的第一阶段是将用户和物品的模型与数据相适应。在Esty中，我们处理的是“隐式反馈”的数据，只观察用户与物品的交互（如收藏或者购买）的指标。这和用户给体验过的物品打分（例如在5分制下打3分）的“显示反馈”恰恰相反。我们用一个二进制矩阵代表这个隐式反馈，每个元素的值为0或1，1代表用户喜欢（如收藏）这个物品，0代表用户没有这么做。0并不一定表示用户对这个物品不感兴趣，而只是意味着他们对该物品尚未表现出兴趣。这可能是由于他们不关心或者不感兴趣，或者是由于用户在浏览的时候还没看到这个物品。

隐式反馈数据集中，一组用户对各种物品感兴趣。请留意我们并不收集显式的不喜欢行为，只是收集用户收藏与否。

矩阵分解模型能够生效的支撑假设是：在用户和物品之间的相关度，能通过一个低维线性模型进行解释。这意味着每一个物品和用户确实对应一个未观察的实数向量，在某些细小维度上。空间的坐标对应物品项的潜在特征（可以是：该物品是否是服装，它是否有V形标识，画面的背景是否为褐色等），用户向量的元素描述了用户对这些特征的偏好。我们可以将这些向量组成矩阵，一个用于用户，一个用于物品，这样观察到的数据是通过取两个位置矩阵和添加噪声来产生的。

基础低维模型是从观察隐式反馈产生的，“d”是该模型的维度。

因此，我们为每个用户和每个物品找到了一个的可以表示它们的向量。我们计算这些向量，使得用户向量和物品向量之间的内积，接近在隐式反馈矩阵所观察到的值（在用户喜欢这个物品的情况下，这个值接近1，否则接近0）.

将一个二维模型用于上述数据集的结果是，在这个小例子中，第一个被发现的特征是物品是否是一个架子，第二个特征是：是否是一个“几何”风格。

因为在矩阵中的零不一定表示对物品不感兴趣，我们不希望强制让模型适合它们，因为用户实际上可能是对其中的一些物品是有兴趣。因此，我们找到分解，最小化加权误差函数，其中，数据矩阵的非零项比零项的权重更高。如何设置这些权重取决于矩阵的稀疏程度，并且可以通过某种形式的[交叉验证]来发现。

当我们优化上述的加权损失函数时会重构矩阵（两个因素的乘积），而这个矩阵在输入矩阵中包含0的时候会包含一些积极的元素，因为我们不强制模型适用于这些以及非零的情况。这些都是用户可能感兴趣的但还没见过的物品。出现这种情况的原因是为了使模型更好的适用，那些已经对交叉的物品集感兴趣的用户会有相似的向量，对物品同样是这样。所以，没有浏览过，但是被其他有相同兴趣的用户喜欢的物品，在重构后的矩阵中，会有一个比较高的值。

交替最小二乘法

为了优化这个模型，我们在物品矩阵和用户矩阵之间进行交替计算，并在每个阶段对加权平均误差进行最小化，保持另一个矩阵的稳定（因此命名为交替最小二乘）。在每个阶段，因为有可行的分析方案，我们可以计算加权平方误差的精确最小化。这意味着，每一次迭代都保证不会增加总误差，而是降低到两个矩阵构成一个局部最小误差函数。因此，整个过程将逐步减小误差直到达到局部最小值。最小值的量可能会有所不同，所以它可能是一个合理的想法，重复上述步骤，并选择最好的一个，虽然我们不这样做。

这种方法的R Demo代码获取方式见文章底部。

这个计算过程在MapReduce中实现起来是非常自然的。因为例如，当更新一个用户向量时，所需要的就是：他互动过的物品向量，以及一个小的平方矩阵：通过将物品矩阵和它自己的转置矩阵相乘。用这种方式计算每个用户，可以用很有限的内存，并且每个用户可以被并行更新。更新物品的方法类似。有些用户喜欢了很多物品，或者有些物品被很多用户喜欢，这些计算需要更多的内存。在这种情况下，我们对输入矩阵进行抽样，或者过滤掉这些物品，或者只取每一个用户的最近喜欢宝贝。

当我们对模型满意之后，我们可以持续的更新它（通过每晚重复ALS的几个步骤），随着越来越多信息，包括用户，商品，收藏……流入线上系统。新物品和用户能够被方便的融入模型中，只要它们与模型中已有的用户和物品之间有足够多的交互。

这种方法的生产化MapReduce代码获取方式见文章底部。

随机SVD（奇异值分解）

上面描述的交替最小二乘法，给了我们一种简单通过MapReduce对用户偏好矩阵进行因式分解的方法。然而，它的缺点是需要多次迭代，有时花费很长时间达才能到一个好的结果。一个有吸引力的替代方案是随机SVD。这个是一种较新的方法，类似于在一个超大矩阵上进行有名的SVD，采用了一个非迭代的MapReduece实现。我们将它实现为一个函数，它可以被任何一个可扩展的MapReduce Job调用。

线性代数中的一个基本结论是：通过对几个纬度进行奇异值截断后形成的矩阵，是所有同秩的矩阵中（从平方差角度来看）最佳近似的矩阵。然而，我们注意到，使用这种方法时，我们不能采用在ALS中使用的优化方法：为错误值赋于同样的“权重”的方法。但是对于某些数据集，如果其零的个数没有压倒性的超过非零，则此方法是可行的。举个例子，我们可以用它成功地为用户的收藏行为构建一个模型，而不能用它对购买行为来构建一个有用的模型，因为购买稀疏得多，权重是必要的。

这种方法的一个优点是，它产生的矩阵有不错的正则化结构，因此能更容易的在线为新用户构造向量，因为没有矩阵反转是必须的。我们还使用这个方法产生除了用户喜好以外其他物品清单的向量，例如珍藏品，或者其他用户在Etsy创建的列表。用这种方法，我们可以从其它清单中，推荐其他相关物品。

产品推荐

一旦我们有了用户和物品模型，我们就可以用它来构建产品推荐。这是大多数研究文献容易忽略的一个步骤。例如，我们不能期望以计算用户和物品矩阵的乘积，然后为每个用户找到最好的未发现的物品，因为这需要和时间成正比的物品数和用户数的乘积，而这两者都是在数亿级。

一篇研究论文建议使用一种树型数据结构，以允许所述空间的非穷尽搜索，通过削减内积太小的整个物品集中。但是，我们观察到这种方法在实践中没有很好地工作，可能是由于维数与我们使用的模型类型的祸因（数百维度）。

因此我们用近似方法去计算推荐结果。这样做是为了产生物品的第一候选集，然后根据内积对它们进行排序，并取最高的。有几种方法可以产生候选集，例如从用户喜欢收藏的商店的清单，或者那些文本上类似于用户收藏的。但是我们使用的主要方法是局部敏感性散列（LSH），其中我们把用户和物品向量的空间分成几个散列箱，再为取那些被映射到相同箱中的物品集作为每个用户化的物品集。

局部敏感哈希

局部敏感哈希是一种用于在大型数据集中查找近似最小近邻的技术。这个技术有几种变种，但是我们专注于其中一个，设计用于处理实数数据和基于欧氏距离的近似最近邻。

该方法的思想是将空间分隔成一组散列桶，以使它们在空间中靠近彼此的点有可能落入相同的桶中。我们这样做是通过在空间中构建平面中的一些数字“p”使他们都通过原点。这种划分空间分成2 ^ P凸锥体，其中每一个构成一个散列桶。

实际上，我们可以通过代表平面的法向量来实现这一点。一个点落在平面的一侧，然后由点及法线矢量内积的符号决定（如果平面是随机的，毫无疑问我们将得到非零内积，但原则上我们可以将这些点任意的分配到一侧或者另一侧）。产生这些法向量我们只需要空间中的各个方向随机均匀。众所周知，各项同性的高斯分布绘制有这样的特性。

我们对散列桶进行标号，如果一个点和第i个平面的内积为正，使得散列码的第i位为1，否则为0，这意味着每个平面负责哈希码中的一个比特。

在我们将每个点映射到各自对应的散列桶中，我们可以计算近似最近邻或者等价的近似推荐，通过检查同一个桶中的向量。平均每个桶中的数量将是2 ^ { - P}的点的总次数，因此，使用更多的平面使得过程非常有效率。但是它也降低了近似的准确度，因为它减少了附近指向任何目标点会在同一个桶的机会。

因此，要达到效率和质量的折中，我们需要重复多次散列过程，然后再合并输出。最后，为了获得更多对计算过程的控制度，我们抛弃了较大的散列箱，从而实现高效的最近邻计算。

使用Conjecture实现的代码在获取方式见文章底部。

其他思路

以上所述是个性化推荐的基本技术。在开发这些推荐系统的过程中，我们发现了一些可以改进的地方，帮助我们提高推荐的质量。

• 计算前的向量标准化：如前所述，矩阵分解模型往往会在流行的物品上产生大规模向量。结果是将一些受欢迎的物品可能推荐给许多用户，即使它们不一定是最对那些用户口味的。因此，在计算推荐结果之前，我们标准化所有物品的向量。这也让对接近最近邻理论的使用听起来可行：因为向量有统一的基准，所以用户向量的最大内积可以通过所有的最近物品向量来获得。
• 店铺多样性：Etsy是一个由众多卖家组成的市场。为了公平对待这些卖家，我们限制了展现给每个用户的同商铺推荐结果数。而由于用户总是可以通过某一个点击进入店铺，浏览这个店铺的其他物品，这看来是不会对推荐质量造成影响。
• 物品多样性：为了使推荐结果多样化，我们对用户选取一个100个最近邻的候选集，然后过滤掉在更高秩上有相似距离的物品，这个距离是通过计算物品向量之间的欧氏距离得到的。
• 相似用户的物品重排列：我们使用LSH代码找到用户之间的最近邻（所以对每个用户，我们可以发现与其有相同兴趣爱好的用户）然后为了产生物品推荐的结果，我们可以利用这些用户的喜好列表，根据物品向量和目标用户向量之间的内积重新排列它们。这应该能得到看似更好更相关的推荐，但仍然需要一个适当的实验来验证。

结论

综上所述，我们描述了如何基于隐式反馈数据为电子商务构建推荐系统。我们建立了一个系统，在Hadoop上计算推荐结果，这是现在我们的开源机器学习包Conjecture的一部分。最后，我们分享了一些额外的技巧，关于如何做一些额外的调整来潜在地提高推荐的质量。