一種兩階段聯合哈希的協同過濾算法

張輝宜,侯耀祖,陶 陶

(安徽工業大學 計算機學院,安徽 馬鞍山 243032)

0 概述

個性化推薦技術由于能為用戶推薦感興趣的內容,提高用戶的使用體驗,進而增強用戶粘性以及用戶的忠誠度,已經得到很多大型互聯網公司(如Amazon、Alibaba、Tencent等)的廣泛關注和深入研究。

協同過濾是推薦系統中流行的技術之一,其主要思想是相似的用戶會偏好相似的項目,它主要利用用戶過往的行為如評分、點擊等信息,無需關注項目的內容。協同過濾還具有新異推薦、對用戶友好等特點,因而受到研究者的青睞,得到廣泛研究。常見的協同過濾算法主要分為2類:一類是基于模型的方法,利用數據挖掘和機器學習等技術在數據集上訓練出模型,然后基于模型為目標用戶對未評分項目的偏好度進行預測,從而完成推薦;另一類是基于內存的方法,通過計算用戶之間或項目之間的相似度,利用相似度來獲取用戶或項目的近鄰,對近鄰評分加權來預測用戶對未評分項目的評分,進而實現對用戶推薦,文獻[1]對這2類方法進行了詳細的介紹與總結。近年來,矩陣分解技術因為其在擴展性及預測準確度方面的優勢得到廣泛關注[2-3]。矩陣分解技術通過分解用戶評分矩陣,得到低維的用戶和項目的特征向量,利用用戶和項目特征向量的點積來衡量用戶對項目的偏好程度,使用戶和項目向量的維度得到降低,且其利用特征向量的點積來取代傳統的相似度計算,因此推薦效率得到較大提高。

然而,隨著系統中數據量的極速增長,用戶對項目的評分數據呈現海量高維的特點,這對傳統的協同過濾算法提出了嚴峻的挑戰。一方面,由于數據的體量增大、維度增加,評分數據表現出高稀疏性,這導致傳統的相似度方法在計算用戶或項目的相似度時不夠準確,近鄰檢索準確度低,預測精度低;另一方面,體量和維度的增加也帶來了計算和存儲開銷的極速增長,導致推薦系統的效率下降。

本文在分析前人工作的基礎上,提出一種兩階段聯合哈希(Two-stage Joint Hashing,TSH)的協同過濾算法。從用戶或項目視角上應用主成分分析(Principal Component Analysis,PCA)[4]技術,采用迭代量化哈希(Iterative Quantization,ITQ)[5]的策略,得到保留該視角分布信息的二值碼,然后由已得到的二值碼和評分信息來約束用戶與項目的海明距離,得到另一視角的二值碼。

1 哈希學習相關研究

協同過濾系統為目標用戶在項目集上檢索偏好的項目,這個過程可以看做是一個相似性檢索問題:檢索用戶感興趣的項目[6]。盡管傳統的相似性度量,如Jaccard相似系數、余弦相似系數和歐式距離等,已經廣泛使用在推薦系統中,但是其在高維海量的數據上計算量過大且對于高稀疏度數據的相似度計算精度低。研究表明,哈希學習[7]在相似性檢索方面有獨特的優勢,它通過機器學習機制將數據映射成二進制串的形式,能夠顯著減少數據的存儲和通信開銷,從而有效提高學習系統的效率[8]。哈希學習學到的二值碼能保持原空間中的近鄰關系,其在快速相似性檢索領域的應用具有強大的生命力,已經被廣泛應用到信息檢索[9]、計算機視覺[10-11]和推薦系統[12-14]等領域。

迭代量化哈希算法是最有代表性的哈希算法之一,由于它最早考慮到不同維度信息量分布不均問題,并且提出對主成分分析后的低維特征進行迭代量化的策略,因此在檢索性能和速度上都取得較大的提高。其主要思想為:

1)在原始空間上應用主成分分析技術對高維樣本進行降維,將其高維特征映射到低維空間,得到低維空間的特征表示。記X為原始空間數據,降維后的維度為c,W為投影矩陣,V為應用PCA后得到的原始高維數據的低維表示,V=XW。

2)對V量化進行編碼,考慮到數據方差分布不均的問題即投影后的低維數據可區分性差,直接對V進行量化無法很好地代表樣本的真實分布情況,因此ITQ算法提出數據旋轉的策略,若W為最優的投影矩陣,則WR也是如此,其中R為c×c的正交矩陣,基于此對PCA降維后的樣本進行旋轉,使旋轉后的數據在各個主方向上方差盡可能的均衡,建立如下損失方程:

(1)

其中,B為期望得到的哈希編碼。求解式(1)可以通過隨機初始化R,固定R求解B,再固定B求解R的步驟迭代進行直至達到局部最優解。

ITQ算法具有計算復雜度低、檢索性能高的優點,在解決傳統的協同過濾算法應對海量高維數據時性能不足的問題上有獨特的優勢,但它也有一個明顯的缺點,即為提升檢索性能所做平衡方差的工作會造成信息量的丟失,這在推薦系統稀疏評分數據上尤其明顯,因此直接從用戶和項目視角上應用ITQ算法會損失大量信息,影響推薦性能。

針對上述問題,本文提出一種兩階段聯合哈希的協同過濾算法,既可以利用ITQ算法的優點,又結合系統中數據的性質改善ITQ算法的缺點,使得ITQ算法能更好地應用在推薦系統中。

2 本文算法

假定系統中的用戶數量為m,項目數量為n,用戶對項目的評分構成的評分矩陣為S∈m×n,其中,Sij表示用戶i對項目j的評分,分值越高表示用戶越偏好該項目,向量ui=(Si1,Si2,…,Sin)為用戶i的向量表示,向量vj=(S1j,S2j,…,Smj)為項目j的向量表示,哈希后的用戶空間為U:{u1,u2,…,um}∈{-1,1}c×m,哈希后的項目空間為V:{v1,v2,…,vn}∈{-1,1}c×n。tr(.)表示矩陣的跡,‖.‖F表示矩陣的Frobenius范式,sgn()為符號函數,輸入大于等于0時輸出1,反之輸出-1。

2.1 基于用戶視角的兩階段聯合哈希算法UTSH

基于用戶視角的兩階段聯合哈希算法的主要階段如下:

1)在用戶視角進行降維,將用戶映射到低維空間,應用PCA技術得到c位用戶的特征向量,對之量化即可得到c位用戶的二值碼。為了減少量化過程的信息損失,引用文獻[10]中的迭代量化策略,具體的流程如下:

(1) 在用戶空間應用PCA,得到c位用戶的特征向量f1,f2,…,fn∈F。

(2) 建立量化過程的損失方程:

(2)

其中,R為正交的旋轉矩陣,量化后的用戶空間為U,隨機初始化R后,交替執行如下2個過程直至得到局部最優解,從而得到最優的U:保持R不變,按照U=sgn(FR)來更新U;保持U不變,對UFT進行奇異值分解(Singular Value Decomposition,SVD)為PΩQT,其中,P為c×c階酉矩陣,Q為m×m階酉矩陣,按照R=PQT來更新R。

2)通過系統中的評分來約束用戶與項目的海明距離,即以用戶與項目在低維空間中的相似度來預測用戶對項目的偏好程度。參照文獻[6]中用戶ui與項目vj的相似度定義,如式(3)所示。

(3)

其中,I()為指示函數,如果條件為真則返回1,否則返回0。由上面的定義可知,當用戶與項目的海明距離越小時,相似度越接近1;海明距離越大時,相似度越接近于0?；谶@個性質可以建立如下的損失方程:

s.t.V∈{-1,1}c×n

(4)

在約束條件下,直接由式(4)求解最優的V是一個NP-難問題[14],在此引入輔助集合V’={X∈Rc×n|X1=0,XTX=nI},距離d(V,V’)=minX∈V'||V-X||F,基于式(4),可得:

s.t.V∈{-1,1}c×n

(5)

通過調整足夠大的參數α,使得X逼近V即d(V,V’)=0,進而將難以求解的V的離散約束轉移到連續的容易求解的X上,由約束條件的性質,式(5)可化簡為:

s.t.V∈{-1,1}c×n,XTX=nI,X1=0

(6)

將求解V、X的問題分解為求解V和X的2個子問題,交替優化這2個子問題直至收斂即可求得V的最優解。

在求解V的子問題中,保持X不變,對于vj∈V有:

(7)

其中,Rj為S中已知的用戶對項目vj的評分集合。由于vj的值是離散的,故采用逐位更新的策略更新vj,更新規則同文獻[14]如下所示:

(8)

對于X的子問題,保持V不變,由式(6)可得:

argmaxXtr(VTX)

s.t.XTX=nI,X1=0

(9)

UTSH算法描述如下:

輸入評分矩陣Sm×n,二值碼位數c,權衡系數α

輸出用戶的二值碼Uc×m,項目的二值碼Vc×n

1)F←PCA(S)

2)隨機初始化正交矩陣R

3)交替執行(1)、(2)直至收斂

(1)U←sgn(FR)

(2)(P,Q)←SVD(UFT),R←PQT

4)初始化V,X,將S放縮

5)交替執行(1)、(2)直至收斂

(1) for j=1 to n :

重復以下過程直至收斂

for k=1 to c :

(2)構造中心矩陣C

6)返回U、V

2.2 基于項目視角的兩階段聯合哈希算法ITSH

基于項目視角的兩階段哈希算法先從項目視角哈希,再通過評分約束用戶與項目的海明距離,進一步得到用戶二值碼的算法,由于其過程與上述基于用戶視角的兩階段哈希算法對稱,在此不再贅述。

3 仿真實驗

為驗證算法的有效性,對UTSH、ITSH、ITQ和二值化的矩陣分解算法BinMF[15]進行仿真實驗。其中,ITQ分別在用戶和項目視角上哈希來獲得用戶和項目的二值碼;BinMF為二值化的基于交替最小二乘法的矩陣分解算法,即對矩陣分解算法生成的特征表示以中位數作為閾值進行量化,得到用戶和項目的二值碼。

3.1 數據集

仿真實驗數據選擇MovieLen-1M數據集[16]。MovieLens-1M數據集共包括6 040個用戶對3 900部電影的1 000 209個評分,可以看出只有約4%的用戶-電影存在評分。評分是從1到5的整數,評分越低表示用戶對該電影的偏好程度越低,反之,評分越高則表示用戶對該電影偏好程度較強。通常,從數據集中隨機選取80%的記錄作為訓練數據,余下的記錄作為測試數據來驗證算法效果。實驗選取歸一化折損累計增益(Normalized Discounted Cumulative Gain,NDCG)[17]來作為評估指標,這要求過濾掉數據集中記錄過少的用戶,以確保這一指標的有效性。本文過濾掉評分個數低于5個的電影的評分,并且選取評分個數超過20個的用戶,每個用戶的80%記錄作為訓練數據,余下的20%記錄作為測試驗證數據。對數據集進行5次同樣比例的隨機劃分,并取5次實驗結果的均值用來評估。

3.2 度量標準

通常的推薦算法采用均方根誤差(Root Mean Square Error,RMSE)來評估算法的性能,這個指標衡量算法在訓練集上生成的預測評分與驗證集中真實評分的差距。然而在現實的推薦系統中,通常只為目標用戶推薦預測評分較高的項目,而預測評分低的項目通常不會被推薦給用戶,因此,RMSE在推薦任務上并不是一個最優的度量標準。

本文選取文獻[17]中提出的NDCG作為實驗的度量標準,它是一個建立在折損累計增益上的指標。具體來說,對于任意一個用戶,算法為該用戶返回的前K個推薦結果在驗證集中的實際評分為{r1,r2,…,rK},則對應的折損累計增益為:

(10)

根據該用戶在驗證集中的實際評分,選取其中最大的K個評分并按照降序排列,即為理想的項目評分{R1,R2,…,RK},由此可計算此用戶的理想折損累計增益為:

(11)

最終,可以得到該用戶的歸一化折損累計增益為:

(12)

在接下來的實驗中,計算在不同算法上所有用戶的NDCG值,并取均值進行比較。

3.3 實驗結果及分析

實驗的結果如圖1、圖2所示,其中,圖1顯示在進行top-K推薦時,K=5場景下各算法的NDCG值,圖2顯示在進行top-K推薦時,K=10場景下各算法的NDCG值。

圖1 top-5推薦時各算法的折損累計增益比較

圖2 top-10推薦時各算法的折損累計增益比較

從圖1、圖2可以看出:

1)UTSH算法的NDCG值高于其他算法,其曲線增長平緩,在小于128位時就有較高的NDCG值,反映了該算法受編碼的位數影響較小,且用較少位數的編碼就能取得較好的性能,表明UTSH算法的推薦性能較好而且存儲代價小。

2)BinMF算法的性能隨著位數增加呈現明顯的下降趨勢,一方面是因為訓練集的稀疏性導致算法在量化階段損失大量信息,另一方面是NDCG著重衡量top-K推薦的質量,而BinMF算法著重于對整體未知評分的預測,由此可知其在高稀疏性的數據集上進行top-K推薦任務中的表現不如本文算法。

3)對3種哈希算法,在NDCG@5情況下,ITSH算法比ITQ算法提高7.53%,UTSH算法比ITQ算法提高12.69%,實際上,ITSH算法與ITQ算法在項目視角的哈希學習過程是基本一致的,性能上的差異體現在用戶視角上采用的監督式哈希方法,由于數據的稀疏性,直接在評分數據集上應用ITQ編碼會損失大量的信息,為了保留更多的評分中的信息,ITSH算法在第二階段用評分約束用戶與項目的海明距離,通過監督式的哈希算法獲得了高效的用戶編碼,同理,UTSH在項目視角采用監督式的哈希算法,也取得了更好的性能。

4)UTSH算法比ITSH算法的NDCG高出了5.58%(在NDCG@5情況下),這說明數據的稀疏性對ITQ算法的性能的影響較大,也進一步體現了兩階段哈希算法的優勢,TSH算法不僅充分的利用評分數據的信息,而且針對評分數據各視角的稀疏性特點進行針對性的處理,進一步提高了推薦的質量。

4 結束語

本文提出先對用戶或項目視角進行哈希,然后用評分來約束哈希后的距離,再對另一視角進行哈希編碼的方法。該方法第一階段從數據的其中一個視角挖掘其潛在特征,有利于捕捉數據的全局結構信息;第二階段對另一視角進行逐位編碼,又有效地利用了數據在該視角內的局部結構信息。兩階段聯合哈希的協同過濾算法將傳統的相似度計算問題轉化為高效的二值碼檢索問題,大幅減少了計算和存儲開銷,能夠有效降低稀疏性對推薦性能的影響,同時也為利用除評分外的信息來編碼提供可能,有利于進一步提高推薦系統的性能。然而,本文所做的工作仍然是完全依賴于評分數據的,沒有將評分以外的信息加入到編碼過程中,對推薦性能的提升有限。因此,利用好評分以外的信息來生成二值碼以解決稀疏性問題,將是下一步的工作。