Exakter Split für binäre Klassifizierung mit numerischen Merkmalen

In dieser Einheit lernen Sie den einfachsten und häufigsten Splitter-Algorithmus kennen, der Bedingungen mit der Form $\mathrm{feature}_i \geq t$ in der folgenden Einstellung erstellt:

• Aufgabe zur binären Klassifizierung
• Ohne Werte in den Beispielen
• Ohne im Voraus berechneten Index für die Beispiele

Angenommen, es sind mehrere $n$-Beispiele mit einem numerischen Merkmal und einem binären Label &ort;"blue". Grundsätzlich wird das Dataset $D$ so beschrieben:

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

wobei

• $x_i$ ist der Wert eines numerischen Merkmals in $\mathbb{R}$ (die Menge der reellen Zahlen).
• $y_i$ ist ein Label für eine binäre Klassifizierung in {orange, blue}.

Unser Ziel ist es, einen Grenzwert $t$ (Schwellenwert) zu finden, mit dem die Beispiele $D$ in die Gruppen $T(rue)$ und $F(alse)$ gemäß der Bedingung $x_i \geq t$ unterteilt werden, um die Trennung der Labels zu verbessern. Beispiele für mehr Beispiele in $T$.$&$;blau

Die Shannon-Entropie ist ein Maß für Störung. Für ein binäres Label:

• Die Shannon-Entropie ist optimal, wenn die Labels in den Beispielen ausgewogen sind (50% blau und 50% orange).
• Die Shannon-Entropie beträgt mindestens (Wert null), wenn die Labels in den Beispielen rein sind (100% blau oder 100% orange).

Abbildung 8. Drei verschiedene Entropiestufen.

 

Grundsätzlich möchten wir eine Bedingung finden, mit der die gewichtete Summe der Entropie der Labelverteilungen in $T$ und $F$ verringert wird. Der entsprechende Wert ist der Informationsgewinn, der die Differenz zwischen $D$'s Entropie und {$T$,$F$} Entropie ist. Dieser Unterschied wird als Gewinn von Informationen bezeichnet.

Die folgende Abbildung zeigt eine fehlerhafte Aufteilung, bei der die Entropie hoch bleibt und die Informationen niedrig werden:

Abbildung 9. Eine fehlerhafte Aufteilung reduziert die Entropie des Labels nicht.

 

Im Gegensatz dazu zeigt die folgende Abbildung eine bessere Aufteilung, bei der die Entropie niedrig wird (und die Informationen hoch werden):

Abbildung 10. Eine gute Aufteilung reduziert die Entropie des Labels.

 

Offiziell:

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

wobei

• $IG(D,T,F)$ ist der Informationsgewinn aus der Aufteilung von $D$ in $T$ und $F$.
• $H(X)$ ist die Entropie der Beispiele $X$.
• $|X|$ ist die Anzahl der Elemente im Satz $X$.
• $t$ ist der Grenzwert.
• $pos$ ist der positive Labelwert, z. B. "blue" im Beispiel oben. Die Auswahl eines anderen Labels als „positives Label“ hat keinen Einfluss auf den Wert der Entropie oder den Informationsgewinn.
• $R(X)$ ist das Verhältnis der positiven Labelwerte in den Beispielen $X$.
• $D$ ist das Dataset (wie zuvor in dieser Einheit definiert).

Im folgenden Beispiel wird ein binäres Klassifizierungs-Dataset mit einem einzelnen numerischen Merkmal $x$ betrachtet. Die folgende Abbildung zeigt verschiedene Schwellenwerte von $t$-Werten (x-Achse):

1. Das Histogramm des Elements $x$.
2. Das Verhältnis von „blau“-Beispielen in den Werten „$D$“, „$T$“ und „$F$“ richtet sich nach dem Grenzwert.
3. Entropie in $D$, $T$ und $F$.
4. Der Informationsgewinn, d. h. das Entropiedelta zwischen $D$ und {$T$,$F$}, gewichtet nach Anzahl der Beispiele.

Abbildung 11. Vier Schwellenwertdiagramme

 

Diese Diagramme zeigen Folgendes:

• Die Frequenz „Plot“ zeigt, dass die Beobachtungen bei einer Konzentration zwischen 18 und 60 relativ gut verteilt sind. Eine breite Wertverteilung bedeutet, dass es viele mögliche Aufteilungen gibt, die sich gut für das Training des Modells eignen.

• Das Verhältnis von "blauen" Labels im Dataset beträgt ca. 25%. Das Verhältnis von blauem Label – zeigt für Schwellenwerte zwischen 20 und 50:

  • Das Set $T$ enthält zu viele Labels des Typs Blau (bis zu 35% für den Grenzwert 35).
  • Das $F$-Set enthält ein ergänzendes Defizit von "blauen" Labelbeispielen (nur 8% für den Grenzwert 35).

  Sowohl das Verhältnis von blauen Labels als auch das Diagramm von „Entropie“ zeigen an, dass die Labels in diesem Schwellenwertbereich relativ gut getrennt werden können.

• Diese Beobachtung lässt sich anhand des Informationsgewinns erkennen. Wir sehen, dass der maximale Informationsgewinn mit t~=28 für einen Informationsverstärkungswert von ~0,074 erzielt wird. Daher wird die vom Split zurückgegebene Bedingung so berechnet: $x \geq 28$.

• Der Informationszuwachs ist immer positiv oder null. Er nähert sich null an, da sich der Grenzwert dem Höchst- bzw. Minimalwert nähert. In diesen Fällen wird entweder $F$ oder $T$ leer, während die andere das gesamte Dataset enthält und eine Entropie entspricht, die mit der in $D$ übereinstimmt. Der Informationszuwachs kann auch null sein, wenn $H(T)$ = $H(F)$ = $H(D)$. Bei Schwellenwerten von 60 $ sind die Verhältnisse von $B$D und $D$ für $$$ und F$ gleich und $D$F.

Die Kandidatenwerte für $t$ im Satz der reellen Zahlen ($\mathbb{R}$) sind unbegrenzt. Unter einer begrenzten Anzahl von Beispielen gibt es jedoch nur eine begrenzte Anzahl von Divisionen von $D$ in $T$ und $F$. Daher ist nur eine begrenzte Anzahl von Werten von $t$ für den Test aussagekräftig.

Ein klassischer Ansatz besteht darin, die Werte x_i in aufsteigender Reihenfolge x_s(i) so zu sortieren:

$$ x_{s(i)} \leq x_{s(i+1)} $$

Testen Sie dann $t$ für jeden Wert auf halber Strecke zwischen aufeinanderfolgenden sortierten Werten von $x_i$. Angenommen, Sie haben 1.000 Gleitkommawerte eines bestimmten Merkmals. Angenommen, nach der Sortierung sind die ersten beiden Werte 8,5 und 8,7. In diesem Fall würde der erste zu testende Grenzwert 8, 6 betragen.

Formal betrachten wir die folgenden Kandidatenwerte für t:

$$ X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

Die Zeitkomplexität dieses Algorithmus ist $\mathcal{O} ( n \log n) $ mit $n$ der Anzahl von Beispielen im Knoten (aufgrund der Sortierung der Featurewerte). Bei Anwendung auf einen Entscheidungsbaum wird der Splitter-Algorithmus auf jeden Knoten und jedes Feature angewendet. Jeder Knoten erhält etwa 1/2 seiner übergeordneten Beispiele. Demnach ist der Zeitaufwand für das Training eines Entscheidungsbaums mit diesem Teiler nach dem Mastersatz folgendermaßen:

$$ \mathcal{O} ( m n \log^2 n ) $$

wobei

• $m$ ist die Anzahl der Features.
• $n$ ist die Anzahl der Trainingsbeispiele.

In diesem Algorithmus spielt der Wert der Features keine Rolle, sondern nur die Reihenfolge. Aus diesem Grund funktioniert dieser Algorithmus unabhängig von der Skalierung oder der Verteilung der Featurewerte. Aus diesem Grund müssen wir die numerischen Features nicht normalisieren oder skalieren, wenn wir einen Entscheidungsbaum trainieren.