Saturday, June 7, 2008

K-means y gravedad

Espero que este articulo cierre con un moño azul

 

Disclaimers: Articulo computronico. Drito, no te quejes

Mirando un poco una implementación de k-means me di cuenta que uno de los problemas que tenia era que los puntos no tenían “conciencia” de su posición en el espacio ni de su entorno. Básicamente, un punto era un placeholder de coordenadas, y nada mas.

Como resolver este problema era algo que empezó a dar vueltas por mi cabeza. No llegue a ninguna solución (me adelanto, y bajo las expectativas sobre este post). A pesar de eso, me di cuenta de que el universo esta todo el tiempo haciendo k-means. Básicamente, la gravedad es una función de la distancia entre los cuerpos (y también de la masa, pero gracias al 1, podemos olvidarnos momentáneamente de eso).

Los cuerpos en el espacio “sufren” y la atracción gravitacional de otros cuerpos (no toman conciencia de esa atracción, pero tiene un impacto sobre estos cuerpos). Entonces, el modelo que planteo es pensar a los distintos puntos como distintos cuerpos (a priori, con masa igual a 1), y en determinar los clusters en base a los conjuntos donde las relaciones gravitatorias son mas fuertes (de la misma manera que existen planetas, sistemas planetarios, sistemas de estrellas, galaxias, etc.). Ahora se produce un cambio de la relación, en vez de ser la relación de cada punto contra la media teórica de los clusters, la relación es entre cada unos de los cuerpos (creo que es un poco lo que se hace en fuzzy k-means).

Hasta ahora este cambio de metáfora no aporta nada (es mas, agranda la complejidad algorítmica, lo que no es bueno). Sin embargo, creo que se pueden hacer agregados de cuerpos. Esto seria, definir un Epsilon, y en base a ese Epsilon crear esferas, cuya densidad depende de la cantidad de puntos de esta esfera y del tamaño del Epsilon (volvemos a algo parecido a k-means). Ahora, estos cuerpos pasan a ser iguales a el resto de los cuerpos (no agregados), y solamente difieren en la densidad (y acá si podemos empezar a utilizar feature propios de la gravedad).

Ahora aparece un problema con la definición de un Epsilon. Si hacemos una esfera de un radio determinado, estamos suponiendo implícitamente que los puntos van a estar distribuidos uniformemente en las n dimensiones. Este supuesto es demasiado fuerte. Quizás, algo que se podría hacer es hacer una ponderación en las dimensiones donde los puntos tienen mayor variabilidad. Bueno, básicamente esto seria proyectar todos los puntos en el espacio de los autovectores de la matriz de varianza/covarianza. Es decir, utilizar PCA (sin perdida de información).

Una vez que realizamos esta proyección, nos queda una topología donde, en principio, tiene mas sentido utilizar una esfera para crear los agregados.

 

Creo que una de las ventajas que puede tener esta metáfora es con respecto a las proyecciones.

Pensando por ejemplo en el tiempo. Si el tiempo no es una variable endógena (no es una de las n dimensiones), y quisiéramos hacer una extrapolación. Es decir, quisiéramos hacer una proyección sobre la posición futura de los distintos cuerpos, creo que tiene sentido estadístico utilizar los mismos modelos que se utilizan en la física para establecer la posición futura de un cuerpo en movimiento (es decir, para donde caen las manzanas). Creo que los datos pasados nos podrían ayudar para calcular la velocidad de los cuerpos, y quizás nos ayudarían a detectar “agujeros negros” en nuestra muestra.

De cualquier manera, estas son especulaciones teóricas, recién tengo planeado cursar física del CBC el cuatrimestre próximo, ahí quizás tenga alguna idea mas acabada sobre este tema