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
7
8
Image
Processing
Klasifikasi
Ekstraksi feature
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
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 = ∑ 5.
log ∑
∑
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
akanmencari
negatif.Kemudiandenganrumusdiatas,maka
program
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 NonNegative 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 kej), 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
