{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 실습 05 · 거리 기반 학습과 퓨샷\n",
    "\n",
    "> **연계 강의자료:** M5 「거리 기반 학습과 퓨샷」 · 9주차\n",
    "> **실습 목표:** kNN, K-means, 의사결정트리의 동작을 비교하고 클래스 평균을 이용한 퓨샷 분류를 구현한다.\n",
    ">\n",
    "> 머신러닝 기초(M4)의 특징, 레이블, 훈련·평가 데이터 구분을 복습한 뒤 진행한다. 신경망 학습 없이 CPU에서 실행한다.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. kNN의 이웃 수와 결정 경계"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np, matplotlib.pyplot as plt\n",
    "from sklearn.datasets import make_blobs\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "\n",
    "X, y = make_blobs(n_samples=120, centers=[[2,4],[5,2]], cluster_std=1.3, random_state=7)\n",
    "\n",
    "fig, axes = plt.subplots(1, 3, figsize=(13, 4))\n",
    "xx, yy = np.meshgrid(np.linspace(X[:,0].min()-1, X[:,0].max()+1, 200),\n",
    "                     np.linspace(X[:,1].min()-1, X[:,1].max()+1, 200))\n",
    "for ax, k in zip(axes, [1, 5, 25]):\n",
    "    clf = KNeighborsClassifier(n_neighbors=k).fit(X, y)\n",
    "    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)\n",
    "    ax.contourf(xx, yy, Z, alpha=.25, cmap=\"coolwarm\")\n",
    "    ax.scatter(X[:,0], X[:,1], c=y, s=18, cmap=\"coolwarm\", edgecolors=\"k\", linewidths=.3)\n",
    "    ax.set_title(f\"k = {k}\")\n",
    "plt.suptitle(\"이웃 수 k에 따른 결정 경계 비교\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 과제 1-1\n",
    "`weights=\"distance\"`(가중 투표, 1/d)로 바꾸면 k=25의 경계가 어떻게 달라지는가?\n",
    "단순 다수결 방식과 가중 투표의 차이를 강의자료 M5 실습 1과 연결해 설명하라."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. K-means와 군집 수 선택"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.cluster import KMeans\n",
    "\n",
    "X2, _ = make_blobs(n_samples=180, centers=3, cluster_std=1.0, random_state=23)\n",
    "\n",
    "sse = []\n",
    "for k in range(1, 9):\n",
    "    km = KMeans(n_clusters=k, n_init=10, random_state=0).fit(X2)\n",
    "    sse.append(km.inertia_)          # inertia_ = SSE\n",
    "\n",
    "fig, axes = plt.subplots(1, 2, figsize=(11, 4))\n",
    "km3 = KMeans(n_clusters=3, n_init=10, random_state=0).fit(X2)\n",
    "axes[0].scatter(X2[:,0], X2[:,1], c=km3.labels_, s=18, cmap=\"viridis\")\n",
    "axes[0].scatter(*km3.cluster_centers_.T, marker=\"X\", s=200, c=\"red\")\n",
    "axes[0].set_title(\"k=3 군집과 중심(X)\")\n",
    "axes[1].plot(range(1, 9), sse, \"o-\")\n",
    "axes[1].set_xlabel(\"k\"); axes[1].set_ylabel(\"SSE\"); axes[1].set_title(\"군집 수 k에 따른 SSE\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 과제 2-1\n",
    "`n_init=1`로 두고 `random_state`를 바꿔 실행한다. 최종 SSE가 달라지는 경우가 있는가?\n",
    "이 실습에서 `n_init=10`으로 여러 초기값을 비교하는 이유를 설명한다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 의사결정트리와 정보이득\n",
    "\n",
    "### 3.1 엔트로피 계산\n",
    "\n",
    "엔트로피는 클래스를 알기 전의 불확실성이며, 알게 될 때 얻는 평균 정보량이다. 밑이 2인 로그를 쓰면 단위는 비트(bit)다. 의사결정트리에서는 클래스가 섞인 정도인 불순도의 지표로 사용한다.\n",
    "\n",
    "$$H=-p\\log_2 p-(1-p)\\log_2(1-p)$$\n",
    "\n",
    "비율이 0인 항은 0으로 처리한다. 10개 샘플이 A:B = 5:5이면 1비트, 9:1이면 약 0.469비트, 10:0이면 0비트다. 아래 코드는 여러 클래스에도 적용할 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "from math import log2\n",
    "\n",
    "def entropy(counts):\n",
    "    total = sum(counts)\n",
    "    if total <= 0 or any(n < 0 for n in counts):\n",
    "        raise ValueError(\"샘플 수는 음수가 아니고 전체 합은 양수여야 합니다.\")\n",
    "    return sum(-(n / total) * log2(n / total) for n in counts if n > 0)\n",
    "\n",
    "for counts in [(5, 5), (9, 1), (10, 0)]:\n",
    "    print(f\"클래스별 샘플 수 {counts}: H = {entropy(counts):.3f} 비트\")"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 과일 데이터의 두 분할 후보\n",
    "\n",
    "사과 2개, 바나나 2개를 두 질문으로 나눈다. 아래 괄호는 **(사과 수, 바나나 수)**다. 색상과 길이는 수업용 가상 설정이다.\n",
    "\n",
    "- 후보 1, 빨간색인가: 예 (2, 0), 아니오 (0, 2)\n",
    "- 후보 2, 길이가 10cm 이상인가: 예 (1, 2), 아니오 (1, 0)\n",
    "\n",
    "정보이득은 부모 엔트로피에서 자식 노드 엔트로피의 가중평균을 뺀 값이다.\n",
    "\n",
    "$$IG=H(\\mathrm{부모})-\\frac{n_L}{n}H(L)-\\frac{n_R}{n}H(R)$$\n",
    "\n",
    "후보 1의 가중치는 각각 $\\frac{2}{4}$, 후보 2는 $\\frac{3}{4}$와 $\\frac{1}{4}$다. 중간 계산값은 반올림하지 않는다."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "def information_gain(groups):\n",
    "    parent = [sum(group[k] for group in groups) for k in range(len(groups[0]))]\n",
    "    total = sum(parent)\n",
    "    weighted = sum(sum(group) / total * entropy(group) for group in groups)\n",
    "    return entropy(parent), weighted, entropy(parent) - weighted\n",
    "\n",
    "splits = {\"후보 1: 빨간색인가\": [(2, 0), (0, 2)],\n",
    "          \"후보 2: 길이가 10cm 이상인가\": [(1, 2), (1, 0)]}\n",
    "for label, groups in splits.items():\n",
    "    before, after, gain = information_gain(groups)\n",
    "    print(f\"{label}: 분할 전 {before:.3f}, 분할 후 {after:.3f}, 정보이득 {gain:.3f} 비트\")\n",
    "\n",
    "# 확인: 후보 1은 1비트, 후보 2는 약 0.311비트다.\n",
    "# 과제: 두 자식 노드가 모두 사과 1개와 바나나 1개이면 정보이득은 얼마인가?"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 연속형 값의 기준값 비교\n",
    "\n",
    "같은 과일의 길이를 사과 8cm·12cm, 바나나 14cm·18cm로 둔다. 정렬한 값에서 서로 다른 인접 값의 중간값인 10, 13, 16cm를 후보로 비교한다. 이 코드는 후보마다 길이 ≤ 기준값과 길이 > 기준값으로 나눈다.\n",
    "\n",
    "정보이득이 가장 큰 기준을 현재 노드에서 선택하고 자식 노드에서도 반복하는 방식은 탐욕적 학습이다. 가능한 나무 전체의 최적해를 보장하지 않는다. 실제 구현은 정렬과 누적 통계 등을 활용하며, 모든 실수 경계값을 하나씩 검사하지 않는다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fruits = [(8, \"사과\"), (12, \"사과\"), (14, \"바나나\"), (18, \"바나나\")]\n",
    "values = sorted({length for length, label in fruits})\n",
    "thresholds = [(a + b) / 2 for a, b in zip(values, values[1:])]\n",
    "\n",
    "for threshold in thresholds:\n",
    "    left = [label for length, label in fruits if length <= threshold]\n",
    "    right = [label for length, label in fruits if length > threshold]\n",
    "    groups = [(labels.count(\"사과\"), labels.count(\"바나나\"))\n",
    "              for labels in (left, right)]\n",
    "    before, after, gain = information_gain(groups)\n",
    "    print(f\"기준 {threshold:g}cm: {groups}, 정보이득 {gain:.3f} 비트\")\n",
    "\n",
    "# 13cm에서는 사과와 바나나가 분리되어 정보이득이 1비트다.\n",
    "# 이 데이터에서는 색상 질문과 같은 정보이득을 얻는다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 붓꽃 데이터의 의사결정트리\n",
    "\n",
    "scikit-learn의 의사결정트리는 CART 기반 이진 분할을 사용한다. `criterion=\"entropy\"`는 불순도 기준을 엔트로피로 지정한다. 이 설정이 트리 알고리즘을 ID3로 바꾸지는 않는다.\n",
    "\n",
    "[scikit-learn 의사결정트리 문서](https://scikit-learn.org/stable/modules/tree.html#classification-criteria)\n",
    "\n",
    "`plot_tree`의 entropy는 각 노드에 도착한 샘플의 클래스 비율로 계산한 값이다. 한 클래스만 있는 잎에서는 0이 되는지 확인한다.\n",
    "\n",
    "한 클래스만 남으면 엔트로피가 0이지만, 최대 깊이나 최소 샘플 수 등의 조건으로 그전에 멈출 수도 있다. max_depth=3인 나무에서 엔트로피가 0보다 큰 잎도 있는지 확인한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_iris\n",
    "from sklearn.tree import DecisionTreeClassifier, plot_tree\n",
    "\n",
    "iris = load_iris()\n",
    "tree = DecisionTreeClassifier(criterion=\"entropy\", max_depth=3, random_state=0)\n",
    "tree.fit(iris.data, iris.target)\n",
    "\n",
    "plt.figure(figsize=(13, 6))\n",
    "plot_tree(tree, feature_names=iris.feature_names, class_names=iris.target_names,\n",
    "          filled=True, fontsize=9)\n",
    "plt.title(\"엔트로피 기준의 의사결정트리 (CART 기반)\")\n",
    "plt.show()\n",
    "print(\"훈련 정확도:\", tree.score(iris.data, iris.target))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 과제 3-1\n",
    "`max_depth=None`과 `max_depth=3`의 훈련 정확도를 비교한다. 훈련 정확도만으로 새 데이터의 성능을 판단할 수 있는가?\n",
    "M4의 훈련·평가 데이터 구분을 떠올리고, 깊이를 제한하거나 가지치기를 하는 이유를 설명한다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. 클래스 평균을 이용한 퓨샷 분류\n",
    "\n",
    "손글씨 숫자 데이터에서 클래스당 5장을 지원 샘플로 선택한다. 각 클래스의 픽셀 평균을 대표 벡터로 만들고, 쿼리를 가장 가까운 대표 벡터의 클래스로 분류한다.\n",
    "이 실습은 프로토타입 분류의 계산 원리를 확인하는 예제다. Prototypical Networks는 학습된 임베딩의 평균을 사용한다. 임베딩 학습에 필요한 신경망과 역전파는 M6에서 다룬다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_digits\n",
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "digits = load_digits()\n",
    "Xtr, Xte, ytr, yte = train_test_split(digits.data, digits.target,\n",
    "                                      train_size=0.5, random_state=0, stratify=digits.target)\n",
    "\n",
    "K = 5   # 클래스당 지원 샘플 수 (5-shot)\n",
    "rng = np.random.default_rng(0)\n",
    "support_by_class = [rng.choice(np.where(ytr == c)[0], K, replace=False) for c in range(10)]\n",
    "support_idx = np.concatenate(support_by_class)\n",
    "prototypes = np.stack([Xtr[idx].mean(axis=0) for idx in support_by_class])  # (10, 64)\n",
    "\n",
    "# 쿼리 분류 = 가장 가까운 프로토타입\n",
    "dists = ((Xte[:, None, :] - prototypes[None, :, :]) ** 2).sum(-1)   # (n, 10)\n",
    "pred = dists.argmin(axis=1)\n",
    "acc = (pred == yte).mean()\n",
    "print(f\"10-way {K}-shot 프로토타입 분류 정확도: {acc:.1%} (클래스당 {K}장)\")\n",
    "\n",
    "# 비교: 동일한 지원 샘플을 사용한 1-NN\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "knn = KNeighborsClassifier(1).fit(Xtr[support_idx], ytr[support_idx])\n",
    "print(f\"같은 지원 셋의 1-NN 정확도:           {knn.score(Xte, yte):.1%}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 과제 4-1\n",
    "K를 1, 3, 5, 10으로 바꿔 두 분류기의 정확도를 비교한다. 각 비교에서는 같은 지원 샘플을 사용한다.\n",
    "K=1이면 대표 벡터와 지원 샘플이 같아지는 이유를 설명한다. 최단 거리에 동률이 없다면 두 분류 결과는 같은가?\n",
    "픽셀 거리와 의미적 유사도가 달라지는 예를 들고, M5 그림 6를 참고해 학습된 임베딩의 역할을 설명한다."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}