基于Spark的K近鄰ALS的推薦算法

劉佳耀 王佳斌

摘要：傳統(tǒng)的協(xié)同過濾推薦算法在面對海量數(shù)據(jù)時表現(xiàn)出處理速度慢和效率低下的瓶頸，與Hadoop平臺相比，Spark計算框架具有迭代計算優(yōu)勢，提出了基于spark的K近鄰ALS推薦算法。由于一般的矩陣分解算法只考慮隱含信息忽略了相似度的信息，所以將相似度信息加權(quán)到評分預(yù)測的公式中，并采用交替最小二乘法進(jìn)行模型訓(xùn)練得出結(jié)果。在MovieLens數(shù)據(jù)集上驗(yàn)證，該改進(jìn)算法能夠提高推薦的準(zhǔn)確性，提高對大數(shù)據(jù)集的處理效率。

關(guān)鍵詞：協(xié)同過濾；Hadoop；Spark；ALS

中圖分類號：TP391.1 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）11-0006-02

A Recommendation Algorithm Based on Spark's K neighbor ALS

LIU Jia-yao， WANG Jia-bin

（Institute of Technology Huaqiao University， Quanzhou 362021， China）

Abstract： Traditional collaborative filtering recommendation algorithm in the face of huge amounts of data show the processing speed is slow and inefficient bottleneck， compared with the Hadoop platform， Spark computing framework has the advantages of iterative calculation， and puts forward the K neighbor ALS recommendation algorithm based on the Spark.Due to generally only considered implicit information of the matrix decomposition algorithm ignores the similarity of information， so will be weighted similarity information to score prediction formula， and alternating least squares method is adopted to model the training results.n the MovieLens data set， the improved algorithm can improve the accuracy of recommendation and improve the processing efficiency of large data sets.

Key words： Collaborative filtering； Hadoop； Spark； ALS

1 引言

隨著互聯(lián)網(wǎng)的迅速發(fā)展，各種信息也呈爆炸性增長，接踵而來的是出現(xiàn)了“信息過載”的問題。為了解決這個問題，推薦系統(tǒng)由此產(chǎn)生，推薦系統(tǒng)[1]可以通過用戶對各種商品的評分或用戶以前的瀏覽記錄，來為用戶推薦他們所需的信息。協(xié)同過濾[2]算法是推薦系統(tǒng)中運(yùn)用最常用的算法，但是在大數(shù)據(jù)背景下隨著用戶和項(xiàng)目數(shù)量的不斷增長，用戶-項(xiàng)目矩陣的稀疏和單機(jī)上的瓶頸導(dǎo)致推薦質(zhì)量和準(zhǔn)確性不斷下降。

針對以上問題，許多研究人員提出了有效的改進(jìn)方法。文獻(xiàn)[3]提出了基于矩陣分解的協(xié)同過濾算法，該算法通過降低數(shù)據(jù)稀疏性，提高了推薦準(zhǔn)確性。文獻(xiàn)[4]提出了一種基于矩陣分解與用戶近鄰模型的混合推薦模型，最大程度上利用用戶信息和降維的思想來提升推薦效率，但是沒有實(shí)現(xiàn)并行化，推薦效率低。文獻(xiàn)[5]提出了基于Spark的矩陣分解與最近鄰結(jié)合算法，該算法通過運(yùn)用Spark平臺的優(yōu)勢，提高了算法的可擴(kuò)展性和減少了推薦時間。交替最小二乘法ALS通過矩陣分解把評分缺失值給填充了，降低了數(shù)據(jù)的稀疏性，提高了推薦質(zhì)量。

現(xiàn)在應(yīng)用廣泛的大數(shù)據(jù)平臺有兩種分別為Hadoop和Spark。由于在Hadoop2.6.1[6]YARN上的分布式計算框架MapReduce[7]完成每次的map和reduce任務(wù)，都需要經(jīng)過磁盤，會引起高延遲性。而Spark計算框架的Job中間輸出和結(jié)果可保存在內(nèi)存中，能盡量減少了訪問硬盤次數(shù)，提高迭代速度。

本文圍繞解決上述問題展開研究，并在已有研究的基礎(chǔ)上，把相似度因子加權(quán)到矩陣分解的模型中，并結(jié)合Spark[8]平臺，提高推薦精確度和推薦效率。

2 Spark計算框架

2.1 搭建Spark平臺

本實(shí)驗(yàn)的Spark平臺采用的VMware Workstation的三臺虛擬機(jī)來搭建，包含一個主節(jié)點(diǎn)和三個從節(jié)點(diǎn)，三個節(jié)點(diǎn)的系統(tǒng)均為Centos6.5。

軟件安裝：Hadoop版本為hadoop-2.6.1.tar.gz；JAVA版本為jdk-7u75-linux-i586.gz；Spark版本為1.6.0-bin-hadoop2.6.tgz；Scala版本為2.12.4.tgz。在三臺虛擬機(jī)上分別配置好這些軟件，然后先啟動yarn，在yarn的基礎(chǔ)上再啟動spark。

2.2 Spark內(nèi)存計算框架

Spark大數(shù)據(jù)處理框架通過一種彈性分布式數(shù)據(jù)集RDD，可以把對數(shù)據(jù)的處理都封裝為對RDD的處理，RDD數(shù)據(jù)集有兩個特點(diǎn)：第一個是：適合在內(nèi)存中存取，這樣在迭代計算時，可以減少或避免向磁盤讀數(shù)據(jù)或?qū)憯?shù)據(jù)，都在內(nèi)存中計算，提高數(shù)據(jù)處理效率。第二個是：很好的容錯性，避免了數(shù)據(jù)冗余的麻煩和檢查費(fèi)時的問題。

3 基于矩陣分解的K近鄰ALS模型

3.1 矩陣分解思想

矩陣分解方法的關(guān)鍵思想是將用戶-物品評分矩陣從高維矩陣分解為幾個低維矩陣的相互乘積，不同于一般的協(xié)同過濾算法，該算法是評分預(yù)測算法，最近幾年來在推薦算法中使用最為頻繁，其主要思想就是將評分矩陣中大量缺失的評分值通過邏輯回歸的形式進(jìn)行填充，具體方法如下：

假設(shè)有X個用戶Y個項(xiàng)目，首先把矩陣中大量的缺失值填充成R矩陣，然后再將這個矩陣分解：把R矩陣分解為用戶矩陣[p∈Rf×m]和物品矩陣[Q∈Rf×n]，通過分解后的矩陣估計評分為：

[rui=puqi] （1）

風(fēng)險構(gòu)造函數(shù)為：

[C（p，q）=min（u，i）n（rui-puqTi）2+λ（||pu||2+||qi||2）] （2）

其中[λ]參數(shù)用來正則化模型，成為正則化系數(shù)；k表示預(yù)測評分項(xiàng)，評分預(yù)測的目的就是將上面的損失函數(shù)盡可能最小化。

求解上面的模型，目前效率高的方法有兩種：最小二乘法（ALS）[9]和隨機(jī)梯度下降法[10]（SGD）。

3.2 基于K近鄰ALS的推薦模型

Spark 機(jī)器學(xué)習(xí)庫中的常用的推薦算法是基于矩陣分解的ALS算法，其方法是通過評分預(yù)測的方式填充稀疏用戶-物品矩陣，填充采用ALS算法?；赟park的ALS算法的核心就是將稀疏矩陣進(jìn)行分解為用戶矩陣和物品矩陣，然后用交替最小二乘法進(jìn)行物品與用戶的特征向量不斷更新直到使其誤差平方和最小。由于在訓(xùn)練模型過程中，用戶矩陣和物品矩陣中會丟失部分相似性信息，于是將K近鄰算法得到的相似度信息加權(quán)到ALS算法中的損失函數(shù)，進(jìn)行模型訓(xùn)練。

在公式（1）中，通過將用戶和物品與隱因子聯(lián)系起來，因此在評分預(yù)測公式中加入偏置項(xiàng)，得到的評分預(yù)測公式如下：

[rui=μ+bu+bi+puqi] （3）

其中[μ]表示訓(xùn)練集中所有記錄評分的全局平均數(shù)，[bi]是物品偏置項(xiàng)，[bu]是用戶偏置項(xiàng)。

物品-物品，用戶-用戶之間的相似度用皮爾森相似距離計算，公式如下：

[S（i，j）=c∈Ii（Ri，c-Ri）（Rj，c-Rj）c∈Ii（Ri，c-Ri）2c∈Ii（Rj，c-Rj）2] （4）

根據(jù)公式（2）中ALS推薦模型訓(xùn)練的損失函數(shù)，在使用訓(xùn)練模型求解物品矩陣和用戶矩陣的過程中，發(fā)現(xiàn)忽略了用戶或物品相似度，由此進(jìn)一步考慮將用戶或物品相似度與損失函數(shù)進(jìn)行加權(quán)以縮小系統(tǒng)誤差，得到K近鄰ALS推薦模型，相似度誤差計算如下：

[P=u∈Nu（puk-pv∈KNN（pu）（Spupvpvk）pv∈KNN（pu）Spupv）2] （5）

[Q=i∈Ni（qik-qj∈KNN（qi）（Spipjqjk）qj∈KNN（qi）Spipj）2] （6）

其中的N表示物品或用戶的集合總數(shù)，KNN表示物品或用戶的K近鄰集合，S表示用戶之間相似度，k表示某一個特征（或隱含因子），上述公式從相似物品或用戶的信息進(jìn)行用戶-物品評分誤差的計算，并將得到的相似度誤差信息加權(quán)到基于ALS的評分誤差預(yù)測中，得到改進(jìn)算法，K近鄰ALS模型的損失函數(shù)計算公式如下：

[C（p，q）=min（u，i）∈kn（rui-puqTi）2+λ（||pu||2+||qi||2）]（7）

4 實(shí)驗(yàn)設(shè)計與結(jié)果分析

本文采用的數(shù)據(jù)來自GroupLens的MovieLens標(biāo)準(zhǔn)數(shù)據(jù)集，包含3個大小不同的數(shù)據(jù)集，從小到大依次為ml-100k的數(shù)據(jù)集、ml-1M的數(shù)據(jù)集和ml-10M的數(shù)據(jù)集。用戶對電影評分的等級分為1 ～ 5級別，分?jǐn)?shù)越高，表示用戶對電影越喜愛。

4.1 運(yùn)行時間

根據(jù)不同大小的數(shù)據(jù)集在Spark平臺下的運(yùn)行時間，如下圖1所示。

可知，同一數(shù)據(jù)集上，在Spark計算框架下，增加集群中的節(jié)點(diǎn)數(shù)可以明顯減少處理時間，提高處理速度和擴(kuò)展性。

4.2 平均絕對誤差（MAE）

本文采用推薦領(lǐng)域中常用的平均絕對誤差MAE作為度量指標(biāo)。MAE計算實(shí)際用戶評分值與預(yù)測的評分值之間的差值，根據(jù)這個值來衡量推薦的精確性，計算公式如下：

[MAE=1N|pi-qi|N] （8）

其中N為評分總個數(shù)，[pi]為用戶對項(xiàng)目i預(yù)測評分值，[qi]為實(shí)際評分值。因此，MAE越小代表誤差越小，預(yù)測準(zhǔn)確性越高。

4.3 算法對比

為了對比本文改進(jìn)算法與其他算法的效果，本文在Spark框架下對同一數(shù)據(jù)集ml-1M進(jìn)行了實(shí)驗(yàn)測試，選用的對比算法是Spark MiLib庫中的ALS算法模型，評價指標(biāo)是MAE，如下圖2所示：

其中KNN算法橫坐標(biāo)表示K近鄰值，兩個ALS模型表示最小化損失函數(shù)過程中的迭代次數(shù)，其他兩個參數(shù)lambda和ranks分別使用了0.2和10。

從圖2中看出，隨著最近鄰居的增加和迭代次數(shù)的增加，加權(quán)了相似度信息后的ALS算法的MAE值小于ML庫中的ALS算法，推薦精度更高。

5 總結(jié)

在當(dāng)前信息數(shù)據(jù)量以爆炸式增長的環(huán)境下，提出了把推薦算法和大數(shù)據(jù)平臺相結(jié)合來提高推薦效率，通過對MAE值的觀察，在ALS算法基礎(chǔ)上加入K近鄰相似度信息，隨著迭代次數(shù)的增加以及正則化系數(shù)的調(diào)整，提高了推薦算法的準(zhǔn)確性，也減少了推薦的時間，但由于算法過于依賴用戶數(shù)據(jù)，存在數(shù)據(jù)稀疏的問題，是在后續(xù)研究中需要補(bǔ)充和完善的地方。

參考文獻(xiàn)：

[1] Amatriain X. Past， Present， and Future of Recommender Systems： An Industry Perspective[C]//International Conference on Intelligent User Interfaces. ACM， 2016：1-1.

[2] DietmarJannach. 推薦系統(tǒng)[M]. 人民郵電出版社， 2013：1-8.

[3] 李改， 李磊. 基于矩陣分解的協(xié)同過濾算法[J]. 計算機(jī)工程與應(yīng)用，2011，47（30）：4-7.

[4] 楊陽，向陽，熊磊.基于矩陣分解與用戶近鄰模型的協(xié)同過濾推薦算法.計算機(jī)應(yīng)用，201232（2）：395-398

[5] 王振軍， 黃瑞章. 基于Spark的矩陣分解與最近鄰融合的推薦算法[J]. 計算機(jī)系統(tǒng)應(yīng)用， 2017， 26（4）：124-129.

[6] Tom White. Hadoop權(quán)威指南[M]. 3版.清華大學(xué)出版社， 2015：205-240.

[7] 杜江， 張錚， 張杰鑫，等. MapReduce并行編程模型研究綜述[J]. 計算機(jī)科學(xué)， 2015，42（S1）：2635-2642.

[8] 高彥杰. Spark大數(shù)據(jù)處理：技術(shù)、應(yīng)用與性能優(yōu)化[M]. 機(jī)械工業(yè)出版社， 2014.

[9] Zhou Y， Wilkinson D， Schreiber R， et al. Large-Scale Parallel Collaborative Filtering for the Netflix Prize[C]// Algorithmic Aspects in Information and Management， International Conference， Aaim 2008，Shanghai， China， June 23-25， 2008. Proceedings. DBLP， 2008：337-348.

[10] 李衛(wèi)平， 楊杰. 基于隨機(jī)梯度矩陣分解的社會網(wǎng)絡(luò)推薦算法[J].計算機(jī)應(yīng)用研究，2014，31（6）：1654-1656.