ED-4.2-m11-1.0-Slajd3
Metody iteracyjno-optymalizacyjne(2)
W jaki sposób początkowy podział obiektów pomiędzy k klastrów jest modyfikowany przez algorytmy iteracyjno-optymalizacyjne? Odpowiedź jest następująca. Metody iteracyjno-optymalizacyjne realokują obiekty pomiędzy klastrami optymalizując pewną funkcję kryterialną. Przy czym funkcja kryterialna może być zdefiniowana lokalnie (na podzbiorze obiektów) lub globalnie (na całym zbiorze obiektów).
Jak wspomnieliśmy wcześniej, problem znalezienia optymalnego podziału zbioru obiektów pomiędzy k klastrów jest problemem trudnym. Dla dużej liczby obiektów, rzędu tysięcy obiektów, przeszukanie całej przestrzeni wszystkich możliwych podziałów zbioru obiektów pomiędzy k klastrów jest, praktycznie, nie realizowalne. Ponieważ znalezienie optimum funkcji kryterialnej, praktycznie, jest niemożliwe, zachodzi potrzeba zdefiniowania heurystyki, która będzie znajdowała „najlepszy”, możliwy do osiągnięcia, podział obiektów pomiędzy k klastrów. Okazuje się, że w przypadku algorytmów iteracyjno-optymalizacyjnych wynik grupowania silnie zależy od początkowego podziału obiektów (do tego zagadnienia wrócimy jeszcze później w ramach wykładu), stąd, w celu poprawy wyniku grupowania stosuje się, dodatkowo, prosty mechanizm dywersyfikacji - algorytm grupowanie jest uruchamiany kilkakrotnie, dla różnych podziałów początkowych, a następnie, najlepszy z uzyskanych podziałów jest przyjmowany jako wynik procesu grupowania.
