Pattern Analysis - Exam

Aufgabe 1)

Bei der Mustererkennung ist das Hauptziel die automatische Erkennung und Klassifizierung von Datenmustern. Dies erfolgt in mehreren Schritten: Vorverarbeitung, Merkmalsextraktion und Klassifikation. Typische Anwendungsbereiche sind unter anderem die Bild- und Sprachverarbeitung, medizinische Diagnostik sowie die Finanzmarktanalyse.

Zu den häufig verwendeten Methoden in der Mustererkennung gehören neuronale Netze, Entscheidungsbäume und das K-Nearest-Neighbor-Verfahren (KNN). Eine zentrale Herausforderung bei der Mustererkennung ist die Generalisierung auf unbekannte Daten. Die Leistung der Methoden wird oft anhand von Metriken wie Genauigkeit, Präzision, Recall und F1-Score evaluiert.

a)

Angenommen, Du hast ein Datensatz zur Früherkennung von Hautkrebs, der Bilder von mutmaßlichen Hautläsionen sowie deren Klassifikationen (bösartig oder gutartig) enthält. Beschreibe, wie Du die Methoden der Mustererkennung anwenden könntest, um ein System zur automatischen Klassifikation dieser Hautläsionen zu entwickeln. Gehe dabei insbesondere auf die Schritte der Vorverarbeitung, Merkmalsextraktion und Klassifikation ein.

Lösung:

Um ein System zur automatischen Klassifikation von Hautläsionen zur Früherkennung von Hautkrebs zu entwickeln, solltest Du die folgenden Schritte der Mustererkennung durchlaufen:

• Vorverarbeitung: In diesem Schritt werden die Rohdaten, in diesem Fall die Bilder der Hautläsionen, vorbereitet, um die nachfolgenden Analysen zu erleichtern.
  • Bildskalierung: Anpassung der Bildgröße, um eine einheitliche Eingabegröße für das Modell zu gewährleisten.
  • Bildnormalisierung: Normalisierung der Pixelwerte, damit sie in einem bestimmten Wertebereich liegen (z. B. 0 bis 1 oder -1 bis 1).
  • Rauschunterdrückung: Anwendung von Filtern, um Bildrauschen zu reduzieren und die Qualität der Bilder zu verbessern.
  • Datenaugmentation: Erzeugung zusätzlicher Trainingsdaten durch Bildtransformationen wie Drehen, Spiegeln, Skalieren usw., um das Modell robuster zu machen.
• Merkmalsextraktion: Hierbei handelt es sich um den Prozess der Gewinnung von relevanten Merkmalen aus den Bildern, die für die Klassifikation nützlich sind.
  • Manuelle Merkmalsextraktion: Verwendung von Techniken wie Kanten- und Konturerkennung oder Texturanalyse, um spezifische Merkmale aus den Bildern zu extrahieren. Diese Methode setzt Fachwissen voraus und wird oftmals als veraltet betrachtet.
  • Automatische Merkmalsextraktion: Einsatz von Convolutional Neural Networks (CNNs), die in der Lage sind, aus den Input-Bildern automatisch Merkmale zu lernen. Diese Methode ist sehr effizient und wird weitgehend bevorzugt.
• Klassifikation: In diesem Schritt werden die extrahierten Merkmale verwendet, um die Hautläsionen als bösartig oder gutartig zu klassifizieren.
  • Einsatz von neuronalen Netzen: Vorzugsweise tiefe neuronale Netze (Deep Learning), insbesondere CNNs, die für Bildklassifikationen sehr leistungsfähig sind. Das Netz wird mit den vorverarbeiteten und augmentierten Bildern trainiert, um Kategorien vorherzusagen.
  • Verwendung von anderen Klassifikationsmethoden, wie Entscheidungsbäumen oder K-Nearest-Neighbor, je nach Datenmenge und -qualität sowie Verfügbarkeit der Rechenressourcen.
  • Evaluation der Modellergebnisse: Testen des Modells auf einem separaten Testdatensatz und Berechnung von Leistungsmetriken wie Genauigkeit, Präzision, Recall und F1-Score, um die Leistung des Klassifikators zu bewerten.

Indem Du diese Schritte sorgfältig ausführst, kannst Du ein zuverlässiges System zur automatischen Klassifikation von Hautläsionen entwickeln, das zur Früherkennung von Hautkrebs beiträgt.

b)

Mit Bezug auf den Hautkrebsdatensatz von oben, beschreiben einen Algorithmus, welchen Du verwenden würdest (z. B. ein neuronales Netz, Entscheidungsbaum oder KNN). Formuliere die mathematischen Grundlagen dieses Algorithmus und erläutere, wie die Evaluierung der Modellleistung mittels Genauigkeit, Präzision, Recall und F1-Score erfolgt. Gib entsprechende mathematische Formeln für diese Evaluierungsmetriken an.

Lösung:

Für die Klassifikation eines Datensatzes zur Früherkennung von Hautkrebs würde ich ein Convolutional Neural Network (CNN) verwenden. CNNs sind für Bildverarbeitungsaufgaben besonders geeignet, da sie in der Lage sind, räumliche Hierarchien in den Bilddaten zu lernen und zu nutzen.

• Mathematische Grundlagen des CNN: Ein neuronales Netz besteht aus mehreren Schichten, darunter Faltungsschichten (Convolutional Layers), Pooling-Schichten und vollverbundene Schichten.
  • Faltungsschicht: Die Faltungsschicht wendet einen Satz von Filtern auf das Eingabebild an, um Merkmalskarten zu erstellen. Die mathematische Operation ist die Faltung, beschrieben durch: \( S_{i,j}^{k} = (X * W^k)_{i,j} + b^k \) wobei \( S_{i,j}^{k} \) das Ergebnis der Faltung an Position \( (i,j) \) für den k-ten Filter, \( X \) das Eingabebild, \( W^k \) die Filtergewichte und \( b^k \) der Bias ist.
  • Pooling-Schicht: Pooling reduziert die Dimension der Merkmalskarten und erhält dabei die wichtigsten Informationen. Ein gängiges Verfahren ist das Max-Pooling: \( P_{i,j} = \text{max}(S_{m,n}) \) wobei \( S_{m,n} \) die Werte im Pooling-Fenster sind.
  • Vollverbundene Schicht: Diese Schicht stellt die endgültige Klassifikation bereit, indem sie die extrahierten Merkmale verknüpft und eine Aktivierungsfunktion anwendet.
• Evaluierung der Modellleistung: Die Modellleistung wird anhand der folgenden Metriken evaluiert:
  • Genauigkeit (Accuracy): Beschreibt den Anteil der korrekt klassifizierten Instanzen. \( \text{Genauigkeit} = \frac{TP + TN}{TP + TN + FP + FN} \)
  • Präzision (Precision): Beschreibt den Anteil der korrekt als positiv klassifizierten Instanzen unter allen positiv klassifizierten Instanzen. \( \text{Präzision} = \frac{TP}{TP + FP} \)
  • Recall: Beschreibt den Anteil der korrekt als positiv erkannten Instanzen unter allen tatsächlich positiven Instanzen. \( \text{Recall} = \frac{TP}{TP + FN} \)
  • F1-Score: Ist das harmonische Mittel von Präzision und Recall. \( \text{F1-Score} = 2 \times \frac{\text{Präzision} \times \text{Recall}}{\text{Präzision} + \text{Recall}} \)
  Dabei sind: \( TP \) = True Positives (richtig positiv), \( TN \) = True Negatives (richtig negativ), \( FP \) = False Positives (falsch positiv), \( FN \) = False Negatives (falsch negativ).

Indem Du diese Metriken berechnest, kannst Du die Leistung des Klassifikationsmodells umfassend bewerten und sicherstellen, dass es gut auf unbekannte Daten generalisiert.

Aufgabe 2)

Gegeben sind zwei Hypothesen H₁ und H₂ über die Zugehörigkeit eines Datenpunkts x zu einer Klasse, basierend auf den folgenden Informationen:

• A-priori-Wahrscheinlichkeiten: P(H₁) = 0.6 und P(H₂) = 0.4
• Likelihoods: P(x|H₁) = 0.7 und P(x|H₂) = 0.2

Anhand dieser Informationen sollen die folgenden Aufgaben gelöst werden:

a)

Berechne die a-posteriori-Wahrscheinlichkeiten P(H₁|x) und P(H₂|x). Stelle sicher, dass Du den Rechenweg klar angibst und erläutere, wie die Normierungskonstante P(x) ermittelt wird.

Lösung:

Um die a-posteriori-Wahrscheinlichkeiten P(H₁|x) und P(H₂|x) zu berechnen, müssen wir den Satz von Bayes anwenden. Der Satz von Bayes lautet:

• \( P(H_i|x) = \frac{P(x|H_i) \, P(H_i)}{P(x)} \)

Dabei ist P(x) die Normierungskonstante, die sicherstellt, dass die Wahrscheinlichkeiten korrekt skaliert sind. Sie wird berechnet als die Summe der bedingten Wahrscheinlichkeiten multipliziert mit den A-priori-Wahrscheinlichkeiten:

• \( P(x) = P(x|H_1) \, P(H_1) + P(x|H_2) \, P(H_2) \)

Sind:

• \(P(H_1) = 0.6 \)

• \(P(H_2) = 0.4 \)

• \(P(x|H_1) = 0.7 \)

• \(P(x|H_2) = 0.2 \)

Berechnen wir zuerst die Normierungskonstante P(x):

• \(P(x) = (0.7 \, \cdot \, 0.6) + (0.2 \, \cdot \, 0.4)\)

• \(P(x) = 0.42 + 0.08\)

• \(P(x) = 0.50\)

Nun können wir die gesuchten a-posteriori-Wahrscheinlichkeiten berechnen:

• \(P(H_1|x) = \frac{P(x|H_1) \, P(H_1)}{P(x)} \)

• \(P(H_1|x) = \frac{0.7 \, \cdot \, 0.6}{0.50} \)

• \(P(H_1|x) = \frac{0.42}{0.50} \)

• \(P(H_1|x) = 0.84 \)

• \(P(H_2|x) = \frac{P(x|H_2) \, P(H_2)}{P(x)} \)

• \(P(H_2|x) = \frac{0.2 \, \cdot \, 0.4}{0.50} \)

• \(P(H_2|x) = \frac{0.08}{0.50} \)

• \(P(H_2|x) = 0.16 \)

Zusammenfassend sind die a-posteriori-Wahrscheinlichkeiten:

• \(P(H_1|x) = 0.84 \)

• \(P(H_2|x) = 0.16 \)

b)

Basierend auf den berechneten a-posteriori-Wahrscheinlichkeiten, entscheide, welcher Klasse der Datenpunkt x zugewiesen wird. Nutze hierfür die Bayessche Entscheidungsregel und erläutere kurz dein Vorgehen.

Lösung:

Um zu entscheiden, welcher Klasse der Datenpunkt x zugewiesen wird, verwenden wir die Bayessche Entscheidungsregel. Diese Regel besagt, dass der Datenpunkt der Klasse mit der höheren a-posteriori-Wahrscheinlichkeit zugeordnet wird.

Wir haben bereits die a-posteriori-Wahrscheinlichkeiten berechnet:

• \(P(H_1|x) = 0.84\)

• \(P(H_2|x) = 0.16\)

Vergleichen wir die beiden Wahrscheinlichkeiten:

• \(P(H_1|x) = 0.84\) ist größer als \(P(H_2|x) = 0.16\).

Daher wird der Datenpunkt x der Klasse H₁ zugewiesen.

Vorgehensweise:

• Berechnung der a-posteriori-Wahrscheinlichkeiten mit dem Satz von Bayes.

• Vergleich der berechneten Wahrscheinlichkeiten.

• Zuweisung des Datenpunkts zu der Klasse mit der höheren a-posteriori-Wahrscheinlichkeit.

Aufgabe 3)

Du hast zwei Ansätze des maschinellen Lernens kennengelernt: Unsupervised Learning und Supervised Learning. Beim Unsupervised Learning geht es darum, Daten ohne vordefinierte Labels zu analysieren, um versteckte Muster oder Gruppen zu finden. Methoden beinhalten Clustering und Dimensionalitätsreduktion. Beim Supervised Learning handelt es sich darum, Daten mit vordefinierten Labels zu analysieren, um eine Funktion zu lernen, die Input-Output-Paare beschreibt. Beispiele beinhalten Klassifikation und Regression.

a)

Stelle dir vor, du hast Zugriff auf einen Datensatz bestehend aus Kundeninformationen eines Online-Shops. Die Datenattribute beinhalten Geschlecht, Alter, jährliches Einkommen und Ausgabenwert. Du möchtest Kunden in verschiedene Gruppen einteilen, um gezielte Marketingmaßnahmen durchzuführen.

• (a) Erkläre, ob Du für diese Aufgabe Unsupervised Learning oder Supervised Learning verwenden würdest und warum.
• (b) Wähle eine spezifische Unsupervised Learning Methode aus und beschreibe detailliert, wie Du diese Methode auf den gegebenen Datensatz anwenden würdest. Erkläre die Schritte und Überlegungen, die Du zur Durchführung machen würdest. Gehe dabei insbesondere auf die Notwendigkeit der Vorverarbeitung der Daten ein.

Lösung:

• (a) In diesem Fall würde ich Unsupervised Learning verwenden, weil es darum geht, Kunden ohne vordefinierte Labels oder Gruppen zu segmentieren. Das Ziel ist es, Muster und Gruppierungen in den Daten zu finden, die für gezielte Marketingmaßnahmen genutzt werden können. Ein Algorithmus für Unsupervised Learning, wie Clustering, kann verwendet werden, um natürliche Gruppierungen in den Kundenattributen (Geschlecht, Alter, jährliches Einkommen, Ausgabenwert) zu identifizieren.
• (b) Eine spezifische Unsupervised Learning Methode, die ich auswählen würde, ist der K-Means Clustering-Algorithmus. Hier ist eine detaillierte Beschreibung, wie ich diese Methode auf den gegebenen Datensatz anwenden würde:
• Schritt 1: Vorverarbeitung der Daten: Bevor ich den K-Means-Algorithmus anwende, würde ich die Daten wie folgt vorverarbeiten:
• Fehlende Werte überprüfen und gegebenenfalls ersetzen oder entfernen
• Daten standardisieren, um sicherzustellen, dass alle Attribute (Geschlecht, Alter, jährliches Einkommen, Ausgabenwert) den gleichen Einfluss auf das Clustering haben. Eine Standardisierung könnte mittels Normierung (z.B. Z-Score Standardisierung) erfolgen
• Kategorische Variablen wie Geschlecht in numerische Werte umwandeln (z.B. männlich = 0, weiblich = 1)
• Schritt 2: Anwendungs des K-Means-Algorithmus:
• Wähle die Anzahl der Cluster (k). Dies kann durch die Verwendung des „Elbow-Method“ Diagramms erfolgen, um die optimale Anzahl der Cluster zu bestimmen.
• Initialisieren der Cluster-Zentroiden (Startpunkte).
• Zuweisung jedes Datenpunkts zum nächstgelegenen Cluster-Zentrum basierend auf dem euklidischen Abstand.
• Neuberechnung der Cluster-Zentroiden als den Mittelwert der Datenpunkte in jedem Cluster.
• Wiederhole die Zuweisung und Neuberechnung der Zentroiden, bis die Clusterzuweisungen sich nicht mehr ändern oder eine definierte Maximalanzahl an Iterationen erreicht ist.
• Schritt 3: Ergebnisanalyse: Nach dem Clustering können die resultierenden Gruppen analysiert werden, um die Eigenschaften der einzelnen Cluster zu verstehen und maßgeschneiderte Marketingstrategien zu entwickeln.
• Visualisierung der Cluster mittels Diagrammen (z.B. Scatterplots mit unterschiedlicher Färbung für jeden Cluster).
• Interpretation der Cluster-Zentroiden zur Ermittlung der typischen Attribute der Kunden in jedem Cluster.
• Gegebenenfalls weitere statistische Analysen, um die Bedeutung und Verwendung der Cluster zu verstehen.
• Durch diese Schritte würde der K-Means-Clustering-Algorithmus es ermöglichen, nützliche Kundensegmente für gezielte Marketingmaßnahmen zu identifizieren.

b)

Betrachte den gleichen Datensatz von Kundeninformationen. Nun hast Du aber eine Zielvariable: Kaufentscheidung (0 für gekauft und 1 für nicht gekauft). Du möchtest nun ein Modell trainieren, um vorherzusagen, ob ein Kunde bei einer bestimmten Marketingkampagne kaufen wird oder nicht.

• (a) Stelle den Unterschied zwischen der vorherigen Aufgabe und dieser Aufgabe hinsichtlich der Lernmethode (Unsupervised vs. Supervised Learning) dar. Begründe, welche Methode Du in dieser Situation anwenden würdest.
• (b) Wähle eine spezifische Supervised Learning Methode aus und beschreibe den gesamten Trainingsprozess einschließlich der Datenvorverarbeitung, Modellwahl, Training und Evaluierung. Gehe dabei auch darauf ein, wie Du die Performance des Modells messen würdest.

Lösung:

• (a) Der Unterschied zwischen der vorherigen Aufgabe und dieser Aufgabe liegt in der Art der Lernmethode. Bei der vorherigen Aufgabe wurde Unsupervised Learning verwendet, da es keine Zielvariable gab und der Fokus darauf lag, versteckte Muster oder Gruppen in den Daten zu finden. Unsupervised Learning hilft dabei, Daten ohne vordefinierte Labels zu analysieren. In der aktuellen Aufgabe gibt es hingegen eine Zielvariable (Kaufentscheidung). Das bedeutet, wir nutzen Supervised Learning, das dazu dient, eine Funktion zu lernen, die die Beziehung zwischen den Eingabedaten und der Zielvariable beschreibt. In dieser Situation würde ich Supervised Learning anwenden, weil wir ein Modell trainieren möchten, das Vorhersagen über die Kaufentscheidung basierend auf den Kundendaten trifft.
• (b) Eine spezifische Supervised Learning Methode, die ich auswählen würde, ist der Random Forest Classifier. Hier ist der gesamte Trainingsprozess:
• Schritt 1: Datenvorverarbeitung:
• Überprüfen der Daten auf fehlende Werte und diese gegebenenfalls ersetzen oder entfernen.
• Kategorische Variablen wie Geschlecht in numerische Werte umwandeln (z.B. männlich = 0, weiblich = 1).
• Die numerischen Features (z.B. Alter, jährliches Einkommen, Ausgabenwert) können skaliert werden, um den Bereich zu standardisieren.
• Aufteilung des Datensatzes in Trainings- und Testdatensätze, z.B. im Verhältnis 80:20.
• Schritt 2: Modellwahl:
• Auswahl des Random Forest Classifier, da dieser Algorithmus gut für Klassifikationsprobleme geeignet ist, robust gegenüber Overfitting ist und mit einer Vielzahl von Features umgehen kann.
• Schritt 3: Training des Modells:
• Fitting des Modells auf den Trainingsdatensatz. Dies beinhaltet das Anwenden des Random Forest Algorithmus, der mehrere Entscheidungsbäume trainiert und die Mehrheitsabstimmung der Bäume als endgültige Klassifikation verwendet.
• Schritt 4: Evaluierung des Modells:
• Vorhersagen auf dem Testdatensatz durchführen.
• Verwendung geeigneter Metriken zur Evaluierung der Modellperformance, wie:
• Genauigkeit (Accuracy): Der Anteil der korrekt vorhergesagten Instanzen unter allen Instanzen. \( \text{Accuracy} = \frac{TP + TN}{TP + TN + FP + FN} \), wobei TP für True Positive, TN für True Negative, FP für False Positive und FN für False Negative steht.
• Präzision (Precision): Der Anteil der korrekt vorhergesagten positiven Beobachtungen zu allen vorhergesagten positiven Beobachtungen. \( \text{Precision} = \frac{TP}{TP + FP} \)
• Recall (Sensitivität): Der Anteil der korrekt vorhergesagten positiven Beobachtungen zu den tatsächlichen positiven Beobachtungen. \( \text{Recall} = \frac{TP}{TP + FN} \)
• F1-Score: Der harmonische Mittelwert von Präzision und Recall. \( \text{F1-Score} = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}} \)
• AUC-ROC (Area Under the Receiver Operating Characteristic Curve): Diese Metrik bewertet die Fähigkeit des Modells, zwischen den Klassen zu unterscheiden.
• Schritt 5: Optimierung: Falls die Modellperformance nicht zufriedenstellend ist, könnte man weitere Optimierungen vornehmen, wie z.B. Hyperparameter-Tuning, Cross-Validation oder den Einsatz von erweiterten Techniken wie Feature Engineering.
• Durch diesen Trainingsprozess kann ein robustes Modell entwickelt werden, das die Kaufentscheidung der Kunden effektiv vorhersagt.

Aufgabe 4)

K-means Clustering AlgorithmusDer K-means Clustering Algorithmus ist eine unsupervised learning Methode zur Gruppierung ähnlicher Datenpunkte in k Cluster.

• Datenpunkte werden zufällig in k Cluster eingeteilt
• Centroiden jedes Clusters berechnen
• Datenpunkte den nächstgelegenen Centroiden zuordnen
• Prozess iterativ wiederholen bis Stabilität
• Ziel: Minimierung der Summe der quadratischen Abstände der Datenpunkte zu ihren jeweiligen Centroiden
• Formel zur Berechnung der Distanz zu Centroiden:
• \[J = \sum_{i=1}^{k} \sum_{j=1}^{n} || x_j^{(i)} - \mu_i ||^2\]

a)

(a) Implementiere den K-means Clustering Algorithmus in Python:

Schreibe eine Funktion mit dem Namen kmeans, die die Punkte X (ein numpy Array), die Anzahl der Cluster k und die maximale Anzahl der Iterationen max_iter akzeptiert. Deine Funktion soll den Zentroiden jedes Clusters und die Clusterzuordnung für jeden Punkt zurückgeben.

import numpy as npdef kmeans(X, k, max_iter):        # Zufälliges Initialisieren der Zentroiden    centroids = X[np.random.choice(X.shape[0], k, replace=False)]        for i in range(max_iter):        # Zuweisen der Punkte zu den nächstgelegenen Zentroiden        distances = np.zeros((X.shape[0], k))        for j in range(k):            distances[:, j] = np.linalg.norm(X - centroids[j], axis=1)        clusters = np.argmin(distances, axis=1)        # Neuberechnung der Zentroiden        new_centroids = np.zeros((k, X.shape[1]))        for j in range(k):            new_centroids[j] = X[clusters == j].mean(axis=0)        # Überprüfung der Konvergenz        if np.all(centroids == new_centroids):            break        centroids = new_centroids    return centroids, clusters

Lösung:

K-means Clustering Algorithmus

• Datenpunkte werden zufällig in k Cluster eingeteilt
• Centroiden jedes Clusters berechnen
• Datenpunkte den nächstgelegenen Centroiden zuordnen
• Prozess iterativ wiederholen bis Stabilität
• Ziel: Minimierung der Summe der quadratischen Abstände der Datenpunkte zu ihren jeweiligen Centroiden
• Formel zur Berechnung der Distanz zu Centroiden:

• \[J = \sum_{i=1}^{k} \sum_{j=1}^{n} \vert\vert x_j^{(i)} - \mu_i \vert\vert^2\]

Schreibe eine Funktion mit dem Namen kmeans, die die Punkte X (ein numpy Array), die Anzahl der Cluster k und die maximale Anzahl der Iterationen max_iter akzeptiert. Deine Funktion soll die Zentroiden jedes Clusters und die Clusterzuordnung für jeden Punkt zurückgeben.

import numpy as npdef kmeans(X, k, max_iter):    # Zufälliges Initialisieren der Zentroiden    centroids = X[np.random.choice(X.shape[0], k, replace=False)]    for i in range(max_iter):        # Zuweisen der Punkte zu den nächstgelegenen Zentroiden        distances = np.zeros((X.shape[0], k))        for j in range(k):            distances[:, j] = np.linalg.norm(X - centroids[j], axis=1)        clusters = np.argmin(distances, axis=1)        # Neuberechnung der Zentroiden        new_centroids = np.zeros((k, X.shape[1]))        for j in range(k):            new_centroids[j] = X[clusters == j].mean(axis=0)        # Überprüfung der Konvergenz        if np.all(centroids == new_centroids):            break        centroids = new_centroids    return centroids, clusters

b)

(b) Theoretische Analyse:

Nehmen wir an, Du hast einen Datensatz mit 3 Clustern und folgender Zentroiden-Konfiguration:

• \[\mu_1 = (2, 3)\]
• \[\mu_2 = (6, 7)\]
• \[\mu_3 = (5, 2)\]

Die Datenpunkte sind:

• \[x_1 = (2, 2)\]
• \[x_2 = (3, 3)\]
• \[x_3 = (6, 6)\]
• \[x_4 = (4, 5)\]

Berechne die Summe der quadratischen Abstände der Datenpunkte zu ihren jeweiligen Centroiden nach der ersten Iteration der Zuweisungsphase.

Hinweis: Die euklidische Distanz zwischen zwei Punkten \((x_1, y_1)\) und \((x_2, y_2)\) ist gegeben durch: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)

Lösung:

• Für \(x_1 = (2, 2)\):
  • Distanz zu \(\mu_1 = \sqrt{(2 - 2)^2 + (2 - 3)^2} = 1\)
  • Distanz zu \(\mu_2 = \sqrt{(6 - 2)^2 + (7 - 2)^2} = \sqrt{41}\)
  • Distanz zu \(\mu_3 = \sqrt{(5 - 2)^2 + (2 - 2)^2} = 3\)
  • \(x_1\) wird zu \(\mu_1\) zugeordnet. Quadratischer Abstand: \(1^2 = 1\)
• Für \(x_2 = (3, 3)\):
  • Distanz zu \(\mu_1 = \sqrt{(2 - 3)^2 + (3 - 3)^2} = 1\)
  • Distanz zu \(\mu_2 = \sqrt{(6 - 3)^2 + (7 - 3)^2} = \sqrt{25} = 5\)
  • Distanz zu \(\mu_3 = \sqrt{(5 - 3)^2 + (2 - 3)^2} = \sqrt{5}\)
  • \(x_2\) wird zu \(\mu_1\) zugeordnet. Quadratischer Abstand: \(1^2 = 1\)
• Für \(x_3 = (6, 6)\):
  • Distanz zu \(\mu_1 = \sqrt{(2 - 6)^2 + (3 - 6)^2} = \sqrt{25} = 5\)
  • Distanz zu \(\mu_2 = \sqrt{(6 - 6)^2 + (7 - 6)^2} = 1\)
  • Distanz zu \(\mu_3 = \sqrt{(5 - 6)^2 + (2 - 6)^2} = \sqrt{17}\)
  • \(x_3\) wird zu \(\mu_2\) zugeordnet. Quadratischer Abstand: \(1^2 = 1\)
• Für \(x_4 = (4, 5)\):
  • Distanz zu \(\mu_1 = \sqrt{(2 - 4)^2 + (3 - 5)^2} = \sqrt{8}\)
  • Distanz zu \(\mu_2 = \sqrt{(6 - 4)^2 + (7 - 5)^2} = \sqrt{8}\)
  • Distanz zu \(\mu_3 = \sqrt{(5 - 4)^2 + (2 - 5)^2} = \sqrt{10}\)
  • \(x_4\) wird zu \(\mu_1\) zugeordnet (bei Gleichstand kann beliebig gewählt werden). Quadratischer Abstand: \(8\)

Summe der quadratischen Abstände: \(1 + 1 + 1 + 8 = 11\)

Lösung:

K-means Clustering Algorithmus

• Datenpunkte werden zufällig in k Cluster eingeteilt
• Centroiden jedes Clusters berechnen
• Datenpunkte den nächstgelegenen Centroiden zuordnen
• Prozess iterativ wiederholen bis Stabilität
• Ziel: Minimierung der Summe der quadratischen Abstände der Datenpunkte zu ihren jeweiligen Centroiden
• Formel zur Berechnung der Distanz zu Centroiden:

• \[J = \sum_{i=1}^{k} \sum_{j=1}^{n} \vert\vert x_j^{(i)} - \mu_i \vert\vert^2\]

(b) Theoretische Analyse:

Nehmen wir an, Du hast einen Datensatz mit 3 Clustern und folgender Zentroiden-Konfiguration:

• \(\mu_1 = (2, 3)\)
• \(\mu_2 = (6, 7)\)
• \(\mu_3 = (5, 2)\)

Die Datenpunkte sind:

• \(x_1 = (2, 2)\)
• \(x_2 = (3, 3)\)
• \(x_3 = (6, 6)\)
• \(x_4 = (4, 5)\)

Berechne die Summe der quadratischen Abstände der Datenpunkte zu ihren jeweiligen Centroiden nach der ersten Iteration der Zuweisungsphase.

Hinweis: Die euklidische Distanz zwischen zwei Punkten \((x_1, y_1)\) und \((x_2, y_2)\) ist gegeben durch: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)

Lösung:

• Für \(x_1 = (2, 2)\):
  • Distanz zu \(\mu_1 = \sqrt{(2 - 2)^2 + (2 - 3)^2} = 1\)
  • Distanz zu \(\mu_2 = \sqrt{(6 - 2)^2 + (7 - 2)^2} = \sqrt{41}\)
  • Distanz zu \(\mu_3 = \sqrt{(5 - 2)^2 + (2 - 2)^2} = 3\)
  • \(x_1\) wird zu \(\mu_1\) zugeordnet. Quadratischer Abstand: \(1^2 = 1\)
• Für \(x_2 = (3, 3)\):
  • Distanz zu \(\mu_1 = \sqrt{(2 - 3)^2 + (3 - 3)^2} = 1\)
  • Distanz zu \(\mu_2 = \sqrt{(6 - 3)^2 + (7 - 3)^2} = \sqrt{25} = 5\)
  • Distanz zu \(\mu_3 = \sqrt{(5 - 3)^2 + (2 - 3)^2} = \sqrt{5}\)
  • \(x_2\) wird zu \(\mu_1\) zugeordnet. Quadratischer Abstand: \(1^2 = 1\)
• Für \(x_3 = (6, 6)\):
  • Distanz zu \(\mu_1 = \sqrt{(2 - 6)^2 + (3 - 6)^2} = \sqrt{25} = 5\)
  • Distanz zu \(\mu_2 = \sqrt{(6 - 6)^2 + (7 - 6)^2} = 1\)
  • Distanz zu \(\mu_3 = \sqrt{(5 - 6)^2 + (2 - 6)^2} = \sqrt{17}\)
  • \(x_3\) wird zu \(\mu_2\) zugeordnet. Quadratischer Abstand: \(1^2 = 1\)
• Für \(x_4 = (4, 5)\):
  • Distanz zu \(\mu_1 = \sqrt{(2 - 4)^2 + (3 - 5)^2} = \sqrt{8}\)
  • Distanz zu \(\mu_2 = \sqrt{(6 - 4)^2 + (7 - 5)^2} = \sqrt{8}\)
  • Distanz zu \(\mu_3 = \sqrt{(5 - 4)^2 + (2 - 5)^2} = \sqrt{10}\)
  • \(x_4\) wird zu \(\mu_1\) zugeordnet (bei Gleichstand kann beliebig gewählt werden). Quadratischer Abstand: \(8\)

Summe der quadratischen Abstände: \(1 + 1 + 1 + 8 = 11\)