{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1572292d",
   "metadata": {},
   "source": [
    "# Lab Minggu 15 — Stream & Graph Mining\n",
    "\n",
    "**Tujuan lab:**\n",
    "1. Mensimulasikan data stream dan menghitung sliding window, decaying window, reservoir sampling.\n",
    "2. Mencari dokumen mirip dengan Jaccard → MinHash → LSH.\n",
    "3. Menghitung PageRank dengan power iteration dan membandingkannya dengan NetworkX.\n",
    "\n",
    "Baca `lesson.md` dulu. Jalankan sel satu per satu (Shift+Enter)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "39b18873",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.path.insert(0, \"..\")\n",
    "\n",
    "import random\n",
    "from collections import deque, defaultdict\n",
    "from itertools import combinations\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "\n",
    "from common.datasets import dokumen_teks, jaringan_web, log_transaksi"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c62ddcbe",
   "metadata": {},
   "source": [
    "## 1. Simulasi data stream\n",
    "\n",
    "Kita perlakukan `log_transaksi()` sebagai stream: setiap baris datang satu per satu.\n",
    "Generator Python cocok untuk meniru stream — data tidak dimuat sekaligus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6da573a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def stream_nilai_transaksi():\n",
    "    for baris in log_transaksi():\n",
    "        tgl, kota, produk, jumlah, harga = baris.split(\",\")\n",
    "        yield int(jumlah) * int(harga)\n",
    "\n",
    "s = stream_nilai_transaksi()\n",
    "print([next(s) for _ in range(5)])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e461cf17",
   "metadata": {},
   "source": [
    "## 2. Sliding window dengan jumlah berjalan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9ee0a240",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sliding_mean(stream, w):\n",
    "    jendela, total = deque(maxlen=w), 0.0\n",
    "    for x in stream:\n",
    "        if len(jendela) == w:\n",
    "            total -= jendela[0]\n",
    "        jendela.append(x)\n",
    "        total += x\n",
    "        if len(jendela) == w:\n",
    "            yield total / w\n",
    "\n",
    "nilai = list(stream_nilai_transaksi())[:1000]\n",
    "sw = list(sliding_mean(nilai, 50))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4885774e",
   "metadata": {},
   "source": [
    "## 3. Exponentially decaying window\n",
    "\n",
    "Untuk membandingkan dengan rata-rata, kita pakai *rata-rata berbobot* `S_t · c`\n",
    "(karena jumlah bobot ≈ 1/c)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1c5f608e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def decaying(stream, c):\n",
    "    s = 0.0\n",
    "    for x in stream:\n",
    "        s = (1 - c) * s + x\n",
    "        yield s\n",
    "\n",
    "c = 1 / 50\n",
    "dw = [v * c for v in decaying(nilai, c)]\n",
    "\n",
    "plt.figure(figsize=(12, 3.5))\n",
    "plt.plot(nilai, alpha=0.25, label=\"nilai transaksi\")\n",
    "plt.plot(range(49, 1000), sw, label=\"sliding window (w=50)\")\n",
    "plt.plot(dw, label=\"decaying window (c=1/50)\")\n",
    "plt.legend(); plt.title(\"Ringkasan stream\"); plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "547278eb",
   "metadata": {},
   "source": [
    "Decaying window bereaksi halus dan tidak butuh menyimpan 50 elemen — cukup **satu angka**.\n",
    "\n",
    "### Trending produk dengan decaying window\n",
    "Setiap produk punya skor sendiri; skor semua produk meluruh tiap ada transaksi baru."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a2501a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def trending(stream_baris, c=0.01):\n",
    "    skor = defaultdict(float)\n",
    "    for baris in stream_baris:\n",
    "        produk = baris.split(\",\")[2]\n",
    "        for p in skor:\n",
    "            skor[p] *= (1 - c)\n",
    "        skor[produk] += 1\n",
    "    return pd.Series(skor).sort_values(ascending=False)\n",
    "\n",
    "trending(log_transaksi()).head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a2924ee",
   "metadata": {},
   "source": [
    "## 4. Reservoir sampling\n",
    "\n",
    "Ambil 5 transaksi acak seragam tanpa tahu panjang stream."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b36448ba",
   "metadata": {},
   "outputs": [],
   "source": [
    "def reservoir(stream, k, seed=0):\n",
    "    rng = random.Random(seed)\n",
    "    res = []\n",
    "    for i, x in enumerate(stream):\n",
    "        if i < k:\n",
    "            res.append(x)\n",
    "        else:\n",
    "            j = rng.randint(0, i)\n",
    "            if j < k:\n",
    "                res[j] = x\n",
    "    return res\n",
    "\n",
    "reservoir(log_transaksi(), 5, seed=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c6486c4",
   "metadata": {},
   "source": [
    "Bukti empiris keseragaman: ulangi 3000 kali pada stream 0..19, setiap angka mestinya terpilih ≈ k/n = 25%."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a1971fdc",
   "metadata": {},
   "outputs": [],
   "source": [
    "hitung = np.zeros(20)\n",
    "for s_ in range(3000):\n",
    "    for x in reservoir(range(20), 5, seed=s_):\n",
    "        hitung[x] += 1\n",
    "plt.bar(range(20), hitung / 3000); plt.axhline(0.25, color=\"r\", ls=\"--\")\n",
    "plt.title(\"Peluang terpilih tiap elemen\"); plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "717e2d37",
   "metadata": {},
   "source": [
    "## 5. Kemiripan dokumen: Jaccard"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ea94479",
   "metadata": {},
   "outputs": [],
   "source": [
    "docs = dokumen_teks()\n",
    "himp = [set(t.lower().split()) for t in docs]\n",
    "\n",
    "def jaccard(a, b):\n",
    "    return len(a & b) / len(a | b)\n",
    "\n",
    "n = len(docs)\n",
    "J = np.array([[jaccard(himp[i], himp[j]) for j in range(n)] for i in range(n)])\n",
    "pd.DataFrame(J).round(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10ad09aa",
   "metadata": {},
   "source": [
    "## 6. MinHash signature"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a97bf607",
   "metadata": {},
   "outputs": [],
   "source": [
    "P = 2_147_483_647\n",
    "vocab = sorted(set().union(*himp))\n",
    "idx = {v: i for i, v in enumerate(vocab)}\n",
    "\n",
    "def minhash(himpunan, n_hash=100, seed=0):\n",
    "    rng = np.random.default_rng(seed)\n",
    "    a = rng.integers(1, P, n_hash, dtype=np.int64)\n",
    "    b = rng.integers(0, P, n_hash, dtype=np.int64)\n",
    "    sig = np.zeros((n_hash, len(himpunan)), dtype=np.int64)\n",
    "    for d, h in enumerate(himpunan):\n",
    "        ids = np.array([idx[x] for x in h], dtype=np.int64)\n",
    "        sig[:, d] = ((a[:, None] * ids[None, :] + b[:, None]) % P).min(axis=1)\n",
    "    return sig\n",
    "\n",
    "sig = minhash(himp, 200, seed=1)\n",
    "print(\"ukuran signature:\", sig.shape)\n",
    "\n",
    "est = np.array([[np.mean(sig[:, i] == sig[:, j]) for j in range(n)] for i in range(n)])\n",
    "iu = np.triu_indices(n, 1)\n",
    "plt.scatter(J[iu], est[iu]); plt.plot([0, 1], [0, 1], \"r--\")\n",
    "plt.xlabel(\"Jaccard asli\"); plt.ylabel(\"Estimasi MinHash\"); plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42a0a02d",
   "metadata": {},
   "source": [
    "## 7. LSH banding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "491f87bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lsh(sig, bands):\n",
    "    r = sig.shape[0] // bands\n",
    "    kandidat = set()\n",
    "    for b in range(bands):\n",
    "        bucket = defaultdict(list)\n",
    "        for d in range(sig.shape[1]):\n",
    "            bucket[tuple(sig[b * r:(b + 1) * r, d])].append(d)\n",
    "        for anggota in bucket.values():\n",
    "            kandidat.update(combinations(anggota, 2))\n",
    "    return kandidat\n",
    "\n",
    "kand = lsh(sig, bands=50)   # r = 4\n",
    "print(f\"Kandidat: {len(kand)} dari {n*(n-1)//2} pasangan\")\n",
    "for i, j in sorted(kand):\n",
    "    print(f\"({i},{j}) J={J[i,j]:.2f}  |  {docs[i][:40]}…  ~  {docs[j][:40]}…\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9be82d0c",
   "metadata": {},
   "source": [
    "### Kurva-S LSH"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d255ef56",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_ = np.linspace(0, 1, 200)\n",
    "for b, r in [(50, 4), (20, 10), (100, 2)]:\n",
    "    plt.plot(s_, 1 - (1 - s_ ** r) ** b, label=f\"b={b}, r={r}, ambang≈{(1/b)**(1/r):.2f}\")\n",
    "plt.xlabel(\"kemiripan s\"); plt.ylabel(\"P(kandidat)\"); plt.legend(); plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49c8c893",
   "metadata": {},
   "source": [
    "## 8. PageRank"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "38ee0cfe",
   "metadata": {},
   "outputs": [],
   "source": [
    "edges = jaringan_web()\n",
    "G = nx.DiGraph(edges)\n",
    "nx.draw_networkx(G, pos=nx.spring_layout(G, seed=1), node_color=\"#9ecae1\", arrows=True)\n",
    "plt.axis(\"off\"); plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fc29beaa",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pagerank(edges, d=0.85, tol=1e-10, max_iter=200):\n",
    "    simpul = sorted({u for e in edges for u in e})\n",
    "    N = len(simpul)\n",
    "    keluar = defaultdict(list)\n",
    "    for u, v in edges:\n",
    "        keluar[u].append(v)\n",
    "    r = {u: 1 / N for u in simpul}\n",
    "    for it in range(max_iter):\n",
    "        bocor = sum(r[u] for u in simpul if u not in keluar)\n",
    "        baru = {u: (1 - d) / N + d * bocor / N for u in simpul}\n",
    "        for u, tujuan in keluar.items():\n",
    "            for v in tujuan:\n",
    "                baru[v] += d * r[u] / len(tujuan)\n",
    "        selisih = sum(abs(baru[u] - r[u]) for u in simpul)\n",
    "        r = baru\n",
    "        if selisih < tol:\n",
    "            break\n",
    "    print(\"konvergen setelah\", it + 1, \"iterasi\")\n",
    "    return r\n",
    "\n",
    "pr = pagerank(edges)\n",
    "pd.DataFrame({\"manual\": pr, \"networkx\": nx.pagerank(G, alpha=0.85)}).sort_values(\"manual\", ascending=False).round(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c977e356",
   "metadata": {},
   "source": [
    "Bentuk matriks: `r = (1-d)/N + d·M·r`. Matriks transisi M (kolom = sumber):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ab91e593",
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = sorted(G.nodes)\n",
    "M = nx.to_numpy_array(G, nodelist=nodes).T\n",
    "M = M / M.sum(axis=0, keepdims=True)\n",
    "pd.DataFrame(M, index=nodes, columns=nodes).round(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a1f4eff",
   "metadata": {},
   "source": [
    "## ✍️ Coba sendiri\n",
    "\n",
    "1. Ubah `w` sliding window menjadi 10 dan 200. Apa efeknya pada kehalusan kurva?\n",
    "2. Tambahkan dokumen baru yang hampir sama dengan dokumen ke-3, lalu jalankan MinHash + LSH. Apakah pasangan barunya tertangkap?\n",
    "3. Coba `bands=10` (r = 20). Berapa kandidat yang tersisa? Jelaskan dengan kurva-S.\n",
    "4. Tambahkan simpul dangling `H` (C→H) ke graf. Bagaimana PageRank berubah? Bandingkan dengan NetworkX.\n",
    "5. Ubah damping d = 0.5 dan d = 0.99. Simpul mana yang paling terpengaruh?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "99c83d8a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c4299f3f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "de54a4d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2f059bdf",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 4."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1db81370",
   "metadata": {},
   "source": [
    "**Jawaban no. 5:**\n",
    "\n",
    "- ..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eaee5774",
   "metadata": {},
   "source": [
    "## Selanjutnya\n",
    "Kerjakan kuis dan `exercise.py`, lalu jalankan `python check.py 15` dari folder utama."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}