Dynamické řezání stromu

Jak jsme již zmiňovali výše, hierarchické shlukování má svoji speciální roli v analýze genomických a proteomických dat. V porovnání s jinými shlukovacími technikami, shluky jsou zde definovány "ad-hoc", tedy až po provedení shlukování, a to řezáním větví hierarchicky strukturovného stromu podobnosti, který se nazývá dendrogram.

Toto řezání probíhá ve fixované výšce stromu (jinak řečeno na zvolené hranici vzdálenosti). Všechny větve stromu pod touto hranicí reprezentují finální shluky. Hlavní nevýhodou tohoto statického řezu je, že shluky se můžou vyskytovat na různých vzdálenostech, protože přirozene reflektují skupiny vzorků s různou podobností. Když se tedy dendrogram řeže v příliš nízké výšce, aby se dosáhlo podrobnější rozdělení některých skupin, má to za následek rozpad možná méně konzistentních shluků a vznik velkého množství nezařazených vzorků.

Tomuto problému se věnují nové dynamická metody detekování shluků v dendogramu hierarchického shlukování (Langfelder a kol., 2007). V tomto přístupu se shluky definují na základě jejich tvaru. Velkou výhodou je že takový systém je flexibilní - výsledek se dá ovlivnit množinou parametrů, jako například výška řezu, minimální velikost shluku, minimální mezishluková vzdálenost a podobně.

První metoda s názvem Dynamický strom (dynamic tree) - je vlastně o něco flexibilnější varianta statického řezu - pracuje pouze se strukturou dendrogramu. Druhá metoda Dynamický hybrid (angl. dynamic hybrid) dynamicky prohledává dendogram zespodu nahor a po definici shluků nabízí možnost dalšího zařazení dosud nezařazených vzorků do nejbližších jádrových shluků definovaných v prvním kroku, nenaruší-li se tím vnitřní similarita shluku (nepřekročí-li stanovenou hranici).

Detailní popis obou algoritmů je velice komplexní a my proto odkazujeme posluchače na originální článek.

Obě metody jsou implementovány v R balíku dynamicTreeCut.

Příklad použití algoritmu je demonstrovaný na reálném datovém souboru golub na obrázku níže.

Po hierarchickém shlukování vzorků na základě genové exprese jsme použili jsme statický řez a dynamický hybrid (funkce cutreeHybrid) dendrogramu na výšce řezu 1.2.

Minimální velikost shluků pro metodu dynamický hybrid byli tři a pět vzorků. Zatímco statický řez na zvoleném řezu identifikoval tři shluky, dynamický hybrid s minimální velikostí shluku pět identifikoval čtyři hlavní shluky. Snížení minimální velikosti shluků na tři identifikovalo další konzistentní shluky.