In this tutorial, you’ll set up a 3-node Proxmox cluster using three computers (or virtual machines for practice). By the end, you’ll have a working cluster ready to host virtual machines (VMs) and experiment with cool features like guest migration and VM replication etc.

Let’s dive in!

Prerequisites: What You’ll Need to Know

This guide is beginner-friendly for clustering, but you’ll need some basic skills to follow along. You should be comfortable with:

• Installing an OS from a USB drive (don’t worry, I’ll walk you through the steps).

• Using a terminal for simple commands like ping or nano.

• Setting up a home network with static IPs (for example, knowing your router’s IP range). No advanced virtualization or clustering experience is required—I’ll explain the key concepts as we go.

What You’ll Need

• Three computers (or VMs): Start with at least 8GB RAM and 100GB storage per machine, plus a virtualization-capable CPU (most modern ones work). These specs are a baseline—actual RAM and storage depend on how many VMs you want to host (e.g., more VMs need more resources).

• Proxmox VE: Free and open-source. Grab the ISO from proxmox.com.

• Network connection: All three must be on the same network and be able to ping each other.

• A web browser: For Proxmox’s web interface.

• 30–60 minutes: Depending on your setup pace.

Why Proxmox and Clustering?

Proxmox VE is a free, open-source virtualization platform built on Debian Linux. It uses KVM for VMs (fully virtualized systems) and LXC for containers (lightweight app environments), all managed via a slick web interface.

Clustering means linking multiple Proxmox machines—called nodes—so they act as one system. Think of it like a team: each node shares the workload, and you control them from a single dashboard. This setup lets you move (migrate) VMs between nodes, boost reliability, and experiment with high availability (HA)—where VMs auto-restart (on healthy node) if a node fails.

Plus, Proxmox offers a handy replication feature: it can sync VM data between nodes automatically, keeping backups ready if something goes wrong.

It’s a must-have skill for DevOps, app testing, or IT tinkering.

2 Nodes vs. 3 Nodes: Which Should You Choose?

Before we build your 3-node cluster, let’s explore your options. Clustering can start with 2 nodes or go to 3 (or more). Here’s why you might pick one over the other:

• 2-Node Cluster:

  • Pros: Easier setup with just two machines. Great for learning basics or small projects. Uses less hardware.

  • Cons: No quorum—a voting majority to keep the cluster running if a node fails—so HA isn’t reliable. You’d need an extra trick (like a quorum device) to avoid stalling.

  • Best For: Learning, Testing clustering, or limited resources.

• 3-Node Cluster:

  • Pros: Built-in quorum—two out of three nodes keep things going if one crashes. Ideal for HA practice. More stable and scalable.

  • Cons: Needs an extra machine and a bit more setup time.

  • Best For: Serious learners or small production setups.

We’ll go with 3 nodes—it’s the sweet spot for stability and real-world skills.

Step 1: Install Proxmox VE on All Three Machines

First, download the Proxmox VE ISO from proxmox.com. Make a bootable USB with Rufus (Windows), dd (Linux/macOS), or Raspberry Pi Imager (available for all platforms).

For dd, use this command (replace placeholders with your ISO and USB device):

sudo dd if=proxmox-ve.iso of=/dev/sdX bs=1M status=progress oflag=sync

Boot each machine from the USB and follow the installer. Stick with the default partitioning scheme (it uses EXT4 filesystem) and set static IPs and hostnames as follows (or you can use your own IPs knowing your router’s IP range):

• Node 1: 172.20.1.101 [hostname: node01.local]

• Node 2: 172.20.1.102 [hostname: node02.local]

• Node 3: 172.20.1.103 [hostname: node03.local]

After installation, each node displays its IP on the console (for example, https://172.20.1.101:8006). Test it by opening a browser, visiting each IP, and logging in with root and your password. You’ll see the Proxmox dashboard.

Step 2: Prepare Your Nodes

Now, let’s get your nodes ready to talk to each other—a crucial step for clustering. Without this, they won’t recognize each other properly.

Update /etc/hosts on all three nodes to map IPs to hostnames (since we’re not using a DNS server). Open the file with:

nano /etc/hosts

Add these lines (IPs and hostnames) on each node:

172.20.1.101 node01.local node01
172.20.1.102 node02.local node02
172.20.1.103 node03.local node03

Save and exit (Ctrl+O, Enter, Ctrl+X). This ensures nodes can resolve each other’s names (for example, node01 pings node02.local).

Next, check connectivity. From Node 1’s console (or SSH), ping the others:

ping 172.20.1.102

ping 172.20.1.103

Repeat from Node 2 and Node 3. If pings fail, check your network or firewall.

Finally, sync their clocks—clusters need precise time to coordinate. On each node, run:

ntpdate pool.ntp.org

All three nodes are now primed for clustering.

Step 3: Create the Cluster on Node 1

Let’s set up the cluster starting with Node 1. Log into its web interface at https://172.20.1.101:8006. On the left sidebar, click Datacenter, then Cluster. Hit the Create Cluster button, and a dialog pops up. Name your cluster—let’s call it MyCluster and click Create. A task window will appear, showing the process. Wait a few seconds until you see “TASK OK”—that means your cluster is live and Node 1 is its first member. Now we can add the other nodes!

Step 4: Join Node 2 and Node 3 to the Cluster

With the cluster created, let’s bring in Node 2 and Node 3. On Node 1’s cluster page, click Join Information, then Copy Information—this copies a key you’ll need.

Open Node 2’s web interface (https://172.20.1.102:8006), go to Datacenter > Cluster > Join Cluster, paste the key into the Information field, enter Node 1’s root password, and click Join MyCluster.

Repeat this process on Node 3’s interface (https://172.20.1.103:8006). Refresh Node 1’s dashboard—under Datacenter, you’ll see all three nodes with green checkmarks.

Your 3-node cluster is up!

Step 5: Test Your Cluster

Let’s verify it works by creating and moving a test VM. On Node 1, click Create VM, name it TestVM, skip the ISO, and finish with defaults (no disk content needed). Hit the Start button to boot it up.

Now, let’s migrate it around—migration means moving the VM from one node to another to test your cluster’s flexibility. Right-click TestVM, select Migrate, choose Node 2, and click Migrate. The VM stops briefly, copies to Node 2, and restarts (normal without shared storage).

Repeat this, migrating it from Node 2 to Node 3. If it hops between nodes successfully, your cluster’s rocking! With three nodes, you’ve got quorum—try shutting down Node 3 to see the others stay active.

What’s Next?

You’ve built a 3-node Proxmox cluster for free—congrats! Take it further with:

• Shared storage: Add NFS or a spare drive for live VM migration (no stopping/shutdown needed).

• High Availability: Enable HA—VMs auto-restart on a healthy node if one fails.

• VM Replication: Configure Replication—Sync VM data between nodes automatically, keeping backups ready if something goes wrong.

• Scale up: Add more nodes or try LXC containers.

Check your cluster’s health anytime (from console) with:

pvecm status

Wrapping Up

You’ve just set up a 3-node Proxmox cluster at no cost. It’s a playground for virtualization, DevOps practice, or even hosting small projects. Share your thoughts with me – I’d love to hear how you liked it.

There are three different approaches to machine learning, depending on the data you have. You can go with supervised learning, semi-supervised learning, or unsupervised learning.

In supervised learning you have labeled data, so you have outputs that you know for sure are the correct values for your inputs. That's like knowing car prices based on features like make, model, style, drivetrain, and other attributes.

With semi-supervised learning, you have a large data set where some of the data is labeled but most of it isn't.

This covers a large amount of real world data because it can be expensive to get an expert to label every data point. You can work around this by using a combination of supervised and unsupervised learning.

Unsupervised learning means you have a data set that is completely unlabeled. You don’t know if there are any patterns hidden in the data, so you leave it to the algorithm to find anything it can.

That's where clustering algorithms come in. It's one of the methods you can use in an unsupervised learning problem.

What are clustering algorithms?

Clustering is an unsupervised machine learning task. You might also hear this referred to as cluster analysis because of the way this method works.

Using a clustering algorithm means you're going to give the algorithm a lot of input data with no labels and let it find any groupings in the data it can.

Those groupings are called clusters. A cluster is a group of data points that are similar to each other based on their relation to surrounding data points. Clustering is used for things like feature engineering or pattern discovery.

When you're starting with data you know nothing about, clustering might be a good place to get some insight.

Types of clustering algorithms

There are different types of clustering algorithms that handle all kinds of unique data.

Density-based

In density-based clustering, data is grouped by areas of high concentrations of data points surrounded by areas of low concentrations of data points. Basically the algorithm finds the places that are dense with data points and calls those clusters.

The great thing about this is that the clusters can be any shape. You aren't constrained to expected conditions.

The clustering algorithms under this type don't try to assign outliers to clusters, so they get ignored.

Distribution-based

With a distribution-based clustering approach, all of the data points are considered parts of a cluster based on the probability that they belong to a given cluster.

It works like this: there is a center-point, and as the distance of a data point from the center increases, the probability of it being a part of that cluster decreases.

If you aren't sure of how the distribution in your data might be, you should consider a different type of algorithm.

Centroid-based

Centroid-based clustering is the one you probably hear about the most. It's a little sensitive to the initial parameters you give it, but it's fast and efficient.

These types of algorithms separate data points based on multiple centroids in the data. Each data point is assigned to a cluster based on its squared distance from the centroid. This is the most commonly used type of clustering.

Hierarchical-based

Hierarchical-based clustering is typically used on hierarchical data, like you would get from a company database or taxonomies. It builds a tree of clusters so everything is organized from the top-down.

This is more restrictive than the other clustering types, but it's perfect for specific kinds of data sets.

When to use clustering

When you have a set of unlabeled data, it's very likely that you'll be using some kind of unsupervised learning algorithm.

There are a lot of different unsupervised learning techniques, like neural networks, reinforcement learning, and clustering. The specific type of algorithm you want to use is going to depend on what your data looks like.

You might want to use clustering when you're trying to do anomaly detection to try and find outliers in your data. It helps by finding those groups of clusters and showing the boundaries that would determine whether a data point is an outlier or not.

If you aren't sure of what features to use for your machine learning model, clustering discovers patterns you can use to figure out what stands out in the data.

Clustering is especially useful for exploring data you know nothing about. It might take some time to figure out which type of clustering algorithm works the best, but when you do, you'll get invaluable insight on your data. You might find connections you never would have thought of.

Some real world applications of clustering include fraud detection in insurance, categorizing books in a library, and customer segmentation in marketing. It can also be used in larger problems, like earthquake analysis or city planning.

The Top 8 Clustering Algorithms

Now that you have some background on how clustering algorithms work and the different types available, we can talk about the actual algorithms you'll commonly see in practice.

We'll implement these algorithms on an example data set from the sklearn library in Python.

We'll be using the _makeclassification data set from the sklearn library to demonstrate how different clustering algorithms aren't fit for all clustering problems.

You can find the code for all of the following example here.

K-means clustering algorithm

K-means clustering is the most commonly used clustering algorithm. It's a centroid-based algorithm and the simplest unsupervised learning algorithm.

This algorithm tries to minimize the variance of data points within a cluster. It's also how most people are introduced to unsupervised machine learning.

K-means is best used on smaller data sets because it iterates over all of the data points. That means it'll take more time to classify data points if there are a large amount of them in the data set.

Since this is how k-means clusters data points, it doesn't scale well.

Implementation:

from numpy import unique
from numpy import where
from matplotlib import pyplot
from sklearn.datasets import make_classification
from sklearn.cluster import KMeans

# initialize the data set we'll work with
training_data, _ = make_classification(
    n_samples=1000,
    n_features=2,
    n_informative=2,
    n_redundant=0,
    n_clusters_per_class=1,
    random_state=4
)

# define the model
kmeans_model = KMeans(n_clusters=2)

# assign each data point to a cluster
dbscan_result = dbscan_model.fit_predict(training_data)

# get all of the unique clusters
dbscan_clusters = unique(dbscan_result)

# plot the DBSCAN clusters
for dbscan_cluster in dbscan_clusters:
    # get data points that fall in this cluster
    index = where(dbscan_result == dbscan_clusters)
    # make the plot
    pyplot.scatter(training_data[index, 0], training_data[index, 1])

# show the DBSCAN plot
pyplot.show()

DBSCAN clustering algorithm

DBSCAN stands for density-based spatial clustering of applications with noise. It's a density-based clustering algorithm, unlike k-means.

This is a good algorithm for finding outliners in a data set. It finds arbitrarily shaped clusters based on the density of data points in different regions. It separates regions by areas of low-density so that it can detect outliers between the high-density clusters.

This algorithm is better than k-means when it comes to working with oddly shaped data.

DBSCAN uses two parameters to determine how clusters are defined: minPts (the minimum number of data points that need to be clustered together for an area to be considered high-density) and eps (the distance used to determine if a data point is in the same area as other data points).

Choosing the right initial parameters is critical for this algorithm to work.

Implementation:

from numpy import unique
from numpy import where
from matplotlib import pyplot
from sklearn.datasets import make_classification
from sklearn.cluster import DBSCAN

# initialize the data set we'll work with
training_data, _ = make_classification(
    n_samples=1000,
    n_features=2,
    n_informative=2,
    n_redundant=0,
    n_clusters_per_class=1,
    random_state=4
)

# define the model
dbscan_model = DBSCAN(eps=0.25, min_samples=9)

# train the model
dbscan_model.fit(training_data)

# assign each data point to a cluster
dbscan_result = dbscan_model.predict(training_data)

# get all of the unique clusters
dbscan_cluster = unique(dbscan_result)

# plot the DBSCAN clusters
for dbscan_cluster in dbscan_clusters:
    # get data points that fall in this cluster
    index = where(dbscan_result == dbscan_clusters)
    # make the plot
    pyplot.scatter(training_data[index, 0], training_data[index, 1])

# show the DBSCAN plot
pyplot.show()

Gaussian Mixture Model algorithm

One of the problems with k-means is that the data needs to follow a circular format. The way k-means calculates the distance between data points has to do with a circular path, so non-circular data isn't clustered correctly.

This is an issue that Gaussian mixture models fix. You don’t need circular shaped data for it to work well.

The Gaussian mixture model uses multiple Gaussian distributions to fit arbitrarily shaped data.

There are several single Gaussian models that act as hidden layers in this hybrid model. So the model calculates the probability that a data point belongs to a specific Gaussian distribution and that's the cluster it will fall under.

Implementation:

from numpy import unique
from numpy import where
from matplotlib import pyplot
from sklearn.datasets import make_classification
from sklearn.mixture import GaussianMixture

# initialize the data set we'll work with
training_data, _ = make_classification(
    n_samples=1000,
    n_features=2,
    n_informative=2,
    n_redundant=0,
    n_clusters_per_class=1,
    random_state=4
)

# define the model
gaussian_model = GaussianMixture(n_components=2)

# train the model
gaussian_model.fit(training_data)

# assign each data point to a cluster
gaussian_result = gaussian_model.predict(training_data)

# get all of the unique clusters
gaussian_clusters = unique(gaussian_result)

# plot Gaussian Mixture the clusters
for gaussian_cluster in gaussian_clusters:
    # get data points that fall in this cluster
    index = where(gaussian_result == gaussian_clusters)
    # make the plot
    pyplot.scatter(training_data[index, 0], training_data[index, 1])

# show the Gaussian Mixture plot
pyplot.show()

BIRCH algorithm

The Balance Iterative Reducing and Clustering using Hierarchies (BIRCH) algorithm works better on large data sets than the k-means algorithm.

It breaks the data into little summaries that are clustered instead of the original data points. The summaries hold as much distribution information about the data points as possible.

This algorithm is commonly used with other clustering algorithm because the other clustering techniques can be used on the summaries generated by BIRCH.

The main downside of the BIRCH algorithm is that it only works on numeric data values. You can't use this for categorical values unless you do some data transformations.

Implementation:

from numpy import unique
from numpy import where
from matplotlib import pyplot
from sklearn.datasets import make_classification
from sklearn.cluster import Birch

# initialize the data set we'll work with
training_data, _ = make_classification(
    n_samples=1000,
    n_features=2,
    n_informative=2,
    n_redundant=0,
    n_clusters_per_class=1,
    random_state=4
)

# define the model
birch_model = Birch(threshold=0.03, n_clusters=2)

# train the model
birch_model.fit(training_data)

# assign each data point to a cluster
birch_result = birch_model.predict(training_data)

# get all of the unique clusters
birch_clusters = unique(birch_result)

# plot the BIRCH clusters
for birch_cluster in birch_clusters:
    # get data points that fall in this cluster
    index = where(birch_result == birch_clusters)
    # make the plot
    pyplot.scatter(training_data[index, 0], training_data[index, 1])

# show the BIRCH plot
pyplot.show()

Affinity Propagation clustering algorithm

This clustering algorithm is completely different from the others in the way that it clusters data.

Each data point communicates with all of the other data points to let each other know how similar they are and that starts to reveal the clusters in the data. You don't have to tell this algorithm how many clusters to expect in the initialization parameters.

As messages are sent between data points, sets of data called exemplars are found and they represent the clusters.

An exemplar is found after the data points have passed messages to each other and form a consensus on what data point best represents a cluster.

When you aren't sure how many clusters to expect, like in a computer vision problem, this is a great algorithm to start with.

Implementation:

from numpy import unique
from numpy import where
from matplotlib import pyplot
from sklearn.datasets import make_classification
from sklearn.cluster import AffinityPropagation

# initialize the data set we'll work with
training_data, _ = make_classification(
    n_samples=1000,
    n_features=2,
    n_informative=2,
    n_redundant=0,
    n_clusters_per_class=1,
    random_state=4
)

# define the model
model = AffinityPropagation(damping=0.7)

# train the model
model.fit(training_data)

# assign each data point to a cluster
result = model.predict(training_data)

# get all of the unique clusters
clusters = unique(result)

# plot the clusters
for cluster in clusters:
    # get data points that fall in this cluster
    index = where(result == cluster)
    # make the plot
    pyplot.scatter(training_data[index, 0], training_data[index, 1])

# show the plot
pyplot.show()

Mean-Shift clustering algorithm

This is another algorithm that is particularly useful for handling images and computer vision processing.

Mean-shift is similar to the BIRCH algorithm because it also finds clusters without an initial number of clusters being set.

This is a hierarchical clustering algorithm, but the downside is that it doesn't scale well when working with large data sets.

It works by iterating over all of the data points and shifts them towards the mode. The mode in this context is the high density area of data points in a region.

That's why you might hear this algorithm referred to as the mode-seeking algorithm. It will go through this iterative process with each data point and move them closer to where other data points are until all data points have been assigned to a cluster.

Implementation:

from numpy import unique
from numpy import where
from matplotlib import pyplot
from sklearn.datasets import make_classification
from sklearn.cluster import MeanShift

# initialize the data set we'll work with
training_data, _ = make_classification(
    n_samples=1000,
    n_features=2,
    n_informative=2,
    n_redundant=0,
    n_clusters_per_class=1,
    random_state=4
)

# define the model
mean_model = MeanShift()

# assign each data point to a cluster
mean_result = mean_model.fit_predict(training_data)

# get all of the unique clusters
mean_clusters = unique(mean_result)

# plot Mean-Shift the clusters
for mean_cluster in mean_clusters:
    # get data points that fall in this cluster
    index = where(mean_result == mean_cluster)
    # make the plot
    pyplot.scatter(training_data[index, 0], training_data[index, 1])

# show the Mean-Shift plot
pyplot.show()

OPTICS algorithm

OPTICS stands for Ordering Points to Identify the Clustering Structure. It's a density-based algorithm similar to DBSCAN, but it's better because it can find meaningful clusters in data that varies in density. It does this by ordering the data points so that the closest points are neighbors in the ordering.

This makes it easier to detect different density clusters. The OPTICS algorithm only processes each data point once, similar to DBSCAN (although it runs slower than DBSCAN). There's also a special distance stored for each data point that indicates a point belongs to a specific cluster.

Implementation:

from numpy import unique
from numpy import where
from matplotlib import pyplot
from sklearn.datasets import make_classification
from sklearn.cluster import OPTICS

# initialize the data set we'll work with
training_data, _ = make_classification(
    n_samples=1000,
    n_features=2,
    n_informative=2,
    n_redundant=0,
    n_clusters_per_class=1,
    random_state=4
)

# define the model
optics_model = OPTICS(eps=0.75, min_samples=10)

# assign each data point to a cluster
optics_result = optics_model.fit_predict(training_data)

# get all of the unique clusters
optics_clusters = unique(optics_clusters)

# plot OPTICS the clusters
for optics_cluster in optics_clusters:
    # get data points that fall in this cluster
    index = where(optics_result == optics_clusters)
    # make the plot
    pyplot.scatter(training_data[index, 0], training_data[index, 1])

# show the OPTICS plot
pyplot.show()

Agglomerative Hierarchy clustering algorithm

This is the most common type of hierarchical clustering algorithm. It's used to group objects in clusters based on how similar they are to each other.

This is a form of bottom-up clustering, where each data point is assigned to its own cluster. Then those clusters get joined together.

At each iteration, similar clusters are merged until all of the data points are part of one big root cluster.

Agglomerative clustering is best at finding small clusters. The end result looks like a dendrogram so that you can easily visualize the clusters when the algorithm finishes.

Implementation:

from numpy import unique
from numpy import where
from matplotlib import pyplot
from sklearn.datasets import make_classification
from sklearn.cluster import AgglomerativeClustering

# initialize the data set we'll work with
training_data, _ = make_classification(
    n_samples=1000,
    n_features=2,
    n_informative=2,
    n_redundant=0,
    n_clusters_per_class=1,
    random_state=4
)

# define the model
agglomerative_model = AgglomerativeClustering(n_clusters=2)

# assign each data point to a cluster
agglomerative_result = agglomerative_model.fit_predict(training_data)

# get all of the unique clusters
agglomerative_clusters = unique(agglomerative_result)

# plot the clusters
for agglomerative_cluster in agglomerative_clusters:
    # get data points that fall in this cluster
    index = where(agglomerative_result == agglomerative_clusters)
    # make the plot
    pyplot.scatter(training_data[index, 0], training_data[index, 1])

# show the Agglomerative Hierarchy plot
pyplot.show()

Other types of clustering algorithms

We've covered eight of the top clustering algorithms, but there are plenty more than that available. There are some very specifically tuned clustering algorithms that quickly and precisely handle your data. Here are a few of the others that might be of interest to you.

There's another hierarchical algorithm that's the opposite of the agglomerative approach. It starts with a top-down clustering strategy. So it will start with one large root cluster and break out the individual clusters from there.

This is known as the Divisive Hierarchical clustering algorithm. There's research that shows this is creates more accurate hierarchies than agglomerative clustering, but it's way more complex.

Mini-Batch K-means is similar to K-means, except that it uses small random chunks of data of a fixed size so they can be stored in memory. This helps it run faster than K-means so it converges to a solution in less time.

The drawback to this algorithm is that the speed boost will cost you some cluster quality.

The last algorithm we'll briefly cover is Spectral Clustering. This algorithm is completely different from the others we've looked at.

It works by taking advantage of graph theory. This algorithm doesn't make any initial guesses about the clusters that are in the data set. It treats data points like nodes in a graph and clusters are found based on communities of nodes that have connecting edges.

Other thoughts

Watch out for scaling issues with the clustering algorithms. Your data set could have millions of data points, and since clustering algorithms work by calculating the similarities between all pairs of data points, you might end up with an algorithm that doesn’t scale well.

Conclusion

Clustering algorithms are a great way to learn new things from old data. Sometimes you'll be surprised by the resulting clusters you get and it might help you make sense of a problem.

One of the coolest things about using clustering for unsupervised learning is that you can use the results in a supervised learning problem.

The clusters could be your new features that you use on a completely different data set! You can use clustering on just about any unsupervised machine learning problem, but make sure that you know how to analyze the results for accuracy.

Take a look at the image below. It’s a collection of bugs and creepy-crawlies of different shapes and sizes. Take a moment to categorize them by similarity into a number of groups.

This isn’t a trick question. Start with grouping the spiders together.

Images via Google Image Search, labelled for reuse

Done? While there’s not necessarily a “correct” answer here, it’s most likely you split the bugs into four clusters. The spiders in one cluster, the pair of snails in another, the butterflies and moth into one, and the trio of wasps and bees into one more.

That wasn’t too bad, was it? You could probably do the same with twice as many bugs, right? If you had a bit of time to spare — or a passion for entomology — you could probably even do the same with a hundred bugs.

For a machine though, grouping ten objects into however many meaningful clusters is no small task, thanks to a mind-bending branch of maths called combinatorics, which tells us that are 115,975 different possible ways you could have grouped those ten insects together.

Had there been twenty bugs, there would have been over fifty trillion possible ways of clustering them.

With a hundred bugs — there’d be many times more solutions than there are particles in the known universe.

How many times more? By my calculation, approximately five hundred million billion billion times more. In fact, there are more than four million billion googol solutions (what’s a googol?).

For just a hundred objects.

Almost all of those solutions would be meaningless — yet from that unimaginable number of possible choices, you pretty quickly found one of the very few that clustered the bugs in a useful way.

Us humans take it for granted how good we are categorizing and making sense of large volumes of data pretty quickly. Whether it’s a paragraph of text, or images on a screen, or a sequence of objects — humans are generally fairly efficient at making sense of whatever data the world throws at us.

Given that a key aspect of developing A.I. and machine learning is getting machines to quickly make sense of large sets of input data, what shortcuts are there available?

Here, you can read about three clustering algorithms that machines can use to quickly make sense of large datasets. This is by no means an exhaustive list — there are other algorithms out there — but they represent a good place to start!

You’ll find for each a quick summary of when you might use them, a brief overview of how they work, and a more detailed, step-by-step worked example. I believe it helps to understand an algorithm by actually carrying out yourself.

If you’re really keen, you’ll find the best way to do this is with pen and paper. Go ahead — nobody will judge!

Three suspiciously neat clusters, with K = 3

K-means clustering

Use when...

…you have an idea of how many groups you’re expecting to find a priori.

How it works

The algorithm randomly assigns each observation into one of k categories, then calculates the mean of each category. Next, it reassigns each observation to the category with the closest mean before recalculating the means. This step repeats over and over until no more reassignments are necessary.

Worked Example

Take a group of 12 football (or ‘soccer’) players who have each scored a certain number of goals this season (say in the range 3–30). Let’s divide them into separate clusters — say three.

Step 1 requires us to randomly split the players into three groups and calculate the means of each.

Group 1
  Player A (5 goals),
  Player B (20 goals),
  Player C (11 goals)
Group Mean = (5 + 20 + 11) / 3 = 12 goals

Group 2
  Player D (5 goals),
  Player E (3 goals),
  Player F (19 goals)
Group Mean = 9 goals

Group 3
  Player G (30 goals),
  Player H (3 goals),
  Player I (15 goals)
Group Mean = 16 goals

Step 2: For each player, reassign them to the group with the closest mean. E.g., Player A (5 goals) is assigned to Group 2 (mean = 9). Then recalculate the group means.

Group 1 (Old Mean = 12 goals)
  Player C (11 goals)
New Mean = 11 goals

Group 2 (Old Mean = 9 goals)
  Player A (5 goals),
  Player D (5 goals),
  Player E (3 goals),
  Player H (3 goals)
New Mean = 4 goals

Group 3 (Old Mean = 16 goals)
  Player G (30 goals),
  Player I (15 goals),
  Player B (20 goals),
  Player F (19 goals)
New Mean = 21 goals

Repeat Step 2 over and over until the group means no longer change. For this somewhat contrived example, this happens on the next iteration. Stop! You have now formed three clusters from the dataset!

Group 1 (Old Mean = 11 goals)
  Player C (11 goals),
  Player I (15 goals)
Final Mean = 13 goals

Group 2 (Old Mean = 4 goals)
  Player A (5 goals),
  Player D (5 goals),
  Player E (3 goals),
  Player H (3 goals)
Final Mean = 4 goals

Group 3 (Old Mean = 21 goals)
  Player G (30 goals),
  Player B (20 goals),
  Player F (19 goals)
Final Mean = 23 goals

With this example, the clusters could correspond to the players’ positions on the field — such as defenders, midfielders and attackers.

K-means works here because we could have reasonably expected the data to fall naturally into these three categories.

In this way, given data on a range of performance statistics, a machine could do a reasonable job of estimating the positions of players from any team sport — useful for sports analytics, and indeed any other purpose where classification of a dataset into predefined groups can provide relevant insights.

Finer details

There are several variations on the algorithm described here. The initial method of ‘seeding’ the clusters can be done in one of several ways.

Here, we randomly assigned every player into a group, then calculated the group means. This causes the initial group means to tend towards being similar to one another, which ensures greater repeatability.

An alternative is to seed the clusters with just one player each, then start assigning players to the nearest cluster. The returned clusters are more sensitive to the initial seeding step, reducing repeatability in highly variable datasets.

However, this approach may reduce the number of iterations required to complete the algorithm, as the groups will take less time to diverge.

An obvious limitation to K-means clustering is that you have to provide a priori assumptions about how many clusters you’re expecting to find.

There are methods to assess the fit of a particular set of clusters. For example, the Within-Cluster Sum-of-Squares is a measure of the variance within each cluster.

The ‘better’ the clusters, the lower the overall WCSS.

Hierarchical clustering

Use when...

…you wish to uncover the underlying relationships between your observations.

How it works

A distance matrix is computed, where the value of cell (i, j) is a distance metric between observations i and j.

Then, pair the closest two observations and calculate their average. Form a new distance matrix, merging the paired observations into a single object.

From this distance matrix, pair up the closest two observations and calculate their average. Repeat until all observations are grouped together.

Worked example

Here’s a super-simplified dataset about a selection of whale and dolphin species. As a trained biologist, I can assure you we normally use much more detailed datasets for things like reconstructing phylogeny.

For now though, we’ll just look at the typical body lengths for these six species. We’ll be using just two repeated steps.

Species          Initials  Length(m)
Bottlenose Dolphin     BD        3.0
Risso's Dolphin        RD        3.6
Pilot Whale            PW        6.5
Killer Whale           KW        7.5
Humpback Whale         HW       15.0
Fin Whale              FW       20.0

Step 1: compute a distance matrix between each species. Here, we’ll use the Euclidean distance — how far apart are the data points?

Read this exactly as you would a distance chart in a road atlas. The difference in length between any pair of species can be looked up by reading the value at the intersection of the relevant row and column.

    BD   RD   PW   KW   HW
RD  0.6                    
PW  3.5  2.9               
KW  4.5  3.9  1.0          
HW 12.0 11.4  8.5  7.5     
FW 17.0 16.4 13.5 12.5  5.0

Step 2: Pair up the two closest species. Here, this will be the Bottlenose & Risso’s Dolphins, with an average length of 3.3m.

Repeat Step 1 by recalculating the distance matrix, but this time merge the Bottlenose & Risso’s Dolphins into a single object with length 3.3m.

    [BD, RD]   PW   KW   HW
PW       3.2               
KW       4.2   1.0          
HW      11.7   8.5  7.5     
FW      16.7  13.5 12.5  5.0

Next, repeat Step 2 with this new distance matrix. Here, the smallest distance is between the Pilot & Killer Whales, so we pair them up and take their average — which gives us 7.0m.

Then, we repeat Step 1 — recalculate the distance matrix, but now we’ve merged the Pilot & Killer Whales into a single object of length 7.0m.

         [BD, RD] [PW, KW]   HW
 [PW, KW]      3.7              
 HW           11.7      8.0     
 FW           16.7     13.0   5.0

Next, repeat Step 2 with this distance matrix. The smallest distance (3.7m) is between the two merged objects — so now merge them into an even bigger object, and take the average (which is 5.2m).

Then, repeat Step 1 and compute a new distance matrix, having merged the Bottlenose & Risso’s Dolphins with the Pilot & Killer Whales.

   [[BD, RD] , [PW, KW]]    HW
HW                   9.8    
FW                  14.8   5.0

Next, repeat Step 2. The smallest distance (5.0m) is between the Humpback & Fin Whales, so merge them into a single object, and take the average (17.5m).

Then, it’s back to Step 1 — compute the distance matrix, having merged the Humpback & Fin Whales.

         [[BD, RD] , [PW, KW]]
[HW, FW]                  12.3

Finally, repeat Step 2 — there is only one distance (12.3m) in this matrix, so pair everything into one big object. Now you can stop! Look at the final merged object:

[[[BD, RD],[PW, KW]],[HW, FW]]

It has a nested structure (think JSON), which allows it to be drawn up as a tree-like graph, or 'dendrogram'.

It reads in much the same way a family tree might. The nearer two observations are on the tree, the more similar or closely-related they are taken to be.

_A no-frills dendrogram generated at [R-Fiddle.org](http://www.r-fiddle.org/#" rel="noopener" target="blank" title=")

The structure of the dendrogram gives insight into how the dataset is structured.

In this example, there are two main branches, with Humpback Whale and Fin Whale on one side, and the Bottlenose Dolphin/Risso’s Dolphin and Pilot Whale/Killer Whale on the other.

In evolutionary biology, much larger datasets with many more specimens and measurements are used in this way to infer taxonomic relationships between them.

Outside of biology, hierarchical clustering has applications in data mining and machine learning contexts.

The cool thing is that this approach requires no assumptions about the number of clusters you’re looking for.

You can split the returned dendrogram into clusters by “cutting” the tree at a given height. This height can be chosen in a number of ways, depending on the resolution at which you wish to cluster the data.

For instance, looking at the dendrogram above, if we draw a horizontal line at height = 10, we’d intersect the two main branches, splitting the dendrogram into two sub-graphs. If we cut at height = 2, we’d be splitting the dendrogram into three clusters.

Finer details

There are essentially three aspects in which hierarchical clustering algorithms can vary to the one given here.

Most fundamental is the approach — here, we have used an agglomerative process, whereby we start with individual data points and iteratively cluster them together until we’re left with one large cluster.

An alternative (but more computationally intensive) approach is to start with one giant cluster, and then proceed to divide the data into smaller and smaller clusters until you’re left with isolated data points.

There are also a range of methods that can be used to calculate the distance matrices. For many purposes, the Euclidean distance (think Pythagoras’ Theorem) will suffice, but there are alternatives that may be more applicable in some circumstances.

Finally, the linkage criterion can also vary. Clusters are linked according to how close they are to one another, but the way in which we define ‘close’ is flexible.

In the example above, we measured the distances between the means (or ‘centroids’) of each group and paired up the nearest groups. However, you may want to use a different definition.

For example, each cluster is made up of several discrete points. You could define the distance between two clusters to be the minimum (or maximum) distance between any of their points — as illustrated in the figure below.

There are still other ways of defining the linkage criterion, which may be suitable in different contexts.

Red/Blue: centroid linkage; Red/Green: minimum linkage; Green/Blue: maximum linkage

Graph Community Detection

Use when

…you have data that can be represented as a network, or ‘graph’.

How it works

A graph community is very generally defined as a subset of vertices which are more connected to each other than with the rest of the network.

Various algorithms exist to identify communities, based upon more specific definitions. Algorithms include, but are not limited to: Edge Betweenness, Modularity-Maximsation, Walktrap, Clique Percolation, Leading Eigenvector…

Worked example

Graph theory, or the mathematical study of networks, is a fascinating branch of mathematics that lets us model complex systems as an abstract collection of ‘dots’ (or vertices) connected by ‘lines’ (or edges).

Perhaps the most intuitive case-studies are social networks.

Here, the vertices represent people, and edges connect vertices who are friends/followers. However, any system can be modelled as a network if you can justify a method to meaningfully connect different components.

Among the more innovative applications of graph theory to clustering include feature extraction from image data, and analysing gene regulatory networks.

As an entry-level example, take a look at this quickly put-together graph. It shows the eight websites I most recently visited, linked according to whether their respective Wikipedia articles link out to one another.

You could assemble this data manually, but for larger-scale projects, it’s much quicker to write a Python script to do the same. Here’s one I wrote earlier.

Graph plotted with ‘igraph’ package for R version 3.3.3

The vertices are colored according to their community membership, and sized according to their centrality. See how Google and Twitter are the most central?

Also, the clusters make pretty good sense in the real-world (always an important performance indicator).

The yellow vertices are generally reference/look-up sites; the blue vertices are all used for online publishing (of articles, tweets, or code); and the red vertices include YouTube, which was of course founded by former PayPal employees. Not bad deductions for a machine.

Aside from being a useful way to visualize large systems, the real power of networks comes from their mathematical analysis. Let’s start by translating our nice picture of the network into a more mathematical format. Below is the adjacency matrix of the network.

         GH Gl  M  P  Q  T  W  Y
GitHub    0  1  0  0  0  1  0  0  
Google    1  0  1  1  1  1  1  1
Medium    0  1  0  0  0  1  0  0
PayPal    0  1  0  0  0  1  0  1
Quora     0  1  0  0  0  1  1  0
Twitter   1  1  1  1  1  0  0  1
Wikipedia 0  1  0  0  1  0  0  0
YouTube   0  1  0  1  0  1  0  0

The value at the intersection of each row and column records whether there is an edge between that pair of vertices.

For instance, there is an edge between Medium and Twitter (surprise, surprise!), so the value where their rows/columns intersect is 1. Similarly, there is no edge between Medium and PayPal, so the intersection of their rows/columns returns 0.

Encoded within the adjacency matrix are all the properties of this network — it gives us the key to start unlocking all manner of valuable insights.

For a start, summing any column (or row) gives you the degree of each vertex — i.e., how many others it is connected to. This is commonly denoted with the letter k.

Likewise, summing the degrees of every vertex and dividing by two gives you L, the number of edges (or ‘links’) in the network. The number of rows/columns gives us N, the number of vertices (or ‘nodes’) in the network.

Knowing just k, L, N and the value of each cell in the adjacency matrix A lets us calculate the modularity of any given clustering of the network.

Say we’ve clustered the network into a number of communities. We can use the modularity score to assess the ‘quality’ of this clustering.

A higher score will show we’ve split the network into ‘accurate’ communities, whereas a low score suggests our clusters are more random than insightful. The image below illustrates this.

Modularity serves as a measure of the ‘quality’ of a partition.

Modularity can be calculated using the formula below:

That’s a fair amount of math, but we can break it down bit by bit and it’ll make more sense.

M is of course what we’re calculating — modularity.

1/2L tells us to divide everything that follows by 2L, i.e., twice the number of edges in the network. So far, so good.

The Σ symbol tells us we’re summing up everything to the right, and lets us iterate over every row and column in the adjacency matrix A.

For those unfamiliar with sum notation, the i, j = 1 and the N work much like nested for-loops in programming. In Python, you’d write it as follows:

sum = 0
for i in range(1,N):
    for j in range(1,N):
        ans = #stuff with i and j as indices 
    sum += ans

So what is #stuff with i and j in more detail?

Well, the bit in brackets tells us to subtract ( _k_i kj ) / 2L from _Aij.

_Aij is simply the value in the adjacency matrix at row i, column j.

The values of _ki and _kj are the degrees of each vertex — found by adding up the entries in row i and column j respectively. Multiplying these together and dividing by 2L gives us the expected number of edges between vertices i and j if the network were randomly shuffled up.

Overall, the term in the brackets reveals the difference between the network’s real structure and the expected structure it would have if randomly reassembled.

Playing around with the values shows that it returns its highest value when _Aij = 1, and ( _k_i kj ) / 2L is low. This means we see a higher value if there is an ‘unexpected’ edge between vertices i and j.

Finally, we multiply the bracketed term by whatever the last few symbols refer to.

The ?ci,_ cj i_s the fancy-sounding but totally harmless Kronecker-delta function. Here it is, explained in Python:

def kroneckerDelta(ci, cj):
    if ci == cj:
        return 1
    else:
        return 0

kroneckerDelta("A","A")
#returns 1

kroneckerDelta("A","B")
#returns 0

Yes — it really is that simple. The Kronecker-delta function takes two arguments, and returns 1 if they are identical, otherwise, zero.

This means that if vertices i and j have been put in the same cluster, then ?ci,_ cj = 1_. Otherwise, if they are in different clusters, the function returns zero.

As we are multiplying the bracketed term by this Kronecker-delta function, we find that for the nested sum Σ, the outcome is highest when there are lots of ‘unexpected’ edges connecting vertices assigned to the same cluster.

As such, modularity is a measure of how well-clustered the graph is into separate communities.

Dividing by 2L bounds the upper value of modularity at 1. Modularity scores near to or below zero indicate the current clustering of the network is really no use. The higher the modularity, the better the clustering of the network into separate communities.

By maximising modularity, we can find the best way of clustering the network.

Notice that we have to pre-define how the graph is clustered to find out how ‘good’ that clustering actually is.

Unfortunately, employing brute force to try out every possible way of clustering the graph to find which has the highest modularity score would be computationally impossible beyond a very limited sample size.

Combinatorics tells us that for a network of just eight vertices, there are 4140 different ways of clustering them. A network twice the size would have over ten billion possible ways of clustering the vertices.

Doubling the network again (to a very modest 32 vertices) would give 128 septillion possible ways, and a network of eighty vertices would be cluster-able in more ways than there are atoms in the observable universe.

Instead, we have to turn to a heuristic method that does a reasonably good job at estimating the clusters that will produce the highest modularity score, without trying out every single possibility.

This is an algorithm called Fast-Greedy Modularity-Maximization, and it’s somewhat analogous to the agglomerative hierarchical clustering algorithm describe above. Instead of merging according to distance, ‘Mod-Max’ merges communities according to changes in modularity.

Here’s how it goes:

Begin by initially assigning every vertex to its own community, and calculating the modularity of the whole network, M.

Step 1 requires that for each community pair linked by at least a single edge, the algorithm calculates the resultant change in modularity ΔM if the two communities were merged into one.

Step 2 then takes the pair of communities that produce the biggest increase in ΔM, which are then merged. Calculate the new modularity M for this clustering, and keep a record of it.

Repeat steps 1 and 2 — each time merging the pair of communities for which doing so produces the biggest gain in ΔM, then recording the new clustering pattern and its associated modularity score M.

Stop when all the vertices are grouped into one giant cluster. Now the algorithm checks the records it kept as it went along, and identifies the clustering pattern that returned the highest value of M. This is the returned community structure.

Finer details

Whew! That was computationally intensive, at least for us humans.

Graph theory is a rich source of computationally challenging, often NP-hard problems — yet it also has incredible potential to provide valuable insights into complex systems and datasets.

Just ask Larry Page, whose eponymous PageRank algorithm — which helped propel Google from start-up to basically world domination in less than a generation — was based entirely in graph theory.

Community detection is a major focus of current research in graph theory, and there are plenty of alternatives to Modularity-Maximization, which while useful, does have some drawbacks.

For a start, its agglomerative approach often sees small, well-defined communities swallowed up into larger ones. This is known as the resolution limit — the algorithm will not find communities below a certain size.

Another challenge is that rather than having one distinct, easy-to-reach global peak, the Mod-Max approach actually tends to produce a wide ‘plateau’ of many similar high modularity scores — making it somewhat difficult to truly identify the absolute maximum score.

Other algorithms use different ways to define and approach community detection.

Edge-Betweenness is a divisive algorithm, starting with all vertices grouped in one giant cluster. It proceeds to iteratively remove the least ‘important’ edges in the network, until all vertices are left isolated. This produces a hierarchical structure, with similar vertices closer together in the hierarchy.

Another algorithm is Clique Percolation, which takes into account possible overlap between graph communities.

Yet another set of algorithms are based on random-walks across the graph, and then there are spectral clustering methods which start delving into the eigendecomposition of the adjacency matrix and other matrices derived therefrom. These ideas are used in feature extraction in, for example, areas such as computer vision.

It’d be well beyond the scope of this article to give each algorithm its own in-depth worked example. Suffice to say that this is an active area of research, providing powerful methods to make sense of data that even a generation ago would have been extremely difficult to process.

Conclusion

Hopefully this article has informed and inspired you to better understand how machines can make sense of data. The future is a rapidly changing place, and many of those changes will be driven by what technology becomes capable of in the next generation or two.

As outlined in the introduction, machine learning is an extraordinarily ambitious field of research, in which massively complex problems require solving in as accurate and as efficient a way possible. Tasks that come naturally to us humans require innovative solutions when taken on by machines.

There’s still plenty of progress to be made, and whoever contributes the next breakthrough idea will no doubt be generously rewarded. Maybe someone reading this article will be behind the next powerful algorithm?

All great ideas have to start somewhere!