Exemples d'algorithmes d'arbre de décision dans l'exploration de données

decision tree algorithm examples data mining

Ce didacticiel détaillé explique tout sur l'algorithme d'arbre de décision dans l'exploration de données. Vous découvrirez les exemples d'arbres de décision, l'algorithme et la classification:

Nous avons jeté un coup d'œil à quelques Exemples d'exploration de données dans notre précédent tutoriel en Série de formation gratuite sur l'exploration de données .

L'exploration d'arbre de décision est un type de technique d'exploration de données utilisé pour créer des modèles de classification. Il construit des modèles de classification sous la forme d'une structure arborescente, tout comme son nom. Ce type d'exploitation minière appartient à l'apprentissage supervisé en classe.

Dans l'apprentissage supervisé, le résultat cible est déjà connu. Les arbres de décision peuvent être utilisés pour les données catégorielles et numériques. Les données catégorielles représentent le sexe, l'état matrimonial, etc. tandis que les données numériques représentent l'âge, la température, etc.

char en entier c ++

Un exemple d'arbre de décision avec l'ensemble de données est présenté ci-dessous.

(image la source )

Ce que vous apprendrez:

• À quoi sert un arbre de décision?
• Analyse de classification
• Analyse de régression
• Comment fonctionne un arbre de décision?
• Algorithme d'induction d'arbre de décision
• Induction de l'arbre de décision
• CHARIOT
• Induction d'arbre de décision pour l'apprentissage automatique: ID3
• Qu'est-ce que le fractionnement binaire récursif gourmand?
• Comment sélectionner des attributs pour créer une arborescence?
  • # 1) Gain d'information
  • # 2) Rapport de gain
  • # 3) Indice de Gini
• Surajustement dans les arbres de décision
• Qu'est-ce que l'élagage des arbres?
• Qu'est-ce que la modélisation prédictive?
• Avantages de la classification par arbre de décision
• Inconvénients de la classification par arbre de décision
• Conclusion
• lecture recommandée

À quoi sert un arbre de décision?

L'arbre de décision est utilisé pour construire des modèles de classification et de régression. Il est utilisé pour créer des modèles de données qui prédiront les étiquettes de classe ou les valeurs pour le processus de prise de décision. Les modèles sont construits à partir du jeu de données de formation fourni au système (apprentissage supervisé).

En utilisant un arbre de décision, nous pouvons visualiser les décisions qui le rendent facile à comprendre et c'est donc une technique d'exploration de données populaire.

Analyse de classification

La classification des données est une forme d'analyse qui construit un modèle qui décrit des variables de classe importantes.Par exemple, un modèle conçu pour classer les demandes de prêts bancaires comme sûres ou risquées. Les méthodes de classification sont utilisées dans l'apprentissage automatique et la reconnaissance de formes.

L'application de la classification comprend la détection de fraude, le diagnostic médical, le marketing cible, etc. La sortie du problème de classification est considérée comme «Mode» de toutes les valeurs observées du nœud terminal.

Un processus en deux étapes est suivi pour construire un modèle de classification.

1. Dans la première étape, c'est-à-dire l'apprentissage: un modèle de classification basé sur les données de formation est construit.
2. Dans la deuxième étape, c'est-à-dire la classification, la précision du modèle est vérifiée, puis le modèle est utilisé pour classer les nouvelles données. Les étiquettes de classe présentées ici se présentent sous la forme de valeurs discrètes telles que «oui» ou «non», «sûr» ou «risqué».

L'approche générale pour la construction de modèles de classification est donnée ci-dessous:

(image la source )

Analyse de régression

L'analyse de régression est utilisée pour la prédiction des attributs numériques.

Les attributs numériques sont également appelés valeurs continues. Un modèle conçu pour prédire les valeurs continues au lieu d'étiquettes de classe est appelé le modèle de régression. Le résultat de l'analyse de régression est la «moyenne» de toutes les valeurs observées du nœud.

Comment fonctionne un arbre de décision?

Un arbre de décision est un algorithme d'apprentissage supervisé qui fonctionne à la fois pour des variables discrètes et continues. Il divise l'ensemble de données en sous-ensembles sur la base de l'attribut le plus significatif de l'ensemble de données. La manière dont l'arbre de décision identifie cet attribut et comment cette division est effectuée est décidée par les algorithmes.

Le prédicteur le plus significatif est désigné comme le nœud racine, la division est effectuée pour former des sous-nœuds appelés nœuds de décision, et les nœuds qui ne se séparent pas davantage sont des nœuds terminaux ou feuilles.

Dans l'arbre de décision, l'ensemble de données est divisé en régions homogènes et sans chevauchement. Il suit une approche descendante car la région supérieure présente toutes les observations à un seul endroit qui se divise en deux ou plusieurs branches qui se divisent davantage. Cette approche est également appelée approche gourmande car il ne considère que le nœud actuel entre le travaillé sans se concentrer sur les futurs nœuds.

Les algorithmes d'arbre de décision continueront de fonctionner jusqu'à ce qu'un critère d'arrêt tel que le nombre minimum d'observations, etc. soit atteint.

Une fois qu'un arbre de décision est construit, de nombreux nœuds peuvent représenter des valeurs aberrantes ou des données bruyantes. La méthode d'élagage des arbres est appliquée pour supprimer les données indésirables. Ceci, à son tour, améliore la précision du modèle de classification.

Pour trouver la précision du modèle, un ensemble de test composé de tuples de test et d'étiquettes de classe est utilisé. Les pourcentages des tuples de l'ensemble de test sont correctement classés par le modèle pour identifier la précision du modèle. Si le modèle s'avère précis, il est utilisé pour classer les tuples de données pour lesquels les étiquettes de classe ne sont pas connues.

Certains des algorithmes d'arbre de décision incluent l'algorithme de Hunt, ID3, CD4.5 et CART.

Exemple de création d'un arbre de décision

(L'exemple est tiré de Data Mining Concepts: Han et Kimber)

# 1) Étape d'apprentissage: Les données d'apprentissage sont introduites dans le système pour être analysées par un algorithme de classification. Dans cet exemple, l'étiquette de classe est l'attribut, c'est-à-dire «décision de prêt». Le modèle construit à partir de ces données d'apprentissage est représenté sous la forme de règles de décision.

# 2) Classification: L'ensemble de données de test est envoyé au modèle pour vérifier l'exactitude de la règle de classification. Si le modèle donne des résultats acceptables, il est appliqué à un nouvel ensemble de données avec des variables de classe inconnues.

Algorithme d'induction d'arbre de décision

Induction de l'arbre de décision

L'induction d'arbre de décision est la méthode d'apprentissage des arbres de décision à partir de l'ensemble d'apprentissage. L'ensemble d'apprentissage se compose d'attributs et d'étiquettes de classe. Les applications de l'induction d'arbre de décision comprennent l'astronomie, l'analyse financière, le diagnostic médical, la fabrication et la production.

Un arbre de décision est une structure en forme d'arborescence d'organigramme créée à partir de tuples d'ensemble d'apprentissage. L'ensemble de données est décomposé en sous-ensembles plus petits et se présente sous la forme de nœuds d'un arbre. La structure arborescente a un nœud racine, des nœuds internes ou des nœuds de décision, un nœud feuille et des branches.

Le nœud racine est le nœud le plus élevé. Il représente le meilleur attribut sélectionné pour la classification. Les nœuds internes des nœuds de décision représentent un test d'un attribut du nœud feuille de l'ensemble de données ou du nœud terminal qui représente l'étiquette de classification ou de décision. Les branches montrent le résultat du test effectué.

Certains arbres de décision n'ont nœuds binaires , cela signifie exactement deux branches d'un nœud, tandis que certains arbres de décision ne sont pas binaires.

L'image ci-dessous montre l'arbre de décision pour l'ensemble de données Titanic pour prédire si le passager survivra ou non.

(image la source )

CHARIOT

Le modèle CART, c'est-à-dire les modèles de classification et de régression, est un algorithme d'arbre de décision pour la construction de modèles. Le modèle d'arbre de décision où les valeurs cibles ont une nature discrète est appelé modèles de classification.

Une valeur discrète est un ensemble fini ou infini de valeurs, Par exemple, âge, taille, etc. Les modèles dans lesquels les valeurs cibles sont représentées par des valeurs continues sont généralement des nombres appelés modèles de régression. Les variables continues sont des variables à virgule flottante. Ces deux modèles ensemble sont appelés CART.

CART utilise l'indice de Gini comme matrice de classification.

Induction d'arbre de décision pour l'apprentissage automatique: ID3

À la fin des années 1970 et au début des années 1980, J. Ross Quinlan était un chercheur qui a construit un algorithme d'arbre de décision pour l'apprentissage automatique. Cet algorithme est appelé ID3, dichotomiseur itératif . Cet algorithme était une extension des systèmes d'apprentissage de concepts décrits par E.B Hunt, J et Marin.

ID3 est devenu plus tard connu sous le nom de C4.5. ID3 et C4.5 suivent une approche descendante gloutonne pour la construction d'arbres de décision. L'algorithme commence par un ensemble de données d'entraînement avec des étiquettes de classe qui sont réparties en sous-ensembles plus petits au fur et à mesure de la construction de l'arborescence.

#1) Au départ, il y a trois paramètres, à savoir liste d'attributs, méthode de sélection d'attributs et partition de données . La liste d'attributs décrit les attributs des tuples de l'ensemble d'apprentissage.

#deux) La méthode de sélection d'attribut décrit la méthode de sélection du meilleur attribut pour la discrimination entre les tuples. Les méthodes utilisées pour la sélection d'attributs peuvent être le gain d'information ou l'indice de Gini.

# 3) La structure de l'arbre (binaire ou non binaire) est décidée par la méthode de sélection d'attribut.

# 4) Lors de la construction d'un arbre de décision, il commence comme un nœud unique représentant les tuples.

# 5) Si les tuples du nœud racine représentent différentes étiquettes de classe, il appelle une méthode de sélection d'attribut pour diviser ou partitionner les tuples. L'étape conduira à la formation de branches et de nœuds de décision.

# 6) La méthode de fractionnement déterminera quel attribut doit être sélectionné pour partitionner les tuples de données. Il détermine également les branches à développer à partir du nœud en fonction du résultat du test. Le motif principal des critères de division est que la partition à chaque branche de l'arbre de décision doit représenter la même étiquette de classe.

Un exemple d'attribut de fractionnement est présenté ci-dessous:

une. Le portionnement ci-dessus a une valeur discrète.

b. Le portionnement ci-dessus est pour une valeur continue.

# 7) Les étapes de partitionnement ci-dessus sont suivies de manière récursive pour former un arbre de décision pour les tuples d'ensemble de données d'apprentissage.

# 8) Le partitionnement s'arrête uniquement lorsque toutes les partitions sont faites ou lorsque les tuples restants ne peuvent plus être partitionnés.

# 9) La complexité de l'algorithme est décrite par n * | D | * journal | D | où n est le nombre d'attributs dans l'ensemble de données d'apprentissage D et | D | est le nombre de tuples.

Qu'est-ce que le fractionnement binaire récursif gourmand?

Dans la méthode de fractionnement binaire, les tuples sont fractionnés et chaque fonction de coût fractionné est calculée. La répartition des coûts la plus basse est sélectionnée. La méthode de division est binaire qui est formée de 2 branches. Il est de nature récursive car la même méthode (calcul du coût) est utilisée pour diviser les autres tuples de l'ensemble de données.

Cet algorithme est appelé aussi gourmand car il se concentre uniquement sur le nœud actuel. Il se concentre sur la réduction de son coût, tandis que les autres nœuds sont ignorés.

Comment sélectionner des attributs pour créer une arborescence?

Les mesures de sélection d'attributs sont également appelées règles de fractionnement pour décider de la manière dont les tuples vont être fractionnés. Les critères de fractionnement sont utilisés pour partitionner au mieux l'ensemble de données. Ces mesures fournissent un classement des attributs de partitionnement des tuples d'apprentissage.

Les méthodes les plus courantes de sélection de l'attribut sont le gain d'information, l'indice de Gini.

# 1) Gain d'information

Cette méthode est la principale méthode utilisée pour créer des arbres de décision. Cela réduit les informations requises pour classer les tuples. Cela réduit le nombre de tests nécessaires pour classer le tuple donné. L'attribut avec le gain d'information le plus élevé est sélectionné.

Les informations d'origine nécessaires à la classification d'un tuple dans l'ensemble de données D sont données par:

Où p est la probabilité que le tuple appartienne à la classe C. Les informations sont codées en bits, par conséquent, le journal à la base 2 est utilisé. E (s) représente la quantité moyenne d'informations nécessaires pour connaître le libellé de classe de l'ensemble de données D. Ce gain d'informations est également appelé Entropie .

jointure interne jointure externe jointure gauche jointure droite

Les informations nécessaires au classement exact après le portionnement sont données par la formule:

Où P (c) est le poids de la partition. Ces informations représentent les informations nécessaires pour classer l'ensemble de données D sur le portionnement par X.

Le gain d'informations est la différence entre les informations d'origine et attendues qui sont nécessaires pour classer les tuples de l'ensemble de données D.

Le gain est la réduction des informations qui est nécessaire en connaissant la valeur de X. L'attribut avec le gain d'information le plus élevé est choisi comme «meilleur».

# 2) Rapport de gain

Le gain d'informations peut parfois entraîner des portions inutiles pour la classification. Cependant, le rapport de gain divise l'ensemble de données d'apprentissage en partitions et considère le nombre de tuples du résultat par rapport au total des tuples. L'attribut avec le rapport de gain maximum est utilisé comme attribut de division.

# 3) Indice de Gini

L'indice Gini est calculé pour les variables binaires uniquement. Il mesure l'impureté dans les tuples de formation de l'ensemble de données D, comme

P est la probabilité que le tuple appartienne à la classe C.L'indice de Gini qui est calculé pour le jeu de données divisé binaire D par l'attribut A est donné par:

Où n est la nième partition de l'ensemble de données D.

La réduction d'impureté est donnée par la différence de l'indice de Gini du jeu de données d'origine D et de l'indice de Gini après partition par l'attribut A.

La réduction maximale des impuretés ou l'indice de Gini max est sélectionné comme le meilleur attribut pour la division.

Surajustement dans les arbres de décision

Le surajustement se produit lorsqu'un arbre de décision essaie d'être aussi parfait que possible en augmentant la profondeur des tests et réduit ainsi l'erreur. Cela entraîne des arbres très complexes et conduit à un surajustement.

Le surajustement réduit la nature prédictive de l'arbre de décision. Les approches pour éviter le surajustement des arbres comprennent la pré-taille et la post-taille.

Qu'est-ce que l'élagage des arbres?

L'élagage est la méthode pour supprimer les branches inutilisées de l'arbre de décision. Certaines branches de l'arbre de décision peuvent représenter des valeurs aberrantes ou des données bruyantes.

L'élagage des arbres est la méthode pour réduire les branches indésirables de l'arbre. Cela réduira la complexité de l'arbre et aidera à une analyse prédictive efficace. Il réduit le surajustement en supprimant les branches sans importance des arbres.

Il existe deux façons d'élaguer l'arbre:

# 1) Pré-taille : Dans cette approche, la construction de l'arbre de décision est arrêtée prématurément. Cela signifie qu'il est décidé de ne plus partitionner les branches. Le dernier nœud construit devient le nœud feuille et ce nœud feuille peut contenir la classe la plus fréquente parmi les tuples.

Les mesures de sélection d'attributs sont utilisées pour connaître la pondération de la répartition. Des valeurs de seuil sont prescrites pour décider quelles divisions sont considérées comme utiles. Si le fractionnement du nœud entraîne une division en tombant en dessous du seuil, le processus est interrompu.

# 2) Post-élagage : Cette méthode supprime les branches aberrantes d'un arbre complètement développé. Les branches indésirables sont supprimées et remplacées par un nœud feuille indiquant l'étiquette de classe la plus fréquente. Cette technique nécessite plus de calculs que le pré-élagage, cependant, elle est plus fiable.

Les arbres élagués sont plus précis et compacts que les arbres non élagués, mais ils présentent un inconvénient de réplication et de répétition.

La répétition se produit lorsque le même attribut est testé encore et encore le long d'une branche d'un arbre. Réplication se produit lorsque les sous-arbres dupliqués sont présents dans l'arborescence. Ces problèmes peuvent être résolus par des fractionnements multivariés.

L'image ci-dessous montre un arbre non élagué et élagué.

Exemple d'algorithme d'arbre de décision

Exemple La source

Construire un arbre de décision

Prenons un exemple de l'ensemble de données météorologiques des 10 derniers jours avec les attributs Outlook, température, vent et humidité. La variable de résultat jouera au cricket ou non. Nous utiliserons l'algorithme ID3 pour construire l'arbre de décision.

syntaxe python vs c ++

Étape 1: La première étape sera de créer un nœud racine.

Étape 2: Si tous les résultats sont oui, alors le nœud feuille «oui» sera retourné, sinon le nœud feuille «non» sera retourné.

Étape 3: Trouvez l'entropie de toutes les observations et l'entropie avec l'attribut «x» qui est E (S) et E (S, x).

Étape 4: Découvrez le gain d'informations et sélectionnez l'attribut avec un gain d'informations élevé.

Étape 5: Répétez les étapes ci-dessus jusqu'à ce que tous les attributs soient couverts.

Calcul de l'entropie:

Oui Non

9 5

Si l'entropie est nulle, cela signifie que tous les membres appartiennent à la même classe et si l'entropie est un, cela signifie que la moitié des tuples appartiennent à une classe et l'un d'entre eux appartient à une autre classe. 0,94 signifie une distribution équitable.

Trouvez l'attribut de gain d'information qui donne un gain d'information maximal.

Par exemple «Vent», il prend deux valeurs: Fort et Faible, donc x = {Fort, Faible}.

Découvrez H (x), P (x) pour x = faible et x = fort. H (S) est déjà calculé ci-dessus.

Faible = 8

Fort = 8

Pour le vent «faible», 6 d'entre eux disent «Oui» pour jouer au cricket et 2 d'entre eux disent «Non». Donc l'entropie sera:

Pour le vent «fort», 3 ont dit «non» pour jouer au cricket et 3 ont dit «oui».

Cela montre un hasard parfait car la moitié des éléments appartiennent à une classe et la moitié restante appartient à d'autres.

Calculez le gain d'information,

De même, le gain d'informations pour d'autres attributs est:

L'attribut Outlook a le gain d'information le plus élevé de 0,246, il est donc choisi comme racine.

Couvert a 3 valeurs: Ensoleillé, Couvert et Pluie. Couvert avec le cricket de jeu est toujours «Oui». Donc, il se termine par un nœud feuille, «oui». Pour les autres valeurs «Sunny» et «Rain».

Le tableau pour Outlook comme «Ensoleillé» sera:

L'entropie pour «Outlook» «Sunny» est:

Le gain d'information pour les attributs par rapport à Sunny est:

Le gain d'information pour l'humidité est le plus élevé, il est donc choisi comme nœud suivant. De même, l'entropie est calculée pour la pluie. Le vent donne le gain d'information le plus élevé .

L'arbre de décision ressemblerait à ci-dessous:

Qu'est-ce que la modélisation prédictive?

Les modèles de classification peuvent être utilisés pour prédire les résultats d'un ensemble inconnu d'attributs.

Lorsqu'un ensemble de données avec des étiquettes de classe inconnues est introduit dans le modèle, il lui attribuera automatiquement l'étiquette de classe. Cette méthode d'application de la probabilité pour prédire les résultats est appelée modélisation prédictive.

Avantages de la classification par arbre de décision

Vous trouverez ci-dessous les divers avantages de la classification par arbre décisionnel:

1. La classification de l'arbre de décision ne nécessite aucune connaissance du domaine, par conséquent, elle est appropriée pour le processus de découverte de connaissances.
2. La représentation des données sous la forme de l'arbre est facilement comprise par l'homme et elle est intuitive.
3. Il peut gérer des données multidimensionnelles.
4. C'est un processus rapide avec une grande précision.

Inconvénients de la classification par arbre de décision

Vous trouverez ci-dessous les divers inconvénients de la classification par arbre décisionnel:

1. Parfois, les arbres de décision deviennent très complexes et on les appelle des arbres sur-équipés.
2. L'algorithme d'arbre de décision peut ne pas être une solution optimale.
3. Les arbres de décision peuvent renvoyer une solution biaisée si une étiquette de classe la domine.

Conclusion

Les arbres de décision sont des techniques d'exploration de données pour la classification et l'analyse de régression.

Cette technique couvre maintenant de nombreux domaines comme le diagnostic médical, le marketing ciblé, etc. Ces arbres sont construits en suivant un algorithme tel que ID3, CART. Ces algorithmes trouvent différentes façons de diviser les données en partitions.

C'est la technique d'apprentissage supervisé la plus connue qui est utilisée dans l'apprentissage automatique et l'analyse de modèles. Les arbres de décision prédisent les valeurs de la variable cible en construisant des modèles grâce à l'apprentissage à partir de l'ensemble d'apprentissage fourni au système.

Nous espérons que vous avez tout appris sur Decision Tree Mining grâce à ce didacticiel informatif !!

Tutoriel PREV | Tutoriel SUIVANT

lecture recommandée

• Exemples d'exploration de données: applications les plus courantes de l'exploration de données 2021
• Techniques d'exploration de données: algorithmes, méthodes et principaux outils d'exploration de données
• Exploration de données: processus, techniques et problèmes majeurs dans l'analyse des données
• Arborescence B et structure de données d'arbre B + en C ++
• Structure de données d'arbre binaire en C ++
• Processus d'exploration de données: modèles, étapes de processus et défis impliqués
• Arborescence AVL et structure de données de tas en C ++
• Exploration de données Vs Machine Learning Vs Intelligence Artificielle Vs Deep Learning