劉佳耀 王佳斌

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

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

中圖分類號(hào)：TP391.1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ā)展，各種信息也呈爆炸性增長(zhǎng)，接踵而來(lái)的是出現(xiàn)了“信息過(guò)載”的問(wèn)題。為了解決這個(gè)問(wèn)題，推薦系統(tǒng)由此產(chǎn)生，推薦系統(tǒng)[1]可以通過(guò)用戶對(duì)各種商品的評(píng)分或用戶以前的瀏覽記錄，來(lái)為用戶推薦他們所需的信息。協(xié)同過(guò)濾[2]算法是推薦系統(tǒng)中運(yùn)用最常用的算法，但是在大數(shù)據(jù)背景下隨著用戶和項(xiàng)目數(shù)量的不斷增長(zhǎng)，用戶-項(xiàng)目矩陣的稀疏和單機(jī)上的瓶頸導(dǎo)致推薦質(zhì)量和準(zhǔn)確性不斷下降。

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

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

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

2 Spark計(jì)算框架

2.1 搭建Spark平臺(tái)

本實(shí)驗(yàn)的Spark平臺(tái)采用的VMware Workstation的三臺(tái)虛擬機(jī)來(lái)搭建，包含一個(gè)主節(jié)點(diǎn)和三個(gè)從節(jié)點(diǎn)，三個(gè)節(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。在三臺(tái)虛擬機(jī)上分別配置好這些軟件，然后先啟動(dòng)yarn，在yarn的基礎(chǔ)上再啟動(dòng)spark。

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

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

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

3.1 矩陣分解思想

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

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

[rui=puqi] （1）

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

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

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

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

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

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

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

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

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

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

[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)練模型求解物品矩陣和用戶矩陣的過(guò)程中，發(fā)現(xiàn)忽略了用戶或物品相似度，由此進(jìn)一步考慮將用戶或物品相似度與損失函數(shù)進(jìn)行加權(quán)以縮小系統(tǒng)誤差，得到K近鄰ALS推薦模型，相似度誤差計(jì)算如下：

[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表示某一個(gè)特征（或隱含因子），上述公式從相似物品或用戶的信息進(jìn)行用戶-物品評(píng)分誤差的計(jì)算，并將得到的相似度誤差信息加權(quán)到基于ALS的評(píng)分誤差預(yù)測(cè)中，得到改進(jìn)算法，K近鄰ALS模型的損失函數(shù)計(jì)算公式如下：

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

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

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

4.1 運(yùn)行時(shí)間

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

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

4.2 平均絕對(duì)誤差（MAE）

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

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

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

4.3 算法對(duì)比

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

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

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

5 總結(jié)

在當(dāng)前信息數(shù)據(jù)量以爆炸式增長(zhǎng)的環(huán)境下，提出了把推薦算法和大數(shù)據(jù)平臺(tái)相結(jié)合來(lái)提高推薦效率，通過(guò)對(duì)MAE值的觀察，在ALS算法基礎(chǔ)上加入K近鄰相似度信息，隨著迭代次數(shù)的增加以及正則化系數(shù)的調(diào)整，提高了推薦算法的準(zhǔn)確性，也減少了推薦的時(shí)間，但由于算法過(guò)于依賴用戶數(shù)據(jù)，存在數(shù)據(jù)稀疏的問(wèn)題，是在后續(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é)同過(guò)濾算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2011，47（30）：4-7.

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

[5] 王振軍， 黃瑞章. 基于Spark的矩陣分解與最近鄰融合的推薦算法[J]. 計(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ì)算機(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ī)梯度矩陣分解的社會(huì)網(wǎng)絡(luò)推薦算法[J].計(jì)算機(jī)應(yīng)用研究，2014，31（6）：1654-1656.