- Verileri sınıflandırmak için özellik uzayını tekrar tekrar bölen bir yapı olup, her adımda bilgi kazancı en yüksek olan bölme seçilir
- Entropi (Entropy) kullanılarak verinin saflığı (purity) ölçülür ve buna dayanarak bilgi kazancı (Information Gain) hesaplanır
- ID3 algoritması, ebeveyn düğüm ile çocuk düğümlerin entropi farkını hesaplayarak en uygun bölme noktasını bulur ve ağacı özyinelemeli olarak genişletir
- Entropi yerine Gini safsızlığı da kullanılabilir; iki yöntem çoğu zaman benzer sonuçlar üretse de hesaplama verimliliği farklıdır
- Aşırı bölme, aşırı uyum (overfitting) ve kararsızlığa yol açtığı için, bunu hafifletmek amacıyla budama (pruning) veya Random Forest kullanılır
Karar ağaçlarının temel kavramı
- Karar ağaçları veriyi yukarıdan aşağıya doğru böler ve her adımda koşul kuralları uygulayarak veriyi iyi ayrışan bölgelere ayırır
- Her bölme, verinin belirli bir özelliğine (feature) ve eşik değerine (cutoff value) göre belirlenir
- Amaç, sınıflandırmada sınıfların net biçimde ayrıldığı saf düğümler oluşturmaktır
Entropi'nin tanımı ve özellikleri
- Entropi, bilgi belirsizliğini ölçen bir göstergedir ve olasılık (p_i) için (H = -\sum p_i \log_2(p_i)) olarak tanımlanır
- Başlıca özellikleri
- Yalnızca bir olayın olasılığı 1, diğerlerinin 0 olduğu durumda (H=0), yani belirsizlik yoktur
- Tüm olayların olasılığı eşit olduğunda entropi en yüksek değerine ulaşır ve en saf olmayan durumu gösterir
- Olasılıklar eşitlendikçe entropi artar
- Bu nedenle saf düğümlerin entropisi 0'dır, karışık düğümler ise yüksek entropi değerine sahiptir
Bilgi kazancı (Information Gain) ve ID3 algoritması
- Bilgi kazancı, bölme öncesi ve sonrası entropi farkı olarak hesaplanır ve veri bölmenin verimliliğini gösterir
- Formül: (\Delta IG = H_{\text{parent}} - \frac{1}{N}\sum N_{\text{child}} \cdot H_{\text{child}})
- ID3 algoritmasının adımları
- Her özelliğin entropisini hesapla
- Veri kümesini çeşitli bölme kriterlerine göre ayır ve bilgi kazancını hesapla
- Bilgi kazancı en yüksek olan bölmeyi seçip bir karar düğümü oluştur
- Artık bölme yapılamadığında bir yaprak düğüm oluştur
- Tüm alt kümeler için özyinelemeli işlemi sürdür; ancak tüm öğeler aynı sınıftaysa dur
- Örneğin, Diameter ≤ 0.45 koşulu 0.574 bilgi kazancı ile en yüksek değeri verdiği için ilk bölme olarak seçilmiştir
Gini safsızlığı ve alternatif ölçüm
- Gini safsızlığı (Gini impurity), entropiye alternatif olup bilgi safsızlığını ölçmenin başka bir yoludur
- Logaritma hesabı gerektirmediği için hesaplama hızı yüksektir
- Dengesiz veri kümelerinde entropi daha temkinli bir seçim olabilir
- Her iki yöntem de genel olarak benzer sonuçlar üretir
Aşırı uyum ve kararsızlık sorunu
- ID3 algoritması entropiyi en aza indirmek için bölmeyi sürdürdüğünden, ağaç aşırı derecede derinleşebilir
- Bu durum aşırı uyuma (overfitting) neden olur ve yeni veriler üzerindeki genelleme performansını düşürür
- Ayrıca verideki küçük değişimlerin bile ağaç yapısını büyük ölçüde değiştirdiği kararsızlık (high variance) sorunu vardır
- Örnek: Eğitim verisinin %5'ine küçük Gaussian gürültüsü eklense bile tamamen farklı bir ağaç oluşabilir
- Çözüm olarak, budama (pruning) ile ağacın derinliği, yaprak sayısı, minimum örnek sayısı gibi değerler sınırlandırılabilir
Random Forest'a genişleme
- Tek bir karar ağacının kararsızlığını azaltmak için, birden fazla ağacın farklı veri örnekleriyle eğitilip tahminlerinin birleştirildiği yöntem kullanılır
- Bu yaklaşım Random Forest olup yüksek kararlılık ve genelleme performansı sağlar
- Bu yöntem, karar ağaçlarının zayıf yönlerini tamamlar ve günümüzde en başarılı makine öğrenmesi algoritmalarından biri olarak değerlendirilir
Sonuç ve ek öğrenme
- Karar ağaçları, yorumlanması kolay, öğrenme hızı yüksek ve ön işleme ihtiyacı düşük modellerdir
- Ancak aşırı uyum ve kararsızlık sorunlarını çözmek için budama veya ensemble teknikleri gereklidir
- Yazıda regresyon ağaçları, end-cut preference ve hiperparametreler ele alınmamış; ilgili kaynaklarla ek öğrenme önerilmiştir
1 yorum
Hacker News yorumları
Sınıflandırıcı öğrenirken bende çok işe yarayan gizli silah, önce iyi bir doğrusal sınıflandırıcı eğitmekti
Sonra o doğrusal sınıflandırıcının eşiklenmemiş çıktı değerini ek bir özellik boyutu olarak kullanıp bir karar ağacı eğitiyor ve bunu boosted tree sistemiyle sarıyordum
Böylece karar ağacının zayıf yönlerini doğrusal model telafi ediyor, doğrusal modelin zorlandığı kısımları da ağaç ele alıyordu
Veri döndürme ya da eksen normalizasyonu da düşünülebilir ama çoğu zaman gerekmedi
Yalnız, özellikler çok seyrek olduğunda ağaç bölme noktası bulmakta zorlanıyor
Ham duruma ek hesaplamalar ekleyip gözlemlenen durum (observed state) oluşturuyor ve bunun üzerinden öğreniyorsunuz
Örneğin Snake oyununda yalnızca yılanın koordinatlarını değil, kaçış yolu sayısı gibi türetilmiş özellikleri de hesaplayıp öğreniyorsunuz
Veriyi temizleyip özellikleri iyi tasarlamazsanız, sinir ağları gibi kara kutu modellere kıyasla çok daha kötü sonuçlar alırsınız
İronik olan şu ki sinir ağları bu tür örtük özellikleri kendi kendine buluyor, ama neden öyle çalıştıklarını yorumlamak zor
Oblique Decision Tree, Model Tree (M5), Logistic Model Tree (LMT), Hierarchical Mixture of Experts (HME) bunlardan bazıları
2010 civarında CERN'de çalışırken en popüler sınıflandırıcı Boosted Decision Tree idi
Bunun nedeni açıklanabilirlik ile ifade gücü arasındaki dengesi idi ve o dönemde fizik analizlerinde sinir ağları kullanmaya kültürel olarak mesafeli yaklaşılıyordu
Şimdi dönem epey değişti
Fizikte önemli olan yalnızca eğriye iyi uydurmak değil, nedensel mekanizmayı anlamaktır
Tıpkı Ptolemaios'un epicycle sisteminin gök cisimlerinin hareketini daha iyi uydurmasına rağmen nedeni açıklayamaması gibi
Derinlik biraz artınca yorumlanması neredeyse imkânsız bir ormana dönüşüyor
Sinir ağlarında da benzer biçimde iç işlemleri takip edebilirsiniz, ama sonunda neden o kararı verdiğini yine bilemezsiniz
Aynı sitede Random Forest açıklaması da var → mlu-explain/random-forest
İlginç bir gerçek: 1 bitlik sinir ağı (single-bit neural network) aslında özünde bir karar ağacı
Teorik olarak çoğu sinir ağını if-else zincirine “compile” etmek mümkün, ama bunun ne zaman iyi çalıştığı hâlâ net değil
Daha çok kavramın genişletilmiş bir hâli gibi, doğrudan eşleme yapmak zor
O yüzden bunun tam olarak hangi anlamda söylendiğini biraz daha açıklarsanız iyi olur
Karar ağaçlarının en büyük avantajı hız
Düşük gecikmeli bir ortamda ağaç tabanlı sınıflandırıcıyı küçük bir sinir ağıyla değiştirmeye çalıştım, ama sinir ağı doğrulukta biraz daha iyi olsa da çıkarım gecikmesi (latency) 100 kattan fazla yüksekti
Buna karşılık boosting ya da bagging uygulanmış ağaçlar karmaşıklaşıyor ve diğer klasik ML algoritmaları da taşınabilirlik açısından zayıf kalıyor
Bir ML ders kitabında, sanırım ESL, karar ağaçları şöyle tarif ediliyordu
“Yorumlanabilir, hızlıdır, çeşitli veri türlerinde iyi çalışır, ölçeklemeye duyarsızdır ve az sayıda ayar parametresi vardır ama... iyi çalışmaz”
Tabii bagging ya da boosting ile bu zayıflık giderilebilir, ama bu süreçte ilk avantajlarının bir kısmı da kaybolur
Karar ağaçlarını gerçekten seviyorum. En sevdiğim klasik ML algoritması bu
GNU Guile ile saf fonksiyonel ve paralel bir uygulama yazdım → kod bağlantısı
Ama Guile'da NumPy ya da DataFrame benzeri şeyler olmadığı için veri temsili verimsiz kalıyor
Guile ağaç manipülasyonu için uygun olduğundan, karar ağacı uygulaması için doğal bir seçim
Yine de makine koduna derleme yapılırsa daha verimli olurdu
Ayrıca Lush(https://lush.sourceforge.net/) ya da aiscm(https://wedesoft.github.io/aiscm/) da bakmaya değer
Uzmanların muğlak karar verme süreçleri bile çoğu zaman basit bir karar ağacı ya da karar zinciri ile modellenebilir
Uzmanın kendisi bunu karmaşık sanabilir, ama gerçekte basit bir ağaç çoğu durumda daha iyi açıklama sağlar
Eskiden regresyon ya da uzaklık tabanlı kümeleme daha sofistike görünürdü, ama ağaçlar çok daha etkili
Bununla ilgili ayrıntılar Oxford Handbook of Expertise 7. bölümde var
Sonuçta karar ağacı, kD-Tree gibi olasılık uzayını bölüp her bölgeye bir eylem atayan bir yapı
Uzmanın incelikli yargısı sınır yüzeylerinin ayrıntısından geliyor, ama ağaçlar da oldukça iyi bir yaklaşım sunuyor
Site ilginçti ve sunum da iyiydi
Yalnız bazı metinlerde renk kontrastı düşüktü, bu yüzden okumak zordu
Erişilebilirlik sadece engelliler için değil, okunabilirliği artıran temel bir unsur
Bugünün derin öğrenme çağında karar ağaçları olduğundan az değer görüyor
Ama hâlâ yorumlanabilir, hızlı ve yeterince pratikler
Ben web sitesi analizi için ağaç tabanlı bir puanlama sistemi kurdum;
“meta açıklaması var mı?”, “3 saniye içinde yükleniyor mu?”, “mobil uyumlu mu?” gibi koşulları değerlendiriyor
Kullanıcı neden o puanı aldığını anında anlayabiliyor
Bir sinir ağının neden 73 puan verdiğini açıklamak imkânsız, ama ağaçta bu kolay
Bunun başlangıcı MÖ 1000 civarındaki Esagil-kin-apli'nin tanı ağacı sayılabilir