基于位置社會(huì)網(wǎng)絡(luò)的雙重細(xì)粒度興趣點(diǎn)推薦

廖國(guó)瓊 姜 珊 周志恒 萬(wàn)常選

1(江西財(cái)經(jīng)大學(xué)信息管理學(xué)院 南昌 330013) 2(江西省高校數(shù)據(jù)與知識(shí)工程重點(diǎn)實(shí)驗(yàn)室(江西財(cái)經(jīng)大學(xué)) 南昌 330013)

基于位置社會(huì)網(wǎng)絡(luò)的雙重細(xì)粒度興趣點(diǎn)推薦

廖國(guó)瓊1,2姜 珊1周志恒1萬(wàn)常選1,2

1(江西財(cái)經(jīng)大學(xué)信息管理學(xué)院 南昌 330013)2(江西省高校數(shù)據(jù)與知識(shí)工程重點(diǎn)實(shí)驗(yàn)室(江西財(cái)經(jīng)大學(xué)) 南昌 330013)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 問(wèn)題定義及推薦框架

本文擬研究問(wèn)題為，在給定時(shí)間點(diǎn)向用戶推薦其最感興趣的興趣點(diǎn)，具體如下：

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

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

圖2包括以下步驟：

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

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

3) 張量分解.建立用戶-主題-時(shí)間三維張量，通過(guò)張量分解方法，獲取用戶在24個(gè)時(shí)間段中更為準(zhǔn)確的主題偏好分布.

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

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

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

2.1主題提取

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

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

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

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

1) α和β為語(yǔ)料級(jí)別先驗(yàn)參數(shù)，α代表每個(gè)文檔下主題多項(xiàng)分布的Dirichlet先驗(yàn)參數(shù)，β代表每個(gè)主題下單詞多項(xiàng)分布的Dirichlet先驗(yàn)參數(shù)；

2)θ和φ是隱含變量，θ表示每個(gè)興趣點(diǎn)與主題之間的多項(xiàng)分布，φ表示每個(gè)主題與語(yǔ)料庫(kù)單詞之間的多項(xiàng)分布；

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

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

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

輸入： K、α、POI描述文檔、單詞語(yǔ)料庫(kù)；

輸出：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個(gè)矩陣：

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

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

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

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

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

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

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

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

2.2興趣映射

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

具體步驟如下：

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

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

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

具體興趣映射過(guò)程如下：

1) 統(tǒng)計(jì)每個(gè)用戶在每個(gè)時(shí)間段對(duì)每個(gè)主題所對(duì)應(yīng)的所有興趣點(diǎn)簽到次數(shù)，以及對(duì)于該主題的簽到總次數(shù).

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

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

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

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

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

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

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

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

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

Table 3 Examples of Dealing Standardly表3 標(biāo)準(zhǔn)化處理示例

3 用戶-主題-時(shí)間張量分解

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

3.1UZT模型

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

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

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

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

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

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

其中，“×U”表示張量和矩陣按照U-mode展開(kāi)形式進(jìn)行相乘，下標(biāo)U表示了張量乘以矩陣的方向.“×Z”和“×T”同理.

3.2模型訓(xùn)練求解

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

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

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

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

算法2. UZT算法.

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

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

設(shè)置步長(zhǎng)η；

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

endwhile

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

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

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

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

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

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

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

若fm為F中的元素，表示用戶un在時(shí)間t對(duì)于興趣點(diǎn)lm的興趣得分：

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

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

4 實(shí)驗(yàn)與結(jié)果分析

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

4.1實(shí)驗(yàn)數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

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

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

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

2) 評(píng)價(jià)指標(biāo)

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

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

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

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

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

4.2實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

4) 時(shí)間粒度對(duì)推薦效果的影響

本研究是將簽到數(shù)據(jù)按“小時(shí)(hour)”劃分到24個(gè)時(shí)間片段中，然后按照時(shí)間點(diǎn)落在對(duì)應(yīng)時(shí)段中推薦.

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

① 針對(duì)每天不同時(shí)間段用戶的簽到習(xí)慣可能不同，將全部簽到數(shù)據(jù)按“時(shí)間段(section)”劃分，即劃分為6個(gè)時(shí)間段(每個(gè)時(shí)間段為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).

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

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

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

Fig. 9 POI recommendation performance on time granularity圖9 時(shí)間粒度對(duì)興趣點(diǎn)推薦效果的影響

5 全文總結(jié)

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

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

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

[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中基于元路徑的興趣點(diǎn)推薦[J]. 計(jì)算機(jī)學(xué)報(bào), 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īng)最優(yōu)LDA模型選擇方法[J]. 計(jì)算機(jī)學(xué)報(bào), 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

國(guó)家自然科學(xué)基金項(xiàng)目(61772245,61262009)；江西省自然科學(xué)基金項(xiàng)目(20151122040083)；江西省優(yōu)勢(shì)科技創(chuàng)新團(tuán)隊(duì)建設(shè)計(jì)劃項(xiàng)目(20113BCB24008)；江西省教育廳重點(diǎn)科技項(xiàng)目(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