algorithm - particionales - clustering ejemplos

Algoritmo de agrupamiento para Paper Boys (17)

Necesito ayuda para seleccionar o crear un algoritmo de agrupamiento según ciertos criterios.

Imagine que está administrando personas que reparten periódicos.

Usted tiene un conjunto de direcciones, cada una de las cuales está geocodificada.
Desea agrupar las direcciones para que cada clúster se asigne a una persona de entrega.
El número de personas de entrega, o clusters, no es fijo. Si es necesario, siempre puedo contratar más personas de entrega o despedirlas.
Cada grupo debe tener aproximadamente el mismo número de direcciones. Sin embargo, un clúster puede tener menos direcciones si las direcciones de un clúster están más dispersas. (Dicho de otra manera: número mínimo de clústeres donde cada grupo contiene un número máximo de direcciones, y cualquier dirección dentro del grupo debe estar separada por una distancia máxima).
Para los puntos de bonificación, cuando el conjunto de datos se altera (dirección añadida o eliminada) y el algoritmo se vuelve a ejecutar, sería bueno si los clústeres permanecieran lo más invariables posible (es decir, esto excluye el clúster de k-means simple que es al azar en la naturaleza). De lo contrario, las personas que entregan se volverán locas.

Entonces ... ¿ideas?

ACTUALIZAR

El gráfico de la red de calles, como se describe en la respuesta de Arachnid, no está disponible.

Buena encuesta de algos agrupados simples. Sin embargo, hay más: http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/index.html

Creo que quieres una técnica de aglomeración jerárquica en lugar de k-means. Si obtiene su algoritmo correcto, puede detenerlo cuando tenga el número correcto de clústeres. Como mencionó otra persona, puede sembrar agrupamientos posteriores con soluciones anteriores que pueden proporcionarle una mejora significativa en el rendimiento.

Es posible que desee examinar de cerca la función de distancia que utiliza, especialmente si su problema tiene una gran dimensión. La distancia euclidiana es la más fácil de entender pero puede que no sea la mejor, mire alternativas como Mahalanobis.

Supongo que su problema real no tiene nada que ver con la entrega de periódicos ...

En lugar de un modelo de agrupación, creo que realmente desea una variante del modelo de ubicación de configuración de cobertura, con una restricción adicional para cubrir el número de direcciones cubiertas por cada instalación. Realmente no puedo encontrar una buena explicación en línea. Puedes echarle un vistazo a esta página , pero la están resolviendo usando unidades de área y probablemente quieras resolverla en espacio euclidiano o de red. Si desea desenterrar algo en formato árbol muerto, consulte el capítulo 4 de Red y ubicación discreta de Daskin.

Puede hacer que los promedios K o la maximización esperada permanezcan lo más invariables posible utilizando el clúster anterior como una función de agrupamiento. Hacer que cada grupo tenga la misma cantidad de elementos parece un poco más complicado. Puedo pensar en cómo hacerlo como un paso posterior a la agrupación haciendo k medias y luego barajando algunos puntos hasta que las cosas se equilibren, pero eso no parece muy eficiente.

Lo que está describiendo es un (Multi) -Vehicle-Routing-Problem (VRP). Existe una gran cantidad de literatura académica sobre diferentes variantes de este problema, utilizando una gran variedad de técnicas (heurísticas, solucionadores listos para usar, etc.). Por lo general, los autores intentan encontrar soluciones buenas u óptimas para una instancia concreta, lo que también implica un agrupamiento de los sitios (todos los sitios en la ruta de un vehículo).

Sin embargo, los clústeres pueden estar sujetos a cambios importantes con instancias ligeramente diferentes, que es lo que desea evitar. Aún así, algo en los VRP-Papers puede inspirarte ...

Si decide seguir con el paso de clúster explícito, no olvide incluir su distribución en todos los clústeres, ya que es parte de cada ruta.

Para evaluar los conglomerados utilizando una representación gráfica de la cuadrícula de la calle probablemente obtendrá resultados más realistas que la conexión de los puntos en un mapa blanco (aunque ambos son variantes del TSP). Si un modelo de gráfico no está disponible, puede usar el taxicab-metric (| x_1 - x_2 | + | y_1 - y_2 |) como una aproximación para las distancias.

Me gustaría enfocarlo de manera diferente: considerando la red de calles como un gráfico, con un borde para cada lado de cada calle, encuentre una partición del gráfico en n segmentos, cada uno no más de una longitud determinada, de modo que cada repartidor pueda andar solo trayectoria continua desde el inicio hasta el final de su ruta. De esta forma, evitará darles a las personas rutas que les obliguen a recorrer los mismos segmentos repetidamente (por ej., Cuando se les pida que cubran ambos lados de una calle sin cubrir todas las calles circundantes).

Tal vez un árbol de expansión mínimo de los clientes, dividido en un conjunto basado en la localidad para el chico de papel. Prims o Kruskal para obtener el MST con la distancia entre casas para el peso.

Utilizaría un algoritmo básico para crear un primer conjunto de rutas de papel para periódicos de acuerdo con el lugar donde viven y las ubicaciones actuales de los suscriptores, y luego:

cuando paperboys son:

Agregado: toman ubicaciones de uno o más Paperboys que trabajan en la misma área general desde donde vive el nuevo tipo.
Eliminado: sus ubicaciones se otorgan a los otros Paperboys, utilizando las ubicaciones más cercanas a sus rutas.

cuando las ubicaciones son:

Agregado: Lo mismo, la ubicación se agrega a la ruta más cercana.
Eliminado: recién eliminado de la ruta de ese chico.

Una vez por trimestre, puede volver a calcular todo y cambiar todas las rutas.

¿Has pensado en usar una solución económica / basada en el mercado? Divida la configuración por un arbitrario (pero constante para evitar efectos de aleatoriedad) dividido en subconjuntos pares (según lo determinado por el número de personas entregadas).

Asigne una función de costo a cada punto por cuánto agrega al gráfico y otorgue a cada punto extra un valor económico.

Iteramos permitiendo a cada persona, a su vez, subastar su peor punto, y darle a cada persona un presupuesto máximo.

Esto probablemente coincida bastante bien con la forma en que la gente de reparto pensaría en la vida real, ya que las personas encontrarán intercambios, o dirán "mi vida sería mucho más fácil si no hiciera esto uno o dos. También es bastante flexible (para ejemplo, permitiría que un punto a millas de distancia de cualquier otro reciba una prima con bastante facilidad).

Este es un método muy rápido y sucio para descubrir dónde se encuentran sus "grupos". Esto fue inspirado por el juego "Buscaminas".

Divida todo su espacio de entrega en una cuadrícula de cuadrados. Nota: será necesario ajustar el tamaño de la cuadrícula antes de que funcione correctamente. Mi intuición me dice que un tamaño cuadrado aproximadamente del tamaño de un bloque de barrio físico será un buen punto de partida.

Pasa por cada cuadrado y almacena el número de ubicaciones de entrega (casas) dentro de cada bloque. Use un segundo ciclo (o algún método inteligente en el primer pase) para almacenar el número de puntos de entrega para cada bloque vecino.

Ahora puede operar en esta cuadrícula de forma similar al software de manipulación de fotos. Puede detectar los bordes de los clústeres al encontrar bloques donde algunos bloques vecinos no tienen puntos de entrega en ellos.

Finalmente, necesita un sistema que combine el número de entregas realizadas y la distancia total recorrida para crear y asignar rutas. Puede haber algunos clusters aislados con solo algunas entregas, y uno o dos súper clusters con muchos hogares muy cerca uno del otro, que requieren varias personas de entrega en el mismo clúster. Todos los hogares deben ser visitados, por lo que esa es su primera restricción.

Derive una distancia máxima permitida que debe recorrer cualquier persona de entrega en una sola ejecución. A continuación, haga lo mismo para la cantidad de entregas realizadas por persona.

La primera vez que se ejecute el algoritmo de enrutamiento asignaría una única persona de entrega, los enviará a cualquier agrupación aleatoria sin todas las entregas completadas, les permitirá entregar hasta que lleguen a su límite de entrega o se hayan entregado a todas las casas en el clúster. Si alcanzan el límite de entrega, finalice la ruta enviándolos a la base de operaciones. Si pudieran viajar con seguridad al clúster más cercano y luego a su casa sin tocar su distancia máxima de recorrido, hágalo y repita lo anterior.

Una vez que la ruta finaliza para la persona que realiza la entrega actual, verifique si hay casas que aún no han recibido una entrega. Si es así, asigne otra persona de entrega y repita el algoritmo anterior.

Esto generará rutas iniciales. Almacenaría toda la información: la ubicación y las dimensiones de cada cuadrado, el número de viviendas dentro de un cuadrado y todos sus vecinos directos, el grupo al que pertenece cada cuadrado, las personas encargadas de la entrega y sus rutas: almacenaría todos estos. en una base de datos

Dejaré el procedimiento recalc a usted, pero tener todas las rutas, clústeres, etc. actuales en una base de datos le permitirá mantener todas las rutas históricas, y también probar varios escenarios para ver cómo adaptarse mejor a los cambios creando la menor posibles cambios a las rutas existentes.

Una respuesta trivial que no obtiene ningún punto de bonificación:

Una persona de entrega para cada dirección.

Usted tiene un conjunto de direcciones, cada una de las cuales está geocodificada.
Desea agrupar las direcciones para que cada clúster se asigne a una persona de entrega.
El número de personas de entrega, o clusters, no es fijo. Si es necesario, siempre puedo contratar más personas de entrega o despedirlas.
Cada grupo debe tener aproximadamente el mismo número de direcciones. Sin embargo, un clúster puede tener menos direcciones si las direcciones de un clúster están más dispersas. (Dicho de otra manera: número mínimo de clústeres donde cada grupo contiene un número máximo de direcciones, y cualquier dirección dentro del grupo debe estar separada por una distancia máxima).
Para los puntos de bonificación, cuando el conjunto de datos se altera (dirección añadida o eliminada) y el algoritmo se vuelve a ejecutar, sería bueno si los clústeres permanecieran lo más invariables posible (es decir, esto excluye el clúster de k-means simple que es al azar en la naturaleza). De lo contrario, las personas que entregan se volverán locas.

Como se ha mencionado, un problema de enrutamiento de vehículos probablemente sea más adecuado ... Aunque estrictamente no está diseñado con la agrupación en mente, se optimizará para asignar en función de las direcciones más cercanas. Por lo tanto, sus clusters serán en realidad las rutas recomendadas.

Si proporciona una cantidad máxima de distribuidores y luego trata de alcanzar la solución óptima, esto debería indicarle el mínimo que necesita. Esto trata del punto 2.

Se puede obtener el mismo número de direcciones proporcionando un límite en el número de direcciones que se visitarán, básicamente asignando un valor de stock (ahora es un problema de enrutamiento vehicular capitado).

Agregar ventanas de tiempo u horas que las personas que entregan ayuda a reducir la carga si las direcciones están más extendidas (ahora un problema de enrutamiento vehicular captado con ventanas de tiempo).

Si usa un algoritmo de vecino más cercano, puede obtener resultados idénticos cada vez, eliminar una sola dirección no debería tener demasiado impacto en su resultado final, por lo que debería tratarse con el último punto.

De hecho, estoy trabajando en una biblioteca de clases C # para lograr algo como esto, y creo que es probablemente la mejor ruta para bajar, aunque no es necesariamente fácil de imponer.

Conozco un enfoque bastante novedoso de este problema que he visto aplicado a la Bioinformática, aunque es válido para cualquier tipo de problema de agrupamiento. Ciertamente no es la solución más simple, pero creo que es muy interesante. La premisa básica es que la agrupación implica múltiples objetivos. Por un lado, quiere minimizar el número de clusters, la solución de trival es un solo clúster con todos los datos. El segundo objetivo estándar es minimizar la cantidad de varianza dentro de un clúster, la solución trivial es que muchos clústeres tienen un solo punto de datos. Las soluciones interesantes surgen cuando intenta incluir estos dos objetivos y optimizar el equilibrio.

En el núcleo del enfoque propuesto se encuentra algo llamado algoritmo memético que se parece un poco a un algoritmo genético, lo cual se mencionó, aunque no solo explora bien el espacio de soluciones sino que también tiene la capacidad de centrarse en regiones interesantes, es decir, soluciones. Por lo menos recomiendo leer algunos de los trabajos sobre este tema ya que los algoritmos meméticos son un enfoque inusual, aunque una palabra de advertencia; puede llevarte a leer The Selfish Gene y todavía no he decidido si eso era algo bueno ... Si los algoritmos no te interesan, entonces tal vez puedas intentar expresar tu problema como lo requiere el formato y usar la fuente código provisto Los documentos y el código relacionados se pueden encontrar aquí: Agrupación de objetivos múltiples

Este es un ejemplo clásico de un problema que merece una solución optimizada en lugar de tratar de resolver para "The OPTIMUM". Es similar en algunos aspectos al " Problema del viajante de viajes ", pero también necesita segmentar las ubicaciones durante la optimización.

He utilizado tres algoritmos de optimización diferentes para obtener buenos resultados en problemas como este:

Utilizando un algoritmo de optimización, creo que ha descrito los siguientes "objetivos":

El área geográfica para cada niño de papel debe ser minimizada.
La cantidad de suscriptores atendidos debe ser aproximadamente igual.
La distancia recorrida por cada uno debe ser aproximadamente igual.
(Y uno que no mencionaste, pero podría importar) La ruta debería terminar donde comenzó.

Espero que esto te haga comenzar!

* Editar *

Si no le importan las rutas, eso elimina los objetivos 3 y 4 anteriores, y quizás permita que el problema se adapte mejor a sus requisitos de bonificación.

Si toma en cuenta la información demográfica (como la densidad de población, la tasa de adopción de suscripción y la tasa de cancelación de suscripción) probablemente pueda utilizar las técnicas de optimización anteriores para eliminar la necesidad de volver a ejecutar el algoritmo a medida que los suscriptores adopten o cancelen su servicio. Una vez optimizados los clusters, se mantendrían en equilibrio porque las tasas de cada uno para un clúster individual coincidían con las tasas de los otros clusters.

La única vez que tendría que volver a ejecutar el algoritmo fue cuando un factor externo (como una recesión / depresión) causó cambios en el comportamiento de un grupo demográfico.

Esto no está directamente relacionado con el problema, sino con algo que he escuchado y que debería considerarse si realmente se trata de un problema de planificación de ruta que tiene. Esto afectaría el orden de las direcciones dentro del conjunto asignado a cada controlador.

UPS tiene un software que genera rutas óptimas para que la gente de entregas las siga. El software intenta maximizar el número de giros a la derecha que se toman durante la ruta. Esto les ahorra mucho tiempo en las entregas.

Para las personas que no viven en los EE. UU., La razón para hacer esto puede no ser inmediatamente obvia. En los Estados Unidos, las personas conducen por el lado derecho de la carretera, por lo que cuando gire a la derecha no tendrá que esperar el tráfico en sentido contrario si la luz es verde. Además, en los EE. UU., Al girar a la derecha en una luz roja, usted (por lo general) no tiene que esperar al verde antes de poder ir. Si siempre está girando a la derecha, nunca tendrá que esperar a las luces.

Hay un artículo al respecto aquí: http://abcnews.go.com/wnt/story?id=3005890

Reconozco que esto no necesariamente proporcionará grupos de aproximadamente el mismo tamaño:

Una de las mejores técnicas actuales en la agrupación de datos es la acumulación de pruebas. (Fred y Jain, 2005) Lo que haces es:

Dado un conjunto de datos con n patrones.

Use un algoritmo como k-means en un rango de k. O use un conjunto de algoritmos diferentes, el objetivo es producir un conjunto de particiones.
Cree una matriz de coasociación C de tamaño nx n.
Para cada partición p en el conjunto:
3.1 Actualizar la matriz de asociación conjunta: para cada par de patrones (i, j) que pertenece al mismo grupo en p, establezca C (i, j) = C (i, j) + 1 / N.
Use un algoritmo de agrupamiento como Single Link y aplique la matriz C como medida de proximidad. Single Link da un dendrograma como resultado en el que elegimos la agrupación con la duración más larga.

Proporcionaré descripciones de SL y k-means si estás interesado.

Escribí un algoritmo ineficiente pero simple en Java para ver qué tan cerca podía llegar a hacer algunos clusters básicos en un conjunto de puntos, más o menos como se describe en la pregunta.

El algoritmo funciona en una lista if (x, y) coords ps que se especifican como int s. También se necesitan otros tres parámetros:

radio ( r ): dado un punto, ¿cuál es el radio para escanear puntos cercanos?
direcciones máximas ( maxA ): ¿cuál es el número máximo de direcciones (puntos) por clúster?
direcciones minA ( minA ): direcciones mínimas por clúster

Establecer limitA=maxA . Repetición principal: Inicializa las possibleSolutions soluciones de la lista vacía. Iteración exterior: para cada punto p en ps . Inicializa los pclusters lista pclusters . Se define una lista de trabajo de puntos wps=copy(ps) . Punto de trabajo wp=p . Repetición interna: mientras que wps no está vacío. Retire el punto wp en wps . Determine todos los puntos wpsInRadius en wps que están a una distancia < r de wp . Clasifique wpsInRadius ascendente de acuerdo con la distancia de wp . Mantenga los primeros min(limitA, sizeOf(wpsInRadius)) en wpsInRadius . Estos puntos forman un nuevo cluster (lista de puntos) pcluster . Agregue pcluster a pclusters . Eliminar puntos en pcluster de wps . Si wps no está vacío, wp=wps[0] y continúa la iteración interna. Finaliza la iteración interna. Se obtiene una lista de clusters pclusters . Agregue esto a possibleSolutions . Finalizar la iteración externa.

Tenemos para cada p en ps una lista de clusters pclusters en possibleSolutions . Cada pclusters es ponderado. Si avgPC es el número promedio de puntos por grupo en possibleSolutions (globales) y avgCSize es el número promedio de grupos por pclusters (globales), entonces esta es la función que usa estas dos variables para determinar el peso:

private static WeightedPClusters weigh(List<Cluster> pclusters, double avgPC, double avgCSize) { double weight = 0; for (Cluster cluster : pclusters) { int ps = cluster.getPoints().size(); double psAvgPC = ps - avgPC; weight += psAvgPC * psAvgPC / avgCSize; weight += cluster.getSurface() / ps; } return new WeightedPClusters(pclusters, weight); }

La mejor solución es ahora los pclusters con el menor peso. Repetimos la iteración principal siempre que podamos encontrar una mejor solución (menos peso) que la mejor anterior con limitA=max(minA,(int)avgPC) . Terminar la iteración principal.

Tenga en cuenta que para los mismos datos de entrada, este algoritmo siempre producirá los mismos resultados. Las listas se usan para conservar el orden y no hay ningún factor aleatorio involucrado.

Para ver cómo se comporta este algoritmo, esta es una imagen del resultado en un patrón de prueba de 32 puntos. Si maxA=minA=16 , entonces encontramos 2 clusters de 16 direcciones.

A continuación, si disminuimos el número mínimo de direcciones por conjunto configurando minA=12 , encontramos 3 grupos de 12/12/8 puntos.

Y para demostrar que el algoritmo está lejos de ser perfecto, aquí está la salida con maxA=7 , pero obtenemos 6 clusters, algunos de ellos pequeños. Entonces, todavía tiene que adivinar demasiado al determinar los parámetros. Tenga en cuenta que r aquí es solo 5.

Solo por curiosidad, probé el algoritmo en un conjunto más grande de puntos elegidos al azar. Agregué las imágenes a continuación.

¿Conclusión? Esto me llevó medio día, es ineficiente, el código parece feo y es relativamente lento. Pero muestra que es posible producir algún resultado en un corto período de tiempo. Por supuesto, esto fue solo por diversión; Convertir esto en algo realmente útil es la parte difícil.