Evolutionary Data Clustering in MATLAB

Clustering is an unsupervised machine learning task. It groups a set of data objects so that members of the same group (cluster) are as similar as possible, and members of different groups are as different as possible. Many real-world problems can be stated as clustering problems.

Clustering appears in machine learning, data mining, and statistical data analysis. It has many applications in pattern recognition, image processing, signal processing, bioinformatics, and information retrieval. For more background, see the Wikipedia article on cluster analysis (opens in a new tab).

Clustering as an optimization problem

Many approaches exist for clustering, such as Lloyd’s k-Means Algorithm (opens in a new tab), DBSCAN (opens in a new tab), OPTICS (opens in a new tab), and Fuzzy Clustering (opens in a new tab). Each has its own advantages and drawbacks.

Clustering can also be stated as an optimization problem, so optimization algorithms can solve it. Evolutionary algorithms and metaheuristics are a good fit. They also handle a harder version of the task, called automatic clustering, where the number of clusters is not known. Some classic clustering methods, such as k-Means, need the number of clusters in advance. With a good objective, evolutionary methods can perform automatic clustering just like ordinary clustering.

What this post shares

This post shares a complete open-source MATLAB implementation of evolutionary data clustering. Three metaheuristics perform clustering and automatic clustering:

• Real-Coded Genetic Algorithm (GA)
• Particle Swarm Optimization (PSO)
• Differential Evolution (DE)

The algorithms are implemented in a structured way, so if you know MATLAB, you can easily use the code in your research projects.

Clustering with a known number of clusters

The folder 01 Evolutionary Clustering solves the standard problem. A solution is a $k \times d$ matrix whose rows are the cluster centers $m_1, \dots, m_k$, where $d$ is the number of features. Each center is limited to the range of the data in every feature. The sample script uses $k = 3$.

The cost function in ClusteringCost.m assigns every data point $x_i$ to its nearest center and adds up these distances, the within-cluster distance:

The algorithm searches for the centers that make this sum as small as possible. The distances are Euclidean, and they are not squared as in the k-Means objective.

Automatic clustering

The folder 02 Evolutionary Automatic Clustering also finds the number of clusters. A solution now holds up to $k = 10$ candidate centers, and each center has one extra value $a_j \in [0, 1]$, its activation. A center is used only if $a_j \ge 0.4$. If fewer than two centers pass this threshold, the two with the largest activations are switched on, so every solution has at least two clusters.

The sum of distances cannot be used here, because adding centers cannot increase the best achievable within-cluster distance. Instead, the code measures the quality of the clustering with a validity index that balances compact clusters against well separated ones. Two indices are included, and the variable Method in ClusteringCost.m selects one of them:

The default is the Davies-Bouldin (DB) index (Davies and Bouldin, 1979), in DBIndex.m. For each pair of clusters it compares the scatter inside the two clusters with the distance between their centers, and it averages the worst ratio of each cluster:

Here $S_i$ is the root mean square distance of the points in cluster $i$ to its center. A smaller value means a better clustering.

The other option is the CS index, in CSIndex.m. It divides the average of the largest within-cluster distances by the average distance between each center and its nearest other center. A smaller value is also better here.

How to run it

Open one of the two folders in MATLAB and run main.m. A dialog asks which algorithm to use (GA, PSO or DE) and then starts ga.m, pso.m or de.m. Each script loads the sample data from mydata.mat (300 points in two dimensions), prints the best cost in every iteration, draws the current best clustering, and plots the best cost against the iteration at the end.

To cluster your own data, replace mydata.mat with a file that holds a matrix X, one sample per row, and change k at the top of the script. The code uses pdist2 and unifrnd, so it probably needs the Statistics and Machine Learning Toolbox.

Parameters in the code

All the scripts run for MaxIt = 200 iterations. The other parameters are set at the top of each script.

Check the result

Scale features deliberately before using Euclidean distances so that large numeric ranges do not dominate by accident. Check for empty clusters, coincident centers, and nonfinite validity scores. The automatic variant searches between two and ten active clusters with the defaults, so it cannot discover an unrestricted cluster count. Compare repeated runs and inspect the assignments as well as the index value. A favorable validity index does not by itself establish useful groups for the application.

Related posts

• DBSCAN Clustering in MATLAB, a density based method that also finds the number of clusters.
• Neural Gas and GNG Networks in MATLAB, for clustering and topology learning.
• Intelligent Image Color Reduction and Quantization, an application of clustering to images.

Mostapha Kalami Heris, Evolutionary Data Clustering in MATLAB (YPML101), Yarpiz, 2015. https://yarpiz.com/evolutionary-clustering-ypml101

@misc{yarpiz-ypml101,
  author = {{Mostapha Kalami Heris}},
  title = {{Evolutionary Data Clustering in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPML101},
  url = {https://yarpiz.com/evolutionary-clustering-ypml101}
}