{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem sheet 13 - Clustering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 13.1 - K-Means Algorithm\n",
    "The goal of this problem is to implement the K-Means algorithm known from slide 477:\n",
    "\n",
    "### Algorithm (K-Means Clustering)\n",
    "\n",
    "1. Fix the number of clusters $K$ and assign (by random) a number, from $1$ to $K$, to each of the observations. These serve as initial cluster assignments for the observations.\n",
    "2. Iterate until the cluster assignments stop changing:\n",
    "  1. For each of the $K$ clusters, compute the cluster centroid. The $k$-th cluster centroid is the vector of the $p$ feature means for the observations in the $k$-th cluster.\n",
    "  2. Assign each observation to the cluster whose centroid is closest (where closest is defined by Euclidean distance).\n",
    "  \n",
    "You should start by generating a test example, e.g., with the `make_blobs` function from `sklearn.datasets`.\n",
    "\n",
    "**Task**: Implement the K-Means Clustering using only `numpy` (and `matplotlib`, if you wish to display your findings graphically)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 13.2 - Further Clustering \n",
    "\n",
    "While the K-Means Clustering algorithm is by far the simplest clustering algorithm, there are many other clustering algorithms available.\n",
    "This [Towards Data Science article](https://towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68) describes 5 important clustering algorithms, the first one being *K-Means Clustering*, the last one being *Agglomerative Hierarchical Clustering*, which you'll learn about in the upcoming lecture.\n",
    "\n",
    "You should also have a look at [the `sklearn` documentation](https://scikit-learn.org/stable/modules/clustering.html).\n",
    "\n",
    "**Task**: Implement at least two of these using methods from `scikit-learn`. Test the performance of the algorithms for the swiss roll data set, which can be generated and plotted by\n",
    "\n",
    "    from sklearn.datasets import make_swiss_roll\n",
    "    import mpl_toolkits.mplot3d.axes3d as p3\n",
    "    %matplotlib notebook\n",
    "    # Generate swiss roll\n",
    "    n = 1000\n",
    "    eps = 0.05\n",
    "    X, _ = make_swiss_roll(n, eps)\n",
    "\n",
    "    # Plot the swiss roll\n",
    "    fig = plt.figure()\n",
    "    ax = p3.Axes3D(fig)\n",
    "    ax.view_init(7, -80)\n",
    "    ax.scatter(X[:,0], X[:,1], X[:,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}