A quad-tree-based fast and adaptive Kernel Density Estimation algorithm for heat-map generation

ABSTRACT

Kernel Density Estimation (KDE) is a classic algorithm for analyzing the spatial distribution of point data, and widely applied in spatial humanities analysis. A heat-map permits intuitive visualization of spatial point patterns estimated by KDE without any overlapping. To achieve a suitable heat-map, KDE bandwidth parameter selection is critical. However, most generally applicable bandwidth selectors of KDE with relatively high accuracy encounter intensive computation issues that impede or limit the applications of KDE in big data era. To solve the complex computation problems, as well as make the bandwidths adaptively suitable for spatially heterogenous distributions, we propose a new Quad-tree-based Fast and Adaptive KDE (QFA-KDE) algorithm for heat-map generation. QFA-KDE captures the aggregation patterns of input point data through a quad-tree-based spatial segmentation function. Different bandwidths are adaptively calculated for locations in different grids calculated by the segmentation function; and density is estimated using the calculated adaptive bandwidths. In experiments, through comparisons with three mostly used KDE methods, we quantitatively evaluate the performance of the proposed method in terms of correctness, computation efficiency and visual effects. Experimental results demonstrate the power of the proposed method in computation efficiency and heat-map visual effects while guaranteeing a relatively high accuracy.

KEYWORDS:

• Kernel Density Estimation (KDE)
• heat-map
• spatial point pattern
• spatial humanities
• visualization

Acknowledgments

We are grateful to the editor and anonymous reviewers whose comments helped improve this manuscript.

Disclosure statement

No potential conflict of interest was reported by the authors.

Correction Statement

This article has been republished with minor changes. These changes do not impact the academic content of the article.

Notes

1. The experimental data and codes are available at https://github.com/FaLi-KunxiaojiaYuan/Spatial-Statistics.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [No. 41501434, No. 41501443]; The Open Research Fund of Key Laboratory of Space Utilization, Chinese Academy of Sciences [No. LSU-SJLY-2017-02]; National Key Research and Development Program of China [No. 2017YFB0503802].

Notes on contributors

Kunxiaojia Yuan

Kunxiaojia Yuan is PhD candidate in State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing at Wuhan University. Her research interest is spatiotemporal data mining and visualization, spatial statistics, and geographic simulation.

Xiaoqiang Cheng

Xiaoqiang Cheng is lecturer of the Faculty of Resources and Environmental Science, Hubei University. His research interest is geo-visualization, spatial data mining and multi-scale representation.

Zhipeng Gui

Zhipeng Gui is Associate Professor of Geographic Information Science at School of Remote Sensing and Information Engineering, Wuhan University. His research interest is high-performance spatiotemporal data mining and geovisual analytics.

Fa Li

Fa Li is a PhD candidate of the State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing of Wuhan University. His research interest is machine-learning supported big spatiotemporal data mining, parallel computing, as well as their applications in urban planning and environment science.

Huayi Wu

Huayi Wu is full professor, Vice Director of the State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, and PI of the Collaborative Innovation Center of Geospatial Technology, Wuhan University. His research interest is geospatial big data processing, mining and visualization.