pengenalan pola -...

34
Pengenalan Pola PTIIK - 2014 Dasar Pengenalan Pola

Upload: hoangtruc

Post on 09-Mar-2019

268 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Pengenalan Pola

PTIIK - 2014

Dasar Pengenalan Pola

Page 2: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Course Contents

Pola, Kelas Pola, dan Pengenalan Pola 1

Persepsi Manusia dan Mesin 2

Proses Pengenalan Pola 3

Studi Kasus 4

Page 3: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Pola

Pola adalah Objek, Proses, atau Kejadian yang

dapat diberi nama (identitas)

Pola adalah himpunan pengukuran yang

menggambarkan sebuah objek

Page 4: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Kelas Pola

Kelas Pola / Kategori merupakan himpunan pola

yang memiliki atribut tertentu

Kumpulan dari beberapa objek yang identik

(kemiripan data)

Selama proses pengenalan, objek dimasukkan

ke dalam kelas yang ditentukan

Page 5: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Pengenalan Pola

Teori (Model), Algoritma (Metode), Sistem untuk

meletakkan pola-pola ke dalam kategori

Menemukan hubungan suatu pola terhadap

pola-pola sebelumnya

Belajar membedakan pola yang dianggap

penting terhadap latar belakangnya

Page 6: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Persepsi Manusia

Manusia telah dianugerahi kemampuan untuk

menerima rangsangan (indera) dari lingkungan

dan memberikan aksi terhadap apa yang

diamati,

Mengenali wajah

Memahami kata yang diucapkan

Membaca tulisan tangan

Membedakan makanan segar dari baunya

Tugas kita:

Menjadikan mesin (komputer) memiliki kemampuan

yang mirip dengan manusia

Page 7: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Contoh Aplikasi

•Handwritten: sorting letters by postal code.

•Printed texts: reading machines for blind people, digitalization of text documents.

Optical Character Recognition

(OCR)

•Face recognition, verification, retrieval.

•Finger prints recognition.

•Speech recognition. Biometrics

•Medical diagnosis: X-Ray, ECG (ElectroCardioGraph) analysis.

Diagnostic systems

•Automated Target Recognition (ATR).

• Image segmentation and analysis (recognition from aerial or satelite photographs).

Military applications

Page 8: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Aplikasi Pengenalan Pola

berdasarkan Domain Permasalahan

Problem Domain Application Input Pattern Pattern Classes

Bioinformatics Sequence Anaysis DNA/Protein

sequence

Known types of

genes/patterns

Data Mining Seaching for

meaningful patterns

Points in multi-

dimensional space

Compact and well-

seperated cluster

Document

classification

Internet search Text Document Semantic categories

(e.g., business,

sports, etc.)

Document image

analysis

Reading machine for

the blind

Document image Alphanumeric

characters, words

Industrial

automation

Printed circuit board

inspection

Intensity or range

image

Defective / non-

defective nature of

product

Multimedia database

retrieval

Internet search Video clip Video genres (e.g.,

action, dialogue,

etc.)

Page 9: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Aplikasi Pengenalan Pola

berdasarkan Domain Permasalahan

Problem Domain Application Input Pattern Pattern Classes

Biometric

Recognition

Personal

Identification

Face, iris, fingerprint Authorized user for

access control

Remote Sensing Forcasting crop yield Multispectral image Land use

categories, growth

pattern of crop

Speech Recognition Telephone directory

enquiry without

operator assistance

Speech waveform Spoken words

Page 10: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Pendekatan Pengenalan Pola

Template Matching : berdasarkan template

Statistical : berdasarkan model statistik dari

pola dan kelas pola yang diberikan

Structural (or syntactic) : kelas pola

direpresentasikan oleh struktur formal seperti

grammer, string, automata, dll.

Neural networks : mesin klasifikasi yang

direpresentasikan oleh model sel neuron dari

otak manusia

Page 11: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Model Pengenalan Pola

Approach Representation Recognition

Function

Typical

Criterion

Template

matching

Samples, pixels,

curves

Correlation,

distance

measure

Classification

error

Statistical Features Discriminant

function

Classification

error

Syntactic or

structural

Primitives Rules, grammar Acceptance

error

Neural networks Samples, pixels,

features

Network

function

Mean square

error

Page 12: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Pendekatan Statistik

A A B Membandingkan

Grid per Grid

Page 13: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

A A B 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1

0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1

Jumlah grid

yang tidak

sesuai = 3

Page 14: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

A A B Membandingkan

Grid per Grid

Page 15: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

A A B 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1

1 1 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 1 0

Jumlah grid

yang tidak

sesuai = 10

Page 16: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Permasalahan

Waktu yang dbutuhkan untuk mengenali

pola (sesuai jumlah pola yang disimpan)

A-Z a-z

0-9

Solution

Artificial

Intelligence

Page 17: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Persepsi Manusia dan Mesin

Kita sering dipengaruhi oleh pengetahuan tentang

bagaimana pola dimodelkan dan dikenali secara alami

ketika kita membangun algoritma pengenalan pola

Penelitian tentang persepsi mesin juga membantu kita

mendapatkan pemahaman lebih dalam dan apresiasi

untuk sistem pengenalan pola secara alami

Sampai saat ini, kita telah mengaplikasikan beberapa

teknik yang murni secara numerik dan tidak ada

korespondensinya dengan sistem alamiah

Page 18: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Pengenalan Pola

Dua Tahap

Learning

Detection

Waktu Learning lebih besar

Sulit untuk belajar, tetapi sekali terpelajar sistem

akan menjadi “natural”

Dapat menggunakan metode AI :

Neural Network

Machine Learning

Page 19: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Konsep Dasar

y

Feature vector x ϵ X

- Vector dari hasil pengamatan

(pengukuran).

- x adalah sebuah titik dalam

ruang vektor X

Pola X1

X2

. = x

.

xn

Hidden state y ϵ Y

- Tidak dapat diukur secara langsung.

- Pola dengan hidden state yang sama terdapat dalam kelas

yang sama Task

- Mendesain classifer (decision rule) q : X Y yang menentukan

hidden state berdasarkan pengamatan

Page 20: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Contoh

Task: jockey-hooper recognition

Himpunan hidden state Y = {H,J}

Ruang vektor A = R2

Tinggi

x

= A

y

Linier classifier :

Lebar

0b)x.w(ifJ

0b)x.w(ifH)x(q

Training examples :

{(x1,y1), …..(xn,yn)}

y

x

+ +

+ +

+ +

+

+ +

+ +

+ +

(w.x)+b = 0

y = H

Page 21: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Learning

Bagaimana mesin dapat belajar aturan (rule) dari

data.

Supervised learning : User menyediakan label kategori atau value/ bobot

untuk masing-masing pola dalam data training.

Unsupervised learning : Sistem membentuk cluster atau pengelompokan

secara alami dari pola yang dimasukan.

Page 22: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Classification Vs Clustering

Classification (Kategori/ Label kelasnya diketahui).

Clustering (Kategori/ Label kelompoknya tidak diketahui

dan biasanya dinamai dengan kelas pertama, kedua dst).

Page 23: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Siklus Desain Sistem

Collect Data

Mengumpulkan data training dan data testing

Choose Features

Disesuaikan dengan domain data.

Choose Model

Disesuaikan dengan domain data.

Training

Supervised learning.

Unsupervised learning.

Evaluate

Menghitung kinerja dengan fitur data yang digunakan.

Page 24: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Pattern Recognation Process

Input & Sensing :

Proses pengambilan data (Acquisition) & pemasukkan data.

Pemrosesan data sesuai dengan karakteristik/ fakta yang ada &

pengukuran untuk nilai dari variable data.

Pre-processing :

Menghilangkan noise pada data.

Melakukan pemisahan pola-pola yang menarik (pattern of

interest) dari data.

Segmentation :

Proses pemisahan objek satu dengan objek yang lain dalam

suatu gambar.

Feature extraction :

Menemukan representasi baru/ perwakilan/ ciri khas data dari

segi fitur.

Classification :

Menggunakan fitur dan model/ algoritma pembelajaran untuk

menetapkan pola pada suatu kelas tertentu.

Post-processing :

Melakukan evaluasi tingkat keberhasilan dalam

keputusan.

Page 25: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Pattern Recognation System

Sistem adalah keseluruhan bagian dari pengenalan pola

mulai dari Input, Proses dan Output.

Teacher/ Human sebagai salah satu sumber basis

pengetahuan (knowledge base)

Page 26: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Studi Kasus

Klasifikasi Ikan Salmon dan Sea Bass.

Permasalahan : Bagaimana memisahkan ikan yang

masuk secara otomatis pada permukaan yang berjalan

(mesin) sesuai dengan spesiesnya.

Asumsikan bahwa kita hanya memiliki dua jenis ikan :

Sea bass.

Salmon.

Page 27: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Studi Kasus

Apa yang bisa menyebabkan masalah selama proses

Sensing ?

Kondisi pencahayaan.

Posisi ikan di permukaan yang berjalan (mesin).

Noise dari kamera dan hal-hal lainnya.

Apa saja langkah-langkah dalam Proses?

Mengambil gambar.

Memisahkan setiap gambar ikan.

Melakukan pengukuran.

Membuat keputusan.

Page 28: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Studi Kasus

Diagram proses klasifikasi :

Page 29: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Studi Kasus

Pre-Processing :

Peningkatan kualitas gambar.

Memisahkan titik data yang merupakan representasi dari kedua

ikan yang hampir saling bersinggungan atau saling overlap.

Menemukan garis boundary/batas pemisah kedua ikan.

How to separate Sea Bass from Salmon?

Menggunakan fitur yang memungkinkan untuk bisa memisahkan

: (Panjang ikan, Tingkat kecerahan, Lebar ikan, Jumlah dan

Bentuk sirip, Posisi mulut dan fitur lainnya jika masih ada).

Asumsi beberapa nelayan mengatakan bahwa "Sea Bass"

umumnya lebih panjang daripada "Salmon".

Meskipun rata-rata "Sea Bass" lebih panjang dari "Salmon",

namun ada banyak contoh di mana ikan yang dilakukan

pengamatan menggunakan fitur ini, malah tidak berlaku.

Page 30: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Studi Kasus

How to separate Sea Bass from Salmon?

Untuk meningkatkan hasil recognition/ pengenalan, kita mungkin

harus menggunakan lebih dari satu fitur pada suatu waktu.

Fitur tunggal kemungkinan besar tidak akan dapat menghasilkan

kinerja terbaik.

Kombinasi fitur kemungkinan besar akan menghasilkan kinerja

yang lebih baik.

Feature Extraction :

1

2

x

x

1

2

:

:

x lightness

x width

Page 31: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Studi Kasus

Decision Boundary :

Model yang lebih kompleks akan

menghasilkan boundary/batas

pemisah yang lebih kompleks

pula.

Penggunaan fitur yang berbeda

akan menghasilkan boundary/

batas pemisah keputusan yang

berbeda pula.

Page 32: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Studi Kasus

Isu-Isu terkait dengan Ekstraksi Fitur :

Fitur yang berkorelasi besar tidak akan meningkatkan kinerja.

Kemungkinan akan ada kesulitan untuk mengekstraksi fitur

tertentu.

Dibutuhkan komputasi yang cukup mahal untuk mengekstraksi

banyak fitur.

Adanya fitur yang hilang.

Domain pengetahuan yang digunakan.

Page 33: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

Diskusi

Carilah contoh kasus di dunia nyata yang dapat

dijadikan topik pengenalan pola oleh mesin !

Tentukan fitur-fiturnya dan kategori (kelas)nya !

Jumlah dan Nama fitur

Jumlah dan Nama kelas

Jumlah dan Contoh datanya

Referensi: http://archive.ics.uci.edu/ml/

Most Popular Data (Sebelah Kanan)

Satu Kelompok Satu Data dan Tidak Boleh Sama

Page 34: Pengenalan Pola - afif.lecture.ub.ac.idafif.lecture.ub.ac.id/files/2014/02/Slide-01-Dasar-Pengenalan-Pola.pdf · 1 Pola, Kelas Pola, dan Pengenalan Pola 2 Persepsi Manusia dan Mesin

[email protected]

081 331 834 734 / 088 160 127 40