Trouver un nombre connu de centres de cercle qui maximisent le nombre de points à une distance fixe

J'ai un ensemble de données 2D où je veux trouver les centres d'un nombre spécifié de centres de cercles ( ) qui maximisent le nombre total de points dans une distance spécifiée ( ).$N$$R$

Par exemple, j'ai 10 000 points de données et je veux trouver les centres de cercles qui capturent autant de points que possible dans un rayon de . Les 5 centres et le rayon de 10 sont donnés à l'avance, non dérivés des données.$(X_i, Y_i)$$N=5$$R=10$

La présence d'un point de données dans un cercle est une proposition binaire soit / ou. Si , il n'y a pas de différence de valeur avec un point à 11 unités de distance contre 100 unités de distance, car ils sont tous les deux> 10. De même pour être dans le cercle, il n'y a pas de valeur supplémentaire à être près du centre vs près du bord . Un point de données se trouve dans l'un des cercles ou à l'extérieur.$R=10$

Existe-t-il un bon algorithme qui peut être utilisé pour résoudre ce problème? Celles-ci semblent liées aux techniques de regroupement, mais plutôt que de minimiser la distance moyenne, la fonction "distance" est 0 si le point est à l'intérieur de de l'un des points, et 1 sinon.$R$$N$

Ma préférence serait de trouver un moyen de le faire en R, mais toute approche serait appréciée.

Il s'agit d'un problème de variation k-means. Le rayon des centres n'a pas d'importance, tant qu'ils sont supposés égaux.

Liens:

• http://en.wikipedia.org/wiki/K-means_clustering
• http://stat.ethz.ch/R-manual/R-devel/library/stats/html/kmeans.html

Il placera les centres des cercles aux endroits où la probabilité des points est la plus élevée.

Procédure classique K-means:

1. définir le nombre de clusters sur 5
2. mettre chaque point dans un cluster aléatoire
3. pour chaque grappe, calculer la position moyenne
4. pour chaque point, calculez la distance jusqu'à chaque nouvelle position moyenne
5. associer l'adhésion au cluster le plus proche
6. répéter jusqu'à la fin (itérations, changement de position ou autre mesure d'erreur)

Options:

• Vous pouvez utiliser une sous-relaxation après 3, où vous traduisez lentement la position moyenne vers la nouvelle position.
• c'est un système discret donc il ne converge pas parfaitement. Parfois, c'est le cas et vous pouvez terminer lorsque les points cessent de changer d'appartenance, mais parfois ils bougent un peu.
• Si vous créez votre propre code (comme la plupart des gens devraient le faire), vous pouvez utiliser le POR k-means ci-dessus comme point de départ et faire quelques variations sur EM informées par un pourcentage de points exclusivement et complètement englobées par les cercles.

Pourquoi K-means attaque le problème:

• C'est l'équivalent de l'ajustement d'un modèle de mélange gaussien où les covariances des composants sont égales. Les centres des composants du mélange vont être situés aux positions de plus haute espérance de points. Les courbes de probabilité constante vont être des cercles. Il s'agit d'un algorithme EM qui a donc la convergence asymptotique. Les adhésions sont dures, pas molles.
• Je pense que si l'hypothèse fondamentale du modèle de mélange de composants à variance égale est raisonnablement "proche", quoi que cela signifie, alors cette méthode va s'adapter. Si vous distribuez simplement des points au hasard, il est moins probable qu'ils correspondent bien.

Il devrait y avoir un analogue d'un «Poisson gonflé zéro» où il y a une composante non gaussienne qui capte la distribution uniforme.

Si vous vouliez "ajuster" votre modèle et que vous étiez convaincu qu'il y avait suffisamment de points d'échantillonnage, vous pouviez initialiser avec les k-moyennes, puis faire un ajusteur augmenté des k-moyennes qui supprimait les points en dehors des rayons des cercles de la compétition. Cela perturberait légèrement les cercles que vous avez, mais cela pourrait avoir des performances légèrement améliorées compte tenu des données.

Quelqu'un a probablement un meilleur algorithme formel, mais voici une approche par force brute (un hack?). J'utiliserais l'un des algorithmes de binning hexagonaux pour calculer un histogramme 2D. Comme hexbindans R.

J'utiliserais une taille hexagonale qui circonscrirait grossièrement votre cercle de rayon R, puis trier sur les N bacs supérieurs. Si vous avez Ndes bacs éloignés distincts, tant mieux. Maintenant, une façon consiste à se déplacer sur le cercle localement sur une échelle 2 * R (dans les directions x et y) à partir du centre des hexagones de densité supérieure. Les densités de calcul peuvent à peu près optimiser la position localement. Cela expliquera le fait que les hexagones n'étaient pas une fenêtre mobile par rapport à une origine fixe.

Si tous les bacs supérieurs sont à proximité, vous devriez avoir une façon plus intelligente de déplacer vos cercles dans ce voisinage.

Notez que je peux penser à plusieurs cas de coin où une telle stratégie naïve échouera de manière spectaculaire. Pourtant, juste un point de départ.

En attendant, j'espère que quelqu'un a un meilleur algorithme.