Algoritma C4.5

Daftar Isi “Algoritma C4.5“

1. Pengertian Algoritma C4.5
2. Perbedaan ID3 & C4.5
3. Entropy, Information Gain & Gain Ratio
4. Latihan Soal

1. Pengertian Algoritma C.45

Algoritma data mining C4.5 merupakan salah satu algoritma yang digunakan untuk melakukan klasifikasi atau segmentasi atau pengelompokan dan bersifat prediktif. Klasifikasi merupakan salah satu proses pada data mining yang bertujuan untuk menemukan pola yang berharga dari data yang berukuran relatif besar hingga sangat besar. Algortima C4.5 sendiri merupakan pengembangan dari algortima ID3.

2. Perbedaan ID3 dengan C4.5

Algoritma C4.5 mempunyai prinsip dasar kerja yang sama dengan algoritma ID3. Beberapa perbedaannya antara lain :

a. Mampu Menangani Atribut dengan Tipe Diskrit atau Kontinu

Pemilihan atribut pada algoritma induksi decision tree menggunakan ukuran berdasarkan entropy yang dikenal dengan information gain sebagai sebuah heuristic untuk memilih atribut yang merupakan bagian terbaik dari contoh ke dalam kelas. Semua atribut adalah bersifat kategori yang bernilai diskrit. Atribut dengan nilai continuous harus didiskritkan.

atribut kontinu

Diskritisasi atribut bertujuan untuk mempermudah pengelompokan nilai berdasarkan kriteria yang telah ditetapkan. Hal ini juga bertujuan untuk menyederhanakan permasalahan dan meningkatkan akurasi dalam proses pembelajaran.

Terdapat beberapa teknik yang bisa dilakukan, diantaranya ‘binning’, yang mendefinisikan kumpulan kelas nominal untuk setiap atribut, kemudian menetapkan setiap nilai atribut ke dalam salah satu kelas. Misalnya, jika domain atribut numerik mempunyai nilai dari 0 sampai dengan 100, domain tersebut dapat dibagi menjadi empat bin (0..24, 25..49, 50..74, 75..100). Setiap nilai atribut akan dikonversi menjadi atribut nominal yang berkorespondensi dengan salah satu bin. Oleh karena itu metode binning disebut  unsupervised discretization method.

Teknik berikutnya dapat dilakukan dengan pengukuran entropi, dengan mempertimbangkan semua kemungkinan pembagian dan cari pemotongan terbaik.

split kontinu

Langkah pertama adalah urutkan nilai atribut kontinu beserta nilai kelas utama nya. Kemudian lakukan pemotongan dengan pertimbangan pembagian jumlah kelas utama 50:50 atau mendekati,  untuk memerkirakan mendapat nilai entropi tertinggi atau mendekati 1. Contoh:

temperature < 71.5: yes/4, no/2
temperature ≥ 71.5: yes/5, no/3

Info([4,2],[5,3]) = 6/14 info([4,2]) + 8/14 info([5,3]) = 0.939

Teknik lain, normalisasi, juga dapat dilakukan dengan cara mencari nilai rata dan standart deviasi pada rentang atribut kontinu.

standart deviasi

b. Mampu Menangani Atribut yang Kosong (Missing Value)

Nilai kosong pada sebuah dataset wajib kita isi terlebih dahulu sebelum diproses untuk tahap machine learning atau bentuk kedalam sebuah model decision tree.

missing value c4.5-1

Cara paling mudah dalam pengisian atribut kosong adalah dengan memberikan nilai berdasar nilai yang paling banyak atau dominan dalam atribut tersebut. Contoh, atribut Shape baris ketiga dan keempat kita beri nilai 4 dikarenakan pada kelompok class 1 mayoritas atribut Shape memiliki angka 4. Sedangkan pada class 0, baris 7 kita berikan nilai 1.

missing-value-c4.5-2

c. Pemangkasan Pohon Keputusan

Pada saat pembangunan pohon keputusan, banyaknya cabang mungkin mencerminkan adanya noise atau outlier pada training data. Pemangkasan pohon dapat dilakukan untuk mengenali dan menghapus cabang-cabang tersebut. Pohon yang dipangkas akan menjadi lebih kecil dan lebih mudah dipahami. Pohon semacam itu biasanya juga menjadi lebih cepat dan lebih baik dalam melakukan klasifikasi.

overfitting vs underfitting

Jika suatu fungsi atau dataset memiliki terlalu banyak atribut (fitur), model pelatihan yang terbentuk akan menghasilkan akurasi yang baik, namun akan sangat mungkin mengalami kegagalan untuk memprediksi data masukan baru seperti pada contoh diatas.

Pemangkasan pohon juga dapat digunakan untuk mengatasi overfitting. Overfitting terjadi karena ada noise data training, yaitu data yang tidak relevan sehingga mengakibatkan pohon memiliki subtree yang panjang dan tidak seimbang. Misal internal node memiliki kelas YA = 5 dan TIDAK = 1. Data yang berada pada kelas TIDAK merupakan noise, sehingga apabila data tersebut diolah akan menghasilkan pohon dengan subtree yang panjang. Overfitting juga dapat terjadi karena data training yang sedikit.

overfitting

Ada dua metode dalam melakukan pemangkasan dalam pohon keputusan, yaitu:
a. Prepruning, yaitu menghentikan pembangunan suatu subtree lebih awal, yaitu dengan memutuskan untuk tidak lebih jauh mempartisi data training. Pada pendekatan prepruning, sebuah pohon dipangkas dengan cara menghentikan pembangunannya jika partisi yang akan dibuat dianggap tidak signifikan. Untuk mengetahui nilai parameter apakah akan dilakukan expanding atau pruning dapat menggunakan metode chi-squared.

b. Postpruning, yaitu menyederhanakan pohon dengan cara membuang beberapa cabang subtree setelah pohon selesai dibangun. Metode postpruning ini merupakan metode standard untuk algoritma C4.5.

Reduced Error Pruning merupakan salah satu algoritma postpruning. Algoritma ini membagi data menjadi dua, yaitu training data dan test data. Training data adalah data yang digunakan untuk membentuk pohon keputusan, sedangkan test data digunakan untuk menghitung nilai error rate pada pohon setelah dipangkas.

Cara kerja REP adalah dengan memangkas internal node yang dimulai dari internal node paling bawah ke atas. Pemangkasan dilakukan dengan cara mengganti atribut dengan leaf node yang memiliki kelas yang dominan muncul. Setelah itu test data diproses menggunakan rule hasil pemangkasan, kemudian dihitung nilai error ratenya. Test data juga diproses dengan rule awal, yaitu rule yang terbentuk sebelum pohon dipangkas, kemudian dihitung nilai error ratenya. Apabila nilai error rate yang dihasilkan dari pemangkasan pohon lebih kecil, maka pemangkasan dilakukan.

reduced error pruning

Dimana:
r = nilai perbandingan error rate
n = total sample
z = Φ^-1(c)

post pruning tree

Pada contoh diatas dapat diketahui bahwa atribut “Health Plan Contribution” banyak memiliki class Bad, maka dari itu dipangkas menjadi leaf node Bad untuk keseluruhan atribut tersebut, dan seterusnya.

d. Pemilihan Atribut yang Dilakukan Menggunakan Gain Ratio
Quinlan memperkenalkan metode C4.5, dimana untuk pemilihan split atribut menggunakan metode Gain Ratio (GR) menggantikan Information Gain (IG).

Information gain pada ID3 lebih mengutamakan pengujian yang menghasilkan banyak keluaran. Dengan kata lain, atribut yang memiliki banyak nilailah yang dipilih sebagai splitting atribut. Sebagai contoh, pembagian terhadap 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.

Partisi semacam ini tentu saja bersifat pure, sehingga informasi yang dibutuhkan untuk mengklasifikasi D berdasarkan partisi seperti ini adalah sebesar Infoproduct_ID(D) = 0. Sebagai akibatnya, information gain yang dimiliki atribut product_ID menjadi maksimal. Padahal, jelas sekali terlihat bahwa partisi semacam ini tidaklah berguna. Karena itu algoritma C4.5 yang merupakan suksesor dari ID3 menggunakan gain ratio untuk memperbaiki information gain, dengan rumus gain ratio (Larose, 2009).

split-id-code

3. Entropy, Information Gain & Gain Ratio

Pemilihan atribut yang baik adalah atribut yang memungkinkan untuk mendapatkan decision tree yang paling kecil ukurannya. Atau atribut yang bisa memisahkan obyek menurut kelasnya. Secara heuristik atribut yang dipilih adalah atribut yang menghasilkan simpul yang paling ”purest” (paling bersih). Ukuran purity dinyatakan dengan tingkat impurity, dan untuk menghitungnya, dapat dilakukan dengan menggunakan konsep Entropy, Entropy menyatakan impurity suatu kumpulan objek.

Formula mencari entropi sebagai berikut :

formula entropi

Keterangan :
• S adalah himpunan (dataset) kasus
• k adalah banyaknya partisi S
• p_j adalah probabilitas yang di dapat dari Sum(Ya) dibagi Total Kasus.

Information gain adalah kriteria yang paling populer untuk pemilihan atribut. Algoritma C4.5 adalah pengembangan dari algoritma ID3. Oleh karena pengembangan tersebut algoritma C4.5 mempunyai prinsip dasar kerja yang sama dengan algoritma ID3. Hanya saja dalam algoritma C4.5 pemilihan atribut dilakukan dengan menggunakan Gain Ratio dengan rumus :

gain ratio

Dimana:
a = atribut.
gain(a) = information gain pada atribut a
Split(a) = split information pada atribut a

Atribut dengan nilai Gain Ratio tertinggi dipilih sebagai atribut test untuk simpul. Dengan gain adalah information gain. Pendekatan ini menerapkan normalisasi pada information gain dengan menggunakan apa yang disebut sebagai split information. SplitInfo menyatakan entropy atau informasi potensial dengan rumus :

split-info

Dimana:
S = ruang (data) sample yang digunakan untuk training.
A = atribut.
S_i = jumlah sample untuk atribut i

dimana Xi menyatakan sub himpunan ke-i pada sampel X.

information gain

Dimana:
S = ruang (data) sample yang digunakan untuk training.
A = atribut.
|S_i| = jumlah sample untuk nilai V.
|S| = jumlah seluruh sample data.
Entropi(S_i) = entropy untuk sample-sample yang memiliki nilai i

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.

4. Latihan Soal

Berikut hasil perhitungan dengan menghitung gain ratio.

contoh perhitungan gain ratio

Untuk mendapatkan contoh perhitungan di excel dapat download disini.

Semoga artikel berjudul “Algoritma C4.5” bisa bermanfaat dan silahkan jika masih ada yang kurang jelas dapat ditanyakan di kolom komentar dibawah ini.

Silahkan Like Fanspage dan Share artikel ini jika menurut kamu bermanfaat untuk kamu dan orang lain.

Artikel Lainnya