MachineLearning/Clustering/k_means_issues.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Issues-with-K-Means\" data-toc-modified-id=\"Issues-with-K-Means-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Issues with K-Means</a></span><ul class=\"toc-item\"><li><span><a href=\"#Demonstration-of-&quot;Incorrect&quot;-Clusters-are-Found\" data-toc-modified-id=\"Demonstration-of-&quot;Incorrect&quot;-Clusters-are-Found-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Demonstration of \"Incorrect\" Clusters are Found</a></span><ul class=\"toc-item\"><li><span><a href=\"#Example-1\" data-toc-modified-id=\"Example-1-1.1.1\"><span class=\"toc-item-num\">1.1.1&nbsp;&nbsp;</span>Example 1</a></span><ul class=\"toc-item\"><li><span><a href=\"#Solution\" data-toc-modified-id=\"Solution-1.1.1.1\"><span class=\"toc-item-num\">1.1.1.1&nbsp;&nbsp;</span>Solution</a></span></li></ul></li><li><span><a href=\"#Example-2\" data-toc-modified-id=\"Example-2-1.1.2\"><span class=\"toc-item-num\">1.1.2&nbsp;&nbsp;</span>Example 2</a></span><ul class=\"toc-item\"><li><span><a href=\"#Solution\" data-toc-modified-id=\"Solution-1.1.2.1\"><span class=\"toc-item-num\">1.1.2.1&nbsp;&nbsp;</span>Solution</a></span></li></ul></li></ul></li><li><span><a href=\"#In-Summary\" data-toc-modified-id=\"In-Summary-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>In Summary</a></span></li><li><span><a href=\"#Datasets\" data-toc-modified-id=\"Datasets-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Datasets</a></span></li></ul></li><li><span><a href=\"#Other-Clustering-Algorithms\" data-toc-modified-id=\"Other-Clustering-Algorithms-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Other Clustering Algorithms</a></span></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "# Issues with K-Means"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "- Initial parameters matter: (hillclimbing)\n",
    "- Clusters are not always what we expect (because of local minimum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "## Demonstration of \"Incorrect\" Clusters are Found"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "> Can I find a local minimum where the \"obvious\" groups are incorrectly identified?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-11-13T16:59:12.660028Z",
     "start_time": "2019-11-13T16:59:12.507294Z"
    },
    "hidden": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "np.random.seed(27)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "### Example 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-11-13T16:59:12.790393Z",
     "start_time": "2019-11-13T16:59:12.665409Z"
    },
    "hidden": true
   },
   "outputs": [],
   "source": [
    "sigma_x = sigma_y = 0.1\n",
    "n = 10\n",
    "all_pts = []\n",
    "\n",
    "for c_x,c_y in [[0,4],[0,2],[1,3]]:\n",
    "    a_x = np.random.normal(c_x, sigma_x, n)\n",
    "    a_y = np.random.normal(c_y, sigma_y, n)\n",
    "\n",
    "    pts = np.array([(x,y) for (x,y) in zip(a_x,a_y)])\n",
    "    all_pts.append(pts)\n",
    "    \n",
    "    plt.scatter(pts[:,0], pts[:,1])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "> Using **3 centroids** find a local minimum where the two groups on the left are one group and another group on the right."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-11-13T17:04:02.954244Z",
     "start_time": "2019-11-13T17:04:02.847864Z"
    },
    "hidden": true
   },
   "outputs": [],
   "source": [
    "for pts in all_pts:\n",
    "    plt.scatter(pts[:,0], pts[:,1], alpha=0.55)\n",
    "    \n",
    "plt.scatter([0,1,1],[3,3.2,2.8], marker='*', s=200)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "### Example 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-11-13T17:05:05.156334Z",
     "start_time": "2019-11-13T17:05:05.054030Z"
    },
    "hidden": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "sigma_x = 0.1\n",
    "sigma_y = 0.5\n",
    "n = 15\n",
    "\n",
    "centers = [[0,2],[1,2]]\n",
    "all_pts = []\n",
    "\n",
    "for c_x,c_y in centers:\n",
    "    a_x = np.random.normal(c_x, sigma_x, n)\n",
    "    a_y = np.random.normal(c_y, sigma_y, n)\n",
    "\n",
    "    pts = np.array([(x,y) for (x,y) in zip(a_x,a_y)])\n",
    "    all_pts.append(pts)\n",
    "    \n",
    "    plt.scatter(pts[:,0], pts[:,1])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "> Using **2 centroids** find a local minimum where the two groups on the left are one group and another group on the right."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "#### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-11-13T17:06:42.024702Z",
     "start_time": "2019-11-13T17:06:41.918172Z"
    },
    "hidden": true
   },
   "outputs": [],
   "source": [
    "for pts in all_pts:\n",
    "    plt.scatter(pts[:,0], pts[:,1], alpha=0.55)\n",
    "    \n",
    "plt.scatter([0.5,0.5],[2,1.5], marker='*', s=200, color='red')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "## In Summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "> K-means relies on distance centers (lines of data) → looks for \"blob\" data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true,
    "hidden": true
   },
   "source": [
    "## Datasets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "The clustering algorithm's performance can depend on the initial data's structure/distribution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "- Random\n",
    "- Crescents\n",
    "- Cocentric circles\n",
    "- Clusters\n",
    "- Clusters w/ density\n",
    "- lined densities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "![https://scikit-learn.org/stable/_images/sphx_glr_plot_cluster_comparison_0011.png](images/sklearn_clustering_dataset_comparisons.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "# Other Clustering Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": true
   },
   "source": [
    "Leads us to other algorithms to deal with the short comings to k-means: [Heirarchical Clustering](heirarchical_clustering.ipynb)"
   ]
  }
 ],
 "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.6"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}