IMPLEMENTASI GABUNGAN METODE HIERARCHY DAN ALGORITMA K-MEANS DALAM CLUSTER DOKUMEN BERITA
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Oleh : Marisa Dyah Anggraini NIM. 201010370311064
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2015
LEMBAR PERSETUJUAN
IMPLEMENTASI GABUNGAN METODE HIERARCHY DAN ALGORITMA K-MEANS DALAM CLUSTER DOKUMEN BERITA
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Menyetujui Pembimbing I
Pembimbing II
Yuda Munarko, S.Kom., M.Sc. NIDN: 0706077902
Yufis Azhar, M.Kom. NIDN: 0728088701
LEMBAR PENGESAHAN IMPLEMENTASI GABUNGAN METODE HIERARCHY DAN ALGORITMA K-MEANS DALAM CLUSTER DOKUMEN BERITA
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Disusun Oleh: Marisa Dyah Anggraini NIM. 201010370311064
Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal 16 Januari 2015 Menyetujui, Penguji I
Penguji II
Galih Wasis Wicaksono, S.Kom, M.Cs NIDN: 0723028801
Agus Eko Minarno, M.Kom NIDN : 0729118203
Mengetahui, Ketua Jurusan Teknik Informatika
Yuda Munarko, S.Kom., M.Sc. NIDN: 0706077902
LEMBAR PERNYATAAN Yang bertanda tangan di bawah ini: NAMA
: MARISA DYAH ANGGRAINI
NIM
: 201010370311064
FAK. / JUR.
: TEKNIK / TEKNIK INFORMATIKA
Dengan
ini
saya
“IMPLEMENTASI
menyatakan
bahwa
GABUNGAN
Tugas
METODE
Akhir
dengan
HIERARCHY
judul DAN
ALGORITMA K-MEANS DALAM CLUSTER DOKUMEN BERITA” beserta seluruh isinya adalah karya saya sendiri dan bukan merupakan karya tulis orang lain, baik sebagian maupun seluruhnya, kecuali dalam bentuk kutipan yang telah disebutkan sumbernya. Demikian surat pernyataan ini saya buat dengan sebenar-benarnya. Apabila kemudian ditemukan adanya pelanggaran terhadap etika keilmuan dalam karya saya ini, atau ada klaim dari pihak lain terhadap keaslian karya saya ini maka saya siap menanggung segala bentuk resiko/sanksi yang berlaku.
Mengetahui, Dosen Pembimbing
Malang, 9 Januari 2015 Yang Membuat Pernyataan
Yuda Munarko, S.Kom., M.Sc. NIDN: 0706077902
Marisa Dyah Anggraini NIM: 201010370311064
KATA PENGANTAR Dengan mengucap puji dan syukur kehadirat Allah SWT, karena atas ridho dan hidayah-Nya, sehingga penulis dapat menyelesaikan Tugas Akhir dengan judul
IMPLEMENTASI
GABUNGAN
METODE
HIERARCHY
DAN
ALGORITMA K-MEANS DALAM CLUSTER DOKUMEN BERITA, untuk memenuhi persyaratan kelulusan program studi Strata 1 pada jurusan Teknik Informatika di Univeristas Muhammadiyah Malang. Selain itu penulis juga dapat mencoba menerapkan dan membandingkan pengetahuan dan keterampilan yang diperoleh di bangku kuliah dengan kenyataan yang ada di lingkungan kerja. Penulis merasa bahwa dalam menyusun laporan ini masih menemui beberapa kesulitan dan hambatan di samping itu juga menyadari bahwa penulisan laporan ini masih jauh dari sempurna dan masih banyak kekurangan lainnya, maka dari itu penulis mengharapkan saran dan kritik yang membangun dari semua pihak.
Malang. 9 Januari 2015
Penulis
iv
DAFTAR ISI HALAMAN JUDUL LEMBAR PERSETUJUAN LEMBAR PENGESAHAN LEMBAR PERNYATAAN KEASLIAN ABSTRAK ....................................................................................................... i ABSTRACT ..................................................................................................... ii LEMBAR PERSEMBAHAN ....................................................................... iii KATA PENGANTAR ................................................................................... iv DAFTAR ISI ................................................................................................... v DAFTAR GAMBAR .................................................................................... vii DAFTAR TABEL ........................................................................................ viii DAFTAR GRAFIK ........................................................................................ ix BAB I : PENDAHULUAN 1.1 Latar Belakang .......................................................................................... 1 1.2 Rumusan Masalah ..................................................................................... 2 1.3 Tujuan Penelitian ...................................................................................... 2 1.4 Batasan Masalah......................................................................................... 3 1.5 Metodologi ................................................................................................ 3 1.5.1. Studi Pustaka .................................................................................. 3 1.5.2. Analisis Kebutuhan ......................................................................... 3 1.5.3. Perancangan Sistem ........................................................................ 4 1.5.4. Implementasi Program .................................................................... 4 1.5.5. Pengujian Sistem ............................................................................ 4 1.5.6. Penyusunan Laporan ....................................................................... 5 1.6 Sistematika Penulisan................................................................................. 5 BAB II : LANDASAN TEORI 2.1 Knowledge Discovery in Database (KDD) ............................................... 7 2.2 Clustering .................................................................................................. 9 2.3 Metode Hierarchy .................................................................................... 10 2.4 Centroid Linkage Hierarchy Method (CLHM) ........................................13 2.5 Metode K-Means ..................................................................................... 14 v
2.6 PHP (Hypertext Preprocessor) ............................................................... 15 2.7 MySQL .................................................................................................... 17 2.8 Unified Modeling Language (UML) ....................................................... 19 BAB III : ANALISIS DAN PERANCANGAN SISTEM 3.1 Analisis Kebutuhan Perangkat Lunak ......................................................22 3.1.1 Metode Analisis ............................................................................ 22 3.1.2 Hasil Analisis ................................................................................ 22 3.1.2.1 Analisis Kebutuhan Proses ............................................... 22 3.1.2.2 Analisis Kebutuhan Masukan ........................................... 23 3.1.2.3 Analisis Kebutuhan Keluaran ........................................... 23 3.1.2.4 Data Penelitian .................................................................. 23 3.1.3 Kebutuhan Antar Muka ................................................................ 25 3.1.4 Analisis Kebutuhan Perangkat Lunak .......................................... 26 3.1.5 Analisis Kebutuhan Minimum Perangkat Keras .......................... 26 3.2 Perancangan Perangkat Lunak ................................................................ 27 Metode Perancangan ............................................................................ 27 Hasil Perancangan ............................................................................... 27 BAB IV : IMPLEMENTASI DAN PENGUJIAN 4.1 Implementasi Perangkat Lunak ............................................................... 35 4.1.1. Batasan Implementasi ................................................................... 35 4.1.2. Implementasi Metode Hierarchy .................................................. 35 4.1.3. Implementasi Metode K-Means ................................................... 46 4.1.4. Implementasi Antar Muka ............................................................ 49 4.2 Pengujian Perangkat Lunak ............................................................ 53 4.2.1. Pengujian Fitur Perangkat Lunak ................................................. 53 4.2.2. Pengujian Performansi Algoritma ................................................ 54 BAB V : PENUTUP 5.1 Kesimpulan ...............................................................................................56 5.2 Saran ........................................................................................................ 56 DAFTAR PUSTAKA .................................................................................... 57 LAMPIRAN .................................................................................................. 59 BIOGRAFI PENULIS .................................................................................. 63 vi
DAFTAR GAMBAR Gambar 2.1 Tahapan Knowledge Discovery in Database (KDD) ...................7 Gambar 2.2 Hierarchy Clustering...................................................................11 Gambar 2.3 Agglomerative ............................................................................12 Gambar 2.4 Teknik-teknik dalam analisis cluster...........................................12 Gambar 2.5 Ilustrasi Algoritma Centroid Linkage Hierarchy Method ..........14 Gambar 2.6 Hubungan komponen-komponen PHP ...................................... 16 Gambar 2.7 Hubungan dari ketiga komponen utama dari halaman web dinamis ...................................................................................... 16 Gambar 3.1 Use Case diagram aplikasi ........................................................ 28 Gambar 3.2 Activity diagram tambah dokumen ............................................ 31 Gambar 3.3 Activity diagram edit dokumen ................................................. 31 Gambar 3.4 Activity diagram hapus dokumen .............................................. 31 Gambar 3.5 Activity diagram klasterisasi dokumen ...................................... 32 Gambar 3.6 Sequence diagram ..................................................................... 32 Gambar 3.7 DFD Level 0 .............................................................................. 33 Gambar 3.8 DFD Level 1 .............................................................................. 33 Gambar 3.9 Flowchart .................................................................................. 34 Gambar 3.10 Halaman Utama ....................................................................... 34 Gambar 4.1 Dendogram ................................................................................ 46 Gambar 4.2 Halaman Utama ......................................................................... 50 Gambar 4.3 Proses manipulasi konten .......................................................... 50 Gambar 4.4 Tampilan untuk menambah dokumen berita ............................. 50 Gambar 4.5 Tampilan edit dokumen berita ................................................... 51 Gambar 4.6 Tampilan setelah proses cluster dokumen ................................ 51 Gambar 4.7 Tampilan nilai centroid di setiap cluster .................................... 52 Gambar 4.8 Tampilan isi dari cluster............................................................. 52 Gambar 4.12 Tampilan bantuan untuk user .................................................. 53
vii
DAFTAR TABEL Tabel 3.1 List Keywords untuk Metadata .......................................................24 Tabel 3.2 Deskripsi Aktor ............................................................................. 28 Tabel 3.3 Deskripsi Use Case Deskripsi Use Case ....................................... 28 Tabel 3.4 Use Case Manage Dokumen ......................................................... 29 Tabel 3.5 Use Case Tambah Dokumen ......................................................... 29 Tabel 3.6 Use Case Edit Dokumen ............................................................... 29 Tabel 3.7 Use Case Hapus Dokumen .......................................................... 30 Tabel 3.8 Use Case Klasterisasi Dokumen ................................................... 30 Tabel 4.1 tabel tf.idf ...................................................................................... 36 Tabel 4.2 Iterasi 1 .......................................................................................... 41 Tabel 4.3 Agglomeration Schedule ............................................................... 41 Tabel 4.4 Nilai term cluster 4,5 .................................................................... 42 Tabel 4.5 Iterasi 2 .......................................................................................... 44 Tabel 4.6 Agglomeration Schedule ............................................................... 44 Tabel 4.7 Nilai term cluster 1,2,4,5 .............................................................. 44 Tabel 4.8 Iterasi 3 .......................................................................................... 45 Tabel 4.9 Agglomeration Schedule ............................................................... 45 Tabel 4.10 Tabel nilai centroid ..................................................................... 46 Tabel 4.11 Nilai centroid metode K-Means .................................................. 47 Tabel 4.12 Pengujian fitur pada perangkat lunak .......................................... 53 Tabel 4.13 Perhitungan akurasi ..................................................................... 54 Tabel 4.14 Perhitungan rata-rata prosentase akurasi ..................................... 55
viii
DAFTAR GRAFIK
Grafik 3.1 Frekuensi Keyword ..................................................................... 25
ix
DAFTAR PUSTAKA Andayani, Sri. 2007. Pembentukan cluster dalam Knowledge Discovery in Database dengan Algoritma K-Means. FMIPA. UNY: Yogyakarta. [Online]. Tersedia: http://staff.uny.ac.id/sites/default/files/Pembentukan%20cluster%20dlm%20 KDD%20dgn%20Algoritma%20kmeans.pdf [Diakses 18 Januari 2014, 18:37] Andre, Petrus. 2013. Konsep Dasar Belajar Bahasa Pemrograman PHP. [Online]. Tersedia: http://www.andre.web.id/2013/10/belajar-php.html [Diakses 16 April 2014, 13:16] Damayanti, Nadia, Mubtadi’i, Nur Rosyid, dan Helen, Afrida. Temu Kembali Informasi Berdasarkan Lokasi pada Dokumen yang Dikelompokkan Menggunakan Metode Centroid Linkage Hierarchy. [Online]. Tersedia: http://repo.eepis-its.edu/1115/1/7407040059.pdf [Diakses 18 Januari 2014, 14:31] Eldira, Hervilorra. Web Mining untuk Pencarian Dokumen Bahasa Inggris menggunakan Hill Climbing Automatic Cluster. [Online]. Tersedia: http://repo.eepis-its.edu/733/1/1011.pdf [Diakses 18 Januari 2014, 14:23] Hong, K. 2013. PHP & MYSQL TUTORIAL-REQUEST 2013. [Online]. Tersedia: http://www.bogotobogo.com/php/php1.php [Diakses 16 April 2014, 12:59] Karanjkar, Sushrut. 1998. Hierarchical Clustering. [Online]. Tersedia: http://www-users.cs.umn.edu/~sushrut/research/pub/cover/node24.html [Diakses 16 April 2014, 12:48] Laboratorium Data Mining Jurusan Teknik Industri Fakultas Teknologi Industri Universitas Islam Indonesia. 2014. Modul II CLUSTERING. [Online]. Tersedia: http://www.ss354.com/wp-content/uploads/2014/03/Data-MiningModul-Clustering-Modul-Clustering.pdf [Diakses 18 Januari 2014, 18:40] Minartiningtyas, Brigida Arie. 2013. Pengertian UML. [Online]. Tersedia: http://informatika.web.id/pengertian-uml.htm [Diakses 18 April 2014, 19:40] Pasaribu, Manaek Y.D. 2008. Analisa dan Implementasi Metode Hidden Markov Model pada Intrusion Detection System (IDS). [Online]. Tersedia: http://digilib.ittelkom.ac.id/index.php?option=com_content&view=article&i 10
d=210:kdd&catid=20:informatika&Itemid=14 [Diakses 18 Maret 2014, 18:29] Prasetyo, Eko. 2012. DATA MINING-Konsep dan Aplikasi Menggunakan MATLAB. Yogyakarta: ANDI Prasetyo, Wahid Budi. 2013. Definisi dan Fungsi Mysql, Apache dan PHP. [Online]. Tersedia: http://comput-techno.blogspot.com/2013/01/definisidan-fungsi-mysql-apache-dan-php.html [Diakses 16 April 2014, 13:18] Rahmawati, Lina, Abadyo, dan Lestari, Trianingsih Eni. Analisis Kelompok dengan Menggunakan Metode Hierarki untuk Pengelompokan Kabupaten/Kota di Jawa Timur Berdasarkan Indikator Kesehatan. [Online]. Tersedia: http://jurnalonline.um.ac.id/data/artikel/artikel1768E9E20B8E53209B2AAE90144ED6 6D.pdf [Diakses 16 April 2014, 12:51] Santosa, Budi. 2007. Data Mining Teknik Pemanfaatan Data untuk Keperluan Bisnis, First Edition ed. Yogyakarta: Graha Ilmu Universitas Kristen Duta Wacana. Analisis Cluster. [Online]. Tersedia: http://lecturer.ukdw.ac.id/budsus/pdf/textwebmining/clustering.pdf [Didownload 19 Januari 2014, 08:09] Wibowo, Aan Tri. 2013. Pembuatan Aplikasi E-Commerce Pusat Oleh-Oleh Khas Pacitan pada Toko Sari Rasa Pacitan. [Online]. Tersedia: http://journal.ijns.org/index.php/ijns/article/view/47/46 [Diakses 16 April 2014, 13:09]
11
58
