dbscan.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# DBSCAN\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import make_blobs\n",
    "import seaborn as sns\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "plt.rcParams[\"figure.figsize\"] = (10,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot(data, labels):\n",
    "    sns.scatterplot(data[:,0], data[:,1], hue=[\"Rauschen\" if x < 0 else \"Cluster {}\".format(x) for x in labels]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir erzeugen uns wieder Beispieldaten. Hierbei wählen wir extra verschiedene Dichten für\n",
    "die Cluster, um das Clustering schwieriger zu machen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "\n",
    "centers = [[1, 0.5], [2, 2], [1, -1]]\n",
    "stds = [0.1, 0.2, 0.3]\n",
    "X, labels_true = make_blobs(n_samples=1000, centers=centers, cluster_std=stds, random_state=0)\n",
    "\n",
    "plot(X, labels_true)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "Jetzt setzen wir DBSCAN an, mit den Hyper-Parametern Eps = 0.5 und MinPts = 10:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.cluster import DBSCAN\n",
    "\n",
    "db = DBSCAN(eps=0.5, min_samples=10).fit(X)\n",
    "\n",
    "plot(X, db.labels_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## Tuning des Eps Hyper-Parameters\n",
    "\n",
    "Das Ergebnis oben ist noch nicht gut: Zwei Cluster wurden zu einem verschmolzen.\n",
    "Lasst uns jetzt eine Reihe von Eps durchprobieren."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(20, 20))\n",
    "fig.subplots_adjust(hspace=.5, wspace=.2)\n",
    "i = 1\n",
    "for x in range(1, 11, 1):\n",
    "    eps = 1/x\n",
    "    db = DBSCAN(eps=eps, min_samples=10).fit(X)\n",
    "    core_samples_mask = np.zeros_like(db.labels_, dtype=bool)\n",
    "    core_samples_mask[db.core_sample_indices_] = True\n",
    "\n",
    "    ax = fig.add_subplot(4, 5, i)\n",
    "    ax.text(1, 3, f\"eps = {round(eps, 5)}\", fontsize=16, ha=\"center\")\n",
    "    plot(X, db.labels_)\n",
    "\n",
    "    i += 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "Der gute Bereich für Eps scheint zwischen 0.16 und 0.33 zu liegen.\n",
    "\n",
    "Kleine Eps führen zu schlecht getrennten zusätzlichen Clustern.\n",
    "Große Eps trennen eigentlich getrennte Cluster nicht auf."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## Eine systematische Methode, um Eps zu tunen\n",
    "\n",
    "Um einen Eindruck für ein optimales Eps zu bekommen, müssen wir wissen, wie sich denn\n",
    "die Anzahl der Punkte innerhalb des Eps-Kreises mit Eps verändert.\n",
    "Dazu ermitteln wir zu jedem Punkt (bzw. zu einem Sample von 1.000 Punkten) den Radius, den es braucht, damit der Punkt 9 Nachbarn hat.\n",
    "(9, damit im Kreis zusammen mit dem Punkt 10 Punkte liegen).\n",
    "\n",
    "Das sortieren wir dann nach aufsteigender Entfernung und schauen, wo sich die Kurve am stärksten ändert.\n",
    "Dies ist dann unser optimales Eps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.neighbors import NearestNeighbors\n",
    "nearest_neighbors = NearestNeighbors(n_neighbors=9)\n",
    "neighbors = nearest_neighbors.fit(X)\n",
    "distances, indices = neighbors.kneighbors(X)\n",
    "distances = np.sort(distances[:,8], axis=0)\n",
    "plt.figure(figsize=(5, 5))\n",
    "plt.plot(distances)\n",
    "plt.xlabel(\"Points\")\n",
    "plt.ylabel(\"Distance\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "\"Ellenbogen-Punkte\" sind oftmal gute Indikatoren für Schwellen, an denen sich ein Verhalten ändert.\n",
    "\n",
    "Daher ermitteln wir diesen Punkt jetzt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "from kneed import KneeLocator\n",
    "\n",
    "i = np.arange(len(distances))\n",
    "knee = KneeLocator(i, distances, S=100, curve='convex', direction='increasing', interp_method='polynomial')\n",
    "plt.figure(figsize=(5, 5));\n",
    "knee.plot_knee();\n",
    "plt.xlabel(\"Points\")\n",
    "plt.ylabel(\"Distance\")\n",
    "\n",
    "eps_knee = distances[knee.knee]\n",
    "print('Eps am Ellbogenpunkt', eps_knee);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import Markdown as md\n",
    "md(f\"Der Ellbogen-Punkt ist bei {round(eps_knee,5)}, dies verwenden wir jetzt als Eps:\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "db = DBSCAN(eps=round(eps_knee,5), min_samples=10).fit(X)\n",
    "\n",
    "plot(X, db.labels_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## Wie geht DBSCAN mit unseren Halbmonden um?\n",
    "\n",
    "Wir hatten ja gesehen, dass k-Means bei komplexeren Formen von Clustern versagt.\n",
    "\n",
    "DBSCAN sollte besser damit umgehen können, probieren wir es aus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.datasets import make_moons\n",
    "\n",
    "X, y = make_moons(200, noise=.05, random_state=0)\n",
    "db = DBSCAN(eps=eps_knee, min_samples=10).fit(X)\n",
    "\n",
    "plot(X, db.labels_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "Mit diesen Parametern ist das noch nicht gut.\n",
    "\n",
    "Die Daten sind weniger dicht als im ersten Beispiel, wir haben viel zu viele als Rauschen klassifizierte Punkte. Daher sollten wir Eps vergrößern (oder min_samples verkleinern)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "db = DBSCAN(eps=0.3, min_samples=10).fit(X)\n",
    "\n",
    "plot(X, db.labels_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "Unsere Struktur hat eine recht gleichmäßige Dichte und die Dichte dazwischen ist Null, daher\n",
    "erhalten wir schon mit diesem geschätzten Eps ein optimales Ergebnis.\n",
    "\n",
    "Zum Schluss nehmen wir wieder das \"schlechte\" Eps und verringern min_samples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "db = DBSCAN(eps=eps_knee, min_samples=3).fit(X)\n",
    "\n",
    "plot(X, db.labels_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Warum hilft uns das nicht richtig weiter?"
   ]
  }
 ],
 "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": 1
}