基于集成局部性特征學習的推薦算法*

莊福振，羅 丹，何 清

1.中國科學院 計算技術研究所 智能信息處理重點實驗室，北京 100190

2.中國科學院大學，北京 100049

1 引言

隨著互聯網的發展，人們正處于一個信息爆炸的時代。相比過去的信息匱乏，現階段的海量信息數據，使得人們獲取有用信息越來越困難。一個良好用戶體驗的推薦系統，能夠對海量信息進行篩選、過濾，將用戶最關注最感興趣的信息展現在用戶面前[1-3]。而一個好的推薦算法，能夠從已有的信息中發現隱藏的特性，發現用戶的潛在興趣分布，發現商品的潛在主題分布，從而將關聯性最大的用戶和商品聯系起來。協同過濾推薦算法是最流行的推薦算法之一，它通過學習用戶商品的特征表示，依此尋找用戶和商品的“近鄰”成員，最后利用從“近鄰”處學到的知識來求得最應該推薦給用戶的商品[4-5]。作為推薦算法最重要的成分之一，特征表示學習在很大程度上影響推薦算法的效果。以往大部分的推薦算法都是采用基于矩陣分解的方法來獲得用戶以及商品的隱性特征表示，而近年來，深度學習已經在自然語言處理、語音識別以及圖像分類等領域被證明可以很好地進行表示學習，并且在深度學習應用到推薦系統方面，已經進行了相關研究[6-8]。本文提出了基于自動編碼機（AutoEncoder）學習用戶商品特征的推薦算法，并證明了其特征學習的有效性。同時進一步拓展該算法，考慮推薦系統中評分數據的局部特性，即評分數據可能由多個垂直的局部結構組成，不同的結構之間關聯度不大，由此來提高推薦算法的特征學習能力，提升推薦效果。Lee等人[5]提出了基于評分矩陣低秩特性的協同過濾算法，同樣考慮了矩陣的局部特性，本文將對比該算法，來驗證所提出的特征學習算法的有效性。

本文組織結構如下：第2章介紹了基于集成局部性特征學習的推薦算法；第3章對算法進行求解；第4章給出了詳細的實驗結果；第5章列出了本文的相關工作；第6章對全文進行總結。

2 基于集成局部性特征學習的推薦算法

2.1 基于局部性的特征學習框架

對評分矩陣直接學習用戶和商品的隱性特征表示顯得有點粗糙，用戶和商品往往形成一個個不同的群組，例如男性和女性關注的商品完全屬于不同的類型，男性主要關注電子設備如手機和電腦等，而女性更關注服裝和化妝品等。因此，在學習用戶興趣特征和商品主題屬性時，將其興趣和主題分成更細的分支，在不同的分支上獨立學習，能夠避免無關聯信息之間的干擾。對女性潛在興趣特征的學習和對男性潛在興趣特征的學習關聯性非常小，分開獨立學習能學到更具代表性的特征表示。推薦系統中的主題是多種多樣的，因此可以將其分成多個模塊來進行特征學習。

圖1展示了將整個評分矩陣分成多個子主題塊進行學習的框架。如圖所示，t個錨點被選出。對于每個錨點pt（1≤t≤q，q是子模型的個數），有一組與該錨點相關的用戶-商品對組成局部矩陣Mt。該相關性度量并不是依據矩陣上錨點位置與其他觀測點的位置距離，而是通過其潛在的相似性得到。簡單地說，原始評分矩陣Mt乘以一個與錨點的相似度矩陣Kt，即可得到第t個子模型的局部矩陣Mt。這里Kt的計算方式可表示為：

這里錨點用戶與其他用戶之間的距離（錨點商品與其他商品之間的距離）可以用高斯核函數或三角核函數K(x,y)=1-||x-y||d計算得到。

Fig.1 Local modeling learning framework圖1 局部模型學習框架

2.2 基于自動編碼機學習用戶商品局部特征

對于每個局部錨點矩陣Mt，本文使用Auto-Encoder來學習其中的用戶商品隱性特征。首先將錨點評分矩陣Mt擴展成且有Rt∈ ?(m+n)×(m+n)。同理，將錨點相似度矩陣Kt擴展成，其中使用AutoEncoder學習用戶和商品的局部特征信息時，對于每個AutoEncoder子模型，其輸入都是原始評分矩陣的擴展R，可表示如下：

其中，Wt∈?r×(m+n)，Wt′∈?(m+n)×r。矩陣R是對矩陣M的擴展，即記I∈?m×n，當Iu,i=1時，用戶u對商品i進行評分，否則Iu,i=0。將矩陣I擴展成每個子模型優化時的側重點不同，均乘以跟錨點相關的相似度矩陣，每個子模型的優化目標可表示為：

2.3 基于Ranking的算法

基于Ranking推薦算法中，在對未知商品進行評分的同時，會盡量使模型在已知用戶產品上的評分值大小順序和原始評分矩陣保持一致。這里為保持該一致性，采用基于Pair-wise的約束項。記(i,j)是用戶u的兩個已知評分商品，若原始矩陣中Mu,i>Mu,j，則在新的原始矩陣中，應該有M?u,i>M?u,j。記Su是觀察數據中用戶u的有序商品對集合的大小，Xk是用戶u的一個有序商品對，ΔMk表示原始觀察矩陣中商品對xk之間的差，Δτ(xk)表示預測評分矩陣中商品對xk之間的差。基于Ranking的目標損失函數可以表示為：

其中，表示0-1損失函數。0-1損失函數不可導，這里可以將它換成其他的光滑損失函數，如：L(ΔM,Δτ)= ΔMln(1+e-Δτ)。

2.4 損失函數形式化表示

給定用戶商品評分矩陣M，如上文所述將其擴展成R。損失函數主要包括三部分，即Pair-wise約束項、重構誤差和參數約束項，表示如下：

式（5）的第二項是AutoEncoder的重構誤差項，定義如下：

該項中，需要考慮的是原始評分矩陣中的可觀察數據，因此這里乘以評分單位矩陣I?，通過最小化重構誤差，對每個錨點局部矩陣，都會優化到相應的用戶特征矩陣Ut和商品特征矩陣Vt。最后的預測矩陣可表示為：

式（5）的第一項是Pair-wise約束項，用來保證同一用戶的商品評分在原始矩陣和預測矩陣中的大小次序的一致性。定義如下：

su表示用戶u的有序商品對的個數。L使用光滑損失函數如下：

這里ΔM是原始評分值的差值，c是一個常量因子，用來控制間距寬度值。式（5）最后一項是參數約束項，表示如下：

3 優化算法

3.1 算法推導

本文算法的優化目標是通過學習權重Wt、bt、Wt′、bt′來得到每個錨點矩陣的用戶-商品特征，同時，使用基于排序的損失函數來監督這些權重的學習過程。模型優化中通過參數α、γ來分別調整損失誤差、重構誤差以及正則項對模型的影響程度。本文采用梯度下降方法進行模型求解。

梯度下降求解之前，需要對目標函數的權重Wt、bt、Wt′、bt′求一階偏導，記：

首先，可對g(u,i,j)求其關于Ut和Vt的偏導數，如下：

根據鏈式求導法則，可得到損失函數ε關于Ut、Vt的偏導數，如下：

于是可以得到各個偏導數如下：

3.2 算法偽代碼

基于以上一階偏導，在初始化Wt、bt、Wt′、bt′后，可以根據以下規則優化參數：

其中，η是學習率。在每次迭代過程中，固定其中的一個參數并優化其他參數，直至算法收斂。算法偽代碼見算法1。

算法1基于集成局部性特征學習的推薦算法（LREAP）

輸入：用戶商品評分矩陣M；隱層節點個數k；錨點個數q以及參數α和γ。

輸出：預測用戶商品評分矩陣。

1.隨機初始化q個子模型的權重矩陣Wt、bt、Wt′、bt′；

2.根據式（2）計算每個AutoEncoder隱層節點的輸出，并將其分解成用戶特征矩陣Ut和商品特征矩陣Vt。同時根據式（7）計算得到預測的評分矩陣M?；

3.根據式（19）、（20）、（21）、（22）計算各項偏導，并通過式（23）、（24）更新權重；

4.重復步驟2和步驟3，直至算法收斂；

5.返回最后的預測評分矩陣。

算法的時間復雜度主要集中在計算用戶和商品的特征表示和排序損失。假設最大迭代次數為T，自動編碼機隱含層個數為k，q是選取的錨點個數，c為每個用戶包含的商品對的最大個數，那么算法的最大復雜度為O(qTkmn+qTcm)，其中m和n分別為用戶數和商品數，可以看到與用戶數和商品數直接相關。由于評分矩陣通常比較稀疏，矩陣的稀疏運算可以大大縮短算法運行時間。

4 實驗

4.1 實驗環境

實驗中使用了兩個真實評分數據集，分別是MovieLens（http://www.grouplens.org/）和 Netflix（http://prea.gatech.edu/download/netflix 3m1k.zip）。其中，MovieLens包含了943個用戶和1 682個商品的信息，評分矩陣稀疏度為6.3%；Netflix包含了4 427個用戶和1 000個商品，評分矩陣稀疏度為1.27%。

所有實驗采用的硬件環境為Intel Core i5-2500 CPU，4核3.1 GHz的主頻，4 GB內存；軟件環境：Windows 7操作系統，Matlab版本R2015a。

4.2 實驗評估

4.2.1 比較方法

（1）使用3個基于矩陣分解的算法NMF（nonnegative matrix factorization）[9]、PMF（probabilistic matrix factorization）[10]和 BPMF（Bayesian probabilistic matrix factorization）[11]作為基準分類器。其中，NMF是基于非負矩陣分解的算法，PMF是基于概率的矩陣分解算法，而BPMF是基于貝葉斯的矩陣分解算法。

（2）另外3個對比算法是基于Ranking的推薦算法，分別為RSVD（regularized singular value decomposition）、ColiRank[12]和 LCR（local collaborative ranking）[5]。RSVD是基于Ranking的奇異值矩陣分解算法，Coli-Rank是基于Rank的概率估計算法，而LCR則是基于局部矩陣的算法。

4.2.2 實驗設置

（1）對于每個數據集，隨機抽取N個商品作為訓練集，其他商品作為測試集（為保證測試數據中每個用戶至少10個商品，因此抽樣是保證被挑選出的用戶至少對N+10個商品有評分記錄）；評價指標是計算預測評分的NDCG@10值和平均準確率AvgPrecision（AP）；實驗中，N分別取5、10、15、20和25。

（2）本文算法有3個參數k、α和γ；實驗過程中，從每個訓練集中隨機抽取20%作為驗證集，來得到每組數據的最優參數。

4.2.3 實驗結果

表1和表2展示了在MovieLens和Netflix數據集上的實驗結果，其評估指標分別為NDCG@10和AP。從這些結果中，可以得出如下結論：

（1）隨著訓練樣本數量的增加，所有算法的性能都逐步提高。基于Ranking的算法（RSVD和Coli-Rank等）整體比沒有考慮評分順序的算法（NMF、PMF和BPMF等）性能要好一些，這體現了將評分的Ranking考慮進去能夠得到性能更優的算法。

Table 1 Experimental results in MovieLen data set表1 數據集MovieLen的實驗結果

Table 2 Experimental results in Netflix data set表2 數據集Netflix的實驗結果

LREAP的性能整體要顯著優于NMF、PMF和BPMF，這體現了LREAP使用AutoEncoder同時學習用戶和商品特征的優越性。LREAP具有良好的特征學習能力，同時考慮了商品的評分次序，因而能夠取得相對突出的效果。

（2）基于局部特征學習的算法LCR和LREAP比其他算法的性能都要更優，這體現了評分數據中的局部結構是存在的，針對局部“近鄰”簇進行學習，能學到更有效的特征。LREAP在NDCG@10和AP上取得和LCR相近甚至更高的評估結果，體現了基于AutoEncoder進行局部特征學習的有效性。

5 相關工作

下面簡單介紹本文的相關工作，包括采用矩陣分解的推薦系統以及利用深度學習技術的推薦系統。

基于矩陣分解的推薦方法大致可以分為兩類，即只利用評分矩陣的評分信息以及需要評分以外的其他信息。矩陣分解可以對多變量數據進行很好的分解，因此被用來分解評分矩陣得到用戶和商品的特征[9]。Paterek提出提升正則化奇異值分解來預測用戶的偏好[13]。Salakhutdinov和Mnih[10-11]進一步提出了概率矩陣分解（PMF）以及貝葉斯概率矩陣分解（BPMF）。PMF采用帶有高斯觀測噪聲的概率線性模型學習用戶和商品的隱性特征表示，在大規模以及稀疏評分數據上表現得很好。在BPMF中，通過集成所有模型參數以及超參數，可以自動控制模型能力。為了解決可擴展非參數矩陣分解模型到大規模問題中，Yu等人[14]介紹了一種新的優化算法，同時學習奇異值分解模型以及概率主成分分析模型。Sun等人[12]對排序數據進行建模，并應用到推薦系統以及網頁搜索中。Lee等人[5]也提出局部協同排序算法來考慮排序數據，實際上是矩陣分解模型的集成。本文提出的模型也考慮了排序數據。

為了考慮評分信息以外的信息，比如用戶社交網絡關系以及商品屬性信息[15-19]，Ma等人[17]利用用戶的社交網絡信息以及評分記錄，來解決數據稀疏性以及預測不準確等問題。Yang等人[18]推斷用戶社交信任圈和朋友關系用于推薦。Yu等人[16]提出隱性反饋推薦模型，從異構網絡中提取隱性特征。Wang等人[19]利用社交標注系統中的異構信息來減輕冷啟動問題。雖然外部信息可以很好地提高推薦性能，但是并不是那么容易獲取，因此本文模型只考慮評分信息的推薦算法。

近來也有一些基于深度學習的推薦系統。Salakhutdinov等人[6]首先使用限制玻爾茲曼機（restricted Boltzmann machines，RBM）進行推薦。Phung等人[8]擴展玻爾茲曼機到協同過濾任務，同時集成相似度以及貢獻矩陣。Wang等人[7]提出考慮商品內容信息，同時利用深度學習技術處理內容信息和利用協同過濾算法處理評分矩陣。這些方法要么需要額外的信息，要么不能很好地完全利用評分信息，本文模型把表示學習以及排序學習集成到一個框架中，提升了推薦算法性能。

6 結論

本文提出了使用AutoEncoder進行局部特征學習的推薦算法。在使用AutoEncoder學習推薦系統中的評分數據特征時，考慮了推薦數據中分類的成組結構特性，將原始評分矩陣分解成多個關聯度不大的獨立子模塊，在每個子模塊上學習用戶和商品隱性特征表示。本文提出的模型能夠使用Auto-Encoder同時學習評分數據中的用戶隱性特征表示和商品隱性特征表示。另外，本文不僅僅關注學習到的特征對信息的還原能力，而且還考慮了評分次序的一致性問題，即同一個用戶對不同商品的評分在原始評分矩陣和與預測評分矩陣中的次序應該保持一致，使用基于Pair-wise的約束項來實現該一致性條件。實驗結果表明，基于AutoEncoder的局部特征表示學習算法能夠有效地學習評分矩陣中的用戶和商品隱性特征表示，提高了推薦系統的性能。實驗結果還驗證了深度學習用于推薦系統中進行特征學習的優越性，同時體現了基于局部特征學習思想的有效性。

:

[1]Adomavicius G,Tuzhilin A.Toward the next generation of recommender systems:a survey of the state-of-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(6):734-749.

[2]Koren Y,Bell R M.Advances in collaborative filtering[M].Berlin,Heidelberg:Springer,2011:145-186.

[3]Ricci F,Rokach L,Shapira B.Introduction to recommender systems handbook[M].Berlin,Heidelberg:Springer,2011:1-35.

[4]Bellogín A,Cantador I,Castells P.A comparative study of heterogeneous item recommendations in social systems[J].Information Sciences,2013,221(1):142-169.

[5]Lee J,Bengio S,Kim S,et al.Local collaborative ranking[C]//Proceedings of the 23rd International World Wide Web Conference,Seoul,Apr 7-11,2014.New York:ACM,2014:85-96.

[6]Salakhutdinov R,Mnih A,Hinton G E.Restricted Boltzmann machines for collaborative filtering[C]//Proceedings of the 24th International Conference on Machine Learning,Corvallis,Jun 20-24,2007.New York:ACM,2007:791-798.

[7]Wang Hao,Wang Naiyan,Yeung D Y.Collaborative deep learning for recommender systems[C]//Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Sydney,Aug 10-13,2015.New York:ACM,2015:1235-1244.

[8]Truyen T T,Phung D Q,Venkatesh S.Ordinal Boltzmann machines for collaborative filtering[C]//Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence,Montreal,Jun 18-21,2009.AUAI Press,2009:548-556.

[9]Lee D D,Seung H S.Algorithms for non-negative matrix factorization[C]//Proceedings of the 13th International Conference on Neural Information Processing Systems,Denver,2001.Cambridge:MIT Press,2011:556-562.

[10]Salakhutdinov R,Mnih A.Probabilistic matrix factorization[C]//Proceedings of the 20th International Conference on Neural Information Processing Systems,Vancouver,Dec 3-6,2007.Red Hook:CurranAssociates,2007:1257-1264.

[11]Salakhutdinov R,Mnih A.Bayesian probabilistic matrix factorization using Markov chain Monte Carlo[C]//Proceedings of the 25th International Conference on Machine Learning,Helsinki,Jun 5-9,2008.New York:ACM,2008:880-887.

[12]Sun Mingxuan,Lebanon G,Kidwell P.Estimating probabil-ities in recommendation systems[J].Journal of the Royal Statistical Society,2012,61(3):471-492.

[13]Paterek A.Improving regularized singular value decomposition for collaborative filtering[C]//Proceedings of KDD Cup and Workshop,San Jose,Aug 12,2007.New York:ACM,2007:5-8.

[14]Yu Kai,Zhu Shenghuo,Lafferty J,et al.Fast nonparametricmatrix factorization for large-scale collaborative filtering[C]//Proceedings of the 32nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Boston,Jul 19-23,2009.New York:ACM,2009:211-218.

[15]Ma Hao,Zhou Dengyong,Liu Chao,et al.Recommender systems with social regularization[C]//Proceedings of the 4th International Conference on Web Search and Web Data Mining,Hong Kong,China,Feb 9-12,2011.New York:ACM,2011:287-296.

[16]Yu Xiao,Ren Xiang,Sun Yizhou,et al.Personalized entity recommendation:a heterogeneous information network approach[C]//Proceedings of the 7th ACM International Conference on Web Search and Data Mining,New York,Feb 24-28,2014.New York:ACM,2014:283-292.

[17]Ma Hao,Yang Haixuan,Lyu M R,et al.Sorec:social recommendation using probabilistic matrix factorization[C]//Proceedings of the 17th ACM Conference on Information and Knowledge Management,Napa Valley,Oct 26-30,2008.New York:ACM,2008:931-940.

[18]Yang Xiwang,Steck H,Liu Yong.Circle-based recommendation in online social networks[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Beijing,Aug 12-16,2012.New York:ACM,2012:1267-1275.

[19]Feng Wei,Wang Jianyong.Incorporating heterogeneous information for personalized tag recommendation in social tagging systems[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Beijing,Aug 12-16,2012.New York:ACM,2012:1276-1284.