How to ensemble Clustering Algorithms
K-Means like you’ve never seen before
Introduction
Ensemble, in the AI context, is a technique that tries to improve performance by aggregating the prediction of multiple Machine Learning models. It can be considered a type of meta-learning, where an external agent computes a final prediction judging the individual predictions of other agents.
There are several ways to ensemble supervised algorithms, like bagging and boosting. In particular, boosting techniques (especially XGBoost) became state-of-the and indispensable tools in any machine learning application.
On other hand, in unsupervised problems, we do not hear a lot about ensemble techniques. So, it’s possible to use this technique on clustering algorithms? It’s not only possible but a lot of strategies have been developed over the years [1]. This post explores two of them.
The similarity matrix
Unlike supervised approaches, where the ensemble can be done straightforwardly by stacking learners above others, clustering is not so simple.
In clustering, the final label of the data has no meaning alone, does not matter if a point is in cluster 1 or 2, what matters is who is also in this cluster with it. So, joining the information of two different clustering results is not as simple as comparing if the final labels are the same, as in classification. Some way to compute how much agreement exists on the different partitions is required.
The similarity Matrix is a simple way to translate this information into a data structure. It is built as follows:
Considering that we have n points on our dataset, the similarity matrix will be a n x n matrix, where the position (i,j) contains how many times the points i and j have fallen in the same cluster. The following image shows an example of this matrix.
A better way to represent this information is using percentages instead of solid counts. In this normalized form, each position (i,j) represents the probability of i and j falling together in the same cluster. This normalization is obtained by dividing each row by its diagonal value (total count).
This approach is better for machine learning, as all the values fall in the range [0,1]. The normalized similarity matrix will be our basic building block for the following sections.
Ensemble with Graph connected components
“Graph connected components” looks like a seven-eyes monster but is a quite simple technique. This approach considers that two points that appear together (in the same cluster) more than X% of the time (for example, 10% or 50%) should be in the same final cluster.
If we consider the similarity matrix as a graph, where each point is a node and the edge from (i,j) has a weight equal to the value of (i,j) in the matrix, what this approach essentially makes is removing the edges that have values below our threshold (X%), disconnecting the nodes. The node groups that remained connected are our final clusters. This is why this approach is called “connected components”.
As it creates new clusters based on a simple threshold, it can be considered equivalent to simple bagging ensemble methods for supervised models.
Let’s see an example in Python.
The first step is to create a clustering dataset.
The code below applies this ensemble clustering technique using K-Means.
The full code is available on github, and the implementation details were omitted to improve readability.
Let’s explain the code.
NUM_KMEANS=32 is the total number of k-means models that are used in the ensemble.
The code uses the MiniBatchKMeans to reduce training time. Setting n_init=1 is essential because, by default, sklearn’s K-means model is executed several times, and only the best result is kept. As we want all results stored, the value n_init=1 ensures that this happens. Reducing max_iter and batch_size also improves code speed.
ClusterSimilarityMatrix is just a simple module that creates a similarity matrix. It receives a clustering partition and updates the counts iteratively. After being built, the similarity matrix is normalized.
The following line of code is the model’s core.
graph = (norm_sim_matrix>MIN_PROBABILITY).astype(int)Here, the probabilities below MIN_PROBABILITY=0.6 are turned into 0 (remove the edge from the graph), while the probabilities above are turned into 1 (maintain the edge on the graph).
Get João Pedro’s stories in your inbox
Join Medium for free to get updates from this writer.
The value for MIN_PROBABILITY works as a hyperparameter, and should be refined to achieve the results intended. If its value is set too high (0.9–1.0), the data will probably be distributed in many little clusters, if it is set too low (0.2–0.4), it may find big clusters.
After that, is just a matter of finding the graph’s connected components. Luckily, the scipy package already gives us the code for that.
So, let’s see the results.
As we can see, the results from the ensemble technique are way more coherent with the expectations about how the data should be partitioned.
This technique is quite interesting. K-means is known for only finding globular-like clusters, splitting the space into Voronoi cells, using a predefined value for k. But, by applying an army of k-means in this simple ensemble technique, they’re able to find more complex-shaped, like HDBSCAN.
Ensemble with other clustering models
Many clustering algorithms make use of an intermediate representation of the data, such as a neighbors graph or a distance matrix in order to find the final clustering. For example, the famous HDBSCAN represents the data using a Minimal Spanning Tree.
Because of this, many clustering algorithms accept a similarity/distance matrix as input instead of a regular points list. So, the similarity matrix introduced previously can be fed into them.
The idea behind this approach is to use a set of “weaker” clustering algorithms to create a “stronger” foundation for the following algorithm. This approach resembles the boosting techniques in supervised machine learning.
Let’s look at the following example, where we use regular K-Means to “improve the performance” of a spectral clustering algorithm.
It’s important to remember that the notion of “improvement” and “better” can be tricky in clustering, as there is no clear absolute definition of what a cluster is/should look[2].
Like previously, was created a set of NUM_KMEANS K-Means models. The aggregator_clt is the algorithm responsible to cluster the similarity matrix, creating the final clustering labels.
128 K-Means models were used as “weaker” learners and Spectral Clustering as the aggregator. It’s important to set affinity=“precomputed”, in order for the model to understand that a similarity matrix is being passed for the .fit() method.
Note:
The spectral clustering algorithm accepts a similarity matrix, but this is not the case for all clustering models that has affinity=“precomputed” or metric=“precomputed” in they hyperparameters (sklearn). Some require a distance matrix, which is the opposite. A simple way to transform a normalized similarity matrix into a distance matrix is by applying a log transformation, distance = -log(similarity), just use some technique to avoid 0≥similarity or similarity>1
The EnsembleClustering is a simple class used to encapsulate the Similarity Matrix creation and models’ training.
So, let’s see the results.
Spectral clustering is not a simple model as K-Means, (curiously, it can use k-means as a step in its implementation), but it was not able to find the clusters that we want. The ensemble method performs visually better than the Spectral clustering alone.
It’s important to remember that this post uses Mini batch k-means just for the sake of execution speed. Any clustering algorithm can be used to build a similarity matrix (just watch out for outliers). So, as homework, I suggest trying to run the code with a heterogeneous set of clustering algorithms, like in the image below.
Conclusion
Ensemble techniques reach the state-of-art in many supervised machine learning tasks. In clustering, on the other hand, they are less famous and not so simple to implement. Hopefully, this post shines a light on how we can perform ensemble on clustering.
We’re able to use the K-means model, one of the simplest clustering models, to perform non-globular clustering, without the need of passing a k value. It was also capable of “improving” the results of another clustering algorithm.
Of course, like all in life, there is no silver bullet, and this post is not sponsored by the “clustering ensemble company”.
The main goal of this post is to present techniques for ensemble clustering. Even though they are very simple, I hope that the techniques covered in this post have helped you understand how the process works.
This short post just scratches the surface of the clustering ensemble subject, search in the references below for more information. The Github repository with the code is also in the references section.
Thank you for reading! :)
References
Code on GitHub:
https://github.com/jaumpedro214/posts/tree/main/ensamble_clustering
[1] Boongoen, T., & Iam-On, N. (2018). Cluster ensembles: A survey of approaches with recent extensions and applications. Computer Science Review, 28, 1–25.
[2] Hennig, C. (2015). What are the true clusters?. Pattern Recognition Letters, 64, 53–62.
[3] Scikit-Learn, Official Documentation on clustering algorithms
[4] Wikipedia Article, Component (graph theory).
![Graph RAG Series:8/15 [Graph-Aware Retrieval and Context Assembly]](https://webproxy.poorya-velaei-d67.workers.dev/https://miro.medium.com/v2/resize:fit:1358/format:webp/1*uDsj43_Olz0fvjcMaTXLgQ.png)
