Decision Tree Example PDF

Alberi di decisione 03/02/20 Data Mining - Classificazione 8  Esempio di albero di decisione l l a a us ric o o...

Alberi di decisione 03/02/20 Data Mining - Classificazione 8  Esempio di albero di decisione l l a a us ric o o ric uo eg eg tin ss t t n l a Nodo radice ca ca co c Condizione di test Home Marital Annual Defaulted ID Owner Status Income Borrower 1 Yes Single 125K No Nodo interno Home 2 No Married 100K No Owner Yes No 3 No Single 70K No 4 Yes Married 120K No NO MarSt 5 No Divorced 95K Yes Single, Divorced Married 6 No Married 60K No Income NO 7 Yes Divorced 220K No 8 No Single 85K < 80K > 80K Yes 9 No Married 75K No NO YES 10 No Single 90K Yes Nodo terminale / foglia 10 Insieme di Modello: albero di addestramento decisione 03/02/20 Data Mining - Classificazione 9  Altro esempio di albero di decisione cal cal us ri ri uo ego ego tin ss t t n a ca ca co cl MarSt Single, Married Divorced Home Marital Annual Defaulted ID Owner Status Income Borrower NO Home 1 Yes Single 125K No Yes Owner No 2 No Married 100K No 3 No Single 70K No NO Income 4 Yes Married 120K No < 80K > 80K 5 No Divorced 95K Yes NO YES 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9 No Married 75K No Ci molti alberi che si adattano agli 10 No Single 90K Yes stessi dati. 10 03/02/20 Data Mining - Classificazione 10  Approccio di base: deduzione Tid Attrib1 Attrib2 Attrib3 Class Learning No 1 Yes Large 125K algorithm 2 No Medium 100K No 3 No Small 70K No 4 Yes Medium 120K No Induction 5 No Large 95K Yes 6 No Medium 60K No 7 Yes Large 220K No Learn 8 No Small 85K Yes Model 9 No Medium 75K No 10 No Small 90K Yes Model 10 Training Set Apply Tid Attrib1 Attrib2 Attrib3 Class Model 11 No Small 55K ? 12 Yes Medium 80K ? 13 Yes Large 110K ? Deduction 14 No Small 95K ? 15 No Large 67K ? 10 Test Set 03/02/20 Data Mining - Classificazione 11  Applicare un modello ai dati Si inizia dalla radice Home Marital Annual Defaulted Owner Status Income Borrower No Married 80K ? Home 10 Yes Owner No NO MarSt Single, Divorced Married Income NO < 80K > 80K NO YES 03/02/20 Data Mining - Classificazione 12  Applicare un modello ai dati Home Marital Annual Defaulted Owner Status Income Borrower No Married 80K ? Home 10 Yes Owner No NO MarSt Single, Divorced Married Income NO < 80K > 80K NO YES 03/02/20 Data Mining - Classificazione 13  Applicare un modello ai dati Home Marital Annual Defaulted Owner Status Income Borrower No Married 80K ? Home 10 Yes Owner No NO MarSt Single, Divorced Married Income NO < 80K > 80K NO YES 03/02/20 Data Mining - Classificazione 14  Applicare un modello ai dati Home Marital Annual Defaulted Owner Status Income Borrower No Married 80K ? Home 10 Yes Owner No NO MarSt Single, Divorced Married Income NO < 80K > 80K NO YES 03/02/20 Data Mining - Classificazione 15  Applicare un modello ai dati Home Marital Annual Defaulted Owner Status Income Borrower No Married 80K ? Home 10 Yes Owner No NO MarSt Single, Divorced Married Income NO < 80K > 80K NO YES 03/02/20 Data Mining - Classificazione 16  Applicare un modello ai dati Home Marital Annual Defaulted Owner Status Income Borrower No Married 80K ? Home 10 Yes Owner No NO MarSt Single, Divorced Married Assegna “No” al campo Defaulted Borrower per questa istanza. Income NO < 80K > 80K NO YES 03/02/20 Data Mining - Classificazione 17  Approccio di base: induzione Tid Attrib1 Attrib2 Attrib3 Class Tree 1 Yes Large 125K No Induction 2 No Medium 100K No algorithm 3 No Small 70K No 4 Yes Medium 120K No Induction 5 No Large 95K Yes 6 No Medium 60K No 7 Yes Large 220K No Learn 8 No Small 85K Yes Model 9 No Medium 75K No 10 No Small 90K Yes Model 10 Training Set Apply Decision Tid Attrib1 Attrib2 Attrib3 Class Model Tree 11 No Small 55K ? 12 Yes Medium 80K ? 13 Yes Large 110K ? Deduction 14 No Small 95K ? 15 No Large 67K ? 10 Test Set 03/02/20 Data Mining - Classificazione 18  Decision Tree Induction Molti algoritmi Algoritmo di Hunt (uno dei primi) CART ID3, C4.5 SLIQ,SPRINT In generale noti come algoritmi di decision tree induction o, in italiano, induzione di alberi di classificazione 03/02/20 Data Mining - Classificazione 19  Algoritmo di Hunt Approccio greedy (ingordo) ID Home Owner Marital Status Annual Defaulted Income Borrower 1 Yes Single 125K No Sia Dt l’insieme di record di 2 No Married 100K No addestramento che raggiunge il nodo t. 3 No Single 70K No Per il nodo radice Dt è tutto l’insieme di 4 5 Yes No Married 120K Divorced 95K No Yes addestramento 6 No Married 60K No Procedura generale 7 Yes Divorced 220K No 8 No Single 85K Yes Se Dt contiene tutti record con la stessa 9 No Married 75K No classe yt, allora t è un nodo foglia con 10 10 No Single 90K Yes classe yt. Dt Se Dt contiene record che appartengono a più classi, determinare una condizione di test per scindere i dati in sottoinsiemi ? più piccoli. Applicare la procedura ricorsivamente a ogni sottoinsieme. 03/02/20 Data Mining - Classificazione 20  Algoritmo di Hunt Home Marital Annual Defaulted Home ID Owner Status Income Borrower Owner 1 Yes Single 125K No Yes No Defaulted = No 2 No Married 100K No Defaulted = No Defaulted = No 3 No Single 70K No (7,3) (3,0) (4,3) 4 Yes Married 120K No (a) (b) 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No Home 8 No Single 85K Yes Owner Home Yes No 9 No Married 75K No Owner 10 No Single 90K Yes Defaulted = No Marital Yes No 10 Status (3,0) Single, Marital Married Defaulted = No Divorced Status (3,0) Single, Annual Defaulted = No Married Divorced Income (3,0) Defaulted = Yes Defaulted = No < 80K >= 80K (1,3) (3,0) Defaulted = No Defaulted = Yes (1,0) (0,3) (c) (d) 03/02/20 Data Mining - Classificazione 21  Algoritmo di Hunt Home Marital Annual Defaulted Home ID Owner Status Income Borrower Owner 1 Yes Single 125K No Yes No Defaulted = No 2 No Married 100K No Defaulted = No Defaulted = No 3 No Single 70K No (7,3) (3,0) (4,3) 4 Yes Married 120K No (a) (b) 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No Home 8 No Single 85K Yes Owner Home Yes No 9 No Married 75K No Owner 10 No Single 90K Yes Defaulted = No Marital Yes No 10 Status (3,0) Single, Marital Married Defaulted = No Divorced Status (3,0) Single, Annual Defaulted = No Married Divorced Income (3,0) Defaulted = Yes Defaulted = No < 80K >= 80K (1,3) (3,0) Defaulted = No Defaulted = Yes (1,0) (0,3) (c) (d) 03/02/20 Data Mining - Classificazione 22  Algoritmo di Hunt Home Marital Annual Defaulted Home ID Owner Status Income Borrower Owner 1 Yes Single 125K No Yes No Defaulted = No 2 No Married 100K No Defaulted = No Defaulted = No 3 No Single 70K No (7,3) (3,0) (4,3) 4 Yes Married 120K No (a) (b) 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No Home 8 No Single 85K Yes Owner Home Yes No 9 No Married 75K No Owner 10 No Single 90K Yes Defaulted = No Marital Yes No 10 Status (3,0) Single, Marital Married Defaulted = No Divorced Status (3,0) Single, Annual Defaulted = No Married Divorced Income (3,0) Defaulted = Yes Defaulted = No < 80K >= 80K (1,3) (3,0) Defaulted = No Defaulted = Yes (1,0) (0,3) (c) (d) 03/02/20 Data Mining - Classificazione 23  Algoritmo di Hunt Home Marital Annual Defaulted Home ID Owner Status Income Borrower Owner 1 Yes Single 125K No Yes No Defaulted = No 2 No Married 100K No Defaulted = No Defaulted = No 3 No Single 70K No (7,3) (3,0) (4,3) 4 Yes Married 120K No (a) (b) 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No Home 8 No Single 85K Yes Owner Home Yes No 9 No Married 75K No Owner 10 No Single 90K Yes Defaulted = No Marital Yes No 10 Status (3,0) Single, Marital Married Defaulted = No Divorced Status (3,0) Single, Annual Defaulted = No Married Divorced Income (3,0) Defaulted = Yes Defaulted = No < 80K >= 80K (1,3) (3,0) Defaulted = No Defaulted = Yes (1,0) (0,3) (c) (d) 03/02/20 Data Mining - Classificazione 24  Dettagli da specificare Criterio di scissione: come determinare le condizioni di test? Individuare le possibili condizioni di test – Dipendono dal tipo degli attributi Scegliere il test migliore Criterio di terminazione: quando deve interrompersi la procedura? Quando tutti i record appartengono alla stessa classe – si sceglie come etichetta la classe in questione Quando tutti i record hanno lo stesso valore per tutti gli attributi – si sceglie come etichetta la classe maggioritaria Si applica un criterio di terminazione anticipata? 03/02/20 Data Mining - Classificazione 25  Dettagli da specificare Criterio di scissione: come determinare le condizioni di test? Individuare le possibili condizioni di test – Dipendono dal tipo degli attributi Scegliere il test migliore Criterio di terminazione: quando deve interrompersi la procedura? Quando tutti i record appartengono alla stessa classe – si sceglie come etichetta la classe in questione Quando tutti i record hanno lo stesso valore per tutti gli attributi – si sceglie come etichetta la classe maggioritaria Si applica un criterio di terminazione anticipata? 03/02/20 Data Mining - Classificazione 26  Condizioni di test Dipendono dal tipo di attributo Nominale Ordinale Continuo Dipendono dal numero di figli che vogliamo creare Scissione a due vie (binaria, o binary split) Scissione a molte vie (multi-way split) 03/02/20 Data Mining - Classificazione 27  Test per attributi nominali Scissione a molte vie Marital Status Usare tanti figli quanti sono i possibili valori distinti dell’attributo. Single Divorced Married Scissione binaria Dividere i possibili valori in due sottoinsiemi Marital Marital Marital Status Status Status OR OR {Married} {Single, {Single} {Married, {Single, {Divorced} Divorced} Divorced} Married} 03/02/20 Data Mining - Classificazione 28  Test per attributi ordinali Shirt Scissione a molte vie Size Usare tanti figlio quanti sono i possibili valori distinti Small Extra Large Medium Large dell’attributo. Shirt Shirt Size Size Scissione binaria Dividere i valori in due {Small, {Large, {Small} {Medium, Large, sottoinsiemi Medium} Extra Large} Extra Large} Shirt La suddivisione deve Size Questo preservare l’ordine tra i partizionamento non preserva valori degli attributi l’ordinamento {Small, {Medium, Large} Extra Large} 03/02/20 Data Mining - Classificazione 29  Test per attributi continui Annual Annual Income Income? > 80K? < 10K > 80K Yes No [10K,25K) [25K,50K) [50K,80K) (i) Binary split (ii) Multi-way split 03/02/20 Data Mining - Classificazione 30  Test per attributi continui Scissione binaria: (A ≤ v) or (A > v) Considera tutte le possibili suddivisioni binarie Costoso dal punto di vista computazionale Partizionamento a molte vie Si discretizza l’attributo per ottenere un attributo ordinale categoriale – Discretizzazione statica – lo si fa una volta per tutte all’inizio del procedimento Più efficiente – Discretizzazione dinamica – si ripete per ogni nodo Produce risultati migliori 03/02/20 Data Mining - Classificazione 31  Dettagli da specificare Criterio di scissione: come determinare le condizioni di test? Individuare le possibili condizioni di test – Dipendono dal tipo degli attributi Scegliere il test migliore Criterio di terminazione: quando deve interrompersi la procedura? Quando tutti i record appartengono alla stessa classe – si sceglie come etichetta la classe in question Quando tutti i record hanno lo stesso valore per gli attributi – si sceglie come etichetta la classe maggioritaria Si applica un criterio di terminazione anticipata? 03/02/20 Data Mining - Classificazione 32  Come valutare la bontà di un test \ \ Prima della suddivisione: 10 record di classe 0, 10 record di classe 1 Quale condizione di test è la migliore? Gender Car Customer Type ID Yes No Family Luxury c1 c20 c10 c11 Sports C0: 6 C0: 4 C0: 1 C0: 8 C0: 1 C0: 1... C0: 1 C0: 0... C0: 0 C1: 4 C1: 6 C1: 3 C1: 0 C1: 7 C1: 0 C1: 0 C1: 1 C1: 1 03/02/20 Data Mining - Classificazione 33  Come valutare la bontà di un test Approccio greedy: I nodi con distribuzioni di classe più omogenee (o pure) sono da preferire. Serve una misura di impurità dei nodi C0: 5 C0: 9 C1: 5 C1: 1 Alto grado di impurità Basso grado di impurità 03/02/20 Data Mining - Classificazione 34  Misure di impurità di un nodo Indice di Gini c 2 GINI (t )=1− ∑ pi (t ) i=1 dove Ci sono c classi possibili, indicate con 1, …, c pi(t) è la frequenza relativa delle istanze di training appartenenti alla classe i nel nodo t. Entropia c H (t)=− ∑ pi (t ) log 2 pi (t ) i=1 Errore di classificazione Error (t)=1−maxi pi (t) 03/02/20 Data Mining - Classificazione 35  Indice di Gini c 2 GINI (t )=1− ∑ pi (t ) i=1 Massimo 1-1/c quando i record sono distribuiti uniformemente tra le classi Minimo 0 quando tutti i record appartengono alla stessa classe. Usato negli algoritmi CART, SLIQ, SPRINT C1 0 P1 = 0/6 = 0 P2 = 6/6 = 1 C2 6 Gini = 1 – P12 – P22 = 1 – 0 – 1 = 0 C1 1 P1 = 1/6 P2 = 5/6 C2 5 Gini = 1 – (1/6)2 – (5/6)2 = 0.278 C1 2 P1 = 2/6 P2 = 4/6 C2 4 Gini = 1 – (2/6)2 – (4/6)2 = 0.444 03/02/20 Data Mining - Classificazione 36  Entropia c H (t)=− ∑ pi (t ) log 2 pi (t ) i=1 Massimo log2c quando i record sono distribuiti uniformemente tra le classi Minimo 0 quando tutti i record appartengono alla stessa classe. Usato negli algoritmi ID3 e C4.5 C1 0 P1 = 0/6 = 0 P2 = 6/6 = 1 C2 6 Entropy = – 0 log 0 – 1 log 1 = – 0 – 0 = 0 C1 1 P1 = 1/6 P2 = 5/6 C2 5 Entropy = – (1/6) log2 (1/6) – (5/6) log2 (1/6) = 0.65 C1 2 P1 = 2/6 P2 = 4/6 C2 4 Entropy = – (2/6) log2 (2/6) – (4/6) log2 (4/6) = 0.92 03/02/20 Data Mining - Classificazione 37  Errore di classificazione Error (t)=1−maxi pi (t) Massimo 1-1/c quando i record sono distribuiti uniformemente tra le classi Minimo 0 quando tutti i record appartengono alla stessa classe. C1 0 P1 = 0/6 = 0 P2 = 6/6 = 1 C2 6 Error = 1 – max (0, 1) = 1 – 1 = 0 C1 1 P1 = 1/6 P2 = 5/6 C2 5 Error = 1 – max (1/6, 5/6) = 1 – 5/6 = 1/6 C1 2 P1 = 2/6 P2 = 4/6 C2 4 Error = 1 – max (2/6, 4/6) = 1 – 4/6 = 1/3 03/02/20 Data Mining - Classificazione 38  Esempio con due sole classi Probabilità delle due classi: p e 1-p 03/02/20 Data Mining - Classificazione 39  Impurità di una partizione Quando nodo t viene diviso in k figli t1,…, tk, l’impurità della partizione è calcolata come segue: k N (t i ) M =∑ M (t i ) i=1 N (t) M(ti) è una qualunque misura di impurità dei nodi N(t) è il numero di record al nodo t N(ti) è il numero di record al nodo figlio ti L’effetto dei pesi N(ti) è di pesare di più i figli con molti record associati. 03/02/20 Data Mining - Classificazione 40  Impurità di una partizione Parent B? C1 7 Yes No C2 5 Gini = 0.486 Node N1 Node N2 Gini(N1) = 1 – (5/6)2 – (1/6)2 N1 N2 M = Gini pesato di N1 e N2 = 0.278 C1 5 2 = 6/12 * 0.278 + Gini(N2) C2 1 4 6/12 * 0.444 = 1 – (2/6)2 – (4/6)2 = 0.361 Gini=0.361 = 0.444 Gain = 0.486 – 0.361 = 0.125 03/02/20 Data Mining - Classificazione 41  Scegliere il test migliore Sia t il nodo originale, suddiviso nei nodi t1, … , tk Sia N(t) il numero di record che arrivano al nodo t. Calcolare la misura di impurità P prima della suddivisione Calcolare la misura di impurità M della suddivisione Calcolare il guadagno di purezza della suddivisione Guadagno=P−M Scegliere la condizione di test che fornisce il massimo guadagno Il guadagno si chiama guadagno di informazione (Information Gain) se la misura di impurità usata è l’entropia. Massimizzare il guadagno equivale a minimizzare M 03/02/20 Data Mining - Classificazione 42  Scegliere il test migliore Prima della scissione C0 N00 P C1 N01 A? B? Yes No Yes No Node N1 Node N2 Node N3 Node N4 C0 N10 C0 N20 C0 N30 C0 N40 C1 N11 C1 N21 C1 N31 C1 N41 M11 M12 M21 M22 M1 M2 Gain = P – M1 vs P – M2 03/02/20 Data Mining - Classificazione 43  Esempio: scegliere il test migliore Home Marital Annual Defaulted ID Owner Status Income Borrower Il guadagno maggiore si ottiene scegliendo l’attributo 1 Yes Single 125K No Home Owner o Marital Status con partizioni {Single, 2 No Married 100K No Divorced} e {Married}. 3 No Single 70K No 4 Yes Married 120K No 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9 No Married 75K No 10 No Single 90K Yes 10 03/02/20 Data Mining - Classificazione 44  Esempio per un attributo continuo Home Marital Annual Defaulted ID Owner Status Income Borrower Il test binario migliore sull’attributo Annual Income risulta 1 Yes Single 125K No Income < 97. Il guadagno che si ottiene è anche migliore 2 No Married 100K No rispetto all’uso di Home Owner nella slide precedente. 3 No Single 70K No 4 Yes Married 120K No 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9 No Married 75K No 10 No Single 90K Yes 10 Cheat No No No Yes Yes Yes No No No No Annual Income Valori ordinati 60 70 75 85 90 95 100 120 125 220 Punti di 55 65 72 80 87 92 97 110 122 172 230 separazione Yes 0 3 0 3 0 3 0 3 1 2 2 1 3 0 3 0 3 0 3 0 3 0 No 0 7 1 6 2 5 3 4 3 4 3 4 3 4 4 3 5 2 6 1 7 0 Gini 0.420 0.400 0.375 0.343 0.417 0.400 0.300 0.343 0.375 0.400 0.420 03/02/20 Data Mining - Classificazione 45  Confronto tra indici (1) Mostriamo un paio di esempi del fatto che cambiando la misura di impurità possono cambiare i risultati. A? Parent C1 7 Yes No C2 3 Node N1 Node N2 Gini = 0.42 Gini(N1) = 1 – (3/3)2 – (0/3)2 N1 N2 C1 3 4 L’indice di Gini migliora =0 aggiungendo la C2 0 3 Gini(N2) suddivisione, ma l’errore Gini=0.342 di classificazione è = 1 – (4/7)2 – (3/7)2 = 0.489 sempre 3/10. Gini(partizione) = 3/10 * 0 + 7/10 * 0.489 = 0.342 03/02/20 Data Mining - Classificazione 46  Confronto tra indici (2) A? Parent C1 7 Yes No C2 3 Node N1 Node N2 Gini = 0.42 N1 N2 N1 N2 C1 3 4 C1 3 4 C2 0 3 C2 1 2 Gini=0.342 Gini=0.416 Diverse suddivisione danno luogo ad indici di Gini diversi, ma l’errore di classificazione in tutti e tre i casi è 0.3 03/02/20 Data Mining - Classificazione 47  Numero elevato di partizioni La misura basata sull’impurità dei nodi tende a preferire test che risultano in un numero grande di nodi figli, ognuno puro o quasi. Gender Car Customer Type ID Yes No Family Luxury c1 c20 c10 c11 Sports C0: 6 C0: 4 C0: 1 C0: 8 C0: 1 C0: 1... C0: 1 C0: 0... C0: 0 C1: 4 C1: 6 C1: 3 C1: 0 C1: 7 C1: 0 C1: 0 C1: 1 C1: 1 CustomerID ha il guadagno più alto perché l’impurità di tutti i figli è 0. Ma CustomerID è un pessimo attributo su cui costruire un algoritmo di classificazione. 03/02/20 Data Mining - Classificazione 48  Gain Ratio Meglio usare il Gain Ratio: k Information Gain N (t i ) N (t i ) GAIN Ratio= SplitInfo=−∑ log 2 SplitINFO i=1 N (t) N (t ) dove il nodo t è diviso nei nodi t1, …, tk Il guadagno di informazione viene modificato con l’entropia della scissione (SplitInfo) Valori elevati di SplitInfo (quindi suddivisioni con molti figli) diminuiscono il valore di Gain Ratio. Usato nell’algoritmo C4.5 03/02/20 Data Mining - Classificazione 49  Esempio di uso di Gain Ratio Gender Car Customer Type ID Yes No Family Luxury c1 c20 c10 c11 Sports C0: 6 C0: 4 C0: 1 C0: 8 C0: 1 C0: 1... C0: 1 C0: 0... C0: 0 C1: 4 C1: 6 C1: 3 C1: 0 C1: 7 C1: 0 C1: 0 C1: 1 C1: 1 H iniziale = H(10/20, 10/20) = 1 bit IG(Gender) = 0,03 bit → GainRatio(Gender) = 0,03 IG(Car Type) = 0,62 bit → GainRatio(Car Type) = 0,41 IG(Customer ID) = 1 bit → GainRatio(CustomerID) = 0,23 03/02/20 Data Mining - Classificazione 50  Vantaggi e svantaggi Vantaggi degli alberi di decisione Si possono applicare in numerosi contesti – Nessuna ipotesi iniziale sulla distribuzione dei dati – Supportano dati sia discreti che continui – Supportano più di due classi – Si estendono facilmente al caso di dati mancanti Procedura di induzione poco costosa dal punto di vista computazionale – usano metodi greedy non ottimali che comunque producono buoni risultati Molto veloci nel classificare nuovi record Gli alberi piccoli sono facili da interpretare Gestiscono facilmente attributi ridondanti o irrilevanti Svantaggi degli alberi di decisione Non gestiscono bene la presenza di attributi che interagiscono tra di loro I test sui nodi coinvolgono un singolo attributo alla volta 03/02/20 Data Mining - Classificazione 51  Attributi che interagiscono + : 1000 istanze o : 1000 istanze x2 x1 03/02/20 Data Mining - Classificazione 52  Attributi che interagiscono Entropia dei miglior split per x1 e x2 Entropia (x1) : 0.99 x2 Entropia (x2) : 0.99 Lo split migliore non si ha per x1 < 10 e x2 < 10 (per i quali l’entropia è 1) ma per valori diversi, cosa che porta a generare alberi con più nodi del x1 necessario. 03/02/20 Data Mining - Classificazione 53  Attributi che interagiscono + : 1000 istanze Entropia (x1) : 0.99 Entropia (x2) : 0.99 o : 1000 istanze Entropia (x3) : 0.98 x2 Si aggiunge un L’attributo scelto per attributo x3 che è un il partizionamento è rumore generato da x3! una distribuzione x1 uniforme. x3 x3 x1 x2 03/02/20 Data Mining - Classificazione 54  Frontiera di decisione Un classificatore partiziona lo spazio degli attributi in regione disgiunte, ognuna delle quali è associata ad una unica classe. L’insieme dei bordi tra regioni adiacenti si chiama frontiera di decisione. Nel caso degli alberi di decisione, la frontiera è composta da linee parallele agli assi 03/02/20 Data Mining - Classificazione 55  Alberi di decisione obliqui Sia le classi positive (+) che negative (o) sono generate da un distribuzione gaussiana asimmetrica con centri (8,8) e (12,12) rispettivamente. Situazioni come quella di sopra sono pessime per gli alberi di decisione tradizionali. Ci sono gli alberi di decisione obliqui che usano test del tipo “x + y < 20” Più espressivi ma più costosi dal punto di vista computazionale 03/02/20 Data Mining - Classificazione 56 Regressione e Statistica multivariata Regressione Che cosa è? È una tecnica utilizzata per capire la forma della relazione che intercorre Può avere un’unica variabile di esposizione (regressione semplice) o può avere più variabili di esposizione (regressione multipla) → questa tecnica è la tecnica principale della statistica multivariata Regressione Perché viene utilizzata? Per stimare e prevedere il valore che assume la variabile di outcome in corrispondenza di una combinazione di valori assunti dalla/dalle variabili exposure Capire se e quanto ciascuna variabile influisce sull’outcome Controllare per i fattori di confondimento e valutare l’interazione Regressione Le variabili di exposure vengono dette «variabili esplicative» o «variabili predittive» o «regressori» (sono l’insieme delle variabili indipendenti) La variabile di outcome è la variabile dipendente e spesso viene chiamata anche «variabile risposta» Regressione In base alla tipologia della variabile dipendente esistono vari tipi di regressione: Regressione lineare (la variabile è quantitativa continua) Regressione logistica (la variabile è dicotomica) Regressione logistica multinomiale (la variabile di outcome è policotomica) Regressione logistica ordinale (la variabile è ordinale) Regressione di Poisson (la variabile è quantitativa discreta) Regressione di Cox (time-to-event, variabile dicotomica+tempo) Regressione lineare La formula della retta di regressione lineare è data da: 𝑌 = 𝛽 + 𝛽 𝑋 + 𝛽 𝑋 +⋯+ 𝛽 𝑋 + 𝜀 Y→VARIABILE DIPENDENTE 𝑋 … 𝑋 →VARIABILI INDIPENDENTI 𝛽 →INTERCETTA 𝛽 … 𝛽 →COEFFICIENTE DI REGRESSIONE 𝜀 →ERRORE Regressione lineare Ci sono dei casi in cui non è opportuno stimare un modello di regressione lineare: 1. Quando attraverso lo scatterplot costruito con la variabile dipendente e quella indipendente osserviamo questa distribuzione a imbuto Regressione lineare Ci sono dei casi in cui non è opportuno stimare un modello di regressione lineare: I punti nella parte sinistra del grafico sono piuttosto vicini alla retta Più ci spostiamo verso destra più si scostano Regressione lineare Ci sono dei casi in cui non è opportuno stimare un modello di regressione lineare: 2. Quando la distribuzione dei dati non ha un andamento lineare  Regressione lineare 90,0 85,0 y = 0,4075x + 4,9953 80,0 75,0 La retta verde è detta retta di Peso 70,0 65,0 regressione 60,0 𝛽 55,0 50,0 150,0 160,0 170,0 180,0 190,0 200,0 (in particolare questa è una retta di Altezza regressione lineare semplice)  Regressione lineare 𝛽 intercetta (4,9953) 90,0 85,0 y = 0,4075x + 4,9953 80,0 è il valore in ordinata del punto di 75,0 intersezione tra la retta e l’asse Peso 70,0 65,0 delle ordinate 60,0 𝛽 55,0 50,0 150,0 160,0 170,0 180,0 190,0 200,0 Altezza Regressione lineare L’intercetta è un valore che tendenzialmente sarà sempre positivo L’intercetta però può essere tolta e possiamo decidere quindi di stimare un modello che ha inizio dal punto di origine (0,0) → 𝑌 = 𝛽 +𝛽 𝑋 + 𝛽 𝑋 + ⋯+𝛽 𝑋 + 𝜀 → 𝑌 = 𝛽 𝑋 + 𝛽 𝑋 + ⋯+ 𝛽 𝑋 + 𝜀  Regressione lineare 𝛽 coefficiente di regressione 90,0 (0,4075) 85,0 y = 0,4075x + 4,9953 80,0 misura il cambiamento medio nella 75,0 𝛽 variabile dipendente per una unità Peso 70,0 65,0 di incremento nella variabile 60,0 dipendente 55,0 50,0 150,0 160,0 170,0 180,0 190,0 200,0 All’aumentare dell’altezza di 1 Altezza centimetro il peso aumenta in media di 0,4075kg Regressione lineare I coefficienti di regressione possono assumere valori: Positivi: all’aumento unitario del regressore corrisponde un aumento della variabile dipendente Negativi: all’aumento unitario del regressore corrisponde una diminuzione della variabile dipendente Regressione lineare Interpretazione del coefficiente di regressione quando il regressore è una variabile dicotomica: Il coefficiente di regressione misura la differenza media della variabile dipendente tra i due gruppi Regressione lineare Esempio: Peso=75.0+4.7*Sesso Prima di tutto dobbiamo aver stabilito un livello di riferimento per la variabile qualitativa (per esempio il sesso Femminile) prima di stimare il modello 4.7 significa che in media gli uomini pesano 4.7kg in più delle donne Regressione lineare Quando il regressore è di tipo qualitativo policotomico o ordinale dobbiamo trasformarlo in tante variabili dicotomiche quante sono il numero-1 delle categorie della variabile qualitativa N-1 perché una categoria è utilizzata come riferimento Un’unica variabile sarà trasformata in N-1 variabili e avremo N-1 coefficienti Regressione lineare Esempio: Peso – mangiare frutta (mai, saltuariamente, tutti i giorni) Mangiare frutta: Mai→ livello di riferimento (non ha coefficiente) Saltuariamente→ se si 1 altrimenti 0 Tutti i giorni→ se si 1 altrimenti 0 Peso=75.0-1.5*Saltuariamente-2.7*TuttiIGiorni Regressione lineare Peso=75.0-1.5*Saltuariamente-2.7*TuttiIGiorni Se un soggetto mangia frutta saltuariamente peserà in media 1.5 kg in meno rispetto a chi non la mangia mai Se un soggetto mangia frutta tutti i giorni peserà in media 2.7 kg in meno rispetto a chi non la mangia mai  Regressione lineare Peso=5.0-1.5*Saltuariamente- Mai 2.7*TuttiIGiorni+0.45*Altezza Saltuariamente 5 Tutti i Le variabili qualitative traslano 5-1.5=3.5 giorni solamente la retta verso l’alto o 5-2.7=2.3 verso il basso I coefficienti vanno a sommarsi/sottrarsi all’intercetta Regressione lineare Esempio: Modello stimato utilizzato per scopo predittivo Peso=5.0 +0.45*Altezza -2.3*MangiareDolci- 0.3*MangiareFruttaSaltuariamente -1.0*MangiareFruttaSempre Per ogni nuovo soggetto posso dire quanto dovrebbe pesare, con un certo grado di errore, senza farlo realmente basta che io sappia la sua altezza e le abitudini alimentari Regressione lineare Esempio: Modello stimato utilizzato per scopo predittivo Peso=5.0 +0.45*Altezza -2.3*MangiareDolci- 0.3*MangiareFruttaSaltuariamente -1.0*MangiareFruttaSempre Il nuovo pz è alto 167.3cm non mangia mai dolci ma mangia frutta tutti i giorni →il suo peso è P=5.0+0.45*167.3-2.3*0-0.3*0-1.0*1=79,3kg Regressione lineare 𝜀 errore È la distanza tra i punti osservati e la retta (questa distanza è detta anche scarto o residuo) I coefficienti di regressione vengono stimati in modo che sia minimizzata la somma di questi errori Regressione lineare Una volta stimato il modello questo parametro non è più presente (non è un valore stimato) Ma è dato dalla differenza tra il valore di Y osservato e Y predetto (𝑌) Regressione lineare Quando stimiamo l’intercetta e i coefficienti di regressione dobbiamo fare un test di ipotesi per capire se il coefficiente è significativo oppure no Ipotesi nulla: 𝛽 = 0 Ipotesi alternativa: 𝛽 ≠ 0 Regressione lineare Se non rifiutiamo l’ipotesi nulla dovremmo scartare quella data variabile dal set dei regressori Con i dati da noi ottenuti non siamo in grado di ottenere come significativa la relazione tra quella variabile e l’outcome Regressione lineare intercetta e regressori Stime dei coefficienti p-value del test Non significativi Regressione lineare Come selezioniamo le variabili da inserire nel modello? Nella pratica clinica selezioniamo le variabili da inserire nel modello secondo i seguenti criteri: Variabili che risultano associate/differenti/correlate all’analisi univariata Regressione lineare Come selezioniamo le variabili da inserire nel modello? Nella pratica clinica selezioniamo le variabili da inserire nel modello secondo i seguenti criteri: Variabili che non risultano significative rispetto all’α stabilito ma che comunque non lo superano di molto Es. α=0.05 →prendo tutte quelle con pf(w,x), e > 0, il wj peso deve essere incrementato per ridurre l’errore – Se y