taW ;/--n
TUGAS AKHIR – KI141502
IMPLEMENTASI PARTICLE SWARM OPTIMIZATION LEVY FLIGHT UNTUK INISIALISASI PUSAT CLUSTER PADA K-MEANS UNTUK PENGELOMPOKAN DATA MUHAMMAD FARIS MAKARIM NRP 5112100154 Dosen Pembimbing I Dr.Eng. Chastine Fatichah, S.Kom, M.Kom Dosen Pembimbing II Bilqis Amaliah, S.Kom., M.Kom JURUSAN TEKNIK INFORMATIKA Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya 2017
i
TUGAS AKHIR – KI141502
IMPLEMENTASI PARTICLE SWARM OPTIMIZATION LEVY FLIGHT UNTUK INISIALISASI PUSAT CLUSTER PADA K-MEANS UNTUK PENGELOMPOKAN DATA MUHAMMAD FARIS MAKARIM NRP 5112100154 Dosen Pembimbing I Dr.Eng. Chastine Fatichah, S.Kom, M.Kom Dosen Pembimbing II Bilqis Amaliah, S.Kom., M.Kom JURUSAN TEKNIK INFORMATIKA Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya 2017
i
[Halaman ini sengaja dikosongkan]
ii
UNDERGRADUATE THESES – KI141502
PARTICLE SWARM OPTIMIZATION LEVY FLIGHT IMPLEMENTATION FOR CENTER CLUSTER ON KMEANS FOR DATA CLUSTERING MUHAMMAD FARIS MAKARIM NRP 5112100154 Supervisor I Dr.Eng. Chastine Fatichah, S.Kom, M.Kom Supervisor II Bilqis Amaliah, S.Kom., M.Kom DEPARTMENT OF INFORMATICS FACULTY OF INFORMATION TECHNOLOGY INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 2017
iii
[Halaman ini sengaja dikosongkan]
iv
LEMBAR PENGESAHAN IMPLEMENTASI PARTICLE SWARM OPTIMIZATION LEVY FLIGHT UNTUK INISIALISASI PUSAT CLUSTER PADA K-MEANS UNTUK PENGELOMPOKAN DATA TUGAS AKHIR Diajukan Untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Komputer pada Bidang Studi Komputasi Cerdas dan Visualisasi Program Studi S-1 Jurusan Teknik Informatika Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Oleh MUHAMMAD FARIS MAKARIM NRP : 5112 100 154
Disetujui oleh Dosen Pembimbing Tugas Akhir: 1. Dr.Eng. Chastine Fatichah, S.Kom, M.Kom ..................... (NIP 197512202001122002) (Pembimbing 1) 2. Bilqis Amaliah, S.Kom., M.Kom (NIP 197509142001122002) SURABAYA JANUARI, 2017
v
..................... (Pembimbing 2)
[Halaman ini sengaja dikosongkan]
vi
Implementasi Particle Swarm Optimization Levy Flight Untuk Inisialisasi Pusat Cluster Pada K-means Untuk Pengelompokan Data Nama Mahasiswa NRP Jurusan Dosen Pembimbing 1 Dosen Pembimbing 2
: : : :
MUHAMMAD FARIS MAKARIM 5112100154 Teknik Informatika FTIF-ITS Dr.Eng. Chastine Fatichah, S.Kom, M.Kom : Bilqis Amaliah, S.Kom., M.Kom
Abstrak Pengelompokan data dapat mempermudah pengolahan, penggunaan dan pemilihan data secara optimal. Pengaplikasian pengelompokan data dapat dilakukan di berbagai bidang, diantaranya adalah segmentasi pasar, pengelompokan data pada search engine dan segmentasi citra pada citra. Oleh karena itu diperlukan suatu sistem yang dapat mengelompokkan data sehingga data tersebut dapat digunakan dengan lebih tepat guna. Tugas Akhir ini mengimplementasikan algoritma particle swarm optimization levy flight untuk melakukan inisialisasi centroid awal untuk optimasi k-means. Pada algoritma k-means konvensional digunakan penentuan centroid awal secara random mengakibatkan hasil pengelompokan belum optimal. Oleh karena itu particle swarm optimization levy flight diharapkan sebagai optimasi centroid awal tersebut. Dataset yang digunakan dalam proses uji coba ada tiga macam data yaitu data yeast, ecoli dan iris. Pada hasil pengujian metode particle swarm optimization levy flight kmeans, telah dihasilkan iterasi yang lebih sedikit dibandingkan dengan k-means. Nilai SSE yang dihasilkan pada data yeast di jumlah cluster sepuluh adalah 17,293. Nilai SSE yang dihasilkan pada data ecoli di jumlah cluster delapan adalah
vii
8,078. Nilai SSE yang dihasilkan pada data iris di jumlah cluster tiga adalah 9.866. Kata Kunci: Particle Swarm Optimization, Levy Flight, Kmeans, Pengelompokan Data.
viii
PARTICLE SWARM OPTIMIZATION LEVY FLIGHT IMPLEMENTATION FOR CENTER CLUSTER ON KMEANS FOR DATA CLUSTERING Student’s Name Student’s ID Department First Advisor Second Advisor
: : : :
MUHAMMAD FARIS MAKARIM 5112100154 Teknik Informatika FTIF-ITS Dr.Eng. Chastine Fatichah, S.Kom, M.Kom : Bilqis Amaliah, S.Kom., M.Kom
Abstract Clustering data could ease data processing, utilization, or selection optimally. The data clustering could be used in many place, including market segmentaion, clustering data on search engine and imagery segmentation on image. Therefore a system that could clustering much data is needed, so the data can be used in an appropriate way. This final project is implementing particle swarm optimization levy flight algorithm for initiate the first centroid for k-means optimization. In k-means algorithm, it use a random value for initial state. The too random value could generate a bad result. The result from clustering software is implemented. The results from particle swarm optimization levy flight will be used for that initial state. The dataset used in the testing process contains three kinds of data. The data is including yeast, ecoli and iris data. On the result particle swarm optimization levy flight k-means test, it produced fewer iteration on comparison with k-means. The SSE value result for yeast data on the ten numbers of cluster is 17.293. The SSE value result for ecoli data on the eight numbers of cluster is 8.078. The SSE value result for iris data on the three numbers of cluster is 9.866.
ix
Keywords: Particle Swarm Optimization, Levy Flight, Kmeans, Data Clustering.
x
KATA PENGANTAR
Puji syukur penulis kehadirat Allah SWT karena berkat rahmat dan karunia-NYA penulis dapat menyelesaikan Tugas Akhir yang berjudul IMPLEMENTASI PARTICLE SWARM OPTIMIZATION LEVY FLIGHT UNTUK INISIALISASI PUSAT CLUSTER PADA K-MEANS UNTUK PENGELOMPOKAN DATA Tugas Akhir ini merupakan salah satu syarat untuk memperoleh gelar Sarjana Komputer di Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember Surabaya. Penulis ingin menyampaikan terima kasih yang sebesar-besarnya atas dukungan dan semangat yang diberikan dan membantu penulis baik secara langsung ataupun tidak dalam menyelesaikan Tugas Akhir ini. Penulis ingin mengucapkan terima kasih kepada 1. Allah SWT karena berkat rahmat dan karunianya penulis berhasil menyelesaikan Tugas Akhir dengan baik. 2. Kedua orang tua, dan keluarga penulis, terima kasih atas doa dan bantuan moral dan material selama penulis belajar di Teknik Informatika ITS. 3. Bapak Dr. Darlis Herumurti, S.Kom., M.Kom., selaku ketua jurusan Teknik Informatika ITS 4. Bapak Radityo Anggoro, S.Kom., M.Sc. selaku Koordinator Tugas Akhir di Teknik Informatika ITS. 5. Ibu Dr.Eng. Chastine Fatichah, S.Kom, M.Kom selaku Dosen Pembimbing I Tugas Akhir yang telah memberikan bimbingan dan dukungan selama penulis menyelesaikan Tugas Akhir.
xi
6. Ibu Bilqis Amaliah, S.Kom., M.Kom selaku pembimbing II Tugas Akhir yang telah memberikan banyak waktu untuk berdiskusi dan memberi semangat dan motivasi kepada penulis untuk menyelesaikan Tugas Akhir. 7. Bapak dan Ibu Dosen di Jurusan Teknik Informatika yang telah memberikan ilmu selama penulis kuliah di Teknik Informatika 8. Seluruh Staf dan karyawan Teknik Informatika yang telah memberikan bantuan selama penulis kuliah di Teknik Informatika. Penulis Mohon maaf apabila terdapat kekurangan dalam penulisan Tugas Akhir ini. Kritik dan saran penulis harapkan untuk perbaikan dan pembelajaran di kemudian hari. Semoga Tugas Akhir ini dapat memberikan Manfaat yang sebesar besarnya. Surabaya, Januari 2017 Penulis
xii
DAFTAR ISI LEMBAR PENGESAHAN..................................................... v Abstrak .................................................................................. vii Abstract .................................................................................. ix KATA PENGANTAR ........................................................... xi DAFTAR ISI ........................................................................ xiii DAFTAR GAMBAR ............................................................ xv DAFTAR TABEL ............................................................... xvii DAFTAR KODE SUMBER ................................................ xix BAB I PENDAHULUAN ....................................................... 1 1.1 Latar Belakang ................................................................... 1 1.2 Rumusan Masalah .............................................................. 2 1.3 Batasan Masalah................................................................. 3 1.4 Tujuan ................................................................................ 3 1.5 Manfaat .............................................................................. 3 1.6 Metodologi ......................................................................... 3 BAB II TINJAUAN PUSTAKA ............................................. 5 2.1 Particle Swarm Optimization ............................................. 5 2.2 Levy Flight ......................................................................... 7 2.3 Particle Swarm Optimization Levy Flight.......................... 8 2.4 K-means ........................................................................... 10 BAB III DESAIN PERANGKAT LUNAK .......................... 13 3.1 Deskripsi Dataset ............................................................. 13 3.2 Desain Sistem Secara Umum ........................................... 15 3.3 Particle Swarm Optimization Levy Flight Optimasi Centroid .......................................................................... 16 3.3.1 Inisiasi Parameter dan Populasi..................................... 17 3.3.2 Pembuatan Partikel........................................................ 18 3.3.3 Pengecekan Pbest .......................................................... 18 3.3.4 Pengecekan Gbest ......................................................... 18 3.4 PSOLF K-means .............................................................. 19 3.4.1 Inisialisasi Parameter..................................................... 20 3.4.2 Pengelompokan Data..................................................... 20 3.4.3 Update Centroid ............................................................ 20
xiii
BAB IV IMPLEMENTASI ................................................... 21 4.1 Lingkungan Implementasi ................................................ 21 4.2 Implementasi .................................................................... 21 4.2.1 Implementasi Tahap Inisialisasi Awal ........................... 22 4.2.2 Implementasi Tahap Inisialisasi Random pada Partikel Awal........................................................................... 22 4.2.3 Implementasi Tahap Konversi Data .............................. 23 4.2.4 Implementasi Particle Swarm Optimization Levy Flight.......................................................................... 24 4.2.5 Implementasi K-means .................................................. 28 4.2.6 Tahap Pemunculuan Nilai Keluaran .............................. 30 BAB V UJI COBA DAN EVALUASI.................................. 33 5.1 Lingkungan Uji Coba ....................................................... 33 5.2 Data Uji Coba ................................................................... 33 5.3 Alur Uji Coba ................................................................... 33 5.3.1 Input............................................................................... 34 5.3.2 Output ............................................................................ 34 5.4 Skenario Uji Coba ............................................................ 36 5.4.1 Skenario Uji Coba Data Yeast ....................................... 36 5.4.2 Skenario Uji Coba Data Ecoli ....................................... 41 5.4.3 Skenario Uji Coba Data Iris........................................... 44 5.5 Analisis Uji Coba K-means dan PSOLF K-means ........... 47 BAB VI KESIMPULAN DAN SARAN ............................... 49 6.1 Kesimpulan ....................................................................... 49 6.2 Saran ................................................................................. 49 DAFTAR PUSTAKA ............................................................ 51 BIODATA PENULIS ............................................................ liii
xiv
DAFTAR GAMBAR Gambar 2.1 Ilustrasi Particle Swarm Optimization ................. 6 Gambar 2.2 Perubahan Data Setelah Proses K-means ........... 10 Gambar 3.1 Diagram Alir Sistem ........................................... 16 Gambar 3.2 Digram Alir Particle Swarm Optimization Levy Flight Optimasi Centroid ....................................................... 17 Gambar 3.3 Diagram Alir PSOLF K-means .......................... 19 Gambar 5.1 Contoh Proses Input ........................................... 34 Gambar 5.2 Contoh Proses Output ......................................... 35 Gambar 5.3 Grafik Yeast Cluster terhadap SSE .................... 40 Gambar 5.4 Grafik Ecoli Cluster terhadap SSE ..................... 44 Gambar 5.5 Grafik Iris Cluster terhadap SSE ........................ 47
xv
[Halaman ini sengaja dikosongkan]
xvi
DAFTAR TABEL Tabel 3.1 Deskripsi Dataset ................................................... 13 Tabel 3.2 Atribut Data Yeast.................................................. 14 Tabel 3.3 Atribut Data Ecoli .................................................. 14 Tabel 3.4 Atribut Data Iris ..................................................... 15 Tabel 4.1 Lingkungan Perancangan Perangkat Lunak ........... 21 Tabel 5.1 Hasil Data Yeast K-means ..................................... 36 Tabel 5.2 Hasil Data Yeast PSOLF K-means ........................ 38 Tabel 5.3 Hasil Data Ecoli K-means ...................................... 41 Tabel 5.4 Hasil Data Ecoli PSOLF K-means ......................... 42 Tabel 5.5 Hasil Data Iris K-means ......................................... 45 Tabel 5.6 Hasil Data Iris PSOLF K-means ............................ 45 Tabel 5.7 Hasil Rata-Rata K-means dan PSOLF K-means… 48
xvii
[Halaman ini sengaja dikosongkan]
xviii
DAFTAR KODE SUMBER Kode Sumber 4.1 Implementasi Tahap Inisialisasi Awal ...... 22 Kode Sumber 4.2 Inisialisasi Nilai Random Awal Partikel ... 23 Kode Sumber 4.3 Implementasi Konversi Data ..................... 24 Kode Sumber 4.4 Implementasi pembuatan partikel ............. 25 Kode Sumber 4.5 Implementasi Pengelompokan Data dan Pengecekan pbest ................................................................... 26 Kode Sumber 4.6 Memperbarui Pbest dan Gbest .................. 27 Kode Sumber 4.7 Inisialisasi Jumlah Iterasi dan Cluster Baru ................................................................................................ 28 Kode Sumber 4.8 Mendapatkan Kelompok Data ................... 29 Kode Sumber 4.9 Memperbarui Cluster dan Centroid Baru.. 30 Kode Sumber 4.10 Tahap Pemunculan Nilai Keluaran ......... 31
xix
[Halaman ini sengaja dikosongkan]
xx
BAB I PENDAHULUAN Pada bab ini dibahas mengenai latar belakang, rumusan masalah, batasan masalah, tujuan, manfaat, metodologi, dan sistematika laporan tugas akhir. Diharapkan dari penjelasan dalam bab ini gambaran Tugas Akhir secara umum dapat dipahami. 1.1 Latar Belakang Clustering merupakan suatu proses pengelompokan data ke dalam kelas-kelas atau cluster-cluster berdasarkan suatu kemiripan atribut – atribut diantara kelompok data tersebut. Clustering merupakan fungsionalitas pada data mining. Tujuan dari proses clustering yaitu untuk mengelompokkan data ke dalam suatu cluster, sehingga objek pada suatu cluster memiliki kemiripan yang sangat besar dengan objek lain pada cluster yang sama, tetapi sangat tidak mirip dengan objek pada cluster yang lain. Salah satu ciri clustering yang baik atau optimal adalah jika menghasilkan cluster yang berisi data dengan tingkat kemiripan (similarity) yang tinggi pada cluster yang sama dan tingkat kemiripan rendah pada cluster yang berbeda. Dengan adanya clustering akan sangat memudahkan pengelompokan-pengelompokan dokumen. K-means adalah salah satu metode clustering yang sering digunakan dalam pengelompokan data. K-means merupakan suatu metode yang membagi sekumpulan data atau objek ke dalam k kelompok sehingga anggota yang berada pada kelompok yang sama memiliki karateristik yang sama dan memiliki perbedaan karakteristik dengan anggota yang berada pada kelompok lain. Metode ini dapat menghasilkan cluster atau kelompok dengan proses yang cepat dan dinilai cukup efisien yang ditunjukkan dengan kompleksitasnya [1].
1
2 Kelemahan pada algoritma ini adalah inisialisasi cluster awal yang random sehingga dapat meningkatkan tingkat error Particle Swarm Optimization adalah algoritma berbasis kecerdasan buatan yang digunakan untuk menyelesaikan persoalan optimasi. Algoritma ini terinspirasi dari perilaku sosial kolektif dari kecerdasan koloni binatang, seperti burung dan ikan. Algoritma ini sudah semakin berkembang dan sering digunakan oleh para ahli. Particle Swarm Optimization sudah sering dikembangkan dan memiliki banyak versi baru. Levy flight merupakan suatu algoritma yang sering digunakan untuk mencari nilai optimal dari suatu nilai random. Dari masalah yang ada, tujuan dari usulan tugas akhir ini yaitu, mengimplementasikan particle swarm optimization levy flight untuk inisialisasi pusat cluster pada k-means untuk pengelompokan data. Data uji yang akan digunakan adalah beberapa dataset UCI machine learning. Dalam prosesnya, aplikasi ini akan mengeluarkan hasil centroid-centroid yang menentukan ciri setiap cluster dan hasil pengelompokan data. 1.2 Rumusan Masalah Rumusan masalah yang diangkat dalam tugas akhir dapat dipaparkan sebagai berikut. a) Bagaimana melakukan implementasi Particle Swarm Optimization menggunakan Levy Flight? b) Bagaimana melakukan penggabungan antara metode Particle Swarm Optimization Levy Flight dan Algoritma K-means? c) Bagaimana melakukan pengukuran performa kinerja Particle Swarm Optimization Levy Flight-K-means pada beberapa dataset?
3 1.3 Batasan Masalah Permasalahan yang dibahas dalam tugas akhir memiliki beberapa batasan, yakni sebagai berikut. 1. Implementasi menggunakan bahasa pemrograman Python. 2. Data yang digunakan adalah data UCI machine learning dengan format bilangan integer atau bilangan real. 1.4 Tujuan Tujuan dari pembuatan tugas akhir ini adalah menggunakan k-means dengan particle swarm optimization levy flight sebagai inisialisasi pusat cluster pengelompokan data. 1.5 Manfaat Pengerjaan tugas akhir ini dilakukan dengan harapan bisa mempermudah pembagian data pada dokumen dan menurunkan tingkat error pada pengelompokan data. 1.6 Metodologi Metodologi yang dipakai pada pengerjaan Tugas Akhir ini adalah sebagai berikut: 1. Penyusunan Proposal Tugas Akhir Tahap awal yang dilakukan dalam pengerjaan Tugas Akhir ini adalah penyusunan proposal Tugas Akhir. Di dalam proposal diajukan suatu gagasan pembuatan perangkat lunak untuk melakukan optimasi pada k-means clustering. 2. Studi Literatur Pada tahap ini dilakukan pencarian, pengumpulan, penyaringan, pemahaman, dan pembelajaran literatur yang berhubungan dengan particle swarm optimization, levy flight, dan k-means. Literatur yang digunakan meliputi: jurnal, dan dokumentasi internet.
4 3. Implementasi dan pembuatan perangkat lunak Pada tahap ini dilakukan impelementasi perangkat lunak sesuai dengan rancangan perangkat lunak yang dibuat. 4. Uji coba dan Evaluasi Pada tahap ini dilakukan uji coba terhadap perangkat lunak yang telah dibuat untuk mengetahui kemampuan algoritma yang dipakai, mengamati kinerja sistem, serta mengidentifikasi kendala yang mungkin timbul. Parameter yang diujicobakan adalah parameter input pada nilai acak k-means, iterasi pada k-means, dan hasil data pada tiap kelompok data. 5. Penyusunan Laporan Tugas Akhir Pada tahap ini dilakukan penyusunan laporan pengerjaan Tugas Akhir yang berisi dasar teori, dokumentasi dari perangkat lunak, dan hasil yang diperoleh selama pengerjaan Tugas Akhir.
BAB II TINJAUAN PUSTAKA Pada bab ini dibahas mengenai teori-teori yang menjadi dasar dari pembuatan Tugas Akhir. 2.1 Particle Swarm Optimization Particle Swarm Optimization (PSO) adalah algoritma berbasis kecerdasan buatan(Artificial Intelligence) yang digunakan untuk menyelesaikan persoalan optimasi yang berkelanjutan. Pada PSO ada beberapa set partikel yang digunakan untuk mencari solusi terbaik yang diberikan pada permasalahan optimasi yang berkelanjutan. Setiap partikel memiliki solusi dari setiap masalah dan tiap partikel selalu memiliki 2 variabel yaitu posisi dan kecepatan yang masing-masing bertipe data multi dimensi sebanyak permasalahan yang ada. Setiap partikel memiliki partikel terbaiknya pada tiap pengalamannya (pbest) dan pada keseluruhan partikel memiliki pengalaman terbaik (gbest). Untuk memperbarui pengalaman pada partikel diperlukan algoritma pada kecepatan dan posisi yang baru. algoritma tersebut adalah sebagai berikut : 𝑉𝑖𝑟 + 1 = 𝑤 . 𝑉𝑖𝑟 + 𝑐1 . 𝑟𝑎𝑛𝑑 . (𝑃𝑏𝑒𝑠𝑡𝑖𝑟 − 𝑋𝑖𝑟) + 𝑐2 . 𝑟𝑎𝑛𝑑 . (𝐺𝑏𝑒𝑠𝑡𝑖𝑟 − 𝑋𝑖𝑟)
Xir+1 = Xir + Vir+1 wit = wmax -
(𝑤𝑚𝑎𝑥−𝑤𝑚𝑖𝑛)∗𝐼𝑡 𝑖𝑡𝑚𝑎𝑥
Keterangan: Xir Vir
: Posisi kecepatan partikel saat ini : Kecepatan partikel saat ini
5
(2.1)
(2.2) (2.3)
6 Xir+1 : Posisi partikel iterasi selanjutnya Vir+1 : Posisi dan kecepatan partikel iterasi selanjutnya c1 : Konstanta cognitive c2 : Konstanta social acceleration rand : Nilai random yang terdistribusi antara 0 dan 1 Pbestir : Posisi terbaik dari partikel itu sendiri Gbestir : Posisi terbaik dari seluruh populasi yang ada wmax : Koefisien inersia weight maksimal wmin : Koefisien inersia weight minimal It : Iterasi yang selalu berubah dari 1,2, … Itmax tmax : Nilai maksimal dari iterasi yang digunakan
Gambar 2.1 Ilustrasi Particle Swarm Optimization Langkah-langkah algoritma Particle Swarm Optimization: 1. Langkah awal dari algoritma ini adalah menentukan populasi yang akan dibuat dan iterasi yang dilakukan. 2. Lakukan random pada nilai awal yang akan dibuat sebagai acuan partikel awal. 3. Buatlah partikel baru yang memiliki kecepatan dan posisi dengan menggunakan rumus (2.1) dan (2.2). 4. Hitung fitness value pada partikel baru tersebut. Bila fitness value tersebut adalah partikel pertama maka jadikan partikel tersebut sebagai pbest. Bila tidak maka bandingkan fitness value partikel tersebut dengan
7 fitness value pada pbest. Bila fitness value pada partikel tersebut lebih baik dari pbest, maka jadikan partikel tersebut sebagai pbest. 5. Bila partikel yang dihasilkan sudah mencapai maksimal populasi maka dilanjutkan pada tahap selanjutnya. Bila tidak maka kembali ke tahap 2. 6. Bila nilai gbest belum ada, maka gunakan nilai pbest sebagai nilai gbest. Bila sudah ada maka bandingkan fitness value pada pbest dengan fitness value pada gbest. Bila fitness value pada pbest lebih baik, maka gunakan pbest tersebut sebagai gbest. 7. Bila iterasi yang dilakukan belum mencapai iterasi terakhir, maka kembali ke tahap 2. Bila sudah mencapai iterasi maksimal maka nilai gbest adalah hasil output dari algoritma ini. 2.2 Levy Flight Merupakan algoritma nature-inspired untuk memecahkan masalah optimasi. Levy flight memiliki 2 langkah: pilih arah random dan generasi pada langkah yang harus diikuti pada distribusi levy. Random walks tergambar dari distribusi standar levy. Distribusi ini adalah power-law formula L(s) ∼ |s|−1−β Dimana 0 < β < 2 adalah sebuah index [2]. Versi simpel dari distribusi levy:
L(s, Ɣ, μ) √
= {
Ɣ Ɣ 1 exp [ ] , 𝑖𝑓 0 < 𝜇 < 𝑠 < ∞ 2𝜋 2𝜋 (𝑠 − 𝜇)32 0,
𝑖𝑓 𝑠 ≤ 0
(2.4)
8 Pada umumnya distribusi levy didefinisikan dengan Fourier transform: 𝐹(𝑘) = exp[−∝ |𝑘|𝛽 ], 0 < 𝛽 ≤ 2
(2.5)
Untuk random walk, langkah panjang S dapat dihitung dengan menggunakan algoritma Mantegna: 𝑆=
𝑢 |𝑣|1/𝛽
(2.6)
Dimana u dan v tergambar dari distribusi normal (2.7)
u~N(0, 𝜎𝑢2 ), v~N(0, 𝜎𝑣2 )
Dimana 𝜋𝛽
𝜎𝑢 = {
𝜏(1 + 𝛽)sin( )
}
(2.8)
step size = 0.01 * S
(2.9)
2
𝜏[1 + 𝛽/2]𝛽2
𝛽−1 ) 2
(
Kemudian Step size dihitung dengan:
2.3 Particle Swarm Optimization Levy Flight Particle Swarm Optimization Levy Flight merupakan metode pengembangan dari Particle Swarm Optimization. Beberapa peneliti meningkatkan performa Particle Swarm Optimization dengan mendesain teknik yang berbeda untuk memperbarui kecepatan. Levy flight merupakan algoritma yang bagus digunakan untuk variabel random[2].
9 Kecepatan dan posisi pada PSOLF: (𝑡) 𝑉𝑖𝑡+1 = 𝜔 . 𝐿𝑒𝑣𝑦𝑤𝑎𝑙𝑘 (𝑋𝑖 ) + 𝑐1 . 𝑟𝑎𝑛𝑑 . (𝑃𝑏𝑒𝑠𝑡𝑖𝑟 − 𝑋𝑖𝑟 ) + 𝑐2 . 𝑟𝑎𝑛𝑑 . (𝐺𝑏𝑒𝑠𝑡𝑖𝑟 − 𝑋𝑖𝑟 )
𝑋𝑖𝑡 = 𝑉𝑖𝑡
(2.10) (2.11)
dimana (𝑡)
(𝑡)
𝐿𝑒𝑣𝑦𝑤𝑎𝑙𝑘 (𝑋𝑖 ) = 𝑋𝑖
+ 𝑠𝑡𝑒𝑝 . 𝑟𝑎𝑛𝑑𝑜𝑚(𝑠𝑖𝑧𝑒(𝑋𝑖 ))
(2.12)
(𝑡)
step = stepsize . 𝑋𝑖
stepsize adalah hasil yang didapat dari rumus(2.9). Optimasi ω pada PSOLF: 𝜔 = 0.1 + 0.8 ∗ (1 − 𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛/𝑀𝑎𝑥𝑖𝑡𝑒𝑟)
(2.13)
Rumus Sum Squared Errors (SSE): 𝑆𝑆𝐸 = ∑Kj=0 ∑𝑥∈𝐶 𝑑(𝑥𝑖 , 𝑐𝑗 )
(2.14)
𝑑(𝑦, 𝑥) = √(x − y)2
(2.15)
Rumus Fitness Function: 𝐹𝐹 = 𝑓1 =
1 1+𝑓1 𝑆𝑆𝐸 𝑁
Keterangan: 𝑉𝑖𝑡+1 : Kecepatan partikel saat ini 𝑉𝑖𝑡 : Kecepatan partikel iterasi selanjutnya 𝑋𝑖𝑡 : Posisi kecepatan partikel saat ini 𝐿𝑒𝑣𝑦𝑤𝑎𝑙𝑘 : Nilai levy flight 𝑐1 : Konstanta cognitive 𝑐2 : Konstanta social acceleration
(2.16) (2.17)
10 𝑟𝑎𝑛𝑑 : Nilai distribusi random antara 0 dan 1 𝑃𝑏𝑒𝑠𝑡𝑖𝑟 : Posisi terbaik dari partikel itu sendiri 𝐺𝑏𝑒𝑠𝑡𝑖𝑟 : Posisi terbaik dari seluruh populasi yang ada 𝑑 : Nilai jarak antara data dan cluster terdekat 𝑆𝑆𝐸 : Nilai seluruh jarak antara data dan cluster terdekat 𝑓1 : Nilai rata-rata seluruh jarak pada data dan cluster terdekat 𝐹𝐹 : Nilai parameter untuk menentukan partikel terbaik 2.4 K-means K-means merupakan suatu metode yang membagi sekumpulan data atau objek ke dalam k kelompok sehingga anggota yang berada pada kelompok yang sama memiliki karateristik yang sama dan memiliki perbedaan karakteristik dengan anggota yang berada pada kelompok lain. Metode ini dapat menghasilkan cluster atau kelompok dengan proses yang cepat dan dinilai cukup efisien yang ditunjukkan dengan kompleksitasnya [1].
Gambar 2.2 Perubahan Data Setelah Proses K-means
11 Langkah-langkah algoritma k-means: 1. Langkah awal dari algoritma ini adalah menentukan berapa jumlah kelompok yang akan dibentuk. 2. Masukkan seluruh data yang akan dikelompokkan. Setiap kelompok akan memiliki ciri-ciri tersendiri. Pada awal akan dimasukkan nilai random pada setiap nilai dari ciri-ciri setiap kelompok. 3. Pada setiap data, bandingkan jaraknya dengan setiap kelompok yang ada. Pada kelompok yang memiliki nilai terkecil akan menjadikan data tersebut termasuk pada kelompok tersebut. 4. Jumlahkan seluruh data yang berada pada masingmasing kelompok dan bagi dengan jumlah data yang ada pada masing-masing kelompok. Nilai tersebut akan digunakan untuk nilai ciri-ciri pada tiap kelompok yang baru. 5. Cek pada tiap kelompok apakah nilai ciri-ciri yang ada pada tiap kelompok berubah. Bila tidak berubah maka proses selesai dan bila berubah maka ulangi proses 3 dan 4.
12 [Halaman ini sengaja dikosongkan]
BAB III DESAIN PERANGKAT LUNAK Pada bab ini dijelaskan mengenai rancangan sistem perangkat lunak yang akan dibuat. Perancangan yang dijelaskan meliputi data dan proses. Data yang dimaksud adalah data yang akan diolah dalam perangkat lunak sehingga tujuan Tugas Akhir ini bisa tercapai. Proses yaitu tahap-tahap yang ada dalam sistem pada nilai acak inisialisasi k-means, iterasi pada kmeans, dan hasil data pada tiap kelompok data. 3.1 Deskripsi Dataset Pada sub bab ini akan dijelaskan mengenai dataset yang digunakan sebagai masukan perangkat lunak untuk diuji. Data tersebut masing-masing memiliki nilai bilangan real, tidak memiliki nilai yang kosong dan setiap centroidnya tidak memiliki selisih nilai yang jauh sehingga tidak diperlukan proses normalisasi pada dataset. Tabel 3.1 Deskripsi Dataset No 1 2 3
Nama Dataset Yeast Ecoli Iris
Jumlah Data 1484 338 150
Jumlah Cluster 10 8 3
Jumlah Atribut 8 7 4
Pada tabel 3.1 dapat dilihat macam dataset, jumlah data, jumlah cluster dan jumlah atribut yang dimiliki pada setiap dataset. Setiap dataset memiliki nilai yang bermacam - macam dan range yang berbeda. Penjelasan tentang atribut setiap masing – masing dataset dapat dilihat pada Tabel 3.2, Tabel 3.3 dan Tabel 3.4.
13
14 Tabel 3.2 Atribut Data Yeast Nama Atribut mcg gvh alm
mit erl pox vac
nuc
Keterangan Metode McGeoch untuk pengenalan sinyal Metode von Heijne untuk pengenalan sinyal Nilai membran ALOM untuk prediksi program Nilai analisis diskriminasi kadar asam amino dari wilayah N-terminal pada protein mitochondrial dan nonmitochondrial Substring keberadaan pada “HDEL” Target sinyal peroxisomal di Cterminus Nilai analisis diskriminasi kadar asam amino dari protein vacuolar dan extracellular Nilai analisis diskriminasi sinyal lokalisasi protein nuklir dan nonnuklir
Type Data
Range Nilai
Real
0.11 - 1.0
Real
0.13 - 1.0
Real
0.21 - 1.0
Real
0.0 - 1.0
Real
0.5 - 1.0
Real
0.0 - 0.83
Real
0.0 - 0.73
Real
0.0 - 0.1
Type Data
Range Nilai
Real
0.0 - 0.89
Real
0.16 - 1.0
Real
0.48 - 1.0
Real
0.5 - 1.0
Tabel 3.3 Atribut Data Ecoli Nama Atribut mcg gvh lip chg
Keterangan Metode McGeoch untuk pengenalan sinyal Metode von Heijne untuk pengenalan sinyal Urutan nilai konsensus pada sinyal peptidase II von Heijne Keberadaan prediksi lipoprotein pada N-terminus
15
aac alm1 alm2
Nilai diskriminasi analisis kadar asam amino pada membran luar dan protein periplasmic Nilai membran ALOM untuk prediksi program Nilai program ALOM setelah memisahkan sinyal yang diduga dapat dibelah dari urutan
Real
0.0 - 0.88
Real
0.03 - 1.0
Real
0.0 - 0.99
Type Data Real Real Real Real
Range Nilai 4.3 - 7.9 2.0 - 4.4 1.0 - 6.9 0.1 - 2.5
Tabel 3.4 Atribut Data Iris Nama Atribut sepall sepalw petall petalw
Keterangan Panjang sepal dalam cm Lebar sepal dalam cm Panjang petal dalam cm Lebar petal dalam cm
3.2 Desain Sistem Secara Umum Desain sistem pengelompokan data Particle Swarm Optimization Levy Flight untuk Inisialisasi Pusat Cluster pada k-means dimulai dengan membaca masukan berupa masukkan yang berisi nama dari data file yang ingin diproses. Proses optimasi k-means terdiri dari dua proses besar, yaitu Particle Swarm Optimization Levy Flight dan k-means. Diagram alir desain umum perangkat lunak ditunjukkan pada Gambar 3.1 Diagram Alir Sistem .
16
Gambar 3.1 Diagram Alir Sistem Setiap data yang ada pada file tersebut yang pertama akan digunakan untuk proses Particle Swarm Optimization Levy Flight dan kemudian digunakan untuk proses k-means yang pada akhirnya akan mengeluarkan data keluaran. Tahap pertama Particle Swarm Optimization Levy Flight adalah mencari nilai random terbaik dengan mengeluarkan beberapa jumlah partikel baru yang akan dibandingkan dengan partikel terbaik. Setelah mengeluarkan partikel terakhir, diharapkan partikel terbaik telah didapatkan dan akan digunakan untuk proses kedua. Setelah melalui tahap Particle Swarm Optimization Levy Flight, hasil dari proses tersebut akan digunakan untuk proses k-means. Pada proses ini akan dilakukan pengelompokan data pada setiap data masukkan. Proses k-means dilakukan berulangulang sampai nilai cluster tidak berubah. Hasil akhir yang dikeluarkan adalah nilai awal dan akhir proses k-means pada fitness function dan cluster serta banyak iterasi yang terjadi. 3.3 Particle Swarm Optimization Levy Flight Optimasi Centroid Pada proses k-means tidak langsung menggunakan nilai acak yang benar-benar acak. Tahap awal yang digunakan adalah Particle Swarm Optimization Levy Flight. Particle Swarm Optimization Levy Flight bertujuan untuk mendapatkan nilai random yang baik sehingga tidak menimbulkan iterasi yang
17 terlalu banyak dan meminimalisir pengelompokan data yang gagal. Particle Swarm Optimization Levy Flight dilakukan melalui lima tahap yaitu initiate parameter and population, generate particle, pbest checking, dan gbest checking. Diagram alir tahap Particle Swarm Optimization Levy Flight Optimasi Centroid ditunjukkan pada Gambar 3.2.
Gambar 3.2 Digram Alir Particle Swarm Optimization Levy Flight Optimasi Centroid 3.3.1 Inisiasi Parameter dan Populasi Tahap inisiasi parameter dan populasi adalah tahap dimana program menentukan berapa jumlah atribut yang dimiliki data, berapa jumlah cluster yang kan dibentuk dan berapa populasi yang akan dibuat untuk dibandingkan yang mana yang terbaik.
18 3.3.2 Pembuatan Partikel Didalam proses ini dilakukan proses pembuatan partikel. Metode pembuatan partikel yang dilakukan pada proses ini akan digunakan rumus mencari kecepatan(2.10) dan posisi(2.11). Namun khusus untuk partikel pertama akan digunakan nilai random karena kedua rumus tersebut membutuhkan nilai sebelumnya yang pada keadaan partikel pertama belum dimiliki. Setelah mendapatkan nilai partikel, nilai tersebut disimpan untuk diproses pada tahap berikutnya yakni pengecekan pbest. 3.3.3 Pengecekan Pbest Pada tahap ini dilakukan perhitungan pada seluruh data yang ada dan akan dikelompokkan data tesebut dengan cluster dari partikel yang dihasilkan pada tahap sebelumnya. Pengelompokan data ini akan ditentukan dengan rumus distance(2.15) dan akan dipilih yang memiliki nilai terkecil dari seluruh cluster yang ada. Setelah data ini mendapatkan cluster, data tersebut akan dibandingkan dengan data terbaik yang ada pada cluster tersebut. Bila cluster tersebut belum memiliki data terbaik maka otomatis data tersebut akan menjadi cluster terbaik pada cluster tersebut. Namun bila ada cluster terbaik pada data tersebut maka akan dipilih antara kedua data tersebut data manakah yang memiliki nilai distance terendah terhadap nilai cluster kedua data tersebut. 3.3.4 Pengecekan Gbest Pada tahap ini dilakukan perhitungan nilai fitness function (2.16). pada tahap inisiasi parameter dan populasi telah ditentukan jumlah partikel yang dibuat. Pada setiap partikel akan dihitung nilai Fitness Function dan akan dibandingkan dengan nilai Fitness Function terbaik saat itu. Nilai Fitness Function terbaik dimiliki oleh partikel terbaik. Oleh karena itu,
19 bila ada partikel baru yang memiliki nilai Fitness Function lebih baik dari partikel terbaik sebelumnya, maka partikel tersebut akan menjadi partikel terbaik dan menjadi gbest. Proses ini akan terus berlangsung sampai tahap pembuatan partikel mencapai partikel terakhir. Dan gbest akhir pada tahap ini akan menjadi nilai keluaran pada proses ini.
3.4 PSOLF K-means Pada sub bab ini akan dijelaskan mengenai proses PSOLF k-means sehingga menghasilkan keluaran yang diharapkan seperti yang sudah dijelaskan sebelumnya. Setelah melalui tahap Particle Swarm Optimization Levy Flight. Sebelum mengeluarkan hasil keluaran, perlu ada beberapa proses untuk mendapatkan nilai cluster serta termasuk pada cluster mana saja seluruh data yang menjadi masukkan. Proses tersebut akan dijabarkan pada tahap ini. Tahap ini dibagi menjadi tiga proses yaitu inisiasi parameter, pengelompokan data, dan update centroid. Diagram alir tahap k-means ditunjukkan pada Gambar 3.3
Gambar 3.3 Diagram Alir PSOLF K-means
20 3.4.1 Inisialisasi Parameter Pada tahap ini akan dilakukan inisialisasi standar pada beberapa parameter. Diantaranya adalah jumlah data, jumlah cluster, jumlah atribut dan cluster awal. Berbeda dengan kmeans yang biasanya. Pada k-means ini, nilai awal yang digunakan sebagai cluster awal tidaklah random namun menggunakan nilai gbest dari hasil proses pada tahap sebelumnya. 3.4.2 Pengelompokan Data Pada tahap ini akan dilakukan pengelompokan data pada seluruh data. Pengelompokan ini dilakukan dengan cara menghitung jarak terdekat data dengan seluruh cluster dengan rumus distance(2.15). Setelah proses ini selesai, seluruh data sudah memiliki kelompoknya masing-masing. 3.4.3 Update Centroid Pada tahap ini akan dilakukan perhitungan nilai centroid yang baru. Setiap data yang telah mendapatkan kelompoknya masing-masing sesuasi dengan tahap sebelumnya akan dijumlahkan secara keseluruhan dengan setiap data dengan cluster yang sama pada seluruh centroid. Jumlah masingmasing centroid akan dibagi dengan jumlah total data yang ada pada kelompok tersebut dan hasilnya akan menjadi nilai centroid baru pada cluster tersebut. Setelah proses tersebut telah selesai dijalankan, maka nilai setiap cluster akan dibandingkan dengan nilai cluster sebelum nilai cluster tersebut diubah. Bila nilainya tidak sama maka proses 3.4.2 akan dilakukan lagi. Tapi bila seluruh cluster memiliki nilai yang sama dengan cluster sebelumnya maka proses ini selesai.
21
BAB IV IMPLEMENTASI Pada bab ini akan dibahas mengenai implementasi yang dilakukan berdasarkan rancangan yang telah dijabarkan pada bab sebelumnya. Implementasi kode program dilakukan menggunakan bahasa Python. 4.1 Lingkungan Implementasi Spesifikasi perangkat keras dan perangkat lunak yang digunakan dalam implementasi ini ditampilkan pada Tabel 4.1. Tabel 4.1 Lingkungan Perancangan Perangkat Lunak Perangkat Perangkat keras Perangkat lunak
Spesifikasi Prosesor: 2.8 GHz Intel Core i7 Memori: 16.00 GB 1600 MHz DDR3 Sistem Operasi: macOS Sierra version 10.12.2 Perangkat Pengembang: PyCharm CE Perangkat Pembantu: Numbers
4.2 Implementasi Sub bab implementasi ini menjelaskan tentang implementasi proses yang sudah dijelaskan pada bab desain perangkat lunak.
22 4.2.1 Implementasi Tahap Inisialisasi Awal Sub bab ini membahas implementasi tahap inisialisasi awal. Pada tahap ini data masukan berupa data teks pada baris awal file data yang menjadi masukkan. Implementasi dilakukan dengan menggunakan passing variabel sederhana dan ditunjukkan oleh Kode Sumber 4.1. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
clusterAmount = int(f.readline()) clusterDimension = int(f.readline()) min = f.readline() min = min.split(" ") for i in range(clusterDimension): val = float(min[i]) dataMin.append(val) max = f.readline() max = max.split(" ") for i in range(clusterDimension): val = float(max[i]) dataMax.append(val)
Kode Sumber 4.1 Implementasi Tahap Inisialisasi Awal Sesuai dengan yang telah dibahas sebelumnya, 4 baris awal akan digunakan sebagai jumlah cluster yang akan dibuat, jumlah atribut pada setiap cluster, nilai minimum tiap centroid, dan nilai maksimum pada tiap centroid seperti yang dapat dilihat pada Kode Sumber 4.1. 4.2.2 Implementasi Tahap Inisialisasi Random pada Partikel Awal Sub bab ini membahas implementasi tahap Random pada Partikel Awal. Partikel terdiri dari velocity dan position yang masing-masing memiliki data sebanyak centroid yang telah ditentukan dan ditambah dua data sebagai nama cluster serta nilai fitness function sebagai pembanding yang akan digunakan pada tahap selanjutnya. Implementasi ditunjukkan oleh Kode Sumber 4.2.
23
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24.
pbestData = [] listPbest = [] listX = [] listV = [] for i in range(clusterAmount): X = [] V = [] temp = [] for y in range(clusterDimension): X.append(random.uniform(dataMin[y], dataMax[y])) V.append(random.uniform(dataMin[y], dataMax[y])) temp.append(dataMax[y]) X.append(i+1) V.append(i+1) temp.append(i+1) X.append(100.0) V.append(100.0) temp.append(100.0) listX.append(X) listV.append(V) pbestData.append(temp) listPbest.append(listX) listPbest.append(listV)
Kode Sumber 4.2 Inisialisasi Nilai Random Awal Partikel 4.2.3 Implementasi Tahap Konversi Data Data masukkan yang dibaca oleh program adalah data teks dan bertipe data string. Oleh karena itu perlu dilakukan konversi data agar data tersebut bisa diolah oleh program. Konversi data dilakukan dengan konversi standar yang telah dimiliki oleh python. Pada implementasi ini, proses konversi data dapat dilihat pada Kode Sumber 4.3.
24 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
totalData = 0 for line in f: totalData += 1 tes = line.split(' ') length = len(tes) tes.pop(length - 1) list = [] for x in tes: list.append(float(x)) list.append(0) Data.append(list)
Kode Sumber 4.3 Implementasi Konversi Data Pada Kode Sumber 4.3. setiap data akan dihitung penambahan 1 untuk jumlah total data yang nanti akan digunakan sebagai fitness function dan setiap data akan dipisahkan berdasarkan spasi pada data tersebut yang akan menjadi nilai centroid per datanya dan akan membuang data paling akhir karena data tersebut berupa nama cluster data tersebut yang sesungguhnya dan tidak akan digunakan untuk proses program ini. Kemudian agar data tersebut bisa diolah akan dilakukan konversi dari nilai string menjadi nilai float agar lebih mudah diolah dan pada akhirnya akan dimasukkan data hasil olahan proses ini pada satu array yang bernama Data. 4.2.4 Implementasi Particle Swarm Optimization Levy Flight Sub bab ini membahas implementasi tahap Particle Swarm Optimization Levy Flight yang menggunakan nilai awal random yang dilakukan pada tahap sebelumnya dan data masukkan sebagai masukkan. Particle Swarm Optimization Levy Flight secara kesuluruhan dapat dilihat pada Pada Kode Sumber 4.4 dan Kode Sumber 4.4 Implementasi pembuatan partikel
25 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
17. 18. 19. 20. 21. 22.
23. 24. 25.
for it in range(0,100): #pada awal loop pada setiap iterasi ini #lakukan inisiasi partikel awal for i in range(0,25): listX = [] listV = [] sse = 0 w = 0.1 + 0.8 * (1 - (i + 1) / loop) ran = random.uniform(0,1) if (ran < 0.5): ran1 = random.uniform(0, 1) ran2 = random.uniform(0.01, 1) for x in range(clusterAmount): V = [] X = [] for y in range(clusterDimension): levy = listPbest[0][x][y] + (ran1 / pow(ran2, beta)) tempVelocity = w * levy + 1.2 * ran * (pbestData[x][y] listPbest[0][x][y]) + 1.8 * ran * \ (listGbest[x][y] listPbest[0][x][y]) listPbest[1][x][y] = tempVelocity listPbest[0][x][y] = tempVelocity else: for x in range(clusterAmount): for y in range(clusterDimension): tempVelocity = w * listPbest[1][x][y] + 1.2 * ran * (pbestData[x][y] - listPbest[0][x][y]) \ + 1.8 * ran * (listGbest[x][y] - listPbest[0][x][y]) tempPosition = listPbest[0][x][y] + tempVelocity listPbest[1][x][y] = tempVelocity listPbest[0][x][y] = tempPosition
Kode Sumber 4.4 Implementasi pembuatan partikel
26 Pada Kode Sumber 4.4 dapat dilihat bahwa ada dua cara yang digunakan untuk membut partikel. Cara pertama adalah dengan menggunakan rumus (2.1) dan (2.2). Cara kedua adalah dengan menggunakan rumus (2.10) dan (2.11). Pemilihan rumus manakah yang digunakan bergantung pada nilai random yang muncul. Apakah nilai random tersebut lebih dari 0.5 atau lebih kecil dari 0.5. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27.
for x in range(clusterAmount): for y in range(clusterDimension): pbestData[x][y] = dataMax[y] pbestData[x][fitness] = 100.00 sse = 0 for x in Data: check = 1000 for y in listPbest[0]: val = 0 for z in range(clusterDimension): diff = x[z] - y[z] diff = diff * diff val += diff val = math.sqrt(val) if (check > val): check = val x[cluster] = y[cluster] sse += check for y in pbestData: if (x[cluster] == y[cluster]): if (y[fitness] > check): for z in range(clusterDimension): y[z] = x[z] y[fitness] = check continue
Kode Sumber 4.5 Implementasi Pengelompokan Data dan Pengecekan pbest
27 Pada Kode Sumber 4.5 diawal kode tersebut dilakukan penyimpanan nilai tertinggi pada nilai pbest. Kode tersebut digunakan agar pada data awal yang masuk pada suatu cluster yang ada akan otomatis menjadi pbest pada cluster tersebut. Tahap selanjutnya adalah pengelompokan data berdasarkan jarak terdekat data dengan jarak seluruh cluster. Data dengan jarak cluster terdekat akan masuk pada cluster tersebut. Setelah mendapatkan cluster, data tersebut akan dibandingkan dengan data terbaik pada cluster tersebut. Bila data tersebut lebih baik dari data terbaik pada cluster tersebut, maka data tersebut akan mengganti data terbaik pada cluster tersebut atau yang biasa disebut dengan pbest dengan datanya. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
fitnessfunc = math.sqrt(sse) f1 = fitnessfunc / totalData fitnessfunc = 1 / (1 + f1) if(fitFuncParticle < fitnessfunc): fitFuncParticle = fitnessfunc for x in range(clusterAmount): for y in range(cluster): listPbest[x][y] = listParticle[0][x][y] bestData[x][y] = pbestData[x][y] if(fitFuncGlobal < fitFuncParticle): fitFuncGlobal = fitFuncParticle for x in range(clusterAmount): for y in range(cluster): listGbest[x][y] = listPbest[x][y] gbestData[x][y] = bestData[x][y]
Kode Sumber 4.6 Memperbarui Pbest dan Gbest Pada Kode Sumber 4.6 dilakukan perhitungan fitness function pada partikel tersebut. Setelah mendapatkan nilai tersebut, nilai tersebut akan dibandingkan dengan fitness function pada partikel terbaik. Bila nilai tersebut lebih besar maka nilai cluster yang pada saat itu akan menjadi partikel
28 terbaik yang biasa disebut pbest. Bila iterasi pada populasi sudah sampai pada akhir, maka akan dilakukan pengecekan antara nilai pbest dan nilai gbest. Bila nilai fitness function pada gbest lebih kecil dari nilai fitness function pada pbest, maka nilai pbest akan digunakan sebagai nilai gbest. Kedua nilai tersebut akan selalu digunakan pada saat membuat suatu partikel baru. 4.2.5 Implementasi K-means Sub bab ini membahas implementasi k-means. Masukan dari tahap ini adalah hasil gbest dari proses Particle Swarm Optimization Levy Flight. Implementasi k-means secara keseluruhan dapat dilihat pada Kode Sumber 4.7, Kode Sumber 4.8 dan Kode Sumber 4.9. 1. 2. 3.
idx = 1 for i in range(clusterDimension): newCluster.append(0.0)
Kode Sumber 4.7 Inisialisasi Jumlah Iterasi dan Cluster Baru Pada Kode Sumber 4.7 dilakukan inisiasi pada kedua variabel tersebut. Variabel idx berfungsi sebagai penanda jumlah iterasi yang dilakukan. Variabel tersebut pada tugas akhir ini akan menjadi salah satu parameter pembanding pada optimasi yang dihasilkan. Variabel newCluster berfungsi sebagai penyimpanan data cluster sementara yang nanti akan selalu berubah-ubah pada setiap iterasinya. 1. 2. 3. 4. 5. 6. 7. 8.
while(1): breaker = 1 sse = 0 for i in Data: check = 1000 for y in listGbest: val = 0
29
9. 10. 11. 12. 13. 14. 15. 15.
for z in range(clusterDimension): diff = i[z] - y[z] diff = diff * diff val += diff val = math.sqrt(val) if(check > val): check = val i[cluster] = y[cluster] sse += check
Kode Sumber 4.8 Mendapatkan Kelompok Data Pada Kode Sumber 4.8 dilakukan pengelompokan berdasarkan cluster yang ada. Pada iterasi pertama cluster tersebut berasal dari hasil keluaran proses Particle Swarm Optimization Levy Flight. Pengelompokan data akan dilakukan dengan cara menghitung distance antara data dengan seluruh cluster seperti yang sudah dijelaskan pada tahap dan bab sebelumnya. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
for i in listGbest: total = 0 for y in range(clusterDimension): newCluster[y] = 0.0 for y in Data: if(i[cluster] == y[cluster]): total += 1 for z in range(clusterDimension): newCluster[z] += y[z] else: continue if(total != 0): for z in range(clusterDimension): newCluster[z] /= total if(newCluster[z] != i[z]): breaker = 0 i[z] = newCluster[z] if(breaker == 1): break
30 21.
idx += 1
Kode Sumber 4.9 Memperbarui Cluster dan Centroid Baru Pada Kode Sumber 4.9 dilakukan penghitungan jumlah seluruh data pada setiap cluster dan pada setiap centroidnya. Kemudian setiap centroid akan dibagi dengan jumlah data per cluster. Setelah mendapatkan nilai baru. Nilai tersebut akan dibandingkan dengan seluruh nilai cluster yang sebelumnya. Bila nilai cluster tersebut berubah maka proses k-means akan dilakukan lagi namun dengan nilai masukkan awal yaitu nilai cluster baru. Tapi bila nilai cluster tersebut tidak berubah, maka proses k-means akan berakhir.
4.2.6 Tahap Pemunculuan Nilai Keluaran Sub bab ini membahas pemunculan nilai keluaran. Nilai keluaran pada hasil akhir ini berupa data seluruh cluster, jumlah data per tiap cluster, jumlah iterasi, dan nilai akhir fitness function. Tahap pemunculan nilai keluaran dapat dilihat pada Kode Sumber 4.10 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
fitnessfunc = math.sqrt(sse) f1 = fitnessfunc / totalData fitnessfunc = 1 / (1 + f1) for i in listGbest: total = 0 for y in range(clusterDimension): newCluster[y] = 0.0 for y in Data: if (i[cluster] == y[cluster]): total += 1 for z in range(clusterDimension): newCluster[z] += y[z] else: continue if (total != 0):
31 17. 18. 19. 20. 21. 22. 23. 24.
for z in range(clusterDimension): newCluster[z] /= total if (newCluster[z] != i[z]): breaker = 0 i[z] = newCluster[z] print i, total print idx, fitnessfunc
Kode Sumber 4.10 Tahap Pemunculan Nilai Keluaran Pada Kode Sumber 4.10 langsung dilakukan perhitungan nilai fitness function akhir. Kemudian dilakukan pengecekan terhadap setiap cluster dan mengecek data mana saja yang berada dikelompoknya dan dijumlahkan total keseluruhan data yang ada pada setiap cluster. Pada akhir proses ini akan dikeluarkan output setiap cluster beserta total data pada setiap cluster. Dan pada akhir program akan dikeluarkan nilai jumlah iterasi dan fitness function akhir.
32 [Halaman ini sengaja dikosongkan]
BAB V UJI COBA DAN EVALUASI Pada bab ini akan dijelaskan hasil uji coba dan evaluasi program yang telah selesai diimplementasikan. 5.1 Lingkungan Uji Coba Lingkungan uji coba yang akan digunakan adalah, 1. Perangkat Keras Prosesor 2.8 GHz Intel Core i7 2. Perangkat Lunak macOS Sierra version 10.12.2 3. Perangkat Pengembang PyCharm CE 5.2 Data Uji Coba Data yang digunakan untuk uji coba implementasi particle swarm optimization levy flight untuk inisialisasi pusat cluster pada k-means untuk pengelompokan data adalah data UCI yang memiliki tipe atribut real atau integer. Pada awal data diperlukan 4 baris tambahan. Pada baris pertama berisi jumlah cluster yang ingin dibuat. Baris kedua berisi jumlah atribut yang dimiliki data tersebut. Baris ketiga berisi nilai minimum pada tiap dimensi yang antar dimensinya dipisahkan dengan tanda spasi. Bari keempat berisi nilai maksimum pada tiap dimensi yang antar dimensinya dipisahkan dengan tanda spasi. Jumlah data yang diuji berjumlah tiga dataset yang berupa data yeast, data ecoli, dan data iris[3]. 5.3 Alur Uji Coba Pada sub bab ini akan dijelaskan mengenai alur kerja dari sistem pengelompokan data. Dimulai dari input hingga output.
33
34 5.3.1 Input Tahap Input cukup sederhana. Pastikan data yang dimiliki telah memenuhi spesifikasi yang telah dijelaskan. Kemudian cukup ketikkan nama file data pada data yang ingin ada uji. Ilustrasi tahap input dapat dilihat pada Gambar 5.1
Gambar 5.1 Contoh Proses Input 5.3.2 Output Tahap output akan secara otomatis dan langsung muncul ketika input telah diketikkan dan tombol enter ditekan. Ilustrasi tahap output dapat dilihat pada Gambar 5.2
35
Gambar 5.2 Contoh Proses Output
36 5.4 Skenario Uji Coba Pada sub bab ini akan dijelaskan mengenai skenario uji coba yang telah dilakukan. Uji coba yang dilakukan akan membandingkan hasil output pada PSOLF k-means dan kmeans. Dilakukan sebanyak dua puluh kali pada setiap data yang diuji. Pada percobaan akan ada keterangan mengenai fitness awal, fitness akhir, iterasi jumlah data per kelompok data dan waktu. Fitness awal dan fitness akhir adalah parameter pembanding untuk kedekatan data dengan cluster yang berfungsi sebagai pembanding baik atau buruknya hasil dari output program yang telah dijalankan. Iterasi adalah banyaknya perulangan pada proses k-means yang dijalankan. Jumlah data per kelompok data adalah jumlah data yang dimiliki oleh masing-masing data. Waktu adalah lama waktu yang dihabiskan untuk setiap percobaan yang dilakukan. Telah dilakukan beberapa skenario uji coba, diantaranya yaitu: 1. Perbandingan hasil pada data yeast. 2. Perbandingan hasil pada data ecoli. 3. Perbandingan hasil pada data iris.
5.4.1 Skenario Uji Coba Data Yeast Skenario uji coba data yeast adalah perbandingan hasil pada data yeast. Data yeast sendiri memiliki 1484 data, 10 cluster dan 8 atribut. Hasil k-means dapat dilihat pada Tabel 5.1 dan hasil PSOLF k-means dapat dilihat pada Tabel 5.2. Tabel 5.1 Hasil Data Yeast K-means No
Fitness Awal
Itera si
Fitness Akhir
1
0.97974
29
0.98955
Jumlah Data per Kelompok Data 168, 319, 15, 0, 111, 191, 391, 110, 3, 176
Waktu (detik) 1.149
37
2
0.98178
15
0.98849
3
0.98033
18
0.98963
4
0.97729
24
0.98923
5
0.97987
20
0.98918
6
0.98206
29
0.98918
7
0.9809
12
0.98882
8
0.98012
28
0.98971
9
0.97986
17
0.98929
10
0.98063
18
0.98918
11
0.978
36
0.98965
12
0.97893
14
0.9895
13
0.98065
27
0.98918
14
0.97955
15
0.98888
0, 289, 251, 929, 0, 5, 0, 0, 0, 10 15, 0, 210, 219, 192, 130, 191, 61, 108, 358 428, 0, 0, 13, 511, 125, 225, 0, 15, 167 168, 0, 0, 15, 224, 0, 124, 438, 0, 515 517, 0, 225, 0, 435, 0, 168, 124, 2, 13 819, 0, 0, 0, 0, 234, 273, 0, 15, 143 303, 68, 147, 87, 252, 96, 150, 183, 15, 183 438, 0, 15, 162, 14, 508, 0, 221, 3, 123 515, 11, 0, 4, 225, 168, 0, 0, 436, 125 359, 165, 187, 110, 110, 208, 15, 128, 0, 202 14, 428, 15, 329, 210, 120, 198, 167, 0, 3 124, 514, 15, 0, 0, 436, 168, 227, 0, 0 4, 138, 0, 0, 11, 212, 0, 803, 41, 275
0.59 0.742
1.002
0.799
1.205
0.488
1.167
0.687
0.715
1.498
0.567
1.135
0.612
38
15
0.98028
17
0.9894
16
0.9805
20
0.98923
17
0.97998
14
0.98926
18
0.97888
29
0.98918
19
0.97939
24
0.98918
20
0.97797
36
0.98939
RataRata
0.97983
22.1
0.98925
0, 335, 172, 218, 0, 425, 198, 121, 11, 4 165, 3, 225, 10, 512, 3, 124, 440, 0, 2 11, 510, 4, 165, 223, 434, 14, 0, 0, 123 515, 124, 0, 168, 0, 15, 0, 0, 438, 224 515, 224, 124, 0, 15, 0, 0, 0, 438, 168 12, 146, 306, 15, 0, 384, 294, 114, 213, 0
0.681
0.801
0.579
1.222
0.999
1.49 0.906
Tabel 5.2 Hasil Data Yeast PSOLF K-means No
Fitness Awal
Itera si
Fitness Akhir
1
0.98703
12
0.98882
2
0.9875
36
0.98902
3
0.98768
30
0.98918
4
0.9868
9
0.98777
Jumlah Data per Kelompok Data 15, 235, 0, 266, 0, 0, 144, 824, 0, 0 227, 171, 124, 0, 0, 0, 516, 446, 0, 0 0, 435, 0, 0, 225, 517, 168, 124, 15, 0 0, 458, 0, 0, 0, 1026, 0, 0, 0, 0
Waktu (detik) 106.79
101.1
101.17 100.19
39
5
0.98683
15
0.98784
6
0.98677
12
0.98792
7
0.98769
23
0.98918
8
0.98733
12
0.98848
9
0.98746
15
0.98924
10
0.98756
14
0.98849
11
0.98638
12
0.98792
12
0.98632
11
0.98848
13
0.98754
7
0.98825
14
0.98691
18
0.98848
15
0.98773
21
0.98941
16
0.98728
18
0.98893
17
0.98666
13
0.98882
18
0.98654
12
0.98798
19
0.98756
16
0.98918
20
0.98707
11
0.98832
0, 1013, 457, 0, 14, 0, 0, 0, 0, 0 0, 453, 0, 0, 1016, 0, 15, 0, 0, 0 0, 0, 515, 224, 0, 15, 124, 438, 168, 0 0, 0, 15, 252, 0, 289, 0, 928, 0, 0 15, 0, 0, 165, 14, 434, 510, 123, 223, 0 5, 0, 251, 10, 0, 0, 289, 929, 0, 0 0, 1016 ,0, 0, 0, 15, 453, 0, 0, 0 0, 0, 15, 289, 0, 0, 929, 0, 0, 251 0, 0, 432, 0, 0, 0, 0, 149, 15, 888 0, 0, 929, 0, 0, 15, 251, 0, 0, 289 423, 198, 340, 219, 15, 119, 0, 0, 2, 168 0, 0, 14, 0, 0, 166, 15, 235, 497, 557 0, 273, 0, 143, 0, 0, 15, 0, 234, 819 0, 0, 0, 0, 0, 0, 14, 15, 1007, 448 125, 166, 0, 227, 514, 0, 15, 0, 0, 437 0, 15, 0, 428, 14, 0, 0, 0, 879, 148
100.15 101.75
100.42 100.12 100.59 101.19 99.02 99.79 100.05 102.72 99.59
100.66 100.62 100.4 104.78 99.97
40 Rata Rata
0.98713
15.85
0.98858
101.05
Dari kedua tabel tersebut terlihat bahwa metode PSOLF k-means menghasilkan fungsi fitness yang lebih rendah dan memiliki iterasi yang lebih sedikit bila dibandingkan dengan metode k-means. Evaluasi yang dilakukan adalah melihat posisi global optimum pada percobaan satu jumlah cluster sampai dua belas jumlah cluster terhadap nilai SSE yang dimiliki tiap cluster. Secara jelasnya dapat dilihat pada Gambar 5.3
Gambar 5.3 Grafik Yeast Cluster terhadap SSE Pada Gambar 5.3 terlihat perbandingan jumlah cluster dan SSE pada data yeast. Jumlah cluster sepuluh menjadi jumlah cluster optimum karena pada gambar tersebut terlihat jumlah cluster setelahnya memiliki nilai stabil. Walaupun pada jumlah cluster tiga sampai jumlah cluster enam memiliki nilai
41 yang stabil namun pada jumlah cluster tujuh dan jumlah cluster sepuluh terdapat penurunan yang signifikan. 5.4.2 Skenario Uji Coba Data Ecoli Skenario uji coba data ecoli adalah perbandingan hasil pada data ecoli. Data ecoli sendiri memiliki 338 data, 8 cluster dan 7 atribut. Hasil k-means dapat dilihat pada Tabel 5.3 dan hasil PSOLF k-means dapat dilihat pada Tabel 5.4. Tabel 5.3 Hasil Data Ecoli K-means No
Fitness Awal
Iteras i
Fitness Akhir
1
0.96018
17
0.97652
2
0.95965
29
0.97682
3
0.95842
13
0.97555
4
0.96224
11
0.97569
5
0.96095
33
0.97657
6
0.962
14
0.97575
7
0.96194
23
0.97638
8
0.9571
8
0.97615
9
0.96401
18
0.97652
10
0.96206
14
0.97643
11
0.96291
14
0.97586
Jumlah Data per Kelompok Data 22, 63, 46, 8, 40, 99, 58, 0 42, 21, 28, 72, 76, 33, 54, 10 73, 80, 40, 0, 0, 77, 0, 66 121, 87, 22, 2, 38, 0, 8, 58 72, 76, 55, 39, 20, 66, 8, 0 9, 41, 73, 142, 62, 0, 8, 1 63, 25, 0, 67, 40, 53, 18, 70 70, 15, 34, 52, 0, 82, 44, 39 22, 61, 40, 46, 10, 57, 0, 100 60, 41, 0, 53, 27, 67, 25, 63 10, 22, 0, 57, 64, 140, 0, 43
Waktu (detik) 0.1184 0.1927 0.0937 0.0838 0.224 0.1002 0.1571 0.058 0.1239 0.0977 0.1004
42
12
0.96072
13
0.97569
13
0.96199
13
0.97647
14
0.9613
13
0.97538
15
0.96066
10
0.97586
16
0.96116
12
0.97511
17
0.96119
9
0.97588
18
0.96225
8
0.97543
19
0.96149
12
0.97569
20
0.96003
9
0.97643
RataRata
0.96111
14.65
0.97600
99, 0, 22, 0, 46, 8, 57, 104 69, 0, 63, 39, 8, 66, 51, 40 0, 26, 0, 143, 60, 0, 41, 66 43, 0, 0, 66, 57, 8, 22, 140 0, 0, 126, 40, 8, 0, 73, 89 40, 0, 64, 10, 22, 141, 59, 0 34, 0, 140, 80, 44, 9, 0, 29 45, 0, 99, 105, 22, 57, 8, 0 36, 0, 48, 36, 66, 40, 90, 20
0.0992 0.0939 0.0973 0.0763 0.0843 0.064 0.0569 0.0882 0.0641 0.1037
Tabel 5.4 Hasil Data Ecoli PSOLF K-means No
Fitness Awal
Iteras i
Fitness Akhir
1
0.9717
24
0.976
2
0.9729
21
0.9765
3
0.9725
11
0.9764
4
0.9726
25
0.9763
5
0.9737
11
0.9762
6
0.9744
11
0.9764
Jumlah Data per Kelompok Data 72, 42, 64, 0, 0, 24, 76, 58 72, 70, 61, 18, 3, 39, 66, 7 68, 46, 0, 44, 62, 66, 40, 10 10, 79, 0, 41, 40, 45, 60, 61 39, 74, 10, 34, 0, 66, 83, 30 61, 35, 44, 0, 78, 68, 10, 40
Waktu (detik) 18.265 17.831 17.43 16.835 16.607 17.437
43
7
0.9735
13
0.9759
8
0.974
10
0.9766
9
0.9747
5
0.9763
10
0.9729
15
0.9765
11
0.9727
10
0.9766
12
0.9726
9
0.9762
13
0.9725
10
0.9767
14
0.9726
15
0.9763
15
0.973
27
0.9766
16
0.973
14
0.9762
17
0.9723
13
0.9763
18
0.9725
5
0.9751
19
0.9722
7
0.9765
20
0.9718
7
0.9752
RataRata
0.97290
13.15
0.97624
10, 0, 31, 57, 96, 38, 44, 60 60, 38, 32, 61, 10, 64, 61, 10 39, 10, 36, 47, 17, 10, 104, 73 72, 41, 7, 50, 40, 26, 64, 36 61, 68, 40, 66, 44, 47, 4, 6 0, 74, 40, 4, 104, 47, 6, 61 56, 50, 64, 34, 25, 7, 41, 59 68, 73, 35, 1, 6, 3, 77, 73 45, 60, 7, 75, 62, 41, 3, 43 7, 0, 3, 74, 66, 83, 41, 62 66, 0, 8, 40, 85, 48, 39, 50 92, 0, 2, 72, 40, 0, 122, 8 37, 25, 54, 7, 23, 66, 79, 45 3, 102, 0, 22, 7, 0, 143, 59
18.563 17.495 18.572 17.292 16.686 16.904 16.582 17.712 17.149 17.103 16.789 16.935 17.34 17.153 17.334
Dari kedua tabel tersebut terlihat bahwa metode PSOLF k-means menghasilkan fungsi fitness yang lebih rendah dan memiliki iterasi yang lebih sedikit bila dibandingkan dengan metode k-means. Evaluasi yang dilakukan adalah melihat posisi global optimum pada percobaan satu jumlah cluster sampai sebelas
44 jumlah cluster terhadap nilai SSE yang dimiliki tiap cluster. Secara jelasnya dapat dilihat pada Gambar 5.4
Gambar 5.4 Grafik Ecoli Cluster terhadap SSE Pada Gambar 5.4 terlihat perbandingan jumlah cluster dan SSE pada data ecoli. Jumlah cluster tujuh menjadi jumlah cluster optimum karena pada gambar tersebut terlihat jumlah cluster setelahnya memiliki nilai yang lebih stabil. 5.4.3 Skenario Uji Coba Data Iris Skenario uji coba data iris adalah perbandingan hasil pada data iris. Data iris sendiri memiliki 150 data, 3 cluster dan 4 atribut. Hasil k-means dapat dilihat pada Tabel 5.5 dan hasil PSOLF k-means dapat dilihat pada Tabel 5.6.
45 Tabel 5.5 Hasil Data Iris K-means No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 RataRata
Fitness Awal 0.8912 0.9039 0.8972 0.8914 0.9041 0.9061 0.9028 0.8858 0.8974 0.8963 0.89 0.8982 0.9067 0.8826 0.9047 0.8984 0.9084 0.9121 0.8873 0.9029
Iter asi 12 5 5 9 11 12 9 5 5 5 7 11 13 8 15 3 4 6 10 5
Fitness Akhir 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9313 0.9382 0.9297 0.9382 0.9382 0.9382 0.9297
0.8983
8
0.9370
Jumlah Data per Kelompok Data 61, 39, 50 62, 50, 38 38, 62, 50 50, 61, 39 61, 50, 39 61, 50, 39 62, 50, 38 38, 62, 50 50, 62, 38 50, 39, 61 50, 38, 62 61, 39, 50 39, 50, 61 97, 29, 24 39, 61, 50 0, 53, 97 50, 39, 61 62, 50, 38 61, 50, 39 0, 97, 53
Waktu (detik) 0.0134 0.0074 0.0075 0.0121 0.0135 0.0144 0.0112 0.0076 0.0078 0.0075 0.0086 0.0132 0.0151 0.0105 0.0173 0.0054 0.0056 0.0086 0.0129 0.0074 0.01035
Tabel 5.6 Hasil Data Iris PSOLF K-means No 1 2 3 4 5 6 7
Fitness Awal 0.9334 0.9308 0.9313 0.9349 0.9357 0.9313 0.9327
Iter asi 4 9 3 3 3 5 4
Fitness Akhir 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382
Jumlah Data per Kelompok Data 38, 62, 50 39, 61, 50 50, 62, 38 62, 50, 38 50, 62, 38 62, 50, 38 50, 62, 38
2.3117 2.2454 2.1288 2.24 2.1492 2.2724 2.2253
46 8 9 10 11 12 13 14 15 16 17 18 19 20 RataRata
0.9323 0.9311 0.9298 0.9358 0.9308 0.9296 0.9281 0.9358 0.9362 0.9339 0.9329 0.9334 0.9262
4 3 5 9 4 3 5 8 4 6 3 4 3
0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382 0.9382
0.9323
4.6
0.9382
50, 62, 38 50, 61, 39 38, 62, 50 61, 50, 39 38, 62, 50 39, 50, 61 38, 62, 50 39, 61, 50 62, 38, 50 39, 50, 61 50, 38, 62 62, 50, 38 62, 50, 38
2.1166 2.2032 2.1997 2.1474 2.3216 2.1112 2.1748 2.1584 2.1998 2.2557 2.1294 2.267 2.1159 2.198675
Dari kedua tabel tersebut terlihat bahwa metode PSOLF k-means menghasilkan fungsi fitness yang lebih rendah dan memiliki iterasi yang lebih sedikit bila dibandingkan dengan metode k-means. Pada data iris dapat dengan mudah terlihat error yang berbahaya pada proses k-means. Dengan metode PSOLF k-means, error tersebut dapat dihilangkan khusus pada data iris. Evaluasi yang dilakukan adalah melihat posisi global optimum pada percobaan satu jumlah cluster sampai enam jumlah cluster terhadap nilai SSE yang dimiliki tiap cluster. Secara jelasnya dapat dilihat pada Gambar 5.5.
47
Gambar 5.5 Grafik Iris Cluster terhadap SSE Pada Gambar 5.5 terlihat perbandingan jumlah cluster dan SSE pada data iris. Jumlah cluster empat menjadi jumlah cluster optimum karena pada gambar tersebut terlihat jumlah cluster setelahnya memiliki nilai yang lebih stabil. 5.5 Analisis Uji Coba K-means dan PSOLF K-means Pada sub bab ini akan dijelaskan mengenai hasil uji coba yang telah dilakukan pada k-means dan PSOLF k-means. Dari uji coba tersebut dapat dilihat perbedaan pada hasil rata-rata iterasi dan fitness awal. Perbedaan hasil k-means dan PSOLF kmeans dapat dilihat pada Tabel 5.7.
48 Tabel 5.7 Hasil Rata-Rata K-means dan PSOLF K-means
Dataset
Yeast Ecoli Iris
Rata-Rata Fitness Awal Kmeans 0.97983 0.96111 0.8983
Rata-Rata Fitness Awal PSOLF Kmeans 0.98713 0.97290 0.9323
Rata-Rata Iterasi Kmeans
Rata-Rata Iterasi PSOLF Kmeans
22.1 14.65 8
15.85 13.15 4.6
Pada Tabel 5.7 dapat ditarik analisis yang diantaranya adalah PSOLF k-means dapat menghasilkan fitness awal yang lebih tinggi dan fitness awal yang tinggi dapat mempengaruhi penurunan iterasi pada proses k-means.
49
BAB VI KESIMPULAN DAN SARAN Pada bab ini akan dijelaskan mengenai kesimpulan dari proses dan uji coba dari program dan saran untuk pengembangan dari program itu sendiri. 6.1 Kesimpulan Dari hasil uji coba yang telah dilakukan, dapat diambil kesimpulan sebagai berikut: 1. Nilai random pada k-means yang buruk dapat menyebabkan akurasi yang buruk, nilai random yang bagus pada proses k-means dapat mempercepat performa k-means. 2. Particle Swarm Optimization Levy Flight dapat mengurangi tingkat error yang terjadi pada data iris pada proses k-means. 3. Nilai random yang sangat buruk tidak dapat ditanggulangi oleh Particle Swarm Optimization Levy Flight namun yang buruk masih dapat ditanggulangi. 4. PSOLF k-means tidak menambah akurasi best case pada kmeans tapi hanya dapat mengurangi terjadinya nilai random yang terlalu buruk pada proses k-means. 6.2 Saran Saran yang diberikan untuk pengembangan perangkat lunak ini adalah :
1.
Untuk meningkatkan akurasi secara signifikan perlu dilakukan optimasi pada proses k-means.
50 [Halaman ini sengaja dikosongkan]
DAFTAR PUSTAKA
[1]
[2]
[3]
"Pengelompokan Dokumen". [Online]. Available: http://aresearch.upi.edu/operator/upload/s_d545_060696_chap ter1.pdf. [Accessed 12 21 2016]. R. Jensi, G. Wiselin Jiji , An enhanced particle swarm optimization with levy flight for global optimization, Applied Soft Computing 43 (2016) 248–261. "Machine Learning Repository". [Online] Available: https://archive.ics.uci.edu/ml/datasets.html. [Accessed 12 21 2016]
51
52 [Halaman ini sengaja dikosongkan]
BIODATA PENULIS
Muhammad Faris Makarim, lahir di kota Jakarta pada tanggal 30 Juni 1994. Penulis adalah anak kedua dari dua bersaudara dan dbersarkan di kota Tangerang Selatan, Banten. Penulis menempuh pendidikan formal di SD. Negeri Puspiptek (2000-2006), SMP Negeri 1 Pamulang (2006-2009), SMA Negeri 1 Kota Tangerang Selatan (20092012). Pada tahun 2012 penulis memulai pendidikan strata satu di jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember Surabaya, Jawa Timur. Di Jurusan Teknik Informatika, penulis mengambil bidang minat Komputasi Cerdas Visual dan memiliki ketertarikan di bidang kecerdasan buatan, kecerdasan komputasional dan yang berhubungan dengan analisa data secara umum. Penulis dapat dihubungi melalui alamat email
[email protected]
liii
