سابِق|تال

Spatial clustering method considering spatial distribution feature in the attribute domain

  • role： First author第一作者
  • Email：Chu_Je@163.com
  • Introduction：朱杰(1989—　)，男，博士研究生，研究方向为空间数据表达与挖掘。E-mail：Chu_Je@163.com
Jie ZHU,  
  • role： Corresponding author通信作者
  • Email：sunyizhong_cz@163.com
  • Introduction：孙毅中(1957—　)，男，教授，研究方向为城市空间数据挖掘。E-mail：sunyizhong_cz@163.com
Yizhong SUN*,  
  • No information about the author is available
Jilong LI

ملخص

Spatial clustering is important for spatial data mining and spatial analysis. Spatial objects in the same cluster should be similar in the spatial and attribute domains. Tendency and heterogeneity are important characteristics of geographic phenomena. Currently, most spatial clustering algorithms only consider either tendency or heterogeneity, failing to obtain satisfied clustering results. To overcome these limitations, a spatial clustering method based on graph theory and information entropy is developed in this work. The proposed algorithm involves two main steps: construct spatial proximity relationships and cluster spatial objects with similar attributes. Delaunay triangulation with edge length constraints is first employed to construct spatial proximity relationships among objects. To obtain satisfactory results in spatial clustering with attribute similarity, the information entropy is introduced to overcome the defects of similarity measure with binary relation, which can reflect the clustering tendency of geographical phenomena. Furthermore, a local parameter measurement method based on the principle of “equal probability maximum entropy” is designed to adapt to the local change information of attribute distribution. The performance of the proposed algorithm was evaluated experimentally by comparing the leading state-of-the-art alternatives: DDBSC and multi-constraint algorithms. Results showed that our method outperformed the two other algorithms as attributes are unevenly distributed in space. The sensitivity analysis of these algorithms showed that our method was the least sensitive to outliers. The effectiveness and practicability of the proposed algorithm were validated using simulated and real spatial datasets. Two experiments were performed to illustrate the three advantages of our algorithm: (1) It can reflect the tendency of the entity attribute in the spatial distribution. (2) It can meet the requirement that attributes are unevenly distributed in space. (3) It can discover clusters with arbitrary shape and is robust to outliers.

مفهوم

spatial clustering;Delaunay triangulation;information entropy;tendency;heterogeneity

References

  1. 1.
    Ahuja N. 1982. Dot pattern processing using Voronoineighborhoods. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-4(3): 336–343
  2. 2.
    Ai T H and van Oosterom P. 2002. GAP-Tree extensions based on skeletons//Richardson DE and van Oosterom P, eds.Advances in Spatial Data Handling. Berlin Heidelberg: Springer: 501–513 [DOI: 10.1007/978-3-642-56094-1_37]
  3. 3.
    Bai X, Zhao Y B and Luo S W. 2012. Normalized joint mutual information measure for ground truth based segmentation evaluation. IEICE Transactions on Information and Systems, E95.D(10): 2581–2584
  4. 4.
    Birant D and Kut A. 2007. ST-DBSCAN: an algorithm for clustering spatial-temporal data. Data and Knowledge Engineering, 60(1): 208–221
  5. 5.
    Deng M, Liu Q L, Li G Q and Cheng T. 2010. Field-theory based spatial clustering method. Journal of Remote Sensing, 14(4): 694–709 (
  6. 6.
    Deng M, Liu Q L, Li G Q and Huang J B. 2011.Spatial Clustering Analysis and Its Application. Beijing: Science Press: 2–5
  7. 7.
    Eldershaw C and Hegland M. 1997. Cluster analysis using triangulation//NoyeB J, TeubnerM D and GillA W, eds.Computational Techniques and Applications: CTAC97. Singapore: World Scientific: 201–208
  8. 8.
    Ester M, Kriegel H P, Sander J and Xu X W. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96). Menlo Park, CA: AAAI: 226–231
  9. 9.
    Estivill-Castro V and Lee I. 2002. Argument free clustering for large spatial point-data sets via boundary extraction from Delaunay Diagram. Computers, Environment and Urban Systems, 26(4): 315–334
  10. 10.
    Guo X C, Xi X T, Fan X L and Han X. 2015. Fuzzy C-Means clustering algorithm based on semi-supervised learning. Journal of Jilin University (Science Edition), 53(4): 705–709 (
  11. 11.
    He H, Hu D and Yu X C. 2016. Land cover classification based on adaptive interval type-2 fuzzy clustering. Chinese Journal of Geophysics, 59(6): 1983–1993 (
  12. 12.
    Hong S Y and O’Sullivan D. 2012. Detecting ethnic residential clusters using an optimisation clustering method. International Journal of Geographical Information Science, 26(8): 1457–1477
  13. 13.
    Jiao L M, Hong X F and Liu Y L. 2011. Self-organizing spatial clustering under spatial and attribute constraints. Geomatics and Information Science of Wuhan University, 36(7): 862–866 (
  14. 14.
    Jiao L M, Zhang X and Mao L F. 2015. Self-organizing dual spatial clustering algorithm and its application in the analysis of urban sprawl structure. Journal of Geo-Information Science, 17(6): 638–643 (
  15. 15.
    Kang I S, Kim T W and Li K J. 1997. A spatial data miningmethod by Delaunay triangulation//Proceedingsof the 5th ACM International Workshop on ADVANCES in Geographic Information Systems. Las Vegas, Nevada, USA: ACM: 35–39 [DOI: 10.1145/267825.267836]
  16. 16.
    Li G Q, Deng M, Cheng T and Zhu J J. 2008. A dual distance based spatial clustering method. ActaGeodaetica et CartographicaSinica, 37(4): 482–488 (
  17. 17.
    Li H F, Zhang K S and Jiang T. 2004. Minimum entropy clustering and applications to gene expression analysis//Proceedings of the 2004 IEEE Computational Systems Bioinformatics Conference. Stanford, CA, USA: IEEE: 142–151 [DOI:10.1109/CSB.2004.1332427]
  18. 18.
    Li K and Cao Z. 2016. A fuzzy clustering algorithm with generalized entropy based on neural network. Acta Electronica Sinica, 44(8): 1881–1886 (
  19. 19.
    Lin C R, Liu K H and Chen M S. 2005. Dual clustering: integrating data clustering over optimization and constraint domains. IEEE Transactions on Knowledge and Data Engineering, 17(5): 628–637
  20. 20.
    Liu D and Sourina O. 2004. Free-parameters clustering of spatial data with non-uniform density//Proceedings of the2004 IEEE Conference on Cybernetics and Intelligent Systems. Singapore, Singapore:IEEE, 1: 387–392
  21. 21.
    Liu Q L, Deng M, Shi Y and Peng D L. 2011. A novel spatial clustering method based on multi-constraints. ActaGeodaetica et CartographicaSinica, 40(4): 509–516 (
  22. 22.
    Liu Q L, Deng M, Shi Y and Wang J Q. 2012. A density-based spatial clustering algorithm considering both spatial proximity and attribute similarity. Computers and Geosciences, 46: 296–309
  23. 23.
    MacQueen J. 1967. Some methods for classification and analysis of multivariate observations//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, Calif: University of California Press, 1: 281–297
  24. 24.
    Mundur P, Rao Y and Yesha Y. 2006. Keyframe-based video summarization using Delaunay clustering. International Journal on Digital Libraries, 6(2): 219–232
  25. 25.
    Pakhira M K, Bandyopadlhyay S and Maulik U. 2004. Validity index for crisp and fuzzy clusters. Pattern Recognition, 37(3): 487–501
  26. 26.
    Sander J, Ester M, Kriegel H P and Xu X W. 1998. Density-based clustering in spatial databases: the algorithm gdbscan and its applications. Data Mining and Knowledge Discovery, 2(2): 169–194
  27. 27.
    Shannon C E. 1948. A mathematical theory of communication. The Bell System Technical Journal, 27(3): 379–423
  28. 28.
    Shi Y, Liu Q L, Deng M and Lin X M. 2012. A hybrid spatial clustering method based on graph theory and spatial density. Geomatics and Information Science of Wuhan University, 37(11): 1276–1280 (
  29. 29.
    Shi Y, Deng M, Liu Q L and Tang J B. 2013. A multi-scale regionalization method for sea surface temperature based on a scale-space clustering. Geomatics and Information Science of Wuhan University, 38(12): 1484–1489 (
  30. 30.
    Slonim N, Atwal G S, Tkačik G and Bialek W. 2005. Information-based clustering. Proceedings of the National Academy of Sciences of the United States of America, 102(51): 18297–18302
  31. 31.
    Wu F, Qian H Z, Deng H Y and Wang H L. 2008.Intelligent Processing of Spatial Information for Map Generalization. Beijing: Science Press: 3–6
  32. 32.
    Yan W M and Wu W M. 2007.Data Structure (C Language Edition). Beijing: Tsinghua University Press
  33. 33.
    Zhang J G and Singh V P. 2012. Information Entropy: Theory and Application. Beijing: China Water Power Press
  34. 34.
    Zhang T, Ramakrishnan R and Livny M. 1996. BIRCH: an efficient data clustering method for very large databases. ACM SIGMOD Record, 25(2): 103–114
  35. 35.
    Zhong C M, Miao D Q and Wang R Z. 2010. A graph-theoretical clustering method based on two rounds of minimum spanning trees. Pattern Recognition, 43(3): 752–766
  36. 36.
    Zhou Y L. 2011. Grid-Based and Information Entropy-Based Clustering Algorithm.Changsha: Hunan University

قراءة النص الكامل

The above content is generated by Large Model Translation. The translated content is for reference only. We do not assume any commercial or legal responsibilty for any consequences arising from the use of our website