廖國瓊 姜 珊 周志恒 萬常選

1(江西財經(jīng)大學信息管理學院 南昌 330013) 2(江西省高校數(shù)據(jù)與知識工程重點實驗室(江西財經(jīng)大學) 南昌 330013)

基于位置社會網(wǎng)絡的雙重細粒度興趣點推薦

廖國瓊1,2姜 珊1周志恒1萬常選1,2

1(江西財經(jīng)大學信息管理學院 南昌 330013)2(江西省高校數(shù)據(jù)與知識工程重點實驗室(江西財經(jīng)大學) 南昌 330013)

興趣點推薦是在基于位置社會網(wǎng)絡(location-based social network, LBSN)中流行起來的一種全新形式的推薦.利用LBSN所包含的豐富信息進行個性化推薦能有效增強用戶體驗和提高用戶對LBSN的依賴度.針對無顯示用戶偏好、興趣非一致性和數(shù)據(jù)稀疏性等挑戰(zhàn)性問題，研究一種針對LBSN的雙重細粒度POI推薦策略，即一方面將用戶的全部歷史簽到信息以小時為單位細分為24個時間段，另一方面將每個POI細分為多個潛在主題及其分布，同時利用用戶的歷史簽到信息和評論信息挖掘出用戶在不同時間段的主題偏好，以實現(xiàn)POI的Top-N推薦.為實現(xiàn)該推薦思路，首先，根據(jù)用戶的評論信息，運用LDA模型提取出每個POI的主題分布;然后，對于每個用戶，將其簽到信息劃分到24個時間段中，通過連接相應的POI主題分布映射出用戶在不同時間段對每個主題的興趣偏好.為解決數(shù)據(jù)稀疏問題，運用高階奇異值分解算法對用戶-主題-時間三階張量進行分解，獲取用戶在每個時間段對每個主題更為準確的興趣評分.在真實數(shù)據(jù)集上進行了性能測試，結(jié)果表明所提出的推薦策略具有較好的推薦效果.

興趣點推薦；基于位置社會網(wǎng)絡；LDA主題模型；興趣映射；張量分解

隨著移動設備和全球定位系統(tǒng)(GPS)的快速發(fā)展，近年來出現(xiàn)了一種以Foursquare和Gowalla為代表的基于位置社會網(wǎng)絡(location-based social network, LBSN)，將用戶的線上活動和線下交互有機地結(jié)合在一起.LBSN除允許用戶添加好友形成傳統(tǒng)意義上的在線社會網(wǎng)絡外，還能提供主動簽到(check-in)功能，幫助用戶與好友即時分享正在訪問的興趣點(point-of-interest, POI)信息.

興趣點是指用戶能夠獲取某種服務或享受樂趣的特定地點，如咖啡廳、餐館、電影院等.圖1是一個典型的LBSN結(jié)構(gòu)，包含3個層次信息，即地理位置層(簽到位置)、社會關(guān)系層(朋友關(guān)系)和內(nèi)容層(對興趣點的評論、照片及視頻等).有效利用LBSN中所包含的豐富信息進行興趣點推薦能增強用戶體驗和提高用戶對LBSN的依賴度.

然而，與傳統(tǒng)書籍、電影及商品推薦相比，POI推薦主要面臨3個挑戰(zhàn)：

1) 無顯示用戶偏好.雖然LBSN中存在大量簽到信息，但它們只能反映用戶訪問過某個POI這個事實，而不能簡單認為用戶在某位置簽到就是喜歡，未簽到就是不喜歡[1].因此，挖掘用戶隱式偏好是POI推薦應考慮的首要問題.

2) 興趣非一致性.通常來講，不同用戶在不同時間的興趣偏好是不一致的.例如有的人喜歡早晨去喝咖啡，下午健身，晚上去KTV；而有的人喜歡早晨健身，下午去KTV，晚上去喝咖啡.因此，POI推薦策略應為時間感知策略，即能根據(jù)不同時間進行興趣點的個性化推薦[2].

3) 數(shù)據(jù)稀疏性.眾所周知，LBSN中存在大量興趣點，而每個用戶的簽到信息十分有限，故簽到數(shù)據(jù)較為稀疏[3].

因此，傳統(tǒng)推薦策略已不能很好地應用于LBSN中的POI推薦.近幾年來，POI推薦得到了學者們的關(guān)注，以下分別從用戶偏好挖掘、時間感知推薦和數(shù)據(jù)稀疏性3個方面對相關(guān)研究進行分析.

1) 用戶偏好挖掘.用戶興趣偏好主要是從用戶的簽到信息或評論信息中來獲取.文獻[4]將用戶的簽到次數(shù)和用戶對POI的情感指向融合到一個矩陣分解模型中進行推薦.該策略考慮了兩者對用戶行為的影響.文獻[5]采用LDA方法提取興趣點的主題分布以及用戶興趣的主題分布，然后將兩者進行匹配獲取用戶的興趣偏好.但是，這2種方法都未考慮用戶興趣的非一致性特征，即認為用戶的興趣在任何時間都一樣.文獻[6]基于協(xié)同過濾方法計算用戶的偏好，但該方法過于依賴歷史數(shù)據(jù).文獻[7]利用HPY(hierarchical Pitman-Yor)語言模型處理用戶的歷史簽到信息，并以此為依據(jù)計算用戶的偏好;但該模型僅考慮了用戶的簽到次數(shù)，其準確率有待提高.

2) 時間感知推薦策略.時間因素在POI推薦中得到越來越多的關(guān)注.文獻[8]首次提出時間感知推薦策略，通過增添時間維度拓展基于用戶的協(xié)同過濾方法，其優(yōu)點在于能計算出不同時間段的用戶興趣.文獻[9]強調(diào)了時間非均勻性和連續(xù)性特征，將用戶簽到信息按小時劃分到24個矩陣中，并利用矩陣分解方法和余弦相似度計算連續(xù)時間段內(nèi)用戶偏好的相似性.但是，將簽到信息劃分到24個小時的矩陣中后，使得原本就稀疏的簽到信息變得更加稀疏.文獻[10]提出一種基于圖的推薦方法，同樣將時間以小時為單位進行劃分，然后將時間段、興趣點和用戶作為圖中的3類節(jié)點進行連結(jié)，有效地表示了用戶歷史簽到數(shù)據(jù)中時間與地點的關(guān)系;但該模型過于復雜，一旦改變時間段劃分標準，就會導致圖結(jié)構(gòu)發(fā)生巨大變化.

3) 數(shù)據(jù)稀疏特征.在LBSN中，用戶簽到信息的稀疏特征比傳統(tǒng)商品推薦更為明顯.文獻[11]采用傳統(tǒng)基于記憶的協(xié)同過濾方法進行推薦，但容易遭遇數(shù)據(jù)稀疏問題.這是因為無論是用戶還是興趣點之間的相似度，都是基于完整的共同簽到數(shù)據(jù)，而現(xiàn)實情況是不同用戶或興趣點所共享的簽到數(shù)據(jù)較少.文獻[12]利用非負貝葉斯矩陣分解方法將地理位置因素和文本內(nèi)容結(jié)合在一起，能處理非零值和零值簽到數(shù)據(jù)，但其不能較好地處理稀疏數(shù)據(jù)中的缺失值.文獻[13]提出一種利用多元中心高斯模型處理地理位置影響，并將其與矩陣分解模型相結(jié)合進行推薦，但該方法只能處理非零值簽到數(shù)據(jù)，且不適用于多維數(shù)據(jù)場合.文獻[14]提出基于用戶的歷史簽到數(shù)據(jù)構(gòu)建用戶-位置-時間三階張量，并采用張量分解法進行興趣點推薦.該方法能較好地解決數(shù)據(jù)稀疏問題，但其僅根據(jù)簽到次數(shù)來確定用戶的興趣偏好，而未考慮POI的主題特征.

除以上研究外，學者們還提出了考慮地理位置因素、社會朋友關(guān)系因素、用戶情感因素、POI流行程度等不同特征的POI推薦策略[15-23]，都能不同程度提高POI推薦效果.

綜上所述，已有興趣點推薦方法都只在某些方面解決了興趣點推薦所面臨過的上述挑戰(zhàn)問題.本文擬研究一種雙重細粒度POI推薦策略，即一方面將每天的時間細分為24個時間段，利用用戶的歷史簽到信息和評論信息挖掘出用戶在每個時間段的隱式主題偏好，即時間感知主題偏好；另一方面，將每個POI細分為潛在主題及相應的權(quán)重，通過計算給定時間的用戶的主題偏好和POI的主題分布之間的相似度進行推薦.在該推薦策略下，不僅使用了用戶的歷史簽到信息，而且結(jié)合了用戶簽到POI的評價信息，在兩者的共同作用下獲取用戶在不同時間段的隱式興趣偏好.同時，通過使用張量分解方法填補偏好的空缺值，可有效解決數(shù)據(jù)稀疏性問題，從而提高POI推薦的準確性.

1 問題定義及推薦框架

本文擬研究問題為，在給定時間點向用戶推薦其最感興趣的興趣點，具體如下：

本研究整體推薦框架如圖2所示:

Fig. 2 Overall recommendation framework圖2 整體推薦框架

圖2包括以下步驟：

1) 提取POI主題分布.基于用戶評論信息，利用LDA模型提取出全部POI的潛在主題分布.

2) 挖掘用戶的時間感知主題偏好分布.將用戶歷史簽到信息分為24個時間段，根據(jù)POI的主題分布，映射出用戶在每個時間段的潛在主題偏好分布.

3) 張量分解.建立用戶-主題-時間三維張量，通過張量分解方法，獲取用戶在24個時間段中更為準確的主題偏好分布.

4) 利用計算得到的時間感知主題偏好.生成給定用戶特定時間點的Top-N個POI推薦列表，從而實現(xiàn)個性化推薦.

2 POI-主題提取及興趣映射

首先，利用LDA(latent Dirichlet allocation)主題模型提取每個POI包含的主題分布；然后，利用離散變量的概率質(zhì)量函數(shù)將簽到信息與POI主題分布相結(jié)合，映射得到用戶的時間感知主題偏好分布.

2.1主題提取

LDA模型是一種語言模型，通過對自然語言進行建模識別出大規(guī)模文檔集合或語料庫中隱藏的主題信息.在該模型中，每個文檔表示為多個主題的概率分布，每個主題表示為一組單詞的概率分布.因此，該模型包含2個隱性變量：主題-單詞分布Φ和文檔-主題分布Θ.

主題提取的目標是根據(jù)全部用戶對POI的歷史評論信息提取出每個POI的主題分布.我們將全部POI的所有評價信息聚合到一個POI文檔中，并通過圖3所示的LDA模型[5]，生成每個文檔的主題分布.

Fig. 3 LDA topic generation model圖3 LDA主題生成模型

圖3中各參數(shù)的意義為

1) α和β為語料級別先驗參數(shù)，α代表每個文檔下主題多項分布的Dirichlet先驗參數(shù)，β代表每個主題下單詞多項分布的Dirichlet先驗參數(shù)；

2)θ和φ是隱含變量，θ表示每個興趣點與主題之間的多項分布，φ表示每個主題與語料庫單詞之間的多項分布；

3)w是顯示可觀察到的單詞向量，z是隱含的主題向量.wm,n表示第m個文檔中的第n個單詞；zm,n表示第m個文檔中第n個單詞所對應的主題.

基于LDA模型的POI主題分布生成過程如算法1所示：

算法1. POI主題生成算法.

輸入： K、α、POI描述文檔、單詞語料庫；

輸出：z，Φ，Θ.

for all topick∈[1,K] do

sample mixture componentsφk～Dir(β)；

end for

/*文檔層面*/

for all documentsm∈[1,M] do

sample mixture proportionφm～Dir(α)；

/*單詞層面*/

for all wordsn∈[1,Nm] in documentmdo

sample topic indexzm,n～Mult(θm)；

sample word indexwm,n～Mult(φzm,n)；

end for

end for

利用LDA模型可生成2個矩陣：

1) 主題-單詞概率矩陣ΦK×V，K是主題個數(shù)，V是數(shù)據(jù)集中不重復的單詞個數(shù)，向量φi為第i個主題的概率分布；

2) 興趣點-主題概率矩陣ΘM×K，其中M是POI個數(shù)，K是主題個數(shù)，向量θi為第i個POI的主題概率分布.

未知隱含變量θ和φ可通過式(1)求解得到.

本文利用吉布斯采樣(Gibbssampling)算法進行參數(shù){Θ,Φ}學習估計.該算法是每次選取概率向量的一個維度，通過固定其他維度的值抽樣當前維度值，重復迭代直到收斂，從而得到最終的主題-單詞分布Φ和文檔-主題分布Θ.

本研究的主要目的是要獲取每個主題的權(quán)重信息.以興趣點2612和2681為例，通過LDA模型得到的POI-主題分布如表1所示:

Table 1 The Examples of Results on POI-Topic Distribution表1 POI-主題分布結(jié)果示例

可以看出，2612號興趣點隸屬4個主題：1，10，13，39；2681號興趣點隸屬3個主題：20，30，39.每個主題都有相應的權(quán)重.例如，2612號興趣點第1個主題的權(quán)重約為0.093 2.一個POI隸屬的全部主題權(quán)重之和為1.

該算法單次迭代的時間復雜度為O(K×C)，其中K是主題個數(shù)，C是單詞總數(shù).多次迭代的時間復雜度為O(K×C×r)，其中r為迭代次數(shù).

2.2興趣映射

基于得到的POI-主題分布信息，進一步將用戶的歷史簽到信息按24個小時進行分片，映射出用戶的時間感知主題興趣分布，如圖4所示：

具體步驟如下：

1) 根據(jù)原始POI評價信息，利用算法1提取出各個POI的主題分布表，如圖4的POI-Topic Distri-bution圖所示；

2) 將每個用戶的簽到數(shù)據(jù)根據(jù)簽到時間劃分成24個時間切片，并統(tǒng)計每個時間片的簽到次數(shù)，得到每個用戶的時間感知簽到數(shù)據(jù)表，如圖4的Time-Aware Check-in Data圖所示；

3) 通過連接POI-主題分布表和時間感知簽到數(shù)據(jù)表，映射出用戶的時間感知興趣，得到時間感知的用戶-主題分布，如圖4的Time-Aware User-Topic Distribution圖所示.

具體興趣映射過程如下：

1) 統(tǒng)計每個用戶在每個時間段對每個主題所對應的所有興趣點簽到次數(shù)，以及對于該主題的簽到總次數(shù).

以用戶2為例，其數(shù)據(jù)連接示例如表2所示.在第18個時間段，用戶2對于隸屬于第39個主題的2個興趣點2612和2681的簽到次數(shù)分別為1和2，故簽到總次數(shù)為3,可以得出2個興趣點的簽到次數(shù)比率分別為33.3%和66.7%.

Table 2 Examples of Data Connecting表2 數(shù)據(jù)連接示例

3) 利用概率質(zhì)量函數(shù)(probability mass function， PMF)計算時間感知主題興趣偏好初始得分，即將該主題下每個POI的簽到次數(shù)比率與該主題所對應POI中的權(quán)重相乘后求和.

設Zk,t(un)表示用戶un在第t個時間段對于第k個主題的興趣偏好初始得分，其計算為

根據(jù)式(3)，可以計算用戶2在第18個時間段，對于第39號主題的初始興趣偏好：

Z39,18(u2)= 0.127 468 83×33.3%+
0.216 908 56╳66.6%=0.187 095 34.

由式(3)得到的每個主題的興趣初始偏好得分只反映用戶在每個時間段對每個主題的訪問偏好，而未考慮在該時間段對其他主題的訪問情況.為能對用戶在同一時間段全部主題的興趣偏好進行比較，需將用戶在同一時間段下的不同主題的興趣偏好初始值進行標準化處理.

設δk,t(un)為標準化因子，表示用戶un在第t個時間段對第k個主題的簽到總次數(shù)Ck,t(un)與在該時間段上所有主題的簽到總次數(shù)之和的比值，K為在第t個時間段訪問全部主題數(shù)，則δk,t(un)計算為

同樣以用戶2為例，其最終的興趣偏好的標準化處理如表3所示.用戶2在第18個時間段共簽到過3個主題：39，51，60，每個主題的初始興趣偏好由步驟1～3計算得到.在該時間段上全部簽到總次數(shù)之和為6，故3個主題的標準化因子分別為12(36)，16，13(26)，乘以各自的興趣偏好初始得分后，即可得到該用戶在該時間段下對于不同主題的最終偏好得分.

Table 3 Examples of Dealing Standardly表3 標準化處理示例

3 用戶-主題-時間張量分解

張量分解(tensor factorization, TF)是對矩陣分解的拓展，其原理是通過對高維張量進行分解，生成稠密的預測張量逼近原始張量.由于它能完整地表示高維數(shù)據(jù)，且能維持高維空間數(shù)據(jù)的本征結(jié)構(gòu)信息，具有提高數(shù)據(jù)統(tǒng)計特性及改善數(shù)據(jù)稀疏性等優(yōu)點[14].因此，本節(jié)擬采用張量分解中的高階奇異值分解(high-order singular value decomposition，HOSVD)方法對由時間感知用戶-主題分布構(gòu)成的張量進行分解，得到稠密的預測張量，以實現(xiàn)更為準確的推薦.

3.1UZT模型

首先，構(gòu)建初始三階初始評分張量Y∈N×K×O，其中N為用戶數(shù)，K為主題數(shù)，O為時間片數(shù)，如圖5所示：

Fig. 5 User-topic-time 3-order original tensor圖5 用戶-主題-時間三階初始張量

Y中的每個元素Yn kt表示第n個用戶在時間段t對第k個主題的興趣評分(preferencerating,PR)：

該三階張量為稀疏矩陣，不能反映用戶對全部主題的興趣.本文采用高階奇異值分解方法獲取稠密張量，該方法是以多元線性代數(shù)為基礎(chǔ)的奇異值泛化分解方法，用于解決多維數(shù)據(jù)的降維問題，基本步驟為

1) 將三階張量分解成為用戶U∈N×dU、主題Z∈K×dZ和時間T∈O×dT三個因子矩陣；

2) 構(gòu)建核心張量G∈dU×dZ×dT，用于控制用戶、主題、時間各因子矩陣之間的交互；

其中，“×U”表示張量和矩陣按照U-mode展開形式進行相乘，下標U表示了張量乘以矩陣的方向.“×Z”和“×T”同理.

3.2模型訓練求解

為避免過度擬合，將與U，Z，T，G相關(guān)的正則化引入到式(8)中，即添加這些因子F范數(shù)的正規(guī)則項，得到目標函數(shù)為

其中，λ和λG都為正則化參數(shù).

運用簡單在線算法的同時對因子矩陣Un*,Mk*,Tt*和核心張量G進行迭代，采取子空間隨機梯度下降法(stochasticgradientdescent，SGD)將目標函數(shù)最小化.每個因子矩陣以及核心張量的迭代過程如下：

用戶-主題-時間張量分解算法(簡稱為UZT)如算法2所示：

算法2. UZT算法.

輸入：用戶-主題-時間初始稀疏張量Y；

用較小的隨機值初始化U∈K×dU，Z∈K×dZ，T∈O×dT，G∈dU×dZ×dT；

設置步長η；

while(n,k,t)in觀察Ydo

endwhile

由于每次只訪問矩陣U，Z，T中的1行數(shù)據(jù)，所以該算法比較容易實現(xiàn)，其時間復雜度為O(dU×dZ×dT×r)，其中dU，dZ，dT分別為張量分解3個因子矩陣的維度，r為迭代次數(shù).

3.3POI得分轉(zhuǎn)換及推薦

在進行POI推薦時，需將用戶對主題的興趣得分轉(zhuǎn)換為對POI的興趣得分.

根據(jù)得出的POI-主題矩陣，結(jié)合用戶在特定時間下的主題興趣分布(用戶-時間-主題張量)，可計算用戶在特定時間下對于具體POI的興趣分布(用戶-時間-POI).具體步驟為:

1) 采用K維向量P表示用戶在特定時間段對于所有主題的興趣得分，其中pk表示該用戶對于主題k的興趣偏好最終得分，即n和t固定時Yn kt的取值Yn:t；

2) 采用M×K維矩陣Q表示POI-主題分布，其中qmk表示主題k在興趣點m中所占的比重.將K維向量與M×K的轉(zhuǎn)置矩陣進行相乘，得到M維向量F，即用戶在時間t對于全部興趣點的興趣得分.

(un,t):F=P×QT.

若fm為F中的元素，表示用戶un在時間t對于興趣點lm的興趣得分：

(un,t):fm=pk×qmk.

于是，根據(jù)每個用戶的POI得分向量F，選擇得分最高的前N個興趣點進行推薦.

4 實驗與結(jié)果分析

本節(jié)通過在真實數(shù)據(jù)集上進行測試，驗證所提出推薦策略的性能.

4.1實驗數(shù)據(jù)集及評價指標

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

實驗采用來自Twitter提供的WW(world-wide)真實數(shù)據(jù)集，時間區(qū)域從2012-11-01—2013-02-13.

該數(shù)據(jù)集為“用戶簽到數(shù)據(jù)文檔”，每一行包含用戶編號、POI編號、POI經(jīng)緯度、簽到時間和評價信息5個屬性.數(shù)據(jù)集共包含74 938條簽到記錄，其中包含3 883個用戶和49 357個興趣點.我們將其分為訓練集和測試集2部分，其中訓練集包含2012-11-01—2013-01-31數(shù)據(jù)，測試集包含從2013-02-01—2013-02-13的數(shù)據(jù).

2) 評價指標

性能評價指標選用準確率、召回率和平均準確率(mean average precision,MAP)，分別用PRE@N，REC@N，MAP表示，其中N為推薦的POI數(shù)量.

準確率和召回率只是對返回POI推薦列表的正確性進行度量，而未考慮正確結(jié)果在推薦列表中的位置，即正確POI只要在推薦列表中出現(xiàn)就認為推薦正確;而評價指標MAP則是對準確率的進一步精準度量,該指標除考慮推薦結(jié)果的正確性之外，還考慮推薦正確的POI在推薦列表中的位置,若正確推薦結(jié)果在推薦列表中的位置越靠前，則MAP值就越高.

給定用戶u，在時間片段t下的準確率PRE@N(t)、召回率REC@N(t)和MAP(t)的計算如式(15)所示：

其中，Top_N(u)代表算法獲取的Top-N興趣點推薦列表;L(u)代表用戶測試集中用戶去過的興趣點列表;Top_N(u)∩L(u)代表Top-N推薦列表和測試集列表的交集，即正確推薦列表;locn(Top_N(u)∩L(u))代表在Top-N列表中第n個興趣點在推薦正確列表中的位置值.注意，在Top-N列表中但不在推薦正確列表中的locn(Top_N(u)∩L(u))=0.

整個算法的各項評價指標是所有時間段中各項指標的平均值.本文選取3種相關(guān)POI推薦算法進行比較：基于簽到信息的矩陣分解法(CMF)[9],主題及位置感知法(TLA)[5]和用戶-位置-時間張量分解法(ULT)[14].

4.2實驗結(jié)果及分析

1) 主題個數(shù)對推薦結(jié)果的影響

在LDA模型中，主題個數(shù)K的選擇直接影響到提取的主題結(jié)構(gòu).然而，選擇最佳主題數(shù)仍然是其面臨的主要難題[24].已有一些非參數(shù)主題模型提出，即主題個數(shù)隨文檔數(shù)目的變化而相應調(diào)整，而無需事先人為指定.但是，這些模型大都較為復雜，且效果也不理想.目前常用的方法是通過設置不同的K值，訓練后驗證比較求得主題個數(shù)的最佳值.

本實驗分別取K=40，60，80，100，120時，驗證UZT算法的性能，結(jié)果如圖6所示.可以看出，對于本文的數(shù)據(jù)集，當K=100時，其準確率、召回率及平均準確率均高于其他值.因此主題個數(shù)不是越大越好，而要根據(jù)原始數(shù)據(jù)集所表現(xiàn)的特征確定.后續(xù)設置實驗的主題個數(shù)K=100.

Fig. 6 POI recommendation performance on different numbers of topics圖6 不同主題個數(shù)下的興趣點推薦效果

2) 張量分解秩對推薦的影響

張量分解3個矩陣的秩參數(shù)，即核心張量的維度，決定了張量分解中潛在特征因素的數(shù)目.對于張量秩的確定，目前還沒有方法能夠直接求解任意給定張量的秩，已被證明是一個NP難問題[25].因此，本實驗通過設定不同值，比較后求得秩的最優(yōu)值.

在本文數(shù)據(jù)集中，原始張量維度為3883×24×100，設置其分解的秩為其維度的20%，40%，60%，80%，100%.實驗結(jié)果如圖7所示.可以看出，維度在60%時的性能優(yōu)于其余4種，故本研究將秩設置為原始張量的60%.

Fig. 7 POI recommendation performance on different ranks of tensor圖7 不同秩下的張量分解的興趣點推薦效果

3) 不同推薦算法對比結(jié)果

基于上述實驗參數(shù)，將所提出的UZT算法與所選擇的3種算法進行實驗對比，實驗結(jié)果如圖8所示.可以看出，UZT算法性能均優(yōu)于其余算法.這是由于ULT只考慮了用戶的簽到次數(shù)，未考慮評論信息及用戶的主題權(quán)重；TLA方法雖然考慮了用戶-主題分布，但未考慮用戶興趣的時間感知特征，即認為所有時間的興趣相同；CMF方法只能處理二維數(shù)據(jù)，計算得到的用戶偏好準確度較低.

4) 時間粒度對推薦效果的影響

本研究是將簽到數(shù)據(jù)按“小時(hour)”劃分到24個時間片段中，然后按照時間點落在對應時段中推薦.

用戶簽到習慣往往具有一定規(guī)律性，因此，在不同時間表現(xiàn)出來的興趣偏好可能不同.例如，用戶在上午、下午和晚上的簽到習慣不同,周一至周五(周工作日)的簽到習慣與周六、周日(周末)的簽到習慣也不相同.因此，我們將時間粒度進行擴展：

① 針對每天不同時間段用戶的簽到習慣可能不同，將全部簽到數(shù)據(jù)按“時間段(section)”劃分，即劃分為6個時間段(每個時間段為4 h)：[6:00—10:00)，[10:00—14:00)，[14:00—18:00)，[18:00—22:00)，[22:00—2:00)，[2:00—6:00).

② 針對每周內(nèi)每天用戶的簽到習慣可能不同，將全部簽到數(shù)據(jù)按“周天(day of week)”進行劃分，即按周一至周日劃分為7個時間段.

③ 針對每月內(nèi)每天用戶的簽到習慣可能不同，將全部簽到數(shù)據(jù)按“月天(day of month)”進行劃分，即劃分為30個時間段.

圖9的實驗結(jié)果表明，時間粒度劃分得越細，就能夠獲取更為準確的用戶偏好，也就能得到更為準確的推薦結(jié)果.

Fig. 9 POI recommendation performance on time granularity圖9 時間粒度對興趣點推薦效果的影響

5 全文總結(jié)

本文針對基于位置社會網(wǎng)絡提出了一種雙重細粒度POI推薦策略，即將時間劃分為“小時”粒度，POI劃分為“主題”粒度，以獲取更為準確的用戶偏好，從而能實現(xiàn)時間感知的POI推薦.

論文的主要工作包括2部分：利用LDA主題提取模型提取出POI-主題分布，并將其映射為時間感知的用戶-主題偏好分布.為解決數(shù)據(jù)稀疏性問題，運用張量分解算法對得到的初始用戶-主題-時間三階張量進行分解，以獲取更為準確的主題興趣評分，從而實現(xiàn)POI的Top-N推薦.實驗結(jié)果表明，本文所提算法具有較好性能.

本文所研究的時間感知推薦策略是將時間劃分為離散的24個小時進行推薦，未能反映興趣變化的連續(xù)性.因此，下一步我們將研究連續(xù)時間感知策略，進一步提高推薦準確率.

[1]Bobadilla J, Ortega F, Hernando A, et al. Recommender systems survey[J]. Knowledge-Based Systems, 2013, 46(1): 109-132[2]Gao Huiji, Liu Huan. Data analysis on location-based social networks[G]Mobile Social Networking. Berlin: Springer, 2014: 165-194

[3]Bao Jie, Zheng Yu, Wilkie D, et al. Recommendations in location-based social networks: A survey[J]. GeoInformatica, 2015, 19(3): 525-565

[4]Gao Huiji, Tang Jiliang, Hu Xia, et al. Content-aware point of interest recommendation on location-based social networks[C]Proc of the 29th Int AAAI Conf. Menlo Park, CA: AAAI, 2015: 1721-1727

[5]Liu Bin, Xiong Hui. Point-of-interest recommendation in location based social networks with topic and location awareness[C]Proc of the 13th SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2013: 396-404

[6]Ference G, Ye M, Lee W C. Location recommendation for out-of-town users in location-based social networks[C]Proc of the 22nd ACM Int Conf on Information amp; Knowledge Management. New York: ACM, 2013: 721-726

[7]Gao Huiji, Tang Jiliang, Liu Huan. Exploring social-historical ties on location-based social networks[C]Proc of the 6th Int AAAI Conf on Weblogs and Social Media. Menlo Park, CA: AAAI, 2012: 114-121

[8]Yuan Quan, Cong Gao, Ma Zongyang, et al. Time-aware point-of-interest recommendation[C]Proc of the 36th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2013: 363-372

[9]Gao Huiji, Tang Jiliang, Hu Xia, et al. Exploring temporal effects for location recommendation on location-based social networks[C]Proc of the 7th Int ACM Conf on Recommender Systems. New York: ACM, 2013: 93-100

[10]Yuan Quan, Cong Gao, Sun Aixin. Graph-based point-of-interest recommendation with geographical and temporal influences[C]Proc of the 23rd Int ACM Conf on Conf on Information and Knowledge Management. New York: ACM, 2014: 659-668

[11]Ye Mao, Yin Peifeng, Lee Wang-Chien, et al. Exploiting geographical influence for collaborative point-of-interest recommendation[C]Proc of the 34th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2011: 325-334

[12]Liu Bin, Fu Yanjie, Yao Zijun, et al. Learning geographical preferences for point-of-interest recommendation[C]Proc of the 19th Int ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 1043-1051

[13]Cheng Chen, Yang Haiqin, King I, et al. Fused matrix factorization with geographical and social influence in location-based social networks[C]Proc of the 26th Int AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2012: 17-23

[14]Yao Lina, Sheng Quanzheng, Qin Yongrui, et al. Context-aware point-of-interest recommendation using tensor factorization with social regularization[C]Proc of the 38th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2015: 1007-1010

[15]Bao Jie, Zheng Yu, Mokbel M F. Location-based and preference-aware recommendation using sparse geo-social networking data[C]Proc of the 20th Int Conf on Advances in Geographic Information Systems. New York: ACM, 2012: 199-208

[16]Noulas A, Scellato S, Lathia N, et al. Mining user mobility features for next place prediction in location-based services[C]Proc of the 12th Int Conf on Data Mining. Piscataway, NJ: IEEE, 2012: 1038-1043

[17]Noulas A, Scellato S, Mascolo C, et al. An empirical study of geographic user activity patterns in foursquare[C]Proc of 5th Int AAAI Conf on Weblogs and Social Media (ICWSM). Menlo Park, CA: AAAI, 2011: 570-573

[18]Li Xutao, Cong Gao, Li Xiao Li, et al. Rank-GeoFM: A ranking based geographical factorization method for point of interest recommendation[C]Proc of the 38th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2015: 433-442

[19]Gao Huij, Tang Jiliang, Hu Xia, et al. Modeling temporal effects of human mobile behavior on location-based social networks[C]Proc of the 22nd Int ACM Conf on Information amp; Knowledge Management. New York: ACM, 2013: 1673-1678

[20]Ifada N, Nayak R. Tensor-based item recommendation using probabilistic ranking in social tagging systems[C]Proc of the 23rd Int Conf on World Wide Web. New York: ACM, 2014: 805-810

[21]Yuan Q, Cong G, Ma Z, et al. Who, where, when and what: Discover spatio-temporal topics for Twitter users[C]Proc of the 19th Int ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 605-613

[22]Liu Bin, Xiong Hui, Papadimitriou S, et al. A general geographical probabilistic factor model for point of interest recommendation[J]. IEEE Trans on Knowledge and Data Engineering, 2015, 27(5): 1167-1179

[23]Cao Jiuxin, Dong Yi, Yang Pengwei, et al. POI recommendation based on meta-path in LBSN[J]. Chinese Journal of Computers, 2016, 39(4): 676-684 (in Chinese)(曹玖新, 董羿, 楊鵬偉, 等. LBSN中基于元路徑的興趣點推薦[J]. 計算機學報, 2016, 39(4): 676-684)

[24]Cao Juan, Zhang Yongdong, Li Jintao, et al. A method of adaptively selecting best LDA model based on density[J]. Chinese Journal of Computers, 2008, 31(10): 1780-1787 (in Chinese)(曹娟, 張勇東, 李錦濤, 等. 一種基于密度的自適應最優(yōu)LDA模型選擇方法[J]. 計算機學報, 2008, 31(10): 1780-1787)

[25]Anandkumar A, Ge R, Hsu D, et al. Tensor decompositions for learning latent variable models[J]. Journal of Machine Learning Research, 2014, 15(1): 2773-2832

LiaoGuoqiong, born in 1969. PhD. Professor and PhD supervisor at the School of Information Technology, Jiangxi University of Finance and Economics. Senior member of CCF. His main research interests include databases, data mining and social networks.

JiangShan, born in 1991. Master candidate at the School of Information Technology, Jiangxi University of Finance and Economics. Her main research interests include data mining and social networks.

ZhouZhiheng, born in 1993. Master candidate at the School of Information Technology, Jiangxi University of Finance and Economics. His main research interests include data mining and social networks.

WanChangxuan, born in 1962. PhD. Professor and PhD supervisor at the School of Information Technology, Jiangxi University of Finance and Economics. Senior member of CCF. His main research interests include Web data management and Web information retrieval.

DualFine-GranularityPOIRecommendationonLocation-BasedSocialNetworks

Liao Guoqiong1,2, Jiang Shan1, Zhou Zhiheng1, and Wan Changxuan1,2

1(School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013)2(Jiangxi Province Key Laboratory of Data and Knowledge Engineering (Jiangxi University of Finance and Economics), Nanchang 330013)

Point of interest recommendation is a new form of popular recommendation in location-based social network (LBSN). Utilizing the rich information contained in the LBSN to do personalized recommendation can enhance user experience effectively and enhance user’s dependence on LBSN. Facing the challenging problems in LBSN, such as no explicit user preferences, non-consistency of interest, the sparseness of data, and so on, a dual fine-granularity POI recommendation strategy is proposed, of which, on the one hand, the historical check-in information of each user is divided into 24 time periods in hours; on the other hand, each POI is divided into a number of potential topics and distribution. Both the information of user’s check-in and comments are used to mine user’s topic preference in different time periods for Top-Nrecommendation of the POIs. In order to achieve the recommendation ideas, first of all, according to the comments information on the visited POIs, we use LDA topic generation model to extract the topic distribution of each POI. Secondly, for each user, we divide each user’s check-in data into 24 time periods, and connect it with the topic distribution of the corresponding POIs to map user interest preference on each topic in different periods. Finally, in order to solve the issue of data sparse, we use higher order singular value decomposition algorithm to decompose the third-order tensor of user-topic-time to get more accurate interest score of users on each topic in all time periods. The experiments on a real dataset show that the proposed approach outperforms the state-of-the-art POI recommendation methods.

POI recommendation; location-based social network (LBSN); LDA topic model; interest mapping; tensor factorization

2016-07-11；

2016-12-15

國家自然科學基金項目(61772245,61262009)；江西省自然科學基金項目(20151122040083)；江西省優(yōu)勢科技創(chuàng)新團隊建設計劃項目(20113BCB24008)；江西省教育廳重點科技項目(GJJ160419)

This work was supported by the National Natural Science Foundation of China (61772245,61262009), the Natural Science Foundation of Jiangxi Province of China (20151122040083), the Superiority Science and Technology Innovation Team Building Program of Jiangxi Province (20113BCB24008), and the Science Foundation of Jiangxi Provincial Department of Education of China (GJJ160419).

(liaoguoqiong@163.com)

TP181