Mean-shift Clustering

"Mendaki Bukit Kepadatan (Hill Climbing)"

1. Apa itu Mean-shift?

Jika K-Means harus diberitahu jumlah cluster ($K$), Mean-shift tidak peduli! Dia mencari pusat cluster secara otomatis dengan cara mencari area yang paling padat (banyak titiknya).

Bayangkan Anda tersesat di hutan kabut tebal. Anda ingin mencari keramaian. Strateginya: Di setiap langkah, Anda melihat sekeliling (dalam radius tertentu), lalu melangkah ke arah di mana orangnya lebih banyak. Lama-lama, Anda akan sampai di pusat keramaian.

2. Visualisasi: Sliding Window

Start
↗
Puncak (Dense)

3. Langkah-Langkah Algoritma

  • 1. Inisialisasi: Tebar banyak lingkaran pencarian (Windows) secara acak pada data.
  • 2. Hitung Mean: Dalam setiap lingkaran, hitung rata-rata posisi (Mean) dari semua titik yang ada di dalamnya.
  • 3. Shift (Geser): Geser pusat lingkaran ke posisi Mean baru tersebut. (Lingkaran akan bergerak ke arah yang lebih padat).
  • 4. Konvergensi: Ulangi sampai lingkaran berhenti bergerak (sudah di puncak kepadatan).
  • 5. Penggabungan: Lingkaran yang berakhir di puncak yang sama dianggap satu cluster.

4. Simulasi Perhitungan Manual

Data 1D:

Titik: 1, 2, 8, 9, 10.

Bandwidth (Radius Lingkaran) = 3.

Iterasi 1:

Misal kita mulai window di posisi $x = 2$.

  • Cari Tetangga: Siapa yang jaraknya $\le 3$ dari 2?
    Titik: 1 (jarak 1), 2 (jarak 0). Titik 8 kejauhan (jarak 6).
  • Hitung Mean Tetangga: $\frac{1+2}{2} = 1.5$.
  • Geser: Pusat window pindah dari 2 ke 1.5.
Iterasi 2:

Pusat sekarang di 1.5.

  • Cari Tetangga: Radius 3 dari 1.5 (Range: -1.5 s/d 4.5).
    Titik: 1, 2. (Sama saja).
  • Hitung Mean: 1.5.
  • Geser: Tidak bergerak. Konvergen!

Jadi, titik 1 dan 2 membentuk Cluster 1 pusatnya di 1.5.

Lakukan hal sama jika mulai dari 9, akan ketemu cluster di 9 (rata-rata 8,9,10).

5. Implementasi Python (Scikit-Learn)

from sklearn.cluster import MeanShift
import numpy as np

# 1. Data Dummy
X = np.array([[1, 1], [2, 1], [1, 0],
              [4, 7], [3, 5], [3, 6]])

# 2. Model MeanShift
# bandwidth: radius pencarian (Sangat PENTING!)
# Jika tidak diisi, sklearn akan mengestimasi sendiri (bisa lama).
clustering = MeanShift(bandwidth=2).fit(X)

# 3. Hasil
print("Label:", clustering.labels_)
# Output: [1 1 1 0 0 0]

print("Pusat Cluster:", clustering.cluster_centers_)
# Akan menemukan 2 pusat tanpa kita minta 2.