• Author / Uploaded
• ReyesArangurenJuan

Citation preview

UNIVERSIDAD AUTONOMA DE BUCARAMANGA

FACULTAD DE INGENIERIAS FISICO-MECANICAS

INTELIGENCIA ARTIFICIAL

CARLOS ARIZMENDI

INGENIERIA MECATRONICA

ANDRES FELIPE CASTRO MANZANO

U00098705

JUAN SEBASTIAN REYES ARANGUREN

U00097351

2018

Laboratorio 1 Clasificación usando vecinos cercanos (nearest neighbors) Distancia pairwise Categorizando puntos de consulta basados en su propia distancia a puntos en conjuntos de datos de entrenamiento que pueden ser caminos efectivos de nuevos puntos clasificados aún más simples. Se pueden usar varias métricas para determinar la distancia. Distancia métrica Dada una matriz de datos 𝑋 𝑚𝑥 − 𝑏𝑦 − 𝑛, la cual es tratada como fila de vectores 𝑚𝑥 (1 − 𝑏𝑦 − 𝑛) y matriz de datos 𝑌 𝑚𝑦 − 𝑏𝑦 − 𝑛, la cual es tratada como fila de vectores 𝑚𝑦 (1 − 𝑏𝑦 − 𝑛), las varias distancias entre el vector 𝑥𝑠 y 𝑦𝑡 son definidos de la siguiente manera: Distancia Euclidean 𝒅𝟐𝒔𝒕 = (𝒙𝒔 − 𝒚𝒕 )(𝒙𝒔 − 𝒚𝒕 )’ La distancia euclidean es un caso especial de la métrica de minkowski, donde 𝑝 = 2 Distancia euclidean estandarizada 𝒅𝟐𝒔𝒕 = (𝒙𝒔 − 𝒚𝒕 )𝑽−𝟏 (𝒙𝒔 − 𝒚𝒕 )’ Donde 𝑉 es la matriz diagonal 𝑛 − 𝑏𝑦 − 𝑛 cuyo elemento diagonal 𝑗𝑡ℎ es 𝑆(𝑗)2 Donde 𝑆 es el vector contenido de pesos inversos. Distancia de Mahalanobis 𝒅𝟐𝒔𝒕 = (𝒙𝒔 − 𝒚𝒕 )𝑪−𝟏 (𝒙𝒔 − 𝒚𝒕 )’ Donde C es la matriz de covarianza Métrica City block 𝒏

𝒅𝒔𝒕 = ∑|𝒙𝒔𝒋 − 𝒚𝒕𝒋 | 𝒋=𝟏

La distancia city block es un caso especial de la métrica de minkowski, donde 𝑝 = 1 Métrica de Minkowski 𝒑

𝒏

𝒅𝒔𝒕 = √∑|𝒙𝒔𝒋 − 𝒚𝒕𝒋 |

𝒑

𝒋=𝟏

Para el caso especial de 𝑝 = 1, la métrica de minkowski da la métrica city block, para el caso especial de 𝑝 = 2, la métrica minkowski da la distancia euclidean, y para el caso especial de 𝑝 = ∞, la métrica de minkowski da la distancia de chebychev.

Distancia de Chebychev 𝒅𝒔𝒕 = 𝒎𝒂𝒙𝒋 {|𝒙𝒔𝒋 − 𝒚𝒕𝒋 |} La distanci de Chebychev es un caso especial de la métrica de minkowski, donde 𝑝 = ∞ Distancia coseno 𝒅𝒔𝒕 = (𝟏 −

𝒙𝒔 𝒚′𝒕

) √(𝒙𝒔 𝒙′𝒔 )(𝒚𝒕 𝒚′𝒕 )

Distancia de correlación 𝒅𝒔𝒕 =

̅𝒔 )(𝒚𝒕 − 𝒚 ̅𝒕 )′ (𝒙𝒔 − 𝒙 ̅𝒔 )(𝒙𝒔 − 𝒙 ̅𝒔 )′√(𝒚𝒕 − 𝒚 ̅𝒕 )(𝒚𝒕 − 𝒚 ̅𝒕 )′ √(𝒙𝒔 − 𝒙

Donde 𝑥̅ =

1 ∑ 𝑥𝑠𝑗 𝑛 𝑗

Y 𝑦̅ =

1 ∑ 𝑦𝑡𝑗 𝑛 𝑗

Distancia Hamming 𝒅𝒔𝒕 = (#(𝒙𝒔𝒋 ≠ 𝒚𝒕𝒋 )/𝒏) Distancia Jaccard 𝒅𝒔𝒕 =

#[(𝒙𝒔𝒋 ≠ 𝒚𝒕𝒋 ) ∩ ((𝒙𝒔𝒋 ≠ 𝟎) ∪ (𝒚𝒕𝒋 ≠ 𝟎))] [(𝒙𝒔𝒋 ≠ 𝟎) ∪ (𝒚𝒕𝒋 ≠ 𝟎)]

Distancia Spearman 𝒅𝒔𝒕 = 𝟏 −

(𝒓𝒔 − 𝒓̅𝒔 )(𝒓𝒕 − 𝒓̅𝒕 )′ √(𝒓𝒔 − 𝒓̅𝒔 )(𝒓𝒔 − 𝒓̅𝒔 )′√(𝒓𝒕 − 𝒓̅𝒕 )(𝒓𝒕 − 𝒓̅𝒕 )′

𝑟𝑠𝑗 Es un rango de 𝑥𝑠𝑗 , que es computado por tiedrank 𝑟𝑡𝑗 Es un rango de 𝑦𝑡𝑗 , que es computado por tiedrank 𝑟𝑠𝑗 Y 𝑟𝑡 son vectores del rango de coordenadas prudentes de 𝑥𝑠 y 𝑦𝑡 𝒓̅𝒔 =

𝟏 (𝒏 + 𝟏) ∑ 𝒓𝒔𝒋 = 𝒏 𝟐 𝒋

𝒓̅𝒕 =

𝟏 (𝒏 + 𝟏) ∑ 𝒓𝒕𝒋 = 𝒏 𝟐 𝒋

Búsqueda k-Nearest Neighbor (kNN) y búsqueda de radio Permite encontrar puntos cercanos k en X para puntos de consulta o conjunto de puntos Y dada un conjunto X de puntos n y una función de distancia. La técnica de búsqueda kNN y los algoritmos basados en kNN son ampliamente usados como puntos de referencia en reglas de aprendizaje. La técnica ha sido usada en varias áreas como: Bioinformacion Procesamiento de imagen y compresión de datos Recuperación de documentos Visión computacional Base de datos multimedia Análisis de datos de marketing También se puede usar la búsqueda kNN muchas funciones de distancia basadas en aprendizaje, como K-means clustering. Búsqueda k-Nearest Neighbor usando búsqueda exhaustiva Cuando los datos de entrada se encuentran cualquiera de los siguientes criterios, la búsqueda knn usa el método de búsqueda exhaustiva por defecto para encontrar el k-NN: El número de columnas de X es más de 10 X es escaso La medida de distancia es cualquiera: -

‘seuclidean’ ‘mahalanobis’ ‘coseno’ ‘correlación’ ‘spearman’ ‘hamming’ ‘jaccard’

Una función de distancia personalizada La búsqueda k-NN también usa el método de búsqueda exhaustiva si su objeto búsqueda es un objeto de buscador exhaustivo. Este método busca la distancia entre cada punto de consulta en X, clasifica en orden ascendente, y regresa los puntos k con distancias pequeñas. Ejemplo con k=3

Búsqueda k-Nearest Neighbor usando un árbol kd (kd-Tree) Cuando los datos de entrada se encuentran cualquiera de los siguientes criterios, la búsqueda knn usa un árbol kd por defecto para encontrar el k-NN: El número de columnas de X es menos que 10 X no es escaso La medida de distancia es cualquiera: -

´euclidean´ (default) ´cityblock´ ´minkowski´ ´chebychev’

La búsqueda k-NN también usa un árbol kd si su objeto de búsqueda es un objeto de buscador de árbol kd. Ejemplo

¿Que son los objetos de búsqueda? Básicamente, objetos que almacenan información de manera conveniente. Clases de objetos relacionados tienen las mismas propiedades con valores y tipos relevantes para un método de búsqueda específico. Para determinar cual tipo de objeto y método de búsqueda es el mejor para los datos, considerar las consideración previamente vistas en los anteriores métodos. Clasificación de datos de consulta usando búsqueda k-NN Código en matlab load fisheriris %carga la base de datos de iris x = meas(:,3:4); gscatter(x(:,1),x(:,2),species)%crea diagrama de dispersi?n de los vectores en x set(legend,'location','best') newpoint = [5 1.45]% Creamos un punto con esas cordenadas line(newpoint(1),newpoint(2),'marker','x','color','k','markersize',10,'linewidth',2)%cre a una marca en forma de X color negro tama?o 10px y grosor de la line 2px [n,d] = knnsearch(x,newpoint,'k',10);%Guardamos en un vector el numero y la distancia de los vecinos cercanos line(x(n,1),x(n,2),'color',[.5 .5 .5],'marker','o','linestyle','none','markersize',10)% Crea una marca en forma de circulo con tama?o 10 px y sin estilo de linea y color en rgb como gris x(n,:) set(gca,'xlim',[4.5 5.5], 'ylim',[1 2]); axis square %Definimos la region que queremos visualizar en coordenadas y de forma cuadrada tabulate(species(n)) %Crea una tabla de el tipo de iris la cantidad y el porcentaje con respecto a las 10 que estan cerca ctr = newpoint - d(end);%Calcular el centroide de lo que evaluaremos diameter = 2*d(end);%Definir el diametro a dibujar mediante el mas lejano. h = rectangle('position',[ctr,diameter,diameter],'curvature',[1 1]);%Dibuja un circulo al rededor de los 10 vecinos cercanos. set(h,'linestyle',':')% parametros para dibujar h y que sea punteado

figure newpoint2 = [5 1.45;6 2;2.75 .75];%Creamos 3 puntos mas a graficar gscatter(x(:,1),x(:,2),species)%crea diagrama de dispersi?n de los vectores en x legend('location','best') [n2,d2] = knnsearch(x,newpoint2,'k',10);%Guardamos los vecinos mas cercanos y la distancia de ellos line(x(n2,1),x(n2,2),'color',[.5 .5 .5],'marker','o','linestyle','none','markersize',10) %Marcamos cada vecino cercado a los puntos generados line(newpoint2(:,1),newpoint2(:,2),'marker','x','color','k','markersize',10,'linewidth', 2,'linestyle','none')%Marcar con una x los puntos generados tabulate(species(n2(1,:)))%Crea con respecto a las 10 que estan tabulate(species(n2(2,:)))%Crea con respecto a las 10 que estan tabulate(species(n2(3,:)))%Crea con respecto a las 10 que estan

una tabla cerca del una tabla cerca del una tabla cerca del

de el tipo de iris la cantidad y el porcentaje primer punto de el tipo de iris la cantidad y el porcentaje segundo punto de el tipo de iris la cantidad y el porcentaje tercer punto

Resultado de la ventana de comando de matlab newpoint =

5.0000

1.4500

ans =

5.0000

1.5000

4.9000

1.5000

4.9000

1.5000

5.1000

1.5000

5.1000

1.6000

4.8000

1.4000

5.0000

1.7000

4.7000

1.4000

4.7000

1.4000

4.7000

1.5000

Value

Count Percent

virginica

2

versicolor Value

8

2

versicolor

virginica Value

80.00%

Count Percent

virginica

Value

20.00%

8

20.00% 80.00%

Count Percent 10

100.00%

Count Percent

versicolor

7

70.00%

setosa

3

30.00%

Conclusiones -

1. 2. 3.