İçeriğe atla
Arama sonuçlarına dön

Yarı denetimli En Yakın Komşular

Ortaya koyan
Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
Yıl
2002 (semi-supervised extension); 1967 (KNN base)
Tür
Semi-supervised classifier / label propagation
Aile
Machine learning

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Yarı denetimli KNN, klasik K-en yakın komşular algoritmasını, küçük bir etiketli kümenin yanı sıra büyük miktarda etiketsiz veriden yararlanacak şekilde genişletir.

Tüm gözlemler üzerinde bir KNN grafiği oluşturarak ve bilinen etiketleri grafın kenarları boyunca yayarak, yöntem her örneğin pahalı manuel etiketlenmesini gerektirmeden etiketsiz noktalar için etiketler çıkarır.

Yöntemin mantığı

Sınıfta sadece avuç içi kadar öğrencinin isim etiketi olduğu ve geri kalanların anonim olduğu bir sınıf hayal edin. Standart KNN, anonim bir öğrenciyi yalnızca yakındaki etiketli komşularına bakarak sınıflandırabilir. Yarı denetimli KNN bunun yerine tüm odayı bir ağ olarak haritalar — her öğrenci en yakın komşularına bağlıdır — ve etiketli öğrencilerden mürekkebin ıslak kağıda yayılması gibi etiketleri dışarı doğru yayar. Ağ, verinin genel yapısını yakaladığı için, etiketler etiketsiz çoğunluğu göz ardı etmek yerine alttaki geometriye saygı duyan ilkeli bir şekilde etiketsiz noktalara ulaşır.

Tarih

KNN grafikleri üzerindeki etiket yayılımı, Vapnik'in transductive SVM'si ve daha önceki graf tabanlı difüzyon fikirleri üzerine inşa edilen Zhu ve Ghahramani tarafından 2002'de sistematikleştirildi. Çerçeve, yarı denetimli öğrenmenin standart referansı olmaya devam eden MIT Press ciltü Semi-Supervised Learning (Chapelle et al., 2006) içinde pekiştirildi. Ölçeklenebilir yaklaşık-KNN kütüphaneleri (FAISS, Annoy) daha sonra milyonlarca noktada yaklaşımı pratik hale getirdi ve yarı denetimli görüntü ve metin sınıflandırması için güçlü bir temel olarak kullanılmaya devam ediyor.

Ne zaman kullanılır?

Küçük bir etiketli kümeniz ve aynı dağılımdan büyük bir etiketsiz havuzunuz olduğunda, veri nispeten düşük boyutlu bir alanda (yaklaşık 50 özellikten az) yaşadığında ve komşu noktaların aynı sınıfa sahip olduğuna inandığınızda yarı denetimli KNN kullanın. Görüntü yaması sınıflandırması, seyrek ek açıklamalarla metin kategorizasyonu ve her örneğin pahalı olduğu tıbbi tarama görevleri için uygundur. Etiketli ve etiketsiz veriler farklı dağılımlardan geldiğinde (kovaryans kayması), özellik uzayı çok yüksek boyutlu olduğunda (KNN grafiği güvenilmez hale gelir), veri kümesi tamamen denetimli KNN'nin zaten yeterli olduğu kadar küçük olduğunda veya sınıf sınırları verinin yerel yoğunluk yapısıyla uyumlu olmadığında bundan kaçının.

Sınırlar ve dikkat edilmesi gerekenler

  • Yaklaşık en yakın komşu yöntemleri kullanılmadıkça, graf oluşturma veri kümesi boyutuna göre karesel olarak ölçeklenir.
  • Mesafe metriklerinin ayırt edici gücünü kaybettiği yüksek boyutlu uzaylarda performans keskin bir şekilde düşer.
  • Etiketli ve etiketsiz verilerin aynı dağılımdan çekildiği varsayılır; kovaryans kayması yöntemi bozar.
  • k, kenar ağırlığı bant genişliği ve yayılım karıştırma parametresinin dikkatli bir şekilde ayarlanmasını gerektirir.
  • Etiket yayılımı, grafın büyük bölümleri boyunca başlangıç etiketleme hatalarını büyütebilir.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Yalnızca etiketli küme ile mümkün olanın ötesinde doğruluğu iyileştirmek için ucuz etiketsiz verilerden yararlanır.
  • Parametrik model varsayımı yok: yalnızca yerel komşuluk geometrisine dayanır.
  • Modifikasyon olmadan çok sınıflı problemleri doğal olarak ele alır.
  • KNN grafiği oluşturma şeffaftır ve denetlenmesi kolaydır.
  • Sınıflar özellik uzayında kompakt, iyi ayrılmış kümeler oluşturduğunda iyi çalışır.

Uygulama alanları

  • Küçük bir etiketli görüntü kümesi ve büyük bir etiketsiz derlem ile görüntü sınıflandırması.
  • Manuel etiketlemenin pahalı olduğu metin ve belge kategorizasyonu.
  • Sınırlı uzman ek açıklamaları ile tıbbi kayıt veya patoloji slaytı sınıflandırması.
  • Yalnızca az sayıda onaylanmış dolandırıcılık vakasının mevcut olduğu durumlarda dolandırıcılık tespiti.
  • Seyrek temel gerçek olaylarla endüstriyel IoT ortamlarında sensör verisi etiketleme.

Nasıl çalışır?

Nasıl çalışır?

1

Hem etiketli hem de etiketsiz tüm gözlemler üzerinde bir graf oluşturulur. Her düğüm bir veri noktasını temsil eder ve yönlü veya yönsüz kenarlar her düğümü özellik uzayındaki k en yakın komşusuna bağlar. k'nin seçimi, etiketlerin ne kadar yerel veya küresel olarak yayılacağını kontrol eder: küçük k yayılımı sıkı tutar; büyük k etiketlerin daha büyük boşlukları aşmasını sağlar.

2

Kenar ağırlıkları, tipik olarak özellik vektörleri arasındaki Öklid mesafesine uygulanan bir Gauss (RBF) çekirdeği aracılığıyla, bağlı düğümler arasındaki benzerlik gücünü yakalar. Bir bant genişliği parametresi sigma, benzerliğin mesafeyle ne kadar hızlı azaldığını kontrol eder. Daha güçlü kenarlar, yayılım sırasında etiketleri daha kolay taşır.

Formül
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)
3

Etiketler, etiketli düğümlerden etiketsiz komşulara iteratif olarak yayılır. Her iterasyonda, her düğüm, komşularının mevcut dağılımlarının ağırlıklı bir kombinasyonu ve kendi başlangıç etiketinin (etiketliyse) ağırlıklı bir kombinasyonu olarak yumuşak etiket dağılımını günceller. Bir karıştırma parametresi alfa, graf yapısının etkisi ile sabit etiketlerin etkisini dengeler ve dağılımlar yakınsayana kadar iterasyon devam eder.

Formül
F \leftarrow \alpha W D^{-1} F + (1-\alpha) Y
4

Yayılım yakınsadıktan sonra, her etiketsiz düğüme, yakınsak dağılımındaki en yüksek yumuşak etiket puanına sahip sınıf atanır. Etiketli düğümler, bilinen etiketlerin asla geçersiz kılınmaması için tüm süreç boyunca gerçek etiketlerine sabitlenir.

Formül
\hat{y}_i = \arg\max_c F_{ic}

Sık yapılan hatalar

  • Özellikleri normalleştirmeden KNN grafiği oluşturmak, yüksek varyanslı özelliklerin mesafe hesaplamalarına hakim olmasına neden olur.
  • k'yi çok büyük ayarlamak, gerçek sınıf sınırlarını yumuşatarak aşırı yumuşatılmış etiket dağılımları üretir.
  • Etiketsiz verilerin etiketli kümeye göre dağıtım dışı olma olasılığını göz ardı etmek.
  • Etiketsiz düğümler üzerindeki doğruluğu, sanki tarafsız bir test kümesi tahminiymiş gibi raporlamak — etiketsiz düğümler eğitim sırasında grafiğe sızdı.
  • Yakınsama kontrollerini atlayıp sabit, keyfi sayıda yayılım iterasyonu kullanmak.

Sık sorulan sorular

k'yi nasıl seçerim?

5-15 aralığında k ile başlayın ve tutulan etiketli doğrulama doğruluğu ile ayarlayın. Daha küçük k daha keskin, daha yerel sınırlar verir; daha büyük k etiketlerin daha uzağa yayılmasını sağlar ancak gerçek sınıf sınırlarını aşma riski taşır.

Verilerin çoğu etiketsiz olduğunda yöntemi dürüstçe değerlendirebilir miyim?

Grafiğe asla eklenmeyen özel bir etiketli test kümesini ayırın. Grafikteki düğümler — etiketsiz olanlar bile — eğitimin bir parçasıdır, bu nedenle graf oluşturmaya katılan herhangi bir etiketli düğüm test noktası olarak hizmet etmemelidir.

Veri kümem tam bir KNN grafiği oluşturmak için çok büyükse ne olur?

Grafiği O(n^2) yerine O(n log n) sürede oluşturmak için FAISS veya Annoy gibi yaklaşık en yakın komşu kütüphanelerini kullanın, ardından seyrek yaklaşık graf üzerinde etiket yayılımı uygulayın.

Yarı denetimli KNN her zaman denetimli KNN'den daha iyi performans gösterir mi?

Zorunlu değil. Etiketsiz veriler dağıtım dışıysa veya özellik uzayı çok yüksek boyutluysa, graf gürültülüdür ve yayılım performansı düşürebilir. Etiketsiz verilerden bir fayda iddia etmeden önce her zaman denetimli bir KNN taban çizgisine karşı karşılaştırın.

Bu, scikit-learn'deki etiket yayma veya etiket yayılımı ile aynı mı?

Yakından ilgili. Scikit-learn'in LabelPropagation ve LabelSpreading'i, KNN veya RBF çekirdek grafiğini kullanarak Zhu ve Ghahramani'nin çerçevesini uygular, bu nedenle burada açıklanan yöntemin doğrudan uygulamalarıdır.

İlgili yöntemler

Kaynaklar

  1. Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    Yayın kaynağını aç
    Kopyalandı.
  2. Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN: 978-0-262-03358-9
    Kopyalandı.