戴 琳,孟祥武,張玉潔,紀威宇

1(智能通信軟件與多媒體北京市重點實驗室(北京郵電大學),北京 100876)

2(北京郵電大學 計算機學院,北京 100876)

通訊作者:孟祥武,E-mail:mengxw@bupt.edu.cn

隨著GPS 在手持設備的廣泛應用,基于位置社交網絡[1-5]的服務應運而生,并且已經達到了一種前所未有的水平.在基于位置社交網絡的服務上,用戶可以簽到自己的位置,并分享自己的評價.推薦系統(tǒng)通過用戶的這些隱式反饋(簽到信息)和顯式反饋(用戶的評分和評論)挖掘用戶的偏好,就可以為用戶生成興趣點推薦列表.這種基于位置社交網絡的興趣點推薦系統(tǒng)有很多,典型的包括美國最大的點評網站 Yelp(https://www.yelp.com/sf)、基于用戶地理位置的手機服務網站 Foursquare(https://foursquare.com/)以及國內的大眾點評(http://www.dianping.com/)等,這些網站通過分析用戶簽到及評論信息等,挖掘用戶個性化偏好,為用戶提供合適的選擇,從而為用戶帶來便利,同時為商家?guī)砜捎^的利益.本文所研究的餐館推薦是興趣點推薦中一個典型的應用.

餐館推薦可以利用多種數據信息挖掘用戶的飲食偏好,為用戶生成餐館推薦列表.從文獻[6,7]可知:除了用戶的顯式反饋(評分、評論等)和隱式反饋(簽到)直接反映了用戶的偏好,還有以下因素也影響用戶的餐館選擇:(1)時間上下文,在不同時間段用戶的飲食偏好是不同的;(2)地理上下文,用戶通常會選擇活動區(qū)域附近的餐館;(3)用戶的人口統(tǒng)計信息,例如,不同年齡或不同性別的用戶對于餐館的需求是不同的,有的人看中服務,有的人看中環(huán)境等;(4)餐館的屬性信息,例如,用戶對于餐館的選擇通常集中在某幾類風格.因此,如果能夠同時考慮這些數據信息,并有效地進行整合,挖掘這些信息的最大價值,就能夠提高推薦精度.

文獻[8]考慮了用戶行為的空間聚類現象,提出一種結合地理位置信息的矩陣分解模型,該模型在加權矩陣分解的基礎上引入了地理上下文,將用戶的活動區(qū)域向量融合到用戶隱式空間中,將興趣點的區(qū)域影響向量融合到興趣點隱式空間中,通過這種融合,有效地解決了矩陣稀疏性問題,從而提高了推薦準確度;但是該模型沒有考慮時間上下文信息,也沒有考慮其他元數據信息.

文獻[6]基于用戶的隱式反饋提出了一種隱式偏好模型,該模型同時考慮了時間上下文、地理上下文以及餐館屬性信息,分別利用概率張量分解和邏輯回歸獲得用戶的隱式偏好.該方法能夠很好地提高推薦準確度,但是該方法是分別對各數據信息相對獨立地進行分析,缺乏對所有數據信息進行有效地融合,且時間復雜度高.

文獻[9]考慮到用戶存在一些依賴關系,而用戶的這些關系會相互影響用戶的偏好,因此,作者提出了一種概率關系矩陣分解模型.該模型的創(chuàng)新點在于不再僅僅只考慮用戶的社交關系,而通過學習用戶的依賴提高了推薦準確度,但是該方法缺乏對時間上下文和地理上下文的研究.

文獻[10]為了解決下一個興趣點的推薦問題,提出了一種兩步策略的方法:首先,基于用戶簽到的興趣點種類構建三維張量,并提出一種新的優(yōu)化準則(LBPR)對張量優(yōu)化學習,進而得到預測的興趣點種類;然后,根據預測的興趣點種類獲得位置列表.該方法的推薦效果要優(yōu)于目前存在的方法,但是該方法沒有考慮時間上下文的影響,也缺乏對其他元數據信息的研究,例如用戶信息或者興趣點信息等.

文獻[11]認為,用戶的興趣點會隨著時間和當前位置的變化而變化,因此,作者提出了兩步策略的方法進行興趣點的推薦:首先,根據用戶簽到的興趣點種類和時間上下文構建四維張量,預測用戶偏好的下一個興趣點種類;然后,基于預測的興趣點種類進一步獲得位置列表.該模型的創(chuàng)新點在于既考慮了時間和位置,還降低了數據稀疏性的影響,但是缺乏對其他元數據信息的研究.

為了同時考慮多種數據信息,并進行有效的融合,本文提出了一種融合多種數據信息的餐館推薦模型(a restaurant recommendation model with multiple information fusion,簡稱RRMIF).該模型首先利用簽到信息和時間上下文構建“用戶-餐館-時間片”的三維張量,同時,利用其他數據信息挖掘若干用戶相似關系矩陣和餐館相似關系矩陣;然后,在概率張量分解模型[12]的基礎上同時對這些關系矩陣進行分解,并保證張量和矩陣分解后有共同的低維隱式因子矩陣;最后,利用BPR[13,14]優(yōu)化準則和梯度下降算法進行模型求解.可以看出,該模型將多種數據信息通過用戶、餐館以及時間片的隱式因子矩陣進行了有效地融合,這也就是本文提出的模型與目前存在的模型最大的區(qū)別.值得注意的是,為了降低模型的復雜度,本文提出的模型沒有考慮用戶的顯式反饋.本文的貢獻主要包括以下幾點.

1)與現有研究不同,本文沒有簡單地將時間上下文按照小時制劃分為24 個時間片,而通過K-means 聚類算法[15]將一天分為4 個用餐時間段,這樣不僅對用戶的用餐行為進行了聚類,還降低了模型的復雜度;

2)本文基于地理上下文、餐館屬性信息構建了兩種餐館相似關系矩陣,基于用戶人口統(tǒng)計信息構建了用戶相似關系矩陣;進而提出一種融合多種數據信息的餐館推薦模型,該模型是在概率張量分解模型的基礎上同時對用戶相似關系和餐館相似關系進行分解,它以用戶和餐館的隱式因子作為橋梁,更好地融入了多種數據信息;最后,采用BPR 優(yōu)化準則和梯度下降算法進行模型求解;

3)實驗在兩種真實的數據集上進行,主要包括以下4 個部分:1)比較本文提出的模型和現有模型的推薦效果;2)研究多種數據信息對于推薦效果的影響,包括時間上下文、地理上下文、餐館屬性信息以及用戶人口統(tǒng)計信息;3)研究本文提出的模型在不同稀疏度數據集的表現,并與現有模型作比較;4)研究本文提出的模型的運行時間,并與現有模型作比較.實驗結果表明:相比于目前存在的餐館推薦模型,本文提出的餐館推薦模型有著更好的推薦效果和可接受的運行時間,并且緩解了數據稀疏性對推薦效果的影響.

本文第1 節(jié)介紹餐館推薦的相關工作,包括興趣點推薦和餐館推薦.第2 節(jié)介紹多種數據信息的研究,提出一種融合多種數據信息的餐館推薦模型.第3 節(jié)介紹實驗的相關設置及實驗結果分析.第4 節(jié)是全文的總結.

1 相關工作

1.1 興趣點推薦

興趣點推薦[16]作為位置社交網絡的一個重要應用,已經成為學術界和工業(yè)界的一個熱門課題.它給用戶和商家都帶來了前所未有的便利和好處:對于用戶而言,興趣點推薦系統(tǒng)能夠將其從海量的興趣點搜索中解放出來,根據他們的歷史數據挖掘其個性化偏好,為他們推薦合適的興趣點;另一方面,對于商家而言,可以吸引大量感興趣的用戶,持續(xù)提高經濟效益.

用戶隱式反饋的研究是當前興趣點推薦的一個熱點,矩陣分解模型(MF)[17]就常常被用于隱式反饋數據的處理.該模型基于用戶的歷史簽到數據構建“用戶-興趣點”的簽到矩陣,再通過對簽到矩陣的分解,得到用戶隱式因子矩陣和興趣點隱式因子矩陣,再利用這些隱式因子矩陣預測用戶對于興趣點的評分,進而為用戶生成推薦列表.雖然該模型有著較高的準確率,且模型簡單,但是隱式反饋中只有正反饋,當用戶在某興趣點沒有簽到時,并不能反映用戶就不喜歡該興趣點,傳統(tǒng)的矩陣分解沒有很好地解決在這一問題.為了從隱式反饋中獲得額外的信息,Hu 等人[18]提出了加權矩陣分解模型,該模型在概率矩陣分解的基礎上,通過分析用戶的隱式反饋,得到正反饋和負反饋的置信水平,從而使得矩陣分解模型更好地應用于隱式反饋的研究.但是由于“用戶-興趣點”矩陣的稀疏性,該方法依舊面臨著很大的挑戰(zhàn).為了解決稀疏性問題,Lian 等人[8]提出了結合地理上下文的矩陣分解模型(GeoMF).該模型在加權矩陣分解的基礎上將地理上下文引入模型,讓用戶的活動區(qū)域向量融合到用戶隱式空間中,將興趣點的區(qū)域影響向量融合到興趣點隱式空間中.通過這種融合,不僅考慮了用戶行為的空間聚類現象,還有效地解決了矩陣稀疏性問題.但是該模型僅僅只考慮了用戶的簽到信息和地理上下文,而沒有考慮用戶的評論信息以及時間上下文信息.為了融合用戶的評論信息,Li 等人[19]提出了一種多方面考慮的興趣點推薦系統(tǒng).該系統(tǒng)從用戶對于興趣點的評論中學習用戶的偏好以及商家的質量標簽,再結合用戶評分矩陣分解得到的用戶特征矩陣和商家特征矩陣,預測目標用戶對于其他興趣點的效用評分,最后生成推薦列表.該系統(tǒng)很好地結合了用戶的評論信息和評分信息,提高了推薦的精度.但是該系統(tǒng)沒有考慮到時間上下文信息.考慮到時間信息對于興趣點推薦重要性,Luan 等人[20]提出了基于張量分解的協同過濾模型.該模型利用用戶的簽到行為構建一個“用戶-興趣點-時間片”的三維張量,同時從不同角度提取3 個特征矩陣,例如“用戶-興趣點類別”或者“時間片-用戶”等特征矩陣,然后利用特征矩陣協同地對張量進行分解,并使得目標函數最小,最后得到預測張量,通過預測張量就可以為目標用戶在某一時間對生成興趣點推薦列表.雖然該模型考慮了時間因素,提高了推薦準確度,但是該模型沒有考慮地理上下文.

1.2 餐館推薦

目前,國內對于餐館推薦研究得不多,而國外則相對較多.例如,Fu 等人[21]提出了一種考慮多種評分數據,并融合地理上下文以及用戶和餐館特征信息的餐館推薦模型.該模型同時對多種評分矩陣進行分解,并利用用戶和餐館的位置信息構建位置相關性,利用用戶和餐館特征信息構建特征相關性,最后利用分解得到的隱式因子矩陣和這兩種相關性得到用戶對餐館的預測評分.由于融合了多種評分數據,該模型提高了推薦準確度,但是該模型沒有考慮時間上下文信息.為了融入時間上下文,Zhang 等人[6]提出了一種隱式反饋模型.該模型分別從用戶簽到信息、時間上下文以及其他數據信息獲得兩種偏好:(1)構建“用戶-餐館-時間片”的三維簽到張量,利用概率張量分解從簽到張量中獲得隱式空間的偏好;(2)利用邏輯回歸的方法分析用戶依賴于其他數據信息的偏好.最后,結合這兩種偏好得到用戶在某一時間片對餐館的預測評分,進而為目標用戶在某一時間片生成餐館推薦列表.該模型雖然同時考慮了多種數據信息,但是該模型是針對各種數據信息分別建模,沒有完全挖掘這些數據信息的價值.除了考慮以上數據信息,Sun 等人[7]還考慮了用戶的社交網絡信息,提出了一種考慮多源信息的餐館推薦模型.該模型的基本思想是:用戶的隱式偏好不僅由用戶的評分信息決定,還會受用戶社交網絡以及行為模式相似人群的影響.因此,作者在矩陣分解的框架中融入了評分信息、社交網絡信息以及行為模式信息.該模型雖然有著較高的推薦精度,但是沒有考慮餐館的屬性信息.

通過對餐館推薦相關工作的分析,本文借鑒前人的經驗,提出了一種融合多種數據信息的餐館推薦模型.該模型綜合考慮了用戶的簽到信息、時間上下文、地理上下文、餐館屬性信息以及用戶人口統(tǒng)計信息,并有效地將這些信息進行融合,從而進一步提高了推薦精度.

2 融合多種數據信息的餐館推薦模型

本節(jié)首先基于大眾點評數據集(相關介紹見第3.1 節(jié))介紹了各種數據信息的研究,通過K-means 算法將一天24 小時劃分為4 個用餐時間段,另外,基于地理上下文、基于餐館屬性信息構建兩種餐館相似關系,基于用戶人口統(tǒng)計信息構建用戶相似關系;然后提出了一種融合多種數據信息的餐館推薦模型;最后,利用BPR 優(yōu)化準則和梯度下降算法進行模型求解.

2.1 多種數據信息的研究

2.1.1 時間上下文

文獻[6,22]指出:用戶在不同時間片對于餐館的選擇是不同的,通過引入時間上下文,可以為目標用戶在不同時間片生成相對應的餐館推薦列表.因此,該文獻按照小時制將一天劃分成24 個時間片,但是這種方法存在一定的缺點,即需要在每個時間片生成推薦列表,這會導致模型復雜度增大,運行時間變長.實際上,用戶的用餐時間是存在聚類現象的,從圖1 可以看出:用戶的聚餐時間存在明顯的高峰和低谷,且高峰段大概有4 段,因此,推薦系統(tǒng)只需要在每個用餐高峰之前為用戶生成推薦列表.這樣不僅可以降低模型的復雜度,還能保證模型具有較好的推薦效果.

Fig.1 Number of diners at different time slots圖1 用戶在不同時間片的用餐人數

為了更精確地劃分用戶高峰,本文利用K-means 算法對數據集的用餐時間進行聚類分析,將用戶的用餐時間段分成4 段,聚類結果見表1.

Table 1 Clustering of dining time表1 用餐時間的聚類

從表1 可以看出,通過聚類將一天劃分為了4 個用餐時間段,每一段分別對應[0,5],[6,13],[14,18],[19,23].

2.1.2 地理上下文

在目前的興趣點推薦和餐館推薦的研究中,地理位置基本都被看做一種影響用戶選擇的重要因素.對于餐館而言,用戶通常會選擇活動區(qū)域內的餐館,那么活動區(qū)域內的餐館之間理應具有相似性.文獻[23,24]認為,距離用戶100km 以內的區(qū)域可以看做是用戶的活動區(qū)域,那么就可以近似認為餐館R與距離該餐館100km 以內的其他餐館相似,它們之間的相似表現為:用戶如果選擇了餐館R,那么該用戶也有可能選擇距離餐館R100km 以內的其他餐館.因此,基于地理位置的餐館相似關系A可以定義為公式(1):

其中,|loc(i)-loc(j)|表示餐館i和餐館j的距離.

2.1.3 餐館屬性信息

餐館的屬性信息包括餐館的名字、餐館的風格以及餐館的平均消費等,為了研究餐館的風格與用戶偏好的關系,我們隨機抽取了3 名用戶,計算了每個用戶選擇各種餐館風格的次數,如圖2 所示.需要注意的是,這里的餐館風格只是所有風格的一部分.

Fig.2 Number of selected times for different restaurant styles圖2 用戶選擇不同餐館風格的次數

從圖2 可以看出,用戶通常會多次選擇自己喜好的某類餐館用餐.因此,餐館風格相同的餐館理應具有相似性.這種相似性表現為:當用戶選擇了餐館R,那么該用戶也可能喜歡與餐館R風格相同的其他餐館.因此,基于餐館風格的餐館相似關系B可以定義為公式(2):

其中,style(i)表示餐館i的風格.

除了餐館的風格,餐館的屬性還包括餐館的平均消費,但是由于很多餐館的簽到次數少,且用戶通常很少標注消費金額,導致很多餐館的平均消費為0.經統(tǒng)計,數據集中平均消費為0 的餐館占45.1%,因此很難利用餐館的平均消費進行研究.

2.1.4 用戶人口統(tǒng)計信息

用戶的人口統(tǒng)計信息一般包括用戶的性別、年齡以及居住地,但是由于用戶的隱私保護,有的數據很難獲取.通過分析用戶歷史簽到的餐館的所在城市,可以將用戶簽到次數最多的城市看作是用戶的居住地.文獻[6]也分析了同一居住地的用戶通常會有相似的偏好,例如北京人更偏愛北京菜,湖南人更愛湖南菜.因此,可以得到基于居住地的用戶相似關系E,如公式(3)所示:

其中,residence(i)表示用戶的居住地.

2.2 模型描述

為了更好地融合用戶簽到信息、時間上下文、地理上下文、餐館屬性信息以及用戶人口統(tǒng)計信息,提高推薦精度,本文提出了一種融合多種數據信息的餐館推薦模型,如圖3 所示,其中,

·I,J,S分別表示用戶、餐館以及時間片的個數;

·A,B,C,E是可觀察量,其中:A表示基于地理位置的餐館相似關系,B表示基于餐館風格的餐館相似關系,C表示用戶的簽到張量,E表示基于居住地的用戶相似關系;

·Eiv表示用戶i與用戶v的居住地的相似性,Ajq,Bjp類似.

Fig.3 Graphical representation for a restaurant recommendation model with multiple information fusion圖3 一種融合多種數據信息的餐館推薦模型的圖表示

關于用戶簽到張量C的構建及其含義,在下文會有介紹.另外,表2 介紹了模型參數的符號及其定義.

Table 2 Symbols and definition of model parameters表2 模型參數的符號及定義

2.2.1 融合用戶簽到信息和時間上下文

根據用戶的簽到信息和時間上下文,可以構建“用戶-餐館-時間片”的三維簽到張量C∈{0,1}I×J×S,其中,I,J,S分別表示用戶、餐館以及時間片的個數,且通過第2.1.1 節(jié)的分析,時間片的個數設定為4.如果在時間片s,用戶i在餐館j用餐,則Cijs=1,這代表了用戶的正反饋;如果在時間片s,用戶i在餐館j沒有用餐,則Cijs=0,這并不一定代表用戶的負反饋,因為用戶i可能并不知道餐館j.從圖3 可以看出,通過對三維簽到張量C的分解,可以得到用戶、餐館和時間片的隱式因子矩陣,分別用UI×D,VJ×D,TS×D表示,即:每一個張量元素Cijs都可以分解為用戶i、餐館j以及時間片s的隱式特征向量,分別表示為Ui,Vj,Ts.

2.2.2 融合其他數據信息

文獻[24]認為用戶的社交關系影響了用戶行為,因此同時分解社交網絡矩陣和評分矩陣,且分解后有一個共同的用戶隱式因子矩陣.基于此思想,我們認為:用戶i的相似用戶影響了用戶i的特征向量,餐館j的相似餐館也影響了餐館j的特征向量.因此,本文同時分解基于居住地的用戶相似關系E、基于地理位置的餐館相似關系A、基于餐館風格的餐館相似關系B和用戶簽到張量C.從圖3 中可以看出,矩陣E分解為UI×D和FI×D,其中,UI×D是矩陣E和張量C分解后的共同隱式因子矩陣;矩陣A分解為VJ×D和ZJ×D,矩陣B分解為VJ×D和MJ×D,其中,VJ×D是矩陣A,B以及張量C分解后的共同隱式因子矩陣.

2.2.3 模型的基本原理

在概率張量分解模型[12]的研究中,隱式特征向量是由多元高斯分布生成的,而張量的每個元素是由高斯分布生成的,且該分布的均值是由相應的隱式因子決定的.由于本文提出的模型是在概率張量分解模型基礎上的擴展,因此該模型的基本原理可以描述如下.

4.對于基于居住地的用戶相似關系E中的每個元素,其中,表示Eiv是由均值為Ui·Fv、方差為的高斯分布生成的;

5.對于基于地理位置的餐館相似關系A中的每個元素;

6.對于基于餐館風格的餐館相似關系B中的每個元素Bjq,,其中,;

7.對于三維簽到張量C中的每個元素Cijs,,其中,.

2.3 模型參數求解

無論是張量分解還是矩陣分解,都是通過分解得到的低維隱式因子矩陣來求得預測張量或者預測矩陣,并使得預測張量和原始張量的誤差最小,使得預測矩陣和原始矩陣的誤差也最小.因此,該模型的目標函數可以定義為公式(4):

其中:L是誤差函數;Reg是防止過擬合的正則項;αC,αE,αA,αB分別是各個誤差項的比重,且αC+αE+αA+αB=1;U·V·T表示預測張量,其中,預測張量的每一項.

由于用戶的相似關系矩陣E是對稱矩陣,則U=F;同理,V=Z=M.那么,該模型的目標函數可以簡化為公式(5):

文獻[13,14]認為:推薦列表的生成實際上是一種排名問題,通過優(yōu)化項目的排名,可以優(yōu)化目標函數,使得模型更快地收斂到最優(yōu)解.因此,該文獻通過BPR 優(yōu)化準則和梯度下降算法進行求解.實驗表明,直接優(yōu)化排名的方法要明顯優(yōu)于其他方法.受此啟發(fā),本文使用BPR 優(yōu)化準則來優(yōu)化誤差函數.

BPR 優(yōu)化準則的基本思想是:當Cijs=1,Cij′s=0 時,用戶i在時間片s對于餐館j的排名要高于餐館j′.對于簽到張量C,定義一個集合PC來表示C中的排名對,如公式(6)所示:

對于L(c,U·V·T)的優(yōu)化,可以轉化為公式(7):

對于其他誤差函數的優(yōu)化,同樣采用BRP 優(yōu)化準則,分別如公式(8)～公式(10)所示:

其中,

對于正則項Reg(U,V,T),為了方便使用梯度下降算法[25]進行求解,本文采用L2-regularization[26],如公式(11)所示:

其中,λU,λV和λT是正則化參數,都是L2范數的平方.

綜上,該模型的目標函數可以轉化為公式(12):

利用梯度下降算法最大化這個目標函數,就可以得到模型參數U,V,T.需要注意的是,由于是最大化目標函數,因此必須沿著梯度方向迭代,而不是負梯度方向.對于模型參數的完整求解過程見算法1.

算法1.求解模型參數.

輸入:用戶的簽到張量C,基于居住地的用戶相似關系E,基于地理位置的餐館相似關系A,基于餐館風格和消費的餐館相似關系B,方差參數σU,σV,σT,誤差權重αC,αE,αA,αB,正則化參數λU,λV,λT,迭代次數Iter,學習速率參數uC,uE,uA,uB,隱式因子個數D;

輸出:模型參數U,V,T.

從算法1 可以看出,模型求解的時間復雜度為O(Iter×(|PC|+|PE|+|PA|+|PB|)×D),其中:Iter為迭代次數;|PC|,|PE|,|PA|和|PB|分別表示集合PC,PE,PA和PB中元素的個數,即排名對的個數;D表示隱性因子的個數.通過學習到的模型參數U,V,T,就可以得到預測簽到張量?C,從而為目標用戶在某一時間片生成餐館推薦列表.

3 實驗及結果分析

3.1 數據集及實驗環(huán)境

本文使用大眾點評數據集(http://yongfeng.me/)和Yelp 數據集(https://www.yelp.com/dataset)進行餐館推薦研究.這兩種數據集都包括用戶的評論數據集和商家的屬性數據集,由于用戶隱式的保護,都沒有公開用戶的人口統(tǒng)計信息.用戶的評論數據集中都包括用戶的評分、評論以及消費信息,不同的是:Yelp 數據集給出的評論時間只具體到哪一天,而大眾點評數據集具體到了一天中的某個時刻.另外,本文將用戶評論一次可以看做簽到一次.商家的屬性數據集都包括商家的ID、名字、位置(城市、經緯度等)、餐館的種類以及標簽等信息.

在這兩種數據集中,商家不僅包括餐館,還包括超市、酒吧以及茶館等.由于除了餐館的其他商家與研究的主題無關,因此首先必須從數據集中剔除與餐館無關的信息.對處理后的兩種數據集,各項統(tǒng)計信息見表3.

Table 3 Statistics of dataset表3 數據集的各項統(tǒng)計信息

從表3 中可以看出,Yelp 數據集中,用戶的數量是Dianping 數據集中用戶數量的將近3 倍;而Dianping 數據集中,餐館的數量是Yelp 數據集中餐館數量的近15 倍.這可能導致模型在Yelp 數據集中的推薦效果要優(yōu)于Dianping 數據集.

為了更好地驗證推薦模型的效果,分別將兩種數據集劃分為訓練集(80%)和測試集(20%),訓練集主要是用來學習推薦模型中的參數,測試集主要是用來驗證模型的推薦效果.

本文的實驗環(huán)境為:Windows7 操作系統(tǒng),4GB 內存,Intel(R)Core(TM)2 Duo CPU 2.93GHz,實驗程序使用java1.6 語言開發(fā).

3.2 評價指標

對于基于隱式反饋的推薦而言,MAE 不是一個很好的評價指標,因為與評分不同,隱式反饋只有1 或者0,而且由于數據的稀疏性,1 的數目會很少,這樣,計算MAE 是沒有意義的.因此,為了驗證推薦的效果,本文采用recall@K作為評價指標,對于recall@K的定義如公式(13):

其中,recall@K表示在top-K列表中的召回率;hit表示測試集中的命中次數,所謂命中是指如果測試集中的簽到餐館出現在了top-K的推薦列表中,那么就表示命中一次;recall表示測試集簽到總次數.

3.3 實驗結果與分析

在這一節(jié),主要在兩種數據集中分別進行以下實驗:(1)比較本文提出的模型(RRMIF 模型)和現有模型的推薦效果;(2)研究多種數據信息對于推薦效果的影響,包括時間上下文、地理上下文、餐館風格以及用戶居住地;(3)研究RRMIF 模型在不同稀疏度數據子集的表現,并與現有模型作比較;(4)研究RRMIF 模型的運行時間,并與現有模型作比較.

通過網格搜索法對RRMIF 模型的參數進行調優(yōu),得到實驗效果最好的模型參數如下:方差參數σU=σV=σT=0.1;正則化參數λU=λV=λT=0.004;誤差參數αC=0.45,αE=0.2,αA=0.3,αB=0.05;迭代次數Iter=40;學習速率參數uC=0.2,uE=0.06,uA=0.1,uB=0.04 以及隱性因子個數D=10.

值得注意的是:由于Yelp 數據集中沒有提供用戶在一天中具體的簽到時間,因此時間片的大小為1;而對于Dianping 數據集,按照上文的聚類結果,將時間片的大小設置為4.

3.3.1 與其他對比模型的比較

為了驗證文中提出的RRMIF 模型的推薦效果,本文選取下面幾種利用用戶隱式反饋來進行興趣點推薦的相關模型作為對比.

(1)概率矩陣分解模型(PMF)[17]:該模型主要是利用了用戶的簽到信息,將“用戶-興趣點”的簽到矩陣分解為用戶隱式因子矩陣和興趣點隱式因子矩陣,再利用這些隱式因子矩陣預測用戶對于興趣點的評分,進而為用戶生成推薦列表;

(2)加權矩陣分解模型(WMF)[18]:該模型在概率矩陣分解的基礎上,通過分析用戶的隱式反饋,得到正反饋和負反饋的置信水平,從而使得矩陣分解模型更好地應用于隱式反饋的研究;

(3)基于用戶的協同過濾模型(UCF)[27]:該模型主要利用相似度計算目標用戶的相似用戶集合,然后根據相似用戶對于目標項目的評分預測目標用戶對目標項目的評分,最后給出推薦列表;

(4)結合地理位置信息的矩陣分解模型(GeoMF)[8]:該模型在加權矩陣分解的基礎上引入了地理上下文,將用戶的活動區(qū)域向量融合到用戶隱式空間中,將興趣點的區(qū)域影響向量融合到興趣點隱式空間中.通過這種融合,不僅考慮了用戶行為的空間聚類現象,還有效地解決了矩陣稀疏性問題;

(5)隱式反饋模型(IPM)[6]:該模型首先構建“用戶-餐館-時間片”的三維簽到張量,利用概率張量分解從簽到張量中獲得隱式空間的偏好;其次,利用邏輯回歸的方法分析用戶依賴于其他數據信息(餐館屬性、用戶人口統(tǒng)計信息)的偏好;最后,結合這兩種偏好得到用戶在某一時間片對餐館的預測評分,進而為目標用戶在某一時間片生成餐館推薦列表.

該實驗設置top-K=5,10,15,20,25,30,且當上述5 種模型的參數設置為最優(yōu)參數時,比較各模型在Dianping數據集和Yelp 數據集中的召回率(recall@K),結果如圖4 所示.

Fig.4 recall@K comparison of different model圖4 不同模型的召回率比較

觀察圖4 可以得到以下結果.

(1)無論在哪種數據集中,PMF 模型的推薦效果都是最差的,這主要是因為用戶的簽到數據是稀疏的;另外,PMF 模型沒有考慮時間上下文,也沒有融合其他數據信息;

(2)在兩種數據集中,WMF 模型的推薦效果都要優(yōu)于PMF 模型.這是因為WMF 模型在PMF 模型的基礎上還分析了正負反饋的置信水平,從而提升了推薦效果;

(3)在兩種數據集中,UCF 模型的推薦效果都要明顯優(yōu)于WMF 模型和PMF 模型.但是UCF 模型存在以下缺點:面對大數據集,模型的復雜度會急劇增大;很難融入其他數據信息,不易擴展.而對于WMF 模型和PMF 模型,則更易擴展,且面對大數據集仍然表現不錯.因此,WMF 模型和PMF 模型在適用性上要強于UCF 模型;

(4)與WMF 模型相比,在兩種數據集中,GeoMF 模型的推薦效果都要明顯優(yōu)于WMF 模型.這主要是因為GeoMF 模型考慮了餐館的地理位置信息,從而緩解了數據的稀疏性問題,也提高了推薦效果;

(5)在兩種數據集中,IPM 模型的推薦效果都要明顯優(yōu)于GeoMF 模型、WMF 模型、UCF 模型和PMF 模型.這是因為IPM 模型考慮了餐館的地理位置信息,并融入了時間上下文和其他數據信息;

(6)在兩種數據集中,RRMIF 模型的推薦效果都是最好的.這充分地說明了,雖然IPM 模型和RRMIF 模型都考慮了多種數據信息,但是RRMIF 模型相比于IPM 模型更加有效地將多種數據信息進行融合,充分挖掘了多種數據信息的價值,從而提升了推薦效果;

(7)Yelp 數據集中,各模型的召回率趨勢相比于Dianping 數據集更加緊湊,而且各模型在Yelp 數據集中的推薦效果要明顯優(yōu)于Dianping 數據集.這主要是因為Yelp 數據集中餐館的數量要明顯少于Dianping數據集,導致各模型的差距相對縮小.

實驗結果表明:RRMIF 模型相比于現有模型,更加有效地融合了多種數據信息,提升了推薦效果.

3.3.2 多種數據信息對推薦效果的影響

為了研究多種數據信息對于推薦效果的影響,該實驗對下面9 種推薦模型進行對比.

(1)概率矩陣分解模型(PMF):該模型僅僅考慮用戶的簽到信息,而沒有考慮時間上下文、地理上下文以及其他數據信息;

(2)概率張量分解模型(PTF)[12]:該模型僅僅考慮用戶的簽到信息和時間上下文,對用戶簽到張量進行分解,而不考慮地理上下文和其他數據信息;

(3)PTF+E:該模型不僅考慮用戶的簽到信息和時間上下文,還考慮了基于居住地的用戶相似關系E,同時對簽到張量和關系矩陣E進行分解;

(4)PTF+A:該模型不僅考慮用戶的簽到信息和時間上下文,還考慮了基于地理位置的餐館相似關系A,同時對簽到張量和關系矩陣A進行分解;

(5)PTF+B:該模型不僅考慮用戶的簽到信息和時間上下文,還考慮了基于餐館風格的餐館相似關系B,同時對簽到張量和關系矩陣B進行分解;

(6)PTF+E+A:該模型不僅考慮用戶的簽到信息和時間上下文,還考慮了基于居住地的用戶相似關系E和基于地理位置的餐館相似關系A,同時對簽到張量、關系矩陣E和關系矩陣A進行分解;

(7)PTF+E+B:該模型不僅考慮用戶的簽到信息和時間上下文,還考慮了基于居住地的用戶相似關系E和基于餐館風格的餐館相似關系B,同時對簽到張量、關系矩陣E和關系矩陣B進行分解;

(8)PTF+A+B:該模型不僅考慮用戶的簽到信息和時間上下文,還考慮了基于地理位置的餐館相似關系A和基于餐館風格的餐館相似關系B,同時對簽到張量、關系矩陣A和關系矩陣B進行分解;

(9)PTF+A+B+E(RRMIF):該模型就是本文提出的RRMIF 模型,它不僅考慮用戶的簽到信息和時間上下文,還考慮了基于居住地的用戶相似關系E、基于地理位置的餐館相似關系A以及基于餐館風格的餐館相似關系B,同時對簽到張量、關系矩陣E、關系矩陣A和關系矩陣B進行分解.

該實驗設置top-K=5,10,15,20,30,且當上述9 種模型的參數設置為最優(yōu)參數時,比較各種模型在兩種數據集中的召回率(recall@K),如圖5 所示.

Fig.5 Research of multiple data information圖5 多種數據信息的研究

從圖5 中可以看出:

(1)在Dianping 數據集中,PMF 模型的推薦效果要低于PTF 模型,這主要是因為PTF 模型考慮了時間上下文信息;而在Yelp 數據集中,PMF 模型的推薦效果幾乎與PTF 模型一樣,這主要是因為Yelp 數據集中沒有用戶簽到的具體時間,因此時間片設置為1,因此,PTF 模型的效果基本和PMF 模型相同;

(2)在兩種數據集中,PTF+A>PTF+E>PTF+B>PTF.這驗證多種數據信息對于用戶餐館選擇的影響,并且餐館的地理位置影響最大,其次是用戶的居住地,最后是餐館的風格;

(3)在兩種數據集中,PTF+A+E>PTF+A+B>PTF+B+E.這說明如果只考慮兩種數據信息,同時考慮餐館地理位置和用戶居住地的效果是最好的;

(4)在兩種數據集中,PTF+A>PTF+B+E.這說明考慮餐館的地理位置對于推薦效果的提升比同時考慮用戶的居住地和餐館風格還要大;

(5)無論在哪種數據集中,PTF+A+B+E 的推薦效果都是最好的,這個模型也就是本文提出RRMIF 模型.這說明當同時考慮了餐館的地理位置、餐館的風格以及用戶的居住地時,模型的效果是最好的;

(6)Yelp 數據集中,各模型的召回率要相比于Dianping 數據集更緊湊.這是由于數據集本身特性的影響,Yelp 數據集中餐館的數量明顯少于Dianping 數據集.

實驗結果表明,多種數據信息能夠有效地提高推薦的效果,按照作用大小排序如下:餐館地理位置>用戶居住地>餐館風格;另外,RRMIF 模型通過融合多種數據信息,使得推薦效果明顯要優(yōu)于只融合一種或者兩種數據信息的模型.

3.3.3 稀疏性驗證

為了驗證RRMIF 模型在不同稀疏度數據集的表現,該實驗從Dianping 數據集和Yelp 數據集中分別抽取了4 種稀疏度不同的數據子集,各數據子集的統(tǒng)計信息見表4.其中,稀疏度定義為

Table 4 Statistics of different sparse subset表4 不同稀疏度數據子集的統(tǒng)計信息

從表4 中可以看出,按照稀疏度排序:

RRMIF 模型與第3.3.1 節(jié)中的5 種對比模型在以上各數據子集的召回率(recall@30)比較如圖6 所示,從圖6 中可以看出:

(1)隨著數據稀疏度的降低,PMF 模型的推薦效果逐漸提升.例如,PMF 模型在Dianping-3 的效果相比于Dianping-1 提升了1.5 倍,相比于Dianping-2 提升了35%.這是因為PMF 模型的目的是通過矩陣中的“1”來填充整個矩陣的值,因此極易受數據的稀疏性影響.當數據相對稠密時,也就是說矩陣中“1”的比例相對較多時,模型的效果就會得到提升.另外,PMF 模型在Dianping-4 的效果相比于Dianping-3 降低了2.3%.這說明PMF 模型隨著數據稀疏度的繼續(xù)增加,PMF 模型的推薦效果會逐漸趨于平穩(wěn),并有降低的趨勢;

(2)與PMF 模型類似,UCF 模型和WMF 模型隨著數據稀疏度的降低,推薦效果都有明顯的提升,且最后也會趨于平穩(wěn).WMF 模型通過引入正負反饋的置信水平來提升推薦效果,但是正負反饋的置信水平仍然受到數據稀疏性的影響.UCF 模型是通過用戶的共同評分來計算用戶相似度的,因此數據的稀疏性影響著UCF 模型的推薦效果;

(3)從Dianping 的數據子集中可以看出,隨著數據稀疏度的變化,GeoMF 模型推薦效果變化不大.這是因為該模型考慮了餐館的地理位置信息,緩解了矩陣的稀疏性問題;

(4)在Dianping 的數據子集中,隨著數據集稀疏度的變化,IPM 模型的推薦效果相對穩(wěn)定;而在Yelp 數據子集中,IPM 模型的推薦效果還是受到了稀疏性的影響;

(5)不論在Dianping 的數據子集還是在Yelp 的數據子集,RRMIF 模型的推薦效果都是最好的,而且基本不受數據稀疏性的影響.這說明本文提出的模型不僅在有效性上優(yōu)于其他對比模型,在穩(wěn)定性上也要優(yōu)于其他對比模型;

(6)隨著數據稀疏度的降低,其他對比模型的推薦效果有一定的提升,但仍然低于RRMIF 模型.

Fig.6 Sparsity verification圖6 稀疏性驗證

實驗結果表明:相比于現有其他模型,RRMIF 模型在數據極其稀疏的情況下仍然能夠很好地進行推薦,這說明RRMIF 模型有效地緩解了數據稀疏性對于推薦效果的影響.

3.3.4 效率評估

在實際應用中,推薦模型的運行時間往往是重要的評價指標之一,如果模型的運行時間超過了可接受范圍,那么這個模型的實用性就會受到限制.該實驗主要對RRMIF 模型和第3.3.1 節(jié)中的5 種對比模型分別在Dianping 數據集和Yelp 數據集進行效率的評估.首先,從Dianping 數據集分別抽取4 種用戶數量不同的數據子集,用戶數量分別為300、600、1200 和2400,然后得到RRMIF 模型和其他5 種對比模型在4 種數據子集的運行時間.為了全面地進行效率比較,在Yelp 數據集上按照相同的操作進行.最后,分別得到各模型基于兩種數據集的效率評估,如圖7 所示.橫軸表示用戶數量,縱軸表示為運行時間,單位為秒(s).

從圖7 中可以看出:

(1)在兩種數據集中,PMF 模型、WMF 模型、UCF 模型和GeoMF 模型的運行時間大致排序為:GeoMF>UCF>WMF>PMF.這是因為WMF 模型是基于PMF 模型,考慮了正負反饋的置信水平,增加了一個權重矩陣;而GeoMF 模型是基于WMF 模型,考慮餐館的地理位置信息,增加了特征向量的維數.對于UCF 模型,需要計算每個用戶的相似用戶,受用戶數量影響明顯,當用戶數量增加時,會出現運行時間陡增的情況;

(2)Dianping 數據集中,模型的運行時間相比于Yelp 數據集顯著地增加,這主要有兩個原因:第一,因為Yelp 數據集中用戶的簽到時間沒有具體到一天的某個時刻,因此時間片設置為1,這樣就導致Yelp 數據集中的模型的運行時間顯著地降低;第二,Dianping 數據集的稀疏度要低于Yelp 數據集,這有可能導致了運行時間較高;

(3)無論在Dianping 數據集還是在Yelp 數據集,IPM 模型的運行時間都是最多的.IPM 模型的運行時間是最長的,而且隨著數據集的增大,運行時間也隨之增長,并且增長速率也逐漸增大,幾乎呈現指數增長的趨勢.這主要有兩方面的原因:第一,該模型對多種數據信息預處理的復雜度相對較高;第二,該模型除了要通過概率張量分解進行求解,還需要通過邏輯回歸求解;

(4)基于Dianping 數據集,RRMIF 模型的運行時間要高于GeoMF 模型、WMF 模型、UCF 模型和PMF模型,這主要是因為RRMIF 模型考慮了時間上下文信息,需要為用戶在某一時間片生成推薦列表,因此計算的時間復雜度增大.而基于Yelp 數據集,RRMIF 模型的運行時間雖然高于PMF 模型,但是要低于GeoMF 模型、WMF 模型和UCF 模型.這是因為基于Yelp 數據集的實驗,時間片設置為1,這樣,RRMIF 模型的運行時間顯著降低.這也說明了在同樣不考慮時間上下文的情況下,RRMIF 模型的運行效率是相當可觀的;

(5)從這兩種數據集可以看出:RRMIF 模型的運行時間雖然隨著數據集的增大而增大,但是沒有呈現出急劇增大的趨勢.換句話說,該模型的運行時間隨著數據集的增大而平穩(wěn)增大.因此,本文提出的模型在大數據集下仍然是實用的.

Fig.7 Efficiency evaluation of different model圖7 各模型的效率評估

實驗結果表明,RRMIF 模型的運行時間要遠低于IPM 模型,略高于其他模型.但是隨著數據量的增大,RRMIF 模型的運行時間幾乎呈現穩(wěn)定增長的趨勢.這說明RRMIF 模型的運行時間雖然不是最少的,但是它的增長趨勢仍然是可接受的.

4 總結

本文首先介紹了餐館推薦的相關工作,包括興趣點推薦和餐館推薦,并分析了現有推薦模型的優(yōu)缺點.然后,基于大眾點評數據集研究了多種數據信息對于用戶餐館選擇的影響,并通過K-means 聚類算法將一天24 小時分為4 個用餐時間段.另外,基于地理上下文、餐館屬性信息構建了兩種餐館相似關系矩陣,基于用戶人口統(tǒng)計信息構建了用戶相似關系矩陣.在此基礎上,本文提出了一種融合多種數據信息的餐館推薦模型(RRMIF).該模型首先利用簽到信息和時間上下文構建“用戶-餐館-時間片”的三維張量;然后,在概率張量分解模型的基礎上同時分解用戶相似關系矩陣和餐館相似關系矩陣;最后,利用BPR 優(yōu)化準則和梯度下降算法進行模型求解.為了更加全面地驗證RRMIF 模型的有效性,本文基于大眾點評數據集和Yelp 數據集做了以下4 個實驗:(1)與現有模型比較;(2)研究多種數據信息對推薦效果的影響;(3)稀疏性驗證;(4)效率評估.最后,實驗結果表明,相比于目前存在的餐館推薦模型,RRMIF 模型有著更好的推薦效果和可接受的運行時間,并且緩解了數據稀疏性對推薦效果的影響.