ED-4.2-m11-1.0-Slajd4

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Metody iteracyjno-optymalizacyjne(3)

Metody iteracyjno-optymalizacyjne(3)


Zanim przejdziemy do przedstawienia ogólnego iteracyjno-optymalizacyjnego algorytmu grupowania, rozważmy problem grupowania jako klasyczny problem optymalizacyjny. Dowolny problem optymalizacyjny, a do takiej klasy należą problemy eksploracji danych, można zdefiniować w kontekście następujących 5 elementów: zadanie, model, funkcja kryterialna metoda przeszukiwania przestrzeni rozwiązań, oraz algorytmy i struktury danych wspierające proces eksploracji. W przypadku problemu grupowania zadaniem jest podział zbioru n obiektów na k rozłącznych zbiorów (klastrów, skupień). Modelem jest charakterystyka (definicja) wynikowych klastrów – np. możemy założyć, że poszukujemy wyłącznie klastrów wypukłych, że klaster musi zawierać co najmniej m obiektów, itd. Istnieje wiele możliwych rozwiązań danego zadania: które z rozwiązań jest najlepsze? W tym celu wprowadzamy funkcję kryterialną, która pozwala ocenić jakość przyjętego rozwiązania. W przypadku, gdy liczba możliwych rozwiązań danego problemu jest niewielka, to można zastosować metodę przeszukiwania pełnego – znaleźć wartość funkcji kryterialnej dla każdego z rozwiązań i, następnie, wybrać rozwiązanie, które jest optymalne z punktu widzenia przyjętej funkcji kryterialnej.


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