Si alguna vez ha visto a un grupo de turistas acompañados por una pareja de guía de turistas,

estos últimos con una gran sombrilla cada uno y los turistas del grupo intentando seguir a uno
de los dos guías, entonces ha visto, de cierta manera, una versión dinámica del algoritmo k-
medias. Nuestra situación aquí es más simple, ya que los datos (que hacen las veces de
turistas en el ejemplo) no son los que se mueven, sino los guías de turistas (sólo son dos).

Suponga que queremos dividir nuestros datos de entrada en k categorías o clústers, en donde
conozcamos de antemano el valor de k (por ejemplo, supongamos que contamos con un
conjunto considerable de personas que sufren una de entre tres enfermedades distintas, con
los resultados de una prueba médica para cada persona y queremos ver qué tan bien esas
pruebas pueden identificar qué enfermedad tiene la persona). Ahora, vamos a ubicar un total
de k centros de clúster, a lo largo del espacio asociado a nuestros datos de entrada y nos
gustaría ubicar cada centro justo en el medio de uno de los clústers. Sin embargo, no sabemos
de antemano dónde estan los clústers en el espacio de entrada, ya ni se diga de sus
centroides, por lo que necesitamos un algoritmo que lo encuentre por nosotros. Los algoritmos
de aprendizaje generalmente tratan de minimizar algún criterio de error, así que necesitamos
aquí establecer el criterio de error que describa mejor nuestro objetivo. La idea de “en el medio”
es la primera a la que podemos acudir. ¿Cómo definimos “en el medio” de un conjunto
arbitrario de puntos en el espacio? De hecho, hay dos cosas que debemos definir primero:

Una medida de distancia. Para poder hablar acerca de distancias entre puntos, primero
necesitamos alguna manera de medir distancias. Usualmente se utiliza la distancia euclidiana
aunque existen más alternativas; cubriremos algunas de ellas en la sección 7.2.3.

La media promedio. Una vez elegida una medida de distancia, podemos calcular el punto
central de un conjunto de puntos de entrada, el cual es la media promedio (si esto no le
convence, piense sobre cuál sería la media de dos puntos cualquiera, el cual es el punto medio
sobre la línea recta que une a esos dos puntos). En realidad, esto sólo aplica al espacio
euclidiano, donde todo es bonito y plano. Todo se vuelve más truculento si tuviéramos que
pensar en espacios curvos; cuando hay que preocuparse por la curvatura, la medida de la
distancia euclidiana no es la adecuada y hay por lo menos dos definiciones diferentes de
media. Así que no vamos a preocuparnos por ninguna de estas situaciones y asumiremos que
el espacio de entrada es plano, no curvo. Es lo que los estadísticos (los que trabajan con
estadística) hacen todo el tiempo.

Pensemos ahora en una forma apropiada de posicionar los centros de los clústers: podemos
calcular la media de cada clúster, uc(i), y poner ahí el centro. Esto es equivalente a minimizar la
distancia euclidiana (que a su vez es una medida de error de sumas de cuadrados) desde cada
punto del clúster al centro.

¿Cómo decidimos qué puntos pertenecen a cuál clúster? Esto es importante definirlo, ya que
nos sirve para posicionar los centros de los clústers. Lo más obvio sería asociar cada punto con
el clúster cuyo centro esté más cercano. Esto puede ir cambiando mientras el algoritmo va
iterando, pero por ahora está bien.

Empecemos por posicionar los centros de clústers en posiciones al azar sobre el espacio de
entrada, puesto que no tenemos mejor idea de dónde ponerlos en un comienzo, para luego ir
actualizando esas posiciones conforme los datos de entrada. Decidiremos a qué clúster le
corresponde a cada punto de entrada calculando la distancia entre el punto y todos los centros
de clúster existentes, asignando el punto al clúster cuyo centro es el más cercano. Nótese que
se podría reducir el coste computacional de este procedimiento mediante el uso de algoritmos
con árboles KD tal y como se describió en la sección 7.2.2. Luego, para todos los puntos que
fueron asignados a un determinado clúster, calculamos su media y reubicamos el centro del
clúster justo a la ubicación de esa media. Iteramos el algoritmo hasta que los centros de todos
los clústers dejen de cambiar de posición.

Algoritmo k-medias

· Inicialización
o Elegir un valor para k
o Elegir k posiciones aleatorias en el espacio de entrada
o Asignar a cada clúster uj una de esas posiciones
· Aprendizaje:
o Repetir
 * por cada punto de entrada xi:
· Calcular la distancia a cada centro de clúster
· Asignar el punto al centro de clúster más cercano, con distancia
di=min d(xi, uj)
 * por cada centro de clúster:
· Mover la posición del centro a donde está la media de los puntos
en ese clúster (Nj es el número de puntos en el clúster)

o Hasta que los centros de los clústers dejen de moverse.

· Utilización:
o Para cada punto nuevo a probar:
 * calcular la distancia a cada centro de clúster
 * asignar el punto nuevo al clúster más cercano con distancia

La implementación de NumPy sigue los pasos del algoritmo descrito casi exactamente y
podemos tomar ventaja de del uso de la función np.argmin(), la cual regresa el índice del valor
mínimo, para poder así encontrar el clúster más cercano. El código para calcular las distancias,
encontrar el clúster más cercano y actualizar los centros puede ser el siguiente:
Figura 14.1 Izq: Un conjunto de puntos en un espacio 2-dimensional. Der: Tres posibles
maneras de posicionar los 4 centros inicialmente (dibujados como caritas) según k-medias. Se
puede ver claramente que esto es susceptible a mínimos locales.

Para poder ver cómo trabaja todo esto en la práctica, las figuras 14.1 y 14.2 muestran algo de
datos de entrada y algunas formas en las que quedarían “clusterizados” después de ejecutar k-
medias. Debe estar claro que el algoritmo es susceptible a mínimos locales: dependiendo de
en dónde quedan ubicados los centros inicialmente, el algoritmo entregará soluciones
diferentes y muchas de ellas no serán para nada agradables a nuestros ojos. Figura 14.2
muestra ejemplos de qué es lo que pasa cuando escoges el número de centros (o clústers) de
forma errónea. Hay ciertos casos en los que no sabemos a priori cuántos clústers pueden
formarse en los datos y el algoritmo de k-medias no maneja esto muy bien que digamos.

A costa de más trabajo computacional, podemos subsanar estos problemas ejecutando el

algoritmo varias veces. Para encontrar un óptimo local que sea bueno (o incluso llegar a
encontrar el óptimo global) podemos usar diferentes puntos iniciales para los centros y la
solución que minimice el error de suma de cuadrados generalmente será la mejor solución.
Figura 14.2 Izq: Solución con solo dos clústers, la cual no ajusta los datos muy bien que
digamos. Der: Una solución con 11 clústers, mostrando sobreajuste severo.

Por otro lado, ejecutando el algoritmo con diferentes valores de k, podríamos ver cuál valor es
el que da la mejor solución. Por supuesto, hay que proceder con cuidado con esto. Si
solamente medimos el error de suma de cuadrados entre cada punto de entrada y su centro de
clúster más cercano, entonces cuando tengamos k igual al número de puntos de entrada,
tendremos los centros de clúster justo en cada punto de entrada y el error de suma de
cuadrados sería cero (de hecho, esto no podría pasar, dada la naturaleza aleatoria de las
posiciones iniciales de los centros de los clústers y estos tendrían que coincidir con suerte
desde la inicialización). Sin embargo, el aprendizaje realizado realmente no realiza una buena
generalización en esta situación, hablamos de un caso de severo de sobreajuste. Sin embargo,
al calcular el error en un conjunto de datos de validación y multiplicando el error por k podemos
ver algo acerca del beneficio de agregar un clúster más.

14.1 Lidiando con ruido

Hay muchas razones para elegir métodos de clustering (como k-medias), pero una de las más
comunes es el lidiar con el ruido en las lecturas de donde provienen los datos de entrada. Tales
lecturas pueden estar ligeramente corruptas o de plano estar mal. Si pudiéramos escoger el
número de clústers y su ubicación correctamente, entonces podríamos remover el ruido,
reemplazando cada dato de entrada con ruido por el centroide del clúster correspondiente
(usaremos esta forma de representar los datos para otros propósitos en la sección 14.2).
Desafortunadamente, la media promedio, la cual es importante para el algoritmo de k-medias,
es muy susceptible a valores atípicos (outliers), en otras palabras, a valores con ruido. Una
forma de evitar este problema es reemplazar la media promedio con la mediana, conocida por
ser robusta, ya que es mucho menos susceptible a los valores atípicos (la media de
(1,2,1,2,100) es 21.2, mientras que la mediana es 2). El único cambio que habría que hacerle al
algoritmo es cambiar el cálculo de la media por el de la mediana, la cuál es
computacionalmente más costosa, pero mucho más efectiva removiendo el ruido.