Research on Irregularly Shaped Spatio-Temporal Abnormal Cluster Pattern Mining for Spatial Point Data Sets

Spatio-temporal abnormal cluster pattern is an important spatial point pattern. The pattern results can reflect the distribution and evolution of spatio-temporal events timely and accurately. Early researches has verified the scan statistic based clustering methods are very effective in detection spatial and spatio-temporal abnormal cluster pattern. However, due to the fixed shape of scan window, traditional scan statistic based clustering methods have limitation on obtaining exact shape and size of cluster. This paper proposed an improved irregularly shaped spatio-temporal abnormal cluster pattern mining algorithm stAntScan. The algorithm constructs the spatio-temporal neighborhood matrix by a newly defined 26 directions spatio-temporal neighbor cells. Then the algorithm improves the ant colony optimization based method to fit for spatio-temporal scanning on three-dimensional large data set. In the end, the Monte Carlo simulation method is used to test the significance of clusters. Experimental results on both simulated data and real Weibo check-in data have testified the efficiency and accuracy of stAntScan on irregularly shaped spatio-temporal abnormal cluster pattern mining. And compared with the classical SaTScan, it gets much better results in finding exact shape and size of clusters.