A Novel Linear Cellular Automata-Based Data Clustering Algorithm - Foundations on Natural and Artificial Computation - page 71

can evolve. Under this approach, social phenomena such as the emergence of
order, the micro-macro relations and the social dynamics can be analytically
understood with the help of Cellular Automata Theory.
Several data clustering algorithms based on the social collective behavior have
been proposed [11,9] and also in other different tasks [8,14,6,5].
Beckers et al. [1] run a classic experiment in which a group of mobile robots
gather several randomly distributed objects and cluster them into separated
piles. The agents' coordination in those experiments was achieved through stig-
mergy , principle originally developed for the description of termite building be-
havior. The agents' behavior is determined by an indirect communication be-
tween them, which is carried out sensing and modification of the agents' local
environment. This situated experiment inspired several successful data clustering
algorithms [2,15,13].
In ants clustering algorithms, a group or colony of ant-like agents perform
a clustering task in a toroidal 2D rectangular lattice or grid in which the N-
dimensional data items to be clustered have been previously scattered at ran-
dom with a single data item at each site. The individual data items randomly
scattered in the rectangular lattice can be picked-up, transported and dropped
by the ants-like agents. The two basic actions of picking-up and dropping a data
item are performed in a probabilistic way by the agents. Generally speaking,
the probability for an agent of picking-up a particular data item depends pro-
portionally on the number of similar data items deposited in its neighborhood,
so that the lower the number of similar neighbors, the higher the probability of
picking-up a particular data item. Conversely, the higher the number of similar
neighbors, the higher the probability for a loaded agent to drop a data item at
an empty site in the toroidal rectangular grid.
In this paper we propose a novel data clustering algorithm based on the idea
of considering the individual data items as mobile agents. Our proposed algo-
rithm combines insights from both ants clustering algorithms —particularly in
the idea of distributing at random the data items to be clustered toroidal discrete
lattices— and also from social segregation models based on Cellular Automata
Theory, in which the data items themselves, like individuals in a social neighbor-
hood, are able to move autonomously in the toroidal linear lattice, following a
basic rule for staying at a particular site if a similarity with the neighbors' con-
dition holds or for migrating from a particular location in which the similarity
with the neighbors' condition does not hold.

2 One-Dimensional Cellular Automata-Based Clustering

In this paper we propose to employ one-dimensional discrete lattices of cells upon
which cellular automata operate performing an unsupervised data clustering
process. Each cell σ i∈L ( t ) in the discrete lattice is the i th cell at time t and

is related to a particular data item, x i , in the dataset. The number of cells in
the lattice, N , is also the number of data items in the dataset. As usual for one-
dimensional lattices we are assuming periodic boundary conditions, in which
σ i +1 is identified with σ i .

L