Rozhodovací stromy

Jedná se o shlukovací metodu, tedy přesněji řečeno hierarchické shlukovací metody. Tyto metody vytváří stromy, které postupně shlukují objekty podle vzájemné podobnosti. Tento strom se nazývá též dendrogram. Ideálně použitelná je tato metoda pro objekty, které vznikly nějakým dělením či spojováním (státy na kontinentech, obce v republice, zvířata apod.). Mezi hlavní výhody patří fakt, že není potřeba vědět předem počet shluků a stačí použít pouze matici odlišnosti. Mezi nevýhody patří opět citlivost na jednotky měření, náročný výpočet pro rozsáhlejší datové sady a fakt, že někdy rozdílné metody výpočtu dosahují rozdílné výsledky. Dendrogramy jsou vytvářeny buďto směrem bottom-up (aglomerativní) nebo top-down (divizivní). Důležité informace opět získáte z prezentace doc. Harmana.

Hierarchické aglomerativní shlukování – v případě této metody se začíná v kroku, kdy každý objekt vytváří jeden shluk. Postupně se shlukují nejpodobnější (nejbližší) objekty až do doby, kdy jsou všechny objekty propojeny do jednoho shluku spojujícího všechny objekty v analyzovaném souboru. Rozdílné definice vzdáleností mezi objekty přináší rozdílné výsledky:

• Metoda nejbližšího souseda (single linkage) – nejmenší vzdálenosti mezi objekty shluků (vede k vytváření nejvíce zřetězených shluků)
• Průměrná vzdálenost (average linkage) – průměrné vzdálenosti mezi objekty shluků
• Centroidní metoda (pair group centroid) – vzdálenosti centroidů shluků
• Metoda nejvzdálenějšího souseda (complete linkage) – vzdálenosti mezi nejvzdálenějšími objekty shluků (vytváří dobře oddělené shluky)
• Wardova metoda – kritériem pro shlukování je celkový součet druhých mocnin odchylek každého objektu od těžiště shluku, do kterého náleží.

Při jednotlivých krocích v případě metody nejbližší vzdálenosti se postupuje tak, že se vypočítá asociační matice, které obsahuje vzdálenosti mezi jednotlivými objekty. Vybere se vzdálenost mezi nejbližšími objekty a ty se spojí do shluku. V další kole se opět přepočte asociační matice, kdy dva objekty reprezentovány dvěma objekty vytváří nově jeden objekt a v případě metody nejbližší vzdálenosti se vypočítává vzdálenost toho bližšího objektu z daného shluku k ostatním objektů a opět se vybírá nejmenší vzdálenost. Může nastat situace, kdy je k danému shluku přidán další objekt, nebo je vytvořen jiný nový shluk. Postupuje se tak dlouho, doku nejsou všechny objekty spojeny v jednom shluku.

V R se tato metoda volá funkcí agnes() z balíčku cluster:

agnes(x, diss, metric, stand, method, …)

kde x je datový rámec vektorů nebo matice odlišnosti, diss nabývá hodnoty TRUE, pokud x je matice odlišnosti, metric definuje použitou metriku (euclidean, manhattan), stand nabývá hodnoty TRUE, pokud vyžadujeme standardizaci hodnot a method pak definuje metodu měření vzdálenosti mezi objekty shluků (sigle, average, complete, Ward).

Hierarchické divizivní shlukování – tady metoda postupuje tak, že vstupem je jeden velký shluk, který obsahuje všechny objekty. V dalším kroku je nalezen objekt, který je nejvíce odlišný ke všem ostatním a tento objekt vytváří základ dalšího shluku. V dalších krocích je porovnávána podobnost všech objektů k ostatním objektům a k nejvíce odlišnému objektu (např. se porovnává průměrná odlišnost objektu ke všem ostatních objektům a odlišnost k nejvíce odlišnému objektu). Pokud je daný objekt podobnější k nejvíce odlišnému objektu, tak je přiřazen do shluku k tomuto nejvíce odlišnému. Tímto postupem se pokračuje dále, doku každý objekt nevytváří samostatný shluk.

V R se tato metoda volá funkcí diana() z balíčku cluster:

agnes(x, diss, metric, stand, …)

kde x je datový rámec vektorů nebo matice odlišnosti, diss nabývá hodnoty TRUE, pokud x je matice odlišnosti, metric definuje použitou metriku (euclidean, manhattan) a stand nabývá hodnoty TRUE, pokud vyžadujeme standardizaci hodnot.

Zpracování v prostředí IBM SPSS Statistics

Zadání

Vyzkoušíme si vytvořit hierarchické shlukování pro data z minulého cvičení – výsledky ze SLDB 2011 pro obce ČR. Načtěte si tato data a vytvořte si datový rámec s prvními 50 záznamy a jen s číselnými hodnotami, které obsahují relativní čísla. Tato data budou vstupovat do výpočtu obou metod.

 

Kromě níže uvedených dendrogramů je součást výsledků také tzv. divisive coefficient, který je v případě diany roven 0,78 a v případě agnes pak 0,76. Tento koeficient udává, jak moc se dané objekty shlukují. Rozsah je od 0 do 1, kdy hodnoty blíže 1 indikují velmi jasnou strukturu shluků, zatímco 0 naznačuje, že nebyly nalezeny žádné přirozené shluky, tedy data se skládají jen z jednoho velkého shluku. Je potřeba si dále uvědomit, že daný ukazatel roste s rostoucím počtem objektů a neměl by být tedy porovnáván mezi různě velkými datovými soubory.

Samostatná práce

• připravte si datový soubor, do kterého vyberete 20 různých obcí a vyberte si 5 různých relativních ukazatelů
• vyzkoušejte si hierarchické aglomerativní shlukování a porovnejte výsledky pro všechny 4 různé metody určení vzdáleností
• porovnejte také s výsledkem hierarchického divizivního shlukování

Data pro vedené i samostatné cvičení

Cvičení je vytvořeno v rámci projektu Inovace bakalářských a magisterských studijních oborů na Hornicko-geologické fakultě VŠB-TUO pod číslem CZ.1.07/2.2.00/28.0308. Tento projekt je realizován za spoluúčasti EU.