留言板

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

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

一种基于重排检验的时空聚类方法

唐建波 刘启亮 刘博 邓敏 黄金彩 胡卫松

唐建波, 刘启亮, 刘博, 邓敏, 黄金彩, 胡卫松. 一种基于重排检验的时空聚类方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(4): 503-511. doi: 10.13203/j.whugis20141016
引用本文: 唐建波, 刘启亮, 刘博, 邓敏, 黄金彩, 胡卫松. 一种基于重排检验的时空聚类方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(4): 503-511. doi: 10.13203/j.whugis20141016
TANG Jianbo, LIU Qiliang, LIU Bo, DENG Min, HUANG Jincai, HU Weisong. A Spatio-temporal Clustering Method Based on Permutation Test[J]. Geomatics and Information Science of Wuhan University, 2017, 42(4): 503-511. doi: 10.13203/j.whugis20141016
Citation: TANG Jianbo, LIU Qiliang, LIU Bo, DENG Min, HUANG Jincai, HU Weisong. A Spatio-temporal Clustering Method Based on Permutation Test[J]. Geomatics and Information Science of Wuhan University, 2017, 42(4): 503-511. doi: 10.13203/j.whugis20141016

一种基于重排检验的时空聚类方法

doi: 10.13203/j.whugis20141016
基金项目: 

国家自然科学基金 41471385, 41171351,41601410

资源与环境信息系统国家重点实验室开放基金 

中南大学中央高校基本科研业务费专项资金 2016zzts084

详细信息

A Spatio-temporal Clustering Method Based on Permutation Test

Funds: 

The National Natural Science Foundation of China 41471385, 41171351,41601410

State Key Laboratory of Resources and Environmental Information System Foundation 

Fundamental Research Funds for the Central Universities of Central South University 2016zzts084

More Information
  • 摘要: 融合时空邻近与专题属性相似的时空聚类是挖掘地理现象时空演化规律的重要手段。现有方法需要的聚类参数许多难以获取,影响了聚类方法的可操作性与聚类结果的可靠性。提出一种基于重排检验的时空聚类方法。首先,通过重排检验发现时空数据集中的均质子区域;进而,采用均方误差准则合并均质子区域内的时空实体生成时空簇,并通过簇内重排检验自动识别聚类合并的终止条件;最后,借助时空拓扑关系在保证结果精度的前提下发展一种快速重排检验的方法,提高了聚类方法的运行效率。通过实验和比较发现,该方法一方面可以发现不同形状、大小的时空簇,聚类质量优于经典的ST-DBSCAN方法;另一方面聚类过程中人为设置参数的主观性显著降低,提高了聚类方法的可操作性。
  • 图  1  实体A的时空邻域

    Figure  1.  Spatio-temporal Neighborhood of an Entity A

    图  2  基于随机重排计算局部方差的显著性

    Figure  2.  A Sample Dataset and p-value Computation Based on Random Permutation

    图  3  月降水数据聚类结果

    Figure  3.  Results of the Proposed Clustering Method on the Monthly Precipitation Data

    图  4  ST-DBSCAN聚类结果 (Eps1=300 km, Eps2=5.7 mm, MinPts=9)

    Figure  4.  Results of ST-DBSCAN Algorithm

    表  1  随机重排检验与快速随机重排检验的运行时间比较/s

    Table  1.   Comparison of Running Times Between General Permutation Test Method and the Proposed Method/s

    数据集实体数拓扑数100次500次1 000次5 000次10 000次
    MCFMCMCFMCMCFMCMCFMCMCFMC
    测试数据15030.1180.0120.5820.045 1.1620/.0915.8790.44911.9610.901
    测试数据257641.4460.0287.0150.08913.4340.16469.2740.762138.6671.544
    测试数据314 4041335.4310.532178.4451.193361.0392.0521 771.4709.1633 559.37918.948
    注:为了减少随机因素影响,运行时间取20次重复试验的平均值。
    下载: 导出CSV
  • [1] 李德仁, 王树良, 李德毅, 等. 论空间数据挖掘和知识发现的理论与方法[J]. 武汉大学学报·信息科学版, 2002, 27(3):221-233 http://ch.whu.edu.cn/CN/abstract/abstract4949.shtml

    Li Deren, Wang Shuliang, Li Deyi,et al. Theories and Technologies of Spatial Data Mining and Knowledge Discovery[J]. Geomatics and Information Science of Wuhan University, 2002, 27(3):221-233 http://ch.whu.edu.cn/CN/abstract/abstract4949.shtml
    [2] Rao K V, Govardhan A, Rao K V C. Spatio-temporal Data Mining:Issues, Tasks and Applications[J].International Journal of Computer Science & Engineering Survey (IJCSES), 2012, 3(1):39-52 http://airccse.org/journal/ijcses/papers/0212ijcses04.pdf
    [3] Kisilevich S, Mansmann F, Nanni M, et al. Spatio-temporal Clustering[M]//Maimon O, Rokach L. Data Mining and Knowledge Discovery Handbook. 2nd edition. New York:Springer Press, 2010:855-874
    [4] 邓敏, 刘启亮, 王佳璆, 等. 时空聚类分析的普适性方法[J]. 中国科学:信息科学, 2012, 42(1):111-124 http://www.cnki.com.cn/Article/CJFDTOTAL-PZKX201201011.htm

    Deng Min, Liu Qiliang, Wang Jiaqiu, et al. A General Method of Spatio-temporal Clustering Analysis[J]. Scientia Sinica Informationis, 2012, 42(1):111-124 http://www.cnki.com.cn/Article/CJFDTOTAL-PZKX201201011.htm
    [5] 王劲峰, 葛勇, 李连发, 等. 地理学时空数据分析方法[J]. 地理学报, 2014, 69(9):1326-1345 http://www.cnki.com.cn/Article/CJFDTOTAL-DLXB201409008.htm

    Wang Jinfeng, Ge Yong, Li Lianfa, et al. Spatio Temporal Data Analysis in Geography[J]. Acta Geographica Sinica, 2014, 69(9):1326-1345 http://www.cnki.com.cn/Article/CJFDTOTAL-DLXB201409008.htm
    [6] Birant D, Kut A. ST-DBSCAN:An Algorithm for Clustering Spatial-temporal Data[J].Data & Knowledge Engineering, 2007, 60(1):208-221
    [7] 焦利民, 洪晓峰, 刘耀林. 空间和属性双重约束下的自组织空间聚类研究[J]. 武汉大学学报·信息科学版, 2011, 36(7):862-866 http://ch.whu.edu.cn/CN/abstract/abstract608.shtml

    Jiao Limin, Hong Xiaofeng, Liu Yaolin. Self-organizing Spatial Clustering Under Spatial and Attribute Constraints[J].Geomatics and Information Science of Wuhan University, 2011, 36(7):862-866 http://ch.whu.edu.cn/CN/abstract/abstract608.shtml
    [8] Pei T, Zhou C, Zhu A X, et al. Windowed Nearest Neighbor Method for Mining Spatio-temporal Clusters in the Presence of Noise[J].International Journal of Geographical Information Science, 2010, 24(6):925-948 doi:  10.1080/13658810903246155
    [9] Hagenauer J, Helbich M. Hierarchical Self-organizing Maps for Clustering Spatiotemporal Data[J]. International Journal of Geographical Information Science, 2013, 27(10):2026-2042 doi:  10.1080/13658816.2013.788249
    [10] 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
    [11] Takahashi K, Kulldorff M, Tango T, et al. A Flexibly Shaped Space-time Scan Statistic for Disease Outbreak Detection and Monitoring[J].International Journal of Health Geographics, 2008, 7(1):1-14 doi:  10.1186/1476-072X-7-1
    [12] Li X Z, Wang J F, Yang W Z, et al. A Spatial Scan Statistic for Multiple Clusters[J].Mathematical Biosciences, 2011, 233(2):135-142 doi:  10.1016/j.mbs.2011.07.004
    [13] Wan Y, Pei T, Zhou C, et al. ACOMCD:A Multiple Cluster Detection Algorithm Based on the Spatial Scan Statistic and Ant Colony Optimization[J]. Computational Statistics & Data Analysis, 2012, 56(2):283-296
    [14] Ester M, Kriegel H P, Sander J, et al. A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C].The 2nd International Conference on Knowledge Discovery and Data Mining, Portland, 1996
    [15] Joshi D, Samal A, Soh L K. Spatio-temporal Polygonal Clustering with Space and Time as First-class Citizens[J].GeoInformatica, 2012, 17(2):387-412
    [16] 李光强,邓敏,刘启亮,等.一种适应局部密度变化的空间聚类方法[J].测绘学报,2009,38(3):255-263 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200903011.htm

    Li Guangqiang, Deng Min, Liu Qiliang, et al. A Spatial Clustering Method Adaptive to Local Density Change[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(3):255-263 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200903011.htm
    [17] 石岩, 刘启亮, 邓敏, 等. 融合图论与密度思想的混合空间聚类方法[J]. 武汉大学学报·信息科学版, 2012, 37(11):1276-1280 http://ch.whu.edu.cn/CN/abstract/abstract379.shtml

    Shi Yan, Liu Qiliang, Deng Min, et al. A Hybrid Spatial Clustering Method Based on Graph Theory and Spatial Density[J]. Geomatics and Information Science of Wuhan University, 2012, 37(11):1276-1280 http://ch.whu.edu.cn/CN/abstract/abstract379.shtml
    [18] Anselin L. Local Indicators of Spatial Association-LISA[J]. Geographical analysis, 1995, 27(2):93-115 http://dces.wisc.edu/wp-content/uploads/sites/30/2013/08/W4_Anselin1995.pdf
    [19] Benjamini Y, Hochberg Y. Controlling the False Discovery Rate:A Practical and Powerful Approach to Multiple Testing[J].Journal of the Royal Statistical Society Series B (Methodological), 1995, 1(1):289-300 http://www.umassmed.edu/contentassets/a7bd41506c5a4308b401e312a7ff59fc/controlling-the-false-discovery-rate-manuscript.pdf
    [20] Guo D. Greedy Optimization for Contiguity-constrained Hierarchical Clustering[C].IEEE 4th International Workshop on Spatial and Spatiotemporal Data Mining, Florida,2009
    [21] 刘明光. 中国自然地理图集[M]. 3版. 北京:中国地图出版社, 2010

    Liu Mingguang. Atlas of Physical Geography of China[M]. 3rd Edition. Beijing:China Cartographic Publishing House, 2010
  • [1] 罗芳, 艾廷华, 贾小斌.  空间自相关支撑下的地类分布模式一致性评价 . 武汉大学学报 ● 信息科学版, 2022, 47(7): 1017-1024. doi: 10.13203/j.whugis20200179
    [2] 王昶, 张永生, 王旭.  基于变分法与Markov随机场模糊局部信息聚类法的SAR影像变化检测 . 武汉大学学报 ● 信息科学版, 2021, 46(6): 844-851. doi: 10.13203/j.whugis20190167
    [3] 盛宇裕, 毕硕本, 范京津, NKUNZIMANAAthanase, 许志慧.  运用交通运行状况指标分析交通热点时空模式 . 武汉大学学报 ● 信息科学版, 2021, 46(5): 746-754. doi: 10.13203/j.whugis20190357
    [4] 程诗奋, 彭澎, 张恒才, 陆锋.  异质稀疏分布时空数据插值、重构与预测方法探讨 . 武汉大学学报 ● 信息科学版, 2020, 45(12): 1919-1929. doi: 10.13203/j.whugis20200488
    [5] 李延, 王大魁, 耿晶, 王树良.  数据质量聚类算法 . 武汉大学学报 ● 信息科学版, 2019, 44(1): 153-158. doi: 10.13203/j.whugis20150760
    [6] 李玉, 胡海峰, 赵雪梅, 赵泉华.  基于可变形状参数Gamma分布的模糊聚类多视SAR图像分割 . 武汉大学学报 ● 信息科学版, 2018, 43(7): 984-992. doi: 10.13203/j.whugis20160149
    [7] 岳瀚, 朱欣焰, 呙维, 佘冰, 高超.  Knox时空交互检验空间阈值确定方法 . 武汉大学学报 ● 信息科学版, 2018, 43(11): 1719-1724. doi: 10.13203/j.whugis20170017
    [8] 陈俊平, 周建华, 严宇, 陈倩, 王彬.  GNSS数据处理时空参数的相关性 . 武汉大学学报 ● 信息科学版, 2017, 42(11): 1649-1657. doi: 10.13203/j.whugis20170278
    [9] 万幼, 周脚根, 翁敏.  点集数据不规则形状时空异常聚类模式挖掘研究 . 武汉大学学报 ● 信息科学版, 2017, 42(7): 924-930. doi: 10.13203/j.whugis20150069
    [10] 胡勇, 罗文, 俞肇元, 冯琳耀.  多维时空场数据的多模式张量表达模型 . 武汉大学学报 ● 信息科学版, 2015, 40(7): 977-982. doi: 10.13203/j.whugis20130491
    [11] 许宁, 尹凌, 胡金星.  从大规模短期规则采样的手机定位数据中识别居民职住地 . 武汉大学学报 ● 信息科学版, 2014, 39(6): 750-756. doi: 10.13203/j.whugis20140085
    [12] 田晶, 张泊宇, 杨雯雨.  对自组织映射聚类实现道路网网格模式识别 . 武汉大学学报 ● 信息科学版, 2013, 38(11): 1330-1334.
    [13] 孔令桥, 秦昆, 龙腾飞.  利用二型模糊聚类进行全球海表温度数据挖掘 . 武汉大学学报 ● 信息科学版, 2012, 37(2): 215-219.
    [14] 李德仁, 眭海刚, 单杰.  论地理国情监测的技术支撑 . 武汉大学学报 ● 信息科学版, 2012, 37(5): 505-512.
    [15] 邹志强, 江南, 吴家皋, 王汝传.  一种基于语义分簇聚类的P2P空间数据索引机制 . 武汉大学学报 ● 信息科学版, 2011, 36(1): 76-81.
    [16] 刘启亮, 李光强, 邓敏.  一种基于局部分布的空间聚类算法 . 武汉大学学报 ● 信息科学版, 2010, 35(3): 373-377.
    [17] 王海军, 邓羽, 王丽, 关兴良.  基于数据场的C均值聚类方法研究 . 武汉大学学报 ● 信息科学版, 2009, 34(5): 626-629.
    [18] 喻永平, 陈晓勇, 刘经南, 都洁.  状态扩展元胞自动机模型在时空数据挖掘中的应用 . 武汉大学学报 ● 信息科学版, 2008, 33(6): 592-595.
    [19] 胡春春, 孟令奎, 谢文君, 周新忠.  空间数据模糊聚类的有效性评价 . 武汉大学学报 ● 信息科学版, 2007, 32(8): 740-743.
    [20] 唐亮, 黄培之, 谢维信.  顾及数据空间分布特性的模糊C-均值聚类算法研究 . 武汉大学学报 ● 信息科学版, 2003, 28(4): 476-479.
  • 加载中
图(4) / 表(1)
计量
  • 文章访问数:  1252
  • HTML全文浏览量:  77
  • PDF下载量:  442
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-08-22
  • 刊出日期:  2017-04-05

一种基于重排检验的时空聚类方法

doi: 10.13203/j.whugis20141016
    基金项目:

    国家自然科学基金 41471385, 41171351,41601410

    资源与环境信息系统国家重点实验室开放基金 

    中南大学中央高校基本科研业务费专项资金 2016zzts084

    作者简介:

    唐建波,博士生,主要从事时空数据聚类分析的理论与方法研究。jianbo.tang@csu.edu.cn

    通讯作者: 刘启亮,博士。qiliang.liu@csu.edu.cn
  • 中图分类号: P208

摘要: 融合时空邻近与专题属性相似的时空聚类是挖掘地理现象时空演化规律的重要手段。现有方法需要的聚类参数许多难以获取,影响了聚类方法的可操作性与聚类结果的可靠性。提出一种基于重排检验的时空聚类方法。首先,通过重排检验发现时空数据集中的均质子区域;进而,采用均方误差准则合并均质子区域内的时空实体生成时空簇,并通过簇内重排检验自动识别聚类合并的终止条件;最后,借助时空拓扑关系在保证结果精度的前提下发展一种快速重排检验的方法,提高了聚类方法的运行效率。通过实验和比较发现,该方法一方面可以发现不同形状、大小的时空簇,聚类质量优于经典的ST-DBSCAN方法;另一方面聚类过程中人为设置参数的主观性显著降低,提高了聚类方法的可操作性。

English Abstract

唐建波, 刘启亮, 刘博, 邓敏, 黄金彩, 胡卫松. 一种基于重排检验的时空聚类方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(4): 503-511. doi: 10.13203/j.whugis20141016
引用本文: 唐建波, 刘启亮, 刘博, 邓敏, 黄金彩, 胡卫松. 一种基于重排检验的时空聚类方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(4): 503-511. doi: 10.13203/j.whugis20141016
TANG Jianbo, LIU Qiliang, LIU Bo, DENG Min, HUANG Jincai, HU Weisong. A Spatio-temporal Clustering Method Based on Permutation Test[J]. Geomatics and Information Science of Wuhan University, 2017, 42(4): 503-511. doi: 10.13203/j.whugis20141016
Citation: TANG Jianbo, LIU Qiliang, LIU Bo, DENG Min, HUANG Jincai, HU Weisong. A Spatio-temporal Clustering Method Based on Permutation Test[J]. Geomatics and Information Science of Wuhan University, 2017, 42(4): 503-511. doi: 10.13203/j.whugis20141016
    • 随着对地观测系统、传感网络和移动监测设备的飞速发展,时空数据的获取能力显著提升[1, 2]。由于空间、时间和专题属性信息耦合的复杂性,时空数据的分析和处理较空间数据更为困难。发现时空数据的分布模式是时空数据分析的一个重要任务,亦是进一步分析地理现象时空动态变化过程与演化规律的基础[3]。时空聚类是挖掘时空数据分布模式的主要手段,旨在从时空数据库中发现具有相似特征的时空实体的集合 (即时空簇),已受到地球信息科学与计算机科学领域学者的广泛关注[4-7]。当前时空聚类方法主要可以分为空间聚类和时空耦合的方法,前者将同一空间位置上不同时间点的专题属性观测值作为空间单元的一个多维属性进行空间聚类;后者主要针对空间位置固定,专题属性随时间变化的时空数据,将专题属性的观测值视为附加了空间和时间属性的时空实体,时空数据为这些观测值 (即时空实体) 的集合,进一步针对时空实体进行聚类。空间聚类的方法忽视了时空实体在时间维度上的动态性,导致其发现地理现象时空动态变化的能力有限,因此时空耦合的方法更适合发现地理现象的时空演化模式[8]。鉴于此,本文主要针对基于时空耦合思想的时空聚类方法进行探索和研究。

      目前基于时空耦合的时空聚类方法主要包括基于时空距离的方法、时空扫描统计方法及基于密度的方法[4]。基于时空距离的方法融合时空实体的空间位置、时间和专题属性信息, 定义一种混合的时空距离,进而采用K-means、模糊C均值 (fuzzy C-means, FCM)、自组织映射神经网络 (self-organizing map, SOM) 等空间划分聚类方法进行聚类。如2013年Hagenauer等[9]在单层SOM聚类的基础上构建了一种多隐含层HSTSOM (hierarchical spatio-temporal SOM) 神经网络,并提出了STKM (spatio-temporal kangas map) 时空聚类方法,用于社会经济时空数据的分析;2014年王劲峰等[5]借助自组织映射SOM对中国中东部区域的手足口病和降雨数据进行时空聚类,提取出疾病和降雨的时空格局。基于时空距离的方法中混合距离的定义较为困难,需要较多的先验知识,同时需要簇的数目作为参数,且难以识别复杂形状的时空簇[4, 6]。时空扫描统计方法则以最大似然比检验为理论基础,采用一定形状且大小可变的扫描窗口对数据进行扫描,定位异常聚集的区域,并对聚类结果进行显著性检验,主要应用于疾病、犯罪等时空事件的聚集模式探测。2005年Kulldorff等[10]首先提出了基于重排检验的时空扫描统计方法,用于发现传染疾病的聚集和疾病暴发的早期预警;2008年Takahashi等[11]针对扫描窗口形状的限制,发展了一种任意形状扫描窗口的时空扫描统计方法;2011年Li等[12]针对扫描统计方法探测多个簇的问题,以数据集中存在多个簇为零假设构造扫描统计量,探测数据集中的多个聚类;2012年Wan等[13]以扫描统计方法探测的簇为初始聚类,进而采用蚁群算法进行优化,以识别不同形状的簇。时空扫描统计方法具有严密的理论基础,但是也存在一些局限,如需要首先假设数据的概率分布模型,使得实际数据难以找到合适的概率模型,且聚类质量受扫描窗口形状的影响,对近似球形的簇比较有效,难以准确识别复杂形状的多个时空簇[4]等。基于密度的方法多是在经典空间聚类算法DBSCAN[14]的基础上增加时间窗口和专题属性阈值,将空间邻域扩展为时空邻域定义时空实体的密度,进而将高密度的时空实体进行合并。2006年Birant等[6]在DBSCAN基础上考虑时间和非空间的专题属性提出了ST-DBSCAN时空聚类算法,探测海温的时空分布模式;2010年裴韬等[8]基于密度分解思想发展了一种时空聚类方法 (windowed nearest neighbour, WNN),降低了密度聚类参数设置的困难,但是该算法没有考虑时空实体的非空间专题属性,只适用于时空点事件的聚类分析;2012年邓敏等[4]结合时空统计学和图论方法提出了一种构建时空邻域的方法,进一步采用密度聚类思想进行时空扩展和聚类。2012年Joshi等[15]亦基于密度聚类思想,通过拓扑邻接关系定义时空邻域,进而定义时空核点进行扩展聚类,与其他方法不同的是,该方法主要针对时空面数据进行聚类。基于密度的方法可以发现任意形状的时空簇,但是全局的阈值设置使这类方法难以识别密度分布不均匀的时空簇,且带有较多参数,参数设置也比较困难[16]

      综上所述,目前时空聚类研究虽然取得了一定的进展,但由于现实世界中的时空数据大都包含空间、时间和专题属性信息,需要在时空聚类过程中同时考虑时空邻近与专题属性相似。现有方法大多忽略了数据的聚类趋势性分析,即数据中即使不存在任何聚集结构,亦可以产生聚类的结果,聚类结果的可靠性和显著性缺乏评价。同时,现有顾及时空和专题属性的时空聚类方法都需要人为设定阈值,且阈值设置都缺乏严密的理论依据,导致聚类结果主观性强。为此,本文提出一种基于重排检验的时空聚类方法。

    • 时空邻近关系的定义和构建是识别均质子区域的基础,本文借助图论工具构建时空邻近关系。首先根据文献[17]提出的约束Delaunay三角网方法构建实体的空间邻近域,如图 1(a)所示 (蓝色圆圈表示A的空间邻近实体);在空间邻近约束的基础上,进一步考虑时间上相邻的时空实体之间的相互影响,以时间邻近为约束将空间邻域扩展为时空邻域。一个时空实体的时空邻域包含相邻时间点上所有空间邻近的实体,图 1(b)显示了时空实体A的时空邻近实体 (包含A本身),记为STN (A)。本文将每个时空实体与其时空邻近实体构成的子集视为一个候选时空均质子区域。

      图  1  实体A的时空邻域

      Figure 1.  Spatio-temporal Neighborhood of an Entity A

      在此基础上,针对任一个时空实体A,以专题属性方差为指标度量其所在候选时空均质子区域内实体专题属性的均质性,以下称为时空实体的局部方差,记为H (A),具体表达为:

      (1)

      式中,P表示STN(A)内实体;Z (P) 表示时空实体P的专题属性;mA表示STN (A) 内实体专题属性的平均值。局部方差越小,表示时空实体与其时空邻近实体的专题属性越相似。

      进一步,在随机化假设[18]下 (即时空对象的专题属性不依赖于其邻近对象的专题属性,是时空上完全随机分布的),采用随机重排检验确定时空实体局部方差的显著性p-value,在给定的显著性水平α下,若实体A的局部方差是显著的,则称STN (A) 为均质子区域,A称为该均质子区域的核。

      针对时空数据集STD={P1, P2, …, Pn},识别均质子区域的具体步骤如下。

      1) 依据时空邻域,按照式 (1) 计算每个时空实体的局部方差,记为{H (P1), H (P2), …, H (Pn)};

      2) 保持时空实体的空间位置和时间属性不变,对所有时空实体的专题属性值进行一次随机重排,计算重排后每个时空实体的局部方差,记为{H (P1k), H (P2k), …, H (Pnk)},其中H (Pik) 表示第k次随机重排后时空实体Pi的局部方差;

      3) 重复步骤2) m次,得到每个时空实体局部方差的经验概率密度分布,根据式 (2) 计算时空实体局部方差H (Pi)的显著性p-value (即在随机化假设下可能发生的概率):

      (2)

      4) 显著性水平α下,若p-value (H (Pi))≤α,则称STN (Pi) 为均质子区域,时空实体Pi为该均质子区域的核。

      图 2所示,以一个简单的数据集SD为例说明计算实体局部方差显著性p-value的过程,时空实体局部方差的显著性检验过程与此类似。图 2中每个单元格代表一个实体,数字表示其专题属性值。以A表示实线方框内中心实体 (与其邻近实体专题属性相似),B表示虚线方框内中心实体 (与其邻近实体专题属性不相似)。如图 2(a)所示,局部方差分别为H (A)=0.25,H (B)=45.53;对所有实体的专题属性进行一次随机重排,如图 2(b)所示,计算重排后AB的局部方差H (A1)=50.5,H (B1)=39.19;图 2(c)~2(d)表示经过99次随机重排后AB局部方差的排序。由此可以计算出实体A和B局部方差的显著性p-value (H (A))=1/100=0.01,p-value (H (B))=80/100=0.8,在显著性水平α=0.05下,STN (A) 为均质子区域,A为该均质子区域的核。

      图  2  基于随机重排计算局部方差的显著性

      Figure 2.  A Sample Dataset and p-value Computation Based on Random Permutation

      值得注意的是,局部方差的显著性检验是一个多重假设检验问题[18],因此需要对局部方差的p-value进行多重假设检验校正,本文采用控制错误发现率 (false discovery rate,FDR) 的方法[19]对局部方差的p-value进行校正,具体步骤为:在显著性水平α下,将p-value (Pk)(k=1, 2, …, n) 按从小到大排序,记为p-value(P(k))(k=1, 2, …, n),从p-value (P(n)) 开始逐步向前检测式 (3),若存在Q (1≤Q≤n) 满足

      (3)

      则p-value(P(k))(k=1, 2, …, Q) 是统计显著的。

      通过以上步骤,可以获得时空数据中的均质子区域。如果未检测到均质子区域,则说明数据中没有聚集结构,聚类过程停止;否则,提取出时空数据中的均匀子区域,进行下一步的凝聚聚类。均质子区域是构成均质时空簇的基本单元,从时空数据库中首先提取出这些子区域,一方面可以作为聚类趋势性探测的指标,另一方面可以将时空数据库中属性值异常的实体或区域去除,进一步的聚类过程只针对均质子区域进行操作,这样可以避免离群值的干扰和减少计算量。

    • 均匀子区域的凝聚聚类,以簇内方差增量最小为原则,不断合并两个空间上相互毗邻和时间上相邻的时空实体或时空簇[20]。聚类中需要解决的一个难题是聚类合并停止条件的判断,针对这个问题,本文基于簇内随机重排检验发展了一种层次聚类截止条件自动判别的方法。该方法的主要思想是:均匀子区域是构成均质簇的基本单元,如果一个簇是均质的,则对簇内实体专题属性随机重排后,簇内均质子区域数目应保持不变,否则均质子区域的数目减少。因此,两个簇合并后,可以对新生成的簇进行簇内专题属性随机重排,通过检验簇内随机重排前后均匀子区域的数目是否发生变化,作为聚类合并的停止条件。此外,簇内随机重排检验可以增强算法的抗噪性:当实体 (或簇) 试图合并一个离群值时,由于合并后方差必然显著增大而无法满足簇内均质性检验的条件,减小了离群值对聚类过程的影响。凝聚聚类的具体步骤如下。

      1) 聚类开始时,将每个时空实体视为一个时空簇,依据时空邻域获得每个时空簇的邻接关系,并计算每个时空簇的簇内方差,如果时空簇只包含一个时空实体,则其簇内方差等于所含时空实体的局部方差。

      2) 将当前簇内方差最小的时空簇作为初始聚类 (如果时空簇只包含一个时空实体且为均质子区域的核,则将该时空实体与其时空邻域内实体合并作为初始聚类),记为S。计算S与其邻接的时空簇间的属性距离,即合并前后簇内实体专题属性方差的增量。设QS周围与S属性距离最小的时空簇,将QS暂时合并生成新的时空簇STC=Q∪S。

      3) 针对新生成的时空簇STC,将STC内包含的均匀子区域的核记为{ST1, ST2, …, STk},对STC内实体的专题属性进行r次随机重排,每次重排后按照§1.1的方法计算STi(i=1, 2, …, k) 的局部方差的显著性,若重排后STi(i=1, 2, …, k) 的局部方差都依然显著,则记Ij=0(j=1, 2, …, r),否则Ij=1;在给定的显著性水平β下,如果STC的显著性p-value (STC) 满足条件

      (4)

      则STC内实体的专题属性是统计上显著相似的,合并QS,计算STC的簇内方差,并更新时空簇间的邻接关系 (根据簇内实体的时空邻接关系获得)。否则,不合并QS,并标记QS为不相邻。

      4) 重复步骤2)~3),直到数据集中没有可以合并的时空簇时,聚类停止。

      在步骤4) 中计算簇内均匀子区域的核的局部方差显著性时,可根据§1.1中时空实体局部方差的经验概率密度分布{H (P1k), H (P2k), …, H (Pnk)} (k=1, 2, …, m),计算簇内随机重排后STi(i=1, 2, …, k) 的局部方差的显著性。

    • 由于随机重排检验的计算复杂度较高,在不影响检验结果精度的前提下,本文提出了一种基于时空拓扑关系的快速随机重排检验方法。该方法的主要思想是, 具有相同拓扑结构 (即时空邻接实体的数目相同) 的时空实体的局部方差在随机化假设下具有相同的概率密度分布。因此,在实体专题属性随机重排后,具有相同拓扑结构的时空实体只需要计算其中任意一个实体的局部方差即可,而不需要针对其中的每个时空实体都计算一次局部方差。由于数据中包含的拓扑结构的种类数不大于 (通常情况下是远小于) 时空实体的个数,因此,根据拓扑结构确定时空实体局部方差的经验概率密度分布,可以大大减少计算量,同时不影响检测结果的精度。如图 2(a)中的示例数据,包含50个实体,以八邻近方式定义实体的邻接关系时,共包含3种拓扑邻接关系,在每次随机重排后只需要计算3个实体的局部方差,这样就减少了47个局部方差的计算量。对于实体集合C={P1, P2, …, Pn},快速重排检验的具体步骤如下.

      1) 统计集合C内每个时空实体的时空邻域内包含的实体的数目,记为N={k1, k2, …, kn}

      2) 根据Nki (i=1, 2, …, n) 相同的实体分为一个组,记为Gj(j=1, 2, …, g),可以发现,分组的数目g (gn) 即为集合C中包含的拓扑结构的种类数,在专题属性完全随机分布的假设下,位于同一个分组内的实体的局部方差具有相同的经验概率密度分布;

      3) 对集合C内的实体进行专题属性随机重排,按照式 (1) 计算每个分组Gj内任意一个实体的局部方差 (与§1.1、§1.2的重排检验方法不同,这里不再是计算集合C内每一个实体的局部方差),得到g个实体的局部方差,记为{H (PG1k), H (PG2k), …, H (PGgk)}(gn),其中H (PGik) 表示第k次随机重排后Gi分组内任意一个实体的局部方差;

      4) 重复步骤3) m次,得到每个时空实体局部方差的经验概率密度分布,计算集合C内每个时空实体的局部方差H (Pi) 的显著性p-value时,位于同一个分组Gi内的时空实体采用同一组局部方差序列{H (PGi1), H (PGi2), …, H (PGim)},根据式 (2) 计算其局部方差的p-value值;

      5) 按照式 (3) 对每个时空实体局部方差的p-value进行校正,判断其是否统计显著。

      进一步,为了验证该方法的有效性,分别采用3组测试数据 (测试数据1如图 2所示,测试数据2模拟了4个时相上12X12大小的栅格数据,测试数据3采用我国陆地554个气象观测站点26年的年平均降水量数据) 进行分析。表 1显示了简单重排检验方法 (Monte Carlo simulation test, MC) 与基于拓扑关系的快速重排检验方法 (fast Monte Carlo simulation test, FMC) 的运行时间比较 (测试平台Windows 8系统,处理器Intel i7双核,内存8 GB)。

      表 1  随机重排检验与快速随机重排检验的运行时间比较/s

      Table 1.  Comparison of Running Times Between General Permutation Test Method and the Proposed Method/s

      数据集实体数拓扑数100次500次1 000次5 000次10 000次
      MCFMCMCFMCMCFMCMCFMCMCFMC
      测试数据15030.1180.0120.5820.045 1.1620/.0915.8790.44911.9610.901
      测试数据257641.4460.0287.0150.08913.4340.16469.2740.762138.6671.544
      测试数据314 4041335.4310.532178.4451.193361.0392.0521 771.4709.1633 559.37918.948
      注:为了减少随机因素影响,运行时间取20次重复试验的平均值。

      可以发现,FMC方法较MC方法,运行时间有了显著提升,且基于拓扑关系的快速重排检验方法的时间复杂度与实体数目n无关。

    • 对于一个时空数据STDB (包含n个空间位置和t个时间段),本文方法主要包括三个步骤.①时空邻近域的构建。由于时空邻近域是在空间邻近域上的简单扩展,其时间复杂度与空间邻近域构建的时间复杂度相当约为O (nlgn),空间复杂度约为O (kN),其中k为时空实体邻域内点个数的平均值,N=n×t。②时空均质子区域的识别。首先需要针对每一个时空实体计算局部方差,其时间复杂度与N近似线性关系,进一步随机重排m次检验的时间复杂度约为O (mu),其中u (u远小于N) 为STDB包含的拓扑种类的数目,故该步骤的时间复杂度约为O (N)+O (mu),空间上需要存储每个时空实体的局部方差和p-value,以及m次随机重排计算的局部方差的经验分布,故该步骤的空间复杂度约为O (mu+2N);③设经过前一步检测出的均质子区域个数为R,最终聚类数目为C,则时空实体凝聚聚类过程的时间复杂度约为O (rg (R+C)(R-C+1) /2),其中r为簇内随机重排的次数,g为簇内拓扑种类数目的平均值,空间复杂度主要有存储N个时空实体类标签的开销以及合并过程中计算簇的显著性的开销,约为O (N+r)。因此,该方法整体时间复杂度约为O (nlgn)+O (mu)+O (N)+O (rg (R+C)(R-C+1) /2),空间复杂度约为O (kN)+O (mu+2N)+O (N+r)。与经典的ST-DBSCAN算法 (时间复杂度约为O (N2+NlgN)) 相比,本文方法需要模拟随机数据集,运行效率较ST-DBSCAN算法低。但是,本文的主要目的是为了解决现有方法具有较多难以设定的聚类参数的问题;并且现有方法通过调试参数进行聚类具有很大的主观性,本文方法虽然计算量大,但是不需要过多的参数设置,大大降低了参数设置的困难,特别是针对实际数据的分析,用户不需要过多的干预,在一定程度上降低了聚类算法实际应用的难度。由于时空数据的数据量大,数据分析时的空间复杂度一般都较高,算法的空间复杂度可以根据数据特点设计特殊类型的时空数据结构或采用一定的空间索引技术 (如四叉树、R树、最小外接矩形等)[6]进一步改善。

    • 气象观测数据是研究地理气候现象和规律的基础数据资料,挖掘降水的时空分布模式是气象数据分析中的一项重要任务,可为揭示气候现象的分布规律和演变机制提供有益参考。由于我国具有复杂的气候条件,降水具有明显的空间趋势和季节性趋势[21],对于降水分布的先验认识亦可为聚类算法的有效性检验提供一定参考。为了验证本文方法的有效性,采用我国陆地554个气象观测站点2009年的月降水量数据进行实验分析,聚类结果如图 3所示。实验分析中随机重排的模拟次数mr取9 999,显著性水平αβ取0.05。

      图  3  月降水数据聚类结果

      Figure 3.  Results of the Proposed Clustering Method on the Monthly Precipitation Data

      对于月降水数据,本文聚类方法发掘了8个时空簇,如图 3C1~C8所示。为了更好地观察这些时空簇的边界,图 3中显示了每个时空簇在空间上的投影 (西藏、新疆的西部区域由于没有气象监测站点,显示为空白)。从空间分布来看,簇C1包含了我国秦岭-淮河以北的大部分干旱和半干旱地区,簇内站点的月降水量主要集中于0~20 mm,这些地区由于远离东南沿海,受季风影响较少,且进一步受南北分段山脉的阻隔,降水常年偏少;从时间分布来看,簇C1对应时间段为1~6月,且空间上有从1月开始逐步向北收缩的趋势,到6月停止,开始进入春夏换季的雨季,降雨开始活跃。与簇C1相对应,簇C4对应了我国北方夏季雨季的结束,逐步进入冬季枯水期的过程,簇C4的时间分布为9~12月,空间上有从9月开始逐步扩大的趋势。同时可以发现,簇C1C4的边界与我国800 mm等降水线相当吻合。簇C2对应了我国热带区域冬季 (1~3月) 的“枯水期”,降水量为30~50 mm,簇C3为7~10月我国局部区域出现的降水比较集中的地区 (时间分别为7~10月,降水量为70~130 mm)。簇C5~C8分别对应了10~12月我国中部和南部局部地区降水聚集的区域,因为受到海洋飓风的影响,在靠近海洋的区域,如簇C6(广东等)、C7(福建) 等地区出现了大范围的降雨,形成一定的时空聚集模式,从图 3中亦可以发现这些时空簇的持续时间相对较短,主要表现为空间上的聚集。进一步可以发现,在6~9月,我国南方区域基本没有降雨的聚集,这主要是因为6~9月为夏季,降水在各地区时有出现且降雨量差异较大,即使相邻监测站点的降水波动也相对较大,因此没有形成时空簇。

      进一步,为了验证本文方法的有效性,与经典基于密度的时空聚类算法ST-DBSCAN进行比较。按照文献[6]推荐的方法进行参数设置,参数中Eps1是空间阈值,Eps2是属性阈值,MinPts是密度阈值。聚类结果如图 4所示。

      图  4  ST-DBSCAN聚类结果 (Eps1=300 km, Eps2=5.7 mm, MinPts=9)

      Figure 4.  Results of ST-DBSCAN Algorithm

      图 4中可以发现,ST-DBSCAN算法识别出了3个簇,其中的一个大簇 (图 4(a)) 包含了C1C4,同时还包含了周围的大量噪声,主要原因在于ST-DBSCAN算法利用参数Eps1(空间阈值) 和Eps2(属性阈值) 只能控制实体邻域内属性的均质性,而未能充分考虑簇内实体属性之间的均质性。从空间分布来看,大簇覆盖了监测站点的所有区域,未能反映我国降水的南北差异和时空分异特征。值得注意的是,ST-DBSCAN算法在6~9月南方地区亦没有识别出任何降水的聚集模式,与本文方法一致,其主要原因如前文所述;同时,两个较小的时空簇可以看成是C3的一部分,对应了一段时间内降水的局部聚集。从实验分析结果可以看出,本文方法相比ST-DBSCAN算法具有以下优势:不需要过多的参数设置,降低了人为影响;可以有效去除噪声,避免噪声干扰;通过簇内属性重排检验,充分考虑了同一个簇内实体属性之间的均质性,挖掘出的时空聚集模式更能反映出降水的时空分异特征。

    • 本文提出了一种基于重排检验的时空聚类方法。首先,基于重排检验发现时空数据集中的均质子区域;进而,采用均方误差准则合并均质子区域内的时空实体生成时空簇,并通过簇内重排检验自动识别聚类合并的终止条件;最后,借助时空拓扑关系发展了一种快速重排检验方法,在保证结果精度的前提下提高了聚类方法的运行效率。通过实验和比较发现, 本文方法一方面可以发现不同形状、大小的时空簇,聚类质量优于经典的ST-DBSCAN方法;另一方面降低了聚类过程中人为设置参数的主观影响,聚类方法的可操作性提高。进一步的研究将主要集中在进一步提高该方法的运行效率方面,使其可以适用于大数据环境下的分析和处理。

参考文献 (21)

目录

    /

    返回文章
    返回