Affinity Propagation

"Demokrasi Data: Memilih Ketua (Exemplar) Sendiri"

1. Apa itu Affinity Propagation?

Sebagian besar algoritma clustering meminta kita menentukan jumlah cluster ($K$) di awal. Affinity Propagation tidak perlu! Dia akan menemukan sendiri jumlah cluster yang optimal.

Cara kerjanya unik: Semua titik data dianggap sebagai kandidat "Ketua Geng" (Exemplar). Mereka saling kirim pesan (Message Passing) tentang "Seberapa pantas kamu mewakili saya?"

2. Visualisasi: Dua Jenis Pesan

A
B
C
Responsibility
Availability
Responsibility $r(i,k)$

Pesan dari Anggota ($i$) ke Calon Ketua ($k$):
"Bro, lu pantas banget jadi ketua gue dibanding calon lain!"

Availability $a(i,k)$

Pesan dari Calon Ketua ($k$) ke Anggota ($i$):
"Tenang, gue available kok buat jadi ketua lu (karena banyak yang dukung gue juga)."

3. Logika Algoritma

  1. Inisialisasi: Hitung Similarity Matrix (biasanya negatif jarak kuadrat).
  2. Message Passing: Update nilai Responsibility dan Availability berulang-ulang.
  3. Keputusan: Titik yang nilai $R+A$ nya positif akan terpilih menjadi Exemplar (Pusat Cluster).
  4. Titik lain akan bergabung ke Exemplar terdekat.

4. Implementasi Python (Scikit-Learn)

from sklearn.cluster import AffinityPropagation
import numpy as np

# 1. Data Dummy (3 kelompok)
X = [[1, 2], [1, 4], [1, 0],
     [4, 2], [4, 4], [4, 0],
     [10, 2], [10, 4], [10, 0]]

# 2. Model
# Preference: Parameter penting! Semakin kecil (negatif), semakin sedikit cluster yang terbentuk.
# damping: Faktor peredam osilasi (0.5 - 1.0)
af = AffinityPropagation(preference=-50, random_state=0)

# 3. Training
clustering = af.fit(X)

# 4. Hasil
print("Cluster Centers Indices:", clustering.cluster_centers_indices_)
# Output indeks titik mana yang jadi ketua

print("Labels:", clustering.labels_)
# Output label setiap titik