Algoritmus hierarchického klastru Typy a kroky hierarchického klastru

Obsah:

Anonim

Úvod do hierarchického klastrovacího algoritmu

Hierarchický klastrovací algoritmus je technika strojového učení bez dozoru. Jeho cílem je nalezení přirozeného seskupení na základě charakteristik údajů.

Hierarchický klastrovací algoritmus si klade za cíl najít vnořené skupiny dat vytvořením hierarchie. Je to podobné biologické taxonomii rostlinného nebo živočišného království. Hierarchické klastry jsou obecně reprezentovány pomocí hierarchického stromu známého jako dendrogram.

Typy hierarchického klastrovacího algoritmu

Hierarchické klastrové algoritmy jsou 2 typů:

  • Divisive
  • Aglomerativní

1. Divisive

Jedná se o přístup shora dolů, kde zpočátku považuje všechna data za jednu skupinu a poté iterativně rozdělí data do podskupin. Pokud je znám počet hierarchických klastrových algoritmů, proces dělení se zastaví, jakmile je dosaženo počtu klastrů. Jinak se proces zastaví, když data již nelze dále dělit, což znamená, že podskupina získaná z aktuální iterace je stejná jako ta získaná z předchozí iterace (lze také zvážit, že dělení se zastaví, když každý datový bod je klastr ).

2. Aglomerativní

Jedná se o přístup zdola nahoru, který se opírá o sloučení klastrů. Zpočátku jsou data rozdělena do m singletonových shluků (kde hodnota m je počet vzorků / datových bodů). Dva klastry jsou sloučeny do jedné iterativně, čímž se snižuje počet klastrů v každé iteraci. Tento proces slučování klastrů se zastaví, když všechny klastry byly sloučeny do jednoho nebo je dosaženo požadovaného počtu klastrů.

Na úrovni 1 jsou klastry m, které se redukují na 1 klastr na úrovni m. Tyto datové body, které se sloučí a vytvoří klastr na nižší úrovni, zůstanou ve stejném klastru i na vyšších úrovních. Předpokládejme například, že existuje 8 bodů x1..x8, takže zpočátku existuje 8 shluků na úrovni 1. Předpokládejme, že body x1 a x2 se sloučí do shluku na úrovni 2, pak až do úrovně 8, zůstanou ve stejném shluku.

Výše uvedený obrázek ukazuje dendrogramové znázornění přístupu k aglomeračnímu seskupování pro 8 datových bodů, stejně jako měřítko podobnosti odpovídající každé úrovni.

Úrovně klastrů nám dávají představu o tom, jak podobné jsou datové body v klastrech. Jak je znázorněno na obr. 1, dříve se datové body sloučí do klastru, podobně jako jsou. Datové body v klastru na úrovni 2 (např. X2 a x3) jsou tedy podobnější než datové body v klastru na úrovni 6 (např. X1 a x2).

Na obrázku výše je znázorněno schéma Set nebo Venn aglomeračního přístupu k shlukování výše uvedených 8 datových bodů. Pro shlukování lze použít jak dendrogramy, tak reprezentace množin. Dendrogram je však obvykle výhodnější reprezentace aktiv, která nemůže kvantitativně reprezentovat podobnosti klastrů.

Kroky pro hierarchický klastrovací algoritmus

Pro hierarchický klastrovací algoritmus postupujte následovně:

1. Algoritmus

Aglomerační hierarchický klastrovací algoritmus

  1. Začněte inicializovat c, c1 = n, Di = (xi), i = 1, …, n '
  2. Do c1 = c1 - 1
  3. Najděte nejbližší klastry, řekněme, Di a Dj
  4. Sloučit Di a Dj
  5. Dokud c = c1
  6. Návrat klastrů c
  7. Konec

Tento algoritmus začíná n klastry zpočátku, kde každý datový bod je klastr. S každou iterací se počet klastrů sníží o 1, protože se spojí 2 nejbližší klastry. Tento proces pokračuje, dokud se počet klastrů sníží na předdefinovanou hodnotu c.

Jak se rozhodnout, které klastry jsou blízko?

To je definováno pomocí několika metrik vzdálenosti, které jsou následující:

  • Minimální vzdálenost mezi klastry dmin (Di, Dj). Užitečné pro singl.
  • Maximální vzdálenost mezi klastry dmax (Di, Dj). Užitečné pro dokončení.
  • Průměrná vzdálenost mezi klastry davg (Di, Dj).

Co je to Single Linkage a Complete Linkage?

  • Když se použije dmin (di, dj) k nalezení vzdálenosti mezi dvěma klastry a algoritmus skončí, pokud vzdálenost mezi nejbližšími klastry překročí prahovou hodnotu, pak se algoritmus nazývá algoritmus jediné vazby.
  • Když se použije dmax (Di, Dj) k nalezení vzdálenosti mezi dvěma klastry a algoritmus skončí, pokud vzdálenost mezi nejbližší klastry překročí prahovou hodnotu, pak se algoritmus nazývá algoritmus úplného propojení.
  • Uvažujme každý datový bod jako uzel grafu. Mezi dvěma datovými body je hrana, pokud patří do stejného klastru. Když se sloučí dva nejbližší klastry, přidá se okraj. Říká se tomu jediné propojení, protože existuje jedinečná cesta z jednoho uzlu do druhého.
  • Algoritmus úplného propojení spojuje dva klastry minimalizováním vzdálenosti mezi dvěma nejvzdálenějšími body.
  • Jediný algoritmus propojení generuje překlenovací strom. Tento algoritmus je však citlivý na šum. Kompletní algoritmus propojení generuje kompletní graf.

Jaká je časová složitost algoritmu?

Předpokládejme, že máme n obrazců v d-dimenzionálním prostoru a pomocí dmin (Di, Dj) vytvoříme klastry c. Musíme vypočítat n (n - 1) mezistupňové vzdálenosti - každá z nich je výpočtem O (d 2 ) - a výsledky umístit do tabulky mezistupňových vzdáleností. Složitost prostoru je O (n 2 ). Nalezení páru minimální vzdálenosti (pro první sloučení) vyžaduje, abychom prošli celým seznamem a udrželi index nejmenší vzdálenosti.

Tudíž pro první aglomerační krok je složitost O (n (n - 1) (d2 + 1)) = O (n2d2). Pro další libovolný krok aglomerace (tj. Od c1 do c1 - 1) pouze procházíme n (n - 1) - c1 „nevyužité“ vzdálenosti v seznamu a najdeme nejmenší, pro které leží x a x 'v různých klastrech . Toto je opět O (n (n − 1) −c1). Celková časová složitost je tedy O (cn 2 d 2 ) a za typických podmínek n >> c.

2. Vizualizace

Jakmile jsou data rozdělena do klastrů, je dobrým zvykem tyto klastry vizualizovat, abyste získali představu o tom, jak vypadá seskupení. Vizualizace těchto vysokorozměrných dat je však obtížná. Proto pro vizualizaci používáme analýzu hlavních komponent (PCA). Po PCA získáme datové body v nízkodimenzionálním prostoru (obvykle 2D nebo 3D), které můžeme vykreslit, abychom viděli seskupení.

Poznámka: Vysoký rozměr znamená velký počet funkcí a ne počet datových bodů.

3. Hodnocení

Jednou z metod pro hodnocení shluků je to, že vzdálenost bodů mezi shluky (vzdálenost mezi klastry) by měla být mnohem větší než vzdálenost bodů uvnitř klastru (vzdálenost uvnitř klastru).

Závěr

Zde je několik klíčových akcí s sebou:

  1. Hierarchický klastrovací algoritmus se používá k nalezení vnořených vzorů v datech
  2. Hierarchické shlukování je 2 typů - Divisive a Agglomerative
  3. Pro zobrazení lze použít dendrogram a set / Venn diagram
  4. Jednotné propojení spojuje dva klastry minimalizováním minimální vzdálenosti mezi nimi. Tvoří to překlenutí
  5. Kompletní propojení spojuje dva klastry minimalizováním maximální vzdálenosti mezi tím, že vytváří úplný graf.
  6. Celková časová složitost hierarchického klastrovacího algoritmu je O (cn 2 d 2 ), kde c je předdefinovaný počet shluků, n je počet vzorů ad je d-rozměrný prostor n obrazců.

Doporučené články

Toto je průvodce algoritmem hierarchického klastru. Zde diskutujeme typy a kroky hierarchických klastrových algoritmů. Další informace naleznete také v následujících článcích

  1. Hierarchická klastrová analýza
  2. Hierarchické shlukování v R '
  3. Clustering Algorithm
  4. Co je klastrování v těžbě dat?
  5. Hierarchické klastry Aglomerativní a dělící se shlukování
  6. Algoritmus C ++ | Příklady algoritmu C ++