K-means Clustering

Assalamu’alaikum Warahmatullah Wabarakatuh, Oke gais. Hallo!! Sekarang kita akan bahas tentang model pada metode unsupervised learning nih, Apa aja yaa. Yuk Simak di bawah ini!!

K-means Clustering

A. Pengertian K-Means

K-means merupakan algoritma clustering. K-means Clustering adalah salah satu “unsupervised machine learning algorithms” yang paling sederhana dan populer. K-Means Clustering adalah suatu metode penganalisaan data atau metode Data Mining yang melakukan proses pemodelan tanpa supervisi (unsupervised) dan merupakan salah satu metode yang melakukan pengelompokan data dengan sistem partisi.

K-means clustering merupakan salah satu metode cluster analysis non hirarki yang berusaha untuk mempartisi objek yang ada kedalam satu atau lebih cluster atau kelompok objek berdasarkan karakteristiknya, sehingga objek yang mempunyai karakteristik yang sama dikelompokan dalam satu cluster yang sama dan objek yang mempunyai karakteristik yang berbeda dikelompokan kedalam cluster yang lain. Metode K-Means Clustering berusaha mengelompokkan data yang ada ke dalam beberapa kelompok, dimana data dalam satu kelompok mempunyai karakteristik yang sama satu sama lainnya dan mempunyai karakteristik yang berbeda dengan data yang ada di dalam kelompok yang lain.

Dengan kata lain, metode K-Means Clustering bertujuan untuk meminimalisasikan objective function yang diset dalam proses clustering dengan cara meminimalkan variasi antar data yang ada di dalam suatu cluster dan memaksimalkan variasi dengan data yang ada di cluster lainnya juga bertujuan untuk menemukan grup dalam data, dengan jumlah grup yang diwakili oleh variabel K. Variabel K sendiri adalah jumlah cluster yang diinginkan. Membagi data menjadi beberapa kelompok. Algoritma ini menerima masukan berupa data tanpa label kelas. Hal ini berbeda dengan supervised learning yang menerima masukan berupa vektor (x1 , y1) , (x2 , y2) , …, (xi , yi), di mana xi merupakan data dari suatu data pelatihan dan yi merupakan label kelas untuk xi .

Pada algoritma pembelajaran ini, komputer mengelompokkan sendiri data-data yang menjadi masukannya tanpa mengetahui terlebih dulu target kelasnya. Pembelajaran ini termasuk dalam unsupervised learning. Masukan yang diterima adalah data atau objek dan k buah kelompok (cluster) yang diinginkan. Algoritma ini akan mengelompokkan data atau objek ke dalam k buah kelompok tersebut. Pada setiap cluster terdapat titik pusat (centroid) yang merepresentasikan cluster tersebut.

K-means ditemukan oleh beberapa orang yaitu Lloyd (1957, 1982), Forgey (1965) , Friedman and Rubin (1967), and McQueen (1967). Ide dari clustering pertama kali ditemukan oleh Lloyd pada tahun 1957, namun hal tersebut baru dipublikasi pada tahun 1982. Pada tahun 1965, Forgey juga mempublikasi teknik yang sama sehingga terkadang dikenal sebagai Lloyd-Forgy pada beberapa sumber.

Terdapat dua jenis data clustering yang sering dipergunakan dalam proses pengelompokan data yaitu Hierarchical dan Non-Hierarchical, dan K-Means merupakan salah satu metode data clustering non-hierarchical atau Partitional Clustering.

Data clustering menggunakan metode K-Means Clustering 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

K-means clustering adalah salah satu algoritma analisis klaster (cluster analysis) non hirarki. Analisis klaster merupakan salah satu alat untuk mengelompokkan data berdasarkan variabel atau feature. Tujuan dari k-means clustering, seperti metode klaster lainnya, adalah untuk mendapatkan kelompok data dengan memaksimalkan kesamaan karakteristik dalam klaster dan memaksimalkan perbedaan antar klaster.

Algoritma K-means clustering mengelompokkan data berdasarkan jarak antara data terhadap titik centroid klaster yang didapatkan melalui proses berulang. Analisis perlu menentukan jumlah K sebagai input algoritma. Dalam ranah machine learning, algoritma k-means clustering termasuk ke dalam jenis unsupervised learning.

B. Beberapa Permasalahan yang Terkait Dengan K-Means Clustering

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. Outliers

5. Bentuk cluster

· Overlapping

Menurut Daniel dan Eko, Langkah-langkah algoritma K-Means adalah sebagai berikut:

· Pilih secara acak k buah data sebagai pusat cluster.

· Jarak antara data dan pusat cluster dihitung menggunakan Euclidean Distance. Untuk menghitung jarak semua data ke setiap titik pusat cluster dapat menggunakan teori jarak Euclidean yang dirumuskan sebagai berikut: dimana: D (i,j) = Jarak data ke i ke pusat cluster j Xki = Data ke i pada atribut data ke k Xkj = Titik pusat ke j pada atribut ke k

· Data ditempatkan dalam cluster yang terdekat, dihitung dari tengah cluster.

· Pusat cluster baru akan ditentukan bila semua data telah ditetapkan dalam cluster terdekat.

· Proses penentuan pusat cluster dan penempatan data dalam cluster diulangi sampai nilai centroid tidak berubah lagi.

C. Langkah – Langkah Algortima K-Means

Algoritma untuk melakukan K-Means clustering adalah sebagai berikut

1. Pilih K buah titik centroid secara acak

2. Kelompokkan data sehingga terbentuk K buah cluster dengan titik centroid dari setiap cluster merupakan titik centroid yang telah dipilih sebelumnya

3. Perbaharui nilai titik centroid

4. Ulangi langkah 2 dan 3 sampai nilai dari titik centroid tidak lagi berubah

Proses pengelompokkan data ke dalam suatu cluster dapat dilakukan dengan cara menghitung jarak terdekat dari suatu data ke sebuah titik centroid.

D. Contoh aplikasi K-means

Contoh penggunaan K-means clustering antara lain:

· Segmentasi pasar (market segmentation)

· Segmentasi citra

· Kompresi gambar

· Klasifikasi citra penginderaan jauh

Seperti metode clustering lainnya, K-means digunakan dalam penelitian eksploratori, confirmatori dan eksplanatori. Untuk tujuan-tujuan eksploratori, k-means dapat dimanfaatkan untuk melengkapi proses Exploratory Data Analysis (EDA), selain menggunakan analisis statistik deskriptif dan visualisasi data. Sedangkan dalam proses confirmatori dan eksplanatori, K-means clustering dapat digunakan untuk melakukan konfirmasi terhadap teori-teori yang sudah ada. Selain itu, algoritma ini juga digunakan untuk melakukan identifikasi jika tiba-tiba terjadi perubahan cluster setelah data baru masuk. Pada tahap terakhir, hasil cluster dapat digunakan sebagai dasar melakukan strategi atau kebijakan terhadap suatu masalah tertentu yang dikaji.

E. Metode algoritma K-means clustering (step by step)

Algoritma K-means clustering dilakukang dengan proses sebagai berikut:

1. LANGKAH 1: TENTUKAN JUMLAH CLUSTER (K). Dalam contoh ini, kita tetapkan bahwa K =3

2. LANGKAH 2: PILIH TITIK ACAK SEBANYAK K. Titik ini merupakan titik seed dan akan menjadi titik centroid proses pertama. Titik ini tidak harus titik data kita

3. LANGKAH 3: LABEL SEMUA DATA BERDASARKAN TITIK CENTROID TERDEKAT. Semua data diberikan label mengikuti titik centroid dari setiap klaster. Perhitungan jarak ini bisa menggunakan algoritma jarak tertentu, secara default dilakukan dengan Euclidean Distance

4. LANGKAH 4: TENTUKAN TITIK CENTROID BARU BERDASARKAN CLUSTER YANG TERBENTUK. Titik centroid selanjutnya “berpindah” ke lokasi centroid setiap cluster yang telah terbentuk.

5. LANGKAH 5: LABEL ULANG DATA BERDASARKAN JARAK TERDEKAT TERHADAP CENTROID BARU. Langkah ini merupakan langkah yang sama dengan langkah ketiga. Perhatikan titik data yang diberikan tanda panah, berubah dari cluster merah ke cluster biru.

6. LANGKAH 6: ULANGI LANGKAH 4 DAN LANGKAH 5 SAMPAI TIDAK ADA PERGERAKAN LAGI. Secara berulang, algoritma akan mencari lokasi centroid baru dan melabel data berdasarkan centroid tersebut sampai mendapat hasil final, yaitu tidak ada lagi perpindahan centroid di setiap cluster.

Untuk lebih jelasnya, lihat penjelasan dan ilustrasi dalam gambar di bawah ini. Klik kanan dan pilih Open image in new tab untuk gambar yang lebih besar.

Selain jumlah klaster (K), parameter yang penting yang harus ditentukan oleh analis adalah bagaimana jarak antara titik ke centroid (lihat lankah 3 dan 5). Dalam k-means clustering, jarak ini dapat diukur menggunakan jarak:

· Euclidean distance

· Manhattan distance

· A squared euclidean distance measure

· Cosine distance measure

Pemilihan metode pengukuran jarak ini akan mempengaruhi bagaimana algoritma menghitung kesamaan dalam klaster dan bentuk klaster. Kita sebagai analis harus dapat menentukan pengukuran jarak mana yang paling sesuai dengan kasus kita. Meskipun demikian, sebagian besar k-means dilakukan dengan pengukuran jarak euclidean (default).

F. Kapan menggunakan K-MEANS CLUSTERING

K-means clustering dapat kita gunakan jika kita melakukan pengelompokkan data berdasarkan variabel tertentu, di mana kita belum dapat menentukan kelas outputnya seperti apa (unsupervised learning). Algoritma ini dapat kita gunakan jika kita dihadapkan pada maslah yang penyelaesaiannya membutuhkan proses segmentasi atau pengelompokkan menjadi subgroup tertentu, seperti analisis pasar dan pelanggan.

Algoritma ini dapat kita gunakan saat melakukan pembacaan intuitif terhadap data yang baru kita dapatkan. Selain itu, kita juga dapat memanfaatkan algoritma k-means clustering dalam proses Exploratory Data Analysis (EDA) untuk melengkapi proses analisis statistika deskriptif dan visualisasi data.

G. Syarat-syarat dan asumsi

Untuk dapat menjalankan K-means clustering, ada beberapa asumsi yang harus dipenuhi, di antaranya:

1. Tidak ada outlier dalam data kita

2. Sampel kita mewakili keseluruhan populasi.

3. Tidak ada multikolinieritas antara variabel/ feature

H. Kelebihan dan keunggulan

Berikut ini adalah kelebihan-kelebihan atau keunggulan algoritma K-means clustering:

· Algoritma yang sederhana dan mudah dipahami

· Cepat pemrosesannya

· Tersedia di berbagai tools atau software

· Mudah dalam penerapannya

· Selalu memberikan hasil, apapun datanya.

· Mudah untuk diimplementasikan dan dijalankan.

· Waktu yang dibutuhkan untuk menjalankan pembelajaran ini relatif cepat.

· Mudah untuk diadaptasi.

· Umum digunakan.

I. Kelemahan dan kekurangan

Sedangkan kelemahan atau kekurangan algoritma K-means clustering:

1. Hasilnya sensitif terhadap jumlah cluster (K). Solusinya, dapat dengan menggunakan Elbow Method, dengan menghitung dan membandingkan nilai WCSS. Lihat penjelasannya di bawah.

2. Sensitif terhadap inisialisasi “seed”. Untuk mengatasi ini, kita bisa menerapkan algoritma K-means ++

3. Sensitif terhadap pencilan atau outlier. Solusi untu masalah ini adalah dengan menghapus outlier dengan hati-hati dan berbagai pertimbangan.

4. Sensitif terhadap data dengan variabel yang memiliki skala berbeda. Maka, sebaiknya kita selalu melakukan scale atau standardisasi data sebelum melakukan k-means clustering. Satu kondisi di mana sebaikany kita tidak melakukan standardisasi data adalah ketika satu variabel memiliki bobot atau nilai penting yang lebih tinggi daripada yang lain.

5. Mengasumsikan setiap klaster berbentuk menyerupai lingkaran (spherical) dan kesulitan jika bentuk cluster yang memiliki bentuk berbeda.

6. Sebelum algoritma dijalankan, k buah titik diinisialisasi secara random sehingga pengelompokkan data yang dihasilkan dapat berbeda-beda. Jika nilai random untuk inisialisasi kurang baik, maka pengelompokkan yang dihasilkan pun menjadi kurang optimal.

7. Dapat terjebak dalam masalah yang disebut curse of dimensionality. Hal ini dapat terjadi jika data pelatihan memiliki dimensi yang sangat tinggi (Contoh jika data pelatihan terdiri dari 2 atribut maka dimensinya adalah 2 dimensi. Namun jika ada 20 atribut, maka akan ada 20 dimensi). Salah satu cara kerja algoritma ini adalah mencari jarak terdekat antara k buah titik dengan titik lainnya. Jika mencari jarak antar titik pada 2 dimensi, masih mudah dilakukan. Namun bagaimana mencari jarak antar titik jika terdapat 20 dimensi. Hal ini akan menjadi sulit.

8. Jika hanya terdapat beberapa titik sampel data, maka cukup mudah untuk menghitung dan mencari titik terdekat dengan k titik yang diinisialisasi secara random. Namun jika terdapat banyak sekali titik data (misalnya satu milyar buah data), maka perhitungan dan pencarian titik terdekat akan membutuhkan waktu yang lama. Proses tersebut dapat dipercepat, namun dibutuhkan struktur data yang lebih rumit seperti kD-Tree atau hashing.

Wassalamu’alaikum Warahmatullah Wabarakatuh, Sekian dan Terima kasih 😊

Referensi :

1. https://id.wikipedia.org/wiki/K-means

2. https://informatikalogi.com/algoritma-k-means-clustering/

3. https://www.researchgate.net/publication/326849650_PENERAPAN_METODE_K-MEANS_CLUSTERING_PADA_PERUSAHAAN

4. https://ilmukomputer.org/wp-content/uploads/2018/05/agus-k-means-clustering.pdf