Upload
florentino-lopez
View
79
Download
0
Embed Size (px)
DESCRIPTION
Imágenes espaciales
Citation preview
Intelligent Databases and Information Systems research groupDepartment of Computer Science and Artificial IntelligenceE.T.S Ingeniería Informática – Universidad de Granada (Spain)
Métodos de clasificaciónMétodos de clasificación
Clasificación© Fernando Berzal
2
Analizador NuméricoAnalizador NuméricoEjecutamos nc.bat:
Pinchamos sobre el botón Inicio y buscamos el fichero de configuración necesario para acceder a nuestros datos (p.ej. Iris.cfg).
3
Analizador NuméricoAnalizador NuméricoAhora podemos utilizar distintas técnicas de aprendizaje sobre nuestro conjunto de datos:
4
Analizador NuméricoAnalizador NuméricoEmpezamos viendo algunas características del conjunto de datos (Datos > Estadísticas…):
5
Analizador NuméricoAnalizador NuméricoTambién podemos ver gráficamente la distribución de las muestras (Datos > Representación 2D…):
6
Analizador NuméricoAnalizador NuméricoCuando nuestro conjunto de patrones viene dado por un conjunto de imágenes (como es el caso de Galaxy o Igaliko) podemos acceder a la representación visual de cada “dimensión” (Datos > Estadísticas… > Ver imagen):
7
Métodos de clasificaciónMétodos de clasificación
Objetivo Predecir el valor de un atributo particular (clase).
Aprendizaje supervisadoExisten clases predefinidas
Los resultados obtenidos dependerán de: El método de clasificación seleccionado. El conjunto de datos disponible para entrenar
el clasificador (lo bueno que sea como muestra representativa de los datos reales).
8
Métodos de clasificaciónMétodos de clasificación
Inducción
Deducción
Modelo
Tid Attrib1 Attrib2 Attrib3 Class
1 Yes Large 125K No
2 No Medium 100K No
3 No Small 70K No
4 Yes Medium 120K No
5 No Large 95K Yes
6 No Medium 60K No
7 Yes Large 220K No
8 No Small 85K Yes
9 No Medium 75K No
10 No Small 90K Yes 10
Tid Attrib1 Attrib2 Attrib3 Class
11 No Small 55K ?
12 Yes Medium 80K ?
13 Yes Large 110K ?
14 No Small 95K ?
15 No Large 67K ? 10
Conjunto de prueba
Algoritmo de
aprendizaje
Conjunto de entrenamiento
Aprendermodelo
Aplicarmodelo
9
Algoritmos de clasificaciónAlgoritmos de clasificación
Métodos paramétricosMétodos paramétricos Clasificador lineal Clasificador lineal de Mahalanobis Clasificador cuadrático Método de los paralelepípedos
Métodos no paramétricosMétodos no paramétricos Vecino más cercano (k-NN) LVQ (Linear Vector Quantization) DSM (Decision Surface Mapping)
10
Métodos paramétricosMétodos paramétricos
El aprendizaje supervisado requiere un conjunto de entrenamiento a partir del cual construiremos un modelo de clasificación.
Dependiendo de si se supone o no un conocimiento a priori de la estructura estadística de las clases, la forma de construir el clasificador será radicalmente distinta.
Aproximación paramétrica
Supongamos que podemos modelar las clases de nuestro problema mediante funciones de densidad de probabilidad conocidas…
11
Métodos paramétricosMétodos paramétricos
12
Métodos paramétricosMétodos paramétricos
Función de densidad normalFunción de densidad normal
13
Métodos paramétricosMétodos paramétricos
Función de densidad normalFunción de densidad normal
14
Métodos paramétricosMétodos paramétricos
Función de densidad normal Función de densidad normal multidimensionalmultidimensional
ii Vector medio de la clase iVector medio de la clase i
ii Matriz de covarianzaMatriz de covarianza
15
Métodos paramétricosMétodos paramétricos
Función de densidad normal Función de densidad normal multidimensionalmultidimensional
Densidad de probabilidad y diagrama de dispersiónDensidad de probabilidad y diagrama de dispersión
16
Métodos paramétricosMétodos paramétricos
Clasificador de mínimo error:Clasificador de mínimo error:Clasificador de BayesClasificador de Bayes
17
Métodos paramétricosMétodos paramétricos
Funciones discriminantes para la función de densidad de probabilidad normal (3 casos) :
i = 2 I Clasificador lineal euclídeoVariables estadísticamente independientes.Matrices de covarianza iguales para todas las clases.
i = Clasificador de MahalanobisVariables correladas.Matrices de covarianza iguales para todas las clases.
i Clasificador cuadráticoMatrices de covarianza arbitrarias(independientes para las distintas clases)
18
Clasificador linealClasificador lineal
Característica principal: Las fronteras de decisión se expresan como una función lineal.
19
Clasificador linealClasificador lineal
20
Clasificador linealClasificador lineal
Clasificador de mínima distancia euclídea
Fronteras de decisión
21
Clasificador linealClasificador lineal
Clasificador de mínima distancia euclídea
Uso del clasificador
22
Clasificador linealClasificador lineal
Clasificador de mínima distancia euclídea
i = i I
Basta con calcular la distancia euclídea de cada patrón a cada uno de los centros de las J clases y asignarle la etiqueta de la clase más cercana.
23
Clasificador linealClasificador lineal
24
Clasificador linealClasificador lineal
DISTANCIA EUCLÍDEA NORMALIZADA:Se elige la clase j que minimiza el valor de la
función gj
Al normalizar las distancias,se evita que aquellos atributoscuyos rangos sean más amplios
influyan más que los demása la hora de clasificar.
2
,)(
i i
jiij range
Xxxg
25
Método de los paralelepípedosMétodo de los paralelepípedos
26
Método de los paralelepípedosMétodo de los paralelepípedos
El método de los paralelepípedos elige la clase j que minimiza el valor de la función gj
Sólo requiere calcular la media de cada atributopara cada clase y la desviación típica de cada
atributo (independientemente de la clase).
2
,)(
i
jiij dev
Xxxg
27
Clasificador linealClasificador lineal
28
Clasificador linealClasificador lineal
Variables correladas
29
Clasificador linealClasificador lineal
Clasificador demínima distancia de Mahalanobis
Distancia de Mahalanobis vs. Distancia euclídea
30
Clasificador linealClasificador lineal
Clasificador demínima distancia de Mahalanobis
i =
Basta con calcular la distancia de Mahalanobis al cuadrado de cada patrón a cada uno de los centros de las J clases y asignarle la etiqueta de la clase más cercana.
31
Clasificador cuadráticoClasificador cuadrático
32
Clasificador cuadráticoClasificador cuadrático
Característica principal: Las fronteras de decisión se expresan como una función cuadrática (círculos, elipses, parábolas, hipérbolas).
33
Clasificador cuadráticoClasificador cuadrático
34
Métodos paramétricosMétodos paramétricos
¿Qué clasificador es más conveniente?¿Qué clasificador es más conveniente?
Desde el punto de vista formal, el clasificador cuadrático (i arbitrario) es el más general. Sin embargo…
Un clasificador cuadrático requiere un número de patrones mucho mayor que un clasificador lineal para estimar adecuadamente las densidades de probabilidad:
Los estimadores no son fiables cuando tenemos pocos datos y/o la dimensionalidad de los datos es elevada.
35
Métodos paramétricosMétodos paramétricos
Resultados experimentalesResultados experimentales
36
Métodos paramétricosMétodos paramétricos
Diseño de clasificadores paramétricos:Diseño de clasificadores paramétricos:Fenómeno de HughesFenómeno de Hughes
37
Métodos paramétricosMétodos paramétricos
Diseño de clasificadores paramétricos:Diseño de clasificadores paramétricos:Clase de rechazoClase de rechazo
38
Métodos paramétricosMétodos paramétricos
Diseño de clasificadores paramétricos:Diseño de clasificadores paramétricos:Observaciones finalesObservaciones finales
También habría que comprobar que las clases de nuestro problema sigan una distribución normal.
Si no es así (p.ej. distribuciones bimodales), habrá que recurrir a otro tipo de técnicas…
39
Métodos no paramétricosMétodos no paramétricos
El aprendizaje supervisado requiere un conjunto de entrenamiento a partir del cual construiremos un modelo de clasificación.
Dependiendo de si se supone o no un conocimiento a priori de la estructura estadística de las clases, la forma de construir el clasificador será radicalmente distinta.
Aproximación no paramétrica
Supongamos que NONO podemos modelar las clases de nuestro problema mediante funciones de densidad de probabilidad conocidas…
40
k-NNk-NN
41
k-NNk-NN
k vecinos más cercanos
K demasiado pequeño Sensible a ruido
K demasiado grande El vecindario puede incluir puntos de otras clases
X X X
(a) 1-nearest neighbor (b) 2-nearest neighbor (c) 3-nearest neighbor
42
1-NNRegla de clasificación del vecino más
cercano
k-NNk-NN
43
No tiene sentido probar con valores pares de kporque el error asociado a la regla k-NN
es el mismo para 2N y 2N-1
k-NNk-NN
44
Interpretación de los resultadosInterpretación de los resultadosConforme aumentamos el valor de k, se reduce el error si disponemos de un número suficiente de muestras de entrenamiento (p.ej. Igaliko), siempre que éstas estén correctamente etiquetadas. Por otro lado, cuantas más muestras tengamos, más tiempo se tardará en realizar la clasificación.
Los métodos de edición aparecen para solucionar el problema de los patrones mal etiquetados, que intentan eliminar.
Los métodos de condensado procurar reducir el número de muestras sin afectar a la calidad del clasificador para reducir la complejidad computacional del problema.
k-NNk-NN
45
Métodos de ediciónMétodos de edición
k-NNk-NN
46
Métodos de condensadoMétodos de condensado
Conjunto de datos original Conjunto condensado
Condensado de HartCondensado de Hart(sobre un conjunto previamente multieditado)(sobre un conjunto previamente multieditado)
k-NNk-NN
47
Métodos de edición y condensadoMétodos de edición y condensado
k-NNk-NN
48
Métodos de edición y condensadoMétodos de edición y condensado
k-NNk-NN
50
LVQLVQ
51
LVQ LVQ Linear Vector QuantizationLinear Vector Quantization
Basado en los mapas autoorganizativos de Kohonen [SOM: Self-Organizing MapsSOM: Self-Organizing Maps]:
Número fijo y relativamente bajo de prototipos para aproximar las funciones de densidad de probabilidad de las distintas clases.
Dada una secuencia de observaciones vectoriales (patrones), se selecciona un conjunto inicial de vectores de referencia (codebookscodebooks o prototipos).
Iterativamente, se selecciona una observación X y se actualiza el conjunto de prototipos de forma que case mejor con X.
Una vez finalizado el proceso de construcción del conjunto de prototipos (codebooks), las observaciones se clasificarán utilizando la regla 1-NN (buscando el vecino más cercano en el conjunto de vectores de referencia).
52
LVQ LVQ Linear Vector QuantizationLinear Vector Quantization
LVQ aplicado a dos clases solapadasque siguen una distribución normal:
53
LVQLVQ
LVQ-1
En cada paso de aprendizaje, LVQ-1 modifica únicamente elprototipo más cercano al patrón.
Si la clase del prototipo coincide con la de la muestra, el prototipo se acerca a la muestra. En el caso contrario, el prototipo se aleja de ésta (por lo cual este algoritmo tiende a reducir la densidad de prototipos alrededor de las fronteras de decisión).
La dirección de la corrección coincide con la línea recta que une el patrón y su prototipo más cercano.
54
LVQLVQ
Variante OLVQ-1
El método OLVQ-1 es idéntico al LVQ-1 salvo que cada prototipo (codebook) mantiene su razón de aprendizaje propia, que determina la magnitud del desplazamiento del prototipo a lo largo de la línea recta que lo une con el patrón del conjunto de entrenamiento.
55
LVQLVQ
Resultados experimentales con LVQ-1
56
DSMDSM
57
DSM DSM Decision Surface MappingDecision Surface Mapping
Variante de los métodos de aprendizaje adaptivo que consiste en aproximar directamente las fronteras de decisión (para lo que requiere un conjunto editado de datos).
Si una muestra es clasificada correctamente, no se realiza ninguna acción. Cuando se produce un error de clasificación durante la fase de aprendizaje, la corrección se aplica a dos prototipos simultáneamente:
Se castiga al prototipo más cercano (que provoca el error de clasificación).
Se premia al prototipo más cercano de la misma clase que el patrón considerado.
58
DSM DSM Decision Surface MappingDecision Surface Mapping
Variante de los métodos de aprendizaje adaptivo que consiste en aproximar directamente las fronteras de decisión (para lo que requiere un conjunto editado de datos).
ObservacionesObservaciones
Lo más probable es que los errores de clasificación se produzcan cerca de las fronteras de decisión.
DSM actúa sobre parejas de prototipos situados a ambos lados de las fronteras de decisión y no permite tratar problemas con solapamiento entre clases.
60
EvaluaciónEvaluación
Métricas Cómo evaluar la “calidad” de un modelo de
clasificación
MétodosCómo estimar, de forma fiable, la calidad de un
modelo.
ComparaciónCómo comparar el rendimiento relativo
de dos modelos de clasificación alternativos
61
La evaluación de un algoritmo de clasificación se puede realizar atendiendo a distintos aspectos del modelo creado o del proceso utilizado para crearlo:
Precisión (porcentaje de casos clasificados correctamente).
Eficiencia(tiempo necesario para construir/usar el clasificador).
Robustez(frente a ruido y valores nulos)
Escalabilidad(utilidad en grandes bases de datos)
Interpretabilidad(el clasificador, ¿es sólo una caja negra?)
Complejidad(del modelo de clasificación) Navaja de Occam
EvaluaciónEvaluación
62
Estimación de la precisión del modeloEstimación de la precisión del modelo Antes de construir el modelo de clasificación, se
divide el conjunto de datos disponible en un conjunto de entrenamiento (para construir el modelo) y un conjunto de prueba (para evaluar el modelo).
Una vez construido el modelo, se usa para clasificar los datos del conjunto de prueba: Comparando los casos etiquetados del conjunto de prueba con el resultado de aplicar el modelo, se obtiene un porcentaje de clasificación.
Si la precisión del clasificador es aceptable, podremos utilizar el modelo para clasificar nuevos casos (de los que desconocemos su clase).
EvaluaciónEvaluación
63
Estimación de la precisión del Estimación de la precisión del modelomodelo
Cuanto mayor sea su complejidad, los modelos de clasificación tienden a ajustarse más al conjunto de entrenamiento utilizado en su construcción (sobreaprendizaje).
El conjunto de prueba debe ser independiente del conjunto de entrenamiento.
El error de clasificación en el conjunto de entrenamiento NONO es un buen estimador de la precisión del clasificador.
EvaluaciónEvaluación
64
SobreaprendizajeSobreaprendizaje
Sobreaprendizaje debido a la complejidad del clasificador
65
SobreaprendizajeSobreaprendizaje
Sobreaprendizaje debidoa la presencia de ruido en los datos
66
SobreaprendizajeSobreaprendizaje
Sobreaprendizaje debidoa la escasez de muestras
67
Evaluación: MétricasEvaluación: MétricasMatriz de confusión(confusion matrix)
Precisión del clasificadorPrecisión del clasificador
accuracyaccuracy = (TP+TN)/(TP+TN+FP+FN)
Predicción
CP CN
Cla
se re
al
CP TP: True positive
FN: False negative
CN FP: False
positive
TN: True negative
68
Evaluación: MétricasEvaluación: Métricas
Limitaciones de la precisión (“accuracy”) :
Supongamos un problema con 2 clases: 9990 ejemplos de la clase 1 10 ejemplos de la clase 2
Si el modelo de clasificación siempre dice que los ejemplos son de la clase 1, su precisión es
9990/10000 = 99.9%
Totalmente engañosa, ya que nunca detectaremos ningún ejemplo de la clase 2.
69
Evaluación: MétricasEvaluación: Métricas
Alternativa: Matriz de costes
El coste de clasificación será proporcional
a la precisión del clasificador sólo si i,j: i j C(i|j) = C(j|i)
C(i|i) = C(j|j)
C(i|j)Predicción
CP CN
Cla
se
real
CP C(P|P) C(N|P)
CP C(P|N) C(N|N)
70
Evaluación: MétricasEvaluación: MétricasMedidas “cost-sensitive”
precision = TP/(TP+FP)
True positive recognition rate
recall = sensitivity = TP/P = TP/(TP+FN)
True negative recognition rate
specificity = TN/N = TN/(TN+FP)
Predicción
CP CN
Cla
se re
al
CP TP: True positive
FN: False negative
CN FP: False
positive
TN: True negative
71
Evaluación: MétricasEvaluación: MétricasMedidas “cost-sensitive”
F-measureF-measure
F = 2*precision*recall / (precision+recall)
F= 2TP / (2TP+FP+FN)
Predicción
CP CN
Cla
se re
al
CP TP: True positive
FN: False negative
CN FP: False
positive
TN: True negative
72
Evaluación: MétricasEvaluación: Métricas
AccuracyAccuracy
Predicción
CP CN
Real
CP TP FN
CN FP TN
RecallRecall
Predicción
CP CN
Real
CP TP FN
CN FP TN
PrecisionPrecision
Predicción
CP CN
Real
CP TP FN
CN FP TN
F-measureF-measure
Predicción
CP CN
Real
CP TP FN
CN FP TN
73
Evaluación: MétodosEvaluación: Métodos
Para evaluar la precisión de un modelo de clasificación nunca debemos utilizar el conjunto de entrenamiento (lo que nos daría el “error de resustitución” del clasificador), sino un conjunto de prueba independiente:
Por ejemplo, podríamos reservar 2/3 de los ejemplos disponibles para construir el clasificador y el 1/3 restante lo utilizaríamos de conjunto de prueba para estimar la precisión del clasificador.
74
Evaluación: MétodosEvaluación: MétodosValidación cruzada Validación cruzada
(k-CV: k-fold Cross-Validation)(k-CV: k-fold Cross-Validation)
Se divide aleatoriamente el conjunto de datos en k subconjuntos de intersección vacía (más o menos del mismo tamaño). Típicamente, k=10.
En la iteración i, se usa el subconjunto i como conjunto de prueba y los k-1 restantes como conjunto de entrenamiento.
Como medida de evaluación del método de clasificación se toma la media aritmética de las k iteraciones realizadas.
75
Evaluación: MétodosEvaluación: MétodosValidación cruzada Validación cruzada
Variantes de la validación cruzadaVariantes de la validación cruzada
“Leave one out”: Se realiza una validación cruzada con k particiones del conjunto de datos, donde k coincide con el número de ejemplos disponibles.
Validación cruzada estratificada: Las particiones se realizan intentando mantener en todas ellas la mismo proporción de clases que aparece en el conjunto de datos completo.
76
Evaluación: MétodosEvaluación: MétodosBootstrapping Bootstrapping
Muestreo uniforme con reemplazo de los ejemplos disponibles (esto es, una vez que se escoge un ejemplo, se vuelve a dejar en el conjunto de entrenamiento y puede que se vuelva a escoger).
0.632 bootstrap: Dado un conjunto de d datos, se toman d muestras. Los datos que no se escojan formarán parte del conjunto de prueba.
En torno al 63.2% de las muestras estarán en el “bootstrap” (el conjunto de entrenamiento) y el 36.8% caerá en el conjunto de prueba ya que (1-1/d)d e-1 =0.368
Si repetimos el proceso k veces, tendremos:
))(368.0)(632.0()( _1
_ settraini
k
isettesti MaccMaccMacc
77
CréditosCréditos Francisco J. Cortijo Bon: Apuntes de
Reconocimiento de Formas, Universidad de Granada, 1999
Jiawei Han: “Data Mining: Concepts and Techniques”, capítulo 7, 2006
Pang-Ning Tan (Michigan State University), Michael Steinbach & Vipin Kumar (University of Minnesota): “Introduction to Data Mining”, capítulos 8 y 9, 2006