{"course":{"slug":"machine-learning-foundations","title":"Machine Learning, Foundations","url":"https://addaly.com/learn/machine-learning-foundations","level":"intermediate","track":"start"},"lesson":{"slug":"nearest-neighbours","title":"k-nearest neighbours, and why distance stops meaning anything","url":"https://addaly.com/learn/machine-learning-foundations/nearest-neighbours","position":58,"of":92,"minutes":8,"answer":"k-NN makes the assumption behind most machine learning explicit (nearby points share targets) and the curse of dimensionality breaks it because distances concentrate, so the nearest neighbour in 1.","keyIdea":"k-NN makes the assumption behind most machine learning explicit (nearby points share targets) and the curse of dimensionality breaks it because distances concentrate, so the nearest neighbour in 1,000 raw dimensions is barely nearer than the farthest."},"body":{"format":"markdown","text":"## The model with no training\n\nStore the data. To predict, find the k closest training rows and take their average or their majority vote.\n\n```python\nfrom sklearn.neighbors import KNeighborsClassifier\nKNeighborsClassifier(n_neighbors=15, weights=\"distance\")\n```\n\nThere is no fitting step: `fit` just stores the array. All the work happens at prediction time, which inverts the usual cost profile: instant training, slow predictions, and the entire training set has to live in memory forever.\n\nk-NN is worth understanding for three reasons beyond its own use. It is the clearest possible illustration of the curse of dimensionality; it is the mechanism underneath every embedding search in module 7; and it makes the assumption behind most machine learning explicit: **that things close together in feature space have similar targets.** Every model assumes some version of that. k-NN says it out loud.\n\n## Choosing k\n\nk = 1 memorises: training error is zero and the decision boundary is a jagged shape drawn around individual points. High variance.\n\nLarge k smooths: at k = n every prediction is the global average. High bias.\n\nSomething between 5 and 50 is usually right, chosen by cross-validation. `weights=\"distance\"` makes nearer neighbours count more, which usually helps and lets you use a larger k without over-smoothing.\n\n## Scaling is not optional here\n\nWith age in years and income in rupees, the distance between two people is essentially the difference in their incomes. Age contributes nothing measurable. Standardise, always, before any distance-based method: this is the model where forgetting it produces the most obviously wrong answer.\n\nCategorical features are a genuine problem. What is the distance between Mumbai and Chennai? One-hot encoding makes every pair of distinct cities exactly the same distance apart, which at least is not misleading, but it also inflates dimensionality, which brings us to the real issue.\n\n## The curse of dimensionality, with numbers\n\nIn high dimensions, everything is far away and, worse, everything is roughly *equally* far away.\n\nGenerate 1,000 random points uniformly in a unit cube and look at the distance from one point to its nearest and farthest neighbours:\n\n- **2 dimensions**: nearest about 0.02, farthest about 1.2. The ratio is around 60. \"Near\" and \"far\" are clearly different.\n- **10 dimensions**: nearest about 0.5, farthest about 2.0. Ratio 4.\n- **100 dimensions**: nearest about 3.5, farthest about 5.5. Ratio 1.6.\n- **1,000 dimensions**: nearest about 12.4, farthest about 14.8. Ratio 1.2.\n\nBy 1,000 dimensions, your nearest neighbour is barely nearer than your farthest. The word \"neighbour\" has stopped picking anything out, and a method built entirely on that word has nothing to work with.\n\n> Figure: How far the farthest point is, relative to the nearest. Bars (farthest distance divided by nearest distance): 2 dimensions 60; 10 dimensions 4; 100 dimensions 1.6; 1,000 dimensions 1.2. 1,000 random points in a unit cube. In two dimensions the farthest neighbour is sixty times further away than the nearest. By 1,000 dimensions it is only 20 per cent further, and the word neighbour has stopped picking anything out. This is geometry, and it affects every method built on distance.\n\nThe geometric reason: in d dimensions, distance is a sum of d squared differences. As d grows, that sum concentrates around its expectation (the law of large numbers applied to coordinates) and the spread between the smallest and largest sums shrinks relative to their size.\n\n## What this means beyond k-NN\n\nThis is not a k-NN problem; it is a geometry problem, and it affects every method that relies on distance or density: k-means, DBSCAN, RBF-kernel SVMs, Gaussian mixtures, and any anomaly detector built on distance.\n\nTwo qualifications keep it from being paralysing.\n\n**Real data usually has lower intrinsic dimension than its column count.** Photographs of faces occupy a tiny, curved region of pixel space; the features are heavily correlated, so the effective dimensionality is far below the nominal one. This is why nearest-neighbour search over 768-dimensional embeddings works well in practice, and it is the reason the manifold idea in module 7 matters.\n\n**Learned representations are built to make distance meaningful.** An embedding is trained so that similar things land close together. That is precisely what raw high-dimensional coordinates fail to give you, and it is why the pairing of embeddings with nearest-neighbour search is so effective.\n\n## When k-NN is the right answer\n\nSmall datasets. Low dimensions. Genuinely irregular decision boundaries that a parametric model would smooth over. Recommendation by similarity. As a baseline, because it takes one line and sometimes surprises you.\n\nAnd when the dataset is large, exact search becomes too slow, at which point you want approximate nearest neighbour indexes (FAISS, HNSW, Annoy, all free) which trade a small amount of recall for enormous speed. Module 7 covers them, because that is where they earn their keep."},"check":{"question":"A team applies k-NN to 300-dimensional TF-IDF vectors and finds predictions no better than chance, though a linear model on the same features works well. What explains the difference?","options":[{"text":"TF-IDF values are not standardised, and k-NN requires standardisation while linear models do not.","correct":false,"tempting":"Scaling does matter for k-NN, but TF-IDF vectors are already L2-normalised by default, so the usual scale mismatch is absent."},{"text":"In 300 sparse dimensions the distances between documents concentrate, so nearest neighbours are barely nearer than distant ones, while a linear model uses a weighted sum that does not depend on distances at all.","correct":true},{"text":"k-NN cannot handle sparse matrices, so the vectors were densified incorrectly.","correct":false,"tempting":"scikit-learn's k-NN accepts sparse input directly; a representation issue would raise an error rather than produce chance-level predictions."},{"text":"300 dimensions is too few for k-NN, which needs high-dimensional data to find meaningful neighbourhoods.","correct":false,"tempting":"Inverts the relationship: k-NN works best in low dimensions and degrades as dimensionality rises."}]},"prev":{"slug":"the-boosting-libraries","title":"XGBoost, LightGBM, CatBoost: what actually differs","url":"https://addaly.com/learn/machine-learning-foundations/the-boosting-libraries"},"next":{"slug":"naive-bayes","title":"Naive Bayes: wrong assumptions, useful results","url":"https://addaly.com/learn/machine-learning-foundations/naive-bayes"},"authorship":"Founder and series editor: Dr Mustafa Mun. Written by AI models to a written standard. Exam keys checked blind by a second model: 3,665 of 3,666 agreed. Academic review invited.","review":{"status":"Draft, open for academic review"},"cite":"Addaly (2026) 'k-nearest neighbours, and why distance stops meaning anything', in Machine Learning, Foundations. Edited by M. Mun. Addaly. Available at: https://addaly.com/learn/machine-learning-foundations/nearest-neighbours (Accessed: 13 October 2026).","licence":{"name":"CC BY-NC-SA 4.0","url":"https://creativecommons.org/licenses/by-nc-sa/4.0/"},"reader":{"schema":1,"title":"k-nearest neighbours, and why distance stops meaning anything","courseTitle":"Machine Learning, Foundations","module":{"index":6,"slug":"trees-and-ensembles","title":"Trees, ensembles, and the algorithms that win on tables"},"answer":null,"keyIdea":"k-NN makes the assumption behind most machine learning explicit (nearby points share targets) and the curse of dimensionality breaks it because distances concentrate, so the nearest neighbour in 1,000 raw dimensions is barely nearer than the farthest.","hero":{"kind":"figure","figure":{"t":"figure","label":"Figure","figure":{"type":"bars","unit":"farthest distance divided by nearest distance","title":"How far the farthest point is, relative to the nearest","series":[{"label":"2 dimensions","value":60},{"label":"10 dimensions","value":4},{"label":"100 dimensions","value":1.6},{"label":"1,000 dimensions","value":1.2,"highlight":true}],"caption":"1,000 random points in a unit cube. In two dimensions the farthest neighbour is sixty times further away than the nearest. By 1,000 dimensions it is only 20 per cent further, and the word neighbour has stopped picking anything out. This is geometry, and it affects every method built on distance."},"alt":"Figure: How far the farthest point is, relative to the nearest. Bars (farthest distance divided by nearest distance): 2 dimensions 60; 10 dimensions 4; 100 dimensions 1.6; 1,000 dimensions 1.2. 1,000 random points in a unit cube. In two dimensions the farthest neighbour is sixty times further away than the nearest. By 1,000 dimensions it is only 20 per cent further, and the word neighbour has stopped picking anything out. This is geometry, and it affects every method built on distance."}},"blocks":[{"t":"h2","id":"the-model-with-no-training","runs":[{"text":"The model with no training"}]},{"t":"p","runs":[{"text":"Store the data. To predict, find the k closest training rows and take their average or their majority vote."}]},{"t":"code","lang":"python","label":"Python","text":"from sklearn.neighbors import KNeighborsClassifier\nKNeighborsClassifier(n_neighbors=15, weights=\"distance\")"},{"t":"p","runs":[{"text":"There is no fitting step: "},{"text":"fit","code":true},{"text":" just stores the array. All the work happens at prediction time, which inverts the usual cost profile: instant training, slow predictions, and the entire training set has to live in memory forever."}]},{"t":"p","runs":[{"text":"k-NN is worth understanding for three reasons beyond its own use. It is the clearest possible illustration of the curse of dimensionality; it is the mechanism underneath every embedding search in module 7; and it makes the assumption behind most machine learning explicit: "},{"text":"that things close together in feature space have similar targets.","b":true},{"text":" Every model assumes some version of that. k-NN says it out loud."}]},{"t":"h2","id":"choosing-k","runs":[{"text":"Choosing k"}]},{"t":"p","runs":[{"text":"k = 1 memorises: training error is zero and the decision boundary is a jagged shape drawn around individual points. High variance."}]},{"t":"p","runs":[{"text":"Large k smooths: at k = n every prediction is the global average. High bias."}]},{"t":"p","runs":[{"text":"Something between 5 and 50 is usually right, chosen by cross-validation. "},{"text":"weights=\"distance\"","code":true},{"text":" makes nearer neighbours count more, which usually helps and lets you use a larger k without over-smoothing."}]},{"t":"h2","id":"scaling-is-not-optional-here","runs":[{"text":"Scaling is not optional here"}]},{"t":"p","runs":[{"text":"With age in years and income in rupees, the distance between two people is essentially the difference in their incomes. Age contributes nothing measurable. Standardise, always, before any distance-based method: this is the model where forgetting it produces the most obviously wrong answer."}]},{"t":"p","runs":[{"text":"Categorical features are a genuine problem. What is the distance between Mumbai and Chennai? One-hot encoding makes every pair of distinct cities exactly the same distance apart, which at least is not misleading, but it also inflates dimensionality, which brings us to the real issue."}]},{"t":"h2","id":"the-curse-of-dimensionality-with-numbers","runs":[{"text":"The curse of dimensionality, with numbers"}]},{"t":"p","runs":[{"text":"In high dimensions, everything is far away and, worse, everything is roughly "},{"text":"equally","i":true},{"text":" far away."}]},{"t":"p","runs":[{"text":"Generate 1,000 random points uniformly in a unit cube and look at the distance from one point to its nearest and farthest neighbours:"}]},{"t":"ul","items":[[{"text":"2 dimensions","b":true},{"text":": nearest about 0.02, farthest about 1.2. The ratio is around 60. “Near” and “far” are clearly different."}],[{"text":"10 dimensions","b":true},{"text":": nearest about 0.5, farthest about 2.0. Ratio 4."}],[{"text":"100 dimensions","b":true},{"text":": nearest about 3.5, farthest about 5.5. Ratio 1.6."}],[{"text":"1,000 dimensions","b":true},{"text":": nearest about 12.4, farthest about 14.8. Ratio 1.2."}]]},{"t":"p","runs":[{"text":"By 1,000 dimensions, your nearest neighbour is barely nearer than your farthest. The word “neighbour” has stopped picking anything out, and a method built entirely on that word has nothing to work with."}]},{"t":"p","runs":[{"text":"The geometric reason: in d dimensions, distance is a sum of d squared differences. As d grows, that sum concentrates around its expectation (the law of large numbers applied to coordinates) and the spread between the smallest and largest sums shrinks relative to their size."}]},{"t":"h2","id":"what-this-means-beyond-k-nn","runs":[{"text":"What this means beyond k-NN"}]},{"t":"p","runs":[{"text":"This is not a k-NN problem; it is a geometry problem, and it affects every method that relies on distance or density: k-means, DBSCAN, RBF-kernel SVMs, Gaussian mixtures, and any anomaly detector built on distance."}]},{"t":"p","runs":[{"text":"Two qualifications keep it from being paralysing."}]},{"t":"p","runs":[{"text":"Real data usually has lower intrinsic dimension than its column count.","b":true},{"text":" Photographs of faces occupy a tiny, curved region of pixel space; the features are heavily correlated, so the effective dimensionality is far below the nominal one. This is why nearest-neighbour search over 768-dimensional embeddings works well in practice, and it is the reason the manifold idea in module 7 matters."}]},{"t":"p","runs":[{"text":"Learned representations are built to make distance meaningful.","b":true},{"text":" An embedding is trained so that similar things land close together. That is precisely what raw high-dimensional coordinates fail to give you, and it is why the pairing of embeddings with nearest-neighbour search is so effective."}]},{"t":"h2","id":"when-k-nn-is-the-right-answer","runs":[{"text":"When k-NN is the right answer"}]},{"t":"p","runs":[{"text":"Small datasets. Low dimensions. Genuinely irregular decision boundaries that a parametric model would smooth over. Recommendation by similarity. As a baseline, because it takes one line and sometimes surprises you."}]},{"t":"p","runs":[{"text":"And when the dataset is large, exact search becomes too slow, at which point you want approximate nearest neighbour indexes (FAISS, HNSW, Annoy, all free) which trade a small amount of recall for enormous speed. Module 7 covers them, because that is where they earn their keep."}]}],"check":{"question":[{"text":"A team applies k-NN to 300-dimensional TF-IDF vectors and finds predictions no better than chance, though a linear model on the same features works well. What explains the difference?"}],"options":[{"text":[{"text":"TF-IDF values are not standardised, and k-NN requires standardisation while linear models do not."}],"correct":false,"tempting":[{"text":"Scaling does matter for k-NN, but TF-IDF vectors are already L2-normalised by default, so the usual scale mismatch is absent."}]},{"text":[{"text":"In 300 sparse dimensions the distances between documents concentrate, so nearest neighbours are barely nearer than distant ones, while a linear model uses a weighted sum that does not depend on distances at all."}],"correct":true,"tempting":null},{"text":[{"text":"k-NN cannot handle sparse matrices, so the vectors were densified incorrectly."}],"correct":false,"tempting":[{"text":"scikit-learn’s k-NN accepts sparse input directly; a representation issue would raise an error rather than produce chance-level predictions."}]},{"text":[{"text":"300 dimensions is too few for k-NN, which needs high-dimensional data to find meaningful neighbourhoods."}],"correct":false,"tempting":[{"text":"Inverts the relationship: k-NN works best in low dimensions and degrades as dimensionality rises."}]}],"order":[0,3,1,2],"why":null},"prev":{"slug":"the-boosting-libraries","title":"XGBoost, LightGBM, CatBoost: what actually differs","minutes":9},"next":{"slug":"naive-bayes","title":"Naive Bayes: wrong assumptions, useful results","minutes":8}}}