TESIS OPTIMASI PUSAT CLUSTER K-PROTOTYPE DENGAN ALGORITMA GENETIKA

TESIS

OPTIMASI PUSAT CLUSTER K-PROTOTYPE DENGAN ALGORITMA GENETIKA

NI LUH GEDE PIVIN SUWIRMAYANTI

PROGRAM PASCASARJANA UNIVERSITAS UDAYANA DENPASAR 2014

TESIS

OPTIMASI PUSAT CLUSTER K-PROTOTYPE DENGAN ALGORITMA GENETIKA

NI LUH GEDE PIVIN SUWIRMAYANTI NIM 1191761014

PROGRAM MAGISTER PROGRAM STUDI TEKNIK ELEKTRO PROGRAM PASCASARJANA UNIVERSITAS UDAYANA DENPASAR 2014

OPTIMASI PUSAT CLUSTER K-PROTOTYPE DENGAN ALGORITMA GENETIKA

Tesis untuk Memperoleh Gelar Magister pada Program Magister, Program Studi Teknik Elektro, Program Pascasarjana Universitas Udayana

NI LUH GEDE PIVIN SUWIRMAYANTI NIM 1191761014

PROGRAM MAGISTER PROGRAM STUDI TEKNIK ELEKTRO PROGRAM PASCASARJANA UNIVERSITAS UDAYANA DENPASAR 2014 ii

iii

Tesis Ini Telah Diuji pada Tanggal 25 April 2014

Panitia Penguji Tesis Berdasarkan SK Rektor Universitas Udayana, No.: 1201/UN14.4/HK/2014, Tanggal 24 April 2014

Ketua

: Dr. I Ketut Gede Darma Putra, S.Kom,. MT

Anggota

:

1.

I Nyoman Satya Kumara, ST., M.Sc., PhD

2.

Prof. Ir. Rukmi Sari Hartati, MT., PhD

3.

Dr. Eng. Putu Agung Bayupati, ST., MT

4.

Ni Made Ary Esta Dewi Wirastuti, ST,. MSc,.PhD

iv

SURAT PERNYATAAN BEBAS PLAGIAT

Saya yang bertanda tangan dibawah ini : Nama

: Ni Luh Gede Pivin Suwirmayanti

NIM

: 1191761014

Program Studi

: Magister Teknik Elektro

Judul Tesis

: Optimasi Pusat Cluster K-Prototype dengan Algortima Genetika

Dengan ini menatakan bahwa karya ilmiah Tesis ini bebas plagiat. Apabila di kemudian hari terbukti plagiat dalam karya ilmiah ini, maka saya bersedia menerima sanksi sesuai peraturan Mendiknas RI No. 17 tahun 2010 dan Peraturan Perundang-undangan yang berlaku

Denpasar, 20 Juni 2014 Yang membuat pernyataan,

Ni Luh Gede Pivin Suwirmayanti

v

KATA PENGANTAR Puji syukur penulis panjatkan kehadirat Tuhan Yang Maha Esa atas segala berkah, semangat, kekuatan, dan karunia yang telah diberikan-Nya, sehingga penulis dapat menyelesaikan penyusunan laporan tesis yang berjudul “Optimasi Pusat Cluster K-Prototype Dengan Algoritma Gnetika”. Dalam penyusunan laporan tesis ini penulis banyak sekali mendapatkan bantuan baik berupa pengetahuan maupun moril dari berbagai pihak, sehingga akhirnya penulis dapat menyelesaikan tesis ini. Mengingat hal tersebut, penulis ingin mengucapkan terima kasih yang sebesar-besarnya kepada berbagai pihak, antara lain: 1. Ibu Prof. Dr. dr. A.A Raka Sudewi, Sp.S (K), sebagai Direktur Program Pasca Sarjana Univeristas Udayana. 2. Ibu Prof. Ir. Ida Ayu Dwi Giriantari, M.Eng.Sc.,Ph.D, sebagai Ketua Program Magister Program Studi Teknik Elektro Program Pasca Sarjana Universitas Udayana. 3. Bapak Dr. IKG Darma Putra, S.Kom., MT, selaku pembimbing I yang telah banyak membantu dalam memberikan ilmu, bimbingan, saran dan motivasi dalam menyelesaikan laporan tesis ini. 4. Bapak I Nyoman Satya Kumara, ST., M.Sc., PhD, selaku pembimbing II yang telah memberikan bimbingan, saran dan motivasi dalam menyelesaikan tesis ini. 5. Bapak dan Ibu dosen Program Studi Teknik Elektro Program Pasca Sarjana Universitas Udayana beserta staff dan karyawan. 6. Bapak I Wayan Budi Sentana, ST., M.Kom, atas ide, waktu yang diluangkan untuk bimbingan dan motivasi yang telah diberikan sehingga penulis dapat menyelesaikan tesis ini. 7. Bapak, Ibu dan Keluarga yang selalu memberikan doa, dukungan, materi dan motivasi sehingga penulis bisa menyelesaikan studi ini. 8. Teman-teman Dosen, Komang Budiarta, Kusuma Wardana, Bapak Adi Purwantara, Rosa, Melati, Ecik. yang senantiasa memberikan bantuan, dukungan, dan motivasi untuk menyelesaikan studi ini 9. Seluruh pihak yang tidak dapat penulis sebutkan satu-persatu, atas partisipasi dan kontribusinya terhadap penyusunan laporan tesis ini. Akhirnya penulis mohon maaf atas segala keterbatasan yang ada dalam laporan tesis ini. Semoga tesis ini dapat memberikan kontribusi positif bagi semua pihak.

Denpasar, Juni 2014 Penulis

vi

ABSTRAK Teknik clustering saat ini telah banyak digunakan untuk mengatasi permasalahan yang terkait dengan segementasi data. Implementasi clustering ini dapat diterapkan pada berbagai bidang sebagai contoh dalam hal pemasaran, clustering dapat digunakan sebagai metode untuk mengelompokkan data. Tujuan utama dari metode cluster adalah pengelompokan sejumlah data atau obyek ke dalam cluster(group) sehingga dalam setiap cluster akan berisi data yang semirip mungkin. Dalam proses clustering, secara umum tipe data yang diolah adalah tipe data numerik, namun pada kenyataannya proses pengelompokan data tidak hanya menggunakan tipe data numerik, terdapat juga tipe data kategorikal. Untuk itu penulis menggunakan metode K-Prototype yang dioptimasi dengan Algortima Genetika dimana data uji yang digunakan adalah Data German Credit yang memiliki tipe data numerikal dan kategorikal. Dalam penelitian dilakukan perbandingan kinerja antara metode K-Prototype dengan Algoritma Genetika, dengan metode K-Prototype Tanpa Algortima Genetika, dan metode K-Means. Dari beberapa hasil percobaan yang dilakukan metode K-Prototype dengan Algoritma Genetika menghasilkan hasil yang terbaik dari metode K-Prototype tanpa Algortima Genetika, dan metode K-Means. Kata kunci: Clustering, Optimasi, K-Prototype, Algoritma Genetika.

vii

ABSTRACT Nowadays the clustering technique has been used to overcome problems connected with data segmentation. This clustering implementation can be applied on many fields such as in marketing, clustering can be used as a method to classify data. The main purpose of the clustering method is to classify a sum of data or objects into cluster (group) so that in each cluster will contain similar data. Generally, the processed data in clustering process is the type of numerical data. However, in reality, the classification process is not only using numerical data, but also using categorical data. Therefore, the author used KPrototype which is optimized with Genetic Algorithm. The testing data were Credit Germany Data which has both numerical and categorical data. In this research, the performance between the K-Prototype method with the Genetic Algorithm was compared to the K-Prototype method without the Genetic Algorithm and K-Means method. According to the testing process, it is obtained that the K-Prototype method with Genetic Algorithm is better than the KPrototype method without Generic Algorithm and K-Means method. Keywords: Clustering, Optimization, K-Prototype, Genetic Algorithm.

viii

DAFTAR ISI

SAMPUL DALAM................................................................................................. i PRASYARAT GELAR ......................................................................................... ii LEMBAR PERSETUJUAN ................................................................................ iii PENETAPAN PANITIA PENGUJI .................................................................. iiv SURAT PERNYATAAN BEBAS PLAGIAT ..................................................... v KATA PENGANTAR .......................................................................................... vi ABSTRAK ........................................................................................................... vii ABSTRACT ......................................................................................................... viii DAFTAR ISI......................................................................................................... ix DAFTAR TABEL ................................................................................................ xi DAFTAR GAMBAR ........................................................................................... xii DAFTAR ISTILAH ........................................................................................... xiv BAB I PENDAHULUAN ............................................................................... 1 1.1 Latar Belakang ......................................................................................... 1 1.2 Rumusan Masalah .................................................................................... 6 1.3 Batasan Masalah ....................................................................................... 6 1.4 Tujuan Penelitian...................................................................................... 7 1.5 Manfaat Penelitian.................................................................................... 7 1.6 Keaslian Penelitian ................................................................................... 7 1.7 Sistematika Penulisan ............................................................................... 8 BAB II KAJIAN PUSTAKA ......................................................................... 10 2.1 State of The Art ....................................................................................... 10 2.2 Algoritma Genetika ................................................................................ 13 2.2.1 Siklus Algoritma Genetika .............................................................. 20 2.2.2 Teknik Encoding/Decoding Gen dan Individu ............................... 24 2.2.3 Representasi Kromosom ................................................................. 27 2.2.4 Membangkitkan Populasi Awal ...................................................... 29 2.2.5 Nilai Fitness .................................................................................... 30 2.2.6 Elitisme ........................................................................................... 31 2.2.7 Seleksi ............................................................................................. 31 2.3 Operator Genetika .................................................................................. 37 2.3.1 Operator Reproduksi ....................................................................... 37 2.4 Clustering ............................................................................................... 48 2.4.1 Tipe Cluster .................................................................................... 54 2.5 Algoritma Clustering K-Prototype ......................................................... 57 2.6 Cost Function Criterion ......................................................................... 59 BAB III METODE PENELITIAN................................................................. 63 3.1 Tempat dan Waktu Penelitian ................................................................ 63 3.2 Alur Analisis .......................................................................................... 63 3.3 Studi Pustaka .......................................................................................... 64 3.4 Pengumpulan Data ................................................................................ 65 3.5 Gambaran Umum Sistem ....................................................................... 66 ix

3.5.1 Data Uji ........................................................................................... 67 3.5.2 Inputan Kategori ............................................................................. 70 3.5.3 Clustering K-Prototype dengan Algoritma Genetika...................... 71 3.5.4 Clustering K-Prototype Tanpa GA ................................................. 77 3.5.5 Clustering K-Means ........................................................................ 79 3.5.6 Pengujian Total Cost ....................................................................... 82 3.5.7 Hasil ................................................................................................ 83 3.5.8 Deskripsi ......................................................................................... 83 3.6 Instrumen Penelitian ............................................................................... 84 BAB IV HASIL DAN PENGUJIAN .............................................................. 85 4.1 Antarmuka Sistem .................................................................................. 85 4.2 Antarmuka Aplikasi Clustering ............................................................. 85 4.2.1 Input Dataset. .................................................................................. 86 4.2.2 Inputan Kategori ............................................................................. 88 4.2.3 Eksekusi Program ........................................................................... 89 4.2.4 Pengujian Total Cost ..................................................................... 104 4.2.5 Hasil Percobaan ............................................................................ 108 4.2.6 Antarmuka Aplikasi Deskripsi ...................................................... 112 BAB V KESIMPULAN DAN SARAN ....................................................... 120 5.1 Kesimpulan........................................................................................... 120 5.2 Saran ..................................................................................................... 121 DAFTAR PUSTAKA ........................................................................................ 122

x

DAFTAR TABEL Tabel 2.1 Kromosom dan Nilai fitnessnya ............................................................ 34 Tabel 2.2 Kondisi kromosom sebelum dan sesudah di ranking ............................ 35 Tabel 3.1 Spesifikasi German Credit Dataset ....................................................... 69

xi

DAFTAR GAMBAR Gambar 2.1 Visualisasi gen, allele, kromosom, individu, dan populasi pada ...... 19 Gambar 2.2 Siklus algoritma genetika yang diperkenalkan oleh David Goldberg21 Gambar 2.3 Siklus algoritma genetika yang diperbaiki oleh Zbigniew Michalewicz .......................................................................................................... 21 Gambar 2.4 Struktur Umum Algoritma Genetik .................................................. 22 Gambar 2.5 Contoh Kromosom Biner .................................................................. 27 Gambar 2.6 Contoh Kromosom Float .................................................................. 28 Gambar 2.7 Contoh Kromosom Nilai ................................................................... 28 Gambar 2.8 Contoh Kromosom Permutasi ........................................................... 29 Gambar 2.9 Grafik Lokal Optimim (T.Sutojo, Edy Mulyanto, Dr. Vincent Suhartono, 2011) ................................................................................................... 32 Gambar 2.10 Contoh probabilitas kromosom pada roda roullete ......................... 34 Gambar 2.11 Seleksi dengan Roulette-Wheel ....................................................... 35 Gambar 2.12 Pertukaran secara langsung ............................................................. 39 Gambar 2.13 Pertukaran Secara Aritmatika ......................................................... 40 Gambar 2. 14 Proses one point crossover ............................................................. 41 Gambar 2. 15 Proses two point crossover............................................................. 42 Gambar 2.16 Proses n point crossover.................................................................. 42 Gambar 2.17 Proses uniform crossover ................................................................ 43 Gambar 2.18 Contoh proses mutasi ...................................................................... 46 Gambar 2.19 Clustering berdasarkan warna ......................................................... 51 Gambar 2.20 Clustering berdasarkan bentuk ........................................................ 51 Gambar 2.21 Clustering berdasarkan jarak........................................................... 52 Gambar 2.22 Merupakan ilustrasi prinsip Clustering. .......................................... 52 Gambar 2.23 Beberapa cara menentukan cluster bagi dataset yang sama ........... 53 Gambar 2.24 Algoritma Clustering ...................................................................... 53 Gambar 2.25 Tipe cluster Well-Separated. ........................................................... 54 Gambar 2.26 Tipe clusterPrototype-Based/Center-Based ................................... 55 Gambar 2.27 Tipe cluster Graph-Based ............................................................... 55 Gambar 2.28 Tipe Cluster Density-Based ............................................................ 56 Gambar 2.29 Tipe Cluster Shared-Property ......................................................... 56 Gambar 3.1 Alur Analisi Penelitian ...................................................................... 64 Gambar 3.2 Gambaran Umum Sistem .................................................................. 66 Gambar 3. 3 Contoh Data Uji ............................................................................... 68 Gambar 3.4 Clustering K-Prototype dengan GA .................................................. 72 Gambar 3.5 Contoh Kromosom ............................................................................ 73 Gambar 3.6 Inisialisasi awal ................................................................................. 74 Gambar 3.7 Flowchart K-Means Clustering ......................................................... 81 Gambar 4.1 Tampilan Aplikasi Clustering ........................................................... 85 Gambar 4.2 Tampilan Dataset .............................................................................. 86 Gambar 4.3 Pemilihan Data Uji. .......................................................................... 86 Gambar 4.4 Data telah diload ............................................................................... 87 Gambar 4.5 Tampilan Penetapan Variabel ........................................................... 88 Gambar 4.6 Tampilan K-Prototype Dengan GA .................................................. 90 xii

Gambar 4. 7 Hasil Uji K-Protoype dengan GA .................................................... 90 Gambar 4.8 Inisialisasi kromosom awal ............................................................... 91 Gambar 4.9 Inisialisasi awal prototype (a) Nilai kategorikal dan numerik pada kromosom (b) Nilai kategorikal pada kromosom (c) nilai numerik pada kromosom ............................................................................................................. 93 Gambar 4.10 Hasil Nilai Fitness ........................................................................... 95 Gambar 4.11 Pengkopian Individu Terbaik .......................................................... 96 Gambar 4.12 Hasil Roulette-Wheel ....................................................................... 96 Gambar 4.13 Hasil pindah silang .......................................................................... 97 Gambar 4.14 Hasil Mutasi pada seluruh kromosom ............................................. 99 Gambar 4.15 Tampilan K-Prototype Tanpa GA ................................................. 100 Gambar 4.16 Hasil Uji K-Prototype Tanpa GA ................................................. 102 Gambar 4.17 Hasil Uji dengan K-Means. ........................................................... 103 Gambar 4.18 Total Cost K-Protoype dengan GA ............................................... 105 Gambar 4.19 Total Cost K-Protoype tanpa GA ................................................. 106 Gambar 4.20 Total Cost K-Means ...................................................................... 107 Gambar 4.21 Grafik Hasil ................................................................................... 109 Gambar 4.22 Tampilan Aplikasi Deskripsi......................................................... 112 Gambar 4.23 Load Data ...................................................................................... 113 Gambar 4.24 Hasil Load Data ............................................................................ 114 Gambar 4.25 Hasil Rekap Nilai Per Cluster ....................................................... 115

xiii

DAFTAR ISTILAH Alelle Cluster Clustering

Clustering Criterion Cost Function Criterion Crossover Elitisme Encoding/Decoding Evaluasi Fitness Gen Generasi German Credit Dataset Individu Inisialisasi Populasi Awal K-Means

K-Prototype

Kromosom Mutasi Nilai Fitness Populasi

Pre-Evaluasi

: Nilai suatu gen. : Obyek didalam grup yang memiliki kemiripan satu dengan lainnya. : Suatu teknik dalam data mining yang digunakan untuk memasukkan data ke dalam grup yang bersesuaian. : Suatu metode pengukuran hasil clustering : Biaya yang dihabiskan untuk menempatkan object pada cluster yang bersesuaian. : Mempersiapkan individu baru pada masingmasing populasi melalui proses pindah silang : Prosedur untuk meng-copy individu yang mempunyai nilai fitness tertinggi : Mengkodekan nilai gen-gen pembentuk individu : Mengevaluasi nilai dari fungsi tujuan : Variabel dasar yang membentuk suatu kromosom. : Satu satuan siklus proses evolusi : Dataset untuk penilaian kelayakan pemberian kredit. : Kumpulan gen, bisa dikatakan sama dengan kromosom. : Menentukan sejumlah kromosom awal yang akan digunakan untuk komputasi selanjutnya : Metode Klasifikasi tak terawasi (unsupervised) yang membagi data ke dalam satu atau lebih cluster atau kelompok. : Algoritma yang digunakan untuk melakukan clustering pada data dengan tipe campuran numerik dan kategorikal : Gabungan dari gen-gen yang membentuk arti tertentu. : Proses mengubah nilai dari satu atau beberapa gen dalam suatu kromosom : Nilai dari fungsi tujuan : Sekumpulan individu yang akan diproses secara bersama-sama dalam satu siklus proses evolusi. : Mempersiapkan dataset yang akan diclustering dan menyesuaikannya dengan model kromosom yang ada xiv

Pusat Cluster

Roulette-Wheel

Seleksi

: Centroid dan medoid. Centroid adalah rataan semua titik dalam cluster, sedangkan medoid adalah titik yang paling mewakili cluster : Metode seleksi dimana masing-masing kromosom menempati potongan lingkaran pada roda roulette secara proporsional sesuai dengan nilai fitness-nya : Suatu urutan proses dalam algortima genetika untuk mendapatkan calon induk yang baik.

xv

BAB I PENDAHULUAN 1.1

Latar Belakang Analisa Cluster saat ini merupakan salah satu metode yang banyak

digunakan untuk melakukan pengelompokan data menjadi segmen–segmen yang lebih kecil.

Analisa Cluster merupakan suatu teknik yang digunakan untuk

membagi sekumpulan obyek ke dalam k kelompok sehingga nilai dalam setiap kelompok adalah homogen dengan mengacu kepada atribut tertentu berdasarkan kriteria tertentu (Huang dkk, 2007). Kesamaan nilai (homogenity) dalam setiap segmen yang diwakili oleh cluster mengGambarkan kesamaan pola perilaku pelanggan (Huang dkk, 2007). Dengan analisa cluster ini, kesamaan pola prilaku pelanggan dapat digali melalui cluster-cluster yang terbentuk. Semakin akurat cluster yang terbentuk maka akan semakin jelas kesamaan pola prilaku dari pelanggan. Sehingga dengan demikian, para pelaku bisnis dapat menentukan strategi pemasaran dengan lebih akurat, berdasarkan pada pola prilaku pelanggan yang didapatkan dari proses analisa cluster tersebut.

Teknik clustering saat ini juga telah banyak digunakan untuk mengatasi permasalahan yang terkait dengan segementasi data. Implementasi clustering ini dapat diterapkan pada berbagai bidang sebagai contoh dalam hal pemasaran, clustering dapat digunakan sebagai metode untuk mengelompokkan pelanggan yang memiliki kesamaan dalam perilaku belanja. Tujuan utama dari metode

1

2

cluster adalah pengelompokan sejumlah data atau obyek ke dalam cluster (group) sehingga dalam setiap cluster akan berisi data yang semirip mungkin. Dalam clustering, sistem berusaha menempatkan obyek yang mirip (memiliki jarak yang dekat) dalam satu cluster dan membuat jarak antar cluster yang sejauh mungkin. Ini berarti obyek dalam satu cluster sangat mirip satu sama lain dan berbeda dengan obyek dalam cluster-cluster yang lain. Clustering adalah salah satu teknik unsupervised learning dimana fase training tidak diperlukan untuk metode ini.

Berkembangnya penelitian tentang teknik clustering, telah ditemukan berbagai algoritma yang bisa menghasilkan cluster dengan tingkat akurasi yang semakin baik. Salah satu teknik yang diusulkan oleh Liu dkk, tahun 2008 adalah menggunakan algoritma genetika yang dikombinasikan dengan metode K-Means Clustering, untuk mendapatkan jumlah cluster yang optimal. Kombinasi Metode GA dan K-Means juga dimanfaatkan oleh Kim dkk, tahun 2008 untuk pengelompokan pelanggan dalam membuat recomender system pada online shoping market. Dari hasil penelitian tersebut, bisa disimpulkan bahwa GA KMeans mampu menghasilkan pengelompokan (clustering) yang lebih baik dibandingkan dengan Self Organising Map (SOM) yang berbasis neural network. (Min Feng, Zhenyan-wang, 2011) melakukan penelitian untuk mengoptimalkan Algoritma K-Means dalam menentukan pusat awal cluster, dimana hasil penelitian menunjukkan bahwa algoritma K-Means memiliki kelemahan tidak hanya memiliki ketergantungan pada data awal, tetapi juga konvergensi yang cepat dan kualitas clustering. Untuk memperoleh cluster yang efektif dan akurat,

3

maka Min Feng dan Zhenyan-wang mengoptimalkan Algoritma K-Means (PKM) dengan Algoritma Genetika menjadi sebuah Algoritma Hibrid (PGKM). Percobaan menunjukkan bahwa algoritma itu memiliki kualitas cluster dan performance yang baik.

Publikasi penelitian Liu dkk, tahun 2008 menggunakan algoritma genetik (Genetic Algorithm, GA) dan dikombinasikan dengan metode clustering yang sangat populer, yaitu K-Means untuk menemukan variabel yang valid dan jumlah cluster optimal secara simultan. Hasil penelitian menunjukkan, gabungan algoritma genetik dan K-Means berhasil menghilangkan variabel yang tidak relevan

dan menghasilkan jumlah cluster secara otomatis, dan berhasil

meningkatkan hasil pengelompokan pelanggan secara signifikan. Menurut K.Arun Prabha, R.Saranya tahun 2011 dengan penelitinanya yang memperbaiki K-Means Clustering dengan menggunakan algoritma genetik, dimana disebutkan Clustering K-Means adalah sebuah algoritma clustering yang populer berdasarkan hasil partisi data. Untuk meningkatkan kualitas dari cluster K-Means menggunakan algoritma genetika dan hasil penelitian menunjukkan bahwa algoritma yang diajukan mencapai hasil yang lebih baik. Chittu.V,N.Sumathi tahun 2011 dalam penelitiannya menyebutkan ada sebuah algoritma Clustering baru yang diusulkan yaitu Modified Genetic Algorithm Initializing K-Means (MGAIK). MGAIK diinspirasi oleh sebuah metode initialization algoritma genetik untuk K-Means clustering tapi beberapa fitur perbaikan dari GAIK. Akhirnya, ketika perbandingan yang dilakukan mendapatkan hasil bawha MGAIK lebih baik dari yang sederhana algoritma genetika .

4

Keseluruhan penelitian tersebut di atas, belum ada penelitian yang memperhatikan kemungkinan munculnya kesalahan pada data karena adanya perbedaan tipe data dalam dataset yang digunakan. Misalnya dalam penelitian yang dilakukan oleh Liu dkk, data uji yang digunakan memiliki tipe data campuran yaitu data dengan tipe numerik dan kategorikal. Sementara itu penelitian yang dilakukan oleh Huang tahun 1997 dan Huang tahun 1998 menunjukkan bahwa, penanganan data kategorikal dengan metode untuk data numerik tidak selalu memberikan hasil yang berguna, karena tidak semua data categorical di dunia nyata disajikan dalam bentuk terurut (ordered).

Penelitian Huang tahun 1997 tersebut diusulkan sebuah algoritma yang disebut dengan K-Prototype, untuk menangani clustering pada data dengan tipe campuran numerik dan kategorikal. Penelitian ini telah menyajikan Algoritma KPrototype untuk cluster data set yang besar yang ada di dunia nyata. K-Prototype adalah salah satu metode clustering yang berbasis partitioning. Algoritma ini adalah hasil pengembangan atau kombinasi antara K-Means dan K-Modes Clustering untuk menangani clustering pada data dengan campuran atribut bertipe numerik dan kategorikal. K-Protoype memiliki keunggulan karena algoritmanya yang tidak terlalu kompleks dan mampu menangani data yang besar lebih baik dibandingkan dengan algoritma yang berbasis hierarki (Huang,1998).

Hasil yang diperoleh dari optimal dengan metode Clustering K-Prototype akan dioptimasi dengan Algoritma Genetika. Algoritma Genetika sangat tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan sukar

5

diselesaikan dengan menggunakan metode konvensional. Algoritma Genetika adalah suatu metode algoritma optimalisasi dan pencarian yang didasarkan pada prinsip genetika dan seleksi natural (Haupt.2004). Algoritma Genetika sebenarnya terinspirasi dari prinsip genetika dan seleksi alam (teori Darwin) yang ditemukan di Universitas Michigan, Amerika Serikat oleh John Holland melalui sebuah penelitian dan dipopulerkan oleh salah satu muridnya, David Goldberg. Algoritma genetika merupakan algoritma yang berusaha menerapkan pemahaman mengenai evolusi alamiah pada tugas-tugas pemecahan-masalah (problem solving).

Berdasarkan pada fakta-fakta yang didapatkan dari beberapa penelitian sebelumnya maka penulis melalui penelitian ini mengusulkan metode K-Prototype yang dioptimasi dengan Algoritma Genetika untuk melakukan optimasi pada pusat cluster, untuk mendapatkan pusat cluster yang optimal, sehingga akurasi dari cluster menjadi lebih baik dimana data uji yang aka digunakan adalah German Credit Dataset. German Credit Dataset adalah dataset yang banyak digunakan dalam permasalahan klasifikasi untuk penilaian kelayakan pemberian kredit.

6

1.2

Rumusan Masalah Berdasarkan latar belakang di atas, maka dapat dirumuskan masalah dari

penelitian ini adalah sebagai berikut : 1.

Bagaimana menggabungkan metode clustering K-Prototype dan Algoritma Genetika, dengan tujuan menghasilkan pengelompokan data yang lebih baik dan memiliki kesamaan ciri atau karakteristik didalam cluster yang semakin erat.

2.

Bagaimana unjuk kerja metode gabungan K-Prototype dan Algoritma Genetika dalam pembentukan pusat cluster, jika dibandingkan dengan metode K-Prototype tanpa Algoritma Genetika. Selanjutnya dibandingkan dengan metode K-Means. Ketiga Metode tersebut akan diuji dengan menggunakan tipe data uji campuran numerik dan kategorikal yang sama.

1.3

Batasan Masalah Dengan luasnya cakupan yang dapat terkait dengan tesis ini dan untuk

keseragaman pemahaman dalam penelitian, maka terdapat batasan-batasan yang perlu diberlakukan pada penelitian ini. Adapun batasan

permasalahan

yang

penulis angkat pada penelitian ini adalah: 1.

Optimasi Pusat Cluster pada K-Prototype menggunakan Algoritma Genetika dengan studi kasus Segmentasi Pasar dengan menggunakan data uji : German Credit Dataset, dataset tersebut adalah dataset yang umum digunakan untuk klasifikasi pemberian kredit, yang terdiri dari 1000 record dengan 20 variabel.

7

2.

Pengujian hasil akan dibandingkan dengan Metode K-Prototype tanpa Algoritma Genetika, dan Metode K-Means Clustering.

1.4

Tujuan Penelitian Tujuan yang diharapkan setelah penulis melakukan penelitian adalah

Mengimplementasikan metode K-Prototype dan Genetic Algorithm (GA) untuk melakukan optimasi pada pusat cluster, khususnya pada data set dengan tipe data campuran numerik dan kategorikal, sehingga diharapkan dapat menghasilkan pengelompokan (cluster) data yang lebih baik.

1.5

Manfaat Penelitian Manfaat yang bisa didapatkan dari penelitian ini adalah penggabungan

metode clustering K-Prototype dan Algortima Genetika, dapat digunakan untuk membentuk cluster-cluster yang memiliki kesamaan karakteristik yang semakin kompak dan erat, sehingga nantinya dapat dimanfaatkan oleh para pelaku bisnis untuk membuat strategi pemasaran yang lebih fokus kepada cluster-cluster yang terbentuk, dengan melihat karakteristik yang ada pada setiap cluster.

1.6

Keaslian Penelitian Penelitian terkait yang sejenis adalah penelitian yang dilakukan oleh Min

Feng, Zhenyan Wang-(2011), yang berjudul A Genetic K-Means Clustering Algorithm Based on the Optimized

Initial Centers, penelitian ini bertujuan

mengoptimalkan initial centers pada algoritma K-Means untuk mementukan pusat

8

awal cluster. Penelitian yang dilakukan oleh Chittu.V, N.Sumathi (2011) yang berjudul A Modified Genetic Algorithm Initializing K-Means Clustering. Dalam penelitian ini disebutkan ada sebuah algoritma Clustering baru yang diusulkan yaitu Modified Genetic Algorithm Initializing K-Means (MGAIK). MGAIK diinspirasi oleh sebuah metode initialization Algoritma Genetik untuk K-Means Clustering tapi beberapa fitur perbaikan dari GAIK. Berdasarkan pada beberapa hasil penelitian yang telah dilakukan sebelumnya, maka penulis mengusulkan pendekatan baru yaitu algoritma KPrototype yang dioptimasi dengan Algoritma Genetika untuk menghasilkan pusat cluster yang optimal. Penelitian terkait yang menggunakan metode berbeda penulis rangkum pada state of the art yang ada pada Bab II.

1.7

Sistematika Penulisan Sistematika penulisan penelitian adalah sebagai berikut.

BAB I : PENDAHULUAN Bab ini memaparkan mengenai latar belakang, rumusan masalah, tujuan, manfaat, ruang lingkup dan batasan masalah, keaslian penelitian serta sistematika penulisan dalam menyusun laporan penelitian. BAB II: TINJAUAN PUSTAKA Bab ini terdiri dari state of the art yang berisi penelitian sebelumnya yang akan dijadikan perbandingan untuk penelitian ini, serta teori penunjang yang digunakan membantu memecahkan permasalahan penjadwalan. BAB III : METODE PENELITIAN

9

Bab ini berisikan alur analisis dari penelitian, tempat dan waktu penelitian, tipe data, bentuk data, sumber data serta metode perancangan pembuatan sistem seperti pemodelan sistem. BAB IV : PEMBAHASAN Bab ini berisikan pembahasan mengenai analisis dari penelitian, pengukuran kinerja metode yang digunakan pada penelitian dan implementasi sistem dengan data dari perusahaan tempat studi kasus. BAB V : KESIMPULAN Bab ini berisikan kesimpulan dan saran dari hasil penelitian ini.

BAB II KAJIAN PUSTAKA

2.1

State of The Art Beberapa penelitian yang telah dilakukan sebelumnya terkait dengan judul

yang diangkat: Kombinasi Metode GA dan K-Means juga dimanfaatkan oleh Kim dkk, tahun 2008, untuk pengelompokan pelanggan dalam membuat recomender sistem pada online shoping market. Dari hasil penelitian tersebut, bisa disimpulkan bahwa GA K-Means mampu menghasilkan pengelompokan (Clustering) yang lebih baik dibandingkan dengan Self Organising Map (SOM) yang berbasis neural network. Penelitian dengan judul A Genetic K-Means ClusteringAlgorithm Based on the Optimized Initial Centers, oleh Min Feng, Zhenyan Wang pada tahun 2011. Dalam penelitian tersebut menjelaskan mengenai optimalkan initial centers sebuah Algoritma K-Means untuk mementukan pusat awal cluster. Percobaan menunjukkan bahwa alogaritma K-Means memiliki kelemahan tidak hanya memiliki ketergantungan pada data awal, tapi juga konvergensi yang cepat dan kualitas Clustering. Untuk memperoleh cluster yang efektif dan akurat, maka dioptimalkannya Algoritma K-Means (PKM) yang digabunggkan dengan Algoritma Genetik menjadi sebuah Algoritma Hibrid (PGKM). Percobaan menunjukkan bahwa alogaritma itu memiliki kualitas cluster dan performance yang baik.

10

11

Publikasi metode K-Means Clustering menggunakan Genetic Algorithm, oleh K.Arun Prabha, R.Saranya tahun 2011 yang mengangkat penelitian yang berjudul Refinement of K-Means Clustering Using Genetic Algorithma. Dimana dalam penelitian tersebut menyajikan Clustering K-Means adalah sebuah algoritma Clustering yang populer berdasarkan hasil partisi data. Ada beberapa kekurangan itu, seperti menentukan jumlah cluster di pertama, sensitif untuk menentukan kondisi awal, dan memungkinkan

suatu cluster tidak memiliki

anggota. Untuk meningkatkan kualitas dari cluster K-Means menggunakan algoritma genetik. Hasil penelitian menunjukkan bahwa algoritma yang diajukan mencapai hasil yang lebih baik daripada yang konvensional dan kernel algoritma K-Means bila diterapkan pada data riil set . Bashar Al-Shboul, and Sung-Hyon Myaeng pada tahun 2009, melakukan penelitian yang berjudul Initializing K-Means using Genetic Algorithms. K-Means (KM). Dalam penelitiannya membahas mengenai salah satu algoritma utama yang digunakan dalam Clustering. Masalah lain KM adalah konvergen menuju local minima. Ketika membandingkan hasil eksperimen K-Means, GKA, GAIK dan KIGA kita menemukan bahwa KIGA lebih baik daripada yang lain. Seperti yang ditunjukkan oleh hasil pada semua dataset KIGA siap untuk mencapai akurasi Clustering yang tinggi jika dibandingkan dengan algoritma lainnya. Dalam penelitian ini, mengusulkan dua algoritma untuk memecahkan masalah inisialisasi,

KM

menginisialisasi

algoritma

menginisialisasi genetik algoritma (KIGA).

genetik

(GAIK)

dan

KM

12

Penelitian yang berjudul A Modified Genetic Algorithm Initializing KMeans Clustering, oleh Chittu.V, N.Sumathi pada tahun 2011. Dalam penelitian ini disebutkan ada Sebuah algoritma Clustering baru yang diusulkan yaitu Modified Genetic Algorithm Initializing K-Means ( MGAIK). MGAIK diinspirasi oleh sebagai sebuah metode initialization algoritma genetik untuk K-Means Clustering tapi beberapa fitur perbaikan dari GAIK. Karya ini menyajikan yang Modifikasi Genetic Algorithm (MGA) dengan beberapa parameter subpopulasi dan dinamis. Untuk menunjukkan efektivitas dan efisiensi algoritma, sebuah perbandingan tersebut dilakukan di antara K-Means, GAIK dan MGAIK. Akhirnya, ketika membandingkan hasil percobaan K-Means, GAIK dan MGAIK jelas bahwa MGAIK lebih baik dari yang sederhana algoritma genetik. Zhexue Huang tahun 1998 mempubilkasikan penelitiannya yang berjudul Extensions to the K-Means Algorithm for Clustering Large Data Sets with Categorical Values. Dalam penelitian ini menyajikan dua algoritma yang memperluas algoritma K-Means untuk domain kategorikal dan dengan campuran nilai-nilai numerik dan kategori. Algoritma K-Prototype, mengintegrasikan KMeans dan K-Modes algoritma untuk melakukan Clustering pada data campuran. Menggunakan data set penyakit tanaman (soybean disease) untuk mengukur kinerja algoritma yg digunakan. Dari penelitian tersebut didapatkan bahwa algoritma tersebut sangat efisien untuk melakukan Clustering pada data set yang berukuran besar.

13

Penelitian yang dipubilkasikan dengan judul Clustering Large Data Sets With Mixed Numeric and Categorical Value oleh Zhexue Huang, Penelitian ini membahas Algoritma K-Means yang menjanjikan untuk efisiensi mereka dalam pengolahan kumpulan data besar. Namun, penggunaannya sering terbatas untuk data numerik. Menyajikan algoritma K-Prototype yang didasarkan pada paradigma K-Means tapi menghilangkan batasan data numerik untuk efisiensi. Penelitian ini didorong oleh masalah dari berurusan dengan kumpulan data besar campuran, yang umum dalam aplikasi data mining. Penelitian ini telah menyajikan Algoritma K-Prototype untuk cluster data set yang besar yang ada di dunia nyata. Telah menunjukkan efisien untuk Clustering data numerik dan data kategorikal.

2.2

Algoritma Genetika Algoritma Genetika pertama kali diperkenalkan oleh John Holland dalam

bukunya yang berjudul “Adaption in natural and artificial systems”, dan oleh De Jong dalam bukunya “Adaption of the behavior of a class of genetic adaptive systems”, yang keduanya diterbitkan pada tahun 1975, yang merupakan dasar dari Algoritma Genetika (Davis, 1991). Algoritma Genetik sebenarnya terinspirasi dari prinsip genetika dan seleksi alam (teori Darwin) yang ditemukan di Universitas Michigan, Amerika Serikat oleh John Holland melalui sebuah penelitian dan dipopulerkan oleh salah satu muridnya, David Goldberg menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975. Konsep dasar algoritma genetika

14

sebenarnya dirancang untuk mensimulasikan proses-proses dalam sistem alam yang diperlukan untuk evolusi, khusunya teori evolusi alam yang dicetuskan oleh Charles Darwin, yaitu survival of the fittest. Menurut teori ini, di alam terjadi persaingan antara individu-individu untuk memperebutkan sumber daya alam yang langka sehingga makhluk yang kuat mendominasi makhluk yang lemah. Algoritma genetika adalah suatu algoritma pencarian yang berbasis pada mekanisme seleksi alam dan genetika. Algoritma genetika merupakan salah satu algoritma yang sangat tepat digunakan dalam menyelesaikan masalah optimasi kompleks, yang sulit dilakukan oleh metode konvensional (Desiani, 2006). Algoritma Genetika banyak dipakai pada aplikasi bisnis, teknik maupun pada bidang keilmuan lainnya. Algoritma ini dimulai dengan kumpulan solusi yang disebut dengan populasi. Solusi-solusi dari sebuah populasi diambil dan digunakan untuk membentuk populasi yang baru. Hal ini dimotivasi dengan harapan bahwa populasi yang baru dibentuk tersebut akan lebih baik daripada yang lama. Solusi-solusi yang dipilih untuk membentuk solusisolusi yang baru dipilih sesuai dengan fitness mereka masing-masing (Juniawati, 2003). Pertahanan yang tinggi dari individu memberikan kesempatan untuk melakukan reproduksi melalui perkawinan silang dengan individu yang lain dalam populasi tersebut. Individu baru yang dihasilkan dalam hal ini dinamakan keturunan, yang membawa beberapa sifat induknya.Sedangkan individu dalam populasi yang tidak terseleksi dalam reproduksi akan mati dengan sendirinya. Dengan jalan ini, beberapa generasi dengan karakteristik yang bagus akan bermunculan dalam populasi tersebut, untuk kemudian dicampur dan ditukar

15

dengan karakter lain. Dengan mengawinkan semakin banyak individu, maka akan semakin banyak kemungkinan terbaik yang dapat diperoleh. Sifat algoritma genetik mencari kemungkinan-kemungkinan dari kandidat solusi untuk mendapatkan yang optimal untuk penyelesaian masalah. Ruang cakupan dari semua solusi yang layak (feasible), yaitu objek-objek diantara solusi yang sesuai, dinamakan ruang pencarian (search space). Tiap titik dalam ruang pencarian merepresentasikan satu solusi yang layak. Tapi solusi yang layak dapat ditandai dengan nilai fitness-nya bagi masalah. Sebelum Algoritma Gentika dapat dijalankan, maka sebuah kode yang sesuai(representatif) untuk persoalan harus dirancang. Untuk ini maka titik solusi dalam ruang permasalahan dikodekan dalam bentuk kromosom/string yang terdiri atas komponen genetik terkecil yaitu gen. Dengan teori evolusi dan teori genetika, di dalam penerapan Algoritma Genetika akan melibatkan beberapa operator, yaitu: 1.

Operasi Evolusi yang melibatkan proses seleksi (selection) di dalamnya.

2.

Operasi Genetika yang melibatkan operator pindah silang (crossover) dan mutasi (mutation). Algoritma genetika merupakan algoritma yang berusaha menerapkan

pemahaman mengenai evolusi alamiah pada tugas-tugas pemecahan-masalah (problem solving). Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness. Generasi

16

ini akan merepresentasikan perbaikan-perbaikan pada populasi awalnya. Dengan melakukan proses ini secara berulang, algoritma ini diharapkan dapat mensimulasikan proses evolusioner. Pada akhirnya, akan didapatkan solusi-solusi yang paling tepat bagi permasalahan yang dihadapi. Algoritma genetika sangat tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan sukar diselesaikan dengan menggunakan metode konvensional. Sebagaimana halnya proses evolusi di alam, suatu algoritma genetika yang sederhana umumnya terdiri dari tiga operasi yaitu: operasi reproduksi, operasi persilangan (crossover), dan operasi mutasi. Struktur umum dari suatu algoritma genetika dapat didefinisikan dengan langkah–langkah sebagai berikut (Utami 2008):

1.

Membangkitkan populasi awal secara random.

2.

Membentuk generasi baru dengan menggunakan tiga operasi diatas secara berulang-ulang sehingga diperoleh kromosom yang cukup untuk membentuk generasi baru sebagai representasi dari solusi baru.

Evolusi solusi yang akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom hingga kriteria berhenti terpenuhi. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah 2. beberapa kriteria berhenti yang sering digunakan antara lain (Utami, 2008):

17

1. Berhenti pada generasi tertentu 2. Berhenti jika sudah ditemukan solusi, yaitu solusi yang sesuai dengan kriteria 3. Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness

tertinggi/terendah

(tergantung

persoalan)

tidak

berubah

(konvergen). 4. Kombinasi dari kriteria – kriteria diatas.

Beberapa pengertian dasar yang perlu diketahui mengenai Algoritma Genetika :

1. Gen (Genotype) adalah variabel dasar yang membentuk suatu kromosom. Dalam algoritma genetika, gen ini bisa bernilai biner, float, integer maupun karakter. 2. Alelle adalah nilai suatu gen, bisa berupa biner, float, integer maupun karakter. a. Kromosom adalah gabungan dari gen-gen yang membentuk arti tertentu. Ada beberapa macam bentuk kromosom. b. Kromosom biner, adalah kromosom yang disusun dari gen-gen yang bernilai biner. Kromosom ini mempunyai tingkat keberhasilan yang tinggi. Jumlah gen pada kromosom biner menunjukkan tingkat ketelitian yang diharapkan. Kromosom ini bagus bila digunakan untuk permasalahan yang parameter dan range nilainya tertentu. c. Kromosom Float adalah kromosom yang disusun dari gen-gen yang bernilai pecahan, termasuk gen yang bernilai bulat. Kromosom ini

18

merupakan model dengan jumlah parameternya banyak. Tingkat keberhasilan dari kromosom ini rendah dalam kecepatan (jumlah generasi). Model cross-over dan mutasi pada kromosom ini sangat berbeda dengan kromosom biner sehingga diperlukan strategi khusus untuk melakukan cross-over dan mutasi. Nilai range (min max) menjadi tidak penting. d. Kromosom String, yaitu kromosom yang disusun dari gen-gen yang bernilai string. e. Kromosom Kombinasi, yaitu kromosom yang disusun dari gen-gen yang dinilai berdasarkan urutannya. 3. Individu adalah kumpulan gen, bisa dikatakan sama dengan kromosom. Individu menyatakan salah satu kemungkinan solusi dari suatu permasalahan. 4. Populasi adalah sekumpulan individu yang akan diproses secara bersamasama dalam satu siklus proses evolusi. 5. Generasi menyatakan satu satuan siklus proses evolusi. 6. Nilai Fitness menyatakan seberapa baik nilai dari suatu individu atau solusi yang didapatkan. Nilai inilah yang dijadikan acuan untuk mencapai nilai optimal.

19

Gambar 2.1 Visualisasi gen, allele, kromosom, individu, dan populasi pada Algoritma Genetika (T. Sutojo,S.Si dkk, 2011)

Ciri-ciri permasalahan yang dapat dikerjakan dengan menggunakan algoritma genetika adalah (Basuki, 2003):

20

1.

Mempunyai fungsi tujuan optimalisasi non linear dengan banyak kendala yang juga non linear.

2.

Mempunyai kemungkinan solusi yang jumlahnya tak berhingga.

3.

Membutuhkan solusi “real-time” dalam arti solusi bisa didapatkan dengan cepat sehingga dapat diimplementasikan untuk permasalahan yang mempunyai perubahan yang cepat seperti optimasi pada pembebanan kanal pada komunikasi seluller.

4.

Mempunyai multi-objective dan multi-criteria, sehingga diperlukan solusi yang dapat secara bijak diterima oleh semua pihak.

2.2.1

Siklus Algoritma Genetika David Goldberg orang pertama kali memperkenalkan siklus algoritma

genetika yang di Gambarkan seperti Gambar 2. Siklus dimulai dari membuat populasi awal secara acak, kemudian setiap individu dihitung nilai fitness nya. Proses berikutnya adalah seleksi individu terbaik, kemudian dilakukan cross-over dan dilanjutkan oleh proses mutasi sehingga terbentuk populasi baru. Selanjutnya populasi baru ini mengalami siklus yang sama dengan populasi sebelumnya. Proses ini berlangsung terus hingga generasi ke –n.

21

Gambar 2.2 Siklus algoritma genetika yang diperkenalkan oleh David Goldberg

Siklus ini kemudian diperbaiki oleh Zbigniew Michalewicz dengan menambahkan satu proses elitisme dan membalik proses reproduksi terlebih dahulu, kemudian proses seleksi seperti tampak pada Gambar.

Gambar 2.3 Siklus algoritma genetika yang diperbaiki oleh Zbigniew Michalewicz

22

Algoritma genetik secara umum dapat diilustrasikan dalam diagram alir berikut (Goldberg, 1989):

Gambar 2.4 Struktur Umum Algoritma Genetik

Keterangan singkat dari Gambar 2.4, Algoritma Genetika secara umum struktur yang akan dimplementasikan adalah sebagai berikut (Thiang,dkk. 2001): 1.

Bangkitkan Populasi awal Proses ini merupakan proses yang digunakan untuk membangkitkan populasi awal secara random sehingga didapatkan solusi awal. Populasi awal ini dibangkitkan secara random sehingga diperoleh solusi awal. Populasi

ini

sendiri

terdiri

atas

mempresentasikan solusi yang diinginkan.

sejumlah

kromosom

yang

23

2.

Evaluasi fitness Proses ini merupakan proses untuk mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Suatu individu dievaluasi berdasarkan suatu fungsi tertentu sebagai ukuran performansinya. Didalam evolusi alam, individu yang bernilai fitness rendah akan mati. Pada masalah optimasi, jika solusi yang dicari adalah memaksimalkan sebuah fungsi h (dikenal sebagai masalah maksimasi), maka nilai fitness yang digunakan adalah nilai dari fungsi h tersebut, yakni fitness f = h . 3. Seleksi Proses seleksi merupakan proses

untuk menentukan individu-individu

mana saja yang akan dipilih untuk dilakukan crossover. Ada beberapa jenis metode seleksi yang biasa digunakan diantaranya yaitu : Metode yang menirukan permainan roulette-wheel dimana masing-masing kromosom menempati potongan lingkaran pada roda roulette secara proporsional sesuai dengan nilai fitnessnya. Seleksi Rangking Proses dimulai dengan merangking atau mengurutkan kromosom di dalam populasi berdasarkan fitnessnya kemudian memberi nilai fitness baru berdasarkan urutannya. 4. Crossover Proses crossover ini merupakan proses untuk menambah keanekaragaman string dalam satu populasi. Operator pindah silang mempunyai peran yang paling penting dalam algoritma genetik karena didalamnya terdapat proses

24

perkawinan (persilangan) gen antara dua individu (parent) yang menghasilkan dua individu baru (offspring) pada generasi berikutnya. 5. Mutasi Mutasi merupakan proses mengubah nilai dari satu atau beberapa gen dalam suatu kromosom. Mutasi menciptakan individu baru dengan melakukan modifikasi satu atau lebih gen dalam individu yang sama. Mutasi berfungsi untuk menggantikan gen yang hilang dari populasi selama proses seleksi serta menyediakan gen yang tidak ada dalam populasi awal. 6. Kriteria berhenti Kriteria berhenti merupakan kriteria yang digunakan untuk menghentikan proses Algoritma Genetika yang merupakan tujuan yang ingin dicapai dari proses tersebut. 7. Hasil Hasil merupakan solusi optimum yang didapat dengan menggunakan Algoritma Genetika.

2.2.2

Teknik Encoding/Decoding Gen dan Individu Teknik Encoding/Decoding Gen dan Individu merupakan salah satu

komponen dari algoritma genetika, dimana Encoding (pengkodean) berguna untuk mengkodekan nilai gen-gen pembentuk individu. Nilai-nilai gen ini diperoleh secara acak. Ada 3 pengkodean yang paling umum digunakan, yaitu Pengkodean bilangan real : nilai gen berada dalam interval [0 1 ]

25

Contoh : 3 variabel (x1,x2,x3) dikodekan ke dalam individu yang terdiri dari 3 gen

x1

0,2431

x2

0,9846

g1

g2

x3

0,5642

g3

Pengkodean diskrit desimal : nilai gen berupa bilangan bulat dalam interval [0 9] Contoh : 3 Variabel (x1, x2, x3) dikodekan ke dalam individu yang terdiri dari 9 gen, tiaptiap variabel dikodekan ke dalam 3 gen.

Pengkodean Biner : nilai gen berupa bilangan biner 0 atau 1. 3 Variabel (x1, x2, x3) dikodekan ke dalam individu yang terdiri dari 9 gen, tiap-tiap variabel dikodekan ke dalam 3 gen.

26

Decoding (pengkodean) berguna untuk mengkodekan gen-gen pembentuk individu agar nilainya tidak melebihi range yang telah ditentukan dan sekaligus menjadi nilai variabel yang akan dicari sebagai solusi permasalahan. Jika nilai variabel x yang telah dikodekan tersebut range-nya dirubah menjadi [ra rb], yaitu rb=batas bawah, ra = batas atas, maka cara untuk mengubah nilai-nilai variabel di atas hingga berada dalam range yang baru [rb

ra], disebut Decoding

(pengkodean). Pendekodean Bilangan real : X = rb + (ra - rb) g

Pendekodean Diskrit Desimal : X = rb + (ra - rb) (g1 x 10-1 + g2 x 10-2 +.......+ gn x 10-n)

Pendekodean Biner : X = rb + (ra - rb) (g1 x 2-1 + g2 x 2-2 +.......+ gn x 2-n) Dengan catatan bahwa N adalah jumlah gen dalam individu.

27

2.2.3

Representasi Kromosom

Representasi kromosom merupakan proses awal sebelum masuk proses regenerasi. Cara merepresentasikan permasalahan dalam kromosom merupakan suatu hal yang penting dalam algoritma genetika. Model representasi kromosom yang dapat dipergunakan untuk menyelesaikan suatu masalah, antara lain :

2.2.3.1

Kromosom Biner

Kromosom biner merupakan kromosom yang disusun dari gen-gen yang bernilai 0 dan 1. Kromosom ini adalah model standar dalam algoritma genetika. Kromosom biner merupakan model yang sederhana dengan tingkat keberhasilan yang tinggi. Permasalahan yang direpresentasikan dengan kromosom biner antara lain, knapsack, TSP, Optimasi fungsi dll. Contoh representasi kromosom biner seperti pada Gambar. Kromosom A

1

0

1

1

0

Kromosom B

1

1

0

0

0

Gambar 2.5 Contoh Kromosom Biner

2.2.3.2 Kromosom Float Kromosom float merupakan model yang jumlah parameternya banyak. Tingkat keberhasilan dari bentuk kromosom ini rendah dalam kecepatan (jumlah generasi).

28

Model crossover dan mutasi pada kromosom float ini sangat berbeda dengan model crossover dan mutasi pada kromosom biner. Sehingga perlu strategi khusus didalam menentukan model crossover dan mutasi. Contoh representasi kromosom float seperti pada Gambar. Kromosom A

1.2

3.4

1.6

2.2

4.1

Kromosom B

2.2

3.1

1.2

4.2

1.6

Gambar 2.6 Contoh Kromosom Float

2.2.3.3 Kromosom Nilai Kromosom nilai tersusun dari gen – gen bernilai string dari suatu nilai (simbol). Nilai tersebut merupakan suatu hal yang berhubungan dengan masalah yang akan diselesaikan. Permasalahan yang menggunakan kromosom ini biasanya akan sulit dipecahkan jika menggunakan pengkodean biner (kromosom biner). Contoh representasi kromosom nilai seperti pada Gambar . Kromosom A

1,2 3,3 2,5 1,6 4,4 35

Kromosom B

AHDKHSTFNSFKSL

Kromosom C

(left) (right) (back)

Gambar 2.7 Contoh Kromosom Nilai

29

2.2.3.4 Kromosom Permutasi Kromosom A

854912367

Kromosom B

912438576

Gambar 2.8 Contoh Kromosom Permutasi

Kromosom kombinatorial yaitu kromosom yang disusun dari gen–gen yang dinilai berdasarkan urututannya. Kromosom ini biasanya digunakan untuk menyelesaikan permasalahan pengurutan seperti Ordering task dan TSP. Contoh representasi kromosom permutasi seperti pada Gambar 2.8.

2.2.4

Membangkitkan Populasi Awal Pada awalnya solusi individual akan secara acak dibuat dalam bentuk

sebuah inisial populasi. Besar populasinya sangat tergantung pada keadaan masalah itu sendiri, tapi biasanya populasi mengandung sekitar beberapa ratus atau bahkan ribuan solusi yang mungkin. Secara sederhana, populasinya dibuat secara acak, dengan mengcaver seluruh kemungkinkan solusi (search space). Membangkitkan populasi awal adalah proses membangkitkan sejumlah individu secara acak atau melalui prosedur tertentu. Sebelum membangkitkan populasi awal, terlebih dahulu kita harus menentukan jumlah individu dalam populasi tersebut. Misalnya jumlah individu tersebut N. Setelah itu, baru kita membangkitkan populasi awal yang mempunyai N individu secara random.

30

Syarat-syarat yang harus dipenuhi untuk menunjukkan suatu solusi harus benarbenar diperhatikan dalam pembangkitan setiap individunya.

2.2.5

Nilai Fitness Nilai fitness menyatakan nilai dari fungsi tujuan. Tujuan dari algoritma

genetika adalah memaksimalkan nilai fitness. Jika yang dicari nilai maksimal, maka nilai fitness adalah nilai dari fungsi itu sendiri. Tetapi jika yang dibutuhkan adalah nilai minimal, maka nilai fitness merupakan invers dari nilai fungsi itu sendiri. Proses invers dapat dilakukan dengan cara berikut.

Suatu individu dievaluasi berdasarkan suatu fungsi tertentu sebagai ukuran performansinya. Didalam evolusi alam, individu yang bernilai fitness rendah akan mati. Pada masalah optimasi, jika solusi yang dicari adalah memaksimalkan sebuah fungsi h (dikenal sebagai masalah maksimasi), maka nilai fitness yang digunakan adalah nilai dari fungsi h tersebut, yakni fitness f = h . Tetapi jika masalahnya adalah meminimalkan fungsi h (masalah minimasi), maka fungsi h tidak bisa digunakan secara langsung. Hal ini disebabkan adanya aturan bahwa individu yang memiliki nilai fitness tinggi lebih mampu bertahan hidup pada generasi berikutnya. Oleh karena itu nilai fitness yang bisa digunakan adalah f = 1/h , yang artinya semakin kecil nilai h , semakin besar nilai f (fitness). Tetapi hal ini akan menjadi masalah jika h bisa bernilai 0, yang mengakibatkan f bisa bernilai tak hingga. Untuk mengatasinya, h perlu ditambah sebuah bilangan yang dianggap sangat kecil sehingga nilai fitnessnya menjadi :

31

f=

(2.1)

dimana a adalah bilangan yang dianggap sangat kecil dan bervariasi sesuai dengan masalah yang akan diselesaikan.

2.2.6

Elitisme Elitisme adalah prosedur untuk meng-copy individu yang mempunyai nilai

fitness tertinggi sebanyak satu (bila jumlah individu dalam suatu populasi adalah ganjil) atau dua (bila jumlah individu dalam suatu populasi adalah genap). Hal ini dilakukan agar

individu ini tidak mengalami kerusakan (nilai fitness-nya

menurun) selama proses pindah silang maupun mutasi. Misalnya pada contoh sebelumnya, maka individu ke-4 dibuat copy-nya sebanyak satu, kemudian disimpan dalam variabel temporer_individu. Contoh : temporer_individu =111, 111;

2.2.7

Seleksi Kadang kala suatu fungsi tertentu dapat menyebabkan setiap individu

mempunyai nilai fitness hampir sama. Hal ini bisa berakibat buruk pada saat dilakukan proses seleksi untuk memilih orangtua karena dapat menyebabkan optimum lokal. Gambar menggambarkan bagaimana terjadinya optimum lokal.

Pada Gambar 2.9 untuk sebelah kiri, semua individu berada sangat jauh dari titik optimal sesungguhnya. Kebetulan ada satu individu P yang nilai fitnessnya tertinggi dibanding

individu lainnya. Akibatnya individu P akan

32

memproduksi banyak anak. Pada generasi tertentu individu P dan anak-anaknya, melalui proses pindah silang dan mutasi, akan menghasilkan individu-individu yang mendekati lokal optimum (gambar sebelah kanan), sehingga terjadilah konvergensi prematur, di mana populasi konvergen pada suatu solusi optimal lokal. Permasalahan inilah yang sering muncul pada algoritma genetika.

Gambar 2.9 Grafik Lokal Optimim (T.Sutojo, Edy Mulyanto, Dr. Vincent Suhartono, 2011)

Pada Gambar sebelah kiri, individu P mempunyai nilai fitness tertinggi dibanding individu lainnya. Pada gambar sebelah kanan, populasi konvergen pada suatu optimum lokal dekat individu P. Tidak ada individu yang mencapai nilal optimal sebenarnya. Untuk menghindari hal ini, dibuatlah suatu mekanisme yang disebut dengan Linier Fitness Rangking (LFR). Tujuan dan mekanisme mi sebenarnya adalah untuk melakukan penskalaan nilai-nilai fitness dengan menggunakan persamaan berikut.

33

LFR(i) =fmax –(fmax - fmin)(

)

(2.2)

Dengan catatan bahwa: LFR(i) = nilai LFR individu ke-i N R(i)

= jumlah individu dalam populasi = rangking individu ke-i setelah diurutkan dan nilai fitness terbesar hingga terkecil

fmax fmin

= nilai fitness tertinggi = nilai fitness terendah

Seleksi dilakukan untuk mendapatkan calon induk yang baik. “Induk yang baik akan menghasilkan keturunan yang baik”. Semakin tinggi nilai fitness suatu individu semakin besar kemungkinannya untuk terpilih. Seleksi dapat dilakukan dengan menggunakan dua macam teknik, yaitu

Metode ini menirukan permainan roulette-wheel di mana masing-masing kromosom menempati potongan lingkaran pada roda roulette secara proporsional sesuai dengan nilai fitness-nya. Kromosom yang memiliki nilai fitness lebih besar menempati potongan lingkaran yang lebih besar dibandingkan dengan kromosom bernilai fitness rendah. Berikut ini mengilustrasikan sebuah contoh penggunaan metode Roulette-Wheel.

34

Tabel 2.1 Kromosom dan Nilai fitnessnya Kromosom

Nilai Fitness

A

1

B

2

C

0,5

D

0,5

Jumlah

4

Tabel 2.1 menunjukkan suatu populasi dengan 5 kromosom dan telah dihitung masing-masing nilai fitnessnya. Masing-masing kromosom memiliki fitness yang berbeda

Roda Roulette 12.5%

A B

12.5%

37.5%

C D

25%

E 12.5%

Gambar 2.10 Contoh probabilitas kromosom pada roda roullete

Gambar diatas merupakan representasi nilai fitness masing-masing kromosom pada roda roulette.

35

Gambar 2.11 Seleksi dengan Roulette-Wheel

2.2.7.1 Seleksi Rangking (Rank Selection) Tabel 2.2 Kondisi kromosom sebelum dan sesudah di ranking Sebelum

Sesudah

Kromosom

Fitness

Kromoso m

Fitness

Fitness baru

A

15

B

5

1

B

5

D

5

2

C

10

E

5

3

D

5

C

10

4

E

5

A

15

5

Pada metode seleksi roda roulette akan bermasalah saat terdapat perbedaan fitness yang jauh. Sebagai contoh, jika fitness kromosom yang terbaik

36

adalah 90% dari semua roda roulette dapat menyebabakan kromosom lain memiliki kesempatan yang kecil untuk dapat terpilih.

Proses dimulai dengan merangking atau mengurutkan kromosom di dalam populasi berdasarkan fitnessnya kemudian memberi nilai fitness baru berdasarkan urutannya. Kromosom dengan nilai terburuk akan memiliki fitness baru nilai 1, terburuk kedua bernilai 2 dan begitu seterusnya, sehingga kromosom yang memiliki fitness terbaik akan memiliki nilai fitness N, dimana N adalah jumlah kromosom di dalam populasi. Seperti dapat dilihat pada tabel 2.

Setelah adanya proses seleksi tersebut, maka saat ini seluruh kromosom mempunyai kesempatan untuk dipilih. Kelemahan metode ini terletak pada kecepatan pencapaiannya. Hal ini dikarenakan kromosom yang lebih baik tidak bisa menjadi petunjuk bagi populasi untuk mendapatkan solusi terbaik secara mudah, sehingga untuk mencapai solusi yang baik memerlukan waktu yang lebih lama.

2.2.7.2 Seleksi Turnamen (Turnamen Selection)

Metode ini merupakan kombinasi dari seleksi roda roulette dan seleksi rangking. Sejumlah k kromosom tertentu dari populasi beranggota n kromosom (k ≤n) dipilih secara acak dengan probabilitas yang sama. Dari k kromosom yang terpilih kemudian akan dipilih satu kromosom dangan fitness terbaik, yang diperoleh dari hasil pengurutan rangking fitness semua kromosom terpilih.

37

Perbedaan dengan seleksi roda roulette adalah pemilihan kromosom yang akan digunakan untuk berkembangbiak tidak berdasarkan skala fitness dari populasi. Partikel data merupakan partisi dari sebuah kelas yang antara sembarang pasangan anggotanya memiliki jarak kurang dari radius tertentu. Cara termudah untuk membuat partikel data ialah memperlakukan setiap anggota data pelatihan sebagai partikel data tunggal. Cara ini akan menghasilkan perhitungan gravitasi data yang sangat akurat. Namun cara ini akan mengakibatkan proses klasifikasi tidak efisien dari segi waktu komputasi.

2.3

Operator Genetika

Operator genetik dipergunakan untuk mengkombinasi (modifikasi) individu dalam aliran populasi guna mencetak individu pada generasi berikutnya 2.3.1

Operator Reproduksi

Untuk setiap solusi baru yang dibentuk, sebuah pasangan "parent" atau orang tua solusi dipilih dari kumpulan populasi sebelumnya. Dengan membuat sebuah "child" atau anak solusi menggunakan metode diatas, yaitu persilangan dan mutasi, sebuah solusi baru telah dibuat, dimana pada umumnya anak akan mewarisi bagian-bagian dari orang tuanya. Orang tua baru dipilih lagi dan membuat suatu anak solusi lagi, dan berlanjut sampai suatu populasi solusi baru dengan ukuran yang cukup terbentuk

38

2.3.1.1 Operator Pindah Silang (Crossover)

Operator pindah silang mempunyai peran yang paling penting dalam algoritma genetik karena didalamnya terdapat proses perkawinan (persilangan) gen antara dua individu (parent) yang menghasilkan dua individu baru (offspring) pada generasi berikutnya.

Crossover (Pindah Silang) merupakan salah satu operator dalam algoritma genetika yang melibatkan dua induk untuk menghasilkan keturunan yang baru. Crossover dilakukan dengan melakukan pertukaran gen dari dua induk secara acak. Macam-macam Crossover yang banyak digunakan antara lain: pertukaran gen secara langsung dan pertukaran gen secara aritmatika. Proses crossover dilakukan pada setiap individu dengan probabilitas crossoveryang ditentukan.

Sebuah individu yang mengarah pada solusi optimal bisa diperoleh melalui proses pindah silang, dengan catatan bahwa pindah silang hanya bisa dilakukan jika sebuah bilangan random r dalam interval [0 1] yang dibangkitkan nilainya lebih kecil dari probabilitas tertentu prob, dengan kata lain : r < prob. Biasanya nilai prob diset mendekati 1. Cara yang paling sederhana untuk melakukan pindah silang adalah pindah silang satu titik potong. Posisi titik potong dilakukan secara random.

Penentuan individu yang berhak melakukan operasi crossover tergantung pada probabilitas crossover (Pc) yang telah ditentukan. Langkah- langkah untuk melakukan operasi crossover sebagai berikut :

39

1. Tentukan probabilitas crossover (Pc). 2. Lakukan proses seleksi untuk memilih individu yang akan mengalami crossover 3. Lakukan crossover. Crossover : Pertukaran secara langsung, dengan ditentukan probabilitas crossover= 0,9, seperti pada Gambar 2.12

Gambar 2.12 Pertukaran secara langsung

Cross Over : Pertukaran Secara Aritmatika

40

Gambar 2.13 Pertukaran Secara Aritmatika

Beberapa teknik atau metode crossover yaitu (Utami, 2008) : 1.

Pindah Silang Satu Titik (One Point Crossover) Pada pindah silang satu titik (one-point crossover), satu titik sepanjang

kromosom dipilih secara random. Segmen dari induk dari titik point ke kiri atau kekanan ditukar untuk menghasilkan individu baru. Mekanisme one point crossover diilustrasikan pada gambar berikut.

41

Gambar 2.14 Proses one point crossover

2.

Pindah Silang Dua Titik (Two Point Crossover)

Pada pindah silang dua titik, dua titik sepanjang kromosom dipilih secara random. Segmen induk diantara kedua titik potong dipertukarkan untuk menghasilkan individu baru. Mekanisme two point crossover diilustrasikan pada gambar berikut :

42

Gambar 2.15 Proses two point crossover

3.

Pindah Silang Banyak Titik (N-point Crossover)

Gambar 2.16 Proses n point crossover

43

Pada pindah silang banyak titik, sejumlah N titik sepanjang kromosom dipilih secara random, dimana titik potong tidak boleh sama. Mekanisme n point crossover diilustrasikan pada gambar dibawah ini.

4.

Pindah Silang Seragam (Uniform Crossover)

Pada uniform crossover, sejumlah N titik ditentukan secara random baik itu jumlah maupun letaknya. Segmen yang dipertukarkan sesuai dengan jumlah titik potong yang didapatkan secara random tersebut. Uniform crossover hampir sama dengan N point crossover. Untuk uniform crossover, jumlah titik ditentukan secara random sedangkan N point jumlah titik sudah ditentukan.

Uniform

crossover juga akan sama dengan two point crossover jika titik potong yang dihasilkan dua titik.

Gambar 2.17 Proses uniform crossover

44

5.

Pindah Silang Aritmatik (Aritmathic Crossover) Pada pindah silang ini digunakan operator aritmatik untuk menghasilkan

kromosom baru. Contoh :

6.

Induk 1

:1 1 0 0 1 0 1 1 1 0 0 0

Induk 2

:1 0 0 1 1 1 0 0 1 1 0 1

Anak (OR)

:1 1 0 1 1 1 1 1 1 1 0 1

Pindah Silang untuk Pengkodean Permutasi

Pindah silang dengan permutasi (Permutation Crossover) ini biasa menggunakan teknik pindah silang satu titik karena prosesnya yang sederhana dan agar tetap menjaga konsistensi urutan nilai pada kromosom.

Dalam proses penyilang ini, pertama kali ditentukan posisi titik pindah silang. Kemudian dari gen pertama sampai dengan titik perkawinan silang disalin dari induk pertama, sedangkan sisanya didapatkan dengan cara melihat satu persatu nilai pada orang tua kedua, jika belum ada pada kromosom keturunan, maka nilai tersebut ditambahkan. Berikut contoh : Induk 1

:123456789

Induk 2

:453689721

Anak 1

:123456879

Anak 2

:453681279

45

2.3.1.2 Operator Mutasi

Mutasi menciptakan individu baru dengan melakukan modifikasi satu atau lebih gen dalam individu yang sama. Mutasi berfungsi untuk menggantikan gen yang hilang dari populasi selama proses seleksi serta menyediakan gen yang tidak ada dalam populasi awal. Sehingga mutasi akan meningkatkan variasi populasi.

Individu yang terpilih untuk proses mutasi dapat dilakukan dengan membandingkan nilai probabilitas mutasinya dengan probabilitas mutasi yang telah ditentukan atau dapat dipilih secara acak (random).

Mutasi Gen merupakan operator yang menukar nilai gen dengan nilai inversinya, mialnya gennya bernilai 0 menjadi 1.Setiap individu mengalami mutasi gen dengan probabilitas mutasi yang ditentukan. Mutasi dilakukan dengan memberikan nilai inversi atau menggeser nilai gen pada gen yang terpilih untuk dimutasikan

Mutasi dilakukan untuk semua gen yang terdapat pada individu, jika bilangan random yang dibangkitkan lebih kecil dan probabilitas mutasi p yang ditentukan. Biasanya p diset = 1/N, di mana N adalah jumlah gen dalam individu. Untuk kode biner, mutasi dilakukan dengan cara membalik nilai bit 0 menjadi bit 1, sebaliknya bit 1 diubah menjadi bit 0.

46

Gambar 2.18 Contoh proses mutasi

Representasi kromosom yang berbeda akan membedakan jenis mutasi yang digunakan. Metode mutasi yang biasanya digunakan yaitu : 1.

Inversi Mutasi ini dilakukan dengan mengubah nilai 1 menjadi 0 atau sebaliknya.

Mutasi ini biasanya terapkan pada kromosom biner.

a( k )  a( k )  1 C

:1 0 0 1 1 0 1

C’

:1 0 0 1 0 1 1

47

2.

Random Mutasi ini dilakukan dengan mengganti gen yang termutasi dengan nilai

random.

a(k )  random C

:1 2 3 4 5 6 7

C’

:1 2 9 4 5 6 7

Shift, mutasi ini dilakukan dengan menggeser nilai gen termutasi sebesar , dimana  adalah nilai bilangan kecil yang ditentukan.

a( k )  a( k )   3.

Swap Mutasi ini dilakukan dengan menukar urutan gen yang terdapat pada satu

kromosom, sehingga konsistensi urutan gen tetap terjaga. Contoh untuk pengkodean permutasi : Induk : 1 2 3 4 5 6 7 Anak : 1 4 3 2 5 6 7

Probabilitas mutasi yang baik berada pada kisaran 0 sampai dengan 0.3. Probabilitas mutasi yang terlalu kecil menyebabkan terjebak dalam optimum lokal, dan probabilitas mutasi yang terlalu besar menyebabkan konvergensi sulit didapatkan

48

2.4

Clustering Data Clustering merupakan salah satu metode Data Mining yang bersifat

tanpa arahan (unsupervised). Ada dua jenis data Clustering yang sering dipergunakan dalam proses pengelompokan data yaitu hierarchical (hirarki) data Clustering dan non-hierarchical (non hirarki) data Clustering.

Metode ini

mempartisi data ke dalam cluster/kelompok sehingga data yang memiliki karakteristik yang sama dikelompokkan ke dalam satu cluster yang sama dan data yang mempunyai karakteristik yang berbeda dikelompokkan ke dalam kelompok yang

lain.

Adapun

tujuan

dari

data

Clustering

ini

adalah

untuk

meminimalisasikan objective function yang diset dalam proses Clustering, yang pada umumnya berusaha meminimalisasikan variasi di dalam suatu cluster dan memaksimalisasikan variasi antar cluster.

Clustering adalah suatu teknik dalam data mining yang digunakan untuk memasukkan data ke dalam grup yang bersesuaian tanpa pengetahuan yang mendalam tentang grup tersebut (Santosa, 2007). Clustering digunakan untuk menganalisis pengelompokkan berbeda terhadap data, menyerupai klasifikasi, namun pengelompokkan belum didefinisikan sebelum dijalankannya tool data mining. Biasanya menggunakan metode neural networkatau statistik. Clustering membagi item menjadi kelompok-kelompok berdasarkan yang ditemukan tool data mining. Prinsip dari Clustering adalah memaksimalkan kesamaan antar anggota satu kelas dan meminimumkan kesamaan antar cluster. Clustering dapat dilakukan pada data yang memiliki beberapa atribut yang dipetakan sebagai ruang multidimensi.

49

Pada algoritma Clustering, data akan dikelompokkan menjadi clustercluster berdasarkan kemiripan satu data dengan yang lain. Prinsip dari Clustering adalah memaksimalkan kesamaan antar anggota satu cluster dan meminimumkan kesamaan antar anggota cluster yang berbeda.

Analisa Cluster merupakan proses deskriptif yang mengidentifikasi kelompok obyek yang memiliki karakteristik homogen berdasarkan nilai dari setiap

atribut

pada

object

tersebut.

Clustering

merupakan

proses

mengelompokkan obyek ke dalam beberapa kelas atau kluster sehingga data-data didalam cluster yang sama memiliki kesamaan lebih dibandingkan dengan datadata pada cluster yang berbeda yang mana pada sebuah kluster, setiap obyek memiliki karakteristik yang sama, tetapi memiliki ketidakmiripan dengan obyek pada kluster yang lain (Han et al 2001). Kriteria utama yang harus dipenuhi oleh algoritma Clustering yaitu: 1.Dimensionalitas tinggi Algoritma Clustering yang baik seharusnya dapat bekerja di ruang dengan dimensi rendah dan tidak mengalami penurunan drastis ketika digunakan pada ruang berdimensi tinggi.

50

2.Skalabilitas Algoritma Clustering seharusnya dapat menangani himpunan data baik dalam jumlah kecil maupun besar. 3. Akurasi Solusi Clustering yang baik seharusnya memiliki kemiripan inter-cluster tinggi dan kemiripan intra-cluster rendah.

Analisis cluster membagi data ke dalam grup (cluster) yang bermakna, berguna, atau keduanya. Jika tujuannya mencari grup yang memiliki makna, maka cluster seharusnya menangkap struktur alami dari data, disebut juga Clustering for understanding. Analisis cluster akan mengelompokkan obyek-obyek data hanya berdasarkan pada informasi yang terdapat pada data, yang menjelaskan obyek dan relasinya. Tujuan analisis cluster adalah agar obyek-obyek di dalam grup adalah mirip (berhubungan) satu dengan lainnya, dan berbeda (atau tidak berhubungan) dengan obyek dalam grup

lainnya. Semakin besar tingkat

kemiripan/similarity (homogenitas) di dalam satu grup dan semakin besar tingkat perbedaan diantara grup, maka semakin baik (lebih berbeda) Clustering tersebut.

Clustering (pengelompokkan) berdasarkan kesamaan warna, maka pengelompokkannya seperti yang terlihat pada gambar berikut :

51

Gambar 2.19 Clustering berdasarkan warna

Untuk Clustering (pengelompokkan) berdasarkan kesamaan bentuk, maka pengelompokannya dapat dilihat seperti gambar berikut :

Gambar 2.20 Clustering berdasarkan bentuk

Jika Clustering (pengelompokkan) dilihat dari jarak yang terdekat, dapat dilihat pada gambar berikut :

52

Gambar 2.21 Clustering berdasarkan jarak

Semakin besar tingkat kemiripan/similarity (homogenitas) di dalam satu grup dan semakin besar tingkat perbedaan diantara grup, maka semakin baik (lebih berbeda) Clustering tersebut.

Gambar 2.22 Merupakan ilustrasi prinsip Clustering.

53

Gambar dibawah ini merupakan ilustrasi bagaimana definisi cluster tidak presisi dan definisi terbaik tergantung dari kondisi data serta hasil yang diinginkan.

(a) Original point

(b) Two clusters.

(c) Four clusters

(d) Six clusters.

Gambar 2.23 Beberapa cara menentukan cluster bagi dataset yang sama

Gambar 2.24 Algoritma Clustering

54

Telah banyak algoritma Clustering yang dikembangkan, Gambar diatas menyajikan beberapa algoritma Clustering dan hubungan diantara algoritmaalgoritma tersebut. 2.4.1

Tipe Cluster

Clustering bertujuan mencari kelompok obyek (cluster) yang bermanfaat, sedangkan tingkat manfaat ditentukan oleh tujuan analisis data yang ditetapkan. Oleh karena itu, terdapat beberapa jenis cluster, yaitu:

Well-Separate cluster merupakan himpunan titik sehingga sembarang titik dalam cluster lebih dekat (atau lebih mirip) dengan setiap titik dalam cluster dibandingkan dengan sembarang titik yang tidak di dalam cluster.

gambar

merupakan ilustrasi Well-Separated Cluster.

Gambar 2.25 Tipe cluster Well-Separated.

Prototype-Based/Center-Basedcluster

merupakan

himpunan

obyek,

sehingga sebuah obyek dalam cluster lebih dekat (lebih mirip) dengan “pusat” cluster, daripada dengan pusat cluster lainnya. Yang sering dijadikan pusat cluster adalah centroid dan medoid. Centroid adalah rataan semua titik dalam

55

cluster, sedangkan Medoid adalah titik yang paling mewakili cluster. Centerbased cluster di-ilustrasikan pada gambar

Gambar 2.26 Tipe cluster Prototype-Based/Center-Based

Graph-Based Jika data direpresentasikan sebagai graph, dimana obyek menjadi node dan link menyatakan koneksi diantara obyek, maka cluster dapat didefinisikan sebagai connected component; yaitu grup obyek yang terkoneksi satu sama lain, tetapi tidak memiliki koneksi dengan obyek di luar grup. Contoh penting dari graph-based cluster adalah contiguity-based cluster,

dimana dua

obyek terkoneksi hanya jika keduanya berada dalam jarak tertentu satu sama lain. Contoh contiguity-based cluster dapat dilihat pada gambar

Gambar 2.27 Tipe cluster Graph-Based

Density-Based Sebuah

cluster adalah wilayah yang padat obyek

dikelilingi oleh wilayah dengan kepadatan rendah. Cluster tipe ini berguna untuk membentuk

cluster dengan bentuk tak-teratur (irregular) atau terpilih

(intertwined), dan juga jika terdapat noise dan outlier. Gambar merupakan contoh Density-Based Clustering.

56

Gambar 2.28 Tipe Cluster Density-Based

Shared-Property (Conceptual Cluster). Mencari cluster dengan beberapa sifat yang sama, atau menyatakan konsep tertentu. Gambar berikut merupakan cluster yang mempunyai sifat “lingkaran”

Gambar 2.29 Tipe Cluster Shared-Property Misalkan X = {X1,X2,…,Xn} dinotasikan sebagai sekumpulan n object dan Xi=[xi1,xi2,…,xim] adalah object

yang direpresentasikan dengan m nilai

atribut. Kemudian dimisalkan juga k adalah sebuah bilangan integer positif. Tujuan utama dari Clustering X adalah ingin menemukan sebuah partisi yang membagi object didalam X menjadi k cluster disjoint. Untuk sejumlah n, jumlah partisi yang dimungkinkan adalah terbatas, tetapi ukurannya bisa menghasilkan variasi yang sangat banyak. Sangatlah tidak praktikal jika dilakukan penelusuran setiap kemungkinan partisi dengan tujuan untuk mencari partisi yang paling bagus diantara kemungkinan yang ada (Huang, 1997). Solusi umum yang digunakan

57

untuk menentukan apakah bagus atau tidaknya suatu partisi adalah dengan menggunakan ClusteringCriterion.

2.5

Algoritma Clustering K-Prototype Clustering adalah teknik yang cukup dikenal luas dan banyak dipakai dalam

data mining. Tujuan utama dari metode cluster adalah pengelompokan sejumlah data atau obyek ke dalam cluster (group) sehingga dalam setiap cluster akan berisi data yang semirip mungkin. Dalam Clustering, sistem berusaha menempatkan obyek yang mirip (memiliki jarak yang dekat) dalam satu cluster dan membuat jarak antar cluster yang sejauh mungkin. Ini berarti obyek dalam satu cluster sangat mirip satu sama lain dan berbeda dengan obyek dalam clustercluster yang lain. Clustering adalah salah satu teknik unsupervised learning dimana fase training tidak diperlukan untuk metode ini. Metode-metode yang masuk ke dalam unsupervised learning adalah metode yang tidak memerlukan label ataupun keluaran dari setiap data yang akan diinvestigasi.

Secara umum terdapat dua pendekatan dalam Clustering, yaitu partisioning dan hirarki. Dalam partisioning obyek xi, x2, …., xn dikelompokkkan ke dalam k cluster. Hal ini bisa dilakukan dengan menentukan pusat cluster awal, lalu dilakukan realokasi obyek berdasarkan kriteria tertentu sampai dicapai pengelompokan yang optimum. Dalam cluster hirarki, metode dimulai dengan membuat m cluster dimana setiap cluster beranggotakan satu obyek dan berakhir dengan satu cluster dimana anggotanya adalah m obyek. Pada setiap tahap dalam prosedurnya, satu cluster digabung dengan satu cluster yang lain. Jumlah

58

clusterbisa dipilih sesuai keinginan pengguna dengan menentukan cut-off pada tingkat tertentu (Santosa, 2007).

Algoritma Clustering yang diangkat dalam penelitian ini adalah mengenai K-Prototype yang melakukan Clustering pada data dengan tipe campuran numerik dan kategorikal. Algoritma ini dipilih karena sangat sederhana dari sisi kompleksitas algoritma dan mampu menangani data dengan ukuran yang sangat besar. K-Prototype adalah salah satu metode Clustering yang berbasis partitioning. Algoritma ini adalah hasil pengembangan atau kombinasi antara KMeans dan K-Modes Clustering untuk menangani Clustering pada data dengan campuran atribut bertipe numerik dan kategorikal (Huang,1998).

K-Prototype adalah salah satu metode Clustering yang berbasis partitioning. Algoritma ini adalah hasil pengembangan atau kombinasi antara K-Means dan KModesClustering (Huang,1998) untuk menangani Clustering pada data dengan campuran atribut bertipe numerik dan kategorikal. Perubahan yang mendasar terdapat pada pengukuran kesamaan (similarity measure) antara object dengan centroid (prototype)-nya. Pada proses Clustering dengan K-Prototype disini dilakukan beberapa proses utama yaitu :

1. Inisialiasi awal prototype Pada proses ini akan dilakukan pemilihan sejumlah K-Prototype dari dataset X sesuai dengan jumlah cluster yang ditentukan. Pemilihan ini biasanya

59

dilakukan secara acak. Proses ini akan menghasilkan matrik prototype berukuran k x panjang atribut X.

2. Alokasi object di dalam X ke Cluster dengan prototype terdekat

Pada proses ini akan dilakukan pengalokasian semua object di dalam daset X ke cluster yang memiliki jarak prototype terdekat dengan object yang diukur. Untuk setiap kali object X selesai dialokasikan, maka selanjutnya akan dilakukan penghitungan (update) terhadap prototype cluster yang berkaitan.

3. Realokasi object Jika terjadi perubahan prototype

Setelah semua object

dalam X selesai dialokasikan, selanjutnya akan

dilakukan pengukuran ulang jarak antara semua object di dalam X terhadap semua prototype yang ada. Jika ditemukan adanya object yang ternyata lebih dekat ke prototype yang lain, maka akan dilakukan pemindahan keanggotaan dan kemudian akan dilakukan update terhadap prototype cluster lama dan prototype cluster baru. Proses ini akan terus dilakukan sampai tidak ada lagi perubahan prototype. 2.6

Cost Function Criterion Metode pengukuran hasil Clustering sering disebut dengan Clustering

Criterion. Clustering Criterion inilah yang akan dijadikan nilai fitness dari setiap kromosom yang telah dievaluasi. Semakin tinggi nilai fitness, maka semakin bagus kromosom yang dievaluasi tersebut. Clustering criterion yang digunakan adalah cost function, atau biaya yang dihabiskan untuk menempatkan object pada

60

cluster yang bersesuaian. Solusi umum yang digunakan untuk menentukan apakah bagus atau tidaknya suatu partisi adalah dengan menggunakan Clustering Criterion. Dalam hal ini, Clustering criterion yang digunakan adalah dengan mencari cost function seperti yang diGambarkan seperti dibawah ini. Cost function yang dipergunakan secara luas adalah penelusuran terhadap matriks dispersi dalam cluster(within cluster dispersion matrix). Salah satu cara untuk mendefinisikan cost function ini adalah dengan formula berikut.

k

n

E   yil d ( X i , Ql )

(2.3)

l 1 i 1

Disini, Ql=[ql1,ql2, ... ,qlm] adalah vector representatif atau sering disebut dengan prototype untuk cluster, dan yil adalah sebuah elemen dari matrik partisi Ynxl. d adalah pengukuran kesamaan (similarity measure) yang pada umumnya menggunakan jarak Euclidean. Y memiliki dua ciri berikut, (1) 0yil1 dan (2)

k

y l 1

il

 1 . Y disebut hard partition

jika yil {0,1}, dan disebut dengan fuzzy partition jika sebaliknya. Dalam hard partition, yil = 1 mengindikasikan bahwa object Xi ditempatkan pada cluster l oleh Y. Dalam penelitian ini, jenis partisi yang digunakan adalah hard partition.

n

Terminologi di dalam

 y d(X ,Q ) i 1

il

i

l

pada persamaan (2.3) adalah total

biaya (total cost) untuk menempatkan X ke dalam cluster, seperti halnya dispersi total dari object di dalam cluster terhadap prototype Ql-nya. El diminimalkan jika

61

qlj 

1 nl

n

y x i 1

il ij

untuk j = 1, …., m

(2.4)

n

dimana nl   yil adalah jumlah object di dalam cluster. i 1

Ketika X memiliki atribut bertipe categorikal , maka diperkenalkan pengukuran kesamaan (similarity measure) sebagai berikut :

mr

mc

j 1

j 1

d ( X i , Ql )   ( xijr  qljr ) 2  l   ( xijc , qljc )

(2.5)

dimana (p,q) = 0 untuk p = q(p,q) = 1 untuk pq. Untuk nilai p mewakili nilai dari xijc dimana merupakan atribut kategorikal untuk object ke i sedangkan q mewakili nilai dari qljc yang merupakan prototype kategorikal dari cluster ke l. Sedangkan xijr dan qljr adalah nilai atribut numerik. mr dan mc adalah jumlah atribut numerik dan kategorikal. l adalah bobot untuk atribut kategorikal pada cluster ke l.

Sehingga cost function El bisa dituliskan ulang menjadi

n

mr

n

mc

i 1

j 1

i 1

j 1

El   yil  ( xijr  qljr ) r   l  yil   ( xijc , qljc )

El  Elr  Elc

(2.6)

62

dimana Elr adalah biaya total untuk semua atribut numerik dari object dalam clusterl. Elr diminimalkan jika qljr dihitung dengan persamaan (2.4).

Misalkan Cj adalah sekumpulan nilai unik yang terdapat dalam atribut kategorikal j dan p(cj Cj|l) adalah probabilitas dari kemunculan nilai cj di dalam clusterl. maka Elc dalam persamaan (2.6) bisa ditulis ulang dengan

mc

Elc   l  nl (1  p(qljc  C j | l ))

(2.7)

j 1

dimana nladalah jumlah object di dalam cluster. Solusi untuk meminimalisasi Elc dijelaskan dengan Lemma 1 berikut.

Lemma 1: untuk sebuah cluster khusus l, Elc diminimalisasi jika dan hanya jika p(qljc  C j | l )  p(c j  C j | l ) untuk qljc  c j untuk semua atribut kategorikal.

Akhirnya E bisa dituliskan ulang dengan

k

k

k

l 1

l 1

l

E   ( Elr  Elc )   Elr   Elc  E r  E c

(2.8)

Persamaan (2.8) adalah cost function untuk Clustering dataset dengan atribut bernilai numerik dan kategorikal. Karena Er dan Ec adalah non-negatif, minimalisasi E bisa dilakukan dengan meminimalkan Er dan Ec, total cost dari atribut numerik dan kategorikal untuk semua cluster.

63

BAB III METODE PENELITIAN

3.1

Tempat dan Waktu Penelitian Penelitian ini mengusulkan metode Clustering K-Prototype yang

dioptimasi dengan Algoritma Genetika untuk melakukan optimasi pada pusat cluster, untuk mendapatkan pusat cluster yang optimal, sehingga memperoleh akurasi dari cluster yang lebih baik. Pelaksanaan penelitian ini dilakukan di Program Magister Jurusan Teknik Elektro Fakultas Teknik, Universitas Udayana. Dimana data uji yang aka digunakan adalah German Credit Data Set. German Credit Dataset adalah dataset yang banyak digunakan dalam permasalahan klasifikasi untuk penilaian kelayakan pemberian kredit.

3.2

Alur Analisis Penelitian merupakan investigasi yang sistematis, terkontrol, empiris dan

kritis dari suatu proposal hipotesis mengenai hubungan tertentu antar fenomena. Penelitian disini bertujuan untuk memberikan kontribusi terhadap ilmu pengetahuan dalam memecahkan masalah dengan menggunakan metode-metode yang sesuai. Alur analisis usulan penelitian dilakukan berdasarkan permasalahan yang ditangani sistem. Pembahasan alur analisi dari metode penelitian yang akan dilakukan penulis untuk pembuatan penelitian ini, diantaranya sebagai berikut :

63

64

Gambar 3.1 Alur Analisi Penelitian 3.3

Studi Pustaka Studi pustaka merupakan pengumpulan data ataupun pengumpulan referensi

mengenai teori yang nantinya dijadikan sebagai pedoman-pedoman sesuai dengan penelitian yang diangkat. Manfaat dari studi literatur adalah dapat memberikan Gambaran menyeluruh mengenai sejauh mana perkembangan penelitianpenelitian yang terkait dengan penelitian yang akan diambil. Dalam penelitian ini, referensi diperoleh dari jurnal, artikel laporan penelitian, dan buku yang berhubungan mengenai penelitian yang berjudul Optimasi Pusat Cluster pada KPrototype menggunakan Algoritma Genetika.

65

3.4

Pengumpulan Data Berdasarkan sumbernya, data penelitian dapat dikelompokkan menjadi dua

jenis yaitu data primer dan data sekunder. Pemahaman terhadap kedua jenis data tersebut diperlukan sebagai landasan dalam menentukan teknik serta langkahlangkah pengumpulan data penelitian.

1. Data Primer adalah data yang diperoleh atau dikumpulkan oleh peneliti secara langsung dari sumber datanya. Data primer disebut juga sebagai data asli atau data baru yang memiliki sifat up to date. Untuk mendapatkan data primer, peneliti harus mengumpulkannya secara langsung. Teknik yang dapat digunakan peneliti untuk mengumpulkan data primer antara lain observasi, wawancara, diskusi terfokus (focus grup discussion – FGD) dan penyebaran kuesioner. 2. Data Sekunder adalah data yang diperoleh atau dikumpulkan peneliti dari berbagai sumber yang telah ada (peneliti sebagai tangan kedua). Data sekunder dapat diperoleh dari berbagai sumber seperti Biro Pusat Statistik (BPS), buku, laporan, jurnal, dan lain-lain.

66

3.5

Gambaran Umum Sistem

Input Data

Input Kategori Jumlah Populasi

Generasi Max

Eksekusi Program

K-Protoype dengan GA

K-Prototpye tanpa GA

K-Means

Pengujian Total Cost

Pengujian Total Cost

Pengujian Total Cost

Hasil

Hasil

Hasil

Simpan Hasil

Deskripsi

Gambar 3.2 Gambaran Umum Sistem

Jumlah Cluster

67

3.5.1

Data Uji

Penelitian ini nantinya akan menggunakan data uji yang banyak dipakai dalam permasalahan klasifikasi untuk penilaian kelayakan pemberian kredit yang disebut German Credit Dataset, data set ini didonasikan oleh Prof. Hofman dari Hamburg University, Jerman. Dataset ini terdiri dari 1000 record dan 20 variabel ditambah dengan sebuah variabel target atau variabel response, dimana 13 variabel diantaranya bertipe kategori dan sisanya sebanyak 7 variabel bertipe numerik.

German Credit Dataset ini dapat diunduh di UCI Machine Learning

Repository.

Studi kasus yang diangkat dalam penelitian ini adalah mengenai segmentasi pasar. Pendefinisian pemasaran memberikan definisi yang lebih terinci dengan mengatakan bahwa segmentasi pasar adalah proses membagi-bagi pasar yang semula berperilaku heterogen menjadi beberapa kelompok pasar yang sekarang berperilaku lebih seragam (Teguh,1993:52). Menurut Warren (1995), penentuan segmentasi pasar berdasarkan pada beberapa kriteria diantaranya: Segmentasi demografis didasarkan pada karakteristik populasi yang dapat diukur dari umur, jenis kelamin, pendapatan, pendidikan, dan pekerjaan. Segmentasi Psikografis adalah proses pengelompokkan orang dalam arti sikap, nilai-nilai yang dianut, dan gaya hidup. Segmentasi tingkah laku memfokuskan pada apakah orang akan membeli dan menggunakan suatu produk atau tidak, disamping seberapa sering dan berapa banyak yang dipakainya. Konsumen dapat dikategorikan menurut tingkat penggunaan, misalnya, pengguna berat, sedang,

68

ringan, dan bukan pengguna. Segmentasi manfaat (Benefit Segmentation), memfokuskan pada nilai persamaan (value equation). Pendekatan ini dapat memberikan hasil yang memuaskan karena pemahaman pemasar yang luar biasa terhadap masalah yang dapat diselesaikan oleh suatu produk atau manfaat yang ditawarkannya, tanpa mempedulikan wilayah geografisnya. Menurut Teguh (1993), segmentasi juga didasarkan pada kebiasaan (membeli, mengkonsumsi, dsb.) berikut contoh data dari German Credit Dataset:

Gambar 3.3 Contoh Data Uji

69

Dengan spesifikasi data sebagai berikut: Tabel 3.1 Spesifikasi German Credit Dataset No 1

Nama Variabel Status of existing checking

Tipe Categorical variabel

account 2 3

Duration in month Credit history

Numeric Categorical

4

Purpose

Categorical

5 6

Credit amount Savings account/bonds

Numeric Categorical

7

Present employment since

Categorical

8 9

Installment rate in percentage Personal status and sex of disposable income

Numeric Categorical

10

Other debtors / guarantors

Categorical

11 12

Present residence since Property

Numeric Categorical

13 14

Age in years Other installment plans

Numeric Categorical

15

Housing

Categorical

Nilai A11 A12 A13 A14

Keterangan Nilai ... < 0 DM 0 <= ... < 200 DM ... >= 200 DM no checking account

A30 A31 A32 A33 A34

no credits taken/ all credits paid back all credits at this bank paid back duly duly existing credits paid back duly till now delay in paying off in the past critical account/ other credits existing

A40 A41 A42 A43 A44 A45 A46 A47 A48 A49 A410

(not at this bank) car (new) car (used) furniture/equipment radio/television domestic appliances Repairs Education Vacation Retraining Business Others

A61 A62 A63 A64 A65 A71 A72 A73 A74 A75

... < 100 DM 100 <= ... < 500 DM 500 <= ... < 1000 DM ..>= 1000 DM unknown/ no savings account Unemployed ... < 1 year 1 <= ... < 4 years 4 <= ... < 7 years ..>= 7 years

A91 A92 A93 A94 A95 A101 A102 A103

male:divorced/separated female: divorced/separated/married male : single male : married/widowed female : single None co-applicant Guarantor

A121 A122 A123 A124

real estate if not A121 : building society savings if not A121/A122 : car or other, not in agreement/ attribute 6 unknown / no property life insurance

A141 A142 A143 A151

Bank Stores None Rent

70

16 17

Number of existing credits at Job this bank

Numeric Categorical

18 19

Number of people being Telephone liable to provide maintenance

Numeric Categorical

20

foreign worker for

Categorical

A152 A153

Own for free

A171 A172 A173 A174

unemployed/ unskilled - non-resident unskilled – resident skilled employee / official management/ self-employed/ highly qualified employee/ officer

3.5.2

A191 A192 A201 A202

None yes, registered under the customers Yes name No

Inputan Kategori

3.5.2.1 Jumlah Populasi Jika jumlah kromosom yang digunakan terlalu sedikit, maka individu yang dapat digunakan untuk proses crossover dan mutasi akan sangat terbatas, sehingga menyia-nyiakan proses yang ada. Tetapi jika jumlah kromosom yang digunakan terlalu banyak, akan memperlambat proses algoritma genetika yang dilakukan. Populasi semakin banyak dalam satu generasi, maka akan menghasilkan solusi yang lebih baik. 3.5.2.2 Generasi Max Mempengaruhi jumlah komputasi yang dilakukan pada saat pengolahan data, dimana 1 generasi dapat mewakili jumlah populasi yang telah ditentukan. jika terdapat 10 generasi dan jumlah populasi 50 maka komputasi yang dilakukan akan sebanyak 500 kali sehingga menghasilkan kromosom yang lebih variatif dalam proses fitness. Kromosom menjadi variatif dikarenakan pada saat pencarian nilai fitness terbaik pada generasi pertama telah selesai, maka selanjutnya

71

dilakukan proses pindah silang dari populasi yang ada, sehingga pada generasi selanjutnya akan menghasilkan populasi yang baru.

3.5.2.3 Jumlah Cluster Untuk menggelompokkan data yang diolah sesuai dengan jumlah cluster yang diinginkan, dan sebagai perbandingan dari hasil yang diperoleh pada saat jumlah cluster yang berbeda. 3.5.3

Clustering K-Prototype dengan Algoritma Genetika Metode yang digunakan dalam penelitian ini adalah gabungan dari metode

Clustering K-Prototype dengan Genetic Algorithm(GA) atau Algoritma Genetika. Penelitian ini akan mencoba melakukan optimasi pusat cluster dari algoritma Clustering K-Prototype dengan menggunakan Algoritma Genetika. Penelitin ini diharapkan memperoleh pusat cluster yang lebih optimal sehingga nantinya akan membantu proses terbentuknya cluster-cluster yang lebih akurat dan untuk mencapai tingkat komputasi lebih baik dengan tipe dataset campuran.

Desain dari optimasi yang dilakukan pada K-Prototype terletak pada pusat cluster. Jadi ketika pusat cluster di optimasi dengan Algoritma Genetik diharapkan K-Prototype mempunyai awalan prototype yang bagus, sehingga untuk proses selanjutnya dapat memperoleh cluster lebih yang lebih akurat dan cepat.

72

Mulai

Data Normal

Inisialisasi populasi Awal

Clustering menggunakan K-Prototype

Evaluasi Fitness

Apakah Optimasi tercapai

Pusat Cluster Optimal

Selesai

Seleksi

Pindah Silang

Populasi Individu Baru

Gambar 3.4 Clustering K-Prototype dengan GA 3.5.3.1 Inisialisasi Populasi Awal Fase inisialisasi populasi ini digunakan untuk menentukan sejumlah kromosom awal yang akan digunakan untuk komputasi selanjutnya. Panjang gen ini adalah sama dengan jumlah K (jumlah cluster) dari proses Clustering. Dimana masing-masing nilai yang ada pada gen akan mewakili no record data pada proses Clustering. Berdasarkan penelitian sebelumnya yang dilakukan oleh Liu dengan

73

menggunakan data uji yang sama yaitu segmentasi pasar dengan pemberian data kredit.

Nilai yang terkandung dalam gen berupa integer yang dibangkitkan secara acak dengan nilai 0-1000 sesuai jumlah record data. Maka bentuk kromosom yang akan digunakan:

243

543

743

854

....

...

...

...

...

...

...

....

126

478

967

543

Sesuai Dengan Jumlah Populasi.

Gambar 3.5 Contoh Kromosom

3.5.3.2 Clustering menggunakan K-Prototype Tahap ini dilakukan setelah populasi awal terbentuk. Setiap kromosom yang terbentuk pada fase inisialiasi populasi akan melewati proses Clustering. Jumlah cluster akan ditentukan oleh nilai gen terakhir yang ada pada setiap kromosom. Algoritma yang digunakan untuk melakukan Clustering pada data dengan tipe campuran numerik dan kategorikal ini adalah K-Prototype. Algoritma ini dipilih karena sangat sederhana dari sisi kompleksitas algoritma dan mampu menangani data dengan ukuran yang sangat besar dan dengan tipe data campuran.

74

Pada proses Clustering dengan K-Prototype disini dilakukan beberapa proses penting yaitu : 1.

Inisialiasi awal prototype Pada proses ini akan dilakukan pemilihan sejumlah k prototype dari datasetX sesuai dengan jumlah cluster yang ditentukan. Dimana dalam tahap ini menentukan atribut dari kategorikal dan numerik. Nilai dari prototype numerik adalah rerata atau mean dari setiap nilai numerik pada setiap atribut numerik di setiap cluster yang terbentuk. Sedangkan prototype kategorikal berisi modus dari setiap nilai kategorikal pada setiap atribut kategorikal di setiap cluster yang terbentuk.

Pada inisialisasi awal prototype menggunakan urutan data record yang sesuai dengan nilai yang ada pada gen di masing-masing kromosom. Misalnya:

Gambar 3.6 Inisialisasi awal

75

2.

Ukur Jarak Objek ke semua prototype dan tempatkan objek pada cluster terdekat. Alokasi objek di dalam X ke Cluster dengan prototype terdekat. Tahap ini algoritma K-Prototype mengalokasikan semua object didalam dataset ke cluster dimana prototype dari cluster tersebut memiliki jarak yang paling dekat ke object data. Pengalokasian semua object di dalam daset X ke cluster yang memiliki jarak prototype terdekat dengan object yang diukur. Untuk setiap kali object X selesai dialokasikan, maka selanjutnya akan dilakukan penghitungan (update) terhadap prototype cluster yang berkaitan.

3.

Realokasi object jika terjadi perubahan prototype Setelah semua object dalam X selesai dialokasikan, selanjutnya akan dilakukan pengukuran ulang jarak antara semua object di dalam X terhadap semua prototype yang ada. Proses ini akan terus dilakukan sampai tidak ada lagi perubahan prototype.

3.5.3.3 Evaluasi Fitness Menggunakan Cost Function Criterion Dalam penelitian ini, Clustering criterion yang digunakan adalah cost function, atau biaya yang dihabiskan untuk menempatkan object pada cluster yang bersesuaian. Semakin kecil biaya (cost) yang dikeluarkan, maka semakin bagus hasil Clustering yang diperoleh.Hal ini berbanding terbalik dengan fungsi fitness yang diharapkan, dimana fungsi fitness mengharapkan nilai yang semakin

76

besar dari hasil evaluasi kromosom.Permasalahan ini dalam model algoritma genetika sering disebut dengan minimalisasi.

3.5.3.4 Seleksi Langkah selanjutnya dalam iterasi reproduksi ini adalah mempersiapkan individu baru pada masing-masing populasi melalui proses pindah silang (crossover) dan mutasi (mutation). Individu-individu baru yang dihasilkan pada tahap ini akan dijadikan sebagai populasi baru di generasi berikutnya. Ada beberapa langkah penting dalam proses persiapan individu baru ini, yaitu proses seleksi, pindah silang (crossover), dan mutasi (mutation). Proses seleksi bertujuan untuk memilih individu-individu yang akan dipindahsilangkan atau dikenal dengan istilah parent pada proses pindah silang (crossover), dan juga akan dimutasikan. Seleksi dilakukan untuk mendapatkan calon induk yang baik. Istilahnya Induk yang baik akan menghasilkan keturunan yang baik. Semakin tinggi nilai fitness suatu individu semakin besar kemungkinannya untuk terpilih. Seleksi disini menggunakan seleksi dengan teknik Roulette-Wheel, dimana dengan rumus : Pr(hi) = Fitness (hi) / Σj = 1p Fitness (hj)

(3.1)

3.5.3.5 Pindah Silang Operator pindah silang mempunyai peran penting dalam algoritma genetika karena didalamnya terdapat proses perkawinan (persilangan) gen antara dua individu (parent) yang menghasilkan dua individu baru (offspring) pada

77

generasi berikutnya. Penentuan individu yang berhak melakukan operasi crossover tergantung pada probabilitas crossover (Pc) yang telah ditentukan.

Operator pindah silang yang digunakan dalam penelitian ini menggunakan satu titik potong, Pada pindah silang satu titik (one-point crossover), satu titik sepanjang kromosom dipilih secara random. Segmen induk dari titik point ke kiri atau kekanan ditukar untuk menghasilkan individu baru. sehingga nantinya setiap anaknya akan terdiri dari sebagian pasangan parentnya.

3.5.3.6 Mutasi Mutasi menciptakan individu baru dengan melakukan modifikasi satu atau lebih gen dalam individu yang sama. Mutasi berfungsi untuk menggantikan gen yang hilang dari populasi selama proses seleksi serta menyediakan gen yang tidak ada dalam populasi awal. Mutasi akan meningkatkan variasi populasi.Individu yang terpilih untuk proses mutasi dapat dilakukan dengan membandingkan nilai probabilitas mutasinya dengan probabilitas mutasi yang telah ditentukan atau dapat dipilih secara acak (random).

3.5.4

Clustering K-Prototype Tanpa GA K-Prototype adalah salah satu metode Clustering yang berbasis

partitioning. Algoritma ini menangani Clustering pada data dengan campuran atribut bertipe numerik dan kategorikal. Pada proses Clustering dengan K-Prototype disini dilakukan beberapa proses yaitu :

78

Mulai

Inisialisasi Prototype

Ukur Jarak Object ke Semua Prototype, Tempatkan Object pada Cluster Terdekat

Hitung Ulang Prototype Ya

Terjadi Perubahan Prototype

Tidak

Selesai

Gambar 3.7 Alur Cluster K-Prototype

1.

Inisialiasi awal prototype Pada proses ini akan dilakukan pemilihan sejumlah K-Prototype dari dataset X sesuai dengan jumlah cluster yang ditentukan.

2.

Ukur Jarak Objek ke semua prototype dan tempatkan objek pada cluster terdekat. Pada proses ini akan dilakukan pengalokasian semua object di dalam dataset X ke cluster yang memiliki jarak prototype terdekat dengan object yang diukur.

79

3.

Hitung ulang prototype. Realokasi object Jika terjadi perubahan prototype. Setelah semua object dalam X selesai dialokasikan, selanjutnya akan dilakukan pengukuran ulang jarak antara semua object di dalam X terhadap semua prototype yang ada. Jika terjadi perubahan, maka proses akan diulang ke proses sebelumnya yaitu mulai dari Ukur Jarak Objek ke semua prototype dan tempatkan objek pada cluster terdekat.

4.

Jika tidak terjadi perubahan maka proses selesai.

3.5.5

Clustering K-Means K-Means Clustering merupakan

sebuah

algoritma

untuk

mengelompokkan data berdasarkan atribut-atribut ke dalam K kelompok. KMeans juga merupakan bilangan positif dan pengelompokan dilakukan dengan meminimalisasi jumlah jarak setiap data ke-cluster-nya. Menurut J. Macqueen (1967), J.A. Hartigan dan M.A. Wong (1975), K-Means Clustering adalah sebuah algoritma untuk mengelompokkan data, berdasarkan pada atribut– atribut atau feature–feature ke dalam K kelompok (grup). Prinsip utama dari teknik ini adalah menyusun K buah prototype atau pusat massa (centroid) atau rata-rata (mean) dari sekumpulan data berdimensi N. Teknik ini mensyaratkan nilai K sudah diketahui sebelumnya. Algoritma K-Means dimulai dengan pembentukan prototype cluster di

awal

kemudian secara iteratif prototype

cluster ini diperbaiki hingga konvergen (tidak terjadi perubahan yang signifikan pada prototype cluster).

80

K-Means merupakan metode pengklasteran secara partitioning yang memisahkan data kedalam kelompok yang berbeda dimana cluster (K) merupakan konstanta jumlah cluster yangdiinginkan maka K harus ditentukan sebelumnya (contoh: K = 5 cluster). Sedangkan means berarti nilai suatu rata-rata dari suatu grup data yang dalam hal ini didefinisikan sebagai cluster. Sehingga dapat disimpulkan bahwa algoritma ini menggunakan K nilai rata-rata yangsetiap nilai rata-ratanya dihitung dari suatu cluster. Kalau ada 5 cluster, maka akan ada 5 ratarata yang dipakai oleh algoritma ini. Algoritma K-Means clustering merupakan algortima iteratif dengan meminimalkan jumlah kuadrat error antara vektor objek dengan pusat kluster terdekatnya, yaitu:

(3.2)

mj adalah pusat cluster (mean vector ) dalam kluster ke j. Proses dimulai dengan memilih secara random k buah data sebagai pusat cluster awal.Pada tahap awal, algoritma K-Means memilih secara acak k buah data sebagai centroid. Kemudian, jarak antara data dan centroid dihitung menggunakan Euclidian distance. Data ditempatkan dalam cluster yang terdekat, dihitung dari titik tengah cluster. Centroid baru akan ditentukan bila semua data telah ditempatkan dalam cluster terdekat. Proses penentuan centroid dan penempatan data dalam cluster diulangi sampai nilai centroid konvergen(centroid dari semua cluster tidak

81

berubah lagi). Data clustering menggunakan metode K-Means ini secara umum dilakukan dengan algoritma dasar sebagai berikut: Mulai

Tentukan Jumlah Cluster K

Tentukan Asumsi Centroid

Hitung Jarak Obyek ke Cluster

Ya

Apakah Obyek Berpindah?

Tidak Selesai

Kelompokkan Obyek berdasarkan jarak minimum

Gambar 3.8 Flowchart K-Means Clustering Keterangan: 1.

Algoritma menerima jumlah cluster untuk mengelompokkan data ke dalamnya, dan dataset yang akan dicluster sebagai nilai input.

2.

Menentukan jumlah cluster. Sebagai contoh, jika terdapat 10.000 baris data di dalam dataset dan 3 cluster perlu dibentuk, maka K=3 cluster awal

82

pertama akan dibuat dengan mengambil 3 record secara random dari dataset, sebagai cluster permulaan. 3.

Setiap cluster yang terbentuk akan dihitung nilai rata-ratanya. Rata-rata dari suatu cluster adalah rata-rata dari semua record yang terdapat di dalam cluster tersebut.

4.

Alokasikan data ke dalam cluster secara random.

5.

Hitung centroid /rata-rata dari data yang ada di masing-masing cluster

6.

Alokasikan masing-masing data ke centroid /rata-rata terdekat

7.

Ulangi langkah-langkah sebelumnya sampai terbentuk cluster-cluster stabil dan prosedur K-Means selesai. Cluster stabil terbentuk ketika iterasi atau perulangan dari K-Means tidak membuat cluster baru sebagai pusat cluster atau nilai rata-rata aritmatika dari semua cluster baru sama dengan cluster lama. Terdapat beberapa teknik untuk menentukan kapan suatu cluster stabil terbentuk atau kapan algoritma K-Means berakhir.

3.5.6

Pengujian Total Cost Total cost adalah biaya yang dihabiskan untuk menempatkan setiap object

ke dalam cluster terdekat. Total biaya ini adalah setara dengan total jarak dari setiap object ke cluster tempat dia berada. Semakin kecil biaya yang dihasilkan berarti jarak antara semua obyek dengan clusternya semakin dekat. Sehingga bisa dikatakan bahwa cluster yang terbentuk semakin kompak. Clustering sendiri bertujuan tuntuk memperoleh kesamaan ciri-ciri dari setiap object pada cluster tertentu, jika ukuran cluster semakin lebar maka kesamaan ciri-ciri yang ada pada

83

sekumpulan object juga akan semakin rendah, sehingga bisa dikatakan bahwa hasil cluster tersebut kurang bagus. Pada tahap pengujian ini, total jarak yang diukur tidak hanya dari hasil penggabungan K-Prototype dengan Algortima Genetika, tetapi dapat dibandingan dengan metode yang lainnya yaitu total jarak K-Prototype, dibandingkan juga dengan total jarak K-Means.

3.5.7

Hasil Hasil dari pengujian yang dilakukan pada masing-masing algoritma akan

disajikan dalam bentuk tabel untuk pusat clusterdan grafik 3D untuk menggambarkan posisi pusat cluster, serta menampilkan total jarak yang dihasilkan pada proses pengujian tersebut.

3.5.8

Deskripsi Pada tahapan deskripsi, akan digunakan untuk memunculkan nilai-nilai

dominan yang akan menjadi ciri-ciri dari masing-masing kelompok atau segment. Sehingga informasi ini nantinya akan dapat ditindaklanjuti sebagai bahan pertimbangan untuk pengambilan keputusan dan juga memungkinkan untuk melakukan pendekatan marketing yang sesuai dengan ciri-ciri dominan dari kelompok-kelompok yang terbentuk.

84

3.6

Instrumen Penelitian Instrumen penelitian yang akan digunakan dalam penelitian ini untuk

mengumpulkan, mengolah, menganalisa dan menyajikan data-data diantanya: 1.

Perangkat Lunak (Software) a. Sistem Operasi Windows 7 b. Matlab dan beberapa toolbox bantuan.

2.

Perangkat Keras (Hardware) a. Processor 2,3 GHz b. 2048 MB RAM c. Hardisk 40 GB d. VGA 64 MB

BAB IV HASIL DAN PENGUJIAN

4.1

Antarmuka Sistem Antarmuka sistem ini dipersiapkan untuk mempermudah penggunaan

aplikasi ini. Ada dua bagian atau antarmuka yang disiapkan, yaitu : antarmuka untuk aplikasi clustering, dan antarmuka deskripsi yang dipergunakan untuk menampilkan hasil cluster yang telah dilakukan.

4.2

Antarmuka Aplikasi Clustering

Gambar 4.1 Tampilan Aplikasi Clustering

Aplikasi clustering data ini adalah antarmuka utama dari penelitian ini, seperti terlihat pada Gambar 4.1.

85

86

4.2.1

Input Dataset. Pada panel dataset digunakan untuk memanggil data yang akan diolah,

kemudian ditampilkan dalam bentuk Grid, serta menampilkan posisi dari variabel kategorikal.

Gambar 4.2 Tampilan Dataset

Cara Penggunaan dalam pemanggilan data yang akan diolah dengan memilih tombol Load

Dataset. Kemudian akan muncul jendela baru untuk

memilih data yang diolah dengan format .mat.

Gambar 4.3 Pemilihan Data Uji.

87

Setelah data dipilih kemudian pilih tombol Open, maka data yang dipilih secara otomatis akan ditampilkan pada Grid seperti yang ditampilkan pada Gambar 4.4.

Gambar 4.4 Data telah di-load Dataset yang banyak dipakai dalam permasalahan clustering untuk penilaian kelayakan pemberian kredit yang disebut German Credit Dataset, Dataset yang ditampilkan berupa grid terdiri dari 1000 record data dan 20 variabel, dimana 13 variabel diantaranya bertipe kategori dan sisanya sebanyak 7 variabel bertipe numerik. Posisi variabel kategorikal sudah bisa ditentukan pada saat melakukan proses pre processing, dimana letak variabel kategorikal terletak pada kolom 1,3,4,5,7,9,10,12,14,15,17,19,20. Letak variabel numerik pada kolom 2,6,8,11,13,16,18.

88

4.2.2

Inputan Kategori

Gambar 4.5 Tampilan Penetapan Variabel

Pada saat melakukan input kategori hal pertama yang dilakukan adalah melakukan penentuan atribut dengan memilih 3 buah atribut bebas dari 20 jumlah atribut yang ada. Misalkan atribut pertama diisi dengan angka 8, atribut kedua diisi dengan angka 9 dan atribut ketiga diisi dengan angka 18. Setelah ditentukan maka pilih tombol tampilkan, sehingga akan muncul hasil seperti pada Gambar 4.5.

Tahap kedua dilakukan pengisian textbox pada Total Populasi yang dapat diisi bebas dengan angka, misal diisi 30. Total Populasi dapat mempengaruhi hasil dan waktu yang dibutuhkan untuk melakukan proses. Apabila Total Populasi yang digunakan semakin banyak dalam satu generasi, maka akan menghasilkan solusi yang lebih baik, dan jika jumlah kromosom yang digunakan terlalu sedikit, maka individu yang dapat digunakan untuk proses crossover dan mutasi akan sedikit.

Tahap ketiga, dilakukan pengisian textbox pada Generai Max yang dapat diisi bebas dengan angka misal 5. Dimana 1 generasi dapat mewakili jumlah

89

populasi yang telah ditentukan pada tahap pengisian Total Populasi, sehingga menghasilkan kromosom yang lebih variatif dalam proses fitness, pada generasi selanjutnya akan menghasilkan populasi yang baru. Tahap

Keempat

melakukan

penentuan

jumlah

menggelompokkan data yang diolah sesuai dengan

cluster

untuk

jumlah cluster yang

diinginkan. Fungsi ini diberikan agar user dapat mencoba dengan berbagai jumlah cluster, dan untuk mengetahui hasil yang diberikan oleh algoritma jika dicobakan pada jumlah cluster yang berbeda.

4.2.3

Eksekusi Program Eksekusi program utama bertujuan untuk mendapatkan pusat cluster yang

optimal

dari Dataset yang diujikan dalam penelitian ini, yaitu German Credit

Dataset. Hasil eksekusi akan menghasilkan pusat cluster yang disajikan dalam bentuk grid, dan grafik dalam setiap percobaan. Eksekusi program ini menggunakan tiga perbandingan metode yaitu: Gabungan metode K-Prototype dengan Algortima Genetika, metode K-Prototype tanpa Algoritma Genetika, Metode K-Means Clustering.

4.2.3.1 Hasil K-Prototype dengan GA Pada

tampilan

Gambar

4.6.

ini

merupakan

eksekusi

program

menggunakan K-Prototype dengan Algoritma Genetika. Setelah proses penentuan atribut, maka atribut yang dipilih akan ditampilkan dalam bentuk grafik 3D.

90

Gambar 4.6 Tampilan K-Prototype Dengan GA

Eksekusi Program yang pertama dapat dilakukan dengan memilih tombol "RUN GA", dan hasil eksekusi program dapat dilihat pada Gambar 4.7.

Gambar 4.7 Hasil Uji K-Protoype dengan GA

91

Dari hasil pengujian K-Protoype dengan GA dapat dilihat bahwa total cost yang diperlukan adalah 2623,25. Dengan posisi masing-masing pusat cluster dapat dilihat pada Grid, dan digambarkan pada grafik serta waktu yang dibutuhkan dalam melakukan pengujian sebesar 288,8089 detik. Untuk memperoleh hasil seperti diatas, maka dilakukan beberapa fase yang merupakan penggabungan Algoritma Genetika dan Algortima K-Prototype. Beberapa fase yang dilewati pada saat Eksekusi Program yaitu:

1)

Fase Inisialisai Fase inisialisasi populasi digunakan untuk menentukan kromosom awal dimana kromosom awal yang ditentukan pada saat percobaan input kategori sebanyak 30 kromosom yang dipilih secara acak seperti Gambar 4.8. dengan

jumlah cluster sebanyak 4. Nilai yang ada disetiap kolom menggambarkan urutan penempatan dari pusat cluster untuk pertama kali dalam proses clustering.

Gambar 4.8 Inisialisasi kromosom awal

92

2)

Fase Clustering menggunakan K-Prototype Setiap Kromosom yang terbentuk pada fase Inisialisasi akan melewati

proses clustering. Algoritma yang digunakan untuk melakukan clustering pada data dengan tipe numerik dan kategorikal adalah K-Prototype. Algoritma ini dipilih karena sangat sederhana dari sisi kompleksitas algoritma dan mampu menangani data dengan ukuran yang sangat besar. Ada beberapa tahapan yang dilakukan pada saat Clustering dimana Tahap pertama merupakan tahap inisialisasi awal prototype. Tahap Inisialisasi awal prototype menggunakan urutan data record yang ada pada masing-masing kromosom sesuai dengan nilai yang dimiliki. Kromosom yang digunakan akan dipisahkan sehingga membentuk dua buah protoype. Prototype yang pertama merupakan prototype numerik dimana merupakan rerata atau mean dari setiap nilai numerik pada setiap atribut numerik di setiap cluster yang terbentuk dan prototype yang kedua prototype kategorikal berisi modus dari setiap nilai kategorikal pada setiap atribut kategorikal di setiap cluster yang terbentuk. Proses inisialisasi awal prototype terhadap sebuah kromosom dapat dilihat pada Gambar 4.9.

93

(a)

(b)

(c)

Gambar 4.9 (a) Nilai kategorikal dan numerik pada kromosom (b) Nilai kategorikal pada kromosom (c) nilai numerik pada kromosom

Tahap Kedua merupakan tahapan pengukuran jarak object ke semua prototype dan menempatkan objek pada cluster terdekat.

Tahap Ketiga

merupakan tahapan pengukuran ulang jarak antara semua object terhadap semua prototype yang ada. Jika ditemukan adanya object yang ternyata lebih dekat ke prototype yang lain, maka akan dilakukan pemindahan keanggotaan dan kemudian akan dilakukan update terhadap prototype cluster lama dan prototype cluster baru sampai akhirnya tidak ada perubahan.

94

3)

Fase Evaluasi Fitness Nilai Fitness digunakan untuk mencari nilai terbaik dari pengolahan

clustering yang dilakukan. Setelah dilakukan clustering terhadap dataset dengan model kromosom yang bersesuaian, maka proses selanjutnya adalah melakukan penilaian terhadap hasil clustering tersebut. Metode pengukuran hasil clustering sering disebut dengan Clustering Criterion. Clustering Criterion inilah yang akan dijadikan nilai fitness dari setiap kromosom yang telah dievaluasi.

Dalam penelitian ini, clustering criterion yang digunakan adalah cost function, atau biaya yang dihabiskan untuk menempatkan object pada clusteryang bersesuaian. Semakin kecil biaya (cost) yang dikeluarkan, maka semakin bagus hasil clustering yang diperoleh. Hal ini berbanding terbalik dengan fungsi fitness yang diharapkan, dimana fungsi fitness mengharapkan nilai yang semakin besar dari hasil evaluasi kromosom. Beberapa nilai Fitness yang dihasilkan tiap kromosom yaitu:

95

Gambar 4.10 Hasil Nilai Fitness

Nilai Fitness Terbaik dapat dilihat pada Gambar 4.10, dimana terletak pada baris ke 29 yang disebut sebagai individu terbaik dengan nilai Fitness 3.8060e-04. Nilai Fitness yang telah didapat akan dilakukan proses pengecekan apakah Nilai Fitness tersebut yang terbaik dengan sebelumnya.

96

4)

Seleksi Sebelum seleksi melakukan fase Elitisme dilakukan proses pengkopian

individu yang mempunyai nilai fitness tertinggi sebanyak satu (bila jumlah individu dalam suatu populasi adalah ganjil) atau dua (bila jumlah individu dalam suatu populasi adalah genap). Hal ini dilakukan agar

individu ini tidak

mengalami kerusakan (nilai fitness-nya menurun) selama proses pindah silang maupun mutasi. Proses pengkopian individu terbaik dapat digambarkan sebagai berikut :

Gambar 4.11 Pengkopian Individu Terbaik Populasi terbaik yang telah dikopi, akan dilanjutkan dengan proses seleksi. Proses seleksi menggunakan algoritma roulette-wheel dimana proses tersebut dilakukan dengan mengambil 2 buah kromosom sehingga menghasilkan nilai Parent 1 (IP1) dan Parent 2 (IP2) yang nantinya akan digunakan pada proses Pindah Silang. Hasil roulette-wheel pada kromosom 3 dan 4 dapat dilihat pada Gambar 4.12. Nilai 29 untuk IP 1 dan nilai 13 untuk IP2, menggambarkan kromosom ke-29 dan ke-13 pada populasi.

Gambar 4.12 Hasil Roulette-Wheel

97

5)

Pindah Silang Setelah melewati fase seleksi, selanjutnya melakukan proses pindah silang,

dimana didalamnya terdapat proses perkawinan (persilangan) gen antara dua individu (parent) yang menghasilkan dua individu baru (offspring) pada generasi berikutnya. Dengan membuat sebuah "child" atau anak, sebuah solusi baru telah dibuat, dimana pada umumnya anak akan mewarisi bagian-bagian dari orang tuanya. Orang tua baru dipilih lagi dan membuat suatu anak solusi lagi, dan berlanjut sampai suatu populasi solusi baru dengan ukuran yang cukup terbentuk.

Operator pindah silang yang digunakan dalam penelitian ini menggunakan satu titik potong, satu titik sepanjang kromosom dipilih secara random. Segmen induk dari titik point ke kiri atau kekanan ditukar untuk menghasilkan individu baru. Sehingga nantinya setiap anaknya akan terdiri dari sebagian pasangan parentnya. Hasil dari proses pindah silang berdasarkan parent 1 dan parent 2 yang didapat pada proses roulette-wheel dapat dilihat pada Gambar 4.13.

Gambar 4.13 Hasil pindah silang

98

6)

Mutasi Operator berikutnya pada algortima genetika adalah mutasi gen. Operator

ini berperan untuk menggantikan gen yang hilang dari populasi akibat proses seleksi yang memungkinkan munculnya kembali gen yang tidak muncul pada inisialisasi populasi awal. Mutasi berfungsi untuk menggantikan gen yang hilang dari populasi selama proses seleksi. Sehingga mutasi akan meningkatkan variasi populasi. Peluang mutasi mengendalikan banyaknya gen baru yang akan dimunculkan untuk dievaluasi. Jika peluang mutasi terlalu kecil, banyak gen yang mungkin berguna tidak pernah dievaluasi. Tetapi bila peluang mutasi ini terlalu besar, maka akan terlalu banyak gangguan acak, sehingga anak akan kehilangan kemiripan dan induknya. Kromosom anak dimutasi dengan menambahkan nilai random yang sangat kecil (ukuran langkah mutasi), dengan probabilitas yang rendah. Peluang mutasi (Pm) didefiinisikan sebagai persentasi dan jumlah total gen pada populasi yang mengalami mutasi. Individu yang terpilih untuk proses mutasi dapat dilakukan dengan membandingkan nilai probabilitas mutasinya dengan probabilitas mutasi yang telah ditentukan atau dapat dipilih secara acak (random). Nilai yang diperoleh dari proses mutasi dapat ditampilkan pada Gambar 4.14, dimana jumlah hasil mutasi sesuai dengan jumlah populasi yang ditunjukkan yaitu sebanyak 30 kromosom, dengan jumlah cluster 4.

99

Gambar 4.14 Hasil Mutasi pada seluruh kromosom

4.2.3.2 Hasil K-Prototype tanpa GA Tampilan Gambar dibawah ini merupakan pengujian menggunakan KPrototype tanpa Algoritma Genetika. Pada grafik dapat dilihat letak tiap atribut yang dimilki oleh data.

100

Gambar 4.15 Tampilan K-Prototype Tanpa GA

Untuk menjalankan proses pengujian K-Prototype tanpa Algoritma Genetika, dapat memilih tombol RUN GA. Algoritma yang digunakan untuk melakukan clustering pada data dengan tipe campuran numerik dan kategorikal ini adalah k-prototype. Algoritma ini dipilih karena sangat sederhana dari sisi kompleksitas algoritma dan mampu menangani data dengan ukuran yang sangat besar. Algoritma K-Prototype secara umum dibagi menjadi tiga bagian yaitu : a.

Pemilihan prototype awal secara acak Istilah prototype digunakan untuk mewakili pusat cluster yang nantinya akan berisi mean dan modus dari setiap cluster yang ada. Prototypeakan berbentuk matrik dengan ukuran k x m, dimana k adalah

101

jumlah cluster dan m adalah jumlah variabel atau atribut. Nilai dari prototype numerik adalah rerata atau mean dari setiap nilai numerik pada setiap atribut numerik di setiap cluster yang terbentuk. Sedangkan prototype kategorikal berisi modus dari setiap nilai kategorikal pada setiap atribut kategorikal di setiap cluster yang terbentuk. Untuk pertama kali, prototype akan diinisialisasi dengan memilih object (record) data secara acak sejumlah k, dimana nilai k akan diambil dari gen terakhir pada setiap kromosom yang terbentuk. b.

Alokasi setiap object data ke dalam cluster Tahap kedua dari algoritma K-Prototype adalah mengalokasikan semua object didalam dataset ke cluster dimana prototype dari cluster tersebut memiliki jarak yang paling dekat ke object data. Pengukuran jarak antara object data dengan prototype ini dapat terlihat seperti pada persamaan (2.4). Setiap kali selesai dilakukan alokasi object data ke dalam cluster, maka prototype dari cluster yang bersesuaian akan diupdate.

c.

Re-alokasi object data ke cluster baru Setelah semua object teralokasi ke sebuah cluster, maka dalam tahap ketiga ini akan dilakukan pengukuran ulang jarak antara setiap object dengan semua prototype yang ada. Jika ditemukan ada object yang memiliki jarak lebih dekat dengan prototype lain diluar clusternya, maka akan dilakukan re-alokasi object tersebut ke prototype yang terdekat. Setelah proses re-alokasi ini selesai, maka prototypecluster

102

yang baru dan prototype cluster yang lama harus diupdate. Pengukuran ulang ini dilakukan terhadap semua object di dalam dataset dan dilakukan berulang sampai tidak ada lagi perubahan prototype.

Terlihat bahwa algoritma pada fase ini hampir sama dengan dengan fase atau tahap alokasi object ke dalam cluster sebelumnya. Bedanya pada fase ini akan dilakukan update terhadap prototype dari cluster lama dan cluster baru setelah proses re-alokasi.

Gambar 4.16 Hasil Uji K-Prototype Tanpa GA

Dari hasil pengujian K-Protoype tanpa GA dapat dilihat bahwa total cost yang diperlukan adalah 2657,74 serta waktu yang dibutuhkan dalam melakukan pengujian sebesar 10,8297 detik. Dengan posisi masing-

103

masing pusat cluster dapat dilihat pada Grid, dan digambarkan pada grafik.

4.2.3.3 Hasil K-Means Untuk membandingkan hasil dengan metode yang disusulkan, maka dalam penelitian ini selain menggunkan K-Prototype tanpa Algoritma Genetika juga membandingkan dengan metode clustering K-Means. Dimana tampilan yang diperoleh seperti pada Gambar 4.17 berikut:

Gambar 4.17 Hasil Uji dengan K-Means.

Dari hasil pengujian K-Means dapat dilihat bahwa total cost yang diperlukan jauh lebih besar adalah 11049,9 serta waktu yang dibutuhkan dalam melakukan pengujian sebesar 8,3772 detik. Dengan posisi masing-masing pusat cluster dapat dilihat pada Grid, dan digambarkan pada grafik.

104

Ada beberapa fase yang dilalui pada tahapan K-Means Clustering, diantara:

1.

Algoritma menerima jumlah cluster untuk mengelompokkan data ke dalamnya, dan dataset yang akan dicluster sebagai nilai input. Menentukan jumlah cluster.

2.

Setiap cluster yang terbentuk akan dihitung nilai rata-ratanya. Rata-rata dari suatu cluster adalah rata-rata dari semua record yang terdapat di dalam cluster tersebut.

3.

Alokasikan data ke dalam cluster secara random. Hitung centroid /ratarata dari data yang ada di masing-masing cluster.

4.

Alokasikan masing-masing data ke centroid/rata-rata terdekat. Uangi langkah-langkah sebelumnya sampai terbentuk cluster-cluster stabil dan prosedur K-Means selesai.

5.

Cluster stabil terbentuk ketika iterasi atau perulangan dari K-Means tidak membuat cluster baru sebagai pusat cluster.

4.2.4

Pengujian Total Cost Metode pengukuran hasil Clustering sering disebut dengan Clustering

Criterion. Clustering Criterion inilah yang akan dijadikan nilai fitness dari setiap kromosom yang telah dievaluasi. Semakin tinggi nilai fitness, maka semakin bagus kromosom yang dievaluasi tersebut. Clustering criterion yang digunakan adalah cost function, atau biaya yang dihabiskan untuk menempatkan object pada cluster yang bersesuaian. Solusi umum yang digunakan untuk menentukan apakah

105

bagus atau tidaknya suatu partisi adalah dengan menggunakan Clustering Criterion.

4.2.4.1 Total Cost Algoritma K-Prototype dengan Algoritma Genetika

Gambar 4.18 Total Cost K-Protoype dengan GA

Dari hasil pengujian K-Protoype dengan GA dapat dilihat bahwa total cost yang diperlukan adalah 2623,25. Jadi total jarak yang dihasilkan sebesar 2623,25 pada cluster yang terbentuk. Dengan posisi masing-masing pusat cluster dapat dilihat pada Grid, dan digambarkan dalam bentuk grafik pada Gambar 4.18.

106

4.2.4.2 Total Cost Algoritma K-Prototype tanpa Algoritma Genetika

Gambar 4.19 Total Cost K-Protoype tanpa GA

Dari hasil pengujian K-Protoype tanpa GA dapat dilihat bahwa total cost yang diperlukan adalah 2680.75. Jadi total jarak yang dihasilkan sebesar 2680.75 pada cluster yang terbentuk. Dengan posisi masing-masing pusat cluster dapat dilihat pada Grid, dan digambarkan pada Gambar 4.19.

107

4.2.4.3 Total Cost Algoritma K-Means

Gambar 4.20 Total Cost K-Means

Dari hasil pengujian K-Means dapat dilihat bahwa total cost yang diperlukan adalah 9579,46. Jadi total jarak yang dihasilkan sebesar 9579,46 pada cluster yang terbentuk. Posisi masing-masing pusat cluster dapat dilihat pada Grid, dan digambarkan pada Gambar 4.20.

108

4.2.5

Hasil Percobaan Hasil pengujian untuk Optimasi K-Prototype dengan GA, K-Protoype

Tanpa GA,

dan K-Means ditunjukkan seperti pada Tabel 4.1. Beberapa

percobaan dilakukan untuk melihat perbedaan total cost untuk tiap-tiap metode. Berdasarkan hasil yang ditunjukkan pada Tabel 4.1, diperoleh keterangan bahwa K-Prototype dengan GA menghasilkan total cost terkecil dari pada metode lainnya. Hasil ini dipengaruhi oleh penentuan total populasi dan maksimum generasi. Dalam hal ini, total populasi dan generasi maksimum masing-masing sebesar tigapuluh dan lima. Tabel 4.1 Tabel Percobaan untuk Perhitungan Total Cost K-Prototype dengan Ga

Percobaan

Jumlah Pusat Cluster

1

Hasil Total Cost K-Prototype Tanpa GA

Hasil Total Cost K-Means

Total Populasi

Generasi Max

Hasil Total Cost

4

30

5

2640.16

2643.02

9579.46

2

4

30

5

2632.84

2683.59

9579.46

3

4

30

5

2632.84

2645.61

10551.5

4

4

30

5

2623.25

2655.65

9579.46

5

4

30

5

2623.25

2683.59

9579.46

Hasil yang diperoleh pada Tabel 4.1 dapat ditabulasikan dalam bentuk diagram batang, seperti yang terlihat pada Gambar 4.21. Untuk keperluan perbandingan, visualisasi dalam bentuk diagram batang dapat memperlihatkan perbedaan yang lebih jelas.

109

Hasil Percobaan Cluster K-PROTOTYPE DENGAN GA 9579.46

1

K-Prototype Tanpa GA

9579.46

2

10551.5

3

K-Means

9579.46

4

9579.46

5

Gambar 4.21 Grafik Hasil Perhitungan Total Cost

Hasil pengujian selanjutnya untuk Optimasi K-Prototype dengan GA, KProtoype Tanpa GA, dan K-Means ditunjukkan seperti pada Tabel 4.2. Sebanyak lima percobaan dilakukan untuk melihat perbedaan total cost untuk tiap-tiap metode. Berdasarkan hasil yang ditunjukkan pada Tabel 4.2, diperoleh keterangan bahwa K-Prototype dengan GA menghasilkan total cost terkecil dari pada metode lainnya. Hasil ini dipengaruhi oleh penentuan total populasi dan maksimum generasi. Dalam hal ini, total populasi dan generasi maksimum masing-masing sebesar tigapuluh dan sepuluh.

110

Tabel 4.2 Tabel Percobaan untuk Perhitungan Total Cost K-Prototype dengan Ga Hasil Total Cost

Hasil Total Cost K-Prototype Tanpa GA

Hasil Total Cost K-Means

Percobaan

Jumlah Pusat Cluster

1

5

30

10

2532.5

2606.21

8994.7

2

5

30

10

2518.12

2572.09

8994.7

3

5

30

10

2526.86

2580.32

8946.52

4

5

30

10

2543.01

2590.78

8946.52

5

5

30

10

2538.4

2597.53

8946.52

Total Generasi Populasi Max

Hasil yang diperoleh pada Tabel 4.2 dapat ditabulasikan dalam bentuk diagram batang, seperti yang terlihat pada Gambar 4.22. Untuk keperluan perbandingan, visualisasi dalam bentuk diagram batang dapat memperlihatkan perbedaan yang lebih jelas.

Hasil Percobaan Cluster K-PROTOTYPE DENGAN GA 8994.7

1

8994.7

2

K-Prototype Tanpa GA

K-Means

8946.52

8946.52

8946.52

3

4

5

Gambar 4.22 Grafik Hasil Perhitungan Total Cost

111

Berdasarkan data pada Tabel 4.3, diperoleh keterangan bahwa kenaikan jumlah total populasi dan generasi maksimum akan meningkatkan perbedaan hasil total cost untuk k-prototype dengan GA. Perbedaan ini terlihat jelas ketika data pada Tabel 4.2 dan Tabel 4.3 dibandingkan satu sama lain. Pada Tabel 4.3, perbandingan total cost antara k-prototype dengan GA, k-prototype tanpa GA dan k-means terpaut lebih besar ketika total populasi dan generasi maksimum ditingkatkan. Tabel 4.3 Tabel Percobaan untuk Perhitungan Total Cost K-Prototype dengan Ga Percobaan

Jumlah Pusat Cluster

1

Hasil Total Cost K-Prototype Tanpa GA

Hasil Total Cost K-Means

Total Populasi

Generasi Max

Hasil Total Cost

4

80

40

2621.53

2706.39

9579.46

2

4

80

40

2621.53

2664.31

9579.46

3

4

80

40

2621.53

2683.59

9579.46

4

4

80

40

2621.53

2683.59

9579.46

Hasil yang diperoleh pada Tabel 4.3 dapat ditabulasikan dalam bentuk diagram batang, seperti yang terlihat pada Gambar 4.23. Untuk keperluan perbandingan, visualisasi dalam bentuk diagram batang dapat memperlihatkan perbedaan yang lebih jelas. Perbedaan ini terlihat jelas ketika Gambar 4.22 dan Gambar 4.23 dibandingkan.

112

Hasil Percobaan Cluster K-PROTOTYPE DENGAN GA 9579.46

1

K-Prototype Tanpa GA

9579.46

2

K-Means

9579.46

3

9579.46

4

Gambar 4.23 Hasil Grafik Perhitungan Total Cost

4.2.6

Antarmuka Aplikasi Deskripsi

Gambar 4.24 Tampilan Aplikasi Deskripsi

113

Tampilan aplikasi deskripsi pada Gambar 4.24 merupakan tahapan lanjutan dari tampilan aplikasi clustering, yang akan digunakan untuk menampilkan rekap nilai per cluster yang ada. Adapun penjabaran dari Gambar 4.24 yaitu:

1. Load Hasil Segmentasi Proses untuk memanggil data hasil segmentasi yang sudah disimpan sebelumnya pada tahapan clustering dalam format *.mat. Pemanggilan data yang diload dapat dilihat pada Gambar 4.25.

Gambar 4.25 Load Data Data yang telah dipilih akan ditampilkan dalam bentuk grid, dimana data yang dipilih terdiri dari attribut data, hasil cluster. Hasil load data dapat ditampilkan pada Gambar 4.25.

114

Gambar 4.26 Hasil Load Data

1. Threshold Rekap Digunakan untuk mengisi nilai threshold minimal yang akan dimunculkan pada pada Rekap Nilai Per Cluster. Nilai yang bisa diisikan pada threshold rekap mulai dari 0 sampai 1. 2. Rekap Nilai Per Cluster. Proses rekap nilai per cluster akan muncul jika sudah menentukan “Threshold Rekap” dan memilih tombol “Proses Rekap”, maka akan muncul hasil seperti pada Gambar 4.24. Pada hasil yang ditampilkan pada rekap nilai terdapat 5 kolom yaitu : a) Kolom Cluster ke-

: Menunjukkan cluster mana saja yang dipilih.

b) Kolom Total Element : Jumlah data yang ada per cluster c) Kolom Variabel ke-

: Variabel keberapa yang muncul sebagai nilai dominan.

d) Kolom Nilai

: Nilai yang dominan atau sering muncul pada masing-masing variabel.

e)

Kolom Jumlah

: Jumlah kemunculan nilai per variabel per cluster.

115

3. Simpan Rekap Langkah terakhir pilih simpan rekap untuk menyimpan hasil rekap nilai per cluster, dengan bentuk data *.mat.

Gambar 4.27 Hasil Rekap Nilai Per Cluster

Pada Gambar 4.27 terlihat 4 cluster yang terbentuk dengan threshold 0,5. Dengan data uji menggunakan German Credit Dataset, untuk penjelasan masingmasing cluster yang terbentuk yaitu: 1. Cluster ke-2: cluster yang dipilih adalah cluster 2 dengan total elemen sebanyak 223, dengan variabel ke-3 yang muncul sebagai nilai dominan. Pada varibel ke-3 tersebut, nilai dominan yang muncul adalah 3 dengan total kemunculan sebanyak 138. Artinya, pada cluster ke-2 memiliki ciri-ciri: 138 customer masih memiliki kredit yang sedang dibayar.

116

2. Cluster ke-3: cluster yang dipilih adalah cluster 3, dengan total elemen sebanyak 307, dengan variabel ke-1 yang muncul sebagai nilai dominan. Pada varibel ke-1 itu, nilai dominan yang muncul adalah 2 dengan total kemunculan sebanyak 160. Artinya, pada cluster ke-2 memiliki ciri-ciri: 160 Status rekening giro yang ada adalah 0 <= ... < 200 DM (Deutsche Mark) 3. Cluster ke-3: cluster yang dipilih adalah cluster 3, dengan total elemen sebanyak 307, dengan variabel ke-3 yang muncul sebagai nilai dominan. Pada variabel ke-3 nilai dominan yang muncul adalah 3 dengan total kemunculan sebanyak 215. Artinya, pada cluster ke-2 memiliki ciri-ciri: 215 customer

masih

memiliki kredit yang sedang dibayar. 4. Cluster Ke-4: cluster yang dipilih adalah cluster 4, dengan total elemen sebanyak 144, dengan variabel ke-3 yang muncul sebagai nilai dominan. Pada varibel ke-3 nilai dominan yang muncul adalah 3 dengan total kemunculan sebanyak 93. Artinya, pada cluster ke-2 memiliki ciri-ciri: 93 customer masih memiliki kredit yang sedang dibayar.

117

Pada tahapan dekripsi digunakan untuk memunculkan nilai-nilai dominan yang akan menjadi ciri-ciri dari masing-masing kelompok atau segment, sehingga informasi ini nantinya akan dapat digunakan dalam pengambilan keputusan. Tampilan aplikasi deskripsi pada Gambar 4.28 menggunakan jumlah cluster sebanyak 5.

Gambar 4.28 Hasil Rekap Nilai Per Cluster Pada Gambar 4.28, menampilkan load hasil segmentasi yang diolah pada proses sebelumnya, kemudian dilanjutkan ke threshold rekap untuk menampilan batas minimal nilai yang dominan, dan proses terakhir adalah proses rekap yang akan menampiklan cluster mana yang dominan sesuai dengan nilai threshold. Rekapitulasi hasil cluster threshold 0.5 memperlihatkan ciri atau karakteristik yang ada pada setiap cluster, memberikan ciri-ciri setiap kelompok sebagai berikut:

118

1. Cluster ke-3: cluster yang dipilih adalah cluster 3 dengan total elemen sebanyak 271, dengan variabel ke-3 yang muncul sebagai nilai dominan. Pada varibel ke-3 tersebut, nilai dominan yang muncul adalah 5 dengan total kemunculan sebanyak 164. Artinya, pada cluster ke-3 memiliki ciri-ciri: 164 critical account/ memiliki kredit lain namun bukan di bank tersebut. 2. Cluster ke-4: cluster yang dipilih adalah cluster 4 dengan total elemen sebanyak 158, dengan variabel ke-1 yang muncul sebagai nilai dominan. Pada varibel ke-1 tersebut, nilai dominan yang muncul adalah 1 dengan total kemunculan sebanyak 86. Artinya, pada cluster ke-4 memiliki ciri-ciri: 86 Status rekening giro yang ada adalah ..< 0 DM (Deutsche Mark) 3. Cluster ke-4: cluster yang dipilih adalah cluster 4 dengan total elemen sebanyak 158, dengan variabel ke-3 yang muncul sebagai nilai dominan. Pada varibel ke-3 tersebut, nilai dominan yang muncul adalah 3 dengan total kemunculan sebanyak 92. Artinya, pada cluster ke-4 memiliki ciri-ciri: 92 customer

masih

memiliki kredit yang sedang dibayar. 4. Cluster ke-5: cluster yang dipilih adalah cluster 5 dengan total elemen sebanyak 236, dengan variabel ke-1 yang muncul sebagai nilai dominan. Pada varibel ke-1 tersebut, nilai dominan yang muncul adalah 2 dengan total kemunculan sebanyak 146.

119

Artinya, pada cluster ke-5 memiliki ciri-ciri: 146 Status rekening giro yang ada adalah 0 <= ... < 200 DM (Deutsche Mark). 5. Cluster ke-5: cluster yang dipilih adalah cluster 5 dengan total elemen sebanyak 236, dengan variabel ke-3 yang muncul sebagai nilai dominan. Pada varibel ke-3 tersebut, nilai dominan yang muncul adalah 3 dengan total kemunculan sebanyak 146. Artinya, pada cluster ke-5 memiliki ciri-ciri: 146 customer memiliki kredit yang sedang dibayar.

masih

BAB V KESIMPULAN DAN SARAN

5.1

Kesimpulan Berdasarkan hasil uji coba yang telah dilakukan dapat diambil beberapa

kesimpulan sebagai berikut: 1.

Pada penelitian ini, penggabungan metode Clutering K-Prototype dengan Algoritma Genetika dilakukan sebelum fase Evaluasi Fitness. Hal ini berbeda dengan proses Algoritma Genetika pada umumnya, karena setelah proses inisialisasi awal akan langsung dilanjutkan ke fase evaluasi fitness tanpa melalui proses clustering. Proses penggabungan metode ini untuk menghasilkan pengelompokan data yang lebih baik dan memiliki kesamaan ciri atau karakteristik didalam suatu cluster.

2.

Metode gabungan K-Prototype dengan Algortima Genetika yang diusulkan dalam penelitian ini menghasilkan optimasi pusat cluster dengan hasil yang lebih baik daripada K-Prototype tanpa GA, ataupun K-Means. Hal ini terlihat dari hasil percobaan yang telah dilakukan, dimana pada saat dilakukan pengujian menggunakan total cost atau total jarak metode K-Prototype dengan GA menghasilkan nilai total cost terendah yaitu sebesar 2621,53 kemudian metode K-Prototype tanpa GA menghasilkan nilai total cost sebesar 2706,39 dan Metode K-Means menghasilkan nilai total cost sebesar 9579,46. Oleh karena itu, K-Prototype dengan GA memiliki tingkat kesamaan ciri atau karakteristik dari setiap kelompok yang terbentuk lebih baik. 120

121

5.2

Saran Penelitian ini memanfaatkan metode k-prototype dengan GA sebagai metode utama dalam proses clustering. Perlu dilakukan uji coba menggunakan

metode

lainnya

sebagai

pembanding

sehingga

memungkinkan mendapatkan tingkat optimasi yang lebih baik. Untuk penelitian selanjutnya, penulis menyarankan penggunaan metode optimasi yang berbeda dan metode clustering yang berbeda.

DAFTAR PUSTAKA

Bashar Al-Shboul, and Sung-Hyon Myaeng. (2009), Initializing K-Means using Genetic Algorithms, World Academy of Science, Engineering and Technology 54 Chittu.V,N.Sumathi. (2011), A Modified Genetic Algorithm Initializing K-Means Clustering, Global Journal of Computer Science and Technology Volume 11. Duc-Truong Pham, Maria M. Suarez-Alvarez and Yuriy I. Prostov, (2011). Random search with K-Prototype Algorithm for clustering mixed datasets, Proceedings Thes Royal Of Society. Gen, M. and Cheng, R., (2000). Genetic Algorithms and Engineering Optimization, John Wiley & Sons, New York. H., Rahila, Raghuwanshi, M. dan Jaisawal, N.

Genetic Algorithm Based

Clustering. International Journal of Information System. 16 Juli 2008. H.S Behera, Rosly Boy Lingdoh, Diptendra Kodamasingh. (2011), An Improved Hybridized K-Means Clustering Algorithm (IHKMCA) for Highdimensional Dasaset & It’s Performance Analysis, International Journal on Computer Science and Engineering (IJCSE), ISSN: 0975-3397, Vol.3, No.3. Hwei-JenLin, Fu-WenYang and Yang-TaKao. (2005), An Efficient GA based Clustering Technique, Tamkang Journal of Science and Engineering, Vol.8, No2, pp.113-122 K.Arun Prabha, R.Saranya. (2011), Refinement of K-Means Clustering Using Genetic Algorithm, Journal of Computer Applications (JCA), Volume IV, Issue 2. K.KrishnaandM.NarasimhaMurty, (1999). Genetic K-Means Algorithm, IEEE Transaction System, Man, and Cybernetics-Partb: Cybernetics, Vol.29, No.3.

122

123

Kohei Arai and Ali Ridho Barakbah, (2007). Hierarchical K-means: an algorithm for centroids initialization for K-means, Reports of the Faculty of Science and Engineering, Saga University, Vol. 36, No.1. Kyoung-jae Kim, Hyunchul Ahn. (2008). A recommender system using GA Kmeans clustering in an online shopping market. Expert Systems with Applications 34. 1200–1209. M. V. Jagannatha Reddy and B. Kavitha, (2012). Clustering the Mixed Numerical and Categorical Dataset using Similarity Weight and Filter Method, International Journal of Database Theory and Application Vol. 5, No. 1. Min Feng , Zhenyan Wang. (2011), A Genetic K-means Clustering Algorithm Based on the Optimized Initial Centers, Computer and Information Science, Vol. 4, No. 3. Ming-Yi Shih, Jar-Wen Jheng and Lien-Fu Lai. (2010), A Two-Step Method for Clustering Mixed Categroical and Numeric Data, Tamkang Journal of Science and Engineering, Vol.13, No.1, pp.11-19 Zhexue Huang. (1998), Extensions to the K-Means Algorithm for Clustering Large Data Sets with Categorical Values, Data Mining and Knowledge Discovery 2, 283–304. Zhexue Huang. Clustering Large Data Sets With Mixed Numeric and Categorical, CSIRO Mathematical and Information Sciences.