基于手機經緯度數據的重要位置識別應用研究

王興旺

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

關鍵詞：聚類;局部異常因子;經緯度數據;重要位置

中圖分類號：TP311 文獻標識碼：A 文章編號：1007-9416（2019）08-0053-02

0 引言

隨著移動通訊、無線定位、移動互聯網技術的高速發展，在智能手機及各類APP應用日益普及的當下，手機用戶日常生活軌跡網絡化的程度越來越高，當人們使用手機瀏覽新聞資訊、接打電話、收發信息、聊天、游戲時，手機與基站之間時刻發生即時通訊，由此產生了大量的空間位置數據。

目前，對手機用戶軌跡進行聚類的研究中，文獻[1]提出對軌跡點進行空間密度聚類，該方法沒有對軌跡的離群點進行預處理，只通過KNN算法對數據進行聚類，聚類的區分度不夠高。文獻[2]將軌跡點轉化為線段序列，通過對線段序列進行聚類來挖掘熱點路徑，該方法適用于GPS數據，對手機采集的信令數據并不適用。文獻[3]通過將數據序列化網格序列，基于網格進行聚類發現熱點區域，但基于手機信息的數據量巨大，傳統的聚類方法已經不能滿足熱區挖掘要求。文獻[4]提出了基于DBSCAN的空間聚類算法，處理帶有噪聲的空間位置數據，多個區域間相差較大，導致聚類質量較差。基于此，本文結合LOF離群點檢測算法，提出了基于LOF的k-means空間聚類算法。LOF算法適用于基于不同密度的數據集群，通過利用LOF算法去掉部分異常位置數據，再利用聚類算法，找到手機用戶的幾個常用的聚集地。經過實驗論證，該算法在處理海量數據時有較好效果。

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

1.1 LOF算法

LOF算法作為一種基于密度方法的異常檢測算法，通過將數據樣本點的可達密度與其鄰居的平均可達密度之比作為離群因子，用以識別離群點。

1.1.1 定義

（1）可達距離。點o到p的第k可達距離定義為：

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

（2）局部可達密度。點p的局部可達密度表示為：

lrdk（p）=1/

該值代表一個密度，密度越高，認為越可能屬于同一簇，密度越低，越可能是離群點。

（3）局部離群因子。點p的局部離群因子表示為：

LOFk（p）==/lrdk（p）

表示點p的鄰域點Nk（p）的局部可達密度與點p的局部可達密度之比的平均數。

1.1.2 異常點判斷

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

1.1.3 算法1 LOF算法

輸入：數據樣本空間及局部鄰居數和異常比;（1）設定局部鄰居數和異常比，使用LOF算法對數據樣本空間進行異常點檢測;（2）根據1中得到正常點和異常點;（3）從數據樣本空間中刪除異常點。

1.2 K-means算法

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

k-means算法的實現準則是選取適當的準則函數，是一種發現這種內在結構的技術，由于不需要標注樣本而被稱為無監督學習。由于簡潔和效率而成為所有聚類算法中最廣泛使用的一種算法。給定一個樣本空間和需要劃分的聚類數目k，k由用戶指定，k均值算法根據某個距離函數反復把樣本歸入到k個聚類中。

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

在識別重要位置時，由于個體日常生活、工作中在空間位置移動時，多數情況下會在幾個主要區域切換，有部分位置因為偶爾出現，而在數據上表現出一定的隨機性，在識別特定手機用戶重要位置時可以先將這些數據剔除，因此，本文考慮將局部異常因子算法結合k-means算法，達到識別出特定手機用戶的重要位置。

根據模型輸入數據的特征及業務特點，可以利用k-means聚類算法，挖掘出每個手機用戶的三個簇（工作地、居住地、其他），再根據聚類中心與數據樣本中距離最近的樣本，標注為該手機用戶的工作地、居住地、其他。

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

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

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

2 實驗結果及分析

2.1 數據準備

數據來源為某市接入的各類數據，包括行程服務、打車類/代駕類、地理位置信息等五個源數據集，并從各數據集中初步篩選相關字段元素，作為分析要素。

手機用戶的網絡行為是多維度的，獲取的樣本越多，從這些信息中就越能逼近其現實狀態，基于此，需要盡可能多的融合各類信息，融合形成如表1，用于建模輸入。