C4.5 Ağacı (C4.5 Tree)

C4.5 Ağacı (C4.5 Tree)

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, karar ağaçlarına (decision tree) bir örnek olaran C4.5 ağacını açıklamaktır. C4.5 ağacı, ID3 ağacının geliştirilmiş bir hali olarak düşünülebilir ve daha önce bu konuda yayınlanan ID3 ağacı başlıklı yazıyı okumanızda yarar vardır. Bu yazıda iki ağacı karşılaştırarak konu anlatılacaktır.

C4.5 ağacının ID3 ağacından en büyük farkı normalleştirme (normalization) kullanıyor olmasıdır. Yani ID3 ağacı üzerinde e ntropi hesabı yapılır (veya bilgi kazanımı (information gain)) ve bu değere göre karar noktaları belirlenir. C4.5 ağacında ise entropi değerleri birer oran olarak tutulur. Ayrıca ağaç üzerinde erişim sıklıklarına göre alt ağaçların (subtree) farklı seviyelere taşınması da mümkündür. C4.5 ağacının diğer bir farkı ise tam bu noktada orataya çıkar ID3 ağacının yaklaşımından farklı olarak C4.5 ağacında budama (prunning) işlemi yapılmaktadır.

Bu farklılıklardan bahsettikten sonra nasıl çalıştığını hızlıca açıklamaya çalışalım.

• Her adımda bütün özellikler kontrol edilir

• Her özelliğin normalize edilmiş bilgi kazanımı (information gain) hesaplanır

• En iyi bilgi kazanımını veren özellik karar ağacında karar olarak taşınır.

• Ardından bu yeni karar düğümünün altında bir alt liste oluşturularak alt karar ağacı inşa edilir.

Konuyu bir örnek üzerinden anlamaya çalışalım. Örnek olarak aşağıdaki veri kümesini (data set) ele alalım:

Yukarıdaki veri kümesi için bir C4.5 ağacı oluşturmak istiyor olalım. Yapacağımız ilk adım bilgi kazanımını (information gain) hesaplamaktır. Bu adımda bilgi kazanımının formülünü hatırlayalım. Bilgi kazanımı hesaplanırken, o anda veri kümesinde bulunan bütün veriler ve hesaplanması istenen belirli bir verinin üzerinden gidilir. Bu hesaplaması yapılacak olan belirli veriye örnekleme (misal, sampling) ismi verilir ve bütün veri kümesi üzerinden bu örneklemeye ait hesaplama yapılır.

Bilgi (information) hesaplaması sırasında kullanılacak olan formül yukarıdaki şekildedir. Buna göre herhangi bir misal (M ile gösterilmiştir) için o sınıftaki (S ile gösterilmiştir) değerlere göre frekansına bakılır. Ayrıca yukarıdaki formülde |M| değeri, o sınıftaki misallerin sayısını ifade etmektedir.

Yukarıdaki şekilde her örnek için bilgi değeri hesaplandıktan sonra kazanım (gain) hesaplanması mümkündür.

Genelde tam bu adımda bilgi parçalara bölünür ve bölünen parçalar (partition) üzerinden işlem yapılır. Bu durum için ise hesaplama aşağıdaki şekilde yapılabilir:

Yukarıdaki formülde her bir i parçası için yapılan bilgi hesaplaması verilmektedir.

Kazanım ise bu durumda aşağıdaki şekilde hesaplanabilir:

Yani herhangi bir X özelliği için kazanım değeri, o özelliğin bağlı olduğu bütün parça ve sadece o özelliği ilgilendiren parça arasındaki farka eşittir. Bu iki değerin hesabı da yukarıda verilmiştir (yazıdaki ilk ve ikinci formüller).

Şimdi yukarıda anlattığımız bu değerlerin gerçek bir uygulama üzerinden nasıl hesaplandığını görelim.

Örnek veri kümemiz aşağıdaki şekilde olsun:

Örneğin sınıf değerinin bilgi kazanımını (information gain) hesaplamak istiyor olalım. Yukarıdaki formüle göre, 14 toplam satırdan 5 tanesi sınıf 2 ve 9 tanesinin sınıf 1 olduğunu dikkate alarak aşağıdaki eşitliği yazıyoruz. Önce bilgi değerlerini hesaplayacak sonra da kazanımı bulacağız:

İlk bilgi değeri bütün parçanın hesaplandığı yani 14 satırın tamamının dikkate alındığı ve 9/14 ve 5/14 olarak iki ihtimalin hesaba katıldığı durumdur. Bu durum aynı zamanda entropi olarak da düşünülebilir.

İkinci bilgi hesabımızda özellik 1 kullanılacak. Buna göre veri kümemizin ilk 5 satırında Ali, sonraki 4 satırında Evren ve son 5 satırında Şadi özellikleri var. Buna göre tabloyu 3 parçaya bölersek :

Yukarıdaki yeni tabloya göre her özellik parçasının ayrı ayrı hesaplanarak denklemde yerine yazılması gerekir:

Yukarıdaki formülde mavir renkle belirtilen durum 1. özellik için (x1) 5, 4 ve 5 parçadan oluşan ve her parça için ayrı ayrı Sınıf1 ve Sınıf2 değerlerinin sayıldığı durumdur. Yani ilk 5 satırlık parçanın 2 satırı Sınıf1 ve 3 satırı Sınıf2 olduğu için 2/5 ve 3/5 şeklinde iki değer alınmıştır. Diğerleri de benzer şekilde hesaplanmıştır.

Son adımda bu iki değer arasındaki farkı hesaplayabiliriz:

olarak bulunur.

Yukarıda bulunan bilgi kazanımı, bütün veri kümesindeki Özellik1 için bütün sınıflar arasındaki kazanımı göstermektedir. Bu değerleri kullanarak aslında veri kümemizi 3 parçaya bölmüş ve her birisi için bilgi kazanımının olası değerini hesaplamış oluyoruz:

Yukarıdaki gösterim karar ağacının alabileceği olasılıklardan birisidir ve ağacın özellik 1’de bulunan isimlere göre karar noktası oluşturulması halinde alacağı vaziyeti gösterir.

Şimdi aynı hesabı, Özellik 3 için yapalım. Burada geçti / kaldı ihtimalleri bulunuyor dolayısıyla ağaç 2 dala ayrılabilir. Ancak biz önce hesabımızı yapalım.

Özellik 3 için 3/6 ve 6/8 olmak üzere iki parça bulunuyor ve her ikisi için de hesap yapılıp toplam bilgiden çıkarıldığında kazanım değeri olarak 0.048 bit bulunuyor. Bu değeri yorumlamadan önce ağacın şu anda hesaplanan halini göstermeye çalışalım:

Yukarıdaki şekilde ağacın ilk karar noktasını Geçti / Kaldı ihtimalleri üzerine kuracak olursak bilgi kazanımı olarak 0.048 beklenmektedir.

Bu durumda C4.5 ağacı en yüksek kazanıma sahip olan değeri alacaktır. Bu değer Özellik 1 için isimler olduğundan karar ağacının bu adımda Özellik 1’e göre karar noktası eklemesi yerinde olacaktır.

Arıdından diğer adımlar için benzer şekilde hesaplamalar yapılarak ağacın karar noktaları oluşturulmaya devam edecektir.

C4.5 Ağacının önemli bir diğer özelliği ise budama işlemidir. Esas olarak ağaçlarda iki tip budama yapılabilir. Birisi ön budama (preprunning) diğeri ise son budama (post prunning). C4.5 ağacı son budama (postprunning) yöntemini tercih etmektedir.

Hemen burada karar ağaçlarında (decision trees) ön budama ve son budamanın nasıl yapıldığından bahsedelim. Ön budama, genelde ağaç oluşturulurken bazı dalların oluşturulmaması yönündedir. Örneğin bazı dallar anlamsız olacağından veya hiç eleman içermeyeceğinden oluşturulmaz. Son budama ise ağacın bütün dallarını oluşturur ve sonra bazı şartlara göre budama yapar. Burada da eleman içermeyen dallar budanabileceği gibi, bazı durumlarda istatistiksel yaklaşımlar da kullanılabilir. Örneğin yukarıdaki veri kümemizi Özellik 2’yi kullanarak 10luk dilimlere bölmek isteyelim. 100-90 arasında 90-80 ve 80-70 arasında verilerimiz olacak ancak 70’in altında verilerimiz olmayacak. Bunu verilere bakmadan anlayamayız. Şayet illaki ağaç oluşturulacaksa ve kural 0 ile 100 arasındaki notların 10’arlık dilimler halinde bölünmesi ise bu dalların da ağaçta yer alması gerekir ancak hiç veri içermeyeceği için bu dallanmalar anlamsız olacak ve budanacaktır.

C4.5 ağacı için son olarak WEKA programında J48 olarak açık kaynak kodlu bir versiyonunun yazılmış olduğunu söylemekte yarar vardır.