TINF

PENGENALAN POLA DALAM FUZZY CLUSTERING DENGAN PENDEKATAN ALGORITMA GENETIKA

TESIS Oleh

AYU NURIANA SEBAYANG 097038005/TINF

PROGRAM STUDI MAGISTER (S2) TEKNIK INFORMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA

MEDAN 2011

Universitas Sumatera Utara


TESIS

Diajukan sebagai salah satu syarat untuk memperoleh gelar Magister Sains dalam Program Studi Magister Teknik Informatika pada Program Studi Magister (S2) Teknik Informatika Fakultas MIPA Universitas Sumatera Utara

Oleh

AYU NURIANA SEBAYANG 097038005/TINF

PROGRAM STUDI MAGISTER (S2) TEKNIK INFORMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA

MEDAN 2011


PENGESAHAN TESIS

: PENGENALAN POLA DALAM

Judul Tesis

FUZZY CLUSTERING DENGAN PENDEKATAN ALGORITMA GENETIKA Nama Mahasiswa Nomor Induk Mahasiswa Program Studi Fakultas

: Ayu Nuriana Sebayang : 097038005 : Magister Teknik Informatika : Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara

Menyetujui Komisi Pembimbing

Syahril Effendi, S.Si, MIT Anggota

Prof. Dr. Tulus Ketua

Ketua Program Studi

Dekan

Prof. Dr. Muhammad Zarlis NIP.19570701 198601 1 003

Dr. Sutarman, Msc NIP.19631026 199103 1 001


PERNYATAAN ORISINALITAS


TESIS

Dengan ini saya nyatakan bahwa saya mengakui semua karya tesis ini adalah hasil kerja saya sendiri kecuali kutipan dan ringkasan yang tiap satunya dijelaskan sumbernya dengan benar.

Medan, 23 Juli 2011

Ayu Nuriana Sebayang NIM. 097038005


PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS

Sebagai sivitas akademis Universitas Sumatera Utara, saya yang bertanda tangan dibawah ini: Nama

: Ayu Nuriana Sebayang

NIM

: 097038005

Program Studi

: Magister Teknik Informatika

Jenis Karya Ilmiah

: Tesis

Demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Sumatera Utara Hak Bebas Royalti Non-Eksklusif (Non-Exclusive Royalty Free Right ) atas Tesis saya yang berjudul:

PENGENALAN POLA DALAM FUZZY CLUSTERING DENGAN PENDEKATAN ALGORITMA GENETIKA Beserta perangkat keras yang ada (jika diperlukan). Dengan Hak Bebas Royalti Non-Ekslusif ini, Universitas Sumatera Utara berhak menyimpan, mengalihkan media,

memformat,

mengelola

dalam

bentuk

data-base,

merawat

dan

mempublikasikan Tesis saya tanpa meminta izin dari saya selama tetap mencatumkan nama saya sebagai penulis dan sebagai pemegang dan atau sebagai pemilik hak cipta.

Demikian pernyataan ini dibuat dengan sebenarnya.

Medan, 23 Juli 2011

Ayu Nuriana Sebayang


Telah diuji pada Tanggal : 27 Juli 2011

PANITIA PENGUJI TESIS KETUA

:

Prof. Tulus

Anggota

:

1. Syahril Effendi, S.Si, MIT 2. Prof. Dr. Herman Mawengkang 3. Prof. Dr. Muhammad Zarlis 4. Syahriol Sitorus, S.Si, M.Si


RIWAYAT HIDUP

DATA PRIBADI

Nama lengkap berikut gelar

: Ayu Nuriana Sebayang, S.Kom

Tempat dan Tanggal Lahir

: Medan, 17 September 1985

Alamat Rumah

: Jl. Puskesmas I gg. Mawar No. 11 Medan

Telepon/Faks/HP

: 085261744566

Email

: [email protected]

Instansi Tempat Bekerja

: STMIK/AMIK Logika Medan

Alamat kantor

: Jl. Yosudarso No. 374 C Medan

Telepon/Faks/HP

: 061-6618572

DATA PENDIDIKAN SD

: SD Negeri 060915 Medan

Tamat

: 1998

SLTP

: SLTP Negeri 9 Medan

Tamat

: 2001

SMU

: SMU Negeri 15 Medan

Tamat

: 2004

Strata-1

: FMIPA USU

Tamat

: 2008


KATA PENGANTAR Puji Syukur Penulis ucapkan kepada Allah SWT atas segala limpahan rahmat dan karunia-Nya sehingga penulis dapat menyelesikan tesis ini dengan judul: PENGENALAN POLA DALAM FUZZY CLUSTERING DENGAN PENDEKATAN ALGORITMA GENETIKA. Dengan selesainya tesis ini, penulis menyampaikan terima kasih sebesarbesarnya kepada: Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc (CTM), Sp.A(K) selaku Rektor Universitas Sumatera Utara yang telah memberikan kesempatan kepada penulis untuk mengikuti dan menyelesaikan pendidikan Program Magister. Dr. Sutarman, M.Sc selaku Dekan FMIPA USU atas kesempatan penulis menjadi mahasiswa pada Program Studi Magister Teknik Informatika. Prof. Dr. Muhammad Zarlis, selaku Ketua Program Studi Magister Teknik Informatika FMIPA Universitas Sumatera Utara. M. Andri Budiman, S.T., M.Comp Sc., M.E.M., selaku Sekretaris Program Studi Magister Teknik Informatika. Prof. Dr. Tulus, selaku Pembimbing Utama yang telah banyak memberikan bimbingan dan arahan serta motivasi kepada penulis. Syahril Effendi, S.Si, M.I.T., selaku Pembimbing Kedua yang telah banyak memberikan bimbingan dan arahan serta motivasi kepada penulis. Seluruh Staff Pengajar yang telah banyak memberikan ilmu pengetahuan selama masa perkuliahan serta Seluruh Staff Pegawai pada Program Magister Teknik Informatika FMIPA Universitas Sumatera Utara. Teristimewa kepada Ayahanda Drs. Djakaria Sebayang, M.Si. dan Ibunda Ruslina Sembiring, yang telah memberikan doa, dukungan, perhatian dan kasih sayang yang tulus serta pengorbanan yang tidak ternilai harganya semenjak penulis dilahirkan hingga menyelesaikan tesis ini. Abang dan adik-adik tersayang serta seluruh keluarga tercinta yang selalu memberikan dukungan kepada penulis.


Ucapan terima kasih juga penulis ucapkan kepada sahabat-sahabat terbaik, Raihan, Ari Eka, Silvia, Tetty, Rosita, Yani Maulita, Ramliana dan rekan-rekan kuliah angkatan ’09 yang telah memberikan semangat kepada penulis. Akhir kata penulis hanya berdoa kepada Allah SWT semoga Allah memberikan limpahan karunia kepada semua pihak yang telah memberikan bantuan, perhatian, serta kerja samanya kepada penulis dalam menyelesaikan tesis ini.

Medan, 23 Juli 2011 Penulis

Ayu Nuriana Sebayang



ABSTRAK

Masalah mengelompokkan data dengan suatu pola dalam cluster untuk menentukan pusat cluster berdasarkan derajat kesamaan yang diukur dari fungsi jarak. Dengan menggunakan mekanisme operator genetik yaitu persilangan dan mutasi populasi dievolusikan melalui fungsi fitness yang diarahkan pada kondisi konvergensi. Algoritma ini dapat diterapkan dalam banyak area fungsi-fungsi optimasi, penerapannya adalah fungsi objektif berbasis fuzzy clustering. Penulis menggunakan Fuzzy C-Means yaitu algoritma pengklusteran untuk mengkluster IPM (Indeks Pembangunan Manusia) dari setiap Propinsi di Indonesia dengan membagi Propinsi dalam beberapa cluster. Pada pendekatan algoritma genetika untuk penyelesaian fuzzy clustering ditempuh pilihan untuk menggunakan pendekatan Prototype-based algorithms, yaitu mengevolusikan matrik pusat c

n

cluster dengan menentukan fungsi fitness Jm( U, V) = ∑ ∑ µ ik Dik (v i − x k ) . 2

i =1 k =1

Kata Kunci : Pengenalan pola, Fuzzy clustering, FCM, Algoritma Genetika.


INTRODUCTION OF PATTERN IN FUZZY CLUSTERING BY GENETIC ALGORITHM APPROACH

ABSTARCT

The classification of data by pattern in a cluster to determine the cluster center based on the equality level measured by distance function. By using genetic operator mechanism, i.e. crossing and population mutation in evolution through the fitness function that directed to the convergence condition. This algorithm can be applied in any optimization function area, its application is fuzzy clustering based objective function. The writer using the Fuzzy C-Means, i.e. clustering algorithm for IPM clustering (Human Development Index) in each Province in Indonesia by classified the provinces into any clusters. In the genetic algorithm approach in solving the fuzzy clustering is conducted by alternative for using the Prototype based algorithm approach, i.e. evolution of cluster center matrix by c

n

determining the fitness function Jm( U, V) = ∑ ∑ µ ik Dik (v i − x k ) . 2

i =1 k =1

Keywords : Introduction of Pattern, Fuzzy Clustering, FCM, Genetic Algorithm


DAFTAR ISI

Halaman PENGESAHAN

iii

PERNYATAAN ORISINALITAS

iv

PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS

v

PENETAPAN PANITIA PENGUJI TESIS

vi

RIWAYAT HIDUP

vii

KATA PENGANTAR

viii

ABSTRAK

x

ABSTRACT

xi

DAFTAR ISI

xii

DAFTAR GAMBAR

xiv

DAFTAR TABEL

xv

BAB I PENDAHULUAN

1

1.1 Latar Belakang Masalah

1

1.2 Perumusan Masalah

3

1.3 Batasan Masalah

4

1.4 Tujuan Penelitian

4

1.5 Manfaat Penelitian

4

BAB II TINJAUAN PUSTAKA

5

2.1 Pengenalan Pola

5

2.2 Teknik Pengenalan Pola

5

2.2.1. Evaluasi Ciri Melalui Ukuran-Ukuran Fuzzy

6

2.2.2. Pendekatan Teoritik Keputusan

7

2.3 Algoritma Genetika

8


2.3.1 Pengertian Algoritma genetika

8

2.3.2 Encoding

9

2.3.3 Fungsi fitness

10

2.3.4 Seleksi

11

2.3.5 Crossover

11

2.3.6 Mutasi

11

2.3.7 Konsep Penggunaan Algoritma Genetika

11

2.4 Logika Fuzzy

12

2.4.1 Pengertian Logika Fuzzy

12

2.4.2 Fungsi Keanggotaan

13

2.4.3 Proses Sistem Fuzzy

14

2.5 Fuzzy Cluestering

14

2.5.1 Algoritma Fuzzy Clustering dengan Pendekatan Algoritma genetika (Genetic Guided Algorithm for Fuzzy C-Means = GGA-FCM)

15

2.5.2. Parameter dalam Algoritma Genetika

18

2.5.3. Validitas Clustering dan Classification Rate

18

2.5.4. Algoritma Fuzzy clustering konvensional

19

2.5.5. Fuzzy C-Means

19

BAB III METODOLOGI PENELITIAN

22

3.1. Rancangan

22

3.2. Pelaksanaan Penelitian

22

3.3. Variabel Yang Diamati

22

3.3.1. Ukuran Fuzzy

23

3.3.2. Diagram Alir

23

BAB IV ANALISIS DAN PEMBAHASAN

26

4.1. Data Perkembangan Indeks Pembangunan Manusia untuk tingkat propinsi Indonesia

26

4.1.1. Metode Perhitungan IPM

26

4.2. Analisis Cluster IPM

28


4.2.1. Pengolahan Data

28

4.2.2. Analisis dengan algoritma genetika

35

A. Penentuan populasi

35

B. Penentuan Fitness

35

BAB V KESIMPULAN DAN SARAN

38

5.1. Kesimpulan

38

5.2. Saran

38

DAFTAR PUSTAKA

39


TINF

Recommend Documents