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.
