ml K‐nearest neighbours - ghdrako/doc_snipets GitHub Wiki

K-nearest neighbours

Algorytm k-najblizszych sąsiadów klasyfikuje cechy na podstawie ich odległosci od okreslonej liczby k próbek treningowych. Nalezy do algorytmów odległosciowych ponieważ nie uczy sie tylko na podstawie tego parametru. Przyjmuje sie w nim załozenie, ze miara odległości jest wystarczajaca do wnioskowania. Nie sa przyjmowane zadne inne załozenia dotyczace wartosci i rozkladu danych. Najtrudniesza kwestia jest dobór włascwej wartosci k

Strengths	Weaknesses
Simple and effective	Does not produce a model, limiting the ability to understand how the features are related to the class
Makes no assumptions about the underlying data distribution	Requires selection of an appropriate k
Fast training phase	Nominal features and missing data require additional processing

Measuring similarity with distance

Locating the tomato’s nearest neighbors requires a distance function, which is a formula that measures the similarity between two instances. There are many ways to calculate distance. The choice of distance function may impact the model’s performance substantially, although it is difficult to know which to use except by comparing them directly on the desired learning task. Traditionally, the k-NN algorithm uses Euclidean distance, which is the distance one would measure if it were possible to use a ruler to connect two points. Euclidean distance is measured “as the crow flies,” which implies the shortest direct route.

Another common distance measure is Manhattan distance, which is based on the paths a pedestrian would take by walking city blocks.

Euclidean distance is specified by the following formula, where p and q are the examples to be compared, each having n features. The term p1 refers to the value of the first feature of example p, while q1 refers to the value of the first feature of example q:

dist(𝑝𝑝𝑝 𝑝𝑝) = √(𝑝𝑝1 − 𝑝𝑝1)2 + (𝑝𝑝2 − 𝑝𝑝2)2+. . . +(𝑝𝑝𝑛𝑛 − 𝑝𝑝𝑛𝑛)2

The distance formula involves comparing the values of each example’s features.

If we use the k-NN algorithm with k = 3 instead, it performs a vote among the three nearest neighbors.

Choosing an appropriate k

The decision of how many neighbors to use for k-NN determines how well the model will general- ize to future data. The balance between overfitting and underfitting the training data is a problem known as the bias-variance tradeoff. Choosing a large k reduces the impact of variance caused by noisy data but can bias the learner such that it runs the risk of ignoring small but important patterns.

Suppose we took the extreme stance of setting a very large k, as large as the total number of observations in the training data. With every training instance represented in the final vote, the most common class always has a majority of the voters. The model would consequently always predict the majority class, regardless of the nearest neighbors.

On the opposite extreme, using a single nearest neighbor allows noisy data and outliers to unduly influence the classification of examples. For example, suppose some of the training examples were accidentally mislabeled. Any unlabeled example that happens to be nearest to the incorrectly labeled neighbor will be predicted to have the incorrect class, even if nine other nearby neighbors would have voted differently.

Obviously, the best k value is somewhere between these two extremes.

Preparing data for use with k-NN

Features are typically transformed to a standard range prior to applying the k-NN algorithm. The rationale for this step is that the distance formula is highly dependent on how features are measured. In particular, if certain features have a much larger range of values than others, the distance measurements will be strongly dominated by the features with larger ranges.

The solution is to rescale the features by shrinking or expanding their range such that each one contributes relatively equally to the distance formula.

The traditional method of rescaling features for k-NN is min-max normalization. This process transforms a feature such that all values fall in a range between 0 and 1. The formula for normal- izing a feature is as follows:

To transform each value of feature X, the formula subtracts the minimum X value and divides it by the range of X. The resulting normalized feature values can be interpreted as indicating how far, from 0 percent to 100 percent, the original value fell along the range between the original minimum and maximum.

Another common transformation is called z-score standardization. The following formula sub- tracts the mean value of feature X, and divides the result by the standard deviation of X:

This formula rescales each of a feature’s values in terms of how many standard deviations they fall above or below the mean. The resulting value is called a z-score. The z-scores fall in an unbounded range of negative and positive numbers. Unlike the normalized values, they have no predefined minimum and maximum.

The same rescaling method used on the k-NN training dataset must also be applied to the test examples that the algorithm will later classify. This can lead to a tricky situation for min-max normalization, as the minimum or maximum of future cases might be outside the range of values observed in the training data. If you know the theoretical minimum or maximum value ahead of time, you can use these constants rather than the observed minimum and maximum values. Alternatively, you can use z-score standardization under the assumption that the future examples are taken from a distribution with the same mean and standard deviation as the training examples.

The Euclidean distance formula is undefined for nominal data. Therefore, to calculate the distance between nominal features, we need to convert them into a numeric format. A typical solution utilizes dummy coding, where a value of 1 indicates one category, and 0 indicates the other. For instance, dummy coding for a male or non-male sex variable could be constructed as:

Notice how dummy coding of the two-category (binary) sex variable results in a single new fea- ture named male. There is no need to construct a separate feature for non-male. Since both are mutually exclusive, knowing one or the other is enough. This is true more generally as well. An n-category nominal feature can be dummy coded by cre- ating binary indicator variables for n - 1 levels of the feature. For example, dummy coding for a three-category temperature variable (for example, hot, medium, or cold) could be set up as (3 - 1) = 2 features, as shown here:

Knowing that hot and medium are both 0 provides enough information to know that the tem- perature is cold, and thus, a third binary feature for the cold category is unnecessary. However, a widely used close sibling of dummy coding known as one-hot encoding creates binary features for all n levels of the feature, rather than n - 1 as with dummy coding. It is known as “one-hot” because only one attribute is coded as 1 and the others are set to 0.

In practice, there is virtually no difference between these two methods, and the results of ma- chine learning will be unaffected by the choice of coding. This being said, one-hot encoding can cause problems with linear models and thus one-hot encoding is often avoided among statisticians or in fields like economics that rely heavily on such models. On the other hand, one-hot encoding has become prevalent in the field of machine learning and is often treated synonymously with dummy coding for the simple reason that the choice makes virtually no difference in the model fit; yet, in one-hot encoding, the model itself may be easier to understand since all levels of the categorical features are specified explicitly.