Optimizing Spatial Trend Detection By Artificial Immune Systems

Authors: M. Derakhshanfar, B. Minaei-Bidgoli

Abstract:

Spatial trends are one of the valuable patterns in geo databases. They play an important role in data analysis and knowledge discovery from spatial data. A spatial trend is a regular change of one or more non spatial attributes when spatially moving away from a start object. Spatial trend detection is a graph search problem therefore heuristic methods can be good solution. Artificial immune system (AIS) is a special method for searching and optimizing. AIS is a novel evolutionary paradigm inspired by the biological immune system. The models based on immune system principles, such as the clonal selection theory, the immune network model or the negative selection algorithm, have been finding increasing applications in fields of science and engineering. In this paper, we develop a novel immunological algorithm based on clonal selection algorithm (CSA) for spatial trend detection. We are created neighborhood graph and neighborhood path, then select spatial trends that their affinity is high for antibody. In an evolutionary process with artificial immune algorithm, affinity of low trends is increased with mutation until stop condition is satisfied.

Keywords: Spatial Data Mining, Spatial Trend Detection, Heuristic Methods, Artificial Immune System, Clonal Selection Algorithm (CSA)

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1328650

References:

[1] K. Koperski and J. Han, "Discovery of spatial association rules in geographic information databases," in Proc. 4th Int. Symp. on Large Spatial Databases , 1995, pp.47-66.
[2] Y. Huang, S. Shekhar, H. Xiong, "Discovering Spatial Co-location Patterns from Spatial Datasets: A General Approach.", IEEE Transactions on Knowledge and Data Eng. vol.17, no.12 (2004) 1472- 1485
[3] L. Wang, K. Xie, T. Chen, X. Ma, "Efficient Discovery of Multilevel Spatial Association Rules Using Partitions", Information and Software Technology, Vol. 47, no. 13 (2005) 829- 840
[4] K. Koperski, J. Han, N. Stefanovic, "An Efficient Two-step Method for Classification of Spatial Data", Proc. International Symp. On Spatial Data Handling (1998) 320-328
[5] S. Shekhar, P. Schrater, W. R. Vatsavai, W. Wu , S. Chawla, "Spatial Contextual Classification and Prediction Models for Mining Geospatial Data.", IEEE Transactions on Multmedia, vol. 2, no.4 (2002) 174-188
[6] R. Ng, J. Han, "CLARANS: A Method for Clustering Objects for Spatial Data Mining." IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 5 (2005) 1003-1017
[7] M. Ester, A. Frommelt, H.P. Kriegel and J. Sander, "Spatial data mining: database primitives, Algorithms and efficient DBMS support," Data Mining and Knowledge Discovery, vol. 4, no.2/3, pp. 193-217, 2000.
[8] M. Ester, A. Frommelt, H.P. Kriegel and J. Sander, "Algorithms for characterization and trend detection in spatial databases," in Proc. 4th International Conf. on Knowledge Discovery and Data Mining, 1998 pp. 44-50.
[9] M. Ester, H. P. Kriegel, J. Sander, "Spatial Data Mining: A Database Approach." Proc. 5th Int. Symp. On Large Spatial Databases. (1997) 320-328
[10] M. Ester, H. P. Kriegel, J. Sander, X. Xu, "Density-Connected Sets and Their Application for Trend Detection in Spatial Databases." Proc. 3rd Int. Conf. on Knowledge Discovery and Data Mining. (1997) 44-50
[11] A.P. Engelbrecht, "Computational Intelligence: An Introduction Second Edition" Wiley, 2007, pp. 431-435.
[12] C. Guangzhu, L. Zhishu, Y. Daohua, Nimazhaxi and Zhai yusheng , "An Immune Algorithm based on the Complement Activation Pathway", IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.1A, January 2006
[13] L.N. De Castro, F. J. Von Zuben, "Artificial Immune Systems: Part I - Basic Theory and Applications," Technical Report, RT-DCA 01/99, December 1999.
[14] L.N. De Castro, F. J. Von Zuben, "the Clonal Selection Algorithm with Engineering Applications," In Proceedings of GECCO-00 Las Vegas, Nevada, USA, 2000.
[15] N. K. Jwenw, "Towards a Network Theory of the Immune System," Annual Immunology, vol.125c, 1974.
[16] J.Timmis, M.Neal, J.Hunt, "An Artificial Immune System for Data Analysis," Biosystems, vol.55 (1/3), 2000.
[17] L.N. De Castro, F. J. Von Zuben, "AiNet: an Artificial Immune Network for Data Analysis," International Journal of Computation Intelligence and Application (IJCIA), vol.1 (3). 2001.
[18] P.D-haeseleer, S.Forrest, "An Immunological Approach to Change Detection: Algorithm, Analysis and Implication," In Proc. of IEEE Symposium on Research in Security and Privacy, Oakland, CA, 1996.
[19] L.N. De Castro, F. J. Von Zuben, " Artificial Immune Systems: Part II - A Survey of Applications", TechnicalReport, DCA- RT,021/00,February, 2000.
[20] A. Zarnani, M. Rahgozar, "Efficient Discovery of knowledge from larg Geo- Spatial Databases: An Evolutionary Approach" 2006.
[21] M. Dorigo, V. Maniezzo, A. Colorni, "The Ant System: Optimization by a Colony of Cooperating Agents." IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, vol. 26, no.1 (1996) 29-41
[22] M. Dorigo, T. St├╝tzle , "The Ant Colony Optimization Meta-Heuristic: Algorithms, Applications and Advances. " In: Glover F., Kochenberger G.: Handbook of Meta-heuristics. Kluwer Academic Publishers (2002)
[23] A. Zarnani and M. Rahgozar, "Mining spatial trends by a colony of cooperative ant agents," in Proc. SIAM Conf. on Data Mining-06 Workshop on Spatial Data Mining
[Online]. 2006, Available: http://www.siam.org/meetings/sdm06/workproceed/Spatial%20Data% 20Mining/index.html