Image Image Image Image Image Image Image Image Image Image

Turing Finance | December 4, 2016

Scroll to top

Top

10 Comments

Clustering using Ant Colony Optimization

Clustering using Ant Colony Optimization

For many years entomologists have studied the behaviour of ant colonies and marveled at their ability to solve complex problems collectively. An example of this collective intelligence observed by entomologists is that ants leaving their colony will often follow very efficient routes between their colony and surrounding food sources. Another example is that ants form mounds of dead ants which distract predators from their colony.

Entomologists study ants to understand how they are able to perform such intelligent tasks. Computer scientists then use this information to derive algorithms which mimic the ants in order to replicate their intelligence. Artificial intelligence algorithms which mimic intelligent behaviour observed in nature are called nature-inspired algorithms. Ant colony optimization algorithms represent an interesting subset of nature-inspired algorithms.

Two popular ant algorithms are inspired by the two examples mentioned previously. The first algorithm is used to solve the classical shortest path problem and the second algorithm is used to perform dynamic clustering on large data sets. Both of these problems' complexity grows exponentially as the number of dimensions increase. Such problems are called NP-complete problems and cannot be solved analytically or by brute force.

Single Class Clustering

When ants form mounds of dead ants, also known as cemeteries, around their colony they are performing a simple form of clustering. Clustering is the problem of forming groups of similar items, in this example there is just one type or call of items namely the dead ants. Each living ant helps the colony to form clusters of these dead ants by autonomously following the very simple two-step algorithm described below,


Step One ~ While walking around, if you encounter a dead ant and it is surrounded by many other dead ants, do nothing, otherwise, if it is not surrounded by many other dead ants, pick it up.

Step Two ~ While waling around, if you are carrying a dead ant for each step you take check if you are surrounded by many other dead ants, if so then drop the dead ant here, otherwise, do nothing.


If you have many ants, essentially they will be walking around and either picking up ants, dropping ants, or doing nothing. Intuitively it makes sense that the ants would slowly start to form cemeteries of dead ants to lure away potential predators. This is called an emergent property. Emergence is when order (also known as a pattern) arises from the uncoordinated interactions of simpler entities that themselves do not exhibit such order.

Here is a video which demonstrates this emergent property,

The best thing about this algorithm is that the ants act autonomously meaning that no central control of the ants is required. This implies that the algorithm, if implemented using concurrent programming, is highly scalable and is therefore quite relevant to large data-sets. Notice that in the video there are two classes of items being clustered, red items and blue items. The simple algorithm mentioned previously can easily be extended multiple classes. 

Multiple Class Clustering

Clustering is only really useful when a given data set contains of two or more classes of input patterns and you want to partition it into subsets. In order to do this you need a way of distinguishing patterns from one another. One approach is to use distance metrics, which measure the distance between any two patterns.

For continuous valued patterns Manhattan, Euclidean, and Minkowski distances work well. Another approach for measuring the distance between continuous valued patterns is to measure their correlation, cosine similarity is an example of this. For discrete valued patterns Hamming Distance and the Jaccard Coefficient are popular choices.

Minkowski distance is a generalized distance metric which can be equivalent to Manhattan or Euclidean distance. Given two patterns (vectors) \textbf{x} and \textbf{y}, the Minkowski distance of order p between \textbf{x} and \textbf{y} is given by,

d(\textbf{x}, \textbf{y}) = \bigg( \sum^n_{i=1} |x_i - y_i|^p \bigg)^{\frac{1}{p}}

Minkowski Distances

Different order Minkowski distances

d(\textbf{x}, \textbf{y}) is equivalent to the Manhattan distance between \textbf{x} and \textbf{y} when p=1; the Euclidean distance between \textbf{x} and \textbf{y} when p=2; and the Chebyshev distance between \textbf{x} and \textbf{y} in the limiting case where p=\infty. For some more information on distance metrics please see the related post, Monte Carlo K-Means Clustering of Countries

This concept is incorporated into the algorithm by specifying that the ants should pick up an object if it is surrounded by dissimilar objects and drop an item if it is surrounded by similar items. The challenge now becomes determining how large the neighbourhood should be for any ant, and specifying the pick up and drop rules probabilistically so that the algorithm is stochastic which allows it to break down sub-optimal clusters.

Ant Colony Optimization

The ant colony optimization algorithm is defined by the pick up and drop off rules followed by the ants. Given a point in space these rules look at the surrounding points and determine the average similarity of the surrounding patterns either to the pattern at that point or to the pattern being carried by the ant. The number of surrounding points which are looked at is called the neighbourhood function. A neighbourhood function could be as complex as a copula or as simple as a radius which specifies the number of points in every direction to consider. 

Ant Neighbourhoods

In the image above we see how the simple radius-based neighbourhood function works. Starting at the location of the ant every point on the grid within an n radius is looked at. For each block which contains an item, the similarity between either the item at that point on the grid, or the item the ant is carrying, is calculated. These are summed up and divided by the total number of points looked at which, for a grid, is given by (2n)^2 - 1. This can be done using a simple nested-for loop as shown below. Note that this could be done more quickly in parallel.

This essentially calculates the average dissimilarity of the item at that point on the grid (item being carried) to the surrounding items. If this is high, then the item should be picked up (not dropped); if this is low then the item should be not picked up (dropped). Let the output from this function be denoted by D for density. Observe that this term is being normalized in the code by the maximum average distance seen to date. This is done to ensure that when we calculate the probabilities in the drop and pick up rules D is in the range (0, 1).

The probability of dropping an ant, P(drop) is,

T = e^{-c.D}

P(drop) = \frac{1 - T}{1 + T}

The probability of picking up an ant, P(pick) is,

T = e^{-c.D}

P(pick) = 1 - \frac{1 - T}{1 + T} = 1 - P(drop)

where c is a parameter for controlling convergence. The larger c is, the faster the ants will converge on a solution, because the less likely it is to drop or pick up an ant for any given density. This is illustrated in the graphs below. 

Ant Colony Optimization Neighbourhood Functions

Now that we know how the ants will pick up and drop off items, and how we measure the similarity between those items, the only remaining component is defining how the ants move around. This process is quite simple and is defined by two parameters, the number of ants, m, and the step size of each ant, s. Initially the m ants are uniformly initialized across the grid. From that point on their next location (xy coordinate) is their current location plus a two dimensional vector of random integers between -s and sThe resulting coordinate is then modded by the height, h, and width, w, of the grid to generate a new location that is guaranteed to be on the grid.

Taking the modulo of the location essentially means that there are no edges on the 'grid' because it wraps around. This reduces the maximum possible distance between any two patterns to max(\frac{1}{2} h, \frac{1}{2} w). The resulting shape (grid without edges on the top, bottom, or either side) is basically a three dimensional doughnut. The ants move around this shape randomly picking up and dropping items according to the pick up and drop probability rules.

Putting It Together

The final form of the algorithm ends up being something quite simple. This algorithm is consists of the steps presented below when given a set of un-ordered input patterns, \textbf{Z},


Initialize a grid of size h \times w where h.w \geq 2|\textbf{Z}|
Randomly scatter patterns \textbf{Z} across the grid
Initialize m ants in random locations
While stopping condition is not true 
----For each ant : 
--------Move to new location
--------If the location contains a pattern :  
------------If the ant is not already carrying a pattern : 
----------------Assign p \leftarrow P(pick)
----------------Assign r \leftarrow random()
----------------If r < p : 
--------------------Pick up the pattern
--------Else if location contains no pattern:
------------If the ant is carrying a pattern:
----------------Assign p \leftarrow P(drop)
----------------Assign r \leftarrow random()
----------------If r < p :
--------------------Drop the pattern
Identify the clusters on the grid using a cluster finding algorithm


One major benefit of the algorithm is that it can be run indefinitely and new patterns can be added to \textbf{Z} or the patterns in \textbf{Z} can be updated over time and the algorithm will adapt to the changing conditions quite well. This is why I refer to this as a dynamic clustering algorithm. That having been said the algorithm does suffer from a number of shortcomings. The biggest shortcoming is the trade-off between run-time and large clusters as defined by n. The larger n is the larger the clusters will be and the less likely the ants are to produce multiple clusters of the same class, however, the larger n is the more time-consuming the calculation of D and therefore P(drop) and P(pick) become. However, this could be largely offset with a good parallel implementation of the algorithm.

Additionally this algorithm works only with memory-less ants i.e. ants which move around randomly. This algorithm could be improved through the implementation of memory which would essentially bias the direction of the ants towards a spot on the grid in their memory where they saw a similar pattern in the past.

Python Implementation and Applications

One potential application of dynamic clustering in finance is to automated portfolio construction. One challenge with constructing portfolios is picking investments which are dissimilar from one another so as to diversify the portfolio. One measure of this is correlation but correlation is subject to a number of fatal flaws.

An alternative approach taken by a computational investor might involve clustering the universe of available securities according to quantities for factors such as value, firm size, momentum, geographic location, etc. The wisdom here is that securities exposed to a similar array of factors should behave similarly and therefore exhibit stable high correlations over time. The investor would then need to select the best investments from each cluster.

Another benefit to using Ant Colony Optimization to do this is simply that the investor would not need to specify the number of clusters up-front as they would with other clustering techniques such as K-Means Clustering.

This implementation was used to produce the clustering video shown previously. This was done by generating images of the grid using Matplotlib's matshow feature and then merging these images into a video.

Previous Story

There are no older stories.

Comments

  1. Martin Thomas

    I love to use your code, but it give me the following error and I don't know how to deal with it.

    Traceback (most recent call last):
    File "ants.py", line 230, in
    optimize(500, 500, 250, 500000, 25, 10, freq=500, path="Video 8/")
    File "ants.py", line 214, in optimize
    grid = Grid(height, width, path)
    File "ants.py", line 29, in __init__
    self.grid = numpy.empty((height, width), dtype=Datum)
    TypeError: data type not understood

    Thanks !!
    Have a nice day and continue the good work
    Thomas

    • Thanks Thomas. What version of Numpy are you using? It seems like it isn't recognizing the Datum class which is defined in the source code. Either that is a numpy versioning problem (2.7 vs. 3.x), or something went wrong with a) the order of the code or b) the naming of the classes in the .py file.

  2. Thomas

    Hello,
    I'm a french student and i want to make a project about Ant colony program and applications.
    About the first algorithm "Probability", i don't understand what is "self".
    Can you help me ?
    Thanks a lot !
    Thomas

    PS: is it possible to contact (by email) the person who maid this program ?

    • Hey Thomas, you can drop me a mail directly via the contact form on the website. I wrote the code. The self keyword is used when you are coding object orientated-ly, and it refers to the object which is doing the calling. It is the equivalent of this in Java or C++.

  3. S NAYAK

    Hello,
    I tried to run your code in Jupyter Notebook. Its executed, the image is created also. But the simulation of clustering is not played. Each time it pops up a small window with "Not responding" message.

Submit a Comment