Grupowanie hierarchiczne

Czym jest grupowanie hierarchiczne?

Grupowanie hierarchiczne to technika grupowania danych, która polega na tworzeniu hierarchicznej struktury klastrów. Proces ten organizuje dane w postaci drzewa (dendrogramu), gdzie każdy poziom reprezentuje różne stopnie podobieństwa między obiektami. Grupowanie hierarchiczne nie wymaga wcześniejszego określenia liczby klastrów i pozwala na analizę danych na różnych poziomach szczegółowości.

Podejścia do grupowania hierarchicznego:

1. Aglomeracyjne (bottom-up):

   • Każdy obiekt zaczyna jako osobny klaster.
   • Klastery są stopniowo łączone na podstawie miary podobieństwa, aż wszystkie obiekty znajdą się w jednym klastrze.

2. Deglomeracyjne (top-down):

   • Wszystkie obiekty zaczynają jako jeden klaster.
   • Klaster jest iteracyjnie dzielony na mniejsze, aż każdy obiekt stanie się osobnym klastrem.

Miary odległości w grupowaniu hierarchicznym:

1. Odległość euklidesowa:

   • Najczęściej stosowana miara dla danych numerycznych.
   • Oblicza prostą odległość w przestrzeni wielowymiarowej.

2. Odległość Manhattan:

   • Suma wartości bezwzględnych różnic między współrzędnymi.

3. Miara Jaccarda:

   • Używana dla danych binarnych, mierzy podobieństwo między zestawami.

4. Odległość Minkowskiego:

   • Uogólnienie odległości euklidesowej i Manhattan.

Metody łączenia klastrów:

1. Pojedyncze połączenie (single linkage):

   • Odległość między dwoma klastrami jest definiowana jako najmniejsza odległość między dowolnymi punktami w tych klastrach.

2. Kompletne połączenie (complete linkage):

   • Odległość między dwoma klastrami to największa odległość między dowolnymi punktami w tych klastrach.

3. Średnie połączenie (average linkage):

   • Odległość między klastrami to średnia odległość między wszystkimi parami punktów w klastrach.

4. Połączenie centroidów (centroid linkage):

   • Odległość między środkami klastrów.

5. Metoda Warda:

   • Minimalizuje sumę kwadratów różnic w obrębie klastrów.

Zalety grupowania hierarchicznego:

• Brak potrzeby określenia liczby klastrów z góry:
  • Liczbę klastrów można wybrać na podstawie dendrogramu.
• Elastyczność:
  • Może działać zarówno z danymi numerycznymi, jak i kategorycznymi.
• Dendrogram:
  • Wizualizuje relacje między obiektami i klastrami na różnych poziomach szczegółowości.

Wady grupowania hierarchicznego:

• Wysoki koszt obliczeniowy:
  • Metoda jest czasochłonna dla dużych zbiorów danych.
• Nieodwracalność:
  • Raz połączone klastery nie mogą być ponownie podzielone w metodzie aglomeracyjnej.
• Wrażliwość na szum i wartości odstające:
  • Odległości między obiektami mogą być zakłócone przez punkty odstające.

Zastosowania:

1. Taksonomia biologiczna:
   • Organizowanie gatunków w hierarchie na podstawie cech biologicznych.
2. Analiza tekstów:
   • Grupowanie dokumentów w hierarchiczne kategorie tematyczne.
3. Przetwarzanie obrazu:
   • Segmentacja obrazu poprzez grupowanie pikseli.
4. Marketing:
   • Segmentacja klientów na podstawie ich zachowań zakupowych.

Przykład działania:

Załóżmy zbiór danych: \((A, B, C, D)\) i ich odległości:

• \(d(A, B) = 2\), \(d(A, C) = 6\), \(d(A, D) = 10\)
• \(d(B, C) = 5\), \(d(B, D) = 9\)
• \(d(C, D) = 4\)

Proces aglomeracyjny:

1. Połącz najbliższe punkty \(A\) i \(B\) (\(d = 2\)).
2. Utwórz nowy klaster \((AB)\) i oblicz jego odległości od pozostałych punktów.
3. Powtarzaj proces, aż wszystkie punkty znajdą się w jednym klastrze.

Rezultat: Dendrogram pokazujący hierarchię klastrów, z możliwością przecięcia go na wybranej wysokości, aby określić liczbę klastrów.

Grupowanie hierarchiczne to skuteczna metoda analizy danych, szczególnie w przypadkach, gdy zależy nam na wizualizacji relacji między danymi i ich hierarchicznej strukturze.