Metoda k-medoidů

Metoda -medoidů je velice podobná metodě k-průměrů, s tím rozdílem, že zástupcem středu shluku není centroid, ale tzv. reprezentativní objekt – medoid. Další rozdíl mezi metodami -průměrů a -medoidů je v metrice (čtverec Euklidovské vzdálenosti u metody -průměrů, jakákoliv metrika vzdálenosti u metody -medoidů), kterou se hodnotí vzdálenost objektů od středu shluku, tj. centroidů v metodě -průměrů a medoidů v metodě -medoidů.

Princip metody k-medoidů je v hledání reprezentativních objektů, které nazýváme medoidy. Medoid je definován jako objekt shluku, jehož průměrná nepodobnost ke všem objektům v shluku je minimální, tj. je to nejcentrálněji umístěný bod v daném datovém souboru. Shluk je pak definován jako soubor objektů, které jsou přiřazeny ke stejnému medoidu. Metodu -medoidů můžeme považovat za robustnější obdobu metody -průměrů.

Nejčastější realizací shlukování -medoidů je algoritmus PAM Partitioning around medoids:

1. Postupně je selektováno reprezentativních objektů. První objekt je ten, pro který je suma nepodobností ke všem dalším objektům co nejmenší. Tento objekt je umístěn nejvíce centrálně v sadě objektů. Postupně je v každé iteraci vybrán další objekt, který snižuje sumu (přes všechny objekty) nepodobností k nejpodobnějšímu vybranému objektu co nejvíce. Proces pokračuje, až dokud není nalezeno reprezentativních objektů – medoidů.
2. Všechny objekty jsou spojeny s nejbližším medoidem. Míra nepodobnosti/vzdálenosti je definována jakoukoliv platnou metrikou vzdálenosti, nejčastěji Euklidovskou vzdáleností, Manhattanskou vzdáleností, Minkowského vzdáleností, 1 – korelace.
3. V druhé fázi algoritmu se zlepšuje sada medoidů a tedy shlukování. To se děje srovnáním všech párů objektů, kde jeden z nich je medoidem a druhý ne. Pro každý medoid a postupně pro každý objekt , který není medoidem, se vymění pozice a a zjišťuje se hodnota kriteria shlukování pro tuto konfiguraci. Když se zlepší kriterium shlukování, testovaný objekt se stane medoidem místo původního medoidu. Tato procedura se opakuje, dokud již nedochází k žádnému dalšímu zlepšení.

Výhody metody -medoidů:

• Metoda nevyžaduje původní data, může být aplikována také přímo na matici nepodobnosti.
• Shlukování je možné na základě jakékoliv metriky vzdálenosti, co může být důležité např. v biologických aplikacích, kdy se může jednat např. o shlukování korelovaných prvků.
• Medoidy jsou robustními představiteli středů shluků, jsou méně citlivé k odlehlým pozorováním než centroidy v metodě k-průměrů (tato robustnost je důležitá, když objekty nepatří jasně k žádnému shluku).
• Shlukování není závislé na pořadí objektů v datové matici (s výjimkou případů, kdy existují ekvivalentní řešení, což je velice zřídka).

Nevýhodou metody -medoidů je stejně jako u metody -průměrů potřeba definovat počet shluků předem. Tento problém lze řešit pomocí koeficientu siluety (silhouette coefficient) nebo jiných metod pro určení optimálního počtu shluků .