Comment grouper des objets dans un ensemble par proximité?

Question

J'ai un ensemble contenant des milliers d'adresses. Si je peux obtenir la longitude et la latitude de chaque adresse, comment puis-je diviser l’ensemble en groupes par proximité?

De plus, je souhaiterai peut-être réessayer le 'clustering' selon différentes règles:

• N groupes
• M adresses par groupe
• distance maximale entre toute adresse d'un groupe

Answer 1

Vous pouvez essayer l'algorithme k-means .

Answer 2

Vous voulez une quantification vectorielle:

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

& "; Cela fonctionne en divisant un grand ensemble de points (vecteurs) en groupes ayant approximativement le même nombre de points les plus proches. Chaque groupe est représenté par son centre de centroïde, comme dans k-means et certains autres algorithmes de classification. & Quot;

Ici les vecteurs sont les coordonnées géographiques de chaque adresse, et vous pouvez alimenter vos algorithmes avec d’autres paramètres en fonction de vos contraintes (proximité, taille du groupe, nombre de groupes ...).

Vous pouvez commencer avec k-means, mais d'après mon expérience, un algorithme basé sur Voronoï est plus flexible. Une bonne introduction ici .

Answer 3

Cela dépend un peu de l’échelle des données que vous souhaitez regrouper. L’approche par force brute consiste à calculer la distance entre toutes les combinaisons de points dans un tableau de distance. Le tableau résultant est N ^ 2 et, puisque la distance de A à B est identique à celle de B à A, vous n’avez besoin que de la moitié de celle-ci; le résultat est donc N ^ 2/2.

Pour des coordonnées lat lon relativement proches, vous pouvez parfois vous en sortir en utilisant la grille comme une grille x, y et en calculant la distance cartésienne. Puisque le monde réel n’est pas plat, la distance cartésienne sera entachée d’erreur. Pour un calcul plus exact que vous devriez utiliser si vos adresses sont situées dans tout le pays, voir ce lien de Mathforum.com .

Si vous ne possédez pas l’échelle pour gérer l’ensemble de la matrice de distance, vous devrez programmer des algorithmes pour améliorer l’efficacité.

Answer 4

Les " N groupes " et " M adresses par groupe " les contraintes s'excluent mutuellement. L'un implique l'autre.

Answer 5

1. Créez une matrice de distances entre toutes les adresses.
2. En commençant par une adresse aléatoire, triez la matrice en fonction de la distance qui la sépare
3. Supprimez les adresses de la matrice au fur et à mesure, placez les adresses les plus proches de l'adresse de départ dans un nouveau groupe jusqu'à atteindre vos critères (taille du groupe ou distance maximale).
4. Une fois qu'un groupe est plein, choisissez une autre adresse aléatoire et utilisez la matrice en fonction de la distance jusqu'à cette adresse
5. Continuez ainsi jusqu'à ce que toutes les adresses soient retirées de la matrice.

Si les adresses étaient distribuées équitablement, chaque groupe aurait une sorte de forme circulaire autour de l'adresse de départ. Le problème survient lorsque les adresses de démarrage se trouvent à proximité de groupes existants. Lorsque cela se produit, le nouveau groupe s'enroule autour de l'ancien et peut même l'entourer complètement si votre critère d'arrêt est uniquement la taille du groupe. Si vous utilisez la contrainte de distance maximale, cela ne se produira pas (en supposant qu'aucune autre contrainte ne soit présente).

Je ne sais pas vraiment si c'est un bon moyen de le faire mais c'est ce que j'essaierais. Je suis sûr que beaucoup d'optimisation serait nécessaire. Surtout pour les adresses sur les bords.