Speciation by k-means Clustering (SharpNEAT)

Speciation by k-means Clustering

k-means clustering (k-means) is a method that partitions n data points within a vector space into k distinct clusters. Points are allocated to the closest cluster and cluster locations arise naturally to fit the available data. k-means minimizes intra-cluster variance, that is, clusters form that minimize the sum of the squared distances between data points and the center (centroid) of their containing cluster. However, k-means is not guaranteed to find a global minimum.

An alternative explanation from wikipedia:

k-means clustering is a method of cluster analysis which aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean.

k-means has some attributes that make it a promising candidate for performing speciation with NEAT. These are :

k-means is applicable to sets of points in higher dimensional spaces, such as a population of NEAT genomes.
k-means partitions data points into k clusters. This meets the requirement in NEAT of speciating into k species.
k-means is not dependent on any particular distance metric. The k-means method requires a distance metric to be defined but the method itself is independent of any specific metric, such as Euclidean distance. E.g. The genome compatibility metric from O-NEAT could be used.
Simple to implement.

In addition, some benefits of k-means in comparison to speciation in O-NEAT are:

There is no compatibility threshold and therefore we don't have the problems associated with the threshold; specifically the need for a scheme to maintain the number of species at or near the target number by dynamically updating the threshold.
Genomes are guaranteed to be allocated to the nearest cluster. In comparision O-NEAT allocates genomes to the first species in a list that is within the compatibility threshold, and as such may allocate genomes to a cluster other than the nearest one.
k-means is a widely accepted and understood method and as such its use facilitates explanation and understanding of the NEAT method as a whole.

More speculatively, it is likely that k-means finds better clusters than O-NEAT, that is, we can reasonably expect that k-means will generally result in lower intra-cluster variance ('tighter' clusters), partly due to the second bullet point above. However this is an unproven claim at this time.

The k-means Algorithm

There exist a number of algorithm variations for implementing the k-means method; however, the standard approach is to start with randomly allocated clusters and to iteratively re-allocate points until the clusters become stable. The algorithm steps are:

Allocate data points randomly to k clusters.
Calculate the center (centroid) of each cluster.
For each point find the cluster centroid it is closest to and move it to that cluster (if it is not the point's current cluster).
If clusters have changed then goto step 2.

The algorithm stops when the clusters become stable (e.g. zero reallocations) or some maximum number of iterations has been performed; this latter test case is necessary because the clusters may not stabilise in a reasonable amount of time for some sets of points, this issue may become more prevalent when dealing with points in higher dimensional spaces and/or when using non-Euclidean distance metrics such as Manhattan distance. Unstable clusters are typically not a significant issue because clusters will be distinct and well formed after just a few iterations despite not being completely stable.

Important modifications to the above algorithm are :

Initialization by randomly allocating just one data point to each cluster; these points effectively become cluster centroids and the remaining points are allocated to the nearest centroid. This guarantees that each cluster will have at least one member after the first iteration. Without this modification some clusters may become empty after the first iteration.
Even with the above modification empty clusters can still occur in later iterations, this is especially so for higher dimensional spaces and some non-Euclidean distance metrics. Therefore some means of re-establishing k clusters is required when this happens. Reasonable solutions are to allocate the points furthest from any centroid to the empty species, or to split the largest clusters or the clusters with the largest intra-cluster variance.
k-means++. This is a variation on k-means that aims to select better initial centroids.

N.B. An alternative approach that avoids empty clusters is the k-medoids algorithm. k-medoids is very similar to k-means but instead of calculating a centroid one of the cluster members is chosen as the centroid, this is called a medoid. This has the affect that each cluster will always have at least one member.

Cluster Centroids

The centroid is the point that resuts in the lowest mean squared distance between it and the members of the cluster. For Euclidean distance this is the componentwise mean of all the points in a cluster, e.g. for two points on the Cartesian plane, (x1, y1), (x2, y2), the centroid is given by:

x = (x1+x2)/2, y = (y1 + y2)/2

This is also the equation for calculating the center of mass (barycenter) of a set of points of equal mass.

The centroid calculation is dependent on the distance metric and whether one wishes to minimize mean distance (MD) or mean squared distance (MSD). The appropriate calculations for L1, L2 distance and MD and MSD are:

	L1 Distance (Manhattan Distance)	L2 Distance (Euclidean Distance)
Minimize(Sum(Distance))	Componentwise median	Geometric Median. Fermat-Weber point. Weiszfeld's Algorithm.
Minimize(Sum(Distance^2))	?	Componentwise mean. Classical Centroid.

Table 1. Centroid calculations for L1, L2 Distance and minimizing distance and squared distance.

Note that the name k-means is based on the centroid calculation in the bottom right square of table 1, therefore strictly speaking any deviation from this sub-type of k-means is not k-means. E.g. Minimizing sum of L1 distance (top left sqaure in table 1) is sometimes refered to in the literature as k-medians.

Centroid-free k-means

For certain combinations of distance metric and choice of minimizing distance or squared distance it may not be possible or convenient to calculate a cluster centroid. In these cases k-means can still be used by using a different method for calculating the distance between a point and a cluster. Instead of measuring the distance between a point and the centroid we can calculate the mean distance between a point and every point in the cluster. We can then allocate the point to the nearest cluster as normal.

Another variation on this idea is the k-medoids algorithm. k-medoids requires that the centroid be one of the points in the cluster, therefore no centroid calculation is required. However by limiting the centroid to be one of the points the centroid is effectively a sub-optimal approximate choice of centroid with regard to minimizing mean distance or mean squared distance. Also, the greater number of point to point distance calculations required by k-medoids and centroid free k-means results in an algorithm with worse time complexity than standard k-means with centroids.

An alternative to centroid free k-means or k-medoids is to use an approximate centroid calculation. The componentwise mean and median calculations that give an optimal centroid for two of the combinations in table 2 can also be used as a simple method to produce an approximate sub-optimal centroid in the other two.

Choice of Distance Metric for NEAT

The standard distance metric used with k-means is Euclidean(L2) distance and this has the nice quality of having an easy to compute centroid calculation. However, the justification for using L2 distance is not always clear. Where points are composed of multiple independent (or mostly independent) variables such as document word counts there is a case for expecting L1 to be a better measure of distance between to points.

Where genomes are concerned we can consider the family tree that represents the chain of parents that lead to a given genome through a series of mutations and crossovers. If we now consider two genomes representing two different species on the leaf nodes of the tree and how distant they are genetically. In nature there is a great deal of genetic similarity between even wildly different species, but there is quite likely no direct or easy sequence of mutations that leads directly from one to another. The mutations that caused the two species to separate must be reversed, e.g. we reverse the mutations on species A, effectively walking back up the family tree to a common ancestor. We can now apply the mutations that lead to species B; walking back down the family tree on a separate path.

Species A and B have both acquired a series of mutations that have incrementally improved their fitness, but the mutations have also caused A and B to become more and more incompatible and specialised. If we were to try and mutate species A to B directly we would have to find a sequence of fit genomes directly between A and B and this implies mixed morphologies (in nature) and mixed topolies (for neural networks).

We know there is a path up the family tree and back down, and this is similar in concept to Manhattan(L1) distance, where to traval between points we must travel parallel to the x and y axes rather than directly between the two points. The genetic distance case can also be thought of as a variation of edit distance which measures the number of edits requried to convert A into B, but crucially the type or 'direction' of edits is restricted.

Defining the Position of NEAT Genomes

In order for k-means to cluster genomes their position in some coordinate space must be defined. The simplest approach is to consider each unique connection gene innovation ID to represent a numbered dimension and the connection weight as a position in that dimension. This effectively means we have an unbounded number of dimensions; the dimensionality of the space increases as the population complexifies. Also note that we ignore neuron genes because they are redundant in the context of representing an artificial neural network (ANN); a complete ANN can be constructed from just the connection genes.

SharpNEAT abstracts representation of position away from genomes by defining a CoordinateVector class that contains a list of (ID,value) pairs; this list only defines a position in the dimensions a genome is in, not a position for every innovation ID currently defined across the whole population; CoordinateVector therefore remains relatively compact in terms of computer memory usage. An alternative approach would be to define distance metrics that operate on genomes directly, this allows the same coordinate space to be used but the range of speciation strategies would be limited. Crucially, with no abstract position class there is no way of representing the centroid required by strategies such as k-means, apart from by manufacturing a new genome to act as a centroid; however that approach leads to a clash of design goals inside genome classes. In addition, distance metric classes would have to be implemented for each type of genome, e.g. common metrics such as Manhattan distance would have to be re-implemented for each genome class thus adding additional development and testing effort when experimenting with new genome types.

Coordinate System in O-NEAT

It turns out that the genome distance metric defined by O-NEAT is very close to Manhattan distance. For matching conenction genes the O-NEAT distance scales the distance between them by the c3 coefficient (see Speciation in Original NEAT). Non-matching genes yield a fixed distance, the c1 and c2 coefficients in the O-NEAT distance equation. By adding a coefficeint to Manhattan distance to scale matching positions on an axis and also a fixed constant for non-matches we can generalise the Manhattan distance metric to accomodate both classical Manhattan distance (MD) and O-NEAT. For clasical MD the coefficient is simply set to 1.0 and the constant to 0.0. If necessary we can also define a second coefficient in order to distinguish between disjoint and excess genes/positions.

A k-means Example in 2D Space

The following animated GIF demonstrates k-means clustering operating on a set of randomly generated points in 2D space. The points have fixed position, point colour indicates the owning cluster and we can see how clusters spontaneously form to represent the data and iteratively improve over a number of algorithm iterations (click image to see animation).

Click image to see an animated gif of k-means in two dimensions.

Time Complexity of k-means and Variants

For n data points, k clusters and i iterations

Standard k-means (using a centroid). O(i * n * k)
Centroid-free k-means. O(i * n^2)
k-medoids. O(i * (n-k)*k) = O(i * n * k - k^2)

The length of genomes to compare is also a significant factor in algorithm time. The above big O notation only considers how the number of comparisons scale, and excludes the time complexity of a typical comparison.

Attachments (1)

kmeans_example.gif - on 9 Sep 2009 10:59 by Colin Green (version 2 / earlier versions)
520k View Download