BAB 2 TINJAUAN PUSTAKA Pada bab ini akan diuraikan mengenai dasar teori yang digunakan dalam pengerjaan tugas akhir. Teori yang dibahas antara lain mengenai pengenalan obyek, Principal Component Analysis (PCA), Linear Discriminant Analysis (LDA), Subclass Discriminant Analysis (SDA), serta teknik Stabiliy Criterion. 2.1
Pengenalan Obyek
Pengenalan obyek merupakan suatu proses pendeteksian dan klasifikasi suatu obyek, yang sebelumnya telah dipelajari oleh sistem. Pengenalan obyek dilakukan dengan membandingkan ciri obyek yang diamati dengan pengetahuan yang sebelumnya telah dimiliki tentang obyek-obyek yang ada. Pengenalan citra obyek tidak berbeda dengan pengenalan citra wajah atau pengenalan citra yang lain. Tiap citra obyek pasti memiliki perbedaan. Hal tersebut bisa saja karena adanya perbedaan intesitas cahaya ataupun perbedaan sudut pengambilan gambar. Citra dengan berbagai sudut pandang yang berbeda akan dikenali dan dikumpulkan untuk mewakili obyek tersebut. Ekstraksi ciri dilakukan pada kumpulan tersebut untuk mendapatkan informasi ciri suatu obyek. Hasil ekstraksi ciri kemudian digunakan untuk proses pengenalan citra obyek. Ciri dari suatu citra adalah tingkat keabuan (grey-level) dari tiap piksel pada citra. Pada suatu sistem pengenalan, yang dilakukan terlebih dahulu adalah membentuk data pelatihan. Setelah data pelatihan terbentuk, pengenalan dilakukan dengan cara membandingkan data masukan / data uji coba (berupa citra obyek) dengan citra pada data pelatihan yang telah dibentuk sebelumnya.
7
8 2.1.1
Representasi Citra Obyek
Sebuah citra dapat dipandang sebagai sebuah vektor. Sebuah citra dengan lebar w dan tinggi h akan membentuk vektor yang mempunyai komponen sebanyak w x h. Vektor ini disusun dengan melakukan penggabungan terhadap baris citra yang disusun berdampingan satu sama lain, seperti yang terlihat pada Gambar 2.1.
Gambar 2.1 Pembentukan Vektor Citra dari Sebuah Citra Obyek
Vektor citra obyek yang telah dideskripsikan sebelumnya merupakan bagian dari sebuah ruang. Ruang ini adalah sebuah ruang lingkup citra (image space), yaitu ruang dari semua citra keseluruhan yang mempunyai dimensi w x h piksel. Mendeskripsikan suatu citra obyek dalam sebuah ruang citra penuh (spasial) tidak akan optimal jika digunakan untuk mengenal obyek tiga dimensi. Bentuk representasi citra acuan yang digunakan adalah representasi ruang eigen. Ide dasar dari representasi ini adalah merepresentasi sekumpulan citra atau ciri suatu citra dalam sebuah ruang transformasi dimana setiap ciri tidak berkorelasi. Bentuk representasi ruang eigen dapat diperoleh dengan melakukan Principal Component Analysis (PCA) terhadap sekumpulan citra acuan. Hasil transformasi ini adalah vektor basis ortonormal yang digunakan untuk membentuk suatu sub ruang vektor yang disebut ruang ciri. Vektor citra acuan ditransformasikan menggunakan transformasi Karhunen-Loeve atau Principal Component Analysis (PCA), yang akan menghasilkan sejumlah vektor basis
9 ortonormal. Vektor basis ortonormal digunakan untuk membentuk ruang ciri bagi obyek yang akan dikenali. Pengekstrakan ciri suatu citra dilakukan dengan memetakan citra masukan ke dalam ruang ciri yang telah dihasilkan. 2.1.2
Feature Extraction (Ekstraksi Ciri)
Pola merupakan suatu entitas terdefinisi dan dapat diidentifikasi melalui ciri-cirinya (feature). Ciri-ciri tersebut digunakan untuk membedakan suatu pola. Sehingga, ciri yang bagus adalah ciri yang memiliki daya pembeda yang tinggi, sehingga pengelompokan pola berdasarkan ciri yang dimiliki dapat dilakukan dengan keakuratan yang tinggi. Sebagai contoh, apabila polanya adalah penyakit, maka ciri yang digunakan adalah umur pasien, jenis kelamin, suhu tubuh, dan tekanan darah. Apabila polanya adalah sebuah citra, maka ciri yang dapat digunakan adalah tingkat keabuan (grey-level) dari tiap piksel pada citra. Ketika merepresentasikan data, untuk meningkatkan performa klasifikasi dapat dilakukan dengan cara menambahkan ciri (dimensi). Namun pada prakteknya, banyaknya ciri tersebut tidak semuanya berguna dalam menggambarkan karakteristik data. Semakin banyak ciri yang diukur, maka akan semakin kompleks. Hal tersebut mengakibatkan perlunya reduksi dimensi. Terdapat dua cara dalam reduksi dimensi, yaitu feature selection (seleksi ciri) dan feature extraction (ekstraksi ciri). Seleksi ciri mengacu pada algoritma yang memilih subset ciri terbaik untuk merepresentasikan data. Sedangkan ekstraksi ciri menentukan ruang ciri berdimensi m dari ruang ciri berdimensi p yang asli, dimana m < p, dengan transformasi linier ataupun transformasi non linier berdasarkan kriteria yang ditentukan sebelumnya. Metode ekstraksi ciri banyak berkembang, dengan tujuan untuk memperoleh hasil yang optimal. Metode ekstraksi ciri yang menjadi acuan pada pengerjaan tugas akhir ini adalah metode Principal Component Analysis (PCA) dan Linear
10 Discriminant Analysis (LDA). Kedua metode tersebut akan dijelaskan pada sub bab berikutnya. 2.2
Metode Principal Component Analysis (PCA)
Pada tahun 1933, Hotelling mengajukan sebuah teknik untuk mengurangi dimensi sebuah ruang yang direpresentasikan oleh variabel statistik x1, x2, …, xn, dimana variabel tersebut biasanya saling berkorelasi antara satu dengan yang lain. Pertanyaan kemudian timbul, apakah terdapat sebuah himpunan variabel baru yang memiliki sifat yang relatif sama dengan variabel sebelumnya, dimana dikehendaki himpunan variabel baru tersebut memiliki jumlah variabel (dimensi) yang lebih sedikit dari variabel sebelumnya. Selanjutnya Hotelling menyebut metode tersebut sebagai Principal Component Analysis (PCA) atau kadang juga Transformasi Hotelling dan Transformasi Karhunen Loeve. Transformasi PCA banyak digunakan untuk memproyeksikan atau mengubah suatu kumpulan data berukuran besar menjadi bentuk representasi data lain dengan ukuran yang lebih kecil. Transformasi PCA terhadap sebuah ruang data yang besar akan menghasilkan sejumlah vektor basis ortonormal ke dalam bentuk kumpulan vektor eigen dari suatu matriks kovarian tertentu, yang dapat secara optimal merepresentasikan distribusi data. Transformasi sebagai berikut:
PCA
bekerja
dengan
langkah-langkah
1. Membentuk matriks data pelatihan Y dengan orientasi vektor kolom. Himpunan dari M citra pelatihan, X = [X1, X2, ..., XM] dengan dimensi tiap citra adalah N (baris x kolom).
11
x11 x Y = 12 K x1N
x21 K xM 1 x22 L xM 2 K K K x2 N K xMN
xij adalah nilai intensitas dari piksel pada citra pelatihan ke-i dan indeks dimensi ke-j. 2. Menjadikan vektor kolom pada matriks Y menjadi vektor satuan. X 11 X 2 + X 2 +K+ 12 11 X 12 2 2 +K+ X + X Y = 11 12 K X 1N 2 X + X 2 +K+ 12 11
X
X
X 21 2 X + X 2 +K+ X 2 21 22 2N X 22 X 2 + X 2 +K+ X 2 21 22 2N
2 1N 2 1N
K
X
X 2N 2 X + X 2 +K+ X 2 21 22 2N
2 1N
K
L
K K
X M1 2 2 2 X +X +K+ X M1 M2 MN X M2 2 2 2 X +X +K+ X M1 M2 MN K X MN 2 2 2 X +X +K+ X M1 M2 MN
Sehingga matriks Y dapat dinyatakan dengan:
y11 y 12 Y = K y1 N
y 21 y 22 K y2 N
K L K K
yM1 y M 2 K y MN
3. Menghitung rata – rata total dari himpunan citra pelatihan. y11 + y 21 + K + y M 1 M y12 + y 22 + K + y M 2 Y = M avg K y1 N + y 2 N + K + y MN M
12 4. Menghitung matriks A yang merupakan selisih antara Y dengan Yavg.
A = Y − Yavg 5. Menghitung matriks kovarian dari A yaitu AAT (berordo N x N). Jika jumlah data pelatihan M lebih kecil dari dimensi citra N, maka matriks kovarian dihitung dengan ATA (berordo M x M). 6. Menghitung nilai eigen dan vektor eigen dari matriks kovarian. Karena matriks A berukuran besar, maka digunakan metode Singular Value Decomposition (SVD). Metode SVD mendekomposisi matriks asal A menjadi perkalian dari tiga komponen matriks:
A = USV T Dimana : • A : • U : • V : • S :
matriks asal dengan ordo N x M. matriks orthonormal dengan ordo N x N. matriks orthonormal dengan N x M. matriks dengan elemen tidak nol pada diagonal utama berordo N x M.
7. Mengurutkan vektor eigen berdasarkan nilai eigen yang terbesar. 2.3
Metode Fisher Linear Discriminant Analysis (FLDA)
Sebelum membahas penerapan metode Fisher Linear Discriminant Analysis (FLDA) pada pengenalan pola, akan dijelaskan mengenai metode pengenalan pola dengan pendekatan statistik (Statistical Pattern Recognition) dan kaitannya dengan fungsi diskriminasi linier (Linear Discriminant Functions) secara ringkas.
13 2.3.1
Metode Pengenalan Pola dengan Pendekatan Statistik
Titik berat pada pengembangan metode pengenalan pola dengan pendekatan statistik terletak pada pengembangan strategi klasifikasi atau pengambilan keputusan (decision or classification strategies) yang akan menjadi dasar pembentukan rancangan pengklasifikasi (classifier). Aturan-aturan yang terlibat pada pengembangan strategi klasifikasi atau pengambilan keputusan tersebut meliputi:
Konversi dari peluang prior suatu kelas P(wi) (prior class probability) menjadi peluang posterior P(wi|x) (measurement-conditioned probability).
Merumuskan ukuran dari ekspektasi terhadap galat klasifikasi atau suatu fungsi risiko dan selanjutnya memilih aturan yang dapat meminimumkan ukuran tersebut.
Kedua aturan tersebut berperan dalam pembentukan partisi dari ruang berdimensi tinggi Rd dan diimplementasikan melalui suatu fungsi diskriminasi. Konversi dari peluang prior suatu kelas menjadi peluang posterior dapat diselesaikan dengan menggunakan teorema Bayes pada persamaan (2.1). P (wi | x ) =
p (x | wi )P (wi ) p(x )
dengan: p( x ) = ∑ p ( x | wi )P(wi )
(2.1)
c
i =1
Dimana: P (w i | x ) : posterior probabilit y p ( x | w i ) : likelihood
P (w i ) p (x )
: prior probabilit y : evidence
(2.2)
14 Teorema Bayes dapat dituliskan dengan: P (wi | x ) =
p (x | wi )P (wi ) posterior = likelihood x prior evidence p(x )
Dengan menggunakan asumsi probability density function-nya adalah Multivriate Gaussian, maka dapat dituliskan seperti persamaan (2.3).
p(x ) =
1
(2π )
d /2
∑
1/ 2
1 t exp− ( x − µ ) ∑ −1 ( x − µ ) 2
(2.3)
Dimana: x
: vektor kolom berdimensi d.
µ
: vektor mean berdimensi d.
Σ
: matriks kovarian, d x d.
Fungsi diskriminan yang maksimal akan mencapai errorrate yang minimum. Sehingga dapat dinyatakan dengan: g ( x ) = P (wi | x ) , dengan kata lain: memaksimalkan fungsi diskriminan sama dengan memaksimalkan posterior probability. p( x | wi ) p ( wi ) p ( x) g i ( x) = p ( x | wi ) p ( wi )
g i ( x) = p ( wi | x) =
g i ( x) = ln p( x | wi ) + ln p( wi )
Jika diasumsikan model distribusinya adalah Distribusi Gaussian dengan matriks kovarian dan prior probability yang sama untuk tiap kelas, maka fungsi diskriminannya dituliskan seperti pada persamaan (2.4)
1 1 1 g i ' ( x) = − ( x − µ i )T Σ −1 ( x − µ i ) − ln(2π ) − ln | Σ | (2.4) 2 2 2
15 Suku kedua dan ketiga dari persamaan (2.4) merupakan konstanta bias yang class-independent, sehingga dapat dieliminasi. Karena matriks kovarian bersifat simetris, maka:
(
g i ( x ) = ∑ −1 µ i
)
T
1 T x − µ i ∑ −1 µ i 2
g i ( x ) = wi x − wi 0 T
(
dengan: wi = ∑ −1 µ i 2.3.2
)
dan wi 0 =
1 T −1 µi ∑ µi . 2
Fisher Linear Discriminant Analysis (FLDA)
Pendekatan Fisher (Fisher. R.A, “The Use of Multiple Measurements in Taxonomic Problems”, 1936) dilakukan dengan melakukan proyeksi terhadap data berdimensi-d pada suatu garis. Tujuan penggunaan proyeksi garis tersebut agar pemisahan antar kelas menjadi lebih baik (well separated), sehingga dapat meningkatkan kemampuan pendiskriminasiannya (good discrimination ability). Untuk menjelaskan metode Fisher, dimisalkan sebagai berikut:
Terdapat pola dengan dua kelas (c = 2)
Terdapat
{
himpunan
H = x1 , x 2 , K, x n
}
data
pelatihan H dengan = {H 1 , H 2 } , n1 pada subset H1 yang
terdapat di kelas ω1 , dan n2 pada subset H2 yang terdapat di
kelas ω 2 , serta n1 + n2 = n.
Sehingga proyeksi vektor ciri dapat dinyatakan dalam persamaan (2.5).
y i = v x i = < v, x i > T
i = 1, 2, K, n
(2.5)
16 Persoalan selanjutnya adalah menentukan arah dari v berdasarkan H, sedemikian sehingga y i dari H1 (Y1) dan y i dari H2 (Y2) berada pada klaster yang berbeda sepanjang garis proyeksi. Ukuran pemisahan dari hasil proyeksi dapat ditentukan dengan beda (difference) diantara mean dari hasil proyeksi 2 tersebut. Contoh ukuran tersebut adalah µ Y 1 − µ Y 2 , dengan:
µY i = E{ yi | x i ∈ vi } = E{v T x i | x i ∈ vi } Jika diketahui mean dari data sample untuk H1, H2 dinyatakan dengan persamaan (2.6).
mi =
1 ni
∑
xi∈H
xi
(2.6)
i
maka mean dari hasil proyeksi dapat dinyatakan sebagai berikut:
mi =
1 ni
∑
y
1 ni
∑
v xi
=
y∈Yi T
x i∈ H i
= v mi T
Sedangkan beda diantara hasil proyeksi dapat dinyatakan berdasarkan data sampel dengan persamaan (2.7).
m1 − m 2 = v
T
(m 1 − m 2 )
(2.7)
Untuk memperoleh klasifikasi yang baik, selain menggunakan informasi beda diantara mean dari hasil proyeksi, harus dipertimbangkan juga variansi dari y i pada Yi relatif
17 terhadap tiap nilai mean. Sehingga ukuran pemisahan kelas dapat dinyatakan sebagai rasio antara (beda nilai mean) / (variansi data
(m J (v ) =
)
2
− m 2 , dengan σ 2 menyatakan ukuran tiap kelas) 1 2 σ 1 + σ 22 scatter pada tiap kelas (within-class) dari data proyeksi. 1
Selain menggunakan variansi, dapat dengan mendefinisikan ukuran scatter pada tiap kelas (within-class) dari data proyeksi, seperti persamaan (2.8) berikut ini:
Si = 2
∑ (y − m )
2
(2.8)
i
y ∈Y i
Terdapat definisi ketentuan Fisher, persamaan (2.9):
(m J (v ) =
)
2
− m2 2 2 S1 + S 2 1
Untuk didefinisikan: -
menyelesaikan
persamaan
(2.9),
maka
Matriks Scatter Si
Si = -
(2.9)
∑ (x − m )(x − m )
T
i
i
,
i = 1, 2 , dan
x∈ H i
S w = S1 + S 2
Sehingga dapat dituliskan: S 1 + S 2 = v S W v , dengan penjabaran sebagai berikut: 2
2
T
18
Si = 2
∑ (y − m )
2
i
y∈Yi
=
∑ (v
T
x − v mi T
x∈ H i
=
)
2
∑ v (x − m )(x − m )
T
T
i
i
v
x∈ H i
= v Si v T
(m (m
Sedangkan 1
1
)
2
− m2 − m2
(m − m )
2
1
2
dapat
dinyatakan
dengan:
= v S B v . Penjabarannya adalah sebagai berikut: T
) = (v 2
T
m1 − v m 2 T
(
)(
)
2
)
T
= v m1 − m 2 m1 − m 2 v , T
= v SB v T
dengan SB adalah matriks scatter antar kelas (between-class scatter matrix). Sehingga persamaan (2.9) dapat dituliskan seperti persamaan (2.10) berikut ini.
J (v ) =
T
v SB v T
(2.10)
v SW v Vektor w yang memaksimalkan J (⋅) harus memenuhi
persamaan : S B w = λ S w w . 2.4
Metrics of Discriminant Analysis
Sebagian besar metode Discriminant Analysis (DA) adalah berdasarkan persamaan Fisher-Rao. Seperti yang telah dijelaskan pada subbab sebelumnya, yaitu pada persamaan (2.11):
19
v T Av v T Bv
=
vT S Bv
(2.11)
vT SW v
Dimana: A = SB = matriks scatter antar kelas B = SW = matriks scatter dalam kelas v = matriks proyeksi (vektor eigen) Ketika distribusi data tiap kelas diasumsikan dengan menggunakan distribusi mixture Gaussian, maka untuk mendapatkan vektor diskriminannya adalah dengan menggunakan persamaan dekomposisi nilai eigen, seperti persamaan (2.12) berikut ini:
∑BV = ∑
X
VΛ
(2.12)
Dengan ∑ B merupakan matriks penyebaran antar subkelas,
∑ X merupakan
matriks kovarian, V merupakan vektor diskriminan, dan Λ merupakan matriks yang diagonalnya adalah nilai eigen. Metode DA hanya dapat diaplikasikan untuk beberapa aplikasi yang terbatas. Hal tersebut karena tiap metode DA menggunakan asumsi yang berbeda-beda. Metode Linear Discriminant Analysis (LDA) mengasumsikan vektor sampel dari tiap kelas dihasilkan dari distribusi normal multivarian. Pada metode LDA, matriks scatter antar kelas:
S B = ∑ Ci=1 (µ i − µ )(µ i − µ ) , dan matriks scatter T
ni C dalam kelas: S W = 1 ∑ ∑ (µ ij − µ i )(µ ij − µ i )T . n i =1 j =1
Dimana: C adalah jumlah kelas,
20
µ i adalah mean sample kelas i, µ adalah mean keseluruhan (termasuk sample dari semua kelas), xij adalah sample ke-j di kelas ke-i, dan
ni jumlah sample di kelas ke-i tersebut. Sedangkan metode Nonparametric Discriminant Analysis (NDA) mengasumsikan bahwa data di tiap kelas dikelompokkan ke dalam cluster tunggal. Metode NDA tidak akan bekerja dengan baik ketika data di tiap kelas dibagi menjadi dua cluster atau lebih. Metode NDA menggunakan matriks scatter antar kelas dengan versi non parametrik, sebagai berikut:
SB =
1 n
∑ ∑ ∑ α (x C
i =1
ni
C
j =1 l =1 l≠i
l ij
ij
)(
− µ ijl x ij − µ ijl
)
T
,
Dimana:
µ
l ij
merupakan mean dari k sample yang terdekat dengan xi yang termasuk kelas l (l ≠ i ) dan α
l ij
merupakan beberapa
factor skala yang menghalangi hasilnya dipengaruhi oleh sampel terisolasi yang terletak jauh dari batas. Alternatif lain dengan versi berbobot dari LDA adalah metode approximate Pairwise Accuracy Criterion (aPAC) ataupun Penalized Discriminant Analysis (PDA), yang mengasumsikan datanya direpresentasikan dengan cluster tunggal. Pada metode aPAC didefinisikan matriks scatter antar kelas yang baru dengan versi berbobot, C −1
yaitu: S B = ∑ i =1 ∑
C j = i +1
w ( d ij ) S ij ,
21 Dimana:
S ij = (µ i − µ j )(µ i − µ j ) , T
d ij adalah jarak Mahalanobis antara kelas i dan j, dan w(.) adalah fungsi bobot. Untuk metode Penalized Discriminant Analysis (PDA), definisi matriks scatter dalam kelas adalah : B = SW + Ω . Namun, metode LDA, NDA dan PDA, tidak dapat menyelesaikan permasalahan yang kelas-kelasnya terpisah secara non linier. Sehingga, solusinya adalah dengan menggunakan metode non linier, seperti Flexible Discriminant Analysis (FDA) dan Generalized Discriminant Analysis (GDA). FDA berusaha merumuskan ulang dengan menggunakan fungsi non linier. Sedangkan GDA dengan cara menggunakan kernel. Namun terdapat beberapa permasalahan, sehingga menghalangi penggunaan metode FDA dan GDA, diantaranya adalah: 1.
Menemukan kernel yang tepat untuk permasalahan (untuk setiap distribusi data).
sebagian
2.
Pendekatan non linier (seperti FDA) secara umum memerlukan jumlah sampel yang cukup besar agar berhasil dalam menggunakan algoritma tersebut.
3.
Metode non linier biasanya memiliki biaya perhitungan yang tinggi.
Satu hal yang menjadi kekurangan metode DA, dan tidak dibahas sebelumnya adalah kurangnya rank A. Sebagai contoh, rank (S B ) ≤ C − 1 , oleh karena itu LDA, PDA, aPAC, dan metode DA yang lain, hanya dapat mengekstrak C – 1 ciri dari ruang ciri asli. Namun pada prakteknya, data jarang terpisah secara linier, dan C – 1 ciri diperoleh bukan merupakan yang
22 optimal. Hal tersebut melatarbelakangi pendefinisian metrik baru yang dapat digunakan untuk mengekstrak lebih dari C – 1 ciri. Beberapa kekurangan-kekurangan metode DA yang telah dijelaskan secara singkat sebelumnya, merupakan hal yang menjadi dasar adanya metode SDA. 2.5
Metode Subclass Discriminant Analysis (SDA)
Metode Subclass Discriminant Analysis (SDA) merupakan salah satu pengembangan dari metode Discriminant Analysis. Mengacu pada beberapa kekurangan-kekurangan yang dimiliki oleh metode-metode DA sebelumnya, SDA diperkenalkan dengan tujuan agar dapat menyesuaikan terhadap sebagian besar tipe distribusi data. Hal tersebut dapat dilakukan dengan cara mengasumsikan tipe distribusi data tiap kelasnya dengan mixture of Gaussian. Gaussian mixture cukup fleksibel ketika menggambarkan beberapa distribusi data yang banyak ditemui pada aplikasi nyata. Sehingga solusinya adalah dengan menentukan seberapa banyak mixture Gaussian-nya, atau dengan kata lain seberapa banyak jumlah subkelasnya di tiap kelas. Pada subbab sebelumnya telah dijelaskan secara singkat mengenai kekurangan-kekurangan dari beberapa metode Discriminant Analysis (DA). Diantaranya adalah kurangnya nilai rank A. Contohnya, rank (S B ) ≤ C − 1 , maka pada LDA, PDA, aPAC, dan metode DA yang lain, hanya dapat mengekstrak C - 1 ciri dari ruang ciri asli. C – 1 ciri belum tentu bisa digunakan untuk membedakan sebanyak C kelas. Pada prakteknya, jarang sekali terdapat data yang terpisah secara linier dan C – 1 ciri yang diperoleh bukanlah yang optimal. Karena permasalahan tersebut, maka didefinisikan matriks baru sebagai alternatif agar dapat digunakan untuk mengekstrak lebih dari C – 1 ciri, yaitu dengan mendefinisikan matriks A yang mempertimbangkan perbedaan mean antar kelas dan kovariannya. Heteroscedastic LDA (HLDA) merupakan suatu metode yang
23 menggunakan jarak Chernoff untuk memperkirakan kemiripan kelas yang berdasarkan pada mean dan kovarian. Pada HLDA, didefinisikan matriks A sebagai berikut:
SC =
C −1
∑ i =1
−1 ( µ i − µ j )(µ i − µ j )T ∑ ij 2 + − 12 ∑ ∑ ij 1 1 j = i +1 4 log ∑ ij − log ∑ i − log ∑ j 2 2 C
Dimana ∑ i adalah matriks kovarian dari sample di kelas i,
∑ ij adalah rata-rata antara ∑ i dan ∑ j dan diasumsikan dengan prior yang sama. Metode ini dapat digunakan untuk mendapatkan ruang sub berdimensi dua yang kelas-kelasnya terpisah secara linier. Berdasarkan metode HLDA tersebut, ketika metode SDA membagi data di tiap kelas menjadi beberapa subkelas, maka didefinisikan matriks scatter baru yang rank nya dapat lebih dari C – 1 ciri. Sehingga berdasarkan definisi tradisional matriks scatter pada LDA, didefinisikan matriks scatter antar subkelas seperti yang tertulis pada persamaan (2.13) berikut ini:
∑ˆ B =
C
Hi
i =1
j =1
∑∑
p ij (µ ij − µ )(µ ij − µ )
T
(2.13)
Dimana H i adalah jumlah pembagian subkelas di kelas i,
pij dan µ ij merupakan prior dan mean subkelas ke-j di kelas i. Seperti pada LDA, persamaan (2.13) di atas mencoba untuk memaksimalkan jarak antar mean kelas dan jarak antar mean subkelas di kelas yang sama.
ˆ , dapat ∑ B ˆ = S + Q , dengan Q = C ni Q , didekomposisi menjadi ∑ ∑i =1 n i B B Matriks
kovarian
dari
mean
subkelas
24 dan Qi merupakan jarak antar mean subkelas di kelas yang sama,
Qi = ∑ j =i1 H
nij ni
(µ
− µ i )(µ ij − µ i ) , dengan nij adalah jumlah T
ij
sampel di subkelas ke-j di kelas i. Pembuktian definisi di atas adalah sebagai berikut:
∑ˆ B = S B + Q C
C
= ∑ (µi − µ )(µi − µ ) + ∑ T
i =1
C
i =1
ni n
C
Hi
H i nij ∑ (µij − µi )(µij − µi )T n j =1 i
ni nij (µij − µi )(µij − µi )T j =1 n ni
= ∑ (µi − µ )(µi − µ ) + ∑∑ T
i =1
i =1
C
C
Hi
= ∑ (µi − µ )(µi − µ ) + ∑∑ T
i =1
i =1 j =1
nij n
(µ
− µi )(µij − µi )
T
ij
Persamaan di atas dapat digunakan pada persamaan dekomposisi nilai eigen untuk mendapatkan vektor yang memaksimalkan jarak antar mean kelas dan jarak antar mean subkelas di kelas yang sama. Persamaan tersebut akan bekerja dengan baik ketika pembagian subkelasnya optimal. Maka didefinisikan ∑ B baru, persamaan (2.14), yang mengukur penyebaran subkelas-subkelas di kelas yang berbeda, dan juga mengukur penyebaran dalam subkelas. C −1 H i
∑ B = ∑∑
C
Hk
∑∑p
i =1 j =1 k = i +1 l =1
ij
pkl (µ ij − µ kl )(µij − µ kl )
T
(2.14)
25
Dimana pij =
nij n
merupakan prior dari subkelas ke-j di
kelas i, dengan nij adalah jumlah sampel subkelas ke-j di kelas i, dan n adalah jumlah sampel keseluruhan. 2.5.1
Pembagian Subkelas yang Optimal
Pada algoritma Subclass Discriminant Analysis (SDA), sampel di tiap kelas dibagi menjadi beberapa subkelas. Jumlah data di tiap subkelas diusahakan sama rata. Algoritma yang digunakan untuk membagi tiap kelas menjadi beberapa subkelas adalah algoritma NN-Clustering. Setelah data di tiap kelas dibagi menjadi beberapa subkelas, agar persamaan (2.14) memberikan hasil yang optimal, ditentukan jumlah subkelas yang optimal dengan cara stability criterion. 2.5.1.1
Membagi Data di Tiap Kelas Menjadi Subkelas Berdasarkan Algoritma NN-Clustering
Membagi data di tiap kelas menjadi beberapa subkelas dilakukan dengan metode pengelompokan yang berdasarkan algoritma NN-Clustering. Metode pengelompokan ini diharapkan dapat bekerja dengan baik ketika jumlah sampelnya besar ataupun kecil. Sebelum membagi tiap kelas menjadi beberapa subkelas, yang dilakukan pertama kali adalah mengurutkan sampel-sampel di kelas i. Misalnya, sampel yang telah terurut di kelas 1 adalah X1 = {x1, x2, x3, ..., xn}. Maka x1 dan xn adalah dua sampel di X1 yang memiliki jarak paling jauh, yaitu dengan mencari persamaan argmaxjk ||xj2-xk2||. Dan, x2 merupakan vektor yang paling dekat dengan x1, dan xn-1 merupakan vektor yang paling dekat dengan xn. Setelah mengurutkan data di tiap kelas, langkah selanjutnya adalah membagi tiap kelas menjadi H subkelas. Membagi tiap kelas menjadi H subkelas dilakukan dengan jumlah
26 sampel tiap subkelas yang sama rata. Misalnya, tiap kelas akan dibagi menjadi 2 (dua) subkelas. Maka kumpulan tersebut akan menjadi xi1 , ..., xi [ni / 2 ] dan xi [ni / 2 ]+1 , ..., xini .
{
}
{
}
Gambar 2.2 berikut ini merupakan ringkasan dari metode pengelompokan berdasarkan algoritma NN-Clustering. Algoritma 1 NN Clustering for i = 1 to C do Misal
{
Xˆ i = xˆ i1 , ..., xˆ ini
} menjadi sample di kelas i.
Membuat matriks D = {dij} dimana dij adalah jarak Euclidean antara sample i dan j, dengan kata lain d jk = xˆij − xˆik . 2
Misal
xi1 = xˆis
dan
for g = 1 to
xig+1 = xˆim ,
xini = xˆib
ni /2 †
dimana
[s,b] = argmaxj,k d jk
do
dimana
m = arg min j ≠ s d sj .
d sm = ∞
xini−g = xˆik dimana k = arg min j ≠b d bj .
d bj = ∞ end for Membagi kumpulan
{xˆ
i1
, ..., xˆini
}
hasil
menjadi
yang
telah
subkelas
diurutkan Hi.
Saat
melakukannya, diusahakan agar jumlah sample di setiap subkelas sama. end for
† untuk ketika mod(ni / 2) ≠ 0 , disini akan ada sample yang ditinggalkan untuk diurutkan. Ini akan dengan jelas sesuai dengan
xi,ni / 2+1 .
Gambar 2.2 Algoritma NN Clustering
27 2.5.1.2
Stability Criterion
Tujuan utama persamaan Fisher Rao, (2.11) adalah memaksimalkan ∑ B dan meminimumkan ∑ X . Ketika vektor eigen ke-i dari ∑ B dan vektor eigen ke-j dari ∑ X sama, maka hasil yang diperoleh ketika menggunakan persamaan (2.12) akan tergantung pada rasio antara nilai eigen dari ∑ B dan ∑ X . Sehingga tidak ada cara untuk mengetahui pilihan mana yang terbaik untuk klasifikasi, apakah vektor eigen dari ∑ B atau vektor eigen dari ∑ X . Misal, uj merupakan vektor eigen dari ∑ X dan wi merupakan vektor eigen dari ∑ B . Karena vektor eigen pertama dari ∑ B dan ∑ X sama (uj = wi), maka ketika menggunakan persamaan (2.12) untuk mereduksi dimensi, vektor eigen dari ∑ B yang variansinya besar dan vektor eigen dari ∑ X variansinya kecil tidak dapat dipilih.
yang
Pada beberapa kasus, persamaan (2.12) bisa memberikan hasil yang benar. Namun, untuk beberapa kasus lain, persamaan (2.12) bisa memberikan hasil yang salah. Hal tersebut memberi kesimpulan bahwa penggunaan persamaan (2.12) bersifat tidak stabil. Idealnya, ketika menggunakan persamaan (2.12), diharapkan persamaan tersebut bisa memberikan hasil yang tepat. Ketika nilai eigen dari vektor uj lebih kecil dari nilai eigen dari vektor wi, hasil yang diperoleh dari persamaan (2.12) akan optimal berdasarkan dengan Bayes. Ketika nilai eigen dari vektor uj lebih besar dari nilai eigen dari vektor wi, maka hasil yang diperoleh dari persamaan (2.12) tidak menjamin dapat menjadi optimal, karena tidak dapat memaksimalkan v T ∑ B v dan meminimumkan v T ∑ X v secara simultan.
28 Permasalahan tersebut dapat dengan mudah diketahui karena ketika hal tersebut terjadi, sudut antara vektor eigen pertama dari ∑ B dan ∑ X adalah mendekati nol (kecil). Sehingga dapat dihitung dengan persamaan (2.15) berikut ini: m
i
(
K = ∑∑ u wi i =1 j =1
T j
)
2
(2.15)
Dimana m < rank (∑ B ) , dengan nilai K yang sekecil mungkin. Keadaan ideal yang diinginkan adalah satu matriks dapat dimaksimalkan, dan satu matriks lainnya dapat diminimalkan. Untuk mencapai keadaan ideal tersebut, digunakan metode yang membagi tiap kelas menjadi sejumlah subkelas yang optimal, yang dapat meminimalkan persamaan (2.15). Untuk menggunakan stability criterion secara efisien, maka diperlukan untuk menghitung nilai K dari persamaan (2.15) untuk setiap nilai H yang mungkin, dan kemudian memilih nilai yang paling kecil. Dengan kata lain adalah menghitung persamaan (2.16) berikut ini: m
i
(
K H = ∑∑ u Tj wH , j i =1 j =1
)
2
(2.16)
Dimana wH ,i adalah vektor eigen ke-i dari ∑ B ketika datanya dibagi dengan H subkelas. Kemudian menentukan jumlah subkelas yang optimal, yang dapat meminimalkan persamaan (2.16). Nilai KH tergantung nilai m. Semakin besar nilai m, maka semakin besar pula nilai KH. Langkah selanjutnya adalah menentukan jumlah subkelas yang optimal, yang meminimalkan nilai dari persamaan (2.16), dengan persamaan (2.17) berikut ini:
H 0 = arg min H
1 KH m
(2.17)
29 Gambar 2.3 berikut ini merupakan ringkasan teknik stability criterion. Algoritma 2 SDAstability Mengurutkan clustering. Menghitung
training
sample
menggunakan
NN
class
∑X ∑ X U = UΛ X
Menghitung for H = C to l · C Menghitung
†
do
∑B
Memperhitungkan ∑ X W = WΛ B Menghitung KH menggunakan persamaan:
K =
∑ ∑ (u m
i =1
j =1
)
2
i
T j
wH,j
end for
H 0 = arg min H m −1 K H Menghittung Matriks
∑B
dengan H = H0.
proyeksi
akhir
pertama dari V, dimana †
Vq*
diberikan
∑ −X1 ∑ B V = VΛ X
oleh .
Nilai l ditetapkan sendiri. Gambar 2.3 Algoritma Stability Criterion
kolom
q
