基于Spark的矩陣分解與最近鄰融合的推薦算法①

王振軍, 黃瑞章,(貴州大學 計算機科學與技術學院, 貴陽 55005)(貴州省公共大數據重點實驗室, 貴陽 55005)

基于Spark的矩陣分解與最近鄰融合的推薦算法①

王振軍1, 黃瑞章1,21(貴州大學 計算機科學與技術學院, 貴陽 550025)2(貴州省公共大數據重點實驗室, 貴陽 550025)

隨著當前移動互聯網的快速發展, 人們所面臨的信息過載問題變得尤為嚴重, 大數據場景下對特定用戶的個性化推薦面臨著巨大挑戰. 為了進一步提高推薦的時效性、準確度以及緩解面臨的大數據量. 提出了一種矩陣分解推薦算法在大數據環境下的優化算法模型. 該模型通過在傳統矩陣分解推薦算法的基礎上融合了用戶以及物品的相似性計算, 在訓練目標函數的過程中, 即融入用戶以及物品的前k個最近鄰居的相似性計算, 增強了算法的推薦準確度. 利用Spark在內存計算以及迭代計算上的優勢, 設計了一種Spark框架下的矩陣分解與最近鄰融合的推薦算法. 通過在經典數據集—MovieLens數據集上的實驗結果表明, 該算法與傳統的矩陣分解推薦算法相比, 可以很好的緩解數據稀疏性, 提高推薦算法的準確度, 并且在計算效率方面也優于現有的矩陣分解推薦算法.

協同過濾; 推薦算法; 矩陣分解; 交替最小二乘法; Spark

協同過濾技術(Collaborative Filtering Recommendation, CF)[1]基于用戶或者物品的相似性來產生推薦, 是當前推薦系統領域最成功的技術之一,隨著數據挖掘相關技術的迅速發展, 基于隱語義模型(Latent Factor Model, LFM)的推薦算法[2]是一類更加精確高效的協同過濾技術. 自Netflix Prize大賽[3]以來, LFM算法中很重要的一部分當屬矩陣分解范疇, 該方法在文獻[4]中首次提到, 它與其他算法結合的混合推薦算法最終獲得了Netflix推薦算法大賽大獎.

近些年來, 矩陣分解在學術研究以及商業應用中越來越受到研究人員的青睞. 文獻[5]提出了SVD(singular value decomposition(SVD))模型方法, 其推薦效果優于傳統的基于鄰域的推薦算法, 其中心思想是把用戶-物品的評分矩陣進行因子分解, 很多方法[6,7]通常會忽略了矩陣中高度的缺失值導致的數據稀疏性問題, 傳統的SVD在矩陣稀疏的時候作用是不明確的,而且, 粗暴的處理一些相對已知的條目非常容易產生過度擬合. 文獻[8]提出了一種基于矩陣分解與用戶近鄰模型的推薦算法, 該算法很好的實現了矩陣分解與用戶近鄰模型的融合, 在一定程度上提高了推薦準確度, 但是忽略了物品之間的相似性對推薦準確度的影響, 并且該算法存在模型的過擬合問題. 文獻[9]提出了基于MapReduce的矩陣分解算法, 該算法解決了大規模評分矩陣在多節點間的高效共享問題, 實現了多次迭代計算的并行處理, 但是在基于Mapreduce的編程框架下, 迭代過程中過多的節點間通信以及I/O讀寫影響了算法的執行效率.

本文圍繞解決上述問題展開研究, 并在已有研究的基礎上, 結合經典的矩陣分解推薦模型, 融合最近鄰模型的相似性計算, 提出了基于Spark的矩陣分解與最近鄰融合的推薦算法. 首先通過評分矩陣計算用戶以及物品之間的相似性, 然后分別應用用戶以及物品的前k個近鄰融合矩陣分解模型來達到預測特定用戶評分的目的. 實驗表明, 該算法能夠有效的提高推薦算法準確度以及計算效率.

1 基礎知識

1.1 矩陣分解

假設用戶-物品評分矩陣為R, 矩陣中每一個元素表示用戶u對物品i的評分, 則由矩陣奇異值分解原理可知, 矩陣R可以分解為幾個矩陣相乘的形式, 矩陣分解的目標就是把用戶和物品評分矩陣映射到同一個維數為f的潛在因子空間, 這樣用戶和項目之間的關系就可以通過因子空間中的內積來建模, 如下公式:

其中: m表示用戶數量, n表示物品數量; P ∈?f×m表示用戶的隱語義屬性參數(行),表示物品的隱語義屬性參數(行). 那么, 對于用戶u對物品i的評分的預測值u, i)=r,可以通過如下公式計算:

其中: puf=P( U, F), qif=Q( i, f). 那么矩陣分解的目標就是計算得到每個用戶的因子向量pu, 每個物品對應的因子向量qi, 使得預測用戶u對物品i的預測評分r?ui能夠盡可能地接近真實評分rui. 當給定的矩陣不完全時, 此模型容易導致過擬合, 因此, 當前的很多研究都建議對存在的評分項進行建模, 采用正則化參數避免過擬合問題, 目標函數定義如下:

其中: λ參數用來正則化模型, 成為正則化系數; K表示訓練集中存在的評分項. 求解上面的模型, 目前常用的方法有兩種: 隨機梯度下降法(Stochastic Gradient Descent, SGD)和交替最小二乘法(Alternating Least Squares, ALS).

1.2 最近鄰模型

最近鄰模型[10]是協同過濾推薦算法中比較常用的算法模型, 基本上可以分為基于用戶的近鄰模型以及基于物品的近鄰模型. 其中心思想是計算選取用戶或者物品的前k個最近鄰居來模擬主體的行為從而預測用戶對物品的評分. 這種方法不關注用戶物品之間的相互關系,而只關注用戶之間以及物品之間的相似度就能計算出某用戶對某物品的興趣評分, 從而給出推薦類目.

1.3 Spark平臺

Spark[11]由美國加州大學的伯克利分校的AMP實驗室首次提出的類Hadoop MapReduce的基于內存計算的大數據并行計算框架. Spark不同于MapReduce的是job的中間結果不需要再寫入本地的HDFS, 而是直接在內存中完成, 可以更好的適用于機器學習以及數據挖掘的多次迭代的計算, 近些年來, Spark已經被廣泛應用到學術研究以及商業計算中.

Spark最主要的創新點是提出了彈性分布式數據集[12](Resilient Distributed Dataset, RDD). RDD本質上是一種只讀的分布式共享內存模型, 它具備像MapReduce等數據流模型的容錯特性, 并且允許開發人員在大型集群上執行內存的計算. 彈性表現在若一個RDD分片丟失, Spark可以根據日志信息重構它; 分布式表現在可以用操作本地集合的方式來操作分布式數據集. 此外, RDD可以被緩存在內存中, 在之后的計算過程中可以直接從內存中讀入, 省去了大量的磁盤存取開銷, 適合需要迭代計算尋優的矩陣分解算法.圖1 展示了Spark的基本工作流程, 每一個Spark 應用程序主要由SaprkContext和Executor兩部分完成, Executor負責執行任務, 運行Executor的機器稱為Worker節點, SparkContext由用戶程序啟動, 通過資源調度模塊和Executor通信. 這種運行模式有利于進行不同應用程序之間的資源調度隔離以及共享.

圖1 Spark的基本工作流程

2.1 問題分析

在前面介紹矩陣分解算法, 在求解隱語義向量的過程中, P和Q矩陣中會丟失用戶或者物品的某些信息, 如用戶之間的相似性以及物品之間的相似性, 通過模型訓練后得到的P和Q矩陣求得的用戶或物品之間相似性(皮爾森相關系數)與由用戶評分矩陣求得的相似性存在出入. 于是, 我們提出一種新的目標函數,即融入用戶和物品之間的相似性進行模型訓練, 這樣,就可以保持訓練前后, 它們之間相似性的一致性.

2.2 優化方案

本文稱這種融合模型推薦算法為Matrix Factori(MF-KNN), 下面是具體步驟.

1) 通過用戶-物品的歷史評分數據得到用戶-物品評分矩陣, 經過對比研究, 這里, 我們采用皮爾森相似距離計算用戶-用戶, 物品-物品之間的相似度:

2) 設計損失函數時, 為使模型訓練前后的用戶以及物品之間的相似性保持一致, 我們將上面計算得到的相似度數據融入目標函數中, 再迭代求解最小化目標函數, 最后得到最終的P和Q矩陣.

上述公式中, (i, j)∈I訓練集中存在的評分項, Ij表示用戶集合, Ii表示物品集合, KNN(ui)表示用戶ui的前K個最近鄰居集合, KNN(mj)表示物品mj的前K個最近鄰居集合, simuiup代表用戶之間的相似度, simmimp代表物品之間的相似度, k表示某一個特征(或隱含因子).

為求解上述目標函數, 我們采用Spark計算方式來求解特征矩陣U和M, 與上一節中提到求解傳統矩陣分解模型的方法類似, 這里我們采用最小二乘法(ALS), 首先固定U求解M, 然后固定M求解U, 這樣迭代求解. 具體如下:

以上, 每次迭代求取ui, 同理, 對于mj, 有:

2 基于Spark的矩陣分解算法優化

我們這樣設計是因為考慮融合相似性信息進損失函數中, 如果全面考慮計算U和M中用戶或者物品的相似性, 然后與由評分矩陣計算的到的相似性進行對比時, 偏導數的求解很復雜, 而且計算量過大, 于是設計為計算用戶或者物品的K近鄰這種方法簡單處理.可以很好的中和K近鄰模型的相似性進損失函數, 以期望在矩陣分解后, 能減少用戶或者物品信息的丟失,進而提高算法在評分預測場景下的準確度.

2.3 Spark框架下的矩陣分解最最近鄰融合的并行化算法

輸入: 用戶評分矩陣Ratings

輸出: 矩陣分解模型

#Ratings為用戶評分矩陣, U與M為用戶及物品個數, F為隱語義屬性個數

1) partitions = N

2) sc = SparkContext()

3) 讀入數據生成Rating:RDD,#Rating是序列

＜User,Item,rating＞

4) 隨機生成ms和us矩陣

W = matrix(rand(m,F))

U = matrix(rand(u,F))

Rb = sc.broadcast(R)

Mb = sc.broadcast(M)

Ub = sc.broadcast(U)

5) #相似性計算獲得最近鄰居

user_sims = Rb.map(lambda

x:calcSim(x[0],x[1])).map(lambda

x:keyOnFirstUser(x[0],x[1]))groupByKay().ma

p(lambda x:nearestNeighbors(x[0],x[1],20))

item_sims = Rb.map(lambda

x:calcSim(x[0],x[1])).map(lambda

x:keyOnFirstItem(x[0],x[1]))groupByKay()

.map(lambda

x:nearestNeighbors(x[0],x[1],20)) 6) #按照設定的迭代值進行迭代

for i in range(ITERATIONS):

#固定U, 并行化更新M

M = sc.parallelize(range(m),partisons)

.map(lambda

x:update(x,Mb.value[x,:],Ub.value,Rb.val ue))

.collect()

M = matrix(np.array(M)[:,:,0])

Mb = sc.broadcast(M)

#固定M, 并行化更新U

U = sc.parallelize(range(u),partition)

.map(lambda

x:update(x,Ub.value[x,:],Mb.value,Rb.val ue.T)).collect()

U = matrix(np.array(U)[:,:,0])

Ub = sc.broadcast(U)

error = rmse(R,M,U)

sc.stop()

如上述算法所示: 基于Spark的矩陣分解與最近鄰融合算法的尋優方式和矩陣分解類似, 算法主要是模型不斷迭代尋優的過程, 其中固定U更新M, 然后固定M更新U, 依次循環迭代, 直到在訓練集上計算得到rmse值達到近似收斂, 即模型達到了最優, 最后求得的Ub和Mb分別為用戶和物品的特征矩陣.

3 實驗分析

3.1 實驗環境

基于上述研究, 本實驗采用3臺搭載CentOS 6.5操作系統的服務器, 在部署了Hadoop2.6.0基礎上部署了Spark-1.5.0分布式集群, 利用Pycharm作為開發工具.

3.2 數據集

為了驗證算法效果, 本實驗采用國際經典數據集—MovieLens數據集, 數據集包括了943個用戶對大約1500部電影的評分數據, 數據條數為100000. 用戶對電影的評分數值為從1到5. 其中, 1表示最低, 5表示最高, 0代表未評論.

實驗過程將原始數據集以8:2的比例劃分為訓練集和測試集.

3.3 評測標準

本實驗將采用推薦系統領域最常用的均方根誤差(Root Mean Squared Error, RMSE)作為評測標準. 通過計算預測的用戶評分與實際的用戶評分之間的誤差來反映評分預測的準確性, RMSE越小, 評分預測準確度就越高.

對于測試集中的每一個用戶u和物品i, 令T表示用戶u對物品i的評分集合, rui是用戶u對物品i的實際評分, 而?uir是推薦算法給出的預測評分, RMSE的定義公式如下:

3.4 實驗結果與分析

本文通過實驗對比MF-KNN算法在評分預測問題中的性能. 在該算法中, 重要的模型參數有3個: 隱含特征個數F, 近鄰模型鄰居k的個數以及正則化參數lambda. 通過多輪試驗發現, 隱含特征個數以及近鄰模型鄰居k的個數對算法性能影響最大. 算法參數選擇: 正則化參數lambda通過交叉驗證決定.

本文統一采用lambda=0.005進行實驗, 在訓練集上迭代次數選用40次. 控制鄰域范圍k, 通過實驗證明k值越大, 算法精度越高, 因此需要在算法精度與計算代價之間取得平衡.

實驗1我們首先在Spark環境下分別對優化后的矩陣分解與最近鄰融合的推薦算法(MF-KNN)、傳統的矩陣分解推薦算法(MF)以及基于物品的鄰域模型(ItemNgbr)進行對比實驗, 計算兩者的評分預測準確度指標RMSE值.

對于上組實驗中的的每種模型, 選用最優化的參數, 對于基于物品的鄰域模型, 我們選取鄰居大小為50, 而對于矩陣分解與最近鄰融合的模型, 我們分別選取用戶以及物品鄰居大小集合為20. 實驗結果如圖2所示, 可以得出矩陣分解模型可以很好的優于基于鄰域的模型, 進而得出, 矩陣分解與最近鄰融合模型可以在很大程度提高矩陣分解的推薦準確度, 另外,從圖中可以看出, 隨著F值的增加, RMSE值下降速度明顯變緩, 這也從側面表明了算法每次計算得出的結果都是最顯著的特征向量.

其次, 我們進一步考慮最近鄰居k的個數對算法性能的影響. 實驗2我們采用固定F=50, 等差增加k值, 觀測算法迭代耗費時間以及預測誤差的變化.

圖2 不同F值各模型在MovieLens數據集下的RMSE值

表1 隨著最近鄰居k的增加所獲得的預測誤差

表1可以得出, 當固定隱特征數量F=50, 迭代收斂的耗費時間隨最近鄰居k值的增加而上升, 當達到k=20時, RMSE值變化幅度微小. 主要是因為, 在融合最近鄰居相似度信息的時候, 前k個最近鄰居可以基本代表整個主體行為信息. 因此, 針對于不同的應用場景, 經過多次實驗, 才可以獲得本場景下最佳近鄰模型的k值.

最后, 為驗證算法的計算效率, 實驗3在Spark環境下和非分布式環境下分別計算本文提出的基于Spark的矩陣分解與最近鄰融合的推薦算法運行時間,比較其在相同用戶數量, 相同硬件條件下的計算效率.圖3表明基于Spark的矩陣分解與最近鄰融合的推薦算法對于同等規模的數據集, Spark框架下的計算方式要比非分布式的計算方式節約更多的運行時間, 并且隨著Spark節點數量的增加, 此算法在Spark框架下的耗時增長更趨于平滑, 這體現了Spark基于內存計算的實時性優勢. 當用戶數=200時, 一個Saprk節點與非分布式的計算時間相比耗時要多一些, 這說明, Spark開始計算時, 要啟動整個計算框架分片, 要耗費一定時間.

圖3 不同用戶數量并行化運行時間的比較

綜上可以得出, 基于Spark的矩陣分解與最近鄰融合的推薦算法無論是在推薦準確度還是在計算效率方面都要優于當前大部分的推薦算法.

4 結語

最近幾年, 矩陣分解推薦算法是推薦系統領域中的一個非常熱門的研究課題. 本文針對傳統矩陣分解推薦算法面臨的推薦準確度以及計算效率方面的問題,結合傳統的最近鄰算法以及當前新興并行化計算框架,提出了基于Spark的矩陣分解與最近鄰融合的推薦算法. 該算法充分利用顯性反饋數據, 提高了推薦準確度的同時, 也很大程度上提高了傳統矩陣分解算法的計算效率.

最后, 本文設定的主要應用場景為只有顯式反饋,雖然這種場景比較普遍, 但在現實生活中, 顯式反饋與隱式反饋并存, 如何整合這兩種資源以提高推薦質量有待進一步研究.

1 Schafer JB, Dan F, Herlocker J, et al. Collaborative filtering recommender systems. The Adaptive Web, Methods and Strategies of Web Personalizationk, 2010: 46–45.

2 Koren Y. Factorization meets the neighborhood: A multifaceted collaborative filtering model. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM. 2008. 426–434.

3 Bennett J, Lanning S, Netflix N. The Netflix Prize// Kdd Cup and Workshop in Conjunction with Kdd. 2009.

4 Koren Y, Bell R,Volinsky C. Matrix factorization techniques for recommender systems. Computer, 2009, 42(8): 30–37.

5 Vozalis MG, Margaritis KG. Applying SVD on item-based filtering. International Conference on Intelligent Systems Design and Applications. 2005. 464–469.

6 Kim D, Yum BJ. Collaborative filtering based on iterative principal component analysis. Expert Systems with Applications, 2005, 28(4): 823–830.

7 Herlocker JL, Konstan JA, Borchers A, et al. An algorithmic framework for performing collaborative filtering. SIGIR’99: Proc. of the International ACM SIGIR Conference on Research and Development in Information Retrieval. August 15–19, 1999. Berkeley, Ca, Usa. 1999. 230–237.

8楊陽,向陽,熊磊.基于矩陣分解與用戶近鄰模型的協同過濾推薦算法.計算機應用,2012,32(2):395–398.

9 張宇,程久軍.基于MapReduce的矩陣分解推薦算法研究.計算機科學,2013,40(1):19–21.

10 Su X, Khoshgoftaar TM. A survey of collaborative filtering techniques. Advances in Artificial Intelligence, 2009, (12).

11 Zaharia M, Chowdhury M, Franklin MJ, et al. Spark: Cluster computing with working sets. Usenix Conference on Hot Topics in Cloud Computing. USENIX Association. 2010. 1765–1773.

12 Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. Usenix Conference on Networked Systems Design and Implementation. 2012. 141–146.

Recommendation Algorithm Using Matrix Decomposition and Nearest Neighbor Fusion Based on Spark

WANG Zhen-Jun1, HUANG Rui-Zhang1,212(School of Computer Science and Technology, Guizhou University, Guiyang 550025, China) (Guizhou Provincial Key Laboratory of Public Big Data, Guiyang 550025, China)

With the current rapid development of mobile Internet, the information overload problem that people face is particularly serious, which makes it a big challenge to do particular users’ personalized recommendation in the big data scenario. In order to further improve the timeliness, accuracy of recommendation and ease the problem led by large amount of data, we propose a optimized matrix decomposition recommendation algorithm under the environment of big data in this paper. This algorithm integrates users and the similarity computation of items on the basis of the traditional matrix decomposition algorithm. In the process of training objective function, we enhance the recommendation accuracy by taking in account of users and k nearest neighbors’ similarity computation of items. Taking Spark’s advantage on memory computing and iterative computing, we design an algorithm using matrix decomposition and nearest neighbor fusion under the Spark framework. Experiments conducted on the classical MovieLens dataset show that our proposed algorithm can deal with data sparseness well, improve recommendation accuracy to some extent, and has a better computational efficiency in the comparison with traditional matrix decomposition recommendation algorithms.

collaborative filtering; recommendation algorithm; matrix decomposition; ALS; Spark.

國家自然科學基金(61462011,61202089);高等學校博士學科專項科研基金(20125201120006);貴州大學引進人才科研項目(2011015);貴州省應用基礎研究計劃重大項目(黔科合JZ字[2014]2001-01)

2016-08-15;收到修改稿時間:2016-09-27

10.15888/j.cnki.csa.005743