7

BAB II

KAJIANPUSTAKA

2.1 Klasifikasi

Klasifikasi adalah proses pengelompokan data menjadi suatu kelas

berdasarkan kesamaan karakteristik pada data – data yang ada. Ada 2 jenis

metode yang dapat digunakan dalam klasifikasi, yaitu supervised

classification dan unsupervised classification. Supervised classification

adalah suatu teknik klasifikasi yang digunakan untuk mengekstraksi

informasi dari data yang telah di training (Liu Xiang). Data yang akan

ditraining adalah data yang sudah diklasifikasi atau dikelompokkan

terlebih dahulu, sehingga classifier akan mendapatkan informasi terlebih

dahulu dari data training. Kemudian teknik yang lain untuk klasifikasi

adalah Unsupervised classification. Unsupervised classification

merupakan sebuah teknik yang tidak membutuhkan manusia untuk

mengklasifikan data terlebih dahulu. Teknik ini menggunakan beberapa

algoritma klasifikasi untuk mengelompokkan data tanpa perlu data training

terlebih dahulu. Berikut contoh proses klasifikasi

8

Gambar 2.1 Proses Klasifikasi

2.2 Image Processing

Pada umumnya original image yang ingin digunakan untuk proses

dalam suatu aplikasi memiliki ukuran yang besar dan resolusi yang tinggi

sehingga membutuhkan lebih banyak waktu dan memori untuk program

dapat mengevaluasi image tersebut. Selain itu, terkadang image yang akan

digunakan terdapat beberapa noise sehingga dapat mengurangi akurasi

program dalam mengenali suatu image. Oleh karena itu sebelum kita

menggunakan image dalam aplikasi, diperlukan suatu proses yang

dinamakan imageprocessing.

Imageprocessingmemainkan peran yang sangat penting dalam

proses klasifikasi image. Imageprocessing adalah sebuah teknik untuk

meningkatkan kualitas atau merekonstruksi sebuah gambar untuk

digunakan dalam berbagai macam aplikasi (Furtado, 2010).Salah satu

teknik yang bisa digunakan untuk melakukan image processing adalah

operasi Morphologi. Operasi morphologi bergantung pada urutan

kemunculan pixel, sehingga teknik morphologi sangat sesuai apabila

digunakan untuk melakukan pengolahan binary image atau grayscale

Image Processing

Ekstraksi feature

Klasifikasi

9

image(Agung, 2006).Operasi morphologi yang standar dilakukan adalah

dilatasi dan erosi.

2.2.1 Dilatasi

Dilatasi adalah operasi morphologi yang bekerja dengan cara

menambahkan pixel pada batas antar objek dalam suatu citra digital.Pada

umumnya dilatasi digunakan pada gambar biner, tetapi ada beberapa versi

yang dapat bekerja pada gambar grayscale(Pawar, 2012).Contoh proses

dilatasi :

Gambar 2.2 Proses Dilatasi

2.2.2 Erosi

Erosi adalah operasi morphologi yang bekerja dengan cara

mengurangi pixel pada batas antar objek dalam suatu citra digital.Pada

umumnya erosi digunakan pada gambar biner, tetapi ada beberapa versi

yang dapat bekerja pada gambar grayscale(Pawar, 2012).Contoh proses

erosi :

10

Gambar 2.3 Proses Erosi

2.3 Feature Extraction

Feature extraction adalah sebuah proses untuk mengambil atau

mengekstrak karakteristik atau informasiyang penting dari

suatuimageuntuk digunakan dalam proses klasifikasi. Ada beberapa teknik

untuk melakukan feature extraction, seperti PCA (Principal Component

Analysis) dan NMF (Nonnegative Matrix Factorization).Tujuan dari

feature extractionadalah :

1. Menghilangkan data gambar yang berulang atau redundan.

2. Menghilangkan data gambar yang kurang atau tidak memiliki arti

dalam klasifikasi.

3. Rekonstruksi data agar optimal dalam proses klasifikasi.

2.4 Algoritma Feature Ekstraction

2.4.1 Principal Component Analysis (PCA)

Principal Component Analysis (PCA) adalah salah satu teknik

untuk melakukan reduksi dimensi.Pada face recognition basic vectors

11

dapat menampilkan wajah seperti hantu yang disebut eigenfaces.Gambar

apapun dapat diubah menjadi kombinasi linear dengan teknik ini.Karena

metode ini bersifat holistic, PCA tidak mampu untuk mengekstrak

komponen berdasarkan fitur lokal saja.

Hal pertama yang harus dilakukan dalam proses PCA adalah

menghitung rata – rata setiap gambar dengan rumus :

Ψ 1

Γ

Setiap wajah dihitung nila perbedaan matrix wajah dengan rata –

rata gambar dengan vector Γ Ψ. Kemudian setelah selisihnya

didapatkan, maka hitung nilai eigenvector dan eigenvalue nya.

2.4.2 Algoritma Non-Negative Matrix Factorization (NMF)

Menurut Lee & Seung, algoritma NMF dapat mempelajari bagian

dari wajah atau sebagian dari data (Lee, 1999). Metode ini berbeda dengan

metode lainyang sejenis, seperti Principal Component Analysis

(PCA).Basis imagesyang dihasilkan memiliki fitu local dari bagian –

bagian gambar.Non-negative matrix factorization memberikan sebuah

matrix non-negative yang biasa diberikan namaX.matrixX berisi data –

data images yang ingin digunakan atau berisi database images. Kemudian

ada 3 matrix yang digunakan untuk membangun factorization dalam NMF,

yaituX≈WH atau

12

Dimana matrix W berukuran n x rdan matrix H berukuran r x m

sehingga jika matrix W dikalikan dengan matrix H,maka akan

menghasilkan matrix X dengan ukuran n x m. Setiap kolom n pada matrix

X mengandung nilai pixel yang non-negative dari setiap m gambar.Matrix

W disebut sebagai basis image, sedangkan matrix H disebut sebagai

encoding dan masing – masing kolom dari matrix H berhubungan dengan

data image yang ada pada matrix X.Nilai r pada matrix W dan H

umumnya didapatkan dari hasil percobaan dengan syarat (n + m) r < nm,

dan hasil dari WH dapat dianggap sebagai bentuk kompresi data dari

matrix X. Masing – masing matrix tidak boleh ada yang bernilai negative.

Karena batasan non negative yang dilakukan pada proses dekomposisi,

rekonstruksi images dibentuk dengan penambahan komposisi basis image.

Kualitas aproksimasi tergantung pada cost function yang berhubungan

dengan dekomposisi (Buciu et al, 2006). Ada 2 cost function yang

dipakai, yaitu:

4. Kullback-Leibler divergence

KL(X||WH)NMF = ∑ log∑

∑

5. Squared Euclidean distance

Berdasarkan factorization darirumusan NMF, maka matrix yang

perludicariadalah matrix W dan H berdasarkan matrix X yang berisi

database gambar.Rumusuntukmencari matrix W dan H adalah :

13

∑

Proses awal yang dilakukan dalam NMF adalah memberi nilai nilai

awal untuk matrix W dan H secaraacak dengan ketentuan tidak boleh ada

nilai yang negatif.Kemudiandenganrumusdiatas,maka program

akanmencari matrix W dan H yang paling optimal agar matrix W

jikadikalidengan matrix H, makaakanmendekati matrix X. berikut adalah

contoh basis images dari NMF

Gambar 2.4 Basis Images NMF

2.5.3 Local Non-negative Matrix Factorization (LNMF)

Setelah NMF yang dikembangkan oleh Lee & Seung, Li et al mulai

mengembangkan LNMF (Local Non-negative Matrix Function) untuk

meningkatkan kekurangan basis image dengan cara memodifikasi cost

14

function informasi yang berulang pada basis image dapat diminimalkan

(Li, 2001). Cost function yang baru dalam LNMF menjadi:

|| ||

Dimana nilai = U = , = V = HHT dan , 0 adalah

bilangan konstan. Sedangkan untuk rumus dari update rules pada basis

images (matrix W) dan koefisien (matrix H) juga mengalami penyesuaian

menjadi :

Berikut adalah contoh basis images dari LNMF

Gambar 2.5 Basis Images LNMF

15

2.5.4 Nonsmooth Non-negative Matrix Factorization

Kemudian model NMF yang baru diperkenalkan oleh Pascual

Montano pada tahun 2006 yang diberi namaNonsmooth Nonnegative

Matrix Factorization (nsNMF) (Montano, 2006). NMF sebelumnya

membuat 2 matrix W dan H dimana salah satu matrix harus bersifat

sparse, sedangkan matrix lainnya harus bersifat non sparse.Akibat

memaksakan sparseness constraintsuntuk kedua matrix tersebut, maka

dapat merusak atau mengurangi kualitas dari model data yang dibentuk.

Pada model NMF yang baru ini, rumus untuk menghasilkan matrix W dan

H agak sedikit berubah menjadi

Dimana matrix X, W dan H masih sama dengan NMF yang

sebelumnya, sedangkan matrix S adalah sebuah matrix positif yang

simetris dan merupakan matrix yang bersifat sparseness atau

smooth.Dengan adanya matrix S, maka matrix W dan H akan menjadi

matrix yang bersifat sparse atau nonsmooth.Matrix S sendiri dibentuk

dengan rumus

1 11

Dimana I adalah sebuah matrix identitas dan 1 merupakan sebuah

vector 1 kolom yang bernilai angka satu dengan ukuran r x r. Sedangkan θ

adalah sebuah nilai antara 0 sampai 1.Perubahan juga terjadi pada

perhitungan update rules untuk matrix W dan H, dimana untuk rumus

update H, ganti matrix W menjadi WS dan untuk matrix W, ganti matrix H

menjadi SH sehingga kedua rumus update rules W dan H menjadi :

16

Berikut adalah contoh basis images dari nsNMF

Gambar 2.6 Basis Images nsNMF

2.5 Penelitian Terkait NMF

Berikut ini adalah beberapa penelitian mengenai NMF.

1. NMF pertama kali diteliti oleh Lee & Seung pada tahun 1999. Pada

penelitian ini NMF digunakan untuk mereduksi dimensi pada gambar

wajah secara local

2. Metode LNMF digunakan dalam penelitian Li et al dengan judul

penelitian Learning Spatially Localized, Parts-Based Representation.

Pada penelitian ini LNMF juga digunakan untuk face recognition dan

17

memberikan akurasi yang lebih tinggi dibandingkan dengan NMF dan

PCA

3. Liu et al pada tahun 2003 mengajukan metode SNMF (Sparse Non-

Negative Matrix Factorization). Metode ini menghasilkan algoritma

yang lebih cepat. Namun juga memberikan dampak dari sparseness

yang dilakukan secara implisit

4. Non Negative Matrix Factorization with Sparseness Constraint

(NMFSC) diusulkan oleh Hoyer pada tahun 2004. Menunjukkan

bahwa NMFSC dapat mencapai konvergensi yang lebih cepat.

5. Nonsmooth Non-Negative Matrix Factorization diperkenalkan oleh

Pascual Montano pada tahun 2006. Metode ini memberikan sebuah

matrix tambahan untuk menambah sparseness dari NMF dan

penelitian ini membuktikan bahwa nsNMF lebih unggul dibandingkan

dengan metode NMF yang ada dalam face recognition dan Brain

Electromagnetic Tomography.

6. Pada tahun 2009, Buciu dan Gascadi melakukan penelitian untuk

melakukan klasifikasi terhadap mammogram dengan menggunakan

NMF, PCA dan ICA. Pada penelitian ini terbukti bahwa NMF

memiliki hasil reduksi dimensi yang lebih baik dibandingkan dengan

2 metode lainnya.

2.6 Supervised Classification

2.6.1 Support Vector Machine (SVM)

SVM pertama kali dikenalkan oleh Vapnik pada tahun 1992

(Nugroho, 2006). SVM pada dasarnya dibuat untuk melakukan proses

18

klasifikasi. Inti dari metode SVM adalah pembangunan hyperplane yang

optimal yang dapat memisahkan antara data dengan class yang berlawanan

dengan menggunakan kemungkinan margin yang terbesar.Sedangkan

margin adalah jarak antara hyperplane optimal dengan vector yang paling

dekat dengan hyperplane itu (Antkowiak, 2006).

Gambar 2.7 Optimal Hyperplane

Masalah klasifikasi pada SVM dapat diartikan sebagai usaha

menemukan hyperplane yang dapat memisahkan data menjadi 2 kelompok

atau kelas.Dari gambar 2.1, dapat dilihat ada banyak kemungkinan

hyperplane yang dapat dilakukan.Namun karena ingin mencari hyperplane

yang terbaik antara kedua kelas tersebut, maka perlu dilakukan

pengukuran margin hyperplane tersebut dan dicari titik maksimalnya.Garis

solid pada gambar 2.1 menunjukkan hyperplane terbaik yang bisa

didapatkan.Usaha untuk mendapatkan hyperplane terbaik ini merupakan

inti dari training atau pembelajaran padaSVM.

19

2.6.2 Artificial Neural Network (ANN)

Artificial Neural Network (ANN) adalah cabang ilmu soft

computingyang meniru sistem jaringan saraf biologis atau sistem kerja

otak makhluk hidup.Ada beberapa keuntungan yang bisa didapat dengan

menggunakan neural network, yaitu (Zhang, 2000) :

7. Neural network adalah data driven self-adaptivemethodssehingga

neural network dapat menyesuaikan diri dengan data tanpa spesifikasi

eksplisit.

8. Neural network menggunakan fungsi pendekatan, sehingga neural

network dapat melakukan pendekatan dengan berbagai macam fungsi

dan akurasi yang berbeda – beda.

9. Neural network adalah model non linier, sehingga membuat neural

network menjadi lebih fleksibel dalam melakukan permodelan

hubungan data yang kompleks. Dan akhirnya neural network dapat

memperkirakan probabilitas yang memberikan dasar dalam

menetapkan aturan klasifikasi dan analisis statistik.

Neural network sudah berhasil diaplikasikan di dalam berbagai

bidang industry, bisnis dan scienceseperti speechrecognition, medical

diagnosis, prediction, dan sebagainya. Pada dasarnya neural network

memiliki struktur umum yang membentuk neural network, yaitu :

1. Input Layer

Input layer berfungsi sebagai penghubung jaringan ke dunia luar

(sumber data). Neuron-neuron ini tidak melakukan perubahan apapun

terhadap data, tapi hanya meneruskan data ini ke lapisan berikutnya.

20

2. Hidden Layer

Suatu jaringan dapat memiliki satu atau lebihhidden layer atau bahkan

bisa juga tidak memilikinya sama sekali. Jika jaringan memiliki

beberapa hidden layer, maka lapisan tersembunyi terbawah berfungsi

untuk menerima masukan dari lapisan input. Besarnya nilai masukan

(net) neuron ke-j pada lapisan tersembunyi ini tergantung pada

akumulasi jumlah perkalian antara nilai bobot (w, kekuatan hubungan

antar neuron) dengan nilai keluaran (O) neuron ke i pada lapisan

sebelumnya (neuron input) ditambah dengan nilai bias (w, neuron ke-

j), atau

Nilai bias ini merupakan nilai konstan yang dimiliki oleh setiap neuron

(kecuali neuron pada lapisan input) yang digunakan untuk

memperbaiki keluaran jaringan agar dapat menyamai atau mendekati

nilai keluaran (output) yang diinginkan. Bobot wji bernilai 0

menunjukkan bahwa antara neuron ke-j dan ke-i tidak terdapat

hubungan.

Nilai keluaran neuron pada lapisan tersembunyi ini merupakan fungsi

dari nilai masukannya f(net (j)). Salah satu contoh fungsi yang biasa

sering dipakai adalah fungsi Sigmoid.Pada hidden layer pada lapisan

yang berikutnya (jika ada) berlaku hal yang sama seperti hidden layer

di atas, hanya saja data masukannya berasal dari hidden layer lapisan

sebelumnya.

3. Output Layer

21

Prinsip kerja neuron-neuron pada lapisan ini mirip dengan prinsip

kerja neuron-neuron pada lapisan tersembunyi (hidden layer) tetapi

keluaran dari neuron pada lapisan ini sudah dianggap sebagai hasil

dari proses