Répartition exacte pour la classification binaire avec des caractéristiques numériques

Dans cette unité, vous allez explorer l'algorithme de division le plus simple et le plus courant, qui crée des conditions au format $\mathrm{feature}_i \geq t$ avec le paramètre suivant:

• Tâche de classification binaire
• Sans valeurs manquantes dans les exemples
• Sans index précalculé sur les exemples

Supposons un ensemble d'exemples $n$ avec une caractéristique numérique et une étiquette binaire ""orange" et "bleu". Désignons officiellement l'ensemble de données $D$ comme suit:

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

où :

• $x_i$ est la valeur d'une caractéristique numérique dans $\mathbb{R}$ (l'ensemble de nombres réels).
• $y_i$ est une valeur de libellé de classification binaire en {orange, blue}.

Notre objectif est de trouver une valeur de seuil $t$ (seuil) de sorte que la division des exemples $D$ dans les groupes $T(rue)$ et $F(alse)$ en fonction de la condition $x_i \geq t$ améliore la séparation des étiquettes, par exemple d'autres exemples en $$$ et en $$$.

L'entropie de Shannon est une mesure du trouble. Pour une étiquette binaire:

• L'entropie de Shannon est maximale lorsque les étiquettes des exemples sont équilibrées (50% bleu et 50% orange).
• L'entropie de Shannon est minimale (valeur égale à zéro) lorsque les étiquettes des exemples sont purs (100% bleu ou 100% orange).

Figure 8. Trois niveaux d'entropie différents.

 

Officiellement, nous souhaitons trouver une condition qui diminue la somme pondérée de l'entropie des distributions d'étiquettes en $T$ et en $F$. Le score correspondant est le gagnement de l'information, qui correspond à la différence entre l'entropie $D$&$3$ et l'entropie {$T$,$F$}. Cette différence est appelée gain d'information.

La figure suivante montre une répartition incorrecte, dans laquelle l'entropie reste élevée et les informations deviennent faibles:

Figure 9. Une répartition incorrecte ne réduit pas l'entropie du libellé.

 

En revanche, la figure suivante montre une meilleure répartition dans laquelle l'entropie devient faible (et les informations deviennent élevées):

Figure 10. Une répartition appropriée réduit l'entropie du libellé.

 

Officiellement:

\[\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}\]

où :

• $IG(D,T,F)$ correspond au gain d'informations de la division de $D$ en $T$ et $F$.
• $H(X)$ est l'entropie de l'ensemble des exemples $X$.
• $|X|$ est le nombre d'éléments dans l'ensemble $X$.
• $t$ est la valeur du seuil.
• $pos$ est la valeur de libellé positive, par exemple "blue" dans l'exemple ci-dessus. Choisir un autre libellé comme & quot; positif libellé ne modifie pas la valeur de l'entropie ni du gain d'informations.
• $R(X)$ est le ratio de valeurs d'étiquettes positives dans les exemples $X$.
• $D$ est l'ensemble de données (tel que défini précédemment dans cette unité).

Dans l'exemple suivant, nous considérons un ensemble de données de classification binaire avec une seule caractéristique numérique xx$. La figure suivante illustre des valeurs de seuil de $t$ (axe des abscisses) différentes :

1. Histogramme de l'élément géographique $x$.
2. Proportion d'exemples "bleus" dans les ensembles $D$, $T$ et $F$ basés sur la valeur du seuil.
3. L'entropie en $D$, $T$ et $F$.
4. Le gain d'informations, c'est-à-dire le delta d'entropie entre $D$ et {$T$,$F$} pondéré par le nombre d'exemples.

Figure 11. Quatre graphiques représentant un seuil.

 

Ces graphiques indiquent les éléments suivants:

• Le graphique de la fréquence indique que les observations sont relativement bien réparties avec des concentrations comprises entre 18 et 60. Une répartition à grande échelle signifie qu'il existe un grand nombre de divisions potentielles, ce qui est bon pour l'entraînement du modèle.

• Le ratio d'étiquettes "bleues" dans l'ensemble de données est d'environ 25%. Le ratio d'une étiquette bleue indique les valeurs de seuil comprises entre 20 et 50:

  • L'ensemble $T$ contient un excès d'exemples de libellés bleus (jusqu'à 35% pour le seuil 35).
  • L'ensemble $F$ contient un déficit complémentaire d'exemples d'étiquettes "bleues" (seulement 8% pour le seuil 35).

  Les graphiques "libellés bleus" et "entropie" indiquent tous deux que les libellés peuvent être relativement bien séparés dans cette plage de seuils.

• Cette observation est confirmée sur le graphique de gain d'information. Nous constatons que le gain d'information maximal est obtenu avec t=28, pour une valeur de gain d'information d'environ 0,074. Par conséquent, la condition renvoyée par le séparateur sera $x \geq 28$.

• Le gain d'informations est toujours positif ou nul. Elle converge vers zéro lorsque la valeur du seuil converge vers sa valeur maximale / minimale. Dans ce cas, $F$ ou $T$ deviennent vides tandis que l'autre contient l'intégralité de l'ensemble de données et affiche une entropie égale à celle de $D$. Le gain d'information peut également être égal à zéro lorsque $H(T)$ = $H(F)$ = $H(D)$. Pour un seuil de 60 $, les ratios de libellés bleus et numériques sont les mêmes pour $T et $T$ que pour le $$$$$$$$$$$$$$$$$$$$$$$$.

Les valeurs proposées pour $t$ dans l'ensemble de nombres réels ($\mathbb{R}$) sont infinies. Cependant, étant donné un nombre fini d'exemples, il n'existe qu'un nombre fini de divisions de $D$ en $T$ et de $F$. Par conséquent, seul un nombre limité de valeurs de $t$ est pertinent pour le test.

Une approche classique consiste à trier les valeurs x_i dans l'ordre croissant x_s(i) comme suit:

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

Testez ensuite $t$ pour chaque valeur à la moitié des valeurs triées consécutives de $x_i$. Par exemple, supposons que vous ayez 1 000 valeurs à virgule flottante pour une caractéristique particulière. Après le tri, supposons que les deux premières valeurs sont 8,5 et 8,7. Dans ce cas, la première valeur de seuil à tester est 8,6.

Officiellement, nous prenons les valeurs suivantes pour t:

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

La complexité temporelle de cet algorithme est de $\mathcal{O} ( n \log n) $ avec $n$ le nombre d'exemples dans le nœud (en raison du tri des valeurs des caractéristiques). Lorsqu'il est appliqué à un arbre de décision, l'algorithme de division est appliqué à chaque nœud et à chaque caractéristique. Notez que chaque nœud reçoit environ la moitié de ses exemples parents. Par conséquent, selon le théorème maître, la complexité de l'entraînement d'un arbre de décision avec ce séparateur est la suivante:

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

où :

• $m$ correspond au nombre de caractéristiques.
• $n$ correspond au nombre d'exemples d'entraînement.

Dans cet algorithme, la valeur des caractéristiques n'a pas d'importance. Seul l'ordre est important. Pour cette raison, cet algorithme fonctionne indépendamment de l'échelle ou de la distribution des valeurs des caractéristiques. C'est pourquoi nous n'avons pas besoin de normaliser ni de mettre à l'échelle les caractéristiques numériques lors de l'entraînement d'un arbre de décision.