基于加權融合的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.