Download - DocumentBI

Transcript

Nama: I Komang Gusnadi PutraNim: 12101212

TEKNIK KLASIFIKASI DENGAN MENGGUNAKAN ALGORITMA C45

A. Definisi KlasifikasiKlasifikasi adalah sebuah proses untuk menemukan model yang menjelaskan atau membedakan konsep atau kelas data, dengan tujuan untuk dapat memperkirakan kelas dari suatu objek yang kelasnya tidak diketahui (Tan et all, 2004).

Gambar 1. Klasifikasi sebagai suatu tugas memetakan atribut xke dalam label kelas y (Tan et all, 2006)

Model Klasifikasi terdiri dari (Tan et all, 2006):1. Pemodelan DeskriptifDapat bertindak sebagai suatu alat yang bersifat menjelaskan untuk membedakan antara objek dengan klas yang berbeda.2. Pemodelan PrediktifModel klasifikasi juga dapat menggunakan prediksi label kelas yang belum diketahui recordnya.

B. Konsep Pembuatan Model dalam KlasifikasiUntuk meningkatkan akurasi dan efisiensi proses klasifikasi, terdapat beberapa langkah pemrosesan terhadap data, yaitu :1. Data CleaningData cleaning merupakan suatu pemrosesan terhadap data untuk menghilangkan noise dan penanganan terhadap missing value pada suatu record.2. Analisis RelevansiAnalisis relevansi dapat meningkatkan efisiensi klasifikasi karena waktu yang diperlukan untuk pembelajaran lebih sedikit daripada proses pembelajaran terhadap data data dengan atribut yang masih lengkap (masih terdapat redundansi).3. Transformasi DataPada data dapat dilakukan generalisasi menjadi data dengan level yang lebih tinggi. Misalnya dengan melakukan diskretisasi terhadap atribut degan nilai kontinyu.

(a)

(b)Gambar 2. Proses Klasifikasi: (a) Learning: Training data dianalisis dengan algoritma klasifikasi. Disini atribut label kelas adalah Tenured, danLearned Model atau classifier di gambarkan pada blok aturan klasifikasi. (b) Classification: Test data digunakan untuk memperkirakan keakuratan aturan klasifikasi.

Untuk mengevaluasi performansi sebuah model yang dibangun oleh algoritma klasifikasi dapat dilakukan dengan menghitung jumlah dari test record yang di prediksi secara benar (akurasi) atau salah (error rate) oleh model tersebut. Akurasi dan error rate didefinisikan sebagai berikut.

Algoritma klasifikasi berusaha untuk mencari model yang mempunyai akurasi yang tinggi atau error rate yang rendah ketika model diterapkan pada test set.

C. Pohon Keputusan (Decision Tree)Decision tree menggunakan struktur hierarki untuk pembelajaran supervised. Proses dari decision tree dimulai dari root node hingga leaf node yang dilakukan secara rekursif. Di mana setiap percabangan menyatakan suatu kondisi yang harus dipenuhi dan pada setiap ujung pohon menyatakan kelas dari suatu data.Proses dalam pohon keputusan yaitu mengubah bentuk data (tabel) menjadi model pohon (tree) kemudian mengubah model pohon tersebut menjadi aturan (rule). Pohon keputusan terdiri dari himpunan IFTHEN. Setiap path dalam tree dihubungkan dengan sebuah aturan, dimana premis terdiri atas sekumpulan node-node yang ditemui dan kesimpullannya dari aturan atas kelas yang terhubung dengan leaf node dari path.

D. Arsitektur Pohon KeputusanArsitektur pohon keputusan dibuat menyerupai bentuk pohon, dimana pada umumnya sebuah pohon terdapat akar (root), cabang dan daun (leaf). Pada pohon keputusan juga terdiri dari tiga bagian sebagai berikut : a. Root nodeRoot node atau node akar merupakan node yang terletak paling atas dari suatu pohon. b. Internal node Internal Node ini merupakan node percabangan, dimana pada node ini hanya terdapat satu input dan mempunyai minimal dua output.c. Leaf nodeNode ini merupakan node akhir, hanya memiliki satu input, dan tidak memiliki output. Pada pohon keputusan setiap leaf node menandai label kelas.

Gambar berikut merupakan bentuk arsitektur pohon keputusan.

Gambar 3. Arsitektur Pohon KeputusanLambang bulat pada pohon keputusan melambangkan node akar (root node) dan juga node cabang (internal node). Lambang kotak melambangkan node daun (leaf node). Setiap node daun berisi nilai atribut dari node cabang atau node akarnya.E. Algoritma C4.5Algoritma C4.5 adalah algoritma klasifikasi data dengan teknik pohon keputusan yang terkenal dan disukai karena memiliki kelebihan-kelebihan. Algoritma C4.5 mengkonstruksi pohon keputusan dari data pelatihan, yang berupa kasus-kasus atau record (tupel) dalam basisdata.Ada tiga prinsip kerja algoritma C4.5 pada tahap belajar dari data, yaitu sebgai berikut :1. Pembuatan Pohon KeputusanAlgoritma ini memilih pemecahan kasus-kasus yang terbaik dengan menghitung dan membandingkan gain ratio, kemudian pada node-node yang terbentuk di level berikutnya. Demikian seterusnya sampai terbentuk daun- daun.2. Pemangkasan Pohon Keputusan dan Evaluasi (Opsional)Karena pohon yang dikonstruksi dapat berukuran besar dan tidak mudah dibaca, C4.5 dapat menyederhanakan pohon dengan melakukan pemangkasan berdasarkan nilai tingkat kepercayaan (confidence level). Pembuatan Aturan3. Aturan dari Pohon Keputusan (Opsional)Aturan-aturan dalam bentuk if-then diturunkan dari pohon keputusan dengan melakukan penelusuran dari akar sampai ke daun. Setiap node dan syarat pencabangannya akan diberikan di if, sedangkan nilai pada daun akan menjadi ditulis di then. Setelah semua aturan dibuat, maka aturan akan disederhanakan (digabung atau diperumum).

F. Langkah-Langkah Konstruksi Pohon Keputusan dengan Algoritma C4.5Adapun langkah-langkah dalam konstruksi pohon keputusan adalah sebagai berikut :Langkah 1: Pohon dimulai dengan sebuah simpul yang mereperesentasikan sampel data pelatihan yaitu dengan membuat simpul akar.Langkah 2 : Jika semua sampel berada dalam kelas yang sama, maka simpul ini menjadi daun dan dilabeli menjadi kelas. Jika tidak, gain ratio akan digunakan untuk memilih atribut split, yaitu atribut yang terbaik dalam memisahkan data sampel menjadi kelas-kelas individu.Langkah 3 : Cabang akan dibuat untuk setiap nilai pada atribut dan data sampel akan dipartisi lagi.Langkah 4 : Algoritma ini menggunakan proses rekursif untuk membentuk pohon keputusan pada setiap data partisi. Jika sebuah atribut sduah digunakan disebuah simpul, maka atribut ini tidak akan digunakan lagi di simpul anak-anaknya.Langkah 5 :Proses ini berhenti jika dicapai kondisi seperti berikut : Semua sampel pada simpul berada di dalam satu kelas Tidak ada atribut lainnya yang dapat digunakan untuk mempartisi sampel lebih lanjut. Dalam hal ini akan diterapkan suara terbanyak. Ini berarti mengubah sebuah simpul menjadi daun dan melabelinya dnegan kelas pada suara terbanyakG. EntropyEntropi merupakan pengukuran ketidakpastian rata-rata kumpulan data ketika kita tidak tahu hasil dari sumber informasi. Bentuk perhitungan untuk entropi adalah sebagai berikut :

dimana, X : Himpunan Kasusk : jumlah partisi Xpj : Proporsi Xj terhadap X

Entropi split yang membagi X dengan n record menjadi himpunan-himpunan X1 dengan n1 baris dan X2 dengan n2 baris adalah :

Besar nilai Entropy(X) menunjukkan bahwa X adalah atribut yang lebih acak. Di sisi lain, atribut yang lebih kecil dari nilai Entropy(X) menyiratkan atribut ini sedikit lebih acak yang signifikan untuk data mining. Nilai entropi mencapai nilai minimum 0, ketika semua pj lain = 0 atau berada pada kelas yang sama. Nilainya mencapai maksimum log2 k, ketika semua nilai pj adalah sama dengan 1/k. H. Gain RatioPada kontruksi pohon C4.5, di setiap simpul pohon, atribut dengan nilai gain ratio tertinggi dipilih sebagai atribut split untuk simpul. Rumus dari gain ratio adalah sebagai berikut :

Dimana gain(a) adalah information gain dari atribut a untuk himpunan sampel X dan split info(a) menyatakan entropi atau informasi potensial yang didapat pada pembagian X menjadi n sub himpunan berdasarkan telaahan pada atribut a. Sedangkan gain(a) didefinisikan sebagai berikut :

Untuk rumus split info(a) adalah sebagai berikut :

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

Dengan kata lain rumus untuk menghitung nilai gain ratio untuk dipilih sebagai atribut dari simpul yang ada sebagai berikut ini :