LBSN中基于并行圖的協(xié)同過濾位置推薦算法研究
發(fā)布時間：2018-12-17 16:50
【摘要】：在互聯(lián)網(wǎng)高速發(fā)展的今天,推薦系統(tǒng)能夠緩解用戶篩選感興趣內(nèi)容時的困擾,幫助用戶發(fā)現(xiàn)有價值信息,已成為解決信息過載的有效手段。推薦系統(tǒng)中的協(xié)同過濾算法,因其領(lǐng)域無關(guān)性及支持用戶發(fā)現(xiàn)潛在興趣的優(yōu)點(diǎn)被廣泛應(yīng)用。隨著智能手機(jī)和地理位置服務(wù)的普及,基于位置的社會化網(wǎng)絡(luò)(Location-based Social Network,LBSN)被社交網(wǎng)絡(luò)服務(wù)應(yīng)用商提出并受到大眾的歡迎。LBSN可以實(shí)時獲取用戶的地理位置信息,并將在虛擬網(wǎng)絡(luò)中傳播的虛擬信息與用戶在真實(shí)世界中的位置信息有效結(jié)合起來。為了解決LBSN中位置推薦的需求,學(xué)術(shù)界和工業(yè)界將協(xié)同過濾算法應(yīng)用到LBSN的位置推薦中來。LBSN中的位置推薦一方面可以幫助普通用戶篩選感興趣的新地點(diǎn),另一方面可以協(xié)助商家進(jìn)行自身品牌推廣與營銷。但是,由于當(dāng)前LBSN中數(shù)據(jù)具有規(guī)模過大且異構(gòu)、多維度的特點(diǎn),使得當(dāng)前提出的應(yīng)用于LBSN中的協(xié)同過濾位置推薦算法在算法實(shí)時性、推薦精確度等方面仍有較大提升空間。具體的,考慮時間、地點(diǎn)的實(shí)時位置推薦,本文完成了如下工作:(1)通過建立基于圖的評分?jǐn)?shù)據(jù)模型,將傳統(tǒng)的協(xié)同過濾算法與并行圖計算框架及改進(jìn)的K近鄰(K-nearest Neighbors,KNN)算法結(jié)合,提出了 GK-CF(Graph KNN Collaborative Filtering)算法。通過圖的消息傳播及改進(jìn)的相似度計算模型對用戶先進(jìn)行篩選再做相似度計算;以用戶-項(xiàng)目二部圖的節(jié)點(diǎn)結(jié)構(gòu)為基礎(chǔ),通過圖的最短路徑算法進(jìn)行待評分項(xiàng)目的快速定位。(2)在GK-CF算法的基礎(chǔ)上,結(jié)合了 LBSN中的時空信息,進(jìn)一步提出了 LBSN中結(jié)合時空信息的協(xié)同過濾位置推薦算法LGP-CF(Location Graph Place Collaborative Filtering)。根據(jù)用戶簽到行為規(guī)律,將數(shù)據(jù)集分片,降低需要計算的數(shù)據(jù)規(guī)模。通過聚類算法獲取相似用戶集,縮小相似用戶集選擇范圍。將軌跡數(shù)據(jù)及點(diǎn)數(shù)據(jù)結(jié)合起來進(jìn)行相似度計算。最后,在根據(jù)經(jīng)緯度信息將位置進(jìn)行聚類的基礎(chǔ)上,快速可靠定位可推薦位置集。(3)通過Spark平臺上的GraphX并行圖框架對上述算法進(jìn)行了并行化實(shí)現(xiàn)及優(yōu)化。通過算法流程優(yōu)化及性能調(diào)優(yōu),有效的提高了算法的可擴(kuò)展性和實(shí)時性能。在真實(shí)的物理集群環(huán)境下,對上述算法進(jìn)行了實(shí)驗(yàn),結(jié)果表明,與其他的協(xié)同過濾算法相比,在rmse、準(zhǔn)確率、召回率等指標(biāo)上,本文提出的算法顯示了很好的推薦準(zhǔn)確度和評分預(yù)測的準(zhǔn)確性,在加速比等指標(biāo)上也表明本文算法具有較好的可擴(kuò)展性和實(shí)時性能。
[Abstract]:With the rapid development of the Internet, the recommendation system can alleviate the puzzlement of the users when they filter the content of interest, and help the users to find valuable information. It has become an effective means to solve the information overload. Collaborative filtering algorithms in recommendation systems are widely used because of their domain independence and the advantages of supporting users to discover potential interests. With the popularity of smartphones and geolocation services, location-based social networks (Location-based Social Network,LBSN) have been proposed by social networking service providers and are popular with the public. LBSN can access users' geographic location information in real time. The virtual information propagated in the virtual network is effectively combined with the location information of the user in the real world. In order to solve the need of location recommendation in LBSN, academia and industry apply collaborative filtering algorithm to the location recommendation of LBSN. On the one hand, the location recommendation in LBSN can help ordinary users to filter out new sites of interest. On the other hand, it can help merchants to promote their own brand and marketing. However, due to the large scale, heterogeneity and multi-dimension of the data in current LBSN, the proposed collaborative filtering location recommendation algorithm for LBSN still has much room for improvement in real-time and recommendation accuracy. Specifically, considering the real-time location recommendation of time and location, this paper has completed the following work: (1) through the establishment of graph-based scoring data model, By combining the traditional collaborative filtering algorithm with the parallel graph computing framework and the improved K nearest neighbor (K-nearest Neighbors,KNN) algorithm, the GK-CF (Graph KNN Collaborative Filtering) algorithm is proposed. Through the message propagation of graph and the improved similarity calculation model, the users are filtered first and then the similarity is calculated. Based on the node structure of the user-item bipartite graph, the shortest path algorithm of the graph is used to locate the item to be graded quickly. (2) based on the GK-CF algorithm, the spatio-temporal information in LBSN is combined. Furthermore, a collaborative filtering location recommendation algorithm LGP-CF (Location Graph Place Collaborative Filtering). Based on spatio-temporal information in LBSN is proposed. According to the behavior of user check-in, the data set is partitioned to reduce the size of the data to be calculated. The similar user set is obtained by clustering algorithm, and the selection range of similar user set is reduced. Track data and point data are combined to calculate similarity. Finally, on the basis of the location clustering based on longitude and latitude information, fast and reliable location can be recommended. (3) the above algorithms are parallelized and optimized by using the GraphX parallel graph framework on the Spark platform. The scalability and real-time performance of the algorithm are improved by optimizing the algorithm flow and performance. In the real physical cluster environment, the experimental results show that, compared with other collaborative filtering algorithms, the rmse, accuracy, recall rate and other indicators, The algorithm presented in this paper shows good recommendation accuracy and accuracy of score prediction. The speedup ratio also shows that the proposed algorithm has good scalability and real-time performance.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP391.3
本文編號：2384472
[Abstract]:With the rapid development of the Internet, the recommendation system can alleviate the puzzlement of the users when they filter the content of interest, and help the users to find valuable information. It has become an effective means to solve the information overload. Collaborative filtering algorithms in recommendation systems are widely used because of their domain independence and the advantages of supporting users to discover potential interests. With the popularity of smartphones and geolocation services, location-based social networks (Location-based Social Network,LBSN) have been proposed by social networking service providers and are popular with the public. LBSN can access users' geographic location information in real time. The virtual information propagated in the virtual network is effectively combined with the location information of the user in the real world. In order to solve the need of location recommendation in LBSN, academia and industry apply collaborative filtering algorithm to the location recommendation of LBSN. On the one hand, the location recommendation in LBSN can help ordinary users to filter out new sites of interest. On the other hand, it can help merchants to promote their own brand and marketing. However, due to the large scale, heterogeneity and multi-dimension of the data in current LBSN, the proposed collaborative filtering location recommendation algorithm for LBSN still has much room for improvement in real-time and recommendation accuracy. Specifically, considering the real-time location recommendation of time and location, this paper has completed the following work: (1) through the establishment of graph-based scoring data model, By combining the traditional collaborative filtering algorithm with the parallel graph computing framework and the improved K nearest neighbor (K-nearest Neighbors,KNN) algorithm, the GK-CF (Graph KNN Collaborative Filtering) algorithm is proposed. Through the message propagation of graph and the improved similarity calculation model, the users are filtered first and then the similarity is calculated. Based on the node structure of the user-item bipartite graph, the shortest path algorithm of the graph is used to locate the item to be graded quickly. (2) based on the GK-CF algorithm, the spatio-temporal information in LBSN is combined. Furthermore, a collaborative filtering location recommendation algorithm LGP-CF (Location Graph Place Collaborative Filtering). Based on spatio-temporal information in LBSN is proposed. According to the behavior of user check-in, the data set is partitioned to reduce the size of the data to be calculated. The similar user set is obtained by clustering algorithm, and the selection range of similar user set is reduced. Track data and point data are combined to calculate similarity. Finally, on the basis of the location clustering based on longitude and latitude information, fast and reliable location can be recommended. (3) the above algorithms are parallelized and optimized by using the GraphX parallel graph framework on the Spark platform. The scalability and real-time performance of the algorithm are improved by optimizing the algorithm flow and performance. In the real physical cluster environment, the experimental results show that, compared with other collaborative filtering algorithms, the rmse, accuracy, recall rate and other indicators, The algorithm presented in this paper shows good recommendation accuracy and accuracy of score prediction. The speedup ratio also shows that the proposed algorithm has good scalability and real-time performance.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP391.3
【參考文獻(xiàn)】
相關(guān)期刊論文 前7條
1 鄒本友;李翠平;譚力文;陳紅;王紹卿;;基于用戶信任和張量分解的社會網(wǎng)絡(luò)推薦[J];軟件學(xué)報;2014年12期
2 劉樹棟;孟祥武;;基于位置的社會化網(wǎng)絡(luò)推薦系統(tǒng)[J];計算機(jī)學(xué)報;2015年02期
3 朱夏;宋愛波;東方;羅軍舟;;云計算環(huán)境下基于協(xié)同過濾的個性化推薦機(jī)制[J];計算機(jī)研究與發(fā)展;2014年10期
4 謝娟英;高紅超;;基于統(tǒng)計相關(guān)性與K-means的區(qū)分基因子集選擇算法[J];軟件學(xué)報;2014年09期
5 馬遠(yuǎn)坤;梁永全;劉彤;趙建立;李玉軍;;一種基于數(shù)據(jù)遷移的冷啟動解決算法[J];計算機(jī)工程;2014年04期
6 孫光福;吳樂;劉淇;朱琛;陳恩紅;;基于時序行為的協(xié)同過濾推薦算法[J];軟件學(xué)報;2013年11期
7 賈冬艷;張付志;;基于雙重鄰居選取策略的協(xié)同過濾推薦算法[J];計算機(jī)研究與發(fā)展;2013年05期
相關(guān)碩士學(xué)位論文 前3條
1 吳庭;基于位置的推薦計算:Spark實(shí)現(xiàn)[D];浙江大學(xué);2016年
2 王靜金;基于位置社交網(wǎng)絡(luò)的個性化地點(diǎn)推薦算法研究[D];廈門大學(xué);2014年
3 張亮;基于聚類技術(shù)的推薦算法研究[D];電子科技大學(xué);2012年
，本文編號：2384472
本文鏈接：http://sikaile.net/guanlilunwen/yingxiaoguanlilunwen/2384472.html
最近更新
教材專著
