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)

Tarea #2 Divide y vencerás

Divide y vencerás

La técnica consiste en dividir un problema en almenos 2 partes (instancias) del problema, resolver (vencer) estas instancias y obtener una solución general del problema, combinando las soluciones de los sub problemas.

Pseudocódigo:

funcion divide&venceras(problema)

{

Si problema es suficientemente pequeño o sencillo:

return (solucion tradicional del problema)

descomponer el problema en n subproblemas más pequeños;

para i=1 hasta n hacer

resolver el subproblema k

combinar las n soluciones

}

Tarea #1 Array & String

Array en Java

Un Array es un medio para guardar un conjunto de objetos de la misma clase. Se accede a cada elemento individual del Array mediante un número entero denominado índice. 0 es el índice del primer elemento y n-1 del último, siendo n el tamaño del Array.

Declaración de un Array
tipo_de_dato [tamaño del Array] nombre_del_Array;

Int [ ] arregloNumeros; (Array de números tipo entero)

arregloNumeros = new int [ 10 ]; (Array de tamaño 10 de números tipo entero)

arregloNumeros = 0; (Inicializamos el arrglo en 0)

Llenado de arreglo

for(int i=0; i<cuadrado.length; i++){

        System.out.println(cuadrado[i].calcularArea());

    }

Tarea #1 Arboles y Hash Table

Árbol
El arbol como estructura de datos es una de las las estructuras de datos más avanzadas, consiste en nodos organizados de manera jerárquica.

Cuando uno usa una base de datos hay un 99 % de probabilidad que un index esté involucrado. El simple tipo de index es una lista ordenada de un campo de llave. Esto provee una búsqueda rápida porque uno puede usar una búsqueda binaria para localizar cualquier artículo sin tener que que ver a cada uno.

Ejemplo de un árbol binario completo:


El problema viene cuando uno quiere añadir uno nuevo elemento y mantener la lista ordenada.

Tarea #1 MapReduce

MapReduce

Es el paradigma de programación que permite  una escalabilidad masiva a traves de  cientos y miles de servidores a traves de un clúster de un software que te permite procesar grandes cantidades de datos a traves de los clústers de servidores de comodidad, los cuales pueden escalar desde un simple servidor hasta miles de máquinas, con un alto grado de tolerancia a errores. En lugar de depender en hardware, la fortaleza de estos clúster viene de la habilidad del software para detectar y encargase de errores en la capa de aplicación.

Tarea #1 Big Data

Big data es una vasta cantidad de datos sin estructura, los cuales ahora sabemos que tenemos la habilidad de procesar en tiempo real.

• ·         Está adquiriendo importancia por el aumento de los teléfonos inteligentes con GPS y conectividad a internet

Hay 4.6 billones de subscriptores de teléfonos celulares alrededor del mundo y entre uno y dos billones de personas con acceso actual a internet.

• ·         Los sensores aéreos y las redes  sensoriales

El centro de la NASA para simulación del clima que almacena 32 petabytes acerca de las observaciones del clima y simulaciones en el clúster de descubrimientos de la supercomputadora.

Tarea#1 - Filas y Pilas

Filas (Queue) y Colas(Stacks)

En esta ocasión, nos toco hablar acerca de algunas estructuras de datos, en este caso particularmente de las estructuras de datos lineales, que son las Filas que también son conocidas como Colas y las Pilas, particularmente estas dos estructuras se comportan como una Lista que también es una estructura de datos lineal pero con característica especial cada una.
Estas tres estructuras son dinámicas, aunque, dependiendo del lenguaje en el que se este implementanto se puede implementar usando un array con longitud fija pero resulta ser ineficiente tanto en memoria como en forma de implementación.

Otra cuestión acerca de la implementación es la gran ayuda en lenguajes de muy alto nivel como lo que es Python ya que por defecto contiene una estructura de datos que son las listas. Esta estructura de datos, que también es un objeto, contiene una serie de métodos que además lo vuelven dinámico que ya nos sirven para agregar elementos y eliminar elementos en cualquier posición, entre otros. Las listas en Python se puede acceder a cualquier elemento de ella por medio de indices como en los Arrays, de echo, en este lenguaje no existen los arrays sino que de forma generica se utilizan las listas como arrays gracias a su gran potencial.

Introducción al Blog y Tarea #1

Bienvenidos.

Este es el Blog del Laboratorio de Sistemas Adaptativos del Semestre Agosto-Diciembre del 2013. Nuestro equipo se encuentra formado por:

1. Constantino Mora
2. Marco Urrea
3. Marin Salinas

Se espera que con este blog del laboratorio, reforzar lo aprendido en clase, así como también aportar sobre los conocimiento que hasta ahora como estudiantes hemos logrado obtener, para que de esta manera nos resulte más sencillo exponer las diferentes tareas y actividades.