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

At initialization ( t = 0), the data items x i are randomly associated to the
cells σ i∈L ( t = 0). Then, a set of transition rules φ r is iteratively applied on a
range of r cells ( r specifies the size of the neighborhood for the rule φ r ). The
transitions are local in both space and time: a cell evolves according a function
of the current state of that cell and its neighboring cells. One iteration step is
achieved by the application of the rules φ r to each cell in the lattice

L

.The
number of rules in the set, R , is computed in terms of the number of cells in
the lattice, N , and the size of the greater cluster: the greater R , the greater the
clusters sizes can be.
The process finishes when the the lattice converges to a final state, in which

the states of each cell σ i ( t )are stationary and equivalent to the previous states
σ i ( t

L

− 1), for each i =1 ,...,N .Twostates σ i and σ j are equivalent when the

associated data items x i and x j belong to the same cluster.

A generic rule φ r for a neighborhood of r cells can be written as follows:

[ σ i ( t +1) ,σ i +1 ( t +1) ,...,σ i + r− 1 ( t +1)]= φ r ( σ i ( t ) ,σ i +1 ( t ) ,...,σ i + r− 1 ( t ))
(1)
where i is the initial or reference cel l .Noticethat r must be greater or equal
to 2, i.e. the minimum neighborhood considered has 3 cells. Fig. 1 shows one
iteration of the algorithm.

⎬
⎭

r =3 σ 0 σ 1 σ 2 ... ... σ 1 σ 2 σ 3 ... ...

r =4 σ 0 σ 1 ... σ 3 ... ... σ 1 σ 2 ... σ 4 ... ...

r =5 σ 0 σ 1 ... ... σ 4 ... ... σ 1 σ 2 ... ... σ 5 ... ...

For each
iteration

. .

r σ 0 σ 1 ... ... σ r ... ... σ 1 σ 2 ... ... σ r ... ...

Fig. 1. For each iteration the rules φ r are sequentially applied to each cell in the
lattice L and r is also increased for checking if the data items are similar to the current
reference cell

The rule φ r computes the distance between the feature vectors of the data
items associated to the reference cell σ i ( t ) and its contiguous cell σ i +1 ( t )and
compares it to the distance between the feature vectors of the data items associ-
ated to the reference cell σ i ( t )andthelastcellinthatneighborhood σ i + r− 1 ( t ).
The data items associated to the cell σ i +1 ( t + 1) will be the data items with the
lesser distance. Formally:
σ i +1 ( t +1)= σ i +1 ( t )

if d ( x i , x i +1 ) <d ( x i , x i + r− 1 )

(2)

σ i + r− 1 ( t )otherwise