PENENTUAN DISTRIBUSI UKT MAHASISWA DI PERGURUAN TINGGI DENGAN MENGGUNAKAN METODE K-MEANS
SEBAGAI
LAPORAN TUGAS BESAR DATA MINING & DATA WAREHOUSE


  
Kelompok Clustering

Annisa Nurika    0902118419127
Engga Ramadhan   09021181419034
M. Basir  09021181419130
M. Ryan Fadholi  09021281419050
Safira Aprianti Balqis   09021281419049
Siti Inayah Rizki Hasanah  09021281419042

FAKULTAS ILMU KOMPUTER
JURUSAN TEKNIK INFORMATIKA
UNIVERSITAS SRIWIJAYA
2017
I. Konsep Clustering dalam Data Mining
Clustering atau clusterisasi adalah metode pengelompokan data. Menurut Tan, 2006 clustering adalah sebuah proses untuk mengelompokan data ke dalam beberapa cluster atau kelompok sehingga data dalam satu cluster memiliki tingkat kemiripan yang maksimum dan data antar cluster memiliki kemiripan yang minimum.
Clustering merupakan proses partisi satu set objek data ke dalam himpunan bagian yang disebut dengan cluster. Objek yang di dalam cluster memiliki kemiripan karakteristik antar satu sama lainnya dan berbeda dengan cluster yang lain. Partisi tidak dilakukan secara manual melainkan dengan suatu algoritma clustering. Oleh karena itu, clustering sangat berguna dan bisa menemukan group atau kelompokyang tidak dikenal dalam data.
Clustering banyak digunakan dalam berbagai aplikasi seperti misalnya pada business inteligence, pengenalan pola citra, web search, bidang ilmu biologi, dan untuk keamanan (security). Di dalam business inteligence, clustering bisa mengatur banyak customer ke dalam banyaknya kelompok. Contohnya mengelompokan customer ke dalam beberapa cluster dengan kesamaan karakteristik yang kuat. Clustering juga dikenal sebagai data segmentasi karena clustering mempartisi banyak data set ke dalam banyak group berdasarkan kesamaannya. Selain itu clustering juga bisa sebagai outlier detection.
Algoritma K-Means adalah algoritma clustering yang paling popular dan banyak digunakan dalam dunia industri. Algoritma  K-Means bertujuan untuk membagi data menjadi beberapa kelompok dengan menerima masukan berupa data tanpa label kelas. Metode clustering non-hirarki yang mempartisi data ke dalam satu atau lebih cluster, sehingga data dengan karakteristik yang sama dikelompokkan ke dalam satu cluster yang sama dan data yang mempunyai karateristik berbeda dikelompokkan ke dalam cluster yang lain. Pengelompokkan masukkannya dilakukan tanpa mengetahui terlebih dahulu target kelasnya. Masukkan yang diterima adalah data atau objek dan k buah kelompok (cluster) yang diinginkan. Pada setiap cluster terdapat titik pusat (centroid) yang merepresentasikan cluster tersebut.

II. Penerapan Data Mining
Kasus yang diangkat dalam tugas ini adalah mengelompokkan tingkat UKT (Uang Kuliah Tunggal) mahasiswa baru tahun 2017 di Universitas Sriwijaya. Tujuan clustering adalah mendapatkan kelompok mahasiswa berdasarkan tingkat UKT-nya. Tingkat UKT dikelompokkan menjadi 8 tingkatan dengan jumlah nominal disesuaikan dengan standar pembayaran masing - masing fakultas, serta sesuai dengan Peraturan Pemerintah yang diatur dan dikeluarkan oleh Kementerian Riset, Teknologi dan Perguruan Tinggi. Data masukan untuk perhitungan cluster yang digunakan adalah jumlah penghasilan orang tua dan jumlah tanggungan keluarga.
Data dari tiap mahasiswa dan juga delapan tingkatan UKT tersebut akan dijadikan masukan untuk metode K-Means. Di mana delapan tingkatan tersebut akan menjadi nilai K, yang berarti jumlah cluster yang dikehendaki. Sedangkan data dari tiap mahasiswa tersebut akan dihitung jaraknya (cara menghitung akan dijelaskan pada bagian langkah percobaan) sehingga dapat dikelompokkan ke dalam salah satu cluster dari delapan cluster yang ada.

III. Eksplorasi Tools untuk Data Mining
Dalam tugas ini diimplementasikan menggunakan bahasa pemrograman Python 3.6 pada Sistem Operasi Windows. Python adalah sebuah bahasa pemrograman tingkat tinggi yang bersifat cross-platform, general-purpose, dan multi-paradigm. Sebelum menggunakan bahasa Python, diperlukan sebuah Python interpreter yang bertugas mengonversi kode dalam bahasa Python ke bahasa mesin  yang dapat dijalankan komputer. Ada banyak variasi interpreter untuk bahasa Python, dengan fitur dan performa yang berbeda-beda.
Walaupun kode bahasa Python bersifat portable, ada sebagian library Python yang dikembangkan untuk sistem operasi terentu dan belum tentu dapat digunakan pada sistem operasi lain. Salah satu library tersebut adalah numpy yang versi default-nya tidak bisa di-install pada i Windows. Hal ini disebabkan oleh bagian-bagian pada library numpy yang menggunakan C-, CPython, dan Fortran pada implementasinya.
Untuk mengatasi masalah tersebut, pada penelitian ini digunakan Python interpreter yang terdapat di dalam distribusi Miniconda3. Salah satu fitur utama yang dimiliki oleh Miniconda3 adalah package manager conda, yang menyediakan library.

IV. Penjelasan Dataset
Dataset yang digunakan pada program berbentuk sebuah array yang tiap elemennya menyimpan 1 elemen float (penghasilan orang tua) dan 1 elemen integer (tanggungan orang tua).
Sumber pertama dari dataset adalah data Penerimaan Mahasiswa Baru BEM KM Unsri 2017. Data tersebut merupakan data komprehensif setiap mahasiswa yang diisi secara langsung oleh setiap mahasiswa pada proses registrasi ulang mahasiswa baru Unsri 2017. Data tersebut tersimpan dalam sebuah database MySQL.
Untuk menjaga privasi mahasiswa secara individu, dari data tersebut yang diambil hanya data penghasilan gabungan dari ayah dan ibu setiap mahasiswa sejumlah 6653 data. Karena data tersebut masih berupa data mentah hasil masukan tiap mahasiswa lalu dilakukan preprocessing untuk membuang data-data kosong dan pencilan (outlier).  Setelah dilakukan preprocessing, jumlah data menyusut menjadi 5547 data.
Selanjutnya dilakukan normalisasi pada data penghasilan orang tua dengan cara membaginya dengan nilai 10^6. Hal ini dilakukan karena algoritma K-Means menggunakan jarak antar data sebagai penentu cluster utama. Jika tidak dilakukan normalisasi maka jarak antar data penghasilan orang tua yang dapat mencapai jutaan akan berpengaruh sangat besar pada cluster, sedangkan data tanggungan yang jaraknya hanya bernilai satuan tidak akan berpengaruh sama sekali.
Data penghasilan yang telah dibersihkan dan dinormalisasi tersebut lalu digabung dengan data jumlah tanggungan orang tua mahasiswa, yang dibangkitkan oleh program berdasarkan total penghasilan orang tua mahasiswa tersebut sesuai algoritma yang telah dibangun. Pembangkitan dilakukan karena tidak terdapat data tanggungan pada data aslinya.
Setelah data berhasil dibangkitkan, seluruh data disimpan pada sebuah array dimana setiap pasangan data penghasilan dan jumlah tanggungan tersebut disimpan di dalam sebuah tuple. Array inilah yang digunakan dalam operasi perhitungan cluster.
Setelah data berhasil dibangkitkan, seluruh data disimpan pada sebuah objek numpy.ndarray dimana setiap pasangan data penghasilan dan jumlah tanggungan tersebut disimpan di dalam sebuah numpy.array. Objek numpy.ndarray digunakan karena objek ini lebih efisien dari Python list biasa. Selain itu objek ini mendukung berbagai operasi-operasi yang terdapat pada library numpy, seperti linalg.norm yang digunakan untuk menghitung jarak antara data dan centroid. Array inilah yang digunakan dalam operasi perhitungan klaster.

V. Algoritma
Berikut adalah algoritma dari metode K-Means:
1. Pilih jumlah cluster k yang diinginkan.
2. Inisialisasi k pusat cluster (centroid) secara random
3. Tempatkan setiap data atau objek ke cluster terdekat. Kedekatan dua objek ditentukan berdasar jarak. Jarak yang dipakai pada algoritma K-Means adalah Euclidean distance (d).
 
4. Hitung kembali pusat cluster dengan keanggotaan cluster yang sekarang. Pusat cluster adalah rata-rata (mean) dari semua data atau objek dalam cluster tertentu.
5. Tugaskan lagi setiap objek dengan memakai pusat cluster yang baru. Jika pusat cluster sudah tidak berubah lagi, maka proses pengclusteran selesai. Atau, kembali lagi ke langkah nomor 3 sampai pusat cluster tidak berubah lagi (stabil) atau tidak ada penurunan yang signifikan dari nilai SSE (Sum of Squared Errors).

Berikut adalah gambar flowchart yang menjelaskan algoritma dalam metode K-Means.


VI. Langkah Percobaan
Berikut adalah langkah percobaan yang kami lakukan:
1. Pertama-tama, install versi terbaru dari Miniconda, yang sudah mempunyai sebuah interpreter Python didalamnya. Lalu masukkan direktori instalasi Miniconda ke dalam Environment Variable PATH dalam Windows. Hal ini memungkinkan command python dapat diakses dari direktori mana saja pada Windows.
2. Tes Environment Variable dengan cara membuka command prompt dan mengetikkan “python”, apabila berhasil dijalankan maka Miniconda telah berhasil ditambahkan pada Environment Variable.
3. Tutup command prompt sebelumnya, lalu buka lagi command prompt baru. Ketikkan “conda install numpy matplotlib”. Perintah ini akan mendownload sekaligus menginstall library numpy dan matplotlib, yang diperlukan untuk menjalankan script yang telah dibuat.
4. Setelah proses instalasi sebelumnya selesai, ketikkan “pip install pymysql”. Perintah tersebut akan memulai proses install library PyMySQL, yang diperlukan untuk menghubungkan Python dan MySQL.
5. Setelah proses instalasi selesai, buka command prompt lalu mengetikkan python, yang merupakan perintah untuk mengeksekusi file yang berekstensi .py (ekstensi untuk file python), dalam hal ini file yang telah dibuat bernama kmeans.
6. Karena pada tugas ini kami menggunakan k yang berjumlah delapan, maka setelah mengetikkan nama file, ketikkan –k 8, yang berarti nanti dataset yang digunakan akan dibagi menjadi delapan buah cluster.
 
Gambar 2. Langkah Percobaan
7. Tunggu proses berjalannya program. Selagi melakukan perhitungan, program akan menampilkan angka-angka yang berhubungan dengan perhitungan tersebut. Jika proses selesai, maka akan keluar sebuah grafik scatter plot sebagai visualisasi dataset dan cluster yang dihasilkan.

VII. Hasil
Berikut adalah hasil clustering yang didapat setelah melakukan langkah yang ada pada bagian VI.
Gambar 3. Visualisasi Hasil Clustering

Pada sumbu X merupakan jumlah tanggungan per keluarga sedangkan pada sumbu Y merupakan nominal gaji per keluarga dalam satuan juta. Pada gambar terlihat bahwa ada delapan warna, yakni warna yang mewakili jumlah cluster yang telah ditetapkan sebelumnya.

VIII. Referensi
P.-N. Tan, M. Steinbach, and V. Kumar, Introduction to Data Mining, (First Edition). Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 2005.