左甜甜

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

?

社交網(wǎng)絡(luò)簽到地點分類

左甜甜

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

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

簽到地點；分類；DBSCAN；KNN

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

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

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

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

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

一、基于DBSCAN的地點聚類

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

(一)DBSCAN算法流程

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

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

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

(二)對簽到地點數(shù)據(jù)中的經(jīng)緯度應(yīng)用DBSCAN算法

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

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

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

(一)KNN算法流程

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

2.k值的選?。和ǔＨ∮?xùn)練集樣本數(shù)量的平方根，或通過實驗的準確率確定k值。

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

(二)對未簽到地點數(shù)據(jù)應(yīng)用KNN算法

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

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

三、分類模型的現(xiàn)實意義

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

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

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

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

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

[3]黃文,王正林.數(shù)據(jù)挖掘:R語言實戰(zhàn)[M].電子工業(yè)出版社,2014:111-120.

[4]BrettLantz.機器學(xué)習(xí)與R語言[J].2015:82-95.

[5]Java獲取Map地圖經(jīng)緯度與所處地理名稱相互轉(zhuǎn)化.http://yegshine.blog.163.com

左甜甜(1993-)，女，滿族，遼寧鐵嶺市人，工科碩士，沈陽理工大學(xué)通信與信息系統(tǒng)專業(yè)，研究方向：移動無線網(wǎng)絡(luò)技術(shù)。