{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c10af91c",
   "metadata": {},
   "source": [
    "# Lab Minggu 6 — Decision Tree Induction\n",
    "\n",
    "**Tujuan lab:**\n",
    "1. Menghitung entropy, information gain, gain ratio, dan Gini pada dataset Play Tennis.\n",
    "2. Melatih pohon keputusan scikit-learn dan memvisualisasikan percabangannya.\n",
    "3. Melatih pohon pada data churn pelanggan, mengamati **overfitting**, dan melakukan pruning."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2ad636ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.path.insert(0, \"..\")\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from common.datasets import play_tennis, churn_pelanggan\n",
    "\n",
    "df = play_tennis()\n",
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5847693",
   "metadata": {},
   "source": [
    "## 1. Entropy & Gini"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ac011224",
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(y):\n",
    "    p = pd.Series(y).value_counts(normalize=True)\n",
    "    return -(p * np.log2(p)).sum()\n",
    "\n",
    "def gini(y):\n",
    "    p = pd.Series(y).value_counts(normalize=True)\n",
    "    return 1 - (p ** 2).sum()\n",
    "\n",
    "print(f\"Entropy(play) = {entropy(df.play):.3f}\")\n",
    "print(f\"Gini(play)    = {gini(df.play):.3f}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56cf499e",
   "metadata": {},
   "outputs": [],
   "source": [
    "p = np.linspace(0.001, 0.999, 200)\n",
    "plt.plot(p, -(p * np.log2(p) + (1 - p) * np.log2(1 - p)), label=\"entropy\")\n",
    "plt.plot(p, 1 - p**2 - (1 - p)**2, label=\"gini\")\n",
    "plt.xlabel(\"proporsi kelas positif\"); plt.legend(); plt.title(\"Ukuran impurity (2 kelas)\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5c3829e",
   "metadata": {},
   "source": [
    "## 2. Information gain, gain ratio, gini split untuk tiap atribut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "865d35db",
   "metadata": {},
   "outputs": [],
   "source": [
    "def info_gain(d, a, target=\"play\"):\n",
    "    n = len(d)\n",
    "    return entropy(d[target]) - sum(len(g) / n * entropy(g[target]) for _, g in d.groupby(a))\n",
    "\n",
    "def gain_ratio(d, a, target=\"play\"):\n",
    "    return info_gain(d, a, target) / entropy(d[a])\n",
    "\n",
    "def gini_split(d, a, target=\"play\"):\n",
    "    n = len(d)\n",
    "    return sum(len(g) / n * gini(g[target]) for _, g in d.groupby(a))\n",
    "\n",
    "tabel = pd.DataFrame({a: {\"gain\": info_gain(df, a), \"gain_ratio\": gain_ratio(df, a),\n",
    "                          \"gini_split\": gini_split(df, a)} for a in df.columns[:-1]}).T\n",
    "tabel.sort_values(\"gain\", ascending=False).round(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "caebdac1",
   "metadata": {},
   "source": [
    "**outlook** terpilih sebagai root. Rincian per nilai:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b5c1fd28",
   "metadata": {},
   "outputs": [],
   "source": [
    "pd.crosstab(df.outlook, df.play).assign(\n",
    "    entropy=lambda t: [entropy(df[df.outlook == v].play) for v in t.index])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9de16a50",
   "metadata": {},
   "source": [
    "## 3. Rekursi: subset Sunny dan Rain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9786e9e0",
   "metadata": {},
   "outputs": [],
   "source": [
    "for v in [\"Sunny\", \"Rain\"]:\n",
    "    sub = df[df.outlook == v].drop(columns=\"outlook\")\n",
    "    gains = {a: round(info_gain(sub, a), 3) for a in sub.columns[:-1]}\n",
    "    print(v, \"->\", gains)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c04f083c",
   "metadata": {},
   "source": [
    "## 4. Decision tree scikit-learn pada Play Tennis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bb82f8f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.tree import DecisionTreeClassifier, export_text, plot_tree\n",
    "\n",
    "X = pd.get_dummies(df.drop(columns=\"play\"), dtype=int)\n",
    "y = df[\"play\"]\n",
    "pohon = DecisionTreeClassifier(criterion=\"entropy\", random_state=0).fit(X, y)\n",
    "print(export_text(pohon, feature_names=list(X.columns)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ef422e96",
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(12, 6))\n",
    "plot_tree(pohon, feature_names=X.columns, class_names=pohon.classes_, filled=True, rounded=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd2160c9",
   "metadata": {},
   "source": [
    "Perhatikan: scikit-learn (CART) membuat **split biner** pada kolom one-hot, misalnya\n",
    "`outlook_Overcast <= 0.5`, berbeda dari ID3 yang bercabang multi."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6428bae",
   "metadata": {},
   "source": [
    "## 5. Studi kasus: prediksi churn pelanggan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bc515511",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "churn = churn_pelanggan()\n",
    "Xc = pd.get_dummies(churn.drop(columns=\"churn\"), dtype=int)\n",
    "yc = churn[\"churn\"]\n",
    "X_tr, X_te, y_tr, y_te = train_test_split(Xc, yc, test_size=0.3, random_state=42, stratify=yc)\n",
    "print(X_tr.shape, X_te.shape, \"proporsi churn:\", yc.mean().round(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6f593031",
   "metadata": {},
   "outputs": [],
   "source": [
    "penuh = DecisionTreeClassifier(random_state=0).fit(X_tr, y_tr)\n",
    "print(\"Pohon penuh  — kedalaman:\", penuh.get_depth(), \"daun:\", penuh.get_n_leaves())\n",
    "print(f\"  akurasi latih = {accuracy_score(y_tr, penuh.predict(X_tr)):.3f}\")\n",
    "print(f\"  akurasi uji   = {accuracy_score(y_te, penuh.predict(X_te)):.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fb8d0d3",
   "metadata": {},
   "source": [
    "### Overfitting: akurasi vs. kedalaman"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "040b6863",
   "metadata": {},
   "outputs": [],
   "source": [
    "hasil = []\n",
    "for d in range(1, 21):\n",
    "    mdl = DecisionTreeClassifier(max_depth=d, random_state=0).fit(X_tr, y_tr)\n",
    "    hasil.append((d, accuracy_score(y_tr, mdl.predict(X_tr)), accuracy_score(y_te, mdl.predict(X_te))))\n",
    "h = pd.DataFrame(hasil, columns=[\"max_depth\", \"latih\", \"uji\"]).set_index(\"max_depth\")\n",
    "h.plot(marker=\"o\", title=\"Akurasi vs. max_depth\")\n",
    "plt.show()\n",
    "print(\"max_depth terbaik (uji):\", h[\"uji\"].idxmax())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c68d177",
   "metadata": {},
   "source": [
    "### Post-pruning dengan `ccp_alpha`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d906213",
   "metadata": {},
   "outputs": [],
   "source": [
    "path = penuh.cost_complexity_pruning_path(X_tr, y_tr)\n",
    "alphas = path.ccp_alphas[:-1]\n",
    "skor = [accuracy_score(y_te, DecisionTreeClassifier(ccp_alpha=a, random_state=0)\n",
    "                       .fit(X_tr, y_tr).predict(X_te)) for a in alphas]\n",
    "terbaik = alphas[int(np.argmax(skor))]\n",
    "plt.plot(alphas, skor, marker=\".\")\n",
    "plt.xlabel(\"ccp_alpha\"); plt.ylabel(\"akurasi uji\"); plt.title(\"Post-pruning\")\n",
    "plt.show()\n",
    "print(f\"ccp_alpha terbaik = {terbaik:.5f}, akurasi uji = {max(skor):.3f}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a97d3b33",
   "metadata": {},
   "outputs": [],
   "source": [
    "final = DecisionTreeClassifier(max_depth=4, random_state=0).fit(X_tr, y_tr)\n",
    "plt.figure(figsize=(18, 7))\n",
    "plot_tree(final, feature_names=Xc.columns, class_names=[\"stay\", \"churn\"], filled=True,\n",
    "          rounded=True, fontsize=8)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "87a34701",
   "metadata": {},
   "outputs": [],
   "source": [
    "pd.Series(final.feature_importances_, index=Xc.columns).sort_values().plot(\n",
    "    kind=\"barh\", title=\"Feature importance (max_depth=4)\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "123c642f",
   "metadata": {},
   "source": [
    "## ✍️ Coba sendiri\n",
    "\n",
    "1. Latih pohon dengan `criterion=\"gini\"` vs `\"entropy\"` (max_depth=4). Apakah akurasinya berbeda?\n",
    "2. Tambahkan kolom `id_pelanggan` unik ke data Play Tennis. Bandingkan information gain dan gain ratio-nya.\n",
    "3. Ekstrak 3 aturan IF-THEN dari pohon churn `final` (gunakan `export_text`). Terjemahkan ke strategi retensi.\n",
    "4. Lengkapi `id3()` di `exercise.py` dan bandingkan pohon yang dihasilkan dengan materi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "29e62066",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3c103954",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 2."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49306789",
   "metadata": {},
   "source": [
    "**Aturan & strategi no. 3:**\n",
    "\n",
    "- ..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d91a4af6",
   "metadata": {},
   "source": [
    "## Selanjutnya\n",
    "Kerjakan kuis dan `exercise.py`, lalu jalankan `python check.py 6` dari folder utama."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}