05 · Bez nadzoru · 5 min czytania · aktualizacja 11 października 2026

Jak działa klasteryzacja spektralna i dlaczego rozdziela półksiężyce, których nie rozdzieli k-średnich?

Co to jest

Klasteryzacja spektralna dzieli dane na grupy, patrząc nie na same współrzędne punktów, tylko na graf ich podobieństw. Każdy punkt to wierzchołek, a krawędź łączy punkty bliskie sobie — z wagą tym większą, im są bliżej. Dobra grupa to fragment grafu, wewnątrz którego krawędzi jest dużo, a na zewnątrz mało.

Szukanie najlepszego cięcia grafu jest trudne obliczeniowo. Metoda spektralna zastępuje je zadaniem łatwym: liczy kilka wektorów własnych macierzy opisującej graf (laplasjanu), traktuje je jako nowe współrzędne punktów i dopiero w tej nowej przestrzeni uruchamia zwykłe k-średnich. Nazwa pochodzi od widma, czyli zbioru wartości własnych.

Mechanizm — dlaczego tak działa

Krok pierwszy: macierz podobieństw W. Dwa typowe wybory to jądro RBF, w_ij = exp(−γ · ‖x_i − x_j‖²), i graf k najbliższych sąsiadów, w którym w_ij = 1, gdy jeden punkt jest wśród k najbliższych drugiego. Parametr γ albo k decyduje, co znaczy „blisko”.

Krok drugi: laplasjan L = D − W, gdzie D to macierz diagonalna stopni (sum wag w wierszach). Częściej używa się wersji znormalizowanej, I − D^(−1/2) W D^(−1/2). Kluczowa własność: dla dowolnego wektora f wyrażenie fᵀ(D − W)f to połowa sumy w_ij · (f_i − f_j)² po wszystkich parach. Jest małe, gdy f przypisuje podobne wartości punktom połączonym silnymi krawędziami. Najmniejsza wartość własna wynosi 0, a liczba zerowych wartości własnych równa się liczbie spójnych składowych grafu.

Krok trzeci: k wektorów własnych o najmniejszych wartościach własnych tworzy macierz n × k; jej wiersze to nowe współrzędne punktów. Gdy graf składa się z k rozłącznych części, te wektory są stałe na każdej części (w wersji znormalizowanej — po przeskalowaniu wierszy), więc punkty z jednej części lądują w jednym miejscu, a k-średnich nie ma czego mylić. Gdy części są połączone słabymi krawędziami, wektory zmieniają się tylko trochę — to uzasadnienie z teorii zaburzeń (Ng, Jordan i Weiss, 2001). Z kolei Shi i Malik (2000) pokazali, że ten sam rachunek rozwiązuje złagodzoną wersję znormalizowanego cięcia grafu.

Dlaczego rozdziela kształty niewypukłe? Bo graf sąsiedztwa łączy punkty łańcuchem bliskich par. Półksiężyc to jedna spójna ścieżka, nawet jeśli jego końce leżą daleko od siebie, a punkty z drugiego półksiężyca, choć bliżej w linii prostej, nie mają z nim krawędzi. K-średnich patrzy tylko na odległość od środka, więc tnie prostą linią.

Wybór liczby grup: luka własna (eigengap). Jeśli pierwsze k wartości własnych jest bliskich zera, a k + 1-sza wyraźnie większa, k jest dobrym kandydatem.

Na przykładzie

Dwa sztuczne zbiory po 500 punktów: półksiężyce i dwa współśrodkowe pierścienie. Zgodność z prawdziwym podziałem mierzymy skorygowanym indeksem Randa (ARI, 1 to pełna zgodność, 0 to poziom przypadku).

Na półksiężycach k-średnich ma ARI 0,257, klasteryzacja spektralna na grafie 10 sąsiadów 1,000, a DBSCAN przy ε od 0,15 do 0,3 również 1,000. Na pierścieniach k-średnich ma −0,002 (zero informacji), spektralna 1,000, DBSCAN 1,000 przy ε 0,15–0,2, ale przy ε = 0,1 rozbija dane na 7 grup (0,583), a przy 0,3 łączy w jedną.

Luka własna działa tu wzorcowo. Na grafie 10 sąsiadów pierwsze wartości własne znormalizowanego laplasjanu półksiężyców to 0; 0; 0,00101 — dwie zerowe, bo graf rozpadł się na dokładnie dwie części. Przy jądrze RBF z γ = 30 graf jest spójny, ale luka i tak jest wyraźna: 0; 0,00025; 0,00931, trzecia wartość 37 razy większa od drugiej.

Wrażliwość na parametr jest duża. Domyślne w scikit-learn γ = 1 daje na półksiężycach ARI 0,290, a na pierścieniach −0,002 — tyle co k-średnich. Dopiero γ = 10 daje 0,906 na półksiężycach, a γ od 30 do 100 — 1,000 na obu zbiorach. Graf sąsiadów jest łatwiejszy w strojeniu, ale też ma granice: na półksiężycach k = 3 dzieli graf na 6 kawałków i ARI spada do 0,000, k = 5 daje 0,134, k od 10 do 50 — 1,000, a k = 100 łączy półksiężyce mostami (0,608). Na pierścieniach k = 50 i 100 łączy oba pierścienie w jeden spójny graf i ARI spada do −0,002.

Teraz uczciwy test na danych rzeczywistych. Irysy (150 kwiatów, 4 standaryzowane pomiary, 3 gatunki): k-średnich 0,620, spektralna z grafem 10 sąsiadów 0,646, z 5 sąsiadami tylko 0,470. Różnica w najlepszym razie niewielka. Luka własna podpowiada tu k = 2 (wartości 0; 0,00249; 0,03866), bo dwa z trzech gatunków tworzą jedną ciągłą chmurę. Na pingwinach Palmer metoda spektralna wypada lepiej: 0,916 wobec 0,793 dla k-średnich, ale i tu graf 10 sąsiadów rozpada się na dwie części (wszystkie 123 pingwiny białobrewe osobno, Adeli i maskowe razem), więc luka znów wskazuje 2 grupy, nie 3.

Dane: Iris (irysy Fishera) Palmer Penguins (pingwiny z Antarktydy)

W praktyce

• W scikit-learn: SpectralClustering(n_clusters=k, affinity="nearest_neighbors", n_neighbors=10). Domyślne affinity="rbf" z γ = 1 bywa złym wyborem, co pokazał przykład; zawsze sprawdź kilka wartości.
• Standaryzuj cechy przed budową grafu — odległość decyduje o krawędziach.
• Liczbę grup oceniaj luką własną, ale traktuj ją jako wskazówkę: na irysach i pingwinach wskazała 2 zamiast 3 gatunków.
• Gdzie to się psuje: zbyt mało sąsiadów (graf rozpada się na wiele kawałków), zbyt dużo albo zbyt małe γ (mosty między grupami), grupy o bardzo różnej gęstości i duże zbiory — pełna macierz podobieństw ma n² elementów, więc przy dziesiątkach tysięcy punktów trzeba grafów rzadkich i przybliżonych solverów (eigen_solver="amg").
• Metoda nie przypisze nowego punktu bez ponownego liczenia — w odróżnieniu od k-średnich nie ma predict.
• Gdy dane są szumne i potrzebujesz etykiety „szum”, DBSCAN albo HDBSCAN bywają prostsze.

Najczęstsze pytania

Czym klasteryzacja spektralna różni się od k-średnich?

K-średnich grupuje punkty według odległości od środków, więc znajduje grupy wypukłe, zbliżone do kul. Metoda spektralna najpierw przenosi punkty do przestrzeni wektorów własnych grafu sąsiedztwa, gdzie łańcuch bliskich punktów skupia się w jednym miejscu, i dopiero tam używa k-średnich.

Jak wybrać liczbę grup w klasteryzacji spektralnej?

Policz kilka najmniejszych wartości własnych znormalizowanego laplasjanu i szukaj pierwszej dużej luki. Sprawdź też, czy wynik jest stabilny dla kilku wartości `n_neighbors` lub γ. Luka mówi o strukturze grafu, nie o etykietach, które masz w głowie.

Czy klasteryzacja spektralna jest zawsze lepsza od k-średnich?

Nie. Na półksiężycach i pierścieniach wygrywa wyraźnie, na irysach daje 0,646 wobec 0,620, a przy źle dobranym parametrze wypada gorzej. Kosztuje też więcej obliczeń i ma parametr, który trzeba stroić.

Co ma klasteryzacja spektralna wspólnego z cięciem grafu?

Szukanie podziału, który przecina mało krawędzi przy zrównoważonych rozmiarach grup (znormalizowane cięcie), jest trudne obliczeniowo. Po zastąpieniu etykiet 0/1 dowolnymi liczbami rozwiązaniem staje się wektor własny laplasjanu — to właśnie pokazali Shi i Malik.

Źródła

Zobacz też