基于Hash的Top-N推薦方法

朱 婷， 陳 德， 唐長兵， 鄭忠龍

(浙江師范大學 數(shù)理與信息工程學院,浙江 金華 321004)

0 引 言

隨著以計算機網絡為核心的信息技術的迅速發(fā)展，以及國際互聯(lián)網在全球的應用和普及，一種嶄新的商務模式——電子商務隨之產生.縱觀全球，每天都有成千上萬的商品在網上售賣，數(shù)以百計的客戶在網上購買.怎樣為用戶有效而準確地匹配所需商品至關重要，于是，推薦系統(tǒng)應運而生.Top-N推薦系統(tǒng)已經被電子商務網站廣泛使用，將最符合客戶需求的前N個項目列表推薦給用戶.

Top-N推薦系統(tǒng)主要是根據用戶的歷史信息估計其對于新項目的評分，并且把預測評分高的項目推薦給用戶.一般情況下，歷史信息分為顯性信息(評分)和隱性信息(點擊、收藏).在過去的10年里，學者已經提出了許多Top-N推薦系統(tǒng)[1].這些方法大致分為以下幾類：基于鄰域的協(xié)同過濾[2]、基于模型的協(xié)同過濾[3]、基于排序的方法[4]和基于內容的推薦方法[5].基于鄰域的方法又分為基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾[6]，一般的原則是確定用戶或項目之間的相似性[7].例如，基于項目的最近鄰(itemKNN)協(xié)同過濾方法，首先確定一組消費者已經購買過項目的相似項目，然后推薦出最相似的前N個項目給消費者.基于模型的方法一般是先建立一個模型，然后再生成推薦.例如，矩陣分解(MF)方法，利用潛在空間中用戶-項目的相似性提取用戶-項目的購買模式.純基于奇異值分解(PureSVD)的矩陣分解方法，通過用戶-項目矩陣的主奇異值向量描述用戶和項目的特征[8].高斯過程分解機(GPFM)構建了一個非線性的模型，更好地捕獲了用戶偏好與上下文間的相互作用，再生成推薦[9].本文采用基于鄰域的協(xié)同過濾Top-N推薦與Hash學習結合的方法構成推薦.

目前，各行各業(yè)積累的數(shù)據都呈現(xiàn)出爆炸式的增長趨勢,已經進入大數(shù)據時代.數(shù)據是與推薦技術密不可分的因素，而過多的數(shù)據會給存儲與運算帶來困難.Hash學習能通過機器學習機制,將數(shù)據映射成二進制串的形式[10]，顯著減少了數(shù)據的存儲和通信開銷.Hash學習的目的是學到用數(shù)據的二進制Hash碼表示，使得Hash碼盡可能地保持原空間中的近鄰關系，即保相似性.更具體地說，每個數(shù)據點都將會被編碼成一個緊湊的二進制串，并且原空間中相似的數(shù)據點會被映射成相似的二進制串.通過使用Hash碼，可以使得搜索復雜度呈恒定的或次線性的.此外，數(shù)據存儲所需的空間急劇下降.直接為給定數(shù)據集計算最優(yōu)的二進制碼是一個NP問題,為了避免NP問題，Hash方法通常采用2個步驟[11-12]:首先是投影階段，用一個線性或非線性的投影函數(shù)將樣本數(shù)據轉換成低維的向量；然后是量化階段，把投影得到的向量量化為二進制碼.

Hash學習已經被視為一種很有前景的快速相似性搜索方法[13].大多數(shù)Hash方法都采用漢明距度量Hash碼空間中點與點之間的相似度.2個字符串之間的漢明距是指字符串間對應位置不相同字符的個數(shù).但是漢明距在保相似性方面存在一定的局限性[14]，所以本文采用Manhattan距離來度量Hash碼之間的相似性.先通過Hash學習處理數(shù)據，找到相似用戶或項目，然后進行預測與推薦.

1 相關工作

近鄰搜索被廣泛運用于機器學習及相關的各個領域，如信息查詢及搜索、數(shù)據挖掘，還有計算機視覺等.近年來，伴隨著互聯(lián)網技術的高速發(fā)展，數(shù)據量也在顯著增長，這使得近鄰搜索的價值變得更大.然而，傳統(tǒng)的近鄰搜索要求遍歷數(shù)據集中的每一個數(shù)據點，而時間復雜度與數(shù)據集的大小成線性關系.因此，在大數(shù)據的背景下，傳統(tǒng)的近鄰搜索方法的計算時間會很長.此外，如果使用傳統(tǒng)的存儲格式來存儲數(shù)據，就會增加巨大的存儲成本.為了解決這個問題，學者提出了結合Hash技術進行有效近似近鄰搜索的方法[11-14].

1.1 投影階段

Hash學習的第1階段為投影階段，即將數(shù)據降維.大多數(shù)Hash算法采用的策略可以被分為2類：一類是獨立于數(shù)據的Hashing，如局部敏感Hashing(Locality Sensitive Hashing)[15]、監(jiān)督離散Hashing[16]和位移敏感Hashing(Shift Invariant Kernel Hashing)[17]；另一類是數(shù)據依賴Hashing，顧名思義，即在投影階段要依賴數(shù)據，如譜Hashing(spectral Hashing)[18]、迭代量化(iterative quantization)[19]和主成分分析Hashing(principle component analysis Hashing)[20].

面對海量的數(shù)據信息，想要直接從中挖掘出有價值的信息及規(guī)律非常困難.主成分分析法能夠將數(shù)據進行降維，最大限度地降低數(shù)據信息的重復疊加.

設樣本集U={X1,X2,…,Xn}，Xi={xi1,xi2,…,xim}(i=1,2,…,n)，且m

(1)

為了確保樣本數(shù)據中任何維度的偏移都是以零作為基準點，需對樣本數(shù)據進行中心化操作，即分別將矩陣每一列中的所有值減去其所在維度的平均值，得到矩陣D.衡量2個樣本間的關系，計算樣本的協(xié)方差矩陣C，即

(2)

通過式(2)計算協(xié)方差矩陣C的特征值λ={λ1,λ2,…,λn}，將得到的特征值按照從大到小的順序排列，并去除一些較小的值，得到λ={λ1,λ2,…,λm}.一個特征值對應一個維度，特征值越大表明該維度的數(shù)據越重要.

det(λE-C)=0;

(3)

(λiE-C)Z=0,i=1,2,…,m.

(4)

式(4)中，Z=(z1,z2,…,zn).將從式(3)解得的特征值λi逐個代入式(4)，得到特征向量Σ={ξ1,ξ2,…,ξm}.特征矩陣S由特征向量組成，即

(5)

原始矩陣X通過S作線性變換

Y=SX,

(6)

得到降維后的矩陣Y.

1.2 量化階段

在使用漢明距的條件下，SBQ與HQ不能有效地保持原始數(shù)據點之間的鄰域關系[14].圖1(a)是SBQ對一個投影維度的量化結果，其中C和D分別被量化為0和1，但C和D在實值空間中卻是相隔很近的；圖1(b)表示HQ對一個投影維度的量化結果，若用dh(A,B)表示A，B之間的漢明距，則dh(A,F)=dh(C,D)=1，dh(A,D)=2.然而在實值空間中A，F(xiàn)之間的距離應該大于C，D及A，D之間的距離.為了彌補這些缺陷，一些新的量化方式被逐漸提出，如雙比特量化(Double bit quantization 簡寫為 DBQ)[21]、多比特量化(Mulit-bit quantization)、自適應量化(Adaptive quantization)[22]和可變比特量化(Variable-bit quantization)[23]等.

圖1 SBQ與HQ對一個維度的量化示意圖

本文使用q比特量化(q>1)，將每個投影維度分成2q個區(qū)域，并用q個比特位的自然二進制碼去編碼每個區(qū)域的索引[14].比如，q=2，每個維度分別被分成4個區(qū)域，這4個區(qū)域的索引{0,1,2,3}的自然二進制碼為{00,01,10,11}；同理，若q=3，則區(qū)域的索引為{0,1,2,3,4,5,6,7}，其自然二進制碼為{000,001,010,011,100,101,110,111}.量化階段中另一個重要的因素是閾值.k-means聚類算法是一種有效的學習閾值的方法[24].因此，本文使用k-means聚類算法將每個投影維度的實數(shù)值聚類成2q類.

2 算法框架

通過Hash學習的2個步驟，將用戶-項目矩陣降維、量化為由二進制碼表示的矩陣，再選擇一個有效的距離來度量相似性，從而進行高質量的推薦.將Hash技術與推薦技術結合起來，能提高推薦的效率.

2.1 聚類量化

本文使用k-means算法將每一個投影維度的實值聚類為2q類，并用聚類的質心作為量化的閾值.k-means算法是一種經典的基于距離的聚類算法，即2個對象的距離越近，說明它們越相似.

對于給定的數(shù)據Ψ=(ψ(1),ψ(2),…,ψ(m))，計算每個樣本點的歸屬類,具體步驟如下：

第1步，隨機選取k(k=2q)個樣本點作為聚類質心μ1,μ2,…,μk∈Rm；

第2步，計算每一個樣例i(i=1,2,…,m)的歸屬類c(i)(c(i)=1,2,…,k)，即

(7)

當c(i)=j時，x(i)被歸為第j類，該聚類的質心為μj；

第3步，重新計算聚類質心的值

(8)

使用新的中心值替代原質心值，重復第2,3步，直到μj值趨于穩(wěn)定，并確定質心值.

2.2 距離選擇

大多數(shù)Hash方法采用漢明距測量Hash碼空間中點與點之間的相似性，然而漢明距自身存在著一些缺陷，使得整個Hash過程會毀壞原始空間中的鄰域結構.例如，圖2(b)用漢明距度量2比特二進制碼之間的距離，其最大漢明距為2，但卻不能有效地詮釋4個不同點之間的關系，這有違Hash的原則.因此，想要得到如圖2(a)所示的度量效果，就需要用另一種距離dr來代替漢明距.

(a)用dr度量2比特二進制碼之間距離示意圖

(b)用漢明距度量2比特二進制碼之間距離示意圖

設β=(β1,β2,…,βm)T,δ=(δ1,δ2,…,δm)T，距離dMa為

(9)

稱dMa為Manhattan距離[12].

(10)

如果將每一個投影維度量化成q比特的二進制碼，那么每一個表示長度為L的二進制碼串被分為L/q段，再進行距離計算.例如，

dr(10,00)=dMa(2,0)=2;

(11)

dr(000100,110000)=

dMa(0,3)+dMa(1,0)+dMa(0,0)=

3+1+0=4.

(12)

2.3 預測過程

根據上一節(jié)確定的Manhattan距離衡量用戶之間的相似度.對于有些項目而言，將目標用戶評論過的項目再次推薦給該用戶是沒有意義的，如用戶購買過的書、觀看過的電影等.所以本文在推薦階段采用排除用戶已評論過項目的方式避免重復推薦.但是，并不是所有用戶沒有評論過的項目都會被同等對待，實際操作中需要根據某些潛在條件對這些項目作出相應的調整.因此，本文根據目標用戶與相似用戶之間的不同相似性對不同的推薦項目使用不同的權重，以區(qū)分來自各個相似用戶的推薦項.權重的計算方式如下:

(13)

式(13)中：Wij表示用戶ui與用戶uj之間的權重；sim(ui,uj)表示用戶ui與用戶uj之間的相似度.

設Iiv為用戶ui的對項目Iv評過分的相似用戶的集合，用戶ui對項目Iv的預測評分為

(14)

式(14)中：|Iiv|為用戶ui的對項目Iv評過分的相似用戶的總數(shù)；rjv表示用戶uj對項目Iv的評分值；j=1,2,…,m；|I|是物品的總數(shù).

相似度計算與推薦的過程如下：

相似度:

輸入：用戶-項目評分矩陣，用戶的二進制碼矩陣Data，相似用戶數(shù)量Γ，推薦項目數(shù)量N，項目總數(shù)M.

輸出：相似用戶矩陣sim_user.

[t1,U_in]=sort(Data,"descend");

form=1,2,…,Mdo

forτ=1,2,…,Γdo

W(m,k)=t1(k)/sum(d(1:Γ));

%用戶的前τ個相似用戶

sim_users(τ)=U_in(1:τ);

%每一個用戶的M×Γ階相似用戶矩陣

推薦：

輸入：用戶-項目評分矩陣，相似用戶矩陣sim_user，推薦項目數(shù)量N，項目總數(shù)M，每一個用戶的相似用戶評論過的項目的矩陣RA.

輸出：推薦項目矩陣Re.

fori=1,2,…,Mdo

rated=find(Rating(i,:));

%無重復

RT(i) =RA(i)-rated;

%推薦項對應的評分

rt(i)=[Rating(i,RT(i))];

forj= 1,2,…,Ndo

Rr(i,j)=W(i,j)rt(i,j);

%W(i,j)是權重

%按Rr降序排列,選取前N項

T1=sort(Rr(i,1:τ),"decent");

Re(i,:)=T1(i,1:N).

3 實 驗

3.1 數(shù)據集

使用表1所示的4個數(shù)據集評價本文的方法.ML 100K是MovieLens 數(shù)據集的子集，是對電影評分的集合，分值為1～5.Netifix是Netifix大賽提供的數(shù)據集的子集，其中每一個用戶至少對10部視頻評過分，分值為1～5.Yahoo/Rating是Yahoo!Movies數(shù)據集中的用戶評分子集，在此數(shù)據集中，每一個用戶至少對5部電影評過分，每一部電影至少被3個用戶評過分，評分范圍為1～5.BX_Book提取了Book-Crossing數(shù)據集的隱性反饋，是對于書籍的數(shù)據集，其中每一本書至少被10個用戶閱讀過.

表1 數(shù)據集

對于顯性反饋，當評分值小于某個閾值時代表用戶不太喜歡這項目，所以在預測評分前，可以將該種項目的值都設為0，以減少預測時的計算量.例如，在評分值為1～5的評分系統(tǒng)中，認為當用戶給一個項目的評分值小于3時，表示該用戶不喜歡這個項目，該項目的評分值可以被設為0.

采用交叉驗證的方法證明本文方法的有效性，將每一個數(shù)據集隨機分為訓練集與測試集.訓練集用來訓練模型，然后為每一個用戶形成一個大小為N的推薦列表.對每一個用戶的推薦列表和測試集中該用戶的交互項進行比較，并用這種方法評價模型[25].本文用命中率(hit-rate，下文使用HR表示)及平均命中等級的倒數(shù)(average reciprocal hit-rank,下文用ARHR表示)度量推薦的質量.“命中”表示某個用戶測試集中交互過的項目(即經過用戶評分、評論或點擊、瀏覽等操作的項目)同樣出現(xiàn)在該用戶的推薦列表中.

HR定義為

(15)

式(15)中：g表示測試集中某用戶項目也在其推薦列表中的這類用戶數(shù)量；G表示測試集中的用戶總數(shù).若HR的值為1.0，則表示這個算法可以非常有效地推薦潛在項目；若HR的值為0，則表示這個算法不能推薦任何潛在項目.

HR將Top-N推薦列表中的每一項都看作具有相同的地位，但是，在列表中排在前面的項應該比排在后面的項擁有更高的權重.ARHR通過為每一個命中的項目設置權重來彌補HR的不足.在Top-N推薦列表中，越靠后的命中項目，其權重值越低.ARHR定義如下:

(16)

式(16)中，pi表示第i個用戶的命中項在其Top-N列表中的位置.當命中的項出現(xiàn)在推薦列表最前面位置時，ARHR的值達到最大；相反，當命中項出現(xiàn)在推薦列表的最后位置時，ARHR的值最小.

3.2 實驗結果

本文采用ItemKNN,PureSVD,WRMF,BPRKNN,BPRMF,SLIM,LorSLIM這7種推薦方法與本文的方法作對比，實驗結果如表2所示，其中推薦列表項目個數(shù)N=10.

表2 實驗結果

通過比較可以看出，本文方法在顯性數(shù)據集上的推薦效果更勝一籌.

PureSVD[5]通過用戶-項目矩陣的主奇異值向量來描述用戶和項目的特征;WRMF[26]采用加權矩陣來區(qū)分顯性數(shù)據與隱性數(shù)據;BPRKNN[27]是融合了貝葉斯最大后驗估計、k最近鄰協(xié)同過濾與矩陣分解的新方法;SLIM[28]是一種Top-N推薦方法，從用戶-項目矩陣中，將每一個項目編碼為其他項目的線性組合，通過求解L1范數(shù)和L2范數(shù)的優(yōu)化問題，進而得到一個表征相似度的稀疏矩陣.SLIM只能捕獲到被相同用戶購買或評論過的項目之間的關系，而通常一個用戶能夠評論的項目只是總項目的很小一部分;LorSLIM則是對SLIM的改進[20].

相似用戶的個數(shù)Γ與推薦項目個數(shù)N的取值對推薦效果也有影響.圖3為N=Γ時HR與ARHR的變化趨勢；圖4為Γ=40時HR和ARHR的變化趨勢；圖5為Γ=40時NDCG的變化趨勢.

圖3 N=Γ時，HR與ARHR的變化趨勢

NDCG(Normalized Discounted Cumulative Gain)通過推薦列表排序質量衡量推薦系統(tǒng)的性能，定義為

(17)

(18)

式(17)中，r(i)是用戶對第i個項目的評分值；式(18)中，IDCGN是DCGN的最理想值.

q的取值關系到每一個投影維度的聚類及其被量化的長度，將q分別取值為2,3,4進行試驗比較，結果如圖6所示.從圖6不難看出，當q=2時，效果更好.

圖4 Γ=40時，HR與ARHR的變化趨勢

圖5 Γ=40時，NDCG的變化趨勢 圖6 q=2,3,4時召回率-準確率曲線圖

4 結 語

本文針對目前電子商務面臨的數(shù)據過大、信息稀疏等問題，提出了將Hash與協(xié)同過濾相結合的推薦模型.先對原始數(shù)據進行PCA降維處理，剔除一些冗余信息，降低運算強度；再對降維后的數(shù)據進行二進制碼量化，減少數(shù)據儲存空間.采用dr距離作為度量目標用戶與鄰居用戶相似性的手段，直觀且有效.從實驗結果可以看出，這個方法提高了推薦質量.

[1]Deshpande M,Karypis G.Item-based top-Nrecommendation algorithms[J].ACM Trans Inf Syst,2004,22(1):143-177.

[2]吳海峰,張書奎,林政寬,等.融合隱語義和鄰域算法的興趣點推薦模型[J].計算機應用研究,2017,21(16):1-8.

[3]居斌,錢沄濤,葉敏超.基于結構投影非負矩陣分解的協(xié)同過濾算法[J].浙江大學學報:工學版,2015,49(6):1319-1325.

[4]Li H.Learning to rank for information retrieval and natural language processing[J].Synth Lect Hum Lang Technol,2009,4(1):113-119.

[5]Arora G,Kumar A,Devre G S,et al.Movie recommendation system based on users′ similarity[J].Int J Comp Sci Mob Comp,2014,3(4):765-770.

[6]Patra B K,Launonen R,Ollikainen V,et al.A new similarity measure using Bhattacharyya coefficient for collaborative filtering in sparse data[J].Knowl-Based Syst,2015,82(2):163-177.

[7]Ricci F,Rokach L,Shapira B.Introduction to recommender systems handbook[J].Rec Syst Handb,2010,35(3):1-35.

[8]Cremonesi P,Koren Y,Turrin R.Performance of recommender algorithms on top-Nrecommendation tasks[C]//Recommender Systems Recsys 2010.Barcelona:Association for Computing Machinery,2010:39-46.

[9]Shi Y,Karatzoglou A,Baltrunas L,et al.TFMAP:optimizing MAP for top-Ncontext-aware recommendation[C]//Special Interest Group on Information Retrieval.Portland:Association for Computing Machinery,2012:155-164.

[10]李武軍,周志華.大數(shù)據哈希學習:現(xiàn)狀與趨勢[J].科學通報,2015,60(5):485-490.

[11]Kong Weihao,Li Wujun.Double-bit quantization for hashing[C]//The Twenty-Sixth Artificial Intelligence.Toronto:Association for the Advance of Artificial Intelligence,2012:385-407.

[12]Gong Y,Lazebnik S,Gordo A,et al.Iterative quantization:A procrustean approach to learning binary codes for large-scale image retrieval[J].IEEE Trans Pattern Anal Mach Intell,2013,35(12):2916-2929.

[13]Wang J,Liu W,Kumar S,et al.Learning to Hash for Indexing big data:A survey[J].Proc IEEE,2015,104(1):34-57.

[14]Kong W,Li W J,Guo M.Manhattan Hashing for large-scale image retrieval[C]//The 35th International Conference on Research and Development in Information Retrieval.Portland:Association for Computing Machinery,2012:45-54.

[15]Andoni A,Indyk P.Near-optimal Hashing algorithms for approximate nearest neighbor in high dimensions[J].Found Comp Sci Ann Sym,2006,51(1):459-468.

[16]Shen F,Shen C,Liu W,et al.Supervised discrete Hashing[J].Comp Sci,2015,62(2):37-45.

[17]Chua T S,Tang J,Hong R,et al.NUS-WIDE:A real-world web image database from National University of Singapore[C]//International Conference on Image and Video Retrieval.Santorini Island:Association for Computing Machinery,2009:1-9.

[18]Weiss Y,Torralba A,Fergus R.Spectral Hashing[C]//Conference on Neural Information Processing Systems.Vancouver:Neural Information Processing Systems,2008:1753-1760.

[19]Gong Y,Lazebnik S.Iterative quantization:A procrustean approach to learning binary codes[C]//Conference on Computer Vision and Pattern Recognition.Colorado:Computer Society,2011:817-824.

[20]Cheng Y,Yin L,Yu Y.LorSLIM:Low rank sparse linear methods for top-Nrecommendations[C]//International Conference on Data Mining.Atlantic City:Computer Society,2015:90-99.

[21]Kong Weihao,Li Wujun.Double-bit quantization for Hashing[C]//The Twenty-Sixth Conference on Association for the Advance of Artificial Intelligence.Toronto:Association for the Advance of Artificial Intelligence,2012:346-355.

[22]Xiong C,Chen W,Chen G,et al.Adaptive quantization for Hashing:An information-based approach to learning binary codes[C]//The 14th Society for Industrial and Applied Mathematics International Conference on Data Mining.Bethlehem:American Statistical Association,2014:1-9.

[23]Moran S,Lavrenko V,Osborne M.Variable bit quantisation for LSH[C]//Meeting of the Association for Computational Linguistics.Sophia:Association for Computational Linguistics,2013:753-758.

[24]He K,Wen F,Sun J.k-means Hashing:An affinity-preserving quantization method for learning binary compact codes[J].Proc IEEE,2013,9(4):2938-2945.

[25]Kang Z,Peng C,Cheng Q.Top-Nrecommender system via matrix completion[C]//Association for the Advancement of Artificial Intelligence.Tucson:Association for Computational Linguistics,2016:38-49.

[26]Pan R,Zhou Y,Cao B,et al.One-class collaborative filtering[J].Data Mining,2008,29(5):502-511.

[27]Rendle S,Freudenthaler C,Gantner Z,et al.BPR:Bayesian personalized ranking from implicit feedback[C]//Conference on Uncertainty in Artificial Intelligence.Montreal:Association for Uncertainty in Artificial Intelligence,2009:452-461.

[28]Ning X,Karypis G.SLIM:Sparse linear methods for top-Nrecommender systems[J].Data Mining,2011,11(3):497-506.