Decision Tree menggunakan WEKA

Sudah pernah mendengar nama WEKA ? WEKA adalah sebuah aplikasi yang sangat membantu dalah hal melakukan analisa pada klasifikasi atau klusterisasi data. Info detil dan cara mendapatkannya bisa langsung ke situs resminya di http://www.cs.waikato.ac.nz/ml/weka/

Aplikasi WEKA ini ditulis menggunakan bahasa Java. Jadi jika kita ingin melakukan perubahan di dalamnya dapat kita lakukan langsung dengan mengubah source codenya dan mengkompilasi ulang.

Information, Entropy dan Information Gain

Konsep sederhana dari informasi

Secara sederhana kita bisa saja menganggap bahwa informasi adalah ukuran dari ketidakpastian atau ukuran dari kejutan. Semakin besar kita takjub, terkejut atau kagum akan sebuah berita di TV, maka semakin besar informasi tersebut. Sebagai contoh jika ada sebuah koran yang menuliskan tentang terbitnya matahari di pagi hari, tentunya sudah bisa dipastikan tidak ada orang yang berminat membacanya. Karena hal tersebut memang seperti itu kejadiannya bahwa matahari akan sealu terbit di pagi hari. Keesokan hari pun akan selalu seperti itu, sehingga informasi menjadi tidak penting. Sebaliknya, berita tentang kematian penyanyi Michael Jackson mengejutkan banyak masyarakat sehingga menjadi informasi yang sangat penting pada saat itu.

Entropy

Secara umum enthropy adalah ukuran dari sebuah ketidakpastian dengan variabel yang random (acak). Dalam hal stored instances, maka entropy adalah ukuran ketidakpastian dari attribut.

dimana p(xi) adalah propabilitas mass function dari outcome xi

Information Gain

Information gain adalah pengurangan yang diharapkan dalam enthropy. Dalam machine learning, ini dapat digunakan untuk menentukan urutan atribut atau mempersempit atribut yang dipilih. Urutan inilah yang akan membentuk pohon keputusan (decession tree). Biasanya attribut dengan gain informasi terbesar yang dipilih.

CONTOH

Tabel di bawah ini menunjukkan 14 instance yang tersimpan dalam database dengan 6 atribut (day, outlook, temperature, humidity, wind, playTennis). Setiap instance menggambarkan kondisi dari sebuah hari dan aksi dari orang yang akan bermain tenis (played atau not played tennis).

instance dengan 6 attribut

Untuk root element, atribut dengan entrophy terbesar yang dipilih. Untuk contoh di atas ini maka yang dipilih adalah outlook karena mempunyai parameter ketidakpastian terbesar. Setelah memilih root, maka selanjutnya dihitung setiap pasangan kombinasi yang mungkin terjadi. 

Entropy(S) adalah entropy of classificator dari PlayTennis - ada 14 instance dalam dataset yang mana ada 9x (9+) keputusan untuk play tennis dan 5x not to play (5-).

Contoh kalkulasi untuk classificator Wind :

Ada 8 instance dengan value : Weak. Jika Wind bernilai Weak maka ada 6x keputusan untuk Play dan 3x keputusan untuk not Play. [6+, 2-]. Jika strong wind (6 instances), keputusan to play 3x dan not to play 3x juga. Maka information gain attribute wind adalah 0.48.

Information gain dari semua attibut adalah :

Gain(S, Outlook) = 0.246
Gain(S, Humidity) = 0.151
Gain(S, Wind) = 0.048
Gain(S, Temperature) = 0.029

WEKA The .arff file

Format file untuk menyimpan records dalam Weka adalah arff. Contoh di atas jika dituliskan dalam arff menjadi :

@relation PlayTennis  

@attribute day numeric
@attribute outlook {Sunny, Overcast, Rain} 
@attribute temperature {Hot, Mild, Cool} 
@attribute humidity {High, Normal}
@attribute wind {Weak, Strong} 
@attribute playTennis {Yes, No}  

@data  
1,Sunny,Hot,High,Weak,No,? 
2,Sunny,Hot,High,Strong,No,?
3,Overcast,Hot,High,Weak,Yes,? 
4,Rain,Mild,High,Weak,Yes,? 
5,Rain,Cool,Normal,Weak,Yes,? 
6,Rain,Cool,Normal,Strong,No,?
7,Overcast,Cool,Normal,Strong,Yes,?
8,Sunny,Mild,High,Weak,No,?
9,Sunny,Cool,Normal,Weak,Yes,?
10,Rain,Mild,Normal,Weak,Yes,? 
11,Sunny,Mild,Normal,Strong,Yes,? 
12,Overcast,Mild,High,Strong,Yes,? 
13,Overcast,Hot,Normal,Weak,Yes,? 
14,Rain,Mild,High,Strong,No,?

File ini akan di import menggunakan WEKA explorer. Nanti setelah di import akan terlihat seperti gambar di bawah ini :

Setelah berhasil mengimport arff ini maka kita sudah bisa memilih menu classifier. Jika ingin menggunakan algorithm c4.5 maka pilih j48 (Tree). Setelah itu klik tombol start running sehingga menghasilkan seperti di bawah ini :

Setelah selesai di proses menggunakan j48

Pohon keputusannya bisa dilihat dengan melakukan klik kanan di hasilnya dan menekan Visualize Tree.

Tree

Terlihat bahwa atibut Outlook mempunyai information gain tertinggi sesuai dengan perhitungan manualnya.

Cek http://www.slideshare.net/putusundika/c45-sample-case untuk penjelasan lebih detil tentang cara menghitung secara manual.



Referensi
Data Mining and KnowledgeDiscovery; Prof. Dr. Nada Lavrac
Data Mining: Practical Machine Learning Tools and Techniques, Second Edition; Ian H. Witten, Eibe Frank