基于位置服務(wù)的潛在好友推薦方法

符饒

摘要：有效的潛在好友推薦是促進(jìn)社交網(wǎng)絡(luò)不斷增長(zhǎng)的重要途徑，基于位置的社交網(wǎng)絡(luò)（LBSN）支持用戶隨時(shí)隨地記錄自己所處的位置以及分享身邊發(fā)生的事，用戶通過簽到生成的地理位置信息構(gòu)成了用戶的行為軌跡。文章提出了一種利用用戶簽到信息的潛在好友推薦方法，不同于傳統(tǒng)的只考慮簽到位置信息的方法，文章中的方法還考慮了簽到的時(shí)間以及簽到的次數(shù)。方法首先將簽到的時(shí)間信息及空間信息壓縮，然后進(jìn)一步通過計(jì)算用戶之間的相似度來決定向目標(biāo)用戶推薦的潛在好友。相似度主要決定于用戶之間的重合點(diǎn)數(shù)量、近似點(diǎn)數(shù)量以及簽到點(diǎn)集大小。文章最后使用大型位置服務(wù)社交網(wǎng)絡(luò)Gowalla的真實(shí)用戶訪問數(shù)據(jù)，以準(zhǔn)確率與召回率作為評(píng)價(jià)標(biāo)準(zhǔn)，證明了本文使用的方法在效果上優(yōu)于傳統(tǒng)的使用位置信息的潛在好友推薦方法。

關(guān)鍵詞：好友推薦；位置服務(wù)；用戶相似度；簽到數(shù)據(jù)

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

0 引言

隨著移動(dòng)智能終端的普及和移動(dòng)互聯(lián)網(wǎng)的發(fā)展，社交網(wǎng)絡(luò)也在移動(dòng)互聯(lián)網(wǎng)上得到了迅猛的發(fā)展。用戶可以以多種方式隨時(shí)隨地接入移動(dòng)社交網(wǎng)絡(luò)，用戶之間可以方便地相互聯(lián)系，分享自己身邊發(fā)生的事情。

社交網(wǎng)絡(luò)能夠如此活躍的原因，除了能夠幫助用戶維護(hù)現(xiàn)實(shí)生活中的社交關(guān)系，更重要的是幫助用戶發(fā)現(xiàn)與自己志趣相投的新朋友。因此，潛在的好友推薦功能是每個(gè)社交網(wǎng)站所必備的，并且該功能應(yīng)該具備一定的準(zhǔn)確性。

根據(jù)用戶的好友網(wǎng)絡(luò)拓?fù)溥M(jìn)行推薦，算法首先通過用戶好友之間的距離選出潛在好友候選人，然后再?gòu)暮蜻x人中選出與用戶興趣相同的人作為用戶的潛在好友進(jìn)行推薦?；谟脩舻呐d趣特征計(jì)算設(shè)計(jì)了通用的潛在的好友框架。通過計(jì)算用戶資料之間的相似性來推薦潛在的好友。以上的研究都利用了當(dāng)前存在的好友網(wǎng)絡(luò)拓?fù)鋱D，為用戶推薦的好友可以簡(jiǎn)單的概括為朋友的朋友或是有相同興趣愛好的人。

基于位置的社交網(wǎng)絡(luò)服務(wù)，是利用GPS、蜂窩網(wǎng)、WLAN等技術(shù)獲得移動(dòng)終端的地理位置信息，支持用戶隨時(shí)隨地自由記錄并分享地理位置等信息。用戶可以通過任意類型的移動(dòng)終端上的專用軟件簽到所處位置信息，并且告知朋友。簽到行為的發(fā)生在用戶行為的研究上引發(fā)了一個(gè)新的維度。用戶與位置的交互數(shù)據(jù)第一次被引入到研究當(dāng)中，提供了空前的機(jī)會(huì)來理解用戶怎樣動(dòng)態(tài)的通過位置和線上的朋友交互。

1 相關(guān)工作

傳統(tǒng)的推薦系統(tǒng)使用得最多的方法就是協(xié)同過濾，協(xié)同過濾是利用集體智慧的一個(gè)典型方法。該算法分析用戶興趣，在用戶群中找到與指定用戶有相似興趣的用戶，綜合這些相似用戶對(duì)某一信息的評(píng)價(jià)，形成系統(tǒng)對(duì)該指定用戶對(duì)此信息的喜好程度預(yù)測(cè)。協(xié)同過濾算法主要是向用戶推薦其可能感興趣的物品。

對(duì)于潛在好友的推薦大致上可以分為兩類，一類是“你可能認(rèn)識(shí)的”，一類是“你可能感興趣的”。第一類算法主要是通過分析目標(biāo)用戶的好友網(wǎng)絡(luò)，社交網(wǎng)絡(luò)用戶之間主要存在兩種關(guān)系：強(qiáng)關(guān)系和弱關(guān)系。強(qiáng)關(guān)系指一級(jí)人脈，即兩個(gè)用戶是好友關(guān)系。弱關(guān)系指二級(jí)人脈，即用戶與用戶的關(guān)系通過用戶產(chǎn)生，也就是說兩個(gè)用戶有共同好友，即為弱關(guān)系用戶。SNS中的弱關(guān)系往往具有長(zhǎng)尾性，能夠帶來巨大的經(jīng)濟(jì)效益。把目標(biāo)用戶的弱關(guān)系用戶推薦給他的強(qiáng)關(guān)系用戶，但沒有給目標(biāo)用戶進(jìn)行弱關(guān)系用戶的好友推薦。主要工作是對(duì)目標(biāo)用戶進(jìn)行熱點(diǎn)用戶的推薦，沒有考慮目標(biāo)用戶個(gè)人興趣，對(duì)潛在的弱關(guān)系用戶進(jìn)行推薦。我們將弱關(guān)系用戶看成是目標(biāo)用戶的候選推薦用戶，根據(jù)目標(biāo)用戶與候選推薦用戶的共同好友數(shù)量，確定兩個(gè)用戶相互關(guān)聯(lián)的程度。共同好友數(shù)量越多，說明兩個(gè)用戶關(guān)聯(lián)程度越高，就越有可能認(rèn)識(shí)，因此我們按照這個(gè)關(guān)聯(lián)程度向目標(biāo)用戶推薦好友。但是兩個(gè)用戶共同認(rèn)識(shí)的好友數(shù)量多，只能說明兩個(gè)用戶在現(xiàn)實(shí)生活中有可能是認(rèn)識(shí)的，卻不能說明推薦的用戶是目標(biāo)用戶感興趣的用戶。

第二類算法主要是通過分析用戶資料當(dāng)中的相似性，如兩個(gè)用戶就讀于同一所學(xué)校，年齡相近，或是從用戶的標(biāo)簽中提取出關(guān)鍵詞，分析兩個(gè)用戶的興趣愛好是否相似等以作為向目標(biāo)用戶推薦的依據(jù)。這種推薦算法是從全局的社交網(wǎng)絡(luò)入手的，具有一定的參考價(jià)值，但由于用戶所提供的內(nèi)容有限，并且部分用戶可能會(huì)提供虛假信息，因此這種推薦有一定的局限性。

隨著基于位置的社交網(wǎng)絡(luò)服務(wù)的興起，用戶可以隨時(shí)隨地的記錄自己的位置以及分享身邊的事。而用戶簽到的時(shí)間與地點(diǎn)是一個(gè)能反映用戶行為的重要信息。目前已經(jīng)有不少通過位置信息分析用戶行為的研究。文獻(xiàn)分析出用戶的簽到次數(shù)并不會(huì)隨著用戶好友數(shù)的增加而增加。主要分析位置服務(wù)社交網(wǎng)絡(luò)當(dāng)中用戶的行為，這其中的用戶行為包括用戶喜歡在什么時(shí)間簽到以及用戶喜歡訪問哪些地點(diǎn)。通常的基于位置信息的好友推薦算法都只考慮了用戶之間簽到位置的相似性，本文提出的算法不僅考慮了用戶之間簽到位置的相似性，還引入了簽到時(shí)間及簽到次數(shù)對(duì)好友推薦效果的影響。

2 好友推薦方法

本文使用大型位置服務(wù)社交網(wǎng)站Gowalla的真實(shí)用戶訪問數(shù)據(jù)，設(shè)計(jì)基于用戶歷史簽到的地理位置信息的好友推薦算法。算法首先對(duì)用戶簽到的時(shí)間信息及空間信息進(jìn)行壓縮，進(jìn)而將用戶的歷史簽到數(shù)據(jù)映射到二維平面上，將求解兩個(gè)用戶之間的相似性問題轉(zhuǎn)化為幾何上求解兩個(gè)點(diǎn)集之間的相似性問題。

2.1數(shù)據(jù)描述

研究大型的線上社交網(wǎng)絡(luò)通常是件困難的事，因?yàn)橛脩舻臄?shù)據(jù)都被社交網(wǎng)絡(luò)服務(wù)提供者有效的保護(hù)起來，一般人很難獲取。因此隨機(jī)化的爬蟲仍然是目前唯一的有效獲取數(shù)據(jù)的方式。我們研究的數(shù)據(jù)來自于大型位置服務(wù)社交網(wǎng)絡(luò)Gowalla。

2.1.1數(shù)據(jù)集特征

在我們的數(shù)據(jù)集當(dāng)中，并非每位用戶都是活躍用戶。所謂活躍用戶就是至少有過一次簽到行為的用戶。數(shù)據(jù)集中共包含了107092位活躍用戶。數(shù)據(jù)集的一些統(tǒng)計(jì)特性見表1。其中包括活躍用戶總數(shù)、簽到位置總數(shù)、簽到總次數(shù)、每個(gè)位置平均被簽到次數(shù)以及每個(gè)用戶的平均簽到次數(shù)。

2.2算法描述

從數(shù)據(jù)集中發(fā)現(xiàn)，當(dāng)兩個(gè)用戶是好友時(shí)，往往他們之間的簽到距離比較近，好友之間的共同簽到地點(diǎn)與非好友之間的共同簽到地點(diǎn)相比，好友之間的共同簽到地點(diǎn)大約為14個(gè)，而非好友之間的簽到地點(diǎn)大約為4個(gè)，前者大約是后者的三倍。由此可以看出，用戶的地理特征和社交關(guān)系互為補(bǔ)充。由此可知，地理位置信息能夠十分有效的反映用戶之間的好友關(guān)系，進(jìn)而可以有效的向目標(biāo)用戶推薦潛在好友。算法主要是從兩個(gè)用戶簽到的次數(shù)以及簽到的位置兩個(gè)因素來評(píng)估兩個(gè)用戶是否有可能成為好友。

2.2.1時(shí)空信息預(yù)處理

若兩個(gè)用戶在相近的時(shí)間、相近的地點(diǎn)產(chǎn)生簽到行為，并且發(fā)生該行為的次數(shù)越多，說明兩個(gè)用戶越有可能成為好友。然而，由于社交網(wǎng)絡(luò)上用戶規(guī)模非常大，若兩個(gè)用戶需要精確匹配每次發(fā)生簽到的時(shí)間、地點(diǎn)，計(jì)算量是相當(dāng)龐大的，因此，本文首先考慮對(duì)用戶簽到的時(shí)間、地點(diǎn)進(jìn)行壓縮，以減少計(jì)算量。

首先從時(shí)間上來說，我們只關(guān)心用戶在幾時(shí)幾分產(chǎn)生了簽到行為，但是不關(guān)心產(chǎn)生簽到行為的具體日期。我們僅僅將日期劃分成工作日與節(jié)假日兩類，因?yàn)榇蟛糠钟脩舻男袨閮H僅只在這兩種類別的日期上有明顯差異。

進(jìn)一步，我們按照普通人的生活習(xí)慣將一天劃分為7個(gè)時(shí)段，分別是：

（1）23：00～7：00，休息時(shí)間

（2）7：00～8：30，工作準(zhǔn)備時(shí)間

（3）8：30～12：00，上午工作時(shí)間

（4）12：00～13：30，午休時(shí)間

（5）13：30～17：30，下午工作時(shí)間

（6）17：30～20：00，回家及晚飯時(shí)間

（7）20：00～23：00，夜晚生活時(shí)間

這樣一來，我們就將時(shí)間信息劃分成了14個(gè)類別，大大的壓縮了時(shí)間維度的信息量，減少了計(jì)算量。在表2中我們統(tǒng)計(jì)了各個(gè)時(shí)間段的簽到數(shù)量的分布。

可以看出簽到時(shí)間最多的時(shí)間段是23：00～7：00，也就是休息時(shí)間，我們?cè)龠M(jìn)一步分解這個(gè)時(shí)間段發(fā)現(xiàn)，23：00～1：00簽到的數(shù)量占比為47.4%，1：00～6：00簽到的數(shù)量占比為16.1%，而6：00～7：00簽到的數(shù)量占比為36.4%?？梢钥闯龃蟛糠秩硕剂?xí)慣于在睡前或起床時(shí)使用手機(jī)。

由于在某一地理位置附近，可能有很多不同的簽到點(diǎn)，用戶訪問相近的地理位置時(shí)并不一定是在同一個(gè)簽到點(diǎn)上簽到，僅通過判斷用戶是否訪問同一個(gè)簽到點(diǎn)來計(jì)算得到用戶間的相似性是趨近于零的。因此，需要對(duì)用戶簽到的位置進(jìn)行聚類。

2.2.2用戶相似度計(jì)算

我們基于上述討論，使用一個(gè)量化的值來評(píng)估兩個(gè)用戶之間是否有可能成為好友，我們將這個(gè)值稱為用戶的相似度。對(duì)于用戶的每一次簽到，我們知道其簽到時(shí)間及簽到地點(diǎn)，可以將信息映射到二維空間當(dāng)中，以時(shí)間作為橫軸，以地點(diǎn)作為縱軸，每個(gè)用戶的簽到行為就可以看成是二維平面上的一個(gè)點(diǎn)集。我們需要做的就是評(píng)估兩個(gè)用戶簽到點(diǎn)集的相似性。

定義1：簽到點(diǎn)集（Checking Point Set，CPS），由用戶的簽到數(shù)據(jù)映射到二維平面形成的點(diǎn)集。

定義2：重合點(diǎn)（Common Point，CP），若兩條簽到記錄發(fā)生的時(shí)間段及區(qū)域相同，則稱這兩條簽到記錄映射的點(diǎn)為重合點(diǎn)。

定義3：近似點(diǎn)（Similarity Point，SP），若兩條簽到記錄發(fā)生的時(shí)間段不同，但區(qū)域相同，則稱這兩條簽到記錄映射的點(diǎn)為近似點(diǎn)。

用戶簽到的次數(shù)是用戶性格的一種表征，表3是用戶簽到次數(shù)的分布。

從表中我們可以看出，絕大部份用戶兩年時(shí)間僅僅簽到不到400次，簽到最多的一個(gè)用戶共簽到2175次，平均一天3次左右。因此，不同性格的人會(huì)在簽到次數(shù)上有所不同。該項(xiàng)因素為相似度的一個(gè)弱影響項(xiàng)，所以有w₃1且w₃2。

重合點(diǎn)的數(shù)量是反映兩個(gè)用戶相似最重要的指標(biāo)，因?yàn)槊恳粋€(gè)重合點(diǎn)都代表兩個(gè)用戶在同一個(gè)時(shí)間段，在同一個(gè)地點(diǎn)發(fā)生過一次簽到行為，因此他們有可能在此時(shí)此刻發(fā)生了同樣的行為。在這一項(xiàng)使用指數(shù)函數(shù)是基于下面這樣的考慮，兩個(gè)用戶如果只有很少的幾個(gè)重合點(diǎn)，那么這兩個(gè)用戶有可能只是偶然產(chǎn)生了相同的行為，但隨著兩個(gè)用戶重合點(diǎn)的數(shù)量增多，兩個(gè)用戶就越有可能有著相似的生活習(xí)慣，因此相似度應(yīng)該隨著重合點(diǎn)數(shù)量的上升而上升，并且上升趨勢(shì)是先慢后快。

近似點(diǎn)的數(shù)量也是相似度的一個(gè)強(qiáng)影響項(xiàng)，兩個(gè)用戶有較多的近似點(diǎn)，說明兩個(gè)用戶經(jīng)常出現(xiàn)在相近的位置，但是這只能說明他們之間可能會(huì)受到相同環(huán)境的影響，但卻不能說明他們之間的生活習(xí)性相近，因此該影響項(xiàng)沒有重合點(diǎn)的影響力大，因此有w₁>w₂。

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

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

目前常用來評(píng)估推薦算法的指標(biāo)有：準(zhǔn)確率（precision）、召回率（recall）及F1指標(biāo)。準(zhǔn)確率指檢索出的相關(guān)信息量占檢索出的總信息量的百分比。召回率指檢索出的相關(guān)信息量占相關(guān)信息總量的百分比。F1指標(biāo)是根據(jù)準(zhǔn)確率與召回率得出的一項(xiàng)綜合評(píng)價(jià)指標(biāo)。它們的定義如下：

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

本文使用上述算法計(jì)算用戶之間的相似度，并對(duì)目標(biāo)用戶進(jìn)行Top-N推薦，隨著N值的變化，所有用戶的平均準(zhǔn)確率、平均召回率及平均F1指標(biāo)均會(huì)變化。下面將本文提出的算法與傳統(tǒng)的只考慮用戶簽到位置的好友推薦算法進(jìn)行比較。從圖1與圖2中可以看出，本文算法在準(zhǔn)確率及召回率上都要優(yōu)于傳統(tǒng)算法。

4 結(jié)論

本文使用位置服務(wù)社交網(wǎng)絡(luò)Gowalla的真實(shí)用戶訪問數(shù)據(jù)，提出了基于用戶位置信息的潛在好友推薦算法。算法首先將時(shí)間信息及空間信息壓縮，然后將用戶的簽到數(shù)據(jù)映射到二維空間中，將用戶的相似度計(jì)算轉(zhuǎn)化為求平面上兩個(gè)點(diǎn)集的相似度。兩個(gè)用戶的相似度主要受重合點(diǎn)數(shù)量、相似點(diǎn)數(shù)量以及簽到數(shù)據(jù)集大小的影響。文章最后使用準(zhǔn)確率與召回率作為評(píng)價(jià)指標(biāo)，將本文算法與傳統(tǒng)的只考慮用戶簽到位置信息的好友推薦算法進(jìn)行比較，證明本文算法在準(zhǔn)確率及召回率上都優(yōu)于傳統(tǒng)算法。