

Decision Tree¶

Decisioin tree adalah alat pendukung keputusan yang menggunakan model keputusan seperti pohon. Decisioin tree (pohon keputusan) biasanya digunakan dalam riset operasi, khususnya dalam analisis keputusan, untuk membantu mengidentifikasi strategi yang paling memungkinkan untuk mencapai tujuan, dan juga merupakan alat yang populer dalam pembelajaran mesin.

Dalam ilmu komputer, pembelajaran Decision tree sebagai model prediktif untuk melakukan pengamatan tentang item (diwakili di cabang-cabang) ke kesimpulan tentang nilai target item (diwakili dalam daun). Decision tree ini adalah salah satu pendekatan pemodelan prediktif yang digunakan dalam statistik, penambangan data, dan pembelajaran mesin. Dalam struktur decision tree, daun mewakili label kelas dan cabang mewakili konjungsi fitur yang mengarah ke label kelas tersebut. Decision tree ini di mana variabel target dapat mengambil nilai kontinu yang disebut pohon regresi.

Entropy¶

Entropi adalah nilai informasi yang menyatakan ukuran ketidakpastian(impurity) dari attribut dari suatu kumpulan obyek data dalam satuan bit. $$ Entropy(S)={\sum \limits_{i=1}^{n} -pi\quad log_2\quad pi} $$ Keterangan :

S=Himpunan kasus
n = jumlah partisi S
pi= proposi Si terhadap S

Gain¶

Gain adalah ukuran efektifitas suatu atribut dalam mengklasifikasikan data, gain digunakan untuk menentukan urutan atribut dimana attribut yang memiliki nilai information Gain terbesar yang dipilih. $$ GAIN(S,A)= entropy(S)-{\sum \limits_{i=1}^{n} \frac{|Si|}{|s|}*entropy(Si)} $$ Keterangan :

S=himpunan kasus
n=jumlah partisi S
|si|=proporsi terhadap S
|s|=jumlah kasus dalam S

GINI Index¶

Dalam penerapan GINI index untuk data berskala continuous, terdapat beberapa metode yang dapat digunakan untuk menentukan titik pemecah terbaik, yakni metode brute-force dan metode midpoints.

Script¶

# menentukan value atau jenis pada atribut

def banyak_elemen (kolom, data):
    kelas=[]
    for i in range (len(data)):
        if data.values.tolist()[i][kolom] not in kelas:
            kelas.append(data.values.tolist()[i][kolom])
    return kelas

kelas=banyak_elemen(df.shape[1]-1, df)
outlook=banyak_elemen(df.shape[1]-5,df)
temp=banyak_elemen(df.shape[1]-4,df)
humidity=banyak_elemen(df.shape[1]-3,df)
windy=banyak_elemen(df.shape[1]-2,df)

print(kelas,outlook,temp,humidity,windy)`

['no', 'yes'] ['sunny', 'overcast', 'rainy'] ['hot', 'mild', 'cool'] ['high', 'normal'] [False, True]

# menentukan count value pada Kelas
#Fungsi countvKelas untuk menghitung berapa perbandingan setiap elemen yang terdapat di class

def countvKelas(kelas,kolomKelas,data):
    hasil=[]
    for x in range(len(kelas)):
        hasil.append(0)
    for i in range (len(data)):
        for j in range (len(kelas)):
            if data.values.tolist()[i][kolomKelas] == kelas[j]:
                hasil[j]+=1
    return hasil

pKelas=countvKelas(kelas,df.shape[1]-1,df)
pKelas

[5, 9]

# menentukan nilai entropy target
# Fungsi entropy untuk Menghitung nilai entropy pada sebuah fiture/class. fungsi e_list untuk mempermudah penghitungan entropy setiap elemen di dalam sebuah fiture

def entropy(T):
    hasil=0
    jumlah=0
    for y in T:
        jumlah+=y
    for z in range (len(T)):
        if jumlah!=0:
            T[z]=T[z]/jumlah

    for i in T:
        if i != 0:
            hasil-=i*math.log(i,2)
    return hasil

def e_list(atribut,n):
    temp=[]
    tx=t_list(atribut,n)
    for i in range (len(atribut)):
        ent=entropy(tx[i])
        temp.append(ent)
    return temp

tOutlook=t_list(outlook,5)
tTemp=t_list(temp,4)
tHum=t_list(humidity,3)
tWin=t_list(windy,2)

print("Sunny, Overcast, Rainy",eOutlook)
print("Hot, Mild, Cold", eTemp)
print("High, Normal", eHum)
print("False, True", eWin)

Sunny, Overcast, Rainy [0.9709505944546686, 0.0, 0.9709505944546686]
Hot, Mild, Cold [1.0, 0.9182958340544896, 0.8112781244591328]
High, Normal [0.9852281360342516, 0.5916727785823275]
False, True [0.8112781244591328, 1.0]

Berikut adalah contoh data yang akan dirubah menjadi decision tree:

	0	1	2	3	4
0	CASTEMER ID	GENDER	CAR TIPE	SHIRT SIZE	CLASS
1	1	M	FAMILY	SMALL	C0
2	2	M	SPORT	MEDIUM	C0
3	3	M	SPORT	MEDIUM	C0
4	4	M	SPORT	LARGE	C0
5	5	M	SPORT	EXTRA LARGE	C0
6	6	M	SPORT	EXTRA LARGE	C0
7	7	F	SPORT	SMALL	C0
8	8	F	SPORT	SMALL	C0
9	9	F	SPORT	MEDIUM	C1
10	10	F	LUXURY	LARGE	C1
11	11	M	FAMILY	LARGE	C1
12	12	M	FAMILY	EXTRA LARGE	C1
13	13	M	FAMILY	MEDIUM	C1
14	14	M	LUCURY	EXTRA LARGE	C1
15	15	F	LUCURY	SMALL	C1
16	16	F	LUCURY	SMALL	C1
17	17	F	LUCURY	MEDIUM	C1
18	18	F	LUCURY	MEDIUM	C1
19	19	F	LUCURY	MEDIUM	C1
20	20	F	LUCURY	LARGE	C1

pertama mencari entropy(s) dari kolom class di atas,

diket:

co=10 = Pi=10/20

c1=10=Pi=10/20 $$ Entropy(S)={\sum \limits_{i=1}^{n} -pi\quad log2\quad pi} $$

$$ Entropy(S)= -10/20 * log2 10/20 -10/20 *log2 10/20 $$

$$ Entropy(S)= 1 $$

Kemudian menghitung gain setiap kolom di atas: $$ GAIN(GENDER)= entropy(S)-{\sum \limits_{i=1}^{n} \frac{|Si|}{|s|}*entropy(Si)} $$ GAIN(GENDER)= 1-[10/20(6,4)+10/20(4,6)]

= 1-10/20(-6/10 x log2 6/10 - 4/10 x log2 4/10) +10/20(-4/10 x log2 4/10 - 6/10 x log2 6/10 )

=1-(10/20 x 0,970951)+(10/20 x 0,970951)

=1-(0,4485475+0,4485475)

=1-0,970951

=0.029049 $$ GAIN(CAR\quad TIPE)= entropy(S)-{\sum \limits_{i=1}^{n} \frac{|Si|}{|s|}*entropy(Si)} $$ GAIN(CAR TIPE)= 1-[4/20(1,3)+8/20(8,0)+8/20(1,7)]

= 1-4/20(-1/4 x log2 1/4 - 3/4 x log2 3/4) +8/20(-8/8 x log2 8/8 - 0/8 x log2 0/8 )+8/20(-1/8 x log2 1/8 - 7/8 x log2 7/8)

=1-(0,162256+0+0,217426)

=1-0,379681

=0,620319

GAIN(shirt hat)= 1-[5/20(3,2)+7/20(3,4)+4/20(2,2)+4/20(2,2)]

= 1-5/20(-3/5 x log2 3/5 - 2/5 x log2 2/45 +7/20(-3/7 x log2 3/7 - 4/7 x log2 4/7 )+4/20(-2/4 x log2 2/4 - 2/2 x log2 2/2)+4/20(-2/4 log2 2/4-2/4 log2 2/4)

=1-(0,242738+0,34483+0,2+0,2)

=1-0,987567

=0,012433

Referensi¶

https://en.wikipedia.org/wiki/Decision_tree_learning http://dinus.ac.id/repository/docs/ajar/5DecTreeClass.pdf