ED-4.2-m11-1.0-Slajd20
Z Studia Informatyczne
Wersja z dnia 10:32, 29 sie 2006 autorstwa ALesniewska (dyskusja | edycje)
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).