PERBANDINGAN KINERJA EUCLIDEAN DAN MAHALANOBIS DISTANCE CLASSIFIER UNTUK KLASIFIKASI CITRA MAMOGRAFI Oleh: Indah Susilawati Staf Pengajar Program Studi Teknik Informatika Universitas Mercu Buana Yogyakarta Jl. Wates Km. 10 Yogyakarta Telp. (0274) 6498211, 6498212 Fax. (0274) 6498213 email:
[email protected] Abstrak Terdapat beberapa jenis abnormalitas pada jaringan payudara yang dapat diketahui dengan cara analisis citra rekam medis mamografi. Salah satu jenis abnormalitas tersebut adalah keberadaan mikrokalsifikasi pada jaringan payudara. Mikrokalsifikasi merupakan timbunan kalsium pada jaringan dan dapat merupakan gejala awal perubahan ke arah kanker. Berbagai algoritma yang kompleks telah digunakan oleh para peneliti untuk mengklasifikasikan citra mamografi untuk mengenali keberadaan mikrokalsifikasi. Algoritma yang sering digunakan misalnya jaringan saraf tiruan, Support Vector Machine, dan lain-lain. Tujuan utama penelitian ini adalah melakukan pengenalan pola citra normal dan citra bermikrokalsifikasi pada citra mamografi digital menggunakan pengklasifikasi berdasarkan teori Bayes, yaitu Euclidean dan Mahalanobis Classifier, kemudian membandingkan kinerja yang diperoleh. Dalam penelitian ini, pengenalan citra normal dan citra bermikrokalsifikasi pada citra mamografi digital dirancang sebagai suatu proses klasifikasi dengan 6 input ciri. Proses klasifikasi dilakukan dalam tiga tahap. Pertama, tahap pra-pengolahan, dan kedua tahap ekstraksi ciri-ciri citra berdasarkan nilai piksel citra. Ketiga, dilakukan klasifikasi untuk mengelompokkan citra normal dan citra bermikrokalsifikasi. Penelitian menggunakan total 140 sampel; 100 sampel untuk pelatihan dan 40 sampel untuk pengujian yang terdiri atas 20 citra normal dan 20 citra bermikrokalsifikasi. Hasil penelitian menunjukkan bahwa Euclidean Distance Classifier menghasilkan kinerja klasifikasi setinggi 52,5% dan error sebesar 47,5%, sedangkan Mahalanobis Distance Classifier menghasilkan kinerja klasifikasi setinggi 87,5% dan error sebesar 12,5%; atau dikatakan terjadi peningkatan kinerja dan penurunan tingkat error sebesar 35% saat digunakan Mahalanobis Distance Classifier. Kata kunci: mamografi, mikrokalsifikasi, Euclidean, Mahalanobis, ciri. 1. Pendahuluan Mamografi adalah pencitraan menggunakan sinar X untuk pengujian (examination) jaringan payudara. Mamografi terutama digunakan untuk deteksi dan diagnosa kanker payudara, juga digunakan untuk keperluan pra-operasi, yaitu untuk menentukan lokasi yang dicurigai dan untuk mengarahkan biopsi. Saat ini mamografi merupakan cara paling efektif untuk mendeteksi kanker payudara stadium dini. Hal ini dapat dilakukan baik untuk pasien yang memiliki gejala-gejala kanker (symptomatic patient) maupun untuk skrining bagi wanita-wanita tanpa gejala kanker (asymptomatic patient). Kanker payudara dideteksi berdasar empat tipe tanda-tanda pada citra mamografi, yaitu: 1. Karakteristik morfologi massa tumor, 2. Keberadaan deposit atau timbunan kalsium pada jaringan payudara dan biasanya menjadi tandatanda awal perubahan ke arah kanker yang disebut mikrokalsifikasi, 3. Distorsi arsitektur dari pola jaringan normal yang disebabkan oleh kanker, dan 4. Asimetri antara citra payudara kanan dan kiri. Berbagai algoritma yang kompleks telah digunakan oleh para peneliti untuk mengklasifikasikan
citra mamografi untuk mengenali beberapa jenis abnormalitas yang mungkin terjadi pada jaringan payudara seperti mikrokalsifikasi, massa, dan lessi. Algoritma yang sering digunakan misalnya jaringan saraf tiruan dan Support Vector Machine. Pada penelitian ini dilakukan klasifikasi citra mamografi menjadi dua kelas, yaitu citra normal dan citra bermikrokalsifikasi (citra yang mengandung mikrokalsifikasi). Pengklasifikasi (classifier) yang digunakan adalah pengklasifikasi berdasar jarak minimum yaitu Euclidean dan Mahalanobis Distance Classifier. Euclidean Distance Classifier adalah pengklasifikasi berdasar jarak euclidean minimum dengan beberapa asumsi sebagai berikut: 1. Semua kelas mempunyai probabilitas yang sama (equiprobable), 2. Semua data dalam semua kelas mempunyai distribusi normal atau Gaussian, 3. Semua kelas mempunyai matriks kovarian yang sama, 4. Matriks kovarian berbentuk matriks diagonal dan semua elemen diagonalnya sama besar, yaitu S = 2 I dengan I adalah matriks identitas. Sedangkan Mahalanobis Distance Classifier adalah pengklasifikasi berdasar jarak minimum untuk kondisi dimana asumsi terakhir pada Euclidean Distance Classifier tidak terpenuhi atau dengan kata lain matriks kovarian tidak
berbentuk matriks diagonal dan semua elemen diagonalnya tidak sama besar. Asumsi-asumsi yang digunakan oleh dua pengklasifikasi ini menjadikan algoritma implementasinya tidak rumit sebagaimana pengklasifikasi jenis lain, seperti jaringan saraf tiruan dan Support Vector Machine. Pada penelitian ini akan dibandingkan kinerja Euclidean dan Mahalanobis Distance Classifier dalam mengklasifikasikan citra mamografi menjadi dua kelas, yaitu citra normal dan citra bermikrokalsifikasi. Dengan demikian pada akhirnya dapat diketahui jenis pengklasifikasi yang mempunyai kinerja yang lebih baik diantara keduanya untuk selanjutnya dapat digunakan dalam proses deteksi mikrokalsifikasi pada citra mamografi.
bermikrokalsifikasi dilakukan dengan memilih posisi dimana terdapat mikrokalsifikasi sesuai informasi dari basis data MIAS. Gambar 2 memperlihatkan proses cropping untuk memperoleh citra sampel.
2. Metode Penelitian 2.1. Bahan Penelitian Bahan penelitian diperoleh dari basis data MIAS (Mammographic Image Analysis Society). Citra yang tersedia berupa citra aras keabuan 8 bit berukuran 1024 x 1024 piksel dengan ukuran piksel 200 mikron. 2.2. Metodologi Langkah-langkah yang dilakukan dalam penelitian ini diperlihatkan dengan diagram alir pada Gambar 1. Mulai
Citra mamografi
Pra-pengolahan
Gambar 2. Cropping untuk memperoleh citra sampel Pada penelitian ini digunakan total 140 sampel yang terdiri atas 70 sampel citra mamografi normal (50 sampel untuk pelatihan dan 20 sampel untuk pengujian) dan 70 citra mamografi bermikrokalsifikasi (50 sampel untuk pelatihan dan 20 sampel untuk pengujian). Selanjutnya dilakukan ekstraksi ciri dari semua citra sampel. Ada enam ciri yang diekstrak yaitu rerata, varians, standar deviasi (std), entropi, beda nilai maksimum dan minimum piksel (bedaan1), serta beda nilai maksimum piksel dari reratanya (bedaan2). Ekstraksi dilakukan menggunakan persamaan-persamaan berikut.
Ekstraksi Ciri
rerata Klasifikasi
Analisis Hasil dan Perbandingan
1 N
u(m, n)
1 [u(m, n) rerata]2 N 1 standar deviasi [u(m, n) rerata]2 N varians
(1) (2) (3)
L 1
entropi E[ log 2 pu ] pu ( x) log 2 pu ( x)
(4)
x 0
Selesai
Gambar 1. Diagram alir langkah penelitian Pada tahap pra-pengolahan dilakukan cropping citra mamografi untuk memperoleh sampel citra normal dan sampel citra bermikrokalsifikasi dengan ukuran sampel 40x40 piksel. Sampling untuk memperoleh citra normal dilakukan dengan mengambil sampel secara acak pada citra mamografi normal. Sedangkan untuk memperoleh sampel citra
bedaan1 max[ u(m, n)] min[u(m, n)] (5) bedaan2 max[ u(m, n)] rerata (6) dengan u(m,n) adalah nilai piksel citra pada baris ke-m kolom ke-n, N adalah jumlah piksel dalam citra yang bersangkutan, pu(x) adalah probabilitas kemunculan nilai piksel sama dengan x atau u(m,n) = x. Gambar 3 memperlihatkan diagram alir proses ekstraksi ciri. Pada tahap klasifikasi dilakukan klasifikasi untuk membedakan citra normal dan citra bermikrokalsifikasi. Citra normal dikelompokkan dalam kelas 1 dan citra
bermikrokalsifikasi dikelompokkan dalam kelas 2. Pada penelitian ini digunakan dua jenis pengklasifikasi berdasarkan jarak minimum, yaitu Euclidean dan Mahalanobis Distance Classifier.
1,2,…,N, maka nilai rerata (m) dan matriks kovarian (S) dapat dicari dengan
mML
S ML
Mulai
1 N
N
x i 1
(9)
i
1 N ( xi mML )( xi mML ) T N i 1
(10)
Kinerja yang dicapai oleh masing-masing pengklasifikasi kemudian akan dibandingkan.
Baca Citra
3. Hasil dan Pembahasan 3.1 Hasil Penelitian Gambar 4 memperlihatkan hasil pra-pengolahan berupa sampel citra normal (kelas 1) dan Gambar 5 memperlihatkan sampel citra bermikrokalsifikasi (kelas 2).
Vektorisasi
Hitung rerata, varians, std, entropi, bedaan1, bedaan2
Susun vektor ciri
Gambar 4. Hasil sampling citra normal Selesai
Gambar 3. Diagram alir proses ekstraksi ciri
Gambar 5. Hasil sampling citra bermikrokalsifikasi
Euclidean dan Mahalanobis Distance Classifier merupakan jenis pengklasifikasi yang bekerja berdasar jarak minimum, dengan beberapa asumsi untuk kepentingan penyederhanaan yaitu (1) semua kelas mempunyai probabilitas sama atau equiprobable, (2) semua data dalam semua kelas mempunyai distribusi normal, (3) semua kelas mempunyai matriks kovarian yang sama, dan (4) matriks kovarian berbentuk matriks diagonal dan semua elemen diagonalnya sama besar, yaitu S = 2 I dengan I adalah matriks identitas. Euclidean Distance Classifier akan mengklasifikasikan suatu pola x ke dalam kelas i jika
x mi ( x mi ) T ( x mi ) x m j
(7)
untuk i j dengan S adalah matriks kovarian dan mi adalah rerata kelas i. Jika asumsi terakhir tidak terpenuhi (matriks kovarian tidak berbentuk matriks diagonal dan semua elemen diagonalnya tidak sama besar), maka harus digunakan Mahalanobis Distance Classifier. Suatu pola x akan dimasukkan ke dalam kelas i jika
( x mi )T S 1 ( x mi ) ( x m j )T S 1 ( x m j )
(8)
untuk j i Untuk mengetahui matriks kovarian dari data, digunakan teknik maximum likelihood untuk estimasi fungsi PDF. Dengan asumsi bahwa PDF terdistribusi normal dan terdapat N data dengan xi Rℓ, I =
Hasil ekstraksi ciri untuk setiap sampel citra disusun menjadi vektor ciri (sesuai diagram alir pada Gambar 3) sebagai berikut: ciri = [rerata varians std entropi bedaan1 bedaan2] Untuk tiga sampel citra normal yang diperlihatkan pada Gambar 4 diperoleh vektor ciri sebagai berikut. N1 = [141 31,2 5,59 4,5 34 20,6] N2 = [220 10,5 3,24 3,67 19 6,4] N3 = [89,5 16,6 4,07 4,01 23 10,5] Untuk tiga sampel citra bermikrokalsifikasi yang diperlihatkan pada Gambar 5 diperoleh vektor ciri sebagai berikut. C1 = [124 232 15,2 5,84 94 54,6] C2 = [146 195 14,0 5,69 76 42,7] C3 = [181 94,2 9,7 5,22 59 37,9] Nilai rerata ciri untuk kelas 1 dan kelas 2 diperoleh dari data pelatihan dan dinyatakan sebagai matriks M berikut; kolom 1 adalah nilai rerata ciri untuk kelas 1 dan kolom 2 adalah nilai rerata ciri untuk kelas 2. 144,6123 147,6324 351,3899 158,7820 15,6554 11,8479 M 5,3752 5,4296 69,84 71,16 31,1877 42,4276
Rerata ciri masing-masing kelas akan digunakan sebagai pusat dari kelas yang bersangkutan. Berdasarkan letak pusat kelas inilah, Euclidean Distance Classifier akan mengklasifikasikan sebuah data baru yaitu berdasarkan jarak Euclidean terpendek (minimum). Hasil klasifikasi menggunakan 40 data pengujian menunjukkan kinerja Euclidean Distance Classifier setinggi 52,5 % atau kesalahan klasifikasi sebesar 47,5%. Untuk keperluan klasifikasi menggunakan Mahalanobis Distance Classifier, dibutuhkan rerata ciri kedua kelas dan matriks kovarians dari data pelatihan. Matriks kovarians diperoleh menggunakan teknik maximum likelihood, dan hasilnya dinyatakan dalam matriks SM berikut.
SM
0.0147 0.0184 0.0005 0.0184 1.1595 0.0265 0.0005 0.0265 0.0007 1.0e 05 0.0019 0.0001 0 0.0015 0.0810 0.0021 0.0007 0.0012 0.0250
0.0015 0.0012 0.0810 0.0250 0.0001 0.0021 0.0007 0 0.0002 0.0001 0.0002 0.0084 0.0034 0.0001 0.0034 0.0021
0 0 0 0 0 2.76e 04 0 2 . 76 e 04 0 0 0 0 0 0 2.76e 04 0 0 0 SE 0 0 0 2.76e 04 0 0 0 0 0 0 2.76e 04 0 0 0 0 0 0 2.76e 04
0
0.0019
Mahalanobis Distance Classifier melakukan klasifikasi untuk data baru berdasarkan asumsi yang sama dengan Euclidean Distance Classifier kecuali asumsi yang terakhir. Hasil klasifikasi menggunakan 40 data pengujian menunjukkan kinerja Mahalanobis Distance Classifier mencapai 87,5% atau kesalahan klasifikasi sebesar 12,5%. 3.2 Pembahasan Perbandingan kinerja dan error atau kesalahan klasifikasi menggunakan Euclidean dan Mahalanobis Distance Classifier diperlihatkan secara grafis pada Gambar 6. Kinerja dan Error Klasifikasi (%) 100 80 60
Euclidean
40
Mahalanobis
20 0 Kinerja
dalam algoritma pengklasifikasi itu sendiri yang mengasumsikan semua kelas mempunyai probabilitas yang sama (equiprobable) dan mempunyai distribusi normal, serta semua kelas mempunyai matriks kovarian yang sama. Di samping itu matriks kovarian diasumsikan berupa matriks diagonal dengan semua elemen diagonal sama besar, yaitu S = 2 I. Dengan asumsi ini maka Euclidean Distance Classifier menganggap bahwa matriks kovarian dari data pelatihan adalah matriks SE sebagai berikut:
Error
Gambar 6. Perbandingan kinerja dan error dari Euclidean dan Mahalanobis Distance Classifier Euclidean dan Mahalanobis Distance Classifier menunjukkan kinerja yang berbeda dalam melakukan klasifikasi citra mamografi. Peningkatan kinerja sebesar 35% diperoleh saat menggunakan Mahalanobis Distance Classifier, demikian juga diperoleh penurunan 35% untuk kesalahan atau error klasifikasinya. Rendahnya kinerja Euclidean Distance Classifier dikarenakan oleh penyederhanaan kondisi melalui asumsi-asumsi yang cukup banyak yang tercermin
Elemen diagonal pada matriks kovarian SE adalah nilai varians dari data pelatihan. Jika dibandingkan dengan matriks kovarian yang sebenarnya yang diperoleh dari data pelatihan (yaitu SM), maka dapat diketahui perbedaan yang signifikan antara kenyataan dan asumsi yang digunakan dalam Euclidean Distance Classifier. Hal ini dapat menjelaskan mengapa kinerja klasifikasi yang dicapai cukup rendah atau error klasifikasinya tinggi. Pada saat digunakan Mahalanobis Distance Classifier, penyederhanaan kondisi hanya dilakukan pada tiga hal yang pertama. Asumsi ke-4 pada Euclidean Distance Classifier tidak digunakan lagi dalam algoritma Mahalanobis Distance Classifier, sehingga pada proses klasifikasi harus diketahui terlebih dahulu matriks kovarian dari data yang digunakan. Dengan kata lain, Mahalanobis Distance Classifier menggunakan matriks kovarian yang sesungguhnya dari data pelatihan yaitu matriks SM (bukan menggunakan asumsi bahwa matriks kovarian dari data pelatihan adalah berupa matriks diagonal dengan semua elemen diagonal sama besar, yaitu S = 2 I, seperti pada algoritma Euclidean Distance Classifier). Oleh karena asumsi atau penyederhanaan kondisi yang lebih sedikit dibandingkan asumsi yang digunakan dalam algoritma Euclidean Distance Classifier, maka hal tersebut berarti bahwa pengklasifikasi Mahalanobis Distance Classifier ‘melihat’ kondisi data secara lebih nyata. Hal inilah yang menjadikan Mahalanobis Distance Classifier menunjukkan kinerja klasifikasi yang lebih tinggi dan error klasifikasi yang lebih rendah dari pada Euclidean Distance Classifier. Pada penelitian ini digunakan 100 data pelatihan dan 40 data pengujian; penggunaan data pelatihan yang jauh lebih banyak kemungkinan akan menghasilkan kinerja yang lebih tinggi dan error yang lebih rendah baik untuk Euclidean maupun Mahalanobis Distance Classifier, karena asumsi pertama dan kedua, yaitu bahwa semua data dalam semua kelas mempunyai probabilitas yang sama dan terdistribusi secara normal, menjadi lebih mendekati kenyataan. 4. Simpulan dan Saran 4.1 Simpulan Berdasarkan hasil penelitian dan pembahasan pada bab sebelumnya, dapat ditarik beberapa kesimpulan sebagai berikut. 1. Dua pengklasifikasi berdasar jarak minimum, yaitu Euclidean dan Mahalanobis Distance Classifier, dapat
2.
digunakan untuk mengklasifikasikan citra normal dan citra bermikrokalsifikasi pada citra mamografi digital, dengan masukan berupa ciri-ciri yang diekstrak berdasarkan nilai piksel citra yaitu rerata, varians, standar deviasi, entropi, beda nilai piksel minimum dan maksimum, serta beda nilai piksel maksimum dengan reratanya. Mahalanobis Distance Classifier menghasilkan kinerja klasifikasi yang lebih baik dari pada Euclidean Distance Classifier. Pada penelitian ini, Euclidean Distance Classifier menghasilkan kinerja klasifikasi setinggi 52,5% dan error sebesar 47,5%, sedangkan Mahalanobis Distance Classifier menghasilkan kinerja klasifikasi setinggi 87,5% dan error sebesar 12,5%; atau dikatakan terjadi peningkatan kinerja dan penurunan tingkat error sebesar 35% saat digunakan Mahalanobis Distance Classifier.
4.2 Saran Berdasarkan hasil penelitian dan pembahasan serta simpulan, maka dapat disarankan untuk pengembangan penelitian ini. 1. Penggunaan data pelatihan yang jauh lebih banyak sehingga asumsi yang kedua, yaitu bahwa semua data dalam semua kelas diasumsikan mempunyai distribusi normal, menjadi terpenuhi. Dengan demikian diharapkan akan menghasilkan kinerja yang lebih tinggi dan error yang lebih rendah baik untuk Euclidean maupun Mahalanobis Distance Classifier. 2. Selain hal tersebut, penggunaan pengklasifikasi yang memfasilitasi kenyataan bahwa data pada semua kelas tidak selalu mempunyai probabilitas yang sama (equiprobable), dapat meningkatkan kinerja klasifikasi. Hal ini didasari kenyataan bahwa probabilitas kejadian munculnya citra normal dan citra bermikrokalsifikasi kemungkinan tidak sama besar.
El-Naqa, Issam, dkk, Support Vector Machine Learning for Detection of Microcalcifications in Mammograms, Dept. Of Electrical and Computer Engineering, Illinois Institute of Technology. Fessant dkk, 2001, Comparison of supervised Self Organizing Maps Using Euclidean or Mahalanobis Distance in Classification Context, 6th International Work Conference on Artificial and Natural Neural Networks (IWANN2001), Granada, June 13-15 2001. Garcia, Arnaud., dkk, 2008, Multivariate Mathematical Morphology and Bayesian Classifier Application to Colour and Medical Images, Proceedings of SPIEIS&T Vol. 6812 681203-1, 2008. Jain, Anil K., 1989, Fundamental of Digital Image Processing, Prentice Hall International, Inc. Singapore. Karande dan Talbar, Independent Component Analysis of Edge Information for Face Recognition, International Journal of Image Processing (IJIP) Volume 3: Issue 3. Liu, Sheng., Babbs, Charles F., dan Delp, Edward J., Normal Mammogram Analysis and Recognition, Purdue University, Indiana. Maged Marghany dan Mazlan Hashim, 2011, Mahalanobis Classification and Neural Network for Oil Spill Detection Using RADARSAT-1 SAR Data, INSTEG UTM, Malaysia. Munir, R., 2004, Pengolahan Citra Digital dengan Pendekatan Algoritmik, Informatika Bandung. Sheshadri, H.S. dan Kandaswamy, A., 2006, Computer Aided Decision System for Early Detection of Breast Cancer, Indian J Med Res 124, pp 149 – 154. Yaffe,
Daftar Pustaka Babiloni, Fabio., dkk, 2001, Mahalanobis DistanceBased Classifiers are Able to Recognize EEG Pattern by Using Few EEG Electrodes, Proceeding 23rd Annual Conference – IEEE/EMBS Oct 25-28 2001, Istanbul, Turkey. Duda,
Martin J,. 1995, Mammography, Engineering Handbook, IEEE Press.
Biomedical
____, http://www.imaginis.com/breasthealth/ statistics.asp, download tanggal 15 Mei 2008 pukul 13.42 WIB. ____,
http: //peipa.essex.ac.uk/ipa/pix/mias, download tanggal 27 Desember 2007 pukul 12.22 WIB.
R.O., Harl, P.E., Stork, D.G., Pattern Classification, Second Edition, John Wiley & Sons, Inc.
Naskah diterbitkan pada Jurnal Orbith Volume 2, Juli 2013, ISSN 1858-2095, halaman 62-68