Density-Based Clustering (DBSCAN) & Outlier Detection Dasar

Capaian Pembelajaran

Setelah minggu ini kamu bisa:

Menjelaskan mengapa K-Means gagal pada klaster berbentuk arbitrer dan data berderau.
Mendefinisikan ε-neighborhood, titik core, border, dan noise.
Menjalankan DBSCAN secara manual dan mengimplementasikannya dari nol.
Memilih parameter eps menggunakan k-distance plot.
Mendeteksi outlier dengan z-score (univariat) dan Local Outlier Factor (multivariat).

1. Keterbatasan K-Means

K-Means (Minggu 10) meminimalkan SSE terhadap centroid. Akibatnya:

Asumsi K-Means	Masalah di dunia nyata
Klaster berbentuk bola (sferis) & ukurannya mirip	Klaster bisa memanjang, melengkung (bulan sabit), bersarang (cincin)
Jumlah klaster `k` diketahui	Sering tidak tahu ada berapa kelompok
Setiap titik harus masuk klaster	Noise/outlier ikut ditarik ke klaster → centroid bergeser

   Data "bulan sabit" (make_moons)        Hasil K-Means (k=2)        Hasil DBSCAN
      ooooo                                  AAAAA                      AAAAA
    oo     oo                              AA     AB                  AA     AA
   o    xx   o                            A    BB   B                A    BB   A
         xx    xx                                BB    BB                  BB    BB
          xxxxxx                                  BBBBBB                    BBBBBB
                                       (potong lurus di tengah)    (ikuti bentuk kerapatan)

Ide DBSCAN (Density-Based Spatial Clustering of Applications with Noise, Ester dkk., 1996): klaster = daerah padat yang dipisahkan oleh daerah jarang.

2. Definisi Formal

Dua parameter:

ε (eps) — radius lingkungan.
MinPts — jumlah titik minimum (termasuk titik itu sendiri) agar sebuah daerah dianggap padat.

ε-neighborhood titik p:

N_ε(p) = { q ∈ D  |  dist(p, q) ≤ ε }      (p sendiri termasuk)

Jenis titik:

Jenis	Syarat	Arti
Core	`	N_ε(p)
Border	bukan core, tetapi berada dalam `N_ε` dari suatu core	Pinggiran klaster
Noise	bukan core dan bukan border	Outlier

          ε
       .-----.
     /  •  •   \          ★ = core   (≥ MinPts tetangga)
    |  • ★  •   |  ◆      ◆ = border (tetangga core, tapi dirinya jarang)
     \  •  •   / ◆        ✕ = noise
       '-----'
                       ✕

Relasi keterjangkauan:

Directly density-reachable: q berada di N_ε(p) dan p core.
Density-reachable: ada rantai p = p1 → p2 → … → pn = q yang tiap langkahnya directly density-reachable.
Density-connected: p dan q sama-sama density-reachable dari suatu titik o.

Klaster DBSCAN = himpunan maksimal titik yang saling density-connected.

Catatan konvensi: scikit-learn menghitung titik itu sendiri ke dalam min_samples. Kita mengikuti konvensi yang sama.

3. Algoritma DBSCAN

DBSCAN(D, eps, MinPts):
    label[semua] = BELUM_DIKUNJUNGI
    C = -1
    untuk setiap titik p di D (urut indeks):
        jika label[p] sudah ditentukan: lanjut
        N = regionQuery(p, eps)
        jika |N| < MinPts:
            label[p] = NOISE              # bisa berubah jadi border nanti
            lanjut
        C = C + 1                         # klaster baru
        label[p] = C
        antrian = N \ {p}
        selama antrian tidak kosong:
            q = ambil(antrian)
            jika label[q] == NOISE: label[q] = C          # noise → border
            jika label[q] sudah ditentukan: lanjut
            label[q] = C
            N_q = regionQuery(q, eps)
            jika |N_q| ≥ MinPts:          # q core → perluas
                antrian += N_q
    return label

Kompleksitas: O(n²) dengan pencarian tetangga naif; O(n log n) dengan indeks spasial (KD-tree, Ball-tree, R*-tree).

4. Contoh Hitung Manual

Data 1 dimensi: A=1, B=2, C=3, D=8, E=9, F=10, G=25, dengan eps = 1.5 dan MinPts = 3.

| Titik | N_ε (jarak ≤ 1.5) | |N| | Jenis | |---|---|---|---| | A=1 | {A, B} | 2 | border (tetangga core B) | | B=2 | {A, B, C} | 3 | core | | C=3 | {B, C} | 2 | border | | D=8 | {D, E} | 2 | border | | E=9 | {D, E, F} | 3 | core | | F=10 | {E, F} | 2 | border | | G=25 | {G} | 1 | noise |

Hasil: Klaster 0 = {A, B, C}, Klaster 1 = {D, E, F}, noise = {G}. Kita tidak perlu menentukan k — jumlah klaster muncul sendiri.

5. Memilih eps: k-distance Plot

Tetapkan k = MinPts − 1 (atau MinPts).
Untuk setiap titik, hitung jarak ke tetangga terdekat ke-k (tidak termasuk dirinya).
Urutkan jarak tersebut, lalu plot.
Pilih eps pada titik siku (knee/elbow) — sesudah titik itu jarak naik tajam (titik-titik noise).

 k-dist
   │                                  ╭─  ← noise
   │                               ╭──╯
   │                            ╭──╯   ← "siku": eps ≈ nilai di sini
   │   ─────────────────────────╯
   └──────────────────────────────────── titik (diurutkan)

Aturan praktis MinPts: MinPts ≥ dimensi + 1; untuk data 2D sering dipakai MinPts = 4 atau 2·dimensi.

Penting: DBSCAN berbasis jarak → standarisasi fitur dulu (Minggu 2), kalau tidak fitur berskala besar (misal rupiah) mendominasi.

6. Kelebihan & Kekurangan DBSCAN

Kelebihan	Kekurangan
Tidak perlu menentukan jumlah klaster	Sensitif terhadap pilihan eps & MinPts
Menemukan klaster bentuk arbitrer	Kesulitan jika kerapatan antar klaster sangat berbeda (→ OPTICS, HDBSCAN)
Tahan noise, sekaligus menandai outlier	Kurang baik di dimensi tinggi (jarak jadi tidak informatif)
Hasil deterministik untuk core & noise	Titik border di antara dua klaster bisa bergantung urutan data

Varian: OPTICS (urutan keterjangkauan, banyak eps sekaligus), HDBSCAN (hierarkis, hanya butuh min_cluster_size).

7. Evaluasi Tanpa Label vs Dengan Label

Tanpa label: silhouette score (Minggu 10) — hati-hati, silhouette menyukai klaster sferis sehingga bisa "menghukum" hasil DBSCAN yang benar. Hitung tanpa titik noise.
Dengan label acuan (untuk eksperimen): Adjusted Rand Index (ARI) — 1 = identik dengan label acuan, ≈0 = acak. ARI tidak peduli nama/nomor klaster.

8. Outlier Detection Dasar

Outlier = objek yang menyimpang jauh dari mayoritas sehingga diduga dibangkitkan oleh mekanisme berbeda (Hawkins). Contoh bisnis: transaksi penipuan, sensor rusak, salah input.

8a. Z-score (univariat, parametrik)

z = (x − μ) / σ        outlier jika |z| > 3   (asumsi distribusi ≈ normal)

Contoh: rata-rata transaksi μ = Rp 200rb, σ = Rp 50rb. Transaksi Rp 420rb → z = (420−200)/50 = 4.4 → outlier.

Kelemahan: μ dan σ sendiri terpengaruh outlier (masking). Alternatif robust: IQR (Tukey) dari Minggu 1, atau modified z-score berbasis median & MAD.

8b. Berbasis jarak / kerapatan (multivariat)

Noise DBSCAN — titik yang tidak masuk klaster mana pun.
k-NN distance — skor = jarak ke tetangga ke-k; makin jauh makin anomali.
Local Outlier Factor (LOF) (Breunig dkk., 2000) — membandingkan kerapatan lokal titik dengan kerapatan tetangganya:

reach-dist_k(p, o) = max( k-distance(o), d(p, o) )
lrd_k(p)  = 1 / ( rata-rata reach-dist_k(p, o) untuk o ∈ N_k(p) )
LOF_k(p)  = rata-rata [ lrd_k(o) / lrd_k(p) ]  untuk o ∈ N_k(p)

LOF	Arti
≈ 1	kerapatan sama dengan tetangga → normal
> 1 (mis. 1.5, 2, …)	jauh lebih jarang dari tetangganya → outlier lokal

LOF unggul ketika data punya klaster dengan kerapatan berbeda: titik yang "agak jauh" dari klaster padat tetap terdeteksi, sedangkan titik di klaster yang memang jarang tidak dianggap outlier.

Teknik lanjutan (Isolation Forest, Autoencoder) dibahas di Minggu 16.

9. Aplikasi Bisnis

Kasus	Teknik
Hotspot lokasi pengantaran / titik GPS ojek online	DBSCAN dengan jarak haversine
Segmentasi pelanggan sekaligus menyisihkan pelanggan "aneh"	DBSCAN pada fitur RFM terstandarisasi
Deteksi transaksi kartu kredit mencurigakan	LOF, z-score per nasabah
Kontrol kualitas sensor pabrik	z-score bergerak, LOF

Ringkasan

DBSCAN mengelompokkan berdasarkan kerapatan: core, border, noise.
Hanya butuh eps dan MinPts; jumlah klaster otomatis; bentuk klaster bebas.
Pilih eps dari siku k-distance plot; standarisasi fitur dulu.
Z-score cocok untuk outlier univariat berdistribusi normal; LOF untuk outlier lokal multivariat.

Bacaan

Ester, Kriegel, Sander & Xu (1996) — A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.
Breunig, Kriegel, Ng & Sander (2000) — LOF: Identifying Density-Based Local Outliers.
Han, Kamber & Pei — Data Mining: Concepts and Techniques, Bab 10.4 & 12.

Tugas Minggu Ini

Kerjakan lab.ipynb sampai selesai.
Kerjakan kuis (di web, atau baca quiz.json).
Isi exercise.py, lalu cek: python check.py 11