Use of Asynchronous Cellular Automata in Clustering Problem
Souvik Roy, Virendra Kumar Gautam and Sukanya Mukherjee
In general, a cluster is a group of objects with common features and the objects of a cluster are similar to each other. To map the clustering problem in cellular automata (CA), here, we consider that if we take any two objects in a cluster, they are reachable from each other. Now, this property of clustering (in CA) leads us to use reversible cellular automata as clustering tool. This work uses finite sized fully asynchronous reversible cellular automata with stochastic update of cells for the purpose of data clustering. For this work, we consider asynchronous reversible CA with constant, linear (in CA size n), and δn number of communication classes (cycles), where δ is non-trivial. Here, we need to evolve the cellular systems to understand the reachability relation of two data objects which takes exponential time in the worst case scenario (commonly known as reachability problem). In this context, this issue of reachability relation is the major drawback of reversible CA based clustering literature. This paper develops an efficient algorithm to identify the reachability relation after considering the selected asynchronous CA rules. Next, a scheme is used to merge a group of clusters at every level based on the closeness of the clusters and it repeats until we get the desired number of clusters. The use of fully asynchronous reversible CA for clustering enables us to work with only a very few rules and results in faster convergence. This paper demonstrates a comparative analysis of our technique to the existing benchmark clustering algorithms (along with existing CA based clustering algorithms) using an experimental study.
Keywords: Cellular automata (CA), fully asynchronous CA, reversible CA, communication class, clustering