Optimizing Spatial Trend Detection By Artificial Immune Systems

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.

Authors:

• M. Derakhshanfar
• B. Minaei-Bidgoli

Keywords:

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

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