基于时间距离的时空重排扫描优化方法

杨威 龙华 王美 杜庆治

引用本文:
Citation:

基于时间距离的时空重排扫描优化方法

    作者简介: 杨威(1992−),男,山西人,硕士生,研究方向为信息处理. E-mail:513079328@qq.com;
    通讯作者: 龙华, longhua@kmust.edu.cn
  • 中图分类号: TP311.13

Space–time permutation scanning optimization method based on multi-factor distance

    Corresponding author: LONG Hua, longhua@kmust.edu.cn ;
  • CLC number: TP311.13

  • 摘要: 针对时空重排扫描方法扫描使用中,通过空间直线距离来测量两观测点间距会忽略城市中的楼房、公园等障碍物等因素,导致两点间测得真实距离的偏差,从而对扫描结果造成影响, 提出了一种基于时间距离的时空重排扫描优化方法. 首先依据城市中障碍物对两点间实际路径的影响得到观测点间的真实路径,然后利用真实路径计算得到两观测点间的交通时间,最后利用交通时间来代替表示两点间的真实距离. 通过旧金山火灾数据集对本文优化方法进行验证,模型性能普遍提升了2%~5%.
  • 图 1  时空重排扫描示意图

    Figure 1.  Schematic diagram of space-time permutation scan statistic

    图 2  事件因子传播路径示意图

    Figure 2.  Schematic diagram of the event factor propagation path

    图 3  时空重排扫描优化方法基本原理图

    Figure 3.  Basic schematic diagram of space-time permutation scan optimization method

    图 4  时空重排扫描优化方法流程图

    Figure 4.  Flow chart of space-time permutation scan optimization method

    图 5  42个观测点火灾实际发生情况图

    Figure 5.  Actual situation of fire at 42 observation points

    图 6  2018年2月1日~2018年2月7日时空重排扫描方法扫描结果

    Figure 6.  Scanning results of the Space–Time Permutation Scanning method from February 1 to 7, 2018

    图 7  2018年5月1日~2018年5月7日时空重排扫描方法扫描结果

    Figure 7.  Scanning results of the Space–Time Permutation Scanning method from May 1 to 7, 2018

    图 8  2018年10月1日~2018年10月7日时空重排扫描方法扫描结果

    Figure 8.  Scanning results of the Space–Time Permutation Scanning method from October 1 to 7, 2018

    表 1  旧金山火灾事件观测地点编号

    Table 1.  Numbers of the fire incident observation site in San Francisco

    地点名称地点编号地点名称地点编号
    Tenderloin1Outer Richmond8
    Mission2Inner Sunset9
    South of Market3Mission Bay10
    Haight Ashbury4Pacific Heights11
    Noe Valley5Parkside12
    North Beach6······
    Financial District7Seacliff42
    下载: 导出CSV

    表 2  时空重排扫描数据集

    Table 2.  Scanned data sets of the space–time permutation

    地点
    编号
    日期火灾事件
    发生数
    地点
    编号
    日期火灾事件
    发生数
    402018-01-01132018-01-011
    252018-01-01322018-01-013
    182018-01-01512018-01-011
    162018-01-011322018-01-011
    102018-01-011172018-01-011
    72018-01-015······
    42018-01-011272018-12-311
    下载: 导出CSV

    表 3  实际发生火灾的观测点情况

    Table 3.  Observation points of actual fires

    时间实际发生火灾事件的观测点观测点个数
    2018-2-8~2018-2-14 [1,2,3,4,6,7,8,9,10,11,12,13,14,16,17,18,19,20,21,22,23,24,25,27,28,29,30,32,33,35,36] 31
    2018-5-8~2018-5-14 [1,2,3,4,5,6,7,8,10,12,13,14,16,17,18,19,20,21,22,23,24,25,26,27,29,30,33,38,39] 29
    2018-10-8~2018-10-14 [1,2,3,4,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,22,23,24,26,28,29,30,31,32,33,34,36,37,39] 33
    下载: 导出CSV

    表 4  2018年2月1日~2018年2月7日时空重排扫描方法预警观测点

    Table 4.  Early warning observation points of the Space–Time Permutation Scanning method from February 1 to 7, 2018

    扫描方法预警观测点
    传统方法 [2, 4, 5, 8, 9, 10, 12, 13, 14, 15, 17, 18, 22, 23, 24, 25, 26, 29, 30, 31, 32, 33, 34, 35, 38, 39, 40, 41, 42]
    优化方法 [1, 2, 3, 4, 5, 9, 10, 12, 13, 14, 15, 17, 18, 22, 23, 24, 25, 29, 30, 31, 32, 33, 35, 38, 40, 41, 42]
    下载: 导出CSV

    表 5  2018年5月1日~2018年5月7日时空重排扫描方法预警观测点

    Table 5.  Early warning observation points of the Space–Time Permutation Scanning method from May 1 to 7, 2018

    扫描方法预警观测点
    传统方法[1, 3, 8, 11, 13, 16, 18, 20, 21, 22, 24, 27, 31, 35, 36, 37, 38, 39, 40, 41, 42]
    优化方法[1, 3, 4, 7, 8, 9, 10, 11, 17, 18, 20, 21, 24, 26, 27, 28, 29, 34, 37, 39, 40, 41, 42]
    下载: 导出CSV

    表 6  2018年5月1日~2018年5月7日时空重排扫描方法预警观测点

    Table 6.  Early warning observation points of the Space–Time Permutation Scanning method from October 1 to 7, 2018

    扫描方法预警观测点
    传统方法[1, 2, 3, 4, 6, 7, 8, 9, 11, 14, 15, 16, 17, 20, 21, 26, 27, 28, 29, 34, 35, 36, 37, 38, 39, 40, 41, 42]
    优化方法[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 20, 21, 25, 26, 27, 28, 29, 31, 34, 35, 36, 37, 39, 40, 41, 42]
    下载: 导出CSV

    表 7  2018年2月1日~2018年2月7日2种方法扫描结果的 ${S\!_{\rm{P}}}$${S\!_{\rm{R}}}$$F$

    Table 7.  ${S\!_{\rm{P}}}$, ${S\!_{\rm{R}}}$ and $F$ of the scanning results of the two methods from February 1 to 7, 2018

    扫描方法评价指标传统方法优化方法
    ${S\!_{\rm{P}}}$61.3%64.5%
    ${S\!_{\rm{R}}}$65.5%74.1%
    $F$0.3160.345
    下载: 导出CSV

    表 8  2018年5月1日~2018年5月7日2种方法扫描结果的 ${S\!_{\rm{P}}}$${S\!_{\rm{R}}}$$F$

    Table 8.  ${S\!_{\rm{P}}}$, ${S\!_{\rm{R}}}$ and $F$ of the scanning results of the two methods from May 1 to 7, 2018

    扫描方法
    评价指标
    传统方法优化方法
    ${S\!_{\rm{P}}}$44.8%51.7%
    ${S\!_{\rm{R}}}$61.9%65.2%
    $F$0.260.288
    下载: 导出CSV

    表 9  2018年10月1日~2018年10月7日2种方法扫描结果的 ${S\!_{\rm{P}}}$${S\!_{\rm{R}}}$$F$

    Table 9.  ${S\!_{\rm{P}}}$, ${S\!_{\rm{R}}}$ and $F$ of the scanning results of the two methods from October 1 to 7, 2018

    扫描方法
    评价指标
    传统方法优化方法
    ${S\!_{\rm{P}}}$66.7%78.7%
    ${S\!_{\rm{R}}}$78.6%78.8%
    $F$0.3610.393
    下载: 导出CSV
  • [1] Cressie N, Wikle C K. Statistics for spatio-temporal data[M]. New Jersey: John Wiley & Sons, 2015.
    [2] 李敏, 何红弟, 郝杨杨. 上海市大气环境中PM2.5/PM10时空分布特征[J]. 云南大学学报:自然科学版, 2019, 41(2): 323-332. Li M, He H D, Hao Y Y. Spatial and temporal variability of PM2.5/PM10 ratio in Shanghai[J]. Journal of Yunnan University: Natural Sciences Edition, 2019, 41(2): 323-332.
    [3] Atluri G, Karpatne A, Kumar V. Spatio-temporal data mining: A survey of problems and methods[J]. ACM Computing Surveys (CSUR), 2018, 51(4): 83. DOI:  10.1145/3161602.
    [4] Karpatne A, Faghmous J, Kawale J, et al. Earth science applications of sensor data[M]// Managing and Mining Sensor Data, Springer, Boston, MA, 2013: 505-530. DOI: 10.1007/978-1-4614-6309-2_15.
    [5] Shi Z, Pun-Cheng L S C. Spatiotemporal data clustering: A survey of methods[J]. ISPRS International Journal of Geo-Information, 2019, 8(3): 112. DOI:  10.3390/ijgi8030112.
    [6] 李智, 李卫红. 点模式条件下的犯罪嫌疑人时空同现模式挖掘与分析[J]. 地球信息科学学报, 2018, 20(6): 827-836. DOI:  10.12082/dqxxkx.2018.180009. Li Z, Li W H. Mining and analyzing spatiotemporal Co-occurrence patterns among criminal suspects under point pattern[J]. Journal of Geo-Information Science, 2018, 20(6): 827-836.
    [7] 张婷, 程昌秀, 杨山力, 等. 时空聚集性探测方法在极端高温事件聚集分析中的应用研究[J]. 地理与地理信息科学, 2019, 35(3): 51-57. DOI:  10.3969/j.issn.1672-0504.2019.03.008. Zhang T, Cheng W X, Yang S L, et al. Application of spatio-temporal aggregation detection method in extreme high temperature aggregation analysis[J]. Geography and Geo-Information Science, 2019, 35(3): 51-57.
    [8] 吕丹, 龙华, 赵继东, 等. 基于地图地理信息点的数据融合算法的改进[J]. 西北大学学报:自然科学版, 2017, 47(5): 687-692. Lv D, Long H, Zhao J D, et al. An improved data fusion algorithm based on geographic information points[J]. Journal of Northwest University: Natural Science Edition, 2017, 47(5): 687-692.
    [9] Duczmal L, Assuncao R. A simulated annealing strategy for the detection of arbitrarily shaped spatial clusters[J]. Computational Statistics & Data Analysis, 2004, 45(2): 269-286. DOI:  10.1016/S0167-9473(02)00302-X.
    [10] Naus J L. Clustering of random points in two dimensions[J]. Biometrika, 1965, 52(1-2): 263-266. DOI:  10.2307/2333829.
    [11] Loader C R. Large-deviation approximations to the distribution of scan statistics[J]. Advances in Applied Probability, 1991, 23(4): 751-771. DOI:  10.2307/1427674.
    [12] Turnbull B W, Iwano E J, Burnett W S, et al. Monitoring for clusters of disease: application to leukemia incidence in upstate New York[J]. American Journal of Epidemiology, 1990, 132(S1): 136-143. DOI:  10.1093/oxfordjournals.aje.a115775.
    [13] Kulldorff M. A spatial scan statistic[J]. Communications in Statistics-Theory and methods, 1997, 26(6): 1 481-1 496. DOI:  10.1080/03610929708831995.
    [14] Kulldorff M. Prospective time periodic geographical disease surveillance using a scan statistic[J]. Journal of the Royal Statistical Society: Series A (Statistics in Society), 2001, 164(1): 61-72. DOI:  10.1111/1467-985X.00186.
    [15] Kulldorff M, Heffernan R, Hartman J, et al. A space–time permutation scan statistic for disease outbreak detection[J]. PLoS Medicine, 2005, 2(3): 216-224. DOI:  10.1371/journal.pmed.0020059.
    [16] Fanaeet H, Gama J. Eigenspace method for spatiotemporal hotspot detection[J]. Expert Systems, 2015, 32(3): 454-464. DOI:  10.1111/exsy.12088.
    [17] Ullah S, Daud H, Dass S C, et al. Detecting space-time disease clusters with arbitrary shapes and sizes using a co-clustering approach[J]. Geospatial Health, 2017, 567(12): 210-216. DOI:  10.4081/gh.2017.567.
    [18] Choi H, Song E, Hwang S, et al. A modified generalized lasso algorithm to detect local spatial clusters for count data[J]. AStA Advances in Statistical Analysis, 2018, 102(4): 537-563. DOI:  10.1007/s10182-018-0318-7.
    [19] Katragadda S, Chen J, Abbady S. Spatial hotspot detection using polygon propagation[J]. International Journal of Digital Earth, 2019, 12(7): 825-842. DOI:  10.1080/17538947.2018.1485754.
    [20] Cary G J, Keane R E, Gardner R H, et al. Comparison of the sensitivity of landscape-fire-succession models to variation in terrain, fuel pattern, climate and weather[J]. Landscape Ecology, 2006, 21(1): 121-137. DOI:  10.1007/s10980-005-7302-9.
    [21] Linn R, Winterkamp J, Edminster C, et al. Coupled influences of topography and wind on wildland fire behaviour[J]. International Journal of Wildland Fire, 2007, 16(2): 183-195. DOI:  10.1071/WF06078.
    [22] Forbes C, Evans M, Hastings N, et al. Statistical distributions[M]. New York: John Wiley & Sons, 2000. DOI: 10.1002/9780470627242.
    [23] Neill D B. Expectation-based scan statistics for monitoring spatial time series data[J]. International Journal of Forecasting, 2009, 25(3): 498-517. DOI:  10.1016/j.ijforecast.2008.12.002.
    [24] Tuia D, Ratle F, Lasaponara R, et al. Scan statistics analysis of forest fire clusters[J]. Communications in Nonlinear Science and Numerical Simulation, 2008, 13(8): 1 689-1 694. DOI:  10.1016/j.cnsns.2007.03.004.
    [25] Vadrevu K P. Analysis of fire events and controlling factors in eastern India using spatial scan and multivariate statistics[J]. Geografiska Annaler: Series A, Physical Geography, 2008, 90(4): 315-328. DOI:  10.1111/j.1468-0459.2008.00348.x.
  • [1] 李涛吴小平王莹 . 基于分区空间扫描研究云南地区b值分布特征. 云南大学学报(自然科学版),
    [2] 龚婧婧高茜管莹李雪梅魏云林夭建华 . CHO细胞微核的激光扫描细胞仪自动化检测方法. 云南大学学报(自然科学版),
    [3] 姚庆六 . 一类非线性三阶两点边值问题的单调迭代方法. 云南大学学报(自然科学版),
    [4] 姚庆六 . 一类非线性三阶两点边值问题的单调迭代方法. 云南大学学报(自然科学版),
    [5] 姚庆六 . 一类不连续三阶两点边值问题的变号解. 云南大学学报(自然科学版),
    [6] 姜跃 . 基于云有序概念层次树的时间序列距离计算模型. 云南大学学报(自然科学版),
    [7] 尤卫红赵付竹 . 夏季北太平洋副热带高压年际变化的特征时间尺度及其时空演变. 云南大学学报(自然科学版),
    [8] 王晓霞杨树政 . 两维整体单极黑洞时空中的Casimir效应. 云南大学学报(自然科学版),
    [9] 陈欣木钧杨群羽刘琨 . γ暴搜寻中实测角分布与角半径的关系. 云南大学学报(自然科学版),
    [10] 程春玉孟捷 . 旅客到达昆明机场交通方式选择影响因素分析. 云南大学学报(自然科学版),
    [11] 曹良坤王昆山周灿东张 熹岳 燕杨艳华 . 基于Web的交通违法处理系统研究. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.2014a13
    [12] 许弟余焦善庆 . 对宇观天体和微观粒子质量-半径统一计算的注记. 云南大学学报(自然科学版),
    [13] 和永军姚庆华缪应锋孙雪赵娜 . 基于大数据的云南省智慧城市交通建设研究. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.2016d
    [14] 蒲斌李浩卢晨阳王治辉刘华 . 基于神经网络的海量GPS数据交通流量预测. 云南大学学报(自然科学版), doi: 10.7540/j.ynu.20170292
    [15] 钱民唐克生 . 基于定性动态概率网络的交通状态预测及改进. 云南大学学报(自然科学版),
    [16] 张祖林刘光富 . 昆明市主城区道路交通控制与管理改进方案研究. 云南大学学报(自然科学版),
    [17] 雷晓强 . 可分任务的完工时间. 云南大学学报(自然科学版),
    [18] 农庆琴陈智斌雷晓强 . 并行加工的完工时间. 云南大学学报(自然科学版),
    [19] 吴佳刘宏程吕亚琼张玉顺董泽民刘建平 . 赤霉素A环重排反应催化剂研究. 云南大学学报(自然科学版),
    [20] 刘建平 . 赤霉素类化合物中C,D环的重排反应研究Ⅰ:偶姻重排反应条件研究. 云南大学学报(自然科学版),
  • 加载中
图(8)表(9)
计量
  • 文章访问数:  256
  • HTML全文浏览量:  272
  • PDF下载量:  16
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-10-13
  • 录用日期:  2020-02-20
  • 网络出版日期:  2020-04-28

基于时间距离的时空重排扫描优化方法

    作者简介:杨威(1992−),男,山西人,硕士生,研究方向为信息处理. E-mail:513079328@qq.com
    通讯作者: 龙华, longhua@kmust.edu.cn
  • 昆明理工大学 信息工程与自动化学院,云南 昆明 650500

摘要: 针对时空重排扫描方法扫描使用中,通过空间直线距离来测量两观测点间距会忽略城市中的楼房、公园等障碍物等因素,导致两点间测得真实距离的偏差,从而对扫描结果造成影响, 提出了一种基于时间距离的时空重排扫描优化方法. 首先依据城市中障碍物对两点间实际路径的影响得到观测点间的真实路径,然后利用真实路径计算得到两观测点间的交通时间,最后利用交通时间来代替表示两点间的真实距离. 通过旧金山火灾数据集对本文优化方法进行验证,模型性能普遍提升了2%~5%.

English Abstract

  • 随着近些年来时空数据日益增长,时空数据挖掘给公共事件预警与分析提供了参考与依据[1-2]. 其中,时空异常挖掘是时空数据挖掘中新兴的一个领域,通过对时空数据所呈现异常特性的探测,从而挖掘其中所蕴含未知的知识,对相关领域发展提供帮助[1]. 例如在日常的交通拥堵中,交通管理部门可以根据时空异常有效地发现交通拥堵点,合理的安排车辆及行人出行[3];在气象方面,气象预报人员可以根据时空异常有效发现气象灾害分布情况,从而进一步深入判断其发展规律,为下一步灾害预测提供可靠依据[4];在对消防、犯罪及流行病等方面,预警人员通过对事件发生异常点进行检测,根据其时空特性,对事件的发生进行预警[3]. 正因时空异常探测的巨大研究价值,近些年已成为时空数据挖掘的关键领域[5-8].

    在时空异常探测中,主要涉及以下两种方法,分别是基于点数据异常挖掘和基于区域数据异常挖掘[9]. 基于点数据异常挖掘相较区域数据异常挖掘拥有更好的准确性,得到了更为广泛的应用. 扫描统计方法是点数据异常挖掘的常用手段,通过划定某一区域,计算该区域内某一类事件发生的次数与区域外事件发生次数的比值,并构造统计量,然后不断改变划定区域的范围和位置,搜索整个研究范围内统计量最大的区域,主要目的是探测和评估空间域或时空域内的聚集,从而解释无法通过空间或时空随机性解释的问题. 1965年Naus首先提出空间扫描统计方法的概念,利用规定尺寸的矩形窗口在空间域上对集群进行扫描[10];此后Loader在此基础上放宽了对矩形尺寸的限制[11]. Turnbull等提出了利用固定大小的圆形进行空间扫描的方法[12];Kulldorff等将固定大小的圆形扫描窗口扩展为可变大小的圆形扫描窗口,通过对圆形扫描窗口半径的变化,来寻找空间域中拥有显著性的圆形簇[13];2001年Kulldorff等在现有空间扫描统计方法的基础上,进行了一个重要的扩展,在空间扫描统计方法上加入了时间参量,提出了时空扫描统计方法[14];2005年Kulldorff等的工作进一步扩展,为了减少对风险人口数的依赖性,提出了时空重排扫描方法[15]. 虽然,Kulldorff等对模型进行了不断的修改,但是扫描窗口对于不规则大型实际数据集的探测仍有局限性.

    为了克服扫描窗口对大型不规则实际数据集探测的局限性问题,许多人员对扫描窗口进行了改进. 2015年Fanaee等提出了一种通过主空间和时间奇异向量中的异常元素的联合组合,近似时空空间中热点的方法[16]. 该方法与时空重排方法,利用对数似然比作为热点识别的标准不同,采用了跟踪空间和时间维度中,相关模式的变化来近似热点位置的方法. 该方法虽然在单个异常点的检测中具有较好的效果,但是在多异常点的检测中效果较差. 2017年Ullah等为了解决扫描窗口对不规则形状区域的扫描问题,提出了一种利用共聚类策略跟踪时空事件结构变化的方法,这种方法通过跟踪时空结构发生的变化进行异常探测,在一定程度上减少了形状对扫描的限制[17]. 2018年Choi等提出了一种惩罚似然法,以克服现有的方法中,局部空间聚类方法的局限性[18]. 该方法在检测局部空间聚类时,表现出很好的灵敏度和较高的特异性. 但是,该方法参数设置过多,会造成额外的计算量. 2019年Ktragadda等提出了一种利用多边形传播算法得到多边形扫描统计量的方法[19]. 该方法利用多边形传播算法,对多个三角形组成的多边形区域进行扫描,从而进行热点检测,较好的解决了实际研究区域的不规则问题. 但是该算法的时间复杂度与观测数量均为非线性,对于较大的数据集而言,其不能很好地进行扩展.

    上述研究虽然都对时空扫描窗口形状进行了改进,但没有考虑研究区域内地形、房屋等外在因素对真实距离测量造成的偏差. 在进行时空扫描时,单纯使用空间直线距离表示中心点与观察点间距离,忽略了地形等外界因素对于事件传播的影响[20-21],尤其在障碍物和人口较多的城市时空数据中,城市中的楼房、公园等障碍物都是不可忽略的重要因素,对这些因素的忽略都会造成最终扫描结果出现偏差.

    为了克服单纯使用空间直线距离表示中心点与观察点间距离的局限性问题,本文提出了一种基于空间两点间交通时间作为两点间距离的方法. 该方法可以归纳为3个步骤:①通过地图工具获取任意两观测点路径距离;②根据路径距离以及人流移动平均时间,计算量观测点间交通时间;③根据研究区域内各观测点间交通时间,判断观测点是否在扫描窗口内.

    本文的主要贡献是基于单纯使用空间直线距离表示中心点与观察点间距离的缺陷,提出了一种基于空间两点间交通时间作为两点间距离的方法. 该方法通过计算空间两点间的路径距离,根据平均人流速度获得空间两点间交通时间,并将其作为空间两点间真实距离. 通过此方法,可以将城市中的楼房、公园等障碍物等因素对扫描模型造成的影响加入到真实距离的计算中,从而提升扫描窗口获取到观测点的真实性.

    • 时空重排扫描方法[15]是由Kulldorff等在2005年基于时空扫描方法提出. 研究人员只需提前获知事件发生数,不再需要风险人口数. 该方法令时空扫描方法在人口数据缺失情况下依旧可以使用,提升了时空扫描模型应用范围.

      时空重排方法与时空扫描方法在原理上基本一致,均采用若干圆柱体柱面作为扫描窗口,从研究区域内寻找事件可能爆发的候选区域,其中圆柱底面大小代表潜在事件爆发的地理区域,底面中心为每一个观测点,圆柱体的高度代表了所研究的时间阈值,为了避免过大的扫描半径,通常将最大扫描半径 $R$ 的上限设置为研究地理区域大小的50%所对应的圆形区域半径. 时空重排扫描的示意图如图1所示.

      图  1  时空重排扫描示意图

      Figure 1.  Schematic diagram of space-time permutation scan statistic

      图1中,设实心圆点表示发生的事件,空间点位置 $\left( {x,y} \right)$ 在研究区域内所映射的点由数值 $s$ 来标记,则在 $s \in \left\{ {\left. {1,2,\cdots,m,\cdots,n} \right\}} \right.,1 \leqslant m \leqslant n,n \in R$$d \in \left\{ {1,2,\cdots,a,\cdots,D} \right\},1 \leqslant a \leqslant D,D \in R$ 的时空域内可以得到一个时空矩阵 ${{N}}$,其中,集合 $\left\{1,2,\cdots,\right. $$\left.m,\cdots,n\right\}$ 表示研究区域内的所有观测点,集合 $d \in \left\{ {1,2,\cdots,a,\cdots,D} \right\}$ 表示研究时间阈值内所对应的日期,时空矩阵 ${{N}}$ 也可以由公式(1)表示.

      ${{N}} = [{n_{sd}}] = \left( {\begin{array}{*{20}{c}} {{n_{11}}}& \cdots &{{n_{1D}}} \\ \vdots & & \vdots \\ {{n_{n1}}}& \cdots &{{n_{nD}}} \end{array}} \right),$

      其中,${n_{11}},{n_{12}},\cdots,{n_{nD}}$ 代表了在日期 $d$ 内,观测点 $s$ 处所发生的事件数.

      设2个观测点 $i$$j$ 的坐标为 $\left( {{x_i},{y_i}} \right)$$\left( {{x_j},{y_j}} \right)$,则它们之间的距离为 ${L_{ij}}$,利用地图的经纬度球面距离公式计算可以得到如公式(2)所示的空间距离矩阵 ${{L}}$,其中,由于距离的对称性,则 ${L_{ij}} = {L_{ji}}, {L_{ii}} = $${L_{jj}} = 0;i = 1,2,\cdots,m,\cdots,n;j = 1,2,\cdots,m,\cdots,n;1 \leqslant m \leqslant n$$n \in R $.

      ${{L}} = \left( {\begin{array}{*{20}{c}} 0& \cdots &{{L_{1n}}} \\ \vdots & & \vdots \\ {{L_{n1}}}& \cdots &0 \end{array}} \right),$

      其中,${L_{11}},{L_{12}},\cdots,{L_{nn}}$ 代表了集合 $\left\{ {\left. {1,2,\cdots,m,\cdots,n} \right\}} \right.$ 中任意两点的空间距离.

      在研究区域规定时间间隔内观察到的总事件数 $N$ 可以由公式(3)计算得到.

      $N = \sum\limits_s {\sum\limits_d {{n_{sd}}} } . $

      设所有观测点 $s$ 上全时段的事件数为 ${n_s}$,指定时间段 $d$ 上所有观测点的事件数为 ${n_d}$,其计算方法为:

      $ {{n_s} = \displaystyle\sum\limits_{d = 1}^D {{n_{sd}}} ,s \in \left\{ {\left. {{s_1},{s_2},\cdots,{s_m},\cdots,{s_n}} \right\}} \right.,} $

      ${{n_d} = \displaystyle\sum\limits_{s = 1}^{{S_n}} {{n_{sd}}} ,d \in \left\{ {1,2,\cdots,a,\cdots,D} \right\}. } $

      ${n_s}$${n_d}$ 是时空矩阵 ${{N}}$ 分别沿列和行值的累加和,称为空间和时间上的边缘累计和. 其中${n_{sd}}$ 是第 $d$ 天在观察点 $s$ 处观测到的事件数. 根据观测值可以得到每一个观测点每一天的事件数的期望 ${\mu _{sd}}$,并通过公式(6)计算得到.

      $\begin{split} {\mu _{sd}} =& \frac{{{n_d} \times {n_s}}}{N} = \frac{1}{N}\left( {\sum\limits_s {{n_{sd}}} } \right)\left( {\sum\limits_d {{n_{sd}}} } \right)= \\ &\frac{{\left( {\displaystyle\sum\limits_s {{n_{sd}}} } \right)\left( {\displaystyle\sum\limits_d {{n_{sd}}} } \right)}}{{\displaystyle\sum\limits_s {\displaystyle\sum\limits_d {{n_{sd}}} } }}. \end{split}$

      设圆柱体模型 ${\rm{H}}$ 的圆心是观测点集合中的任意一个,半径为 ${R_{\rm{H}}}$,则图1中圆柱体 ${\rm{H}}$ 内预期的事件数 , ${\mu _{\rm{H}}}$就是该圆柱体内所有观测点在研究时间内预期事件数的总和,其计算方法如公式(7)所示.

      ${\mu _{\rm{H}}} = \sum\limits_{\left( {s,d} \right) \in\rm H} {{\mu _{sd}}} . $

      假设在 $d$ 天中观测到事件数的期望,在研究区域内对于任意的 $d$ 天都是相同的. 且 ${n_{\rm{H}}}$ 是观测到的圆柱体 ${\rm{H}}$ 内的事件数. 在没有发生时空交互时,${C_{\rm{H}}}$ 服从均值为 ${n_{\rm{H}}}$ 的超几何分布[15],可以得到概率函数 $P\left( {{C_{\rm{H}}}} \right)$,其计算方法为:

      $P\left( {{C_{\rm{H}}}} \right) = {{\left(\!\! {\begin{array}{*{20}{c}} {\displaystyle\sum\limits_{s \in {\rm {H}}} {{n_{sd}}} } \\ {{n_{\rm {H}}}} \end{array}} \!\!\right)\left(\!\! {\begin{array}{*{20}{c}} {N - \displaystyle\sum\limits_{s \in {\rm{H}}} {{n_{sd}}} } \\ {\displaystyle\sum\limits_{d \in {\rm{H}}} {{n_{sd}} - {n_{\rm{H}}}} } \end{array}}\!\! \right)} \Bigg/ {\left(\!\! {\begin{array}{*{20}{c}} N \\ {\displaystyle\sum\limits_{d \in {\rm{H}}} {{n_{sd}}} } \end{array}}\!\! \right)}}.\!\!\!\!\!\!\! $

      $\displaystyle\sum\limits_{s \in {\rm{H}}} {{n_{sd}}}$$\displaystyle\sum\limits_{d \in {\rm{H}}} {{n_{sd}}}$$N$ 相对较小时,${n_{\rm{H}}}$ 可以近似为泊松分布,期均值为 ${\;\mu _{\rm{H}}}$[22]. 令 $G$ 是圆柱体的对数似然比,$I$ 是指示函数,这里用阶跃信号表示,如果左侧大于右侧,则 $I = 1$,否则 $I = 0$. $G$ 的计算方式如:

      $G \!=\! \log {\left( {\dfrac{{{n_{\rm{H}}}}}{{{\mu _{\rm{H}}}}}} \right)^{{n_{\rm{H}}}}}{\left( {\dfrac{{N - {n_{\rm{H}}}}}{{N - {\mu _{\rm{H}}}}}} \right)^{\left( {N - {n_{\rm{H}}}} \right)}}I\left( {\dfrac{{{n_H}}}{{{\mu _{\rm{H}}}}} > \dfrac{{N - {n_{\rm{H}}}}}{{N - {\mu _{\rm{H}}}}}} \right). \!\!\!\!\!\!\!\!\!$

      对所有圆柱体的对数似然比进行比较,找到不可能偶然发生的时空集群作为可能发生事件爆发的候选区域.

      但在城市中,楼房、公园等障碍物以及人口流动都是不可忽略的重要因素,如果将这些因素都考虑到,则无法单纯使用距离矩阵 ${{L}}$ 来表示集合 $\left\{ {\left. {1,2,\cdots,m,\cdots,n} \right\}} \right.$ 中任意两点的距离.

    • 本研究针对单纯使用距离矩阵 ${{L}}$ 来表示集合 $\left\{ {\left. {1,2,\cdots,m,\cdots,n} \right\}} \right.$ 中任意两点的距离所带来的缺陷,采用交通时间来表示中心点与观察点间距离. 交通时间可以理解为从一个观测点到达另外一个观测点的实际消耗时间. 在实际应用中,令能对周围其他事件造成影响的因素称为事件因子. 那么当运动个体携带事件因子从一个观测点抵达另一观测点的途中,可能会经过房屋、山地、湖泊等障碍物,这些障碍物可能会对事件因子携带个体的移动路径产生干扰. 所以,考虑到两观测点间障碍物等其他因素对距离测量干扰所得路径距离为 ${D_{ij}}$.

      假设,事件因子携带个体在移动中遇到了k次障碍物,每次遇到障碍物时,事件因子携带个体会沿着通畅的路径继续移动,直到到达目标位置,其示意图如图2所示. 其中,虚线代表了 $i$$j$ 两观测点间的直线距离,实线代表了两观测点间事件因子携带个体所走的真实距离. 则两点间的路径距离 ${D_{ij}} =\displaystyle \sum\limits_k {{D_k}} ,k = 1,2,\cdots,u$,其中 ${D_k}$ 为事件因子每一次遇到障碍物改变方向后所经过的最短空间距离.

      图  2  事件因子传播路径示意图

      Figure 2.  Schematic diagram of the event factor propagation path

      当假设事件因子携带个体的移动速度同人的平均步行速度一致,且人步行移动的平均速度为 ${v_{{\rm{person}}}}$. 此处为了在体现以人类活动为主的城市环境中两点间真实距离的同时,减小算法复杂度提升对模型运算速度的影响,所以事件因子携带个体移动速度采用人均步行移动速度. 那么,两观测点间的交通时间 ${T_{ij}}$ 的计算方法为:

      ${T_{ij}} = \frac{{{D_{ij}}}}{{{v_{{\rm{person}}}}}}. $

    • 通过结合交通时间计算方法,提出了一种基于时间距离的时空重排优化方法. 通过考虑障碍物等对于事件因子传播的影响,利用交通时间重新构成距离矩阵,以达到优化时空重排扫描方法的目的.

      设两个观测点 $i$$j$ 的坐标为 $\left( {{x_i},{y_i}} \right)$$\left( {{x_j},{y_j}} \right)$,则它们之间的交通时间为 ${T_{ij}}$,利用地图工具可以得到两点间的步行距离以及步行时间,从而可以得到交通时间矩阵 ${{ T}}$,其计算方法如公式(11)所示. 其中,由于步行路径的对称性,则 ${T_{ij}} = {T_{ji}},{T_{ii}} = {T_{jj}} = $$ 0$$i = 1,\,2,\,\cdots,\,m,\cdots,n;j = 1,\,2,\,\cdots,\,m,\,\cdots, n;\,1 \leqslant m \leqslant n,$$ n \in R$. 时空重排扫描优化方法的基本原理图如图3所示. 其中 ${T_{11}},{T_{12}},\cdots,{T_{SS}}$ 代表了集合 $\left\{1,2,\cdots,m,\cdots,\right. $$\left. n \right\}$ 中任意两点的交通时间.

      图  3  时空重排扫描优化方法基本原理图

      Figure 3.  Basic schematic diagram of space-time permutation scan optimization method

      ${{T}} = \left( {\begin{array}{*{20}{c}} 0& \cdots &{{T_{1n}}} \\ \vdots & & \vdots \\ {{T_{n1}}}& \cdots &0 \end{array}} \right). $

    • 为了更好的评价距离矩阵 ${{ L}}$ 替换为交通距离矩阵 ${{ T}}$ 后,扫描圆柱体内事件总数 ${n_{\rm{H}}}$ 改变对模型性能的影响. 本文引入调和平均值 $F$ 作为目标函数[23],其计算方法为:

      $F = \frac{1}{{\dfrac{1}{{{S_{\rm{P}}}}} + \dfrac{1}{{{S_{\rm{R}}}}}}},$

      其中,${S_{\rm{P}}}$ 表示空间命中率,${S_{\rm{R}}}$ 表示空间精确度,其由公式(13)计算得出.

      $\left\{ {\begin{array}{*{20}{c}} {{S_{\rm{P}}} = \dfrac{{\left| {{Z^ * } \cap {Z_{{\rm{true}}}}} \right|}}{{\left| {{Z^ * }} \right|}},}\\ {{S_{\rm{R}}} = \dfrac{{\left| {{Z^ * } \cap {Z_{{\rm{true}}}}} \right|}}{{\left| {{Z_{{\rm{true}}}}} \right|}},} \end{array}} \right.$

      其中,${Z^ * }$ 表示通过时空重排扫描方法发现的预警点的个数,${Z_{{\rm{true}}}}$ 表示研究区域内确实爆发事件的点的个数.

      调和平均值 $F$ 通过权衡精确度和命中率之间的关系,避免了空间命中率和空间精确度单一评价指标对实验结果进行评价产生的误差.

    • 基于时间距离的时空重排优化算法的结果可通过以下步骤得到,算法流程图如图4所示.

      图  4  时空重排扫描优化方法流程图

      Figure 4.  Flow chart of space-time permutation scan optimization method

      步骤1 获取所研究地域内某一时段的案件发生数据,并生成时空矩阵 ${{ N}}$

      步骤2 利用地图工具计算研究区域内观测点之间的路径距离 ${D_{ij}}$

      步骤3 根据研究区域内观测点之间的路径距离生成观测点间的交通时间矩阵 ${{ T}}$

      步骤4 循环:从观测点集 $\left\{ {\left. {1,2,\cdots,m,\cdots,n} \right\}} \right.$ 中依次选取观测点作为扫描中心,扫描半径递增直至最大扫描半径,对数据进行时空重排扫描,直至观测点集 $\left\{ {\left. {1,2,\cdots,m,\cdots,n} \right\}} \right.$ 中的观测点均作为扫描中心点时,扫描结束;

      步骤5 获取时空重排扫描结果.

    • 在现实中存在着大量时空数据,为了验证优化方法的性能. 本研究采用旧金山地区数据协调网站DataSF(https://datasf.org/opendata/)提供的“Fire Department Service”数据作为实验数据集,且已有研究人员在研究中证明火灾事件可以作为时空事件进行研究[24-25]. 为了便于准确率和命中率的计算,这里提取2018年度的火灾事件数据进行实验. 并且为了方便时空重排扫描方法的使用,在实验前对研究区域内的42个观测点进行了编号,如表1所示. 并根据观测地点、事件发生时间以及事件发生个数,对实验数据集进行了整理,生成了便于时空重排扫描的数据集,如表2所示.

      地点名称地点编号地点名称地点编号
      Tenderloin1Outer Richmond8
      Mission2Inner Sunset9
      South of Market3Mission Bay10
      Haight Ashbury4Pacific Heights11
      Noe Valley5Parkside12
      North Beach6······
      Financial District7Seacliff42

      表 1  旧金山火灾事件观测地点编号

      Table 1.  Numbers of the fire incident observation site in San Francisco

      地点
      编号
      日期火灾事件
      发生数
      地点
      编号
      日期火灾事件
      发生数
      402018-01-01132018-01-011
      252018-01-01322018-01-013
      182018-01-01512018-01-011
      162018-01-011322018-01-011
      102018-01-011172018-01-011
      72018-01-015······
      42018-01-011272018-12-311

      表 2  时空重排扫描数据集

      Table 2.  Scanned data sets of the space–time permutation

      在本研究中,为了准确计算两点间的交通时间. 采用谷歌地图中的两点间步行时间作为交通时间进行实验.

    • 在实验中,总共抽取了3个时间段的数据分别使用进行时空重排扫描方法与时空重排扫描优化方法进行实验,并在用调和平均值 $F$ 作为目标函数来评价两种方法的性能.

      分别选取2018年2月1日~2018年2月7日、2018年5月1日~2018年5月7日、2018年10月1日~2018年10月7日旧金山地区的火灾事件作为时空重排扫描的扫描时间段. 研究区域空间大小50%所对应的圆形区域半径作为时空重排扫描方法的最大扫描半径[15],即10 km. 根据人步行的平均速率,时空重排扫描优化方法的最大扫描半径为10 km所对应的步行时长125 min. 并将这3个时间段的第8日开始的7 d作为火灾预警时间段,为了方便验证,从数据集中提取2018年2月8日~2018年2月14日、2018年5月8日~2018年5月14日、2018年10月8日~2018年10月14日这3个时间段中42个观测点的火灾发生情况,如图5所示. 从图中观察可以得到,2018年2月8日~2018年2月14日、2018年5月8日~2018年5月14日、2018年10月8日~2018年10月14日3个时间段的旧金山火灾事件发生情况,如表3所示.

      时间实际发生火灾事件的观测点观测点个数
      2018-2-8~2018-2-14 [1,2,3,4,6,7,8,9,10,11,12,13,14,16,17,18,19,20,21,22,23,24,25,27,28,29,30,32,33,35,36] 31
      2018-5-8~2018-5-14 [1,2,3,4,5,6,7,8,10,12,13,14,16,17,18,19,20,21,22,23,24,25,26,27,29,30,33,38,39] 29
      2018-10-8~2018-10-14 [1,2,3,4,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,22,23,24,26,28,29,30,31,32,33,34,36,37,39] 33

      表 3  实际发生火灾的观测点情况

      Table 3.  Observation points of actual fires

      图  5  42个观测点火灾实际发生情况图

      Figure 5.  Actual situation of fire at 42 observation points

      使用时空扫描重排传统及优化方法对2018年2月1日~2018年2月7日的火灾数据进行扫描,可以得到如图6所示的扫描结果. 为了更好地表现实验结果,在图中用火焰图标表示未预警到的火灾发生点,用停止图标表示预警到的火灾发生点. 通过观察图6可得到如表4所示预警结果.

      扫描方法预警观测点
      传统方法 [2, 4, 5, 8, 9, 10, 12, 13, 14, 15, 17, 18, 22, 23, 24, 25, 26, 29, 30, 31, 32, 33, 34, 35, 38, 39, 40, 41, 42]
      优化方法 [1, 2, 3, 4, 5, 9, 10, 12, 13, 14, 15, 17, 18, 22, 23, 24, 25, 29, 30, 31, 32, 33, 35, 38, 40, 41, 42]

      表 4  2018年2月1日~2018年2月7日时空重排扫描方法预警观测点

      Table 4.  Early warning observation points of the Space–Time Permutation Scanning method from February 1 to 7, 2018

      图  6  2018年2月1日~2018年2月7日时空重排扫描方法扫描结果

      Figure 6.  Scanning results of the Space–Time Permutation Scanning method from February 1 to 7, 2018

      为了更好的表现对照结果,在图6(b)中用黑色方框将与传统扫描方式所得结果(图6(a))不同的观测点进行了标注. 通过观察可以发现相较于传统扫描方法,优化扫描方法通过采用新的距离测量手段探测到了1、3号观测点,但8号观测点被忽视,总体上增加了1个被命中的观测点.

      使用时空扫描重排传统及优化方法对2018年5月1日~2018年5月7日的火灾数据进行扫描,可以得到如图7所示的扫描结果. 为了更好地表现实验结果,在图中用火焰图标表示未预警到的火灾发生点,用停止图标表示预警到的火灾发生点. 通过观察图7可得到如表5所示预警结果.

      扫描方法预警观测点
      传统方法[1, 3, 8, 11, 13, 16, 18, 20, 21, 22, 24, 27, 31, 35, 36, 37, 38, 39, 40, 41, 42]
      优化方法[1, 3, 4, 7, 8, 9, 10, 11, 17, 18, 20, 21, 24, 26, 27, 28, 29, 34, 37, 39, 40, 41, 42]

      表 5  2018年5月1日~2018年5月7日时空重排扫描方法预警观测点

      Table 5.  Early warning observation points of the Space–Time Permutation Scanning method from May 1 to 7, 2018

      图  7  2018年5月1日~2018年5月7日时空重排扫描方法扫描结果

      Figure 7.  Scanning results of the Space–Time Permutation Scanning method from May 1 to 7, 2018

      为了更好的表现对照结果,图7(b)中用黑色方框将与传统扫描方式所得结果(图7(a))不同的观测点进行了标注. 通过观察可以发现相较于传统扫描方法,优化扫描方法通过采用新的距离测量手段探测到了4、7、10、17、26、29号观测点,但16号观测点被忽视,总体上增加了5个被命中的观测点.

      使用时空扫描重排传统及优化方法对2018年10月1日~2018年10月7日的火灾数据进行扫描,可以得到如图8所示的扫描结果. 为了更好地表现实验结果,在图中用火焰图标表示未预警到的火灾发生点,用停止图标表示预警到的火灾发生点. 通过观察图8可得到如表6所示预警结果.

      扫描方法预警观测点
      传统方法[1, 2, 3, 4, 6, 7, 8, 9, 11, 14, 15, 16, 17, 20, 21, 26, 27, 28, 29, 34, 35, 36, 37, 38, 39, 40, 41, 42]
      优化方法[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 20, 21, 25, 26, 27, 28, 29, 31, 34, 35, 36, 37, 39, 40, 41, 42]

      表 6  2018年5月1日~2018年5月7日时空重排扫描方法预警观测点

      Table 6.  Early warning observation points of the Space–Time Permutation Scanning method from October 1 to 7, 2018

      图  8  2018年10月1日~2018年10月7日时空重排扫描方法扫描结果

      Figure 8.  Scanning results of the Space–Time Permutation Scanning method from October 1 to 7, 2018

      为了更好的表现对照结果,图8(b)中用黑色方框将与传统扫描方式所得结果(图8(a))不同的观测点进行了标注. 通过观察可以发现相较于传统扫描方法,优化扫描方法通过采用新的距离测量手段探测到了10、12、18、31号观测点,总体上增加了4个被命中的观测点.

      根据上述实验,可以得到这3组对比实验所对应时空重排扫描方法与时空重排扫描优化方法的预警结果,根据预警结果与火灾实际发生情况,可以计算得到两种方法的命中率(${S\!_{\rm{P}}}$)、精确度(${S\!_{\rm{R}}}$)和调和平均值($F$),如表79所示.

      扫描方法评价指标传统方法优化方法
      ${S\!_{\rm{P}}}$61.3%64.5%
      ${S\!_{\rm{R}}}$65.5%74.1%
      $F$0.3160.345

      表 7  2018年2月1日~2018年2月7日2种方法扫描结果的 ${S\!_{\rm{P}}}$${S\!_{\rm{R}}}$$F$

      Table 7.  ${S\!_{\rm{P}}}$, ${S\!_{\rm{R}}}$ and $F$ of the scanning results of the two methods from February 1 to 7, 2018

      扫描方法
      评价指标
      传统方法优化方法
      ${S\!_{\rm{P}}}$44.8%51.7%
      ${S\!_{\rm{R}}}$61.9%65.2%
      $F$0.260.288

      表 8  2018年5月1日~2018年5月7日2种方法扫描结果的 ${S\!_{\rm{P}}}$${S\!_{\rm{R}}}$$F$

      Table 8.  ${S\!_{\rm{P}}}$, ${S\!_{\rm{R}}}$ and $F$ of the scanning results of the two methods from May 1 to 7, 2018

      扫描方法
      评价指标
      传统方法优化方法
      ${S\!_{\rm{P}}}$66.7%78.7%
      ${S\!_{\rm{R}}}$78.6%78.8%
      $F$0.3610.393

      表 9  2018年10月1日~2018年10月7日2种方法扫描结果的 ${S\!_{\rm{P}}}$${S\!_{\rm{R}}}$$F$

      Table 9.  ${S\!_{\rm{P}}}$, ${S\!_{\rm{R}}}$ and $F$ of the scanning results of the two methods from October 1 to 7, 2018

      根据表79的数据可以看出,在使用时空重排扫描优化方法进行实验时,其 ${S\!_{\rm{P}}}$${S\!_{\rm{R}}}$ 以及 $F$ 的值相对于时空重排扫描方法,都有了不同程度的提升,由此可以得出优化方法对时空重排扫描方法性能的提升是有效的.

    • 时空重排扫描方法是时空数据挖掘中时空异常探测的新兴方法,在本研究中该方法用于短期时空事件的预警研究. 本研究的目的是通过考虑时空重排扫描时障碍物和人口较多的城市时空数据中,城市中的楼房、公园等障碍物等因素对于扫描方法性能的影响. 提出了一种基于空间两点间交通时间作为两点间距离的方法,经过试验比对,使用本方法,模型的性能普遍提升了2%~5%,最终证明了在使用时空重排优化算法进行扫描时,模型的性能得到了提升.

      这项研究的重要性在于,通过使用交通时间作为两点间距离,在扫描模型中增加了地形、房屋等阻碍物因素,使得扫描模型更加适用于实际数据的使用. 但是,在实际数据中,对于模型可能造成影响的因素还有很多,例如天气因素、政策因素等,在以后的研究中,将会尝试加入更多参考因素以进一步提升模型的有效性.

参考文献 (25)

目录

    /

    返回文章
    返回