BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

Pada bab ini akan diperlihatkan teori-teori yang berhubungan dengan penelitian ini sehingga dapat dijadikan sebagai landasan berfikir dalam melakukan penelitian ini dan akan mempermudah dalam hal pembahasan hasil utama pada bab berikutnya. Teori tersebut mencakup pengertian dari pengenalan pola secara statistika (statistical pattern recognition), contoh statistical pattern recognition, matriks kovarians, contoh matriks kovarians, nilai eigen dan vektor eigen,contoh nilai eigen dan vektor eigen, analisis diskriminan linier, analisis diskriminan linier 2-dimensi dan analisis diskriminan linier 2-dimensi simetris.

2.1 Pengenalan Pola Secara Statistika (Statistical Pattern Recognition) Pengenalan pola atau dikenal dengan sebutan pattern recognition merupakan salah satu cabang ilmu sains. Pengenalan pola pada dasarnya adalah suatu sistem yang tujuannya adalah mengklasifikasikan objek-objek ke dalam kategori-kategori atau kelas-kelas berdasarkan baik pada apriori pengetahuan atau pada informasi statistik yang diambil dari pola (Theodoridis, 2003).

Fukunaga (1990) menyajikan cara-cara dasar perhitungan matematika untuk proses pembuatan keputusan secara statistik dalam pengenalan pola. Tujuan utama pattern recognition adalah mengklarifikasikan mekanisasi sulit yang sering ditemukan dalam dunia sehari-hari seperti langkah dalam permainan catur didasarkan pada pola yang ada di papan catur, pembelian atau persediaan penjualan diputuskan melalui suatu pola informasi yang kompleks. Sebagian besar aplikasi-aplikasi penting

Universitas Sumatera Utara

12 dalam pattern recognition dikarakterkan ke dalam satu bentuk kurva atau pola gambar geometri. Sebagai contoh, pengetesan suatu mesin layak atau tidak menampilkan pola berbentuk kurva. Masalah ini mereduksi untuk pemisahan kurva dari mesin yang bagus dan yang tidak bagus. Pada contoh lain, pengenalan pola huruf hasil cetak tulisan tangan diklasifikasikan dalam bentuk gambar geometri. Dalam proses untuk pengklasifikasiannya, pertama kita ukur karakteristikkarakteristik pengamatan dari sampel. Kemudian, ekstrasi seluruh informasi yang terdapat dalam sampel untuk menghitung nilai sampel-waktu untuk suatu pola berbentuk kurva, x(t1 ),..., x(tn ) , dan tingkat kehitaman piksel untuk suatu figur, x(1),..., x(n) seperti yang ditunjukkan dalam gambar 2.1.

x(t)

Pixel #1

... 0 t1 t2 t3

t

tn-1 tn

Pixel #n (b)

(a)

Gambar 2.1: Contoh dua pengukuran pola (a) gelombang (b) huruf Karena input dari pengenalan pola merupakan suatu vektor acak dengan n peubah, maka, baik untuk pola berbentuk gelombang ataupun huruf, keduanya diekspresikan ke dalam bentuk vektor dalam suatu ruang dimensi-n. Sebagai contoh, pengamatan x(i) bervariasi dari huruf A yang satu ke huruf A yang lainnya dan oleh karena itu, x(i) merupakan suatu variabel acak, dan X merupakan vektor acak.

2.1.1 Vektor Acak dan Distribusinya Seperti yang telah didiskusikan pada bagian 2.1, input dari jaringan pengenalan pola merupakan suatu vektor acak dengan n peubah sebagai berikut X=  x1x 2 ...x n 

T

(2.1)


13 dimana T adalah transpos dari vektor. Suatu vektor acak dapat dikarakterisasikan oleh suatu fungsi distribusi peluang, yang didefinisikan oleh

P ( x1 , . . ., xn )  Pr x1  x1 , . . ., x n  xn



(2.2)

(Fukunaga, 1990) Selain itu, suatu vektor acak mempunyai suatu paramater distribusi. Parameter distribusi yang akan dibahas dalam penelitian ini adalah matriks kovarians.

2.1.2 Matriks Kovarians Matriks kovarians S adalah matriks kovarians sampel yang didefinisikan sebagai berikut: S = E [ Xi – Mi ] [ Xi – Mi ]T (Fukunaga, 1990)

(2.3)

Xi adalah data pada masing-masing kelas, Mi adalah rata-rata kelas ke-i. Matriks kovarians S berisi nilai varians pada diagonal utama sebanyak p variabel dan nilai kovarians pada elemen lainnya sebanyak p – 1 kovarians. Suatu matriks  dikatakan matriks kovarians populasi jika matriks tersebut adalah matriks simetris yang diagonalnya harus berisi elemen-elemen nonnegatif sehingga matriks tersebut merupakan matriks definit nonnegatif. Jika Ai = [ ai1, ai2, . . ., ain]T mempunyai rata-rata kelas M i 

1 ni

n

 a , maka i 1

i

untuk melihat betapa dekatnya korelasi antar kelas, harus diatur agar masing-masing nilai mempunyai jumlah selisih rata-rata sama dengan 0, yaitu dengan cara mengurangi setiap ai dengan rata-rata kelasnya. Kemudian menempatkan nilai-nilai tersebut ke dalam sebuah matriks seperti berikut:

X

 a11  M 1  a1n  M n        a  M  a  M  1 nn n  n1


14  a11  M 1  a1n  M n  1   S     n 1     a M  a M 1 nn n  n1

T

 a11  M 1  a1n  M n        a  M  a  M  1 nn n  n1

(2.4)

Komponen diagonal dari matriks kovarians adalah varians dari masing-masing kelas peubah acak. Untuk lebih jelasnya tentang matriks kovarians, perhatikan contoh 2.1.2 berikut. Contoh 2.1.2 Diketahui suatu data nilai 7 mahasiswa meliputi nilai tugas rumah, ujian dan ujian akhir sebagai berikut. Mahasiswa

Nilai Tugas Rumah

Ujian

Ujian Akhir

MH 1

198

200

196

MH 2

160

165

165

MH 3

158

158

133

MH 4

150

165

91

MH 5

175

182

151

MH 6

134

135

101

MH 7

152

136

80

Rata-rata

161

163

131

Dari data pada contoh 2.1.2 akan diperlihatkan bagaimana kinerja mahasiswa dengan membandingkan antara kelompok ujian atau nilai tugas. Agar terlihat betapa dekatnya dua kelompok nilai saling berkorelasi, harus diatur agar masing-masing nilai tersebut mempunyai rata-rata sama dengan 0, yaitu dengan cara mengurangi setiap nilai dalam kolom dengan rata-rata nilai pada kolom yang sama sehingga nilai yang telah ditranslasikan ini akan mempunyai jumlah selisih atau deviasi terhadap rata-rata sama dengan 0. Kemudian, tempatkan nilai-nilai yang telah ditranslasikan tersebut ke dalam matriks


15  37   -1  -3   -11  14   -27  -9 

37 2 -5 2 19 -28 -27

65   34  2  -40  20   -30  -51 

Jika terdapat lebih dari dua kelompok data, maka dapat dibentuk sebuah matriks X dimana kolom-kolomnya memperlihatkan simpangan dari rata-rata untuk setiap kelompok dan kemudian membentuk sebuah matriks kovariansi S dengan menetapkan S

1 T X X n -1

Matriks kovariansi untuk ketiga kelompok data nilai matematika adalah 65   37 37   2 34   1 2   37 1 3 11 14 27 9   3 5 1   S   37 2 5 2 19 28 27   11 2 40  6  20   65 34 2 10 20 30 51   14 19   27 28 30   9 27 51    

 417, 7 4375,5 725, 7   437,5 546,0 830,0     725, 7 830,0 1814,3   

Entri-entri diagonal matriks S adalah variansi untuk ketiga kelompok nilai dan entrientri di luar diagonal adalah kovariansi-kovariansi.

2.1.3 Nilai Eigen dan Vektor Eigen Definisi. Anggap A adalah suatu matriks n × n. Skalar  disebut sebagai suatu nilai eigen atau nilai karakteristik dari A jika terdapat suatu vektor tak nol x, sehingga Ax =

x. Vektor x disebut vektor eigen dari A yang berasosiasi dengan  (Horn and Johnson, 1985).


16 Untuk mengetahui lebih jelas mengenai nilai eigen dan vektor eigen, perhatikan contoh 2.1.3 berikut.

Contoh 2.1.3 Misalkan

3 2   -1 A dan x    .   3 -2  3

Karena

 3 2   -1  3   -1 Ax          -3    -3x ,  3 -2   3   -9  3

dari penyelesaian contoh soal di atas terlihat bahwa  = -3 adalah nilai eigen dari A

 -1 dan x =   merupakan vektor eigen yang berasosiasi dengan  = -3. 3

Hasil Kali dan Jumlah Nilai Eigen Jika p() adalah polinom karakteristik dari matriks A yang berorde n × n, maka

p ( )  det( A   I ) 

a11   a21  an1

a12  a12   an 2

a1n a2 n

(2.5)

ann  

Dengan menguraikan determinan sepanjang kolom pertama, diperoleh n

det( A -  I )  (a11 -  ) det( M 11 )   ai1 (-1)i 1 det( M i1 ) i 1

di mana minor-minor Mi1, i = 2, . . ., n tidak mengandung kedua elemen diagonal (aii   ) . Dengan menguraikan det(M11) dengan cara yang sama, dapat disimpulkan

bahwa

(a11   )(a22   )...(ann   )

(2.6)

adalah satu-satunya suku dalam ekspansi det( A   I ) yang menyebabkan suatu hasil kali lebih dari n – 2 elemen diagonal. Jika persamaan (2.7) diuraikan, maka koefisien dari n akan menjadi (-1)n. Jadi, koefisien utama dari p() adalah (-1)n dan dengan demikian jika 1, . . .,n adalah nilai-nilai eigen dari A, maka p ( )  ( 1) n (  1 )(  2 )...(  n )

(2.7)

untuk menghitung nilai eigen dan vektor eigen, nilai p ( ) harus sama dengan 0, sehingga diperoleh


17 p ( )  (1   )(2   )...(n   )

Dari persamaan (2.5) dan (2.7) maka diperoleh

1.2  n  p(0)  det( A) Dari persamaan (2.6), juga diperoleh

n

a

ii

i 1

persamaan (2.7)

sebagai koefisien dari (-)n – 1. Jika dengan

n

  . Dengan demikian, maka i 1

i

n

n

 = a i 1

i

i 1

ii

Jumlah elemen diagonal dari (A) dinamakan trace dari A, dan dilambangkan dengan tr(A), catatan bahwa tr(A + B) = tr(A) + tr(B) (Horn and Johnson, 1985). Contoh 2.1.3.1

 3 2  Jika A    maka det(A) = (-6) – 6 = -12 dan tr(A) = -3 + 2 = -1  3 2 Polinom karakteristik dari A diberikan oleh persamaan

3   3

2   2    12 2

dan sebagai akibatnya nilai-nilai eigen dari A adalah -4 dan 3. Dapat ditinjau bahwa 1 + 2 = -1 = tr(A) dan 1 . 2 = -12 = det(A). Dalam penelitian ini digunakan nilai eigen dan vektor eigen. Fungsi nilai eigen pada penelitian ini yakni karena trace = jumlah nilai eigen = jumlah elemen diagonal akan digunakan untuk menentukan nilai fungsi objektif yang berupa skalar bukan dalam bentuk matriks. Vektor eigen digunakan untuk mengetahui kombinasi linier matriks L dan R yang merupakan matriks transformasi kiri dan kanan oleh ADL2-D. Matriks L dan R selanjutnya akan digunakan untuk menentukan matriks sebaran dalam kelas jika L atau R tetap dan matiks sebaran antar kelas jika L atau R tetap S wR , S wL , SbR , SbL . Matriks L dan R tersebut kemudian akan digunakan untuk menghitung transformasi bilinier sehingga diperoleh perbedaan antar kelas dan hasil klasifikasi yang baik.


18

2.2

Analisis Diskriminan Linier (ADL)

Analisis diskriminan adalah teknik statistik multivariat yang terkait dengan pemisahan (separating) atau alokasi/klasifikasi (classification) sekelompok objek atau observasi ke dalam kelompok (group) yang telah terlebih dahulu didefinisikan. Dalam tujuan pengenalan objek (observasi), metode ini mencoba menemukan suatu ‘discriminant’ yang nilainya secara numeris sedemikian sehingga mampu memisahkan objek yang karakteristiknya telah diketahui. Sedangkan dalam tujuan klasifikasi objek, metode ini akan mensortir objek (observasi) ke dalam 2 atau lebih kelas (Fukunaga, 1990). Jika diberikan suatu matriks data A  R N n , metode ADL klasik bertujuan menemukan suatu transformasi G  R N l yang memetakan setiap kolom ai dari matriks A, untuk 1 ≤ i ≤ n, dalam ruang dimensi N ke vektor bi dalam ruang dimensi l. Yakni G : ai  R N n  bi  G T ai  R l (l  N ) . Dengan kata lain,

ADL bertujuan

menemukan suatu ruang vektor  direntangkan oleh {g i }il 1 di mana G= [g1, g2, …,gl], sehingga setiap ai diproyeksikan ke  oleh ( g1T .ai ,..., glT .ai )T  Rl (Ye et. al, 2004). Asumsikan bahwa data asli dalam A dipartisi ke dalam k kelas sehingga A = {∏1, ∏2,…, ∏k}, dimana ∏i memuat ni titik data dari kelas ke –i, dan



k i 1

ni  n .

ADL klasik bertujuan untuk menemukan transformasi optimal G sehingga struktur kelas dari data ruang berdimensi tinggi yang asli diubah ke dalam ruang berdimensi rendah (Ye et. al, 2004). Dalam ADL, transformasi ke subruang yang berdimensi lebih rendah yaitu yi  G T xi (Luo et al, 2007)

(2.8)

di mana G merupakan transformasi ke subruang. Sering juga dituliskan dengan (y1, ..., yn) = GT (x1, ..., xn) atau Y = GT X. Tujuan utama dari ADL adalah mencari nilai G sehingga kelas dapat lebih terpisah dalam ruang transformasi dan dengan mudah dapat dibedakan dari yang lainnya.


19 Dalam metode Analisis Diskriminan Linier, terdapat dua matriks sebaran yaitu matriks sebaran dalam-kelas disimbolkan dengan S w , dan matriks sebaran antar-kelas disimbolkan dengan Sb , masing-masing didefinisikan sebagai berikut: c

Sw  

 [x

i 1 xk  i

k

 mi ][xk  mi ]T

(2.9)

c

Sb   ni [mi  m][mi  m]T

(2.10)

i 1

di mana ni adalah jumlah sampel pada kelas xi , dan mi adalah image rata-rata dari kelas ke-i dan m adalah rata-rata keseluruhan. Rumus rata-rata kelas dan rata-rata keseluruhan adalah sebagai berikut:

mi 

1 ni



xi

x

adalah mean (rata-rata) dari kelas ke-i, dan m 

1 k   x n i 1 xi

adalah rata-rata keseluruhan (Fukunaga, 1990). Seperti diutarakan sebelumnya, metode Analisis Diskriminan Linier diharapkan dapat meminimumkan jarak dalam matriks sebaran dalam-kelas ( S w ) sementara jarak matriks sebaran antar-kelas ( Sb ) dapat dimaksimumkan sehingga dapat terlihat perbedaan atau pemisahan antar kelas. Dalam hasil ruang dimensi yang lebih rendah dari transformasi linier G (atau proyeksi linier ke dalam ruang vektor ), Sb dan S w menjadi Sb (Y )  G T Sb ( X )G ,

(2.11)

S w (Y )  G T S w ( X )G.

(2.12)

Transformasi optimal G akan memaksimumkan trace( SbL ) dan meminimumkan trace( S wL ). Optimisasi umum dalam Analisis Diskriminan Linier

meliputi (lihat Fukunaga,

1990) :

max{trace(( S wL ) 1 S bL )} dan min{trace(( SbL ) 1 S wL )} G

G

(2.13)

Hal ini dituliskan dalam fungsi objektif optimum:


20

max J (G )  tr G

Sb (Y ) G T S ( X )G  tr T b S w (Y ) G S w ( X )G

(2.14)

Catatan bahwa trace(A/B) = trace(B-1A) = trace (AB-1) Masalah optimisasi dari persamaan (2.14) di atas ekivalen dengan masalah generalisasi nilai eigen berikut: Sb x   S w x , untuk   0. Penyelesaiannya dapat diperoleh dengan menerapkan eigen-dekomposisi ke matriks S w1Sb x jika S w nonsingular, atau Sb1 S w x jika Sb nonsingular. Terdapat paling banyak k – 1 vektorvektor eigen yang cocok ke nilai eigen tak nol, karena kedudukan dari matriks Sb dibatasi oleh k – 1. Oleh karena itu, dimensi yang direduksi oleh ADL klasik terletak pada k – 1. Gambar berikut ini menunjukkan hasil dari penerapan metode Analisis Diskriminan Linier (ADL) dalam pengklasifikasian.

Gambar 2.2 Hasil Klasifikasi dengan Analisis Diskriminan Linier Dalam hal transformasi setiap data, Fukunaga (1990) mengklasifikasikan himpunan data dan vektor uji ke dalam ruang transformasi melalui dua pendekatan yang berbeda sebagai berikut: 1. Transformasi Class-dependent yaitu pendekatan yang memaksimumkan rasio varians antar-kelas ke varians dalam-kelas. 2. Transformasi Class-independent yaitu memaksimumkan rasio seluruh varians dalam-kelas. Selain itu, ia juga menyajikan operasi matematika untuk mempermudah klasifikasi sejumlah objek yaitu:


21 1. Formulasikan himpunan data dan data uji yang akan diklasifikasikan dalam ruang aslinya. Untuk memudahkan pengertian, peneliti menggunakan dua data dan direpresentasikan ke dalam matriks yang berisi fitur dalam bentuk seperti berikut

 a11   a21 set1      a  m1

a12   a22     am 2 

 b11 b12     b21 b22  set1           b   m1 bm 2 

2. Hitung rata-rata setiap himpunan data dan rata-rata dari seluruh data. Anggap 1 dan  2 adalah rata-rata dari himpunan data 1 dan 2, serta 3 sebagai rata-rata dari seluruh data yang diperoleh dari

3  p11  p2 2 di mana p1 dan p2 adalah peluang dari masing-masing kelas. Pada kasus dua kelas, faktor peluang diasumsikan sebesar 0,5. 3. Matriks sebaran dalam kelas merupakan ekspektasi kovarians dari setiap kelas. dengan perhitungan sebagai berikut S w   p j cov j j

Untuk permasalahan dua kelas, S w  0, 5cov1  0, 5cov 2

Semua matriks kovarians adalah matriks yang simetris. Matriks kovarians dihitung menggunakan persamaan berikut

cov j  ( x j   j )( x j   j )T Matriks sebaran antar-kelas dihitung dengan menggunakan persamaan berikut

Sb   (  j  3 )(  j  3 )T j

Faktor optimisasi dalam tipe dependent-class transformasi dapat dihitung sebagai criterion j  inv (cov j )  Sb

Faktor optimisasi dalam tipe independent-class

transformasi dapat dihitung

sebagai

criterion  inv(S w )  Sb


22

2.3

Analisis Diskriminan Linier 2-Dimensi

Analisis Diskriminan Linier 2-Dimensi (ADL2-D) adalah suatu metode baru yang merupakan perkembangan dari Analisis Diskriminan Linier. Beberapa tahun belakangan ini, metode-metode ADL2-D ini telah diperkenalkan. Li and Yuan (2005), dan Xiong et. al (2005) memformulasikan gambar berdasarkan perhitungan matriks sebaran dalam kelas dan antar kelas. Metode-metode tersebut tidak merepresentasikan gambar ke dalam vektor sehingga tereduksi secara dimensional ke dalam matriks gambar. Song et. al (2005) dan Yang et. al (2003) menggunakan korelasi kolom demi kolom untuk mereduksi sejumlah kolom. Selanjutnya Yang et. al (2005) memperbaiki dan memberikan suatu algoritma untuk mereduksi bilanganbilangan pada kolom pertama dan mereduksi bilangan-bilangan pada baris berikutnya. Metode ini merupakan suatu algoritma dependen. Ye et. al (2005) memperkenalkan suatu ADL2-D independen dengan suatu algoritma solusi iteratif. Untuk Analisis Diskriminan Linier 2 Dimensi, perbedaan utama antara ADL klasik dan ADL2-D yang peneliti usulkan dalam penelitian ini adalah tentang perwakilan (representasi) data. ADL klasik menggunakan representasi vektor, sedangkan ADL2-D bekerja dengan data dalam representasi matriks. Dalam penggunaan metode ADL2-D akan terlihat bahwa representasi mengarah ke eigendekomposisi pada matriks dengan ukuran lebih kecil. Lebih khusus, ADL2-D melibatkan eigen-dekomposisi matriks dengan ukuran r × r dan c × c, yang jauh lebih kecil daripada matriks ADL klasik (Ye et. al, 2005). Dalam ADL2-D telah disepakati bahwa suatu himpunan gambar disimbolkan dengan X =(X1, X2, ..., Xn), Xi r c . Dengan intuisi yang sama dengan ADL klasik, ADL2-D mencoba untuk mencari suatu transformasi bilinier Yi  LT X i R

(2.15)

sehingga kelas-kelas yang berbeda dipisahkan. Kuncinya adalah bagaimana memilih ruang bagian L dan R berdasarkan matriks sebaran dalam kelas dan antar kelas (Luo et. al, 2007).


23 Tidak seperti ADL klasik, ADL2-D menganggap hal berikut (l1×l2) - ruang dimensi L⊗R merupakan perkalian tensor (kronecker product) dua ruang berikut: L direntang oleh {u i }li1 1 dan R direntangkan oleh

{ v i } li 2 1 dan

didefinisikan sebagai dua

matriks L = [u1 , ...,u l1 ]  R rl1 dan R = [ v1 ,..., v l 2 ]  R cl2 . Kemudian, himpunan gambar X  R rc diproyeksikan ke ruang L⊗ R sehingga hasil proyeksinya adalah LTX R  Rl1l2 (Ye et. al, 2004). Kronecker product (perkalian tensor) didefinisikan sebagai: anggap L  R rl1 , R  R cl2 maka Kronecker product (perkalian tensor) L dan R didefinisikan sebagai matriks  l11R  l1l1 R    LR      l R  l R rl1   r1

L  R  R  L dan apabila L  R rl1 dan R  R cl2 simetris maka L  R simetris (Horn and Johnson, 1985). Sebagai contoh a L   11  a21

a12   a11 R a12 R   dan R maka L  R    a22   a21 R a22 R 

Jika dimisalkan Ai   rc , untuk i = 1, 2, …, n adalah gambar (pola) dalam dataset, kemudian masing-masing pola dikelompokkan ke dalam ∏1, ∏2,…, ∏k dimana ∏i memiliki ni gambar (pola). Misalkan M i  dari kelas ke–i, 1 ≤ i ≤ k , dan M 

1 ni



xi

X adalah rata-rata

1 k   X berarti rata-rata keseluruhan, n i 1 xi

dalam 2DLDA, peneliti menganggap gambar sebagai sinyal dua dimensi dan bertujuan untuk menemukan dua matriks transformasi

L   rl1 dan R   cl2 yang

memetakan setiap anggota Ai   rc untuk 1≤ x ≤ n , ke suatu matriks Bi   l1 l2 sehingga Bi = LT Ai R. Sama halnya seperti ADL klasik, ADL2D bertujuan untuk mencari transformasi (proyeksi) optimal L dan R sehingga struktur kelas dari ruang


24 berdimensi tinggi yang asli diubah ke ruang berdimensi rendah. Suatu kesamaan metrik alami antara matriks adalah norma Frobenius (Ye, et. al, 2004). Di bawah metrik ini kuadrat jarak dari within-class (dalam kelas) dan between class (antar kelas) dapat dihitung sebagai berikut: k

Dw    X  M i i 1 xi

trace (M MT)= M

2 F

2 F

,

k

Db   ni M i  M i 1

2 F

(2.16)

, untuk suatu matriks M, maka diperoleh

 k Dw  trace    X  M i  i 1 xi  k Db  trace    X  M i  i 1 xi

 F  

(2.17)

 F  

(2.18)

2

2

Dalam ruang berdimensi rendah, hasil dari transformasi linier L dan R, jarak withinclass dan between class menjadi: _  k  T D w  trace    LT  X  M i  RRT  X  M i  L   i 1 xi 

(2.19)

_  k T  D b  trace   ni LT  X  M i  RRT  X  M i  L   i 1 

(2.20)

_

_

Transformasi optimal L dan R akan memaksimumkan D b dan meminimumkan D w , oleh karena kesulitan menghitung optimal L dan R secara simultan, berikut ini adalah algoritma untuk ADL2D. Lebih khususnya, untuk suatu R tetap, kita dapat menghitung optimal L dengan memecahkan permasalahan optimisasi yang sama dengan persamaan (2.14). Dengan menghitung L,

kita kemudian dapat

memperbaharui R dengan memecahkan masalah optimisasi lain sebagai satu-satunya penyelesaian dalam persamaan (2.14).


25 Beberapa notasi penting yang digunakan dalam penelitian ini terdaftar dalam Tabel 2.1 dibawah ini: Tabel 2.1 Notasi Penting dalam Analisis Diskriminan Linier 2 Dimensi Notasi

Keterangan

N

jumlah gambar dalam dataset

K

jumlah kolom dalam dataset

Ai

Gambar ke-i dalam representasi matriks

ai

gambar ke-i dalam representasi vektor

R

jumlah baris dalam matriks A

C

jumlah kolom dalam matriks A

N

Dimensi dari ai (N= r * c)

∏j

Kelas ke- j dalam dataset

L

matriks transformasi (kiri) oleh ADL2D

R

matriks transformasi (kanan) oleh ADL2D

I

jumlah iterasi dalam ADL2D

Bi

Pereduksian representasi Ai oleh ADL2D

l1

jumlah baris dalam Bi

l2

jumlah kolom dalam Bi

Perhitungan L _

_

Untuk suatu R tetap, D w dan D b dapat ditulis kembali sebagai _

_

D w  trace  LT S wR L  , D b  trace  LT SbR L 

(2.21)

di mana k

S wR  



i 1 X  i

k

( X  M i ) RRT ( X  M i )T , SbR   ni ( M i  M ) RRT ( M i  M )T

(2.22)

i 1

Sama seperti masalah yang terdapat pada persamaan (2.14), optimal L dapat dihitung dengan memecahkan masalah optimisasi berikut: maxL trace (( LT S wR L) 1 ( LT SbR L)) . Penyelesaiannya dapat diperoleh dengan memecahkan masalah generalisasi nilai


26 eigen berikut: S wR x   SbR x . Karena S wR secara umum adalah nonsingular, maka L optimum dapat diperoleh dengan menghitung suatu eigen-dekomposisi pada ( S wR ) 1 SbR . Catatan bahwa ukuran dari matriks S wR dan SbR adalah r  r (matriks

bujursangkar), yang ukurannya lebih kecil dibandingkan ukuran matriks S w dan Sb dalam ADL klasik.

Perhitungan R _

_

Kemudian menghitung R untuk suatu L yang tetap. D w dan D b dapat ditulis kembali sebagai _

_

D w  trace  RT S wL R  , D b  trace  RT SbL R 

(2.23)

di mana k

SwL  



i 1 X  i

k

( X  M i )T LLT ( X  M i ), SbL   ni ( M i  M )T LLT ( M i  M )

(2.24)

i 1

Sama seperti masalah yang terdapat pada persamaan (2.14), optimal L dapat dihitung dengan memecahkan masalah optimisasi berikut: maxR trace (( RT S wL R )1 ( RT SbL R)) . Penyelesaiannya dapat diperoleh dengan memecahkan masalah generalisasi nilai eigen berikut: S wL x   SbL x . Karena S wL secara umum adalah nonsingular, maka R optimum dapat diperoleh dengan menghitung suatu eigen-dekomposisi pada ( S wR ) 1 SbR . Catatan bahwa ukuran dari matriks S wL dan SbL adalah r  r (matriks

bujursangkar), yang ukurannya lebih kecil dibandingkan ukuran matriks S w dan Sb dalam ADL klasik.

Algoritma 2.2 ADL2D ( A1,…,An, l1, l2) Input: Output:

A1,…,An, l1, l2 L, R, B1,…, Bn

1. Hitung rata-rata Mi

Mi 

1 ni



xi

dari kelas ke-i untuk setiap i sebagai

X

2. Hitung rata-rata global

M

1 k   X n i 1 xi


27 3. R0  Il ,0 2

T

4. Untuk j dari 1 sampai I k

5.

S wR     X  M i  R j 1 RTj 1  X  M i 

T

i 1 xi

SbR   i 1 ni  X  M i  R j 1RTj 1  X  M i  k

T

{lL }li11 dari (S Rw )-1 SbR

6. Hitung eigen vektor l1 pertama 7.

L j  {1L ,..., l1L }

8.

S wL     X  M i  L j LTj  X  M i 

k

T

i 1 xi

SbL   i 1 ni  X  M i  L j LTj  X  M i  k

T

9. Menghitung eigen vektor l2 pertama 10.

{lR }ll21 dari (S Lw )-1 SbL

R j  {1R ,..., lR2 }

11. End for 12.

L  LI , R  RI

13.

Bl  LT Al R, untuk l  1, 2,..., n

14. Return (L, R, B1, …,Bn)

(Ye, et.al, 2004)

Namun, dalam ADL2-D kita akan melihat ada suatu masalah keraguan yang sangat mendasar yakni ada dua cara untuk mendefinisikan matriks sebaran dalam kelas S w k

S w ( XX T )  

 (X

j 1 xi  k

Sw ( X T X )  

i

(2.25)

 M j )T ( X i  M j )

(2.26)

j

 (X

j 1 xi 

 M j )( Xi  M j )T

i

j

dan ada 2 cara untuk mendefinisikan matriks sebaran antar kelas Sb k

Sb ( XX T )   n j ( M j  M )( M j  M )T

(2.27)

j 1 k

Sb ( X T X )   n j ( M j  M )T ( M j  M )

(2.28)

j 1


28 Oleh karena itu, dalam ruang transformasi, dapat dituliskan sebagai Sb (YY T ), Sb (Y T Y ),

S w (YY T ), S w (Y T Y ),

Pada umumnya, gambar tidak bersifat simetris: Xi  XiT , maka Sb (YY T )  Sb (Y T Y ),

S w (YY T )  S w (Y T Y ),

Karena alasan ini, fungsi objektif ADL menjadi bermakna ganda dan menimbulkan keraguan manakah fungsi objektif yang baik yakni mempunyai sejumlah pilihan sebagai berikut:

J1  tr

Sb (YY T ) S w (YY T )

(2.29)

J 2  tr

Sb (Y T Y ) S w (Y T Y )

(2.30)

 S (YY T ) Sb (Y T Y )  J 3  tr  b   T T  S w (YY ) S w (Y Y ) 

(2.31)

 S (Y T Y ) Sb (YY T )  , J 4  tr  b T T   S w (Y Y ) S w (YY ) 

(2.32)

J 5  tr

Sb (YY T )  Sb (Y T Y ) , S w (YY T )  S w (Y T Y )

(2.33)

dan lain-lain.

2.3.1 Transformasi Bilinier Suatu transformasi bilinier didefinisikan sebagai:    Yi

Yi T  T    T  Xi 

Xi  L   ,     R  

(Luo, et.al, 2007)

(2.34)

Dengan menggunakan transformasi symmetris ini, matriks sebaran menjadi tunggal dan masalah keraguan yang terdapat dalam ADL2-D dapat diselesaikan. Kemudian, berikut ini ditunjukkan bahwa transformasi bilinier pada persamaan (2.34) ekivalen ke transformasi linier pada persamaan (2.15):


29

 T  T  Xi

Xi   RT X iT L     T     L XiR 

(2.35)

maka Yi = LT Xi R. Pada Fukunaga(1990), matriks Γ didefinisikan sebagai:  1 0 0  0      0    n 

yakni matriks yang diagonal utamanya merupakan nilai varians dari suatu himpunan data dan elemen lain dalam matriks bernilai 0.


BAB 2 LANDASAN TEORI

Recommend Documents