Dunnův index - Dunn index

The Dunnův index (DI) (představený J. C. Dunnem v roce 1974) je metrikou pro hodnocení shlukovací algoritmy.^[1][2] Toto je část skupiny indexů platnosti, včetně Davies – Bouldinův index nebo Silueta index v tom, že se jedná o schéma interního hodnocení, kde je výsledek založen na samotných seskupených datech. Stejně jako všechny ostatní takové indexy je cílem identifikovat sady klastrů, které jsou kompaktní, s malou odchylkou mezi členy klastru a dobře oddělené, kde jsou prostředky různých klastrů dostatečně vzdálené ve srovnání s klastrem uvnitř rozptyl. U daného přiřazení klastrů označuje vyšší Dunnův index lepší klastrování. Jednou z nevýhod tohoto použití jsou výpočetní náklady, protože se zvyšuje počet klastrů a rozměrnost dat.

Předkola

Existuje mnoho způsobů, jak definovat velikost nebo průměr klastru. Může to být vzdálenost mezi nejvzdálenějšími dvěma body uvnitř klastru, může to být průměr všech párových vzdáleností mezi datovými body uvnitř klastru, nebo to může být také vzdálenost každého datového bodu od těžiště klastru. Každá z těchto formulací je matematicky uvedena níže:

Nechat C_i být shluk vektorů. Nechat X a y být libovolné dva ndimenzionální vektory funkcí přiřazené stejnému klastru C_i.

${ displaystyle Delta _ {i} = { podmnožina {x, y v C_ {i}} { text {max}}} d (x, y)}$ , který vypočítá maximální vzdálenost.

${ displaystyle Delta _ {i} = { dfrac {2} {| C_ {i} | (| C_ {i} | -1)}} { podmnožina {x, y v C_ {i}, x neq y} { sum}} d (x, y)}$ , který vypočítá střední vzdálenost mezi všemi páry.

${ displaystyle Delta _ {i} = { dfrac {{ podmnožina {x v C_ {i}} { sum}} d (x, mu)} {| C_ {i} |}}, mu = { dfrac {{ underset {x in C_ {i}} { sum}} x} {| C_ {i} |}}}$ , vypočítá vzdálenost všech bodů ze střední hodnoty.

To lze také říci o vzdálenosti mezi klastry, kde lze vytvořit podobné formulace, a to buď pomocí nejbližších dvou datových bodů, jednoho v každém klastru, nebo nejvzdálenějších dvou, nebo vzdálenosti mezi centroidy atd. Definice indexu zahrnuje jakoukoli takovou formulaci a takto vytvořená skupina indexů se nazývá Dunnovy indexy. Nechat ${ displaystyle delta (C_ {i}, C_ {j})}$ být touto metrickou vzdáleností mezi klastry mezi klastry C_i a C_j.

Definice

S výše uvedeným zápisem, pokud existují m shluky, pak je Dunnův index pro sadu definován jako:

${ displaystyle { mathit {DI}} _ {m} = { frac {{ podmnožina {1 leqslant i$.

Vysvětlení

Tímto způsobem je definována DI záleží na m, počet klastrů v sadě. Pokud počet klastrů není apriori znám, m pro které DI je nejvyšší lze zvolit jako počet klastrů. Existuje také určitá flexibilita, pokud jde o definici d (x, y) kde lze použít kteroukoli ze známých metrik, jako Vzdálenost na Manhattanu nebo Euklidovská vzdálenost na základě geometrie problému shlukování. Tato formulace má zvláštní problém v tom, že pokud se jeden z klastrů chová špatně, zatímco ostatní jsou pevně zabaleni, protože jmenovatel obsahuje místo průměrného výrazu výraz „max“, bude Dunnův index pro tuto skupinu klastrů nezvykle nízká. Jedná se tedy o indikátor nejhoršího případu a je třeba ho mít na paměti. Existují připravené implementace Dunnova indexu v některých vektorových programovacích jazycích, jako je MATLAB, R a Apache Mahout.^[3][4][5]

Poznámky a odkazy

externí odkazy

• Pakhira, Malay K .; Bandyopadhyay, Sanghamitra; Maulik, Ujjwal (2004). "Index platnosti pro ostré a fuzzy shluky". Rozpoznávání vzorů. 37 (3): 487–501. doi:10.1016 / j.patcog.2003.06.005.
• Bezdek, J.C .; Pal, N.R. (1995). "Ověření clusteru s generalizovanými Dunnovými indexy". Proceedings 1995 Druhá novozélandská mezinárodní dvouproudá konference o umělých neuronových sítích a expertních systémech. IEEE Xplore: 190–193. doi:10.1109 / ANNES.1995.499469. ISBN  0-8186-7174-2.
• Algoritmy platnosti klastru