Quels critères un algorithme d’arbre de décision doit-il utiliser pour diviser les variables/colonnes ?

Avant de construire un algorithme d’arbre de décision, la première étape consiste à répondre à cette question. Jetons un coup d’œil à l’une des façons de répondre à cette question. Pour ce faire, nous devrons comprendre une utilisation de quelques concepts clés de la théorie de l’information.

Examinons cette méthode en procédant comme suit :

1. Examinons brièvement ce qu’est un arbre de décision.
2. Définissez et examinez la formule de l’entropie.
3. Discutez de ce qu’est un peu la théorie de l’information.
4. Définissez le gain d’information et utilisez l’entropie pour le calculer.
5. Écrivez quelques fonctions Python de base en utilisant les concepts ci-dessus.

En science des données, l’algorithme de l’arbre de décision est un algorithme d’apprentissage supervisé pour les problèmes de classification ou de régression. Notre objectif final est d’utiliser des données historiques pour prédire un résultat. Contrairement à la régression linéaire, les arbres de décision peuvent capter des interactions non linéaires entre les variables des données.

Regardons un arbre de décision très simple. Vous trouverez ci-dessous un flux de travail qui peut être utilisé pour prendre une décision de manger ou non un biscuit au beurre d’arachide.

Dans cet exemple, un arbre de décision peut prendre en compte le fait que vous ne devez manger le cookie que si certains critères sont remplis. C’est le but ultime d’un arbre de décision. Nous voulons continuer à prendre des décisions (scissions) jusqu’à ce que certains critères soient remplis. Une fois rencontré, nous pouvons l’utiliser pour classer ou faire une prédiction. Cet exemple est très basique en utilisant seulement deux variables (allergie, dîner ruinant). Mais, si vous avez un ensemble de données avec des milliers de variables / colonnes, comment décidez-vous quelles variables / colonnes sont les plus efficaces pour les diviser? Un moyen populaire de résoudre ce problème, en particulier si vous utilisez un algorithme ID3, consiste à utiliser l’entropie et le gain d’informations.

La tâche

Disons que nous avons des données et que nous voulons les utiliser pour créer un quiz en ligne qui prédit quelque chose sur le preneur du quiz. Après avoir examiné les relations dans les données, nous avons décidé d’utiliser un algorithme d’arbre de décision. Si vous n’avez jamais été aspiré par un quiz en ligne, vous pouvez voir des centaines d’exemples ici. Le but du quiz sera de deviner si le preneur du quiz vient de l’un des États du Midwest américain. Les questions du quiz tourneront autour de savoir s’ils aiment un certain type de nourriture ou non. Vous trouverez ci-dessous un petit ensemble de données fictives avec quinze entrées. Chaque entrée a des réponses à une série de questions. La plupart des questions portent sur le fait de savoir s’ils ont aimé un certain type de nourriture, auquel le participant a répondu (1) pour oui ou (0) pour l’instant. La dernière colonne (« midwest? »” est notre colonne cible, ce qui signifie qu’une fois l’arbre de décision construit, c’est la classification que nous essayons de deviner.

Entropie

Pour nous lancer, nous utiliserons une métrique de la théorie de l’information appelée entropie. En science des données, l’entropie est utilisée comme moyen de mesurer à quel point une colonne est « mixte”. Plus précisément, l’entropie est utilisée pour mesurer le trouble. Commençons par trouver l’entropie de notre colonne cible, « midwest?”.

Il y a dix personnes qui vivent dans le midwest et cinq personnes qui ne le font pas. Si quelqu’un vous demandait à quel point la colonne est mixte, vous pourriez dire qu’elle était en quelque sorte mélangée, avec une majorité (2/3) de personnes du midwest. L’entropie nous donne un moyen de quantifier la réponse ”en quelque sorte mixte”. Plus les (1) s et (0) s sont mélangés dans la colonne, plus l’entropie est élevée. Si « midwest? »si des quantités égales de (1) s et de (0) s, notre entropie serait de 1. Si « midwest? »composé seulement de (1) s l’entropie serait 0.

Nous pouvons utiliser la formule suivante pour calculer l’entropie:

Passons en revue chaque étape de la formule et calculons l’entropie pour le « midwest?” colonne.

1. Nous devons parcourir chaque valeur unique dans une seule colonne et l’affecter à i. Pour cet exemple, nous avons 2 cas (c) dans le « midwest? » colonne, soit (0), soit (1).
2. Nous calculons ensuite la probabilité que cette valeur se produise dans les données. Pour le cas de (1), la probabilité est de 10/15. Pour le cas de (0), la probabilité est de 5/15.
3. On prend la probabilité de chaque cas et on la multiplie par le logarithme base 2 de la probabilité. 2 est la base la plus courante car l’entropie est mesurée en bits (plus à ce sujet plus tard). L’explication complète de la raison pour laquelle 2 est utilisé est hors de portée de cet article, mais un utilisateur sur stack exchange offre une bonne explication. Pour le cas de (1), on obtient 10/15 * log2 (10/15). Pour le cas de (0), on obtient 5/15 * log2 (5/15).
4. Ensuite, nous prenons notre produit de chaque cas ci-dessus et le additionnons ensemble. Pour cet exemple, 10/15 * log2(10/15) + 5/15 *log2 (5/15).
5. Enfin, nous annulons la somme totale d’en haut, —(10/15 *log2(10/15) + 5/15 *log2(5/15)).

Une fois que nous avons mis les étapes ensemble, nous obtenons ce qui suit:

Notre entropie finale est.918278. Alors, qu’est-ce que cela signifie vraiment?

Théorie de l’information et un peu d’information

Pour aller de l’avant, il sera important de comprendre le concept de bit. En théorie de l’information, un bit est considéré comme un nombre binaire représentant 0 pour aucune information et 1 pour un bit complet d’information. Nous pouvons représenter un peu d’information comme un nombre binaire car il a la valeur (1) ou (0). Supposons qu’il y ait une probabilité égale qu’il pleuve demain (1) ou qu’il ne pleuve pas (0). Si je vous dis qu’il va pleuvoir demain, je vous ai donné une petite information.

On peut aussi considérer l’entropie comme une information. Supposons que nous ayons un dé à six faces chargé qui atterrit toujours sur (3). Chaque fois que nous lançons le dé, nous savons dès le départ que le résultat sera (3). Nous n’obtenons aucune nouvelle information en faisant rouler le dé, donc l’entropie est 0. Par contre, si le dé est loin et que nous roulons un (3), il y avait 1/6 de chance de rouler le (3). Maintenant, nous avons acquis des informations. Ainsi, rouler le dé nous donne un peu d’informations — de quel côté le numéro a atterri.

Pour une plongée plus profonde dans le concept d’un peu d’information, vous pouvez en lire plus ici.

Nous obtenons moins d’un ”bit » d’informations uniquement.918278 – parce qu’il y a plus de (1) s dans le « midwest? Cela signifie que si nous prédisions une nouvelle valeur, nous pourrions deviner que la réponse est (1) et avoir raison plus souvent que tort (car il y a une probabilité de 2/3 que la réponse soit 1). Grâce à ces connaissances préalables, nous gagnons moins qu’un « bit” complet d’informations lorsque nous observons une nouvelle valeur.

Utilisation de l’entropie pour prendre des décisions

Notre objectif est de trouver la (les) meilleure(s) variable(s) / colonne(s) à diviser lors de la construction d’un arbre de décision. Finalement, nous voulons continuer à diviser les variables / colonnes jusqu’à ce que notre colonne cible mixte ne soit plus mélangée.

Par exemple, regardons l’entropie du « midwest? » colonne après avoir divisé notre jeu de données sur le « potato_salad?” colonne.

Ci-dessus, notre jeu de données est divisé en deux sections. Sur le côté gauche, tous ceux qui aiment la salade de pommes de terre. Sur le côté droit, tous ceux qui ne le font pas.Nous remplissons le focus sur le côté gauche qui compte maintenant sept personnes du Midwest et deux personnes qui ne le sont pas.En utilisant la formule pour l’entropie sur la colonne du midwest divisé à gauche, la nouvelle entropie est.764204. C’est génial! Notre objectif est de réduire l’entropie et nous sommes partis de.918278 à.764204. Mais, nous ne pouvons pas nous arrêter là, si nous regardons la colonne de droite, notre entropie a augmenté car il y a une quantité égale de (1) s et (0) s. Ce dont nous avons besoin, c’est d’un moyen de voir comment l’entropie change des deux côtés de la division. La formule pour le gain d’informations le fera. Cela nous donne un nombre pour quantifier le nombre d’informations que nous avons obtenues chaque fois que nous divisons nos données.

Gain d’information

Nous avons précédemment établi que nous voulons des divisions qui abaissent l’entropie de notre colonne cible. Quand nous nous sommes séparés sur « potato_salad? »nous avons vu cette entropie dans le « midwest? » descendit sur le côté gauche. Maintenant, nous devons comprendre l’entropie totale abaissée lorsque nous regardons les deux côtés de la scission. Jetons un coup d’œil au gain d’informations.

Le gain d’information utilisera la formule suivante:

Décomposons ce qui se passe ici.

Nous reviendrons à notre « potato_salad ?” exemple. Les variables de la formule ci-dessus représenteront ce qui suit :

• T=Target, notre « midwest? »column
• A = la variable (colonne) que nous testons, « potato_salad?”
• v = chaque valeur dans A, chaque valeur dans le « potato_salad? »column

1. Tout d’abord, nous allons calculer l’entropie originale pour (T) avant la scission, .918278
2. Ensuite, pour chaque valeur unique (v) de la variable (A), nous calculons le nombre de lignes dans lesquelles (A) prend la valeur (v), et la divisons par le nombre total de lignes. Pour le « potato_salad? »colonne nous obtenons 9/15 pour la valeur unique de (1) et 6/15 pour la valeur unique de (0).
3. Ensuite, on multiplie les résultats par l’entropie des lignes où (A) est (v). Pour la division de gauche (split sur 1 pour « potato_salad? ») nous obtenons 9/15 *.764204. Pour le côté droit de la scission (diviser sur 0 pour « potato_salad? »” nous obtenons 6/15 * 1.
4. Nous ajoutons tous ces produits sous-ensembles ensemble, 9/14*.764204 + 6/15 = .8585224.

5. Nous soustrayons ensuite de l’entropie globale pour obtenir un gain d’information, .918278 -.8585224 = .059754

Notre gain d’information est.059754. Qu’est-ce que ça nous dit ?

Voici une autre explication. Nous trouvons l’entropie de chaque ensemble après la division, en la pondérant par le nombre d’éléments de chaque division, puis en la soustrayant de l’entropie actuelle. Si le résultat est positif, nous avons réduit l’entropie avec notre division. Plus le résultat est élevé, plus nous avons réduit l’entropie.

On se retrouve avec.059754, ce qui signifie que nous gagnons.059754 bits d’informations en fractionnant notre jeu de données sur le « potato_salad? » variable / colonne. Notre gain d’information est faible, mais il reste positif, car nous avons abaissé l’entropie du côté gauche de la scission.

Maintenant, nous devons répéter ce processus pour chaque colonne que nous utilisons. Au lieu de le faire à la main, écrivons du code Python.

Envelopper le tout Avec Python

Maintenant que nous comprenons le gain d’informations, nous avons besoin d’un moyen de répéter ce processus pour trouver la variable / colonne avec le plus grand gain d’informations. Pour ce faire, nous pouvons créer quelques fonctions simples en Python.

Importation des données

Transformons notre table ci-dessus en une trame de données à l’aide de la bibliothèque Python pandas. Nous allons importer des pandas et utiliser la fonction read_csv() pour créer une trame de données nommée « midwest”.

import pandas as pd
midwest = pd.read_csv('midwes.csv')

Une fonction Python pour l’entropie

Pour cette fonction, nous aurons besoin de la bibliothèque NumPy pour utiliser la fonction bincount() et du module math pour utiliser la fonction log().

import numpy
import math

Ensuite, nous définirons notre fonction avec un paramètre. L’argument donné sera la série, la liste ou le tableau NumPy dans lequel nous essayons de calculer l’entropie.

def calc_entropy(column):

Nous devrons trouver le pourcentage de chaque cas dans la colonne. On peut utiliser le numpy.fonction bincount() pour cela. La valeur de retour est un tableau NumPy qui stockera le nombre de chaque valeur unique de la colonne passée en argument.

counts = numpy.bincount(column)

Nous allons stocker les probabilités de chaque valeur unique en divisant le tableau « counts” par la longueur de la colonne.

probabilities = counts / len(column)

On peut alors initialiser une variable nommée « entropie” et la mettre à 0.

entropy = 0

Ensuite, nous pouvons utiliser une « boucle for” pour parcourir chaque probabilité de notre tableau de probabilités et la multiplier par le logarithme base 2 de probabilité en utilisant les mathématiques.fonction log(). Ensuite, ajoutez chaque cas à notre variable d’entropie stockée. * assurez-vous de vérifier que votre probabilité est supérieure à 0 sinon log(0) retournera undefined

for prob in probabilities:
if prob > 0:
endtropy += prob * math.log(prob,2)

Enfin, nous retournerons notre variable d’entropie négée.

return -entropy

Tous ensemble maintenant:

Super! Maintenant, nous pouvons construire une fonction pour calculer le gain d’informations.

Une fonction Python pour le gain d’informations

Nous devrons définir une fonction qui aura trois paramètres, un pour l’ensemble des données, un pour le nom de la colonne sur laquelle nous voulons diviser et un pour le nom de notre colonne cible.

def calc_information_gain(data, split_name, target_name):

Ensuite, nous pouvons utiliser la fonction d’entropie précédente pour calculer l’entropie d’origine de notre colonne cible.

orginal_entropy = calc_entropy(data)

Maintenant, nous devons diviser notre colonne.

* Pour cet exemple, nous n’utiliserons que les variables /colonnes avec deux uniques. Si vous souhaitez diviser une variable / colonne telle que « age”, il existe plusieurs façons de le faire. Une façon est de diviser sur chaque valeur unique. Une autre façon consiste à simplifier le calcul du gain d’informations et à simplifier les fractionnements en ne fractionnant pas pour chaque valeur unique. Au lieu de cela, la médiane est trouvée pour la variable / coumn divisée. Toutes les lignes où la valeur de la variable est inférieure à la médiane iront à la branche gauche, et le reste des lignes ira à la branche droite. Pour calculer le gain d’informations, nous n’aurons qu’à calculer des entropies pour deux sous-ensembles. Nous ne suivrons pas cette méthode, mais une fois la division sur la médiane effectuée, le reste des étapes serait le même que celui décrit ci-dessous.

Puisque les colonnes avec lesquelles nous travaillons n’ont que deux valeurs uniques, nous ferons une division à gauche et une division à droite.

Nous allons commencer par utiliser les pandas.Série.unique() pour nous donner un tableau des valeurs uniques dans la colonne

values = data.unique()

Ensuite, nous créerons une division gauche et droite en utilisant ”values ».

left_split = data == values]
right_split = data == values]

Maintenant, nous pouvons initier une variable à soustraire de notre entropie d’origine.

to_subtract = 0

Ensuite, nous parcourrons chaque sous-ensemble créé par notre division, calculerons la probabilité du sous-ensemble, puis ajouterons le produit de la probabilité et l’entropie de la colonne cible des sous-ensembles.

for subset in :
prob = (subset.shape / data.shape)
to_subtract += prob * calc_entropy(subset)

Enfin, nous pouvons renvoyer la différence de to_subract soustraite de l’entropie d’origine.

return original_entropy - to_subtract

Toute la fonction est ci-dessous.

Une fonction Python pour le Gain d’informations le plus élevé

Notre fonction finale sera celle qui renverra le nom de la variable / colonne avec le gain d’informations le plus élevé.

Comme mentionné précédemment, nous utilisons uniquement les colonnes avec deux valeurs uniques pour cet exemple. Nous stockerons ces noms de colonnes dans une liste à utiliser dans la fonction. Pour en arriver au point, nous allons coder cela en dur pour cet exemple, mais dans un grand ensemble de données, il serait préférable d’écrire du code pour construire cette liste dynamiquement en fonction des critères que nous utilisons pour choisir les colonnes.

columns = 

Enveloppons la dernière étape dans une fonction afin de pouvoir la réutiliser au besoin. Il aura un paramètre, la liste des colonnes pour lesquelles nous voulons trouver le gain d’informations le plus élevé.

def highest_info_gain(columns):

Nous initialiserons un dictionnaire vide pour stocker nos gains d’informations.

information_gains = {}

Et ensuite nous pouvons parcourir la liste des colonnes et stocker le résultat dans notre dictionnaire information_gains.

for col in columns:
information_gain = calc_information_gain(midwest, col, 'midwest?)
information_gains = information_gain

Enfin, nous pouvons retourner la clé de la valeur la plus élevée dans notre dictionnaire.

return max(information_gains, key=information_gains.get)

Tous ensemble maintenant:

Une fois que nous exécutons notre fonction finale

print(highest_info_gain(midwest, columns, 'midwest?'))
//sushi

nous voyons la variable/colonne avec le gain d’information le plus élevé est « sushi?’.

Nous pouvons visualiser une division sur sushi ci-dessous:

Notre division gauche compte deux personnes sur six du Midwest. La division de droite compte huit des neuf personnes du Midwest. Ce fut une division efficace et a réduit notre entropie des deux côtés. Si nous devions continuer, nous utiliserions la récursivité pour continuer à diviser chaque division dans le but de terminer chaque branche avec une entropie de zéro.

Conclusion

Les arbres de décision peuvent être un algorithme d’apprentissage automatique utile pour détecter les interactions non linéaires entre les variables dans les données. Dans cet exemple, nous avons examiné les premières étapes d’un algorithme de classification d’arbre de décision. Nous avons ensuite examiné trois concepts de la théorie de l’information, l’entropie, le bit et le gain d’information. En utilisant ces concepts, nous avons pu construire quelques fonctions en Python pour décider quelles variables / colonnes étaient les plus efficaces pour se diviser. Avec une compréhension ferme de ces concepts, nous pouvons avancer pour construire un arbre de décision.