Student Clustering Based on Academic Using K-Means Algoritms Hironimus Leong, Shinta Estri Wahyuningrum Faculty of Computer Science, Faculty of Computer Science Unika Soegijapranata
[email protected] Abstract One goal of clustering data mining is to find a cluster of a particular data modeling. By modeling the data, it can provide more description of the data being analyzed and can be visualized in graphical form. One of the methods used in data mining to search for data modeling is to use KMeans algorithm analysis. K-Means algorithm is used to find groupings of data with specific points, called the centroid. By grouping the data, then large amounts of data, grouped in a simpler visualization. The final results can be used as Decision Support System. Keyword: K-Means Algoritms, Data Mining, Clustering
1. Pendahuluan Sistem pembelajaran di perguruan tinggi dibangun berdasarkan perencanaan yang relevan dengan tujuan pendidikan yang ingin dicapai. Sehingga perlu diterapkan berbagai strategi dan teknik yang menunjang pengembangan mahasiswa untuk berpikir kritis, bereksplorasi, berkreasi dalam memanfaatkan berbagai sumber pengetahuan. Salah satu proses dalam pengembangan sistem pembelajaran tersebut adalah pengembangan dan pembaharuan proses dan kegiatan perkuliahan antara dosen dan mahasiswa. Keseluruhan pengembangan dan pembaharuan, tertuang dalam proses kegiatan belajar mengajar yang diatur oleh kurikulum. Kurikulum memberikan perangkat rencana dan pengaturan tentang isi, bahan kajian maupun bahan pelajaran sampai pada cara penyampaian dan penilaian yang digunakan sebagai pedoman dalam penyelenggaraan kegiatan belajar mengajar. Pedoman penilaian kepada mahasiswa menjadi tolak ukur bagi suatu program studi dalam pengembangan kurikulum dan kualitas pendidikan yang ingin dicapai. Penelitian tentang ‘Student Clustering Based On Academic Using KMeans Algorithms’ adalah penelitian yang ingin menggambarkan proses penilaian mahasiswa dalam bentuk analisis data
mining. Bahan analisis adalah nilai akademik mahasiswa secara keseluruhan. Hasil akhir yang ingin dicapai dari penelitian ini adalah penggambaran mahasiswa secara cluster atau secara pemodelan kelompok nilai baik indeks prestasi komulatif (IPK) mahasiswa maupun nilai mahasiswa pada mata kuliah-mata kuliah tertentu dan dapat divisualisasikan dalam bentuk tabel dan grafik. 2. Tinjauan Pustaka 2.1 Konsep Data Mining Pengertian data mining mengacu pada kata “menyaring” atau “menambang” pengetahuan dari sejumlah data berukuran besar. Berry dan Linoff mendefinisikan data mining sebagai: “suatu proses eksplorasi dan analisis, dengan cara otomatis atau semi otomatis, dari sejumlah data yang besar supaya menemukan pola dan aturan yang sangat penting” Umumnya data mining mempunyai pengertian yang sama dengan istilah “Knowledge Discovery in Databases” atau menemukan pengetahuan dalam database. Proses menemukan pengetahuan dalam database menggunakan beberapa langkah iteratif secara sekuensial yaitu sebagai berikut: 1. Data cleaning (untuk membersihkan data pencilan dan tidak konsisten) 2. Data integration (menggabungkan data dari beberapa sumber data yang berbeda)
3. Data selection (mengambil data yang relevan dari database yang akan digunakan dalam proses analisis) 4. Data transformation (data ditransformasikan atau digabungkan dalam bentuk form untuk proses analisis) 5. Data mining (proses-proses mendasar dengan menggunakan metode kecerdasan buatan dalam menemukan pola-pola yang khusus dari analisis data) 6. Pattern Evaluation (mengidentifikasikan pola yang menarik berdasarkan pengukuran tertentu dari pengetahuan) 7. Knowledge presentation (teknik yang digunakan untuk visualisasi dan representasi pengetahuan) Berdasarkan fungsi dan tujuannya, semua proses eksplorasi dalam data mining dapat digolongkan ke dalam 2 kategori besar yaitu proses data mining yang bersifat deskriptif atau menjelaskan dan proses data mining yang bersifat prediktif atau meramalkan. 2.2 Algoritma K-Means Algoritma K-Means adalah metode clustering secara partisi yang membagi data ke dalam beberapa kelompok yang berbeda yang disebut sebagai cluster. Dalam proses algoritma K-Means, dilakukan proses secara iteratif dengan penentuan kelompok/cluster dilakukan secara acak. Setiap data akan dibagi berdasarkan jarak minimal rata-rata data tersebut ke cluster terdekat. Berikut adalah langkah-langkah algoritma K-Means: Tentukan jumlah cluster K yang akan dibentuk 1. Tentukan centroid C secara acak 2. Hitunglah jarak setiap data ke masingmasing centroid menggunakan rumus jarak antar data (euclidian distance)
d ( x, y )
n
(x
i
yi ) 2
i 1
Keterangan: d = distance/jarak titik (X, Y) xi = titik x data ke-i yi = titik y data ke-i 3. kelompokkan setiap data berdasarkan jarak terdekat data tersebut dengan setiap
centroid C. Tentukan posisi centroid C yang baru dengan cara menghitung nilai rata-rata dari data-data yang ada pada centroid yang sama 1 C k d i nk Keterangan: nk adalah jumlah data dalam cluster k dan di adalah data ke-i dalam cluster k 4. Lakukan kembali langkah 3, jika posisi centroid baru tidak sama dengan centroid yang lama (proses iterasi sampai kondisi centroid ke n sama dengan centroid n-1) 3. Metodologi Penelitian Metode yang digunakan dalam penelitian adalah metode CRISP-DM (CRoss Industry Standard Process for Data Mining). Metode CRISP-DM adalah standarisasi yang berhubungan dengan proses pemodelan data mining. Standarisasi ini tidak mengacu pada teknologi tertentu, melainkan pada semua tingkatan pengguna data mining untuk menyelesaikan masalah perusahaan atau lembaga secara umum.
Gambar 3.1 Metode CRISP-DM
Business Understanding: merupakan fase inisialisasi awal pengembangan data mining yaitu pemahaman tentang obyektivitas dan kebutuhan. Pemahaman tersebut diterjemahkan ke dalam definisi masalah yang akan diselesaikan dengan data mining sehingga dapat dirancang perencanaan awal untuk mencapai tujuan.
Data Understanding: Fase data understanding dimulai dengan eksplorasi data yang akan digunakan dalam permasalahan data mining, verifikasi dan menemukan pengertian awal dari data yang akan digunakan dalam proses analisis. Dari proses-proses tersebut, maka dapat diperoleh hal-hal menarik untuk penyusunan hipotesis dari informasi yang tersembunyi. Data Preparation: Hampir sebagian besar dari proses pemodelan data mining terfokus pada fase data preparation atau persiapan data. Pengumpulan data, penilaian terhadap data, konsolidasi dan pembersihan data, seleksi dan transformasi data dibutuhkan dalam fase ini. Modeling: Fase modeling adalah fase pemilihan model analisis yang akan diimplementasikan dalam data mining, misalnya decision tree, neural network, aturan asosiasi, dan lain-lain. Pemilihan model analisis disesuaikan dengan permasalahan yang diselesaikan, bahkan beberapa model dapat diimplementasikan dalam penyelesaian masalah. Evaluation: Fase evaluation atau evaluasi adalah fase analisis terhadap model yang digunakan, bagaimana kinerja model terhadap analisis data yang digunakan; apakah model yang diimplementasikan sudah atau belum memenuhi fase pertama Deployment: Fase deployment mendefinisikan bagaimana model dikembangkan dalam bentuk sistem, siapa yang akan menggunakannya, dan seberapa sering sistem tersebut digunakan. Terdapat 3 langkah yang ada dalam fase ini, yaitu: Perencanaan deployment, Perencanaan pengawasan dan pemeliharaan; langkah ini penting apabila hasil dari pemodelan dalam data mining digunakan secara periodik. 4. Hasil Penelitian dan Pembahasan Persiapan data adalah proses awal dari implementasi sistem. Dalam proses persiapan data, perlu dilakukan persiapan database mahasiswa Fakultas Ilmu Komputer yaitu sebagai berikut:
Gambar 4.1 Schema Database
Tiga tabel utama menyimpan data tentang mahasiswa, mata kuliah dan hasil studi mahasiswa. Dari sejumlah kolom yang tersedia, maka diambil data yang dijadikan bahan analisis yaitu data mahasiswa (nim dan nama mahasiswa), data mata kuliah (kode matakuliah, nama mata kuliah dan besar sks) dan data hasil studi berupa nilai. Berikut adalah contoh penerapan algoritma clustering untuk analisis data nilai mata kuliah dengan nama Relational Database Management System (RDBMS). Tabel 4.1 Data IPK dan Nilai RDBMS nim ipk rdbms 09.02.0001 3.83 4.0 09.02.0002 3.90 4.0 09.02.0003 3.14 3.0 09.02.0004 3.88 4.0 09.02.0005 2.95 3.5 09.02.0007 2.76 1.0 09.02.0008 3.88 4.0 09.02.0010 2.58 1.0 09.02.0011 2.68 2.5 09.02.0013 3.76 3.5 09.02.0016 3.74 3.5 09.02.0017 3.62 3.5 09.02.0021 2.97 4.0 09.02.0029 2.73 3.0 09.02.0030 3.71 4.0 09.02.0033 3.28 3.0 09.02.0051 2.95 2.5 09.02.0052 3.42 3.0 09.02.0056 2.65 2.5 09.02.0058 2.57 2.5
Langkah pertama adalah menentukan jumlah cluster yang akan dibentuk. Sebagai contoh: ditentukan dua cluster secara acak sebagai berikut: C1 = (2.75, 3.00) C2 = (3.25, 3.75)
Langkah kedua adalah menghitung jarak setiap titik terhadap C1 dan C2 menggunakan rumus distance. Perhitungan jarak data pertama dengan nim 09.02.0001 adalah sebagai berikut: d 2 ( x, y ) (3.83 3.25) 2 (4.0 3.75) 2 0.63
Nilai minimal 0.63 sehingga data pertama masuk ke dalam pengelompokan cluster C2 Dengan cara yang sama, maka data selanjutnya dapat diperoleh perhitungan jarak dan pengelompokan clusteringdalam bentuk tabel sebagai berikut: Tabel 4.2 Hasil Hitungan Iterasi 1 nim ipk rdbms d1 d2 CLUSTER 09.02.0001 3.83 4.0 1.47 0.63 C2 09.02.0002 3.90 4.0 1.52 0.69 C2 09.02.0003 3.14 3.0 0.39 0.76 C1 09.02.0004 3.88 4.0 1.51 0.68 C2 09.02.0005 2.95 3.5 0.54 0.39 C2 09.02.0007 2.76 1.0 2.00 2.79 C1 09.02.0008 3.88 4.0 1.51 0.68 C2 09.02.0010 2.58 1.0 2.01 2.83 C1 09.02.0011 2.68 2.5 0.50 1.37 C1 09.02.0013 3.76 3.5 1.13 0.57 C2 09.02.0016 3.74 3.5 1.11 0.55 C2 09.02.0017 3.62 3.5 1.00 0.45 C2 09.02.0021 2.97 4.0 1.02 0.38 C2 09.02.0029 2.73 3.0 0.02 0.91 C1 09.02.0030 3.71 4.0 1.38 0.52 C2 09.02.0033 3.28 3.0 0.53 0.75 C1 09.02.0051 2.95 2.5 0.54 1.29 C1 09.02.0052 3.42 3.0 0.67 0.77 C1 09.02.0056 2.65 2.5 0.51 1.39 C1 09.02.0058 2.57 2.5 0.53 1.42 C1
Apabila data dalam bentuk tabel di atas, digambarkan dalam bentuk grafik clustering, maka didapatkan visualisasi sebagai berikut:
Clustering 4,5 4 3,5 3
RDBMS
d1 ( x, y ) (3.83 2.75) 2 (4.0 3.00) 2 1.47
Grafik
2,5 2 1,5 1 0,5 0 2,4
2,6
2,8
3
3,2
3,4
3,6
3,8
4
IPK
Gambar 4.2 Visualisasi Clustering Iterasi 1
Langkah terakhir adalah menentukan posisi titik centroid yang baru dengan perhitungan mengambil nilai rata-rata dari data yang ada pada centroid C1 dan centroid C2.
nim ipk rdbms 09.02.0003 3,14 3 09.02.0007 2,76 1 09.02.0010 2,58 1 09.02.0011 2,68 2,5 09.02.0029 2,73 3 09.02.0033 3,28 3 09.02.0051 2,95 2,5 09.02.0052 3,42 3 09.02.0056 2,65 2,5 09.02.0058 2,57 2,5 C1 baru = AVERAGE (IPK, RDBMS) = (2.88, 2.4) nim ipk rdbms 09.02.0002 3,9 4 09.02.0004 3,88 4 09.02.0005 2,95 3,5 09.02.0008 3,88 4 09.02.0013 3,76 3,5 09.02.0016 3,74 3,5 09.02.0017 3,62 3,5 09.02.0021 2,97 4 09.02.0030 3,71 4 C2 baru = AVERAGE (IPK, RDBMS) = (3.62, 3.8)
Dengan cara yang sama pada pembahasan di atas, maka dapat dilakukan proses untuk iterasi berikut. Hasilnya dari iterasi berikut adalah sebagai berikut: Tabel 4. 3 Hasil Perhitungan Iterasi 2 nim ipk rdbms d1 d2 CLUSTER 09.02.0001 3.83 4.0 1.86 0.29 C2 09.02.0002 3.90 4.0 1.90 0.34 C2 09.02.0003 3.14 3.0 0.65 0.93 C1 09.02.0004 3.88 4.0 1.89 0.33 C2 09.02.0005 2.95 3.5 1.10 0.74 C2 09.02.0007 2.76 1.0 1.41 2.93 C1 09.02.0008 3.88 4.0 1.89 0.33 C2 09.02.0010 2.58 1.0 1.43 2.99 C1 09.02.0011 2.68 2.5 0.22 1.60 C1 09.02.0013 3.76 3.5 1.41 0.33 C2 09.02.0016 3.74 3.5 1.40 0.32 C2 09.02.0017 3.62 3.5 1.33 0.30 C2 09.02.0021 2.97 4.0 1.60 0.68 C2 09.02.0029 2.73 3.0 0.62 1.20 C1 09.02.0030 3.71 4.0 1.80 0.22 C2 09.02.0033 3.28 3.0 0.72 0.87 C1 09.02.0051 2.95 2.5 0.12 1.46 C1 09.02.0052 3.42 3.0 0.80 0.83 C1 09.02.0056 2.65 2.5 0.26 1.62 C1 09.02.0058 2.57 2.5 0.32 1.67 C1
Grafik Clustering 4,5 4 3,5
RDBMS
3 2,5 2 1,5 1 0,5 0 2,4
2,6
2,8
3
3,2
3,4
3,6
3,8
4
IPK
Gambar 4.3 Visualisasi Clustering Iterasi 2
5. Kesimpulan dan Saran 5.1 Kesimpulan 1. Algoritma K-Means dapat digunakan untuk mengelola nilai IPK mahasiswa menjadi pengelompokan clustering. Pengelompokan IPK dapat dilakukan dengan perhitungan jarak dan nilai centroid menggunakan rumusan dan formula K-Means
2. Terdapat 3 analisis utama yang dapat diselesaikan menggunakan algoritma KMeans yaitu analisis data nilai IPK mahasiswa, analisis perbandingan nilai mata kuliah tertentu terhadap nilai IPK dan analisis perbandingan nilai mata kuliah terhadap mata kuliah dalam rumpun mata kuliah yang sama dalam kurikulum. 3. Dengan melakukan proses analisis terhadap nilai baik IPK maupun mata kuliah, maka didapatkan gambaran secara umum tentang data hasil studi mahasiswa. 5.2 Saran Penelitian yang dilakukan masih sebatas dalam penggambaran data secara umum sehingga pengembangan di masa-masa mendatang perlu mempertimbangkan pengembangan sistem pendukung keputusan menggunakan algoritma yang sama. Daftar Pustaka [1] Michael J.A Berry and Gordons S. Linnoff, “Data Mining Techniques”, Wiley Publishing, Inc, 2004 [2] Cross Industry Standard Process for Data Mining, http://www.crisp-dm.org/ [3] Jiawei Han dan Micheline Kamber, “Data Mining : Concepts and Techniques”, Morgan Kaufmann Publisher, 2001 [4] Mehmed Kantardzic, “Data MiningConcepts, Models, Methods, and Algorithms”, New John Wiley & Sons, Inc., 2003 [5] Sean Kelly, “Data Warehouse in Action”, John Wiley & Sons, Inc., 1997 [6] Efrem G. Mallach, “Decision Support and Data Warehouse Systems”, McGrawHill, 2000 [7] George M. Marakas , “Modern Data Warehousing, Mining, and Visualization Core Concepts”, Prentice Hall, Inc., 2003
