Decision Tree Learning: Constructing Decision Tree

Decision Tree Learning (DTL) merupakan salah satu metode dalam pembelajaran mesin untuk menyelesaikan masalah klasifikasi. Berbeda dengan regresi linear yang menggunakan persamaan garis linear sebagai cara memodelkan, DTL menggunakan representasi pohon keputusan (decision tree) untuk memodelkan suatu masalah. Sebagai outputnya DTL akan menghasilkan sekumpulan rules atau aturan yang digunakan untuk mengklasifikasi suatu data baru.

Sebagai contoh misalnya kita ingin mengetahui bagaimana resiko sakit jantung seseorang berdasarkan atribut Umur, Jenis Kelamin, Kebiasaan Diet (Baik/Buruk), dan Status Merokok(Perokok/Bukan Perokok). Yang kita inginkan ialah jika diberikan suatu data baru, kita dapat mengklasifikasi apakah orang tersebut masuk ke dalam kategori dengan resiko sakit jantung yang tinggi atau rendah. Gambar dibawah ini merupakan pohon keputusan untuk masalah tersebut.

Perhatikan bahwa semua atribut input akan menjadi node dalam pohon keputusan dengan jumlah branch sesuai dengan jumlah kategori tiap atribut. Atribut target (resiko sakit jantung) akan menjadi leaf node. Pertanyaan selanjutnya ialah bagaimana membuat pohon keputusan tersebut? Mengapa atribut Merokok yang menjadi root node? Mengapa atribut Jenis Kelamin tidak dilibatkan?

Divide-and-Conquer DTL

Untuk memberikan gambaran bagaimana proses konstruksi pohon keputusan, gw bakal pake dataset dibawah. Dengan dataset ini kita ingin memprediksi apakah suatu komunitas skateboard di Bandung akan menggelar latihan atau tidak berdasarkan data cuaca, suhu, kelembapan, dan kondisi awan.

Cuaca Suhu Kelembapan Berawan Main
 Cerah  Panas  Tinggi  Tidak  Tidak
 Cerah  Panas  Tinggi  Ya  Tidak
 Mendung  Panas  Tinggi  Tidak  Ya
 Hujan  Sejuk  Tinggi  Tidak  Ya
 Hujan  Dingin  Normal  Tidak  Ya
 Hujan  Dingin  Normal  Ya  Tidak
 Mendung  Dingin  Normal  Ya  Ya
 Cerah  Sejuk  Tinggi  Tidak  Tidak
 Cerah  Dingin  Normal  Tidak  Ya
 Hujan  Sejuk  Normal  Tidak  Ya
 Cerah  Sejuk  Normal  Ya  Ya
 Mendung  Sejuk  Tinggi  Ya  Ya
 Mendung  Panas  Normal  Tidak  Ya
 Hujan  Sejuk  Tinggi  Ya  Tidak

Secara umum, proses konstruksi pohon keputusan ialah sebagai berikut:

  • Pertama, pilih sebuah atribut yang akan menjadi node
  • Setelah itu buatlah sejumlah cabang berdasarkan kemungkinan nilai dari atribut tersebut. Hal ini juga akan membagi dataset menjadi beberapa bagian sesuai jumlah cabang.
  • Ulangi proses diatas secara rekursif sampai yang menjadi leaf node ialah nilai dari atribut target.

Proses ini disebut juga proses divideandconquer.

Lalu bagaimana menentukan atribut mana yang harus dipilih menjadi node terlebih dahulu?

Menentukan Root Node

Oke, gw kasih contoh lain dulu. Misalnya kita punya sebuah dataset yang memiliki 10 data dan terdiri dari 3 atribut input dan 1 atribut output. Kita ingin menentukan dari 3 atribut input tersebut atribut mana yang semestinya dipilih terlebih dahulu untuk menjadi node.

 A B C X
 A1  B1  C1  Ya
 A2  B1  C1  Tidak
 A2  B2  C1  Ya
A1  B2  C2  Tidak
 A2  B2  C2  Tidak
 A2  B3  C1  Ya
 A1  B1  C2  Tidak
 A2  B3  C1  Ya
 A1  B3  C1  Ya
 A2  B1  C2  Tidak

Sekarang menurut lo atribut mana yang seharusnya pilihan pertama untuk jadi root node, A, B, atau C?

Harusnya, lo bisa pilih dengan hanya melihat atau menghitung jumlah Ya dan Tidak dalam suatu atribut. Lo bisa lihat bahwa atribut C paling homogen, 5/6 bernilai Ya pada C1 dan 4/4 bernilai Tidak pada C2. Dengan kondisi seperti ini kita akan lebih yakin dalam mengklasifikasi suatu data baru, misalnya kalo ada data dengan nilai C=C2 maka secara pasti output-nya bernilai Tidak (karena berdasarkan dataset, output seluruh data dengan nilai C2 pada atribut C ialah Tidak). Hal ini berbeda kalo ada data baru dengan nilai A=A1, kemungkinannya masih 50:50. Jelas?

Konsep homogenitas diatas dinamakan (im)purity, yaitu seberapa murni output yang dihasilkan dari suatu atribut. Semakin homogen suatu atribut maka purity nya semakin tinggi, begitu juga sebaliknya. Oleh karena itu, kita pilih atribut yang memiliki purity yang paling tinggi. Secara kuantitatif, kita bisa menghitung kadar purity atau impurity berdasarkan nilai entropi. Entropi ini mirip dengan entropi dalam kimia yang menggambarkan tingkat ketidakteraturan suatu sistem. Semakin tinggi nilai entropi maka semakin tinggi ketidakteraturannya, atau dengan kata lain semakin tinggi impurity nya. Sebaliknya, semakin rendah nilai entropi maka semakin teratur, semakin homogen, semakin tinggi purity nya. Kita ingin mencari atribut yang memiliki nilai entropi terendah atau information gain tertinggi untuk dipilih sebagai node.

$$E(a_1, a_2, …, a_n)=-p_1 log_2 p_1-p_2 log_2 p_2…-p_n log_2 p_n$$

dimana $n$ merupakan jumlah kemungkinan output. Kalo kemungkinan output-nya Ya atau Tidak maka $n=2$. $a_1, a_2, …, a_n$ merupakan jumlah output suatu data. $p_1, p_2, …, p_n$ merupakan probabilitas output suatu data dimana $p_1=\frac{a_1}{a_1+a_2+…+a_n}$. Pada data skateboard diatas, output-nya terdiri dari 9 Ya dan 5 Tidak, sehingga:

$$E(9, 5)=-\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940$$

Nilai entropi berkisar antara nol hingga $log_2(jumlah kemungkinan output)$. Jadi untuk data skateboard, yang merupakan klasifikasi biner, nilai entropi berkisar dari nol sampai $log_2(2)$, atau dari 0-1.

Selanjutnya kita hitung entropi tiap atribut. Untuk atribut Cuaca terdiri dari 3 kemungkinan nilai (Cerah, Mendung, Hujan) dengan distribusi sebagai berikut:

 Ya  Tidak
 Cerah  2  3  5
 Mendung  4  0  4
 Hujan  3 2  5

Sebelum menghitung entropi atribut Cuaca, kita hitung terlebih dahulu entropi tiap-tiap kemungkinan nilainya.

$$E(\text{Cerah})=E(2, 3)=0.971$$

$$E(\text{Mendung})=E(4, 0)=0$$

$$E(\text{Hujan})=E(3, 2)=0.971$$

Selanjutnya entropi Cuaca dihitung secara kumulatif dengan pembobotan

$$E(\text{Cuaca})= P(\text{Cerah}) \times E(\text{Cerah}) + P(\text{Mendung}) \times E(\text{Mendung}) + P(\text{Hujan}) \times E(\text{Hujan})$$

$$E(\text{Cuaca})=\frac{5}{14} \times 0.971 + \frac{4}{14} \times 0 + \frac{5}{14} \times 0.971$$

$$E(\text{Cuaca})=0.693$$

Setelah kita mendapatkan nilai entropi calon atribut dan parent node, selanjutnya kita hitung information gain untuk atribut tersebut. Information gain merupakan selisih antara entropi parent node dengan entropi calon atribut. Information gain menggambarkan seberapa besar ketidakpastian yang  dapat dihindari jika memilih atribut tersebut. Oleh karena itu kita mencari atribut yang memiliki information gain tertinggi.

$$Gain(\text{Cuaca})=0.940-0.693=0.247$$

Dengan cara yang sama kita dapat menghitung entropi untuk semua atribut lain, sehingga akan menghasilkan:

$Gain(\text{Cuaca})=0.247$

$Gain(\text{Suhu})=0.029$

$Gain(\text{Kelembapan})=E(\text{Kelembapan})=0.152$

$Gain(\text{Berawan})=E(\text{Berawan})=0.048$

Dari keempat information gain diatas, atribut Cuaca memiliki information gain yang paling tertinggi, sehingga atribut ini yang kita jadikan node. Dari node ini terbentuk 3 cabang, masing-masing untuk Cerah, Mendung, dan Hujan.

Menentukan Internal Node

Langkah selanjutnya setelah kita dapatkan root node beserta cabang-cabangnya ialah melakukan langkah sebelumnya secara rekursif. Sekarang gw akan perlihatkan bagaimana menentukan atribut yang tepat untuk cabang Cuaca=Cerah. Kita pilih data yang memilki Cuaca=Cerah sehingga tampak seperti dataset berikut.

Suhu Kelembapan Berawan Main
 Panas  Tinggi  Tidak  Tidak
 Panas  Tinggi  Ya  Tidak
 Sejuk  Tinggi  Tidak  Tidak
 Dingin  Normal  Tidak  Ya
 Sejuk  Normal  Ya  Ya

Selanjutnya kita hitung entropi tiap atribut. Untuk atribut Suhu terdiri dari 3 kemungkinan nilai (Panas, Sejuk, Dingin) dengan distribusi sebagai berikut:

 Ya  Tidak
 Panas  0  2  2
 Sejuk  1  1  2
 Dingin  1  0  1

Pertama, kita hitung entropi dataset ini, yang merupakan parent node

E(\text{Parent Node})=E(2, 3)==-\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}=0.971$$

Selanjutnya kita hitung entropi untuk atribut Cuaca dengan terlebih dahulu menghitung entropi tiap-tiap kemungkinan nilainya.

$$E(\text{Panas})=E(0, 2)=0$$

$$E(\text{Sejuk})=E(1, 1)=1$$

$$E(\text{Dingin})=E(1, 0)=0$$

Selanjutnya entropi Suhu dihitung secara kumulatif dengan pembobotan

$$E(\text{Suhu})= P(\text{Panas}) \times E(\text{Panas}) + P(\text{Sejuk}) \times E(\text{Sejuk}) + P(\text{Dingin}) \times E(\text{Dingin})$$

$$E(\text{Suhu})=\frac{2}{5} \times 0 + \frac{2}{5} \times 1 + \frac{1}{5} \times 0$$

$$E(\text{Suhu})=0.4$$

$$Gain(\text{Suhu})=Entropi(\text{Parent Node})-Entropi(\text{suhu})=0.971-0.4=0.571$$

Dengan cara yang sama kita dapat menghitung entropi untuk semua atribut lain, sehingga akan menghasilkan:

$Gain(\text{Suhu})=0.571$

$Gain(\text{Suhu})=0.971$

$Gain(\text{Suhu})=0.020$

Dari ketig information gain diatas, atribut Kelembapan memiliki information gain yang paling tinggi, sehingga atribut ini yang kita jadikan node. Dari node ini terbentuk 2 cabang, masing-masing untuk Tinggi dan Normal.

Langkah-langkah diatas diulangi sehingga hasil akhirnya akan tampak seperti pohon keputusan berikut:

Atribut Super

Dari dataset saat ini misalnya gw tambah sebuah atribut baru bernama Hari yang kemungkinan nilainya mulai dari H1 sampai H14.

Hari Cuaca Suhu Kelembapan Berawan Main
 H1  Cerah  Panas  Tinggi  Tidak  Tidak
 H2  Cerah  Panas  Tinggi  Ya  Tidak
 H3  Mendung  Panas  Tinggi  Tidak  Ya
 H4  Hujan  Sejuk  Tinggi  Tidak  Ya
 H5  Hujan  Dingin  Normal  Tidak  Ya
 H6  Hujan  Dingin  Normal  Ya  Tidak
 H7  Mendung  Dingin  Normal  Ya  Ya
 H8  Cerah  Sejuk  Tinggi  Tidak  Tidak
 H9  Cerah  Dingin  Normal  Tidak  Ya
 H10  Hujan  Sejuk  Normal  Tidak  Ya
 H11  Cerah  Sejuk  Normal  Ya  Ya
 H12  Mendung  Sejuk  Tinggi  Ya  Ya
 H13  Mendung  Panas  Normal  Tidak  Ya
 H14  Hujan  Sejuk  Tinggi  Ya  Tidak

Apa yang akan terjadi terhadap pohon keputusan setelah penambahan atribut ini? Coba kita cari dulu root node nya dengan menghitung entropi Hari.

$$E(\text{Hari})=\frac{1}{14} \times E(0, 1) + \frac{1}{14} \times E(0, 1) + … + \frac{1}{14} \times E(0, 1)$$

Nilai dari $E(0, 1)$ adalah $0$ sehingga $E(\text{Hari})=0$. Ini artinya, atribut Hari memiliki entropi yang paling rendah atau information gain yang paling tinggi sehingga otomatis menjadi root node. Root node dengan 14 cabang!

Gimana kalo punya data baru dengan Hari=H32, Cuaca=Cerah, Suhu=Panas, Kelembapan=Tinggi, dan Berawan=Ya? Gak bisa coy! Dengan kondisi seperti ini kita tidak bisa melakukan prediksi, bahkan pohon keputusan tersebut tidak memberikan informasi bermanfaat mengenai proses klasifikasi. Inilah yang disebut atribut super.

Lalu bagaimana mengatasinya?

Kita bisa atasi dengan memberikan penalti berdasarkan banyak cabang. Semakin banyak cabang makin besar penaltinya. Penalti ini dinamakan Split Information. Split information menunjukkan seberapa murni cabang suatu atribut. Jika semakin sedikit maka semakin murni, begitu pula sebaliknya. Oleh karena itu perhitungan penalti atau split information ini menggunakan perhitungan entropi. Misalnya split information atribut Cuaca ialah:

$$SplitInfo(\text{Cuaca})=E(5, 4, 5)=-\frac{5}{14}log_2\frac{5}{14}-\frac{4}{14}log_2\frac{4}{14}-\frac{5}{14}log_2\frac{5}{14}$$

$$SplitInfo(\text{Cuaca})=1.577$$

Dengan cara yang sama maka split information dari atribut Hari ialah 3.807. Selanjutnya untuk menentukan atribut mana yang dipilih sebagai node, kita hitung berdasarkan nilai Gain dibagi SplitInfo. Nilai ini dinamakan GainRatio.

$$GainRatio(Atribut)=\frac{Gain(Atribut)}{SplitInfo(Atribut)}$$

Berikut ini GainRatio untuk seluruh atribut diatas:

$$GainRatio(Hari)=0.247$$

$$GainRatio(Cuaca)=0.156$$

$$GainRatio(Temperature)=0.019$$

$$GainRatio(Kelembapan)=0.152$$

$$GainRatio(Berawan)=0.049$$

Mengapa gain ratio atribut Hari masih yang tertinggi? Hal ini karena data yang sedikit. Bayangkan jika ada 200 instances unik, maka split information akan jauh lebih besar dan gain ratio yang dihasilkan akan jauh lebih kecil.

One thought on “Decision Tree Learning: Constructing Decision Tree

Leave a Reply

Your email address will not be published. Required fields are marked *