Vecino Mas Cercano

DEFINICION, SUS APLICACIONES Y EJEMPLO...

El algoritmo del vecino más próximo fue, en las ciencias de la computación, uno de los primeros algoritmos utilizados para determinar una solución para el problema del viajante. Este método genera rápidamente un camino corto, pero generalmente no el ideal.

Abajo está la aplicación del algoritmo del vecino más próximo al problema del viajante.

Estos son los pasos del algoritmo:

  1. elección de un vértice arbitrario respecto al vértice actual.
  2. descubra la arista de menor peso que ya este conectada al vértice actual y a un vértice no visitado V.
  3. convierta el vértice actual en V.
  4. marque V como visitado.
  5. si todos los vértices del dominio estuvieran visitados, cierre el algoritmo.
  6. vaya al paso 2.

La secuencia de los vértices visitados es la salida del algoritmo.

El algoritmo del vecino más próximo es fácil de implementar y ejecutar rápidamente, pero algunas veces puede perder rutas más cortas, que son fácilmente notadas con la visión humana, debido a su naturaleza más "ávida". Como norma general, si los últimos pasos del recorrido son comparables en longitud al de los primeros pasos, el recorrido es razonable; si estos son mucho mayores, entonces es probable que existan caminos mucho mejores.

El método del "vecino más cercano"

✔ Disponemos de una tabla resumen de tipo T(n,p)

✔ Los elementos de T(n,p) presentan una estructura de grupo
o de jerarquía de grupos encajados.
Aplicamos las etapas ya vistas del proceso de clasificación :
Primera etapa :
Con una distancia dij podemos evaluar la disimilaridad
entre los objetos a clasificar.
Podemos crear una tabla D(n,n), simétrica, que resume las
distancias entre los n objetos a clasificar, comparados dos a
dos.
Suponemos que es aceptable considerar que la distancia
entre dos clases que contienen un solo objeto cada una es
igual a la distancia entre los objetos:
( ) () { }{ } d d x,y I
x , y= x,y" Î
 
Segunda etapa :
Buscamos en la tabla D(n,n) el término extra-diagonal mínimo, es decir el valor d( ) () { }{ } x , y
=d x,y mínimo.
Formamos una nueva clase que reagrupa esos dos objetos: { }xy { }y .
Iteración :
Se recomienza a partir de la primera etapa, pero ahora sólo
con n - 1 objetos a comparar, puesto que una clase contiene
ahora dos objetos.Programa PRESTA - 1999 - Eduardo CRIVISQUI Tr. N°23
Para calcular la Tabla D’(n-1, n-1) correspondiente a la nueva
situación debemos darnos un criterio para calcular la distancia
entre una clase que contiene dos objetos y las clases restantes
que sólo contienen un objeto.
La estrategia de agregación responde a ese problema...
La estrategia del «vecino más cercano» consiste en elegir como
distancia entre la clase{ } x;y y la clase { }k la más pequeña de las
dos distancias siguientes:
d( ) { }{ } x , k
 o bien d( ) { }{ } y , k
En cada etapa t de iteración del proceso de agregación por el
método del «vecino más cercano», la Tabla D(n-t, n-t) es
construida con la siguiente distancia ultramétrica :
Los términos diagonales de D(n,n) son nulos, puesto que, si
dijo es una distancia : ( ) () { }{ } d d 0 x I
 
 
✔ Ventaja del método : simplicidad de cálculo. No requiere el
cálculo de la matriz Dt (n-t, n-t) en cada etapa de agregación.
✔ Inconveniente del método : tiene tendencia a producir un
«efecto de encadenamiento»

ALGORITMO

Los ejemplos de entrenamiento son vectores en un espacio característico multidimensional, cada ejemplo está descrito en términos de p atributos considerando q clases para la clasificación. Los valores de los atributos del i-esimo ejemplo (donde 1\le i\le n) se representan por el vector p-dimensional

x_i=(x_{1i}, x_{2i}, ..., x_{pi}) \in X

El espacio es particionado en regiones por localizaciones y etiquetas de los ejemplos de entrenamiento. Un punto en el espacio es asignado a la claseC si esta es la clase más frecuente entre los k ejemplos de entrenamiento más cercano. Generalmente se usa la Distancia euclideana.

d(x_i,x_j)=\sqrt{\sum_{r=1}^p(x_{ir}-x_{jr})^2}

La fase de entrenamiento del algoritmo consiste en almacenar los vectores característicos y las etiquetas de las clases de los ejemplos de entrenamiento. En la fase de clasificación, la evaluación del ejemplo (del que no se conoce su clase) es representada por un vector en el espacio característico. Se calcula la distancia entre los vectores almacenados y el nuevo vector, y se seleccionan los k ejemplos más cercanos. El nuevo ejemplo es clasificado con la clase que más se repite en los vectores seleccionados.

Este método supone que los vecinos más cercanos nos dan la mejor clasificación y esto se hace utilizando todos los atributos; el problema de dicha suposición es que es posible que se tengan muchos atributos irrelevantes que dominen sobre la clasificación: dos atributos relevantes perderían peso entre otros veinte irrelevantes.

Para corregir el posible sesgo se puede asignar un peso a las distancias de cada atributo, dándole así mayor importancia a los atributos más relevantes. Otra posibilidad consiste en tratar de determinar o ajustar los pesos con ejemplos conocidos de entrenamiento. Finalmente, antes de asignar pesos es recomendable identificar y eliminar los atributos que se consideran irrelevantes.

En síntesis, el método k-nn se resumen en dos algoritmos:

Algoritmo de entrenamiento

Para cada ejemplo <x, f(x)> ,donde x \in X, agregar el ejemplo a la estructura representando los ejemplos de aprendizaje.

Algoritmo de clasificación

Dado un ejemplar x_q que debe ser clasificado, sean x_1,..., x_k los k vecinos más cercanos a x_q en los ejemplos de aprendizaje, regresar

\hat{f}(x) \leftarrow argmax_{v \in V} \sum_{i=1}^k\delta(v,f(x_i))

donde

\delta(a,b)=1\mbox{ si } a=b; \mbox{ y } 0 \mbox{ en cualquier otro caso.}

el valor \hat{f}(x_q) devuelto por el algoritmo como un estimador de f(x_q) es solo el valor más común de f entre los k vecinos más cercanos a x_q. Si elegimos k=1; entonces el vecino más cercano a x_i determina su valor.


EJEMPLO 1:

 

Problema Clásico del Vendedor Viajero - Algoritmo del Vecino más Cercano - Circuito Hamiltoniano

 
Problema Clásico del Vendedor Viajero:
 
Un vendedor viajero debe visitar 5 ciudades para vender en ellas. Está al comienzo en una de las ciudades a visitar. La red muestra las tarifas más baratas disponibles entre cada par posible de ciudades, en ambas direcciones:
 
En la figura cada ciudad es un nodo signado con las letras: W (punto de partida), P, C, S y A.
 
Necesitamos encontrar una ruta que comience en "W" y que pase exactamente una vez por cada uno de los nodos y vuelva a "W". Cualquier ruta que pase por cada nodo exactamente una vez y termine en el punto de partida se le conoce como "Circuito Hamiltoniano".
 
Existe un método conocido como "Método de la Fuerza Bruta" que consiste en evaluar cada uno de los Circuitosa Hamiltonianos posibles y para encontrar por comparación el que sea más barato.
 
Por ejemplo Ud. puede comparar: WPCSAW y WPCASW y ver que el segundo:
 
WPCASW: 74 + 98 + 104 + 149 + 105 = 530 es más caro que el primero ....
 
Solución Técnica es conocida como el "Algoritmo del Vecino más cercano"
 
1) Escoja un nodo como punto de partida.
2) Desde ese nodo de partida recorra hasta el nodo que tiene la tarifa más barata. Llamaremos a este nodo el vecino más cercano. Si existe otro con igual tarifa escoja uno de los dos en forma arbitraria.
3) Repita el proceso con un nodo a la vez, viajando a los nodos que aun no han sido visitados. Continúe con este procedimiento hasta que todos los nodos han sido visitados.
4) Complete un Circuito Hamiltoniano regresando al punto de partida.
5) Calcule el costo del circuito.

EJEMPLO 2:

 
 

 

U

RUTA

W

V ´

INICIO

-

C

0

C

 

D

CD

3

D

 

A

CDA

11

A

 

B

CDAB

16

B

FINAL

C

CDABC

23

C


 

EJEMPLO 3:

 

U

RUTA

W

V ´

INICIO

-

A

0

A

 

C

AC

3

C

 

E

ACE

5

E

 

D

ACED

12

D

 

B

ACEDB

14

B

Final

A

ACEDBA

24

A


 

EJEMPLO 4:

 

U

RUTA

W

V ´

INICIO

-

S

0

S

 

C

SC

2

C

 

E

SCE

10

E

 

T

SCET

13

T

 

D

SCETD

19

D

 

B

SCETDB

24

B

 

S

SCETDBS

28

S