ED-4.2-m11-1.0-Slajd20

Algorytm k-średnich (2)

Złożoność algorytmu k-średnich jest rzędu O(knI), gdzie I oznacza liczbę iteracji algorytmu, n liczbę grupowanych obiektów, natomiast k oznacza zadaną liczbę klastrów. Wynika ona z następującego spostrzeżenia. Dla danego zbioru środków klastrów rk, w ramach jednokrotnego przeglądu bazy danych D, można obliczyć wszystkie k*n odległości d(rk, x) i dla każdego obiektu x wybrać minimalną odległość tego punktu do środka klastra. Obliczenie nowych środków klastrów można wykonać w czasie O(n).

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