Pertemuan 6 : KLASIFIKASI METODE ALGPRITMA C4.5

Algoritma C4.5 merupakan kelompok algoritma Decision Tree. Algoritma ini mempunyai input berupa training samples dan samplesTraining samples berupa data contoh yang akan digunakan untuk membangun sebuah tree yang telah diuji kebenarannya. Sedangkan samples merupakan field-field data yang nantinya akan digunakan sebagai parameter dalam melakukan klasifikasi data (Sunjana, 2010).

Algoritma C 4.5 adalah salah satu metode untuk membuat decision tree berdasarkan training data yang telah disediakan. Algoritma C 4.5 dibuat oleh Ross Quinlan yang merupakan pengembangan dari ID3 yang juga dibuat oleh Quinlan (Quinlan, 1993). Beberapa pengembangan yang dilakukan pada C4.5 antara lain adalah : bisa mengatasi missing value, bisa mengatasi continue data, dan pruning.

1.1. Klasifikasi

Klasifikasi data merupakan suatu proses yang menemukan properti-properti yang sama pada sebuah himpunan obyek di dalam sebuah basis data dan mengklasifikasikannya ke dalam kelas-kelas yang berbeda menurut model klasifikasi yang ditetapkan. Tujuan dari klasifikasi adalah untuk menemukan model dari training set yang membedakan atribut ke dalam kategori atau kelas yang sesuai, model tersebut kemudian digunakan untuk mengklasifikasikan atribut yang kelasnya belum diketahui sebelumnya. Teknik klasifikasi terbagi menjadi beberapa teknik yang diantaranya adalah Pohon Keputusan (Decision Tree).

1.2. Pohon Keputusan (Decision Tree)

Pohon keputusan merupakan metode klasifikasi dan prediksi yang sangat kuat dan terkenal. Metode pohon keputusan mengubah fakta yang sangat besar menjadi pohon keputusan yang merepresentasikan aturan. Aturan dapat dengan mudah dipahami dengan bahasa alami. Dan mereka juga dapat diekspresikan dalam bentuk bahasa basis data seperti Structured Query Language untuk mencari record pada kategori tertentu. Pohon keputusan juga berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variabel input dengan sebuah variabel target.

Karena pohon keputusan memadukan antara eksplorasi data dan pemodelan, pohon keputusan sangat bagus sebagai langkah awal dalam proses pemodelan bahkan ketika dijadikan sebagai model akhir dari beberapa teknik lain. Sebuah pohon keputusan adalah sebuah struktur yang dapat digunakan untuk membagi kumpulan data yang besar menjadi himpunan-himpunan record yang lebih kecil dengan menerapkan serangkaian aturan keputusan. Dengan masing-masing rangkaian pembagian, anggota himpunan hasil menjadi mirip satu dengan yang lain (Berry dan Linoff, 2004).

Sebuah model pohon keputusan terdiri dari sekumpulan aturan untuk membagi sejumlah populasi yang heterogen menjadi lebih kecil, lebih homogen dengan memperhatikan pada variabel tujuannya. Sebuah pohon keputusan mungkin dibangun dengan seksama secara manual atau dapat tumbuh secara otomatis dengan menerapkan salah satu atau beberapa algoritma pohon keputusan untuk memodelkan himpunan data yang belum terklasifikasi.

Variabel tujuan biasanya dikelompokkan dengan pasti dan model pohon keputusan lebih mengarah pada perhitungan probability dari tiap-tiap record terhadap kategori-kategori tersebut atau untuk mengklasifikasi record dengan mengelompokkannya dalam satu kelas. Pohon keputusan juga dapat digunakan untuk mengestimasi nilai dari variabel continue meskipun ada beberapa teknik yang lebih sesuai untuk kasus ini.

Banyak algoritma yang dapat dipakai dalam pembentukan pohon keputusan,antara lain ID3, CART, dan C4.5 (Larose, 2006).

Data dalam pohon keputusan biasanya dinyatakan dalam bentuk tabel dengan atribut dan record. Atribut menyatakan suatu parameter yang dibuat sebagai kriteria dalam pembentukan pohon. Misalkan untuk menentukan main tenis, kriteria yang diperhatikan adalah cuaca, angin, dan temperatur.

Salah satu atribut merupakan atribut yang menyatakan data solusi per item data yang disebut target atribut. Atribut memiliki nilai-nilai yang dinamakan dengan instance. Misalkan atribut cuaca mempunyai instance berupa cerah, berawan, dan hujan (Basuki dan Syarif, 2003)

Proses pada pohon keputusan adalah mengubah bentuk data (tabel) menjadi model pohon, mengubah model pohon menjadi rule, dan menyederhanakan rule (Basuki dan Syarif, 2003).

1.3. Algoritma C4.5

Berikut ini algoritma dasar dari C4.5:
Input : sampel training, label training, atribut
Output : pohon keputusan

  1. Membuat simpul akar untuk pohon yang dibuat
  2. Jika semua sampel positif, berhenti dengan suatu pohon dengan satu simpul akar, beri tanda (+)
  3. Jika semua sampel negatif, berhenti dengan suatu pohon dengan satu simpul akar, beri tanda (-)
  4. Jika atribut kosong, berhenti dengan suatu pohon dengan suatu simpul akar, dengan label sesuai nilai yang terbanyak yang ada pada label training
  5. Untuk yang lain, Mulai
    1. A —— atribut yang mengklasifikasikan sampel dengan hasil terbaik (berdasarkan Gain rasio)
    2. Atribut keputusan untuk simpul akar —– A
    3. Untuk setiap nilai, vi, yang mungkin untuk A
      1. Tambahkan cabang di bawah akar yang berhubungan dengan A= vi
      2. Tentukan sampel Svi sebagai subset dari sampel yang mempunyai nilai vi untuk atrribut A
      3. Jika sampel Svi kosong
        1. Di bawah cabang tambahkan simpul daun dengan label = nilai yang terbanyak yang ada pada label training
        2. Yang lain tambah cabang baru di bawah cabang yang sekarang C4.5 (sampel training, label training, atribut-[A])
    4. Berhenti

Mengubah tree yang dihasilkan dalam beberapa rule. Jumlah rule sama dengan jumlah path yang mungkin dapat dibangun dari root sampai leaf node.

Secara umum algoritma C4.5 untuk membangun pohon keputusan adalah sebagai berikut (Craw 2005).

  1. Pilih atribut sebagai akar
  2. Buat cabang untuk masing-masing nilai
  3. Bagi kasus dalam cabang
  4. Ulangi proses untuk masing-masing cabang sampai semua kasus pada cabang memiliki kelas yang sama.

1.3.1 Gain

Konsep Gain

  • Gain (S,A) merupakan perolehan informasi dari atribut A relative terhadap output data S.
  • Perolehan informasi didapat dari output data atau variable dependent S yang dikelompokkan berdasarkan atribut A, dinotasikan dengan gain (S,A).

1.3.2. Entropy


Konsep Entropy :

  • Entropy (S) merupakan jumlah bit yang diperkirakan dibutuhkan untuk dapat mengekstrak suatu kelas (+ atau -) dari sejumlah data acak pada ruang sampel S.
  • Entropy dapat dikatakan sebagai kebutuhan bit untuk menyatakan suatu kelas.
  • Entropy digunakan untuk mengukur ketidakaslian S.

1.3.3. Information Gain

Information gain adalah salah satu attribute selection measure yang digunakan untuk memilih test attribute tiap node pada tree. Atribut dengan informasi gain tertinggi dipilih sebagai test atribut dari suatu node (Sunjana, 2010). Dalam prosesnya perhitungan gain bisa terjadi atau tidak suatu missing value.

1.4. Prinsip Kerja

Pada tahap pembelajaran algoritma C4.5 memiliki 2 prinsip kerja yaitu:

  1. Pembuatan pohon keputusan. Tujuan dari algoritma penginduksi pohon keputusan adalah mengkontruksi struktur data pohon yang dapat digunakan untuk memprediksi kelas dari sebuah kasus atau record baru yang belum memiliki kelas. C4.5 melakukan konstruksi pohon keputusan dengan metode divide and conquer. Pada awalnya hanya dibuat node akar dengan menerapkan algoritma divide and conquer. Algoritma ini memilih pemecahan kasus-kasus yang terbaik dengan menghitung dan membandingkan gain ratio, kemudian node-node yang terbentuk di level berikutnya, algoritma divide and conquer akan diterapkan lagi sampai terbentuk daun-daun.
  2. Pembuatan aturan-aturan (rule set). Aturan-aturan yang terbentuk dari pohon keputusan akan membentuk suatu kondisi dalam bentuk if-then. Aturan-aturan ini didapat dengan cara menelusuri pohon keputusan dari akar sampai daun. Setiap node dan syarat percabangan akan membentuk suatu kondisi atau suatu if, sedangkan untuk nilai-nilai yang terdapat pada daun akan membentuk suatu hasil atau suatu then.

Contoh


Langkah 1

  • Menghitung jumlah kasus, jumlah kasus untuk keputusan Yes, jumlah kasus untuk keputusan No, dan Entropy dari semua kasus dan kasus yang dibagi berdasarkan atribut OUTLOOK, TEMPERATURE, HUMIDITY, dan WINDY.
  • Setelah itu lakukan perhitungan Gain untuk setiap atribut.
  • Hasil perhitungan ditunjukan di bawah ini.

Perhitungan Node 1

Cara Perhitungan Node 1 (1)


Cara Perhitungan Node 1 (2)

Cara Perhitungan Node 1 (3)

Cara Perhitungan Node 1 (3)

  • Dari hasil diketahui bahwa atribut dengan gain tertinggi adalah HUMIDITY yaitu sebesar 0.37. Sehingga HUMIDITY dapat menjadi node akar.
  • Ada dua nilai atibut dari HUMIDITY, yaitu HIGH dan NORMAL.
  • Nilai atribut NORMAL sudah mengklasifikasikan kasus menjadi 1, yaitu keputusannya Yes, sehingga tidak perlu dilakukan perhitungan lebih lanjut.
  • Tetapi untuk nilai HIGH masih perlu dilakukan perhitungan lagi.


Langkah 2

  • Menghitung jumlah kasus, jumlah kasus untuk keputusan Yes, jumlah kasus untuk keputusan No. 
  • Entropy dari semua kasus dan kasus yang dibagi berdasarkan atribut OUTLOOK, TEMPERATURE dan WINDY, yang dapat menjadi node akar dari nilai atribut HIGH.
  • Setelah itu lakukan perhitungan Gain, untuk tiap-tiap atribut.

Perhitungan Node 1.1

Cara Perhitungan Node 1.1 (1)

  • Atribut dengan Gain tertinggi adalah OUTLOOK, yaitu sebesar 0.6995.
  • Sehingga OUTLOOK dapat menjadi node cabang dari nilai atribut HIGH.
  • Ada tiga nilai dari atribut OUTLOOK yaitu CLOUDY, RAINY dan SUNNY.

  – CLOUDY => klasifikasi kasus 1 (Yes)
  – SUNNY   => klasifikasi kasus 1 (No)
  – RAINY     => masih perlu perhitungan lagi.

Cara Perhitungan Node 1.1 (2)

Langkah 3

  • Menghitung jumlah kasus, jumlah kasus untuk keputusan Yes, jumlah kasus untuk keputusan No. 
  • Entropy dari semua kasus dan kasus yang dibagi berdasarkan atribut TEMPERATURE dan WINDY, yang dapat menjadi node cabang dari nilai atribut RAINY.

Setelah itu lakukan perhitungan Gain, untuk tiap-tiap atribut.

Perhitungan Node 1.1.2


Cara Perhitungan Node 1.1.2 (1)

  • Atribut dengan Gain tertinggi adalah WINDY, yaitu sebesar 1.
  • Sehingga WINDY dapat menjadi node cabang dari nilai atribut RAINY.
  • Ada dua nilai dari atribut WINDY, yaitu FALSE dan TRUE.


  – Nilai atribut FALSE sudah mengklasifikasikan kasus menjadi 1 (Yes).
  – Nilai atribut TRUE sudah mengklasifikasikan kasus menjadi 1 (No).
  – Sehingga tidak perlu dilakukan perhitungan lagi.
 
Cara Perhitungan Node 1.1.2 (2)

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s