¿Cómo agrupo objetos en un conjunto por proximidad?

Question

Tengo un conjunto que contiene miles de direcciones. Si puedo obtener la longitud y latitud de cada dirección, ¿cómo divido el conjunto en grupos por proximidad?

Además, es posible que desee volver a intentar el 'agrupamiento' de acuerdo con diferentes reglas:

• N grupos
• M direcciones por grupo
• distancia máxima entre cualquier dirección en un grupo

Answer 1

Puede probar el algoritmo k-means clustering .

Answer 2

Desea la cuantización vectorial:

http://en.wikipedia.org/wiki/Vector_quantization

" Funciona dividiendo un gran conjunto de puntos (vectores) en grupos que tienen aproximadamente el mismo número de puntos más cercanos a ellos. Cada grupo está representado por su punto centroide, como en k-means y algunos otros algoritmos de agrupación. & Quot;

Aquí los vectores son las coordenadas geográficas de cada dirección, y puede alimentar sus algoritmos con otros parámetros dependiendo de sus restricciones (proximidad, tamaño de grupo, número de grupos ...).

Puede comenzar con k-means, pero desde mi experiencia, un algoritmo basado en Voronoi es más flexible. Una buena introducción aquí .

Answer 3

Depende un poco de la escala de los datos que desea agrupar. El enfoque de la fuerza bruta es calcular la distancia entre todas las combinaciones de puntos en una matriz de distancia. La matriz resultante es N ^ 2 y dado que la distancia de A a B es la misma que B a A, solo necesita la mitad, por lo que el conjunto resultante es N ^ 2/2.

Para coordenadas lat lon relativamente cercanas, a veces puede salirse con la suya usando una cuadrícula x, y y calcular la distancia cartesiana. Como el mundo real no es plano, la distancia cartesiana tendrá un error. Para un cálculo más exacto que debe usar si sus direcciones se encuentran en todo el país, consulte este enlace de Mathforum.com .

Si no tiene la escala para manejar la matriz de distancia completa, necesitará realizar una programación de algoritmos para aumentar la eficiencia.

Answer 4

El " N grupos " y " M direcciones por grupo " Las restricciones son mutuamente excluyentes. Uno implica el otro.

Answer 5

1. Cree una matriz de distancias entre todas las direcciones.
2. Comenzando con una dirección aleatoria, clasifique la matriz por distancia ascendente a esa dirección
3. Eliminando las direcciones de la matriz a medida que avanza, coloque las direcciones más cercanas a la dirección de inicio en un nuevo grupo hasta que alcance sus criterios (tamaño del grupo o distancia máxima).
4. Una vez que un grupo está lleno, elija otra dirección aleatoria y recurra la matriz por distancia a esa dirección
5. Continúe así hasta que todas las direcciones se saquen de la matriz.

Si las direcciones se distribuyeran de manera uniforme, cada grupo tendría una especie de forma circular alrededor de la dirección de inicio. El problema surge cuando las direcciones de inicio están cerca de grupos existentes. Cuando esto sucede, el nuevo grupo se ajustará al anterior e incluso podría rodearlo por completo si su criterio de detención es solo el tamaño del grupo. Si usa la restricción de distancia máxima, esto no va a suceder (suponiendo que no haya otras restricciones).

Realmente no sé si esta es una buena manera de hacerlo, pero es lo que probaría. Estoy seguro de que se necesitaría mucha optimización. Especialmente para direcciones en los bordes.