高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于信令数据的轨迹驻留点识别算法研究

李万林 王超 许国良 雒江涛 张轩

李万林, 王超, 许国良, 雒江涛, 张轩. 基于信令数据的轨迹驻留点识别算法研究[J]. 电子与信息学报. doi: 10.11999/JEIT190914
引用本文: 李万林, 王超, 许国良, 雒江涛, 张轩. 基于信令数据的轨迹驻留点识别算法研究[J]. 电子与信息学报. doi: 10.11999/JEIT190914
Wanlin LI, Chao WANG, Guoliang XU, Jiangtao LUO, Xuan ZHANG. Research of Track Resident Point Identification Algorithm Based on Signaling Data[J]. Journal of Electronics and Information Technology. doi: 10.11999/JEIT190914
Citation: Wanlin LI, Chao WANG, Guoliang XU, Jiangtao LUO, Xuan ZHANG. Research of Track Resident Point Identification Algorithm Based on Signaling Data[J]. Journal of Electronics and Information Technology. doi: 10.11999/JEIT190914

基于信令数据的轨迹驻留点识别算法研究

doi: 10.11999/JEIT190914
基金项目: 重庆市自然科学基金 (cstc2018jcyjAX0587),新型感知技术、信息融合处理及其应用(A2017-10)
详细信息
    作者简介:

    李万林:男,1963年生,教授、博士生导师,研究方向为新一代网络技术、自动驾驶,车联网及移动大数据等

    王超:男,1994年生,硕士生,研究方向为移动大数据、机器学习

    许国良:男,1973年生,教授、硕士生导师,研究方向为光电传感与检测、通信网络设计与规划、大数据分析挖掘

    雒江涛:男,1971年生,教授、博士生导师,研究方向为移动大数据、新一代网络技术、通信网络测试与优化等

    张轩:男,1991年生,硕士生,研究方向为移动大数据、机器学习

    通讯作者:

    许国良 xugl@cqupt.edu.cn

  • 中图分类号: TN929.5

Research of Track Resident Point Identification Algorithm Based on Signaling Data

Funds: The Natural Science Foundation of Chongqing (cstc2018jcyjAX0587), The New Sensing Technology, Information Fusion Processing and its Application (A2017-10)
  • 摘要: 针对密度聚类算法只能识别密度相近的簇类且计算复杂度高等问题,该文提出一种基于信令数据中时空轨迹信息的密度峰值快速聚类(ST-CFSFDP)算法。首先对低采样密度的信令数据进行预处理,消除轨迹震荡现象;然后基于密度峰值快速聚类(CFSFDP)算法显式地增加时间维度限制,将局部密度由2维扩展到3维,并提出高密度时间间隔以表征簇中心在时间维度上的数据特征;接着设计筛选策略以选取聚类中心;最后识别用户出行轨迹中的驻留点,完成出行链的划分。实验结果表明,所提算法适用于采样密度低且定位精度差的信令数据,相比CFSFDP算法更适用于时空数据,相比基于密度的时空聚类算法(ST-DBSCAN)召回率提升14%,准确率提升8%,同时降低计算复杂度。
  • 图  1  震荡时间最大间隔与平均震荡比的关系

    图  2  原始数据分布与CFSFDP算法决策分析

    图  3  原始数据分布与改进的CFSFDP算法决策分析

    图  4  聚类中心权重分布

    图  5  CFSFDP算法结果图

    图  6  ST-DBSCAN算法结果图

    图  7  ST-CFSFDP算法结果图

    图  8  ST-DBSCAN与ST-CFSFDP算法对比

    表  1  信令数据主要字段

    字段名称字段解释字段内容(示例)
    user ID用户身份0001A
    LAC_CID基站位置区域码与小区识别码13119-2056
    TimeStamp用户接入时间戳2019-10-23 17:42:09
    CoverScene当前基站的覆盖场景道路/学校/火车站等
    Lon_Lat当前基站经度、维度(106.59767, 29.40709)
    下载: 导出CSV

    表  2  震荡轨迹数据示例

    轨迹位置时间距离 (km)切换速度 (km/h)
    ${D_0}$${L_0}$(106.607617,29.530807)08:19:35//
    ${D_1}$${L_1}$(106.602659,29.545336)08:20:141.6147.6923
    ${D_2}$${L_2}$(106.607617,29.530807)08:20:391.6230.4000
    下载: 导出CSV

    表  3  基于时间窗的震荡轨迹检测方法

     输入:原始轨迹数据${{L} } = \left\{ { {L_1}{\rm{ } }···{\rm{ } }{L_i}{\rm{ } }{L_{i + 1} }{\rm{ } }···{\rm{ } }{L_{i + {N_w} } }{\rm{ } }···} \right\}$,轨迹序列切片中基站位置个数${N_w}$,震荡数据最大时间阈值${T_{w\_\max }}$;
     输出:检测到的震荡轨迹数据${L_{\rm{osc}}}$;
     (1) 按顺序截取原始数据${{L}}$中的前${N_w}$个位置组成序列${L_w}$;
     (2) 检测${L_w}$中是否出现循环模式,如果出现则执行(3),否则序列点向前移1位,重新执行(1),截取后续${N_w}$个位置的序列片段;
     (3) 对检测到的震荡部分记为(${L_{\rm{beg} } }{\rm{ } }···{\rm{ } }{L_{\rm{end} } }$),判断该部分序列的总时间是否小于${T_{w\_\max }}$,如果满足,那么将该震荡序列记为${L_{\rm{osc}}}$,同时序
       列点向前移1位,返回步骤1;如果不满足,直接返回(1),直至遍历完${{L}}$内所有轨迹点。
     算法结束
    下载: 导出CSV

    表  4  ST-CFSFDP聚类算法

     输入:原始空间数据$P\left\langle {x\;y\;t\;d} \right\rangle $;截断距离${d_{\rm c}}$;截断时间${t_{\rm c}}$;数据点覆盖场景的描述$d$
     输出:该原始数据的聚类集合${C_k}$,$k = 1,2, ··· ,n$;
     (1) 计算每一个数据点的局部时空密度${\rho _i}$;
     (2) 依照定义4与定义5计算每个数据点的高密度空间距离${\delta _i}$、高密度时间间隔${\tau _i}$;
     (3) 计算各个数据点的聚类中心权值,将聚类中心权值的平均值作为阈值,将大于该阈值的数据点放入聚类中心候选点集合${C_{\rm c}}$中;
     (4) 合并候选点中覆盖场景相同且空间距离小于${d_{\rm c}}$或时间间隔小于${t_{\rm c}}$的“近邻数据点”,保留聚类中心权重较高的点;
     (5) 将剩余的数据点,按照最近邻思想分配到各个聚类中心所代表的簇中。
     算法结束
    下载: 导出CSV

    表  5  算法距离误差对比(m)

    编号驻留点坐标(Long, Lat)CFSFDP算法的距离误差ST-DBSCAN算法的距离误差ST-CFSFDP算法的距离误差
    1106.601230, 29.533960044.842.234.6
    2106.602061, 29.5343564\43.548.3
    3106.496737, 29.616684448.835.337.4
    4106.496729, 29.6166840\\50.6
    5106.546322, 29.620312052.6\46.4
    下载: 导出CSV
  • [1] 陈鸿昶, 徐乾, 黄瑞阳, 等. 一种基于用户轨迹的跨社交网络用户身份识别算法[J]. 电子与信息学报, 2018, 40(11): 2758–2764. doi:  10.11999/JEIT180130

    CHEN Hongchang, XU Qian, HUANG Ruiyang, et al. User identification across social networks based on user trajectory[J]. Journal of Electronics &Information Technology, 2018, 40(11): 2758–2764. doi:  10.11999/JEIT180130
    [2] 彭大芹, 罗裕枫, 江德潮, 等. 基于移动信令数据的城市热点识别方法[J]. 重庆邮电大学学报: 自然科学版, 2019, 31(1): 95–102. doi:  10.3979/j.issn.1673-825X.2019.01.013

    PENG Daqin, LUO Yufeng, JIANG Dechao, et al. Urban hotspots identification method based on mobile signaling data[J]. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition, 2019, 31(1): 95–102. doi:  10.3979/j.issn.1673-825X.2019.01.013
    [3] 罗孝羚, 蒋阳升. 基于出租车运营数据和POI数据的出行目的识别[J]. 交通运输系统工程与信息, 2018, 18(5): 60–66. doi:  10.16097/j.cnki.1009-6744.2018.05.010

    LUO Xiaoling and JIANG Yangsheng. Trip-purpose-identification based on taxi operating data and POI data[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(5): 60–66. doi:  10.16097/j.cnki.1009-6744.2018.05.010
    [4] 鲍冠文, 刘小明, 蒋源, 等. 基于改进DBSCAN算法的出租车载客热点区域挖掘研究[J]. 交通工程, 2019, 19(4): 62–69. doi:  10.13986/j.cnki.jote.2019.04.010

    BAO Guanwen, LIU Xiaoming, JIANG Yuan, et al. Research on mining taxi pick-up hotspots area[J]. Journal of Transportation Engineering, 2019, 19(4): 62–69. doi:  10.13986/j.cnki.jote.2019.04.010
    [5] 李岩, 陈红, 孙晓科, 等. 基于热点探测模型的城市居民出行特征分析[J]. 交通信息与安全, 2019, 37(1): 128–136. doi:  10.3963/j.issn.1674-4861.2019.01.017

    LI Yan, CHEN Hong, SUN Xiaoke, et al. An analysis of travel characteristics of urban residents based on hot spot detection model[J]. Journal of Transport Information and Safety, 2019, 37(1): 128–136. doi:  10.3963/j.issn.1674-4861.2019.01.017
    [6] 张海霞, 李腆腆, 李东阳, 等. 基于车辆行为分析的智能车联网关键技术研究[J]. 电子与信息学报, 2020, 42(1): 36–49. doi:  10.11999/JEIT190820

    ZHANG Haixia, LI Tiantian, LI Dongyang, et al. Research on vehicle behavior analysis based technologies for intelligent vehicular networks[J]. Journal of Electronics &Information Technology, 2020, 42(1): 36–49. doi:  10.11999/JEIT190820
    [7] 李浩, 王旭智, 万旺根. 基于位置数据的居民出行时空特征研究——以上海市为例[J]. 电子测量技术, 2019, 42(19): 25–30. doi:  10.19651/j.cnki.emt.1902923

    LI Hao, WANG Xuzhi, and WAN Wanggen. Research on temporal and spatial characteristics of residents’ travel based on location data—A case of Shanghai[J]. Electronic Measurement Technology, 2019, 42(19): 25–30. doi:  10.19651/j.cnki.emt.1902923
    [8] 周洋, 杨超. 基于时空聚类算法的轨迹停驻点识别研究[J]. 交通运输系统工程与信息, 2018, 18(4): 88–95. doi:  10.16097/j.cnki.1009-6744.2018.04.014

    ZHOU Yang and YANG Chao. Anchors identification in trajectory based on temporospatial clustering algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(4): 88–95. doi:  10.16097/j.cnki.1009-6744.2018.04.014
    [9] 方琪, 王山东, 于大超, 等. 基于出租车轨迹的居民出行特征分析[J]. 地理空间信息, 2019, 17(5): 128–130. doi:  10.3969/j.issn.1672-4623.2019.05.034

    FANG Qi, WANG Shandong, YU Dachao, et al. Analysis of resident trip characteristics based on taxi trajectory[J]. Geospatial Information, 2019, 17(5): 128–130. doi:  10.3969/j.issn.1672-4623.2019.05.034
    [10] BIRANT D and KUT A. ST-DBSCAN: An algorithm for clustering spatial–temporal data[J]. Data & Knowledge Engineering, 2007, 60(1): 208–221. doi:  10.1016/j.datak.2006.01.013
    [11] RODRIGUEZ A and LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492–1496. doi:  10.1126/science.1242072
    [12] WANG Feilong and CHEN C. On data processing required to derive mobility patterns from passively-generated mobile phone data[J]. Transportation Research Part C: Emerging Technologies, 2018, 87: 58–74. doi:  10.1016/j.trc.2017.12.003
    [13] CHEN C, BIAN Ling, and MA Jingtao. From traces to trajectories: How well can we guess activity locations from mobile phone traces?[J]. Transportation Research Part C: Emerging Technologies, 2014, 46: 326–337. doi:  10.1016/j.trc.2014.07.001
    [14] HARD E, CHIGOY B, SONGCHITRUKSA P, et al. Synopsis of new methods and technologies to collect Origin-Destination (O-D) data[R]. FHWA-HEP-16-083, 2016.
    [15] LEE J K and HOU J C. Modeling steady-state and transient behaviors of user mobility: Formulation, analysis, and application[C]. The 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Florence, Italy, 2006: 85–96.
  • [1] 肖满生, 张龙信, 张晓丽, 胡永祥.  一种改进的区间型不确定数据模糊聚类方法, 电子与信息学报. 2020, 42(8): 1968-1974. doi: 10.11999/JEIT190591
    [2] 张雄涛, 蒋云良, 潘兴广, 胡文军, 王士同.  基于迭代模糊聚类算法与K近邻和数据字典的集成TSK模糊分类器, 电子与信息学报. 2020, 42(3): 746-754. doi: 10.11999/JEIT190214
    [3] 叶茂, 刘文芬.  基于快速地标采样的大规模谱聚类算法, 电子与信息学报. 2017, 39(2): 278-284. doi: 10.11999/JEIT160260
    [4] 刘俊, 刘瑜, 何友, 孙顺.  杂波环境下基于全邻模糊聚类的联合概率数据互联算法, 电子与信息学报. 2016, 38(6): 1438-1445. doi: 10.11999/JEIT150849
    [5] 吴佳妮, 陈永光, 代大海, 陈思伟, 王雪松.  基于快速密度搜索聚类算法的极化HRRP分类方法, 电子与信息学报. 2016, 38(10): 2461-2467. doi: 10.11999/JEIT151457
    [6] 罗恩韬, 王国军.  大数据中一种基于语义特征阈值的层次聚类方法, 电子与信息学报. 2015, 37(12): 2795-2801. doi: 10.11999/JEIT150422
    [7] 孙力娟, 陈小东, 韩崇, 郭剑.  一种新的数据流模糊聚类方法, 电子与信息学报. 2015, 37(7): 1620-1625. doi: 10.11999/JEIT141415
    [8] 叶有时, 唐林波, 赵保军.  一种基于聚类的深空红外多目标快速检测算法, 电子与信息学报. 2011, 33(1): 77-84. doi: 10.3724/SP.J.1146.2010.00175
    [9] 唐成龙, 王石刚, 徐威.  基于数据加权策略的模糊聚类改进算法, 电子与信息学报. 2010, 32(6): 1277-1283. doi: 10.3724/SP.J.1146.2009.00857
    [10] 曹苏群, 王士同, 陈晓峰, 谢振平, 邓赵红.  基于模糊Fisher准则的半模糊聚类算法, 电子与信息学报. 2008, 30(9): 2162-2165. doi: 10.3724/SP.J.1146.2007.00232
    [11] 缑水平, 焦李成, 田小林.  基于免疫克隆聚类协同神经网络的图像识别, 电子与信息学报. 2008, 30(2): 263-266. doi: 10.3724/SP.J.1146.2007.00405
    [12] 张载龙, 孙建, 李君, 张顺颐.  一种优化的SIP信令网过载控制算法, 电子与信息学报. 2008, 30(10): 2486-2489. doi: 10.3724/SP.J.1146.2007.00478
    [13] 贾宇平, 李亚楠, 付耀文, 庄钊文.  一种基于灰色定权聚类的决策层融合目标识别算法, 电子与信息学报. 2008, 30(2): 255-258. doi: 10.3724/SP.J.1146.2007.00096
    [14] 王慎超, 苗夺谦, 陈敏, 王睿智.  基于覆盖的粗糙聚类算法, 电子与信息学报. 2008, 30(7): 1713-1716. doi: 10.3724/SP.J.1146.2007.00450
    [15] 刘海华, 张武, 陈心浩, 陈亚光.  基于模糊聚类的运动对象分割算法研究, 电子与信息学报. 2006, 28(9): 1689-1692.
    [16] 包志强, 韩冰, 吴顺君.  基于模糊聚类的信源个数检测新算法, 电子与信息学报. 2006, 28(10): 1761-1765.
    [17] 姜园, 张朝阳, 仇佩亮, 周东方.  用于数据挖掘的聚类算法, 电子与信息学报. 2005, 27(4): 655-662.
    [18] 陈金山, 韦岗.  遗传+模糊C-均值混合聚类算法, 电子与信息学报. 2002, 24(2): 210-215.
    [19] 王之禹, 朱敏慧, 白有天.  基于Mueller矩阵分解的非监督聚类算法, 电子与信息学报. 2001, 23(5): 454-459.
    [20] 魏立梅, 谢维信.  模糊C-球壳聚类算法的研究, 电子与信息学报. 2001, 23(1): 37-44.
  • 加载中
  • 图(8) / 表ll (5)
    计量
    • 文章访问数:  212
    • HTML全文浏览量:  97
    • PDF下载量:  8
    • 被引次数: 0
    出版历程
    • 收稿日期:  2019-11-14
    • 修回日期:  2020-06-09
    • 网络出版日期:  2020-07-16

    目录

      /

      返回文章
      返回

      官方微信,欢迎关注