基于改進(jìn)MPLSH的協(xié)同過濾推薦算法

王旭寧超+劉盛英杰

摘要：針對(duì)基于項(xiàng)目的協(xié)同過濾推薦算法（Item-CF）在處理高維項(xiàng)目評(píng)分?jǐn)?shù)據(jù)時(shí)出現(xiàn)計(jì)算效率急劇下降的不足，提出一種將改進(jìn)的多探尋局部敏感哈希算法（MPLSH）和Item-CF相結(jié)合的推薦算法。改進(jìn)的MPLSH通過將待搜索哈希桶的探尋方式由原始的哈希值差異導(dǎo)向替換為由距離遠(yuǎn)近導(dǎo)向，從而減少M(fèi)PLSH需要探尋哈希桶的個(gè)數(shù)，縮小了Item-CF中相似項(xiàng)目集合的查找范圍。并利用MPLSH本身具有的高效數(shù)據(jù)降維特性，提高Item-CF在高維項(xiàng)目評(píng)分?jǐn)?shù)據(jù)中尋找相似項(xiàng)目集合的速度，從而有效改善Item-CF在處理高維項(xiàng)目評(píng)分?jǐn)?shù)據(jù)時(shí)計(jì)算效率下降的問題。通過在MovieLens電影評(píng)分?jǐn)?shù)據(jù)集上進(jìn)行實(shí)驗(yàn)和算法比較，驗(yàn)證了該算法的有效性。

關(guān)鍵詞：協(xié)同過濾；多探尋；局部敏感哈希；項(xiàng)目相似度；推薦算法

DOIDOI：10.11907/rjdk.172174

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

作為緩解信息爆炸問題的有效手段之一，推薦系統(tǒng)（Recommended System，RS）[1，2]在諸多領(lǐng)域得到廣泛應(yīng)用，作為推薦系統(tǒng)核心的推薦算法也逐漸成為研究熱點(diǎn)。推薦算法的功能就是通過獲取數(shù)據(jù)，分析預(yù)測(cè)用戶將會(huì)對(duì)哪些未瀏覽或未購(gòu)買的項(xiàng)目感興趣。推薦算法可分為基于模型的推薦算法、協(xié)同過濾推薦算法和混合推薦算法。

基于項(xiàng)目的協(xié)同過濾推薦算法（Item-CF）是協(xié)同過濾推薦算法中的一種，其從項(xiàng)目角度進(jìn)行推薦分析。首先通過項(xiàng)目的評(píng)分值計(jì)算項(xiàng)目間的相似度，找到與目標(biāo)項(xiàng)目相似度最高且目標(biāo)用戶還未評(píng)過分的項(xiàng)目作為候選項(xiàng)目集合；然后根據(jù)目標(biāo)用戶對(duì)候選項(xiàng)目集合中各個(gè)項(xiàng)目的最近鄰項(xiàng)目評(píng)分的加權(quán)平均值來預(yù)測(cè)目標(biāo)用戶對(duì)此項(xiàng)目的感興趣程度，分值越高代表其越有可能對(duì)此項(xiàng)目感興趣，并據(jù)此產(chǎn)生推薦。然而隨著項(xiàng)目評(píng)分?jǐn)?shù)據(jù)維度的增加，在高維項(xiàng)目評(píng)分?jǐn)?shù)據(jù)下該算法的效率會(huì)大大下降。不少學(xué)者提出了改進(jìn)算法，比如Wei等[3]基于項(xiàng)目聚類的方法來縮小目標(biāo)項(xiàng)目的最近鄰搜索范圍，從而加快相似項(xiàng)目計(jì)算的速度。文獻(xiàn)[4]提出了一個(gè)基于協(xié)同聚類的增量協(xié)同過濾框架，用以提高計(jì)算效率。文獻(xiàn)[5]使用增量奇異值分解技術(shù)進(jìn)行協(xié)同過濾推薦，使用此方法可以降低項(xiàng)目集合的維數(shù)，加快計(jì)算速度。

針對(duì)此問題，本文提出一種將改進(jìn)的MPLSH與Item-CF相結(jié)合的推薦算法，提高處理高維項(xiàng)目評(píng)分?jǐn)?shù)據(jù)時(shí)的推薦計(jì)算效率。

1 相關(guān)概念

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

在介紹MPLSH之前，需要先了解最原始的局部敏感哈希算法（LSH）[6，7]。LSH基于這樣的假設(shè)：如果兩個(gè)點(diǎn)在原有高維空間中是相似的，那么分別經(jīng)過特定的哈希函數(shù)轉(zhuǎn)換到低維空間后它們也有很大的可能是相似的，這就為高維數(shù)據(jù)中相似項(xiàng)目的快速選取提供了可能。LSH的主要思想是通過設(shè)計(jì)一族哈希函數(shù)將高維空間中的點(diǎn)集映射到一個(gè)由哈希碼所構(gòu)成的低維空間[8]，并使其分散到若干個(gè)哈希桶中，此過程會(huì)形成一張到多張哈希表。原始數(shù)據(jù)集中相似的數(shù)據(jù)點(diǎn)被哈希到同一個(gè)哈希桶中的概率很高。在進(jìn)行相似點(diǎn)搜索時(shí)，只需要通過哈希函數(shù)定位目標(biāo)數(shù)據(jù)點(diǎn)所在的哈希桶，然后將這些桶中的數(shù)據(jù)點(diǎn)作為候選集合，將它們與目標(biāo)數(shù)據(jù)點(diǎn)進(jìn)行相似度計(jì)算即可。這樣做可以有效地過濾出大量的無(wú)關(guān)數(shù)據(jù)，從而避免了不必要的計(jì)算過程，加速最近鄰數(shù)據(jù)點(diǎn)獲取。LSH雖然是近似技術(shù)，不能保證相似性檢索的精確性，但在實(shí)際計(jì)算中，其通?？梢栽诤苄〉臅r(shí)間復(fù)雜度下返回精確或近似精確的相似結(jié)果，提高高維數(shù)據(jù)的處理效率[9]。

LSH為了保證搜索的效率和準(zhǔn)確度，往往需要使用大量的哈希表，這樣會(huì)導(dǎo)致大量存儲(chǔ)空間被占用。相關(guān)學(xué)者提出利用多探尋的方法來解決空間占用過大的問題，使用此方法的LSH被稱為多探尋局部敏感哈希（MPLSH）[10]。其主要思想是在探尋目標(biāo)點(diǎn)對(duì)應(yīng)哈希桶的同時(shí)，探尋與該哈希桶有近似編碼的哈希桶，因?yàn)橄嚓P(guān)學(xué)者認(rèn)為如果一個(gè)點(diǎn)的近鄰點(diǎn)沒有被哈希到與之相同的哈希桶中也一定被哈希到了與之相鄰的哈希桶中[11]。

MPLSH的多探尋是一種步進(jìn)式的，在余弦相似度度量下哈希值是01值，它對(duì)應(yīng)的多探尋首先是探尋目標(biāo)點(diǎn)所在的哈希桶，然后探尋與目標(biāo)點(diǎn)所在哈希桶哈希值僅有一位不同的哈希桶，接著探尋兩位不同的哈希桶，以此類推，直到回收夠指定數(shù)量的哈希桶后結(jié)束算法。

這種方法可以從少量哈希表中獲取足量的哈希桶，在降低內(nèi)存空間占用的同時(shí)擴(kuò)大了候選空間，從而達(dá)到與LSH接近的搜索范圍，但是這種方法的不足是其檢索時(shí)間比傳統(tǒng)LSH要長(zhǎng)。

1.2 基于項(xiàng)目的協(xié)同過濾推薦算法（Item-CF）

基于項(xiàng)目的協(xié)同過濾推薦算法（Item-CF）[12，13]認(rèn)為與用戶喜愛的項(xiàng)目相似度高的其它項(xiàng)目有很大可能再次被用戶所喜愛，因此可以通過項(xiàng)目的評(píng)分找到與用戶喜愛項(xiàng)目相似度高的項(xiàng)目，構(gòu)成候選項(xiàng)目集合，并預(yù)測(cè)用戶對(duì)其中各個(gè)項(xiàng)目感興趣的程度。其推薦過程主要包含兩個(gè)步驟：①項(xiàng)目間的相似度計(jì)算；②候選項(xiàng)目的預(yù)測(cè)評(píng)分。其中項(xiàng)目間相似度計(jì)算是最為關(guān)鍵的一個(gè)步驟。最常用的幾種計(jì)算方法是：余弦相似度、修正的余弦相似度和相關(guān)相似度。本文采用修正的余弦相似度來計(jì)算項(xiàng)目間的相似度。

2 改進(jìn)的推薦算法

2.1 對(duì)MPLSH的改進(jìn)

本文通過分析MPLSH的步進(jìn)式探尋方法，發(fā)現(xiàn)存在鄰近哈希桶的探尋過于盲目的問題，導(dǎo)致計(jì)算速度不及LSH。因此，本文試圖用由距離為導(dǎo)向的探尋方式替換原始的以哈希值差異為導(dǎo)向的探尋方式，縮小MPLSH需要探尋的哈希桶數(shù)量，提高M(jìn)PLSH的計(jì)算速度，并將其與Item-CF相結(jié)合，改善Item-CF在處理高維數(shù)據(jù)時(shí)效率低下的問題。

本文使用距離為多探尋的導(dǎo)向，僅去探尋那些與目標(biāo)項(xiàng)目所在哈希桶距離最近的哈希桶，是基于這樣一個(gè)概念：高維空間中相似的兩點(diǎn)，即距離近的兩點(diǎn)，經(jīng)過哈希函數(shù)處理投影到低維空間后，投影點(diǎn)仍然有很大的概率距離相近。說明如下。

對(duì)高維空間中任意兩點(diǎn)x和y，若‖x-y‖越小則對(duì)任意一個(gè)大于0的常數(shù)λ，有P{‖VTx-VTy‖<λ}越大。其中‖x-y‖為原高維空間中兩點(diǎn)之間的距離，P{‖VTx-VTy‖<λ}表示投影后兩點(diǎn)之間的距離小于λ的概率。令d=‖x-y‖，存在一正交矩陣C使得Cz=x-y，其中z=[d，0，…，0]T。則有VTx-VTy=VT（x-y）=VTCz，VT的每個(gè)元素均為服從標(biāo)準(zhǔn)高斯分布的隨機(jī)變量且相互獨(dú)立。因?yàn)镃為正交矩陣，根據(jù)高斯分布的特性，VTC的每個(gè)元素均服從標(biāo)準(zhǔn)高斯分布且相互獨(dú)立。因此‖VTCz‖可以轉(zhuǎn)化為dX1，其中X1為服從標(biāo)準(zhǔn)高斯分布的隨機(jī)變量。故有P{‖VTx-VTy‖<λ}=P{dX1<λ}=PX1<λd=2Φλd-1，因?yàn)棣岛瘮?shù)在定義域內(nèi)單調(diào)遞增，當(dāng)d越小時(shí)P{‖VTx-VTy‖<λ}取值越大，即高維空間中兩點(diǎn)的距離越近，它們經(jīng)過哈希函數(shù)投影到低維空間中時(shí)就越有可能距離越近。因此本文利用這一特性，使用近鄰哈希桶與目標(biāo)項(xiàng)目點(diǎn)的距離代替近鄰哈希桶中的項(xiàng)目與目標(biāo)項(xiàng)目點(diǎn)的距離，并據(jù)此進(jìn)行探尋。

綜上所述，本文提出的改進(jìn)MPLSH優(yōu)勢(shì)在于充分利用了高維空間中距離較近的相似點(diǎn)在經(jīng)過特定哈希函數(shù)降維后，仍有很大概率保持距離相近這一特性，從而有效地縮小需要探尋哈希桶的范圍，加快MPLSH的計(jì)算速度。

3 實(shí)驗(yàn)部分

3.1 實(shí)驗(yàn)數(shù)據(jù)來源及度量標(biāo)準(zhǔn)

3.1.1 數(shù)據(jù)集來源

本實(shí)驗(yàn)數(shù)據(jù)集采用美國(guó)明尼蘇達(dá)大學(xué)GroupLens研究組提供的電影評(píng)價(jià)數(shù)據(jù)集MovieLens（https：//grouplens.org/datasets/movielens/）。該數(shù)據(jù)集包含6 040名用戶對(duì)3 900部電影的1 000 209條評(píng)分?jǐn)?shù)據(jù)，每位用戶至少對(duì)20部電影進(jìn)行了評(píng)分，所有電影屬于19個(gè)類別，評(píng)分值大小分布在[0，5]區(qū)間內(nèi)，如表1所示。

本文將算法計(jì)算所消耗的時(shí)間作為另一個(gè)評(píng)價(jià)的標(biāo)準(zhǔn)，計(jì)算消耗的時(shí)間越短其性能越好，即推薦系統(tǒng)的效率越高。

3.2 實(shí)驗(yàn)結(jié)果及分析

本文將基于改進(jìn)MPLSH的Item-CF與基于MPLSH的Item-CF以及原始的Item-CF進(jìn)行比較，主要對(duì)比3種算法的計(jì)算效率和準(zhǔn)確度差異。實(shí)驗(yàn)結(jié)果如圖2所示。

圖2是最近鄰項(xiàng)目數(shù)對(duì)這3種算法MAE值的影響，為了獲得比較明顯的效果比較，需要計(jì)算使得各個(gè)算法MAE值均較小時(shí)的最近鄰項(xiàng)目數(shù)。從圖2中可以看出隨著最近鄰項(xiàng)目數(shù)的增加3種方法的MAE首先大幅度的下降，接著到達(dá)最小值，最后逐漸上升趨于穩(wěn)定。其中MAE值大小的規(guī)律總體呈現(xiàn)MPLSH>改進(jìn)MPLSH>Item-CF。從圖2中可以發(fā)現(xiàn)，當(dāng)最近鄰項(xiàng)目數(shù)達(dá)到300左右時(shí)MAE值均較小。

本文取最近鄰項(xiàng)目數(shù)為300對(duì)3種方法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2所示。可以觀察到改進(jìn)MPLSH的MAE為0.716，優(yōu)于MPLSH的0.722，略差于原始Item-CF的0.704。同時(shí)任意時(shí)刻改進(jìn)MPLSH探尋哈希桶的數(shù)量均小于同時(shí)刻MPLSH的探尋數(shù)量，且改進(jìn)MPLSH的計(jì)算耗時(shí)均少于MPLSH。

為了方便進(jìn)一步的分析，將實(shí)驗(yàn)結(jié)果繪制成折線圖。如圖3所示，其中橫軸代表算法結(jié)果的MAE值，縱軸代表算法的計(jì)算時(shí)間。實(shí)線代表基于改進(jìn)MPLSH的Item-CF，虛線代表基于MPLSH的Item-CF。

通過圖3可以觀察到，在獲得相同MAE值的情況下，基于改進(jìn)MPLSH的Item-CF運(yùn)行時(shí)間均少于基于MPLSH的Item-CF。其中最小的時(shí)間差值為4.7s，最大的時(shí)間差值為12.3s，平均差值達(dá)到了8.5s，說明Item-CF的計(jì)算效率確實(shí)獲得了提升。在相同運(yùn)行時(shí)間的情況下，基于改進(jìn)MPLSH的Item-CFMAE值也略低于基于MPLSH的Item-CF，說明本改進(jìn)算法的準(zhǔn)確度是可以接受的。結(jié)合表2中的數(shù)據(jù)可以發(fā)現(xiàn)，本文的改進(jìn)MPLSH所需要探尋的哈希桶數(shù)量均小于同等條件下的MPLSH，說明本文對(duì)MPLSH的改進(jìn)是有效的。

4 結(jié)語(yǔ)

本文針對(duì)傳統(tǒng)協(xié)同過濾推薦算法在處理高維項(xiàng)目評(píng)分?jǐn)?shù)據(jù)時(shí)會(huì)產(chǎn)生實(shí)時(shí)性差的問題，提出了一種基于改進(jìn)MPLSH的協(xié)同過濾推薦算法。實(shí)驗(yàn)結(jié)果表明：相較基于MPLSH的協(xié)同過濾推薦算法，本文的算法可以在保證推薦準(zhǔn)確度的前提下獲得更高的效率，有效緩解協(xié)同過濾算法在處理高維項(xiàng)目評(píng)分?jǐn)?shù)據(jù)時(shí)的效率下降問題。

本文對(duì)協(xié)同過濾算法處理高維數(shù)據(jù)的效率問題進(jìn)行了研究，提出的算法雖然在MAE上略差于原始算法，但計(jì)算效率有較明顯的提升。該算法存在進(jìn)一步改進(jìn)的空間，如當(dāng)數(shù)據(jù)維度不夠高時(shí)，效率的提升可能不夠明顯；未考慮將用戶興趣隨時(shí)間變化的問題；算法的適用范圍研究等，這些問題有待后續(xù)研究。

參考文獻(xiàn)：

[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] 韋素云，業(yè)寧，朱健，等.基于項(xiàng)目聚類的全局最近鄰的協(xié)同過濾算法[J].計(jì)算機(jī)科學(xué)，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] 鄧愛林，朱揚(yáng)勇，施伯樂.基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào)，2003，14（9）：1621-1628.

（責(zé)任編輯：劉亭亭）