pembentukan pohon keputusan dengan id3 dan c4.5

BAB IV

METODE KLASIFIKASI

4.1 Metode Pohon Keputusan (Decision tree method)

Pada bab ini akan dibahas salah satu metode klasifikasi dalam data

mining. Salah satu metode klasifikasi yang menarik melibatkan

pembangunan pohon keputusan, koleksi node keputusan, terhubung oleh

cabang-cabang, memperluas ke bawah dari simpul akar sampai berakhir di

node daun. Pohon Keputusan adalah flowchart yang berbentuk seperti

struktur pohon, dimana setiap simpul internal (node keputusan) menunjukkan

test pada atribut, setiap cabang merupakan keluaran dari test dan setiap simpul

daun (simpul terminal) adalah merupakan sebuah class. Metode pohon

keputusan mengubah fakta yang sangat besar menjadi pohon keputusan yang

merepresentasikan rule. Secara umum metode membangun pohon keputusan

antara lain menentukan atribut sebagai akar, membuat cabang untuk masing-

masing nilai, membagi data dalam cabang dan mengulangi proses untuk

masing-masing cabang sampai semua data pada cabang memiliki kelas yang

sama.

Bagian awal dari pohon keputusan ini adalah akar (root) dan setiap cabang

dari pohon keputusan merupakan pembagian berdasarkan hasil perhitungan,

dan titik akhir (leaf) merupakan pembagian kelas yang dihasilkan.

Pohon keputusan mempunyai 3 tipe simpul yaitu:

1. Simpul akar, dimana tidak memiliki cabang yang masuk dan memiliki

cabang keluar lebih dari satu, terkadang tidak memiliki cabang sama sekali.

Simpul ini biasanya berupa atribut yang paling memiliki pengaruh terbesar

pada suatu kelas tertentu.

2. Simpul keputusan, dimana hanya memiliki 1 cabang yang masuk, dan

memiliki lebih dari 1 cabang yang keluar.

3. Simpul daun, atau simpul akhir dimana hanya memiliki 1 cabang yang

masuk, dan tidak memiliki cabang sama sekali dan menandai bahwa simpul

tersebut merupakan label kelas.

Gambar 4.1 Pohon Keputusan untuk konsep pembelian komputer.

(Jiawei Han, 2006)

Pada gambar 4.1 menunjukkan sebuah pohon keputusan dalam membeli

komputer, yaitu memprediksi apakah pelanggan kemungkinan akan membeli

komputer. Node keputusan ditandai dengan persegi panjang, dan node daun

ditandai dengan oval. Simpul akar pada tersebut adalah umur yang memiliki

tepat dua simpul keputusan dibawah nya. Beberapa algoritma pohon

keputusan hanya menghasilkan pohon biner (di mana setiap cabang simpul

keputusan memilik tepat dua simpul daun atau simpul keputusan dibawah

nya), sedangkan yang lain dapat menghasilkan pohon non biner.

Pohon keputusan dengan mudah dapat dikonversi ke aturan

klasifikasi. Pembangunan pengklasifikasi pohon keputusan tidak

memerlukan pengetahuan domain atau pengaturan parameter, dan karena itu

cocok untuk eksplorasi penemuan pengetahuan. Pohon keputusan dapat

menangani data dimensi tinggi. Ketika pohon keputusan dibangun,

banyaknya jumlah cabang dapat mencerminkan noise atau outlier dalam data

pelatihan. Upaya pemangkasan pohon dilakukan untuk mengidentifikasi dan

menghapus cabang dengan tujuan meningkatkan akurasi klasifikasi pada

data. Secara umum, pengklasifikasi pohon keputusan memiliki akurasi yang

baik. Namun, keberhasilan tergantung pada data yang ada. Algoritma induksi

pohon keputusan telah digunakan untuk klasifikasi dalam banyak area

aplikasi, seperti kedokteran, manufaktur dan produksi, analisis keuangan,

astronomi, dan biologi molekuler. Pohon keputusan merupakan dasar dari

beberapa sistem induksi aturan komersial.

4.1.1 ID3

Pada tahun 1970 dan awal 1980, J. Ross Quinlan, seorang peneliti

dalam machine learning mengembangkan algoritma decision tree yang

dikenal sebagai ID3 (Iterative Dichotomiser). Algortima ID3 merupakan

algortima yang sering digunakan karena kemudahan dan kefektifannya.

Algoritma ID3 membentuk decision tree dari beberapa data simbolik yang

bersifat tetap ataupun historikal untuk melakukan pembelajaran

mengklasifikasikan data tersebut dan memprediksi klasifikasi data yang baru.

Data harus memiliki beberapa atribut dengan nilai yang berbeda. Selain itu

data ini juga harus memiliki beragam standar, class yang diskrit (misal:

Yes/No). Decision tree memilih atribut untuk pengambilan keputusan dengan

menggunakan Information Gain. Algoritma ID3 adalah algoritma decision

tree learning (algoritma pembelajaran pohon keputusan) yang paling dasar.

Algoritma ini melakukan pencarian secara rakus/menyeluruh (greedy) pada

semua kemungkinan pohon keputusan.

Struktur dasar dari ID3 adalah iteratif. Sebuah subset dari training set

disebut window, dipilih secara acak dan dibentuk pohon keputusan. Pohon

ini mengklasifikasikan semua objek pada window, kemudian objek-objek lain

pada training set ini kemudian diklasifikasikan menggunakan pohon tersebut.

Jika pohon tersebut memberikan jawaban yang benar untuk semua objek,

maka dinyatakan benar juga untuk seluruh training set dan selanjutnya

seluruh proses dihentikan. Jika tidak, objek terpilih yang belum

terklasifikasikan akan ditambahkan ke window dan proses berlanjut.

Algoritma ini membentuk pohon keputusan dengan cara pembagian

dan menguasai sampel secara rekursif dari atas ke bawah. Algoritma ID3

dimulai dengan semua data yang ada sebagai akar dari pohon keputusan.

Sebuah atribut yang dipilih akan menjadi pembagi dari sampel tersebut.

Untuk setiap atribut dari cabang yang telah dibentuk, semua sampel yang

memiliki nilai yang sama dengan atribut cabang akan masuk dalam

anggotanya dan dinamakan anak cabang.

Tujuan dari pengukuran nilai Information Gain adalah untuk memilih atribut

yang akan dijadikan cabang pada pembentukan pohon keputusan. Atribut

yang memiliki nilai Information Gain yang tertinggi akan dipilih menjadi

atribut uji untuk dijadikan cabang pohon.

ENTROPY & INFORMATION GAIN

Metode dasar ID3 adalah memilih atribut-atribut untuk klasifikasi

dengan menggunakan metode statistik dimulai dari tree bagian atas. Cara

memilih atribut adalah dengan menggunakan properti statistikal yang disebut

dengan Information Gain, yang didefinisikan untuk menentukan ukuran nilai

dari suatu atribut. Sebelumnya sebuah objek yang diklasifikasikan dalam

pohon harus dites nilai entropinya. Entropy adalah ukuran dari teori informasi

yang dapat mengetahui karakteristik dari impurity dan homogenity dari

kumpulan data. Dari nilai entropy tersebut kemudian dihitung nilai

Information Gain (IG) masing-masing atribut. Nilai entropy didefinisikan

sebagai berikut:

() = log2()

Dimana Pi adalah rasio dari class Ci didalam set data sampel

S = {x1,x2,... xk}

=

Sebagai contoh, set sampel S mempunyai 14 members, dimana didalamnya

ada 9 sampel positif dan 5 sampel negatif. Entropy dari S adalah :

(9 + ,5 ) = (9

14) log2 (

9

14) (

5

14) log2 (

5

14) = 0.940

Pada beberapa kasus, jika semua member dari set sampel S memiliki

nilai yang sama, maka nilai entropy adalah nol. Hal itu berarti tidak ada

klasifikasi yang mempunyai ketidakpastian (uncertainty). Namun jika jumlah

sampel positif sama dengan jumlah sampel negatif, maka entropy bernilai 1,

berarti ketidakpastian bernilai maksimum. Ini berarti set sampel tidak

mempunyai ketidakpastian (keputusan dari decision tree sudah jelas). Jika

jumlah sampel positif tidak sama dengan jumlah sampel negatif, maka nilai

entropy akan berada diantara 0 dan 1.

Dari rumus entropy diatas dapat disimpulkan bahwa definisi entropy

(S) adalah jumlah bit yang diperkirakan dibutuhkan untuk dapat mengekstrak

suatu kelas (+ atau -) dari sejumlah data acak pada suatu ruang sampel S.

Entropy bisa dikatakan sebagai kebutuhan bit untuk menyatakan suatu kelas.

Semakin kecil nilai entropy maka semakin baik digunakan dalam

mengekstraksi suatu kelas. Setelah mendapat nilai entropy untuk suatu

kumpulan data, maka kita dapat mengukur efektivitas suatu atribut dalam

mengklasifikasikan data. Ukuran efektifitas ini disebut Information Gain.

Secara matematis, infomation gain dari suatu atribut A,dituliskan sebagai

berikut :

(, ) = () ||

||()

()

Dimana :

bobot W_i=|S_v |/|S| merupakan rasio dari data dengan atribut v didalam

set sampel

A : atribut

V : suatu nilai yang mungkin untuk atribut A

Values (A) : himpunan yang mungkin untuk atribut A

|Sv| : jumlah sampel untuk nilai v

|S| : jumlah seluruh sampel data

E(Sv) : entropy untuk sampel-sampel yang memilki nilai v

Contoh Penerapan Algoritma ID3

Sebagai contoh penerapan algortima ID3 akan digunakan contoh data sebagai

berikut. Sebuah perusahaan akan memberikan bonus tahunan kepada seluruh

karyawannya. Untuk memberikan bonus ini, departemen kepegawaian

perusahaan ini melakukan pembagian karyawan ke dalam tiga buah golongan

yaitu, Golongan A, Golongan B, dan Golongan C. Berikut adalah bonus yang

diperoleh oleh masing-masing golongan karyawan.

Golongan Bonus Tahunan

A Rp 10.000.000,00

B Rp 5.000.000,00

C Rp 2.500.000,00

Dalam melakukan klasifikasi karyawan ke dalam tiga golongan ini,

departemen kepegawaian menggunakan lima buah parameter, yaitu:

1. Tingkat kehadiran karyawan (Tinggi, Sedang, Rendah) 2. Prestasi karyawan (Tinggi, Rendah) 3. Lama karyawan bekerja di perusahaan ini (Lama, Baru)

4. Jumlah tanggungan karyawan (Banyak, Menengah, Sedikit, Tidak Ada)

5. Pendidikan karyawan (Tinggi, Sedang, Rendah).

Berikut ini adalah data arsip karyawan yang sudah terklasifikasi secara valid.

Kehadiran Prestasi Lama

Bekerja Tanggungan Pendidikan Gol

Tinggi Tinggi Lama Tidak Ada Tinggi A

Sedang Rendah Baru Sedikit Sedang C

Rendah TInggi Lama Menengah Rendah B

Tinggi Rendah Baru Banyak Tinggi C

Sedang Tinggi Baru Menengah Rendah B

Tinggi Tinggi Baru Menengah Rendah B

Tinggi Rendah Lama Menengah Rendah C

Rendah Tinggi Lama Tidak Ada Tinggi A

Sedang Tinggi Baru Tidak Ada Tinggi B

Sedang Rendah Lama Tidak Ada Sedang C

Rendah Tinggi Lama Banyak Sedang A

Tinggi Tinggi Lama Banyak Tinggi A

Tinggi Tinggi Lama Banyak Rendah B

Tinggi Rendah Baru Tidak Ada Tinggi C

Tinggi Tinggi Baru Tidak Ada Sedang B

Rendah Rendah Lama Menengah Tinggi C

Sedang Rendah Baru Menengah Rendah C


Rendah Tinggi Lama Menengah Tinggi A

Tinggi Tinggi Lama Menengah Sedang A

Pembentukan Akar

Langkah pertama dalam algortima ini adalah pembentukan akar dengan

memilih atribut dengan nilai gain tertinggi. Sebelum melakukan hal tersebut,

harus dilakukan perhitungan jumlah objek data sampel dengan golongan

(kelas data) A, B, dan C serta dibagi berdasarkan atribut kehadiran, prestasi,

lama bekerja, tanggungan, dan pendidikan. Tabel berikut menggambarkan

hasil penghitungan jumlah objek data sampel tersebut.

Atribut Jumlah Kasus Golongan

A B C

Total 20 6 7 7

Kehadiran

Tinggi 9 3 3 3

Sedang 6 0 3 3

Rendah 5 3 1 1

Prestasi Tinggi 13 6 7 0

Rendah 7 0 0 7

Lama Bekerja Lama 11 6 2 3

Baru 9 0 5 4

Tanggungan

Banyak 4 2 1 1

Sedikit 1 0 0 1

Menengah 9 2 4 3

Tidak Ada 6 2 2 2

Pendidikan

Tinggi 8 4 1 3

Sedang 5 2 1 2

Rendah 7 0 5 2

Selanjutnya adalah melakukan perhitungan entropi dari seluruh partisi atribut

data. Berikut perhitungannya:

Entropi Total :

() = ((6

20) log2

6

20) + ((

7

20) log2

7

20) + ((

7

20) log2

7

20)

= 1,581

Entropi Kehadiran :

() = ((3

9) log2

3

9) + ((

3

9) log2

3

9) + ((

3

9) log2

3

9)

= 1,585

() = ((0

6) log2

0

6) + ((

3

6) log2

3

6) + ((

3

6) log2

3

6)

= 1,000

() = ((3

5) log2

3

5) + ((

1

5) log2

1

5) + ((

1

5) log2

1

5)

= 1,371

Entropi Prestasi :

() = ((6

13) log2

6

13) + ((

7

13) log2

7

13) + ((

0

13) log2

0

13)

= 0,996

() = ((0

7) log2

0

7) + ((

0

7) log2

0

7) + ((

7

7) log2

7

7)

= 0,000

Entropi Lama Bekerja :

() = ((6

11) log2

6

11) + ((

2

11) log2

2

11) + ((

3

11) log2

3

11)

= 1,435

() = ((0

9) log2

0

9) + ((

5

9) log2

5

9) + ((

4

9) log2

4

9)

= 0,991

Entropi Tanggungan :

() = ((2

4) log2

2

4) + ((

1

4) log2

1

4) + ((

1

4) log2

1

4)

= 1,500

() = ((0

1) log2

0

1) + ((

0

1) log2

0

1) + ((

1

1) log2

1

1)

= 0,000

() = ((2

9) log2

2

9) + ((

4

9) log2

4

9) + ((

3

9) log2

3

9)

= 1,530

( ) = ((2

6) log2

2

6) + ((

2

6) log2

2

6) + ((

2

6) log2

2

6)

= 1,585

Entropi Pendidikan :

() = ((4

8) log2

4

8) + ((

1

8) log2

1

8) + ((

3

8) log2

3

8)

= 1,406

() = ((2

5) log2

2

5) + ((

1

5) log2

1

5) + ((

2

5) log2

2

5)

= 1,522

() = ((0

7) log2

0

7) + ((

5

7) log2

5

7) + ((

2

7) log2

2

7)

= 0,863

Selanjutnya adalah melakukan perhitungan nilai gain dari seluruh atribut data.

Berikut perhitungannya:

(, ) = 1,581 ((9

20) 1,585 + (

6

20) 1,000 + (

5

20) 1,371)

= 0,225

(, ) = 1,581 ((13

20) 0,996 + (

7

20) 0,000)

= 0,934

(, ) = 1,581 ((11

20) 1,435 + (

9

20) 0,991)

= 0,346

(, ) = 1,581 ((

4

20) 1,500 + (

1

20) 0,000

+ (9

20) 1,530 + (

6

20) 1,585

)

= 0,117 (, )

= 1,581 ((8

20) 1,406 + (

5

20) 1,522 + (

7

20) 0,863)

= 0,336

Hasil perhitungan entropi dan gain dapat dilihat pada tabel berikut:

Atribut Entropi Gain

Total 1.581

Kehadiran

Tinggi 1.585

0.225 Sedang 1.000

Rendah 1.371

Prestasi Tinggi 0.996

0.934 Rendah 0.000

Lama Bekerja Lama 1.435

0.346 Baru 0.991

Tanggungan

Banyak 1.500

0.117 Sedikit 0.000

Menengah 1.530

Tidak Ada 1.585

Pendidikan

Tinggi 1.406

0.336 Sedang 1.522

Rendah 0.863

Dari hasil perhitungan di atas, tampak bahwa atribut dengan nilai gain

tertinggi adalah Prestasi, yaitu sebesar 0,934. Oleh karena itu atribut Prestasi

dijadikan sebagai akar.

Ada dua nilai atribut ini, yaitu Tinggi dan Rendah yang dijadikan sebagai

cabang dari akar Prestasi. Data dari prestasi tinggi dan rendah dipisah seperti

tabel berikut.

Tabel Data Prestasi Tinggi




Rendah Tinggi Lama Menengah Rendah B












Tabel Data Prestasi Rendah



Sedang Rendah Baru Sedikit Sedang C

Tinggi Rendah Baru Banyak Tinggi C

Tinggi Rendah Lama Menengah Rendah C

Sedang Rendah Lama Tidak Ada Sedang C

Tinggi Rendah Baru Tidak Ada Tinggi C

Rendah Rendah Lama Menengah Tinggi C

Sedang Rendah Baru Menengah Rendah C

Pembentukan Node Keputusan 1.1

Berikutnya adalah pembentukan node keputusan 1.1 dengan memilih atribut

dengan nilai gain tertinggi, selain atribut Prestasi. Sama seperti langkah

sebelumnya, harus dilakukan perhitungan jumlah objek data sampel dengan

golongan (kelas data) A, B, dan C serta dibagi berdasarkan atribut kehadiran,

lama bekerja, tanggungan, dan pendidikan. Selain itu, jumlah objek data yang

dihitung merupakan data dengan atribut Prestasi bernilai Tinggi. Tabel

berikut menggambarkan hasil penghitungan jumlah objek data sampel

dengan atribut prestasi bernilai tinggi.

Prestasi

Rendah Tinggi

GOL C 1.1 ?

Atribut Jumlah

Kasus

Golongan

A B C

Total 13 6 7 0

Kehadiran

Tinggi 6 3 3 0

Sedang 3 0 3 0

Rendah 4 3 1 0


Baru 5 0 5 0

Tanggungan

Banyak 3 2 1 0

Sedikit 0 0 0 0

Menengah 6 2 4 0

Tidak Ada 4 2 2 0

Pendidikan

Tinggi 5 4 1 0

Sedang 3 2 1 0

Rendah 5 0 5 0



Entropi Total :

() = ((6

13) log2

6

13) + ((

7

13) log2

7

13) + ((

0

13) log2

0

13)

= 0,996

Entropi Kehadiran :

() = ((3

6) log2

3

6) + ((

3

6) log2

3

6) + ((

0

6) log2

0

6)

= 1,000

() = ((0

3) log2

0

3) + ((

3

3) log2

3

3) + ((

0

3) log2

0

3)

= 0,000

() = ((3

4) log2

3

4) + ((

1

4) log2

1

4) + ((

0

4) log2

0

4)

= 0,811


() = ((6

8) log2

6

8) + ((

2

8) log2

2

8) + ((

0

8) log2

0

8)

= 0,811

() = ((0

5) log2

0

5) + ((

5

5) log2

5

5) + ((

0

5) log2

0

5)

= 0,000


() = ((2

3) log2

2

3) + ((

1

3) log2

1

3) + ((

0

3) log2

0

3)

= 0,918

() = ((0

0) log2

0

0) + ((

0

0) log2

0

0) + ((

0

0) log2

0

0)

= 0,000

() = ((2

6) log2

2

6) + ((

4

6) log2

4

6) + ((

0

6) log2

0

6)

= 0,918

( ) = ((2

4) log2

2

4) + ((

2

4) log2

2

4) + ((

0

4) log2

0

4)

= 1,000


() = ((4

5) log2

4

5) + ((

1

5) log2

1

5) + ((

0

5) log2

0

5)

= 0,722

() = ((2

3) log2

2

3) + ((

1

3) log2

1

3) + ((

0

3) log2

0

3)

= 0,918

() = ((0

5) log2

0

5) + ((

5

5) log2

5

5) + ((

0

5) log2

0

5)

= 0,000



(, ) = 0,996 ((6

13) 1,000 + (

3

13) 0,000 + (

4

13) 0,811)

= 0,285

(, ) = 0,996 ((8

13) 0,811 + (

5

13) 0,000)

= 0,496

(, ) = 0,996 ((

3

13) 0,918 + (

0

13) 0,000

+ (6

13) 0,918 + (

4

13) 1,000

)

= 0,052

(, )

= 0,996 ((5

13) 0,722 + (

3

13) 0,918 + (

5

13) 0,000)

= 0,506

Hasil perhitungan di atas dapat dilihat pada tabel berikut:


Total 0.996

Kehadiran

Tinggi 1.000

0.285 Sedang 0.000

Rendah 0.811


0.496 Baru 0.000

Tanggungan

Banyak 0.918

0.052 Sedikit 0.000

Menengah 0.918

Tidak Ada 1.000

Pendidikan

Tinggi 0.722

0.506 Sedang 0.918

Rendah 0.000


tertinggi adalah Pendidikan, yaitu sebesar 0,506. Oleh karena itu atribut

Pendidikan dijadikan sebagai node keputusan 1.1. Ada tiga nilai atribut ini,

yaitu Tinggi, Sedang, dan Rendah yang dijadikan sebagai cabang dari node

keputusan Pendidikan. Data dari atribut pendidikan dipisah seperti berikut.

Tabel Data Prestasi Tinggi dan Pendidikan Tinggi








Tabel Data Prestasi Tinggi dan Pendidikan Sedang






Tabel Data Prestasi Tinggi dan Pendidikan Rendah



Rendah Tinggi Lama Menengah Rendah B





Cabang Tinggi dan Sedang masih perlu dilakukan perhitungan lebih lanjut

lagi, karena seluruh data sampel belum terkumpul di satu kelas yang sama.

Cabang Rendah sudah dapat mengklasifikasikan objek data ke dalam

Golongan B, karena seluruh data sampel sudah terkumpul di kelas B. Berikut

adalah gambaran decision tree yang sudah terbentuk pada tahapan ini.

Pembentukan Node keputusan 1.1.1

Berikutnya adalah pembentukan node keputusan 1.1.1 dengan memilih

atribut dengan nilai gain tertinggi, selain atribut Prestasi dan Pendidikan.

Sama seperti langkah sebelumnya, harus dilakukan perhitungan jumlah objek

data sampel dengan golongan (kelas data) A, B, dan C serta dibagi

berdasarkan atribut kehadiran, lama bekerja, tanggungan, dan pendidikan.

Prestasi

Rendah Tinggi

GOL C 1.1

Pendidikan

1.1.2 ?

GOL B 1.1.1 ?

Rendah Tinggi

Sedang

Selain itu, jumlah objek data yang dihitung merupakan data dengan atribut

Prestasi bernilai Tinggi dan atribut Pendidikan bernilai Tinggi. Tabel berikut

menggambarkan hasil penghitungan jumlah objek data sampel dengan atribut

Pendidikan Tinggi.

Atribut Jumlah

Kasus

Golongan

A B C

Total 5 4 1 0

Kehadiran

Tinggi 2 2 0 0

Sedang 1 0 1 0

Rendah 2 2 0 0


Baru 1 0 1 0

Tanggungan

Banyak 1 1 0 0

Sedikit 0 0 0 0

Menengah 1 1 0 0

Tidak Ada 3 2 1 0



Entropi Total :

() = ((4

5) log2

4

5) + ((

1

5) log2

1

5) + ((

0

5) log2

0

5)

= 0,722

Entropi Kehadiran :

() = ((2

2) log2

2

2) + ((

0

2) log2

0

2) + ((

0

2) log2

0

2)

= 0,000

() = ((0

1) log2

0

1) + ((

1

1) log2

1

1) + ((

0

1) log2

0

1)

= 0,000

() = ((2

2) log2

2

2) + ((

0

2) log2

0

2) + ((

0

2) log2

0

2)

= 0,000


() = ((4

4) log2

4

4) + ((

0

4) log2

0

4) + ((

0

4) log2

0

4)

= 0,000

() = ((0

1) log2

0

1) + ((

1

1) log2

1

1) + ((

0

1) log2

0

1)

= 0,000


() = ((1

1) log2

1

1) + ((

0

1) log2

0

1) + ((

0

1) log2

0

1)

= 0,000

() = ((0

0) log2

0

0) + ((

0

0) log2

0

0) + ((

0

0) log2

0

0)

= 0,000

() = ((1

1) log2

1

1) + ((

0

1) log2

0

1) + ((

0

1) log2

0

1)

= 0,000

( ) = ((2

3) log2

2

3) + ((

1

3) log2

1

3) + ((

0

3) log2

0

3)

= 0,918



(, ) = 0,722 ((2

5) 0,000 + (

1

5) 0,000 + (

2

5) 0,000)

= 0,722

(, ) = 0,722 ((4

5) 0,000 + (

1

5) 0,000)

= 0,722

(, ) = 0,722 ((

1

5) 0,000 + (

0

5) 0,000

+ (1

5) 0,000 + (

3

5) 0,918

)

= 0,171



Total 0.722

Kehadiran

Tinggi 0.000

0.722 Sedang 0.000

Rendah 0.000


0.722 Baru 0.000

Tanggungan

Banyak 0.000

0.171 Sedikit 0.000

Menengah 0.000

Tidak Ada 0.918


tertinggi adalah Kehadiran dan Lama Bekerja, yaitu sebesar 0,722. Oleh

karena itu dipilih salah satu dari atribut tesebut. Missal dipilih atribut

Kehadiran dijadikan sebagai node keputusan 1.1.1. Ada tiga nilai atribut ini,

yaitu Tinggi, Sedang, dan Rendah yang dijadikan sebagai cabang dari node

keputusan Kehadiran.

Tabel Data Prestasi Tinggi, Pendidikan Tinggi dan Kehadiran Tinggi





Tabel Data Prestasi Tinggi, Pendidikan Tinggi dan Kehadiran Sedang




Tabel Data Prestasi Tinggi, Pendidikan Tinggi dan Kehadiran Rendah





Cabang Tinggi, Sedang, dan Rendah sudah tidak perlu dilakukan perhitungan

lebih lanjut lagi, karena seluruh data sampel sudah terkumpul di satu kelas

yang sama. Cabang Tinggi sudah dapat mengklasifikasikan objek data ke

dalam Golongan A, karena seluruh data sampel sudah terkumpul di kelas A.

Cabang Sedang sudah dapat mengklasifikasikan objek data ke dalam

Golongan B, karena seluruh data sampel sudah terkumpul di kelas B. Cabang

Rendah sudah dapat mengklasifikasikan objek data ke dalam Golongan A,

karena seluruh data sampel sudah terkumpul di kelas A. Berikut adalah

gambaran decision tree yang sudah terbentuk pada tahapan ini.


Prestasi

Rendah Tinggi

GOL C 1.1

Pendidikan

1.1.2 ?

GOL B 1.1.1 Kehadiran

Rendah Tinggi

Sedang

GOL B

Rendah

GOL A GOL A

Sedang Tinggi


atribut dengan nilai gain tertinggi, selain atribut Prestasi dan Pendidikan.



berdasarkan atribut kehadiran, lama bekerja, tanggungan, dan pendidikan.

Selain itu, jumlah objek data yang dihitung merupakan data dengan atribut

Prestasi bernilai Tinggi dan atribut Pendidikan bernilai Sedang. Tabel berikut

menggambarkan hasil penghitungan jumlah objek data sampel tersebut.

Atribut Jumlah

Kasus

Golongan

A B C

Total 3 2 1 0

Kehadiran

Tinggi 2 1 1 0

Sedang 0 0 0 0

Rendah 1 1 0 0


Baru 1 0 1 0

Tanggungan

Banyak 1 1 0 0

Sedikit 0 0 0 0

Menengah 1 1 0 0

Tidak Ada 1 0 1 0



Entropi Total :

() = ((2

3) log2

2

3) + ((

1

3) log2

1

3) + ((

0

3) log2

0

3)

= 0,918

Entropi Kehadiran :

() = ((1

2) log2

1

2) + ((

1

2) log2

1

2) + ((

0

2) log2

0

2)

= 1,000

() = ((0

0) log2

0

0) + ((

0

0) log2

0

0) + ((

0

0) log2

0

0)

= 0,000

() = ((1

1) log2

1

1) + ((

0

1) log2

0

1) + ((

0

1) log2

0

1)

= 0,000


() = ((2

2) log2

2

2) + ((

0

2) log2

0

2) + ((

0

2) log2

0

2)

= 0,000

() = ((0

1) log2

0

1) + ((

1

1) log2

1

1) + ((

0

1) log2

0

1)

= 0,000


() = ((1

1) log2

1

1) + ((

0

1) log2

0

1) + ((

0

1) log2

0

1)

= 0,000

() = ((0

0) log2

0

0) + ((

0

0) log2

0

0) + ((

0

0) log2

0

0)

= 0,000

() = ((1

1) log2

1

1) + ((

0

1) log2

0

1) + ((

0

1) log2

0

1)

= 0,000

( ) = ((0

1) log2

0

1) + ((

1

1) log2

1

1) + ((

0

1) log2

0

1)

= 0,000



(, ) = 0,918 ((2

3) 1,000 + (

0

3) 0,000 + (

1

3) 0,000)

= 0,252

(, ) = 0,918 ((2

3) 0,000 + (

1

3) 0,000)

= 0,918

(, ) = 0,918 ((

1

3) 0,000 + (

0

3) 0,000

+ (1

3) 0,000 + (

1

3) 0,000

)

= 0,918



Total 0.918

Kehadiran

Tinggi 1.000

0.252 Sedang 0.000

Rendah 0.000


0.918 Baru 0.000

Tanggungan

Banyak 0.000

0.918 Sedikit 0.000

Menengah 0.000

Tidak Ada 0.000


tertinggi adalah Lama Bekerja dan Tanggungan, yaitu sebesar 0,918. Oleh

karena itu dipilih salah satu dari atribut tersebut. Misal dipilih atribut Lama

Bekerja dijadikan sebagai node keputusan 1.1.2.

Tabel Data Prestasi Tinggi, Pendidikan Sedang dan Lama Bekerja Lama





Tabel Data Prestasi Tinggi, Pendidikan Sedang dan Lama Bekerja Baru




Ada dua nilai atribut ini, yaitu Lama dan Baru yang dijadikan sebagai cabang

dari node keputusan Lama Bekerja. Cabang Lama dan Baru sudah tidak perlu

dilakukan perhitungan lebih lanjut lagi, karena seluruh data sampel sudah

terkumpul di satu kelas yang sama. Cabang Lama sudah dapat

mengklasifikasikan objek data ke dalam Golongan A, karena seluruh data

sampel sudah terkumpul di kelas A. Cabang Baru sudah dapat

mengklasifikasikan objek data ke dalam Golongan B, karena seluruh data

sampel sudah terkumpul di kelas B. Berikut adalah gambaran decision tree

yang sudah terbentuk pada tahapan ini.

Proses pembentukan pohon keputusan sudah berakhir, karena sudah tidak ada

cabang yang perlu dilakukan perhitungan lebih lanjut lagi. Pada perhitungan

setiap cabang, seluruh objek data sampel sudah berkumpul di satu kelas yang

sama.

Prestasi

Rendah Tinggi

GOL C 1.1

Pendidikan

1.1.2 Lama Bekerja

Rendah Sedang

Tinggi

1.1.1 Kehadiran

GOL B

GOL B

Rendah

GOL A GOL A

Sedang Tinggi

GOL B

Lama

GOL A

Baru

Berikut adalah contoh data baru. Data ini akan diklasifikasikan ke dalam

Golongan Karyawan A, B, atau C. dengan menggunakan decision tree di atas:

No Kehadiran Prestasi Lama


1 Rendah Tinggi Lama Tidak Ada Tinggi ?

2 Sedang Tinggi Baru Banyak Tinggi ?

Untuk data no 1 diketahui data baru dengan atribut kehadiran bernilai rendah,

atribut pretasi bernilai Tinggi, atribut lama bekerja bernilai Lama, atribut

tanggungan bernilai Tidak Ada, dan atribut pendidikan bernilai Tinggi.

Aturan yang terjadi sesuai dengan data baru tersebut adalah

IF (Prestasi = Tinggi) ^ (Pendidikan = Tinggi) ^

(Kehadiran = Rendah) THEN (Gol = Gol A)

Dari penelusuran di atas, diketahui bahwa data baru karyawan tersebut

diklasifikasi sebagai karyawan dengan Golongan A

Untuk data no 2 diketahui data baru dengan atribut kehadiran bernilai sedang,

atribut pretasi bernilai Tinggi, atribut lama bekerja bernilai Baru, atribut

tanggungan bernilai Banyak, dan atribut pendidikan bernilai Tinggi. Aturan

yang terjadi sesuai dengan data baru tersebut adalah

IF (Prestasi = Tinggi) ^ (Pendidikan = Tinggi) ^

(Kehadiran = Rendah) THEN (Gol = Gol B)


diklasifikasi sebagai karyawan dengan Golongan B

4.1.2 C4.5

Metode klasifikasi berikutnya yang cukup popular adalah algoritma

C4.5. Algoritma C4.5 merupakan pengembangan dari algoritma ID3. Konsep

dasar algoritma C4.5 memiliki kesamaan dengan IDE. Perbedaan utama C4.5

dari ID3 adalah:

- C4.5 dapat menangani atribut kontinyu dan diskrit.

- C4.5 dapat menangani training data dengan missing value.

- Hasil pohon keputusan C4.5 akan dipangkas setelah dibentuk.

- Pemilihan atribut yang dilakukan dengan menggunakan Gain ratio.

Gain ratio

Informasi gain pada ID3 lebih memilih atribut yang memiliki data

yang besar. Sebagai contoh, mempertimbangkan atribut yang berfungsi

sebagai unique identifier, seperti product_ID akan menghasilkan keluaran

dalam jumlah yang banyak, di mana setiap keluaran hanya terdiri dari satu

tuple. Karena setiap partisi murni, informasi yang diperlukan untuk

mengklasifikasikan data set D berdasarkan partisi ini akan menjadi

Infoproduct ID (D) = 0. Sebagai akibatnya, informasi yang diperoleh oleh

partisi pada atribut ini adalah maksimal. Padahal, jelas sekali terlihat bahwa

partisi semacam ini tidaklah berguna.

C4.5 sebagai penerus dari ID3 menggunakan ekstensi untuk informasi

gain yang dikenal sebagai gain ratio untuk mengatasi bias yang terjadi pada

ID3. Ini semacam bentuk normalisasi untuk mendapatkan informasi

menggunakan split informasi yang dapat didefinisikan seperti berikut.

() =

=0

||

|| 2 (

||

||)

Dimana:

D = ruang (data) sample yang digunakan untuk training.

Dj = jumlah sample untuk atribut i

Nilai ini merupakan informasi yang potensial yang dihasilkan dengan

memisahkan set data pelatihan, D, menjadi partisi v, sesuai dengan hasil v

dari tes pada atribut A. Untuk mecari nilai gain ratio didefinisikan seperti

berikut.

() = ()

()

Contoh Penerapan Algoritma C4.5

Sebagai contoh penerapan algortima C4.5 akan digunakan contoh data

sebagai berikut. Sebuah perusahaan akan memberikan bonus tahunan kepada

seluruh karyawannya. Untuk memberikan bonus ini, departemen

kepegawaian perusahaan ini melakukan pembagian karyawan ke dalam tiga

buah golongan yaitu, Golongan A, Golongan B, dan Golongan C. Berikut

adalah bonus yang diperoleh oleh masing-masing golongan karyawan.

Golongan Bonus Tahunan

A Rp 10.000.000,00

B Rp 5.000.000,00

C Rp 2.500.000,00

Dalam melakukan klasifikasi karyawan ke dalam tiga golongan ini,

departemen kepegawaian menggunakan lima buah parameter, yaitu:

1. Tingkat kehadiran karyawan (Tinggi, Sedang, Rendah) 2. Prestasi karyawan (Tinggi, Rendah) 3. Lama karyawan bekerja di perusahaan ini (Lama, Baru) 4. Jumlah tanggungan karyawan (Banyak, Menengah, Sedikit, Tidak

Ada)

5. Pendidikan karyawan (Tinggi, Sedang, Rendah).

Berikut ini adalah data arsip karyawan yang sudah terklasifikasi secara valid.



1 Tinggi Tinggi Lama Tidak Ada Tinggi A

2 Sedang Rendah Baru Sedikit Sedang C

3 Rendah Tinggi Lama Menengah Rendah B

4 Tinggi Rendah Baru Banyak Tinggi C

5 Sedang Tinggi Baru Menengah Rendah B

6 Tinggi Tinggi Baru Menengah Rendah B

7 Tinggi Rendah Lama Menengah Rendah C

8 Rendah Tinggi Lama Tidak Ada Tinggi A

9 Sedang Tinggi Baru Tidak Ada Tinggi B

10 Sedang Rendah Lama Tidak Ada Sedang C

11 Rendah Tinggi Lama Banyak Sedang A

12 Tinggi Tinggi Lama Banyak Tinggi A

13 Tinggi Tinggi Lama Banyak Rendah B

14 Tinggi Rendah Baru Tidak Ada Tinggi C

15 Tinggi Tinggi Baru Tidak Ada Sedang B

16 Rendah Rendah Lama Menengah Tinggi C

17 Sedang Rendah Baru Menengah Rendah C


19 Rendah Tinggi Lama Menengah Tinggi A

20 Tinggi Tinggi Lama Menengah Sedang A

Pembentukan Akar

Langkah pertama dalam algortima ini adalah pembentukan akar dengan

memilih atribut dengan nilai gain ratio tertinggi. Sebelum melakukan hal

tersebut, harus dilakukan perhitungan jumlah objek data sampel dengan


prestasi, lama bekerja, tanggungan, dan pendidikan. Tabel berikut

menggambarkan hasil penghitungan jumlah objek data sampel tersebut.

Atribut Jumlah Kasus Golongan

A B C

Total 20 6 7 7

Kehadiran

Tinggi 9 3 3 3

Sedang 6 0 3 3

Rendah 5 3 1 1

Prestasi Tinggi 13 6 7 0

Rendah 7 0 0 7


Baru 9 0 5 4

Tanggungan

Banyak 4 2 1 1

Sedikit 1 0 0 1

Menengah 9 2 4 3

Tidak Ada 6 2 2 2

Pendidikan

Tinggi 8 4 1 3

Sedang 5 2 1 2

Rendah 7 0 5 2



Entropi Total :

() = ((6

20) log2

6

20) + ((

7

20) log2

7

20) + ((

7

20) log2

7

20)

= 1,581

Entropi Kehadiran :

() = ((3

9) log2

3

9) + ((

3

9) log2

3

9) + ((

3

9) log2

3

9)

= 1,585

() = ((0

6) log2

0

6) + ((

3

6) log2

3

6) + ((

3

6) log2

3

6)

= 1,000

() = ((3

5) log2

3

5) + ((

1

5) log2

1

5) + ((

1

5) log2

1

5)

= 1,371

Entropi Prestasi :

() = ((6

13) log2

6

13) + ((

7

13) log2

7

13) + ((

0

13) log2

0

13)

= 0,996

() = ((0

7) log2

0

7) + ((

0

7) log2

0

7) + ((

7

7) log2

7

7)

= 0,000


() = ((6

11) log2

6

11) + ((

2

11) log2

2

11) + ((

3

11) log2

3

11)

= 1,435

() = ((0

9) log2

0

9) + ((

5

9) log2

5

9) + ((

4

9) log2

4

9)

= 0,991


() = ((2

4) log2

2

4) + ((

1

4) log2

1

4) + ((

1

4) log2

1

4)

= 1,500

() = ((0

1) log2

0

1) + ((

0

1) log2

0

1) + ((

1

1) log2

1

1)

= 0,000

() = ((2

9) log2

2

9) + ((

4

9) log2

4

9) + ((

3

9) log2

3

9)

= 1,530

( ) = ((2

6) log2

2

6) + ((

2

6) log2

2

6) + ((

2

6) log2

2

6)

= 1,585


() = ((4

8) log2

4

8) + ((

1

8) log2

1

8) + ((

3

8) log2

3

8)

= 1,406

() = ((2

5) log2

2

5) + ((

1

5) log2

1

5) + ((

2

5) log2

2

5)

= 1,522

() = ((0

7) log2

0

7) + ((

5

7) log2

5

7) + ((

2

7) log2

2

7)

= 0,863



(, ) = 1,581 ((9

20) 1,585 + (

6

20) 1,000 + (

5

20) 1,371)

= 0,225

(, ) = 1,581 ((13

20) 0,996 + (

7

20) 0,000)

= 0,934

(, ) = 1,581 ((11

20) 1,435 + (

9

20) 0,991)

= 0,346

(, ) = 1,581 ((

4

20) 1,500 + (

1

20) 0,000

+ (9

20) 1,530 + (

6

20) 1,585

)

= 0,117 (, )

= 1,581 ((8

20) 1,406 + (

5

20) 1,522 + (

7

20) 0,863)

= 0,336

Selanjutnya adalah melakukan perhitungan nilai Splitinfo dari seluruh atribut


() = (9

20) log2

9

20 (

6

20) log2

6

20 (

5

20) log2

5

20

= 1.539

() = (13

20) log2

13

20 (

7

20) log2

7

20

= 0.934

( ) = (11

20) log2

11

20 (

9

20) log2

9

20

= 0.993

()

= (4

20) log2

4

20 (

1

20) log2

1

20 (

9

20) log2

9

20 (

6

20) log2

6

20

= 1.720

() = (8

20) log2

8

20 (

5

20) log2

5

20 (

7

20) log2

7

20

= 1.559

Selanjutnya adalah melakukan perhitungan nilai Gain ratio dari seluruh

atribut data. Berikut perhitungannya:

() = 0.225 / 1.539 = 0.146

() = 0.934 / 0.934 = 1

( ) = 0.346 / 0.993 = 0.348

() = 0.117 / 1.720 = 0.068

() = 0.336 / 1.559 = 0.216

Hasil perhitungan entropi, gain, splitinfo dan gain ratio dapat dilihat pada

tabel berikut:

Atribut Entropi Gain Split

Info

Ratio

Gain

Total 1.581

Kehadiran

Tinggi 1.585

0.225 1.539 0.146 Sedang 1.000

Rendah 1.371

Prestasi Tinggi 0.996

0.934 0.934 1 Rendah 0.000


0.346 0.993 0.348 Baru 0.991

Tanggungan

Banyak 1.500

0.117 1.720 0.068 Sedikit 0.000

Menengah 1.530

Tidak Ada 1.585

Pendidikan

Tinggi 1.406

0.336 1.559 0.216 Sedang 1.522

Rendah 0.863

Dari hasil perhitungan di atas, tampak bahwa atribut dengan nilai gain ratio

tertinggi adalah Prestasi, yaitu sebesar 1. Oleh karena itu atribut Prestasi

dijadikan sebagai akar.

Ada dua nilai atribut Prestasi, yaitu Tinggi dan Rendah yang dijadikan

sebagai cabang dari akar Prestasi. Data dari prestasi tinggi dan rendah dipisah

seperti tabel berikut.

Tabel Data Prestasi Tinggi
















Tabel Data Prestasi Rendah



2 Sedang Rendah Baru Sedikit Sedang C

4 Tinggi Rendah Baru Banyak Tinggi C

7 Tinggi Rendah Lama Menengah Rendah C

10 Sedang Rendah Lama Tidak Ada Sedang C

14 Tinggi Rendah Baru Tidak Ada Tinggi C

16 Rendah Rendah Lama Menengah Tinggi C

17 Sedang Rendah Baru Menengah Rendah C

Cabang Tinggi masih perlu dilakukan perhitungan lebih lanjut lagi, karena

seluruh data sampel belum terkumpul di satu kelas yang sama. Cabang

Rendah sudah dapat mengklasifikasikan objek data ke dalam Golongan C,

karena seluruh data sampel sudah terkumpul di kelas C. Berikut adalah


Pembentukan Node keputusan 1.1

Berikutnya adalah pembentukan node keputusan 1.1 dengan memilih atribut

dengan nilai gain ratio tertinggi, selain atribut Prestasi. Sama seperti langkah

sebelumnya, harus dilakukan perhitungan jumlah objek data sampel dengan


lama bekerja, tanggungan, dan pendidikan. Selain itu, jumlah objek data yang

dihitung merupakan data dengan atribut Prestasi bernilai Tinggi. Tabel

berikut menggambarkan hasil penghitungan jumlah objek data sampel

dengan atribut prestasi bernilai tinggi.

Atribut Jumlah

Kasus

Golongan

A B C

Total 13 6 7 0

Kehadiran

Tinggi 6 3 3 0

Sedang 3 0 3 0

Rendah 4 3 1 0


Baru 5 0 5 0

Tanggungan

Banyak 3 2 1 0

Sedikit 0 0 0 0

Menengah 6 2 4 0

Tidak Ada 4 2 2 0

Pendidikan

Tinggi 5 4 1 0

Sedang 3 2 1 0

Rendah 5 0 5 0

Prestasi

Rendah Tinggi

GOL C 1.1 ?


data kecuali atribut prestasi. Berikut perhitungannya:

Entropi Total :

() = ((6

13) log2

6

13) + ((

7

13) log2

7

13) + ((

0

13) log2

0

13)

= 0,996

Entropi Kehadiran :

() = ((3

6) log2

3

6) + ((

3

6) log2

3

6) + ((

0

6) log2

0

6)

= 1,000

() = ((0

3) log2

0

3) + ((

3

3) log2

3

3) + ((

0

3) log2

0

3)

= 0,000

() = ((3

4) log2

3

4) + ((

1

4) log2

1

4) + ((

0

4) log2

0

4)

= 0,811


() = ((6

8) log2

6

8) + ((

2

8) log2

2

8) + ((

0

8) log2

0

8)

= 0,811

() = ((0

5) log2

0

5) + ((

5

5) log2

5

5) + ((

0

5) log2

0

5)

= 0,000


() = ((2

3) log2

2

3) + ((

1

3) log2

1

3) + ((

0

3) log2

0

3)

= 0,918

() = ((0

0) log2

0

0) + ((

0

0) log2

0

0) + ((

0

0) log2

0

0)

= 0,000

() = ((2

6) log2

2

6) + ((

4

6) log2

4

6) + ((

0

6) log2

0

6)

= 0,918

( ) = ((2

4) log2

2

4) + ((

2

4) log2

2

4) + ((

0

4) log2

0

4)

= 1,000


() = ((4

5) log2

4

5) + ((

1

5) log2

1

5) + ((

0

5) log2

0

5)

= 0,722

() = ((2

3) log2

2

3) + ((

1

3) log2

1

3) + ((

0

3) log2

0

3)

= 0,918

() = ((0

5) log2

0

5) + ((

5

5) log2

5

5) + ((

0

5) log2

0

5)

= 0,000

Selanjutnya adalah melakukan perhitungan nilai gain dari seluruh atribut data

kecuali atribut prestasi. Berikut perhitungannya:

(, ) = 0,996 ((6

13) 1,000 + (

3

13) 0,000 + (

4

13) 0,811)

= 0,285

(, ) = 0,996 ((8

13) 0,811 + (

5

13) 0,000)

= 0,496

(, ) = 0,996 ((

3

13) 0,918 + (

0

13) 0,000

+ (6

13) 0,918 + (

4

13) 1,000

)

= 0,052

(, )

= 0,996 ((5

13) 0,722 + (

3

13) 0,918 + (

5

13) 0,000)

= 0,506



() = (6

13) log2

6

13 (

3

13) log2

3

13 (

4

13) log2

4

13

= 1.526

( ) = (8

13) log2

8

13 (

5

13) log2

5

13

= 0.961

()

= (3

13) log2

3

13 (

0

13) log2

0

13 (

6

13) log2

6

13 (

4

13) log2

4

13

= ~

() = (5

13) log2

5

13 (

3

13) log2

3

13 (

5

13) log2

5

13

= 1.549



() = 0.285 / 1.526 = 0.186

( ) = 0.496 / 0.961 = 0.517

() = 0.052 / ~ = ~

() = 0.506/ 1.549 = 0.327



Info

Ratio

Gain

Total 0.996

Kehadiran

Tinggi 1.000

0.285 1.526 0.186 Sedang 0.000

Rendah 0.811


0.496 0.961 0.517 Baru 0.000

Tanggungan

Banyak 0.918

0.052 ~ ~ Sedikit 0.000

Menengah 0.918

Tidak Ada 1.000

Pendidikan

Tinggi 0.722

0.506 1.549 0.327 Sedang 0.918

Rendah 0.000

Dari hasil perhitungan di atas, tampak bahwa atribut dengan nilai gain ratio

tertinggi adalah Lama Bekerja, yaitu sebesar 0,517. Oleh karena itu atribut

Lama Bekerja dijadikan sebagai node keputusan 1.1. Ada dua nilai atribut ini,

yaitu Lama dan Baru yang dijadikan sebagai cabang dari node keputusan

Lama Bekerja. Data dari atribut Lama Bekerja dipisah seperti berikut.

Tabel Data Prestasi Tinggi dan Lama Bekerja Baru








Tabel Data Prestasi Tinggi dan Lama Bekerja Lama











Data Lama Bekerja = Lama masih perlu dilakukan perhitungan lebih lanjut

lagi, karena seluruh data sampel belum terkumpul di satu kelas yang sama.

Cabang Lama Bekerja = Baru sudah dapat mengklasifikasikan objek data ke

dalam Golongan B, karena seluruh data sampel sudah terkumpul di kelas B.

Berikut adalah gambaran pohon keputusan yang sudah terbentuk pada

tahapan ini.


Prestasi

Rendah Tinggi

GOL C 1.1

Lama Bekerja

GOL B 1.1.1 ?

Baru Lama


atribut dengan nilai gain tertinggi, selain atribut Prestasi dan Lama Bekerja.



berdasarkan atribut kehadiran, tanggungan, dan pendidikan. Selain itu,

jumlah objek data yang dihitung merupakan data dengan atribut Prestasi

bernilai Tinggi dan atribut Lama Bekerja = Lama. Tabel berikut

menggambarkan hasil penghitungan jumlah objek data sampel dengan atribut

Prestasi bernilai Tinggi dan atribut Lama Bekerja = Lama.

Atribut Jumlah

Kasus

Golongan

A B C

Total 8 6 2 0

Kehadiran

Tinggi 4 3 1 0

Sedang 0 0 0 0

Rendah 4 3 1 0

Tanggungan

Banyak 3 2 1 0

Sedikit 0 0 0 0

Menengah 3 2 1 0

Tidak Ada 2 2 0 0

Pendidikan

Tinggi 4 4 0 0

Sedang 2 2 0 0

Rendah 2 0 2 0


data Kehadiran, Tanggungan dan Pendidikan. Berikut perhitungannya:

Entropi Total :

() = ((6

8) log2

6

8) + ((

2

8) log2

2

8) + ((

0

8) log2

0

8)

= 0,811

Entropi Kehadiran :

() = ((3

4) log2

3

4) + ((

1

4) log2

1

4) + ((

0

4) log2

0

4)

= 0,811

() = ((0

0) log2

0

0) + ((

0

0) log2

0

0) + ((

0

0) log2

0

0)

= 0,000

() = ((3

4) log2

3

4) + ((

1

4) log2

1

4) + ((

0

4) log2

0

4)

= 0,811


() = ((2

3) log2

2

3) + ((

1

3) log2

1

3) + ((

0

3) log2

0

3)

= 0,918

() = ((0

0) log2

0

0) + ((

0

0) log2

0

0) + ((

0

0) log2

0

0)

= 0,000

() = ((2

3) log2

2

3) + ((

1

3) log2

1

3) + ((

0

3) log2

0

3)

= 0,918

( ) = ((2

2) log2

2

2) + ((

0

2) log2

0

2) + ((

0

2) log2

0

2)

= 0,000


() = ((4

4) log2

4

4) + ((

0

4) log2

0

4) + ((

0

4) log2

0

4)

= 0,000

() = ((2

2) log2

2

2) + ((

0

2) log2

0

2) + ((

0

2) log2

0

2)

= 0,000

() = ((0

2) log2

0

2) + ((

2

2) log2

2

2) + ((

0

2) log2

0

2)

= 0,000

Selanjutnya adalah melakukan perhitungan nilai gain dari seluruh atribut data

Kehadiran, Tanggungan dan Pendidikan. Berikut perhitungannya:

(, ) = 0,811 ((4

8) 0,811 + (

0

8) 0,000 + (

4

8) 0,811)

= 0,000

(, ) = 0,811 ((

3

8) 0,918 + (

0

8) 0,000

+ (3

8) 0,918 + (

2

8) 0,000

)

= 0,123

(, ) = 0,811 ((4

8) 0,000 + (

2

8) 0,000 + (

2

8) 0,000)

= 0,811



() = (4

8) log2

4

8 (

0

8) log2

0

8 (

4

8) log2

4

8

= ~

()

= (3

8) log2

3

8 (

0

8) log2

0

8 (

3

8) log2

3

8 (

2

8) log2

2

8

= ~

() = (4

8) log2

4

8 (

2

8) log2

2

8 (

2

8) log2

2

8

= 1.500



() = 0.000 / ~ = ~

() = 0.123 / ~ = ~

() = 0.811/ 1.500 = 0.541



Info

Ratio

Gain

Total 0.811

Kehadiran

Tinggi 0.811

0.000 ~ ~ Sedang 0.000

Rendah 0.811

Tanggungan

Banyak 0.344

0.123 ~ ~ Sedikit 0.000

Menengah 0.344

Tidak Ada 0.000

Pendidikan

Tinggi 0.000

0.811 1.500 0.541 Sedang 0.000

Rendah 0.000


tertinggi adalah Pendidikan, yaitu sebesar 0,541. Oleh karena Pendidikan

dijadikan sebagai node keputusan 1.1.1 Ada tiga nilai atribut ini, yaitu Tinggi,

Sedang, dan Rendah yang dijadikan sebagai cabang dari node keputusan

Pendidikan.

Tabel Data Prestasi Tinggi, Lama Bekerja Lama dan Pendidikan Tinggi







Tabel Data Prestasi Tinggi, Lama Bekerja Lama dan Pendidikan Sedang





Tabel Data Prestasi Tinggi, Lama Bekerja Lama dan Pendidikan Rendah





Cabang Tinggi, Sedang, dan Rendah sudah tidak perlu dilakukan perhitungan

lebih lanjut lagi, karena seluruh data sampel sudah terkumpul di satu kelas

yang sama. Cabang Tinggi sudah dapat mengklasifikasikan objek data ke

dalam Golongan A, karena seluruh data sampel sudah terkumpul di kelas A.

Cabang Sedang sudah dapat mengklasifikasikan objek data ke dalam

Golongan B, karena seluruh data sampel sudah terkumpul di kelas B. Cabang

Rendah sudah dapat mengklasifikasikan objek data ke dalam Golongan B,

karena seluruh data sampel sudah terkumpul di kelas B. Berikut adalah


Berikut adalah contoh data baru. Data ini akan diklasifikasikan ke dalam

Golongan Karyawan A, B, atau C. dengan menggunakan decision tree di atas:

Prestasi

Rendah Tinggi

GOL C 1.1

Lama Bekerja

GOL B 1.1.1

Pendidikan

Baru Lama

GOL A GOL B GOL A

Tinggi Rendah

Sedang



1 Rendah Tinggi Lama Tidak Ada Tinggi ?

2 Sedang Tinggi Baru Banyak Tinggi ?

Untuk data no 1 diketahui data baru dengan atribut kehadiran bernilai rendah,

atribut pretasi bernilai Tinggi, atribut lama bekerja bernilai Lama, atribut

tanggungan bernilai Tidak Ada, dan atribut pendidikan bernilai Tinggi.

Aturan yang terjadi sesuai dengan data baru tersebut adalah

IF (Prestasi = Tinggi) ^ (Lama Bekerja = Lama) ^

(Pendidikan = Tinggi) THEN (Gol = Gol A)


diklasifikasi sebagai karyawan dengan Golongan A

Untuk data no 2 diketahui data baru dengan atribut kehadiran bernilai sedang,

atribut pretasi bernilai Tinggi, atribut lama bekerja bernilai Baru, atribut

tanggungan bernilai Banyak, dan atribut pendidikan bernilai Tinggi. Aturan

yang terjadi sesuai dengan data baru tersebut adalah

IF (Prestasi = Tinggi) ^ (Lama Bekerja = Baru)

THEN (Gol = Gol B)


diklasifikasi sebagai karyawan dengan Golongan B

Pada data no 2 terlihat lebih cepat ditemukan nya hasil dibandingkan dengan

data no 1. Bila dibandingkan dengan algoritmaa ID3 sebelumnya, untuk

data no 2 juga lebih cepat ditemukan hasil dengan menggunakan algoritma

C4.5. Ini merupakan pengaruh dari penggunaan gain ratio pada algoritma

C4.5.

DAFTAR PUSTAKA

Quinlan, J. R. Induction of Decision trees. Machine Learning, vol. 1, pp. 81-

106, 1986

Han, J., Kamber, M. Data Mining: Concepts and Techniques. Morgan

Kaufmann, 2000

Larose, D.T. Discovering Knowledge in data An introduction to data

mining. John Wiley & Sons, 2005

http://nugikkool.blogspot.com/2012/08/pohon-keputusan-id3-dan-c45-

menggunakan.html

pembentukan pohon keputusan dengan id3 dan c4.5

Documents