ANALISIS PERBANDINGAN PROSES CLUSTER MENGGUNAKAN KMEANS CLUSTERING DAN K-NEAREST NEIGHBOR PADA PENYAKIT DIABETES MELLITUS
SKRIPSI
RONNY BENEDIKTUS SIRINGORINGO 131421021
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2016
Universitas Sumatera Utara
ANALISIS PERBANDINGAN PROSES CLUSTER MENGGUNAKAN K-MEANS CLUSTERING DAN K-NEAREST NEIGHBOR PADA PENYAKIT DIABETES MELLITUS
SKRIPSI
Diajukan untuk melengkapi tugas guna memenuhi syarat mencapai gelar Sarjana Komputer
RONNY BENEDIKTUS SIRINGORINGO 131421021
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2016
Universitas Sumatera Utara
PERSETUJUAN
Judul
:ANALISIS PERBANDINGAN PROSES CLUSTER MENGGUNAKAN K-MEANS CLUSTERING DAN KNEAREST
NEIGHBOR
PADA
PENYAKIT
DIABETES MELLITUS Kategori
: SKRIPSI
Nama
: RONNY BENEDIKTUS SIRINGORINGO
Nomor Induk Mahasiswa : 131421021 Program Studi
: EKSTENSI S1 ILMU KOMPUTER
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Diluluskan di Medan, 28 Januari 2016 Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Amer Sharif. S.Si, M.Kom
Dr. Poltak Sihombing, M.Kom NIP. 1961203171991031001
Diketahui / Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
Universitas Sumatera Utara
PERNYATAAN
ANALISIS PERBANDINGAN PROSES CLUSTER MENGGUNAKAN K-MEANS CLUSTERING DAN K-NEAREST NEIGHBOR PADA PENYAKIT DIABETES MELLITUS
SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 28 Januari 2016
Ronny Benediktus Siringoringo NIM. 131421021
Universitas Sumatera Utara
PENGHARGAAN
Segala puji dan syukur Penulis ucapkan kepada Tuhan Yesus Kristus yang senantiasa melimpahkan rahmat dan karunia-Nya sehingga skripsi ini dapat diselesaikan. Ucapan terima kasih Penulis sampaikan kepada semua pihak yang telah membantu Penulis dalam menyelesaikan skripsi ini baik secara langsung maupun tidak langsung, teristimewa untuk kedua orangtua terkasih. Pada kesempatan ini penulis ingin mengucapkan terima kasih yang sebesar-besarnya kepada : 1.
Bapak Prof. Dr. Muhammad Zarlis selaku Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara.
2.
Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Program Studi S1 Ilmu Komputer Universitas Sumatera Utara.
3.
Ibu Maya Silvi Lydia, B.Sc, M.Sc selaku Sekretaris Program Studi S1 Ilmu Komputer Universitas Sumatera Utara.
4.
Bapak Dr. Poltak Sihombing, M.Kom selaku Dosen Pembimbing I yang telah memberikan bimbingan, saran dan masukan kepada penulis dalam pengerjaan skripsi ini.
5.
Bapak Amer Sharif, S.Si, M.Kom selaku Dosen Pembimbing II yang telah memberikan bimbingan, saran dan masukan kepada penulis dalam pengerjaan skripsi ini.
6.
Bapak Drs. Marihat Situmorang, M.Kom selaku Dosen Pembanding I yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.
7.
Bapak Jos Timanta Tarigan, S.Kom, M.Sc selaku Dosen Pembanding II yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.
8.
Semua dosen dan semua pegawai di Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara.
9.
Semua pihak yang terlibat langsung ataupun tidak langsung yang tidak dapat penulis ucapkan satu per satu yang telah membantu penyelesaian skripsi ini.
Universitas Sumatera Utara
Penulis menyadari bahwa skripsi ini masih terdapat kekurangan. Oleh karena itu, kepada pembaca agar kiranya memberikan kritik dan saran yang bersifat membangun demi kesempurnaan skripsi ini. Sehingga dapat bermanfaat bagi kita semuanya.
Medan, 28 Januari 2016 Penulis,
(Ronny Benediktus Siringoringo)
Universitas Sumatera Utara
ABSTRAK
Klasifikasi merupakan salah satu dari beberapa peran data mining. Pada fungsi klasifikasi, terdapat banyak algoritma yang dapat digunakan untuk mengolah Input menjadi output yang diinginkan, sehingga harus diperhatikan aspek performance dari masing-masing algoritma tersebut. Tujuan penelitian ini adalah untuk menganalisis dan membandingkan performance K-Nearest Neighbor dan K-Means Clustering dari sudut pandang akurasi dan runing time.Data sets penelitian berasal dari UCI Machine Learning Repository, yaitu: PIMA Indians Diabetes Dataset.Hasil analisis perbandingan akurasi menunjukkan bahwa nilai ke-akuratan algoritma K-Means Clustering lebih baik dengan akurasi 67.143 % dibandingkan algoritma K-Nearest Neighbor dengan akurasi 64.286 % pada implementasi terhadap data sets.sedangkan waktu proses pengujian algoritma K-Nearest Neighbor relatif lebih cepat dibandingkan dengan K-Means Clustering dimana watu pengujian K-Nearest Neighbor yaitu 0.2492 detik sedangkan K-Means Clustering yaitu 12.1285 detik.
Kata Kunci: Klasifikasi, Dataset, K-Means Clustering, K-Nearest Neighbor, runing time, Akurasi.
Universitas Sumatera Utara
COMPARATIVE ANALYSIS OF CLUSTER PROCESS USING K -MEANS CLUSTERING AND K-NEAREST NEIGHBOR DISEASE DIABETES MELLITUS
ABSTRACT
Classification is one of the few role of data mining. In the classification function, there are many algorithms that can be used to process input into the desired output, so it must be considered aspects of performance of each algorithm. The purpose of this study was to analyze and compare the performance of K-Nearest Neighbor and KMeans Clustering from the standpoint of accuracy and runing time.Data sets the research came from the UCI Machine Learning Repository, ie: PIMA Indians Diabetes Dataset.Hasil accuracy comparative analysis shows that the value to-accuracy algorithm K-Means Clustering with an accuracy better than 67 143% K-Nearest Neighbor algorithm with 64 286% accuracy in the implementation of the testing process the data sets.sedangkan time K-Nearest Neighbor algorithm is relatively faster than the K-Means Clustering where Watu testing of K-Nearest Neighbor ie 0.2492 seconds while K-Means Clustering is 12.1285 seconds.
Keywords : Classification , Dataset , K -Means Clustering , K - Nearest Neighbor , runing time , accuracy .
Universitas Sumatera Utara
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Daftar Lampiran
ii iii iv vi vii viii xi xiii xv
BAB 1 PENDAHULUAN 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan
1 2 2 3 3 3 4
BAB 2 TINJAUAN PUSTAKA 2.1 Data Mining 2.2 Proses Data Mining 2.3 Data Clustering 2.4 Clustering 2.4.1 K-Means clustering 2.4.1.1 Algoritma K-Means clustering 2.4.2 k-Nearest Neighbor 2.4.2.1 Algoritma k-Nearest Neighbor 2.5 Euclidean Distance 2.6 Centroids 2.7 Dataset 2.8 Diabetes Melitus 2.8.1 Pengertian Diabetes Melitus 2.8.2 Determinan Diabetes Melitus
6 10 13 13 14 15 17 18 21 21 21 21 22 22
BAB 3 ANALISIS DAN PERANCANGAN SISTEM 3.1 Pengumpulan Data Pelatihan 3.2 Proses Training pada Algoritma k-means Clustering 3.2.1 Menentukan jumlah cluster dan nilai Centroids 3.2.2 Menentukan jumlah Euclidean distance 3.2.3 Proses perpindahan centroids
23 25 25 26 30
Universitas Sumatera Utara
3.3 Proses Training pada Algoritma k-nearest neighbor 3.3.1 Proses perhitungan similarity function pada algoritma k-nearest neighbor 3.4 Struktur Tabel 3.5 Perancangan Sistem 3.5.1 Diagram Konteks 3.5.2 Data Flow Diagram 3.5.3 Data Flow Diagram level 2 3.5.4 Entity Relation Diagram 3.6 Flowchart 3.7 Perancangan User Interface 3.7.1 Perancangan Admin Interface Input (Pemasukan) Data 3.7.2 Perancangan Admin Interface Outnput(Keluaran) BAB 4 IMPLEMENTASI DAN PENGUJIAN 4.1 Pengertian Implementasi Sistem 4.2 Komponen utama dalam Implementasi Sistem 4.2.1 Perangkat Keras (Hardware) 4.2.2 Perangkat Lunak (Software) 4.2.3 Unsur Manusia (Brainware) 4.3 Tampilan Program 4.3.1 Tampilan Import Data 4.3.2 Halaman Data Sampel Dibetes 4.3.3 Halaman Input Data Atribut 4.3.4 Halaman Data Atribut 4.3.5 Halaman Input nilai acak centroid 4.3.6 Halaman Hasil Clustering K-Means 4.3.6.1 Halaman Hasil Clustering K-Means dengan hasil diabetes negatif dan positif 4.3.7 Halaman Input data baru dan nilai limit 4.3.8 Halaman Hasil Clustering KNN 4.3.8.1 Halaman Hasil Clustering KNN dengan hasil diabetes negatif dan positif
31 31 38 45 45 46 47 49 51 54 54 60 69 69 69 70 70 71 71 71 72 73 74 75 76 77 78 79
BAB 5 KESIMPULAN DAN SARAN 5.1 Kesimpulan 5.2 Saran
80 80
Daftar Pustaka
81
Universitas Sumatera Utara
DAFTAR TABEL
Halaman Tabel 3.1 Tabel 3.2 Tabel 3.3 Tabel 3.4 Tabel Tabel Tabel Tabel Tabel
3.5 3.6 3.7 3.8 3.9
Tabel Tabel Tabel Tabel Tabel Tabel Tabel Tabel Tabel Tabel Tabel Tabel Tabel
3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 3.21 3.22
Tabel karakterisik pada masing-masing kolom dalam PIMA Indians dataset Tabel nilai centroids yang akan digunakan Tabel nilai sample Tabel Hasil Perhitungan Euclidean Distance Terhadap Centroids pada Sample Tabel Hasil Pergeseran centroids Tabel nilai Data Testing yang akan digunakan Tabel nilai Nilai data testing Tabel Nilai Similarity Function Pada Sample Tabel Mengurutkan Objek ke dalam Kelompok ke Jarak Euclid Terkecil Tabel Label classY Tabel Hasil Akhir Mayoritas Kategori Tabel akumulasi_jarak Tabel akumulasi_jarak2 Tabel akumulasi_knn Tabel Tabel atribut Tabel Tabel iterasi Tabel jarak Tabel jarak_knn Tabel nilai_acak Tabel nilai_acak2 Tabel sampel Tabel testing
24 26 27 29 31 32 32 34 35 36 37 38 39 39 40 40 41 41 42 43 43 44
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman Gambar Gambar Gambar Gambar Gambar Gambar Gambar Gambar
2.1 2.2 2.3 2.4 3.1 3.2 3.3 3.4
Gambar Gambar Gambar Gambar Gambar Gambar Gambar Gambar Gambar Gambar Gambar Gambar Gambar Gambar Gambar
3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19
Gambar Gambar Gambar Gambar Gambar Gambar Gambar
4.1 4.2 4.3 4.4 4.5 4.6 4.7
Gambar 4.8 Gambar 4.9 Gambar 4.10
Tahapan KDD pada Data Mining Flowchart Algoritma Metode k-Means Clustering Ilustrasi Kedekatan Kasus Pasien Flowchart Algoritma k-nearest neighbor Diagram Konteks Data Flow Diagram DFD Level 2 olah data atribut DFD Level 2 Proses Clustering sampel dengan KNN DFD Level 2 proses clustering dengan K-Means Entity Relation Diagram Flowchart Menu Flowchrt K-Means Flowchart KNN Import Data Sampel Diabetes Perancangan Input Nilai Data Baru dan Nilai Limit Perancangan Input Nilai Data Centroid 1 dan Data Centroid 2 Perancangan Form Atribut Perancangan Output Sampel Diabetes Perancangan Output Data Atribut Perancangan Tampilan KNN Perancangan tampilan Hasil clustering KNN Positif dan Negatif Perancangan Tampilan K-Means Perancangan tampilan Hasil clustering K-Means Positif dan Negatif Tampilan Import Data Halaman Data Sampel Diabetes Input Data Atribut Input Data Bobot Halaman Input nilai acak centroid Halaman Hasil Clustering K-Means Halaman Hasil Clustering K-Means dengan hasil diabetes Negati dan positif Halaman Input data baru dan nilai limit Halaman Hasil Clustering KNN Halaman Hasil Clustering KNN dengan hasil diabetes Positif dan Negatif
11 16 19 20 45 47 48 48 49 50 51 52 53 54 55 57 59 61 62 63 64 66 67 71 72 73 74 75 76 77 77 78 79
Universitas Sumatera Utara
DAFTAR LAMPIRAN
Halaman A B C
Tabel Dataset Listing Program Daftar Riwayat Hidup
A-1 B-1 C-1
Universitas Sumatera Utara
