Karar Ağacı Sınıflandırması

Giriiş

Karar Ağaçları (DT'ler), sınıflandırma ve regresyon için kullanılan parametrik olmayan denetimli bir öğrenme yöntemidir. Amaç, veri özelliklerinden çıkarılan basit karar kurallarını öğrenerek hedef değişkenin değerini tahmin eden bir model oluşturmaktır.

Entropi

Eğitimin amacı, en uygun ağacı bulmak için düğümlerdeki en iyi bölünmeleri bulmaktır. Bölmeler aşağıdaki gibi bazı kriterler kullanılarak yapılır: Entropi.

Entropinin aşağıdaki gibi birçok tanımı vardır:

Entropi, bir bilgi kaynağının içerdiği bilgi miktarına karşılık gelir.
Entropi aynı zamanda bir kümedeki rastlantısallık veya sürprizin ölçümü olarak da görülebilir.
Entropi, sistemdeki öngörülemezliği veya kirliliği ölçen bir ölçümdür.

Karar ağaçlarında entropiyi bir düğümün içindeki saflığın ölçüsü olarak ele alacağız. Karar ağacı modelinin amacı, her bölünmede düğümlerin entropisini azaltmaktır:

Böylece ana düğümün entropisi ile alt düğümlerin entropisi arasındaki farkı maksimuma çıkarmak istiyoruz. Bu farka Bilgi kazancı denir.

Bir $X$ kümesinin Entropisi $H$ matematiksel olarak aşağıdaki şekilde formüle edilir:

H(X) = - \sum\limits\_{x \in X} p(x) \log p(x)

Bilgi kazanımı

Bilgi Kazanımı, ana düğümün entropisi ile chlid düğümlerin entropilerinin ağırlıklı toplamı arasındaki farktır ve dolayısıyla aşağıdaki şekilde formüle edilebilir:

$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$

$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$

Neresi:

$H(.)$ entropidir.
$Y$ bölünmeden önceki popülasyondur, ana düğümü temsil eder.
$X$ bölme için kullanmak istediğimiz değişkendir.
$x$ , X'in benzersiz bir değeridir.
$Y[X==x]$ yalnızca $x$ değerlerine sahip bölünmüş bir listedir.

uygun bir örnek verelim:

Ana düğümü X değerlerini kullanarak böldüğümüzde Bilgi Kazancını hesaplayacağız:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

İlk olarak ana düğümün entropisini hesaplıyoruz:

$H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow)$

$= - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3$

Daha sonra, X'in benzersiz değerlerini kullanarak, bölünme sonrasında her bir alt düğümün iç olasılığını hesaplayacağız:

$unique(X) = [Circle, Square]$

$\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square)$

$+ P(Circle|X) \times H(Y | X = Circle)$

$= \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle)$

Örneğin:

$H(Y | X = Square)$ : ilk alt düğümün entropisini temsil eder.
$H(Y | X = Circle)$ : ikinci alt düğümün entropisini temsil eder.

İlk alt düğümle başlıyoruz:

$H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square)$

$- P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square)$

$= - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23$

Ve sonra ikinci alt düğüm:

$H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle)$

$- P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle)$

$= - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28$

Son olarak Bilgi Kazanımı formülündeki entropileri yerine koyarız:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

$= 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041$

Daha önce de belirtildiği gibi, düğüm bölünmesinin amacı Bilgi Kazanımını en üst düzeye çıkarmak ve böylece sonuçta ortaya çıkan alt düğümdeki Entropiyi en aza indirmektir. Bunu yapmak için, düğümü $X_1, X_2, \ldots, Xn$ gibi farklı giriş kümeleriyle denememiz ve bölmemiz gerekir ve yalnızca Bilgi Kazanımını maksimuma çıkaran bölmeyi koruruz:

$X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)$

Bölmeyi ne zaman durdurmalı

Karar ağaçlarındaki düğüm bölünmesi özyinelemeli olduğundan, bölünmeyi durdurmak için kullanabileceğimiz bir kriterin olması gerekir. Bunlar en çok uygulanan kriterlerden bazıları:

Düğüm saf olduğunda: H(düğüm) = 0. Düğümü daha fazla bölmenin bir anlamı yoktur.
Maksimum derinlik sayısı: Modelin ulaşabileceği maksimum derinliği ayarlayabiliriz, bu, düğüm saf olmasa bile bölmenin durdurulduğu anlamına gelir.
Düğüm başına minimum örnek sayısı: Ayrıca düğüm başına minimum $N$ örnek sayısı da ayarlayabiliriz. Düğüm başına örnek sayısı $N$ 'a eşitse, düğüm saf olmasa bile bölmeyi durdururuz.

Eğitimin (bölme) sonunda, karar ağacının sonuna dayanan her düğüme "Yaprak" adı verilir çünkü bu, herhangi bir alt ağacın kökü değildir. Her yaprak en çok örneğe sahip sınıfı temsil edecektir.

Çözüm

Karar ağacı, verimliliği, sezgisel arka planı ve basit uygulaması nedeniyle en ünlü makine öğrenimi algoritmalarından biridir. Bu algoritma ayrıca sayısal bağımsız değişkenlerle ( Gauss Karar Ağacı ) kullanılabilir ve regresyon görevlerini çözmek için de genişletilebilir.