pengenalan pola

PENGENALAN POLA
(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.

Tahap Pengklasifikasian

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.

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:

• 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.