{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Unsupervised learning with Clustering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Clustering:-\n",
    "Cluster analysis or clustering is the most commonly used technique in unsupervised learning. It is used to find data clusters such that each cluster have most closely matched data.\n",
    "\n",
    "## Clustering Algorithm:-\n",
    "1. Prototype-based Clustering \n",
    "1. Heirarchical Clustering\n",
    "1. Desity-Based Clustering\n",
    "\n",
    "### * Prototype-Based Clustering \n",
    "Prototype-based clustering assumes that most data is located near prototypes. \n",
    "Example- Centroids (average) or medoids (most frequently occuring points) , K means , a Prototype based method, is most popular clustering method which involves \n",
    "* Training data that gets assigned to matching cluster based on similarity\n",
    "* the iterative process to get data points in best cluster possible\n",
    "\n",
    "***K-Means Clustering Example***\n",
    "Problem Statement :- In california , the govt tries to identify high density cluster to build hospitals (no other ground truth or features is provided apart from the population data). How can the clusters be identified ?\n",
    "\n",
    "* **Step1 :-**\n",
    "Randomly pick K centroids. Start by picking k centroids , Let's assume k = 3\\\n",
    "Find the number of clusters , by using elbow method \n",
    "\n",
    "* **Step2 :-**\n",
    "Assign each point to the nearest centeroid $$ M(J) , J \\in {1 \\cdots k} $$\n",
    "\n",
    "The points are assigned such that the euclidean distance of each point from respective centroids should be minimum.\n",
    "\n",
    "* **Step3 :-**\n",
    "Move each `Centroid` to the center of the respective cluster.\n",
    "\n",
    "* **Step4 :-**\n",
    "Calculate distance of the centroid from each point again.\\\n",
    "Calculate Euclidean distance between each point and centroids.\n",
    "\n",
    "* **Step5 :-**\n",
    "Move points across cluster and recalulate the distance from the centroid.\n",
    "\n",
    "* **Step6 :-**\n",
    "Keep moving points across cluster untill the Euclidean distance is minimized.\n",
    "\n",
    "\n",
    "Repeat the steps untill within the cluster the `Euclidean distance` is minimized for each cluster.\n",
    "\n",
    "### Mathematical Angle\n",
    "\n",
    "* A key challenge in clustering is that you have to preset the number of clusters. This influences the quality of clusters.\n",
    "\n",
    "* Unlike `Supervised learning` here one doesn't have ground truth lables. Hence , to check the quality of the clustering ,one should to use intrinsic methods , such as with-in clustering SSE , also called as `Distortion`.\n",
    "\n",
    "* In sklearn ML library , this value is available via the inertia_ attribute , after fitting the `K Means Clusttering` model.\n",
    "\n",
    "* One should plot the distortion agains the number of the clusters k. Intutively , Number of k increases ,distortion decreases.\\\n",
    "This is because the samples will be close to their assigned centroids.\n",
    "\n",
    "* This plot is called elbow method. It indicates optimum number of clusters at the position of elbow , the point at which distortion starts to increase rapidly.\n",
    "\n",
    "* The adjoining cluster indicates the K=3 is suitable for the clustering.\n",
    "\n",
    "* K means is based on finding points close to cluster centroids. The distance between two points X and Y is measured by using squared Euclidean Distance between them in an m-dimentional space.\n",
    "\n",
    "* Here , J refers to the Jth dimension (or Jth feature) of the data point.\n",
    "\n",
    "$$ d(x,y)^2 = \\sum_{j=1}^m(x_j - y_j)^2 = ||x-y||_2^2 $$\n",
    "\n",
    "* Based on this , the optimization problem is to minimize the within-cluster `sum of squared errors (SSE)` which is sometimes called `cluster inertia`.\n",
    "\n",
    "    * Here j refers to the Jth cluster. mu of (j) is the centroid of that cluster.\n",
    "    * w(i,j) = 1 if the sample x (i) is in cluster j, and 0 otherwise.\n",
    "    \n",
    "    $$ SSE = \\sum_{i=1}^n\\sum_{j=1}^k w^{(i,j)} ||x^{(i)} - \\mu^{(j)}||_2^2 $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Importing libraries\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "from sklearn.cluster import KMeans\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>CustomerID</th>\n",
       "      <th>Genre</th>\n",
       "      <th>Age</th>\n",
       "      <th>Annual Income (k$)</th>\n",
       "      <th>Spending Score (1-100)</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>Male</td>\n",
       "      <td>19</td>\n",
       "      <td>15</td>\n",
       "      <td>39</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>Male</td>\n",
       "      <td>21</td>\n",
       "      <td>15</td>\n",
       "      <td>81</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>Female</td>\n",
       "      <td>20</td>\n",
       "      <td>16</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>Female</td>\n",
       "      <td>23</td>\n",
       "      <td>16</td>\n",
       "      <td>77</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>Female</td>\n",
       "      <td>31</td>\n",
       "      <td>17</td>\n",
       "      <td>40</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   CustomerID   Genre  Age  Annual Income (k$)  Spending Score (1-100)\n",
       "0           1    Male   19                  15                      39\n",
       "1           2    Male   21                  15                      81\n",
       "2           3  Female   20                  16                       6\n",
       "3           4  Female   23                  16                      77\n",
       "4           5  Female   31                  17                      40"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "link = '/home/rahul/my_project_dir/python_learning/Class/Datasets/Customers.csv'\n",
    "df = pd.read_csv(link)\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 12724 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Let's check how many clusters we can form \n",
    "# we simply use scatterplot to see this\n",
    "plt.scatter(df['Annual Income (k$)'], df['Spending Score (1-100)'])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Annual Income (k$)</th>\n",
       "      <th>Spending Score (1-100)</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>70</th>\n",
       "      <td>49</td>\n",
       "      <td>55</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>119</th>\n",
       "      <td>67</td>\n",
       "      <td>57</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>166</th>\n",
       "      <td>86</td>\n",
       "      <td>20</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>67</th>\n",
       "      <td>48</td>\n",
       "      <td>48</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>150</th>\n",
       "      <td>78</td>\n",
       "      <td>17</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>40</th>\n",
       "      <td>38</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     Annual Income (k$)  Spending Score (1-100)\n",
       "70                   49                      55\n",
       "119                  67                      57\n",
       "166                  86                      20\n",
       "67                   48                      48\n",
       "150                  78                      17\n",
       "40                   38                      35"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cVar = df[['Annual Income (k$)','Spending Score (1-100)' ]]\n",
    "cVar.sample(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[269981.28,\n",
       " 181363.59595959596,\n",
       " 106348.37306211118,\n",
       " 73679.78903948834,\n",
       " 44448.45544793371,\n",
       " 37233.81451071001,\n",
       " 30552.71402546729,\n",
       " 26155.582930794695,\n",
       " 22209.851608025543]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# To find max number of cluster we use Elbow Method\n",
    "wcss = []\n",
    "for i in range(1,10):\n",
    "    cluster = KMeans(i)\n",
    "    cluster.fit(cVar)\n",
    "    wcss.append(cluster.inertia_)\n",
    "    \n",
    "wcss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 12500 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Let's plot elbow method\n",
    "plt.plot(range(1,10) , wcss)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 14488 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Let's compare the elbow method\n",
    "plt.plot(range(1,10) , wcss,'k')\n",
    "plt.scatter(range(1,10), wcss , marker= '*' ,color='m')\n",
    "plt.xlabel('k values')\n",
    "plt.ylabel('wcss')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3,\n",
       "       4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 0,\n",
       "       4, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 1, 2, 1, 2, 1,\n",
       "       0, 1, 2, 1, 2, 1, 2, 1, 2, 1, 0, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1,\n",
       "       2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1,\n",
       "       2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1,\n",
       "       2, 1], dtype=int32)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# now we can cluster easily by k = 5\n",
    "km = KMeans(n_clusters=5 , random_state=5)\n",
    "km.fit_predict(cVar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/rahul/my_project_dir/my_project_env/lib/python3.6/site-packages/ipykernel_launcher.py:1: SettingWithCopyWarning: \n",
      "A value is trying to be set on a copy of a slice from a DataFrame.\n",
      "Try using .loc[row_indexer,col_indexer] = value instead\n",
      "\n",
      "See the caveats in the documentation: https://pandas.pydata.org/pandas-docs/stable/user_guide/indexing.html#returning-a-view-versus-a-copy\n",
      "  \"\"\"Entry point for launching an IPython kernel.\n"
     ]
    }
   ],
   "source": [
    "cVar['Cluster'] = km.predict(cVar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Annual Income (k$)</th>\n",
       "      <th>Spending Score (1-100)</th>\n",
       "      <th>Cluster</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>15</td>\n",
       "      <td>39</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>15</td>\n",
       "      <td>81</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>16</td>\n",
       "      <td>6</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>16</td>\n",
       "      <td>77</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>17</td>\n",
       "      <td>40</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>195</th>\n",
       "      <td>120</td>\n",
       "      <td>79</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>196</th>\n",
       "      <td>126</td>\n",
       "      <td>28</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>197</th>\n",
       "      <td>126</td>\n",
       "      <td>74</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>198</th>\n",
       "      <td>137</td>\n",
       "      <td>18</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>199</th>\n",
       "      <td>137</td>\n",
       "      <td>83</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>200 rows × 3 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "     Annual Income (k$)  Spending Score (1-100)  Cluster\n",
       "0                    15                      39        4\n",
       "1                    15                      81        3\n",
       "2                    16                       6        4\n",
       "3                    16                      77        3\n",
       "4                    17                      40        4\n",
       "..                  ...                     ...      ...\n",
       "195                 120                      79        1\n",
       "196                 126                      28        2\n",
       "197                 126                      74        1\n",
       "198                 137                      18        2\n",
       "199                 137                      83        1\n",
       "\n",
       "[200 rows x 3 columns]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cVar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([4, 3, 0, 1, 2], dtype=int32)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# unique values of cluster\n",
    "cVar.Cluster.unique()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "c1 = cVar[cVar['Cluster'] == 0]\n",
    "c2 = cVar[cVar['Cluster'] == 1]\n",
    "c3 = cVar[cVar['Cluster'] == 2]\n",
    "c4 = cVar[cVar['Cluster'] == 3]\n",
    "c5 = cVar[cVar['Cluster'] == 4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Counter({0: 81})\n",
      "Counter({1: 39})\n",
      "Counter({2: 35})\n",
      "Counter({3: 22})\n",
      "Counter({4: 23})\n"
     ]
    }
   ],
   "source": [
    "print(Counter(c1.Cluster))\n",
    "print(Counter(c2.Cluster))\n",
    "print(Counter(c3.Cluster))\n",
    "print(Counter(c4.Cluster))\n",
    "print(Counter(c5.Cluster))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.axes._subplots.AxesSubplot at 0x7f7d981658d0>"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "[encoded data, 6244 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "sns.countplot(cVar.Cluster)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[55.2962963 , 49.51851852],\n",
       "       [86.53846154, 82.12820513],\n",
       "       [88.2       , 17.11428571],\n",
       "       [25.72727273, 79.36363636],\n",
       "       [26.30434783, 20.91304348]])"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "km.cluster_centers_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Index(['Annual Income (k$)', 'Spending Score (1-100)', 'Cluster'], dtype='object')"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c1.columns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 25976 characters]\n",
      "text/plain": [
       "<Figure size 720x504 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.figure(figsize=(10,7))\n",
    "plt.scatter(c1['Annual Income (k$)'],c1['Spending Score (1-100)'] , label = 'Cluster 1')\n",
    "plt.scatter(c2['Annual Income (k$)'],c2['Spending Score (1-100)'] , label = 'Cluster 2')\n",
    "plt.scatter(c3['Annual Income (k$)'],c3['Spending Score (1-100)'] , label = 'Cluster 3')\n",
    "plt.scatter(c4['Annual Income (k$)'],c4['Spending Score (1-100)'] , label = 'Cluster 4')\n",
    "plt.scatter(c5['Annual Income (k$)'],c5['Spending Score (1-100)'] , label = 'Cluster 5')\n",
    "plt.scatter(km.cluster_centers_[:, 0], km.cluster_centers_[:,1] , marker='*' , color= 'k' , label ='centroids')\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  }
 ],
 "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
