Gehört zu: Klassifikation
Siehe auch: Machine Learning, Thermodynamik, Zustand
Benutzt: Latex-Plugin für WordPress, Fotos von Wikimedia

Stand: 26.01.2024

Was ist Entropie?

Der Begriff “Entropie” wird klassischerweise in der statistischen Thermodynamik verwendet.
Dieser Begriff wurde von Rudolf Clausius (1822-1888) in die Physik eingeführt.

Ludwig Boltzmann (1844-1906)  hat dann 1877 die berühmte Formel aufgestellt, die auch auf seinem Grabstein auf dem Wiener Zentralfriedhof steht:

\(  S = k \log_2{W} \\\)

Zur Beschreibung des Zustands eines physikalischen Systems wird eine physikalische Größe, die Entropie (Formelzeichen S) verwendet.   Wobei k die Boltzmann-Konstante und W eine Art “Wahrscheinlichkeit” für den Zustand sein soll…

Die Entropie wird auch gerne als Ausmaß von Unordnung der Teilchen eines Systems gesehen. Hohe Entropie wäre hohe Unordnung; niedrige Entropie wäre stärkere Ordnung der Teilchen.

Abbildung 1: Boltzmanns Grab (Wikimedia: Grab_von_Ludwig_Boltzmann_auf_dem_Wiener_Zentralfriedhof.JPG)

Klassifikationsalgorithmen

Beim “Machine Learning” ist es die allgemeine Aufgabe Muster in Datensätzen (Data Records) einer Datenmenge (Data Set – gerne falsch übersetzt mit “Datensatz”) zu finden.

Wenn wir ein Modell suchen, das Voraussagen zu einer Zielvariablen, einer Klassifikation, machen kann und wenn wir dazu ein Trainings-Datenmenge haben, sprechen wir von sog. “Supervised Learning“,

Ein Ansatz zur Klassifikation ist die wiederholte Aufteilung (rekursive Partitionierung).
Die “Güte” einer möglichen Aufteilung kann man durch den sog. Informationsgewinn, soll heissen Entropiedifferenz (nach der Aufteilung – vor der Aufteilung) bestimmen. So einen Klassifizierungsalgorithmus nennt man auch C5.

Zur Veranschaulichung nehmen wir mal ein ganz einfaches Beispiel. Eine Datenmenge soll eine binäre Klassifikation bekommen; z.B. Personen sind “kreditwürdig” oder “nicht kreditwürdig”.

Wir haben eine Trainings-Datenmenge in der Personen mit mehreren Attributen (“Features”) beschrieben sind; z.B. Jahreseinkommen, Alter, Name der Wohngemeinde, Einwohnerzahl der Wohngemeinde,…

Auch die Klassifikation auf der Trainings-Datenmenge ist bereits erfolgt. Wir haben da also schon ein Attribut Kreditwürdig Ja/Nein. Deshalb sprechen wir von “Supervised” Learning.

Diese gesamte Trainings-Datenmenge möchten wir anhand eines Entscheidungs-Kriteriums in zwei Teilmengen aufteilen, sodass die Summe der Entropien der Teilmengen kleiner ist als die Entropie der gesamten Trainings-Datenmenge.
So ein “Entscheidungs-Kriterium” wollen wir mithilfe der Datenattribute (den sog. Features) formulieren z.B. “Einwohnerzahl > 500”.

Zunächst haben wir also die Aufgabe, die Entropie (S) von Teilmengen der Trainings-Datenmenge zu bestimmen.

Quelle: https://rpubs.com/cyobero/C50

Die Formel lautet (nach Boltzmann s.o.)

\( S = \sum\limits_{i=1}^n {-p_i \cdot \log_2{p_i}} \\\)

Wobei n die Anzahl der Klassen in unserer Klassifizierung ist und p_i die Anteil der Datensätze, die in die Klasse i fallen.

Wenn wir, wie im Beispiel, eine binäre Klassifikation haben, ist n=2 und p₂ = 1- p₁.

Wir betrachten im Beispiel einmal folgende Trainingsmenge:

Tabelle 1: Trainingsmenge

Feature 1	Feature 2	Klasse
Gehalt	Alter	Kreditwürdigkeit
48000	./.	ja
30000	./.	nein
52000	./.	ja
31000	./.	nein
53000	./.	ja
32000	./.	nein
54000	./.	ja
55000	./.	ja
49000	./.	ja
33000	./.	nein

Hier haben wir p₁ =0.6 und p₂=0.4

Woraus sich eine Entropie für die gesamte Trainings-Datenmenge ergibt von:

\( S = -0.6 \cdot \log_2{0.6} – 0.4 \cdot \log_2{0.4} = 0.970951  \)

Wir versuchen jetzt einmal eine Partitionierung anhand von Feature 1 und probieren ein Kriterium Gehalt>50000. Daduch erhalten wir zwei Teilmengen durch Gehalt>50000 und Gehalt≤50000.

Tabelle 2: Teilmenge 1

Feature 1	Feature 2	Klasse
Gehalt	Alter	Kreditwürdigkeit
52000	./.	ja
53000	./.	ja
54000	./.	ja
55000	./.	ja

Hier haben wir p₁ = 1.0 und p₂ = 0.0

Das ergibt eine Entropie S₁ = 0.0

Tabelle 3: Teilmenge 2

Feature 1	Feature 2	Klasse
Gehalt	Alter	Kreditwürdigkeit
48000	./.	ja
30000	./.	nein
31000	./.	nein
32000	./.	nein
49000	./.	ja
33000	./.	nein

Hier haben wir p₁ =0.3333 und p₂ = 0.6667

Das ergibt eine Entropie S₂ = 0.918296

Nun müssen wir die beiden “Teil-Entropien” addieren.
Dazu gewichten wir jede Teilmenge i mit dem Anteil der Datensätze, die in diese Teilmenge fallen w_i.
Wir bekommen als Gewichte: w1=0.4 und w2= 0.6 und damit die Gesamtentropie nach erster Aufteilung bei Gehalt>50000:

\( S = w_1 \cdot S_1 + w_2 \cdot S_2 = 0.4 \cdot 0.0 + 0.6 \cdot 0.918296 = 0.5509776 \)

Durch die Aufteilung haben wir also Informationsgewinn (Differenz der Entropien) von:  0.970951 – 0.5509776 = 0,419973

Das ist schon einmal ganz gut, wir müssen nun noch prüfen, ob wir bei einer anderen Aufteilung im Feature “Gehalt” noch besser würden und ob eine Aufteilung nach einem andren Feature (z.B. “Alter”) ein noch größeren Informationsgewinn bringen würde.