ID3 Tekrarlı İkilikçi Ağaç, Iterative Dichotomiser 3

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, özellikle veri madenciliği (Data Mining) konularında sıkça kullanılan ve bir karar ağacı (decision tree) çeşidi olan ID3 ağacının nasıl çalıştığını açıklamaktır.

Klasik karar ağaçlarının iyileştirimesi olarak görülebilecek olan ID3, İngilizcedeki Iterative Dichotomiser 3 kelimelerinin baş harflerinden oluşmaktadır ve Türkçeye, tekrarlı ikililikçi ağacı kelimeleri ile çevrilebilir (Buradaki 3 sayısı ingilizcedeki ağaç kelimesine yakın olduğu için kullanılmıştır).

Ağacın, isminden de anlaşılacağı üzere amacı sürekli olarak ağaçtaki verileri mümkün olan en büyük iki parçaya bölmek ve böylece ağacın derinliğini azaltmaktır.

Karar Ağacına Bir Örnek

Bu konuyu anlatmadan önce bir karar ağacında (decision tree) aynı bilginin nasıl farklı iki şekilde tutulacağını göstermeye çalışalım. Örnek olarak aşağıdaki veri kümesini (data set) kullanmak isteyelim:

Yukarıda verilen hayvanların çeşitli özelliklerine göre aşağıdaki şekilde bir karar ağacı hazırlamak mümkündür:

Yukarıdaki ağaçta, karar ayırmlarını mor, ve karardan sonra evet olanları sağda hayır olanları ise solda göstermeye çalıştım. Buna göre ilk karardan sonra tek bir veri ayrılırken sonraki her kararda birer eleman ayrılıyor ve nihayet son karar olan Tüylü kararında hiç ayrılma olmuyor. Dolayısıyla bu sıra ile bakıldığında aslında Tüylü ayrımının bir önemi yoktur. Yani aslında 3 seviyede yapılabilecek bütün ayrımlar yapılmıştır denilebilir.

Yukarıdaki ayrımları, daha iyi anlaşılması için aşağıda uzunca yazacağım:

Koala, Kürklüdür

Timsah, Kürksüz ve Sıcak Kanlı değildir

Yunus, Kürksüzdür, Sıcak Kanlıdır ve yüzer

Deve Kuşu, Kürksüzdür, Sıcak Kanlı değildir ve yüzmez

Albatros, Kürksüzdür, Sıcak Kanlı değildir ve yüzmez

Kuzgun, Kürksüzdür, Sıcak Kanlı değildir ve Yüzmez.

Yukarıda, her elemana giden yolları uzunca yazdık. Buna göre herhangi bir elemanı ağaçta kodlayan kaçar adım olduğunu listeleyelim:

Koala -> 1 (sadece kürklüdür ayrımı yeterli)

Timsah -> 2 (hem kürksüz hem de sıcak kanlı olduğunu bilmemiz gerekiyor)

Yunus -> 3 ( hem kürksüz hem sıcak kanlı hem de yüzdüğünü bilmemiz gerekiyor)

Deve Kuşu -> 3

Albatros -> 3

Kuzgun -> 3

Yukarıdaki değerleri toplarsak, 15 adımda bütün elemanları birer kere ziyaret etmek mümkündür denilebilir.

Şimdi aynı verilerden, aşağıdaki ağacı üretelim:

Yukarıdaki yeni ağaç, aynı bilgileri tutmakta sadece karar ağacının karar adımlarının yeri değiştirilmiş. Bu durumda erişim sayılarını yazarsak:

Deve Kuşu -> 1

Albatros -> 1

Kuzgun -> 1

Koala -> 2

Timsah -> 3

Yunus -> 3

Yukarıdaki yeni ağaçta her elemana birer kere erişilmesi istendiğinde toplam 11 adım harcanması gerekmektedir. Bu durumda birinci ağaca göre daha iyi sonuç elde edileceği söyelenebilir.

ID3 algoritması da tam bu noktada devreye girer ve Shannon’un bilgi teorisine (information theory) dayalı olarak entropi(dağınım) hesabı yapar ve ağacı bu yaptığı hesaba göre dağıtmaya çalışır.

Algoritma

ID3 algorimasını burada adım adım verip çalışmasını anlatmaya çalışalım:

1. Şu ana kadar ağaca dahil edilmemiş olan özellikleri alıp bu özelliklerin entropi (dağınım) değerlerini hesapla.

2. En düşük entropi değerine sahip olan özelliği seç.

3. Bu özelliği ayıran kararı ağaca ekle.

Buradaki entropi (dağınım) formülünü hatırlatmak istiyorum:

Yani bütün verilerden sadece o anda incelenen veri değeri çıkarılarak bu veri değerinin ikilik tabandaki logaritması ile çarpılır.

Bir örnek yaparak hatırlayalım. Örneğin yukarıdaki Evet / Hayır durumları için 2 Evet ve 4 Hayır olan bir durumu inceleyelim ve entropi değerini hesaplayalım:

Entropi (4E,2H) = – [(4/6) log2 (4/6)] – [(2/6) log2(2/6)] = – [0.666667 x –0.584962] – [0.3333334 x -1.56496 ] = – [-0.389975] – [ -0.528320833 ] = 0.918295

olarak bulunur.

Buradaki hesap 4 evet ve 2 hayır olması durumu için örnek olarak hazırlanmıştır. Örnek olarak aldığımız veri kümesindeki diğer kolonlar için de hesaplama yapılabilir. Ayrıca karar ağacında bazı kararlardan sonra kümedeki eleman sayısının azalacağı unutulmamalıdır.

Her adımda entropi hesabı yapıldıktan sonra en düşük entropiye sahip olan karar seçilecektir. Aslında bu adımda yapılan seçim bilgi kazanımı (information gain) açısından incelenebilir, yani bilgi kazanımı (information gain) entropinin tersidir ve bu yüzden en düşük entropiye sahip olan karar önce alınmaktadır.

Bu açıdan bakıldığında bir aç gözlü yaklaşımı (greedy approach) olarak görülebilir. Her adımda en düşük entropiye sahip olan karar ihtimali seçilmektedir. Bu seçim belki ilerideki adımların entropi değerlerinin yükselmesine sebep olacaktır ancak ID3 bununla ilgilenmeden aç gözlü olarak ilk en iyi ihtimali alır.

Neticede çizilecek olan karar ağacı aşağıdaki şekilde olacaktır:

Yukarıdaki ağacın en büyük özelliği en az dağılımla karar veriyor olmasıdır. Yani Tüylü ve Sıcak Kanlı ayrımlarından sonraki ayrımların bir öneminin olmaması ve ağacı sadece 2 seviyeye indiriyor olmasıdır.