{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Data Science 1 (Hierarchisches Clustering)\n",
    "\n",
    "Im zweiten Teil dieses Tutoriums beschäftigen wir uns nun mit hierarchischem Clustering. \n",
    "\n",
    "Hinweis: Aufgaben, die durch einen Asterisk (*) markiert sind, sind Bonusaufgaben. Diese Aufgaben können im Tutorium behandelt werden, dies ist jedoch von den Übungsleitern nicht geplant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import time\n",
    "import warnings\n",
    "from itertools import cycle, islice\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import sklearn\n",
    "from scipy.cluster.hierarchy import dendrogram, linkage\n",
    "from scipy.spatial import distance_matrix\n",
    "from sklearn import cluster, mixture\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.metrics import adjusted_rand_score\n",
    "\n",
    "# Schriftfarbe für dark/light Mode Nutzer\n",
    "# Bei Bedarf auf einen passenden Wert setzen\n",
    "COLOR = \"silver\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Aufgabe 3: Theorie\n",
    "\n",
    "Ist hierarchisches Clustering ein distanzbasiertes Clusteringverfahren?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Aufgabe 4: Dendrogramme zuordnen\n",
    "![Dendrogramme erkennen](../resources/10_data_science/dendrogramme_erkennen.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "*Hinweis*: Es gibt verschiedene Varianten, bei welchem Wert Cluster-Verbindungen in ein Dendrogramm eingetragen werden. In der Vorlesung wurden Beispiele gezeigt, in denen Cluster-Verbindungen bei der Hälfte der Distanz eingetragen wurden (z.B., $8.5$ für Distanz $17$ auf Slide 8 von Vorlesung 9). Oben und im Folgenden verwenden wir die heute gängige Definition, bei der Cluster-Verbindungen bei der tatsächlichen Distanz eingetragen werden (im Beispiel von Slide 8 wäre das $17$ für die Distanz $17$). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Aufgabe 5: Natürliche Zahlen Clustern\n",
    "\n",
    "Wir nutzen hierarchische Clusteranalyse mit euklidischer Distanzfunktion, um die\n",
    "Menge der natürlichen Zahlen von 1 bis 512 (inklusive 1 und 512) zu clustern.\n",
    "\n",
    "Falls mehrere Cluster dieselbe Distanz aufweisen, werden die zwei Cluster zusammengeführt, die die kleinste Zahl beinhalten. Wenn zum Beispiel Cluster\n",
    "$A$ und $B$ dieselbe Distanz zueinander haben wie Cluster $C$ und $D$,\n",
    "führen wir $A$ und $B$ zusammen, falls $\\operatorname{min}(A \\cup B) <\n",
    "\\operatorname{min}(C \\cup D)$. Falls $\\operatorname{min}(A \\cup B) =\n",
    "\\operatorname{min}(C \\cup D)$ entscheidet die nächstgrößere Zahl.\n",
    "\n",
    "Wir interessieren uns dafür, wie groß die beiden Cluster sind, die wir als\n",
    "letztes zusammenführen (also die Cluster, die am Ursprung des Dendrogramms\n",
    "anliegen). \n",
    "\n",
    "Fragen\n",
    "1. Wie groß sind die letzten beiden Cluster für single linkage Clustering?\n",
    "2. Wie groß sind die letzten beiden Cluster für complete linkage Clustering?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Aufgabe 6: Hierarchisches Clustering üben\n",
    "\n",
    "In dieser Aufgabe sollen Sie ein hierarchisches Clustering per Handsimulation auf zufällig generierten Datenpunkten durchführen. Dabei sollen Sie sowohl Single-Linkage als auch Complete-Linkage verwenden. Berechnen Sie dafür die Euklidische Distanz und runden Sie auf eine Nachkommastelle. Benutzen Sie den vorgegebenen Code, um die Datenpunkte für die Aufgabe zu erzeugen. Vergleichen Sie Ihre eigene Lösung mit der vorgegebenen Distanz-Matrix und dem Dendrogramm.\n",
    "\n",
    "**Achtung!** Bei jeder Ausführung wird eine neue zufällige Kombination von Datenpunkten erzeugt.\n",
    "Diese Aufgabe eignet sich daher besonders zum selbstständigen Üben und zur Vorbereitung auf den Test."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "Zuerst werden die Datenpunkte für die Durchführung der Handsimulation erzeugt und visualisiert."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Zufällige Kombination von Datenpunkten erzeugen\n",
    "coords = (np.random.rand(5, 2) * 10).round(1)\n",
    "\n",
    "# x- und y-Werte zuteilen\n",
    "x = coords[:, 0]\n",
    "y = coords[:, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Liste von Datenpunkte ausgeben\n",
    "print(coords)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Datenpunkte visualisieren\n",
    "plt.scatter(x, y)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Aufgabe 6.1\n",
    "\n",
    "Erstellen Sie jetzt selbstständig die Distanz-Matrix für die vorgegebenen Datenpunkte, wobei die Abstände auf eine Nachkommastelle gerundet werden. Führen Sie den folgenden Code aus, um Ihre Lösung zu prüfen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Distanz-Matrix erstellen\n",
    "print(distance_matrix(coords, coords).round(1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Aufgabe 6.2\n",
    "\n",
    "Führen Sie zuerst hierarchisches Clustering mit Single-Linkage und dann mit Complete-Linkage durch. Benutzen Sie den folgenden Code, um die Dendrogramme zu erstellen und Ihre Lösungen zu prüfen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Dendrogram für Single-Linkage Clustering\n",
    "plt.figure(figsize=(5, 3))\n",
    "dendrogram(linkage(coords, \"single\"))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Dendrogram für Complete-Linkage Clustering\n",
    "plt.figure(figsize=(5, 3))\n",
    "dendrogram(linkage(coords, \"complete\"))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Beispiel-Datenset: IRIS\n",
    "\n",
    "Der IRIS-Datensatz beinhaltet 150 Datenpunkte von 4 Attributen von Schwertlilienpflanzen. Gemessen wurden jeweils Kelchblattlänge, Kelchblattbreite, Blütenblattlänge und Blütenblattbreite. Wir werden im Folgenden versuchen, die beobachteten Pflanzen zu clustern. Die Daten beinhalten zusätzlich auch die tatsächliche Art der Schwertlilien (Setosa, Versicolour oder Virginica). Somit können wir unser Clustering am Ende mit der \"ground truth\" vergleichen. Der Datensatz besteht also aus einer 150x4 Datenmatrix und einem 150x1 Labelvektor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Iris Dataset importieren"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Datensatz laden\n",
    "iris = load_iris()\n",
    "\n",
    "# Das Objekt enthält Beobachtungen und Labels\n",
    "iris.data[:10]  # wir geben hier nur die ersten 10 Beobachtungen aus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Sowie die möglichen Label\n",
    "list(iris.target_names)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Einführung in Hierarchisches Clustering mit scikit-learn\n",
    "In dieser Aufgabe werden Sie die [Hierarchical Clustering Implementierung von scikit-learn](https://scikit-learn.org/stable/modules/clustering.html#hierarchical-clustering) nutzen, um das IRIS-Datenset mit verschiedenen Linking-Methoden zu clustern. \n",
    "\n",
    "Im Folgenden geben wir Ihnen ein Beispiel, wie die scikit-learn Implementierung angewandt wird. Ihre Aufgabe ist es, verschiedene Linking-Methoden anzuwenden und die sich ergebenden Clusterings zu vergleichen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Führt Hierarchisches Clustering durch und zeichnet das Dendrogramm\n",
    "linkage_matrix = linkage(iris.data, \"ward\")\n",
    "plt.figure(figsize=(20, 5))\n",
    "dendrogram(linkage_matrix)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Führt hierarchisches Clustering bis zu einer gegebenen Zahl von Clustern durch\n",
    "# und gibt Cluster-Assignments für jeden Datenpunkt zurück\n",
    "assignments = cluster.AgglomerativeClustering(n_clusters=3, linkage=\"ward\").fit_predict(iris.data)\n",
    "assignments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Aufgabe 7: Dendrogramme interpretieren\n",
    "Interpretieren Sie das aus der Einführung entstandene Dendrogramm.\n",
    "- Was stellt die x-Achse dar?\n",
    "- Was stellt die y-Achse dar? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Aufgabe 8: Vergleich verschiedener Linkage-Methoden*\n",
    "\n",
    "Der unten stehende Code generiert zuerst hierarchische Clusterings mit unterschiedlichen Linkage-Methoden. Zusätzlich zu den in der Vorlesung vorgestellten Methoden wird hier auch *Ward* und *average* Linkage berechnet. Da wir wissen, dass es drei Klassen der Pflanze gibt, lassen wir scikit-learn mittels der diversen Linkage-Methoden drei Cluster bilden. \n",
    "\n",
    "Vergleichen Sie verschiedene Verknüpfungskriterien (\"linkage methods\") für den IRIS-Datensatz, d.h. neben \"single\" und \"complete\" auch \"ward\" und \"average\", indem Sie verschiedene Feature-Kombinationen plotten und die Punkte entsprechend ihres Clusters einfärben.\n",
    "\n",
    "- Was sind die konzeptionellen Unterschiede zwischen den Methoden? \n",
    "- Welches der Kriterien kommt Ihrer Meinung nach am nähsten an die \"ground truth\" Cluster-Assignments heran?\n",
    "\n",
    "Hinweis: Vergleichen Sie hierzu auch die Cluster-Assignments des hierarchischen Clusterings (`assignments_<type>`) mit den tatsächlichen Clustern (`iris.target`). Speichern Sie die Cluster-Assignments der verschiedenen Methoden (z.B., als `assignments_ward`, `assignments_complete`, ...). \n",
    "\n",
    "Hinweis: Das Ward-Linkage minimiert die Varianz innerhalb eines Clusters. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "assignments_ward = cluster.AgglomerativeClustering(n_clusters=3, linkage=\"ward\").fit_predict(\n",
    "    iris.data\n",
    ")\n",
    "assignments_complete = cluster.AgglomerativeClustering(\n",
    "    n_clusters=3, linkage=\"complete\"\n",
    ").fit_predict(iris.data)\n",
    "assignments_average = cluster.AgglomerativeClustering(n_clusters=3, linkage=\"average\").fit_predict(\n",
    "    iris.data\n",
    ")\n",
    "assignments_single = cluster.AgglomerativeClustering(n_clusters=3, linkage=\"single\").fit_predict(\n",
    "    iris.data\n",
    ")\n",
    "\n",
    "fig, axes = plt.subplots(5, 6, figsize=(20, 10))\n",
    "plt.subplots_adjust(left=0.06, right=0.98, bottom=0.09, top=0.98, wspace=0.02, hspace=0.02)\n",
    "\n",
    "for i, (assignments, name) in enumerate(\n",
    "    [\n",
    "        (assignments_ward, \"Ward\"),\n",
    "        (assignments_complete, \"Complete\"),\n",
    "        (assignments_average, \"Average\"),\n",
    "        (assignments_single, \"Single\"),\n",
    "        (iris.target, \"Ground Truth\"),\n",
    "    ]\n",
    "):\n",
    "    for j, features in enumerate([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]):\n",
    "        axes[i][j].scatter(*np.split(iris.data[:, (features)], 2), c=assignments)\n",
    "        if j == 0:\n",
    "            axes[i][j].set_ylabel(name, size=\"large\", color=COLOR)\n",
    "        if i == 4:\n",
    "            axes[i][j].set_xlabel(\n",
    "                f\"({iris.feature_names[features[0]][:-5]}, {iris.feature_names[features[1]][:-5]})\",\n",
    "                size=\"large\",\n",
    "                color=COLOR,\n",
    "            )\n",
    "        axes[i][j].set_xticks([])\n",
    "        axes[i][j].set_yticks([])\n",
    "\n",
    "fig.supxlabel(\"Dataset Features\", size=\"x-large\", color=COLOR)\n",
    "fig.supylabel(\"Linkage Method\", size=\"x-large\", color=COLOR)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Aufgabe 9: Systematischer Vergleich der Assignments\n",
    "Cluster-Assignments manuell zu vergleichen ist mühsam, besonders bei großen Datensätzen. Wir werden nun die Metrik [`adjusted_rand_score`](https://scikit-learn.org/stable/modules/generated/sklearn.metrics.adjusted_rand_score.html) nutzen, um die Assignments jeder Methode zu beurteilen. Die Metrik gibt einen Cluster-Validierungsindex zurück, der zwischen -1 und 1 liegt, wobei 1 bedeutet, dass zwei Clusterings identisch sind (unabhängig davon, welches Label jedem Cluster zugeordnet ist).\n",
    "\n",
    "Unten werden die Scores beispielhaft berechnet und dann für unseren konkreten Datensatz. Was kann bzgl. der Qualität unserer Linkage-Methoden gesagt werden?  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Beispiel:\n",
    "ground_truth = [0, 0, 1, 1, 2, 2]\n",
    "assignments_good_clustering = [1, 1, 2, 2, 0, 0]\n",
    "assignments_bad_clustering = [0, 1, 2, 0, 1, 2]\n",
    "print(f\"Guter Score: {adjusted_rand_score(ground_truth, assignments_good_clustering)}\")\n",
    "print(f\"Schlechter Score: {adjusted_rand_score(ground_truth, assignments_bad_clustering)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "pd.DataFrame.from_dict(\n",
    "    {\n",
    "        \"ward\": (adjusted_rand_score(iris.target, assignments_ward),),\n",
    "        \"complete\": (adjusted_rand_score(iris.target, assignments_complete),),\n",
    "        \"average\": (adjusted_rand_score(iris.target, assignments_average),),\n",
    "        \"single\": (adjusted_rand_score(iris.target, assignments_single),),\n",
    "    }\n",
    ").style.hide(axis=\"index\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Aufgabe 10: Clustering-Algorithmen*\n",
    "\n",
    "Wir haben in diesem Modul zwei Cluster-Verfahren kennengelernt: k-Means und hierarchisches Clustering. Darüber hinaus gibt es viele weitere Clustering-Verfahren. Nachfolgend ist ein Vergleich der verschiedenen Clustering-Verfahren in scikit-learn auf verschiedenen Datensätzen implementiert. [Weitere Informationen](https://scikit-learn.org/stable/modules/clustering.html#clustering)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Konstruktion der Datensätze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "np.random.seed(0)\n",
    "n_samples = 1500\n",
    "\n",
    "# Datasets 1-4\n",
    "noisy_circles = sklearn.datasets.make_circles(n_samples=n_samples, factor=0.5, noise=0.05)\n",
    "noisy_moons = sklearn.datasets.make_moons(n_samples=n_samples, noise=0.05)\n",
    "blobs = sklearn.datasets.make_blobs(n_samples=n_samples, random_state=8)\n",
    "no_structure = np.random.rand(n_samples, 2), None\n",
    "\n",
    "# 5. Dataset: Anisotropisch verteilte Daten\n",
    "random_state = 170\n",
    "X, y = sklearn.datasets.make_blobs(n_samples=n_samples, random_state=random_state)\n",
    "transformation = [[0.6, -0.6], [-0.4, 0.8]]\n",
    "X_aniso = np.dot(X, transformation)\n",
    "aniso = (X_aniso, y)\n",
    "\n",
    "# 6. Dataset: 'Kleckse' mit unterschiedlichen Varianzen\n",
    "varied = sklearn.datasets.make_blobs(\n",
    "    n_samples=n_samples, cluster_std=[1.0, 2.5, 0.5], random_state=random_state\n",
    ")\n",
    "\n",
    "default_base = {\n",
    "    \"quantile\": 0.3,\n",
    "    \"eps\": 0.3,\n",
    "    \"damping\": 0.9,\n",
    "    \"preference\": -200,\n",
    "    \"n_neighbors\": 10,\n",
    "    \"n_clusters\": 3,\n",
    "    \"min_samples\": 20,\n",
    "    \"xi\": 0.05,\n",
    "    \"min_cluster_size\": 0.1,\n",
    "}\n",
    "\n",
    "datasets = [\n",
    "    (\n",
    "        noisy_circles,\n",
    "        \"Noisy Circles\",\n",
    "        {\n",
    "            \"damping\": 0.77,\n",
    "            \"preference\": -240,\n",
    "            \"quantile\": 0.2,\n",
    "            \"n_clusters\": 2,\n",
    "            \"min_samples\": 20,\n",
    "            \"xi\": 0.25,\n",
    "        },\n",
    "    ),\n",
    "    (\n",
    "        noisy_moons,\n",
    "        \"Noisy Moons\",\n",
    "        {\"damping\": 0.75, \"preference\": -220, \"n_clusters\": 2},\n",
    "    ),\n",
    "    (blobs, \"Blobs\", {}),\n",
    "    (no_structure, \"No Structure\", {}),\n",
    "    (\n",
    "        aniso,\n",
    "        \"Anisotropic\",\n",
    "        {\n",
    "            \"eps\": 0.15,\n",
    "            \"n_neighbors\": 2,\n",
    "            \"min_samples\": 20,\n",
    "            \"xi\": 0.1,\n",
    "            \"min_cluster_size\": 0.2,\n",
    "        },\n",
    "    ),\n",
    "    (\n",
    "        varied,\n",
    "        \"Varied\",\n",
    "        {\n",
    "            \"eps\": 0.18,\n",
    "            \"n_neighbors\": 2,\n",
    "            \"min_samples\": 5,\n",
    "            \"xi\": 0.035,\n",
    "            \"min_cluster_size\": 0.2,\n",
    "        },\n",
    "    ),\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Anwendung von verschiedenen Cluster-Verfahren\n",
    "\n",
    "**Hinweis:** Das Ausführen der unten stehenden Codezelle braucht etwas länger."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "for i, (dataset, d_name, d_params) in enumerate(datasets):\n",
    "    # Aktualisierung der Parameter mit datensatzspezifischen Werten\n",
    "    params = default_base.copy()\n",
    "    params.update(d_params)\n",
    "    X, y = dataset\n",
    "\n",
    "    # Datensätze normalisieren, um die Parameterauswahl zu erleichtern\n",
    "    X = sklearn.preprocessing.StandardScaler().fit_transform(X)\n",
    "\n",
    "    # Bandbreite für 'mean shift' schätzen\n",
    "    bandwidth = cluster.estimate_bandwidth(X, quantile=params[\"quantile\"])\n",
    "\n",
    "    # Konnektivitätsmatrix für strukturierte 'structured Ward'\n",
    "    connectivity = sklearn.neighbors.kneighbors_graph(\n",
    "        X, n_neighbors=params[\"n_neighbors\"], include_self=False\n",
    "    )\n",
    "\n",
    "    # Konnektivität symmetrisch machen\n",
    "    connectivity = 0.5 * (connectivity + connectivity.T)\n",
    "\n",
    "    # Cluster-Objekte mit Hilfe der Datasets I. - VI. erstellen\n",
    "    k_means = cluster.MiniBatchKMeans(n_clusters=params[\"n_clusters\"], init=\"random\", n_init=1)\n",
    "    ward = cluster.AgglomerativeClustering(\n",
    "        n_clusters=params[\"n_clusters\"], linkage=\"ward\", connectivity=connectivity\n",
    "    )\n",
    "    affinity_propagation = cluster.AffinityPropagation(\n",
    "        damping=params[\"damping\"], preference=params[\"preference\"]\n",
    "    )\n",
    "    ms = cluster.MeanShift(bandwidth=bandwidth, bin_seeding=True)\n",
    "    spectral = cluster.SpectralClustering(\n",
    "        n_clusters=params[\"n_clusters\"],\n",
    "        eigen_solver=\"arpack\",\n",
    "        affinity=\"nearest_neighbors\",\n",
    "    )\n",
    "    average_linkage = cluster.AgglomerativeClustering(\n",
    "        linkage=\"average\",\n",
    "        metric=\"manhattan\",\n",
    "        n_clusters=params[\"n_clusters\"],\n",
    "        connectivity=connectivity,\n",
    "    )\n",
    "    dbscan = cluster.DBSCAN(eps=params[\"eps\"])\n",
    "    optics = cluster.OPTICS(\n",
    "        min_samples=params[\"min_samples\"],\n",
    "        xi=params[\"xi\"],\n",
    "        min_cluster_size=params[\"min_cluster_size\"],\n",
    "    )\n",
    "    birch = cluster.Birch(n_clusters=params[\"n_clusters\"])\n",
    "    gmm = mixture.GaussianMixture(n_components=params[\"n_clusters\"], covariance_type=\"full\")\n",
    "\n",
    "    # Speichern der Algorithmus-Parameter/Cluster-Objekte\n",
    "    clustering_algorithms = (\n",
    "        (\"MiniBatch\\nKMeans\", k_means),\n",
    "        (\"Affinity\\nPropagation\", affinity_propagation),\n",
    "        (\"Ward\", ward),\n",
    "        (\"MeanShift\", ms),\n",
    "        (\"Spectral\\nClustering\", spectral),\n",
    "        (\"Agglomerative\\nClustering\", average_linkage),\n",
    "        (\"DBSCAN\", dbscan),\n",
    "        (\"OPTICS\", optics),\n",
    "        (\"BIRCH\", birch),\n",
    "        (\"Gaussian\\nMixture\", gmm),\n",
    "    )\n",
    "\n",
    "    # Visualisierung der Ergebnisse\n",
    "    plt.figure(figsize=(21, 12.5))\n",
    "    plt.subplots_adjust(left=0.02, right=0.98, bottom=0.001, top=0.96, wspace=0.05, hspace=0.01)\n",
    "\n",
    "    for j, (a_name, algorithm) in enumerate(clustering_algorithms):\n",
    "        t0 = time.time()\n",
    "\n",
    "        # Warnungen bei langen Laufzeiten\n",
    "        with warnings.catch_warnings():\n",
    "            warnings.filterwarnings(\n",
    "                \"ignore\",\n",
    "                message=\"the number of connected components of the connectivity\"\n",
    "                + \" matrix is [0-9]{1,2} > 1. Completing it to avoid stopping the tree early.\",\n",
    "                category=UserWarning,\n",
    "            )\n",
    "            warnings.filterwarnings(\n",
    "                \"ignore\",\n",
    "                message=\"Graph is not fully connected, spectral embedding\"\n",
    "                + \" may not work as expected.\",\n",
    "                category=UserWarning,\n",
    "            )\n",
    "            warnings.filterwarnings(\n",
    "                \"ignore\",\n",
    "                message=\"Affinity propagation did not converge, this model may\"\n",
    "                + \" return degenerate cluster centers and labels.\",\n",
    "                category=sklearn.exceptions.ConvergenceWarning,\n",
    "            )\n",
    "\n",
    "            algorithm.fit(X)\n",
    "\n",
    "        t1 = time.time()\n",
    "        if hasattr(algorithm, \"labels_\"):\n",
    "            y_pred = algorithm.labels_.astype(int)\n",
    "        else:\n",
    "            y_pred = algorithm.predict(X)\n",
    "\n",
    "        plt.subplot(len(datasets), len(clustering_algorithms), j + 1)\n",
    "        if i == 0:\n",
    "            plt.title(a_name, size=18, color=COLOR)\n",
    "        if j == 0:\n",
    "            plt.ylabel(d_name, size=18, color=COLOR)\n",
    "\n",
    "        # Farbpalette\n",
    "        colors = np.array(\n",
    "            list(\n",
    "                islice(\n",
    "                    cycle(\n",
    "                        [\n",
    "                            \"#377eb8\",\n",
    "                            \"#ff7f00\",\n",
    "                            \"#4daf4a\",\n",
    "                            \"#f781bf\",\n",
    "                            \"#a65628\",\n",
    "                            \"#984ea3\",\n",
    "                            \"#999999\",\n",
    "                            \"#e41a1c\",\n",
    "                            \"#dede00\",\n",
    "                        ]\n",
    "                    ),\n",
    "                    int(max(y_pred) + 1),\n",
    "                )\n",
    "            )\n",
    "        )\n",
    "        # Schwarze Farbe für Ausreißer hinzufügen (falls vorhanden)\n",
    "        colors = np.append(colors, [\"#000000\"])\n",
    "\n",
    "        plt.scatter(X[:, 0], X[:, 1], s=10, color=colors[y_pred])\n",
    "\n",
    "        plt.xlim(-2.5, 2.5)\n",
    "        plt.ylim(-2.5, 2.5)\n",
    "        plt.xticks(())\n",
    "        plt.yticks(())\n",
    "        plt.text(\n",
    "            0.99,\n",
    "            0.01,\n",
    "            (\"%.2fs\" % (t1 - t0)).lstrip(\"0\"),\n",
    "            transform=plt.gca().transAxes,\n",
    "            size=15,\n",
    "            horizontalalignment=\"right\",\n",
    "        )\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Aufgabe 10.1 \n",
    "\n",
    "k-Means läuft (fast immer) schneller als hierarchisches Clustering (siehe Laufzeiten unten rechts in den Bildern). Warum?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Aufgabe 10.2\n",
    "\n",
    "Welche Limitierungen von k-Means können Sie gegenüber hierarchischem Clustering erkennen?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Aufgabe 10.3\n",
    "\n",
    "Welche Vor- und Nachteile erkennen Sie bei den anderen Clustering-Algorithmen?"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 4
}