Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

PENERAPAN TEKNIK DATA MINING DECISION TREE MENGGUNAKAN ALGORITMA CART UNTUK MEMPREDIKSI PENYAKIT JANTUNG

No description
by

Fikhri Abduhan

on 7 February 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of PENERAPAN TEKNIK DATA MINING DECISION TREE MENGGUNAKAN ALGORITMA CART UNTUK MEMPREDIKSI PENYAKIT JANTUNG

PENERAPAN TEKNIK DATA MINING DECISION TREE
MENGGUNAKAN ALGORITMA CART
UNTUK MEMPREDIKSI PENYAKIT JANTUNG Abduhan Fikhri
140110080065 BAB II
TINJAUAN PUSTAKA Penyakit kardiovaskular adalah kelas penyakit yang melibatkan jantung atau pembuluh darah (arteri, kapiler, dan pembuluh darah) (Maton dan Anthea, 1993).
Sebagian besar serangan jantung disebabkan oleh gumpalan darah yang menyumbat di salah satu arteri koroner, pembuluh darah yang membawa darah dan oksigen ke otot jantung. Ketika darah tidak dapat mencapai bagian jantung, daerah tersebut akan kekurangan oksigen. Jika sumbatan berlangsung cukup lama, sel-sel di daerah tersebut akan mati (http://www.news-medical.net, 2012). BAB I
PENDAHULUAN Latar Belakang 1 3 Batasan Masalah 2 Maksud dan Tujuan 4 Kegunaan Penelitian 5 Metodologi Penelitian 6 Sistematika Penulisan 7 Sebagian besar rumah sakit saat ini memiliki data atau riwayat medis pasien berupa angka, grafik, teks, dan gambar. Mereka menggunakan beberapa jenis sistem informasi untuk menghasilkan data tersebut. Sayangnya, data yang telah dihasilkan tersebut jarang sekali digunakan untuk mendukung pengambilan keputusan klinis (Palaniapan dan Awang, 2008). Bagaimana prinsip kerja algoritma Classification and Regression Tree (CART) dalam melakukan prediksi penyakit jantung
Bagaimana implementasi algoritma CART dalam memprediksi penyakit jantung berdasarkan variabel-variabel yang telah ditentukan
Bagaimana akurasi yang dihasilkan dari algoritma CART dalam memprediksi penyakit jantung Identifikasi Masalah Metode yang digunakan adalah algoritma CART

Data yang digunakan adalah data yang diperoleh dari Dr. Detrano, VA Medical Center, Long Beach, CA melalui situs web http://www1.ics.uci.edu/pub/machine-learning-databases/heart-disease/cleve.mod
variabel prediksi penyakit jantung : jenis kelamin, umur, chest pain type, blood pressure, kolesterol, fasting blood sugar < 120, resting electrographic, maximum heart rate, angina, slope, peak, number colored vessels, thal

Software yang digunakan dalam penelitian ini adalah Waikato Environment for Knowledge Analysis (WEKA) version 3.6.8. BAB I : PENDAHULUAN
Latar belakang masalah, identifikasi masalah, batasan masalah, maksud dan tujuan penelitian, kegunaan penelitian, metodologi penelitian, dan sistematika penulisan

BAB II : TINJAUAN PUSTAKA
Data mining, decision tree, algoritma CART, dan penyakit jantung

BAB III : METODOLOGI PENELITIAN
Membahas data dan perangkat lunak yang akan digunakan dalam penelitian serta penjelasan mengenai perhitungan manual dari algoritma CART

BAB IV : PEMBAHASAN DAN HASIL PENELITIAN
Berisi implementasi sistem, pembahasan dan hasil yang diperoleh dari penelitian

BAB V : KESIMPULAN DAN SARAN
Berisi kesimpulan dari hasil prediksi penyakit jantung menggunakan algoritma CART dan saran-saran untuk penelitian selanjutnya Mengumpulkan berbagai literatur yang berkaitan dengan masalah yang akan dibahas.
Mengumpulkan data penelitian.
Menganalisis dan mengolah data yang telah didapatkan.
Melakukan uji validasi untuk mengetahui tingkat keakuratan dari algoritma CART.
Menuliskan hasil dari penelitian dalam bentuk skripsi. Memberikan pengetahuan tentang cara kerja algoritma CART
Memberikan pengetahuan tentang akurasi yang dihasilkan oleh sistem dengan menggunakan algoritma CART dalam melakukan prediksi penyakit jantung
Memberikan informasi pendukung kepada praktisi kesehatan tentang ada atau tidaknya penyakit jantung pada pasien sebelum dilakukan tahap uji klinis lebih lanjut
Sebagai infomasi tambahan bagi peneliti lain dalam melakukan penelitian lanjutan terhadap permasalahan yang ada Maksud : Menerapkan algoritma CART dalam memprediksi penyakit jantung terhadap sekumpulan data yang diberikan. Setelah itu hasil yang didapat dari penerapan algoritma ini akan disajikan dalam prosentase tingkat keakuratan.


Tujuan terbagi dalam 2 hal, yaitu :

Melakukan proses data mining untuk klasifikasi penyakit jantung dengan menggunakan algoritma CART.
Menghitung keakuratan algoritma CART untuk data mining dalam memprediksi penyakit jantung. 2.1 Penyakit Jantung 2.1.1 Faktor Risiko Beberapa faktor risiko, Kelly (2010) menyebutkan diantaranya :

usia
jenis kelamin
konsumsi alkohol berlebihan
riwayat keluarga
faktor psikososial
polusi udara 2.2 Data Mining

Data mining adalah proses menemukan pola-pola di dalam data, dimana proses penemuan tersebut dilakukan secara otomatis atau semi otomatis dan pola-pola yang ditemukan harus bermanfaat (J. Han dan M. Kamber, 2001).
”Data mining mencakup penggunaan alat analisis data yang canggih untuk menemukan yang sebelumnya tidak diketahui, yaitu pola dan hubungan yang valid dalam kumpulan data besar” (Two Crows Corporation, 1999; Addison Wesley, 1996). 2.2.1 Tahapan Proses Data Mining 2.2.2 Tugas Data Mining 1.Descriptive MiningDescriptive mining merupakan proses untuk menemukan karakteristik penting dari data dalam suatu basis data. Teknik data mining yang termasuk pada descriptive mining yaitu, clustering, association, dan sequential mining.
2.Predictive MiningPredictive mining merupakan proses untuk menemukan pola dari data dengan menggunakan beberapa variabel lain di masa depan. Teknik data mining yang termasuk pada predictive mining yaitu classification. 2.2.3 Teknik Data Mining 1. Klasifikasi dan Prediksi
Statistika : Bayesian, Hidden Markov Model, serta regresi linier dan nonlinier
Kecerdasan buatan : neural network, decision tree, roughs set, algoritma genetika, K-nearest neighbour, case base reasoning dan logika fuzzy
Machine learning : SOMs (Self Organizing feature maps).
2. Association Rule, teknik ini dapat digunakan untuk menemukan suatu hubungan yang terdapat pada nilai atribut dari sekumpulan data.
apriori.
3. Clustering, teknik ini berbeda dengan klasifikasi dan prediksi. Pada teknik ini nama dari masing-masing kelas tidak ditentukan dari awal proses.
Partitioning method
Hierarchical method
Density based method
Grid based method
Model based clustering method 2.3 Decision Tree Decision tree adalah salah satu metode klasifikasi yang populer karena mudah untuk diinterpretasi oleh manusia. Konsep dasar metode decision tree adalah mengubah data menjadi pohon keputusan dan aturan-aturan keputusan.

Pada umumnya, beberapa ciri kasus yang cocok untuk diterapkan pada decision tree, yaitu (Santosa, 2007) :
Data dinyatakan dengan pasangan atribut dan nilainya
Label/output data biasanya bernilai diskrit
Data mempunyai missing value 2.3.1 Tipe Decision Tree Classification Tree
Memberikan label dan memasukkan record-record ke dalam class-class yang telah tersedia.

Regression Tree
Membuat estimasi nilai dari sebuah variabel target yang berdasar pada nilai numerik. 2.3.2 Tipe Simpul pada Tree Decision tree merupakan flow-chart seperti struktur tree (pohon), dimana tiap internal node menunjukkan sebuah test pada sebuah atribut, tiap cabang menunjukkan hasil dari test, dan leaf node menunjukkan class-class.

P.N. Tan, M. Steinbach, dan V. Kumar (2006) menyebutkan 3 simpul pada tree, yaitu :
Simpul akar (root node) merupakan titik awal dari suatu tree, yaitu tidak memiliki edge yang masuk dan nol atau lebih banyak edge yang keluar.
Simpul internal (internal node) berhubungan dengan suatu pertanyaan atau pengujian, yaitu memiliki satu edge yang masuk dan dua atau lebih edge yang keluar.
Simpul akhir (leaf node) memuat suatu keputusan akhir dari suatu tree, yaitu memiliki satu edge yang masuk dan tidak memiliki edge yang keluar. 2.3.3 Pembentukan Decision Tree Pembentukan decision tree terdiri atas tiga tahap, yaitu :
1.Pembentukan Pohon
Pada pembentukan pohon dilakukan pemilihan atribut untuk penentuan posisi dalam pembentukan pohon, yaitu menggunakan perhitungan information gain. Sebelumnya data yang akan diproses menjadi decision tree harus digeneralisasi terlebih dahulu.

2.Pemangkasan Pohon
Pemangkasan pohon (tree pruning) merupakan pengidentifikasian dan pembuangan cabang yang tidak diperlukan pada pohon yang telah dibentuk. Terdapat dua metode dalam pemangkasan pohon, yaitu :
Prepruning, yaitu pemangkasan yang dilakukan dari awal pembentukan pohon.
Post-pruning, pemangkasan yang dilakukan saat pohon telah terbentuk secara utuh.

3.Pembentukan Decision Tree
Aturan yang dihasilkan dari decision tree dapat ditampilkan dalam bentuk aturan IF-THEN. Setiap node yang bukan leaf node berperan sebagai IF, sedangkan THEN diambil dari leaf node yang merupakan konsekuen dari aturan. 2.3.4 Kelebihan dan Kekurangan Decision Tree 1. Kelebihan dari metode decision tree adalah :
Daerah pengambilan keputusan yang sebelumnya kompleks dan sangat global, dapat diubah menjadi lebih simple dan spesifik
Eliminasi perhitungan-perhitungan yang tidak diperlukan
Fleksibel untuk memilih fitur dari internal node yang berbeda, fitur yang terpilih akan membedakan suatu kriteria dibandingkan kriteria yang lain dalam node yang sama
Dalam analisis multivariat, dengan kriteria dan kelas yang jumlahnya sangat banyak, seorang penguji biasanya perlu untuk mengestimasikan baik itu distribusi dimensi tinggi ataupun parameter tertentu dari distribusi kelas tersebut. Metode decision tree dapat menghindari munculnya permasalahan ini dengan menggunakan kriteria yang jumlahnya lebih sedikit pada setiap internal node tanpa banyak mengurangi kualitas keputusan yang dihasilkan

2. Adapun kekurangannya diantaranya :
Terjadi overlap terutama ketika kelas-kelas dan kriteria yang digunakan jumlahnya sangat banyak
Pengakumulasian jumlah error dari setiap tingkat dalam sebuah decision tree yang besar
Kesulitan dalam mendesain decision tree yang optimal
Hasil kualitas keputusan yang didapatkan dari metode decision tree sangat tergantung pada bagaimana pohon tersebut didesain 2.4 Algoritma CART Metode klasifikasi CART (Classification And Regression Trees) merupakan metode nonparametrik yang berguna untuk mendapatkan suatu kelompok data yang akurat sebagai penciri dari suatu pengklasifikasian.
Algoritma CART pertama kali digagas pada tahun 1984 oleh Leo Breiman, Jerome Friedman, Richard Olshen, Charles Stone (Larose, 2005).

Pada algoritma CART mencakup 3 bagian, yaitu :
Mengkonstruksi pohon optimal
Memilih ketepatan ukuran pohon
Mengklasifikasikan data baru menggunakan pohon yang telah dikonstruksi 2.4.1 Mengkonstruksi Pohon Optimal
Pohon klasifikasi dibangun sesuai dengan aturan pembelahan (splitting rule), yaitu aturan yang membelah data latih hingga bagian yang tidak dapat dibelah lagi. Algoritma pembelahan (splitting) untuk pohon klasifikasi berbeda dengan pohon regresi. Pembagian data kedalam 2 bagian harus berdasarkan homogenitas maksimum.


Dimana x_j merupakan variabel j dan x_j^R merupakan nilai pembelahan terbaik terhadap variabel x_j.
Persamaan diatas menunjukkan bahwa CART akan mencari semua kemungkinan nilai dari semua variabel dalam matriks X untuk pertanyaan pembelahan terbaik x_j< x_j^R yang akan memaksimalkan perubahan ukuran impurity ∆i(t).

Dalam konstruksi pohon,berikut algoritma CART yang dipakai :
Susunlah calon cabang dari atribut data
Menghitung nilai keseluruhan calon cabang menggunakan persamaan kesesuaian (goodness)
Menentukan cabang yang benar-benar dijadikan cabang berdasarkan nilai kesesuaian (goodness) yang terbesar
Ulangi proses hingga didapat kelas yang sama
Gambarkan percabangan 2.4.1.1 Kesesuaian (Goodness)
Percabangan pada algoritma CART akan diukur melalui ukuran yang disebut kesesuaian (goodness). Kesesuaian dari calon cabang s pada pohon keputusan t dilambangkan dengan Φ(s|t). Berikut persamaannya : Dimana :
Φ(st)= calon cabang s pada pohon keputusan tt_L= calon cabang kiri dari pohon keputusan tt_R= calon cabang kanan dari pohon keputusan tP_L = (jumlah catatan pada calon cabang kiri t_L)/(jumlah catatan pada data latihan) P_R= (jumlah catatan pada calon cabang kanan t_R)/(jumlah catatan pada data latihan)P(j|t_L )= (jumlah catatan berkategori j pada calon cabang kiri t_L)/(jumlah catatan pada pohon keputusan t)P(j|t_R )= (jumlah catatan berkategori j pada calon cabang kanan t_R)/(jumlah catatan pada pohon keputusan t) 2.5 Memilih Ketepatan Ukuran Pohon
Optimasi pohon berarti memilih ukuran yang tepat untuk pohon, yaitu dengan cara memotong node yang tidak signifikan dan bahkan subtrees sekalipun. Dua algoritma pemangkasan yang dapat digunakan pada tahap ini adalah optimasi banyaknya poin pada setiap node dan cross-validation. Pada penelitian ini menggunakan algoritma cross-validation. 2.5.1 Cross-Validation
Metode cross-validation digunakan untuk menghindari overlapping pada data testing. Disebut juga dengan k-fold cross-validation. k-fold cross-validation akan mengulang pengujian sebanyak k kali dan hasil pengukuran adalah nilai rata-rata dari k kali pengujian (Wahono, 2012).
Tahapan cross-validation:
Bagi data menjadi k subset yg berukuran sama
Gunakan setiap subset untuk data testing dan sisanya untuk data training 2.6 Mengklasifikasikan Data Baru
Ketika pohon regresi atau klasifikasi telah selesai dikonstruksi, dapat digunakan untuk proses klasifikasi terhadap data baru. Output dari tahap ini adalah nilai kelas atau respon yang diberikan ke masing-masing pengamatan baru. Dengan serangkaian pertanyaan di pohon, masing-masing pengamatan baru akan sampai ke salah satu node terminal pohon.
Full transcript