王森 林勤花

摘 要：隨著信息技術(shù)的普及與移動(dòng)互聯(lián)網(wǎng)的發(fā)展，用戶(hù)每年都會(huì)產(chǎn)生海量的數(shù)據(jù)，目前我們已經(jīng)進(jìn)入了大數(shù)據(jù)時(shí)代。面對(duì)海量數(shù)據(jù)，如何尋找感興趣的信息已經(jīng)成為困擾用戶(hù)的問(wèn)題。由于每個(gè)人的興趣愛(ài)好不太相同，使用一個(gè)大眾版的排行榜并不能滿(mǎn)足每個(gè)人的需求。位置推薦算法就是在大量數(shù)據(jù)作為支撐的情況下，對(duì)用戶(hù)進(jìn)行相似性計(jì)算，最后根據(jù)相似用戶(hù)的簽到地點(diǎn)做出推薦。本文主要通過(guò)經(jīng)典的協(xié)同過(guò)濾方式實(shí)現(xiàn)一個(gè)位置推薦算法。

關(guān)鍵詞：海量數(shù)據(jù);位置推薦;協(xié)同過(guò)濾

隨著移動(dòng)互聯(lián)網(wǎng)的興起，用戶(hù)可以方便快捷地記錄當(dāng)前的位置坐標(biāo)，產(chǎn)生了許多有名的軟件，比如微博、forsqure、ins等。Foursquare作為位置信息服務(wù)的巨頭，目前積累了超過(guò)80億的簽到數(shù)據(jù)，全球每天都有用戶(hù)使用該軟件用來(lái)分享他們的生活。通過(guò)這些位置社交軟件，用戶(hù)對(duì)他們?nèi)ミ^(guò)的地點(diǎn)進(jìn)行簽到，同時(shí)可以分享視頻、音樂(lè)、圖片等信息。本文以新加坡簽到數(shù)據(jù)為例，對(duì)經(jīng)典的協(xié)同過(guò)濾算法進(jìn)行了位置推薦方面的實(shí)現(xiàn)。

一、相關(guān)知識(shí)

（一）基于位置的社交網(wǎng)絡(luò)

基于位置的社交網(wǎng)絡(luò)（Location-Based Social Networks，簡(jiǎn)稱(chēng)為L(zhǎng)BSN）是在社交網(wǎng)絡(luò)的基礎(chǔ)上融合了位置服務(wù)的一種新的社交模式。這種新的模式不僅將用戶(hù)和用戶(hù)進(jìn)行了聯(lián)系（這種聯(lián)系包括同學(xué)、同事、家人等），也將用戶(hù)與地點(diǎn)進(jìn)行了聯(lián)系，形成了一個(gè)更加深層次的社交網(wǎng)絡(luò)。隨著智能手機(jī)的廣泛運(yùn)用，用戶(hù)可以隨時(shí)通過(guò)GPS定位自己的位置，這種基于位置的軟件也越來(lái)越廣泛地被人們使用，因此產(chǎn)生了大量的基于位置的軟件，foursqure就是其中之一。

（二）Foursquare

Foursquare是Dennis Crowley于2009年在美國(guó)創(chuàng)立的基于用戶(hù)位置信息的網(wǎng)站，用于使用戶(hù)方便深入了解當(dāng)?shù)?，并可?duì)當(dāng)?shù)鼐包c(diǎn)或餐廳等進(jìn)行評(píng)分。目前已在全球積累了海量的用戶(hù)。

二、協(xié)同過(guò)濾算法

（一）協(xié)同過(guò)濾算法公式介紹

相似的用戶(hù)往往會(huì)有相同的興趣，因此位置推薦算法常用的方式是先計(jì)算出每個(gè)用戶(hù)的相似用戶(hù)，再根據(jù)相似用戶(hù)對(duì)相關(guān)地點(diǎn)進(jìn)行推薦。

推薦算法中最經(jīng)典的就是協(xié)同過(guò)濾算法。假設(shè)用U表示與當(dāng)前用戶(hù)最相似的用戶(hù)組，用L來(lái)表示用戶(hù)簽到的地點(diǎn)集合， 則是指某個(gè)用戶(hù)（這里用i表示）在某個(gè)地點(diǎn)（用j來(lái)表示）進(jìn)行簽到的概率，則該概率的計(jì)算公式如公式3-1所示：

這里的? 表示是用戶(hù)? 在是否曾經(jīng)去過(guò)地點(diǎn)j， 值零表示該用戶(hù)未曾去過(guò)j，有值說(shuō)明該用戶(hù)去過(guò)。 是指用戶(hù)K和用戶(hù)i之間的相似性，具體計(jì)算公式如公式3-2所示：

（二）協(xié)同過(guò)濾算法在LBSN上的運(yùn)用

下面通過(guò)一個(gè)小實(shí)驗(yàn)來(lái)說(shuō)明基于位置的協(xié)同過(guò)濾推薦算法是如何工作的，假設(shè) ??的值只能是0和1。1代表去過(guò)該地點(diǎn)而0代表沒(méi)有去過(guò)，具體的簽到矩陣如表1所示。

通過(guò)表1可知，用戶(hù)A去過(guò)景點(diǎn)B、景點(diǎn)C，用戶(hù)B則去過(guò)景點(diǎn)A、景點(diǎn)D。通過(guò)協(xié)同過(guò)濾算法，首先需要用公式3-2算出用戶(hù)兩兩之間的相似性，以用戶(hù)A為例：

最終可算出用戶(hù)相似性矩陣如表2所示。通過(guò)用戶(hù)兩兩之間的相識(shí)程度，可以找到每個(gè)用戶(hù)最相似的N個(gè)用戶(hù)，通過(guò)最相似的N個(gè)用戶(hù)的簽到情況即可進(jìn)行推薦，即使用公式3-1計(jì)算用戶(hù)在某個(gè)地點(diǎn)的簽到可能性，很明顯簽到可能性最好的地點(diǎn)就是我們最終的推薦結(jié)果。

以用戶(hù)A為例，假設(shè)采用最相似的兩個(gè)用戶(hù)進(jìn)行位置推薦，則用戶(hù)A最相似的用戶(hù)是B和C。通過(guò)公式可以算出：

可以看出????? >????? ，說(shuō)明在歷史數(shù)據(jù)的基礎(chǔ)上用戶(hù)A去景點(diǎn)1的可能性要大于景點(diǎn)4，最終的推薦結(jié)果是景點(diǎn)1而不是景點(diǎn)4。

三、通過(guò)foursquare數(shù)據(jù)進(jìn)行實(shí)驗(yàn)

（一）foursquare數(shù)據(jù)集介紹

本文實(shí)驗(yàn)中使用的數(shù)據(jù)是Foursquare數(shù)據(jù)集。該數(shù)據(jù)是位置推薦算法相關(guān)領(lǐng)域常用的經(jīng)典數(shù)據(jù)集，是新加坡學(xué)者在2010年與2011年之間收集的新加坡簽到數(shù)據(jù)，F(xiàn)oursquare上2010年8月～2011年7月新加坡的簽到記錄，共計(jì)342，850條。

（二）實(shí)驗(yàn)過(guò)程

首先將數(shù)據(jù)集合按照80%和20%的數(shù)據(jù)劃分為訓(xùn)練集和測(cè)試集，然后計(jì)算每個(gè)用戶(hù)的相似用戶(hù)，最后根據(jù)相似用戶(hù)去過(guò)的地點(diǎn)推薦得分最佳的地點(diǎn)。通過(guò)最終的實(shí)驗(yàn)，我們完成了協(xié)同過(guò)濾算法在位置推薦上的運(yùn)用。

四、結(jié)束語(yǔ)

面對(duì)海量的數(shù)據(jù)，用戶(hù)越來(lái)越難以獲取感興趣的信息，通過(guò)推薦算法可以較好地完成該任務(wù)。本文介紹了經(jīng)典的協(xié)同過(guò)濾算法，并且介紹了該算法如何在位置推薦服務(wù)上使用。最后我們計(jì)劃通過(guò)一個(gè)網(wǎng)頁(yè)實(shí)現(xiàn)對(duì)數(shù)據(jù)可視化展示。

參考文獻(xiàn)

[1] 宋亞偉，司亞利，劉文遠(yuǎn)，等. 融合時(shí)間特征和協(xié)同過(guò)濾的興趣點(diǎn)推薦算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2016，37（6）：1153-1158.

[2] 劉袁柳.面向LBSN的興趣點(diǎn)和用戶(hù)推薦方法研究[D].蘇州大學(xué)，2015.

[3] 周翔宇，高仲合.基于地理位置和用戶(hù)行為特征的推薦算法研究[J].通信技術(shù)，2019，52（8）：1928-1931.