K-Nearest Neighbors is one of the most basic classification algorithms in Machine Learning.

Code and Data-set Link : Github – StuffByYC | Kaggle – StuffByYC

Code and Data-set also available in Downloads section of this website

In this blog we will understand how K-Nearest Neighbors algorithm works. How to Implement it with Python.

KNN algorithm uses “feature similarity” to predict the values of new data-points based on distance.

To see type of distance used in distance based model go to: Type of Distances used in Machine Learning algorithm

Understanding K-Nearest Neighbor

What is K ?

k is the number of neighbors which will help us to decide the class of the new data-point.

Algorithm Steps:

Step 1: Choose the values of “K” that is. the number of neighbor which will be used to predict the resulting class.

Ex. Lets suppose we choose value of k as 5.

There are 2 classes [“Cat” , “Dog” ]. We have to predict if the new data point belongs to class “Cat” or “Dog”.

Step 2: Calculate the distance from the new data point to remaining data points and take k number of the shortest distant neighboring data point. you can choose which distance formula to use. Type of Distances used in Machine Learning algorithm

Ex. Lets suppose the 5 nearest data-point to the New data point “N( x,y ) “ are “A“, “B“, “C“, “D“, “E” that we calculated using euclidean distance method.

Step 3: After getting the “K” nearest data-points, count the categories of the data point ( That is count how many of those k neighbors belong to which categories).

Ex. The class of data points are

A – “Cat”

B – “Dog”

C – “Cat”

D – “Dog”

E – “Dog”

Now count the categories.

“Cats” – 2 and “Dog” – 3

Step 4: Assign the new data point “N” with the class having maximum categories count

Ex. Here category or class “Dog” has the maximum number of category count.

“3” out of “5” of the nearest data-point belong to category “dog”

So the new data point “N” will be assigned to class “Dog”

Let me know in comments if you have any difficulty understanding this.

Implementing K-Nearest Neighbor

Below we will Implement KNN Algorithm using Sklearn Library.

The task is to Predict if the Customer will purchase the product or not

Code and Data-set Link : Github – StuffByYC | Kaggle StuffByYC

Code and Data-set also available in Downloads section of this website

You need to install the Sklearn library

Open command prompt

pip install scikit-learn

Step 1: We will Import the Libraries

Step 2: Importing the data ( You can find the Sales.csv file in the Github Link above )

Step 3: Splitting Data into training and testing data

Here Test_size = 0.25. It means the out of the dataset that data Allocated for testing is 25%

Step 4: Feature Scaling

What is Feature Scaling ?

As we have learned above we are using distance to predict a particular class. Now in this particular data-set we have salary with value ranging from thousand to 100 thousand and the value of age is within 100.

As salary has a wide range from 0 to 150,000+. Where as, Age has a range from 0 – 60 the distance calculated will be dominated by salary column which will result in erroneous model so we need feature scaling

Feature Scaling is a technique to standardize/normalize the independent features (data columns) present in the data in a fixed range.

Below is the sample transition of data from

X(data) -> X (After train_test_split) -> X (After feature scaling)

Step 5: Fitting the model

Here we will be using euclidean distance so we have set p = 2

Click on : Type of Distance to know more.

K value is set to 5

Step 6: Predicting the test result using the Classifier / Model

Step 7: Calculating Performance Metrics to Evaluate model

Click on Performance metrics to know more

Confusion matrix

True Positive (TP): Result data is positive, and is predicted to be positive.

False Negative (FN): Result data is positive, but is predicted negative.

False Positive (FP): Result data is negative, but is predicted positive.

True Negative (TN): Result data is negative, and is predicted to be negative.

Click on confusion matrix to know more

Recall – 85.29%

Click on recall to know more

Accuracy – 90.53%

Click on accuracy to know more

Precision – 87.88%

Click on Precision to know more

F1 Score

Click on F1 Score to know more

Have successfully implemented K-Nearest Neighbors in python with the help of scikit-learn Library. check out Advantages and Disadvantages of K-Nearest Neighbors

k-nearest neighbors is a very simple algorithm used to solve classification problems.

To Understand and Implement the algorithm Visit – k-nearest neighbors in Machine Learning (k-NN)

Advantages

1. k-NN is called Lazy Learner (Instance based learning). It does not learn anything in the training period. There is no training period. It stores the training dataset and learns from it only at the time of making real time predictions.

2. New data can be added without effecting the algorithm performance or accuracy

3. k-nearest neighbors Algorithm is very easy to implement. You need only two input

1. Distance (e.g. Euclidean or Manhattan etc.) . Check of type of distance
2. The value of K

Disadvantages

1. Performance Issue with large data-set: The time required to calculate the distance between the new point and each existing points is huge. Which then degrades the performance of the algorithm.

2. Does not work well with high dimensions / Features: The k-NN algorithm doesn’t work well with large no of Features dimensional data because with large number of Features , it becomes difficult for the algorithm to calculate the distance in each Features .

3. Value of K: It is really crucial to determine what value to assign to k. with different value of K you get different results

Programming is a skill best acquired by practice and example rather than from books. – Alan Turing

In classification, the goal is to predict a class label, which is a choice from a predefined list of possibilities.

If you are new to machine learning check out : Introduction to machine learning 

Classification is a supervised machine learning problem where data is collected, analyzed and used to construct classifier by using classification algorithm. These algorithms are used when the value of target output variable is discrete as { Yes| No }

Binary or binomial classification is the task of classifying the elements of a given set into two groups on the basis of a classification rule Example.( Yes/No ), ( True/False ), ( animal/human )

Multi-class or multi-nomial classification is the problem of classifying instances into one of three or more classes

Performance Metrics

Performance matrix and how to calculate them using formulas and sklearn in python

Confusion Matrix

Don’t go on the name it is just a table that tells you which values were correctly predicted and which are not.

In technical terms: A confusion matrix is a performance measurement technique for Machine learning classification. It is a kind of table which helps you to know the performance of the classification model on a set of test data for that the true values are known.

sklearn – confusion matrix

>>> from sklearn.metrics import confusion_matrix
>>> confusion_matrix(y_actual, y_pred)

True Positive (TP): Result data is positive, and is predicted to be positive.

False Negative (FN): Result data is positive, but is predicted negative.

False Positive (FP): Result data is negative, but is predicted positive.

True Negative (TN): Result data is negative, and is predicted to be negative.

True Positive Rate ( TPR )

It is also called as Sensitivity or Recall or Hit rate

TPR = TP / ( TP + FN )

Recall gives us an idea about when it’s actually yes, how often does it predict yes.

sklearn – recall

>>> from sklearn.metrics import recall_score
>>> recall_score(y_actual, y_pred)

Sensitivity computes the ratio of positive classes correctly detected. This metric gives how good the model is to recognize a positive class.

Ideally recall must be close to 1, that means there are near to 100% correctly predicted positive cases.

True Negative Rate ( TNR )

It is also called as Specificity.

TNR = TN / ( FP + TN )

Specificity computes the ratio of negative classes correctly detected. This metric gives how good the model is to recognize a negative class.

Specificity measure is used to determine the proportion of actual negative cases, which got predicted correctly.

Ideally Specificity must be close to 1, that means there are near to 100% correctly predicted negative cases.

False Positive Ratio ( FPR )

It is also called as fall-out.

FPR = FP / ( FP + TN )

It is the ratio of all negative classes predicted incorrectly, that is predicted as positive divided by all the classes actually as Negative

FPR = 1- TNR

Ideally FPR must be close to 0.

False Negative Ratio ( FNR )

It is also called as the miss rate

FNR = FN / ( FN+TP )

It is the ratio of all positive classes predicted incorrectly that is predicted as negative divided by all the classes actually as positive

FNR = 1 – TPR

Ideally FNR must be close to 0.

Accuracy

Accuracy tells us how often is the classifier correct?

Accuracy = ( TP + TN ) / ( TP + TN + FP + FN )

sklearn – Accuracy

>>> from sklearn.metrics import accuracy_score
>>> accuracy_score(y_actual, y_pred)

Ideally Accuracy must be close to 1.

Error rate

Error rate (ERR) is calculated as the number of all incorrect predictions divided by the total number of the dataset.

Error Rate = ( FP + FN ) / ( TP +TN + FP + FN )

Error Rate = 1 – Accuracy

Ideally Error rate must be close to 0.

Precision ( positive predictive value )

Precision is the number of True Positives divided by the number of True Positives and False Positives. Put another way, it is the number of positive predictions divided by the total number of positive class values predicted. It is also called the Positive Predictive Value (PPV).

Precision = TP / ( TP + FP )

sklearn – Precision

>>> from sklearn.metrics import precision_score
>>> precision_score(y_actual, y_pred)

Ideally Precision must be close to 1.

F1 Score

The F1 Score is the 2*((precision*recall)/(precision+recall)). The F1 score is the harmonic mean of the precision and recall.It is also called the F Score or the F Measure.

To put it in simple terms, the F1 score conveys the balance between the precision and the recall.

F1 Score = 2TP / ( 2TP + FP + FN )

sklearn – f1 score

>>> from sklearn.metrics import f1_score
>>> f1_score(y_actual, y_pred)

F1 score reaches its best value at 1, which means perfect precision and recall

Classification report

This function in sklearn provides the text summary of the precision, recall, F1 score for each class.

sklearn – Classification report

>>> from sklearn.metrics import classification_report
>>> classification_report(y_true, y_pred, labels=[1, 2, 3])

We will be evaluating performance parameter for some of the classification algorithm.

“Everything that civilization has to offer is a product of human intelligence. we cannot predict what we might achieve when this intelligence is magnified by the tools that AI may provide, but the eradication of war, disease, and poverty would be high on anyone’s list. Success in creating AI would be the biggest event in human history. Unfortunately, it might also be the last.” -Stephen Hawking.

Learn Distances in machine Learning : Go here

Distance metric are used to represent distances between any two data points. There are many distance metrics, but in this article, we will only be discussing a few widely used distance metrics.

If you are new to machine learning check out : Introduction to machine learning 

Type of Distances:

1. Manhattan distance
2. Euclidean distance
3. Minkowski distance
4. Hamming distance
5. Mahalanobis distance

Manhattan Distance

The Manhattan distance as the sum of absolute differences

In a plane with p1 at (x1, y1) and p2 at (x2, y2), it is |x1 – x2| + |y1 – y2|.

Example:

Lets calculate Distance between { 2, 3 } from { 3, 5 }

we put it in formula

|2-3|+|3-5| = |-1| + |-2| = 1+2 = 3

In 3-D space Manhattan Distance example: [{a, b, c}, {x, y, z}] :

Abs [a − x] + Abs [b − y] + Abs [c − z]

Euclidean distance

The Euclidean distance between two points in either the plane or 3-dimensional space measures the length of a segment connecting the two points.

Example:

Lets calculate Distance between { 2, 3 } from { 3, 5 }

we put it in formula

Minkowski distance

Minkowski distance is a generalization of the Euclidean distance and the Manhattan distance. Minkowski distance is applied in machine learning to find out distance similarity.

If C = 1 it is Manhattan Distance.

If C = 2 It is Euclidean distance.

Hamming distance

Hamming distance is a metric for comparing two binary data strings.

If ‘p’ and ‘q’ are binary strings then hamming distance is the number of bits required to convert from ‘p’ to ‘q’ or in other terms the number of different bits

Lets consider two binary string A = ‘010’ and B = ‘011’

Then if you change the 3 bit of string A ( 010 ) that is 0 to 1 the you get B ( 011 ) therefore the number of bits required or the number of different bits is 1 so the hamming distance for the above two string is 1 .

Mahalanobis Distance

Mahalanobis distance between two vectors, x and y, where S is the co-variance matrix.

co-variance of two feature indicated how values of two features are varying together. It measure how values of one feature are varying according to values of another feature.

The Mahalanobis distance uses inverse of co-variance matrix. The ‘T’ in equation indicates transpose of a matrix.

Some of the most important question we first ask about any topic are What ? Why ? How ?. You will find a lot of paid courses on Machine learning. Here I will creating a complete series of Blogs on Machine learning after that deep learning and Artificial Intelligence. So lets start with the base question of any topic. What is it ?

“ A computer would deserve to be called intelligent if it could deceive a human into believing that it was human “ – Alan Turing

What is Machine Learning ?

Machine Learning is a branch on science that deals with programming the system in such a way that they automatically learn and improve with experience.

To put it in simple words think of any task a human does like arranging a desk or shelf. First we put thinks in order how good they look. but, after some time we arrange it according to how frequently we use things on the shelf. Like, we put the book that we are reading in a place which is easily accessing an not behind a pile of Books having good cover page. This is done when you get the experience and come to a conclusion that accessibility is more important that appearance in case of arranging the books.

Similarly, In Machine Learning we use data for gaining experience ( Experience is ML might be as simple as changing value of few variable in a formula by using the data).

Learning Means recognizing and understanding the input data and making wise decisions based on the supplied data. Algorithm builds knowledge from specific data and past experience with the principles of statistics, probability theory, reinforcement learning, etc.

What are the two broad categories of Machine learning tasks ?

1. Supervised Learning

2. Unsupervised Learning

Supervised Learning

Supervised learning is where you have Input variables ( x ) and an output variable ( y ) and you use an algorithm to learn the mapping function from the input to the output.

y= f(x)

The goal is to approximate the mapping function so well that when you have new input data ( x ) that you can predict the output variable ( y ) from that data

In Supervised learning the model is trained on a labelled dataset. Labelled dataset is one which has both input and output parameters.

It is called supervised learning because the process of an algorithm learning from the training data set can be thought of as a teacher supervising the learning process

The algorithm iteratively makes prediction on the training data set and is corrected by the teacher ( correct answer ).

There are basically two type of supervised learning

1. Classification
2. Regression

1. Classification

The main goal of classification is to predict the target class ( Yes/No ), ( True/False ), ( animal/human )

These algorithms are used when the value of target output variable is discrete as { Yes| No }

Binary or binomial classification is the task of classifying the elements of a given set into two groups on the basis of a classification rule

Multi-class or multi-nomial classification is the problem of classifying instances into one of three or more classes

Example : classifying email to predict if the email is a Spam mail or not

2. Regression

Regression is a technique for predicting the value of dependent variable as a function of one or more independent variable in the presence of random error.

In simple terms Regression is used to predict continuous values. It is a statistical processes for estimating the relationships between a dependent variable and one or more independent variables.

Example: Predicting house prices of a particular area.

Unsupervised Learning

Unsupervised learning is where you only have input data ( x ) and no corresponding output variable

The goal for unsupervised learning is to model the underlying structure or distribution in the data in order to learn more about the data

It is called unsupervised learning because unlike supervised learning there is no Labelled data that means no correct answer or no teacher.

Unsupervised learning problems can be further grouped into two parts

1. Clustering
2. Association Rule Mining

1. Clustering

A clustering problem is where you want to discover the inherent grouping in the data such as grouping customers by purchasing behavior

In simple terms Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group are more similar to each other than to those in other groups

Example : Suppose you have data of all the products sales from your store and you want to assign priority to customer in order to boost sale by giving offers according to priority. you can use clustering algorithms to generate cluster of people and assign priority accordingly.

2. Association Rule Mining

An association rules learning problem is where you want to discover rules that describe large portions of your data, such as people that buy X also tend to by Y.

Association rule learning is a rule-based machine learning method for discovering interesting relations between variables in large databases.

Example: Market basket analysis – It is used in deciding the location of items inside a store. ex.If someone buys a packet of milk also tends to buy bread at the same time.

We will get into details of explanation of each algorithm and task Blog by Blog.

Now lets get to the second important question …

Why Machine Learning ?

Most of us know the answer to this question. I will try to example in too. Humans, most of the time have a lot of things to focus on. Now just image if we were made to do one and only one task and now if we could do that task without the need to take break or rest.

With the help of machine learning we can focus on a single task with more precision than human and machine do not need rest or time off. Machine learning is a way to reduce human efforts.

Some of the task are very complex for a human mind and some are easy but takes time. Example take simple calculation but with big number. Best of best would still require a few second. But, for machine 1 second is similar to eternity depending on the processing power the machine has.

The base reasons are machine is faster, Machine needs no rest and if we have the resources to make machine do our activity we could focus on much more important problem in the world.

There are a lot of reasons to this why statement. Give some of your reasons in comment section.

The final question

How does it work ?

I will be creating a Series of Blogs in which I will try and explain most of the models of machine learning and how to implement them in python and how the algorithm works. Stay Tuned…