daftar isi -...
TRANSCRIPT
Vol. 5, No. 3, Januari 2010 ISSN 0216-0544
DAFTAR ISI
ALGORITMA PEMUTUSAN SIKLUS ITERATIF PADA 137-146
ESTIMASI ROTASI CITRA DENGAN MENGGUNAKAN
PSEUDO-POLAR FOURIER TRANSFORM Arya Yudhi Wijaya, Agus Zainal Arifin, dan Diana Purwitasari
PENGENALAN CITRA WAJAH MENGGUNAKAN 147-156
METODE TWO-DIMENSIONAL LINEAR DISCRIMINANT
ANALYSIS DAN SUPPORT VECTOR MACHINE Fitri Damayanti, Agus Zainal Arifin, dan Rully Soelaiman
ESTIMASI BENTUK STRUCTURING ELEMENT 157-165
BERDASAR REPRESENTASI OBYEK Sri Huning Anwariningsih, Agus Zainal Arifin, dan Anny Yuniarti
OPTIMASI METODE DISCRIMINATIVELY 166-174
REGULARIZED LEAST SQUARE CLASSIFICATION
DENGAN ALGORITMA GENETIKA Ariadi Retno Tri Hayati Ririd, Agus Zainal Arifin, dan Anny Yuniarti
PERBAIKAN STRUKTUR WEIGHTED TREE DENGAN 175-185
METODE PARTISI FUZZY DALAM PEMBANGKITAN
FREQUENT ITEMSET Budi Dwi Satoto, Daniel O Siahaan, dan Akhmad Saikhu
SIMULASI PERGERAKAN PENGUNJUNG MALL 186-196
MENGGUNAKAN POTENTIAL FIELD Arik Kurniawati, Supeno MS Nugroho, dan Moch Hariadi
DETEKSI OUTLIER BERBASIS KLASTER PADA SET DATA 197-204
DENGAN ATRIBUT CAMPURAN NUMERIK DAN KATEGORIKAL Dwi Maryono dan Arif Djunaidy
Vol. 5, No. 3, Januari 2010 ISSN 0216 - 0544
137
ALGORITMA PEMUTUSAN SIKLUS ITERATIF PADA
ESTIMASI ROTASI CITRA DENGAN MENGGUNAKAN
PSEUDO-POLAR FOURIER TRANSFORM
*Arya Yudhi Wijaya, **Agus Zainal Arifin, ***Diana Purwitasari
Program Pasca Sarjana, Jurusan Teknik Informatika, ITS
Jl. Raya ITS, Kampus ITS, Sukolilo, Surabaya, 60111
E-Mail: *[email protected], **[email protected], ***[email protected]
Abstrak
Registrasi citra adalah proses sistematik untuk menempatkan citra yang terpisah
dalam sebuah kerangka acuan yang sama, sehingga informasi yang dikandung oleh
citra tersebut dapat diintregasikan atau dibandingkan secara optimal. Estimasi sudut
rotasi dan translasi untuk registrasi citra dilakukan menggunakan Pseudo-polar
Fourier Transform (PPFT). Akurasi akan dicapai secara optimal apabila dilakukan
iterasi pada estimasi dengan batasan tingkat kesalahan sesuai nilai threshold yang
ditentukan sebelumnya. Proses iterasi membuat kompleksitas registrasi menjadi
kurang efisien. Penelitian ini bertujuan mengoptimasi registrasi citra dengan
mengusulkan estimasi rotasi citra non-iteratif dengan PPFT. Optimasi dilakukan
dengan menghapus sejumlah iterasi pada estimasi rotasi citra iteratif dengan PPFT
menjadi satu kali proses estimasi, yaitu dengan menjadikan nilai-nilai sekitar estimasi
sudut rotasi sebagai kandidat yang baru. Selanjutnya, I1 dirotasi dengan kandidat
sudut estimasi. Sudut estimasi yang paling akurat adalah sudut estimasi yang
menghasilkan penghitungan nilai phase correlation tertinggi antara I2 dan citra-citra
hasil rotasi I1 oleh kandidat sudut estimasi. Uji coba menunjukkan bahwa nilai iterasi
yang dapat dihapus pada registrasi citra iteratif menggunakan PPFT adalah sebesar 3-
11. Metode yang diusulkan juga memiliki kekuatan estimasi pada citra ber-noise jenis
gaussian noise yang memiliki mean µ = 0 hingga varian σ sebesar 0,13.
Kata kunci: registrasi citra, Pseudo-polar Fourier Transform, phase-correlation.
Abstract
Image registration is a systematic process to put the separated image in a frame, so
the information of the image can be integrated or compared optimally. The estimation
of rotation and translation to register image is done by using Pseduo-polar Fourier
Transform (PPFT). The accuracy will be reached optimally if iteration on estimation
by the limitation in the level of mistake according to treshold which is determined.
The iteration process creates the complexity of registration less efficient. This
research purposes to optimize the image registration by giving suggestion estimation
of non interactive of image rotation by using PPFT. The optimum which is done by
deleting a number of estimation of iterative image rotation with the PPFT becomes
once of estimation process. The deletion of iteration value which is done by uniting
the surround of estimation of rotation side as a new candidate. Furthermore, I1 is
rotated with estimation of estimation side. The most accurate side is the side resulting
in the calculation of the highest phase correlation value between I2 and rotation
image I1, candidate estimation side. The try out shows that the iteration value which
is deleted on registration of iterative image using PPTF is 3–11. The method
pruposed has estimation on image of noise of gaussian noise having mean u=0 till
variant 0 for 0,13.
Key words: image registration, Pseudo-polar Fourier Transform, phase-correlation.
138 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 137-146
PENDAHULUAN
Registrasi citra adalah proses menemukan
kembali titik-titik yang bersesuaian antara citra
I1 dengan citra I2. Citra I2 adalah citra I1 yang
mengalami transformasi geometri antara lain
translasi (translation), rotasi, perbesaran
(scaling), pembalikan (fliping), dan penarikan
(stretching). Registrasi citra memainkan peran
utama dalam banyak aplikasi misalnya
kompresi video [1], perbaikan kualitas video
[2], scene representation [3], dan analisa citra
medis [4]. Beberapa metode telah diusulkan untuk
registrasi citra. Registrasi citra pada domain
spasial dilakukan dengan cara mencari nilai
rata-rata, median, atau ukuran statistika lainnya
pada setiap nilai derajat keabuan (grayscale)
atau RGB citra [5]. Registrasi citra pada
domain frekuensi spasial bekerja dengan baik
ketika diaplikasikan terhadap citra yang
memiliki tingkat ketidakteraturan kecil.
Registrasi citra pada domain frekuensi
dilakukan dengan menggunakan Transformasi
Fourier. Metode berbasis Transformasi
Fourier mampu memperkirakan skala
perbesaran, rotasi, dan translasi lebih akurat
dibandingkan dengan metode pada domain
spasial. Sebagian besar pendekatan yang
dilakukan berdasarkan Transformasi Fourier
memanfaatkan nilai translasi pada domain yang
dapat diestimasi dengan akurat oleh phase
correlation [6]. Phase correlation adalah
metode dalam registrasi citra untuk
mengestimasi translasi dua citra yang mirip
dengan memanfaatkan nilai puncak fase pada
domain frekuensi.
Metode mutahir yang diusulkan dalam
registrasi citra pada domain frekuensi adalah
estimasi skala rotasi dan translasi
menggunakan Pseudo-polar Fourier Transform
(PPFT) [7,8]. Perbedaan mendasar pada
penelitian yang dilakukan Reddy dkk [7] dan
Guo dkk [8] adalah penggunaan metode
penghitungan translasi PPFT pada koordinat
polar. Penghitungan translasi PPFT dapat
dilakukan dengan menggunakan Analytical
Fourier-Mellin Transform [7] maupun phase
correlation [8].
Langkah pertama yang dilakukan untuk
estimasi rotasi dengan PPFT adalah dengan
melakukan mapping citra dari domain spasial
ke domain frekuensi di atas pseudopolar-grid.
Rotasi diestimasi dengan mengubah basis
koordinat kartesian (x,y) ke basis koodinat
polar (r,θ). Sudut rotasi adalah translasi I2
terhadap I1 pada sumbu θ. Estimasi rotasi dan
translasi dengan PPFT memiliki akurasi yang
tinggi. Akan tetapi, akurasi akan dicapai secara
optimum apabila dilakukan iterasi dengan
batasan tingkat kesalahan sesuai nilai threshold
yang ditentukan sebelumnya. Proses iterasi ini
menjadikan registrasi menjadi boros dalam hal
komputasi.
Penelitian ini mengusulkan suatu metode
untuk meningkatkan efisiensi komputasi
dengan cara mengubah cara iteratif menjadi
non-iteratif tanpa mengurangi akurasi dari hasil
estimasi rotasi dan translasi. Cara non-iteratif
dilakukan dengan dua tahap utama yaitu tahap
representasi PPFT dan tahap estimasi dengan
memanfaatkan phase correlation. Tahap
representasi melakukan perbaikan representasi
PPFT, sehingga phase correlation akan dapat
mengestimasi translasi dengan lebih akurat.
Sedangkan tahap estimasi dilakukan tanpa
iterasi karena menggunakan kandidat lain
sebagai sudut rotasi yang merupakan tetangga
dari sudut yang ditemukan.
KONSEP REGISTRASI CITRA PADA
DOMAIN SPASIAL DAN FREKUENSI
Estimasi Pergeseran
I2 adalah citra I1 yang mengalami translasi pada
sumbu x dan sumbu y sebesar (∆x,∆y) sehingga
didapatkan Persamaan (1).
∆y)+y∆x,+(xI=y)(x,I 21 (1)
maka besar translasi I2 terhadap I1 sebesar
(∆x,∆y) dapat ditemukan secara akurat dengan
phase correlation [9]. Metode estimasi
translasi dengan phase correlation dapat
dilakukan dengan Transformasi Fourier 2D
pada I1 dan I2 sehingga secara berturut-turut
menghasilkan 1I dan 2I . 1I dan 2I berturut-
turut adalah citra I1 dan I2 dalam domain
Fourier Transform yang dinotasikan dengan
Persamaan (2).
11ˆ I=I ℑ ; 22
ˆ I=I ℑ (2)
Selanjutnya dilakukan penghitungan phase
correlation dengan Persamaan (3).
Wijaya dkk, Algoritma Pemutusan Siklus Iteratif… 139
|II|
II=
∗
∗ℜ
21
21 ˆˆ
ˆˆ (3)
dimana ℜ adalah phase correlation dari 1I
dan 2I . Sedangkan I2* adalah complex
conjugate dari I2. Selanjutnya dicari phase
correlation R pada domain spasial dimana R
adalah seperti yang ditunjukkan oleh
Persamaan (4).
ℜℑ−1=R (4)
Translasi citra I2 terhadap I1 dapat ditemukan
dengan mencari letak puncak dari R yaitu
degan menggunakan Persamaan (5).
R=∆y)(∆∆xy)(x,
xamgra (5)
∆x adalah besar translasi I2 terhadap I1 pada
arah sumbu x, sedangkan ∆y adalah besar
translasi I2 terhadap I1 pada arah sumbu y.
Estimasi Rotasi
Apabila I2 adalah citra I1 yang mengalami
rotasi sebesar ∆θ, maka cara untuk menemukan
sudut rotasi relatif I2 terhadap I1 sebesar ∆θ
adalah dengan mengubah sistem koordinat
kartesian pada citra I1 dan I2 menjadi sistem
koordinat polar sehingga didapatkan
Persamaan (6).
∆θ)+θ(r,I=θ)(r,I 21 (6)
),(1 θrI adalah citra I1 pada koordinat polar
dan ),(2 θθ ∆+rI adalah citra I2 pada
koordinat polar dimana I2 memiliki sudut rotasi
relatif sebesar ∆θ terhadap I1. r adalah jarak
suatu titik dengan pusat koordinat dan θ adalah
rotasi relatif terhadap sumbu x positif dengan
pusat rotasi pangkal koordinat.
Gambar 1(a) dan (b) adalah I1 dan I2 pada
koordinat kartesian. Dilakukan transformasi I1
dan I2 menuju sistem koordinat polar sehingga
secara berurutan I1 dan I2 berubah menjadi
seperti pada Gambar 1(c) dan (d). Sumbu
horisontal pada Gambar 1(c) dan (d)
merupakan sumbu r. Sedangkan sumbu vertikal
pada Gambar 1(c) dan (d) merupakan sumbu θ.
Dapat diamati bahwa ∆θ)+θ(r,I2 yang
ditunjukkan oleh Gambar 1(d) merupakan versi
translasi sepanjang sumbu θ dari θ)(r,I1 yang
ditunjukkan Gambar 1(c). Besar translasi
sepanjang sumbu θ ∆θ)+θ(r,I2 terhadap
θ)(r,I1 dapat ditemukan secara akurat dengan
phase correlation. Sehingga, sudut rotasi
relatif I2 terhadap I1 sebesar ∆θ dapat dicari
dengan mereduksi peristiwa rotasi menjadi
peristiwa translasi pada koordinat polar.
(a) (b) (c) (d)
Gambar 1. Estimasi rotasi. (a) Citra I1, (b) Citra I2 yang merupakan versi rotasi sebesar ∆θ
terhadap I1, (c) I1 pada sistem koordinat polar, dan (d) I2 pada sistem koordinat polar.
(a) (b) (c)
Gambar 2. Pseudopolar-grid (contoh: masukan citra 8x8). (a) P1, (b) P2, dan (c) P = P1UP2.
140 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 137-146
Kendala Estimasi Rotasi pada Domain
Spasial
Konsep estimasi translasi dan rotasi dengan
phase correlation yang dipaparkan pada bagian
sebelumnya akan menghasilkan estimasi yang
akurat apabila I1 dan I2 memiliki pusat rotasi
yang sama, dimana pusat tersebut telah
didefinisikan terlebih dahulu (secara default
pusat perbesaran berada di titik tengah citra).
Akan tetapi, hasil estimasi rotasi I2 terhadap I1
tidak akurat apabila diterapkan pada citra yang
memiliki pusat rotasi yang tidak sama. Kendala
ini terjadi akibat adanya translasi citra I2
terhadap I1, sehingga pusat rotasi dan
perbesaran yang seharusnya sama menjadi
bergeser. Peristiwa ini seharusnya tidak akan
menjadi kendala apabila pengerjaannya
dilakukan pada domain frekuensi. Domain
frekuensi menjadi solusi karena adanya sifat
shift invariant pada domain frekuensi, yang
berarti bahwa domain frekuensi tidak
dipengaruhi oleh translasi.
Berdasarkan konsep ini, maka diusulkan
metode yang mengadopsi prinsip yang
dilakukan pada sub bagian sebelumnya, akan
tetapi dilakukan pada domain frekuensi [8].
Domain frekuensi yang diusulkan adalah
Pseudo-polar Fourier Transform (PPFT)
seperti yang diperlihatkan dalam Persamaan
(7).
21 PPP ∪≡ (7)
dimana
≤≤−≤≤−
−≡ NkN,N
lN
|kk,N
P22
2l1
dan (8)
≤≤−≤≤−
−≡ NkN,N
lN
|kN
k,P22
2l2
(9)
P adalah pseudopolar-grid yang tersusun
dari gabungan P1 dan P2. P1 adalah komponen
P pada arah vertikal dan P2 adalah komponen P
pada arah horisontal. k disebut sebagai
pseudoradius dan l disebut sebagai
pseudoangle. Resolusi dari pseudopolar-grid
untuk citra ukuran N x N adalah 2N +1 pada
bagian angular dan N + 1 pada bagian radial.
Ilustrasi himpunan P1 dan P2 dapat dilihat
pada Gambar 2(a) dan (b). Pseudopolar-grid P
diilustrasikan pada Gambar 2(c). Dengan
representasi pada koordinat polar (r,θ),
pseudopolar-grid didefinisikan dengan
Persamaan (10).
)θ,(r=l)(k,P lk
11
1dan
)θ,(r=l)(k,P lk
22
2 (10)
Dimana
14
2
1+
N
lk=rk
, 14
2
2 +N
lk=rk
(11)
−N
π=θl
2larctan2/1 dan
N
=θl
2larctan2 (12)
Nilai k = –N, …, N dan l = – N/2, …, N/2.
Nilai PPFT didefinisikan sebagai sampel
dari Transformasi Fourier di atas pseudopolar-
grid P yang diberikan pada Persamaan (8) dan
(9). Secara detil, PPFT )=(jI j
pp 1,2ˆ adalah
sebuah transformasi linear, dimana terdefinisi
untuk k = –N,…,N dan l = – N/2,…,N/2,
sebagai Persamaan (13) dan (14).
∑−
−
−−
−≡
12/
2/
1
1
2i2πexp ˆ
2lˆˆ
N
N=vu,
pp
pp
kv+kuNM
v)I(u,=I
kk,N
II (13)
.2i2π
expˆ
2lˆˆ
12/
2/
2
2
∑−
−
−−
−≡
N
N=vu,
pp
pp
kvN
kuM
v)I(u,=I
kN
k,II (14)
I adalah I pada domain frekuensi. 1ˆppI
adalah
nilai PPFT yang akan diberikan di atas P1 dan 2ˆppI adalah nilai PPFT yang akan diberikan di
atas P2.
Sebagaimana dapat dilihat pada Gambar
2(c), untuk setiap sudut yang telah ditentukan
sebesar l, sampel dari pseudopolar-grid
memiliki space yang sama pada bagian radial.
Akan tetapi, space ini berbeda untuk sudut
yang berbeda. Demikian pula, grid memiliki
space yang tidak sama dalam bagian angular,
tetapi memiliki space kemiringan yang sama
(lihat Persamaan (15) dan (16)).
N=θθ(l)θ∆ l+lpp
2cotcottan 11
1
1 −≡ (15)
N=θθ(l)θ∆ l+lpp
2cotcottan 22
1
2 −≡ (16)
dimana θpp
1
dan θpp
2
diberikan pada
Persamaan (12).
Properti penting PPFT adalah bahwa
transformasi ini memiliki kemampuan invert.
Wijaya dkk, Algoritma Pemutusan Siklus Iteratif… 141
Selain itu, PPFT forward dan invert dapat
diaplikasikan dengan sebuah komputasi yang
cepat dengan bantuan FrFT. Dan yang lebih
penting lagi, algoritma ini tidak membutuhkan
regriding atau interpolasi sehingga memiliki
keakuratan yang tinggi.
Fractional Fourier Fourier (FrFT)
Kompleksitas penghitungan PPFT dapat
ditekan dengan bantuan FrFT. FrFT adalah
algoritma cepat dengan komputasi O(N logN)
yang dapat memetakan Transformasi Fourier
Diskrit (DFT) di atas beberapa himpunan dari
N titik pada sebuah keliling lingkaran [8].
Sehingga FrFT menjadikan kompleksitas
komputasi keseluruhan PPFT pada Persamaan
(13) dan (14) yang semula adalah O(N3)
kemudian dapat direduksi menjadi O(N2 logN).
Lebih spesifik, diberikan sebuah vektor C
dengan panjang N+1, )(uCC = ,
)2/,...,2/( NNu −= , Rα∈ . FrFT
didefinisikan sebagai Persamaan (17).
∑−
−2/
2/
1 1/2ππiexpN
N=u
α
+N )]+(Nku[C(u)=C)(k)(F
N/2 ,N2,.......k −= (17)
Algoritma Estimasi Rotasi Iteratif dengan
PPFT
Algoritma estimasi rotasi iteratif dengan
menggunakan PPFT [8] dapat dilihat pada
Gambar 3. Penjelasan algoritma pada Gambar
3 adalah sebagai berikut:
1. Magnitude PPFT dihitung setelah dilakukan
zero-padding pada citra masukan sehingga
memiliki ukuran yang sama.
2. θ ditemukan dengan melakukan 1D phase
correlation sepanjang sumbu θ pada domain
pseudo-polar. 3. Salah satu dari citra masukan diputar
dengan sudut akumulasi θn.
4. Dilakukan iterasi langkah 1-3 hingga ∆θ
lebih kecil dari threshold yang ditentukan
yaitu sebesar εθ.
5. Ambiguitas θ diselesaikan dengan
menggunakan 2D phase correlation, yaitu
dengan memutar salah satu citra sebesar θ
dan θ+π. Ambiguitas ini disebabkan oleh
ambiguitas nilai arctan p yang dapat
bernilai θ atau θ + π.
6. Pergeseran ditemukan dengan menggunakan
2D phase correlation.
Gambar 3. Algoritma Estimasi Rotasi Iteratif dengan PPFT.
142 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 137-146
Gambar 4. Estimasi Rotasi Non-iteratif dengan PPFT.
(a) (b) (c) (d)
Gambar 5. (a) Citra I1, (b) Citra I2, (c) θ)(r,IG p1ˆ , dan (d) θ)(r,IG p2
ˆ .
Gambar 6. Sudut Tetangga αT yang Menjadi Kandidat Baru Sudut Rotasi.
Wijaya dkk, Algoritma Pemutusan Siklus Iteratif… 143
(a) (b) (c) (d)
Gambar 7. Salah Satu Contoh Uji Coba. (a) Citra I1, (b) Citra I2 Memiliki Rotasi Relatif 66°
terhadap I1, (c) PPFT I1 dan I2 dalam Representasi Grayscale, dan (d) Citra I1
Ditambah Hasil Estimasi Rotasi.
(a) (b) (c) (d)
Gambar 8. Salah Satu Contoh Hasil Uji Coba. (a) Citra I1, (b) Citra I2 Memiliki Rotasi Relatif
33,7° terhadap I1, gaussian noise µ = 0 dan Varian σ = 0,09, (c) PPFT I1 dan I2 dalam
Representasi Grayscale, dan (d) Citra I1 Ditambah Hasil Estimasi Rotasi Citra I2.
ALGORITMA PEMUTUSAN SIKLUS
ITERATIF ESTIMASI ROTASI
DENGAN PPFT
Algoritma yang diusulkan yaitu estimasi rotasi
non-iteratif dengan PPFT akan memperbaiki
algoritma estimasi rotasi iteratif dengan PPFT
yang terdapat pada Gambar 3. Perbaikan
dilakukan dengan membuang iterasi untuk
menemukan sudut rotasi optimum. Secara
keseluruhan algoritma yang diusulkan dapat
dilihat pada Gambar 4.
Algoritma memiliki dua tahap utama, yaitu
tahap representasi dan tahap estimasi. Tahap
representasi bertujuan melakukan pemrosesan
PPFT sehingga siap untuk dilakukan pencarian
nilai translasinya pada koordinat polar.
Sedangkan tahap estimasi bertujuan
mengestimasi translasi maupun mengukur
tingkat kesamaan dua buah citra dengan
memanfaatkan kemampuan phase correlation.
Tahap Representasi
Masukan dari tahap representasi adalah dua
buah citra grayscale I1 dan I2. Dilakukan
penghitungan magnitude PPFT pada masing-
masing citra I1 dan I2 sehingga menghasilkan
1ˆ
ppIM untuk I1 dan menghasilkan 2
ˆppIM
untuk
I2. Representasi PPFT dalam pseudopolar-grid
ditransformasikan pada koordinat polar
sehingga 1
ˆppIM dan
2ˆ
ppIM
masing-masing
diubah menjadi θ)(r,IM p1ˆ dan θ)(r,IM p2
ˆ pada
koordinat polar.
Dikarenakan jangkauan nilai yang sangat
besar pada θ)(r,IM p1ˆ dan θ)(r,IM p2
ˆ , maka
dilakukan operasi logaritma pada θ)(r,IM p1ˆ dan
θ)(r,IM p2ˆ sehingga menghasilkan θ)(r,IL p1
ˆ dan
θ)(r,IL p2ˆ sebagaimana Persamaan (18).
θ))(r,I(Mln+=θ)(r,IL ppˆ1ˆ (18)
θ)(r,IL p1ˆ dan θ)(r,IL p2
ˆ masih terlalu kasar
untuk dilakukan pemrosesan berikutnya karena
nilai kontras yang kecil. Oleh karena itu,
θ)(r,IL p1ˆ dan θ)(r,IL p2
ˆ
perlu diinterpolasikan
nilainya dalam interval grayscale sesuai
Persamaan (19).
=θ)(r,IG
θ)(r,IL:jika,
>IL:jika;
xθ)(r,IL
<θ)(r,IL:jika;
p
p
p
p
p
ˆ
14ˆ4
14ˆ255
255414
4ˆ
4ˆ0
≤≤
−
−
(19)
144 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 137-146
),( θrIG p
∧ adalah representasi PPFT dalam
grayscale yang telah dinormalisasi. ),(1 θrIG p
∧
dan ),(2 θrIG p
∧
adalah PPFT milik citra
masukan I1 dan I2 yang siap diestimasi
translasinya dengan phase correlation. Ilustrasi
mengenai representasi ),( θrIG p
∧ dapat dilihat di
Gambar 5. Gambar 5(a) dan (b) masing masing
adalah citra masukan I1 dan I2. Gambar 5(c)
dan (d) adalah representasi PPFT pada
grayscale yang telah dinormalisasi dengan
Persamaan 19. Terlihat dengan jelas bahwa
Gambar 5(d) adalah versi translasi dari Gambar
5(c) pada sumbu θ (vertikal).
Tahap Estimasi
Tahap estimasi diawali dengan melakukan
estimasi translasi relatif p1IG ˆ terhadap
p2IG ˆ
sepanjang sumbu θ dengan phase correlation
sebagaimana Persamaan (3). Sudut rotasi
relatif I2 terhadap I1 sebesar α ditemukan
dengan mencari besar translasi sepanjang
sumbu θ. pIG ˆ memiliki periode 180º, yang
berarti bahwa selain sudut rotasi α masih
terdapat kandidat sudut rotasi yang lain yaitu
sebesar α + 180º. Sehingga terdapat dua
kadidat sudut rotasi sebesar α1 dan α2 yang
nilainya ditunjukkan pada Persamaan (20) dan
(21).
α=α1 (20)
°+α=α 1802 (21)
Sudut rotasi sebenarnya sebesar αT dapat
dihitung dengan memanfaatkan phase
correlation 2D. I1 masing-masing diputar
sebesar α1 dan α2. Sudut rotasi sebenarnya
sebesar αT adalah sudut yang menghasilkan
puncak phase correlation terbesar.
Penghalusan sudut rotasi dengan
pembandingan sudut tetangga bertujuan untuk
meningkatkan akurasi estimasi rotasi sebesar
αT. Ide langkah ini adalah adanya
ketidakpercayaan bahwa sudut rotasi yang
sebenarnya adalah αT. Mungkin saja sudut
rotasi yang sebenarnya adalah sudut di sekitar
αT. Langkah ini akan menghemat biaya
komputasi dibandingkan dengan iterasi yang
dilakukan oleh registrasi citra iteratif dengan
PPFT. Penghematan terjadi karena iterasi yang
dilakukan akan digantikan dengan
pembandingan sudut tetangga sehingga tidak
diperlukan lagi iterasi. Gambaran mengenai
pembandingan sudut tetangga disajikan pada
Gambar 6. Jika banyaknya tetangga di atas
sudut αT adalah p dan banyaknya tetangga di
bawah sudut αT juga berjumlah p, maka
terdapat himpunan kandidat sudut rotasi yang
baru yaitu αK. Sudut rotasi akhir hasil
penghalusan adalah αR yang merupakan elemen
αK yang memiliki puncak phase correlation
tertinggi.
HASIL DAN PEMBAHASAN
Hasil Uji Coba untuk Menentukan Banyak
Iterasi yang Dihilangkan dan Akurasi
Estimasi
Uji coba pertama bertujuan untuk menentukan
banyak iterasi metode estimasi rotasi iteratif
dengan PPFT yang dapat dihapus oleh metode
yang diusulkan. Selain itu, uji coba juga
bertujuan untuk menentukan akurasi estimasi
rotasi algoritma iteratif maupun non-iteratif.
Uji coba dilakukan dengan melakukan
registrasi terhadap empat pasang citra berbeda
dimana masing-masing pasang memiliki sudut
rotasi relatif sesamanya. Sudut rotasi
sebenarnya pada masing-masing pasang citra
telah diketahui sebelumnya yaitu: 66°; 33,7°;
0,8°; dan 177°. Sudut 66° diharapkan mewakili
rotasi pada kondisi umum dengan sudut rotasi
berupa bilangan bulat di kuadran I. Selanjutnya
sudut 33,7° diharapkan mewakili rotasi pada
kondisi umum dengan sudut rotasi berupa
bilangan desimal di kuadran I. Kemudian sudut
rotasi 0,8° diharapkan dapat mewakili pada
kondisi sudut rotasi yang kecil yaitu ±1°
dimana pada umumnya sudutnya merupakan
bilangan desimal. Terakhir, sudut 177°
diharapkan mewakili rotasi pada kondisi umum
dengan sudut rotasi > 90°.
Tabel 1. Jumlah Iterasi dan Akurasi Estimasi
Rotasi Iteratif dengan PPFT.
Sudut
(deg)
Jumlah
Iterasi
Estimasi
Rotasi (deg)
Error
(deg)
066,0 11 066,09 0,09
033,7 08 033,49 0,21
000,8 03 000,68 0,12
177,0 05 177,26 0,26
Wijaya dkk, Algoritma Pemutusan Siklus Iteratif… 145
Tabel 2. Akurasi Estimasi Rotasi Non-Iteratif
dengan PPFT.
Sudut
(deg)
Jumlah
Iterasi
Estimasi
Rotasi (deg)
Error
(deg)
066,0 1 066,09 0,09
033,7 1 033,75 0,05
000,8 1 000,70 0,10
177,0 1 177,19 0,19
Tabel 3. Akurasi Estimasi Rotasi pada Citra
ber-noise (Gaussian noise, mean µ
= 0).
Rotasi
(derajat) Varian (σ)
Estimasi
Rotasi Error
0.01 34.10 0.40
0.02 33.40 0.30
0.03 34.10 0.40
0.04 33.75 0.05
0.05 34.10 0.40
0.06 34.10 0.40
0.07 34.10 0.40
0.08 34.10 0.40
0.09 33.40 0.30
0.10 33.05 0.65
0.11 33.40 0.30
0.12 33.05 0.65
0.13 34.10 0.40
0.14 34.45 0.75
0.15 33.05 0.65
33.70
0.16 08.09 25.61*)
*)nilai error estimasi rotasi terlalu besar sehingga tidak
dilanjutkan untuk nilai varian berikutnya.
Salah satu contoh uji coba dengan metode
yang diusulkan dapat dilihat pada Gambar 7.
Gambar 7(a) dan (b) adalah citra masukan I1
dan I2. I2 memiliki rotasi relatif 66° terhadap I1.
Gambar 7(c) adalah PPFT I1 dan I2 dalam
representasi grayscale. Gambar 7(d) adalah
Citra I1 ditambah hasil estimasi rotasi citra I2.
Hasil uji coba dengan metode iteratif dapat
dilihat pada Tabel 1. Iterasi yang dilakukan
untuk mencapi tingkat kesalahan terkecil
adalah sebesar 3-11 kali. Tingkat kesalahan
terbesar adalah 0,26°. Sedangkan hasil uji coba
dengan metode yang diusulkan yaitu estimasi
rotasi non-iteratif dengan PPFT yang hanya
memerlukan satu kali iterasi dapat diamati pada
Tabel 2. Tingkat kesalahan maksimum estimasi
rotasi yang diusulkan adalah sebesar 0,19°.
Hasil uji coba pada Tabel 1 dan 2
menunjukkan bahwa metode yang diusulkan
mampu memutus siklus iteratif pada estimasi
rotasi iteratif dengan PPFT. Tingkat akurasi
metode yang disulkan juga menunjukkan
tingkat kesalahan yang lebih kecil
dibandingkan metode iteratif.
Hasil Uji Coba Ketahanan Terhadap Noise
Uji coba kedua bertujuan untuk menentukan
akurasi estimasi rotasi oleh metode yang
diusulkan pada citra yang memiliki noise.
Noise yang dipilih adalah Gaussian Noise
dengan mean µ = 0 dan varian σ = 0,01; 0,02;
hingga metode yang diusulkan tidak mampu
lagi mengestimasi rotasi secara akurat.
Gaussian Noise dipilih karena lebih umum
terjadi pada dunia nyata. Sudut rotasi yang
dipilih adalah 33,7°.
Salah satu contoh uji coba kedua dapat
dilihat pada Gambar 8. Gambar 8(a) dan (b)
masing-masing adalah citra masukan I1 dan I2.
I2 adalah versi rotasi 33,7° terhadap I1 dan I2
diberi Gaussian Noise dengan mean µ = 0 dan
varian σ = 0,09. Gambar 8(c) adalah PPFT
milik I1 dan I2 pada representasi grayscale.
Sedangkan Gambar 8(d) adalah hasil estimasi
rotasi I2 terhadap I1 yang merupakan
penjumlahan I1 dan I2 hasil rekonstruksi dari
rotasi dan translasi yang ditemukan.
Hasil uji coba kedua dapat diamati pada
Tabel 3. Tingkat kesalahan tetap bernilai kecil
(di bawah 1°) hingga gaussian noise memiliki
varian 0,15. Uji coba ini membuktikan bahwa
metode yang diusulkan memiliki ketahanan
terhadap noise. Hal ini dikarenakan bahwa
dengan pengamatan visual citra yang memiliki
Gausian noise dengan mean µ = 0 dan varian σ
= 0,10 sudah tidak nampak lagi bentuk aslinya.
SIMPULAN
Berdasarkan hasil uji dan pembahasan yang
dilakukan, maka dapat ditarik simpulan:
1. Algoritma yang diusulkan mampu memutus
siklus iterasi berkisar 3-11 dibanding
146 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 137-146
algoritma registrasi citra untuk estimasi
rotasi dengan menggunakan PPFT.
2. Algoritma registrasi citra dengan PPFT
yang sebelumnya memiliki kompleksitas
komputasi O(MN2 logN), dimana M
menunjukkan banyak iterasi dan N
menyatakan ukuran citra masukan ukuran
NxN, dapat direduksi menjadi O(N2 logN)
dikarenakan iterasi sebanyak M bernilai 1.
3. Ditinjau dari segi akurasi, hasil registrasi
citra dengan metode yang diusulkan
memiliki tingkat akurasi yang signifikan
yang didapatkan secara otonom tanpa
pendefinisian nilai threshold sebelumnya.
Berbeda dengan metode registrasi PPFT
yang menggunakan iterasi, akurasi
didefinisikan sebagai nilai threshold dan
iterasi akan berhenti ketika nilai estimasi
rotasi mencapai nilai threshold yang
ditentukan.
4. Metode yang diusulkan juga memiliki
ketahanan terhadap gaussian noise yang
memiliki mean µ = 0 hingga varian σ
sebesar 0,13.
DAFTAR PUSTAKA
[1] Dufaux F and Konrad J. Efficient, Robust,
and Fast Global Motion Estimation for
Video Coding. IEEE Transaction on
Image Processing. 9: 497-501. 2000.
[2] Kuglin CD and Hines DC. The Phase
Correlation Image Alignment Method.
Proc. IEEE Conf. Cybernetics and
Society. 163-165. 1975.
[3] Irani M and Peleg S. Motion Analysis for
Image Enhancement: Resolution,
Occlusion, and Transparency. J Visual
Comm and Image Representation. 4: 324-
335. 1993.
[4] Mann S and Picard R. Virtual Bellows:
Constructing High Quality Stills from
Video. Proc IEEE Int’l Conf Image
Processing. 363-367. 1994.
[5] Wan R and Li M. An Overview of
Medical Image Registration. Fifth
International Conference on
Computational Intelligence and
Multimedia Applications (ICCIMA'03).
385. 2003.
[6] Wolberg G and Zokai S. Robust Image
Registration using Log-Polar Transform.
Proc. IEEE Int. Conf. Image Processing.
493-496. 2000.
[7] Reddy S and Chatterji BN. An FFT-Based
Technique for Translation, Rotation, and
Scale-Invariant Image Registration. IEEE
Trans. Image Processing. 3: 1266-1270.
1996.
[8] Guo X, Xu Z, Lu Y, Liu Z, and Pang Y.
Image Registration Based on Pseudo-
Polar FFT and Analytical Fourier-Mellin
Transform. Lecture Notes in Computer
Science. Berlin: Springer Berlin. 2005.
[9] Keller Y, Averbuch A, and Israeli M.
Pseudopolar-Based Estimation of Large
Translations, Rotation, and Scalings in
Images. IEEE Transactions on Image
Processing. 14: 12-22. 2005.
Vol. 5, No. 3, Januari 2010 ISSN 0216 - 0544
147
PENGENALAN CITRA WAJAH MENGGUNAKAN
METODE TWO-DIMENSIONAL LINEAR DISCRIMINANT
ANALYSIS DAN SUPPORT VECTOR MACHINE
*Fitri Damayanti, Agus Zainal Arifin, Rully Soelaiman
Program Magister Teknik Informatika,ITS
Jl. Raya ITS, Kampus ITS, Sukolilo, Surabaya, 60111
E-Mail: *[email protected]
Abstrak
Linear Discriminant Analysis telah digunakan secara luas dalam pola linier
pengenalan terhadap fitur ekstraksi dan pengurangan dimensi. Hal ini dimaksudkan
untuk membuat seperangkat vektor proyeksi yang sangat berbeda untuk dipadatkan
sepadat mungkin pada jenis yang sama. Projection vector bekerja dalam hitungan
jenis Sw dan antara jenis Sh matrix scatter. Umumnya pada aplikasi pengenalan wajah
jumlah dimensi data lebih besar dibandingkan jumlah sampelnya, hal ini
menyebabkan tunggalnya isi jenis scatter matrix Sw, sehingga fitur wajah tidak
diekstraksi dengan baik. Dalam penelitian ini digunakan metode Two Dimensional
Linier Discrimination Analysis (TDLDA) untuk ekstraksi fitur, yang menilai secara
langsung isi jenis scatter matrix tanpa pencitraan terhadap transformasi vektor,
sehingga mengurangi masalah tunggal dalam isi jenis scatter matrix. Penelitian ini
akan mengembangkan aplikasi pengenalan wajah yang dintegrasikan dengan metode
TDLDA dan SVM untuk pengenalan wajah. Dengan kombinasi kedua metode tersebut
terbukti dapat memberikan hasil yang optimal dengan tingkat akurasi pengenalan
antara 84,18% sampai 100% dengan uji coba menggunakan basis data ORL, YALE,
dan BERN.
Kata kunci: Linear Discriminant Analysis, Two Dimensional Linear Discriminant
Analysis, Support Vector Machine.
Abstract
Linear Discriminant Analysis (LDA) has been widely used in linear pattern
recognition for feature extraction and dimension reduction. It aims to find a set of
projection vector that separate the different as far as possible while compressing the
same class as compact as possible. It works by calculated the within class Sw and
between class Sb scatter matrices. In face recognition application, generally the
dimension of data larger than the number of samples, this causes the within class
scatter matrix Sw is singular, that can make the face features’s not well extracted.
Two Dimensional Linear Discriminant Analysis (TDLDA) is used on this research for
feature extraction, that evalutes directly the within class scatter matrix from the
image matrix without image to vector transformation, and hence dilutes the singular
problem of within class scatter matrix. This research will develop a face recognition
application that combined Two Dimensional Linear Discriminant Analysis and
Support Vector Machine. The combination of two methods give optimal results that
have high accuracy of recognition between 84.18% until 100% with the ORL, YALE,
and BERN database.
Key words: Linear Discriminant Analysis, Two Dimensional Linear Discriminant
Analysis, Support Vector Machine.
148 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 147-156
PENDAHULUAN
Pengenalan wajah dewasa ini telah menjadi
salah satu bidang yang banyak diteliti dan juga
dikembangkan oleh para pakar pengenalan
pola. Hal ini disebabkan karena semakin
luasnya penggunaan teknik identifikasi wajah
dalam aplikasi yang digunakan oleh
masyarakat. Para peneliti telah melakukan
penelitian terhadap teknik yang sudah ada dan
mengajukan teknik baru yang lebih baik dari
yang lama, meskipun banyak teknik baru telah
diajukan, akan tetapi teknik-teknik tersebut
masih belum dapat memberikan akurasi yang
optimal. Dua hal yang menjadi masalah utama
pada identifikasi wajah adalah proses ekstraksi
fitur dari sampel wajah yang ada dan juga
teknik klasifikasi yang digunakan untuk
mengklasifikasikan wajah yang ingin dikenali
berdasarkan fitur-fitur yang telah dipilih.
Ekstraksi fitur adalah proses untuk
mendapatkan ciri-ciri pembeda yang
membedakan suatu sampel wajah dari sampel
wajah yang lain. Bagi sebagian besar aplikasi
pengenalan pola, teknik ekstraksi fitur yang
handal merupakan kunci utama dalam
penyelesaian masalah pengenalan pola. Metode
Analisa Komponen Utama (PCA) untuk
pengenalan wajah dikenalkan oleh Turk dan
Pentland pada tahun 1991. Metode tersebut
bertujuan untuk memproyeksikan data pada
arah yang memiliki variasi terbesar
(ditunjukkan oleh vektor eigen) yang
bersesuaian dengan nilai eigen terbesar dari
matrik kovarian. Kelemahan dari metode PCA
adalah kurang optimal dalam pemisahan antar
kelas. Pada tahun 1991, Cheng dkk
memperkenalkan metode Analisa Diskriminan
Linier (LDA) untuk pengenalan wajah. Metode
ini mencoba menemukan sub ruang linier yang
memaksimalkan perpisahan dua kelas pola
menurut Fisher Criterion JF. Hal ini dapat
diperoleh dengan meminimalkan jarak matrik
sebaran dalam kelas yang sama (within-class)
Sw dan memaksimalkan jarak matrik sebaran
antar kelas (between-class) Sb secara simultan
sehingga menghasilkan Fisher Criterion JF
yang maksimal. Diskriminan Fisher Linier
akan menemukan sub ruang dimana kelas-kelas
saling terpisah linier dengan memaksimalkan
Fisher Criterion JF. Jika dimensi data jauh
lebih tinggi daripada jumlah sample training,
maka Sw menjadi singular. Hal tersebut
merupakan kelemahan dari metode LDA [1].
Telah banyak metode yang ditawarkan
untuk mengatasi kovarian kelas yang sama
(within class) yang selalu singular karena
small sample size problem. Pada tahun 1997,
Belheumeur memperkenalkan metode
fisherface untuk pengenalan wajah. Metode ini
merupakan penggabungan antara metode PCA
dan LDA. Proses reduksi dimensi dilakukan
oleh PCA sebelum melakukan proses LDA. Hal
ini dapat mengatasi singular problem. Tetapi
kelemahan dari metode ini adalah pada saat
proses reduksi dimensi PCA akan
menyebabkan kehilangan beberapa informasi
diskriminan yang berguna dalam proses LDA
[1]. Metode-metode lainnya yang dapat
mengatasi singular problem adalah Direct-
LDA, Null-space based LDA, Pseudo-inverse
LDA, Two-stage LDA, dan Regularized LDA
[2]. Semua teknik LDA tersebut memakai
model representasi data berdasarkan vektor
yang menghasilkan vektor-vektor yang
biasanya memiliki dimensi tinggi. Metode Two
Dimensional Linear Discriminant Analysis
(TDLDA) menilai secara langsung matrik
within-class scatter dari matrik citra tanpa
transformasi citra ke vektor, dan hal itu
mengatasi singular problem dalam matrik
within-class scatter [3]. TDLDA memakai
fisher criterion untuk menemukan proyeksi
diskriminatif yang optimal.
Dalam pengenalan wajah, proses klasifikasi
sama pentingnya dengan proses ekstraksi fitur.
Setelah fitur-fitur penting data atau citra wajah
dihasilkan pada proses ekstraksi fitur, fitur-
fitur tersebut nantinya akan digunakan untuk
proses klasifikasi. Metode klasifikasi yang
digunakan adalah pengklasifikasi Support
Vector Machine (SVM). Pengklasifikasi SVM
menggunakan sebuah fungsi atau hyperplane
untuk memisahkan dua buah kelas pola. SVM
akan berusaha mencari hyperplane yang
optimal dimana dua kelas pola dapat
dipisahkan dengan maksimal.
Penelitian ini mengintegrasikan TDLDA dan
SVM untuk pengenalan wajah. TDLDA sebagai
metode ekstraksi fitur yang dapat mengatasi
singular problem dan SVM sebagai metode
klasifikasi yang mempunyai kemampuan
generalisasi yang tinggi dibanding metode
klasifikasi KNN.
Damayanti dkk, Pengenalan Citra Wajah… 149
Two-Dimensional Linear Discriminant
Analysis (TDLDA)
TDLDA adalah pengembangan dari metode
LDA. Di dalam LDA, matrik 2D terlebih dahulu
ditransformasikan ke dalam bentuk citra vektor
satu dimensi. Sedangkan pada TDLDA atau
disebut teknik proyeksi citra secara langsung,
matrik citra wajah 2D tidak perlu
ditransformasikan ke dalam bentuk citra
vektor. Matrix scatter citra dapat dibentuk
langsung dengan menggunakan matrik citra
aslinya.
A1,….,An adalah n matrik citra, dimana Ai
(i=1,…,k) adalah r x c matrik. Mi (i=1,…,k)
adalah rata-rata citra pelatihan dari kelas ke i,
M adalah rata-rata citra dari semua data
pelatihan dan X adalah matrik masukan.
Menganggap 1l x 2l ruang dimensi
(dimensional space) L⊗ R, dimana ⊗
menunjukkan tensor product, L menjangkau
u1,…,u1l dan R menjangkau v1,..,v 2l .
Sehingga didefinisikan dua matrik L =
[u1,…,u1l ] dan R = [v1,..,v 2l ].
Metode ekstraksi fitur adalah untuk
menemukan L dan R sehingga ruang citra asli
(original image space) Ai diubah ke dalam
ruang citra dimensi rendah (low-dimensional
image) menjadi Bi=LTAiR. Ruang dimensi
rendah (low-dimensional space) diperoleh
dengan transformasi linier L dan R, sedangkan
jarak between-class Db dan jarak within-class
Dw didefinisikan dalam Persamaan (1) dan (2).
Db = RMMLnk
i
i
T
i )(1
−∑=
2
F (1)
Dw = 2
1
)(Fi
k
i x
T RMXLi
−∑∑= Π∈
(2)
Dimana F merupakan Frobenius norm.
Meninjau bahwa 2
FA = Ptrace(AT
A) =
trace(AAT) untuk matrik A. Sedemikian hingga
Persamaan (1) dan (2) dapat direpresentasikan
lebih lanjut sebagai Persamaan (3) dan (4).
))()((1
LMMRRMMLntraceD T
i
Tk
i
i
T
ib −−= ∑=
(3)
))()(( LMXRRMXLtraceDT
i
T
i
k
1i Πx
T
w
i
−−= ∑∑= ∈
(4)
Sama halnya dengan LDA, metode TDLDA
digunakan untuk menemukan matrik L dan R,
sedemikian hingga struktur kelas dari ruang
orisinil tetap di dalam ruang proyeksi.
Sehingga patokan (criterion) dapat
didefinisikan sebagai Persamaan (5).
J1(L,R) = max
W
b
D
D (5)
Hal tersebut jelas bahwa Persamaan (9)
terdiri dari matrik transformasi L dan R. Matrik
transformasi optimal L dan R dapat diperoleh
dengan memaksimalkan Db dan
meminimumkan Dw. Namun, sangatlah sulit
untuk menghitung L dan R yang optimal secara
simultan. Dua fungsi optimasi dapat
didefinisikan untuk memperoleh L dan R.
Untuk sebuah R yang pasti, L dapat diperoleh
dengan menyelesaikan fungsi optimasi pada
Persamaan (6).
J2(L) = maxtrace((LTS
R
W L)-1
(LTS
R
b L)) (6)
dimana
T
i
Tk
i
ii
R
b MMRRMMnS )()(1
−−=∑=
(7)
T
i
T
i
k
i x
R
W MXRRMXSi
)()(1
−−=∑∑= Π∈
(8)
Dengan catatan bahwa ukuran matrik R
WS dan
R
bS adalah r x r yang lebih kecil daripada
ukuran matrik Sw dan Sb pada LDA klasik.
Untuk sebuah L yang pasti, R dapat
diperoleh dengan menyelesaikan fungsi
optimasi pada Persamaan (9).
J3(R) = maxtrace((RTSL
W R)-1(RTSL
b R)) (9)
Dimana
)()(1
MMLLMMnS i
TTk
i
ii
L
b −−=∑=
(10)
)()(1
i
TT
i
k
i x
L
W MXLLMXSi
−−=∑∑= Π∈
(11)
Ukuran matrik SL
w dan SL
b adalah c x c yang
lebih kecil daripada ukuran matrik Sw dan Sb
pada LDA klasik.
Secara khusus, untuk sebuah R yang pasti, L
yang optimal dapat diperoleh dengan
menyelesaikan generalized eigenvalue problem
dari Persamaan (6). Demikian pula, R dapat
diperoleh dengan menyelesaikan generalized
eigenvalue problem dari Persamaan (9) pada L
yang pasti.
150 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 147-156
Gambar 1. Hard Margin Hyperplane.
Support Vector Machine (SVM)
SVM berusaha menemukan hyperplane yang
terbaik pada input space. Prinsip dasar SVM
adalah linear classifier yang selanjutnya
dikembangkan agar dapat bekerja pada
problem non-linear dengan memasukkan
konsep kernel trick pada ruang kerja
berdimensi tinggi [4].
SVM dapat melakukan klasifikasi data yang
terpisah secara linier (linearly separable) dan
non-linier (nonlinear separable) [5]. Linearly
separable data merupakan data yang dapat
dipisahkan secara linier. Misalkan x1,..., xn
adalah dataset dand
ix ℜ∈ , serta yi ∈+1,−1
adalah label kelas dari data xi.. Anggap ada
beberapa hyperplane yang memisahkan sampel
positif dan negatif, maka x yang berada pada
hyperplane akan memenuhi persamaan
0. =+ bxw . Untuk permasalahan data linier,
algoritma support vector hanya mencari
hyperplane dengan margin yang terbesar (jarak
antara dua kelas pola). Hard margin
hyperplane ditunjukkan pada Gambar 1.
Hyperplane terbaik tidak hanya dapat
memisahkan data dengan baik tetapi juga yang
memiliki margin paling besar. Data yang
berada pada bidang pembatas ini disebut
support vector.
Untuk menyelesaikan permasalahan data
non-linier dalam SVM adalah dengan cara
memetakan data ke ruang dimensi lebih tinggi
(ruang fitur atau feature space) [5], dimana
data pada ruang tersebut dapat dipisahkan
secara linier, dengan menggunakan
transformasi Ф pada Persamaan (12).
ΗΦ: daℜ (12)
Dengan demikian algoritma pelatihan
tergantung dari data melalui dot product dalam
H. Sebagai contoh Ф(xi). Ф(xj). Jika terdapat
fungsi kernel K, sedemikian hingga K(xi,xj) =
Ф(xi). Ф(xj), maka algoritma pelatihan hanya
memerlukan fungsi kernel K, tanpa harus
mengetahui transformasi Ф secara pasti.
SVM pertama kali dikembangkan oleh
Vapniks untuk klasifikasi biner, namun
selanjutnya dikembangkan untuk klasifikasi
multiclass (banyak kelas). Pendekatannya
adalah dengan membangun multiclass
classifier, yaitu dengan cara menggabungkan
beberapa SVM biner. Pendekatan ini terdiri
dari metode satu lawan semua (One Against
All) dan metode satu lawan satu (One Against
One) [6].
PERANCANGAN SISTEM
Secara garis besar sistem terdiri dari dua
bagian, yaitu proses pelatihan citra dan proses
pengujian. Gambar 2 merupakan gambaran
garis besar sistem pengenalan wajah. Pada
proses pelatihan terdapat proses TDLDA yang
digunakan untuk mengekstraksi fitur. Fitur-
fitur yang terpilih pada saat proses pelatihan
digunakan dalam proses klasifikasi dan juga
digunakan untuk mendapatkan fitur-fitur yang
terpilih pada data uji coba. Masing-masing
basisdata wajah yang digunakan dibagi
menjadi dua, yaitu satu bagian digunakan untuk
proses pelatihan (training) dan sisanya
digunakan untuk proses pengujian (testing).
Ekstraksi Fitur
Ekstraksi fitur pada proses pelatihan dilakukan
dengan menggunakan metode TDLDA. Tahap
ini bertujuan untuk mendapatkan fitur-fitur
yang terpilih dari masukan data-data pelatihan.
Fitur-fitur yang terpilih nantinya digunakan
untuk proses klasifikasi pelatihan dan
digunakan untuk ekstraksi fitur data pengujian.
Ekstraksi fitur pada proses pengujian
dilakukan dengan cara mengambil hasil
ekstraksi fitur pada proses pelatihan untuk
diterapkan pada data pengujian. Hasil ekstraksi
fitur pada data pengujian ini nantinya
digunakan sebagai masukan pada proses
klasifikasi pengujian.
Support vector
Kelas 2
Kelas 1
xi.w+b = -1
xi.w+b = +1
-b/w
m
Damayanti dkk, Pengenalan Citra Wajah… 151
Proses Pelatihan Proses Pengujian
Gambar 2. Sistem Pengenalan Wajah.
Klasifikasi
Proses klasifikasi pelatihan dilakukan setelah
data-data pelatihan diambil fitur-fitur khusus.
Fitur-fitur khusus ini berupa vektor fitur yang
dimensinya lebih kecil. Penelitian ini
menggunakan SVM metode satu lawan semua
dengan kernel gaussian. Pada proses
klasifikasi, pelatihan variabel hyperplane untuk
setiap pengklasifikasi (classifier) yang didapat
akan disimpan dan nantinya akan digunakan
sebagai data tiap pengklasifikasi dalam proses
pengujian. Dengan kata lain proses klasifikasi
pelatihan adalah untuk mencari support vector
dari data masukan (dalam hal ini digunakan
quadratic programming).
Pada proses klasifikasi pengujian
menggunakan hasil ekstraksi fitur data
pengujian dan hasil proses klasifikasi
pelatihan. Hasil dari proses ini berupa nilai
indeks dari fungsi keputusan yang terbesar
yang menyatakan kelas dari data pengujian.
Jika kelas yang dihasilkan dari proses
klasifikasi pengujian sama dengan kelas data
pengujian, maka pengenalan dinyatakan benar.
Hasil akhirnya berupa citra wajah yang sesuai
dengan nilai indeks dari fungsi keputusan yang
terbesar hasil dari proses klasifikasi pengujian.
Algoritma TDLDA
Berikut ini adalah langkah-langkah dalam
proses TDLDA terhadap suatu basisdata citra
pelatihan:
1. Jika dalam suatu basisdata citra wajah
terdapat himpunan sebanyak n citra
pelatihan Ai = [A1,A2,…,An] (i = 1,2,…,n)
dengan dimensi citra (r x c), maka
himpunan total matrik dari semua citra
tersebut adalah:
An =
rcnrnrn
cnnn
cnnn
AAA
AAA
AAA
)(2)(1)(
2)(22)(21)(
1)(12)(11)(
...
............
...
...
2. Menentukan nilai 1l (dimensi proyeksi
baris) dan 2l (dimensi proyeksi kolom).
Nilai 1l ≤ r dan 2l ≤ c.
Memasukkan basis data pelatihan
Ekstraksi fitur TDLDA
Pengklasifikasi SVM
Memasukkan data
pengujian
Ekstraksi fitur data
pengujian
Pengklasifikasi SVM
Data hyperplane
Hasil identifikasi
152 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 147-156
3. Tahapan berikutnya adalah perhitungan
rata-rata citra pelatihan dari kelas ke-I
dengan menggunakan Persamaan (13).
∑ Π∈=
iXi
i Xn
M1
(13)
4. Menghitung rata-rata semua citra pelatihan
dengan menggunakan Persamaan (14).
∑ ∑= Π∈=
k
i X i
Xn
M1
1 (14)
5. Menetapkan matrik transformasi R ukuran
(c, 2l ) yang diperoleh dari gabungan antara
matrik identitas ukuran ( 2l , 2l ) dengan
matrik nol ukuran (c- 2l , 2l ).
6. Menghitung matrik between class scatter R
sesuai dengan Persamaan (7).
T
i
Tk
i
ii
R
b MMRRMMnS )()(1
−−=∑=
, ukuran
matriknya (r x r).
7. Menghitung matrik within class scatter R
sesuai dengan Persamaan (8).
,)()(1
T
i
T
i
k
i x
R
b MXRRMXSi
−−=∑∑= Π∈
ukuran
matriknya (r x r).
8. Hitung generalized eigenvalue ( iλ ) dari SR
b
dan SR
W menggunakan SVD sesuai dengan
Persamaan (6).
))())( 1
4 LSLLSLmaxtrace((LJ R
b
TR
W
T −= ,
ukuran matriknya (r x r).
9. Ambil sebanyak 1l eigenvector dari
langkah 8 sebagai matrik transformasi baris
],...,[).( 11
LLLL lφφ= , ukuran matriknya
)( 1l×r .
10. Menghitung matrik between class scatter L
sesuai dengan Persamaan (10).
)()(1
MMLLMMnS i
TTk
i
ii
L
b −−=∑=
, ukuran
matriknya (c x c).
11. Menghitung matrik within class scatter L
sesuai dengan Persamaan (11).
),()(1
i
TT
i
k
i x
L
W MXLLMXSi
−−=∑∑= Π∈
ukuran matriknya (c x c).
12. Hitung generalized eigenvalue ( iλ ) dari SL
b
dan SL
W menggunakan SVD sesuai dengan
Persamaan (9).
))()(()( 1
5 RSRRSRmaxtraceRJ L
b
TL
W
T −= ,
ukuran matriknya (c x c).
13. Ambil sebanyak 2l eigenvector dari
langkah 12 sebagai matrik transformasi
kolom (R). R = [R
1φ , ..., R
2lφ ], ukuran
matriknya (c x 2l ).
14. Hitung matrik fitur ekstraksi adalah
RALB i
T
i = , ukuran matriknya ( 1l x 2l ).
15. Keluaran: matrik fitur ektraksi Bi, matrik
transformasi baris L, dan matrik
transformasi kolom R.
Tabel 1. Hasil Uji Coba Menggunakan
TDLDA-KNN.
Prosentase Pengenalan Basisdata
Uji 3 Uji 4 Uji 5
ORL 92,14 % 94,58 % 97,00 %
Yale 91,67 % 97,14 % 98,89 %
Bern 82,65 % 92,26 % 95,71 %
Tabel 2. Hasil Uji Coba Menggunakan
TDLDA-SVM.
Prosentase Pengenalan Basisdata
Uji 3 Uji 4 Uji 5
ORL 92,86 % 96,67 % 97,50 %
Yale 95,00 % 99,05 % 100 %
Bern 84,18 % 94,05 % 97,14 %
Tabel 3. Perbandingan Hasil Uji Coba
dengan Basis Data ORL.
Prosentase Pengenalan Variasi Pengujian TDLDA-
SVM
TDLDA-
KNN
2DPCA* Fisherface**
Uji ORL 3 92,86 % 92,14 % 91,80 % 84,50 %
Uji ORL 4 96,67 % 94,58 % 95,00 % 91,46 %
Uji ORL 5 97,50 % 97,00 % 96,00 % 95,15 %
Ket: *) diperoleh dari sumber [7]
**) diperoleh dari sumber [8].
Damayanti dkk, Pengenalan Citra Wajah… 153
Gambar 3. Blok Diagram Proses Pelatihan dan Klasifikasi Menggunakan SVM.
Rancangan Algoritma SVM
Blok diagram proses pelatihan dan pengujian
SVM dapat ditunjukkan pada Gambar 3.
Pengklasifikasian dengan SVM dibagi menjadi
dua proses, yaitu proses pelatihan dan proses
pengujian. Pada proses pelatihan SVM
menggunakan matrik fitur yang dihasilkan pada
proses ekstraksi fitur sebagai masukan.
Sedangkan pada pengujian SVM memanfaatkan
matrik proyeksi yang dihasilkan pada proses
ekstraksi fitur yang kemudian dikalikan dengan
data uji (sampel pengujian) sebagai masukan.
Pengklasifikasian SVM untuk multiclass
One Against All akan membangun sejumlah k
SVM biner (k adalah jumlah kelas). Fungsi
keputusan yang mempunyai nilai maksimal
menunjukkan bahwa data xd merupakan
angggota dari kelas fungsi keputusan tersebut.
Proses pengujian pada setiap SVM biner
Memetakan input space ke feature space menggunakan kernel Gaussian
K(x,y) = exp ))2(
||(
2
2
σyx −−
Menghitung fungsi keputusan :
iidii bwxxKf += ),(
Dimana : i = 1 sampai k; xi = support vector; xd = data pengujian
Membangun sejumlah k SVM biner (k adalah jumlah kelas)
Menentukan nilai fi yang paling maksimal. Kelas i dengan fi terbesar adalah kelas dari data
pengujian
Memetakan input space ke feature space menggunakan kernel Gaussian
K(x,y) = exp ))2(
||(
2
2
σyx −−
Menentukan sejumlah support vector dengan cara menghitung nilai alpha α1, ..., αN (
N = sejumlah data pelatihan) menggunakan quadratic programming
∑∑==
−=l
ii
jijiji
l
i
i xxyyQ1,1 2
1)(
rrαααα
Subject to: 0),...,2,1(01
==≥ ∑=
i
l
i
ii yli αα
Data ixr
yang berkorelasi dengan αi > 0 inilah yang disebut sebagai support vector
Solusi bidang pemisah didapatkan dengan rumus w =Σαiyixi ; b = yk- wTxk untuk
setiap xk , dengan αk≠ 0.
Proses pelatihan pada setiap SVM biner
154 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 147-156
75,00
80,00
85,00
90,00
95,00
100,00
ORL3 ORL4 ORL5
Jumlah Data Pelatihan Per Kelas
Prosentase Pengenalan
2DLDA+SVM
2DLDA+K-NN
2DPCA
Fisherface
Gambar 4. Grafik Tingkat Keberhasilan Pengenalan untuk Tiap Variasi Pengujian pada Basisdata
ORL Menggunakan Metode TDLDA-SVM dan Metode Lainnya.
Data pelatihan yang sudah diproyeksikan
oleh TDLDA selanjutnya menjadi data
pelatihan SVM. Jika sebaran data yang
dihasilkan pada proses TDLDA mempunyai
distribusi yang tidak linier, maka salah satu
metode yang digunakan SVM untuk
mengklasifikasikan data tersebut adalah dengan
mentransformasikan data ke dalam dimensi
ruang fitur (feature space), sehingga dapat
dipisahkan secara linier pada feature space.
Feature space biasanya memiliki dimensi yang
lebih tinggi dari vektor masukan (input space).
Hal ini mengakibatkan komputasi pada feature
space mungkin sangat besar, karena ada
kemungkinan feature space dapat memiliki
jumlah feature yang tidak terhingga.
Metode SVM menggunakan ”kernel trick”.
Fungsi kernel yang digunakan pada penelitian
ini adalah Gaussian (Persamaan (15)).
))2(
||(),(
2
2
σyx
expyxK−−
= (15)
Sejumlah support vector pada setiap data
pelatihan harus dicari untuk mendapatkan
solusi bidang pemisah terbaik. Persoalan solusi
bidang pemisah terbaik dapat dirumuskan
dalam Persamaan (16).
∑∑==
−=l
ii
jijiji
l
i
i xxyyQ1,1 2
1)(
rrαααα (16)
dimana: 0),...,2,1(01
==≥ ∑=
i
l
i
ii yli αα
Data ixr
yang berkorelasi dengan αi > 0
inilah yang disebut sebagai support vector.
Dengan demikian, dapat diperoleh nilai yang
nantinya digunakan untuk menemukan w.
Solusi bidang pemisah didapatkan dengan
rumus iii xyaw ∑= ; k
T
k xwyb −= untuk
setiap kx , dengan αk≠ 0.
Proses pengujian atau klasifikasi dilakukan
juga pada setiap SVM biner menggunakan nilai
w, b, dan xi yang dihasilkan pada proses
pelatihan di setiap SVM biner. Fungsi yang
dihasilkan untuk proses pengujian
didefinisikan dalam Persamaan (17).
iidii bwxxKf += ),( (17)
Dimana:
i = 1 sampai k
xi = support vector
xd = data pengujian.
Keluarannya adalah berupa indeks i dengan fi
terbesar yang merupakan kelas dari data
pengujian.
HASIL DAN PEMBAHASAN
Uji coba terhadap sistem pengenalan wajah
pada penelitian ini dilakukan pada tiga jenis
basisdata wajah baku, yaitu Olivetti Research
Laboratorium atau Basis Data ORL, dan The
Yale Face Database atau Basisdata Yale, dan
The University of Bern atau Basisdata Bern.
Untuk masing-masing basisdata wajah,
pelatihan menggunakan tiga wajah (uji 3),
empat wajah (uji 4), lima wajah (uji 5). Sisa
Damayanti dkk, Pengenalan Citra Wajah… 155
wajah yang tidak di-training digunakan sebagai
data pengenalan.
Metode yang digunakan dalam pengujian ini
ada dua kelompok. Kelompok pertama
menggunakan metode TDLDA untuk ekstraksi
fitur dan metode SVM untuk klasifikasi.
Kelompok yang kedua menggunakan metode
TDLDA sebagai ekstraksi fitur dan metode K-
Nearest Neighbor (KNN) menggunakan
Euclidean Distance sebagai klasifikasi. Tabel 1
dan Tabel 2 menunjukkan bahwa prosentase
pengenalan TDLDA-SVM lebih tinggi
dibandingkan dengan TDLDA-KNN.
Untuk melihat kelebihan algoritma TDLDA-
SVM, dibuat perbandingan dengan beberapa
metode lain. Perbandingan hasil uji coba antara
metode TDLDA-SVM dengan TDLDA-KNN,
2DPCA, dan Fisherface menggunakan
basisdata ORL dapat dilihat pada Tabel 3.
Tabel 3 menunjukkan bahwa prosentase
pengenalan TDLDA-SVM lebih tinggi
dibanding dengan metode lainnya (TDLDA-
KNN, 2DPCA, Fisherface).
Untuk mempermudah melihat perbedaan
hasil uji coba antara metode TDLDA-SVM
dengan metode lainnya digunakan diagram
batang. Gambar 4 menunjukkan hasil uji coba
terhadap basisdata ORL untuk metode TDLDA-
SVM dengan metode lainnya.
Berikut adalah keunggulan metode TDLDA-
SVM dibanding metode lainnya:
1. TDLDA-SVM dibanding dengan TDLDA-
KNN.
KNN tidak memperhatikan distribusi dari
data hanya berdasarkan jarak data baru itu
ke beberapa data/tetangga terdekat. Boleh
jadi, merupakan data/tetangga terdekat
bukan kelompoknya, sehingga klasifikasi
yang dihasilkan salah.
SVM memperhatikan distribusi data
sehingga berusaha untuk menemukan fungsi
pemisah (classifier) yang optimal yang
dapat memisahkan dua set data dari dua
kelas yang berbeda. Setiap kelas memiliki
pola yang berbeda dan dipisahkan oleh
fungsi pemisah. Sehingga, jika ada data
baru yang akan diklasifikasikan maka akan
diketahui kelas yang sesuai dengan data
baru tersebut. Dengan demikian klasifikasi
yang dihasilkan lebih sempurna dibanding
dengan metode klasifikasi lainnya.
2. TDLDA-SVM dibandingkan dengan 2DPCA.
2DPCA lebih fokus pada pengoptimalan
representasi data daripada pengoptimalan
diskriminan data, sehingga data-data tidak
terpisah dengan sempurna.
TDLDA mengoptimalkan diskriminan data
dengan lebih baik jika dibandingkan dengan
2DPCA. Sehingga TDLDA dapat
mengelompokkan vektor data dari kelas
yang sama dan memisahkan kelas yang
berbeda.
3. TDLDA-SVM dibandingkan dengan
Fisherface.
Pada Fisherface prosedur pre-processing
untuk mereduksi dimensi menggunakan
PCA dapat menyebabkan kehilangan
beberapa informasi diskriminan yang
penting untuk algoritma LDA yang
diterapkan setelah PCA.
TDLDA mengambil keuntungan penuh dari
informasi yang diskriminatif dari ruang
lingkup wajah (face space), dan tidak
membuang beberapa subruang (subspace)
yang mungkin berguna untuk pengenalan.
SIMPULAN
Dari uji coba yang sudah dilakukan dapat
diambil simpulan sebagai berikut:
1. Metode TDLDA-SVM mampu menunjukkan
akurasi pengenalan yang optimal
dibandingkan dengan metode lainnya
(TDLDA-KNN, 2DPCA, Fisherface). Hal ini
dikarenakan TDLDA mampu mengatasi
singular problem, mempertahankan
keberadaan informasi diskriminatif, serta
memaksimalkan jarak antar kelas dan
meminimalkan jarak inter kelas. Sedangkan
SVM mempunyai kemampuan menemukan
fungsi pemisah (classfier) yang optimal.
2. Terdapat tiga variabel penting yang
mempengaruhi tingkat keberhasilan
pengenalan, yaitu variasi urutan dari sampel
pelatihan per kelas yang digunakan, jumlah
sampel pelatihan per kelas yang digunakan,
dan jumlah dimensi proyeksi.
3. Dari hasil uji coba menggunakan metode
TDLDA-SVM dengan memvariasi urutan
data pelatihan didapatkan tingkat akurasi
pengenalan antara 84,18% sampai 100%
untuk basisdata ORL, YALE, dan BERN.
156 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 147-156
DAFTAR PUSTAKA
[1] Belhumeur PN, Hespanha JP and
Kriegman DJ. Eigenfaces vs Fisherfaces
Recognition Using Class Specific Linear
Projection. IEEE Transactions on Pattern
Analysis and Machine Intelligence. 19:
711-720. 1997.
[2] Kong H, Wang L, Teoh EK, Wang JG,
and Venkateswarlu R. A framework of 2D
Fisher Discriminant Analysis: Application
to Face Recognition with Small Number
of Training Samples. IEEE Conf. CVPR.
2005.
[3] Quan XG, Lei Z and David Z. Face
Recognition Using FLDA With Single
Training Image Per Person. Applied
Mathematics and Computation. 205: 726-
734. 2008.
[4] Nugroho AS, Witarto BA dan Handoko D.
Support Vector Machine - Teori dan
Aplikasinya Dalam Bioinformatika.
Kuliah Umum Ilmu Komputer.com. 2003.
URL: http://www.ilmukomputer.com/
anto-SVM.pdf, diakses tanggal 16 Maret
2008.
[5] Burges JC. A Toturial on Support Vector
Machines for Pattern Recognition. Data
Mining and Knowledge Discovery. 2: 955-
974. 1998.
[6] Hsu CW and Lin CJ. A Comparison of
Methods for Multi-class Support Vector
Machines. IEEE Transactions on Neural
network. 13: 415-425. 2002.
[7] Yang J, Zhang D, Frangi AF, and Yang
JY. Two-dimensional PCA: A New
Approach to Appearance-based Face
Representation and Recognition. IEEE
Transactions on Pattern Analysis and
Machine Intelligence. 26: 131-137. 2004.
[8] Liang Z, Li Y, and Shi P. A Note on Two-
Dimensional Linear Discriminant
Analysis. Pattern Recogn. 29: 2122-2128.
2008.
Vol. 5, No. 3, Januari 2010 ISSN 0216 - 0544
157
ESTIMASI BENTUK STRUCTURING ELEMENT
BERDASAR REPRESENTASI OBYEK
*Sri Huning Anwariningsih, **Agus Zainal Arifin, ***Anny Yuniarti Program Magister Teknik Informatika, ITS
Jl. Raya ITS, Kampus ITS, Sukolilo, Surabaya, 60111
E-Mail: *[email protected], **[email protected], ***[email protected]
Abstrak
Pemrosesan citra secara morfologi dilakukan dengan cara menerapkan sebuah
structuring element (strel) terhadap sebuah citra dengan cara yang hampir sama
dengan konvolusi. Structuring element memegang peranan penting dalam pengolahan
citra dengan morfologi. Pemilihan bentuk dan ukuran structuring element sangat
berpengaruh terhadap hasil pengolahan citra. Sebuah structuring element yang sesuai
digunakan pada sebuah obyek, belum tentu sesuai digunakan pada obyek lain.
Umumnya pemilihan structuring element hanya didasarkan pada kemiripan bentuk
dengan obyek yang diteliti yang ditentukan secara manual. Pada penelitian ini
diusulkan suatu metode estimasi bentuk structuring element berdasar pada
representasi bentuk obyek yang diteliti. Representasi bentuk yang digunakan berbasis
shape matrix. Representasi obyek ini akan membantu menentukan bentuk structuring
element pada obyek yang diteliti karena bentuk structuring element yang digunakan
akan sesuai dengan representasi obyek yang diteliti. Untuk menguji kinerjanya,
bentuk structuring element yang didapatkan diujicobakan untuk deteksi tepi dengan
menggunakan operasi morfologi gradien. Hasil uji coba pada 30 sampel data citra
sintetis menunjukkan bahwa algoritma deteksi tepi menggunakan metode shape
descriptor berbasis shape matrix ini terbukti dapat diandalkan dengan akurasi rata-
rata sebesar 99,6 %.
Kata kunci: deteksi tepi, morfologi gradien, representasi bentuk, structuring element,
shape matrix.
Abstract
Basic concept of morphology is conducted by passing a structuring element (strel) to
an image. In morphology, structuring element plays an important role in image
processing. The selection the shape and size of structuring element can influence the
result of image processing. An appropriate structuring element which is used at an
object is not always appropriate to be used at other objects. Generally, the selection
of structuring element only relies on similarity with shape of observed object that is
determined manually. This paper proposes a method to estimate the shape of
structuring element based on the representation of observed object. Every
representation can describe the internal dan exsternal characteristic of object. So this
object representation will help to determine the shape of structuring element at
observed object because the shape of structuring element used is appropriate to the
representation of the obseved object. Therefore, to measure its performance, the
shape of structuring element can be tried out in detecting the side by using the
gradient morphology operation. Testing for this method uses 30 samples of synthetic
image shows that detection of algorithm using method of shape descriptor based on
shape matrix is reliable with the average accuration 99.6% .
Key words: edge detection, morphological gradient, structuring element, shape
matrix, shape representation.
158 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 157-165
PENDAHULUAN
Operasi morfologi banyak digunakan dalam
pengolahan dan analisis citra, misalkan untuk
operasi perbaikan citra (image enhancement)
ekstrasi fitur, deteksi tepi, analisis bentuk, dan
beberapa implementasi operasi pengolahan
citra lain. Dalam operasi morfologi, pemilihan
structuring element (strel) sangat
mempengaruhi hasil pemrosesan citra.
Penggunaan dua buah structuring element yang
berbeda akan menghasilkan hasil yang berbeda
meski obyek/citra yang dianalisa adalah sama
[1].
Ada beberapa bentuk structuring element
yang biasa digunakan, yaitu rectangle, square,
disk, linear, dan diamond. Setiap bentuk
structuring element tersebut memiliki
kelebihan dan kekurangan masing-masing.
Structuring element berbentuk rectangle dan
square dapat digunakan untuk mendeteksi tepi
bagian atas, bawah, pinggir kiri, dan kanan dari
sebuah obyek. Sedangkan structuring element
berbentuk disk dapat digunakan untuk
melakukan operasi dilasi/rotasi yang tidak
berhubungan dengan arah. Hal ini dikarenakan
structuring element berbentuk disk simetris
terhadap obyek aslinya. Structuring element
berbentuk line/linear hanya dapat mendeteksi
single border [2].
Bentuk structuring element yang sesuai
untuk satu obyek belum tentu sesuai untuk
obyek lain. Deteksi sel tumor gastric lebih
tepat menggunakan structuring element
berbentuk rectangle dibanding menggunakan
structuring element berbentuk diamond atau
linear [2]. Sedangkan deteksi adanya retakan
kecil (microcrack) pada batu dolomit lebih
cocok menggunakan structuring element
berbentuk linear karena microcrack pada batu
dolomit berbentuk garis-garis [3].
Belum ada pedoman baku dalam pemilihan
bentuk structuring element. Umumnya
pemilihan bentuk structuring element hanya
didasarkan pada kemiripan dengan bentuk
obyek yang diteliti [2]. Salah satu atribut yang
penting untuk mengenali sebuah obyek adalah
shape (bentuk) karena ia merupakan
representasi dari sebuah obyek [4]. Shape
adalah salah satu atribut yang penting untuk
mengenali sebuah obyek. Pemilihan bentuk
stucturing element lebih didasarkan pada
kemiripan dengan bentuk obyek. Oleh karena
itu bentuk obyek dapat digunakan sebagai
penentuan bentuk stucturing element.
Shape descriptor adalah teknik untuk
merepresentasikan bentuk obyek. Sebuah
representasi yang baik akan dapat
menggambarkan karakteristik intrinsik dari
sebuah shape secara eksplisit. Representasi
sebuah shape juga harus invarian terhadap
rotasi, scaling dan transformasi [4]. Salah satu
teknik shape descriptor adalah shape matrix.
Shape matrix menggunakan informasi global
dari sebuah shape, kemudian mengubahnya
menjadi sebuah matrik yang mendeskripsikan
sebuah shape. Beberapa penelitian
mengemukakan bahwa shape matrix dapat
menggambarkan bentuk obyek serta invarian
terhadap scaling, rotasi, dan translasi [5,6].
Representasi bentuk obyek ini dapat digunakan
untuk mendeteksi bentuk structuring element
yang mendekati bentuk obyek yang diteliti.
Oleh karena itu, penelitian ini mengusulkan
metode baru untuk estimasi bentuk structuring
element yang dapat digunakan mendeteksi
sebuah obyek. Estimasi ini dilakukan dengan
menganalisa representasi shape sebuah obyek.
Representasi shape yang digunakan pada
penelitian ini adalah berbasis shape matrix.
Shape matrix memiliki keunggulan yaitu telah
teruji invarian terhadap translasi, rotasi, dan
scaling [7]. Selain itu shape matrix dapat
merepresentasikan region yang memiliki hole.
Shape matrix memiliki karakteristik yang mirip
dengan karakteristik structuring element.
Dengan melakukan proses resizing terhadap
bentuk dari shape matrix diharapkan dapat
menentukan bentuk structuring element yang
mirip dengan obyek yang sedang diteliti.
MORFOLOGI
Matematika morfologi merepresentasikan citra
obyek dua dimensi sebagai suatu himpunan
matematika dalam ruang Euclidean E2, dimana
ia dapat berupa ruang kontinyu R2 atau ruang
diskrit Z2. Dahulu, sebuah citra dipandang
sebagai suatu fungsi intensitas terhadap posisi
(x,y), sedangkan dengan pendekatan morfologi,
suatu citra dipandang sebagai himpunan.
Sebuah obyek citra A dapat direpresentasikan
dalam bentuk himpunan dari posisi-posisi (x,y)
yang bernilai 1 atau 0, dimana nilai-nilai
Anwariningsih dkk, Estimasi Bentuk Structuring Element… 159
tersebut menunjukkan tingkat gray scale setiap
posisi. Nilai 1 untuk gray level warna putih dan
nilai 0 untuk gray level warna hitam.
Gambar 1. Contoh Structuring Element.
(a) Titik “O” adalah Titik Poros
dan (b) Representasi Biner Strel.
Gambar 2. Citra Hasil Deteksi Tepi
Menggunakan Morfologi Gradien.
Gambar 3. Taksonomi Representasi Shape
[6].
Prinsip dasar dari matematika morfologi
adalah penggunaan structuring element yaitu
bentuk dasar dari suatu obyek yang digunakan
untuk menganalisis struktur geometri dari
obyek lain yang lebih besar dan kompleks [8].
Tujuannya adalah untuk memperoleh informasi
mengenai bentuk dari suatu citra dengan
mengatur bentuk dan ukuran suatu structuring
element.
Structuring Element
Structuring element dapat diibaratkan dengan
mask pada pemrosesan citra biasa (bukan
secara morfologi). Structuring element juga
memiliki titik poros (disebut juga titik origin/
titik asal/titik acuan). Gambar 1 menunjukkan
contoh structuring element dengan titik poros
di (0,0) yang ditunjukkan dengan huruf “O”.
Bentuk structuring element pada Gambar
1(a) dapat direpresentasikan dalam bentuk
matrik biner seperti pada Gambar 1(b), dimana
angka “1” dan angka “0” menunjukkan nilai
gray level.
Dalam morfologi, yang menjadi kunci
penting adalah pemilihan structuring element.
Structuring element memiliki dua komponen
penting yaitu bentuk dan ukuran, yang
mempengaruhi hasil pengujian. Pemilihan
bentuk structuring element juga mempengaruhi
citra hasil operasi morfologi.
Operasi-operasi Morfologi
Dalam morfologi ada beberapa operasi yang
dapat dilakukan, yaitu:
1. Translasi
Translasi artinya sebuah citra yang digeser
pada arah (x,y), dimana (x,y) adalah
koordinat matrik. Operasi translasi
dinyatakan sebagai Persamaan (1).
)(:)()( Aba,yx,ba,wA ∈+= (1)
2. Dilasi
Operasi dilasi dilakukan untuk
memperbesar ukuran segmen obyek dengan
menambah lapisan di sekeliling obyek.
Operasi ini menyebabkan citra hasil dilasi
cenderung menebal [9].
Dilasi A oleh B dinotasikan dengan
BA⊕ dan didefinisikan sebagai Persamaan
(2).
IBx
xABA∈
=⊕ (2)
(a) (b)
=
010
111
010
B
160 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 157-165
3. Erosi
Operasi erosi adalah kebalikan dari operasi
dilasi. Pada operasi ini, ukuran obyek
diperkecil dengan mengikis sekeliling obyek
sehingga citra hasil cenderung diperkecil
menipis [9]. Erosi A oleh B dinotasikan
BAΘ didefinisikan sebagai Persamaan (3).
: ABwBA w ⊆=Θ (3)
IBb
bABA∈
=Θ (4)
4. Opening
Proses opening pada sebuah citra A oleh
strel B dinotasikan dengan BA o dan
didefinisikan sebagai proses erosi. Proses
ini dilanjutkan dengan proses dilasi dimana
kedua proses tersebut dilakukan secara
berulang untuk semua titik (x,y), seperti
yang ditunjukkan oleh Persamaan (5).
BBABAA opening ⊕Θ== )()( o (5)
Persamaan (5) dapat dituliskan ke dalam
bentuk Persamaan (6).
Uo ):( AxBxBBA ⊂++= (6)
Operasi opening digunakan untuk memutus
bagian-bagian dari obyek yang hanya
terhubung dengan satu atau dua buah titik
saja, dan menghilangkan obyek yang sangat
kecil. Operasi opening bersifat
memperhalus kenampakan citra,
menyambung fitur yang terputus (break
narrow joins), dan menghilangkan efek
pelebaran pada obyek (remove protrusions).
5. Closing
Operasi closing adalah kombinasi antara
operasi dilasi dan erosi yang dilakukan
secara berurutan. Citra asli didilasi terlebih
dahulu dan kemudian hasilnya dierosi.
Proses closing pada sebuah citra A oleh
strel B dinotasikan dengan BA • dan
didefinisikan sebagai Persamaan (7).
BBABA Θ⊕=• )( (7)
Beberapa kegunaan operasi closing
adalah menutup atau menghilangkan
lubang-lubang kecil yang ada dalam segmen
obyek; menggabungkan dua segmen obyek
yang saling berdekatan (menutup sela antara
dua obyek yang sangat berdekatan); dan
juga dilakukan dalam beberapa rangkaian
dilasi-erosi (misalnya tiga kali dilasi, lalu
tiga kali erosi) apabila ukuran lubang atau
jarak antar obyek cukup besar.
Operasi closing juga cenderung akan
memperhalus obyek pada citra, yaitu
dengan cara menyambung pecahan-pecahan
(fuses narrow breaks and thin gulf) dan
menghilangkan lubang-lubang kecil pada
obyek.
6. Morphological Gradient
Operasi dilasi dan erosi seringkali
dikombinasikan untuk memaksimalkan
operasi morfologi pada image processing.
Soille menyatakan bahwa terdapat tiga jenis
morphological gradient [10], yaitu:
a Basic morphological gradient dimana
dilated_image – eroded_image
b Internal gradient dimana original_image
– eroded_image
c External gradient dimana dilated_image
– original_image.
Dilated_image adalah citra hasil dilasi,
sedangkan eroded_image adalah citra hasil
erosi.
Persamaan untuk Morphological gradient
didefinisikan dalam Persamaan (8), Internal
gradient dalam Persamaan (9), dan External
gradient dalam Persamaan (10).
)()( BABAMG Θ−⊕= (8)
)( BAAIG Θ−= (9)
ABAEG −⊕= )( (10)
Internal gradient akan mempertajam
internal boundary dari obyek sehingga
obyek akan lebih terang dibandingkan
dengan backgroundnya. Sedangkan pada
eksternal gradient, boundary obyek akan
lebih gelap dibanding dengan background-
nya (Gambar 2). Pada citra biner, internal
gradient akan menjadi mask dari internal
boundary dari obyek [10].
Morfologi gradien dapat disebut citra
tepi, karena dengan mengurangkan operasi
hasil penebalan dan penipisan maka akan
diperoleh citra yang menonjolkan tepi
obyek, karena daerah non-tepi obyek sudah
hilang karena pengurangan tersebut.
REPRESENTASI OBYEK
Pengenalan bentuk menjadi faktor yang penting
dalam pengenalan suatu obyek.
Anwariningsih dkk, Estimasi Bentuk Structuring Element… 161
Gambar 4. Taksonomi Teknik Representasi Shape Menggunakan Region-Based [6].
Gambar 5. (a) Contoh Shape dan (b) Shape Matrix [7].
Gambar 6. (a) Contoh Shape dengan Hole, (b) Shape Matrix [5].
Gambar 7. Rancangan Sistem untuk Pengujian Estimasi Bentuk Structuring Element Berbasis
Shape Matrix.
A
mulai Menentukan Citra Uji dan
citra ground truth
Menetukan shape
matrix dari citra uji
Melakukan operasi morfologi
gradient untuk deteksi tepi
Menghitung Kinerja Algoritma selesai
162 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 157-165
Bentuk 1 Bentuk 2 Bentuk 3 Bentuk 4 Bentuk 5
entuk 6 Bentuk 7 Bentuk 8 Bentuk 9 Bentuk 10
Bintang Kotak Flag Bunga Kotaktumpul
Layang Lingkaran 1 Lingkaran 2 Oval Persegi
PMI Segienam Segitiga 1 Segitiga 2 Kepala
Trapesium Trapesium 2 Tanjakan Segilima Daun
Gambar 8. Citra Uji (Berupa Citra Buatan) dengan Ukuran 140 x 140 piksel.
Representasi Shape
Sebuah representasi yang baik akan dapat
menggambarkan karakteristik intrinsik dari
sebuah shape secara eksplisit. Sebuah
representasi shape yang bagus harus dapat
menggambarkan sebuah obyek secara akurat
sehingga akan memudahkan menemukan
bentuk asli sebuah obyek setelah obyek
tersebut telah di-rekonstruksi. Pada dasarnya
bentuk sebuah obyek dapat direpresentasikan
dalam bentuk karakteristik internal dan
eksternal.
Pendekatan shape secara struktural
merupakan salah cara representasi shape yang
umum digunakan pada metode representasi
shape pada morfologi [5,11]. Shape
didefinisikan sebagai sekumpulan titik yang
saling terhubung [6]. Jadi sebuah obyek
dikatakan mempunyai bentuk jika semua titik
pada obyek tersebut terhubung.
Secara taksonomi, ada beberapa teknik
dalam representasi shape yaitu dalam bentuk
contours, region, dan transforms. Contour-
based sama dengan boundary-based yaitu
merepresentasikan shape berdasar boundary-
nya. Region-based berdasar area dari suatu
obyek, sedangkan teknik transform
merepresentasikan shape dalam bentuk
koefisien transform. Teknik ini biasanya
menggunakan transformasi fourier maupun
wavelet (Gambar 3). Teknik region-based
dibagi menjadi beberapa metode (Gambar 4).
Anwariningsih dkk, Estimasi Bentuk Structuring Element… 163
Tabel 1. Nilai Akurasi Deteksi Tepi.
Nama Obyek Akurasi (%) No Ukuran
140 x 140 SM Square Diamond Disk
1 Bentuk 1 99,99 99,99 98,33 98,33
2 Bentuk 2 97,98 97,97 98,00 98,00
3 Bentuk 3 98,28 98,28 98,20 98,20
4 Bentuk 4 99,61 99,61 98,51 98,51
5 Bentuk 5 99,97 99,98 99,31 99,31
6 Bentuk 6 99,76 99,76 99,34 99,34
7 Bentuk 7 99,98 99,98 99,15 99,15
8 Bentuk 8 99,97 99,97 98,88 98,88
9 Bentuk 9 99,97 99,97 98,57 98,57
10 Bentuk 10 99,99 99,99 99,41 99,41
11 Bintang 99,99 99,98 98,51 98,51
12 Kotak 100,00 100,00 99,98 99,98
13 Flag 99,92 99,92 99,62 99,62
14 Bunga 98,29 98,26 98,28 98,28
15 Kotak
tumpul
100,00 100,00 99,82 99,82
16 Layang 99,27 99,27 97,76 97,76
17 Lingkaran 1 99,99 99,99 99,00 99,00
18 Lingkaran 2 99,97 99,97 98,83 98,83
19 Oval 99,99 99,99 99,37 99,37
20 Persegi 100,00 100,00 99,98 99,98
21 PMI 100,00 100,00 99,94 99,94
22 Segienam 99,99 99,99 99,28 99,28
23 Segitiga 1 100,00 100,00 99,05 99,05
24 Segitiga 2 99,91 99,91 98,73 98,73
25 Kepala 95,40 95,39 95,40 95,40
26 Trapesium 100,00 100,00 99,42 99,42
27 Tanjakan 99,69 99,69 99,39 99,39
28 Segilima 100,00 100,00 99,22 99,22
29 Trapesium 2 100,00 100,00 99,30 99,30
30 Daun 99,99 99,99 99,27 99,27
Representasi Shape Matrix
Shape Matrix dapat digunakan untuk
merepresentasikan sebuah shape. Shape matrix
adalah kuantisasi polar dari sebuah bentuk
(Gambar 5a) yang dianalogikan sama dengan
sistem koordinat. Titik tengah koordinat (0,0)
merupakan titik tengah dari shape obyek dan
sumbu axis x merupakan sumbu yang ditarik
dari titik tengah menuju titik terjauh dari
shape. Jika shape diubah ke dalam bentuk
koordinat polar (r, θ) maka shape tidak akan
dipengaruhi oleh posisi dan sudut rotasinya [7].
Shape matrix juga tidak dipengaruhi oleh skala
dari shape obyek tersebut. Shape matrix
invariant terhadap translasi, rotasi, dan scaling
dari shape tersebut [7].
Pada konsep shape matrix, sebuah shape
akan diubah menjadi bentuk matrik dengan
melakukan kuantisasi polar pada shape tersebut
(Gambar 5b). Asumsikan titik O adalah titik
tengah dari shape dan garis OA dengan panjang
L adalah radius terjauh shape dihitung dari titik
tengah O. Untuk mendapatkan shape matrix
m x n, garis OA dibagi menjadi )1( −n bagian
dengan jarak yang sama. Kemudian dibuat
lingkaran dengan titik pusat O dengan nilai
radius lingkaran masing-masing adalah
)1/()1(...,),1/(2),1/( −−−− nLnnLnL . Maka
akan didapatkan titik potong antara masing-
masing lingkaran dengan garis OA pada
121 ,...,, −niii . Misalkan didapatkan titik
potong (1), (2), (3), dan (4), maka dari setiap
titik potong tersebut, dengan arah berlawanan
jarum jam setiap lingkaran, dibagi menjadi
m busur yang sama dengan sudut
md /360=θ derajat.
Untuk menentukan nilai-nilai elemen pada
shape matrix dijelaskan pada algoritma berikut:
1. Bentuk sebuah matrik M berukuran nxm .
2. For i = 0 to (n – 1)
For j = 0 to (m – 1)
If titik dengan koordinat polar
( ))/360(),1/( mjniL − berada di
dalam shape, then 1:),( =jiM
otherwise 0:),( =jiM
Selain memuat informasi tentang region,
shape matrix juga memuat informasi tentang
boundary sehingga shape matrix juga dapat
merepresentasikan sebuah region obyek yang
memiliki hole (Gambar 6).
Pada shape matrix, sebuah obyek akan
direpresentasikan dalam sebuah bentuk matrik
ukuran m x n. Karakteristik shape matrix mirip
dengan karakteristik structuring element.
Keduanya sama berbentuk matrik m x n dengan
nilai elemen “1” atau “0”, dimana nilai-nilai
tersebut menunjukkan posisi piksel dalam
sebuah obyek. Bentuk shape matrix akan
berubah-ubah menyesuaikan bentuk obyek
yang diteliti. Hal ini menunjukkan bahwa ada
kemiripan antara representasi obyek dengan
164 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 157-165
obyek yang diteliti. Fakta ini sesuai dengan
alasan pemilihan bentuk structuring element.
Pemilihan bentuk structuring element berdasar
kemiripan dengan obyek yang diteliti.
Representasi obyek berbasis shape matrix
dengan berbagai keunggulannya dapat
digunakan untuk menentukan bentuk
structuring element.
HASIL DAN PEMBAHASAN
Rancangan pengujian secara umum untuk
estimasi bentuk structuring element berbasis
shape matrix dari penelitian dapat dilihat pada
Gambar 7. Langkah-langkah yang dilakukan
adalah:
1. Menentukan citra uji dan citra ground truth.
2. Menentukan shape matrix dari citra uji dan
melakukan proses resizing pada shape
matrix untuk dapat menentukan bentuk
structuring element.
3. Melakukan operasi morfologi gradien pada
citra uji dengan structuring element hasil
langkah (2).
4. Menghitung akurasi citra hasil operasi
morfologi gradien berbasis shape matrix
dengan citra ground.
Gambar 9. Citra Hasil Deteksi Tepi, (a) Ground
Truth, (b) Shape Matrix.
Tabel 2. Perbandingan Rata-rata Akurasi Uji
Coba Normal.
No Structuring Element Rata-rata Akurasi (%)
1 shape matrix 99,6
2 square 99,5
3 diamond 98,9
4 disk 98,9
Pada penelitian ini digunakan 30 citra uji
sebagai bahan uji coba. Citra uji ini berupa
citra buatan (sintetis). Ukuran citra uji normal
adalah 140 x 140 piksel. Tipe citra adalah citra
hitam putih (citra BW), dengan warna putih
menunjukkan obyek dan warna hitam
menunjukkan warna latar belakang. Gambar 8
menunjukkan semua citra uji yang digunakan.
Citra uji normal dibuat menggunakan
aplikasi Paint. Citra uji terdiri dari berbagai
bentuk baik bentuk yang beraturan maupun
bentuk yang tidak beraturan. Hal ini bertujuan
untuk menguji apakah bentuk structuring
element yang diusulkan dalam penelitian ini
dapat digunakan untuk mendeteksi tepi
sembarang bentuk bangun.
Uji coba pada penentuan bentuk structuring
element berbasis algoritma shape matrix yang
dikembangkan pada penelitian ini dilakukan
pada semua kelompok sampel data citra uji.
Pada masing-masing citra uji, secara garis
besar akan dilakukan tiga tahap pengujian.
Langkah pertama adalah mencari ukuran shape
matrix dari obyek pada citra uji. Penentuan
ukuran shape matrix yang digunakan dalam
pengujan berdasarkan ukuran minimal shape
matrix yang sudah mampu mendeteksi obyek.
Langkah kedua adalah melakukan pengujian
proses deteksi tepi untuk mencari boundary
dari obyek citra asli. Langkah terakhir adalah
melakukan evaluasi tingkat keberhasilan
algoritma dengan menghitung akurasi sistem
dalam melakukan deteksi tepi. Akurasi ini akan
dibandingkan dengan algoritma yang
menggunakan structuring element yang
berbentuk disk, diamond, dan square.
Setelah dilakukan pengujian terhadap 30
citra uji dengan ukuran structuring element
3x3, didapatkan hasil perbandingan tingkat
akurasi deteksi tepi menggunakan bentuk
structuring element berbasis shape matrix
dengan structuring element berbentuk square,
diamond, dan disk (Tabel 1).
Secara keseluruhan nilai akurasi rata-rata
menggunakan structuring element berbasis
shape matrix ukuran 3x3 adalah 99,6%, square
99,5%, sedangkan diamond dan disk memiliki
akurasi yang sama yaitu sebesar 98,9%.
Selanjutnya, nilai akurasi yang memiliki rata-
rata tertinggi dibanding dengan structuring
element pembanding (Tabel 2).
(a) (b)
Anwariningsih dkk, Estimasi Bentuk Structuring Element… 165
Secara visual, citra hasil deteksi tepi
menggunakan bentuk structuring element
berbasis representasi obyek juga berhasil
mendeteksi tepi obyek pada citra uji (Gambar
9). Pada penelitian ini, salah satu faktor yang
mempengaruhi akurasi hasil adalah bentuk dari
obyek dan citra ground truth. Dari penelitian
didapatkan fakta bahwa metode shape
descriptor berbasis shape matrix dapat
diandalkan untuk estimasi bentuk structuring
element. Kelebihan dari metode ini adalah
bentuk structuring element menyesuaikan
dengan obyek yang diteliti, sehingga bentuk
structuring element yang didapatkan benar-
benar merupakan representasi bentuk obyek
yang diteliti. Akan tetapi pemilihan ukuran
shape matrix m x n sangat mempengaruhi hasil
representasi bentuk obyek. Oleh karena itu
diperlukan penelitian lebih lanjut untuk
membahas tentang metode pemilihan ukuran
shape matrix yang tepat.
SIMPULAN
Beberapa simpulan yang dapat diambil
berdasarkan uji coba yang telah dilakukan:
1. Representasi obyek berbasis shape matrix
dengan berbagai keunggulannya dapat
digunakan untuk menentukan bentuk
structuring element.
2. Uji coba yang dilakukan pada 30 citra uji
untuk mendeteksi tepi menggunakan
structuring element berbasis shape matrix,
menghasilkan akurasi rata-rata sebesar
99,6%. Hal ini menunjukkan bahwa metode
ini dapat diandalkan.
DAFTAR PUSTAKA
[1] Cun Jin X, Fen Zhen S, and Jun-qi Z. An
Adaptive Algorithm to Define Optimal
Size of Structuring Element. Journal of
Image and Graphics. 11: 317-324. 2006.
[2] Gang Li T, Su-pin Wang and NanZhao.
Gray-scale Edge Detection for Gastric
Tumor Pathologic Cell Images by
Morphological Analysis. Biology and
Medicine Journal. 39: 947-952. 2009.
[3] Obara B. Identification of Transcrystalline
Microcracks Observed in Microscope
Images of a Dolomite Structure using
Image Analysis Methods Based on Linear
Structuring Element Processing. Journal
Computers & Geosciences. 33: 151-158.
2007.
[4] Loncaric S. A Survey of Shape Analysis
Techniques, Thesis PhD. Zagreb:
University of Zagreb. 1999.
[5] Goshtasby A. Description and
Discrimination of Planar Shapes Using
Shape Matrices. IEEE Transaction On
Pattern Analysis and Machine
Intelligence. 7: 738-743. 1985.
[6] Costa LF dan Cesar RM Jr. Shape
Representation and Analysis: Theory and
Practice, 2nd Edition. London: CRC
Press. 2009.
[7] Goshtasby A. Intersience 2-D and 2-D
and 3-D Image Registration for Medical,
Remote Sensing, and Industrial
Applications. New York: John Wiley &
Sons, Inc. 2005.
[8] Serra J. Image Analysis and Mathematical
Morphology. London: Academic Press,
Inc. 1982.
[9] Murni A. Pengolahan Citra Digital.
Diktat kuliah. Jakarta: Universitas
Indonesia. 2004.
[10] Soille P. Morphological Image Analysis:
Principles and Applications. Berlin,
Heidelberg: Springer Verlag. 1999.
[11] Haralick RM, Sternberg SR, dan Zhuang
X. Image Analysis Using Mathematical
Morphology. IEEE Transactions on
PAMI. 9: 532-550. 1987.
Vol. 5, No. 3, Januari 2010 ISSN 0216 - 0544
166
OPTIMASI METODE DISCRIMINATIVELY
REGULARIZED LEAST SQUARE CLASSIFICATION
DENGAN ALGORITMA GENETIKA
*Ariadi Retno Tri Hayati Ririd, **Agus Zainal Arifin, ***Anny Yuniarti
*Program Studi Manajemen Informatika, Gedung AH, Politeknik Negeri Malang
Jl. Soekarno Hatta No.9 Malang 65141 **&***Program Pasca Sarjana Jurusan Teknik Informatika, ITS
Jl. Raya ITS, Kampus ITS, Sukolilo, Surabaya, 60111
E-Mail: *[email protected], **[email protected], ***[email protected]
Abstrak
Metode regularisasi dianalisa untuk mengklasifikasi data sehingga diperoleh hasil
pengklasifikasian yang lebih tepat dalam pengenalan pola. Metode Discriminatively
Regularized Least Square Classification (DRLSC) digunakan sebagai metode
pengklasifikasian data berdasarkan informasi diskriminatif dengan menerapkan
penghitungan matrik Laplacian. Kelemahan DRLSC adalah hasil dari
pengklasifikasian data dipengaruhi oleh jumlah tetangga terdekat dari setiap data (K)
dan parameter regularisasi(η). Penelitian ini bertujuan untuk menentukan jumlah
tetangga terdekat dan parameter regularisasi secara otomatis dengan meminimalkan
fitness berdasarkan kesalahan pembelajaran untuk menghasilkan bobot dengan
kualitas yang baik. Penentuan nilai dilakukan dengan menggunakan Algoritma
Genetika (GA) sebagai metode optimasi. GA menggunakan probabilitas crossover
100% dan mutasi gaussian dengan probabilitas 20%. Seleksi dalam operasi crossover,
dilakukan berdasarkan urutan data yang memiliki nilai fitness terbaik hingga nilai
fitness terburuk. Metode GA yang diterapkan untuk mengoptimalkan metode DRLSC
menghasilkan nilai fitness yang lebih baik jika dibandingkan dengan metode DRLSC
tanpa optimasi, dengan perbedaan nilai fitness antara 1.0796e-004 hingga 0,0048.
Kata Kunci: Algoritma Genetika, Discriminatively Regularized Least Square
Classification, Pengenalan Pola.
Abstract
Regularization method has been applied in pattern recognition which aims at
producing of classification data in order to obtain a more accurate classification. The
classification of data based on the information discriminating based on Laplacian
matrix method has been applied with Discriminatively Regularized Least Squares
Classification (DRLSC). The weakness of DRLSC is that the result of data
classification is strongly influenced by the amount of the nearest neighbors on each
data and regularization parameter. The purpose of this study is to determine the
number of the nearest neighbors and the regularization parameters automatically by
minimizing the fitness based on the learning error to produce good quality.
Optimization method used in this study is the learning method of Genetic Algorithm
(GA). GA uses crossover probability 100% and random gaussian mutation with a
probability 20%. The selection in the crossover operation is based on sequence of the
data from best to worst fitness value. GA method which is applied to optimize DRLSC
method produces better fitness value if it is compared with DRLSC method without
optimization. The difference fitness value is between 1.0796e-004 and 0.004.
Key words: Genetic Algorithm, Discriminatively Regularized Least Squares
Classification, Pattern Recognition.
Ririd dkk, Optimasi Metode Discriminatively… 167
PENDAHULUAN
Metode regularisasi pada pengenalan pola telah
mengalami perkembangan misalkan untuk
pengklasifikasian dan pengelompokan data
(clustering). Tujuan dari pengklasifikasian data
adalah kemampuan komputer dalam mengenali
pola secara otomatis untuk menghasilkan data-
data berdasarkan kategori yang berbeda [1].
Pada beberapa metode regularisasi seperti
metode Support Vector Machine (SVM),
Regularization Network (RN), Least Square
Support Vector Machine (LS SVM),
Generalized Radial Basis Function (GRBF)
dan Manifold Regularization (MR), belum
mengklasifikasikan data berdasarkan informasi
diskriminatif. Selain itu, metode-metode
tersebut membutuhkan lebih dari satu
parameter regularisasi. Pada pengklasifikasian,
informasi diskriminatif bertujuan untuk
memaksimalkan jarak data-data yang berbeda
kelasnya agar menghasilkan pengklasifikasian
yang lebih akurat [2].
Metode Discriminatively Regularized Least
Square Classification (DRLSC) menggunakan
dua grafik berdasarkan konsep keterhubungan
data-data pada kelas yang sama (intraclass)
dan keterhubungan data-data pada kelas yang
berbeda (interclass) yang bertujuan untuk lebih
memaksimalkan pengklasifikasian data
berdasarkan informasi diskriminatif.
Sedangkan pada metode SVM,
pengklasifikasian data yang terbagi pada
banyak kelas (multiclass) dilakukan dengan
beberapa kali pengklasifikasian data
berdasarkan dua kelas (binaryclass). Kelebihan
dari metode DRLSC selain berdasarkan
informasi diskriminatif adalah dapat
mengklasifikasikan data secara multiclass
dengan serangkaian persamaan linear.
Multiclass tidak perlu diklasifikasikan ke
dalam bentuk beberapa binaryclass dengan
menggunakan metode Least Square [2].
Metode DRLSC membutuhkan satu parameter
regularisasi untuk mengklasifikasikan data,
sedangkan pada metode sebelumnya, yaitu MR
membutuhkan dua parameter regularisasi.
Kelemahan dari metode DRLSC adalah
pada hasil pengklasifikasiannya sangat
dipengaruhi oleh jumlah tetangga terdekat
setiap data sebanyak K dan parameter
regularisasi. Berdasarkan hal ini maka perlu
adanya optimasi pada penentuan jumlah
tetangga terdekat pada setiap data (K) dan
parameter regularisasi ( η ). Penelitian ini
mengoptimasikan parameter K dan η dengan
Algoritma Genetika yang bertujuan untuk
mendapatkan nilai dari kedua parameter ini
secara otomatis dengan meminimumkan fitness
pembelajaran.
DISCRIMINATIVE REGULARIZED
LEAST SQUARE CLASSIFICATION
(DRLSC)
Penelitian ini dalam pengklasifikasiannya
menggunakan metode Discriminative
Regularization Least Square Classification
(DRLSC) yang dibangun berdasarkan graph
dan operasi matrik. Konsep graph pada metode
DRLSC diterapkan ketika membangun matrik
adjacency dan matrik Laplacian sedangkan
konsep penghitungan matrik diterapkan sebagai
dasar dalam penghitungan Least Square.
Konsep dasar pembangunan graph (G)
dengan menggunakan metode K Nearest
Neighbor digunakan untuk menentukan
hubungan antara data. Pada setiap data ix ,
maka dicari K data yang memiliki jarak yang
terdekat kemudian dibangun edge yang
menghubungkan data ix dengan K data. K data
yang terdekat disimpan pada variabel
ne(i)= k
i
1
i x,...,x . Pada DRLSC dibangun dua
graph berdasarkan intraclass (Gw) dan
interclass (Gb).
Sebelum membangun graph maka perlu
dibagi data ne menjadi dua subset, yaitu seperti
yang ditunjukkan dalam Persamaan (1) dan (2).
new (i) =j
ix | jika j
ix dan ix
masuk pada kelas yang sama, 1≤j≤K (1)
neb (i) =j
ix | jika j
ix dan ix
masuk pada kelas yang berbeda, 1≤j≤K (2)
Pembangunan graph Gw dan Gb berdasarkan
matrik adjacency dengan keanggotaan dari new
dan neb. Setelah pembangunan matrik Gw dan
Gb, maka dilanjutkan dengan pembangunan
matrik Laplacian. Matrik Laplacian dibangun
sebagaimana Persamaan (3) dan (4).
www GDL −= (3)
168 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 166-174
bbb GDL −=, (4)
dimana wD adalah matrik diagonal dengan
elemen diagonalnya merupakan jumlah seluruh
j elemen dari wG . Sedangkan bD merupakan
matrik diagonal dimana elemen diagonalnya
merupakan jumlah seluruh j elemen dari bG .
Pada pengklasifikasian binary class dimana
parameter γ∈RN, dapat dirumuskan
sebagaimana Persamaan (5).
+Ω
N
T
N
N Iη
1
1
0
γb
=
y
0 (5)
Dimana b adalah variabel bias, iγ merupakan
variabel perkalian Langrange (Langrange
multiplier), dan ηS didapatkan dari
Persamaan (6).
( )[ ] T
bw XLLXS ηηη −−= 1 (6)
Dimana
( ) [ ] [ ] NxN
N
T
N
T
Ni
T
jij RIxSx ∈===Ω +,,...,,1,...,11, 1, γγγηη , I
merupakan matrik identitas dan X adalah
kumpulan dari data-data x. Jika data
diproyeksikan berdasarkan kernel, maka perlu
pembangunan matrik kernel dengan cara data
diproyeksikan ke dalam fungsi kernel
kemudian dilanjutkan dengan penyelesaian
persamaan linier [2]. Kernel yang digunakan
adalah kernel gaussian [2]. Persamaan (7)
adalah persamaan untuk kernel gaussian
[3][4][5].
.2σ
exp2
2
−−
ji
ji
xx=)x,K(x (7)
Penghitungan bobot (w) berdasarkan
Persamaan (8).
i
N
i
i xSw
+
=∑=
1
)( ηγ (8)
Untuk pengklasifikasian multiclass, maka
pada label kelas dibangun secara vektor dengan
tujuan dapat mengatasi permasalahan
multiclass. Jika data ix termasuk pada kelas k
maka target kelas adalah Yi=[0,...,1,...,0]T ∈ Rc,
dimana kelas ke-k bernilai 1 dan yang lain
bernilai 0. Penghitungan actual output pada
multiclass dapat dilakukan dengan
menggunakan Persamaan (9).
bxwxf T +=)( (9)
Dimana w∈Rnxc, b∈Rc
Persamaan multiclass didefinisikan dalam
Persamaan (10).
[ ] [ ]YI
b N
N
T
N
N
01
1
0=
+Ω
η
γ (10)
Dimana
[ ] [ ] [ ]N
T
cN yyY ,...,,0,...,00,,..., 11 === γγγ ,
parameter yang lain termasuk ηΩ memiliki
penyelesaian yang sama dengan penyelesaian
pada binary class.
Algoritma Genetika (GA)
Algoritma Genetika memiliki konsep natural
selection untuk permasalahan search dan
optimasi. Dalam hal ini mencari data dengan
nilai terbaik dari suatu kumpulan data.
Ruangan dari semua kumpulan nilai ini
dinamakan search space. Setiap point pada
search space mampu memberikan suatu solusi.
Dengan demikian setiap point pada search
space dapat diberikan nilai fitness tergantung
dari definisi permasalahan. GA berusaha
mencari satu point terbaik dari search space.
Permasalahan dalam hal ini adalah local
minima dan nilai awal dari pencarian data.
Penggunaan random pada GA merupakan
hal yang sangat penting, karena pada proses
seleksi dan pada reproduksi membutuhkan
random. Setiap iterasi pada pembelajaran
dengan metode GA akan selalu menyimpan
populasi yang memiliki informasi yang terbaik.
Kelebihan dari algoritma ini adalah tidak
adanya pembatasan dalam menentukan
permasalahan pada setiap gennya. Dengan
kelebihan ini, maka GA mampu menyelesaikan
semua permasalahan. Kelemahan GA adalah
pada search space. Ia dapat mengalami
kegagalan jika search space tidak tepat atau
tidak adanya point solusi yang tepat pada
search space. Maka perlu adanya batasan pada
search space yaitu batas atas dan batas bawah
pada setiap gen.
GA tidak hanya menggunakan proses mutasi
tetapi juga recombination atau dikenal dengan
istilah crossover. Tujuan dari crossover adalah
reproduksi dua kromosom untuk menghasilkan
kromosom baru dengan karakteristik dari kedua
parent. Pada ilmu biologi, metode
recombination yang umum dengan crossover
Ririd dkk, Optimasi Metode Discriminatively… 169
adalah dengan menentukan satu titik potong
pada setiap kromosom dan dilanjutkan dengan
menggabungkan pada setiap setengah
kromosom. Hasil dari crossover adalah
mendapatkan individu baru yang dihasilkan
dari kedua parent yaitu bapak dan ibu.
Pembentukan individu baru ini sangat penting,
karena kedua individu baru akan memiliki
karakteristik dari kedua parent. Jika kedua
parent memiliki karakteristik yang baik maka
diharapkan individu baru yang terbentuk juga
memiliki karakteristik yang baik. Pada GA,
parent adalah data-data yang dibelajarkan yang
telah terpilih melalui proses seleksi.
Metode mutasi pada GA merupakan cara
lain untuk mendapatkan perubahan dalam
individu baru dalam hal perubahan gen.
Kegunaan dari mutasi adalah membantu
mempercepat proses pencarian nilai optimal.
Selain itu, mutasi bertujuan untuk menghindari
terjadinya local minima [6]. Jika crossover
bertujuan untuk mendapatkan kemungkinan
individu yang baru dengan nilai fitness yang
lebih baik, maka mutasi meningkatkan wilayah
search point setelah individu baru terbentuk
[6]. GA berusaha menangani permasalahan
dengan menganalisa setiap solusi pada masing-
masing populasi. Langkah pertama adalah
dengan melakukan kode pada setiap kromosom
sesuai dengan permasalahan yang akan
diselesaikan. Berikutnya adalah persiapan
pembelajaran dengan operator GA. Operator
reproduksi pada GA dilakukan dengan mutasi
dan crossover.
Seleksi berdasarkan fitness digunakan untuk
mengetahui kualitas dari data yang terseleksi.
Semakin besar nilai fitness maka semakin baik
kualitas data. Namun dalam permasalahan
minimum cost, konsep tersebut dibalik menjadi
bahwa semakin kecil nilai fitness maka kualitas
data semakin baik. Berikut adalah penjelasan
dari proses-proses yang merupakan
pembelajaran GA pada setiap iterasinya (lihat
Gambar 1):
1. Dilakukan random sebesar n populasi yang
merupakan n kromosom.
2. Mengevaluasi fitness dari setiap kromosom.
3. Membangun populasi baru hingga dicapai
nilai optimal dengan perulangan
sebagaimana berikut:
a. Selection: memilih dua parent
kromosom berdasarkan fitness. Semakin
bagus nilai fitness, maka kemungkinan
untuk dipilih semakin besar.
b. Crossover: crossover kedua parent
untuk mendapatkan generasi baru.
c. Mutation: dengan adanya mutation
probability, setiap locus dilakukan
mutasi.
d. Accepting: populasi lama diganti dengan
populasi baru.
e. Replace: populasi baru digunakan untuk
pembelajaran iterasi berikutnya.
f. Test: jika telah memenuhi hasil yang
diinginkan proses berhenti, jika tidak
maka lakukan Loop.
g. Loop: kembali ke langkah dua untuk
mengevaluasi fitness.
Crossover adalah proses penggabungan genetik
dari kedua parent untuk mendapatkan satu atau
lebih anak yang merupakan generasi baru.
Sedangkan mutasi adalah perubahan genetik
dari individu dengan cara beberapa genetik
awal dari individu mengalami perubahan
secara random.
Berdasarkan analisa proses dari GA, maka
dapat disimpulkan beberapa hal yang penting
dalam pembelajaran GA, yaitu:
1. Permasalahan yang akan diselesaikan.
2. Penghitungan fitness.
3. Variasi dari variabel dan parameter pada
kromosom.
4. Hasil akhir dan cara untuk pemberhentian
pembelajaran (pemberhentian iterasi).
Penghitungan fitness adalah cara
pembelajaran GA mendapatkan solusi untuk
mendapatkan data yang menghasilkan suatu
nilai yang mendekati optimal. Penentuan nilai
fitness berdasarkan permasalahan yang akan
dipecahkan. Penentuan nilai fitness memiliki
tujuan untuk mengoptimasi parameter
pembelajaran sebagaimana pada Gambar 1.
Dalam penelitian ini, analisa fitness
berdasarkan Mean Square Error digunakan
dalam menganalisa optimasi kualitas bobot dan
real code diterapkan dalam proses
pembelajaran. Kelebihan dari real code [7]
adalah:
1. Meningkatkan tingkat efisiensi dengan tidak
perlu adanya proses pengubahan dari nilai
binary ke nilai real ataupun sebaliknya. 2. Meningkatkan presisi nilai.
170 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 166-174
Gambar 1. Flowchart Pembelajaran GA.
Gambar 2. Konsep Optimasi Metode DRLSC
dengan GA.
PERANCANGAN SISTEM
Rancangan sistem pengklasifikasian data
dengan metode DRLSC, penentuan jumlah K
tetangga terdekat pada metode KNN, dan
penentuan nilai regularization parameter
secara otomatis ditunjukkan dalam Gambar 2.
Garis titik-titik pada Gambar 2. merupakan
proses GA untuk mengoptimasi DRLSC. Data
yang dimasukkan adalah data-data yang akan
dianalisa, yaitu berupa dataset IRIS, WINE dan
LENSA. Sebelum data dibelajarkan perlu
adanya proses normalisasi data sebagaimana
Persamaan (11).
(j) feature nilai minimum - (j) feature nilai maximumx
(f) feature nilai minimumij
x
ij = (11)
Normalisasi data dilakukan dengan cara
setiap fitur dikurangi nilai minimum pada fitur
tersebut kemudian dibagi dengan nilai
maksimum fitur dan dikurangi dengan nilai
minimum fitur. Tujuan dari proses normalisasi
data adalah menghindari nilai yang terlalu
besar antara data pembelajaran dan data uji
coba.
Inisialisasi Parameter
Langkah awal untuk memperoleh nilai
parameter K dan parameter regularization yang
optimum adalah dengan inisialisasi. Inisialisasi
pada penelitian ini dilakukan secara random
sebagaimana pada GA. Inisialisasi awal adalah
sebesar N data untuk parameter K dan
regularization parameter. Pada penelitian ini
jumlah masukan data sebesar 20 data. Setiap
data terdiri dua bagian, berupa parameter yang
akan dioptimasi, yaitu nilai K dan Ita (η).
Langkah inisialisasi data adalah sebagai
berikut:
1. Random 20 data dengan perintah berikut: Populasi = rand(20,2)
Maka akan dihasilkan 20 data dimana setiap
data memiliki dua parameter yang akan
dioptimasi dengan rancangan kromosom/
partikel sebagaimana Tabel 1. 2. Pengubahan menjadi nilai sebenarnya pada
20 data berdasarkan batas atas dan batas
bawah sebagaimana perintah berikut:
X(:,1)=round(Batas Bawah + (Batas
Atas-Batas Bawah)*Populasi(:,1));
X(:,2)=Batas Bawah + (Batas Atas-
Batas Bawah)*Populasi(:,2);
Ririd dkk, Optimasi Metode Discriminatively… 171
Pengertian dari X(:,1) adalah variabel yang
menyimpan hasil dari pemetaan nilai
random populasi pada kolom pertama
terhadap Batas Atas dan Batas Bawah yang
sesuai dengan parameter X(:,1). Nilai X(:,1)
adalah data-data yang memiliki nilai K.
Pengertian dari X(:,2) adalah variabel yang
menyimpan hasil pemetaan pada parameter
kedua. Nilai X(:,2) adalah parameter Ita
yang memiliki batasan lebih kecil atau sama
dengan 1 (Tabel 2).
Pengklasifikasian DRLSC dilakukan setelah
penentuan inisialisasi ke-20 parameter.
Mendapatkan Fitness Hasil Pembelajaran
DRLSC
Hasil pembelajaran DRLSC adalah penentuan
data-data pembelajaran yang terkelompokkan
pada kelas ke-i, dimana i=1 hingga C yang
merupakan jumlah kelas dengan menerapkan
Persamaan (1) hingga (10). Nilai actual output
yang merupakan nilai keluaran sebenarnya
digunakan sebagai dasar menghitung error
minimum dengan cara mencari selisih target
kelas dikurangkan dengan nilai actual output
pada seluruh data kelas. Fitness yang
digunakan adalah Mean Square Error (MSE).
Berdasarkan nilai MSE, akan didapatkan nilai
parameter K dan Ita yang paling tepat dengan
memperkecil error untuk mendapatkan kualitas
bobot. Hasil dari pembelajaran DRLSC adalah
mendapatkan fitness berdasarkan actual output,
dengan persamaan fitness sebagaimana
Persamaan (12).
∑ − 2f(x))(yN
1=Error(MSE)MeanSquare (12)
Optimasi Metode DRLSC dengan GA
Operator GA berperan penting dalam
mendapatkan optimasi kromosom. Penelitian
ini menggunakan crossover dan mutasi sebagai
operator GA. Persamaan crossover M data
didefinisikan dalam Persamaan (13).
,)1(*
1,......,2,1)1(*
1
'
1
'
Mixxx
Mixxx
ii
iii
=−+=
−=−+= +
αα
αα (13)
Nilai α dari Persamaan (13) adalah nilai yang
dapat bernilai konstan atau random. α dan M
didapatkan dari jumlah inisialisasi parameter.
Berdasarkan Persamaan (13), maka kedua
parent menghasilkan satu anak. Dimulai dari
data pertama crossover dengan pola kedua,
dilanjutkan data kedua crossover dengan data
ketiga demikian berlanjut hingga pola ke-M
crossover dengan pola pertama. Metode ini
sesuai dengan tujuan seleksi yaitu
mendapatkan parent yang baik untuk generasi
berikutnya.
Tabel 1. Rancangan Kromosom pada
Penelitian.
Parameter 1 Parameter 2
K η
Tabel 2. Rancangan 20 Partikel yang
Digunakan.
Data Populasi (data,1) Populasi (data,2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
172 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 166-174
Dengan pengurutan fitness, pola pertama
dan kedua adalah populasi dengan nilai fitness
yang terbaik. Diharapkan generasi berikutnya
akan mendapatkan search point yang lebih baik
dibandingkan kedua parent. Untuk menyimpan
individu terbaik pada generasi sebelumnya,
maka proses crossover dimulai pada data ke-2
(Gambar 3). Jika tidak menyimpan generasi
terbaik sebelumnya, maka dapat terjadi naik
turunnya nilai fitness.
Proses selanjutnya adalah mutasi. Proses
mutasi adalah mengubah satu atau seluruh gen
berdasarkan probabilitas random yang
bertujuan untuk menghindari local minimum.
Jika probabilitas sebesar 100%, maka seluruh
data dan seluruh gen pada data dimutasi. Jika
probabilitas mutasi 0%, maka populasi
berikutnya sama dengan populasi sebelumnya.
Metode mutasi yang digunakan berdasarkan
random gaussian. Metode ini didefinisikan
dalam Persamaan (14).
])[(0,1, gen jumlahnormrandk
xk
x' = (14)
Setiap gen ditambahkan dengan bilangan
random dan dikalikan dengan nilai gaussian.
Nilai gaussian didapatkan sepanjang jumlah
gen yang dibelajarkan. Pada gen pertama, maka
gen ditambahkan dengan nilai gaussian yang
pertama, dan demikian seterusnya. Penentuan
nilai gaussian dilakukan berdasarkan
normrand, yaitu penghitungan nilai gaussian
dari sejumlah data sepanjang jumlah gen yang
telah di-random. Proses optimasi dilakukan
dengan melakukan proses crossover dan mutasi
pada setiap iterasinya hingga mendapatkan
nilai dari kedua parameter, yaitu parameter K
dan , untuk menghasilkan nilai fitness yang
terbaik (meminimumkan fitness).
Stopping Criteria
Berdasarkan Gambar 2, proses akan kembali
pada penentuan nilai K dan η jika belum
memenuhi proses stopping criteria. Jjika telah
memenuhi stopping criteria, maka proses
berhenti (pembelajaran telah konvergen).
Tabel 3. Hasil Percobaan 1 Tanpa Optimasi.
Data Set Fitness Jumlah iterasi Prosentase uji coba K Ita
Iris 1,1e-004 24 93,33% 6 1
Wine 0,0012 24 98,89% 3 0,95
Lensa 0,0049 2 81,82% 3 0,95
Tabel 4. Hasil Percobaan 1 dengan GA.
Data Set Fitness Jumlah iterasi Prosentase uji coba K Ita
Iris 2,04e-006 14 93,33% 8 0,9984
Wine 0,002 20 98,89% 11 0,9757
Lensa 5,6e-005 18 81,82% 3 0.9937
Tabel 5. Hasil Percobaan 2 Tanpa Optimasi.
Data Set Fitness Jumlah iterasi Prosentase uji coba K Ita
Iris 6,7e-005 24 74,67% 6 1
Wine 2,9e-004 24 93,33% 2 0.95
Lensa 0,005 2 92,31% 2 0.95
Tabel 6. Hasil Percobaan 2 dengan GA.
Data Set Error pembelajaran Jumlah iterasi Prosentase uji coba K Ita
Iris 6,7e-005 16 74,67% 6 1
Wine 1,4e-007 17 93,33% 9 0,9004
Lensa 2,8e-004 21 92,31% 3 0.9915
Ririd dkk, Optimasi Metode Discriminatively… 173
Gambar 3. Proses Crossover.
(a)
(b)
(c)
Gambar 4. Grafik Hasil Pembelajaran GA Pada Tabel 6. (a) Grafik Metode GA Data IRIS,
(b) Grafik Metode GA Data WINE, dan (c) Grafik Metode GA Data LENSA.
174 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 166-174
HASIL DAN PEMBAHASAN
Penelitian ini menggunakan dataset uji coba
IRIS, WINE, dan LENSA. Hasil uji coba tanpa
optimasi didapatkan dengan jumlah iterasi
dipengaruhi oleh jumlah data terkecil dari kelas
yang ada dengan lambang N. Sehingga nilai K
dimulai dari 2 hingga N + 1. Untuk nilai η, uji
coba tanpa optimasi menggunakan batas bawah
bernilai 0 dan batas atas bernilai 1. Tabel 3 dan
Tabel 4 menunjukkan hasil uji coba dengan
data pembelajaran sebesar 50% dan data uji
coba sebesar 50% pada setiap kelas.
Fitness yang didapatkan dari hasil tanpa
optimasi memiliki error pembelajaran yang
lebih besar jika dibandingkan dengan hasil
pembelajaran yang dioptimasi dengan GA
(Tabel 4). Maka, untuk meningkatkan kualitas
bobot yang lebih baik dibutuhkan optimasi
untuk mendapatkan nilai parameter K dan η
terbaik. Hasil pembelajaran dengan
menggunakan data yang sama sebagaimana
data-data dari Tabel 3 yang telah dioptimasi
dengan GA ditampilkan pada Tabel 4.
Hasil fitness pada Tabel 4 memiliki
kecenderungan lebih kecil jika dibandingkan
dengan uji coba pada Tabel 3. Hasil fitness
pada Tabel 5 diperoleh dengan menggunakan
data pembelajaran yang merupakan data uji
coba pada Tabel 3 dan Tabel 4. Nilai fitness
memiliki kecenderungan menghasilkan nilai
fitness yang lebih besar jika dibandingkan
error pembelajaran pada Tabel 6. Hal ini
disebakan parameter K dan η pada Tabel 5
belum dioptimasi dengan metode GA.
Hasil fitness pembelajaran data IRIS, WINE
dan LENSA pada Tabel 6 memiliki
kecenderungan menghasilkan nilai fitness yang
lebih kecil jika dibandingkan dengan hasil pada
Tabel 3 yang belum dioptimasi. Gambar 4
menunjukkan terjadi penurunan nilai fitness
pada setiap iterasinya. Proses pembelajaran
akan berhenti jika nilai fitness telah
mendapatkan n iterasi dengan nilai fitness yang
sama. Nilai fitness pada penelitian adalah
Mean Square Error, dimana semakin kecil
nilai error maka diharapkan kualitas bobot
yang didapatkan semakin baik.
SIMPULAN
Berdasarkan hasil uji coba dan pembahasan,
dapat diambil simpulan sebagaimana berikut:
1. Parameter K dan η dapat secara otomatis
didapatkan dengan menerapkan metode
optimasi GA.
2. GA yang diterapkan untuk mengoptimasi
metode DRLSC memiliki kecenderungan
mampu menghasilkan nilai fitness yang
lebih baik jika dibandingkan metode
DRLSC tanpa optimasi yaitu antara
1.0796e-004 dan 0.0048.
DAFTAR PUSTAKA
[1] Bishop CM. Pattern Classification and
Machine Learning. New York: Springer
Berlin Heidelberg. 2006.
[2] Xue H, Chen S, and Yang Q.
Discriminatively Regularized Least-
Squares Classification. Science Direct,
Pattern Recognition. 42: 93-104. 2009.
[3] Rifkin RM and Lippert RA. Computer
Science and Artificial Intelligence
Laboratory Technical Report. Notes on
Regularized Least Squares. 2007.
URL: http://cbcl.mit.edu/projects/cbcl/pub
lications/ps/MIT-CSAIL-TR-2007-
025.pdf, diakses tanggal 10 Agustus 2009.
[4] Arune K and Gopal M. Least Squares
Twin Support vector machines for pattern
classification. Science Direct, Expert
Systems with Applications. 36:7535-
7543.2009.
[5] Schölkopf B, Guyon I and Weston J.
Statistical Learning and Kernel Methods
in Bioinformatics. Proceedings NATO
Advanced Studies Institute on Artificial
Intelligence and Heuristics Methods for
Bioinformatics. 1-21. 2001.
[6] Sivanandam SN and Deepa SN.
Introduction to Genetic Algorithms.
NewYork: Springer Berlin Heidelberg.
2008.
[7] Wright AH. Genetic Algorithms for Real
Parameter Optimization. Montana
Missoula: Department of Computer
Science, University of Montana Missoula.
1991.
Vol. 5, No. 3, Januari 2010 ISSN 0216 - 0544
175
PERBAIKAN STRUKTUR WEIGHTED TREE DENGAN
METODE PARTISI FUZZY DALAM PEMBANGKITAN
FREQUENT ITEMSET
*Budi Dwi Satoto, **Daniel O Siahaan, ***Akhmad Saikhu
* Jurusan Teknik Informatika, Universitas Trunojoyo
Jl. Raya Telang PO. BOX 2, Kamal, Bangkalan, Madura, 69162 **&*** Jurusan Teknik Informatika, ITS
Jl.Raya ITS, Kampus ITS, Sukolilo, Surabaya, 60111
E-Mail: *[email protected], **[email protected], ***[email protected]
Abstrak
Association Rule (AR) merupakan salah satu metode untuk menemukan nilai asosiasi
hubungan antar barang. AR meliputi pembangkitan frequent itemset dan penggalian
kaidah asosiasi. Kelemahan proses sebelumnya pada metode AR yang menggunakan
algoritma generasi kandidat maupun stuktur tree adalah saat pembangkitan frequent
itemset tidak memperhatikan jumlah jenis barang dalam satu transaksi. Struktur
Weighted Tree merupakan salah satu metode untuk membangkitkan frequent itemset.
Kelebihan struktur data ini adalah memperbaiki kebutuhan jumlah data yang diolah di
dalam FPTree. Adapun kelemahan Weighted Tree adalah apabila variasi nilai weight
berupa quantity terlalu tinggi, maka variasi node yang muncul menjadi tinggi.
Sehingga ada kemungkinan node menjadi banyak dan mempengaruhi kecepatan
proses apabila seluruh data disisipkan. Untuk mengatasi kelemahan tersebut,
penelitian ini memperbaiki Weighted Tree dengan menambahkan Metode Partisi
Fuzzy dimana data weight berupa quantity item akan dibagi menjadi lima kelompok
label yaitu very Low, Low, Medium, Height dan very Height. Hasilnya adalah apabila
variasi data weight quantity cukup tinggi, maka data akan menjadi lebih mudah untuk
dilihat dalam pengamatan pengguna dan perhitungan jumlah node yang digunakan
dalam proses pencarian dan penggalian frequent itemset menjadi minimal (nilai
prosentase penurunan jumlah node adalah 37,18%).
Kata kunci: Association Rule, Weighted Tree, Metode Partisi Fuzzy.
Abstract
Association Rule is one of methods to find relationship value between two different
products. AR method consists of the frequent itemset generation and Association Rule
Mining among frequent itemset. The weakness of the previous process for A.R method
using candidate generation or tree structure is it doesn’t note the amount of variety of
goods in transaction. Weighted Tree structure is one of data structures to generate
frequent itemset. The advantage of this data structure is to repair the needs of the
data required by Frequent Pattern Tree. Inevitably, the weakness is if there are many
variation of weight quantity, It will increase the number of node, and influence to
speed of computation process when all data are inserted. To solve the weakness, this
research purposes to repair Weighted Tree by adding Fuzzy Partition Method that
will be splited the weight quantity item into five group labels. The labels are Very
Low, Low, Medium, Height and Very Height. The result is if the data variation
become high, the data will be viewed easily by the users, and the calculation the
number of node which is used in the process of finding and creating frequent itemset
becomes minimal (number of nodes reduction procentage is 37.18%).
Key word: Association Rule, Weighted Tree, Fuzzy Partition Method.
176 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 175-185
PENDAHULUAN
Association Rule (AR) merupakan salah satu
metode untuk menemukan nilai hubungan antar
barang. Contoh analisa asosiasi adalah market
basket analysis dimana dua barang berbeda, a
dan b, dikatakan mempunyai nilai asosiasi jika
dibeli bersama dalam satu transaksi. Metode
AR memiliki dua buah algoritma yaitu
algoritma pembangkitan frequent itemset dan
algoritma penggalian kaidah asosiasi.
Weighted Tree adalah salah satu struktur
data untuk membangkitkan frequent itemset
dengan cara menampung data ke dalam sebuah
tree berdasarkan weight berupa quantity item.
Teknik penyisipan dan penelusuran data
menggunakan konsep tree menyusun informasi
nama item, nomor transaksi dan quantity ke
dalam suatu wadah secara berurut sehingga
data frequent itemset menjadi lebih mudah dan
cepat untuk ditelusuri [1].
Penelitian Weighted Tree dalam
pembangkitan frequent itemset diajukan oleh
Kumar untuk meminimalkan jumlah data dan
jumlah node yang diolah Frequent Pattern
Tree. Pembangkitan frequent itemset pada
penelitian sebelumnya masih menggunakan
Algoritma Generasi Kandidat (Algoritma
Apriori) dan Algoritma Frequent Pattern
Growth (FP-Growth).
Hasil dari perbaikan Weighted Tree adalah
frequent itemset yang telah dilakukan seleksi
berdasar weight minimum support, min_length,
Top-K item, dan gradient. Selain itu, dihasilkan
rule generation yang akan menjadi bahan
pertimbangan pengguna dalam menentukan
item yang akan dicari tingkat asosiasinya.
Dalam penelitian ini dilakukan pengembangan
terhadap Metode Weighted Tree, yaitu adanya
penambahan Metode Partisi Fuzzy dan
pengembangan untuk mendapatkan balancing
tree. Terdapat beberapa alasan sehingga
Metode Partisi Fuzzy [2] dibutuhkan pada
struktur data Weighted Tree [3], di antaranya
adalah:
1. Apabila nilai weight berupa quantity terlalu
bervariasi maka data menjadi sulit untuk
diamati dan hasil algoritma sorting untuk
mencari rute terpendek menjadi lebih
panjang. Selain itu akan membuat jumlah
node menjadi tinggi.
2. Apabila quantity dalam transaksi berbeda
adalah sama, misalnya item mangga dengan
quantity pembelian 4 dengan item jambu
dengan quantity 4, maka dapat dipastikan
bahwa kedua item tersebut saling frequent.
3. Ketidakpastian muncul apabila terdapat
item dengan jumlah quantity yang
jumlahnya sedikit lebih banyak. Misal item
mangga dengan quantity 4 dan jambu
dengan quantity 6. Keduanya dapat
dikatakan saling frequent dengan nilai
support dan confidence yang berbeda.
Permasalahannya adalah apabila data
masukan besar dan cukup variatif, maka
selisih quantity tersebut akan menjadi sulit
untuk diamati pengguna.
Di dalam Metode Association Rule terdapat
algoritma pembangkitan frequent itemset yang
merupakan algoritma untuk mendapatkan
itemset yang memiliki nilai asosiasi dalam satu
transaksi berdasarkan nilai support dan
confidence. Selain itu terdapat algoritma
penggalian kaidah asosiasi yang merupakan
algoritma untuk mendapatkan rule pembelian
itemset berdasarkan kaidah frequent closed dan
frequent maximal [4].
Gambar 1. Blok Diagram Association Rule.
Satoto dkk, Perbaikan Struktur Weighted Tree… 177
Tabel 1. Tabel Transaksi dengan Count
Weight Quantity.
TID KodeItem i1 i2 i3 i4 i5
100 2 6 4
200 4 6 3
300 3 4
400 3 6 8
500 6 2
600 2 7
700 4 5
800 3 4 6 2
900 6 3 2
Tabel 2. Contoh Tabel Itemset Weighted
Tree dengan Tiga Item dan Tiga
Transaksi.
A1 A2 A3
T1 3 2 1
T2 6 2 1
T3 2 2 4
Tabel 3. Tabel Dataset dengan Informasi
Weight.
Kode Item TID i1 i2 i3 i4 i5
100 6 4
200 4 6
300 4
400 6 8
500 6
600 7
700 4 5
800 4 6
900 6
Tabel 4. Sorting Transaksi dan Count Weight.
Nama Item Sorting Transaksi Count Diff
Weight
i1 4:7 6:5:9 2
i2 4:2:8 6:1:4 2
i3 4:3 5:7 6:8 7:6 4
i4 6:2 8:4 2
i5 4:1 1
Tabel 5. Mapping Matrik Pencarian Rute
Terpendek.
Nama Item i1 i2 i3 i4 i5
i1 2 2 4 3 2
i2 2 2 4 3 2
i3 4 4 4 5 4
i4 3 3 5 2 3
i5 2 2 4 3 1
Tabel 6. Perbandingan Jumlah Node FP Tree
dan Weighted Tree.
Jumlah
Transaksi FPTree
Weighted
Tree
Tingkat
Kompresi
9 10 7 30%
ANALISA KAIDAH ASOSIASI
Association Rule menganalisa kebiasaan
pelanggan dalam membeli barang dan
menemukan nilai hubungan antar barang yang
disimpan dalam record transaksi. Secara
umum, sebuah basisdata transaksi terdiri dari
file dimana setiap record-nya berisi daftar
barang yang dibeli dalam sebuah transaksi
seperti yang ditunjukkan oleh Tabel 1 [5].
Gambar 1 menunjukkan blok diagram
Association Rule dalam menggunakan struktur
Weighted Tree untuk mendapatkan frequent
itemset dan nilai kaidah asosiasi. Algoritma
Apriori dan FP tree pada saat pembangkitan
frequent itemset diganti dengan struktur data
weighted tree [1].
Nilai Support count (σ) adalah frekuensi
munculnya itemset tertentu dalam tabel
transaksi. Secara matematis, nilai support dapat
dinyatakan dengan Persamaan (1).
|,||)( TttXtX iii ∈⊆=σ (1)
Dimana:
X = itemset
ti = transaksi ke i
T = set transaksi
Itemset I=i1, i2,…, id adalah set dari semua
item pada data market basket dan T=t1, t2,…,
tN adalah set dari semua transaksi. Tiap
transaksi ti mengandung subitemset dari I. Pada
analisa asosiasi kumpulan dari satu atau lebih
item disebut dengan itemset. Apabila itemset
mengandung k item, maka disebut k-itemset.
178 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 175-185
Gambar 2. Pilihan Node pada Weighted Tree.
Gambar 3. Struktur Weighted Tree.
Null set adalah itemset yang tidak
mengandung item. Lebar transaksi
didefinisikan sebagai banyaknya item yang ada
dan tidak kosong dalam transaksi. Contoh
itemset: i1, i2, i3. Strategi umum pada Metode
Association Rule adalah sebagai berikut:
1. Frequent Itemset Generation, yang
bertujuan untuk menemukan semua itemset
yang memenuhi batasan threshold weight
minimum support, minimum length dan Top-
K Nilai support Item.
2. Rule Generation, bertujuan untuk
mengekstrak semua frequent itemset
menjadi sebuah rule.
WEIGHTED TREE
Pembangkitan frequent itemset menggunakan
struktur Weighted Tree menguraikan kaidah
asosiasi antar atribut dengan menyisipkan nilai
weight berupa quantity per transaksi dengan
mempertimbangkan nilai support dan
confidence masing-masing itemset [1].
Jika A adalah satu item set, suatu transaksi
T dikatakan berisi A hanya jika A⊆T. Suatu
kaidah asosiasi adalah suatu implikasi format
A→B, dimana A⊆I, B⊆I, dan A∩B=Ø. Kaidah
A→B menetapkan D dengan support s, dimana
s merupakan prosentase dari transaksi pada D
yang berisi A ∪ B (keduanya A dan B). Nilai ini
merupakan nilai probabilitas, P(A∩B).
Kaidah A→B mempunyai nilai ”confidence
c” di dalam transaksi D, jika c adalah
prosentase dari transaksi pada D yang di
dalamnya terdapat A dan juga terdapat item B.
Dengan mempertimbangkan probabilitas,
P(B|A), maka Support(A→B) = P(A∩B)=s,
confidence(A→B) = P(B|A)=
Support(A→B)/Support(A) = c [1].
Optimal order merupakan penentuan
sequence order terbaik di dalam tree dengan
jumlah node minimal (lihat dataset Tabel 2)
yang mempunyai tiga atribut. Nilai total
pencarian kombinasi yang dapat dilakukan
adalah sebesar 3!, yaitu enam kombinasi
seperti ditunjukkan dalam Gambar 2.
Unsur atribut tertentu ditemukan di
tingkatan yang ditetapkan sebagai posisi atribut
dalam atribut-sequence. Jika catatan total
jumlah node adalah n, dan di dalam tree
terdapat kombinasi atribut berbeda, maka nilai
optimal order yang terbaik dari weighted tree
di atas adalah atribut sequence 2-3-1 dengan
jumlah node terkecil yaitu 6 [1].
Satoto dkk, Perbaikan Struktur Weighted Tree… 179
Gambar 4. Senarai Weighted Tree.
Struktur Weighted Tree
Weighted Tree memiliki dua jenis node:
1. Jenis node pertama berupa label dengan
atribut berisi nama atribut dan dua pointer
penunjuk node berisi ID transaksi dan
weight. Sedangkan yang lainnya adalah
anak pointer menunjuk pada atribut
berikutnya. Node ini mewakili kepala
cabang tertentu.
2. Jenis node kedua mempunyai dua bagian.
Bagian pertama diberi label TID yang
mewakili suatu jumlah transaksi atau ID
transaksi. Bagian kedua diberi label weight
yang menunjukkan quantity pembelian
dalam transaksi atau cost. Node ini hanya
mempunyai satu pointer yang menunjuk
pada obyek berikutnya dari atribut [1].
Adapun penjelasan konstruksi Weighted Tree
ditunjukkan dalam Gambar 3.
Beberapa definisi yang perlu diketahui
sebelum masuk pada partisi fuzzy adalah
sebagai berikut:
1. Probe item merupakan item yang akan
dijadikan acuan untuk mengetahui tingkat
asosiasi item lain. Isi item ini adalah items
yang sama dalam transaksi atau kumpulan
item transaksi yang sudah pasti nilai
asosiasinya 100%.
2. Top-K merupakan urutan items yang
memiliki nilai count item tertinggi dan
selalu muncul dalam tiap transaksi setelah
dikurangi probe item [4].
3. Projected database merupakan item dan
transaksi yang akan dicari nilai asosiasinya.
Adapun item-nya adalah item total
dikurangi probe item.
4. Minimum length merupakan batas minimum
panjang transaksi yang akan dipantau
tingkat asosiasinya.
5. Weight minimum support adalah batas
maximum pembelanjaan yang memenuhi
syarat yang telah ditentukan pada awal
proses.
Data yang ditunjukkan pada Tabel 1
dipotong berdasarkan nilai weight minimum
support. Contoh, ketika ditentukan weight
minimum support adalah 4, maka weight
quantity 2 dan 3 akan dihapus (seperti yang
ditunjukkan Tabel 3). Setelah itu pemotongan
dilakukan terhadap transaksi yang hanya
mengandung satu item saja, yaitu transaksi
nomor 300, 500, 600 dan 900. Langkah
selanjutnya adalah menyusun senarai Weighted
Tree seperti ditunjukkan pada Gambar 4.
Gambar 4 menerangkan bahwa kode item
yang dihapus karena batasan minimum support
dan nomor transaksi tidak disertakan dalam
penyusunan weighted tree [1]. Langkah
berikutnya adalah pencarian rute terpendek,
dimana idenya adalah jika dalam transaksi
berbeda memiliki nilai weight sama. Maka,
urutan order sequence akan menjadi prioritas
bagi transaksi yang memiliki weight sama
terlebih dahulu seperti pada Tabel 4. Cara
penyelesaian adalah dengan melakukan sorting
terhadap transaksi berdasarkan quantity per
itemname. Untuk Tabel 4, misal, arti dari 6:5:9
adalah “quantity= 6, transaksi= 5 dan 9”.
Dari hasil sorting dan merge prefik pada
Tabel 4 didapatkan nilai count different weight.
Nilai ini selanjutnya akan digunakan untuk
membuat mapping matrik pencarian rute
terpendek, seperti tampak pada Tabel 5 dimana
hasil urutan sequence-nya adalah i5, i1, i2, i4,
i3.
Langkah selanjutnya adalah melakukan
penyisipan ke dalam Weighted Tree dan
hasilnya dapat dilihat pada Gambar 5(b).
Gambar 5(a) menunjukkan jumlah node FP
Tree dan Gambar 5(b) adalah node weighted
tree dari senarai Gambar 4.
Data yang telah disisipkan pada weighted
tree akan ditelusuri sesuai keinginan user pada
waktu melakukan query atau permintaan.
Tampak dari Tabel 6 bahwa jumlah node yang
digunakan oleh Weighted Tree adalah 30%
lebih sedikit dibandingkan dengan FP Tree.
180 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 175-185
Gambar 5. (a) Node FP Tree dan (b) Node Weighted Tree.
Gambar 6. Pencarian Maximal dan Closed Frequent Itemset.
Gambar 7. Membership Function untuk Quantity Item.
(a) (b)
Satoto dkk, Perbaikan Struktur Weighted Tree… 181
Penggalian Kaidah Asosiasi
Konsep penggalian adalah sebuah pendekatan
terhadap hasil pembangkitan frequent itemset
untuk lebih meningkatkan validitas hasil
terdapat acuan pada saat menentukan frequent
itemset. Itemset dikatakan frequent closed
apabila itemset tersebut memenuhi dua kondisi
berikut:
1. Itemset X adalah itemset yang frequent.
2. Tidak ada satupun superset langsung
(immediate supperset) X yang memiliki
count sama dengan X. Jika nilai count-nya
sama maka itemset tersebut dikatakan
frequent not closed.
Pencarian maximal dan closed frequent itemset
ini ditunjukkan dalam Gambar 6. Sebagai
contoh, itemset (11,15) memiliki count 2 dan
superset (11,12,15) juga memiliki count 2,
sehingga dapat dikatakan bahwa itemset
(11,15) adalah itemset yang frequent maximal
but not closed [4].
PEMBANGKITAN FREQUENT
ITEMSET DENGAN METODE
PARTISI FUZZY WEIGHTED TREE
Saat ini teknik pembangkitan frequent itemset
mulai dikembangkan untuk menggantikan
teknik pembangkitan generasi kandidat seperti
metode apriori yang antara lain menggunakan
FP Tree dan Weighted Tree.
Metode Partisi Fuzzy
Metode Partisi Fuzzy melakukan partisi
terhadap weight quantity masing-masing item.
Masing-masing item dibagi menjadi lima label,
yaitu label A, B, C, D dan E. Partisi fuzzy
membantu menyelesaikan masalah pada
Weighted Tree apabila nilai quantity terlalu
bervariasi. [2] Membership function untuk
quantity item yang akan diolah ditunjukkan
oleh Gambar 7.
Dapat dinyatakan setiap kandidat k-itemset,
Ik, sebagai fuzzy set pada transaksi M. Fuzzy
membership function µ dipetakan sebagai kIµ :
M→[0,1], seperti yang dinyatakan dalam
Persamaan (2).
MTTcard
iT T
Iii kk ∈∀
=∈
,)(
)(inf)(
ηµ (2)
Dimana:
T = transaksi yang memenuhi syarat
card(T) = jumlah jenis barang pada transaksi T
η = boolean membership function dan
ηT → 0,1 yang menyatakan
boolean MF (Persamaan (3)).
∈
=lainnya,0
,1)(
TiiTη (3)
Dengan:
i = barang pada transaksi
T = transaksi yang memenuhi syarat
Perhitungan Nilai Support dan confidence
didefinisikan dalam Persamaan (4).
∑∈
=MT
I
k TIsupport k )()( µ (4)
Dimana:
Ik = barang I pada k-itemset
kIµ = fuzzy membership function
T = transaksi yang memenuhi syarat
Sementara nilai Confidence didefinisikan
dalam Persamaan (5).
)(
)()|()(
Asupport
BAsupportABPBAcf
∪==⇒ (5)
dimana:
A,B = k-itemset
Nilai Efisiensi Jumlah Node
Nilai efisiensi didefinisikan sebagai
perbandingan jumlah node sesudah partisi fuzzy
dengan jumlah node sebelum dilakukan partisi
fuzzy. Sedangkan (nilai efisiensi yang
didapatkan pada penelitian sebelumnya
merupakan perbandingan jumlah node
Weighted Tree terhadap jumlah node FP Tree).
Kedua jumlah node tersebut didapatkan dari
matrik m x n senarai Weighted Tree yang
dihasilkan. Sehingga persamaan fungsi fitness
dapat dituliskan dalam nilai efisiensi seperti
pada Persamaan (6).
∑ = ∑ =
∑ = ∑==
m1i
n1j partisi sebelumji,NNode
m1i
n1 partisi setelahji,NNode
node jumlah efisiensi Nilai (6)
182 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 175-185
Gambar 8. Class Diagram Fuzzy Weighted Tree.
Gambar 9. Struktur Data Weighted Tree Partisi Fuzzy.
Gambar 10. Rancangan Weighted Tree.
Satoto dkk, Perbaikan Struktur Weighted Tree… 183
Gambar 11. Projected Database.
Gambar 12. Konversi Data Weight ke Label Fuzzy.
Gambar 13. Rule Generation.
184 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 175-185
Tabel 7. Tabel Perbandingan dengan Penelitian Sebelumnya.
No Perbandingan Penelitian Penelitian kumar
Spec (waktu,node) Penelitian ini
1 Rata-rata waktu untuk konstruksi tree untuk
tiap sequence (dalam detik)
1.2 detik 0.7detik
2 Total waktu untuk mencari sequence terbaik
untuk optimal tree menggunakan metode
pengecekan iterative
45!*1.2=
1.722*10^56 sec
45!*0.7=
8.37356E+55
3 Total jumlah node pada tree menggunakan
serial order attribute (S1)
7729 7729
4 Total jumlah node yang dibentuk tree
menggunakan best sequence dari atribut yang
digunakan menggunakan algoritma ini (S2)
6651 4855
5 Hemat jumlah node 1078 node 2865
HASIL DAN PEMBAHASAN
Masukan Weighted Tree adalah Dataset
SPECTF Heart Data. Data ini diklasifikasikan
menjadi dua kelompok kategori, yaitu normal
dan abnormal. Basisdata ini merupakan 267 set
gambar dengan perincian jumlah atribut 45
(terdiri dari 44 continues class dan satu binary
class), dimana nilai atribut terletak di antara
range 0 sampai dengan 100. Dataset ini dibagi
menjadi SPECTF train 80 item dan SPECTF
test 187 item. Dengan klasifikasi dataset class
0 adalah 15 sample dan class 1 adalah 172
sample.
FuzzyWT adalah sebuah class yang
dibangun untuk melakukan partisi quantity
sebuah item dalam suatu transaksi. Method
utama yang ada pada class FuzzyWT adalah
FuzzyWT(). Method ini adalah constructor
yang digunakan untuk melakukan inisialisasi
object FuzzyWT dengan parameter berupa
array of integer. Class diagram Weighted Tree
ditunjukkan oleh Gambar 8. Parameter yang
ditunjukkan dalam Gambar 8 ini adalah tabel
transaksi yang merupakan keluaran dari
method, yaitu dengan membuat Tabel
Transaksi() pada class
DataSetIO.ProsesKonversiTransToWeight().
Method ini bertugas untuk melakukan
persiapan konversi dari tabel transaksi yang
berisi data array of integer menjadi nilai fuzzy
A sampai E. Struktur data Weighted Tree yang
digunakan dalam penyisipan transaksi pada
penelitian ini ditunjukkan dalam Gambar 9.
Penelitian ini menggunakan struktur linked
list untuk menyimpan informasi weight, item
name, dan nomor transaksi (Gambar10).
Gambar 11 menggambarkan keluaran program
setelah pembacaan dataset SPECTF, yaitu
Projected database disertai probe item.
Informasi yang disimpan meliputi kode biner
SPECTF, nomor transaksi TrID, panjang
transaksi length, dan rata-rata keuntungan
average profit. Pada sampling data tersebut
digunakan probe item i67 dengan weight = 4.
Selanjutnya penentuan weight minimum
support, min_length dan Top-K support item
disertai pemotongan item yang hanya
mengandung satu item akan menentukan data
yang akan disisipkan ke dalam struktur data
Weighted Tree. SPECTF Heart DATA
dikonversikan ke dalam bentuk tabel count
weight quantity, yaitu dalam bentuk label fuzzy
seperti yang ditunjukkan dalam Gambar 12.
Untuk mendapatkan rule generation dicari
Nilai optimum order yang terbaik. Penyisipan
ke dalam weighted tree dan result rule yang di-
generate meliputi nilai support dan confidence
(Gambar 13).
Dari data penelitian sebelumnya dikatakan
terjadi penghematan jumlah node senilai 1078
node dari total node yang disusun
menggunakan teknik serial order atribut.
Dalam hal ini, penghematan mengacu pada
jumlah node pada FPTree dari 7729 node
menjadi 6651 node apabila disusun dengan
menggunakan best sequence order atribut.
Detil perbandingan penelitian dapat dilihat
pada Tabel 7. Nilai perbandingan penurunan
Satoto dkk, Perbaikan Struktur Weighted Tree… 185
jumlah node yang dihasilkan penelitian
sebelumnya adalah [1]:
86052529407729
6651.
node
node anperbandingNilai
a sebelumnypenelitian==
Dari data Tabel 7 maka dapat dicari nilai
perbandingan penurunan berdasarkan jumlah
node yang digunakan penelitian ini yaitu 4855
terhadap jumlah node awal yang digunakan
Kumar [1] yaitu 7729.
62818346507729
4855 .
anperbanding Nilai
ini penelitian==
SIMPULAN
Dari hasil penelitian perbaikan struktur
Weighted Tree menggunakan partisi fuzzy
dapat diambil simpulan sebagai berikut:
1. Penelitian ini memberikan kontribusi
terhadap perbaikan struktur Weighted Tree
dalam penelusuran frequent itemset dengan
adanya penambahan partisi fuzzy untuk
weight dan penambahan keseimbangan di
dalam penyusunan struktur tree. Hal ini
menyebabkan jumlah node yang digunakan
dapat diminimalisasi.
2. Keluaran dari penelitian ini merupakan
hasil obyektif dari sistem. Keluaran
frequent itemset yang dihasilkan
mempunyai frequent itemset yang tetap bila
diberikan masukan dataset yang sama
dengan atau tanpa partisi fuzzy. Perbedaan
proses ditunjukkan oleh jumlah node yang
digunakan dan waktu proses dalam
penelusuran frequent itemset tersebut.
3. Nilai prosentase penurunan jumlah node
yang dihasilkan penelitian ini lebih besar
jika dibandingkan dengan hasil penelitian
sebelumnya, yaitu 37,18% terhadap 13,9%.
DAFTAR PUSTAKA
[1] Kumar P. Discovery of Frequent Itemsets
Using Weighted Tree Approach. IJCSNS
International Journal of Computer
Science and Network Security. 8: 195-200.
2008.
[2] Wang CH. Finding Fuzzy Association
Rules using FWFP Growth with
Linguistic Supports and Confidences.
WORLd Academy of Science, Engineering
and Technology. 53: 1139-1147. 2009.
[3] Kumar P. Discovery of Frequent Itemsets
Based on Minimum Quantity and Support.
International Journal of Computer
Science and Security. 3: 216-225. 2009.
[4] Absari DT. Penggalian Top-K Frequent
Closed Constrained Gradient itemsets
pada basis data retail, Januari 2009. URL:
http://mmt.its.ac.id/library/?p=4737,
diakses tanggal 16 Agustus 2009.
[5] Anbalagan E. Building E-shop using
Incremental Association Rule Mining and
transaction clustering. International
Journal of Computational Intelligence
Research. 5: 11-23. 2009.
Vol. 5, No. 3, Januari 2010 ISSN 0216 - 0544
186
SIMULASI PERGERAKAN PENGUNJUNG MALL
MENGGUNAKAN POTENTIAL FIELD
*Arik Kurniawati, **Supeno MS Nugroho, ***Moch Hariadi Pasca Sarjana Jaringan Cerdas Multimedia (Game Teknologi), Jurusan Teknik Elektro, ITS
Jl. Raya ITS, Kampus ITS, Sukolilo, Surabaya, 60111
E-Mail: *[email protected], **[email protected], ***[email protected]
Abstrak
Simulasi kerumunan manusia yang real-time sulit untuk dilakukan karena perilaku
yang dipamerkan pada kelompok besar ini sangat kompleks dan pelik. Beberapa hal
yang perlu dicermati antara lain penanganan terhadap permasalahan path planning
(perencanaan jalur), collision avoidance (penghindaran tabrakan), serta separation
(pemisahan jarak). Salah satu metode untuk perencanaan jalur adalah potential field
yang berbasis grid. Metode ini memiliki prinsip seperti medan magnet yang menarik
atau menolak partikel besi yang ada di sekitarnya. Berdasarkan karakteristiknya, maka
metode ini dapat digunakan untuk mensimulasikan pergerakan simulasi kerumunan
manusia. Perilaku menolak partikel besi diaplikasikan untuk menghindari halangan
dinding dan perilaku menarik diaplikasikan untuk keluar menuju pintu utama. Selain
itu, diatur juga agar pergerakan antar orang tidak menimbulkan tabrakan. Setelah
diadakan simulasi dan penelitian, maka pergerakan kerumunan manusia yang tersebar
dalam ruang-ruang dan lorong-lorong di mall dengan menggunakan metode potential
field dapat menghindari halangan dinding dan dapat bergerak keluar menuju pintu
utama tanpa terjebak local minima. Namun, hasil penelitian ini masih memiliki
kelemahan, yaitu akan tejadi tabrakan dengan orang lain jika daerah yang dituju sama.
Tingkat frekuensi tabrakan semakin meningkat seiring meningkatnya jumlah populasi.
Untuk jumlah populasi sebanyak 10 dapat terjadi satu kali tabrakan. Bahkan tabrakan
dapat mencapai 9558 kali untuk jumlah populasi sebanyak 500.
Kata kunci: path planning, collision avoidance, separation, potential field, local
minima.
Abstract
Real-time crowd simulation is complicated because large groups of people exhibit
behavior of enormous complexity and subtlety. In crowd simulation, there are many
factors that must be seriously addressed, such as: path planning, collision avoidance,
and separation. Potential field is path planning with grid based. This method works
as magnet field that attract or repulse iron particle. Based on itscharacteristic, it cn
be assumed that this method can be applied to figure the simulation of crowd people
movement. Repulsing iron particle behavior is applied to avoid static obstacles and
attracting is applied to drive the crowd to target. Beside, it also arranges the process
the collision prediction to avoid collision with the others. After the simulation using
potential field method, it can be known that the movement of the human crowd
scattered in the rooms and hallways in the mall can avoid obstacles (walls) and able
to find a target without trapped local minima. However, the possibility in collisison
with others in the same destination. The collision frequency is increasing as number
of population developed, population 10 to 1 times the crash happened and could
reach 9558 for a population of 500.
Key words: path planning, collision avoidance, separation, potential field, local
minima.
Kurniawati dkk, Simulasi Pergerakan Pengunjung Mall… 187
PENDAHULUAN
Salah satu aspek dalam animasi adalah
bagaimana memodelkan sesuatu agar mirip
dengan aslinya di dunia nyata. Menampilkan
perilaku kerumunan yang alami sebagai
peningkatan kualitas animasi menjadi tren
utama dalam film dan game.
Mensimulasikan kerumunan manusia seperti
di dunia nyata menjadi sesuatu kebutuhan
pemodelan yang interaktif dan realistis.
Simulasi kerumunan yang real-time ini sulit
dilakukan karena perilaku yang dipamerkan
pada kelompok besar ini sangat kompleks dan
pelik.
Sebuah model kerumunan tidak hanya
meliputi pergerakan individu manusia dalam
lingkungannya dengan rintangan/batasan yang
ada, akan tetapi juga interaksi dinamis antara
orang-orangnya. Lebih jauh lagi, model harus
dapat mencerminkan Intelligent Path Planning
melalui perubahan lingkungannya. Dan
selanjutnya, orang-orang yang berada di
dalamnya harus dapat menyesuaikan jalan
mereka secara dinamis. Bahkan perubahan
tiba-tiba dari gerakan individu harus dapat
ditangkap dalam efek simulasi ini [1].
Pada prinsipnya pergerakan kerumunan
adalah bagaimana penanganan terhadap
permasalahan Path Planning (Perencanaan
Jalur), Collision Avoidance (Penghindaran
Tabrakan), serta Separation (Pemisahan Jarak).
Jika hanya menggunakan penghindaran
tabrakan, maka model kerumunan yang nyata
tidak akan dapat dihasilkan saat sekelompok
orang tersebut mencapai tujuan.
Konsekuensinya, banyak model kerumunan
yang menggabungkan antara menghindari
tabrakan (collision avoidance) dan
perencanaan global (global navigation).
Gambar 1. Pergerakan dengan Tanda Khas
[3].
Salah satu perencanaan global adalah
potential field statis (static potential field)
dengan berbasis grid. Prinsip kinerjanya adalah
seperti kelereng yang menggelinding menuruni
bukit. Kondisi lingkungan yang dilewati
menjadi penentu arah dan pergerakannya, atau
dapat juga digambarkan seperti medan magnet
yang menarik atau menolak partikel besi [2].
BEHAVIOUR KERUMUNAN
Path finding
Pergerakan dalam suatu simulasi sangat erat
kaitannya dengan path finding (pencarian
jalan). Path finding adalah salah satu dasar
algoritma dalam konsep menggerakkan
karakter. Pergerakan obyek menuju sasaran
dengan mengambil nilai potential field yang
lebih besar diperlihatkan dalam Gambar 1.
Collision Prediction
Dalam setiap frame simulasi kerumunan
(crowd simulation), kebutuhan untuk
memprediksi tabrakan dengan orang lain
menjadi sebuah keharusan. Setelah seseorang
berhasil menghindari tabrakan, maka ia akan
kembali ke jalur aslinya.
Jika sebuah tabrakan telah dapat
diprediksikan, maka jenis tabrakan yang terjadi
harus ditentukan. Ada tiga kemungkinan jenis
tabrakan, yakni:
1. Toward collision atau face-to-
face/berhadap-hadapan, yaitu terjadi ketika
seseorang berjalan menuju satu sama lain
(Gambar 2a).
2. Away collision atau rear/di belakangnya.
Tabrakan ini akan terjadi ketika seseorang
berjalan di belakang orang lain atau ada
hambatan di depannya (Gambar 2(b)). 3. Glancing collision, yaitu tabrakan yang
berasal dari samping kanan atau samping
dan berjalan menuju daerah yang sama
(Gambar 2(c)).
Collision Avoidance
(Penghindaran Tabrakan)
Penghindaran tabrakan antar orang ternyata
dapat menimbulkan banyak permasalahan
ketika berurusan dalam kerumunan. Sebuah
metode untuk menghindari tabrakan antar
individu menjadi tidak efisien ketika digunakan
188 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 186-196
dalam kerumunan banyak orang. Ada lebih
banyak kendala yang terjadi dalam sebuah
variabel lingkungan yang kompleks (dengan
hambatan yang tetap, rintangan
mobile/bergerak dan daerah yang kecil untuk
berjalan) dan mencakup banyak orang [5].
Namun, jika struktur grup dalam kelompok
harus dipertahankan, maka harus ada
penambahan parameter lain dalam kerumunan
kompleksitas untuk menghindari tabrakan [6].
Walaupun collision avoidance
(penghindaran tabrakan) terlihat begitu
kompleks dalam realitanya, namun hal ini
dapat didefinisikan menjadi beberapa aturan
yang sederhana. Berikut ini adalah cara-cara
bagaimana mengantisipasi berbagai jenis
tabrakan:
1. Toward Collisions
Tahap pertama adalah menentukan apakah
akan bertabrakan di sebelah kiri atau kanan
dari seseorang. Pengamatan menunjukkan
bahwa seseorang akan memiliki tiga cara
yang berbeda untuk menghindari tabrakan:
a. Mengubah arah saja
b. Mengubah kecepatan saja
c. Mengubah arah dan kecepatan
Jika tidak ada perilaku yang ditemukan
untuk menghindari tabrakan, maka
seseorang tersebut hanya akan berhenti
berjalan. Setelah orang lain keluar dari jalur
tabrakan maka seseorang tersebut akan
melanjutkan jalannya.
2. Away Collisions
Jika seseorang berjalan di belakang orang
lain atau dengan kata lain seseorang
tersebut tepat di belakang orang lain,
sehingga akan terjadi tabrakan dengan
orang lain yang ada di depannya. Untuk
mengatasi situasi ini, maka seseorang
tersebut ada dua pilihan:
a. Menyesuaikan kecepatan dengan orang
yang ada di depannya dengan
memperlambat kecepatan berjalannya.
b. Berjalan dengan kecepatan tinggi dengan
mengambil jalur di samping depan orang
lain.
3. Glancing Collisions
Cara untuk mengantisipasi jenis tabrakan ini
sama seperti dengan metode nomor 1
(toward collisions).
Potential Field
Konsep dasar metode potential field
digambarkan seperti partikel besi yang
bergerak menuju objek melalui medan magnet
yang dibuat oleh objek yang dituju. Pergerakan
ini tergantung dari medan magnet yang ada,
yaitu partikel akan ditarik ke arah tujuan atau
justru sebaliknya partikel tersebut akan ditolak
oleh medan magnet pada saat bertemu
halangan [7].
Potential Field Aktraktif
Potential field atraktif adalah potential field
yang mengatur bagaimana setiap agen yang ada
bergerak mengarah ke tujuan, seperti yang
diperlihatkan dalam Gambar 3.
Perhitungan nilai potential field tujuan,
didapatkan dari konsep potential field dari
elektrostatika [8], yaitu dengan menggunakan
Persamaan (1).
Vga = V * exp (-λ * Xga) (1)
Dimana:
V = Konstanta potential field
Λ = Konstanta
Vga = Potential field untuk tujuan
Xga = Jarak ke tujuan
Gambar 2. Tipe-tipe Tabrakan [4]. (a) Toward
Collision, (b) Away Colliso, dan (c)
Glancing Collision.
Gambar 3. Potential Field Aktraktif.
Kurniawati dkk, Simulasi Pergerakan Pengunjung Mall… 189
(a) (b)
Gambar 4. Implementasi Fungsi Eksponensial
untuk Potential Field Aktraktif.
(a) Potential Field Aktraktif dan
(b) Grafik Eksponen Potential
Field Aktraktif.
Gambar 5. Potential Field Repulsif.
(a) (b)
Gambar 6. Implementasi Fungsi Eksponensial
untuk Potential Field Aktraktif.
(a) Potential Field Repulsif dan
(b) Grafik Eksponen Potential Field
Repulsif.
Gambar 7. Potential Field Gabungan.
Gambar 8. Permasalahan Local Minima.
Persamaan (1) dapat digunakan untuk
menentukan nilai potential field aktraktif
dengan memanfaatkan puncak gundukan.
Dalam artian, semua partikel yang berada di
bawah nilai puncak gundukan tersebut akan
tertarik ke puncak gundukan (yang mempunyai
nilai tertinggi). Jadi dapat diibaratkan puncak
gundukan adalah target yang akan dituju.
Ilustrasi ini seperti yang diperlihatkan dalam
Gambar 4.
Potential Field Repulsif
Potential field repulsif adalah potential field
yang mengatur bagaimana setiap agen dapat
menghindari halangan (obstacle) yang ada,
seperti yang diperlihatkan dalam Gambar 5.
Perhitungan nilai potential field halangan,
didapatkan dari konsep potential field dari
elektrostatika [8], dengan menggunakan
Persamaan (2).
Vgo= -V * exp (-λ * Xgo) (2)
Dimana:
V = Konstanta potential field halangan
Λ = Konstanta
Vgo = Potential field untuk obstacle
Xgo = Jarak ke obstacle
Persamaan (2) jika dimanfaatkan untuk
menghitung nilai potential repulsif, maka
partikel tidak akan tertarik ke puncak
gundukan. Namun sebaliknya, partikel akan
menolak dan berlari menuju nilai yang lebih
tinggi. Jadi dapat diibaratkan garis yang
membentuk fungsi eksponensial itu, harus
dijauhi atau dalam artian halangan harus
dihindari seperti yang diperlihatkan dalam
Gambar 6.
190 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 186-196
Gambar 9. Bentuk Grid.
Setiap potential field dapat dirancang
tersendiri untuk digunakan dalam
menghadirkan suatu perilaku khusus. Dengan
mengkombinasikan beberapa potential field
yang ada maka pergerakannya dapat mencapai
tingkat perilaku yang beragam [7].
Potential Field total = Potential Field Atraktif + Potential Field Repulsif
Akibat dari penggabungan ini adalah nilai
potential field yang didapat pada daerah tujuan
merupakan nilai paling tinggi dari sekitarnya
sehingga partikel akan bergerak menuju tujuan.
Sedangkan pada halangan nilai-nilainya adalah
lebih rendah, dengan tujuan agar partikel dapat
menghindari halangan (Gambar 7).
Permasalahan Local Minima
Permasalahan local minima merupakan
permasalahan yang melekat pada potential
field. Tidak ada solusi standar untuk
menyelesaikan permasalahan local minima [9].
Local minima terjadi ketika agen terjebak
pada penghalang karena nilai dari posisinya
mengarahkan ke daerah itu. Hal ini berarti agen
tidak dapat mengakses nilai yang lebih tinggi
dari posisinya sekarang karena agen berada
pada nilai terendah dibanding sekelilingnya.
Sehingga agen tidak dapat menemukan target
yang dituju (Gambar 8).
Grid
Cara pengorganisasian potential field adalah
dengan membuat area menjadi grid. Tiap kotak
pada grid adalah sebuah posisi dan setiap
posisi memiliki sebuah nilai yang
merepresentasikan sedekat apa posisi tersebut
dengan target.
Grid seperti yang diperlihatkan dalam
Gambar 9 mempunyai fungsi untuk menyimpan
resultan potential field dari seluruh vektor
repulsive halangan. Vektor resultan ini
kemudian ditambahkan dengan vektor dari
target. Sehingga pergerakan seseorang hanya
mengikuti arah vektor resultan tersebut menuju
target.
PERANCANGAN SISTEM
Pada bagian ini akan dijelaskan beberapa hal
tentang mengenai proses perancangan simulasi
yang dibuat. Diagram penelitian ditunjukan
dalam Gambar 10, yaitu menggambarkan
sebuah sistem simulasi yang akan dibuat.
Simulasi ini menggambarkan pergerakan
kerumunan manusia mencari jalan keluar lewat
pintu utama di sebuah mall. Goal dari simulasi
ini adalah semua orang yang berada dalam
ruangan dapat keluar menuju pintu utama.
Masing-masing orang yang berhasil sampai
menuju pintu utama tidak sama waktunya. Hal
ini tergantung dari panjang lintasan seseorang,
kecepatan berjalan dan jalur lintasan yang
dilewati. Pemilihan jalur menuju pintu utama
menggunakan Algoritma Potential Field.
Halangan
Halangan statis dalam simulasi adalah dinding
pembatas ruangan dan halangan permanen
lainnya yang terdapat di tengah-tengah
ruangan. Halangan statis diibaratkan sebagai
potential field repulsif, seperti yang
diperlihatkan dalam Gambar 11.
Gambar 10. Diagram Blok Penelitian.
Kerumunan
manusia dalam
mall dengan
posisi cak
Kerumunan manusia
dalam mall dengan
posisi acak
Pemilihan Jalur
Potential Field
Collision Avoidance
Pemilihan Jalur
Potential Field
Collision Avoidance
Semua orang
berhasil keluar
menuju pintu
utama
Semua orang berhasil
keluar menuju pintu
utama
(3)
Kurniawati dkk, Simulasi Pergerakan Pengunjung Mall… 191
Gambar 11. Halangan Statis sebagai Potential
Field Repulsive.
(a) (b)
Gambar 12. Pergerakan Seseorang ketika
akan Menabrak Halangan Statis.
(a) Kondisi Awal dan
(b) Kondisi Setelah Berputar.
Gambar 13. Nilai Potential Field Jalur
Penghubung antar Ruangan.
Agar seseorang dapat keluar dari ruangan-
ruangan kecil dalam mall tersebut, maka
rancangan potential field jalur-jalur
penghubung antar ruangan dijadikan potential
field aktraktif atau dibuat lebih tinggi dari
lingkungan sekitarnya (Gambar 13).
Selain halangan statis tersebut, ada
halangan lain yang bersifat dinamis yakni
orang-orang di sekitarnya yang juga berusaha
mencari jalur keluar ke pintu utama. Jika
seseorang menemui halangan dinamis, maka
ada beberapa jenis pergerakan yang mungkin
dilakukan, antara lain:
1. Jika di depannya ada orang lain:
a. Jika orang lain tersebut bergerak searah
dengan seseorang yang ada di
belakangnya, maka pergerakan orang
tersebut akan menyesuaikan orang yang
dihadapannya (Gambar 14).
Aturan yang digunakan pada kondisi
Gambar 14, antara lain:
i. Simpan kecepatan bergerak orang
yang di depannya.
ii. Kecepatan orang di depannya
dikurangi dan menjadi kecepatan
bergerak orang di belakangnya. iii. Bergerak searah.
b. Jika orang lain tersebut bergerak tidak
searah dengan seseorang yang ada di
belakangnya maka pergerakan orang
tersebut akan berputar arah haluan
mencari tempat yang kosong (Gambar
15). Namun, jika tidak ada tempat
kosong, maka orang yang tersebut akan
berhenti sampai mendapatkan tempat.
2. Jika daerah yang dituju sama dengan daerah
yang dituju oleh orang lain, maka hal ini
dapat menyebabkan tabrakan jika tidak
dihindari. Untuk mengantisipasinya, arah
pergerakannya diputar mencari tempat yang
kosong, seperti yang diilustrasikan dalam
Gambar 16.
Target
Target adalah area yang harus dituju oleh
semua orang, yang tak lain adalah potential
field atraktif. Area tersebut mempunyai
pengaruh atau influence yang meliputi seluruh
area.
Nilai pada
daerah ini
dibuat lebih
tinggi dari
sebelumnya.
Nilai pada daerah ini
dibuat lebih tinggi dari sekitarnya
192 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 186-196
(a) (b)
Gambar 14. Pergerakan yang Searah. (a) Kondisi Awal dan (b) Kondisi Setelah Bergerak.
(a) (b)
Gambar 15. Pergerakan 450 ke Kiri Depan. (a) Kondisi Awal dan (b) Kondisi Setelah Bergerak.
Gambar 16. Jika Daerah yang Dituju Sama.
Kurniawati dkk, Simulasi Pergerakan Pengunjung Mall… 193
Gambar 17. Rancangan Posisi Setiap Orang.
Gambar 18. Rancangan Perhitungan Potential
Field Jalur Penghubung ke-1.
Skenario Pergerakan Kerumunan Manusia
Menuju Pintu Utama
Posisi orang-orang di dalam mall diatur secara
random. Posisi setiap orang tidak ada yang
sama dan tidak boleh menempati area dinding
yang berwarna merah. Selain itu, posisi
menghadap setiap orang diatur menghadap
pintu utama seperti yang ditunjukkan dalam
Gambar 17.
Algoritma Pemilihan Jalur Menggunakan
Potential Field
Pemilihan jalur alternatif menuju pintu utama
menggunakan Algoritma Potential Field.
Rancangan skenario Algoritma Potential Field,
adalah sebagai berikut:
1. Potential field halangan statis diberi nilai
= 0.
2. Potential field jalur-jalur penghubung di
setiap ruangan dijadikan potential field
aktraktif sehingga diberi nilai lebih tinggi
dari sekitarnya. Sedangkan dinding-dinding
dalam ruangan diberi nilai potential field
repulsif. Agar orang-orang dalam ruangan
tersebut dapat keluar menuju jalur
penghubung dan bergerak menjauhi
dinding, maka kedua nilai potential tersebut
digabungkan sesuai dengan Persamaan (4)
dan (5).
Vgo = - V * exp (-λ * Xgo) (4)
Vg1 = V * exp (-λ * Xg1) (5)
Dimana:
V = Konstanta potential field, V=2
(Pemilihan angka 2 agar nilai hasil
tidak terlalu besar)
Λ = Konstanta 0,05 (Pemilihan angka
0.05 agar grafik eksponensialnya
tidak terlalu landai dan tidak
terlalu runcing)
Vg1 = Potential Field aktraktif untuk
jalur penghubung ke-1
Vgo = Potential Field repulsif untuk
dinding-dinding dalam ruangan
tersebut
Xg1 = Jarak ke jalur penghubung ke-1
Xgo = Jarak ke Obstacle
Rancangan perhitungan diilustrasikan dalam
Gambar 18.
Jika nilai Potential field jalur
penghubung ke-1 sudah didapatkan, maka
nilai Potential field jalur penghubung ruang
ke-2 adalah nilai potential field jalur
penghubung ke-2 ditambah dengan nilai
Potential field repulsif dari dinding-dinding
sekitarnya. Nilai-nilai tersebut kemudian
digabungkan dengan nilai Potential field
sebelumnya (jalur penghubung ke-1), dan
berikut seterusnya sesuai dengan Persamaan
(6), (7), dan (8).
Vg2 = Vg2 + Vgo (6)
Vg2 = Vg2 + Vg1 (7)
Vgi = Vgi + Vgi-1 (8)
Jadi, nilai potential field yang ada dalam
peta ruangan mall tersebut adalah
penjumlahan potential field jalur-jalur
penghubung antar ruangan. Urutan
penjumlahan berdasarkan letak ruangan
194 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 186-196
dimulai dari yang paling dalam sampai
dengan mendekati pintu utama, seperti
dalam Gambar 19.
3. Potential field target diset dengan nilai
paling tinggi dari sekitarnya. Jadi,
perhitungan nilai potential field untuk
target merupakan nilai potential field target
ditambah dengan perhitungan nilai-nilai
potential field jalur-jalur penghubung
sebelumnya sesuai dengan Persamaan (9).
Vga = V * exp (-λ * Xga) (9)
Dimana:
V = Konstanta potential field, V=2
Λ = Konstanta 0,05
Vga = Potential field untuk tujuan
Xga = Jarak ke tujuan
HASIL DAN PEMBAHASAN
Uji coba dirancang dalam beberapa skenario
uji coba untuk melihat faktor keberhasilan dari
rancangan simulasi yang dirancang
sebelumnya.
Gambar 19. Urutan Perhitungan Potential
Field Jalur Penghubung antar
Ruangan.
Skenario Pertama
Skenario pertama adalah jika seseorang dalam
perjalanannya menemui halangan statis, yakni
akan menabrak dinding. Pengamatan dilakukan
dengan memvariasi berbagai arah gerak orang
yang akan menabrak dinding. Hasil uji coba ke-
1 sampai dengan ke-4 menunjukkan bahwa jika
seseorang akan menabrak dinding, maka dia
akan berputar ke kanan sebesar (180 + random
180)0 seperti yang diperlihatkan dalam Tabel 1.
Skenario Kedua
Skenario kedua adalah pengamatan tentang
terhadap pergerakan seseorang jika berpapasan
dengan orang lain, yaitu:
1. Jika ada orang lain di depannya dengan arah
yang sama, maka orang yang berjalan di
belakangnya menyesuaikan kecepatannya
dengan orang yang di depannya. Sedangkan
arah geraknya tergantung pada tempat yang
kosong di depannya.
2. Hasil uji coba ditampilkan dalam Tabel 2.
Jika ada orang lain di depannya dengan arah
yang berbeda, maka orang yang berjalan di
belakangnya menyesuaikan kecepatannya
dengan orang yang di depannya. Sedangkan
arah geraknya tergantung pada tempat yang
kosong di depannya.
3. Hasil uji coba ditampilkan dalam Tabel 3.
Tampak dari hasil uji coba untuk skenario
ini (Tabel 4), masih terjadi tabrakan antar
orang. Terlebih lagi jika jumlah populasinya
sangat besar, maka frekuensi tabrakan juga
semakin besar.
Jika daerah yang dituju sama, maka uji coba
simulasi dilakukan dengan variasi jumlah
populasi.
Skenario Ketiga
Skenario ketiga ini adalah perbandingan
pengamatan pergerakan kecepatan seseorang
untuk sampai tujuan. Uji coba dilakukan
dengan memvariasi daerah asal. Kecepatan
berjalan orang dewasa lebih cepat dari orang
tua. Hasil simulasi seperti yang diperlihatkan
dalam Tabel 5.
Skenario Keempat
Skenario keempat ini adalah skenario utama
pencapaian hasil simulasi, yaitu mengenai
Kurniawati dkk, Simulasi Pergerakan Pengunjung Mall… 195
Tabel.1. Data Uji Perputaran Sudut
Menghindari Rintangan.
No
Uji
coba
ke-n
Sudut
Kedatangan
Sudut
Perputaran
Keberhasilan
Menghindari
Rintangan
1 1 45 o 225 o Ya
2 2 135 o 315 o Ya
3 3 125 o 305 o Ya
4 4 30 o 210 o Ya
Tabel 2. Data Uji Pergerakan skenario ke-2(1).
No Uji coba
ke-n
Berhasil Mencari
Tempat Kosong
Kecepatan
Lebih Pelan
1. 1 Bergerak lurus Ya
2. 2 Berputar Ya
3. 3 Bergerak lurus Ya
4. 4 Berputar Ya
Tabel 3. Data Uji Pergerakan skenario ke-2(2).
No Uji coba
ke-n
Berhasil Mencari
Tempat Kosong
Kecepatan
Lebih Pelan
1. 1 Bergerak lurus Ya
2. 2 Berputar Ya
3. 3 Berputar Ya
4. 4 Berputar Ya
Tabel 4. Data Uji Pergerakan skenario ke-2(3).
No Uji coba
ke-n
Jumlah
Populasi
Jumlah
Tabrakan
1. 1 10 1
2. 2 50 37
3. 3 100 197
4. 4 200 1046
5. 5 400 3957
6. 6 500 9558
Tabel 5. Data Uji Skenario ke-3.
No Uji Coba
ke-n
Waktu Orang
Dewasa
Waktu
Orang Tua
1. 1 68.1 82.4
2. 2 100 105
3. 3 84 93
4. 4 47.1 58
Tabel 6. Data Uji Skenario ke-4.
Jumlah
Populasi
Jumlah
Orang
Sampai
di Tujuan
Jumlah
Orang
Masih di
Ruangan
Waktu
Keluar
Rata-Rata
%
Keberhasilan
yang keluar
10 10 0 124.3 100
50 50 0 126.95 100
100 100 0 142.35 100
200 200 0 182.75 100
400 400 0 252 100
pergerakan orang keluar menuju pintu utama.
Uji coba dilakukan dengan memvariasi jumlah
populasi. Tampak dalam Tabel 6 bahwa semua
orang (dalam berbagai jumlah populasi yang
berbeda) yang terdapat dalam mall berhasil
keluar menuju pintu utama tanpa ada yang
tertinggal di dalam ruangan. Hanya saja waktu
yang diperlukan akan semakin lama jika jumlah
populasinya semakin besar.
SIMPULAN
Dari penelitian penggunaan metode potential
field dalam simulasi kerumunan untuk
pergerakan orang-orang keluar menuju pintu
utama dapat disimpulkan sebagai berikut:
1. Dalam kemampuan menghindari halangan
statis (dinding), tingkat keberhasilan
mencapai 100%.
2. Jika dilihat dari collision avoidance dengan
orang lain, tingkat keberhasilannya sudah
mencapai 100% untuk kondisi jika ada
orang lain di depannya. Akan tetapi jika
daerah yang dituju adalah sama maka masih
terjadi tabrakan. Tingkat frekuensi tabrakan
semakin meningkat seiring meningkatnya
jumlah populasi. Untuk jumlah populasi 10,
terjadi satu kali tabrakan dan dapat
mencapai tabrakan 9558 untuk jumlah
populasi 500.
3. Kemampuan pergerakan orang keluar
menuju pintu utama memiliki tingkat
keberhasilannya 100% (tidak terjadi local
minima). Hal ini terjadi karena gaya tarik
yang diberikan oleh potential field aktraktif
di jalur penghubung lebih kuat dari pada
gaya tolak dari dinding yang diberikan oleh
potential field repulsif.
196 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm. 186-196
DAFTAR PUSTAKA
[1] Treuille A, Cooper S, and Popovi Z.
Continuum Crowds. URL: http://grail.cs.
washington.edu/projects/crowd-flows/
continuum-crowds.pdf, diakses tanggal 20
Oktober 2009.
[2] Michael A and Goodrich. Potential fields
Tutorial. URL: http://students.cs.byu.edu
/~cs470ta/readings, diakses tanggal 11
Desember 2009.
[3] Thurau C, Bauckhage C, and Sageger G.
Learning Human Like Movement Behavior
for Computer Games. URL: http://www.
airesearch.techfak.uni-bielefeld.de/files/
papers/Thurau2004-LHL.pdf, diakses
tanggal 15 Desember 2009.
[4] Foudil C, Noureddine D, Sanza C, and
Duthen Y. Path Finding and Collision
avoidance in Crowd Simulation. Journal
of Computing and Information
Technology. 17: 217-228. 2009.
[5] Lightfoot TJ and Milne GJ. Modelling
Emergent Crowd Behaviour. URL:
http://www.csse.uwa.edu.au/ComplexSyst
ems/Literature/Modelling%20Emergent%
20Crowd%20Behaviour.pdf, diakses
tanggal 18 Desember 2009.
[6] Wolff M, Birenbaum A, and Sagar E.
Crowd Notes on the behaviour of
pedestrians, In People in Places: The
Sociology of the Familiar. New York:
Praeger. 1973.
[7] Villena HC. Multiple Potential field In
Quake 2 Multiplayer, Master Thesis
Department of Software Engineering and
Computer Science Blekinge Institute of
Technology. URL: http://www.
bth.se/fou/cuppsats.nsf/all/5a0cf1e001ac9
489c12571f100512ae6/$file/MasterThesis
HectorVillena.pdf, diakses tanggal 1
Desember 2009.
[8] NetLogo User Community Models. OBS.
URL: http://ccl.northwestern.edu/netlogo
/community/OBS.nlogos, diakses tanggal
1 November 2009.
[9] Laue T and Rover T. A Behavior
Architecture for Autonomous Mobile
Robots Based on Potential field, in
RoboCup 2004: Robot World Cup VIII.
Lecture Notes in Artificial Intelligence,
Springer. (Nr. 3276,S): 122-133. 2005.
URL: http://www.informatik.uni-bremen.
de/kogrob/papers/rc05-potentialfields.pdf,
diakses tanggal 17 Desember 2009.
Vol. 5, No. 3, Januari 2010 ISSN 0216 - 0544
197
DETEKSI OUTLIER BERBASIS KLASTER PADA SET DATA
DENGAN ATRIBUT CAMPURAN NUMERIK DAN KATEGORIKAL
*Dwi Maryono, **Arif Djunaidy Program Magister Teknik Informatika, Fakultas Teknologi Informasi, ITS
Jl. Raya ITS, Kampus ITS, Sukolilo, Surabaya, 60111
E-Mail: *[email protected], **[email protected]
Abstrak
Deteksi outlier merupakan salah satu bidang penelitian yang penting dalam topik data
mining. Penelitian ini bermanfaat untuk mendeteksi perilaku yang tidak normal
seperti deteksi intrusi jaringan, diagnosa medis, dan lain-lain. Banyak metode telah
dikembangkan untuk menyelesaikan masalah ini, namun kebanyakan hanya fokus
pada data dengan atribut yang seragam, yaitu data numerik atau data kategorikal saja.
Kenyataan di lapangan, set data seringkali merupakan gabungan dari dua nilai atribut
seperti ini. Dalam penelitian ini diajukan sebuah metode untuk mendeteksi outlier
pada set data campuran yaitu MixCBLOF. Algoritma ini merupakan gabungan dari
beberapa teknik, seperti klasterisasi subset data, deteksi outlier berbasis klaster, dan
penggunaan Multi-Atribute Decision Making (MADM). Uji coba dilakukan pada
beberapa set data dari UCI Machine Learning Repository. Evaluasi dilakukan dengan
membandingkan rata-rata pencapaian coverage untuk top ratio antara jumlah outlier
eksak dengan jumlah data. Dari uji coba yang dilakukan, diperoleh hasil bahwa
MixCBLOF cukup efektif untuk mendeteksi outlier pada set data campuran dengan
rata-rata pencapaian coverage 73,54%. Hasil ini lebih baik dibandingkan dengan
algoritma CBLOF yang diterapkan pada set data yang telah didiskritisasi dengan rata-
rata pencapaian coverage 67,98%, untuk diskritisasi dengan K-Means, dan 59,48%
untuk diskritisasi dengan equal width.
Kata kunci: data campuran, deteksi outlier, Outlier berbasis klaster, CBLOF,
MixCBLOF.
Abstract
Outlier detection is one of most the important research on mining data. This data is
useful to detect abnormal behaviour such as networking detection, medical diagnosis
and the others. Such methods have been developed to solve these problems, yet mostly
focus on the data in similar attribute like numerical and categorical. Set data, in fact,
is combination of the two attributes. This research purposes a method to detect the
outlier at mix data set, like Mix CBLOF. Furthermore, algorithm is combination of
several techniques such as subset cluster, outlier detection cluster based, and Multi-
attribute Decision Making (MADM). A test was done of a set of data from UCI
Machine Learning Repository. The Evaluation is conducted to compare the means of
coverage achieiving for top ratio between the amount of exact outlier and the amount
of data. From the test, it can be concluded that MixCBLOF is effective to detect
outlier at set of mix data of means of coverage achieiving 73.54%. This result is
better with CBLOF algorithm which is applied at the data set discridit with coverage
achieiving 67.98% for discreet with K-Means, and 59.48% for equal width discreet.
Key words: mix data, outlier detection, outlier cluster based, CBLOF, MixCBLOF
.
198 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm.197-204
PENDAHULUAN
Deteksi outlier pada sekumpulan data adalah
salah satu bidang penelitian yang terus
berkembang dalam topik data mining.
Penelitian ini sangat bermanfaat untuk
mendeteksi adanya perilaku atau kejadian yang
tidak normal seperti deteksi penipuan
penggunaan kartu kredit, deteksi intrusi
jaringan, penggelapan asuransi, diagnosa
medis, segmentasi pelanggan, dan sebagainya.
Bermacam-macam metode telah
dikembangkan baik berdasarkan teknik ataupun
jenis data yang dijadikan obyek. Untuk set data
numerik, ada banyak teknik yang telah
dikembangkan seperti statistic-based, distance-
based, density-based, clustering-based,
subspace-based, dan lain-lain. Sedangkan
untuk set data kategorikal teknik yang dapat
digunakan di antaranya adalah CBLOF, FPOF
dan LSA. Namun demikian kebanyakan metode
tersebut hanya fokus pada set data yang
seragam, yaitu hanya terdiri dari salah satu tipe
atribut saja. Adanya tipe atribut yang berbeda
biasanya diatasi dengan melakukan
transformasi dari salah satu tipe data menjadi
tipe data yang lain, seperti diskritisasi atribut
numerik. Namun demikian metode diskritisasi
atribut numerik ini terdapat kekurangan seperti
yang disebutkan Tan dkk [1]. Kekurangannya,
antara lain adalah sulitnya menetapkan jumlah
interval yang tepat sehingga dapat
menyebabkan banyak pola yang redundant atau
sebaliknya banyak pola yang hilang. Ini akan
sangat berpengaruh jika atribut numerik cukup
banyak dalam set data.
Sejauh ini tidak banyak penelitian yang
bekerja pada data campuran seperti ini. He dkk
[2] telah melakukan klasterisasi pada data
campuran dengan pendekatan divide and
conquer. Ia membagi set data menjadi dua
subset data, yaitu numerik dan kategorikal.
Masing-masing subset data diklasterisasi,
kemudian hasilnya digabungkan. Data hasil
penggabungan keduanya kemudian diklaster
lagi untuk mendapatkan hasil akhir. Hasil
eksperimen menunjukkan bahwa metode ini
cukup efektif untuk melakukan klasterisasi.
Jika klasterisasi dapat dilakukan dengan
partisi data numerik dan kategorikal [2], maka
tentunya cara ini juga memungkinkan untuk
deteksi outlier.
Mengingat penelitian lain juga menunjukkan
bahwa deteksi outlier pada subset data tertentu
dapat digunakan untuk mendeteksi outlier dari
keseluruhan set data [3,4] Selain itu,
penggabungan klasterisasi subset data juga
digunakan untuk menemukan outlier pada data
numerik dengan konsep cluster uncertainty [5].
Dari beberapa penelitian yang disebutkan di
atas, dimungkinkan untuk melakukan beberapa
pendekatan yang dapat diusulkan dalam
penelitian ini. Di antaranya adalah pembagian
set data menjadi numerik dan kategorikal,
deteksi outlier pada subset data, dan
pemanfaatan klasterisasi untuk untuk deteksi
outlier. Untuk dapat menerapkan ide tersebut
digunakan definisi outlier yang paling tepat.
Outlier didefinisikan berbasis klaster, dimana
sebuah outlier didefinisikan sebagai sembarang
obyek yang tidak berada pada klaster yang
”cukup besar” [6]. Meskipun konsep ini
diusulkan untuk data kategorikal, tapi sangat
memungkinkan untuk diterapkan dengan data
numerik dengan menggunakan konsep jarak.
Penelitian ini dilakukan untuk
menggabungkan beberapa pendekatan di atas
dengan langkah-langkah sebagai berikut.
Pertama, bagi set data menjadi dua bagian,
yaitu subset data numerik dan kategorikal [2].
Selanjutnya dilakukan teknik klasterisasi dan
deteksi outlier pada masing-masing partisi
secara terpisah. Untuk meningkatkan hasil
deteksi outlier pada keseluruhan data,
dilakukan teknik persilangan. Hasil klasterisasi
sub data numerik digunakan untuk menentukan
derajat outlier berbasis klaster dengan atribut
sub data kategorikal. Dan sebaliknya hasil
klasterisasi sub data kategorikal digunakan
untuk menentukan derajat outlier dengan
menggunakan atribut numerik. Selanjutnya,
untuk menggabungkan hasil langkah-langkah
ini dapat digunakan multi-atribut decision
making (MADM) yaitu dengan menggunakan
fungsi atau operator agregat tertentu [7].
DETEKSI OUTLIER BERBASIS
KLASTER
Metode yang diajukan dalam penelitian ini
adalah pengembangan dari konsep outlier
berbasis klaster yaitu dengan mendefinisikan
konsep baru mengenai deteksi outlier berbasis
klaster [6] (Gambar 1).
Maryono dan Djunaidy, Deteksi Outlier Berbasis Klaster… 199
Gambar 1. Set Data DS1 [8].
Gambar 2. Jarak Obyek dari Centroid
Terdekat [10].
Gambar 3. Jarak Relatif Obyek dari Centroid
Terdekat [10].
Gambar 1 memperlihatkan data dua dimensi
yang terdiri dari empat klaster C1, C2, C3, dan
C4. Dari sudut pandang klaster, obyek-obyek
data pada C1 dan C3 dapat dianggap sebagai
outlier karena tidak terdapat pada klaster yang
besar yaitu C2 dan C4. C2 dan C4 disebut klaster
besar karena C2 dan C4 merupakan klaster yang
dominan pada set data, yaitu memuat sebagian
besar obyek pada set data [9].
Konsep CBLOF digunakan untuk
menyelesaikan masalah deteksi outlier pada
data kategorikal [6]. Namun, dalam penelitian
ini dapat ditunjukkan bahwa konsep ini juga
dapat dikembangkan untuk data numerik juga.
CBLOF (Cluster-Based Outlier Factor)
Untuk mengidentifikasi signifikansi fisik dari
definisi outlier, setiap obyek didefinisikan
dengan sebuah derajat yang disebut dengan
CBLOF (Cluster Based Local Outlier Factor)
yang diukur dengan ukuran klaster di mana ia
berada dan jaraknya terhadap klaster terdekat
(jika ia terdapat dalam obyek kecil) [6].
Definisi 1: Misalkan A1, A2, ..., Am adalah
himpunan atribut dengan domain D1, D2, ...,
Dm. Set data D terdiri dari record atau transaksi
t: t∈D1 × D2 × …×Dm. Hasil klasterisasi pada
D dinotasikan sebagai C= C1, C2, …, Ck
dimana Ci ∩ Cj = ∅ dan C1∪ C2∪ …∪Ck=D,
dengan k adalah jumlah klaster.
Masalah yang penting pada tahap selanjutnya
adalah pendefinisian klaster besar (large
cluster) dan klaster kecil (small cluster).
Definisi 2: Misalkan C= C1, C2, …, Ck
adalah himpunan klaster pada set data dengan
urutan ukuran klaster adalah |C1| ≥ |C2 |≥ …≥
|Ck|. Diberikan dua parameter numerik α dan
β. Didefinisikan b sebagai batas antara klaster
besar dan kecil jika memenuhi formula pada
Persamaan (1) dan (9).
(|C1|+|C2|+...+|Cb|)≥|D|*α (1)
|Cb|/|Cb+1|≥β (2)
Didefinisikan himpunan klaster besar (large
cluster) sebagai LC = Ci, / i ≤ b dan klaster
kecil (small cluster) didefinisikan dengan SC =
Ci, / i >b.
Definisi 2 memberikan ukuran kuantitatif
untuk membedakan klaster besar dan kecil.
Persamaan (1) menunjukkan bahwa sebagian
besar data bukan outlier. Oleh karena itu
200 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm.197-204
klaster besar mempunyai porsi yang jauh besar.
Sebagai contoh jika α diberikan 90% maka
artinya lebih klaster besar memuat lebih dari
90% dari total obyek data pada set data.
Persamaan (2) menunjukkan fakta bahwa
klaster besar dan kecil harus memiliki
perbedaan yang signifikan. Jika diberikan β =
5, artinya setiap klaster besar minimal 5 kali
lebih besar dari klaster kecil.
Definisi 3: Misalkan C = C1, C2, …, Ck
adalah himpunan klaster dengan urutan ukuran
|C1| ≥ |C2| ≥ … ≥ |Ck|. Didefinisikan LC dan SC
sebagaimana Definisi 2. Untuk sembarang
record t, didefinisikan cluster-based local
outlier factor sebagaimana Persamaan (3).
∈∈
∈∈∈=
C ,Cuntuk t )),(s*(||
Cdan C ,Cuntuk t ),( smax(*||)(
ii
jii
LCtCimC
LCSCtCimCtCBLOF
ii
ji (3)
Fungsi sim(C,t) pada Persamaan (3) adalah
fungsi kemiripan transaksi t terhadap kelas C
sebagaimana dalam algoritma Squeezer [8].
Meskipun CBLOF diperuntukkan untuk data
kategorikal dan dapat dikembangkan untuk
data numerik. Ini dilakukan dengan
mendefinisikan CBLOF dengan perhitungan
derajat outlier sebagaimana Persamaan (3).
NCBLOF (Implementasi CBLOF pada Data
Numerik)
Salah satu pendekatan deteksi outlier berbasis
klaster adalah dengan mengesampingkan
klaster-klaster kecil yang jauh dari klaster yang
lain. Pendekatan ini dapat digunakan dengan
menggunakan sembarang teknik klasterisasi,
namun memerlukan threshold berapa jumlah
minimum ukuran klaster dan jarak antara
klaster kecil dengan klaster yang lebih besar.
Pendekatan lain adalah dengan menentukan
derajat dimana sebuah obyek berada pada
sembarang klaster. Sebagai perwakilan klaster
dapat digunakan centroid untuk menghitung
jarak antara obyek dengan klaster.
Ada beberapa cara untuk mengukur jarak
sebuah obyek ke sebuah klaster, yaitu dengan
mengukur jarak sebuah obyek terhadap
centroid terdekat, atau dapat juga dengan
mengukur jarak relatif obyek dengan centroid
terdekat. Jarak relatif adalah rasio jarak obyek
terhadap centroid dibagi dengan jarak rata-rata
semua titik terhadap centroid klaster di mana ia
berada.
Hasil derajat outlier dapat dilihat
berdasarkan shading. Pendekatan hanya
berdasarkan jarak saja akan menyebabkan
masalah jika set data mempunyai kerapatan
yang berbeda-beda. Pada Gambar 2, dengan
menggunakan jarak saja, obyek D tidak
dianggap sebagai outlier, padahal obyek
tersebut cenderung sebagai outlier lokal dari
klaster terdekatnya. Sedangkan pendekatan
pada Gambar 3, akan mengidentifikasikan A,
C, dan D sebagai outlier sebagaimana
Algoritma LOF [9].
Namun demikian jika sebuah obyek berada
dalam klaster yang kecil, maka untuk
perhitungan dengan jarak relatif seperti di atas
ia tidak akan terdeteksi sebagai outlier. Oleh
karena itu, pada penelitian ini digunakan
pendekatan sebagaimana pada CBLOF yang
menganggap obyek-obyek dalam klaster yang
kecil sebagai kandidat outlier. Deteksi outlier
menggunakan konsep mengenai klaster besar
dan klaster kecil juga, dimana derajat outlier
dihitung sebagai Numerical Cluster-based
Local Outlier Factor (NCBLOF).
Dalam CBLOF ada dua komponen
pembentukan derajat outlier, yaitu jumlah
anggota klaster besar terdekat dan
kemiripannya terhadap klaster terdekat
tersebut. Dua komponen ini digunakan juga
untuk mendefinisikan NCBLOF sebagaimana
Persamaan (4).
∈∈
=
∈∈∈
=
C ,Cuntuk t )),(distance relatif
1|C|
))(,min(argC
,Cdan C ,Cuntuk t ),(distance relatif
1||
)(
iii
j
jii
LCCt
Ccentroidt
LCSCCt
C
tNCBLOF
i
j
j
j
Rumus NCBLOF pada Persamaan (4)
didefinisikan dengan menyesuaikan
interprestasi derajat outlier pada CBLOF pada
Persamaan (3).
MULTI CRITERIA DECISION
MAKING (MCDM)
MCDM adalah cabang dari masalah
pengambilan keputusan, yang berkaitan dengan
pengambilan keputusan, di bawah keberadaan
sejumlah kriteria keputusan. Metode ini dibagi
menjadi Multi-objective Decision making
(MODM) dan Multi-attribute decision making
(MADM). Metodologi ini mencakup adanya
(4)
Maryono dan Djunaidy, Deteksi Outlier Berbasis Klaster… 201
konflik antar kriteria, incomparable unts, dan
kesulitan dalam pemilihan alternatif. Dalam
MODM, alternatif-alternatif solusi tidak
ditentukan lebih dahulu. Melainkan
sekumpulan fungsi obyektif dioptimasi
terhadap sekumpulan konstrain atau batasan.
Dalam MADM, alternatif dievaluasi dengan
mengatasi sekumpulan kriteria atau atribut
yang saling konflik. Masalah penggabungan
outlier dalam permasalahan penelitian ini
termasuk dalam kategori ini. Masing-masing
sub data numerik dan kategorikal dianggap
sebagai sebuat atribut dalam MADM. Teori
yang banyak digunakan dalam MADM adalah
multi-atribut value theory (MAVT), dimana
perangkingan alternatif keputusan
dibangkitkan. Dalam prakteknya, metode
berbasis MAVT menggunakan operator
agregasi yang dirasa cocok untuk mendapatkan
faktor outlier dari seluruh obyek. Operator
tersebut di antaranya adalah operator product
(kali), sum (tambah), dan operator S∞.
Berikut adalah macam-macam operator
agregat yang dapat digunakan dalam MAVT:
1. Operator Perkalian ∏
Operator perkalian juga dikenal sebagai
metode perkalian berbobot. Operator ini
menggunakan perkalian untuk
menghubungkan rating dari atribut sebagai
berikut:
⊕( a1, a2, ..., am) = ∏ (a1w1, a2
w2, ..., amwm) =
a1w1 a2
w2 ... amwm = ∏ ai
wi
2. Operator Penjumlahan
Operator penjumlahan juga disebut dengan
metode penjumlahan berbobot. Operator ini
menggunakan penambahan untuk
menghubungkan rating dari atribut sebagai
berikut:
⊕( a1, a2, ..., am) = +(w1 a1, w2 a2, ..., wm am)
= w1 a1+w2 a2, ... +wm am = Σwi ai
3. Operator S∞
Operator S∞ juga dikenal dengan operator
maksimum atau operator agregasi dasar.
Operator ini memberikan nilai terbesar dari
sekumpulan nilai yang diberikan sebagai
berikut:
⊕( a1, a2, ..., am) = S∞ (w1 a1, w2 a2, ..., wm
am) = max wi ai
ALGORITMA MIXCBLOF
Penelitian ini mengusulkan metode MixCBLOF
untuk menyelesaikan masalah deteksi outlier
pada set data campuran. Misalkan diberikan
sebuah set data D yang terdiri dari n obyek
dengan atribut campuran numerik dan
kategorikal. Langkah-langkah Algoritma
MixCBLOF adalah sebagai berikut:
1. Bagi set data campuran menjadi dua bagian,
yaitu set data numerik, D1 dan set data
kategorikal, D2.
2. Lakukan klasterisasi pada subset data
numerik D1 sehingga diperoleh sejumlah
klaster C11, C12, ..., C1p dengan ukuran
berturut-turut:
|C11| ≥ |C12| ≥ ... ≥ |C1p|
Tentukan klaster besar (LC) dan klaster
kecil (SC) menggunakan Definisi 2.
3. Terapkan deteksi outlier berbasis klaster
menggunakan atribut numerik, NCBLOF,
terhadap obyek-obyek dalam klaster pada
langkah 2 sebagaimana Persamaan (4).
4. Terapkan deteksi outlier berbasis klaster
menggunakan atribut kategorikal terhadap
obyek-obyek dalam klaster pada langkah 2
dengan CBLOF pada Persamaan (3).
5. Lakukan klasterisasi pada sub set data
kategorikal sehingga diperoleh sejumlah
klaster C21, C22, ..., C2q dengan ukuran
berturut-turut:
|C21| ≥ |C22| ≥ ... ≥ |C2q|
Tentukan klaster besar (LC) dan klaster
kecil (SC) menggunakan Definisi 2.
6. Terapkan deteksi outlier berbasis klaster
menggunakan atribut kategorikal terhadap
obyek-obyek dalam klaster pada langkah 2
dengan CBLOF pada Persamaan (3).
7. Terapkan deteksi outlier berbasis klaster
menggunakan atribut numerik terhadap
obyek-obyek dalam klaster pada langkah 5
dengan NCBLOF pada Persamaan (4).
8. Susun derajat outlier pada langkah 3, 4, 6,
dan 7 dalam matrik keputusan A=[aij].
9. Lakukan pembobotan secara default (bobot
sama) atau dengan metode Entropy.
10. Gabungkan bobot outlier tiap obyek t1, t2, ..,
tn pada langkah 9 dengan fungsi agregat
untuk mendapatkan derajat outlier akhir OF
dari sebuah obyek ti.
OF(ti ) = ⊕ (a1i, a2i, a3i, a4i)
202 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm.197-204
HASIL DAN PEMBAHASAN
Algoritma MixCBLOF diimplemetasikan pada
beberapa set data nyata yang diperoleh dari
UCI Machine Learning Repository dengan
beberapa karakteristik khusus. Set data uji coba
terdiri dari atribut campuran numerik dan
kategorikal serta memiliki beberapa kelas atau
klaster dimana sebagian di antaranya adalah
kelas dengan ukuran yang relatif lebih kecil
sehingga dapat dianggap sebagai sekumpulan
outlier. Data yang digunakan pada uji coba ini
adalah Set data Cleveland (Heart Disease),
Hypothyroid, Hepatitis, dan Annealing. Dalam
algoritma MixCBLOF ini melibatkan
Algoritma Squeezer dan CBLOF untuk sub
data kategorikal, sedangkan untuk data
numerik digunakan Algoritma CLUTO [10]
dan NCBLOF.
Uji coba dijalankan sesuai dengan skenario
yang telah dirancang, yaitu:
1. Menentukan parameter yang tepat utuk
Algoritma MixCBLOF meliputi penentuan
α, β, operator agregat, dan pembobotan
yang tepat untuk masing-masing set data
2. Membandingkan MixCBLOF dibandingkan
dengan algoritma lain, yaitu algoritma
CBLOF yang diterapkan pada set data yang
sudah didiskritisasi.
Evaluasi dilakukan dengan menggunakan
top ratio dan coverage. Top ratio adalah
perbandingan antara jumlah k outlier yang
dihasilkan oleh algoritma (n top ratio) dengan
jumlah keseluruhan obyek dalam data.
Sedangkan coverage adalah rasio antara jumlah
outlier eksak yang terdeteksi dengan jumlah
keseluruhan outlier eksak yang dicari. Agar
lebih mudah dalam melakukan analisa hasil,
evaluasi dilakukan dengan melihat rata-rata
pencapaian coverage untuk top ratio antara
jumlah outlier eksak dengan jumlah
keseluruhan data.
Hasil uji coba algoritma MixCBLOF dapat
dilihat pada Tabel 1. Pencapaian coverage
terbaik untuk top ratio antara jumlah outlier
eksak dengan jumlah keseluruhan data dicetak
dengan huruf tebal. Jika dilakukan rata-rata,
algoritma MixCBLOF mencapai coverage
73.54%. Dari Tabel 1 dapat dilihat bahwa di
antara operator yang ada, operator perkalian
menghasilkan kinerja yang lebih baik jika
dibandingkan dengan dua operator lainnya,
yaitu penjumlahan dan maksimum. Selain itu,
pembobotan sama menghasilkan kinerja yang
lebih baik jika dibandingkan pembobotan
dengan pembobotan berdasaran entropy.
Salah satu parameter yang juga penting,
selain operator agregat dan pembobotan,
adalah α dan β yang mempengaruhi
dipenuhinya konsep klaster besar dan kecil.
Pada Tabel 2 dapat dilihat hasil pencapaian
coverage untuk dua kasus, yaitu dipenuhinya
konsep klaster besar dan kecil atau tidak.
Berdasarkan hasil Tabel 2, tidak ada perbedaan
yang signifikan terhadap dipenuhinya konsep
klaster besar dan kecil. Namun demikian
konsep ini tetap dibutuhkan berdasarkan
definisi CBLOF yang dijelaskan di awal.
Tabel 1. Pencapaian Coverage untuk n = Jumlah Outlier Eksak pada Keseluruhan Set Data
Berdasarkan Operator dan Pembobotan.
Coverage
(+) ∏ S∞ Set data
wi=1 entropy wi=1 entropy wi=1 entropy
Sub data Cleveland I 76.90% 53.80% 92.30% 76.90% 53.80% 23.10%
Sub data Cleveland II 77.00% 77.00% 89.00% 86.00% 66.00% 66.00%
Dataset Cleveland 73.00% 74.00% 76.00% 75.00% 69.00% 68.00%
Hypothyroid 72.10% 73.00% 47.50% 63.90% 9.00% 54.90%
Hepatitis 52.40% 33.30% 66.70% 47.60% 33.30% 19.00%
Annealing 35.30% 32.40% 47.10% 47.10% 26.50% 26.50%
Rata-rata 64.45% 57.25% 69.77% 66.08% 42.93% 42.92%
Maryono dan Djunaidy, Deteksi Outlier Berbasis Klaster… 203
Tabel 2. Perbandingan Kinerja MixCBLOF
Dilihat dari Pemenuhan Konsep
Klaster Besar dan Kecil.
Dipenuhi Konsep Klaster
Besar/Kecil Set data
Iya Tidak
Sub Cleveland I 61.50% 53.80%
Hypothyroid 67.20% 72.10%
Hepatitis 66.70% 66.7%
Annealing 47.10% 47.10%
Rata-rata Coverage 60.63% 59.93%
Tabel 3. Perbandingan Pencapaian Coverage
Terbaik untuk Top Ratio, N=Jumlah
Outlier Eksak, Antara Mixcblof
dengan CBLOF Berbasis
Diskritisasi Set Data.
Best Coverage
CBLOF Set data
MixCBLOF K-Means Equal
Width
Sub data
Cleveland I
92.30% 84.60% 92.30%
Sub data
Cleveland II
88.60% 82.90% 88.60%
Hypothyroid 73.00% 66.40% 16.40%
Hepatitis 66.70% 61.90% 61.90%
Annealing 47.10% 44.10% 38.20%
Rata-rata 73.54% 67.98% 59.48%
Tabel 4. Running Time Algoritma
MixCBLOF dilihat dari Jumlah
Atribut dan Record.
Set data Jumlah
record
Jumlah
atribut
Running
time
(detik)
Sub data
Cleveland I
177 14 0.125
Sub data
Cleveland II
199 14 0.1563
Hypothyroid 2000 17 0.4688
Hepatitis 118 16 0.1406
Annealing 535 6 0.1406
Pada uji coba juga dilakukan perbandingan
MixCBLOF terhadap Algoritma CBLOF
dengan diskritisasi atribut numerik. Hasil dari
keseluruhan uji coba dirangkum pada Tabel 3.
Dari Tabel 3 dapat dilihat bahwa Algoritma
MixCBLOF dapat menyelesaikan masalah
deteksi outlier pada set data campuran dengan
cukup baik. Top ratio antara jumlah outlier
eksak dengan jumlah keseluruhan data mampu
mencapai rata-rata coverage sebesar 73.54 %.
Hasil ini lebih baik jika dibandingkan CBLOF
dengan diskritisasi numerik yang hanya mampu
mencapai rata-rata coverage 67.98% untuk
diskritisasi dengan K-Means dan 59.48% untuk
diskritisasi dengan equal width.
Tabel 4 menampilkan informasi mengenai
running time dari algoritma MixCBLOF jika
dilihat dari jumlah atribut dan record pada
masing-masing kasus. Uji coba ini dilakukan
pada lingkungan sebagai berikut.
1. Hardware:
a. Processor: Dual Core Genuine Intel
(R) CPU T2080 @ 1.73 GHz
b. Memory: DDR 512 MB
c. Hard disk: 80 GB
2. Software:
a. Microsoft Windows XP Professional
Version 2002 Service Pack 2
b. MATLAB Versi 7.0
SIMPULAN DAN SARAN
Dari uji coba dan pembahasan yang telah
dilakukan dapat ditarik simpulan sebagai
berikut:
1. Berkaitan dengan penggunaan parameter
Algoritma MixCBLOF:
a. Penetapan nilai α dan β yang tepat
diperlukan untuk mendapatkan konsep
klaster besar dan kecil. Hal ini berguna
untuk mendapatkan definisi outlier yang
sesungguhnya sesuai dengan konsep
outlier berbasis klaster. Mengenai
besaran nilai α dan β dapat ditentukan
dengan melihat hasil klasterisasi pada
kedua subset data numerik dan
kategorikal.
b. Operator perkalian menghasilkan rata-
rata coverage lebih baik dibandingkan
dua operator penjumlahan dan
maksimum untuk top ratio sejumlah
outlier eksak.
c. Pembobotan sama (wi=1) menghasilkan
rata-rata coverage lebih baik daripada
pembobotan berdasarkan entropy untuk
top ratio sejumlah outlier eksak.
204 Jurnal Ilmiah KURSOR Vol. 5, No. 3, Januari 2009, hlm.197-204
2. Algoritma MixCBLOF dapat menyelesaikan
masalah deteksi outlier pada set data
dengan atribut campuran dengan baik, yaitu
dengan rata-rata coverage 73.54%. Hasil ini
lebih baik daripada menggunakan metode
diskritisasi atribut numerik yang hanya
mencapai coverage 67.98% dengan
menggunakan metode unsupervised seperti
K-Means dan 59.48% dengan menggunakan
equal width.
Untuk pengembangan lebih lanjut, dapat
dilakukan dengan mencari sebuah metode yang
dapat secara otomatis menentukan parameter
treshold s dan k pada metode klasterisasi. Ide
yang dapat digunakan adalah dengan
mengoptimalkan hasil klasterisasi yang mampu
menghasilkan klaster-klaster besar dan kecil
dengan ukuran yang jauh berbeda.
DAFTAR PUSTAKA
[1] Tan PN, Steinbach M, and Kumar V.
Introduction to Data Mining. Boston:
Pearson Addison Weisley. 2006.
[2] He Z, Deng X, and Xu X. Clustering
Mixed Numeric and Categorical Data: A
Cluster Ensemble Approach. eprint
arXiv:cs/0509011. 2005. URL:
http://arxiv.org/ftp/cs/papers/0509/050901
1.pdf, diakses tanggal 20 November 2009.
[3] Assent I, Krieger R, Muller E, and Seidl
T. Subspace Outlier Mining in Large
Multimedia Databases. Dagstuhl Seminar
Proceedings 07181: Parallel Universes
and Local Patterns. 2007. URL:
http://citeseerx.ist.psu.edu/viewdoc/downl
oad?doi=10.1.1.90.4039&rep=rep1&type
=pdf, diakses tanggal 20 Nopember 2009.
[4] Aggarwal C and Yu P. An Effective and
Efficient Algorithm for High-dimensional
Outlier Detection. VLDB Journal. 14:
211-221. 2005.
[5] Hong Y, Kwong S, Chang Y and Ren Q.
Unsupervised Data Pruning for Clustering
of Noisy Data. Elvesier: Knowledge-
Based System. 21: 612-616. 2008.
[6] He Z, Xu X and Deng S. Discovering
Cluster-based Local Outliers. Pattern
Recognition Letter. 24: 1641-1650. 2003.
[7] Climaco J. Multicriteria analysis. New
York: Springer-Verlag. 1997.
[8] He Z, Xu X and Deng S. Squeezer: An
Efficient Algorithm for Clustering
Categorical Data. Journal of Computer
Science and Technology. 17: 611-624.
2002.
[9] Breunig M M. Kriegel. HP, Ng RT and
Sander J. LOF: Identifying Density-based
Local Outliers. Proceedings of the 2000
ACM SIGMOD International Conference
on Management of Data. 93-104. 2000.
[10] Anonim. CLUTO 2.1.1. Software for
Clustering High-Dimensional Dataset.
URL: http://www.cs.umn.edu/~karpys,
diakses tanggal 20 November 2009.
PEDOMAN BAGI (CALON) PENULIS KURSOR
1. Naskah yang ditulis untuk KURSOR meliputi hasil pemikiran dan hasil penelitian di bidang
Informatika dan Teknologi Informasi. Naskah harus diketik rapi pada kertas A4 sepanjang
maksimum 15 halaman (satu kolom) dan setiap lembar tulisan harus diberi nomor halaman.
Penulisan naskah menggunakan huruf Times New Roman ukuran 12 poin, dengan margin
kanan 2 cm, margin kiri 3 cm, margin atas 2 cm, dan margin bawah 3 cm, serta format dengan
1.5 spasi. Berkas (file) dibuat dengan menggunakan Microsoft Word. Naskah dapat dikirimkan
sewaktu-waktu melalui email ke alamat: [email protected].
2. Naskah ditulis dalam Bahasa Indonesia atau Bahasa Inggris, disertai dengan judul pada
masing-masing bagian naskah. Judul naskah dicetak dengan huruf besar di tengah-tengah,
dengan huruf sebesar 14 poin. Peringkat judul bagian dinyatakan dengan jenis huruf yang
berbeda (semua judul bagian dan sub-bagian dicetak tebal atau tebal dan miring), dan tidak
menggunakan angka nomor pada judul bagian:
PERINGKAT 1 (HURUF BESAR SEMUA, TEBAL, RATA TEPI KIRI)
Peringkat 2 (Huruf Besar Kecil, Tebal, Rata Tepi Kiri)
Peringkat 3 (Huruf Besar Kecil, Tebal-Miring, Rata Tepi Kiri)
3. Sistematika naskah hasil pemikiran adalah: judul yang harus ditulis secara ringkas, tetapi
cukup informatif untuk menggambarkan isi naskah; nama penulis (tanpa gelar akademik);
instansi penulis beserta alamat pos; alamat email; abstrak (150-200 kata); kata kunci (minimal
tiga buah); pendahuluan yang berisi latar belakang dan tujuan atau ruang lingkup tulisan;
bahasan utama (dapat dibagi ke dalam beberapa sub-bagian); penutup atau simpulan; daftar
pustaka (hanya memuat sumber-sumber yang dirujuk).
4. Sistematika naskah hasil penelitian adalah: judul yang harus ditulis secara ringkas, tetapi
cukup informatif untuk menggambarkan isi naskah; nama penulis (tanpa gelar akademik);
instansi penulis beserta alamat pos; alamat email; abstrak (150-200 kata) yang berisi latar
belakang, tujuan, metode, dan hasil penelitian; kata kunci (minimal tiga buah); pendahuluan
yang berisi latar belakang, sedikit tinjauan pustaka, dan tujuan penelitian; metode (dapat terdiri
lebih dari satu buah metode); hasil dan pembahasan; simpulan dan atau saran; daftar pustaka
(hanya memuat sumber-sumber yang dirujuk).
5. Tabel dan gambar harus diberi nomor dan judul lengkap serta harus diacu dalam tulisan.
Contoh: Tabel 1, Tabel 2(a), Gambar 1, Gambar 2(a).
6. Persamaan matematika harus diberi nomor urut dalam kurung biasa dengan penulisan rata
kanan dan harus diacu dalam tulisan.
7. Sumber pustaka/rujukan sedapat mungkin merupakan pustaka-pustaka terbitan 10 tahun
terakhir. Pustaka yang diutamakan adalah sumber-sumber primer berupa laporan penelitian
(termasuk Skripsi/Tugas Akhir, Tesis, Disertasi) atau naskah-naskah penelitian dalam jurnal
dan/atau majalah ilmiah.
8. Daftar Pustaka disusun dengan menggunakan cara penomoran (pemberikan angka) yang
berurutan untuk menunjukkan rujukan pustaka (sitasi). Dalam daftar pustaka, pemunculan
sumber rujukan dilakukan secara berurut menggunakan nomor sesuai kemunculannya sebagai
sitasi dalam naskah tulisan, sehingga memudahkan pembaca untuk menemukannya. Berikut
adalah contoh penulisan daftar pustaka:
Jurnal:
[1] Nama_Belakang_Penulis Singkatan_Nama_Depan_Penulis. Judul_Naskah. Nama_Jurnal.
Volume: Halaman. Tahun.
Contoh:
[1] Priyambodo TK. Infrastruktur Teknologi Informasi dalam Implementasi e-Government.
KURSOR. 1: 9-14. 2005.
Buku:
[2] Nama_Belakang_Penulis Singkatan_Nama_Depan_Penulis. Judul_Buku. Nama_Kota:
Nama_Penerbit. Tahun.
Contoh:
[2] Hoffer JA, George JF and Valacich JS. Modern Systems Analysis and Design 4th Edition.
New Jersey: Pearson Prentice Hall. 2005.
Naskah dari internet:
[3] Nama_Belakang_Penulis Singkatan_Nama_Depan_Penulis. Tahun. Judul_Naskah. URL,
Tanggal_Akses.
Contoh:
[3] Ahmed K and Moore G. An Introduction to Topic Maps. July 2005. URL:
http://msdn2.microsoft.com/en-us/library/aa480048.aspx, diakses tanggal 14 Agustus
2007.
9. Semua naskah ditelaah secara anonim oleh mitra bestari (reviewers) yang ditunjuk oleh redaksi
menurut bidang kepakarannya. Penulis naskah diberi kesempatan untuk melakukan perbaikan
(revisi) naskah atas dasar rekomendasi/saran dari mitra bestari dan redaksi pelaksana.
Kepastian pemuatan atau penolakan naskah akan diberitahukan secara tertulis melalui email.
10. Pemeriksaan dan penyuntingan cetak-coba dikerjakan oleh redaksi dan/atau dengan melibatkan
penulis. Naskah yang sudah dalam bentuk cetak-coba dapat dibatalkan pemuatannya oleh
redaksi jika diketahui bermasalah.
11. Segala sesuatu yang menyangkut perijinan pengutipan atau penggunaan software komputer
untuk pembuatan naskah atau ihwal lain yang terkait dengan HAKI yang dilakukan oleh
penulis naskah, berikut konsekuensi hukum yang mungkin timbul karenanya, menjadi
tanggung jawab penuh penulis naskah tersebut.
12. Penulis yang naskahnya dimuat wajib membayar kontribusi biaya cetak sebesar Rp.
100.000,00 (seratus ribu rupiah) per judul. Sebagai imbalannya, penulis menerima nomor bukti
pemuatan sebanyak 2 (dua) eksemplar dan cetak lepas sebanyak 2 (dua) eksemplar. Naskah
yang tidak dimuat tidak akan dikembalikan, kecuali atas permintaan penulis.