Znalezienie znanej liczby środków okręgu, które maksymalizują liczbę punktów w ustalonej odległości

Mam zestaw danych 2D, w których chcę znaleźć środki o określonej liczbie środków kół ( ), które maksymalizują całkowitą liczbę punktów w określonej odległości ( ).$N$$R$

np. mam 10 000 punktów danych $(X_i, Y_i)$ i chcę znaleźć środki $N=5$ okręgów, które przechwytują jak najwięcej punktów w promieniu $R=10$ . 5 centrów i promień 10 są podane wcześniej, a nie pochodzą z danych.

Obecność punktu danych w okręgu jest albo wartością binarną albo / albo. Jeśli $R=10$ , nie ma różnicy wartości w stosunku do punktu oddalonego o 11 jednostek w porównaniu do 100 jednostek w oddaleniu, ponieważ oba są w odległości> 10. Podobnie w przypadku przebywania w kręgu, nie ma żadnej dodatkowej wartości będąc blisko środka vs. blisko krawędzi . Punkt danych znajduje się w jednym z okręgów lub na zewnątrz.

Czy istnieje dobry algorytm, którego można użyć do rozwiązania tego problemu? Wydaje się, że są one związane z technikami grupowania, ale zamiast minimalizować średni dystans, funkcja „odległości” wynosi 0, jeśli punkt znajduje się w obrębie $R$ dowolnego z $N$ punktów, a 1 w przeciwnym razie.

Wolę znaleźć sposób na zrobienie tego w R, ale każde podejście byłoby mile widziane.

Jest to wariacja problemu k-średnich. Promień centrów nie ma znaczenia, o ile zakłada się, że są one równe.

Spinki do mankietów:

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

Umieści środki okręgów w miejscach o najwyższym prawdopodobieństwie punktów.

Klasyczne K-oznacza Procedura:

1. ustaw liczbę klastrów na 5
2. umieść każdy punkt w losowej grupie
3. dla każdego klastra oblicz średnią pozycję
4. dla każdego punktu obliczyć odległość do każdej nowej średniej pozycji
5. powiązać członkostwo z najbliższym klastrem
6. powtarzaj aż do zakończenia (iteracje, zmiana pozycji lub inne dane błędu)

Opcje:

• Po 3 możesz użyć trochę rozluźnienia, w którym powoli przesuwasz średnią pozycję w kierunku nowej pozycji.
• jest to dyskretny system, więc nie łączy się idealnie. Czasami tak się dzieje i możesz skończyć, gdy punkty przestaną zmieniać członkostwo, ale czasami po prostu trochę się poruszają.
• Jeśli tworzysz swój własny kod (jak powinna większość ludzi), możesz użyć powyższych wartości POR k-średnich jako punktu początkowego i wprowadzić pewne zmiany w EM, oparte na procentach punktów wyłącznie i całkowicie objętych kręgami.

Dlaczego K-znaczy atakuje problem:

• Jest to odpowiednik dopasowania modelu mieszanki Gaussa, w którym kowariancje składników są równe. Ośrodki składników mieszanki będą znajdować się w miejscach o najwyższym oczekiwaniu punktów. Krzywe stałego prawdopodobieństwa będą kołami. Jest to algorytm EM, więc ma asymptotyczną zbieżność. Członkostwo jest trudne, a nie miękkie.
• Myślę, że jeśli fundamentalne założenie modelu mieszanki składników o równej wariancji jest dość „bliskie”, cokolwiek to znaczy, to metoda ta będzie pasować. Jeśli losowo rozdzielisz punkty, mniej prawdopodobne jest, aby pasowały dobrze.

Powinien istnieć jakiś analog „Zero Inflated Poissona”, w którym występuje element niegaussowski, który odbiera rozkład równomierny.

Jeśli chcesz „dostroić” swój model i masz pewność, że istnieje wystarczająca liczba punktów próbnych, możesz zainicjować za pomocą k-średnich, a następnie wykonać ulepszony regulator k-średnich, który usuwa punkty poza promieniami kręgów z konkurencji. Lekko zakłócałoby to twoje kręgi, ale może nieco poprawić wydajność, biorąc pod uwagę dane.

Ktoś prawdopodobnie ma lepszy algorytm formalny, ale oto jedno podejście brutalnej siły (hack?). Użyłbym jednego z sześciokątnych algorytmów binowania do obliczenia histogramu 2D. Podobnie jak hexbinw R.

Użyłbym sześciokąta, który z grubsza określiłby twój okrąg o promieniu R, a następnie posortowałbym według górnych N pojemników. Jeśli masz Nwyraźne odległe kosze, świetnie. Teraz jednym ze sposobów jest lokalne poruszanie się po okręgu w skali 2 * R (w kierunkach x i y) od środka sześciokątów o największej gęstości. Gęstości obliczeniowe mogą z grubsza optymalizować lokalnie pozycję. To wyjaśnia fakt, że sześciokąty nie były ruchomym oknem w odniesieniu do ustalonego początku.

Jeśli wszystkie górne kosze są blisko, musisz mieć lepszy sposób na przemieszczanie swoich kręgów w tej okolicy.

Zauważ, że mogę myśleć o kilku narożnych przypadkach, w których tak naiwna strategia spektakularnie się nie powiedzie. Ale to tylko punkt wyjścia.

Tymczasem mam nadzieję, że ktoś ma lepszy algorytm.