Reversible Cellular Automata: A Natural Clustering Technique
Sukanya Mukherjee, Kamalika Bhattacharjee and Sukanta Das
This work proposes reversible finite cellular automaton (CA) as a natural clustering tool, where closeness between two configurations is measured as whether they are reachable from each other. As any finite reversible CA distributes its configurations into a number of cyclic spaces, so, two configurations belonging to the same cycle are close to each other. Exploiting this behavior, we treat reversible CA as a natural clustering technique where each of the cyclic spaces forms a unique cluster. To use this characteristics, real data objects are mapped to binary strings (configurations of a CA) using a surjective encoding function. Some properties are identified to filter candidate cellular automata (CAs) that perform effective clustering. Further, an iterative algorithm is also proposed that guarantees that only the desired number of clusters are formed. Finally, performance of our algorithm on real data is measured using some standard validation indices. While comparing with the existing benchmark clustering algorithms, we have observed that our algorithm is at least at par with the best algorithms existing today. So, if chosen appropriately, the locality and interconnectivity of simple systems like reversible CAs have the potential to do the best clustering of any real-life data-set.
Keywords: Cellular automaton (CA), reversibility, reachability, iterative level-wise clustering, connectivity, Silhouette score, Dunn index