Description
Supervised Learning Model
Can be used for both Regression and Classification
Fix & Hodges proposed K-nearest neighbor classifier algorithm in the year of 1951 for performing pattern classification task.
KNN is very simple algorithm, using distance calculation
Non Parametric, as it does not assumes the distribution of data
KNN is lazy algorithm, l\azy means during training not much is done, fit function will run faster and predict will run slower
Y value is identified with the majority of vote casted by the Neighbours (K), having K as constant
Classification:
Eg: If the neighbours are as below :
F, F, F, T, T, T, F
The result will also be F
Regression
If the values are continuous like 32, 34, 43, 54, 21
Below are some methods can be used to predit
Mode, Median, Mean
Neighbours are identified by using distance, and using the closest distance
So defining the K value is important, as based on K (either mode or median ) of the neighbours the Y value is predicted
K value is kept as odd number, for clarity in classification of Y value
Increasing the K value, refine the judgement of Y value
If only we take 2 neighbours and see them as :
T, T
Then we would come predict Y as T
But the real picture would be like this :
F, F, F, F, F, F, T, T
Here where the two T were outliers and actual prediction should be as F
Always suggested to have the Data to be Scaled, else it might skew towards the high magnitude attributes.
Beautifully explained in the below link:
https://medium.com/analytics-vidhya/why-is-scaling-required-in-knn-and-k-means-8129e4d88ed7
Short summary:
Having 2 attributes, age and income
As age is much smaller than income, the distance becomes much biased to the income
After scaling, similar weightage is given to both the variables
Suggested selection method for the prediction :
Classification : Mode
Regression : Mean or Median
Steps :
Calculate distance from the given input
Sort the distance
Find K closest neighbours
Vote for Y
Eg:
Input:
age, income -> Vote/Not Vote
33, 10K -> Vote
34, 40L -> Not Vote
29, 45K -> Vote
45, 50L -> Note Vote
31, 30K -> Vote
28, 25K -> Note
Output:
29, 35K
1
30
2
29
3
1, 2, 3, 29, 30
K = 3
1 , 2 , 3
Vote, Vote, Vote
Vote
Formula
Distance Formulas for Continuous X values, either one could be used
Euclidean: Remember “Pythagorean Theorem”, L2 Norm
Manhattan: Also known as Taxicab Geometry, City Block Distance etc., L1 Norm
Minkowshi: Lp Norm
Fig1: Distance functions for continuous values
Distance Formulas for Categorical X values
Hamming distance: Number of position of different bit. Eg:
10100
10111
At times Cosine Distance Metric is used,
Actually the distance is calculated by the Cos Theta, the angle between P1 and P2
Here,
cosine value 1: vectors are pointing to same direction, i.e there is similarities,
value 0: some similarities found though unrelated and
value -1: the vectors point opposite direction, hence no similarities found
Note: Researchers have shown for larger dimensions or when more values are with 0 Euclidean distance is not useful, Cosine similarity have less impact in such scenario. I assume that as the two points are zero there is possibility those values could be similar (i.e the angle distance between cos 0 will be 1).
Reference: https://www.youtube.com/watch?v=ieMjGVYw9ag
Fig2: Distance functions for discrete values
Assumption
Scaling of the data is important
Address missing values
Hyper Parameter Tuning
Metric : Euclidean, Manhattan, Minkowski, Hamming, Cosine
The distance metric to use for the tree.
The default metric is minkowski, and with p=2, as p is 2 its is equivalent to the standard Euclidean metric (so by default its euclidean, even though in the default parameter it says minkowski)
K : Starting for 3, Odd number
Elbow Curve: helps to select the optimal number of K
Eg: The optimal value of K is 20. The graph of the error rate increases after 20.
Fig3: Elbow curve
Algorithm :
brute
Lazy, finds all the distance of the neighbours, also time costly (O(N^2) ) and inefficient with increase in number of points
kd_tree
binary tree – but holds K values
sort the points first
tree is split alternatively on the parameters
eg: if we have only 2 parameters, x1 and x2
the first split will happen in x1
the second spilt will happen in x2
sample image:
Fig4: kd_tree
Credit: https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/KDtree.html
works well in low dimensions, but causes curse of dimensionality with high dimensions data
because higher the dimensions the near points and the far points are so close to each other in the vector, its difficult to calculate the distances between the values
ball_tree
binary tree – but holds K values
find the random point and find the farthest point, and farthest point from this point, hence the split will happen
Sample image
works well in high dimensions, and it would take more time than kd_tree for low dimensions data
Very nice explanation:
https://www.youtube.com/watch?v=czC0j_oUb6g
auto
will attempt to decide most appropriate algorithm based on the values passed to the fit function
Weights : uniform, distance
Weights function used while prediction
uniform: uniform weights, all the points in each neighbourhood are weighted equally
distance: closer neighbours will have greater influence in the predictions
Visualisation
Fig6: KNN 2D visualisation
Credit: https://dataaspirant.com/k-nearest-neighbor-classifier-intro/
Evaluation
For Regression :
R2
Goodness of the best fit model
More the R^2 value, better the model
Formuala : R^2
= 1 – (SSRes/SSTotal)
= 1 – ( Ʃ (yi- ŷi) ^2 / Ʃ (yi - ̅yi) ^2 )
SSRes
Sum of Residuals : Ʃ (yi- ŷi) ^2
Residuals means errors, predictions minus actual Y value
The reason we are squaring is to absolute the negative values
SSTotal
- Sum of Total means Sum of Average Total : Ʃ (yi - ̅yi) ^2
- Eg: Average Model
- 1- 2/4
- 1- 1/2
- 1- .5
- 1-0.5
- 0.5
- Eg: Good Model
- 1-1/4
- 1-.25
- .75
- Eg: Bad Model
- 1-4/4
- 1-1
- 0
- Eg: Very Bad Model
- 1-8/4
- 1-2
- -1
- Adjusted R Square
When we have new number of features added, we have an increase in R2 value
So AdjRSquare value is used when there are comparisions between 2 or more reg models with different independent variables
It helps us to find the new added independent variable is helpful or not in increasing the R2 square value
Formula :
1 - ( (1-R^2) * (N-1) / (N-P-1) )
N: no of rows or sample size
P: no of predictors or independent features
- If the independent variables are correlated to the Target variable, we will have small decrease in the adjR2.
- Else we will have higher decrease in adjR2
Points to remember :
Every time we add a independent variable to a model the R Square always increase
Even if there is no significant correlation with Target variable, it will never decline
Whereas Adjusted R Square increases only when independent variable is significant and affects dependent variable
Adjusted R Square value would always be less than or equal to R Square value
Reference : https://www.youtube.com/watch?v=WuuyD3Yr-js
For Classification
- Accuracy
Percentage of correct predictions
But in real life scenarios, we may be more keen in looking for precision and recall
Because eg: we have a scenario where in when need to find if the there is fraud transaction, as out of all the transactions we would have only 1% of fraud transactions, we may have good results in accuracy, but our intention would be to find less False Negatives.
Accuracy of model : TP+TN / (TP+TN+FP+FN)
Confusion Matrix
An easy and popular method of diagnosing model performance.
TN : True Negative
TP : True Positive
FN : False Negative - Type II
FP : False Positive - Type I
Example:
Fig7: Example for Confusion Matrix for Spam Email and Real EmailAlways Type I and Type II models are inversaly propotions, intuitively if Type I increases Type II error decreases
Module
Classification
>>> X = [[0], [1], [2], [3]]
>>> y = [0, 0, 1, 1]
>>> from sklearn.neighbors import KNeighborsClassifier
>>> neigh = KNeighborsClassifier(n_neighbors=3)
>>> neigh.fit(X, y)
KNeighborsClassifier(...)
>>> print(neigh.predict([[1.1]]))
[0]
>>> print(neigh.predict_proba([[0.9]]))
[[0.66666667 0.33333333]]
Regression
>>> X = [[0], [1], [2], [3]]
>>> y = [0, 0, 1, 1]
>>> from sklearn.neighbors import KNeighborsRegressor
>>> neigh = KNeighborsRegressor(n_neighbors=2)
>>> neigh.fit(X, y)
KNeighborsRegressor(...)
>>> print(neigh.predict([[1.5]]))
[0.5]
Advantages
Faster in Training Phase
Useful when the data is Non Linear
Not impacted by the outliers
Drawbacks
Curse of Dimensionality, struggles when the input parameters are high, as more the features means overfitting of the model, and to control overfitting requires more the data.
Testing phase is costlier in time and memory
Scaling is important
References
https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.NearestNeighbors.html
https://people.revoledu.com/kardi/tutorial/KNN/HowTo_KNN.html
https://www.geeksforgeeks.org/k-nearest-neighbours/
https://www.datacamp.com/community/tutorials/k-nearest-neighbor-classification-scikit-learn
