基于手機(jī)經(jīng)緯度數(shù)據(jù)的重要位置識(shí)別應(yīng)用研究

王興旺

摘要：在大數(shù)據(jù)背景下，為挖掘手機(jī)與基站交互而產(chǎn)生的經(jīng)緯度數(shù)據(jù)的社會(huì)價(jià)值，在聚類算法的基礎(chǔ)上，提出一種基于局部異常因子LOF的k-means空間聚類算法。試驗(yàn)結(jié)果表明，該算法在去除離群點(diǎn)后，提高了分類識(shí)別準(zhǔn)確度，對(duì)大數(shù)據(jù)集和高維數(shù)據(jù)重要位置識(shí)別上有較理想的效果。

關(guān)鍵詞：聚類;局部異常因子;經(jīng)緯度數(shù)據(jù);重要位置

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2019）08-0053-02

0 引言

隨著移動(dòng)通訊、無(wú)線定位、移動(dòng)互聯(lián)網(wǎng)技術(shù)的高速發(fā)展，在智能手機(jī)及各類APP應(yīng)用日益普及的當(dāng)下，手機(jī)用戶日常生活軌跡網(wǎng)絡(luò)化的程度越來(lái)越高，當(dāng)人們使用手機(jī)瀏覽新聞資訊、接打電話、收發(fā)信息、聊天、游戲時(shí)，手機(jī)與基站之間時(shí)刻發(fā)生即時(shí)通訊，由此產(chǎn)生了大量的空間位置數(shù)據(jù)。

目前，對(duì)手機(jī)用戶軌跡進(jìn)行聚類的研究中，文獻(xiàn)[1]提出對(duì)軌跡點(diǎn)進(jìn)行空間密度聚類，該方法沒(méi)有對(duì)軌跡的離群點(diǎn)進(jìn)行預(yù)處理，只通過(guò)KNN算法對(duì)數(shù)據(jù)進(jìn)行聚類，聚類的區(qū)分度不夠高。文獻(xiàn)[2]將軌跡點(diǎn)轉(zhuǎn)化為線段序列，通過(guò)對(duì)線段序列進(jìn)行聚類來(lái)挖掘熱點(diǎn)路徑，該方法適用于GPS數(shù)據(jù)，對(duì)手機(jī)采集的信令數(shù)據(jù)并不適用。文獻(xiàn)[3]通過(guò)將數(shù)據(jù)序列化網(wǎng)格序列，基于網(wǎng)格進(jìn)行聚類發(fā)現(xiàn)熱點(diǎn)區(qū)域，但基于手機(jī)信息的數(shù)據(jù)量巨大，傳統(tǒng)的聚類方法已經(jīng)不能滿足熱區(qū)挖掘要求。文獻(xiàn)[4]提出了基于DBSCAN的空間聚類算法，處理帶有噪聲的空間位置數(shù)據(jù)，多個(gè)區(qū)域間相差較大，導(dǎo)致聚類質(zhì)量較差?；诖?，本文結(jié)合LOF離群點(diǎn)檢測(cè)算法，提出了基于LOF的k-means空間聚類算法。LOF算法適用于基于不同密度的數(shù)據(jù)集群，通過(guò)利用LOF算法去掉部分異常位置數(shù)據(jù)，再利用聚類算法，找到手機(jī)用戶的幾個(gè)常用的聚集地。經(jīng)過(guò)實(shí)驗(yàn)論證，該算法在處理海量數(shù)據(jù)時(shí)有較好效果。

1 基于LOF+K-means的重要位置識(shí)別算法

1.1 LOF算法

LOF算法作為一種基于密度方法的異常檢測(cè)算法，通過(guò)將數(shù)據(jù)樣本點(diǎn)的可達(dá)密度與其鄰居的平均可達(dá)密度之比作為離群因子，用以識(shí)別離群點(diǎn)。

1.1.1 定義

（1）可達(dá)距離。點(diǎn)o到p的第k可達(dá)距離定義為：

rdk（p，o）=max{k-distance（o），d（p，o）

（2）局部可達(dá)密度。點(diǎn)p的局部可達(dá)密度表示為：

lrdk（p）=1/

該值代表一個(gè)密度，密度越高，認(rèn)為越可能屬于同一簇，密度越低，越可能是離群點(diǎn)。

（3）局部離群因子。點(diǎn)p的局部離群因子表示為：

LOFk（p）==/lrdk（p）

表示點(diǎn)p的鄰域點(diǎn)Nk（p）的局部可達(dá)密度與點(diǎn)p的局部可達(dá)密度之比的平均數(shù)。

1.1.2 異常點(diǎn)判斷

如果局部離群因子越接近1，說(shuō)明p的鄰域點(diǎn)密度差不多，p可能和鄰域同屬一簇;如果這個(gè)比值越小于1，說(shuō)明p的密度高于鄰域點(diǎn)密度，p為密集點(diǎn);如果這個(gè)比值越大于1，說(shuō)明p的密度小于其鄰域點(diǎn)密度，p越可能是異常點(diǎn)。

1.1.3 算法1 LOF算法

輸入：數(shù)據(jù)樣本空間及局部鄰居數(shù)和異常比;（1）設(shè)定局部鄰居數(shù)和異常比，使用LOF算法對(duì)數(shù)據(jù)樣本空間進(jìn)行異常點(diǎn)檢測(cè);（2）根據(jù)1中得到正常點(diǎn)和異常點(diǎn);（3）從數(shù)據(jù)樣本空間中刪除異常點(diǎn)。

1.2 K-means算法

k-means算法是基于劃分的聚類算法，將樣本空間在特征空間下相似的樣本進(jìn)行分類組織的過(guò)程，形成若干個(gè)不相交的簇，使得組內(nèi)距離盡可能小，而組間距離盡可能大。

k-means算法的實(shí)現(xiàn)準(zhǔn)則是選取適當(dāng)?shù)臏?zhǔn)則函數(shù)，是一種發(fā)現(xiàn)這種內(nèi)在結(jié)構(gòu)的技術(shù)，由于不需要標(biāo)注樣本而被稱為無(wú)監(jiān)督學(xué)習(xí)。由于簡(jiǎn)潔和效率而成為所有聚類算法中最廣泛使用的一種算法。給定一個(gè)樣本空間和需要?jiǎng)澐值木垲悢?shù)目k，k由用戶指定，k均值算法根據(jù)某個(gè)距離函數(shù)反復(fù)把樣本歸入到k個(gè)聚類中。

1.3 基于LOF+K-means的重要位置識(shí)別算法

在識(shí)別重要位置時(shí)，由于個(gè)體日常生活、工作中在空間位置移動(dòng)時(shí)，多數(shù)情況下會(huì)在幾個(gè)主要區(qū)域切換，有部分位置因?yàn)榕紶柍霈F(xiàn)，而在數(shù)據(jù)上表現(xiàn)出一定的隨機(jī)性，在識(shí)別特定手機(jī)用戶重要位置時(shí)可以先將這些數(shù)據(jù)剔除，因此，本文考慮將局部異常因子算法結(jié)合k-means算法，達(dá)到識(shí)別出特定手機(jī)用戶的重要位置。

根據(jù)模型輸入數(shù)據(jù)的特征及業(yè)務(wù)特點(diǎn)，可以利用k-means聚類算法，挖掘出每個(gè)手機(jī)用戶的三個(gè)簇（工作地、居住地、其他），再根據(jù)聚類中心與數(shù)據(jù)樣本中距離最近的樣本，標(biāo)注為該手機(jī)用戶的工作地、居住地、其他。

1.4 算法2基于LOF的K-means算法

輸入：數(shù)據(jù)樣本空間、局部鄰居數(shù)和異常比、聚類數(shù)k;

（1）根據(jù)LOF算法過(guò)濾異常點(diǎn);（2）預(yù)先給定k=3，隨機(jī)從樣本中選取3個(gè)初始聚類中心;（3）計(jì)算所有樣本到每個(gè)聚類中心的距離，并將所有樣本劃歸到距離最近的距離中心;（4）在每個(gè)聚類中，根據(jù)所有樣本的平均值，將其作為新的聚類中心;（5）循環(huán)2、3，直到迭代步達(dá)到預(yù)先設(shè)定的迭代步數(shù)，或前后兩次聚類中心的變化小于預(yù)先設(shè)定的閾值;（6）根據(jù)兩個(gè)聚類中心與樣本距離最近，獲得數(shù)據(jù)集中對(duì)應(yīng)的重要位置。（7）結(jié)合發(fā)生時(shí)間，分類識(shí)別出職、住地。

2 實(shí)驗(yàn)結(jié)果及分析

2.1 數(shù)據(jù)準(zhǔn)備

數(shù)據(jù)來(lái)源為某市接入的各類數(shù)據(jù)，包括行程服務(wù)、打車類/代駕類、地理位置信息等五個(gè)源數(shù)據(jù)集，并從各數(shù)據(jù)集中初步篩選相關(guān)字段元素，作為分析要素。

手機(jī)用戶的網(wǎng)絡(luò)行為是多維度的，獲取的樣本越多，從這些信息中就越能逼近其現(xiàn)實(shí)狀態(tài)，基于此，需要盡可能多的融合各類信息，融合形成如表1，用于建模輸入。