Wybieranie najbardziej rozproszonych punktów z zestawu punktów

15

Czy istnieje (skuteczny) algorytm do wybierania podzbioru punktów z zestawu punktów ( ) tak, aby „obejmowały” większość obszaru (we wszystkich możliwych podzbiorach rozmiaru )?M.N.M.<N.M.

Zakładam, że punkty są w płaszczyźnie 2D.

Naiwny algorytm jest prosty, ale zbyt skomplikowany pod względem złożoności czasowej:

for each subset of N points
    sum distance between each pair of points in the subset
    remember subset with the maximum sum

Szukam bardziej wydajnej lub nawet przybliżonej metody.

Przykład, oto płaszczyzna z kilkoma losowymi punktami:

wprowadź opis zdjęcia tutaj

Dla oczekuję wybrania takich punktów:M.=5

wprowadź opis zdjęcia tutaj

Zwróć uwagę, że wybrane punkty (czerwone) są rozrzucone po całej płaszczyźnie.

Znalazłem artykuł „ EFEKTYWNIE WYBIERAJĄCY KLUCZOWE PUNKTY DYSTRYBUCJI PRZESTRZENNEJ ”, który jest związany z tym problemem. Zakłada się jednak, że punkty są ważone.

Libor
źródło
2
W przypadku zobacz to z StackOverflow: Algorytm znajdujący punkty, które są najdalej od siebie - lepsze niż O (n ^ 2)? . M=2
hardmath
Niestety, wynosi zwykle około 1500-5000, a około 10-50. N.M.
Libor
Czy oba i są stałe, czy też zmieniasz (np. Ponieważ chcesz zmaksymalizować średnią odległości, w którym to przypadku zwiększenie może spowodować zmniejszenie)? M.N.M.M.
Wolfgang Bangerth
1
Podejrzewam, że to trudne NP. Przypomina to problem kliki o maksymalnej masie, gdzie ciężar krawędzi między dwoma wierzchołkami jest odległością euklidesową między nimi. (Wierzę, że istnieją praktycznie skuteczne heurystyki znane z max-clique. Nie jestem pewien, które to są.)
tmyklebu
1
@hardmath Przepraszamy, to była literówka. Próbowałem zilustrować, co muszę osiągnąć. Problem pochodzi z ekstrakcji cech obrazu, w której muszę uzyskać tylko garść cech punktowych, ale rozproszenie ich po całym obrazie, ponieważ są one używane do oszacowania transformacji, a gdy są rozproszone przestrzennie, oszacowanie jest bardziej stabilne. Może lepszym rozwiązaniem jest „entropia” - chciałbym wybrać punktów tak, aby były wszędzie, jak gaz w stanie maksymalnej entropii. Z drugiej strony staram się unikać grupowania wybranych punktów. M.
Libor

Odpowiedzi:

11

Oto przybliżone rozwiązanie. Ponieważ N jest tak duży, a M jest tak mały, co powiesz na:

  1. Oblicz wypukły kadłub N
  2. Wybierz maksymalnie M punktów z kadłuba, które spełniają kryteria maksymalnej odległości.
  3. Jeśli krok 2 pozostawia mniej niż M punktów, wybierz 1 punkt z wnętrza, który maksymalizuje odległość od wcześniej wybranych punktów.
  4. Powtarzaj krok 3, aż liczba wybranych punktów wyniesie M.

Intuicja za tym stoi, ponieważ skoro N >> M i chcesz punktów jak najdalej od siebie, prawdopodobnie będą one blisko krawędzi danych, więc równie dobrze możesz zacząć od kadłuba, a następnie iteracyjnie stamtąd wejdź do środka.

Ponadto, zaczynając od kadłuba, zmniejszasz początkowe wyszukiwanie z N do N 1/2 .


AKTUALIZACJA

Jeśli kroki 3 i 4 powyżej trwają zbyt długo (ponieważ testujesz iteracyjnie wnętrze zestawu danych), przyszło mi do głowy jeszcze dwa pomysły, aby przyspieszyć twój problem.

  1. Wyszukiwanie losowe : Powiedzmy, że w kroku 2 znalazłeś punkty P na kadłubie. Następnie losowo narysuj punkty M - P z wnętrza. Wybierz najlepszy zestaw po X próbach.
  2. Symulowane wyżarzanie : oblicz najmniejszą ramkę ograniczającą, która pokrywa twój zestaw danych (nie musi być wyrównany z osiami, może być przechylany). Następnie zdefiniuj zestaw M równomiernie rozmieszczonych punktów siatki na tej obwiedni. Uwaga: punkty te niekoniecznie pokrywają się z żadnym z punktów zestawu danych. Następnie dla każdego punktu siatki znaleźć k -nearest sąsiadów w swoim zbiorze. Uruchom każdą kombinację M x k i wybierz tę, która spełnia kryteria maksymalnego dystansu. Innymi słowy, używasz początkowej siatki jako paska startowego, aby znaleźć dobre początkowe rozwiązanie.
dpmcmlxxvi
źródło
Dzięki. Może źle sformułował pytanie. Dążę do takiego zbioru punktów, aby „obejmowały” większość obszaru. Myślałem, że wystarczy kryterium odległości, ale wygląda na to, że trzeba coś jeszcze dodać.
Libor
M.
1
Być może bardziej formalnym sposobem stwierdzenia problemu jest to, że chcesz teselacji rozmiaru M, która obejmuje N i minimalizuje średni obszar aspektu teselacji? Minimalizacja obszarów aspektów wydaje się sposobem na rozłożenie punktów wokół i upewnienie się, że się nie zlepią.
dpmcmlxxvi
Tak. Chciałem uniknąć korzystania z siatki, ponieważ jeśli punkty mogą zostać przypadkowo zgrupowane wokół linii siatki, a następnie zostaną zgrupowane w zaznaczeniu.
Libor,
Jedyny problem z twoim chciwym algorytmem, o którym wspomniałeś, to to, że będzie on bardzo wrażliwy na początkowy punkt początkowy. Algorytmy uprawy nasion (gdzie zaczynamy od wewnątrz) mają ten problem. Podejście do kadłuba, o którym wspominam, będzie prawdopodobnie bardziej stabilne, ponieważ działa od zewnątrz.
dpmcmlxxvi
6

N.M.

M.M.

M.1M.=3),4,5

M.=3)1M.=4M.=51

Jeśli chcemy uniknąć przeważającego wyboru punktów na peryferiach, przydatny może okazać się inny cel. Takim kryterium jest maksymalizacja minimalnej odległości między punktami. Powiązane problemy zostały poruszone w StackOverflow , Computer Science SE , Math.SE i MathOverflow .

M.reM.re

matematyka
źródło
1

OK, więc chcesz wybrać M punktów z danego zestawu N punktów na płaszczyźnie euklidesowej, aby suma odległości par wybranych punktów była maksymalna, prawda?

Standardowy algorytm wyszukiwania lokalnego jest dość szybki i zapewnia całkiem dobre przybliżenie. Czas działania jest liniowy w N i kwadratowy w M. Jego współczynnik aproksymacji wynosi 1 - 4 / M. Oznacza to, że stosunek ten rośnie wraz ze wzrostem M. Na przykład dla M = 10 dostaje 60% wartości optymalnej, a dla M = 50 dostaje 92% wartości optymalnej.

Algorytm działa również dla przestrzeni euklidesowych o wymiarze ogólnym. W tym przypadku problem jest trudny NP. Ale w samolocie nie wiadomo, czy jest NP-twardy.

Źródłem jest ten artykuł . Mam nadzieję że to pomoże! Pozdrawiam, Alfonso


Alfonso
źródło
1
Rozwiązałem to już za pomocą algorytmu „Suppression via Disk Covering” z artykułu „Efektywne wybieranie rozproszonych przestrzennie punktów kluczowych do śledzenia wizualnego” 18. 18. Międzynarodowa Konferencja IEEE na temat przetwarzania obrazu. IEEE, 2011
Libor
1
Alfonso, proszę wyraźnie podać swoją przynależność do sugerowanego artykułu.
nicoguaro
0

Jednym z rozwiązań jest:

  • O(n)

  • Spraw, aby M sztucznie rozłożył nawet punkty wewnątrz tego ograniczającego prostokąta, niektóre M są trudniejsze niż inne. W twoim przypadku cztery w rogach prostokąta i jeden w środku

  • O(n(losol(n)))

  • O(m(losol(n)))

O(n(losol(n)))M.N.

Jan Hackenberg
źródło