k-nearest neighbors
In plain wordsPredicting something about a new example by finding the few most similar examples already known and going with their majority answer, or their average.
A nonparametricnonparametric model, n.: A model that lets the data decide how complex it becomes: the more examples it gets, the more detail it can capture — for instance, one that predicts by comparing a new case with every stored example. method resting on the assumption that inputs close together have similar outputs. Nothing is fitted in advance: the training set is simply stored ('lazy' or instance-based learning), and a query is answered by retrieving its k closest stored examples under a chosen distance, often Euclidean distanceEuclidean distance, n.: How far apart two points are in a straight line, as a ruler would measure it, extended from two or three dimensions to lists of numbers of any length. or cosine similaritycosine similarity, n.: A score from −1 to 1 for how closely two lists of numbers point the same way, ignoring their size. It is the standard test of whether two texts mean similar things., then returning their most common label for classificationclassification, n.: Sorting things into categories — spam or not spam, which animal is in a photo, which language a text is written in — by learning from examples that are already labeled. or their average value for regressionregression, n.: Predicting a number rather than a category — a house's price, tomorrow's temperature, a patient's blood pressure — by learning from past examples where the answer is known., sometimes counting nearer neighbors more. The number k sets the smoothness: small k gives flexible, high-variance boundaries, large k smoother ones. Because all the work happens at query time, spatial indexes such as k-d trees or approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster. keep lookups fast. Results depend on feature scalingfeature scaling, n.: Putting input measurements on comparable scales, so that income in dollars and age in years, say, both span similar ranges and no feature dominates just because of its units. and degrade in high dimensions, where distances become less informative (the curse of dimensionalitycurse of dimensionality, n.: The problems that pile up when each item is described by very many measurements: even huge datasets end up thinly scattered across the possibilities, and 'near' and 'far' stop meaning much.). With unlimited data, the 1-nearest-neighbor error rate is at most twice the Bayes-optimal error. Nearest-neighbor lookup over embeddingsembedding, n.: A list of numbers that stands for a word, picture or other item, arranged so that similar items get similar lists. It lets a computer measure similarity of meaning as distance. underlies modern vector searchvector search, n.: Searching by closeness instead of exact match: the query and all stored items are lists of numbers, and the search returns the items whose numbers are most similar to the query's. and retrieval.
With k = 15 and standardized features, k-nearest neighbors matched the logistic regression baseline.
Origin
Introduced by Evelyn Fix and Joseph Hodges in a 1951 U.S. Air Force School of Aviation Medicine report, 'Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties'. Thomas Cover and Peter Hart's 'Nearest Neighbor Pattern Classification' (IEEE Transactions on Information Theory, 1967) proved the twice-the-Bayes-error bound and popularized the method.
Usage note
Not to be confused with k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat., an unsupervised method that also uses a number k and distances.
Related
- nonparametric modelnonparametric model, n.: A model that lets the data decide how complex it becomes: the more examples it gets, the more detail it can capture — for instance, one that predicts by comparing a new case with every stored example.
- approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster.
- curse of dimensionalitycurse of dimensionality, n.: The problems that pile up when each item is described by very many measurements: even huge datasets end up thinly scattered across the possibilities, and 'near' and 'far' stop meaning much.
- feature scalingfeature scaling, n.: Putting input measurements on comparable scales, so that income in dollars and age in years, say, both span similar ranges and no feature dominates just because of its units.
- vector searchvector search, n.: Searching by closeness instead of exact match: the query and all stored items are lists of numbers, and the search returns the items whose numbers are most similar to the query's.
- decision boundarydecision boundary, n.: The dividing line, or surface, where a classifier switches from predicting one category to another. Simple models draw straight lines; flexible ones draw curves.
- k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat.
Sources
- Fix, E. & Hodges, J. L. (1951). Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties. Report 4, USAF School of Aviation Medicine, Randolph Field, Texas.
- Cover, T. M. & Hart, P. E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.
Mentioned in
classificationclassification, n.: Sorting things into categories — spam or not spam, which animal is in a photo, which language a text is written in — by learning from examples that are already labeled., baggingbagging, n.: Training many copies of a model, each on a different random resample of the data, and averaging their predictions. The averaging cancels out much of each copy's random error., collaborative filteringcollaborative filtering, n.: Recommending things based on what people with similar tastes liked, without needing to know anything about the things themselves, as in 'people who bought this also bought…'., curse of dimensionalitycurse of dimensionality, n.: The problems that pile up when each item is described by very many measurements: even huge datasets end up thinly scattered across the possibilities, and 'near' and 'far' stop meaning much., decision boundarydecision boundary, n.: The dividing line, or surface, where a classifier switches from predicting one category to another. Simple models draw straight lines; flexible ones draw curves., Euclidean distanceEuclidean distance, n.: How far apart two points are in a straight line, as a ruler would measure it, extended from two or three dimensions to lists of numbers of any length., feature scalingfeature scaling, n.: Putting input measurements on comparable scales, so that income in dollars and age in years, say, both span similar ranges and no feature dominates just because of its units., hyperparameterhyperparameter, n.: A setting chosen by people before training, such as how fast a model learns or how big it is, as opposed to the internal values the model learns by itself from data., imputationimputation, n.: Filling in missing values in a dataset with sensible estimates, such as the typical value or a prediction from the other columns, so the data can be analyzed or used for training., inductive biasinductive bias, n.: The assumptions built into a learning method that decide how it fills the gaps between the examples it was shown, such as that similar inputs get similar answers. Every learner needs some to cope with new cases., k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat., multiclass classificationmulticlass classification, n.: Sorting each item into exactly one of three or more categories — for example, deciding which of the ten digits a handwritten number shows., nonparametric modelnonparametric model, n.: A model that lets the data decide how complex it becomes: the more examples it gets, the more detail it can capture — for instance, one that predicts by comparing a new case with every stored example., SMOTESMOTE, abbr.: A technique for lopsided data that invents extra examples of the rare category by blending each rare example with one of its nearest rare neighbors, so a model sees more of it during training., UMAPUMAP, n.: A fast technique for turning data with many measurements per item into a flat map that keeps similar items together; often preferred to older methods because it is quicker and copes with more data., vector searchvector search, n.: Searching by closeness instead of exact match: the query and all stored items are lists of numbers, and the search returns the items whose numbers are most similar to the query's., Bayes error rateBayes error rate, n.: The lowest error any classifier could ever achieve on a task, because some cases are genuinely ambiguous: even a perfect model that knew the true odds would still sometimes guess wrong., case-based reasoningcase-based reasoning, n.: Handling a new situation by finding the most similar one dealt with before and adjusting what worked then, much as a cook adapts a remembered recipe to the ingredients at hand., metric learningmetric learning, n.: Teaching a model to measure similarity: it learns to place items so that ones that should count as alike end up close together and different ones far apart.