Cellular Automata Based Binary Classification

Year 2019, , 43 - 58, 31.01.2019

Serkan Peldek , Yaşar Becerikli

https://doi.org/10.17671/gazibtd.397452

Abstract

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

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

Abstract

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. 

Keywords

hücresel otomata, çoklu cezbedici hücresel otomatlar, , ikili sınıflandırma

References

• [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 Multi-Label 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.