ED-4.2-m11-1.0-Slajd4
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 kryterialnametoda 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.
