Resumen 2.0 Robocup

Presentación Final - Fractales.

La siguiente presentación se realizó referente al tema de fractales, explicando el fractal de Von Koch, basándonos en las publicaciones de Daniel Shiffman creador del Libro Nature Of Code.

Resumen Robocup - Práctica 4

Robocup, es un proyecto internacional fundado en 1997, creado para fomentar la educación e investigación de la inteligencia artificial. La competencia es la principal motivación realizadas por robots autónomos.

Su principal objetivo del RoboCup es la formación de equipos capaces de ganar el campeonato, cada ajente (jugador) deben trabajar en conjunto con ayuda de la inteligencia artificial.

La Robocup esta dividida en 4 categorías principales:
Soccer: Competencia de futbol con robots, puede ser de simulación (virtual), robots humanoides o robos cuadrupedos, de diferentes tamaños.
Rescue:  Pruebas de de robots para hacer búsquedas o salvar victimas.
Junior: Competencias para niños de primaria y secundaria.
@home: Competencia que centra la aplicación de robots interactuando en el hogar.

Avance 1 - Fractales

A continuación se mostrará una breve presentación acerca de la creación de arte con fractales, como evidencia para el primer avance de la práctica 3, del laboratorio de Sistemas Adaptativos.

Reporte Practica 2: K-Means

♦ Introducción

Agrupamiento viene de la acción de acomodar personas, lugares o cosas estrechamente relacionados por alguna similitud como puede ser por ejemplo color, forma, característica cualitativa y cuantitativa, entre otras, además los estos grupos que saldrán a partir de este análisis no se conocen de antemano, tal vez se sabrá cuantos grupos que querrán formar pero no que grupos son o con que características.

Un algoritmo clásico de agrupamiento es el K-means el cual toma una serie de vectores candidatos, y a partir de K Centroides (numero de vectores de que representan cuantos grupos se quieren obtener) se van obteniendo  la similitud (distancia)  entre cada vector con todos los centroides para sabes cuales vectores están más cercanos a cada centroide, después por cada centroide calcular la Media entre los vectores más cercanos y así obtener un nuevo valor de los centroides.

Nuestro análisis consiste en deportes de cualquier tipo, para ello se analizan diversas características de los de tal manera que cualquier deporte puede ser tomado en cuenta para tratar de agruparlos. Se tomara en cuenta todas aquellas características como el área donde se juega, las reglas, numero de jugadores, entre muchas otras.

En la entrada se hablará un poco más a fondo acerca del algoritmo de K-means, agrupamiento además de realizar en el contexto de los deportes el agrupamiento de K-means por medio de un programa, se anezaran resultados y conclusiones al respecto de este algoritmo. 

♦ Marco teórico

Agrupamiento (en inglés Clustering) es juntar cosas por algún razgo de similaridad. Los grupos constan cada uno por alguna característica y los elementos que se almacenan en cada grupo comparten una característica la cual los hace ser similares en algo. En nuestro contexto tipo de agrupamiento "ideal" debería ser por  traslape (overlapping) ya que los deportes pueden caer en varias categorías y no se cierran únicamente a  alguna en especial. Sin embargo, el algoritmo de K-means se basa en tipo de agrupamiento disjunto el cual también se le conoce como particional que quiere decir que cada grupo esta separado entre si, de tal manera que no comparten características.

Por ahora se dice que el K-means trabaja con vectores, estos vectores son llamados vectores características los cuáles en este algoritmo también son llamados Puntos ya que cada elemento de este vector es tomado como una coordenada en un plano aunque si llegan a ser más de tres coordenadas es difícil poderse graficar sin embargo existen algoritmos los cuales 3 o más coordenadas las pasa a ser solo dos y así poder graficar sin embargo no es la intención de esta entrada. Bien, los vectores características (como tal vez es algo lógico), contiene en cada elemento del vector una característica de aquello que se quiera agrupar, más adelanta quedará un poco más claro.

Algoritmo General de K-means trabaja de esta manera:

1.Se seleccionan K objetos, serán el total de grupos.

2.Calcular las Distancias (Cosenoidal, Euclidiana), entre todos los puntos con cada uno de los centroides.

3.Los puntos se asignan a aquellos grupos donde la distancia es mínima, respecto a los centroides.

4.Actualizar centroides con la medio de los objetos asignados a cada centroide.

5. Se realiza de nuevo el paso uno hasta que se cumpla un critero (umbral).

Una forma más particular del algoritmo se presenta a continuación:

se tienen K cantidad de centroides y sus coordenadas son elegidas al azar digamos en por ahora 2 centroides entonces el valor de K es 2 los centroides son denotados por Ci(x1,x2, ...xn) y se tienen 4 puntos Pj(x1,x2, ...xn) entonces se tiene que sacar la distancia entre cada punto y cada centroide por medio de la distancia euclidiana la cual se obtiene con la siguiente formula:

Distancia euclidiana entre los puntos P y Q imagen obtenida de Wikipedia véase para más información

esta formula se tiene que seguir con el primer centroide y todos los puntos para sacar las distancias euclidianas, así como con el segundo centroide y los mismos 4 puntos.Al terminar esta tarea se comparan los resultados de las distancias euclidianas de cada punto obtenias con el primer y segundo centroide, entonces se enfrentan los las distancias euclidadanadas obtenidas digamos del punto P1 con el centroide C1 y P1 con el centroide C2 entonces la menor distancia entre los dos resultados define con que centroide se va el punto, este proceso se repite con todos los puntos. Después de esto se tiene que recalcular el centroide, para ello se tiene que realizar un la siguiente ecuacion, 

Cj(x)=(parte x de los puntos que se quedaron con Cj)/(numero de puntos que se quedaron con Cj)

y Cj(y)=(parte y de los puntos que se quedaron con Cj)/(numero de puntos que se quedaron con Cj).

de igual manera si se tienen más características.

Esto se hace esto para calcular el nuevo C1 y C2. Para la siguiente iteración se tienen que utilizar los mismos

puntos y los nuevos centroides y repetir el procedimiento hasta cumplir algún criterio por ejemplo que la el valor del centroide nuevo con al anterior sea realmente muy pequeña. (Umbral).

♦ Desarrollo
Contexto de agrupamiento
    *Deportes
Vectores de características.

Los caracteristicas de los vectores:

Contexto a desarrollar: agrupamiento de deportes
c[0] = Gana mayor o menor puntaje? ejemplo Gana Mayor 2 Gana Menor 1
c[1] = Se desenvuelve en un solo tipo de espacio?  si 2 no 1
c[2] = se desenvuelve en agua? si 2 no 1
c[3] = se desenvuelve en superficie terrestre? si 2 no 1
c[4] = Distribuicion?  equipo 2 indiviual 1
c[5] = Requiere de un objetos para lograr puntaje? si 2 no 1
c[6] = Es de contacto fisico? si 2 no 1
c[7] = Se necesita de preparacion fisica? si 2 no 1
c[8] = Deporte de impacto? si 2 no 1
c[9] = Puede deporte mixto? si 2 no 1
c[10] = Tiempo definido? si 2 no 1
c[11] = Estatico? si 2 no 1
c[12] = Monotono? si 2 no 1

Football soccer

c1 = [2,2,1,2,2,2,1,2,1,1,2,1,1]

Tiro con arco
c2 = [2,2,1,2,1,2,1,2,1,1,1,2,2]

Golf

c3 = [1,2,1,2,1,2,1,2,1,1,1,1,2]

Animacion (Porristas)

c4 = [2,2,1,2,2,1,2,2,2,2,2,1,1]

Triathlon

c5 = [1,1,2,2,1,2,1,2,1,1,1,1,1]

Ajedrez

c6 = [2,2,1,2,1,1,1,1,1,2,2,2,1]

Natacion

c7 = [1,2,2,1,1,1,1,2,1,1,1,1,2]

Tae Kwon DO

c8 = [2,2,1,2,1,2,2,2,2,1,2,1,1]

Water Polo

c9 = [2,2,2,1,2,2,1,2,1,1,2,1,1]

Medida de similitud
En la medida de similitud optamos por elegir el de la Similitud o distancia euclidiana ya que es la que por lo general se utiliza para este tipo de algoritmo.

Algoritmo k-means

         

Cálculo de centroides

Cálculo de distancias

Nuevo centroide
Realizamos el cálculo de un nuevo centroide en base a los promedios de puntos, de tal manera que el centroide se aproxime a mediación de cada cluster.

 Actualizar centroide

Realizamos primero el cálculo de uno nuevo y al mismo tiempo comprobamos si la diferencia entre centroides cae dentro el umbral o no.

Algoritmo principal
Aquí es donde hacemos uso de todas las funciones en conjunto y utilizamos la instrucción "asignación_centroide"

Después de la asignación realizamos una "Actualización de ellos" y continuará el ciclo mientras la salida no sea igual a "1", lo cual solo ocurre cuando cae dentro del umbral.

 

 Parámetros

 Recibe como los vectores de características como puntos, el numero de centroides y el umbral:

numero de centroides = 3

umbral = 0.01

Se realizarán 10 corridas de nuestro algoritmo

El criterio de terminación para cada una es que esté dentro del umbral 0.01

 Resultados:

 Al realizar una corrida sin respetar el umbral corría al infinito y realizaba cálculos como acontinuación:







 Después nos encargamos de ajustar el parámetro y podemos apreciar un mejor resultado:





Fué algo difícil para nosotros representar el agrupamiento, pero decidimos ponerlo en listas con índices:











En el ejemplo anterior, nos dice primero el # de cluster y el vector correspondiente entre corchetes para poder identificar los clusters.





Los resultados no son del todo claro, ya que es la primera vez que realizamos algo así y no lo visualizamos instantaneamente.





Definitivamente hay cosas inesperadas pero suceden debido a la ambigüedad con la que hemos manejado el algoritmo, y bugs no detectados aún.

♦Conclusiones
 

Nuestro aprendizaje con K-means fué muy bueno y nos mostró una manera distinta de analizar datos, definitivamente fué una muy buena práctica de programación.

Las experiencias buenas que nos llevamos es el análisis múltiple y el ver la complejidad con la que se torna la situación al hacerlas interactuar.

Sin embargo nuestros habilidades necesitan incrementarse para poder aplicar en forma y propiamente a un contexto profesional.

Las mejoras futuras que realizaremos será la reducción de dimensionalidad y gráficadores para poder visualizar en tiempo y forma que es lo que esta ocurriendo, en lugar de interpretar listas y cadenas de texto llano.

 

♦Referencias

Salvat enciclopedia volumen 1 A-ARRE

http://www.cs.uvm.edu/~xwu/kdd/Slides/Kmeans-ICDM06.pdf

Reporte Práctica 1 - ACO (Optimización por Colonia de Hormigas).

Introducción.

El Problema del Agente Viajero o TSP (del inglés Travelling Salesman Problem) básicamente es un problema de Optimización que busca la minimización. Surge con la  necesidad de buscar la ruta más corta o de menor costo en un conjunto de ciudades o puntos, esto sin depender del orden a seguir en el viaje siempre y cuando el recorrido sea cerrado.

El TSP es muy importante ya que se aplicar en la vida diaria cuando simplemente estamos de viaje y queremos dar el tour más corto en los lugares turísticos, o hasta en la industria por ejemplo cuando se busca hacer taladrado en piezas de metal tomando el menor tiempo, otras situaciones que pueden aplicar son en el autobús escolar, el repartidor de comida y  el diseño de tarjetas electrónicas.

La dificultad de este problema crece a medida de que aumentas las ciudades ya que se generan cada vez más combinaciones que por fuerza bruta; lo cual sería muy tedioso y cansado para resolver.

La Optimización por Colonia de Hormigas o ACO (del inglés Ant Colony Optimization) es una metaheurística para la resolución de problemas como la ruta más corta, la cual se inspira en las colonias de hormigas reales ya que por naturaleza se organizan para ir por la comida cada vez por una mejor ruta.

El ACO  es justamente lo que el TSP necesita porque es un Algoritmo que nos ayudará a encontrar la ruta con menor costo.

En esta entrada implementaremos el ACO para la resolución de instancias TSP, primero dando un enfoque teórico para conocer y entender cómo se soluciona este problema, y después la implementación con un programa de la solución de una instancia donde se mostraran los parámetros utilizados y finalmente la verificación de resultados.

Práctica 1 | Parte 1

En esta tarea nuestros puntos a realizar son:

* Generar instancias del problema del viajero
* Resolver una instancia por fuerza bruta
* Generar pseudocódigo o diagrama de flujo para ACO (elegimos el diagrama)