date-created: 2024-05-28 02:22:00 date-modified: 2024-06-02 03:57:38

Decision Trees

anchored to 116.00_anchor_machine_learning

Motivation

Zuvor haben wir uns der Klassifizierung durch 116.04_regression oder 116.05_MLE, also Methoden um Wahrscheinlichkeiten für lineare Funktionen oder Polynome gut berechnen und dadurch eine Klassifizierung mit diesen durchführen zu können. Wir haben bis dato nur lineare System betrachtet und ferner waren diese meist schon eher Komplex in ihrem Aufbau.

[!Motivation] Motivation von Decision Trees

Wir möchten bisherige lineare Modell insofern ersetzen, dass wir weniger Komplexe Entscheidungen zur Zuordnung von neuen Einträgen / Werten erreichen möchten.

Was wäre eine Kernidee um jetzt Decision Trees umzusetzen? #card

Hierbei möchten wir einfache Metriken einbringen, die binäre Entscheidungen - pro Stufe - ermöglichen und wir uns somit bei der Entscheidung einer Baumstruktur anpassen, in welcher wir etwas suchen und einfügen wollen

Alternativer Ansatz zu Regression: Es besteht auch die Möglichkeit einfach den gesamten Datensatz zu lernen, sodass man anschließend bei neuen Datenpunkten, schaut wo es sich im Cluster befindet und mit dieser Information dann den neuen Datenpunkt einer entsprechenden Klasse einfügt.

Das heißt man sammelt also Informationen um die umliegenden, bereits klassifizierten Werte, um dann eine Entscheidung für den neuen Punkt formen zu können.

Vorteile dieser Idee:

wir haben keine Trainingsphase - weil wir einfach die Daten anschauen und immer die nächsten Punkte betrachten, um zu entscheiden
kann man bei vorliegenden Daten gut interpretieren ( reasonable, etwa bei einem Cluster was vorliegt)
Mit KD-Trees / Approximate Nearest Neighbour Algorithmen kann man die Laufzeit auf $O (lo g N)$ verkürzen! Probleme dieser Idee:
Sie skaliert nicht gut –> Es benötigt $O (N)$ um die nächsten Datenpunkte unter $N$ Punkten finden zu können.
Es ist langsam in der Laufzeit –> Datenpunkt einfügen und dann alle Nachbar-Daten abrufen
Bei hohen Dimensionen wird klassifizierung schwierig –> Einordnen der Daten und Vergleichen wird schwierig!

Daher möchten wir uns jetzt also das Verfahren von Decision Trees anschauen, um eine Alternative bzw. einen anderen Ansatz betrachten und evaluieren zu können.

Decision Tree | Grundlage

(Wir werden uns die Definition unter Betrachtung eines Beispieles anschauen und aneignen. Hierbei möchten wir den Pflanzenwachstum unter Betrachtung bestimmter Parameter vorhersagen können)

[!Definition] Decision Tree

Wie der Name schon suggeriert handelt es sich um einen Baum welcher diverse Entscheidungsstufen aufweist.

Unter dieser Prämisse: Wie ist ein solcher Baum aufgebaut, auf welchem Prinzip baut er auf? Wo findet die Klassifizierung am Ende statt? #card

Die Baumstruktur hat in jeder Stufe eine Ja/Nein-Frage, welche uns dabei hilft in seinen Stufen zu traversieren.

Ein Decision Tree bildet dabei ein:

hierarchisches und ( weil die Stufen den Verlauf entscheiden)

nicht-parametrisches Modell für supervised learning (wir haben keine Parameter, mit welchen wir bearbeiten, sondern wir haben einfach die Regeln zum entscheiden)

Am Ende jedes Zweiges - also einem Blatt - findet sich die Klassifizierung / der Wert

Folgend haben wir im Kontext des Pflanzenwachstums-Problemes eine Möglichkeit in 4 Klassen / Stufen einordnen zu können.

Wir sehen also, dass dieser Baum aus bestimmten Komponenten besteht, die einen Entscheidungsprozess beim Einordnen neuer Daten ermöglicht.

Regressionsbaum | Entscheidungsbaum

In der Betrachtung von Decision Trees- Entscheidungsbäumen - spielen die Bäume und ihre Struktur eine wichtige Rolle.

Link

[!Definition] Regressionsbaum | Entscheidungsbaum

Was meinen wir mit einem Regressionsbaum? Was stellt er da? #card

Ein Regressionsbaum | Entscheidungsbaum bildet Daten in Form von Entscheidungsregeln ab. Hiermit wird also ein geschätzter Wert nicht durch mögliche Parameter - wie bei der Regression in 116.05_MLE - vorgegeben, sondern nach dem Durchlaufen des Baumes ein Wert gesetzt -> jenachdem, wie der Entscheidungsbaum resultierte

[!Tip] Komponenten des Entscheidungsbaumes

Wir können dem Entscheidungsbaum diverse Komponenten zuweisen.

Welche gehören dazu? Was befindet sich in diesen? #card

In dem Bild sehen wir verschiedene Bereiche:

der mittlere gibt einen internen Knoten an. Hier wird je nach Stufe $=$ Dimension! eine Eingabe mit einem Wert verglichen - eine Entscheidung getroffen! - und danach zu einem der beiden Kinder weitergeleitet.

Diese Kinder können interne Knoten oder Blätter sein –> diese geben einen Endwert an!

Das heißt also, dass bei einem Eingabewert mit jeder Stufe des Baumes eine bestimmte Dimension der Eingabe $X = x_{1}, x_{2}, \dots, x_{d}$ bearbeitet / verarbeitet wird, und wir dann anhand der Entscheidungen der Stufen eine Klassifizierung stattfinden lassen können!

[!Example] possible usage Haben wir wieder unser Pflanzenwachstums-Problem: Es liegt folgender Baum vor: Wobei wir folgenden Stufen folgende Werte zuweisen:

$x_{1}$ moisture

$x_{2}$ sun exposure

$x_{3}$ soil type

$x_{4}$ ph-value

$r$ output!

Mit diesen Grundinformationen: Wo wird der neue Punkt $x = (0.8, 6, b l a c k, 5.8, 0.05)$ eingeordnet? #card

Durchlaufen wir den Baum,dann kommen wir am Ende bei $T (x) = 2$ raus, was also der erwartete Wert ist!

Visualisierung:

Der Entscheidungsbaum hilft uns also dabei eine gewisse Dimension mit einfachen Entscheidungen abstecken, und somit Werte in bestimmten Bereichen einordnen und Charakterisieren zu können!

Ferner sehen wir auch, dass ein solcher Entscheidungsbaum dann einfach den Raum von Inputs entsprechend aufteilt, und somit in der Betrachtung vereinfacht.

Wie es beim Konzept von KD-Trees bereits umgesetzt wird, möchten wir Entscheidungsgrenzen definieren, die immer Achsen-Orientiert sind.

Dabei ist ferner relevant, wie wir unsere Grenzen setzen, damit dann die Entscheidungen von neuen Datenpunkte möglichst richtig gesetzt oder evaluiert / etabliert wird.

Vergleiche etwa general idea

Vergleich | Einbettung in Grundlegende ML-Pipeline

Betrachten wir ferner nochmal die Grundkonzepte von Machine-Learning-Modellen:

[!Important] Grundlegende ML-Pipeline

Welche drei großen Aspekte müssen wir bei einem Machine-Learning-Modell betrachten? #card

Die ML-Pipeline baut immer auf drei Punkten auf, die miteinander agieren und sich “verbessern/anpassen”.

Das Modell $g$ - welches uns eine Vorhersage geben / eine Entscheidung treffen möchten. Also es berechnet mit Parametern $θ$ $g (x ∣ θ)$

Wir haben einen Feedback-Mechanismus, der durch die Lossfunktion dargestellt wird –> Sie gibt an, wie falsch / wie viele Fehler unser Modell bei Predictions und dem erwarteten Wert macht. Beschrieben wird sie mit: $E (θ ∣ X) = t \sum l (r^{t}, g (x^{t} ∣ θ))$

Weiterhin gibt es jetzt den Part der Pipeline, welcher versucht die Parameter zu optimieren. Beschrieben als Optimierungsverfahren, was also aufgrund des Feedbacks der Lossfunktion nach und nach die besten Parameter finden möchte. Beschrieben mit $θ^{*} = ar g min E (θ ∣ X)$

Übernommen in unser System können wir diese Mechanismus auch wiederfinden, oder mögliche Alternativen betrachten.

[!Definition] ML-Pipeline mit Decision Trees

Wir haben jetzt also einen Decision-Tree, welcher gewisse Parameter für jeden Eintrag hat und dann damit eine Eingabe klassifizieren kann.

Wo sehen wir die drei Aspekte: Modell,Feedback-Mechanismus und Optimierung; in dieser Struktur? Was gibt es als Alternative zu einigen davon? #card

Das Modell ist hier folglich einfach der Decision-Tree

Die Parameter, die wir angeben ( und u.U. verbessern wollen) sind mit jedem Knoten festgelegt / beschrieben. Hierbei ist wichtig, dass die Parametergröße fest ist –> Denn wir haben nur bestimmte Mengen von Werten / Eingaben. (daher dann der Aspekt des non-parametric Modells!)

Es gibt hier keine Optimierung, durch eine Funktion, die das Minimum sucht –> Etwa der Gradientenabstieg bei 116.04_regression und Co! Konstruktion des Baumes muss überprüft und sinnig umgesetzt werden!

Aufbauen eines Decision Trees | ID3-Algorithmus

Wir haben also gesehen, dass es relevant ist, dass man den Decision Tree möglichst “effizient / richtig” aufbaut, damit er gut klassifizieren kann.

Dafür möchten wir uns ferner einen grundlegenden Algorithmus anschauen:

Dafür werden wir jetzt einen Regressionbaum mit einem quadratischen Loss aufbauen:

[!Definition] ID3-Algorithmus | Bauen eines Baumes

Wir wollen für eine Menge $I$ mit $k$ Mindesteinträgen jetzt einen Baum aufbauen. Dafür suchen wir immer die besten Einträge, die eine Entscheidung aufspannen –> also der beste Trenner des Raumes.

Wie bauen wir jetzt den PseudoCode auf, um das zu bewerkstelligen? Was muss hier beachtet werden (Hinblick auf Wahl des Parameters?) Was beschreiben wir mit $w$ in dem Kontext des Algorithmus? Was ist $x_{j}^{i}$ #card

$I$ gibt die Menge von Datenpunkten an , die wir betrachten und aufteilen wollen!

\begin{algorithm}
\begin{algorithmic}
\Procedure{BuildTree}{$\mathcal{I},k$} 
  \If{$\mid \mathcal{I}\mid >k$}
  	\Comment{ damit prüfen wir, ob wir genügend Daten haben, oder zu wenige vorliegen, um dann aufzusplitten}
  	\For{$\text{each split,dim} j \text{ and value} w$} 
  		\Comment{wir wollen aber nur endlich viele $w$ betrachten, sonst zu viel!}
  		\State\Comment{$w$ beschreibt den möglichen Trenner des Raumes in der Dimension $j$!}
  		\State $\mathcal{I}^{+}_{j,w} = \{  i \in \mathcal{I} \mid x^{i}_{j} > w \}$ 
  		\Comment{ $j$ gibt die Dimension an, in welcher wir soeben teilen / schauen!} 
  		\State \Comment{ wir sammeln die positiven Werte, daher $+$}
  		\State\Comment{$x^{i}_{j}$ gibt den Entscheidungsparameter abhängig der Dimension $j$ an!}
  		\State\Comment{$x^{i}_{j}$ beschreibt einen Datenpunkt, $x$ in Betrachtung der $j$-ten Dimension und $i$ gibt an welchen wir anschauen}
  		\State $\mathcal{I}^{-}_{j,w} = \{  i \in \mathcal{I}\mid x^{i}_{j} \leq w \}$
  		\Comment{Negativ-Beispiele, bzw. halt nicht Fall 1 (binary decision)}
  		\State $\hat{r}^{+}_{j,w} = avg_{i \in \mathcal{I}^{+}_{j,w}} r^{i}$ 
  		\Comment{we build the average for positive entries with the given metric}
  		\State $\hat{r}^{-}_{j,w} = avg_{i \in \mathcal{I}^{-}_{j,w}} r^{i}$ 
  		\State $E_{j,w} = \sum\limits_{i \in \mathcal{I}^{+}_{j,w}}( r^{-}- \hat{r}^{+}_{j,s})^{2} + \sum\limits_{i \in \mathcal{I}^{-}_{j,s}} ( r^{i}- \hat{r}^{-}_{j,w})^{2}$ 
  		\State \Comment{Wir haben also den Error berechnet, indem wir die Varianz beider Mengen berechnen}
  		
  	\EndFor
  	\State $(j^{*},w^{*)}= \arg\min_{j,w} E_{j,w}$ \comment{Wir wollen das Minimum für diese Dim und den Werten $w$ bestimmen} 
  	\State $\text{ return } Node(j^{*},w^{*}, BuildTree(\mathcal{I}^{-}_{j^{*},w^{*},k}) , BuildTree(\mathcal{I}^{+}_{j^{*},w** },k))$
  	\State \Comment{ Wir rufen also Rekursiv auf, wobei wir jetzt die linken/rechten Kinder bestimmen werden, und unseren Optimalen Parameter $j^{*},w^{*}$ bestimmt haben}
  \Else 
  \State $\text{ return } Leaf(Label = avg_{i \in \mathcal{I} r^{i}})$ \Comment{ Wir haben eine eindeutige Einordnung gefunden und müssen nicht weiter teilen!}
  \State \Comment{ das heißt auch, dass wir keine Fehler haben!}  
  \EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

Wir sehen hier, dass bei jedem Rekursiven Aufruf die übrig gebliene Menge genommen und dann zum Bauen bzw bestimmen der neuen Linie genutzt wird. Dass wir hier verschiedene Dimensionen betrachtet folgt daraus, dass es Trenner in verschiedenen Bereichen geben kann, die man finden könnte!

$x_{j}^{i}$ beschreibt einen Punkt $x$ innerhalb der Menge von betrachteten Punkten. Ferner ist $j$ die Dimension in der wir gerade sind und $i$ gibt an, welchen Eintrag aus $I$ wir anschauen

In unserem Beispiel können wir dann etwa folgen erkennen, wie dieses Prozedere durchgeführt werden kann / wird.

-> Wir sehen, dass hier nach der ersten Iteration der linke Bereich - blau - sofort bestimmt werden kann.

Ferner sieht man, wie der gelbe Parameter -> durch die optimalen Werte der Trennung bestimmt und gesetzt wird.

[!Attention] Aufwand des Findens eines Splitters: Da unser Raum u.U. reellwertig ist könnte es unendliche viele Möglichkeiten zum Aufteilen des Bereiches geben –> Das ist zu aufwendig, wir würden uns auf ein paar wenige limitieren.

Wie könnten wir vorgehen, um diese Menge von möglichen Trennern zu minimieren? #card

Wir haben zuvor bereits betrachtet, dass es immer wichtig ist, die Trennenden Parameter zu nehmen, die den größten Margin zwischen den nächsten Datenpunkten aufweisen. –> Wir können also einfach immer mögliche Linien, zwischen zwei Datenpunkten ausprobieren und betrachten. Hier suchen wir dann den mit dem größten Abstand zu beiden (oder mehreren Punkten) und können die in die Auswahl von möglichen Trennern aufnehmen! ( Ob es der beste ist, wird hier noch nicht entschieden!)

Regularisierung

Wie im folgenden Beispiel zu sehen ist / sein kann, kann es passieren, dass aus Versehen noch Trenner eingebracht werden, die keinen Mehrwert bieten. Also ein neuer Entscheidungsprozess wird angebracht, obwohl uns dieser keine neuen Informationen liefern kann / wird.

Weiterhin kann es immernoch zu Overfitting kommen!

Um das zu lösen, möchten wir einige Parameter zum vorherigen Algorithmus Aufbauen eines Decision Trees ID3-Algorithmus einfügen:

[!Definition] Erweiterung und Regularisierung des Decision-Tree Constructor

Wir möchten Probleme, wie Overfitting und nicht hilfreiche Aufteilungen vermeiden, also dann nicht einfügen / anbringen, wenn es dem Datensatz keinen Mehrwert bietet.

Unter Betrachtung des zuvor beschriebenen Algorithmus, wie können wir jetzt genau diese Regularisierung einbringen –> Also wir wollen einen Threshold schaffen, sodass darunter nichts akzeptiert wird? #card

Wir wollen ferner eine Regularisierung in die Kostenfunktion einbringen: Sie sieht somit um den Parameter $α$ erweitert, folgend aus: $E_{α} = i \in I \sum (r^{i} - T (x^{i})^{2}) + α \cdot # Bl \overset{a}{¨} tter ∣ T ∣$ Dadurch werden wir jetzt immer dann eine Bestrafung erhalten, wenn $α > 0$ ist!

Somit haben wir jetzt ein Maß geschaffen, um entscheiden zu können, ob etwas gut /schlecht ist –> Wir es also eventuell übernehmen oder nicht sollten.

Frage: Wann sollten wir schauen, ob jetzt eine neue Aufteilung / Entscheidungsoption angenommen werden sollte oder nicht?

Optimierung Decision Tree | Pre-Pruning

Wir haben jetzt also schon eine Metrik erhalten, um entscheiden zu können, ob es sich lohnt eine neue Entscheidung einzubringen oder nicht.

Das wollen wir bei Pre-Pruning beim Erstellen einer neuen Kante direkt prüfen!

[!Definition] Pre-Pruning

Wir wollen also beim Bauen des Bauemes schauen, ob sich eine weitere Aufteilung im derzeitigen Schritt lohnen würde oder nicht.

Wie können wir das in unserem Algorithmus einbauen? Welchen zusätzlichen If-Case brauch es bei einer Iteration? #card

Nachdem wir im Algorithmus $(j^{*}, w^{*}) = ar g min_{j, w} E_{j, w}$ bestimmt haben, also die minimalen Werte, werden wir jetzt mit einem If-Clause checken, ob wir den Treshhold überschreiten –> es sich also lohnt oder nicht!
\begin{algorithm} 
\begin{algorithmic} 
\If{$E_{(j^{*},w^{*}) } + \alpha \cdot 2 < E^{nosplit}$} \Comment{ also ist der Fehler jetzt geringer, also zuvor?}
  \state $\text{ return } Node(j^{*},w^{*}, BuildTree(\mathcal{I}^{-}_{j^{*},w^{8}}, k)BuildTree(\mathcal{I}^{+}_{j^{*},w^{8}}, k)$ \Comment{baue neuen Zweig auf}
\Else 
  \State $\text{ return } Leaf(label=avg_{i\in\mathcal{I}}r^{i})$

\EndIf

\end{algorithmic} \end{algorithm}


Wir entscheiden also nach der Konstruktion der **besten Parameter**, ob es sich gelohnt haben würde und jenachdem, ob es das tut, behalten wir sie und teilen weiter auf, oder beenden und geben ein **Blatt** als Resultat an!

Optimierung Decision Tree | Post-Pruning

Selbiges Prinzip, ob wir eine Entscheidung und somit Aufteilung erhalten / betrachten möchten oder nicht, folgt nun bei Post-Pruning. -> Nur eben nachdem der ganze Baum konstruiert wurde!

Wir pflücken also die unpassenden Zweige aus unserem Baum heraus, um jetzt einen optimalen konstruieren zu können.

Das Vorgehen ist hier ähnlich, aber etwas anders strukturiert bzw. durchgeführt!

[!Definition] Post-Pruning

Auch hier wollen wir einen optimalen Baum bauen, und schauen, ob sich manche Aufteilungen in diesem Baum lohnen oder nicht. Hierbei werden wir diese Optimierung nach der Konstruktion durchführen

Wie können wir jetzt den Baum nachträglich optimieren. Mit welchem Algorithmus geht das am optimalsten? #card

Wir möchten jetzt also den Baum erstmal konstruieren. Ist das abgeschlossen, werden wir den Baum in einer Tiefensuche durchlaufen (DFS)

Für jeden Knoten berechnen wir jetzt, wie viele Blätter er hat und weiterhin auch die Fehlerraten

$# Bl \overset{a}{¨} tter$ und

weiterhin $E_{α}^{+}, E_{α}^{-}, E^{n os pl i t}$

Mit diesen Werten prüfen wir jetzt, ob die neuen Fehler für $E_{α}^{+}, E_{α}^{-} \geq E^{n os pl i t}$ sind oder nicht. Also hat es sich verschlechtert oder ist gleich geblieben?

Ist das der Fall, dann verwerfen wir diesen Schnitt und machen ein Blatt daraus!

Sonst gehen wir den Baum weiter durch!

Betrachtet man es jetzt wieder am Beispiel, sieht der Vorgang folgend aus und wird folgendes Ergebnis liefern:

[!Important] Vergleich Pre/Post-Pruning

betrachte beide Verfahren, welches ist vorteilhafter, und warum? #card

Prinzipiell kann man sagen, dass Post-Pruning besser ist, weil es den Baum bauen lässt und hierbei dann die gesamte Struktur schon aufgebaut wurde (wo sich viele gute und womöglich auch einige schlechte Bereiche auftun bzw. vorkommen).

Classification Trees

Wir möchten also jetzt für $K$ viele Klassen ein System aufbauen, was uns dann für Punkte in unserem System entsprechend die Klassenzugehörigkeit zurückgeben kann / wird. Decision Trees im Vergleich sind einfach eine Struktur, die je nach Entscheidung etwas über einen Datenpunkt aussagen kann. Im vorherigen Beispiel war das etwa die Wachstumsrate pro Woche (Was nicht zwingend einer Klasse entsprechen muss!)

Wir wollen also erstmal die Rahmen betrachten und definieren:

[!Definition] Klassifikationsbäume | Grundlagen

Wir wollen folgende Voraussetzungen betrachten und mit diesen dann das Vorgehen definieren:

$K$ Klassen benannt mit $r \in {C_{1}, \dots, C_{K}}$

Ferner haben wir wieder die Baumfunktion (die also eine Entscheidung trifft, gemäß des Baumes selbst), welche die Klasse für einen Datenpunkt wiedergibt: $T (x^{i})$

Es gibt jetzt das Klassenvorkommen, beschrieben mit: $\hat{P} (C_{k} ∣ I) \equiv p_{k}^{I} 7$

wie beschreiben wir jetzt das Klassenvorkommen genau? Was ist mit dem Mehrheitsentscheid gemeint? Wie wird bei dieser Struktur der Loss umgesetzt? #card

Das Klassenvorkommen wird folgend für eine gegebene Indexmenge definiert: $p_{k}^{I} = \frac{# Klasse k}{∣ I ∣} = \frac{i \in I \sum ( 1 \cdot ( r ^{i} = k ))}{∣ I ∣}$

Der Mehrheitsentscheid versucht jetzt das Maximum der WSK für eine gegebene Indexmenge herausbekommen. Anders also eine besonders gute Einteilung der Datenpunkte durch die Trennung. Definiert dann mit: $\overset{r}{^} * I = ar g k max p_{k}^{I}$

Der Loss bezeichnet jetzt die Quantität der Fehler bei der Klassifizierung: $i \in I \sum (1 (r^{i} \neq = T (x^{i})))$

Betrachten wir dafür ein Beispiel, welches verschiedene Klassen in einem zwei-dim Raum verteilt:

Jetzt ist es aber wichtig, wieder herauszufinden, wo geteilt werden soll. Dafür möchten wir dann ferner die Impurity-Measure betrachten und konsultieren.

Node Impurity | Knotenunreinheit

–> Wir nennen einen Split rein (geringer Impurity grad), wenn folglich :: alle Daten, die einen bestimmten Zweig wählen zu einer einzigen Klasse gehören.

[!Idea] Impurity Measure Konzept / Ansatz –> Nach jeder Evaluation betrachten wir dann die Impurity measure, was uns dabei hilft zu evaluieren, wie rein ein Split ist. Im Kontext heißt es jetzt, dass etwas “rein” ist, wenn es zu einer einzigen Klasse gehört.

[!Definition] Impurity Measure | Entropy Wenn wir die Impurity Measure nutzen möchten, dann betrachten wir die Entropie der Indexmenge (die, die wir anschauen wollen).

Wie ist die Entropie $H^{I}$ definiert? Was können wir dann beim berechnen dieser Entropie aussagen / folgern? Wann resultiert $lo g_{2} (K)$ ? #card

Die Entropie gibt die Wahrscheinlichkeit der Streuung von verschiedenen Klassen in der Menge an. Dafür werden die WSK der einzelnen Klassen entsprechend summiert. $H^{I} = - k = 1 \sum K (p_{k}^{I} \cdot lo g_{2} \cdot p_{k}^{I})$

Hierbei sollten wir $lo g 0 \equiv 0$ verwenden

$lo g_{2} (K)$ resultiert, wenn alle Klassen gleich wahrscheinlich sind, bzw gleich häufig auftreten.

Wenn jetzt die Entropie $= 0$ ist, dann signalisiert es, dass alle Elemente einer Klasse angehören. Am Beispiel der obigen Menge können wir dann bei einer einfachen Trennung folgende Entropie berechnen: Ferner wäre für den grünen Teil: $I^{-} : p^{I^{-}} = (1, 0, 0) ⟹ H^{I^{-}} = 0$ Ferner wäre der orangene Teil: $I^{+} : p^{I^{+}} = (0.3, 0.4, 0.3) ⟹ H^{I^{+}} = 1.57$ Wir sehen hier ganz gut, dass eine geringere Entropie darauf hinweist, dass die Menge besser geordnet ist.

Wir wollen dann also unsere Entscheidung über einen Split über den besten Entropie-Wert festlegen und bestimmen.

Warum tritt ein Minus bei der Summe in der Definition der Entropie auf?:

Betrachtet man den Logarithmus, dann wächst er ab 0.
Da wir aber immer nur den Integral vom Logarithmus haben wollen (zur Darstellung der Entropie) und dieser negativ ist, müssen wir halt entsprechend invertieren
(Dazu gibts garantiert noch eine bessere Erklärung, aber das ist in etwa die Intuition.

Fehlklassifikation

Wenn wir jetzt die Entropie nutzen, um anzugeben, wie gut die Verteilung bzw der nächste Split sein wird, dann können wir dafür natürlich auch wieder den Fehler beschreiben.

[!Definition] Fehlklassifikation

Wie wird sie beschrieben / notiert? #card

$E = 1 - p_{k} max$

Gini-Impurity

The Gini impurity is calculated for a specific subset of data in a decision tree. –> The Gini impurity is a measure of how often a randomly chosen element would be incorrectly classified. It is used to evaluate how pure a node is in a decision tree. The Gini impurity for a subset is calculated by summing the squared probabilities of each class being chosen times the probability of a mistake in categorizing that class.

[!Definition] Was gibt der Impurity #card

Gini-Impurity ( nicht der Gini-Index!)

-> $I_{G} = k = 1 \sum K (p_{k} (1 - p_{k}))$

Wir berechnen diese Metrik für eine Submenge von Daten ( wenn wir etwa in zwei Bereiche teilen, dann werden wir hier zweimal berechnen, wie die Impurity für beide Bereiche ist). Für zwei Klassen gilt dann etwa: $I_{G} = 2 p_{1} (1 - p_{1})$ Das ist ähnlich der Struktur von Bernoulli-Verteilung

Das heißt also: Anhand der Metriken schauen wir, welchen Split wir nehmen möchten / werden –> Wenn es wie im Beispiel nicht eindeutig splittbar ist, dann werden wir also in der Iteration die Aufteilung minimieren und dann erst bei späteren Iterationen dann bessere bzw. weitere Splits einbauen!

Diskussionen | Entscheidungsbäume

[!Definition] Problem, dass Entscheidungsbäume nicht parametrisch

was sind Vorteile von Entscheidungsbäumen, was sind ihre Nachteile. bzgl der Vorteile, was können wir bei Datentypen #card

Vorteile:

Effizient aufrund der Baumstruktur - verglichen mit instanzbasierten Methoden, zB. $k$ -NN

Es reicht aus, die Baumstruktur zu speichern, nicht die Trainingsdaten, zB. $k$ -NN

Einfach zu verstehen und zu interpretieren

Bäume können visualisiert werden –> Macht es einfacher zu verstehen

Erforder wenig Datenvorbereitung –> Wir nutzen einfach die Daten

Kann sowohl numerische als auch kategoriale Daten verarbeiten Nachteile:

Overfitting passiert hier schnell durch sinnlose Splits.(Kann man aber mit Pruning etc reduzieren!)

Entscheidungsbäume können u.U. instabil sein. —> Das kann man mit Ensembles reduzieren!

optimale Decision Trees werden damit nicht garantiert.

Bagging / Random Forest

Random Forest –> Random Baum nehmen und dann wird man entsprechend einen großen daraus bauen / aufsetzen.

Ensembling:

Lernen mit Vielen Instanzen! Das Konzept wird nicht nur bei Bäumen verwendet.

[!Idea] Idee des Ensemblings

Wenn wir das Konzept von Ensembling anwenden, dann betrachten wir viele Instanzen auf der gleichen Menge und versuchen dann das Mittel über diese zu setzen. Dabei haben diese Modelle hohe Varianzen.

Wie wird Ensembling mathematisch beschrieben, wenn wir $M$ Modelle haben.Was bringt uns die hohe Varianz? #card

Dadurch, dass diese Bäume nun als Schätzer agieren ( also für Daten bestimmte Einordnungen vermuten) und eine hohe Varianz aufweisen, ergibt sich folgende Abhängigkeit: -> kleine Änderungen in den Daten haben drastische Auswirkungen auf die Vorhersagen des Baumes.

Wenn wir jetzt entsprechend das Mittel bilden wollen, dann konstruieren wir es folgend: $h (r ∣ x) = m \in M \sum (β_{m} h_{m} (r ∣ x))$ Beispielsweise könnte man beta folgend beschreiben: $β_{m} := \frac{1}{∣ M ∣}$

–> Ensemble-Modelle haben eine ähnliche Bias, denn alle von den vielen Modellen haben den gleichen Datensatz und weil sie gemittelt werden, übernimmt sich der Bias auch! Dennoch haben sie eine geringere Varianz

Das können wir jetzt auch für Bäume umsetzen –> Es gilt also verschiedene Bäume zu finden

Dafür können wir zwei Ansätze betrachten:

Bagging
Random Forest

Bagging | Bootstrap AGGregatING

[!Definition] Bootstrap-Sampling

was ist mit Bootstrap-Sampling gemeint? #card

Basically ist es ziehen mit Zurückziehen. –> Aus einem Datensatz der Größe $N$ ziehe man jetzt $N$ Datenpunkte mit Zurücklegen. Das sind die Trainingsdaten

Aus dieser Idee heraus können wir jetzt mehrere Versuche unter Anwendung des Bootstrap-Samplings umsetzen.

[!Information] Folgerung bei Bootstrapping mit $N$ Datenpunkten

was können wir unter Anwendung von Bootstrap-Sampling und dem Modell, dass dadurch die Daten sieht, sagen? Wie viel sieht es davon? Woraus folgt das #card

Das Modell sieht im Durchschnitt %63 der Eingaben –> Das folgt daraus, dass für einen Punkt die WSK $N -$ mal nicht gezogen zu werden folgend konnotiert ist: $(1 - \frac{1}{N})^{N}$

Für ein großes $N$ folgt dann folgend: -> $e^{- 1} \approx 0.37$

Die anderen 37% der Daten können dann entsprechend verwendet werden, um ein Test-Set aufzubauen, was die Leistung abschätzen lässt. –> ähnlich wie bei der Kreuzvalidierung, die wir zuvor betrachtet haben.

Der Aggregierungs part aus GGING folgt jetzt ferner:

[!Attention] wo wird aus Bagging, dann GGGING

unter der Betrachtung, dass wir Bootstrap-Sampling anwenden, wie aggregieren wir jetzt? #card

Die Aggregierung ist in dem Falle einfach das Trainieren von $M$ Modellen, woraufhin wir danach den Durchschnitt der Ausgaben berechnen

Random Forest

Random Forest sind jetzt noch eine Fortführung des vorherigen Konzepts (Bagging), jedoch mit additionaler Zufälligkeit.

[!Tip] Idee von Random Forest

Aus der Prämisse, dass Random-Forests eigentlich nur bagging + Zufälligkeit sind, wie können wir es konstruieren? Wie wird die Zufälligkeit realisiert? #card

ziehe hier also $M$ bootstrapped Datensätze, zum trainieren etc

baue weiterhin $M$ Modelle mit extra Zufälligkeit

ensemble Vorhersagen der Bäume (aggregieren)

Die “extra Zufälligkeit” folgt, wenn wir einen random Split betrachten und vornehmen –> Also statt das Beste zu finden, nutzen wir random Werte um zu teilen. Dadurch ist es nicht mehr deterministisch, wie ein Baum erstellt wird!!

–> Am beispiel etwa: wobei die gelben Linien random Werte $w$ sind und wir dann davon den besten suchen / nehmen (statt alle zu berechnen)

Dabei kann man jetzt ferner auch den Algorithmus zum Bauen des Baumes anpassen –>

Was muss jetzt beim Algorithmus angepasst werden? #card

\begin{algorithm}
\begin{algorithmic}
\Procedure{BuildTreeRND}{$\mathcal{I},k$} 
	\If{$\mid \mathcal{I}\mid >k$}
		\For{$\text{dim} j \in \text{random subset of dims} \land \text{ and random value} w$} 
			\State $\mathcal{I}^{+}_{j,w} = \{  i \in \mathcal{I} \mid x^{i}_{j} > w \}$ 
			\State $\mathcal{I}^{-}_{j,w} = \{  i \in \mathcal{I}\mid x^{i}_{j} \leq w \}$
			\Comment{Negativ-Beispiele, bzw. halt nicht Fall 1 (binary decision)}
			\State $\hat{r}^{+}_{j,w} = avg_{i \in \mathcal{I}^{+}_{j,w}} r^{i}$ 
			\State $\hat{r}^{-}_{j,w} = avg_{i \in \mathcal{I}^{-}_{j,w}} r^{i}$ 
			\State $E_{j,w} = \sum\limits_{i \in \mathcal{I}^{+}_{j,w}}( r^{-}- \hat{r}^{+}_{j,s})^{2} + \sum\limits_{i \in \mathcal{I}^{-}_{j,s}} ( r^{i}- \hat{r}^{-}_{j,w})^{2}$ 
			\State \Comment{Wir haben also den Error berechnet, indem wir die Varianz beider Mengen berechnen}
			
		\EndFor
		\State $(j^{*},w^{*)}= \arg\min_{j,w} E_{j,w}$ \comment{Wir wollen das Minimum für diese Dim und den Werten $w$ bestimmen} 
		\State $\text{ return } Node(j^{*},w^{*}, BuildTree(\mathcal{I}^{-}_{j^{*},w^{*},k}) , BuildTree(\mathcal{I}^{+}_{j^{*},w** },k))$
		\State \Comment{ Wir rufen also Rekursiv auf, wobei wir jetzt die linken/rechten Kinder bestimmen werden, und unseren Optimalen Parameter $j^{*},w^{*}$ bestimmt haben}
	\Else 
	\State $\text{ return } Leaf(Label = avg_{i \in \mathcal{I} r^{i}})$ \Comment{ Wir haben eine eindeutige Einordnung gefunden und müssen nicht weiter teilen!}
	\State \Comment{ das heißt auch, dass wir keine Fehler haben!}  
	\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

Es hat sich nicht viel geändert, außer, dass wir jetzt entsprechend die Splits random entscheiden und auch random Dimensionen dafür konsultieren!

Somit haben wir die Zufälligkeit in die Bildung eines Baumes gebracht, müssen jetzt aber noch entsprechend anpassen und hier den Random-Forest konstruieren

[!Definition] Konstruktion Random-Forest Wir haben den Algorithmus zum generieren eines zufälligen Baumes beschrieben, müssen jetzt aber erweitern, um einen Random-Forest zu bauen.

Wie gehen wir vor, um diesen Forest zu generieren? #card

Wie zuvor betrachtet, wollen wir also Bagging einbringen:

Ziehe $M$ bootstrapped Datensätze

baue $M$ Bäume mit extra Zufälligkeit

ensemble sieh –> Vorhersagen der Bäume

Als Algorithmus sieht das folgend aus:
\begin{algorithm} 
\begin{algorithmic} 
\Procedure{RandomForest}{$\mathcal{I},k, M$}
\For{$m =1 to~ M$}
  \State $\mathcal{I}_{m}= \text{Draw indices of bootstrap data from the training data }X$
   \State $\mathcal{T}_{m} = \text{ BuildTreeRnd}(\mathcal{I}_{m},k)$ 
\EndFor
\State $\text{ Ensemble trees} \{ T_{m} \}^{M}_{1}$
\EndProcedure
\end{algorithmic}
\end{algorithm}
Man kann für diesen Algorithmus auch verschiedene Verläufe / Eigenschaften betrachten: Am Ende erhalten wir für einen Datenpunkt dann verschiedene Pfade in den $M$ Bäumen!

Effekte von Random Forests:

Betrachten wir folgendes Beispiel, was Datenpunkte und die Anwendung von Decision Trees darstellt: Im BSP: Es gibt eventuell zwei verschiedene Aufsplittungen der Klassen –> Anhand der starken Linie zu erkennen!

Wenn man jetzt mehr und mehr dieser Bäume einbringt, steigt die confidence rate, wie in den Bildern erkennbar -> Farben geben an, wie sicher es sich ist. (je nach Farbe gibt die Intensität das an.)

Bei de Spirale kann man es ähnlich erkennen: Selbst mit weiterem Rauschen ist die Klassifizierung noch ok, wenn auch manche Punkte falsch gesetzt oder gelabeled werden

Mit Random-Forest können wir also ganz gut unterteilen. Jenachdem, wie tief wir die Bäume bauen lassen, können dabei Probleme auftreten –> auch wieder Over/Underfitting!

Effekte von Bagging

Random Note Optimization: -> Wo wird die Grenze innerhalb von zwei Datenpunkten gesetzt –> Also wo zwischen den Punkten setzen wir jetzt einen Schnitt?! (meist wollen wir ja den größten Margin haben)

Mit Bagging wird der Gradient der Confidence-Rate etwas verschoben –> Die Grenze zwischen diesen beiden Punkte ist somit nicht mehr so stark.

Dadurch werden Ausreißer nicht mehr so stark in die Wichtung genommen, weil da ja die Klassifizierungsrate sowieso nicht mehr so hoch ist ///

Mit Random Forest und Bagging erhalten wir generell eine bessere Skalierung für mehr Daten etc

Beispielhaft mit Bildern: –> Der Gradient ist feiner/stärker verrückt und somit werden Ausreißer noch richtig erkannt.

scattered-lenity

date-created: 2024-05-28 02:22:00 date-modified: 2024-06-02 03:57:38