基于類別轉(zhuǎn)移加權(quán)張量分解模型的興趣點分區(qū)推薦

李 勝 劉桂云 何熊熊

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

1 引言

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

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

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

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

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

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

2 預(yù)備知識

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

2.1 相關(guān)性分析

2.1.1 時間特征分析

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

圖1 時間特征劃分示例

2.1.2 類別特征分析

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

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

圖2 類別轉(zhuǎn)移圖示例

2.1.3 朋友特征分析

隨著網(wǎng)絡(luò)科技的發(fā)展，人們社交中“朋友”間的交互不斷地豐富著個人的興趣偏好，因此隱式社交關(guān)系在推薦系統(tǒng)中應(yīng)用的越發(fā)頻繁，且用戶與“朋友”間的信任關(guān)系有助于提高推薦系統(tǒng)的性能[15]?！芭笥选钡暮灥筋l率z遵循冪律分布[6](Powerlaw Distribution， PD)，其概率密度函數(shù)如式(3)所示

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

2.1.4 位置特征分析

2.2 框架構(gòu)造

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

圖3 框架圖

3 類別預(yù)測

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

3.1 張量構(gòu)造

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

3.2 張量分解模型

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

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

4 分區(qū)推薦

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

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

圖5 用戶區(qū)域劃分示例

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

圖6 二分圖示例

表1 類別預(yù)測算法

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

5 實驗總結(jié)

5.1 數(shù)據(jù)集

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

表2 數(shù)據(jù)集統(tǒng)計分布表

5.2 評價指標(biāo)

5.3 實驗結(jié)果對比分析

本文提出的基于類別轉(zhuǎn)移加權(quán)張量分解模型的興趣點分區(qū)推薦算法(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]：位置鄰域感知加權(quán)概率矩陣分解算法，從位置的角度挖掘地理特征，將其作為隱式反饋權(quán)重。

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

圖7 分區(qū)推薦的優(yōu)勢對比

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

圖8 算法性能對比

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

表3 多維因素有效性驗證

6 結(jié)束語

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