0
$\begingroup$

I'm just getting started with learning about K-nearest neighbor and am having a hard time understanding why standardization is required. Reading through, I came across a section saying

When independent variables in training data are measured in different units, it is important to standardize variables before calculating distance. For example, if one variable is based on height in cms, and the other is based on weight in kgs then height will influence more on the distance calculation.

Since K nearest neighbor is just a comparison of distances apart, why does it matter if one of the variables has values of a larger range since it is what it is.

Considering 3 points A,B & C with x,y co-ordinates (x in cm, y in grams) A(2,2000), B(8,9000) and C(10,20000), the ranking of the points as distance from origin for example (or any other point), will be the same whether the y values are in grams,pounds, tonnes or any other combinations of units for both x and y so where's the need to standardise. Every example or QA i see brushes through with the same statement of 'one variable influencing the other' without a real example of how this might occur. Again, how does one know when this influence is too much as to call for standardization.

Also,what exactly does standardization do to the values? One of the formulas does it by Xs = (X-mean)/(max-min) Where does such a formula come from and what is it really doing? Hopefully someone can offer me a simplified explanation or give me a link to a site or book that explains this in simple terms for beginners.

$\endgroup$
  • $\begingroup$ @sAguinaga Thanks that answers my last point. Im quite confused by the need to do it in the first place. $\endgroup$ – West Aug 21 '19 at 11:55
  • $\begingroup$ stats.stackexchange.com/questions/287425/… See this stack exchange question that shows the point quite well $\endgroup$ – Tasty213 Aug 21 '19 at 12:26
  • 1
    $\begingroup$ A better answer is offered here and here z score lets you do standardization: z = x – x̄ / s, where x̄ (the sample mean) and s (the sample standard deviation). $\endgroup$ – sAguinaga Aug 21 '19 at 13:07
3
$\begingroup$

Considering 3 points A,B & C with x,y co-ordinates (x in cm, y in grams) A(2,2000), B(8,9000) and C(10,20000), the ranking of the points as distance from origin for example (or any other point), will be the same whether the y values are in grams,pounds, tonnes or any other combinations of units for both x and y so where's the need to standardise.

This is true for the example you provided, but not for euclidean distance between points in general. Look at this example:

def euclidian_distance(a, b):
    return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5

a1 = 10   #10 grams
a2 = 10  #10 cm
b1 = 10   #10 gram
b2 = 100  #100 cm
c1 = 100  #100 gram
c2 = 10   #10 cm 

# using (grams, cm) 
A_g_cm = [a1, a2]
B_g_cm = [b1, b2]
C_g_cm = [c1, c2]

print('[g, cm] A-B:', euclidian_distance(A_g_cm, B_g_cm))
print('[g, cm] A-C:', euclidian_distance(A_g_cm, C_g_cm))

# using (kg, cm) 
A_kg_cm = [a1/1000, a2]
B_kg_cm = [b1/1000, b2]
C_kg_cm = [c1/1000, c2]

print('[kg, cm] A-B:', euclidian_distance(A_kg_cm, B_kg_cm))
print('[kg, cm] A-C:', euclidian_distance(A_kg_cm, C_kg_cm))

# using (grams, m) 
A_g_m = [a1, a2/100]
B_g_m = [b1, b2/100]
C_g_m = [c1, c2/100]

print('[g, m] A-B:', euclidian_distance(A_g_m, B_g_m))
print('[g, m] A-C:', euclidian_distance(A_g_m, C_g_m))

# using (kilo, m) 
A_kg_m = [a1/1000, a2/100]
B_kg_m = [b1/1000, b2/100]
C_kg_m = [c1/1000, c2/100]

print('[kg, m] A-B:', euclidian_distance(A_kg_m, B_kg_m))
print('[kg, m] A-C:', euclidian_distance(A_kg_m, C_kg_m))

Output:

[g, cm] A-B: 90.0
[g, cm] A-C: 90.0
[kg, cm] A-B: 90.0
[kg, cm] A-C: 0.09000000000000001
[g, m] A-B: 0.9
[g, m] A-C: 90.0
[kg, m] A-B: 0.9
[kg, m] A-C: 0.09000000000000001

Here you can clearly see that the choice of units influence the ranking, thus the need for standardization.

$\endgroup$
  • 1
    $\begingroup$ Exactly the sort of example I've been looking for! Nice and clear thanks a lot mate.,really struggled for a while with this $\endgroup$ – West Aug 21 '19 at 15:16
2
$\begingroup$

There are several reasons for the standardization, the relevant reasons for the KNN algorithm important since the algorithm is based on calculating the distance between neighbours. Let's assume that the distance measure that we are using is the euclidian distance and we are having 2 features x in grams and y in kilometres.

If we'll take a look at the distance (d) formula between 2 points (p,q) with 2 features (1,2): enter image description here

We may notice, that the term (q1-p1) is in grams and (q2-p2) is in kms. There are several issues with this:

  1. we are summing deltas with different units
  2. we are summing deltas with different scale
  3. we are summing deltas of features with different distribution/variance

For example, the first feature has a small magnitude of delta (between 2 points) which is meaningful in its scale and variance, the second feature has a delta with a large magnitude but in its scale and variance it is negligible (1km while reducing 200k km with 199k km).

We can agree that the points are far in the feature 1 space and are close to each other in the feature 2 space, but, our distance metric might not detect that.

The Standardization of the features before applying the distance metric would solve these issues.

$\endgroup$
0
$\begingroup$

Considering 3 points A,B & C with x,y co-ordinates (x in cm, y in grams) A(2,2000), B(8,9000) and C(10,20000), the ranking of the points as distance from origin for example (or any other point), will be the same whether the y values are in grams,pounds, tonnes or any other combinations of units for both x and y so where's the need to standardise.

I'm not sure this is entirely right:

import pandas as pd
import numpy as np
from sklearn.metrics.pairwise import euclidean_distances
from sklearn.preprocessing import StandardScaler

df = pd.read_csv('https://raw.githubusercontent.com/mwaskom/seaborn-data/master/iris.csv')
df = df.drop('species', axis=1)

ss = StandardScaler()

ed1 = euclidean_distances(df)
ed2 = euclidean_distances(ss.fit_transform(df))

ed1_max = np.array([np.argmax(i) for i in ed1])
ed2_max = np.array([np.argmax(i) for i in ed2])

print(np.where(ed1_max == ed2_max, 1, 0).mean())

So for each sample in the iris dataset, this calculates the sample that's furthest away in euclidean distance for both the scaled and unscaled data, and then calculates the percentage of samples where they match. The output is 0.33. So scaling definitely affects the ranking of distances between samples.

So the problem is unscaled data tends to lead to the features with a larger scale drowning out the vote of the other features in determining distance to other samples. Scaling prevents that.

$\endgroup$
0
$\begingroup$

Another goog reason is that standarization of features may serve as a way of preconditioning the problem.

Steepest descent optimization algorithms does not work well on ill-conditioned cases, for instance, when the loss function shows ravines and ridges. In such cases, vanilla Gradient Descent may oscillate in the direction of the largest gradient, deviating from the right direction to the optimum point, and thus, convergence may be very slow. This issue can be addressed with more sophisticated optimizes (RMSprop, Adam...) but standardization of features may precondition the scenario (smoothing the ravines of the loss function, for example)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.