Friday 15 June 2012

Induksi Decision Tree menggunakan konsep Gini Index

Decision Tree adalah salah satu metode klasifikasi yang populer karena mudah diinterprestasikan oleh manusia. 
Decision tree digunakan untuk pengenalan pola dan termasuk dalam pengenalan pola secara statistik.

Sekarang kita coba menyelesaikan Decision Tree menggunakan kosenp Gini Index.




Examples (S), adalah training examples yang ditunjukkan oleh tabel di bawah ini:
Dataset Playing Tennis

Target attribute adalah PlayTennis yang memiliki value yes atau no, selama 14 minggu pada setiap Sabtu pagi. Attribute adalah Outlook, Temperature, Humidity, dan Wind.
Penyelesaian Decision Tree menggunakan konsep Gini Index.
Gini (9+,5-)         = 1-((9/14)2 + (5/14)2)
                           = 1-(0.4 + 0.13)
                           = 0.46

Penentuan Root Decision Tree
Value Windy      = (weak, strong)
S weak                  = (6+,2-)                               Gini(weak) = 1-((6/8)2 + (2/8)2)  = 0.38
S strong                = (3+,3-)                               Gini(strong) = 1-((3/6)2 + (3/6)2)  = 0.5
Gain(S, windy)  = Gini(S) – 8/14 Gini(weak) – 6/14 Gini(strong)
                                = 0.46 - 8/14 0.38 – 6/14 0.5         = 0.03

Value Humidity                 = (high, normal)
S high                    = (3+,4-)                               Gini(high) = 1-((3/7)2 + (4/7)2)    = 0.49
S normal              = (6+,1-)                               Gini(normal) = 1-((6/7)2 + (1/7)2)  = 0.24
Gain(S, humidity)= Gini(S) – 7/14 Gini(high) – 7/14 Gini(normal)
                                = 0.46 - 7/14 0.49 – 7/14 0.24 = 0.095

Value Temperatur= (hot, mid, cool)
S hot                      = (2+,2-)                               Gini(hot) = 1-((2/4)2 + (2/4)2)      = 0.5
S mid                     = (4+,2-)                               Gini(mid) = 1-((4/6)2 + (2/4)2)     = 0.44
S cool                    = (3+,1-)                               Gini(cool) = 1-((3/4)2 + (1/4)2)     = 0.38
Gain(S, temperatur)= Gini(S) – 4/14 Gini(hot) – 6/14 Gini(mid) – 4/14 Gini(cool)
                                = 0.46 - 4/14 0.5 – 6/14 0.44 – 4/14 0.38 = 0.02

Value Outlook= (sunny, overcast, rain)
S sunny               = (2+,3-)                               Gini(sunny) = 1-((2/5)2 + (3/5)2)         = 0.48
S overcast           = (4+,0-)                               Gini(overcast) = 1-((4/4)2 + (0/4)2)     = 0
S rain                  = (3+,2-)                               Gini(rain) = 1-((3/5)2 + (2/5)2)             = 0.48
Gain(S, outlook)= Gini(S) – 5/14 Gini(sunny) – 4/14 Gini(overcast) – 5/14 Gini(rain)
                                = 0.46 - 5/14 0.48 – 4/14 0 – 5/14 0.48 = 0.13

Dari perhitungan di atas didapat:
Gain (S,windy)              = 0.03
Gain (S,humidity)           = 0.095
Gain (S,temperatur)       = 0.02
Gain (S,outlook)           = 0.13

Maka attribute Outlook diambil sebagai Root Decision Tree karena menyediakan prediksi terbesar.
Root Decision Tree

Branch node Outlook = Sunny
S sunny                = (2+,3-)               Gain(sunny) = 0.48
Value Temperatur= (hot, mid, cool)
S hot                      = (0+,2-)                               Gini(hot) = 1-((0/2)2 + (2/2)2)      = 0
S mid                     = (1+,1-)                               Gini(mid) = 1-((1/2)2 + (1/2)2)     = 0.5
S cool                    = (1+,0-)                               Gini(cool) = 1-((1/1)2 + (0/1)2)     = 0
Gain(Sunny, temperatur)= Gini(Sunny) – 2/5 Gini(hot) – 2/5 Gini(mid) – 1/5 Gini(cool)
                                = 0.48 – 2/5 0 – 2/5 0.5 – 1/5 0    = 0.28

Value humidity = (high, normal)
S high                    = (0+,3-)                               Gini(high) = 1-((0/2)2 + (3/3)2)    = 0
S normal              = (2+,0-)                               Gini(normal) = 1-((2/2)2 + (0/2)2) = 0
Gain(Sunny, humidity)= Gini(Sunny) – 3/5 Gini(high) – 2/5 Gini(normal)
                                = 0.48 – 3/5 0 – 2/5 0 = 0.46

Value windy       = (weak, strong)
S weak                  = (1+,2-)                               Gini(weak) = 1-((1/3)2 + (2/3)2)  = 0.44
S strong                = (1+,1-)                               Gini(strong) = 1-((1/2)2 + (1/2)2)  = 0.5
Gain(Sunny, windy)= Gini(Sunny) – 3/5 Gini(weak) – 2/5 Gini(strong)
                                = 0.48 – 3/5 0.44 – 2/5 0.5 = 0.016

Dari Perhitungan diatas didapat:
Gain(Sunny, temperatur) = 0.28
Gain(Sunny, humidity)    = 0.46
Gain(Sunny, windy)        = 0.016

Maka Attribut humidity dipilih sebagai Branch node karena menyediakan prediksi terbesar.


Dengan cara yang sama, Anda dapat menemukan Branch node lainnya.

Semoga bermanfaat,

Endro A

Posted by at

6 comments:

  1. Flashcom Indonesia17 April 2014 at 02:11

    saya pusing liat kaya begian sob :D

    ReplyDelete
  2. Endro Andriyanto17 April 2014 at 03:48

    ha ha ha..... pegangan aja kang. :-) atau minum obat.

    ReplyDelete
  3. yanti21 December 2014 at 20:55

    artikelnya cukup membantu.. tapi sya bingung knp bisa perhitungannya seperti itu.. (bisa mita referensinya)... mungkin krn perhitungannya memakai konsep ini ya
    Gini (9+,5-) = 1-((9/14)2 + (5/14)2)
    = 1-(0.4 + 0.13)
    = 0.46...
    sehingga hasil akhirnya memakai nilai tertinggi.. krn sdh banyak sya bca referensi (buku bahkan paper) semuanya memakai nilai terendah tapi tdk memakai perhitungan ini Gini (9+,5-) = 1-((9/14)2 + (5/14)2).... bedanya adl kalau pakai perhitungan pakai cara di atas, memang hasilnya adl kebalikan dari cara yg saya pakai...
    tapi apapun itu, trims ats pencerahannya.. mungkin ini cara lain utk menghitung gini index

    ReplyDelete
  4. yanti21 December 2014 at 21:30

    saya punya data utk pakai gini index, information gain dan gain ratio,, masalahnya, ketika saya pakai caraku atau cara yg mas endro berikan, ttp saja hasilnya tdk sma dengan hasil rapid miner khusus utk gini index... kalau information gain dan gain ratio hasilnya sama dengan rapid miner.. (hanya utk data ini sja yg beda).... data sebelum2x (file lain) sama antara hitung manual dengan rapid miner...

    ReplyDelete
  5. Unknown5 April 2016 at 22:35

    Membantu banget sob tulisan nya, sama seperti yg guru and ajarkan. (Salam Hamzah Sby)

    ReplyDelete
  6. Unknown6 April 2016 at 06:23

    Membantu banget sob tulisan nya, sama seperti yg guru and ajarkan. (Salam Hamzah Sby)

    ReplyDelete

Subscribe to: Post Comments (Atom)