{
 "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": [
    "# Clustering with K-Means\n",
    "\n",
    "Learn without labels — step through the K-Means loop, choose k with the elbow and silhouette methods, and know when to reach for DBSCAN instead.\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/clustering).*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0001",
   "metadata": {},
   "source": [
    "Everything so far had a supervisor: every row came with the right answer, and\n",
    "the model's job was to match it. Clustering removes the answer key. You hand\n",
    "the algorithm raw points and ask, \"which of these belong together?\" In this\n",
    "lesson you'll run the K-Means loop by hand, learn how to pick the number of\n",
    "clusters, and see exactly where K-Means breaks — and what to use when it does."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0002",
   "metadata": {},
   "source": [
    "## Learning without labels\n",
    "\n",
    "In supervised learning, \"good\" means \"close to the labels\". Without labels,\n",
    "we need a different definition, and clustering uses geometry: a good grouping\n",
    "puts similar points in the same cluster and dissimilar points in different\n",
    "ones. That makes clustering genuinely useful when labels don't exist yet —\n",
    "segmenting customers, grouping documents by theme, compressing colors in an\n",
    "image — but it also means *you* have to judge whether the clusters mean\n",
    "anything. The algorithm will always give you groups; it can't tell you if\n",
    "they matter."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0003",
   "metadata": {},
   "source": [
    "## The K-Means loop\n",
    "\n",
    "K-Means is the workhorse. You choose **k**, the number of clusters, and the\n",
    "algorithm alternates two moves until nothing changes:\n",
    "\n",
    "1. **Assign** — give each point to its nearest centroid\n",
    "2. **Update** — move each centroid to the mean of its assigned points\n",
    "\n",
    "Try it yourself. Step through the iterations below and watch the two moves\n",
    "alternate — and keep an eye on the inertia readout as the centroids settle:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0004",
   "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/clustering)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0005",
   "metadata": {},
   "source": [
    "A few things you probably noticed: the assignments and centroids stabilize\n",
    "after just a handful of iterations, the inertia only ever goes down, and if\n",
    "you re-initialize, the final clusters can differ. K-Means is only guaranteed\n",
    "to find a *local* optimum, which is why scikit-learn's `KMeans` runs several\n",
    "random restarts (`n_init`) and keeps the best one by default."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0006",
   "metadata": {},
   "source": [
    "## Inertia, and why it always drops with k\n",
    "\n",
    "**Inertia** is the quantity K-Means minimizes: the sum of squared distances\n",
    "from each point to its own centroid. Lower inertia means tighter clusters —\n",
    "but be careful using it to choose k. Adding a cluster can only ever reduce\n",
    "inertia (in the extreme, k = n gives inertia 0, with every point as its own\n",
    "\"cluster\"). So you can't just pick the k with the lowest inertia; you look\n",
    "for the point of **diminishing returns**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0007",
   "metadata": {},
   "source": [
    "## Choosing k: elbow and silhouette\n",
    "\n",
    "The **elbow method** plots inertia against k and looks for the bend — the k\n",
    "after which extra clusters stop paying for themselves. The **silhouette\n",
    "score** measures, for each point, how much closer it is to its own cluster\n",
    "than to the nearest other cluster (from −1 to +1, higher is better) — and\n",
    "unlike inertia, it *peaks* at a good k instead of always decreasing:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0008",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import make_blobs\n",
    "from sklearn.cluster import KMeans\n",
    "from sklearn.metrics import silhouette_score\n",
    "\n",
    "X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.9, random_state=42)\n",
    "\n",
    "ks = range(2, 10)\n",
    "inertias, silhouettes = [], []\n",
    "for k in ks:\n",
    "    km = KMeans(n_clusters=k, n_init=5, random_state=42).fit(X)\n",
    "    inertias.append(km.inertia_)\n",
    "    silhouettes.append(silhouette_score(X, km.labels_))\n",
    "\n",
    "fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9, 3.5))\n",
    "ax1.plot(ks, inertias, \"o-\")\n",
    "ax1.set_xlabel(\"k\"); ax1.set_ylabel(\"Inertia\"); ax1.set_title(\"Elbow\")\n",
    "ax2.plot(ks, silhouettes, \"o-\", color=\"tab:orange\")\n",
    "ax2.set_xlabel(\"k\"); ax2.set_ylabel(\"Silhouette\"); ax2.set_title(\"Silhouette\")\n",
    "plt.tight_layout()\n",
    "plt.show()\n",
    "\n",
    "best_k = list(ks)[silhouettes.index(max(silhouettes))]\n",
    "print(f\"Best k by silhouette: {best_k}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0009",
   "metadata": {},
   "source": [
    "The data was generated with 4 blobs, and both diagnostics agree: the elbow\n",
    "bends at 4 and the silhouette peaks there. On real data the signals are\n",
    "rarely this clean — treat them as evidence, not verdicts, and sanity-check\n",
    "the clusters against domain knowledge."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0010",
   "metadata": {},
   "source": [
    "> **Scale your features first**\n",
    "> \n",
    "> K-Means is built on Euclidean distance, so a feature measured in thousands\n",
    "> (income) will completely drown one measured in single digits (number of\n",
    "> purchases). Put a `StandardScaler` in front of `KMeans` — in a `Pipeline` —\n",
    "> essentially every time you cluster real data."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0011",
   "metadata": {},
   "source": [
    "## Where K-Means fails\n",
    "\n",
    "The assign-to-nearest-centroid rule carves space into convex regions, so\n",
    "K-Means silently assumes clusters are **roughly spherical, similar in size,\n",
    "and separable by straight boundaries**. Give it two interleaved crescents and\n",
    "it fails confidently:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0012",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import make_moons\n",
    "from sklearn.cluster import KMeans\n",
    "\n",
    "X, y_true = make_moons(n_samples=300, noise=0.06, random_state=42)\n",
    "km = KMeans(n_clusters=2, n_init=5, random_state=42)\n",
    "labels = km.fit_predict(X)\n",
    "\n",
    "fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9, 3.8))\n",
    "ax1.scatter(X[:, 0], X[:, 1], c=y_true, s=12, cmap=\"coolwarm\")\n",
    "ax1.set_title(\"True structure: two moons\")\n",
    "ax2.scatter(X[:, 0], X[:, 1], c=labels, s=12, cmap=\"coolwarm\")\n",
    "c = km.cluster_centers_\n",
    "ax2.scatter(c[:, 0], c[:, 1], c=\"white\", edgecolors=\"k\", s=120, linewidths=2)\n",
    "ax2.set_title(\"K-Means: splits them wrong\")\n",
    "for ax in (ax1, ax2):\n",
    "    ax.set_aspect(\"equal\")\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0013",
   "metadata": {},
   "source": [
    "K-Means slices the moons with a straight cut because that's all it *can* do.\n",
    "Other classic failure modes: clusters with very different densities or sizes\n",
    "(the big cluster \"steals\" points from the small one), outliers dragging\n",
    "centroids around, and non-numeric data you can't take a mean of (variants\n",
    "like K-Modes and K-Prototypes exist for that)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0014",
   "metadata": {},
   "source": [
    "## Beyond K-Means: DBSCAN and agglomerative clustering\n",
    "\n",
    "Two alternatives cover most of what K-Means can't:\n",
    "\n",
    "- **DBSCAN** grows clusters from dense regions: points with enough neighbors\n",
    "  within radius `eps` seed a cluster, and it expands through connected dense\n",
    "  areas. It finds arbitrarily shaped clusters, doesn't need k, and labels\n",
    "  sparse points as noise (`-1`).\n",
    "- **Agglomerative clustering** starts with every point as its own cluster and\n",
    "  repeatedly merges the closest pair, building a hierarchy (visualized as a\n",
    "  dendrogram). With `linkage=\"single\"` (\"closest points\" distance) it chains\n",
    "  along curved shapes nicely."
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0015",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import make_moons\n",
    "from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering\n",
    "\n",
    "X, _ = make_moons(n_samples=300, noise=0.06, random_state=42)\n",
    "\n",
    "models = [\n",
    "    (\"K-Means\", KMeans(n_clusters=2, n_init=5, random_state=42)),\n",
    "    (\"DBSCAN (eps=0.2)\", DBSCAN(eps=0.2)),\n",
    "    (\"Agglomerative (single)\", AgglomerativeClustering(n_clusters=2, linkage=\"single\")),\n",
    "]\n",
    "\n",
    "fig, axes = plt.subplots(1, 3, figsize=(11, 3.6))\n",
    "for ax, (name, model) in zip(axes, models):\n",
    "    labels = model.fit_predict(X)\n",
    "    ax.scatter(X[:, 0], X[:, 1], c=labels, s=10, cmap=\"viridis\")\n",
    "    ax.set_title(name)\n",
    "    ax.set_aspect(\"equal\")\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0016",
   "metadata": {},
   "source": [
    "Both alternatives recover the moons perfectly. So why is K-Means still the\n",
    "default? It's fast, it scales to millions of points, its clusters come with\n",
    "centroids you can interpret and reuse (as you'll see next lesson), and many\n",
    "real datasets — especially after scaling — really are blob-shaped. DBSCAN's\n",
    "weakness is choosing `eps` and handling clusters of varying density;\n",
    "agglomerative clustering is O(n²) and struggles past tens of thousands of\n",
    "points."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0017",
   "metadata": {},
   "source": [
    "### 🏋️ Exercise — Break K-Means, then fix the diagnosis\n",
    "\n",
    "Generate blobs with **very different spreads**: 3 centers with\n",
    "`cluster_std=[0.5, 2.5, 0.5]` (400 points, `random_state=7`). Run K-Means\n",
    "with the *correct* k = 3, then compare its labels to the true ones with a\n",
    "side-by-side scatter plot and compute the silhouette score of both labelings.\n",
    "Which failure mode from the lesson are you seeing?"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0018",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Your solution here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0019",
   "metadata": {},
   "source": [
    "<details><summary>✅ Show solution</summary>\n",
    "\n",
    "```python\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import make_blobs\n",
    "from sklearn.cluster import KMeans\n",
    "from sklearn.metrics import silhouette_score\n",
    "\n",
    "X, y_true = make_blobs(n_samples=400, centers=3,\n",
    "                       cluster_std=[0.5, 2.5, 0.5], random_state=7)\n",
    "\n",
    "km = KMeans(n_clusters=3, n_init=5, random_state=42)\n",
    "labels = km.fit_predict(X)\n",
    "\n",
    "print(f\"silhouette (kmeans labels): {silhouette_score(X, labels):.3f}\")\n",
    "print(f\"silhouette (true labels)  : {silhouette_score(X, y_true):.3f}\")\n",
    "\n",
    "fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9, 3.8))\n",
    "ax1.scatter(X[:, 0], X[:, 1], c=y_true, s=10)\n",
    "ax1.set_title(\"True labels\")\n",
    "ax2.scatter(X[:, 0], X[:, 1], c=labels, s=10)\n",
    "ax2.set_title(\"K-Means labels\")\n",
    "plt.tight_layout()\n",
    "plt.show()\n",
    "\n",
    "# The wide cluster leaks points into the tight ones: K-Means prefers\n",
    "# similar-sized convex regions, so it redraws the boundary of the\n",
    "# spread-out blob even though k is correct.\n",
    "```\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0020",
   "metadata": {},
   "source": [
    "Next up: putting clusters to work — segmenting customers into named personas\n",
    "and compressing an image down to a handful of colors."
   ]
  }
 ]
}