Anasayfa / Bilgisayar Mühendisliği / Algoritmanın Analizi / Karar Ağacı ID3 Algoritması Örneği

Karar Ağacı ID3 Algoritması Örneği

id3 soru

Yukardaki tabloya göre son iki satırın sonucunu, karar ağaçlarından id3 algoritması ile çözünüz ve sonucu bulunuz

Böyle bir soru karşımıza geldiğinde ilk yapacağımız işlem entropy hesaplama olur. Entropy yi sonuca göre yani burada atar mı atamaz mı bizim sonucumuz olacağından ilk ona göre yaparız.

Atar –> 2 adet

Atamaz–> 5 adet

Entropy(Gol)(+2,-5)= -((2/7)*log2(2/5) + (3/7)*(log2(3/5)) = 0,85 == Genel Entropy diyorum kısaca ben buna..

Daha sonra Gain Hesabı yapmamız gerekecektir.

id3 soru adim 1

Gain hesabı yapmadan önce aynı genel entropy yi hesaplar gibi entropy hesabı yapıyoruz. Ve daha sonra bu entropylerin aritmetik ortalamasını alıyoruz. Örneğin bu tablo da genç sayısının adedi 3’tür. Toplam adet 7 olduğundan (3/7) olarak alacağız aritmetik ortalama hesaplarken. Daha sonra çıkan sonucu genel entropy den çıkararak Gain hesabını tamamlayacağız.

(3/7) Entropy(Genç)(+1,-2) = – (1/3*log2(1/3) + (2/3)*log2(2/3)) = 0.91

(2/7) Entropy(Genç)(+1,-1) = – (1/2*log2(1/2) + (1/2)*log2(1/2)) = +1

(2/7) Entropy(Genç)(+0-2) = – (0/2*log2(0/2) + (2/2)*log2(2/2)) = 0

Gain(yaş) = 0.85 -((3/7)*0.91+(2/7)*1 +(2/7)*0) = 0.18

id3 soru adim 2

(3/7) Entropy(Forvet)(+2,-1) = – (2/3*log2(2/3) + (1/3)*log2(1/3)) = 0.91

(2/7) Entropy(Orta Saha)(0,-2) = – (0/2*log2(0/2) + (2/2)*log2(2/2)) = 0

(2/7) Entropy(Defans)(0,-2) = – (0/2*log2(0/2) + (2/2)*log2(2/2)) = 0

Gain(Mevki) = 0.85 -((3/7)*0.91+(2/7)*0 +(2/7)*0) = 0.46

id3 soru adim 3

(5/7) Entropy(Uzun)(+2,-3) = – (2/5*log2(2/5) + (3/5)*log2(3/5)) = 0.96

(2/7) Entropy(Kısa)(0,-2) = – (0/2*log2(0/2) + (2/2)*log2(2/2)) = 0

Gain(Mevki) = 0.85 -((5/7)*0.96+(2/7)*0) = 0.16

gain 1

Görüldüğü üzere en çok Mevki sonucu etkilemektedir. Gain hesabı bu sonucu bulmamıza yaramaktadır. Şimdi Mevki ile ilgili sonuçları sadece düşüneceğiz.

id3 soru adim 2

Görüldüğü üzere Mevkimiz Orta Saha ise her halukarda Atamaz çıkmaktadır.

Defans da ise her halukarda Atamaz çıkmaktadır.

Söz konusu Forvet olunca 2 tane Atar, 1 tane Atamaz sonucu doğmaktadır. Böylece aşağıdaki ağacı oluşturmamız uygun olur.

agac1

Artık sadece Forvet içeren kayıtlarımıza bakacağız.

gainislem1

Sadece bu veriler için en başta yaptığımız işlemleri sırasıyla tekrar yapacağız.

Genel Entropy(GOL)(+2,-1) =(2/3*log2(2/3) + (1/3)*log2(1/3)) = 0.91 (Genel Entropy değerimiz)

gainislem2

(1/3) Entropy(Genç)(+1,0) = – (1/1*log2(1/1) + (0/0)*log2(0/0)) = 0 = (1/3) Entropy(Orta Yaşlı)(+1,0) = (1/3) Entropy(Yaşlı)(0,-1) (Diğer işlemleri yapmadım. çünkü entropy sonuçları eşit çıkmaktadır)

Gain(YAŞ)=0.91 – ((1/3)*0+(1/3)*0+(1/3)*0)) =0.91

gainislem3

(3/3)Entropy(UZUN)(+2,-1) = (2/3*log2(2/3) + (1/3)*log2(1/3)) = 0.91

Gain(BOY) = 0.91 – ((3/3)*0.91) = 0

gain 2

Ve şimdi en yüksek Gain değerine sahip olan Yaş durumunu değerlendirerek ağacımızı tamamlıyoruz. Görüldüğü üzere Boy durumunun hiçbir etkisi olmamaktadır.

gainislem2

Ağacımı şu şekilde tamamlanmaktadır.

agac2

Hakkında Ali Demirci

Ben Ali Demirci... 1991 Ankara doğumluyum. Ankara da yaşıyorum. Fırsat buldukça öğrendiklerimi burada paylaşıyorum. Java ile haşır neşirim. Android'den asla vazgeçemem. Öğrenmeye bayılırım. Yeni şeyler öğrendiğimde, geçmişteki projelerimde keşke böyle yapsaydım diye çok üzülmüşümdür. O yüzden öğrenmekten korkmayın. Takıldığınız yerleri mutlaka sorun. Biliyorsam yanıt veririm. Bilmiyorsam yol gösteririm. Teşekkürler :)

Kontrol Et

Regex Nedir? Nasıl Kullanılır?

Regex(Regular Expression) yani düzenli ifadeler, metinlerde aranan bir tümceyi kolayca bulmamızı sağlayan bir çeşit algoritmadır. Yani …

9 Yorumlar

  1. gamze

    Çok güzel olmuş gerçekten teşekkürler 🙂

  2. Bir kişi

    Genel entropy kısmını anlamadım,

    “Entropy(Gol)(+2,-5)= -((2/7)*log2(2/5) + (3/7)*(log2(3/5)) = 0,85 == Genel Entropy”

    denilmiş fakat sonuç: = “0.85” değil “0.693536139” çıkıyor. Ayrıca formülde hata var ?

    formül: -((p / (p + n) * log2(p / (p + n)) + n / (p + n) * log2(n / (p + n)))

    Doğrusu:

    Entropy(Gol)(+2,-5)= -((2/7)*log2(2/7) + (5/7)*(log2(5/7)) = = 0.863120569 ~ 0,85 == Genel Entropy

    • Matematiksel işlemde hata olduğunu söylüyorsun. Yani kontrol etmedim. Fakat o sonuca takılmadan konuyu anladıysan bu yeterli olmuştur. Sağlaması da doğru olduğundan rakamların önemi yok

      • Bir kişi

        İlk başta formülü yanlış anladım sonra bir kaç kaynağa da bakınca formülü anladım.

  3. Bir kişi

    Ayrıca,

    (3/7) Entropy(Genç)(+1,-2) = – (1/3*log2(1/3) + (2/3)*log2(2/3)) = 0.91
    (2/7) Entropy(Genç)(+1,-1) = – (1/2*log2(1/2) + (1/2)*log2(1/2)) = +1
    (2/7) Entropy(Genç)(+0-2) = – (0/2*log2(0/2) + (2/2)*log2(2/2)) = 0

    Burada da üçü içinde “Genç” yazılmış fakat “Genç”, “Orta Yaş”, “Yaşlı” olması gerekli.

    • yok kardeşim keisnlikle doğru hesap. doğruluğunu oluşan ağaca bakarak, ardından ilk resme bakarım kontrol edebilirsin. Kontrol ettim ve yanlış gözüme çarpmadı

      • Bir kişi

        İşlemde hata yok fakat yazım hatası var:

        (3/7) Entropy(Genç)(+1,-2) = – (1/3*log2(1/3) + (2/3)*log2(2/3)) = 0.91
        (2/7) Entropy(Genç)(+1,-1) = – (1/2*log2(1/2) + (1/2)*log2(1/2)) = +1
        (2/7) Entropy(Genç)(+0-2) = – (0/2*log2(0/2) + (2/2)*log2(2/2)) = 0

        yerine

        (3/7) Entropy(Genç)(+1,-2) = – (1/3*log2(1/3) + (2/3)*log2(2/3)) = 0.91
        (2/7) Entropy(Orta Yaşlı)(+1,-1) = – (1/2*log2(1/2) + (1/2)*log2(1/2)) = +1
        (2/7) Entropy(Yaşlı)(+0-2) = – (0/2*log2(0/2) + (2/2)*log2(2/2)) = 0

        olması gerekli.

  4. Bir kişi

    Kodlama kısmına yer verilmemiş.