METAGENOME FRAGMENT CLUSTERING MENGGUNAKAN ALGORITME PILLAR K-MEANS SECARA PARALEL DALAM MODEL MAPREDUCE FATHURROHMAN

METAGENOME FRAGMENT CLUSTERING MENGGUNAKAN ALGORITME PILLAR K-MEANS SECARA PARALEL DALAM MODEL MAPREDUCE

FATHURROHMAN

SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2016

PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa Tesis berjudul Metagenome Fragment Clustering Menggunakan Algoritme Pillar K-Means Secara Paralel Dalam Model MapReduce adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Oktober 2016 Fathurrohman NRP G651140071

RINGKASAN FATHURROHMAN. Metagenome Fragment Clustering Menggunakan Algoritme Pillar K-Means Secara Paralel Dalam Model MapReduce. Dibimbing oleh WISNU ANANTA KUSUMA dan HERU SUKOCO. Metagenom adalah DNA yang berasal dari komunitas mikroba yang dapat mengandung dari berbagai jenis spesies. Hal ini membuat rekonstruksi DNA dari metagenom tidak dapat langsung dilakukan. Mikroba yang heterogen pada metegenom tersebut, memungkinkan terjadinya kesalahan perakitan fragmen metagenom yaitu munculnya interspecies chimeras akibat tersambungnya fragmen antara spesies. Oleh karena itu diperlukan sebuah metode untuk mecegah terjadinya kesalahan tersebut. Salah satu cara untuk melakukan pencegahan terjadinya kesalahan perakitan fragmen metagenom sebelum rekonstruksi DNA dilakukan adalah dengan melakukan proses binning. Clustering merupakan sebuah cara untuk mengelompokan objek-objek yang mempunyai kemiripan ke dalam kelompok tertetntu, sehingga dapat digunakan untuk melakukan binning. Salah satu algoritme clustering adalah K-Means. K-Means Clustering tidak menjamin hasil clustering yang unik. Untuk mendapatkan hasil clustering optimal dapat dilakukan dengan melakukan penentuan centroid awal terlebih dahulu dengan menggunakan algoritme Pillar sebelum proses clustering dilakukan. Algoritme Pillar sangat efektif untuk menentukan posisi awal centroid pada KMeans dan meningkatkan ketepatan hasil clustering. Selain itu, data metagenom merupakan data dengan ukuran yang sangat besar, sehingga bisa digolongkan sebagai big data. Data berukuran besar dapat menjadi sebuah masalah komputasi dalam pengelolaan data secara sekuensial. Salah satu solusi untuk menangani masalah data berukuran besar ialah dengan memproses data secara paralel. MapReduce merupakan sebuah model pemrograman yang penerapannya digunakan untuk memproses data berukuran besar secara paralel. Hasil clustering data metagenom, baik dengan algoritme K-Means maupun dengan algoritme Pillar K-Means pada masing-masing data uji pada penelitian ini menunjukkan kesimpulan hasil yang sama, di mana secara dominan genus Agrobacterium selalu menggerombol dalam satu cluster, sedangkan genus Bacillus and Staphylococcus secara dominan selalu bergerombol dalam cluster yang sama. Jumlah iterasi dan waktu eksekusi pada penerapan Pillar K-Means dalam clustering data lebih efisien dibandingkan pada penerapan metode KMeans. Penggunaan model MapReduce memberikan kinerja yang lebih baik dibandingkan dengan proses sekuensial, di mana speedup yang dihasilkan berkisar antara 60,00 sampai 69,03 dengan nilai efisiensi rata-rata sebesar 400%. Penentuan nilai centroid awal pada algoritme Pillar menambah waktu total clustering dibandingkan dengan penentuan centroid dengan K-Means, sehingga masih bisa memungkinkan untuk dilakukan optimalisasi algoritme Pillar pada penelitian selanjutnya. Kata kunci: K-Means, MapReduce, Metagenome, Parallel Computing, Pillar Algorithm

SUMMARY FATHURROHMAN. Metagenome Fragment Clustering Using Pillar K-Means Algorithm in Parallel Using MapReduce Model. Supervised by WISNU ANANTA KUSUMA and HERU SUKOCO. Metagenome is DNA of the microbial community that contains a wide variety of species, it makes reconstruction of the desired DNA of microorganisms that could not perform directly. Various microbes on the metagenome can possibly cause an error in metagenome fragment assembly, that is, the occurrence of interspecies chimeras due to the connection of fragments among species. Therefore, it is necessary to construct a method that can avoid that error. One of the ways to make the prevention of the occurrence of mistakes in metagenome assembly is required a binning process before reconstruction of DNA. Clustering is a way to group objects that have similarities in certain clusters, so it can be used to perform the binning process. One of clustering algorithm is K-Means. Although the implementation of KMeans to clustering metagenome data have been performed successfully, but it allows for the development of the application of optimization in the initialization centroid phase to obtain a more optimal result. K-Means does not guarantee the product of a unique cluster. To get the optimal clustering can be done by determining the initial centroid using Pillar algorithm before the clustering process is done. Pillar highly effective algorithm for determining the initial position of the centroid of K-Means clustering and increase the accuracy of the results. Besides, metagenome data is data with an enormous size so it can be classified as big data. It can be a computation problem in data processing sequentially. One solution for dealing with large data is to process the data in parallel. MapReduce is a programming model to process significant amounts of data in parallel. The results of metagenome binning, both with K-Means or by a combination of Pillar and K-Means on each of the data test in this study showed the same conclusion, which is agrobacterium dominantly always huddled together in one cluster, while the bacillus and staphylococcus dominantly always clustered in the same group. The number of iterations and execution time on the Pillar K-Means clustering more efficiently than of K-Means. Likewise, using the MapReduce model provide better performance than the sequential process. The result showed that speedup values ranged from 60.00 to 69.03. Thoroughly, the efficiency of the parallelization process produced an average of 400%. However, the determination of the value of the initial centroid on Pillar algorithm add the total time of clustering compared with the K-Means, so it could still be possible to do the optimization of Pillar in future studies. Keywords: K-Means, MapReduce, metagenome, parallel computing, Pillar algorithm

© Hak Cipta Milik IPB, Tahun 2016 Hak Cipta Dilindungi Undang-Undang Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumbernya. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah; dan pengutipan tersebut tidak merugikan kepentingan IPB Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis ini dalam bentuk apa pun tanpa izin IPB

METAGENOME FRAGMENT CLUSTERING MENGGUNAKAN ALGORITME PILLAR K-MEANS SECARA PARALEL DALAM MODEL MAP-REDUCE

FATHURROHMAN

Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Komputer pada Program Studi Ilmu Komputer

SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2016

Penguji Luar Komisi pada Ujian Tesis : Irman Hermadi, SKom MS PhD

Judul Tesis : Metagenome Fragment Clustering Menggunakan Algoritme Pillar K-Means Secara Paralel Dalam Model MapReduce Nama : Fathurrohman NRP : G651140071

Disetujui oleh Komisi Pembimbing

DrEng Wisnu Ananta Kusuma, ST MT Ketua

DrEng Heru Sukoco, SSi MT Anggota

Diketahui oleh

Ketua Program Studi Ilmu Komputer

Dekan Sekolah Pascasarjana

Dr Ir Sri Wahjuni, MT

Dr Ir Dahrul Syah, MScAgr

Tanggal Ujian: 9 September 2016

Tanggal Lulus:

PRAKATA Puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Kuasa atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Tema yang dipilih dalam penelitian yang dilaksanakan sejak bulan Januari 2016 ini ialah clustering fragmen metagenom, dengan judul Metagenome Fragment Clustering Menggunakan Algoritme Pillar K-Means Secara Paralel Dalam Model MapReduce. Terima kasih penulis ucapkan kepada ibu, istri dan anak-anak serta seluruh keluarga, atas segala do’a dan kasih sayangnya. Ungkapan terima kasih juga disampaikan kepada Bapak DrEng Wisnu Ananta Kusuma, ST, MT dan Bapak DrEng Heru Sukoco, SSi, MT selaku pembimbing, serta Bapak Irman Hermadi, SKom, MS, PhD yang telah banyak memberi saran. Semoga karya ilmiah ini bermanfaat.

Bogor,

Oktober 2016 Fathurrohman

DAFTAR ISI DAFTAR TABEL

vi

DAFTAR GAMBAR

vi

DAFTAR LAMPIRAN

vi

1 PENDAHULUAN Latar Belakang Perumusan Masalah Tujuan Penelitian Manfaat Penelitian Ruang Lingkup Penelitian

1 1 2 2 3 3

2 TINJAUAN PUSTAKA Metagenom K-Means Clustering Algoritme Pillar Parallel Computing MapReduce

4 4 4 4 5 6

3 METODE Pengumpulan Data Ekstrasi Fitur Penentuan nilai centroid awal Clustering Data Evaluasi Hasil Clustering Menghitung Speedup dan Efisiensi Paralelisasi

8 8 8 9 9 10 11

4 HASIL DAN PEMBAHASAN Waktu dan Lokasi Penelitian Hasil Pengumpulan Data Hasil Ekstraksi Fitur Hasil Penentuan Nilai Centroid Awal dan Clustering Data

12 12 12 14 14

5 SIMPULAN DAN SARAN Simpulan Saran

19 19 19

DAFTAR PUSTAKA

20

RIWAYAT HIDUP

41

LAMPIRAN

DAFTAR TABEL 1 2 3 4 5 6 7 8 9

Data uji ke-1 (10 000 fragmen) Data uji ke-2 (100 000 fragmen) Data uji ke-3 (7 500 000 fragmen) Spesifikasi Perangkat Keras Perbandingan hasil clustering 3 cluster Perbandingan hasil clustering 4 cluster Kualitas clustering Nilai speedup untuk pengujian 10 000 fragmen pada 3 cluster Nilai speedup untuk pengujian 10 000 fragmen pada 4 cluster

12 13 13 14 17 17 18 18 18

DAFTAR GAMBAR 1 2 3 4 5 6

Perbedaan serial computing dan parallel computing Ilustrasi model MapReduce Tahapan Penelitian Ilustrasi proses k-mers frequency Algoritme Pillar (Barakbah 2009) Clustering 10 000 fragmen pada 3 cluster dengan : (a) K-Means (b) Pillar K-Means 7 Clustering 100 000 fragmen pada 3 cluster dengan : (a) K-Means (b) Pillar K-Means 8 Clustering 7 500 000 fragmen pada 3 cluster dengan : (a) K-Means (b) Pillar K-Means 9 Clustering 10 000 fragmen pada 4 cluster dengan: (a) K-Means (b) Pillar K-Means 10 Clustering 100 000 fragmen pada 4 cluster dengan: (a) K-Means (b) Pillar K-Means 11 Clustering 7 500 000 fragmen pada 4 cluster dengan: (a) K-Means (b) Pillar K-Means

6 7 8 9 10 15 15 15 16 16 16

DAFTAR LAMPIRAN 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Contoh Isi File Hasil Simulasi MetaSim Contoh Isi File Ekstraksi Fitur Contoh Keluaran Hasil Clustering Contoh keluaran perhitungan silhouette coefficient Rekap clustering setiap genus dalam 3 cluster untuk tiap data uji menggunakan algoritme Pillar K-Means Rekap clustering setiap genus dalam 3 cluster untuk tiap data uji menggunakan algoritme K-Means (percobaan ke-1) Rekap clustering setiap genus dalam 3 cluster untuk tiap data uji menggunakan algoritme K-Means (percobaan ke-2) Rekap clustering setiap genus dalam 3 cluster untuk tiap data uji menggunakan algoritme K-Means (percobaan ke-3) Rekap clustering setiap genus dalam 3 cluster untuk tiap data uji menggunakan algoritme K-Means (percobaan ke-4) Rekap clustering setiap genus dalam 3 cluster untuk tiap data uji menggunakan algoritme K-Means (percobaan ke-5) Rekap clustering setiap genus dalam 4 cluster untuk tiap data uji menggunakan algoritme Pillar K-Means Rekap clustering setiap genus dalam 4 cluster untuk tiap data uji menggunakan algoritme K-Means (percobaan ke-1) Rekap clustering setiap genus dalam 4 cluster untuk tiap data uji menggunakan algoritme K-Means (percobaan ke-2) Rekap clustering setiap genus dalam 4 cluster untuk tiap data uji menggunakan algoritme K-Means (percobaan ke-3) Rekap clustering setiap genus dalam 4 cluster untuk tiap data uji menggunakan algoritme K-Means (percobaan ke-4) Rekap clustering setiap genus dalam 4 cluster untuk tiap data uji menggunakan algoritme K-Means (percobaan ke-5) Waktu clustering dengan algoritme K-Means untuk data uji-1 (10 000 fragmen) pada 3 cluster Waktu clustering dengan algoritme K-Means untuk data uji-2 (100 000 fragmen) pada 3 cluster Waktu clustering dengan algoritme K-Means untuk data uji-1 (10 000 fragmen) pada 4 cluster Kode Program

23 23 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30

1

1 PENDAHULUAN Latar Belakang Metagenom adalah DNA yang berasal dari komunitas mikroba yang heterogen, kadang-kadang mengandung lebih dari 10.000 spesies dengan urutan data yang banyak mengandung noise dan parsial (Wooley et al. 2010). Hal ini membuat rekonstruksi DNA dari mikroorganisme yang diinginkan tidak dapat langsung dilakukan (Wooley et al. 2010). Sebuah DNA utuh merupakan hasil rekonstruksi dari fragmen-fragmen metagenom. Sehubungan dengan mikroba yang heterogen pada metegenom tersebut, maka diperlukan sebuah metode untuk mencegah terjadinya kesalahan perakitan terhadap fragmen metagenom, yaitu munculnya interspecies chimeras akibat tersambungnya fragmen antara spesies (Pekuwali et al. 2015). Salah satu cara untuk melakukan pencegahan terjadinya kesalahan perakitan metagenom adalah dengan melakukan proses binning sebelum rekonstruksi DNA dilakukan (Overbeek et al. 2013). Clustering yang termasuk dalam metode yang bersifat unsupervised learning merupakan salah satu cara untuk melakukan binning. Clustering merupakan sebuah cara untuk mengelompokkan objek-objek yang mempunyai kemiripan ke dalam kelompok tertentu (Zaki dan Meira 2014). Selain isu yang terkait sulitnya melakukan perakitan sekuens metagenom, data metagenom merupakan data dengan ukuran yang sangat besar, sehingga bisa digolongkan sebagai big data. Data berukuran besar dapat menjadi sebuah masalah komputasi dalam pengelolaan data secara sekuensial. Salah satu solusi untuk menangani masalah data berukuran besar ialah dengan memproses data secara paralel. MapReduce merupakan sebuah model pemrograman yang penerapannya digunakan untuk memproses data berukuran besar secara paralel yang diperkenalkan oleh Dean dan Ghemawat (2004). Sejak model pemrograman MapReduce dikembangan pada tahun 2004, serta munculnya Hadoop, model MapReduce menjadi pusat perhatian dan banyak digunakan dalam berbagai domain aplikasi sebagai strategi umum untuk paralelisasi pengolahan data yang besar. Penggunaan model MapReduce dan algoritme K-Means sudah dilakukan dalam beberapa penelitian. Model pemrograman MapReduce secara efektif dapat berhasil mengurangi waktu komputasi dalam melakukan penjajaran sekuen dibandingkan dengan melakukan penjajaran sekuen dengan algoritme sekuensial (Che-Lun et al. 2012). Arumugam et al (2012) telah melakukan penelitian yang menghasilkan kesimpulan bahwa penggunaan algoritme pada lingkungan cloud computing lebih efisien dibandingkan dengan pelaksanaan pada node tunggal untuk input data yang besar. Penelitian menggunakan pendekatan MapReduce juga dilakukan oleh Rasheed dan Rangwala (2013) mengenai clustering fragmen metagenom yang berhasil diimplementasikan dengan model MapReduce pada platform Hadoop. Zhao et al (2009) juga telah berhasil melakukan implementasi MapReduce untuk algoritme K-Means. Penerapan algoritme K-Means juga telah berhasil diimplementasikan menggunakan model MapReduce untuk mengelompokkan fragmen metagenom (Farino et al. 2015).

2 Walaupun implementasi model MapReduce pada K-Means untuk clustering metagenom telah berhasil dilakukan, namun masih memungkinkan untuk pengembangan dalam penerapan optimisasi pada tahap inisialisasi cluster untuk mendapatkan hasil yang lebih optimal. Algoritme K-Means tidak menjamin hasil clustering yang unik. Hasil clustering dari algoritme K-Means sulit untuk mencapai global optimum. Hasil lebih baik pada clustering menggunakan KMeans dapat dicapai setelah melaksanakan lebih dari satu kali, namun sulit untuk menentukan batas eksekusi yang memberikan kinerja terbaik (Bhusare et al. 2014). Untuk mendapatkan inisialisasi clustering optimal dapat dilakukan dengan melakukan penentuan centroid awal terlebih dahulu dengan menggunakan algoritme Pillar sebelum proses clustering dilakukan. Algoritme Pillar sangat efektif untuk menentukan posisi awal centroid pada K-Means dan meningkatkan ketepatan hasil clustering (Bhusare et al. 2014). Bhusare et al (2014) juga telah melakukan pengembangan algoritme Pillar K-Means pada penelitiannya dalam clustering data UCI Repository yang terdiri atas beberapa dataset antara lain iris, dan new thyroid. Modifikasi pengembangan algoritme Pillar yang dilakukan adalah dengan mengurangi proses pengulangan dalam mencari jarak anggota terhadap titik centroid yang sudah terpilih saat inisialisasi. Pada penelitian ini, penulis melakukan pengembangan penelitian berdasarkan penelitian-penelitian terkait yang sudah dilakukan oleh peneliti sebelumnya. Penelitian berfokus pada implementasi model pemrograman MapReduce dalam proses clustering data fragmen metagenom secara paralel dengan menerapkan algoritme Pillar K-Means. Algoritme Pillar digunakan dalam menentukan centroid awal untuk kemudian dilakukan clustering dengan algoritma K-Means. Perumusan Masalah

1.

2.

Rumusan masalah pada penelitian ini adalah: Apakah penggunaan algoritme Pillar dapat digunakan dalam clustering fragmen metagenom secara paralel menggunakan model pemrograman MapReduce ? Apakah hasil clustering fragmen metagenom menggunakan algoritme Pillar K-Means dapat meningkatkan kinerja dibandingkan dengan menggunakan algoritme K-Means ? Tujuan Penelitian

1. 2.

Tujuan penelitian ini, yaitu : Melakukan clustering data fragmen metagenom menggunakan algoritme Pillar K-Means secara parallel dengan model MapReduce. Mengevaluasi hasil clustering fragmen metagenom dengan mengukur kualitas hasil clustering dan waktu komputasi yang dibutuhkan dan membandingkan hasil clustering antara algoritme K-Means dengan algoritme Pillar K-Means.

3

Manfaat Penelitian Manfaat dari penelitian ini adalah untuk memberikan peningkatan kinerja lebih baik dalam melakukan clustering fragmen metagenom, sehingga dapat bermanfaat dalam rekonstruksi DNA. Ruang Lingkup Penelitian

1. 2.

Ruang lingkup pembahasan dalam penelitian ini adalah: Data yang digunakan adalah data penelitian Kusuma (2012) yang terdiri atas tiga genus dan 10 spesies. Fragmen yang dihasilkan tidak mengandung sequencing error.

4

2 TINJAUAN PUSTAKA Metagenom Metagenom adalah DNA yang berasal dari komunitas mikroba yang heterogen dari mikroorganisme yang diambil langsung dari lingkungan (Wooley et al. 2010). Sekuensing DNA atau pengurutan DNA adalah proses atau teknik penentuan urutan basa nukleotida pada suatu molekul DNA. Urutan tersebut dikenal sebagai sekuens DNA yang merupakan informasi paling mendasar suatu gen atau genom karena mengandung instruksi yang dibutuhkan untuk pembentukan tubuh makhluk hidup (Rogers 2011). Sekuensing DNA dapat dimanfaatkan untuk menentukan identitas maupun fungsi gen atau fragmen DNA lainnya dengan cara membandingkan sekuens-nya dengan sekuens DNA lain yang sudah diketahui (Glick et al. 2010). Fragmen-fragmen yang diperoleh dari metagenom mengandung berbagai organisme sehingga perlu dilakuan proses binning untuk mencegah terjadinya kesalahan perakitan terhadap fragmen metagenom, yaitu munculnya interspecies chimeras akibat tersambungnya fragmen antara spesies (Pekuwali et al. 2015). K-Means Clustering K-Means merupakan salah satu algoritme yang digunakan untuk mengelompokkan data. Tujuan algoritme ini yaitu untuk membagi data menjadi beberapa kelompok (Wu dan Kumar 2009). Algoritme ini menerima masukan berupa data tanpa label kelas. Hal ini berbeda dengan supervised learning yang menerima masukan berupa vektor (x1 , y1) , (x2 , y2) , …, (xi , yi), di mana xi merupakan data dari suatu data pelatihan dan yi merupakan label kelas untuk xi (Russell dan Norvig 2010). Pada algoritme pembelajaran ini, komputer mengelompokkan sendiri datadata yang menjadi masukannya tanpa mengetahui terlebih dulu target kelasnya (Wu dan Kumar 2009). Pembelajaran ini termasuk dalam unsupervised learning. Masukan yang diterima pada K-Means Clustering adalah data atau objek dan k buah kelompok (cluster) yang diinginkan. Algoritme ini akan mengelompokkan data atau objek ke dalam k buah kelompok tersebut. Pada setiap cluster terdapat titik pusat (centroid) yang merepresentasikan cluster tersebut. Proses clustering data ke dalam suatu cluster dapat dilakukan dengan cara menghitung jarak terdekat dari suatu data ke sebuah titik centroid (Wu dan Kumar 2009). Algoritme Pillar K-Means mempunyai masalah pada penentuan centroid awal, di mana centroid yang dipilih secara acak cenderung memiliki ketidakstabilan dalam penentuan cluster, terlebih untuk menangani data berukuran besar akan menghabiskan waktu dalam melakukannya. Masalah kedua adalah, jumlah cluster harus diamati secara menyeluruh untuk mendapatkan solusi cluster terbaik (Wahyudin et al. 2015). Untuk menagani permasalahan tersebut, maka disediakan

5 modifikasi K-Means clustering, dengan menerapkan optimasi centroid menggunakan algoritme Pillar. Algoritme Pillar mengadopsi fungsi pilar pada sebuah gedung yang digunakan pada setiap tepi atau sudut bangunan, sehingga berat bangunan terkonsentrasi pada tiap pilar. Ide yang sama dilakukan untuk tugas clustering di mana centroid awal terbaik diduga ada di tepi dataset, atau dengan kata lain, data objek k-terjauh dalam dataset dipilih sebagai centroid awal, di mana k adalah jumlah cluster yang diamati (Wahyudin et al. 2015). Bhusare et al (2014) telah melakukan pengembangan terhadap algoritme Pillar sehingga dapat memperbaiki waktu kompleksitas yang diperoleh oleh waktu kompleksitas K-Means. Waktu kompleksitas Pillar adalah (( ) ), di mana k adalah jumlah cluster, n adalah jumlah item dan h adalah jumlah outlier pada dataset. Dalam kasus jika tidak ada outlier dalam kumpulan data, ) ), atau sama dengan (( ) ), di mana i kompleksitas menjadi (( adalah jumlah iterasi. Untuk kasus yang lebih buruk di mana ada sejumlah outlier ) kompleksitas menjadi ( ) Dengan perbaikan dekat dengan ( algoritme Pillar yang tidak memasukkan anggota centroid untuk setiap centroid yang dipilih, jumlah item data n akan menurun setiap iterasi. Ketika anggota centroid awal tidak disertakan dan tidak terlibat dalam perhitungan jarak untuk langkah-langkah selanjutnya, n di iterasi akan menurun. Sehingga dengan perbaikan ini, dalam kasus di mana tidak ada outlier, kompleksitas menjadi ( ) Kompleksitas akan ( ) untuk kasus ada sejumlah outiler (Bhusare et al. 2014). Komputasi Paralel Komputasi paralel adalah penggunaan lebih dari satu Central Processing Unit (CPU) untuk menjalankan sebuah program secara simultan. Ide pemrosesan paralel adalah membagi tugas pengolahan data yang tadinya dibebankan kepada satu komputer, sekarang dibebankan ke beberapa komputer dalam sebuah cluster. Idealnya, parallel processing membuat program berjalan lebih cepat karena semakin banyak CPU yang digunakan (Barney 2015). Komputasi paralel merupakan teknik melakukan komputasi secara bersamaan dengan memanfaatkan beberapa komputer independen secara bersamaan. Ini umumnya diperlukan saat kapasitas yang diperlukan sangat besar, baik karena harus mengolah data dalam jumlah besar ataupun karena tuntutan proses komputasi yang banyak (Barney 2015). Tujuan utama dari pemrosesan paralel adalah untuk meningkatkan performa komputasi. Semakin banyak hal yang bisa dilakukan secara bersamaan (dalam waktu yang sama), semakin banyak pekerjaan yang bisa diselesaikan. Untuk melakukan aneka jenis komputasi paralel ini diperlukan infrastruktur mesin paralel yang terdiri atas banyak komputer yang dihubungkan dengan jaringan dan mampu bekerja secara paralel untuk menyelesaikan satu masalah. Untuk itu diperlukan aneka perangkat lunak pendukung yang biasa disebut sebagai middleware yang berperan untuk mengatur distribusi pekerjaan antar node dalam satu mesin paralel. Selanjutnya pemakai harus membuat pemrograman paralel untuk merealisasikan komputasi (Barney 2015).

6 Pemrograman paralel sendiri adalah teknik pemrograman komputer yang memungkinkan eksekusi perintah atau operasi secara bersamaan. Beberapa komputer terpisah yang digunakan secara bersamaan dan terhubung dalam satu jaringan komputer, biasanya disebut sistem terdistribusi. Komputasi paralel berbeda dengan multitasking. Pengertian multitasking adalah komputer dengan processor tunggal mengeksekusi beberapa tugas secara bersamaan. Sedangkan komputasi paralel melakukan tugas menggunakan beberapa processor atau komputer. Pada dasarnya, secara tradisional, perangkat lunak dibuat untuk melakukan tugas komputasi secara serial (serial computing), di mana satu instruksi dijalankan setelah instruksi lain dilakukan (berurutan) dan menggunakan satu processor. Gambaran perbedaan antara komputasi serial dengan komputasi paralel dapat dilihat pada Gambar 1 (Barney 2015).

Serial Computing

Parallel Computing

Gambar 1 Perbedaan serial computing dan parallel computing (Barney 2015) MapReduce MapReduce adalah salah satu model pemrograman paralel yang diciptakan untuk pengolahan data berukuran besar. Pengguna menentukan fungsi map yang memproses suatu pasangan key/value untuk menghasilkan satu set pasangan intermediate key/value, dan fungsi reduce yang menggabungkan semua nilai yang terkait. Program yang ditulis dalam model ini bersifat diparalelkan dan dijalankan pada sekelompok mesin/komputer. Sistem run-time mengurus rincian dari partisi data input, penjadwalan eksekusi program pada satu set mesin, penanganan kegagalan mesin, dan mengelola komunikasi antar mesin yang diperlukan. Hal ini memungkinkan pemrogram yang belum pengalaman dengan sistem paralel dan sistem terdistribusi mudah memanfaatkan sumber daya dari sistem terdistribusi. MapReduce dapat memproses banyak data dalam ukuran terabytes pada ribuan mesin. Ratusan program MapReduce telah diimplementasikan dan ribuan tugas MapReduce dijalankan pada cluster Google setiap hari (Dean dan Ghemawat 2004). Salah satu perangkat lunak yang mendukung model MapReduce adalah Apache Hadoop. Hadoop merupakan perangkat lunak yang berfungsi untuk mengolah data secara paralel pada sebuah kelompok komputer yang terkoneksi dalam sebuah jaringan. Hadoop mendukung pengolahan data secara terdistribusi. Istilah pengolahan data secara terdistribusi ini disebut dengan Hadoop Distribute File System (HDFS). HDFS terdiri atas komponen namnode dan datanode yang saling berhubungan. Namenode adalah komponen yang bertugas pada komputer

7 yang berfungsi sebagai master, sedangkan datanode adalah komponen yang bertugas pada komputer yang berfungsi sebagai slave (Khusumanegara 2013). Pada sebuah cluster komputer dalam hadoop terdiri atas sebuah master node dan beberapa slave node. Namenode pada sebuah master node bertugas sebagai jobtracker, yaitu mengkoordinasi datanode-datanode untuk melakukan beberapa tugas. Datanode pada sebuah slave node bertugas sebagai tasktracker, yaitu untuk menyimpan dan mengambil data pada slave node pada setiap permintaan yang dilakukan oleh namenode (Khusumanegara 2013).

Sumber : http://stackoverflow.com/posts/33395854/revisions

Gambar 2 Ilustrasi model MapReduce

8

3 METODE Tahapan-tahapan yang dilakukan dalam penelitian ini terdiri atas lima tahapan. Kelima tahapan tersebut adalah pengumpulan data, penyiapan data, ekstraksi fitur, penentuan centroid awal, clustering data, dan evaluasi hasil. Tahapan-tahapan tersebut dapat dilihat seperti pada Gambar 3.

Mulai

Pengumpulan data

Ekstrasi fitur Penentuan nilai centroid awal

Selesai

Evaluasi hasil

Clustering data

Gambar 3 Tahapan Penelitian Pengumpulan Data Data yang digunakan dalam penelitian ini menggunakan beberapa spesies mikroorganisme yang berasal dari beberapa genus. Data mikroorganisme tersebut didapatkan dengan cara mendapatkan dari sebuah organisasi yang diberi mandat menyimpan semua data metagenom (Thomas et al. 2012), yaitu National Centre For Biotechnology Information (NCBI) melalui alamat situs http://www.ncbi.nlm.nih.gov dengan format file FASTA (*.fna). Data mikroorganisme yang digunakan dalam penelitian ini terdiri atas 3 genus dengan klasifikasi terdiri atas 10 spesies (Kusuma 2012). Data merupakan hasil simulasi sequencing menggunakan MetaSim dengan error model exact, di mana hasil simulasi tidak memiliki kesalahan insersi, subtitusi, dan delesi pada proses sequencing (Farino et al. 2015). Ekstrasi Fitur Data fragmen metagenom yang dihasilkan berupa string panjang, kemudian diekstraksi fiturnya dengan menggunakan metode k-mers frequency. Feature vector akan dihasilkan dari proses ekstraksi fitur ini. K-mers frequency merupakan frekuensi kemunculan seluruh substring dengan panjang k pada suatu String. Nilai k yang digunakan dalam penelitian ini adalah 3-mer, sehingga akan menghasilkan 64 kombinasi. Ilustrasi proses clustering k string dari string fragmen metagenom dapat dilihat pada Gambar 4. Clustering kombinasi string yang dihasilkan akan dijumlahkan untuk setiap kombinasi yang sama.

9

Gambar 4 Ilustrasi proses k-mers frequency (Kusuma 2012) Penentuan nilai centroid awal Data fragmen metagenom yang sudah diekstraksi menjadi feature vector, kemudian dilakukan penentuan centroid awal untuk digunakan dalam proses clustering dengan metode K-Means. Algoritme Pillar digunakan sebagai metode untuk memilih kandidat centroid awal dalam data fragmen metagenom. Adapun algoritme Pillar yang digunakan dapat dilihat pada Gambar 5. Clustering Data Fragmen metagenom yang telah diekstraksi fiturnya selanjutnya akan dikelompokkan dengan menggunakan metode K-Means berdasarkan centroid awal yang sudah ditentukan dengan algoritme Pillar pada tahapan sebelumnya. Algoritme K-Means ialah sebagai berikut (Zaki dan Meira 2014): a. Inisialisasi secara random k titik untuk dijadikan pusat cluster atau centroid. b. Tempatkan setiap objek pada sebuah cluster. Sebuah objek akan ditempatkan ke dalam sebuah cluster dengan jarak terkecil (cluster assigment). c. Update/Perbaharui centroid dari masing-masing cluster (update centroid). d. Lakukan kembali tahap b dan c hingga tidak ada perubahan dari centroid setiap cluster. Langkah awal pada algoritme K-Means, diganti dengan penentuan k titik sebagai pusat cluster atau centroid dengan menggunakan data hasil penentuan centroid awal menggunakan algoritme Pillar pada tahapan sebelumnya. Pada penelitian ini, ukuran jarak antar fragmen yang digunakan adalah jarak Euclid. Jarak Euclid dirumuskan sebagai (Zaki dan Meira 2014): √∑ ( dengan: Di m i xik yik

: jarak antara objek xik dan yik, : jumlah fitur objek, : objek ke i, : fitur ke k dari objek xik, : fitur ke k dari objek yik.

)

( 1)

10 1. C = 0; SX = 0 ; DM=[] 2. Calculate D  dis(X,m) 3. Set number of neighbors nmin = α * (n/k) 4. Assign dmax  argmax(D) 5. Set neighborhood boundary nbdis = β * dmax 6. Set i as counter to determine the ith initial centroid 7. DM = DM + D 8. Select x  xargmax(DM) as the candidate for ith initial centroids 9. SX = SX + x 10. Set D as the distance metric between X to x 11. Set no  number of data points fulfilling D ≤ nbdis 12. Assign DM(x) = 0 13. If no < nmin, go to step 8 14. Assign D(SX) = 0 15. C = C υ x 16. i = i + 1 17. If i < k, go back to step 7 18. Finish in which C is the solution as optimized initial centroids

Gambar 5 Algoritme Pillar (Barakbah 2009)

Evaluasi Hasil Clustering Data hasil clustering harus dilakukan evaluasi untuk menentukan kualitas cluster. Salah satu metode yang popular untuk menilai kualitas cluster adalah Silhouette Coefficient (Zoubi dan Rawi. 2008). Nilai silhouette adalah sebuah ukuran tentang bagaimana kemiripan sebuah objek dalam cluster-nya (cohesion) dibandingkan terhadap cluster lain (separation). Nilai silhouette berkisar antara -1 sampai 1, di mana nilai tertinggi mengindikasikan bahwa objek berada pada cluster yang tepat dan tidak cocok berada pada cluster tetangganya. Jika objekobjek lebih banyak bernilai tinggi, maka hasil clustering telah sesuai. Jika lebih banyak nilai rendah atau nilai negatif, maka clustering kurang sesuai (Rousseeuw. 1987). Nilai silhouette dapat dihitung dengan menggunakan metode distance metric, seperti Euclidean distance atau manhattan distance (Rousseeuw. 1987). Silhouette Coefficient digunakan untuk melihat kualitas dan kekuatan cluster, seberapa baik suatu objek ditempatkan dalam suatu cluster. Metode ini merupakan gabungan dari metode cohesion dan separation. Rumus Silhouette Coefficient (Rousseeuw. 1987) adalah sebagai berikut: ()

() () ( ( ) ( ))

2)

dengan: s(i) : nilai silhouette coefficient data ke i, a(i) : rata-rata jarak data ke i terhadap data lain pada cluster yang sama, b(i) : rata-rata jarak data ke i terhadap data lain pada cluster yang berbeda dan diambil nilai terkecil.

11 Hasil semua nilai s(i) pada cluster yang sama dijumlahkan, kemudian dihitung rata-rata terhadap jumlah data pada cluster tersebut. Nilai rata-rata yang diperoleh menyatakan ukuran seberapa tepat data telah berkelompok pada cluster tersebut (Amorim dan Hennig. 2015). Nilai a(i) adalah seberapa berbeda titik ke-i pada cluster-nya sendiri, nilai a(i) yang rendah menyatakan bahwa titik tersebut sangat tepat berada pada kelompoknya. Nilai b(i) menyatakan jarak titik i ke titik lain pada cluster berbeda, semakin besar nilai b(i) menyatakan bahwa titik i cocok berada pada cluster-nya. Nilai b(i) yang sangat jauh lebih besar dari nilai a(i) mengindikasikan bahwa titik i tersebut berada pada kelompok yang tepat (Amorim dan Hennig. 2015). Nilai s(i) merupakan nilai rata-rata perbandingan jarak titik i antara jarak rata-rata pada cluster-nya terhadap jarak rata pada cluster lainnya. Nilai s(i) yang mendekati nilai satu menyatakan bahwa data ada pada cluster yang tepat. Nilai s(i) mendekati nilai negatif satu menyatakan bahwa data berada pada cluster yang kurang tepat, sedangkan s(i) mendekati nilai nol, menyatakan bahwa data ada pada posisi border di antara dua cluster. Rata-rata s(i) dari seluruh data pada sebuah cluster menyatakan bagaimana ukuran sebuah kelompok rapat pada kelompok tersebut. Rata-rata s(i) atas semua data dari dataset menyatakan ukuran seberapa tepat data telah berkelompok (Amorim dan Hennig. 2015). Menghitung Speedup dan Efisiensi Paralelisasi Proses mengetahui efisiensi hasil program paralelisasi dilakukan dengan cara menghitung waktu yang diperlukan dalam mengeksekusi data secara sekuensial dibandingkan waktu eksekusi dengan hasil yang diperloh secara paralelisasi. Pada tahapan ini dihitung waktu eksekusi masing-masing, baik secara paralel maupun secara sekuensial. Setelah didapatkan waktu eksekusinya, dihitung speedup (Sp) dan efisiensi (Ep) program paralel. Speedup adalah berapa kali lebih cepat waktu eksekusi program paralel (Tp) dibandingkan dengan program biasa (Ts). Efisiensi adalah ukuran seberapa besar waktu prosesor dipakai dengan baik, yaitu dengan menghitung speedup dibagi dengan jumlah prosesor (p). Rumus menghitung speedup dan efisiensi (Willmore 2012) adalah sebagai berikut : 5 3) 5 4)

12

4 HASIL DAN PEMBAHASAN Waktu dan Lokasi Penelitian Periode pengambilan, pengumpulan data penelitian serta pengujian dilakukan mulai dari Januari 2016 sampai dengan Juli 2016. Tempat penelitian dilakukan pada laboratorium Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam. Hasil Pengumpulan Data Data simulasi dibuat dalam tiga kelompok data uji dengan ukuran tiap fragmen metagenom pada masing-masing data uji berbeda-beda. Data uji ke-1 terdiri atas 10 000 fragmen metagenom dengan masing-masing fragmen berukuran 500bp, data uji ke-2 terdiri atas 100 000 fragmen metagenom dengan masing-masing fragmen berukuran 300bp, dan data uji ke-3 terdiri atas 6 500 000 fragmen metagenom dengan masing-masing fragmen berukuran 150bp. Setiap file .fna yang digunakan disimulasikan dengan menggunakan perangkat lunak MetaSim untuk menghasilkan fragmen-fragmen metagenom pada tiap data uji tersebut. Contoh data hasil simulasi dapat dilihat pada Lampiran 1, sedangkan rincian hasil simulasi diperlihatkan pada Tabel 1, Tabel 2 dan Tabel 3. Tabel 1 Data uji ke-1 (10 000 fragmen) No Spesies Genus Jumlah Ukuran Fragmen Fragmen 1 Agrobacterium radiobacter K84 785 500 bp chromosome 2 2 Agrobacterium tumefaciens str. Agrobacterium 794 500 bp C58 chromosome circular 3 Agrobacterium vitis S4 991 500 bp chromosome 4 Bacillus amyloliquefaciens 1109 500 bp FZB42 5 Bacillus anthracis str. Ames Bacillus 1435 500 bp Ancestor 6 Bacillus cereus 03BB102 1496 500 bp 7 Bacillus pseudofarmus OF4 1108 500 bp chromosome 8 Staphylococcus aureus subsp. 822 500 bp Aureus JH 9 Staphylococcus epidermis ATCC Staphylococcus 705 500 bp 12228 10 Staphylococcus haemolyticus 755 500 bp JCSC1435

13 Tabel 2 Data uji ke-2 (100 000 fragmen) No Spesies Genus Jumlah Ukuran Fragmen Fragmen 1 Agrobacterium radiobacter 7935 300 bp K84 chromosome 2 2 Agrobacterium tumefaciens Agrobacterium 7571 300 bp str. C58 chromosome circular 3 Agrobacterium vitis S4 10472 300 bp chromosome 4 Bacillus amyloliquefaciens 11043 300 bp FZB42 5 Bacillus anthracis str. Ames Bacillus 14799 300 bp Ancestor 6 Bacillus cereus 03BB102 14697 300 bp 7 Bacillus pseudofarmus OF4 10970 300 bp chromosome 8 Staphylococcus aureus subsp. 7991 300 bp Aureus JH 9 Staphylococcus epidermis Staphylococcus 6996 300 bp ATCC 12228 10 Staphylococcus haemolyticus 7526 300 bp JCSC1435 Tabel 3 Data uji ke-3 (7 500 000 fragmen) No Spesies Genus Jumlah Ukuran Fragmen Fragmen 1 Agrobacterium radiobacter K84 599380 150 bp chromosome 2 2 Agrobacterium tumefaciens str. Agrobacteriu 559771 150 bp C58 chromosome circular m 3 Agrobacterium vitis S4 784834 150 bp chromosome 1 4 Bacillus amyloliquefaciens 826226 150 bp FZB42 5 Bacillus anthracis str. Ames Bacillus 1102617 150 bp Ancestor 6 Bacillus cereus 03BB102 1110272 150 bp 7 Bacillus pseudofarmus OF4 812559 150 bp chromosome 8 Staphylococcus aureus subsp. 612295 150 bp Aureus JH 9 Staphylococcus epidermis Staphylococc 526599 150 bp ATCC 12228 us 10 Staphylococcus haemolyticus 565447 150 bp JCSC1435

14 Hasil Ekstraksi Fitur Setiap data uji yang dihasilkan pada pada langkah sebelumnya, diekstrak untuk didapatkan jumlah tiap kombinasi karakter dengan mengunakan metode kmers frequency. Nilai k yang digunakan dalam penelitian ini adalah 3, sehingga akan diperoleh jumlah kombinasi 3 karakter sebanyak 64 kombinasi. Hasil ekstraksi fitur berupa file text (.txt) yang berisi informasi jumlah tiap fitur (kombinasi) dari kombinasi AAA, AAC, AAG, sampai TTT, serta informasi identitas fragmen tersebut. Contoh format isi file ekstraksi fitur dapat dilihat pada Lampiran 2. Hasil Penentuan Nilai Centroid Awal dan Clustering Data Serangkaian uji coba dilakukan untuk mengelompokan tiga data uji fragmen metagenom yang dihasilkan dari proses ekstraksi fitur 3-mers ke dalam 3 dan 4 cluster. Jumlah iterasi clustering pada setiap uji coba dibatasi sampai maksimal 20 iterasi. Percobaan yang dilakukan menggunakan tiga personal komputer dengan spesifikasi perangkat keras seperti terlihat pada Tabel 4. Tabel 4 Spesifikasi Perangkat Keras PC Processor RAM Hard disk Operating System PC 1 Intel® Core™ i5 CPU 4 GB 300 GB Ubuntu 14.04 LTS 650@3,20GHz PC 2 Pentium®Dual Core 2 GB 150 GB Ubuntu 14.04 LTS CPU E5300 @2,60GHz PC 3 Pentium®Dual Core 2 GB 150 GB Ubuntu 14.04 LTS CPU E5300 @2,60GHz Pengujian dilakukan menggunakan dua metode algoritme yaitu K-Means dan Pillar K-Means. Pada metode Pillar K-Means, proses clustering dikerjakan setelah dilakukan penentuan centroid awal menggunakan algoritme Pillar. Kode program yang digunakan dalam penelitian ini dapat dilihat pada Lampiran 20, sedangkan contoh keluaran hasil proses clustering dapat dilihat pada Lampiran 3. Hasil pengujian dari dua metode yang digunakan, yaitu K-Means dan Pillar K-Means, menunjukkan bahwa kedua metode tersebut menghasilkan kesimpulan yang sama pada clustering 3 cluster seperti terlihat pada Gambar 6, Gambar 7 dan Gambar 8. Berdasarkan hasil dari masing-masing metode clustering, memperlihatkan bahwa genus Agrobacterium secara dominan selalu bergerombol sendiri pada satu cluster, sementara genus Bacillus dan Staphylococcus secara dominan selalu bergerombol secara bersamaan dalam cluster yang sama. Hal ini dikarenakan karena genus Bacillus dan Staphylococcus merupakan mikroorganisme yang berada pada satu ordo. Kesimpulan hasil clustering tersebut sesuai dengan kesimpulan yang diperoleh dari hasil penelitian yang dilakukan oleh Farino et al (2015). Rincian hasil jumlah fragmen metagenom tiap cluster pada data uji ke-1, data uji ke-2, dan data uji ke-3 dari serangkaian uji coba yang dilakukan dapat dilihat pada Lampiran 5, Lampiran 6, Lampiran 7, Lampiran 8, Lampiran 9, Lampiran 10, Lampiran 11, Lampiran 12, Lampiran 13, Lampiran 14, Lampiran 15, dan Lampiran 16.

15

80 Persentase

100

80 Persentase

100

60 40

60 40 20

20 0

0 Cluster 1

Agrobacterium

Cluster 2

Cluster 3

Bacillus

Cluster 1

Staphylococcus

Cluster 2

Agrobacterium

Cluster 3

Bacillus

Staphylococcus

(a) (b) Gambar 6 Clustering 10 000 fragmen pada 3 cluster dengan : (a) K-Means (b) Pillar K-Means

80

80 Persentase

100

Persentase

100

60 40

60 40 20

20 0

0 Cluster 1

Agrobacterium

Cluster 2 Bacillus

Cluster 3

Cluster 1 Agrobacterium

Staphylococcus

Cluster 2 Bacillus

Cluster 3

Staphylococcus

100

100

80

80

Persentase

Persentase

(a) (b) Gambar 7 Clustering 100 000 fragmen pada 3 cluster dengan : (a) K-Means (b) Pillar K-Means

60 40

60 40 20

20

0

0 Cluster 1 Agrobacterium

Cluster 2 Cluster 3 Bacillus Staphylococcus

Cluster 1 Agrobacterium

Cluster 2 Bacillus

Cluster 3

Staphylococcus

(a) (b) Gambar 8 Clustering 7 500 000 fragmen pada 3 cluster dengan : (a) K-Means (b) Pillar K-Means

Kesimpulan hasil clustering pada 3 cluster tidak jauh berbeda dengan clustering pada 4 cluster. Gambar 9, Gambar 10 dan Gambar 11 merupakan grafik hasil pengelompkan metagenom pada 4 cluster. Hasil clustering tetap memperlihatkan bahwa genus Agrobacterium secara dominan selalu bergerombol

16 sendiri pada satu cluster, sementara genus Bacillus dan Staphylococcus secara dominan selalu bergerombol secara bersamaan dalam cluster yang sama.

80 Persentase

100

80 Persentase

100

60 40 20

60 40 20 0

0

Cluster 1 Cluster 2 Cluster 3 Cluster 4 Agrobacterium Bacillus Staphylococcus


100

100

80

80 Persentase

Persentase

(a) (b) Gambar 9 Clustering 10 000 fragmen pada 4 cluster dengan: (a) K-Means (b) Pillar K-Means

60 40

60 40

20

20

0

0



100

100

80

80 Persentase

Persentase

(a) (b) Gambar 10 Clustering 100 000 fragmen pada 4 cluster dengan: (a) K-Means (b) Pillar K-Means

60 40 20

60 40 20

0 Cluster 1 Cluster 2 Cluster 3 Cluster 4 Agrobacterium

Bacillus

Staphylococcus

0 Cluster 1 Cluster 2 Cluster 3 Cluster 4 Agrobacterium Bacillus Staphylococcus

(a) (b) Gambar 11 Clustering 7 500 000 fragmen pada 4 cluster dengan: (a) K-Means (b) Pillar K-Means Tabel 5 dan Tabel 6 menunjukan bahwa metode Pillar K-Means memberikan performa kinerja lebih baik dan efisien dalam hal jumlah iterasi dan waktu eksekusi dalam mengelompokan data dibandingkan dengan metode KMeans. Metode Pillar K-Means mempunyai waktu eksekusi lebih cepat dibandingkan dengan metode K-Means. Demikian juga jumlah iterasi yang

17 dibutuhkan oleh metode Pillar K-Means lebih sedikit dibandingkan dengan metode K-Means. Pencatatan jumlah iterasi dan waktu eksekusi dari metode KMeans, dilakukan percobaan sebanyak 5 kali pada setiap data uji, kemudian diambil nilai rata-ratanya. Hal ini dilakukan karena hasil dari metode K-Means berbeda-beda pada setiap percobaan. Rincian detil pencatatan jumlah iterasi dan waktu eksekusi dengan menggunakan metode K-Means dapat dilihat pada Lampiran 17, Lampiran 18, dan Lampiran 19. Tabel 5 Perbandingan hasil clustering 3 cluster 10 000 Fragments1) Pengukuran Waktu inisialisasi Waktu clustering Total waktu Jumlah iterasi

K-Means

Pillar K-Means

-

2.41

43.59 43.59 15

100 000 7 500 000 1) Fragments Fragments2) KPillar Pillar K-Means Means K-Means K-Means

27.50 29.91 10

-

4.60

-

6.13

85.60 85.60 17

56.70 61.30 14

105.76 105.76 > 20

81.40 87.53 > 20

Catatan : 1) dalam satuan detik ; 2) dalam satuan menit

Tabel 6 Perbandingan hasil clustering 4 cluster 10 000 Fragments1) Pengukuran

100 000 Fragments1)

7 500 000 Fragments2)

KMeans

Pillar K-Means 3.02

KMeans

Pillar K-Means 6.09

KMeans

Pillar K-Means 10.16

Waktu clustering

57.12

30.21

121.13

81.76

171.11

119.87

Total waktu

57.12

33.23

121.13

87.85

171.11

130.03

11

> 20

17

> 20

> 20

Waktu inisialisasi

Jumlah iterasi Catatan :

1)

17

dalam satuan detik ;

2)

dalam satuan menit

Pada tahapan selanjutnya dilakukan pengujian terhadap kualitas cluster hasil clustering dengan menghitung silhouette coefficient. Nilai kualitas tiap cluster yang dihasilkan pada setiap data uji menunjukan bahwa clustering data menghasilkan kelompok data dengan kualitas yang baik, di mana setiap data tepat berada pada kelompoknya masing-masing. Hal ini bisa ditunjukan dengan nilai hasil pengujian terhadap kualitas tiap cluster yang berada pada kisaran nilai antara 0.699 sampai 0.734 seperti dapat dilihat pada Tabel 7. Namun demikian, hasil pengujian kualitas cluster pada clustering data 7 500 000 fragmen menunjukan nilai kualitas cluster lebih rendah dibandingkan dengan kualitas cluster hasil clustering data 10 000 fragmen dan 100 000 fragmen. Hal ini disebabkan clustering data pada 7 500 000 fragmen tersebut tidak selesai sampai semua titik sudah tepat pada kelompoknya masing-masing. Proses clustering berhenti pada batas maksimal iterasi yang ditetapkan, yaitu 20 iterasi. Hal tersebut masih memungkinkan hasil clustering mencapai pada kualitas cluster lebih baik jika tidak ada batasan iterasi. Contoh keluaran hasil perhitungan silhouette coefficient dapat dilihat pada Lampiran 4.

18

Tabel 7 Kualitas clustering Data Uji 10 000 Fragmen 100 000 Fragmen 7 500 000 Fragmen

Cluster 1 0.711 0.713 0.607

K-Means Cluster 2 0.701 0.714 0.611

Cluster 3 0.699 0.702 0.598

Pillar K-Means Cluster 1 Cluster 2 Cluster 3 0.717 0.734 0.721 0.720 0.733 0.712 0.621 0.638 0.616

Setelah menghasilkan kualitas cluster yang tepat, tahapan terakhir dari penelitian ini adalah melakukan perhitungan nilai speedup dengan cara membandingkan waktu eksekusi secara paralel dengan waktu eksekusi secaa sekuensial serta menghitung nilai efisiensi proses paralelisasi dengan cara membandingkan nilai speedup dengan jumlah core processor yang digunakan pada proses paralelisasi. Data uji yang digunakan dalam menghitung nilai speedup adalah data uji 10 000 fragmen. Pelaksanaan eksekusi secara sekuensial dilakukan dengan menggunakan PC1 dan tanpa menggunakan model MapReduce. Komputer PC1 dipilih untuk melakukan proses secara sekuensial karena PC1 mempunyai spesifikasi perangkat keras lebih baik dari pada komputer lainnya. Tabel 8 dan Tabel 9 menampilkan hasil nilai speedup dan nilai efisiensi pada penerapan metode K-Means dan Pillar K-Means untuk clustering pada 3 dan 4 cluster. Hasil yang diperoleh menunjukan bahwa nilai speedup pada penerapan Pillar K-Means memiliki nilai speedup lebih tinggi dibandingkan dengan nilai speedup pada penerapan K-Means. Rata-rata efisiensi yang dihasilkan dari proses paralelisasi adalah 400%. Tabel 8 Nilai speedup untuk pengujian 10 000 fragmen pada 3 cluster Algoritme K-Means Pillar K-Means

Proses Sekuansial (detik) 2,615.36 1,874.50

Pareses Paralel (detik) 43.59 29.91

Speedup 60.00 62.67

Efisiensi (%) 374.99 391.70

Tabel 9 Nilai speedup untuk pengujian 10 000 fragmen pada 4 cluster Algoritme K-Means Pillar K-Means

Proses Sekuansial (detik) 3,793.00

Paralel Paralel (detik) 57.12

2,294.01

33.23

66.40

Efisiensi (%) 415.03

69.03

431.46

Speedup

19

5 SIMPULAN DAN SARAN Simpulan Berdasarkan pada hasil pengujian dapat diambil beberapa kesimpulan sebagai berikut: 1. Hasil clustering data metagenom pada masing-masing metode yang digunakan menunjukan kesimpulan hasil yang sama, di mana secara dominan genus Agrobacterium selalu menggerombol secara bersama dalam satu cluster, sedangkan genus Bacillus and Staphylococcus secara dominan selalu bergerombol dalam cluster yang sama. 2. Jumlah iterasi dan waktu eksekusi pada penerapan Pillar K-Means dalam clustering data lebih efisien dibandingkan pada penerapan metode KMeans. Penggunaan model MapReduce memberikan speedup dan kinerja lebih 3. efisien dibandingkan dengan proses sekuensial. Nilai speedup yang dihasilkan berkisar antara 60,00 sampai 69,03 dengan nilai efisiensi ratarata sebesar 400% Saran Penentuan nilai centroid awal pada algoritme Pillar dapat menambah waktu eksekusi secara keseluruhan dalam clustering K-Means. Kekurangan algoritme Pillar tersebut dapat dijadikan celah yang bisa dilakukan dalam penelitian selanjutnya untuk mencari sebuah metode dalam menyediakan optimalisasi penentuan nilai centroid awal pada algoritme Pillar untuk clustering data.

20

DAFTAR PUSTAKA Amorim RCD, Hennig C (2015). "Recovering the number of clusters in data sets with noise features using feature rescaling factors". Information Sciences 324: 126–145.doi:10.1016/j.ins.2015.06.039 Arumugam K, Tan YS, Lee BS, Kanagasabai R. 2012. Cloud-enabling sequence alignment with hadoop mapreduce: A performance analysis. 4th International Conference on Bioinformatics and Biomedical Technology IPCBEE. 29:82-88. Barakbah AR, Kiyoki Y. 2009. A pillar algorithm for k-means optimization by distance maximization for initial centroid designation. Di dalam: 2009 IEEE Symposium on Computational Intelligence and Data Mining; 2009; . Piscataway (US): I E E E. hlm 61-68. Barney B. 2015. Introduction to parallel computing. Lawrence Livermore National Laboratory. [Diunduh 2015 Nov 05]. Tersedia pada https://computing.llnl.gov/tutorials/parallel_comp/#Models. Bhusare BB, Bansode SM. 2014. Centroids initialization for k-means clustering using improved pillar algorithm. International Journal of Advanced Research in Computer Engineering & Technology (IJARCET) . 3(4):13171322. doi:ISSN: 2278 – 1323 . Che-Lun H, Yaw-Ling L, Chen-En H, Guan-Jie H. 2012. Efficient protein structure alignment algorithms under the MapReduce framework. Cloud Computing Technology and Science (CloudCom), IEEE 4th International Conference. Dean J, Ghemawat S. 2004. Mapreduce: simpliﬁed data processing on large clusters. Di dalam: Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation; 2004 Dec 6-8; San Francisco, California, Amerika Serikat. Berkeley (US): USENIX Association Berkeley. hlm 137-150. Farino, Haryanto T, Kusuma WA. 2015. Implementasi mapreduce pada k-means untuk clustering metagenome [skripsi]. Bogor (ID): Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Glick, B.R., Pasternak, J.J., Patten, C.L. 2010. Molecular biotechnology: principles and applications of recombinant DNA (4 ed.). Washington, DC: ASM Press. pp. 117–118. Kusuma WA. 2012. Combined approaches for improving the performance of denovo DNA sequence assembly and metagenomic classification of short fragments from next generation sequencer [disertasi]. Tokyo (JP): Tokyo Institute of Technology. Khusumanegara P. 2013. Analisa pengaruh block size pada HDFS terhadap kecepatan proses mapreduce [skripsi]. Jakarta (ID): Universitas Indonesia. Overbeek MV, Kusuma WA, Buono A. 2013. Clustering metagenome fragments using growing self organizing map. Di dalam: International Conference on Advanced Computer Science and Information System (ICACSIS); 2013 Sep 28-29; Bali, Indonesia. Depok (ID): IEEE. hlm 285-289. Pekuwali R.A, Kusuma WA, Buono A. 2015. Optimasi pengekstraksi fitur spaced k-mers frekuensi menggunakan algoritme genetika pada pengklasifikasian

21 fragmen metagenome [tesis]. Bogor (ID): Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Rasheed Z, Rangwala H. 2013. A MapReduce framework for clustering metagenomes. Di dalam: HiCOMB 2013 Online Proceedings [internet]. 2013 Mei 20; Cambridge, Amerika Serikat. [tempat tidak diketahui]: IEEE. hlm 549-558; [diunduh 2015 Okt 12]. Tersedia pada http://www.hicomb.org /HiCOMB2013/papers/HICOMB2013-06.pdf. Rogers, K. 2011. New thinking about Genetics, New York: Britannica Educational Publishing, p. 132. Rousseeuw PJ. 1987. Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis. Computational and Applied Mathematics 20: 53–65. doi:10.1016/0377-0427(87)90125-7. Russell S.J, Norvig P. 2010. Artificial intelligence a modern approach. Upper Saddle River, New Jersey 07458: Pearson Education, Inc., 3 ed. Seung-Jin S, Tovchigrechko A., Craig J. 2011. Parallelizing BLAST and SOM algorithms with MapReduce-MPI library. IEEE International Parallel & Distributed Processing Symposium. Thomas T., Gilbert J., Meyer F. 2012. Metagenomics - a guide from sampling to data Analysis;[diunduh 2015 Okt 12]. Tersedia pada http://www.microbialinformaticsj.com/content/2/1/3. Wahyudin I, Djatna T, Kusuma WA. 2015. Modeling Risk Cluster Based on Sentiment Analysis in Bahasa Indonesia for SME Business Financing Risk Analysis Documents [tesis]. Bogor (ID): Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Willmore F. 2012. Introduction to parallel computing. Texas Advanced Computing Cnter, 2012 Feb.. The University of Texas at Austin. Wooley JC, Godzik A, Friedberg I. 2010. A primer on metagenomics. PLos Computational Biology. 6(2):1–13. doi: 10.1371/journal.pcbi.1000667. Wu X, Kumar V. 2009. The Top Ten Algorithms in Data Mining.Chapman and Hall. Zaki MJ, Meira W. 2014. Data mining and analysis: Fundamental concepts and algorithms. New York (US): Cambridge Pr. Zhao W, Ma H, He Q. 2009. Parallel k-means clustering based on mapreduce. Di dalam: Jaatun MG, Zhao G, Rong C, editor. CloudCom 2009, 2009 Des 14; Beijing, China. [tempat tidak diketahui]: Springer-Verlag Berlin Heidelberg. hlm 674-679. Zoubi MBA, Rawi MA. 2008. An efficient approach for computing silhouette coefficients . Journal of Computer Science . 4(3):252-255. doi:ISSN 15493636 .

22

LAMPIRAN

23

Lampiran 1 Contoh Isi File Hasil Simulasi MetaSim

Lampiran 2 Contoh Isi File Ekstraksi Fitur

24 Lampiran 3 Contoh Keluaran Hasil Clustering

Lampiran 4 Contoh keluaran perhitungan silhouette coefficient

25 Lampiran 5 Rekap clustering setiap genus dalam 3 cluster untuk tiap data uji menggunakan algoritme pillar k-means Data Uji 1

2

3

Cluster 1 2 3 1 2 3 1 2 3

Agrobacterium 17 2537 15 184 25683 112 13271 1919605 11109

Bacillus 2250 665 16 23211 7025 21273 1790993 448422 1612260

Staphylococcus 1071 16 1195 11272 165 11076 909249 13425 781

Lampiran 6 Rekap clustering setiap genus dalam 3 cluster untuk tiap data uji menggunakan algoritme k-means (percobaan ke-1) Data Uji 1

2

3

Cluster 1 2 3 1 2 3 1 2 3

Agrobacterium 2459 3 108 25705 147 126 1925300 11960 6725

Bacillus 203 2282 2663 7316 22857 21336 589175 1494986 1767514

Staphylococcus 1 1314 967 170 11947 10396 45751 985649 672941


2

3

Cluster 1 2 3 1 2 3 1 2 3

Agrobacterium 2471 5 94 25344 299 335 1888193 29549 26244

Bacillus 216 2415 2517 6562 23607 21340 545397 1533737 1772540

Staphylococcus 26 1274 982 272 11632 10608 47381 967554 689406

26 Lampiran 8 Rekap clustering setiap genus dalam 3 cluster untuk tiap data uji menggunakan algoritme k-means (percobaan ke-3) Data Uji 1

2

3

Cluster 1 2 3 1 2 3 1 2 3

Agrobacterium 2466 32 72 25464 6959 205 1884499 38685 20801

Bacillus 206 2229 2713 192 23581 12015 659021 1494986 1697818

Staphylococcus 42 1280 960 322 20969 10293 30337 957499 716505


2

3

Cluster 1 2 3 1 2 3 1 2 3

Agrobacterium 2438 25 107 25212 255 512 1915797 14580 13608

Bacillus 208 2208 2732 6815 23169 21526 544242 1531426 1776007

Staphylococcus 48 1266 968 230 11452 10831 17555 960226 726561


2

3

Cluster 1 2 3 1 2 3 1 2 3

Agrobacterium 2413 199 4 25196 455 327 1881194 36547 26244

Bacillus 58 2271 1297 6238 23977 21294 513428 1507930 1830315

Staphylococcus 99 2677 981 205 11918 10390 44483 977269 682589

27 Lampiran 11 Rekap clustering setiap genus dalam 4 cluster untuk tiap data uji menggunakan algoritme pillar k-means Data Uji 1

2

3

Cluster 1 2 3 4 1 2 3 4 1 2 3 4

Agrobacterium 0 16 2542 12 0 166 150 25662 2802 52901 1872381 15901

Bacillus 0 2232 731 2185 3 23207 21651 6648 91020 1800901 230893 1728861

Staphylococcus 5 1178 16 1084 0 11844 10510 159 14092 719202 91902 879145


2

3

Cluster 1 2 3 4 1 2 3 4 1 2 3 4

Agrobacterium 2 3 2378 187 34 11 2523 2 140 39 2330 61

Bacillus 1737 1658 86 1667 2029 2002 492 624 2006 1859 710 573

Staphylococcus 1188 1050 1 43 491 825 11 956 963 635 96 588


2

3

Cluster 1 2 3 4 1 2 3 4 1 2 3 4

Agrobacterium 3 5 2367 195 371 239 25206 161 116639 39074 1766305 21967

Bacillus 1700 1715 101 1632 20763 19290 5218 6238 1403935 1373507 556952 517280

Staphylococcus 1166 1032 21 63 5210 7929 144 9230 687190 446878 87092 483181

28 Lampiran 14 Rekap clustering setiap genus dalam 4 cluster untuk tiap data uji menggunakan algoritme k-means (percobaan ke-3) Data Uji 1

2

3

Cluster 1 2 3 4 1 2 3 4 1 2 3 4

Agrobacterium 47 82 2364 77 309 268 25336 65 25978 79898 34214 1790605

Bacillus 2061 1607 109 1371 20011 18785 4713 7999 51509 1428586 1386603 479148

Staphylococcus 1149 1045 26 63 5047 8276 245 8944 700655 478068 70219 455400


2

3

Cluster 1 2 3 4 1 2 3 4 1 2 3 4

Agrobacterium 44 77 2365 84 262 255 25414 47 136079 5443 1785550 16913

Bacillus 1807 1701 53 1587 19115 20722 5208 6464 1373507 1317658 544242 616268

Staphylococcus 1186 1009 26 61 4552 7934 540 9487 682418 476363 79252 466308


2

3

Cluster 1 2 3 4 1 2 3 4 1 2 3 4

Agrobacterium 2 11 2390 167 283 294 25336 65 83786 39074 1790799 30326

Bacillus 1801 1654 80 1613 20248 19805 4703 6753 1403935 1373507 556952 517280

Staphylococcus 1151 1024 27 79 4984 8233 144 9152 687190 446878 87092 483181

29 Lampiran 17

Waktu clustering dengan algoritme k-means untuk data uji-1 (10 000 fragmen) pada 3 cluster Ulangan 1 2 3 4 5 Rataan

Waktu Clustering 49.42 37.78 40.66 49.42 40.66 43.59

Jumlah Iterasi 17 13 14 17 14 15

Lampiran 18 Waktu clustering dengan algoritme k-means untuk data uji-2 (100 000 fragmen) pada 3 cluster Ulangan 1 2 3 4 5 Rataan



Lampiran 19 Waktu clustering dengan algoritme k-means untuk data uji-1 (10 000 fragmen) pada 4 cluster Ulangan 1 2 3 4 5 Rataan



30 Lampiran 20 Kode Program //Menghitung jarak dengn euclidian distance // public class DistanceMeasurer { public static final double measureDistance(ClusterCenter center,Vector v) { double sum = 0; int length = v.getVector().length; for (int i = 0; i < length; i++) { sum += Math.pow((center.getCenter().getVector()[i] - v.getVector()[i]),2); } sum=Math.sqrt(sum); return sum; } }

//Membaca dan menulis data ke dalam vector // import java.io.DataInput; import java.io.DataOutput; import java.io.IOException; import org.apache.hadoop.io.WritableComparable; public class ClusterCenter implements WritableComparable { private Vector center; public ClusterCenter() { super(); this.center = null; } public ClusterCenter(ClusterCenter center) { super(); this.center = new Vector(center.center); } public ClusterCenter(Vector center) { super(); this.center = center; } public boolean converged(ClusterCenter c) { return compareTo(c) == 0 ? true : false; } @Override public void write(DataOutput out) throws IOException { center.write(out); } @Override public void readFields(DataInput in) throws IOException { this.center = new Vector(); center.readFields(in); } @Override public int compareTo(ClusterCenter o) { return center.compareTo(o.getCenter());

31 } public Vector getCenter() { return center; } @Override public String toString() { return "ClusterCenter [center=" + center + "]"; } }

//Memeriksa keanggotaan tiap cluster// import java.io.DataInput; import java.io.DataOutput; import java.io.IOException; import java.util.Arrays; import org.apache.hadoop.io.WritableComparable; public class Vector implements WritableComparable{ private double[] vector; public Vector(){ super(); } public Vector(Vector v){ super(); int l= v.vector.length; this.vector= new double[l]; System.arraycopy(v.vector, 0,this.vector, 0, l); } @Override public void readFields(DataInput in) throws IOException { int size = in.readInt(); vector = new double[size]; for(int i=0;i<size;i++) vector[i]=in.readDouble(); } @Override public void write(DataOutput out) throws IOException { out.writeInt(vector.length); for(int i=0;i
32 return 0; else return 1; } public double[] getVector(){ return vector; } public void setVector(double[]vector){ this.vector=vector; } public String toString(){ return "Vector [vector=" + Arrays.toString(vector) + "]"; } }

//Mapper : menempatkan data pada cluster yang terdekat// import java.io.IOException; import java.util.LinkedList; import java.util.List; import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.fs.FileSystem; import org.apache.hadoop.fs.Path; import org.apache.hadoop.io.IntWritable; import org.apache.hadoop.io.SequenceFile; import org.apache.hadoop.mapreduce.Mapper; public class KMeansMapper extends Mapper{ List centers = new LinkedList(); @Override protected void setup(Context context) throws IOException, InterruptedException { super.setup(context); Configuration conf = context.getConfiguration(); Path centroids = new Path(conf.get("centroid.path")); FileSystem fs = FileSystem.get(conf); SequenceFile.Reader reader = new SequenceFile.Reader(fs, centroids, conf); ClusterCenter key = new ClusterCenter(); IntWritable value = new IntWritable(); while (reader.next(key,value)) { centers.add(new ClusterCenter(key)); } reader.close(); } @Override protected void map(ClusterCenter key, Vector value, Context context) throws IOException, InterruptedException { ClusterCenter nearest = null; double nearestDistance = Double.MAX_VALUE; for (ClusterCenter c : centers) {

33 double dist = DistanceMeasurer.measureDistance(c,value); if (nearest == null) { nearest = c; nearestDistance = dist; } else { if (nearestDistance > dist) { nearest = c; nearestDistance = dist; } } } context.write(nearest, value); } }

34 //Reducer : update centroid baru// import java.io.IOException; import java.util.LinkedList; import java.util.List; import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.fs.FileSystem; import org.apache.hadoop.fs.Path; import org.apache.hadoop.io.IntWritable; import org.apache.hadoop.io.SequenceFile; import org.apache.hadoop.mapreduce.Reducer; public class KMeansReducer extends Reducer{ public static enum UpdateCounter{ UPDATED } List centers = new LinkedList(); protected void reduce(ClusterCenter key, Iterable values, Context context) throws IOException, InterruptedException{ Vector newCenter = new Vector(); List vectorList = new LinkedList(); int vectorSize = key.getCenter().getVector().length; newCenter.setVector(new double[vectorSize]); for(Vector value :values){ vectorList.add(new Vector(value)); for(int i=0;i
35 //Main program// import java.io.IOException; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.fs.FileStatus; import org.apache.hadoop.fs.FileSystem; import org.apache.hadoop.fs.Path; import org.apache.hadoop.io.IntWritable; import org.apache.hadoop.io.SequenceFile; import org.apache.hadoop.mapreduce.Job; import org.apache.hadoop.mapreduce.lib.input.SequenceFileInputFormat; import org.apache.hadoop.mapreduce.lib.output.SequenceFileOutputFormat; import java.util.Random; import java.util.Scanner; import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.util.ArrayList; import java.util.Date; import java.util.StringTokenizer; import java.io.BufferedWriter; import java.io.FileWriter; import java.io.PrintWriter; import java.text.DateFormat; import java.text.SimpleDateFormat; public class KMeansClusteringJob { private static final Log LOG = LogFactory.getLog(KMeansClusteringJob.class); public static File setFile(String filePath) { File file = null; String path = System.getProperty("user.dir") + File.separatorChar + filePath; try { file = new File(path); } catch (Exception e) { e.printStackTrace(); } if (file == null) { throw new RuntimeException(); } if (!file.exists()) { try { file.createNewFile(); } catch (IOException ex) {} } return file; }

public static boolean fileWrite(String[] text, File file) { try { BufferedWriter out = new BufferedWriter(new FileWriter(file,true)); PrintWriter writeOut = new PrintWriter(out); // menulis text ke file for (int i = 0; i < text.length; i++) { writeOut.println(text[i]); } writeOut.close(); return true;

36 } catch (IOException e) { e.printStackTrace(); return false; } } public static ArrayList<String> readTeks(String bacateks, String nFile) throws FileNotFoundException, IOException { ArrayList<String> data = new ArrayList<String>(); File bacafile = new File(nFile); FileReader inputDokumen = new FileReader(bacateks + bacafile); System.out.println(bacateks + bacafile); BufferedReader bufferBaca = new BufferedReader(inputDokumen); StringBuffer content = new StringBuffer(); String barisData; while ((barisData = bufferBaca.readLine()) != null) { content.append(barisData); content.append(System.getProperty("line.separator")); data.add(barisData); } return data; } public static ArrayList<String> token(String kalimat) throws FileNotFoundException, IOException { ArrayList<String> listKata = new ArrayList<String>(); StringTokenizer token = new StringTokenizer(kalimat, ";"); while (token.hasMoreTokens()) { listKata.add(token.nextToken()); } return listKata; } public static String[][] saveToArray(ArrayList<String> IOException { String[][] data=new String[input.size()][65]; for (int i = 0; i < input.size(); i++) { ArrayList<String> item=token(input.get(i)); for (int j = 0; j < item.size(); j++) { data[i][j]=item.get(j); } } return data; }

input)

throws

FileNotFoundException,

public static void main(String[] args) throws IOException, InterruptedException, ClassNotFoundException { Scanner baca=new Scanner(System.in); int jFile; int jumCluster; String NamaFileHasil; NamaFileHasil="HasilKMeans.txt"; System.out.print("Number of Cluster = ? "); jumCluster = baca.nextInt(); System.out.print("Number of Data File = ? "); jFile = baca.nextInt(); System.out.print("Name of Result File = ? "); NamaFileHasil= baca.next(); System.out.println("Get ready....1"); int iteration = 1; int JumFile=jFile; int dimensi=64; int JumData=JumFile*100000; int nCluster=jumCluster;

37 Configuration conf = new Configuration(); //JobConf conf=new JobConf(KMeansClusteringJob.class); conf.set("num.iteration", iteration + ""); Path in = new Path("files/clustering/import/data"); Path center = new Path("files/clustering/import/center/cen.seq"); conf.set("centroid.path", center.toString()); Path out = new Path("files/clustering/depth_1"); Job job = new Job(conf); job.setJobName("KMeans Clustering"); job.setMapperClass(KMeansMapper.class); job.setReducerClass(KMeansReducer.class); job.setJarByClass(KMeansMapper.class); SequenceFileInputFormat.addInputPath(job, in); FileSystem fs = FileSystem.get(conf); if (fs.exists(out)) fs.delete(out, true); if (fs.exists(center)) fs.delete(out, true); if (fs.exists(in)) fs.delete(out, true); final SequenceFile.Writer centerWriter = SequenceFile.createWriter(fs, conf, center, ClusterCenter.class, IntWritable.class); final IntWritable value = new IntWritable(0); Random dice = new Random(); String nFolder="data/"; System.out.println("Define The First Centroid...."); String [] noFile = new String[JumFile+1]; for (int j=1; j<=JumFile;j++){ noFile[j]="NewEkstrak3Mers_" + j + ".txt"; } int bil []=new int [nCluster]; for (int i=0; i < nCluster; i++){ bil[i]= dice.nextInt(JumData); System.out.println(bil[i] + "-" + "\t"); } //Akhir pemilihan centroid awal secara acak int NoData; NoData=1; System.out.println("Reading data...."); int bil1[] = new int[dimensi]; final SequenceFile.Writer dataWriter = SequenceFile.createWriter(fs, conf, in, ClusterCenter.class, Vector.class); for (int no=1;no<=JumFile;no++){ final ArrayList<String> listData=readTeks(nFolder,noFile[no]); String[][] array2=saveToArray(listData); System.out.println("Reading data...." + noFile[no]); for (int i = 0; i < array2.length; i++) { int cent1[]= new int[dimensi]; for (int j = 0; j < dimensi; j++) { bil1[j]=Integer.parseInt(array2[i][j]); if (nCluster==1){ if (NoData==bil[0]){ cent1[j]=Integer.parseInt(array2[i][j]); } }

38 else if (nCluster==2){ if (NoData==bil[0] || NoData==bil[1]){ cent1[j]=Integer.parseInt(array2[i][j]); } } else if (nCluster==3){ if (NoData==bil[0] || NoData==bil[1] || NoData==bil[2]){ cent1[j]=Integer.parseInt(array2[i][j]); } } } if (nCluster==1){ if (NoData==bil[0]){ {centerWriter.append(new ClusterCenter(new Vector(cent1[0],cent1[1])),value);} } } else if (nCluster==2){ if (NoData==bil[0] || NoData==bil[1]){ {centerWriter.append(new ClusterCenter(new Vector(cent1[0],cent1[1])),value);} } } else if (nCluster==3){ if (NoData==bil[0] || NoData==bil[1] || NoData==bil[2]){ {centerWriter.append(new ClusterCenter(new Vector(cent1[0],cent1[1])),value);} } } NoData++; dataWriter.append(new ClusterCenter(new Vector(0,0)), new Vector(bil1[0],bil1[1])); } } centerWriter.close(); dataWriter.close(); DateFormat dateFormat = new SimpleDateFormat("yyyy/MM/dd HH:mm:ss"); Date date = new Date(); System.out.println("Waktu mulai Inisialisasi : "+ date); //Akhir bagian baca data file teks SequenceFileOutputFormat.setOutputPath(job, out); job.setInputFormatClass(SequenceFileInputFormat.class); job.setOutputFormatClass(SequenceFileOutputFormat.class); job.setOutputKeyClass(ClusterCenter.class); job.setOutputValueClass(Vector.class); job.waitForCompletion(true); long counter = job.getCounters(). findCounter(KMeansReducer.UpdateCounter.UPDATED).getValue(); iteration++; while ((counter > 0) && (iteration<21)) { conf = new Configuration(); conf.set("centroid.path", center.toString()); conf.set("num.iteration", iteration + ""); job = new Job(conf); job.setJobName("KMeans Clustering " + iteration); job.setMapperClass(KMeansMapper.class); job.setReducerClass(KMeansReducer.class);

39 job.setCombinerClass(KMeansReducer.class); job.setJarByClass(KMeansMapper.class); in = new Path("files/clustering/depth_" + (iteration - 1) + "/"); out = new Path("files/clustering/depth_" + iteration); SequenceFileInputFormat.addInputPath(job, in); if (fs.exists(out)) fs.delete(out, true); SequenceFileOutputFormat.setOutputPath(job, out); job.setInputFormatClass(SequenceFileInputFormat.class); job.setOutputFormatClass(SequenceFileOutputFormat.class); job.setOutputKeyClass(ClusterCenter.class); job.setOutputValueClass(Vector.class); job.waitForCompletion(true); iteration++; job.getCounters().findCounter(KMeansReducer.UpdateCounter.UPDATED).getValue(); } date = new Date(); System.out.println("Waktu akhir cluster : "+ date); Path result = new Path("files/clustering/depth_" + (iteration - 1) + "/"); System.out.println("Reporting data...."); FileStatus[] stati = fs.listStatus(result); for (FileStatus status : stati) { if (!status.isDir() && !status.getPath().toString().contains("/_")) { Path path = status.getPath(); LOG.info("FOUND " + path.toString()); SequenceFile.Reader reader = new SequenceFile.Reader(fs, path,conf); ClusterCenter key = new ClusterCenter(); Vector v = new Vector(); int i=0; int j=0; int NoUrut; int nomor; int grup; File file = setFile("/files/" + NamaFileHasil + "1.txt"); String[] text = new String[100000]; String kunci; kunci="x"; NoUrut=2; nomor=0; grup=1; while (reader.next(key, v)) { if (j==0){ text[i] = "1 / " + key.toString() + " / " + v.toString(); } else { text[i] = j + " / " + key.toString() + " / " + v.toString(); } if (kunci.toString().equals(key.toString())){ } else{ j++; System.out.println(j); kunci=key.toString(); } if(nomor>=100000){ file = setFile("/files/" + NamaFileHasil + NoUrut + ".txt"); nomor=1; NoUrut++; grup++;

40 } if (i>=99999){ fileWrite(text, file); i=0; } i++; nomor++; } reader.close(); } } System.out.println("Finish..."); } }

41

RIWAYAT HIDUP Penulis dilahirkan di Bogor pada tanggal 08 Juli 1971 sebagai anak ke 5 dari pasangan Drs. M. Djuhri Yasin dan Siti Hafsoh. Pendidikan Diploma ditempuh di Institut Pertanian Bogor program studi Informatika, lulus tahun 1994. Pendidikan Sarjana ditempuh di Universitas Budi Luhur Jakarta jurusan Sistem Informasi, lulus pada tahun 2002. Pada tahun 2014, penulis diterima di Program Studi Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Pascasarjana IPB. Beasiswa pendidikan pascasarjana, yaitu BPPDN diperoleh dari DIKTI. Penulis bekerja sebagai tenaga pada bagian sistem informasi di Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, IPB.

METAGENOME FRAGMENT CLUSTERING MENGGUNAKAN ALGORITME PILLAR K-MEANS SECARA PARALEL DALAM MODEL MAPREDUCE FATHURROHMAN

Recommend Documents