Theory and Application of Cellular Automata For Pattern Classification

• Autorzy: Maji P. , Shaw C. , Ganguly N. , Sikdar B.K. , Chaudhuri P.P.
• Języki publikacji: EN

Abstrakty

EN

This paper presents the theory and application of a high speed, low cost pattern classifier. The proposed classifier is built around a special class of sparse network referred to as Cellular Automata (CA). A specific class of CA, termed as Multiple Attractor Cellular Automata (MACA), has been evolved through Genetic Algorithm (GA) formulation to perform the task of pattern classification. The versatility of the classification scheme is illustrated through its application in three diverse fields - data mining, image compression, and fault diagnosis. Extensive experimental results demonstrate better performance of the proposed scheme over popular classification algorithms in respect of memory overhead and retrieval time with comparable classification accuracy. Hardware architecture of the proposed classifier has been also reported.

Słowa kluczowe

EN

cellular automata; Multiple Attractor Cellular Automata; MACA; pattern clasification; genetic algorithm; data mining; image compression; fault diagnosis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 3,4
• Strony: 321--354
• Opis fizyczny: Bibliogr. 36 poz., tab.

Twórcy

autor

Maji P.

• Department of Computer Science and Technology, Bengal Engineering College (DU), Howrah, India 711103

autor

Shaw C.

• Department of Computer Science and Technology, Bengal Engineering College (DU), Howrah, India 711103

autor

Ganguly N.

• Technical University of Dresden, High Performance Computing Centre, Zellescher Weg 12, Willers-Bau A 115, D-01069 Dresden

autor

Sikdar B.K.

• Department of Computer Science and Technology, Bengal Engineering College (DU), Howrah, India 711103

autor

Chaudhuri P.P.

• Department of Computer Science and Technology, Bengal Engineering College (DU), Howrah, India 711103

Bibliografia

• [1] Abramovici, M., Breuer, M., Friedman, A.: Digital Systems Testing and Testable Design, IEEE Press, 1990.
• [2] Agrawal, R., Imielinski, Т., Swami, A.: Database Mining: A Performance Perspective. IEEE Transaction on Knowledge and Data Engineering, 5(6), December 1993.
• [3] Agrawal, V. D., Mercer, M. R.: Testability Measures - What Do They Tell Us?, In Proc. International Test Conference, 1982, 391-396.
• [4] Bardel 1, P., McAnney, W., Savir, J.: Built In Test for VLSI: Pseudorandom Techniques, Wiley Interscience, 1987.
• [5] Boppana, V., Fuchs, W. K.: Fault Dictionary Compaction by Output Sequence Removal, In 1CCAD, November 1994, 576-579.
• [6] Breiman, L., Friedman, J. H., Olshen, R. A., Stone, C. J.: Classification and Regression Trees, Wadsworth, Belmont, 1984.
• [7] Chattopadhyay, S., Adhikari, S., Sengupta, S., Pal, M.: Highly Regular, Modular, and Cascadable Design of Cellular Automata-Based Pattern Classifier, IEEE Transaction on VLSI Systems, 8(6), December 2000, 724-735.
• [8] Chaudhuri, P. P., Chowdhury. D. R., Nandi, S., Chatterjee, S.: Additive Cellular Automata, Theory and Applications, VOL. 1, IEEE Computer Society Press, Los AIamitos, California. ISBN-0-8186-7717-1, 1997.
• [9] Cheeseman. P., Stutz, J.: Bayesian Classification (AutoClass): Theory and Results, In U. M. Fayyad, G. Piatetsky-Shapiro, P. Smith and R. Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, 1996, 153-180.
• [10] Gallant, S. I.: Neural Networks Learning and Expert Systems, Cambridge, Mass; MIT Press, 1993.
• [11] Ganguly, N.: Cellular Automata Evolution: Theory and Applications in Pattern Recognition and Classification, Ph.D Thesis, CST Dept, BECDU, India, 2003.
• [12] Ganguly, N., Maji, P., Dhar, S., Sikdar, B. K., Chaudhuri. P. P.: Evolving Cellular Automata as Pattern Classifier. Proceedings of Fifth International Conference on Cellular Automata for Research and Industry, ACRI2002. Switzerland, October 2002, 56-68.
• [13] Gantamatcher, F. R.: The Theory of Matrices, Chelsa Publishing Co., New York, 1 & II, 1959.
• [14] Goldberg, D. E.: Genetic Algorithms in Search, Optimizations and Machine Learning, Morgan Kaufmann, 1989.
• [15] Gresho, A., Gray, R. M.: Vector Quantization and Signal Compression, Kluwer Academy Publishers, 1992.
• [16] Han, J., Kamber. M.: Data Mining, Concepts and Techniques, Morgan Kaufmann Publishers, ISBN :1-55860-489-8, 2001.
• [17] Hertz, J., Krogh, A., Palmer, R. G.: Introduction to the Theory of Neural Computation, Santa Fe Institute Studies in the Sciences of Complexity, Addison Wesley, 1991.
• [18] Holland, J. H.: Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor, MI, 1975.
• [19] Lee, H. K.: Hope: An Efficient Parallel Fault Simulator for Synchronous Sequential Circuits, In Proceedings of 29th Design Automation Conference, 1992, 336-340.
• [20] Lippmann. R.: An Introduction to Computing with Neural Nets, IEEE ASSP Magazine, 4(22), April 1987.
• [21] Matheus. C. J., Chan, P., Piatetsky-Shapiro, G.: Systems for Knowledge Discovery in Databases, IEEE Transaction on Knowledge and Data Engineering, 5. 1993, 903-913.
• [22] Mehta, M., Agrawal, R., Rissanen, J.: SLIQ: A Fast Scalable Classifier for Data Mining, Proceedings of International Conference on Extending Database Technology, Avignon, France, 1996.
• [23] Neumann, J. V.: The Theory of Self-Reproducing Automata, A. W. Burks, Ed. University of Illinois Press, Urbana and London, 1966.
• [24] Pal, K.: Theory and Application of Multiple Attractor Cellular Automata for Fault Diagnosis, Proceedings of Asian Test Symposium, December 1998.
• [25] Piatetsky-Shapiro, G., Fayyad, U., Smith, P.: From Data Mining to Knowledge Discovery: An Overview, In U. M. Fayyad, G. Piatetsky-Shapiro, P. Smith and R. Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, 1996, 1-35.
• [26] Piatetsky-Shapiro, G., Frawley, W. J.: Knowledge Discovery in Databases, AAAI/MIT Press, 1991.
• [27] Pomeranz, I., Reddy, S. M.: On The Generation of Small Dictionaries for Fault Location, In ICCAD, November 1992,272-279.
• [28] Quinlan, J. R.: C4.5: Programs for Machine Learning, Morgan Kaufmann, CA, 1993.
• [29] Roy, B. N., Chaudhuri, P. P., Nandi, P. K.: Efficient Synthesis of OTA Network for Linear Analog Functions, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 21(5), May 2002, 517-533.
• [30] Ryan, P G., Fuchs, W. K., Pomeranz. I.: Fault Dictionary Compression and Equivalence Class Computation for Sequential Circuits, In ICCAD, November 1993, 508-511.
• [31] Santa-Cruz., Ebrahimi, Т., Askelf, J., Larsson, M., Christopoulos, C.: JPEG 2000 still image coding versus other standards, Proceedings of the SPIE’s 46th annual meeting, Applications of Digital Image Processing XXIV, San Diego, California, 4472, July 2001. 267-275.
• [32] Shafer, J., Agrawal, R., Mehta, M.: SPRINT: A Scalable Parallel Classifier for Data Mining, In 22nd VLDB Conference, 1996.
• [33] Shaw, C., Chatterjee, D., Maji, P., Sen, S., Chaudhuri, P. P.: A Pipeline Architecture For Encompression (Encryption + Compression) Technology, Proceedings of 16th International Conference on VLSI Design, India, January 2003.
• [34] Sikdar, B. K., Ganguly, N., A. Karmakar, S. Chowdhury, Chaudhuri, P. P.: Multiple Attractor Cellular Automata for Hierarchical Diagnosis of VLSI Circuits, Proceedings of 10//? Asian Test Symposium, Japan, 2001.
• [35] Sikdar, B. K., Ganguly, N., Majumder, P., Chaudhuri, P. P.: Design of Multiple Attractor GF(2P) Cellular Automata for Diagnosis of VLSI Circuits, Proceedings of 14th International Conference on VLSI Design, India, January 2001,454-459.
• [36] Wolfram, S.: Theory and Application of Cellular Automata, World Scientific, 1986.