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

4 comments:

VorteX said...

Lo leí... y no entendí nada! ufa.

jb said...

claramente hubo un problema al momento de escribir este post entre el teclado, y el respaldo de la silla del que lo escribio.
Espero que pronto salga otra version

Mariana Soffer said...

Es una idea muy interesante, yo la pense hace poco, creo que se puede hacer algo muy copado con esto, pero no aplicado a el tipo de clustering que se puede
usar en datamining y estadistica multivariada, ya que algo fundamental en todos estos algoritmos es que los puntos del dataset son estaticos.

El universo no esta haciendo todo el tiempo el clasico k-means, el k-means que esta haciendo es el que incluye las reglas de gravedad de newton:

1. Every object in a state of uniform motion tends to remain in that state of motion unless an external force is applied to it.

2. The relationship between an object's mass m, its acceleration a, and the applied force F is F = ma. Acceleration and force are vectors (as indicated by their symbols being displayed in slant bold font); in this law the direction of the force vector is the same as the direction of the acceleration vector.

Another difference is that measures used in the models are in different units, for example in gravitational you have (ft/s2), but not in k-means.

Por lo tanto el kmeans gravitacional tiene un grado mayor de complejidad ya que incluye la masa del objeto,la fuerza aplicada, la aceleracion.

La gravedad no es una funcion de distancia. La atraccion de un cuerpo hacia otro el cual es generador del desplazamiento de los puntos no tiene relacion con las funciones de distancia, las cuales deforman el hyperespacio causando que los diferentes tipos de distancias entre dos mismos puntos puntos tengan diferentes valores segun el tipo de distancia utilizada (euclidiana,manhattan,taxicab...)

Hay un algoritmo llamado ISODATA que hace algo muy parecido a lo que vos propones con el epsilon, pero, no uses epsilon, epsilon se usa para la condicion de terminacion
de el algoritmo, cuando el valor anterior de la funcion objetivo menos el valor siguiente es menor a epsilon este termina.

Con respecto al parrafo que habla de pca, es muy hacertada una parte de lo que decis, de hecho muchos algoritmos de clustering ponderan la matriz de pertenencia a partir
de mu y la varianza. Esto es totalmente logico, ya que los distintos clusters no tienen porque tener las mismas mu y varianzas. Es mas tambien se puede cambiar la funcion de distribucion y no usar la funcion normal sino cualquier otra que se yo como chi cuadrado.
Lo de PCA lo estoy meditando, pero me parece que no es asi.

Los ultimos dos parrafos, acerca de utilizar los mismos modelos me resulta una idea genial, no la conocia, pero me puse a investigar y hay montones de papers al respecto, me sorprendio.

PD:Javi me encanto salir conitigo
Carinios

Anonymous said...

we want miles... de posts más.
me encantó salir con vos bebé