K-medoidy - K-medoids
The k-medoidy nebo dělení kolem medoidů (PAM) algoritmus je a shlukování algoritmus připomínající k-prostředek algoritmus. Oba k- znamená a k-medoidní algoritmy jsou dílčí (rozdělení datové sady do skupin) a oba se pokoušejí minimalizovat vzdálenost mezi body označenými jako klastr a bodem označeným jako střed daného klastru. Na rozdíl od k- znamená algoritmus, k-medoids vybírá datové body jako centra (medoidy nebo exempláře) a lze je použít s libovolnými vzdálenostmi, zatímco v k- znamená, že střed klastru nemusí být nutně jedním ze vstupních datových bodů (jedná se o průměr mezi body v klastru). Metoda PAM byla navržena v roce 1987[1] pro práci s norma a další vzdálenosti.
k-medoid je klasická technika dělení na shluky, která shlukuje datovou sadu n předměty do k shluky s číslem k shluků, o nichž se předpokládá, že jsou známy a priori (což znamená, že programátor musí před provedením algoritmu zadat k). "Dobrota" dané hodnoty k lze posoudit pomocí metod, jako je silueta metoda.
Je odolnější vůči hluku a odlehlým hodnotám ve srovnání s k-prostředek protože místo součtu minimalizuje součet párových odlišností na druhou euklidovské vzdálenosti.
A medoid lze definovat jako objekt klastru, jehož průměrná odlišnost vůči všem objektům v klastru je minimální, to znamená, že se jedná o nejvíce centrálně umístěný bod v klastru.
Algoritmy

Nejběžnější realizace k-medoidní shlukování je rozdělení kolem algoritmu medoidů (PAM). PAM používá chamtivé hledání, které nemusí najít optimální řešení, ale je rychlejší než vyčerpávající vyhledávání. Funguje to následovně:
- Inicializovat: hltavě vybrat k z n datové body jako medoidy, aby se minimalizovaly náklady
- Přiřaďte každý datový bod k nejbližšímu medoidu.
- Zatímco náklady na konfiguraci klesají:
- Pro každého medoida ma pro každý nemedoidní datový bod Ó:
- Zvažte výměnu m a Óa spočítat změnu nákladů
- Pokud je změna nákladů v současnosti nejlepší, pamatujte na to m a Ó kombinace
- Proveďte nejlepší výměnu a , pokud sníží nákladovou funkci. Jinak se algoritmus ukončí.
- Pro každého medoida ma pro každý nemedoidní datový bod Ó:
Runtime složitost původního PAM algoritmu na iteraci (3) je pouze výpočtem změny nákladů. Bude naivní implementace, která pokaždé přepočítá celou nákladovou funkci . Tuto dobu běhu lze dále snížit na rozdělením změny nákladů na tři části, aby bylo možné výpočty sdílet nebo se jim vyhnout.[2]
Algoritmy jiné než PAM byly také navrženy v literatuře, včetně následujících Voronoiova iterace metoda:[3][4][5]
- Náhodně vyberte počáteční medoidy
- Iterujte, zatímco cena klesá:
- V každém klastru udělejte bod, který minimalizuje součet vzdáleností v klastru medoidem
- Přiraďte každý bod ke shluku definovanému nejbližší medoidem určeným v předchozím kroku.
Nicméně, k- znamená Voronoiova iterace ve stylu znamená horší výsledky, protože neumožňuje opětovné přiřazení bodů jiným klastrům při změně prostředků, a proto zkoumá pouze menší prostor pro vyhledávání.[2][6]
Přibližné algoritmy CLARA a CLARANS vyměňují optimálnost za běhu. CLARA aplikuje PAM na více dílčích vzorků a udržuje nejlepší výsledek. CLARANS funguje na celém souboru dat, ale zkoumá pouze podmnožinu možných swapů medoidů a nemedoidů pomocí vzorkování.
Software
- ELKI zahrnuje několik k-medoidní varianty, včetně Voronoi-iterace k-medoidy, původní algoritmus PAM, vylepšení Reynoldse a algoritmus O (n²) FastPAM, CLARA, CLARANS, FastCLARA a FastCLARANS.
- Julie obsahuje a k-medoidní implementace algoritmu stylu k-means (rychlejší, ale mnohem horší kvalita výsledků) v JuliaStats / Clustering.jl balík.
- KNIME zahrnuje a k-medoidní implementace podporující řadu účinných opatření vzdálenosti matic, stejně jako řadu nativních (a integrovaných třetích stran) k- znamená implementace
- R obsahuje PAM v balíčku „cluster“, včetně některých vylepšení FastPAM prostřednictvím možnosti pamonce = 5.
- RapidMiner má operátor jménem KMedoids, ale má ne správně implementujte algoritmus KMedoids. Místo toho je to varianta k-means, která nahradí průměr nejbližším datovým bodem (který není medoidem).
- MATLAB implementuje PAM, CLARA a dva další algoritmy k řešení k- problém seskupení medoidů.
Reference
- ^ Kaufman, L. a Rousseeuw, P.J. (1987), Shlukování pomocí Medoidů, ve Statistické analýze dat založené na –Norm a související metody, editoval Y. Dodge, North-Holland, 405–416.
- ^ A b Schubert, Erich; Rousseeuw, Peter J. (2019), Amato, Giuseppe; Gennaro, Claudio; Oria, Vincent; Radovanović, Miloš (eds.), „Rychlejší shlukování k-Medoidů: Zlepšení algoritmů PAM, CLARA a CLARANS“, Hledání podobnosti a aplikaceSpringer International Publishing, 11807, str. 171–187, arXiv:1810.05691, doi:10.1007/978-3-030-32047-8_16, ISBN 9783030320461
- ^ Maranzana, F. E. (1963). "Na umístění odběrných míst, aby se minimalizovaly náklady na dopravu". IBM Systems Journal. 2 (2): 129–135. doi:10.1147 / sj.22.0129.
- ^ T. Hastie, R. Tibshirani a J. Friedman. Prvky statistického učení, Springer (2001), 468–469.
- ^ Park, Hae-Sang; Jun, Chi-Hyuck (2009). "Jednoduchý a rychlý algoritmus pro shlukování K-medoidů". Expertní systémy s aplikacemi. 36 (2): 3336–3341. doi:10.1016 / j.eswa.2008.01.039.
- ^ Teitz, Michael B .; Bart, Polly (01.10.1968). "Heuristické metody pro odhad zobecněného mediánu vrcholů váženého grafu". Operační výzkum. 16 (5): 955–961. doi:10,1287 / opre.16.5.955. ISSN 0030-364X.