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

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

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

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

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

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

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

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

1 混合推薦模型

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

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

圖1 模型基本環節圖

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

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

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

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

地點推薦模型的在線推薦環節根據用戶輸入的約束條件將符合條件的地點推薦給用戶,這個過程跟特定的用戶有關.如圖2所示.

圖2 在線推薦環節流程圖

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

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

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

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

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

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

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

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

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

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

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

表1 用戶-地點簽到矩陣

表2 地點-屬性矩陣

表3 用戶-屬性偏好矩陣

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

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

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

1.1 基于用戶-地點屬性偏好的數據填充方式

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

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

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

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

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

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

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

2 Spark計算并行化

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

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

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

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

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

3 實驗與分析

3.1 實驗環境

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

JAVA環境為JDK1.8.0_201,分布式系統基礎架構為Hadoop2.7.3;大數據處理并行框架為Spark2.4.0;推薦算法開發語言為Python2.7.12.

3.2 數據來源與評價指標

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

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

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

3.3 實驗結果分析

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

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

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

圖4 實驗結果

4 總結

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