Algoritma ID3
Pengertian
Algoritma ID3 atau Iterative Dichotomiser 3 adalah sebuah metode yang digunakan untuk membuat pohon keputusan yang telah dikembangkan oleh J. Ross Quinlan sejak tahun 1986. Algoritma ID3 melakukan pencarian secara menyeluruh pada semua kemungkinan pohon keputusan. Algoritma ID3 berusaha membangun decision tree (pohon keputusan) secara top-down (dari atas ke bawah).
Struktur Pohon Keputusan
Struktur pohon keputusan terdiri dari root node (node akar), internal node (node cabang), dan leaf node. Pembentukan pohon klasifikasi dengan algoritma ID3 melalui dua langkah, yaitu :
Menghitung nilai entropy
Menghitung nilai information gain dari setiap variabel
Tahapan Algoritma ID3
Tahapan Algoritma ID3 dibagi menjadi 6 tahapan, yaitu :
Menyiapkan Dataset
Dataset yang digunakan yaitu dataset yang berlabel nominal. Untuk algoritma ID3 menggunakan data jenis klasifikasi.
Menghitung Nilai Entropy
Konsep Entropy digunakan untuk mengukur “seberapa informatifnya” sebuah node (yang biasanya disebut seberapa baiknya).
Rumus Entropy : \[\begin{equation} \operatorname{entropy}(s)=-p_{+} \log _2 p_{+}-p_{-} \log _2 p_{-} \end{equation}\] Keterangan :
S = Himpunan (dataset) Kasus
𝑝_+ = jumlah label yang bersolusi positif (mendukung) dibagi total kasus.
𝑝_− = jumlah label yang bersolusi negative (tidak mendukung) dibagi total kasus.
Menghitung Nilai Information Gain
Information gain adalah kriteria pemisahan yang menggunakan pengukuran entropy. Information gain digunakan untuk mengukur efektivitas suatu atribut dalam mengklasifikasikan data.
Rumus Information Gain : \[\begin{equation} \operatorname{Gain}(A)=\operatorname{entropy}(s)-\sum_{i=1}^k \frac{|S i|}{|S|} x \operatorname{entropy}(S i) \end{equation}\] Keterangan :
S = Ruang data (sampel)
A = Atribut
⎸𝑆𝑖⎹ = jumlah sampel data
⎸𝑆⎹ = jumlah seluruh sampel data
Entropy (Si) = untuk sampel-sampel yang memiliki nilai i
Menentukan Root Node (Node Akar)
Root node atau node akar ditentukan berdasarkan nilai information gain yang telah di cari. Atribut dengan nilai information gain tertinggi akan menjadi root node nya. Atribut yang telah di pilih tidak diikutkan lagi ke perhitungan entropy dan information gain selanjutnya.
Membuat Node Cabang
Node cabang di dapat dari perhitungan entropy dan information gain selanjutnya.
Ulangi Langkah 2-4
Mengulangi langkah 2-4 hingga membentuk pohon keputusan.
Eksperimen Algoritma ID3
Berikut ini merupakan eksperimen menggunakan Algoritma ID3
Library
library(dplyr)Loading Dataset
pada eksperimen ini menggunakan data Penguin yang bersumber dari Kaggle
library(readxl)## Warning: package 'readxl' was built under R version 4.1.3Data_penguin <- read_excel("Data penguin.xlsx")
View(Data_penguin)Menghitung Nilai Entropy
Nilai entropy dapat dihitung dengan cara berikut :
IsPure <- function(data) {
length(unique(data[,ncol(data)])) == 1
}
Entropy <- function( vls ) {
res <- vls/sum(vls) * log2(vls/sum(vls))
res[vls == 0] <- 0
-sum(res)
}Menghitung nilai entropy untuk kolom Culmen.Length
print(Entropy(Data_penguin$Culmen.Length))## [1] 8.406704Menghitung nilai entropy untuk kolom Culmen.Depth
print(Entropy(Data_penguin$Culmen.Depth))## [1] 8.40822Menghitung nilai entropy untuk kolom Flipper.Length
print(Entropy(Data_penguin$Flipper.Length))## [1] 8.414352Menghitung nilai entropy untuk kolom Body.Mass
print(Entropy(Data_penguin$Body.Mass))## [1] 8.392099Nilai Information Gain
Menghitung nilai information gain dapat dilakukan dengan cara berikut :
InformationGain <- function( tble ) {
tble <- as.data.frame.matrix(tble)
entropyBefore <- Entropy(colSums(tble))
s <- rowSums(tble)
entropyAfter <- sum (s / sum(s) * apply(tble, MARGIN = 1, FUN = Entropy ))
informationGain <- entropyBefore - entropyAfter
return (informationGain)
}Menghitung nilai informtion gain untuk kolom Culmen.Length
InformationGain(table(Data_penguin[,c('Culmen.Length', 'Species')]))## [1] 1.15916Menghitung nilai informtion gain untuk kolom Culmen.Depth
InformationGain(table(Data_penguin[,c('Culmen.Depth', 'Species')]))## [1] 0.9514694Menghitung nilai informtion gain untuk kolom Flipper.Length
InformationGain(table(Data_penguin[,c('Flipper.Length', 'Species')]))## [1] 0.9853352Menghitung nilai informtion gain untuk kolom Body.Mass
InformationGain(table(Data_penguin[,c('Body.Mass', 'Species')]))## [1] 0.9216235Menghitung nilai informtion gain untuk kolom Species
InformationGain(table(Data_penguin[,c('Species', 'Species')]))## [1] 1.514707Membuat Pohon Keputusan
Pohon keputusan dapat dibuat dengan cara berikut
library(rpart) ## Warning: package 'rpart' was built under R version 4.1.3library(rpart.plot) ## Warning: package 'rpart.plot' was built under R version 4.1.3tree<- rpart(Species~., data = Data_penguin, method = 'class')
rpart.plot(tree)