偏好保留哈希的效率推荐
摘要：
推荐系统通常需要比较大量的项目，才能找到用户最喜欢的项目。如果在大规模数据集上经常提出推荐，这个过程可能是非常昂贵（时间，内存上）的。在本文中，提出了一种名为“偏好保留哈希（PPH）”的散列算法，以加快推荐。哈希已被广泛地用于大规模相似搜索（例如，类似的图像搜索），并且具有二进制散列码的搜索速度比具有实际特征的搜索速度显着更快。然而，推荐使用哈希的一个挑战是，推荐涉及用户对项目的偏好，而不是相似之处。为了解决这个挑战，PPH包含两个新颖的组件，它们与流行的矩阵分解（MF）算法一起使用。在MF中，用户对项目的偏好被计算为所学习的真实用户/项目特征之间的内积。 PPH的第一个部分限制了学习过程，使得用户偏好可以很好地接近用户项目的相似度。第二个组件是一种新颖的量化算法，从学习的实值用户/项目特征中生成二进制散列码。最后，可以通过快速哈希代码搜索有效地实现推荐。三个真实数据集的实验表明，提出的PPH算法的推荐速度可以比具有实数特征的原始MF快几百倍，推荐精度比以前的推荐哈希算法显着更好。
关键词：偏好 哈希 推荐 效率
1介绍：
建议引起了学术界和工业界的高度关注[17，1]，近期取得了重大进展[13,14]。然而，设计一个有效的推荐系统仍然具有挑战性，该系统可以很好地与大型数据集进行比较[33,4]。
在本文中，我们关注流行的矩阵分解（MF）算法[14]，并提出了关于推荐效率的新研究。 MF的推荐过程可以分为两部分：（1）为每个用户和项目学习实数特征，我们称之为偏好建模; （2）所有候选项目进行比较和排序，以便将顶部的项目作为推荐返回，这称为优先级排序。对于大多数MF类算法[13,14,17,22]，特定用户的偏好建模成本为，其中为特定项目的数量。相比之下，偏好排序成本通常为，其中是整个数据集中的项目数量。一般情况下，。
虽然偏好建模的效率已得到广泛的研究[5,33]，但有限的研究存在偏好排序的效率。然而，的复杂性在实践中可能成为一个关键问题。例如，对于诸如Netfix[1]的大规模数据集，基于MF的预先训练的偏好模型（即实值用户和项目特征），可能需要几个小时来对所有用户进行偏好排序。如果我们认为即使是1亿数量级的Net flix数据集只是现实世界的一小部分（不到1％），情况会更糟。此外，许多推荐系统[36,3,25,38]经常更新用户的偏好模型，由用户自己明确请求或由其项目评级行为隐含地更新。良好的推荐系统应提出满足用户最新偏好模型的建议。在这种情况下，偏好排名将频繁进行。虽然有时工程策略可能有帮助，例如并行计算，整体计算负担仍然没有降低。因此，需要新的研究来降低偏好排序的成本。
基于上述考虑，在本文中，我们研究了偏好排序的效率问题，并提出了一种新颖的散列算法作为解决方案。哈希[6,24,31]现在已经成为一种非常受欢迎的大规模相似搜索技术。通过将实值数据特征转换为二进制散列码，散列搜索可以非常快。在最好的情况下[24,8]，确定类似数据的成本与数据集大小无关。这样一个很好的属性使得哈希优于其他许多快速搜索技术（例如k-d树） [8]。因此，有希望考虑利用散列来加快偏好排名。在以前的工作[37]中，周等直接应用传统的哈希方法进行相似搜索，并报告了显着的加速（例如100次）。我们把他们的方法称为周的方法。然而，被忽视的事实是，推荐中的偏好排序不等同于传统散列中的相似度搜索。对于MF算法，用户对项目的偏好被计算为用户和项目特征之间的内积。两个向量之间的内积与其相似性基本相同（见第3节）。因此，尽管有明显的加速，周的方法[37]具有很高的精度损失（见第5节）。提出的散列算法，我们称之为“偏好保留哈希”（PPH），提供了将哈希应用于推荐的新视角。像传统散列一样，PPH还将实数用户和项目功能转换为二进制散列码。但是，PPH中的散列码是为了保持用户对项目的偏好（内部产品的排序顺序）而不是相似之处。简而言之，我们的PPH是面向排名的，而传统散列是面向相似的。 PPH由两个新颖的组件组成，即常规特征范数（CFN）约束和幅度和相位量化（MPQ），将在第四节中详细阐述。与周的方法相比，提出的PPH算法实现了类似的加速，但推荐精度显着提高。对三个实际数据集（即MovieLens-1M，MovieLens-10M和100M Net flix数据集）进行了广泛的实验，结果清楚地表明了所提出的PPH算法的优点。
本文的其余部分安排如下。第2节评论以前的作品与传统散列和推荐效果相关。第3节讨论为什么我们的PPH不是传统的哈希。算法细节见第4节，广泛的实验结果见第5节。我们在第6节总结并指出未来的一些工作方向。
2 相关工作
2.1 传统哈希相似度搜素
我们称之前的散列工作保留了数据相似性传统散列，已被广泛应用于类似图像[27,31,19]和类似文档[34,29]搜索的应用中。一般来说，传统散列有两个步骤：散列码构造，快速搜索哈希代码空间。
在哈希代码构建中，基本原理是类似的数据应该有类似的哈希码。直接散列码导出是NP-难问题 [31]。相反，大多数散列算法首先根据某些标准导出实值散列特征，然后使用量化方法来获得二进制散列码。一些散列标准是数据独立的，这意味着派生的散列特征不依赖于特定的数据分布。例如，著名的局部敏感哈希（LSH）[6]及其变体（例如[15]）通过随机投影导出哈希特征。其他标准依赖于数据，这意味着基于某些数据集学习推导。这种典型的算法包括迭代量化（ITQ）[7]，内核监督哈希（KSH）[19]，自学哈希（STH）[35]，光谱哈希（SpH）[31]等。
量化过程是相当标准的。通常，实际哈希特征是关于某些阈值而被二进制化。大多数方法对于每个特征维度都采用单个阈值，通常将其设置为特征平均值或中值[35]。如果数据被归一化为具有零均值，则零将成为阈值[31]。这被称为熵最大化原理[27,35]，因为这样的量化使每个维度的方差最大化，从而可以记录更多的信息。一些其他作品，如曼哈顿哈希[12]，为每个维度学习多个阈值。
PPH的两个组成部分， CFN和MPQ相应于上述两个步骤，但具有鲜明的新颖性。首先，CFN约束形成了导出实值哈希特征的标准，实际上也就是用户和项目特征的推导（偏好模型）。特别地，CFN通过相似性近似偏好，而上面列出的传统散列标准仅考虑数据相似性。第二，MPQ算法通过哈希码来建模偏好，而传统散列中的上述量化算法被设计为保持数据相似性（通过熵最大化）。我们将在第4节详细介绍。
在获得散列码后，搜索最近的邻居是非常快的。汉明排名（例如[19]）和散列查找[24]是两种流行的方法。在汉明排名中，数据点按查询的汉明距离进行排序。虽然它具有关于数据集大小线性时间复杂度，实际上由于哈希码的快速运算而非常快。在哈希查找中，在以查询哈希码为中心的r-radius汉明球中搜索类似的数据。时间复杂度是，其中D是代码长度，它是关于数据集大小的一个常数。此外，我们确定了最近提出的方法，多索引哈希（MIH）[21]更适合于有效推荐的任务。 MIH可以被视为具有非常好的属性的广义散列查找方法。上述检索方法的进一步分析和比较见4.3节。
2.2 效率推荐
如第1节所述，推荐的效率包括偏好建模的效率和偏好排序的效率。前者已被广泛研究[33,5]，其中随机优化和并行计算最受欢迎。
本文重点介绍了偏好排序的效率，尽管这些优先级排名的关键因素很少受到关注。我们将以前的作品分类为非哈希方法和哈希方法。我们首先检查非散列方法。在[17]中，linden等讨论了项目空间分区的思想，从而对所有项目的某些子集进行了推荐。他们认为这样一个天真的策略将会产生低品质的建议。 [4,11,22]采用用户聚类，使类似用户拥有相同的推荐结果。该策略基本上减少了用户空间，这可能会降低个性化推荐的性能。特殊数据结构，如k-d树或变体（例如[18,11]）也可以是解决方案。然而，Koenigstein等[11]表明使用纯树结构的加速相当有限，而Grauman等人[8]在许多现实世界的应用程序中，特别是处理高维数据的哈希显示了散列比树更优越。
上述算法的另一潜在缺点是它们都需要基于用户和项目特征的一些训练数据集学习加速模型（例如，群集，树）。然而在第1节中提到，如果用户的偏好频繁更新，学习的加速模式即将过时。增加额外的计算负担来学习新的加速模型，这不可避免地降低了优先级排序的效率。相比之下，我们的PPH并不是这样的问题，这会在我们的第4.4和5.3.1节中分析。
当哈希与推荐结合在一起时，它提供了一个新的视角，从根本上不同于非冲突的方法。然而，仅存在非常有限的以前的作品。 CF-Budget [10]可能是设计二进制哈希码进行协同过滤的第一项工作。然而，他们主要集中在降低存储成本，并没有讨论推荐加速。 Zhou等[37]应用哈希技术进行有效的推荐，最终的加速是很大的。然而，如上所述，[37]没有意识到偏好和相似性之间的差异。因此，它们比PPH算法产生更大的精度损失
3 初步分析
3.1 问题陈述
假设从MF算法，我们得到一组用户特征和一组项目特征，其中D是 特征维度。 从现在开始，我们使用符号u，v作为实数特征，而对于长度为的二进制散列码
在MF中，用户对项目的偏好被计算为内部产品。 因此，偏好排名可以表示为：
（1）
其中u：vigt;vj意味着用户u喜欢vi相对于vj。 那么的内积应该大于。
PPH的目标是找出一个散列方法H将U，V转换成二进制码，使式中的偏好顺序可以保存，同时可以利用快速哈希码操作的优点。 另外注意，两个哈希码的内积相当于汉明距离：
（2）
所以我们的目标是寻找散列方法H，使得：
(3)
我们给出以下定义来总结方程3：
定义1.函数f（u，vi）被称为关于哈希函数H排序一致，
如果f（u，vi）的降序排列顺序与Ham（H（u），H（VI））的升序排列顺序相同。 即，当且仅当Ham（H（u），H（v1））lt;Ham（H（u），H（v2））时，f（u，v1）gt; f（u，v2） 我们使用fharr;H表示排名一致性。 有了这个定义，PPH的目标是找出适当的H，使函数f（u，v）=尽可能地排列一致于H。
3.2为什么PPH不是传统哈希。
我们的PPH算法中的3式个比现在更具挑战性，直接应用传统的散列算法将无法正常运行。 为了了解PPH为什么不是传统的散列，有两个主要论点。
（1）PPH和传统哈希集中在不同的问题上。
看到这一点，回想一下传统散列的目标是保持数据相似性。 类似的数据应该被分配类似的哈希码; 因此，大的相似性表示小的汉明距离。 如果我们使用与方程式中相同的符号 3，并且让sim（u，v）在u，v之间是一个有效的相似度函数，传统哈希的目标应该表示为
但是， 4不等于公式 3，由于以下证明。
1）内积不是有效的相似度度量。
证明。 为了清楚起见，这里我们只提供最明显的证据。 根据[2,16]，有效相似性度量应遵循自相似性规则，即
Given u, forall;v, sim(u,u) ge; sim(u)
这意味着，没有其他的v与u比u它自己更相似。 但是，forall;v，uTuge;uTv一般不成立。 因此，内积不是有效的相似性度量。
对于大多数散列算法，相似性在欧氏距离的意义上定义（例如[31]）; 对于一些其他作品，利用余弦相似性（例如[35,20]）。 验证声明非常简单。 内积和欧式或余弦相似度。 因此，传统的散列和PPH是不同的算法，专注于不同的问题（等式4与等式3的区别）。
2）假设sim（u，v）等价于H是合理的。但是对于一些H ， 一般不存在。
如第2.1节所述，传统散列的基本假设是，如果sim（u，v）很高（例如欧氏距离或余弦相似度），散列函数H将产生类似的哈希码和比较小的。 因此，假设相似度函数近似排列一致于一些哈希函数H.这是哈希技术在相似搜索中成功的原因[8]。 然而，相比之下，由于内积不是有效的相似性度量，通常不能保证对于具有两个输入u，v的函数H，如果uTv为高，则输出散列码相似， 尽管有小的汉明距离。 因此，哈希码和散列函数本质上只保留数据相似性而不是偏好。
这个观点似乎与我们在方程式3中的目标相矛盾。 尽管方程式 3不能完全满足，但是一个很好的近似将对我们的目的是有效的。 在下面的部分中，我们将展示内积（大约）如何在一定的约束条件下进行一定的散列函数的排序一致。
4 偏好保留哈
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[141311]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
课题毕业论文、外文翻译、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
