  Clustering is a difficult and widely-studied data mining task, with many
varieties of clustering algorithms proposed in the literature. Nearly all
algorithms use a similarity measure such as a distance metric (e.g. Euclidean
distance) to decide which instances to assign to the same cluster. These
similarity measures are generally pre-defined and cannot be easily tailored to
the properties of a particular dataset, which leads to limitations in the
quality and the interpretability of the clusters produced. In this paper, we
propose a new approach to automatically evolving similarity functions for a
given clustering algorithm by using genetic programming. We introduce a new
genetic programming-based method which automatically selects a small subset of
features (feature selection) and then combines them using a variety of
functions (feature construction) to produce dynamic and flexible similarity
functions that are specifically designed for a given dataset. We demonstrate
how the evolved similarity functions can be used to perform clustering using a
graph-based representation. The results of a variety of experiments across a
range of large, high-dimensional datasets show that the proposed approach can
achieve higher and more consistent performance than the benchmark methods. We
further extend the proposed approach to automatically produce multiple
complementary similarity functions by using a multi-tree approach, which gives
further performance improvements. We also analyse the interpretability and
structure of the automatically evolved similarity functions to provide insight
into how and why they are superior to standard distance metrics.
