云環(huán)境中基于海量簽到數(shù)據(jù)的并行地點(diǎn)推薦算法研究

金寧+欒方軍+師金鋼

摘要：目的：提出一種基于MapReduce架構(gòu)的并行推薦算法，提高在超大規(guī)模且結(jié)構(gòu)復(fù)雜的數(shù)據(jù)集中的推薦效率。方法：在MapReduce并行計(jì)算模型中分析用戶訪問真實(shí)地理位置的行為軌跡，將用戶的簽到行為量化為用戶對簽到地點(diǎn)的喜好程度，綜合分析用戶間的相同簽到記錄及不同用戶對簽到地點(diǎn)的偏好程度，計(jì)算用戶間的相似性，實(shí)現(xiàn)個(gè)性化地點(diǎn)推薦。利用Gowalla和Foutsquare社交網(wǎng)站真實(shí)的簽到數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證。結(jié)果：推薦結(jié)果在召回率及精度上均優(yōu)于傳統(tǒng)的協(xié)同過濾推薦算法且具有較高的加速比。結(jié)論：該推薦算法具有良好的可擴(kuò)展性及高效的執(zhí)行性能，能夠適用于云計(jì)算環(huán)境中針對海量數(shù)據(jù)的推薦。

關(guān)鍵詞：推薦系統(tǒng)；云計(jì)算；基于位置服務(wù)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）36-0012-02

1 基于海量簽到數(shù)據(jù)的推薦算法

在基于位置的社交網(wǎng)絡(luò)中，如果兩個(gè)用戶是好友，那么他們在相同地點(diǎn)簽到次數(shù)是兩個(gè)陌生用戶的三倍，說明了用戶間的地理位置特征與其社會(huì)關(guān)系互相補(bǔ)充. 用戶的每次簽到行為都具有一定意義，用戶的每個(gè)簽到記錄能夠反映其偏好，在同一地點(diǎn)進(jìn)行簽到的用戶之間具有某種共性。

2 基于MapReduce架構(gòu)的并行推薦系統(tǒng)模型

2.1 并行推薦框架

MapReduce是Google 公司首先提出的一種能在大型計(jì)算機(jī)集群上并發(fā)處理海量數(shù)據(jù)的分布式計(jì)算框架模型。它是一種簡化的分布式編程模式，以充分發(fā)揮廉價(jià)計(jì)算機(jī)集群的計(jì)算能力，以解決單一普通計(jì)算機(jī)由于處理器以及存儲(chǔ)資源的限制而無法有效處理海量數(shù)據(jù)計(jì)算的問題。該模型會(huì)解決輸入數(shù)據(jù)的分布細(xì)節(jié)，跨越機(jī)器集群的程序執(zhí)行調(diào)度，處理機(jī)器失效問題，并且管理機(jī)器之間的通訊請求。對大規(guī)模數(shù)據(jù)的計(jì)算過程可以簡化為Map 和Reduce兩大基本操作，Map就是將一個(gè)任務(wù)分解成為多個(gè)任務(wù)，Reduce就是將分解后多任務(wù)處理的結(jié)果匯總起來，得出最終的分析結(jié)果。初始狀態(tài)下，數(shù)據(jù)集進(jìn)行劃分并存儲(chǔ)在分布式文件系統(tǒng)中。用戶通過重寫自己的Map函數(shù)處理初始的數(shù)據(jù)key/value 對，產(chǎn)生一系列的中間key/value 對，并且使用重寫的Reduce 函數(shù)將具有相同key 值的中間鍵值對聚集起來進(jìn)行處理，最后將結(jié)果輸出。

Map （k1，v1） → list（k2，v2）

Reduce （k2，list（v2）） → list（k3，v3）

Hadoop是Apache 開源社區(qū)開發(fā)的一個(gè)MapReduce的Java 實(shí)現(xiàn)，提供了在由通用計(jì)算設(shè)備組成的大型集群上執(zhí)行分布式應(yīng)用的框架。圖1 展示了在Hadoop計(jì)算中的數(shù)據(jù)流向，Hadoop將輸入數(shù)據(jù)分為N個(gè)Split，啟動(dòng)相應(yīng)的N個(gè)Map 函數(shù)應(yīng)用到輸入數(shù)據(jù)的不同分塊上，輸出key/value值對；然后通過merge 過程對中間鍵值對進(jìn)行分配，將相同key 值的所有鍵值對發(fā)送到同一Reduce 節(jié)點(diǎn)上；最后Reduce 計(jì)算過程被觸發(fā)，對相同key 的鍵值對列表進(jìn)行處理，將最終的結(jié)果輸出到分布式文件系統(tǒng)HDFS（hadoop distributed file system）中。

2.2 海量簽到數(shù)據(jù)存儲(chǔ)

Gowalla和Foutsquare提供的簽到數(shù)據(jù)格式為，將海量簽到數(shù)據(jù)以分塊的形式存儲(chǔ)到HDFS分布式文件存儲(chǔ)系統(tǒng)中，導(dǎo)入的數(shù)據(jù)格式為txt文本格式。HDFS具有高容錯(cuò)性，為了保證數(shù)據(jù)的安全和高效，存入的簽到數(shù)據(jù)均備份副本，保證了數(shù)據(jù)的魯棒性。

2.3 相似度計(jì)算與推薦算法

簽到地點(diǎn)對用戶偏好的貢獻(xiàn)度計(jì)算構(gòu)建過程如下：其中CheckinDate為用戶的簽到數(shù)據(jù)信息，包括用戶編號(hào)user_id，簽到地點(diǎn)point_id，用戶的簽到數(shù)checkin_num等。

Map階段。將簽到數(shù)據(jù)作為輸入，Map函數(shù)根據(jù)CheckinDate數(shù)據(jù)格式特點(diǎn)，按照偏移量提取< point_id，（ user_id+ checkin_num）>鍵值對作為輸出。

Reduce階段。Reduce的輸入為< point_id，list（ user_id+ checkin_num）>記錄列表，將point_id作為key值，將相同key值的簽到數(shù)據(jù)分配給同一個(gè)Reduce任務(wù).Reduce函數(shù)分別累加兩個(gè)變量pn、un，對每個(gè)新出現(xiàn)的point_id同時(shí)對pn、un加1，對每個(gè)已現(xiàn)的point_id僅對pn加1，對每個(gè)user_id的pn除以對應(yīng)的checkin_num求得簽到頻率，將用戶總數(shù)N除以un并取對數(shù)，然后將兩結(jié)果相乘計(jì)算得出簽到地點(diǎn)對其偏好的貢獻(xiàn)度pw.Reduce階段輸出格式為<（ point_id+ user_id）， pw >。

用戶相似性計(jì)算階段的MapReduce構(gòu)建過程中，首先計(jì)算在一個(gè)地點(diǎn)的相似性，然后匯總在各地的相似值，計(jì)算出用戶間相似度，具體構(gòu)建過程為：

Map階段。輸入鍵值對為， Map函數(shù)比較用戶間pw，計(jì)算出用戶間在該點(diǎn)的相似性Sim（m，n，c），其輸出形式為

Reduce階段。該階段重新分配Map階段的輸出，以< user_m+user_n >作為復(fù)合鍵，將相同< user_m+user_n >的任務(wù)分配到同一個(gè)Reduce函數(shù)，累加其在各簽到地點(diǎn)的相似值，并按照相似值度高低排序，其輸出的鍵值對表示為：，其中samelist（point_id）為相同的簽到序列用于下階段地點(diǎn)推薦。

地點(diǎn)推薦階段首先讀取用戶的簽到序列，按對用戶偏好貢獻(xiàn)度排序輸出，得到推薦地點(diǎn)序列，其MapReduce構(gòu)建過程為：

Map階段。Map函數(shù)讀取user_m相似度最高的用戶user_n的簽到序列并按照pw排序，其輸出形式為。

Reduce階段。Reduce函數(shù)判斷point_id是否在samelist（point_id）中，如不在，則將point_id輸出，得到推薦序列鍵值對< user_id ，recommend（point_id）>

本階段在MapReduce架構(gòu)下實(shí)現(xiàn)了并行協(xié)同過濾推薦算法，整個(gè)構(gòu)建過程功能劃分明確，各階段依次銜接，上一次MapReduce的輸出即為下一次的輸入。

3 實(shí)驗(yàn)分析

為了評估基于MapReduce架構(gòu)的并行地點(diǎn)推薦算法的性能，將基于MapReduce架構(gòu)的并行推薦方法與傳統(tǒng)的協(xié)同過濾推薦方法在推薦準(zhǔn)確度及執(zhí)行效率上進(jìn)行了實(shí)驗(yàn)，對實(shí)驗(yàn)結(jié)果進(jìn)行了分析討論。

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中搭建了一個(gè)由7臺(tái)電腦組成的計(jì)算機(jī)集群，其中一臺(tái)作為master控制幾點(diǎn)，其余6臺(tái)作為slaver計(jì)算節(jié)點(diǎn)，每臺(tái)電腦搭配Inter酷睿 i3 CPU，2G內(nèi)存，操作系統(tǒng)為Ubuntu10.10，Hadoop版本為1.0.4.實(shí)驗(yàn)測試采用Gowalla和Foursquare社交網(wǎng)站真實(shí)的簽到數(shù)據(jù)集，包括美國舊金山市2009 年3 月到2010 年10月的155254條簽到記錄。

3.2 推薦結(jié)果準(zhǔn)確度評價(jià)

實(shí)驗(yàn)采用多次實(shí)驗(yàn)方法，抽取一定比例的用戶簽到數(shù)據(jù)作為訓(xùn)練集，余下的位置作為測試集，使用召回率和精度模型驗(yàn)證。從表1和表2中結(jié)果可以看出，本文提出的MR-CF算法的推薦效果優(yōu)于采用余弦相似度的傳統(tǒng)協(xié)同過濾推薦算法CF，說明簽到行為可以體現(xiàn)出用戶的偏好，將用戶的位置信息作為新的考慮因素添加到推薦系統(tǒng)中可以為用戶提供更加有效、符合用戶個(gè)性化需求的地點(diǎn)推薦，提高推薦的準(zhǔn)確度。

4 結(jié)論

針對云計(jì)算環(huán)境中海量數(shù)據(jù)的推薦問題，提出了一種基于MapReduce架構(gòu)的并行協(xié)同過濾地點(diǎn)推薦算法，將地理位置信息加入傳統(tǒng)推薦算法中，并在Hadoop應(yīng)用框架上設(shè)計(jì)了相應(yīng)的并行推薦模式。實(shí)驗(yàn)證明，基于MapReduce架構(gòu)的并行協(xié)同過濾地點(diǎn)推薦在推薦精度、應(yīng)時(shí)間及對大數(shù)據(jù)集的適應(yīng)上表現(xiàn)較好，具有良好的可擴(kuò)展性和高效的執(zhí)行性能，適用于云計(jì)算環(huán)境中針對海量數(shù)據(jù)的推薦。文章的相似度計(jì)算算法并不是很完善，在今后的研究組將進(jìn)行改進(jìn)。

參考文獻(xiàn)：

[1] Sheng C， Zheng Y， Hsu W， et al. Answering Top-k Similar Region Queries[C]. In Database Systems for Advanced Applications. 2010： 186-201.

[2] 榮鑫. 基于地理位置的社交網(wǎng)絡(luò)潛在用戶和位置推薦模型研究[D]. 南京郵電大學(xué)， 2013.