Autor Wątek: Grupowanie obiektow w przestrzeni 2D  (Przeczytany 807 razy)

Offline johnson84

  • Użytkownik

# Sierpień 13, 2010, 17:59:18
Witam,

Potrzebuje szybkiego algorytmu grupowanie obiektow. Problem jest nastepujacy: W ukladzie 2D danych jest n punktow. Dany jest promien r (maksymalna odleglosc miedzy kazda para punktow w grupie). Nalezy utworzyc mozliwie najmniejsza liczbe grup zawirajacych co najmniej jeden punkt kazda. Czy macie jakies pomysly ? Prosze zwrocic mi uwage jezeli nie sprecyzowalem wystarczajaca.

Dziekuje.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Liosan

  • Redaktor

# Sierpień 13, 2010, 18:22:08
Hasło do google'a - cluster analysis. Algorytmów jest sporo, ja kojarzę k-means i hierarchical clustering; oba są heurystyczne i obie nie rozwiązują dokładnie Twojego problemu, ale jeśli nie poszukujesz optymalnego rozwiązania, to mogą się nadać. Do optymalnego... ja nic nie kojarzę.

Liosan

Offline RedHot

  • Użytkownik

# Sierpień 13, 2010, 20:26:25
Spróbuj fcm (fuzzy c-means). k-means jest zwykły a tak to tutaj masz rozmyty  8)

Offline maciek_slon

  • Użytkownik

# Sierpień 22, 2010, 04:00:52
Może jeszcze DB-Scan? Zaleta - ilość grup jest określana automagicznie, nie trzeba jej definiować na początku algorytmu jak w k-means na przykład, dodatkowo można dodać odporność na szum, jego parametrem jest promień który podałeś.