基于類別轉移加權張量分解模型的興趣點分區推薦

李 勝 劉桂云 何熊熊

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

1 引言

隨著社會信息化進程的不斷加速，位置信息服務在社會各行各業中越發普及，這使得基于位置的社交網絡(Location Based Social Networks， LBSN)服務成為一項具有重要價值的應用，比如Foursquare、去哪兒網等都是以提供類似服務為主的產品。POI推薦是基于位置的社交網絡服務研究中的一項重要內容，它不僅可以一定程度地解決大數據時代用戶面臨的信息過載問題，而且能夠幫助商家快速找到目標用戶，實現精準營銷[1]。

在如此良好的發展機遇面前，推薦系統面臨著許多挑戰，比如用戶的POI決策過程建模困難、數據稀疏等。傳統的推薦算法主要是協同過濾算法，在此算法基礎上衍生出了許多推薦模型，例如基于POI排名的因式分解[2]、矩陣分解[3]等。現有研究多利用高階張量模型代替傳統的用戶定位矩陣，這有助于解決用戶動態簽入隨時間變化的時間依賴性[4]。但高維張量分解會增加系統的負擔，如何權衡信息的維度成了研究的一大難題。

在推薦系統中，用戶的顯式偏好是結合用戶歷史行為和地點信息進行分析計算得到的[3]，如偏好的時間、類別、位置標簽等。除此之外，還有一部分隱式信息需要挖掘，這些隱式反饋往往存在于交互關系中，如連續行為偏好[5]、隱式社交關系[6]等。為此，一些研究會把隱式反饋轉化為權重以此降低矩陣維度[6，7]，或者把從信息中提取的影響因素納入模型中減少數據稀疏[8，9]。

事實上，使用隱式反饋來探索POI推薦是具有挑戰性的，因為學習過程需要一種有效的策略。例如在挖掘用戶連續行為偏好時，利用不同層次上的類別轉換來對用戶的偏好轉換進行建模[5]，能減緩利用POI之間的轉換進行建模[10]帶來的稀疏性。但是由于用戶的移動性，推薦區域多有不同，此類模型在捕獲POI的語義相關性上需要考慮更全面的影響因素才能給游客帶來更多便利。

在一個不熟悉的區域中，旅行者和POI之間的交互是非常稀少的，但其興趣在家鄉與所到城市之間存在著漂移和轉移的現象。將興趣漂移和興趣轉移結合起來，利用用戶跨城市的訪問行為可以改善所到城市的POI推薦[11，12]。其次，通過引入POI的顯式信息[4，8]或者借鑒朋友的偏好影響[6]，也可以緩解所到城市用戶POI交互的稀疏性問題。那么，為了有效地利用社會和空間相關性，可以把興趣的漂移和轉移現象同顯式和隱式信息中提取的影響因素結合起來，根據當前位置進行分區域推薦。

綜上所述，對推薦系統的現有研究可以在模型、類別轉化、影響因素以及分區域推薦4個方面進行突破。本文提出一種新型的基于加權張量分解模型的興趣點分區推薦算法，主要貢獻有以下3點：(1)對簽到信息中蘊含的顯式信息和隱式信息進行用戶標簽和地點標簽的劃分，改善時間、類別和朋友特征的提取方法，更好地把影響因子融合到不同的推薦區域中。(2)對張量構造進行改進，把隱式反饋中的用戶連續行為偏好與類別信息結合作為模型的權重信息，加入到用戶-時間-類別張量中，此做法不僅綜合了用戶、時間和類別這3維信息，又充分考慮到歷史訪問信息的權重影響。(3)基于用戶的移動性特征，把候選類別與提取的特征相融合進行分區POI推薦：依據用戶當前位置與常駐地之間的距離把推薦場景細粒度化，劃分出本地推薦和異地推薦，再匹配不同的影響因素做不同區域的推薦。發揮各類影響因素特點的同時，也使得預測用戶的下一步偏好更精準。

2 預備知識

2.1節分析如何改善從顯式和隱式信息中抽取特征的方法。2.2節是文章整體框架的圖示。

2.1 相關性分析

2.1.1 時間特征分析

人們的行為在特定時間會有特定變化，即實時性，而且具有持續性[13]，因此在興趣點推薦中加入時間分析是必要的。大多數文章對于時間區域的劃分為均勻24段[14]，這忽略了用戶出行習慣的不確定性及事件的持續性，而且會額外增加數據維度。從種類信息中選取6個具有時間象征性的類別，如圖1(a)橫軸坐標所示，分別對應為：1→專業場所(professional & other places)、2→辦公樓(office)、3→博物館(museum)、4→體育場(stadium)、5→戶外休閑(outdoors & recreation)、6→夜生活場所(nightlife spot)，可以看出，用戶在工作日和休息日的類別訪問占比有所不同，這說明在工作日和休息日，用戶的興趣側重不同。由Foursquare數據集中用戶的訪問分布可知，人們的活動軌跡大多集中在3個時間段，示例如圖1(b)所示。本文把用戶每天的時間活躍范圍劃分成3個時間段：“7:00～15:00”，“15:00～21:00”，“21:00～7:00(次日)”。綜上所述，本文根據工作日、休息日和3個時間段劃分6個時間標簽，既減少數據稀疏性，又具有興趣針對性。比如用戶1會在休息日7:00～15:00時間段運動，用戶2會在工作日21:00～7:00(次日)時間段現身酒吧。

圖1 時間特征劃分示例

2.1.2 類別特征分析

本文將類別信息和連續行為結合作為類別預測模型的權重信息，在捕獲用戶興趣的同時可以簡化信息維度。在連續POI推薦的問題上，以往的研究多使用1階馬爾科夫鏈來建模[10]，但此模型僅依賴用戶最后訪問的興趣點，不考慮其歷史訪問。而實際中，每個用戶有其獨特的歷史訪問序列，對新興趣點的訪問概率也參考歷史訪問信息。因此本文引用一種基于高階序列的模型—加權馬爾科夫鏈模型來研究用戶的連續行為，為此構造基于加權馬爾科夫鏈的類別轉移權重，定義為WTC，它將考慮簽到歷史中所有簽到點對新興趣點訪問概率的影響。

加權馬爾科夫鏈是在轉移圖的基礎上構造的，而基于類別訪問序列的轉移圖相對于地點轉移圖更具有泛化度[9]。在類別轉移圖中，把一個節點的轉出頻率定義為Cout，轉移頻率定義為CTrans。如圖2所示，對于酒店這個節點，其轉出頻率有8次(Cout為8)，轉入餐飲節點5次，轉入大型交通工具節點2次(CTrans為7)。給出目標用戶的類別訪問序列，用戶對新興趣點的轉移權重如式(1)所示

圖2 類別轉移圖示例

2.1.3 朋友特征分析

隨著網絡科技的發展，人們社交中“朋友”間的交互不斷地豐富著個人的興趣偏好，因此隱式社交關系在推薦系統中應用的越發頻繁，且用戶與“朋友”間的信任關系有助于提高推薦系統的性能[15]。“朋友”的簽到頻率z遵循冪律分布[6](Powerlaw Distribution， PD)，其概率密度函數如式(3)所示

興趣朋友指社交網絡中興趣相投的人群，其位置分布廣，但在同一時間段有相似的愛好。興趣朋友的定義是為適應異地推薦的場景，如式(6)所示

2.1.4 位置特征分析

2.2 框架構造

本文的整體框架分為3部分，如圖3所示。

圖3 框架圖

3 類別預測

本文構造用戶-時間-類別3維張量，并且從隱式反饋信息中提取用戶連續行為偏好，將其作為類別轉移權重加入張量分解中，然后優化分解過程得到類別預測列表。

3.1 張量構造

張量構造可解決用戶動態簽入行為的時間依賴性[16]，本文根據用戶在某個時間場景下的特定喜好，分析出時間類別對，構造用戶-時間-類別張量R。

3.2 張量分解模型

本文采用張量分解中的Tucker分解，其原理是通過分解高維張量，生成稠密的預測張量來逼近原始張量，填補空缺值，從而生成推薦，如圖4所示。

圖4 截斷Tucker分解：秩-(τ1，τ2，τ3)近似

4 分區推薦

用戶訪問位置的概率不僅受距離影響，而且還受到位置固有特性的影響[11]。因此，用戶的實際簽到位置分布在不同區域，且潛在影響因子多有不同。本文將POI推薦細粒度化：本地推薦和異地推薦。

本文用K-means聚類算法將每個用戶簽到信息中的經緯度聚類得到一個中心作為每個用戶的常駐地 loc；然后以此中心設置距離閾值f，若當前位置cur與常駐地l oc的距離小于該閾值，則推薦場景為本地推薦，否則為異地推薦。如圖5所示，這是某個用戶的歷史訪問記錄，虛線圈之內定義為此用戶的本地范圍，之外則為異地范圍。

圖5 用戶區域劃分示例

首先，將式(12)的類別預測分數進行排序，獲得目標用戶的類別預測列表C。再構造目標用戶的二分圖[18]BG=(U～，Vc，E)，其中U～表示目標用戶的朋友集合用戶，Vc是U～中用戶在預測類別列表中訪問過的位置，E表示用戶和位置之間的關系連接，如圖6所示。

圖6 二分圖示例

表1 類別預測算法

然后在不同的區域，匹配不同權重的影響因素。最后，結合式(5)—式(8)和二分圖 BG，得到用戶對下一個地點的訪問概率Score如式(13)所示

5 實驗總結

5.1 數據集

Foursquare是一種基于地理位置信息的社交網絡，它記錄了用戶的簽到信息，例如用戶信息、地點經緯度等，而且基于此網絡的數據集多用于推薦系統的評測。本文的兩個數據集是由Foursquare用戶在加州(CaliforniA， CA)和紐約州(New York， NY)兩個特大地區生成的，包含了用戶在2012年4月至2013年4月期間發布的信息，其中同時包含的類別信息和具體的時間信息，符合本文實驗所需要的數據標簽且方便數據預處理，分布如表2所示。在數據的預處理階段，去掉簽到記錄少于10條的用戶以及少于5個用戶訪問的地點，以此緩解用戶的朋友關系。然后在每個用戶中隨機選擇70%的簽到信息作為實驗的訓練數據，30%作為實驗的測試數據。

表2 數據集統計分布表

5.2 評價指標

5.3 實驗結果對比分析

本文提出的基于類別轉移加權張量分解模型的興趣點分區推薦算法(Weighted Tensor Decomposition Partition Recommendation algorithm，WTD-PR)將與以下5種算法作對比：

(1) Augmented Square error based Matrix Factorization (ASMF)[6]：基于平方誤差的矩陣分解算法，該算法融合了3種朋友影響以及地理影響。

(2) Geographical Factorization Model based on POI Ranking (Rank-GeoFM)[2]：基于POI排名的因式分解算法，并且融入地理和時間因素。

(3) POI recommendation based on Tensor Decomposition model (TD)[4]：基于張量分解模型并融合多維信息的興趣點推薦算法。

(4) A LOcation REcommendation algorithm that incorporates Geography， Friends and Popularity factors (GFP-LORE)[8]：融合了序列信息、地理、朋友和流行度因素的推薦算法。

(5) Location neighborhood-aware Weighted pro-babilistic Matrix Factorization (LWMF)[7]：位置鄰域感知加權概率矩陣分解算法，從位置的角度挖掘地理特征，將其作為隱式反饋權重。

為了驗證本文算法在興趣點分區推薦上的有效性，我們進行了無差別推薦、本地推薦和異地推薦這3種驗證實驗，其在k為5、10、15、20、25、30的情況下的精確率和召回率如圖7所示。相比于無差別推薦，本地推薦和異地推薦的推薦性能在不同的k值上都處于領先狀態，這說明本文的模型在推薦層面更具有針對性，不同的場景中融入合適的影響因素，提高了推薦數據的有效性，緩解數據稀疏問題的同時提升人們的旅行體驗度。

圖7 分區推薦的優勢對比

在不分區推薦中，本文訓練出一個α值，滿足與其他算法的性能對比方式，α取0.69。實驗數據如圖8所示，無論是在哪一個區域，本文算法的性能都有較大的優勢，且相對于POI的直接推薦，類別預測在系統冷啟動問題上更有話語權。本文算法與LWMF和GFP-LORE這兩種算法作對比，證明了高階張量分解應用于推薦系統的優勢：張量填補減緩了數據稀疏性，且降低了信息的維度。TD模型和WTD-PR模型的對比，充分地顯示了權重的重要性，本文的權重分析是依據加權馬爾科夫鏈的序列轉移原理，這同時說明用戶連續行為的特征和歷史訪問記錄對于人們的下一步訪問有著很大的主導作用。

圖8 算法性能對比

除了以上兩種實驗場景，本文還做了消融實驗。其中對比算法分為2類5種：(1)在類別預測模塊消除信息維度：不融入時間信息(WTD-T)，不融入類別信息(WTD-C)；(2)在類別預測列表的基礎上融合不同影響因素：融合朋友和距離因素(WTD-FL)，融合朋友和地點流行度因素(WTD-FP)，融合位置和地點流行度因素(WTD-LP)。對比結果如表3所示，第1類算法的性能指標沒有第2類的高，這表明時間和類別信息對模型性能的影響較大，與現實中人們在不同的時段會有不同的喜好側重現象相吻合。在第2類算法中，WTD-LP算法的指標相對較低，這說明社交關系在推薦模型中有很大的權重占比。相對于這兩類算法，WTD-PR考慮多維上下文信息，分配其合適的權重，獲得了最優的性能，這表明推薦系統中上下文信息的重要性。此外，在該實驗中，去掉不同的數據標簽，本文模型仍具有較好的性能，這說明本文模型能適應標簽種類不同的相關數據集。

表3 多維因素有效性驗證

6 結束語

本文研究了一種基于類別轉移加權張量分解模型的POI分區推薦算法。在類別因子上融入加權馬爾科夫模型，生成類別轉移權重；構造基于用戶-時間-類別的加權張量，利用梯度下降算法進行迭代更新，推選出候選類別；再把位置信息中隱藏的距離因素、流行度因素以及朋友因素與候選類別進行融合，作基于用戶當前位置的POI分區推薦，并在無差別推薦、不分區推薦和消融實驗中做了對比分析。實驗表明，本文算法在多維信息融合和張量改進方面做了很大的突破，提升了性能也增加了通用性。