曹瑛典

研究背景

在大數(shù)據(jù)時代，面臨數(shù)據(jù)海量、多樣性和價值稀疏性等特點，能不能用某種方法快速找到與自己興趣愛好相投的新朋友呢？能不能利用大數(shù)據(jù)分析解決潛在好友推薦的問題呢？

移動定位社交服務(wù)的出現(xiàn)為人們提供了一種全新的交友方式。這類應(yīng)用通過將用戶的位置數(shù)據(jù)在地圖上可視化，讓用戶相互分享生活經(jīng)歷，結(jié)交新的朋友。潛在好友和位置推薦作為移動定位社交服務(wù)中最重要的一個功能，已經(jīng)被應(yīng)用到很多交友軟件當(dāng)中。但是，現(xiàn)有的一些交友軟件的推薦功能仍然存在不足，推薦的潛在好友很多在現(xiàn)實生活中沒有交集，與自己真正想要找到的朋友相差甚遠；微信通過“附近的人”這一功能向用戶推薦潛在好友，但該方法只是根據(jù)用戶之間的距離遠近進行推薦，找到的所謂“好友”與用戶往往沒有相同的興趣愛好。

現(xiàn)有推薦方案的問題

現(xiàn)有的一些潛在好友及位置推薦系統(tǒng)主要局限于用戶的網(wǎng)絡(luò)行為。這些研究的注意力主要集中在用戶的網(wǎng)絡(luò)行為上，卻忽略了用戶在現(xiàn)實世界中的位置等信息。與網(wǎng)絡(luò)行為相比，用戶的現(xiàn)實行為更能體現(xiàn)出用戶的喜好和社會屬性。通過對比現(xiàn)有社交應(yīng)用軟件的潛在好友及位置推薦方案，單一的使用位置數(shù)據(jù)或用戶網(wǎng)絡(luò)行為進行推薦已經(jīng)無法提高推薦成功率。因此，本文根據(jù)用戶歷史位置數(shù)據(jù)結(jié)合詞頻逆文本頻率（Term Frequency Inverse Document Frequency，TF-IDF）算法思想計算用戶的相似性，進而發(fā)現(xiàn)用戶的興趣位置，挖掘用戶的愛好特點，最后實現(xiàn)潛在好友及位置推薦，提高推薦準確性。

本文的主要研究內(nèi)容包括：挖掘用戶停留位置；計算相似用戶；通過計算對停留位置的訪問頻率提取用戶感興趣的位置，為用戶位置推薦提供數(shù)據(jù)源；從前三步得到的相似用戶列表和用戶興趣位置列表選取符合條件的結(jié)果為用戶推薦潛在好友和位置。

算法思想與設(shè)計

整體架構(gòu)

算法的整體架構(gòu)和實現(xiàn)流程如圖1所示。首先從用戶的原始位置數(shù)據(jù)中挖掘其停留區(qū)域，并從停留區(qū)域中挖掘用戶的停留位置；然后采用TF-IDF算法計算出用戶之間的相似性，并通過計算用戶對于不同停留位置的訪問頻率，得出用戶感興趣的位置；最后從得到的相似用戶列表和用戶興趣位置列表選取符合條件的結(jié)果，為用戶推薦潛在好友和位置。

用戶停留位置挖掘和相似性算法

原始的GPS位置數(shù)據(jù)對于用戶而言意義并不大。因為一般人外出購物或者旅游時都會表述自己“要去”某一具體地點，而不會指出該地點的經(jīng)緯度。同時，原始的GPS位置數(shù)據(jù)由于數(shù)據(jù)量大從而加大了算法處理難度。為了彌補這些缺陷，本文從原始的GPS位置數(shù)據(jù)中挖掘用戶的停留區(qū)域。

由于挖掘出的用戶停留區(qū)域范圍太大，無法將其直接應(yīng)用于用戶的相似計算中，因此進一步從停留區(qū)域中挖掘停留位置，縮小原始位置數(shù)據(jù)的范圍。停留位置是指用戶活動的實際地點，即某用戶在某區(qū)域內(nèi)停留的時間超過某一特定閾值時，即為該用戶的停留位置。

停留位置可以分為3種情況：情況一，某用戶會經(jīng)常從不同方向經(jīng)過某一地點；情況二，某用戶進入某一建筑一段時間后再從該建筑出來；情況三，某用戶在某地段以很慢的速度行走。

用戶的停留位置包括其中心點及相鄰的鄰居點，這些鄰居點數(shù)據(jù)中隱藏著用戶的停留位置，據(jù)此設(shè)計了停留位置挖掘算法。

上述算法中處理停留位置的中心點是通過計算用戶周邊所有鄰居點的平均值得出，這樣將會導(dǎo)致同一個停留位置而位置數(shù)據(jù)卻不一樣。為了提高用戶相似計算的有效性，本文將停留位置的中心進行了標準化處理。

計算結(jié)果有時會給出2種停留位置不一致，但實際上是同一個位置的情況。在圖2（a）中，用戶A和B都在同一道路上移動，而A與B由于速度不一樣或者軌跡序列之間的距離間隙導(dǎo)致A與B的停留位置中心不一致；在圖2（b）中，A與B都是圍繞同一建筑移動，但是由于A與B移動的方向不同或者移動距離不一致導(dǎo)致停留位置中心不一致。

為了避免圖2中的情況影響用戶相似計算的有效性，將鄰近的停留位置合并，取合并后的中心作為新的停留位置。假設(shè)每個停留位置都有一個范圍r，以鄰居點的平均值為圓心，半徑r畫圓，當(dāng)鄰近的2個停留位置所畫的圓相交時，將這2個圓代表的停留位置中心合并成1個新的中心，并且用這個新的中心作為用戶的停留位置。

進行用戶相似計算時，本文借鑒了TF-IDF算法的思想。

本文中將每個停留位置中心對應(yīng)成文本中的一個詞，不同的停留位置中心對用戶的重要性不同，因此利用TF-IDF算法計算停留位置中心對用戶的重要性。由此得到每個用戶的相似用戶列表。

用戶興趣位置提取

根據(jù)地理學(xué)第一定律，地理位置和用戶的行為具有重要關(guān)聯(lián)關(guān)系。為了提取用戶興趣位置，需要對沒有語義的原始GPS數(shù)據(jù)進行處理。通過百度地圖API將由經(jīng)緯度構(gòu)成的GPS原始數(shù)據(jù)映射為現(xiàn)實中具有語義的地理位置名稱，如某學(xué)校、某餐廳等。

接著通過計算用戶停留位置的興趣度獲取用戶的興趣位置列表。用戶對某一停留位置訪問越頻繁，代表用戶對這個位置興趣度越髙。

潛在好友與位置推薦策略

令潛在好友推薦。經(jīng)過用戶相似計算后，獲得指定用戶的相似用戶列表，在此基礎(chǔ)上使用相似矩陣表示用戶之間的相似度。經(jīng)過該處理后用戶之間相似值的取值范圍為[〇，1]。當(dāng)需要查詢某個用戶的相似用戶時，只需要查詢該用戶的行向量即可找到相似用戶列表，根據(jù)該列表中的相似值大小給指定用戶推薦潛在好友。

位置推薦。位置推薦主要是為用戶提供符合其愛好的場所，并且這些場所是該用戶從未訪問過的。由于相似用戶的社會屬性相近，即相似的人會表現(xiàn)出相近的行為特點、愛好等，因此反過來通過用戶相似計算，可以發(fā)現(xiàn)用戶潛在的感興趣位置。

實驗及結(jié)果分析

挖掘停留位置實驗

本文的實驗數(shù)據(jù)來自微軟亞洲研究院（Microsoft Research Asia）的GeoLife項目，該項目從2007年4月到2012年8月的5年時間里，采集了182名志愿者的GPS位置數(shù)據(jù)。采集器每隔1?5秒或者5?10米記錄一次用戶的GPS坐標點，共有2400多萬條記錄。endprint

GPS位置數(shù)據(jù)在采集過程中受用戶的活動規(guī)律、活動范圍等因素的影響，每個用戶采集的數(shù)據(jù)集大小不一致。本文從MSData中選取記錄條數(shù)在9萬?50萬的3個用戶（0號、5號、112號用戶），他們分別采集了173870、109046、90565個GPS點，將GPS位置數(shù)據(jù)在地圖上進行了可視化，如圖3所示。從該圖中可以看出3個用戶的數(shù)據(jù)分布大致相同，但是數(shù)據(jù)密度完全不同。

本文針對0號、5號、112號用戶的原始數(shù)據(jù)集做了多次實驗，完成對算法參數(shù)的設(shè)定，從而計算出這3個用戶的停留區(qū)域。

用戶相似計算實驗

用戶相似計算第一步將所有用戶的停留位置中心進行標準化處理。在合并之前，由于采集的數(shù)據(jù)過于密集，導(dǎo)致很多停留位置會重疊。通過將停留位置合并后，減少了重疊的停留位置，不同的停留位置能更精確地代表其特定的區(qū)域范圍，有利于用這些標準化處理后的停留位置計算用戶之間的相似值。

為了驗證用戶相似計算算法的理論，本文選取與指定用戶相似值最大和最小的用戶停留位置在地圖上顯示，對比其停留位置的重合率。通過實驗分析可以得出每一個用戶的相似用戶列表，該用戶經(jīng)過的地點與其他用戶越相似，用戶之間的相似值越大，他們的相似性越高。

結(jié)論與創(chuàng)新點

本文采用大數(shù)據(jù)分析技術(shù)，針對原始數(shù)據(jù)集進行數(shù)據(jù)清洗，引入TF-IDF算法思想，改進用戶相似計算方法，提髙檢測用戶興趣位置的準確性，提出全新的潛在好友與位置推薦策略，最終在建立用戶相似矩陣的基礎(chǔ)上，實現(xiàn)了潛在好友和位置的精準推薦。

本文通過一系列實驗對提出的算法和策略思想進行了驗證，通過實驗分析

證明了潛在好友和位置推薦框架的精準和有效。

本文的主要創(chuàng)新點是：采用TF-IDF算法實現(xiàn)在位置大數(shù)據(jù)中相似用戶的挖掘；首次提出將停留位置中心進行標準化，采用余弦定理計算用戶相似度。該方法具有耗時短、占用資源少、高效的特點；用此方法可探索出基于用戶相似計算的潛在好友及位置推薦策略。

該項目獲得第31屆全國青少年科技創(chuàng)新大賽創(chuàng)新成果競賽項目中學(xué)組計算機科學(xué)一等獎。

專家評語

該項目選題具有先進性和新穎性。作者依據(jù)“喜歡在同一地點停留的人具有某種相同的興趣或行為習(xí)慣”的假設(shè)，通過對用戶的地理位置信息進行挖掘，找出興趣或習(xí)慣相近的人進行推薦。這是一種比較新穎并有效的方法，值得嘗試，值得注意的是，該方法要在大多數(shù)人愿意共享位置信息時才有效。整個工作比較完整，答辯表述清楚，回答問題切題。endprint