空间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定位技术”和“比邻小区测量定位技术”。“Cell ID定位技术”使用终端服务小区基站位置作为手机位置，定位速度快，但是精度随扇区大小而变化，一般是1～3km。“比邻小区测量定位技术”通过测量终端与相邻3个基站的距离，根据基站坐标计算终端位置。基于建设成本、实施难度的考虑，本文使用“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算法对基于手机信令定位数据分析，可以挖掘出两类交通数据，即基于手机采集技术的实时交通状态信息和基于手机采集技术的动态出行调查信息。基于手机采集技术的实时交通状态信息，可以在采集手机信令数据的基础上分析处理，从而获得实时的路段旅行时间/速度，和实时交通状态（通畅、拥挤、堵塞）。基于手机采集技术的动态出行调查信息，可以在采集手机信令数据的基础上分析处理，从而获得基于基站小区与位置区定位，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.