METODE HIERARCHICAL K-MEANS UNTUK PENGELOMPOKAN DESA TERTINGGAL DIPROVINSI SUMATERA UTARA
SKRIPSI NANIEK BJ MATANARI 101402019
PROGRAM STUDI S1 TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
METODE HIERARCHICAL K-MEANS UNTUK PENGELOMPOKAN DESA TERTINGGAL DIPROVINSI SUMATERA UTARA SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Teknologi Informasi
NANIEK BJ MATANARI 101402019
PROGRAM STUDI S1 TEKNOLOGI INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
ii PERSETUJUAN
Judul
: METODE HIERARCHICAL K-MEANS UNTUK PENGELOMPOKAN DESA TERTINGGAL DI PROVINSI SUMATERA UTARA
Kategori
: SKRIPSI
Nama
: NANIEK BJ MATANARI
NomorIndukMahasiswa
: 101402019
Program Studi
: S1 TEKNOLOGI INFORMASI
Departemen
: TEKNOLOGI INFORMASI
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Dedy Arisandi, S.T., M.Kom NIP19790831200912 1 002
Dr. Syahril Efendi, S.Si.M.IT NIP 19671110 199602 1 001
Diketahui/Disetujui oleh Program Studi S1 TeknologiInformasi Ketua,
Muhammad Anggia Muchtar NIP 19800110 200801 1 010
Universitas Sumatera Utara
iii
PERNYATAAN
METODE HIERARCHICAL K-MEANSUNTUK PENGELOMPOKAN DESA TERTINGGAL DIPROVINSI SUMATERA UTARA
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.
Medan, 23 Mei 2015
Naniek BJ Matanari 101402019
Universitas Sumatera Utara
iv UCAPAN TERIMA KASIH
Puji dan syukur penulis sampaikan kehadirat Tuhan Yang Maha Esa atas berkat dan rahmat yang telah diberikan sehingga penulis dapat menyelesaikan skripsi ini sebagai syarat untuk memperoleh gelar Sarjana Teknologi Informasi Universitas Sumatera Utara. Penulis mengucapkan banyak terimakasih kepada Bapak Dr. Syahril Efendi, S.Si., M.IT selaku dosen pembimbing pertama dan Bapak Dedy Arisandi, S.T., M.Kom selaku dosen pembimbing kedua yang telah membimbing, memberi kritik dan saran kepada penulis selama proses penelitian serta penulisan skripsi. Tanpa inspirasi serta motivasi dari kedua dosen pembimbing, tentunya penulis tidak akan mampu menyelesaikan skripsi ini. Penulis juga mengucapkan terimakasih kepada Ibu Sarah Purnamawati, ST., M.Sc. selaku dosen pembanding pertama dan Bapak Seniman, S.Kom., M.Kom. sebagai dosen pembanding kedua yang telah membantu memberikan kritik dan saran yang membantu penulis dalam pengerjaan skripsi ini. Ucapan terimakasih juga penulis tujukan pada semua dosen, pegawai serta staff pada program studi S1 Teknologi Informasi yang telah membantu dan membimbing penulis selama proses perkuliahan. Penulis juga berterimakasih terutama kepada kedua orang tua penulis, Bapak Asi Matanari serta Ibu Dameria Siringoringo yang telah membesarkan penulis dengan sabar dan penuh kasih sayang. Penulis juga berterimakasih kepada adik-adik penulis Try Loren Matanari, Pascal S.H Matanaridan Daniel S Matanari serta seluruh anggota keluarga penulis yang namanya tidak dapat disebutkan satu per satu. Terimakasih juga penulis ucapkan kepada senior-senior serta junior-junior Terknologi Informasi di Universitas Sumatera Utara. Secara khusus, penulis juga mengucapkan terimakasih juga kepada sahabat penulis Siti Moriza Tania, Imerlyn A. Silitonga S.K.M., Ossy Memorial S.Sos., Maria Elisabeth, Laura Chandra, Febrina Grace Ivone M, temanteman Scarlet serta seluruh teman-teman angkatan 2010 Teknologi Informasi yang telah membantu dan bersama-sama dengan penulis melewati seluruh proses perkuliahan di Universitas Sumatera Utara ini.
Universitas Sumatera Utara
v
ABSTRAK
Salah satu masalah utama saat ini baik di negara-negara miskin, berkembang, maupun di negara-negara maju adalah kemiskinan. Kemiskinan merupakan awal dari timbulnya masalah-masalah social lainnya yang terkait erat dengan kualitas pendidikan, kriminalitas, kelaparan, dan sebagainya yang secara tidak langsung akan mengganggu ketahanan atau stabilitas negara. Beragam kebijakan pemerintah terkait dengan kemiskinan tentunya akan efektif jika kebijakan tepat mengarah pada faktor-faktor yang mempengaruhi kemiskinan itu sendiri. Sehingga akan dapat dirumuskan alternative kebijakan pengentasan kemiskinan yang lebih intensif dan tepat sasaran. Oleh sebab itu dilakukan pengelompokan desa dengan menggunakan algoritma hierarchical clustering dan k-means yang mampu mengolah data dan membangun model secara efisien dengan jumlah data yang besar. Variabel input untuk pengelompokkan desa tertinggal meliputi jarak kantor kepala desa terhadap kantor bupati, rasio jumlah sarana pendidikan per 100 penduduk, rasio jumlah sarana kesehatan per 100 penduduk, rasio jumlah tenaga kesehatan per 100 penduduk, jumlah minimarket, persentase keluarga pertanian, persentase keluarga pengguna listrik, persentase keluarga yang tinggal dibantaran sungai, dan rasio penderita gizi buruk per 1000 penduduk. Dari sistem yang dibangun diperlukan waktu ± 2 menit untuk proses iterasi centroid dan jarak clusternya untuk clustering 5797 data desa. Yang mana hasil yang diperoleh dengan penggunaan 5 cluster adalah kelompok desa paling banyak berada di cluster 3 dengan banyak desa 4443 desa, kemudian diikuti oleh cluster 1 sebanyak 1264 desa, cluster 4 sebanyak 62 desa, kemudian cluster 2 dan 5 sebanyak 14 desa.
Kata Kunci— clustering, algoritma k-means, hierarhical, pengelompokan, desa tertinggal, data mining.
Universitas Sumatera Utara
vi HIERARCHICAL K-MEANS METHODTO CLASSIFYTHE UNDERDEVELOPED VILLAGESINTHE PROVINCEOF NORTH SUMATERA
ABSTRACT
One of the main problem in poor, developing and even developed countries nowadays is poverty. Poverty is the root to all other social problems related to education quality, crimes, famine, etc, which will indirectly affect the national resilience or stability. Various government policies related to the poverty will surely become more effective if those policies are aiming directly at the cause of the poverty itself, so that government could find a more intensive and 'right on target' alternative to alleviate poverty. Therefore, groupings were done using Hierarchical Clustering and K-Means algorithm which are able to process data and construct model efficiently even with a large amount of data. Input variable for underdeveloped village grouping includes the distance between village chief's office and regent's office, ratio of educational facilities per 100 residents, ratio of health facilities per 100 residents, ratio of health professionals per 100 residents, number of minimarket built, farmer household percentage, power user household percentage, percentage of household which live on riverbanks, and ratio of malnutrition per 1000 residents. Built system needs approximately 2 minutes for centroid iteration process and the cluster distance for 5797 village data clustering. Result gained using 5 clusters is most village were in the cluster 3 with 4443 villages, followed by cluster 1 with 1264 villages, cluster 4 with 62 villages, then cluster 2 and 5 both with 14 villages.
Keywords - clustering, algorithm, k-means, hierarchical, grouping, underdeveloped village, data mining. DAFTAR ISI
Persetujuan
Hal. ii
Pernyataan
iii
Ucapan Terima Kasih
iv
Universitas Sumatera Utara
vii Abstrak
v
Abstract
vi
Daftar Isi
vi
Daftar Tabel
ix
Daftar Gambar
xii
BAB 1 Pendahuluan 1.1 Latar Belakang
1
1.2 Rumusan Masalah
3
1.3 Tujuan Penelitian
4
1.4 Ruang Lingkup Penelitian
4
1.5 Manfaat Penelitian
4
1.6 Metodologi Penelitian
5
1.7 Sistematika Penulisan
6
BAB 2 Landasan Teori
7
2.1 Daerah Tertinggal
7
2.2 Penambangan Data (Data Mining)
8
2.2.1. Tahapan Data Mining
9
2.2.2.Pengelompokkan Data Mining
11
2.3 Clustering
12
2.3.1.Ukuran Kedekatan (Proximity)
13
2.4 Hierarhical Clustering
15
2.5Algoritma K-Means
17
2.6 Penelitian Terdahulu
18
BAB 3 Analisis dan Perancangan Sistem
21
3.1 Data yang Digunakan
21
3.2Pemrosesan Data
22
3.3 Uji Coba Algoritma Hierachical dan K-Means
22
3.4 Analisis Sistem
54
BAB 4 Implementasi dan Pengujian Sistem
57
4.1 Implementasi Sistem
57
4.1.1. Spesifikasi Perangkat Keras dan Lunak yang Digunakan
57
Universitas Sumatera Utara
viii 4.1.2. Implementasi Perancangan Antarmuka
4.2 Pengujian Sistem
57
71
4.2.1. Rencana Pengujian Sistem
71
4.2.2. Kasus dan Hasil Pengujian Sistem
72
BAB 5 Kesimpulan dan Saran
75
5.1 Kesimpulan
75
5.2 Saran
76
Daftar Pustaka
77
Universitas Sumatera Utara
ix
DAFTAR TABEL
Hal. Tabel 2.1. Penelitian Terdahulu
19
Tabel 3.1. Pemberian Nama Cluster Pada Masing - Masing Data
25
Tabel 3.2. Matrik Perhitungan Jarak Cluster
31
Tabel 3.3. Matrik Perhitungan Jarak Cluster L(C0) = 0 dan m = 0
32
Tabel 3.4. Matrik Perhitungan Jarak Cluster L(C0/C1) =0.50 dan m = 1
32
Tabel 3.5. Matrik Perhitungan Jarak Cluster L(C3/ C4) = 1.30 dan m = 2
32
Tabel 3.6. Matrik Perhitungan Jarak Cluster L(C2/C3/ C4) = 2.07 dan m = 3
33
Tabel 3.7 Matrik Perhitungan Jarak Cluster L(C0/C1/C2/C3/ C4) = 0.74 dan m = 4
33
Tabel 3.8 Matrik Perhitungan Jarak Cluster L(C0/C1/C2/C3/ C4/ C5796) = 2.21 dan m = 5
33
Tabel 3.9 Anggota Cluster Baru yang Dibentuk
35
Tabel 3.10 Hasil Centroid Awal Masing – Masing Cluster
37
Tabel 3.11 Hasil Penghitungan Jarak Cluster Dengan Centroidnya
40
Tabel 3.12 Anggota Data Awal Masing-Masing Cluster
40
Tabel 3.13 Anggota Cluster Baru yang Dibentuk
41
Universitas Sumatera Utara
x Tabel 3.14 Hasil Centroid Baru Masing – Masing Cluster
43
Tabel 3.15 Hasil Penghitungan Jarak Cluster Dengan Centroidnya Pada Pengulangan I
46
Tabel 3.16 Anggota Data Baru Masing-Masing Cluster Pada Pengulangan I
47
Tabel 3.17 Anggota Cluster baru yang dibentuk
47
Tabel 3.18 Hasil Centroid Baru Masing – Masing Cluster SetelahPengulangan II
49
Tabel 3.19 Hasil Penghitungan Jarak Cluster Dengan Centroidnya Pada Pengulangan II
52
Tabel 3.20 Anggota Data Baru Masing-Masing Cluster Pada Pengulangan II
53
Tabel 3.21 Hasil Akhir Proses Clustering
53
Tabel 4.1. Perhitungan Total Jarak Cluster Terhadap Centroidnya
67
Tabel 4.2. Perhitungan Jarak Rata-Rata Cluster
67
Tabel 4.3. Perhitungan Jarak Rata-Rata Cluster Terhadap Jumlah Rata-Rata
68
Tabel 4.4. Total JarakCluster Terhadap Semua Parameter
68
Tabel 4.5. Rencana Pengujian
71
Tabel 4.6. Hasil Pengujian
72
Universitas Sumatera Utara
xi
DAFTAR GAMBAR
Hal. Gambar 2.1.BidangIlmu Data Mining (Pramudiono, 2006)
9
Gambar 2.2.Tahapan Data Mining (Fayyad, 1996)
11
Gambar 2.3. Dendogram Penggromboloan Berhierarki Dengan Prosedur Agglomerative Dan Divisive (Izenman, 2008)
15
Gambar 2.4. Ilustrasi Prosedur Linkage dari Dua Cluster (Izenman, 2008)
17
Gambar 3.1. Print Screen Data Podes Sumatera Utara Tahun 2011
22
Gambar 3.2. Flowchart Algoritma Hierarchical Clustering dan K-Means
24
Gambar 3.3. Dendrogram Jarak Cluster
33
Gambar 3.4. Flowchart Hierarchical Clustering K-Means
54
Gambar 3.5. Flowchart Sistem
56
Gambar 4.1. Halaman Home
58
Gambar 4.2. Halaman Proses
58
Gambar 4.3. Halaman Proses Clustering
59
Gambar 4.4. Halaman Hasil Clustering
60
Gambar 4.5. Halaman Cek Cluster
63
Gambar 4.6. Halaman Proses Cek Cluster
64
Gambar 4.7. Halaman HasilCek Cluster
65
Gambar 4.8. Halaman Proses Gagal
66
Gambar 4.9. Perbandingan Cluster Maju Dengan Rata-Rata Cluster
69
Universitas Sumatera Utara
xii Gambar 4.10. Perbandingan Cluster Menuju Maju Dengan Rata-Rata Cluster
69
Gambar 4.11. Perbandingan Cluster Sedang Dengan Rata-Rata Cluster
70
Gambar 4.12. Perbandingan Cluster Menuju Sedang Dengan Rata-Rata Cluster
70
Gambar 4.13. Perbandingan Cluster Tertinggal Dengan Rata-Rata Cluster
70
Universitas Sumatera Utara
