融合用戶行為網絡信息的個性化餐館推薦

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

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

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

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

1 相關工作

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

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

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

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

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

2 數據集介紹

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

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

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

3 餐館推薦模型設計流程

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

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

3.1 用戶就餐地理位置遷移網絡

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

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

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

3.2 用戶就餐口味遷移網絡

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

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

3.3 網絡表征學習

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

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

(1)

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

(2)

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

利用DeepWalk算法，分別對3.1，3.2節中用戶的就餐地理位置轉移網絡NG與口味轉移網絡NT進行網絡節點的表征學習，得到每個地理區塊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]，表示兩種模型預測得分的加權系數，選擇模型評價指標作為目標函數，通過貪婪算法尋優選擇最優的參數a,b。

4 實驗設計及結果

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

4.1 對比方法介紹

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

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

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

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

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

4.2 評估指標介紹

采用3 個常用的評價指標[25]，來度量評價不同推薦算法的優劣，分別是準確度(Precision，P)，召回率(Recall，R)，F1-分數(F1-Measure，F1)。令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實際去過的餐館個數，即被正確預測的餐館的個數。

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

(9)

(10)

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

(11)

4.3 實驗設計

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

4.4 結果分析

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

表2 不同的餐館推薦方法在兩個城市數據中的top@10推薦結果比較

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

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

5 結 論

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