Tag Archives: algorithm

Data Mining – Decision Tree

Decision Tree atau Pohon Keputusan merupakan salah satu cara Data Mining dalam memprediksi masa depan dengan membangun klasifikasi atau regresi model dalam bentuk struktur pohon. Hal tersebut dilakukan dengan cara memecah terus ke dalam himpunan bagian yang lebih kecil lalu pada saat itu juga sebuah pohon keputusan secara bertahap dikembangkan. Hasil akhir dari proses tersebut adalah pohon dengan node keputusan dan node daun. Sebuah node keputusan (misalnya, Cuaca/ Outlook) memiliki dua atau lebih cabang (misalnya, Panas, Berawan dan Hujan). Node daun (misalnya, Bermain) merupakan klasifikasi atau keputusan. Node keputusan paling atas di pohon yang sesuai dengan prediktor terbaik disebut simpul akar. pohon keputusan dapat menangani data deskriptif maupun numerik.

decision_tree_1

Algoritma
Algoritma inti untuk membangun pohon keputusan disebut ID3 oleh J. R. Quinlan dengan cara kerja top-down pada pencarian greedy melalui ruang cabang tanpa teknik backtracking. ID3 menggunakan Entropi dan Information Gain untuk membangun pohon keputusan.

Entropi
Sebuah pohon keputusan dibangun secara top-down dari simpul akar dan melibatkan partisi data ke dalam himpunan bagian yang berisi contoh dengan nilai yang sama (homogen). Algoritma ID3 menggunakan entropi untuk menghitung homogenitas sampel. Jika sampel sudah benar-benar homogen, entropi bernilai nol dan jika pembagian sampel dibagi rata maka entropi bernilai satu.

entropy

Untuk membangun pohon keputusan, kita perlu menghitung dua jenis entropi menggunakan tabel frekuensi sebagai berikut:
a) Entropi yang menggunakan tabel frekuensi satu atribut:

entropy_3

b) Entropi yang menggunakan tabel frekuensi dua atribut:

entropy_2

Information Gain
Information gain didasarkan pada penurunan entropi setelah dataset dibagi oleh atribut. Membangun pohon keputusan adalah seluruh hal tentang penemuan atribut yang mengembalikan information gain tertinggi (yaitu, cabang yang paling homogen).
Langkah 1: Hitung entropi dari target.

entropy_targetLangkah 2: dataset tersebut kemudian dibagi pada atribut yang berbeda. Entropi untuk setiap cabang dihitung. Kemudian ditambahkan secara proporsional, untuk mendapatkan jumlah entropi untuk perpecahan. entropi yang dihasilkan dikurangi dari entropi sebelum perpecahan. Hasilnya adalah Information Gain, atau penurunan entropi.

entropy_attributes

entropy_gainLangkah 3: Pilih atribut dengan Information Gain terbesar sebagai simpul keputusan, membagi dataset oleh cabang-cabangnya dan ulangi proses yang sama pada setiap cabang.

entropy_attribute_best

decision_tree_slices
Langkah 4a: Sebuah cabang dengan entropi 0 adalah simpul daun.

entropy_overcast
Langkah 4b: Sebuah cabang dengan entropi lebih dari 0 akan dipecah kembali.

entropy_sunny
Langkah 5: Algoritma ID3 dijalankan secara rekursif pada cabang-cabang non-daun, sampai semua data terklasifikasikan.

Pohon Keputusan Untuk Aturan keputusan
Sebuah pohon keputusan dapat dengan mudah diubah untuk satu set aturan oleh pemetaan dari simpul akar ke simpul daun satu per satu.

decision_rules

Isu pada Pohon Keputusan
– Bekerja dengan atribut berkelanjutan (binning)
– Menghindari overfitting (terlalu bagus)
– Super Atribut (atribut dengan banyak nilai)
– Bekerja dengan nilai-nilai yang hilang

Sumber : Data Mining

QBASIC, Sebuah Interpreter BASIC dari Microsoft

QBASIC (Microsoft Quick Beginners All purpose Symbolic Instruction Code) adalah IDE dan interpreter bagi varian dari bahasa pemrograman BASIC yang didasarkan pada QuickBasic. Kode yang dimasukkan ke IDE dikompilasi ke bentuk peralihan (intermediate), dan bentuk peralihan ini segera ditafsirkan pada permintaan dalam IDE. Hal ini dapat berjalan di bawah hampir semua versi DOS dan Windows, atau melalui DosBox / DOSEMU, pada Linux dan FreeBSD. Pada masanya, QBASIC menyediakan state-of-the-art IDE, termasuk debugger dengan fitur seperti evaluasi ekspresi on-the-fly dan modifikasi kode. Continue reading QBASIC, Sebuah Interpreter BASIC dari Microsoft

BASIC

BASIC, adalah singkatan dari Beginners’ All-purpose Symbolic Instruction Code adalah sebuah kelompok bahasa pemrograman tingkat tinggi. Secara harfiah, BASIC memiliki arti “kode instruksi simbolis semua tujuan yang dapat digunakan oleh para pemula”. Memang, istilah “Bahasa BASIC” di sini juga bisa diartikan menjadi bahasa untuk pemula, atau dengan kata lain, disebut sebagai bahasa dasar, tapi hal tersebut dirasa kurang tepat, mengingat BASIC dapat juga digunakan oleh para pemrogram ahli. Continue reading BASIC