BAB 2 KAJIAN PUSTAKA
2.1
Tinjauan Umum Citra Dalam Artificial Intelligence banyak menggunakan citra sebagai inputyang diproses dalam clustering dan classification. Citra yang diproses memiliki memori yang besar dan sering membawa nilai yang ambigu dan data redundancy (bagian data yang tidak mengandung informasi terkait atau merupakan pengulangan dari informasi yang sudah dinyatakan sebelumnya atau sudah diketahui), sehingga menghambat dalam transmisi data citra. Perkembangan secara pesat dalam pengolahan citra digital dimulai sekitar tahun 1960 yaitu pada saat teknologi komputer telah sanggup memenuhi suatu kecepatan proses serta kapasitas memori yang dibutuhkan oleh berbagai algoritma pengolahan citra. Secara umum jenis aplikasi yang dikembangkan ada tiga yaitu : a. M emperbaiki
kualitas
suatu
citra,
sehingga
dapat
lebih
mudah
diinterpretasikan oleh mata manusia. b. M engolah informasi yang terdapat pada suatu citra untuk keperluan pengenalan objek secara otomatis oleh suatu mesin. Bidang ini sangat erat hubungannya dengan ilmu pengenalan pola (pattern recognition) yang umumnya bertujuan mengenali suatu objek dengan cara mengekstraksi informasi
penting
yang
terdapat 8
dalam
suatu
citra.
9
c. M engompres atau memampatkan data citra sehingga hanya memakai jumlah memori yang jauh lebih kecil dari aslinya tanpa mengurangi kualitas citra yang berarti. 2.1.1. Pengertian Citra Citra yang terlihat merupakan cahaya yang direfleksikan dari sebuah objek. Sumber cahaya menerangi objek, objek memantulkan kembali sebagian dari berkas cahaya tersebut dan pantulan cahaya ditangkap oleh alat-alat optik, misalnya mata manusia, kamera, scanner, sensor satelit, yang kemudian direkam. Ada 2 jenis citra yaitu citra tampak dan citra tak tampak.Citra tampak adalah citra yang nampak dilayar monitor atau foto, lukisan, citra. Sedangkan citra tak tampak adalah citra yang direprentasikan dalam fungsi matematis (data foto atau citra dalam file). Citra digital adalah citra yang disimpan dalam format digital (dalam bentuk file). Hanya citra digital yang dapat diolah menggunakan komputer. Jenis citra lain jika akan diolah dengan komputer harus diubah dulu menjadi citra digital. 2.1.2. Citra Digital Citra digital merupakan fungsi kontinyu dari intensitas cahaya pada bidang 2 dimensi. Fungsi dari intensitas citra adalah dimana
dan
adalah koordinat spasial dan nilai
secara matematis adalah intensitas citra
pada koordinat tersebut.
Citra digital adalah barisan bilangan nyata maupun kompleks yang diwakili oleh bit-bit tertentu Umumnya citra digital berbentuk
10
persegi panjang atau bujur sangkar (pada beberapa sistem pencitraan ada pula yang berbentuk segienam) yang memiliki lebar dan tinggi tertentu.Ukuran ini biasanya dinyatakan dalam banyaknya titik atau piksel sehingga ukuran citra selalu bernilai bulat (Positif).Setiap titik memiliki koordinat sesuai posisinya dalam citra.Koordinat ini biasanya dinyatakan dalam bilangan bulat positif, yang dapat dimulai dari 0 atau 1 tergantung pada sistem yang digunakan.
Gambar 2.1 Citra Digital
Setiap titik juga memiliki nilai berupa angka digital yang merepresentasikan informasi yang diwakili oleh titik tersebut.Format data citra digital berhubungan erat dengan warna.Pada kebanyakan kasus, terutama untuk keperluan penampilan secara visual, nilai data digital merepresentasikan warna dari citra yang diolah.
11
Citra digital merupakan suatu matriks dimana indeks baris dan kolomnya menyatakan suatu titik pada citra tersebut dan elemen matriksnya (yang disebut sebagai elemen citra / piksel / pixel / picture element / pels) menyatakan tingkat keabuan pada titik tersebut. Citra digital dinyatakan dengan matriks berukuran kolom/lebar =
(baris/tinggi =
,
).
= jumlah baris = jumlah kolom = maksimal warna intensitas (derajat keabuan / gray level)
Gambar 2.2 Citra Digital dalam matriks
Dalam citra digital dikenal citra dengan derajat keabuan dan citra berwarna. Citra digital dengan derajat keabuan direpresentasi sebagai array dua dimensi dari sejumlah bilangan.M asing-masing bilangan merepresentasikan intensitas atau derajat keabuan dari citra di posisi yang bersesuaian. Jika setiap tingkat keabuan direpresentasikan dalam 8 bit (1 byte), maka rentang data citra yang dicakup adalah sebanyak 256 derajat keabuan, yaitu dari 0 – 255. Derajat keabuan 0 merepresentasikan intensitas warna gelap sedangkan nilai tertinggi 255 merepresentasikan
12
intensitas warna terang. Nilai tingkat keabuan dari suatu pixel adalah sama dengan terang rata-rata pada sejumlah grid yang dilingkupi pixel tersebut. 2.1.3. Resolusi Resolusi citra menyatakan ukuran panjang kali lebar dari sebuah citra. Resolusi citra biasanya dinyatakan dalam satuan piksel. Semakin tinggi resolusi sebuah citra, semakin baik kualitas citra tersebut. Namun, tingginya resolusi menyebabkan semakin banyaknya jumlah bit yang diperlukan untuk menyimpan dan mentransmisikan data citra tersebut. 2.1.4. Kedalaman bit Kedalaman bit menyatakan jumlah bit yang dipelukan untuk mrepresentasikan tiap piksel citra pada sebuah frame. Kedalaman bit biasanya dinyatakan dalam satuan bit/piksel. Semakin banyak jumlah bit yang digunakan untuk merepresentasikan sebuah citra, maka semakin baik kualitas citra tersebut. 2.1.5. Pengolahan Citra (Image Processing) Pengolahan
citra
(Image
Processing)
merupakan
proses
pengolahan dan analisis citra yang banyak melibatkan persepsi visual. Proses ini mempunyai ciri data masukan dan informasi keluaran yang berbentuk citra.
Gambar 2.3 Diagram proses Image Processing
13
Istilah pengolahan citra secara umum didefinisikan sebagai pemrosesan
citra
dua
dimensi
dengan
komputer.Secara
umum
pengolahan citra digital dapat diartikan sebagai pemrosesan terhadap sebuah citra dua dimensi oleh suatu komputer digital atau dapat juga diartikan
sebagai
suatu
pengolahan
data
dua
dimensi
secara
digital.Aplikasi pengolahan citra digital dapat dijumpai dalam berbagai bidang, diantaranya untuk penginderaan jarak jauh melaui satelit, pengolahan citra pada bidang kedokteran, dan pengolahan citra untuk siaran televisi. Operasi pengolahan citra dapat dikelompokan dalam beberapa proses sebagai berikut: a. Perbaikan Citra (Image Restoration) Perbaikan citra adalah proses yang dilakukan untuk mendapatkan kembali (rekonstruksi) citra asli dari suatu citra yang telah mengalami proses degradasi. Kualitas citra yang diperoleh ditentukan dengan kemiripan dengan citra aslinya. Peningkatan kualitas citra adalah proses yang dilakukan terhadap suatu citra dengan tujuan untuk mendapatkan citra baru yang lebih baik kualitasnya untuk tujuan tertentu. b. Peningkatan Kualitas Citra (Image Enhancement) Proses peningkatan kualitas citra ini dilakukan terhadap suatu citra yang tidak mengalami degradasi dari citra aslinya. M etode
14
peningkatan kualitas citra terhadap suatu citra akan berbeda dengan metode yang dilakukan terhadap citra lainnya. c. Registrasi Citra (Image Registration ) Proses registrasi citra dilakukan berdasarkan beberapa atau banyak citra dari objek yang diambil secara terpisah. Selanjutnya, tiap-tiap citra digabungkan menjadi suatu objek agar dapat dianalisis lebih lanjut. Contoh registrasi citra adalah proses pengambilan citra bumi oleh satelit. Citra bumi yang ingin daimbil tidak dapat diambil langsung secara keseluruhan secara langsung, tetapi harus diambil bagian per bagian. Kemudian bagian-bagian ini disatukan sehingga membentuk citra bumi secara utuh.
Gambar 2.4 Image Registration citra bumi
15
d. Analisis Citra (Image Analysis) Operasi ini bertujuan untuk menghitung besaran kuantitatif citra untuk menghasilkan deskripsinya.Teknik analisis citra mengekstraksi fitur tertentu yang membantu dalam identifikasi objek. Proses segmentasi kadangkala diperlukan untuk melokalisasi objek yang diinginkan dari sekelilingnya. Analisis image biasanya melakukan edge detection, ekstrasi batas, fourier transform, dan lain-lain. e. Rekonstruksi Citra (Image Reconstruction) Operasi ini bertujuan untuk membentuk ulang objek dari beberapa citra hasil proyeksi.operasi rekonstruksi citra banyak digunakan dalam bidang medis.Contohnya adalah foto rontgen dengan sinar X digunkan untuk membentuk ulang citra organ tubuh. f. Kompresi Citra (Image Compression) Proses kompresi citra bertujuan untuk mendapatkan suatu citra baru yang dapat merepresentasikan suatu citra dalam bentuk ukuran bit yang lebih sedikt dibandingkan citra aslinya dan dalam citra terkompresi ini tidak terjadi penurunan kualitas yang berarti. Dengan kompresi data ini diharapkan dapat mengurangi besarnya ruang penyimpanan data dan lebarnya pita frekuensi yang dibutuhkan dalam sistem transmisi data.
2.2
Kompresi Citra Saat ini kebanyakan aplikasi menginginkan representasi citra digital dengan menggunakan kebutuhan memori yang seminimal mungkin.Kebutuhan akan adanya sistem kompresi merupakan suatu tuntutan dalam memperoleh hasil
16
penyimpanan data citra yang optimal. Walaupun konsekuensi yang diperoleh adalah adanya perbandingan terbalik antara rasio penyimpanan data citra dengan kualitas citra yang diperoleh. Citra yang belum dikompres disebut citra mentah (raw image), sementara citra hasil ompresi disebut CompressedImages. Kompresi citra (Images Compression) mempunyai tujuan meminimalkan kebutuhan memori untuk merepresentasikan sebuah citra digital. Prinsip umum yang digunakan pada proses kompresi citra digital adalah mengurangi duplikasi data di dalam citra sehingga memori yang dibutuhkan untuk merepresentasikan citra menjadi lebih sedikit dari pada citra digital aslinya.Terdapat dua proses utama dalam permasalahan kompresi citra digital, yaitu : a. Kompresi citra (Images Compression) Pada proses ini citra digital dalam representasinya yang asli (belum dikompres) dikodekan dengan representasi yang meminimumkan kebutuhan memori. Citra dengan format bitmap pada umumnya tidak dalam bentuk kompresan.Citra yang sudah dikompres disimpan ke dalam arsip dengan menggunakanformat tertentu. b. Dekompresi citra (Images Decompression) Pada proses dekompresi, citra yang sudah dikompresi harus dapat dikembalikan lagi menjadi representasi citra seperti citra aslinya. Proses ini diperlukan jika citra ingin ditampilkan ke layar atau disimpan ke dalam arsip dengan format yang tidak terkompres.
17
Input Image
Preprocessing
Encoding
Compressed File
Postprocessing
Decoded Image
Kompresi Compressed File
Decoding
Dekompresi Citra 2.5 Diagram proses Kompresi dan Dekompresi Citra
Pada proses Preprocessing dan postprocessing dilakukan transformasi dan kuantisasi pada citra mentah. Biasanya dilakukan fourier transform untuk menghilangkan noise pada citra mentah. Kuantisasi mempunyai fungsi untuk membatasi jumlah simbol yang dapat digunakan untuk merepresentasikan citra yang terkompres.Kuantisasi merupakan sebuah model pemetaan banyak ke satu. Kuantisasi dapat dibentuk dari pengkuantisasian skalar maupun pengkuantisasi vektor. Pengkuantisasi skalar, merujuk pada kuantisasi data elemen-elemen, sedangkan pengkuantisasi vektor merupakan kuantisasi dengan menggunakan suatu blok data citra. Encoding dan decoding berfungsi untuk membentuk sebuah kode tertentu (binary bit stream) dari setiap simbol yang dikeluarkan dari blok pengkuantisasi di atas. Coder bisa memakai fixed-length code atau variablelength code.Variable-length code (VLC) juga dikenal dengan nama entropy coding, yang memberikan kode sedemikian rupa sehingga mampu memperkecil panjang rata-rata representasi biner dari simbol tersebut. Hal tersebut dapat dilakukan dengan cara memberikan kode yang panjang menjadi lebih pendek
18
dibandingkan dengan data yang dimiliki simbol, yang mana hal ini merupakan prisnsip dasar dari entropy coding. 2.2.1. Tinjauan Umum Kompresi Citra Ada beberapa hal yang perlu diperhatikan dalam kompresi citra, yaitu: a. Scalability / Progressive Coding / Embedded Bitstream adalah kualitas dari hasil proses pengkompresian citra karena manipulasi bitstream tanpa adanya dekompresi atau rekompresi. Contohnya pada saat preview image sementara citra tersebut didownload. Semakin baik scalability, makin bagus preview image. M acam-macam dari scalability: i.
Quality progressive: dimana citra dikompres secara perlahanlahan dengan penurunan kualitasnya.
ii.
Resolution progressive: dimana citra dikompresi dengan mengenkode resolusi citra yang lebih rendah terlebih dahulu baru kemudian ke resolusi yang lebih tinggi.
iii.
Component progressive: dimana citra dikompresi berdasarkan komponennya, pertama mengenkode komponen gray baru kemudian komponen warnanya.
b. Region of Interest Coding adalah daerah-daerah tertentu dienkode dengan kualitas yang lebih tinggi daripada yang lain.
19
c. M eta Information adalah citra yang dikompres juga dapat memiliki informasi meta seperti statistik warna, tekstur, small preview image, dan author atau copyright information.
2.2.2. Teknik Kompresi Dalam teori informasi, proses pemampatan data dengan mengurangi pengulangan adalah berdasarkan pada sumber pengkodean. Citra memiliki dua tipe redundansi yaitu redundansi statistik (redundansi ruang dan redundansi spektrum) dan redundansi psikovisual. Redundansi statistik muncul karena beberapa pola ruang mempunyai kemiripan, sedangkan redundansi psikovisual terjadi karena adanya kenyataan bahwa mata manusia tidak sensitif terhadap adanya frekuensi beberapa ruang dalam citra. Setiap
sistem
kompresi
citra
yang
berbeda
akan
mengimplementasikan kombinasi pilihan-pilihan yang berbeda pula. Pada dasarnya metode kompresi citra dibagi menjadi dua jenis, yaitu : a. Kompresi Lossless, hasil yang ingin dicapai dari metode ini adalah mengurangi bitrate tanpa mengurangi data yang dimiliki oleh citra tersebut. M etode ini digunakan untuk aplikasi yang khusus, misalnya digunakan untuk pengiriman citra-citra di bidang kedokteran. b. Kompresi Lossy, hasil yang ingin dicapai adalah memperoleh ketelitian yang optimal dari suatu bitrate. Pada metode ini kita bisa melakukan manipulasi data-data yang dimiliki oleh citra. M anipulasi disini berupa pengurangan nilai presisi integer pada karakter citra.
20
2.2.3. Metode Kompresi Citra a. M etode Huffman M etode ini termasuk teknik Kompresi Lossless sering disebut juga sebagai statistical compression. Pengkodean citra berdasarkan pada derajat keabuan (gray level) dari piksel-piksel dalam keseluruhan citra. Nilai atau derajat keabuan yang sering muncul di dalam citra akan dikodekan dengan jumlah bit yang lebih sedikit sedangkan nilai keabuan yang frekuensi kemunculannya sedikit dikodekan dengan jumlah bit yang lebih panjang. Berikut algoritma metode Huffman: i.
Urutkan secara menaik nilai keabuan berdasarkan frekuensi kemunculannya atau peluang kumunculan yaitu frekuensi kemunculan dibagi dengan (
jumlah piksel dalam citra
). Setiap nilai keabuan dinyatakan sebagai pohon
bersimpul tunggal dan setiap simpul diassign dengan frekuensi kemunculan nilai keabuan tersebut. ii.
Gabung 2 buah pohon yang mempunyai frekuensi kemunculan paling kecil pada sebuah akar. Akar mempunyai frekuensi yang merupakan jumlah dari frekuensi 2 pohon penyusunnya. Perhatikan : frekuensi dengan nilai lebih kecil diletakkan di sisi kiri
iii.
Ulangi langkah satu (i) dan dua (ii) sampai tersisa satu pohon biner
21
iv.
Beri label setiap sisi pada pohon biner, label sisi kiri = 0, label sisi kanan = 1.
v.
Telusuri pohon biner dari akar ke daun. Barisan label-label sisi dari akar ke daun menyatakan kode Huffman untuk derajat keabuan yang bersesuaian.
b. M etode Run Length Encoding (RLE) Cocok digunakan untuk memampatkan citra yang memiliki kelompok-kelompok piksel berderajat keabuan yang sama. M etode ini dilakukan dengan menyatakan seluruh baris citra menjadi sebuah baris run, lalu menghitung run-length untuk setiap derajat keabuan yang berurutan. M etode RLE dapat dikombinasikan dengan metode Huffman untuk meningkatkan ratio kompresi.M ula-mula lakukan kompresi RLE lalu hasilnya dimampatkan lagi dengan Huffman. c. Kompresi JPEG JPEG (Joint Photograpic Experts Group) menggunakan teknik Kompresi Lossy sehingga sulit untuk proses pengeditan. Teknik kompresi JPEG menggunakan transformasi DCT untuk merubah nilai–nilai pixel dalam domain spasial menjadi koefisen – koefisien dalam domain frekuensi. JPEG cocok untuk citra pemandangan (natural generated image), tidak cocok untuk citra yang mengandung banyak garis, ketajaman warna, dan computer generated image. Dalam kompresi JPEG, mula–mula citra yang akan dikompresi dibagi menjadi blok-blok tertentu berukuran 8 x 8 yang selanjutnya ditransformasi dengan DCT untuk mendapatkan koefisien – koefisien
22
dalam domain frekuensi. Langkah selanjutnya adalah melakukan proses
kuantisasi
dan
pengkodean
dengan
metode
zig-zag
menggunakan RLE, Huffman. Setelah itu dilakukan konversi vector kuantisasi menjadi bit-bit untuk mengkontruksi file JPEG. d. Kompresi Wavelet Selain JPEG teknik lain yang berkembang adalah kompresi wavelet dengan menggunakan transformasi wavelet DWT (M orlet dan
Grossman,
1980). Transformasi DWT
mentransformasi Selanjutnya
citra
koefisien
menjadi wavelet
beberapa ini
digunakan koefisien
ditanam
untuk
wavelet.
kembali
dengan
menggunakan metode EZW. EZW mampu menyusun bit-bit menurut tingkat kepentingan, hasilnya adalah sebuah kode penempelan penuh (Fully Embedded), sehingga mampu mencapai kompresi yang maksimal. 2.2.4. Perhitungan Hasil Kompresi M emori
yang
dibutuhkan
untuk
merepresentasikan
citra
seharusnya berkurang secara berarti. Teknik kompresi dikatakan baik apabila didapatkan rasio kompresi yang besar, karena semakin besar rasio kompresi yang didapat berarti semakin kecil ukuran hasil kompresi. Pada beberapa metode, ukuran memori hasil kompresi bergantung pada citra itu sendiri. Citra yang mengandung banyak elemen duplikasi (misalnya citra langit cerah tanpa awan, citra lantai keramik) umumnya berhasil dikompresikan dengan memori yang lebih sedikit dibandingkan dengan
23
mengkompresikan citra yang mengandung banyak objek (misalnya citra pemandangan alam). Hasil rasio dapat di rumuskan sebagai: (2.1) Dimana: U kompresi adalah ukuran citra setelah dilakukan proses kompresi Uasli adalah ukuran citra asli Perhitungan
kualitas
citra digital yang
merupakan
hasil
modifikasi, terhadap citra digital yang asli, dapat dilakukan dengan menghitung nilai M SE (Mean Square Error) dan juga nilai PSNR (Peak Signal-to-Noise Ratio). Perhitungan nilai M SE dari citra digital berukuran , dilakukan sesuai dengan rumus berikut: (2.2) Dimana:
adalah nilai pixel di citra asli adalah nilai pixel pada citra hasil kompresi adalah dimensi image menyatakan citra digital yang asli sebelum dikompresi,
sedangkan
, merupakan citra digital hasil kompresi. Nilai M SE
yang besar, menyatakan bahwa penyimpangan atau selisih antara citra hasil modifikasi dengan citra aslinya cukup besar. Sedangkan untuk perhitungan nilai PSNR, dapat dilakukan dengan rumus berikut: (2.3)
24
Semakin besar PSNR, maka kualitas citra hasil modifikasi akan semakin baik, sebab tidak banyak data yang mengalami perubahan, dibandingkan aslinya.
2.3
Computer Vision Teknik-teknik kompresi yang sudah ada ternyata masih belum menjawab kebutuhan teknik kompresi yang baik. Kecepatan transmisi citra memang baik, tetapi disisi lain hal ini mengobarkan akurasi dari hasil kompresi citra, dan ini adalah hal penting dalam kompresi citra. Computer Vision memberikan solusi untuk permasalahan ini, yaitu dengan teknik reduksi dimensi. Terminologi lain yang berkaitan dengan pengolahan citra adalah Computer Vision atau Machine Vision. Pada hakikatnya, Computer Vision mencoba meniru cara kerja sistem visual manusia (human vision). Human vision sesungguhnya sangat kompleks. M anusia melihat objek dengan indera penglihatan (mata), lalu citra objek diteruskan ke otak untuk diinterpretasi sehingga manusia mengerti objek apa yang tampak dalam pandangan matanya. Hasil interpretasi ini mungkin digunakan untuk pengambilan keputusan. Computer Vision merupakan proses otomatis yang mengintegrasikan sejumlah besar proses untuk persepsi visual, seperti akuisisi citra, pengolahan citra, klasifikasi, pengenalan (recognition), dan membuat keputusan. Computer Vision terdiri dari teknik-teknik untuk mengestimasi ciri-ciri objek di dalam citra, pengukuran ciri yang berkaitan dengan geometri objek, dan menginterpretasi informasi geometri tersebut.
Proses-proses di dalam Computer Vision dapat
dibagi menjadi tiga aktivitas:
25
a. M emperoleh atau mengakuisisi citra digital b. M elakukan teknik komputasi untuk memproses atau memodifikasi data citra (operasi-operasi pengolahan citra). c. M enganalisis dan menginterpretasi citra dan menggunakan hasil pemrosesan untuk tujuan tertentu, misalnya memandu robot, mengontrol peralatan, memantau proses manufaktur, dan lain-lain. 2.3.1 Face Recognition Face Recognition adalah sebuah aplikasi komputer yang secara otomatis dapat mengidentifikasi dan memverifikasi wajah seseorang dari sebuah citra digital. Salah satu cara untuk melakukan Face Recognition adalah dengan membandingkan facial features dari citra yang dipilih dengan facial database yang sudah di training sebelumnya. Beberapa algoritma Face Recognition mengidentifikasi wajah dengan mengekstrak fitur dari citra wajah subjek. Sebagai contoh, sebuah algoritma dapat menganalisis posisi relatif, ukuran, dan bentuk dari mata, hidung, tulang pipi, dan rahang. Fitur-fitur ini kemudian digunakan untuk mencari citra lain dengan algoritma pencocokan fitur. Dalam melakukan proses recognisi, digunakan perhitungan Euclidean Distance antara citra input dengan citra asli yaitu : (2.4)
Namun ada juga algoritma yang pertama-tama menormalisasi sebuah dataset citra wajah lalu melakukan training sehingga dataset itu
26
terkompresi. Dataset ini akhirnya digunakan sebagai database pencocokan dalam melakukan Face Recognition maupun Face Detection. Beberapa algoritma Recognition yang terkenal diantarannya adalah Principal Component Analysis (PCA) menggunakan eigenfaces. 2.4
Reduksi Dimensi Data real-world, seperti sinyal suara, digital foto, atau scan fM RI, biasanya memiliki dimensi yang tinggi. Dengan tujuan untuk menangani data ini secara memadai, maka dimensinya perlu dikurangi. Reduksi dimensi adalah transformasi dari data berdimensi tinggi menjadi representasi data yang mengalami reduksi dimensi. Idealnya, reduksi dimensi harus memiliki dimensi yang sesuai dengan dimensi intrinsik dari sebuah data. Dimensi intrinsik data adalah jumlah minimum parameter yang diperlukan untuk account guna mengamati sifat suatu data. Reduksi dimensi penting dalam banyak domain, karena meringankan dimensi yang sangat besar dan sifat lain yang tidak diinginkan dari ruang berdimensi tinggi. Adapun hasil yang diperoleh. reduksi dimensi memfasilitasi klasifikasi, visualisasi, dan kompresi dari data berdimensi tinggi. Proses reduksi dimensi dapat didefinisikan sebagai berikut . Diberikan dataset matrik dengan terkadang
berukuran (
) yang terdiri dari
dimensi yang memiliki dimensi
, dan
yang berada disebuah manifold dengan
yang tertanam di dimensi ruang . Teknik reduksi dimensi mengubah
intrinsik (dimana
). Dalam istilah matematika, dimensi intrisik dapat diartikan
sebagai titik – titik dalam dataset dimensi
data
27
dataset
dengan
dimensi ke dalam dataset
baru dengan
dimensi, dengan
tetap mempertahankan geometri data sebanyak mungkin.Secara umum, geometri manifold data, dan dimensi intrisik
dataset
selalu diketahui.Oleh karena itu,
reduksi dimensi merupakan masalah yang hanya dapat diselesaikan dengan mengasumsikan sifat – sifat tertentu dari suatu data (seperti dimensi intrinsik). Teknik reduksi dimensi dibagi menjadi dua macam teknik, yaitu teknik reduksi dimensi non-linear dan teknik reduksi dimensi linear. Dalam pembagiannya dapat dilihat dari citra dibawah ini :
Dimensionality Reduction
linear
PCA
LDA
Nonlinear Alignment of lokal representations
NMF
Preserving global properties
Distance preservation
Unfolding Neural network
MDS, Isomap Diff.map s
Kernel‐ based
Kernel PCA Autoencoder
Preserving lokal properties
Reconstruction weights
Lokal tangent space
Neighborhood graph Laplacian
LLE MVU
LTSA Hessian LEE
Gambar 2.6 Diagram pembagian teknik reduksi dimensi
LLCChar
Laplacian Eigenmaps
28
2.4.1. Reduksi Dimensi Non-Linear Pada teknik ini terdapat 3 bagian, namun kami akan membahas 2 teknik non-linear utama yang digunakan untuk reduksi dimensi yang telah ditetapkan dan dipelajari dengan baik. Teknik yang paling utama untuk reduksi dimensi secara non-linear dapat dibagi menjadi 2 jenis utama, antara lain : 2.4.1.1. Teknik Global Teknik-teknik yang mencoba untuk mempertahankan sifat global asli suatu data dalam representasi yang berdimensi rendah. Ada 6 macam teknik reduksi dimensi yang termasuk dalam Teknik Global : a.
M ulti Dimensional Scaling (M DS) MDS adalah teknik yang mewakili kumpulan teknik non-linear yang memetakan representasi data berdimens i tinggi ke representasi data berdimensi rendah dengan tetap mempertahankan jarak berpasangan diantara datapoints sebanyak mungkin. Kualitas dari pemetaan ini dinyatakan dalam stress function, dimana kesalahan antara jarak berpasangan pada representasi data berdimensi rendah dan data berdimensi tinggi. Stress function dapat dirumuskan sebagai berikut: (2.5)
29
Dimana datapoints
adalah dan
jarak Euclidean antara
berdimensi tinggi, dan
jarak Euclidean antara datapoints
dan
adalah berdimensi
rendah. MDS banyak
digunakan
untuk
visualisasi data,
misalnya, dalam fM RI analisis dan dalam pemodelan molekul.Popularitas M DS telah menyebabkan usulan varian seperti SPE, CCA, SNE, dan FastMap. Selain itu, terdapat varian nonmetric M DS, yang bertujuan untuk menunjukkan hubungan ordinal dalam data, bukan jarak berpasangan. b.
Isomap Isomap adalah sebuah teknik reduksi dimensi nonlinear yang digunakan untuk memecahkan masalah dari MDS yang tidak dapat memperhitungkan account distribusi yang berdekatan dengan cara mempertahankan jarak geodesic berpasangan (atau lengkung) antara datapoints. Jarak geodesic adalah jarak antara dua titik yang diukur melalui manifold. Dalam Isomap, jarak geodesic antara datapoints membangun datapoint
graph G yang berdekatan, dimana setiap terhubung dengan k yang paling berdekatan
dengan
di dataset
dihitung dengan
. Jalur terpendek
30
antara dua titik dalam grafik membentuk perkiraan yang baik dari jarak geodesic antara dua poin yang ada, dan dengan mudah dapat dihitung menggunakan Dijkstra atau algoritma Floyd. Jarak geodesic antar semua datapoints dihitung, sehingga membentuk jarak geodesic matriks berpasangan. Representasi datapoints
di ruang
berdimensi rendah dari
dimensi rendah dihitung dengan
menerapkan skala multidimensi pada matriks jarak yang dihasilkan. Sebuah kelemahan penting dari algoritma ini adalah ketidakstabilan topologi yang ada. Dimana terkadan g Isomap dapat membangun koneksi yang salah pada grafik yang berdekatan. Seperti hubungan short-circuiting yang kemungkinan besar dapat merusak kinerja dari Isomap. Untuk mengatasi masalah ini dibuat beberapa pendekatan misalnya, dengan menghapus datapoints dengan jumlah aliran yang besar di jalur terpendek algoritma atau dengan menghapus neighbors terdekat yang melanggar linearitas lokal sekitar grafik. c.
M aximum Variance Unfolding(M VU) Maximum Variance Unfolding (M VU) mirip dengan Isomap dalam mendefinisikan grafik di sekitar data dan mempertahankan
jarak
berpasangan
di
grafik
yang
31
dihasilkan.
Namun
dalam
hal
mencoba
untuk
‘mengungkap’ manifold data secara eksplisit M VU berbeda dengan Isomap. Dimana M VU melakukan hal tersebut dengan
memaksimalkan
Euclidean
Distance
antara
datapoints, dalam batasan bahwa jarak dalam lingkaran grafik yang tersisa tidak berubah. M asalah optimisasi yang dihasilkan
dapat
diselesaikan
secara efisien
dangan
menggunakan pemrograman semidefinite. Algoritma
M VU
dimulai dengan
pembangunan
lingkaran grafik , dimana setiap datapoint
terhubung ke
yang merupakan neighbors terdekat dari
. Selanjutnya,
upaya M VU untuk memaksimalkan jumlah jarak kuadrat Euclidean antara semua datapoints, di bawah batasan bahwa jarak disekitar grafik G dipertahankan. Dengan kata lain, M VU melakukan optimasi masalah berikut: (2.6) Dimana : (2.7) Dari persamaan di atas M VU merumuskan masalah optimasi sebagai pemrograman Semidefinite Programming Program (SDP) dengan mendefinisikan matriks
yang
32
merupakan inti produk dari representasi data
berdimensi
rendah. Dapat dirumuskan sebagai berikut: Maximize trace
dimana:
i. ii. iii. Dari pesamaan
diatas,
representasi data
berdimensi rendah dapat diperoleh dengan melakukan dekomposisi nilai singular. Serupa dengan Isomap, tidak menutup kemungkinan hubungan short-circuiting dapat merusak kinerja dari M VU, karena menambah batasan ke dalam masalah optimasi untuk mencegah terjadinya unfolding dari suatu manifold. M eskipun demikian, M VU berhasil diterapkan untuk, lokalisasi misalnya, sensor dan DNA microarray analisis data. d.
Kernel PCA (KPCA) M erupakan reformulasi dari linear PCA tradisional dalam ruang dimensi tinggi yang dibangun menggunakan Fungsi Kernel. Kernel PCA menghitung vektor pokok
33
eigen dari matriks kernel yang dibandingkan dengan matriks kovarians. Kernel PCA menghitung K sebagai kernel matriks datapoints
yang didefinisikan sebagai berikut: (2.8)
Dimana
adalah Fungsi Kernel. Selanjutnya, kernel
matriks
dipusatkan dengan menggunakan modifikasi dari
persamaan berikut: (2.9) Operasi
pemusatan
berkoresponden
dengan
mengurangkan rata – rata fitur dalam PCA tradisional. Hal ini memastikan bahwa fitur dalam ruang dimensi tinggi didefinisikan oleh Fungsi Kernel yaitu berarti nol. Kemudian
utama dari vektor eigen
dari pusat matriks
kernel dihitung. Sekarang vektor – vektor eigen dari kovarians matriks
dapat dihitung, dikarenakan mereka
berhubungan dengan vector-vektor eigen dari matriks kernel
melalui: (2.10)
Untuk mendapatkan representasi data yang berdimens i rendah , maka data tersebut diproyeksikan ke vektor –
34
vektor eigen dari matriks kovarians aj .Hasil proyeksi ditunjukan sebagai berikut: (2.11) menunjukan nilai ke j dalam vector
Dimana
dan
adalah Fungsi Kernel yang juga digunakan dalam perhitungan matriks kernel. Dikarenakan kernel PCA merupakan
metode berbasis
kernel,
pemetaan
yang
dilakukan oleh kernel PCA bergantung pada pilihan Fungs i Kernel
. Pilihan yang mungkin untuk Fungsi Kernel
termasuk kernel linier (membuat kernel sama dengan PCA tradisional), polinom kernel, dan kernel Gaussian. Kernel PCA telah berhasil ditetapkan untuk face recognition, speech recognition dan novelty detection. Sebuah kelemahan penting dari kernel PCA adalah bahw a ukuran dari matriks kernel sebanding dengan kuadrat dari jumlah hal dalam dataset.
e.
Diffusion M aps Diffusion Maps (DM ) berasal dari bidang sistem dinamis yang mendefinisikan random walk markov pada suatu grafik data sejumlah timesteps untuk mendapatkan datapoints. Dengan menggunakan pengukuran ini, jarak difusi dapat
didefinisikan.
Dalam representasi data
35
berdimensi
rendah,
jarak
difusi berpasangan
dapat
dipertahankan sebaik mungkin. Dalam metode Diffusion Maps, langkah pertama adalah membangun grafik dari suatu data. Bobot dari sisi dalam grafik dihitung dengan menggunakan Fungsi Kernel Gaussian, yang mencari matriks W dengan persamaan (2.12)
Dimana
menunjukkan
varians
Selanjutnya, normalisasi matriks
dari
Gaussian.
dilakukan sedemikian
rupa dimana baris – barisnya ditambahkan menjadi 1. Dengan
cara
ini,
M atriks
dibentuk
dengan
persamaan:
(2.12)
M atriks yang dihasilkan
dianggap sebagai
matriks M arkov yang mendefinisikan probabilitas transisi ke depan matriks dalam suatu proses dinamis. Oleh karena itu, matriks
mewakili probabilitas transisi dari satu
datapoint ke datapoint lainnya dalam timestep tunggal. Forward
probability
untuk timesteps
ditunjukkan
matrix dengan
.
36
M enggunakan probabilitas random walk forward
,
jarak difusi didefinisikan dengan :
(2.13)
Dalam persamaan,
adalah sebuah aturan
dimana atribut – atribut lebih kearah bagian – bagian grafik dengan kepadatan tinggi. Hal ini didefinisikan dengan (2.14)
Dimana
adalah tingkat suatu node
didefinisikan
dengan
.
Dari
yang
persamaan
tersebut, dapat diamati bahwa pasangan datapoint – datapoint dengan probabilitas transisi kemajuan yang memiliki sebuah jarak difusi yang kecil. Ide utama dibalik jarak difusi tersebut adalah didasarkan pada banyaknya jalan yang melalui grafik. Hal tersebut membuat jarak difusi lebih tahan terhadap noise, misalnya, jarak geodesic. Dalam representasi data
berdimensi rendah, diffusion
maps berupaya untuk mempertahankan jarak difusi dengan menggunakan teori spectral pada random walk, yang menunjukkan bahwa representasi data
berdimensi
37
rendah mempertahankan jarak difusi yang dibentuk oleh vector-vektor utama eigend nontrivial dari persamaan eigen. (2.15) Dikarenakan grafik sepenuhnya terhubung, maka nilai eigen terbesar adalah trivial (viz. eigen
), dan vektor
dibuang. Representasi data
berdimensi rendah
ditunjukkan oleh vektor – vektor eigen utama pada berikutnya. Dalam representasi data berdimensi rendah, vektor – vektor eigen dinormalisasikan oleh koresponden nilai – nilai eigen tersebut. Oleh karena itu, representasi data berdimensi rendah dapat ditunjukan oleh: (2.16)
Diffusion Maps telah berhasil diterapkan untuk, shape matching dan gene expression analysis. f.
M ultilayer Autoencoders Multilayer Autoencoders merupakan kemajuan dari jaringan saraf dengan suatu jumlah ganjil pada hidden layer. Hidden layer tengah memiliki node input dan output yang memiliki node
, dan layer
. Contoh dari suatu
38
autoencoder secara skematis ditunjukkan pada gambar berikut:
Gambar 2.7 S kema Multilayer Autoencoder
Jaringan dilatih untuk meminimalkan kesalahan rata – rata kuadrat antara input dan output pada suatu jaringan (idealnya, input dan output adalah sama). Pelatihan jaringan saraf pada datapoints
mengarah ke suatu
jaringan dimana hidden layer tengah menghasilkan representasi melindungi
dimensi dari datapoint – datapoint yang informasi
Representasi
di
sebanyak
mungkin.
berdimensi rendah dapat diperoleh dengan
mengekstraksi nilai node pada hidden layer tengah, ketika
39
datapoint
digunakan sebagai input. Fungsi aktivasi
linier jaringan saraf yang digunakan adalah sebuah autoencoder yang hampir serupa dengan PCA. Dengan tujuan membiarkan autoencoder untuk belajar suatu pemetaan nonlinear antara representasi data berdimensi tinggi dengan representasi data berdimensi rendah, dimana pada umumnya menggunakan fungsi aktivasi sigmoid. Dalam metode ini juga digunakan backpropagation untuk menyatukan koneksi secara perlahan namun cenderung terjebak dalam lokal minima. Kekurangan pendekatan tersebut dapat diatasi melalui pembelajaran prosedur yang terdiri dari tiga tahap utama. Tahap pertama, layer pengenalan dari jaringan (layer ke
) dilatih satu per satu menggunakan Restricted
Boltzmann Machines (RBM s). RBM s merupakan 2 layer jaringan saraf dengan node visual dan tersembunyi dimana keduanya adalah biner dan stokastik. RBMs dapat dilatih secara efisien menggunakan prosedur pembelajaran tidak terawasi yang meminimalkan perbedaan yang disebut kontrastif. Tahap kedua, layer rekonstruksi pada suatu jaringan (layerY ke X’) dibentuk oleh kebalikan dari layer
40
pengenalan terlatih. Dengan kata lain, autoencoder tidak tergulung. Tahap ketiga, autoencoder yang tidak tergulung merupakan finetuned dan diawasi dengan menggunakan backpropagation. Autoencoders telah berhasil diterapkan untuk masalah–masalah seperti imputasi data yang hilang dan analisis HIV. 2.4.1.2. Teknik Lokal Teknik yang mencoba untuk mempertahankan sifat lokal dari suatu data asli dalam representasi yang berdimensi rendah. Teknik lokal ini terbagi menjadi 4 sub bagian yaitu: a. Local Linear Embedding (LLE) Local Linear Embedding (LLE) merupakan suatu teknik lokal untuk reduksi dimensi yang mirip dengan Isomap dalam hal membangun sebuah representasi grafik dari datapoint. Berbeda dengan isomap, teknik ini mencoba untuk mempertahankan sifat lokal data. Sehingga menyebabkan LLE kurang sensitif tehadap hubungan short-circuiting. Dengan menggunakan LLE memungkinkan untuk sukses dalam embedding manifolds dalam nonconvex. Dalam LLE, Sifat lokal dibangun dengan mendapatkan datapoints dari kombinasi linear dari nearest neighbors yang ada. Algoritma LLE ini lebih mengupayakan untuk mempertahankan bobot rekonstruksi dalam
41
kombinasi linear sebaik mungkin. LLE mengambarkan sifat lokal manifold disekitar datapoint datapoint
(bobot) dari
yang dikombinasikan dengan nearest neighbors
yang dapat
ditulis sebagai berikut:
(2.17)
LLE biasa digunakan untuk membuat aplikasi seperti super resolution dan sound source locatization. Namun dari penelitian yang ada bisa di bilang kinerja LLE cukup lemah. b. Laplacian Eigenmaps M irip dengan LLE, teknik ini berusaha mendapatkan representasi data berdimensi rendah dengan menjaga property local dari manifold. Dalam Laplacian Eigenmaps sifat lokal di dapat berdasarkan jarak berpasangan antara nearest neighbors dengan memperhitungkan representasi data berdimensi rendah dari jarak antara datapoint dan
nearest neighbors seminimal
mungkin. Hal ini dilakukan untuk untuk meminimalisasi biaya fungsi dari eigen problem. Langkah pertama dari algoritma Laplacian Eigenmap adalah membangun sebuah lingkaran graf datapoin semua titik
terhubung dengan dan
dimana setiap
nearest neighbors. Untuk
yang terhubung dengan sebuah sisi
42
dalam graf
yang dihitung menggunakan fungsi Gaussian
Kernel. Fungsi yang digunakan untuk meminimalkan adalah sebagai berikut: (2.18) Kemudian untuk menghitung tingkat matriks grafik Laplacian
dari grafik
dan
dapat dirumuskan untuk
masalah minimasi dengan eigen problem. Grafik Laplacian dihitung dengan
, yang ditunjukan dalam
persamaan:
(2.19)
Persamaan ini memberitahu kita bahwa miminimalkan sebanding dengan meminimalkan
sehingga dapat
memecahkan masalah nilai eigen dengan persamaan: (2.20)
Eigenmaps Laplacian telah berhasil diterapkan untuk clustering, pengenalan wajah, analisis data fM RI dan semisupervised learning. c. Hessian LLE (HLLE) Hessian LLE (HLLE) merupakan modifikasi dari LLE yang meminimalkan ‘curviness’ dari manifold berdimensi
43
tinggi
ketika
embedding
menggunakan
eigen
ke
analysis
dimensi dari
rendah
dengan
matrik
yang
mengambarkan curviness dari manifold sekitar datapoint yang diukur dengan menggunakan hessian local pada setiap datapoint. Algoritma dari HLLE dimulai dengan mengidentifikasi neighbors nearest untuk setiap datapoint
menggunakan
Euclidean Distance. Sehingga basis untuk ruangan tangent local pada titik pada
dapat ditemukan dengan menerapkan PCA
neighbors nearest
basis datapoint
. Dengan kata lain, untuk setiap
di ruang ruang tangent local ditentukan
dengan menghitung
vektor eigen utama dari matriks kovarians
mengharuskan
dimana Dimana
.
Selanjutnya, estimator untuk hessian dari manifold pada titik
dalam kordinat ruang lokal dihitung untuk membentuk
matriks dari
dengan cara menggabungkan semua hasil silang sampai ke urutan ke
menerapkan
Normalisasi
. M atriks
Gram-Schmidt.
Estimasi
dari
diberikan dengan transpos dari
Hessian tangent
terakhir pada kolom matriks persamaan:
adalah matriks yang
. Nilai
dibangun dengan
44
(2.21) Dimana matriks
mewakili informasi tentang curviness
dari representasi data berdimensi tinggi pada data manifold yang berguna untuk menemukan representasi data berdimensi rendah yang minimal. Hessian LLE berhasil diterapkan dalam lokalisasi sensor. d. Local Tangent Space Analysis (LTSA) M erupakan teknik yang menggambarkan sifat lokal data berdimensi tinggi yang menggunakan lokal tangent dari masing-masing
datapoint.
LTSA
berupaya
untuk
menyelaraskan pemetaan-pemetaan linier sedemikian rupa dengan menbangun garis singgung lokal ruangan manifold dari representasi berdimensi rendah. Algoritma LTSA dimulai dengan komputasi basis untuk ruangan tangent lokal di datapoints
dengan menerapkan
PCA pada datapoint
pada
menghasilkan pemetaan
dari lingkungan dari
neighbors di
untuk ke tangen
lokal ruang i. LTSA melakukan minimisasi sebagai berikut: (2.22) Dimana pemusatan
adalah
matriks
dengan
ukuran
45
Yang menunjukkan solusi dari minimisasi dalam bentuk vektor - vektor eigen dari suatu matrik
yang
sesuai dengan nilai d eigen terkecil dari
yang
dirumuskan: (2.23) LTSA sukses digunakan untuk Micro-array data. Perbedaan mendasar dari beberapa teknik reduksi non-linear disajikan dalam tabel berikut : Tabel 2.1 Tabel Perbedaan Teknik Reduksi Non-Linear Teknik
Conveks
Parameters
MDS
Ya
Tidak ada
Isomap
Ya
Tidak ada
M VU
Ya
k
Kernel PCA
Ya
k(.,.)
Diffusion Maps
Ya
Autoencoders
Tidak
net size
LLE
Ya
k
Laplacian Eigenmaps
Ya
k,
Hessian LLE
Ya
k
LTSA
Ya
k
,k
Perhitungan
M emori
46
2.4.2. Teknik Reduksi Dimensi Linear Teknik linear melakukan reduksi dimensi dengan menempelkan data ke dalam suatu subruang dari dimensi yang lebih rendah. Pada subbab ini akan dibahas tiga teknik yang sering digunakan dalam reduksi dimensi linear, yaitu Pricipal Component Analysis (PCA), Linear Discriminant Analysis (LDA) dan Non-Negative Matrix Factorization (NM F). 2.4.2.1. Pricipal Component Analysis (PCA) Pricipal Component Analysis (PCA) atau disebut juga Transformasi Karhunen-Loeve adalah teknik yang digunakan untuk menyederhanakan suatu data, dengan cara mentransformasi linear sehingga terbentuk sistem koordinat baru dengan variansi maksimum. PCA dapat digunakan untuk mereduksi dimensi suatu data tanpa mengurangi karakteristik data tersebut secara signifikan. M etode ini mengubah dari sebagian besar variabel asli yang saling berkorelasi menjadi satu himpunan variabel baru yang lebih kecil dan saling bebas (tidak berkorelasi lagi). Komponen utama adalah kombinasi linier tertentu dari dimensi acak
. Secara geometris kombinas i
linier ini merupakan sistem koordinat baru yang didapat dari rotasi sistem semula. Koordinat baru tersebut merupakan arah
47
dengan variabilitas maksimum dan memberikan kovariansi yang lebih sederhana. Analisis komponen utama lebih baik digunakan jika variabel-variabel asal saling berkorelasi analisis komponen utama merupakan penyelesaian masalah eigen yang secara matematis ditulis dalam persamaan : (2.24) yang mana variabilitas suatu dataset yang dinyatakan dalam matriks kovariansi
dapat digantikan oleh suatu skalar tertentu
tanpa mengurangi variabilitas asal secara signifikan. Diberikan dataset matrik dari
berukuran
observasi
yang terdiri
dengan
dimensi.
Algoritma dari analisis komponen utama adalah sebagai berikut: dengan
a. Hitung vektor rata-rata
(2.25) b. Hitung matriks kovariansi atau
dengan (2.26)
c. Hitung nilai eigen
dan vektor eigen
yang memenuhi
persamaan : dan
(2.27)
d. Vektor eigen-vektor eigen yang didapatkan merupakan komponen utama-komponen utama untuk membentuk variabel baru.
48
Variabel-variabel baru merupakan perkalian antara vektor eigen
dengan matriks
, yaitu matriks
yang telah
dinormalisasi (adjusted) yang dihitung dengan rumus : (2.28) e. Sedangkan variansi yang dapat dijelaskan oleh variabel baru ke-i tergantung persentase kontribusi
dari masing-masing
nilai eigen, yang dihitung dengan rumus : (2.29) f. Sedangkan penentuan jumlah variabel baru yang digunakan tergantung persentase kontribusi kumulatif dari kumulatif nilai eigen yang telah diurutkan dari nilai yang terbesar. Nilai persentase kontribusi kumulatif sampai komponen ke– dihitung dengan rumus : (2.30) Dengan Walaupun hasil reduksi dari PCA menghasilkan ekstraksi fitur citra yang baik, tenyata citra yang dihasilkan masih memiliki dimensi yang tinggi.
49
2.4.2.2. Linear Discriminant Analysis (LDA) Linear Discriminant Analysis (LDA) merupakan metode yang cukup dikenal untuk fitur ekstraksi dan reduksi dimensi. LDA telah digunakan secara luas pada berbagai aplikasi seperti pengenalan
wajah.
LDA
bertujuan
untuk
menemukan
transformasi optimal dengan meminimumkan perbedaan rasio within-class dan memaksimumkan perbedaan rasio antara class. Berikut adalah algoritma untuk LDA: i.
Lakukan proses training untuk mendapatkan weight matrik
ii.
Transpose weight matrix untuk menjadi input dari LDA
iii.
Cari rata – rata dari
iv.
Cari
v.
Cari invers
vi.
Cari kovarian matriks Æ
dan
vii.
Cari
dan
viii.
Dapatkan fitur LDA Namun,
dari matrik
LDA
memiliki
keterbatasan
yakni
untuk
memperoleh transformasi optimal maka salah satu sebaran matriksnya harus non-singular. Pada kenyataannya, berbagai aplikasi seperti sistem pengenalan wajah, sebaran matriksnya
50
selalu singular, hal ini disebabkan dimensi matriks data pelatihan melampaui jumlah datanya. 2.4.2.3. Non-negative Matrix Factorization(NMF) Non-negative Matrix Factorization (NM F) merupakan salah satu bagian dari teknik reduksi yang bersifat linear dan dapat memperkirakan representasi data yang ada. NM F adalah suatu algoritma optimasi iterasi. Dimana modifikasi pada setiap iterasi fungsi basis non-negatif dan pengkodean mengalami konvergensi. NM F dapat diilustrasikan seperti berikut :
=
Gambar 2.8 Ilustrasi Teknik Non-negative Matrix Factorization NM F berguna untuk memperoleh citraan dari data nonnegatif. Dengan adanya bilangan bulat positif matriks
non-negatif
data matriks
dengan
dan
, NMF mendapatkan 2 dan
sehingga
didapatkan persamaan : (2.31) Dimana kolom
merupakan representatif pada suatu obyek
lalu memperkirakannya dengan kombinasi linier dari
basis
51
dalam kolom
. Setelah itu dilakukan pendekatan konvensional
untuk mendapatkan antara
dan
dan
dengan memperkecil perbedaan
dengan menggunakan norm Frobenius sehingga
didapatkan persamaan :
(2.32)
Ada beberapa pendekatan yang dapat digunakan untuk menyelesaikan persamaan diatas.Pendekatan paling populer adalah
algoritma Non-negative Matrix Factorization
with
multiplicative (Lee dan Seung, 2001).Selain itu ada algoritmaNonnegative Matrix Factorization with Gradient Descent, algoritma Non-negative Matrix Factorization with Least Square (ALS), dan algoritma Non-negative Matrix Factorization with Sparseness Contraints (Patrik O. Hoyer, 2002 ). a. Non-negative M atrix Factorization dengan multiplicative Algoritma Update Multiplicative dikenalkan pertama kali oleh Lee dan Seung pada tahun 2001. Algoritma Update Multiplicative dengan rata-rata kuadrat kesalahan fungsi objektif adalah sebagai berikut : Faktorisasi M atriks Non Negatif (dalam sintax M atlab):
Untuk
: maxiter
52
; ; dalam hukum update ditambahkan untuk mencegah pembagian dari nol. M enggunakan gradient dan sifat-sifat
kontinu
untuk
mengklaim bahwa algoritma
berkonvergen terhadap suatu minimum lokal yang kemudian memperlihatkan bahwa hal itu tidak terbukti. Pembuktian memperlihatkan
sifat-sifat
kontinu
yang tidak
sesuai
penjelasannya terhadap titik pelana. Untuk memahami hal tersebut, kita harus mempertimbangkan dua dasar observasi yang melibatkan kondisi optimal Karush-Khun Tucker. Pertama, matriks awal
dan
positif dan kemudian
matriks ini akan tetap positif sepanjang iterasi. Hal ini dapat diverifikasi dengan membandingkan terhadap bentuk aturan multiplicative update. Kedua, jika urutan iterasi dan
dan
dan
,
= 0
= 0. Hal ini dapat diverifikasi terhadap
, dimana :
konvergen terhadap
53
Perhatikan elemen dicapai sehingga
dari
. Jika titik limit untuk
, maka
dapat dicari dengan
persamaan : (2.33) Kondisi optimum dapat dicapai untuk titik limit jika tidak memiliki suatu elemen yang bernilai 0.
Namun, jika semua elemen dapat konvergen terhadap nilai limit dari 0 dengan maka mungkin saja bahwa nilai
terhadap . Dalam hal ini, maka
akan mengalami kondisi kelambanan dalam mencari yang sebanding dan akan muncul kondisi diluar hukum update multiplicative, dimana
.
Dalam algoritma Update Multiplicative Lee dan Seung ini, dapat kita simpulkan bahwa:
54
Bila algoritma konvergen terhadap titik limit di dalam interior dari daerah fisibel, titik ini adalah suatu titik tetap. Titik stasionaire ini dapat atau tidak dapat berupa suatu lokasi minimum. Bila titik limit berada pada batas dari daerah fisibel, maka titik tetapnya tidak dapat ditentukan. Algoritma Update Multiplicative ini telah berulang kali digunakan sebagai algoritma pembanding terhadap algoritma-algoritma yang lebih baru. Algoritma ini terbukti memerlukan waktu yang sangat lama dalam berkonvergensi dan memerlukan banyak iterasi (karena memerlukan kerja ) dibandingkan dengan algoritma yang lain, seperti algoritma Descent Gradient dan algoritma ALS. b. Non-negative M atrix Factorization dengan Gradient Descent Algoritma NM F yang kedua ini didasarkan pada metode penurunan gradient. Algoritma penurunan gradient dasar untuk NMF adalah (dalam sintax M atlab) : % inisialisasi W ;% inisialisasi H Untuk i = 1: maxiter
55
Ukuran parameter dari
dan
berubah tergantung
pada algoritma turunan parsialnya. Algoritma ini selalu mengambil suatu langkah di dalam arah gradient negatif dari penurunan yang paling tajam. A gar membuat tiap elemen dari matriks update
dan
dari pendekatannya menjadi negatif,
maka setiap hukum update, matriks update diproyeksikan terhadap elemen-elemen negatif mendekati nilai-nilai non negatif 0. Algoritma Gradient Descent ini sangat sensitif terhadap inisialisasi
dan
. Jika menggunakan inisialisasi acak,
metode ini akan mengalami konvergensi ke suatu faktorisasi yang tidak terlalu jauh dari nilai matriks awal. Dalam perkembangannya, ada satu metode, yaitu M etode Shepherd yang diperkenalkan oleh Chu et al pada tahun 2004. M etode ini merupakan perkembangan dari teknik gradient descent yang dapat mempercepat konvergensi dengan menggunakan pilihan yang bijak untuk stepsize tersebut. Sayangnya, teori konvergensi untuk mendukung metode ini agak kurang. c. Non-negative M atrix Factorization dengan Least Square (ALS) Algoritma Least Square (ALS) merupakan salah satu algoritma NM F yang menggunakan kuadrat terkecil yang diikuti oleh kuadrat terkecil yang lain secara bergantian.
56
Algoritma ini pertama kali digunakan oleh Paatero pada tahun 1994. Algoritma dasar dari ALS adalah sebagai berikut (dalam sintax M atlab):
Untuk i = 1: maxiter (LS)
Solver untuk H pada persamaan matriks W TWH = W TA
(NONNEG)
Set semua elemen negatif di H menjadi 0
(LS)
Solver untuk W pada persamaan matriks HH TW T = HA T
(NONNEG)
Set smua elemen negatif di W menjadi 0
Dalam
pseudocode
diatas,
sudah
kepastian bahwa tidak ada unsur negatif pada
memiliki dan
,
karena semua elemen negatif yang dihasilkan dari kuadrat terkecil di set menjadi 0. Algoritma ini juga memiliki beberapa keuntungan. Pada algoritma ini memungkinkan beberapa fleksibilitas iterasi tambahan yang tidak tersedia dalam algoritma lain, terutama dari algoritma update multiplicative. Salah satu kekurangan dari algoritma multiplicative adalah bahwa setelah unsur di
atau
menjadi 0, maka akan tetap 0.
Sehingga jika algoritma mulai menuju titik tetap, walaupun jika itu adalah titik tetap yang buruk, algoritma tersebut harus terus berjalan.
57
Pada Algoritma ALS ini, dapat lebih fleksibel, sehingga memungkinkan proses iteratif untuk melepaskan diri dari jalan yang buruk. d. Non-negative
M atrix
Factorization
dengan
Sparseness
Contraints (NMFSC) M enurut Patrik O. Hoyer (2002) Non-Negative Matrix Factorization merupakan bagian dari reduksi dimensi yang bersifat linear dengan memperkirakan representasi data yang ada. NMF dapat diasumsikan sebagai sebuah data yang terdiri dari pengukuran menunjukan
dalam
non-negatif variable skalar yang
( -dimensi)
pengukuran
vektor
. Adapun pendekatan linear dari data yang diberikan adalah sebagai berikut : (2.34) dimana
adalah matriks
berisi vektor - vektor basis
sebagai kolom - kolomnya. Dapat dilihat bahwa setiap perhitungan vektor ditulis dalam bentuk vektor – vektor basis yang sama. Dasar vektor
dalam
dapat dianggap sebagai
‘building blocks’ dari suatu data dan ( -dimensi) koefisien vektor
menjelaskan bagaimana kuatnya setiap blok
bangunan dalam pengukuran vektor
.
58
Pengukuran vektor matriks
dalam suatu kolom dari sebuah
dapat ditulis seperti pada persamaan (2.31).
Dimana setiap kolom H berisi koefisien vektor berkoresponden dengan vektor pengukuran
yang
. Pada bentuk
ini, terlihat jelas bahwa representasi data linear merupakan sample faktorisasi dari suatu matriks data. Perlu diingat matriks data optimal dari matriks
dan
, harus dipilih yang paling . Hal ini berkaitan dengan
definisi NM F yaitu meminimalkan kesalahan rekonstruksi antara
dan
. Berbagai kesalahan fungsi telah diusulkan
(Paatero dan Tapper,1994; Lee dan seung, 2001), dan yang paling banyak digunakan adalah Euclidean Distance: (2.35)
M eskipun masalah minimisasi terfokus di
dan
secara
terpisah, akan tetapi sebenarnya permasalahan yang timbul tidak terfokus di keduanya secara bersamaan. Paatero dan Tapper (1994) memberikan algoritma gradien untuk optimasi ini, sedangkan Lee dan Seung (2001) merancang algoritma perkalian yang lebih mudah untuk diterapkan dengan kinerja yang baik.
59
Konsep sparseness dalam metode Hoyer mengacu pada skema representasi dimana hanya beberapa unit (dari populasi besar) secara efektif digunakan untuk mewakili data khas vektor
sehingga
mengakibatkan
sebagian
besar
unit
mengambil nilai mendekati nol sementara hanya sebagian kecil unit mengambil nilai diluar nol secara signifikan. Sampai saat ini, banyak langkah penyebaran telah diusulkan dan digunakan dalam suatu literatur. Seperti cara pemetaan dari
untuk
yang mengukur berapa banyak
energi dari sebuah vektor dikemas ke dalam beberapa komponen.
Pada
skala
normal,
kemungkinan
vektor
sparseness (hanya satu komponen adalah non - nol) harus memiliki satu sparseness, sedangkan vektor dengan semua elemen yang sama harus memiliki sparseness dari nol. Dalam metode ini, kami menggunakan ukuran penyebaran yang didasarkan pada hubungan norm
dan
:
(2.36) adalah dimensi dari
Dimana
. Fungsi diatas
berguna untuk menyatukan jika dan hanya jika
berisi hanya
komponen tunggal non-nol, dan mengambil nilai nol jika dan hanya jika semua komponen yang sama (hingga tanda-tanda) dan, interpolasi antara dua ekstrem berjalan lancar.
60
Tujuan NM F dengan Sparseness Constraints adalah untuk membatasi NM F apabila menemukan solusi dengan derajat sparseness yang diinginkan sehingga
dan
yang
tersebar menandakan bahwa setiap objek tertentu hadir dalam beberapa citra dan hanya mempengaruhi sebagian kecil dari citra yang ada. Pertimbangan ini menuntun kita untuk mendefinisikan NM F dengan kendala kekurangan bahwa dari data nonnegatif matriks non-negatif
ukuran dan
dapat diperoleh matriks
dari ukuran
dan
(masing-masing) sehingga : (2.37) diminimalkan, dengan batas-batas :
Dimana dari
adalah kolom ke- dari . Di sini,
sedangkan
dan
masing-masing
dan
adalah baris ke-
menunjukkan jumlah komponen, adalah penyebaran yang diinginkan dari dan
. Ketiga parameter tersebut
ditetapkan oleh pengguna. Perlu diperhatikan bahwa dalam metode ini membatasi
skala
atau
.
Namun,
tidak
dikarenakan
61
maka kita dapat dengan bebas untuk memperbaiki salah satu norm yang ada. Dengan demikian algoritma ini membuat kita memilih untuk memperbaiki norm untuk disatukan. Algoritma yang dirancang oleh Hoyer adalah sebuah algoritma turunan gradien yang diproyeksikan untuk NMF dengan kendala sparseness. Berikut algoritma untuk Nonnegative Matrix Factorization with Sparseness Contraints : Algorithm: NMF dengan sparseness constraints (1)
M enginisialisasi matriks positif
(2)
Jika ada sparseness constraints pada kolom dari
dan
secara acak , maka ubah setiap
menjadi non-negatif, dengan syarat
memiliki norm
yang tidak berubah, sedangkan norm
diatur untuk mencapai sparseness yang diinginkan. (3)
Jika ada sparseness constraints pada , maka ubah setiap baris dari
menjadi non-negatif, dengan syarat yang
memiliki unit norm
dan
diatur untuk mencapai
sparseness yang diinginkan. (4)
Iterasi a. Jika ada sparseness constraints di W i.
Set
62
ii.
Ubah setiap kolom dari W untuk menjadi non-negatif, yang memiliki norm
yang
tidak berubah, sedangkan norm
diatur
untuk
mencapai
sparseness
yang
diinginkan Selain itu dilakukan langkah perkalian standar :
b. Jika ada sparseness constraints di H i.
Set
ii.
Ubah setiap baris dari
agar menjadi non-
negatif, dengan ketentuan yang memiliki unit norm
dan
diatur untuk mencapai
sparseness yang diinginkan. Selain itu dilakukan langkah perkalian standar
Pada algoritma di atas,
dan
masing-masing
menunjukan perkalian dan pembagian element wise.Selain itu, dan
adalah konstanta positif kecil (stepsizes) yang
algoritmanya harus diatur dengan benar untuk dapat bekerja dengan baik. Namun itu tidak perlu diatur sendiri oleh
63
pengguna karena dalam algoritma ini otomatis menyesuaikan parameter tersebut.langkah ini diambil dari algoritma Lee dan Seung (2001). 2.5
Aplikasi Face Recognition Pada sub-bab ini penulis akan menjelaskan aplikasi yang berguna dalam metode pengenalan citra wajah (face recognition). Aplikasi yang akan penulis jelaskan adalah sistem absensi pegawai menggunakan Face Recognition. Aplikasi ini tidak menggunakan sidik jari (fingerprint) sebagai bahan pencocokan, melainkan menggunakan gambar wajah pegawai yang terekam dalam kamera. M ekanismenya cukup sederhana, yakni hanya dengan menghadap kamera dan kemudian aplikasi akan mencocokkan wajah pegawai dengan face database yang sebelumnya telah diinput ke dalam aplikasi. Sistem absensi pegawai menggunakan Face Recognition ini memiliki beberapa kelebihan sebagai berikut:
a.
Sistem Face Recognition dapat mengidentifikasi dengan baik walaupun seseorang menggunakan kacamata maupun tidak.
b.
Sistem Face Recognition tidak dapat mengidentifikasi seseorang hanya dengan menggunakan foto dirinya yang dihadapkan ke kamera. sehingga pegawai tidak dapat melakukan manipulasi dengan menitipkan fotonya kepada pegawai lain untuk melakukan absensi.
c.
Sistem Face Recognition tetap dapat mengidentifikasi wajah apabila terjadi perubahan detil wajah seperti kumis dan jenggot yang tidak terlalu
64
ekstrim. Apabila perubahan tersebut terlalu ekstrim dan tidak sulit diidentifikasi sistem, maka wajah pegawai tersebut harus dicapture ulang untuk disimpan kembali ke dalam database sistem.
2.5.1
Flowchart dan Cara Kerja S istem Start
Camera Capturing
Yes
Tracking ?
Tracking Processing
No NMF Processing Final Result
End
Gambar 2.9 Flowchart sistem secara sederhana Cara kerja sistem absensi ini terbagi menjadi beberapa bagian, yaitu : 1. Camera Capturing Camera Capturing merupakan proses melakukan pengambilan gambar yang berasal dari kamera. Dalam proses ini terdiri dari dua sub program, yang pertama adalah proses untuk menerima input dari kamera
65
dan yang kedua adalah proses untuk melakukan pengambilan frame dari input tersebut. 2. Haar Tracking Haar Tracking merupakan salah satu metode untuk melakukan proses tracking pada bagian dari citra yang ditangkap melalui kamera. Pada program ini fungsi tersebut akan dipakai untuk melakukan tracking wajah dari citra yang sudah ditangkap oleh kamera.
