空間KMeans挖掘算法在基于手機信令的OD分析中的應用

孫強

摘 要：在基于手機信令的OD分析應用中，利用空間Kmeans挖掘算法可以對目標群體實時交通狀態信息和動態出行調查，進而識別出用戶出行方式，構建城市綠色交通的具體方案。

關鍵詞：Kmeans挖掘算法 手機信令 大數據 OD分析

中圖分類號：U49 文獻標識碼：A 文章編號：1672-3791（2018）12（c）-0014-02

Abstract： In the application of OD analysis based on mobile signaling， spatial Kmeans mining algorithm can be used to detect real-time traffic status information and dynamic travel survey of target groups， and then identify user travel mode， and construct a specific scheme of urban green traffic.

Key Words： Kmeans mining algorithm； Mobile signaling； Big data； OD analysis

基于運營商移動網絡定位技術可以在用戶無感的情況下實現用戶群體定位。移動網絡定位技術有多種，典型且建設成本較低的有兩種，分別是“Cell ID定位技術”和“比鄰小區測量定位技術”?！癈ell ID定位技術”使用終端服務小區基站位置作為手機位置，定位速度快，但是精度隨扇區大小而變化，一般是1～3km?！氨揉徯^測量定位技術”通過測量終端與相鄰3個基站的距離，根據基站坐標計算終端位置?；诮ㄔO成本、實施難度的考慮，本文使用“Cell ID定位技術”[1]，此技術建設成本低，定位速度快，雖然精度不高，但是可以滿足客戶群的定位、跟蹤等需求。

基于手機信令數據的用戶跟蹤和捕獲技術已經相當成熟，本文擬動態跟蹤用戶群移動，結合GIS路徑匹配算法，得到手機使用者的出行軌跡，包括出行時間、平均速度、出行距離信息，獲取交通信息，估算出城市路網中各條道路的行程車速、交通流量、擁堵狀況等交通參數，識別出用戶可能使用的出行方式，實現城市OD調查分析系統[2]。

1 空間KMeans挖掘算法的應用

KMeans算法[3]是一種基于樣本間相似性度量的間接聚類算法。算法根據輸入參數K，將n個樣本分為K個簇，其核心思想是找到K個簇中心，使得簇中的樣本點與其所在簇中心點的差的總和最小化，經典KMeans聚類算法僅適合數值型數據。

在OD分析的手機定位的空間數據中，樣本點與中心點是包含經緯度的坐標點，兩點的差可使用兩點的距離代替。為能處理空間數據[4]，對其計算距離的算法進行了重構，計算方法如下。

/**

* 根據經緯度計算兩點間的距離

* @param lng1 起點經度

* @param lat1 起點維度

* @param lng2 終點經度

* @param lat2 終點維度

* @return

*/

public static double distance（double lng1， double lat1， double lng2， double lat2） {

double radLat1 = lat1 * Math.PI / 180；

double radLat2 = lat2 * Math.PI / 180；

double a = radLat1 - radLat2；

double b = lng1 * Math.PI / 180 - lng2 * Math.PI / 180；

double s = 2 * Math.asin（Math.sqrt（Math.pow（Math.sin（a / 2）， 2） + Math.cos（radLat1） * Math.cos（radLat2） * Math.pow（Math.sin（b / 2）， 2）））；

s = s * 6378137.0；// 取WGS84標準坐標系，參考地球長半徑（單位：m）

s = Math.round（s * 10000） / 10000；

return s；

}

通過對經典KMeans算法進行改造，使其可以處理空間數據，則此算法可對用戶空間數據的聚類挖掘計算，應用的場景包括以下方面。

（1）某用戶一段時間內的位置定位。

將此用戶的多個位置分成1個族，族的中心點即為此用戶的位置。

（2）多用戶某時刻的位置定位。

將多個用戶的位置分成K個族，可以得到K個不同的位置，即K個不同的用戶群。

2 結語

在南京市急救OD系統應用中，通過KMeans算法對基于手機信令定位數據分析，可以挖掘出兩類交通數據，即基于手機采集技術的實時交通狀態信息和基于手機采集技術的動態出行調查信息?；谑謾C采集技術的實時交通狀態信息，可以在采集手機信令數據的基礎上分析處理，從而獲得實時的路段旅行時間/速度，和實時交通狀態（通暢、擁擠、堵塞）。基于手機采集技術的動態出行調查信息，可以在采集手機信令數據的基礎上分析處理，從而獲得基于基站小區與位置區定位，15min動態OD矩陣、校核線調查、居住地就業崗位分布、客流集散地人流調查，該技術采集的數據具有較高的采樣率和較高的更新頻率。

參考文獻

[1] 韓魯峰，孟凡寧，叢中昌.基于Cellid定位的精度優化算法研究與實現[J].移動通信，2013（14）：61-64.

[2] 張昊.移動定位平臺和位置管理關鍵技術研究[D].北京郵電大學，2006.

[3] 胡永愷，宋璐，張健，等.基于手機信令數據的交通OD提取方法改進[J].交通信息與安全，2015（5）：84-90.

[4] 趙偉，張姝，李文輝.改進K-means的空間聚類算法[J].計算機應用研究，2008，25（7）：1995-1997.

[5] 樂婭菲.基于GPS經緯度的空間相對方位與距離計算方法初探[J].中國高新技術企業，2012（25）：73-75.