Fundamentos de K-Means y KNN: Métodos de Agrupamiento y Clasificación en Machine Learning

Algoritmo K-Means (K-Medias)

Objetivos del K-Means

El K-Means es un método de agrupamiento (clustering) que permite determinar grupos de observaciones con características similares (clústeres). Las observaciones obtenidas deben ser parecidas entre los miembros de un mismo grupo y diferentes de los miembros de otros grupos.

Si encontramos 4 grupos y las observaciones de estos 4 grupos se parecen mucho, realmente tenemos un solo grupo. Nuestro deseo es maximizar la variación interclúster y minimizar la variación intraclúster.

Funcionamiento del K-Means

1. Elegir un valor de $k$.
2. Seleccionar $k$ objetos en forma arbitraria. Utilizar estos como el conjunto inicial de $k$ centroides.
3. Asignar cada observación al grupo con la media más cercana (es decir, la partición de las observaciones de acuerdo con el diagrama de Voronoi generado por los centroides).
4. Calcular los nuevos centroides como el centroide de las observaciones en el grupo para todos los clústeres $k$.
5. Repetir los pasos 3 y 4 hasta que los centroides ya no se muevan.

Definición de Centroide

En geometría, el centroide de un objeto $X$ perteneciente a un espacio $n$-dimensional es la intersección de todos los hiperplanos que dividen a $X$ en dos partes de igual $n$-volumen con respecto al hiperplano. El Sum of Squared Error (SSE) sobre un punto de referencia es mínima cuando ese punto es el centroide del clúster.

Limitaciones del K-Means

El K-Means presenta problemas cuando los clústeres difieren en:

• Tamaño
• Densidad
• Figuras no redondeadas

Además, el K-Means tiene problemas con los outliers (valores atípicos).

Evaluación de Clústeres y Métricas de Calidad

Conceptos Fundamentales

Cohesión

Mide cuán estrechamente relacionados están los objetos dentro del clúster.

Separación

Mide cuán distintos o bien separados está un clúster de los otros.

Propósito de la Evaluación de Clústeres

De la misma forma que se tienen medidas para evaluar cuán bueno es un modelo de clasificación supervisado, se busca evaluar la calidad de los agrupamientos resultantes. A menudo se dice que “los clústeres están en el ojo del observador”.

¿Para qué evaluarlos?

• Para evitar ruido en los patrones.
• Para comparar resultados con distintos algoritmos de clustering (distintos métodos y distancias).
• Para comparar dos conjuntos de clústeres para ver cuál agrupamiento resulta mejor.
• Para ver los grupos que se forman naturalmente y si se corresponden con algún agrupamiento externo.

Clasificación de las Medidas de Evaluación Numérica

Las medidas de evaluación de clústeres numéricas se clasifican en:

• Externas: Usadas para medir la correspondencia entre el alcance del grupo y las etiquetas de clases provistas externamente. Ejemplo: Entropía.
• Internas: Usadas para medir la bondad de la estructura del clúster sin tener en cuenta información externa. Ejemplo: Sum of Squared Error (SSE).
• Relativas: Usadas para comparar dos agrupamientos o dos grupos diferentes. Generalmente se usa alguno de los índices internos o externos para esta función (ejemplo: SSE o Entropía).

Coeficiente de Silhouette

El Coeficiente de Silhouette mide cuán buena es la asignación de un elemento o dato a su grupo. Combina las ideas de cohesión y separación. Para esto, compara las distancias de este elemento respecto a todos los demás elementos del grupo al que pertenece, contra las distancias respecto a los grupos vecinos.

Algoritmo K-Nearest Neighbors (KNN)

Requisitos del KNN

El algoritmo KNN requiere tres partes fundamentales:

1. Un conjunto de datos guardados (entrenamiento).
2. Una medida de distancia entre los registros.
3. El valor de $k$, el número de vecinos más cercanos a consultar.

Clasificación de un Registro Desconocido

Para clasificar un registro desconocido, se siguen los siguientes pasos:

1. Se computa la distancia a los registros de entrenamiento.
2. Se identifican los $k$ vecinos más cercanos.
3. Se usa la clase de los vecinos más cercanos para determinar la clase del registro (por ejemplo, tomando votación por mayoría).

Funcionamiento Detallado del KNN

Los $K$-vecinos más cercanos de un registro $x$ son los puntos de datos que tienen las $k$ distancias más pequeñas a $P$.

Proceso de Determinación de Clase

1. Se calcula la distancia entre dos puntos.
2. Determinar la clase a partir de la lista de vecinos más cercanos:
   • Tomar el voto por mayoría entre los $k$-vecinos más cercanos.
   • Asignarle peso a los votos de acuerdo a la distancia (factor de peso).