Algorytm tworzenia klastrów na sferze jednostkowej

Witam,

Otóż mam ogólnie taki problem. Na kuli jednostkowej znajduje się bardzo wiele punktów. Oczywiście każdy z nich może być wyrażony poprzez podanie dwóch liczb (współrzędne kątowe w przestrzeni). Można też bardzo łatwo obliczyć "odległość" dwóch dowolnych punktów (czyli kąt między dwoma wektorami w przestrzeni). W moim przypadku mam bardzo wiele takich punktów (np. ok. 300 tyś.). Sprawa sprowadza się do tego aby jakoś spróbować ten zbiór zredukować tworząc klastry (w oparciu o jakieś kryterium związane z odległością). Zastanawiam się nad jakimś algorytmem, który by łatwo pozwolił na implementację (np. w Fortranie) i by jakoś znośnie działa w sensownym czasie. Przeglądanie literatury nie za bardzo mi pomogło niestety. Algorytmów jest bardzo dużo i mają wiele zastosowań, więc nie wiem, który byłby w miarę najlepszy w takim przypadku.

Z góry dziękuję za pomoc i odpowiedzi.

Pozdrawiam,

Radek

http://en.wikipedia.org/wiki/DBSCAN
to jest przykład prostego algorytmu klastrowania, który jest raczej trywialny w implementacji.
Kwestia "który najlepszy" wynika nie z algorytmu jako takiego a raczej z tego co chcesz uzyskać. Zauważ że taki k-means może być lepszy jeśli chcesz uzyskać konkretną liczbę klastrów, bo w przypadku DBSCANa nie masz na to wpływu.

Dzięki za przydatną odpowiedź. W moim przypadku nie potrzebuję wiedzieć ile mam mieć klastrów, to mam się tego dowiedzieć po procesowaniu. Jak czytałem to zastanawia mnie czas obliczeń. Niestety nie wiem ile by to mogło zająć mając te 300 czy 500 tyś. punktów.

Kolejna sprawa to sama implementacja. Sądzę, że dobrym pomysłem jest wpierw zrobienie macierzy połączeń (w oparciu o jakieś kryterium) i pracowanie na tym jak na jakimś grafie. Tworzenie macierzy odległości (tablica np. 300 tyś. na 300 tyś. elementów) mogłoby powodować chyba problemy z dostępną pamięcią. Może jakieś ew. sugestie też w tym względzie?

No macierz odległości raczej ci nie siądzie ;)
300k na 300k = 90 mld więc taka macierz miała by przynajmniej 90GB ;) trochę za dużo :)
Ale zauważ ze dla takiego DBSCANa nie potrzebujesz odległości między wszystkimi węzłami. Interesują cię tylko węzły które są w odległości epsilon od siebie. No i na dobrą sprawę liczysz każdą z tych odległości co najwyżej raz więc nie ma sensu tego tablicować. Poza tym wystarczy ci że dowolny węzeł klastra ma w zasięgu jakiś inny węzeł żeby go "dołączyć". Nie interesują cię więc odległości pomiędzy danym węzłem a całym klastrem, co ułatwia sprawę.
No i to jest dość szybki algorytm :)

Przyznam, że nie za bardzo załapałem algorytm prezentowany na stronie. Spróbowałem go zaimplementować, ale to co mam nie działa (oczywiście:)) tak jak trzeba. Napotkałem na pewne trudności przede wszystkim w implementacji kilku instrukcji (np. NeighborPts = NeighborPts joined with NeighborPts'). Jako, że mój kod musi być zasadniczo napisany w Fortranie to muszę się zastanowić dokładnie jak przeszukiwane są wszystkie punkty. Nie za bardzo załapałem też jak to jest możliwe, że co najwyżej raz liczę odległości pomiędzy punktami. Tym niemniej muszę to znacznie dokładniej przemyśleć. Aczkolwiek wszelkie bardziej szczegółowe komentarze są zawsze miło widziane:)

A bo ten pseudokod tam napisali jakoś bez sensu i nieczytelnie. Idea jest dość trywialna:
0. Ustalasz parametry -> rozmiar otoczenia i minimalną liczbę punktów do budowy klastra

1. Wybierasz losowy punkt i oznaczasz jako odwiedzony
2. Bierzesz epsilon-otoczenie tego punktu (tzn wszystkie punkty oddalone od źródła o nie więcej niż epsilon)
3. Jeśli punktów jest wystarczająco dużo to tworzymy z tego klaster
   4. Dla każdego nieodwiedzonego punktu z otoczenia oznaczamy punkt jako odwiedzony i dodajemy jego epsilon-otoczenie (jeśli zawiera dość punktów) do tej listy po której właśnie iterujemy
   5. Wszystkie punkty które w ten sposób przelecimy, a które nie miały klastra, dodajemy do aktualnego klastra
4. Jeśli punktów jest za mało to zostawiamy ten punkt i losujemy kolejny

Jak nie trudno zauważyć, oznaczanie punktów jako "odwiedzone" sprawia że w całym algorytmie dla każdego punktu tylko raz szukamy jego otoczenia, więc odległość od danego punktu do innych węzłów liczymy tylko raz, ale mimo wszystko jest to raczej dość kosztowna zabawa.
Zastanowiłbym się na twoim miejscu nad jakimś sprytnym sposobem wyszukiwania punktów w pewnym zasięgu. Może w ogóle skorzystać z jakiejś http://en.wikipedia.org/wiki/Spatial_database ? Bo naiwne szukanie daje O(n) a szukanie z użyciem jakiegoś zapytania przestrzennego opartego o indeks przestrzenny to jest O(logn), więc różnica dość znaczna. Dla twoich 300k punktów zamiast 300k operacji byłoby jakieś 18 ;] Ale implementowanie tego w fortranie może być bolesne, ale może są jakieś gotowe biblioteki?