Vol 3, No 3Desember 2013
ISSN 2088-2130
SISTEM DETEKSIRETINOPATI DIABETIKA MENGGUNAKAN SUPPORT VECTOR MACHINE Wahyudi Setiawan1), Fitri Damayanti Manajemen Informatika, Universitas Trunojoyo Jl. Raya Telang PO. BOX 2, Kamal, Bangkalan,Madura 1) email :
[email protected]
Abstrak Retinopati Diabetika adalah efek samping dari Diabetes Mellitus. Hal ini dapat menyebabkan kebutaan jika tidak ditangani sedini mungkin. Sistem yang dibuat dalam penelitian ini adalah deteksi tingkat retinopati diabetik dari gambar yang diperoleh dari foto fundus. Ada tiga langkah utama untuk menyelesaikan masalah, preprocessing, ekstraksi fitur dan klasifikasi. Metode Preprocessing yang digunakan dalam sistem ini adalah Grayscale channel Hijau, Gaussian Filter, Contrast Limited Adaptive Histogram Equalization dan Masking. Two Dimensional Linear Discriminant Analysis (2DLDA) digunakan untuk ekstraksi fitur. Support Vector Machine (SVM) digunakan untuk klasifikasi. Hasil pengujian dilakukan dengan mengambil dataset dari Messidor dengan jumlah Images yang bervariasi untuk tahap pelatihan, citra yang lain digunakan untuk tahap pengujian. Hasil pengujian menunjukkan akurasi yang optimal adalah 84%. Kata kunci: Retinopati Diabetik, Support Vector Machine, Two Dimensional Linear Discriminant Analysis (2DLDA), Messidor Abstract Diabetic Retinopathy is side effect of Diabetes Melitus. It can be a blindness if untreated settled as early as possible. System created in this study is the detection of diabetic retinopathy level of the image obtained from fundus photographs. There are three main steps to resolve the problems, preprocessing, feature extraction and classification. Preprocessing methods that used in this system are Grayscale Green Channel, Gaussian Filter, Contrast Limited Adaptive Histogram Equalization and Masking. Two Dimensional Linear Discriminant Analysis (2DLDA) is used for feature extraction. Support Vector Machine (SVM) is used for classification. The test result performed by taking a dataset of MESSIDOR with number of images that vary for the training phase, otherwise is used for the testing phase. Test result show the optimal accuracy are 84% . Keywords : Diabetic Retinopathy, Support Vector Machine, Two Dimensional Linear Discriminant Analysis, MESSIDOR
170
Vol 3, No 3Desember 2013
PENDAHULUAN Penelitian dan pengembangan aplikasi dengan berbagai metode dalam pencitraan medis telah berkembang sangat luas.Salah satu penelitian dalam pencitraan medisadalah klasifikasi citra retina untuk deteksi penyakit. Pada citra retina dapat dianalisa untuk mendapatkan informasi penting misalnya informasi tentang tingkat resiko penyakit retinopati diabetik. Retinopati diabetika tidak bisa dideteksi langsung secara kasat mata karena tanda-tandanya berada di bagian syaraf retina.Tanda-tanda penyakit ini hanya dapat dilihat menggunakan foto fundus tetapi memerlukan waktu yang relatif lama untuk mengetahui hasilnya.Permasalahan tersebut diselesaikan dengan membangun sebuah sistem yang dapat mendeteksi tingkatresiko retinopati diabetik dengan waktu yang relatif cepat. Sistem deteksi yang dibangun memerlukan sebuah model komputasi untuk mengubah piksel citra retina menjadi suatu ciri retina yang terindikasi retinopati diabetik. Tiga permasalahan utama pada sistem, yaitu prapengolahan, ekstraksi ciri dan teknik klasifikasi. Prapengolahan berfungsi mempersiapkan citra agar dapat menghasilkan ciri yang lebih baik pada tahap berikutnya. Pada tahap ini sinyal informasi ditonjolkan dan sinyal pengganggu (derau) diminimalisasi [1]. Ekstraksi ciri adalah tahapan untuk memunculkan ciri dan mereduksi dimensi citra dari dimensi tinggi ke dimensi lebih rendah.Teknik ekstraksi ciri yang handal merupakan kunci utama dalam penyelesaian masalah pengenalan pola[2]. Proses klasifikasi sama pentingnya dengan proses ekstraksi ciri. Setelah ciri-ciri penting data citra retina yang dihasilkan pada proses ekstraksi ciri, ciri-ciri tersebut nantinya akan digunakan untuk proses klasifikasi. Penelitian ini mengintegrasikan proses prapengolahan, ekstraksi ciri dan klasifikasi. Proses prapengolahan menggunakan metode Grayscale Green Channel, Filter Gaussian, Contrast Limited Adaptive Histogram Equalization (CLAHE), dan Masking. Proses ekstraksi ciri menggunakan metode Two Dimensional Linear Discriminant Analysis (2DLDA), sedangkan proses klasifikasi menggunakan Support Vector Machine (SVM).
dapat berupa kumpulan hasil pengukuran atau pemantauan dan dapat dinyatakan dalam notasi vektor atau matriks [1].Struktur sistem pengenalan pola terdapat pada Gambar 1.
Gambar 1. Struktur sistem pengenalan pola Akuisisi citra Akuisisi citra merupakan cara untuk mendapatkan citra yang akan digunakan dalam proses pengolahan citra. Dalam penelitian ini citra retina yang akan dilatih dan diuji berasal dari foto kamera fundus. Pra-pengolahan Pra-pengolahan bertujuan untuk memperbaiki kualitas citra dengan cara memanipulasi parameter-parameter citra. Dalam penelitian ini, proses pra pengolahan terdiri dari grayscale, filter gaussian, ekualisasi histogram dan masking. Grayscale Citra retina yang diterima adalah citra berwarna, sehingga terlebih dahulu perlu dilakukan proses grayscale untuk mendapatkan citra dengan aras keabuan. Jumlah warna pada citra grey adalah 256, karena citra grey jumlah bitnya adalah 8, sehingga jumlah warnanya adalah 28=256, nilainya berada pada jangkauan 0-255.Untuk mendapatkan citra keabuan digunakan persamaan 1. I ( x, y) .R .G .B …………………(1)
Filter Gaussian Filter Gaussian adalah salah satu filter linier dengan nilai pembobotan untuk setiap anggotanya dipilih berdasarkan bentuk fungsi Gaussian. Filter ini sangat baik untuk menghilangkan derau (noise) yang bersifat sebaran normal. Secara alami derau juga memiliki sebaran Gaussian, sehingga secara teoritis akan menjadi netral jika dilawan dengan fungsi lain yang juga memiliki fungsi Gaussian, hal ini disebut sebagai zero mean. Zero mean dari fungsi Gaussian dengan nilai pembobotan 2 dimensi ditunjukkan pada persamaan 2 [3].
KERANGKA TEORI (
Pengenalan Pola Pengenalan pola adalah suatu ilmu untuk mengklasifikasikan atau menggambarkan sesuatu berdasarkan pengukuran kuantitatif citra atau sifat dari obyek. Pola sendiri merupakan suatu entitas yang terdefinisi, dapat diidentifikasi dan diberi nama. Pola
171
)
…………. (2) dengan k = konstanta normalisasi dan menyatakan standar deviasi dari distribusi. Fungsi diatas diasumsikan memiliki zero mean (pusat distribusi pada garis x=0). Semakin besar nilai maka kurva distribusi Gaussian semakin melebar dan puncaknya
Wahyudi Setiawan dkk,Sistem Deteksi Retinopati...
menurun.Bentuk 2-D dari fungsi gaussian ditunjukkan pada persamaan 3. (
)
Contrast-Limited Adaptive Equalization (CLAHE)
(3)
Histogram
CLAHE dapat digunakan sebagai alternatif pengganti ekualisasi histogram. Ekualisasi histogram bekerja pada seluruh citra, sedangkan CLAHE beroperasi pada daerah kecil di citra yang disebut tile. Setiap tile ditingkatkan nilai kontrasnya, sehingga histogram dari wilayah sekitar cocok untuk histogram tertentu. Setelah melakukan pemerataan, CLAHE menggabungkantile tetangga menggunakan interpolasi bilinier untuk menghilangkan batas-batas artifisial. CLAHE juga dapat digunakan untuk menghindari noise yang ada pada citra dengan membatasi kontras pada daerah homogen. CLAHE menghasilkan output citra yang memiliki nilai merata di seluruh bagian citra [4].
dimana menunjukkan tensor product, L menjangkau {u1,…,u 1 } dan R menjangkau {v1,..,v
2 }, sehingga didefinisikan dua matriks L = [u1,…,u 1 ] dan R = [v1,..,v 2 ] [5]. Metode ekstraksi ciri adalah untuk menemukan L dan R sehingga ruang citra asli (original image space) Ai dirubah kedalam ruang citra dimensi rendah (low-dimensional image) menjadi Bi=LTAiR. Ruang dimensi rendah (low-dimensional space) diperoleh dengan transformasi linier L dan R, jarak between-class Db dan jarak within-class Dw didefinisikan sebagai berikut : k
Db= ni LT ( M i M ) R i 1
k
Dw=
Two-Dimensional Linear Discriminant Analysis(2DLDA) 2DLDA adalah pengembangan dari metode LDA. Didalam LDA pada pengenalan citra dengan matrik 2D terlebih dahulu ditransformasikan kedalam bentuk citra vektor satu dimensi. Sedangkan pada 2DLDA atau disebut teknik proyeksi citra secara langsung, matriks citra 2D tidak perlu ditransformasikan kedalam bentuk citra vektor namun secara langsung matriks scatter citranya dapat dibentuk langsung dengan menggunakan matriks citra aslinya. 2DLDA adalah pengembangan dari metode LDA. Didalam LDA pada pengenalan citra dengan matrik 2D terlebih dahulu ditransformasikan kedalam bentuk citra vektor satu dimensi. Sedangkan pada 2DLDA atau disebut teknik proyeksi citra secara langsung, matriks citra 2D tidak perlu ditransformasikan kedalam bentuk citra vektor namun secara langsung matriks scatter citranya dapat dibentuk langsung dengan menggunakan matriks citra aslinya. {A1,….,An} adalah n matriks citra, dimana Ai (i=1,…,k) adalah r x c matriks. Mi (i=1,…,k) adalah rata-rata citra pelatihan dari kelas ke i dan M adalah rata-rata citra dari semua data pelatihan. 1 x 2
adalah ruang dimensi (dimensional space) L R,
L
T
i 1 x i
dimana Masking Citra hasil segmentasi diberikan masking agar nantinya background hitam pada citra retina, tidak dihitung sebagai obyek. Operator AND digunakan untuk mendapatkan citra hasil operasi dari dua citra yang berbeda.
2 F
F
( X M i )R
………(4)
2 F
(5)
……….
merupakan Frobenius norm.
Meninjau bahwa
A
2 F
= Ptrace(ATA) =
trace(AAT) untuk matriks A. Sedemikian sehingga persamaan (4) dan (5) dapat direpresentasikan lebih lanjut. k
D b = trace ( ni LT ( M i M ) RR T ( M i M ) T L) i 1
(6) …..
k
Dw trace( LT ( X M i ) RR T ( X M i ) T L). (7) i 1 x i
Sama halnya dengan LDA, metode 2DLDA adalah untuk menemukan matriks L dan R, sedemikian hingga struktur kelas dari ruang orisinil tetap didalam ruang proyeksi, sehingga patokan (criterion) dapat didefinisikan sebagai: J(L,R)=max
Db . DW
(8)
Hal tersebut jelas bahwa persamaan (8) terdiri dari matriks transformasi L dan R. Matriks transformasi optimal L dan R dapat diperoleh dengan memaksimalkan Db dan meminimumkan Dw. Bagaimanapun, sangat 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 sebagai berikut :
172
Vol 3, No 3Desember 2013
J2(L)=maxtrace((LTS WR L)-1(LTS bR L)) ………… (9) dimana k
S bR = ni (M i M ) RR T (M i M ) T i 1
(10)
……….
k
S WR = ( X M i ) RR T ( X M i )T
(11)
i 1 x i
Dengan catatan bahwa ukuran matriks S WR dan S R b
adalah r x r yang lebih kecil daripada ukuran matriks Sw dan Sb pada LDA klasik. Untuk sebuah L yang pasti, R dapat diperoleh dengan menyelesaikan fungsi optimasi sebagai berikut : J3(R)=maxtrace((R
S WL
T
-1
R) (R
S bL
T
R))
(12)
k
n (M i 1
i
i
M ) T LLT ( M i M )
(13)
dan k
S WL = ( X M i )T LLT ( X M i )
(14)
i 1 x i
Support Vector Machine (SVM) Konsep SVM dapat dijelaskan secara sederhana sebagai usaha mencari hyperplane terbaik yang berfungsi sebagai pemisah dua buah class pada input space. Hyperplane dalam ruang vector berdimensi d adalah affine subspace berdimensi d-1 yang membagi ruang vector tersebut ke dalam dua bagian, yang masing-masing berkorespondensi pada class yang berbeda. Hyperplane pemisah terbaik antara kedua kelas dapat ditemukan dengan mengukur margin hyperplane tersebut.dan mencari titik maksimalnya. Margin adalah jarak antara hyperplane tersebut dengan pattern terdekat dari masing-masing kelas. Pattern yang paling dekat ini disebut sebagai support vector.Garis solid pada Gambar 2.2 menunjukkan hyperplane yang terbaik, yaitu yang terletak tepat pada tengah-tengah kedua kelas, sedangkan titik merah dan kuning yang berada dalam lingkaran hitam adalah support vector. Usaha untuk mencari lokasi hyperplane ini merupakan inti dari proses pembelajaran pada SVM.
173
Data
xi d , dinotasikan
yang
tersedia
sedangkan
dinotasikan label
sebagai
masing-masing
yi 1,1 untuk i=1,2,3 …. l. Yang
mana l adalah banyaknya data. Diasumsikan kedua class –1 dan +1 dapat terpisah secara sempurna oleh hyperplane berdimensi d. yang didefinisikan
w x b 0
dimana S bL =
Gambar 2 SVM berusaha menemukan hyperplane terbaik yang memisahkan kedua class –1 dan +1
(15)
Pattern w yang termasuk class –1 (sampel negatif) dapat dirumuskan sebagai pattern yang memenuhi pertidaksamaan
w x b 1 Sedangkan pattern positif)
w
(16) yang termasuk class +1 (sampel
w x b 1
(17)
Margin terbesar dapat ditemukan denganmemaksimalkan nilai jarak antara hyperplane dan titik terdekatnya, yaitu
1 . Hal ini dapat w
dirumuskan sebagai Quadratic Programming (QP) problem, yaitu mencari titik minimal persamaan (16), dengan memperhatikan constraint persamaan (17). 1 2 (18) ( w) w min w 2
yi xi w b 1 0, i
(19)
Problem ini dapat dipecahkan dengan berbagai teknik komputasi, di antaranya Lagrange Multiplier.
1 2 l Lw, b, w i ( yi ( xi w b) 1)) (20) 2 i 1 dengan i = 1, 2, …, l . αi adalah Lagrange multipliers, yang bernilai nol atau positif ( αi≥0 ). Nilai optimal dari persamaan (20) dapat dihitung dengan meminimalkan L terhadap w dan b, dan memaksimalkan L terhadap αi. Dengan
Wahyudi Setiawan dkk,Sistem Deteksi Retinopati... memperhatikan sifat bahwa pada titik optimal gradient L =0, persamaan (20) dapat dimodifikasisebagai maksimalisasi problem yang hanya mengandung saja αi, sebagaimana persamaan (21). l
i i 1
1 l i j yi y j xi x j 2 i ,i 1
dimana
i 0 (i 1,2,..., l )
(21) l
y i 1
i
i
0 (22)
Dari hasil dari perhitungan ini diperoleh αi yang kebanyakan bernilai positif. Data yang berkorelasi dengan αi yang positif inilah yang disebut sebagai support vector [6]. METODOLOGI
Desain Sistem Sistem klasifikasi retina meliputi tahap pelatihan dan pengujian. Tahap pelatihan dimulai dengan menginputkan citra retina, selanjutnya pada citra akan dilakukan proses pra-pengolahan. Citra diubah terlebih dahulu kedalam format grayscale green channel, selanjutnya dilakukan operasi filter Gaussian untuk menghilangkan noise.Proses selanjutnya dilakukan ekualisasi histogram untuk mengubah sebaran tingkat keabuan citra, menggunakan Contrast Limited Adaptive Histogram Equalization (CLAAHE). Selanjutnya citra akan dilakukan operasi masking untuk memisahkan obyek dengan background. Ekstraksi ciri pada proses pelatihan dilakukan dengan menggunakan metode 2DLDA. Tahap ini bertujuan untuk mendapatkan ciri-ciri yang terpilih dari masukkan data-data pelatihan. Ciri-ciri yang terpilih nantinya digunakan untukproses klasifikasi pelatihan dan digunakan untuk ekstraksi ciri data pengujian. Ekstraksi ciri pada proses pengujian dilakukan dengan mengambil hasil ekstraksi ciri pada proses pelatihan diterapkan pada data pengujian. Hasil ekstraksi ciri pada data pengujian ini nantinya digunakan sebagai inputan pada proses klasifikasi pengujian. Proses klasifikasi pelatihan dilakukan setelah data-data pelatihan diambil ciri-ciri khusus, ciri-ciri khusus ini berupa vektor ciri yang dimensinya lebih kecil. Dalam penelitian ini menggunakan SVM multiclass One Against All 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 input, menggunakanquadratic programming.
Pada proses klasifikasi pengujian menggunakan hasil ekstraksi ciri 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 retina yang sesuai dengan nilai indeks dari fungsi keputusan yang terbesar hasil dari proses klasifikasi pengujian. Pada Gambar 3.1 merupakan tahapan proses sistem deteksi retinopati diabetik. Pada proses pelatihan terdapat metode 2DLDA yang digunakan untuk mengekstraksi ciri, ciri-ciri yang terpilih pada saat proses pelatihan digunakan dalam proses klasifikasi dan juga digunakan untuk mengekstraksi ciri pada data uji coba. Masing-masing dataset citra retina yang digunakan dibagi menjadi dua, sebagian digunakan untuk proses pelatihan (training) dan sisanya digunakan untuk proses pengujian (testing).
Desain Algoritma Desain Algoritma 2DLDA Desain algoritma 2DLDA dibagi menjadi dua subsistem yaitu subsistem pelatihan dan subsistem pengujian.Berikut ini adalah penjabaran masingmasing subsistem. Proses Pelatihan 2DLDA Untuk proses pelatihan 2DLDA dibagi menjadi tiga tahapan, yaitu : tahap pertama menghitung nilai rata-rata kelas dan rata-rata global, tahap kedua menghitung matriks within class scatter dan matriks between class scatter, dan tahap terakhir menghitung matriks ciri ekstraksi data-data pelatihan.
Algoritma 2DLDA Inputannya adalah matriks data pelatihan, pada matriks data pelatihan tidak ditransformasikan kedalam vektor tetapi tetap berupa matriks. Inputan lainnya adalah jumlah kelas (k), jumlah data perkelas (ni), dan n (banyaknya data pelatihan). 1. Jika dalam suatu dataset citra retina terdapat himpunan sebanyak n citra pelatihan Ai = [A1,A2,…,An] (i = 1,2,…,n) dengan dimensi citra (r x c), maka himpunan total matriks dari semua citra tersebut adalah :
A( n )11 A ( n ) 21 An= ... A( n ) r1
A( n )12 ... A( n )1c A( n ) 22 ... A( n ) 2c . ... ... ... A( n ) r 2 ... A( n ) rc
Matriks ini digunakan sebagai data inputan. Data inputan lainnya adalah jumlah kelas (k), jumlah
174
Vol 3, No 3Desember 2013
data perkelas (ni), dan banyaknya data pelatihan (n). 2. Tahapan berikutnya adalah menghitung rata-rata citra pelatihan dari kelas ke i:
Mi
1 ni
X i
X.
ukuran matriksnya (c x c). Ukuranmatriks S bL lebih kecil dari ukuran matriks Sb pada LDA klasik (Dimensi x Dimensi). 11. Menghitung matriks within class scatter L sesuai dengan persamaan
3. Menghitung rata-rata semua citra pelatihan : M=
1 n
k
k
i 1
X i
X .
S WL =
4. Menentukan nilai 1 (dimensi proyeksi baris) dan
2 (dimensi proyeksi kolom). Nilai 1 ≤ r dan 2 ≤ c. 5. Menetapkan matriks transformasi R ukuran (c, 2 ) yang diperoleh dari gabungan antara matriks identitas ukuran ( 2 , 2 ) dengan matriks nol ukuran (c- 2 , 2 ). 6. Menghitung matriks between class scatterR sesuai dengan persamaan S bR =
k
n (M i
i 1
i
M ) RR T ( M i M ) T , ukuran
matriksnya (r x r). Ukuranmatriks S bR lebih kecil dari ukuran matriks Sb pada LDA klasik (Dimensi x Dimensi). 7.
Menghitung matriks within class scatterR sesuai dengan persamaan k
S WR
=
i 1 x i
( X M i ) RR T ( X M i ) T ,
ukuran matriksnya (r x r). Ukuranmatriks S WR lebih kecil dari ukuran matriks Sw pada LDA klasik (Dimensi x Dimensi). 8. Hitung generalized eigenvalue ( i ) dari S bR dan S R W
sesuai dengan persamaan (17).
J1(L)=maxtrace((LTS WR L)-1(LTS bR L)), ukuran matriksnya (r x r). 9. Ambil sebanyak 1 eigenvector terbesar dari langkah 5 sebagai matriks transformasi baris (L). L
L ], ukuran matriksnya (r x 1 ).
= [ 1 , ..., L
1
10. Menghitung matriks between class scatter L sesuai dengan persamaan k
S bL =
n (M i 1
175
i
i
M ) T LLT ( M i M ) ,
i 1 x i
( X M i ) T LLT ( X M i ),
ukuran matriksnya (c x c). Ukuranmatriks S WL lebih kecil dari ukuran matriks Sw pada LDA klasik (Dimensi x Dimensi) 12. Hitung generalized eigenvalue ( i ) dari S bL dan S L W
sesuai dengan persamaan (9).
J2(R)=maxtrace((RTS WL R)-1(RTS bL R)), ukuranmatriksnya (c x c). 13. Ambil sebanyak 2 eigenvector terbesar dari langkah 9 sebagai matriks transformasi kolom (R). R = [ 1 , ..., R
R ], ukuran matriksnya (c x 2 ). 2
14. Hitung matriks ciri ekstraksi adalah Bi=LTAiR , ukuran matriksnya ( 1 x 2 ). 15. Output : matriks ciri ektraksi Bi, matriks transformasi baris L, dan matriks transformasi kolom R. Desain Algoritma SVM Pengklasifikasi SVM untuk multiclassOne Against All akan membangun sejumlah k SVM biner (k adalah jumlah kelas). Fungsi keputusan yang mempunyai nilai maksimal, menunjukkan bahwa data xd merupakan anggota dari kelas fungsi keputusan tersebut. Pengklasifikasian dengan SVM dibagi menjadi dua proses, yaitu proses pelatihan dan pengujian. Pada proses pelatihan SVM menggunakan matriks ciri yang dihasilkan pada proses ekstraksi ciri pelatihan sebagai input. Sedangkan pada pengujian SVM memanfaatkan matriks ciri yang dihasilkan pada proses ekstraksi ciri pengujian sebagai input [7].
Wahyudi Setiawan dkk,Sistem Deteksi Retinopati...
Prapengolahan
Citra Asli
Grayscale biasa
Grayscale
Red Channel
Filter Gaussian
Green Channel
Blue Channel
Histogram
Ekualisasi Histogram
Tahap Pelatihan
Masking
Resize 112x92
CLAHE
Tahap Pengujian
input dataset pelatihan
input data pengujian
Ekstraksi ciri 2DLDA Tahap Pengujian
Ekstraksi ciri 2DLDA Tahap pelatihan
Klasifikasi Support Vector Machine Multiclass One Againts All Tahap Pengujian
Klasifikasi Support Vector Machine Multiclass One Againts All Tahap Pelatihan
Data Hyperplane
Hasil klasifikasi
Gambar 3. Tahapan Proses Sistem Deteksi Retinopati Diabetik
Proses Pelatihan SVM Algoritma pelatihan untuk masing-masing pengklasifikasi SVM biner dapat dituliskan sebagai berikut : input berupa matriks B (matriks hasil ektraksi ciri pelatihan) dan vektor Y sebagai pasangan input-target dan outputnya adalah w, x, b (variable - variabel persamaan hyperplane). Langkah – langkahnya dijelaskan sebagai berikut : 1.
Tentukan Input (Z =B) dan Target (Y) sebagai pasangan pelatihan dari dua kelas.
2.
2 Hitung Kernel Gaussian K(Z,Zi) = exp ( | Z Z i | ) (2 2 )
3.
Hitung Matriks Hessian H = K(Z,Zi) * Y * YT.
4.
Tetapkan c dan epsilon.
5.
Tetapkan vektor e sebagai vektor satuan yang memiliki dimensi sama dengan dimensi Y.
6.
Hitung solusi quadratic programming: min L( ) 1 T H e T , 2
176
dimana y T 0 dan 0 c.
alir untuk algoritma pelatihan SVM Gambar 3.6.
Input matriks Z merupakan matriks ciri yang dihasilkan pada proses ekstraksi ciri dan vektor Y sebagai target. Contoh untuk Dataset MESSIDOR yang terdiri dari 5 kelas, maka jika digunakan sepuluh sampel tiap kelas dan dimensi proyeksi baris 1 = 10, dimensi proyeksi kolom
2 = 10, maka matriks Z yang dihasilkan adalah matriks ciri dengan dimensi 50 x 100 (50 didapat dari jumlah sampel tiap kelas dikalikan dengan banyaknya kelas, 100 didapat dari perkalian dimensi proyeksi baris dengan dimensi proyeksi kolom). Vektor Y merupakan vektor kolom untuk pengklasifikasi pertama dimana semua citra retina dari kelas pertama akan disimbolkan dengan angka 1, semua citra retina dari kelas lainnya dengan angka -1. Vektor Y untuk pengklasifikasi kedua semua citra retina dari kelas kedua disimbolkan dengan 1 dan semua citra retina bukan kelas kedua disimbolkan dengan -1, demikian seterusnya untuk pengklasifikasi ketiga sampai ke k. Pada penelitian ini, digunakan fungsi kernel gaussian dengan nilai varian (σ) = 1. Langkah selanjutnya adalah menghitung matriks Hessian, yaitu perkalian antara kernel gaussian dengan Y. Y disini adalah berupa vector yang berisi nilai 1 dan -1. Dari contoh di atas jika classifier pertama yang dilatih, maka nilai Y untuk 10 elemen pertama (jika digunakan 10 sampel citra retina per kelas) akan bernilai 1 dan elemen lainnya bernilai -1. Jika classifier kedua dilatih, maka elemen 11, sampai dengan 20 bernilai 1, sedangkan sisanya bernilai -1. Matriks Hessian ini nantinya digunakan sebagai variabel input dalam quadratic programming. Fungsi quadratic programming monqp memerlukan variabel c dan epsilon. Untuk itu tetapkan nilai c dan epsilon (c adalah batas atas nilai αi ) dari C-SVM. Vektor satuan e juga dibentuk dengan dimensi sama dengan vektor Y. Penyelesaian min L( ) 1 T H e T dengan 2 quadratic programming, merupakan implementasi dari
1 2 n w C i . 2 i 1 Jika diimplementasikan dalam bentuk matriks menjadi 1 n min wT w C i , dengan yi T (wT ( xi )) b) 1 i 2 i 1 . Jika formula dalam bentuk matriks tersebut diubah ke bentuk dual problem, maka formula tersebut menjadi min 1 T L( ) T H e T , dimana y 0 dan 0 C . 2 pencarian solusi atas permasalahan min
Disini H yi y j K ( xi , x j ) , dan K(xi,xj) = exp ( | xi x j | ) (2 2 ) adalah fungsi kernelnya, dan e adalah vektor satuan yang dimensi sama dengan Y , sedangkan c> 0 adalah batas atas dari nilai α Dalam penelitian ini digunakan nilai c = 1000 dan epsilon = 1x10-7. Hasil dari fungsi monqp (quadratic programming) adalah nilai variable w, x, dan b yang nantinya akan digunakan untuk proses pengujian. Diagram 2
177
dapat dilihat pada
Proses Pengujian SVM Setelah pada proses pelatihan didapat nilai variabel w, x, dan b untuk masing - masing kelas. Nilai variabel w, x, dan b untuk didefinisikan sebagai vektor w, x, dan b. Untuk input data yang akan diklasifikasikan adalah matriks ciri Dyang dihasilkan pada proses ekstraksi ciri pengujian. Matriks ciri D tersebut ditransformasikan dulu kedalam bentuk vektor menjadi 1 x ( 1 x 2 ) diberi nama T. Langkah – langkahnya sebagai berikut : 1.
Input : vektor T (data pengujian), vektor w, x, b, dan k (jumlah kelas).
2.
2 Hitung Kernel Gaussian K(T,xi) = exp ( | T xi | ) . 2 (2 )
3.
Hitung f i K (T , xi )wi bi .
4.
Ulangi langkah 2 dan 3 untuk i = 2 sampai k.
5.
Tentukan nilai
f i yang paling maksimal.
6.
Kelas i dengan
f i terbesar adalah kelas dari vektor T.
Nilai T adalah transformasi matriks ciri D kedalam bentuk vektor. Langkah selanjutnya adalah dengan menghitung Kernel Gaussian K (T , xi ) , dengan T adalah data input dan xi adalah support vector yang dihasilkan pada proses pelatihan SVM. Fungsi keputusan f i K (T , xi )wi bi dihitung untuk masing-masing nilai i. dimana i = 1 sampai k (k adalah jumlah kelas). Output dari algoritma ini berupa indeks i dengan f i terbesar yang merupakan kelas dari vektor T. Diagram alir untuk algoritma pengujian dapat dilihat pada Gambar 3.7. Dari proses pelatihan dan pengujian SVM dapat diringkas dalam bentuk blok diagram proses pelatihan dan pengujian yang ditunjukkan pada Gambar 3.8. Gambar 3.8 menjelaskan secara garis besar proses pelatihan dan pengujian pada SVM. Data pelatihan yang sudah diproyeksikan oleh 2DLDA, selanjutnya menjadi data pelatihan SVM. Jika sebaran data yang dihasilkan pada proses 2DLDA mempunyai distribusi yang tidak linier, maka salah satu metode yang digunakan SVM untuk mengklasifikasikan data tersebut adalah dengan mentransformasikan data ke dalam dimensi ruang ciri (feature space), sehingga dapat dipisahkan secara linier pada feature space. Karena feature space dalam prakteknya biasanya memiliki dimensi yang lebih tinggi dari vektor input (input space). Hal ini mengakibatkan komputasi pada feature space mungkin sangat besar, karena ada kemungkinan feature space dapat memiliki jumlah feature yang tidak terhingga. Maka pada SVM digunakan ”kernel trick”.Fungsi kernel yang digunakan pada penelitian ini adalah Gaussian
Vol 3, No 3Desember 2013 K(x,y)=exp ( | x y | ) . (2 2 ) 2
(23)
Sejumlah support vector pada setiap data pelatihan harus dicari untuk mendapatkan solusi bidang pemisah terbaik. Persoalan solusi bidang pemisah terbaik dapat dirumuskan : l
Q( ) i i 1
1 l i j yi y j xi x j 2 i ,i 1
dimana : i 0 (i 1,2,..., l )
l
y i 1
i
i
,(24)
0.
DAFTAR PUSTAKA [1]
[2]
[3]
Data xi 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 w =Σαiyixi; b = yk- wTxk untuk setiap xk , dengan αk0. 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 adalah f i K ( xi , xd )wi bi
Dari hasil uji coba menggunakan metode 2DLDA SVM didapatkan tingkat akurasi pengenalan optimal 84%.
[4]
[5]
[6]
[7] (25)
Putra, D., Suarjana, I.G., 2010. Segmentasi citra retina digital retinopati diabetes untuk membantu pendeteksian mikroaneurisma.Jurnal teknologi teknik elektro vol 9 no 1. Purnomo, M.H., Muntasa, A., 2010. Konsep Pengolahan Citra Digital dan Ekstraksi Ciri. Graha Ilmu, Yogyakarta Ahmad, U., 2005. Pengolahan Citra Digital dan Teknik Pemrogramannya, Graha Ilmu, Yogyakarta. Zuiderveld,K.,1994. Contrast Limited AdaptiveHistograph Equalization. Graphic Gems IV. Academic Press Professional, San Diego. Liang, Z., Li, Y.,Shi, P., 2008.“A note on twodimensional linear discriminant analysis”, Pattern Recognition. 2122-2128. Nugroho, A.S., Witarto, A. B., Handoko,D., 2003. Support Vector Machine Teori dan aplikasinya dalam Bioinformatika, Kuliah umum Ilmu Komputer.com, website : http://ilmukomputer.com, diakses 20 Desember 2011. Damayanti, F., Arifin, A.Z., Soelaiman, R., 2010. Pengenalan citra wajah menggunakan support vector machine. KURSOR Vol. 5, No. 3, 147-156.
dimana : i = 1 sampai k; xi = support vector; xd = data pengujian. Outputnya adalah berupa indeks i dengan fi terbesar yang merupakan kelas dari data pengujian [7].
HASIL DAN PEMBAHASAN Tahapan pengujian terhadap sistem dilakukan dengan variasi data pelatihan dan variasi dimensi proyeksi. Hal ini dilakukan untuk mengetahui keakuratan dari sistem yang dibuat. Dataset yang digunakan adalah MESSIDOR, terdiri dari 125 citra retina, dibagi menjadi5 kelas, masing-masing kelas terdiri dari 25 citra. Dimensi proyeksi menggunakan nilai p dari 10 sampai dengan 20, nilai q dari 10 sampai dengan 20. Hasil pengujian ditunjukkan pada Tabel 4.1 Tabel 1. Tingkat keberhasilan pengenalan dataset MESSIDORmetode 2DLDA – SVM Jumlah data Akurasi Jumlah data latih uji optimal 50 25 72% 75 25 64% 100 25 84%
KESIMPULAN Terdapat dua variabel penting yang mempengaruhi tingkat keberhasilan pengenalan, yaitu variasi urutan dari sampel pelatihan per kelas yang digunakan dan jumlah sampel pelatihan per kelas yang digunakan.
178
