3.4 Aprendizaje No Bool - Vecino + Cercano 2011 (42)

Aprendiendo con valores no booleanos

El hombre bueno, del buen tesoro del corazón saca buenas cosas; y el hombre malo, del mal tesoro saca malas cosas

JesucristoMt.12.35

Espacio de atributos Los atributos pueden ser mucho mas

complejos Opciones frente a un conjunto discreto

grande Si el conjunto no es ordenado (por ejemplo

4 diferencias que tienen los carros), use atributos binarios para codificar los valores(1000, 0100, 0010, 0001)

Si el conjunto es ordenado, trátelo como valores reales

Espacio de atributos Los atributos pueden ser mucho mas

complejos Opciones frente a un conjunto discreto

grande Si el conjunto no es ordenado (por ejemplo

4 diferencias que tienen los carros), use atributos binarios para codificar los valores(1000, 0100, 0010, 0001)

Si el conjunto es ordenado, trátelo como valores reales

Valores reales: trate que las entradas cuyos atributos tiene valores “cercanos” vayan a tener salidas “cercanas”

Prediciendo la bancarrotaL R B3 0.2 No1 0.3 No4 0.5 No2 0.7 No0 1.0 No1 1.2 No1 1.7 No6 0.2 Si7 0.3 Si6 0.7 Si3 1.1 Si2 1.5 Si4 1.7 Si2 1.9 Si

0 0.5 1 1.5 2 R

8765

L 43210

Si No

L: # de pagos tardíos / añoR: gastos / ingresos

El querido vecino cercano Recuerde todos sus datos Cuando alguien hace una consulta

• Encuentre el viejo punto de datos mas cercano

• Retorne la respuesta asociada con el

?

Qué significa el “más cercano”? Se necesita una función de la distancia en

las entradas Típicamente usamos distancia Euclidiana

(longitud de una línea recta entre dos puntos)

• D(xi, xk) = √Σ(xij,- xk

j) j

Qué significa el “más cercano”?

Se necesita una función de la distancia en las entradas

Típicamente usamos distancias Euclidianas (longitud de una línea recta entre dos puntos)

• D(xi, xk) = √Σ(xij, xk

j)• j

La distancia entre cadenas de caracteres podría ser el número de ediciones requeridas para cambiar el uno en otro (Ej. Cadenas de DNA).

Escalamiento Que pasa si tratamos de predecir el

kilometraje de combustible de un carro?• F1 = peso en libras• F2 = número de cilindros

Escalamiento Que pasa si tratamos de predecir

el consumo de combustible de un carro?

• F1 = peso en libras (cientos)• F2 = numero de cilindros(4 y 8)

Cualquier efecto de F2 estará completamente perdido debido a la escala relativa.

Escalamiento Que pasa si tratamos de predecir el

consumo de combustible de un carro?• F1 = peso en libras• F2 = numero de cilindros

cualquier efecto de F2 estará completamente perdido debido a la escala relativa

Por tanto re- escalamos las entradas

Escalamiento Que pasa si tratamos de predecir el

consumo de combustible de un carro?• F1 = peso en libras• F2 = numero de cilindros

Cualquier efecto de f2 estará completamente perdido debido a la escala relativa

Por tanto re- escalamos las entradas X’= (X – X) / σX

PROMEDIO

DESVIACIÓN ESTANDARD

√varianza

Prediciendo la bancarrota

0 0.5 1 1.5 2 R

8765

L 43210

Si No

D(xi, xk) = √Σ(Li - Lk)2 + (5Ri - 5Rk) 2

j  

Prediciendo la bancarrota

0 0.5 1 1.5 2 R

8765

L 43210

Si No

D(xi, xk) = √Σ(Li - Lk)2 + (5Ri - 5Rk) 2

j  

R=0.3L=2Y?

Prediciendo la bancarrota

0 0.5 1 1.5 2 R

8765

L 43210

Si No

D(xi, xk) = √Σ(Li - Lk)2 + (5Ri - 5Rk) 2

j  

Prediciendo la bancarrota

0 0.5 1 1.5 2 R

8765

L 43210

Si No

D(xi, xk) = √Σ(Li - Lk)2 + (5Ri - 5Rk) 2

j  

Prediciendo la bancarrota

0 0.5 1 1.5 2 R

8765

L 43210

Si No

D(xi, xk) = √Σ(Li - Lk)2 + (5Ri - 5Rk) 2

j  

Prediciendo la bancarrota

0 0.5 1 1.5 2 R

8765

L 43210

Si No

D(xi, xk) = √Σ(Li - Lk)2 + (5Ri - 5Rk) 2

j  

Prediciendo la bancarrota8765

L 43210

Si No

D(xi, xk) = √Σ(Li, Lk)2 + (5Ri - 5Rk) 2

j  

0 0.5 1 1.5 2 R

la hipótesis? Es diferente porque no se esta construyendo

HipótesisSi No

0 0.5 1 1.5 2 R

8765

L 43210

D(xi, xk) = √Σ(Li - Lk)2 + (5Ri - 5Rk) 2

j  

HipótesisSi No

0 0.5 1 1.5 2 R

8765

L 43210

D(xi, xk) = √Σ(Li - Lk)2 + (5Ri - 5Rk) 2

j  

Tiempo y espacio El aprendizaje es rápido

Solo hay que recordar

Tiempo y espacio Aprendizaje es rápido Buscar toma cerca de m*n cálculos

• M= cantidad de puntos en el conj de entrenamiento• N= cantidad de atributos

Almacenar datos en un ingenioso estructura de datos(árbol KD ) reduce esto en promedio a log(m)*n

Tiempo y espacio Aprendizaje es rápido Buscar toma cerca de m*n cálculos

Almacenar datos en un ingenioso estructura de datos(árbol KD ) reduce esto en promedio a log(m)*n

Memoria pude saturarse con todos los datos

Tiempo y espacio Aprendizaje es rápido Buscar toma cerca de m*n cálculos

Almacenar datos en un ingenioso estructura de datos(árbol KD ) reduce esto en promedio a log(m)*n

Memoria pude saturarse con todos los datos Borre los puntos que están lejos de las fronteras

Ruido

0 0.5 1 1.5 2 R

8765

L 43210

Al menos dos formas de tratar con esta situación

Si No

Ruido

0 0.5 1 1.5 2 R

8765

L 43210

consulta

Si No

Ruido

0 0.5 1 1.5 2 R

8765

L 43210

consulta

Si No

Ruido

0 0.5 1 1.5 2 R

8765

L 43210

Cambiando el algoritmo a k vecinos más cercanos. Encontrando los k puntos mas cercanos

Si No

Ruido

0 0.5 1 1.5 2 R

8765

L 43210

Encontrando los k puntos mas cercanosPrediciendo la salida de acuerdo a la mayoría

Si No

Ruido

0 0.5 1 1.5 2 R

8765

L 43210

Encontrando los k puntos mas cercanosPrediciendo la salida de acuerdo a la mayoríaEscoja k con validación cruzada

Si No

Curso de dimensionalidad El vecino más cercano trabaja bien con

dimensiones bajas (cerca de 6) Cuando n se incrementa, las cosas se ponen

raras:

Curso de dimensionalidad El vecino mas cercano trabaja bien en

dimensiones bajas (cerca de 6) y espacios con valores reales.

Cuando n se incrementa, las cosas se ponen raras: En la alta dimensión, casi todos los puntos están

lejos uno de otro. Ellos casi siempre están cerca de la frontera.

Curso de dimensionalidad El vecino mas cercano es mayor en dimensiones

bajas (cerca de 6) Cuando n se incrementa, las cosas se ponen raras:

En la alta dimensión, casi todos los puntos están lejos uno de otro.

Ellos casi siempre están cerca de la frontera.

Imagine los puntos datos dispersos uniformemente en un cubo de 10 dimensiones

Para capturar 10% de los puntos, necesitará un cubo con lados .63!

Remedio: seleccione los atributos o los modelos más globales.

Evaluación del domino Enfermedades cardíacas: predecir si una

persona tiene una limitación significativa en las arterias, basada en los exámenes 26 atributos 297 puntos datos

Evaluación del domino Enfermedades cardíacas: predecir si una

persona tiene una limitación significativa en las arterias, basada en los exámenes 26 atributos 297 puntos dato

Carro MPG: predecir si un auto hace mas de 22 millas por galón, basado en atributos del carro 12 atributos 385 puntos dato

Enfermedad cardiaca Relativamente insensible a k

10.8

0.6

0.40.20

0 20 40 K

Exactitud de la validación cruzada del vecino mas cercano sobre datos de enfermedades cardiacas.

Exactitud de clasificación

Afectación del corazón Relativamente insensible a k Importancia de la normalización

Normalizada10.8

0.6

0.40.20

0 20 40 k

Carro MPG Relativamente insensible a k Normalización no importa mucho

10.8

0.6

0.40.20

0 20 40 k

Carro MPG Ahora la normalización importa mucho Observe la escala de sus grafos

Normalizada

0.950.93

0.91

0.890.870.85

0 20 40 K

Tomado del Instituto Tecnológico de Massachusetts www.owc.mit.edu6.034 Artificial Intelligence 2004

Archivo: ch6-mach2.pdf

Ejercicios1.- Este problema trata con datos de entrada que tienen un solo atributo “x”. La salida es de dos clases, dada por los valores “y”. Se presenta la siguiente tabla de valores.

Responda: Cuál sería la salida cuando x=9?

a. Con el K-Vecino más cercano (K-VC), cuando k=1?

b. Y Cuándo K-VC=5?

x y1 02 13 14 06 17 110 011 1

2.- Represente los siguientes datos en un plano cartesiano:Negativos: (-1, 0), (2, 1), (2, -2) Positivos(0, 0), (1, 0)a) Dibuje la línea divisoria para 1- Vecino más Cercano.b) Cómo se predeciría con 1-VC este nuevo punto: (1, -1.01). Explique por qué?