Este es un caso especial interesante donde k-means se puede optimizar de manera eficiente y de manera óptima a nivel mundial. Como la dimensión es una y tiene dos grupos, habrá un “punto de interrupción” en el que todos los puntos a su izquierda pertenecerán a un grupo y todos los puntos a su derecha pertenecerán al otro grupo.
Para encontrar el punto de interrupción óptimo, simplemente podemos ordenar los datos en orden creciente, [matemática] x_1 <x_2 <… <x_m [/ matemática], luego marchar a través de ellos uno por uno, decidiendo si cada punto [matemática] x_i [/ matemática ] en la secuencia es el punto de interrupción óptimo.
Para calcular esta “puntuación de breakpointiness” para un punto dado [matemáticas] x_i [/ matemáticas], necesitamos calcular la suma de las distancias al cuadrado a la media de todos los puntos a la izquierda de [matemáticas] x_i [/ matemáticas] y el suma de distancias al cuadrado a la derecha de [math] x_i [/ math]. Notarás que esta es simplemente la puntuación que k-means ordinaria intenta minimizar de forma iterativa (a veces llamada “distorsión”).
- ¿Cuáles son los tipos de algoritmos más básicos y complicados?
- ¿Qué proyectos de aprendizaje automático se ven bien en un currículum?
- Soy un desarrollador de fuerza bruta, ¿cómo puedo mejorar mis habilidades de algoritmos?
- Si F2L se resuelve mejor de forma intuitiva, ¿por qué cada tutorial incluye algoritmos para todos los casos de F2L?
- Dadas las coordenadas de 3 puntos, cómo encontrar el centro del círculo formado por estos puntos con alta precisión. Para lograr una alta precisión, debe haber algún proceso de división. ¿Hay alguna forma de hacerlo?
En este punto, puede elegir hacer esto de la manera ingenua, lo que requeriría un tiempo lineal en el tamaño del conjunto de datos para calcular una puntuación de punto crítico por punto, lo que resulta en una complejidad final de [matemáticas] O (m ^ 2) [/ matemáticas ] para k-medias. Pero también puede notar que al almacenar en caché las sumas de [math] x_i [/ math] (y sus cuadrados), puede actualizar la puntuación en tiempo constante por punto, lo que resulta en una complejidad final de [math] O ( m) [/ math] para encontrar el mejor punto de interrupción (aunque todavía [math] O (m \ log m) [/ math] en total debido al paso de clasificación).
Y luego, una vez que tenga estos puntajes, simplemente devuelve el agrupamiento correspondiente al mejor puntaje (es decir, el más bajo), ¡y eso es todo! Si desea un desafío adicional, puede pensar en cómo extender este truco de “programación dinámica” para manejar números arbitrarios de clústeres en 1 dimensión.
