Filtrer les points proches d'une liste

Question

Je à moitié répondu à une question sur la recherche de grappes de masse dans un bitmap . Je dis demi-réponse parce que je l'ai laissée dans une condition où tous les points du bitmap étaient triés en masse et laissée au lecteur pour filtrer la liste en supprimant les points du même cluster.

Puis, en réfléchissant à cette étape, j’ai trouvé que la solution ne m’était pas apparue comme je le pensais. Alors maintenant, je vous demande de l'aide. Nous avons une liste de points avec des masses comme celle-ci (une liste de n-uplets en Python, mais vous pouvez la représenter à votre guise dans n'importe quelle langue):

[ (6, 2, 6.1580555555555554),
  (2, 1, 5.4861111111111107),
  (1, 1, 4.6736111111111107),
  (1, 4, 4.5938888888888885),
  (2, 0, 4.54),
  (1, 5, 4.4480555555555554),
  (4, 7, 4.4480555555555554),
  (5, 7, 4.4059637188208614),
  (4, 8, 4.3659637188208613),
  (1, 0, 4.3611111111111107),
  (5, 8, 4.3342191043083904),
  (5, 2, 4.119574829931973),
  ...
  (8, 8, 0.27611111111111108),
  (0, 8, 0.24138888888888888) ]

Chaque tuple est de la forme:

(x, y, mass)

Notez que la liste est triée ici. Si votre solution préfère ne pas les avoir triés, tout va bien.

Le défi, si vous vous souvenez , consiste à trouver les principaux groupes de masse. Le nombre de clusters n'est pas connu. Mais vous connaissez les dimensions du bitmap. Parfois, plusieurs points dans un cluster ont plus de masse que le centre du prochain cluster (en taille). Ce que je veux faire, c’est donc partir des points de masse supérieure et supprimer des points du même groupe (points proches).

Lorsque j’ai essayé, j’ai dû parcourir plusieurs parties de la liste. J'ai l'impression que je suis juste stupide à ce sujet. Comment le ferais-tu? Pseudo code ou code réel. Bien sûr, si vous pouvez simplement enlever ce que j'ai laissé dans cette réponse avec du code Python, il est plus facile pour moi de l'expérimenter.

La prochaine étape consiste à déterminer le nombre de clusters présents dans le bitmap. J'ai encore du mal à définir ce problème, alors je pourrais revenir avec une question à ce sujet.

MODIFIER: je devrais préciser que je sais qu'il n'y a pas de "correct". répondre à cette question. Et le nom de la question est la clé. La première phase de mon regroupement est terminée. Je suis à la recherche d'une solution rapide, précise et "suffisante". méthode de filtrage des points voisins.

Faites-moi savoir si vous voyez comment je peux clarifier la question.

Answer 1

Pour votre information, vous demandez une solution à un mal placé problème: aucune solution définitive n'existe. C'est bien ... ça rend les choses plus amusantes. Votre problème est mal posé principalement parce que vous ne savez pas combien de grappes vous voulez. Le clustering est l’un des domaines clés de l’apprentissage automatique et de nombreuses approches ont été développées au fil des ans.

Comme Arachnid l'a fait remarquer, l'algorithme k-means tend à être bon et c'est assez facile à mettre en œuvre. Les résultats dépendent essentiellement de l'estimation initiale et du nombre de clusters souhaités. Pour résoudre le problème de la conjecture initiale, il est courant d'exécuter l'algorithme plusieurs fois avec des initialisations aléatoires et de sélectionner le meilleur résultat. Vous devrez définir le "meilleur" programme. veux dire. Une mesure serait la distance moyenne au carré de chaque point à son centre de cluster. Si vous voulez deviner automatiquement le nombre de clusters, vous devez exécuter l'algorithme avec toute une gamme de nombres de clusters. Pour tout bon "meilleur" mesure, plus de grappes auront toujours l’air meilleur que moins, vous aurez donc besoin d’un moyen de pénaliser le fait qu’il y ait trop de grappes. La discussion sur MDL sur wikipedia est un bon point de départ.

La classification K-means est le modèle de mélange le plus simple . Parfois, il est utile de passer à un mélange de Gaussiens appris par maximisation des attentes (décrit dans le lien donné ci-dessus). Cela peut être plus robuste que k-means. Il faut un peu plus d’efforts pour le comprendre, mais lorsque vous le faites, ce n’est pas beaucoup plus difficile à mettre en œuvre que k-means.

Il existe de nombreuses autres techniques de clustering , telles que le clustering agglomératif et le clustering spectral. La mise en cluster agglomérée est assez facile à mettre en œuvre, mais il peut être difficile de choisir à quel moment arrêter de construire les clusters. Si vous effectuez une classification par agglomération, vous voudrez probablement consulter kd trees pour accélérer recherches du voisin le plus proche. La réponse de smacl décrit une manière légèrement différente de regrouper par agglomération à l'aide d'un diagramme de Voronoï.

Certains modèles peuvent choisir automatiquement le nombre de clusters, comme ceux basés sur Allocation de Dirichlet latent , mais ils sont beaucoup plus difficiles à comprendre correctement un outil.

Vous pouvez également consulter le algorithme de décalage moyen pour voir s'il est plus proche de ce que vous voulez vraiment.

Answer 2

Il me semble que vous recherchez l'algorithme K-means .

Answer 3

Comme je l'ai mentionné dans le commentaire de votre question, la réponse est basée sur le fait que la masse peut ou non être considérée comme scalaire dans ce contexte. Si tel est le cas, les solutions basées sur les couleurs ne fonctionneront probablement pas car les couleurs ne sont souvent pas considérées comme étant scalaires.

Par exemple, si j’ai une surface donnée avec 1 point de masse élevée, est-ce que cela revient à avoir la même surface avec 10 points de 1/10 de la masse? Si cela est vrai, la masse n'est pas scalaire dans ce contexte, et j'aurais tendance à regarder un algorithme utilisé pour le groupage spatial de valeurs non scalables similaires, par ex. diagrammes de Voronoi .

Dans ce cas, où deux zones de voronoï adjacentes ont une correspondance de masse et une distance suffisamment proches, elles peuvent être regroupées. Vous pouvez répéter cette opération pour rechercher tous les clusters.

Si, en revanche, votre masse est évolutive ou si la masse à une position inconnue peut être interpolée à partir de points environnants, j'aurais tendance à triangulez , contournez les données en entrée et utilisez les zones entre les contours pour trouver des grappes de masse similaire.

Answer 4

Cela ressemble à une quantification des couleurs, dans laquelle vous réduisez le nombre de couleurs dans une image. Une solution consisterait à tracer les couleurs dans l’espace et à combiner des groupes au centre (ou à une moyenne pondérée) d’un groupe.

Le nom exact de l'algorithme qui a déclenché cette mémoire m'échoue, mais je vais modifier la réponse si elle apparaît, mais entre-temps, vous devriez examiner la quantification des couleurs et voir si certains algorithmes sont utiles.

Answer 5

Commencez par le Convex Hull " problème. Vous recherchez également des groupes de type "coque convexe".

Notez que & cl; clusters " est vague. Vous avez une masse moyenne dans votre champ. Certains points ont une masse supérieure à la moyenne et d'autres, inférieurs à la moyenne. À quel point au-dessus de la moyenne signifie que vous avez trouvé un cluster? À quelle distance les nœuds doivent-ils être pour faire partie d'un cluster ou d'un cluster séparé?

Quelle est la différence entre deux sommets et une crête?

Vous devez calculer une "topographie". - relier tous les points avec une densité égale dans les régions. Cela nécessite que vous choisissiez un point et que vous travailliez de manière radiale à partir d'un point, en localisant des positions où les densités sont égales. Vous pouvez connecter ces points à des régions.

Si vous avez judicieusement choisi votre point initial, les régions doivent s'emboîter. Choisir votre point de départ est facile car vous commencez aux sommets locaux.

Answer 6

Puisque vous parlez déjà de masse, pourquoi pas une solution basée sur la gravité. Un système de particules simple n'aurait pas besoin d'être très précis et vous ne l'auriez pas fait fonctionner trop longtemps avant de pouvoir mieux deviner le nombre de clusters.

Si vous avez une meilleure idée des numéros de grappe, k-signifie que le plus proche voisin devient réalisable.