Hücresel Otomata Tabanlı İkili Sınıflandırma

Bu çalışmada lineer olmayan hücresel otomatlar ikili örüntü sınıflandırmada kullanılmıştır. Hücresel otomatlar ilk olarak günümüz bilgisayar mimarisinin çalışma prensiplerini belirleyen Von Neumann tarafından biyolojik canlıların kendini yenileme yeteneklerini modellemek için önerilmiştir. Hücresel otomatlar, ızgara düzlemindeki hücrelerin etrafındaki hücrelerle etkileşime bağlı durum güncelleme mantığına dayanan hesaplama modeline sahiptir. Hücresel otomatlar üzerine yapılan çalışmalarda bazı durumların diğer durumlarla dinamik bir etkileşim içerisinde olduğu gözlemlendi. Bu durumlar diğer durumları etrafında toplayan ve çekim merkezi formunda hareket eden davranışlar sergiliyorlardı. Çekim merkezi formunda hareket eden durumlara cezbedici durum(veya cezbedici kap) adı verildi. Cezbedicilerin dinamik davranışları, bir örüntünün diğer örüntüleri çekmesi olarak ele alınması hücresel otomatların örüntü tanıma ve sınıflandırmada kullanma potansiyelini ortaya çıkarmıştır. Hücresel otomata tabanlı ilk örüntü tanıma yöntemleri XOR ve XNOR mantığına göre durum güncellemesi yapan kurallar kullanan lineer yöntemlerdir. Daha sonra lineer yöntemlerin kısıtlarını aşmak için lineer olmayan yöntemler geliştirilmiştir. Bu çalışmada cezbedici durumların nitelenmesi için erişilebilirlik ağacı tabanlı lineer olmayan yöntemler kullanılmıştır. Cezbedici durumlar farklı veri setleri üzerinde ikili sınıflandırma amacı ile kullanılmıştır. Elde edilen sonuçlar daha önce yapılan hücresel otomata tabanlı örüntü tanıma yöntemleri ve diğer yöntemlerle karşılaştırılmıştır.

Cellular Automata Based Binary Classification

In this study, nonlinear cellular automata were used for binary pattern classification. Cellular automata were first proposed by Von Neumann, who determined the working principles of today's computer architecture, to model the self-renewal abilities of biological beings. Cellular automata have a computational model based on the state update logic due to the interaction with the cells around the cells in the grid plane. Studies on cellular automata have shown that some states are in a dynamic interaction with other states. These states gathered other situations around itself and acted in the center of attraction. States that behave in the form of attraction center are called attractor state(or attractor basin). The dynamic behaviours of the attractor were considered as a pattern of attracting other patterns and revealed the potential of using cellular automata in pattern recognition and classification. The first pattern recognition methods based on cellular automata are linear methods that use rules that update the state according to XOR and XNOR logic. Later nonlinear methods have been developed to overcome the limitations of linear methods. In this study, reachability tree based nonlinear methods are used to characterize the attractors. Attractor states are used for binary classification purposes on different data sets. The results obtained were compared with previous cellular automata based pattern recognition methods and other known methods.

Keywords:

cellular automata, multiple attractor cellular automata,

PDF

___

[1] S. Das, Theory and Applications of Nonlinear Cellular Automata In VLSI Design, Ph. D Thesis, Bengal: The Bengal Engineering and Science University, 2006.
[2] J. v. Neumann, The theory of self-reproducing Automata, A. W. Burks, Dü., Urbana and London: Univ. of Illinois Press, 1966.
[3] V. V. Nabiyev, Algoritmalar Teoriden Uygulamalara, Seçkin Yayıncılık, Ankara, Türkiye, 2013.
[4] C. G. Langton, “Self-reproduction in cellular automata”, Physica D: Nonlinear Phenomena, 10(1), 135-144, 1984.
[5] E. F. Codd, Cellular Automata, Academic Press, New York, A.B.D., 1968.
[6] S. Wolfram, A new kind of science, Champaign: IL: Wolfram Media, 2002.
[7] P. Sarkar, “A Brief History of Cellular Automata”, ACM Computing Surveys (CSUR), 1, 80-107 , 2000.
[8] E. F. Moore, “Machine models of self-reproduction”, Proc. Symp. Appl. Math., 14, 17-33, 1962.
[9] M. Gardner, “Mathematical games: The fantastic combinations of John Conway’s new solitaire game life”, Scientific American, 223(4), 120-123., 1970.
[10] M. Gardner, “Cellular automata, self-reproduction, Garden of Eden and Game life”, Scientific American, 224(2), 112, 1971.
[11] S. Wolfram, “Universality and complexity in cellular automata”, Physica D: Nonlinear Phenomena, 10(1), 1-35, 1984.
[12] J. Strotmann, M. Chopra, R. T. Bonnecaze, “A cellular automata simulation of atomic layer etching”, Advanced Etch Technology for Nanopatterning VII, 10589, 105890H, 2018.
[13] E. R. Speer, C. Maes, J. L. Lebowitz, “Probablistic Cellular Automata: Some Statistical Mechanical Considerations”, Pattern Formation In The Physical And Biological Sciences, CRC Press, 175-188, 2018.
[14] K. Clarke, “Cellular Automata and Agent-Based Models”, Handbook of Regional Science, Berlin, Heidelberg, Springer, 2018.
[15] M. J. Phipps, “From local to global: the lesson of cellular automata”, Individual-based models and approaches in ecology, Chapman and Hall/CRC, 165-187, 2018.
[16] X. Liu, L. Ma, X. Li, B. Ai, S. Li, Z. He, “Simulating urban growth by integrating landscape expansion index (LEI) and cellular automata”, International Journal of Geographical Information Science, 28(1), 148-163, 2014.
[17] P. Rosin, A. Adamatzky, Cellular automata in image processing and geometry, X. Sun, Dü., Springer International Publishing, 2014.
[18] P. P. Chaudhuri, D. R. Chowdhury, S. Nandi, S. Chattopadhyay, Additive Cellular Automata: Theory and Applications, Washington: Wiley-IEEE Computer Society, 1997.
[19] S. Das, S. Mukherjee, N. Naskar, B. K. Sikdar, “Characterization of Single Cycle CA and its Application in Pattern Classification”, Electronic Notes in Theoretical Computer Science, 181-203, 2009.
[20] N. Ganguly, P. Maji, B. K. Sikdar, P. P. Chaudhuri, “Generalızed Multıple Attractor Cellular Automata (Gmaca) Model For Assocıatıve Memory”, International Journal of Pattern Recognition and Artificial Intelligence, 16(7), 781-793, 2002.
[21] D. Kagaris, S. Tragoudas, “Von Neumann hybrid cellular automata for generating deterministic test sequences”, ACM Transactions on Design Automation of Electronic Systems, 6(3), 308-321, 2001.
[22] K. Bhattacharje, N. Naska, S. Roy, S. Das, “A Survey of Cellular Automata: Types, Dynamics, Non-uniformity and Applications”, ACM Computing Surveys, 2016.
[23] T. Toffoli, N. Margolus, Cellular Automata Machines: A New Environment for Modeling, Cambridge, MA,: MIT Press, 1987.
[24] P. C. Fischer, “Generation of primes by a one-dimensional real-time iterative array”, Journal ACM, 12, 388-394, 1965.
[25] S. Das, H. Rahaman, B. K. Sikdar., “Cost Optimal Design of Nonlinear CA Based PRPG for Test Applications”, Proc. of Asian Test Symposium, 2005.
[26] S. Das, B. Sikdar, “A Scalable Test Structure for Multicore Chip”, IEEE Trans. on CAD of Integrated Circuits and Systems, 29(1), 127- 137, 2010.
[27] D. Çalıkoğlu, On the computational properties of a class of cellular automata, The University of Iowa, 1973.
[28] R. Sommerhalder, S. Westrhenen, “Parallel language recognition in constant time by cellular automata”, Acta Inf., 19, 397-407, 1983.
[29] E. S. Deutsch, “Thinning algorithms on rectangular, hexagonal, and triangular arrays”, Communications of the ACM, 15, 9, 827-837, 1970.
[30] E. E. Triendl, “Skeletonization of noisy handdrawn symbols using parallel operations”, Pattern Recognition, 2(3), 215-226, 1970.
[31] M. Duff, D. Watson, T. Fountain, G. Shaw, “A cellular logic array for image processing”, Pattern Recognition, 5(3), 241-247, 1973.
[32] A. R. Smith, “Two-dimensional formal languages and pattern recognition by cellular automata”, Switching and Automata Theory, East Lansing, 1971.
[33] P. Rosin, “Training cellular automata for image processing”, IEEE transactions on image processing, 15(7), 2076-2087, 2006.
[34] P. Rosin, “Image processing using 3-state cellular automata”, Computer Vision And Image Understanding, 114(7), 790-802, 2010.
[35] V. Vezhnevets, V. Konouchine, ““GrowCut” - Interactive MultiLabel N-D Image Segmentation By Cellular Automata”, proc. of Graphicon, 1, 150-156, 2005.
[36] P. Ghosh, S. K. Antani, L. R. Long, G. R. Thoma, “Unsupervised Grow-Cut: Cellular Automata-based Medical Image Segmentation”, Healthcare Informatics, Imaging and Systems Biology (HISB), 2011 First IEEE International Conference on, San Jose, 2011.
[37] B. Karasulu, “Görüntülerde İnsan Kulağı Tespit Ve Bölütlemesini Temel Alan Biyometrik Yetkilendirme Üzerine Bir İnceleme”, Bilişim Teknolojileri Dergisi, 9(2), 97, 2016.
[38] H. Göker, H. Tekedere, “FATİH Projesine Yönelik Görüşlerin Metin Madenciliği Yöntemleri İle Otomatik Değerlendirilmesi”, Bilişim Teknolojileri Dergisi, 10(3), 291-299, 2017.
[39] A. Karacı, M. Erdemir, “Arduino ve Wifi Temelli Çok Sensörlü Robot Tasarımı Ve Denetimi”, Bilişim Teknolojileri Dergisi, 10(4), 435-449, 2017.
[40] S. Mukherjee, Theory and Applications of Nonlinear Cellular Automata In Pattern Recognition, Shibpur: Bengal Engineering And Science University, 2009.
[41] S. Peldek, Face Recognıtıon Usıng Cellular Automata Technıque, Karabük: Karabuk University, 2012.
[42] S. Peldek, Y. Becerikli, “GMACA ile Hareket Tespiti Yapılan Video Görüntülerde İnsan Hareketlerinin Tanınması”, Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, 2018(18-2), 2018.
[43] S. Peldek, Y. Becerikli, “Use of multiple attractor cellular automata for dimension reduction”, 2017 International Conference on Computer Science and Engineering (UBMK), Antalya, 2017.
[44] P. P. Chaudhuri, Additive cellular automata, Los Alamitos, Calif [u.a.]: IEEE Computer Society Press, 1997.
[45] S. Das, B. K. Sikdar, P. P. Chaudhuri, “Characterization of Reachable/Nonreachable Cellular Automata States”, Proceedings of Sixth International Conference on Cellular Automata for Research and Industry, Netherlands, 2004.
[46] W. Duch, K. Grudziński, “Ensembles of Similarity-Based Models”, Advances in Intelligent and Soft Computing, cilt 10, M. Kłopotek , M. Michalewicz ve S. Wierzchoń , Dü, Heidelberg, Physica, Heidelberg, 75-85, 2001.
[47] N. Naskar, Theory and applications of nonlinear cellular automata in pattern classification, Shibpur: Bengal Engineering And Science University, 2009.
[48] M. R. Bozkurt, N. Yurtay, Z. Yılmaz, C. Sertkaya, “Comparison of different methods for determining diabetes”, Turkish Journal of Electrical Engineering & Computer Sciences, 22, 1044-1055, 2014.