Nella seguente repository viene implementato l'algoritmo di apprendimento per alberi di decisione con l'aggiunta di una strategia per la gestione dei valori mancanti degli attributi basata sull'assegnamento di una probabilità per ogni valore di un attributo in base ai valori noti negli esempi.
Per poter utilizzare il codice è necessario scaricare i tre datasets utilizzati dai link specificati qui di seguito ed inserirli nella directory "datasets" dove sono già presenti i files .name in cui sono riportati i nomi degli attributi di ciascun dataset.
In tutti e tre i casi si dovrà scaricare il file con estensione .data per poter ottenere il dataset d'interesse.
I tre datasets usati sono:
- Tic-Tac-Toe Endgame: reperibile a questo link.
- MONK's Problems: reperibile a questo link. Scaricare tutti i file aventi estensione .train ed unirli in unico file chiamato monks.data.
- Balance Scale: reperibile a questo link.
I file che compongono il progetto sono:
- main.py: gestisce l'esecuzione dell'intero codice. Si occupa anche della creazione dei grafici, della divisione del dataset in training set, validation set e test set e della validazione.
- performances.py: contiene i metodi per il calcolo dell'accuratezza:
- test: per ogni elemento del test set verifica se il valore del target ricavato tramite l'albero di decisone coincide o meno con il suo valore effettivo
- accuracy: calcola l'accuratezza dell'albero di decisione in funzione del numero di valori del target correttamente predetti
- dataset.py: contiene i metodi per la gestione del dataset e per la rimozione dei valori:
- remove_data: rimuove in modo casuale e uniforme con una data probabilità alcuni valori dagli esempi
- get_dts_name: restituisce il nome del dataset in esame
- get_attributes: restituisce il nome degli attributi che compongono il dataset e la posizione dell'attributo target
- get_examples: permette di estrapolare dal file .data tutti gli esempi che compongono il dataset con la relativa classificazione memorizzata a parte
- get_attributes_values: restituisce i valori di ciascun attributo
- get_target_values: resistuisce i valori assunti dal target
- dt_learning.py: classe che implementa l'algoritmo di apprendimento per alberi di decisione con la gestione dei valori mancanti:
- height_update: aggiorna il valore dell'attributo height che tiene traccia della profondità dell'albero di decisione
- same_classification: verifica se gli esempi forniti in ingresso al metodo hanno tutti la stessa classificazione (i.e. stesso valore del target)
- check_missing: verifica se nell'insieme di esempi ricevuto in ingresso mancano dei valori
- get_values: restituisce i valori di un certo attributo
- plurality_value: fornisce il valore più frequente del target entro un certo insieme di esempi
- get_weighted_occur: restituisce le occorrenze pesate per ogni singolo valore di un determinato attributo per un certo insieme di esempi
- get_prob: calcola la probabilità di un certo attributo in relazione ai suoi valori osservati in un certo insieme di esempi
- get_entropy: calcola l'entropia
- gain: calcola il gain per ciascun attributo disponibile su un dato insieme di esempi fornendo poi l'attributo con il gain più grande
- dt_learning: implementazione dell'algoritmo di apprendimento per alberi di decisione
Il progetto è stato realizzato utilizzando Python 3.8 come linguaggio di programmazione. Sono inoltre state utilizzate alcune librerie esterne:
- matplotlib: libreria esterna per la creazione dei grafici, utilizzata per mostare i risultati. [download]
- termcolor: per la stampa a colori sulla console. [download]
Sono state utilizzate anche le seguenti librerie di Python:
- random: per generare numeri casuali, rimuovere casualmente e uniformemente con una data probabilità alcuni valori e per scegliere casualmente degli elementi da una lista
- math: per eseguire calcoli matematici
- copy: per eseguire la deepcopy di alcune liste nel main
- statistics: per calcolare la moda delle altezze per cui si ha la maggior accuratezza