Skip to content
Tutorials Center
My learning

Topics

Lesson 64 of 111 ยท Unsupervised Learning

More Clustering Algorithms

Go beyond k-means: mean-shift finds the cluster count itself, k-medoids resists outliers, divisive clustering splits top-down, k-modes handles categories.

K-means, hierarchical clustering, DBSCAN and Gaussian mixtures cover most day-to-day work. But each assumes something: a known number of clusters, numeric features, round blobs, no outliers. This lesson adds four algorithms that relax those assumptions: mean-shift, k-medoids, divisive clustering and k-modes. It also gives you a map of the four families of clustering methods so you can see where each belongs.

A map of clustering families

Family Idea Examples
Centroid-based Each cluster has a center; points join the nearest one k-means, k-medoids, k-modes, fuzzy c-means
Density-based Clusters are dense regions separated by sparse ones DBSCAN, OPTICS, mean-shift
Distribution-based Each cluster is a probability distribution Gaussian mixture models
Connectivity-based Close points join step by step into a tree Agglomerative (bottom-up) and divisive (top-down) hierarchical clustering

Mean-shift: let the data choose the number of clusters

Mean-shift treats the points as samples from a density and climbs to its peaks. Each point starts a small window (a circle of radius bandwidth), moves the window to the mean of the points inside it, and repeats until the window stops moving. Points whose windows end at the same peak form one cluster, and the number of clusters is a result, not an input.

The one setting that matters is the bandwidth: a small window finds many tiny peaks, a large window merges everything. estimate_bandwidth proposes a value from the data.

Python Mean-shift finds three clusters by itself

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A bandwidth near 1.5 gives the three true clusters (an adjusted Rand index of 1.0 means a perfect match). Shrink it and you get dozens of tiny clusters; grow it and the three groups collapse into one. Mean-shift suits low-dimensional data such as image segmentation by color or object tracking. It is slow on large datasets (it is roughly quadratic in the number of points) and a single bandwidth cannot suit clusters of very different sizes.

K-medoids: a center that is a real data point

K-means uses the mean of each cluster as its center, so a few extreme points pull the center away. K-medoids (also called PAM, "partitioning around medoids") uses a medoid instead: the actual data point whose total distance to all other points of the cluster is smallest. It follows the same loop as k-means (assign each point to the nearest center, then update the centers), but the update picks a member rather than averaging.

Two consequences follow. First, a medoid is a real row, so you can show it as a representative example ("a typical customer"). Second, medoids work with any distance, including Manhattan distance or a custom dissimilarity matrix, and they are much less sensitive to outliers. The cost is speed: finding a medoid needs all pairwise distances inside each cluster.

scikit-learn itself has no k-medoids (it lives in the add-on package scikit-learn-extra), but the alternating version is short enough to write by hand.

Python K-medoids against k-means when outliers appear

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the cluster centered near (8, 0). With six outliers to its right, the k-means center drifts from (8.23, 0.03) to (8.90, 0.29), while the medoid does not move at all. The medoid also is an actual row of the data, which a mean never is.

Divisive clustering: split from the top

In agglomerative clustering every point starts alone and the closest clusters are merged. Divisive (top-down) clustering runs the other way: start with one cluster containing everything, then keep splitting. A common practical version is bisecting k-means: pick the cluster with the largest error (sum of squared distances to its center) and split it in two with 2-means, until you have k clusters. Each split is cheap, the result is a hierarchy of nested clusters, and the large clusters are fixed early, which often gives more evenly sized results than plain k-means.

scikit-learn provides BisectingKMeans. The second half of the example below writes the same idea by hand and prints each split.

Python Bisecting k-means and a hand-written divisive loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On well-separated blobs all three methods agree. Divisive clustering is more helpful when you want the whole hierarchy, or when the top-level split matters to you. Its weak point is that a bad early split can never be repaired, because points do not move between branches afterwards.

K-modes: clustering categorical data

K-means needs means, and the mean of "red", "green" and "blue" does not exist. K-modes replaces the two ingredients:

  • The distance becomes the simple matching dissimilarity: the number of attributes in which two rows differ.
  • The center becomes the mode: the most frequent value of each attribute within the cluster.

Everything else is the k-means loop. For mixed data (numbers and categories) the variant k-prototypes combines both distances. The Python package kmodes implements these; the example below writes the core loop by hand so you can see that nothing else is needed. The data has three hidden customer groups, each with its own typical attribute values, plus 15% random noise.

Python K-modes on purely categorical customers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three modes are exactly the three hidden profiles, even though 15% of the entries were replaced by noise: a mode is the majority value, so noise does not move it. As with k-means, results depend on the starting rows, so run several seeds and keep the lowest cost.

Choosing among the algorithms

  • Numeric, roughly round clusters, k known: k-means.
  • Outliers or a need for real representatives, or a non-Euclidean distance: k-medoids.
  • Number of clusters unknown, low-dimensional data: mean-shift (or DBSCAN if you also want noise points).
  • You want a hierarchy and the big structure first: divisive (bisecting k-means); the details first: agglomerative.
  • Overlapping groups with a probabilistic reading: Gaussian mixtures; soft memberships: fuzzy c-means.
  • Categorical attributes: k-modes; mixed attributes: k-prototypes.

Whatever you choose, judge the result with the tools in cluster evaluation, and remember that clusters are a hypothesis to inspect, not a fact.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main setting of mean-shift, and what does it control?

    Mean-shift finds density peaks. A small bandwidth finds many peaks, a large one merges them. The number of clusters is an outcome.
  2. 2. Why is a k-medoids center more robust to outliers than a k-means center?

    The mean is dragged by extreme values; the medoid is the most central actual point and stays where the bulk of the data is.
  3. 3. What is the difference between agglomerative and divisive clustering?

    Agglomerative starts with every point alone and merges. Divisive starts with one big cluster and keeps splitting it.
  4. 4. How does k-modes replace the mean and the Euclidean distance of k-means?

    Categorical values have no mean. Cluster centers are the most common value per attribute, and distance counts the attributes that differ.

Summary

  • Clustering methods fall into centroid, density, distribution and connectivity families.
  • Mean-shift climbs density peaks and finds the number of clusters itself, controlled by the bandwidth.
  • K-medoids uses real points as centers; it resists outliers and works with any distance, but is slower.
  • Divisive clustering splits top-down; bisecting k-means is the practical version.
  • K-modes clusters categorical data with matching dissimilarity and modes (k-prototypes handles mixed data).

Next: the statistics behind many of these methods, in Density Estimation and Maximum Likelihood.