Decision Tree – ID3

Kemaren dapet PR buat bikin Decision Tree dari tabel berikut:

Langkah buat bikin decision tree nya:

  1. Hitung entropy sistem
  2. Hitung entropy masing2 atribut
  3. Hitung information gain & Gain masing2 atribut
  4. Pilih atribut tertinggi buat jadi root
  5. Bikin tabel pemilahan data
  6. Mulai lagi dari poin 1 untuk bikin simpul dan cabang

Untuk perhitungan entropi pake rumus:

Entropy sistem:

dihitung dulu Jumlah P ada 3; jumlah N ada 7, p+n=10

Entropy sistem = -(3/10) log2 (3/10) – (7/10) log2 (7/10) = 0,521 + 0,36 = 0,881

Entropy masing2 atribut:

Atribut P:

dari tabel terlihat P memiliki 2 value yaitu F & R

dihitung dulu untuk masing2 value:

F: jumlah P ada 0; jumlah N=5; n+p=5

Entropy F= -(0/5) log2 (0/5) – (5/5) log2 (5/5)= 0

R: jumlah P=3; jumlah N=2; n+p=5

Entropy R= -(3/5) log2 (3/5) – (2/5) log2 (2/5)= 0,442+0,5287=0,971

Atribut Q:

Q memiliki 3 value yaitu S,B dan M:

S: jumlah P=0, jumlah N=3; n+p=3

Entropy S=-(0/3) log2 (0/3) – (3/3) log2 (3/3) = 0

B: jumlah P=2, jumlah N=1; p+n=3

Entropy B=-(2/3) log2(2/3) – (1/3) log 2 (1/3) = 0,389+ 0,528 = 0,918

M: jumlah P=1; jumlah N= 3; p+n=4

Entropy M=-(1/4) log2(1/4) – (3/4) log2 (3/4) = 0,5 + 0,311 = 0,811

Atribut R

R memiliki 2 value: S dan B

value S: jumlah P = 2; jumlah N=3; n+p=5

Entropy S=-(2/5) log2 (2/5) – (3/5) log2 (3/5) = 0,528 + 0,442 = 0,971

value B: jumlah P=1; jumlah N=4; n+p=5

Entropy B=-(1/5) log2 (1/5) -(4/5) log2 (4/5) = 0,464 + 0,2575 = 0,7215

Hitung Gain

Rumus untuk menghitung Gain adalah:

Persamaan tersebut memiliki 2 komponon. Di bagian kiri, Entropy S adalah entropi sistem secara keseluruhan yaitu 0,881. Sementara di bagian kanan adalah average entropy masing2 atribut. Karena ada 3 atribut kita harus hitung dulu nilai masing2 atribut:

Atribut P:

Average Entropy P = (n+p)f/(n+p)total * Entropy (P) + (n+p)R/(n+p)total * Entropy R = (5/10) * 0 + (5/10) * 0,971 = 0,4855

Gain P = 0,881 – 0,4855 = 0,3955

Atribut Q:

Average entropy Q= (3/10)*0+(3/10)*0,918+(4/10)*0,811= 0 + 0,275 + 0,324 = 0,5998

Gain(Q) = 0,881 – 0,5998 = 0,2812

Atribut R:

Average entropy R= (5/10)*0,971 + (5/10)*0,7215=0,4855+0,361=0,846

Gain R = 0,881 – 0,846 = 0,035

Atribut yg dipilih

Gain(P)= 0,3955

Gain(Q)=0,2812

Gain(R)= 0,035

yang dipilih adalah yang memiliki gain tertinggi, yaitu atribut P. Sehingga P jadi Root.

Kemudian dibuat tabel pemilahan Data berdasarkan atribut P:

Dari tabel terlihat semua nilai P menghasilkan kelas N, sementara R memiliki 3 nilai P dan 2 N. Sehingga harus displit lagi.

Untuk nilai R kita mencari atribut yang akan dipilih sebagai cabang yaitu antara Q dan R. Caranya sama seperti perhitungan diatas. Kita fokus hanya pada nilai R berarti data ke 2,3,4,6 dan 10

Hitung entropy sistem:

p=3; N=2; n+p=5

menggunakan rumus entropy didapat Entropy(s)= 0,629

kemudian hitung entropy masing2 atribut

Atribut Q

ada 3 nilai B,M,S

dengan menggunakan rumus entropy diperoleh

Entropy B=0

entropy M= 1

Entropy S = 0

Atribut R

ada 2 value:

entropy S=0,918

entropy B=1

langkah berikutnya menghitung Gain

Gain

Average entropy Q= 0,4

Gain Q=0,229

Average entropy R=0,951

Gain R=-0,32203

Atribut yang dipilih dengan gain terbesar adalah Q

Q memiliki 3 nilai yaitu B,M,S

Dari tabel terlihat semua nilai B menghasilkan kelas P

dan semua nilai S menghasilkan nilai N

sementara nilai M memiliki 1 P dan 1 N sehingga perlu displitting

PIlih atribut

Atribut berikutnya yang bisa dipilih adalah R.

R memiliki 2 nilai yaitu S & B.

Namun dari tabel terlihat semua nilai S menghasilkan nilai P

dan semua nilai N menghasilkan nilai N

sehigga didapat decision tree final adalah sebagai berikut:

Semoga Bermanfaat!

Silahkan tuliskan tanggapan, kritik maupun saran