Contoh kasus perhitungan Decision Tree ID3

We’ve updated our privacy policy so that we are compliant with changing global privacy regulations and to provide you with insight into the limited ways in which we use your data.

You can read the details below. By accepting, you agree to the updated privacy policy.

Thank you!

View updated privacy policy

We've encountered a problem, please try again.

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

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

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

Jadi, pohon keputusan pada Gambar merupakan pohon keputusan terakhir yang terbentuk

Contoh Induksi Decision Tree

Training data set: Buys_computer

Gain Ratio untuk seleksi atribut (C4.5)

Indeks Gini(CART)

Perhitungan Indeks Gini

Membandingkan Ukuran Seleksi Atribut

Tiga ukuran, secara umum, memberikan hasil yang baik tetapi

• Information Gain:
  • bias terhadap atribut multinilai
• Gain Ratio:
  • cenderung lebih suka perpecahan yang tidak seimbang di mana satu partisi jauh lebih kecil daripada yang lain
• indeks gini:
  • bias terhadap atribut multinilai
  • mengalami kesulitan ketika # kelas besar
  • cenderung mendukung pengujian yang menghasilkan partisi berukuran sama dan kemurnian di kedua partisi tersebut

Tindakan Pemilihan Atribut Lainnya

• CHAID: algoritma pohon keputusan populer, mengukur berdasarkan uji χ2 untuk independensi
• C-SEP: berkinerja lebih baik daripada info. gain dan indeks gini dalam kasus-kasus tertentu
• G-statistik: memiliki perkiraan dekat dengan distribusi χ2
• Prinsip MDL (Minimal Description Length) (yaitu Solusi paling sederhana lebih disukai):
  • Pohon terbaik sebagai pohon yang membutuhkan bit # paling sedikit untuk kedua (1) menyandikan pohon, dan (2) menyandikan pengecualian ke pohon
• Split multivarian (partisi berdasarkan beberapa kombinasi variabel)
  • CART: menemukan pemisahan multivarian berdasarkan sisir linier. attrs.
• Ukuran pemilihan atribut mana yang terbaik?
  • Sebagian besar memberikan hasil yang baik, tidak ada yang secara signifikan lebih unggul daripada yang lain

Overfitting dan Tree Pruning

• Overfitting: Pohon yang diinduksi dapat menyesuaikan data pelatihan
  • Terlalu banyak cabang, beberapa mungkin mencerminkan anomali karena kebisingan atau pencilan
  • Akurasi yang buruk untuk sampel yang tidak terlihat
• Dua pendekatan untuk menghindari overfitting
  1. Prepruning: Hentikan konstruksi pohon lebih awal ̵ jangan membelah sebuah simpul jika ini akan menghasilkan ukuran kebaikan yang jatuh di bawah ambang batas. Sulit untuk memilih ambang yang sesuai
  2. Postpruning: Buang cabang dari pohon “dewasa” – dapatkan urutan pohon yang dipangkas secara progresif. Menggunakan serangkaian data yang berbeda dari data pelatihan untuk memutuskan mana yang merupakan “pohon pemangkasan terbaik”

Mengapa induksi pohon keputusan populer?

• Kecepatan belajar yang relatif lebih cepat (daripada metode klasifikasi lainnya)
• Konversi ke aturan klasifikasi sederhana dan mudah dipahami
• Dapat menggunakan query SQL untuk mengakses database
• Ketepatan klasifikasi yang sebanding dengan metode lain

Baca Juga:
Algoritma Clustering dalam Data Mining: Metode Partisi
Metode Clustering: hierarki, Density-Based dan Grid-Based