Comment regrouper les points de latitude / longitude qui sont "proches" les uns des autres?
j'ai une base de données des points de latitude/longitude soumis par l'utilisateur et j'essaie de grouper les points "proches" ensemble. 'Fermer' est relatif, mais pour l'instant, il semble ~500 pieds.
au début il me semblait que je pouvais simplement Grouper par lignes qui ont la même latitude / longitude pour les 3 premières décimales (environ une boîte de 300x300, en comprenant que cela change quand vous vous éloignez de l'Équateur).
cependant,cette méthode semble faire défaut. 'Proximité' ne peut pas être significativement différente de la distance que représente chaque décimale. Il ne tient pas compte du fait que deux endroits peuvent avoir des chiffres différents à la 3e (ou n'importe quelle) décimale, mais se trouver tout de même à l'intérieur de la distance que cet endroit représente (33.1239 et 33.1240).
j'ai également réfléchi à la situation où le point A et le Point C sont tous deux "proches" du Point B (mais pas l'un de l'autre) - devraient-ils être regroupés? Dans l'affirmative, que se passe - t-il lorsque le point D est "proche" du point C (et aucun autre point)? - il être regroupés. J'ai certainement afin de déterminer le comportement désiré, mais comment pourrait être mis en œuvre?
est-ce que quelqu'un peut m'indiquer la bonne direction quant à la façon de procéder et aux différentes méthodes/approches qui peuvent être utilisées?
j'ai l'impression de rater quelque chose d'évident.
actuellement les données sont une base de données MySQL, utilisée par une application PHP; cependant, je suis ouvert à d'autres méthodes de stockage si elles sont une partie clé dans l'accomplissement de cette. ici.
5 réponses
il y a plusieurs façons de déterminer la distance entre deux points, mais pour tracer des points sur un graphique 2-D vous voulez probablement le distance euclidienne. Si (x1, y1) représente votre premier point et (x2, y2) représente votre seconde, la distance est
d = sqrt( (x2-x1)^2 + (y2-y1)^2 )
en ce qui concerne le regroupement, vous pourriez vouloir utiliser une sorte de moyen 2-D pour déterminer comment les choses sont "proches" les unes des autres. Par exemple, si vous avez trois points, (x1, y1), (x2, y2),(x3, y3), vous pouvez trouver le centre de ces trois points par moyenne simple:
x(mean) = (x1+x2+x3)/3
y(mean) = (y1+y2+y3)/3
vous pouvez alors voir à quel point chacun est proche du Centre pour déterminer s'il doit faire partie du "cluster".
il y a plusieurs façons de définir les clusters, qui utilisent toutes une variante de algorithme de regroupement. Je suis pressé et je n'ai pas le temps de résumer, mais vérifiez le lien et les algorithmes, et j'espère que d'autres personnes seront en mesure de fournir plus en détail. Bonne chance!
Utilisez quelque chose de semblable à la méthode que vous avez décrite dans votre question pour obtenir un ensemble approximatif de résultats, puis blanchissez cette approximation fixé en faisant des calculs appropriés. Si vous choisissez correctement la taille de votre grille (c.-à-d. combien vous arrondissez vos coordonnées), vous pouvez au moins espérer réduire la quantité de travail à faire à un niveau acceptable, bien que vous devez gérer ce que la taille de la grille est.
Par exemple, earthdistance extension à PostgreSQL fonctionne en convertissant lat/longues paires en (x,y,z) coordonnées cartésiennes, modélisant la terre comme une sphère uniforme. PostgreSQL a un système d'indexation sophistiqué qui permet à ces coordonnées, ou à des boîtes autour d'elles, d'être indexées en arbres R, mais vous pouvez frapper quelque chose ensemble qui est encore utile sans cela.
Si vous prenez votre (x,y,z) triple et d'arrondir à - dire multiplier par un facteur et de tronquer entier - vous avez alors trois entiers que vous pouvez concaténer pour produire un "nom de la case", qui identifie une case dans votre" grille " où se trouve le point.
si vous voulez rechercher tous les points à moins de X km d'un point cible, vous générez tous les "noms de boîtes" autour de ce point (une fois que vous avez converti votre point cible en un (x,y,z) triple ainsi, c'est facile) et éliminez toutes les boîtes qui ne croisent pas la surface de la terre (plus difficile, mais l'utilisation de la x^2+y^2+z^2=R^2 formule à chaque coin vous dira) vous vous retrouvez avec une liste de boîtes points cibles peuvent être dans - donc il suffit de rechercher tous les points correspondant à l'une de ces cases, qui vous retournera également quelques points supplémentaires. Ainsi, comme étape finale, vous devez calculer la distance réelle à votre point cible et en éliminer certains (encore une fois, cela peut être accéléré en travaillant dans les coordonnées cartésiennes et en convertissant votre rayon de distance de grand-cercle cible en distance sécante).
le bricolage autour vient à s'assurer que vous n'avez pas à chercher trop de boîtes, mais en même temps ne pas apporter trop des points supplémentaires. J'ai trouvé utile d'indexer chaque point sur plusieurs grilles différentes (résolutions de 1Km, 5Km, 25Km, 125Km, etc.). Idéalement, vous voulez être à la recherche d'une seule boîte, rappelez-vous qu'il se développe à au moins 27 dès que votre rayon cible dépasse votre taille de grille.
j'ai utilisé cette technique pour construire un indice spatial à L'aide de Lucene plutôt que de faire des calculs dans une base de données SQL. Il fonctionne, bien qu'il y ait quelques bricolages pour le mettre en place, et les indices prennent un certain temps à générer et sont assez grandes. L'utilisation d'un arbre R pour tenir toutes les coordonnées est une approche beaucoup plus agréable, mais prendrait plus de codage personnalisé-cette technique nécessite essentiellement juste une recherche rapide de table de hachage (donc fonctionnerait probablement bien avec toutes les bases de données NoSQL qui sont la rage ces jours, et devrait être utilisable dans une base de données SQL aussi).
Peut-être exagéré, mais il me semble qu'un problème de clustering: distance mesure va déterminer comment la similarité de deux éléments est calculée. Si vous avez besoin d'une solution moins naïve essayer exploration de données: Outils et Techniques pratiques D'apprentissage automatique, et utiliser Weka ou Orange
si vous tenez compte de la latitude et de la longitude, plusieurs facteurs doivent être pris en compte dans les données en temps réel: les obstacles, comme les rivières et les lacs, et les installations, comme les ponts et les tunnels. Vous ne pouvez pas les grouper simplement; si vous utilisez l'algorithme simple comme k signifie que vous ne serez pas en mesure de les grouper. Je pense que vous devriez choisir les méthodes de regroupement spatial comme méthode de partitionnement CLARANS.
si je m'y attaquais, je commencerais par une grille. Mettre chaque point dans un carré sur la grille. Cherchez les réseaux à forte densité de population. Si les grilles adjacentes ne sont pas peuplées, alors vous avez un groupe décent.
si vous avez des grilles adjacentes densément peuplées, vous pouvez toujours laisser tomber un cercle au centre de chaque grille et optimiser pour la zone du cercle vs (nombre de points dans le cercle * un certain poids réglable). Pas parfait, mais facile. De meilleurs regroupements sont une optimisation beaucoup plus compliquée problème.