A Nonparametric Test Method for Identifying Significant Cross-outliers in Spatial Point Dataset

doi:10.11947/j.AGCS.2018.20170321

Abstract

Abstract: In the field of geography,a spatial outlier is an object whose non-spatial attribute value is significantly different from the values of its spatial neighbors. Detection of spatial outliers will be helpful to uncover special geographical phenomenon,so it has become an important branch of spatial data mining.Although existing methods are able to measure spatial outlier factor,the significance of these outliers can not be evaluated in an objective way. Furthermore,the existing methods are mainly designed for single class dataset,without taking into account the interaction between different categories of dataset.In this study,a nonparametric test was developed to identify the significant cross-outliers in spatial point dataset.Firstly,a reasonable and stable spatial neighborhood is constructed for the primary dataset entitys using the constraint Delaunay triangulation.Then,using the number of reference dataset entitys falling in the spatial reference neighbor radius to measure the initial outlier factor.Constructed the support domain by α-Shape method,the null model is constructed based on spatial randomness process,and the significant spatial cross-outliers are identified by statistical test.Finally,the stability of the spatial cross-outlliers are evaluated by the living distance.Experimentson on both simulated and real-world datasets show that the proposed permutation test is effective for determining significant spatial cross-outliers in spatial point datasets.

Key words: spatial data mining, spatial outlier detection, cross-outlier, nonparametric test, significance

CLC Number:

P208

YANG Xuexi, DENG Min, SHI Yan, TANG Jianbo, LIU Qiliang. A Nonparametric Test Method for Identifying Significant Cross-outliers in Spatial Point Dataset[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(9): 1250-1260.

References

[1] 李德仁, 王树良, 李德毅. 空间数据挖掘理论及应用[M]. 2版. 北京:科学出版社, 2013. LI Deren, WANG Shuliang, LI Deyi. Spatial Data Mining Theories and Applications[M]. 2nd ed. Beijing:Science Press, 2013.
[2] 刘大有, 陈慧灵, 齐红, 等. 时空数据挖掘研究进展[J]. 计算机研究与发展, 2013, 50(2):225-239. LIU Dayou, CHEN Huiling, QI Hong, et al. Advance in Spatiaotemporal Data Mining[J]. Journal of Computer Research and Development, 2013, 50(2):225-239.
[3] HAWKINS D. Identification of Outliers[M]. London:Chapman and Hall, 1980.
[4] SHEKHAR S, LU C T, ZHANG Pusheng. A Unified Approach to Detecting Spatial Outliers[J]. GeoInformatica, 2003, 7(2):139-166.
[5] KNORR E M, Ng R T. Algorithms for Mining Distance-Based Outliers in Large Datasets[C]//Proceedings of the 24th International Conference on Very Large Data Bases, New York:VLDB Press, 1998:392-403.
[6] BREUNIG M M, KRIEGEL H P, Ng R T, et al. LOF:Identifying Density-Based Local Outliers[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. Dallas:ACM, 2000:93-104.
[7] 刘启亮, 邓敏, 石岩, 等. 一种基于多约束的空间聚类方法[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.
[8] SHI Yan, DENG Min, YANG Xuexi, et al. Adaptive Detection of Spatial Point Event Outliers Using Multilevel Constrained Delaunay Triangulation[J]. Computers, Environment and Urban Systems, 2016, 59:164-183.
[9] 杨学习, 石岩, 邓敏, 等. 一种基于多层次专题属性约束的空间异常探测方法[J]. 武汉大学学报(信息科学版), 2016, 41(6):810-817. YANG Xuexi, SHI Yan, DENG Min, et al. A New Method of Spatial Outlier Detection by Considering Multi-level Thematic Attribute Constraints[J]. Geomatics and Information Science of Wuhan University, 2016, 41(6):810-817.
[10] LU C T, DOS SANTOS JR R F, LIU Xutong, et al. A Graph-based Approach to Detect Abnormal Spatial Points and Regions[J]. International Journal on Artificial Intelligence Tools, 2011, 20(4):721-751.
[11] CHEN Dechang, LU C T, KOU Yufeng, et al. On Detecting Spatial Outliers[J]. GeoInformatica, 2008, 12(4):455-475.
[12] CHAWLA S, SUN P. SLOM:A New Measure for Local Spatial Outliers[J]. Knowledge and Information Systems, 2006, 9(4):412-429.
[13] DENG Min, LIU Qiliang, LI Guangqiang. Spatial Outlier Detection Method Based on Spatial Clustering[J]. Journal of Remote Sensing, 2010, 14(5):944-958.
[14] 唐建波, 刘启亮, 邓敏, 等. 空间层次聚类显著性判别的重排检验方法[J]. 测绘学报, 2016, 45(2):233-240. DOI:10.11947/j.AGCS.2016.20140605. TANG Jianbo, LIU Qiliang, DENG Min, et al. A Permutation Test for Identifying Significant Clusters in Spatial Dataset[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(2):233-240. DOI:10.11947/j.AGCS.2016.20140605.
[15] HE Zengyou, DENG Shengchun, XU Xiaofei. Outlier Detection Integrating Semantic Knowledge[M]//MENG Xiaofeng, SU Jianwen, WANG Yujun. Advances in Web-age Information Management. Berlin, Heidelberg:Springer, 2002:126-131.
[16] PAPADIMITRIOU S, FALOUTSOS C. Cross-Outlier Detection[M]//MENG Xiaofeng, SU Jianwen, WANG Yujun. Advances in Spatial and Temporal Databases. Berlin, Heidelberg:Springer, 2003:199-213.
[17] HE Zengyou, XU Xiaofei, HUANG J Z, et al. Mining Class Outliers:Concepts, Algorithms and Applications in CRM[J]. Expert Systems with Applications, 2004, 27(4):681-697.
[18] HEWAHI N M, SAAD M K. Class Outliers Mining:Distance-Based Approach[J]. International Journal of Computer and Information Engineering, 2007, 1(9):2805-2818.
[19] LIU Xutong, CHEN Feng, LU C T. On Detecting Spatial Categorical Outliers[J]. GeoInformatica, 2014, 18(3):501-536.
[20] LU Y C, CHEN Feng, WANG Yating, et al. Discovering Anomalies on Mixed-type Data Using a Generalized Student-t Based Approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(10):2582-2595.
[21] JANEJA V P, PALANISAMY R. Multi-domain Anomaly Detection in Spatial Datasets[J]. Knowledge and Information Systems, 2013, 36(3):749-788.
[22] ZHENG Yu, ZHANG Huichu, YU Yong. Detecting Collective Anomalies from Multiple Spatio-temporal Datasets Across Different Domains[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle:ACM, 2015:2.
[23] 蔡建南, 刘启亮, 徐枫, 等. 多层次空间同位模式自适应挖掘方法[J]. 测绘学报, 2016, 45(4):475-485. DOI:10.11947/j.AGCS.2016.20150337. CAI Jiannan, LIU Qiliang, XU Feng, et al. An Adaptive Method for Mining Hierarchical Spatial Co-location Patterns[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4):475-485. DOI:10.11947/j.AGCS.2016.20150337.
[24] PEI Tao, WANG Weiyi, ZHANG Hengcai, et al. Density-based Clustering for Data Containing Two Types of Points[J]. International Journal of Geographical Information Science, 2015, 29(2):175-193.
[25] KOLINGEROVÁ I, ŽALIK B. Reconstructing Domain Boundaries within a Given Set of Points, Using Delaunay Triangulation[J]. Computers & Geosciences, 2006, 32(9):1310-1319.
[26] HUBERT M, VANDERVIEREN E. An Adjusted Boxplot for Skewed Distributions[J]. Computational Statistics & Data Analysis, 2008, 52(12):5186-5201.
[27] EDELSBRUNNER H, KIRKPATRICK D, SEIDEL R. On the Shape of a Set of Points in the Plane[J]. IEEE Transactions on Information Theory, 1983, 29(4):551-559.
[28] 王远飞, 何洪林. 空间数据分析方法[M]. 北京:科学出版社, 2007:60. WANG Yuanfei, HE Honglin. Spatial Data Analysis Method[M]. Beijing:Science Press, 2007:60.
[29] LEUNG Y, ZHANG Jiangshe, XU Zongben. Clustering by Scale-space Filtering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(12):1396-1410.
[30] 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.
[31] DENG Min, HE Zhanjun, LIU Qiliang, et al. Multi-scale Approach to Mining Significant Spatial Co-location Patterns[J]. Transactions in GIS, 2017, 21(5):1023-1039.
[32] RIPLEY B D. The Second-Order Analysis of Stationary Point Processes[J]. Journal of Applied Probability, 1976, 13(2):255-266.
[33] 毛媛媛, 丁家骏. 抢劫与抢夺犯罪行为时空分布特征研究——以上海市浦东新区为例[J]. 人文地理, 2014, 29(1):49-54. MAO Yuanyuan, DING Jiajun. Study on Spatial-temporal Patterns of Robbery and Snatch:A Case Study of Pudong New Area, Shanghai[J]. Human Geography, 2014, 29(1):49-54.