Spectral Clustering (Spektral Kümeleme)

#SpektralKumeleme #MakineOgrenimi #Algoritma #GrafTeori

Veri benzerlik grafiğinin Laplacian matrisini özdeğer ayrışımına tabi tutarak karmaşık ve iç içe geçmiş kümeleri tespit eden grafik teorisi tabanlı kümeleme algoritması.

Spektral kümeleme, geleneksel mesafe tabanlı yöntemlerin yetersiz kaldığı karmaşık ve iç içe geçmiş veri yapılarını tespit edebilen, grafik teorisi ile lineer cebiri birleştiren bir kümeleme algoritmasıdır. Temel fikri, veri noktaları arasındaki benzerlik ilişkilerini bir grafik olarak modellemek ve bu grafiğin Laplacian matrisinin özvektörlerini düşük boyutlu kümeleme için kullanmaktır. Algoritmanın kökeni, 1970'lerin grafik kesim (graph partitioning) problemlerine dayanır; ancak makine öğrenmesine yönelik modern biçimlenmesi Shi ve Malik'in 2000 tarihli "Normalized Cuts and Image Segmentation" çalışmasıyla ivme kazandı. Ng, Jordan ve Weiss ise 2002'de yöntemi yaygın kullanılan standart hale getirdi. Spektral kümeleme üç temel aşamada çalışır. İlk aşamada her veri noktasını bir düğüm, iki nokta arasındaki benzerliği ise (Gauss/RBF çekirdeği ya da k-NN yöntemiyle hesaplanmış) bir kenar ağırlığı olarak tanımlayan W benzerlik matrisi oluşturulur. İkinci aşamada grafik Laplacian'ı (L = D − W veya normalize biçimi) hesaplanır ve ilk k özvektörü çıkarılır; bu özvektörler orijinal verinin küme yapısını koruyarak düşük boyutlu uzayda temsil eder. Üçüncü aşamada bu özvektör uzayındaki noktalar K-Means ile kümelenir. Bu son adım, doğrusal olmayan sınırlara sahip kümelerin bile ayrılabilir hale gelmesini sağlar. Algoritmanın en önemli avantajı şekil bağımsızlığıdır: ay biçimli (crescent), halka (ring) veya iç içe geçmiş spiral veri kümeleri gibi K-Means'in başarısız olduğu durumlarda üstün performans gösterir. Görüntü bölütleme, sosyal ağ topluluk tespiti, biyoinformatik gen ifadesi analizi ve belge kümeleme başlıca uygulama alanları arasındadır. scikit-learn kütüphanesindeki SpectralClustering sınıfı Python ekosisteminde standart uygulamayı sunar. Temel sınırlılık ölçeklenebilirlik sorunudur: Laplacian özdeğer ayrışımının O(n³) zaman karmaşıklığı büyük veri kümelerinde hesaplama yükünü artırır. Bu sorunu gidermek için Nyström yaklaşımı ve Landmark-based Spectral Clustering gibi yaklaşık yöntemler geliştirilmiştir. Küme sayısı k'nın önceden belirlenmesi zorunludur; eigengap heuristiği ile özvektörler arasındaki en büyük boşluğa bakarak k tahmini yapılabilir. Modern derin öğrenme alanında spektral yöntemler grafik sinir ağlarının (GNN) teorik temelini oluşturmaktadır: GCN (Graph Convolutional Network), ChebNet ve Graph Attention Network mimarileri doğrudan spektral grafik teorisinden türemektedir.

Spektral Kümeleme Nedir?

Spektral kümeleme, geleneksel mesafe tabanlı yöntemlerin yetersiz kaldığı karmaşık ve iç içe geçmiş veri yapılarını tespit edebilen, grafik teorisi ile lineer cebiri birleştiren bir kümeleme algoritmasıdır. Temel fikri, veri noktaları arasındaki benzerlik ilişkilerini bir grafik olarak modellemek ve bu grafiğin Laplacian matrisinin özvektörlerini düşük boyutlu kümeleme için kullanmaktır. Algoritmanın kökeni 1970 lerin grafik kesim (graph partitioning) problemlerine dayanır; makine öğrenmesine yönelik modern biçimlenmesi ise Shi ve Malik in 2000 tarihli Normalized Cuts and Image Segmentation çalışmasıyla ivme kazandı. Ng, Jordan ve Weiss 2002 de yöntemi yaygın kullanılan standart hale getirdi.

Üç Aşamalı Çalışma Prensibi

  • check_circle Benzerlik Grafiği Oluşturma: Her veri noktası bir düğüm, iki nokta arasındaki benzerlik ise (Gauss/RBF çekirdeği veya k-NN yöntemiyle hesaplanmış) bir kenar ağırlığı olarak tanımlanır. Bu adım, verinin geometrik yapısını yakalayan W benzerlik matrisini üretir.
  • check_circle Laplacian Özdeğer Ayrışımı: Normalize grafik Laplacian matrisi (L = D − W veya normalize biçimi) hesaplanır ve ilk k özvektörü çıkarılır. Bu özvektörler, orijinal verinin küme yapısını koruyarak düşük boyutlu uzayda temsil eder.
  • check_circle K-Means ile Kümeleme: Özvektör uzayındaki noktalar standart K-Means algoritmasıyla kümelenir. Bu son adım, doğrusal olmayan sınırlara sahip kümelerin bile birbirinden kolayca ayrılabilir hale gelmesini sağlar.

K-Means ten Farkı ve Avantajları

Spektral kümelemenin en önemli avantajı şekil bağımsızlığıdır: ay biçimli (crescent), halka (ring) veya iç içe geçmiş spiral veri kümeleri gibi K-Means in başarısız olduğu durumlarda üstün performans gösterir. K-Means, kümeleri küresel şekle sahip ve verilerin homojen dağıldığı senaryolarda iyi çalışır; ancak bu varsayım gerçek dünyada sıkça ihlal edilir. Spektral kümeleme, verinin geometrik şekline değil noktalar arasındaki bağlantı yapısına odaklanarak bu kısıtı aşar. Herhangi bir çift benzerlik fonksiyonu kullanılabilir; öklid mesafesine bağımlılık yoktur.

Uygulama Alanları ve Araçlar

Spektral kümeleme; görüntü bölütleme (piksel benzerlik grafikleriyle nesne sınırları tespiti), sosyal ağ topluluk analizi (kullanıcılar arası etkileşim grafikleri), biyoinformatik gen ifadesi analizi ve belge kümeleme alanlarında yaygın kullanılmaktadır. Python ekosisteminde scikit-learn kütüphanesinin SpectralClustering sınıfı standart uygulamayı sunar; affinity_matrix parametresi özelleştirilmiş benzerlik matrislerini destekler. Büyük veri kümelerinde Nyström yaklaşımı veya seyrek k-NN grafikleriyle hesaplama maliyeti önemli ölçüde düşürülebilir.

Grafik Sinir Ağlarıyla Bağlantısı

Spektral kümeleme, modern grafik sinir ağlarının (GNN) teorik temelini oluşturmaktadır. Kipf ve Welling in 2017 tarihli GCN (Graph Convolutional Network) çalışması, spektral konvolüsyon operatörünü komşuluk özetlemesi olarak basitleştirerek grafik üzerinde derin öğrenmeye kapı araladı. Defferrard ve arkadaşlarının ChebNet mimarisi Chebyshev polinomlarını, Graph Attention Network (GAT) ise öz-dikkat mekanizmasını bu spektral temel üzerine inşa etmiştir. Bu bağlantı, kümeleme ve sınıflandırma görevlerinde grafik yapılı verilerle çalışmak için spektral kümeleme anlayışını temel bir ön koşul haline getirmektedir.

Sık Sorulan Sorular

  • check_circle Spektral kümeleme kaç küme (k) kullanılacağını nasıl belirler? Küme sayısı k önceden belirlenmeli veya eigengap heuristiği kullanılmalıdır: özdeğerler küçükten büyüğe sıralandığında ardışık iki özdeğer arasındaki en büyük boşluk uygun k sayısını gösterir.
  • check_circle K-Means veya DBSCAN yerine neden spektral kümeleme tercih edilir? Verinin geometrik şekli küresel veya konveks olmadığında (ay, halka, sarmal yapılar) spektral kümeleme K-Means e üstündür. DBSCAN gürültüye dayanıklıdır ancak düzensiz yoğunluklu grafiklerde spektral daha iyi ayrışım sağlar.
  • check_circle Büyük veri kümelerinde spektral kümeleme uygulanabilir mi? O(n³) özdeğer ayrışımı yerine Nyström yaklaşımı veya Landmark-based Spectral Clustering kullanılır. Grafiğin k-NN yapısıyla seyrekleştirilmesi de hesaplama yükünü önemli ölçüde azaltır.
  • check_circle Spektral kümeleme hangi affinite fonksiyonunu kullanır? Varsayılan olarak radial basis function (RBF/Gauss) çekirdeği kullanılır. scikit-learn da nearest_neighbors seçeneği de mevcuttur; ham benzerlik matrisi precomputed parametresiyle aktarılabilir.
  • check_circle Spektral kümeleme ile GNN arasında nasıl bir ilişki vardır? GCN, ChebNet ve GAT gibi grafik sinir ağı mimarileri doğrudan spektral kümelemenin matematiksel çerçevesinden türemiştir. Bu nedenle spektral kümeleme, grafik tabanlı derin öğrenmeyi anlamanın doğal başlangıç noktasıdır.