Pokok Bahasan
1. Konsep Klasifikasi
2. Linear dan Non-Linear Classifier
3. Algoritma Klasifikasi:
o Extreme Learning Machine (ELM) Untuk Regresi
Vs ELM Untuk Klasifikasi
o Support Vector Machine (SVM) Linear dan Non-
Linear
2 Kelas (Binary SVM)
> 2 Kelas (OAA-SVM, OAO-SVM, BDT-SVM,
DAG-SVM)
4. Studi Kasus
5. Tugas
Konsep Klasifikasi (Just Review)
• Prediksi berbeda dengan klasifikasi (dalam machine
learning, klasifikasi dianggap sebagai salah satu jenis
dari prediksi).
• Klasifikasi digunakan untuk memprediksi label
kelas/kategori.
• Klasifikasi dapat dibagi lagi menjadi dua macam, yaitu:
– supervised classification (Klasifikasi) dan
– unsupervised classification (Clustering sudah
dibahas pada pertemuan sebelumya)
• Prediksi versus Peramalan (Jangka waktu merupakan
kata kunci untuk membedakan antara prediksi dan
peramalan)
Konsep Klasifikasi (Just Review)
• Supervised Learning (Pembelajaran yang terawasi,
yaitu terdapat proses training dan testing):
o Regresi: untuk memprediksi nilai yang sifatnya kontinu.
o Klasifikasi: untuk memprediksi kelas atau label data dan
bersifatnya diskrit.
Property
Supervised
Classification
(Klasifikasi)
Regresi
Keluaran
berupa
Diskrit (label
kelas)
Kontinu
(angka)
Target
Pencarian
Decision
Boundary
“best fit line”
Nilai
Evaluasi
Akurasi MSE, MAE,
MAPE,
RMSE, ..
ELM Untuk Regresi (Just Review)
Misalkan diketahui, data training (terdapat 3 fitur dan
single target) sebagai berikut (Lihat Materi Pert. 6):
1 1 1 1
1 0 1 1
1 1 0 1
1 1 0 2
X = 0 1 0 2
0 0 0 2
0 1 0 3
1 1 0 3
0 0 0 3
Input
LayerHidden
Layer
Output
Layer
fitur ke-1
fitur ke-2
fitur ke-k
ijk
Hasil
Prediksi
6. Menghitung Y prediksi
7. Hitung MAPE
Pada proses training, didapatkan hasil testing
menggunakan data training sendiri masih
memiliki error MAPE sebesar 30.11
Penyelesaian:
Y =
.ˆ HY
1.48
0.91
1.90
1.90
2.75
2.17
2.75
1.90
2.17
Y
9
1
|100ˆ
|9
1 N
i i
ii
y
yy
NMAPE
11.30
ELM Untuk Klasifikasi
Misalkan diketahui, data training (terdapat 3 fitur dan
single target) sebagai berikut:
1 1 1 1
1 0 1 1
1 1 0 1
1 1 0 2
X = 0 1 0 2
0 0 0 2
0 1 0 3
1 1 0 3
0 0 0 3
6. Menghitung Y prediksi
7. Hitung Akurasi
Pada proses training, didapatkan hasil testing
menggunakan data training sendiri masih
memiliki nilai akurasi sebesar 55.56%
Penyelesaian:
Y =.ˆ HY
1.48
0.91
1.90
1.90
2.75
2.17
2.75
1.90
2.17
Y
Y sebagai kelas aktual, yaitu
terdapat kelas 1, 2, dan 3
Kelas Aktual
Kelas Prediksi
1.48 1 0.48 0.52 1.52 1
0.91 1 0.09 1.09 2.09 1
1.90 1 0.90 0.10 1.10 2
1.90 2 0.90 0.10 1.10 2
2.75 2 1.75 0.75 0.25 3
2.17 2 1.17 0.17 0.83 2
2.75 3 1.75 0.75 0.25 3
1.90 3 0.90 0.10 1.10 2
2.17 3 1.17 0.17 0.83 2
Y 1ˆ Y 2ˆ Y 3ˆ Y
%56.55%100 x 9
5
trainNAkurasi
ELM Untuk Regresi (Just Review)
Misalkan diketahui, data testing sebagai berikut (Lihat
Materi Pert. 6):
1 1 1 1
1 0 1 1
1 1 0 1
1 1 0 2
X = 0 1 0 2
0 0 0 2
0 1 0 3
1 1 0 3
0 0 0 3
Y =
1 0 1
Xtest = 1 1 0
0 1 0
Ytest =
Data training:
Data testing:
113
2. Htung matrik output hidden H = 1/(1+exp(-Hinit))
3. Menghitung Y prediksi
, diketahui , maka
4. Hitung MAPE
Pada proses testing, didapatkan hasil prediksi
dengan error MAPE sebesar 36.0048
Penyelesaian:
0.43 0.55 0.40
0.45 0.45 0.50
0.55 0.50 0.57H =
.ˆ HY 13.06
-7.74
-0.98
Y0.91
1.90
2.75
0048.36|100ˆ
|3
1 3
1
N
i i
ii
y
yy
NMAPE
ELM Untuk Klasifikasi
Misalkan diketahui, data testing sebagai berikut:
1 1 1 1
1 0 1 1
1 1 0 1
1 1 0 2
X = 0 1 0 2
0 0 0 2
0 1 0 3
1 1 0 3
0 0 0 3
Y =
1 0 1
Xtest = 1 1 0
0 1 0
Ytest =
Data training:
Data testing:
113
3. Menghitung Y prediksi
, diketahui , maka
4. Hitung Akurasi
Pada proses testing, didapatkan nilai akurasi
sebesar 66.67%
Penyelesaian:
.ˆ HY 13.06
-7.74
-0.98
Y0.91
1.90
2.75
Kelas Aktual
Kelas Prediksi
0.91 1 0.09 1.09 2.09 1
1.90 1 0.90 0.10 1.10 2
2.75 3 1.75 0.75 0.25 3
Y 1ˆ Y 3ˆ Y
%67.66%100 x 3
2
testNAkurasi
Y sebagai kelas aktual, yaitu
terdapat kelas 1, 2, dan 3
Ytest sebagai kelas
aktual, yaitu terdapat
kelas 1 dan 3
2ˆ Y
Support Vector Machine (SVM)
SVM Linear
SVM Non-Linear
Support Vector kelas -1
Support Vector kelas +1
(w.x) + b = -1
(w.x) + b = +1
(w.x) + b = 0
w
y = +1
y = -1
2
2
2
1
2
w
2 Margin
ww
Jarak titik (xi) ke Hyperplane :
w
1
w
by ,, i
wxxbwd i
i
w
1
w
y ,, i i
i
xfxbwd
Input Space x High-dimensional Feature Space Φ(x)
Hyperplane
Support Vector Machine (SVM)
SVM Non-Linear
(terdapat data
noise, outliers, atau
memang sebaran
datanya secara
alami non-linear).
Slack variables ξi
dapat ditambahkan
untuk mentoleransi
adanya mis-
classification yang
sulit dipecahkan
karena misal, ada
data noise.
x1
x2
Kelas +1
Kelas -1
12
Support Vector Machine (SVM)
Langkah-langkah dalam SVM:
1. Data dan kelas dimana
2. Melakukan proses training untuk mendapatkan nilai 𝛼i dengan
menggunakan algoritma Sequential Training SVM
3. Hitung w dan b dan Hasil klasifikasi sign(f(x))
1,1iy
in
i
ii xyw
1
m
i
iii
m
i
iii
m
i
iii
m
i
iii
m
i
iii
m
i
iii
xxKyxxKyb
xxyxxyb
xxyxxyb
xwxwb
11
11
11
),(),(2
1
)()()()(2
1
2
1
].[2
1
bxxKyxf
bxxyxf
bxxyxf
bxwxf
m
i
iii
m
i
iii
m
i
iii
1
1
1
),()(
)()()(
)(
)(
n
iii yx1
,
dimana m adalah jumlah support vector/titik data yang memiliki αi > 0
Support Vector Machine (SVM)
Algoritma Sequential Training SVM:
1. Inisialisasi nilai 𝛼i = 0, λ, γ (learning rate), C, ε (epsilon), IterMax,
parameter kernel (jika ada) dan hitung matrik Dij untuk i, j = 1,
..., n. Dimana n adalah banyaknya data training.
2. Melakukan iterasi untuk perhitungan:
a.
b.
c.
3. Cek kondisi berhenti ketika memenuhi kondisi,
atau telah mencapai IterMax, jika tidak, maka
kembali pada langkah ke-2
Note: Jika anda sudah paham SVR, maka anda akan mudah paham SVM di atas.
)),(( 2 jijiij xxKyyD
n
j
ijji DE1
}],),1(min{max[ iiii CE
|)max(| i
iii
Support Vector Machine (SVM)
Algoritma Sequential Training SVM untuk data dengan 2
kelas (Binary SVM atau SVM Biner):
Kelas jual = +1, dan beli = -1
1. Inisialisasi nilai 𝛼i = 0, λ = 4.32, γ (learning rate) = 0.00406,
C = 100, ε (epsilon) = 0.0004, IterMax=1, σ = 0.7 dan hitung
matrik Dij
No Tgl/Bln/Thn F1 F2 F3 F4 Kelas
1 9 Juli 2015 13338 13356 13332 13331 Jual
2 10 Juli 2015 13356 13332 13331 13337 Jual
3 11 Juli 2015 13332 13331 13337 13316 Beli
4 12 Juli 2015 13331 13337 13316 13316 Beli
5 13 Juli 2015 13337 13316 13316 13316 Beli
6 14 Juli 2015 13313 13346 13347 13304 Beli
7 15 Juli 2015 13346 13347 13304 13304 Beli
8 16 Juli 2015 13347 13304 13304 13304 Beli
Diketahui data training dan testing:
Data Latih
Data Uji
𝛼i
0
0
0
0
0
Support Vector Machine (SVM)
Algoritma Sequential Training SVM untuk data dengan 2
kelas (Binary SVM):
Kelas jual = +1, dan beli = -1
Diketahui data training dan testing (hasil normalisasi dengan Xmin= 9634 Xmax= 14728):No Tgl/Bln/Thn F1 F2 F3 F4 Kelas
1 9 Juli 2015 0.727129957 0.730663526 0.725952101 0.725755791 1
2 10 Juli 2015 0.730663526 0.725952101 0.725755791 0.726933647 1
3 11 Juli 2015 0.725952101 0.725755791 0.726933647 0.72281115 -1
4 12 Juli 2015 0.725755791 0.726933647 0.72281115 0.72281115 -1
5 13 Juli 2015 0.726933647 0.72281115 0.72281115 0.72281115 -1
No Tgl/Bln/Thn F1 F2 F3 F4 Kelas
1 14 Juli 2015 0.72281115 0.72281115 0.72281115 0.730074598 -1
2 15 Juli 2015 0.72281115 0.72281115 0.730074598 0.722222222 -1
3 16 Juli 2015 0.72281115 0.730074598 0.722222222 0.728700432 -1
0.727129963414728
)963413338('
x
minmax
min )('
xx
xxx
Support Vector Machine (SVM)
Algoritma Sequential Training SVM untuk data dengan 2
kelas (Binary SVM):
1. Inisialisasi 𝛼i = 0, λ = 4.32, γ (learning rate) = 0.00406, C = 100, ε
(epsilon) = 0.0004, IterMax=2, σ = 0.7 dan matrik Dij
)),(( 2 jijiij xxKyyD
Dij 1 2 3 4 5
1 19.6624000000 19.6623631542 -19.6623641766 -19.6623649631 -19.6623181311
2 19.6623631542 19.6624000000 -19.6623585535 -19.6623482512 -19.6623495488
3 -19.6623641766 -19.6623585535 19.6624000000 19.6623812034 19.6623728276
4 -19.6623649631 -19.6623482512 19.6623812034 19.6624000000 19.6623812427
5 -19.6623181311 -19.6623495488 19.6623728276 19.6623812427 19.6624000000
1 1 -1 -1 -1
1 1 1 -1 -1 -1
1 1 1 -1 -1 -1
-1 -1 -1 1 1 1
-1 -1 -1 1 1 1
-1 -1 -1 1 1 1
54219.6623631
32.4)7.0(2
103.61095exp1x1 2
2
-5
2,1
D
Support Vector Machine (SVM)
Algoritma Sequential Training SVM untuk data dengan 2
kelas (Binary SVM):
2. Melakukan iterasi untuk perhitungan (iterasi =1):
a.
b.
c.
01551441331221111
1
DDDDDE
DEn
j
ijji
00406.0}0100],0),01(00406.0min{max[
}100],),1(00406.0min{max[
}],),1(min{max[
1
1111
E
CE iiii
00406.000406.00111
iii
i Ei1 0
2 0
3 0
4 0
5 0
i
1 0.00406
2 0.00406
3 0.00406
4 0.00406
5 0.00406
i
1 0.00406
2 0.00406
3 0.00406
4 0.00406
5 0.00406
Support Vector Machine (SVM)
Algoritma Sequential Training SVM untuk data dengan 2
kelas (Binary SVM):
3. Cek kondisi berhenti ketika memenuhi kondisi,
Karena iterasi = IterMax (Stop), misalkan jika ,
dan iterasi < IterMax, maka iterasi = iterasi + 1, lalu kembali
pada langkah ke-2
Hitung b
i
1 0.00406
2 0.00406
3 0.00406
4 0.00406
5 0.00406
|)max(| i
m
i
iii
m
i
iii xxKyxxKyb11
),(),(2
1
Support Vector Machine (SVM)
Hitung b
Set nilai x+ dan x- dari masing kelas yang memiliki nilai
𝛼i tertinggi, yaitu dan karena semua
nilai 𝛼i > 0, maka banyaknya support vector (m) =
banyak data training, yaitu 5
m
i
iii
m
i
iii xxKyxxKyb11
),(),(2
1
31 xxxx
5
1
3
5
1
1
11
),(),(2
1
),(),(2
1
i
iii
i
iii
m
i
iii
m
i
iii
xxKyxxKyb
xxKyxxKyb
Support Vector Machine (SVM)
Hitung b (dengan fungsi Kernel, w langsung bisa di by pass)
5
1
3
5
1
1
11
),(),(2
1
),(),(2
1
i
iii
i
iii
m
i
iii
m
i
iii
xxKyxxKyb
xxKyxxKyb
950.00405952),(..),(),( 15551111
5
1
1
xxKyxxKyxxKyi
iii
710.00406012),(..),(),( 35553111
5
1
3
xxKyxxKyxxKyi
iii
8297524990.00405982
2708165399-0.00406019513395990.00405952-2
1
b
Support Vector Machine (SVM)
Hasil klasifikasi sign(f(x))
Misal menghitung hasil klasfikasi dari uji ke-1, maka
tentukan sign(f(xtest1))
bxxKyxfm
i
iii 1
),()(
8297524990.00405982),()(5
1
11 i
iii xtestxKyxtestf
No Tgl/Bln/Thn F1 F2 F3 F4 Kelas
1 14 Juli 2015 0.72281115 0.72281115 0.72281115 0.730074598 -1
2 15 Juli 2015 0.72281115 0.72281115 0.730074598 0.722222222 -1
3 16 Juli 2015 0.72281115 0.730074598 0.722222222 0.728700432 -1
K(xi,xtest1) xtest1
x1 0.999888955584422
x2 0.999908104359568
x3 0.999909913096674
x4 0.999919979151857
x5 0.999928826350961
388961603661634-0.0000000
8297524990.004059824433414133-0.0040598)( 1
xtestf
Hasil kelas prediksi xtest1sign(f(xtest1)) = -1
Maka xtest1 masuk kelas beli (true).
Support Vector Machine (SVM)
Algoritma Sequential Training SVM untuk data dengan >
2 kelas, berikut beberapa strategi yang bisa digunakan:
o One Against All (OAA) oleh (Cortes and Vapnik, 1995)
o One-Against-One (OAO)
o Binary Decision Tree (BDTSVM)
o Directed Acrilyc Graph SVM (DAGSVM)
𝑦𝑖 = 1 𝑦𝑖 = −1 Hipotesis
Kelas 1 Bukan kelas 1 𝑓1 𝑥 = 𝑤1 𝑥 + 𝑏1
Kelas 2 Bukan kelas 2 𝑓2 𝑥 = 𝑤2 𝑥 + 𝑏2
Kelas 3 Bukan kelas 3 𝑓3 𝑥 = 𝑤3 𝑥 + 𝑏3
SVM Biner dengan Metode One-Against-All
Jika anda sudah menguasai
Binary SVM (SVM Biner),
maka kemungkinan besar
anda akan sangat mudah
menguasai 4 strategi
disamping
Support Vector Machine (SVM)
Algoritma Sequential Training SVM untuk data dengan >
2 kelas, berikut beberapa strategi yang bisa digunakan:
o One Against All (OAA)
o One-Against-One (OAO) oleh (Fridman, 1996)
o Binary Decision Tree (BDTSVM)
o Directed Acrilyc Graph SVM (DAGSVM)
Pair-wise
Misal
Hasil Voting
Pair-wise. k(k-1)/2
Misal banyaknya kelas (k) = 4
Support Vector Machine (SVM)
o One-Against-One (OAO) oleh (Fridman, 1996)
𝑦𝑖 = 1 𝑦𝑖 = −1 Hipotesis
Kelas 1 Kelas 2 𝑓12 𝑥 = (𝑤12)𝑥 + 𝑏12
Kelas 1 Kelas 3 𝑓13 𝑥 = (𝑤13)𝑥 + 𝑏13
Kelas 1 Kelas 4 𝑓14 𝑥 = (𝑤13)𝑥 + 𝑏14
Kelas 2 Kelas 3 𝑓23 𝑥 = (𝑤23)𝑥 + 𝑏23
Kelas 2 Kelas 4 𝑓24 𝑥 = (𝑤24)𝑥 + 𝑏24
Kelas 3 Kelas 4 𝑓34 𝑥 = (𝑤34)𝑥 + 𝑏34
SVM Biner dengan Metode One-Against-One
Support Vector Machine (SVM)
o Binary Decision Tree (BDTSVM) oleh (Gjorgji M., dkk, 2008)
SVM
SVM
SVM
SVM
SVM SVM6
2 3 4 7 1 5
1,2,3,4,5,6,7
2,3,4,7 1,5,6
1,52,3 4,7
Langkah membuat Tree untuk BDTSVM :
1. Tentukan titik pusat
data (center data)
tiap kelas.
2. Buat Matrik Jarak
(Euclidean) antar titik
pusat data.
3. Cari Jarak Terjauh
untuk pemisahan kelas
(y = +1 dan y = -1)
4. Tetapkan kelas dari
center data dengan
jarak terdekat, pada
kelas (y = +1) atau
kelas (y = -1) dari hasil
pemisahan pada
langkah (3).
Tree pada BDTSVM
Support Vector Machine (SVM)
o Binary Decision Tree (BDTSVM) oleh (Gjorgji M., dkk, 2008)
𝑦𝑖 = 1 𝑦𝑖 = −1 Hipotesis
Kelas 2,3,4,7 Kelas 1, 5, 6 𝑓(2,3,4,7)(1,5,6) 𝑥 = (𝑤(2,3,4,7)(1,5,6))𝑥 + 𝑏(2,3,4,7)(1,5,6)
Kelas 2,3 Kelas 4,7 𝑓(2,3)(4,7) 𝑥 = (𝑤(2,3)(4,7))𝑥 + 𝑏(2,3)(4,7)
Kelas 1,5 Kelas 6 𝑓(1,5)(6) 𝑥 = (𝑤(1,5)(6))𝑥 + 𝑏(1,5)(6)
Kelas 2 Kelas 3 𝑓23 𝑥 = (𝑤23)𝑥 + 𝑏23
Kelas 4 Kelas 7 𝑓47 𝑥 = (𝑤47)𝑥 + 𝑏47
Kelas 1 Kelas 5 𝑓15 𝑥 = (𝑤15)𝑥 + 𝑏15
Support Vector Machine (SVM)
o Directed Acrilyc Graph SVM (DAGSVM) oleh (C. W. Hsu and
C. J. Lin, 2002)
1 vs 4
2 vs 4 1 vs 3
3 vs 4 2 vs 3 1 vs 2
1234
234
123
34
23
12
Node 1
Node 2 Node 3
Node 4 Node 5 Node 6
Kelas 4 Kelas 3 Kelas 2 Kelas 1
Tugas Kelompok
1. Jelaskan perbedaan antara regresi dengan klasifikasi!
2. Jelaskan perbedaan antara Underfitting, Just right, dan Overfitting dalam sudut pandang regresi
dan klasifikasi!
3. Jelaskan pengertian dari Support Vector, dan Lagrange Multipier pada SVM!
4. Berdasarkan pada slide sebelumnya yaitu tentang Algoritma Sequential Training SVM untuk
data dengan 2 kelas (Binary SVM), jika fungsi kernel RBF digantikan dengan fungsi kernel
polynomial (c=1 dan d=2). Tentukan besarnya nilai akurasi dari data testing!
5. Selesaikan kasus berikut menggunakan OAOSVM, atau OAASVM atau BDTSVM, atau
DAGSVM (Pilih salah satu), dengan nilai parameter 𝛼i = 0, λ = 4.32, γ (learning rate) = 0.00406,
C = 100, ε (epsilon) = 0.0004, IterMax=2, dengan kernel RBF (σ = 0.7). Tentukan besarnya nilai
akurasi dari data testing!
10 1 1 True
5 2 1 True
2 2 3 True
1 1 1 False
X = 3 2 3 Flase
4 6 9 False
0 14 1 None
1 10 0 None
7 8 0 None
Y =
3 0 2
Xtest = 1 1 5
0 1 4
Ytest =
Data training: Data testing:
TrueTrueNone
Kelas Aktual
Kelas Aktual