Clustering, algoritmo K-means

Bueno en esta entrega brindaré un poco de teoria acerca del clustering y mostraré el algoritmo K-means, ya en otras entregas manejarè un algoritmo por cada tipo de clustering.

Bien primero ¿Qué es el clustering?,pues bien, este es un análisis que se realiza sobre los datos con el objetivo de obtener agrupaciones que nos puedan brindar información acerca de los mismos.

El objetivo principal es poder determinar la similitud o diferencia de los elementos que conforman nuestra información y en base a esto podemos tomar decisiones.

En muchas ocasiones la noción de los cluster en nuestra información no está bien definida, veamos un ejemplo, tomando en cuenta la siguiente imagen:

Si quisieramos agrupar los circulos en la misma podriamos tener los siguientes resultados (entre muchos otros):

o bien

uno mas


 

Como podemos apreciar, depende mucho de la interpretación que deseemos darle a nuestra información. Usualmente una buena idea es conocer los datos antes siquiera de intentar agruparlos, posterior a ello se deben de probar diversos algoritmos de agrupamiento para asi poder determinar cual es el mas indicado.

Otra peculiaridad es como queremos que se formen los grupos, usualmente existen 3 formas:

Particionales: Los grupos se definen perfectamente, de tal manera que un elemento solo puede pertenecer a un grupo (Las imágenes de arriba detallan este ejemplo)

Jerarquico: Los elementos estan agrupados en jerarquias, de tal manera que un elemento pertenece a un grupo, pero puede al mismo tiempo pertenecer a un subgrupo. La imagen siguiente muestra un ejemplo de este caso:

Este tipo de clustering son de los mas utilizados debido a que suelen ser muy representativos y nos dan usualmente un buen punto de partida para entender nuestra información, veamos la siguiente imagen de un cluster jerarquico real:

Difusos: Estos definen que un elemento puede tener cierto grado de pertenecia aun grupo u otro, por ejemplo, digamos que tenemos dos grupos, uno donde se definen a los delgados y otro que define a los obesos, supongamos que nos llega una persona que tiene 3 kilos de sobrepeso, podriamos ponerla con un 40% de pertenecia al grupo de delgados y un 60% al grupo de obesos.

Pues bien, una vez que hayamos definido el tipo de cluster que deseamos utilizar, nos queda por elegir la metodología con la cual crearemos los grupos, a continuación muestro diversas formas (abordaré un algoritmo por tema en futuras entregas):

Grupos bien separados ó definidos: No existe mucho que decir aquí, en estos casos los grupos estan como su nombre lo dice bien definidos , usualmente con determinadas características que los hacen particulares y dificiles de confundir, por ejemplo, podemos tener dos grupos uno para aves y otro para reptiles.

Basados en prototipos: En estos algoritmos se suele determinar la pertenencia a un grupo en base a alguna medida de distancia. Como punto de partida es comun usar algun dato muy representativo de cada grupo o alguna medida estadística como la media o la mediana.(cabe mencionar que este tipo de metodologías es necesario le proporcionemos cuantos grupos queremos crear).

Basados en conexiones: Aqui los elementos estan conectados de alguna manera con su grupo particular y desconectados de los otros grupos. Estos algoritmos son utiles para encontrar grupos con formas no comunes. La imagen siguiente muestra un ejemplo de estas agrupaciones:

Basados en densidad: Estos grupos se forman organizando los elementos en base a regiones pobladas, usualmente aquellos elementos que se encuentran fuera de estas regiones son ignorados o se consideran que no forman parte del grupo:

Basados en forma: En este tipo de clusters se conocen bien los datos y usualmente se definen fórmulas que representan a los grupos. La siguiente imagen muestra a dos grupos definidos, uno por tener una forma triangular y otro una rectangular:

Bien ahora que ya tenemos la teoria, veamos el algortimo K-means, este es un cluster basado en prototipos, veamos su algoritmo:

• Paso 1 : Establece un grupo K como centroides en el espacio representado
• Paso 2 : Calcula la distancia de cada objeto con cada uno de los centroides de K y asígnalo al centroide del cual su distancia sea menor.
• Paso 3: Cuando todos los objetos sean asignados, entonces recalcula la posición de los centroides.
• Paso 4: Repite los pasos 2 y 3 hasta que los centroides no se muevan mas.

Para el paso 1 usualmente se suele tomar alguna medida estadística como la media o la mediana, algun dato que represente perfectamente a cada grupo o bien se utilizan datos aleatorios. Dependiendo del número de grupos que demos serán los cluster que obtendremos.

Para el paso 2 se puede utilizar cualquier fórmula de distancia. Cada objeto será comparado con todos los centroides y se asignará al centroide que haya tenido una distancia menor.

Para el paso 3, usualmente se utiliza alguna heurístca personalizada para determinar como modificar los centroides, aunque en la práctica se suele calcular la media o mediana de sus objetos y movilizar los centroides a esa posición

Para el paso 4, de la misma manera se suele utilizar una heurística que nos permita determinar alguna condición de paro, estas van desde correr el proceso un número determinado de ocasiones, sumar las distancias mas cortas del paso 2 y si se obtiene una suma inferior continuar con el proceso (siendo esta la mas usada y en algunos casos considerada obligatoria) o bien determinar un mecanismo personalizado para el problema en cuestión.

Como vemos es en realidad un algoritmo sencillo de implementar “” , las siguientes imagenes muestran un ejemplo del algoritmo K-means con la base de datos de iris. Para poder representarla en 2D simplemente utilice el algoritmo PCA (Lo explicaré en otra entrada) para obtener 2 dimensiones.

Veamos como evoluciona el algoritmo Kmeans cuando movemos los centroides hacia su media(como punto de partida inicial se tomo un objeto aleatorio dentro del grupo):

La condición de paro se tomó cuando su medición no pudiese descender, en este caso el algoritmo convergió en su cuarta corrida, ya que de hecho su medición fue mayor, tomando a la imagen 3 como el mejor cluster que logró clasificar

Veamos ahora el mismo algoritmo pero esta vez moviendo a los centroides con la mediana:

Como vemos funcionó mejor la mediana ya que su medición menor se encuentra en 77 mientras que para la media fue de 79, claro que necesitó de mas pasos para converger.