MAKALAH UJI K-MEANS STATISTIKA

BAB I

PENDAHULUAN

1.1 Latar Belakang

Mendapat nilai IP yang baik adalah keinginan seluruh mahasiswa. Tidak hanya itu, Mendapat nilai IP yang baik adalah keuntungan bagi dua pihak. Pertama, pihak mahasiswa, karena dengan begitu mahasiswa akan mendapatkan pekerjaan dengan lebih mudah karena perusahaan cenderung mencari karyawan ber-IPK tinggi Kedua, pihak universitas, karena seiring tepatnya waktu kelulusan mahasiswa, hal itu akan membantu memajukan kualitas universtas tersebut, seperti peningkatan akreditasi. Sayangnya, IP mahasiswa tidak selalu dapat dideteksi secara dini. Hal ini tentunya merugikan kedua pihak. Untuk memecahkan masalah tersebut, perlu adanya suatu sistem atau program yang dapat mengelompokkan golongan mahasiswa berdasarkan tingkat kebugaran dan kesehatan serta gaya hidup mahasiswa itu sendiri. Dalam tugas ini, pengelempokkan mahasiswa dilakukan dengan cara clustering, menggunakan algoritma k-Means. Clustering merupakan teknik yang sudah cukup dikenal dan banyak dipakai dalam data mining. Sampai sekarang para ilmuwan dalam bidang data mining masih melakukan berbagai usaha untuk melakukan perbaikan model klaster karena metode yang dikembangkan masih bersifat heuristik. Dari beberapa teknik klastering yang paling sederhana dan umum adalah algoritma k-Means, yang mengelompokkan obyek berdasarkan jarak. (Budi Santoso, 2007)

Peneliti-peneliti terdahulu telah melakukan proses clustering dengan menggunakan algoritma k-Means untuk memecahkan masalah serupa. Salah satu contoh pada paper nasional berjudul, “Aplikasi K-Means Untuk Pengelompokan Mahasiswa Berdasarkan Nilai Body Mass Index (BMI) & Ukuran Kerangka”.  Peneliti tersebut menjelaskan bahwa, “Masalah kesehatan merupakan permasalahan yang sangat penting untuk diperhatikan, diantaranya adalah masalah BMI dan ukuran kerangka seseorang. Apabila seseorang telah mengetahui nilai BMI-nya, orang tersebut dapat mengontrol berat badan sehingga dapat mencapai berat badan normal yang sesuai dengan tinggi badan. Pada penelitian ini, penulis mencoba membangun suatu sistem untuk mengelompokkan data yang ada berdasarkan status gizi dan ukuran rangkanya dengan memasukkan parameter kondisi fisik dari orang tersebut. Pengelompokkan data dilakukan dengan menggunakan metode clustering KMeans, yaitu dengan mengelompokkan n buah objek ke dalam k kelas

berdasarkan jaraknya dengan pusat kelas...” (Tedy Rismawan dan Sri Kusumadewi, 2008) Selain itu, paper bertaraf internasional pun pernah mengimplementasikan algoritma k-Means. Paper tersebut berjudul “Application of K-Means Clustering Algorithm for Prediction of Students’ Academic Performance”. Peneliti tersebut menjelaskan bahwa, “Kemampuan untuk memantau progress akademik siswa merupakan isu penting untuk komunitas pembelajaran. Didirikan sebuah sistem yang digunakan untuk menganalisis hasil akademik siswa. Hasil tersebut berdasarkan dari analisa klaster dan menggunakan standart statistik algoritma untuk mengatur nilai mereka sesuai dengan tingkat kinerja. Dalam paper ini, kami juga mengimplementasi algoritma k-Means untuk menganalisa hasil data.

1.2 Rumusan Masalah

Berikut adalah rumusan-rumusan masalah untuk menemukan solusi dari permasalahan di atas:

a. Mengumpulkan data mahasiswa berdasarkan parameter seringnya berolahraga, makan teratur, waktu tidur,makanan yang dikonsumsi dan transportasi yang digunakan ke kampus.

b. Mengklasterisasi mahasiswa dengan menggunakan algoritma k-Means.

c. Mengimplementasi algoritma K-Means dengan program SPSS.

 

1.3 Batasan Masalah

Dari permasalahan-permasalahan di atas, maka batasan-batasan dalam tugas ini adalah:

a. Program dibangun dengan menggunakan MATLAB versi R2010b dan

tidak diintegerasikan dengan program lain, seperti database maupun hal

hal yang berhubungan dengan penyimpanan data. 

b. Jumlah klaster dibatasi tiga klaster.

c. Data mahasiswa yang diuji adalah 25 data mahasiswa TI Universitas Syarifhidayatullah Jakarta angkatan 2014. 

1.4 Tujuan

Mengacu pada perumusan masalah di atas, tujuan yang hendak dicapai dalam penyusunan tugas ini antara lain:

a. Mengklaster data-data mahasiswa berdasarkan parameter yang ada.

b. Menghasilkan program yang dapat menunjukkan hasil data setelah melalui proses clustering, beserta grafiknya.

 

1.5 Manfaat

Bila program ini berhasil diimplementasikan, maka manfaat yang dapat diberikan antara lain:

a. Pihak universitas dapat melihat hasil pengelompokkan mahasiswa, sehingga dapat mengetahui mahasiswa mana saja yang membutuhkan bantuan untuk meningkatkan nilai IP-nya.

b. Mahasiswa dapat mengetahui ia berada di kelas mana, sehingga mengoptimalkan dirinya untuk segera mengejar ketertinggalan. 

BAB II

LANDASAN TEORI

2.1 Clustering 

Pada dasarnya clustering terhadap data adalah suatu proses untuk mengelompokkan sekumpulan data tanpa suatu atribut kelas yang telah didefinisikan sebelumnya, berdasarkan pada prinsip konseptual clustering yaitu memaksimalkan dan juga meminimalkan kemiripan intra kelas. Misalnya, sekumpulan obyek-obyek komoditi pertama-tama dapat di clustering menjadi sebuah himpunan kelas-kelas dan lalu menjadi sebuah himpunan aturan-aturan yang dapat diturunkan berdasarkan suatu klasifikasi tertentu.  

Proses untuk mengelompokkan secara fisik atau abstrak obyek-obyek ke dalam bentuk kelas-kelas atau obyek-obyek yang serupa, disebut dengan clustering atau unsupervised classification. Melakukan analisa dengan clustering, akan sangat membantu untuk membentuk partisi-partisi yang berguna terhadap sejumlah besar himpunan obyek dengan didasarkan pada prinsip "divide and conquer" yang mendekomposisikan suatu sistem skala besar, menjadi komponen-komponen yang lebih kecil, untuk menyederhanakan proses desain dan implementasi. Perbedaan utama antara Clustering Analysis dan klasifikasi adalah bahwa Clustering Analysis digunakan untuk memprediksi kelas dalam format bilangan real dan pada format katagorikal atau Boolean. 

2.2 Data Clustering 

Data Clustering merupakan salah satu metode data miningyang bersifat tanpa arahan (unsupervised). Ada dua jenis data clustering yang sering dipergunakan dalam proses pengelompokan data yaitu hierarchical dataclustering dan non-hierarchical dataclustering. K-Means merupakan salah satu metode data clustering non hirarki yang berusaha mempartisi data yang ada ke dalam bentuk satu atau lebih cluster/kelompok. Metode ini mempartisi data ke dalam cluster/kelompok sehingga data yang memiliki karakteristik yang sama dikelompokkan ke dalam satu cluster yang sama dan data yang mempunyai karakteristik yang berbeda dikelompokkan ke dalam kelompok yang lain.  Adapun tujuan dari data clustering ini adalah untuk meminimalisasikan objective function yang diset dalam proses clustering, yang pada umumnya berusaha meminimalisasikan variasi di dalam suatu cluster dan memaksimalisasikan variasi antar cluster. Data clustering menggunakan metode K-Means ini secara umum dilakukan dengan algoritma dasar sebagai berikut: 1. Tentukan jumlah cluster 2. Alokasikan data ke dalam cluster secara random 3. Hitung centroid (rata-rata) dari data yang ada di masing-masing cluster 4. Alokasikan masing-masing data ke centroid (rata-rata) terdekat 5. Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau apabila perubahan nilai centroid, ada yang di atas nilai threshold yang ditentukan atau apabila perubahan nilai pada objective function yang digunakan di atas nilai threshold yang ditentukan. 

2.2.1 Perkembangan Penerapan K-Means 

Beberapa alternatif penerapan K-Means dengan beberapa pengembangan teori-teori penghitungan terkait telah diusulkan. Hal ini termasuk pemilihan:

1. Distance space untuk menghitung jarak di antara suatu data dan centroid.

2. Metode pengalokasian data kembali ke dalam setiap cluster.

3. Objective function yang digunakan.         

2.3 Beberapa Permasalahan yang Terkait Dengan K-Means 

Beberapa permasalahan yang sering muncul pada saat menggunakan metode K-Means untuk melakukan pengelompokan data adalah:

1. Ditemukannya beberapa model clustering yang berbeda

2. Pemilihan jumlah cluster yang paling tepat

3. Kegagalan untuk converge

4. Pendeteksian outliers

5. Bentuk masing-masing cluster 6. Masalah overlapping 

Keenam permasalahan ini adalah beberapa hal yang perlu diperhatikan pada saat menggunakan K-Means dalam mengelompokkan data. Permasalahan 1 umumnya disebabkan oleh perbedaan proses inisialisasi anggota masing-masing cluster. Proses initialisasi yang sering digunakan adalah proses inisialisasi secara random. Dalam suatu studi perbandingan, proses inisialisasi secara random mempunyai kecenderungan untuk memberikan hasil yang lebih baik dan independent, walaupun dari segi kecepatan untuk converge lebih lambat. 

Permasalahan 2 merupakan masalah laten dalam metode K-Means. Beberapa pendekatan telah digunakan dalam menentukan jumlah cluster yang paling tepat untuk suatu dataset yang dianalisa termasuk di antaranya Partition Entropy (PE) dan GAP Statistics. Satu hal yang patut diperhatikan mengenai metode-metode ini adalah pendekatan yang digunakan dalam mengembangkan metode-metode tersebut tidak sama dengan pendekatan yang digunakan oleh K-Means dalam mempartisi data item ke masing-masing cluster. Permasalahan kegagalan untuk converge, secara teori memungkinkan untuk terjadi dalam kedua metode K-Means. Kemungkinan ini akan semakin besar terjadi untuk metode Hard K-Means, karena setiap data di dalam dataset dialokasikan secara tegas (hard) untuk menjadi bagian dari suatu cluster tertentu. Perpindahan suatu data ke suatu cluster tertentu dapat mengubah karakteristik model clustering yang dapat menyebabkan data yang telah dipindahkan tersebut lebih sesuai untuk berada di cluster semula sebelum data tersebut dipindahkan dan demikian juga dengan keadaan sebaliknya. Kejadian seperti ini tentu akan mengakibatkan pemodelan tidak akan berhenti dan kegagalan untuk converge akan terjadi. Untuk Fuzzy K-Means walaupun ada, kemungkinan permasalahan ini untuk terjadi sangatlah kecil, karena setiap data diperlengkapi dengan membership function (Fuzzy K-Means) untuk menjadi anggota cluster yang ditemukan. 

Permasalahan 4  merupakan permasalahan umum yang terjadi hampir di setiap metode yang melakukan pemodelan terhadap data. Khusus untuk metode K-Means hal ini memang menjadi permasalahan yang cukup menentukan. Beberapa hal yang perlu diperhatikan dalam melakukan pendeteksian outliers dalam proses pengelompokan data termasuk bagaimana menentukan apakah suatu data item merupakan outliers dari suatu cluster tertentu dan apakah data dalam jumlah kecil yang membentuk suatu cluster tersendiri dapat dianggap sebagai outliers. Proses ini memerlukan suatu pendekatan khusus yang berbeda dengan proses pendeteksian outliers di dalam suatu dataset yang hanya terdiri dari satu populasi yang homogen.       

Permasalahan kelima adalah menyangkut bentuk cluster yang ditemukan. Tidak seperti metode data clustering lainnya termasuk Mixture Modelling, K-Means umumnya tidak mengindahkan bentuk dari masing-masing cluster yang mendasari model yang terbentuk, walaupun secara alamiah masing-masing cluster umumnya berbentuk bundar. Untuk dataset yang diperkirakan mempunyai bentuk yang tidak biasa, beberapa pendekatan perlu untuk diterapkan.  

Masalah overlapping sebagai permasalahan terakhir sering sekali diabaikan karena umumnya masalah ini sulit terdeteksi. Hal ini terjadi untuk metode Hard K-Means dan Fuzzy K-Means, karena secara teori metode ini tidak diperlengkapi feature untuk mendeteksi apakah di dalam suatu cluster ada cluster lain yang kemungkinan tersembunyi. 

K-Means merupakan metode data clustering yang digolongkan sebagai metode pengklasifikasian yang bersifat unsupervised (tanpa arahan). Pengkategorian metodemetode pengklasifikasian data antara supervised dan unsupervised classification didasarkan pada adanya dataset yang data itemnya sudah sejak awal mempunyai label kelas dan dataset yang data itemnya tidak mempunyai label kelas. Untuk data yang sudah mempunyai label kelas, metode pengklasifikasian yang digunakan merupakan metode supervised classification dan untuk data yang belum mempunyai label kelas, metode pengklasifikasian yang digunakan adalah metode unsupervised classification. 

Selain masalah optimasi pengelompokan data ke masing-masing cluster, data clustering juga diasosiasikan dengan permasalahan penentuan jumlah cluster yang paling tepat untuk data yang dianalisa. Untuk kedua jenis K-Means, baik Hard KMeans dan Fuzzy K-Means, yang telah dijelaskan di atas, penentuan jumlah cluster untuk dataset yang dianalisa umumnya dilakukan secara supervised atau ditentukan dari awal oleh pengguna, walaupun dalam penerapannya ada beberapa metode yang sering dipasangkan dengan metode K-Means. Karena secara teori metode penentuan jumlah cluster ini tidak sama dengan metode pengelompokan yang dilakukan oleh KMeans, kevalidan jumlah cluster yang dihasilkan umumnya masih dipertanyakan.  

Melihat keadaan dimana pengguna umumnya sering menentukan jumlah cluster sendiri secara terpisah, baik itu dengan menggunakan metode tertentu atau berdasarkan pengalaman, di sini kedua metode K-Means ini dapat disebut sebagai metode semi-supervised classification, karena metode ini mengalokasikan data item ke masing-masing cluster secara unsupervised dan menentukan jumlah cluster yang paling sesuai dengan data yang dianalisa secara supervised. 

2.4 K-Means untuk Data yang Mempunyai Bentuk Khusus 

Beberapa dataset yang mempunyai bentuk tertentu memerlukan suatu metode pemecahan khusus yang disesuaikan dengan keadaan data tersebut. Gambar 2.2. mengilustrasikan suatu dataset yang mempunyai bentuk khusus yang kalau dimodel dengan metode K-Means, baik Hard K-Means dan Fuzzy K-Means akan memberikan hasil yang tidak mewakili keadaan dataset tersebut. Untuk keperluan seperti itu, beberapa peneliti telah mengusulkan pengembangan metode K-Means yang secara khusus memanfaatkan kernel trik, dimana data space untuk data awal di-mapping ke feature space yang berdimensi tinggi. Beberapa hal yang perlu diperhatikan dalam pengembangan metode K-Means dengan kernel trik ini adalah bahwa data pada feature space tidak lagi dapat didefinisikan secara eksplisit, sehingga penghitungan nilai membership function dan centroid tidak dapat dilakukan secara langsung.             

Beberapa trik penghitungan telah diusulkan dalam menurunkan nilai kedua variabel yang diperlukan tersebut. Dengan penerapan trik perhitungan terhadap kedua variabel tersebut, objective function yang digunakan dalam menilai apakah suatu proses pengelompokan sudah converge atau tidak juga akan berubah.

Algoritma K-means, K-means merupakan salah satu metode data klustering non hirarki yang berusaha mempartisi data yang ada ke dalam bentuk satu atau lebih cluster / kelompok. Metode ini mempartisi ke dalam cluster / kelompok sehingga data yang memiliki karakteristik yang sama (High intra class similarity) dikelompokkan ke dalam satu cluster yang sama dan yang memiliki karakteristik yang berbeda  (Law inter class similarity) dikelompokkan pada kelompok yang lain [3]. Proses klustering dimulai dengan mengidentifikasi data yang akan dikluster, Xij (i=1,...,n; j=1,...,m) dengan n adalah jumlah data yang akan dikluster dan  m adalah jumlah variabel. Pada awal iterasi, pusat setiap kluster ditetapkan secara bebas (sembarang), Ckj (k=1,...,k; j=1,...,m). Kemudian dihitung jarak antara setiap data dengan setiap pusat kluster. Untuk melakukan penghitungan jarak data ke-i (xi) pada pusat kluster ke-k (ck), diberi nama (dik), dapat

digunakan formula Euclidean [2] seperti pada persamaan (1), yaitu:  

          

(1)  

Suatu data akan menjadi anggota dari kluster ke-k apabila jarak data tersebut ke pusat kluster ke-k bernilai paling kecil jika dibandingkan dengan jarak ke pusat kluster lainnya. Hal ini dapat dihitung dengan menggunakan  persamaan (2) Selanjutnya, kelompokkan data-data yang menjadi anggota pada setiap kluster.         

(2)             

Nilai pusat kluster yang baru dapat dihitung dengan cara mencari nilai rata-rata dari data-data yang menjadi anggota pada kluster tersebut, dengan menggunakan  rumus pada persamaan 3:  

         

(3) 

Dimana  xij ∈ kluster ke – k          p   =  banyaknya anggota kluster ke k     Algoritma dasar dalam k-means adalah  1. Tentukan jumlah kluster (k), tetapkan pusat kluster sembarang.  2. Hitung jarak setiap data ke pusat kluster menggunakan persamaan (2.1). 3. Kelompokkan data ke dalam kluster yang dengan jarak yang paling pendek menggunakan persamaan (2.2).  4. Hitung pusat kluster yang baru menggunakan persamaan (2.3) Ulangi langkah 2 sampai dengan 4 hingga sudah tidak ada lagi data yang berpindah ke kluster yang lain.

BAB III

PEMBAHASAN

III.A Pembahasan Data

         Dari data yang telah diperoleh lalu kita olah menggunakan program IBM SPSS 22 didapat sebagai berrikut :

Sesuai dengan teori yang ada dimana data yang paling kecil yaitu yang mempengaruhi variable yang ada. Dimana dalam kasus ini keadaan IP mahasiswa. Maka dari itu kita lihat dahulu pada cluster 1,data yang paling kecil.  Dimana yang paling kecil yaitu Olahraga, makan tepat waktu, dan mengkonsumsi makanan 4 sehat 5 sempurna. Lalu yang paling besar yaitu tidur cukup. Dari data yang kecil itu adalah yang menurut data menentukan IP mahasiswa. Dan yang besar sedikit tidak mempengaruhi IP mahasiswa.

III.B Kesimpulan Data

CLUSTER I	CLUSTER II
SERINGNYA MAHASISWA BEROLAHRAGA	MAHASISWA TIDUR CUKUP SETIAP HARINYA
MAHASISWA MAKAN TEPAT WAKTU
MAHASISWA MAKAN MAKANAN 4 SEHAT 5 SEMPURNA

             CLUSTER I : Yang mempengaruhi IP Mahasiswa

             CLUSTER II : Yang sedikit tidak mempengaruhi IP mahasiswa

Dari sini kita dapat simpulkan data ini hanya dapat dibagi kedalam 2 cluster saja.

BAB IV

KESIMPULAN DAN SARAN

IV.1 Kesimpulan

a. Setelah dilakukan pengelompokan data mahasiswa melalui kuisioner yang disebar kita peroleh bahwa yang mempengaruhi keadaan IP Mahasiswa setidaknya Olahraga teratur,makan tepat waktu serta makan makanan 4 sehat 5 sempurna. Dan yang tidak mempengaruhi yaitu tidur cukup setiap harinya.  

b. Strategi untuk menyiasati agar tidak terjadinya penurunan IP Mahasiswa TI UIN SYARIFHIDAYATULLAH JAKARTA adalah dengan diadakan agenda olahraga bersama atau istirahat yang tepat waktu setiap harinya.

IV.2 Saran

a. Pengelompokan terhadap data mahasiswa TI UIN SYARIFHIDAYATULLAH JAKARTA sebaiknya dilakukan secara rutin setiap semester untuk menghindari penurunan IP mahasiswa pada semester berikutnya berikutnya.

b. Penelitian ini dapat dijadikan sebagai salah satu referensi bagi pihak admisi TI UIN SYARIFHIDAYATULLAH JAKARTA untuk  mengambil keputusan dalam melakukan strategi promosi bagi calon mahasiswa baru.