E-learning 2. Analýza dat 2.1. Obecný průběh analýzy 2.1.3. Objevování skupin 2.1.3.1. Metody založené na vzdálenosti

Hierarchické metody představují skupinu metod která shlukováním vytváří hierarchii. Jednotlivé prvky (geny, nebo pacienti) jsou uspořádané do množin a tyto množiny jsou navzájem dále hierarchicky propojeny, na základě vzdálenosti mezi nimi.

Existují dva základní postup hierarchického shlukování :

• Aglomerativní  - v angličtině také nazývaný "botoom-up" - shlukování začíná na úrovni jednotlivých prvků, v každém kroku jsou vytvořené množiny shlukovány podle určené míry vzdálenosti a vybraného algoritmu až v posledním kroku jsou všechny zahrnuty v jedné skupině. Mezi nejznámější aglomerativní algoritmy patří:
  
  • Single linkage
  • Average linkage
  • Complete linkage
  • Ward 

• Divizivní -v angličtině také nazývaný "top-down" - proces začína naopak velkým shlukem všech prvků, který je dále dělen na dva shluky, každý z nich zas na další a podobně, až se dostaneme na úroveň jednotlivých prvků. Mezi nejznámější divizivní algoritmy patří například:
  • DIANA
     

Na obrázku 1 je zobrazen příklad výsledků shlukováni pacientů, pomocí rozličných algoritmů.

Základní charakteristikou hierarchických shlukování je, že není nutné dopředu znát počet shluků . Hierarchické shlukování se také jednoduše vizualizuje a koncept podobnosti jednotlivých shluků a závislosti mezi skupinami se zdá být intuitivnější.

Toto shlukování je velice oblíbené hlavně pro tyto vlastnosti.

Na druhé straně, neznalost počtu shluků je také nevýhodná a to proto, že je potřebné se "ad-hoc" rozhodnout, kolik skupin je vlastně relevantních, tedy v jaké výšce by se měl dendrogram virtuálně rozstřihnout. K tomuto účelu existuje poměrně velké množství metod, které se snaží různými mechanizmy stanovit stabilitu jednotlivých shluků a tak určit jejich optimální počet.

Grafické znázornění výsledku hierarchického shlukování v podobě stromu, kde na osi X jsou jednotlivé shlukované prvky a os Y představuje vzdálenost na které byli mezi prvky/množiny sjednoceny se nazývá dendrogram.

Obrázek 1. Dendrogram výsledků hierarchického slukování rozličnými algoritmy.