| archetype | title | author | readings | tldr | outcomes | quizzes | assignments | youtube | fhmedia | challenges | |||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
lecture-cg |
Entropie |
Carsten Gips (HSBI) |
|
Die Entropie kann als Maß für den Informationsgehalt einer Trainingsmenge betrachtet werden:
Wieviele Ja/Nein-Entscheidungen sind nötig, um die Daten fehlerfrei zu repräsentieren?
Nach der Wahl eines Attributs kann die verbleibende mittlere Entropie berechnet werden. Damit
hat man ein Kriterium für die Auswahl von Attributen beim Aufbau von Entscheidungsbäumen:
Nimm das Attribut, welches einen möglichst hohen Informationsgehalt hat. Oder andersherum:
Wähle das Attribut, bei dem die verbleibende mittlere Entropie der Trainingsmenge nach der
Wahl des Attributs am kleinsten ist.
|
|
|
|
|
**Entropie einer Trainingsmenge**
Betrachten Sie die folgenden Aussagen:
> * Patient A hat weder Husten noch Fieber und ist gesund.
> * Patient B hat Husten, aber kein Fieber und ist gesund.
> * Patient C hat keinen Husten, aber Fieber. Er ist krank.
> * Patient D hat Husten und kein Fieber und ist krank.
> * Patient E hat Husten und Fieber. Er ist krank.
Aufgaben:
1. Geben Sie die Entropie |
::: notes
- Zyklische Iteration durch die Trainingsmenge
- Ausschließlich aktuelles Objekt betrachtet
- [Reihenfolge]{.alert} der "richtigen" Attributwahl bei Verzweigung unklar
=> Betrachte stattdessen die komplette Trainingsmenge! :::
- Shannon/Weaver (1949): [Entropie]{.alert}
- Maß für die Unsicherheit einer Zufallsvariablen
- Anzahl der Bits zur Darstellung der Ergebnisse eines Zufallsexperiments
\bigskip
- Münze, die immer auf dem Rand landet: keine Unsicherheit, 0 Bit
- Faire Münze: Kopf oder Zahl: Entropie 1 Bit
- Fairer 4-seitiger Würfel: 4 mögliche Ausgänge: Entropie 2 Bit
- Münze, die zu 99% auf einer Seite landet: Entropie nahe Null
\smallskip => Anzahl der Ja/Nein-Fragen, um zur gleichen Information zu kommen
\bigskip
- Zufallsvariable
$V$ => mögliche Werte$v_k$ - Wahrscheinlichkeit für
$v_k$ sei$p_k = P(v_k)$
::: cbox
\bigskip \bigskip \bigskip
:::::: columns ::: {.column width="40%"}
[Hinweis]{.alert}:
::: ::: {.column width="50%"}
::: ::::::
::: notes
- Nur eine Klasse:
$\log_2 1 = 0$ =>$H(V) = 0$ Bit - Zwei Klassen, gleichwahrscheinlich:
$\log_2 0.5 = -1$ =>$H(V) = 1$ Bit :::
::: cbox
Entropie:
\bigskip \bigskip
:::::: columns ::: {.column width="75%"}
$v_1 = \operatorname{Kopf}, v_2 = \operatorname{Zahl}$ $p_1 = 0.5, p_2 = 0.5$ -
$H(\operatorname{Fair}) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1$ Bit
::: ::: {.column width="25%"}
::: ::::::
::: cbox
Entropie:
\bigskip \bigskip
:::::: columns ::: {.column width="75%"}
\pause
-
$v_1 = \operatorname{Kopf}, v_2 = \operatorname{Zahl}$ -
$p_1 = 0.99, p_2 = 0.01$ -
$H(\operatorname{UnFair}) = -(0.99 \log_2 0.99 + 0.01 \log_2 0.01)$ $H(\operatorname{UnFair}) \approx 0.08$ Bit
::: ::: {.column width="25%"}
::: ::::::
::: cbox
Entropie:
\bigskip \bigskip
:::::: columns ::: {.column width="75%"}
\pause
$v_1 = 1, v_2 = 2, v_3 = 3, v_4 = 4$ $p_1 = p_2 = p_3 = p_4 = 0.25$ -
$H(\operatorname{Wuerfel}) = -4\cdot(0.25 \log_2 0.25) = 2$ Bit
::: ::: {.column width="25%"}
::: ::::::
:::::: columns ::: {.column width="35%"}
| Nr. | ||||
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | A |
| 2 | 1 | 0 | 2 | A |
| 3 | 0 | 1 | 1 | A |
| 4 | 1 | 1 | 0 | B |
| 5 | 0 | 1 | 1 | B |
| 6 | 0 | 1 | 0 | A |
::: ::: {.column width="55%"}
\vspace{8mm}
- Anzahl Klasse
$A$ : 4 - Anzahl Klasse
$B$ : 2 - Gesamtzahl Beispiele: 6
Wahrscheinlichkeit für
Wahrscheinlichkeit für
::: ::::::
\bigskip \pause
\large
\normalsize
::: notes
-
Auswahl von Attribut
$A$ partitioniert die Trainingsmenge: \newline Je Ausprägung$v$ von$A$ erhält man eine Submenge$S_v$ -
$R(S, A)$ berechnet die mittlere Entropie der Trainingsmenge, nachdem Attribut$A$ ausgewählt wurde: Unsicherheit/nötige Bits nach Auswahl von Attribut$A$ :::
:::::: columns ::: {.column width="40%"}
| Nr. | ||||
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | A |
| 2 | 1 | 0 | 2 | A |
| 3 | 0 | 1 | 1 | A |
| 4 | 1 | 1 | 0 | B |
| 5 | 0 | 1 | 1 | B |
| 6 | 0 | 1 | 0 | A |
::: ::: {.column width="50%"}
\vspace{8mm}
- Sei Attribut
$x_1$ ausgewählt -
$x_1$ partitioniert die Trainingsmenge-
$x_1=0$ liefert$S_0 = \lbrace 1,3,5,6 \rbrace$ -
$x_1=1$ liefert$S_1 = \lbrace 2,4 \rbrace$ - Häufigkeit für
$x_1=0$ :$4/6$ - Häufigkeit für
$x_1=1$ :$2/6$ - Gesamtzahl Beispiele: 6
-
::: ::::::
\bigskip \pause
::: notes
Wir haben hier die Entropie
als Maß für den Informationsgehalt einer Trainingsmenge genutzt.
In anderen Entscheidungsbaumlernern wird stattdessen die Gini Impurity zur Bestimmung des Informationsgehalts eingesetzt (u.a. CART). Dieses Maß sagt aus, wie oft man ein zufällig gezogenes Element des Datensatzes falsch klassifizieren würde, wenn man es mit einer zufälligen Klasse basierend auf der Verteilung der Klassen im Datensatz labeln würde.
Hierzu drei lesenswerte Blog-Einträge:
- Deep dive into the basics of Gini Impurity in Decision Trees with math Intuition
- Decision Trees, Explained
- Decision Tree Algorithm With Hands-On Example :::
- Begriff und Berechnung der Entropie: Maß für die Unsicherheit
- Begriff und Berechnung des Informationsgewinns
- Entropie für eine Trainingsmenge
- Mittlere Entropie nach Wahl eines Attributs
::: slides
Unless otherwise noted, this work is licensed under CC BY-SA 4.0. :::