Pendahuluan

Pada dasarnya bagging terdiri dari 2 tahapan:

1. Bootstrap

Algoritam dasar:

• Data training diambil (Bootstrap resampling) sehingga mendapatkan Data#1. Lalu dijalankan algoritma pohon klasifikasi 1 dengan data#1.

• Lanjutkan proses pertama s.d. ke-k

• Pada saat ingin memprediksi, kita memasukkan prediksi pada pohon pertama, pohon kedua, s.d. pohon ke-k. Hasil prediksi setiap pohon selanjutnya akan digabungkan yang disebut sebagai proses AGGREGATING.

• Aggregating (majority vote). Misalnya mayoritas hasil prediksi dari seluruh pohon tadi kategori hijau, maka yang kita pilih adalah hijau.

2. Aggregating

• Aggregating (majority vote). Misalnya mayoritas hasil prediksi dari seluruh pohon tadi kategori hijau, maka yang kita pilih adalah hijau. Jika dalam regresi, kita gunakan nilai rata2nya.

Ilustrasi

Kita ingin memprediksi seorang perempuan tertarik atau tidak untuk membeli suatu produk?

Ciri2 wanita: Perempuan, menikah, usia 35 tahun, income 8 juta per bulan.

Tahapan: Kita cari prediksi untuk setiap pohon lalu kita rekap/aggregasi (mana yg suaranya terbanyak itu yg kita pilih).

Karena dari 3 pohon terdapat 2 pohon yang memprediksi tidak tertarik sehingga prediksi akhir dari individu tadi adalah TIDAK TERTARIK untuk membeli.

Pendekatan bagging (bootstrap + aggregating) merupakan salah satu pendekatan paling sederhana pada metode ensemble. Meskipun pendekatan ini dapat dipakai luas untuk berbagai algoritma pemodelan, pada dokumen ini kita akan membatasi diskusi pada metode bagging untuk klasifikasi dengan base learner berupa pohon klasifikasi.

Andaikan kita memiliki sebuah data training D yang berisi beberapa variabel prediktor dan sebuah variabel target kelas (kita batasi pembahasan untuk variabel target memiliki hanya dua kelas). Secara umum, tahapan pemodelan bagging untuk klasifikasi adalah berikut ini.

Lakukan prosedur bootstrap untuk melakukan resampling (yaitu sampling with replacement) pada D. Andaikan kita dapatkan Db

Susun model pohon klasifikasi menggunakan Db dan peroleh modelnya

Ulangi langkah 1-2 hingga k kali. Misalkan k=100, maka kita akan memiliki 100 buah pohon klasifikasi

Proses prediksi dilakukan dengan menentukan prediksi dari suatu amatan menggunakan setiap 100 pohon yang terbentuk. Masing-masing pohon bisa memberikan prediksi yang berbeda. Prediksi akhir diperoleh secara agregat dengan melakukan proses majority voting atau voting dengan suara terbanyak. Jika kelas prediksi yang dominan adalah YA, maka prediksi final adalah YA. Sebaliknya, jika yang dominan adalah TIDAK, maka prediksi finalnya TIDAK.

Karena adanya proses agregasi, bagging efektif dalam mereduksi ragam dugaan dari masing-masing base learner (ingat, umumnya merata-ratakan menyebabkan ragam mengecil), meskipun tidak selalu berhasil. Proses agregasi ini lebih efektif jika base learner yang digunakan adalah yang kurang stabil seperti pohon klasifikasi dan k-NN.

Proses Bagging di R

Salah satu fungsi yang dapat digunakan untuk menjalankan algoritma bagging di R adalah bagging() yang tersedia pada package ipred.

Berikut ini ilustrasi penerapannya pada data winequality-red.csv yang memuat informasi karakteristik 1599 anggur merah di Portugas, beserta dengan hasil penilaian kualitasnya menurut pakar wine. Data diperoleh dari UCI Machine Learning Repository.

Nilai kualitas yang semula berada pada selang 0-10 dikelompokkan terlbeih dahulu menjadi dua kelas yaitu yang nilainya kurang dari atau sama dengan 6 masuk dalam kelas 0 (kurang), selainnya dimasukkan pada kelas 1 (baik).

Pada program di bawah ini, replikasi bootstrap yang dilakukan adalah 100 kali, yang berarti ada 100 kali pengambilan sampel ulang dari data dan 100 kali pembuatan pohon klasifikasi dari setiap sampel tersebut. Pohon yang dibuat sedemikian rupa dengan setting minsplit=20 dan cp=0.

Opsi lain yang digunakan pada program ini adalah coob=TRUE yang berarti bahwa kita meminta program menghitung out-of-bag error, yaitu tingkat kesalahan prediksi yang didasarkan pada amatan yang tidak terpilih pada proses bootstrap. Ini adalah salah satu keuntungan menerapkan bagging dimana dugaan tingkat kesalahan klasifikasi tidak harus dihitung menggunakan validasi silang. PAda saat proses resampling ada saja amatan yang tidak terambil, dan itu disebut sebagai amatan out-of-bag (OOB), yang kemudian diprediksi seperti berlaku sebagai data testing.

setwd("D:\\Kuliah S2 IPB\\Bahan Kuliah\\Semester 1 SSD 2020\\05 Sains Data\\R\\UAS\\")
data <- read.csv("winequality-red.csv", sep=";",header = TRUE)
data$quality <- ifelse(data$quality <= 6, 0, 1)

dim(data)

## [1] 1599   12

colnames(data)

##  [1] "fixed.acidity"        "volatile.acidity"     "citric.acid"         
##  [4] "residual.sugar"       "chlorides"            "free.sulfur.dioxide" 
##  [7] "total.sulfur.dioxide" "density"              "pH"                  
## [10] "sulphates"            "alcohol"              "quality"

#model bagging
library(ipred)
library(rpart)
model_bag <- bagging(
  formula = as.factor(quality) ~ .,
  data = data,
  nbagg = 100,  
  coob = TRUE,
  control = rpart.control(minsplit = 20, cp = 0)
)

model_bag

## 
## Bagging classification trees with 100 bootstrap replications 
## 
## Call: bagging.data.frame(formula = as.factor(quality) ~ ., data = data, 
##     nbagg = 100, coob = TRUE, control = rpart.control(minsplit = 20, 
##         cp = 0))
## 
## Out-of-bag estimate of misclassification error:  0.1032

set.seed(1104)
ooberr <- NULL
for (banyakpohon in seq(10,100, by=2)) {
  model_bag <- bagging(formula = as.factor(quality) ~ .,
                       data = data, nbagg = banyakpohon,
                       coob = TRUE, control = rpart.control(minsplit = 20, cp = 0))
  ooberr[banyakpohon] <- model_bag$err
}
plot(seq(10,100, by=2) , na.omit(ooberr), type="b", xlab="banyaknya pohon", ylab="error OOB")

set.seed(1104)
model_bag <- bagging(
  formula = as.factor(quality) ~ .,
  data = data,
  nbagg = 70,  
  coob = TRUE,
  control = rpart.control(minsplit = 20, cp = 0))
anggurbaru <- data.frame(
  fixed.acidity = 8.1,
  volatile.acidity = 0.45,
  citric.acid = 0.10,
  residual.sugar = 2.1,
  chlorides = 0.080,
  free.sulfur.dioxide = 14,
  total.sulfur.dioxide = 43,
  density = 0.9981,
  pH = 4.50,
  sulphates = 0.64,
  alcohol = 10.3)
predict(model_bag, newdata=anggurbaru)

## [1] 0
## Levels: 0

Pendahuluan

Secara umum Random Forest merupakan pengembangan dari Bagging, yaitu secara berkali-kali melakukan bootstrap terhadap data training dan menyusun pohon klasifikasi berdasarkan data hasil resampling tersebut, dan kemudian proses prediksi dilakukan dengan mengagregasi hasil prediksi dari banyak pohon yang umumnya menggunakan pendekatan majority vote.

Perbedaan antara Random Forest dan Bagging terletak pada proses penentuan splitting pada pembentukan pohon klasifikasi. JIka pada algoritma asalnya, untuk menentukan splitting terbaik dilakukan dengan memeriksa semua variabel prediktor, pohon-pohon pada random forest dibentuk dengan proses splitting yang memilih cara terbaik dari sebagian kecil variabel prediktor. SUbset variabel yang diperiksa diperoleh secara acak dari set variabel prediktor yang ada. Karena itu, bentuk pohon yang diperoleh pada algoritma ini dapat sangat berbeda dari satu pohon ke pohon yang lain. Proses ini diharapkan mampu memperkecil korelasi antar pohon sehingga efektifitas proses ensemble menjadi lebih baik.

Algoritma dasar dari random forest adalah sebagai berikut:

1. Given a training data set

2. Select number of trees to build (n_trees)

3. for i = 1 to n_trees do

4.  Generate a bootstrap sample of the original data
5.  Grow a classification tree to the bootstrapped data
6.  for each split do
7.  | Select m_try variables at random from all p variables
8.  | Pick the best variable/split-point among the m_try
9.  | Split the node into two child nodes
10.  end
11. Use typical tree model stopping criteria to determine when a tree is complete (but do not prune)

12. end

13. Output ensemble of trees

Algoritma random forest mengadopsi algoritma bagging. Namun, k yang digunakan oleh Random Forest cukup besar sekitar >500.

Perbedaan Bagging dan Random Forest

• Perbedaan terletak pada Proses SPLITTING dalam pembentukan POHON

• Alih-alih memeriksa splitting/partisi terbaik dari SEMUA VARIABEL, Random forest hanya mencari yang terbaik dari SEBAGIAN VARIABEL. Variabel dipilih secara acak baru dicari yang terbaik dari yang terpilih.

• Jika ada p variabel prediktor, pemilihan terbaik disarankan hanya pada akar p saja di setiap kali proses penyekatan/splitting.

Semakin sedikit variabel yang digunakan pada proses splitting akan menyebabkan korelasi antar pohon lebih rendah (sumber: The Elements of Statistical Learning oleh Trevor Hastie, Robert Tibshirani, Jerome H.Friedman). Dengan korelasi antar pohon yang kecil inilah diharapkan akurasi prediksi akhirnya menjadi lebih baik. Oleh karena itu, inilah yang mendasari beberapa peneliti untuk menyatakan bahwa Random Forest menghasilkan prediksi yang lebih baik dibandingkan Bagging.

Random Forest di R

Salah satu fungsi yang dapat digunakan untuk menjalankan algoritma Random Forest di R adalah randomForest() yang tersedia pada package randomForest.

Berikut ini ilustrasi penerapannya pada data winequality-red.csv yang memuat informasi karakteristik 1599 anggur merah di Portugas, beserta dengan hasil penilaian kualitasnya menurut pakar wine.

Nilai kualitas yang semula berada pada selang 0-10 dikelompokkan terlebih dahulu menjadi dua kelas yaitu yang nilainya kurang dari atau sama dengan 6 masuk dalam kelas 0 (kurang), selainnya dimasukkan pada kelas 1 (baik).

Pada program di bawah ini, replikasi bootstrap yang dilakukan adalah 500 kali, yang berarti ada 500 kali pengambilan sampel ulang dari data dan 500 kali pembuatan pohon klasifikasi dari setiap sampel tersebut. Pohon yang dibuat sedemikian rupa dengan setting mtry=3 yang berarti bahwa pada proses splitting pemebntukan pohon klasifikasinya, hanya 3 variabel secara acak yang dicek/dibandingkan untuk menentukan splitting terbaik.

Algoritma dijalankan dan model yang diperoleh disimpan pada objek dengan nama model_rf

library(randomForest)

## randomForest 4.6-14

## Type rfNews() to see new features/changes/bug fixes.

model_rf <- randomForest(as.factor(quality) ~ .,
                       data=data,  
                       ntree=1000, mtry=3)
model_rf

## 
## Call:
##  randomForest(formula = as.factor(quality) ~ ., data = data, ntree = 1000,      mtry = 3) 
##                Type of random forest: classification
##                      Number of trees: 1000
## No. of variables tried at each split: 3
## 
##         OOB estimate of  error rate: 8.26%
## Confusion matrix:
##      0   1 class.error
## 0 1346  36   0.0260492
## 1   96 121   0.4423963

Terlihat dari hasil di atas bahwa berdasarkan amatan OOB (out-of-bag), tingkat kesalahan klasifikasi yang diperoleh adalah sekitar 8.2% atau akurasi sebesar 91.8%. Akurasi ini cenderung lebih tinggi jika kita melihat hasil pengerjaan yang sama menggunakan Bagging

anggurbaru <- data.frame(
  fixed.acidity = 8.1,
  volatile.acidity = 0.45,
  citric.acid = 0.10,
  residual.sugar = 2.1,
  chlorides = 0.080,
  free.sulfur.dioxide = 14,
  total.sulfur.dioxide = 43,
  density = 0.9981,
  pH = 4.50,
  sulphates = 0.64,
  alcohol = 10.3)
prediksi <- predict(model_rf, newdata=anggurbaru)
prediksi

## 1 
## 0 
## Levels: 0 1

Perbedaan AdaBoost dan Random Forest

Dalam Random Forest, pemisah pada pohon klasifikasi diperoleh dengan memilih yang terbaik dari sebagian (subset) variabel prediktor, bukan dari semua variabel. Pohon dibiarkan tumbuh besar dan algoritma splitting berhenti sesuai dengan hyperparameter yang ditentukan di awal (seperti minsplit, maxdepth, dsb).Tidak ada proses pruning (pemangkasan) pada pohon tersebut.

Perbedaan:

Random Forest: Kumpulan Pohon AdaBoost: Kumpulan Stump. Stump adalah pohon kecil yang hanya diperoleh dari satu kali splitting. Pohon kecil yang hanya punya dua simpul akhir (dua daun). Karena pohonnya kecil, maka akurasinya bisa rendah sehingga sering disebut weak learner (model yang akurasi sangat kurang dibandingkan dengan pohon yang tumbuh besar).

Random Forest: antar pohon diperoleh secara paralel. Jadi, satu pohon dengan pohon lain saling bebas (INDEPENDEN).

AdaBoost: Stump dibuat secara sekuensial. Jadi dibuat satu stump dulu, stump selanjutnya dibuat dari stump sebelumnya. Hal ini karena kesalahan yang dibuat oleh pohon/stump pertama akan memengaruhi proses pembuatan pohon/stump yang kedua, karena kesalahan yang dibuat oleh pohon/stump kedua akan memengaruhi proses pembuatan pohon/stump yang ketiga, dst.

Random Forest: Prediksi final disusun dengan menetapkan majority vote (prediksi yang dominan) dimana satu pohon satu suara (one tree, one vote).Misal: ada 5 pohon, pohon pertama prediksi YES, pohon Kedua NO, Pohon Ketiga YES, Pohon keempat YES, dan Pohon kelima NO. Rekapnya 3 YES dan 2 NO sehingga prediksi FINAL adalah YES (yang dominan).

AdaBoost: masing2 stump memiliki bobot suara yang berbeda (bobotnya tidak sama untuk setiap stump).Misal: stump 1 YES bobot 0.51, stumpt kedua NO bobot 0.86, stump ketiga YES bobot 0.13, stump keempat YES bobot 0.27, stump kelima No bobot 0.74, dan Stump keenam YES bobot 0.27. Jika ditotal jumlah bobot untuk YES: 1.18 dan NO: 1.60. Karena bobot NO lebih besar, maka prediksi final NO.

Algoritma AdaBoost

AdaBoost adalah Kumpulan pohon kecil (stump) yang dibuat secara sekuensial. Hal ini karena kesalahan yang dibuat oleh pohon/stump pertama akan memengaruhi proses pembuatan pohon/stump yang kedua, karena kesalahan yang dibuat oleh pohon/stump kedua akan memengaruhi proses pembuatan pohon/stump yang ketiga, dst. Pengaruh ini ditandai dengan peningkatan bobot pada amatan yang “salah klasifikasi”. Jadi, amatan yang “salah klasifikasi” pada satu tahap akan ditingkatkan bobotnya pada tahap berikutnya.

Ensemble untuk mendapatkan prediksi final diperoleh dengan mempertimbangkan bobot suara dari setiap pohon.

AdaBoost di R

Salah satu fungsi yang dapat digunakan untuk menjalankan algoritma AdaBoost di R adalah boosting() yang tersedia pada package adabag.

Berikut ini ilustrasi penerapannya pada data winequality-red.csv yang memuat informasi karakteristik 1599 anggur merah di Portugas, beserta dengan hasil penilaian kualitasnya menurut pakar wine.

Nilai kualitas yang semula berada pada selang 0-10 dikelompokkan terlbeih dahulu menjadi dua kelas yaitu yang nilainya kurang dari atau sama dengan 6 masuk dalam kelas 0 (kurang), selainnya dimasukkan pada kelas 1 (baik).

Pada program di bawah ini, hanya untuk menyederhanakan ilustrasi, digunakan iterasi sebanyak 5 kali. Artinya ada 5 stump/pohon kecil yang dibuat secara sekuensial yang diatur sedemikian rupa menggunakan opsi mfinal=3.

Opsi pohon yang digunakan adalah maxdepth=1 untuk meminta program membuat stump sebagai weak learner dari algoritma boosting. Pembaca dapat menghilangkan opsi tersebut jika ingin menggunakan pohon klasifikasi biasa sebagai weak lerner.

Algoritma dijalankan dan model yang diperoleh disimpan pada objek dengan nama model.adaboost. Model dibuat menggunakan data training yang sebelumnya diambil secara acak dari data lengkap.

#install.packages("adabag")
library(adabag)

## Loading required package: caret

## Loading required package: lattice

## Loading required package: ggplot2

## 
## Attaching package: 'ggplot2'

## The following object is masked from 'package:randomForest':
## 
##     margin

## Loading required package: foreach

## Loading required package: doParallel

## Loading required package: iterators

## Loading required package: parallel

## 
## Attaching package: 'adabag'

## The following object is masked from 'package:ipred':
## 
##     bagging

library(caret)

#membagi data menjadi dua bagian: training dan testing
set.seed(1104)
acak <- createDataPartition(data$quality, p=0.7, list = F)
train <- data[acak, ]
test <- data[-acak, ]


train$quality<- as.factor(train$quality)
head(train)

##   fixed.acidity volatile.acidity citric.acid residual.sugar chlorides
## 2           7.8             0.88        0.00            2.6     0.098
## 3           7.8             0.76        0.04            2.3     0.092
## 5           7.4             0.70        0.00            1.9     0.076
## 6           7.4             0.66        0.00            1.8     0.075
## 7           7.9             0.60        0.06            1.6     0.069
## 9           7.8             0.58        0.02            2.0     0.073
##   free.sulfur.dioxide total.sulfur.dioxide density   pH sulphates alcohol
## 2                  25                   67  0.9968 3.20      0.68     9.8
## 3                  15                   54  0.9970 3.26      0.65     9.8
## 5                  11                   34  0.9978 3.51      0.56     9.4
## 6                  13                   40  0.9978 3.51      0.56     9.4
## 7                  15                   59  0.9964 3.30      0.46     9.4
## 9                   9                   18  0.9968 3.36      0.57     9.5
##   quality
## 2       0
## 3       0
## 5       0
## 6       0
## 7       0
## 9       1

#membangun model dengan algoritma adaboost
model.adaboost <- boosting(quality~., data=train, 
                  mfinal=5, control=rpart.control(maxdepth=1),
                  coeflearn='Freund')

#menampilkan stump pertama
model.adaboost$trees[1]

## [[1]]
## n= 1120 
## 
## node), split, n, loss, yval, (yprob)
##       * denotes terminal node
## 
## 1) root 1120 159 0 (0.85803571 0.14196429)  
##   2) alcohol< 11.55 955  75 0 (0.92146597 0.07853403) *
##   3) alcohol>=11.55 165  81 1 (0.49090909 0.50909091) *

#menampilkan bobot dari stump pertama
model.adaboost$weights[1]

## [1] 1.70686

#menampilkan stump kedua
model.adaboost$trees[2]

## [[1]]
## n= 1120 
## 
## node), split, n, loss, yval, (yprob)
##       * denotes terminal node
## 
## 1) root 1120 265 0 (0.7633929 0.2366071)  
##   2) volatile.acidity>=0.355 863 131 0 (0.8482039 0.1517961) *
##   3) volatile.acidity< 0.355 257 123 1 (0.4785992 0.5214008) *

#menampilkan bobot dari stump kedua
model.adaboost$weights[2]

## [1] 1.089605

maudiprediksi <- test[1,]
prob1 <- predict(model.adaboost$trees[1], maudiprediksi)
prob2 <- predict(model.adaboost$trees[2], maudiprediksi)
prob3 <- predict(model.adaboost$trees[3], maudiprediksi)
prob4 <- predict(model.adaboost$trees[4], maudiprediksi)
prob5 <- predict(model.adaboost$trees[5], maudiprediksi)

prediksi1 <- ifelse(prob1[[1]][1]>prob1[[1]][2],0,1)
prediksi2 <- ifelse(prob2[[1]][1]>prob2[[1]][2],0,1)
prediksi3 <- ifelse(prob3[[1]][1]>prob3[[1]][2],0,1)
prediksi4 <- ifelse(prob4[[1]][1]>prob4[[1]][2],0,1)
prediksi5 <- ifelse(prob5[[1]][1]>prob5[[1]][2],0,1)

bobot1 <- model.adaboost$weights[1]
bobot2 <- model.adaboost$weights[2]
bobot3 <- model.adaboost$weights[3]
bobot4 <- model.adaboost$weights[4]
bobot5 <- model.adaboost$weights[5]

hasil <- cbind(c(prediksi1, prediksi2, prediksi3, prediksi4, prediksi5),
               c(bobot1, bobot2, bobot3, bobot4, bobot5))
hasil

##      [,1]      [,2]
## [1,]    0 1.7068600
## [2,]    0 1.0896050
## [3,]    0 0.7643298
## [4,]    0 0.7232426
## [5,]    1 0.3959532

sumbobot.0 <- (1-prediksi1)*bobot1+
  (1-prediksi2)*bobot2+
  (1-prediksi3)*bobot3+
  (1-prediksi4)*bobot4+
  (1-prediksi5)*bobot5
sumbobot.1 <- prediksi1*bobot1+
  prediksi2*bobot2+
  prediksi3*bobot3+
  prediksi4*bobot4+
  prediksi5*bobot5

prediksifinal <- ifelse(sumbobot.0 > sumbobot.1, 0, 1)
c(sumbobot.0, sumbobot.1, prediksifinal)

## [1] 4.2840373 0.3959532 0.0000000

prediksi.langsung <- predict(model.adaboost, maudiprediksi)$class
prediksi.langsung

## [1] "0"

test$quality<- as.factor(test$quality)
prediksi.boost <- predict(model.adaboost, test)$class

confusionMatrix(as.factor(prediksi.boost), 
                test$quality, positive = "1")

## Confusion Matrix and Statistics
## 
##           Reference
## Prediction   0   1
##          0 390  41
##          1  24  24
##                                           
##                Accuracy : 0.8643          
##                  95% CI : (0.8303, 0.8937)
##     No Information Rate : 0.8643          
##     P-Value [Acc > NIR] : 0.53301         
##                                           
##                   Kappa : 0.3498          
##                                           
##  Mcnemar's Test P-Value : 0.04719         
##                                           
##             Sensitivity : 0.3692          
##             Specificity : 0.9420          
##          Pos Pred Value : 0.5000          
##          Neg Pred Value : 0.9049          
##              Prevalence : 0.1357          
##          Detection Rate : 0.0501          
##    Detection Prevalence : 0.1002          
##       Balanced Accuracy : 0.6556          
##                                           
##        'Positive' Class : 1               
##