ED-4.2-m11-1.0-Slajd2

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Metody iteracyjno-optymalizacyjne(1)

Metody iteracyjno-optymalizacyjne(1)


Na poprzednim wykładzie przedstawiliśmy hierarchiczne algorytmy grupowania. Obecnie przejdziemy do przedstawienia drugiego z zasadniczych podejść do problemu grupowania, tj. podejścia iteracyjno-optymalizacyjnego. Metody iteracyjno-optymalizacyjne grupowania tworzą jeden podział zbioru obiektów (partycję) w miejsce hierarchicznej struktury podziałów, jak ma to miejsce w przypadku algorytmów hierarchicznych. Idea podejścia jest następująca: tworzony jest początkowy podział obiektów (zbiór klastrów k), a następnie, stosując technikę iteracyjnej realokacji obiektów pomiędzy klastrami, podział ten jest modyfikowany w taki sposób, aby uzyskać poprawę podziału zbioru obiektów pomiędzy klastry. Niestety, problem znalezienia najlepszego podziału zbioru obiektów pomiędzy k klastrów jest problemem trudnym. Łatwo zauważyć, że osiągnięcie „optimum” globalnego podziału obiektów wymaga przeanalizowania wszystkich możliwych podziałów zbioru n obiektów pomiędzy k klastrów. Zauważmy również, że w przypadku metod iteracyjno-optymalizacyjnych, liczba zadanych klastrów jest parametrem wejściowym procedury grupowania.


<< Poprzedni slajd | Spis treści | Następny slajd >>