空間KMeans挖掘算法在基于手機(jī)信令的OD分析中的應(yīng)用

孫強(qiáng)

摘 要：在基于手機(jī)信令的OD分析應(yīng)用中，利用空間Kmeans挖掘算法可以對(duì)目標(biāo)群體實(shí)時(shí)交通狀態(tài)信息和動(dòng)態(tài)出行調(diào)查，進(jìn)而識(shí)別出用戶出行方式，構(gòu)建城市綠色交通的具體方案。

關(guān)鍵詞：Kmeans挖掘算法 手機(jī)信令 大數(shù)據(jù) OD分析

中圖分類號(hào)：U49 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

基于運(yùn)營(yíng)商移動(dòng)網(wǎng)絡(luò)定位技術(shù)可以在用戶無(wú)感的情況下實(shí)現(xiàn)用戶群體定位。移動(dòng)網(wǎng)絡(luò)定位技術(shù)有多種，典型且建設(shè)成本較低的有兩種，分別是“Cell ID定位技術(shù)”和“比鄰小區(qū)測(cè)量定位技術(shù)”。“Cell ID定位技術(shù)”使用終端服務(wù)小區(qū)基站位置作為手機(jī)位置，定位速度快，但是精度隨扇區(qū)大小而變化，一般是1～3km?！氨揉徯^(qū)測(cè)量定位技術(shù)”通過(guò)測(cè)量終端與相鄰3個(gè)基站的距離，根據(jù)基站坐標(biāo)計(jì)算終端位置。基于建設(shè)成本、實(shí)施難度的考慮，本文使用“Cell ID定位技術(shù)”[1]，此技術(shù)建設(shè)成本低，定位速度快，雖然精度不高，但是可以滿足客戶群的定位、跟蹤等需求。

基于手機(jī)信令數(shù)據(jù)的用戶跟蹤和捕獲技術(shù)已經(jīng)相當(dāng)成熟，本文擬動(dòng)態(tài)跟蹤用戶群移動(dòng)，結(jié)合GIS路徑匹配算法，得到手機(jī)使用者的出行軌跡，包括出行時(shí)間、平均速度、出行距離信息，獲取交通信息，估算出城市路網(wǎng)中各條道路的行程車速、交通流量、擁堵?tīng)顩r等交通參數(shù)，識(shí)別出用戶可能使用的出行方式，實(shí)現(xiàn)城市OD調(diào)查分析系統(tǒng)[2]。

1 空間KMeans挖掘算法的應(yīng)用

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

在OD分析的手機(jī)定位的空間數(shù)據(jù)中，樣本點(diǎn)與中心點(diǎn)是包含經(jīng)緯度的坐標(biāo)點(diǎn)，兩點(diǎn)的差可使用兩點(diǎn)的距離代替。為能處理空間數(shù)據(jù)[4]，對(duì)其計(jì)算距離的算法進(jìn)行了重構(gòu)，計(jì)算方法如下。

/**

* 根據(jù)經(jīng)緯度計(jì)算兩點(diǎn)間的距離

* @param lng1 起點(diǎn)經(jīng)度

* @param lat1 起點(diǎn)維度

* @param lng2 終點(diǎn)經(jīng)度

* @param lat2 終點(diǎn)維度

* @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標(biāo)準(zhǔn)坐標(biāo)系，參考地球長(zhǎng)半徑（單位：m）

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

return s；

}

通過(guò)對(duì)經(jīng)典KMeans算法進(jìn)行改造，使其可以處理空間數(shù)據(jù)，則此算法可對(duì)用戶空間數(shù)據(jù)的聚類挖掘計(jì)算，應(yīng)用的場(chǎng)景包括以下方面。

（1）某用戶一段時(shí)間內(nèi)的位置定位。

將此用戶的多個(gè)位置分成1個(gè)族，族的中心點(diǎn)即為此用戶的位置。

（2）多用戶某時(shí)刻的位置定位。

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

2 結(jié)語(yǔ)

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

參考文獻(xiàn)

[1] 韓魯峰，孟凡寧，叢中昌.基于Cellid定位的精度優(yōu)化算法研究與實(shí)現(xiàn)[J].移動(dòng)通信，2013（14）：61-64.

[2] 張昊.移動(dòng)定位平臺(tái)和位置管理關(guān)鍵技術(shù)研究[D].北京郵電大學(xué)，2006.

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

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

[5] 樂(lè)婭菲.基于GPS經(jīng)緯度的空間相對(duì)方位與距離計(jì)算方法初探[J].中國(guó)高新技術(shù)企業(yè)，2012（25）：73-75.