Implémentation de l'algorithme de classification de l'arbre de décision en Python

L'article ci-dessous partage le code spécifique à Python pour l'algorithme de classification par arbre de décision, à titre d'exemple, voici le contenu détaillé :

1、概述

Arbre de décision (decision tree) - est un algorithme de classification largement utilisé.

Compared to the Bayesian algorithm, the advantage of the decision tree is that the construction process does not require any domain knowledge or parameter setting

Dans l'application pratique, pour la découverte de connaissances exploratoires, l'arbre de décision est plus applicable.

2、algorithmes

En termes simples, l'idée de classification par arbre de décision est similaire à la recherche d'un partenaire. Imaginez que la mère d'une jeune fille veut lui présenter un ami, et voici la conversation suivante :

　　　　　 Fille : À quel âge est-elle ?

　　　　　 Mère :26.

　　　　　 Fille : Elle est-elle belle ou pas ?

　　　　　 Mère : Elle est assez belle.

　　　　　 Fille : Son salaire est-il élevé ?

　　　　　 Mère : Pas très élevé, une situation moyenne.

　　　　　 Fille : Elle est fonctionnaire, non ?

　　　　　 Mère : Oui, elle travaille à l'administration fiscale.

　　　　　 Fille : Bien, je vais l'aller voir.　

Le processus de décision de cette fille est un processus de décision d'arbre de classification typique.

Substance :Classer les hommes en deux catégories : voir ou ne pas voir en fonction de l'âge, de l'apparence, du revenu et de ce qu'ils sont fonctionnaires

Supposons que les exigences de la fille pour un homme soient :30 ans et moins, apparence moyenne ou supérieure et haut revenu ou fonctionnaire de revenu moyen ou supérieur, alors cette fille peut représenter la logique de décision dans l'image suivante

L'image complète exprime la stratégie de décision de la fille pour décider de voir ou non un partenaire de rendez-vous, dans laquelle :

◊ les nœuds verts représentent les conditions de jugement

◊ les nœuds orange représentent le résultat de la décision

◊ les flèches indiquent le chemin de décision sous différentes conditions d'une condition de jugement

Les flèches rouges dans la figure indiquent le processus de décision de la fille dans l'exemple précédent.　

Cette image peut être considérée comme un arbre de décision, disons qu'elle peut être considérée comme un arbre de décision car les conditions de jugement dans l'image ne sont pas quantifiées, comme les revenus élevés, moyens et bas, etc., et ne peuvent pas être considérés comme un arbre de décision au sens strict. Si toutes les conditions sont quantifiées, cela deviendra un arbre de décision réel.　

La clé de l'algorithme de classification de l'arbre de décision consiste à construire un arbre de décision optimal à partir de "données préalables" pour prédire la catégorie des données inconnues　

Arbre de décision : c'est une structure en arbre (peut être un arbre binaire ou non binaire). Chaque noeud non feuille représente un test sur une propriété de caractéristique, chaque branche représente la sortie de cette propriété dans un domaine de valeurs, et chaque noeud feuille contient une catégorie. Le processus de décision à l'aide d'un arbre de décision consiste à commencer par le noeud racine, à tester la propriété de caractéristique correspondante de l'élément à classifier, à choisir la branche de sortie en fonction de sa valeur, jusqu'à atteindre le noeud feuille, et à utiliser la catégorie stockée dans le noeud feuille comme résultat de décision.

3、construction d'arbre de décision

Si vous avez les données d'échantillons suivantes pour juger de la qualité des pommes :

Échantillon Rouge Grand Bonne pomme

0　　　　　　　 　1　　　　　 1　　　　　　　　 1

1　　　　　　　 　1　　　　　 0　　　　　　　　 1

2　　　　　　　 　0　　　　　 1　　　　　　　　 0

3　　　　　　　 　0 0 0

Les échantillons ont2Un attribut, A0 représente si c'est une pomme rouge. A1Représente si c'est une grande pomme. Si vous devez utiliser ce jeu de données pour construire un arbre de décision automatique pour juger de la qualité des pommes.

En raison des données de cet exemple, il n'y a que2Un attribut, par conséquent, nous pouvons énumérer tous les arbres de décision possibles, c'est-à-dire2Arbres, comme indiqué dans la figure suivante :

Il est évident que l'arbre de décision qui utilise d'abord A0 (rouge) à gauche est supérieur à celui qui utilise A à droite.1(Taille) faire des divisions en fonction de l'arbre de décision.

Bien sûr, c'est une cognition intuitive. Mais l'intuition n'est évidemment pas adaptée à la mise en œuvre du programme, donc il est nécessaire d'avoir une méthode d'évaluation quantitative pour évaluer les performances de ces deux arbres.

La méthode d'évaluation quantitative utilisée pour évaluer l'arbre de décision estCalculer l'augmentation de l'entropie pour chaque situation de division:

Si la division des données après un attribut sélectionné réduit l'entropie le plus, alors cet attribut de division est le choix optimal　

Choix de la division des attributs (c'est-à-dire la construction d'un arbre de décision) :

En termes simples, l'entropie est l'importance de "désordre" et "mélangé".

Pour comprendre par le calcul :

1、l'entropie des données d'échantillons originaux :

Nombre total d'exemples :4

Bonne pomme :2

Mauvais pomme :2

Entropie : -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1

L'entropie est de1Représente l'état le plus désorganisé et le plus désordonné actuel.

2、calcul de l'augmentation de l'entropie de l'information de la division des deux arbres de décision

arbre1faire la division A0 en premier, les calculs de l'entropie de l'information des sous-nœuds de chaque division sont les suivants :

0,1Les nœuds feuilles ont2exemples positifs, 0 exemples négatifs. L'entropie est : e1 = -(2/2 * log(2/2) + 0/2 * log(0/2)) = 0.

2,3Les nœuds feuilles ont 0 exemples positifs,2exemples négatifs. L'entropie est : e2 = -(0/2 * log(0/2) + 2/2 * log(2/2)) = 0.

Par conséquent, l'entropie de l'information après la division A0 est la pondération pondérée de la proportion de l'entropie de l'information de chaque sous-nœud : E = e1*2/4 + e2*2/4 = 0.

L'augmentation de l'entropie de l'information de la division G(S, A0) = S - E = 1 - 0 = 1.

En fait, les nœuds feuilles de l'arbre de décision représentent déjà tous les mêmes catégories, donc l'entropie est certainement 0.　

arbre2Choisissez d'abord A1faire la division, les calculs de l'entropie de l'information des sous-nœuds de chaque division sont les suivants :

0,2les sous-nœuds ont1exemples positifs,1exemples négatifs. L'entropie est : e1 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1.

1,3les sous-nœuds ont1exemples positifs,1exemples négatifs. L'entropie est : e2 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1.

Par conséquent, choisissez A1L'entropie de l'information après la division est la pondération pondérée de la proportion de l'entropie de l'information de chaque sous-nœud : E = e1*2/4 + e2*2/4 = 1。C'est-à-dire que de diviser ou non ne fait pas de différence !

Choisir A1Calculer l'augmentation de l'entropie de l'information de la division G(S, A1）=S - E = 1 - 1 = 0.　

Par conséquent, avant chaque division, nous devons simplement calculer la division avec l'augmentation de l'entropie de l'information la plus grande.

L'augmentation de l'entropie de l'information de la division A0 en premier est1>Faire la division A1l'augmentation de l'entropie de l'information lors de la division, donc faire la division A0 en premier est le choix optimal !!!!

4、principe de conception de l'algorithme

Après la division des attributs de décision, le degré d'ordre des données devient de plus en plus faible, c'est-à-dire que l'entropie de l'information devient de plus en plus petite　

5、implémentation de l'algorithme

Classifiez les attributs des données

Comparez l'augmentation de l'entropie de l'information des données divisées selon une propriété spécifique, choisissez la propriété avec l'augmentation de l'entropie de l'information la plus grande comme premier critère de division, puis continuez à choisir le deuxième attribut, et ainsi de suite

Voici la totalité du contenu de cet article, j'espère qu'il vous aidera dans vos études, et j'espère que vous soutiendrez également le tutoriel Yell.

Déclaration : le contenu de cet article est issu d'Internet, les droits d'auteur appartiennent aux propriétaires respectifs, le contenu est contribué et téléchargé spontanément par les utilisateurs d'Internet, ce site n'appartient pas à la propriété, n'a pas été traité par l'éditeur humain et n'assume aucune responsabilité juridique. Si vous trouvez du contenu suspect de violation de droits d'auteur, vous êtes invité à envoyer un email à : notice#oldtoolbag.com (veuillez remplacer # par @ lors de l'envoi d'un email pour signaler une violation, et fournir des preuves pertinentes. Une fois confirmée, ce site supprimera immédiatement le contenu suspect de violation de droits d'auteur.)