Los diferentes tipos de Clusterización atienden a necesidades específicas de análisis de datos. Puede resultarnos un proceso natural agrupar datos en comunidades por similaridad. De hecho podemos calcular la similitud existente entre diferentes pares de vértices dentro de un grafo, tomando como referencia alguna de sus propiedades, sin importar si están conectados de forma directa o no.

Estas medidas se corresponden con lo que los expertos del análisis de datos y detección de comunidades conocen como métodos tradicionales de agrupamiento o clusterización. A continuación realizaremos un breve recorrido por los principales métodos tradicionales para entender sus ventajas, desventajas y algunas de sus aplicaciones.

Principales tipos de Clusterización tradicional

Partición de grafos

La partición de grafos es uno de los tipos de clusterización tradicional más utilizados por los analistas de datos. Este método consiste en dividir los vértices en grupos determinados de un tamaño predefinido, de forma que el número de bordes que se encuentran entre los grupos de creados, sea mínimo. El número de bordes que se ejecutan entre los grupos generados recibe el nombre de «tamaño de corte». Este número es el que determina o especifica el número de clústeres generados a raíz de la partición.

Para que este método sea eficiente debemos establecer este tamaño de corte, ya que de lo contrario la solución que obtendríamos no sería representativa, y la resolución más probable que nos indique el grafo sería separar el vértice de menor grado de todo el grafo, sin brindarnos más información útil.

Agrupación jerárquica

Los grafos poseen una estructura. Aunque en ocasiones suelen ser estructuras con un nivel de complejidad alto, que dificulta determinar a simple vista el número de conglomeraciones de datos que lo integra. En tales casos los métodos tradicionales de clusterización no son eficientes y se encuentran con barreras muy complejas para otorgarnos información de calidad. Es por esto que los procesos de agrupación jerárquica toman una gran relevancia.

Estos modelos de detección de comunidades de datos nos puede ayudar a mostrar varios niveles de agrupación de los vértices dentro de un grafo. Podemos tomar en cuenta grupos pequeños de datos que se encuentran solapados por otros y mezclar nuestra selección con otros grupos más grandes para así enriquecer el producto del análisis.

Este tipo de métodos suele ser de especial utilidad en análisis de datos orientados a negocios. Por ejemplo, las redes sociales poseen una estructura jerárquica que viene determinada por el orígen de la relación entre los usuarios. Utilizando algoritmos podemos diseñar estructuras multinivel de agrupación dentro de un grafo y así entender el nivel de relación, las interacciones que pueden existir y diseñar experiencias personalizadas que saquen provecho de esta relación.

La agrupación jerárquica es un método que también es utilizado en el marketing digital, la ingeniería y la biología. El punto de partida inicial de cualquier método de este tipo es la definición de una medida de similitud entre vértices. Posteriormente se debe realizar un calculo de similitud entre cada par de vértices sin importar si están conectados o no, para posteriormente generar matrices donde podamos enumerar las posibles definiciones de similitud.

Para realizar este tipo de agrupación o detección de comunidades contamos con dos tipos de algoritmos. Los algoritmos aglomerativos, en los que los clústeres de datos se fusionan de forma iterativa en el caso de que la similitud de los vértices sea alta y los algoritmos divisivos en los que los grupos se dividen iterativamente eliminando los bordes que conectan los vértices con poca similitud.

Como podemos ver estos procesos son totalmente opuestos. Los algoritmos de tipo aglomerativo comienzan la construcción de los grupos separados hasta formar un grupo único, mientras que el de tipo divisivo realiza la acción contraria mientras se traslada por el grafo.

Agrupación particional

El método de agrupación particional es otro de los tipos de clusterización que podemos utilizar para agrupar conjuntos de datos. En este método el número de clúster se encuentra predefinido. Los vértices se plasman dentro de un espacio métrico de forma tal de que cada vértice sea un punto y así poder determinar la distancia entre pares de puntos en un espacio. La distancia es una medida de disimilitud entre los vértices.

El objetivo de este método es separar los puntos en grupos de manera que se maximice / minimice una función de costo determinada en función de las distancias entre puntos  de los puntos a los centroides que conforman el plano determinado.

Agrupación espectral

La agrupación espectral se trata de crear clústeres de datos mediante una función de similitud por pares de forma simetríca y no negativa. La agrupación espectral incluye todos los métodos y técnicas que dividen el conjunto en agrupaciones mediante el uso de vectores propios de matrices y sus derivaciones. En este caso en particular los objetos a estudiar podrían ser puntos en algún espacio métrico o en los vértices de un grafo.

Esperamos que esta información sea de utilidad para entender los diferentes tipos de clusterización  que podemos aprovechar para analizar nuestros datos.

Visita más de Grapheverywhere y descubre todo lo que necesitas saber sobre la detección de comunidades.