{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d8fd84b9",
   "metadata": {},
   "source": [
    "# Lab Minggu 5 — FP-Growth & Evaluasi Aturan Asosiasi\n",
    "\n",
    "**Tujuan lab:**\n",
    "1. Membangun & mencetak FP-Tree dari contoh Han & Kamber.\n",
    "2. Membandingkan **kecepatan** Apriori vs. FP-Growth (mlxtend) pada dataset ritel.\n",
    "3. Membangkitkan aturan asosiasi dan memilih aturan dengan **lift > 1**.\n",
    "4. Menerjemahkan aturan menjadi strategi bisnis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a7178f5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.path.insert(0, \"..\")\n",
    "\n",
    "import time\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from common.datasets import transaksi_contoh, transaksi_ritel"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30bed811",
   "metadata": {},
   "source": [
    "## 1. FP-Tree dari nol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ff7ca551",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, item, parent):\n",
    "        self.item, self.parent, self.count, self.children = item, parent, 0, {}\n",
    "\n",
    "def bangun_fptree(transaksi, min_count):\n",
    "    cnt = {}\n",
    "    for t in transaksi:\n",
    "        for i in t:\n",
    "            cnt[i] = cnt.get(i, 0) + 1\n",
    "    flist = sorted((i for i in cnt if cnt[i] >= min_count), key=lambda i: (-cnt[i], i))\n",
    "    rank = {i: r for r, i in enumerate(flist)}\n",
    "    root, header = Node(None, None), {i: [] for i in flist}\n",
    "    for t in transaksi:\n",
    "        node = root\n",
    "        for i in sorted((i for i in t if i in rank), key=rank.get):\n",
    "            if i not in node.children:\n",
    "                node.children[i] = Node(i, node)\n",
    "                header[i].append(node.children[i])\n",
    "            node = node.children[i]\n",
    "            node.count += 1\n",
    "    return root, header, flist\n",
    "\n",
    "def cetak(node, indent=\"\"):\n",
    "    for anak in node.children.values():\n",
    "        print(f\"{indent}└── {anak.item}:{anak.count}\")\n",
    "        cetak(anak, indent + \"    \")\n",
    "\n",
    "root, header, flist = bangun_fptree(transaksi_contoh(), 2)\n",
    "print(\"F-list:\", flist)\n",
    "print(\"null\")\n",
    "cetak(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e59cc301",
   "metadata": {},
   "source": [
    "### Conditional pattern base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e030fd2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cpb(header, item):\n",
    "    hasil = []\n",
    "    for node in header[item]:\n",
    "        path, p = [], node.parent\n",
    "        while p.item is not None:\n",
    "            path.append(p.item)\n",
    "            p = p.parent\n",
    "        if path:\n",
    "            hasil.append((path[::-1], node.count))\n",
    "    return hasil\n",
    "\n",
    "for item in reversed(flist):\n",
    "    print(f\"{item}: {cpb(header, item)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b4679b8",
   "metadata": {},
   "source": [
    "## 2. Apriori vs. FP-Growth (mlxtend)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "572b7350",
   "metadata": {},
   "outputs": [],
   "source": [
    "from mlxtend.preprocessing import TransactionEncoder\n",
    "from mlxtend.frequent_patterns import apriori, fpgrowth, association_rules\n",
    "\n",
    "ritel = transaksi_ritel(5000, seed=2)\n",
    "te = TransactionEncoder()\n",
    "onehot = pd.DataFrame(te.fit(ritel).transform(ritel), columns=te.columns_)\n",
    "print(onehot.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5cfb0753",
   "metadata": {},
   "outputs": [],
   "source": [
    "baris = []\n",
    "for ms in [0.1, 0.05, 0.03, 0.02, 0.01]:\n",
    "    for nama, fn in [(\"apriori\", apriori), (\"fpgrowth\", fpgrowth)]:\n",
    "        t0 = time.perf_counter()\n",
    "        hasil = fn(onehot, min_support=ms, use_colnames=True)\n",
    "        baris.append({\"algoritma\": nama, \"min_support\": ms,\n",
    "                      \"waktu_ms\": (time.perf_counter() - t0) * 1000, \"itemset\": len(hasil)})\n",
    "banding = pd.DataFrame(baris)\n",
    "banding.pivot(index=\"min_support\", columns=\"algoritma\", values=[\"waktu_ms\", \"itemset\"]).round(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3317009f",
   "metadata": {},
   "outputs": [],
   "source": [
    "banding.pivot(index=\"min_support\", columns=\"algoritma\", values=\"waktu_ms\").plot(\n",
    "    marker=\"o\", title=\"Waktu komputasi (ms)\")\n",
    "plt.gca().invert_xaxis()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "291ff7eb",
   "metadata": {},
   "source": [
    "> Jumlah itemset **identik** — kedua algoritma menemukan pola yang sama, hanya caranya berbeda.\n",
    "> Mengukur memori bisa dicoba dengan `tracemalloc` (lihat *Coba sendiri*)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7974e37b",
   "metadata": {},
   "source": [
    "## 3. Membangkitkan aturan & metrik"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c5317327",
   "metadata": {},
   "outputs": [],
   "source": [
    "fi = fpgrowth(onehot, min_support=0.03, use_colnames=True)\n",
    "rules = association_rules(fi, metric=\"confidence\", min_threshold=0.3)\n",
    "rules = rules[[\"antecedents\", \"consequents\", \"support\", \"confidence\", \"lift\", \"leverage\", \"conviction\"]]\n",
    "rules.sort_values(\"lift\", ascending=False).head(10).round(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2833e391",
   "metadata": {},
   "source": [
    "Verifikasi manual satu aturan:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ac7c0cff",
   "metadata": {},
   "outputs": [],
   "source": [
    "r = rules.sort_values(\"lift\", ascending=False).iloc[0]\n",
    "A, B = set(r.antecedents), set(r.consequents)\n",
    "sA = onehot[list(A)].all(axis=1).mean()\n",
    "sB = onehot[list(B)].all(axis=1).mean()\n",
    "sAB = onehot[list(A | B)].all(axis=1).mean()\n",
    "print(f\"{A} => {B}\")\n",
    "print(f\"confidence = {sAB / sA:.3f}  lift = {sAB / (sA * sB):.3f}  \"\n",
    "      f\"leverage = {sAB - sA * sB:.3f}  conviction = {(1 - sB) / (1 - sAB / sA):.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4c4d8a5",
   "metadata": {},
   "source": [
    "## 4. Confidence vs. lift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "af34aac2",
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.scatter(rules[\"support\"], rules[\"confidence\"], c=rules[\"lift\"], cmap=\"coolwarm\", s=25)\n",
    "plt.colorbar(label=\"lift\")\n",
    "plt.xlabel(\"support\"); plt.ylabel(\"confidence\")\n",
    "plt.title(\"Aturan asosiasi (warna = lift)\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6ad467b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Aturan confidence ≥ 0.3 tetapi lift < 1 (korelasi negatif/menyesatkan):\")\n",
    "rules[rules[\"lift\"] < 1].sort_values(\"confidence\", ascending=False).head().round(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d517523",
   "metadata": {},
   "source": [
    "## 5. Aturan teratas untuk bisnis (lift > 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2d2a503c",
   "metadata": {},
   "outputs": [],
   "source": [
    "top = rules[(rules[\"lift\"] > 1.2)].sort_values([\"lift\", \"support\"], ascending=False).head(8).copy()\n",
    "top[\"aturan\"] = top.apply(lambda r: f\"{set(r.antecedents)} => {set(r.consequents)}\", axis=1)\n",
    "top[[\"aturan\", \"support\", \"confidence\", \"lift\"]].round(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e40cf280",
   "metadata": {},
   "source": [
    "Contoh interpretasi:\n",
    "\n",
    "- `{mentega} => {roti}`: lift tinggi & support tinggi → letakkan berdekatan, promo bundling.\n",
    "- `{gula} => {kopi}`: pembeli gula cenderung membeli kopi → rekomendasi \"sering dibeli bersama\"."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21655ec8",
   "metadata": {},
   "source": [
    "## ✍️ Coba sendiri\n",
    "\n",
    "1. Gunakan `tracemalloc` untuk membandingkan **puncak memori** apriori vs. fpgrowth pada min_support 0.01.\n",
    "2. Saring aturan dengan `conviction > 1.5`. Bandingkan dengan saringan `lift > 1.5`.\n",
    "3. Implementasikan `fpgrowth` dari nol (lihat `exercise.py`) dan pastikan hasilnya sama dengan mlxtend.\n",
    "4. Tulis 3 aturan teratas beserta strategi bisnisnya (penempatan, bundling, rekomendasi)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "81cfaa0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1.\n",
    "import tracemalloc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8442361c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 2."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0e82ddf",
   "metadata": {},
   "source": [
    "**Strategi no. 4:**\n",
    "\n",
    "- ..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7db9defb",
   "metadata": {},
   "source": [
    "## Selanjutnya\n",
    "Kerjakan kuis dan `exercise.py`, lalu jalankan `python check.py 5` dari folder utama."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}