基于改进MPLSH的协同过滤推荐算法

王旭宁超+刘盛英杰

摘要：针对基于项目的协同过滤推荐算法（Item-CF）在处理高维项目评分数据时出现计算效率急剧下降的不足，提出一种将改进的多探寻局部敏感哈希算法（MPLSH）和Item-CF相结合的推荐算法。改进的MPLSH通过将待搜索哈希桶的探寻方式由原始的哈希值差异导向替换为由距离远近导向，从而减少MPLSH需要探寻哈希桶的个数，缩小了Item-CF中相似项目集合的查找范围。并利用MPLSH本身具有的高效数据降维特性，提高Item-CF在高维项目评分数据中寻找相似项目集合的速度，从而有效改善Item-CF在处理高维项目评分数据时计算效率下降的问题。通过在MovieLens电影评分数据集上进行实验和算法比较，验证了该算法的有效性。

关键词：协同过滤；多探寻；局部敏感哈希；项目相似度；推荐算法

DOIDOI：10.11907/rjdk.172174

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2017）012-0074-04

Abstract：Aimed at the insufficient of computation efficiency drops dramatically when item-based collaborative filtering recommendation algorithm（Item-CF） processing high dimension item scoring data， we proposed a new recommendation algorithm which combine an improved multi probing local sensitive hashing algorithm（MPLSH） with Item-CF. This improved MPLSH decrease the number of hash buckets that need to be explored by replace the search way of hash buckets from hash value difference orientation to distance guide， decrease the search range of the similar item set in Item-CF. And make use of the efficient data dimension reduction characteristic of MPLSH， increase the speed of finding similar item sets in high dimension item scoring data， So as to effective improve the problem of computation efficiency reduce of Item-CF when it handle high dimension item scoring data. By conduct experiment on film scoring data set of MovieLens and compare it with other algorithms， the effectiveness of this algorithm is verified.

Key Words：collaborative filtering；multi probing；local sensitive hashing；item similarity；recommendation algorithm

0 引言

作為缓解信息爆炸问题的有效手段之一，推荐系统（Recommended System，RS）[1，2]在诸多领域得到广泛应用，作为推荐系统核心的推荐算法也逐渐成为研究热点。推荐算法的功能就是通过获取数据，分析预测用户将会对哪些未浏览或未购买的项目感兴趣。推荐算法可分为基于模型的推荐算法、协同过滤推荐算法和混合推荐算法。

基于项目的协同过滤推荐算法（Item-CF）是协同过滤推荐算法中的一种，其从项目角度进行推荐分析。首先通过项目的评分值计算项目间的相似度，找到与目标项目相似度最高且目标用户还未评过分的项目作为候选项目集合；然后根据目标用户对候选项目集合中各个项目的最近邻项目评分的加权平均值来预测目标用户对此项目的感兴趣程度，分值越高代表其越有可能对此项目感兴趣，并据此产生推荐。然而随着项目评分数据维度的增加，在高维项目评分数据下该算法的效率会大大下降。不少学者提出了改进算法，比如Wei等[3]基于项目聚类的方法来缩小目标项目的最近邻搜索范围，从而加快相似项目计算的速度。文献[4]提出了一个基于协同聚类的增量协同过滤框架，用以提高计算效率。文献[5]使用增量奇异值分解技术进行协同过滤推荐，使用此方法可以降低项目集合的维数，加快计算速度。

针对此问题，本文提出一种将改进的MPLSH与Item-CF相结合的推荐算法，提高处理高维项目评分数据时的推荐计算效率。

1 相关概念

1.1 多探寻局部敏感哈希算法（MPLSH）

在介绍MPLSH之前，需要先了解最原始的局部敏感哈希算法（LSH）[6，7]。LSH基于这样的假设：如果两个点在原有高维空间中是相似的，那么分别经过特定的哈希函数转换到低维空间后它们也有很大的可能是相似的，这就为高维数据中相似项目的快速选取提供了可能。LSH的主要思想是通过设计一族哈希函数将高维空间中的点集映射到一个由哈希码所构成的低维空间[8]，并使其分散到若干个哈希桶中，此过程会形成一张到多张哈希表。原始数据集中相似的数据点被哈希到同一个哈希桶中的概率很高。在进行相似点搜索时，只需要通过哈希函数定位目标数据点所在的哈希桶，然后将这些桶中的数据点作为候选集合，将它们与目标数据点进行相似度计算即可。这样做可以有效地过滤出大量的无关数据，从而避免了不必要的计算过程，加速最近邻数据点获取。LSH虽然是近似技术，不能保证相似性检索的精确性，但在实际计算中，其通常可以在很小的时间复杂度下返回精确或近似精确的相似结果，提高高维数据的处理效率[9]。

LSH为了保证搜索的效率和准确度，往往需要使用大量的哈希表，这样会导致大量存储空间被占用。相关学者提出利用多探寻的方法来解决空间占用过大的问题，使用此方法的LSH被称为多探寻局部敏感哈希（MPLSH）[10]。其主要思想是在探寻目标点对应哈希桶的同时，探寻与该哈希桶有近似编码的哈希桶，因为相关学者认为如果一个点的近邻点没有被哈希到与之相同的哈希桶中也一定被哈希到了与之相邻的哈希桶中[11]。

MPLSH的多探寻是一种步进式的，在余弦相似度度量下哈希值是01值，它对应的多探寻首先是探寻目标点所在的哈希桶，然后探寻与目标点所在哈希桶哈希值仅有一位不同的哈希桶，接着探寻两位不同的哈希桶，以此类推，直到回收够指定数量的哈希桶后结束算法。

这种方法可以从少量哈希表中获取足量的哈希桶，在降低内存空间占用的同时扩大了候选空间，从而达到与LSH接近的搜索范围，但是这种方法的不足是其检索时间比传统LSH要长。

1.2 基于项目的协同过滤推荐算法（Item-CF）

基于项目的协同过滤推荐算法（Item-CF）[12，13]认为与用户喜爱的项目相似度高的其它项目有很大可能再次被用户所喜爱，因此可以通过项目的评分找到与用户喜爱项目相似度高的项目，构成候选项目集合，并预测用户对其中各个项目感兴趣的程度。其推荐过程主要包含两个步骤：①项目间的相似度计算；②候选项目的预测评分。其中项目间相似度计算是最为关键的一个步骤。最常用的几种计算方法是：余弦相似度、修正的余弦相似度和相关相似度。本文采用修正的余弦相似度来计算项目间的相似度。

2 改进的推荐算法

2.1 对MPLSH的改进

本文通过分析MPLSH的步进式探寻方法，发现存在邻近哈希桶的探寻过于盲目的问题，导致计算速度不及LSH。因此，本文试图用由距离为导向的探寻方式替换原始的以哈希值差异为导向的探寻方式，缩小MPLSH需要探寻的哈希桶数量，提高MPLSH的计算速度，并将其与Item-CF相结合，改善Item-CF在处理高维数据时效率低下的问题。

本文使用距离为多探寻的导向，仅去探寻那些与目标项目所在哈希桶距离最近的哈希桶，是基于这样一个概念：高维空间中相似的两点，即距离近的两点，经过哈希函数处理投影到低维空间后，投影点仍然有很大的概率距离相近。说明如下。

对高维空间中任意两点x和y，若‖x-y‖越小则对任意一个大于0的常数λ，有P{‖VTx-VTy‖<λ}越大。其中‖x-y‖为原高维空间中两点之间的距离，P{‖VTx-VTy‖<λ}表示投影后两点之间的距离小于λ的概率。令d=‖x-y‖，存在一正交矩阵C使得Cz=x-y，其中z=[d，0，…，0]T。则有VTx-VTy=VT（x-y）=VTCz，VT的每个元素均为服从标准高斯分布的随机变量且相互独立。因为C为正交矩阵，根据高斯分布的特性，VTC的每个元素均服从标准高斯分布且相互独立。因此‖VTCz‖可以转化为dX1，其中X1为服从标准高斯分布的随机变量。故有P{‖VTx-VTy‖<λ}=P{dX1<λ}=PX1<λd=2Φλd-1，因为Φ函数在定义域内单调递增，当d越小时P{‖VTx-VTy‖<λ}取值越大，即高维空间中两点的距离越近，它们经过哈希函数投影到低维空间中时就越有可能距离越近。因此本文利用这一特性，使用近邻哈希桶与目标项目点的距离代替近邻哈希桶中的项目与目标项目点的距离，并据此进行探寻。

综上所述，本文提出的改进MPLSH优势在于充分利用了高维空间中距离较近的相似点在经过特定哈希函数降维后，仍有很大概率保持距離相近这一特性，从而有效地缩小需要探寻哈希桶的范围，加快MPLSH的计算速度。

3 实验部分

3.1 实验数据来源及度量标准

3.1.1 数据集来源

本实验数据集采用美国明尼苏达大学GroupLens研究组提供的电影评价数据集MovieLens（https：//grouplens.org/datasets/movielens/）。该数据集包含6 040名用户对3 900部电影的1 000 209条评分数据，每位用户至少对20部电影进行了评分，所有电影属于19个类别，评分值大小分布在[0，5]区间内，如表1所示。

本文将算法计算所消耗的时间作为另一个评价的标准，计算消耗的时间越短其性能越好，即推荐系统的效率越高。

3.2 实验结果及分析

本文将基于改进MPLSH的Item-CF与基于MPLSH的Item-CF以及原始的Item-CF进行比较，主要对比3种算法的计算效率和准确度差异。实验结果如图2所示。

图2是最近邻项目数对这3种算法MAE值的影响，为了获得比较明显的效果比较，需要计算使得各个算法MAE值均较小时的最近邻项目数。从图2中可以看出随着最近邻项目数的增加3种方法的MAE首先大幅度的下降，接着到达最小值，最后逐渐上升趋于稳定。其中MAE值大小的规律总体呈现MPLSH>改进MPLSH>Item-CF。从图2中可以发现，当最近邻项目数达到300左右时MAE值均较小。

本文取最近邻项目数为300对3种方法进行实验，实验结果如表2所示。可以观察到改进MPLSH的MAE为0.716，优于MPLSH的0.722，略差于原始Item-CF的0.704。同时任意时刻改进MPLSH探寻哈希桶的数量均小于同时刻MPLSH的探寻数量，且改进MPLSH的计算耗时均少于MPLSH。

为了方便进一步的分析，将实验结果绘制成折线图。如图3所示，其中横轴代表算法结果的MAE值，纵轴代表算法的计算时间。实线代表基于改进MPLSH的Item-CF，虚线代表基于MPLSH的Item-CF。

通过图3可以观察到，在获得相同MAE值的情况下，基于改进MPLSH的Item-CF运行时间均少于基于MPLSH的Item-CF。其中最小的时间差值为4.7s，最大的时间差值为12.3s，平均差值达到了8.5s，说明Item-CF的计算效率确实获得了提升。在相同运行时间的情况下，基于改进MPLSH的Item-CFMAE值也略低于基于MPLSH的Item-CF，说明本改进算法的准确度是可以接受的。结合表2中的数据可以发现，本文的改进MPLSH所需要探寻的哈希桶数量均小于同等条件下的MPLSH，说明本文对MPLSH的改进是有效的。

4 结语

本文针对传统协同过滤推荐算法在处理高维项目评分数据时会产生实时性差的问题，提出了一种基于改进MPLSH的协同过滤推荐算法。实验结果表明：相较基于MPLSH的协同过滤推荐算法，本文的算法可以在保证推荐准确度的前提下获得更高的效率，有效缓解协同过滤算法在处理高维项目评分数据时的效率下降问题。

本文对协同过滤算法处理高维数据的效率问题进行了研究，提出的算法虽然在MAE上略差于原始算法，但计算效率有较明显的提升。该算法存在进一步改进的空间，如当数据维度不够高时，效率的提升可能不够明显；未考虑将用户兴趣随时间变化的问题；算法的适用范围研究等，这些问题有待后续研究。

参考文献：

[1] BOBADILA J， ORTEGA F， HERNANDO A， et al. Recommender systems survey[J]. Knowledge-Based Systems，2013，46（1）：109-132.

[2] TANG J， HU X， LIU H. Social recommendation： a review[J]. Social Network Analysis & Mining，2013，3（4）：1113-1133.

[3] 韦素云，业宁，朱健，等.基于项目聚类的全局最近邻的协同过滤算法[J].计算机科学，2012，39（12）：149-152.

[4] GEORGE T， MERUGU S. A scalable collaborative filtering framework based on co-clustering[C].IEEE International Conference on Data Mining，2005：47-125.

[5] SARWAR B， KONSTAN J， RIEDL J. Incremental singular value decomposition algorithms for highly[C].International Conference on Computer & Information Science，2002：27-28.

[6] GIONIS A， INDYK P， MOTWANI R. Similarity search in high dimensions via hashing[C].International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc，1999：118-129.

[7] SLANEY M， CASEY M. Locality-sensitive hashing for finding nearest neighbors[C]. IEEE Signal Processing Magazine，2008：128-131.

[8] BUHLER J. Efficient large-scale sequence comparison by locality-sensitive hashing[J]. Bioinformatics，2001，17（5）：419.

[9] RAVICHANDRAN D， PANTEL P， HOVY E. Randomized algorithms and NLP： using locality sensitive hash functions for high speed noun clustering[C]. ACL 2005， Meeting of the Association for Computational Linguistics， Proceedings of the Conference， University of Michigan， Usa. DBLP，2008：250-258.

[10] LV Q， JOSEPHSON W， WANG Z， et al. Multi-probe LSH： efficient indexing for high-dimensional similarity search[C].International Conference on Very Large Data Bases. VLDB Endowment，2007：950-961.

[11] BUSSION O， BUISSON O. A posteriori multi-probe locality sensitive hashing[C].ACM International Conference on Multimedia. ACM，2008：209-218.

[12] SARWAR B， KARYPIS G， KONSTAN J， et al. Item-based collaborative filtering recommendation algorithms[C]. International Conference on World Wide Web. ACM，2001：285-295.

[13] 鄧爱林，朱扬勇，施伯乐.基于项目评分预测的协同过滤推荐算法[J].软件学报，2003，14（9）：1621-1628.

（责任编辑：刘亭亭）