Objectives

Upon completion of this lesson, you will be able to:

  • define the kNN algorithm
  • know when to use kNN
  • tune the value of the hyper-parameter k
  • appreciate the need for feature normalization
  • recognize why outliers can be problematic for kNN

Introduction

k-Nearest Neighbors (k-NN or kNN) is a type of instance-based learning algorithm used in both classification and regression tasks. It is called ‘lazy learning’ as it doesn’t build a model but instead memorizes the training dataset. The prediction is done based on the “neighborhood” of data points in the dataset.

The basic steps involved in the k-NN algorithm are:

  1. Choose the number of k and a distance metric: The number of neighbors (k) and the type of distance are chosen as per the problem context. For example, you could choose k=3 and use Euclidean distance as the metric.

  2. Find the k nearest neighbors of the sample that you want to classify: For each data point that you want to make a prediction for, you identify the k points in the training dataset that are “closest” according to the chosen distance metric.

  3. Assign the label: For a classification problem, the new data point is assigned the class which has the majority among its k nearest neighbors. For a regression problem, the new data point could be assigned the mean value of its k nearest neighbors.

kNN is a simple algorithm that is easy to understand and implement. It works well with smaller datasets that have fewer dimensions (features), and where the data points are clearly separable. However, it may not be suitable for large, high-dimensional datasets, as the computation of distances can become very expensive. It is also sensitive to irrelevant or correlated features, which can impact the calculation of “closest” neighbors.

An important aspect of kNN is the choice of k. A small value of k can make the algorithm sensitive to noise, while a large value of k makes the boundaries between classes less distinct. Typically, the optimal value of k is selected using techniques such as cross-validation.

Examples of applications of kNN include recommendation systems, image recognition, and text categorization, among others.

Required Data Shaping

Prior to applying kNN, the data must be shaped:

  1. remove outliers
  2. impute or remove missing feature values
  3. normalize numeric features
  4. encode categorical features

Tutorials

In the narrated presentation below, Khoury Boston’s Dr. Schedlbauer provides an introduction to the kNN machine learning algorithm for predicting categorical target variables.

In the presentation below, Dr. Schedlbauer provides a more detailed look at kNN, its implementation, and the data preparation steps required for kNN.

Files & Resources

All Files for Lesson 3.410

References

No references.

Errata

None collected yet. Let us know.

LS0tCnRpdGxlOiAia05OIGZvciBDbGFzc2lmaWNhdGlvbiBhbmQgUmVncmVzc2lvbiIKcGFyYW1zOgogIGNhdGVnb3J5OiAzCiAgc3RhY2tzOiAwCiAgbnVtYmVyOiA0MTAKICB0aW1lOiA0NQogIGxldmVsOiBiZWdpbm5lcgogIHRhZ3M6IGtubixtYWNoaW5lIGxlYXJuaW5nLGNsYXNzaWZpY2F0aW9uLHJlZ3Jlc3Npb24KICBkZXNjcmlwdGlvbjogIkV4cGxhaW5zIHRoZSBrTk4gKGsgTmVhcmVzdCBOZWlnaGJvcikgbWFjaGluZSBsZWFybmluZwogICAgICAgICAgICAgICAgYWxnb3JpdGhtIGZvciBwcmVkaWN0aW5nIGEgY2F0ZWdvcmljYWwgdGFyZ2V0IHZhcmlhYmxlCiAgICAgICAgICAgICAgICAoY2xhc3NpZmljYXRpb24pIGFuZCBhIGNvbnRpbnVvdXMgbnVtZXJpYyB0YXJnZXQgdmFyaWFibGVzCiAgICAgICAgICAgICAgICAocmVncmVzc2lvbikuIgpkYXRlOiAiPHNtYWxsPmByIFN5cy5EYXRlKClgPC9zbWFsbD4iCmF1dGhvcjogIjxzbWFsbD5NYXJ0aW4gU2NoZWRsYmF1ZXI8L3NtYWxsPiIKZW1haWw6ICJtLnNjaGVkbGJhdWVyQG5ldS5lZHUiCmFmZmlsaXRhdGlvbjogIk5vcnRoZWFzdGVybiBVbml2ZXJzaXR5IgpvdXRwdXQ6IAogIGJvb2tkb3duOjpodG1sX2RvY3VtZW50MjoKICAgIHRvYzogdHJ1ZQogICAgdG9jX2Zsb2F0OiB0cnVlCiAgICBjb2xsYXBzZWQ6IGZhbHNlCiAgICBudW1iZXJfc2VjdGlvbnM6IGZhbHNlCiAgICBjb2RlX2Rvd25sb2FkOiB0cnVlCiAgICB0aGVtZTogc3BhY2VsYWIKICAgIGhpZ2hsaWdodDogdGFuZ28KLS0tCgotLS0KdGl0bGU6ICI8c21hbGw+YHIgcGFyYW1zJGNhdGVnb3J5YC5gciBwYXJhbXMkbnVtYmVyYDwvc21hbGw+PGJyLz48c3BhbiBzdHlsZT0nY29sb3I6ICMyRTQwNTM7IGZvbnQtc2l6ZTogMC45ZW0nPmByIHJtYXJrZG93bjo6bWV0YWRhdGEkdGl0bGVgPC9zcGFuPiIKLS0tCgpgYGB7ciBjb2RlPXhmdW46OnJlYWRfdXRmOChwYXN0ZTAoaGVyZTo6aGVyZSgpLCcvUi9faW5zZXJ0MkRCLlInKSksIGluY2x1ZGUgPSBGQUxTRX0KYGBgCgotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCiMjIE9iamVjdGl2ZXMKClVwb24gY29tcGxldGlvbiBvZiB0aGlzIGxlc3NvbiwgeW91IHdpbGwgYmUgYWJsZSB0bzoKCi0gICBkZWZpbmUgdGhlICprTk4qIGFsZ29yaXRobQotICAga25vdyB3aGVuIHRvIHVzZSAqa05OKgotICAgdHVuZSB0aGUgdmFsdWUgb2YgdGhlIGh5cGVyLXBhcmFtZXRlciAqayoKLSAgIGFwcHJlY2lhdGUgdGhlIG5lZWQgZm9yIGZlYXR1cmUgbm9ybWFsaXphdGlvbgotICAgcmVjb2duaXplIHdoeSBvdXRsaWVycyBjYW4gYmUgcHJvYmxlbWF0aWMgZm9yICprTk4qCgotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCiMjIEludHJvZHVjdGlvbgoKay1OZWFyZXN0IE5laWdoYm9ycyAoKmstTk4qIG9yICprTk4qKSBpcyBhIHR5cGUgb2YgaW5zdGFuY2UtYmFzZWQgbGVhcm5pbmcgYWxnb3JpdGhtIHVzZWQgaW4gYm90aCBjbGFzc2lmaWNhdGlvbiBhbmQgcmVncmVzc2lvbiB0YXNrcy4gSXQgaXMgY2FsbGVkICdsYXp5IGxlYXJuaW5nJyBhcyBpdCBkb2Vzbid0IGJ1aWxkIGEgbW9kZWwgYnV0IGluc3RlYWQgbWVtb3JpemVzIHRoZSB0cmFpbmluZyBkYXRhc2V0LiBUaGUgcHJlZGljdGlvbiBpcyBkb25lIGJhc2VkIG9uIHRoZSAibmVpZ2hib3Job29kIiBvZiBkYXRhIHBvaW50cyBpbiB0aGUgZGF0YXNldC4KClRoZSBiYXNpYyBzdGVwcyBpbnZvbHZlZCBpbiB0aGUgay1OTiBhbGdvcml0aG0gYXJlOgoKMS4gICoqQ2hvb3NlIHRoZSBudW1iZXIgb2YgayBhbmQgYSBkaXN0YW5jZSBtZXRyaWMqKjogVGhlIG51bWJlciBvZiBuZWlnaGJvcnMgKCprKikgYW5kIHRoZSB0eXBlIG9mIGRpc3RhbmNlIGFyZSBjaG9zZW4gYXMgcGVyIHRoZSBwcm9ibGVtIGNvbnRleHQuIEZvciBleGFtcGxlLCB5b3UgY291bGQgY2hvb3NlICprPTMqIGFuZCB1c2UgRXVjbGlkZWFuIGRpc3RhbmNlIGFzIHRoZSBtZXRyaWMuCgoyLiAgKipGaW5kIHRoZSAqayogbmVhcmVzdCBuZWlnaGJvcnMgb2YgdGhlIHNhbXBsZSB0aGF0IHlvdSB3YW50IHRvIGNsYXNzaWZ5Kio6IEZvciBlYWNoIGRhdGEgcG9pbnQgdGhhdCB5b3Ugd2FudCB0byBtYWtlIGEgcHJlZGljdGlvbiBmb3IsIHlvdSBpZGVudGlmeSB0aGUgKmsqIHBvaW50cyBpbiB0aGUgdHJhaW5pbmcgZGF0YXNldCB0aGF0IGFyZSAiY2xvc2VzdCIgYWNjb3JkaW5nIHRvIHRoZSBjaG9zZW4gZGlzdGFuY2UgbWV0cmljLgoKMy4gICoqQXNzaWduIHRoZSBsYWJlbCoqOiBGb3IgYSBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtLCB0aGUgbmV3IGRhdGEgcG9pbnQgaXMgYXNzaWduZWQgdGhlIGNsYXNzIHdoaWNoIGhhcyB0aGUgbWFqb3JpdHkgYW1vbmcgaXRzICprKiBuZWFyZXN0IG5laWdoYm9ycy4gRm9yIGEgcmVncmVzc2lvbiBwcm9ibGVtLCB0aGUgbmV3IGRhdGEgcG9pbnQgY291bGQgYmUgYXNzaWduZWQgdGhlIG1lYW4gdmFsdWUgb2YgaXRzICprKiBuZWFyZXN0IG5laWdoYm9ycy4KCiprTk4qIGlzIGEgc2ltcGxlIGFsZ29yaXRobSB0aGF0IGlzIGVhc3kgdG8gdW5kZXJzdGFuZCBhbmQgaW1wbGVtZW50LiBJdCB3b3JrcyB3ZWxsIHdpdGggc21hbGxlciBkYXRhc2V0cyB0aGF0IGhhdmUgZmV3ZXIgZGltZW5zaW9ucyAoZmVhdHVyZXMpLCBhbmQgd2hlcmUgdGhlIGRhdGEgcG9pbnRzIGFyZSBjbGVhcmx5IHNlcGFyYWJsZS4gSG93ZXZlciwgaXQgbWF5IG5vdCBiZSBzdWl0YWJsZSBmb3IgbGFyZ2UsIGhpZ2gtZGltZW5zaW9uYWwgZGF0YXNldHMsIGFzIHRoZSBjb21wdXRhdGlvbiBvZiBkaXN0YW5jZXMgY2FuIGJlY29tZSB2ZXJ5IGV4cGVuc2l2ZS4gSXQgaXMgYWxzbyBzZW5zaXRpdmUgdG8gaXJyZWxldmFudCBvciBjb3JyZWxhdGVkIGZlYXR1cmVzLCB3aGljaCBjYW4gaW1wYWN0IHRoZSBjYWxjdWxhdGlvbiBvZiAiY2xvc2VzdCIgbmVpZ2hib3JzLgoKQW4gaW1wb3J0YW50IGFzcGVjdCBvZiAqa05OKiBpcyB0aGUgY2hvaWNlIG9mICprKi4gQSBzbWFsbCB2YWx1ZSBvZiAqayogY2FuIG1ha2UgdGhlIGFsZ29yaXRobSBzZW5zaXRpdmUgdG8gbm9pc2UsIHdoaWxlIGEgbGFyZ2UgdmFsdWUgb2YgKmsqIG1ha2VzIHRoZSBib3VuZGFyaWVzIGJldHdlZW4gY2xhc3NlcyBsZXNzIGRpc3RpbmN0LiBUeXBpY2FsbHksIHRoZSBvcHRpbWFsIHZhbHVlIG9mICprKiBpcyBzZWxlY3RlZCB1c2luZyB0ZWNobmlxdWVzIHN1Y2ggYXMgY3Jvc3MtdmFsaWRhdGlvbi4KCkV4YW1wbGVzIG9mIGFwcGxpY2F0aW9ucyBvZiAqa05OKiBpbmNsdWRlIHJlY29tbWVuZGF0aW9uIHN5c3RlbXMsIGltYWdlIHJlY29nbml0aW9uLCBhbmQgdGV4dCBjYXRlZ29yaXphdGlvbiwgYW1vbmcgb3RoZXJzLgoKIyMgUmVxdWlyZWQgRGF0YSBTaGFwaW5nCgpQcmlvciB0byBhcHBseWluZyAqa05OKiwgdGhlIGRhdGEgbXVzdCBiZSBzaGFwZWQ6CgoxLiAgcmVtb3ZlIG91dGxpZXJzCjIuICBpbXB1dGUgb3IgcmVtb3ZlIG1pc3NpbmcgZmVhdHVyZSB2YWx1ZXMKMy4gIG5vcm1hbGl6ZSBudW1lcmljIGZlYXR1cmVzCjQuICBlbmNvZGUgY2F0ZWdvcmljYWwgZmVhdHVyZXMKCiMjIFNlZSBBbHNvCgotICAgWzMuMjA2IOKUhiBOb3JtYWxpemluZyBOdW1lcmljIEZlYXR1cmVzIGZvciBNYWNoaW5lIExlYXJuaW5nIEFsZ29yaXRobXNdKGh0dHA6Ly9hcnRpZmljaXVtLnVzL2xlc3NvbnMvMDMubWwvbC0zLTIwNi1mZWF0dXJlLW5vcm1hbGl6YXRpb24vbC0zLTIwNi5odG1sKQotICAgWzMuMjA3IOKUhiBFbmNvZGluZyBDYXRlZ29yaWNhbCBGZWF0dXJlc10oaHR0cDovL2FydGlmaWNpdW0udXMvbGVzc29ucy8wMy5tbC9sLTMtMjA3LWNhdGVnb3JpY2FsLWVuY29kaW5nL2wtMy0yMDcuaHRtbCkKLSAgIFszLjIwOCDilIYgRGlzdGFuY2UgTWVhc3VyZXNdKGh0dHA6Ly9hcnRpZmljaXVtLnVzL2xlc3NvbnMvMDMubWwvbC0zLTIwOC1kaXN0YW5jZS1tZWFzdXJlcy9sLTMtMjA4Lmh0bWwpCi0gICBbMy40MTEgLS0gU2ltcGxlIEltcGxlbWVudGF0aW9uIG9mIGtOTiBpbiBSXShodHRwOi8vYXJ0aWZpY2l1bS51cy9sZXNzb25zLzAzLm1sL2wtMy00MTEta25uLWltcGxlbWVudGF0aW9uLXIvbC0zLTQxMS5odG1sKQoKIyMgVHV0b3JpYWxzCgpJbiB0aGUgbmFycmF0ZWQgcHJlc2VudGF0aW9uIGJlbG93LCBLaG91cnkgQm9zdG9uJ3MgRHIuIFNjaGVkbGJhdWVyIHByb3ZpZGVzIGFuIGludHJvZHVjdGlvbiB0byB0aGUgKmtOTiogbWFjaGluZSBsZWFybmluZyBhbGdvcml0aG0gZm9yIHByZWRpY3RpbmcgY2F0ZWdvcmljYWwgdGFyZ2V0IHZhcmlhYmxlcy4KCmBgYHs9aHRtbH0KPGlmcmFtZSBzcmM9Imh0dHBzOi8vcGxheWVyLnZpbWVvLmNvbS92aWRlby84MzAzOTczNjM/aD00YjQxZmEwMDFhJmFtcDt0aXRsZT0wJmFtcDtieWxpbmU9MCZhbXA7cG9ydHJhaXQ9MCZhbXA7c3BlZWQ9MCZhbXA7YmFkZ2U9MCZhbXA7YXV0b3BhdXNlPTAmYW1wO3BsYXllcl9pZD0wJmFtcDthcHBfaWQ9NTg0NzkiIHdpZHRoPSI2NDAiIGhlaWdodD0iMzYwIiBmcmFtZWJvcmRlcj0iMCIgYWxsb3c9ImF1dG9wbGF5OyBmdWxsc2NyZWVuOyBwaWN0dXJlLWluLXBpY3R1cmUiIGFsbG93ZnVsbHNjcmVlbiB0aXRsZT0iVW5kZXJzdGFuZGluZyBrTk4iIGRhdGEtZXh0ZXJuYWw9IjEiPjwvaWZyYW1lPgpgYGAKSW4gdGhlIHByZXNlbnRhdGlvbiBiZWxvdywgRHIuIFNjaGVkbGJhdWVyIHByb3ZpZGVzIGEgbW9yZSBkZXRhaWxlZCBsb29rIGF0ICprTk4qLCBpdHMgaW1wbGVtZW50YXRpb24sIGFuZCB0aGUgZGF0YSBwcmVwYXJhdGlvbiBzdGVwcyByZXF1aXJlZCBmb3IgKmtOTiouCgpgYGB7PWh0bWx9CjxpZnJhbWUgc3JjPSJodHRwczovL3BsYXllci52aW1lby5jb20vdmlkZW8vODMwMzk3NDEwP2g9MzVkYjRkZmM4MCZhbXA7dGl0bGU9MCZhbXA7YnlsaW5lPTAmYW1wO3BvcnRyYWl0PTAmYW1wO3NwZWVkPTAmYW1wO2JhZGdlPTAmYW1wO2F1dG9wYXVzZT0wJmFtcDtwbGF5ZXJfaWQ9MCZhbXA7YXBwX2lkPTU4NDc5IiB3aWR0aD0iNjQwIiBoZWlnaHQ9IjM2MCIgZnJhbWVib3JkZXI9IjAiIGFsbG93PSJhdXRvcGxheTsgZnVsbHNjcmVlbjsgcGljdHVyZS1pbi1waWN0dXJlIiBhbGxvd2Z1bGxzY3JlZW4gdGl0bGU9IlRoZSBrTk4gTWFjaGluZSBMZWFybmluZyBBbGdvcml0aG0iIGRhdGEtZXh0ZXJuYWw9IjEiPjwvaWZyYW1lPgpgYGAKCi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKIyMgRmlsZXMgJiBSZXNvdXJjZXMKCmBgYHtyIHppcEZpbGVzLCBlY2hvPUZBTFNFfQp6aXBOYW1lID0gc3ByaW50ZigiTGVzc29uRmlsZXMtJXMtJXMuemlwIiwgCiAgICAgICAgICAgICAgICAgcGFyYW1zJGNhdGVnb3J5LAogICAgICAgICAgICAgICAgIHBhcmFtcyRudW1iZXIpCgp0ZXh0QUxpbmsgPSBwYXN0ZTAoIkFsbCBGaWxlcyBmb3IgTGVzc29uICIsIAogICAgICAgICAgICAgICBwYXJhbXMkY2F0ZWdvcnksIi4iLHBhcmFtcyRudW1iZXIpCgojIGRvd25sb2FkRmlsZXNMaW5rKCkgaXMgaW5jbHVkZWQgZnJvbSBfaW5zZXJ0MkRCLlIKa25pdHI6OnJhd19odG1sKGRvd25sb2FkRmlsZXNMaW5rKCIuIiwgemlwTmFtZSwgdGV4dEFMaW5rKSkKYGBgCgotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCiMjIFJlZmVyZW5jZXMKCk5vIHJlZmVyZW5jZXMuCgojIyBFcnJhdGEKCk5vbmUgY29sbGVjdGVkIHlldC4gTGV0IHVzIGtub3cuCgpgYGB7PWh0bWx9CjxzY3JpcHQgc3JjPSJodHRwczovL2Zvcm0uam90Zm9ybS5jb20vc3RhdGljL2ZlZWRiYWNrMi5qcyIgdHlwZT0idGV4dC9qYXZhc2NyaXB0Ij4KICBuZXcgSm90Zm9ybUZlZWRiYWNrKHsKICAgIGZvcm1JZDogIjIxMjE4NzA3Mjc4NDE1NyIsCiAgICBidXR0b25UZXh0OiAiRmVlZGJhY2siLAogICAgYmFzZTogImh0dHBzOi8vZm9ybS5qb3Rmb3JtLmNvbS8iLAogICAgYmFja2dyb3VuZDogIiNGNTkyMDIiLAogICAgZm9udENvbG9yOiAiI0ZGRkZGRiIsCiAgICBidXR0b25TaWRlOiAibGVmdCIsCiAgICBidXR0b25BbGlnbjogImNlbnRlciIsCiAgICB0eXBlOiBmYWxzZSwKICAgIHdpZHRoOiA3MDAsCiAgICBoZWlnaHQ6IDUwMCwKICAgIGlzQ2FyZEZvcm06IGZhbHNlCiAgfSk7Cjwvc2NyaXB0PgpgYGAKYGBge3IgY29kZT14ZnVuOjpyZWFkX3V0ZjgocGFzdGUwKGhlcmU6OmhlcmUoKSwnL1IvX2RlcGxveUtuaXQuUicpKSwgaW5jbHVkZSA9IEZBTFNFfQpgYGAK