應(yīng)文杰，?；w

北京交通大學(xué) 計算機與信息技術(shù)學(xué)院，北京100044

1 引言

個性化推薦技術(shù)由于能為用戶推薦感興趣的內(nèi)容，提高用戶體驗，進而增強用戶粘性以及用戶的忠誠度，已經(jīng)得到許多大型互聯(lián)網(wǎng)公司（如Amazon、Alibaba、Baidu等）的廣泛關(guān)注和深入研究[1-2]。然而，隨著互聯(lián)網(wǎng)的快速發(fā)展，各行各業(yè)的數(shù)據(jù)都呈現(xiàn)爆炸式的增長。例如，截止到2018 年10 月，Taobao 平臺上已經(jīng)有超過5 億的用戶和10 億的商品。因此，推薦系統(tǒng)也面臨著數(shù)據(jù)存儲和檢索效率等挑戰(zhàn)[3-5]。

哈希學(xué)習(xí)通過保持原始空間中的近鄰關(guān)系將原始數(shù)據(jù)映射成二進制碼的形式。有效地減少數(shù)據(jù)存儲開銷，加快相似性檢索效率而廣泛地應(yīng)用于信息檢索、計算機視覺、推薦系統(tǒng)等領(lǐng)域[6-10]。最近，一些基于哈希學(xué)習(xí)的推薦方法被應(yīng)用于提高推薦系統(tǒng)的效率[11-15]。這些方法的核心是將用戶評分矩陣看作用戶與項目之間的相似性矩陣，通過分解相似性矩陣來得到用戶和項目的低維二進制表示。然后在二進制空間計算用戶和項目之間的漢明距離，距離越小表示相似性越大，用戶對項目越感興趣。由于這種二進制表示，實值向量空間的內(nèi)積操作被二進制空間中的位運算所取代。因此，即使采用線性掃描，時間復(fù)雜度也能得到顯著降低[3，13]。

然而，現(xiàn)存的基于哈希學(xué)習(xí)的推薦方法普遍存在一個問題，它們忽略了用戶評分與相似性不等價問題。一般而言，用戶評分系統(tǒng)都默認(rèn)為等級評分（如豆瓣電影評分為1到5的等級），而哈希碼在二進制空間的相似性區(qū)間一般為正負(fù)對稱的離散區(qū)間。因此，現(xiàn)存的哈希推薦方法一般采用規(guī)范化的方式直接將評分映射相似性區(qū)間。這種方式是非常粗暴的，它忽略了隱藏在評分信息下用戶和項目的自身特點。比如有些用戶喜歡給高分，而有些用戶喜歡給低分，有些項目更受歡迎，而有些項目不受歡迎[16]。

本文提出了一種改進的哈希推薦方法。它通過移除用戶和項目自身的偏置將用戶評分映射到正負(fù)對稱的相似性區(qū)間。如圖1 所示，首先，計算所有用戶和項目相對于評分系統(tǒng)均值的偏置，在移除偏置之后，將用戶評分映射到相似性區(qū)間。然后，分解相似性矩陣得到用戶和項目的二進制碼，在二進制空間計算用戶與項目之間的相似性。最后，預(yù)測用戶評分時加上對應(yīng)的偏置將相似性映射到評分區(qū)間。通過這種方式，很好地緩解了用戶評分與相似性不等價問題。同時，在分解相似性矩陣時，以保持相似性為目標(biāo)，提出了兩種結(jié)構(gòu)損失來構(gòu)建目標(biāo)函數(shù)。實驗部分，分析了三個數(shù)據(jù)集的評分分布，解釋了偏置項處理的合理性，在三個真實的數(shù)據(jù)集上進行實驗，對比了幾個代表性方法，本文方法能實現(xiàn)更高的檢索精度。

總結(jié)了本文的貢獻如下：

（1）通過移除用戶和項目的偏置，將用戶評分映射到相似性區(qū)間，很好地解決了用戶評分與相似性不等價的問題。

（2）以最小化相似性損失為目標(biāo)，提出了兩種方式來構(gòu)建目標(biāo)函數(shù)，并在實驗中對兩種方式進行了對比分析。

（3）在三個真實的數(shù)據(jù)集上的實驗結(jié)果表明，與幾個代表性方法對比，本文方法能實現(xiàn)更高的檢索精度。

2 相關(guān)工作

目前，基于矩陣分解的推薦方法依然是最受歡迎的方法之一，大多數(shù)基于哈希的推薦方法都建立在矩陣分解基礎(chǔ)上[2-3，13]。在這部分，回顧了傳統(tǒng)的矩陣分解推薦方法和離散矩陣分解推薦方法。

2.1 實值矩陣分解

推薦系統(tǒng)方法包括基于內(nèi)容推薦，協(xié)同過濾推薦以及兩者結(jié)合的方法[17-21]。目前，協(xié)同過濾技術(shù)已經(jīng)成為了主流的方法，尤其是矩陣分解的協(xié)同過濾推薦[22-25]。矩陣分解方法通過分解用戶評分矩陣得到用戶與項目的隱語義表示，然后在向量空間計算用戶對項目的評分[16，25]。FuckSVD[26]分解用戶評分矩陣，在低維的向量空間來表示用戶和項目，通過向量內(nèi)積來計算用戶對項目的偏好。然而，完全基于向量表示來計算用戶對項目的評分是不明智，因為有的用戶喜歡給高評分，有的用戶喜歡給低評分[16]。因此，Paterek等[27]提出了一種帶偏置的矩陣分解方法BiasSVD。考慮了用戶自身的評分特點以及項目受歡迎的程度。為了解決冷啟動問題，Paterek 等[28]提出了一種結(jié)合內(nèi)容感知和隱反饋信息的矩陣分解方法SVD++。郭寧寧等[29]人提出一種融合社交網(wǎng)絡(luò)特征的協(xié)同過濾推薦算法，引入評分以外的信息來提高推薦的性能。雖然，矩陣分解的方法在推薦系統(tǒng)中已經(jīng)取得了很好的表現(xiàn)。然而，面對日益增長數(shù)據(jù)，推薦系統(tǒng)的效率也面臨著巨大的挑戰(zhàn)[3，13]。

2.2 離散矩陣分解

哈希技術(shù)通過將原始數(shù)據(jù)映射為低維的二進制碼表示，從而減少數(shù)據(jù)存儲，加速相似性查詢效率得到了廣泛的關(guān)注和深入的研究[30-34]。

早期的基于哈希的矩陣分解推薦通常是一個“兩階段”的學(xué)習(xí)過程[13]。Zhou 等人[3]提出的離散協(xié)同過濾方法將二進制碼的學(xué)習(xí)過程分為兩個獨立的階段：實值優(yōu)化和二進制量化。在實值優(yōu)化階段，通過丟棄離散約束分解矩陣得到連續(xù)解。在量化階段，通過最小化實值的量化損失來獲得二進制碼。Zhang等[11]提出了一種基于余弦相似性度量的方式來分解用戶評分矩陣進而得到用戶和項目的二進制碼。Liu等[12]提出了一種基于內(nèi)容感知的矩陣分解方法，通過加入內(nèi)容信息，很好地克服了冷啟動問題。

圖1 改進的哈希推薦方法設(shè)計流程

Zhang等[13]人指出兩階段方法由于放松二進制約束而引起的誤差會導(dǎo)致性能差的問題，因此提出了一種離散協(xié)同過濾方法。為了解決帶約束的離散化優(yōu)化問題，它將原始問題轉(zhuǎn)化為兩個子問題。在離散化優(yōu)化階段，提出了一種離散梯度下降算法，同時采用SVD 分解方法來保持位平衡和位不相關(guān)約束來保證哈希碼的有效性。Lian 等[14]在離散協(xié)同過濾基礎(chǔ)了提出了一個結(jié)合內(nèi)容感知的離散協(xié)調(diào)過濾方法。Zhang等[15]提出了一個基于深度學(xué)習(xí)的方法，采用深度信念網(wǎng)絡(luò)來學(xué)習(xí)用戶和項目的二進制表示。由于二進制碼表示，實值向量空間的內(nèi)積操作被二進制空間中的位運算所取代。因此，線性掃描的時間復(fù)雜度也能得到了明顯降低[3，11]。

3 本文方法

假定系統(tǒng)中的用戶數(shù)量為n，項目數(shù)量為m，用戶對項目的評分構(gòu)成稀疏的評分矩陣R ∈Rn×m，其中Rij表示用戶ui對項目vj的評分。哈希后的用戶空間為B:{b1,b2,… ,bn}∈{-1,1}r，×n哈 希 后 的 項 目 空 間 為D:{d1d,2, …,dm}∈{-1,1}r×，m其中r 是哈希碼的長度。tr(?)表 示 矩 陣 的 跡，||?||F表 示 矩 陣 的Frobenius 范 數(shù)，sgn(?)為符號函數(shù)，輸入大于等于0 時輸出1，反之輸出-1。1表示全為1的列向量。

3.1 模型

基于用戶評分矩陣Rij，離散矩陣分解推薦方法通過分解用戶評分矩陣得到用戶和項目的二進制碼。如果用戶ui對項目vj評分越高，那么用戶bi與項目dj的漢明距離越小，相似性越大。其中，bi與dj的相似性定義如下[3]：

其中，I(?)為指示函數(shù)，如果條件成立則返回1，否則返回0。由式（1）定義可知，當(dāng)用戶與項目的向量內(nèi)積越大，相似度越大，反之越小。另外，為了最大化哈希碼的信息熵和方差，定義位平衡B1=0,D1=0和位不相關(guān)約束BBT=nIr×r,DDT=mIr×r來保證每一位哈希碼的有效性。因此，現(xiàn)存的離散矩陣分解方法通常建立如下目標(biāo)函數(shù)：

在大多數(shù)評分系統(tǒng)中，Rij為1～5 的等級評分，而∈{-r,-r+2,… ,r-2,r}。因此，現(xiàn)存的方法大多都對原始用戶評分Rij∈[min s,max s]進行規(guī)范化處理Rij=2r(Rij-r)/(max s-min s)-r[13-15]。然而，這種方式忽略了隱藏在評分信息下面的用戶和項目的自身特點。比如，有些用戶喜歡給高分，有些用戶喜歡給低分，有些項目更受歡迎，而有些項目不受歡迎[16]。直接映射處理無法挖掘潛藏在評分信息下的用戶和項目的特點。因此，提出了基于偏置的方式將用戶評分矩陣映射到正負(fù)對稱的相似性區(qū)間。

在式（3）中，根據(jù)每個用戶，項目以及評分系統(tǒng)的特點，將評分矩陣映射到了正負(fù)對稱的相似性區(qū)間。很好地緩解了評分與相似性不等價問題，同時挖掘了用戶與項目自身的特性。而然，的內(nèi)積值與哈希碼的長度有關(guān)，因此，只需要將相似性Sij歸一化到[-r,r]。最終，目標(biāo)函數(shù)如下：

其中，Sij∈[-r,r]為用戶ui與項目vj的相似性。

問題4 本質(zhì)上是一個帶約束的離散化優(yōu)化問題，直接優(yōu)化是一個NP 難問題[35-36]。因此分別定義了兩個 約 束 空 間 Φ={X ∈Rr×n|X1=0,XXT=nIr×r} 和Ω={Y ∈Rr×n|Y1=0,YYT=mIr×r}。通過放松哈希碼的位平衡和位不相關(guān)約束得到一般化的目標(biāo)函數(shù)：

其中，dist( )B,D,X,Y 表示{B,D}與{X,Y}之間的距離。本文提出了兩種度量方式如下：

值損失度量：分別衡量兩個矩陣中所有元素對應(yīng)之間的誤差：

相似性損失度量：衡量兩個矩陣乘積之后相似性矩陣中所有元素對應(yīng)之間誤差：

由tr(BBT)=tr(XXT)=nr、tr(DDT)=tr(YYT)=mr，可得，式（6）對應(yīng)的值損失目標(biāo)函數(shù)：

類似的，式（7）對應(yīng)的相似性損失目標(biāo)函數(shù)：

其中，式（8）和式（9）中的ρ ≥0,ρ1≥0,ρ2≥0 是調(diào)節(jié)參數(shù)。值得注意的是，可以通過設(shè)置一個很大的調(diào)節(jié)參數(shù)來強制dist(B,D,X,Y)→0。

3.2 學(xué)習(xí)

針對不同損失度量得到的目標(biāo)函數(shù)式（8）和式（9），學(xué)習(xí)算法的過程類似，這里詳細介紹了相似性損失目標(biāo)函數(shù)的學(xué)習(xí)過程。對于式（9），采用交替求解如下四個子問題：

B-問題：在這個問題中，固定D,X,Y，B-問題轉(zhuǎn)化為最小化目標(biāo)函數(shù)：

其中，κi表示用戶ui的所有評分項目集合。

哈希碼的求解過程是一個離散優(yōu)化問題，早期的方法放松哈希碼的離散約束來解決一個近似的優(yōu)化問題，但這導(dǎo)致難以獲得高質(zhì)量的哈希碼[35]。因此，Liu 等人[35]提出一種離散優(yōu)化方法，同之前的工作一致[13，15]，采用離散坐標(biāo)下降優(yōu)化算法來更新每一位哈希碼。用bik表示bi的第k 位哈希碼，bikˉ表示除第k 位剩下的哈希碼，在固定bikˉ不變的時候，bik的更新規(guī)則如下：

D-問題：在這個問題中，固定B,X,Y，D-問題轉(zhuǎn)化為最小化目標(biāo)函數(shù)：

其中，κj表示項目vj的所有評分用戶集合。同B-問題類似，D的更新規(guī)則如下：

X-問題：在這個問題中，固定B,D,Y，關(guān)于X 的目標(biāo)函數(shù)如下：

為了保證X 的位平衡和位不相關(guān)約束，采用SVD分解求解式（14），記P=( BTDYT)T，X的更新規(guī)則如下：

其中，Ub和Vb分別是矩陣的左右奇異值是對應(yīng)0 奇異值的特征向量基于[Vb1]斯密特正交化獲得[13]。

Y-問題：在這個問題中，固定B,D,X，關(guān)于Y 的目標(biāo)函數(shù)如下：

4 算法分析

算法1 總結(jié)了整個優(yōu)化過程，下面分析算法的復(fù)雜度和收斂性。

算法1

輸入：評分矩陣{Rij|i,j ∈κ}，哈希碼長度r，調(diào)節(jié)參數(shù)ρ

輸出：用戶哈希碼B ∈{±1}r×n，項目哈希碼D ∈{±1}r×m，偏置項

p=max(Sij),q=min(Sij)

Sij=(Sij-p)/(p-q)*2r+r

初始化：隨機初始化X,Y，B=sgn(X),D=sgn(Y)循環(huán)

直到收斂

4.1 復(fù)雜度

分析了算法的時間和空間復(fù)雜度。對于空間復(fù)雜度，算 法1 需 要O(|κ|)來 存 儲 稀 疏 的 評 分 矩 陣，需 要O(r.max(m,n))來存儲用戶和項目的哈希碼，其中r 是哈希碼的長度。另外，需要少量的空間O(m+n)來存儲用戶和項目的偏置信息。因此，整個算法的空間復(fù)雜度是線性的。

算法1 的時間復(fù)雜度包括預(yù)處理和四個子問題。預(yù)處理過程需O(κ)來完成評分到相似性的映射。對于B-問題，需要O(r2|κi|Ts)來計算用戶的哈希碼，其中Ts是更新一位哈希碼的時間。類似的D-問題需要O(r2|κj|Ts)來計算項目的哈希碼。對于X-問題需要O(r2(m+n))來進行SVD 分解和斯密特正交化，類似的Y-問題也需要O(r2(m+n))。假設(shè)算法需要迭代T 步收斂，那么整個算法的時間復(fù)雜度為O(Tr2((|κi|+|κj|)Ts+m+n))。因此，算法的樣本時間復(fù)雜度趨于線性。

現(xiàn)有的方法的核心過程大多是分解相似性矩陣，本文的方法相比于DCF多了一個預(yù)處理過程-評分到相似性的映射，該過程的復(fù)雜度與用戶評分?jǐn)?shù)量是線性關(guān)系。由于BCCF、PPH 直接放松了哈希碼的離散約束來解決一個近似的優(yōu)化問題，因此它們不涉及X-問題和Y-問題。相比而言，BCCF、PPH 多了一個連續(xù)值到哈希碼的量化過程?？偟膩碚f，算法1 的時間復(fù)雜度同三個代表性方法相當(dāng)。

4.2 收斂曲線

如圖2 所示，給出了算法在Movielens-10M 數(shù)據(jù)集上目標(biāo)函數(shù)與哈希碼長度比值的收斂曲線。從圖2 中可以看出算法在20 次迭代左右收斂，且收斂效果與哈希碼的長度正相關(guān)。算法的收斂速度非?？欤绕涫乔懊鎺状蔚?。算法收斂性的理論分析與EM 算法的收斂性證明類似，詳細的收斂性分析參見文獻[13]。

圖2 目標(biāo)函數(shù)收斂曲線

5 實驗

實驗中，在三個標(biāo)準(zhǔn)數(shù)據(jù)集上，對比了三個有代表性的哈希推薦方法BCCF、PPH、DCF。其中BCCF 和PPH 為兩階段哈希方法，PPH 采用余弦相似性度量，DCF 直接離散優(yōu)化獲得哈希碼。所有的實驗運行在16 Intel Xeon CPU和64 GB RAM平臺。

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

使用如下三個標(biāo)準(zhǔn)數(shù)據(jù)集：

MovieLens-10M：這個數(shù)據(jù)集包括71 567 個用戶，10 681 部電影和107個評分信息。所有的評分在0.5～5之間，以0.5為間隔。

Douban：這個數(shù)據(jù)集包括129 490個用戶，58 541部電影和16 830 839 個評分信息。所有得評分在1～5 之間，以1為間隔。

Epinions：這個數(shù)據(jù)集來自于40 163個用戶對139 738部電影的664 824 個評分。所有的評分在1～5 之間，以1為間隔。

為了驗證本文的方法適合不同評分密度的數(shù)據(jù)，選擇了三個不同評分密度的數(shù)據(jù)集。同之前的工作一樣[14-15]，過濾了評分信息不足50 個的用戶，使得每個用戶都有可觀察的評分信息用于訓(xùn)練和測試。對于每個用戶，選擇80%的評分信息作為訓(xùn)練數(shù)據(jù)，剩下的20%作為測試數(shù)據(jù)?？偨Y(jié)了過濾處理后的數(shù)據(jù)集如表1。實驗中，對數(shù)據(jù)集進行了5 次同樣比例的隨機劃分，并取5次實驗結(jié)果的均值來評估所有的方法。

表1 過濾后的數(shù)據(jù)集

5.2 評分分布

為了分析移除偏置的合理性，對三個數(shù)據(jù)集的評分分布進行了統(tǒng)計分析。如圖3 所示，發(fā)現(xiàn)三個數(shù)據(jù)集的用戶評分以3 到4 分所占的比例最多，兩端的比例相對較少評分分布大致服從正態(tài)分布。這表示，大多數(shù)用戶的評分具有一定的習(xí)慣，即存在一個評分平衡點，同時所有的評分是在這個平衡點上下浮動。因此，一個基本的假設(shè)就是將用戶均值以及項目均值相互作用看作是平衡點，偏離平衡點偏差則通過哈希碼之間的相似性來擬合。

圖3 三個數(shù)據(jù)集的用戶評分?jǐn)?shù)據(jù)分布

5.3 評價指標(biāo)

采用了如下三個常用的評價指標(biāo)：

NDCG：折扣累計損失（DCG）是廣泛用于評價排序質(zhì)量的指標(biāo)。NDCG 則是對折扣累計損失歸一化的結(jié)果。NDCG 關(guān)注于算法獲得的哈希碼對保持用戶對項目的偏好排序的結(jié)果。NDCG計算如下：

其中，K 為排序靠前的K 個項目，ri是算法預(yù)測第i個偏好的項目的得分，而rj則是由用戶評分信息得到的第j個偏好的項目的得分。因為排序越靠前的項目得分權(quán)重越大，而且rj是實際用戶評分排序后的結(jié)果，所以NDCG的分母一定大于分子，即NDCG在0到1之間，越大說明保持用戶偏好排序的效果越好。

RMSE：平方根損失誤差是用來評價算法預(yù)測的評分與用戶的實際評分的偏差，不保持評分之間的排序關(guān)系。RMSE計算如下：

其中，κ 是所有可觀察的評分集合，yk為預(yù)測評分，y?k為真實評分。

Precision、Recall、F1：精度、召回率、F1 值是常用的分類指標(biāo)。在這里，用于評價算法在預(yù)測用戶對項目是否喜歡的二類問題上。它們的計算公式如下：

對于每一個用戶，設(shè)置預(yù)測評分5 分以上的項目構(gòu)成集合，實際評分為5分的項目構(gòu)成集合。

5.4 實驗結(jié)果

5.4.1 對比實驗

同以往的工作一樣[3，13-15]，使用NDCG 和F1指標(biāo)，對比了本文的方法同其他三個代表性的方法。

在表2 中，報告了不同方法在三個數(shù)據(jù)集上的NDCG@10 精度，可以看出本文的方法有一定的優(yōu)勢，尤其是較短哈希碼長度下，相對于DCF 方法大約有1%～3%的提升。而且，OUR-S 在短哈希碼下的表現(xiàn)更顯著。在表3 中，展示了不同方法的F1 值，可以看出本文方法在大多數(shù)情況下優(yōu)于其他方法，在8 bit 哈希碼下，本文的方法表現(xiàn)優(yōu)越，相對于DCF 方法大約有3%～5%的提升。另外，在圖4 中展示了不同方法在不同哈希碼長度下的NDCG@K 隨K 的變化曲線，圖5 中展示了召回率-精度變化曲線，從圖中可以看出，本文的方法保持一致的優(yōu)勢，尤其是在Douban數(shù)據(jù)集上。

5.4.2 相似性損失與值損失區(qū)別

對于兩種不同損失度量方式，大多數(shù)情況下相似性損失度量OUR-S 優(yōu)于值損失度量OUR-V。如圖6 所示，在NDCG@5 指標(biāo)下相似性損失度量依然優(yōu)于值損失度量，而且在短哈希碼下這種優(yōu)勢較為顯著。這表示相似性損失度量可以用較短的哈希碼就能獲得較優(yōu)的結(jié)果。為了探究其中的原因，分析了兩種度量的RMSE指標(biāo)。如圖7 所示，相似性損失度量相比于值損失度量，在預(yù)測評分上更準(zhǔn)確，這說明相似性損失度量能更好地擬合用戶評分，保持用戶與項目之間的相似性。

6 總結(jié)

本文發(fā)現(xiàn)現(xiàn)存的大多數(shù)哈希推薦方法在處理用戶評分信息與相似性關(guān)系上過于粗暴，沒有挖掘評分信息下潛在的用戶和項目的特點。因此，提出了用一個偏置項來保留這種特點，通過去偏置將用戶評分映射到相似性區(qū)間，很好地緩解了用戶評分與相似性不等價的問題。在構(gòu)建目標(biāo)函數(shù)時，提出了兩種度量方式來構(gòu)建目標(biāo)函數(shù)，并在實驗中分析了兩種方式的區(qū)別，相似性損失度量優(yōu)于值損失度量，尤其是在短哈希碼下。然而，本文沒有考慮推薦系統(tǒng)中的冷啟動問題[28，37]，沒有引入用戶評分以外的信息，探究評分以外的信息對算法性能的影響是一個值得思考的問題，也是下一步要研究的工作。

表2 不同方法在三個數(shù)據(jù)集上的NDCG@10值%

表3 不同方法在三個數(shù)據(jù)集上的F-measure值%

圖4 不同方法在不同哈希碼長度下的NDCG@K值(K=2,4,6,8,10)

圖5 不同方法在不同哈希碼長度下的召回率-精度曲線

圖6 兩種度量方式在不同哈希碼長度下的NDCG@5值

圖7 兩種度量方式在不同哈希碼長度下的RMSE值