基于加权融合的E2LSH用户相似度计算

陈 浩 马娅婕 金 瑾 徐高凯

(武汉科技大学信息科学与工程学院 湖北 武汉 430081)

0 引 言

近年来，随着互联网用户量的爆发式增长，同时也带来了用户行为数据在数目和维度两方面的指数上升，传统协同过滤算法在当前的海量高维度数据情况下面临着计算效率低下、推荐结果不够精确等诸多缺陷[1]。局部敏感哈希LSH(Locality Sensitive Hashing)处理当前海量高维数据情景下的近邻检索、相似度计算方面有得天独厚的优势[2]，尤其是在推荐系统中经常出现的海量高维的用户-商品评分矩阵中相似用户的检索过程。本文使用了精确欧式局部敏感哈希(E2LSH)算法在海量高维用户群体中快速查找相似用户[3]，同时针对基于E2LSH计算用户相似度时提出使用加权模型融合的技术来提升用户相似度计算的精度，从而可以更好地提高推荐系统的推荐准确率。

1 相关工作

推荐系统中首要解决的一个问题就是用户相似度计算的问题，尤为重要的是在海量高维用户数据中快速查找相似的用户。而传统的线性查找方法空间和时间复杂度都较高[4]，已经不适用于当前场景下的相似用户查找。通常用来代替线性查找方法的算法是局部敏感哈希算法[5]。

模型融合通常可以提升模型的效果，使用加权融合技术可以有效地降低预测结果的方差，使得预测结果更为准确。所以本文使用加权融合的E2LSH算法来计算高维场景下的用户近邻。

1.1 皮尔逊相关系数

在推荐系统中，较为常用的一种相似度度量方法是使用皮尔逊相关系数来度量用户或者商品的相似度。其定义如下：

(1)

使用皮尔逊相关系数来计算任意两个不同变量之间的相似度时需要变量满足以下约束条件：

1) 两个变量(两个不同用户或商品)之间具有线性关系。

2) 每个变量都是连续变量且符合正态分布[6]。

同时由于皮尔逊算法是一种线性算法，因此不适合直接使用在海量高纬数据的场景中，本文首先使用E2LSH算法得到相似用户，之后使用皮尔逊相似度进行目标用户对未评分商品的评分预测。同时为了处理E2LSH对用户相似度计算不精确的原因使用了加权融合的E2LSH算法进行用户相似度计算。

1.2 LSH算法

1999年Gionis提出了LSH算法，计算LSH前需要把原始数据从欧式空间下转换到Hamming空间下，便于进行局部敏感哈希计算。在LSH算法中，哈希函数定义如下：

hi(p)=pi

(2)

哈希函数中p是一个01序列，输出的h(p)为序列p中某个值。于是，hash函数簇内就有N个函数(有N种可能，只不过选k个)，一个完整的哈希映射包含k个不同哈希函数共同把高维原始数据映射到特定低维哈希桶中，具体定义如下：

gi(p)=(hi1(p),hi2(p),…,hik(p))

(3)

式中:k表示最终降维的维度;hik(p)表示第k个哈希函数[7]。

LSH的算法步骤如下：

1) 从[0,N]内取L个数，形成集合G，即组成了一个桶哈希函数g。

2) 对于一个向量P，得到一个L维哈希值，即P|G，L维中的每一维都对应一个哈希函数h。

3) 由于直接以第2步中得到的L维哈希值做桶标号不方便，因而再进行第二步哈希，第二步哈希就是普通的哈希，将一个向量映射成一个实数。

LSH哈希函数如下：

h(v1,v2,…,vk)=(a1·v1+…+ak·vk)modM

(4)

式中：a是从[0,M-1]随机抽取的数字，这样就可以把一个向量映射到一个桶中。

1.3E2LSH算法

E2LSH算法是基于p-stable分布的LSH方法的一种实现[8]。E2LSH算法中的哈希函数定义为：

(5)

式中：v表示d维的原始数据；其中a为正态分布产生的随机量。式(5)分子部分a·v+b整体为一个实值量，其中b是由均匀分布[0,w]生成。分母部分w值越大，那么通过上述E2LSH的哈希函数计算原始数据的哈希值就会被分配到相同的哈希桶之内，如果w较小则该哈希函数会无效，就起不到局部敏感的效果。

式(5)表示把数据变为一个实值量，通常我们需要把初始给定的高维度数据降维为k维，则需要选择k个哈希函数共同形成一个由原始数据到降维数据的映射，得到哈希桶p=(N1,N2,…,Nk)。每个Ni均是一个整数，则p是k个整数组成的数组。

1.4 模型融合

模型融合是指通过一系列弱学习器的组合来输出最终需要预测的结果。常用的模型融合技术包括Bagging、Boosting、Stacking、Blending等技术[9]，由于后几种方式不能并行执行而且算法复杂度较高，本文使用Bagging融合的加权融合技术，主要是由于其融合技术可以高效并行、复杂度较低、易于实现。具体加权公式如下：

(6)

(7)

式中：simi表示第i个E2LSH模型对用户对计算得到的相似度，wi表示第i个模型的权重，t表示总共使用多少个模型进行融合。

2 基于加权E2LSH的协同过滤算法

2.1 哈希降维

作为一种高效的降维算法，E2LSH算法在降维的同时也可以保证数据从高维降到低维时不会丢失相似性(任意两个高维用户数据的相似性在低维仍然得以保持)[10]，从而可以使得计算用户相似度时不再使用高维数据，而是直接使用降维后到低维数据进行相似度计算。一个哈希桶的结果由多个式(5)组合而成。其映射函数描述为：

g(v)=(h1(v),h2(v),…,hk(v))

(8)

本文通过改变w的值来检测哈希函数的映射效果。最终经过大量实验证明，当w=4时，哈希函数的效果是相对比较好的。

原始高维数据维度为d，通过映射函数g(v)降低至k维(k<

2.2 最近邻查找

E2LSH算法的最近邻查找是为了在哈希桶中查找到最相似的用户，使用哈希桶来查找近邻用户是为了提高检索的时间效率，具体查找过程如下：v表示原始用户评分向量，v=(v1,v2,…,vd)，d表示商品数目(也就是向量v的维度)。通过映射g( )函数把数据降到k维的结果为(N1,N2,…,Nk)，代表一个哈希桶。图1表示建立哈希桶的分层索引，使用数据和链表结合的方式进行分层。

图1 E2LSH结构图

图1用N来表示哈希表的大小；bucket表示哈希桶；(N1,N2,…,Nk)表示桶编号。对每个形式为k元组的桶标号，使用如式(9)中h1函数和式(10)中h2函数计算得到两个值。h1的结果是数组中的位置，数组的大小也相当于哈希表的大小；h2的结果值作为k元组的代表，链接到对应数组的h1位置上的链表中；r′由[0,prime-1]中依据均匀分布随机产生。

modtableSize

(9)

(10)

建立索引后，计算用户v的m个近邻用户的查找过程如下：

1) 输入:用户v对商品全集d的原始评分向量。

2) 使用g(v)函数对v降维，可以得到(N1,N2,…,Nk)的k维数据。

3) 分别计算降维后的h1、h2值。

4) 获取哈希表位于h1位置的链表。

5) 在获取到的链表中查询h2的值并获取h2值位置上的用户样本p。

6) 分别计算输入用户v与p中每个用户的相似度，并将得到相似度值从大到小排序。

7) 选择前m个用户并返回对应用户和相似度值。

2.3 加权融合相似度计算

本文计算用户相似度使用加权融合方法的基础学习器是E2LSH算法，由于该算法是k值敏感的算法，所以本文使用加权融合不同k值来计算不同用户的相似度。算法主要流程如下：

输入：目标用户评分向量

输出：目标用户最高相似度用户群

1) 选择t个k值；

2) 使用每个k值计算对应的m个最相似用户；

3) 使用式(5)计算目标用户与其余用户的相似度(加权权重由不同k值对应的精度决定);

4) 输出最高相似度的n个用户。

2.4 推荐结果计算

基于2.3节对当前用户返回的相似用户来预测当前用户的商品评分，通过该评分对用户做出推荐。目前协同过滤算法在用户相似度计算时会在部分评分相似度较高的用户组中排除一部分评分有缺失的用户[11]。表1为用户评分表。

表1 用户评分表

(11)

基于E2LSH算法查找到最相似用户进行推荐，如果用户对商品没有评分时先根据用户相似组内的数据递归进行预测。θ表示权重因子，大多数基于用户的协同过滤算法通常设置θ=0[12]。

计算相似度时使用皮尔逊相关系数，其sim(u,v)写为：

(12)

式中：U、V分别表示用户u、v的评分向量。

2.5 算法流程

输入：用户原始评分向量

输出：推荐结果

Step1输入用户原始评分向量，使用本文提出的加权融合E2LSH近邻查找技术查找并返回与输入用户最相似N个用户。

Step2对于Step1中返回的N个与输入用户最为的相似用户，通过式(11)分别计算输入用户对其未评分商品的预测评分并排序，返回前m个商品作为对输入用户的最佳推荐结果。

本文算法的时间复杂度和空间复杂度如表2所示。

表2 时间空间复杂度表

3 实验结果及分析

本文选用MovieLens数据集来验证算法的有效性和优越性，验证评价指标选用平均绝对误差(MAE)来进行评判。

3.1 数据集与实验环境

本文所选用的数据集是由明尼苏达大学的GroupLens研究组公开提供的电影评分数据集MovieLens中的m-100k数据集[13]，如表3所示。

表3 数据集统计表

实验环境为：CPU为Inter Core i3，主频3.60 GHz，内存4 GB。

3.2 推荐准确性

本文使用的MAE评估推荐质量，该方法使用用户的真实评分和算法预测出的评分的绝对偏差来衡量该算法预测结果的准确率，MAE值越小代表推荐质量越好[13]。MAE公式如下:

(13)

式中：k为用户向量维度，预测的用户评分向量为v=(v1,v2,…,vk),真实用户评分向量为r=(r1,r2,…,rk)。

3.3 结果分析

本文算法中影响相似用户查找准确率和计算效率低主要参数是k和L。参数θ是最后进行计算推荐结果时影响MAE的权重因子。根据本文选择的MovieLens数据集选择参数L=8、θ=0.8，通过固定L、θ两个参数，多次选取不同的k值进行实验。对不同k值产生的推荐结果进行对比，通过MAE值的大小来选择最优k值。实验结果如图2所示。

图2 k值的大小影响MAE

图2结果表明，k值的大小都会影响最后的推荐准确率，这是因为k值决定了用户近邻的选择。在k<12时，随着k值的增加，推荐结果MAE值是线性减小的；当k>12时，随着k值的增加，推荐结果MAE值会线性上升。本次实验结果表明当k=12时本文算法具有最低的MAE值，这对本文算法选择加权权重wi具有启发式的意义。不同k值对应的MAE值的大小可以反比于模型权重wi。

为了验证本文算法的有效性，对比了本文算法与基于皮尔逊相似度的用户协同过滤算法(UBCF)、原始的基于E2LSH、基于LSH的用户相似度计算算法。表4为各模型的MAE值对比。

表4 用户相似度MAE值

其中本文算法选择t=3,分别是k1=10，k2=12，k3=14。权重为启发式的选择权重w1=0.3，w2=0.4，w3=0.3(当然各弱学习器的权重,也可以根据交叉验证集合的效果来选择，本文为了简要起见只是选择启发式的给定)。最终用户相似度计算MAE值可以体现本文融合技术的有效性。

图3表示随着模型个数t的增加，基于加权融合E2LSH算法的用户相似度计算的精度，其中对应k值分别取为如表5所示。

表5 模型个数与k值选择

图3 模型个数t的大小与用户相似度计算

图3中不同k值的权是启发式给定的，给定方案是与t=3的给定策略一致，k=12时权重最大，相邻为其次。可以看出，当t=5时预测用户相似度最为精确，随着t>5逐渐增加，用户相似度预测也越来越低，这是由于增加了多个弱学习器而引起的模型的不准确度。

为了验证本文算法的时间复杂度，对比了原始基于E2LSH算法，图4表示随着近邻数目的增加，原始基于E2LSH算法的计算时间随近邻用户增加而逐渐上升，而本文算法的运行时间基本上保持稳定状态，在近邻用户小于40的时候本文算法在运行时间上面没有明显优势，这是因为在用户基数比较少的时候，模型融合的效果不是特别明显。但当近邻用户基数逐渐增加后，本文算法在时间效率上面明显高于原始的E2LSH算法。

图4 本文算法与E2LSH时间复杂度对比

本文最后验证基于加权融合的用户相似度计算方法和原始基于E2LSH算法的推荐结果比较，主要对比不同近邻数目的推荐效果，其中近邻数目为10～100，原始E2LSH算法k=12、L=8、加权融合模型个数为5。图5为比较结果。

图5 本文算法与E2LSH推荐结果对比

当近邻用户数较小时，由于本文选择的模型融合对最优k值进行加权，所以在n<30时对比于原始基于E2LSH算法的推荐精度会偏低，这也是由于E2LSH算法在计算相似度较高的n个用户时较为准确的原因所导致的；当n>30时，由于E2LSH对该部分用户的相似度计算不够准确，从而影响了模型的推荐效果，而本文的加权融合模型可以有效地改进这一点，使得在n>30时用户的相似度也可以计算得较为精确。实验结果表明本文算法在用户相似度计算和推荐准确率方面都有较大提高。

4 结 语

本文首先描述了海量高维的现实数据环境下传统协同过滤算法的推荐效果以及计算效率的缺点，基于E2LSH的协同过滤算法本文融合框架，本文使用加权融合的E2LSH算法来查找相似用户，提高了传统的相似用户查找效率，同时提高了推荐结果的准确率。进一步的工作是如何把本文的推荐算法应用在大数据平台，比如Hadoop上进行部署，同时进一步提升算法精度和降低空间复杂度。

参考文献

[1] 嵇晓声,刘宴兵,罗来明.协同过滤中基于用户兴趣度的相似性度量方法[J].计算机应用,2010,30(10):2618-2620.

[2] 林朝辉.基于位置敏感哈希的分布式高维索引方法研究[D].华中科技大学,2012.

[3] 钟川,陈军.基于精确欧式局部敏感哈希的改进协调过滤推荐算法[J].计算机工程,2017,43(2):74-78.

[4] 贾忠涛.基于协同过滤算法的电影个性化推荐系统设计与实现[J].软件导刊,2015(1):86-88.

[5] 李红梅,郝文宁,陈刚.基于改进LSH的协同过滤推荐算法[J].计算机科学,2015,42(10):256-261.

[6] Fan Yongquan,Du Yajun.Improved user-based collaborative filtering method based on weighted similarity[J].Computer Engineering and Applications,2016,52(22)：222-225.

[7] Datar M,Immorlica N,Indyk P,et al.Locality-sensitive Hashing Scheme Based on p-stable Distributions[C]//Proceedings of the 20thAnnual Symposium on Computational Geometry.New York,USA,ACM Press,2004:253-262.

[8] 李红梅,郝文宁,陈刚.基于精确欧氏局部敏感哈希的协同过滤推荐算法[J].计算机应用,2014,34(12):3481-3486.

[9] 张桐.基于模型融合的迭代式分布式聚类框架的设计与实现[D].天津大学，2012．

[10] Shen Jie,Lin Ying.IRFCF:Iterative Rating Filling Collaborative Filtering Algorithm[M]//Zhou Xiaofang,Li Jianzhong,Heng Taoshen.Frontiers of WWW Research and Development.Berlin,Germany:Springer,2006:862-867.

[11] 韩亚楠,曹菡,刘亮亮.基于评分矩阵填充与用户兴趣的协同过滤推荐算法[J]计算机工程,2016,42(1):36-40.

[12] Zhang J Y,Pu P.A Recursive Prediction Algorithm for Collaborative Filtering Recommender Systems[C]//Proceedings of ACM Conference on Recommender Systems.New York,USA:ACM Press,2007:57-64.

[13] Andoni A,Razenshteyn I.Optimal Data-dependent Hashing for Approximate Near Neighbors[C]//Proceedings of the 47thAnnual ACM Symposium on Theory of Computing.New York,USA:ACM Press,2015:793-801.