8  

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. Memperbaiki kualitas suatu citra, sehingga dapat lebih mudah

diinterpretasikan oleh mata manusia.

b. Mengolah 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 dalam suatu citra.

9  

  

c. Mengompres 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 secara matematis

dimana dan adalah koordinat spasial dan nilai 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 (baris/tinggi = ,

kolom/lebar = ).

= 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.Masing-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. Metode

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 t idak

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  

  

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 variable-

length 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

Input Image

 

Compressed File Encoding Preprocessing

Compressed File

Decoding Postprocessing Decoded Image

 

Kompresi

Dekompresi

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. Macam-macam dari

scalability:

i. Quality progressive: dimana citra dikompres secara perlahan-

lahan 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. Meta 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. Metode 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. Manipulasi

disini berupa pengurangan nilai presisi integer pada karakter citra.

20  

  

2.2.3. Metode Kompresi Citra

a. Metode Huffman

Metode 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. Metode Run Length Encoding (RLE)

Cocok digunakan untuk memampatkan citra yang memiliki

kelompok-kelompok piksel berderajat keabuan yang sama. Metode

ini dilakukan dengan menyatakan seluruh baris citra menjadi sebuah

baris run, lalu menghitung run-length untuk setiap derajat keabuan

yang berurutan. Metode RLE dapat dikombinasikan dengan metode

Huffman untuk meningkatkan ratio kompresi.Mula-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 (Morlet

dan Grossman, 1980). Transformasi DWT digunakan untuk

mentransformasi citra menjadi beberapa koefisien wavelet.

Selanjutnya koefisien wavelet ini ditanam 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

Memori 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 MSE (Mean Square Error) dan juga nilai PSNR (Peak

Signal-to-Noise Ratio). Perhitungan nilai MSE 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 MSE

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. Manusia 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. Memperoleh atau mengakuisisi citra digital

b. Melakukan teknik komputasi untuk memproses atau memodifikasi data citra

(operasi-operasi pengolahan citra).

c. Menganalisis 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 fMRI,

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 berukuran ( ) yang terdiri dari data

dengan dimensi yang memiliki dimensi intrinsik (dimana , dan

terkadang ). Dalam istilah matematika, dimensi intrisik dapat diartikan

sebagai titik – titik dalam dataset yang berada disebuah manifold dengan

dimensi yang tertanam di dimensi ruang . Teknik reduksi dimensi mengubah

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 :

Gambar 2.6 Diagram pembagian teknik reduksi dimensi

Dimensionality Reduction 

Nonlinear 

Neighborhood graph 

Laplacian 

Alignment of lokal 

representations 

linear 

Neural   network  

Preserving global properties  Preserving lokal properties 

Kernel‐based 

Unfolding  Reconstruction weights 

Lokal tangent space 

Distance preservation 

PCA 

LLCChar

NMF 

Kernel PCA 

MVU Autoencoder 

MDS, Isomap Diff.map

s 

LLE  Laplacian Eigenmaps 

LTSA Hessian LEE 

LDA 

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. Multi Dimensional Scaling (MDS)

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 adalah jarak Euclidean antara

datapoints dan berdimensi tinggi, dan adalah

jarak Euclidean antara datapoints dan berdimensi

rendah.

MDS banyak digunakan untuk visualisasi data,

misalnya, dalam fMRI analisis dan dalam pemodelan

molekul.Popularitas MDS telah menyebabkan usulan

varian seperti SPE, CCA, SNE, dan FastMap. Selain itu,

terdapat varian nonmetric MDS, yang bertujuan untuk

menunjukkan hubungan ordinal dalam data, bukan jarak

berpasangan.

b. Isomap

Isomap adalah sebuah teknik reduksi dimensi non-

linear 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 dihitung dengan

membangun graph G yang berdekatan, dimana setiap

datapoint terhubung dengan k yang paling berdekatan

dengan di dataset . 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 berdimensi rendah dari

datapoints di ruang 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. Maximum Variance Unfolding(MVU)

Maximum Variance Unfolding (MVU) 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 MVU berbeda

dengan Isomap. Dimana MVU melakukan hal tersebut

dengan memaksimalkan Euclidean Distance antara

datapoints, dalam batasan bahwa jarak dalam lingkaran

grafik yang tersisa tidak berubah. Masalah optimisasi yang

dihasilkan dapat diselesaikan secara efisien dangan

menggunakan pemrograman semidefinite.

Algoritma MVU dimulai dengan pembangunan

lingkaran grafik , dimana setiap datapoint terhubung ke

yang merupakan neighbors terdekat dari . Selanjutnya,

upaya MVU untuk memaksimalkan jumlah jarak kuadrat

Euclidean antara semua datapoints, di bawah batasan

bahwa jarak disekitar grafik G dipertahankan. Dengan kata

lain, MVU melakukan optimasi masalah berikut:

(2.6)

Dimana :

(2.7)

Dari persamaan di atas MVU 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

MVU, karena menambah batasan ke dalam masalah

optimasi untuk mencegah terjadinya unfolding dari suatu

manifold. Meskipun demikian, MVU berhasil diterapkan

untuk, lokalisasi misalnya, sensor dan DNA microarray

analisis data.

d. Kernel PCA (KPCA)

Merupakan 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)

Dimana menunjukan nilai ke j dalam vector 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 bahwa

ukuran dari matriks kernel sebanding dengan kuadrat dari

jumlah hal dalam dataset.

e. Diffusion Maps

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 dari Gaussian.

Selanjutnya, normalisasi matriks dilakukan sedemikian

rupa dimana baris – barisnya ditambahkan menjadi 1.

Dengan cara ini, Matriks dibentuk dengan

persamaan:

(2.12)

Matriks yang dihasilkan dianggap sebagai

matriks Markov 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 matrix

untuk timesteps ditunjukkan dengan .

36  

  

Menggunakan 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 yang

didefinisikan dengan . Dari 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. ), dan vektor

eigen 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. Multilayer Autoencoders

Multilayer Autoencoders merupakan kemajuan dari

jaringan saraf dengan suatu jumlah ganjil pada hidden

layer. Hidden layer tengah memiliki node , dan layer

input dan output yang memiliki node . Contoh dari suatu

38  

  

autoencoder secara skematis ditunjukkan pada gambar

berikut:

Gambar 2.7 Skema 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 dimensi dari datapoint – datapoint yang

melindungi informasi di sebanyak mungkin.

Representasi 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 (RBMs). RBMs 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 yang dikombinasikan dengan

datapoint (bobot) dari 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

Mirip 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 dimana setiap

datapoin terhubung dengan nearest neighbors. Untuk

semua titik dan 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 dan

grafik Laplacian dari grafik 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 fMRI dan semi-

supervised learning.

c. Hessian LLE (HLLE)

Hessian LLE (HLLE) merupakan modifikasi dari LLE

yang meminimalkan ‘curviness’ dari manifold berdimensi

43  

  

tinggi ketika embedding ke dimensi rendah dengan

menggunakan eigen analysis dari 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 dapat ditemukan dengan menerapkan PCA

pada neighbors nearest . Dengan kata lain, untuk setiap

basis datapoint di ruang ruang tangent local ditentukan

dengan menghitung vektor eigen utama dimana

dari matriks kovarians Dimana

mengharuskan .

Selanjutnya, estimator untuk hessian dari manifold pada

titik dalam kordinat ruang lokal dihitung untuk membentuk

matriks dengan cara menggabungkan semua hasil silang

dari sampai ke urutan ke . Matriks adalah matriks yang

menerapkan Normalisasi Gram-Schmidt. Estimasi dari

Hessian tangent diberikan dengan transpos dari

terakhir pada kolom matriks . Nilai dibangun dengan

persamaan:

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)

Merupakan 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 neighbors di untuk

menghasilkan pemetaan dari lingkungan dari ke tangen

lokal ruang i. LTSA melakukan minimisasi sebagai berikut:

(2.22)

Dimana adalah matriks dengan ukuran

pemusatan

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 Perhitungan Memori

MDS Ya Tidak ada

Isomap Ya Tidak ada

MVU Ya k

Kernel PCA Ya k(.,.)

Diffusion Maps Ya ,k

Autoencoders Tidak net size

LLE Ya k

Laplacian Eigenmaps Ya k,

Hessian LLE Ya k

LTSA Ya k

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 sub-

bab 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

(NMF).

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. Metode 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 berukuran yang terdiri

dari observasi dengan dimensi.

Algoritma dari analisis komponen utama adalah sebagai berikut:

a. Hitung vektor rata-rata dengan

(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 dan

v. Cari invers

vi. Cari kovarian matriks vii. Cari dan dari matrik

viii. Dapatkan fitur LDA

Namun, 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 (NMF) merupakan

salah satu bagian dari teknik reduksi yang bersifat linear dan

dapat memperkirakan representasi data yang ada. NMF adalah

suatu algoritma optimasi iterasi. Dimana modifikasi pada setiap

iterasi fungsi basis non-negatif dan pengkodean mengalami

konvergensi. NMF dapat diilustrasikan seperti berikut :

=

Gambar 2.8 Ilustrasi Teknik Non-negative Matrix Factorization

NMF berguna untuk memperoleh citraan dari data non-

negatif. Dengan adanya data matriks dengan dan

bilangan bulat positif , NMF mendapatkan 2

matriks non-negatif 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 dan dengan memperkecil perbedaan

antara dan 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 algoritmaNon-

negative 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 Matrix 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 Matriks Non Negatif (dalam sintax Matlab):

Untuk : maxiter

52  

  

;

;

dalam hukum update ditambahkan untuk

mencegah pembagian dari nol. Menggunakan 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 konvergen terhadap

dan dan , = 0

dan = 0. Hal ini dapat diverifikasi terhadap

, dimana :

53  

  

Perhatikan elemen dari . Jika titik limit untuk

dicapai sehingga , 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 terhadap

maka mungkin saja bahwa nilai . 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 Matrix Factorization dengan Gradient Descent

Algoritma NMF yang kedua ini didasarkan pada metode

penurunan gradient. Algoritma penurunan gradient dasar

untuk NMF adalah (dalam sintax Matlab) :

% 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. Agar 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 Metode Shepherd

yang diperkenalkan oleh Chu et al pada tahun 2004. Metode

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 Matrix Factorization dengan Least Square (ALS)

Algoritma Least Square (ALS) merupakan salah satu

algoritma NMF 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 Matlab):

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 HHTW T = HAT

(NONNEG) Set smua elemen negatif di W menjadi 0

Dalam pseudocode diatas, sudah memiliki

kepastian bahwa tidak ada unsur negatif pada 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 Matrix Factorization dengan Sparseness

Contraints (NMFSC)

Menurut 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 dalam non-negatif variable skalar yang

menunjukan ( -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 dalam suatu kolom dari sebuah

matriks dapat ditulis seperti pada persamaan (2.31).

Dimana setiap kolom H berisi koefisien vektor yang

berkoresponden dengan vektor pengukuran . Pada bentuk

ini, terlihat jelas bahwa representasi data linear merupakan

sample faktorisasi dari suatu matriks data.

Perlu diingat matriks data , harus dipilih yang paling

optimal dari matriks dan . Hal ini berkaitan dengan

definisi NMF 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)

Meskipun 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)

Dimana adalah dimensi dari . 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 NMF dengan Sparseness Constraints adalah

untuk membatasi NMF 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

NMF dengan kendala kekurangan bahwa dari data non-

negatif matriks ukuran dapat diperoleh matriks

non-negatif dan dari ukuran dan

(masing-masing) sehingga :

(2.37)

diminimalkan, dengan batas-batas :

Dimana adalah kolom ke- dari dan adalah baris ke-

dari . Di sini, menunjukkan jumlah komponen,

sedangkan dan adalah penyebaran yang diinginkan dari

masing-masing dan . Ketiga parameter tersebut

ditetapkan oleh pengguna.

Perlu diperhatikan bahwa dalam metode ini tidak

membatasi skala atau . Namun, 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 Non-

negative Matrix Factorization with Sparseness Contraints :

Algorithm: NMF dengan sparseness constraints

(1) Menginisialisasi matriks positif dan secara acak

(2) Jika ada sparseness constraints pada , maka ubah setiap

kolom dari 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. Mekanismenya 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

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

Camera Capturing 

Start 

Tracking ?  Yes  Tracking Processing 

No 

NMF Processing 

Final 

Result 

End 

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.