Abstract
大规模的推荐系统通常严重依赖于预先构建的产品索引来加速推荐服务，从而使等待时间较长。一个重要的索引结构是产品-产品索引，在这里可以检索给定种子产品的排名产品列表。该指数可以看作是一个加权的产品-产品图。
在本文中，我们提出了一种能够有效地构建这类索引产品图的新技术。特别地，我们提出了Swing算法来捕获产品之间的替代关系，它可以利用用户-项点击双分区图的子结构。在此基础上，我们提出了一种基于互补产品关系建模的算法，它利用产品归类信息，通过聚类技术解决了用户共同购买图的稀疏性问题。
Introduction
除了详细的推荐方法外，另一个重要的问题是理解和捕获产品之间的关系。我们可以将产品关系图视为产品的重建索引，它可以返回给定一个种子产品的排名产品列表。该索引可以显著加快推荐服务，使在线用户的等待时间不明显。
产品之间有两种非常重要的关系：替代关系和互补关系。替代品是可互换的，而补充产品是可以购买的.不同的上下文环境可能对推荐相关性有不同的要求或含义，因此需要不同的关系图来加快推荐的速度。
这篇文章是淘宝写的，所以说淘宝拥有来自数十亿客户的大量真实用户行为数据，这些数据比文本数据更强大、更可靠的信号。因此，本文专注于直接利用用户行为数据，通过一种类似于基于相似度的协同过滤的无监督方法来构建产品图。
然后介绍一下采用传统的方法，比如具有局部相似性的项目CF时所面临的挑战，包括精度，鲁棒性，稀疏性，图的方向，可伸缩性等问题
本文提出了一种新的算法Swing算法，利用用户项行为图的内部结构来构造替代产品图。Swing是一种准局部结构，它被设计得比传统CF方法中使用的单条边更稳定。它提供了在用户项二部图上更可靠的计算传播，并有助于减少有噪声的用户行为数据的影响。在此基础上，提出了一种新的名为Surprise算法来构造互补产品图。惊喜算法利用基于Swing算法的产品类别信息和构建的产品聚类，解决了用户共同购买图上的稀疏性问题。此外，它还考虑了共同购买的产品的时间敏感性和时间顺序。在此基础上，我们可以在淘宝上构建产品替代图和产品互补图，为淘宝提供基本的索引服务，生成进一步推荐排名模块的候选产品。
本文的主要贡献如下：
- 一种利用用户行为图的拟局部结构信息的新的高效算法（Swing算法）。它提供了一个更可靠的计算传播，并消除了有噪声的数据的影响。基于Swing，我们可以在产品之间建立更可靠的相似关系。
- 一种利用产品类别信息和聚类技术的新的高效和有效的算法（Surprise算法）。它解决了稀疏性问题，因此当使用惊喜算法时，产品之间的互补关系更加可靠和合理。
- 通过并行化对所提方法进行了有效的大规模工业实现。
Swing算法
计算两个项之间的相似性是构建替代图任务的核心。有许多相似度度量只需要局部信息，这些方法通常计算效率高，可以应用于非常大的图。
大多数传统的方法在计算邻域强度时侧重于项目-用户-项目路径，采用基于项目的归一化来惩罚流行的项目。这些方法没有利用用户行为图上的其他内部结构，如用户-项目-用户，因此预测精度有限。
由于我们的用户点击数据是有噪声的，有许多意外或随机的点击，我们需要一个节点接近度量，它将考虑更健壮的网络内部结构信息。在链路预测领域已经研究了稳定的网络结构，例如用户在社交网络中倾向于形成三角形。考虑到电子商务中的二部分网络，当只有一个用户一起点击h和i时，这更有可能是一个巧合。但是，如果两个用户同时点击h和i，关系会强得多。因此，对于每个种子产品，考虑到包括所有点击种子产品的用户和这些用户点击的所有产品的本地图，我们将本地图上的每个用户-项目-用户网络结构称为一个摆动（Swing）。
如果一个用户对u和v之间有很多波动，这通常表明许多产品可以满足他们的要求。而这些波动之间的关系也不那么密集。因此，我们通过每个用户对之间形成的摆动总数来衡量每个摆动。swing分数的定义如下。
\[s(i,j)=\sum_{u\in U_i\bigcap U_j}\sum_{v\in U_i\bigcap U_j}\frac1{\alpha+|I_u\bigcap I_v|} \] 其中\(U_i\)是点击了第i项的用户集合，\(I_u\)是用户第u项点击的项目集合。α是一个平滑系数。
对于每个Swing结构，我们进一步添加了用户加权因子。用户点击的项目越多，它所获得的权重就越小。最终的swing score是：
\(s(i,j)=\sum_{u\in U_i\bigcap U_j}\sum_{v\in U_i\bigcap U_j}w_u\cdot w_v\cdot\frac1{\alpha+|I_u\bigcap I_v|}\)
且：
\(w_u=\frac1{\sqrt{|I_u|}},w_v=\frac1{\sqrt{|I_v|}}\)
在本工作中，我们主要关注仅基于用户点击行为的相似度计算，其他的时间衰减等因素也可以纳入到每种方法中。
算法的具体流程如下：
寻找互补关系的Surprise算法
在本节中，我们提出了一个全面的框架，通过挖掘用户购买数据来寻找补充产品。当用户刚买了一件t恤时，再推荐一件t恤就不合适了。相反，短裤和鞋子可能是更好的人选。如果他刚买了一部手机，那么展示手机外壳和便携式电源设备等配件就更合理了，因为用户对手机不再感兴趣了。这种重要的产品-产品关系被称为互补关系，它将种子产品与用户可能额外购买或一起购买的相关产品联系起来
我们还需要考虑产品的时间敏感性和数据稀疏性问题。首先，我们引入了一个与行为相关性相关的连续时间衰减因子，然后，我们引入了一种基于用户点击数据的聚类方法来解决数据稀疏性问题，而不是使用存在于非常高维空间中且不同类别差异很大的内容信息。请注意，用户点击等隐式反馈数据实际上并不是那么稀疏，尽管用户购买的数据很稀疏，因为用户通常会浏览和点击大量的项目，而购买的东西要少得多。我们将这个框架命名为“Surprise”，旨在帮助用户找到用户可能不知道的不同类别的封闭相关项目。
类别级别的相关性
为了找到与所购买的种子项目用户最相关的产品，我们首先尝试找到产品分类法中最相关的类别，通过将每个项映射到它的类别，我们得到了一个用户分类矩阵。然后，可以使用标准的协同过滤技术来计算类别之间的相关性。cj是ci的同一个相关类别的概率，定义如下：
\(\theta_{i,j}=p(c_{i,j}|c_j)=\frac{N(c_{i,j})}{N(c_j)}\)
其中，\(N(c_j)\)时类别\(c_j\)中的总购买量，\(N(c_{i,j})\)为类别ci之后cj的购买次数
设类别列表为\([c_{j_1},c_{j_2},...,c_{j_m}]\)，后验概率列表为\([\theta_{i,j_1},\theta_{i,j_2},...,\theta i,j_m]\)。大致取最高百分比或固定数量的候选项作为ci的相关类别是不公认的，因为类别之间的差异很大。相反，我们计算每个类别\(c_{j,k}\)的相对下降分数
\(\eta_k=\frac{(\theta_{i,j_{k+1}}-\theta_{i,j_k})}{\theta_{i,j_k}}\)
在最大相对下降点之前排名的类别被选择为ci的顶级相关类别，我们将这些类别表示为\(\Gamma(c_i)\)。
产品级别的相关性
对于每个相关类别，我们计算类别中项目的相关性得分，其中可以应用标准的基于项目-项目的协作过滤技术。在我们的系统中，我们添加了一个需要购买候选项目i的约束。该顺序在互补性建模中非常重要。例如，当用户刚刚购买了手机时，推荐便携式电源设备是合理的，而如果我们在购买了便携式电源设备后，为他推荐手机，这将是不合适的。然后将相关的分数定义如下：
\(s_1(i,j)=\frac{\sum_{u\in U_i\bigcap U_j}1/(1+|t_{ui}-t_{uj}|)}{\parallel U_i\parallel\times\parallel U_j\parallel}\)
其中，\(c_j\in\Gamma(c_i)\)和\(t_{uj}\geq t_{ui}\)。我们在分子中加上一个时间衰减因子。如果购买项目i和项目j之间的时间间隔较长，那么它们之间就不太可能存在很强的关系。
集群级别的相关性
假设用户在t恤i之后买了牛仔裤j，我们不确定j是否适合我。而如果有几个用户在i之后购买了j，我们会更有信心，j很可能与i相关。在选择候选项目时，我们还对（i，j）的共现数引入了一个阈值。例如，当我们在购买第i项后提出推荐时，我们只选择使用$Co(i,j)>\gamma $的候选项目，这可以被视为一种行为信心。然而，由于用户共同购买的数据非常稀疏，这种约束将进一步带来数据稀疏性的问题。
考虑到另一种情况，Bob在我之后买了j，David在我之后买了k，同时j和k非常相似，比如它们都是蓝色的左维牛仔裤。这种共同购买是关于产品关系的信息。这促使我们也在聚类水平上计算项目的相关性得分，这有助于缓解在项目水平上共同购买的数据稀疏性问题。
我们利用前一节中Swing算法构建的相似项图，将相似的项目投射到同一个集群中。然后在聚类水平上计算共同购买的相关性。
使用标签传播进行集群化
传统的聚类方法，如基于k-means和基于密度的方法，在淘宝场景中是不可行的，因为可伸缩性是一个涉及数十亿个产品的问题。所以我们在之前创建的替代图中执行了类似的标签传播过程。
对于每个项目，由Swing计算出的顶部相似的项目被添加为它的邻居，并有一个定向链接从一个相似的项目指向种子项目。边\(e_{j,i}\)的权重被设置为相似度得分\(swing_{i,j}\)。请注意，这个权重并不一定是对称的。最初，每个项节点的标签都被设置为其节点id。\(p(\cdot)\)表示一个邻居节点所属的对应标签的当前概率。对于每个项目节点，我们在根据边权值更新标签概率时，考虑其所有的邻居，然后根据一定的概率选择项目节点概率值最大的标签。
使用标签传播进行集群化的算法如下：
集群级相关性
将项目聚类到不同的组后，我们计算聚类级别的相关性得分。设\(L(i)\)是项目i所属的集群。则\(s_2(i,j)=s_1(L(i),L(j))\)。也就是说，我们计算一个相关性得分，即项目集群L (j)的购买发生在项目集群L (i)之后。
计算Surprise分数
基于两个相关性分数s1（i，j）和s2（i，j），我们通过将它们线性组合来计算最终的相关分数
\(s(i,j)=\omega*s_1(i,j)+(1-\omega)*s_2(i,j)\)
其中，ω是可以手动设置或从数据中估计的组合权重
标签：commerce,Product,Scale,项目,用户,算法,产品,Swing,类别 From： https://www.cnblogs.com/anewpro-techshare/p/18036427