Algorithme de clustering pour les garçons de papier

Question

J'ai besoin d'aide pour sélectionner ou créer un algorithme de clustering en fonction de certains critères.

Imaginez que vous gérez des livreurs de journaux.

• Vous disposez d'un ensemble d'adresses de rue, chacune d'entre elles étant géocodée.
• Vous souhaitez regrouper les adresses afin que chaque groupe soit affecté à un livreur.
• Le nombre de livreurs, ou clusters, n'est pas fixe. Si nécessaire, je peux toujours embaucher d'autres livreurs ou les licencier.
• Chaque cluster devrait avoir à peu près le même nombre d'adresses. Cependant, un cluster peut avoir moins d'adresses si les adresses d'un cluster sont plus dispersées. (Formulé autrement : nombre minimal de clusters où chaque cluster contient un nombre maximal d'adresses, et toute adresse au sein d'un cluster doit être séparée par une distance maximale).
• Pour les points bonus, lorsque l'ensemble de données est modifié (ajout ou suppression d'une adresse) et que l'algorithme est relancé, il serait bon que les groupes restent aussi inchangés que possible (c'est-à-dire que cela exclut le simple regroupement de type k-means qui est aléatoire par nature). Sinon, les livreurs vont devenir fous.

Alors... des idées ?

UPDATE

Le graphique du réseau de rues, tel que décrit dans la réponse d'Arachnide, n'est pas disponible.

Answer 1

J'ai écrit un algorithme simple mais inefficace en Java pour voir dans quelle mesure je pouvais faire un regroupement de base sur un ensemble de points, plus ou moins comme décrit dans la question.

L'algorithme fonctionne sur une liste de coordonnées (x,y). ps qui sont spécifiés comme int s. Il prend également trois autres paramètres :

1. rayon ( r ) : étant donné un point, quel est le rayon pour rechercher les points voisins ?
2. adresses maximales ( maxA ) : quel est le nombre maximum d'adresses (points) par cluster ?
3. adresses mini ( minA ) : adresses minimales par cluster

Définir limitA=maxA . Itération principale : Initialiser la liste vide possibleSolutions . Itération externe : pour chaque point p sur ps . Initialiser la liste vide pclusters . Une liste de points à traiter wps=copy(ps) est défini. Point de travail wp=p . Itération interne : tandis que wps n'est pas vide. Retirez le point wp sur wps . Déterminez tous les points wpsInRadius sur wps qui sont à une distance < r de wp . Trier wpsInRadius de manière ascendante en fonction de la distance de wp . Gardez le premier min(limitA, sizeOf(wpsInRadius)) points dans wpsInRadius . Ces points forment un nouveau cluster (liste de points) pcluster . Ajouter pcluster à pclusters . Supprimer les points dans pcluster de wps . Si wps n'est pas vide, wp=wps[0] et continuer l'itération interne. Fin de l'itération interne. Une liste de clusters pclusters est obtenu. Ajoutez ceci à possibleSolutions . Fin de l'itération externe.

Nous avons pour chaque p sur ps une liste de clusters pclusters sur possibleSolutions . Chaque pclusters est alors pondéré. Si avgPC est le nombre moyen de points par cluster dans possibleSolutions (mondial) et avgCSize est le nombre moyen de clusters par pclusters (global), alors c'est la fonction qui utilise ces deux variables pour déterminer le poids :

  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 meilleure solution est maintenant la pclusters avec le plus petit poids. Nous répétons l'itération principale tant que nous pouvons trouver une meilleure solution (moins de poids) que la meilleure solution précédente avec limitA=max(minA,(int)avgPC) . Fin de l'itération principale.

Notez que pour les mêmes données d'entrée, cet algorithme produira toujours les mêmes résultats. Les listes sont utilisées pour préserver l'ordre et il y a pas de hasard impliqué.

Pour voir comment cet algorithme se comporte, voici une image du résultat sur une mire de 32 points. Si maxA=minA=16 alors nous trouvons 2 clusters de 16 adresses.

Ensuite, si nous diminuons le nombre minimum d'adresses par cluster en définissant minA=12 nous trouvons 3 groupes de 12/12/8 points.

Et pour démontrer que l'algorithme est loin d'être parfait, voici le résultat avec maxA=7 et pourtant nous avons 6 groupes, dont certains sont petits. Donc, vous devez encore trop deviner lorsque vous déterminez les paramètres. Notez que r ici, c'est seulement 5.

Par curiosité, j'ai essayé l'algorithme sur un ensemble plus important de points choisis au hasard. J'ai ajouté les images ci-dessous.

Conclusion ? Ce projet m'a pris une demi-journée, il est inefficace, le code est moche et il est relativement lent. Mais cela montre qu'il est possible de produire un peu de résultat dans un court laps de temps. Bien sûr, c'était juste pour s'amuser ; la partie la plus difficile est de transformer cela en quelque chose de réellement utile.

Answer 2

Ce que vous décrivez est un problème de routage (multi)-véhicules (VRP). Il existe de nombreuses publications académiques sur les différentes variantes de ce problème, utilisant une grande variété de techniques (heuristiques, solveurs standards, etc.). Habituellement, les auteurs essaient de trouver des solutions bonnes ou optimales pour une instance concrète, ce qui implique également un regroupement des sites (tous les sites sur la route d'un véhicule).

Cependant, les clusters peuvent être soumis à des changements majeurs avec des instances légèrement différentes, ce que vous voulez éviter. Néanmoins, quelque chose dans les VRP-Papers pourrait vous inspirer...

Si vous décidez de conserver l'étape de mise en grappes explicite, n'oubliez pas d'inclure votre distribution dans toutes les grappes, car elle fait partie de chaque route.

Pour évaluer les clusters, l'utilisation d'une représentation graphique de la grille des rues donnera probablement des résultats plus réalistes que de relier les points sur une carte blanche (bien que les deux soient des variantes de TSP). Si un modèle graphique n'est pas disponible, vous pouvez utiliser la métrique des taxis (|x_1 - x_2| + |y_1 - y_2|) comme approximation pour les distances.

Answer 3

Je pense que vous voulez un agglomération hiérarchique plutôt que la technique des k-means. Si votre algorithme est bien conçu, vous pouvez l'arrêter lorsque vous avez le bon nombre de clusters. Comme quelqu'un d'autre l'a mentionné, vous pouvez ensemencer les clusters suivants avec les solutions précédentes, ce qui peut vous donner une amélioration significative des performances.

Vous voudrez peut-être examiner de près la fonction de distance que vous utilisez, surtout si votre problème a une dimension élevée. La distance euclidienne est la plus facile à comprendre, mais elle n'est peut-être pas la meilleure. Examinez des alternatives telles que la distance de Mahalanobis.

Je présume que votre vrai problème n'a rien à voir avec la livraison de journaux...

Answer 4

Avez-vous pensé à utiliser une solution économique/de marché ? Divisez l'ensemble par une division arbitraire (mais constante pour éviter les effets du hasard) en sous-ensembles pairs (déterminés par le nombre de livreurs).

Attribuez une fonction de coût à chaque point en fonction de ce qu'il ajoute au graphique, et donnez à chaque point supplémentaire une valeur économique.

Faites des itérations en permettant à chaque personne à tour de rôle de mettre aux enchères son pire point, et donnez à chaque personne un budget maximum.

Cela correspond probablement assez bien à la façon dont les livreurs penseraient dans la vie réelle, car les gens trouveront des échanges, ou diront "ma vie serait tellement plus facile si je ne faisais pas ceci ou cela". Ce système est également assez souple (par exemple, il permettrait de donner une prime à un point situé à des kilomètres de tous les autres assez facilement).

Answer 5

Je l'aborderais différemment : En considérant le réseau de rues comme un graphe, avec une arête pour chaque côté de chaque rue, trouvez une partition du graphe en n segments, chacun ne dépassant pas une longueur donnée, de sorte que chaque livreur de journaux puisse parcourir un seul chemin continu du début à la fin de son itinéraire. De cette façon, vous évitez de donner aux gens des itinéraires qui les obligent à parcourir les mêmes segments à plusieurs reprises (par exemple, lorsqu'on leur demande de couvrir les deux côtés d'une rue sans couvrir toutes les rues environnantes).