Algoritma Classification dalam Data Mining: Decision Tree

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

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)
      Interpretasi Entropy

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:
    Expected information (entropy) needed to classify a tuple in D
  • Informasi yang diperlukan (setelah menggunakan A untuk membagi D menjadi partisi v) untuk mengklasifikasikan 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
    Entropy dan Gain
  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

Data Training
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

Entropy dan Gain
Entropy dan Gain

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 Total

Entropy Outlook
Entropy Outlook

Entropy Temperature
Entropy Temperature

Entropy Humidity
Entropy Humidity

Entropy Windy
Entropy Windy

Dari perhitungan di atas menghasilkan tabel seperti di bawah ini.

Perhitungan Entropy dan Gain Akar
Perhitungan Entropy dan Gain Akar

Langkah berikunya yakni mencari nilai Gain.

Penghitungan Gain Akar

Gain (Total, Outlook)
Gain Total-Outlook

Gain (Total, Temperature)
Gain Total-Temperature

Gain (Total, Humidity)
Gain Total-Humidity

Gain (Total, Windy)
Gain Total-Windy

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

Perhitungan Gain Akar
Perhitungan Gain Akar
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.

Gain Humidity
Node 1

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

OUTLOOKTEMPERATUREHUMIDITYWINDYPLAY
SUNNYHOTHIGHFALSENO
SUNNYHOTHIGHTRUENO
CLOUDYHOTHIGHFALSEYES
RAINYMILDHIGHFALSEYES
SUNNYMILDHIGHFALSENO
CLOUDYMILDHIGHTRUEYES
RAINYMILDHIGHTRUENO
Perhitungan Entropi Dan Gain Cabang
Perhitungan Entropi Dan Gain Cabang
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

Gain Outlook
Node 1.1

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

OUTLOOKTEMPERATUREHUMDITYWINDYPLAY
RAINYMILDHIGHFALSEYES
RAINYMILDHIGHTRUENO
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

Gain-Windy
Node 1.1.2

Contoh Induksi Decision Tree

Training data set: Buys_computer

Training data set: Buys_computer

Gain Ratio untuk seleksi atribut (C4.5)

  • Ukuran perolehan informasi bias terhadap atribut dengan sejumlah besar nilai
  • C4.5 (penerus ID3) menggunakan rasio keuntungan untuk mengatasi masalah (normalisasi terhadap perolehan informasi)
    c4.5 normalization to information gain
    GainRatio(A) = Gain(A)/SplitInfo(A)
  • Contoh Contoh c4.5 normalization to information gain
    gain_ratio(income) = 0.029/1.557 = 0.019
  • Atribut dengan rasio perolehan maksimum dipilih sebagai atribut pemisahan

Indeks Gini(CART)

  • Jika data set D berisi contoh-contoh dari n kelas, indeks gini, gini(D) didefinisikan sebagai
    Gini-data set D contains examples from n classes
  • Jika data set D dibagi menjadi A menjadi dua himpunan bagian D1 dan D2, indeks gini gini(D) didefinisikan sebagai
    Gini_data set D is split on A into two subsets D1 and D2
  • Pengurangan Data kotor:
    Reduction in Impurity
  • Atribut memberikan ginisplit(D) terkecil (atau pengurangan terbesar dalam data kotor) dipilih untuk memisahkan simpul (perlu menyebutkan semua titik pemisahan yang mungkin untuk setiap atribut)

Perhitungan Indeks Gini

  • Contoh: D memiliki 9 tuple di buys_computer = “yes” dan 5 di “no”
    contoh Indeks Gini
  • Misalkan partisi pendapatan atribut D menjadi 10 di D1: {low, medium} dan 4 di D2
    Partisi Indeks Gini
    Gini {low, high} adalah 0,458; Gini {medium, high} adalah 0,450. Jadi, bagi pada {low, medium} (dan {high}) karena memiliki indeks Gini terendah
  • Semua atribut dianggap continous-valued.
  • Mungkin perlu alat lain, misaslnya: Clustering, untuk mendapatkan nilai pemisahan yang mungkin.
  • Dapat dimodifikasi untuk atribut kategori

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”
Pruning case
Contoh Pruning
Contoh Pruning
Contoh Pruning-2

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

Tinggalkan komentar

error: Content is protected !!