POHON KEPUTUSAN DENGAN ALGORITMA C4.5

POHON KEPUTUSAN DENGAN ALGORITMA C4.5 1. Pengantar Algoritma C4.5 Klasifikasi merupakan salah satu proses pada data mining yang bertujuan untuk menemukan pola yang berharga dari data yang berukuran relatif besar hingga sangat besar. Data tersebut saat ini kebanyakan dikelola menggunakan Database Management System (DBMS) baik sebagai database maupun data warehouse. Algoritma C4.5 merupakan salah satu algoritma klasifikasi yang populer pada kelompok algoritma pohon keputusan. Pada tahap “belajar” dari data pelatihan, algoritma C4.5 mengkonstruksi pohon keputusan. Pada tahap klasifikasi, pohon keputusan digunakan untuk memprediksi kelas dari sebuah kasus yang kelasnya belum diketahui. Prinsip kerja algoritma ini dalam proses belajar adalah membaca seluruh sampel/kasus dari storage dan memuatnya ke memori, kemudian melakukan komputasi dengan membaca sampel-sampel di memori untuk mengkonstruksi pohon (yang juga disimpan di memori). Dengan pendekatan ini, salah satu kelemahan algoritma C4.5 yang termasuk dalam kategori skalabilitas adalah algoritma tersebut hanya dapat digunakan untuk menangani sampel-sampel yang dapat disimpan secara keseluruhan dan pada waktu yang bersamaan di memori.

2. Pohon Keputusan (Decision Tree) Pohon keputusan yaitu pohon dalam analisis pemecahan masalah pengambilan keputusan mengenai pemetaan mengenai alternatif-alternatif pemecahan masalah yang dapat diambil dari masalah tersebut. Pohon tersebut juga

memperlihatkan

faktor-faktor

kemungkinan/probablitas

yang

akan

mempengaruhi alternatif-alternatf keputusan tersebut, disertai dengan estimasi hasil akhir yang akan didapat bila kita mengambil alternatif keputusan tersebut. 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 pohon keputusan yaitu mengubah bentuk data (tabel) menjadi model pohon (tree) kemudian mengubah model pohon tersebut menjadi aturan

(rule). Metode pohon keputusan digunakan untuk memperkirakan nilai diskret dari fungsi target yang mana fungsi pembelajaran direpresentasikan oleh sebuah pohon keputusan (decision tree). Pohon keputusan terdiri dari himpunan IF…THEN. Setiap path dalam tree dihubungkan dengan sebuah aturan, dimana premis terdiri atas sekumpulan node-node yang ditemui dan kesimpullannya dari aturan atas kelas yang terhubung dengan leaf node dari path. 2.1 Kelebihan Pohon Keputusan 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.

2.2 Kekurangan Pohon Keputusan 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.

2.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 Root node atau node akar merupakan node yang terletak paling atas dari suatu pohon. b. Internal node Internal Node ini merupakan node percabangan, dimana pada node ini hanya terdapat satu input dan mempunyai minimal dua output. c. Leaf node 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. ROOT NODE

A

x1

x4 x2

x3 INTERNAL NODE

a1

B

y1

b1

d1

y2

z1

y3

D

w1

w2

a4

C

b3

c1

z2

z3

c2

LEAF NODE

c3

w3

d2

d3

Gambar 1. Arsitektur Pohon Keputusan

Lambang bulat pada pohon keputusan melambangkan node akar (root node) dan juga node cabang (internal node). Namun node akar selalu terletak paling atas tanpa memiliki input, sedangkan node cabang mempunyai input. Lambang kotak melambangkan node daun (leaf node). Setiap node daun berisi nilai atribut dari node cabang atau node akarnya.

3. Algoritma C4.5 Algoritma C4.5 adalah algoritma klasifikasi data dengan teknik pohon keputusan yang terkenal dan disukai karena memiliki kelebihan-kelebihan. Kelebihan ini misalnya dapat mengolah data numerik (kontinyu) dan diskret, dapat menangani nilai atribut yang hilang, menghasilkan aturan-aturan yang mudah diinterpretasikan dan tercepat di antara algoritma-algoritma yang menggunakan memori utama di komputer. Algoritma C4.5 mengkonstruksi pohon keputusan dari data pelatihan, yang berupa kasus-kasus atau record (tupel) dalam basisdata. Setiap kasus berisikan nilai dari atribut-atribut untuk sebuah kelas. Setiap atribut dapat berisi data diskret atau kontinyu (numerik). C4.5 juga menangani kasus yang tidak memiliki nilai untuk sebuah atau lebih atribut. Akan tetapi, atribut kelas hanya bertipe diskret dan tidak boleh kosong. Ada tiga prinsip kerja algoritma C4.5 pada tahap belajar dari data, yaitu sebgai berikut : 1. Pembuatan Pohon Keputusan Obyektif dari algoritma pohon keputusan adalah mengkonstruksi struktur data pohon (dinamakan pohon keputusan) yang dapat digunakan untuk memprediksi kelas dari sebuah kasus atau record baru yang belum memiliki kelas. Algoritma ini memilih pemecahan kasus-kasus yang terbaik dengan menghitung dan membandingkan gain ratio, kemudian pada node-node yang terbentuk di level berikutnya. Demikian seterusnya sampai terbentuk daundaun.

2. Pemangkasan Pohon Keputusan dan Evaluasi (Opsional) Karena pohon yang dikonstruksi dapat berukuran besar dan tidak mudah dibaca,

C4.5

dapat

menyederhanakan

pohon

dengan

melakukan

pemangkasan berdasarkan nilai tingkat kepercayaan (confidence level). Selain untuk pengurangan ukuran pohon, pemangkasan juga bertujuan untuk mengurangi tingkat kesalahan prediksi pada kasus (rekord) baru.

3. Pembuatan Aturan-Aturan dari Pohon Keputusan (Opsional) Aturan-aturan dalam bentuk if-then diturunkan dari pohon keputusan dengan melakukan penelusuran dari akar sampai ke daun. Setiap node dan syarat pencabangannya akan diberikan di if, sedangkan nilai pada daun akan menjadi ditulis di then. Setelah semua aturan dibuat, maka aturan akan disederhanakan (digabung atau diperumum). 3.1 Langkah-Langkah Konstruksi Pohon Keputusan dengan Algoritma C4.5 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, gain ratio akan digunakan untuk memilih atribut split, yaitu atribut yang 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.

3.2 Entropy Dalam teori informasi, entropi mengukur ketidakpastian antar variabel acak dalam file data. Claude E. Shannon telah mengembangkan gagasan tentang entropi dari variabel acak. Entropi dan informasi terkait menyediakan perilaku jangka panjang dari proses acak yang sangat berguna untuk menganalisis data. Perilaku dalam proses acak juga merupakan faktor kunci untuk mengembangkan pengkodean untuk teori informasi. Entropi merupakan pengukuran ketidakpastian rata-rata kumpulan data ketika kita tidak tahu hasil dari sumber informasi. Itu berarti bahwa seberapa banyak pengukuran informasi yang kita tidak punya. Ini juga menunjukkan jumlah rata-rata informasi yang kami akan menerima dari hasil sumber informasi. Untuk mendapatkan nilai gain ratio dalam pembentukan pohon keputusan, perlu menghitung dulu nilai informasi dalam satuan bits dari suatu kumpulan objek Bentuk perhitungan untuk entropi adalah sebagai berikut : ( )

∑

∑

2

2

dimana, X : Himpunan Kasus k : jumlah partisi X pj : Proporsi Xj terhadap X

Entropi split yang membagi X dengan n record menjadi himpunan-himpunan X1 dengan n1 baris dan X2 dengan n2 baris adalah : (

)

(

)

(

)

Besar nilai Entropy(X) menunjukkan bahwa X adalah atribut yang lebih acak. Di sisi lain, atribut yang lebih kecil dari nilai Entropy(X) menyiratkan atribut ini sedikit lebih acak yang signifikan untuk data mining. Nilai entropi mencapai nilai minimum 0, ketika semua pj lain = 0 atau berada pada kelas yang sama. Nilainya mencapai maksimum log2 k, ketika semua nilai pj adalah sama dengan 1/k.

3.3 Gain Ratio Pada kontruksi pohon C4.5, di setiap simpul pohon, atribut dengan nilai gain ratio tertinggi dipilih sebagai atribut split untuk simpul. Rumus dari gain ratio adalah sebagai berikut : ( ) ( )

( )

Dimana gain(a) adalah information gain dari atribut a untuk himpunan sampel X dan split info(a) menyatakan entropi atau informasi potensial yang didapat pada pembagian X menjadi n sub himpunan berdasarkan telaahan pada atribut a. Sedangkan gain(a) didefinisikan sebagai berikut : ( )

( )

( )

Untuk rumus split info(a) adalah sebagai berikut : ( )

∑

| | | |

| | ( ) | |

dimana Xi menyatakan sub himpunan ke-I pada sampel X. Dengan kata lain rumus untuk menghitung nilai gain ratio untuk dipilih sebagai atribut dari simpul yang ada sebagai berikut ini : ( )

( )

∑

| | | |

( )

Alasan penggunaan gain ratio(a) pada C4.5 (bukan gain(a)) sebagai kriteria pada pemilihan atribut adalah gain ternyata bias terhadap atribut yagn memiliki banyak nilai unik.

CONTOH Soal : 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 C4.5 ! PELAMAR

BAGIAN

PENDIDIKAN

JURUSAN

IPK

WAWANCARA

KELENGKAPAN BERKAS

KERAPIAN

UMUR

STATUS

HASIL

1

TELLER

S1

AKUNTANSI

3,8

BAIK

LENGKAP

BAIK

27

MENIKAH

LULUS

2

TELLER

S1

AKUNTANSI

2,8

CUKUP

TDK LENGKAP

BAIK

28

LAJANG

3

TELLER

S1

AKUNTANSI

2,7

CUKUP

LENGKAP

BAIK

32

BERCERAI

4

IT

S2

INFORMATIKA

3,6

BAIK

LENGKAP

CUKUP

29

LAJANG

LULUS

5

IT

S1

INFORMATIKA

3,6

BAIK

LENGKAP

CUKUP

26

LAJANG

LULUS

6

IT

S2

INFORMATIKA

2,6

BAIK

TDK LENGKAP

BURUK

28

MENIKAH

LULUS

7

IT

D3

INFORMATIKA

2,5

CUKUP

TDK LENGKAP

BURUK

27

LAJANG

TIDAK LULUS

8

TELLER

D3

AKUNTANSI

3,4

CUKUP

TDK LENGKAP

BAIK

22

LAJANG

LULUS

9

MARKETING

S2

MANAJEMEN

3,5

CUKUP

LENGKAP

BAIK

29

LAJANG

LULUS

10

MARKETING

S2

MANAJEMEN

2,8

BURUK

LENGKAP

BAIK

29

MENIKAH

TIDAK LULUS

11

TELLER

S1

AKUNTANSI

3,2

BAIK

LENGKAP

CUKUP

27

MENIKAH

LULUS

12

TELLER

D2

MANAJEMEN

3,3

BAIK

LENGKAP

CUKUP

33

MENIKAH

TIDAK LULUS

TIDAK LULUS TIDAK LULUS

13

TELLER

D2

MANAJEMEN

2,8

BURUK

TDK LENGKAP

CUKUP

22

BERCERAI

14

TELLER

S1

AKUNTANSI

2,8

BAIK

TDK LENGKAP

CUKUP

31

BERCERAI

15

TELLER

S1

AKUNTANSI

2,4

BURUK

TDK LENGKAP

CUKUP

21

MENIKAH

16

TELLER

S1

AKUNTANSI

2,5

BAIK

LENGKAP

CUKUP

25

MENIKAH

LULUS

17

MARKETING

S2

MATEMATIKA

3,2

CUKUP

LENGKAP

BAIK

25

LAJANG

LULUS

S1

MATEMATIKA

3,4

BAIK

LENGKAP

BAIK

26

LAJANG

LULUS

S1

MATEMATIKA

2,7

CUKUP

LENGKAP

BAIK

26

LAJANG

LULUS

18 19

CUST. SERVICE CUST. SERVICE

LULUS TIDAK LULUS TIDAK LULUS

20

MARKETING

S2

MANAJEMEN

3,3

BAIK

LENGKAP

BURUK

29

LAJANG

LULUS

21

MARKETING

S2

MANAJEMEN

3,4

BAIK

LENGKAP

BAIK

33

MENIKAH

LULUS

22

TELLER

D3

MANAJEMEN

2,3

BURUK

LENGKAP

BAIK

23

MENIKAH

TIDAK LULUS

D1

INFORMATIKA

3,2

BAIK

TDK LENGKAP

BAIK

23

MENIKAH

LULUS

D1

INFORMATIKA

2,4

BURUK

LENGKAP

BURUK

29

LAJANG

TIDAK LULUS

S1

AKUNTANSI

3,3

BAIK

LENGKAP

BURUK

26

LAJANG

LULUS

S1

AKUNTANSI

2,4

CUKUP

TDK LENGKAP

BAIK

26

LAJANG

TIDAK LULUS

S1

AKUNTANSI

3,3

CUKUP

LENGKAP

BURUK

27

MENIKAH

LULUS

23 24 25 26 27

CALL CENTRE CALL CENTRE CUST. SERVICE CUST. SERVICE CUST. SERVICE

28

TELLER

S1

MANAJEMEN

3,2

CUKUP

TDK LENGKAP

CUKUP

24

LAJANG

LULUS

29

TELLER

S1

MANAJEMEN

3,4

BAIK

LENGKAP

BAIK

24

LAJANG

LULUS

30

TELLER

S1

MANAJEMEN

2,9

BURUK

TDK LENGKAP

BAIK

29

LAJANG

TIDAK LULUS

PENYELESAIAN

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 : ( ( )

((

( )



)

)

((

(

(

)

))

(

)

(

)

((

))

((

)

)

(

(

))

))

Lakukan juga perhitungan untuk nilai entropy pada setiap atribut : (

(

)

((

)

((

)

)

(

( ))

))

((

((

)

)

(

( ))

))

(

)

(

)

(

)

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

)

(

(

)

((

(

)

((

)

( ))

))

((

((

)

)

(

( ))

))

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

Nilai gain dari masing-masing atribut : ( ) (

)

(

)

(

(

)

)

)

(

(

)

(

((

)

(

((

(

(

((

)

)

)

)

)

(

((

)

(

((

((

)

)

(

)

)

)

(

(

)

)

(

(

)

(

))

)

(

))

(

))

))

))

))

)

)

)

(

(

(

)

(

(

( ) )

)

(

| | | |

(

(

((

((

∑ )

)

((

)

(

( )

(

(

))

)

)

(

(

))

))

Hasil perhitungan untuk nilai entropy dan gain ditunjukkan dalam tabel berikut. ATRIBUT

BANYAK KASUS

LULUS (L)

TDK LULUS (TL)

TOTAL KASUS BAGIAN

30

19

11

ENTROPY 0,9481

0,0659 TELLER

14

MARKETING

5

IT CALL CENTRE CUST. SERVICE

4

7

1

4

1

0,7219

3

1

0,8113

1

1

4

1

D1

2

1

1

1

D2

2

1

1

1

D3

3

1

2

0,9183

S1

16

10

6

0,9544

S2

7

6

1

0,5917

AKUNTANSI

11

6

5

0,9940

MANAJEMEN

10

6

4

0,9710

INFORMATIKA

6

4

2

0,9183

MATEMATIKA

3

3

0

0

2 5

7

1 0,7219

PENDIDIKAN

0,0758

JURUSAN

0,0763

IPK

0,4589 <2,5

4

2.5 - 3

10

3 - 3.5

12

>3,5

4

4

0

4

6

0,9710

11

1

0,4138

4

0

0

0

WAWANCARA

0,2183 BAIK

14

12

2

0,5917

CUKUP

10

6

4

0,9710

BURUK

6

1

5

0,6500

BERKAS

0,0570 LENGKAP TDK LENGKAP

19 11

14

5

5

6

0,8315 1

KERAPIAN

UMUR

GAIN

0,0035 BAIK

15

9

6

0,9710

CUKUP

9

6

3

0,9183

BURUK

6

4

2

0,9183 0,1430

<=23

5

3

2

1

24 - 27

13

11

2

0,6194

28 - 30

8

4

4

1,0000

>30

4

1

3

0,8113

STATUS

0,0316 LAJANG

16

11

5

0,8960

MENIKAH

11

7

4

0,9457

BERCERAI

3

1

2

0,9183 MAX =

Langkah 2 : Menentukan node akar 

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.



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.



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



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.

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

0,4589

IPK

<2,5

>3,5 3 – 3,5

2,5 - 3

TIDAK LULUS

1.2 ?

LULUS

1.3 ?

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




((

( )

)

)

((

(

(

)

))

(

))

)

(

((

((

) )

)

(

(

))

))



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

)

(

(

)

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

)

(

)

(

)

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))



)

)

)

)

)

(

(

(

)

)

)

((

)

(

)

(

( ) (

)

)

(

)

(

)

(

))

)

(

))

(

))

))

))

)

)

(

)

(

(

| | | |

(

(

)

)

∑ )

)

((

((

(

(

((

((

)

)

((

((

(

(

)

((

(

(

( )

(

(

)

)

(

(

))

)

)

(

(

))

))

Hasil perhitungan yang dilakukan ditunjukkan dalam tabel berikut. Node 1.2 : BANYAK KASUS

LULUS (L)

10

4

TDK LULUS (TL) 6

TELLER MARKETING IT CALL CENTRE CUST. SERVICE

6 1 2 0

2 0 1 0

4 1 1 0

0,9183 0 1 0

1

1

0

0

D1 D2 D3 S1 S2

0 1 1 6 2

0 1 0 2 1

0 0 1 4 1

0 0 0 0,9183 1

AKUNTANSI MANAJEMEN INFORMATIKA MATEMATIKA

4 3 2 1

1 1 1 1

3 2 1 0

0,8113 0,9183 1 0

BAIK CUKUP BURUK

3 4 3

2 1 1

1 3 2

0,9183 0,8113 0,9183

LENGKAP TDK LENGKAP

4 6

2 2

2 4

1 0,9183

BAIK CUKUP BURUK

5 3 2

1 2 1

4 1 1

0,7219 0,9183 1

<=23 24 - 27 28 - 30 >30

1 3 4 2

1 2 1 0

0 1 3 2

0 0,9183 0,8113 0

LAJANG MENIKAH BERCERAI

4 3 3

1 2 1

3 1 2

0,0955 0,8113 0,9183 0,9183 MAX = 0,3710

ATRIBUT IPK 2,5 - 3 BAGIAN

ENTROPY

GAIN

0,9710 0,2200

PENDIDIKAN

0,2200

JURUSAN

0,1710

WAWANCARA

0,0955

BERKAS

0,0200

KERAPIAN

0,1345

UMUR

0,3710

STATUS



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.

IPK

<2,5

>3,5 2,5 - 3

1.2 UMUR

TIDAK LULUS

<=23

LULUS

24 - 27

1.2.2 ?

28 - 30

1.2.3 ?

3 – 3,5

1.3 ?

>30

TIDAK LULUS

LULUS

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 = 33.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




((

( )



)

)

((

(

(

)

))

(

)

(

((

))

((

) )

)

(

(

))

))

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

)

(

(

(

)

)

)

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))



)

)

((

(

(

( )

)

)

((

)

(

((

)

(

(

∑ )

)

(

(

)

)

)

| | | |

(

( ) (

(

)

)

)

(

(

(

))

))

))

(

)

(

)

(

(

)

)

(

)

((

)

(

)

((

)

(

))

((

)

(

((

)

(

((

)

(

)

)

(

))

(

))

(

)

)

(

(

))

))

Hasil perhitungan yang dilakukan ditunjukkan dalam tabel berikut. Node 1.3 : TDK BANYAK LULUS LULUS ENTROPY KASUS (L) (TL)

ATRIBUT IPK 3 - 3,5 BAGIAN

12

11

1

0,4138 0,1130

TELLER MARKETING IT CALL CENTRE CUST. SERVICE

5 3 0

4 3 0

1 0 0

0,7219 0 0

1

1

0

0

3

3

0

0

PENDIDIKAN

0,4138 D1 D2 D3 S1 S2

1 1 1 6 3

1 0 1 6 3

0 1 0 0 0

0 0 0 0 0

JURUSAN

0,1130 AKUNTANSI MANAJEMEN INFORMATIKA MATEMATIKA

WAWANCARA

GAIN

4 5 1 2

4 4 1 2

0 1 0 0

0 0,7219 0 0 0,0514

BAIK CUKUP BURUK

8 4 0

7 4 0

1 0 0

0,5436 0 0

BERKAS


9 3

8

1

3

0

0,5033 0

KERAPIAN

0,1842 BAIK CUKUP BURUK

6 3 3

6 2 3

0 1 0

0 0,9183 0

UMUR

0,2472 <=23 24 - 27 28 - 30 >30

2 7 1 2

2 7 1 1

0 0 0 1

0 0 0 1

STATUS

0,1130 LAJANG MENIKAH BERCERAI

7 5 0

7 4

0 1

0

0

0 0,7219 0 MAX = 0,4138



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 anilai 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.

IPK

<2,5

>3,5 3 – 3,5

2,5 - 3

TIDAK LULUS

<=23

LULUS

1.3 ? PENDIDIK AN

1.2 UMUR

24 - 27

1.2.2 ?

28 - 30

D1

>30

TIDAK LULUS

1.2.3 ?

D2

LULUS

D3

S1

TIDAK LULUS

LULUS

S2

LULUS

LULUS

LULUS

 Lakukan perhitungan untuk mencari node cabang dari nilai atribut umur 2427. 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 Tdk Lulus : 1 


((

( )

)

((

)

)

(

(

))

( ))

)

(

((

((

) )

)

( ))

(

))



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

)

(

(

)

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

)

(

)

(

)

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))



)

(

)

(

)

(

)

(

)

(

(

)

)

( )

∑

| | | |

( )

((

)

(

)

(

)

(

)

(

))

((

)

(

)

(

)

(

)

(

))

((

)

(

)

(

)

(

))

((

)

(

)

(

))

((

)

(

))

((

)

(

)

(

))

((

)

(

)

(

))

Hasil perhitungan yang dilakukan ditunjukkan dalam tabel berikut. Node 1.2.2 : TDK BANYAK LULUS LULUS ENTROPY KASUS (L) (TL)

ATRIBUT

3

IPK 2,5 - 3 | UMUR 24-27

2

1

GAIN

0,9183

BAGIAN

0,9183 TELLER MARKETING IT CALL CENTRE CUST.

1 0 1

1 0 0

0 0 1

0 0 0

0

0

0

0

1

1

0

0

SERVICE PENDIDIKAN

0,9183 D1 D2 D3 S1 S2

0 0 1 2 0

0 0 0 2 0

0 0 1 0 0

0 0 0 0 0

JURUSAN


1 0 1 1

1 0 0 1

0 0 1 0

0 0 0 0

WAWANCARA


1 2 0

1 1 0

0 1 0

0 1 0

BERKAS


2 1

2

0

0

1

0 0

KERAPIAN


1 1 1

1 1 0

0 0 1

0 0 0

STATUS


2 1 0

1 1

1 0

0

0

1 0 0 MAX = 0,9183



Dari hasil perhitungan pada tabel diatas, diketahui bahwa nilai Gain terbesar yaitu sebesar 0,9183, karena ada beberapa atribut yang samasama 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. IPK

<2,5

>3,5 2,5 - 3

1.2 UMUR

TIDAK LULUS

<=23

24 - 27

1.2.2 BERKAS

LULUS

LULUS

3 – 3,5

28 - 30

1.2.3 WAWANCARA

1.3 ? PENDIDIKAN

>30

TIDAK LULUS

D1

LULUS

D2

LULUS

D3

TIDAK LULUS

S1

LULUS

S2

LULUS

LULUS

TIDAK LULUS

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 


((

( )



)

)

((

(

(

))

)

( ))

)

(

((

((

) )

)

(

))

( ))

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

)

(

(

)

)

(

)

(

(

)

)

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))

(

)

((

)

( ))

((

)

( ))



)

(

)

(

)

(

(

)

)

( )

∑

| | | |

( )

((

)

(

)

(

)

(

)

(

))

((

)

(

)

(

)

(

)

(

))

((

)

(

)

(

)

(

))

((

)

(

)

((

)

(

))

(

))

(

(

)

)

((

)

(

)

(

))

((

)

(

)

(

))

Hasil perhitungan yang dilakukan ditunjukkan dalam tabel berikut. Node 1.2.3 : ATRIBUT IPK 2,5 - 3 | UMUR 28-30

BANYAK KASUS

LULUS (L)

4

1

TDK LULUS (TL) 3

ENTROPY

GAIN

0,8113

BAGIAN

0,8113 TELLER MARKETING IT CALL CENTRE CUST. SERVICE

2 1 1

0 0 1

2 1 0

0 0 0

0

0

0

0

0

0

0

0

PENDIDIKAN

0,3113 D1 D2 D3 S1 S2

0 0 0 2 2

0 0 0 0 1

0 0 0 2 1

0 0 0 0 1

JURUSAN


1 2 1 0

0 0 1 0

1 2 0 0

0 0 0 0

WAWANCARA


1 1 2

1 0 0

0 1 2

0 0 0

BERKAS

0 LENGKAP TDK LENGKAP

1

0

1

0

3

1

2

0,9183

KERAPIAN


3 0 1

0 0 1

3 0 0

0 0 0

STATUS


2 2 0

0 1 0

2 1 0

0 1 0 MAX =



Dari hasil perhitungan pada tabel diatas, diketahui bahwa nilai Gain terbesar yaitu sebesar 0,8113, karena ada beberapa atribut yang samasama 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.

0,8113

IPK

<2,5

>3,5 3 – 3,5

2,5 - 3

TIDAK LULUS

<=23

LULUS

LULUS

24 - 27

1.2.2 BERKAS

TIDAK LULUS

1.3 ? PENDIDIK AN

1.2 UMUR

28 - 30

1.2.3 WAWANCA RA

LULUS

D1

>30

TIDAK LULUS

TIDAK LULUS

LULUS

D2

TIDAK LULUS

LULUS

D3

S1

LULUS

S2

LULUS

LULUS

TIDAK LULUS

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

DAFTAR PUSTAKA

1. Moertini, Veronica S.”Towards The Use of C4.5 Algorithm for Classifying Banking Dataset”.2003. Sumber : http://home.unpar.ac.id/~integral/Volume%208/Integral%208%20No.%20 2/C45%20Algorithm.PDF 2. Tickle, Kevin S, dkk.”Improved C4.5 Algorithm for Rule Based Classification”. Sumber : http://www.wseas.us/elibrary/conferences/2010/Cambridge/AIKED/AIKED-47.pdf 3. Korting, Thales Sehn.”C4.5 Algorithm and Multivariate Decision Trees”. Sumber : http://www.dpi.inpe.br/~tkorting/projects/c45/material.pdf 4. Hanik, Umi.”Fuzzy Decision Tree dengan Algoritma C4.5”2011. Sumber : http://digilib.its.ac.id/public/ITS-Undergraduate-17454-5107100002Paper.pdf

5. Decision Tree (Pohon Keputusan). Sumber : http://novrina.staff.gunadarma.ac.id/Downloads/files/21783/Algoritma+C4. pdf 6. Moertini, Veronica S.”Pengembangan Skalabilitas Algoritma Klasifikasi C4.5 dengan Pendekatan Konsep Operator Relasi”.2007. Sumber : http://home.unpar.ac.id/~moertini/Disertasi_VeronicaSM.pdf

POHON KEPUTUSAN DENGAN ALGORITMA C4.5

Recommend Documents