Stream & Graph Mining

Capaian Pembelajaran

Setelah minggu ini kamu bisa:

1. Menjelaskan karakteristik data stream dan mengapa algoritma klasik tidak cukup.
2. Menghitung statistik dengan sliding window dan exponentially decaying window.
3. Mengambil sampel acak seragam dari stream tak berujung dengan reservoir sampling.
4. Mengukur kemiripan himpunan (Jaccard), membuat MinHash signature, dan memakai LSH untuk mencari pasangan mirip tanpa membandingkan semua pasangan.
5. Menghitung PageRank dengan power iteration termasuk damping factor dan simpul dangling.

1. Data Stream

Data stream = urutan data yang datang terus-menerus, cepat, dan (secara praktis) tidak berujung: klik website, transaksi kartu kredit, sensor IoT, log server, tweet.

Kendala utama: memori terbatas & satu kali lewat. Karena itu kita memakai ringkasan (synopsis): window, sampel, sketsa (sketch), hash.

Contoh teknologi: Apache Kafka (antrian stream), Apache Flink & Spark Structured Streaming (pemrosesan).

2. Sliding Window

Hanya w elemen terakhir yang diperhatikan; elemen lama "jatuh" keluar jendela.

stream : 4  8  6  2  10  3  ...
w = 3  : [4 8 6] → mean 6
            [8 6 2] → mean 5.33
               [6 2 10] → mean 6
                  [2 10 3] → mean 5

Implementasi efisien: simpan jumlah berjalan S. Saat elemen baru x_baru masuk dan x_lama keluar:

S ← S + x_baru − x_lama        (O(1) per elemen, bukan O(w))
mean = S / w

Pakai collections.deque(maxlen=w) untuk menyimpan isi jendela.

Contoh bisnis: rata-rata transaksi 5 menit terakhir untuk mendeteksi lonjakan (fraud), rata-rata suhu 60 detik terakhir di mesin.

3. Exponentially Decaying Window

Alih-alih memotong tajam, semua elemen dihitung tetapi bobotnya meluruh secara eksponensial. Dengan konstanta kecil c (mis. 10⁻⁶ … 0.1):

S_t = Σ_{i=1..t} x_i · (1 − c)^(t − i)

Pembaruan rekursif (cukup simpan satu angka!):

S_t = (1 − c) · S_{t−1} + x_t

Contoh: stream 1, 1, 1 dengan c = 0.5:

• S₁ = 1
• S₂ = 0.5·1 + 1 = 1.5
• S₃ = 0.5·1.5 + 1 = 1.75

Jika seluruh x = 1, S → 1/c (di sini 2). "Lebar efektif" window ≈ 1/c elemen.

Pemakaian: trending topic (hashtag paling populer saat ini), skor popularitas produk yang memudar bila tidak dibeli lagi.

4. Reservoir Sampling

Masalah: ambil k sampel acak seragam dari stream yang panjangnya n tidak diketahui, memakai memori O(k).

Algoritma R (Vitter):

reservoir = k elemen pertama
untuk elemen ke-i (indeks 0-based, i ≥ k):
    j = bilangan acak bulat dalam [0, i]
    jika j < k:  reservoir[j] = elemen ke-i

Peluang elemen ke-i masuk = k/(i+1). Dapat dibuktikan, setelah n elemen, setiap elemen berpeluang tepat k/n berada di reservoir.

Bukti singkat (induksi): elemen lama yang sudah di reservoir pada langkah i bertahan dengan peluang 1 − (k/(i+1))·(1/k) = i/(i+1). Kalikan: k/i · i/(i+1) = k/(i+1). ✔

5. Kemiripan Dokumen: Jaccard, Shingling, MinHash

5.1 Shingling & Jaccard

Dokumen diubah menjadi himpunan shingle (k-gram kata atau karakter). Kemiripan Jaccard:

J(A, B) = |A ∩ B| / |A ∪ B|

Contoh: A = {data, mining, pola}, B = {data, mining, besar, pola, proses} → |A∩B| = 3, |A∪B| = 5 → J = 0.6

Masalah: dengan N dokumen ada N(N−1)/2 pasangan. 1 juta dokumen → ~5·10¹¹ perbandingan. Terlalu mahal!

5.2 MinHash

Ide: pilih permutasi acak π terhadap semua shingle. h_π(A) = shingle pertama A menurut urutan π. Sifat ajaib:

P[ h_π(A) = h_π(B) ] = J(A, B)

Dengan n fungsi hash berbeda kita mendapat signature n angka per dokumen. Estimasi Jaccard = proporsi baris signature yang sama.

Dalam praktik permutasi diganti fungsi hash universal:

h(x) = (a·x + b) mod p      (p bilangan prima besar, a ∈ [1,p), b ∈ [0,p))
minhash(A) = min_{x ∈ A} h(x)

Signature jauh lebih kecil daripada himpunan asli (mis. 100 angka vs ribuan shingle).

5.3 Locality-Sensitive Hashing (LSH) — teknik banding

Signature (n baris) dipotong menjadi b band × r baris (n = b·r). Tiap band di-hash ke bucket. Dua dokumen menjadi pasangan kandidat bila minimal satu band identik.

Peluang dua dokumen dengan Jaccard s menjadi kandidat:

P(kandidat) = 1 − (1 − s^r)^b

Kurva ini berbentuk S. Ambang kira-kira: t ≈ (1/b)^(1/r).

Contoh: b = 20, r = 5 (n = 100)

• s = 0.8 → 1 − (1 − 0.8⁵)²⁰ = 1 − (1 − 0.32768)²⁰ ≈ 0.9996
• s = 0.3 → 1 − (1 − 0.3⁵)²⁰ = 1 − (0.99757)²⁰ ≈ 0.0475

Hanya pasangan kandidat yang dihitung Jaccard sebenarnya → hemat besar. Trade-off: false positive (dokumen tak mirip jadi kandidat) dan false negative (dokumen mirip terlewat) diatur lewat b dan r.

Aplikasi: deteksi plagiarisme, deduplikasi produk e-commerce, rekomendasi "produk serupa", near-duplicate web page.

6. Graph Mining: PageRank

Web/jejaring sosial = graf berarah: simpul (halaman/akun), sisi (tautan/follow). Pertanyaan: simpul mana paling penting?

6.1 Ide "random surfer"

Seorang pengguna klik tautan secara acak. PageRank r(j) = peluang jangka panjang ia berada di halaman j. Halaman penting = ditautkan oleh banyak halaman penting.

r(j) = Σ_{i → j} r(i) / d_out(i)

Dalam bentuk matriks: r = M·r, dengan M[j, i] = 1/d_out(i) bila ada sisi i→j (matriks stokastik kolom).

6.2 Masalah & solusi: teleportasi (damping)

• Dead end / dangling node: simpul tanpa sisi keluar → "peluang bocor".
• Spider trap: sekelompok simpul yang hanya menaut ke dirinya → menyerap seluruh skor.

Solusi Google: dengan peluang d (damping, biasanya 0.85) ikuti tautan, dengan peluang 1 − d loncat ke simpul acak:

r_baru(j) = (1 − d)/N + d · [ Σ_{i → j} r(i)/d_out(i)  +  Σ_{i dangling} r(i)/N ]

Skor simpul dangling dibagi rata ke semua simpul.

6.3 Power iteration

r ← [1/N, …, 1/N]
ulang:
    r_baru ← rumus di atas
    jika Σ|r_baru − r| < toleransi: berhenti
    r ← r_baru

Contoh 1 langkah: graf A→B, A→C, B→C, C→A (N = 3, d = 0.85), mulai r = [1/3, 1/3, 1/3]:

• r(A) = 0.05 + 0.85·(r(C)/1) = 0.05 + 0.85·0.3333 = 0.3333
• r(B) = 0.05 + 0.85·(r(A)/2) = 0.05 + 0.1417 = 0.1917
• r(C) = 0.05 + 0.85·(r(A)/2 + r(B)/1) = 0.05 + 0.85·0.5 = 0.4750

(0.05 = (1 − 0.85)/3.) Jumlah tetap 1. C paling penting karena ditautkan A dan B.

Aplikasi bisnis: influencer marketing (akun berpengaruh), deteksi fraud ring (graf transaksi), rekomendasi (graf produk–pelanggan), analisis jaringan supplier.

Ringkasan

• Stream: satu kali lewat, memori terbatas → gunakan window, sampel, sketsa.
• Sliding window: jumlah berjalan O(1); decaying window: S = (1−c)S + x.
• Reservoir sampling: tiap elemen berpeluang k/n tanpa tahu n.
• Jaccard → MinHash (P[sama] = J) → LSH banding 1 − (1 − s^r)^b.
• PageRank: power iteration + damping 0.85 + distribusi skor dangling.

Bacaan

• Leskovec, Rajaraman & Ullman — Mining of Massive Datasets, Bab 3 (Finding Similar Items), Bab 4 (Mining Data Streams), Bab 5 (Link Analysis).
• Page, Brin dkk. (1999) — The PageRank Citation Ranking: Bringing Order to the Web.

Tugas Minggu Ini

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