Contoh Soal Decision Tree Data Mining

Unduh sekarang

Lompat ke Halaman

Cari di dalam dokumen

You're Reading a Free Preview
Page 2 is not shown in this preview.

Buy the Full Version

Puaskan Keingintahuan Anda

Segala yang ingin Anda baca.

Kapan pun. Di mana pun. Perangkat apa pun.

Tanpa Komitmen. Batalkan kapan saja.

Bagikan dokumen Ini

Bagikan atau Tanam Dokumen

Opsi Berbagi

• Bagikan di Facebook, terbuka di jendela baru
• Bagikan di Twitter, terbuka di jendela baru
• Bagikan di LinkedIn, terbuka di jendela baru
• Bagikan dengan Email, membuka klien email
• Salin Tautan

Navigasi cepat

• Beranda

• Buku

• Buku audio

• Dokumen

  , aktif

Decision Tree (Pohon keputusan) adalah alat pendukung keputusan yang menggunakan model keputusan seperti pohon dan kemungkinan konsekuensinya, termasuk hasil acara kebetulan, biaya sumber daya, dan utilitas. Ini adalah salah satu cara untuk menampilkan algoritma yang hanya berisi pernyataan kontrol bersyarat.

Baca Juga: Memahami Konsep Data Mining Beserta Prosesnya

Table of Contents

• Algoritma untuk Induksi Decision Tree
• Ulasan Singkat Entropy
• Ukuran Attribute Selection: Information Gain (ID3)
• Attribute Selection: Information Gain
• Tahapan Algoritma Decision Tree (ID3)
  • Contoh Algoritma Decision Tree (ID3)
    • Siapkan Data Training
    • Pilih Atribut Sebagai Akar
      • Perhitungan Entropy dan Gain Akar
      • Penghitungan Gain Akar
      • Gain Tertinggi Sebagai Akar
    • Buat cabang untuk tiap-tiap nilai
      • Perhitungan Entropi Dan Gain Cabang
      • Gain Tertinggi Sebagai Node 1.1
    • Ulangi proses untuk setiap cabang sampai semua kasus pada cabang memiliki kelas yg sama
      • Gain Tertinggi Sebagai Node 1.1.2
  • Contoh Induksi Decision Tree
    • Gain Ratio untuk seleksi atribut (C4.5)
    • Indeks Gini(CART)
    • Perhitungan Indeks Gini
    • Membandingkan Ukuran Seleksi Atribut
    • Tindakan Pemilihan Atribut Lainnya
  • Overfitting dan Tree Pruning
  • Mengapa induksi pohon keputusan populer?

Algoritma untuk Induksi Decision Tree

Algoritma dasar (algoritma greedy):

1. Pohon dibangun dalam sebuah rekursif top-down bergaya divide-and-conquer
2. Pada awalnya, semua training examples berada di akar (root).
3. Atribut bersifat kategoris (jika dinilai terus-menerus, mereka didiskritkan sebelumnya)
4. Examples dipartisi secara rekursif berdasarkan atribut yang dipilih
5. Atribut uji dipilih berdasarkan pada heuristik atau ukuran statistik (misalnya: Perolehan informasi, rasio gain, indeks gini)

Kondisi untuk menghentikan partisi:

• Semua sampel untuk node yang diberikan milik kelas yang sama
• Tidak ada atribut yang tersisa untuk pemartisian lebih lanjut – voting mayoritas digunakan untuk mengklasifikasikan daun
• Tidak ada sampel yang tersisa

Ulasan Singkat Entropy

Entropy (Teori Informasi)

• Ukuran ketidakpastian terkait dengan variabel acak
• Perhitungan: Untuk variabel acak diskrit y mengambil nilai m berbeda{y1, …, ym},
  • H(Y) = – ∑pilog(pi), dimana pi = P(Y = yi)
• Penafsiran:
  • Semakin Tinggi Entropy => Semakin Tinggi Ketidakpastian
  • Semakin Rendah Entropy => Semakin Rendah Ketidakpastian
• Entropy bersyarat
  • H (Y|X) = ∑xp(x)H(Y|X = x)
    
    
    

Ukuran Attribute Selection: Information Gain (ID3)

• Pilih atribut dengan perolehan informasi tertinggi
• Biarkan pi menjadi probabilitas bahwa tuple arbitrer di D milik kelas Ci,
  diperkirakan oleh | Ci, D | / | D |
• Informasi yang diharapkan (entropi) diperlukan untuk mengklasifikasikan tuple dalam D:
  
  
  
• Informasi yang diperlukan (setelah menggunakan A untuk membagi D menjadi partisi v) untuk mengklasifikasikan D:
  
  
  
• Informasi yang diperoleh dengan bercabang pada atribut A
  Gain(A) = Info(D) – InfoA(D)

Attribute Selection: Information Gain

• Anggap atribut A menjadi atribut Continous-Valued
• Harus menentukan split point terbaik untuk A
  • Urutkan nilai A dalam urutan yang meningkat
  • Biasanya, titik tengah antara setiap pasangan nilai yang berdekatan dianggap sebagai split point yang mungkin
    (ai + ai + 1)/ 2 adalah titik tengah antara nilai ai dan ai + 1
  • Titik dengan persyaratan informasi minimum yang diharapkan untuk A dipilih sebagai split-point untuk A
• Split :
  • D1 adalah himpunan tupel dalam D yang memenuhi titik perpecahan ≤, dan
  • D2 adalah himpunan tupel dalam D yang memenuhi titik pisah A>

Tahapan Algoritma Decision Tree (ID3)

1. Siapkan data training
2. Pilih atribut sebagai akar
   
   
   
3. Buat cabang untuk tiap-tiap nilai
4. Ulangi proses untuk setiap cabang sampai semua kasus pada cabang memiliki kelas yg sama

Contoh Algoritma Decision Tree (ID3)

Siapkan Data Training

Pilih Atribut Sebagai Akar

Untuk memilih atribut akar, didasarkan pada nilai Gain tertinggi dari atribut-atribut yang ada. Untuk mendapatkan nilai Gain, harus ditentukan terlebih dahulu nilai Entropy

Rumus Entropy: S = Himpunan Kasus. n = Jumlah Partisi S. pi = Proporsi dari Si terhadap S.

Rumus Gain: S = Himpunan Kasus. A = Atribut. n = Jumlah Partisi Atribut A. | Si | = Jumlah Kasus pada partisi ke-i. | S | = Jumlah Kasus dalam S

Perhitungan Entropy dan Gain Akar

Entropy Total

Entropy Outlook

Entropy Temperature

Entropy Humidity

Entropy Windy

Dari perhitungan di atas menghasilkan tabel seperti di bawah ini.

Langkah berikunya yakni mencari nilai Gain.

Penghitungan Gain Akar

Gain (Total, Outlook)

Gain (Total, Temperature)

Gain (Total, Humidity)

Gain (Total, Windy)

Dari perhitungan di atas, maka didapatkan nilai masing-masing gain. Kemudian nilai tersebut dimasukkan ke dalam tabel.

Gain Tertinggi Sebagai Akar

Dari hasil pada Node 1, dapat diketahui bahwa atribut dengan Gain tertinggi adalah HUMIDITY yaitu sebesar 0.37051. Dengan demikian HUMIDITY dapat menjadi node akar.

Ada 2 nilai atribut dari HUMIDITY yaitu HIGH dan NORMAL. Dari kedua nilai atribut tersebut, nilai atribut NORMAL sudah mengklasifikasikan kasus menjadi 1 yaitu keputusan-nya Yes, sehingga tidak perlu dilakukan perhitungan lebih lanjut. Tetapi untuk nilai atribut HIGH masih perlu dilakukan perhitungan lagi.

Buat cabang untuk tiap-tiap nilai

Untuk memudahkan, dataset di filter dengan mengambil data yang memiliki kelembaban HUMADITY=HIGH untuk membuat table Node 1.1

Perhitungan Entropi Dan Gain Cabang

Gain Tertinggi Sebagai Node 1.1

Dari hasil pada Tabel Node 1.1, dapat diketahui bahwa atribut dengan Gain tertinggi adalah OUTLOOK yaitu sebesar 0.69951. Dengan demikian OUTLOOK dapat menjadi node kedua

Artibut CLOUDY = YES dan SUNNY= NO sudah mengklasifikasikan kasus menjadi 1 keputusan, sehingga tidak perlu dilakukan perhitungan lebih lanjut. Tetapi untuk nilai atribut RAINY masih perlu dilakukan perhitungan lagi

Ulangi proses untuk setiap cabang sampai semua kasus pada cabang memiliki kelas yg sama

Gain Tertinggi Sebagai Node 1.1.2

Dari tabel, Gain Tertinggi adalah WINDY dan menjadi node cabang dari atribut RAINY. Karena semua kasus sudah masuk dalam kelas

Apa itu decision tree dalam Data Mining?

Pada kasus seperti apa decision tree digunakan?

Bagaimana cara decision tree mengambil keputusan?

Apakah decision tree juga dapat membantu dalam pengambilan keputusan perusahaan?