metode jarak minimum dan algoritmarepository.usd.ac.id/27000/2/023114033_full.pdf · 2018. 5....

METODE JARAK MINIMUM DAN ALGORITMA PERCEPTRON

UNTUK KLASIFIKASI POLA

SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Sains

Program Studi Matematika

Disusun oleh :

Siti Wardani

NIM : 023114033

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2007

Setiap orang harus menyadari Bahwa tidak semua yang diharapkan akan terjadi. Tidak semua yang diinginkan akan terpenuhi dan Tidak semua yang diminta akan diberikan. Jangan pernah mengeluh ketika kamu harus menghadapinya !! Jangan pernah menyerah ketika keadaan tidak memihakmu dan Jangan pernah lelah untuk meneruskan langkahmu. Akan datang saatnya kau akan tersenyum, Akan tiba waktunya lukamu akan terobati, dan Akan ada saatnya kamu akan menertawakan apa yang kamu lakukan saat ini. Cobalah untuk menerima kenyataan walau pahit yang kau rasakan dan Cobalah lupakan kepedihan dan mulailah tersenyum. Apa yang dulu terlihat baik kini nampak sangat buruk. Apa yang dulu terasa manis, kini nampak kegetiran karena itu pula Apa yang terasa memilukan tak selamanya demikian. Apa yang kini kamu sesali suatu saat akan kamu syukuri. Karena kamu telah melakukannya dan Apa yang kini membuatmu tertunduk dalam kesedihan Suatu saat akan mendatangkan sorak kegembiraan. Penuhi hatimu dengan ucapan Syukur dan Siapkan hatimu untuk segala kemungkinan. Belajarlah menerima kenyataan dan Jangan ada putus asa dalam hidup sebab Allah megasihimu Ia ada di dekatmu dan kau berharga di hadapan NYA.

Dengan kerendahan hati dan penuh rasa syukur skripsi ini kupersembahkan untuk :

Allah SWT Yang Maha Kasih

Keluarga tercinta ....Bapak, Mamak, dan adik-adikku

Keluarga Besar H. M. Soeharjo dan Kertorejo atas kasih sayangnya

Almamaterku tercinta

iv

ABSTRAK

Klasifikasi pola adalah suatu proses dalam menglasifikasikan suatu obyek yang tidak diketahui ke dalam suatu kelas pola tertentu berdasarkan pada ciri-ciri yang dimiliki obyek tersebut.

Metode Jarak Minimum adalah suatu penglasifikasi yang digunakan untuk menglasifikasikan suatu obyek ke dalam suatu kelas pola tertentu berdasarkan pada perhitungan jarak Euclidean. Dalam metode ini setiap kelas pola akan diwakili oleh suatu prototype tunggal yang merupakan nilai rata-rata kelas polanya. Obyek tersebut akan diklasifikasikan ke dalam kelas yang jarak antara prototype dari setiap kelas dan obyek yang akan diklasifikasikan tersebut terkecil.

Algoritma Perceptron adalah penglasifikasi lain yang digunakan untuk mencari suatu vektor bobot yang dapat memisahkan setiap kelas pola secara linear sehingga sampel-sampel pola pada setiap kelas polanya dapat terklasifikasi dengan tepat.

vi

ABSTRACT

Pattern classification is a process in classifying an unknown object into a particular class pattern based on characteristics possessed by the object.

Minimum distance method is a classifier used to classifier used to classify an object into a particular class pattern based on Euclidean distance calculation. In this method, every single pattern would be represented with a single prototype which is an average score of its class pattern. The object would be classified into a class which has the shortest distance between prototype from each class and the object itself.

Perceptron algorithm is a another classifier used to find a augmented vector which able to separate linearly every class pattern and as the result, pattern samples in every class pattern could be classified correctly.

vii

KATA PENGANTAR

Puji syukur penulis panjatkan kehadirat Allah SWT atas limpahan nikmat dan

karunia-Nya sehingga penulis dapat menyelesaikan skripsi ini. Skripsi ini disusun

sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains di Program Studi

Matematika Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam

Universitas Sanata Dharma Yogyakarta.

Dalam penyusunan skripsi ini hingga selesai, penulis telah banyak mendapat

bantuan dari berbagai pihak berupa bimbingan, pengarahan, dan petunjuk. Untuk itu

pada kesempatan ini perkenankanlah penulis menghaturkan terima kasih yang

sebesar-besarnya kepada pihak yang telah memberikan bantuan ini, antara lain :

1. Bapak Ir. Ig. Aris Dwiatmoko, M.Sc, selaku Dekan Fakultas MIPA dan juga

dosen pembimbing akademik atas masukan, bimbingan serta dorongan kepada

penulis selama menempuh studi dan menyelesaikan skripsi ini.

2. Bapak Y.G. Hartono, S.Si, M.Sc selaku Ketua Program Studi Matematika yang

telah memberikan saran, bantuan, bimbingan dan ilmunya dalam bangku kuliah.

3. Ibu Ch. Enny Murwaningtyas, S.Si, M.Si selaku dosen pembimbing yang telah

dengan sabar membimbing, memberikan arahan, masukan, dan petunjuk kepada

penulis sehingga penulis dapat menyelesaikan skripsi ini.

4. Segenap Bapak dan Ibu dosen Fakultas MIPA atas segala ilmu, bimbingan dan

perhatian yang diberikan kepada penulis selama ini.

viii

5. Segenap karyawan Universitas Sanata Dharma, khususnya karyawan sekretariat

FMIPA atas kemudahan dan pelayanannya.

6. Keluarga tercinta....Bapak, Mamak matur nuwun atas bimbingan, doa, dukungan

moral maupun materiil dan atas kesabaran dalam mengarahkan penulis.Adik-

adikku Suci dan Sigit yang telah menjadi teman dan adik yang baik. Keluarga

besarku yang senantiasa memberikan dorongan, nasihat dan kehangatan dalam

persaudaraan. Semoga jasa-jasa kalian semua selalu menjadi inspirasi penulis

menuju kesuksesan di masa yang akan datang.

7. Teman-teman seperjuangan Mat’02 (Rita, Cheea, Deon, Aning, Palm, Wury,

Asih, Nunung, Lia, Bani, Desy) selamat,ya!! Lili, Priska, Sarry, Vida, Lenta, Ijup,

Ika, Archy, Debby, Aan, Taim, Marcus, Tato, Galeh

8. Teman-teman kosku Linoel, timboel, inem, primtoel, Maria atas keakraban dan

kenyamanannya.

9. Teman-teman KKN kelompok 1, teman-teman P3W, kakak-kakak serta adik-adik

angkatan atas kebersamaan selama ini.

10. Seseorang yang senantiasa menemaniku dalam suka maupun duka. Semoga Allah

SWT senantiasa membimbing kita.

11. Berbagai pihak yang tidak dapat penulis sebutkan satu persatu, terima kasih atas

segala bantuannya.

Semoga skripsi ini dapat bermanfaat bagi kita semua.

Yogyakarta, Mei 2007

Penulis

ix

DAFTAR ISI

Halaman

HALAMAN JUDUL ...…………………………………………………………… i

HALAMAN PERSETUJUAN PEMBIMBING …………………………………. ii

HALAMAN PENGESAHAN …………………………………………………… iii

HALAMAN PERSEMBAHAN ………………………………………………..... iv

PERNYATAAN KEASLIAN KARYA …………………………………………. v

ABSTRAK .............................................................................................................. vi

ABSTRACT ........................................................................................................... vii

KATA PENGANTAR ........................................................................................... viii

DAFTAR ISI ......................................................................................................... x

DAFTAR TABEL ................................................................................................. xiii

DAFTAR GAMBAR ............................................................................................ xiv

DAFTAR LAMPIRAN ........................................................................................ xv

BAB I PENDAHULUAN ................................................................................... 1

A. Latar Belakang ................................................................................... 1

B. Rumusan Masalah ............................................................................. 5

C. Pembatasan Masalah ......................................................................... 5

D. TujuanPenulisan ................................................................................ 6

E. Manfaat Penulisan ............................................................................. 6

F. Metode Penulisan ............................................................................... 7

G. Sistematika Penulisan ......................................................................... 7

x

BAB II LANDASAN TEORI ………………………………………………….. 9

A. Ruang Euclidean Berdimensi-n ......................................................... 9

B. Operasi-operasi dalam Ruang Euclidean Berdimensi-n .................... 10

C. Panjang, Jarak dan Keorthogonalan

dalam Ruang Euclidean berdimensi-n ............................................... 11

BAB III METODE JARAK MINIMUM UNTUK KLASIFIKASI POLA ......... 19

A. Pengantar ............................................................................................ 19

B. Fungsi Pengambilan Keputusan ……………………………………. 22

C. Algoritma Jarak Minimum …………………………………………. 28

BAB IV ALGORITMA PERCEPTRON UNTUK KLASIFIKASI POLA …..... 40

A. Ruang Bobot ………………………………………………………... 40

B. Pelatihan Perceptron untuk Penglasifikasian Pola …………………. 44

1. Algoritma Perceptron untuk 2 kelas pola …………………... 45

2. Algoritma Perceptron untuk L kelas pola …………………... 57

BAB V APLIKASI METODE JARAK MINIMUM DAN

ALGORITMA PERCEPTRON UNTUK KLASIFIKASI POLA …….. 60

A. Pengantar …………………………………………………………… 60

B. Aplikasi Metode Jarak Minimum ………………………………….. 62

C. Aplikasi Algoritma Perceptron …………………………………….. 65

1. Algoritma Perceptron untuk 2 kelas pola …………………... 65

2. Algoritma Perceptron untuk L kelas pola …………………... 68

xi

BAB VI PENUTUP ……………………………………………………………. 72

A. Kesimpulan ………………………………………………………... 72

B. Saran ………………………………………………………………. 73

DAFTAR PUSTAKA …………………………………………………………... 74

LAMPIRAN ……………………………………………………………………. 75

xii

DAFTAR TABEL

Halaman

Tabel Data Training Set ………………………………………………………… 34

Tabel Perhitumgan Prototype Setiap kelas ........................................................... 34

Tabel Hasil Klasifikasi ......................................................................................... 37

Tabel Data Training Set ………………………………………………………… 37

Tabel Hasil Klasifikasi ......................................................................................... 38

Tabel Klasifikasi Huruf Jawa dengan Metode Jarak Minimum ........................... 64

xiii

DAFTAR GAMBAR

Halaman

Gambar Konsep Penglasifikasi Jarak Minimum ………………………………... 20

Gambar Fungsi Pengambilan Keputusan dengan Tiga Kelas …………………... 23

Gambar Fungsi Diskriminan ……………………………………………………. 28

Gambar Prototype Tunggal …………………………………………………….. 31

Gambar Batas Pengambilan Keputusan dengan Dua

Prototype pada Setiap kelas Pola ………………………………….. 32

Gambar Garis Tegak Lurus ……………………………………………………. 41

Gambar Huruf Jawa ……………………………………………………………. 60

Gambar Flowchart Program Klasifikasi dengan Metode Jarak Minimum ……... 63

Gambar Flowchart Program Klasifikasi dengan

Algoritma Perceptron Dua Kelas ……................................................... 67

Gambar Flowchart Program Klasifikasi dengan

Algoritma Perceptron L Kelas ……....................................................... 70

xiv

DAFTAR LAMPIRAN

Halaman

Lampiran Program Klasifikasi Contoh 3.1 dengan 2 Kelas 5 Sampel ………….. 76

Lampiran Program Klasifikasi Contoh 3.2 dengan 3 Kelas 8 Sampel ………….. 79

Lampiran Program untuk Memanggil Huruf Jawa ……………………………… 84

Lampiran Program Aplikasi Metode Jarak Minimum ………………………….. 96

Lampiran Program Klasifikasi Algoritma Perceptron

Contoh 4.1 dan Contoh 4.2 ………………………………………….. 101

Lampiran Program Aplikasi Algoritma Perceptron 2 Kelas Pola ……………… 105

Lampiran Program Klasifikasi Algoritma Perceptron Contoh 4.3 …………….. 109

Lampiran Program Aplikasi Algoritma Perceptron L Kelas Pola ……………… 118

xv

BAB I

PENDAHULUAN

A. Latar Belakang Masalah

Pengenalan pola telah dikenal sejak dahulu. Namun sebelum tahun 1960-an

pengenalan pola lebih dikembangkan pada penelitian yang didasarkan pada teori sta-

tistika saja. Penemuan komputer telah membantu para ilmuwan untuk mencoba

mengembangkan metode pengenalan pola dalam berbagai bidang ilmu pengetahuan.

Sekarang aplikasi dari metode pengenalan pola telah banyak digunakan dalam berba-

gai penelitian, misal dalam bidang kedokteran (mengembangkan obat-obatan, memo-

nitor ECG, meneliti hubungan DNA, dll), bidang teknologi (merancang mesin),

bahkan dalam kehidupan sehari-hari pengenalan pola juga sangat bermanfaat, misal-

nya untuk identifikasi sidik jari, pengenalan karakter mata, dan lain sebagainya.

Gambaran dari suatu obyek disebut pola, sedangkan penglasifikasian suatu obyek ke

dalam suatu kelas pola disebut pengenalan pola. Pengenalan pola bertujuan untuk

menglasifikasikan suatu obyek ke dalam anggota dari suatu kelas berdasarkan pada

ciri-ciri yang dimiliki obyek tersebut.

2

Obyek yang tidak diketahui kelasnya

sensor

ciri obyek yang tampak

Sistem Pengenalan Pola

A B C ( perkiraan kelas )

Diagram 1. Sistem Pengenalan Pola

Input

Sensor

Ekstraksi ciri

Klasifikasi

Kelas

Diagram 2. Sistem Pengenalan Pola

Dalam Sistem pengenalan pola ada beberapa tahap yaitu sensor yang digunakan

sebagai alat penyaring untuk mengenali pola yang tampak dari suatu obyek. Selanjut-

nya adalah ekstraksi ciri yaitu suatu proses pengambilan ciri-ciri yang dimiliki suatu

3

obyek. Pada proses ini obyek dideteksi kemudian diukur sifat-sifat obyek yang ber-

kaitan sebagai ciri. Ekstraksi ciri bertujuan untuk mengkarakterisasi suatu obyek

menggunakan pengukuran numerik. Biasanya satu ciri saja tidak cukup untuk mem-

bedakan antara objek dari kategori yang berbeda. Sehingga perlu untuk mengenali

sebanyak mungkin ciri-ciri yang dimiliki suatu obyek. Ciri-ciri yang dimiliki suatu

obyek akan diabstraksi dalam bentuk vektor yang disebut sebagai vektor ciri. Kum-

pulan dari vektor ciri disebut ruang ciri. Tahap terakhir adalah klasifikasi yang me-

rupakan suatu proses proses pengelompokan obyek ke dalam kelas yang sesuai.

Dalam skripsi ini akan dibahas metode pengenalan pola pada tahap klasifikasi.

Klasifikasi pola bertujuan untuk mengidentifikasi obyek sebagai anggota dari suatu

kelas. Penglasifikasi menggunakan vektor ciri yang diberikan oleh pengekstraksi ciri

untuk memasukkan obyek ke dalam kelas yang sesuai. Penglasifikasi membagi ruang

ciri dari kelas-kelas obyek ke dalam daerah klasifikasi yang berbeda kemudian me-

masukkan obyek tersebut ke dalam daerah klasifikasi yang sesuai.

Contoh sederhana pengenalan pola. Dalam sebuah keranjang terdapat tiga jenis

bunga yaitu bunga mawar, bunga dahlia dan bunga sepatu. Seorang penjual bunga

ingin mengelompokkan setiap bunga dalam keranjang tersebut sesuai dengan jenis-

nya. Sehingga untuk dapat mengelompokkan dengan benar harus dikenali ciri-ciri

dari setiap bunga. Penjual bunga mencoba untuk mengenali panjang dan lebar daun

bunganya. Dalam kasus ini terdapat dua ciri yang akan diamati dari setiap bunga

yaitu panjang dan lebar daun bunganya. Sehingga vektor ciri x terdiri dari dua ciri

4

yaitu 1x = panjang daun bunga dan = lebar daun bunga. Terdapat kasus pen-

genalan pola yang terdiri atas tiga kelas pola misalkan

2x

1C = kelas bunga mawar, 2C =

kelas bunga dahlia dan 3C = kelas bunga sepatu. Setiap kelas pola mempunyai ukuran

panjang dan lebar daun bunga yang berbeda-beda. Sehingga untuk menglasifikasi-

kannya maka setiap bunga dalam keranjang tersebut akan diukur panjang dan lebar

daun bunganya. Setelah itu akan dihitung selisih panjang dan lebar daun bunga setiap

bunga dalam keranjang dengan panjang dan lebar daun bunga setiap kelas. Misalkan

suatu bunga ternyata selisih panjang dan lebar daun bunganya dengan kelas paling

kecil maka bunga tersebut akan dikategorikan sebagai anggota kelas yaitu kelas

bunga mawar. Dalam proses penglasifikasian bunga di atas digunakan faktor jarak

dalam menghitung selisih panjang dan lebar daun bunga suatu bunga dengan kelas

bunga tertentu.

1C

1C

Dalam skripsi akan dibahas penggunaan metode Jarak Minimum untuk klasifi-

kasi pola dan penggunaan algoritma Perceptron. Dengan menggunakan metode Jarak

Minimum maka suatu obyek akan diklasifikasikan ke dalam kelas yang jaraknya ter-

dekat atau terkecil dengan obyek tersebut. Obyek akan diproses melalui tahap-tahap

dalam sistem pengenalan pola di atas. Kemudian akan diperoleh ciri-cirinya dan

diabstraksikan sebagai vektor ciri. Suatu penglasifikasi adalah alat dengan n masukan

dan sebuah keluaran. Setiap input digunakan untuk menginformasikan satu dari n ciri

yaitu yang diukur dari suatu obyek untuk diklasifikasikan. Suatu

penglasifikasi R akan menghasilkan satu dari R simbol

nxxx ,....,, 21

RCCCC ....., , , , 321 sebagai

5

suatu keluaran, keluaran ini merupakan suatu keputusan tentang kelas dari obyek

yang diklasifikasikan.

Algoritma Perceptron digunakan untuk mencari suatu vektor bobot sembarang

w, kemudian vektor bobot w tersebut digunakan untuk memisahkan dua kelas pola

tersebut secara linear sehingga sampel-sampel pola pada setiap kelas akan terklasifi-

kasi dengan benar.

B. Perumusan Masalah

Pokok permasalahan yang akan dibahas adalah :

1. Bagaimana landasan matematis metode Jarak Minimum untuk klasifikasi pola?

2. Bagaimana klasifikasi pola dilakukan dengan metode Jarak Minimum?

3. Bagaimana landasan matematis algoritma Perceptron digunakan untuk

menglasifikasikan dua kelas pola ?

4. Bagaimana klasifikasi pola dari dua kelas yang berbeda dilakukan dengan algo-

ritma Perceptron ?

C. Batasan Masalah

Dalam penulisan skripsi ini, penulis menggunakan metode Jarak Minimum dan

algoritma Perceptron untuk menglasifikasikan sampel-sampel pola pada setiap kelas

pola yang berbeda. Sedangkan proses untuk menemukan vektor ciri dari obyek dan

peggunaan algoritma Perceptron untuk L kelas pola tidak akan dibahas dalam skripsi.

6

D. Tujuan Penulisan

Tujuan penulisan skripsi ini adalah :

1. Memahami landasan matematis yang digunakan dalam klasifikasi pola dengan me-

tode Jarak Minimum dan algoritma Perceptron.

2. Membedakan suatu obyek dari obyek lain dengan menentukan kelompok pola ber

dasarkan ciri-ciri yang dimiliki obyek tersebut.

3. Melakukan identifikasi suatu pola yang diamati sebagai anggota dari suatu kelas

pola yang sudah diketahui menggunakan metode Jarak Minimum dan algoritma

Perceptron.

4. Menyelesaikan masalah-masalah pengenalan pola dalam tahap klasifikasi pola

menggunakan metode Jarak Minimum dan algoritma Perceptron.

E. Manfaat Penulisan

Manfaat penulisan skripsi ini adalah :

1. Dapat mengerti landasan matematis yang digunakan dalam metode Jarak Minimum

dan algoritma Perceptron untuk klasifikasi pola.

2. Dapat mengetahui tahap-tahap klasifikasi pola menggunakan metode Jarak Mini-

mum dan algoritma Perceptron.

3. Dapat mengaplikasikannya dalam masalah-masalah pengenalan pola pada tahap

klasifikasi pola.

7

F. Metode Penulisan

Metode penulisan yang digunakan dalam skripsi ini adalah metode studi pustaka

dengan mempelajari beberapa bagian materi dari buku yang digunakan sebagai bahan

acuan dan bantuan komputer khususnya program Matlab.

G. Sistematika Penulisan

Pada Bab 1 Pendahuluan, berisi gambaran umum tentang isi skripsi yang meli-

puti latar belakang masalah, perumusan masalah, batasan masalah, tujuan penuli san,

manfaat penulisan, metode penulisan, dan sistematika penulisan.

Pada Bab 2 Landasan Teori, berisi beberapa teori yang mendasari pembahasan

bab berikutnya, yaitu sifat-sifat penjumlahan dan perkalian vektor, Norm Euclidean,

jarak Euclidean, dan pertidaksamaan Cauchy Schwart.

Pada Bab 3 Metode Jarak Minimum untuk Klasifikasi Pola, berisi tentang peng-

antar metode Jarak Minimum, pengambilan keputusan dengan pendekatan jarak

Euclidean. Pembahasan terakhir dari bab ini adalah penggunaan metode Jarak Mini-

mum untuk menglasifikasikan pola.

Pada Bab 4 Algoritma Perceptron untuk klasifikasi pola, berisi tentang pengan-

tar algoritma Perceptron, pengambilan keputusan dengan algoritma Perceptron. Pem-

bahasan terakhir dari bab ini adalah penggunaan algoritma Perceptron dalam

menglasifikasiakan pola.

8

Pada Bab 5 Aplikasi Metode Jarak Minimum dan Algoritma Perceptron untuk

Klasifikasi Pola, Bab ini menyajikan suatu kasus klasifikasi pola dengan mengguna-

kan metode Jarak Minimum dan algoritma Perceptron.

Pada Bab 6 Penutup, penulis akan membuat kesimpulan mengenai skripsi yang

ditulis dan mengharapkan saran sebagai masukan yang membangun bagi penulis

dalam pengembangan masalah klasifikasi pola dengan metode Jarak Minimum dan

algoritma Perceptron selanjutnya.

BAB II

LANDASAN TEORI

Pada bab ini akan dibahas teori-teori yang mendasari penggunaan metode Jarak

Minimum untuk klasififkasi pola yaitu :

A. Ruang Euclidean Berdimensi-n

Sub bab ini bertujuan untuk memperkenalkan vektor di ruang Euclidean berdi-

mensi –n.

Definisi 2.1

Himpunan dari semua kumpulan terurut disebut ruang Euclidean

berdimensi-n dan diberi lambang .

),........,,,( 321 nvvvv

nℜ

Definisi 2.2

Vektor v di adalah pasangan terurut dengan

merupakan bilangan real. Ditulis

nℜ ),........,,,( 321 nvvvv

nvvvv ,........,,, 321 ) , ,..... v, , ( 321 nvvv=v , nilai-nilai

disebut komponen atau koordinat dari vektor. nvvvv ,........,,, 321

10

B. Operasi-operasi dalam Ruang Euclidean Berdimensi-n

Operasi-operasi yang berlaku dalam adalah sebagai berikut : nℜ

Definisi 2.3

Dua vektor dan ) , ..... , , ( 21 nuuu=u ) , ..... , , ( 21 nvvv=v dalam disebut sama jika nℜ

),......,, 2211 nn vuvuvu ===

Jumlah u + v adalah

),......,,( 2211 nn vuvuvu +++=+ vu

Jika s sebarang skalar, perkalian skalar su adalah

) ....., , , ( 21 nsususus =u

Teorema 2.1

Jika , ) , ..... , , ( 21 nuuu=u ) , ..... , , ( 21 nvvv=v dan ) , ..... , , ( 21 nwww=w adalah

vektor-vektor dalam dan r dan s sebarang skalar, maka nℜ

Komutatif) (Sifat (a) uvv u +=+

)Assosiatif (Sifat wvuwvu ( ++=++ )()(b)

Identitas) (Sifat u0u =+(c)

elemen) (Invers 0uu =+ (-1)(d)

if)(Distribut vuvu rr)r( (e) +=+

uuu srs)(r (f) +=+

11

uu rs)()r(s (g) =

uu =)1( (h)

C. Panjang, Jarak dan Keorthogonalan dalam Ruang Euclidean berdimensi-n

Selanjutnya akan dibahas tentang gagasan panjang (norm), jarak dan

keorthogonalan vektor-vektor dalam . Namun, sebelumnya akan didefinisiskan

hasil kali titik dalam ruang Euclidean berdimensi –n sebagai berikut

nℜ

Definisi 2.4

Jika dan ) , ..... , , ( 21 nuuu=u ) , ..... , , ( 21 nvvv=v adalah sebarang vektor dalam ,

maka hasil kali dalam Euclidean u · v dari dua vektor tersebut didefinisikan sebagai

nℜ

nnvuvuvu +++=⋅ ....... 2211vu

Karena suatu vektor dapat dituliskan dalam bentuk matriks, maka perkalian titik da-

pat dituliskan sebagai

u · v = ut v

Teorema 2.2

Jika u, v, dan w adalah vektor di dan r sebarang skalar, maka nℜ

(a) u · v = v · u ( Komutatif )

(b) ( u + v ) · w = u · w + v · w ( Distributif )

12

(c) (ru) · v = r(u · v) ( Homogen )

(d) u · u 0 ≥

(e) u · u = 0 jika dan hanya jika u = 0

Dalam , panjang vektor adalah panjang garis yang mewakili vektor itu, dan

jarak diantara vektor u dan v ialah jarak diantara dua titik yang mewakili kedua

vektor itu. Dengan demikian, panjang dan jarak bagi vektor-vektor dalam adalah

sebagai berikut :

2ℜ

nℜ

Definisi 2.5

Norm Euclidean dari suatu vektor ) , ..... , , ( 21 nuuu=u dalam adalah nℜ

u = ) ( 21=⋅ uu uu ⋅ 222

21 )(.......)()( nuuu +++=

2 sehingga u uu =⋅

Definisi 2.6

Jarak Euclidean antara titik-titik ) , ..... , , ( 21 nuuu=u dan ) , ..... , , ( 21 nvvv=v dalam

adalah nℜ

22222

11 )(........)()(),( nn vuvuvud −++−+−=−= vuvu

∑=

−=n

iii vud

1

2)(),( vu

13

Contoh 2. 1

Misalkan u = (1, 3, -2, 1) dan v = (2, 1, 1, 0), maka

15)1()2()3()1( 2222 =+−++=u

6)0()1()1()2( 2222 =+++=v

dan

15)01()12()13()21(),( 2222 =−+−−+−+−=vud ■

Teorema 2.3 Ketaksamaan Cauchy-Schwarz dalam nℜ

Jika dan ) , ..... , , ( 21 nuuu=u ) , ..... , , ( 21 nvvv=v adalah vektor-vektor dalam ,

maka

nℜ

vuvu ≤⋅ (1)

atau dinyatakan dalam bentuk komponen-komponen,

( ) ( ) 21222212122

2212211 .................. nnnn vvvuuuvuvuvu ++++++≤+++

Bukti :

Jika maka kedua ruas di (1) sama dengan nol. Oleh karena itu ketaksamaan

tersebut berlaku. Jika , untuk setiap bilangan real x, berdasarkan Teorema 2.2

maka nilai

0u =

0u ≠

0)( )( ≥+⋅+ vuvu xx

(2) 0) () (2) ( 2 ≥⋅+⋅+⋅ vvvuuu xx

14

pertidaksamaan (2) merupakan fungsi kuadrat dalam x yang harus selalu nonnegatif.

Artinya fungsi kuadrat tersebut tidak mempunyai akar real yang berbeda. Oleh karena

itu, diskriminannya tidak mungkin positif atau

0) ( ) (4) (4 2 ≤⋅⋅−⋅ vvuuvu

) ( ) (4 ) (4 2 vvuuvu ⋅⋅≤⋅

) ( ) ( ) ( 2 vvuuvu ⋅⋅≤⋅

Berdasarkan Definini norm vektor maka diperoleh

222 || || || || ) ( vuvu ≤⋅

dengan mengambil akar kedua ruas diperoleh

|||| || || | | vuvu ≤⋅ ■

Panjang (Norm) dan jarak dalam ruang Euclidean berdimensi-n memenuhi sifat-sifat

berikut :

Teorema 2.4

Jika u, v dan w adalah vektor-vektor dalam dan k sebarang skalar, maka nℜ

(a) 0≥u

(b) 0 jika hanyadan jika 0 == uu

(c) uu k k=

(d) Segitiga)an (Ketaksama vuvu +≤+

15

(e) 0),( ≥vud

(f) vuvu == jika hanyadan jika 0),(d

(g) ),(),( uvvu dd =

(h) Segitiga)an (Ketaksama ),(),(),( vwuwvu ddd +≤

Bukti :

(a) Misalkan , ) , ..... , , ( 21 nuuu=u ) , ..... , , ( 21 nvvv=v dan ,

berdasarkan Definisi norm vektor diperoleh

) , ..... , , ( 21 nwww=w

u = 2222

1 )(.......)()( nuuu +++

Karena kuadrat dari bilangan real maka 0≥ 0≥u

(b) Diketahui (⇒) 0=u , dengan kontradiksi akan dibuktikan 0=u

Andaikan maka 0u ≠ 0 semuanya tidak yang ,......,1 =∃ nuu

Misal , maka . Sehingga 01 ≠u 021 ≠u

u = 0)(.......)()( 2222

1 ≠+++ nuuu

karena kuadrat bilangan real > 0, maka 0>u kontradiksi dengan 0=u .

Jadi 0u =

( Jika maka )⇐ 0u =

u 2222

1 )(.......)()( nuuu +++= 00.......00 =+++=

(c) Jika , maka ) , ..... , , ( 21 nuuu=u )k , ..... ,k ,k ( k 21 nuuu=u sehingga

16

uk =

222

21 )(.......)()( nkukuku +++

222

21 )(.......)()( nuuuk +++= u k=

(d) Berdasarkan Definisi norm vektor diperoleh

( ) )( 2 vuvuvu +⋅+=+

Berdasarkan Teorema 2.2 sifat (b) maka

)()( 2 vuvvuuvu +⋅++⋅=+ )() ()()( vvv uvuuu ⋅+⋅+⋅+⋅=

)() (2)( vvv uuu ⋅+⋅+⋅=

Berdasarkan Definisi Norm vektor diperoleh

2vu + 22 ) (2 vv uu +⋅+=

karena vuvu ⋅≤⋅ maka 2vu + 22 | |2 vv uu +⋅+≤

Berdasarkan Ketaksamaan Cauchy-Schawrz

2vu + 22 2 vvuu ++≤ 2) ( vu +=

Dengan mengakarkan kedua ruas diperoleh

vuvu +≤+

(e) Berdasarkan Definisi jarak vektor maka diperoleh

22222

11 )(........)()(),( nn vuvuvud −++−+−=−= vuvu

maka 0 realbilangan kuadrat Karena ≥ 0),( ≥vud

(f) ( Jika u = v, maka )⇐ 0)(,.....,0)(,0)( 2211 =−=−=− nn vuvuvu , sehingga

17

2222

211 )(........)()(),( nn vuvuvud −++−+−=−= vuvu

0),( ≥vud 00.......00 =+++=

( Diketahui )⇒ 0),( =vud . Dengan kontradiksi akan dibuktikan bahwa u = v

Andaikan u v, ≠ 0dengan sama semuanya tidak )(),....,( 2211 vuvu −−∃

Misal maka 0)( 11 ≠− vu

0)(........)()(),( 22222

11 ≠−++−+−=−= nn vuvuvud vuvu

Kontradiksi dengan 0),( =vud . Jadi u = v

(g) Jika dan ) , ..... , , ( 21 nuuu=u ) , ..... , , ( 21 nvvv=v maka

2222

211 )(........)()(),( nn vuvuvud −++−+−=−= vuvu

Berdasarkan sifat kuadrat bilangan real maka diperoleh

),( vud 22222

11 )(........)()( nn uvuvuv −++−+−= uv −= ),( uvd=

(h) Berdasarkan sifat penjumlahan vektor

=−= vuvu ),(d )()( vww-u −+

Berdasarkan Definisi norm vektor maka diperoleh

))()(( ))( )(()()( 2 v-ww-uvwwuvww-u +⋅−+−=−+

)-()()-( )()()()()( vwv-wvw w-uvwwuw-uw-u ⋅+⋅+−⋅−+⋅=

)-()()-( )(2)()( vwv-wvw w-uw-uw-u ⋅+⋅+⋅=

Berdasarkan Definisi Norm vektor diperoleh

18

2)()( vww-u −+ 22 )-( (2 v-wvw w)-uw-u +⋅+=

Berdasarkan sifat nilai mutlak vuvu ⋅≤⋅ maka

2)()( vww-u −+ 22 |)-( .(|2 v-wvw w)-uw-u ++≤

Berdasarkan Ketaksamaan Cauchy-Schawrz

2)()( vww-u −+ 22 2 v-wv-ww-uw-u ++≤ 2) ( v-ww-u +=

Dengan mengakarkan kedua ruas maka diperoleh

)()( v-ww-uvww-u +≤−+

)()()( vwwuvu, −+−≤ ddd ■

Definisi 2.7

Dua vektor u dan v dalam disebut orthogonal jika u · v = 0. nℜ

BAB III

METODE JARAK MINIMUM UNTUK KLASIFIKASI POLA

A. Pengantar

Klasifikasi pola adalah pengelompokan suatu obyek yang tidak diketahui ke

dalam suatu kelas pola yang diketahui. Pengambilan keputusan adalah penentuan

suatu obyek untuk dikategorikan ke dalam suatu kelas pola yang sesuai.

Penglasifikasi Jarak Minimum digunakan untuk menglasifikasikan suatu pola yang

tak diketahui ke dalam suatu kelas yang jarak antara suatu pola dan kelas pola

tertentu minimum. Penglasifikasian pola dengan metode jarak minimum meng-

gunakan konsep jarak Euclidean. Dalam hal ini kita akan menghitung jarak antara

dua vektor yaitu vektor dari pola yang tidak diketahui dan vektor dari kelas pola

tertentu yang telah diketahui.

Dalam pengenalan pola, ciri-ciri yang tampak dari suatu obyek disebut dengan

istilah pola. Jadi, pola adalah ukuran kuantitatif dari suatu obyek. Kelas pola adalah

kumpulan pola-pola yang memiliki beberapa sifat umum. Jika terdapat suatu

pengenalan pola dengan L kelas pola maka kelas-kelas pola dinotasikan sebagai

dengan

iC

Li ≤≤1 . Irisan dari tiap-tiap kelas pola adalah himpunan kosong yang

dinotasikan dengan

Φ=ji CC I jika ji ≠

Gabungan dari L kelas pola tersebut adalah ruang pola berdimensi n ( ) yang

dinotasikan dengan

nℜ

20

ni

LiC ℜ=∩

≤≤1

Di bawah ini ditunjukan konsep dari suatu penglasifikasi jarak minimum untuk

menglasifikasikan suatu obyek ke dalam kelas yang sesuai yang terdiri dari tiga kelas

pola yaitu , Jarak obyek ke dalam kelas pola tertentu dinotasikan

dengan . Setiap kelas pola dipisahkan oleh suatu garis yang

disebut batas keputusan.

321 dan ,, CCC

31dengan ≤≤ idCi

Data yang tak diketahui

Jarak minimum ke kelasC diklasifikasikan ke kelas C

2

2

Gambar 3.1 Konsep penglasifikasi Jarak Minimum

Sebelum menglasifikasikan suatu obyek harus dikenali dulu ciri-ciri yang tam-

pak dari obyek tersebut. Satu ciri saja tidak cukup untuk membedakan obyek dari ke-

las yang berbeda sehingga perlu untuk mengenali ciri-ciri dari suatu obyek sebanyak

mungkin. Ciri-ciri obyek tersebut ditulis sebagai vektor ciri. Nilai-nilai dari vektor

ciri diukur dari sampel-sampel yang digunakan dalam masing-masing kelas pola yang

Kelas 3C

∗

Kelas 1C

d 1C

Batas keputusan

Kelas 2C

Jarak kelas dan data 2Cyang tak diketahui

Rata-rata kelas C 2

d 2Cd 3C

21

disebut sampel pola. Sampel pola dari masing-masing kelas pola berbeda-beda, kelas

mempunyai sampel pola sebanyak . iC iM

Jika terdapat suatu obyek x yang akan diklasifikasikan mempunyai ciri

sebanyak n, maka vektor cirinya adalah vektor kolom berdimensi n. Vektor ciri

tersebut dinotasikan dengan

(3.1) iji C∈.x

dengan dan Li ≤≤1 iMj ≤≤1 . Vektor ciri adalah elemen-elemen dari ruang

pola , sehingga mempunyai n elemen yang dinotasikan sebagai dengan

.

ji.x

nℜ ji.x jikx.

nk ≤≤1

Misalkan dalam suatu keranjang bunga terdapat tiga jenis bunga yaitu bunga

mawar, bunga dahlia dan bunga sepatu. Setiap bunga dalam keranjang akan

diklasifikasikan sesuai dengan kelasnya berdasarkan ciri-ciri yang dimiliki oleh setiap

bunga. Sedangkan ciri-ciri yang diamati adalah panjang dan lebar daun bunganya.

Jadi penglasifikasian setiap bunga dalam keranjang tersebut didasarkan pada panjang

dan lebar daun bunga dari masing-masing bunga tersebut.

Dalam penglasifikasian bunga di atas, terdapat tiga kelas pola yaitu = kelas

bunga mawar

1C

, 2C = kelas bunga dahlia dan = kelas bunga sepatu. Sedangkan ciri-

ciri yang diamati adalah panjang dan lebar daun bunganya, maka vektor ciri x

berdimensi dua (n = 2) atau

3C

),( 21 xx=x dengan = panjang daun bunga dan =

lebar daun bunga. Dengan demikian, suatu bunga akan diklasifikasikan ke dalam

1x 2x

22

kelas bunga yang sesuai berdasarkan pada ukuran panjang dan ukuran lebar daun bu-

nganya.

B. Fungsi Pengambilan Keputusan

Sistem pengenalan pola adalah suatu sistem yang mengambil sampel baru x*

yang tak diketahui klasifikasinya untuk dikelompokkan ke dalam suatu kelas pola

berdasarkan pada beberapa aturan pengambilan keputusan. Suatu aturan

pengambilan keputusan ini diperoleh dari pemartisian ruang pola ke dalam beberapa

daerah terpisah yang sesuai dengan kelas . Setiap kelas dipisahkan oleh suatu

kurva yang disebut sebagai batas pengambilan keputusan berdimensi (n-1).

iC

)1( Li ≤≤

iC iC

Jika terdapat kasus pengenalan pola dengan tiga kelas dalam ruang pola

berdimensi dua, maka visualisasi secara geometri akan lebih mudah digunakan untuk

menentukan fungsi pengambilan keputusannya. Namun dalam masalah nyata ruang

polanya berdimensi tinggi atau berdimensi n, maka batas pengambilan keputusannya

adalah hipersurface berdimensi (n-1).

23

Kelas 3

0)(13 xg Kelas 1 0)(23 xg

0)(23 =xg

0)(12 =xg

)(12 xx ijg (3.3)

24

Jika x* berada dalam kelas ke-j maka x* ∈ { } 0)(: xijg

0*)( ∈xijg 0)( xijg 0)( >− xjig

25

)()( xx jiij gg −= ▄

Definisi 3. 3

Misalkan adalah ruang pola dan { 1, 2, …., L } himpunan kelas pola. Suatu

fungsi penyeleksi c(x) adalah suatu pemetaan c : {1, 2, …., L} adalah suatu

cara yang mengaitkan setiap unsur di dengan satu unsur dalam himpunan bulat

positif 1, 2, …., L, sedemikian sehingga

nℜ

⎯→⎯ℜn

nℜ

Jika x berada dalam kelas ke-i maka ic =)(x

Berdasarkan pada Definisi 3.2 dan Definisi 3.3 jika x berada dalam kelas ke-i maka

fungsi penyeleksi c(x) menjadi

Jika maka 0)( >xijg ic =)(x , jij ≠∀ , (3.5)

Jika terdapat pengenalan pola dengan tiga kelas maka berdasarkan persamaan

(3.5) aturan penglasifikasiannya adalah

1. Suatu pola yang tak diketahui (x*) akan diklasifikasikan menjadi anggota

kelas ke-1, maka fungsi penyeleksi c(x) untuk kelas ke-1 sebagai berikut

i. Batas pengambilan keputusan yang memisahkan kelas 1 dan kelas 2 adalah

(x*) > 0. 12g

ii. Batas pengambilan keputusan yang memisahkan kelas 1 dan kelas 3 adalah

(x*) > 0. 13g

Sehingga dapat ditulis sebagai berikut

26

Jika (x*) > 0, (x*) > 0 maka (3.6) 12g 13g 1)( =x*c

2. Suatu pola yang tak diketahui (x*) akan diklasifikasikan menjadi anggota ke-

las ke-2, maka fungsi penyeleksi c(x) untuk kelas ke-2 sebagai berikut


(x*) < 0 atau (x*) > 0. 12g 21g


(x*) > 0. 23g


Jika (x*) < 0, (x*) > 0 maka 12g 23g 2)( =x*c (3.7)

3. Suatu pola yang tak diketahui (x*) akan diklasifikasikan menjadi anggota ke-

las ke-2, maka fungsi penyeleksi c(x) untuk kelas ke-2 sebagai berikut


(x*) < 0 atau (x*) > 0. 13g 31g


(x*) < 0 atau (x*) > 0. 23g 32g


Jika (x*) < 0, (x*) < 0 maka (3.8) 13g 23g 3)( =x*c

Jadi berdasarkan pernyataan (3.5) fungsi penyeleksi untuk setiap kelas pola dapat

dituliskan sebagai berikut

27

⎪⎪⎩

⎪⎪⎨

⎧

><

>><

>>

=

)0)(atau ( 0)( ),0)(atau ( 0)( jika 3

0)( ), 0)(atau ( 0)( jika 2

0)( ,0)( jika 1

)(

32233113

232112

1213

xxxx

xxx

xx

x

gggg

ggg

gg

c

Fungsi pengambilan keputusan memisahkan dua kelas yang berbeda yaitu

kelas ke-i dan kelas ke-j. Berdasarkan Teorema 3.1 diketahui bahwa

sehingga banyaknya pilihan fungsi pengambilan keputusan untuk memisahkan L

kelas pola dapat dihitung menggunakan rumus kombinasi yaitu kombinasi 2 yang

diambil dari L berbeda adalah

)(xijg

)()( xx jiij gg −=

LC2 Δ 2)1(

!2)!2()!2)(1(

!2)!2(! −

=−

−−=

−LL

LLlL

LL

Dalam Gambar 3.2, terdapat suatu daerah tak tentu sehingga fungsi pengambilan

keputusan pada Definisi 3.2 tidak dapat digunakan untuk menglasifikasikan sampel.

Namun, masalah ini dapat diselesaikan menggunakan fungsi diskriminan dengan cara

menuliskan setiap dalam bentuk sebagai berikut : ijg

)(xijg = iθ (x) - jθ (x) (3.9)

Fungsi iθ yang didefinisikan sebagai fungsi pengambilan keputusan dalam

persamaan (3.9) di atas disebut sebagai fungsi diskriminan. Dengan demikian, fungsi

penyeleksi dalam pernyataan (3.5) menjadi :

ijg

jika iθ (x) - jθ (x) > 0 maka ic =)(x

atau

jika iθ (x) > jθ (x) maka ic =)(x dengan ji ≠ (3.10)

28

Dengan menggunakan fungsi diskriminan maka Gambar 3.2 di atas akan tampak

sebagai berikut :

( ) ( )xx 21 θθ =( )xx 32 )( θθ =

( ) ( )xx 31 θθ = 1x

2x

Kelas 2

Kelas 1

Kelas 3

Gambar 3.3 Fungsi diskriminan

C. Algoritma Jarak Minimum

Misalkan banyaknya sampel pola pada setiap kelas pola adalah dan sampel-

sampel pola kelas ke-i ditulis dengan

iM

ji.x iMj ≤≤1 . Dalam metode jarak minimum

suatu sampel pola baru yang tak diketahui x akan diklasifikasikan ke dalam kelas pola

yang terdiri dari sampel-sampel pola yang diketahui . Sampel pola baru tersebut

akan diklasifikasikan ke dalam kelas yang jarak antara sampel pola baru (x) dan sam-

pel-sampel pola pada setiap kelas polanya ( ) paling kecil atau jaraknya terdekat.

ji.x

ji.x

Definisi 3. 4

Fungsi diskriminan untuk kelas ke-i, iθ (x) didefinisikan sebagai berikut

29

)(xiθ = (3.11) ),(min. ji

jd xx−

dengan dan adalah ukuran sampel kelas ke-i. iMj ≤≤1 iM

Dalam penglasifikasi jarak minimum d dihitung menggunakan rumus jarak Euclidean

yaitu

),( yxd = || x - y || = 21

1

2)(⎭⎬⎫

⎩⎨⎧

−∑=

n

kkk yx (3.12)

Jika terdapat sampel pola baru x tak diketahui yang mempunyai n ciri atau ruang

pola berdimensi-n ( ) dengan banyaknya kelas pola adalah L dan setiap kelas pola

diwakili oleh sampel tunggal yaitu dengan

nℜ

ix Li ≤≤1 yang disebut suatu prototype,

maka fungsi diskriminan yang digunakan dalam penglasifikasi jarak minimum adalah

sebagai berikut

)(xiθ = (3.13) ),(id xx−

dengan

),( id xx21

1

2)(⎭⎬⎫

⎩⎨⎧

−= ∑=

n

k

ikk xx (3.14)

Fungsi penyeleksi untuk kelas ke-i dalam pernyataan (3.10) menjadi

ic =)(x jika > (3.15) ),( id xx− ),( jd xx−

atau

ic =)(x jika < (3.16) ),( id xx ),( jd xx

30

Dengan mensubstitusikan pernyataan (3.15) ke pernyataan (3.16) maka fungsi

penyeleksi kelas ke-i adalah

ic =)(x jika 21

1

2)(⎭⎬⎫

⎩⎨⎧

−∑=

n

k

ikk xx <

21

1

2)(⎭⎬⎫

⎩⎨⎧

−∑=

n

k

jkk xx (3.17)

ic =)(x jika ∑ < =

−n

k

ikk xx

1

2)( ∑=

−n

k

jkk xx

1

2)( ji ≠∀ (3.18)

Berdasarkan pernyataan (3.18) ketentuan untuk mencari fungsi peyeleksi kelas ke-i

adalah sebagai berikut

∑ ∑=

−n

k

ikk xx

1

2)( <=

−n

k

jkk xx

1

2)(

))(2)(( 21

2 ik

ikk

n

kk xxxx +−∑

=

< ∑ +− ))(2)(( 22 jkjkkk xxxx

2

11

2

1

)(2)( ∑∑∑===

+−n

k

ik

n

k

ikk

n

kk xxxx <

2

11

2

1

)(2)( ∑∑∑===

+−n

k

jk

n

k

jkk

n

kk xxxx

2

11)(2 ∑∑

==

+−n

k

ik

n

k

ikk xxx <

2

11)(2 ∑∑

==

+−n

k

jk

n

k

jkk xxx

Jika kedua ruas dikalikan 21

− maka persamaan menjadi

2

11

)(21∑∑

==

−n

k

ik

n

k

ikk xxx >

2

11

)(21∑∑

==

−n

k

jk

n

k

jkk xxx

Jadi fungsi penyeleksi dalam pernyataan (3.18) menjadi

ic =)(x jika 211

)(21∑∑

==

−n

k

ik

n

k

ikk xxx >

2

11)(

21∑∑

==

−n

k

jk

n

k

jkk xxx (3.19)

sehingga digunakan fungsi diskriminan linear sebagai berikut

31

)(* xiθ = ∑∑==

−n

k

ik

n

k

ikk xxx

1

2

1

)(21 (3.20)

Salah satu cara untuk memperoleh suatu prototype tunggal dari suatu himpunan

sampel dari suatu kelas pola adalah dengan menentukan nilai rata-rata dari setiap

kelas pola. Di bawah ini ditunjukkan gambar penentuan prototype tunggal dari dua

kelas pola

○ ○ ○ ○ ○ ○ ● ○ ○ ○ ○ ○ ○

□ □ □ □ □ ■ □ □ □ □ □

Kelas 1 Kelas 2

Prototype 1 Prototype 2

Gambar 3. 5 Prototype tunggal

Jika jumlah prototype yang mewakili setiap kelas lebih dari satu atau sebanyak

maka adalah prototype dari kelas ke-i dengan iNlix . iNl ≤≤1 . Fungsi diskriminan

yang digunakan dalam penglasifikasi jarak minimum adalah sebagai berikut

),(min)( .lili

d xxx −=θ (3.21)

Jika dilihat sekilas maka pernyataan (3.21) hampir sama dengan persamaan (3.11)

namun kedua persamaan tersebut sesungguhnya berbeda karena pada persamaan

(3.11) banyaknya sampel pola pada setiap kelas pola adalah dan sampel-sampel

pola kelas ke-i ditulis dengan

iM

li.x iMl ≤≤1 sedangkan pada persamaan (3.21)

32

banyaknya prototype pada setiap kelas pola adalah dan sampel-sampel pola kelas

ke-i ditulis dengan

iN

li.x iNl ≤≤1 dengan iN ≤ . Karena mungkin tidak semua

sampel pola yang terdapat pada setiap kelas digunakan sebagai prototype kelas

polanya. Di bawah ini akan ditunjukan batas pengambilan keputusan dari dua kelas

pola dengan masing-masing kelas pola diwakili oleh dua prototype

iM

□ □ ■ □ □ □

○ ○ ● ○ ○ ○ ○ ○

○ ○ ○ ● ○ ○ ○ ○

□ □ □ ■ □ □

Kelas 2

Kelas 1

Kelas 1

Kelas 2

Gambar 3.6 Batas pengambilan keputusan dengan

dua prototype pada setiap kelas pola

Jarak Euclidean dari x dan dengan li.x iNl ≤≤1 adalah

= ),( .lid xx2.lixx −

= )()( .. litli xxxx −−

= ),( .lid xx litlilittlit .... )()( xxxxxxxx +−−

= (3.22) ),( .lid xx litlitlit ... )()(2 xxxxxx +−

Fungsi penyeleksi untuk kelas ke-i adalah

ic =)(x jika > ),(min .lid xx− ),(min .ljd xx− ji ≠∀

33

atau

ic =)(x jika < (3.23) ),(min .lid xx ),(min .ljd xx

Dengan mensubstitusikan persamaan (3.22) ke persamaan (3.23) maka fungsi penye-

leksi kelas ke-i adalah

ic =)(x jika

})()(2{min ... litlitlit xxxxxx +− < (3.24) })()(2{min ... ljtlitljt xxxxxx +−

Berdasarkan pernyataan (3.24) ketentuan untuk mencari fungsi peyeleksi kelas ke-i

adalah sebagai berikut

< (3.25) })()(2{ min ... litlitli xxxx +− })()(2{ min ... ljtlitlj xxxx +−

Jika kedua ruas dikalikan dengan 21− maka pernyataan (3.25) menjadi

})(21)({ max ... litlitli xxxx − > })(

21)({ max ... ljtlitlj xxxx − (3.26)

Jadi fungsi penyeleksi dalam pernyataan (3.18) menjadi

ic =)(x jika })(21)({ max ... litlitli xxxx − > })(

21)({ max ... ljtlitlj xxxx − (3.27)

sehingga berdasarkan persamaan (3.22) fungsi diskriminan menjadi

)(** xiθ = })(21)({ max ... litlitli xxxx − dengan iNl ≤≤1 (3.28)

Contoh 3.1

Misalkan akan dilakukan penglasifikasian dengan 2 kelas dimana setiap kelas

terdiri atas 2 vektor ciri dan 5 sampel pada setiap kelas. Data vektor ciri tersebut dibe-

34

rikan dalam tabel di bawah :

C1 C2Sampel X1 X2 X1 X2

1 2 1 4 3 2 2 2 4 4 3 1 0 3 5 4 0 2 2 4 5 3 1 1 6

Tabel 3.1 Data Training Set

Berdasarkan Metode Jarak Minimum maka akan dicari prototype untuk setiap

kelas yaitu dengan menghitung nilai rata-rata sampel dalam setiap ciri dari masing-

masing kelas. Hasil perhitungan prototype untuk setiap kelas diberikan dalam tabel

berikut :

C1 C2Sampel X1 X2 X1 X2

1 2 1 4 3 2 2 2 4 4 3 1 0 3 5 4 0 2 2 4 5 3 1 1 6

Rata-rata 1.6 1.2 2.8 4.4 Tabel 3.2 Perhitungan Prototype setiap kelas

Selanjutnya akan dihitung jarak setiap sampel dengan prototype setiap kelas dengan

rumus sebagai

),( id xx21

1

2)(⎭⎬⎫

⎩⎨⎧

−= ∑=

n

k

ikk xx

yaitu jarak setiap ciri pada setiap sampel dengan prototype pada setiap kelasnya.

Dengan demikian, maka

35

jarak kelas ke-1 sampel ke-1 dengan prototype kelas ke-1 adalah

4472.0)2.11()6.12(),( 2211.1 =−+−=xxd


4928.3)4.41()8.22(),( 2221.1 =−+−=xxd


8944.0)2.12()6.12(),( 2212.1 =−+−=xxd


5298.2)4.42()8.22(),( 2222.1 =−+−=xxd


3416.1)2.10()6.11(),( 2213.1 =−+−=xxd jarak kelas ke-1 sampel ke-3 dengan prototype kelas ke-2 adalah

7539.4)4.40()8.21(),( 2223.1 =−+−=xxd


7889.1)2.12()6.10(),( 2214.1 =−+−=xxd


6878.3)4.42()8.20(),( 2224.1 =−+−=xxd


4142.1)2.11()6.13(),( 2215.1 =−+−=xxd


36

4059.3)4.41()8.23(),( 2225.1 =−+−=xxd


3)2.13()6.14(),( 2211.2 =−+−=xxd


8439.1)4.43()8.24(),( 2221.2 =−+−=xxd


6878.3)2.14()6.14(),( 2212.2 =−+−=xxd


2649.1)4.44()8.24(),( 2222.2 =−+−=xxd


0497.4)2.15()6.13(),( 2213.2 =−+−=xxd


6325.0)4.45()8.23(),( 2223.2 =−+−=xxd


8284.2)2.14()6.12(),( 2214.2 =−+−=xxd jarak kelas ke-2 sampel ke-4 dengan prototype kelas ke-2 adalah

8944.0)4.44()8.22(),( 2224.2 =−+−=xxd


8374.4)2.16()6.11(),( 2215.2 =−+−=xxd

37


4083.2)4.46()8.21(),( 2225.2 =−+−=xxd

Berdasarkan hasil perhitungan di atas diberikan tabel klasifikasi sebagai berikut :

Sampel ),( 1.1 xx md ),( 1.2 xx md mind klasifikasi keterangan )( 1.1x 0.4472 3.4928 0.4472 C1 benar ( )2.1x 0.8944 2.5298 0.8944 C1 benar

)( 3.1x 1.3416 4.7539 1.3416 C1 benar )( 4.1x 1.7889 3.6878 1.7889 C1 benar )( 5.1x 1.4142 3.4059 1.4142 C1 benar )( 1.2x 3.0000 1.8439 1.8439 C2 benar )( 2.2x 3.6878 1.2649 1.2649 C2 benar )( 3.2x 4.0497 0.6325 0.6325 C2 benar )( 4.2x 2.8284 0.8944 0.8944 C2 benar )( 5.2x 4.8374 2.4083 2.4083 C2 benar

Tabel 3.3 Hasil klasifikasi

Berdasarkan hasil perhitungan di atas dan output Program Klasifikasi lampiran

(1), besarnya persentase kesalahan klasifikasi adalah 0 % artinya tidak terdapat

penglasifikasian yang salah atau semua sampel dapat diklasifikasikan ke dalam kelas

yang sebenarnya.

Contoh 3.2

Misalkan terdapat 3 kelas dimana setiap kelas terdiri atas 5 vektor ciri dan 8

sampel pada setiap kelas. Data vektor ciri tersebut diberikan sebagai berikut :

C1 C2 C3Sampel X1 X2 X3 X4 X5 X1 X2 X3 X4 X5 X1 X2 X3 X4 X5

1 1 2 3 4 5 3 4 2 5 4 6 5 4 0 6 2 1 0 2 3 4 3 3 2 4 5 6 4 3 6 4

38

C1 C2 C3Sampel X1 X2 X3 X4 X5 X1 X2 X3 X4 X5 X1 X2 X3 X4 X5

3 2 0 0 3 1 4 2 4 5 3 5 7 6 4 0 4 3 0 1 2 4 3 0 0 5 6 6 3 6 4 6 5 2 1 0 1 2 3 3 4 2 3 5 4 6 3 4 6 1 1 3 2 0 2 3 4 5 2 5 5 6 7 3 7 0 1 2 3 2 4 3 2 4 3 6 0 5 4 6 8 2 2 0 1 2 5 3 2 4 4 7 4 3 5 6

Tabel 3.4 Data Training Set

Dengan langkah yang sama pada contoh 1 di atas, maka hasil klasifikasi diberi-

kan sebagai berikut :

Sampel ),( 1.1 xx md ),( 2.2 xx md ),( 3.3 xx md mind klasifikasi keterangan ( )1.1x 3.6120 2.8118 5.5213 2.8118 C2 salah )( 2.1x 2.0117 3.7956 6.9451 2.0117 C1 benar

)( 3.1x 2.3552 4.9149 8.1538 2.3552 C1 benar )( 4.1x 2.3552 3.7956 6.5753 2.3552 C1 benar )( 5.1x 2.0729 4.9403 7.8889 2.0729 C1 benar )( 6.1x 3.0491 5.2589 7.6638 3.0491 C1 benar )( 7.1x 1.8157 4.3481 7.5653 1.8157 C1 benar )( 8.1x 2.3552 4.7070 7.5653 2.3552 C1 benar )( 1.2x 4.6419 1.7048 4.0908 1.7048 C2 benar )( 2.2x 4.0059 1.4684 4.1514 1.4684 C2 benar )( 3.2x 4.6419 2.0387 3.2380 2.0387 C2 benar )( 4.2x 4.9038 4.3481 7.1228 4.3481 C2 benar )( 5.2x 3.7479 2.8559 3.9667 2.8559 C2 benar )( 6.2x 4.3355 2.8118 4.7153 2.8118 C2 benar )( 7.2x 3.7479 1.1859 3.7728 1.1859 C2 benar )( 8.2x 4.6954 1.7766 3.1598 1.7766 C2 benar )( 1.3x 7.8770 6.1568 4.6351 4.6351 C3 benar )( 2.3x 6.9316 3.4866 2.6897 2.6897 C3 benar )( 3.3x 8.9469 6.9395 5.4758 5.4758 C3 benar

39

Sampel ),( 1.1 xx md ),( 2.2 xx md ),( 3.3 xx md mind klasifikasi keterangan )( 4.3x 7.8132 4.9403 2.2326 2.2326 C3 benar )( 5.3x 6.7858 4.2903 1.7984 1.7984 C3 benar )( 6.3x 8.5028 5.3532 3.6034 3.6034 C3 benar )( 7.3x 7.0033 5.0156 4.3283 4.3283 C3 benar )( 8.3x 7.8611 4.5723 2.9128 2.9128 C3 benar

Tabel 3.5 Hasil klasifikasi

Berdasarkan Tabel 3.5 di atas dan output Program Klasifikasi sampel ke-1 kelas

ke-1 diklasifikasikan ke dalam kelas ke-2, sehingga terjadi kesalahan penglasifikasian

sebesar 0416.0241

= atau persentase kesalahan klasifikasi adalah 4.16 %.


(2), besarnya persentase kesalahan klasifikasi adalah 4.16 % artinya terdapat

penglasifikasian yang salah yaitu sampel pertama kelas pertama yang diklasifikasikan

ke dalam kelas ke dua.

BAB IV

ALGORITMA PERCEPTRON UNTUK KLASIFIKASI POLA

A. Ruang Bobot

Misalkan x adalah suatu sampel baru dengan n ciri yang akan diklasifikasikan ke

dalam dua kelas pola yaitu dan yang terpisahkan secara linear dan banyaknya

sampel pola untuk setiap kelas pola adalah . Sampel-sampel pola kelas ke-1

adalah dengan dan sampel-sampel pola kelas ke-2 adalah dengan

. Sehingga mempunyai n elemen dengan . Untuk

menglasifikasikan sampel baru x akan digunakan algoritma Perceptron yaitu suatu

penglasifikasi yang bertujuan untuk mencari suatu vektor bobot yang dapat

memisahkan kelas polanya secara linear.

1C 2C

iM

j.1x 11 Mj ≤≤j.2x

21 Mj ≤≤ji

kx. nk ≤≤1

Dalam algoritma Perceptron, fungsi pengambilan keputusan merupakan suatu

bentuk kombinasi linear dari komponen-komponen vektor polanya, sehingga dapat

ditulis sebagai

12211 ......)( +++++= nnn wxwxwxwg x (4.1)

1)( ++= nt wg xwx (4.2)

dengan adalah vektor bobot dan .

Misalkan

),......,,( 21 nt www=w ),.....,,( 21 n

t xxx=x

),,.....,,( 121 += nnta wwwww

41

)1,,.....,,( 21 nta xxx=x

disebut vektor bobot penambah dan vektor pola penambah. Sehingga persamaan (4.1)

dapat ditulis

ata xwx =)g( (4.3)

Jika maka vektor pola orthogonalterhadap vektor pola . 0)( =xg taw ax

w

d

g(x) = 01 =+ +n

t wxw

H

1x

1x 2x

2x

Gambar 3. 4 Garis tegak lurus

Jika H adalah garis yang memenuhi persamaan g(x) = 0. Jarak antara titik pusat

koordinat dengan garis H adalah d, vektor yang tegak lurus H dan melalui pusat

koordinat adalah w. Jika diambil dua titik sembarang yang terletak pada H yaitu x1

dan x2 maka berdasarkan persamaan (4.1) diperoleh

011 =+ +n

t wxw (4.4)

012 =+ +n

t wxw (4.5)

42

Dengan melakukan operasi pengurangan pada persamaan (4.4) dan persamaan (4.5)

diperoleh

0)21 =− x(xw t (4.6)

Karena dan x1x 2 adalah sembarang vektor yang terletak pada H dan dot product dari

vektor wt dan x1 – x2 sama dengan 0 maka wt tegak lurus x1– x2, sehingga wt tegak

lurus H. Karena w adalah sembarang vektor yang tegak lurus H maka d = αw

dengan α dipilih sedemikian sehingga wα ∈ H. Karena wα ∈ H maka berdasarkan

persamaan (4.2) berlaku

01 =+ +nt wαww (4.7)

Berdasarkan norm vektor maka persamaan (4.7) dapat ditulis menjadi

|| w ||2 α + wn+1 = 0 (4.8)

|| w ||2 α = - wn+1 (4.9)

α = 21

|||| w+− nw (4.10)

karena d = || wα || maka berdasarkan Teorema 2.4 diperoleh

d = || w || . | α |

= || w || 21

|||| w+− nw

= || w || 21

||||||

w+− nw

43

d = |||||| 1

w+nw (4.11)

Definisi 4.1

Dua himpunan dan dari titik-titik dalam ruang berdimensi n terpisah secara

linear jika ada n + 1 bilangan real yaitu sedemikian sehingga

memenuhi dan me-

menuhi .

1C 2C

121 ,,.....,, +nn wwww

121 ),......,,( Cxxx n ∈ 011

>+ +=∑ n

n

iii wxw 221 ),......,,( Cxxx n ∈

011

0 maka c(x) = i (4.12) )(xg

Berdasarkan pernyataan (4.12) di atas maka fungsi pengambilan keputusan untuk ke-

las ke-1 dan fungsi pengambilan keputusan untuk kelas ke-2 adalah

⎭⎬⎫

=<=>

2)( maka 0)( Jika1)( maka 0)( Jika

xxxx

cgcg

(4.13)

44

Sehingga berdasarkan persamaan (4.2) dan pernyataan (4.13) diperoleh

⎪⎪⎪⎪⎪⎪

⎭

⎪⎪⎪⎪⎪⎪

⎬

⎫

++++

+

+

+

+

+

+

0.......

0.......0.......

0.......

0.......0.......

1.2.2

22.2

11

12.22.2

222.2

11

11.21.2

221.2

11

1.1.1

22.1

11

12.12.1

222.1

11

11.11.1

221.1

11

222

111

nM

nnMM

nnn

nnn

nM

nnMM

nnn

nnn

wxwxwxw

wxwxwxwwxwxwxw

wxwxwxw

wxwxwxwwxwxwxw

M

M

(4.14)

Vektor bobot w dapat ditentukan dengan menyelesaikan sistem pertidaksamaan

(4.14) di atas. Dengan mengalikan pertidaksamaan dalam sistem pertidaksamaan

(4.14) untuk kelas ke-2 dengan -1 maka dapat diperoleh

⎭⎬⎫

≤≤>−−−−−≤≤>++++

+

+ 1dengan 0........

1dengan 0........

21.2.2

22.2

11

11.1.2

22.1

11

MjwxwxwxwMjwxwxwxw

nj

nnjj

nj

nnjj

(4.15)

Sistem pertidaksamaan (4.15) digunakan untuk menentukan vektor bobot penambah

. aw

B. Pelatihan Perceptron untuk Penglasifikasian Pola

Seperti yang telah dikatakan pada subbab sebelumnya. Jika terdapat suatu

pengenalan pola dengan L kelas pola maka setiap kelas pola akan diwakili oleh

sampel-sampel pola yang telah diketahui atau dilabeli. Kemudian akan ditentukan

suatu batas pengambilan keputusan yang sesuai untuk memisahkan setiap kelas

polanya, sehingga suatu sampel pola yang tak diketahui dapat diklasifikasikan ke

45

dalam kelas pola yang tepat berdasarkan batas pengambilan keputusan yang telah

ditentukan sebelumya. Dalam subbab ini akan dibahas cara menentukan vektor bobot

w dengan menggunakan suatu algoritma Perceptron.

1. Algoritma Perceptron untuk 2 kelas pola

Jika akan dilakukan suatu pengenalan pola dari suatu sampel pola x tak

diketahui yang mempunyai n ciri dengan dua kelas pola yaitu dan dan

banyaknya sampel pola yang mewakili setiap kelas pola adalah dengan i = 1 dan

i = 2. Sampel-sampel pola kelas ke-1 adalah dengan

1C 2C

iM

j.1x 11 Mj ≤≤ dan sampel-sam-

pel pola kelas ke-2 adalah dengan dengan j.2x 21 Mj ≤≤ . Sehingga sistem perti-

daksamaan (4.15) menjadi

⎪⎭

⎪⎬⎫

≤≤>−

≤≤>

1 ,0

1 ,0

2.2

1.1

Mj

Mjj

ata

ja

ta

xw

xw (4.16)

dengan adalah vektor bobot penambah dan

adalah vektor pola penambah. Untuk setiap himpunan sampel

dan harus ditentukan vektor bobot w sehingga memenuhi sistem pertidak-

samaan (4.16). Algoritma yang digunakan untuk menentukan vektor bobot w adalah

sebagai berikut :

tnna wwww ),,.....,,( 121 +=w

tna xxx )1,,......,,( 21=x

j.1x j.2x

Langkah 1 :

Pilihlah sembarang vektor berdimensi-(n+1). aw

46

Langkah 2 :

Untuk setiap sampel pola dalam kelas ke-1 dihitung nilai j.1x jatajp

.1xwΔ . Jika

0≤jp maka sampel pola tidak dapat diklasifikasikan sebagai anggota kelas ke-

1. Pilih kembali dengan aturan

j.1x

taw

.jaaa c1xww +→

dengan c adalah suatu parameter pengoreksi yang dapat bernilai 1.

Langkah 3 :

Untuk setiap sampel pola dalam kelas ke-2 dihitung nilai ja.2x ja

tajq

.2xwΔ . Jika

maka sampel pola tidak dapat diklasifikasikan sebagai anggota kelas ke-

2. Pilih kembali dengan aturan

0≥jqj

a.2x

taw

.jaaa c2xww −→

Ulangi langkah 2 dan langkah 3 sampai dengan 0>jp 11 Mj ≤≤ dan den-

gan .

0

47

Bukti :

Diketahui kelas-kelas polanya dapat dipisahkan secara linear.

Akan dibuktikan algoritma perceptron konvergen maka harus ditunjukkan algoritma

terbatas artinya terbatas ke bawah dan terbatas ke atas.

Akan ditunjukkan algoritma terbatas ke bawah maka harus ditunjukkan algoritma

mempunyai batas bawah.

Misalkan kelas polanya terpisah secara linear oleh vektor bobot dan 0 maka ber-

dasarkan Definisi 4.1 diperoleh algoritma perceptron sebagai berikut

aw

(4.17) ⎪⎭

⎪⎬⎫

≤≤<

≤≤>

1 ,0

1 ,0

2.2

1.1

Mj

Mjj

ata

ja

ta

xw

xw

atau

(4.18) ⎪⎭

⎪⎬⎫

≤≤>−

≤≤>

1 ,0

1 ,0

2.2

1.1

Mj

Mjj

ata

ja

ta

xw

xw

dengan sampel pola adalah dan sampel pola adalah . Misalkan diam-

bil = atau = , maka sistem pertidaksamaan (4.18) menjadi

1Cj.1x 2C

j.2x

*ax

ja.1x *ax

ja

.2x-

(4.19) 0* >ataxw

Perubahan vektor bobot dalam algoritma dituliskan sebagai berikut

⎩⎨⎧

+← *

aa

aa cxw

ww

jikajika

00*

≤>

*xwxw

ata

ata

Misalkan pemeriksaan terjadi dalam setiap langkah maka algoritma dapat dituliskan

sebagai berikut

48

(4.20) )()()1( * kkk aaa xww +=+

dengan adalah pelatihan sampel ke-k. )(* kax

Andaikan dipilih sembarang vektor bobot awal yaitu maka berdasarkan per-

samaan (4.20) diperoleh

)1(aw

)2()1()1()2()2()3(

)1()1()2(

)1()1(

***

*

aaaaaa

aaa

aa

xxwxww

xww

ww

++=+=

+=

=

sehingga secara umum dapat ditulis

(4.21) )(...............)2()1()1()1( *** kwk aaaaa xxxw ++++=+

atau

(4.22) ∑=

+=+k

iaaa ik

1

* )()1()1( xww

Misalkan adalah sembarang vektor bobot yang memisahkan setiap kelas pola

dengan tepat. Dengan mengalikan setiap ruas pada persamaan (4.22) dengan

a∇

a∇

diperoleh

∑=

∇+∇=∇+k

ia

taa

taa

ta ik

1

* )()1()1( xww

Jika dan })({min * at

aii ∇= xε a∇ adalah vektor bobot yang dapat memisahkan setiap

kelas polanya dengan tepat maka . Jadi 0)(* >∇ at

a ix 0>ε , sehingga persamaan di

atas menjadi

49

(4.23) εkk ataa

ta +∇≥∇+ )1()1( ww

dengan . })({min * at

aii ∇= xε

Dengan menerapkan pertidaksamaan Cauchy-Schwartz pada a∇ dan akan

diperoleh

)1( +ktaw

≥+∇ 2||)1(kaa w||||||2 2)]1([ +∇ kaa w

Dengan menerapkan pertidaksamaan Cauchy-Schwartz pada pertidaksamaan (4.23)

akan diperoleh

εkk ataa

ta +∇≥∇+ )1()1( ww

≥+∇ 2||)1(kaa w||||||2 ≥+∇ 2)]1([ kaa w

2])1([ εkata +∇w

≥+∇ 2||)1(kaa w||||||2 2])1([ εka

ta +∇w

sehingga

222 ))1((

)1(a

atat

ak

kw∇

+∇≥+

εw (4.24)

Jadi batas bawah vektor bobot adalah )1( +ktaw 22))1((

a

ata k

∇

+∇ εw.

Akan ditunjukkan algoritma terbatas ke atas maka harus ditunjukkan algoritma mem-

punyai batas atas.

Norm Euclidean dari persamaan (4.20) adalah

=+2

)1(itaw ⋅+ ))()((* ii aa xw ))()((

* ii aa xw +

50

2**2 )())()((2)( iiii aataa xxww +⋅+=

karena sembarang tidak terklasifikasi dengan tepat maka

sehingga diperoleh

)(* iax 0)()(* ≤ii a

ta xw

≤+2

)1(itaw2)(iaw

2* )(iax+

Jika 2* )(max iax=δ atau δ adalah nilai maksimum dari kuadrat panjang sampel-

sampel polanya karena panjang suatu vektor selalu positif maka δ > 0.

δ+≤+22

)()1( ii tata ww

Misalkan pemeriksaan terjadi dalam setiap langkah maka algoritma dapat dituliskan

sebagai berikut

≤+2

)1(ktaw2)1(aw

2*

1)(ia

k

ix∑

=

+

δkk ata +≤+

22 )1()1( ww (4.25)

Jadi batas atas vektor bobot adalah )1( +ktaw δka +2)1(w .

Jadi algoritma terbatas ke bawah dan terbatas ke atas

Jadi algoritma perceptron konvergen.

Andaikan bahwa pemeriksaan dilakukan pada setiap langkah ke-k, berdasarkan hasil

diatas diperoleh pertidaksamaan :

2

22 ))1(()1(

a

atat

ak

kw∇

+∇≥+

εw dan δkk a

ta +≤+

22 )1()1( ww yang saling kon-

tradiksi untuk nilai k yang cukup besar. Padahal algoritma tersebut harus konvergen

51

ke suatu nilai k yang terbatas. Sehingga untuk menentukan iterasi maksimum agar

kedua kelas terpisah secara linear dengan tepat harus terjadi dimana nilai k yang

memenuhi kedua persamaan di atas. Dengan demikian, kedua persamaan tersebut ha-

rus sama yaitu

22

2 ))1(()(a

ata

ak

kk∇

+∇=+

εδ

ww (4.26)

Jadi perubahan vektor bobot dalam algoritma tersebut akan berhenti pada nilai k ter-

tentu berdasarkan perhitungan pada persamaan (4.26).

Contoh 4.1

Misalkan akan dilakukan penglasifikasian dari 2 kelas pola dengan 3 vektor ciri

dan 2 sampel pola pada setiap kelasnya yaitu ( ) ( ){ }ttC 1,1,0,1,0,01 = dan

( ) ( ){ }ttC 1,1,1,1,0,12 = yang terpisah secara linear, maka untuk mencari suatu vektor bobot w yang dapat memisahkan kedua kelas tersebut adalah sebagai berikut :

Andaikan c = 1 dan sembarang vektor bobot penambah awal berdimensi-(n + 1) yaitu

sehingga vektor masukan untuk ( 0,0,0,0)1( =aw ) ( ) ( ){ }ttC 1,1,1,0,1,1,0,01 = dan vektor

masukan untuk ( ) ( ){ }ttC 1,1,1,1,1,1,0,12 = , terlebih dahulu sampel-sampel pola pada kelas akan dikalikan dengan -1 sehingga menjadi : 2C

( ) ( ){ }ttC 1,1,1,1,1,1,0,12 −−−−−−−= Berdasarkan sistem pertidaksamaan (4.18) dalam menentukan suatu vektor bobot w

yang dapat memisahkan kedua kelas pola tersebut secara linear harus memenuhi

52

0* >Δ atajp xw dengan = atau = . Hasil perhitungannya sebagai

berikut :

*ax

ja.1x *ax

ja

.2x-

[ ] 00000

1100

0000(1) 1.11 =+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

=Δ atap xw

karena 001 ≤=p maka =)2(aw +)1(aw

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

+

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

=

1100

1100

0000

1.1ax , sehingga

[ ] 021100

1110

1100(2) 2.12 >=+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

=Δ atap xw

karena maka 022 >=p =)3(aw )2(aw .

Selanjutnya vektor bobot terakhir ( yang dihasilkan dari kelas digunakan

pada sampel ke-1 kelas , karena

))2(aw 1C

2C 022 ≥=p maka =)3(aw )2(aw . Sehingga

[ ] 21100

11

01

1100(3) 1.23 −=−−+=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−−

−

=Δ atap xw

karena maka 023

53

[ ] 10001

1111

0001(4) 2.24 =+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−−−−

−=Δ atap xw

Selanjutnya vektor bobot terakhir ( yang dihasilkan dari kelas dicoba

kembali pada sampel pertama kelas , karena

))4(aw 2C

1C 014 >=p maka .

Dengan demikian

=)5(aw )4(aw

[ ] 00000

1100

0001(5) 1.15 =+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−=Δ atap xw

karena maka 005 ≤=p =)6(aw +)5(aw

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡−

=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

+

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡−

=

1101

1100

0001

1.1ax , sehingga

[ ] 21100

1110

1101(6) 2.16 =+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−=Δ atap xw

karena maka 026 >=p =)7(aw )6(aw . Sehingga

[ ] 11101

11

01

1101(7) 1.27 −=−−+=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−−

−

−=Δ atap xw

54

karena maka 017 =p =)9(aw )8(aw . Dengan demikian

[ ] 00000

1100

0002(9) 1.19 =+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−=Δ atap xw


⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡−

=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

+

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡−

=

1102

1100

0002

1.1ax , sehingga

[ ] 21100

1110

1102(10) 2.110 =+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−=Δ atap xw

karena maka 0210 >=p =)11(aw )10(aw , Sehingga

[ ] 01102

11

01

1102(11) 1.211 =−−+=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−−

−

−=Δ atap xw

55

karena maka 0011 ≤=p =)12(aw −)11(aw

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡−

=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−−

−

+

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡−

=

0003

11

01

1102

1.2ax , sehingga

[ ] 30003

1111

0003(12) 2.212 =+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−−−−

−=Δ atap xw

karena maka 0312 >=qp =)13(aw )12(aw . Dengan demikian

[ ] 00000

1100

0003(13) 1.113 =+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−=Δ atap xw


⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡−

=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

+

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡−

=

1103

1100

0003

1.1ax , sehingga

[ ] 21100

1110

1103(14) 2.114 =+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−=Δ atap xw

karena maka 0214 >=p =)15(aw )14(aw . Sehingga

[ ] 11103

11

01

1103(15) 1.215 =−−+=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−−

−

−=Δ atap xw

56

karena maka 0115 >=p =)16(aw )15(aw , sehingga

[ ] 11103

1111

1103(16) 2.216 =−−+=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−−−−

−=Δ atap xw

karena maka 0116 >=p =)17(aw )16(aw . Dengan demikian

[ ] 21100

1100

1103(17) 1.117 =+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−=Δ atap xw

karena maka 0217 >=p =)18(aw )17(aw , sehingga

[ ] 21100

1110

1103(18) 2.118 =+++=

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

−=Δ atap xw

Karena hasil perkalian setiap sampel pola pada setiap kelas dengan sembarang

vektor bobot penambah ( )1 ,1 ,0 ,3−=aw positif atau (> 0) maka vektor bobot

tersebut sudah dapat digunakan untuk memisahkan dua kelas pola di atas secara

linear sehingga setiap sampel pola pada setiap kelas dapat terklasifikasi dengan

benar.dengan demikian, dapat disimpulkan bahwa kelas dan terpisah secara

linear oleh vektor bobot

1C 2C

( )1 ,0 ,3−=w . Berdasarkan persamaan (4.2) maka fungsi

pengambilan keputusan linearnya adalah

13)( 311 ++−=+= + xxwg nT xwx

57


(5), nilai vektor bobot penambah yang memisahkan kedua kelas tersebut secara linear

adalah konvergen pada iterasi ke-5. Dengan demikian vektor bobot

tersebut dapat menglasifikasikan setiap sampel pola dengan benar pada kelas yang se-

suai dan persentase kesalahan penglasifikasian sebesar 0%.

( 1 ,1 ,0 ,3−=aw )

Contoh 4.2

Misalkan akan dilakukan penglasifikasian dari 2 kelas pola berdimensi-2 dan 3

sampel pola pada setiap kelasnya yaitu ( ) ( ){ }tttC )2,6(,3,2,1,11 = dan

( ) ( ){ }tttC )2,7(,3,5,1,32 = yang tidak terpisah secara linear, untuk mencari suatu vek-tor bobot w dibatasi dengan iterasi maksimum 30 iterasi. Berdasarkan hasil perhi-

tungan di atas dan output Program Klasifikasi lampiran (5), nilai vektor bobot

penambah pada iterasi maksimumnya adalah ( )4,5 ,8−=aw dimana pada iterasi

maksimum masih terjadi kesalahan penglasifikasian sampel pola ke-3 pada kelas 1

dan prosentase kesalahan penglasifikasiannya adalah 16.67%.

2. Algoritma Perceptron untuk L kelas pola

Jika terdapat suatu pengenalan pola dengan x adalah pola yang tak diketahui

mempunyai n ciri dan banyaknya kelas yang digunakan dalam pengenalan pola se-

banyak L kelas pola. Vektor bobot penambah kelas ke-i dinotasikan dengan

dan adalah vektor pola penam-tnnia wwww ),,.....,,( 121 +=wt

na xxx )1,,......,,( 21=x

58

bah. Dalam pengenalan pola menggunakan algoritma perceptron untuk L kelas pola

menggunakan fungsi diskriminan linear iθ (x) dengan Li ≤≤1 .

Definisi 4.2

Suatu pola x yang tak diketahui akan diklasifikasikan ke dalam kelas ke-i berdasarkan

fungsi diskriminan linear iθ (x) sebagai berikut

iθ (x) > jθ (x) , ∀ ji ≠

dengan atiai xwx =θ )(

Algoritma yang digunakan untuk menentukan vektor bobot w adalah sebagai

berikut :

Langkah 1 :

Pilihlah sembarang vektor berdimensi-(n+1). Hitung iaw

atiai xwx =θ )( dan a

tjaj xwx =θ )(

Langkah 2 :

Pelatihan pola ke-k yaitu x*(k) menghasilakn perhitungan akan diklasifikasikan ke

dalam kelas ke-i, jika berlaku

iθ (x*(k)) > jθ (x*(k)) , ) ,..... , 2 ,1( jiLj ≠=

maka

)()1( kk jaja ww =+ , )..... , 2 ,1( Lj =

59

Langkah 3 :

Jika ada l kelas pola yang memenuhi

iθ (x*(k)) ≤ lθ (x*(k))

maka

)()()1( kckk aiaia∗+=+ xww

)()()1( kckk alala∗−=+ xww

)()1( kk jaja ww =+ , ), ,..... , 2 ,1( ljjiLj ≠≠=

dengan c adalah suatu konstanta positif.

Ulangi langkah 2 dan langkah 3 sampai konvergen yaitu iθ (x*(k)) > jθ (x*(k)) den-

gan atau nilai vektor bobot pada setiap kelas polanya tetap. ) ,..... , 2 ,1( jiLj ≠=

Contoh 4.3

Misalkan akan dilakukan penglasifikasian dari 3 kelas pola berdimensi-2 dan 2

sampel pola pada setiap kelasnya yaitu ( ) ( ){ }ttC 1,0,0,01 = , ( ) ( ){ }ttC 1,1,0,12 = dan { }ttC )2,2(,)2,1(3 = untuk mencari suatu vektor bobot w setiap kelas yang dapat

memisahkan kedua kelas tersebut dibatasi dengan 10 iterasi. Berdasarkan hasil output

Program Klasifikasi lampiran (7), pada iterasi ke-6 telah konvergen dengan nilai vek-

tor bobot setiap kelasnya adalah sebagai berikut

)6,1,0()1,4,1()0,3,6(

3

2

1

−=−−=

−−=

a

a

a

www

BAB V

APLIKASI METODE JARAK MINIMUM DAN ALGORITMA

PERCEPTRON UNTUK KLASIFIKASI POLA

A. Pengantar

Pada Bab 5 ini akan dibahas aplikasi penggunaan Metode Jarak Minimum dan

Algoritma Perceptron untuk klasifikasi pola pada huruf Jawa. Seperti yang telah

diketahui bahwa huruf Jawa terdiri atas 20 huruf atau 20 kelas pola yaitu kelas ha,

na, ca, ra, ka, da, ta, sa, wa, la, pa, dha, ja, ya, nya, ma, ga, ba, tha, dan nga. Huruf

Jawa tersebut disajikan dalam gambar di bawah ini :

Gambar 4.1 Huruf Jawa

Dalam pengenalan pola huruf Jawa tersebut digunakan ketentuan-ketentuan se-

bagai berikut :

1. Setiap huruf Jawa yang telah di’scan’ tersebut dibentuk dalam ukuran 60

pixel pada garis horisontal dan 42 pixel pada garis vertikalnya. Selanjutnya

61

setiap huruf akan dibagi lagi menjadi 9 partisi dimana setiap partisi tersebut

berukuran 30 pixel pada garis horizontal dan 14 pixel pada garis vertikalnya.

Jumlah titik hitam yang terdapat dalam 9 partisi inilah yang kemudian akan

digunakan sebagai nilai dari suatu ciri. Jadi setiap kelas huruf jawa tersebut

mempunyai 9 ciri yang nilainya tergantung pada jumlah titik hitam yang

terdapat dalam setiap partisi. Untuk lebih jelasnya dibawah ini akan

diberikan gambar suatu sampel huruf “Ha” yang dibagi menjadi 9 partisi

sebagai berikut :

1x 2x 3x

metode jarak minimum dan algoritmarepository.usd.ac.id/27000/2/023114033_full.pdf · 2018. 5....

Documents