K-Means

Algoritmo K-Means: Explicación Detallada

K-Means es uno de los algoritmos de agrupamiento (clustering) más populares en aprendizaje no supervisado. Su objetivo es dividir un conjunto de datos en ( k ) clústeres, donde ( k ) es un número definido por el usuario. Cada instancia en los datos pertenece al clúster cuyo centroide (el promedio de los puntos dentro del clúster) está más cerca, según una métrica de distancia, generalmente la distancia euclidiana.

Funcionamiento del Algoritmo

1. Inicialización: Se seleccionan ( k ) puntos al azar como los centroides iniciales de los clústeres. Estos puntos representan el centro de cada clúster. También es posible elegir los puntos iniciales mediante métodos más sofisticados, como el algoritmo K-Means++.
2. Asignación de Puntos a Clústeres: Cada instancia en los datos es asignada al clúster cuyo centroide está más cerca. Esta asignación se realiza según la distancia euclidiana entre el punto y los centroides.
3. Recalcular Centroides: Una vez que todas las instancias han sido asignadas a un clúster, se recalcula el centroide de cada clúster. El nuevo centroide es el promedio de todos los puntos que pertenecen a ese clúster.
4. Iteración: Los pasos 2 y 3 se repiten hasta que los centroides no cambian significativamente o se alcanza un número máximo de iteraciones. En ese momento, el algoritmo se detiene y los puntos quedan asignados a sus clústeres finales.

Ventajas del Algoritmo K-Means

• Simplicidad y rapidez: K-Means es fácil de implementar y es computacionalmente eficiente para conjuntos de datos grandes.
• Flexibilidad: Se puede adaptar a diferentes tipos de datos, siempre que se defina una medida de distancia apropiada.

Desventajas del Algoritmo K-Means

• Necesidad de definir ( k ): El usuario debe predefinir el número de clústeres ( k ), lo cual puede ser un desafío si no se tiene una idea clara de la estructura de los datos.
• Sensibilidad a la inicialización: Diferentes inicializaciones pueden llevar a diferentes soluciones. Esto puede ser mitigado usando K-Means++.
• Sensibilidad a los valores atípicos: Los puntos alejados o ruidosos pueden influir en la posición de los centroides.

Casos de Uso

• Segmentación de clientes: Agrupar clientes según su comportamiento de compra para campañas de marketing dirigidas.
• Agrupamiento de imágenes: Agrupar imágenes basadas en similitud de píxeles para organizar álbumes o bases de datos visuales.
• Agrupación de documentos: Agrupar documentos según similitudes en contenido, útil en motores de búsqueda y clasificación de textos.

Ejemplo de K-Means en Weka

Vamos a utilizar el algoritmo K-Means en Weka con el famoso conjunto de datos Iris, que contiene datos sobre 150 plantas clasificadas en tres especies. Las características son las longitudes y anchos del sépalo y del pétalo.

Pasos para Usar K-Means en Weka:

1. Abrir Weka y cargar el dataset Iris:
   • Ir a la pestaña “Explorer”.
   • En “Preprocess”, cargar el dataset Iris (incluido en Weka).
   • El dataset tiene 150 instancias y 5 atributos: sepallength, sepalwidth, petallength, petalwidth, y class.
2. Eliminar la columna de la clase:
   • Dado que K-Means es un algoritmo no supervisado, eliminaremos la columna de la clase para que el algoritmo agrupe los datos sin saber a qué especie pertenecen las plantas.
   • Para eliminar la columna de la clase, en la pestaña “Preprocess”, seleccionar el atributo class y hacer clic en “Remove”.
3. Aplicar K-Means:
   • Ir a la pestaña “Cluster”.
   • Seleccionar el algoritmo SimpleKMeans de la lista de opciones.
   • Configurar el número de clústeres ( k = 3 ) (porque sabemos que hay tres especies diferentes).
   • Opcionalmente, podemos cambiar la opción “distance function” para usar la distancia euclidiana.
4. Ejecutar el Algoritmo:
   • Hacer clic en “Start” para ejecutar el algoritmo.
5. Interpretar los Resultados:
   • Weka proporcionará un informe con la asignación de clústeres a cada instancia y las coordenadas de los centroides de los tres clústeres.

Ejemplo de Salida de Weka para K-Means:

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

Cluster centroids:
                      Cluster 0   Cluster 1   Cluster 2
SepalLength               5.91        5.01        6.85
SepalWidth                2.75        3.43        3.07
PetalLength               5.56        1.46        5.67
PetalWidth                2.03        0.24        2.07

Clustered Instances
Cluster 0 50 (33%)
Cluster 1 50 (33%)
Cluster 2 50 (33%)

En este caso:

• Los centroides de los tres clústeres se muestran para cada uno de los atributos (SepalLength, SepalWidth, PetalLength, PetalWidth).
• El número de instancias asignadas a cada clúster es 50, lo que indica que el algoritmo ha agrupado de manera bastante uniforme las plantas en tres clústeres.

Interpretación:

• Cluster 0 tiene centroides con valores más altos de PetalLength y PetalWidth, lo que sugiere que agrupa las plantas que tienen pétalos más largos y anchos, probablemente asociadas con la especie Iris-virginica.
• Cluster 1 tiene centroides con valores bajos en PetalLength y PetalWidth, probablemente agrupando plantas de la especie Iris-setosa.
• Cluster 2 agrupa las plantas con características intermedias, probablemente relacionadas con Iris-versicolor.

Métricas para Evaluar el Rendimiento:

• Within Cluster Sum of Squared Errors (WSS): Esta métrica se utiliza para evaluar la calidad del agrupamiento, midiendo la suma de las distancias al cuadrado entre cada punto y su centroide.
• Elbow Method: Se puede utilizar el método del codo para determinar el número óptimo de clústeres observando la disminución de WSS a medida que se aumenta ( k ).

Opciones más relevantes del algoritmo SimpleKMeans en Weka:

1. Number of Clusters (-N):
   • Establece el número de clusters que se quieren generar. Por ejemplo, si deseas dividir los datos en 3 grupos, puedes establecer -N 3.
   • Valor predeterminado: 2.
2. Max iterations (-I):
   • Establece el número máximo de iteraciones para el algoritmo. Esto se refiere a cuántas veces el algoritmo ajustará los centroides de los clusters para mejorar la agrupación.
   • Valor predeterminado: 500.
3. Distance Function (-A):
   • Permite definir la función de distancia que se usará para medir la proximidad entre las instancias. El valor predeterminado es la distancia euclidiana, pero también puedes usar otras funciones como la distancia de Manhattan.
   • Ejemplo: -A "weka.core.ManhattanDistance" para usar la distancia de Manhattan.
4. Seed (-S):
   • Define la semilla para la generación de números aleatorios, lo cual afecta la inicialización de los centroides. Cambiar el valor de la semilla puede dar resultados diferentes.
   • Valor predeterminado: 10.
5. Canopy Clustering Initialization (-init):
   • Esta opción usa el algoritmo Canopy para seleccionar los puntos de inicio del algoritmo KMeans. Es útil cuando se tiene una gran cantidad de datos.
   • Valores:
     • 0: No usar.
     • 1: Usar.
6. Minimum Cluster Density (-min-density):
   • Define la densidad mínima requerida para formar un cluster. Si la densidad es menor, el cluster se considera inválido.
   • Valor predeterminado: 2.0.
7. Maximum Number of Candidates (-max-candidates):
   • Establece el número máximo de candidatos para formar clusters durante la ejecución del algoritmo.
   • Valor predeterminado: 100.
8. Periodic Pruning (-periodic-pruning):
   • Establece el número de veces que se realizará la poda periódica de candidatos para mejorar el rendimiento.
   • Valor predeterminado: 10000.
9. Don’t Replace Missing Values:
   • De forma predeterminada, SimpleKMeans reemplaza los valores faltantes en los datos con la media/mode de la columna correspondiente. Esta opción desactiva ese comportamiento si se marca.