Memahami Konsep Matematika Clustering dan Algoritma K-Means | Radarhot com
phone: +62 822-1002-7724
e-mail: dfn@dr.com

Memahami Konsep Matematika Clustering dan Algoritma K-Means


Memahami Konsep Matematika Clustering dan Algoritma K-Means



Memahami Konsep Matematika Clustering dan Algoritma K-Means

Pengantar

Dalam dunia digital yang semakin kompleks, kemampuan untuk mengelompokkan dan mengorganisir data menjadi semakin penting. Clustering, sebagai salah satu cabang ilmu data mining, menawarkan solusi untuk mengidentifikasi dan memahami pola-pola tersembunyi dalam kumpulan data yang besar dan beragam. Salah satu algoritma clustering yang paling populer dan banyak digunakan adalah K-Means.

Dalam posting blog ini, kita akan menyelami konsep matematika di balik clustering dan membahas algoritma K-Means secara mendalam. Kita akan memahami bagaimana algoritma ini bekerja, apa kelebihan dan kekurangannya, serta bagaimana mengimplementasikannya dalam praktik. Jadi, mari kita mulai perjalanan ini dan memperdalam pemahaman kita tentang clustering dan algoritma K-Means.

Apa itu Clustering?

Clustering adalah proses pengelompokan sekumpulan objek atau data ke dalam kelompok-kelompok yang memiliki kemiripan atau kesamaan karakteristik. Tujuan utama clustering adalah untuk mengidentifikasi pola-pola atau struktur alami yang terdapat dalam data, sehingga objek-objek yang serupa dapat dikelompokkan bersama-sama.

Clustering berbeda dengan klasifikasi, di mana pada klasifikasi, kita sudah mengetahui kategori atau label dari data sebelumnya. Dalam clustering, kita tidak memiliki informasi awal tentang kategori atau label data, sehingga algoritma harus menemukan pengelompokan yang optimal berdasarkan kesamaan karakteristik data.

Clustering memiliki banyak aplikasi dalam berbagai bidang, seperti:

  1. Segmentasi pasar: Mengidentifikasi segmen-segmen pelanggan yang memiliki karakteristik serupa untuk strategi pemasaran yang lebih efektif.
  2. Analisis pola belanja: Mengelompokkan pelanggan berdasarkan perilaku belanja mereka untuk memahami preferensi dan tren konsumen.
  3. Deteksi kecurangan: Mengelompokkan transaksi keuangan untuk mengidentifikasi aktivitas yang mencurigakan atau anomali.
  4. Analisis dokumen: Mengelompokkan dokumen berdasarkan topik atau konten untuk memudahkan pencarian dan pengorganisasian informasi.
  5. Bioinformatika: Mengelompokkan gen atau protein berdasarkan fungsi atau struktur untuk memahami proses biologis.

Konsep Matematika di Balik Clustering

Secara matematis, clustering dapat diformulasikan sebagai berikut:

Diberikan sebuah kumpulan data X = {x1, x2, ..., xn}, di mana xi adalah vektor fitur dari objek ke-i. Tujuan clustering adalah untuk menemukan partisi optimal C = {C1, C2, ..., Ck} dari X, di mana Ci adalah klaster ke-i, sedemikian sehingga objek-objek dalam satu klaster memiliki kesamaan yang tinggi, sementara objek-objek di antara klaster memiliki perbedaan yang tinggi.

Untuk mencapai tujuan ini, kita perlu mendefinisikan suatu fungsi objektif yang akan diminimalkan atau dimaksimalkan. Fungsi objektif yang paling umum digunakan adalah fungsi jarak atau jarak Euclidean, yang didefinisikan sebagai:

J = Σ Σ || xi - μj ||^2

di mana:

  • J adalah fungsi objektif yang akan diminimalkan
  • xi adalah vektor fitur objek ke-i
  • μj adalah centroid (pusat) klaster ke-j
  • || xi - μj || adalah jarak Euclidean antara objek xi dan centroid μj

Tujuan clustering adalah untuk menemukan partisi C yang meminimalkan nilai J, sehingga objek-objek dalam satu klaster memiliki jarak yang dekat dengan centroidnya, sementara objek-objek di antara klaster memiliki jarak yang jauh.

Selain jarak Euclidean, terdapat beberapa metrik jarak lain yang dapat digunakan, seperti jarak Manhattan, jarak Chebyshev, atau jarak Mahalanobis, tergantung pada karakteristik data dan tujuan clustering.

Algoritma K-Means

Salah satu algoritma clustering yang paling populer dan banyak digunakan adalah algoritma K-Means. Algoritma ini bekerja dengan cara mengelompokkan objek-objek ke dalam K klaster berdasarkan kesamaan karakteristik.

Langkah-langkah algoritma K-Means adalah sebagai berikut:

  1. Tentukan jumlah klaster (K) yang diinginkan.
  2. Inisialisasi K centroid (pusat klaster) secara acak.
  3. Alokasikan setiap objek ke klaster yang memiliki centroid terdekat berdasarkan jarak Euclidean.
  4. Hitung ulang centroid baru untuk setiap klaster berdasarkan objek-objek yang termasuk dalam klaster tersebut.
  5. Ulangi langkah 3 dan 4 hingga centroid tidak berubah lagi atau kriteria konvergensi terpenuhi.

Secara matematis, algoritma K-Means dapat ditulis sebagai berikut:

Inisialisasi K centroid secara acak: μ1, μ2, ..., μK
Repeat:
    Alokasikan setiap objek xi ke klaster Cj yang memiliki centroid terdekat:
        Cj = {xi | || xi - μj || ≤ || xi - μk || untuk semua k ≠ j}
    Hitung ulang centroid baru untuk setiap klaster:
        μj = (1/|Cj|) Σ xi, untuk xi ∈ Cj
Until centroid tidak berubah lagi

Algoritma ini akan terus berjalan hingga kriteria konvergensi terpenuhi, yaitu ketika centroid klaster tidak berubah lagi atau perubahan yang terjadi sudah cukup kecil.

Kelebihan dan Kekurangan Algoritma K-Means

Algoritma K-Means memiliki beberapa kelebihan dan kekurangan, yaitu:

Kelebihan:

  1. Sederhana dan efisien secara komputasi, sehingga dapat digunakan pada dataset yang besar.
  2. Mudah diimplementasikan dan dapat beradaptasi dengan berbagai jenis data.
  3. Menghasilkan klaster yang kompak dan terpisah dengan baik.
  4. Dapat menangani data numerik dengan baik.

Kekurangan:

  1. Sensitif terhadap nilai awal centroid yang dipilih secara acak, sehingga dapat menghasilkan solusi yang berbeda-beda.
  2. Jumlah klaster (K) harus ditentukan sebelumnya, yang tidak selalu mudah dilakukan.
  3. Tidak dapat menangani data dengan bentuk klaster yang tidak-hiper-elipsoidal (non-convex) dengan baik.
  4. Rentan terhadap outlier, yang dapat mempengaruhi posisi centroid.
  5. Tidak dapat menangani data dengan densitas klaster yang berbeda-beda.

Untuk mengatasi beberapa kekurangan ini, telah dikembangkan berbagai variasi dan perbaikan algoritma K-Means, seperti K-Medoids, K-Harmonic Means, dan Fuzzy C-Means.

Implementasi Algoritma K-Means

Untuk mengimplementasikan algoritma K-Means, kita dapat menggunakan berbagai bahasa pemrograman, seperti Python, R, atau MATLAB. Berikut adalah contoh implementasi sederhana dalam Python menggunakan library scikit-learn:

from sklearn.cluster import KMeans
import numpy as np

# Generate sample data
X = np.array([[1, 2], [1, 4], [1, 0], [4, 2], [4, 0], [4, 4]])

# Apply K-Means clustering
kmeans = KMeans(n_clusters=3, random_state=0).fit(X)

# Get cluster labels and centroids
labels = kmeans.labels_
centroids = kmeans.cluster_centers_

# Print results
print("Cluster Labels:", labels)
print("Cluster Centroids:", centroids)

Dalam contoh di atas, kita menggunakan library sklearn.cluster.KMeans untuk menerapkan algoritma K-Means pada data sampel. Kita menentukan jumlah klaster (K=3) dan menjalankan algoritma. Hasilnya berupa label klaster untuk setiap objek dan posisi centroid untuk masing-masing klaster.

Selain itu, kita juga dapat menggunakan visualisasi untuk melihat hasil clustering, seperti:

import matplotlib.pyplot as plt

# Plot data points and cluster centroids
plt.scatter(X[:, 0], X[:, 1], c=labels)
plt.scatter(centroids[:, 0], centroids[:, 1], marker='x', s=200, c='r')
plt.title("K-Means Clustering")
plt.show()

Hasil visualisasi akan menunjukkan data points yang dikelompokkan ke dalam klaster-klaster yang berbeda, serta posisi centroid untuk masing-masing klaster.

Aplikasi Algoritma K-Means dalam Dunia Nyata

Algoritma K-Means memiliki banyak aplikasi dalam dunia nyata, di antaranya:

  1. Segmentasi Pasar: Perusahaan dapat menggunakan K-Means untuk mengelompokkan pelanggan berdasarkan karakteristik demografis, perilaku belanja, atau preferensi, sehingga dapat mengembangkan strategi pemasaran yang lebih efektif untuk setiap segmen.

  2. Analisis Pola Belanja: Pengecer dapat menerapkan K-Means untuk mengidentifikasi kelompok pelanggan dengan pola belanja yang serupa, membantu mereka dalam perencanaan stok, penempatan produk, dan promosi yang lebih baik.

  3. Deteksi Kecurangan: Lembaga keuangan dapat menggunakan K-Means untuk mengelompokkan transaksi keuangan dan mengidentifikasi aktivitas yang menyimpang atau mencurigakan, membantu dalam mendeteksi dan mencegah kecurangan.

  4. Analisis Dokumen: Perpustakaan digital atau mesin pencari dapat menerapkan K-Means untuk mengelompokkan dokumen berdasarkan topik atau konten, memudahkan pencarian dan pengorganisasian informasi.

  5. Bioinformatika: Peneliti dalam bidang bioinformatika dapat menggunakan K-Means untuk mengelompokkan gen atau protein berdasarkan fungsi atau struktur, membantu dalam memahami proses biologis dan menemukan wawasan baru.

  6. Analisis Citra: Dalam pengolahan citra, K-Means dapat digunakan untuk segmentasi citra, di mana objek-objek dalam citra dikelompokkan berdasarkan fitur visual seperti warna, tekstur, atau bentuk.

  7. Rekomendasi Produk: Dalam sistem rekomendasi, K-Means dapat digunakan untuk mengelompokkan pengguna berdasarkan preferensi atau perilaku, membantu dalam memberikan rekomendasi produk atau layanan yang lebih relevan.

Contoh-contoh di atas menunjukkan bahwa algoritma K-Means memiliki banyak aplikasi yang luas dalam berbagai bidang, dari pemasaran dan keuangan hingga bioinformatika dan pengolahan citra.

Clustering atau pengelompokan adalah teknik dalam pembelajaran mesin yang bertujuan untuk mengelompokkan data ke dalam beberapa grup atau kluster berdasarkan kemiripan atau kedekatan karakteristiknya. Salah satu algoritma yang paling populer untuk melakukan clustering adalah K-Means. Di bawah ini, kita akan mengeksplorasi konsep matematika dari clustering dan algoritma K-Means.

1. Konsep Clustering

Clustering adalah proses mengelompokkan sekumpulan objek sedemikian rupa sehingga objek-objek dalam satu grup (disebut kluster) lebih mirip satu sama lain daripada objek-objek di grup lain (kluster lain). Mirip di sini bisa diartikan sebagai kedekatan atau kesamaan dalam hal fitur atau karakteristik.

2. Algoritma K-Means

K-Means adalah algoritma clustering yang berusaha mempartisi nn pengamatan ke dalam kk kluster di mana setiap pengamatan termasuk ke dalam kluster dengan mean terdekat (titik pusat kluster atau centroid).

Langkah-langkah Algoritma K-Means:

  1. Inisialisasi:

    • Pilih kk centroid secara acak dari dataset.

  2. Penugasan Kluster:

    • Untuk setiap titik data, hitung jarak ke masing-masing centroid dan tetapkan titik data ke kluster dengan centroid terdekat.

  3. Pembaruan Centroid:

    • Setelah semua titik data ditetapkan ke kluster, hitung mean dari titik-titik data dalam setiap kluster dan gunakan mean ini sebagai centroid baru.

  4. Iterasi:

    • Ulangi langkah 2 dan 3 sampai centroid tidak berubah (konvergensi) atau jumlah iterasi maksimum tercapai.

Rumus Matematika:

  1. Jarak Euclidean:

    • Jarak antara dua titik xix_i  dan μj\mu_j  (centroid) di ruang dimensi dd : d(xi,μj)=∑m=1d(xim−μjm)2d(x_i, \mu_j) = \sqrt{\sum_{m=1}^{d} (x_{im} - \mu_{jm})^2}

  2. Fungsi Objektif:

    • Algoritma K-Means berusaha meminimalkan fungsi objektif yang dikenal sebagai "jumlah total kesalahan kuadrat" (sum of squared errors, SSE): J=∑j=1k∑xi∈Cj∥xi−μj∥2J = \sum_{j=1}^{k} \sum_{x_i \in C_j} \| x_i - \mu_j \|^2 
    • Di mana CjC_j adalah kluster j  dan Î¼j\mu_j  adalah centroid dari kluster jj 

Contoh Sederhana:

Misalkan kita memiliki tiga titik data dalam dua dimensi:

  • A=(1,1)A = (1, 1) 
  • B=(2,1)B = (2, 1) 
  • C=(4,3)C = (4, 3) 

Kita ingin mengelompokkan titik data ini ke dalam dua kluster (k=2 ).

Langkah-langkah:

  1. Inisialisasi:

    • Pilih dua centroid secara acak, misalnya:
      • Centroid 1: (1,1) 
      • Centroid 2: (4,3)(4, 3) 

  2. Penugasan Kluster:

    • Hitung jarak setiap titik ke setiap centroid:

      • d(A,(1,1))=0d(A, (1, 1)) = 0 
      • d(A,(4,3))=(4−1)2+(3−1)2=9+4=13d(A, (4, 3)) = \sqrt{(4-1)^2 + (3-1)^2} = \sqrt{9 + 4} = \sqrt{13}
      • d(B,(1,1))=(2−1)2+(1−1)2=1=1d(B, (1, 1)) = \sqrt{(2-1)^2 + (1-1)^2} = \sqrt{1} = 1 
      • d(B,(4,3))=(4−2)2+(3−1)2=4+4=8 ​
      • d(C,(1,1))=(4−1)2+(3−1)2=13d(C, (1, 1)) = \sqrt{(4-1)^2 + (3-1)^2} = \sqrt{13}
      • d(C,(4,3))=0d(C, (4, 3)) = 0 

    • Berdasarkan jarak terdekat, tetapkan titik data ke kluster:

      • AA  ke Centroid 1
      • BB  ke Centroid 1
      • C  ke Centroid 2

  3. Pembaruan Centroid:

    • Hitung mean dari setiap kluster:
      • Centroid baru 1: (1+22,1+12)=(1.5,1) 
      • Centroid baru 2: (4,3)(4, 3) 

  4. Iterasi:

    • Ulangi langkah 2 dan 3 sampai konvergensi.

Implementasi dalam Python

Berikut adalah implementasi sederhana algoritma K-Means dalam Python menggunakan library scikit-learn:

python
 
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

# Data
data = np.array([[1, 1], [2, 1], [4, 3]])

# Model K-Means
kmeans = KMeans(n_clusters=2, random_state=0).fit(data)

# Hasil
labels = kmeans.labels_
centroids = kmeans.cluster_centers_

# Plot hasil K-Means
plt.scatter(data[:, 0], data[:, 1], c=labels, s=50, cmap='viridis')
plt.scatter(centroids[:, 0], centroids[:, 1], c='red', s=200, alpha=0.5)
plt.title('K-Means Clustering')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()

Kode di atas akan menghasilkan plot yang menunjukkan titik data dan centroid kluster yang ditemukan oleh algoritma K-Means.

Contoh Soal

Berikut adalah lima soal matematika tentang Clustering dan Algoritma K-Means, beserta pembahasan dan jawabannya:

Soal 1

Diberikan tiga titik data dalam dua dimensi: (1,1)(1, 1) , (2,1)(2, 1) , (4,3)(4, 3) . Terapkan satu iterasi algoritma K-Means dengan k=2k = 2  dan centroid awal (1,1)(1, 1)  dan (4,3)(4, 3) .

Pembahasan:

  1. Hitung Jarak Euclidean:

    • Jarak titik (1,1)(1, 1) ke centroid (1,1)(1, 1) adalah 0.
    • Jarak titik (1,1)(1, 1) ke centroid (4,3)(4, 3) adalah (4−1)2+(3−1)2=9+4=13\sqrt{(4-1)^2 + (3-1)^2} = \sqrt{9 + 4} = \sqrt{13}
    • Jarak titik (2,1)(2, 1) ke centroid (1,1)(1, 1) adalah (2−1)2+(1−1)2=1=1\sqrt{(2-1)^2 + (1-1)^2} = \sqrt{1} = 1
    • Jarak titik (2,1)(2, 1)  ke centroid (4,3)(4, 3) adalah (4−2)2+(3−1)2=4+4=8\sqrt{(4-2)^2 + (3-1)^2} = \sqrt{4 + 4} = \sqrt{8}
    • Jarak titik (4,3)  ke centroid (1,1)(1, 1) adalah (4−1)2+(3−1)2=13\sqrt{(4-1)^2 + (3-1)^2} = \sqrt{13}
    • Jarak titik (4,3)(4, 3)  ke centroid (4,3)(4, 3)  adalah 0.

  2. Penugasan Kluster:

    • Titik (1,1)(1, 1) lebih dekat ke centroid (1,1)(1, 1) 
    • Titik (2,1)(2, 1)  lebih dekat ke centroid (1,1)(1, 1) .
    • Titik (4,3)(4, 3) lebih dekat ke centroid (4,3)(4, 3) 

  3. Pembaruan Centroid:

    • Kluster 1 terdiri dari titik (1,1)(1, 1) dan (2,1) , centroid baru adalah (1+22,1+12)=(1.5,1)\left(\frac{1+2}{2}, \frac{1+1}{2}\right) = (1.5, 1) 
    • Kluster 2 terdiri dari titik (4,3) , centroid tetap (4,3) .

Jawaban:

  • Centroid baru setelah satu iterasi adalah (1.5,1)(1.5, 1) dan (4,3)(4, 3) 

Soal 2

Diberikan empat titik data dalam dua dimensi: (1,1)(1, 1), (2,2)(2, 2) , (3,3)(3, 3), (8,8)(8, 8). Terapkan satu iterasi algoritma K-Means dengan k=2k = 2 dan centroid awal (1,1)(1, 1) dan (8,8)(8, 8) .

Pembahasan:

  1. Hitung Jarak Euclidean:

    • Jarak titik (1,1)  ke centroid (1,1)  adalah 0.
    • Jarak titik (1,1)(1, 1) ke centroid (8,8)(8, 8) adalah (8−1)2+(8−1)2=49+49=98=72\sqrt{(8-1)^2 + (8-1)^2} = \sqrt{49 + 49} = \sqrt{98} = 7\sqrt{2}
    • Jarak titik (2,2)(2, 2) ke centroid (1,1)(1, 1) adalah (2−1)2+(2−1)2=1+1=2\sqrt{(2-1)^2 + (2-1)^2} = \sqrt{1 + 1} = \sqrt{2}.
    • Jarak titik (2,2) ke centroid (8,8)(8, 8) adalah (8−2)2+(8−2)2=36+36=72=62
    • Jarak titik (3,3)(3, 3) ke centroid (1,1) adalah (3−1)2+(3−1)2=4+4=8=22\sqrt{(3-1)^2 + (3-1)^2} = \sqrt{4 + 4} = \sqrt{8} = 2\sqrt{2}
    • Jarak titik (3,3) ke centroid (8,8)(8, 8) adalah (8−3)2+(8−3)2=25+25=50=52\sqrt{(8-3)^2 + (8-3)^2} = \sqrt{25 + 25} = \sqrt{50} = 5\sqrt{2}.
    • Jarak titik (8,8)(8, 8) ke centroid (1,1)(1, 1) adalah 727\sqrt{2}
    • Jarak titik (8,8)(8, 8) ke centroid (8,8)(8, 8)adalah 0.

  2. Penugasan Kluster:

    • Titik (1,1), (2,2)(2, 2), dan (3,3)(3, 3) lebih dekat ke centroid (1,1)(1, 1).
    • Titik (8,8)(8, 8) lebih dekat ke centroid (8,8)

  3. Pembaruan Centroid:

    • Kluster 1 terdiri dari titik (1,1)(1, 1), (2,2), dan (3,3)(3, 3), centroid baru adalah (1+2+33,1+2+33)=(2,2)\left(\frac{1+2+3}{3}, \frac{1+2+3}{3}\right) = (2, 2).
    • Kluster 2 terdiri dari titik (8,8)(8, 8), centroid tetap (8,8).

Jawaban:

  • Centroid baru setelah satu iterasi adalah (2,2) dan (8,8)(8, 8)

Soal 3

Diberikan lima titik data dalam dua dimensi: (1,2)(1, 2), (1,4)(1, 4), (5,6)(5, 6), (8,8)(8, 8), (9,10)(9, 10). Terapkan satu iterasi algoritma K-Means dengan k=3k = 3 dan centroid awal (1,2)(1, 2), (5,6)(5, 6), dan (8,8)(8, 8).

Pembahasan:

  1. Hitung Jarak Euclidean:

    • Jarak titik (1,2)ke centroid (1,2)(1, 2) adalah 0.
    • Jarak titik (1,2)(1, 2)  ke centroid (5,6)(5, 6) adalah (5−1)2+(6−2)2=16+16=32=42\sqrt{(5-1)^2 + (6-2)^2} = \sqrt{16 + 16} = \sqrt{32} = 4\sqrt{2}.
    • Jarak titik (1,2)(1, 2)  ke centroid (8,8) adalah (8−1)2+(8−2)2=49+36=85\sqrt{(8-1)^2 + (8-2)^2} = \sqrt{49 + 36} = \sqrt{85}
    • Jarak titik (1,4)(1, 4) ke centroid (1,2) adalah (1−1)2+(4−2)2=4=2\sqrt{(1-1)^2 + (4-2)^2} = \sqrt{4} = 2 
    • Jarak titik (1,4)  ke centroid (5,6)(5, 6) adalah (5−1)2+(6−4)2=16+4=20=25\sqrt{(5-1)^2 + (6-4)^2} = \sqrt{16 + 4} = \sqrt{20} = 2\sqrt{5}.
    • Jarak titik (1,4)  ke centroid (8,8)(8, 8)  adalah (8−1)2+(8−4)2=49+16=65\sqrt{(8-1)^2 + (8-4)^2} = \sqrt{49 + 16} = \sqrt{65}.
    • Jarak titik (5,6)(5, 6) ke centroid (1,2)(1, 2)adalah 424\sqrt{2}.
    • Jarak titik (5,6)(5, 6) ke centroid (5,6)  adalah 0.
    • Jarak titik (5,6)(5, 6)  ke centroid (8,8)(8, 8)  adalah (8−5)2+(8−6)2=9+4=13\sqrt{(8-5)^2 + (8-6)^2} = \sqrt{9 + 4} = \sqrt{13}.
    • Jarak titik (8,8)  ke centroid (1,2)  adalah 85\sqrt{85} 
    • Jarak titik (8,8)(8, 8) ke centroid (5,6)  adalah 13 
    • Jarak titik (8,8)  ke centroid (8,8)  adalah 0.
    • Jarak titik (9,10)(9, 10)  ke centroid (1,2)(1, 2)  adalah (9−1)2+(10−2)2=64+64=128=82\sqrt{(9-1)^2 + (10-2)^2} = \sqrt{64 + 64} = \sqrt{128} = 8\sqrt{2}.
    • Jarak titik (9,10)(9, 10) ke centroid (5,6)(5, 6)  adalah (9−5)2+(10−6)2=16+16=42\sqrt{(9-5)^2 + (10-6)^2} = \sqrt{16 + 16} = 4\sqrt{2}.
    • Jarak titik (9,10)  ke centroid (8,8)  adalah (9−8)2+(10−8)2=1+4=5\sqrt{(9-8)^2 + (10-8)^2} = \sqrt{1 + 4} = \sqrt{5}.

  2. Penugasan Kluster:

    • Titik (1,2)  lebih dekat ke centroid (1,2) 
    • Titik (1,4)(1, 4) lebih dekat ke centroid (1,2)(1, 2) .
    • Titik (5,6) lebih dekat ke centroid (5,6)(5, 6) 
    • Titik (8,8)(8, 8)  lebih dekat ke centroid (8,8)(8, 8) 
    • Titik (9,10)(9, 10)  lebih dekat ke centroid (8,8) 

  3. Pembaruan Centroid:

    • Kluster 1 terdiri dari titik (1,2)  dan (1,4)(1, 4) , centroid baru adalah (1+12,2+42)=(1,3)\left(\frac{1+1}{2}, \frac{2+4}{2}\right) = (1, 3) 
    • Kluster 2 terdiri dari titik (5,6)(5, 6) , centroid tetap (5,6)(5, 6) 
    • Kluster 3 terdiri dari titik  (8, 8) dan (9,10)(9, 10) , centroid baru adalah (8+92,8+102)=(8.5,9)\left(\frac{8+9}{2}, \frac{8+10}{2}\right) = (8.5, 9) 

Jawaban:

  • Centroid baru setelah satu iterasi adalah (1,3) , (5,6) , dan (8.5,9)(8.5, 9) 

Soal 4

Diberikan dataset dengan lima titik data dalam dua dimensi: (2,3)(2, 3), (3,3)(3, 3), (6,8)(6, 8), (7,8)(7, 8), (8,9)(8, 9). Terapkan algoritma K-Means dengan k=2k = 2 dan centroid awal (2,3)(2, 3)dan (7,8)(7, 8)  sampai konvergensi.

Pembahasan:

  1. Inisialisasi:

    • Centroid awal: (2,3)(2, 3) dan (7,8) 

  2. Iterasi 1:

    • Penugasan Kluster:

      • Titik (2,3)(2, 3) lebih dekat ke centroid (2,3) 
      • Titik (3,3)(3, 3) lebih dekat ke centroid (2,3)(2, 3) 
      • Titik (6,8)(6, 8) lebih dekat ke centroid (7,8) 
      • Titik (7,8)(7, 8) lebih dekat ke centroid (7,8) 
      • Titik (8,9)(8, 9)  lebih dekat ke centroid (7,8)(7, 8) 

    • Pembaruan Centroid:

      • Kluster 1 terdiri dari titik (2,3)(2, 3)  dan (3,3)(3, 3) , centroid baru adalah (2+32,3+32)=(2.5,3)\left(\frac{2+3}{2}, \frac{3+3}{2}\right) = (2.5, 3) 
      • Kluster 2 terdiri dari titik (6,8)(6, 8) , (7,8)(7, 8) , dan (8,9) , centroid baru adalah (6+7+83,8+8+93)=(7,8.33) 

  3. Iterasi 2:

    • Penugasan Kluster:

      • Titik (2,3)  lebih dekat ke centroid (2.5,3)(2.5, 3) 
      • Titik (3,3) lebih dekat ke centroid (2.5,3)(2.5, 3) 
      • Titik (6,8)(6, 8) lebih dekat ke centroid (7,8.33) 
      • Titik (7,8) lebih dekat ke centroid (7,8.33) 
      • Titik (8,9)(8, 9) lebih dekat ke centroid (7,8.33)(7, 8.33) 

    • Pembaruan Centroid:

      • Kluster 1 tetap sama: centroid baru adalah (2.5,3)(2.5, 3) 
      • Kluster 2 tetap sama: centroid baru adalah (7,8.33)(7, 8.33) 

    Karena centroid tidak berubah, algoritma telah mencapai konvergensi.

Jawaban:

  • Centroid akhir setelah konvergensi adalah (2.5,3)  dan (7,8.33)(7, 8.33) .

Soal 5

Diberikan enam titik data dalam dua dimensi: (1,2)(1, 2), (1,4)(1, 4) , (3,6)(3, 6), (5,8)(5, 8), (7,10)(7, 10), (9,12)(9, 12). Terapkan algoritma K-Means dengan k=2k = 2 dan centroid awal (1,2)(1, 2)  dan (9,12)(9, 12)  sampai konvergensi.

Pembahasan:

  1. Inisialisasi:

    • Centroid awal: (1,2)(1, 2)  dan (9,12)(9, 12) .

  2. Iterasi 1:

    • Penugasan Kluster:

      • Titik (1,2)(1, 2) lebih dekat ke centroid (1,2) 
      • Titik (1,4)(1, 4)  lebih dekat ke centroid (1,2)(1, 2) 
      • Titik (3,6)(3, 6)  lebih dekat ke centroid (1,2) 
      • Titik (5,8)(5, 8)lebih dekat ke centroid (9,12)(9, 12) 
      • Titik (7,10)(7, 10)  lebih dekat ke centroid (9,12)(9, 12) 
      • Titik (9,12) lebih dekat ke centroid (9,12)(9, 12) 

    • Pembaruan Centroid:

      • Kluster 1 terdiri dari titik (1,2)(1, 2) , (1,4)(1, 4) , dan (3,6) , centroid baru adalah (1+1+33,2+4+63)=(1.67,4) 
      • Kluster 2 terdiri dari titik (5,8) , (7,10) , dan (9,12)(9, 12) , centroid baru adalah (5+7+93,8+10+123)=(7,10)\left(\frac{5+7+9}{3}, \frac{8+10+12}{3}\right) = (7, 10) .

  3. Iterasi 2:

    • Penugasan Kluster:

      • Titik (1,2) lebih dekat ke centroid (1.67,4) 
      • Titik (1,4)(1, 4) lebih dekat ke centroid (1.67,4) 
      • Titik (3,6)(3, 6) lebih dekat ke centroid (1.67,4)(1.67, 4) 
      • Titik (5,8) lebih dekat ke centroid (7,10) 
      • Titik (7,10)(7, 10) lebih dekat ke centroid (7,10)(7, 10) 
      • Titik (9,12)(9, 12)  lebih dekat ke centroid (7,10) 

    • Pembaruan Centroid:

      • Kluster 1 tetap sama: centroid baru adalah (1.67,4) 
      • Kluster 2 tetap sama: centroid baru adalah (7,10)(7, 10) 

    Karena centroid tidak berubah, algoritma telah mencapai konvergensi.

Jawaban:

  • Centroid akhir setelah konvergensi adalah (1.67,4)(1.67, 4) dan (7,10) 

Kesimpulan

Algoritma K-Means adalah metode clustering yang kuat dan sederhana yang digunakan untuk mengelompokkan data berdasarkan kedekatan karakteristiknya. Algoritma ini bekerja dengan iterasi melalui inisialisasi centroid, penugasan kluster, dan pembaruan centroid sampai konvergensi tercapai. K-Means banyak digunakan dalam berbagai aplikasi seperti segmentasi pasar, pengenalan pola, dan analisis data.

Dalam posting blog ini, kita telah menjelajahi konsep matematika di balik clustering dan membahas algoritma K-Means secara mendalam. Kita telah memahami bagaimana algoritma K-Means bekerja, apa kelebihan dan kekurangannya, serta bagaimana mengimplementasikannya dalam praktik.

Clustering, khususnya algoritma K-Means, merupakan alat yang sangat powerful dalam menganalisis dan memahami pola-pola tersembunyi dalam data. Dengan kemampuannya untuk mengelompokkan objek-objek berdasarkan kesamaan karakteristik, algoritma K-Means memiliki banyak aplikasi di berbagai bidang, mulai dari pemasaran hingga bioinformatika.

Meskipun algoritma K-Means memiliki beberapa keterbatasan, seperti sensitifitas terhadap nilai awal centroid dan ketidakmampuan dalam menangani data dengan bentuk klaster yang tidak-hiper-elipsoidal, namun terus dikembangkan berbagai variasi dan perbaikan untuk mengatasi kekurangan-kekurangan tersebut.

Dengan pemahaman yang mendalam tentang konsep matematika clustering dan algoritma K-Means, kita dapat memanfaatkan kekuatan teknik ini untuk mengekstrak wawasan yang berharga dari data yang kita miliki, dan menggunakannya untuk membuat keputusan yang lebih baik dan lebih informasi.

Tag : , ,

0 Komentar:

Langganan: Posting Komentar (Atom)