Algoritma ID3

Daftar Isi “Algoritma ID3“

1. Pengertian Algoritma ID3
2. Kelebihan & Kekurangan Pohon Keputusan atau Decision Tree
3. Arsitektur Pohon Keputusan
4. Langkah-Langkah Konstruksi Pohon Keputusan dengan Algoritma ID3
5. Entropy & Information Gain
6. Latihan Soal 1
7. Latihan Soal 2

1. Pengertian Algoritma ID3

Algoritma ID3 merupakan algoritma yang dipergunakan untuk membangun sebuah decision tree atau pohon keputusan. Algoritma ini ditemukan oleh J. Ross Quinlan (1979), dengan memanfaatkan Teori Informasi atau Information Theory milik Shanon. ID3 sendiri merupakan singkatan dari Iterative Dichotomiser 3.

Decision tree menggunakan struktur hierarki untuk pembelajaran supervised. Proses dari decision tree dimulai dari root node hingga leaf node yang dilakukan secara rekursif. Di mana setiap percabangan menyatakan suatu kondisi yang harus dipenuhi dan pada setiap ujung pohon menyatakan kelas dari suatu data.

Proses dalam decision tree yaitu mengubah bentuk data (tabel) menjadi model pohon (tree) kemudian mengubah model pohon tersebut menjadi aturan (rule).

Dengan pendekatan ini, salah satu kelemahan algoritma dari decision tree, adalah faktor skalabilitas dimana algoritma tersebut hanya dapat digunakan untuk menangani sampel-sampel yang dapat disimpan secara keseluruhan dan pada waktu yang bersamaan di memori.

Algoritma ID3 tidak pernah melakukan backtracking untuk merevisi keputusan pemilihan attribute yang telah dilakukan sebelumnya. ID3 hanya menangani nilai-nilai attribute yang sedikit dan diskret, tetapi algoritma modifikasinya, algoritma C4.5 (1993), selanjutnya mampu menangani nilai attribute kontinu.

2. Kelebihan & Kekurangan Pohon Keputusan atau Decision Tree

Metode pohon keputusan mempunyai beberapa kelebihan, diantaranya sebagai berikut :

1. Daerah pengambilan keputusan yang sebelumnya kompleks dan sangat global, dapat diubah menjadi simple dan spesifik.
2. Eliminasi perhitungan-perhitungan yang tidak diperlukan, karena ketika menggunakan metode pohon keputusan maka contoh diuji hanya berdasarkan kriteria atau kelas-kelas tertentu.
3. Fleksibel untuk memilih fitur dari internal node yang berbeda, fitur yang terpilih akan membedakan suatu kriteria dibandingkan kriteria yang lain dalam node yang sama.
4. Metode pohon keputusan dapat menghindari munculnya permasalahan ini dengan menggunakan kriteria yang jumlahnya lebih sedikit pada setiap node internal tanpa banyak mengurangi kualitas keputusan yang dihasilkan.

Selain kelebihan dari pohon keputusan, terdapat juga beberapa kekurangan dari pohon keputusan, diantaranya sebagai berikut :

1. Terjadi overlap terutama ketika kelas-kelas dan kriteria yang digunakan jumlahnya sangat banyak. Hal tersebut juga dapat menyebabkan meningkatnya waktu pengambilan keputusan dan jumlah memori yang diperlukan.
2. Pengakumulasian jumlah eror dari setiap tingkat dalam sebuah pohon keputusan yang besar.
3. Kesulitan dalam mendesain pohon keputusan yang optimal
4. Hasil kualitas keputusan yang didapatkan dari metode pohon keputusan sangat tergantung pada bagaimana pohon tersebut didesain.

3. Arsitektur Pohon Keputusan

Arsitektur pohon keputusan dibuat menyerupai bentuk pohon, dimana pada umumnya sebuah pohon terdapat akar (root), cabang dan daun (leaf). Pada pohon keputusan juga terdiri  dari tiga bagian sebagai berikut :

a. Root node atau node akar merupakan node yang terletak paling atas dari suatu pohon.

b. Internal Node ini merupakan node percabangan, dimana pada node ini hanya terdapat satu input dan mempunyai minimal dua output.

c. Leaf Node ini merupakan node akhir, hanya memiliki satu input, dan tidak memiliki output. Pada pohon keputusan setiap leaf node menandai label kelas.

Pada pohon keputusan di setiap percabangan menyatakan kondisi yang harus dipenuhi dan tiap ujung pohon menyatakan nilai kelas data. Gambar berikut merupakan bentuk arsitektur pohon keputusan.

Arsitektur Pohon Keputusan

4. Langkah-Langkah Konstruksi Pohon Keputusan dengan Algoritma ID3

Adapun langkah-langkah dalam konstruksi pohon keputusan adalah sebagai berikut :

Langkah 1 : Pohon dimulai dengan sebuah simpul yang mereperesentasikan sampel data pelatihan yaitu dengan membuat simpul akar.

Langkah 2 : Jika semua sampel berada dalam kelas yang sama, maka simpul ini menjadi daun dan dilabeli menjadi kelas. Jika tidak, information gain akan digunakan untuk memilih atribut terbaik dalam memisahkan data sampel menjadi kelas-kelas individu.

Langkah 3 : Cabang akan dibuat untuk setiap nilai pada atribut dan data sampel akan dipartisi lagi.

Langkah 4 : Algoritma ini menggunakan proses rekursif untuk membentuk pohon keputusan pada setiap data partisi. Jika sebuah atribut sduah digunakan disebuah simpul, maka atribut ini tidak akan digunakan lagi di simpul anak-anaknya.

Langkah 5 : Proses ini berhenti jika dicapai kondisi seperti berikut :

– Semua sampel pada simpul berada di dalam satu kelas

– Tidak ada atribut lainnya yang dapat digunakan untuk mempartisi sampel lebih lanjut. Dalam hal ini akan diterapkan suara terbanyak. Ini berarti mengubah sebuah simpul menjadi daun dan melabelinya dnegan kelas pada suara terbanyak.

5. Entropy & Information Gain

Algoritma pada metode ini menggunakan konsep dari entropi. Konsep Entropi yang digunakan untuk mengukur “seberapa informatifnya” sebuah node (yang biasanya disebut seberapa baiknya).

Entropi(S) = 0, jika semua contoh pada S berada dalam kelas yang sama.
Entroiy(S) = 1, jika jumlah contoh positif dan jumlah contoh negatif dalam S adalah sama.
0 < Entropi(S) < 1, jika jumlah contoh positif dan negatif dalam S tidak sama.

formula entropi

Dimana:
• S adalah himpunan (dataset) kasus
• k adalah banyaknya partisi S
• p_j adalah probabilitas yang di dapat dari Sum(Ya) dibagi Total Kasus.

Setelah mendapat nilai entropi, pemilihan atribut dilakukan dengan nilai information gain terbesar.

information gain

Dimana:
S = ruang (data) sample yang digunakan untuk training.
A = atribut.
|S_i| = jumlah sample untuk nilai V.
|S| = jumlah seluruh sample data.
Entropi(S_i) = entropy untuk sample-sample yang memiliki nilai i

6. Latihan Soal 1

Data yang telah ada pada Tabel dibawah akan digunakan untuk membentuk pohon keputusan dimana memiliku atribut-atribut seperti Cuaca, Suhu, Kelembaban, dan Berangin. Setiap atribut memiliki nilai. Sedangkan kelasnya ada pada kolom Main yaitu kelas “Tidak” dan kelas “Ya”. Kemudian data tersebut dianalisis; dataset tersebut memiliki 14 kasus yang terdiri 10 “Ya” dan 4 “Tidak” pada kolom Main.

learning dataset

Kemudian hitung entropi dengan rumus seperti diatas.

Entropi (S) = (-(10/14) x log₂ (10/14) + (-(4/10) x log₂ (4/10)) = 0.863120569

hasil perhitungan entropi

Setelah mendapatkan entropi dari keseluruhan kasus, lakukan analisis pada setiap atribut dan nilai-nilainya dan hitung entropinya.

analisis atribut, nilai, banyaknya kejadian, entropi dan gain

Setelah mendapatkan nilai entropy, berikutnya hitung nilai information gain dari setiap variabel.

Gain (Cuaca) = 0.863120569 –  ((4/10) x 0 + (5/14) x 0.721928095 + (5/14) x 0.970950594) = 0.258521037

Hitung pula Gain (Suhu), Gain (Kelembaban), dan Gain (Berangin). Karena nilai gain terbesar adalah Gain (Kelembaban), maka atribut “Kelembaban” menjadi node akar (root node).

Kemudian pada “Kelembaban” normal, memiliki 7 kasus dan semuanya memiliki jawaban Ya (Sum(Total) / Sum(Ya) = 7/7 = 1). Dengan demikian “Kelembaban” normal menjadi daun atau leaf.

pohon keputusan node 1 (root node)

Berdasarkan pembentukan pohon keputusan node 1 (root node), Node 1.1 akan dianalisis lebih lanjut. Untuk mempermudah, Tabel dibawah difilter, dengan mengambil data yang memiliki “Kelembaban” = Tinggi.

atribut data kelembaban = tinggi

Kemudian dihitung nilai entropi atribut “Kelembaban” Tinggi dan entropi setiap atribut serta gainnya. Setelah itu tentukan pilih atribut yang memiliki gain tertinggi untuk dibuatkan node berikutnya.

hasil analisis node 1.1

Gain tertinggi yang didapat ada pada atribut “Cuaca”, dan Nilai yang dijadikan daun atau leaf adalah Berawan dan Cerah. Jika divualisasi maka pohon keputusan tampak seperti Gambar dibawah.

Untuk menganalisis node 1.1.2, lakukan lagi langkah-langkah yang sama seperti sebelumnya hingga semua node beberntuk node leaf.

pohon keputusan analisis node 1.1

hasil analisis node 1.1.2.

pohon keputusan akhir

7. Latihan Soal 2

Terdapat data pelamar pekerjaan beserta hasil penerimaannya pada sebuah Bank. Pada tabel berikut terdapat 10 atribut yaitu bagian pekerjaan yang akan dicari, pendidikan terakhir, jurusan sewaktu kuliah, IPK terakhir, hasil wawancara, kelengkapan berkas pelamar, kerapian penampilan pelamar, umur, status pelamar dan hasil penerimaan kerja. Buatlah pohon keputusan dengan menggunakan algoritma ID3 !

dataset pelamar pekerjaan

Dari kasus diatas akan dibuat sebuah pohon keputusan untuk menentukan pelamar baru apakah diterima atau tidak. Berikut rincian langakah penyelasaian dalam pemebentukan pohon keputusan.

Langkah 1 : Menghitung nilai entropy dan nilai gain

Lakukan perhitungan untuk jumlah kasus keseluruhan yang ada, jumlah kasus untuk hasil Lulus dan juga jumlah kasus untuk hasil Tidak Lulus. Kemudian lakukan perhitungan untuk mencari nilai Entropy dari setiap nilai atribut dan nilai Gain untuk setiap atribut.

Jumlah kasus : 30
Jumlah kasus dengan hasil Lulus : 19
Jumlah kasus dengan hasil Tidak Lulus : 11

Hitung nilai entropy dari total kasus :

Entropi (S) = (-(19/30) x log₂ (19/30) + (-(11/30) x log₂ (11/30)) = 0.4174 + 0.5307 = 0.9481

Lakukan perhitungan untuk nilai entropy pada setiap atribut :

Entropy (bagian=teller) =  (-(7/14) x log₂ (7/14) + (-(7/14) x log₂ (7/14)) = 0.5 + 0.5 = 1
Entropy (bagian=marketing) = (-(4/5) x log₂ (4/5) + (-(1/5) x log₂ (1/5)) = 0.2575 + 0.4644 = 0.7219
Entropy (bagian=IT) = (-(3/4) x log₂ (3/4) + (-(1/4) x log₂ (1/4)) = 0.3113 + 0.5 = 0.8113
Entropy (bagian=call centre) = (-(1/2) x log₂ (1/2) + (-(1/2) x log₂ (1/2)) = 0.5 + 0.5 = 1
Entropy (bagian=cust.service) = (-(4/5) x log₂ (4/5) + (-(1/5) x log₂ (1/5)) = 0.2575 + 0.4644 = 0.7219
Entropy (pendidikan=D1) = (-(1/2) x log₂ (1/2) + (-(1/2) x log₂ (1/2)) = 0.5 + 0.5 = 1
Entropy (pendidikan=D2) = (-(1/2) x log₂ (1/2) + (-(1/2) x log₂ (1/2)) = 0.5 + 0.5 = 1
Entropy (pendidikan=D3) = (-(1/3) x log₂ (1/3) + (-(2/3) x log₂ (2/3)) = 0.5283 + 0.39 = 0.9183

:
:
:

Entropy (status=menikah) = (-(7/11) x log₂ (7/11) + (-(4/11) x log₂ (4/11)) = 0.4150 + 0.5307 = 0.9457
Entropy (status=bercerai) = (-(1/3) x log₂ (1/3) + (-(2/3) x log₂ (2/3)) = 0.5283 + 0.39 = 0.9183

Setelah dicari nilai entropy pada setiap nilai dari atribut yang ada, kemudian lakukan perhitungan untuk mencari nilai gain dari setiap atribut.

Gain(bagian) = 0,9481 – ((14/30*1) + (5/30*0,7219) + (4/30*0,8113) + (2/30*1) + (5/30*0,7219)) = 0,0659
Gain(pendidikan) = 0,9481 – ((2/30*1) + (2/30*2) + (3/30*0,8113) + (16/30*0,9544) + (7/30*0,5917)) = 0,0758
Gain(jurusan) = 0,9481 – ((11/30*0,9940) + (10/30*0,9710) + (6/30*0,9183) + (3/30*0)) = 0,0763
Gain(ipk) = 0,9481 – ((4/30*0) + (10/30*0,9710) + (12/30*0,4138) + (4/30*0)) = 0,4589
Gain(wawancara) = 0,9481 – ((14/30*0,5917) + (10/30*0,9710) + (6/30*0,6500)) = 0,2183
Gain(berkas) = 0,9481 – ((19/30*0,8315) + (11/30*1)) = 0,0570
Gain(kerapian) = 0,9481 – ((15/30*0,971) + (9/30*0,9183) + (6/30*0,9183)) = 0,0035
Gain(umur) = 0,9481 – ((5/30*1) + (13/30*0,6194) + (8/30*1) + (4/30*0,8113)) = 0,1430
Gain(status) = 0,9481 – ((16/30*0,8960) + (11/30*0,9547) + (3/30*0,9183)) = 0,0316

entropy dan information gain

Langkah 2 : Menentukan node akar

1. Dari hasil perhitungan pada tabel diatas, diketahui bahwa nilai Gain terbesar yaitu pada atribut IPK yaitu sebesar 0,4589. Sehingga atribut IPK menjadi node akar.
2. Pada atribut IPK terdapat 4 nilai atribut, yaitu <2.5, 2.5-3, 3-3.5, >3.5. Nilai atribut yang pertama yaitu <2.5 sudah mengklasifikasikan kasus menjadi 1 yaitu dengan hasil Tidak Lulus sehingga tidak perlu dilakukan perhitungan lebih lanjut.
3. Dan nilai atribut keempat >3,5 sudah mengklasifikasikan kasus menjadi 1 yaitu dengan hasil Lulus, sehingga tidak perlu dilakukan perhitungan lebih lanjut.
4. Sedangkan nilai atribut kedua dan ketiga yaitu 2.5–3 dan 3-3.5 belum mengklasifikasikan kasus menjadi satu keputusan sehingga perlu dilakukan perhitungan lagi.

decision tree iterasi 1

Langkah 3 : Mencari node cabang

Perhitungan dilakukan untuk mencari node cabang dari nilai atribut 2.5-3. Perhitungan dilakukan dengan mencari nilai dari atribut selain yang menjadi node akar (IPK), yaitu dengan mencari jumlah kasus untuk hasil Lulus dan Tidak Lulus, dan nilai Entropy dari semua kasus saat IPK = 2.5–3. Dan kemudian lakukan perhitungan untuk mencari nilai Gain, dan atribut dengan nilai Gain terbesar, maka akan menjadi node cabang dari nilai atribut 2.5-3.

Node 1.2 :

Jumlah kasus dengan IPK = 2,5–3 : 10
Jumlah kasus dengan IPK = 2,5–3 yang hasil Lulus : 4
Jumlah kasus dengan IPK = 2,5–3 yang hasil Tidak Lulus : 6

Hitung nilai entropy dari total kasus :

Entropi (S) = (-(4/10) x log₂ (4/10) + (-(6/10) x log₂ (6/10)) = 0.9481

Lakukan perhitungan untuk nilai entropy pada setiap atribut, kecuali pada atibut IPK :

Entropy (bagian = teller) = (-(2/6) x log₂ (2/6) + (-(4/6) x log₂ (4/6)) = 0.9183
Entropy (bagian = marketing) = (-(0/1) x log₂ (0/1) + (-(1/1) x log₂ (1/1)) = 
Entropy (bagian = IT) = (-(1/2) x log₂ (1/2) + (-(1/2) x log₂ (1/2)) = 1
Entropy (bagian = call centre) = (-(0/0) x log₂ (0/0) + (-(0/0) x log₂ (0/0)) = 
Entropy (bagian = cust. service) = (-(1/1) x log₂ (1/1) + (-(0/1) x log₂ (0/1)) =
Entropy (pendidikan = D1) = (-(0/0) x log₂ (0/0) + (-(0/0) x log₂ (0/0)) = 
Entropy (pendidikan = D2) = (-(1/1) x log₂ (1/1) + (-(0/1) x log₂ (0/1)) = 
Entropy (pendidikan = D3) = (-(0/1) x log₂ (0/1) + (-(1/1) x log₂ (1/1)) = 

:
:
:

Entropy (status = menikah) = (-(2/3) x log₂ (2/3) + (-(1/3) x log₂ (1/3)) = 0.9183
Entropy (status = bercerai) = (-(1/3) x log₂ (1/3) + (-(2/3) x log₂ (2/3)) = 0.9183

Setelah dicari nilai entropy pada setiap nilai dari atribut yang ada, kemudian lakukan perhitungan untuk mencari nilai gain dari setiap atribut.

Gain(bagian) = 0,9710 – ((6/10*0,9183) + (1/10*0) + (2/10*1) + (0/10*0) + (1/10*0)) = 0,22
Gain(pendidikan) = 0,9710 – ((0/10*0) + (1/10*0) + (1/10*0) + (6/10*0,9183) + (2/10*1)) = 0,22
Gain(jurusan) = 0,9710 – ((4/10*0,8113) + (3/10*0,9183) + (2/10*1) + (1/10*0)) = 0,171
Gain(wawancara) = 0,9710 – ((3/10*0,9183) + (4/10*0,8113) + (3/10*0,9183)) = 0,0955
Gain(berkas) = 0,9710 – ((4/10*1) + (6/10*0,9183)) = 0,002
Gain(kerapian) = 0,9710 – ((5/10*0,7219) + (3/10*0,9183) + (2/10*1)) = 0,1345
Gain(umur) = 0,9710 – ((1/10*0) + (3/10*0,9183) + (4/10*0,8113) + (2/10*0)) = 0,3710
Gain(status) = 0,9710 – ((4/10*0,8113) + (3/10*0,9183) + (3/10*0,9183)) = 0,0955

tree-node-1.2

Dari hasil perhitungan pada tabel diatas, diketahui bahwa nilai Gain terbesar yaitu pada atribut Umur yaitu sebesar 0,3710. Sehingga atribut Umur menjadi node cabang dari nilai atribut 2.5-3.

Pada atribut Umur terdapat 4 nilai atribut, yaitu ≤23, 24-27, 28-30, >30. Nilai atribut yang pertama yaitu ≤23 sudah mengklasifikasikan kasus menjadi 1 yaitu dengan hasil Lulus sehingga tidak perlu dilakukan perhitungan lebih lanjut.

Dan nilai atribut keempat yaitu >30 sudah mengklasifikasikan kasus menjadi 1 yaitu dengan hasil Tidak Lulus, sehingga tidak perlu dilakukan perhitungan lebih lanjut.

Sedangkan nilai atribut kedua dan ketiga yaitu 24-27 dan 28-30 belum mengklasifikasikan kasus menjadi satu keputusan sehingga perlu dilakukan perhitungan lagi. Dari proses tersebut maka dapat dihasilkan pohon sementara seperti berikut ini.

Dari proses tersebut maka dapat dihasilkan pohon sementara seperti berikut ini.

decision tree iterasi 2

Kemudian lakukan juga perhitungan untuk mencari node cabang dari nilai atribut 3-3.5. Perhitungan dilakukan dengan mencari nilai dari atribut selain yang menjadi node akar (IPK), yaitu dengan mencari jumlah kasus untuk hasil Lulus dan Tidak Lulus, dan nilai Entropy dari semua kasus saat IPK = 3-3.5. Dan kemudian lakukan perhitungan untuk mencari nilai Gain, dan atribut dengan nilai Gain terbesar, maka akan menjadi node cabang dari nilai atribut 3-3.5.

Node 1.3 :

Jumlah kasus dengan IPK = 3–3,5 : 12
Jumlah kasus dengan IPK = 3–3,5 yang hasil Lulus : 11
Jumlah kasus dengan IPK = 3–3,5 yang hasil Tidak Lulus : 1

Hitung nilai entropy dari total kasus :

Entropi (S) = (-(11/12) x log₂ (11/12) + (-(1/12) x log₂ (1/12)) = 0.4138

Lakukan juga perhitungan untuk nilai entropy pada setiap atribut, kecuali pada atibut IPK :

Entropy (bagian = teller) = (-(4/5) x log₂ 4/5) + (-(1/5) x log₂ (1/5)) = 0.7219
Entropy (bagian = marketing) = (-(3/3) x log₂ (3/3) + (-(0/3) x log₂ (0/3)) = 
Entropy (bagian = IT) = (-(0/0) x log₂ (0/0) + (-(0/0) x log₂ (0/0)) =
Entropy (bagian = call centre) = (-(1/1) x log₂ (1/1) + (-(0/1) x log₂ (0/1)) = 
Entropy (bagian = cust. service) = (-(3/3) x log₂ (3/3) + (-(0/3) x log₂ (0/3)) = 
Entropy (pendidikan = D1) = (-(1/1) x log₂ (1/1) + (-(0/1) x log₂ (0/1)) = 
Entropy (pendidikan = D2) = (-(0/1) x log₂ (0/1) + (-(1/1) x log₂ (1/1)) = 
Entropy (pendidikan = D3) = (-(1/1) x log₂ (1/1) + (-(0/1) x log₂ (0/1)) = 

:
:
:

Entropy (status = menikah) = (-(4/5) x log₂ (4/5) + (-(1/5) x log₂ (1/5)) = 0.7219
Entropy (status = bercerai) = (-(0/0) x log₂ (0/0) + (-(0/0) x log₂ (0/0)) = 

Setelah dicari nilai entropy pada setiap nilai dari atribut yang ada, kemudian lakukan perhitungan untuk mencari nilai gain dari setiap atribut.

Gain(bagian) = 0,4138 – ((4/12*0,7219) + (3/12*0) + (0/12*0) + (1/12*0) + (3/12*0)) = 0,1130
Gain(pendidikan) = 0,4138 – ((1/12*0) + (1/12*0) + (1/12*0) + (6/12*0) + (3/12*0)) = 0,4138
Gain(jurusan) = 0,4138 – ((4/12*0) + (5/12*0,7219) + (1/12*0) + (2/12*0)) = 0,113
Gain(wawancara) = 0,4138 – ((8/12*0,5436) + (4/12*0) + (0/12*0)) = 0,0514
Gain(berkas) = 0,4138 – ((9/12*0,5033) + (3/12*0)) = 0,0364
Gain(kerapian) = 0,4138 – ((6/12*0) + (3/12*0,9183) + (3/12*0)) = 0,1842
Gain(umur) = 0,4138 – ((2/12*0) + (7/12*0) + (1/12*0) + (2/12*1)) = 0,2472
Gain(status) = 0,4138 – ((7/12*0) + (5/12*0,7219) + (0/12*0)) = 0,1130

tree-node-1.3

Dari hasil perhitungan pada tabel diatas, diketahui bahwa nilai Gain terbesar yaitu pada atribut Pendidikan yaitu sebesar 0,4138. Sehingga atribut Pendidikan menjadi node cabang dari nilai atribut 3-3.5.

Pada atribut Pendidikan terdapat 5 nilai atribut, dimana semua analisis atribut sudah mengklasifikasikan kasus menjadi 1 yaitu dengan hasil Lulus, Tidak Lulus, Lulus, Lulus dan Lulus sehingga tidak perlu dilakukan perhitungan lebih lanjut. Dari proses tersebut maka dapat dihasilkan pohon sementara seperti berikut ini.

decision tree iterasi 3

Lakukan perhitungan untuk mencari node cabang dari nilai atribut umur 24-27. Perhitungan dilakukan dengan mencari nilai dari atribut selain yang menjadi node akar (IPK) dan node cabang (Umur), yaitu dengan mencari jumlah kasus untuk hasil Lulus dan Tidak Lulus, dan nilai Entropy dari semua kasus saat IPK = 2.5–3 dan Umur = 24-27. Dan kemudian lakukan perhitungan untuk mencari nilai Gain, dan atribut dengan nilai Gain terbesar, maka akan menjadi node cabang dari nilai atribut 24-27.

Node 1.2.2 :

Jumlah kasus dengan IPK = 2,5–3 dan UMUR = 24-27 : 3
Jumlah kasus dg IPK = 3–3,5 dan UMUR = 24-27 yang hasil Lulus : 2
Jumlah kasus dg IPK = 3–3,5 dan UMUR = 24–27 yang hasil Tidak Lulus : 1

Hitung nilai entropy dari total kasus :

Entropi (S) = (-(2/3) x log₂ (2/3) + (-(1/3) x log₂ (1/3)) = 0.9183

Lakukan perhitungan untuk nilai entropy pada setiap atribut, kecuali pada atibut IPK :

Entropy (bagian = teller) = (-(1/1) x log₂ 1/1) + (-(0/1) x log₂ (0/1)) = 
Entropy (bagian = marketing) = (-(0/0) x log₂ (0/0) + (-(0/0) x log₂ (0/0)) = 
Entropy (bagian = IT) = (-(0/1) x log₂ (0/1) + (-(1/1) x log₂ (1/1)) =
Entropy (bagian = call centre) = (-(0/0) x log₂ (0/0) + (-(0/0) x log₂ (0/0)) = 
Entropy (bagian = cust. service) = (-(1/1) x log₂ (1/1) + (-(0/1) x log₂ (0/1)) = 

:
:
:

Entropy (status = menikah) = (-(1/1) x log₂ (1/1) + (-(0/1) x log₂ (0/1)) = 
Entropy (status = bercerai) = (-(0/0) x log₂ (0/0) + (-(0/0) x log₂ (0/0)) = 

Setelah dicari nilai entropy pada setiap nilai dari atribut yang ada, kemudian lakukan perhitungan untuk mencari nilai gain dari setiap atribut.

Gain(bagian) = 0,9183 – ((1/3*0) + (0/3*0) + (1/3*0) + (0/3*0) + (1/3*0)) = 0,9
Gain(pendidikan) = 0,9183 – ((0/3*0) + (0/3*0) + (1/3*0) + (2/3*0) + (1/3*0)) = 0,9183
Gain(jurusan) = 0,9183 – ((1/3*0) + (0/3*0) + (1/3*0) + (1/3*0)) = 0,9183
Gain(wawancara) = 0,9183 – ((1/3*0) + (2/3*1) + (0/3*0)) = 0,2516
Gain(berkas) = 0,9183 – ((2/3*0) + (1/3*0)) = 0,9183
Gain(kerapian) = 0,9183 – ((1/3*0) + (1/3*0) + (1/3*0)) = 0,9183
Gain(status) = 0,9183 – ((2/3*1) + (1/3*0) + (0/3*0)) = 0,2516

tree-node-1.2.2

Dari hasil perhitungan pada tabel diatas, diketahui bahwa nilai Gain terbesar yaitu sebesar 0,9183, karena ada beberapa atribut yang sama-sama memiliki nilai gain terbesar, maka dipilih salah satu atribut yaitu pada atribut Berkas. Sehingga atribut Berkas menjadi node cabang dari nilai atribut 24-27.

Pada atribut Berkas terdapat 2 nilai atribut, dimana semua nilai atribut sudah mengklasifikasikan kasus menjadi 1 yaitu dengan hasil Lulus dan Tidak Lulus sehingga tidak perlu dilakukan perhitungan lebih lanjut.  Dari proses tersebut maka dapat dihasilkan pohon sementara seperti berikut ini.

decision tree iterasi 4

Kemudian lakukan perhitungan untuk mencari node cabang dari nilai atribut umur 28-30. Perhitungan dilakukan dengan mencari nilai dari atribut selain yang menjadi node akar (IPK) dan node cabang (Umur), yaitu dengan mencari jumlah kasus untuk hasil Lulus dan Tidak Lulus, dan nilai Entropy dari semua kasus saat IPK = 2.5–3 dan Umur = 28-30. Dan kemudian lakukan perhitungan untuk mencari nilai Gain, dan atribut dengan nilai Gain terbesar, maka akan menjadi node cabang dari nilai atribut 28-30.

Node 1.2.3 :

Jumlah kasus dengan IPK = 2,5–3 dan UMUR = 28-30 : 4
Jumlah kasus dg IPK = 3–3,5 dan UMUR = 28-30 yang hasil Lulus : 1
Jumlah kasus dg IPK = 3–3,5 dan UMUR = 24-30 yang hasil Tdk Lulus : 3

Hitung nilai entropy dari total kasus :

Entropi (S) = (-(1/4) x log₂ (1/4) + (-(3/4) x log₂ (3/4)) = 0.8113

Lakukan perhitungan untuk nilai entropy pada setiap atribut, kecuali pada atibut IPK :

Entropy (bagian = teller) = (-(0/2) x log₂ 0/2) + (-(2/2) x log₂ (2/2)) = 
Entropy (bagian = marketing) = (-(0/1) x log₂ (0/1) + (-(1/1) x log₂ (1/1)) = 
Entropy (bagian = IT) = (-(1/1) x log₂ (1/1) + (-(0/0) x log₂ (0/0)) =
Entropy (bagian = call centre) = (-(0/0) x log₂ (0/0) + (-(0/0) x log₂ (0/0)) = 
Entropy (bagian = cust. service) = (-(0/0) x log₂ (0/0) + (-(0/0) x log₂ (0/0)) = 

:
:
:

Entropy (status = menikah) = (-(1/2) x log₂ (1/2) + (-(1/2) x log₂ (1/2)) = 1
Entropy (status = bercerai) = (-(0/0) x log₂ (0/0) + (-(0/0) x log₂ (0/0)) = 

Setelah dicari nilai entropy pada setiap nilai dari atribut yang ada, kemudian lakukan perhitungan untuk mencari nilai gain dari setiap atribut.

Gain(bagian) = 0,8113 – ((2/4*0) + (1/4*0) + (1/4*0) + (0/4*0) + (0/4*0)) = 0,8113
Gain(pendidikan) = 0,8113 – ((0/4*0) + (0/4*0) + (0/4*0) + (2/4*0) + (2/4*1)) = 0,3113
Gain(jurusan) = 0,8113 – ((1/4*0) + (2/4*0) + (1/4*0) + (0/4*0)) = 0,8113
Gain(wawancara) = 0,8113 – ((1/4*0) + (1/4*1) + (2/4*0)) = 0,8113
Gain(berkas) = 0,8113 – ((1/4*0) + (3/4*1)) = 0,1226
Gain(kerapian) = 0,8113 – ((3/4*0) + (0/4*0) + (1/4*0)) = 0,8113
Gain(status) = 0,8113 – ((2/4*1) + (2/4*0) + (0/4*0)) = 0,3113

tree-node-1.2.3

Dari hasil perhitungan pada tabel diatas, diketahui bahwa nilai Gain terbesar yaitu sebesar 0,8113, karena ada beberapa atribut yang sama-sama memiliki nilai gain terbesar, maka dipilih salah satu atribut yaitu pada atribut Wawancara. Sehingga atribut Wawancara menjadi node cabang dari nilai atribut 28-30.

Pada atribut Wawancara terdapat 3 nilai atribut, dimana semua nilai atribut sudah mengklasifikasikan kasus menjadi 1 yaitu dengan hasil Lulus, Tidak Lulus dan Tidak Lulus sehingga tidak perlu dilakukan perhitungan lebih lanjut. Dari proses tersebut maka dapat dihasilkan pohon sementara seperti berikut ini.

decision tree iterasi 5

Pembentukan pohon keputusan dengan menggunakan algoritma ID3 diatas sudah terselesaikan karena tidak ada lagi node cabang yang belum mengklasifikasikan 1 (satu) keputusan.

Semoga artikel berjudul “Algoritma ID3” bisa bermanfaat dan silahkan jika masih ada yang kurang jelas dapat ditanyakan di kolom komentar dibawah ini.

Silahkan Like Fanspage dan Share artikel ini jika menurut kamu bermanfaat untuk kamu dan orang lain.

Artikel Lainnya