Efficient construction of
regression trees with
Range and Region
Splitting
Yasuhiko Morimoto, Hiromu Ishii, Shinichi Morishita
(1997)
Gruppo 11:
Paola Belingheri
Maria Giulia Casanova
Alice Spadazzi
Sistemi Informativi per le
Decisioni L-S
Prof. Marco Patella
Costruzione efficiente di alberi di regressione
con splitting in intervallo e regione
Obiettivo:
Predire il valore di un attributo numerico tramite albero di
regressione binario in maniera più efficiente rispetto allo split
con soglia
Indice
1. Introduzione al Range & Region Splitting
2. Possiamo calcolare la regione R ottimale ad
ogni split in modo efficiente?
3. Il region-splitting permette di ottenere un albero
di regressione più preciso?
4. Conclusioni
5. Applicazioni pratiche
1. Introduzione al Range & Region Splitting
Esempio
Il paziente deve fare la dieta?
Albero di regressione
binario
0,85 x 22 x height 2 < weight < 1,15 x 22 x height 2
relazione non-lineare fra gli attributi!
• Costruzione dell’albero di regressione con un test di “Split ad ogni nodo
rettangoli!
• Rischio di overfitting
• La ghigliottina non è efficiente
1. Introduzione al Range & Region Splitting
Un modo più furbo
Definizioni:
• Attributi condizionali: numerici, usati per predire
• Attributo obiettivo A: numerico, il valore da predire
• Scarto quadratico medio (MSE):
valore effettivo di
A
valore predetto = valore medio
delle tuple presenti nella foglia in
cui finisce t
2
 tA   D 
lea f ( t )
min
tuple
tD '
D'
test set
Domande:
1. Possiamo calcolare in modo efficiente la regione che minimizza MSE?
2. Il region-splitting permette di ottenere un albero di regressione più preciso?
1. Introduzione al Range & Region Splitting
Vogliamo
predire il di
valore
dell’indice
SP500
Tre tipologie
regioni
ammissibili:
Attributi:
1.
anno
2.
mese
3.
settimana
4.
BPS: US$/Pound
5.
GDM: US$/Mark
(N Gold = N GDM)
6.
Yen: US$/yen
• Pixel: intersecando
gli N bucket ottengo
N2 pixel
7.
TB3M
8.
TB30Y
• Selezione di due
attributi condizionali:
Gold e GDM
Dw
• Divisione in N
bucket equi-width
Valori
9. Gold: US$/oncia
distribuiti
10. SP500
“meglio”!
Din
Dout
Indice
1.Introduzione al Range & Region
Splitting
2.Possiamo calcolare la regione R
ottimale ad ogni split in modo
efficiente?
3.Il region-splitting permette di ottenere
un albero di regressione più preciso?
4.Conclusioni
5.Applicazioni pratiche
2 - Possiamo calcolare la regione R ottimale ad ogni split
in modo efficiente?
• Regioni ammissibili: tutte le combinazioni di N x N pixel
Esempio: 1010
NN
Dout
= 10.000.000.000 regioni possibili
Din
• Selezionare tra queste la regione che minimizza MSE(R):
  tA   D  
w
in
min
tDinw
2

  tA   D  
w
out
2
w
tDout
Dw
|Din| + |Dout|
• Varianza Interclasse:
max
V ( R)  D  D    D
w
in
max V(R)
w
in
w

2
D
w
out
 D   D 
w
out
min MSE(R)
w
2
2 - Possiamo calcolare la regione R ottimale ad ogni split in modo efficiente?
Trasformazione STAMP POINT
max
V ( R)  D  D    D
w
in
w
in
w

2
D
 
1. Poniamo t A = t A   D w
w
out
 D   D 
w
out
w
Dout
 
2.  D w  0
3. V ( R)  D w
in
 D 
w
in
2
D
4. Poniamo x = Dinw , y =
5.
w
out
 D 
 tA
tDwin
1 
1
V ( R)  y 2  
  f  x, y 
 x M x
w
out
,M=
2
Dw
Din
2
2 - Possiamo calcolare la regione R ottimale ad ogni split in modo efficiente?
1 
1
V ( R)  y 2  
  f  x, y 
x
M

x


V(R)
È una funzione CONVESSA per 0 ≤ x ≤ M
calcolo x e y
y
x
2 - Possiamo calcolare la regione R ottimale ad ogni split in modo efficiente?
Algoritmo Hand-Probing
• max V(R)
y
• in una regione convessa
• quindi
θ
x
il punto di max
corrisponde ad un punto
(x,y) che si trova sulla
frontiera dell’inviluppo
convesso:
la regione minima che
contiene tutti i punti
nel piano
Come trovare i punti dell’inviluppo?
HAND PROBING
NN punti da “tastare”
2 - Possiamo calcolare la regione R ottimale ad ogni split in modo efficiente?
Branch-and-Bound Guidato
• Branch-and-bound :
algoritmo che permette di individuare ricorsivamente la “direzione più
furba” in cui spostarsi alla ricerca della soluzione ottima
scarta a priori le soluzioni ammissibili ma non migliorative
dell’ottimo corrente
Guidato da:
presi due punti P1 e P2 sulla frontiera e
Q intersezione delle tangenti all’inviluppo
in P1 e P2
per ogni punto P interno al triangolo P1P2Q
V(P) ≤ V(Q)
se V(Q) ≤ Vmax corrente,
allora pota tutto il triangolo
altrimenti esplora il vertice più esterno del triangolo (P3)
2 - Possiamo calcolare la regione R ottimale ad ogni split in modo efficiente?
Algoritmo Branch-and-Bound
─ Vmax := 0;
─ Per ogni intervallo I = {Pi,Pj}
Vmax := max {V(Pi),V(Pj), Vmax}
if V(Q) ≤ Vmax allora pota I
else trova il vertice più esterno di I e aggiorna Vmax
Vmax aumenta mentre I si restringe ad
ogni iterazione
Complessità computazionale:
• O(N4 log N): rettilineare
• O(N3 log N): rettangolare
• O(N3 log N): x-monotona
Indice
1.Introduzione al Range & Region
Splitting
2.Possiamo calcolare la regione R
ottimale ad ogni split in modo
efficiente?
3.Il region-splitting permette di
ottenere un albero di regressione più
preciso?
4.Conclusioni
5.Applicazioni pratiche
3 - Il region-splitting permette di ottenere un albero di
regressione più preciso?
• Alberi di regressione più larghi potrebbero ridurre MSE ma…rischio di overfitting!
• Fino a che punto espandere l’albero?
Inizio
Selezione della regione in cui suddividere le tuple
della foglia corrente per ottenere il nuovo nodo di
regression tree trovando la regione che massimizza V(R)
mediante l’algoritmo “Guided Branch-and-Bound”
2






t
A


D

leaf ( t )
tDw
Dw
Calcolo del guadagno di
splitting, fatto da
MSE nodo padre - MSE nodi figli Guadagno
sufficiente
Guadagno
insufficiente
Creazione di due sotto-alberi:
uno con il dataset “interno alla regione
e l’altro con il dataset “esterno” ad essa
(Avvia due ricorsioni)
  tA   D  
w
in
Fine
tDinw
2

  tA   D  
w
out
w
tDout
Dw
2
3 - Il region-splitting permette di ottenere un albero di regressione più preciso?
 tA   D 
2
lea f ( t )
MSE nodo padre - MSE nodi figli ≥ α x
tDw
Dw
parametro di pruning
generiamo una serie di alberi per diversi valori di α e troviamo il migliore
MSE
relativo
α = 0,0002 buon valore!
α pruning
3 - Il region-splitting permette di ottenere un albero di regressione più preciso?
Anche la pixel-density (n° medio di tuple per pixel) influenza MSE…
MSE
relativo
α pruning
…una pixel-density fra 5 e 10 genera minimizza MSE
In sintesi :
• un buon α e una buona pixel-density generano alberi di regressione
più precisi e compressi
• le regioni rettilineari generano gli alberi più precisi
Indice
1.Introduzione al Range & Region
Splitting
2.Possiamo calcolare la regione R
ottimale ad ogni split in modo
efficiente?
3.Il region-splitting permette di ottenere
un albero di regressione più preciso?
4.Conclusioni
5.Applicazioni pratiche
4 - Conclusioni
1. Possiamo trovare relazioni non-lineari fra gli attributi
2. Possiamo ridurre MSE in media del 10% (in alcuni casi fino al 34%)
ma…
3. L’algoritmo è sensibile al numero di attributi (pressoché lineare nel
quadrato del numero di attributi)
N.B. Costruendo l’albero su un training set “scelto bene” posso rendere
ragionevole il costo computazionale
Indice
1.Introduzione al Range & Region
Splitting
2.Possiamo calcolare la regione R
ottimale ad ogni split in modo
efficiente?
3.Il region-splitting permette di ottenere
un albero di regressione più preciso?
4.Conclusioni
5.Applicazioni pratiche
5 – Applicazioni pratiche:
L’età dell’abalone
Abalone: mollusco che vive nei mari della Tasmania e della costa nord dell’Islanda
Studio dell’età: affettare la conchiglia del mollusco, colorarla e esaminare al microscopio
il numero di anelli presenti
lungo e noioso
Usiamo il range-region splitting su altri attributi:
Name
Sex
Diameter
Height
Whole weight
Shucked weight
Viscera weight
Shell weight
Rings
Data Type
nominal
continuos
continuos
continuos
continuos
continuos
continuos
integer
Measure
M, F and I (infant)
mm
mm
mm
grams
grams
grams
Description
Longest schell measurement
perpendicular to lenght
with meat in shell
whole abalone
weight of meat
gut weight (after bleeding)
plus 1,5 gives the age in years
Fonte: http://www.cs.toronto.edu/~delve/data/abalone/desc.html
5 – Applicazioni pratiche:
I bracci meccanici del Robot Puma
Predire l’accelerazione angolare del braccio meccanico del Robot Puma