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

Online Random Forest (Çevrimiçi Rastgele Orman)

Ortaya koyan
Saffari, A. et al.
Yıl
2009
Tür
Incremental ensemble (streaming decision trees)
Aile
Machine learning

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

Yazı boyutu

Ne işe yarar?

Online Random Forest (ORF), klasik Rastgele Orman'ı akış ortamlarına genişleterek, tam eğitim kümesini depolamadan veya yeniden oynatmadan her yeni gözlem geldiğinde her ağacı artımlı olarak günceller.

Adaptive Random Forests (ARF) gibi algoritmalar, veri dağılımı zamanla değiştiğinde topluluğun uyum sağlaması için sapma tespiti ekler.

Yöntemin mantığı

Klasik Rastgele Orman, ağaçlarını büyütmek için tüm veri kümesini önceden gerektirir. Online Random Forest, yığın bootstrap örneklemesinin yerine Poisson ağırlıklı çevrimiçi bir torbalama hilesi kullanır: gelen her gözlem her ağaca iletilir ve ağaç, o örneği kaç kez yeni bir eğitim noktası olarak ele alacağına Poisson sayımı çekerek karar verir. Ağaçlar çevrimiçi bölünme bulma kriterleri (örneğin, Hoeffding sınırları) kullanılarak artımlı olarak büyür ve bir sapma tespit modülü kavram sapmasını izler, güncelliğini yitirmiş ağaçları yenileriyle değiştirir. Sonuç, bir akıştan sürekli öğrenirken varyans azaltma için birden fazla çeşitli ağacı birleştiren bir ormandır.

Tarih

Çevrimiçi torbalama, bootstrap toplama işleminin Poisson ağırlıklı bir yaklaşımı olarak Oza & Russell (2001) tarafından biçimlendirilmiştir. Saffari ve ark. (2009), çevrimiçi torbalamayı rastgele özellik seçimi ve bilgisayar görüşü akışları için Hoeffding tabanlı bölünme kriterleriyle birleştiren On-line Random Forests'ı tanıttı. Gomes ve ark. (2017), ADWIN aracılığıyla ağaç başına sapma tespiti ekleyen Adaptive Random Forests'ı (ARF) tanıttı ve veri akışı sınıflandırma görevleri için benchmark veriler üzerinde son teknoloji doğruluğu gösterdi. ARF, MOA (Massive Online Analysis) çerçevesinde standart bir temel oluşturdu.

Ne zaman kullanılır?

Veri sürekli veya bellekte tutulamayacak kadar büyük yığınlar halinde geliyorsa, kavram sapmasının olası olduğu durumlarda (örneğin, finansal akışlar, sensör ağları, kullanıcı davranışı günlükleri) veya tam veri kümesi mevcut olmadan düşük gecikmeli tahminler gerekiyorsa Online Random Forest'ı kullanın. Etiketli verilerin zamanla az az geldiği uygulamalar için de doğal bir uyumdur. Tüm veri kümesinin belleğe rahatça sığdığı ve yeniden eğitimin uygun olduğu durumlarda bundan kaçının — bu durumda çevrimdışı eğitilmiş standart bir Rastgele Orman genellikle daha doğru ve doğrulanması daha kolay olacaktır. Ayrıca, kararlı, tekrarlanabilir özellik önem sıralamaları gerekiyorsa bundan kaçının, çünkü çevrimiçi ormanlar yığın eşdeğerlerinden daha az kararlı önem tahminleri üretir.

Sınırlar ve dikkat edilmesi gerekenler

  • Seyrek verilerle erken yapılan bölünme kararları optimal olmayabilir ve revize edilmesi zor olabilir.
  • Özellik önem tahminleri, yığın Rastgele Orman'a göre daha az kararlıdır.
  • Hiperparametre ayarı (ağaç sayısı, sapma tespit eşikleri) bir akış bağlamında daha karmaşıktır.
  • Değerlendirme, standart çapraz doğrulamadan farklı olan özel akış tabanlı protokoller (önsel/test-önce-eğit) gerektirir.

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

Güçlü yönleri

  • Ağaç başına sabit bellek ile akış verilerinden öğrenir, akış uzunluğundan bağımsızdır.
  • ADWIN gibi sapma tespit mekanizmalarıyla eşleştirildiğinde kavram sapmasına uyum sağlar.
  • Çevrimiçi bir ortamda bile topluluk toplama işleminin varyans azaltma faydalarından yararlanır.
  • İlk birkaç gözlemden itibaren kullanılabilir tahminler sağlar, zamanla iyileşir.
  • Tüm geçmiş veri kümesini depolamaya veya yeniden oynatmaya gerek yoktur.

Uygulama alanları

  • Ağ veya işlem akışlarında gerçek zamanlı dolandırıcılık ve saldırı tespiti.
  • Dağılımların ekipman yaşlanmasıyla kaydığı sensör akışlarından tahmine dayalı bakım.
  • Kullanıcı davranışlarının günlük olarak geliştiği reklamlarda tıklama oranı tahmini.
  • Hasta durumunun zamanla sürekli değiştiği tıbbi izleme.
  • Durağan olmayan mevsimsel desenlere sahip çevresel ve iklimsel algılama.

Nasıl çalışır?

Nasıl çalışır?

1

Bir T ağacı (veya Hoeffding ağacı) kümesi başlatılır. Her ağaç, ham gözlemleri depolamak yerine, ağaç başına yaprak başına yeterli istatistikler (sınıf sayıları veya regresyon için kareler toplamı) tutar, bu da modeli ağaç başına sabit bellekli hale getirir.

2

Gelen her gözlem için, her ağaç bağımsız olarak bir Poisson(1) dağılımından k çeker ve gözlemi kendisinin k sanal kopyası olarak ele alır. k = 0 olduğunda ağaç noktayı atlar (kendi torba dışı örneği gibi davranır). Bu, tüm veri kümesini gerektirmeden bootstrap örneklemesini yaklaştırır.

Formül
k \sim \text{Poisson}(\lambda),\; \lambda=1
3

Her ağaç, yeterli istatistikleri aktif yaprağında günceller. İstatistiksel olarak sağlam bir kriter (Hoeffding sınırı gibi) en iyi bölünmenin daha fazla veriyle değişmesinin olası olmadığını gösterdiğinde bir bölünme tetiklenir, ardından yaprak bir iç düğüme genişletilir ve yeni yapraklar başlatılır.

4

İsteğe bağlı bir sapma tespit modülü (örneğin, ADWIN), her ağacın torba dışı akış üzerindeki tahmin hatasını izler. İstatistiksel olarak anlamlı bir bozulma tespit edildiğinde, etkilenen ağaç sıfırlanır veya taze başlatılmış bir ağaçla değiştirilir, bu da topluluğu gelişen dağılımlarla güncel tutar.

5

Herhangi bir noktada, tüm aktif ağaçlar oy kullanır: sınıflandırma için çoğunluk oyu veya regresyon için ortalama tahmin. Çok az örnek işlemiş ağaçlar, güvenilir oylar verecek kadar veri biriktirene kadar ağırlığı azaltılabilir veya hariç tutulabilir.

Formül
\hat{y} = \text{mode/mean of active trees}

Sık yapılan hatalar

  • i.i.d. verileri varsayan ve zamansal sırayı göz ardı eden standart k-katlı çapraz doğrulamayı kullanarak değerlendirme.
  • Kavram sapmasını göz ardı etme: veri dağılımı zamanla değiştiğinde bir sapma tespit bileşenini dahil etmeme.
  • Çevrimiçi orman doğruluğunu, tam geçmiş veri kümesi üzerinde eğitilmiş bir yığın Rastgele Orman ile doğrudan karşılaştırma — ikincisi doğası gereği bir bilgi avantajına sahiptir.
  • Her ağacın güvenilir bölünmeler yapacak kadar veri görmesinden önce akışın başlarında çok az sayıda ağaç kullanma.
  • Poisson ağırlıklı torbalamanın bootstrap'i yaklaştırdığını unutma — yığın bootstrap'in istatistiksel özelliklerini tam olarak yeniden üretmez.

Sık sorulan sorular

Online Random Forest, standart Random Forest'tan nasıl farklıdır?

Standart Random Forest, tüm ağaçları bootstrap örneklemesi kullanarak tam veri kümesi üzerinde aynı anda eğitir. Online Random Forest, yığın bootstrap'i Poisson ağırlıklı çevrimiçi torbalama ile değiştirir, her gözlem geldiğinde ağaç bölünmelerini artımlı olarak günceller ve isteğe bağlı olarak kavram sapmasını tespit eder ve buna uyum sağlar — tümü geçmiş verileri depolamadan.

Poisson ağırlıklandırma hilesi nedir?

Gelen her örnek, her ağaca Poisson(1)'den çekilen k kez gösterilir. k'nın beklenen değeri 1 olduğundan ve k olasılıkla ~%37 oranında 0 olduğundan, bu istatistiksel olarak tüm veri kümesini bellekte tutmaya gerek kalmadan bootstrap sürecini (yerine koyarak örnekleme) yaklaştırır.

Bir çevrimiçi rastgele ormanı nasıl değerlendirmeliyim?

Önsel (test-önce-eğit) protokolünü kullanın: gelen her gözlem için önce mevcut modelle tahmin yapın, hatayı kaydedin, ardından modeli güncelleyin. Bu, veri sızıntısı olmadan tahmin performansı için tarafsız, zamansal olarak sıralanmış bir tahmin sağlar.

Ne zaman sapma tespiti eklemeliyim?

Veri üretim sürecinin zamanla değişmesi muhtemel olduğunda — örneğin, kullanıcı tercihleri, finansal piyasalar veya aşınan mekanik sistemler. Sapma tespiti olmadan, güncelliğini yitirmiş ağaçlar birikir ve topluluk doğruluğunu düşürür. ADWIN, yaygın, iyi test edilmiş bir seçimdir.

Adaptive Random Forest aynı şey mi?

ARF, Online Random Forest'ın en yaygın benimsenen varyantıdır. Çevrimiçi torbalama, rastgele özellik seçimi ve ağaç başına ADWIN sapma tespitini birleştirir ve MOA ve scikit-multiflow/River kütüphanelerinde mevcuttur. 'Online Random Forest' terimi genellikle aileye genel olarak atıfta bulunur; ARF, özel, şiddetle tavsiye edilen bir uygulamadır.

İlgili yöntemler

Kaynaklar

  1. Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009). On-line random forests. In Proceedings of the 3rd IEEE International Workshop on On-Line Learning for Computer Vision (OLCV 2009), pp. 1–8. IEEE.

    Yayın kaynağını aç
    Kopyalandı.
  2. Gomes, H. M., Bifet, A., Read, J., Barddal, J. P., Enembreck, F., Pfharinger, B., Holmes, G., & Abdessalem, T. (2017). Adaptive random forests for evolving data stream classification. Machine Learning, 106(9), 1469–1495.

    DOI kaynağını aç
    Kopyalandı.