Reconocimiento de Patrones

Técnicas de validación (Clasificación Supervisada) Jesús Ariel Carrasco Ochoa Instituto Nacional de Astrofísica, Óptica y Electrónica

Clasificación Supervisada

¿Para qué evaluar un clasificador? Para seleccionar cuál clasificador usar ( saber cuál es mejor ) Para estimar el error esperado ( qué tan confiable es )

Técnicas de validación

¿Cómo evaluar un clasificador? Midiendo la calidad ( accuracy ) La mediremos como:

sificadosobjetosClaaciertosaccuracy

##

=

Técnicas de validación

¿Sobre cuál conjunto de objetos evaluar? Dividir la muestra en 2 (entrenamiento y

control)

Validación cruzada de k particiones

Leave one out

Bootstrap

Dividir la muestra en 2

Clasificador

Muestra

Entrenamiento Control

Muestra de Control

Clasificada

accuracy

Dividir la muestra en 2

¿Cómo dividir la muestra? Separarla en 2 manualmente

Separarla aleatoriamente

Dividir la muestra en 2

Problemas En algunos casos la muestra inicial puede ser

muy pequeña de modo que no conviene dividirla se reduce aún más la información para

entrenar

la muestra de control puede ser muy pequeña con lo cual no da información confiable

Si se tiene una mala división los resultados no

son confiables

Dividir la muestra en 2

Para el segundo problema Repetir la división aleatoria varias veces

Calcular el accuracy para cada forma de

dividir

Promediar los resultados

Validación cruzada

Dividir la muestra en k partes (validación cruzada con k pliegues) (k-fold cross validation) Formar el conjunto de entrenamiento con k-1

particiones y el de control con la partición restante

Repetir el proceso dejando como control cada una de las particiones

Promediar los resultados de todas las pruebas

Validación cruzada

Muestra

Control Entrenamiento

Control Entrenamiento

Control Entrenamiento

accuracy

accuracy

accuracy

Validación cruzada

Cuantas particiones hacer?

Si se hacen 2 particiones dividir la muestra en 2

El máximo valor de k es el número de objetos de la muestra original

Usualmente se toma k=10, si la muestra es muy grande se toma k=3, si es muy pequeña se toma el máximo valor de k

Leave one out

Tomar un objeto de la muestra como control y los demás como muestra de entrenamiento

Repetir el proceso dejando como control cada uno de los objetos de la muestra

Promediar los resultados de todas las pruebas

Leave one out Muestra

Control Entrenamiento

Control Entrenamiento

Control Entrenamiento

accuracy

accuracy

accuracy

: :

Bootstrap

Si la muestra tiene N objetos, seleccionar aleatoriamente con reemplazo (los objetos seleccionados se pueden repetir) un conjunto de entrenamiento de N objetos

Formar la muestra de control con los objetos que

no hayan sido seleccionados

Repetir el proceso k veces

Promediar los resultados de todas las pruebas

Técnicas de validación

La medida de accuracy es útil si todos los errores son igualmente graves

Si esto no es así existen otras medidas de calidad

Consideremos la matriz de confusión

Matriz de Confusión

C1 C2 ……… Cr

C1

C2

.

. Cr

n11 n12 …….. n1r

n21 n22 …….. n2r

n11 n12 …….. n1r

nij = numero de objetos de la muestra que estando en la clase Ci fueron puestos en la clase Cj

Matriz de Confusión 2 clases

C1 C2

C1

C2

TP FN FP TN

TP = verdaderos positivos TN = verdaderos negativos FP = falsos positivos FN = falsos negativos

Otras medidas de calidad

TNFPTNdadespecifici

FNTPTPadsensibilid

FNFPTNTPFNFPerror

FNFPTNTPTNTPaccuracy

+=

+=

++++

=

++++

=

Otras medidas de calidad

recuerdopresiciónrecuerdopresiciónFmeasure

FNTPTPrecuerdo

FPTPTPpresición

+∗∗

=

+=

+=

2

Significancia Estadística

Se utilizan para comparar los resultados de un clasificador contra los de otro clasificador

Tiene como objetivo validar que los resultados obtenidos no son debidos al azar

Se busca decidir si ambos clasificadores obtienen resultados equivalentes (son competitivos uno con otro) o si uno es mejor que el otro

Se utilizan técnicas estadísticas de prueba de hipótesis

Significancia Estadística

Comparar dos clasificadores Sobre un solo conjunto de datos

Decidir cuál es el mejor para este conjunto de

datos

Sobre varios conjuntos de datos

Decidir cuál es el mejor de manera general

Comparación sobre un solo conjunto de datos

Se requiere tener una serie de resultados para cada clasificador sobre los mismos datos

Comúnmente estas pruebas se hacen sobre la validación cruzada (particiones iguales para ambos clasificadores)

Usualmente la hipótesis que se prueba es que los resultados son equivalentes

Si se rechaza la hipótesis se infiere que el clasificador que obtiene mejores resultados es realmente mejor y no se debe al azar.

Significancia Estadística

Existen diversas pruebas de significancia estadística. prueba t de Student

prueba de los signos de Wilcoxon

Prueba t de student

Se calcula

donde n es el número de pruebas las µ y σ2 son las medias y varianzas de los resultados para cada clasificador (1,2)

nS

ST

22

21

21

21

21

ˆ

ˆ

σσ

µµ

µµ

µµ

+=

−=

−

−

Prueba t de student

Se supone que T sigue la distribución t de student con 2n-2 grados de libertad

Se selecciona un nivel de confianza y se compara con el valor esperado (tabla)

Si el valor obtenido es mayor que el de la tabla se rechaza la hipótesis de que son equivalentes

Se aplica cuando la población estudiada sigue una distribución normal y la desviación estándar puede aproximarse con los datos.

Prueba t de student

Prueba de los signos de Wilcoxon

Supóngase que se tienen n resultados ai y bi con i=1,…,n para dos clasificadores A y B

El objetivo es comprobar si los clasificadores son equivalentes o no

Prueba de los signos de Wilcoxon

Se calcula zi=ai-bi para i=1,…,n

Se ordenan los zi de acuerdo a su valor

absoluto y se calcula su posición pi

Se calcula:

∑

∑

<

−

>

+

=

=

0zi

0zi

i

i

pT

pT

Prueba de los signos de Wilcoxon

Claramente si no hay valores iguales

Se Busca en la tabla si los valores T+ y T- están fuera del intervalo para el nivel de confianza deseado y de ser así se rechaza la hipótesis de que son equivalentes.

2)1n(nTT +

=+ −+

Prueba de los signos de Wilcoxon

Se aplica a muestras pequeñas, de tamaño entre 6 y 25.

Supone que los valores de zi son independientes y siguen una distribución continua y simétrica

Comparación sobre varios conjuntos de datos

Comparar promedio de resultados para todos los conjuntos de datos

Comparar para cada conjunto de datos y hacer una tabla W/T/L