2010-10-14 24 views
16

Dado: Dado un conjunto de N puntos en el plano 2D (coordenadas xey), y un conjunto de N radios correspondientes a cada punto. Nos referiremos al disco de un punto como el disco centrado en el punto con su radio.clúster de 2d puntos

Problema: Agrupa los puntos. Un grupo de puntos es tal que cada punto CUALQUIERA cae dentro del disco de al menos otro punto del grupo O al menos otro punto del grupo cae dentro de su disco. Los clústeres de puntos individuales no cuentan como grupos.

Necesito un algoritmo para calcular esto de manera eficiente (preferiblemente sin recurrir a complicadas técnicas de hash espacial como kd-trees). Puedo conformarme con O (N^2) tiempo de ejecución pero definitivamente no más que O (N^3). Siento que esto debería ser simple, pero estoy atrapado en la naturaleza no recíproca de mi condición de agrupamiento.

En esencia, estoy buscando llenar el prototipo de la función C:

int cluster_points(
    size_t n, 
    point_t *pt, // length n list of points 
    double *radius, // length n list of radii for each point 
    int *cluster, // length n list of cluster indexes; -1 if not clustered 
    size_t *ncluster // number of clusters (number of distinct non -1 entries in cluster) 
); 

Ésta no es la tarea. Lo necesito como parte de un algoritmo de matriz para agrupar números complejos.

Respuesta

10

La solución de fuerza bruta es solo O (N), por lo que debería funcionar para usted.

1) Comience con todos los puntos en el grupo sin asignar.

2) Seleccione un punto y observe todos los demás en el grupo sin asignar y vea si cumple con el criterio de radios que describe.

  • 2a) Si es así, iniciar un grupo, y continuar con el resto de puntos para ver si encajan en este grupo (basado en su punto actual), y si encajan en, moverlos de el grupo no asignado en este nuevo.
  • 2ab) Cuando haya terminado con el punto actual, vaya a cada punto agregado al grupo y verifique todos los puntos en el grupo no asignado.
  • 2b) Pero, si no hay punto que coincide con los criterios de radios para el punto actual, desprenderse de ella.

3) Al final se habrán agrupado los puntos por sus criterios, y se han hecho no más de N * (N/2) inspecciones.

Por cierto, lo que describes no es lo que normalmente se entiende por "agrupación", por lo que creo que está tirando la gente de aquí. Lo que hace que la agrupación sea un problema difícil es que la cuestión de si dos puntos vecinos se asignarán al mismo clúster está determinada por todos los otros puntos en el conjunto de datos. En su caso, (básicamente) solo está determinado por las propiedades de los dos puntos, por lo que en su caso, puede verificarlos todos.

+1

En el paso 2ab, ¿no tienes que seguir yendo a todos los puntos agregados y mirar el resto de los puntos sin asignar hasta que no se asigne nada nuevo? –

+0

@VictorLiu: No lo creo. Con este método, una vez que haya establecido el grupo 1 (y se haya movido al grupo 2), el grupo 1 contiene todos los puntos que se ajustan a los criterios y que alguna vez pertenecerán a este grupo. Al definir el grupo 1, cada vez que le agrega un punto, barre todos los otros puntos para ver si ahora pueden estar en el grupo. No hay posibilidad de que, por ejemplo, tengas que unirte al grupo 1 y al grupo 2, una vez que se haya establecido el grupo 1. – tom10

3

k-means clustering basan en una combinación de búsqueda local y el algoritmo de Lloyd

http://www.cs.umd.edu/~mount/Projects/KMeans/
(Programa se distribuye bajo las condiciones de la Licencia Pública General de GNU.)

k-medias, k- medianas, K-medoids, treecluster, mapas de auto-organización, clustercentroids, clusterdistance http://bonsai.hgc.jp/~mdehoon/software/cluster/cluster.pdf

+0

k-medias no es una opción. Quiero la métrica de inclusión precisa que describí anteriormente. –

2

la agrupación es un problema NP-duro, incluso si se le da el número de grupos a priori, por lo que probablemente pueda darse por vencido al obtener un tiempo de ejecución polinomial. Hay muchas técnicas para hacer esto y la literatura se encuentra principalmente en la comunidad de aprendizaje automático, k-means es probablemente el algoritmo más fácil de entender e implementar.

+0

No creo que me refiero a la agrupación en ese momento. Puede imaginar que si todos los radios son iguales, puede recorrer todos los pares y determinar si los pares deben estar en un solo grupo. Esto define una matriz de incidencia del gráfico de relaciones de clúster. Después de eso, solo necesitas encontrar los componentes conectados del gráfico (no estoy buscando camarillas). Creo que todo esto es tiempo polinomial. –

+0

Ok, esto ayuda un poco, pero aún no estoy 100% claro sobre lo que estás buscando. Principalmente me pregunto cómo quiere limitar el tamaño o la cantidad de clústeres, es decir, qué me impide declarar siempre que todos los puntos están en el mismo clúster (suponiendo que esté completamente conectado). – fairidox

+0

Bien, imagine esto geométricamente. Tengo un montón de puntos en el avión, y cada punto tiene un radio designado, así que realmente estoy colocando un montón de discos en el avión. Quiero encontrar todos los grupos de discos que se tocan; los clústeres son puntos por los cuales sus discos se superponen para formar una región no circular más grande en el plano (posiblemente con agujeros). No hay límite para el tamaño o la cantidad de clústeres; si los radios son todos cero, entonces no hay clústeres. Si los radios son todos enormes, entonces solo hay un grupo. –

2

Parece que el algoritmo obvio O (n^2) sería crear un gráfico con los puntos como vértices, y luego conectar dos puntos si se cumplen las condiciones dadas. Y luego lee los componentes conectados del gráfico, descartando singletons. Además, la condición que le dio a la agrupación me suena simétrica. ¿Me estoy perdiendo de algo?

+0

Tenía la esperanza de hacer esto en O (1) espacio, pero hacer lo obvio podría ser más sencillo. La condición del clúster es simétrica, pero para una implementación de bucle doble, no lo es. –

2

usted tiene una colección U de pares (p, R) donde P es un punto y R su radio.

La relación ~ en U: (p, R) ~ (q, S) < => p se encuentra en el disco de qo q se encuentra en el disco de p < => | p-q | < = max (R, S)

es claramente reflexivo y simétrico, por lo que su cierre transitivo (~ , por ejemplo) es una relación de equivalencia. Las clases de equivalencia bajo ~ serán (singletons o) clusters.

I belive existen algoritmos estándar para calcular las clases de equivalencia de la clausura transitiva de una relación como ~ anteriormente. Por ejemplo, esto se analiza en Recetas numéricas en el capítulo sobre clasificación, y dicen que su rutina se basa en Knuth.

(En este momento no proporcionar un enlace, sino una breve búsqueda no subió con exactamente lo correcto).

Cuestiones relacionadas