IAC2017-03 clasificacion_a4

Vista previa del material en texto

1.2. Error de clasificación.
Error de clasificación.
Es importante conocer cuán bien nuestro predictor funciona, una medida de la precisión del mismo es el error
de clasificación.
Error de clasificación definición formal.
Dado un conjunto de datos D = {(x1), ...,(xn)}, una estimación del error del predictor f̂ (x) en clasificación es:
error( f̂ ) =
Nerr
Ntot
. (1)
Donde Nerr es el número de clasificaciones erróneas de f̂ (x) sobre D y Ntot es el número total de datos
clasificados.
Error de clasificación.
Sean f̂ (xi) la etiqueta o clase asignada por de f̂ a un objeto xi 2 D y l(xi) la clase real asignada a ese objeto,
entonces:
error( f̂ ) =
1
Ntot
Ntot
Â
i=1
�
I(l(xi), f̂ (xi))
 
. (2)
Donde I(a,b) = 1 sii a 6= b.
1.3. Estimación del Error
Estimación del Error
Para estimar correctamente el error de un clasificador (estimación sin sesgo), se necesita un nuevo conjunto
de datos independiente de los que se usaron para aprender.
Como en la práctica se dispone casi siempre de un conjunto limitado de datos, se utilizan distintas estrategias
para realizar eficazmente las dos tareas (aprender y estimar el error).
Estimación del Error
Dado un conjunto de datos D con N ejemplos, algunos de los métodos más utilizados son:
Resubstitution:
Se entrena el clasificador con D y se lo evalúa con D . El error tiene sesgo optimista y no es confiable.
Hold-Out:
Se particiona D en dos subconjuntos. Se utiliza una parte para entrenar el clasificador y la otra para estimar el
error. Usualmente se repite el procedimiento varias veces para tener una estimación más confiable.
Estimación del Error
Bootstraps:
Se generan L subconjuntos de tamaño N eligiendo aleatoriamente y con repetición elementos de D . Se estima el
error utilizando los ejemplos no incluidos en cada repetición.
Leave-One-Out:
Corresponde a utilizar K-fold Cross Validation con k = N. Es decir, en N repeticiones el clasificador es entrenado
utilizando todos los datos excepto uno, al cual se lo utiliza para testear.
2
Estimación del Error
K-fold Cross Validation:
Se particiona D en k subconjuntos de igual tamaño y se utilizan k� 1 subconjuntos para entrenar y el restante
para evaluar. Esto se repite k veces, dejando para evaluar en cada repetición un subconjunto distinto.
Estimación del Error
En muchos métodos de aprendizaje es necesario ajustar el valor de algún parámetro libre, es este caso es
común utilizar tres conjuntos de datos en vez de dos.
El conjunto de entrenemiento: utilizado para entrenar el clasificador.
El conjunto de validación: actúa como una pseudo-prueba, el cual se utiliza para setear los parámetros libres
del clasificador.
El conjunto de prueba: queda oculto durante el proceso de entrenamiento y luego es utilizado para estimar
el error de clasificación sin sesgo.
2. Métodos Aprendizaje Supervisado en Clasificación.
2.1. Métodos Aprendizaje Supervisado en Clasificación.
Métodos Aprendizaje Supervisado en Clasificación.
Métodos de aprendizaje supervisado.
2.2. Árboles de Decisión.
Árboles de Decisión.
Es una técnica que permite analizar decisiones secuenciales basadas en el uso de resultados y probabilidades
asociadas. Nos ayudan a tomar la decisión más acertada, desde un punto de vista probabilístico, ante un abanico
de posibles decisiones.
Partes del Árbol.
Partes de un arbol de decisión.
3
Ejemplo de un arbol de decisión: Administrar el fármaco X?
Un ejemplo ejemplo de un arbol de decisión.
2.3. Árboles de Decisión en clasificación.
Árboles de Decisión en clasificación.
Los métodos de clasificación basados en árboles son frecuentes en estadística y reconocimiento de patrones.
Al ser fáciles de comprender, se tiende a confiar más en ellos que en otros métodos (por ejemplo redes
neuronales).
Partición jerárquica de los datos
Un árbol de clasificación particiona el espacio sobre el que están definidos los ejemplos de entrenamiento en
sub-regiones. En un árbol de decisión cada nodo del árbol es un atributo (variable) de los ejemplos, y cada rama
representa un posible valor de ese atributo.
Problemas de clasificación ideales.
Los ejemplos están representados por pares (atributo,valor) (xi,yi).
La función de clasificación tiene valores de salida discretos, y de ser posible booleanos.
Los ejemplos pueden contener errores, tanto por ruido presente en la recoleccion de los datos, como errores
en la clasificación de los ejemplos del conjunto de entrenamiento. Es aconsejable eliminar el ruido antes de
aplicar un árbol de clasificación.
Problemas de clasificación ideales ID3.
Se aplica una estrategia de búsqueda top-down, del tipo greedy en el espacio de búsqueda formado por todos
los árboles de decisión posibles. Al ser voraz, puede que conduzca a una solución óptima local en vez de
global.
Se comienza respondiendo a ¿qué atributo usamos como raíz para el árbol?
Esta cuestión se resuelve aplicando un test estadístico para averiguar cual de los atributos clasifica mejor
las instancias por sí solo. ID3 escoge la cantidad de información mutua como medida de evaluación de cada
atributo (ganancia de informacion).
4
Problemas de clasificación ideales ID3.
Se desarrolla una rama para cada posible valor.
En los nuevos nodos se vuelve a hacer la misma pregunta. Así hasta desarrollar un árbol completo (en la
versión básica).
Ejemplo de clasificación con el algoritmo ID3.
El algoritmo más utilizado es el ID3.
Datos disponibles para el entrenamiento del algoritmo ID3.
Ejemplo de clasificación con el algoritmo ID3.
El resultado de aplicar en su versión mas simple el algoritmo.
Arbol resultante del entrenamiento del algoritmo ID3.
ID3 - Cómo saber qué atributo clasifica mejor?
Entropía de un conjunto de ejemplos D. (clasificación)
Ent(D) =�
✓
|P|
|D| · log2
✓
|P|
|D|
◆◆
�
✓
|N|
|D| · log2
✓
|N|
|D|
◆◆
(3)
Donde P y N son, la cantidad de ejemplos positivos y negativos de D (Notación: Ent([p+;n�])).
Mide la ausencia de homegeneidad de la clasificación.
Ent([k+;k�]) = 1 (ausencia total de homogeneidad).
Ent([p+;0]) = Ent([0;n�]) = 0(homogeneidad total).
5
Ganancia de información.
Se prefiere nodos con menos entropía (árboles pequeños)
Entropría esperada después de usar un atributo A en el árbol:
.
Â
veValores(A)
Ent(Dv) (4)
Donde Dv es el subconjunto de ejemplos de D con valor del atributo A igual a v. Entonces:
Ent(Dv) =�
✓
|Pv|
|D| · log2
✓
|Pv|
|Dv|
◆◆
�
✓
|Nv|
|D| · log2
✓
|Nv|
|Dv|
◆◆
(5)
Ganancia de información.
Ganancia de información esperada después de usar A:
Ganancia(D,A) = Ent(D)�
.
Â
veValores(A)
Ent(Dv) (6)
En el algoritmo ID3, en cada nodo usamos el atributo con mayor ganancia de información (considerando
los ejemplos correspondientes al nodo).
6
2.4. Máquinas de vectores soportes.
Máquinas de vectores soportes.
Es una técnica de clasificación que aprende la superficie de decisión de dos clases distintas a partir de
los datos de entrada.
Caractirísticas de las SVM:
A despertado gran interés en la comunidad cientifica en estos últimos años.
Se desmostro en muchos trabajos que tienen mejor desempeño que los métodos de aprendizaje tradicional
como las redes neuronales.
Se basan en la minimización del riesgo estructural.
Máquinas de vectores soportes.
El método SVM busca el hiperplano que separa los ejemplos de 2 clases con máximo margen geométrico,
siendo ese su sesgo inductivo.
SVM hiperplanos de dos (figura a) y 3 dimensiones (figura b).
2.5. SVM caso linealmente separable.
SVM caso linealmente separable.
Supongamos un conjunto de entrenamiento D = {(xi,yi)}ni=1/xi 2 ¬p ^ yi 2 {�1,1}, donde cada ejemplo
o patrón de entrenamiento se encuentra etiquetado.
Asumimos además que los ejemplos son linealmente separables, esto es, que existe una función f̂ (x) =
w ·xi +b donde w 2 ¬p y b 2 ¬, tal que permita predecir correctamente la etiqueta de todos los ejemplos
cumpliendo con las siguientes reglas:
SVM caso linealmente separable.
w ·xi +b > 0 8yi = 1 (7)
w ·xi +b < 0 8yi =�1 (8)
Donde w ·x+b = 0 representa a un hiperplano de dimensión p�1que separa los ejemplos de las dos clases. Note
que w es el vector normal al hiperplano y b es un factor de desplazamiento (corrimiento) desde el origen hasta el
hiperplano.
7
SVM caso linealmente separable (ejemplo).
Tenemos un conjunto de datos linealmente separable y podemos encontrar infinitos hiperplanos que separen
correctamente los ejemplos positivos de los negativos.
Para poder encontrar el hiperplano óptimo las SVM buscan el hiperplano con máximo margen.
SVM caso linealmente separable (ejemplo).
Margen
Es la distancia entre el hiperplano y el ejemplo más cercano a él.
Vectores soporte
La ecuación del hiperplano estaría determinada por los puntos más cercanos a él, dichos puntos se denominan
vectores soporte.
SVM caso linealmente separable.
Margen geométrico
Es la distancia entre los ejemplos de ambas clases, es decir, la suma de la distancia del hiperplano al ejemplo más
próximo de cada clase, como se muestra en la Ecuación:
gg = min+(d(w,b;x+))+min�(d(w,b;x�)) (9)
SVM caso linealmente separable.
Entonces la maximización del margen geométrico se traduce en la minimización de la norma de w, obteniendo
el siguiente problema de optimización que se conoce como formulación primal de SVM:
mı́n
w,b
1
2
||w||2 (10)
sujeto a yi(w ·xi +b)� 1.
Esta solución es aplicable en los casos en que los datos son linealmente separables.
2.6. Truco del Kernel para el caso no linealmente separable
Truco del Kernel para el caso no linealmente separable
Supongamos ahora que tenemos un conjunto de datos que no son linealmente separables, una solución será
llevar cada dato a un espacio de mayor dimensión, mediante una transformación o kernel, y luego encontrar el
mejor híper plano capaz de dividir las clases en esta nueva representación.
Una fuerte base matemática permite asegurar que en un espacio lo suficientemente grande las clases serán
divisibles fácilmente y que el hiperplano encontrado es el mejor posible.
Truco del Kernel para el caso no linealmente separable
En la en la siguiente figura los datos en dos dimensiones son llevados a tres,aplicando una transformación,
para luego encuentrar fácilmente un híper plano que separa los datos.
8
Truco del Kernel para el caso no linealmente separable
La utilización de funciones kernels posibilita que problemas que no son linealmente separables en un espacio
de baja dimensión probablemente sí lo sean en un espacio de mayor dimensionalidad. Los tipos de kernels más
utilizados son:
Lineal: K(x,y) = x ·y
Polinomial: K(x,y) = (x ·y+1)p
Gaussiano: K(x,y) = e�
||x�y||2
2s2
3. Próxima Clase
Próxima Clase
1. Introducción al entorno R.
2. Descarga e instalación de R.
3. Instalación de librerías en R.
4. Ayuda en R.
5. Entrada y manipulación de datos.
6. Primeros ejercicios en R.
4. Bibliografía
Bibliografía
Vapnik, V. Statistical learning theory, 1998.
Cristianini, N., Shawe-Taylor, J. An introduction to support vector machines and other kernel-based learning
methods. Cambridge university press, 2000.
Quinlan, J. Ross, Induction of decision trees, Machine learning vol:1, 81-106, Springe 1986.
9