ED-4.2-m11-1.0-Slajd12

From Studia Informatyczne

Algorytm k-średnich (1)

Algorytm k-średnich (1)


Ogólny schemat algorytmu grupowania k-średnich ma następująca postać. Danymi wejściowymi algorytmu są: baza danych obiektów D oraz zadana liczba klastrów k. Wynikiem działania algorytmu jest zbiór k klastrów minimalizujący kryterium odchylenia wewnątrzklastrowego (błędu średniokwadratowego). Algorytm składa się z 3 kroków. W kroku pierwszym, wybieranych jest losowo k obiektów jako początkowe środki k klastrów.

W kroku drugim, obiekty alokowane są do klastrów. Każdy obiekt jest przydzielany do tego klastra, dla którego odległość obiektu od środka klastra jest najmniejsza. Następnie, po alokacji obiektów do klastrów, uaktualniane są wartości średnie klastrów (środki klastrów) i ponownie wracamy do kroku alokacji obiektów do klastrów. Może się bowiem okazać, że na skutek aktualizacji średnich klastrów zachodzi konieczność realokacji obiektów. Proces realokacji obiektów i uaktualniania średnich klastrów jest powtarzany tak długo, jak długo występują zmiany przydziału obiektów do klastrów. Warunek stopu może być zdefiniowany również w inny sposób, np. warunek time-out’u, zadana liczba iteracji, itp.


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