{ "nbformat": 4, "nbformat_minor": 5, "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.11" }, "colab": { "provenance": [] } }, "cells": [ { "cell_type": "markdown", "id": "cell-0000", "metadata": {}, "source": [ "# K-Nearest Neighbors\n", "\n", "Your first classifier โ€” predict by asking the closest examples to vote, and learn why k and feature scaling change everything.\n", "\n", "*Part of the free [Machine Learning](https://ramadnsyh.dev/courses/machine-learning) course by [Muhammad Ramadiansyah](https://ramadnsyh.dev). This notebook is generated from the interactive lesson โ€” [read it online](https://ramadnsyh.dev/courses/machine-learning/k-nearest-neighbors).*" ] }, { "cell_type": "markdown", "id": "cell-0001", "metadata": {}, "source": [ "K-Nearest Neighbors (KNN) is machine learning at its most human: to classify\n", "something new, look at the most similar things you've seen before and go with\n", "the majority. You already do this โ€” guessing a stranger's home town from\n", "their accent, or a movie's genre from its poster. In this lesson you'll build\n", "that intuition into a working classifier and meet two ideas that follow you\n", "through all of ML: the complexity knob and feature scaling." ] }, { "cell_type": "markdown", "id": "cell-0002", "metadata": {}, "source": [ "## Play with it first\n", "\n", "KNN has no training phase to speak of โ€” it just stores the data. All the\n", "action happens at prediction time. Drag the test point around, change **k**\n", "(the number of neighbors consulted), and toggle the decision regions to see\n", "the boundary the model implies:" ] }, { "cell_type": "markdown", "id": "cell-0003", "metadata": {}, "source": [ "> ๐ŸŽ›๏ธ **Interactive demo** โ€” this section has a hands-on visualization in the web version of this lesson: [open it here](https://ramadnsyh.dev/courses/machine-learning/k-nearest-neighbors)." ] }, { "cell_type": "markdown", "id": "cell-0004", "metadata": {}, "source": [ "Two things to notice while exploring: with **k = 1** the decision regions are\n", "jagged and every stray training point gets its own little island, while with\n", "a large **k** the boundary becomes smooth and stubborn. Keep that trade-off\n", "in mind โ€” the rest of the lesson explains it." ] }, { "cell_type": "markdown", "id": "cell-0005", "metadata": {}, "source": [ "## How KNN decides\n", "\n", "Given a new point, KNN does three things:\n", "\n", "1. **Measure the distance** from the new point to every training point.\n", "2. **Find the k closest** training points.\n", "3. **Take a majority vote** of their labels (for regression: average their\n", " values).\n", "\n", "The standard distance is **Euclidean distance** โ€” the straight-line distance\n", "you'd measure with a ruler:\n", "\n", "`d(a, b) = sqrt( ฮฃ (aแตข โˆ’ bแตข)ยฒ )`\n", "\n", "scikit-learn's `KNeighborsClassifier` exposes this via the Minkowski\n", "parameter `p`: `p=2` is Euclidean, `p=1` is **Manhattan distance** (sum of\n", "absolute differences โ€” city-block travel). Both are worth trying when tuning." ] }, { "cell_type": "markdown", "id": "cell-0006", "metadata": {}, "source": [ "## Uniform vs distance-weighted voting\n", "\n", "By default every one of the k neighbors gets an equal vote\n", "(`weights=\"uniform\"`). With `weights=\"distance\"`, closer neighbors count\n", "more โ€” a neighbor right next to the test point can outvote several far-away\n", "ones. Distance weighting often helps when classes overlap, and it has a\n", "side effect worth knowing: on the training data itself, the nearest neighbor\n", "of a training point is *itself* at distance zero, so training accuracy\n", "becomes perfect. That's not a bug, but it means training accuracy tells you\n", "nothing โ€” evaluate on held-out data, as always." ] }, { "cell_type": "markdown", "id": "cell-0007", "metadata": {}, "source": [ "## The k knob: jagged vs smooth\n", "\n", "**k is a complexity dial**, just like tree depth in the last lesson:\n", "\n", "- **Small k (1โ€“3):** the model reacts to every individual point, including\n", " noise and mislabeled examples. Jagged boundary, high training accuracy,\n", " risk of **overfitting**.\n", "- **Large k:** predictions average over a wide neighborhood, smoothing away\n", " detail. Push k toward the size of the dataset and every prediction becomes\n", " the majority class โ€” **underfitting**.\n", "\n", "The right k lives in between and depends on the data, so we search for it.\n", "Here is KNN on the classic iris dataset (150 flowers, 4 measurements, 3\n", "species), scanning several values of k:" ] }, { "cell_type": "code", "id": "cell-0008", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "from sklearn.datasets import load_iris\n", "from sklearn.model_selection import train_test_split\n", "from sklearn.neighbors import KNeighborsClassifier\n", "\n", "X, y = load_iris(return_X_y=True)\n", "X_train, X_test, y_train, y_test = train_test_split(\n", " X, y, test_size=0.3, stratify=y, random_state=42\n", ")\n", "\n", "print(\" k train test\")\n", "for k in [1, 3, 5, 9, 15, 25, 51]:\n", " knn = KNeighborsClassifier(n_neighbors=k).fit(X_train, y_train)\n", " print(f\"{k:2d} {knn.score(X_train, y_train):.3f} \"\n", " f\"{knn.score(X_test, y_test):.3f}\")" ] }, { "cell_type": "markdown", "id": "cell-0009", "metadata": {}, "source": [ "The pattern: training accuracy is highest at k = 1 and decays as k grows,\n", "while test accuracy peaks somewhere in the middle. (Tip: prefer odd values of\n", "k for binary problems to avoid tied votes.)" ] }, { "cell_type": "markdown", "id": "cell-0010", "metadata": {}, "source": [ "## Distance models need scaled features\n", "\n", "Here's KNN's biggest gotcha. Distance treats all features as if they were in\n", "the same units. If one feature ranges 0โ€“1 and another ranges 0โ€“10,000, the\n", "big-range feature completely dominates the distance โ€” even if it's pure\n", "noise. Watch a useless feature destroy the model, and scaling rescue it:" ] }, { "cell_type": "code", "id": "cell-0011", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "import numpy as np\n", "from sklearn.model_selection import train_test_split\n", "from sklearn.neighbors import KNeighborsClassifier\n", "from sklearn.preprocessing import StandardScaler\n", "\n", "rng = np.random.default_rng(0)\n", "n = 300\n", "\n", "# Feature 1: informative (class 0 near 0, class 1 near 3)\n", "x1 = np.r_[rng.normal(0, 1, n // 2), rng.normal(3, 1, n // 2)]\n", "y = np.r_[np.zeros(n // 2, int), np.ones(n // 2, int)]\n", "# Feature 2: pure noise, but on a huge scale\n", "x2 = rng.normal(0, 1, n) * 1000\n", "X = np.c_[x1, x2]\n", "\n", "X_train, X_test, y_train, y_test = train_test_split(\n", " X, y, test_size=0.3, stratify=y, random_state=42\n", ")\n", "\n", "knn = KNeighborsClassifier(n_neighbors=5).fit(X_train, y_train)\n", "print(f\"raw features : test accuracy = {knn.score(X_test, y_test):.3f}\")\n", "\n", "scaler = StandardScaler().fit(X_train) # fit on TRAIN only\n", "X_train_s = scaler.transform(X_train)\n", "X_test_s = scaler.transform(X_test)\n", "\n", "knn = KNeighborsClassifier(n_neighbors=5).fit(X_train_s, y_train)\n", "print(f\"scaled features : test accuracy = {knn.score(X_test_s, y_test):.3f}\")" ] }, { "cell_type": "markdown", "id": "cell-0012", "metadata": {}, "source": [ "Unscaled, the noisy feature's huge magnitude drowns out the informative one\n", "and accuracy hovers near coin-flipping. After `StandardScaler` (subtract the\n", "mean, divide by the standard deviation โ€” both computed from training data\n", "only), every feature speaks at the same volume. Alternatives include\n", "`MinMaxScaler` (squash to a 0โ€“1 range) and `RobustScaler` (uses median and\n", "quartiles, resistant to outliers)." ] }, { "cell_type": "markdown", "id": "cell-0013", "metadata": {}, "source": [ "> **Fit the scaler on training data only**\n", "> \n", "> Computing the mean and standard deviation from the full dataset leaks\n", "> information about the test set into training. Always\n", "> fit the scaler on the training split, then apply the same transformation to\n", "> the test split. The next lesson's pipelines make this automatic." ] }, { "cell_type": "markdown", "id": "cell-0014", "metadata": {}, "source": [ "## Where KNN struggles\n", "\n", "KNN is a **lazy learner**: `fit` just stores the data, and all the work\n", "happens at `predict` time. That inverts the usual cost profile and brings\n", "some real weaknesses:\n", "\n", "- **Slow predictions.** Each prediction compares against (potentially) every\n", " training point. With millions of rows, that hurts exactly where speed\n", " matters โ€” in production.\n", "- **Memory hungry.** The model *is* the training set; nothing gets compressed\n", " into a small set of learned parameters.\n", "- **The curse of dimensionality.** With many features, all points become\n", " nearly equidistant from each other, and \"nearest\" stops meaning much.\n", " KNN shines with few, well-scaled, informative features.\n", "- **Sensitive to irrelevant features and scale**, as you just saw.\n", "\n", "Still, KNN is a superb first tool: no assumptions about the data's shape,\n", "naturally multiclass, and a strong sanity-check baseline before reaching for\n", "heavier machinery." ] }, { "cell_type": "markdown", "id": "cell-0015", "metadata": {}, "source": [ "### ๐Ÿ‹๏ธ Exercise โ€” Tune k, weights, and distance metric on iris\n", "\n", "best[0]:\n", " best = (score, (k, weights, p))\n", "\n", "print(f\"best test accuracy: {best[0]:.3f}\")\n", "print(f\"settings : k={best[1][0]}, weights={best[1][1]}, p={best[1][2]}\")\n", "`}\n", ">\n", "Extend the iris example into a small manual search: loop over odd `k` from 1\n", "to 25, both `weights` options (`\"uniform\"`, `\"distance\"`), and both distance\n", "metrics (`p=1` Manhattan, `p=2` Euclidean). Print the best test accuracy and\n", "the combination that achieved it. (In the next lesson you'll learn\n", "`GridSearchCV`, which does this search properly with cross-validation.)" ] }, { "cell_type": "code", "id": "cell-0016", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "# Your solution here" ] }, { "cell_type": "markdown", "id": "cell-0017", "metadata": {}, "source": [ "
โœ… Show solution\n", "\n", "```python\n", "from sklearn.datasets import load_iris\n", "from sklearn.model_selection import train_test_split\n", "from sklearn.neighbors import KNeighborsClassifier\n", "\n", "X, y = load_iris(return_X_y=True)\n", "X_train, X_test, y_train, y_test = train_test_split(\n", " X, y, test_size=0.3, stratify=y, random_state=42\n", ")\n", "\n", "best = (0, None)\n", "for k in range(1, 26, 2):\n", " for weights in [\"uniform\", \"distance\"]:\n", " for p in [1, 2]:\n", " knn = KNeighborsClassifier(n_neighbors=k, weights=weights, p=p)\n", " knn.fit(X_train, y_train)\n", " score = knn.score(X_test, y_test)\n", " if score > best[0]:\n", " best = (score, (k, weights, p))\n", "\n", "print(f\"best test accuracy: {best[0]:.3f}\")\n", "print(f\"settings : k={best[1][0]}, weights={best[1][1]}, p={best[1][2]}\")\n", "```\n", "\n", "
" ] }, { "cell_type": "markdown", "id": "cell-0018", "metadata": {}, "source": [ "Next up: scikit-learn pipelines โ€” how to chain scaling, encoding, and models\n", "into one leak-proof object you can tune end to end." ] } ] }