Bab II Dasar Teori
2.1 Estimasi Akurasi Classifier Estimasi akurasi classifier penting dilakukan untuk mengevaluasi seberapa akurat sebuah classifier mengklasifikasikan future data, yaitu data yang belum pernah digunakan di dalam pembelajaran untuk membentuk classifier. Estimasi akurasi juga dapat digunakan untuk membandingkan beberapa buah classifier yang berbeda-beda. Berikut ini akan dibahas beberapa buah teknik untuk mengestimasi akurasi classifier. [HAN01]
2.1.1 Metode Holdout Pada metode holdout, data secara acak dibagi menjadi dua buah bagian yang independent yaitu sebuah training set dan sebuah test set. Pada umumnya perbandingan yang digunakan yaitu 2:1 untuk training set berbanding test set. [HAN01]
Metode holdout termasuk pessimistic estimator karena hanya sebagian data yang diberikan untuk melakukan pembelajaran. Semakin banyak instance yang diambil untuk test set, maka semakin tinggi pula bias estimasinya. Akan tetapi jika semakin kecil jumlah instance dalam test set maka interval kepercayaan untuk akurasi yang dihasilkan akan semakin besar. Metode holdout bergantung pada pembagian training set dan test set yang dilakukan secara acak. [KOH07]
Random subsampling merupakan variasi dari metode holdout dimana metode holdout diulangi sebanyak k kali. Estimasi akurasi secara keseluruhan didapat dengan menghitung
rata-rata
akurasi
yang
dihasilkan
II-1
di
setiap
iterasi.[HAN01]
II-2
2.1.2 Bootstrap Bootstrap adalah sebuah metode perhitungan nilai akurasi yang menggunakan sampling dengan penggantian untuk membentuk training set. Sebuah dataset yang terdiri dari n buah instance akan dilakukan sampling dengan penggantian sebanyak n kali untuk membentuk training set. Sedangkan test set dibentuk dari instance yang tidak muncul pada training set. Metode bootstrap ini sangat cocok untuk dataset yang berukuran kecil.[CCS07]
2.1.3 K-fold Cross Validation K-fold cross validation adalah sebuah teknik intensif komputer yang menggunakan keseluruhan data yang ada sebagai training set dan test set [BEN04]. Seluruh data secara acak dibagi menjadi K buah subset Bk dengan ukuran yang sama dimana Bk merupakan himpunan bagian dari {1,...,n} sedemikian sehingga
∪
K
k =1
Bk = {1,.., n} dan
Bj ∩ Bk = ∅ ( j≠k). Setelah itu dilakukan iterasi sebanyak K kali. Pada iterasi ke k, subset Bk menjadi test set, sedangkan subset yang lain menjadi training set. Setelah itu dihitung nilai rata-rata error dengan menggunakan hasil dari K buah iterasi. [SCH97]
Kelebihan dari metode ini adalah tidak adanya masalah dalam pembagian data. Setiap data akan menjadi test set sebanyak satu kali dan akan menjadi training set sebanyak K-1 kali. Kekurangan dari metode ini adalah algoritma pembelajaran harus dilakukan sebanyak K kali yang berarti menggunakan K kali waktu komputasi.[SCH97]
Leave One Out Cross Validation (LOO CV) merupakan n-fold Cross Validation dimana n adalah jumlah data yang tersedia.
LOO CV sangat membutuhkan
komputasi yang tinggi jika terdapat data dalam jumlah besar. [SCH97]
II-3
2.2 Algoritma C4.5 Algoritma C4.5 yang dirancang oleh J.R. Quinlan merupakan suksesor dari algoritma ID3. Algoritma C4.5 ini dirancang untuk menghindari terjadinya overfitting pada decision tree yang dihasilkan dengan cara melakukan post-prune pada pohon yang telah dibangun.
Default kriteria pembagi yang dipakai oleh C4.5 adalah gain-ratio. Misalkan C adalah jumlah kelas yang ada, p(D,j) adalah proporsi dari kasus D pada kelas j. Maka sisa ketidakpastian (residual uncertainty) dari kelas dimana D berada dapat dirumuskan sebagai :
C
Info( D ) = −∑ p ( D, j ) × log 2 ( p ( D, j ))
(II-1)
j =1
Sedangkan information gain untuk atribut T yang mempunyai k buah nilai adalah :
k
Di
i =1
D
Gain( D, T ) = Info( D ) − ∑
× Info( Di )
(II-2)
Information gain sebuah atribut dipengaruhi dengan kuat oleh banyaknya nilai atribut tersebut dan akan maksimal ketika terdapat satu kasus untuk setiap subset Di. Sebaliknya, potensial informasi yang didapatkan dengan membagi sekumpulan kasus adalah berdasarkan kepastian subset Di dimana kasus tersebut berada, split information dapat dihitung dengan menggunakan rumus :
k
Split ( D, T ) = −∑ i =1
Di × log 2 D D
Di
(II-3)
Split information cenderung untuk meningkat seiring dengan meningkatnya jumlah keluaran dari tes. Kriteria gain ratio menilai desirability dari sebuah tes sebagai rasio dari information gain dengan split information yang dimilikinya. Rumus untuk menghitung gain ratio dapat dilihat pada rumus (II-4). [MIT97]
II-4
GainRatio ( D, T ) =
Gain( D, T ) Split ( D, T )
(II-4)
Gain ratio dari setiap tes dihitung lalu pembagian dengan maksimum gain ratio akan dipilih. [QUI96A]
Pada beberapa situasi, setiap tes yang mungkin dapat membagi D ke dalam subset dengan distribusi kelas yang sama. Seluruh tes kemudian akan diberikan nilai gain 0, dan C4.5 menggunakan ini sebagai kriteria tambahan untuk berhenti. [QUI96A]
Strategi pembagian secara rekursif di atas menghasilkan pohon yang konsisten dengan data latih, jika hal ini memungkinkan. Hampir semua sistem memotong pohon awal tersebut, mengindentifikasikan subpohon yang berperan kecil dalam keakuratan prediksi dan menggantikannya dengan sebuah daun atau sebuah subpohon yang berasal dari salah satu cabangnya. [QUI96A]
Berikut ini adalah algoritma global untuk membangkitkan decision tree dari sekumpulan data latih D [QUI96A] : 1) jika D memenuhi kriteria untuk berhenti (stopping criterion), maka pohon untuk D adalah sebuah daun yang diisi dengan frekuensi kelas terbanyak di dalam D. Salah satu kriteria berhenti adalah D hanya mengandung kasus dari kelas ini, akan tetapi kriteria lain juga dapat digunakan. 2) sebuah atribut T dengan nilai yang berbeda satu sama lain T1, T2, ......, Tk digunakan untuk membagi D menjadi subset D1, D2, ......, Dk dimana Di hanya mengandung kasus-kasus yang mempunyai nilai Ti. Pohon untuk D dengan tes T sebagai akarnya dengan sebuah subpohon untuk setiap keluaran Ti yang dibangun dengan menerapkan prosedur yang sama secara rekursif untuk kasus di dalam Di. Adapun tes default yang dipakai di C4.5 sebagai kriteria pembagi yaitu [QUI96A] : 1) A= x untuk atribut diskrit A, dengan x adalah sebuah keluaran untuk setiap nilai dari A. 2) A ≤ t untuk atribut kontinyu A, dengan dua keluaran yaitu true dan false. Untuk menentukan treshold t yang memaksimalkan kriteria pembagi, data latih D diurutkan berdasarkan nilai atribut A yang dimilikinya untuk memperlihatkan
II-5 perbedaan nilai v1, v2, ...., vN. Setiap pasang nilai yang berbatasan memberikan potensial treshold t yang dihitung dengan cara :
t=
(v i + v i ) 2
(II-5)
Treshold yang memberikan nilai kriteria pembagi yang paling baik yang akan dipilih.
[MIT97] menyebutkan bahwa C4.5 menggunakan rule post pruning yang tahapantahapannya adalah sebagai berikut: 1) Melakukan inferensi decision tree dari training set, pohon ditumbuhkan hingga sesuai mungkin dengan data latih, tidak masalah walaupun akan terjadi overfitting. 2) Pohon yang telah dihasilkan dikonversi menjadi sekumpulan aturan ekuivalen dengan membuat sebuah aturan untuk setiap jalur dari akar ke daun. Sintak aturan yang dipakai adalah IF prekondisi THEN postkondisi Setiap atribut tes sepanjang jalur dari akar ke daun menjadi prekondisi dan klasifikasi pada node daun akan menjadi postkondisi. 3) Potong/generalisasi setiap rule dengan menghilangkan prekondisi sedemikian sehingga akan meningkatkan keakuratan. 4) Urutkan aturan-aturan yang sudah dipotong tersebut berdasarkan nilai estimasi keakuratannya, lalu dipakai secara terurut ketika melakukan klasifikasi. Akan tetapi, C4.5 pada WEKA hanya mengimplementasikan tahap 1 dan 3 saja. Contoh hasil pruning dengan menggunakan rule post pruning dapat dilihat pada Gambar II-1. 1. 2. 3. 4. 5.
IF (outlook=sunny) and (humidity<=75) THEN yes IF (outlook=sunny) and (humidity>75) THEN no IF (outlook=overcast) THEN yes IF (outlook=rainy) and (windy=true) THEN no IF (outlook=rainy) and (windy=false) THEN yes
Gambar II-1 Hasil pruning dengan menggunakan rule post pruning
Sedangkan hasil pruning dengan menggunakan C4.5 pada WEKA dapat dilihat pada Gambar II-2.
overcast
II-6
Gambar II-2 Hasil pruning dengan menggunakan C4.5 pada WEKA
Metode yang digunakan oleh C4.5 untuk mengestimasi keakuratan sebuah aturan adalah dengan melakukan evaluasi performansi dari training set itu sendiri dengan menggunakan pessimistic estimate yaitu dengan menghitung akurasi aturan terhadap training examples yang menerapkannya lalu menghitung standar deviasi pada estimated akurasi ini mengasumsikan distribusi binomial. [MIT97]
2.3 Delegating Classifiers Delegating classifiers dirancang untuk mengatasi kekurangan yang terdapat di dalam multi-classifiers yaitu loss of comprehensibility dan penggunaan resource komputasi yang berlebihan. Delegating-classifiers dibuat dengan motto ‘let others do the things that
you
cannot
do
well’.
Cautious
classifier
digunakan
hanya
untuk
mengklasifikasikan data yang diprediksi mempunyai nilai confidence yang tinggi, menyerahkan data yang memiliki nilai confidence rendah (abstain) kepada classifier yang lain. Perancangan delegating classifiers mempunyai dua buah isu yaitu menentukan nilai batas ambang confidence atau aturan pendelegasian serta penentuan teknik yang baik untuk membuat classifier kedua yang memiliki performansi yang lebih baik daripada classifier pertama. [FER04] Classifier pertama, f(1), menentukan classifier mana yang akan dipakai untuk melakukan klasifikasi data. Proses penentuan ini dilakukan dengan menggunakan
II-7 nilai confidence klasifikasi data dan nilai batas ambang confidence. Oleh karena itu classifier pertama haruslah merupakan probability estimator yang baik. [KHO06] Classifier kedua, f(2), bertugas khusus untuk menangani data yang didelegasikan oleh classifier pertama. Classifier kedua dibangun dengan melakukan pembelajaran terhadap subset dari training set classifier pertama. Training set untuk classifier kedua ini berisi data dari training set classifier pertama yang diprediksi mempunyai nilai confidence yang lebih rendah dari nilai batas ambang classifier pertama. [KHO06]
Gambar II-3 Proses pembangunan umum delegating classifiers [KHO06]
Gambar II-3 menunjukkan proses pembangunan delegating classifiers secara umum. Training set digunakan untuk melakukan pembelajaran membentuk classifier pertama, f(1), yang kemudian diubah menjadi cautious classifier. Dengan menggunakan classifier pertama yang berbentuk cautious classifier, dilakukan partisi training set untuk membentuk delegated set. Delegated set yang dihasilkan akan digunakan dalam pembelajaran untuk membentuk classifier kedua, f(2). Jika cautious classifier, f(1), memutuskan untuk tidak melakukan prediksi terhadap suatu data, e , maka f(1) akan mendelegasikan data tersebut ke classifier yang lain. Jika ada classifier kedua, f(2), dan sebuah nilai batas ambang confidence τ, maka aturan pendelegasian adalah sebagai berikut. [FER04] IF f(1)CONF(e) > τ THEN prediksi f(1)CLASS(e) ELSE prediksi f(2)CLASS(e)
II-8 Terdapat dua buah metode untuk menentukan nilai batas ambang confidence, yaitu [FER04]: 1. Global Absolute Precentage (GAP) Jika ada sebuah bagian ρ, sebuah classifier f dan sebuah training set Tr maka rumus untuk menentukan nilai batas ambang confidence τ adalah sebagai berikut: τ = max{t:|{e ∈ Tr : fCONF(e) > t} | ≥ ρ × |Tr|}
(II-6)
Dengan demikian τ adalah nilai batas ambang maksimum sedemikan sehingga sedikitnya ρ data dari training set mempunyai nilai confidence yang lebih tinggi.
Aturan pendelegasian untuk metode ini adalah sebagai berikut: IF f(1)CONF(e) > τ THEN prediksi f(1)CLASS(e) ELSE prediksi f(2)CLASS(e) 2. Stratified Absolute Precentage (SAP) Metode ini digunakan untuk mengatasi training set yang tidak seimbang. Setiap kelas c akan mempunyai nilai batas ambang confidence masing-masing τc. Rumus untuk menentukan τc adalah sebagai berikut: τc = max{t:|{e ∈ Trc : fPROBc(e) > t} | ≥ ρ × |Trc|}
(II-7)
Dengan demikian τc adalah nilai batas ambang maksimum untuk setiap kelas c sedemikan sehingga sedikitnya sejumlah ρ bagian dari training set Tr dengan kategori c memiliki nilai confidence yang lebih tinggi.
Aturan pendelegasian untuk metode ini adalah sebagai berikut: IF f(1)CONF(e) > τc THEN prediksi f(1)CLASS(e) ELSE prediksi f(2)CLASS(e) WHERE c = f(1)CLASS(e)
II-9 Penelitian yang dilakukan oleh [FER04] menggunakan tiga buah skenenario, yaitu : 1. Two-Stage Pada skenario ini, classifier pertama akan mendelegasikan data yang diklasifikasikannya dengan nilai confidence lebih rendah daripada nilai batas ambang confidence yang dimilikinya kepada classifier kedua. Hasil klasifikasi dari classifier kedua inilah yang akan digunakan. Skenario ini merupakan skenario dasar delegating classifier. Aturan pendelagasian skenario ini adalah sebagai berikut: IF f(1)CONF(e) > τ THEN prediksi f(1)CLASS(e) ELSE prediksi f(2)CLASS(e) 2. Round rebound Skenario round rebound merupakan varian dari skenario two-stage. Perbedaannya adalah jika classifier kedua akan mendelegasikan kembali data yang diklasifikasikannya dengan nilai confidence lebih rendah daripada nilai batas ambang confidence yang dimilikinya kepada classifier pertama. Alasannya adalah jika data tersebut sama-sama menghasilkan nilai confidence yang rendah pada kedua buah classifier maka data tersebut akan lebih baik diklasifikasikan oleh classifier pertama daripada classifier kedua karena classifier pertama bersifat lebih umum dan kemungkinan terjadinya overfitting lebih kecil. Aturan pendelegasian skenario ini adalah sebagai berikut: IF f(1)CONF(e) > τ(1) THEN prediksi f(1)CLASS(e) ELSEIF f(2)CONF(e) > τ(2) THEN prediksi f(2)CLASS(e) ELSE prediksi f(1)CLASS(e) Penentuan nilai batas ambang confidence untuk classifier kedua τ(2) dapat dilakukan dengan menggunakan training set lengkap (Absolute Precentage) atau dapat menggunakan data yang didelegasikan oleh classifier pertama (Relative Precentage). Adapun rumus penentuan nilai confidence batas ambang untuk classifier kedua τ(2) dapat dilihat pada rumus (II-8). τ(2) = max{t:|{e ∈ Tr≤f(1) : f(2)CONF(e) > t} | ≥ ρ × | Tr≤f(1)|} (II-8)
II-10 3. Iterative Skenario ini juga merupakan varian dari skenario two-stage. Pada skenario ini, dilakukan iterasi terhadap beberapa delegating classifiers. Aturan pendelegasian untuk skenario ini adalah sebagai berikut: IF f(1)CONF(e)>τ THEN prediksi f(1)CLASS(e) ELSEIF f(2)CONF(e)>τ(2) THEN prediksi f(2)CLASS(e) ... ELSEIF f(n-1)CONF(e)>τ(n-1) THEN prediksi f(n-1)CLASS(e) ELSE prediksi f(n)CLASS(e) Hasil penelitian [FER04] menunjukkan bahwa nilai keakuratan yang dihasilkan oleh delegating classifiers tidak jauh berbeda dengan yang dihasilkan oleh multi classifiers. Untuk masalah penggunaan resource, delegating classifiers menggunakan resource yang lebih sedikit dibandingkan dengan multi classifiers.
2.3.1 Parameter Terbaik Delegating Classifiers Parameter terbaik delegating classifiers yang terdapat dalam [FER04], yaitu : 1. Metode penentuan batas ambang yang paling baik adalah GAP. Hal ini didapat setelah melakukan eksperimen untuk membangun delegating classifiers skema two-stage dan metode batas ambang GAP serta SAP menggunakan 22 buah dataset lalu dihitung nilai rata-rata akurasi serta rata-rata nilai AUC untuk berbagai macam persentase delegasi. Dari hasil eksperimen ini didapat bahwa nilai rata-rata akurasi dan rata-rata AUC dengan menggunakan GAP untuk berbagai persentasi delegasi lebih baik daripada menggunakan SAP. 2. Persentase delegasi yang memberikan nilai akurasi terbaik adalah 50%. Hal ini didapat setelah melakukan eksperimen untuk membangun delegating classifiers skema two-stage dan metode batas ambang GAP serta SAP menggunakan 22 buah dataset lalu dihitung nilai rata-rata akurasi serta rata-rata nilai AUC untuk persentase delegasi 20%, 33%, 45%, 50%, 55%, 67%, dan 80%. Dari hasil eksperimen ini didapat bahwa persentase delegasi 50% memberikan rata-rata nilai akurasi dan rata-rata nilai AUC yang paling baik.
II-11 3. Skema round rebound menghasilkan nilai akurasi yang lebih baik dibandingkan dengan skema two-stage. Hal ini didapat dengan membandingkan rata-rata nilai akurasi dan nilai AUC untuk skema round rebound dan skema two-stage menggunakan metode penentuan batas ambang SAP dan GAP untuk persentase delegasi 33%, 45%, 50%, 55%, dan 67%. Skema round rebound memberikan rata-rata nilai akurasi dan nilai AUC yang lebih baik daripada skema two-stage untuk seluruh persentase delegasi. 4. Untuk delegating classifiers yang jumlah base classifier-nya lebih dari dua buah, skema iterative dengan persentase delegasi 1% dan 2% merupakan parameter terbaik.
2.3.2 Soft Classifier Classifier merupakan suatu fungsi f:E→C dimana E adalah kumpulan data yang tidak berlabel, sedangkan C adalah sejumlah c kelas/kategori. Biasanya classifier ini cukup untuk permasalahan klasifikasi dan aplikasi. Akan tetapi, beberapa aplikasi membutuhkan nilai reliability, yaitu sebuah angka yang merepresentasikan kualitas dari setiap klasifikasi. Dengan kata lain, dibutuhkan sebuah classifier yang selain dapat memberikan label kelas hasil klasifikasi untuk setiap data juga dapat memberikan estimasi reliability. Classifier jenis ini disebut dengan soft classifier. [FER03]
Istilah reliability sering juga disebut dengan confidence. Nilai confidence merupakan probabilitas bahwa label yang diberikan classifier bernilai benar dan menggambarkan kepercayaan terhadap hasil klasifikasi suatu classifier. Semakin besar nilai confidence dari suatu label kelas yang diberikan, semakin besar probabilitas kelas yang diberikan merupakan label kelas yang benar. [KHO06]
Bentuk paling umum dari soft classifier adalah probability estimator, yaitu sebuah model yang mengestimasi probabilitas pi(e) untuk setiap anggota di dalam kelas i ∈ C untuk setiap data e ∈ E. Sebuah decision tree dapat dengan mudah diubah menjadi sebuah probability estimator dengan menggunakan frekuensi kelas absolut untuk setiap daun yang ada pada pohon tersebut. Sebagai contoh, jika sebuah daun
II-12 mempunyai nilai frekuensi absolut n1, n2, ..., ni (didapatkan dari training set) maka estimasi probabilitas untuk daun tersebut dapat dihitung dengan menggunakan rumus sebagai berikut (II-9). [FER03] pi =
ni ∑ ni
(II-9)
2.3.3 Probability Estimator Tree Untuk decision tree classifier, nilai confidence ditentukan per daun. Banyaknya nilai confidence yang mungkin pada suatu pohon sama dengan banyaknya daun pada pohon tersebut. Nilai confidence, p, diestimasi dengan menggunakan distribusi data latih dari suatu daun dengan rumus berikut ini.
pi =
Ni +1 N +c
(II-10)
dengan Ni adalah jumlah data latih yang berlabel kelas i pada suatu daun, N adalah jumlah total data latih pada daun, dan c adalah jumlah kelas. [KHO06]
Decision tree yang setiap daunnya terdapat distribusi probabilitas setiap kelas disebut probability estimator tree (PET). Proses klasifikasi pada PET sama dengan proses klasifikasi pada decision tree, yaitu dengan melakukan penelusuran pohon mulai dari akar hingga mencapai daun. Jalur penelusuran ditentukan oleh jawaban setiap pertanyaan pada simpul yang bukan daun. Setelah mencapai daun, kelas yang diberikan sebagai hasil klasifikasi adalah kelas yang memiliki probabilitas terbesar pada daun tersebut. [KHO06]
Salah satu contoh dari PET dapat dilihat pada Gambar II-4. PET ini terdiri dari 5 buah daun, yaitu D1, D2, D3, D4, dan D5. Pada setiap daun, baris pertama merupakan keseluruhan nilai kelas yang ada, baris kedua menunjukkan jumlah data latih yang dimiliki masing-masing kelas pada daun tersebut, dan pada baris terakhir merupakan nilai distribusi data latih untuk masing-masing kelas tersebut.
overcast
II-13
Gambar II-4 Contoh PET
2.3.4 Cautious Classifier Pada beberapa area, sebuah classifier yang memilih untuk abstain dalam melakukan klasifikasi ketika classifier tersebut tidak merasa yakin dapat menghasilkan keputusan yang benar dianggap lebih baik daripada sebuah greedy classifier atau classifier lengkap yang selalu memberikan keputusan. Cautious classifier adalah suatu classifier yang akan memberikan keputusan (memberikan hasil klasifikasi)
jika
classifier tersebut merasa yakin dengan keputusannya dan memilih untuk abstain jika classifier tersebut tidak merasa yakin. Dengan kata lain, cautious classifier merupakan fungsi parsial. [FER04]
Jika classifier lengkap didefinisikan sebagai fungsi f:E→C, dengan E adalah himpunan data yang tidak berlabel, dan C adalah himpunan c kelas/kategori yang telah ditentukan sebelumnya. Secara formal, cautious classifier didefinisikan sebagai fungsi d:E→C’, dimana C’= C∪{⊥}, dan ⊥ adalah kelas unknown. Jika cautious classifier memberikan label klasifikasi ⊥ untuk suatu data, hasil klasifikasi ini disebut abstain. Hal ini terjadi jika hasil klasifikasi mempunyai nilai confidence lebih kecil dari nilai batas ambang yang telah ditentukan. Dikarenakan cautious classifier tidak dapat memberikan label untuk beberapa data, maka cautious classifier merupakan fungsi parsial. [KHO06]
II-14 Berikut ini adalah aturan untuk proses klasifikasi yang dilakukan oleh cautious classifier : IF fCONF(e)> τ THEN prediksi fCLASS(e) ELSE abstain
dengan fCONF(e) adalah fungsi yang menghasilkan nilai confidence dari prediksi yang dilakukan oleh classifier f untuk data e, fCLASS(e) adalah fungsi yang menghasilkan label kelas yang diberikan oleh classifier f untuk data e, dan τ adalah nilai batas ambang yang dimiliki oleh cautious classifier. [FER04]
Sebuah soft classifer dapat dikonversi menjadi cautious classifier dengan menentukan nilai batas ambang confidence. Secara umum, aturan konversinya adalah sebagai berikut: [KHO06] confidence ← max(pi) IF confidence ≥ τ THEN kelas ← argmax(pi) ELSE kelas ← ⊥
2.4 Multi-Classifiers Multi-classifiers atau biasa disebut dengan ensemble classifiers atau classifier committees adalah suatu jenis classifier yang terdiri dari beberapa buah base classifier. Keuntungan yang didapat dengan menggunakan ensemble classifiers adalah meningkatnya efektifitas dan ketahanan dari tidak terjadinya overfitting [ESP06].
Berdasarkan tipe classifier yang membentuknya, ada dua kelompok ensemble classfiers yaitu homogenous ensembles dan heterogenous ensembles. homogenous ensembles menggunakan beberapa buah base classifier yang bertipe sama, tetapi masing-masing base classifier dilatih dengan subset subsample yang berbeda-beda dari keseluruhan dataset. Teknik subsampling yang dapat digunakan diantaranya adalah bagging dan boosting. Sedangkan heterogenous ensembles menggunakan beberapa buah base classifier yang berbeda tipe. [KHO06]
II-15
2.4.1
Bagging
Bagging merupakan sebuah metode bootstrap ensemble yang membuat masingmasing base classifier yang membentuknya dengan cara melatih setiap base classifier tersebut menggunakan pembagian kembali training set secara acak. Training set untuk setiap base classifier dibuat dengan cara mengacak, dengan melakukan penggantian, N buah data dimana N adalah jumlah training set secara keseluruhan. Dikarenakan bagging menggunakan resamples training set maka akan terdapat beberapa buah data yang akan berulang, sedangkan yang lain akan dihilangkan [OPI99]. Contoh pembagian training set pada bagging dapat dilihat pada Tabel II-1. Algoritma pembelajaran pada bagging dapat dilihat pada Gambar II-5.
Tabel II-1
Contoh pembagian data dengan menggunakan Bagging [OPI99]
Data asli Training-set-1 Training-set-2 Training-set-3 Training-set-4
1, 2, 3, 4, 5, 6, 7, 8 2, 7, 8, 3, 7, 6, 3, 1 7, 8, 5, 6, 4, 2, 7, 1 3, 6, 2, 7, 5, 6, 2, 2 4, 5, 1, 4, 6, 4, 3, 8
Untuk melakukan klasifikasi sebuah data x, setiap base classifier akan melakukan klasifikasi data tersebut. Hasil klasifikasi dari seluruh base classifier lalu disimpan. Kemudian data x akan diberi label kelas yang jumlahnya paling banyak dari hasil klasifikasi seluruh base classifier. [QUI96B]
Bagging efektif pada algoritma pembelajaran yang tidak stabil dimana perubahan kecil yang terdapat di dalam training set mengakibatkan perubahan yang besar di dalam prediksi. Bagging hampir selalu lebih akurat dibandingkan dengan classifier tunggal, akan tetapi bagging terkadang kurang akurat dibandingkan dengan boosting. Bagging lebih tahan terhadap noise dibandingkan dengan boosting. [OPI99]
II-16 Input: training set S, Inducer I, integer T (number of bootstrap samples) 1. for i = 1 to T { 2. S’ = boostrap sample from S (i.i.d sample with replacement) 3. Ci = I(S’) 4. } 5. C*(x) =
arg max arg max y∈Y
∑1
(the most often predicted label y)
i:Ci ( x ) = y
Output: classifier C*
Gambar II-5 Algoritma Bagging [KOH98]
2.4.2
Boosting
Fokus dari metode ini adalah untuk
menghasilkan serangkaian base classifiers.
Training set yang digunakan untuk setiap base classifier dipilih berdasarkan performansi dari classifier sebelumnya. Di dalam boosting, sampel yang tidak diprediksikan dengan benar oleh classifier di dalam rangkaian akan dipilih lebih sering dibandingkan dengan sampel yang telah diprediksikan dengan benar. Dengan demikian, boosting mencoba menghasilkan base classifier baru yang lebih baik untuk memprediksikan sampel yang pada base classifier sebelumnya memiliki performansi yang buruk. Salah satu contoh pembentukan training set pada boosting dapat dilihat pada Tabel II-2 dengan asumsi data 1 susah diprediksikan dengan benar. [OPI99]
Tabel II-2
Contoh pembagian data dengan menggunakan Boosting [OPI99]
Data asli Training-set-1 Training-set-2 Training-set-3 Training-set-4
1, 2, 3, 4, 5, 6, 7, 8 2, 7, 8, 3, 7, 6, 3, 1 1, 4, 5, 4, 1, 5, 6, 4 7, 1, 5, 8, 1, 8, 1, 4 1, 1, 6, 1, 1, 3, 1, 5
Dalam pembelajaran classifiert, setiap data latih
diberi bobot, yang merepresentasikan seberapa sulit mendapatkan prediksi yang tepat untuk data ini bagi classifier1, ...., classifiert-1. Lalu, classifiert akan diaplikasikan ke data latih, dan bobot akan diperbaharui. Jika prediksi data latih tersebut benar, bobot akan dikurangi, dan sebaliknya jika terjadi salah klasifikasi, bobot akan ditambah [KHO06]. Salah satu contoh algoritma boosting AdaBoost.M1 yang dapat dilihat pada Gambar II-6.
II-17
Algorithm AdaBoost.M1 Input : sequence of m examples {(x1, y1),...,(xm, ym)} with labels yi ∈ Y = {1,...,k} weak learning algorithm WeakLearn integer T specifying number of iterations Initialize D1(i) = 1/m for all i. Do For t = 1, 2,..., T: 1. Call WeakLearn, providing it with the distribution Dt. 2. Get back a hypothesis ht : X → Y. 3. Calculate the error of ht
:
εt =
∑ D (i)
i:ht ( xi ) ≠ yi
t
If εt > 1/2, then set T = t -1 and abort loop. 4. Set β t = ε t /(1 − ε t ) . 5. Update distribution Dt :
Where Zt is a normalization constant (chosen so that Dt+1 will be a distribution). Output : the final hypothesis :β
h fin ( x) = arg max y∈Y
∑
t :ht ( x ) = y
log
1
βt
Gambar II-6 Algoritma AdaBoost.M1 [FRE96] Pada boosting, classifier akhir juga berupa agregasi classifier dengan voting. Akan tetapi, setiap classifier mempunyai bobot yang merupakan suatu fungsi dari nilai akurasinya. [QUI96B]
