III JORNADAS DE DATA MINING

EN EL MARCO DE LA MAESTRÍA EN DATA MINING DE LA UNIVERSIDAD AUSTRAL

VISIÓN DE MODELOS PREDICTIVOS COMO RANKEADORES Gustavo Denicolay, Socio Gerente Adaptive, Profesor Maestría en Data Mining de la Universidad Austral.

IAE - Pilar, 12 y 13 de agosto de 2008

1

Visión de modelos predictivos

como rankeadores

2

•Existe alguna jerarquía entre las tres tareas ?

•Rankear: dados un conjunto de nuevos registros, ordenar a los positivos antes que los negativos.

•Estimación de Probabilidad: dado un registro nuevo asignarle la probabilidad que sea positivo.

•Clasificación: dado un nuevo registro, asignar la etiqueta positivo o de negativo

Motivación

3

Mejor clasificación no implica mejor ranking

Motivación

3 errores ranking

3 errores clasificación

6 errores ranking

2 errores clasificación, MEJOR

Pos Neg

Pos Neg

4

Mejor probabilidades no implica mejor ranking

Motivación

0 errores ranking

0.25 mean squared error

1 errores ranking

0.125 mean squared error, MEJOR0.5

1

01

0.5 0

5

Motivación

•Si el dataset es muy desbalanceado, es trivial obtener un clasificador con gran accuracy asi como asignar probabilidades con un mean squared error muy bajo.

SIN EMBARGO

no es trivial obtener un buen rankeador.

Un buen rankeador captura la esencia de

SEPARAR las clases.

6

Rankear cumple un rol fundamental.

Motivación

•Un mejor rankeador implica un mejor clasificador y un una mejor estimación de probabilidades.

•Una mejor estimación de probabilidades no implicaun mejor rankeador . Pero utilizando la Cascara Convexa de la Curva ROC y reparando concavidades de puede mejorar la estimacion de probabilidades.

7

Curva ROC

8

ROC : Receiver Operating Characteristic

•El término se comenzó a utilizar luego del ataque japones a Pearl Harbor en 1941 para incrementar la exactitud en la detección de aviones japoneses a partir de las señales de radar.

• En 1998 Foster Provost, Tom Fawcett y Ron Kohavi publican “The case against Accuracy Estimation for comparing Induction Algorithms”

• Hoy, 2008, muchos practicantes del data mining aun no utilizan regularmente la curva ROC para comparar algoritmos y continuan utilizando la metrica de accuracy ...

• En 2003 Charles X. Ling, Jin Huang, Harry Zhang demuestran formalmente la superioridad del la métrica AUC sobre la métricaAccuracy “AUC: a Statistically Consistent and more DiscriminatingMeasure than Accuracy ”

9

Curva ROC

de

Predicados

10

0

1

2

3

0 1 2 3

var a

var

b

Negativos

neg= 400

11

0

1

2

3

0 1 2 3

var a

var

b

Positivos

pos= 300

12

0

1

2

3

0 1 2 3

var a

var

b Negativos

Positivos

13

0

1

2

3

0 1 2 3

var a

var

b Negativos

Positivos

Predicado 1 = (0.5 < a < 2) and (1.5 < b < 3 )

Pos=113

Neg = 75

14

0

50

100

150

200

250

300

0 50 100 150 200 250 300 350 400

Negativos

Posi

tivos P 1

Azar

15

0

1

2

3

0 1 2 3

var a

var

b Negativos

Positivos

Predicado 2 = (1<a<3) and (1<b<3) and (a+b >4)

Pos=150

Neg = 0

16

0

50

100

150

200

250

300

0 50 100 150 200 250 300 350 400

Negativos

Posi

tivos P 1

Azar

P 2

17

0

1

2

3

0 1 2 3

var a

var

b Negativos

Positivos

18

Pos = 225

Neg = 0

Pos = 75

Neg = 100

Pos = 0

Neg = 300

19

PosNegRegion

2250Rojo

75100Verde

0300Azul

PosNegRegion

0300Azul

75100Verde

2250Rojo

300400Azul

00Vacio

Acum Pos

AcumNeg

300400Universo

300100Verde

2250Rojo

Construcción de la Curva ROC

20

0

50

100

150

200

250

300

0 50 100 150 200 250 300 350 400

Negativos

Posi

tivos Modelo

Azar

P1

21

Curva ROC

de

Arbol de Decisión

22

0

1

2

3

0 1 2 3

var a

var

b Negativos

Positivos

23

var a

Pos=0Neg=200

var b

Pos=75Neg=0

var b

Pos=75Neg=100

Pos=0Neg=100

var a Pos=150Neg=01

2 3

4

5

24

30020001002

30040002001

300100751003

22507504

150015005

0000Vacio

PosAcum

Neg Acum

PosNegHoja

25

0

50

100

150

200

250

300

0 50 100 150 200 250 300 350 400

var a

var

b Arbol

Azar

26

Construccion

Curva ROC

Rankeador Generico

27

+ + + - + + - + - + - - + - - - + - - - - -

1. Empezar en (0,0)

2. Mientras existanpuntos por leer, iral siguiente punto del ranking

1. Si es positivo, moverse arriba

2. Si es negativo, moverse a la derecha 0

1

2

3

4

5

6

7

8

9

0 1 2 3 4 5 6 7 8 9 10 11 12 13

28

Curva ROC

caso

clases completamente separables

29

DataSet

0

1

2

3

0 1 2 3

var A

var

B Neg

Pos

30

0

10

20

30

40

50

60

0 100 200 300 400 500 600 700 800

31

Curva ROC

un caso mas difuso

32

0

0.5

1

1.5

2

2.5

3

-2 -1 0 1 2 3 4 5 6

var a

var

b

NegNeg400 datosNormal( 1, 1 )

33

0

1

2

3

-2 -1 0 1 2 3 4 5 6

var a

var

b

PosPos300 datosNormal( 3, 1 )

34

0

0.5

1

1.5

2

2.5

3

-2 -1 0 1 2 3 4 5 6

var a

var

b Neg

Pos

35

0

30

60

90

120

150

180

210

240

270

300

0 40 80 120 160 200 240 280 320 360 400

Neg

Pos ROC optima

Azar

36

Comparacion de Modelos

utilizando

curvas ROC

37

0

50

100

150

200

250

300

0 50 100 150 200 250 300 350 400

A

B

El modelo A es mejor que el modelo B

A domina a B

38

0

50

100

150

200

250

300

0 50 100 150 200 250 300 350 400

A

C

El modelo A es mejor que el modelo C en cierta region.

C es mejor que A en otra region.

39

•El modelo A es bueno detectando los positivos.

•El modelo C es bueno detectando los negativos.

•La diferencia entre los modelos A y C se debe a que los algoritmos que los generaron buscaron de forma distinta en el espacio de busqueda de todos los modelos.

•Ningun modelo es superior al otro para todos los puntos.

40

La Cascara Convexa

( Convex Hull )

41

0

50

100

150

200

250

300

0 50 100 150 200 250 300 350 400

A

C

H

42

Clasificador Hibrido H

H es tangente a las curvas A y CNo necesariamente H es paralela a la recta del azar.

Dado un umbral que implique un corte a la curva ROC en el intervalo H, se determina p de la siguiente forma

H

d1 d2

d1

d1 + d2p=

A C

punto de corte

h

43

Clasificador Hibrido H

Supongamos un punto h, del segmento H, que esta a distancia p del punto de tangencia con A ( y a distancia 1-p de punto de tangencia con C )

H(h) = Dado un nuevo registro a clasificargenerar una variable aleatoria uniforme entre 0 y 1Si es menor o igual a p invocar al clasificador “A”En caso contrario invocar al clasificador “C”

44

Relacion

metrica de clasificacion Accuracy

y

curvas ROC

45

Dado un Clasificador, la metrica Accuracy es el porcentaje de registros correctamente clasificados.

El accuracy determina un sentido en el plano de las rectas paralelas a la recta “positivos = negativos” que solamente coincide con el sentido de la recta del azar en el unico caso que el dataset este perfectamente balanceado ( # registros positivos = # registros negativos )

46

0

50

100

150

200

250

300

0 50 100 150 200 250 300 350 400

A

B

47

y si las clases estan mas desbalanceadas

que sucede ?

48

0

50

100

150

200

250

300

0 200 400 600 800 1000 1200 1400 1600

49

En el caso de las clases desbalanceadas se observa la

GRAN FALLA de la metrica accuracy, producto de hacer el

cociente entre positivos y negativos.

50

Estimacion de Probabilidad

y

Cascara Convexa

de la curva ROC

51

•Los Arboles de Decision generan una buena asignacion de probabilidades.

•Naive Bayes, Support Vector Machines y AdaBoost no generan una estimacion de probabilidad, y deben CALIBRADOS.

La CALIBRACION de un clasificador se puede lograr entre otros metodos por:•Estimacion Parametrica

•Binning

•Regresion Isotonica no parametrica. algoritmo Pool Adjacent ViolatorsPAV

52

La CALIBRACION por medio el algoritmo e Pool Adjacent Violators PAV es EQUIVALENTE a reparar concavidades de una curva ROC utilizando la ConvexHull. ( Tom Fawcett , 2007 )

Dado un dataset, y un clasificador, a partir del ranking, reparando concavidades en su Curva ROC, se RECALIBRAN las probabilidades, maximiza el AUC (area bajo la curva ROC) y maximiza el mean squared error de las probabilidades

para cualquier eleccion de umbral de clasificacion y costos de misclasificacion.