Karar Ağaçları

Veri madenciliği, eğiticili öğrenme konularının içerisinde, sınıflandırma uygulamalarında kendine yer bulan Karar Ağaçları konusunu açıklamaya çalışacağım. Daha sonra bir örnek üzerinden konuyu pekiştirmeye çalışacağım.

Karar Ağaçları; Karar ağaçları eğiticili öğrenme için çok yaygın bir yöntemdir. 2 temel avantajı vardır; Görsel olarak seçenekleri, sonuçları, olasılıkları ve fırsatları gösterir, ikincisi, karmaşık senaryoya sahip durumları kolay anlaşılır bir şekilde şekillendirir.

Karar ağaçları bulunurken ID3, C4.5 gibi algoritmalardan yararlanılır.

Algoritmanın adımları;

• T öğrenme kümesini oluştur.
• T kümesindeki örnekleri en iyi ayıran niteliği belirle. 
•  Seçilen nitelik ile ağacın bir düğümünü oluştur ve bu düğümden çocuk düğümleri veya ağacın yapraklarını oluştur. Çocuk düğümlere ait alt veri kümesinin örneklerini belirle. 
• 3. adımda yaratılan her alt veri kümesi için
• Örneklerin hepsi aynı sınıfa aitse 
•  Örnekleri bölecek nitelik kalmamışsa 
• Kalan niteliklerin değerini taşıyan örnek yoksa işlemi sonlandır. Diğer durumda alt veri kümesini ayırmak için 2. adımdan devam et.

Şimdi örneğimize geçebiliriz. Çeşitli kriterlere sahip ailelerinin hafta sonu yaptıkları etkinlikleri karar ağaçları ile sınıflandırmaya çalışacağız.

Tabloda 10 haftalık bir veri setimiz mevcut. Yavaş yavaş karar ağacımızı oluşturalım.

1.adım: Veri setimizin bir öğrenme kümesi olduğunu varsayalım.

2.adım: Veri setindeki en ayırt edici nitelik belirlenir ve ağacın kökü olarak alınır.

ID3, C4.5 gibi algoritmalar en ayırt edici niteliği belirlerken her nitelik için bilgi kazancı (information gain) ölçer. Bu bilgi kazancını ölçerken Entropi kullanılır.

Hafta sonu veri kümesindeki (T kümesi) 10 örnekten 

• 6 örnek için karar sinema 
• 2 örnek için karar tenis oynamak 
• 1 örnek için karar evde kalmak ve 
• 1 örnek için karar alışverişe gitmek olduğuna göre;

Entropy:

H(T)= - (6/10) log₂(6/10) - (2/10) log₂(2/10) - (1/10) log₂(1/10) - (1/10) log₂(1/10)

H(T)= 1,571

X niteliğinin T veri kümesindeki bilgi kazancı:

Gain(T,X)=Entropy(T)-Σ P(x) Entropy(T(x))

x: Values of X, P(x)=|T(x) | / | T |

Gain(T, hava)= ?

Güneşli=3   (1 Sinema, 2 Tenis)
Rüzgârlı=4   (3 Sinema, 1 Alışveriş)
Yağmurlu=3    (2 Sinema, 1 Evde)

Entropy(T_güneşli)= - (1/3) log₂ (1/3) - (2/3) log₂ (2/3)=0,918

Entropy(T_rüzgârlı)= - (3/4) log₂ (3/4) - (1/4) log₂ (1/4) =0,811

Entropy(T_yağmurlu)= - (2/3) log₂ (2/3) - (1/3) log₂ (1/3) =0,918

Gain(T, hava) = Entropy(T)- ((P(güneşli)Entropy(T_güneşli) + P(rüzgârlı) Entropy(T_rüzgârlı)+ 

 P(yağmurlu) Entropy(T_yağmurlu) )

             =1,571- ((3/10)Entropy(T_güneşli)+(4/10)Entropy(T_rüzgârlı)+ (3/10)Entropy(T_yağmurlu))

Gain(T, hava) =0,70

Gain(T, aileli)= ?

Evet=5   (5 Sinema)

Hayır =5    (2 Tenis, 1 Sinema, 1 Alışveriş, 1 Evde kalmış)

Entropy(T_evet)= - (5/5) log₂ (5/5)  = 0

Entropy(T_hayır)= - (2/5) log₂ (2/5) - 3(1/5) log₂ (1/5) =1,922

Gain(T, aileli) = Entropy(T)- ((P(evet)Entropy(T_evet) + P(hayır) Entropy(T_hayır))

                               =1,571- ((5/10)Entropy(T_evet)+(5/10)Entropy(T_hayır))

Gain(T, aileli)=0,61

 

Gain(T, para)= ?

Zengin=7   (3 Sinema, 2 Tenis, 1 Alışveriş, 1 Evde kalmış)

Fakir=3    (3 Sinema)

Entropy(T_zengin)= -(3/7)log₂ (3/7) - (2/7) log₂ (2/7) – 2(1/7)log₂ (1/7)=1,842

Entropy(T_fakir)= -(3/3) log₂ (3/3) = 0

Gain(T, para) = Entropy(T)- ((P(zengin)Entropy(T_zengin) + P(fakir) Entropy(T_fakir))

                               =1,571- ((7/10)Entropy(T_zengin)+(3/10)Entropy(T_fakir))

Gain(T, para)=0,2816 

Gain(T, hava) = 0,70,

Gain(T, aileli) = 0,61,

Gain(T, para) = 0,2816 olduğuna göre;

bilgi kazancı en büyük olan hava niteliği kök nitelik olmuştur.

  

3. Adım: Ağacın çocuk düğümü olan A düğümüne ait alt veri kümesi belirlenir.

Hafta sonu veri kümesindeki (T_A kümesi) 3 örnekte

• 1 örnek için karar sinema ve
• 2 örnek için karar tenis olduğuna göre;

Entropy (Güneşli): 

H(T_A)= - (1/3) log₂(1/3) - (2/3) log₂(2/3)

H(T_A)= 0,918

Gain(T_A, aileli)= ?

Evet = 1 (1 Sinema)

Hayır  = 2 (2 tenis)

Entropy(T_evet)= - (1/1) log₂ (1/1)  = 0

Entropy(T_hayır)= - (2/2) log₂ (2/2) = 0

Gain(T_A, aileli) = Entropy(T)- ((P(evet)Entropy(T_evet) + P(hayır) Entropy(T_hayır))

                               =0,918 - ((1/3)Entropy(T_evet)+(2/3)Entropy(T_hayır))

 

Gain(T_A, aileli) = 0,918

Gain(T_A, para)= ?

Zengin = 3 (1 Sinema, 2 Tenis)

Fakir  = 0

Entropy(T_zengin)= - (1/3) log₂ (1/3) - (2/3) log₂ (2/3) = 0,918

Gain(T_A, para) = Entropy(T)- ((P(zengin)Entropy(T_zengin) + P(fakir) Entropy(T_fakir))

                               =0,918 - (3/3)Entropy(T_zengin)

Gain(T_A, para) = 0,918 - 0,918 = 0 olduğuna göre;

Bilgi kazancı en büyük olan aile niteliği havanın güneşli (A) olması niteliğinin kök niteliği olmuştur.

Yeni düğüm için en ayırt edici özellik Aileli olarak belirlenmiştir. Bu işlemler her düğüm için aşağıdaki durumlardan biri oluşuncaya kadar devam eder.

• Örneklerin hepsi aynı sınıfa ait 
• Örnekleri bölecek özellik kalmamış
• Kalan özelliklerin değerini taşıyan örnek yok

Hafta sonu veri kümesindeki (T_B kümesi) 4 örnekten

• 3 örnek için karar sinema ve 
• 1 örnek için karar alışveriş olduğuna göre;

Entropy (Rüzgârlı):

H(T_B)= - (3/4) log₂(3/4) - (1/4) log₂(1/4)

H(T_B)= 0,811

Gain(T_B, aileli)= ?

Evet = 2 (2 Sinema)

Hayır  = 2 (1 Sinema, 1 Alışveriş)

Entropy(T_evet)= - (2/2) log₂ (2/2)  = 0

Entropy(T_hayır)= - 2(1/2) log₂ (1/2) = 1

Gain(T_B, aileli) = Entropy(T)- ((P(evet)Entropy(T_evet) + P(hayır) Entropy(T_hayır))

                               =0,811 - ((2/4)Entropy(T_evet)+(2/4)Entropy(T_hayır))

Gain(T_B, aileli) = 0,811 – 0,5 = 0,311

Gain(T_B, para)= ?

Zengin = 3 (2 Sinema, 1 Alışveriş)

Fakir  = 1 (1 Sinema)

Entropy(T_zengin)= - (2/3) log₂ (2/3) - (1/3) log₂ (1/3) = 0,918

Entropy(T_fakir)= - (1/1) log₂ (1/1) = 0

Gain(T_B, para) = Entropy(T)- ((P(zengin)Entropy(T_zengin) + P(fakir) Entropy(T_fakir))

                               =0,918 - (3/4)Entropy(T_zengin)

Gain(T_B, para) = 0,918 - 0,918(0,75) = 0,2295 olduğuna göre;

Bilgi kazancı en büyük olan aile niteliği havanın rüzgârlı (B) olması niteliğinin kök niteliği olmuştur.

Hafta sonu veri kümesindeki (T_C kümesi) 3 örnekten

• 2 örnek için karar sinema ve 
• 1 örnek için karar evde kalmak olduğuna göre;

Entropy (Yağmurlu):

H(T_C)= - (1/3) log₂(1/3) - (2/3) log₂(2/3)

H(T_C) = 0,918

Gain(T_C, aileli)= ?

 Evet = 2 (2 Sinema)

Hayır  = 1 (1 Evde)

Entropy(T_evet)= - (2/2) log₂ (2/2)= 0

Entropy(T_hayır)= - (1/1) log₂ (1/1)  = 0

Gain(T_C, aileli) = Entropy(T) - ((P(evet)Entropy(T_evet) + P(hayır) Entropy(T_hayır))

                               =0,918 - ((2/3)Entropy(T_evet)+(1/3)Entropy(T_hayır))

Gain(T_C, aileli) = 0,918

Gain(T_C, para)= ?

Zengin = 1 (1 Evde)

Fakir  = 2 (2 Sinema)

Entropy(T_zengin)= - (1/1) log₂ (1/1)= 0

Entropy(T_fakir)= - (2/2) log₂ (2/2) = 0

Gain(T_C, aileli) = Entropy(T)- ((P(zengin)Entropy(T_zengin) + P(fakir) Entropy(T_fakir))

                               =0,918 - ((1/3)Entropy(T_zengin)+(2/3)Entropy(T_fakir))

Gain(T_C, para) = 0,918 olduğuna göre;

Bilgi kazancı her iki nitelik içinde aynı olması sebebiyle aile niteliği ve para niteliği havanın yağmurlu (C) olması niteliğine kök niteliği olamamıştır.

Sonuç:

Yapılan işlemler sonucunda karar ağacımız yukarıdaki durumunu almıştır. Yapılan matematik işlemlerin fazla olmasına rağmen bu basit karar ağacını sonucunu bulmaya değer olduğunu düşünüyorum. Karar ağacının görsel açıdan basitliği bu örnekte açıkça belli olmaktadır.

Veri madenciliğinde Karar Ağaçlarını bir örnek ile incelediniz. İyi çalışmalar J

İlham: Sultan Turhan ve Songül Albayrak J