Decision Trees.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision Trees"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Take a dataset (root) and calculate the potential information gained from each possible feature split (branch).\n",
    "    - Information gain is calculated by the entropy (0-1) of the parent minus the weighted average times the entropy of the children node.\n",
    "\n",
    "\n",
    "- Split the dataset with that feature and value that gains the most insight.\n",
    "\n",
    "\n",
    "- Continue to divide the main tree and repeat this process for each created branch until a criteria has been reached.\n",
    "    - Example criteria can be maximum depth, minimum number of samples, min impurity decrease, etc.\n",
    "\n",
    "\n",
    "- During testing, follow this tree until you reach a leaf (end node) and return the most common class label."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from collections import Counter\n",
    "from sklearn import datasets\n",
    "from sklearn.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, feature=None, threshold=None, left=None, right=None,*,value=None):\n",
    "        self.feature = feature\n",
    "        self.threshold = threshold\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.value = value\n",
    "        \n",
    "    def is_leaf_node(self):\n",
    "        return self.value is not None\n",
    "\n",
    "\n",
    "class DecisionTree:\n",
    "    def __init__(self, min_samples_split=2, max_depth=100, n_features=None):\n",
    "        self.min_samples_split=min_samples_split\n",
    "        self.max_depth=max_depth\n",
    "        self.n_features=n_features\n",
    "        self.root=None\n",
    "\n",
    "    def fit(self, X, y):\n",
    "        self.n_features = X.shape[1] if not self.n_features else min(X.shape[1],self.n_features)\n",
    "        self.root = self._grow_tree(X, y)\n",
    "\n",
    "    def _grow_tree(self, X, y, depth=0):\n",
    "        n_samples, n_feats = X.shape\n",
    "        n_labels = len(np.unique(y))\n",
    "\n",
    "        # check the stopping criteria\n",
    "        if (depth>=self.max_depth or n_labels==1 or n_samples<self.min_samples_split):\n",
    "            leaf_value = self._most_common_label(y)\n",
    "            return Node(value=leaf_value)\n",
    "\n",
    "        feat_idxs = np.random.choice(n_feats, self.n_features, replace=False)\n",
    "\n",
    "        # find the best split\n",
    "        best_feature, best_thresh = self._best_split(X, y, feat_idxs)\n",
    "\n",
    "        # create child nodes\n",
    "        left_idxs, right_idxs = self._split(X[:, best_feature], best_thresh)\n",
    "        left = self._grow_tree(X[left_idxs, :], y[left_idxs], depth+1)\n",
    "        right = self._grow_tree(X[right_idxs, :], y[right_idxs], depth+1)\n",
    "        return Node(best_feature, best_thresh, left, right)\n",
    "\n",
    "\n",
    "    def _best_split(self, X, y, feat_idxs):\n",
    "        best_gain = -1\n",
    "        split_idx, split_threshold = None, None\n",
    "\n",
    "        for feat_idx in feat_idxs:\n",
    "            X_column = X[:, feat_idx]\n",
    "            thresholds = np.unique(X_column)\n",
    "\n",
    "            for thr in thresholds:\n",
    "                # calculate the information gain\n",
    "                gain = self._information_gain(y, X_column, thr)\n",
    "\n",
    "                if gain > best_gain:\n",
    "                    best_gain = gain\n",
    "                    split_idx = feat_idx\n",
    "                    split_threshold = thr\n",
    "\n",
    "        return split_idx, split_threshold\n",
    "\n",
    "    def _information_gain(self,y, X_column, threshold):\n",
    "        # Parent Entropy\n",
    "        parent_entropy = self._entropy(y)\n",
    "        # Create Children\n",
    "        left_idxs, right_idxs = self._split(X_column, threshold)\n",
    "\n",
    "        if len(left_idxs) == 0 or len(right_idxs) == 0:\n",
    "            return 0\n",
    "        # Calculate the weighted entropy of children\n",
    "        n = len(y)\n",
    "        n_l, n_r = len(left_idxs), len(right_idxs)\n",
    "        e_l, e_r, = self._entropy(y[left_idxs]), self._entropy(y[right_idxs])\n",
    "        child_entropy = (n_l/n) * e_l + (n_r/n) * e_r\n",
    "\n",
    "        # Calculate the Information gain\n",
    "        information_gain = parent_entropy - child_entropy\n",
    "        return information_gain\n",
    "\n",
    "\n",
    "    def _split(self, X_column, split_thresh):\n",
    "        left_idxs = np.argwhere(X_column <= split_thresh).flatten()\n",
    "        right_idxs = np.argwhere(X_column > split_thresh).flatten()\n",
    "        return left_idxs, right_idxs\n",
    "\n",
    "\n",
    "    def _entropy(self, y):\n",
    "        # Bincount creates a sort of histogram that contains the # of times a number occurs in a list\n",
    "        hist = np.bincount(y)\n",
    "        ps = hist / len(y)\n",
    "        return -np.sum([p * np.log(p) for p in ps if p > 0])\n",
    "\n",
    "\n",
    "    def _most_common_label(self, y):\n",
    "        counter=Counter(y)\n",
    "        value = counter.most_common(1)[0][0]\n",
    "        return value\n",
    "\n",
    "\n",
    "    def predict(self, X):\n",
    "        return np.array([self._traverse_tree(x, self.root) for x in X])\n",
    "\n",
    "\n",
    "    def _traverse_tree(self, x, node):\n",
    "        if node.is_leaf_node():\n",
    "            return node.value\n",
    "        \n",
    "        if x[node.feature] <= node.threshold:\n",
    "            return self._traverse_tree(x, node.left)\n",
    "        return self._traverse_tree(x, node.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.9298245614035088\n"
     ]
    }
   ],
   "source": [
    "\n",
    "data = datasets.load_breast_cancer()\n",
    "X, y = data.data, data.target\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(\n",
    "    X, y, test_size=0.2, random_state=1234\n",
    ")\n",
    "\n",
    "clf = DecisionTree()\n",
    "clf.fit(X_train,y_train)\n",
    "predictions = clf.predict(X_test)\n",
    "\n",
    "def accuracy(y_test, y_pred):\n",
    "    return np.sum(y_test == y_pred) / len(y_test)\n",
    "\n",
    "acc = accuracy(y_test, predictions)\n",
    "\n",
    "print(acc)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "minimal_ds",
   "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.9.13"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "d2428ae8bed9cd321a058f75c5910092ede82b77977e4ba5d4d5fac6d1f70533"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}