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

A Novel Linear Cellular Automata-Based Data
Clustering Algorithm

Javier de Lope 1 , 2 and Dar ıo Maravall 1

1 Cognitive Robotics Group
Dept. of Artificial Intelligence
Universidad Politecnica de Madrid
2 Dept. Applied Intelligent Systems
Universidad Politecnica de Madrid
[e-mail], [e-mail]

Abstract. In this paper we propose a novel data clustering algorithm
based on the idea of considering the individual data items as cells be-
longing to an uni-dimensional cellular automaton. Our proposed algo-
rithm combines insights from both social segregation models based on
Cellular Automata Theory, where the data items themselves are able
to move autonomously in lattices, and also from Ants Clustering algo-
rithms, particularly in the idea of distributing at random the data items
to be clustered in lattices. We present a series of experiments with both
synthetic and real datasets in order to study empirically the convergence
and performance results. These experimental results are compared to the
obtained by conventional clustering algorithms.

Keywords: Cellular Automata, Machine Learning, Pattern Recogni-
tion, Data Mining, Data Clustering, Social Segregation Models, Ants
Clustering.

1 Introduction

Clustering is a method of unsupervised learning used in different fields such as
Machine Learning, Data Mining, Pattern Recognition, and so on. It deals with
the assignment of a set of data items into subsets or clusters in such a way that
the data items in the same cluster are similar .
Our proposed algorithm is inspired on social segregation models based on
Cellular Automata Theory. In this line of thought Schelling [12] originally pro-
posed models of segregation in which the population is composed of two well
differentiated types of individuals. Each individual cares about the neighbors. If
the neighbors dissatisfied him, then the individual moves to the nearest point
that meets his minimum demand, i.e. the nearest point at which a significant
proportion of his neighbors satisfy his demands.
In [7] Hegselmann et al. also present similar ideas based on the use of Cellular
Automata Theory [10] by identifying the individuals with cells in a toroidal
rectangular lattice and the individuals' choices with the states that the cells