Pada tulisan sebelumnya telah dibahas tentang Decision Tree, dengan contoh algoritma ID3. Sekarang akan dibahas tentang algoritma CART. Klo ID3 menggunakan perhitungan Information Gain untuk menentukan atribut yang dipilih, di CART digunakan Gini index.
Contohnya misalnya kita masih menggunakan dataset berikut tentang cuaca yang cocok untuk main tenis:
Gini index adalah metrix yang digunakan untuk klasifikasi di CART. Gini menyumpan kuadrat probabilitas dari setuap kelas. Rumusnya :
Outlook
Untuk Outlook ada 3 nilai yaitu sunny, overcast dan rain
Dari tabel kita bisa lihat untuk sunny ada 5 yang terdiri dari 2 yes dan 3 no
Sementara untuk overcast ada 4 yang terdiri dari 4 yes dan 0 no
Rain ada 5 yang terdiri dari 3 yes dan 2 no.
total outlook ada 14
Perhitungan Gini indexnya:
Gini(outlook=sunny)= 1-(2/5)^2-(3/5)^2=1-0,16-0,36=0,48
Gini(outlook=Overcast)=1-(4/4)^2=0
Gini(outlook=rain)=1-(3/5)^2-(2/5)^2=1-0,36-0,16=0,48
Jumlah Gini untuk outlook:
Gini(outlook)=(5/14)*0,48+(4/14)*0+(5/14)*0,48=0,171+0+0,171=0,342
Temperatur:
Temperatur memiliki 3 nilai: Cool Hot dan Mild
Hot: ada 4 dengan 2 yes dan 2 no
Cool: ada 4 dengan 3 yes dan 1 no
Mild: ada 6 dengan 4 yes dan 2 no
Gini(temp=hot)=1-(2/4)^2-(2/4)^2=0,5
Gini(temp=Cool)=1-(3/4)^2-(1/4)^2=1-0,5625-0,0625=0,375
Gini(temp=mild)=1-(4/6)^2-(2/6)^2=1-0,444-0,111=0,445
Gini(temp)=(4/14)*0,5+(4/14)*0,375+(6/14)*0,445=0,142+0,107+0,190=0,439
Humidity:
Humidity hanya memiliki 2 nilai High dan normal
Dari tabel didapat high ada 7 dengan 3 yes dan 4 no
normal ada 7 dengan 6 yes dan 1 no:
Gini(Humidity=high)=1-(3/7)^2-(4/7)^2=1-0,183-0,326=0,489
Gini(humidity=normal)=1-(6/7)^2-(1/7)^2=1-0,734-0,002=0,244
Gini(humidity)=(7/14)*0,489+(7/14)*0,244=0,367
Wind:
Wind hanya ada 2 nilai: weak & strong
Weak ada 8: dengan 6 yes dan 2 no
strong ada 6 dengan 3 yes dan 3 no
Gini(wind=weak)=1-(6/8)^2-(2/8)^2=1-0,5625-0,062=0,375
Gini(wind=strong)=1-(3/6)^2-(3/6)^2=1-0,25-0,25=0,5
Gini(wind)=(8/14)*0,375+(6/14)*0,5=0,428
Root
dari perhitungan kita mendapatkan gini outlook=0,342; temperatur=0,439; humidity=0,367 dan wind=0,428 ; berbeda dengan ID3 yang memilih Gain terbesar, disini kita pilih Gini terkecil yaitu outlook.
sehingga diperoleh rootnya adalah:
outlook
–sunny
–overcast–yes
–rain
Dari tabel terlihat untuk overcast hanya menghasilkan yes, sehingga tidak perlu kita hitung lagi cabangnya
langkah selanjutnya adalah menentukan cabang dari sunny
sunny
tabel untuk sunny adalah sebagai berikut:
Selanjutnya kita hitung nilai gini untuk temperatur dari tabel diatas:
sunny-temperatur
temperatur ada 7 dengan 3 nilai Hot, mild dan cool
Hot ada 2 dengan 0 yes dan 2 no
Cool ada 1 dengan 1 yes dan 0 no
mild ada 2 dengan 1 yes dan 1 no
Gini(outlook=sunny dan temp=hot)=1-(0/2)^2-(2/2)^2=0
Gini(outlook=sunny & temp=cool)=1-(1/1)^2-(0/1)^2=0
Gini(outlook=sunny & temp=mild)=1-(1/2)^2-(1/2)^2=1-0,25-0,25=0,5
Gini(outlook=sunny & temp)=(2/5)*0+(1/5)*0+(2/5)*0,5=0,2
sunny dan humidity
Humidity ada 2 nilai yaitu high dan normal dengan 5 instance
High ada 3 dengan 0 yes dan 3 no
normal ada 2 dengan 2 yes dan 0 no
Gini(outlook=sunny,humidity=high)=1-(0/3)^2-(3/3)^2=0
Gini(outlook=sunny,humidity=normal)=1-(2/2)^2-(0/2)^2=0
Gini(outlook=sunny,humidity)=3/5*0+2/5*0=0
sunny dan wind
ada 5 instance dengan 2 nilai yaitu weak dan strong
weak ada 3 dengan 1 yes dan 2 no
strong ada 2 dengan 1 yes dan 1 no
gini(outlook=sunnny,wind=weak)=1-(1/3)^2-(2/3)^2=0,266
gini(outlook=sunny,wind=strong)=1-(1/2)^2-(1/2)^2=0,2
gini(outlook=sunny,wind)=3/5*0,266+2/5*0,2=0,466
Cabang sunny
Dari perhitinugan didapat gini temperatur=0,2; humidity=0; dan wind=0,466. Nilai terkecil adalah humidity. Dari tabel humidity terdapat dua cabang yaitu high dan normal. Dari nilai high diperoleh klasifikasi yang semuanya bernilai no sedangkan normal selalu yes
Sehingga kita dapatkan
outlook
–sunny
—-humidity
——-high=no
——-normal=yes
–overcast–yes
–rain
Sekarang tinggal menghitung cabang dari rain:
Rain
Rain memiliki tabel berikut:
Selanjutnya kita hitung gini untuk temperatur:
rain – temperatur
hanya ada 2 nilai temperatur yaitu mild dan cool, dengan total ada 5 instance
cool ada 2 dengan 1 yes dan 1 no
mild ada 3 dengan 2 yes dan 1 no
Gini(outlook=rain,temp=cool)=1-(1/2)^2-(1/2)^2=0,5
gini(outlook=rain,temp=mild)=1-(2/3)^2-(1.2)^2=0,44
gini(outlook=rain,temp)=(2/5)*0,5+3/5*0,44=0,466
rain-humidity
dari tabel terlihat ada 5 instance humidity dengan nilai high dan normal
high ada 2 dengan 1 yes dan 1 no
normal ada 3 dengan 2 yes dan 1 no
Gini(outlook=rain, humidity=high)=1-(1/2)^2-(1/2)^2=0,5
gini(outlook=rain, humidit=normal)=1-(2/3)^2-(1/3)^2=0,44
gini(outlook=rain,humidity)=2/5*0,5+3/5*0,44=0,466
Rain-wind
ada 5 instance dengan nilai weak dan strong
weak ada 3 dengan 3 yes dan 0 no
strong ada 2 dengan 0 yes dan 2 no
gini(outlook=rain,wind=weak)=1-(3/3)^2-(0/3)^2=0
gini(outlook=rain,wind=strong)=1-(0/2)^2-(2/2)^2=0
gini(outlook=rain,wind)=3/5*0+2/5*0=0
cabang rain
dari hasil perhitungan gini temperatur=0,466; humidity=0,466; wind=0
sehingga gini yang terkecil adalah wind
wind memiliki 2 nilai yaitu weak dan strong
dari tabel terlihat weak hanya memiliki nilai yes dan string hanya menghasilkan nilai no
dengan demikian perhitungan ini telah selesai dan menghasilkan decision tree yang sama dengan id3 yaitu:
Semoga bermanfaat!
referensi:
https://sefiks.com/2018/08/27/a-step-by-step-cart-decision-tree-example/