Spektral Kümeleme
- Ortaya koyan
- Ng, A. Y.; Jordan, M. I.; Weiss, Y.
- Yıl
- 2002
- Tür
- Graph-based clustering (spectral method)
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
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.
Yöntemin mantığı
Standart k-means, uzayı düz çizgi mesafesine göre böler, bu nedenle yalnızca dışbükey, kabaca küresel yığınları bulabilir. Spektral Kümeleme, veriyi öncelikle bir ağ olarak düşünerek bu sorunu aşar: her nokta bir düğümdür ve düğümler arasındaki kenarlar, iki noktanın ne kadar benzer olduğunu yansıtan bir ağırlık taşır. Kümeler, ağın içten yoğun bir şekilde bağlı ancak geri kalanına gevşek bir şekilde bağlı bölgelerine karşılık gelir. Graf Laplacian matrisi bu bağlantı yapısını kodlar ve en küçük özvektörleri, veriyi, iyi ayrılmış kümelerin orijinal uzayda birbirine dolanmış olsalar bile birbirinden uzaklaşmasını sağlayan pürüzsüz bir koordinat sistemi gibi davranır. O yeni koordinat sistemindeki basit bir k-means adımı daha sonra onları temiz bir şekilde ayırır.
Tarih
Spektral kümelemenin teorik temelleri, Fiedler'in 1973'teki graf bağlantısı ve cebirsel bağlantı özdeğeri üzerine çalışmalarına dayanmaktadır. Shi ve Malik (2000), görüntü segmentasyonu için normalize edilmiş kesme kriterleri aracılığıyla yaklaşımı bilgisayar görüşüne taşıdı. Ng, Jordan ve Weiss (2002), NIPS'te yöntemin ne zaman ve neden işe yaradığını açıklayan bir pertürbasyon teorik analiziyle birlikte temiz, genel amaçlı bir algoritma sundu. Von Luxburg'un 2007'deki Statistics and Computing dergisindeki öğreticisi, rakip formülasyonları birleştirdi, Laplacian normalizasyonunun rolünü netleştirdi ve uygulayıcılar için standart referans haline geldi. Spektral kümeleme artık makine öğrenmesi müfredatında merkezi bir yer tutmaktadır ve ölçeklenebilir yaklaşımlar, sağlam çekirdekler ve graflar ile manifoldlara uzantılar üzerine devam eden çalışmalarla aktif bir araştırma konusu olmaya devam etmektedir.
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.
Sınırlar ve dikkat edilmesi gerekenler
- 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.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- 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.
Uygulama alanları
- Görüntü segmentasyonu: piksel düzeyinde özellik benzerliğini kullanarak algısal olarak tutarlı bölgelere pikselleri veya süperpikselleri bölme.
- Özellik vektörleri yerine çiftler arası bağlantının yapıyı tanımladığı sosyal ve biyolojik ağlarda topluluk tespiti.
- Biyoenformatik: ifade kümelerinin gen uzayında nadiren dışbükey olduğu ifade profili benzerliğine göre genleri veya proteinleri gruplandırma.
- Doğal dil işleme: anlamsal benzerlik çekirdekleri kullanarak belge veya cümle kümelemesi.
- Bilgisayarlı görü: küme sınırlarının düzensiz olduğu hareket segmentasyonu ve nokta bulutu bölümlendirmesi.
- Keşifsel veri analizi: onaylayıcı yöntemler uygulamadan önce belirgin olmayan küme yapısını ortaya çıkarma.
Nasıl çalışır?
Nasıl çalışır?
Veriden bir çift benzerlik (etkinlik) matrisi W oluşturulur. En yaygın seçim, yakın çiftlere yüksek ağırlık ve uzak olanlara sıfıra yakın ağırlık atayan Gauss (RBF) çekirdeğidir. Bant genişliği parametresi sigma, benzerliğin mesafeyle ne kadar hızlı azaldığını kontrol eder; bunu iyi seçmek kritiktir. Alternatif olarak, büyük veri kümelerinde daha seyrek temsiller için k-en yakın komşu grafı kullanılabilir.
Formül
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)D'nin derece matrisi, i'inci girdisi W'nin i'inci satırının toplamı olan köşegen matristir. W ve D'den normalize edilmiş (simetrik) graf Laplacian'ı L_sym oluşturulur. Bu matris, benzerlik grafının tam bağlantı yapısını yakalar; özdeğer spektrumu, verinin kaç doğal küme içerdiğini ve ne kadar temiz ayrıldıklarını ortaya çıkarır.
Formül
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}L_sym'nin k en küçük özdeğerine karşılık gelen k özvektörü hesaplanır. Bu özvektörler, her veri noktası için bir satırı olan gömme matrisi U'nun sütunlarını oluşturur. Bu k-boyutlu spektral uzayda, aynı kümeye ait noktalar, orijinal özellik uzayında iç içe geçmiş olsalar bile birbirine yakın çekilir.
Formül
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]U'nun her satırı, gömülü noktaları birim hiperküreye yansıtmak için Öklid normuna göre bölünür. Ng, Jordan ve Weiss tarafından tanıtılan bu normalleştirme, özvektörler arasındaki yapay ölçek farklılıklarını ortadan kaldırır ve sonraki k-means adımının büyüklük yerine gömmenin açısal yapısına odaklanmasını sağlar.
Formül
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}Normalize edilmiş gömme matrisi T'nin satırlarına standart k-means kümelemesi uygulanır. Spektral gömme küme geometrisini zaten çözdüğü için, k-means anlamlı bölümlendirmeler bulur, hatta dışbükey olmayan küme şekilleri için bile. Küme etiketleri daha sonra orijinal veri noktalarına geri eşlenir.
Sık yapılan hatalar
- İlkesel çapraz doğrulama veya kendi kendine ayarlama olmadan sigma seçimi; çok küçük bir bant genişliği bağlantısız bir graf oluştururken, çok büyük bir bant genişliği farklı kümeleri birleştirir.
- Etkinlik matrisi satırlarını k-means'ten önce normalize etmeyi ihmal etmek (Ng ve ark.'nın satır normalleştirme adımı kararlılık için esastır).
- Özdeğer boşluğunu göz ardı etmek: özdeğer spektrumunu incelemeden sabit bir k kullanmak genellikle alt veya aşırı segmentasyona yol açar.
- Tam algoritmayı, yaklaşık veya seyrek bir varyanta geçmeden on binlerce noktalı veri kümelerine uygulamak.
- Normalleştirilmemiş (L = D - W) ve normalize edilmiş (L_sym, L_rw) Laplacian'ları karıştırmak, bu da küme atamalarını önemli ölçüde değiştirebilir.
Sık sorulan sorular
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.
İlgili yöntemler
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.
Yayın kaynağını açKopyalandı.von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.
DOI kaynağını açKopyalandı.Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.
DOI kaynağını açKopyalandı.