一種兩階段聯(lián)合哈希的協(xié)同過(guò)濾算法

張輝宜,侯耀祖,陶 陶

(安徽工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,安徽 馬鞍山 243032)

0 概述

個(gè)性化推薦技術(shù)由于能為用戶(hù)推薦感興趣的內(nèi)容,提高用戶(hù)的使用體驗(yàn),進(jìn)而增強(qiáng)用戶(hù)粘性以及用戶(hù)的忠誠(chéng)度,已經(jīng)得到很多大型互聯(lián)網(wǎng)公司(如Amazon、Alibaba、Tencent等)的廣泛關(guān)注和深入研究。

協(xié)同過(guò)濾是推薦系統(tǒng)中流行的技術(shù)之一,其主要思想是相似的用戶(hù)會(huì)偏好相似的項(xiàng)目,它主要利用用戶(hù)過(guò)往的行為如評(píng)分、點(diǎn)擊等信息,無(wú)需關(guān)注項(xiàng)目的內(nèi)容。協(xié)同過(guò)濾還具有新異推薦、對(duì)用戶(hù)友好等特點(diǎn),因而受到研究者的青睞,得到廣泛研究。常見(jiàn)的協(xié)同過(guò)濾算法主要分為2類(lèi):一類(lèi)是基于模型的方法,利用數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等技術(shù)在數(shù)據(jù)集上訓(xùn)練出模型,然后基于模型為目標(biāo)用戶(hù)對(duì)未評(píng)分項(xiàng)目的偏好度進(jìn)行預(yù)測(cè),從而完成推薦;另一類(lèi)是基于內(nèi)存的方法,通過(guò)計(jì)算用戶(hù)之間或項(xiàng)目之間的相似度,利用相似度來(lái)獲取用戶(hù)或項(xiàng)目的近鄰,對(duì)近鄰評(píng)分加權(quán)來(lái)預(yù)測(cè)用戶(hù)對(duì)未評(píng)分項(xiàng)目的評(píng)分,進(jìn)而實(shí)現(xiàn)對(duì)用戶(hù)推薦,文獻(xiàn)[1]對(duì)這2類(lèi)方法進(jìn)行了詳細(xì)的介紹與總結(jié)。近年來(lái),矩陣分解技術(shù)因?yàn)槠湓跀U(kuò)展性及預(yù)測(cè)準(zhǔn)確度方面的優(yōu)勢(shì)得到廣泛關(guān)注[2-3]。矩陣分解技術(shù)通過(guò)分解用戶(hù)評(píng)分矩陣,得到低維的用戶(hù)和項(xiàng)目的特征向量,利用用戶(hù)和項(xiàng)目特征向量的點(diǎn)積來(lái)衡量用戶(hù)對(duì)項(xiàng)目的偏好程度,使用戶(hù)和項(xiàng)目向量的維度得到降低,且其利用特征向量的點(diǎn)積來(lái)取代傳統(tǒng)的相似度計(jì)算,因此推薦效率得到較大提高。

然而,隨著系統(tǒng)中數(shù)據(jù)量的極速增長(zhǎng),用戶(hù)對(duì)項(xiàng)目的評(píng)分?jǐn)?shù)據(jù)呈現(xiàn)海量高維的特點(diǎn),這對(duì)傳統(tǒng)的協(xié)同過(guò)濾算法提出了嚴(yán)峻的挑戰(zhàn)。一方面,由于數(shù)據(jù)的體量增大、維度增加,評(píng)分?jǐn)?shù)據(jù)表現(xiàn)出高稀疏性,這導(dǎo)致傳統(tǒng)的相似度方法在計(jì)算用戶(hù)或項(xiàng)目的相似度時(shí)不夠準(zhǔn)確,近鄰檢索準(zhǔn)確度低,預(yù)測(cè)精度低;另一方面,體量和維度的增加也帶來(lái)了計(jì)算和存儲(chǔ)開(kāi)銷(xiāo)的極速增長(zhǎng),導(dǎo)致推薦系統(tǒng)的效率下降。

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

1 哈希學(xué)習(xí)相關(guān)研究

協(xié)同過(guò)濾系統(tǒng)為目標(biāo)用戶(hù)在項(xiàng)目集上檢索偏好的項(xiàng)目,這個(gè)過(guò)程可以看做是一個(gè)相似性檢索問(wèn)題:檢索用戶(hù)感興趣的項(xiàng)目[6]。盡管傳統(tǒng)的相似性度量,如Jaccard相似系數(shù)、余弦相似系數(shù)和歐式距離等,已經(jīng)廣泛使用在推薦系統(tǒng)中,但是其在高維海量的數(shù)據(jù)上計(jì)算量過(guò)大且對(duì)于高稀疏度數(shù)據(jù)的相似度計(jì)算精度低。研究表明,哈希學(xué)習(xí)[7]在相似性檢索方面有獨(dú)特的優(yōu)勢(shì),它通過(guò)機(jī)器學(xué)習(xí)機(jī)制將數(shù)據(jù)映射成二進(jìn)制串的形式,能夠顯著減少數(shù)據(jù)的存儲(chǔ)和通信開(kāi)銷(xiāo),從而有效提高學(xué)習(xí)系統(tǒng)的效率[8]。哈希學(xué)習(xí)學(xué)到的二值碼能保持原空間中的近鄰關(guān)系,其在快速相似性檢索領(lǐng)域的應(yīng)用具有強(qiáng)大的生命力,已經(jīng)被廣泛應(yīng)用到信息檢索[9]、計(jì)算機(jī)視覺(jué)[10-11]和推薦系統(tǒng)[12-14]等領(lǐng)域。

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

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

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

(1)

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

ITQ算法具有計(jì)算復(fù)雜度低、檢索性能高的優(yōu)點(diǎn),在解決傳統(tǒng)的協(xié)同過(guò)濾算法應(yīng)對(duì)海量高維數(shù)據(jù)時(shí)性能不足的問(wèn)題上有獨(dú)特的優(yōu)勢(shì),但它也有一個(gè)明顯的缺點(diǎn),即為提升檢索性能所做平衡方差的工作會(huì)造成信息量的丟失,這在推薦系統(tǒng)稀疏評(píng)分?jǐn)?shù)據(jù)上尤其明顯,因此直接從用戶(hù)和項(xiàng)目視角上應(yīng)用ITQ算法會(huì)損失大量信息,影響推薦性能。

針對(duì)上述問(wèn)題,本文提出一種兩階段聯(lián)合哈希的協(xié)同過(guò)濾算法,既可以利用ITQ算法的優(yōu)點(diǎn),又結(jié)合系統(tǒng)中數(shù)據(jù)的性質(zhì)改善ITQ算法的缺點(diǎn),使得ITQ算法能更好地應(yīng)用在推薦系統(tǒng)中。

2 本文算法

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

2.1 基于用戶(hù)視角的兩階段聯(lián)合哈希算法UTSH

基于用戶(hù)視角的兩階段聯(lián)合哈希算法的主要階段如下:

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

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

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

(2)

其中,R為正交的旋轉(zhuǎn)矩陣,量化后的用戶(hù)空間為U,隨機(jī)初始化R后,交替執(zhí)行如下2個(gè)過(guò)程直至得到局部最優(yōu)解,從而得到最優(yōu)的U:保持R不變,按照U=sgn(FR)來(lái)更新U;保持U不變,對(duì)UFT進(jìn)行奇異值分解(Singular Value Decomposition,SVD)為PΩQT,其中,P為c×c階酉矩陣,Q為m×m階酉矩陣,按照R=PQT來(lái)更新R。

2)通過(guò)系統(tǒng)中的評(píng)分來(lái)約束用戶(hù)與項(xiàng)目的海明距離,即以用戶(hù)與項(xiàng)目在低維空間中的相似度來(lái)預(yù)測(cè)用戶(hù)對(duì)項(xiàng)目的偏好程度。參照文獻(xiàn)[6]中用戶(hù)ui與項(xiàng)目vj的相似度定義,如式(3)所示。

(3)

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

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

(4)

在約束條件下,直接由式(4)求解最優(yōu)的V是一個(gè)NP-難問(wèn)題[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)

通過(guò)調(diào)整足夠大的參數(shù)α,使得X逼近V即d(V,V’)=0,進(jìn)而將難以求解的V的離散約束轉(zhuǎn)移到連續(xù)的容易求解的X上,由約束條件的性質(zhì),式(5)可化簡(jiǎn)為:

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

(6)

將求解V、X的問(wèn)題分解為求解V和X的2個(gè)子問(wèn)題,交替優(yōu)化這2個(gè)子問(wèn)題直至收斂即可求得V的最優(yōu)解。

在求解V的子問(wèn)題中,保持X不變,對(duì)于vj∈V有:

(7)

其中,Rj為S中已知的用戶(hù)對(duì)項(xiàng)目vj的評(píng)分集合。由于vj的值是離散的,故采用逐位更新的策略更新vj,更新規(guī)則同文獻(xiàn)[14]如下所示:

(8)

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

argmaxXtr(VTX)

s.t.XTX=nI,X1=0

(9)

UTSH算法描述如下:

輸入評(píng)分矩陣Sm×n,二值碼位數(shù)c,權(quán)衡系數(shù)α

輸出用戶(hù)的二值碼Uc×m,項(xiàng)目的二值碼Vc×n

1)F←PCA(S)

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

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

(1)U←sgn(FR)

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

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

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

(1) for j=1 to n :

重復(fù)以下過(guò)程直至收斂

for k=1 to c :

(2)構(gòu)造中心矩陣C

6)返回U、V

2.2 基于項(xiàng)目視角的兩階段聯(lián)合哈希算法ITSH

基于項(xiàng)目視角的兩階段哈希算法先從項(xiàng)目視角哈希,再通過(guò)評(píng)分約束用戶(hù)與項(xiàng)目的海明距離,進(jìn)一步得到用戶(hù)二值碼的算法,由于其過(guò)程與上述基于用戶(hù)視角的兩階段哈希算法對(duì)稱(chēng),在此不再贅述。

3 仿真實(shí)驗(yàn)

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

3.1 數(shù)據(jù)集

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

3.2 度量標(biāo)準(zhǔn)

通常的推薦算法采用均方根誤差(Root Mean Square Error,RMSE)來(lái)評(píng)估算法的性能,這個(gè)指標(biāo)衡量算法在訓(xùn)練集上生成的預(yù)測(cè)評(píng)分與驗(yàn)證集中真實(shí)評(píng)分的差距。然而在現(xiàn)實(shí)的推薦系統(tǒng)中,通常只為目標(biāo)用戶(hù)推薦預(yù)測(cè)評(píng)分較高的項(xiàng)目,而預(yù)測(cè)評(píng)分低的項(xiàng)目通常不會(huì)被推薦給用戶(hù),因此,RMSE在推薦任務(wù)上并不是一個(gè)最優(yōu)的度量標(biāo)準(zhǔn)。

本文選取文獻(xiàn)[17]中提出的NDCG作為實(shí)驗(yàn)的度量標(biāo)準(zhǔn),它是一個(gè)建立在折損累計(jì)增益上的指標(biāo)。具體來(lái)說(shuō),對(duì)于任意一個(gè)用戶(hù),算法為該用戶(hù)返回的前K個(gè)推薦結(jié)果在驗(yàn)證集中的實(shí)際評(píng)分為{r1,r2,…,rK},則對(duì)應(yīng)的折損累計(jì)增益為:

(10)

根據(jù)該用戶(hù)在驗(yàn)證集中的實(shí)際評(píng)分,選取其中最大的K個(gè)評(píng)分并按照降序排列,即為理想的項(xiàng)目評(píng)分{R1,R2,…,RK},由此可計(jì)算此用戶(hù)的理想折損累計(jì)增益為:

(11)

最終,可以得到該用戶(hù)的歸一化折損累計(jì)增益為:

(12)

在接下來(lái)的實(shí)驗(yàn)中,計(jì)算在不同算法上所有用戶(hù)的NDCG值,并取均值進(jìn)行比較。

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

實(shí)驗(yàn)的結(jié)果如圖1、圖2所示,其中,圖1顯示在進(jìn)行top-K推薦時(shí),K=5場(chǎng)景下各算法的NDCG值,圖2顯示在進(jìn)行top-K推薦時(shí),K=10場(chǎng)景下各算法的NDCG值。

圖1 top-5推薦時(shí)各算法的折損累計(jì)增益比較

圖2 top-10推薦時(shí)各算法的折損累計(jì)增益比較

從圖1、圖2可以看出:

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

2)BinMF算法的性能隨著位數(shù)增加呈現(xiàn)明顯的下降趨勢(shì),一方面是因?yàn)橛?xùn)練集的稀疏性導(dǎo)致算法在量化階段損失大量信息,另一方面是NDCG著重衡量top-K推薦的質(zhì)量,而B(niǎo)inMF算法著重于對(duì)整體未知評(píng)分的預(yù)測(cè),由此可知其在高稀疏性的數(shù)據(jù)集上進(jìn)行top-K推薦任務(wù)中的表現(xiàn)不如本文算法。

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

4)UTSH算法比ITSH算法的NDCG高出了5.58%(在NDCG@5情況下),這說(shuō)明數(shù)據(jù)的稀疏性對(duì)ITQ算法的性能的影響較大,也進(jìn)一步體現(xiàn)了兩階段哈希算法的優(yōu)勢(shì),TSH算法不僅充分的利用評(píng)分?jǐn)?shù)據(jù)的信息,而且針對(duì)評(píng)分?jǐn)?shù)據(jù)各視角的稀疏性特點(diǎn)進(jìn)行針對(duì)性的處理,進(jìn)一步提高了推薦的質(zhì)量。

4 結(jié)束語(yǔ)

本文提出先對(duì)用戶(hù)或項(xiàng)目視角進(jìn)行哈希,然后用評(píng)分來(lái)約束哈希后的距離,再對(duì)另一視角進(jìn)行哈希編碼的方法。該方法第一階段從數(shù)據(jù)的其中一個(gè)視角挖掘其潛在特征,有利于捕捉數(shù)據(jù)的全局結(jié)構(gòu)信息;第二階段對(duì)另一視角進(jìn)行逐位編碼,又有效地利用了數(shù)據(jù)在該視角內(nèi)的局部結(jié)構(gòu)信息。兩階段聯(lián)合哈希的協(xié)同過(guò)濾算法將傳統(tǒng)的相似度計(jì)算問(wèn)題轉(zhuǎn)化為高效的二值碼檢索問(wèn)題,大幅減少了計(jì)算和存儲(chǔ)開(kāi)銷(xiāo),能夠有效降低稀疏性對(duì)推薦性能的影響,同時(shí)也為利用除評(píng)分外的信息來(lái)編碼提供可能,有利于進(jìn)一步提高推薦系統(tǒng)的性能。然而,本文所做的工作仍然是完全依賴(lài)于評(píng)分?jǐn)?shù)據(jù)的,沒(méi)有將評(píng)分以外的信息加入到編碼過(guò)程中,對(duì)推薦性能的提升有限。因此,利用好評(píng)分以外的信息來(lái)生成二值碼以解決稀疏性問(wèn)題,將是下一步的工作。