close
Technology

K- Nearest Neighbors.

INTRODUCTION :

Most of the real-world problems that can be solved using machine learning are supervised learning problems. The problem of classifying an object into one of many categories comprises the classification task that comes under supervised learning. In this problem, we will address classification problems using a popular and simple algorithm called K-Nearest Neighbors. And we will be doing it all from scratch.

In General, most of the machine learning algorithms have three important traits viz Representation, Evaluation, and Optimization.

  • Representation– As its name suggests, it represents the intuition behind the algorithm, how it utilizes the training data to make predictions. Does it use training data to learn parameters to create a function and then make predictions giving rise to model-based algorithms, or does it rely on the instances in the training data giving rise to instance-based learning algorithms.
  • Evaluation – It refers to the evaluation criteria you use to compare two models. Examples: – precision, recall, f1 score, accuracy, etc.
  • Optimization – If your algorithm learns some parameters from the training data, then how do you arrive at the optimal values of parameters to get the best performing model. Examples: – Convex Optimization (Gradient Descent), Combinatorial Optimization (Greedy Search), Constrained Optimization (Linear Programming) etc.

Now let’s see the representation of K-Nearest Neighbors and then we will see what representation category it falls into.

KNN Representation :

Intuition behind KNN is very simple. Consider the scenario below:

Here points having the same color represents the same class as is evident from the figure.

So, what class would you assign to that star marked point?  The first thing that comes to mind is this “Star point seems closer to red points so let’s assign it, red class.”

That’s it!! That’s exactly what KNN does.

Since KNN relies on training instances to classify test points it’s an instance-based algorithm.

KNN Evaluation :

We will use the F1 score to evaluate our model’s performance and to choose the best model among different models having different hyperparameters. F1 score takes precision and recalls into account.

F1 score = (2 * (recall) * (precision)) / (recall + precision)

If this seems strange, then the F1 score is just the harmonic mean of recall and precision.

KNN Optimization :

since KNN does not use any cost function, so there is no optimization step in KNN. Now let’s focus on some small things.

What if many examples of different classes are close to our test point?

Again, intuitively we take the class whose frequency is highest among all the nearest points being considered.

We talked about “closeness” to the red points in the above example.

How do we define closeness?

Intuitively, the distance between two points can be used as the measure of closeness. It turns out that we can represent the distance between two points in many ways.

But the general form is this: –

it is called the nth norm of a vector.

So, we use the nth norm of distance vector as a metric of closeness between two points.

Here n can vary from 1 to ∞.

When we make n = ∞, the norm just calculates the maximum value of the vector. This can be derived by using limits and derivatives although we won’t be diving into that in this blog.

We are free to choose n as we wish. However, our mode performance will vary based on the value of n we choose. Hence n is one of the hyperparameters of the KNN model.

What’s K in KNN?

As the name suggests, K in K-Nearest Neighbors represents the number of training examples we consider to classify the test point.

K is another hyperparameter of the KNN model.

Now we are in a position to make our own KNN model from scratch.

The only Libraries we will be using are NumPy, and pandas and some plotting libraries like Plotly.

# Distance between two points
def get_distance(vec1, vec2, norm):
    diff_vect = []
    for i in range(len(vec1)):
        diff_vect.append(abs(vec1[i] – vec2[i]) ** norm)
    
    return sum(diff_vect) ** (1/norm)

# most frequent class
def most_frequent(classes):
    return max(set(classes), key = classes.count)

# F1 score calculation
def f1_score(y_pred, y_true):
    from sklearn.metrics import f1_score
    return f1_score(y_true, y_pred, average = ‘weighted’)



# Finding k nearest neighbors
def get_k_nearest(X_train, y_train, test_example, k, norm):
    distances = []
    
    for i in range(len(X_train)):
        d = get_distance(X_train[i], test_example, norm)
        distances.append((i, d))
     
    distances.sort(key = lambda x : x[1])
    k_nearest = distances[:k]
    classes = [y_train[point[0]][0] for point in k_nearest]
   
    return classes

# Making predictions
def predict(X_train, y_train, X_test, k, norm):
    y_pred = [ ]
    
    for test_example in X_test:
        k_nearest_points = get_k_nearest(X_train, y_train, test_example, k, norm)
        pred = most_frequent(k_nearest_points)
        y_pred.append(pred)
       
    return y_pred

Now let’s test our model on a dataset. We will also compare its performance with sciki-learn’s KNN implementation.

Here is the well-commented code that uses our functions (I have defined these functions in the helper module which I import as you can see)

# Importing Libraries

import numpy as np     # Numpy
import helper # Our helper module in which we defined all above written function from scratch
import pandas as pd    # Pandas

# Loading Data
X_df = pd.read_csv(‘train_X_knn.csv’, index_col = False) # Feature Matrix, does not contain true label column in it.
y_df = pd.read_csv(‘train_Y_knn.csv’, index_col = False, header = None) # True Label vector
y_df.columns = [‘Labels’]

dataset_df = pd.concat([X_df, y_df], axis = 1)

Our dataset is about different types of plastics found in the ocean, each characterized by its  chemical composition. There are a total of 6 types of plastics with labels ranging from 1 to 6

Here are the first 5 rows of our dataset.

#Let’s see the number of rows and columns in our data
X_df.shape, y_df.shape

>> ((160, 7), (160, 1))

We have 160 rows and 7 features.

Time to train our Model.

Since our model depends on the norm and value of k, so we try some combinations of these to get the best performance.

scores = [ ] # List of tuples (k_value, norm, f1_score) that will keep track of the score of the different model with different k and norm combination.

# Let’s try some different combinations of k and norm values to get the best possible parameters for our model.

for k in range(1, 6):
    for n in range(1, 6):
        y_pred = helper.predict(X_df.values, y_df.values, X_df.values, k = k, norm = n)
        score = helper.f1_score(y_pred, y_df.values)
        scores.append((k, n, np.mean(score)))

# Since we tried 25 combinations scores list is large. So lets find the best model with highest f1_score
best_model = max(scores, key = lambda x : x[2])

best_model

>> (1, 1, 1.0)

Let’s plot our scores as function of k and norm values

import IPython
import plotly.express as px

k_values, norm_values, f1_scores = [[tup[i] for tup in scores] for i in [0, 1, 2]]

px.scatter_3d(x = k_values, y = norm_values, z = f1_scores, labels = {‘x’ : ‘k values’, ‘y’ : ‘norm values’, ‘z’ : ‘f1 score’}, title = ‘Score of different KNN Models’, height = 700, width = 700)

From this plot, we can see that some models have f1 score of 1 (actually all models with k = 1 have that) and after that, the best f1 score is given by k = 3 which is highlighted in the plot. So which one should we choose?

Is k = 1 the best selection?

From the graph, we can see that all models with k = 1 have an f1_score of 1.0. So we should select k = 1.

Trap :

We trained our model on a complete dataset and are then predicting on the same data. So when we predict, each test-example is closest to itself in our training data. That is why k = 1 gives the best f1_score. But this may not be true for new data points. Hence it is not best to choose k = 1 otherwise our model will be highly variable for new data points. So we should choose a value larger than 1 that gives the best f1_score to reduce the variance of our model.

Selecting Model with k = 4 and norm = 1, our f1_score = 0.8325

Let’s compare with scikit-learn’s implementation

from sklearn.neighbors import KNeighborsClassifier
clf = KNeighborsClassifier(n_neighbors = 3, p = 1)

clf.fit(X_df.values, y_df.values.reshape(len(y_df), ))

KNeighborsClassifier(n_neighbors=3, p=1)

clf.score(X_df.values, y_df.values)

Scikit-Learn score -> 0.8375

So close, these show that our implementation is correct. Although scikit-learn’s implementation is much more sophisticated, still our KNN from scratch works reasonably well.

 Also, if you have been into machine learning for quite some time, you must have heard about preprocessing the data before feeding it to the algorithm.  In our KNN model, since we use distance metric, we could scale our data first so that no feature dominates over other features and could also do feature selection. but since this blog was aimed at writing knn from scratch and comparing its performance with scikit-learn i have not done it HERE.

When should we use KNN?

  • As we can see from implementation, KNN needs to store all the examples to make predictions, so if our dataset is very large then some other techniques like KD-Trees, Inverted Lists, and Locality Sensitive Hashing should be used. Again, these are heuristics and may not lead to true nearest neighbors.
  • We have calculated the distance between all points. This makes our implementation computationally very expensive. Hence above-mentioned heuristic techniques are used to get nearest neighbors.

This is all for this blog. Thanks for reading this far 🙂

Contributed by Vikas Choudhary.

Tags : technology

105 Comments

  1. Hi there, yup this paragraph is truly pleasant and
    I have learned lot of things from it regarding blogging.
    thanks.

    Feel free to visit my web site … Carl

  2. I think this is one of the most vital info for me.

    And i’m glad reading your article. But want to remark on few general things, The web site
    style is ideal, the articles is really excellent : D.
    Good job, cheers

    My web site: private instagram viewer

  3. Having read this I believed it was extremely informative.

    I appreciate you spending some time and effort to put this information together.
    I once again find myself spending way too much time both reading and
    posting comments. But so what, it was still worth it!

    My web blog :: instagram private account viewer

  4. Hello there! This post could not be written much better!
    Going through this article reminds me of my previous roommate!

    He always kept talking about this. I’ll send this article to him.
    Pretty sure he will have a very good read.
    Thanks for sharing!

    Also visit my blog :: instaviewy

  5. Do you mind if I quote a few of your articles as long as I provide
    credit and sources back to your blog? My blog is in the
    very same niche as yours and my visitors would definitely benefit from a lot of the information you present here.

    Please let me know if this okay with you. Many thanks!

    my web-site private instagram viewer

  6. An impressive share! I have just forwarded this onto a friend who had been doing a little research on this.
    And he actually ordered me breakfast due to the fact that I discovered
    it for him… lol. So let me reword this….
    Thank YOU for the meal!! But yeah, thanx for spending some time to talk about this matter here on your
    site.

    My site: instagram private unlocker

  7. I loved as much as you will receive carried out right here.

    The sketch is tasteful, your authored material stylish. nonetheless, you command get got
    an shakiness over that you wish be delivering the following.

    unwell unquestionably come more formerly again since exactly the same
    nearly a lot often inside case you shield this increase.

    Here is my web-site privateinstaviewer.com

  8. Have you ever thought about including a little bit more than just your articles?

    I mean, what you say is fundamental and everything. However imagine if you
    added some great graphics or videos to give your posts more,
    “pop”! Your content is excellent but with images and videos,
    this website could undeniably be one of the best in its field.

    Superb blog!

    My site … private insta

  9. I have read several just right stuff here.
    Definitely value bookmarking for revisiting. I surprise
    how much effort you set to make such a great informative website.

    my webpage … Michaela

  10. Ahaa, its nice discussion regarding this piece of writing at
    this place at this website, I have read all
    that, so at this time me also commenting at
    this place.

    Here is my web blog; Marcella

  11. For hottest news you have to go to see the web and on world-wide-web I found this website as a most excellent website for most recent updates.

    Also visit my web site; Valarie

  12. It is in point of fact a nice and helpful piece of information.
    I am glad that you shared this helpful information with us.

    Please stay us up to date like this. Thank you for sharing.

    My web blog – Eugene

  13. What’s Taking place i am new to this, I stumbled upon this I have found It positively useful
    and it has aided me out loads. I’m hoping to give a contribution &
    help different customers like its aided me. Good job.

    Here is my web-site Opal

  14. Howdy just wanted to give you a quick heads up.
    The text in your article seem to be running off the screen in Firefox.
    I’m not sure if this is a format issue or something to do with internet
    browser compatibility but I figured I’d post to let you know.
    The design look great though! Hope you get the issue solved soon. Thanks

    Also visit my web-site – Janelle

  15. I think this is among the most important info for
    me. And i’m glad reading your article. But should remark
    on few general things, The site style is wonderful, the articles is really excellent : D.
    Good job, cheers

    my blog – Laura

  16. You ought to be a part of a contest for one of the greatest sites on the web.
    I most certainly will highly recommend this blog!

    Look at my blog … Riley

  17. When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get several e-mails with the same comment.
    Is there any way you can remove me from that service? Thanks a lot!

    my web blog – Rayford

  18. You actually make it seem so easy with your presentation but I
    find this matter to be actually something that
    I think I would never understand. It seems too complex and very broad for me.
    I’m looking forward for your next post, I’ll try to get the hang of it!

    Visit my web page :: instagram private unlocker

  19. I was wondering if you ever thought of changing the structure of
    your site? Its very well written; I love what
    youve got to say. But maybe you could a little more in the way
    of content so people could connect with it better.
    Youve got an awful lot of text for only having 1 or two images.
    Maybe you could space it out better?

    My blog post – Adriene

  20. Hi there would you mind sharing which blog platform you’re working with?

    I’m going to start my own blog in the near future but I’m having a difficult
    time making a decision between BlogEngine/Wordpress/B2evolution and
    Drupal. The reason I ask is because your design and style seems different then most
    blogs and I’m looking for something completely unique.
    P.S Sorry for getting off-topic but I had to ask!

    Also visit my web page: Judi

  21. I’m gone to tell my little brother, that he should also pay a visit
    this website on regular basis to get updated from most up-to-date news.

    Feel free to surf to my blog; Weldon

  22. I enjoy what you guys are up too. This sort of clever work and coverage!
    Keep up the excellent works guys I’ve included you guys to
    blogroll.

    My page … Fletcher

  23. I pay a quick visit each day some web sites and sites
    to read posts, except this web site offers quality based articles.

    Feel free to visit my blog … Katie

  24. Normally I do not read post on blogs, but I
    wish to say that this write-up very pressured me to check out and do so!
    Your writing style has been surprised me.
    Thanks, very nice article.

    Feel free to visit my site: Marvin

  25. I blog frequently and I genuinely appreciate your information.
    Your article has really peaked my interest. I will take
    a note of your website and keep checking for new details about once per week.

    I subscribed to your RSS feed too.

    Also visit my web page … Donna

  26. For newest information you have to visit world wide web and on web I found this website as a best site for
    most up-to-date updates.

    My page: Eve

  27. Hurrah! After all I got a blog from where I
    be able to really obtain valuable data concerning my study and knowledge.

    Feel free to surf to my website: Brian

  28. My partner and I stumbled over here by a different web address and thought I may as
    well check things out. I like what I see so i am just following you.

    Look forward to checking out your web page repeatedly.

    Feel free to visit my web blog; private instagram viewer

  29. Hey There. I found your blog using msn. This is a
    very well written article. I will be sure to bookmark it and return to read more of your useful information. Thanks for the
    post. I’ll definitely return.

    Stop by my website … Terrence

  30. Hey! I could have sworn I’ve been to this site before but after
    reading through some of the post I realized it’s new to me.
    Anyhow, I’m definitely happy I found it and I’ll be book-marking and checking back frequently!

    Visit my blog Ruby

  31. Hey very cool site!! Guy .. Beautiful .. Superb ..
    I will bookmark your website and take the feeds
    also? I’m satisfied to search out a lot of useful info right here in the put up,
    we want work out more techniques in this regard,
    thank you for sharing. . . . . .

    My web-site; Joan

  32. I blog frequently and I seriously appreciate your information. This great article has truly
    peaked my interest. I will take a note of your
    blog and keep checking for new information about once a week.
    I subscribed to your Feed as well.

    Look at my web-site instaviewz

  33. We’re a group of volunteers and opening a brand new scheme in our community.
    Your site offered us with helpful information to work on. You have performed a formidable activity and our entire group
    shall be grateful to you.

    Review my blog post … private profile viewer

  34. hello there and thank you for your information – I have certainly picked up anything new from
    right here. I did however expertise several technical points using this
    web site, as I experienced to reload the website many
    times previous to I could get it to load correctly. I had been wondering if your web hosting is OK?

    Not that I’m complaining, but sluggish loading instances times will often affect
    your placement in google and can damage your high-quality score if advertising and marketing with Adwords.
    Anyway I’m adding this RSS to my e-mail and can look out for a
    lot more of your respective interesting content.
    Ensure that you update this again soon.

    Look into my web site – Harris

  35. For the reason that the admin of this web page is working,
    no hesitation very shortly it will be well-known, due to its quality contents.

    Also visit my web blog: Bud

  36. I have been exploring for a little for any high quality articles or blog
    posts on this sort of house . Exploring in Yahoo I eventually stumbled upon this website.
    Studying this info So i’m satisfied to convey that I have a very excellent uncanny feeling
    I found out exactly what I needed. I most certainly will make sure
    to do not fail to remember this web site and provides it a look on a
    constant basis.

    My website; Shaunte

  37. whoah this blog is magnificent i really like
    studying your posts. Keep up the good work!
    You already know, lots of people are hunting around for this info, you can aid them
    greatly.

    Feel free to surf to my website Angelika

  38. Excellent post. Keep writing such kind of information on your page.
    Im really impressed by it.
    Hello there, You have done a fantastic job. I will certainly digg it and personally suggest to my friends.
    I am sure they will be benefited from this web site.

    Here is my homepage … Zelda

  39. of course like your web-site but you have
    to take a look at the spelling on several of your posts.
    Several of them are rife with spelling issues and I in finding it very bothersome to inform the truth
    on the other hand I’ll surely come back again.

    Here is my page … Trevor

  40. Nice post. I was checking continuously this blog and I’m impressed!

    Very useful information specifically the last part 🙂 I care
    for such info much. I was looking for this certain information for a long
    time. Thank you and best of luck.

    Here is my webpage – Cheri

  41. Hey there! I’m at work browsing your blog from my new iphone 3gs!
    Just wanted to say I love reading through your blog and look forward to all
    your posts! Keep up the great work!

    Also visit my web site :: Georgetta

  42. Howdy! This article couldn’t be written any better!

    Going through this article reminds me of my previous roommate!
    He always kept talking about this. I am going to forward this post to him.
    Fairly certain he’s going to have a very good read. Thanks for sharing!

    Feel free to visit my web-site … private instagram profile viewer

  43. Nice post. I was checking continuously this blog and I’m impressed!
    Very useful info particularly the last part 🙂 I care for such
    info a lot. I was seeking this certain information for a long time.

    Thank you and good luck.

    My web page – private instagram viewer

  44. Hello very cool site!! Guy .. Beautiful .. Amazing ..
    I will bookmark your blog and take the feeds also? I’m glad
    to search out numerous useful info right here in the put up,
    we want work out extra strategies in this regard, thanks for sharing.
    . . . . .

    my webpage … instagram private kullanıcı adları

  45. Generally I do not learn post on blogs, but I wish to say that this write-up very compelled me to
    try and do so! Your writing style has been amazed me.
    Thanks, quite great post.

    Also visit my web-site :: watchinsta

  46. It’s appropriate time to make some plans for the future and
    it’s time to be happy. I have read this post and if I could I desire to suggest you few interesting things or advice.
    Perhaps you could write next articles referring to this article.

    I want to read more things about it!

    Also visit my web site: private instagram bios funny

  47. Hello just wanted to give you a quick heads up. The text in your
    post seem to be running off the screen in Opera. I’m not sure if
    this is a formatting issue or something to do with browser compatibility but I thought I’d post to let you
    know. The layout look great though! Hope you get the problem
    fixed soon. Kudos

    My homepage … Justine

  48. I’m impressed, I have to admit. Seldom do I come across a blog that’s both educative and
    interesting, and without a doubt, you’ve hit the nail on the
    head. The problem is an issue that too few people are speaking intelligently about.
    I am very happy I came across this during my hunt for something
    concerning this.

    My web page: Tim

  49. Its like you read my mind! You appear to know so much about
    this, like you wrote the book in it or something. I think that you can do with
    some pics to drive the message home a little bit, but instead of that,
    this is excellent blog. A fantastic read. I will certainly be back.

    Check out my web blog – Felix

  50. Heya i’m for the first time here. I found this board and I to find It truly useful &
    it helped me out much. I hope to provide something
    again and aid others such as you helped me.

    Feel free to surf to my blog post; Gabriel

  51. Wonderful web site. A lot of helpful info here. I am sending it to some buddies
    ans also sharing in delicious. And of course, thanks to your
    effort!

    Here is my web blog :: Arnette

  52. Hello would you mind letting me know which webhost you’re using?

    I’ve loaded your blog in 3 completely different internet browsers and I must say
    this blog loads a lot faster then most. Can you recommend a good hosting provider at a honest price?
    Kudos, I appreciate it!

    Also visit my webpage; Timothy

  53. It’s the best time to make some plans for the long run and it’s
    time to be happy. I’ve read this post and if I may I want to suggest you some interesting issues or advice.

    Maybe you could write subsequent articles referring to this article.
    I want to learn more things about it!

    Here is my web blog: Shaun

  54. I know this website provides quality based articles and extra material, is
    there any other site which presents these kinds
    of data in quality?

    Also visit my web-site: Kendrick

  55. Great blog right here! Also your site a lot up fast!
    What web host are you the use of? Can I get your affiliate link to your host?
    I desire my web site loaded up as quickly as yours lol

    Feel free to surf to my blog – Ashli

  56. Aw, this was an exceptionally good post. Finding the time and actual effort to make a top notch article… but what can I say… I
    procrastinate a whole lot and don’t seem to get nearly anything done.

    My homepage – Freddy

  57. I loved as much as you will receive carried out right here.
    The sketch is tasteful, your authored subject matter stylish.
    nonetheless, you command get got an impatience over that you wish
    be delivering the following. unwell unquestionably come further
    formerly again since exactly the same nearly a lot often inside case you shield this hike.

    Also visit my site Concetta

  58. Excellent blog here! Also your site loads
    up very fast! What web host are you using? Can I get your affiliate link to
    your host? I wish my web site loaded up as quickly as yours lol

    My website Regina

  59. I’m not that much of a internet reader to be honest but your blogs really nice, keep it up!
    I’ll go ahead and bookmark your website to come back in the future.
    Many thanks

    Here is my web page … Helena

  60. Greetings from Florida! I’m bored at work so I decided to browse your blog on my iphone during lunch break.
    I really like the knowledge you present here and can’t wait to take a look when I get home.

    I’m surprised at how quick your blog loaded
    on my phone .. I’m not even using WIFI, just 3G ..

    Anyways, amazing blog!

    my page :: Teresa

  61. Hi there to all, how is everything, I think every one is getting more
    from this website, and your views are fastidious designed for new people.

    Also visit my website Mellissa

  62. Great post. I used to be checking constantly this blog and I am impressed!
    Very useful information specifically the remaining phase :
    ) I care for such info a lot. I used to be looking for this particular information for a long time.
    Thanks and best of luck.

    My web-site: Veta

  63. Hi all, here every person is sharing such experience, therefore it’s fastidious to read this web site,
    and I used to pay a visit this weblog everyday.

    Also visit my webpage – Lan

  64. Pretty great post. I simply stumbled upon your weblog and
    wished to mention that I have truly loved surfing around your blog posts.

    After all I will be subscribing on your rss feed and I hope you write
    again soon!

    My blog; Arden

  65. Have you ever considered about including a little bit more than just your articles?
    I mean, what you say is fundamental and everything. But just imagine if
    you added some great images or video clips to give your posts more,
    “pop”! Your content is excellent but with pics and video clips, this
    blog could definitely be one of the greatest in its niche.

    Very good blog!

    Here is my website :: Dante

  66. Hello, i think that i saw you visited my website thus i came to “return the favor”.I’m
    attempting to find things to improve my site!I suppose its ok
    to use some of your ideas!!

    Also visit my website – Alice

  67. When someone writes an paragraph he/she keeps the idea of a
    user in his/her brain that how a user can know it.
    Therefore that’s why this piece of writing is perfect.
    Thanks!

    Feel free to visit my site … musa basjoo

  68. Excellent post. I was checking constantly this blog and I
    am impressed! Extremely useful information specially the last part :
    ) I care for such info much. I was seeking this particular information for a long time.
    Thank you and good luck.

    Review my web site :: Phoenix Roebelenii

  69. Thanks for every other magnificent post. Where else may anybody get that
    kind of info in such an ideal manner of writing?
    I have a presentation next week, and I’m at the look for such info.

    Here is my web-site … foul vaginal odor

  70. I discovered your blog site on google and check a few of your early posts. Continue to keep up the very good operate. I just additional up your RSS feed to my MSN News Reader. Seeking forward to reading more from you later on!…

  71. Thanks to GTA 5 money defect from where you can add money to your line from
    any of your browsers, and you are completely unhazardous making use of the hacking tool
    and can make gambler resources to freedom the gritty.

    Feel free to surf to my page wings io

Leave a Response

You cannot copy the content of this page!