Davies – Bouldinův index - Davies–Bouldin index - Wikipedia

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek příliš spoléhá na Reference na primární zdroje. Vylepšete to přidáním sekundární nebo terciární zdroje. (Květen 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek vyžaduje pozornost odborníka na statistiku. Přidejte prosím důvod nebo a mluvit parametr k této šabloně pro vysvětlení problému s článkem. Statistiky WikiProject může pomoci s náborem odborníka. (Květen 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The Davies – Bouldinův index (DBI), představený Davidem L. Daviesem a Donaldem W. Bouldinem v roce 1979, je metrikou hodnocení shlukovací algoritmy.^[1] Toto je schéma interního hodnocení, kde se ověřuje, jak dobře bylo klastrování provedeno pomocí množství a funkcí inherentních datové sadě. To má nevýhodu, že dobrá hodnota hlášená touto metodou neznamená nejlepší načítání informací.^{[Citace je zapotřebí ]}

Předkola

Dáno n rozměrové body, nechť C_i být shlukem datových bodů. Nechat X_j být n-dimenzionální vektor funkcí přiřazený klastru C_i.

${ displaystyle S_ {i} = left ({ frac {1} {T_ {i}}} sum _ {j = 1} ^ {T_ {i}} { left | X_ {j} -A_ { i} doprava | ^ {p}} doprava) ^ {1 / p}}$

Tady ${ displaystyle A_ {i}}$ je těžiště z C_i a T_i je velikost klastru i. S_i je míra rozptylu v klastru. Obvykle hodnota str je 2, což z toho dělá a Euklidovská vzdálenost funkce mezi těžištěm klastru a jednotlivými vektory funkcí. Lze použít i mnoho dalších metrik vzdálenosti rozdělovače a vyšší dimenzionální data, kde euklidovská vzdálenost nemusí být nejlepším měřítkem pro určení klastrů. Je důležité si uvědomit, že tato metrika vzdálenosti se musí pro smysluplné výsledky shodovat s metrikou použitou v samotném klastrovacím schématu.

${ displaystyle M_ {i, j} = left | left | A_ {i} -A_ {j} right | right | _ {p} = { Bigl (} displaystyle sum _ {k = 1 } ^ {n} left | a_ {k, i} -a_ {k, j} right | ^ {p} { Bigr)} ^ { frac {1} {p}}}$

${ displaystyle M_ {i, j}}$ je míra oddělení mezi shlukem ${ displaystyle C_ {i}}$ a shluk ${ displaystyle C_ {j}}$.

${ displaystyle a_ {k, i}}$ je kth prvek ${ displaystyle A_ {i}}$, a v nich není n takových prvků A protože je to n dimenzionální těžiště.^{[nekonzistentní ]}

Tady k indexuje vlastnosti dat, a to je v podstatě Euklidovská vzdálenost mezi středy klastrů i a j když str se rovná 2.

Definice

Nechat R_{já, j} být měřítkem toho, jak dobrý je shlukovací systém. Toto opatření musí ze své podstaty odpovídat M_{já, j} oddělení mezi i^th a j^th shluk, který v ideálním případě musí být co největší, a S_i, rozptyl uvnitř klastru pro klastr i, který musí být co nejnižší. Proto je index Davies – Bouldin definován jako poměr S_i a M_{já, j} tak, aby byly zachovány tyto vlastnosti:

1. ${ displaystyle R_ {i, j} geqslant 0}$.
2. ${ displaystyle R_ {i, j} = R_ {j, i}}$.
3. Když ${ displaystyle S_ {j} geqslant S_ {k}}$ a ${ displaystyle M_ {i, j} = M_ {i, k}}$ pak ${ displaystyle R_ {i, j}> R_ {i, k}}$.
4. Když ${ displaystyle S_ {j} = S_ {k}}$ a ${ displaystyle M_ {i, j} leqslant M_ {i, k}}$ pak ${ displaystyle R_ {i, j}> R_ {i, k}}$.

U této formulace platí, že čím nižší je hodnota, tím lepší je oddělení klastrů a „těsnost“ uvnitř klastrů.

Řešení, které splňuje tyto vlastnosti, je:

${ displaystyle R_ {i, j} = { frac {S_ {i} + S_ {j}} {M_ {i, j}}}}$

Používá se k definování D_i:

${ displaystyle D_ {i} ekviv max _ {j neq i} R_ {i, j}}$

Pokud N je počet klastrů:

${ displaystyle { mathit {DB}} equiv { frac {1} {N}} displaystyle sum _ {i = 1} ^ {N} D_ {i}}$

DB se nazývá Davies – Bouldinův index. To závisí jak na datech, tak na algoritmu. D_i zvolí nejhorší scénář a tato hodnota se rovná R_{já, j} pro nejpodobnější klastr i. Mohlo by existovat mnoho variací této formulace, jako je výběr průměru podobnosti shluku, váženého průměru atd.

Vysvětlení

Tyto podmínky omezují takto definovaný index na symetrický a nezáporný. Kvůli způsobu, jakým je definován, jako funkce poměru rozptylu uvnitř klastru k oddělení mezi klastry bude nižší hodnota znamenat, že shlukování je lepší. Stává se to průměrná podobnost mezi každým klastrem a jeho nejpodobnějším, zprůměrovaná ve všech klastrech, kde je podobnost definována jako S_i výše. To potvrzuje myšlenku, že žádný klastr nemusí být podobný jinému, a proto nejlepší klastrovací schéma v podstatě minimalizuje Davies-Bouldinův index. Takto definovaný index je průměrem za všechny i shluky, a proto je dobrým měřítkem rozhodování o tom, kolik klastrů ve datech skutečně existuje, je vykreslit je proti počtu klastrů, pro které se počítá. Číslo i pro které je tato hodnota nejnižší, je dobrým měřítkem počtu shluků, do kterých by bylo možné data ideálně zařadit. To má aplikace při rozhodování o hodnotě k v kmeans algoritmus, kde hodnota k není známa apriori. Sada nástrojů SOM obsahuje a MATLAB implementace.^[2] Implementace MATLAB je také k dispozici prostřednictvím nástroje MATLAB Statistics and Machine Learning Toolbox pomocí příkazu „evalclusters“.^[3] A Jáva implementace se nachází v ELKI a lze jej porovnat s mnoha dalšími indexy kvality shlukování.

Viz také

• Silueta (shlukování)
• Dunnův index

externí odkazy

• http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.2072
• https://books.google.com/books?id=HY8gB2OIqSoC
• http://nl.mathworks.com/help/stats/clustering.evaluation.daviesbouldinevaluation-class.html

Poznámky a odkazy