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.

Üç 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.

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.