A grid-based clustering algorithm for wild bird distribution

Abstract

Advanced satellite tracking technologies provide biologists with long-term location sequence data to understand movement of wild birds then to find explicit correlation between dynamics of migratory birds and the spread of avian influenza. In this paper, we propose a hierarchical clustering algorithm based on a recursive grid partition and kernel density estimation (KDE) to hierarchically identify wild bird habitats with different densities. We hierarchically cluster the GPS data by taking into account the following observations: 1) the habitat variation on a variety of geospatial scales; 2) the spatial variation of the activity patterns of birds in different stages of the migration cycle. In addition, we measure the site fidelity of wild birds based on clustering. To assess effectiveness, we have evaluated our system using a large-scale GPS dataset collected from 59 birds over three years. As a result, our approach can identify the hierarchical habitats and distribution of wild birds more efficiently than several commonly used algorithms such as DBSCAN and DENCLUE.

Keywords

hierarchical clustering / bird migration / kernel density estimation / grid partition

References

[1] Chen H, Li Y, Li Z, Shi J, Shinya K, Deng G, Qi Q, Tian G, Fan S, Zhao H, Sun Y X, Kawaoka Y. Properties and dissemination of H5N1 viruses isolated during an influenza outbreak in migratory waterfowl in western China. Journal of Virology, 2006, 80(12): 5976-5983

[2] Liu J, Xiao H, Lei F, Zhu Q, Qin K, Zhang X W, Zhang X L, Zhao D, Wang G, Feng Y, Ma J, Liu W, Wang J, Gao G F. Highly pathogenic H5N1 influenza virus infection in migratory birds. Science, 2005, 309(5738): 1206

[3] Wilcove D S. No way home: the decline of the world’s great animal migrations. Island Press, 2007

[4] Chen C, Rinsurongkawong V, Eick C, Twa M. Change analysis in spatial data by combining contouring algorithms with supervised density functions. Advances in Knowledge Discovery and Data Mining, 2009, 907-914

[5] Jenson S, Domingue J. Extracting topographic structure from digital elevation data for geographic information system analysis. Photogrammetric Engineering and Remote Sensing, 1988, 54(11): 1593-1600

[6] Wang W, Yang J, Muntz R. Sting: a statistical information grid approach to spatial data mining. In: Proceedings of the 1997 International Conference on Very Large Data Bases. 1997, 186-195

[7] Hinneburg A, Keim D A. An efficient approach to clustering in large multimedia databases with noise. Bibliothek der Universit�t Konstanz, 1998

[8] Bowlin M S, Bisson I A, Shamoun-Baranes J, Reichard J D, Sapir N, Marra P P, Kunz T H, Wilcove D S, Hedenstr�m A, Guglielmo C G, Akesson S, Ramenofsky M, Wikelski M. Grand challenges in migration biology. Integrative and Comparative Biology, 2010, 50(3): 261-279

[9] Li Z, Ji M, Lee J G, Tang L A, Yu Y, Han J, Kays R. MoveMine: mining moving object databases. In: Proceedings of the 2010 International Conference on Management of Data. 2010, 1203-1206

[10] Li Z, Han J, Ji M, Tang L A, Yu Y, Ding B, Lee J G, Kays R. MoveMine: mining moving object data for discovery of animal movement patterns. ACM Transactions on Intelligent Systems and Technology (TIST), 2011, 2(4): 37

[11] Bar-David S, Bar-David I, Cross P C, Ryan S J, Knechtel C U, Getz W M. Methods for assessing movement path recursion with application to African buffalo in South Africa. Ecology, 2009, 90(9): 2467-2479

[12] Ca�izo Rincon J, Carrillo J, Rosado J. Collective behavior of animals: swarming and complex patterns. Arbor: Ciencia, Pensamiento y Cultura, 2010(746): 1035-1049

[13] Li Z, Ding B, Han J, Kays R. Swarm: mining relaxed temporal moving object clusters. Proceedings of the VLDB Endowment, 2010, 3(1-2): 723-734

[14] Altizer S, Bartel R, Han B A. Animal migration and infectious disease risk. Science, 2011, 331(6015): 296-302

[15] Si Y, Skidmore A, Wang T, Boerd W, Debba P, Toxopeus A, Li L, Prins H. Spatio-temporal dynamics of global H5N1 outbreaks match bird migration patterns. Geospatial Health, 2009, 4(1): 65-78

[16] Takekawa J Y, Newman S H, Xiao X, Prosser D J, Spragens K A, Palm E C, Yan B, Li T, Lei F, Zhao D, Douglas D C, Muzaffar S B, Ji W. Migration of waterfowl in the east Asian flyway and spatial relationship to HPAI H5N1 outbreaks. Avian Diseases, 2010, 54(s1): 466-476

[17] Shimazaki H, Tamura M, Higuchi H. Migration routes and important stopover sites of endangered oriental white storks (ciconia boyciana) as revealed by satellite tracking. Memoirs of the National Institute of Polar Research Special, 2004, (58): 162-178

[18] Ester M, Kriegel H P, Sander J, Xu X. A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. 1996, 226-231

[19] Tang M, Zhou Y, Li J, Wang W, Cui P, Hou Y, Luo Z, Li J, Lei F, Yan B. Exploring the wild birds’ migration data for the disease spread study of H5N1: a clustering and association approach. Knowledge and Information Systems, 2011, 27(2): 227-251

[20] Ankerst M, Breunig M M, Kriegel H P, Sander J. Optics: ordering points to identify the clustering structure. ACM SIGMOD Record, 1999, 28(2): 49-60

[21] Worton B J. Kernel methods for estimating the utilization distribution in home-range studies. Ecology, 1989, 70(1): 164-168

[22] Prosser D J, Cui P, Takekawa J Y, Tang M, Hou Y, Collins B M, Yan B, Hill N J, Li T, Li Y, Lei F, Guo S, Xing Z, He Y, Zhou Y, Douglas D C, Perry W M, Newman S H. Wild bird migration across the Qinghai-Tibetan Plateau: a transmission route for highly pathogenic H5N1. PloS One, 2011, 6(3): e17622

[23] Cui P, Hou Y, Tang M, Zhang H, Zhou Y, Yin Z, Li T, Guo S, Xing Z, He Y, Prosser D J, Newman S H, Takekawa J Y, Yan B, Lei F. Movement patterns of bar-headed geese anser indicus during breeding and post-breeding periods at Qinghai Lake, China. Journal of Ornithology, 2011, 152(1): 83-92

[24] Maciejewski R, Rudolph S, Hafen R, Abusalah A, Yakout M, Ouzzani M, Cleveland W S, Grannis S J, Ebert D S. A visual analytics approach to understanding spatiotemporal hotspots. IEEE Transactions on Visualization and Computer Graphics, 2010, 16(2): 205-220

[25] Xie C, Song Y, Liu Z. Density-based clustering algorithm using kernel density estimation and hill-down strategy. Journal of Information and Computational Science, 2010, 7(1): 135-142

[26] Kulczycki P, Charytanowicz M, Kowalski P A, Lukasik S. The complete gradient clustering algorithm: properties in practical applications. Journal of Applied Statistics, 2012, 39(6): 1211-1224

[27] Cui P, Hou Y, Xing Z, He Y, Li T, Guo S, Luo Z, Yan B, Yin Z, Lei F. Bird migration and risk for H5N1 transmission into Qinghai Lake, China. Vector-Borne and Zoonotic Diseases, 2011, 11(5): 567-576

[28] Prosser D J, Takekawa J Y, Newman S H, Yan B, Douglas D C, Hou Y, Xing Z, Zhang D, Li T, Li Y, Zhao D, Perry W M, Palm E C. Satellitemarked waterfowl reveal migratory connection between H5N1 outbreak areas in China and Mongolia. Ibis, 2009, 151(3): 568-576

[29] Seaman D E, Powell R A. An evaluation of the accuracy of kernel density estimators for home range analysis. Ecology, 1996, 2075-2085

[30] Muzaffar S B, Takekawa J Y, Prosser D J, Douglas D C, Yan B, Xing Z, Hou Y, Palm E C, Newman S H. Seasonal movements and migration of Pallas’s Gulls Larus ichthyaetus from Qinghai Lake, China. Forktail, 2008, 24: 100-107

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg