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.
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).
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.
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.
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
