homework_3_decision_tree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Any\n",
    "\n",
    "import numpy as np\n",
    "import numpy.typing as npt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(600, 6)\n",
      "(600,)\n"
     ]
    }
   ],
   "source": [
    "data_113 = np.loadtxt('dataset/20151026_113_labeled.txt')\n",
    "data_114 = np.loadtxt('dataset/20151026_114_labeled.txt')\n",
    "data = np.concatenate((data_113, data_114), axis=0)\n",
    "\n",
    "features = data[:, :6]\n",
    "labels = data[:, 6].astype(np.int8)\n",
    "\n",
    "print(features.shape)\n",
    "print(labels.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calc_entropy(labels: npt.NDArray[np.int8]) -> float:\n",
    "    '''\n",
    "    Calculate the entropy of the labels.\n",
    "    '''\n",
    "    entropy = 0\n",
    "\n",
    "    for count in np.unique(labels, return_counts=True)[1]:\n",
    "        # H(D) = -Σ(|Ck| / |D| * log2(|Ck| / |D|))\n",
    "        prob = count / len(labels)\n",
    "        entropy -= prob * np.log2(prob)\n",
    "\n",
    "    return entropy\n",
    "\n",
    "\n",
    "def calc_info_gain(features: npt.NDArray[np.float64], labels: npt.NDArray[np.int8], split_value: float) -> float:\n",
    "    '''\n",
    "    Calculate the information gain of the features and labels.\n",
    "    '''\n",
    "    # Split the labels by the split value.\n",
    "    left_labels = labels[features < split_value]\n",
    "    right_labels = labels[features >= split_value]\n",
    "\n",
    "    entropy = calc_entropy(labels)\n",
    "    left_entropy = calc_entropy(left_labels)\n",
    "    right_entropy = calc_entropy(right_labels)\n",
    "\n",
    "    left_prob = len(left_labels) / len(labels)\n",
    "    right_prob = len(right_labels) / len(labels)\n",
    "\n",
    "    # H(D|A) = Σ(|Di| / |D| * H(Di))\n",
    "    conditional_entropy = left_prob * left_entropy + right_prob * right_entropy\n",
    "\n",
    "    # G(D|A) = H(D) - H(D|A)\n",
    "    info_gain = entropy - conditional_entropy\n",
    "\n",
    "    return info_gain\n",
    "\n",
    "\n",
    "def choose_best_feature(features: npt.NDArray[np.float64], labels: npt.NDArray[np.int8]) -> tuple[int, float]:\n",
    "    '''\n",
    "    Choose the best feature and split value to split the dataset.\n",
    "    '''\n",
    "    best_feature_index = -1\n",
    "    best_split_value = -1\n",
    "    best_info_gain = 0\n",
    "\n",
    "    # Iterate over all features\n",
    "    for feature_index in range(features.shape[1]):\n",
    "        feature = features[:, feature_index]\n",
    "\n",
    "        # Iterate over all values of the feature\n",
    "        for value in feature:\n",
    "            info_gain = calc_info_gain(feature, labels, value)\n",
    "\n",
    "            # Update the best feature and split value\n",
    "            if info_gain > best_info_gain:\n",
    "                best_feature_index = feature_index\n",
    "                best_split_value = value\n",
    "                best_info_gain = info_gain\n",
    "\n",
    "    return best_feature_index, best_split_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_tree(features: npt.NDArray[np.float64], labels: npt.NDArray[np.int8]) -> dict[str, Any]:\n",
    "    '''\n",
    "    Build the decision tree recursively.\n",
    "    '''\n",
    "    tree: dict[str, Any] = {}\n",
    "\n",
    "    # If all the labels are the same, end the recursion.\n",
    "    if np.all(labels == labels[0]):\n",
    "        tree['label'] = labels[0]\n",
    "        return tree\n",
    "\n",
    "    feature_index, split_value = choose_best_feature(features, labels)\n",
    "\n",
    "    tree['feature_index'] = feature_index\n",
    "    tree['split_value'] = split_value\n",
    "\n",
    "    feature = features[:, feature_index]\n",
    "    tree['left'] = build_tree(features[feature < split_value],\n",
    "                              labels[feature < split_value])\n",
    "    tree['right'] = build_tree(features[feature >= split_value],\n",
    "                               labels[feature >= split_value])\n",
    "    return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'feature_index': 0,\n",
       " 'split_value': 270.79117585820137,\n",
       " 'left': {'feature_index': 4,\n",
       "  'split_value': 0.2265714231505857,\n",
       "  'left': {'feature_index': 4,\n",
       "   'split_value': -0.3938333982986771,\n",
       "   'left': {'feature_index': 5,\n",
       "    'split_value': -0.7126152948127243,\n",
       "    'left': {'feature_index': 0,\n",
       "     'split_value': 112.38079799254311,\n",
       "     'left': {'feature_index': 0,\n",
       "      'split_value': 99.24425716472952,\n",
       "      'left': {'label': 1},\n",
       "      'right': {'label': 2}},\n",
       "     'right': {'feature_index': 5,\n",
       "      'split_value': -1.1411183120960675,\n",
       "      'left': {'feature_index': 5,\n",
       "       'split_value': -24.083641275755816,\n",
       "       'left': {'label': 1},\n",
       "       'right': {'label': 0}},\n",
       "      'right': {'feature_index': 0,\n",
       "       'split_value': 232.16245743708612,\n",
       "       'left': {'label': 0},\n",
       "       'right': {'label': 1}}}},\n",
       "    'right': {'feature_index': 0,\n",
       "     'split_value': 257.30675332208466,\n",
       "     'left': {'label': 0},\n",
       "     'right': {'feature_index': 0,\n",
       "      'split_value': 261.62405552495534,\n",
       "      'left': {'label': 1},\n",
       "      'right': {'label': 0}}}},\n",
       "   'right': {'feature_index': 5,\n",
       "    'split_value': 0.3026275082426316,\n",
       "    'left': {'feature_index': 4,\n",
       "     'split_value': -0.3002611359305827,\n",
       "     'left': {'feature_index': 0,\n",
       "      'split_value': 218.165760867123,\n",
       "      'left': {'feature_index': 1,\n",
       "       'split_value': 220.01266246291885,\n",
       "       'left': {'feature_index': 0,\n",
       "        'split_value': 185.17329480356818,\n",
       "        'left': {'label': 1},\n",
       "        'right': {'label': 0}},\n",
       "       'right': {'label': 0}},\n",
       "      'right': {'feature_index': 1,\n",
       "       'split_value': 175.95622159079113,\n",
       "       'left': {'feature_index': 0,\n",
       "        'split_value': 225.32269402048138,\n",
       "        'left': {'label': 1},\n",
       "        'right': {'label': 0}},\n",
       "       'right': {'label': 1}}},\n",
       "     'right': {'feature_index': 4,\n",
       "      'split_value': 0.14094578319400586,\n",
       "      'left': {'feature_index': 4,\n",
       "       'split_value': -0.20372452578547212,\n",
       "       'left': {'feature_index': 0,\n",
       "        'split_value': 174.12137669825964,\n",
       "        'left': {'feature_index': 2,\n",
       "         'split_value': 377.9539023483287,\n",
       "         'left': {'feature_index': 4,\n",
       "          'split_value': -0.2831142443754208,\n",
       "          'left': {'label': 1},\n",
       "          'right': {'label': 0}},\n",
       "         'right': {'label': 1}},\n",
       "        'right': {'feature_index': 4,\n",
       "         'split_value': -0.2375073090542315,\n",
       "         'left': {'label': 1},\n",
       "         'right': {'feature_index': 4,\n",
       "          'split_value': -0.22617862046227413,\n",
       "          'left': {'label': 0},\n",
       "          'right': {'label': 1}}}},\n",
       "       'right': {'feature_index': 1,\n",
       "        'split_value': 228.8391074187637,\n",
       "        'left': {'feature_index': 5,\n",
       "         'split_value': -0.22971512764266203,\n",
       "         'left': {'feature_index': 0,\n",
       "          'split_value': 146.67667179675342,\n",
       "          'left': {'feature_index': 1,\n",
       "           'split_value': 65.1063515502582,\n",
       "           'left': {'label': 0},\n",
       "           'right': {'label': 1}},\n",
       "          'right': {'feature_index': 5,\n",
       "           'split_value': -0.40024872331861505,\n",
       "           'left': {'label': 1},\n",
       "           'right': {'label': 0}}},\n",
       "         'right': {'feature_index': 5,\n",
       "          'split_value': 0.2040104886216051,\n",
       "          'left': {'label': 1},\n",
       "          'right': {'feature_index': 0,\n",
       "           'split_value': 155.7463634951043,\n",
       "           'left': {'label': 0},\n",
       "           'right': {'label': 1}}}},\n",
       "        'right': {'label': 1}}},\n",
       "      'right': {'feature_index': 2,\n",
       "       'split_value': 238.8973100332504,\n",
       "       'left': {'feature_index': 2,\n",
       "        'split_value': 60.870388725122886,\n",
       "        'left': {'label': 0},\n",
       "        'right': {'label': 1}},\n",
       "       'right': {'feature_index': 2,\n",
       "        'split_value': 366.17314296631014,\n",
       "        'left': {'label': 0},\n",
       "        'right': {'label': 1}}}}},\n",
       "    'right': {'feature_index': 0,\n",
       "     'split_value': 147.80060791730367,\n",
       "     'left': {'label': 0},\n",
       "     'right': {'feature_index': 5,\n",
       "      'split_value': 1.0100533538119552,\n",
       "      'left': {'feature_index': 2,\n",
       "       'split_value': 136.42956263483012,\n",
       "       'left': {'label': 1},\n",
       "       'right': {'feature_index': 0,\n",
       "        'split_value': 187.47651651849935,\n",
       "        'left': {'feature_index': 0,\n",
       "         'split_value': 183.27293229976425,\n",
       "         'left': {'label': 0},\n",
       "         'right': {'label': 1}},\n",
       "        'right': {'label': 0}}},\n",
       "      'right': {'label': 1}}}}},\n",
       "  'right': {'feature_index': 5,\n",
       "   'split_value': 0.5539115284698163,\n",
       "   'left': {'feature_index': 4,\n",
       "    'split_value': 0.3838973222595979,\n",
       "    'left': {'feature_index': 4,\n",
       "     'split_value': 0.3417274374621802,\n",
       "     'left': {'feature_index': 3,\n",
       "      'split_value': 51.39185228901591,\n",
       "      'left': {'label': 2},\n",
       "      'right': {'feature_index': 1,\n",
       "       'split_value': 262.60584426094886,\n",
       "       'left': {'label': 0},\n",
       "       'right': {'feature_index': 0,\n",
       "        'split_value': 128.65064494356346,\n",
       "        'left': {'label': 1},\n",
       "        'right': {'label': 0}}}},\n",
       "     'right': {'feature_index': 0,\n",
       "      'split_value': 258.54033396495015,\n",
       "      'left': {'label': 1},\n",
       "      'right': {'feature_index': 0,\n",
       "       'split_value': 266.0568341433113,\n",
       "       'left': {'label': 2},\n",
       "       'right': {'label': 0}}}},\n",
       "    'right': {'label': 0}},\n",
       "   'right': {'feature_index': 4,\n",
       "    'split_value': 0.5904596594480985,\n",
       "    'left': {'feature_index': 2,\n",
       "     'split_value': 41.3918926659334,\n",
       "     'left': {'label': 1},\n",
       "     'right': {'label': 0}},\n",
       "    'right': {'feature_index': 1,\n",
       "     'split_value': 264.23875856446153,\n",
       "     'left': {'feature_index': 4,\n",
       "      'split_value': 0.9616775358838594,\n",
       "      'left': {'feature_index': 2,\n",
       "       'split_value': 381.14939172728214,\n",
       "       'left': {'feature_index': 0,\n",
       "        'split_value': 119.24429186276078,\n",
       "        'left': {'label': 1},\n",
       "        'right': {'feature_index': 1,\n",
       "         'split_value': 147.38083323976366,\n",
       "         'left': {'label': 2},\n",
       "         'right': {'feature_index': 2,\n",
       "          'split_value': 230.67296897238384,\n",
       "          'left': {'feature_index': 0,\n",
       "           'split_value': 239.30635208434308,\n",
       "           'left': {'label': 2},\n",
       "           'right': {'label': 1}},\n",
       "          'right': {'label': 1}}}},\n",
       "       'right': {'label': 0}},\n",
       "      'right': {'feature_index': 4,\n",
       "       'split_value': 1.2180224180022348,\n",
       "       'left': {'label': 2},\n",
       "       'right': {'label': 0}}},\n",
       "     'right': {'feature_index': 4,\n",
       "      'split_value': 1.2324313918442253,\n",
       "      'left': {'label': 0},\n",
       "      'right': {'feature_index': 0,\n",
       "       'split_value': 240.4251604654444,\n",
       "       'left': {'label': 0},\n",
       "       'right': {'label': 1}}}}}}},\n",
       " 'right': {'feature_index': 1,\n",
       "  'split_value': 311.49531534670064,\n",
       "  'left': {'feature_index': 0,\n",
       "   'split_value': 309.93603101767667,\n",
       "   'left': {'feature_index': 4,\n",
       "    'split_value': 0.9632849693936807,\n",
       "    'left': {'feature_index': 0,\n",
       "     'split_value': 306.3919149334557,\n",
       "     'left': {'feature_index': 5,\n",
       "      'split_value': 1.6037729693755054,\n",
       "      'left': {'feature_index': 1,\n",
       "       'split_value': 294.3481403348653,\n",
       "       'left': {'feature_index': 0,\n",
       "        'split_value': 298.0003690424339,\n",
       "        'left': {'label': 0},\n",
       "        'right': {'feature_index': 0,\n",
       "         'split_value': 298.20453376997006,\n",
       "         'left': {'label': 1},\n",
       "         'right': {'label': 0}}},\n",
       "       'right': {'feature_index': 1,\n",
       "        'split_value': 299.12103445229576,\n",
       "        'left': {'label': 1},\n",
       "        'right': {'label': 0}}},\n",
       "      'right': {'label': 1}},\n",
       "     'right': {'label': 2}},\n",
       "    'right': {'feature_index': 1,\n",
       "     'split_value': 270.7103565389922,\n",
       "     'left': {'feature_index': 2,\n",
       "      'split_value': 405.79073096752984,\n",
       "      'left': {'label': 0},\n",
       "      'right': {'label': 2}},\n",
       "     'right': {'label': 2}}},\n",
       "   'right': {'feature_index': 0,\n",
       "    'split_value': 323.0152833280596,\n",
       "    'left': {'feature_index': 0,\n",
       "     'split_value': 320.7593849864101,\n",
       "     'left': {'label': 0},\n",
       "     'right': {'label': 2}},\n",
       "    'right': {'label': 0}}},\n",
       "  'right': {'feature_index': 1,\n",
       "   'split_value': 399.74207468456234,\n",
       "   'left': {'feature_index': 2,\n",
       "    'split_value': 114.5907565188029,\n",
       "    'left': {'feature_index': 0,\n",
       "     'split_value': 362.5287718737628,\n",
       "     'left': {'feature_index': 0,\n",
       "      'split_value': 305.8250437703199,\n",
       "      'left': {'feature_index': 0,\n",
       "       'split_value': 301.2900141125558,\n",
       "       'left': {'label': 1},\n",
       "       'right': {'label': 2}},\n",
       "      'right': {'label': 1}},\n",
       "     'right': {'feature_index': 0,\n",
       "      'split_value': 425.40867023194494,\n",
       "      'left': {'label': 0},\n",
       "      'right': {'label': 1}}},\n",
       "    'right': {'feature_index': 0,\n",
       "     'split_value': 358.5751673704806,\n",
       "     'left': {'feature_index': 5,\n",
       "      'split_value': 1.397186028379212,\n",
       "      'left': {'feature_index': 4,\n",
       "       'split_value': 0.513053755049896,\n",
       "       'left': {'feature_index': 4,\n",
       "        'split_value': -0.824313455392211,\n",
       "        'left': {'feature_index': 3,\n",
       "         'split_value': 376.3112463031616,\n",
       "         'left': {'feature_index': 4,\n",
       "          'split_value': -1.0465508589775159,\n",
       "          'left': {'label': 0},\n",
       "          'right': {'feature_index': 0,\n",
       "           'split_value': 332.793932733775,\n",
       "           'left': {'label': 0},\n",
       "           'right': {'label': 2}}},\n",
       "         'right': {'label': 2}},\n",
       "        'right': {'feature_index': 1,\n",
       "         'split_value': 329.3825916313043,\n",
       "         'left': {'label': 2},\n",
       "         'right': {'feature_index': 1,\n",
       "          'split_value': 345.8896142565737,\n",
       "          'left': {'label': 1},\n",
       "          'right': {'feature_index': 0,\n",
       "           'split_value': 304.02320722488275,\n",
       "           'left': {'label': 0},\n",
       "           'right': {'feature_index': 1,\n",
       "            'split_value': 351.82495277170585,\n",
       "            'left': {'label': 0},\n",
       "            'right': {'label': 1}}}}}},\n",
       "       'right': {'label': 0}},\n",
       "      'right': {'feature_index': 4,\n",
       "       'split_value': 1.1519100021770594,\n",
       "       'left': {'label': 0},\n",
       "       'right': {'feature_index': 4,\n",
       "        'split_value': 2.9771808243558913,\n",
       "        'left': {'feature_index': 0,\n",
       "         'split_value': 353.7663549797031,\n",
       "         'left': {'label': 2},\n",
       "         'right': {'label': 0}},\n",
       "        'right': {'label': 0}}}},\n",
       "     'right': {'feature_index': 1,\n",
       "      'split_value': 370.5536837999779,\n",
       "      'left': {'feature_index': 4,\n",
       "       'split_value': 9.059904734287471,\n",
       "       'left': {'feature_index': 4,\n",
       "        'split_value': 2.644487008008367,\n",
       "        'left': {'feature_index': 1,\n",
       "         'split_value': 358.0849035017129,\n",
       "         'left': {'label': 0},\n",
       "         'right': {'feature_index': 0,\n",
       "          'split_value': 375.7768733216386,\n",
       "          'left': {'label': 0},\n",
       "          'right': {'label': 2}}},\n",
       "        'right': {'label': 2}},\n",
       "       'right': {'feature_index': 2,\n",
       "        'split_value': 315.0778697253734,\n",
       "        'left': {'label': 0},\n",
       "        'right': {'feature_index': 5,\n",
       "         'split_value': -0.6296758834205123,\n",
       "         'left': {'label': 0},\n",
       "         'right': {'label': 1}}}},\n",
       "      'right': {'feature_index': 4,\n",
       "       'split_value': -1.1232601209132014,\n",
       "       'left': {'feature_index': 4,\n",
       "        'split_value': -15.91779405451687,\n",
       "        'left': {'feature_index': 0,\n",
       "         'split_value': 400.43996883055945,\n",
       "         'left': {'label': 0},\n",
       "         'right': {'label': 2}},\n",
       "        'right': {'label': 2}},\n",
       "       'right': {'feature_index': 4,\n",
       "        'split_value': 1.9284694415071055,\n",
       "        'left': {'feature_index': 0,\n",
       "         'split_value': 381.52353148978386,\n",
       "         'left': {'label': 1},\n",
       "         'right': {'feature_index': 2,\n",
       "          'split_value': 333.9757408207397,\n",
       "          'left': {'label': 1},\n",
       "          'right': {'label': 0}}},\n",
       "        'right': {'feature_index': 0,\n",
       "         'split_value': 390.717743729139,\n",
       "         'left': {'feature_index': 2,\n",
       "          'split_value': 166.69523718231528,\n",
       "          'left': {'label': 0},\n",
       "          'right': {'label': 2}},\n",
       "         'right': {'feature_index': 0,\n",
       "          'split_value': 406.1525529037356,\n",
       "          'left': {'label': 1},\n",
       "          'right': {'label': 2}}}}}}}},\n",
       "   'right': {'feature_index': 0,\n",
       "    'split_value': 383.4840036964175,\n",
       "    'left': {'label': 0},\n",
       "    'right': {'label': 1}}}}}"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "tree = build_tree(features, labels)\n",
    "\n",
    "display(tree)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "ml",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}