反转协同过滤：使用K-最近邻图的快速协同过滤算法外文翻译资料

英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

反转协同过滤：使用K-最近邻图的快速协同过滤算法

摘要：

基于用户和基于项目的协同过滤（CF）方法是推荐系统中使用最广泛的技术之一。由于其简单性和可接受的准确性水平，这些算法在行业和学术界都广泛使用，但它们需要大量时间来确定顶级k类似的邻居（项目或用户）来预测未分级项目的用户偏好。在本文中，我们提出了反转CF（RCF），一种利用k-最近邻（k-NN）图的快速CF算法。 这种方法的一个主要思想是扭转找到k个邻居的过程; 而不是找到k个类似的未分配项目的邻居，RCF找到额定项目的k个最近邻居。 这个算法不仅如此执行较少的预测，同时过滤掉不准确的结果，但也可以使用快速k-NN图形构造算法。 实验结果表明，我们的方法在预处理时间和查询处理时间方面优于传统的基于用户/项目的CF算法，而不会牺牲精度水平。

关键字：反转CF 协同过滤 k最邻近 贪婪过滤

1 _介绍
基于用户和基于项目的协同过滤（CF）方法是推荐系统中使用最广泛的技术之一。 当用户请求推荐时，Herlocker，Konstan，Borchers和Riedl（1999）介绍的基于用户的CF算法预测用户对所有未分类项目的偏好是基于类似用户对这些项目的偏好。 以类似的方式，Sarwar，Karypis，Konstan和Riedl（2001）提出的基于项目的CF算法基于用户对类似项目的偏好水平预测用户对所有未分级项目的偏好。

Cremonesi，Koren和Turrin（2010）和Lee，Song，Kahng，Lee，而Lee（2011）则认为，与基线算法相比，CF算法产生更高质量的电影推荐，其仅推荐最流行的电影或高度评价的电影。虽然已经提出了更有效的算法，例如Cremonesi等人（2010）提出使用奇异矢量分解或Lee等人（2011）提出的随机游走，由于其简单性和可接受的准确度，CF算法在业界和学术界仍然广泛使用。例如，林登介绍的亚马逊和YouTube推荐系统，史密斯和约克（2003）和戴维森（Davidson）等人（2010）分别采用基于CF的算法。此外， Lee，Park，Kahng，Lee和Lee（2010b）以及Park，Lee（2011）正在提出许多修改版本的CF算法，用于构建上下文感知推荐系统的工作。

CF算法的主要缺点之一是所有未分级项目都需要进行预测。 虽然这种方法有助于使用均方根误差（RMSE）来评估各种算法的准确性，但该方法消耗了大量的推荐时间。 此外，预处理时间也长，特别是对于基于用户的CF算法，因为它必须计算用户之间的所有相似性值。

在本文中，我们提出了反转CF（RCF），一种使用k-最近邻（k-NN）图的快速CF算法。 这种方法的一个主要思想是它反转了寻找k个邻居的过程。 这个算法不仅执行较少的预测，同时滤除不准确的结果，而且还可以使用快速的K-NN图形构造算法。 我们工作的贡献可以总结如下：

（1）我们提出RCF，一种使用k-NN图的快速CF算法。由于RCF执行较少的评估预测，与基于用户或基于项目的CF相比，推荐时间（查询处理时间）显着降低
算法。
（2）我们应用称为贪心过滤的快速k-NN图构造算法，显着减少RCF预处理时间。 在执行贪心滤波算法进一步改进之前，我们还对我们的数据集应用TF-IDF加权。
（3）通过不同参数设置的实验，我们可以看出，RCF在预处理时间和推荐时间方面都优于传统的基于用户的/基于项目的CF算法，而不会牺牲精度。

本文的其余部分结构如下。 在第2节中，我们将回顾基于用户的/基于项目的CF算法及其全局优化技术。 在第3节中，我们提出了一种快速协同过滤算法RCF。 在第4节中，我们展示了比较我们的方法与传统CF算法的实验结果。最后，我们在第5节总结论文并展示未来的研究方向。

2_相关工作
Adomavicius和Tuzhilin（2005）根据推荐方法（基于内容的过滤，协同过滤和混合方法）的类型将现有的推荐系统分为六类，以及推荐技术（基于启发式的方法和基于模型的方法）方法）用于评估估计。虽然传统的基于协同和启发式的方法胜过不同类型的推荐系统，特别是基于模型的方法，如使用由Koren，Bell和Volinsky（2009）引入的矩阵因式分解法，单向量分解由Cremonesi等人提出（2010），或由Lee等人提出的随机游走。 （2011年，2013年），Desrosiers和karypis（2011）在预测准确性方面表示，传统方法由于其简单性，合理性，效率和稳定性而得到广泛应用。例如，根据Linden等人（2003）和Davidson等人（2010），亚马逊和YouTube推荐系统利用了基于协同和启发式的方法。本文主要关注基于项目的CF和基于用户的CF算法，它们是其中最受欢迎的两种方法。

基于用户的CF算法基于用于那些项目的类似用户偏好来预测用户未分级的所有项目的偏好。 根据Herlocker等 （1999），项目i的活跃用户a的预测评级定义如下：

其中N（a）表示已经评价项目i的用户中的k个最近邻的集合; r_n,j 表示用户n的项目i的评级：_a和_n分别是用户a和邻居n的平均评级; sim（a，n）是a和n之间的相似度。 我们使用Pearson相关系数作为基于用户的CF算法的相似性度量：

其中C_i表示一组共同项目。

Herlocker等 （1999）和Desrosiers and karypis（2011）指出，对于基于用户的CF算法有常见的优化技术，如重要性加权，方差加权和选择邻域。 前两种技术用于调整用户之间的相似度值。 如果两个用户的普通评级项目少于50个，则重要性权重使它们之间的相似度降低（1个＃个常用项目/ 50）* 100％;方差加权减小了方差较小的项目的影响，如Titanic。 第三种技术在预测未评级项目的评级时仅选择k个邻居，因为使用较不相似的用户可能会对推荐的质量产生负面的影响。

基于项目的CF算法基于用户的类似项目的偏好级别来预测用户未分级的项目的偏好。 根据Sarwar等 （2001），未分类项目i的活跃用户a的预测评级定义如下：

超出字符数上限

取消

显示以下内容的翻译： Herlocker et al. (1999) and Desrosiers and karypis (2011)states that there are common optimization techniques for the user-based

仍然翻译： Herlocker et al. (1999) and Desrosiers and karypis (2011)statethat there are common optimization techniques for the user-based

翻译更多

其中N（i）表示由活动用户a评估的项目中的i的k个最近邻的集合。 为了有效地找到N（i），该算法首先构造一个k-最近邻图，它表示项目之间的最近邻居关系。 然后，我们可以基于该预先计算的K-NN图来找到k个邻居，而不是在请求推荐时计算逐项相似性矩阵。 在这个方程中，我们使用调整余弦相似度作为相似性度量：

其中C_U表示一组共同者。 _u是用户U的平均评级。

Cremonesi（2010）和Lee et al等人 （2011）表明，与基线算法相比，CF算法产生了高质量的电影推荐，其仅推荐最流行的电影或高度评价的电影。虽然已经提出了更有效的算法，但由于其简单性和可接受的准确度，CF算法在工业和学术界仍然被广泛使用。然而，在使用现有方法时，存在阻碍实现快速的建议的几个障碍。首先，有必要根据活跃用户找到不同的邻居。具体来说，基于用户的CF算法在预测i的等级时，从所有评级为某个未评级项目i的所有用户中找到k个最近的用户，而基于项目的CF算法从所有项目中找到k个最近的项目已被活跃用户u评级。其次，当用户请求推荐时，有必要预测所有未分级的项目。根据Cremonesi（2010）和Park，Yang，Song，Lee和Lee（2013b）等人的说法，这个程序有点低效。，我们通常只需要在真实世界的场景中排名前10的推荐结果。而CF如果在短时间内没有太多的推荐请求，算法将提供快速建议，对于许多用户提出实时建议的建议，商业推荐系统将不容易。虽然有是减少推荐时间的几种方法，如Sarwar等人的工作。 （2001），Das，Datar，Garg和Rajaram（2007）以及Birtolo和Ronca（2013），性能收益不显着，或者方法不是基于基于用户/项目的协同过滤。

3_快速协同过滤
我们的方法包括两个主要步骤：首先，我们基于我们以前的Park，Park，Lee和Jung（2013x，2014b）的工作（2013a，2014b），大致构造了一个k-最近邻图（le-NN图）作为一个预处理步骤,我们通常将k设置为I gt;gt; kgt; k。 其次，我们基于K-NN图发现未分配项目的k个邻居。 然后，我们向使用k个邻居的用户和我们修订版本的非归一化余弦区域（3.2节）推荐项目。

3.1 最近邻图形构造
K-NN图的构造是一个任务，其涉及找到与每个节点最相似的k个节点。虽然Datar，Immorlica，Indyk和Mirrokni（2004）以及Gan，Feng，Fang和Ng（2012）提出的其他任务，如k-NN搜索， Achtert等人提出的k-NN反向搜索（2006），Lee，Park，Shim和Lee（2010x）介绍的相似性联合以及Xiao，Wang，Lin和Shang（2009）和Kim和Shim（2012）提出的top-k相似性加入可以用于推荐系统，我们使用K-NN图，因为它是最合适的数据结构之一。我们的算法构建K-NN图的最简单方法之一是计算所有节点之间的相似度，并提取与每个节点最相似的节点。尽管简单，这种强力方法需要二次时间复杂度，当与大量数据结合使用时，这是非常繁琐的。解决这个问题的另一种方法是使用倒排的指数，用户矩阵通常非常稀疏。然而，根据Park等人（2014b），这种方法也不适合处理大量的高维数据。

我们的主要思想是构建Park等人提出的基于贪心滤波的近似K-NN图。 （2013a，2014b），以加快这一进程。 已知贪心滤波优于其他k-NN图构造算法，如Dong，Moses和Li（2011）提出的NN-Descent或kNN-Overlap Chen，Fang和Saad（2009）提出的高维稀疏数据集。 如果我们使用近似图表，建议质量没有下降，我们就不用花太多时间来构建精确的k-NN图。 K-NN图的精度定义如下：

图1示出了贪心过滤如何构建近似K-NN图的示例。 在这个图中，有五个项目和十个用户; 矩阵中的值表示评级，每个对应于其项目和用户。 贪心过滤的主要思想是过滤“大值尺寸”（图中阴影部分）根本不重叠的物品对。 在这个图中，i1和i2具有共同的大值维度。 因此，我们计算i1和i2之间的相似度。 相反，i2和i4没有共同的大值维数; 因此，我们不计算i2和i4之间的相似性。 Park et al （2014b）详细说明为每个项目选择大值尺寸的方式。 在这种方法的实际实现中，我们使用邻接列表而不是邻接矩阵。 贪心过滤的经验时间复杂度为0（一Z一），其中Z是一组项目。

根据Park等 （2014b），当我们应用TF-IDF加权方案时，该算法执行得更好，这个过程不会显着降低建议的质量。 因此，我们基于TF-IDF加权方案调整输入矩阵中的值：

其中M_ij表示对应于第i个项目和第j个用户的矩阵的原始值; u表示一组用户; F（u_j）表示具有与用户u对应的值的项目的数量。
例如，假设我们使用与TF-IDF加权方案的余弦相似度，并且在数据集中有两个项目i1和i2。 在这种情况下，贪婪过滤将计算它们的相似度，如果它们被至少一个非活动用户高度评价。 否则，将过滤掉这些项目对。

3.2快速推荐算法
回想一下，基于用户或基于项目的CF算法的两个主要缺点是，它们必须根据活动用户找到不同的邻居，并且必须预测所有未分级的项目。 我们的新颖算法RCF解决了这些问题。将B [i]作为项目i的k-NN列表，这已经在Section3.1中计算了。 让 和分别是活动用户a的未评级项目和评级项目的集合。 那么RCF的工作如下：
1.对于每个项目isin;，准备一个空集合S [i]。
2.对于每个项目iisin;和每个项目，使得jisin; 和jisin;B[i]，把我添加到SJ“。
3.对于每个项目iisin;，如果| S [i] |gt; k，则删除最相似的k，来自S [i]的项目。
4.然后，预测所有项目i的评级，使iisin; 和 IS [i] | = k。

这里，sim（i，n）是i和n之间的余弦相似度。 它的定义如下：

lt;

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[28260]，资料为PDF文档或Word文档，PDF文档可免费转换为Word