23-Aufgabe.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Clusterbildung mit K-means\n",
    "\n",
    "### - Aufgabe - \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diese Aufgabe befasst sich mit einem sehr beliebten Algorithmus zur Aufteilung eines Datensatzes in sog. Datencluster."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Was ist Clustering?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Clustering ist eine der gebräuchlichsten Techniken der explorativen Datenanalyse, die verwendet wird, um eine Intuition über die Struktur der Daten zu erhalten. Mit Hilfe von Clustering könnnen Untergruppen in den Daten so identifiziert werden, dass Datenpunkte derselben Untergruppe (Cluster) sehr ähnlich sind, während Datenpunkte in verschiedenen Clustern sehr unterschiedlich sind. Mit anderen Worten, wir versuchen, homogene Untergruppen innerhalb der Daten zu finden, sodass Datenpunkte in jedem Cluster gemäß einem Ähnlichkeitsmaß wie der Distanz zueinander so ähnlich wie möglich sind."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![EinFarbigesCluster.png](https://raw.githubusercontent.com/bethgelab/bwki-weekly-tasks/master/ImagesAndDataForExercises/EinfarbigesCluster.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das obige Streudiagramm enthält Informationen über die Streckenlänge und die Anzahl der Haltestellen von verschiedenen Zügen (die Achsen normalisiert). Wenn du die Punkte in drei Arten von Zügen aufteilen solltest, welche drei Gruppen würdest du bilden?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![FarbigesCluster.png](https://raw.githubusercontent.com/bethgelab/bwki-weekly-tasks/master/ImagesAndDataForExercises/FarbigesCluster.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vermutlich hast du intuitiv die Einteilung, welche in der obigen Graphik zu sehen ist, für Sinnvoll gehalten und damit natürlich auch absolut recht.\n",
    "Diese Aufgabe war für dich sehr einfach und du hast nicht sonderlich viel überlegen müssen, aber wenn du einem Computer erklären solltest, was genau er machen muss um das gleiche Ergebnis zu erhalten, ist die Antwort nicht offensichtlich.\n",
    "Klar, er muss sich irgendwie an den Abständen der Punkte zu einander orientieren und nähere Punkte zusammenfassen, aber was passiert genau?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Wie lassen sich sinnvolle Cluster bilden?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Einteilen von Datenpunkte in sog. Cluster (Gruppen/Bündel) lässt sich mit dem K-means-clustering Algorithmus vornehmen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Kmeans-Algorithmus ist ein iterativer Algorithmus, der versucht, den Datensatz in k vordefinierte, unterschiedliche, sich nicht überlappende Untergruppen (Cluster) zu unterteilen, wobei jeder Datenpunkt nur zu einer Gruppe gehören darf. Es versucht, die Datenpunkte innerhalbt eines Clusters so ähnlich wie möglich zu machen und gleichzeitig die Cluster so unterschiedlich (weit entfernt) wie möglich zu halten. Er weist einem Cluster Datenpunkte so zu, dass die Summe des quadrierten Abstands zwischen den Datenpunkten und dem Schwerpunkt des Clusters (Mittelwert aller Datenpunkte, die zu diesem Cluster gehören) minimal ist. Je weniger Variation wir innerhalb von Clustern haben, desto homogener (ähnlicher) sind die Datenpunkte innerhalb desselben Clusters. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es werden also anfangs k Punkte ausgewählt und dann iterativ so verschoben, dass der Abstand zwischen jedem der k Punkte und\n",
    "den ihm zugeordneten Datenpunkten (die die am nächsten an diesem Punkt sind) möglichst gering ist."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sehen wir uns nun den Ausführungsprozess an, dieser lässt sich in 4 Schritte einteilen:\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Schritt 1: Initialisieren\n",
    "Lege zunächst k zufälligen Punkte fest, diese werden als Schwerpunkte des Clusters bezeichnet. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Schritt 2: Clusterzuweisung\n",
    "Nach der Initialisierung werden alle Datenpunkte durchlaufen und der Abstand zwischen allen Schwerpunkten und den Datenpunkten berechnet. Die Datenpunkte werden dem Schwerpunkt zugeordnet zu dem sie den kleinsten Abstand haben."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Schritt 3: Schwerpunkte verschieben\n",
    "Da die im obigen Schritt gebildeten Cluster nicht optimiert sind, müssen wir optimierte Cluster bilden.Dafür muss die durchschnittliche Position der Datenpunkte eines Clusters berechnet werden und der Schwerpunkt auf diese Position gesetzt werden."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Schritt 4: Optimierung\n",
    "Die obigen beiden Schritte werden wiederholt, bis die Schwerpunkte sich nichtmehr bewegen oder (in unserem Fall) bis eine gewisse Anzahl an Iterationen erreicht wurde."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Laden der benötigten Module\n",
    "\n",
    "import numpy as np\n",
    "from scipy.spatial.distance import cdist\n",
    "from sklearn.datasets import load_digits\n",
    "from sklearn.decomposition import PCA\n",
    "from sklearn.cluster import KMeans\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementier hier die vier gegeben Schritte\n",
    "# arr : ein Array mit Koordinaten der Datenpunkte \n",
    "# k : Anzahl der zu bildenden Cluster\n",
    "# no_of_iterations : Anzahl der Durchläufe\n",
    "\n",
    "def kmeans(arr, k, no_of_iterations):\n",
    "    # Zufällige Auswahl von k Schwerpunkten aus der Menge\n",
    "    # der Datenpunkte \n",
    "    centroids = ... # Schritt 1\n",
    "\n",
    "    \n",
    "    # bestimme die euklidische Distanzen zwischen den Schwerpunkten \n",
    "    # und allen Datenpunkten\n",
    "    # Tipp: du kannst cdist benutzen\n",
    "    distances = ... # Schritt 2\n",
    "\n",
    "    # finde für jeden Datenpunkt den Schwerpunkt, der am nächsten ist\n",
    "    # dafür sollst du für jeden Datenpunkt ausgeben an welcher Position\n",
    "    # in seinem Abstandsarray der kleinste Wert ist    \n",
    "    points = ...  # Schritt 3\n",
    "\n",
    "    \n",
    "    # Wiederhole die obigen Schritte für die Anzahl an Iterationen\n",
    "    # Schritt 4\n",
    "    for _ in range(no_of_iterations):\n",
    "        centroids = []\n",
    "        for idx in range(k):\n",
    "            # Aktualisiere die Schwerpunkte indem du ihre Position\n",
    "            # auf die Durchschnittliche Position der ihnen Zugeordeneten Datenpunkte setzt\n",
    "            temp_cent = ...\n",
    "            centroids.append(temp_cent)\n",
    "\n",
    "        centroids = np.vstack(centroids)  # Aktualisierte Schwerpunkte\n",
    "        # berechne genau wie oben die Distanzen und die nächsten Schwerpunkte für die Datenpunkte\n",
    "        distances = ...\n",
    "        points = ...\n",
    "\n",
    "    return points\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In dem unteren Fenster kannst du testen, wie deine kmeans Funktion sich auf unserem Streudiagramm schlägt. Du musst sie nurnoch aufrufen und die Datenpunkte klassifizieren."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Da die Schwerpunkte anfangs zufällig gewählt werden, kann nicht garantiert werden, dass immer die optimale Lösung gefunden wird. Jedoch wird immer mindestens ein lokales Optimum gefunden (also eine Lösung, von der aus jede kleinere Veränderung nicht zu einer Verbesserung führt). Da unser Datensatz relativ klein ist, ist es jedoch ziemlich wahrscheinlich das globale Optimum zu finden und daher sollte beim mehrmaligem Ausführen des Programms auch die obige Lösung auftauchen. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEGCAYAAABo25JHAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAXh0lEQVR4nO3df5jWdZ3v8eerAc5QopiMHRVk8ArZWDTUkUzOGh5andQVSzblrFeHDkntHrzqMtmF0+a1sdvJlrN2dos9SVddlFelpshymUX5A8vMYAgQRWlZ9KwzdhWQGCYYwvv8cX+HczMMc39nmO9933N/Xo/rmmvu7+f76z2fa5gX31+fryICMzNL15tqXYCZmdWWg8DMLHEOAjOzxDkIzMwS5yAwM0vcsFoX0F9jxoyJ1tbWWpdhZjakbNiwYVdEtPQ2b8gFQWtrKx0dHbUuw8xsSJH0f481z6eGzMwS5yAwM0ucg8DMLHFD7hpBbw4cOEBnZyf79++vdSl1pbm5mbFjxzJ8+PBal2JmdawhgqCzs5NRo0bR2tqKpFqXUxcigt27d9PZ2cmECRNqXY6Z1bGGCIL9+/c7BHqQxCmnnMLOnTtrXYqZHadVG7tYumYbL+3Zx+mjR7Lw8klcc94Zg7b9hggCwCHQC/eJ2dC3amMXi1duYd+BgwB07dnH4pVbAAYtDHyx2Mysji1ds+1wCHTbd+AgS9dsG7R9OAgGSVNTE1OnTj38ddtttwEwY8aMww/Atba2smvXLgAuvvjiAe3n1ltv5aGHHhqcos2s7r20Z1+/2geiYU4N1drIkSPZtGlT7uWfeOKJAe1nyZIlA1rPzIam00ePpKuXP/qnjx45aPtI8ohg1cYupt/2CBMWfZfptz3Cqo1dVa/hhBNOAGDt2rVccsklXHnllUyaNImPfexjHDp0iIMHDzJ37lymTJnCOeecwxe+8AUA5s6dy7333gvAokWLmDx5Mueeey633HJL1X8GMyvewssnMXJ40xFtI4c3sfDySYO2j+SOCIq68LJv3z6mTp16eHrx4sVcd911udZdt24dW7duZfz48bS3t7Ny5UomTJhAV1cXTz/9NAB79uw5Yp3du3dz//3389xzzyHpqPlm1hi6/y75rqFB1NeFl+Pp2P6eGio3bdo0zjrrLADmzJnD448/zsyZM9mxYwc33XQTV155JZdddtkR65x00kk0Nzczb948rrrqKq666qoB125m9e2a884Y1D/8PSV3aqgaF176q+dtnpI4+eST2bx5MzNmzODLX/4yH/nIR45YZtiwYaxbt47Zs2fzwAMP0N7eXs2SzayBJHdEUI0LL/21bt06nn/+ecaPH8/dd9/N/Pnz2bVrFyNGjODaa69l0qRJ3HDDDUes8+qrr/Laa69xxRVXMH369MNHFGZm/ZVcECy8fNIR1whgcC689LxG0N7efvgW0kouvPBCFixYwPbt27n00kt5//vfz5YtW/jwhz/MoUOHAPjc5z53xDp79+5l1qxZ7N+/n4jg9ttvP676zSxdyQVBURdeDh482Gv72rVrD39+4YUXDn9+9dVXD38+8cQTeeCBB45Y753vfCc///nPj9reihUrDn9et27dwIo1MyuTXBBA8RdezMyGkiSDoJ7MmDGDGTNm1LoMM0tYw9w1FBG1LqHuuE/MLI+GCILm5mZ2797tP3xlut9H0NzcXOtSzKzONcSpobFjx9LZ2emx93vofkOZmVlfGiIIhg8f7rdwmZkNUEOcGjIzs4ErNAgktUvaJmm7pEW9zD9T0qOSNkp6StIVRdZjZmZHKywIJDUBy4D3AZOBOZIm91jsr4F7IuI84Hrgn4uqx8zMelfkEcE0YHtE7IiI3wN3AbN6LBPAidnnk4CXCqzHzMx6UeTF4jOAF8umO4F39Vjmb4AfSLoJeAvw3gLrMTOzXtT6YvEcYEVEjAWuAO6UdFRNkuZL6pDU4VtEzcwGV5FB0AWMK5sem7WVmwfcAxARPwWagTE9NxQRyyOiLSLaWlpaCirXzCxNRQbBemCipAmSRlC6GLy6xzL/DswEkPQOSkHg//KbmVVRYUEQEW8AC4A1wLOU7g56RtISSVdni30SuFHSZuDbwNzwOBFmZlVV6JPFEfEg8GCPtlvLPm8FphdZg5mZ9a3WF4vNzKzGHARmZolzEJiZJc5BYGaWOAeBmVniHARmZolzEJiZJc5BYGaWOAeBmVniHARmZolzEJiZJc5BYGaWOAeBmVniHARmZolzEJiZJc5BYGaWOAeBmVniHARmZolzEJiZJc5BYGaWOAeBmVniHARmZolzEJiZJc5BYGaWOAeBmVniHARmZolzEJiZJc5BYGaWOAeBmVniHARmZolzEJiZJc5BYGaWOAeBmVniHARmZolzEJiZJc5BYGaWOAeBmVniHARmZokrNAgktUvaJmm7pEXHWOaDkrZKekbSt4qsx8zMjjasqA1LagKWAX8MdALrJa2OiK1ly0wEFgPTI+JlSacWVY+ZmfWuyCOCacD2iNgREb8H7gJm9VjmRmBZRLwMEBG/LrAeMzPrRZFBcAbwYtl0Z9ZW7mzgbEk/kfSkpPbeNiRpvqQOSR07d+4sqFwzszTlCgJJb5P0VUnfy6YnS5o3CPsfBkwEZgBzgK9IGt1zoYhYHhFtEdHW0tIyCLs1M7NueY8IVgBrgNOz6V8An6iwThcwrmx6bNZWrhNYHREHIuL5bLsTc9ZkZmaDIG8QjImIe4BDABHxBnCwwjrrgYmSJkgaAVwPrO6xzCpKRwNIGkPpVNGOnDWZmdkgyBsEv5N0ChAAki4CXulrhSwsFlA6kngWuCcinpG0RNLV2WJrgN2StgKPAgsjYvcAfg4zMxsgRUTlhaTzgS8CU4CngRZgdkQ8VWx5R2tra4uOjo5q79bMbEiTtCEi2nqbl+s5goj4uaT3AJMAAdsi4sAg1mhmZjWSKwgkfaBH09mSXgG2+N5/M7OhLe+TxfOAd1M6jw+lC7wbgAmSlkTEnQXUZmZmVZA3CIYB74iIX0HpuQLgG8C7gB8BDgIzsyEq711D47pDIPPrrO03gK8VmJkNYXmPCNZKegD4TjZ9bdb2FmBPEYWZmVl15A2C/07pj//0bPobwH1Ruvf00iIKMzOz6sh7+2gA92ZfZmbWQPIOOvcBSf8q6RVJv5W0V9Jviy7OzMyKl/fU0N8DfxIRzxZZjJmZVV/eu4Z+5RAwM2tMeY8IOiTdTWm00Ne7GyNiZRFFmZlZ9eQNghOB14DLytoCcBCYmQ1xee8a+nDRhZiZWW3kHXSumdJ4Q38INHe3R8R/K6guMzOrkj4vFktann28E/iPwOXAY5ReO7m32NLMzKwaKt01dHv2/e0R8WngdxHxdeBKSgPOmZnZEFcpCJZk37sHltsjaQpwEnBqYVWZmVnVVLpG8PHs+1clnQx8mtIL6E8Abi2yMDMzq44+gyAifpl9vyNregw4q+iizMysevoMAkk39zU/Im7va76ZmdW/SqeGRlWlCjMzq5lKp4Y+U61CzMysNvI+UNYC3Ai0lq/jB8rMzIa+vGMN/QvwY+Ah4GBx5ZiZWbXlDYI3R8RfFVqJmZnVRN73ETwg6YpCKzEzs5rIGwQfpxQG+/2qSjOzxpJ3GGrfRmpm1qDyvrxekm6Q9OlsepykacWWZmZm1ZD31NA/A+8G/ks2/SqwrJCKzMysqvLeNfSuiDhf0kaAiHhZ0ogC6zIzsyrJe0RwQFITpfcUdz9gdqiwqszMrGryBsE/AfcDp0r6LPA48D8Lq8rMzKom76mhe4ENwExAwDXArwqqyczMqihvEKwEromI5wAknQb8ELigqMLMzKw68p4aWgXcI6lJUiuwBlhcVFFmZlY9eR8o+0p2l9AqSiOQfjQiniiwLjMzq5I+jwgk3dz9BTQDZwKbgIsqvb0sW79d0jZJ2yUt6mO5ayWFpLZ+1m9mZsepv28oW3mM9qNkt5suA/4Y6ATWS1odEVt7LDeK0lhGP8tVsZmZDaoi31A2DdgeETsAJN0FzAK29ljub4HPAwuPY19mZjZAecca+qGk0WXTJ0taU2G1M4AXy6Y7s7by7Z4PjIuI71bY/3xJHZI6du7cmadkMzPLKe9dQy0Rsad7IiJeBk49nh1LehNwO/DJSstGxPKIaIuItpaWluPZrZmZ9ZA3CA5KOrN7QtJ4suEm+tAFjCubHpu1dRsFTAHWSnoBuAhY7QvGZmbVlfeBsk8Bj0t6jNKTxX8EzK+wznpgoqQJlALgev7/6KVExCvAmO5pSWuBWyKiI3f1ZmZ23PI+R/D97Hz+RVnTJyJiV4V13pC0gNLDZ03A1yLiGUlLgI6IWH08hZuZ2eDIFQSSBLQDZ0XEEklnSpoWEev6Wi8iHgQe7NF26zGWnZGvZDMzG0z9fTHNnGx6L34xjZlZQ/CLaczMEucX05iZJc4vpjEzS1zFU0PZg1/PA39J2YtpIuLZgmszM7MqqBgEEXFI0rKIOA94rgo1mZlZFeU9NfRwNlS0Cq3GzMyqLm8QfBT4DvC6pN9K2ivptwXWZWZmVZL3yeKK7x8wM7OhKe8w1A/naTMzs6GnzyMCSc3Am4Exkk6mdMcQwIn0eLeAmZkNTZVODX0U+ARwOrChrH0v8KWCajIzsyqqdGroCeBiSsNDnwV8BngaeAz4VsG1mZlZFVQKgjuA1yPii5IuAT4HfB14BVhedHFmZla8SqeGmiLiN9nn64DlEXEfcJ+kTYVWZmZmVVHpiKBJUndYzAQeKZuXd+RSMzOrY5X+mH8beEzSLmAf8GMASW+ndHrIzMyGuD6DICI+mz0vcBrwg4jofmH9m4Cbii7OzMyKl2fQuSd7aftFMeWYmVm15R1ryMzMGpSDwMwscQ4CM7PEOQjMzBLnIDAzS5yDwMwscQ4CM7PEOQjMzBLnIDAzS5yDwMwscQ4CM7PEOQjMzBLnIDAzS5yDwMwscQ4CM7PEOQjMzBLnIDAzS5yDwMwscQ4CM7PEFRoEktolbZO0XdKiXubfLGmrpKckPSxpfJH1mJnZ0QoLAklNwDLgfcBkYI6kyT0W2wi0RcS5wL3A3xdVj5mZ9a7II4JpwPaI2BERvwfuAmaVLxARj0bEa9nkk8DYAusxM7NeFBkEZwAvlk13Zm3HMg/4Xm8zJM2X1CGpY+fOnYNYopmZ1cXFYkk3AG3A0t7mR8TyiGiLiLaWlpbqFmdm1uCGFbjtLmBc2fTYrO0Ikt4LfAp4T0S8XmA9ZmbWiyKPCNYDEyVNkDQCuB5YXb6ApPOAO4CrI+LXBdZiZmbHUFgQRMQbwAJgDfAscE9EPCNpiaSrs8WWAicA35G0SdLqY2zOzMwKUuSpISLiQeDBHm23ln1+b5H7NzOzyuriYrGZmdWOg8DMLHEOAjOzxDkIzMwS5yAwM0ucg8DMLHEOAjOzxDkIzMwS5yAwM0ucg8DMLHEOAjOzxDkIzMwS5yAwM0ucg8DMLHEOAjOzxDkIzMwS5yAwM0ucg8DMLHEOAjOzxDkIzMwS5yAwM0ucg8DMLHEOAjOzxDkIzMwS5yAwM0ucg8DMLHEOAjOzxDkIzMwS5yAwM0vcsFoXUA2rNnaxdM02Xtqzj9NHj2Th5ZO45rwzal2WmVldaPggWLWxi8Urt7DvwEEAuvbsY/HKLQAOAzMzEjg1tHTNtsMh0G3fgYMsXbOtRhWZmdWXhg+Cl/bs61e7mVlqGj4ITh89sl/tZmapafggWHj5JEYObzqibeTwJhZePqlGFZmZ1ZeGv1jcfUHYdw2ZmfWu4YMASmHgP/xmZr1r+FNDZmbWt0KDQFK7pG2Stkta1Mv8/yDp7mz+zyS1FlmPmZkdrbAgkNQELAPeB0wG5kia3GOxecDLEfF24AvA54uqx8zMelfkEcE0YHtE7IiI3wN3AbN6LDML+Hr2+V5gpiQVWJOZmfVQZBCcAbxYNt2ZtfW6TES8AbwCnNJzQ5LmS+qQ1LFz586CyjUzS9OQuGsoIpYDywEk7ZXk8SH6NgbYVesi6pj7p2/un8qGYh+NP9aMIoOgCxhXNj02a+ttmU5Jw4CTgN0VtrstItoGrcoGJKnDfXRs7p++uX8qa7Q+KvLU0HpgoqQJkkYA1wOreyyzGviv2efZwCMREQXWZGZmPRR2RBARb0haAKwBmoCvRcQzkpYAHRGxGvgqcKek7cBvKIWFmZlVUaHXCCLiQeDBHm23ln3eD/xpPze7fBBKa3Tuo765f/rm/qmsofpIPhNjZpY2DzFhZpY4B4GZWeLqNgg8TlHfcvTPzZK2SnpK0sOSjnkPcaOq1Edly10rKSQ1zO2AeeTpH0kfzH6PnpH0rWrXWGs5/p2dKelRSRuzf2tX1KLO4xYRdfdF6S6jfwPOAkYAm4HJPZb5C+DL2efrgbtrXXed9c+lwJuzz3+eUv/k7aNsuVHAj4AngbZa111P/QNMBDYCJ2fTp9a67jrso+XAn2efJwMv1LrugXzV6xGBxynqW8X+iYhHI+K1bPJJSg/0pSTP7xDA31Ia7HB/NYurA3n650ZgWUS8DBARv65yjbWWp48CODH7fBLwUhXrGzT1GgSDNk5Rg8rTP+XmAd8rtKL6U7GPJJ0PjIuI71azsDqR53fobOBsST+R9KSk9qpVVx/y9NHfADdI6qR0q/xN1SltcA2JsYZs4CTdALQB76l1LfVE0puA24G5NS6lng2jdHpoBqUjyh9JOici9tSyqDozB1gREf8g6d2UHpCdEhGHal1Yf9TrEUF/ximiH+MUNYo8/YOk9wKfAq6OiNerVFu9qNRHo4ApwFpJLwAXAasTumCc53eoE1gdEQci4nngF5SCIRV5+mgecA9ARPwUaKY0IN2QUq9B4HGK+laxfySdB9xBKQRSO7cLFfooIl6JiDER0RoRrZSuo1wdER21Kbfq8vwbW0XpaABJYyidKtpRxRprLU8f/TswE0DSOygFwZAbK78ugyA75989TtGzwD2RjVMk6epssa8Cp2TjFN0MHPP2wEaTs3+WAicA35G0SVLPX+CGlrOPkpWzf9YAuyVtBR4FFkZEKkfdefvok8CNkjYD3wbmDsX/kHqICTOzxNXlEYGZmVWPg8DMLHEOAjOzxDkIzMwS5yAwM0ucg8CGFEnXZCOF/kEB214haXYv7a2Snh7o+v3Y/1xJX+rRtrbSQ27ly0j6HwPdv6XLQWBDzRzg8ez7kJY9ET/YHATWbw4CGzIknQD8J0qP9V9f1j4j+1/xvZKek/RNlbRlD9NtkrRFUmTL3yhpvaTNku6T9Oay3Vwi6QlJOyr97z7bx5ey8eofAk4tm3eBpMckbZC0RtJpWftaSf9bUgfw8X7+/P9HUkf2boDP9DL/NmBk9vN+M2u7QdK6rO0OSU392aelwUFgQ8ks4PsR8QtKT7xeUDbvPOATlMaEPwuYHhEdETE1IqYC3wf+V7bsyoi4MCLeSemJ0Xll2zmNUthcBdxWoZ73A5OyfX4IuBhA0nDgi8DsiLgA+Brw2bL1RkREW0T8Qy/bvK4svDZRGjCw26ciog04F3iPpHPLV4yIRcC+7Gf+s2zIg+uyvpgKHAT+rMLPZAny6KM2lMwB/jH7fFc2vSGbXhcRnQDZH9BWSqeQkHQdcD5wWbbsFEl/B4ymNAzHmrJ9rMpGjtwq6W0V6rkE+HZEHARekvRI1j6J0oB2P1TpFRlNwC/L1ru7j23eHRELuickrS2b90FJ8yn9uz2NUgA91ce2ZgIXAOuzOkYCKY47ZRU4CGxIkPRW4D8D52SneJqAkLQwW6R8dNWDZL/bkqZQGjP+kuwPNsAK4JqI2CxpLtnAar1sZ6AvOhLwTES8+xjzf9fvDUoTgFuACyPiZUkrKA1wVqmOr0fE4v7uz9LiU0M2VMwG7oyI8dmIoeOA54E/OtYKkkZTGgjsQxFRPiLkKOCX2Smc4zlV8iNKp3KasmsAl2bt24AWlcanR9JwSX94HPuB0luwfge8kh2pvO8Yyx3Ifi6Ah4HZkk7N6nirEnx3tVXmILChYg5wf4+2++j77qFZwHjgK2Xn3AE+DfwM+Anw3HHUdD/wr8BW4BvATwGy1xrOBj6fjUq5iez6wUBFxGZK7w9+DvgWpdp7sxx4StI3I2Ir8NfADyQ9BfyQ0iklsyN49FEzs8T5iMDMLHEOAjOzxDkIzMwS5yAwM0ucg8DMLHEOAjOzxDkIzMwS9/8AvVbWCRQiZCQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "\n",
    "\n",
    "# die Koordinaten der Datenpunkte um das Streudiagramm zeichnen zu können\n",
    "data_points = np.array([[0.0418059341609478, 0.8823529411764706],\n",
    "                       [0.03865043446421623, 0.8823529411764706],\n",
    "                       [0.06913211941719055, 0.8235294117647058],\n",
    "                       [0.08081770688295364, 0.8235294117647058],\n",
    "                       [0.026132041588425636, 0.7647058823529412],\n",
    "                       [0.026132041588425636, 0.7647058823529412],\n",
    "                       [0.026132041588425636, 0.7647058823529412],\n",
    "                       [0.09365499764680862, 0.8235294117647058],\n",
    "                       [0.0802222266793251, 0.9411764705882352],\n",
    "                       [0.0, 0.7647058823529412],\n",
    "                       [0.05030515417456627, 1.0],\n",
    "                       [0.05030515417456627, 1.0],\n",
    "                       [0.18185654282569885, 0.3529411764705882],\n",
    "                       [0.18185654282569885, 0.3529411764705882],\n",
    "                       [0.1615954488515854, 0.2941176470588235],\n",
    "                       [0.20047201216220856, 0.2941176470588235],\n",
    "                       [0.13671165704727173, 0.2941176470588235],\n",
    "                       [0.1900033801794052, 0.4705882352941176],\n",
    "                       [0.10838034003973007, 0.4117647058823529],\n",
    "                       [0.1640133410692215, 0.2352941176470588],\n",
    "                       [0.15027260780334473, 0.2352941176470588],\n",
    "                       [0.15027260780334473, 0.2352941176470588],\n",
    "                       [0.08914268016815186, 0.4117647058823529],\n",
    "                       [0.09186362475156784, 0.2941176470588235],\n",
    "                       [0.8996241688728333, 0.2352941176470588],\n",
    "                       [0.8015787601470947, 0.2941176470588235],\n",
    "                       [0.8428218364715576, 0.0588235294117647],\n",
    "                       [0.7590007781982422, 0.1176470588235294],\n",
    "                       [0.7277239561080933, 0.1764705882352941],\n",
    "                       [0.72503662109375, 0.1764705882352941],\n",
    "                       [0.7115687131881714, 0.2352941176470588],\n",
    "                       [0.867732584476471, 0.0],\n",
    "                       [1.0, 0.2941176470588235],\n",
    "                       [0.9983829259872437, 0.1764705882352941],\n",
    "                       [0.7218253016471863, 0.0588235294117647],\n",
    "                       [0.695572018623352, 0.0588235294117647]])\n",
    "\n",
    "# Führe hier deinen k-means-clustering Algorithmus aus\n",
    "label = ...\n",
    "\n",
    "# Visualisierung des Resultats\n",
    "u_labels = np.unique(label)\n",
    "for i in u_labels:\n",
    "    plt.scatter(data_points[label == i, 0], data_points[label == i, 1], label=i)\n",
    "\n",
    "plt.xlabel('Anzahl der Halte')\n",
    "plt.ylabel('Streckenlänge')\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Klasse gemacht, jetzt kannst du mit Hilfe des kmeans Algorithmus die verschiedensten Datensätze ganz einfach sortieren. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fragen & Feedback:\n",
    "\n",
    "**Wenn ihr Fragen oder Anregungen zu der Aufgabe (oder Lösung) habt, dann tauscht euch gerne im [Chat](https://spectrum.chat/bwki/aufgabenarchiv/) darüber aus oder schreibt uns eine E-Mail (an info@bw-ki.de).**\n",
    "\n",
    "Wir freuen uns auch immer über **Feedback** (auch unter info@bw-ki.de):\n",
    "\n",
    "- War diese Aufgabe zu leicht, zu schwer oder genau richtig?\n",
    "- Wie lang hast du für diese Aufgabe ungefähr gebraucht?\n",
    "- Welche Art von Aufgaben wünschst du dir in Zukunft?"
   ]
  }
 ],
 "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}