Decision Trees

16 07 2008

Decision Trees sering disebut juga dengan nama Regression Trees atau Pohon Keputusan.

Decision Trees adalah suatu metode data mining yang bersifat supervised classification dimana setiap record di dalam suatu dataset yang akan dimodel harus mempunyai class/category. Misalnya dataset yang tersedia untuk pemodelan Decision Trees terdiri dari:

Jumlah Anggota Rumah Tangga, Jenis Lantai, Jenis Jamban, Luas Lantai, Miskin/Tidak Miskin

Empat variabel pertama disebut dengan predictor dan satu variabel terakhir adalah class atau category.

Decision trees secara khusus melakukan pemodelan dengan berusaha memodel record yang tersedia ke dalam bentuk pohon keputusan. Dimana dalam suatu pohon keputusan akan ada interior node yang dilabeli dengan suatu variabel. Dari setiap interior node akan keluar tanda panah yang dilabeli dengan nilai dari variabel yang ada pada interior node tersebut. Di bagian akhir pohon keputusan akan terdapat leaf yang dilabeli dengan class atau category. Dalam penggunaannya, atau dalam pengimplementasian model decision trees ini ke dalam suatu sistem (umumnya sistem pendukung keputusan), model pohon keputusan yang didapat perlu diekstrak ke dalam bentuk rule-rule yang berbentuk if – then.

Secara teori, ada dua hal yang perlu diperhatikan dalam melakukan pemodelan decision trees:
1. Bagaimana memilih variabel yang akan diletakkan pada suatu interior node? Variabel mana yang akan dipilih terlebih dahulu?
2. Bagaimana cara memodel agar model decision trees yang didapatkan cukup efektif? Dalam artian occam razor, dimana model yang didapat tidak terlalu fit (overfit), tetapi semua keputusan masih dapat diambil dengan tingkat kesalahan yang kecil.

Untuk menjawab kedua pertanyaan tersebut, ada beberapa metode yang bisa diaplikasikan. Untuk pertanyaan pertama, apakah suatu variabel bisa lebih dulu dipilih dari yang lainnya, dapat dihitung menggunakan Information Gain. Information Gain digunakan untuk menentukan berapa banyak informasi yang bisa diberikan oleh variabel tersebut terhadap category yang ada. Variabel yang memiliki nilai information gain tertinggi, akan dipilih sebagai variabel yang digunakan pada interior node yang sedang dikaji. Secara teori, information gain dirumuskan sebagai berikut:

G(E,f) = H(E) – H(E|f)

dimana:
G(E,f) adalah jumlah informasi baru yang diberikan oleh variabel f
H(E) adalah entropy dari suatu event E
H(E|f) adalah expected entropy dari suatu event E, bila kita mengetahui nilai dari variabel f

Dalam hal ini, entropy dari suatu event E dapat dihitung menggunakan rumus berikut ini:

H(E) = SUM (c in C) P(c) log2 P(c)

dimana:
P(c) adalah probabilitas dari event di dalam E yang mempunyai category c.

Tetapi dengan menggunakan Information Gain saja, variabel yang dipilih umumnya variabel yang mempunyai lebih banyak nilai. Perbandingannya dapat dilihat seperti berikut ini:

– Information gain maksimum untuk variabel yang mempunyai dua nilai (binary) adalah 2, sedangkan information gain maksimum untuk variabel yang mempunyai variabel dengan 1024 nilai adalah 10.

Untuk memecahkan permasalah ini dapat digunakan Information Gain Ratio untuk menghilangkan bias tersebut dengan melakukan normalisasi terhadap nilai semua Information Gain. Information Gain Ratio dapat dihitung dengan rumus sebagai berikut:

IGR(E,f) = G(E,f) / (- SUM (v in V) P(v) log2 P(v)

dimana:
P(v) adalah nilai probabilitas dari jumlah nilai suatu variabel terhadap keseluruhan nilai variabel yang ada.

Masalah yang kedua yang ingin dipecahkan agar model yang didapatkan benar-benar efektif adalah masalah overfitting. Dalam hal ini, memang model decision trees yang benar-benar sesuai dengan record dari dataset yang tersedia, akan lebih konsisten, tetapi model seperti ini sering terlalu overfit dan kurang bisa mengeneralisasikan permasalahan. Hal yang lain yang juga terkait dengan permasalahan ini dengan masalah trade-off antara konsistensi dan compactness.

Salah satu cara yang bisa digunakan untuk memecahkan permasalahan ini adalah Pruning (Pemangkasan). Bagaimana melakukannya? Pruning bisa dilakukan dengan memanfaatkan test data untuk menguji model yang didapat dari training data. Yang artinya dataset yang ada harus dibagi terlebih dahulu menjadi dua: training dan test data. Training data digunakan untuk membuat model, dan test data digunakan untuk menentukan apakah suatu leaf perlu dipangkas atau tidak. Caranya adalah dengan menguji test data dengan leaf tersebut dan tanpa leaf tersebut. Kalau model tanpa leaf memodel lebih bagus, berarti leaf tersebut bisa dipruning.


Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: