What Near Means

The crowd in the box above is the one from the nearest neighbours page, five children and six adults measured by height and weight, and the ringed person at 150 centimetres and 45 kilograms is the one being classified. That page found the three nearest people and let them vote, and it never said what nearest meant, because everyone assumed the straight line.

Switch the metric in the box and two things move at once, which people the ringed person actually consults and the shaded map of what the model would answer everywhere else. Under four of the six metrics the three consulted are the same three and the answer is child; under cosine the third voter is a different adult and the answer is adult; under Hamming every person in the crowd is at exactly the same distance and the vote is decided by whoever happens to come first.

A distance takes two representations and produces one comparison value. A nearest-neighbor model then uses those values to decide which stored examples contribute to its answer. The distance therefore defines what the model treats as relevant similarity.

For the marked example and the nearby observation at height 147 and weight 41, the coordinate differences are three centimetres and four kilograms. The rules produce different kinds of comparison:

Euclidean distance: √(3² + 4²) = 5
Manhattan distance: |3| + |4| = 7
Maximum-coordinate distance: max(3, 4) = 4
Hamming distance: both coordinates differ, so the differing share is 1
Cosine distance: approximately 0.000189

The small cosine distance reflects similar directions from the origin, not small coordinate differences in the same units as the other scores. We will define each rule separately before using it to rank neighbors.

Not every rule that turns two rows into a number deserves the name. A distance has to put a person at zero from themselves and at more than zero from anyone else, it has to answer the same whichever person is named first, and going by way of a third person can never be shorter than going direct.

The third rule is the one that does work, since it is what lets a search prune, if the way station is far from the query then everything near the way station is far too, and it is what makes a distance behave like the word suggests.

d(a, a) = 0,  and  d(a, b) > 0  whenever a ≠ b
d(a, b) = d(b, a)
d(a, b) ≤ d(a, c) + d(c, b)

Take three people of the same height, weighing 45, 52 and 60 kilograms. Compare the direct distance with the route through the middle person.

p-norm distances: 7 + 8 = 15
cosine distances: 0.000892 + 0.001095 = 0.001987
                  direct distance ≈ 0.003962

Cosine distance makes the indirect route shorter than the direct one. That violates the triangle inequality, so it cannot support every shortcut that a metric-based search would use. The other distances tested here satisfy the inequality on this triple.

The reason cosine fails is that it is an angle wearing the vocabulary of a distance. One minus the cosine of an angle is not additive along a path the way the angle itself is, and for a small angle it grows with the square of the angle, so halving the angle quarters the number and two halves sum to less than the whole.

It also fails the first rule at one point. A row of all zeros has no direction, and the last column of the table shows the origin at distance 1 from itself under cosine and at 0 under every other metric.

Now the pair the page works by hand, the ringed person at (150, 45) against their nearest at (147, 41). The gaps are 3 and 4, which is the triangle every schoolchild meets, so the first three answers can be read straight off.

gaps  3 and 4

manhattan   3 + 4                  = 7
euclidean   √(3² + 4²) = √25       = 5
chebyshev   max(3, 4)              = 4

dot product = 150 × 147 + 45 × 41 = 23,895
first squared length = 150² + 45² = 24,525
second squared length = 147² + 41² = 23,290

a · b     = 150·147 + 45·41 = 23895
|a|       = √24525 = 156.6046
|b|       = √23290 = 152.6106

similarity = 23895 / (156.6046 · 152.6106) = 0.99981
cosine     = 1 − 0.99981                    = 0.00019

height contribution = 3 / 297 ≈ 0.0101
weight contribution = 4 / 86 ≈ 0.0465
Canberra distance ≈ 0.0101 + 0.0465 ≈ 0.0566

The same six rules applied to the whole crowd decide who votes. The three p-norms consult the same three people for this query, since a person nearer in every gap is nearer however the gaps are combined, and the three sit at 5, 10 and 13 by the straight line, 7, 14 and 17 by the taxi grid, and 4, 8 and 12 by the largest gap.

Two of the three are children, and the answer is child. Canberra keeps the same three in the same order, at 0.0566, 0.1012 and 0.1346, and answers child.

Manhattan, Euclidean and Chebyshev are one formula. Take the gaps along each feature, raise each to a power, add them up, and take that root back off again. The power is the dial, and the three names are three settings of it.

minkowski, order p    ( Σ |gap|^p ) ^ (1/p)

    p = 1    the gaps added up          Manhattan
    p = 2    the straight line           Euclidean
    p → ∞    the largest single gap      Chebyshev

Raising the order shifts weight onto whichever single gap is largest. On the worked gap of 3 and 4 the sweep from one to infinity is a falling sequence, and every value in it was computed rather than interpolated.

The quickest way to feel what a metric does is to ask it which points are exactly one away from a fixed centre. Under Euclidean distance the answer is a circle, which is what the word means. Under Manhattan it is a diamond, because to stay at a total of one you must trade horizontal movement for vertical one for one.

Under Chebyshev it is a square, because only the larger gap counts, so you can move freely in the other direction until it overtakes. Each panel below is a lattice of 41 by 41 cells a tenth apart, every cell asked how far it is from the centre.

Hamming’s panel looks broken and is not. It can only ever answer zero, a half or one, so of the 1681 cells exactly 1600 sit at its maximum of one and the remaining 81 form a cross through the centre, the cells that happen to share a horizontal or a vertical value with it. There is no curve to draw because there is no gradual falling away.

Now click a panel to move the centre, because that is the control that separates the six into two kinds. The circle, the diamond, the square and the cross are the same shapes wherever you put them, and their counts change only where the shape runs off the edge of the lattice. Cosine and Canberra are not.

Move the centre to (1, 1) and cosine’s region becomes a half-plane of 861 cells with 41 on its boundary, and Canberra’s becomes 413 with 46, and both change again at the next centre you pick. Their notion of one unit depends on where they are standing, which for Canberra is the entire point of it.

The origin, which is where the gallery starts, is the worst place to stand for both of them. Cosine shades every one of the 1681 cells at exactly one, because the origin has no direction for anything to point away from. Canberra shades only the two axes, 81 cells within one and 80 at exactly one, because dividing a gap by the sum of the pair it separates gives exactly one whenever the other number is zero.

Two metrics that work well elsewhere have nothing to say at the one point a reader is most likely to try first, and a model that hands them data centred on zero inherits that silence.

Measured on the lattice, the diamond holds 221 cells within one unit, the circle 317 and the square 441, and the boundaries run 40, 12 and 80 cells. That ordering is not an accident of the drawing. The diamond sits inside the circle, which sits inside the square, for every centre and every radius, and the argument is short.

p ≤ q   implies   ||gap||_q  ≤  ||gap||_p

The same fact read from the worked pair is the sweep in the previous step, 7 down to 4 as the order rises, and read from a model it says that raising the order can never push a person further away, only nearer or the same.

The one derivation worth doing is the limit that produces Chebyshev, because it explains why the largest gap is the sensible reading of an infinite order rather than a convention. Call the largest gap M and pull it out of the sum.

( Σ |gap|^p ) ^ (1/p)  =  M · ( Σ (|gap| / M)^p ) ^ (1/p)

as p → ∞     t ^ (1/p)  →  1        so the distance  →  M

On the worked gap the sweep passes 4.285 at order four and 4.022 at order ten on its way to 4, which is the smaller gap of 3 being raised to a power and vanishing beside the larger one.

Every one of the p-norms adds a gap in centimetres to a gap in kilograms as if they were the same kind of number, and they are only comparable because the crowd happens to span about sixty of each. Nothing in the formula knows that. On the worked pair the height column is doing 0.512 of the squared-gap arithmetic across the crowd, which is roughly half, and it is half by luck of the units rather than by any decision.

Put the weights into grams, which changes no person, and the same pair is 4000.001 apart by the straight line where it was 5, with the height gap of 3 contributing 9 to a squared total of 16,000,009, so the distance is the weight gap of 4000 with a correction in the seventh significant figure.

Refit the whole crowd with its weights multiplied by a thousand and the height column’s share of the arithmetic falls from 0.512 to about one millionth. On this particular crowd the three people the query consults come back the same three, at 4000.001, 8000.002 and 12000.001, because the ranking by weight alone happens to agree with the ranking by both, and the vote is still child. That is the quiet version of the failure, a model that has stopped reading one of its columns and gives no sign of it.

The repair is to put every column on a scale of its own spread before measuring anything, which is the whole subject of the feature scaling page and is not repeated here. Standardised, the query is at (−0.080, −0.403) in units of standard deviations, its three nearest are the same three as the raw fit at 0.233, 0.466 and 0.618, and the height column does 0.464 of the arithmetic, which is close to the 0.512 it did by accident and now holds whatever units the data arrived in.

The standardised panel of the widget above fits the scaler on the crowd and passes the query through the same scalings, in that order. Fitting it on the crowd and the query together would let the query move the mean it is then measured against, which the pipelines page measures as a leak.

It would be convenient if some of the six were immune to units, and one of them is. Canberra divides each gap by the size of the values it sits between, so multiplying a column by a thousand multiplies the gap and its denominator alike, and the pair reads 0.0566 in kilograms and 0.0566 in grams, identical to the last bit. Hamming is exempt too, trivially, since it asks only whether two values are equal and a thousand times equal values are still equal.

I expected cosine to ignore this scaling, but the measurement clarified the distinction. Multiplying every coordinate of one vector by the same positive factor preserves its direction. Rescaling only one feature changes directions and can change cosine comparisons.

Converting the weight column from kilograms to grams changes the selected pair's cosine distance from approximately 0.000189 to 0.0000000318. The vectors now point much more strongly along the weight axis. Although the first three neighbors happen to remain the same, later rankings differ.

Standardizing the features changes the geometry again. In this example, the standardized cosine neighbors produce a child prediction where the raw-feature version predicted adult. The relevant question is therefore how features are scaled, not simply whether a comparison divides by vector length.

Draw a line from the origin to each person and cosine measures the angle between the two lines, as one minus its cosine, and nothing else. Scale the nearest person’s whole row by two, so that they stand at (294, 82), and the straight-line distance to the query goes from 5 to 148.68 while cosine stays at 0.000189 to the last digit, because the doubled person lies on the same line from the origin. Scale by ten and the straight line reads 1369.5 and cosine still reads 0.000189.

The extreme case is (1, 1) against (100, 100), which cosine puts at 0.0000000000000002, an epsilon from zero, and the straight line at 140.007. If magnitude carries meaning, and for a person’s height and weight it plainly does, that is the wrong answer. If the rows are word counts and a long document should resemble a short one on the same subject, it is exactly the right one, and it is why text is usually handled with angles.

Three things follow from cosine being an angle. The range runs from zero to two, since one minus a cosine can reach two only for rows pointing exactly opposite, and (3, 4) against (−3, −4) does reach 2.0. On data that cannot go below zero, counts and shares and measurements of people, two rows are at most a right angle apart and the distance never exceeds one.

A row of all zeros has no direction at all, and it is reported at distance 1 from everything, itself included, which is the convention the wider ecosystem follows and the reason the gallery’s cosine panel is one flat colour at the origin.

A query at the origin under cosine is therefore at exactly 1 from every one of the eleven people, and the neighbour model consults the first three by index because it has nothing else to go on. The third consequence is the one Part 1 measured, that the triangle inequality fails, so a search that prunes by it would prune wrongly.

Rounding adds a small fourth. A row against its own direction lands an epsilon or two from zero rather than on it, and the implementation clamps a distance of minus two times ten to the sixteenth back to zero so that it cannot sort ahead of a genuine zero.

Suppose the first column is a colour encoded as 0, 1 or 2 and the second is a size. There is no sense in which colour 2 is further from colour 0 than colour 1 is, and every metric on this page except Hamming would insist otherwise. Two people whose colours are two apart are 2.0 apart by the straight line and 1.0 by Canberra, two people whose colours are one apart are 1.0 and 1.0, and Hamming puts both pairs at 0.5, one feature of two disagreeing, which is the only honest answer.

Hamming is reported as a share rather than a count, so that 0.25 means one feature in four whether there are four features or four hundred, and so that it sits on the same scale whatever the width of the table.

Hamming compares floating-point values exactly. Arithmetic can produce slightly different stored numbers even when the decimal expressions describe the same mathematical value.

in ordinary binary floating point:
0.1 + 0.2 ≈ 0.30000000000000004
0.3       ≈ 0.29999999999999999

Hamming counts that coordinate as a full disagreement. Integer category codes suit this comparison; measurements computed through different arithmetic paths may not.

Suppose the two columns are counts, a rare species beside a common one, and two sites differ by one in each. The straight line reads the two gaps alike. Canberra reads the first gap against the size of the counts it sits between and the second the same way, and the same gap of one is worth 1.0 between zero and one, 0.333 between one and two, and 0.005 between a hundred and a hundred and one.

Canberra treats the same relative change equally at different scales.

|0.002 − 0.001| / (0.002 + 0.001) = 1/3
|2 − 1| / (2 + 1) = 1/3

That can be useful for relative differences in counts. It can also magnify tiny differences near zero. When both values are zero, this implementation defines the contribution as zero instead of evaluating an undefined quotient.

The nearest neighbours regressor and classifier take the metric as a setting, since a neighbour model learns nothing and the metric is the whole of its opinion. The six named metrics are a closed set, so a misspelling is refused rather than silently defaulted, and beyond the six the model accepts any object that can measure every query against every stored row.

An order-three p-norm, which no name covers, ranks the worked crowd’s nearest three at 4.498, 8.996 and 12.28, between the Euclidean 5, 10, 13 and the Chebyshev 4, 8, 12 as Part 2 says it must.

Two of the clusterers take the same setting, and each for the same reason, that all the model ever asks of a distance is a comparison. The density clusterer asks whether one person is within a radius of another and groups whoever is connected by such steps; single, complete and average linkage ask which two groups are nearest and merge them. Any of the six answers either question. What changes is that the radius is in the metric’s own units, and twenty means something different under each.

Single linkage cut at two groups gives a cleaner reading of what each metric thinks the crowd is. Four of the six cut the three far children off from the other eight, Euclidean making its first merge at 2.236 and its last at 23.35 and Manhattan at 3 and 33. Cosine cuts by direction instead, and puts the person at (147, 41) with the three far children, because all four are small in both measurements and point the same way.

Hamming, with every pair at 1, has nothing to merge by, and its cut leaves one person alone and says nothing about the crowd.

It would be reasonable to expect every method that measures distance to offer the same dial, and the k-means page does not. The reason is a fact about the algorithm rather than a simplification of it. k-means alternates two steps, put every person with the nearest centre and then move each centre to the mean of the people it now holds, and the argument that it must settle rests on both steps lowering one total.

The second step lowers it because the mean is the point that minimises the sum of squared distances to a group, and that is a fact about squared Euclidean distance specifically.

Measured on the crowd’s weight column, whose mean is 53.36 and whose median is 57, the total squared gap from the mean is 4742.5 and from the median 4888.0, so the mean wins on squares. The total absolute gap from the mean is 191.6 and from the median 188.0, so the median wins on absolute gaps, which are Manhattan’s currency.

Hand k-means Manhattan and its update step moves the centre to the wrong place for the total it is supposed to be lowering, the convergence argument collapses, and what is left is a loop with no guarantee.

So the metric is a setting on the neighbour models and on the density and linkage clusterers, where it is a genuine choice, and is absent from k-means, where offering it would be offering something that does not work. The method that does what the expectation wants is k-medoids, which replaces the mean with an actual member of the group, and it is not built here.

The same line runs through two other places. Ward linkage merges whichever pair of groups adds least to the spread about a group mean, so it computes a mean and inherits k-means’ restriction, and pairing it with Manhattan is refused at construction with a message that says so rather than producing a number the rule does not describe. The self-organising map moves a winning unit a step along the negative gradient of half the squared Euclidean distance, which is a different step from the one Manhattan’s gradient would take, so it refuses the setting for a reason one step removed from the mean.

ward with manhattan  →  refused at construction

"ward linkage merges whichever pair adds least to the spread about a group mean, and a mean minimises squared Euclidean distance and no other"

A neighbour model at prediction time measures every query against every remembered row, so the answer is a table with one row per query and one column per stored person. The general way to build it is to line every query up against every stored row, subtract, and reduce over the features, which produces a three-dimensional array of queries by rows by features before the reduction collapses it.

Five hundred queries against twenty thousand stored rows over twenty features is two hundred million numbers at eight bytes each, 1.6 gigabytes for an answer that occupies 80 megabytes.

Four of the six metrics have no way round that array, so the queries are taken a block at a time, with the block sized so the pairing array stays under 64 megabytes, and the loop changes only the peak memory and never the arithmetic, so the blocked and unblocked answers agree bit for bit. The other two reduce to a matrix multiply and never build the array at all.

Open the square in the Euclidean formula and the expensive part becomes a single matrix product. The two squared-norm terms are one pass over each input, and the cross term is every query dotted with every stored row, which is the product of the query block with the transposed stored block.

||a − b||²  =  ||a||²  −  2 a · b  +  ||b||²

On the worked pair the three routes agree. The definition gives 5, the expansion on the raw coordinates gives 4.999999999999273, and the centred expansion gives 5. The expansion is off in the thirteenth decimal on numbers around a hundred and fifty, which is the first sign of what the next step shows. Cosine takes the same route, since after each row is scaled to unit length the whole table is one matrix product of unit rows.

Recovering a small number by subtracting two large nearly equal ones is the classic way to lose it, and the expansion is that pattern exactly. Put two people at coordinates near a million, a millionth apart along one feature. The definition gives 0.0000010000076, which is right to the digits the input carries. The expansion on the raw coordinates gives exactly 0.0, the entire distance gone, because the two squared lengths are each about two million million and their difference is smaller than the rounding in either.

Widen the gap to a thousandth and the raw expansion still gives 0.0. Only at a gap of one do the three routes agree again, at 1.0 each.

Both symptoms come from the coordinates being far from the origin rather than from the people being close together, so the implementation subtracts the stored rows’ mean from both inputs before expanding. Shifting every point equally leaves every distance unchanged while making each squared length a number the size of the spread rather than of the offset, and on the pathological pair the shifted expansion returns the definition’s answer exactly.

The shift is also why the crowd with a constant height column, in Part 8, reports its second neighbour at 7.999999999999999 rather than 8, since the arithmetic is now done on deviations and rounds where the definition would not. A clamp at zero stays regardless, because the square root of a tiny negative is not a number and would propagate silently through a mean.

Every distance on this page was measured in two features, and two is where distance works best. Add columns and something happens to the word nearest that no choice of metric undoes. Draw two hundred rows at random in one feature, measure every row against every other, and ask for each row how much further its farthest neighbour is than its nearest, as a ratio to the nearest.

The median of that ratio is 369.8, so a typical row has a neighbour hundreds of times nearer than the rest. Keep the same rows and add features, each drawn the same way, and the median falls to 28.3 in two, 4.50 in five, 1.98 in ten, 0.544 in fifty and 0.235 in two hundred.

At two hundred features the nearest row is only about a quarter nearer than the farthest, so the k nearest is very nearly a random subset wearing a disguise.

relative contrast  =  (farthest − nearest) / nearest,   one ratio per row, the median over rows

Richard Bellman named the curse of dimensionality in 1957, for the way the volume of a box grows with its dimension, and Beyer, Goldstein, Ramakrishnan and Shaft asked the question this widget answers in “When is nearest neighbor meaningful?” in 1999. Their result is that when the spread of distances from a query grows more slowly than their average, which it does for independent features, every point ends up about equally far away and nearest stops being a property of the data.

The six do not lose contrast at the same rate. At two hundred features the medians are 0.540 for cosine, 0.297 for Manhattan, 0.266 for Canberra, 0.235 for Euclidean and 0.193 for Chebyshev, so the ordering runs from the metric that reads only the angle down to the one that reads only the worst feature, with the p-norms in order of their exponent. Hamming on continuous rows is at zero throughout, since every pair disagrees on every feature and every distance is exactly 1.

That the lower exponents hold up better is the result of Aggarwal, Hinneburg and Keim in 2001, who found that Manhattan beats Euclidean in high dimensions and that fractional orders below one beat both, and it is why Manhattan is the steadier choice on data with many columns. Cosine keeps the most here, which is part of why text, with its thousands of columns, is handled with angles.

In two features cosine is the outlier the other way, with a median of 128,032 and a mean of 2,694,429, because a few rows have another row almost exactly on their line from the origin and the ratio divides by a nearest distance near zero.

Since the loss is a property of distance, the remedies are all about having fewer columns or better ones. The principal component analysis page keeps the few directions the data actually varies along, which is the usual first move before a neighbour model on wide data, and the measurement above is the reason it is usual. Standardising, from Part 3, does not help here, since the drawn features already share a scale, and neither does any metric on its own. The fractional orders that Aggarwal, Hinneburg and Keim recommend are available here, since the p-norm takes any positive order, and Part 8 records the price, which is that below one the triangle inequality fails.

A complete implementation states which metrics it names and whether an unnamed one can be supplied, what order the p-norm family accepts, how Hamming compares floating-point values, what Canberra does with a zero over zero, what cosine does with a row of zeros and with rounding either side of one, whether Euclidean is computed by definition or by expansion and, if by expansion, what it centres on, how a pairing array is bounded, how ties in a ranking are broken, and which models may take the metric and which refuse it. Every row below was probed.

The two rows that deserve a second look are the ones that are accepted. An order below one and a Hamming comparison of computed floats both give a number that a caller can use, and both give one that is not what the caller probably meant. Each is documented rather than refused, because the first is a legitimate request in a high-dimensional setting and the second is correct on the data Hamming exists for.