Tópicos Avanzados en
Ingeniería del Software
Clasificación Supervisada
Ing. José Castañeda Saldaña
Agenda
• Clasificación Supervisada
• NN
•Clasificación Supervisada
• KNN •NN
•KNN
• Análisis Discriminante
•Análisis Discriminante
•Regresión Lineal.
• Regresión Lineal.
Clasificación Supervisada
Clasificación supervisada. Dado una matriz de
aprendizaje I0 (ó control) y los rasgos I(O) de un
objeto del cual no conocemos su clase, encontrar un
Algoritmo que permita clasificarlo
A ( I0, I(O) ) = ( P1(O), P2(O),…,Pr(O) )
¿A qué clase
pertenece?
Algunos Algoritmos
Clasificación Supervisada
- NN (Nearest Neighbor)
- KNN (K-Nearest Neighbor)
- Medios o centros
- KORA-3
- Algunos modelos de redes neuronales (Ej.
Superficies de separación -Perceptron)
- Análisis Discriminante
2) Selección de rasgos. Consiste en encontrar los
rasgos que permitan describir los objetos de manera
tal que podamos diferenciar los objetos de cada clase
Es importante una buena selección de rasgos para:
a) Mejorar la clasificación (más rápido, menos
información)
b) Encontrar mejores soluciones. Mayor precisión en
los resultados
Algunos Algoritmos
Selección de rasgos
- Basados en Testores Típicos
- Algoritmo BT
- FS-Testor
- Zhuravliov
- Análisis Discriminante
Ejemplo. Clasificación Supervisada
Algoritmo NN (Nearest Neighbor)
Fase de Aprendizaje:
- Se determina, en primer lugar, en cuantas clases
diferentes vamos a realizar la clasificación.
- Se determinan los rasgos que caracterizan a los
objetos
- Se busca una muestra de objetos para cada clase y
se le calculan sus rasgos, para formar la matriz de
aprendizaje
Ejemplo. Clasificación Supervisada
Algoritmo NN (Nearest Neighbor)
Fase de Clasificación:
- Se calculan los rasgos del objeto a clasificar y se
calcula la "distancia" a cada uno de los objetos de la
muestra
- La clasificación del objeto corresponde a la clase a la
que pertenece aquel objeto de la muestra cuya
distancia sea la mas cercana al objeto a clasificar
Ejemplo:
Supongamos que los objetos a clasificar son figuras geométricas
y supongamos también que se agrupan en tres clases A, B y C
que representan objetos redondos, semi-alargados y alargados
respectivamente.
Tendremos un solo rasgo ó característica, calculado en base a
dos propiedades geométricas del objeto: división entre el
diámetro mayor y menor del objeto
Supongamos que tenemos el siguiente conjunto de objetos, de
los cuales conocemos sus rasgos y la clase a la que pertenece
cada uno.
La matriz de aprendizaje sería (Las clases A, B, y C estarían
codificadas como 1, 2 y 3 respectivamente)
Objeto Rasgo Clase
1 1.250 1
2 1.288 1
3 1.001 1
4 1.197 1
5 1.737 2
6 1.786 2
7 2.023 2
8 1.985 2
9 4.370 3
10 5.414 3
11 4.728 3
12 3.962 3
Clasificación:
Supongamos que queremos clasificar un nuevo objeto cuyo
rasgo es: 1.6
Habría que calcular la “distancia” entre ese objeto y todos los de
la matriz de aprendizaje para determinar cuál es el más cercano.
En este caso como los objetos están definidos por un solo rasgo
la distancia podría ser el valor absoluto de la resta de los rasgos
distancia( O1, O2 ) = | X1(O1) – X1(O2) |
Clasificación:
Objeto Rasgo Clase |1.6 - Rasgo| La menor distancia es 0.186,
correspondiente al objeto número
1 1.250 1 0.350 6.
2 1.288 1 0.312
Por tanto el objeto que estamos
3 1.001 1 0.599 clasificando, cuyo rasgo es 1.6,
4 1.197 1 0.403 pertenece a la clase 2 (clase del
5 1.737 2 0.137 objeto 6, que es el más cercano
[Nearest Neighbour] )
6 1.786 2 0.186
7 2.023 2 0.423
8 1.985 2 0.385
9 4.370 3 2.770
10 5.414 3 3.814
11 4.728 3 3.128
12 3.962 3 2.362
Problemas:
El proceso de clasificación es lento, ya que se requiere calcular la distancia entre el
objeto y todos los objetos de la matriz de aprendizaje
Se requiere trabajar en un espacio métrico (que exista la función de distancia y que
ésta cumpla ciertas propiedades)
Problemas como el siguiente:
¿A qué clase pertenece el objeto
amarillo, si aplicamos el algoritmo
NN?
Algunas funciones de distancia:
Para el caso de K rasgos podemos utilizar la distancia
Euclidiana u otra medida de distancia basada en la familia de
distancias Ls ó Minkowski
Casos particulares:
s = 1 (distancia Manhattan)
s = 2 (distancia Euclidiana)
Clasificación no Supervisada
Clasificación no supervisada (agrupamiento ó
clustering). Tenemos los objetos de la matriz de
aprendizaje, pero sin clasificar. No conocemos las
clases y el problema consiste entonces en agruparlos
por rasgos “comunes”. De esta manera se determinan
las clases en que se podrían agrupar los objetos
¿En qué clases se
podrían agrupar?
Algunos Algoritmos
Clasificación no supervisada (clustering)
- K-Medias
- CLASS*
- Vector Quantization
- Algunos modelos de redes neuronales (Mapas
autoorganizativos de Kohonen)
Análisis Discriminate
¿Qué es el análisis discriminante?
Es una técnica de clasificación de objetos en la que
se presupone la existencia de dos o más clases:
Objetivos:
1. Describir las diferencias existentes entre esos
clases en base a los valores que toman ciertos
rasgos sobre objetos de cada una de las clases
(selección de rasgos)
2. Clasificar nuevos objetos en alguna de las clases
preexistentes en función de los valores que toman
ciertas variables para esos objetos (clasificación
supervisada)
A manera de ejemplo, trabajaremos con tres clases
de objetos, definidos a priori, de acuerdo a la
forma de las figuras:
Clase A: Figuras Redondas
Clase B: Figuras Semi-Redondas
Clase C: Figuras Alargadas
El punto de partida de nuestro análisis es el conjunto de
rasgos seleccionados para identificar a cada uno de los
objetos.
Trabajaremos con tres rasgos:
-Diámetro Mayor del Objeto
-Diámetro Menor del Objeto
-División entre el [Link] y el [Link]
Nuestro objetivo será, entonces, identificar, en la medida de
lo posible, cuáles de estos rasgos caracterizan la forma de
los objetos de acuerdo a las clases que hemos definido.
En este caso, intencionalmente, se ha incluido dos variables
(diámetro mayor y diámetro menor) que sabemos no son
importantes. La relación entre ambos (división) es el rasgo
importante.
Funciones discriminantes
El análisis discriminante tratará de encontrar funciones
de estas tres variables ó rasgos cuyos valores separen
o discriminen lo más posible a las tres clases
existentes: A, B y C. Estas funciones, denominadas
funciones o ejes discriminantes, serán combinaciones
lineales de las variables originales, y tendrán la forma:
Y = a0 + a1X1 + a2X2 + …. + anXn
Donde n es la cantidad de rasgos. Xi los valores de los
rasgos y aj los coeficientes calculados.
Funciones Discriminantes (cont…)
Los coeficientes a0, a1,…., an se eligen de tal forma
que se consiga la máxima separación entre las tres
clases existentes, es decir, tratando de que los
valores que toman estas funciones discriminantes
Y en los tres grupos, sean lo más diferentes
posibles.
No haremos el desarrollo formal sobre la obtención
de los coeficientes que definen las funciones
discriminantes. Existen softwares de estadística
que nos permiten realizar los cálculos, Ej: SPSS,
MINITAB, XSLAT, STATISXL, y otros.
Funciones Discriminantes (cont…)
Al aplicar el análisis discriminante se obtiene una
función discriminante por cada clase.
Y1 = a10 + a11X1 + a12X2 + …. + a1nXn
Y2 = a20 + a21X1 + a22X2 + …. + a2nXn
Y3 = a30 + a31X1 + a32X2 + …. + a3nXn
…
Ym = am0 + am1X1 + am2X2 + …. + amnXn
n: es la cantidad de rasgos
m: es la cantidad de clases
Interpretación de las funciones discriminantes
Selección de rasgos
Uno de los problemas a resolver mediante el
reconocimiento de patrones es determinar la
importancia de los rasgos en la clasificación.
El análisis discriminante permite determinar la
contribución relativa de los distintos rasgos a la
discriminación, o lo que es lo mismo, determinar
cuáles son los rasgos que más contribuyen a
discriminar entre una clase y otra.
Coeficientes de las funciones
La contribución de cada variable a la discriminación, se
puede observar a través de los propios coeficientes (a1,
a2,…,an) que definen a las funciones discriminantes.
Por ejemplo, si al observar en una función cualquiera Y,
vemos que el coeficiente a1 que acompaña a la variable X1
es “mucho mayor” que los de las otras variables,
podríamos afirmar que esta variable X1 va a contribuir al
valor final de Y en mayor medida que las otras variables, y
por lo tanto es mas más importante.
De igual manera podemos inferir que aquellas variables
cuyos coeficientes tienen un valor “considerablemente”
menor que el resto, contribuyan poco al valor de Y.
Coeficientes de las funciones (cont…)
Sin embargo, esto no es del todo cierto, ya que las variables
(X1,…,Xn) suelen medir magnitudes muy diferentes y/o venir
expresadas en unidades distintas, lo cual dificulta su
comparación.
La solución es utilizar coeficientes estandarizados
(normalizados) los cuales se calculan en base a los valores
de los rasgos estandarizados. Los rasgos estandarizados no
dependen de las unidades de medida y se calculan en base
a la media y a la desviación estandar de cada rasgo. Estos
datos estadísticos, así como la normalización son funciones
que también son brindados por los softwares estadísticos
mencionados.
Ejemplo:
Clases
A (Objetos redondos)
B (Objetos semi-alargados)
C (Objetos alargados)
Rasgos
Diámetro Mayor
Diámetro Menor
Relación entre Diámetro Mayor y Diámetro Menor
En este caso, como ya se mencionó, hemos utilizado
dos rasgos (DMayor y DMenor) que no son
importantes para la clasificación de los objetos. El
rasgo importante es el tercero, cuyo valor nos da la
relación entre los dos diámetros.
El análisis discriminante, en su primera fase, nos
ayudará a determinar cuáles variables son
importantes y cuáles no.
Matriz de Aprendizaje (datos sin normalizar)
Al aplicar el Análisis Discriminante, obtenemos las
siguientes funciones (coeficientes de las funciones)
Fn1: redondo, Fn2 semi, Fn3: alarg
Classification Function Coefficients
Variable Fn 1 Fn 2 Fn 3
dia may -0.278 -0.261 -0.663
dia men 0.445 0.407 0.856
relac 9.292 11.436 30.420
Constant -7.915 -10.757 -64.582
Notar la diferencia significativa que existe entre los
coeficientes correspondientes a la variable relac, que
sabemos que es la importante y los coeficientes de las
otras dos variables, que sabemos que no son importantes
Esta interpretación puede ser incorrecta debido a que
los datos no están normalizados.
Notar que la unidad de medida de DMayor y DMenor,
es la misma, pero a su vez es diferente a la de Relac, por
tanto la magnitud de los coeficientes obtenidos va a
reflejar esta diferencia y por consiguiente su
interpretación en base a la magnitud puede ser
errónea.
Debemos normalizar los datos.
Los datos se normalizan, calculando la media y la
desviación estandar de cada rasgo y aplicando la
función de normalización:
norm(dato) = (dato-media)/desv_estandar
Matriz de Aprendizaje (datos normalizados)
Al aplicar el Análisis Discriminante, con los datos
normalizados, obtenemos las siguientes funciones
(coeficientes de las funciones)
Fn1: redondo, Fn2 semi, Fn3: alarg
Classification Function Coefficients
Variable Fn 1 Fn 2 Fn 3
dmay 2.917 3.327 -6.661
dmen -1.914 -2.529 4.716
relac -12.914 -9.174 23.933
Constant -5.458 -2.931 -14.709
En este caso, con los datos normalizados se mantiene la
diferencia significativa que existe entre los coeficientes
correspondientes a la variable relac, que sabemos que es la
importante y los coeficientes de las otras dos variables,
que sabemos que no son importantes
Puntuaciones Discriminantes
Clasificación
Son los resultados de evaluar cada una de las
funciones discriminantes para los valores de los
rasgos de un objeto en particular
En nuestro ejemplo, dado un objeto con sus rasgos,
se obtendrían tres puntuaciones discriminantes, ya
que tenemos tres clases y por tanto tres funciones
discriminantes que evaluar.
Puntuaciones Discriminantes
Clasificación
Para clasificar un nuevo objeto evaluamos cada una
de las funciones discriminantes (hay una función
para cada clase). Así obtenemos la Puntuación
Discriminante del objeto para cada clase
El objeto pertenecerá a la clase cuya función haya
dado como resultado La mayor puntuación
discriminante
Ejemplo:
Si queremos clasificar el objeto cuyos rasgos son:
DMay = 33, DMen = 14, Relac = 2.35
Evaluamos las tres funciones discriminantes
Variable Fn 1 Fn 2 Fn 3
dia may -0.278 -0.261 -0.663
dia men 0.445 0.407 0.856
relac 9.292 11.436 30.420
Constant -7.915 -10.757 -64.582
Obteniendo
PD1 = 11.05 PD2 = 13.27 PD3 = -2.78
Significa que el objeto pertenece a la clase 2
Regresión Lineal
Análisis de Regresión
Se ha demostrado que el Análisis Discriminante y la
Regresión Lineal Múltiple son
computacionalmente equivalentes, aunque parten
de ideas diferentes.
A través de la regresión lineal múltiple se determina
la influencia de un conjunto de variables
explicativas (independientes): x1, x2, …, xn, sobre
una variable variable dependiente Y.
Análisis de Regresión
Para aplicar el análisis de regresión múltiple al
problema de reconocimiento de patrones se
necesita que las clases estén representadas
mediante valores numéricos (valor de la variable
dependiente Y). Además de otras características
que deben cumplir de los valores de las variables
independientes (rasgos) (ver. regresión lineal
múltiple)
Análisis de Regresión
El resultado de la aplicación del análisis de regresión
múltiple a la matriz de aprendizaje es una única
función (independientemente de la cantidad de
clases:
Y = a0 + a1X1 + a2X2 + …. + anXn
Donde n: cantidad de rasgos
Lo que se obtiene del análisis de regresión son los
coeficientes a0 .. an.
Ejemplo (cráneos). Los datos corresponden a dos tipos raciales
diferentes en los que se practicaron diferentes medidas antropométricas
de longitudes, anchuras de cráneo y de cara. Datos recogidos sobre 24
cráneos en el Tibet.
Notar, que para aplicar
Regresión Lineal
debemos considerar las
clases como valores
numéricos.
Análisis de Regresión
Al aplicar la regresión lineal múltiple a la matriz de
aprendizaje anterior, obtenemos los coeficientes
de la función:
Análisis de Regresión
Clasificación
Para clasificar un objeto, se evalúa la función
obtenida utilizando los valores de los rasgos del
objeto.
El resultado de la función es número real, el cual
interpretamos como la clase, determinando la
clase (valor numérico de la clase) más cercana al
obtenido al evaluar la función.
Ejemplo:
Supongamos que queremos clasificar al objeto cuyos
rasgos son:
Longitud Anchura Altura [Link] .[Link]
192 141 137 74 132
Al evaluar la función
obtenemos:
Y = 1.5837
Este valor es mas cercano
a 2 que a 1, por tanto la
clase del objeto es la 2
Validación del clasificador
Para cualquier técnica de reconocimiento de
patrones es necesario validar la misma, realizando
una verificación de la clasificación con los objetos
de la matriz de aprendizaje y con un conjunto
adicional de objetos llamados de control, de los
cuales conocemos también sus clases.
En el ejemplo anterior, al clasificar cada objeto de la
matriz de aprendizaje, utilizando la función
obtenida al aplicar el análisis de regresión se
obtiene:
Notar que cuatro objetos están mal clasificados
Validación del clasificador
Para este mismo ejemplo, aplicando Análisis
Discriminante, se obtienen las siguientes
funciones:
En este caso, son tres los objetos que están mal clasificados
Validación del clasificador
En ambos casos los objetos mal clasificados son los
mismos
El número 5 y el 13, de la clase 1; y el 16, de la clase
2. En el caso del Análisis de Regresión, también el
19, de la clase 2.
Se requiere hacer un estudio para determinar por
qué el error en la clasificación. Puede ser un error
de los datos de la muestra ó que la técnica utilizada
no es la adecuada para el problema.