Algoritma ID3

Algoritma ID3

Algoritma ID3

Algoritma ID3

Algoritma ID3 (Iterative Dichotomiser 3) pertama kali diperkenalkan oleh Quinlan (Quinlan, 1986) yang digunakan untuk menginduksi decision tree. Algoritma ID3 dapat bekerja dengan baik pada semua fitur yang mempunyai tipe data kategorikal (nominal atau ordinal). Dalam perkembangannya, ID3 banyak mengalami perbaikan pada versi berikutnya seperti C4.5 atau C5.0.

Induksi decision tree ID3
1. Dimulai dari node akar
2. Untuk semua fitur, hitung nilai entropy untuk semua sampel (data latih) pada node.
3. Pilih fitur dengan informasi gain yang maksimal
4. Gunakan fitur tersebut sebagai node pemecahan menjadi cabang.
5. Lakukan secara rekursif pada setiap cabang yang dibuat dengan mengulangi langkah 2 sampai 4 hingga semua data dalam setiap node hanya memberikan satu label kelas. Node yang tidak dapat dipecah lagi merupakan daun yang berisi keputusan (label kelas).

Entropy dapat dihitung menggunakan persamaan berikut:

p(ω_i | s) adalah proporsi kelas ke-i dalam semua data latih yang diproses di node s. p(ω_i | s) didapatkan dari jumlah semua baris data dengan label kalas i dibagi jumlah baris semua dat. Sementara m adalah jumlah nilai berbeda dalam data.
Entropy digunakan untuk menentukan yang manakah node yang akan menjadi pemecah data latih berikutnya. Nilai entropy yang lebih tinggi akan meningkatkan potensi klasifikasi. Yang perlu diperhatikan adalah jika entropy untuk node bernilai 0 berarti semua data vektor berada pada label kelas yang sama dan node tersebut menjadi daun yang berisi keputusan (label kelas). Yang juga perlu diperhatikan dalam perhitungan entropy adalah jika salah satu dari elemen ω_i sama jumlahnya maka dipastikan entropy bernilai 1.
Gain digunakan untuk memperkirakan pemilihan fitur yang tepat untuk menjadi pemecah pada node tersebut. Gain sebuah fitur ke-j dihitung menggunakan persamaan berikut:

p(v_i | s) adalah proporsi nilai v muncul pada kelas dalam node, E(s_i) adalah entropy komposisi nilai v dari kelas ke-j dalam data ke-i node tersebut. n adalah jumlah nilai berbeda dalam node.


sumber : buku data mining

Kata kunci : algoritma ID3,data mining, contoh skripsi teknik informatika, skripsi teknik informatika, skripsi, contoh skripsi teknik informatika