蒲 鑫,孟祥茹,高 岑,王美吉,劉錦揚(yáng)

1(中國(guó)科學(xué)院大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,北京 100049)

2(中國(guó)科學(xué)院 沈陽(yáng)計(jì)算技術(shù)研究所,沈陽(yáng) 110168)

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

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

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

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

1 混合推薦模型

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

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

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

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

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

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

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

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

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

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

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

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

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

(5)使用訓(xùn)練好的模型為集合C作最終的評(píng)分,將前k個(gè)地點(diǎn)作為最終結(jié)果返回.

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

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

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

在計(jì)算對(duì)候選地點(diǎn)的評(píng)分時(shí),直接使用的是離線階段訓(xùn)練好的ALS模型計(jì)算評(píng)分并排序.評(píng)分計(jì)算公式如下:

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

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

表1 用戶-地點(diǎn)簽到矩陣

表2 地點(diǎn)-屬性矩陣

表3 用戶-屬性偏好矩陣

表1中的數(shù)字表示用戶對(duì)地點(diǎn)的評(píng)分,也就是簽到次數(shù).“0”表示用戶沒(méi)有在該地點(diǎn)簽到過(guò).鑒于每個(gè)用戶的簽到頻率不一致,這里沒(méi)有采取統(tǒng)一的歸一化處理.

表2中的數(shù)字”1”表示地點(diǎn)具有該屬性,“0”表示該地點(diǎn)沒(méi)有這個(gè)屬性.通過(guò)分析用戶地點(diǎn)評(píng)分及地點(diǎn)所具有的屬性信息,可以得到用戶描述用戶對(duì)一個(gè)具體的地點(diǎn)屬性的興趣度的用戶-地點(diǎn)屬性偏好矩陣,如表3所示.

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

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

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

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

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

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

在對(duì)一個(gè)用戶評(píng)分缺失項(xiàng)進(jìn)行填充時(shí)需要充分考慮地點(diǎn)的屬性信息,使用地點(diǎn)的屬性評(píng)分和用戶平均評(píng)分的綜合,具體計(jì)算式(3):

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

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

2 Spark計(jì)算并行化

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

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

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

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

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境

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

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

3.2 數(shù)據(jù)來(lái)源與評(píng)價(jià)指標(biāo)

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

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

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

3.3 實(shí)驗(yàn)結(jié)果分析

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

3 種模型在MAE和NDCG這兩個(gè)指標(biāo)上的實(shí)驗(yàn)效果如圖4所示.

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

圖4 實(shí)驗(yàn)結(jié)果

4 總結(jié)

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