[PYTHON] Machine Learning: Supervisé - Arbre de décision

Cible

Comprenez l'arbre de décision et essayez-le avec scicit-learn.

théorie

L'arbre de décision est classé en construisant une structure arborescente en définissant des seuils pour les caractéristiques importantes pour la classification.

L'arbre de décision est un modèle de classification hautement sémantiquement interprétable qui vous permet de savoir quelles caractéristiques sont importantes pour la classification et laquelle est classée à quel seuil en visualisant l'arborescence. Il peut également être utilisé pour la régression.

Arbre de décision

Il existe plusieurs types d'algorithmes d'arbre de décision, mais nous suivons ici l'algorithme CART utilisé par scikit-learn.

Concept d'arbre de décision

Dans la structure arborescente, le début de l'arborescence est appelé le nœud racine et la fin de l'arbre est appelée le nœud feuille, comme illustré dans la figure ci-dessous. Dans chaque nœud, celui ci-dessus est appelé le nœud parent et celui ci-dessous est appelé le nœud enfant.

Dans CART, à partir du nœud racine, un seuil est défini et divisé par la quantité de caractéristiques qui maximise le gain d'informations. Divisez ceci jusqu'à ce que les nœuds feuilles soient purs, c'est-à-dire que toutes les catégories contenues dans les nœuds feuilles sont les mêmes.

Cependant, diviser les nœuds feuilles jusqu'à ce qu'ils soient purs entraînera un surapprentissage, qui peut être atténué par l'élagage.

Apprendre l'arbre de décision

L'apprentissage de l'arbre de décision se fait en maximisant le gain d'information $ IG $ dans la formule ci-dessous.

IG(D_{parent}, f) = I(D_{parent}) - \frac{N_{left}}{N_{parent}} I(D_{left}) - \frac{N_{right}}{N_{parent}} I(D_{right})

Ici, $ f $ est le montant de la caractéristique à diviser, $ D_ {parent} $ sont les données contenues dans le nœud parent, $ D_ {gauche}, D_ {droite} $ sont les données des nœuds enfants gauche et droit, $ N_ { parent} $ est le nombre de données dans le nœud parent, $ N_ {gauche}, N_ {droite} $ est le nombre de données dans les nœuds enfants gauche et droit, et $ I $ est l'impureté décrite ci-dessous.

Au cours de l'apprentissage, plus la pureté des nœuds enfants gauche et droit de chaque entité est petite, plus le gain d'informations est important, et l'entité sera divisée en fonction du seuil défini.

Les trois indicateurs suivants sont des indicateurs typiques utilisés pour l'évaluation de la pureté. Ici, $ C_i (i = 1, 2, .., K) $ est la catégorie $ K $, $ t $ est le nœud, et $ P (C_i | t) $ est les données de cette catégorie dans un nœud. Représente la probabilité d'être

L'erreur de classification $ I_E $ n'est pas sensible aux changements dans le nœud et est utilisée pour l'élagage des arbres comme décrit ci-dessous.

I_E = 1 - \max_i P(C_i | t)

L'entropie $ I_H $ vaut 0 lorsque toutes les données contenues dans le nœud appartiennent à la même catégorie.

I_H = -\sum^K_{i=1} P(C_i | t) \ln P(C_i | t)

Gini $ I_G $ peut être interprété comme un indicateur qui minimise la probabilité d'erreur de classification, qui est de 0 lorsque toutes les données contenues dans le nœud appartiennent à la même catégorie, similaire à l'entropie.

I_G = 1 - \sum^K_{i=1} P^2 (C_i | t)

Chaque fonction est comme indiqué ci-dessous, et gini est la valeur par défaut dans scikit-learn.

Déterminer la taille des arbres

Pendant l'entraînement, l'arbre est approfondi jusqu'à ce que les nœuds feuilles soient purs, mais s'il est laissé tel quel, il sera surappris, donc l'élagage est effectué pour atténuer cela.

Définissez le taux d'erreur de réaffectation lors de la saisie à nouveau des données d'entraînement comme critère d'évaluation pour l'élagage des arbres. Le taux d'erreur de réaffectation $ R (t) $ en un nœud $ t $ est exprimé par l'équation suivante en utilisant l'erreur de classification $ I_E $ et la probabilité marginale $ P (t) $ du nœud $ t $.

R(t) = \left( 1 - \max_i P(C_i | t) \right) \times P(t) \\
P(t) = \frac{N(t)}{N}

Où $ N (t) $ représente le nombre de données contenues dans le nœud $ t $ et $ N $ représente le nombre total de données d'apprentissage.

L'élagage des arbres supprime les branches des arbres en fonction de ce taux d'erreur de réaffectation. Avec scikit-learn, l'argument max_leaf_nodes peut être utilisé pour élaguer et sécuriser le nombre requis de nœuds.

la mise en oeuvre

Environnement d'exécution

Matériel

・ Processeur Intel (R) Core (TM) i7-6700K 4,00 GHz

Logiciel

・ Windows 10 Professionnel 1909 ・ Python 3.6.6 ・ Matplotlib 3.3.1 ・ Numpy 1.19.2 ・ Scikit-learn 0.23.2

Programme à exécuter

Le programme implémenté est publié sur GitHub.

decision_tree_clf.py

decision_tree_reg.py

résultat

Classification par arbre de décision

J'ai appliqué l'arbre de décision à l'ensemble de données sur le cancer du sein que j'utilise jusqu'à présent. Dans l'arbre de décision, le seuil est déterminé pour chaque montant de caractéristique, il n'est donc pas nécessaire de standardiser le montant de caractéristique comme prétraitement.

Accuracy 97.37%
Precision, Positive predictive value(PPV) 97.06%
Recall, Sensitivity, True positive rate(TPR) 98.51%
Specificity, True negative rate(TNR) 95.74%
Negative predictive value(NPV) 97.83%
F-Score 97.78%

Visualisation et interprétabilité des arbres de décision

scikit-learn fournit une fonction plot_tree qui visualise l'arbre de décision, ce qui facilite la visualisation de l'arborescence du modèle entraîné.

Vous pouvez également afficher les critères de jugement au niveau de chaque nœud du modèle entraîné sur la ligne de commande comme suit.

The binary tree structure has 9 nodes and has the following tree structure:
node=0 test node: go to node 1 if X[:, 27] <= 0.1423499956727028 else to node 2.
	node=1 test node: go to node 3 if X[:, 23] <= 957.4500122070312 else to node 4.
	node=2 test node: go to node 5 if X[:, 23] <= 729.5499877929688 else to node 6.
		node=3 leaf node.
		node=4 leaf node.
		node=5 test node: go to node 7 if X[:, 4] <= 0.10830000042915344 else to node 8.
		node=6 leaf node.
			node=7 leaf node.
			node=8 leaf node.

Rules used to predict sample 0: 
decision id node 0 : (X_test[0, 27](= 0.2051) > 0.1423499956727028)
decision id node 2 : (X_test[0, 23](= 844.4) > 729.5499877929688)

The following samples [0, 1] share the node [0] in the tree
It is 11.11%% of all nodes.

La figure ci-dessous montre les limites discriminantes lors de l'exécution de la multiclassification sur un ensemble de données d'iris.

Retour par arbre de décision

Pour les données du problème de régression, un nombre aléatoire a été ajouté à l'onde sinusoïdale. On peut voir que l'approfondissement de l'arbre améliore l'expressivité.

La figure ci-dessous est un exemple appliqué à un problème de régression multi-sorties.

référence

1.10. Decision Tree

1. Yuzo Hirai. «Première reconnaissance de formes», Morikita Publishing, 2012.