in

Los 5 algoritmos de agrupación en clústeres que los científicos de datos deben conocer

1oNt9G9UpVhtyFLDBwEMf8Q

Los 5 algoritmos de agrupación en clústeres que los científicos de datos deben conocer

George Seif

5 de febrero de 2018·11 min de lectura

Escribo un boletín para estudiantes llamado Mighty Knowledge. Cada nuevo número contiene enlaces y lecciones clave del mejor contenido, incluidas citas, libros, artículos, podcasts y videos. Todos y cada uno son seleccionados específicamente para aprender a vivir una vida más sabia, feliz y plena. Registrate aquí.

La agrupación en clústeres es una técnica de aprendizaje automático que implica la agrupación de puntos de datos. Dado un conjunto de puntos de datos, podemos usar un algoritmo de agrupamiento para clasificar cada punto de datos en un grupo específico. En teoría, los puntos de datos que están en el mismo grupo deberían tener propiedades y / o características similares, mientras que los puntos de datos en diferentes grupos deberían tener propiedades y / o características muy diferentes. La agrupación en clústeres es un método de aprendizaje no supervisado y es una técnica común para el análisis de datos estadísticos que se utiliza en muchos campos.

En ciencia de datos, wPodemos usar el análisis de agrupamiento para obtener información valiosa de nuestros datos al ver en qué grupos se ubican los puntos de datos cuando aplicamos un algoritmo de agrupamiento. Hoy, veremos 5 algoritmos de agrupación en clústeres populares que los científicos de datos deben conocer y sus pros y contras.

K-Means es probablemente el algoritmo de agrupación en clústeres más conocido. Se enseña en muchas clases de introducción a la ciencia de datos y al aprendizaje automático. ¡Es fácil de entender e implementar en código! Consulte el gráfico a continuación para ver una ilustración.

Agrupación de K-medias
  1. Para comenzar, primero seleccionamos una cantidad de clases / grupos para usar e inicializamos aleatoriamente sus respectivos puntos centrales. Para calcular la cantidad de clases que se deben usar, es bueno echar un vistazo rápido a los datos e intentar identificar las agrupaciones distintas. Los puntos centrales son vectores de la misma longitud que cada vector de punto de datos y son las «X» en el gráfico de arriba.
  2. Cada punto de datos se clasifica calculando la distancia entre ese punto y el centro de cada grupo, y luego clasificando el punto para que esté en el grupo cuyo centro está más cerca de él.
  3. Con base en estos puntos clasificados, recalculamos el centro del grupo tomando la media de todos los vectores del grupo.
  4. Repita estos pasos para un número determinado de iteraciones o hasta que los centros de grupo no cambien mucho entre iteraciones. También puede optar por inicializar aleatoriamente los centros de grupo varias veces y luego seleccionar la ejecución que parezca que proporcionó los mejores resultados.

K-Means tiene la ventaja de que es bastante rápido, ya que todo lo que realmente estamos haciendo es calcular las distancias entre los puntos y los centros de los grupos; muy pocos cálculos! Por tanto, tiene una complejidad lineal O(norte).

Por otro lado, K-Means tiene un par de desventajas. En primer lugar, debes seleccionar cuántos grupos / clases hay. Esto no siempre es trivial e, idealmente, con un algoritmo de agrupación en clústeres, querríamos que nos los resolviera porque el objetivo es obtener algo de información a partir de los datos. K-means también comienza con una elección aleatoria de centros de conglomerados y, por lo tanto, puede producir diferentes resultados de conglomerados en diferentes ejecuciones del algoritmo. Por lo tanto, es posible que los resultados no sean repetibles y carezcan de consistencia. Otros métodos de agrupación son más consistentes.

K-Medianas es otro algoritmo de agrupamiento relacionado con K-Medias, excepto que en lugar de volver a calcular los puntos centrales del grupo usando la media, usamos el vector mediano del grupo. Este método es menos sensible a los valores atípicos (debido al uso de la mediana), pero es mucho más lento para conjuntos de datos más grandes, ya que se requiere ordenar en cada iteración al calcular el vector de la mediana.

La agrupación en clústeres de cambio medio es un algoritmo basado en ventanas deslizantes que intenta encontrar áreas densas de puntos de datos. Es un algoritmo basado en centroide, lo que significa que el objetivo es ubicar los puntos centrales de cada grupo / clase, que funciona actualizando candidatos para puntos centrales para que sean la media de los puntos dentro de la ventana deslizante. Luego, estas ventanas candidatas se filtran en una etapa de posprocesamiento para eliminar casi duplicados, formando el conjunto final de puntos centrales y sus grupos correspondientes. Consulte el gráfico a continuación para ver una ilustración.

1*bkFlVrrm4HACGfUzeBnErw

Agrupación de cambios medios para una sola ventana deslizante
  1. Para explicar el desplazamiento medio, consideraremos un conjunto de puntos en un espacio bidimensional como la ilustración anterior. Comenzamos con una ventana deslizante circular centrada en un punto C (seleccionado al azar) y que tiene un radio r como núcleo. El cambio medio es un algoritmo de escalada que implica cambiar este núcleo de forma iterativa a una región de mayor densidad en cada paso hasta la convergencia.
  2. En cada iteración, la ventana deslizante se desplaza hacia regiones de mayor densidad cambiando el punto central a la media de los puntos dentro de la ventana (de ahí el nombre). La densidad dentro de la ventana deslizante es proporcional al número de puntos dentro de ella. Naturalmente, al cambiar a la media de los puntos en la ventana, se moverá gradualmente hacia áreas de mayor densidad de puntos.
  3. Continuamos desplazando la ventana deslizante de acuerdo con la media hasta que no haya una dirección en la que un desplazamiento pueda acomodar más puntos dentro del kernel. Mira el gráfico de arriba; seguimos moviendo el círculo hasta que ya no aumentamos la densidad (es decir, el número de puntos en la ventana).
  4. Este proceso de los pasos 1 a 3 se realiza con muchas ventanas deslizantes hasta que todos los puntos se encuentran dentro de una ventana. Cuando varias ventanas deslizantes se superponen, se conserva la ventana que contiene la mayoría de los puntos. Luego, los puntos de datos se agrupan de acuerdo con la ventana deslizante en la que residen.

A continuación se muestra una ilustración de todo el proceso de un extremo a otro con todas las ventanas deslizantes. Cada punto negro representa el centroide de una ventana deslizante y cada punto gris es un punto de datos.

1*vyz94J 76dsVToaa4VG1Zg

Todo el proceso de agrupación de cambios medios

A diferencia de la agrupación en clústeres de K-medias, no es necesario seleccionar el número de clústeres, ya que el desplazamiento medio lo descubre automáticamente. Esa es una gran ventaja. El hecho de que los centros de los conglomerados converjan hacia los puntos de máxima densidad también es bastante deseable, ya que es bastante intuitivo de entender y encaja bien en un sentido natural impulsado por los datos. El inconveniente es que la selección del tamaño / radio de la ventana “r” puede no ser trivial.

DBSCAN es un algoritmo agrupado basado en densidad similar al desplazamiento medio, pero con un par de ventajas notables. ¡Mira otro gráfico elegante a continuación y comencemos!

1*tc8UF h0nQqUfLC8 0uInQ

Agrupación de caras sonrientes DBSCAN
  1. DBSCAN comienza con un punto de datos inicial arbitrario que no se ha visitado. La vecindad de este punto se extrae usando una distancia épsilon ε (Todos los puntos que están dentro de la distancia ε son puntos de vecindad).
  2. Si hay una cantidad suficiente de puntos (según minPoints) dentro de esta vecindad, entonces comienza el proceso de agrupamiento y el punto de datos actual se convierte en el primer punto en el nuevo grupo. De lo contrario, el punto se etiquetará como ruido (más tarde, este punto ruidoso podría convertirse en parte del clúster). En ambos casos, ese punto se marca como «visitado».
  3. Para este primer punto en el nuevo grupo, los puntos dentro de su vecindad de distancia ε también pasan a formar parte del mismo grupo. Este procedimiento de hacer que todos los puntos en la vecindad ε pertenezcan al mismo grupo se repite luego para todos los puntos nuevos que se acaban de agregar al grupo de grupos.
  4. Este proceso de los pasos 2 y 3 se repite hasta que se determinan todos los puntos del conglomerado, es decir, se han visitado y etiquetado todos los puntos dentro de la vecindad ε del conglomerado.
  5. Una vez que terminamos con el clúster actual, se recupera y procesa un nuevo punto no visitado, lo que lleva al descubrimiento de un nuevo clúster o ruido. Este proceso se repite hasta que todos los puntos se marcan como visitados. Dado que al final de esto se han visitado todos los puntos, cada punto se habrá marcado como perteneciente a un grupo o como ruido.

DBSCAN presenta grandes ventajas sobre otros algoritmos de agrupamiento. En primer lugar, no requiere un número pe-set de clusters en absoluto. También identifica los valores atípicos como ruidos, a diferencia del desplazamiento medio, que simplemente los arroja a un grupo, incluso si el punto de datos es muy diferente. Además, puede encontrar grupos de tamaño y forma arbitrarios bastante bien.

El principal inconveniente de DBSCAN es que no funciona tan bien como otros cuando los clústeres son de densidad variable. Esto se debe a que la configuración del umbral de distancia ε y minPoints para identificar los puntos vecinos variará de un grupo a otro cuando la densidad varíe. Este inconveniente también ocurre con datos de muy alta dimensión, ya que nuevamente el umbral de distancia ε se vuelve difícil de estimar.

Uno de los principales inconvenientes de K-Means es su uso ingenuo del valor medio para el centro del grupo. Podemos ver por qué esta no es la mejor manera de hacer las cosas mirando la imagen a continuación. En el lado izquierdo, parece bastante obvio para el ojo humano que hay dos grupos circulares con diferentes radios centrados en la misma media. K-Means no puede manejar esto porque los valores medios de los grupos están muy juntos. K-Means también falla en los casos en que los grupos no son circulares, nuevamente como resultado de usar la media como centro del grupo.

1*Xvl

Dos casos de falla para K-Means

Los modelos de mezcla gaussiana (GMM) nos brindan más flexibilidad que K-Means. Con los GMM asumimos que los puntos de datos tienen una distribución gaussiana; esta es una suposición menos restrictiva que decir que son circulares usando la media. De esa manera, tenemos dos parámetros para describir la forma de los conglomerados: ¡la media y la desviación estándar! Tomando un ejemplo en dos dimensiones, esto significa que los grupos pueden tomar cualquier tipo de forma elíptica (ya que tenemos una desviación estándar en las direcciones x e y). Por lo tanto, cada distribución gaussiana se asigna a un solo grupo.

Para encontrar los parámetros de Gauss para cada grupo (por ejemplo, la media y la desviación estándar), usaremos un algoritmo de optimización llamado Expectativa-Maximización (EM). Eche un vistazo al gráfico a continuación como una ilustración de los gaussianos que se ajustan a los grupos. Luego, podemos continuar con el proceso de agrupación en clústeres de expectativa-maximización utilizando GMM.

1*OyXgise21a23D5JCss8Tlg

Agrupación EM con GMM
  1. Comenzamos seleccionando el número de conglomerados (como hace K-Means) e inicializando aleatoriamente los parámetros de distribución gaussiana para cada conglomerado. También se puede intentar proporcionar una estimación aproximada de los parámetros iniciales echando un vistazo rápido a los datos. Aunque tenga en cuenta, como se puede ver en el gráfico anterior, esto no es 100% necesario ya que los gaussianos comienzan como muy pobres pero se optimizan rápidamente.
  2. Dadas estas distribuciones gaussianas para cada grupo, calcule la probabilidad de que cada punto de datos pertenezca a un grupo en particular. Cuanto más cerca esté un punto del centro de Gauss, es más probable que pertenezca a ese grupo. Esto debería tener un sentido intuitivo, ya que con una distribución gaussiana asumimos que la mayoría de los datos se encuentran más cerca del centro del grupo.
  3. Basándonos en estas probabilidades, calculamos un nuevo conjunto de parámetros para las distribuciones gaussianas de manera que maximizamos las probabilidades de los puntos de datos dentro de los grupos. Calculamos estos nuevos parámetros usando una suma ponderada de las posiciones de los puntos de datos, donde los pesos son las probabilidades del punto de datos que pertenece a ese grupo en particular. Para explicar esto visualmente podemos echar un vistazo al gráfico de arriba, en particular el grupo amarillo como ejemplo. La distribución comienza aleatoriamente el primero …

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

034WtrBubZScJ0BxO0Pm5Kk 1.1632163570.fit lim.size 1200x630

La industria de chips puede experimentar un exceso de capacidad en 2023

social og oracle badge

¿Qué es Internet de las cosas (IoT)?