融合用戶行為網(wǎng)絡信息的個性化餐館推薦

傅晨波，鄭永立，周鳴鳴，宣 琦

(浙江工業(yè)大學 信息工程學院，浙江 杭州 310023)

近年來，隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，在線餐飲平臺服務越來越受到人們的喜愛，但是大量用戶和商家菜品信息的涌入，也造成了信息過載的問題。因此，推薦系統(tǒng)作為一種高效的信息過濾系統(tǒng)對食物信息的搜尋者和傳播者顯得十分重要。目前，推薦系統(tǒng)已經(jīng)廣泛應用于各種在線餐飲服務中，如Yelp，OpenTable，以及國內(nèi)的大眾點評網(wǎng)，餓了嗎等餐飲平臺。

推薦系統(tǒng)主要是從大量的用戶信息中，挖掘探索用戶的就餐喜好模式或者用戶之間相似性等進行推薦。其中，所需要的用戶信息包括顯式信息和隱式信息，顯式信息比較準確，例如用戶評分和評論等，隱式信息如瀏覽歷史，用戶資料，位置信息、社會關(guān)系等難以準確描述用戶喜好。由于隱式輔助信息種類眾多，處理方法各有不同，仍然是個性化餐館推薦研究領(lǐng)域關(guān)注的熱點。筆者從用戶的行為信息和復雜網(wǎng)絡的角度，挖掘了用戶就餐序列之間的行為網(wǎng)絡的拓撲結(jié)構(gòu)關(guān)系，提出了一種融合用戶行為網(wǎng)絡信息的個性化餐館推薦系統(tǒng)。筆者將首先介紹推薦系統(tǒng)的相關(guān)工作；然后介紹研究的數(shù)據(jù)集和融合用戶行為網(wǎng)絡信息的餐館推薦模型，包括就餐位置轉(zhuǎn)移網(wǎng)絡和口味轉(zhuǎn)移網(wǎng)絡的構(gòu)建，網(wǎng)絡表征及用戶行為信息的融合；接下來介紹模型對比方法、評價指標、實驗設計參數(shù)及實驗結(jié)果分析；最后進行總結(jié)和展望。

1 相關(guān)工作

傳統(tǒng)的餐館推薦系統(tǒng)主要分為兩種類型，分別是基于內(nèi)容的推薦系統(tǒng)[1](Content-based，CB)和協(xié)同過濾的推薦系統(tǒng)[2](Collaborative filtering，CF)?；趦?nèi)容的推薦系統(tǒng)主要考慮餐館之間或者用戶之間的屬性描述信息的相似度來進行推薦，而基于協(xié)同過濾的推薦系統(tǒng)則主要考慮外部的關(guān)系，例如用戶-用戶、餐館-餐館之間的相似性關(guān)系等。在協(xié)同過濾算法中，根據(jù)用戶的餐館評分信息，構(gòu)建用戶-餐館評分矩陣，來進一步刻畫用戶之間或者餐館之間的相似性并進行餐館推薦，例如UserCF，ItemCF等。研究表明：基于協(xié)同過濾的推薦算法效果優(yōu)于基于內(nèi)容的推薦算法，并且基于內(nèi)容的推薦系統(tǒng)也容易受限于屬性描述的質(zhì)量[3]?；趩我辉u分信息的協(xié)同過濾推薦算法僅僅依靠用戶的評分信息[4]，久而久之，缺少更多詳細的用戶喜好信息容易使用戶對推薦物品感到厭倦。因此基于多標準評分信息的協(xié)同過濾推薦系統(tǒng)也逐漸被提出來[5-6]。

隨著數(shù)據(jù)采集技術(shù)的不斷完善，越來越多的在線數(shù)據(jù)能夠被采集和利用，如用戶或者商品資料信息[7-8]、評論信息[9]、用戶位置[10]及用戶社交關(guān)系[11-12]等。研究者通過這些輔助數(shù)據(jù)信息，挖掘出用戶的潛在的喜好信息，進一步提高了個性化推薦系統(tǒng)的效果。例如，Bao等[9]通過同時考慮用戶的評分和評論文本信息，利用矩陣因子分解技術(shù)，提出一個更高效的餐館推薦模型TopicMF。Zhang等[10]利用用戶歷史就餐行為的位置信息，餐館評論數(shù)，餐館屬性來探索用戶的就餐偏好，進而設計一個組合的集成推薦模型框架，并在實際數(shù)據(jù)集上驗證了模型的推薦效率。Zhang等[13]根據(jù)用戶的評分信息將用戶進行分組，然后通過結(jié)合組之間和用戶之間的相似性，進一步提升個性化餐館推薦模型的效率。

在現(xiàn)實生活中，復雜網(wǎng)絡[14]是普遍存在的，許多復雜的系統(tǒng)都可以建模成網(wǎng)絡圖來進行表示，比如常見的計算機網(wǎng)絡、交通網(wǎng)絡以及社交網(wǎng)絡等。復雜網(wǎng)絡能夠捕獲網(wǎng)絡系統(tǒng)中節(jié)點的各種拓撲結(jié)構(gòu)特性，為具體的應用研究提供了一種重要的科學方法[14-15]。

隨著網(wǎng)絡科學的發(fā)展，基于網(wǎng)絡圖嵌入的推薦系統(tǒng)受到研究者的關(guān)注。例如，Ha等[16]利用用戶的歷史商品購買記錄，構(gòu)建了用戶的購買商品網(wǎng)絡，并提出一種基于商品網(wǎng)絡的協(xié)同過濾推薦系統(tǒng)。Shi等[17]利用不同元路徑的隨機游走策略，從異質(zhì)信息網(wǎng)絡(Heterogeneous information network，HIN)中學習得到用戶的向量表征，并應用到矩陣分解推薦模型中，能夠取得較好的效果。Jiang等[18]在HIN中利用隨機游走策略設計了一個貝葉斯個性化排序算法，依次來學習網(wǎng)絡中連邊的權(quán)重來進行標簽推薦。Gao等[19]基于用戶-商品的二分網(wǎng)絡提出一種新的二分圖嵌入算法，通過有目的地進行有偏隨機游走策略來學習節(jié)點的向量表征，進而計算用戶和商品之間的得分，進行排序推薦。

上述中，在基于用戶商品網(wǎng)絡或者用戶-商品二分網(wǎng)絡嵌入的推薦模型中，研究者從網(wǎng)絡的角度挖掘了用戶就餐序列之間的網(wǎng)絡拓撲聯(lián)系，并沒有考慮輔助信息網(wǎng)絡的隱含關(guān)系。在多尺度的輔助信息推薦模型中，已有的推薦工作中缺少考慮用戶行為網(wǎng)絡的拓撲結(jié)構(gòu)之間的聯(lián)系。筆者從用戶就餐行為網(wǎng)絡的角度，挖掘行為序列網(wǎng)絡中隱含的地理和口味偏好信息，并提出了一種融合用戶行為網(wǎng)絡信息的個性化推薦系統(tǒng)。具體來說，從用戶去過的歷史餐館列表中，提取用戶的地理位置轉(zhuǎn)移序列和口味轉(zhuǎn)移序列并構(gòu)建了就餐位置轉(zhuǎn)移網(wǎng)絡和口味轉(zhuǎn)移網(wǎng)絡。然后，利用復雜網(wǎng)絡的知識方法挖掘用戶歷史數(shù)據(jù)中包含的行為喜好信息，并結(jié)合用戶的評分信息構(gòu)建組合的協(xié)同過濾餐館推薦系統(tǒng)。

2 數(shù)據(jù)集介紹

本研究工作主要基于在線餐飲網(wǎng)站Yelp平臺官方發(fā)布的第8屆Yelp Dataset Challenge公開競賽數(shù)據(jù)集。原始數(shù)據(jù)集中包含了2004年10月12日到2015年12月24日期間，242 個城市中的25 071 家餐館信息，388 612 個用戶就餐記錄。每個餐館具有一個或者多個口味標簽，例如印度菜、意大利菜、快餐等，這也可以用來表征用戶的就餐時的口味喜好。數(shù)據(jù)集中也包含每個餐館精確的經(jīng)緯度信息，此外還有評論，評分等信息。

為了更好地研究餐館推薦問題，選取評論次數(shù)為50 次及以上的平臺活躍用戶作為研究對象。此外，依據(jù)用戶的就餐行為數(shù)據(jù)，選擇數(shù)據(jù)集中在線活動人數(shù)最多的兩個城市作為實驗數(shù)據(jù)集，分別為Charlotte和Scottsdale。實驗數(shù)據(jù)中的具體描述信息如表1所示。

表1 Yelp平臺中兩個城市數(shù)據(jù)集的數(shù)據(jù)信息Table 1 The preprocessed data of two cities in Yelp platform

3 餐館推薦模型設計流程

融合用戶行為網(wǎng)絡信息的個性化餐館推薦模型整體流程框圖如圖1所示。該流程主要包括6 部分：1) 在原始數(shù)據(jù)中提取用戶歷史就餐行為的地理位置數(shù)據(jù)和口味信息數(shù)據(jù)；2) 構(gòu)建用戶基于地理位置的轉(zhuǎn)移網(wǎng)絡GFN(Geography forage network)和基于口味的轉(zhuǎn)移網(wǎng)絡TFN(Taste forage network)；3) 通過網(wǎng)絡圖嵌入的方法得到網(wǎng)絡中地理位置標簽和口味標簽的向量表征；4) 將用戶歷史行為序列用位置和口味的嵌入向量表征，融合用戶行為信息，挖掘用戶潛在就餐偏好信息；5) 將用戶行為偏好信息和用戶評分信息整合到協(xié)同過濾算法中；6) 最后得到融合用戶行為信息的個性化推薦系統(tǒng)。

圖1 融合用戶行為網(wǎng)絡信息餐館推薦模型整體框圖Fig.1 The overall framework of the recommender combining the user behavior network information

3.1 用戶就餐地理位置遷移網(wǎng)絡

Yelp數(shù)據(jù)集中提供了餐館所在的具體經(jīng)緯度信息，根據(jù)用戶的歷史就餐記錄，可以得到用戶的就餐歷史位置序列。由于地理坐標過于精細化，因此將城市中的餐館劃分若干個區(qū)塊，類似于真實生活中的具體商圈。采用文獻[20]中的DBSCAN聚類算法來對餐館進行區(qū)塊聚類，使得數(shù)據(jù)集中每個餐館對應唯一的一個地理位置區(qū)塊。

對于用戶u，其就餐的歷史餐館序列為{R1,R2,…,Rn}，其中n表示用戶u的去過的餐館個數(shù)，Ri表示用戶u第i次就餐時去的餐館。根據(jù)餐館的地理位置區(qū)塊ci，可以得到用戶的歷史地理位置轉(zhuǎn)移序列，進而可以構(gòu)建用戶的地理位置轉(zhuǎn)移網(wǎng)絡GFN。具體來說，網(wǎng)絡中節(jié)點表示用戶去過的餐館的地位位置區(qū)塊ci，如果用戶訪問了位置區(qū)塊ci之后，下一次訪問了位置cj，則產(chǎn)生了有向連邊ci→cj。統(tǒng)計用戶的所有連邊信息，連邊ci→cj的權(quán)重wij表示用戶ui從位置區(qū)塊ci向cj轉(zhuǎn)移的頻次。圖2展示了某Yelp用戶的地理位置遷移網(wǎng)絡示意圖。節(jié)點越大，連邊越粗，表示該用戶偏好在這幾個地理位置之間就餐。最后，融合所有用戶的GFN網(wǎng)絡得到平臺用戶的就餐地理位置轉(zhuǎn)移網(wǎng)絡NG。

圖2 某Yelp用戶的地理位置遷移網(wǎng)絡GFN示意圖Fig.2 A transfer network GFN based on geography location of one user in Yelp

3.2 用戶就餐口味遷移網(wǎng)絡

在Yelp數(shù)據(jù)集中，餐館的口味標簽大部分不止一個。為了更好地描述用戶在每次就餐時的口味喜好，采用高斯密度函數(shù)估計GDA(Gaussian denoise algorithm)[21]的方法來提取用戶u每次就餐時的最中意的口味標簽t。因此，根據(jù)餐館的口味信息，得到用戶的就餐口味轉(zhuǎn)移序列。同理，按照上節(jié)中地理位置轉(zhuǎn)移網(wǎng)絡的構(gòu)建方法，可構(gòu)建用戶的口味轉(zhuǎn)移網(wǎng)絡TFN。在網(wǎng)絡TFN中，節(jié)點表示用戶每次的就餐口味標簽ti，有向連邊ti→tj表示相鄰的兩次就餐餐館的口味轉(zhuǎn)移情況，連邊權(quán)重表示用戶u從口味標簽ti向tj遷移的次數(shù)。圖3展示了某Yelp用戶的就餐口味轉(zhuǎn)移網(wǎng)絡，節(jié)點越大，連邊越粗，表示該用戶偏好于在這幾個口味的餐館之間就餐。最后，融合所有用戶的GFN網(wǎng)絡得到平臺用戶的就餐地理位置轉(zhuǎn)移網(wǎng)絡NT。

圖3 某Yelp用戶的就餐口味遷移網(wǎng)絡TFN示意圖Fig.3 A transfer network TFN based on cuisine tag of one user in Yelp

3.3 網(wǎng)絡表征學習

網(wǎng)絡是一種重要的表達對象之間聯(lián)系信息的載體，如何合理地表示網(wǎng)絡中的特征信息，一直以來是復雜網(wǎng)絡研究領(lǐng)域的重要課題之一。網(wǎng)絡表征學習[22]的目的在于將復雜網(wǎng)絡中的節(jié)點用低維的向量來表示，從而將網(wǎng)絡內(nèi)在的拓撲結(jié)構(gòu)信息轉(zhuǎn)換成容易表示的空間向量形式，便于應用到后續(xù)的任務場景。

其中，DeepWalk算法[23]類比于自然語言處理領(lǐng)域的詞表示學習算法Word2vec[24]，將網(wǎng)絡節(jié)點以向量的形式表達出來。Word2vec算法的主要思想是通過Skip-Gram模型，用詞向量間的空間距離來表征文本中單詞與其周圍單詞的親疏關(guān)系。在DeepWalk算法中，首先以網(wǎng)絡中每個節(jié)點作為起點，進行隨機游走，然后合并每次隨機游走的結(jié)果作為一整個隨機游走序列。假設在網(wǎng)絡G(V,E)生成的由節(jié)點V組成的隨機游走序列中，將節(jié)點vi的左右兩側(cè)窗口區(qū)間為d的一組序列表示為vi-d,…,vi-1,vi+1,…,vi+d，Skip-Gram模型要求以節(jié)點vi為中心所產(chǎn)生的這組兩側(cè)序列的概率最大化，換言之，即可以通過當前節(jié)點來推測出周圍節(jié)點。其目標函數(shù)為

(1)

其中概率函數(shù)p(vi+j|vi)的計算式為

(2)

式中：wv，w′v分別為節(jié)點v的輸入向量與輸出向量。

利用DeepWalk算法，分別對3.1，3.2節(jié)中用戶的就餐地理位置轉(zhuǎn)移網(wǎng)絡NG與口味轉(zhuǎn)移網(wǎng)絡NT進行網(wǎng)絡節(jié)點的表征學習，得到每個地理區(qū)塊c所對應的嵌入向量wgeo，以及每個口味標簽t所對應的嵌入向量wtas。

3.4 融合用戶行為信息

對于每個餐館，都對應著一組地理位置標簽-口味標簽(c,t)，將地理位置標簽c和口味標簽t分別用嵌入向量wgeo和wtas來表征，合并兩組一維向量，得到基于用戶行為信息的餐館向量表征w=[wgeo,wtas]。

因此，對于一個歷史就餐的餐館序列為{R1,R2,…,Rn}的用戶u，則其歷史就餐的餐館序列可以表征為

(3)

(4)

(5)

(6)

式中：a,b∈[0,1]，表示兩種模型預測得分的加權(quán)系數(shù)，選擇模型評價指標作為目標函數(shù)，通過貪婪算法尋優(yōu)選擇最優(yōu)的參數(shù)a,b。

4 實驗設計及結(jié)果

本節(jié)主要介紹了4 種推薦系統(tǒng)的對比方法以及模型的評價指標，并介紹了模型的實驗設計來驗證融合行為信息的個性化餐館推薦系統(tǒng)的效果。

4.1 對比方法介紹

1) 基于流行度的推薦算法(POP)：該方法直接根據(jù)物品的流行度來對商品進行排序并推薦給目標用戶。

2) 基于用戶的協(xié)同過濾推薦算法(UserCF)：根據(jù)用戶對商品的評分信息，選擇與目標用戶最相似的用戶，將其購買過的商品推薦給目標用戶。

3) 基于商品的協(xié)同過濾推薦算法(ItemCF)：根據(jù)用戶的評分信息，選擇與目標用戶購買過的商品最相似的商品，將其推薦給目標用戶。

4) 基于二分圖嵌入的推薦算法(BiNE)：BiNE

(Bipartite network embedding)是目前最好的二分圖嵌入推薦算法[19]。它從兩個方面來構(gòu)建二分網(wǎng)絡，分別是觀察到的邊所證明的顯式關(guān)系和未觀察到但傳遞的鏈接所暗示的隱式關(guān)系。并通過隨機游走策略學習得到網(wǎng)絡圖中用戶和商品的向量表征，計算用戶與商品的向量內(nèi)積得到用戶對商品的喜好得分排序，進行推薦。

4.2 評估指標介紹

采用3 個常用的評價指標[25]，來度量評價不同推薦算法的優(yōu)劣，分別是準確度(Precision，P)，召回率(Recall，R)，F(xiàn)1-分數(shù)(F1-Measure，F(xiàn)1)。令U表示測試集中的用戶集合，ui∈U。Q(ui)表示用戶ui實際去過得餐館集合，則這3 種指標的計算式為

1)P@k：準確度表示用戶對推薦的餐館感興趣的比例，其計算式為

(7)

(8)

式中：top@k(u)表示模型向用戶u推薦的前k個餐館列表；hits(Q(u),top@k(u))=Q(u)∩top@k(u)表示在推薦的餐館列表top@k(u)中用戶u實際去過的餐館個數(shù)，即被正確預測的餐館的個數(shù)。

2)R@k：召回率表示推薦列表中讓用戶感興趣的餐館占所有感興趣餐館的比例，計算式為

(9)

(10)

3)F1@k：F1-分數(shù)可以看作是評價指標準確率與召回率的一種加權(quán)平均，在推薦系統(tǒng)中F1@k的計算式為

(11)

4.3 實驗設計

在實驗中，選擇數(shù)據(jù)集中從2012年9月1日到2014年9月1日之間的數(shù)據(jù)作為訓練數(shù)據(jù)，并構(gòu)建Yelp社區(qū)的用戶就餐地理位置轉(zhuǎn)移網(wǎng)絡NG和就餐口味標簽轉(zhuǎn)移網(wǎng)絡NT。設定協(xié)同過濾算法UserCF和ItemCF方法中最相似的用戶或者餐館個數(shù)為50。此外，提出的組合推薦模型UserCF+GT和ItemCF+GT中各個單獨模型的權(quán)重參數(shù)a和b調(diào)整范圍為{0,0.1,0.2,…,1.0}，選擇模型評價指標F1-分數(shù)作為貪婪算法尋優(yōu)模型的目標函數(shù)，通過網(wǎng)絡搜索選擇最優(yōu)的權(quán)重系數(shù)a和b。在對比方法BiNE中，設置損失平衡參數(shù)α=β=0.01，γ=0.1；模型的學習率設置為0.025，最大迭代次數(shù)設置為100。隨機游走模型中的最大、最小游走數(shù)maxT和minT分別設置為32和1。實驗重復50 次，并記錄平均值。

4.4 結(jié)果分析

首先在Yelp平臺中活躍用戶數(shù)最多的兩個城市Charlotte和Scottsdale中比較了不同類型的餐館推薦模型top@10的推薦效果，如表2所示。對比基本的協(xié)同過濾算法UserCF和ItemCF，組合推薦模型UserCF+GT和ItemCF+GT均展示出更好的推薦效果。這也驗證了用戶的歷史就餐行為信息中包含著潛在的用戶行為偏好信息，例如地理位置偏好，就餐口味偏好等。由于通過構(gòu)建用戶的就餐行為轉(zhuǎn)移網(wǎng)絡來挖掘計算用戶的行為偏好信息，因此，也與最好的用戶-商品二分網(wǎng)絡嵌入的推薦方法BiNE進行比較，結(jié)果顯示組合模型UserCF+GT在3 種評價指標上均表現(xiàn)最好。

表2 不同的餐館推薦方法在兩個城市數(shù)據(jù)中的top@10推薦結(jié)果比較

此外，調(diào)整k的取值范圍為[5,10,15,20,25,30]，分析了不同推薦模型在top@k上的3 種評價指標的變化趨勢，如圖4所示。圖4中展示，融合用戶行為信息的組合推薦模型UserCF+GT和ItemCF+GT始終優(yōu)于基本的協(xié)同過濾算法UserCF和ItemCF。模型UserCF+GT在k值較小時，表現(xiàn)出更好的推薦效果。隨著k值的增加，不同的推薦算法模型的推薦效果也趨于相近，其中，F(xiàn)1分數(shù)和準確度P趨于穩(wěn)定。

圖4 6 種推薦模型在城市Charlotte和Scottsdale數(shù)據(jù)上隨著不同k值的結(jié)果變化曲線Fig.4 The curve of the results of six recommendation models on Charlotte and Scottsdale with different k values

5 結(jié) 論

主要基于用戶的歷史就餐行為數(shù)據(jù)，構(gòu)建了用戶的地理位置轉(zhuǎn)移網(wǎng)絡和口味轉(zhuǎn)移網(wǎng)絡，利用復雜網(wǎng)絡的方法挖掘了用戶潛在的就餐偏好，并用懷舊指數(shù)具體刻畫了用戶每次就餐行為與歷史就餐行為的差異變化。然后將該指標作為行為信息結(jié)合用戶的評分信息，調(diào)整權(quán)重，改進傳統(tǒng)的協(xié)同過濾推薦算法。最后，在真實的在線餐飲平臺Yelp數(shù)據(jù)集中進行實驗，發(fā)現(xiàn)融合用戶行為信息的個性化餐館推薦模型優(yōu)于已有的協(xié)同過濾和二分圖嵌入推薦模型。眾所周知，用戶就餐偏好是不斷變化的，后續(xù)的工作可以研究用戶行為偏好的時間變化情況，進而改進推薦模型。此外，也可以將懷舊指數(shù)融入到深度學習序列預測模型中，進而改進餐館推薦模型的預測效果。