Laboratorio informatico data mining (modulo informatico)

TRASFORMAZIONE DEI DATI.

Operazioni di scalatura per far rientrare dati in un intervallo. La maggior parte dei modelli di

apprendimento trae beneficio da una preventiva standardizzazione dei dati, indicata anche come

normalizzazione.

RIDUZIONE DEI DATI.

In un contesto con data set molto ampi risulta difficile effettuare un’analisi, in presenza di grandi

dataset è infatti opportuno procedere a un’ulteriore fase di riduzione dei dati, in modo da rendere

più efficienti gli algoritmi di apprendimento, senza compromettere la qualità dei risultati ottenuti.

La tecnica di riduzione dei dati opera per rendere il data set più opportuno in termini di efficienza,

accuratezza e semplicità.

- Problema di risorse del PC: un grande data set crea problemi dal punto di vista di

tempo e risorse richieste.

- Vi è un problema dal punto di vista però umano.

La riduzione dei dati (semplificazione del dataset) si sviluppa su tre logiche:

Riduco gli attributi che danno le stesse informazioni. (ricerca di correlazioni forti tra attributi

predittori), Riduzione delle osservazioni (cardinalità del dataset) mediante campionamento (deve

essere significativo dal punto di vista statistico). Approccio utilizzato nel data mining perché

processare l’intero dataset è spesso troppo costoso o richiede troppo tempo.

La riduzione dei dati si sviluppa secondo tre logiche:

- Riduzione degli attributi (dimensionalità del dataset) mediante selezione, che mira a

eliminare dal dataset un sottoinsieme di variabili ritenute non rilevanti per le analisi di

data mining.

- Riduzione degli attributi (dimensionalità del dataset) mediante proiezione, che si

propone di

sostituire un sottoinsieme di attributi numerici originari con un numero inferiore di nuovi

attributi ottenuti come loro combinazione lineare.

- Riduzione dei valori degli attributi mediante discretizzazione o aggregazione, che si

propone di ottenere una diminuzione nel numero di valori distinti assunti da uno o più

attributi.

La diminuzione di istanze può comunque portare ad una rarefazione del significato del dataset. Il

tutto sta nel trovare un campione significativo della popolazione.

Nei dataset di tipo supervisionato esiste una relazione più importante: la relazione tra l’attributo

predittore e la classe.

Per trovare queste relazioni bisogna rifarsi al concetto di entropia. Entropia: misura quanto un

dataset è ordinato rispetto alla classe di appartenenza guardando di volta in volta ogni attributo

predittore.

Abbiamo quindi parlato della prima fase: comprensione e preparazione dei dati.

Classificazione.

Algoritmi di classificazione che stanno nella famiglia degli alberi decisionali.

Un albero decisionale o, nel contesto specifico delle problematiche di classificazione, albero di

classificazione è una struttura semplice in cui i nodi non terminali rappresentano i test sugli attributi

predittori (o attributi di input) i rami rappresentano il risultato dei test (valori degli attributi predittori)

e i

nodi terminali (o foglie) rappresentano le decisioni risultanti (ossia la classe di appartenenza). È

una delle tecniche di classificazione più utilizzate, che permette di rappresentare con una struttura

ad albero un insieme di regole di classificazione.

Esempio di albero:

Da un albero decisionale è possibile derivare (semplicemente percorrendolo dal nodo radice fino ai

nodi foglia) un insieme di regole (dette regole produttive), aventi la forma: IF condizione

antecedente THEN condizione conseguente.

La condizione antecedente è una congiunzione di predicati sugli attributi predittori, la condizione

conseguente è un’etichetta di classe.

Analisi di tipo supervisionato di osservazioni derivanti dal passato.

Analisi di tipi interpretativo con fini predittivi per il futuro. Provo a vedere se esistono delle regole

predittive che partendo dai sintomi mi permettano di stabilire la diagnosi.

Analisi di tipo supervisionato in quanto l’algoritmo si appoggia nel modello all’attributo target.

L’attributo target fa da supervisore alla costruzione del modello.

Albero decisionale: struttura semplice e quindi facilmente fruibile.

Si parte da un nodo centrale chiamato radice, dal quale partono i rami con le possibili risposte a

quel attributo.

Il nodo finale si chiama foglia e non è altro che la risposta che deriva dall’aver percorso quel

determinato ramo.

La rappresentazione grafica di un albero è sempre la stessa.

Quindi i problemi sono: formalizzare un algoritmo, cercare di capire quale attributo predittore

scegliere per primo e quali altri attributi predittori scegliere se con il primo non si descrivono tutti.

Si parte quindi dall’attributo e si va a percorre il ramo.

Si creano così un set di regole, questo set di regole si chiama sistema di classificazione.

Noi ci concentreremo sempre sulle regole derivanti dall’albero.

Il modello di classificazione è fatto di tutte le regole derivanti dall’albero.

Normalmente il numero di regole è diverso dai valori che può avere l’attributo di classe. Le regole

normalmente sono di più dei valori.

Regola fondamentale: metrica di qualità: confidenza di una regola: una regola è composta da un

antecedente e da un conseguente, la confidenza è data dalla percentuale di osservazioni che

soddisfano oltre alla condizione antecedente anche quella conseguente.

Calcolo il numero di osservazioni che soddisfano l’antecedente e lo metto al denominatore.

Al numeratore vanno il numero delle condizioni conseguenti soddisfatte.

Vi sono più algoritmi di classificazione, esiste la possibilità di definire una tassonomia di modelli di

classificazione.

I modelli si basano su una logica di successiva separazione del dataset in sistemi sempre più

piccoli, dove tendenzialmente le osservazioni appartengono tutte alla stessa classe di

appartenenza.

Modelli euristici. Utilizzano procedure basate su schemi semplici e intuitivi, per lo più di natura

empirica. Tra questi, rientrano gli alberi decisionali e le decision rules.

I modelli di separazione spaziale sono invece un po’ diversi: all’interno dello spazio degli attributi,

cercano di identificare se all’interno degli spazi tutti gli attributi hanno lo stesso valore di classe.

Descrivo i due gruppi che appartengono a spazi diversi tramite l’equazione della retta che separa i

due spazi.

Un altro modello è il nearest neighbor, che ragiona però non in termini di spazio ma in termini di

distanza.

I modelli di regressione non ci interessano.

Ci interessano maggiormente i modelli probabilistici: modelli che si basano sulla teoria della

probabilità, rigorosi dal punto di vista matematico/statistico.

CLASSIFICAZIONE.

Alberi di classificazione.

Prendo un insieme di osservazioni riferite al passato sui quali è noto l’attributo di classe. Su queste

costruisco il modello.

Se il risultato di qualità del modello è cattiva, allora considero il modello come non applicabile.

Nell’ipotesi in cui invece le statistiche prevedano un modello invece di buona qualità, allora lo testo

su un altro dataset di osservazioni sulle quali conosco il set di appartenenza.

Fase di training e successivamente fase di test.

CLASSIFICAZIONE . (come funzione e come saper leggere un risultato di un algoritmo di

classificazione).

Gli alberi di classificazione (appartenenti alla più ampia categoria degli alberi decisionali)

costituiscono il modo più semplice di classificare delle osservazioni in un numero finito di classi.

Essi vengono costruiti suddividendo ripetutamente le osservazioni in sottoinsiemi il più possibile

omogenei rispetto all’attributo target (che ricordiamo essere categorico).

La suddivisione produce una gerarchia ad albero, dove i sottoinsiemi di osservazioni vengono

chiamati nodi e quelli terminali foglie.

Gli alberi si basano su un concetto di progressiva suddivisione di un data set in sottogruppi più

piccoli che siano omogenei rispetto al loro contenuto.

Bisogna allora trovare un attributo che consente sulla base dei suoi lavori tanti sottoinsiemi nei

quali vi siano solo attributi che appartengono alla stessa classe.

Bisogna allora trovare attributi in cui nei sottoinsiemi vi siano dati appartenenti il più possibile alla

stessa classe.

Lo scopo è ottenere una statistica, una metrica dal punto di vista matematico che permetta di

descrivere la classe.

In particolare, i nodi sono etichettati con il nome degli attributi, i rami sono etichettati con i possibili

valori

dell’attributo soprastante, mentre le foglie dell’albero sono etichettate con i differenti valori

dell’attributo target (valori che descrivono le classi di appartenenza).

Un’osservazione è classificata seguendo un percorso lungo l’albero che porti dalla radice ad una

foglia.

I percorsi rappresentano le regole di classificazione.

L’algoritmo che noi utilizzeremo è l’algoritmo C4.5. in Weka l’algoritmo si chiama j48.

Questo algoritmo prende un insieme di osservazioni di partenza, la prima fase si chiama training

(addestramento del modello: l’algoritmo impara a conoscere un modello all’interno dei dati).

Se T è un dataset, la prima fase di funzionamento dell’algoritmo prevede la selezione di un

attributo che differenza meglio le osservazioni che stanno all’interno di T.

Significa quindi trovare l’attributo con la più alta capacità informativa (che suddivide il data set in

sottoinsiemi) rispetto a tutti gli altri rispetto all’attributo di classe.

Si crea un nodo dell’albero: nodo radice, che corrisponde all’attributo selezionato. A partire da tale

nodo si creano dei rami.

Per ogni sottoinsieme creato nel passo 3, si va a vedere se tutte le osservazioni stanno tutte nella

stessa classe (dell’attributo di classe) e allora è un nodo terminale: nodo foglia.

Se non stanno tutte nella stessa classe, andiamo avanti con un'altra separazione tramite un nuovo

attributo che meglio rappresenta l’insieme dal punto di vista informativo, fino a che tutti i

sottoinsiemi non saranno nodi foglia o fino a che non siano finiti gli attributi.

Questa è la logica empirica applicata per l’apprendimento del modello, come funziona l’algoritmo

C4.5.

Per poterlo utilizzare in ambito informatico, si deve formalizzare l’algoritmo in modo matematico.

CRITERI PER LA COSTRUZIONE DEGLI ALBERI.

In realtà, la ripartizione omogenea delle osservazioni si verifica raramente ed è il motivo per cui il

processo di ripartizione del dataset in sottoinsiemi è ricorsivo e porta alla costruzione di alberi

costituiti da un numero elevato di nodi (abbiamo bisogno di più attributi per descrivere la regolarità<