Créer un arbre de décision à partir de 0 avec Python (1. Présentation)

Qu'est-ce qu'un arbre de décision?

Exemple d'arbre de décision

Par exemple, si vous disposez des données suivantes: Lorsque le temps, la température, l'humidité et le vent sont les suivants, le jour où vous êtes allé au golf est marqué par 〇 et le jour où vous n'y êtes pas allé est marqué par x. Supposons que vous ayez 14 de ces données.

D'après ces données, quand vas-tu au golf? Celle décrite comme une règle de structure arborescente comme indiqué ci-dessous est appelée arbre de décision ou arbre de décision.

Par exemple, si vous regardez cet arbre de décision depuis le début, vérifiez d'abord la météo, puis vérifiez son humidité si elle va bien, allez au golf si elle est élevée et non si elle est basse. De plus, lorsque vous revenez au début et que le temps est nuageux, vous pouvez penser à aller au golf quelles que soient les autres conditions.

À propos de cet article

Un algorithme qui crée automatiquement un tel arbre de décision à partir de données est connu. Dans cet article, nous utiliserons python pour implémenter un algorithme appelé ID3.

Position académique de l'arbre de décision

Les arbres de décision appartiennent à l'apprentissage supervisé et à l'apprentissage de la classification, principalement dans l'apprentissage automatique, qui fait partie de l'IA. Cet apprentissage de classification est un terme général pour une méthode dans laquelle des données d'apprentissage avec des données de réponse correctes sont données et un modèle qui en dérive la réponse correcte est automatiquement créé. L'apprentissage profond [^ 1], qui a obtenu de bons résultats en matière de reconnaissance d'image, qui est devenu populaire ces dernières années, est également un type d'apprentissage de classification. La différence entre l'apprentissage en profondeur et l'arbre de décision est de savoir si les règles générées sont ou non sous une forme compréhensible par l'homme. Contrairement à l'apprentissage en profondeur, qui est censé donner une réponse mais dont la raison est inconnue des humains, les règles sont faciles à comprendre comme dans l'exemple précédent de l'arbre de décision, alors créez un programme qui trouve automatiquement la réponse simplement sous forme d'apprentissage de classification. Non seulement cela, l'algorithme de génération d'arbre de décision est également utilisé du point de vue de l'exploration de données, comme la création d'un arbre de décision pour aider les gens à comprendre les données.

À propos de l'algorithme ID3 à créer

ID3 [^ 2] est un algorithme de génération d'arbre de décision inventé par Ross Quinlan en 1986. Il présente les caractéristiques suivantes.

1. Nous ne traitons que des données étiquetées comme aller / ne pas aller au golf, qui sont appelées données catégorielles (échelle nominale). Les données numériques ne peuvent pas être traitées.
2. À l'aide d'un index appelé «entropie d'information», recherchez l'attribut (colonne de données) qui présente la plus petite variation des valeurs d'attribut de classe (colonnes que vous souhaitez classer).

Traitement des données numériques

Dans le cas de l'algorithme C4.5 [^ 3], qui est une extension d'ID3, il est possible de classer les données numériques, mais comme l'idée de base est la même que ID3, ID3 sera repris en premier dans cet article. ..

Environnement de développement

Il a été confirmé que le programme illustré ci-dessous fonctionne dans l'environnement suivant.

--jupyter notebooks (j'ai utilisé des notebooks azur)

• Python 3.6 --import bibliothèque: math, pandas, functools (ne pas utiliser scikit-learn, tensorflow, etc.)

Texte intégral du programme

Si vous copiez le programme sur Jupyter Notebook pour le moment, cela fonctionnera.

id3.py

import math
import pandas as pd
from functools import reduce

#base de données
d = {
    "Météo":["Bien","Bien","Nuageux","pluie","pluie","pluie","Nuageux","Bien","Bien","pluie","Bien","Nuageux","Nuageux","pluie"],
    "Température":["Chaud","Chaud","Chaud","Chaud","Ryo","Ryo","Ryo","Chaud","Ryo","Chaud","Chaud","Chaud","Chaud","Chaud"],
    "Humidité":["Haute","Haute","Haute","Haute","d'habitude","d'habitude","d'habitude","Haute","d'habitude","d'habitude","d'habitude","Haute","d'habitude","Haute"],
    "Vent":["Rien","Oui","Rien","Rien","Rien","Oui","Oui","Rien","Rien","Rien","Oui","Oui","Rien","Oui"],
    #La dernière colonne contient les données que vous souhaitez dériver d'autres colonnes, également appelées variable objectif et données de réponse correctes.
    "le golf":["×","×","○","○","○","×","○","×","○","○","○","○","○","×"],
}
df0 = pd.DataFrame(d)

#Expression Lambda pour la distribution de valeur, l'argument est pandas.Series, la valeur de retour est un tableau contenant le numéro de chaque valeur
cstr = lambda s:[k+":"+str(v) for k,v in s.value_counts().items()]

#Structure de données de l'arbre de décision, nom:Le nom de ce nœud (tronc), df:Données associées à ce nœud,
# edges:Dans le cas d'une liste d'arêtes (branches) sortant de ce nœud, et d'un nœud feuille sans arêtes en dessous, les arêtes sont un tableau vide.
tree = {"name":"decision tree "+df0.columns[-1]+" "+str(cstr(df0.iloc[:,-1])),"edges":[],"df":df0}

#La génération d'arborescence enregistre les troncs susceptibles de générer des branches dans cet opn et les examine dans l'ordre.
#Lors de l'ajout d'un tronc à opn, il est ajouté à la fin du tableau et le nœud à étudier est retiré du début de opn, il s'agit donc d'une recherche de priorité de largeur.
opn = [tree]

#Expression lambda pour calculer l'entropie, l'argument est pandas.Série, la valeur de retour est la valeur d'entropie
entropy = lambda s:-reduce(lambda x,y:x+y,map(lambda x:(x/len(s))*math.log2(x/len(s)),s.value_counts()))

#Répétez jusqu'à ce que opn soit vide.
while(len(opn)!=0):
    #Extrayez le début d'opn et extrayez les données détenues par ce nœud.
    node1 = opn.pop(0)
    df1 = node1["df"]
    #Si l'entropie de ce nœud est 0, l'arête ne peut plus être étendue, donc la recherche de ce nœud se termine.
    if 0==entropy(df1.iloc[:,-1]):
        continue
    #Créez une variable pour enregistrer la liste des valeurs d'attribut de branchabilité.
    attrs = {}
    #Examinez tous les attributs sauf la dernière colonne des attributs de classe.
    for attr in list(df1)[:-1]:
        #Créez une variable pour enregistrer l'entropie lors du branchement avec cet attribut, les données après le branchement et la valeur d'attribut à branchement.
        attrs[attr] = {"entropy":0,"dfs":[],"values":[]}
        #Examinez toutes les valeurs possibles pour cet attribut.
        for value in set(df1[attr]):
            #Filtrer les données par valeur d'attribut.
            df2 = df1[df1[attr]==value]
            #Calculez l'entropie et enregistrez respectivement les données et les valeurs associées.
            attrs[attr]["entropy"] += entropy(df2.iloc[:,-1])*len(df2)/len(df1)
            attrs[attr]["dfs"] += [df2]
            attrs[attr]["values"] += [value]
            pass
        pass
    #Si aucun attribut ne peut séparer les valeurs de classe, terminez l'enquête sur ce nœud.
    if len(attrs)==0:
        continue
    #Obtenez l'attribut qui minimise l'entropie.
    attr = min(attrs,key=lambda x:attrs[x]["entropy"])
    #Ajoutez la valeur de chaque attribut de branchement et les données après le branchement à l'arborescence et à l'opn, respectivement.
    for d,v in zip(attrs[attr]["dfs"],attrs[attr]["values"]):
        tree2 = {"name":attr+"="+v,"edges":[],"df":d.drop(columns=attr)}
        node1["edges"].append(tree2)
        opn.append(tree2)
    pass

#Sortez l'ensemble de données.
print(df0,"\n-------------")
#Méthode pour convertir l'arbre en caractères, l'argument est l'arbre:Structure de données arborescente, retrait:Indentation lors de l'expression de caractères,
#La valeur de retour est une représentation de caractère de l'arbre. Cette méthode est appelée récursivement pour convertir tout ce qui se trouve dans l'arborescence en caractères.
def tstr(tree,indent=""):
    #Créez une représentation de caractère pour ce nœud.
    s = indent+tree["name"]+str(cstr(tree["df"].iloc[:,-1]) if len(tree["edges"])==0 else "")+"\n"
    #Boucle pour tous les bords de ce nœud.
    for e in tree["edges"]:
        #Ajoutez la représentation de caractère du nœud enfant à la représentation de caractère de ce nœud.
        s += tstr(e,indent+"  ")
        pass
    return s
#Exprimez l'arbre sous forme de caractères et affichez-le.
print(tstr(tree))

Résultat d'exécution

Lorsqu'il est exécuté, l'arbre de décision est émis sous forme de notation de caractères.

golf d'arbre de décision
Météo=Bien
Humidité=Haute['×:3']
Humidité=d'habitude['○:2']
Météo=pluie
Vent=Oui['×:2']
Vent=Rien['○:3']
Météo=Nuageux['○:4']

Modifiez l'attribut (colonne de données) que vous souhaitez apprendre

La dernière colonne de données d est l'attribut de classe (la colonne de données que vous souhaitez classer).

data.py

d = {
    "Météo":["Bien","Bien","Nuageux","pluie","pluie","pluie","Nuageux","Bien","Bien","pluie","Bien","Nuageux","Nuageux","pluie"],
    "Température":["Chaud","Chaud","Chaud","Chaud","Ryo","Ryo","Ryo","Chaud","Ryo","Chaud","Chaud","Chaud","Chaud","Chaud"],
    "Humidité":["Haute","Haute","Haute","Haute","d'habitude","d'habitude","d'habitude","Haute","d'habitude","d'habitude","d'habitude","Haute","d'habitude","Haute"],
    "le golf":["×","×","○","○","○","×","○","×","○","○","○","○","○","×"],
    #Le dernier attribut est l'attribut de classe (attribut qui est le but de la classification)
    "Vent":["Rien","Oui","Rien","Rien","Rien","Oui","Oui","Rien","Rien","Rien","Oui","Oui","Rien","Oui"],
}

Par exemple, si vous exécutez le vent en dernier comme ci-dessus, vous obtiendrez le résultat suivant.

vent d'arbre de décision['Rien:8', 'Oui:6']
le golf=×
Météo=pluie['Oui:2']
Météo=Bien
Température=Chaud
Humidité=Haute['Rien:1', 'Oui:1']
Température=Chaud['Rien:1']
le golf=○
Météo=Nuageux
Température=Chaud['Rien:2']
Température=Ryo['Oui:1']
Température=Chaud['Oui:1']
Météo=Bien
Température=Ryo['Rien:1']
Température=Chaud['Oui:1']
Météo=pluie['Rien:3']

Quand il y a du vent / pas de vent, des règles sont créées comme ne pas aller au golf, se ramifier en premier quand on y va.