Filtrar los puntos cercanos de una lista

Question

I respondí una pregunta sobre cómo encontrar grupos de masa en un mapa de bits . Digo media respuesta porque la dejé en una condición en la que tenía todos los puntos en el mapa de bits ordenados por masa y dejé que el lector filtrara la lista de puntos del mismo grupo.

Luego, al pensar en ese paso, descubrí que la solución no saltó hacia mí como pensé. Así que ahora les estoy pidiendo ayuda a ustedes. Tenemos una lista de puntos con masas como esta (una lista de tuplas de Python, pero puedes representarla como lo creas en cualquier idioma):

[ (6, 2, 6.1580555555555554),
  (2, 1, 5.4861111111111107),
  (1, 1, 4.6736111111111107),
  (1, 4, 4.5938888888888885),
  (2, 0, 4.54),
  (1, 5, 4.4480555555555554),
  (4, 7, 4.4480555555555554),
  (5, 7, 4.4059637188208614),
  (4, 8, 4.3659637188208613),
  (1, 0, 4.3611111111111107),
  (5, 8, 4.3342191043083904),
  (5, 2, 4.119574829931973),
  ...
  (8, 8, 0.27611111111111108),
  (0, 8, 0.24138888888888888) ]

Cada tupla es de la forma:

(x, y, mass)

Tenga en cuenta que la lista está ordenada aquí. Si su solución prefiere no tenerlas ordenadas, está perfectamente bien.

El desafío, si recuerdas , es Encuentra los principales grupos de masa. Se desconoce el número de grupos. Pero ya sabes las dimensiones del mapa de bits. A veces, varios puntos dentro de un grupo tienen más masa que el centro del siguiente grupo (en tamaño). Entonces, lo que quiero hacer es ir desde los puntos de mayor masa y eliminar los puntos en el mismo grupo (puntos cercanos).

Cuando intenté esto, terminé teniendo que repasar partes de la lista una y otra vez. Tengo la sensación de que soy estúpido al respecto. ¿Como lo harias? Pseudo código o código real. Por supuesto, si simplemente puede sacar el lugar donde lo dejé en esa respuesta con el código Python, es más fácil para mí experimentar con él.

El siguiente paso es averiguar cuántos clústeres hay realmente en el mapa de bits. Todavía estoy luchando para definir ese problema, así que podría volver con una pregunta al respecto.

EDITAR: Debería aclarar que sé que no hay " correcto " responder a esta pregunta Y el nombre de la pregunta es clave. La primera fase de mi agrupación está terminada. Estoy en busca de un rápido y preciso " suficiente " método de filtrar los puntos cercanos.

Hazme saber si ves cómo puedo aclarar la pregunta.

Answer 1

Para que sepas, estás pidiendo una solución para un mal planteado Problema: no existe una solución definitiva. Eso está bien ... solo lo hace más divertido. Su problema está mal planteado principalmente porque no sabe cuántos grupos desea. La agrupación en clústeres es una de las áreas clave del aprendizaje automático y existen varios enfoques que se han desarrollado a lo largo de los años.

Como señaló Arachnid, el algoritmo k-means tiende a ser bueno y Es bastante fácil de implementar. Los resultados dependen críticamente de la estimación inicial realizada y del número de grupos deseados. Para superar el problema de conjetura inicial, es común ejecutar el algoritmo varias veces con inicializaciones aleatorias y elegir el mejor resultado. Deberás definir qué " mejor " medio. Una medida sería la distancia cuadrática media de cada punto a su centro de agrupación. Si desea adivinar automáticamente cuántos clústeres hay, debe ejecutar el algoritmo con toda una gama de números de clústeres. Para cualquier bien " mejor " Como medida, más grupos siempre se verán mejor que menos, por lo que necesitará una forma de penalizar el tener demasiados grupos. El debate MDL en wikipedia es un buen punto de partida.

K-means clustering es básicamente el modelo de mezcla más simple. A veces es útil actualizar a una mezcla de gaussianos aprendidos por la maximización de las expectativas (descrita en el enlace que se acaba de dar). Esto puede ser más robusto que k-means. Se necesita un poco más de esfuerzo para entenderlo, pero cuando lo haces, no es mucho más difícil de implementar que k-medias.

Hay muchas otras técnicas de agrupación como la agrupación aglomerativa y la agrupación espectral. La agrupación aglomerativa es bastante fácil de implementar, pero elegir cuándo dejar de construir las agrupaciones puede ser complicado. Si realiza un agrupamiento aglomerado, probablemente querrá consultar kd trees para más rápido búsquedas de vecinos más cercanos. La respuesta de smacl describe una forma ligeramente diferente de hacer agrupamientos aglomerados usando un diagrama de Voronoi.

Hay modelos que pueden elegir automáticamente el número de clústeres para usted, como los basados ??en Asignación de Dirichlet latente , pero son mucho más difíciles de entender un implemento correctamente.

Es posible que también desee ver algoritmo de cambio de medias para ver si está más cerca de lo que realmente quieres.

Answer 2

Me parece que estás buscando el algoritmo K-means . / p>

Answer 3

Como mencioné en el comentario a su pregunta, la respuesta se basa en si la masa puede considerarse escalar o no en este contexto. Si es así, es probable que las soluciones basadas en el color no funcionen, ya que el color a menudo no se considera escalar.

Por ejemplo, si tengo un área determinada con 1 punto de masa alta, ¿es lo mismo que tener el mismo área con 10 puntos de 1/10 de la masa? Si esto es cierto, la masa no es escalar en este contexto, y tendería a mirar un algoritmo utilizado para captar de manera espacial valores similares no escalables, por ejemplo. diagramas voronoi .

En este caso, donde dos áreas voronoi adyacentes tienen una distancia y una coincidencia de masa lo suficientemente cercanas, se pueden agrupar juntas. Puede repetir esto para encontrar todos los grupos.

Si, por otro lado, su masa es escalable, o si la masa en una posición desconocida puede interpolarse desde los puntos circundantes, tendería a triangulate y contornea los datos de entrada y usa las áreas entre los contornos para encontrar grupos de masa similar.

Answer 4

Esto suena como cuantización de color, donde se reduce el número de colores en una imagen. Una forma sería trazar los colores en el espacio y combinar los grupos en el centro (o un promedio ponderado) de un grupo.

El nombre exacto del algoritmo que activó esta memoria me falla, pero editaré la respuesta si aparece, pero mientras tanto, debes mirar la cuantización del color y ver si algunos de los algoritmos son útiles.

Answer 5

Comience con el " Casco convexo " problema. También está buscando algunos " convex hull " -como racimos.

Tenga en cuenta que " agrupamientos " es vago Tienes una masa promedio en tu campo. Algunos puntos tienen una masa por encima de la media y otros por debajo de la media. ¿Qué tan por encima del promedio significa que has encontrado un grupo? ¿A qué distancia deben estar los nodos para formar parte de un clúster o un clúster separado?

¿Cuál es la diferencia entre dos picos de montaña y una cresta?

Tienes que calcular una " topografía " - Unir todos los puntos con igual densidad en regiones. Esto requiere que escoja un punto y resuelva su deseo desde un punto radialmente, ubicando posiciones donde las densidades son iguales. Puedes conectar esos puntos en regiones.

Si eligió su punto inicial con inteligencia, las regiones deberían anidar. Elegir tu punto de partida es fácil porque comienzas con máximos locales.

Answer 6

Ya que estás hablando de masa, ¿por qué no una solución basada en la gravedad? Un sistema de partículas simple no tendría que ser súper preciso, y no tendría que ejecutarlo durante mucho tiempo antes de poder hacer una mejor estimación del número de grupos.

Si tiene una mejor idea sobre los números de clúster, k-significa que el vecino más cercano se vuelve viable.