Makine Öğrenimi Bölüm-5 (Karar Ağaçları)

5.1 Giriş

E. Kaan Ulgen
Nov 12, 2017 · 4 min read

Önceki haftalarda k-en yakın komşuluk, yapay sinir ağları ve destek vektör makinalarından bahsetmiştik. Bu haftaki yazımızda ise gözetimli öğrenme algoritmalarından olan “Karar Ağaçları” (Decision Tree — DT) konusunu ele alacağız.

5.2 Karar Ağaçları

Ağaç tabanlı öğrenme algoritmaları, en çok kullanılan gözetimli öğrenme algorimalarındandır. Genel itibariyle ele alınan bütün problemlerin (sınıflandırma ve regression) çözümüne uyarlanabilirler.

Karar agaçları, tesadüfi orman, gradyen güçlendirme (gradient boosting) gibi yöntemler, her türlü veri bilimi problemlerinde yaygın bir şekilde kullanılmaktadırlar. Bu nedenle veri analistleri için bu algoritmaları öğrenmek ve kullanmak çok önemlidir.

Peki Karar Ağaçları Nedir ?

Karar ağacı algoritması, veri madenciliği sınıflandırma algoritmalarından biridir.

Önceden tanımlanmış bir hedef değişkene sahiplerdir. Yapıları itibariyle en tepeden en aşağı inen bir strateji sunmaktadırlar (Kantardzic, 2011; Çelik U., Akçetin E., ve Gök M. , 2017).

Bir karar ağacı, çok sayıda kayıt içeren bir veri kümesini, bir dizi karar kuralları uygulayarak daha küçük kümelere bölmek için kullanılan bir yapıdır. Yani basit karar verme adımları uygulanarak, büyük miktarlardaki kayıtları, çok küçük kayıt gruplarına bölerek kullanılan bir yapıdır.

Karar Ağaçlarının Avantajları:

  • Anlaması ve yorumlaması kolaydır. Kullanılan ağaç yapılar görselleştirilebilir.
  • Az oranda bir veri hazırlığına ihtiyaç duyar. Fakat unutulmamalıdır ki bu model kayıp değerleri desteklememektedir.
  • Kullanılan ağacın maliyeti, ağacı eğitmek için kullanılan veri noktalarının sayısıyla logaritmiktir.
  • Hem sayısal hem de kategorik verileri işleyebilir.
  • Çok çıktılı problemleri ele alabilmektedirler.
  • İstatistiksel testler kullanılarak bir modelin doğrulanması mümkündür.
  • Karar ağaçları, parametrik olmayan bir yöntem olarak düşünülebilir. Yani uzay dağılımı ve sınıflandırma yapısı hakkında bir yaklaşıma sahip değilledir.

Karar Ağaçlarının Dezavantajları:

  • Veriyi iyi bir şekilde açıklamayan aşırı karmaşık ağaçlar üretilebilir. Bu durumda ağaç dallanması takip edilemeyebilir.
  • Ezbere öğrenme yaşanabilir (“over-fitting”). Bu problemin çözümü için model parametrelere kısıtlamalar ve budama gibi yöntemler kullanılabilir. Budama işlemi, az sayıda nesneyi barındıran yaprak düğümlerin karar ağacı grafiğinden atılmasını ifade etmektedir (Schmid, 2013; Çelik U., Akçetin E., ve Gök M. , 2017).

Karar ağacı algoritmalarında bölünmenin nasıl gerçekleşeceği ağacın doğruluğunu etkileyen faktörlerdendir. Sınıflandırma ve regresyon problemleri için bölünme kriterleri genel itibariyle farklıdır.

Karar ağaçları, bir düğümü iki veya daha fazla alt düğümde bölmeye karar vermek için birden fazla algoritma kullanır. Alt düğümlerin oluşturulması, alt düğümlerin homojenliğini arttırır. Başka bir ifadeyle, düğümün saflığının hedef değişkenlere göre arttığını söyleyebiliriz.

Algoritma seçimi, hedef değişkenin tipine dayanır. Karar ağaçlarında en sık kullanılan algoritmalar; kategorik değişkenler için Entropi, Gini, Sınıflandırma Hatası; sürekli değişkenler için ise En Küçük Karalere yöntemi şeklindedir.

Entropi, verilerimizle ilgili belirsizliğin bir ölçüsüdür. Sezgisel olarak, bir veri kümesinin yalnızca bir etiketi varsa (örneğin, her yolcu hayatta kaldı), daha düşük bir entropiye sahip olduğunu düşünebiliriz. Dolayısıyla verilerimizi, entropiyi en aza indirecek bir şekilde bölmemiz gerekmektedir. Bölünmeler ne kadar iyi olursa, tahminimiz de o kadar iyi olur.

H = — Σ p(x) log p(x)

(Entropi Denklemi, Claude Shannon, 1948.)

Burada, p (x) belirli bir sınıfa ait grubun yüzdesini ve H ise entropiyi belirtmektedir.

Karar ağacımızın entropi değerini en aza indirgeyen bölünmeler yapmasını isteriz. En iyi bölünmeyi belirlemek içinde bilgi kazancını kullanırız. Bilgi kazancı aşağıdaki eşitlik ile hesaplanır:

Bilgi Kazancı

Burada, S orijinal veri kümesidir ve D ise kümenin bölünmüş bir parçasıdır. Her V, S’nin bir alt kümesidir. V’nin tümü ayrıktır ve S’yi oluşturmaktadır. Bu durumda bilgi kazancı, bölünmeden önceki orjinal veri setinin entropisi ile her bir özniteliğin entropi değeri arasındaki fark olarak tanımlanmaktadır.

Karar ağacı algoritmasının kullanıldığı sınıflandırma problemlerinde kullanılacak veri seti iki ana parçaya (eğitim-train ve test) ayrılmalıdır. Algoritma, eğitim verilerini kullanarak model oluşturur. Oluşturulan bu model de test verisi üzerinde uygulanarak modelin problem çözümündeki başarısı hesaplanmaktadır.

En çok kullanılan karar ağacı algoritmaları:

  • ID3
  • C4.5
  • CHAID
  • CART

5.3 Uygulama

Karar ağaçları için yapacağımız uygulamada önceki haftalarda da kullanılan iris veri setinden yararlanıcaz. Uygulama kapsamında Pyton programlama dili kullanılmaktadır. Yararlanılan kütüphaneler:

  • Scikit Learn
  • Matplotlib
  • Numpy
  • Graphviz
Şekil-2: Python ile Karar Ağacı Uygulaması
Şekil-3: Python ile Karar Ağacı Uygulaması
Şekil-4: Python ile Karar Ağacı Uygulaması
Şekil-5: Python ile Karar Ağacı Uygulaması

Bu yazıda temel seviyede “karar ağaçları” konusu ele alanmıştır. Gelecek yazının konusu “Regresyon” olacaktır.

Kaynaklar

  1. http://scikit-learn.org/stable/modules/tree.html
  2. Rapidminer ile Uygulamalı Veri Madenciliği (Ufuk Çelik, Eyüp Akçetin, Murat Gök) kitabında “Karar Ağaçları” Bölümü (Şebnem Özdemir),Pusula Yayıncılık — 2017
  3. Kantardzic, M., 2011. Data Mining: Concepts, Models, Methods, and Algorithms
  4. https://www.analyticsvidhya.com/blog/2016/04/complete-tutorial-tree-based-modeling-scratch-in-python/
  5. https://machinelearningmastery.com/implement-decision-tree-algorithm-scratch-python/

E. Kaan Ulgen

Written by

PhD Student at Istanbul University, Extragalactic Astronomy