Algoritma C4.5

Algoritma C.45

 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.

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.

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).

Algoritma C4.5

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

§  Membuat simpul akar untuk pohon yang dibuat

§  Jika semua sampel positif, berhenti dengan suatu pohon dengan satu simpul akar, beri tanda (+)

§  Jika semua sampel negatif, berhenti dengan suatu pohon dengan satu simpul akar, beri tanda (-)

§  Jika atribut kosong, berhenti dengan suatu pohon dengan suatu simpul akar, dengan label sesuai nilai yang terbanyak yang ada pada label training

§  Untuk yang lain, Mulai

§  A ------ atribut yang mengklasifikasikan sampel dengan hasil terbaik (berdasarkan Gain rasio)

§  Atribut keputusan untuk simpul akar ----- A

§  Untuk setiap nilai, vi, yang mungkin untuk A

§ Tambahkan cabang di bawah akar yang berhubungan dengan A= vi

§ Tentukan sampel Svi sebagai subset dari sampel yang mempunyai nilai vi untuk atrribut A

§ Jika sampel Svi kosong

§  Di bawah cabang tambahkan simpul daun dengan label = nilai yang terbanyak yang ada pada label training

§  Yang lain tambah cabang baru di bawah cabang yang sekarang C4.5 (sampel training, label training, atribut-[A])

§  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:

1. Pilih atribut sebagai akar.

2. Buat cabang untuk tiap-tiap nilai.

3. Bagi kasus dalam cabang.

4. Ulangi proses untuk setiap cabang sampai semua kasus pada cabang memiliki kelas yang sama.

Untuk memilih atribut sebagai simpul akar (root node) atau simpul dalam (internal node), didasarkan pada nilai information gain tertinggi dari atribut-atribut yang ada. Sebelum perhitungan information gain, akan dilakukan perhitungan entropy. Entropy merupakan distribusi probabilitas dalam teori informasi dan diadopsi kedalam algoritma C4.5 untuk mengukur tingkat 14

homogenitas distribusi kelas dari sebuah himpunan data (data set). Semakin tinggi tingkat entropy dari sebuah data maka semakin homogen distribusi kelas pada data tersebut. Perhitungan information gain menggunakan rumus 2.2, sedangkan entropy menggunakan rumus 2.3.

𝐺𝑎𝑖𝑛 𝑆,𝐴 = 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 𝑆 − 𝑆𝑖 𝑆 ∗𝐸𝑛𝑡𝑟𝑜𝑝𝑦 (𝑆𝑖𝑛𝑖=1) (2.2)

dimana,

S : Himpunan kasus

A : Atribut

n : Jumlah partisi atribut A

|Si| : Jumlah kasus pada partisi ke i

|S| : Jumlah kasus dalam S

𝐸𝑛𝑡𝑟𝑜𝑝𝑦 𝑆 = − 𝑝𝑖∗𝑙𝑜𝑔2 𝑝𝑖𝑛𝑖=1 (2.3)

dimana,

S : Himpunan kasus

A : Fitur

n : Jumlah partisi S

pi : Proporsi dari Si terhadap S

Selain Information Gain kriteria yang lain untuk memilih atribut sebagai pemecah adalah Rasio Gain. Perhitungan rasio gain menggunakan rumus 2.4, sedangkan split information menggunakan rumus 2.5.

𝐺𝑎𝑖𝑛𝑅𝑎𝑠𝑖𝑜 𝑆,𝐴 = 𝐺𝑎𝑖𝑛 (𝑆,𝐴)𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛(𝑆,𝐴) (2.4)

𝑆𝑝𝑙𝑖𝑡𝐼𝑛𝑓𝑜𝑟𝑚𝑎𝑡𝑖𝑜𝑛 𝑆,𝐴 = − 𝑆𝑖𝑆 𝑙𝑜𝑔2𝑆𝑖𝑆𝑐𝑖=1 (2.5)

dimana S1 sampai Sc adalah c subset yang dihasilkan dari pemecahan S dengan menggunakan atribut A yang mempunyai sebanyak c nilai.

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 membandingkangain 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.