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

Fig5: ball_tree

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 :

Goodness of the best fit model
More the R^2 value, better the model
Formuala : R^2
- = 1 – (SSRes/SSTotal)
- = 1 – ( Ʃ (yi- ŷi) ^2 / Ʃ (yi - ̅yi) ^2 )
SSRes
- Sum of Residuals : Ʃ (yi- ŷ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

Eg: Good Model

1-1/4

1-.25

Eg: Bad Model

1-4/4

Eg: Very Bad Model

1-8/4

-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 Email
  - Always Type I and Type II models are inversaly propotions, intuitively if Type I increases Type II error decreases

Module

Classification

>>> 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