Clustering and nearest-neighbor methods act on a single input: a notion of how far apart, or how alike, two observations are. The centroid method needs squared Euclidean distance, hierarchical clustering needs distances between all pairs, and k-nearest-neighbor classification ranks training examples by distance. The answers these methods give can change completely when the distance or the scale of the features changes, so the choice has to be stated and justified. This unit sets out the standard measures, which of them are genuine metrics, and the preprocessing that makes numerical features comparable.
Metrics and common measures
Definition 14.1.1
(Metric and the Minkowski family)
A function is a metric on a set if for all : ; exactly when ; ; and (the triangle inequality). For define
These are the Manhattan, Euclidean and Chebyshev distances.
Theorem 14.1.2
(The three distances are metrics)
, and are metrics on .
Proof
(Proof)
Non-negativity, symmetry and the property that only if every coordinate agrees are immediate from the formulas. For the triangle inequality of and , use in every coordinate, then sum or take the maximum, noting that the maximum of a sum is at most the sum of the maxima. For , write and . Then by the Cauchy–Schwarz inequality . Taking square roots gives .
Proof X-ray
Where Cauchy–Schwarz enters the Euclidean triangle inequality
Only the triangle inequality needs an idea, and for the idea is to square. With and the claim becomes . Both sides are nonnegative, so it is equivalent to . Expanding leaves one cross term, , and Cauchy–Schwarz is the only non-routine step: it bounds that term by . Equality holds when and are nonnegative multiples of a common vector, that is, when lies on the segment from to .
The final square root is what turns the squared inequality back into the one for . For the same expansion would need , that is , which fails for the collinear points , where and .
Squared Euclidean distance is not a metric: for points on a line, . It is nevertheless the quantity the k-means objective uses.
Concept lensGeometric
Three unit balls
Geometrically, the three distances differ in the shape of the set of points within distance one of a center. In the plane this unit ball is a diamond for , a disc for and an axis-parallel square for . Since pointwise, the diamond lies inside the disc, which lies inside the square. With center , the point has distances , and : it is on the boundary of the diamond but well inside the square.
Definition 14.1.3
(Cosine similarity, Jaccard similarity and Hamming distance)
For nonzero , the cosine similarity is and the cosine dissimilarity is . For finite sets that are not both empty, the Jaccard similarity is and the Jaccard distance is . For two strings of equal length, the Hamming distance counts the positions where they differ.
Cosine similarity ignores vector length, which suits count vectors of documents of different lengths: and have cosine similarity although their Euclidean distance is .
Proposition 14.1.4
(Cosine and Euclidean distance on unit vectors)
If , then . Hence, among unit vectors, ranking by increasing Euclidean distance from a fixed unit vector is the same as ranking by decreasing cosine similarity with .
Proof
(Expand the squared norm)
, and because both norms are 1. The map is strictly decreasing, so it reverses the order of cosine values.
Counterexample mode
Cosine dissimilarity is not a metric
It is nonnegative and symmetric, so one might claim that is a metric. Take , , . Then , so , while gives . Since , the triangle inequality fails. The identity axiom also fails: and are different points with . The angle between directions avoids both problems.
The angle itself, , is a metric on directions, though we do not prove that here. Jaccard distance and Hamming distance are metrics; we use this standard fact without proof.
Scaling numerical features
Euclidean distance adds squared differences across features, so a feature with a large numerical range dominates the sum. Two common remedies rescale each feature separately using training data.
Definition 14.1.5
(Min-max scaling and standardization)
Let a feature have training values with minimum , maximum , mean and population standard deviation . Min-max scaling sends a value to , mapping the training range to . Standardization (the z-score) sends to , so the training values have mean and variance . A constant feature has and and must be removed or left unscaled; the formulas are undefined.
The constants are fitted on the training data only and then applied unchanged to validation and test data. Computing them on a pooled data set lets test information influence the transformation, a form of leakage that makes the evaluation optimistic. A test value outside the training range is mapped outside , and that is correct behavior, not an error to be clipped silently.
Worked examples
Worked example 14.1.6
(Scaling can change the nearest neighbor)
Four customers have (age in years, income) equal to , , , . Unscaled Euclidean distances from are , and , so is the nearest neighbor: the income column dominates, and is nearest only because it shares 's income.
Apply min-max scaling with training ranges to for age and to for income. The scaled points are , , , . The distances from are for , for and for . Now is nearest. Neither answer is "correct" in the abstract; the scaled version treats a one-range difference in either feature as equally large, which is a modeling choice that should be made on purpose.
Worked example 14.1.7
(Standardizing with training statistics, and set and vector measures)
A training feature has values . The mean is and the squared deviations are , summing to , so the population variance is and . The standardized training values are . A test value is mapped to , using the training and . Recomputing the statistics with included would give a different mean and silently change every transformed value.
For sets and we have and , so and the Jaccard distance is .
Worked example 14.1.8
(An outlier and a constant feature under min-max scaling)
A feature has training values . Then , and , so the scaled values are , approximately . Without the outlier the range would be and the four ordinary values would map to . A one-unit difference between ordinary points now contributes to a scaled coordinate instead of , so this feature hardly influences distances among them.
A second feature takes the value in every training row. Then and is , while standardization has . The feature cannot separate training rows, so it is removed (or left unscaled) before scaling, by a policy stated in advance.
Common mistakes and subtle points
Common mistake
(Scaling is not free, and the distance must match the data type)
Standardizing a feature that is already on a meaningful common scale can remove useful information. Min-max scaling is sensitive to a single outlier, which stretches and compresses all other values. Binary indicator features turned into and and given Euclidean distance implicitly count mismatches; whether that is wanted should be decided, not assumed. Finally, the triangle inequality matters because some algorithms, such as those that prune neighbor searches, are only correct for metrics; do not substitute cosine dissimilarity there without checking.
Exercises
Quick check
(1. Compare the three distances)
Compute between and .
Solution · Solution 1
The coordinate differences are . So , and .
Quick check
(2. Scale a test value)
Training values of a feature are . Give the min-max value and the z-score of a new test value , both using training statistics.
Solution · Solution 2
The training minimum and maximum are and , so the min-max value is , outside as it should be. With and the z-score is .
Quick check
(3. Jaccard distance)
Compute the Jaccard distance of and .
Solution · Solution 3
has elements and has . So and the distance is .
Quick check
(4. Cosine and Euclidean distance on unit vectors)
Let and . Verify that both are unit vectors, compute and , and check the identity .
Solution · Solution 4
and . The cosine is . Also , and , as claimed.