arbre_decision.py

# author :
# Anparasan ANPUKKODY
# L2A - Licence Informatique Paris 8
# Numéro étudiant : 23000857
# Arbre de décision 3.0 - Final Project IA1
# Last updated : 30/11/2024


from collections import Counter
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report


# Création de la base de données
def database_creation(filename):

    # Ouverture du fichier
    data = open(filename, 'r')

    database = []
    classes = []


    for line in data:
        database.append(line.split(",", maxsplit=7))
    
    # Récupération des noms des attributs
    attributes = [attr.strip() for attr in database[0]]

    data.close()
    
    database.pop(0)


    # Récupération des cibles
    for entry in database:
        if entry[0] not in classes:
            classes.append(entry[0])

    filt = []
    for data in database:
        tmp = [new.strip() for new in data]
        filt.append(tmp)


    data_train, data_test = train_test_split(filt, test_size=0.20, random_state=42)

    label_test = []

    for data in data_test:
        label_test.append(data.pop(0))

    # Retourne les noms des attributs, les classes, la base de donnée, les données à tester
    return attributes, classes, data_train, data_test, label_test


# Calcul de l'indice de Gini
def Gini(data_index, visited, database, classes):
    total = len(database)
    gini_index = 0

    for entry in database:
        current = entry[data_index]
        
        if current in visited:
            continue

        visited.append(current)

        act = sum(1 for i in database if i[data_index] == current)
        classes_counter = []
        for i in range(len(classes)):
            classes_counter.append(0)
        
        for i, target in enumerate(classes):
            classes_counter[i] = sum(1 for entry in database if entry[data_index] == current and entry[0] == target)
        
        gini_value = (act / total) * (1 - sum((count / act) ** 2 for count in classes_counter))
        gini_index += gini_value

    return gini_index    


# Renvoi la cible majoritaire dans le cas ou database 
# contient des entrées avec les mêmes réponses mais différentes cibles
def get_majority_target(database):
    target_counts = Counter(entry[0] for entry in database)
    majority_target = target_counts.most_common(1)[0][0]
    return majority_target


# Construction de l'arbre
def build_tree(database, index_visited, classes, attributes):
    oneVar = True

    # Vérification si database continent qu'une seule cible, donc fin de la branche
    for i in range(len(database)-1):
        if database[i][0] != database[i+1][0]:
            oneVar = False
            break
    if oneVar :
        return database[0][0]
    
    # Vérification si database contient que des entrées avec les mêmes réponses mais différentes cibles
    sameAnswers = True
    for entry in database[1:]:
        for index in range(1, len(database[0])):
            if database[0][index] != entry[index]:
                sameAnswers = False
                break
        if not sameAnswers:
            break
    if sameAnswers:
        return get_majority_target(database)

    # Calcul de Gini pour trouver la question à traiter
    min_index = 1
    min_gini = 1000
    for i in range(1, len(database[0])):
        if i in index_visited:
            continue
        new_index = i
        new_gini = Gini(i, [], database, classes)
        if min_gini > new_gini:
            min_index = new_index
            min_gini = new_gini
    index_visited.append(min_index)

    # Initialisation du noeud principal pour cette question
    root = (attributes[min_index], [])
    answers = {}

    # Classification des entrées en fonction de la réponse dans un dictionnaire
    for entry in database:
        answer = entry[min_index]
        if answer not in answers:
            answers[answer] = []
        answers[answer].append(entry)

    sorted_answers = sorted(answers.items(), key=lambda x: x[0])

    # Construire le sous-arbre pour chaque réponse
    for answer, entry in sorted_answers:
        subtree = build_tree(entry, index_visited.copy(), classes, attributes)
        root[1].append((answer, subtree))

    return root



def searchNearestTree(branch, classes, attributes, testdata):
    for target in classes:
        if branch == target:
            return target
    index_attr = attributes.index(branch[0])  # Index de l'attribut actuel
    decision = float(testdata[index_attr - 1])      # Valeur de test correspondante

    # Trouver la branche avec la valeur la plus proche
    closest_branch = None
    closest_distance = float('inf')
    for branch_explore in branch[1]:
        # Calculer la distance entre la valeur de test et les réponses possibles
        current_value = float(branch_explore[0])
        distance = abs(current_value - decision)
        if distance < closest_distance:
            closest_distance = distance
            closest_branch = branch_explore
    end = ""
    # Explorer la branche la plus proche
    if closest_branch is not None:
        end = searchNearestTree(closest_branch[1], classes, attributes, testdata)
    if end != "":
        return end
    else :
    # Si aucune branche n'est trouvée, il y a une erreur dans les données
        print("Input error: no close match found!")
        return




# Création de la base de données. 
attributes, classes, database, data_test, label_train = database_creation("NHANES_age_prediction.csv")

tree = build_tree(database, [], classes, attributes)

results = []

for x in data_test:
    results.append(searchNearestTree(tree, classes, attributes, x))

report = classification_report(label_train, results)

print("Rapport de classification :\n", report)