ML7.6 · LESSON 6 OF 6

Anomalies and evaluation

Perform a clustering update and explain dimensionality reduction, mixtures and anomaly detection.

THE IDEA

An anomaly is something unusual, not something wrong

Anomaly detection fits a picture of "normal" and gives every point a score for how badly it fits: far from the centre, far from any cluster, or far from its nearest neighbours. You then choose a threshold: points scoring above it are flagged. The score is only as good as the picture of normal that stands behind it, and the threshold is a decision about how many false alarms you can stand.

Below are 45 points: two normal groups, four real anomalies and one rare but perfectly legitimate point in the middle (think of a valid but unusual transaction). Pick a score, move the threshold, and look at what gets flagged. Then tick "Reveal the truth".

Score:

threshold = 0

Reveal the truth (real life gives you no labels)

Flagged: 45 of 45 points (everything at or above 0). Without labels all you can see is this count and whether it looks reasonable.

Three scores, one threshold slider. Red rings are flagged points. Reveal the truth to see diamonds (real anomalies), the triangle (rare but valid) and circles (normal).

Distance from the overall mean assumes one blob. With two groups the middle of the plot looks normal and the groups' edges look odd. To catch all four anomalies you must flag 4 normal points as well (threshold 4.53).
Distance to the nearest k-means centre fits the two-group picture. A threshold of 3.3 flags exactly the four anomalies: precision 1, recall 1. This works partly by luck: the rare valid point scores 3.09, just below the weakest anomaly at 3.48, so a threshold fits between them.
Mean distance to the 3 nearest neighbours (a density score) needs no clusters at all, but one anomaly sits near a neighbour and scores lower than the rare valid point. To catch all four with threshold 2.5 it flags 1 false alarm: the valid point.

Predict first. A rare but legitimate transaction gets a high anomaly score. What does that tell you?

How do you judge a clustering with no labels?

There is no accuracy because there is no answer key. Three honest checks are available, and none of them proves the clusters are "real".

Silhouette. For point i, let a be its mean distance to the other points in its cluster and b its mean distance to the nearest other cluster. The silhouette is (b − a) / max(a, b): near +1 well inside its cluster, near 0 on a border, negative probably closer to another cluster. Click a point below to see it computed.
Stability. Run the algorithm from different starts. If the partitions differ a lot from run to run, the structure is fragile. We measure agreement with the Rand index, the share of point pairs on which two runs agree (together in both or apart in both).
Downstream use. Does the clustering help the task you actually had, such as better segments, a cheaper index or fewer review cases? That is the test that matters.

k =

Mean silhouette for each k (higher is more separated):

Stability: agreement between 12 one-start runs (1 means identical partitions):

Click a point on the plot to see its silhouette computed. Mean silhouette at k = 4: 0.478.

Forty points that look like four groups, two of them neighbours. Switch k and click points. Bars on the right: mean silhouette and seed stability per k.

Read the result carefully. The mean silhouette is highest at k = 2 (0.637), because merging the two close groups into one removes most of the borderline points (six points score below 0.3 at k = 4, only one at k = 2); at k = 4 it is 0.478. Stability agrees: with k = 2 every one of the 12 starts finds the same split (stability 1) while k = 4 gives 0.858, so some starts get stuck. That does not make k = 2 the truth: the data really has four groups, two of them close together. A metric rewards one definition of good, and silhouette tends to prefer fewer, well-separated clusters.

Chapter context

Unsupervised methods expose structure according to their objectives and assumptions. They do not discover a single objectively correct organization of a dataset; changing distance, dimension or density assumptions can change the result.

TRY IT YOURSELF

Part 1. Do it on the plot

One shared state drives both figures: first the threshold tasks on 45 points, then the silhouette tasks on 40 points.

Score:

threshold = 0

Reveal the truth (real life gives you no labels)

Flagged: 45 of 45 points (everything at or above 0). Without labels all you can see is this count and whether it looks reasonable.

k =

Mean silhouette for each k (higher is more separated):

Stability: agreement between 12 one-start runs (1 means identical partitions):

Click a point on the plot to see its silhouette computed. Mean silhouette at k = 4: 0.478.

To do: Anomalies: with the k-means score, set a threshold that flags all 4 real anomalies and nothing else (use Reveal truth to check)
To do: With the neighbour-distance score, catch all 4 anomalies and notice the rare valid point gets flagged too
To do: With the distance-from-mean score, catch all 4 anomalies with as few false alarms as possible
To do: Clustering: choose the k with the highest mean silhouette
To do: At k = 4, click the single worst-placed point (lowest silhouette)
To do: Find a k where all 12 seeds give exactly the same partition (stability 1)

Part 2. Do it in code

silhouette_point(X, labels, i) returns the silhouette of point i: a is its mean Euclidean distance to the OTHER points of its own cluster, b is the smallest mean distance to the points of any other cluster, and the score is (b - a) / max(a, b).
A point alone in its cluster scores 0. If max(a, b) is 0 (identical points) the score is 0. If there is only one cluster, raise ValueError.
silhouette_mean(X, labels) averages the score over all points.

import numpy as np

def silhouette_point(X, labels, i):
    # (b - a) / max(a, b)
    pass

def silhouette_mean(X, labels):
    # average over all points
    pass

X = np.array([[0.0], [1.0], [10.0], [11.0]])
print(silhouette_point(X, np.array([0, 0, 1, 1]), 0))

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can a rare valid transaction receive an anomaly score?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

J=\sum_i\|x_i-\mu_{c_i}\|^2,\quad \mu_k=\frac1{|C_k|}\sum_{i\in C_k}x_i.

For centered data X, PCA uses leading eigenvectors of $X^TX/(n-1)$ , or an equivalent SVD. Centering and feature scaling are separate choices.

For a Gaussian mixture, EM responsibilities are

r_{ik}=\frac{\pi_k\mathcal N(x_i\mid\mu_k,\Sigma_k)}{\sum_j\pi_j\mathcal N(x_i\mid\mu_j,\Sigma_j)}.

Mixing weights pi are nonnegative and sum to one; each row of responsibilities also sums to one. Weighted sufficient-statistic updates differ from hard k-means assignments.

Worked example

With points [0,2,8,10] and starting centers [0,10], assignments are [0,2] and [8,10]. Updated means are 1 and 9. Squared errors are 1,1,1,1, totaling 4. This example gives one iteration; it does not prove that every initialization finds the best partition.

Reference code

The following example uses the Python standard library and does not call a remote service.

points, centers = [0,2,8,10], [0,10]
groups = [[x for x in points if min(range(2), key=lambda j: (x-centers[j])**2) == i] for i in range(2)]
updated = [sum(group)/len(group) for group in groups]
assert updated == [1,9]
assert sum((x-c)**2 for group,c in zip(groups,updated) for x in group) == 4

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Clusters are objective-dependent. PCA maximizes variance, which may not correspond to useful semantic structure. Anomaly detection is not the same as identifying known fraud classes.