### 7.1 Maximal Margin Classifier

Ingat kembali kedua bab sebelumnya bahwa model klasifikasi mencari suatu
_decision boundary_ untuk memisahkan data pada kelas satu dan kelas lainnya.
Apabila kamu memiliki data berdimensi dua, maka _decision boundary_ yang
kita dapat berupa garis. Pada data tiga dimensi, _decision boundary_ berupa
sebuah bidang ( _plane_ ). Sebagai ilustrasi, lihatlah Gambar 7.1. Secara umum,
konsep bidang pemisah disebut sebagai _hyperplane_. Untuk data berdimensi
F, bidang pemisah kita memiliki dimensiF−1.
Secara matematis, _hyperplane_ didefinisikan pada persamaan 7.1 (dapat
ditulis ulang seperti persamaan 7.2), dimanaxmelambangkan suatu fitur,x
adalah _input_ dalam bentuk _feature vector_ danFmelambangkan banyaknya fitur.
Ingat kembali, ruas kiri pada persamaan adalah bentuk dasar pada model
linear. Dengan demikian, kita mengasumsikan bahwa data dapat dipisahkan


92 7 Support Vector Classifier

```
Gambar 7.1: Ilustrasi _hyperplane_.
```
secara linear.
x 1 w 1 +x 2 w 2 +···+xFwF+b= 0 (7.1)
x·w+b= 0 (7.2)

Untuk permasalahan klasifikasi dua kelas, kita dapat memisahkan keputusan
berdasarkan letak data pada _hyperplane_, misal di atas atau di bawah _hyperplane_ pada
Gambar 7.1. Secara lebih matematis, seperti pada persamaan 7.3
dan 7.4. Konsep ini mirip seperti yang sudah dijelaskan pada bab 5 tentang
melakukan _binary classification_ menggunakan fungsi _sign_ dan _thresholding_.

```
ifx·w+b > 0 ,then classA (7.3)
```
ifx·w+b < 0 ,then classB (7.4)
Apabila kita memang mampu memisahkan data dua kelas secara sempurna
dengan suatu _hyperplane_ ( _linearly separable_ ), pilihan _hyperplane_ yang
dapat kita buat tidaklah satu. Artinya, kita dapat menggeser-geser garis pembatas,
disamping tetap memisahkan data secara sempurna, seperti diilustrasikan
pada Gambar 7.2. _Hyperplane_ terbaik dari beberapa pilihan yang
ada adalah yang memiliki _maximal margin_. Artinya, suatu _hyperplane_ yang
memiliki jarak terjauh terhadap data pada suatu kelas. Dengan demikian,
ada jarak yang besar dari _hyperplane_ dengan data. Ilustrasi diberikan pada
Gambar 7.3. Kita harap, suatu _hyperplane_ yang memiliki _margin_ besar dapat
melakukan klasifikasi dengan baik pada data yang belum kita lihat, karena
kita memberikan _margin_ yang besar untuk suatu data baru masuk ke daerah
kelas masing-masing. Bentuk lingkaran yang memiliki _border_ berwarna hitam
pada Gambar 7.3 menandakan data terluar pada masing-masing kelas, dikenal


```
7.1 Maximal Margin Classifier 93
```
Gambar 7.2: Ilustrasi banyak pilihan _hyperplane_. Garis hitam melambangkan
opsi _hyperplane_ untuk memisahkan data secara sempurna.

sebagai _support vectors_. Garis putus-putus melambangkan garis yang dibentuk
oleh masing-masing _support vectors_ untuk masing-masing kelas ( _margin_ ).
Apabila kita definisikan (simbolkan) kelas pertama dengan _output_ bernilai
1 dan kelas kedua bernilai−1 (ingat kembali materi fungsi _sign_ ), makasupport
vectorsadalah poinxyang memenuhi kriteria pada persamaan 7.5. Dengan
demikian, semua data berlabel 1 dan−1 memenuhi persamaan 7.6, dimanay
melambangkan kategori. Hal inilah yang disebut sebagai _maximal margin_
_classifier_. Kita mencari _support vectors_ yang memberikan _hyperplane_ yang
memiliki _maximal margin_. Lihatlah ilustrasi pada Gambar 7.4!

```
|x·w+b|= 1 (7.5)
```
yi(x·w+b)≥ 1 (7.6)
Misalkan kita ambil satu _support vector_ dari masing-masing kelas. Pada
kelas pertama, ia memenuhixc^1 ·w+b= 1. Pada kelas kedua, ia memenuhi
xc^2 ·w+b=−1. Apabila kita kurangi kedua persamaan tersebut, kita mendapatkan
persamaan 7.7. Persamaan 7.8 memberikan perhitungan _margin_ antara
_support vectors_ dan _hyperplane_ yang memberikan nilai maksimal.

```
w·(xc^1 −xc^2 ) = 2 (7.7)
```
```
w
‖w‖
·(xc^1 −xc^2 ) =
```
#### 2

```
‖w‖
```
#### (7.8)

Sekarang, kita formalisasi _maximal margin classifier_ secara matematis. Objektifnya
adalah memaksimalkan _margin_ (persamaan 7.9) dengan menjaga
setiap _training data_ diklasifikasikan dengan benar (persamaan 7.10).


94 7 Support Vector Classifier

Gambar 7.3: _Maximal Margin Hyperplane_. Bentuk lingkaran yang memiliki
_border_ di- _bold_ berwarna hitam menandakan data terluar pada masing-masing
kelas, dikenal sebagai _support vectors_. Garis putus-putus melambangkan garis
yang dibentuk oleh masing-masing _support vectors_ untuk masing-masing kelas
( _margin_ ).

```
Objective : maximize Margin =
```
#### 2

```
‖w‖
```
#### (7.9)

```
Subject to :yi(xi·w+b)≥ 1 (7.10)
```
Tidak sama dengan _model linear_ yang sudah dijelaskan sebelumnya, kita ingin
mengoptimasi sebuah fungsi sembari memenuhi kendala ( _constraint_ ) dari
fungsi lain. Ini adalah bentuk _integer linear programming_, dan solusi untuk
_maximal margin classifier_ dapat diselesaikan menggunakan _lagrange multiplier_.
Untuk detail penyelesaiannya, silahkan membaca sumber lainnya.
Seperti yang kamu sadari, _maximal margin classifier_ hanya bergantung
pada subset _training data_ yang dipilih sebagai _support vectors_. Dengan demikian,
metode ini sangat sensitif terhadap tiap-tiap observasi. Satu observasi baru
yang menjadi _support vector_ dapat merubah _decision boundary_. Kita kenal
ini sebagai _overfitting_. Ilustrasi permasalahan ini diberikan pada Gambar 7.5.
Selain itu, _maximal margin classifier_ mengasumsikan bahwa data bersifatlinearly
separable, walaupun kebanyakan data tidak bersifat demikian.


```
7.1 Maximal Margin Classifier 95
```
```
Gambar 7.4:Maximal Margin Classifier.
```
Gambar 7.5:Maximal Margin Classifiersangatlah sensitif terhadap perubahan _training_
_data_. Lingkaran berwarna oranye melambangkan _training data_
baru. Akibat kemuculan data baru ini, _decision boundary_ awal (garis berwarna
hitam) berubah secara cukup dramatis (garis berwarna oranye).


96 7 Support Vector Classifier

