date-created: 2024-06-14 04:28:34 date-modified: 2024-07-16 05:30:39

Clustering

anchored to 116.00_anchor_machine_learning

Overview

Wir wollen Datenpunkte unter Betrachtung und Methoden in gewisse Bereiche aufteilen und clustern.

Betrachten wir also ferner eine Datenmenge: un dwollen hier jetzt schauen, wie man sie aufteilen kann in verschiedene Bereiche / Untergruppen bzw Mengen.

Wir können diese Struktur jerzt verschieden Strukturieren bzw in verschiedene Klassen / Mengen aufteilen: Einmal könnte man sie in 2 Cluster aufteilen (grob) oder sie in kleinere 5 CLuster (feiner):

Awendung: Das kann man etwa in der phylogenetischer Beziehungen anwenden –> ALso herausfinden, wie nah gewisse Tiere in ihrer Genetik und Abstammung sind. Damit kann man dann etwa diverse Vögel die sich vielleicht ähneln genau einordnen und schauen, inwiefern sie denn überhaupt verwandt sind.

[!Definition] Allgemeine Idee bei Clustering

Beim Clustering haben wir erstmal nur Eingabedaten, die keine Labels aufweisen.

Es wird unser Ziel sein ein Mapping von Eingaben zu einer Diskreten Zahl - Cluster Nummer - berechnen zu können.

Was streben wir also unter Betrachtung und Verarbeitung der Daten an? Was können wir im Gegensatz zur Dimensionalitätsreduktion aussagen? #card

Wir wollen hier primär für die gegebenen Daten eine Struktur –> Cluster hier, finden und jedem Punkt eine Zugehörigkeit in einem Cluster zuschreiben.

Dabei können wir hier einige alternativen Betrachtung zur Dimensionalitätsreduktion einsehen:

• hier hatten wir einen Eingabepunkt - hohe Dim - genommen und diesem in niedrig-dim Raum dann einen Vektor zugeordnet –> Quasi ein Mapping von hohen zu niedrigen Werten, wobei wir wenige Daten verlieren wollten.

Es gibt üblicherweise kein absolut bestes Clustering –> Das hägt meist davon ab, was über die Daten schon bekannt ist –> Etwa, wenn wir ansetzen und entsprechend umformen

Clustering Definition

Auch hier teilen wir wieder in Clustering in einer transduktiven und induktiven Art auf.

[!Definition] Definition

Betrachten wir eine Menge von Daten $X=\{x^1,\dots ,x^N\}\subset {\mathbb{R}}^d$ die in eienr hohen Dimension auftreten.

Wir wollen jetzt zwei Arten von Clustering-Methoden betrachten und diese spezifisch betrachten / beschreiben: transduktiv und induktiv

Was ist unser Ziel beim transduktiven Clustering und was ist es beim Induktiven? #card

Transduktiv: Wir teilen Punkt aus einer Datenmenge $X$ in verschiedene Cluster auf.

Idee dabei: Elemente innerhalb eines Clusters sind ähnlich zueinander, Elemente in verschiedenen Clustern sind sich jedoch unähnlich (obv)

Induktiv:

(ist die Funktionalere Variante):

Wir Definieren eine Partitionnierungsfunktion $f:{\mathbb{R}}^d\to \{1,\dots ,K\}$ und setzen sie dann in $S_k=\{x\in X:f(x)=k\}>>(dieNeuenPunkte$x \neq X,$ können dann ein Cluster-Labelerhalten, was sie einordnet und uns so hilft sie zu interpretieren und verstehen!)

Agglomerate Clustering \ Linkage Clustering (Transduktive Clustering )

Single Linkage Clustering |

[!Req] Definition | Single Linkage Clustering

Wir beschreiben mit SLC einen Typ des hierarchischem Clustering - als entsprechender Algorithmus

Ferner ist es ein Typ des agglomerate Clusterings

Wie nennt man es auch? Was ist die Grundlegende Idee des Algorithmus? #card

Wir nennen es auch Nearest Neighbour Clustering -> weil es genau diese Idee / Struktur umsetzt:

• Wir führen Cluster zusammen, indem wir immer die kürzesten Distanzen zwischen Clustern vereinen und somit nach und nach Cluster aufbauen.

–> Man beginnt bei einem Cluster pro Datenpunkt und wird dann durch diese Kombination nach und nach größer Cluster - und weniger - aufbauen!

[!Beweis] Ablauf Single Linkage Clustering

Wir wollen die Umsetzung direkt unter Betrachtung eines Beispiels anwenden:

Betrachten wir die Datenpunkte $x_{i} = { A,B,C,D,E }$>>>>Wirsagen\ast \ast amAnfang\ast \ast ,dasseinjederDatenpunkt\ast \ast seineigenesCluster\ast \ast ist/beschreibt(alsowirhabendemnachauf$\mid X\mid$ viele Cluster zu Beginn)

Wie fahren wir jetzt fort, was wird als nächstes getan? und wie bauen wir jetzt ein passendes Clustering der Daten auf? Was müssen wir pro Schritt immer berechnen?! #card

Anschließend möchten wir die euklidische Distanz zwischen diesen Clustern berechnen und dann immer diese mit der geringsten Distanz zueinander zu einem Cluster zusammenfügen / kombinieren!

WICHTIG: Hierbei wird immer der geringste Abstand genommen. Wenn wir, wie im Beispiel, also den Abstand vom Cluster “rot” (mit C,D) nach “orange”(E) betrachten, dann nehmen wir die kürzeste Distanz zu diesem Cluster: –> Ds bauen wir dann zu einem Graphen zusammen!

Wir nehmen nach diesem Schritt immer die ähnlichsten / kleinsten Cluster und fügen sie zu einem neuen Cluster zusammen –> wir verschmelzen also die Datenmenge von vielen großen Datenclustern zu kleineren zusammen, damit wir damit Ähnlichkeiten erkenne und darstellen können (könnten!)

Wir betrachten das visuell folgend: Schritt 2: Berechnung der Distanzen aller Paare / Cluster (werden wir immer wieder wiederholen)

Schritt 3.1: Cluster mit geringster Distanz zusammenfügen Schritt 3.2: Distanzen wieder updaten, etwa $d(S_{i), S_{j}} = \min\limits_{a\in S_{i}, b \in S_{j}} d_{ab})$

REPEAT until all Clusters are linked!

Wir wiederholen, bis alles verbunden ist.

[!Attention]

Der Algorithmus ist deterministisch (weil sich die Distanzen nicht veerändern)

[!Attention] MST durch Single Linkage Clustering

Diese Aufteilung entspricht des 111.26_Graphen_MST in dem Graphen, den wir aus all den Datenpunkten und den Abständen bestimmen können!

[!Bsp] Errungenschaft durch Single Linkage Clustering:

Wir wollen ferner abwägen, was beim anwenden des Algorithmus erreicht wurde:

• wir haben eine Hierarchie von den Clusterings erhalten.
  • am Anfang sind alle ihre eigenen Cluster
  • danach verschmelzen wir sie nach und nach zu gemeinsamen Paaren
• somit erhalten wir mit jeder Iteration wieder ein neues Clustering –> und diese werden immer größer / die Menge von Clustern immer kleiner

Was können wir aus dieser Aufteilung erhalten? Was hat das mit Dendrogrammen zu tun? #card

Wir können damit jetzt folgende Strukturen ableiten:

• ein gewünschtes Clustering, was alle Punkte passend aufteilt, befindet sich irgendwo in diesen Schritten - wir enden ja mit dem trivialen Cluster, wo alles drin ist
• Wir müssen also die Hierarchie entsprechend durchlaufen und an einem Punkt aufhören

Das können wir mit einem Dendrogramm darstellen!

Wir wollen diesen Graphen bzw diese Clusterung jetzt nachtragen in eine sinnige Repräsentation übernehmen und somit einen Sinn für diese Aufteilung einbringen / verleihen!

Dendrogramm-Darstellung

[!Definition]

Wir geben mit dem Dendrogramm ein baumartiges Diagramm dar, das die Abfolge von Verschmelzngen aufzeichnet.

Was stellt es dabei in jeder Ebene des Baumes dar? Was gibt die Hohe einer Linie an, wie können wir daraus ein passendes Clustering erzeugen/ resultieren? #card

Es repräsentiert hier die hierarchische Struktur des Clusterings!

Dabei wird eine Verschmelzung von zwei Clustern - die immer drunter liegen - durch eine horizontale Linie - Ursprung in zwei Clustern etwa - dargestellt.

Die Höhe dieser Linien beschreibt dabei den Abstand, den wir zuvor betrachtet und immer ausgewählt haben.

Wir können jetzt das Dendrogramm durch das “schneiden” an bestimmten Höhen anwenden, um ein Cluster zu erzeugen –> Alle Cluster, die unter der Linie verschmolzen sind, werden dann unser Ergebnis darstellen!

Hierbei ist immer die Höhe des Dendrogrammes wichtig, um anzugeben, wie nah sie beieinander sind oder wie weit sie entfernt sind. Die Konkreten Werte sind darin nciht wirklich zu finden, weil sie durch das Minima etc teils bisschen unpassend auftreten

[!Bsp] Cluster Findung:

Wir wissen, dass wir aus einem Dendrogramm jetzt durch das Aufteilen Cluster betrachten können.

Wie berechnen wir die Höhe einer Linie in dieser Darstellung? #card

Die Höhe der Verschmelzung - pro Ebene / Cluster-Vereinigung - ist beschrieben mit: $h_{C,D} = \frac{d_{CD}}{2}$-->AlsowirnehmendieDistanzund\ast \ast halbieren\ast \ast sie.>>AusdiesemDendrogrammkannmanjetzt\ast \ast verschiedeneCluster\ast \ast bilden,indemmanimmerbei\ast \ast erschiedenenH\ddot{o}hen\ast \ast zerteiltunddamitdanndie\ast \ast entstehendenTeil-Bereiche\ast \ast Clusterdarstellen:>>>-->Hierw\ddot{a}renesdann3Cluster(A,B),(C,D),(E)!DieWerte,dieimmer\ddot{u}bereinerVerbindungvonzweiClusternstehen,bezeichnen\ast \ast dieDistanz\ast \ast zwischenzweiClustern.ImBeispielobenetwa:DieDistanzzwischen$A$und$B$liegtbei$1.1$ / Die Distanz zwischen dem Cluster (A,B) und (C,D,E) liegt bei 0.1!

Andere Linkage-Based-Clusterings

Neben dem Single-Linkage gibt es noch zwei weitere:

[!Beweis] Definition Avg | Complete Linkage / Max

Wir kennen schon das single linkage clustering, wobei immer die kleinste Entfernung zwischen Clusterelementen betrachtet und übernommen wird, also beschrieben mit: $$d(S_1,S_2)=\underset{i\in S_1,j\in S_2}{\min }d(x_i,x_j)$$

wie beschreiben wir jetzt AVG Linkage und Complete Linkage? #card

AVG Linkage baut so auf, dass esu allen Elementen des Clusters den Avg berechnet und das als Kriterium für die Vereinigung nutzt: $$d(S_1,S_2)=\frac{1}{\mid S_1\mid \mid S_2\mid }\sum _{i\in S_1,j\in S_2}(d(x_i,x_j))$$>>Und\ast \ast COMPLETE\ast \ast linkageisteinSystem,wasdie\ast \ast gr\ddot{o}ßteEntfernung\ast \ast betrachtetundverarbeitet:>(EsistdasrobustestegegenAusreißer!):>Wirberechnenfolgend:$$d(S_1,S_2)=\underset{i\in S,j\in S^{\prime }}{\max }d(x_i,x_j)$$

Ein Beispiel dazu können wir folgend betrachten:

Als Beispiel:

Wir betrachten schnell die einzelnen Linkages und ihre Dendrogramme:

beispiel | Anwendung von Complete Linkage Clustering

Folgend ein Tutorial / Beispiel, bei welchem complete linkage clustering genutzt wird, um die entsprechende Matrix und das Clustering umzusetzen: statistics how to Findet sich jetzt auch hier lokal: 116.22_complete_linkage_beispiel

Wichtig ist hierbei, dass wir darauf achten, dass wir für jedes Cluster- und dem neuen Punkt $P$ - schauen, was die maximale Distanz von Punkten im Cluster zu diesem Punkt sind. Anschließend werden wir diese Distanz gegen die, der anderen Cluster, vergleichen und das Minimum suchen / als Zuweisungskriterium wählen!

[!Information] Vorteil der Methode

Da wir hier immer die maximale Distanz eines Clusters zu einem anderen Punkt betrachten, sind wir sehr viel robuster gegen Outliers - solche, die nah am Datensatz liegen, aber schon abfallen und somit einzelne Ausreißer außerhalb des Ballungsgebietes darstellen!

source: link, stack exchange

Beispiel | Mit Rauschen

600 Datenwerte mit 4 erkennbaren Blobs. –> Was erwarten wir?

in der Single linkage hat man am Anfang sehr viele kleine Distanzen zwischen Punkten (sind die einzelnen in den Blobs selbst) und dann wird man am Ende $4$ große Distanzen berachten können ( von den 4 Clustern).

Probleme treten auf, wenn zwischen Clustern kleine Brücken auftreten und ferner kann es passieren, dass einzelne Punkte, die weiter entfernt von den nahen Brücken / Bereichen, dann als eigene Cluster erkannt werden und somit nicht mehr irgendwo zugehören, weil sie in der Distanz weiter weg sind, als die Brücken: –> hier sind die kleinen einzelnen Punkte rechts und links vom roten Cluster, aber auch links vom orangenen!

Beispiel mit einem ROboter, wo wir betrachten können, wie verschiedene Typen der Linkage helfen Daten zu interpretieren und zu verarbeiten:

Single Linkage kann hierbei oft nichts gutes finden, während Average meist robustere Cluster erzeugen kann!

Beispiel | Roboterdaten

[!Exampl]

betrachten wir einen Roboter, der autonom herum fahren kann - vorwärts, rückwärts, Drehungen.

Wir wollen Gesch, Winkelgesch mappen:

Wie werden Single Linkage / Average Linkage und Complete Linkage aufteilen? Was können wir im Bezug auf Robustheit erkennen? #card

Wir sehen hier:

• Single linkage ist sehr anfällig für Rauschen (Ausreißer)
• Avg linkage - da wir den Avg nutzen - wird dabei robuster aufteilen
• complete linkage agiert ähnlich zu Avg

wir können auch einsehen, dass je nach Menge der Cluster, die wir haben möchten, die Struktur der Cluster variiert:

Zusammenfassung | Eigenschaften

[!Satz] Zusammenfassung Linkage Clustering

Wir wissen jetzt, dass es ein hierarisches Clustering ist -> Siehe Dendrogramme, die es visualieren können

Was sagt transduktiv aus? Was macht single linkage gleichzeitig, was ist dessen nachteil? #card

• die Methode ist transduktiv –> jedem Punkt wird ein Cluster zugewiesen –> es gibt also keine Abbildungsfunktion, neue Punkte können wir nicht einfach einfügen!
• wird mit dem Dendrogramm visualisiert und hier wird auch ersichtlich, wie man es mit einem Cutoff in $K$ Cluster aufteilen kann!
• Die Linkage-Funktion ist wichtig zu wählen:
  • single linkage ergibt etwa einen MST, aber ist anfällig für Rauschen!
  • complete/avg linkage sind robuster gegenüber Rauschen –> Änderungen an einem einzelnen Punkt wichten nicht so hoch!

$k$-meansClustering\ast \ast Idee\ast \ast :>[!Idea]Ideef\ddot{u}rCentroid-BasedClustering>>Wirwollenf\ddot{u}reineDatenmenge$K$ Zentroid-Punkte finden ( das sind Zentroiden, die quasi eine Mitte der Datenmenge angibt), sodass dann die Punkte nah zu ihrem nächsten Zentrum sind.

Wir wollen also Punkte bestimmen, wo viele andere Punkte nah dran sind und diese dann nah zuordnen.

Dafür möchten wir zuvor eine Konzept einführen, dass die Idee besser beschreiben kann:

Centroid-based Clustering

[!Definition]

Als Idee sagen wir:

-> Finde $K$ znetroide-Punkte - Zentroide genannt - sodass alle Punkte nah an ihrem nächsten Zentrum sind.

Wie können wir das genau umsetzen? Wie beschreibt man eine Funktion, die genau das realisieren kann? #card

Das heißt wir wollen $k$vieleCentroidsdefinieren-jederf\ddot{u}reinCluster!,beschriebenmit$c_{1}, \dots ,c_{k} \in \mathbb{R}^{d}$>>Anschließendbrauchenwireine\ast \ast Zuordnungsfunktion\ast \ast ,diejedemWertdanngenaueinemdieserClusterzuweist/zuschreibt.>>Also$f: \mathcal{X} \to { 1, \dots ,K }$f(x)=\arg \underset{k=1,\dots K}{\min }\parallel x-c_i\parallel$$

Wir wollen jetzt genau diese Centroids so platzieren können, dass sie die Punkte im Cluster passend aufteilen kann!

Diese angestrebte Bestimmung der Cluster-Punkte bzw. die Berechnung ist nicht optimierbar bzw nicht einfach zu maximieren / optimieren.

Stattdessen werden wir jetzt durch eine Approximation solche Punkte finden oderapproximieren:

Durchgeführt durch Lloyd’s Algorithmus:

Lloyds Algorithmus: #nachtragen

Ist nicht ganz deterministisch:, da wir random initialisieren (was auch zu Problemen führen kann)

[!Definition] Lloyds Algorithmus:

Dieser Algorithmus versucht iterativ die besten Punkte für die Cluster zu finden:

Wie wird er aufgebaut? #card

\begin{algorithm} 

\begin{algorithmic}
\Procedure{LLOYD}{X,K}
\State $c_{1} \dots c_{K} = \text{ random or intelligent}$
\State $S_{1}, \dots ,S_{K} = \emptyset$
\While{$\text{ Änderungen in }S_{k}$}
\State $S_{k} = \{  i : f(x_{i} = k) \} \forall k$
\Comment{Punkte zuweisen}
\State $c_{k} = \frac{1}{\mid S_{k}\mid} \cdot \sum\limits_{ i \in S_{k}}^{}(x_{i}) \forall k$
\Comment{Zentrum anpassen --> Mitteln!}

\EndWhile \State $return ~ c_{1}, \dots c_{k}$ \EndProcedure

\end{algorithmic} \end{algorithm}

und visuell also folgend: 
![](116.12_clustering-20240716173854418.png)

![](116.12_clustering-20240716173909302.png)

Fazit: Dieses Clustering hängt stark von der Initialisierung ab, und kann so zu stark verschiedenen Centroiden und somit verschiedenen **Clustering** führen!

Alternativ (Besser): $k$-means++ Clustering

[!Definition] K-means++ Algorithmus

Wir wollen jetzt eine bessere Variante zum bestimmen von Clustern besprechen / definieren –> hierbei den LLOYD Algorithmus etwas besser umsetzen können!

Grundlegend arbeitet es genau, wie vorher nur Initialisieren wir anders –> Sodass die Startverteilung besser / sinniger gelegen ist!

Wie gehen wir dabei jetzt vor? #card

Wir berechen für jeden Punkt die Distanz zum nächsten Zentrum

Dann normalisieren wir die Distanz Anschließend schauen wir, wie wahrscheinlich dieser Datenpunkt unter Betrachtung seienr Distanz ist und damit können wir dann den neuen Punkt betrachten.

Danach wenden wir die “f” Funktion anwenden und uns damit dann besser der optimalen Position annähern

Im beispiel bei der zweiten Iteration wird der Punkt links oben genommen.

Random anfangsdatenpunkt nehmen ( also einen den wir kennen) Danach berechnen wir die Entfernung zu allen Datenpunkten zu diesen Datenpunkt.

Danach normieren wir die Distanz. Die am weitestens entferten Punkte werde dann am wahrscheinlichtsten zur nächsten Ausahl sein - die wir dann als möglichen Centroid anschauen.

Dieser mit der höchsten WSK werden wir dann als möglichen nächsten Punkt nehmen.

Jetzt: tun wir so , as wäre der vorerhige und der jetztige neue Punkt die K-means. Damit teilen wir in zwei Cluter auf. Danach berechnen wir jetzt die Distanzen zu den Punkten zu den zwei potentiellen Punkten betrachten.

Dadurch erhalten wir auch wieder ein paar Punkte mit hoher WSK auftreten, die wir dann wieder als mögliche Centroide anschauen und dann damit arbeiten könenn / möchten

–> Wir nehmen also die Datenpunkte selbst und schauen uns die Distanz an, schauen dann welcher am WSK ist und dann arbeiten.

Was dieser Algo kann:

• die komischen Ausreißer können mit diesem verhindert / verringert werden.
• aber es wird nicht deterministischer!

Problem:

Es wird hier immer von ausgegangen, dass die auftretenden Cluster etwa gleich groß sind und somit kann es bei unterschiedlicher größe zu suboptimalen Aufteilungen kommen

Diese Initialisierung schreiben wir etwa folgend auf:

Nachteile bei $k$-means Clustering?!

[!Example] Probleme die beim k-means clustering auftreten:

Wir wollen diese Daten immer mit 2 Clustern aufteilen / verarbeiten

Betrachten wir die folgenden Datensetz, welche Probleme können wir dann bei der Konstruktion von k-means finden / herauskristallisieren? #card

• Bei Clustern mit unterschiedlichen Größen werden die Centroids immer in Richtung des Größeren traversieren -> sich normalisieren

• Wenn die Cluster keine gefüllten Kugeln sind - oder wir solche Ringe habe - dann wird die euklidische Distanzfunktion nicht richtig helfen / passend sein!

• Wenn die Cluster verschiedene Dichten haben, dann wird das dichterer meist groß aufgeteilt!

K-means Variationen

[!Tip] Alternativen

Es gibt noch weitere alternative Variationen des k-means.

Welche zwei haben wir betrachtet? Wie gehen sie vor? #card

Wir haben zum einen $k-mediods$ betrachten, welche wie k-means funktionieren, aber die Centroids selbst Datenpunkte sind –> Man wird dann in jeder Iteration immer einen neuen Datenpunkt als bestes Mittel betrachten / konsultieren

k-medians:

• Auch wie k-means aber der Median der Datenpunkte wird genommen, um die Clustercenter zu bestimmen –> Er ist dabei also robuster gegen Ausreißer!

Wie das optimale $k$ bestimmen?

Elbow-Methode

Bildet noch eine Möglichkeit das Ganze umzusetze:

[!Proposition]

Wir wollen die Elbow-Methode betrachten: Sie zielt dabei darauf ab, die optimale Anzahl von Clustern - für ein Datenset - bestimmen zu können.

Wir verwenden dabei die WCSS - Within-Cluter Sum of Squares“ um das zu berechnen. Beschrieben wird sie mit: $$WCSS=\sum _{i=1}^K\left(\sum _{x\in S_i}(\parallel x-c_i{\parallel }^2)\right)$$

Was bestimmen wir dann damit, wie wird sie ausgewertet? #card

Es wird also der Gesamtabstund der Punkte zu den Clusterzentren betrachtet und evaluiert.

Anschließend plottet man die Werte des WCSS –> und man schaut, wo dann die Anzahl der Cluster am “optimalsten ist” -> Also die Abnahmerate am stärksten wechselt

Damit wird ein Gleichgewicht zwischen Clusterkompaktheitt und Menge der Cluster vorgeschlagen / aufgewiesen: