Resume Algoritma ID3

Ini tugas mata kuliah Kecerdasan Buatan, disuruh buat resume tentang Algoritma ID3.


Algoritma Iterative Dichotomous Three


PENGERTIAN
ID3 singkatan dari Iterative Dichotomiser Three. Ada juga yang menyebut Induction of Decision Tree. ID3 adalah suatu algooritma matematika yang digunakan untuk menghasilkan suatu pohon keputusan yang mampu mengklasifikasi suatu obyek. ID3 diperkenalkan pertama kali oleh Ross Quinlan (1979). ID3 merepresentasi konsep-konsep dalam bentuk pohon keputusan. Aturan-aturan yang dihasilkan oleh ID3 mempunyai relasiyang hirarkis seperti suatu pohon (mempunyai akar, titik, cabang, dan daun). Beberapa peneliti menyebut struktur model yang dihasilkan ID3 sebagai pohon keputusan (decision tree) sementara peneliti yang lain menyebutnya pohon aturan (rule tree).

ALGORITMA
Algoritma pada metode ini berbasis pada Occam’s razor: lebih memilih pohon keputusan yang lebih kecil (teori sederhana) dibanding yang lebih besar. Tetapi tidak dapat selalu menghasilkan pohon keputusan yang paling kecil dan karena itu occam’s razor bersifat heuristik. Occam’s razor diformalisasi menggunakan konsep dari entropi informasi. Berikut algoritma dari ID3:



Adapun sample data yang digunakan oleh ID3 memiliki beberapa syarat, yaitu:
1. Deskripsi atribut-nilai. Atribut yang sama harus mendeskripsikan tiap contoh dan memiliki jumlah nilai yang sudah ditentukan.
2. Kelas yang sudah didefinisikan sebelumnya. Suatu atribut contoh harus sudah didefinisikan, karena mereka tidak dipelajari oleh ID3.
3. Kelas-kelas yang diskrit. Kelas harus digambarkan dengan jelas. Kelas yang kontinu dipecah-pecah menjadi kategori-kategori yang relatif, misalnya saja metal dikategorikan menjadi “hard, quite hard, flexible, soft, quite soft”.
4. Jumlah contoh (example) yang cukup. Karena pembangkitan induktif digunakan, maka dibutuhkan test case yang cukup untuk membedakan pola yang valid dari peluang suatu kejadian.

Pemillihan atribut pada ID3 dilakukan dengan properti statistik, yang disebut dengan information gain. Gain mengukur seberapa baik suatu atribut memisahkan training example ke dalam kelas target. Atribut dengan informasi tertinggi akan dipilih. Dengan tujuan untuk mendefinisikan gain, pertama-tama digunakanlah ide dari teori informasi yang disebut entropi. Entropi mengukur jumlah dari informasi yang ada pada atribut.
Rumus menghitung entropi informasi adalah:
 
Rumus untuk menghitung gain adalah:

KEUNTUNGAN DAN KERUGIAN
Keuntungan :
• Dapat membuat aturan prediksi yang mudah dimengerti.
• Membangun pohon keputusan dengan cepat.
• Membangun pohon keputusan yang pendek.
• Hanya membutuhkan beberapa tes atribut hingga semua data diklasifikasikan.

Kerugian :
• Jika contoh yang diteliti terlalu kecil/sederhana mungkin membuat data over-classified.
• Hanya satu atribut yang dapat dites dalam satu waktu untuk membuat keputusan.
• Mengelompokkan data yang berkelanjutan mungkin terhitung mahal, sebanyak pohon yang harus dibuat untuk melihat dimana.


Nb: Ini saya copas hasil googling cuma lupa gak ngesave sumbernya dari mana aja :( Bagi yang memang memerlukan resume ID3 silahkan copas saja. Enjoy :)

Nisaa.

0 comments:

Post a Comment


up