Çevrimiçi Karar Ağacı
- Ortaya koyan
- Domingos, P. & Hulten, G.
- Yıl
- 2000
- Tür
- Incremental supervised classifier
- Aile
- Machine learning
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Bir Çevrimiçi Karar Ağacı, geçmiş örnekleri tekrar ziyaret etmeden sürekli bir veri akışından artımlı olarak büyüyen bir karar ağacıdır.
Baskın algoritma olan Hoeffding Ağacı (VFDT), bir düğümde yeterli sayıda örnek görüldüğünde güvenle bölüneceğini belirlemek için Hoeffding sınırını kullanır ve potansiyel olarak sonsuz veri akışlarında ölçeklenebilir, gerçek zamanlı sınıflandırma sağlar.
Yöntemin mantığı
Standart bir karar ağacı, en iyi bölmeleri bulmak için tam veri kümesini tekrar tekrar tarayarak oluşturulur. Akış ortamlarında bu imkansızdır çünkü veriler tek tek gelir ve saklanamaz. Çevrimiçi yaklaşım, her yaprakta yalnızca çalışan istatistikleri tutar. Yeterli örnek biriktiğinde, Hoeffding sınırı – istatistiksel bir güvence – görünen en iyi bölmenin, olası tüm örnekleri görmüş olsak bile en iyi bölme olarak kalacağını doğrular. Yalnızca o zaman ağaç gerçekten bölünür, geçmiş verilere hiç bakmadan tek bir yapraktan giderek derinleşen bir yapıya doğru büyür.
Tarih
Temel algoritma olan Çok Hızlı Karar Ağacı (VFDT) veya Hoeffding Ağacı, Domingos ve Hulten tarafından KDD 2000'de tanıtıldı. Örnekleri saklamadan asimptotik olarak doğru ağaç indüksiyonunu sağlayan, veri akışından bölme öznitelikleri seçimindeki hatayı sınırlamak için Hoeffding eşitsizliğini uyguladı. Hulten, Spencer ve Domingos bunu 2001'de kavram sapmalı akışlara genişletti. Yaklaşım, MOA (Massive Online Analysis) çerçevesinin temel taşı haline geldi ve bir nesil akış topluluk yöntemlerine ilham verdi.
Ne zaman kullanılır?
Veriler sürekli bir akış olarak geldiğinde, tam veri kümesini depolamak hacim veya gizlilik kısıtlamaları nedeniyle mümkün olmadığında veya modelin her yeni gözlemle gerçek zamanlı olarak güncellenmesi gerektiğinde çevrimiçi bir karar ağacı kullanın. IoT sensör akışları, tıklama akışı sınıflandırması, gelişen kalıplara sahip dolandırıcılık tespiti ve kavram sapmasının beklendiği ve modelin sıfırdan yeniden eğitilmeden uyum sağlaması gereken herhangi bir ortam için çok uygundur. Veri kümesinin küçük ve statik olduğu durumlarda kullanmayın — standart bir karar ağacı veya rastgele orman uygulaması daha hızlı ve daha doğru olacaktır. Ayrıca, bölme eşiklerinin zamanla kayabileceğini kabul etmeden, kesin bölme eşiklerinin yorumlanabilirliğinin kritik olduğu durumlardan kaçının.
Sınırlar ve dikkat edilmesi gerekenler
- Küçük veri kümelerindeki doğruluk, Hoeffding sınırının erken bölmelerin yapılması için birçok örneğe ihtiyaç duyması nedeniyle genellikle toplu bir karar ağacından daha düşüktür.
- Temel algoritmadaki bölme kararları geri alınamaz; kötü bir erken bölme, açık alt ağaç değiştirme eklenmedikçe kalıcı olabilir.
- Güvenlik parametresi delta ve bölme değerlendirmeleri arasındaki bekleme süresinin ayarlanması alan bilgisi gerektirir.
- Ağacın yorumlanabilirliği, yeni bölmeler eklendikçe zamanla değişir, bu da statik raporlamayı zorlaştırır.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Düğüm başına sabit bellek kullanarak tek geçişte veri işler, teorik olarak sonsuz akışlara ölçeklenir.
- Yeterli veri verildiğinde, bölmelerin toplu bir ağacın bölmeleriyle asimptotik olarak aynı olacağına dair teorik güvenceleri Hoeffding sınırı aracılığıyla sağlar.
- Tam yeniden eğitim gerektirmeden durağan olmayan dağılımlara uyum sağlamak için sapma dedektörlerini içerebilir.
- Tam bir veri kümesi gerektiren toplu yöntemlerin aksine, ilk örnekten itibaren kullanılabilir bir model sunar.
- Verilerin pratik olmadığı veya yasal olarak kısıtlı olduğu yüksek işlem hacimli ortamları doğal olarak işler.
Uygulama alanları
- Finansal işlem akışlarında gerçek zamanlı dolandırıcılık tespiti.
- Trafik istatistiklerinin sürekli geldiği ağ saldırısı tespiti.
- Belleği kısıtlı kenar cihazlarla IoT ve sensör verileri sınıflandırması.
- Veri hacminin tam depolamayı engellediği tıklama akışı veya kullanıcı davranışı modellemesi.
- E-postalardaki dilbilimsel kalıplar zamanla geliştikçe uyarlanabilir spam filtreleme.
- Daha karmaşık akış topluluklarının kıyaslandığı temel akış sınıflandırıcı.
Nasıl çalışır?
Nasıl çalışır?
Etiketlenmiş her örnek, ağaç kökten mevcut bölmeler aracılığıyla uygun yaprağa yönlendirilir ve etiketlenmeden önce örnek için bir tahmin yapılır.
Sınıf koşullu sayımlar veya Gauss ortalaması ve varyansı gibi tüm aday bölme öznitelikleri için yeterli istatistikler, örneği alan yaprakta güncellenir. Ham veri saklanmaz; yalnızca bu kompakt özetler büyür.
Hoeffding (veya Chernoff) sınırı epsilon = sqrt(R^2 * ln(1/delta) / (2n)), en az 1 - delta olasılıkla gözlemlenen en iyi bölme özniteliği ile gerçek en iyi bölme arasındaki maksimum hatayı ölçer. n büyüdükçe, epsilon sıfıra doğru küçülür.
Formül
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}En iyi ve ikinci en iyi bölme adayları arasındaki bilgi kazancı farkı mevcut Hoeffding sınırını aşarsa, yaprak kazanan öznitelikte bir iç bölme düğümü ile değiştirilir ve iki yeni yaprak sayacı başlatılır. Aksi takdirde, düğüm daha fazla veri bekler.
Gelen her örnek, etiketi güncelleme için kullanılmadan önce mevcut ağaçtan bir sınıf tahmini alır. İsteğe bağlı olarak, sapma dedektörleri (örneğin, ADWIN) yaprak hata oranlarını izler; kavram sapması tespit edildiğinde, modeli güncel tutmak için alt ağaçlar değiştirilebilir.
Sık yapılan hatalar
- Hoeffding güvenliği delta'yı çok gevşek ayarlayarak, temsilci olmayan erken verilerde erken bölmelere neden olmak.
- Kavram sapmasını göz ardı etmek — durağan bir çevrimiçi ağacı değişen dağılımlara sahip veriler üzerinde çalıştırmak, sessiz doğruluk düşüşüne yol açar.
- Aynı akışın tüm verileri üzerinde eğitilmiş bir toplu modelle karşılaştırıldığında doğruluk karşılaştırması yapmak, bu da toplu modele haksız bir avantaj sağlar.
- Bölünmeden önceki yaprakların her zaman şimdiye kadar görülen çoğunluk sınıfını tahmin ettiğini unutmak, dengesiz akışlarla erken aşamalarda yanıltıcı olabilir.
Sık sorulan sorular
Hoeffding Ağacı standart bir CART karar ağacından nasıl farklıdır?
Bir CART ağacı, küresel olarak en iyi bölmeyi bulmak için her düğümde tam veri kümesini tarar. Hoeffding Ağacı bunun yerine örneklerin tek tek gelmesini izler ve yalnızca istatistiksel teori, görünen kazananın daha fazla veriyle bile kazanacağını garanti ettiğinde bir bölmeye karar verir — ham örnekleri saklamadan.
Çevrimiçi karar ağacı kavram sapmasını ele alır mı?
Temel Hoeffding Ağacı sapmayı otomatik olarak algılamaz. Kavram Uyumlu Çok Hızlı Karar Ağacı (CVFDT) gibi uzantılar ve ADWIN veya Page-Hinkley sapma dedektörleriyle birleştirilmiş sürümler, sapma tespit edildiğinde güncelliğini yitirmiş alt ağaçları değiştirebilir.
Bekleme süresi nedir ve nasıl ayarlanmalıdır?
Bekleme süresi, ardışık bölme değerlendirmeleri arasında bir yaprağa gelen örnek sayısıdır. Daha büyük bir değer hesaplamayı azaltır ancak bölmeleri geciktirir; daha küçük bir değer daha yüksek CPU maliyetiyle bölmeleri daha sık değerlendirir. Tipik varsayılanlar 200 ila 1000 örnek arasında değişir.
Çevrimiçi karar ağacı küçük, statik veri kümeleri için uygun mudur?
Hayır. Küçük, tam olarak mevcut veri kümeleri için standart bir toplu karar ağacı veya rastgele orman, çok daha az karmaşıklıkla neredeyse her zaman daha iyi doğruluk elde edecektir. Çevrimiçi ağaçlar özellikle akış, büyük ölçekli veya kaynak kısıtlı rejim için tasarlanmıştır.
Sabit bir veri kümesinde toplu yöntemlerle doğruluk nasıl karşılaştırılır?
Yeterli veriyle Hoeffding Ağacı, bir toplu öğrenicinin üreteceği aynı ağaca yakınsar, bu nedenle doğruluk sonunda eşleşir. Akışın başlarında, yapraklar birçok örneği görmeden önce, doğruluk şimdiye kadar görülen aynı veriler üzerinde eğitilmiş bir toplu ağaçtan daha düşüktür.
İlgili yöntemler
Kaynaklar
Domingos, P., & Hulten, G. (2000). Mining very fast data streams. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 71–80). ACM.
Yayın kaynağını açKopyalandı.Hulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 97–106). ACM.
DOI kaynağını açKopyalandı.