Evaluación del Aprendizaje
César Hervás Martínez
José Hernández Orallo
• Técnicas estadísticas para el análisis de experimentos.
• ¿Cómo se compara? Evaluación de algoritmos, cuándo las diferencias son
significativas.
•Análisis ROC para clasificadores.
• ¿Qué se mide? Métricas de evaluación
1
Madrid, 6 de mayo de 2004.
Evaluación de Clasificadores en
Minería de Datos:
Análisis ROC
José Hernández Orallo
Dpto. de Sistemas Informáticos y Computación,
Universidad Politécnica de Valencia,
[email protected]
Madrid, 6 de mayo de 2004.
2
Organización
• Introducción. La Clasificación y su Evaluación
• Evaluación Sensible a la Distribución y al Coste
• Análisis ROC de Clasificadores “crisp”
• Análisis ROC de Clasificadores “soft”
• La Métrica AUC: el área bajo la curva ROC
• Relación entre AUC y Error. Elección del umbral
• Aplicaciones
• Extensión a Más de Dos Clases
• Conclusiones
3
Introducción. La Clasificación y su Evaluación
• Clasificación.
– Una de las tareas más importantes en minería de
datos.
– Obtener un modelo, patrón o función que discrimine
entre dos o más clases excluyentes.
• Evaluación de la clasificación.
– Medida tradicional para evaluar clasificadores:
• Error (tb. inversamente accuracy): porcentaje de instancias
mal clasificadas (respecto al conjunto de test o utilizando
validación cruzada / bootstrapping).
4
Introducción. La Clasificación y su Evaluación
• Un clasificador permite asistir en la toma
de decisiones (entre diferentes acciones).
¿Podemos permitirnos tomar decisiones
de una manera no científica?
• Ésta es la pregunta que hacen:
– Swets, J.A., Dawes, R.M., & Monahan, J. (2000).
“Better decisions through science” Scientific
American, 283, 82-87.
5
Evaluación Sensible a la Distribución y al Coste
• Evaluación Sensible a la Distribución:
– No siempre todas las clases tienen la misma proporción (no
están balanceadas, 50% de cada)
• Ejemplo:
– Tenemos varios clasificadores c1, c2, c3 que predicen si se ha
de abrir o cerrar la válvula del módulo de refrigeración de la
central nuclear de Cofrentes.
– Para evaluar los clasificadores usamos un conjunto de datos
obtenido en el último mes, donde un operario ha decidido en
cada momento si se había de abrir o cerrar la fórmula.
• 100.000 ejemplos, de los cuales 99.500 son de la clase “Cerrar”
y 500 son de la clase “Abrir”.
– Digamos que el clasificador c2 predice siempre “Cerrar”
(clasificador trivial).
• Error de c2: 0,5%.
¿Es éste un buen clasificador?
6
Evaluación Sensible a la Distribución y al Coste
• Matriz de confusión/contingencia (p.ej. para el conjunto de test):
Real
Predicho
•
abrir (p)
cerrar (n)
ABRIR (P)
TP
FP
CERRAR (N)
FN
TN
Diagonal de
los aciertos
A partir de aquí, se han definido una serie de métricas:
– Pr(P|p) ≈ True Positive Rate: TPR = TP / (TP + FN). (“recall” o ”sensitivity” o “positive
accuracy”).
– Pr(N|p) ≈ False Negative Rate: FNR = FN / (TP + FN). (“positive error”)
– Pr(N|n) ≈ True Negative Rate: TNR = TN / (TN + FP). (”specificity” o ”negative accuracy”).
– Pr(P|n) ≈ False Positive Rate: FPR = FP / (TN + FP). (“negative error”)
– Pr(p|P) ≈ Positive Predictive Value: PPV = TP / (TP + FP). (”precision”).
– Pr(n|N) ≈ Negative Predictive Value: NPV = TN / (TN + FN).
– Macro-average = MEDIA(TPR, TNR). (La media puede ser aritmética, geométrica u otra)
– BREAK-EVEN= (Precision + Recall) / 2 = (PPV + TPR) / 2
– F-MEASURE= (Precision * Recall) / BREAK-EVEN = 2*PPV*TPR / (PPV + TPR)
7
Evaluación Sensible a la Distribución y al Coste
• Ejemplo: (conjunto de test de 100.000 instancias)
Real
Precision
Especificidad
Recall
Sensitividad
Pred
Real
Real
c1
abrir
cerrar
c2
abrir
cerrar
c3
abrir
cerrar
ABRIR
300
500
ABRIR
0
0
ABRIR
400
5400
CERRAR
200
99000
CERRAR
500
99500
CERRAR
100
94100
ERROR: 0,7%
ERROR: 0,5%
ERROR: 5,5%
TPR= 300 / 500 = 60%
FNR= 200 / 500 = 40%
TNR= 99000 / 99500 = 99,5%
FPR= 500 / 99500 = 0,5%
PPV= 300 / 800 = 37,5%
NPV= 99000 / 99200 = 99,8%
TPR= 0 / 500 = 0%
FNR= 500 / 500 = 100%
TNR= 99500 / 99500 = 100%
FPR= 0 / 99500 = 0%
PPV= 0 / 0 = INDEFINIDO
NPV= 99500 / 10000 = 99,5%
TPR= 400 / 500 = 80%
FNR= 100 / 500 = 20%
TNR= 94100 / 99500 = 94,6%
FPR= 5400 / 99500 = 5,4%
PPV= 400 / 5800 = 6,9%
NPV= 94100 / 94200 = 99,9%
Macromedia= (60 + 99,5 ) / 2 =
Macromedia= (0 + 100 ) / 2 =
Macromedia= (80 + 94,6 ) / 2 =
79,75%
50%
¿Qué clasificador es mejor?
87,3%
8
Evaluación Sensible a la Distribución y al Coste
• Evaluación sensible al coste:
– En muchas situaciones todos los errores producidos por un modelo
predictivo no tienen las mismas consecuencias:
• Ejemplo: Dejar cerrada una válvula en una central nuclear cuando es
necesario abrirla, puede provocar una explosión, mientras que abrir una
válvula cuando puede mantenerse cerrada, puede provocar una parada.
– Matriz de costes:
Predicho
Real
abrir
cerrar
ABRIR
0
100€
CERRAR
2000€
0
– Lo importante no es obtener un “clasificador” que yerre lo menos
posible sino que tenga un coste menor.
– A partir de la matriz se calcula el coste de un clasificador.
• Los clasificadores se evalúan con dichos costes.
• Se selecciona el clasificador de menos coste.
9
Evaluación Sensible a la Distribución y al Coste
Matrices de confusión
• Ejemplos:
Real
Pred
Real
Real
c1
abrir
cerrar
c2
abrir
cerrar
c3
abrir
cerrar
ABRIR
300
500
ABRIR
0
0
ABRIR
400
5400
CERRAR
200
99000
CERRAR
500
99500
CERRAR
100
94100
Real
Predicho
abrir
cerrar
ABRIR
0
100€
CERRAR
2000€
0
Matriz de
coste
Matrices resultado
c1
abrir
cerrar
c2
abrir
cerrar
c3
abrir
cerrar
ABRIR
0€
50.000€
ABRIR
0€
0€
ABRIR
0€
540.000€
CERRAR
400.000€
0€
CERRAR
1.000.000€
0€
COSTE TOTAL: 450.000€
COSTE TOTAL: 1.000.000€
CERRAR 200.000€
0€
10
COSTE TOTAL: 740.000€
Evaluación Sensible a la Distribución y al Coste
• ¿De qué depende el coste final?
– Para dos clases. Depende de un contexto (o skew):
• El coste de los falsos positivos y falsos negativos: FPcost y
FNcost
• El porcentaje de ejemplos de la clase negativa respecto de
ejemplos de la clase positiva. (Neg / Pos).
• Se calcula: (para el ejemplo anterior)
FPcost
FNcost

100
2000

1
Neg
20
Pos

99500
 199
slope 
1
·199  9 ,95
20
500
– Para dos clases, el valor “slope” es suficiente para
determinar qué clasificador será mejor.
Clasifi. 1: FNR= 40%, FPR= 0,5%
Coste Unitario =
1 x 0,40 + 9,95 x 0,005 = 0,45
Clasifi. 2: FNR= 100%, FPR= 0%
Coste Unitario =
1 x 1 + 9,95 x 0 = 1
Clasifi. 3: FNR= 20%, FPR= 5,4%
Coste Unitario =
1 x 0,20 + 9,95 x 0,054 = 11
0,74
Análisis ROC de Clasificadores “crisp”
• El clasificador con menor error no es, frecuentemente,
el mejor clasificador.
• El contexto (la distribución de clases y los costes de
cada error) determinan la bondad de los clasificadores.
• PROBLEMA:
– En muchas aplicaciones, hasta el momento de aplicación, no
se conoce la distribución de clases y/o es difícil estimar la
matriz de costes. P.ej. un clasificador de spam.
– Pero los modelos se aprenden antes generalmente.
• Análisis ROC (Receiver Operating Characteristic).
– Usado por primera vez para evaluar radares en la 2ª guerra mundial,
posteriormente se usó para el análisis de respuesta de transistores,
se desarrolló fundamentalmente para aplicaciones de diagnóstico
médico a partir de 1970 y comienza a popularizarse a finales de los
12
90 en minería de datos.
Análisis ROC de Clasificadores “crisp”
• El espacio ROC
– Se normaliza la matriz de confusión por columnas:
TPR, FNR TNR, FPR.
Real
Pred
abrir
cerrar
ABRIR
400
12000
CERRAR
100
87500
Real
Pred
abrir
cerrar
ABRIR
0,8
0,121
CERRAR
0,2
0,879
Espacio ROC
TPR= 400 / 500 = 80%
FNR= 100 / 500 = 20%
TNR= 87500 / 99500 = 87,9%
FPR= 12000 / 99500 = 12,1%
True Positives
1,000
0,800
0,600
0,400
0,200
0,000
0,000
0,200
0,400
0,600
False Positives
0,80013 1,000
Análisis ROC de Clasificadores “crisp”
• Espacio ROC: buenos y malos clasificadores.
1
1
1
TPR
TPR
TPR
0
0
FPR
1
0
0
FPR
1
0
0
FPR
1
• Buen clasificador.
• Mal clasificador.
• Mal clasificador
– Alto TPR.
– Bajo FPR.
– Bajo TPR.
– Alto FPR.
(en realidad).
14
Análisis ROC de Clasificadores “crisp”
• La Curva ROC. “Continuidad”.
ROC diagram
1
 Dados dos clasificadores:
 Podemos construir cualquier
clasificador “intermedio”
ponderando aleatoramiente
los dos clasificadores (con
más peso a uno u otro).
TPR
0
0
FPR
1
 Esto en realidad crea un
“continuo” de clasificadores
entre cualesquiera dos
clasificadores.
15
Análisis ROC de Clasificadores “crisp”
• La Curva ROC. Construcción.
 Dados varios clasificadores:
ROC diagram
1
La diagonal
muestra por
tanto la peor
situación posible.
TPR
0
0
FPR
1
 Construimos el “casco convexo”
(convex hull) de sus puntos
(FPR,TPR) además de los dos
clasificadores triviales (0,0) y
(1,1).
 Los clasificadores que caen
debajo de la curva ROC se
descartan.
 El mejor clasificador de los que
quedan se seleccionará en el
momento de aplicación…
Podemos descartar los que están por debajo porque no hay ninguna combinación
16
de distribución de clases / matriz de costes para la cual puedan ser óptimos.
Análisis ROC de Clasificadores “crisp”
• En el contexto de aplicación, elegimos el clasificador
óptimo entre los mantenidos. Ejemplo 1:
Contexto:
100%
FPcost
FNcost
true positive rate
80%
60%
Neg
40%
Pos

20%
slope 
 1
 4
4
2
2
0%
0%
20%
40%
60%
80%
100%

false positive rate

2
17
Análisis ROC de Clasificadores “crisp”
• En el contexto de aplicación, elegimos el clasificador
óptimo entre los mantenidos. Ejemplo 2:
Contexto:
100%
FPcost
FNcost
true positive rate
80%
60%
Neg
40%
Pos

20%
slope 
 1
 4
4
8
0%
0%
20%
40%
60%
80%
100%

false positive rate

8
18
 .5
Análisis ROC de Clasificadores “crisp”
• ¿Qué hemos aprendido?
– La optimalidad de un clasificador depende de la
distribución de clases y de los costes de los errores.
– A partir de este contexto se puede calcular una
inclinación (“slope” o “skew” ) característica del
contexto.
• Si sabemos este contexto, podemos seleccionar el mejor
clasificador, multiplicando la matriz de confusión por la
matriz de coste.
• Si desconocemos el contexto de aplicación en el momento
de generación, usando el análisis ROC podemos elegir un
subconjunto de clasificadores, entre los cuales seguro
estará el clasificador óptimo para cualquier contexto posible,
cuando éste se conozca.
¿Podemos ir más allá?
19
Análisis ROC de Clasificadores “soft”
• Clasificadores “crisp” y “soft”:
– Un clasificador “crisp” (discreto) predice una clase entre las
posibles.
– Un clasificador “soft” (probabilístico) predice una clase, pero
acompaña un valor de fiabilidad a cada predicción.
• La mayoría de métodos de aprendizaje en minería de datos
pueden acompañar las predicciones con estos valores de
fiabilidad.
• Un tipo especial de clasificador “soft” son los
estimadores de probabilidad.
– En vez de predecir “a”, “b” o “c”, dan estimaciones de
probabilidad para “a”, “b” o “c”, es decir, “pa”, “pb” y “pc”.
Ejemplo:
• Clasificador 1: pa= 0.2, pb= 0.5 y pc= 0.3.
• Clasificador 2: pa= 0.3, pb= 0.4 y pc= 0.3.
– Los dos predicen b, pero el clasificador 1 está más “seguro”.20
Análisis ROC de Clasificadores “soft”
• “Rankers”:
– Cuando tenemos un estimador de probabilidad para un
problema de dos clases:
• pa = x, entonces pb = 1  x.
– Sólo es necesario especificar la probabilidad de una clase.
– Llamemos a una clase 0 (neg) y a la otra clase 1 (pos).
– Un ranker es un clasificador suave que proporciona un valor
entre 0 y 1 de la probabilidad de una de las clases. Este valor se
denomina también “score” y determina si está más cerca de la
clase 0 o de la clase 1.
– Ejemplos:
• Probabilidad de que un cliente compre un producto.
• Probabilidad de que un correo sea spam.
• ...
21
Análisis ROC de Clasificadores “soft”
• Curva ROC de un Clasificador “soft”:
– Un clasificador “soft” se puede convertir en un
clasificador “crisp” utilizando un umbral.
• Ejemplo: “si score > 0.7 entonces clase A, si no clase B”.
• Con distintos umbrales, tenemos distintos clasificadores,
que les dan más o menos importancia a cada una de las
clases (sin necesidad de sobremuestreo o submuestreo).
– Podemos considerar cada umbral como un
clasificador diferente y dibujarlos en el espacio
ROC. Esto genera una curva...
Tenemos una “curva” para un solo clasificador “soft”
• Esta curva es escalonada (no se suele realizar el “convex hull”). 22
Análisis ROC de Clasificadores “soft”
Clase Real
• Curva ROC de un Clasificador “soft”:
– Ejemplo:
Clase Predicha
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
© Tom Fawcett
p p
p
n p
p
n n
p
n n
p
n n
p
n n
p
n n
p
n n
p
n n
p
n n ... p
n n
p
n n
p
n n
p
n n
p
n n
p
n n
p
n n
p
n n
p
n n
p
n n
p
23
Análisis ROC de Clasificadores “soft”
• Curva ROC de un Clasificador “soft”:
© Tom Fawcett
24
Análisis ROC de Clasificadores “soft”
• Análisis ROC de varios clasificadores “soft”:
En esta zona es mejor
el clasificador “insts”
En esta zona es mejor
el clasificador “insts2”
© Robert Holte
•
Debemos mantener los clasificadores que tengan al menos una “zona
mejor” y después actuar igual que en el caso de los clasificadores “crisp”.25
La Métrica “AUC”: el Área bajo la Curva ROC
• ¿Si queremos seleccionar un solo clasificador?
– Se selecciona el que tiene mayor área bajo la curva ROC
(AUC, Area Under the ROC Curve).
ROC curve
True Positives
1,000
0,800
0,600
AUC
0,400
0,200
0,000
0,000
0,200
0,400
0,600
0,800
1,000
False Positives
– Para clasificadores “crisp” es equivalente a la macromedia.
Alternativa al error para evaluar clasificadores
• Un método de aprendizaje / MD será mejor si
genera clasificadores con alta AUC.
26
La Métrica “AUC”: el Área bajo la Curva ROC
• ¿Si queremos seleccionar un solo clasificador “soft”?
– Se selecciona el que tiene mayor área bajo la curva ROC
(AUC, Area Under the ROC Curve).
En este caso
seleccionamos el B.
© Tom Fawcett
Pero para el caso “soft” tenemos sorpresas…
27
La Métrica “AUC”: el Área bajo la Curva ROC
• Resulta que la AUC y la estadística de Wilcoxon-Mann-Whitney
(WMW) (Wilcoxon 1945) (Mann & Whitney 1947) son equivalentes.
– El test WMW sirve para determinar si una de dos variables aleatorias
es estocásticamente mayor que otra.
P[X>Y]
– Si elegimos X como los ejemplos de una clase e Y como los ejemplos
de la otra clase, y el valor de X e Y como el score estimado por el
clasificador, tenemos que la AUC es equivalente a la WMW.
¿He de alegrarme por ello?
La AUC estima realmente la probabilidad de que si elegimos un
ejemplo de la clase 1 y un ejemplo de la clase 0, el clasificador
otorgue más score al primero que al segundo.
(¡OJO! esto no quiere decir que clasifique bien los dos ejemplos). Pero:
• Sí existe un umbral a partir del cual puede clasificar bien los dos.
• No puede clasificar mal los dos, sea cual sea el umbral.
28
La Métrica “AUC”: el Área bajo la Curva ROC
• La Métrica AUC para clasificadores “soft” o rankers.
– Evalúa cuán bien un clasificador realiza un ránking de sus
predicciones.
o, dicho de otro modo,
– Evalúa cuán bien un clasificador es capaz de ordenar sus
predicciones según la fiabilidad que otorga a las mismas.
– Los ránkings de predicciones son fundamentales en muchas
aplicaciones:
• Detección de fraudes.
• Diseño de campañas publicitarias (mailings).
• Detección de spam.
• Diagnóstico de fallos, diagnóstico médico.
• …
– Y muchos métodos de minería de datos:
• Combinación de clasificadores.
• Métodos colaborativos. Recommender systems…
29
Relación entre AUC y error. Elección del umbral
• Hemos visto que AUC es mejor medida de evaluación
que el error. Pero, ¿qué relación hay entre ambas?
– Lógicamente, un AUC cercano a 1 dará un error cercano a 0.
1
• Sea cual sea la distribución de
TPR
0
clases, se espera un error bajo.
0
FPR
1
– Pero un error cercano a 0 no asegura un AUC cercano a 1.
• Recordemos el ejemplo de la central nuclear:
1
c2
abrir
cerrar
ABRIR
0
0
CERRAR
500
99500
ERROR:
0,005
AUC = 0,5
(Mínimo valor posible)
Macromedia= AUC =
(0 + 100 ) / 2 = 50%
TPR
0
0
FPR
1
30
Relación entre AUC y error. Elección del umbral
• Muchos métodos de aprendizaje de clasificadores son
“soft” por definición y se convierten a “crisp” para
realizar la clasificación.
– Por ejemplo, un clasificador bayesiano Naïve, para un
problema de dos clases (a y b), estima dos probabilidades:
P(a|x) y P(b|x).
– La regla de clasificación es la siguiente:
Si P(a|x) > P(b|x) entonces clase a
Si no
entonces clase b
– Esta regla “desaprovecha” los clasificadores bayesianos. Pero
¿qué otra regla podríamos usar? (Lachiche & Flach 2003)
• En primer lugar, convertimos las probabilidades en scores, de la
manera siguiente.
s(x) = P(a|x) / P(b|x)
31
Relación entre AUC y error. Elección del umbral
• Ahora, simplemente, hagamos análisis ROC.
– Dibujamos la curva ROC usando el score.
– Calculamos la inclinación según la distribución de clases original
(o la de aplicación y costes si se disponen).
– Seleccionamos el umbral de corte entre las dos clases para s(x).
Elección usando la regla
P(a|x) > P(b|x)
Elección usando análisis ROC y
distribución original
Inclinación
(slope) dada por
la distribución
original (la de
entrenamiento o
de test).
32
© Nicolas Lachiche
& Peter Flach
Relación entre AUC y error. Elección del umbral
• Ejemplo de resultados
(accuracy) para 25
datasets:
(Lachiche & Flach 2003)
– Se mejoran los resultados
sólo por utilizar bien el
clasificador bayesiano.
33
© Nicolas Lachiche
& Peter Flach
Relación entre AUC y error. Elección del umbral
• En el sentido inverso, sería interesante convertir
métodos de minería de datos que obtienen
clasificadores “crisp” en clasificadores “soft”.
– Esto permitiría usarlos como rankers, para combinación, ...
– Permitiría elegir mejor el umbral y obtener mejores resultados.
• Se están rediseñando y repensando muchos métodos
clásicos. Por ejemplo, para árboles de decisión.
– Se crean métodos de aprendizaje de árboles de decisión que
utilizan el AUC como criterio de partición (Ferri et al. 2002).
– Se suavizan las probabilidades de las hojas (utilizando la
corrección de Laplace u otras más sofisticadas) y se
comprueba que la poda no es satisfactoria para obtener
buenas medidas en AUC (Provost & Domingos 2003) (Ling &
Yan 2003) (Ferri et al. 2003a).
34
Aplicaciones
• Campañas de “mailings” (propaganda selectiva):
– EJEMPLO: Una compañía quiere hacer un mailing para
fomentar la compra de productos. En caso de respuesta
positiva, los clientes suelen comprar productos por valor medio
de 100€. Si un 55% suelen ser costes de producción (fijos y
variables), tenemos que por cada respuesta positiva hay una
ganancia media de 45€.
– Cada mailing cuesta 1€ (portes, folletos) y el conjunto de la
campaña (indep. del número) tendría un coste base de 20.000€.
– Con un 1.000.000 de clientes, en el que, mediante una prueba
piloto de 1.000 clientes hemos estimado que el 1% responde
(compra)...
¿Cómo hemos de actuar?
35
Aplicaciones
• Campañas de “mailings” (propaganda selectiva):
– Calculemos los costes / beneficios.
• COSTES (suponiendo que enviamos a todos el mailing):
– 20.000€ diseño de la campaña.
– 1.000.000 x 1€ = 1.000.000€ envíos.
– TOTAL: 1.020.000€
• BENEFICIOS
– 1% de respuestas sobre 1.000.000 son 10.000 respuestas, a 45€
cada una.
– TOTAL: 450.000€
– Más costes que beneficios  Campaña anulada.
¿Hemos actuado bien?
36
Aplicaciones
• Campañas de “mailings” (propaganda selectiva):
– Entrenemos un clasificador “soft” con los datos piloto y
dibujemos su curva ROC (habiendo separando unos cuantos
datos de test).
Matriz de costes
1
Compra
no
sí
NO
0€
-45€
SÍ
1€
-44€
0,9
0,8
Enviado
0,7
0,6
0,5
0,4
Pero la matriz de confusión
tiene una casilla imposible: “No
enviado y sí comprado”
0,3
0,2
0,1
0
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
• Además, el clasificador no es muy bueno (no muy por encima de
la diagonal) para saber qué clientes comprarán y qué clientes no.
• Pero aún así lo podemos aprovechar...
37
Aplicaciones
• Campañas de “mailings” (propaganda selectiva):
– Podemos usar el clasificador para determinar a quién enviar
los mailings.
Coste Campaña
20.000 --> 20.000
100.000 x 1 --> 100.000
Total:
120.000
Benef. Campaña
3.000 x 45 --> 135.000
Benef. Netos:
15.000
Coste Campaña
20.000 --> 20.000
200.000 x 1 --> 100.000
Total:
220.000
Benef. Campaña
5.000 x 45 --> 225.000
Benef. Netos:
38
5.000
Aplicaciones
• Campañas de “mailings” (propaganda selectiva):
– Gráfica mostrando el beneficio para tres campañas diferentes....
39
Extensión a Más de Dos Clases
• Las técnicas presentadas se han elaborado para dos
clases:
– La evaluación de clasificadores basada en costes se puede
realizar igualmente.
• Ejemplo:
CO ST
p red icted
lo w
m ed iu m
hig h
lo w
0€
200€
10€
a ctu a l
m ed iu m
5€
-2 0 0 0 €
1€
hig h
2€
10€
-1 5 €
lo w
20
5
4
a ctu a l
m ed iu m
0
15
7
hig h
13
4
60
ERROR
p red icted
lo w
m ed iu m
hig h
Coste total:
-29787€
40
Extensión a Más de Dos Clases
• El análisis ROC, en cambio, no es fácilmente extensible:
– Dadas n clases, aparece un espacio de n x (n1) dimensiones.
• Calcular el “convex hull” se hace impracticable.
• El contexto viene determinado no por un valor (el slope), sino n x
(n1) 1 valores.
– Han aparecido aproximaciones (para tres clases, Mossman 1999) o
intentos de abordar el problema general (Srinivasan 1999) (Ferri et al.
2003b).
• La medida AUC, en cambio, sí que se ha extendido.
– Extensión de “todos los pares” (Hand & Till 2001).
AUC
HT

1
c
c
 
c ( c  1)
AUC ( i , j )
i 1 j 1 , j  i
– Extensión “uno contra todos” (Fawcett)
– Otras extensiones (Yan et al. 2003) (AUC*, Ting 2002).
41
Conclusiones
• El Análisis ROC:
– Destaca que la evaluación de clasificadores va mucho más allá
de estimar el error de predicción.
– Permite trabajar conociendo los costes y distribuciones, o
desconociendo esta información, mejorando la generación, la
selección y la aplicación de clasificadores.
– Dispone de un conjunto de métricas y técnicas variadas para
evaluar clasificadores según tarea: minimizar el error, minimizar
el coste, mejorar un ranking, etc.
• Es una área de gran aplicabilidad en minería de datos, de
actualidad y de intenso estudio.
42
Algunas Referencias
• Bradley, A.P. (1997) “The use of the area under the ROC curve in the evaluation of machine learning
algorithms” Pattern Recognition, 30(7), 1145-1159.
• Egan, J.P. (1975). Signal Detection Theory and ROC Analysis. Series in Cognition and Perception.
Academic Press, New York.
• Fawcett, T.(2001). “Using rule sets to maximize ROC performance”.In Proceedings of the IEEE International
Conference on Data Mining (ICDM-2001), pp.131-138.
• Fawcett, T., & Provost, F. (1997). “Adaptive fraud detection”. Data Mining and Knowledge Discovery,
1(3),291-316.
• Fawcett,T. (2003). “ROC graphs: Notes and practical considerations for data mining researchers” Tech
report HPL-2003-4. HP Laboratories, PaloAlto, CA, USA. Available:
http://www.purl.org/net/tfawcett/papers/HPL-2003-4.pdf.
• Ferri, C., Flach, P.; Hernández-Orallo, J. (2002). “Learning Decision Trees using the Area Under the ROC
Curve”, in C. Sammut; A. Hoffman (eds.) “The 2002 International Conference on Machine Learning”
(ICML2002), IOS Press, Morgan Kaufmann Publishers, pp. 139-146.
• Ferri, C.; Flach, P.A.; Hernández-Orallo, J. (2003a) "Improving the AUC of Probabilistic Estimation Trees".
European Conference on Machine Learning, ECML 2003: 121-132
• Ferri, C.; Hernández-Orallo, J.; Salido, M.A. (2003b) "Volume under the ROC Surface for Multi-class
Problems". European Conference on Machine Learning, ECML 2003: 108-120
• Flach, P.; Blockeel, H.; Ferri, C.; Hernández-Orallo, J.; Struyf, J. (2003) “Decision Support for Data Mining:
Introduction to ROC analysis and its applications” in Data Mining and Decision Support: Integration and
Collaboration, Kluwer Academic Publishers, Boston, 2003.
• Flach, P.A. "The Geometry of ROC Space: Understanding Machine Learning Metrics through ROC
Isometrics". (2003) International Conference on Machine Learning, ICML 2003: 194-201
• Fürnkranz, J.; Flach, P.A.: An Analysis of Rule Evaluation Metrics. (2003) International Conference on
Machine Learning, ICML 2003: 202-209
• Hand, D.J., & Till, R.J. (2001). “A Simple Generalisation of the Area Under the ROC Curve for Multiple Class
Classification Problems”, Machine Learning, 45, pp. 171-186.
43
• Hanley, J.A. , & McNeil, B.J. (1982). “The meaning and use of the area under a receiver operating
characteristic (ROC) curve”. Radiology,143,29-36.
Algunas Referencias
• Lachiche, N. & Flach, P.A. (2003). “Improving Accuracy and Cost of Two-class and Multi-class Probabilistic
Classifiers Using ROC Curves”. International Conference on Machine Learning, ICML 2003: 416-423
• Lane, T. (2000). “Extensions of ROC analysis to multi-class domains”. In Dietterich, T., Margineantu, D.,
Provost, F., & Turney, P. (Eds.), ICML-2000 Workshop on Cost-Sensitive Learning
• Ling, C.X.; Yan, R.J. (2003) “Decision Tree with Better Ranking” The 2003 International Conference on
Machine Learning (ICML2003), IOS Press, Morgan Kaufmann Publishers, to appear.
• Mann, H. B. & Whitney, D. R. (1947). "On a test whether one of two random variables is stochastically larger
than the other". Ann. Math. Statist., 18, pp. 50-60.
• Mossman,D.(1999). “Three-way ROCs”. Medical Decision Making,19,78-89.
• Provost, F., & Domingos, P. (2003). “Tree Induction for Probability-based Ranking”, Machine Learning 52:3
(in press), 2003.
• Srinivasan, A. (1999) “Note on the Location of Optimal Classifiers in N-dimensional ROC Space” Technical
Report PRG-TR-2-99, Oxford University Computing Laboratory, Oxford.
• Swets, J.A. (1988). “Measuring the accuracy of diagnostic systems”. Science, 240,1285-1293.
• Swets, J.A., Dawes, R.M., & Monahan, J. (2000). “Better decisions through science”. Scientific American,
283, 82-87. http://www.psychologicalscience.org/pdf/pspi/sciam.pdf.
• Ting, Kai Ming (2002). “Issues in Classifier Evaluation using Optimal Cost Curves” The Proceedings of the
International Conference on Machine Learning" International Conference on Machine Learning, ICML 2002,
pp. 642-649.
• Turney, P. (2000) “Types of Cost in Inductive Concept Learning” Proceedings Workshop on Cost-Sensitive
Learning at the Seventeenth International Conference on Machine Learning (WCSL at ICML-2000), 15-21.
• Weiss, G. and Provost, F. “The Effect of Class Distribution on Classifier Learning: An Empirical Study”
Technical Report ML-TR-44, Department of Computer Science, Rutgers University, 2001.
• Wilcoxon, F. (1945). "Individual comparisons by ranking methods". Biometrics, 1, pp. 80-83.
• Yan, L., Dodier, R., Mozer, M. C., & Wolniewicz, R. (2003). "Optimizing classifier performance via the
Wilcoxon-Mann-Whitney statistic. In The Proceedings of the International Conference on Machine Learning"
International Conference on Machine Learning, ICML (pp. 848-855).
http://www.cs.colorado.edu/~mozer/papers/
• Zweig, M.H.; Campbell, G. (1993) “Receiver-operating characteristic (ROC) plots: a fundamental evaluation
tool in clinical medicine”, Clin. Chem, 1993; 39: 561-77.
44
Algunas Sitios para Saber Más
• Página de Tom Fawcett sobre Análisis ROC:
http://www.hpl.hp.com/personal/Tom_Fawcett/ROCCH/
• Software de Análisis ROC
http://epiweb.massey.ac.nz/ROC_analysis_software.htm
http://cs.bris.ac.uk/~farrand/rocon/
• Bibliografía extensa de Análisis ROC:
http://splweb.bwh.harvard.edu:8000/pages/ppl/zou/roc.html
• 1st Workshop on “ROC Analysis in AI”, Valencia, 22 agosto 2004
(dentro de ECAI’2004)
http://www.dsic.upv.es/~flip/ROCAI2004/
45
Descargar

transparencias