協(xié)同過濾算法在位置推薦上的運(yùn)用

王森 林勤花

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

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

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

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

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

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

（二）Foursquare

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

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

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

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

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

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

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

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

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

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

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

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

三、通過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)過程

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

四、結(jié)束語

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

參考文獻(xiàn)

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

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

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