algoritma ID3 dengan R

lisa novia

2023-01-12

Algoritma ID3

ID3 merupakan algoritma decision tree Learning(algoritma pembelajaran pohon keputusan) yang melakukan pencarian secara menyeluruh (greedy) pada semua kemungkinan pohon keputusan.

Tahapan Algoritma ID3

  1. Siapkan data training
  2. Pilih atribut sebagai akar
  3. Buat cabang untuk tiap-tiap nilai
  4. Ulangi prosesuntuk setiap cabang sampai semua kasus pada cabang memiliki kelas yang sama

Eksperimen Algoritma ID3

Library

library(dplyr)
## 
## Attaching package: 'dplyr'
## The following objects are masked from 'package:stats':
## 
##     filter, lag
## The following objects are masked from 'package:base':
## 
##     intersect, setdiff, setequal, union

Masukkan Dataset

library(data.tree)
View(iris)

Mencari Nilai Entropy

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)
}
Entropy(c(10, 0))
## [1] 0
Entropy(c(0, 10))
## [1] 0
entropy <- function(Species) Entropy(c(Species, 150 - Species))
entropy <- Vectorize(entropy)
curve( entropy, from = 0, to = 150, xname = 'Species')

Nilai Information Gain

IG_numeric<-function(data, feature, target, bins=4) {
  #Hapus baris di mana fiturnya adalah NA
  data<-data[!is.na(data[,feature]),]
  #Menghitung entropi untuk induk(label data)
  e0<-entropy(data[,target])
  
  data$cat<-cut(data[,feature], breaks=bins, labels=c(1:bins))
  
  #gunakan dplyr untuk menghitung e dan p untuk setiap nilai fitur
  dd_data <- data %>% group_by(cat) %>% summarise(e=entropy(get(target)), 
                 n=length(get(target)),
                 min=min(get(feature)),
                 max=max(get(feature))
                 )
  
  #hitung p untuk setiap nilai fitur
  dd_data$p<-dd_data$n/nrow(data)
  #menghitung IG
  IG<-e0-sum(dd_data$p*dd_data$e)
  
  return(IG)
}

Membuat DataFrame untuk Nilai Entropy & Information Gain Setiap Kolom dan Diurutkan:

Fitur_Exploration <- function(df, bin){
  E <- numeric()
  for (i in 1:ncol(df)){
    nama<-names(df)[i]
    E[i]<-entropy(df[,nama])
    }
  
  ig <- numeric()
  kol=ncol(df)-1
  for (i in 1:kol){
    ig[i]<-IG_numeric(df, names(df)[i], names(df)[ncol(df)], bins=bin)
  }
  ig[ncol(df)]<-0 #Masih dicek lagi
  Column_Name <- names(df)
  Entropy <- E
  IG <- ig
  df_E <- data.frame(Column_Name, Entropy, IG)
  df_E_sort <- df_E[order(-IG),]
  return(df_E_sort)
}

Column_Name Entropy IG

4 Petal.Width 4.049827 1.3245310

3 Petal.Length 5.034570 1.2662530

1 Sepal.Length 4.822018 0.6402424

2 Sepal.Width 4.023181 0.3914756

5 Species 1.584963 0.0000000

Pohon Keputusan

library(rpart)
library(rpart.plot)
trees<-rpart(Species ~. , data = iris, method = 'class')
rpart.plot(trees)