基于改進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.

（責任編輯：劉亭亭）