K-means

Hace tiempo hice una tarea en un antiguo blog que tengo en el que hablaba de k-means, asi que decidi rescatarla solo para recordar algo de algoritmos que e ido dejando de lado por el momento.

Introducción

K-means esta desarrollado por el principio de agrupamiento, el cual tiene principios básicos de características nítidas o difusas, ya que en base a un grupo de características K-means determina los grados de pertenencias de dichas características y los va separando por grupos similares.

Se pretende realizar un algoritmo el cual ordenar un array de vector con el principio de K-Means:

Se desarrollara en la entrada:

  • Introducción
  • Marco Teórico
  • Desarrollo
  • Resultados
  • Conclusiones

Marco Teórico:

Los argumentos son grupos de elementos, en los cuales cada grupo de elemento esa agrupado con características similares o especificas. No pueden aver agrupamientos con características diferentes.

Se pueden encontrar varios tipos de argumentos:

Jerárquico: De los grupos formados se crean grupos nuevos, así podrá obtener nuevos elementos de otros grupos.

Partición: Se miden los grados de pertenencias para ordenar en grupos los cuales llamaremos (centroides)

Difuso: Estas características tienen un grado de pertenencia numérico, y respecto este numero se podra ordenar en varios grupos que contengan ese grado de pertenencia similar.

Traslape : Se actualizan los datos ingresados del algoritmo.

Desarrollo

Se han utilizados las siguientes tecnologías al ser de fácil uso y por que me gustan los lenguajes script, en especial javascript

  • HTML
  • CSS
  • Javascript

Creamos una librería llamada KMeans la cual contiene las siguientes funciones:

recorrerPuntos: Nos sirve para saber que valores tienen los puntos dados solo para cuestiones de debug


calcularDist : Hace las operaciones correspondientes para calcular la distancia euclidiana


obtenerDist: obtiene la distancia euclidiana de una serie de puntos dados implementando la función calcularDist.


agrupamiento: Agrupa los puntos a cierto grupo dependiendo de su distancia euclidiana con los centroides


recalcularCent: Hace las operaciones correspondientes para obtener un nuevo valor para cada par de centroides.

Resultados

Los resultados los mostramos en una serie de tablas en las que se observa cada uno de los elementos y datos que el algoritmo necesita como son las coordenadas en "x" y en "y" de los puntos y de los centroides, las distancias euclidianas calculadas,los grupos que se formaron y los centroides re-calculados, desafortunadamente aun no encuentro alguna herramienta que permita graficar fácilmente, por lo que es una cuestión pendiente.

1

2

Conclusión

K-means sirve para agrupar arrays, tiene de cierta manera similitud con el método Burbuja y Quicksort, mas aun asi K-means también es una opción muy valida para el ordenamiento de vectores.

Descargar codigo

Jesús Perales

Read more posts by this author.

Subscribe to Jesús Perales

Get the latest posts delivered right to your inbox.

or subscribe via RSS with Feedly!