C3_W1_KMeans_Assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# K-means Clustering \n",
    "\n",
    "In this exercise, you will implement the K-means algorithm and use it for image compression. \n",
    "\n",
    "* You will start with a sample dataset that will help you gain an intuition of how the K-means algorithm works. \n",
    "* After that, you will use the K-means algorithm for image compression by reducing the number of colors that occur in an image to only those that are most common in that image.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Outline\n",
    "- [ 1 - Implementing K-means](#1)\n",
    "  - [ 1.1 Finding closest centroids](#1.1)\n",
    "    - [ Exercise 1](#ex01)\n",
    "  - [ 1.2 Computing centroid means](#1.2)\n",
    "    - [ Exercise 2](#ex02)\n",
    "- [ 2 - K-means on a sample dataset ](#2)\n",
    "- [ 3 - Random initialization](#3)\n",
    "- [ 4 - Image compression with K-means](#4)\n",
    "  - [ 4.1 Dataset](#4.1)\n",
    "  - [ 4.2 K-Means on image pixels](#4.2)\n",
    "  - [ 4.3 Compress the image](#4.3)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_**NOTE:** To prevent errors from the autograder, you are not allowed to edit or delete non-graded cells in this lab. Please also refrain from adding any new cells. \n",
    "**Once you have passed this assignment** and want to experiment with any of the non-graded code, you may follow the instructions at the bottom of this notebook._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, run the cell below to import the packages needed in this assignment:\n",
    "\n",
    "- [numpy](https://numpy.org/) is the fundamental package for scientific computing with Python.\n",
    "- [matplotlib](http://matplotlib.org) is a popular library to plot graphs in Python.\n",
    "- `utils.py` contains helper functions for this assignment. You do not need to modify code in this file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from utils import *\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"1\"></a>\n",
    "## 1 - Implementing K-means\n",
    "\n",
    "The K-means algorithm is a method to automatically cluster similar\n",
    "data points together. \n",
    "\n",
    "* Concretely, you are given a training set $\\{x^{(1)}, ..., x^{(m)}\\}$, and you want\n",
    "to group the data into a few cohesive “clusters”. \n",
    "\n",
    "\n",
    "* K-means is an iterative procedure that\n",
    "     * Starts by guessing the initial centroids, and then \n",
    "     * Refines this guess by \n",
    "         * Repeatedly assigning examples to their closest centroids, and then \n",
    "         * Recomputing the centroids based on the assignments.\n",
    "         \n",
    "\n",
    "* In pseudocode, the K-means algorithm is as follows:\n",
    "\n",
    "    ``` python\n",
    "    # Initialize centroids\n",
    "    # K is the number of clusters\n",
    "    centroids = kMeans_init_centroids(X, K)\n",
    "    \n",
    "    for iter in range(iterations):\n",
    "        # Cluster assignment step: \n",
    "        # Assign each data point to the closest centroid. \n",
    "        # idx[i] corresponds to the index of the centroid \n",
    "        # assigned to example i\n",
    "        idx = find_closest_centroids(X, centroids)\n",
    "\n",
    "        # Move centroid step: \n",
    "        # Compute means based on centroid assignments\n",
    "        centroids = compute_centroids(X, idx, K)\n",
    "    ```\n",
    "\n",
    "\n",
    "* The inner-loop of the algorithm repeatedly carries out two steps: \n",
    "    1. Assigning each training example $x^{(i)}$ to its closest centroid, and\n",
    "    2. Recomputing the mean of each centroid using the points assigned to it. \n",
    "    \n",
    "    \n",
    "* The $K$-means algorithm will always converge to some final set of means for the centroids. \n",
    "\n",
    "* However, the converged solution may not always be ideal and depends on the initial setting of the centroids.\n",
    "    * Therefore, in practice the K-means algorithm is usually run a few times with different random initializations. \n",
    "    * One way to choose between these different solutions from different random initializations is to choose the one with the lowest cost function value (distortion).\n",
    "\n",
    "You will implement the two phases of the K-means algorithm separately\n",
    "in the next sections. \n",
    "* You will start by completing `find_closest_centroid` and then proceed to complete `compute_centroids`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"1.1\"></a>\n",
    "### 1.1 Finding closest centroids\n",
    "\n",
    "In the “cluster assignment” phase of the K-means algorithm, the\n",
    "algorithm assigns every training example $x^{(i)}$ to its closest\n",
    "centroid, given the current positions of centroids. \n",
    "\n",
    "<a name=\"ex01\"></a>\n",
    "### Exercise 1\n",
    "\n",
    "Your task is to complete the code in `find_closest_centroids`. \n",
    "* This function takes the data matrix `X` and the locations of all\n",
    "centroids inside `centroids` \n",
    "* It should output a one-dimensional array `idx` (which has the same number of elements as `X`) that holds the index  of the closest centroid (a value in $\\{0,...,K-1\\}$, where $K$ is total number of centroids) to every training example . *(Note: The index range 0 to K-1 varies slightly from what is shown in the lectures (i.e. 1 to K) because Python list indices start at 0 instead of 1)*\n",
    "* Specifically, for every example $x^{(i)}$ we set\n",
    "$$c^{(i)} := j \\quad \\mathrm{that \\; minimizes} \\quad ||x^{(i)} - \\mu_j||^2,$$\n",
    "where \n",
    " * $c^{(i)}$ is the index of the centroid that is closest to $x^{(i)}$ (corresponds to `idx[i]` in the starter code), and \n",
    " * $\\mu_j$ is the position (value) of the $j$’th centroid. (stored in `centroids` in the starter code)\n",
    " * $||x^{(i)} - \\mu_j||$ is the L2-norm\n",
    " \n",
    "If you get stuck, you can check out the hints presented after the cell below to help you with the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# UNQ_C1\n",
    "# GRADED FUNCTION: find_closest_centroids\n",
    "\n",
    "def find_closest_centroids(X, centroids):\n",
    "    \"\"\"\n",
    "    Computes the centroid memberships for every example\n",
    "    \n",
    "    Args:\n",
    "        X (ndarray): (m, n) Input values      \n",
    "        centroids (ndarray): (K, n) centroids\n",
    "    \n",
    "    Returns:\n",
    "        idx (array_like): (m,) closest centroids\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "    # Set K\n",
    "    K = centroids.shape[0]\n",
    "\n",
    "    # You need to return the following variables correctly\n",
    "    idx = np.zeros(X.shape[0], dtype=int)\n",
    "\n",
    "    ### START CODE HERE ###\n",
    "    \n",
    "        \n",
    "        \n",
    "            \n",
    "            \n",
    "        \n",
    "     ### END CODE HERE ###\n",
    "    \n",
    "    return idx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><font size=\"3\" color=\"darkgreen\"><b>Click for hints</b></font></summary>\n",
    "    \n",
    "    \n",
    "* Here's how you can structure the overall implementation for this function\n",
    "\n",
    "```python \n",
    "def find_closest_centroids(X, centroids):\n",
    "\n",
    "    # Set K\n",
    "    K = centroids.shape[0]\n",
    "\n",
    "    # You need to return the following variables correctly\n",
    "    idx = np.zeros(X.shape[0], dtype=int)\n",
    "\n",
    "    ### START CODE HERE ###\n",
    "    for i in range(X.shape[0]):\n",
    "        # Array to hold distance between X[i] and each centroids[j]\n",
    "        distance = [] \n",
    "        for j in range(centroids.shape[0]):\n",
    "            norm_ij = # Your code to calculate the norm between (X[i] - centroids[j])\n",
    "            distance.append(norm_ij)\n",
    "\n",
    "        idx[i] = # Your code here to calculate index of minimum value in distance\n",
    "    ### END CODE HERE ###\n",
    "    return idx\n",
    "```\n",
    "\n",
    "* If you're still stuck, you can check the hints presented below to figure out how to calculate `norm_ij` and `idx[i]`.\n",
    "    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate norm_ij</b></font></summary>\n",
    "           &emsp; &emsp; You can use <a href=\"https://numpy.org/doc/stable/reference/generated/numpy.linalg.norm.html\">np.linalg.norm</a> to calculate the norm \n",
    "          <details>\n",
    "              <summary><font size=\"2\" color=\"blue\"><b>&emsp; &emsp; More hints to calculate norm_ij</b></font></summary>\n",
    "               &emsp; &emsp; You can compute norm_ij as <code>norm_ij = np.linalg.norm(X[i] - centroids[j]) </code>\n",
    "           </details>\n",
    "    </details>\n",
    "\n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate idx[i]</b></font></summary>\n",
    "          &emsp; &emsp; You can use <a href=\"https://numpy.org/doc/stable/reference/generated/numpy.argmin.html\">np.argmin</a> to find the index of the minimum value\n",
    "          <details>\n",
    "              <summary><font size=\"2\" color=\"blue\"><b>&emsp; &emsp; More hints to calculate idx[i]</b></font></summary>\n",
    "              &emsp; &emsp; You can compute idx[i] as <code>idx[i] = np.argmin(distance)</code>\n",
    "          </details>\n",
    "    </details>\n",
    "        \n",
    "    </details>\n",
    "\n",
    "</details>\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's check your implementation using an example dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# Load an example dataset that we will be using\n",
    "X = load_data()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code below prints the first five elements in the variable `X` and the dimensions of the variable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "print(\"First five elements of X are:\\n\", X[:5]) \n",
    "print('The shape of X is:', X.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# Select an initial set of centroids (3 Centroids)\n",
    "initial_centroids = np.array([[3,3], [6,2], [8,5]])\n",
    "\n",
    "# Find closest centroids using initial_centroids\n",
    "idx = find_closest_centroids(X, initial_centroids)\n",
    "\n",
    "# Print closest centroids for the first three elements\n",
    "print(\"First three elements in idx are:\", idx[:3])\n",
    "\n",
    "# UNIT TEST\n",
    "from public_tests import *\n",
    "\n",
    "find_closest_centroids_test(find_closest_centroids)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "<table>\n",
    "  <tr>\n",
    "    <td> <b>First three elements in idx are<b></td>\n",
    "    <td> [0 2 1] </td> \n",
    "  </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"1.2\"></a>\n",
    "### 1.2 Computing centroid means\n",
    "\n",
    "Given assignments of every point to a centroid, the second phase of the\n",
    "algorithm recomputes, for each centroid, the mean of the points that\n",
    "were assigned to it.\n",
    "\n",
    "\n",
    "<a name=\"ex02\"></a>\n",
    "### Exercise 2\n",
    "\n",
    "Please complete the `compute_centroids` below to recompute the value for each centroid\n",
    "\n",
    "* Specifically, for every centroid $\\mu_k$ we set\n",
    "$$\\mu_k = \\frac{1}{|C_k|} \\sum_{i \\in C_k} x^{(i)}$$ \n",
    "\n",
    "    where \n",
    "    * $C_k$ is the set of examples that are assigned to centroid $k$\n",
    "    * $|C_k|$ is the number of examples in the set $C_k$\n",
    "\n",
    "\n",
    "* Concretely, if two examples say $x^{(3)}$ and $x^{(5)}$ are assigned to centroid $k=2$,\n",
    "then you should update $\\mu_2 = \\frac{1}{2}(x^{(3)}+x^{(5)})$.\n",
    "\n",
    "If you get stuck, you can check out the hints presented after the cell below to help you with the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# UNQ_C2\n",
    "# GRADED FUNCTION: compute_centroids\n",
    "\n",
    "def compute_centroids(X, idx, K):\n",
    "    \"\"\"\n",
    "    Returns the new centroids by computing the means of the \n",
    "    data points assigned to each centroid.\n",
    "    \n",
    "    Args:\n",
    "        X (ndarray):   (m, n) Data points\n",
    "        idx (ndarray): (m,) Array containing index of closest centroid for each \n",
    "                       example in X. Concretely, idx[i] contains the index of \n",
    "                       the centroid closest to example i\n",
    "        K (int):       number of centroids\n",
    "    \n",
    "    Returns:\n",
    "        centroids (ndarray): (K, n) New centroids computed\n",
    "    \"\"\"\n",
    "    \n",
    "    # Useful variables\n",
    "    m, n = X.shape\n",
    "    \n",
    "    # You need to return the following variables correctly\n",
    "    centroids = np.zeros((K, n))\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    \n",
    "        \n",
    "        \n",
    "    ### END CODE HERE ## \n",
    "    \n",
    "    return centroids"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><font size=\"3\" color=\"darkgreen\"><b>Click for hints</b></font></summary>\n",
    "    \n",
    "    \n",
    "* Here's how you can structure the overall implementation for this function\n",
    "    ```python \n",
    "    def compute_centroids(X, idx, K):\n",
    "        # Useful variables\n",
    "        m, n = X.shape\n",
    "    \n",
    "        # You need to return the following variables correctly\n",
    "        centroids = np.zeros((K, n))\n",
    "    \n",
    "        ### START CODE HERE ###\n",
    "        for k in range(K):   \n",
    "            points = # Your code here to get a list of all data points in X assigned to centroid k  \n",
    "            centroids[k] = # Your code here to compute the mean of the points assigned\n",
    "    ### END CODE HERE ## \n",
    "    \n",
    "    return centroids\n",
    "    ```\n",
    "  \n",
    "    If you're still stuck, you can check the hints presented below to figure out how to calculate `points` and `centroids[k]`.\n",
    "    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate points</b></font></summary>\n",
    "           &emsp; &emsp; Say we wanted to find all the values in X that were assigned to cluster <code>k=0</code>. That is, the corresponding value in idx for these examples is 0. In Python, we can do it as <code>X[idx == 0]</code>. Similarly, the points assigned to centroid <code>k=1</code> are <code>X[idx == 1]</code>\n",
    "          <details>\n",
    "              <summary><font size=\"2\" color=\"blue\"><b>&emsp; &emsp; More hints to calculate points</b></font></summary>\n",
    "               &emsp; &emsp; You can compute points as <code>points = X[idx == k] </code>\n",
    "           </details>\n",
    "    </details>\n",
    "\n",
    "     <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate centroids[k]</b></font></summary>\n",
    "          &emsp; &emsp; You can use <a href=\"https://numpy.org/doc/stable/reference/generated/numpy.mean.html\">np.mean</a> to find the mean. Make sure to set the parameter <code>axis=0</code> \n",
    "          <details>\n",
    "              <summary><font size=\"2\" color=\"blue\"><b>&emsp; &emsp; More hints to calculate centroids[k]</b></font></summary>\n",
    "              &emsp; &emsp; You can compute centroids[k] as <code>centroids[k] = np.mean(points, axis = 0)</code>\n",
    "          </details>\n",
    "    </details>\n",
    "        \n",
    "    </details>\n",
    "\n",
    "</details>\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now check your implementation by running the cell below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "K = 3\n",
    "centroids = compute_centroids(X, idx, K)\n",
    "\n",
    "print(\"The centroids are:\", centroids)\n",
    "\n",
    "# UNIT TEST\n",
    "compute_centroids_test(compute_centroids)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "\n",
    "2.42830111 3.15792418\n",
    "\n",
    "5.81350331 2.63365645\n",
    "\n",
    "7.11938687 3.6166844 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"2\"></a>\n",
    "## 2 - K-means on a sample dataset \n",
    "\n",
    "After you have completed the two functions (`find_closest_centroids`\n",
    "and `compute_centroids`) above, the next step is to run the\n",
    "K-means algorithm on a toy 2D dataset to help you understand how\n",
    "K-means works. \n",
    "* We encourage you to take a look at the function (`run_kMeans`) below to understand how it works. \n",
    "* Notice that the code calls the two functions you implemented in a loop.\n",
    "\n",
    "When you run the code below, it will produce a\n",
    "visualization that steps through the progress of the algorithm at\n",
    "each iteration. \n",
    "* At the end, your figure should look like the one displayed in Figure 1.\n",
    "* The final centroids are the black X-marks in the middle of the colored clusters.\n",
    "* You can see how these centroids got to their final location by looking at the other X-marks connected to it.\n",
    "\n",
    "<img src=\"images/figure 1.png\" width=\"500\" height=\"500\">\n",
    "\n",
    "\n",
    "**Note**: You do not need to implement anything for this part. Simply run the code provided below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# You do not need to implement anything for this part\n",
    "\n",
    "def run_kMeans(X, initial_centroids, max_iters=10, plot_progress=False):\n",
    "    \"\"\"\n",
    "    Runs the K-Means algorithm on data matrix X, where each row of X\n",
    "    is a single example\n",
    "    \"\"\"\n",
    "    \n",
    "    # Initialize values\n",
    "    m, n = X.shape\n",
    "    K = initial_centroids.shape[0]\n",
    "    centroids = initial_centroids\n",
    "    previous_centroids = centroids    \n",
    "    idx = np.zeros(m)\n",
    "    plt.figure(figsize=(8, 6))\n",
    "\n",
    "    # Run K-Means\n",
    "    for i in range(max_iters):\n",
    "        \n",
    "        #Output progress\n",
    "        print(\"K-Means iteration %d/%d\" % (i, max_iters-1))\n",
    "        \n",
    "        # For each example in X, assign it to the closest centroid\n",
    "        idx = find_closest_centroids(X, centroids)\n",
    "        \n",
    "        # Optionally plot progress\n",
    "        if plot_progress:\n",
    "            plot_progress_kMeans(X, centroids, previous_centroids, idx, K, i)\n",
    "            previous_centroids = centroids\n",
    "            \n",
    "        # Given the memberships, compute new centroids\n",
    "        centroids = compute_centroids(X, idx, K)\n",
    "    plt.show() \n",
    "    return centroids, idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# Load an example dataset\n",
    "X = load_data()\n",
    "\n",
    "# Set initial centroids\n",
    "initial_centroids = np.array([[3,3],[6,2],[8,5]])\n",
    "\n",
    "# Number of iterations\n",
    "max_iters = 10\n",
    "\n",
    "# Run K-Means\n",
    "centroids, idx = run_kMeans(X, initial_centroids, max_iters, plot_progress=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"3\"></a>\n",
    "## 3 - Random initialization\n",
    "\n",
    "The initial assignments of centroids for the example dataset was designed so that you will see the same figure as in Figure 1. In practice, a good strategy for initializing the centroids is to select random examples from the\n",
    "training set.\n",
    "\n",
    "In this part of the exercise, you should understand how the function `kMeans_init_centroids` is implemented.\n",
    "* The code first randomly shuffles the indices of the examples (using `np.random.permutation()`). \n",
    "* Then, it selects the first $K$ examples based on the random permutation of the indices. \n",
    "* This allows the examples to be selected at random without the risk of selecting the same example twice.\n",
    "\n",
    "**Note**: You do not need to implement anything for this part of the exercise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# You do not need to modify this part\n",
    "\n",
    "def kMeans_init_centroids(X, K):\n",
    "    \"\"\"\n",
    "    This function initializes K centroids that are to be \n",
    "    used in K-Means on the dataset X\n",
    "    \n",
    "    Args:\n",
    "        X (ndarray): Data points \n",
    "        K (int):     number of centroids/clusters\n",
    "    \n",
    "    Returns:\n",
    "        centroids (ndarray): Initialized centroids\n",
    "    \"\"\"\n",
    "    \n",
    "    # Randomly reorder the indices of examples\n",
    "    randidx = np.random.permutation(X.shape[0])\n",
    "    \n",
    "    # Take the first K examples as centroids\n",
    "    centroids = X[randidx[:K]]\n",
    "    \n",
    "    return centroids"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can run K-Means again but this time with random initial centroids. Run the cell below several times and observe how different clusters are created based on the initial points chosen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# Run this cell repeatedly to see different outcomes.\n",
    "\n",
    "# Set number of centroids and max number of iterations\n",
    "K = 3\n",
    "max_iters = 10\n",
    "\n",
    "# Set initial centroids by picking random examples from the dataset\n",
    "initial_centroids = kMeans_init_centroids(X, K)\n",
    "\n",
    "# Run K-Means\n",
    "centroids, idx = run_kMeans(X, initial_centroids, max_iters, plot_progress=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"4\"></a>\n",
    "## 4 - Image compression with K-means\n",
    "\n",
    "In this exercise, you will apply K-means to image compression. \n",
    "\n",
    "* In a straightforward 24-bit color representation of an image$^{2}$, each pixel is represented as three 8-bit unsigned integers (ranging from 0 to 255) that specify the red, green and blue intensity values. This encoding is often refered to as the RGB encoding.\n",
    "* Our image contains thousands of colors, and in this part of the exercise, you will reduce the number of\n",
    "colors to 16 colors.\n",
    "* By making this reduction, it is possible to represent (compress) the photo in an efficient way. \n",
    "* Specifically, you only need to store the RGB values of the 16 selected colors, and for each pixel in the image you now need to only store the index of the color at that location (where only 4 bits are necessary to represent 16 possibilities).\n",
    "\n",
    "In this part, you will use the K-means algorithm to select the 16 colors that will be used to represent the compressed image.\n",
    "* Concretely, you will treat every pixel in the original image as a data example and use the K-means algorithm to find the 16 colors that best group (cluster) the pixels in the 3- dimensional RGB space.\n",
    "* Once you have computed the cluster centroids on the image, you will then use the 16 colors to replace the pixels in the original image.\n",
    "\n",
    "<img src=\"images/figure 2.png\" width=\"500\" height=\"500\">\n",
    "\n",
    "$^{2}$<sub>The provided photo used in this exercise belongs to Frank Wouters and is used with his permission.</sub>\n",
    "\n",
    "<a name=\"4.1\"></a>\n",
    "### 4.1 Dataset\n",
    "\n",
    "**Load image**\n",
    "\n",
    "First, you will use `matplotlib` to read in the original image, as shown below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# Load an image of a bird\n",
    "original_img = plt.imread('bird_small.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Visualize image**\n",
    "\n",
    "You can visualize the image that was just loaded using the code below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# Visualizing the image\n",
    "plt.imshow(original_img)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Check the dimension of the variable**\n",
    "\n",
    "As always, you will print out the shape of your variable to get more familiar with the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "print(\"Shape of original_img is:\", original_img.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, this creates a three-dimensional matrix `original_img` where \n",
    "* the first two indices identify a pixel position, and\n",
    "* the third index represents red, green, or blue. \n",
    "\n",
    "For example, `original_img[50, 33, 2]` gives the blue intensity of the pixel at row 50 and column 33.\n",
    "\n",
    "#### Processing data\n",
    "\n",
    "To call the `run_kMeans`, you need to first transform the matrix `original_img` into a two-dimensional matrix.\n",
    "\n",
    "* The code below reshapes the matrix `original_img` to create an $m \\times 3$ matrix of pixel colors (where\n",
    "$m=16384 = 128\\times128$)\n",
    "\n",
    "*Note: If you'll try this exercise later on a JPG file, you first need to divide the pixel values by 255 so it will be in the range 0 to 1. This is not necessary for PNG files (e.g. `bird_small.png`) because it is already loaded in the required range (as mentioned in the [plt.imread() documentation](https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.imread.html)). We commented a line below for this so you can just uncomment it later in case you want to try a different file.* "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# Divide by 255 so that all values are in the range 0 - 1 (not needed for PNG files)\n",
    "# original_img = original_img / 255\n",
    "\n",
    "# Reshape the image into an m x 3 matrix where m = number of pixels\n",
    "# (in this case m = 128 x 128 = 16384)\n",
    "# Each row will contain the Red, Green and Blue pixel values\n",
    "# This gives us our dataset matrix X_img that we will use K-Means on.\n",
    "\n",
    "X_img = np.reshape(original_img, (original_img.shape[0] * original_img.shape[1], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"4.2\"></a>\n",
    "### 4.2 K-Means on image pixels\n",
    "\n",
    "Now, run the cell below to run K-Means on the pre-processed image."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false
   },
   "outputs": [],
   "source": [
    "# Run your K-Means algorithm on this data\n",
    "# You should try different values of K and max_iters here\n",
    "K = 16\n",
    "max_iters = 10\n",
    "\n",
    "# Using the function you have implemented above. \n",
    "initial_centroids = kMeans_init_centroids(X_img, K)\n",
    "\n",
    "# Run K-Means - this can take a couple of minutes depending on K and max_iters\n",
    "centroids, idx = run_kMeans(X_img, initial_centroids, max_iters)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "print(\"Shape of idx:\", idx.shape)\n",
    "print(\"Closest centroid for the first five elements:\", idx[:5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code below will plot all the colors found in the original image. As mentioned earlier, the color of each pixel is represented by RGB values so the plot should have 3 axes -- R, G, and B. You'll notice a lot of dots below representing thousands of colors in the original image. The red markers represent the centroids after running K-means. These will be the 16 colors that you will use to compress the image."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# Plot the colors of the image and mark the centroids\n",
    "plot_kMeans_RGB(X_img, centroids, idx, K)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can visualize the colors at each of the red markers (i.e. the centroids) above with the function below. You will only see these colors when you generate the new image in the next section. The number below each color is its index and these are the numbers you see in the `idx` array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# Visualize the 16 colors selected\n",
    "show_centroid_colors(centroids)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"4.3\"></a>\n",
    "### 4.3 Compress the image\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After finding the top $K=16$ colors to represent the image, you can now\n",
    "assign each pixel position to its closest centroid using the\n",
    "`find_closest_centroids` function. \n",
    "* This allows you to represent the original image using the centroid assignments of each pixel. \n",
    "* Notice that you have significantly reduced the number of bits that are required to describe the image. \n",
    "    * The original image required 24 bits (i.e. 8 bits x 3 channels in RGB encoding) for each one of the $128\\times128$ pixel locations, resulting in total size of $128 \\times 128 \\times 24 = 393,216$ bits. \n",
    "    * The new representation requires some overhead storage in form of a dictionary of 16 colors, each of which require 24 bits, but the image itself then only requires 4 bits per pixel location. \n",
    "    * The final number of bits used is therefore $16 \\times 24 + 128 \\times 128 \\times 4 = 65,920$ bits, which corresponds to compressing the original image by about a factor of 6."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# Find the closest centroid of each pixel\n",
    "idx = find_closest_centroids(X_img, centroids)\n",
    "\n",
    "# Replace each pixel with the color of the closest centroid\n",
    "X_recovered = centroids[idx, :] \n",
    "\n",
    "# Reshape image into proper dimensions\n",
    "X_recovered = np.reshape(X_recovered, original_img.shape) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, you can view the effects of the compression by reconstructing\n",
    "the image based only on the centroid assignments. \n",
    "* Specifically, you replaced each pixel with the value of the centroid assigned to\n",
    "it. \n",
    "* Figure 3 shows a sample reconstruction. Even though the resulting image retains most of the characteristics of the original, you will also see some compression artifacts because of the fewer colors used.\n",
    "\n",
    "<img src=\"images/figure 3.png\" width=\"700\" height=\"700\">\n",
    "\n",
    "* Run the code below to see how the image is reconstructed using the 16 colors selected earlier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# Display original image\n",
    "fig, ax = plt.subplots(1,2, figsize=(16,16))\n",
    "plt.axis('off')\n",
    "\n",
    "ax[0].imshow(original_img)\n",
    "ax[0].set_title('Original')\n",
    "ax[0].set_axis_off()\n",
    "\n",
    "\n",
    "# Display compressed image\n",
    "ax[1].imshow(X_recovered)\n",
    "ax[1].set_title('Compressed with %d colours'%K)\n",
    "ax[1].set_axis_off()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Congratulations on completing this lab on K-means clustering! In the next lesson, you will learn about another use case of unsupervised learning: anomaly detection. See you there!**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><font size=\"2\" color=\"darkgreen\"><b>Please click here if you want to experiment with any of the non-graded code.</b></font></summary>\n",
    "    <p><i><b>Important Note: Please only do this when you've already passed the assignment to avoid problems with the autograder.</b></i>\n",
    "    <ol>\n",
    "        <li> On the notebook’s menu, click “View” > “Cell Toolbar” > “Edit Metadata”</li>\n",
    "        <li> Hit the “Edit Metadata” button next to the code cell which you want to lock/unlock</li>\n",
    "        <li> Set the attribute value for “editable” to:\n",
    "            <ul>\n",
    "                <li> “true” if you want to unlock it </li>\n",
    "                <li> “false” if you want to lock it </li>\n",
    "            </ul>\n",
    "        </li>\n",
    "        <li> On the notebook’s menu, click “View” > “Cell Toolbar” > “None” </li>\n",
    "    </ol>\n",
    "    <p> Here's a short demo of how to do the steps above: \n",
    "        <br>\n",
    "        <img src=\"https://lh3.google.com/u/0/d/14Xy_Mb17CZVgzVAgq7NCjMVBvSae3xO1\" align=\"center\" alt=\"unlock_cells.gif\">\n",
    "</details>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}