Introduction to Unsupervised Learning

Finding structure in data that has no labels. The setting and why it is harder to judge than supervised learning, the three families of methods (clustering, outlier detection and dimension reduction) as three questions about where data are dense, and all three applied to the wine data with the cultivar hidden, including the effect of scaling, the silhouette worked by hand, a check by resampling, and outliers that a two-dimensional map hides.

The wine data (Aeberhard and Forina, 1992) describe 178 wines by 13 chemical measurements, among them alcohol, flavanoids, color intensity and proline. Each wine was made from one of three grape cultivars, and Introduction to Supervised Learning uses that label to train classifiers that name the cultivar of a new wine. Suppose instead that the label had never been recorded, and only the 13 measurements were available. There is no right answer to learn from, but there are still questions to ask. Do the wines fall into natural groups? Are some wines unlike all the others? Do the 13 measurements really vary in 13 independent ways, or do a few underlying differences account for most of them?

Answering such questions from the inputs alone is unsupervised learning. In this article all three questions are put to the wine data with the cultivar hidden. A clustering method divides the wines into three groups, and when the cultivars are revealed afterwards, 172 of the 178 wines turn out to be in a group dominated by their own cultivar. Two summary variables computed from the measurements carry 55.4% of their variation and draw a map on which the groups are plain to see. And five wines stand out as farther from their neighbors than any others, though on that map they look entirely ordinary. Each of these results depended on choices the data could not make, and seeing which choices, and how to check them without labels, is the main subject here.

The setting

In supervised learning each instance has inputs $x = (x_1, \dots, x_p)$ and an output $y$, and the task is to predict $y$ from $x$. In unsupervised learning there is only $x$: a set of $n$ instances, each described by $p$ features, and no output to predict. James, Witten, Hastie and Tibshirani (2021, ch. 12) describe the goal as discovering interesting things about the measurements: whether there is an informative way to visualize them, and whether there are subgroups among the instances or among the variables. Hastie, Tibshirani and Friedman (2009, §14.1) give a more formal statement. Treat the instances as draws from an unknown probability distribution $\Pr(X)$; supervised learning asks about one aspect of it, the conditional distribution of the output given the inputs, while unsupervised learning asks about $\Pr(X)$ itself, which, they write, it must do "without the help of a supervisor or teacher providing correct answers or degree-of-error for each observation".

That view connects the main tasks, each of which asks something about where $\Pr(X)$ is large and how it is shaped. Hastie et al. (2009, §14.1) describe clustering and dimension reduction in these terms, and outlier detection fits the same picture:

  • Clustering looks for separate regions of high density, groups of instances that are more similar to one another than to instances in other groups.
  • Outlier detection looks for instances in regions of low density, unlike the rest.
  • Dimension reduction asks whether the data lie close to a surface of fewer dimensions than the number of features, so that a few derived variables can describe them. When those derived variables are thought of as unobserved causes of the measured ones, they are called latent variables.

Why it is harder

Supervised learning has a clear measure of success: how well the predictions match outputs that were held back, estimated by a test set or Cross-Validation. Unsupervised learning has no such measure. There is no held-back answer to compare against, so there is no direct way to tell whether a set of clusters or a set of outliers is correct (James et al., 2021, §12.1). Hastie et al. (2009, §14.1) put the consequence bluntly: one must "resort to heuristic arguments" both to motivate the methods and to judge their results, and because effectiveness "is a matter of opinion and cannot be verified directly", the methods have proliferated. Unsupervised learning is therefore most often part of exploratory analysis, and its results are judged by whether they hold up under checking and whether they are useful.

Three families of methods

Clustering

A clustering method partitions the instances into groups, usually without being told what the groups mean. Its basic ingredient is a measure of how similar two instances are, most often the Euclidean distance between their feature vectors. The main kinds differ in what they take a cluster to be:

  • Partitioning methods such as k-means fix the number of clusters $k$ in advance and look for the partition with the smallest spread around each cluster's center. The course wiki's k-means derives the algorithm and proves that it converges, and K-means in Practice covers starting points, choosing $k$ and scaling.
  • Hierarchical methods build a tree of nested clusters by repeatedly merging the closest pair, and leave the number of clusters to be chosen by cutting the tree (Hierarchical Clustering).
  • Density-based methods such as DBSCAN define a cluster as a region where points are crowded together, find clusters of any shape, and leave points in sparse regions unassigned (Detecting Outliers Using DBSCAN).
  • Model-based methods assume the data come from a mixture of simple distributions, one per cluster, and estimate it. A mixture of normal distributions fitted by the expectation-maximization (EM) algorithm assigns each instance a probability of belonging to each cluster instead of a single label; Hastie et al. (2009, §14.3.7) show that when every component is a round normal distribution with the same variance, EM is a "soft" version of k-means, and that as the variance shrinks to zero the probabilities become 0 and 1 and the two methods coincide. EM itself is a general algorithm for fitting models with unobserved variables, not a clustering method in its own right.

The Text Clustering topic of the course wiki applies these ideas to documents, where similarity is measured between word-count vectors.

Outlier detection

An outlier or anomaly is an instance that differs markedly from the others: a fraudulent transaction, a faulty sensor reading, a data entry error, or a genuinely rare case. Detecting outliers without labels means deciding what "differs markedly" means. Simple approaches score each instance by how far it is from its nearest neighbors, so that isolated instances score high; DBSCAN labels as noise the instances that lie in no dense region. Outliers found in this way are relative to a choice of features, scaling and threshold, and an unusual instance is not necessarily an error. The Data Exploration topic's Detecting Outliers covers checks on single variables, which are usually the first step.

Dimension reduction and latent variables

Many datasets have more features than independent sources of variation: measurements that move together because they reflect the same underlying property. Principal component analysis (PCA) replaces the features by a few uncorrelated weighted sums that keep as much of their variance as possible (Principal Component Analysis). Factor analysis models the correlations among the features as the effect of a few unobserved factors, each feature also having a part of its own (Factor Analysis). The course wiki's Latent Semantic Indexing and topic models apply the same ideas to text, finding latent dimensions or topics in the words of documents.

Dimension reduction serves several purposes: drawing high-dimensional data in two or three dimensions, removing redundancy and noise before another method is applied, and, in the latent-variable view, naming the underlying properties.

Three questions put to the wine data

Distances depend on units

Clustering the wines starts with deciding when two wines are similar. The measurements are in different units with very different spreads: proline, in milligrams per liter, has a standard deviation of 314.9, while nonflavanoid phenols have one of 0.124. In the Euclidean distance between two wines, differences in proline swamp everything else, as K-Nearest Neighbors shows in detail. Running k-means with $k = 3$ (20 random starts) on the raw measurements effectively clusters the wines by proline. Standardizing each measurement first, by subtracting its mean and dividing by its standard deviation, gives every measurement an equal say. The two clusterings, compared afterwards with the cultivars (rows are clusters, numbered by their majority cultivar):

Raw measurements Cultivar 1 Cultivar 2 Cultivar 3
cluster 1 46 1 0
cluster 2 0 50 19
other cluster 13 20 29
Standardized measurements Cultivar 1 Cultivar 2 Cultivar 3
cluster 1 59 3 0
cluster 2 0 65 0
cluster 3 0 3 48

On standardized data, 172 of the 178 wines are in the cluster dominated by their own cultivar; the six exceptions are all from cultivar 2. On raw data, one cluster mixes all three cultivars. The adjusted Rand index (ARI), which compares two partitions and is 1 for identical ones and close to 0 for unrelated ones (see Evaluating Clusterings), is 0.897 for the standardized clustering and 0.371 for the raw one. Nothing in the data says which scaling is right; the choice expresses a judgment that each measurement should count equally. Standardizing is the usual default when features are in different units, but if one feature is known to matter more, weighting it more is equally legitimate.

How many groups?

The number three was chosen because the answer was known. Without labels, $k$ must be chosen from the data. The within-cluster sum of squares (WCSS), the quantity k-means minimizes, always falls as $k$ grows, so it can only suggest a value through a bend in its curve (an "elbow" or "knee"; K-means in Practice tries this on news stories). A measure that can fall as well as rise is the silhouette (Rousseeuw, 1987). For an instance $i$ in cluster $A$, let

  • $a(i)$ be the average distance from $i$ to the other members of $A$;
  • $b(i)$ be the average distance from $i$ to the members of the nearest other cluster, the smallest such average over the clusters other than $A$.

The silhouette of $i$ is

$$s(i) = \frac{b(i) - a(i)}{\max\{a(i),\, b(i)\}},$$

which lies between $-1$ and $1$. It is near 1 when $i$ is much closer to its own cluster than to any other, near 0 when it lies between two clusters, and negative when it is on average closer to another cluster than to its own (Rousseeuw, 1987; scikit-learn developers, n.d.). The mean silhouette over all instances summarizes a whole clustering.

For the first wine in the data, in the standardized three-cluster solution, the average distance to the other members of its cluster is $a = 3.148$, and the average distances to the members of the other two clusters are 5.707 and 6.746, so $b = 5.707$ and

$$s = \frac{5.707 - 3.148}{5.707} = 0.448.$$

Wine 72, a cultivar 2 wine, has $a = 4.763$ but an average distance of only 4.655 to one of the other clusters, so $s = (4.655 - 4.763)/4.763 = -0.023$: it is slightly closer, on average, to a cluster it was not assigned to. Seven wines have negative silhouettes. Over $k = 2$ to 8, keeping for each $k$ the clustering with the smallest WCSS found in 1,000 random starts (with only 20, k-means stopped at a worse local minimum for most values of $k$):

$k$ 2 3 4 5 6 7 8
WCSS 1,649.4 1,270.7 1,168.7 1,095.2 1,033.6 972.1 921.7
mean silhouette 0.259 0.285 0.260 0.233 0.196 0.202 0.204
Choosing the number of clusters for the standardized wine data without the labels. Left: the within-cluster sum of squares falls with every added cluster, most steeply up to k = 3. Right: the mean silhouette peaks at k = 3 (0.285), with k = 2 and k = 4 next (0.26).
Choosing the number of clusters for the standardized wine data without the labels. Left: the within-cluster sum of squares falls with every added cluster, most steeply up to k = 3. Right: the mean silhouette peaks at k = 3 (0.285), with k = 2 and k = 4 next (0.26).

The total sum of squares, the WCSS of a single cluster, is 2,301.0. Going from one cluster to two removes 652 of it, and from two to three another 379; after that each added cluster removes about 100 or less (102 for the fourth, then 74, 62, 62 and 50). The mean silhouette is highest at $k = 3$. Both point to three clusters, which happens to be the number of cultivars. The margin over $k = 2$ and $k = 4$ is small, though, and a mean silhouette of 0.285 indicates clusters that are distinguishable but far from cleanly separated. On other data these criteria often disagree, or point to a number of clusters that matches no known grouping.

A map in two dimensions

Principal component analysis of the 13 standardized measurements finds that the first two components, two weighted sums of the measurements, carry 36.2% and 19.2% of their total variance, 55.4% together. Plotting each wine at its two component scores gives the best two-dimensional linear picture of the data.

The 178 wines plotted at their first two principal component scores. Left: the three k-means clusters of the standardized data, found without labels; the five wines farthest from their fifth nearest neighbor in all 13 measurements are circled. Right: the same map marked by cultivar, revealed afterwards. The clusters match the cultivars closely. The circled wines look ordinary on the map, because what makes them unusual lies in directions the map does not show.
The 178 wines plotted at their first two principal component scores. Left: the three k-means clusters of the standardized data, found without labels; the five wines farthest from their fifth nearest neighbor in all 13 measurements are circled. Right: the same map marked by cultivar, revealed afterwards. The clusters match the cultivars closely. The circled wines look ordinary on the map, because what makes them unusual lies in directions the map does not show.

The clusters occupy three regions of the map. Running k-means on the two component scores alone, instead of all 13 measurements, gives nearly the same clusters (ARI 0.932 between the two clusterings) and almost the same agreement with the cultivars (ARI 0.895). For these data, two derived variables keep almost all of the group structure, which suggests that the cultivars differ mainly along a few combinations of the measurements, as Principal Component Analysis shows by reading the components.

Unusual wines

A simple outlier score is the distance from each wine to its fifth nearest neighbor among the other wines, in the standardized 13-dimensional space. A wine in a crowded region has close neighbors and a small score; an isolated wine has a large one. The median score is 2.302 and the 90th percentile 3.246. The five highest are all cultivar 2 wines:

Wine Distance to 5th neighbor Most extreme measurements (standardized)
122 5.072 ash +3.15, flavanoids +3.05, alcalinity of ash +2.70
70 4.826 magnesium +3.59, ash −2.25, nonflavanoid phenols −1.78
96 4.678 magnesium +4.36, proanthocyanins +2.95
74 4.396 alcalinity of ash +3.15, magnesium +2.75
111 4.365 proanthocyanins +3.48, ash −1.99, alcohol −1.90

Wine 96 has a magnesium content of 162, more than four standard deviations above the mean; wine 122 has flavanoids of 5.08 and ash of 3.23, each more than three standard deviations high. Whether these are errors, unusual vintages or simply the tail of the distribution, the data cannot say; the analysis can only point to them. The map in the figure shows a further lesson. All five lie inside the clusters on the two-dimensional map, because their unusual values are in measurements that the first two components weight lightly. An outlier in the full space need not stand out in a projection, and outlier detection should use all the features that matter, not a picture of a few of them.

Checking without labels

With labels hidden, how could the three clusters have been checked? One check is stability: if the structure is real, a slightly different sample should give much the same clusters. Draw a bootstrap sample of 178 wines with replacement, cluster it, and compare the result with the full-data clustering on the same wines by the ARI. Over 50 bootstrap samples, the standardized three-cluster solution has a median ARI of 0.945 (interquartile range 0.907 to 0.983), while solutions with $k = 2$, 4 or 5 are markedly less stable, with medians of 0.748, 0.750 and 0.708.

Stability is not correctness, though. The clustering of the raw measurements, which mixes the cultivars, is even more stable, with a median ARI of 0.982, because its clusters are simply bands of proline, and bands of one variable are easy to reproduce. A stable result can be stably uninteresting. The checks available without labels (internal criteria such as the silhouette, stability under resampling, agreement between methods) can rule results out, but cannot show that a result is the meaningful one. That is finally a judgment about the domain: whether the groups correspond to something, whether the outliers turn out to be errors or discoveries, whether the derived variables can be interpreted. Here the cultivars confirmed the clusters; in a real unsupervised problem no such confirmation exists, and the groups found might be valid and useful while matching no label anyone has recorded.

Supervised and unsupervised together

The two kinds of learning are often combined. Unsupervised methods prepare data for supervised ones: principal components can replace many correlated inputs, and cluster memberships can become new features. Clustering can suggest categories that are then labeled by people and learned by a classifier. And when only a few instances are labeled, the structure found in the unlabeled ones can help, the idea behind semi-supervised learning. The boundary between the two is defined by the data available, not by the methods: the same k-means that finds groups in unlabeled data can be compared with labels when they exist, as was done here.

In Python

scikit-learn gives unsupervised methods the same fit interface as supervised ones, without the output.

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import load_wine
from sklearn.decomposition import PCA
from sklearn.metrics import adjusted_rand_score, silhouette_score
from sklearn.neighbors import NearestNeighbors

wine = load_wine()
X = wine.data
Z = (X - X.mean(0)) / X.std(0, ddof=1)            # standardize

for k in range(2, 9):
    km = KMeans(k, n_init=1000, random_state=0).fit(Z)   # many starts: the best WCSS
    print(k, round(km.inertia_, 1), round(silhouette_score(Z, km.labels_), 3))

labels = KMeans(3, n_init=20, random_state=0).fit(Z).labels_
print(adjusted_rand_score(wine.target, labels))   # 0.897: checked only because labels exist

scores = PCA(n_components=2).fit_transform(Z)     # the two-dimensional map

d5 = NearestNeighbors(n_neighbors=6).fit(Z).kneighbors(Z)[0][:, 5]   # 5th neighbor; 0th is itself
print(np.argsort(-d5)[:5] + 1)                    # wines 122, 70, 96, 74, 111

inertia_ is the WCSS. The numbers in this article are computed by tools/experiments/data-science/introduction-to-unsupervised-learning.py in the site's repository.

References