基于Spark并行化改進混合地點推薦①

蒲 鑫,孟祥茹,高 岑,王美吉,劉錦揚

1(中國科學院大學 計算機科學與技術(shù)學院,北京 100049)

2(中國科學院 沈陽計算技術(shù)研究所,沈陽 110168)

3(成都信息工程大學 統(tǒng)計學院,成都 610103)

在信息爆炸的時代,從海量數(shù)據(jù)中找到用戶感興趣的信息是一件非常困難的事情,推薦系統(tǒng)的任務(wù)就是挖掘數(shù)據(jù)中所隱藏的模式.基于位置服務(wù)的應(yīng)用在移動設(shè)備上也快速發(fā)展,這些應(yīng)用通過定位接口采樣了大量的地點簽到數(shù)據(jù)[1].從而實現(xiàn)面向用戶的地點推薦.

本文研究的主要內(nèi)容就是地點推薦算法.根據(jù)利用的信息不同,推薦算法可以分為基于內(nèi)容[2]和基于協(xié)同過濾[3]的推薦兩類算法.基于內(nèi)容的推薦算法提取用戶或者項目的特征構(gòu)建用戶偏好文檔,通過計算項目和用戶偏好文檔的相似度來推薦,推薦的是滿足用戶本身的偏好.與基于內(nèi)容的推薦算法不同,基于協(xié)同過濾的推薦算法考慮的是與他相似的用戶的意見,它的核心思想是相似的用戶有類似的偏好.這兩類推薦算法有各自的優(yōu)缺點.基于內(nèi)容的推薦算法能夠很好地反映用戶對項目的偏好,可以為具有特定愛好的用戶推薦,但用戶偏好文檔根據(jù)用戶的歷史數(shù)據(jù)構(gòu)建,不能發(fā)現(xiàn)潛在偏好;而基于協(xié)同過濾的推薦算法使用相似用戶預(yù)測評分,利用其他用戶的意見,可以發(fā)現(xiàn)潛在偏好,但存在冷啟動[4,5]、稀疏性、推薦效果依賴于已評分項的多少和準確性的問題.

根據(jù)以上分析,本文提出了一個綜合利用這兩種推薦模型的地點推薦模型,綜合利用了兩種推薦算法都有各自的優(yōu)點.此模型基于用戶偏好文檔和用戶地點簽到矩陣,使用基于內(nèi)容的推薦算法滿足用戶的個性化需求,而基于協(xié)同過濾的推薦算法則可以利用其他用戶的意見,發(fā)掘用戶的潛在偏好.同時,同時為應(yīng)對海量數(shù)據(jù)的挑戰(zhàn),使用Spark平臺完成模型的并行化訓練.

1 混合推薦模型

冷啟動[6]和稀疏性問題是地點推薦最突出的問題.在地點推薦中,協(xié)同過濾算法是基于用戶-地點簽到矩陣實現(xiàn)的.不同于傳統(tǒng)商品推薦,地點推薦中的大量用戶訪問的地點非常有限,而且用戶的簽到記錄中沒有負樣本,從而導(dǎo)致用戶-地點簽到矩陣稀疏性非常高.再者,如果僅僅只使用協(xié)同過濾算法來實現(xiàn)推薦系統(tǒng),則只會利用到用戶的歷史偏好,也會有冷啟動和個性化程度低的問題.使用基于內(nèi)容和基于協(xié)同過濾的混合推薦算法不僅能有效改善稀疏性,而且也能兼顧個性化推薦.本文選擇基于用戶屬性偏好文檔和用戶-地點評分矩陣模型組合的方式,前者容易計算,后者的改進填充方法可改善稀疏性問題.

本文提出的推薦模型,結(jié)合兩種推薦算法的優(yōu)勢,利用個人偏好和地點的屬性信息來填充簽到矩陣,大大改善稀疏性和有效性;利用用戶的輸入約束條件實現(xiàn)了個性化推薦,使用協(xié)同過濾考慮了相似用戶的意見.模型的推薦過程分為兩個子過程:基于內(nèi)容推薦和基于協(xié)同過濾的推薦環(huán)節(jié).整個系統(tǒng)的各個流程如圖1所示.

圖1 模型基本環(huán)節(jié)圖

本文提出的地點推薦模型分為準備環(huán)節(jié)、離線計算和在線推薦3個基本環(huán)節(jié):

(1)準備環(huán)節(jié):為地點推薦模型的訓練準備數(shù)據(jù).原始數(shù)據(jù)經(jīng)過ETL加工清洗,得到目標數(shù)據(jù),主要是地點簽到矩陣、用戶偏好文檔.

(2)離線計算:主要實現(xiàn)模型的建立.首先由地點-簽到矩陣計算出兩個矩陣:地點-屬性和用戶-屬性矩陣,然后用這兩個矩陣采用基于地點屬性的矩陣填充方法填充用戶-地點簽到矩陣,最后訓練基于ALS的協(xié)同過濾算法模型.

(3)在線推薦:在線環(huán)節(jié)負責搜集實時的場景,如用戶的輸入約束,利用訓練好的模型做推薦.

地點推薦模型的在線推薦環(huán)節(jié)根據(jù)用戶輸入的約束條件將符合條件的地點推薦給用戶,這個過程跟特定的用戶有關(guān).如圖2所示.

圖2 在線推薦環(huán)節(jié)流程圖

(1)首先根據(jù)用戶輸入約束交互式約束IC,這是用戶感興趣的地點的屬性要求.如果用戶有輸入則進入(2).否則進入(4).

(2)將用戶的IC向量化,轉(zhuǎn)換成屬性約束向量CV.

(3)根據(jù)得到CV結(jié)合地點-屬性矩陣選出滿足一定條件的地點集合C,進入(5).

(4)根據(jù)用戶偏好文檔結(jié)合地點-屬性矩陣選出滿足一定條件的地點集合C,進入(5).

(5)使用訓練好的模型為集合C作最終的評分,將前k個地點作為最終結(jié)果返回.

系統(tǒng)首先讀取用戶輸入的條件,然后將用戶的輸入向量化,再利用建立的地點-屬性矩陣就可以篩選出候選集合C,計算方式就是將約束向量與代表地點的屬性向量相乘,如果結(jié)果不為0就是滿足條件的地點;沒有輸入約束的條件下,使用用戶偏好文檔來構(gòu)成向量,最后將滿足結(jié)果的地點組成集合C.本文使用的倒查表的方式實現(xiàn)的用戶偏好文檔,描述了用戶對于地點的屬性偏好,倒查表建立的基礎(chǔ)是用戶的地點描述信息,示意圖如圖3所示.

圖3 描述用戶偏好的倒查表

如圖3所示,模型將用戶地點簽到數(shù)據(jù)中的地點描述信息轉(zhuǎn)換為用戶屬性偏好,圖中的橢圓代表標簽屬性,直角矩形代表的是用戶,圓角矩形代表用戶的簽到描述信息.

在計算對候選地點的評分時,直接使用的是離線階段訓練好的ALS模型計算評分并排序.評分計算公式如下:

式(1)中,PU,I表示用戶U對地點I的評分,PU模型中代表用戶U的隱含偏好向量,QI表示地點I的隱含特征向量.K表示模型使用的隱含因子數(shù).

模型除了構(gòu)建用戶的地點屬性偏好文檔和用戶-地點簽到矩陣(表1)外,還有2個矩陣,分別是地點-屬性矩陣(表2)、用戶-屬性偏好矩陣(表3),地點-屬性矩陣表明了一個地點所具有的屬性信息,用戶-屬性矩陣代表了用戶對地點屬性的偏好情況,通過這兩個矩陣來填充用戶-簽到矩陣.總體的流程是根據(jù)輸入的約束得到用戶的屬性偏好,根據(jù)偏好得到相應(yīng)滿足的地點集合C,從這些地點中使用基于模型的協(xié)同過濾計算出評分并最終地點給用戶,因此本文提到的模型前階段使用的基于內(nèi)容的推薦,實現(xiàn)了個性化需求,后面的環(huán)節(jié)使用的協(xié)同過濾,來挖掘用戶的歷史偏好.

表1 用戶-地點簽到矩陣

表2 地點-屬性矩陣

表3 用戶-屬性偏好矩陣

表1中的數(shù)字表示用戶對地點的評分,也就是簽到次數(shù).“0”表示用戶沒有在該地點簽到過.鑒于每個用戶的簽到頻率不一致,這里沒有采取統(tǒng)一的歸一化處理.

表2中的數(shù)字”1”表示地點具有該屬性,“0”表示該地點沒有這個屬性.通過分析用戶地點評分及地點所具有的屬性信息,可以得到用戶描述用戶對一個具體的地點屬性的興趣度的用戶-地點屬性偏好矩陣,如表3所示.

模型會維持這3個矩陣,地點-屬性矩陣的信息來自于用戶地點簽到信息,再根據(jù)用戶-地點簽到矩陣和地點-屬性矩陣推算出用戶-屬性偏好矩陣,使用用戶-屬性偏好矩陣來填充用戶-地點簽到矩陣.由于用戶在簽到時都會帶有地點的標簽信息,從而導(dǎo)致地點的屬性相比之下容易獲得,通過用戶對地點屬性評分可以預(yù)測用戶對具有該屬性的地點的評分,具體的計算流程如1.1節(jié)所述,這樣極大的解決了數(shù)據(jù)稀疏的問題,提高了推薦的準確度.

1.1 基于用戶-地點屬性偏好的數(shù)據(jù)填充方式

在地點推薦中的一個很大問題就是地點數(shù)量很大,造成評分矩陣很稀疏,目前很多填充方法都沒有考慮用戶的偏好,缺乏可靠性.在數(shù)據(jù)很稀疏的情況下能夠造成準確率嚴重下降,鑒于地點推薦數(shù)據(jù)的特殊性,本文利用了用戶簽到數(shù)據(jù)中的地點的屬性標簽,利用這些數(shù)據(jù)可以提取出用戶的屬性偏好.如表3所示,用戶-地點屬性矩陣就是用戶的偏好的體現(xiàn).這也是用戶歷史偏好的體現(xiàn),利用了用戶的偏好的填充方法能取得更好的推薦效果.

為了利用用戶的歷史偏好,需要從用戶-地點評分矩陣中總結(jié)出用戶的地點屬性偏好,這就需要利用地點的屬性信息,所以本文所提的推薦模型建立了地點-屬性矩陣,此矩陣容易建立,因為地點簽到數(shù)據(jù)中包含地點的屬性信息,如表3.也就是根據(jù)表1的用戶-地點簽到矩陣和表2的地點-屬性矩陣計算出表3的用戶-屬性評分矩陣,再利用表3的數(shù)據(jù)填充表1的空白項.具體計算過程如下:

計算方法如式(2)所示.表1中的數(shù)字為用戶對地點的簽到次數(shù),表2中1表示地點具有該屬性.計算方法如式(1),然后根據(jù)用戶對地點屬性的評分對用戶-地點矩陣進行填充.

式(2)中,au為用戶u對地點屬性a的評分;Iu,a為用戶u已評分且包含屬性a的地點集合,為該集合中的元素個數(shù);Ru,i為用戶u對地點i的評分.通過計算得到用戶-地點屬性偏好矩陣,如表3.

在對一個用戶評分缺失項進行填充時需要充分考慮地點的屬性信息,使用地點的屬性評分和用戶平均評分的綜合,具體計算式(3):

其中,ru,i表示用戶u對地點i的評分,也就是需要填充的評分;Ai表示地點i包含的屬性集合,|Ai|為該集合的元素個數(shù);ru,a為用戶u對屬性a的評分;Q表示用戶的評分項目中除去Ai的集合,bj為用戶對地點j的評分;λ參數(shù)表示用戶歷史偏好和當前要填充的地點的相似度,此值越高代表利用地點屬性信息的程度越高,引入λ的目的是綜合考慮當一個地點的屬性標簽也很少時的情況,這時還是需要引入用戶的平均簽到次數(shù)作為評分.具體計算公式如式(4):

其中,Li表示地點i的屬性集合,Au表示用戶-屬性矩陣中用戶u的偏好屬性集合,A表示整個系統(tǒng)的地點屬性集合,當?shù)攸c的屬性和用戶的偏好越相近時 λ越大.按照步驟可以計算出用戶U=4對L2的評分為2.

2 Spark計算并行化

Spark是一個基于內(nèi)存計算的開源的集群計算框架.與MapReduce相比,它具有負載均衡、自動容錯和容易擴展等優(yōu)點.Spark的核心是RDD (Resilient Distributed Datasets),他是一種只讀的并行數(shù)據(jù)結(jié)構(gòu),具有很高的可擴放性.Spark包括的組件有:Spark SQL、Spark streaming、Mlib和GraphX,這些組件使得Spark形成大數(shù)據(jù)一站式解決平臺[7].

Spark MLlib當前支持基于模型的協(xié)同過濾,也是一種隱語義模型[8],其核心問題是矩陣分解,用戶和項目通過一小組隱語義因子進行表達,并且這些因子也用于預(yù)測缺失的元素.MLlib使用交替最小二乘法(ALS)來學習這些隱性因子.是將用戶-項目評分矩陣分解為用戶-隱含特征偏好矩陣和隱含特征-項目矩陣,即:

其中,R(m×n)代表用戶-項目評分矩陣,X(m×k)代表用戶-隱含特征偏好矩陣,Y(k×n)表示隱含特征-項目矩陣,其中k=min(m,n),為了使X和Y的乘積盡可能逼近R,采用誤差平方和最小作為損失函數(shù):

式(6)中,表示第u個用戶對第i個項目的評分,本文中的用戶在此地點的簽到次數(shù),xu表示用戶u的偏好特征向量,yi表示地點i的隱含特征向量,為用戶u對地點評分的近似,為防止過擬合,加入正則化項:

采用梯度下降迭代計算,當均方根誤差變化小于指定閾值或迭代次數(shù)達到一定時,迭代結(jié)束.ALS算法功能強大,效果理想而且被證明相對容易并行化,所以模型特別適合在Spark框架下訓練.

3 實驗與分析

3.1 實驗環(huán)境

本文的實驗環(huán)境:采用Hadoop HDFS作為底層存儲、Hadoop YARN作為集群資源管理的Spark分布式集群平臺.主機處理器:Intel(R)Core(TM)i7-7700 CPU,核心數(shù)為8;內(nèi)存:DDR4 32 GB內(nèi)存.通過VMware實現(xiàn)分布式平臺.平臺由4個CentOS操作系統(tǒng)的節(jié)點組成,1個節(jié)點為Master節(jié)點,3個節(jié)點為Slave節(jié)點.

JAVA環(huán)境為JDK1.8.0_201,分布式系統(tǒng)基礎(chǔ)架構(gòu)為Hadoop2.7.3;大數(shù)據(jù)處理并行框架為Spark2.4.0;推薦算法開發(fā)語言為Python2.7.12.

3.2 數(shù)據(jù)來源與評價指標

Foursquare是著名的社交網(wǎng)站,為用戶提供了基于位置的簽到服務(wù).使用Foursquare,用戶能在任何一個地點簽到,比如說地點是餐館,公園等.每一個簽到發(fā)布后,Foursquare的簽到會包含位置的物理位置和用戶的描繪信息,如地點評價等.由于Foursquare網(wǎng)站中,不提供數(shù)據(jù)的下載,所以本文利用已有的Twitter,Facebook賬號與Foursquare相連.通過Twitter提供的API接口,抓取簽到信息.本文抓取了從2017年10月到2018年12月的15 102 513條簽到數(shù)據(jù).共有8690個用戶,地點數(shù)目75 662個.將數(shù)據(jù)集按照3∶1的比例劃分為訓練集和測試集.

為了評估推薦算法的準確度,選擇了推薦系統(tǒng)中常用的平均絕對誤差(MAE)和歸一化折損累計增益(NDCG)作為評價指標[9],MAE反映的是預(yù)測值和真實值間的差距,NDCG則是反映對多個候選項目的預(yù)測排序情況的優(yōu)劣,計算方式如式(8)所示.

式中,NDCGu(u)為用戶u候選項目預(yù)測值排序的NCGn(u)值比上實際情況的 m axDCGn(u)值,DCGn(u)值由式(9)計算得出.

3.3 實驗結(jié)果分析

本文選擇了幾個典型的算法作為比較,選擇的算法為傳統(tǒng)的混合協(xié)同過濾算法(HCFR)、基于受限波爾茲曼機的推薦算法(RBM)[10].

3 種模型在MAE和NDCG這兩個指標上的實驗效果如圖4所示.

如圖4所示,圖中橫坐標表示推薦的結(jié)果數(shù),縱坐標是相應(yīng)的測評值,可以看出,本文所提出的改進的推薦算法在表現(xiàn)效果上都要高于其他兩個對比算法,表現(xiàn)最差的是傳統(tǒng)的協(xié)同過濾算法,這是因為HCFR適用于商品推薦,沒有考慮地點推薦的特殊性,也沒有在數(shù)據(jù)填充上做改進.本文模型所使用的算法融合了用戶的歷史偏好和個性化需求,而且使用了用戶的偏好信息來填充矩陣,填充的結(jié)果更加有效,大大地改善了數(shù)據(jù)稀疏性問題,相比于其他兩種算法,更能體現(xiàn)地點的特征,更適合地點推薦場景.

圖4 實驗結(jié)果

4 總結(jié)

本文提出了一種融合用戶當前需求和歷史偏好的個性化混合地點推薦系統(tǒng),并在推薦的核心階段做了改進,通過提取用戶對地點的屬性偏好,填充用戶-地點簽到矩陣,有效地改善了數(shù)據(jù)稀疏問題;在協(xié)同過濾階段采用了基于模型的地協(xié)同過濾算法,最后將IHLR和HCFR和RBM進行了對比,表明本文所提的IHLR方法在效果上能表現(xiàn)得更好,接下來的工作是將用戶之間的好友關(guān)系用到系統(tǒng)中,使得推薦結(jié)果更加準確,此外,系統(tǒng)運行在流行的Spark分布式平臺,適合做海量數(shù)據(jù)的推薦任務(wù).