Clustering Using Cyclic Spaces of Reversible Cellular Automata
Sukanya Mukherjee
Department of Computer Science and Engineering
Institute of Engineering and Management
Kolkata, West Bengal, 700091, India
sukanya.mukherjee@iemcal.com
Kamalika Bhattacharjee
Department of Computer Science and Engineering
National Institute of Technology
Tiruchirappalli, Tamil Nadu, 620015, India
kamalika.it@gmail.com
Sukanta Das
Department of Information Technology
Indian Institute of Engineering Science and Technology
Shibpur, West Bengal, 711103, India
sukanta@it.iiests.ac.in
Abstract
This paper introduces a cycle-based clustering technique using the cyclic spaces of reversible cellular automata (CAs). Traditionally, a cluster consists of close objects, which in the case of CAs necessarily means that the objects belong to the same cycle; that is, they are reachable from each other. Each of the cyclic spaces of a cellular automaton (CA) forms a unique cluster. This paper identifies CA properties based on “reachability” that make the clustering effective. To do that, we first figure out which CA rules contribute to maintaining the minimum intracluster distance. Our CA is then designed with such rules to ensure that a limited number of cycles exist in the configuration space. An iterative strategy is also introduced that can generate a desired number of clusters by merging objects of closely reachable clusters from a previous level in the present level using a unique auxiliary CA. Finally, the performance of our algorithm is measured using some standard benchmark validation indices and compared with existing well-known clustering techniques. It is found that our algorithm is at least on a par with the best algorithms existing today on the metric of these standard validation indices.
Keywords: reversible cellular automata; reachability; large length cycle; iterative level-wise clustering; connectivity; silhouette score; Dunn index
Cite this publication as:
S. Mukherjee, K. Bhattacharjee and S. Das, “Clustering Using Cyclic Spaces of Reversible Cellular Automata,” Complex Systems, 30(2), 2021 pp. 205–237.
https://doi.org/10.25088/ComplexSystems.30.2.205
