Decision Tree (Karar Ağacı) Nedir ve Nasıl Çalışır

 Decision Tree (Karar Ağacı) böl ve fethet (divide and conquer) algoritmasını kullanan hiyerarşik bir veri yapısıdır. Hem sınıflandırma (classification) hem de regresyonda (regression) kullanılabilen etkili bir metoddur. Bu yazıda Decision Tree'nin nasıl çalıştığını ve bazı terimleri inceleyeceğiz.

GİRİŞ

Parametrik tahminlemede, bir modeli bütün data üzerine tanımlarız ve modelin parametreleri üzerinden öğrenmeye çalışırız. Daha sonra aynı modeli ve aynı parametereleri kullanarak test verisi üzerinde deneriz. Ancak parametrik olmayan (nonparametric) input uzayını belirli bölgelere ayırıp, daha sonra her bir input için bu bölgeleri kullanarak öğrenmeye çalışırız.

Bir decision tree, bu bölgeleri bir dizi recursive ayırma yaparak bulmaya çalışan hiyerarşik bir yapıdır. Decision Tree içsel nodelardan oluşur. Bu her node belirli bir fonksiyon kullanarak belirli sonuçlar doğurur. Verilen her inputta, her node belli bir test uygular ve node dallarından biri seçilir. Bu süreç tepede başlar ve leaf node'a ulaşılana kadar devam eder.

Resimde de görüleceği üzere her dikdörtgen bir node dallara ayırma işlemi bu nodelarda yapılan testlerdir. İnputtaki sonuca göre belirli bir yol izlenir ve bu yollarla bir leaf node'a ulaşılmaya çalışılır.

Decision Treelerde bu testlerin kaç değişkene bağlı olarak yapılmasına göre farklı tree türleri vardır.

1. UNIVARIATE TREE (TEK DEĞİŞKENLİ AĞAÇ)

Başlıktan da anlaşılacağı üzere bu ağaç türlerinde yapılan testler bir değişken üzerinden yapılır. Resimde de görüleceği üzere tepede gender üzerine yapılmış. 

• Eğer bu kullanılan input discrete yani 1 den n'e kadar değer alıyorsa (kategorisel), decision node bu testte n tane branch açar. Her branch belli bir n değeri içindir. 
• Örnek olarak elimizde \(x = {Istanbul, Ankara, Izmır} \) olsun. Bu node listedeki her değer için verilen input bu değerlere eşit mi diye kontrol eder. Eşitse ona göre ayrımını yapar. Bundan dolayı \(n\) tane branch oluşur.

• Eğer bu kullanılan input numeric  value ise yapılan test
• \(f_{m} : x_{j} > w_{m0}\). Bu testte \(w_{m0}\) uygun olarak seçilen threshold  value olur. Bu testten sonra node inputu iki ayrı dala (branch) ayırır. Bunlar
• \( L_{m} = \{x |  x_{j} > w_{m0} \} \)
• \( R_{m} = \{x |  x_{j} \leq w_{m0} \} \)

Belirli bir eğitim verisi (training set) için birden çok bu veriyi öğrenebilecek tree (ağaç) vardır. Ancak biz bunların arasından en küçüğünü bulmaya çalışıyoruz. Bu küçüklük treenin içindeki node sayısı ve bunların complexity sidir.  En küçük ağacı NP-Complete algoritması ile buluyoruz. 

Ağaç öğrenme algoritmaları greddydir. Tepedeki nodedan leaf node'a kadar en iyi ayırma (split) için bakarız. Bu split eğitme verisini numeric ya da kategorisele bağlı olarak, iki ya da \(n\)'e böler. 

Bundan sonra leaf node'a ulaşana kadar recursive şekilde bölme işlemleri yapılır.

1.1 Sınıflandırma Ağaçları (Classification Trees)

Sınıflandırma ağaçları konusunda, splitin başarılığı impurity ölçümü ile yapılır. Impurity ölçümü bir nevi node'un ayırma işleminin ne kadar başarılı olduğunu ölçmek için kullanılan bir yöntemdir. Bir splite, eğer o splitin ayırdığı bütün dallar için her aynı sınıfa ait veri, aynı dala gittiyse, pure split (saf ayırma) denir. 

Diyelim ki node \(m\) için, bu node'a ulaşan veri sayısına \(N_{m}\) diyelim. Tepedeki nodedaki veri sayısına da \(N\) diyelim. 

\(N^{i}_{m} \) de \(N_{m}\) in i'ncı sınıfı olsun. O zaman node m deki bütün sınıfların toplam sayısı bize yine \(n_{m}\) verecek.

\[ \sum_{i} N^{i}_{m} = N_{m}\]

Node m e ulaşan bir veri için bu verinin i sınıfından olma olasılığı \( P( C_{i})\)

\[ P( C_{i}| x, m) = p^{i}_{m} = \frac{N^{i}_{m}}{N_{m}}\]

Node m'de eğer bütün i lar için \(p^{i}_{m} \) 1'se veya 0'sa, bu split işlemi pure split olur. Splitten sonra, eğer i sınıfına ait hiçbir eleman ulaşmamışsa  \(p^{i}_{m}  =  0\) dır. Eğer i sınıfına ait bütün elemanlar  ayrılmışsa  \(p^{i}_{m}  =  1\) olur. 

Eğer split (ayırma) pure ise, daha fazla ayırmamıza gerek yok. \(p^{i}_{m}\) 'ı 1 e eşit olan bir sınıfa leaf node ekleyebiliriz. 

Impurity ölçmek için bir olası fonksiyon da entropy dir.

\[ E_{m} = - \sum_{i=1}^{K} p^{i}_{m} log_{2} (p^{i}_{m}) \]

Eğer node m pure değilse, veri impurity'i azaltmak şeklinde ayrılmalı. Ancak her veriyi ayırmak için birden fazla yöntem var. Sayısal (numeric) bir veri için, birden çok ayırma noktası seçilebilir. Bunların arasından imputiry en az verecek ayırmayı arıyoruz çünkü amacımız veriyi iyi şekilde ayırabilen en küçük boyutlu ağacı bulmak. Ayırmadan sonraki alt kümeler pure gibiyse, daha sonrasında bu alt kümeleri ayırmak için daha az split (ayırma) gerekecektir. Bu yöntem o anki node için uygun bir yöntemdir ancak bize en küçük boylu ağacı vereceğine dair bir garanti yoktur.

Diyelim ki \( M_{mj}\), N_{m} 'in j dalı olsun. Bu j sonucunu veren test \(f_{m}(x^{t}) \) için verilen input da \( x^{t}\) olsun.  n farklı kategorisel bir veri için, n tane ayrı sonuç vardır. Sayısal (numeric) bir veri için ise 2 ayrı sonucumuz vardır (n = 2) . İki durumda da \( \sum_{j=1}^{n} N_{mj} = N_{m}\).

Bu formuluün anlamı ise her ayırmadaki veri sayılarının toplamı, ayıran nodedaki veri sayısında eşittir. 

\( N_{mj}^{i}\) ise \( N_{mj}\)'in i'ncı classına \( C_{i} \) sayıdır. Aynı formül burada da geçerli. 

\[ \sum_{i=1}^{K} N_{mj}^{i} =  N_{mj}\]

Benzer şekilde 

\[ \sum_{j=1}^{K} N_{mj}^{i} =  N_{m}^{i}\].

Node m'de test sonucunun j çıktığı verildiğine göre, \(C_{i}\) sınıfının çıkma olasığı

\[ P(C_{i}| x, m, j) = p^{i}_{mj} = \frac{N_{mj}^{i}}{N_{mj}}\]

Ayırmadan sonraki toplam impurity ise 

\[ \zeta_{m} = - \sum_{j=1}^{n} \frac{N_{mj}}{N_{m}} \hspace{1mm} \sum_{i=1}^{K} \hspace{1mm} p_{mj}^{i}  \hspace{1mm} log_{2}(p_{mj}^{i})\]

Sayısal (numeric) bir veri için, \( p^{i}_{mj}\) hesaplayabilmek için yukarıda bahsettiğimiz  \(f_{m} : x_{j} > w_{m0}\) formülünü kullanabiliriz. Ancak bunun için de \(w_{m0} \) değerini bilmemiz gerekiyor. Bu değer için veride \( N_{m} - 1\) mümkün \( w_{m0} \) değeri var. Ancak bunların hepsini test etmek zorunda değiliz. Sadece verilerin ortasındaki noktalarla test etmemiz yeterlidir. Ayrıca en iyi ayrımın her zaman ardışık sayıların farklı sınıflara ait olmasıyla bulunduğuna dikkat edin. Yani bizim verimizde eğer 10 değeri 0. class'a ait ve 11 değeri 1.class'a aitse o zaman bizim için en iyi split değeri 10 olacaktır. Bu durumda \( w_{m0} = 10\). 

Kategorisel veride ise böyle bir ayrıma gerek kalmayacaktır.

Sayısal verilerde deneyip en az entropy verilen nokta ile devam edilir. Daha sonra bu süreç recursive olarak devam edilir. Ayrıca ağacı oluşturmadaki her adımda, spliti impurity değerini en çok azaltacak şekilde seçeriz.