協同過濾算法在位置推薦上的運用

王森 林勤花

摘 要：隨著信息技術的普及與移動互聯網的發展，用戶每年都會產生海量的數據，目前我們已經進入了大數據時代。面對海量數據，如何尋找感興趣的信息已經成為困擾用戶的問題。由于每個人的興趣愛好不太相同，使用一個大眾版的排行榜并不能滿足每個人的需求。位置推薦算法就是在大量數據作為支撐的情況下，對用戶進行相似性計算，最后根據相似用戶的簽到地點做出推薦。本文主要通過經典的協同過濾方式實現一個位置推薦算法。

關鍵詞：海量數據;位置推薦;協同過濾

隨著移動互聯網的興起，用戶可以方便快捷地記錄當前的位置坐標，產生了許多有名的軟件，比如微博、forsqure、ins等。Foursquare作為位置信息服務的巨頭，目前積累了超過80億的簽到數據，全球每天都有用戶使用該軟件用來分享他們的生活。通過這些位置社交軟件，用戶對他們去過的地點進行簽到，同時可以分享視頻、音樂、圖片等信息。本文以新加坡簽到數據為例，對經典的協同過濾算法進行了位置推薦方面的實現。

一、相關知識

（一）基于位置的社交網絡

基于位置的社交網絡（Location-Based Social Networks，簡稱為LBSN）是在社交網絡的基礎上融合了位置服務的一種新的社交模式。這種新的模式不僅將用戶和用戶進行了聯系（這種聯系包括同學、同事、家人等），也將用戶與地點進行了聯系，形成了一個更加深層次的社交網絡。隨著智能手機的廣泛運用，用戶可以隨時通過GPS定位自己的位置，這種基于位置的軟件也越來越廣泛地被人們使用，因此產生了大量的基于位置的軟件，foursqure就是其中之一。

（二）Foursquare

Foursquare是Dennis Crowley于2009年在美國創立的基于用戶位置信息的網站，用于使用戶方便深入了解當地，并可對當地景點或餐廳等進行評分。目前已在全球積累了海量的用戶。

二、協同過濾算法

（一）協同過濾算法公式介紹

相似的用戶往往會有相同的興趣，因此位置推薦算法常用的方式是先計算出每個用戶的相似用戶，再根據相似用戶對相關地點進行推薦。

推薦算法中最經典的就是協同過濾算法。假設用U表示與當前用戶最相似的用戶組，用L來表示用戶簽到的地點集合， 則是指某個用戶（這里用i表示）在某個地點（用j來表示）進行簽到的概率，則該概率的計算公式如公式3-1所示：

這里的? 表示是用戶? 在是否曾經去過地點j， 值零表示該用戶未曾去過j，有值說明該用戶去過。 是指用戶K和用戶i之間的相似性，具體計算公式如公式3-2所示：

（二）協同過濾算法在LBSN上的運用

下面通過一個小實驗來說明基于位置的協同過濾推薦算法是如何工作的，假設 ??的值只能是0和1。1代表去過該地點而0代表沒有去過，具體的簽到矩陣如表1所示。

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

最終可算出用戶相似性矩陣如表2所示。通過用戶兩兩之間的相識程度，可以找到每個用戶最相似的N個用戶，通過最相似的N個用戶的簽到情況即可進行推薦，即使用公式3-1計算用戶在某個地點的簽到可能性，很明顯簽到可能性最好的地點就是我們最終的推薦結果。

以用戶A為例，假設采用最相似的兩個用戶進行位置推薦，則用戶A最相似的用戶是B和C。通過公式可以算出：

可以看出????? >????? ，說明在歷史數據的基礎上用戶A去景點1的可能性要大于景點4，最終的推薦結果是景點1而不是景點4。

三、通過foursquare數據進行實驗

（一）foursquare數據集介紹

本文實驗中使用的數據是Foursquare數據集。該數據是位置推薦算法相關領域常用的經典數據集，是新加坡學者在2010年與2011年之間收集的新加坡簽到數據，Foursquare上2010年8月～2011年7月新加坡的簽到記錄，共計342，850條。

（二）實驗過程

首先將數據集合按照80%和20%的數據劃分為訓練集和測試集，然后計算每個用戶的相似用戶，最后根據相似用戶去過的地點推薦得分最佳的地點。通過最終的實驗，我們完成了協同過濾算法在位置推薦上的運用。

四、結束語

面對海量的數據，用戶越來越難以獲取感興趣的信息，通過推薦算法可以較好地完成該任務。本文介紹了經典的協同過濾算法，并且介紹了該算法如何在位置推薦服務上使用。最后我們計劃通過一個網頁實現對數據可視化展示。

參考文獻

[1] 宋亞偉，司亞利，劉文遠，等. 融合時間特征和協同過濾的興趣點推薦算法[J].小型微型計算機系統，2016，37（6）：1153-1158.

[2] 劉袁柳.面向LBSN的興趣點和用戶推薦方法研究[D].蘇州大學，2015.

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