Klasifikasi Pohon Keputusan

Perkenalan

Pohon Keputusan (DT) adalah metode pembelajaran terawasi non-parametrik yang digunakan untuk klasifikasi dan regresi. Tujuannya adalah untuk membuat model yang memprediksi nilai variabel target dengan mempelajari aturan keputusan sederhana yang disimpulkan dari fitur data.

Entropi

Tujuan dari pelatihan ini adalah untuk menemukan pemisahan node terbaik untuk menemukan pohon yang paling optimal. Pemisahan dilakukan dengan menggunakan beberapa kriteria seperti: Entropi.

Ada banyak definisi entropi seperti:

Entropi sesuai dengan jumlah informasi yang terkandung dalam suatu sumber informasi.
Entropi juga dapat dilihat sebagai keacakan atau ukuran kejutan dalam suatu himpunan.
Entropi adalah metrik yang mengukur ketidakpastian atau ketidakmurnian dalam sistem.

Dalam pohon keputusan, kita akan mempertimbangkan entropi sebagai ukuran kemurnian di dalam sebuah node. Tujuan dari model pohon keputusan adalah untuk mengurangi entropi node pada setiap pemisahan:

Oleh karena itu, kami ingin memaksimalkan perbedaan antara entropi node induk dan entropi node anak. Perbedaan ini disebut Perolehan informasi.

Entropi $H$ dari himpunan $X$ dirumuskan secara matematis sebagai berikut:

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

Perolehan informasi

Perolehan Informasi adalah selisih antara entropi node induk dan jumlah tertimbang dari entropi node anak, sehingga dapat dirumuskan sebagai berikut:

$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])$

Di mana:

$H(.)$ adalah entropi.
$Y$ adalah populasi sebelum pemisahan, ini mewakili node induk.
$X$ adalah variabel yang ingin kita gunakan untuk pemisahan.
$x$ adalah nilai unik X.
$Y[X==x]$ adalah daftar terpisah dengan hanya nilai $x$ .

mari kita ambil contoh yang tepat:

Kita akan menghitung Perolehan Informasi ketika kita membagi node induk dengan menggunakan nilai X:

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

Pertama, kita menghitung entropi node induk:

$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$

Kemudian, kita akan menghitung probabilitas internal setiap node anak setelah pemisahan dengan menggunakan nilai unik X:

$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)$

Seperti:

$H(Y | X = Square)$ : mewakili entropi node anak pertama.
$H(Y | X = Circle)$ : mewakili entropi node anak kedua.

Kita mulai dengan node anak pertama:

$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$

Dan kemudian simpul anak kedua:

$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$

Terakhir, kami mengganti entropi ke dalam rumus Perolehan Informasi:

$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$

Seperti yang dinyatakan sebelumnya, tujuan pemisahan node adalah untuk memaksimalkan Perolehan Informasi, dan dengan demikian meminimalkan Entropi pada node turunan yang dihasilkan. Untuk melakukan ini, kita perlu mencoba dan membagi node dengan set input berbeda $X_1, X_2, \ldots, Xn$ dan kita hanya menyimpan pemisahan yang memaksimalkan Perolehan Informasi:

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

Kapan harus berhenti membelah

Pemisahan node pada pohon keputusan bersifat rekursif, sehingga harus ada kriteria yang dapat kita gunakan untuk menghentikan pemisahan tersebut. Ini beberapa kriteria yang paling banyak diterapkan:

Jika nodenya murni: H(node) = 0. Tidak ada gunanya membagi node lebih jauh.
Jumlah kedalaman maksimum: Kita dapat menetapkan kedalaman maksimum yang dapat dicapai model, artinya meskipun node tidak murni, pemisahan akan dihentikan.
Jumlah minimum sampel per node: Kami juga dapat menetapkan jumlah minimum $N$ sampel per node. Jika jumlah sampel per node sama dengan $N$ maka kami berhenti memisahkan meskipun node tersebut tidak murni.

Pada akhir pelatihan (pemisahan), setiap node yang bergantung pada akhir pohon keputusan disebut "Leaf", karena node tersebut bukan merupakan akar dari subpohon mana pun. Setiap daun akan mewakili kelas hasil dengan sampel terbanyak.

Kesimpulan

Pohon keputusan adalah salah satu algoritme pembelajaran mesin paling terkenal karena efisiensinya, latar belakang intuitif, dan implementasinya yang sederhana. Algoritme ini selanjutnya dapat digunakan dengan variabel independen numerik (Gaussian Decision Tree), dan juga dapat diperluas untuk menyelesaikan tugas regresi.