社交網絡簽到地點分類

左甜甜

(沈陽理工大學 遼寧 沈陽 110159)

?

社交網絡簽到地點分類

左甜甜

(沈陽理工大學 遼寧 沈陽 110159)

隨著4G和Wi-Fi技術的發展，越來越多的定位技術被運用到網絡和智能終端中，對已簽到的地理位置進行分類(如餐廳、商店等)成為基于地理位置的服務應用的重中之重。以Python爬取的新浪微博簽到及互動數據為基礎，以假設的未分類樣本作為對象，將經緯度數據輸入基于Java的改進DBSCAN密度聚類算法，輸出其地理范圍，用基于R語言的機器學習中KNN分類算法建立模型，實現社交網絡簽到地點的分類。

簽到地點；分類；DBSCAN；KNN

位置可以是絕對的地理位置，如經緯度；也可以是相對意義的地理位置，如XX路XX號XX商場附近100米處；還可以是語義上的地理位置，如某某商場。本文以經緯度為切入點，結合已知的簽到地點分類信息對未知的簽到地點進行分類。

其中兩個地點之間的距離采用公式：

C=sin(LatA)*sin(LatB)*cos(LonA-LonB)+cos(LatA)*cos(LatB)

Distance=R*Arccos(C)*Pi/180

LatA、LonA是A點的經度、緯度，LatB、LonB是B點的經度、緯度，R為地球半徑取6371km，Pi取3.14。

一、基于DBSCAN的地點聚類

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)基于密度的聚類算法，它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區域劃分為簇，并可在有“噪聲”的數據中發現任意形狀的聚類。

(一)DBSCAN算法流程

1.如果一個點p的ε鄰域包含多于m個對象，則創建一個p作為核心對象的新簇；

2.尋找并合并核心對象直接密度可達的對象；

3.沒有新點可以更新簇時，算法結束。

(二)對簽到地點數據中的經緯度應用DBSCAN算法

以遼寧省沈陽市的44914個樣本為例，在做過數據清洗之后剩余40967個樣本，取經緯度兩個特征，并將二級分類信息粗劃為一級分類共11種。(參考美團、大眾點評分類信息進行歸類)。由于Java以及R語言對中文處理敏感，因此將一級分類標號1～11替換文字，作為DBSCAN算法的待輸入數據。由于DBSCAN是將候選服務集每一個對象作為核心對象進行密度聚類，但是該應用場景不需要，只需要將未知地點分類的對象作為核心對象即可，所以，應用用Java語言編寫的改進DBSCAN算法。

二、基于KNN的簽到地點分類

KNN(k-NearestNeighbor)鄰近算法，其主要思想是給定測試樣本，基于某種距離度量找出訓練集中與其最靠近的k個訓練樣本，然后基于這k個“鄰居”的信息來進行預測，通常，在分類任務中可使用“投票法”，即選擇這k個樣本中出現最多的類別標記作為預測結果；在回歸任務中可使用“平均法”，即將這k個樣本中出現最多的類別標記作為預測結果；還可基于距離遠近進行加權平均或加權投票，距離越近的樣本權重越大。該場景應用“投票法”。

(一)KNN算法流程

1.計算距離：通常采用歐氏距離與曼哈頓距離。

2.k值的選取：通常取訓練集樣本數量的平方根，或通過實驗的準確率確定k值。

3.準備數據：通常對數據進行0-1標準變換或z-score標準變換。

(二)對未簽到地點數據應用KNN算法

以假設的未知的簽到地點分類樣本作為對象，通過上述DBSCAN算法確定其地理范圍，然后應用基于R語言的KNN算法，通過R語言的CrossTable()命令輸出交叉校驗表，由此表可看出真實分類與預測分類的對比情況以及分類準確率。

通過將遼寧省沈陽市的40967個樣本中抽取4338個樣本作為訓練樣本，將余下樣本分成10份作為測試集進行測試，其平均準確率達到96.7%，由此證明了模型的優秀。

三、分類模型的現實意義

(一)個性化位置推薦。流行位置推薦雖然可以給用戶推薦相應的位置，但這些位置并沒有考慮用戶的個性化信息，即對所有用戶推薦的都是相同的位置。通過找到與自己相似性高的用戶，再根據這些用戶訪問的位置進行推薦網。也可以通過得到位置間的相關性，再根據與用戶經常訪問的位置相關性大的位置進行推薦。

(二)位置活動推薦。當用戶指定一個位置時，可以給用戶推薦在這個位置上發生的最流行的活動，當用戶指定一種活動時，也可以給用戶推薦進行這種活動的最流行的位置叫。可通過矩陣來描述每個位置發生的每種活動的情況，但由于在每個位置可以進行的活動是有限的，而活動的種類卻是非常多的，因此這個矩陣是非常稀疏的，而進行推薦的主要依據就是矩陣中每個元素的數值。

(三)商店位置選擇。為一個新的商店選擇最好的位置是一個很有意義的問題。與傳統的方法不同，基于LBSN中收集到的描述用戶移動的細粒度數據和位置的流行性，給出問題的形式化定義，并從不同特性的角度進行商店位置預測，如密度特性、竟爭特性、區域的流行性等。

[1]楊帆,徐建剛,周亮.基于DBSCAN空間聚類的廣州市區餐飲集群識別及空間特征分析[J].經濟地理,2016,36(10):110-116.

[2]杜蓉.基于豆瓣同城活動的線上線下社交影響研究[J].計算機學報,2014,37(1):238-245.

[3]黃文,王正林.數據挖掘:R語言實戰[M].電子工業出版社,2014:111-120.

[4]BrettLantz.機器學習與R語言[J].2015:82-95.

[5]Java獲取Map地圖經緯度與所處地理名稱相互轉化.http://yegshine.blog.163.com

左甜甜(1993-)，女，滿族，遼寧鐵嶺市人，工科碩士，沈陽理工大學通信與信息系統專業，研究方向：移動無線網絡技術。