ED-4.2-m11-1.0-Slajd8

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Funkcje kryterialne (3)

Funkcje kryterialne (3)


Funkcję kryterialną problemu grupowania metoda iteracyjno-optymalizacyjną, która pozwala na ocenę jakości grupowania, można zdefiniować jako kombinację miar wc(C) i bc(C), np. jako stosunek bc(C)/wc(C). Proces grupowania jest tym lepszy, im większa jest wartość funkcji kryterialnej. maksymalizację funkcji kryterialnej można uzyskać bądź minimalizując wartość odchylenia wewnątrzklastrowego lub maksymalizując wartość odchylenia międzyklastrowego. Przyjęcie miary odchylenia wewnątrzklastrowego wc(C) zdefiniowanej na slajdzie, jako miary zwartości klastrów, prowadzi do generowania klastrów sferycznych (algorytm k-średnich).

Jak złożony jest obliczeniowo proces obliczania wartości funkcji kryterialnej? Złożoność procesu obliczania odchylenia wewnątrzklastrowego jest rzędu n, gdzie n oznacza liczbę grupowanych obiektów. Z kolei złożoność procesu obliczania odchylenia międzyklastrowego wymaga k do potęgi 2, gdzie k oznacza zadaną liczbę klastrów. Reasumując, obliczenie wartości funkcji kryterialnej dla pojedynczego grupowania (pojedynczego podziału) wymaga przejrzenia całego zbioru obiektów D. W przypadku analizy m podziałów, obliczenie wartości funkcji kryterialnej będzie wymagało m-krotnego przejrzenia zbioru obiektów D


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