A Permutation Test for Identifying Significant Clusters in Spatial Dataset

doi:10.11947/j.AGCS.2016.20140605

Abstract

Abstract: Spatial hierarchical clustering methods considering both spatial proximity and attribute similarity play an important role in exploratory spatial data analysis. Although existing methods are able to detect multi-scale homogeneous spatial contiguous clusters, the significance of these clusters cannot be evaluated in an objective way. In this study, a permutation test was developed to determine the significance of clusters discovered by spatial hierarchical clustering methods. Experiments on both simulated and meteorological datasets show that the proposed permutation test is effective for determining significant clustering structures from spatial datasets.

Key words: spatial hierarchical clustering, significance, spatial pattern, permutation test

CLC Number:

P208

TANG Jianbo, LIU Qiliang, DENG Min, HUANG Jincai, CAI Jiannan. A Permutation Test for Identifying Significant Clusters in Spatial Dataset[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(2): 233-240.

References

[1] 李德仁, 王树良, 李德毅. 空间数据挖掘理论与应用[M]. 北京: 科学出版社, 2006. LI Deren, WANG Shuliang, LI Deyi. Spatial Data Mining Theories and Applications[M]. Beijing: Science Press, 2006.
[2] 艾廷华, 郭仁忠. 基于格式塔识别原则挖掘空间分布模式[J]. 测绘学报, 2007, 36(3): 302-308. AI Tinghua, GUO Renzhong. Polygon Cluster Pattern Mining Based on Gestalt Principles[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 302-308.
[3] 汪闽, 周成虎, 裴韬, 等. MSCMO: 基于数学形态学算子的尺度空间聚类方法[J]. 遥感学报, 2004, 8(1): 45-50. WANG Min, ZHOU Chenghu, PEI Tao, et al. MSCMO: A Scale Space Clustering Algorithm Based on Mathematical Morphology Operators[J]. Journal of Remote Sensing, 2004, 8(1): 45-50.
[4] 李光强, 邓敏, 程涛, 等. 一种基于双重距离的空间聚类方法[J]. 测绘学报, 2008, 37(4): 482-488. LI Guangqiang, DENG Min, CHENG Tao, et al. A Dual Distance Based Spatial Clustering Method[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(4): 482-488.
[5] 郭庆胜, 郑春燕, 胡华科. 基于邻近图的点群层次聚类方法的研究[J]. 测绘学报, 2008, 37(2): 256-261. GUO Qingsheng, ZHENG Chunyun, HU Huake. Hierarchical Clustering Method of Group of Points Based on the Neighborhood Graph[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2): 256-261.
[6] 李光强, 邓敏, 刘启亮, 等. 一种适应局部密度变化的空间聚类方法[J]. 测绘学报, 2009, 38(3): 255-263. 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.
[7] PEI Tao, ZHU Axing, ZHOU Chenghu, et al. A New Approach to the Nearest-Neighbour Method to Discover Cluster Features in Overlaid Spatial Point Processes[J]. International Journal of Geographical Information Science, 2006, 20(2): 153-168.
[8] 程博艳, 刘强, 李小文. 一种建筑物群智能聚类法[J]. 测绘学报, 2013, 42(2): 290-294. CHENG Boyan, LIU Qiang, LI Xiaowen. Intelligent Building Grouping Using Selft-organizing Map[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2): 290-294.
[9] 李新运, 郑新奇, 闫弘文. 坐标与属性一体化的空间聚类方法研究[J]. 地理与地理信息科学, 2004, 20(2): 38-40. LI Xinyun, ZHENG Xinqi, YAN Hongwen. On Sptial Clustering Combination of Coordinate and Attribute[J]. Geography and Geo-Information Science, 2004, 20(2): 38-40.
[10] 宋晓眉, 程昌秀, 周成虎, 等. 利用k阶空间邻近图的空间层次聚类方法[J]. 武汉大学学报(信息科学版), 2010, 35(12): 1496-1499. SONG Xiaomei, CHENG Changxiu, ZHOU Chenghu, et al. Spatial Hierarchical Clustering Method Based on k-order Spatial Neighbouring Map[J]. Geomatics and Information Science of Wuhan University, 2010, 35(12): 1496-1499.
[11] 焦利民, 洪晓峰, 刘耀林. 空间和属性双重约束下的自组织空间聚类研究[J]. 武汉大学学报(信息科学版), 2011, 36(7): 862-866. 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.
[12] GUO Diansheng. Greedy Optimization for Contiguity-Constrained Hierarchical Clustering[C]//Proceedings of IEEE International Conference on Data Mining Workshops.Miami, FL: IEEE, 2009: 591-596.
[13] PARK P J, MANJOURIDES J, BONETTIM, et al. A Permutation Test for Determining Significance of Clusters with Applications to Spatial and Gene Expression Data[J]. Computational Statistics and Data Analysis, 2009, 53(12): 4290-4300.
[14] SUZUKI R, SHIMODAIRA H. Pvclust: An R Package for Assessing the Uncertainty in Hierarchical Clustering[J]. Bioinformatics, 2006, 22(12): 1540-1542.
[15] GREENACRE M, PRIMICERIO R. Multivariate Analysis of Ecological Data[M]. Bilbao: Fundación BBVA, 2013.
[16] ANSELIN L. Local Indicators of Spatial Association-LISA[J]. Geographical Analysis, 1995, 27(2): 93-115.
[17] 刘启亮, 邓敏, 石岩, 等. 一种基于多约束的空间聚类方法[J]. 测绘学报, 2011, 40(4): 509-516.LIU Qiliang, DENG Min, SHI Yan, et al. A Novel Spatial Clustering Method Based on Multi-Constraints[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4): 509-516.
[18] 王远飞, 何洪林. 空间数据分析方法[M]. 北京: 科学出版社, 2007.WANG Yuanfei, HE Honglin. Spatial Data Analysis Method[M]. Beijing: Science Press, 2007.
[19] BENJAMINI Y, YEKUTIELI D. The Control of the False Discovery Rate in Multiple Testing under Dependency[J]. The Annals of Statistics, 2001, 29(4): 1165-1188.
[20] BIRANT D, KUT A. ST-DBSCAN: An Algorithm for Clustering Spatial-temporal Data[J]. Data & Knowledge Engineering, 2007, 60(1): 208-221.
[21] COMANICIU D, MEER P. Mean Shift: A Robust Approach Toward Feature Space Analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619.
[22] OJALA M, GARRIGA G C. Permutation Tests for Studying Classifier Performance[J]. The Journal of Machine Learning Research, 2010, 11(1): 1833-1863.
[23] 《中华人民共和国气候图集》编委会. 中华人民共和国气候图集[M]. 北京: 气象出版社, 2002.The Editorial Board of Climatic Atlas of the People's Republic of China. Climatological Atlas of the People's Republic of China[M]. Beijing: China Meteorological Press, 2002.