ED-4.2-m11-1.0-Slajd23
Algorytm k-medoidów (1)
Jedną z zasadniczych wad algorytmu k-średnich jest jego czułość na dane zaszumione i występowanie punktów osobliwych. W celu uodpornienia algorytmu k-średnich na występowanie punktów osobliwych, zamiast średnich klastrów jako środków tych klastrów, można przyjąć medoidy – najbardziej centralnie ulokowane punkty klastrów. Wystąpienie punktu osobliwego w klastrze nie spowoduje wówczas tak dramatycznej zmiany wartości średniej klastra. Ile wynosi średnia zbioru składającego się z elementów o następujących wartościach: 1, 3, 5, 7, i 9? Średnia wynosi (1+3+5+7+9)/5 = 5. Ile wynosi średnia zbioru składającego się z następujących elementów: 1, 3, 5, 7, i 1009? Punkt 1009 jest tutaj punktem osobliwym, którego wartość istotnie odbiega od pozostałych punktów. Średnia wynosi (1+3+5+7+1009)/5 = 205. Widzimy, że średnia wyraźnie uległa zmianie przesuwając się w kierunku punktu osobliwego. Zastępując średnią zbioru medoidem tego zbioru otrzymujemy następujący wynik – medoidem zbioru 1, 3, 5, 7, i 1009 jest punkt 5. Zastąpienie w algorytmie k-średnich wartości średniej klastra medoidem klastra prowadzi do algorytmu, który w literaturze nosi nazwę algorytmu k-medoidów.
