Pengenalan Pola/

Pattern Recognition

Support Vector Machine (SVM)

 Pokok Pembahasan
1. Support Vector Machine (SVM)
✔ Pengertian SVM
✔ Model SVM
✔ Visualisasi SVM
✔ Karakteristik SVM
2. Case Study
3. Latihan Individu & Diskusi Kelompok
 Support Vector Machine
• Konsep Klasifikasi dengan Support Vector Machine (SVM) adalah
mencari hyperplane terbaik yang berfungsi sebagai pemisah dua
kelas data.
• Ide sederhana dari SVM adalah memaksimalkan margin, yang
merupakan jarak pemisah antara kelas data.
• SVM mampu bekerja pada dataset yang berdimensi tinggi dengan
menggunakan kernel trik.
• SVM hanya menggunakan beberapa titik data terpilih yang
berkontribusi (Support Vector) untuk membentuk model yang akan
digunakan dalam proses klasifikasi.
• Macam-Macam Training untuk SVM :
• Chunking (Quadratic Programming).
• Osuna (Dekomposisi).
• Sequential Minimum Optimation (SMO).
• Least Square (LS) dan lainnya.
 Model SVM
• Titik data : xi = {x1,x2,….,xn} ϵ Rn
• Kelas data : yi ϵ {-1,+1}
• Pasangan data dan kelas :
• Maksimalkan fungsi berikut :

• Hitung nilai w dan b :

• Fungsi keputusan klasifikasi sign(f(x)) :

Keterangan :
N (banyaknya data), n (dimensi data atau banyaknya fitur), Ld (Dualitas
Lagrange Multipier), αi (nilai bobot setiap titik data), C (nilai konstanta), m
(jumlah support vector/titik data yang memiliki αi > 0), K(x,xi) (fungsi kernel).
 Model SVM (Cont.)
• Beberapa Macam Fungsi Kernel Support Vector Machine (SVM) :
No Nama Kernel Definisi Fungsi
1 Linier K(x,y) = x.y
2 Polinomial of degree d K(x,y) = (x.y)d
3 Polinomial of degree up to d K(x,y) = (x.y + c)d
4 Gaussian RBF

5 Sigmoid (Tangen Hiperbolik)

6 Invers Multi Kuadratik

7 Additive
• Kernel Linier digunakan ketika data yang akan diklasifikasi dapat terpisah
dengan sebuah garis/hyperplane.
• Kernel non-Linier digunakan ketika data hanya dapat dipisahkan dengan
garis lengkung atau sebuah bidang pada ruang dimensi tinggi (Kernel Trik,
No.2 sampai 6).
 Visualisasi SVM
• Linier Kernel :
rgin (w.x) + b = +1
ma

Hyp
(w.x) + b = -1

erp
lane
y = +1 Support Vector kelas -1
Support Vector kelas +1
y = -1 w
Jarak titik (xi) ke Hyperplane :

(w.x) + b = 0
• Non-Linier Kernel :
 Karakteristik SVM
• Karakteristik SVM :
– SVM memerlukan proses pelatihan dengan menyimpan hasil
support vektor yang didapatkan untuk digunakan kembali pada
saat proses prediksi/testing.
– SVM selalu memberikan model yang sama dan solusi yang
sama dengan margin maksimal.
– SVM dapat memisahkan data yang distribusi kelasnya bersifat
linier maupun non linier.
– SVM tidak dipengaruhi oleh dimensi data yang tinggi, sehingga
tidak ada proses reduksi dimensi didalamnya.
– Memori yang digunakan dalam SVM dipengaruhi oleh
banyaknya data, bukan besarnya dimensi data.
 Contoh Studi Kasus
• Contoh SVM Linier pada dataset berikut :
Tentukan Hyperplanenya !
x1 x2 Kelas (y) Support Vector (SV)
1 1 1 1
1 -1 -1 1
-1 1 -1 1
-1 -1 -1 0

• Bentuk Visualisasi data :

 Contoh Studi Kasus 1 (Cont.)
• Contoh SVM Linier :
x1 x2 Kelas (y)
1 1 1
1 -1 -1
-1 1 -1
-1 -1 -1

– Karena ada dua fitur (x1 dan x2), maka w juga akan memiliki 2 fitur (w1 dan w2).
– Formulasi yang digunakan adalah sebagai berikut :
• Meminimalkan nilai :

• Syarat :
 Contoh Studi Kasus 1 (Cont.)
– Karena ada dua fitur (x1 dan x2), maka w juga akan memiliki 2 fitur (w1 dan w2).
– Formulasi yang digunakan adalah sebagai berikut :
• Meminimalkan nilai margin :

• Syarat :

Sehingga didapatkan beberapa persamaan berikut :

 Contoh Studi Kasus 1 (Cont.)
Didapatkan beberapa persamaan berikut :
• Menjumlahkan persamaan (1) dan (3) :

• Menjumlahkan persamaan (1) dan (2) :

• Menjumlahkan persamaan (2) dan (3) :

Sehingga didapatkan persamaan hyperplane :

w1x1 + w2x2 + b = 0
x1 + x2 - 1 = 0
x2 = 1 - x1
 Contoh Studi Kasus 1 (Cont.)
Visualisasi garis hyperplane (sebagai fungsi klasifikasi) :
w1x1 + w2x2 + b = 0
x1 + x2 - 1 = 0 x2 = 1 - x1
x2 = 1 - x1

x1 x2 = 1 – x 1
-2 3
-1 2
0 1
1 0
2 -1
 Contoh Studi Kasus 1 (Cont.)
Misalkan diketahui data uji/ data testing berikut :
Diketahui : f(x) = x1 + x2 – 1
Kelas = sign(f(x)) x2 = 1 - x1

Data Uji Hasil Klasifikasi

No
x1 x2 Kelas = sign(x1 + x2 - 1)

1 1 5 sign (1 + 5 - 1) = +1
2 -1 4 sign (-1 + 4 - 1) = +1
3 0 7 sign (0 + 7 - 1) = +1
4 -9 0 sign (-9 + 0 - 1) = -1
5 2 -2 sign (2 - 2 - 1) = -1
 Contoh Studi Kasus 2
• Contoh SVM Non Linier pada dataset berikut :
x1 x2 Kelas (y) Support Vector (SP)
1 1 -1 1
1 -1 1 1
-1 1 1 1
-1 -1 -1 1

• Bentuk Visualisasi data :

 Contoh Studi Kasus 2 (Cont.)
• Contoh SVM Non Linier :
x1 x2 Kelas (y)
1 1 -1
1 -1 1
-1 1 1
-1 -1 -1

– Karena ada dua fitur (x1 dan x2), dan kelompok datanya tidak linear, maka
digunakan fungsi kernel. Misal menggunakan fungsi kernel polynomial ordo 2,
yaitu :
K(x,y) = (x.y + c)d dengan c = 1 dan d = 2.
– Fungsi kernel dituliskan kembali menjadi berikut :
K(x,xi) = ([Link] + 1)2 dengan
– Menghitung matrik kernel K :
K(x,xi) = ᶲ(x).ᶲ(xi)
 Contoh Studi Kasus 2 (Cont.)
– Fungsi kernel dituliskan kembali menjadi berikut :
K(x,xi) = ([Link] + 1)2 dengan

– Menghitung matrik kernel K(x,xi) = ᶲ(x).ᶲ(xi)

– Misal, Menghitung K(u,z) : dengan u=(1,1) dan z=(1,-1)
k(U=(1,1),Z=(1,-1)) = (((U1.Z1)+(U2.Z2))+1)2 = ((U1.Z1)+(U2.Z2))2+2((U1.Z1)+(U2.Z2)).1 + 12
= (U1.Z1)2 + 2(U1.Z1)(U2.Z2) + (U2.Z2)2 + 2(U1.Z1) + 2(U2.Z2) + 1
 Contoh Studi Kasus 2 (Cont.)
– Fungsi kernel dituliskan kembali menjadi berikut :
K(x,xi) = ([Link] + 1)2 dengan

– Menghitung matrik kernel K(x,xi) = ᶲ(x).ᶲ(xi)

– Misal, Menghitung K(u,z) : dengan u=(1,1) dan z=(1,-1)
k(U=(1,1),Z=(1,-1)) = (((U1.Z1)+(U2.Z2))+1)2 = ((U1.Z1)+(U2.Z2))2+2((U1.Z1)+(U2.Z2)).1 + 12
= (U1.Z1)2 + 2(U1.Z1)(U2.Z2) + (U2.Z2)2 + 2(U1.Z1) + 2(U2.Z2) + 1
 Contoh Studi Kasus 2 (Cont.)
– Misal, Menghitung K(u,z) : dengan u=(1,1) dan z=(1,-1)
k(U=(1,1),Z=(1,-1)) = (((1.1)+(1.(-1)))+1)2 = ((1.1)+(1.(-1)))2+2((1.1)+(1.(-1))).1 + 12
= (1.1)2 + 2(1.1)(1.(-1)) + (1.(-1))2 + 2(1.1) + 2(1.(-1)) + 1
=1-2+1+2-2+1=1
 Contoh Studi Kasus 2 (Cont.)
– Menghitung matrik kernel K(x,xi) = ᶲ(x).ᶲ(x ) i
x1 K(1,1) = (x1.x1 + 1)2 = (1.1 + 1.1 +1)2 = 32 = 9
x2 K(1,2) = (x1.x2 + 1)2 = (1.1 + 1.(-1) +1)2 = 12 = 1
x1
x3 K(1,3) = (x1.x3 + 1)2 = (1.(-1) + 1.1 +1)2 = 12 = 1
x4 K(1,4) = (x1.x4 + 1)2 = (1.(-1) + 1.(-1) +1)2 = (-1)2 = 1
x1 K(2,1) = (x2.x1 + 1)2 = (1.1 + (-1).1 +1)2 = 12 = 1
x2 K(2,2) = (x2.x2 + 1)2 = (1.1 + (-1).(-1) +1)2 = 32 = 9
x2
x3 K(2,3) = (x2.x3 + 1)2 = (1.(-1) + (-1).1 +1)2 = 12 = 1
x4 K(2,4) = (x2.x4 + 1)2 = (1.(-1) + (-1).(-1) +1)2 = 12 = 1
x1 K(3,1) = (x3.x1 + 1)2 = ((-1).1 + 1.1 +1)2 = 12 = 1
x2 K(3,2) = (x3.x2 + 1)2 = ((-1).1 + 1.(-1) +1)2 = 12 = 1
X3
x3 K(3,3) = (x3.x3 + 1)2 = ((-1).(-1) + 1.1 +1)2 = 32 = 9
x4 K(3,4) = (x3.x4 + 1)2 = ((-1).(-1) + 1.(-1) +1)2 = 12 = 1
x1 K(4,1) = (x4.x1 + 1)2 = ((-1).1 + (-1).1 +1)2 = 12 = 1
x2 K(4,2) = (x4.x2 + 1)2 = ((-1).1 + (-1).(-1) +1)2 = 12 = 1
x4
x3 K(4,3) = (x4.x3 + 1)2 = ((-1).(-1) + (-1).1 +1)2 = 12 = 1
X4 K(4,4) = (x4.x4 + 1)2 = ((-1).(-1) + (-1).(-1) +1)2 = 32 = 9
 Contoh Studi Kasus 2 (Cont.)
•
9 1 1 1
1 9 1 1
1 1 9 1
1 1 1 9
 Contoh Studi Kasus 2 (Cont.)
•

dimana adalah nilai pada dimensi ke-1 pada data ke-i.

 Contoh Studi Kasus 2 (Cont.)
- Hitung nilai w dan b :

dimana adalah nilai pada dimensi ke-1 pada data ke-i.

 Contoh Studi Kasus 2 (Cont.)
– Misalkan didapatkan nilai Max Ld dengan α1 = α2 = α3 = α4 = 0.125.
Sehingga nilai Ld = 0.25.
– Hitung nilai w dan b :

Pilih salah satu Support Vector dari Kelas “+1” dan “-1” untuk menghitung nilai b.
 Contoh Studi Kasus 2 (Cont.)
– Misalkan didapatkan nilai Max Ld dengan α1 = α2 = α3 = α4 = 0.125.
Sehingga nilai Ld = 0.25.
– Hitung nilai w dan b :

Pilih salah satu Support Vector dari Kelas “+1” dan “-1” untuk menghitung nilai b.
 Contoh Studi Kasus 2 (Cont.)
– Setelah didapatkan nilai w dan b :

Maka model SVM siap digunakan untuk proses klasifikasi.

Misalkan data uji/ data test xt = (1,5) maka K(xi,xt) = ᶲ(xi).ᶲ(xt)

x1 K(1,t) = ([Link] + 1)2 = (1.1 + 5.1 +1)2 = 72 = 49 (-0.125)(49)

x2 K(2,t) = ([Link] + 1)2 = (1.1 + 5.(-1) +1)2 = 32 = 9 (0.125)(9)
xt=(1,5)
x3 K(3,t) = ([Link] + 1)2 = (1.(-1) + 5.1 +1)2 = 52 = 25 (0.125)(25)
x4 K(4,t) = ([Link] + 1)2 = (1.(-1) + 5.(-1) +1)2 = (-5)2 = 25 (-0.125)(25)
-5
+

Jadi data xt = (1,5) tersebut masuk ke kelas negatif.

 Latihan Individu
1. Perhatikan dataset SVM Linier berikut :
x1 x2 Kelas (y) Support Vector (SV) x1 x2 Kelas (y) SV1 SV2
1 1 +1 1 2 3 -1 1 0
1 -1 -1 1 3 4 -1 1 1
0 2 -1 1 5 2 +1 1 1
-1 -1 -1 0 6 3 +1 0 0
dataset 1 dataset 2
Tentukan Visualisasi Hyperplane masing-masing dataset di atas !
2. Perhatikan dataset SVM non-Linier berikut :
x1 x2 Kelas (y) SV
0.5 0 -1 1
1 -1 +1 1
-1 1 +1 1
Tentukan persamaan Hyperplanenya,
-0.5 -0.5 -1 1 lalu uji kelas data xt = (1,1) !
Selesai