Klastrowanie spektralne
- Autor metody
- Ng, A. Y.; Jordan, M. I.; Weiss, Y.
- Rok
- 2002
- Typ
- Graph-based clustering (spectral method)
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Klastrowanie spektralne to algorytm uczenia nienadzorowanego oparty na grafach, sformalizowany przez Ng, Jordana i Weissa w 2002 roku, który mapuje punkty danych do niskowymiarowej przestrzeni własnej pochodzącej z laplasjanu grafu podobieństwa przed zastosowaniem k-średnich.
To osadzenie spektralne umożliwia odzyskanie klastrów o dowolnym kształcie — pierścieni, półksiężyców, przeplatających się spirali — których metody oparte na odległości euklidesowej konsekwentnie nie potrafią rozdzielić.
Intuicja stojąca za metodą
Standardowe k-średnich dzieli przestrzeń na podstawie odległości w linii prostej, więc może znajdować tylko wypukłe, w przybliżeniu kuliste skupiska. Klastrowanie spektralne omija ten problem, najpierw traktując dane jako sieć: każdy punkt jest węzłem, a krawędzie między węzłami mają wagę odzwierciedlającą podobieństwo między dwoma punktami. Klastry odpowiadają regionom sieci, które są gęsto połączone wewnętrznie, ale luźno połączone z resztą. Macierz laplasjanu grafu koduje tę strukturę połączeń, a jej najmniejsze wektory własne działają jak gładki system współrzędnych, który rozciąga dane tak, że dobrze rozdzielone klastry znajdują się daleko od siebie, nawet jeśli były splątane w oryginalnej przestrzeni. Prosty krok k-średnich w tym nowym systemie współrzędnych następnie czysto je rozdziela.
Historia
Podstawy teoretyczne klastrowania spektralnego sięgają pracy Fiedlera z 1973 roku nad spójnością grafów i własną wartością algebraiczną spójności. Shi i Malik (2000) wprowadzili podejście do wizji komputerowej poprzez swoje kryterium znormalizowanych cięć dla segmentacji obrazu. Ng, Jordan i Weiss (2002) przedstawili czysty, ogólnego przeznaczenia algorytm na NIPS — ten najczęściej cytowany — wraz z analizą perturbacyjną wyjaśniającą, kiedy i dlaczego metoda działa. Tutorial Von Luxburga z 2007 roku w Statistics and Computing ujednolicił konkurencyjne sformułowania, wyjaśnił rolę normalizacji laplasjanu i stał się standardowym odniesieniem dla praktyków. Klastrowanie spektralne zajmuje obecnie centralne miejsce w programie nauczania uczenia maszynowego i pozostaje aktywnym tematem badawczym, z trwającymi pracami nad skalowalnymi aproksymacjami, odpornymi jądrami i rozszerzeniami na grafy i rozmaitości.
Kiedy stosować
Klastrowanie spektralne jest dobrze dopasowane, gdy klastry w danych są nie-wypukłe, nieliniowo separowalne lub połączone cienkimi mostkami, których metody podziału euklidesowego nie potrafią wykryć — typowe przykłady obejmują klastry w kształcie pierścienia, przeplatane spirale i segmenty obrazu. Jest odpowiednie, gdy podobieństwo parach między punktami można sensownie obliczyć (albo z jądra na surowych cechach, albo z predefiniowanej macierzy afinityczności), i gdy liczba klastrów k jest znana lub można ją oszacować za pomocą heurystyki eigengapu. Metoda nie wymaga założeń dystrybucyjnych dotyczących kształtów klastrów. Praktyczne ograniczenia obejmują kwadratową pamięć w stosunku do liczby punktów (dla pełnej macierzy afinityczności) i sześcienną złożoność czasową dla rozkładu na wartości własne, co czyni standardową formułę kosztowną dla więcej niż około 10 000 punktów. Metody przybliżone (Nystrom, grafy rzadkie, losowe SVD) rozszerzają jej zasięg na większe zbiory danych.
Ograniczenia i uwagi
- Konstrukcja pełnej macierzy afinityczności n na n wymaga pamięci O(n^2) i czasu O(n^3) na rozkład na wartości własne, co czyni naiwny algorytm niewykonalnym dla dużych zbiorów danych.
- Wyniki są wrażliwe na wybór szerokości pasma jądra sigma i strategii konstrukcji grafu; złe wybory mogą połączyć lub rozfragmentować klastry.
- Inicjalizacja k-średnich w osadzeniu spektralnym wprowadza losowość; różne przebiegi mogą dawać różne podziały.
- Nie skaluje się dobrze do przestrzeni cech o bardzo wysokich wymiarach bez starannego wyboru jądra.
- Dostarcza jedynie etykiety klastrów; nie oferuje modelu generatywnego ani naturalnego rozszerzenia poza próbkę dla nowych punktów.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Wykrywa klastry o dowolnym kształcie, w tym konfiguracje nie-wypukłe i nieliniowo separowalne, które pokonują k-średnich i modele mieszanin Gaussa.
- Może działać na dowolnej macierzy podobieństwa parach, nie tylko na odległościach euklidesowych, co czyni go stosowalnym do grafów, ciągów znaków i innych danych strukturalnych.
- Heurystyka eigengapu zapewnia zasadniczy, oparty na danych przewodnik do wyboru liczby klastrów k.
- Ugruntowane w bogatej teorii grafów spektralnych, umożliwiając formalną analizę zbieżności i jakości klastrów.
- Koncepcyjnie proste i łatwe do zaimplementowania przy użyciu standardowych bibliotek algebry liniowej.
Zastosowania
- Segmentacja obrazu: podział pikseli lub superpikseli na spójne percepcyjnie regiony przy użyciu podobieństwa cech na poziomie pikseli.
- Wykrywanie społeczności w sieciach społecznych i biologicznych, gdzie struktura definiuje połączenie parach, a nie wektory cech.
- Bioinformatyka: grupowanie genów lub białek według podobieństwa profili ekspresji, gdzie klastry ekspresji rzadko są wypukłe w przestrzeni genów.
- Przetwarzanie języka naturalnego: klastrowanie dokumentów lub zdań przy użyciu semantycznych jąder podobieństwa.
- Wizja komputerowa: segmentacja ruchu i podział chmur punktów, gdzie granice klastrów są nieregularne.
- Eksploracyjna analiza danych: ujawnianie nieoczywistej struktury klastrów przed zastosowaniem metod potwierdzających.
Jak to działa
Jak to działa
Konstruowana jest macierz podobieństwa (afinityczności) parach W. Najczęstszym wyborem jest jądro Gaussa (RBF), które przypisuje dużą wagę bliskim parom i wagę bliską zeru odległym parom. Parametr szerokości pasma sigma kontroluje, jak szybko podobieństwo maleje wraz z odległością; jego właściwy wybór jest kluczowy. Alternatywnie, można użyć grafu k-najbliższych sąsiadów dla rzadszych reprezentacji na dużych zbiorach danych.
Wzór
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)Macierz stopni D jest macierzą diagonalną, której i-ty element jest sumą i-tego wiersza W. Z W i D tworzony jest znormalizowany (symetryczny) laplasjan grafu L_sym. Ta macierz zawiera pełną strukturę połączeń grafu podobieństwa; jej widmo wartości własnych ujawnia, ile naturalnych klastrów zawiera dane i jak czysto są one rozdzielone.
Wzór
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}Obliczane są k wektorów własnych odpowiadających k najmniejszym wartościom własnym L_sym. Wektory te tworzą kolumny macierzy osadzenia U, która ma jeden wiersz na punkt danych. W tej k-wymiarowej przestrzeni spektralnej punkty należące do tego samego klastra są przyciągane blisko siebie, nawet jeśli były przeplatane w oryginalnej przestrzeni cech.
Wzór
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]Każdy wiersz U jest dzielony przez jego normę euklidesową, aby odwzorować osadzone punkty na jednostkową hipersferę. Ta normalizacja, wprowadzona przez Ng, Jordana i Weissa, usuwa pozorne różnice skali między wektorami własnymi i zapewnia, że kolejny krok k-średnich skupia się na kątowej strukturze osadzenia, a nie na wielkości.
Wzór
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}Standardowe klastrowanie k-średnich jest stosowane do wierszy znormalizowanej macierzy osadzenia T. Ponieważ osadzenie spektralne już rozplątało geometrię klastra, k-średnich znajduje znaczące podziały nawet dla nie-wypukłych kształtów klastrów. Etykiety klastrów są następnie mapowane z powrotem do oryginalnych punktów danych.
Częste pułapki
- Wybór sigma bez zasadniczej walidacji krzyżowej lub samonastrajania; szerokość pasma zbyt mała tworzy rozłączony graf, podczas gdy zbyt duża łączy odrębne klastry.
- Zaniedbanie normalizacji wierszy macierzy afinityczności przed k-średnich (krok normalizacji wierszy Ng et al. jest niezbędny dla stabilności).
- Ignorowanie eigengapu: używanie ustalonego k bez analizy widma wartości własnych często prowadzi do niedostatecznej lub nadmiernej segmentacji.
- Stosowanie pełnego algorytmu do zbiorów danych liczących dziesiątki tysięcy punktów bez przełączenia na wariant przybliżony lub rzadki.
- Mylenie laplasjanów nieznormalizowanych (L = D - W) i znormalizowanych (L_sym, L_rw), które mogą znacząco zmienić przypisania klastrów.
Najczęściej zadawane pytania
Jak wybrać liczbę klastrów k?
Heurystyka eigengapu jest standardowym wskazaniem: obliczyć wartości własne znormalizowanego laplasjanu w kolejności rosnącej i poszukać największej luki między kolejnymi wartościami własnymi. Indeks, w którym występuje ta luka, sugeruje naturalną liczbę klastrów. Gdy eigengap jest niejednoznaczny, podejścia oparte na stabilności — uruchamianie algorytmu dla kilku wartości k i porównywanie przypisań klastrów między perturbacjami — mogą pomóc.
Jak ustawić szerokość pasma jądra Gaussa sigma?
Częstą heurystyką jest mediana odległości parach w zbiorze danych lub schemat samonastrajania najbliższych sąsiadów (Zelnik-Manor & Perona, 2004), który przypisuje lokalną szerokość pasma każdemu punktowi. W praktyce sigma powinna być walidowana poprzez analizę spójności wynikowego grafu afinityczności: każdy punkt powinien mieć co najmniej kilku sąsiadów o wysokiej wadze, a graf nie powinien rozpadać się na izolowane komponenty.
Dlaczego krok normalizacji wierszy jest konieczny?
Wektory własne laplasjanu mogą się znacznie różnić skalą. Bez normalizacji każdego wiersza macierzy osadzenia do długości jednostkowej, krok k-średnich może być zdominowany przez wektory własne o dużych magnitudach i ignorować informatywne, ale mniejsze komponenty. Normalizacja wierszy wprowadzona przez Ng, Jordana i Weissa mapuje wszystkie punkty na jednostkową sferę, tak aby k-średnich reagowało na kątową geometrię osadzenia.
Czy klastrowanie spektralne może obsługiwać bardzo duże zbiory danych?
Nie w swojej naiwnej formie, która wymaga pamięci O(n^2) i czasu O(n^3) na rozkład na wartości własne. Dla dużego n, standardowe rozwiązania obejmują: budowanie rzadkiego grafu k-najbliższych sąsiadów zamiast pełnej macierzy afinityczności; użycie aproksymacji Nystroma do oszacowania wektorów własnych z podpróbki; lub zastosowanie losowego SVD. Te metody przybliżone odzyskują większość dokładności przy ułamku kosztów.
Pokrewne metody
Źródła
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856.
Otwórz odnośnik do publikacjiSkopiowano.von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.
Otwórz odnośnik DOISkopiowano.Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.
Otwórz odnośnik DOISkopiowano.