Algoritma K-Means dan Implementasinya

Algoritma K-Means adalah salah satu teknik dari algoritma klastering yang paling umum digunakan dalam analisis data. Metode ini membantu mengelompokkan data menjadi beberapa kelompok yang disebut klaster. Implementasi algoritma ini dalam bahasa pemrograman C dapat memberikan pemahaman yang lebih dalam tentang cara kerjanya.

Sebelum mempelajari materi tentang Algoritma K-Means dan Implementasinya, terlebih dahulu pelajari materi tentang: Algoritma Komputer Beserta Fondasi dan Signifikansinya dalam Dunia Komputasi, Kurikulum Merdeka dan Perannya dalam Mewujudkan Pendidikan Inovatif dan Adaptif, dan Contoh Perangkat Output Komputer yang Membantu Produktivitas.

Asal Mula dan Perkembangan Awal

Algoritma K-Means pertama kali diperkenalkan oleh ilmuwan MacQueen pada tahun 1967. Metode ini awalnya digunakan untuk mengelompokkan data secara otomatis dalam studi mengenai pola dalam data astronomi. Algoritma ini dinamakan "K-Means" karena pendekatannya berdasarkan konsep pemilihan K pusat klaster yang mewakili klaster-klaster dalam data.

Seiring perkembangan teknologi dan penelitian dalam ilmu komputer dan statistik, algoritma K-Means mengalami evolusi signifikan. Perubahan dan penyesuaian dilakukan untuk meningkatkan efisiensi algoritma dan kemampuannya dalam menangani data dengan volume yang lebih besar.

Konsep Algoritma K-Means

Algoritma K-Means terdiri dari beberapa langkah utama:

• Inisialisasi Langkah Awal: Pilih secara acak K titik sebagai pusat awal klaster (centroid).
• Tentukan Klaster: Hitung jarak antara setiap titik data dengan setiap pusat klaster yang telah ditentukan. Masukkan setiap titik data ke dalam klaster dengan pusat terdekat.
• Perbarui Pusat Klaster: Hitung ulang pusat klaster baru untuk setiap klaster berdasarkan rata-rata dari titik-titik yang termasuk dalam klaster tersebut.
• Ulangi Proses: Ulangi langkah 2 dan 3 sampai tidak ada lagi perubahan dalam penempatan titik data ke dalam klaster atau batas iterasi yang ditentukan telah tercapai.

Baca Juga:

• Algoritma Klastering dan Penggalian Pola dari Kumpulan Data
• Metode Elbow dalam Algoritma Klastering untuk Memilih Jumlah Klaster Optimal
• Memahami Metode Silhouette Score dalam Analisis Klastering
• Algoritma Hierarchical Clustering Tentang Pemahaman Pengelompokkan Data Bertingkat

Implementasi dalam Bahasa C

Contoh: Berikut contoh sederhana implementasi algoritma K-Means dalam bahasa C.

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define K 3 // Jumlah klaster

// Fungsi untuk menghitung

// jarak antara dua titik

float hitung_jarak(float x1, float y1, 

float x2, 

float y2) 

{

return sqrt(pow((x2 - x1), 2) 

+ 

pow((y2 - y1), 2));

}

int main() {

// Data titik-titik

float data[][2] = {

{1, 1}, 

{1.5, 2}, 

{3, 4}, 

{5, 7}, 

{3.5, 5}, 

{4.5, 5}, 

{3.5, 4.5}

};

int data_count = 

sizeof(data) / 

sizeof(data[0]);

int i, j;

// Inisialisasi pusat 

// klaster secara acak

float centroids[K][2];

for (i = 0; i < K; i++) 

{

centroids[i][0] = data[i][0];

centroids[i][1] = data[i][1];

}

// Inisialisasi label klaster

int labels[data_count];

for (i = 0; i < data_count; i++) 

{labels[i] = -1;}

// Iterasi hingga konvergensi

int iterasi = 0;

while (iterasi < 100) 

{ 

// Batas iterasi

// Tentukan klaster 

// untuk setiap titik

for (i = 0; i < data_count; i++) 

{

float min_jarak = __FLT_MAX__;

int klaster = -1;

for (j = 0; j < K; j++) 

{

float jarak =

hitung_jarak(data[i][0],

data[i][1], 

centroids[j][0],

centroids[j][1]);

if (jarak < min_jarak) 

{

min_jarak = jarak;

klaster = j;

}

}

labels[i] = klaster;

}

// Hitung pusat klaster baru

float sum_x[K] = {0};

float sum_y[K] = {0};

int count[K] = {0};

for (i = 0; i < data_count; i++) 

{

int klaster = labels[i];

sum_x[klaster] += data[i][0];

sum_y[klaster] += data[i][1];

count[klaster]++;

}

for (i = 0; i < K; i++) 

{

centroids[i][0] = 

sum_x[i] / count[i];

centroids[i][1] = 

sum_y[i] / count[i];

}

iterasi++;

}

// Tampilkan hasil klaster

for (i = 0; i < K; i++) 

{

printf("Klaster %d: ", i + 1);

for (j = 0; j < data_count; j++) 

{

if (labels[j] == i) 

{

printf("(%g, %g) ",

data[j][0], 

data[j][1]);

}

}

printf("\n");

}

return 0;

}

Output:

Klaster 1: (1, 1) 

Klaster 2: (1.5, 2) 

Klaster 3: (3, 4) (5, 7) (3.5, 5) (4.5, 5) (3.5, 4.5)

Penjelasan: Dari contoh yang diberikan sebelumnya, akan dicari tiga kluster (K=3) berdasarkan kelompok data yang telah ditentukan menggunakan algoritma K-Means. Nilai K pada contoh ditentukan tidak berdasarkan pendekatan metode optimalisasi apapun atau langsung ditentukan saja.

Data Input yang akan dikelompokkan dalam kluster data tertentu:

• Data 1: (1, 1) 
• Data 2: (1.5, 2) 
• Data 3: (3, 4) 
• Data 4: (5, 7) 
• Data 5: (3.5, 5) 
• Data 6: (4.5, 5) 
• Data 7: (3.5, 4.5)

Data Output yang didapatkan berdasarkan data input:

• Klaster 1: Data 1 (1, 1) 
• Klaster 2: Data 2 (1.5, 2) 
• Klaster 3: Data 3 (3, 4), Data 4 (5, 7), Data 5 (3.5, 5), Data 6 (4.5, 5), dan Data 7 (3.5, 4.5).

Contoh Soal:

Sebuah perusahaan e-commerce ingin menganalisis perilaku pembelinya berdasarkan dua fitur: jumlah pembelian bulanan dan total waktu yang dihabiskan dalam aplikasi selama bulan terakhir. Terdapat 8 pengguna yang diukur berdasarkan kedua fitur ini. Perusahaan ingin menggunakan algoritma K-Means untuk mengelompokkan pengguna-pengguna ini menjadi 3 kelompok berdasarkan perilaku.

Berikut adalah data pembelian bulanan (dalam ribu Rupiah) dan total waktu di aplikasi (dalam jam) untuk setiap pengguna:

Tabel: Pengelompokkan Data Input Algoritma K-Means

Pengguna	Pembelian Bulanan	Total Waktu di Aplikasi (jam)
1	20	15
2	15	12
3	30	20
4	35	18
5	18	10
6	25	22
7	28	25
8	33	30

Pertanyaan:

• Lakukan pengelompokan (klastering) pengguna-pengguna ini menjadi 3 kelompok (K=3) menggunakan algoritma K-Means.
• Tentukan kluster masing-masing pengguna.

Jawaban:

Langkah 1: Persiapan Data

Data yang diberikan:

• Pengguna 1: (20, 15)
• Pengguna 2: (15, 12)
• Pengguna 3: (30, 20)
• Pengguna 4: (35, 18)
• Pengguna 5: (18, 10)
• Pengguna 6: (25, 22)
• Pengguna 7: (28, 25)
• Pengguna 8: (33, 30)

Langkah 2: Implementasi Algoritma K-Means

Menggunakan algoritma K-Means, dilakukan perhitungan jarak antara pengguna dan pusat klaster untuk menentukan klaster setiap pengguna. Setelah iterasi yang cukup, hasil klasteringnya adalah:

• Klaster 1: Pengguna 1 (20, 15), Pengguna 2 (15, 12), Pengguna 5 (18, 10)
• Klaster 2: Pengguna 3 (30, 20), Pengguna 4 (35, 18), Pengguna 6 (25, 22)
• Klaster 3: Pengguna 7 (28, 25), Pengguna 8 (33, 30)

Hasil klastering tersebut didapatkan dengan membandingkan jarak antara setiap pengguna dengan pusat klaster yang dihasilkan oleh algoritma K-Means.

Kesimpulan:

Dari contoh kasus yang diberikan sebelumnya, algoritma K-Means digunakan untuk mengelompokkan pengguna e-commerce ke dalam tiga kelompok berdasarkan perilaku dalam berbelanja (pembelian bulanan) dan penggunaan aplikasi. Dengan demikian, perusahaan dapat menganalisis dan memahami pola perilaku yang berbeda di antara kelompok-kelompok ini untuk mengambil keputusan yang lebih tepat dalam strategi pemasaran atau pengembangan produk.

Signifikansi K dalam Algoritma K-Means

Dalam algoritma K-Means, K merujuk pada jumlah klaster yang ingin dibentuk atau jumlah pusat klaster yang dipilih awalnya. K adalah parameter yang sangat penting dalam algoritma K-Means karena menentukan jumlah kelompok yang akan dihasilkan dari klastering data.

• Jumlah Kelompok yang Diinginkan: Nilai K menentukan berapa banyak klaster yang ingin dibentuk dari data. Pemilihan K yang tepat bisa menjadi kunci untuk menghasilkan kelompok-kelompok yang relevan dan bermakna dari data yang diberikan.
• Memahami Kepentingan Domain: Dalam kebanyakan kasus, memahami domain data sangat penting untuk menentukan nilai K yang tepat. Jumlah klaster yang relevan dan bermakna seringkali berhubungan dengan pemahaman mendalam tentang data itu sendiri.
• Pengaruh pada Hasil Klastering: Nilai K dapat memiliki dampak besar terhadap hasil klastering. Kekeliruan dalam memilih K yang tepat dapat menghasilkan kelompok-kelompok yang tidak informatif atau kurang menggambarkan pola sebenarnya dalam data.
• Metode Penentuan K: Beberapa metode dapat digunakan untuk menentukan nilai K yang optimal, seperti metode Elbow, metode Silhouette Score, metodeGap Statistics, dan metode lainnya. Metode-metode ini membantu menemukan nilai K yang sesuai dengan struktur data.
• Kompleksitas Komputasi: Jumlah klaster juga berdampak pada kompleksitas komputasi. Semakin besar nilai K, semakin kompleks perhitungan yang diperlukan untuk mengelompokkan data.

Penentuan Nilai K

Memilih nilai K yang tepat merupakan tantangan dalam algoritma K-Means. Beberapa strategi yang umum digunakan meliputi:

• Elbow Method: Menggunakan grafik inersia (sum squared distances within clusters) terhadap nilai K. Nilai K yang tepat seringkali terletak di "siku" dari grafik, di mana penurunan inersia menjadi lebih lambat.
• Silhouette Score: Mengukur seberapa kompak dan terpisahnya klaster. Nilai silhouette tertinggi menandakan nilai K yang lebih baik.
• Analisis Domain: Memahami karakteristik data dan tujuan analisis dapat membantu dalam menentukan jumlah klaster yang sesuai dengan konteks.

Catatan: Ketiga metode yang digunakan untuk menentukan nilai K tersebut tidak bersifat baku, pada penelitian tingkat lanjut, beberapa peneliti ada yang menggunakan metode lain atau pendekatan lain dalam menentukan nilai K, dimana hal tersebut bergantung pada kondisi atau permasalahan yang sedang dihadapi atau diteliti.

Keunggulan Algoritma K-Means

Algoritma K-Means adalah salah satu metode klastering yang paling umum digunakan dalam analisis data. Dengan kelebihan-kelbihan tertentu, algoritma ini menjadi pilihan populer dalam berbagai aplikasi di berbagai industri. Berikut adalah beberapa keunggulan utama dari algoritma K-Means:

• Sederhana dan Efisien: Algoritma K-Means tergolong sederhana untuk dipahami dan diimplementasikan. Pendekatan yang relatif mudah ini membuatnya efisien dalam menangani data dengan jumlah yang besar. Prosesnya pun relatif cepat, menjadikannya pilihan yang baik untuk klastering pada skala besar.
• Scalability (Skalabilitas): K-Means bekerja dengan baik dalam skenario di mana jumlah titik data sangat besar. Kemampuannya untuk mengelola dan memproses data dalam jumlah besar secara efisien menjadikannya pilihan yang cocok untuk aplikasi Big Data.
• Hasil yang Terukur dan Tampak: Hasil klastering dari algoritma K-Means cenderung mudah dipahami dan divisualisasikan. Dengan membagi data menjadi kelompok-kelompok yang berbeda, membantu analis atau pengguna untuk mendapatkan pemahaman yang lebih baik tentang pola yang ada dalam data.
• Kinerja yang Baik untuk Data yang Berbentuk Jelas: K-Means cenderung memberikan hasil yang baik ketika klaster dalam data memiliki bentuk yang jelas (spherical) dan ukuran yang seimbang. Jika data memiliki klaster yang terpisah dengan jelas, algoritma ini dapat memberikan performa yang sangat baik.
• Aplikasi yang Luas: Algoritma K-Means memiliki banyak aplikasi dalam berbagai bidang seperti analisis pasar, pengelompokan konsumen, analisis genetik, pengenalan pola, serta dalam teknik-teknik pembelajaran mesin dan kecerdasan buatan.
• Fleksibel dalam Penggunaan Fitur: K-Means dapat bekerja dengan baik pada berbagai jenis fitur (features) dan tipe data. Hal ini memungkinkan penggunaannya dalam berbagai domain tanpa persyaratan khusus terhadap jenis data yang digunakan.
• Menangani Data Berdimensi Tinggi: Meskipun K-Means dapat bekerja dengan baik pada data berdimensi tinggi, algoritma ini juga dapat digunakan bersamaan dengan teknik reduksi dimensi untuk mengatasi masalah "Curse of Dimensionality" (kondisi di mana kinerja algoritma menurun saat dimensi data meningkat).

Algoritma K-Means memiliki sejumlah keunggulan yang membuatnya populer dalam klastering data. Dari kemampuannya yang sederhana hingga skalabilitasnya dalam menangani data besar, algoritma ini memberikan solusi yang efisien dan mudah diimplementasikan untuk berbagai kebutuhan analisis data di berbagai industri dan aplikasi. Dengan pemahaman yang baik tentang kelebihan ini, para praktisi data dapat memanfaatkannya secara efektif dalam analisis.

Kelemahan Algoritma K-Means dalam Analisis Data

Algoritma K-Means, meskipun sering digunakan dalam klastering data karena sederhananya, juga memiliki beberapa kekurangan yang perlu dipertimbangkan sebelum digunakan dalam analisis data yang lebih kompleks. Berikut adalah beberapa kelemahan utama dari algoritma K-Means:

• Bergantung pada Jumlah Klaster yang Ditentukan Secara Manual (Nilai K): Salah satu kelemahan utama algoritma K-Means adalah ketergantungannya pada jumlah klaster yang harus ditentukan sebelumnya (nilai K). Pemilihan K yang tidak tepat dapat menghasilkan klaster yang kurang informatif atau tidak sesuai dengan struktur sebenarnya dari data.
• Rentan terhadap Inisialisasi Pusat Klaster Awal: Hasil dari algoritma K-Means dapat bervariasi tergantung pada inisialisasi awal pusat klaster. Inisialisasi yang acak dapat mengarah pada konvergensi ke solusi lokal yang suboptimal.
• Sensitif terhadap Outliers (Data Pencilan): Algoritma K-Means sensitif terhadap adanya outliers dalam data. Outliers dapat mempengaruhi pusat klaster sehingga klaster-klasternya tidak merepresentasikan secara akurat pola yang sebenarnya dalam data.
• Membutuhkan Kelompok yang Memiliki Bentuk Spherical: K-Means cenderung memberikan hasil yang kurang baik jika klaster dalam data tidak memiliki bentuk yang "spherical" atau jelas dipisahkan. Klaster dengan bentuk yang kompleks atau klaster yang tumpang tindih mungkin sulit untuk dipisahkan dengan baik oleh algoritma K-Means.
• Tidak Cocok untuk Data Berdimensi Tinggi: Algoritma K-Means kurang efektif saat menangani data berdimensi tinggi karena adanya masalah "Curse of Dimensionality". Ketika dimensi data tinggi, jarak antara titik-titik data menjadi kurang bermakna, dan performa algoritma K-Means dapat menurun.
• Memerlukan Keseimbangan Jumlah Data dalam Setiap Klaster: Algoritma K-Means mengasumsikan bahwa klaster-klasternya memiliki jumlah data yang seimbang. Jika jumlah data dalam klaster tidak seimbang, ini dapat memengaruhi pusat klaster yang dihasilkan.

Catatan: Meskipun algoritma K-Means memiliki kelebihan, seperti kesederhanaannya dalam implementasi dan pemahaman yang relatif mudah, tetapi juga memiliki beberapa kekurangan yang perlu dipertimbangkan. Penggunaan algoritma ini memerlukan pertimbangan yang hati-hati terkait dengan pemilihan jumlah klaster yang tepat (nilai K), sifat data, dan kebutuhan analisis yang diinginkan. Terkadang, untuk kasus data yang lebih kompleks atau non-linear, algoritma klastering lain atau variasi dari K-Means mungkin lebih cocok untuk memberikan hasil yang lebih baik.

Algoritma K-Means adalah teknik yang berguna untuk klastering data dalam kelompok yang berbeda. Implementasi dalam bahasa C seperti contoh di atas dapat membantu siswa memahami secara lebih mendalam konsep algoritma ini serta cara kerjanya dalam konteks pemrograman.

Referensi Tambahan:

• Manfaat Air Rebusan Daun Sirih yang Membuatnya Sebagai Ramuan Tradisional Berharga
• Mengapa Jepang Sering Mengalami Gempa Bumi
• Ciri Kurikulum Merdeka Belajar dan Penjelasannya
• Mengapa Toleransi Sangat Penting Bagi Keberagaman Bangsa Indonesia
• Masa Pubertas dan Pencarian Identitas Diri
• Definisi Kecerdasan dan Penjelasannya
• Teori Kecerdasan Ganda dan Penjelasannya

Artikel ini didedikasikan kepada: Yemima Angela Sapphira Sugiarto, Yosafat Leosaputra Lenggo, Yudha Harizky Santoso, Yusria Ikhsanika Jannah, dan Yusrina Fisabila Izza.

Location: Kota Semarang, Jawa Tengah, Indonesia

Berbagi :