EM

Algoritmo Expectation-Maximization (EM) en Clustering

El algoritmo EM (Expectation-Maximization) es un método iterativo utilizado para encontrar los parámetros óptimos de modelos de probabilidad, como las distribuciones gaussianas, que representan mejor los datos en términos de agrupamiento o clasificación. En el contexto de clustering, se utiliza para estimar la estructura subyacente de los datos en términos de grupos o clústeres. A diferencia de K-Means, que asigna de manera rígida cada punto a un clúster, el algoritmo EM calcula la probabilidad de que cada punto pertenezca a un clúster, permitiendo una asignación más flexible.

¿Cómo Funciona EM?

El algoritmo EM funciona en dos fases iterativas:

1. Paso de Expectación (E-Step)

En este paso, el algoritmo estima la probabilidad de que cada punto de datos pertenezca a cada clúster, basándose en los parámetros actuales del modelo (como la media y la covarianza de cada clúster). El resultado de este paso es una matriz de probabilidades, donde cada celda indica la probabilidad de que un punto de datos pertenezca a un determinado clúster.

2. Paso de Maximización (M-Step)

En este paso, el algoritmo actualiza los parámetros del modelo (medias, varianzas y pesos de los clústeres) usando las probabilidades calculadas en el paso anterior. Este proceso maximiza la función de verosimilitud, buscando el mejor ajuste entre los datos y el modelo probabilístico.

Este ciclo de expectación y maximización continúa iterativamente hasta que los parámetros convergen, es decir, hasta que los cambios entre iteraciones son pequeños.

Características Principales del Algoritmo EM

• Modelo probabilístico: EM asume que los datos son generados por una mezcla de distribuciones probabilísticas (como gaussianas) y busca encontrar los parámetros de estas distribuciones.
• Asignación suave: A diferencia de K-Means, que asigna los puntos de datos a un único clúster, EM asigna una probabilidad a cada punto de pertenecer a un clúster.
• Número de clústeres: Puede determinar el número de clústeres automáticamente en algunos casos, aunque en la mayoría se debe especificar.

Casos de Uso del Algoritmo EM

EM es útil en escenarios donde los datos siguen una estructura probabilística subyacente. Algunos casos de uso incluyen:

• Agrupamiento de datos biológicos: Para clasificar especies o tipos celulares en función de sus características.
• Segmentación de mercado: Para encontrar subgrupos de clientes basados en su comportamiento de compra.
• Reconocimiento de patrones: Para detectar patrones o agrupamientos en datos con ruido.
• Análisis de mezclas gaussianas: Modelos donde se asume que los datos provienen de múltiples distribuciones gaussianas.

Ejemplo en Weka: Uso del Algoritmo EM en el Conjunto de Datos Iris

Weka ofrece el algoritmo EM como una opción para realizar agrupamiento. A continuación, te explico cómo usarlo en Weka con el conjunto de datos Iris:

Pasos para Ejecutar EM en Weka

1. Cargar el Dataset:
   • Abre Weka y selecciona el modo “Explorer”.
   • En la pestaña “Preprocess”, carga el dataset Iris que viene incorporado en Weka (iris.arff).
2. Seleccionar el Algoritmo EM:
   • Dirígete a la pestaña “Cluster”.
   • En el menú desplegable “Clusterer”, selecciona weka.clusterers.EM.
   • Puedes ajustar los parámetros si lo deseas, como el número de clústeres. Si dejas el parámetro Number of clusters en -1, Weka intentará determinar automáticamente el número óptimo de clústeres.
3. Ejecutar el Algoritmo:
   • Haz clic en el botón “Start” para ejecutar el algoritmo. Weka mostrará los resultados del clustering.

Ejemplo de Resultados de EM en Weka con el Dataset Iris

Supongamos que ejecutas el algoritmo EM con el conjunto de datos Iris y dejas que Weka determine automáticamente el número de clústeres. Los resultados pueden verse algo así:

=== Run information ===

Scheme:       weka.clusterers.EM -I 100 -N -1 -M 1.0E-6 -S 100
Relation:     iris
Instances:    150
Attributes:   5
              sepallength
              sepalwidth
              petallength
              petalwidth
Ignored:
              class

=== Clustering model (full training set) ===

EM
==

Number of clusters selected by cross validation: 3

Cluster 0: 
    P(Cluster 0) = 0.33
    sepallength mean: 5.006, std.dev: 0.3525
    sepalwidth mean: 3.418, std.dev: 0.381
    petallength mean: 1.464, std.dev: 0.1738
    petalwidth mean: 0.244, std.dev: 0.107

Cluster 1: 
    P(Cluster 1) = 0.34
    sepallength mean: 5.888, std.dev: 0.5171
    sepalwidth mean: 2.737, std.dev: 0.313
    petallength mean: 4.396, std.dev: 0.484
    petalwidth mean: 1.418, std.dev: 0.277

Cluster 2: 
    P(Cluster 2) = 0.33
    sepallength mean: 6.846, std.dev: 0.358
    sepalwidth mean: 3.082, std.dev: 0.214
    petallength mean: 5.702, std.dev: 0.458
    petalwidth mean: 2.079, std.dev: 0.288

=== Model and evaluation on training set ===

Clustered Instances

0      50 ( 33%)
1      51 ( 34%)
2      49 ( 33%)

Interpretación del Resultado

1. Número de Clústeres:
   • El algoritmo EM determinó que el número óptimo de clústeres es 3, que corresponde a las tres especies de flores en el conjunto de datos Iris: Iris-setosa, Iris-versicolor, y Iris-virginica.
2. Parámetros del Modelo:
   • Para cada clúster, el algoritmo estima los parámetros de las distribuciones gaussianas, como la media y la desviación estándar para cada atributo (sepallength, sepalwidth, etc.).
   • Por ejemplo, el Clúster 0 tiene una longitud de sépalo promedio de 5.006 con una desviación estándar de 0.3525.
3. Probabilidad de Pertenencia a un Clúster:
   • La probabilidad de pertenencia a un clúster indica qué porcentaje de las instancias pertenece a cada clúster. Aquí, aproximadamente un 33% de las instancias se agrupan en cada uno de los tres clústeres.
4. Instancias Agrupadas:
   • El número de instancias agrupadas en cada clúster está bastante equilibrado: 50, 51 y 49 instancias en los tres clústeres.

Comparación con K-Means

• EM asigna probabilidades de pertenencia, mientras que K-Means asigna una instancia a un único clúster.
• EM utiliza modelos probabilísticos y puede ajustar distribuciones gaussianas a los datos, mientras que K-Means utiliza distancias euclidianas simples para agrupar las instancias.
• EM es más flexible que K-Means, pero también puede ser más lento y complejo de ajustar en algunos casos.

Opciones relevantes del algoritmo EM en Weka:

1. -N
   • Descripción: Define el número de clusters que se espera encontrar. Si no se especifica, el algoritmo seleccionará el número óptimo de clusters automáticamente, basándose en el criterio de información (como el criterio de información bayesiana, BIC).
   • Ejemplo: -N 3 agrupa los datos en 3 clusters.
2. -I
   • Descripción: Especifica el número máximo de iteraciones que realizará el algoritmo. Si el algoritmo no converge antes de alcanzar este número, se detendrá. Un número mayor permite al algoritmo realizar más pasos para encontrar una mejor solución, pero incrementa el tiempo de procesamiento.
   • Ejemplo: -I 100 limita el número de iteraciones a 100.
3. -M
   • Descripción: Define la desviación estándar mínima para las variables que el algoritmo considerará al ajustar las distribuciones gaussianas. Esto evita problemas con variaciones extremadamente pequeñas que podrían generar errores numéricos o clusters extremadamente compactos.
   • Ejemplo: -M 1e-6 establece la desviación estándar mínima a 0.000001.
4. -V
   • Descripción: Habilita la visualización de la tabla de verosimilitud a lo largo de las iteraciones del algoritmo, permitiendo observar cómo cambia la verosimilitud con cada paso. Esta opción es útil para monitorear la convergencia del algoritmo.
   • Ejemplo: -V habilita la visualización de la verosimilitud.
5. -O
   • Descripción: Cuando se activa, esta opción habilita la clasificación por clases. Si el conjunto de datos incluye una clase definida, EM intentará predecir esta clase como parte del proceso de clustering. De lo contrario, el algoritmo trabajará sin usar clases etiquetadas.
   • Ejemplo: -O habilita la clasificación usando clases en el dataset.
6. -max-options
   • Descripción: Establece el número máximo de pasos de optimización durante la fase de maximización del algoritmo. Controla cuántas veces se optimizan los parámetros del modelo antes de detenerse. Es útil para afinar el rendimiento del algoritmo.
   • Ejemplo: -max-options 20 limita los pasos de optimización a 20.
7. -S
   • Descripción: Establece una semilla de aleatoriedad para la inicialización del algoritmo. Esto garantiza que el resultado sea reproducible cuando se ejecuta en diferentes ocasiones con la misma semilla.
   • Ejemplo: -S 42 establece la semilla de aleatoriedad en 42.
8. -K
   • Descripción: Si no se especifica el número de clusters, el algoritmo probará varios números de clusters diferentes y seleccionará el que minimice algún criterio de selección (como BIC). Esta opción permite especificar el número máximo de clusters que se intentarán.
   • Ejemplo: -K 10 probará hasta 10 clusters y seleccionará el número óptimo dentro de este límite.