PENGENALAN POLA
(PATTERN RECOGNITION)
(PATTERN RECOGNITION)
Pengenalan Pola (1)
•
Proses
mengenali suatu objek secara independent ataupun berdasarkan kemiripan dengan
data-data yang telah ada sebelumnya.
•
Prinsip
kerjanya: meniru kemampuan manusia mengenali objek-objek berdasarkan ciri-ciri
dan pengetahuan yang pernah diamatinya dari objek-objek tersebut.
Pengenalan
Pola (2)
•
Cara
kerjanya: mengklasifikasikan objek kedalam kategori/kelas tertentu berdasarkan
beberapa parameter yg telah disimpan dan ditentukan sebelumnya.
•
Contoh
aplikasi: Speech recognition, Data mining, Biometrics, dll.
Istilah
Dalam Pengenalan Pola
•
Fitur
adalah objek dari sebuah pola yang kuantitasnya dapat diukur,
pengklasifikasiannya berdasar dari masing masing nilai dari fitur-fitur
tersebut
•
Vektor
fitur adalah sejumlah atau sekumpulan dari fitur, misalakan sebuah fitur adalah
x maka kumpulan fitur dapat direpresentasikan sebagai x1, ....,xi.
Metode Pengenalan
Pola
•
Ada3
metode pengenalan pola
1. Sintaks
2. Statistik
3. Jaringan Saraf Tiruan (JST)
a. Sintaks
•
Metode pengenalan pola berdasarkan ciri-ciri fisik yang jelas dengan toleransi yg telah ditentukan sebelumnya.
Metode pengenalan pola berdasarkan ciri-ciri fisik yang jelas dengan toleransi yg telah ditentukan sebelumnya.
b. Statistik
•
Metode
pengenalan pola berdasarkan data-data yg bersifat statistik
Contoh: deskripsi baju yang dimiliki seseorang.
c. Jaringan Saraf Tiruan (JST) ...(1)
•
Metode
pengenalan pola yang menggabungkan metode sintaks dan statistik, yaitu
mengenali objek berdasarkan ciri-ciri fisik yg jelas kemudian mengambil
keputusan berdasarkan data statistik.
• Sistem kerja JST seolah-olah meniru otak manusia.
Jaringan Saraf Tiruan (JST) ...(2)
Contoh: mengenali seseorang dari kejauhan.
Selain itu
ada juga Pengenalan pola yang lain yaitu sebagai beriukut:
Pengenalan pola merupakan bidang dalam pembelajaran mesin dan dapat diartikan sebagai
"tindakan mengambil data mentah dan bertindak berdasarkan klasifikasi
data". Dengan demikian, ia merupakan himpunan kaidah bagi pembelajaran
diselia (supervised learning).
Ada beberapa definisi lain tentang pengenalan pola, di antaranya:
Ada beberapa definisi lain tentang pengenalan pola, di antaranya:
- Penentuan suatu objek fisik atau kejadian ke dalam salah satu atau beberapa kategori.
- Ilmu pengetahuan yang menitikberatkan pada deskripsi dan klasifikasi (pengenalan) dari suatu pengukuran.
- Suatu pengenalan secara otomatis suatu bentuk, sifat, keadaan, kondisi, susunan tanpa keikutsertaan manusia secara aktif dalam proses pemutusan.
Berdasar beberapa definisi di atas,
pengenalan pola bisa didefinisikan sebagai cabang kecerdasan yang
menitik-beratkan pada metode pengklasifikasian objek ke dalam klas - klas
tertentu untuk menyelesaikan masalah tertentu.
Salah satu aplikasinya adalah pengenalan suara, klasifikasi teks dokumen dalam
kategori (contoh. surat-E spam/bukan-spam), pengenalan tulisan tangan, pengenalan kode pos secara
otomatis pada sampul surat, atau sistem pengenalan wajah
manusia.
Aplikasi ini kebanyakan menggunakan analisis citra bagi pengenalan pola yang berkenaan
dengan citra digital sebagai input ke dalam sistem pengenalan
pola.
Support
Vector Machine (SVM)
Konsep
SVM dapat dijelaskan secara sederhana sebagai usaha mencari hyperplane2 terbaik
yang berfungsi sebagai pemisah dua buah class pada input space. Gambar 1a
memperlihatkan
beberapa
pattern yang merupakan anggota dari dua buah class : +1 dan –1. Pattern yang
tergabung
pada class –1 disimbolkan dengan warna merah (kotak), sedangkan pattern pada
class +1, disimbolkan dengan warna kuning(lingkaran). Problem klasifikasi dapat
diterjemahkan
dengan usaha menemukan garis (hyperplane) yang memisahkan antara kedua
2
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.
A.
KARAKTERISTIK SVM
Karakteristik SVM
sebagaimana telah dijelaskan pada bagian sebelumnya, dirangkumkan sebagai berikut:
1. Secara prinsip
SVM adalah linear classifier
2. Pattern
recognition dilakukan dengan mentransformasikan data pada input space ke ruang yang
berdimensi lebih tinggi, dan optimisasi dilakukan pada ruang vector yang baru
tersebut. Hal ini membedakan SVM dari solusi pattern recognition pada umumnya,
yang melakukan optimisasi parameter pada ruang hasil transformasi yang
berdimensi lebih rendah daripada
dimensi input
space.
3. Menerapkan
strategi Structural Risk Minimization (SRM)
4. Prinsip kerja
SVM pada dasarnya hanya mampu menangani klasifikasi dua class.
B.
KELEBIHAN DAN KEKURANGAN SVM
Dalam memilih solusi untuk menyelesaikan suatu masalah, kelebihan dan
kelemahan
masing-masing metode harus diperhatikan. Selanjutnya metode yang tepat
dipilih dengan
memperhatikan karakteristik data yang diolah. Dalam hal SVM, walaupun
berbagai studi telah menunjukkan kelebihan metode SVM dibandingkan metode konvensional
lain, SVM juga memiliki berbagai kelemahan. Kelebihan SVM antara lain sbb.
1. Generalisasi
Generalisasi didefinisikan sebagai kemampuan suatu metode (SVM, neural network,
dsb.) untuk mengklasifikasikan suatu pattern, yang tidak termasuk data yang
dipakai dalam fase pembelajaran metode itu. Vapnik menjelaskan bahwa
generalization
error dipengaruhi oleh dua faktor: error terhadap training set, dan satu
faktor lagi yang dipengaruhi oleh dimensi VC (Vapnik-Chervokinensis). Strategi pembelajaran
pada neural network dan umumnya metode learning machine difokuskan pada usaha
untuk
meminimimalkan
error pada training-set. Strategi ini disebut Empirical Risk Minimization (ERM).
Adapun SVM selain meminimalkan error pada training-set, juga meminimalkan faktor
kedua. Strategi ini disebut Structural Risk Minimization (SRM), dan
dalam SVM diwujudkan dengan memilih hyperplane dengan margin terbesar. Berbagai
studi empiris menunjukkan bahwa
pendekatan
SRM pada SVM memberikan error generalisasi yang lebih kecil daripada yang
diperoleh dari strategi ERM pada neural network maupun metode yang lain.
2. Curse of dimensionality
Curse
of dimensionality didefinisikan sebagai masalah yang dihadapi suatu metode
pattern recognition dalam mengestimasikan parameter (misalnya jumlah hidden
neuron pada neural network, stopping criteria dalam proses pembelajaran dsb.)
dikarenakan jumlah sampel data yang relatif sedikit dibandingkan dimensional ruang
vektor data tersebut. Semakin tinggi dimensi dari ruang vektor informasi yang diolah,
membawa konsekuensi dibutuhkannya jumlah data dalam proses pembelajaran. Pada
kenyataannya seringkali terjadi, data yang diolah berjumlah terbatas, dan untuk
mengumpulkan data yang lebih banyak tidak mungkin dilakukan karena
kendala
biaya dan kesulitan teknis. Dalam kondisi tersebut, jika metode itu “terpaksa” harus
bekerja pada data yang berjumlah relatif sedikit dibandingkan dimensinya, akan
membuat proses estimasi parameter metode menjadi sangat sulit. Curse of
dimensionality sering dialami dalam aplikasi di bidang biomedical engineering,
karena biasanya data biologi yang tersedia sangat terbatas, dan penyediaannya
memerlukan biaya tinggi. Vapnik membuktikan bahwa tingkat
generalisasi
yang diperoleh oleh SVM tidak dipengaruhi oleh dimensi dari input vector [3].
Hal ini merupakan alasan mengapa SVM merupakan salah satu metode yang tepat
dipakai untuk memecahkan masalah berdimensi tinggi, dalam keterbatasan sampel
data yang ada.
3.
Landasan teori
Sebagai
metode yang berbasis statistik, SVM memiliki landasan teori yang dapat dianalisa
dengan jelas, dan tidak bersifat black
box.
4. Feasibility
SVM
dapat diimplementasikan relatif mudah, karena proses penentuan support vector
dapat dirumuskan dalam QP problem. Dengan demikian jika kita memiliki library
untuk menyelesaikan QP problem, dengan sendirinya SVM dapat diimplementasikan dengan
mudah. Selain itu dapat diselesaikan dengan metode sekuensial sebagaimana penjelasan
sebelumnya.
Disamping
kelebihannya, SVM memiliki kelemahan atau keterbatasan, antara lain:
1.
Sulit dipakai dalam problem berskala besar. Skala besar dalam hal ini
dimaksudkan
dengan
jumlah sample yang diolah.
2.
SVM secara teoritik dikembangkan untuk problem klasifikasi dengan dua class. Dewasa
ini SVM telah dimodifikasi agar dapat menyelesaikan masalah dengan class lebih
dari dua, antara lain strategi One versus rest dan strategi Tree Structure. Namun
demikian, masing-masing strategi ini memiliki kelemahan, sehingga dapat dikatakan
penelitian dan pengembangan SVM pada multiclass-problem masih merupakan
tema penelitian yang masih terbuka.
APLIKASI SVM DALAM BIOINFORMATIKA
Pada paruh pertama tulisan ini, diskusi difokuskan
pada dasar-dasar teori metode Support Vector Machine sebagai salah satu topik menarik
yang tengah hangat dibicarakan dalam dunia komputer sains. Sebagaimana lazimnya
perkembangan suatu teori, pertanyaan berikutnya adalah bagaimana teori tersebut
diaplikasikan pada dunia nyata ? Apakah metode yang bagus secara teoritis itu
mampu diaplikasikan untuk menyelesaikan suatu masalah nyata, ataukah teori
tersebut hanya berhenti pada ujicoba dengan toy problems ? Dalam hal ini
Vapnik memberikan ungkapan menarik yang perlu digarisbawahi : “Nothing is
more practical than a good theory”]. Fakta yang
membuktikan pernyataan Vapnik tersebut adalah semakin luasnya penelitian yang
membuktikan kehandalan SVM dari sudut teori maupun aplikasi, dimana salah
satu aplikasinya
adalah dalam bidang bioinformatika. Bioinformatika adalah suatu disiplin yang
mengawinkan teknologi informasi dan teknologi biologi, untuk menjawab permasalahan
kompleks dalam bidang biologi. Bioinformatika berkembang dari kebutuhan manusia
untuk menganalisa data yang dewasa ini kuantitasnya makin meningkat. Akselerasi
dari ketersediaan data biologi ini tidak terlepas dari peranan kerjasama
harmonis teknologi informasi dan kemajuan di bidang bioteknologi. Sebagai
contoh, pembacaan sekuen genom manusia oleh Celera Genomics dapat diselesaikan
dalam waktu singkat, dibandingkan usaha konsorsium lembaga riset publik AS,
Europa, dsb.. Dengan melimpahnya data biologi tersebut,
akan timbul pertanyaan : bagaimana kita memperoleh manfaat dari data ini ? Rutherford
D. Roger memberikan
ungkapan menarik: “We are drowning in information, but starving for
knowledge”. Ungkapan ini sejalan dengan situasi terkini di dunia
bioteknologi. Melimpahnya ketersediaan data harus diikuti dengan tahapan
mengekstrak informasi dari data tersebut. Selanjutnya informasi ini
diolah agar dapat ditarik pengetahuan (knowledge) yang bermanfaat bagi masyarakat
dan kemanusiaan. Misalnya dalam bidang klinis, pengetahuan yang diperoleh tersebut
dipakai untuk mendesain obat atau terapi medis yang sesuai dengan
kebutuhan sang pasien (tailor made medicine), untuk identifikasi
agen penyakit baru, untuk diagnosa penyakit baru . Untuk mewujudkan
proses transformasi data-informasi-knowledge ini, teknologi informasi
memiliki peranan penting. Hal ini terlihat dari banyaknya paper yang
membahas aplikasi metode komputasi untuk menganalisa data biologi
seperti statistical pattern recognition, artificial neural network, SVM,
dsb.[8] Tiap metode memiliki sisi kelebihan dan kekurangan, dan
metode yang tepat harus dipilih dengan memperhatikan karakteristik
problem biologi tersebut. Berbagai penelitian dilakukan untuk mengevaluasi
potensi SVM dalam analisa data biologi, antara lain:
1. Analisa ekspresi gen
2. Deteksi homologi protein
3. Prediksi struktur protein Makalah ini mengambil contoh bahasan aplikasi
SVM pada masalah pertama, yaitu analisa data ekspresi gen, karena kesesuaiannya
dengan kemampuan SVM dalam mengolah informasi berdimensi tinggi. Data biologi
yang diolah dan dianalisa oleh SVM diperoleh dari eksperimen microarray yang
memungkinkan pengamatan ekspresi ribuan gen sekaligus, misalnya pada sel yang
diambil dari penderita penyakit kanker. Pemanfaatan microarray membuka
kemungkinan untuk mengetahui kuantitas maupun kualitas transkripsi satu gen, sehingga
dapat diidentifikasikan : gen-gen apa saja yang aktif terhadap perlakuan
tertentu,
misalnya timbulnya kanker. Informasi ini merupakan
pertimbangan penting bagi ahli
medis untuk mengetahui mekanisme timbulnya penyakit,
dan menentukan terapi mana yang
paling tepat bagi si pasien. Proses dalam
analisa micorarray secara
sederhana dapat diuraikan sebagai berikut. Pertama-tama
mRNA yang disolasi dari sampel dikembalikan dulu dalam bentuk DNA menggunakan
reaksi reverse transcription. Selanjutnya melalui proses hibridisasi, hanya DNA
yang komplementer saja yang akan berikatan dengan DNA di atas chip. DNA yang telah
diberi label warna berbeda ini akan menunjukkan pattern yang unik. Dengan memanfaatkan
teknologi pengolahan citra (image processing), pattern ini selanjutnya ditransfer
ke dalam ekspresi numerik untuk diolah dengan berbagai metode pattern
recognition (dalam hal ini SVM). Dalam studi
analisa ekspresi gen, ada tiga hal yang merupakan bahasan menarik dari sudut
pattern recognition [11]:
1. Mungkinkah dengan data ekspresi gen dari microarray,
kita memprediksi suatu class, misalnya apakah seorang pasien tersebut terkena
kanker atau tidak, atau menentukan
status mutasi p53 pasien, dsb.
2. Kalau hal tersebut memungkinkan untuk dilaksanakan,
berapakah tingkat akurasi yang mungkin dicapai ?
3. Bagaimana menentukan kandidat gen yang memiliki
potensi kedokteran/farmasi ? Bahasan dalam makalah ini dibatasi pada tema
pertama, dengan mengevaluasi performa SVM dalam klasifikasikan ekspresi
gen.Tema ini tergolong tema pattern recognition yang sangat sulit, karena
memiliki karakteristik
1. Data observasi berdimensi tinggi : manusia memiliki
sekitar 31 ribu jenis gen, sehingga
setiap pengukuran memberikan satu titik pada
ruang vektor berdimensi sekitar 31 ribu
2. Noisy
3. Unbalanced, dalam artian sampel class positif
seringkali tersedia dalam jumlah yang jauh lebih sedikit daripada sampel class
negatif. Karakteristik ini menjadi latar belakang mengapa SVM mendapat
perhatian besar dari kalangan bioinformatika. Potensi SVM sebagaimana diuraikan
pada halaman yang terdahulu memberikan harapan untuk dapat menyelesaikan
problem dengan karakteristik tersebut. Salah satu paper yang membahas aplikasi
SVM dalam analisa data ekspresi gen adalah sebagaimana yang dilakukan oleh
group Terrence S. Furey.
RISET GROUP TERRENCE S. FUREY :
ANALISA EKSPRESI GEN MEMAKAI
SVM
Salah
satu penelitian bioinformatika mengenai aplikasi
SVM dalam analisa gene-expression adalah sebagaimana yang dilakukan oleh group Terrence
S. Furey, dimuat di journal Bioinformatics [9]. Group Furey memakai SVM dengan
dot product kernel (linear SVM) untuk menganalisa vektor berdimensi ribuan yang
dibentuk oleh ekspresi gen diperoleh dari eksperimen microarray. Evaluasi
dilakukan terhadap tiga database : Ovarian tissue dataset, human acute leukemia
(Golub dataset), dan yang ketiga adalah human tumour dan normal colon tissue
dataset. Masing-masing eksperimen dapat dirangkumkan sebagai berikut:
1. Ovarian dataset
Sampel
yang berasal dari ovarian cancer tissue, normal ovarian tissue dan normal
tissue non-ovarian yang lain, total sebanyak 31 sampel. Tiap data terdiri dari
97,802 cDNA untuk masing-masing tissue, dengan demikian membentuk ruang vektor
berdimensi 97,802. Untuk mereduksi dimensi dari feature vector ini, dilakukan
feature subset selection (FSS) dengan memilih sekumpulan feature yang paling signikan.
Furey memilih strategy single best criterion, yaitu tiap feature dievaluasi
secara terpisah dengan menentukan mana yang paling berpengaruh pada class
separability. Walaupun metode ini memiliki banyak sisi lemah, dan mengabaikan
kontribusi yang dimiliki secara berkelompok, tapi metode FSS ini mungkin paling
mudah dilakukan dalam kondisi dimensi vektor yang hampir mencapai 100,000.
Hasil dari FSS memperlihatkan bahwa dari 97,802 cDNA, cukup diperlukan 50 buah
feature (cDNA) yang memiliki score signifikansi
tertinggi.
Selanjutnya estimasi parameter dilakukan dengan leave-one-out cross validation.
Hasil eksperimen menunjukkan bahwa satu sampel dari kelompok normal ovarian
tissue selalu gagal diklasifikasikan. Hasil analisa dari kegagalan ini
menunjukkan bahwa margin dari misclassification cukup besar. Hal ini berarti SVM
sangat yakin, bahwa sampel ini tergolong cancerous tissue. Dengan mengeliminasi
satu sampel dari non-ovarian normal tissue yang kualitasnya diragukan, total
akurasi SVM 90% (misklasifikasi : 3 dari total 30 sampel).
2.
Human acute leukemia
Data
pada eksperimen ini berasal dari studi yang dilakukan oleh Golub [12], dan
tersedia online di internet. Data diambil dari 72 pasien penderita myeloid
leukimia (AML) dan acute
lymphoblastic
leukimia (ALL). Data ini dibagi dalam dua kelompok: training set (27 ALL dan 11
AML), dan test set (20 ALL dan 14 AML). Tiap sampel terdiri dari vektor
berdimensi 7129 yang berasal dari ekspresi gen si pasien sebagai hasil analisa
Affymetrix high-density oligonucleotide microarray. FSS dilakukan pada training
set untuk menseleksi feature yang
signifikan,
dengan metode sebagaimana penjelasan sebelumnya. SVM dilatih dengan data dari
training set, dan performa-nya dievaluasi pada test set. Hasil dari eksperimen
menunjukkan bahwa SVM mengklasifikan secara benar antara 30 sampai 32 dari
total 34 sampel pada test set.
3.
Human tumour dan normal colon tissue dataset
Data
pada eksperimen ini berasal dari studi yang dilakukan oleh Alon [13], yang
terdiri dari 40 tissue tumor dan 22 tissue normal colon. Tiap sampel berasal
dari hasil analisa Affymetrix oligonucleotide arrays terhadap 6500 gen manusia.
Dari 6500 gen ini, sebanyak 2000
diantaranya
yang diseleksi terlebih dahulu berdasarkan kriteria tertentu, dipergunakan untuk
keperluan klasifikasi. Performa SVM dievaluasi dengan metode leave-one-out
crossvalidation, dan sebagai hasil 56 sampel berhasil diklasifikasikan secara
benar (misklasifikasi : 6 sampel). Selanjutnya percobaan diulangi dengan
memakai subset yang terdiri dari 1000 dari total 2000 feature pada tiap vektor.
Hasil pada eksperimen kedua ini sama dengan sebelumnya, yaitu 6 sampel saja
yang tidak dapat diklasifikasikan secara benar. Dari ke-6 sampel ini tiga
diantaranya
normal tissue dan
tiga yang lain tumor tissue.
Sebagian dari hasil eksperimen Furey : komparasi SVM dan perceptron pada
studi analisa
ekspresi gen :
 |
Selanjutnya Furey menguji performa perceptron (artificial
neural network), pada ketiga dataset yang sama. Sebagian hasil dari eksperimen tersebut
dirangkumkan pada Tabel 2. Perhatikan bahwa tingkat error pada tabel adalah
hasil rata-rata dari lima kali eksperimen, yang dilakukan dengan mengubah
urutan sampel. Secara keseluruhan SVM memberikan hasil yang lebih baik, kecuali
pada normal tissue data Ovarian. Namun demikian, sebagaimana dijelaskan oleh
Furey, karena evaluasi ini dilakukan pada data yang jumlahnya relatif sedikit,
hasil pada Tabel di atas belum dapat dikatakan valid untuk memberikan
kesimpulan bahwa SVM lebih superior dibandingkan metode yang lain. Dengan makin
banyaknya ketersediaan data ekspresi gen hasil analisa microarray, diharapkan
SVM dapat diujicoba pada eksperimen yang data skala besar, sehingga hasil
komparasi pada eksperimen tersebut tidak diragukan validitasnya.
Walaupun eksperimen dengan data microarray secara
statistik masih terdapat kelemahan, terutama dari sudut keterbatasan data, dan
mahalnya cost yang diperlukan untuk analisa, evaluasi SVM merupakan suatu usaha
yang sangat berharga untuk mengklarifikasikan masalah yang timbul. Analisa pada
data skala kecil ini akan memudahkan bagi kita untuk menemukan sisi-sisi lemah
dari metode yang dipakai. Seiring dengan kemajuan IT dan bioteknologi modern
yang mencengangkan akhir-akhir ini, diperkirakan pada tahun-tahun mendatang,
dunia ilmu pengetahuan akan semakin terbanjiri dengan data biologi, sedangkan
teknologi informasi pun akan melaju dengan kencang. Dalam situasi ini, dengan memanfaatkan
teknologi informasi secara tepat, diharapkan data biologi tersebut dapat diolah
menjadi suatu informasi, dan seterusnya ditransformasikan sebagai suatu
pengetahuan yang dapat ditarik manfaatnya bagi kesehatan dan kesejahteraan umat
manusia.
0 komentar:
Posting Komentar