Spektral Kümeleme
Spectral Clustering via Graph Laplacian Eigenvectors (Ng–Jordan–Weiss Algorithm) · Ayrıca şöyle bilinir: NJW spectral clustering, graph Laplacian clustering, normalized spectral clustering, spectral graph clustering, SC
Spektral Kümeleme, 2002 yılında Ng, Jordan ve Weiss tarafından biçimlendirilen, graf tabanlı bir denetimsiz öğrenme algoritmasıdır. Bu algoritma, k-means uygulamadan önce benzerlik grafının Laplacian'ından türetilen düşük boyutlu bir özuzaya veri noktalarını eşler. Bu spektral gömme, Öklid mesafesi tabanlı yöntemlerin sürekli olarak ayırmakta başarısız olduğu halka, hilal, iç içe geçmiş sarmal gibi keyfi şekilli kümeleri kurtarmayı mümkün kılar.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
+4 tane daha
Ne zaman kullanılır
Spektral Kümeleme, kümelerin dışbükey olmadığı, doğrusal olarak ayrılamadığı veya Öklid bölümlendirme yöntemlerinin tespit edemediği ince köprülerle bağlı olduğu verilerde iyi çalışır — halka şeklindeki kümeler, iç içe geçmiş sarmallar ve görüntü segmentleri yaygın örneklerdir. Çiftler arası benzerliğin anlamlı bir şekilde hesaplanabildiği (ham özellikler üzerinde bir çekirdekten veya önceden sağlanan bir etkinlik matrisinden) ve küme sayısı k'nin bilindiği veya özdeğer boşluğu sezgisel yöntemiyle tahmin edilebildiği durumlarda uygundur. Yöntem, küme şekilleri üzerinde herhangi bir dağılımsal varsayım gerektirmez. Pratik sınırlamalar arasında, noktaların sayısına göre karesel bellek (tam etkinlik matrisi için) ve özdeğer ayrışımı için kübik zaman yer alır, bu da standart formülasyonu yaklaşık 10.000 noktanın ötesinde pahalı hale getirir. Yaklaşık yöntemler (Nystrom, seyrek graflar, rastgeleleştirilmiş SVD), erişimini daha büyük veri kümelerine genişletir.
Güçlü yönler & sınırlılıklar
- Dışbükey olmayan, doğrusal olarak ayrılamayan veya k-means ve Gauss karışım modellerini alt eden ince köprülerle bağlı keyfi şekilli kümeleri tespit eder.
- Sadece Öklid mesafelerine değil, herhangi bir çift benzerlik matrisine göre çalışabilir, bu da onu graflar, dizeler ve diğer yapılandırılmış verilere uygulanabilir hale getirir.
- Özdeğer boşluğu sezgisel yöntemi, küme sayısı k'yi seçmek için ilkeli, veriye dayalı bir rehber sağlar.
- Graf bağlantısı ve cebirsel bağlantı özdeğeri üzerine Fiedler'in 1973 tarihli çalışmalarına dayanan zengin spektral graf teorisine dayanır, bu da yakınsama ve küme kalitesinin biçimsel analizini sağlar.
- Kavramsal olarak basittir ve standart doğrusal cebir kütüphaneleri kullanılarak kolayca uygulanabilir.
- Tam n-by-n etkinlik matrisini oluşturmak, özdeğer ayrışımı için O(n^2) bellek ve O(n^3) zaman gerektirir, bu da kaba algoritmayı büyük veri kümeleri için uygulanamaz hale getirir.
- Sonuçlar, çekirdek bant genişliği sigma ve graf oluşturma stratejisinin seçimine duyarlıdır; kötü seçimler kümeleri birleştirebilir veya bölebilir.
- Spektral gömmedeki k-means başlatma rastgelelik içerir; farklı çalıştırmalar farklı bölümlendirmeler verebilir.
- Dikkatli çekirdek seçimi olmadan çok yüksek boyutlu özellik uzaylarına zarifçe ölçeklenmez.
- Sadece küme etiketleri sağlar; üretken bir model sunmaz ve yeni noktalar için doğal bir örnek dışı genişletme sunmaz.
SSS
Küme sayısı k'yi nasıl seçerim?
Özdeğer boşluğu sezgisel yöntemi standart rehberdir: normalize edilmiş Laplacian'ın özdeğerlerini artan sırada hesaplayın ve ardışık özdeğerler arasındaki en büyük boşluğu arayın. Bu boşluğun oluştuğu indeks, doğal küme sayısını önerir. Özdeğer boşluğu belirsiz olduğunda, kararlılık tabanlı yaklaşımlar — birkaç k değeri için algoritmayı çalıştırmak ve küme atamalarını pertürbasyonlar boyunca karşılaştırmak — yardımcı olabilir.
Gauss çekirdek bant genişliği sigma'yı nasıl ayarlamalıyım?
Yaygın bir sezgisel yöntem, veri kümesindeki çift mesafelerin medyanı veya her noktaya yerel bir bant genişliği atayan bir en yakın komşu kendi kendine ayarlama şemasıdır (Zelnik-Manor & Perona, 2004). Pratikte, sigma, sonuçta ortaya çıkan etkinlik grafının bağlantısını inceleyerek doğrulanmalıdır: her noktanın en az birkaç yüksek ağırlıklı komşusu olmalı ve graf izole bileşenlere parçalanmamalıdır.
Satır normalleştirme adımı neden gereklidir?
Laplacian'ın özvektörleri ölçekte önemli ölçüde farklılık gösterebilir. Gömme matrisinin her satırını birim uzunluğa göre normalize etmeden, k-means adımı büyük büyüklüklere sahip özvektörler tarafından domine edilebilir ve daha küçük büyüklükteki bilgilendirici bileşenleri göz ardı edebilir. Ng, Jordan ve Weiss tarafından tanıtılan satır normalleştirmesi, tüm noktaları birim küreye eşleyerek k-means'in büyüklük yerine gömmenin açısal geometrisine yanıt vermesini sağlar.
Spektral kümeleme çok büyük veri kümelerini işleyebilir mi?
Karesel bellek ve O(n^3) özdeğer ayrışım zamanı gerektiren kaba biçiminde değil. Büyük n için standart çözümler şunları içerir: tam bir etkinlik matrisi yerine seyrek bir k-en yakın komşu grafı oluşturmak; alt örnekten özvektörleri tahmin etmek için Nystrom yaklaşımını kullanmak; veya rastgeleleştirilmiş SVD uygulamak. Bu yaklaşık yöntemler, maliyetin bir kısmı karşılığında doğruluğun çoğunu kurtarır.
Kaynaklar
- 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. link ↗
- von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416. DOI: 10.1007/s11222-007-9033-z ↗
- Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905. DOI: 10.1109/34.868688 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Spectral Clustering via Graph Laplacian Eigenvectors (Ng–Jordan–Weiss Algorithm). ScholarGate. https://scholargate.app/tr/machine-learning/spectral-clustering
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Hiyerarşik KümelemeMakine öğrenmesi↔ karşılaştır
- K-ortalama KümelemeMakine öğrenmesi↔ karşılaştır
- Temel Bileşen AnaliziMakine öğrenmesi↔ karşılaştır
- t-SNEMakine öğrenmesi↔ karşılaştır