chapter  19
22 Pages

Nature-Inspired Clustering

ByJulia Handl, Joshua Knowles

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 19.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420 19.2 Specialist (Self-Organizing) Clustering Heuristics . . . . . . . . . . . . . . . . . . . . . . . 420

19.2.1 Self-Organizing Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421 19.2.2 Ant-Based Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 19.2.3 Flocking Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425 19.2.4 Affinity Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 19.2.5 Prospects and Future Developments . . . . . . . . . . . . . . . . . . . . . . . . . . . 428

19.3 Meta-Heuristic Clustering Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429 19.3.1 Meta-Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429 19.3.2 Solution Representation (and Operators) for Data Clustering . . . . . . . . 430 19.3.3 Objective Functions (Clustering Criteria) . . . . . . . . . . . . . . . . . . . . . . . 431 19.3.4 Meta-Heuristics for Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431 19.3.5 Prospects and Future Developments . . . . . . . . . . . . . . . . . . . . . . . . . . . 433

19.3.5.1 Multiobjective Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 19.3.5.2 Application Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435

19.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437

We survey data clustering techniques that are inspired by natural systems. It is instructive to divide this group into two distinct classes: those methods derived directly from clustering phenomena in nature, such as the self-organizing behavior of some ants, or the schooling of fish and flocking of birds; and those methods that view clustering as an optimization problem, and apply nature-inspired general heuristics (or meta-heuristics) to this problem. The first group work largely in a bottom-up fashion, making them potentially powerful for parallelization and for operating in dynamic and noisy clustering applications, such as distributed robotics. The second group has the advantage that the clustering problem can be specified very precisely using one or more mathematical objective functions; then, due to the general-purpose properties of the heuristics, very good performance against these objectives can be achieved. This chapter charts the progress in these two broad classes of nature-inspired clustering algorithms and points out some further prospects in this area.