treeRegression.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import copy\n",
    "import treelib\n",
    "import itertools\n",
    "import scipy.optimize as opt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,branches=None,attribute=None,threshold=None,value=None):\n",
    "        if branches is None and value is None:\n",
    "            print(\"ERROR\")\n",
    "        \n",
    "        self.branches = branches\n",
    "        self.threshold = threshold\n",
    "        self.attribute = attribute\n",
    "        self.is_leaf = True if self.branches is None else False\n",
    "        self.value = value\n",
    "        self.pinfo = {}\n",
    "        \n",
    "    def get_child(self,df):\n",
    "        if isinstance(df[self.attribute],(int,float,np.number)):\n",
    "            return self.branches[0] if df[self.attribute] < self.threshold else self.branches[1]\n",
    "        else:\n",
    "            return self.branches[0] if df[self.attribute] in self.threshold else self.branches[1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self,root):\n",
    "        self.root = root\n",
    "        \n",
    "    def predict(self,x):\n",
    "        item = self.root\n",
    "        while not item.is_leaf:\n",
    "            item = item.get_child(x)\n",
    "        return item\n",
    "    \n",
    "    def leaf_count(self):\n",
    "        return self._leaf_count(self.root)\n",
    "    \n",
    "    def _leaf_count(self,node):\n",
    "        if node.is_leaf:\n",
    "            return 1\n",
    "        else:\n",
    "            return np.sum([self._leaf_count(b) for b in node.branches])\n",
    "    \n",
    "    def nodes(self):\n",
    "        return self._nodes(self.root)\n",
    "    \n",
    "    def _nodes(self,node):\n",
    "        if node.is_leaf:\n",
    "            return [node]\n",
    "        \n",
    "        nl = [node]\n",
    "        for b in node.branches:\n",
    "            nl += self._nodes(b)\n",
    "        return nl\n",
    "    \n",
    "    def classes(self):\n",
    "        nodes = self.nodes()\n",
    "        c = []\n",
    "        for n in nodes:\n",
    "            c.append(n.value)\n",
    "        return np.unique(c).tolist()\n",
    "    \n",
    "    def show(self):\n",
    "        tree_view = treelib.Tree()\n",
    "        self._show(self.root,tree_view)\n",
    "        tree_view.show()\n",
    "        \n",
    "    def _show(self,node,tree_view,parent=None,prefix=\"\"):\n",
    "        name = str(hash(node))\n",
    "        if node.is_leaf:\n",
    "            text = f\"{prefix}{node.value}\"\n",
    "        else:\n",
    "            if isinstance(node.threshold,(int,float,np.number)):\n",
    "                text = f\"{prefix}{node.attribute}<{node.threshold:.2f}\"\n",
    "            else:\n",
    "                text = f\"{prefix}{node.attribute} in {node.threshold}\"\n",
    "        tree_view.create_node(text,name,parent=parent)\n",
    "        \n",
    "        if not node.is_leaf:\n",
    "            for i, b in enumerate(node.branches):\n",
    "                p = \"True: \" if i == 0 else \"False:\"\n",
    "                self._show(b,tree_view,parent=name,prefix=p)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Node and Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "young\n"
     ]
    }
   ],
   "source": [
    "l0= Node(value=\"young\")\n",
    "l1=Node(value=\"old\")\n",
    "r=Node([l0,l1],\"age\",18)\n",
    "t=Tree(r)\n",
    "print(t.predict({\"age\":2}).value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "old\n"
     ]
    }
   ],
   "source": [
    "print(t.predict({\"age\":20}).value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t.leaf_count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<__main__.Node at 0x7fefd6355410>,\n",
       " <__main__.Node at 0x7fefd63552d0>,\n",
       " <__main__.Node at 0x7fefd6355290>]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t.nodes()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Classification And Regression Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "class CART:\n",
    "    def __init__(self,df,y_name,X_names=None,min_leaf_samples=1,min_split_samples=1,max_depth=32767):\n",
    "        self.y_name = y_name\n",
    "        if X_names is None:\n",
    "            X_names = list(df.columns)\n",
    "            X_names.remove(self.y_name)\n",
    "        self.X_names = X_names\n",
    "        self.df = self._handle_missings(df)\n",
    "        self.tree = None\n",
    "        self.splittyness = 1.\n",
    "        self.leaf_loss_threshold = 1e-12\n",
    "        \n",
    "        self.classes = np.unique(df[self.y_name]).tolist()\n",
    "        \n",
    "        self.min_leaf_samples = min_leaf_samples\n",
    "        self.min_split_samples = min_split_samples\n",
    "        self.max_depth = max_depth\n",
    "        \n",
    "        self.depth = 0\n",
    "        \n",
    "    def train(self,k=5, plot=True, slack=1.):\n",
    "        \"\"\"\n",
    "        train desicion tree by k-fold cross-validation\n",
    "        \"\"\"\n",
    "        #shuffle dataframe\n",
    "        df = self.df.sample(frac=1.)\n",
    "        \n",
    "        # train tree with full dataset\n",
    "        self.create_tree()\n",
    "        pres = self.prune()\n",
    "        beta = self._beta(pres[\"alpha\"])\n",
    "        qual_cv = np.zeros((len(beta),k))\n",
    "        #split df for k-fold cross-validation\n",
    "        training_sets, test_sets = self._k_fold_split(df,k)\n",
    "        for i in range(len(training_sets)):\n",
    "            c = CART(training_sets[i],\n",
    "                     self.y_name,\n",
    "                     X_names = self.X_names, \n",
    "                     min_leaf_samples=self.min_leaf_samples,\n",
    "                     min_split_samples=self.min_split_samples,\n",
    "                     max_depth=self.max_depth)\n",
    "            c.create_tree()          \n",
    "            pres = c.prune(test_set=test_sets[i])\n",
    "            qual = self._qualities(beta,pres)\n",
    "            qual_cv[:,i] = np.array(qual)\n",
    "        qual_mean = np.mean(qual_cv, axis=1)\n",
    "        qual_sd = np.std(qual_cv, axis = 1)\n",
    "        qual_sd_mean = np.mean(qual_sd)\n",
    "        import matplotlib.pyplot as plt\n",
    "        plt.errorbar(beta,qual_mean,yerr=qual_sd)\n",
    "        \n",
    "        qual_max = np.nanmax(qual_mean)\n",
    "        ind_max = np.argmax(qual_mean)\n",
    "        qual_max_sd = qual_sd[ind_max]\n",
    "        qual_upper = qual_mean + qual_sd * slack\n",
    "        ind_best = ind_max\n",
    "        for i in range(ind_max, len(qual_upper)):\n",
    "            if qual_mean[i] > qual_max - qual_max_sd * slack:\n",
    "                ind_best = i\n",
    "        beta_best = beta[ind_best]\n",
    "        print(f\"beta_best: {beta_best}\")\n",
    "        self.create_tree()\n",
    "        self.prune(alpha_max=beta_best)\n",
    "    \n",
    "    def _beta(self,alpha):\n",
    "        beta = []\n",
    "        for i in range(len(alpha)-1):\n",
    "            if alpha[i] <= 0:\n",
    "                continue\n",
    "            b = np.sqrt(alpha[i]*alpha[i+1])\n",
    "            beta.append(b)\n",
    "        return beta\n",
    "            \n",
    "    def _quality_at(self,b,data):\n",
    "        for i, a in enumerate(data[\"alpha\"]):\n",
    "            if a > b:\n",
    "                return data[\"A_cv\"][i-1]\n",
    "        return 0.\n",
    "    \n",
    "    def _qualities(self,beta,data):\n",
    "        return [self._quality_at(b,data) for b in beta]\n",
    "    \n",
    "    @staticmethod\n",
    "    def _k_fold_split(df,k):\n",
    "        N = len(df.index)\n",
    "        n = int(np.ceil(N/k))\n",
    "        training_sets = []\n",
    "        test_sets = []\n",
    "        for i in range(k):\n",
    "            test = df.iloc[i*n:min(N,(i+1)*n),:]\n",
    "            training = df.loc[df.index.difference(test.index),:]\n",
    "            test_sets.append(test)\n",
    "            training_sets.append(training)\n",
    "        return training_sets, test_sets\n",
    "    \n",
    "    def _handle_missings(self,df_in):\n",
    "        df_out = df_in.dropna(subset=[self.y_name])\n",
    "        # use nan as category\n",
    "        # use mean if numerical\n",
    "        for name in self.X_names:\n",
    "            if np.issubdtype(df_out[name].values.dtype, np.number):\n",
    "                df_out[name] = df_out[name].fillna(np.nanmean(df_out[name].values))\n",
    "            else:\n",
    "                df_out[name] = df_out[name].fillna(\"missing\")\n",
    "        return df_out\n",
    "        \n",
    "    def create_tree(self, leaf_loss_threshold=1e-12):\n",
    "        self.leaf_loss_threshold = leaf_loss_threshold\n",
    "        root = self._node_or_leaf(self.df)\n",
    "        self.tree = Tree(root)\n",
    "        n_leafs = self.tree.leaf_count()\n",
    "        print(f\"A tree with {n_leafs} leafs was created\")\n",
    "        return self.tree\n",
    "    \n",
    "    def _gini_impurity(self, df):\n",
    "        unique, counts = np.unique(df[self.y_name].values, return_counts=True)\n",
    "        N = df[self.y_name].values.ravel().size\n",
    "        p = counts/N\n",
    "        #print(unique)\n",
    "        #print(p)\n",
    "        return 1. - np.sum(p**2)\n",
    "    \n",
    "    def _shannon_entropy(self,df):\n",
    "        unique, counts = np.unique(df[self.y_name].values, return_counts=True)\n",
    "        N = df[self.y_name].values.size\n",
    "        p = counts/N\n",
    "        return -np.sum(p * np.log2(p))\n",
    "    \n",
    "    def _misclassification_cost(self,df):\n",
    "        y = df[self.y_name].values\n",
    "        unique, counts = np.unique(y, return_counts=True)\n",
    "        N = y.size\n",
    "        p = np.max(counts)/N\n",
    "        return 1. - p\n",
    "    \n",
    "    def _logistic_loss(self,df):\n",
    "        y = df[self.y_name].values\n",
    "        #unique, counts = np.unique(y, return_counts= True)\n",
    "        #count_max = np.max(counts)\n",
    "        p_ = self._node_value(df) #np.nanmax(counts)/np.sum(counts)\n",
    "        p_ = np.clip(p_,1e-12,1.-1e-12)\n",
    "        p = np.ones_like(y) * p_\n",
    "        l = np.sum(-y*np.log(p)-(1-y)*np.log(1-p))\n",
    "        return l\n",
    "    \n",
    "    def _mean_squared_error(self,df):\n",
    "        y = df[self.y_name].values\n",
    "        y_hat = self._node_value(df)\n",
    "        e = y - y_hat\n",
    "        return 1/e.size * (e.T @ e)\n",
    "        \n",
    "    def _residual(self,df):\n",
    "        y = df(self.y_name).values\n",
    "        p_ = self._probability(df)\n",
    "        \n",
    "        \n",
    "        \n",
    "    def _node_value(self,df):\n",
    "        #return self._probability(df)\n",
    "        v = self._mean(df)\n",
    "        return v\n",
    "    \n",
    "    def _mean(self,df):\n",
    "        return np.nanmean(df[self.y_name].values)\n",
    "    \n",
    "    def _majority_class(self,df):\n",
    "        y = df[self.y_name].values\n",
    "        unique, counts = np.unique(y,return_counts=True)\n",
    "        ind_max = np.argmax(counts)\n",
    "        return unique[ind_max]\n",
    "    \n",
    "    def _odds(self,df):\n",
    "        y = df[self.y_name].values\n",
    "        unique, counts = np.unique(y, return_counts=True)\n",
    "        d={0:0,1:0}\n",
    "        for i, u in enumerate(unique):\n",
    "            d[u] = counts[i]\n",
    "        if d[0] == 0:\n",
    "            return np.Inf\n",
    "        odds = d[1]/d[0]\n",
    "        #print(f\"odds: {odds}\")\n",
    "        return odds\n",
    "    \n",
    "    def _log_odds(self,df):\n",
    "        odds = self._odds(df)\n",
    "        odds = np.clip(odds,1e-12,1e12)\n",
    "        logodds = np.log(odds)\n",
    "        #print(f\"logodds: {logodds}\")\n",
    "        return logodds\n",
    "    \n",
    "    def _probability(self,df):\n",
    "        odds = self._odds(df)\n",
    "        if odds == np.Inf:\n",
    "            return 1.\n",
    "        p = odds/(1+odds)\n",
    "        #print(f\"odds: {odds:.2f} probability: {p:.4f}\")\n",
    "        return p\n",
    "           \n",
    "    def _opt_fun(self,df,split_name):\n",
    "        def fun(x):\n",
    "            split_df = [df[df[split_name]<x],\n",
    "                        df[df[split_name]>=x]]\n",
    "            N = len(df.index)\n",
    "            n = [len(df_.index) for df_ in split_df]\n",
    "            #print(x)\n",
    "            return n[0]/N * self._loss(split_df[0]) + n[1]/N * self._loss(split_df[1])\n",
    "        return fun\n",
    "        \n",
    "    def _node_or_leaf(self,df):\n",
    "        loss_parent = self._loss(df)\n",
    "        #p = self._probability(df)\n",
    "        if (loss_parent < self.leaf_loss_threshold\n",
    "            #p < 0.025\n",
    "            #or p > 0.975\n",
    "            or len(df.index) < self.min_leaf_samples\n",
    "            or self.depth > self.max_depth):\n",
    "            return self._leaf(df)\n",
    "        \n",
    "        loss_best, split_df, split_threshold, split_name = self._loss_best(df)\n",
    "        if split_df is None:\n",
    "            return self._leaf(df)\n",
    "        print(f\"Computed split:\\nloss: {loss_best:.2f} (parent: {loss_parent:.2f})\\nattribute: {split_name}\\nthreshold: {split_threshold}\\ncount: {[len(df_.index) for df_ in split_df]}\")\n",
    "        if loss_best < loss_parent:\n",
    "            #print(f\"=> Node({split_name}, {split_threshold})\")\n",
    "            branches = []\n",
    "            self.depth += 1\n",
    "            for i in range(2):\n",
    "                branches.append(self._node_or_leaf(split_df[i]))  \n",
    "            self.depth -= 1\n",
    "            unique, counts = np.unique(df[self.y_name], return_counts=True)\n",
    "            value = self._node_value(df)\n",
    "            item = Node(branches=branches,attribute=split_name,threshold=split_threshold,value=value)\n",
    "            item.pinfo[\"N\"] = len(df.index)\n",
    "            item.pinfo[\"r\"] = self._misclassification_cost(df)\n",
    "            item.pinfo[\"R\"] = item.pinfo[\"N\"]/len(self.df.index) * item.pinfo[\"r\"]\n",
    "        else:\n",
    "            item = self._leaf(df)\n",
    "            \n",
    "        return item\n",
    "    \n",
    "    def _leaf(self,df):\n",
    "        #unique, counts = np.unique(df[self.y_name].values,return_counts=True)\n",
    "        #print([(unique[i], counts[i]) for i in range(len(counts))])\n",
    "        #sort_ind = np.argsort(-counts)\n",
    "        value = self._node_value(df)#unique[sort_ind[0]]\n",
    "        leaf = Node(value=value)\n",
    "        \n",
    "        leaf.pinfo[\"N\"] = len(df.index)\n",
    "        leaf.pinfo[\"r\"] = self._misclassification_cost(df)\n",
    "        leaf.pinfo[\"R\"] = leaf.pinfo[\"N\"]/len(self.df.index) * leaf.pinfo[\"r\"]\n",
    "        #print(f\"=> Leaf({value}, N={len(df.index)})\")\n",
    "        return leaf\n",
    "    \n",
    "    def _loss_best(self,df):\n",
    "        loss = np.Inf\n",
    "        split_df = None\n",
    "        split_threshold = None\n",
    "        split_name = None\n",
    "        for name in self.X_names:\n",
    "            loss_ = np.Inf\n",
    "            if np.issubdtype(df[name].values.dtype, np.number):\n",
    "                loss_, split_df_, split_threshold_ = self._split_by_number(df,name)\n",
    "            else:\n",
    "                loss_, split_df_, split_threshold_ = self._split_by_class(df,name)\n",
    "            #print(loss_)\n",
    "            if (loss_ < loss\n",
    "                and np.min([len(df_.index) for df_ in split_df_]) >= self.min_split_samples):\n",
    "                loss = loss_\n",
    "                split_threshold = split_threshold_\n",
    "                split_df = split_df_\n",
    "                split_name = name\n",
    "\n",
    "        return loss, split_df, split_threshold, split_name\n",
    "    \n",
    "    def _split_by_number(self,df,name):\n",
    "        if -df[name].min()+df[name].max() < np.finfo(float).tiny:\n",
    "            return np.Inf, None, None\n",
    "        res = opt.minimize_scalar(self._opt_fun(df,name),bounds=(df[name].min(),df[name].max()),method=\"bounded\")\n",
    "        split_threshold = res.x\n",
    "        split_df = [df[df[name]<split_threshold],\n",
    "                    df[df[name]>=split_threshold]]\n",
    "        loss = res.fun\n",
    "        return loss, split_df, split_threshold\n",
    "    \n",
    "    def _split_by_class(self,df,name):\n",
    "        unique = np.unique(df[name])\n",
    "        comb = []\n",
    "        if len(unique) > 5:\n",
    "            comb = [(u,) for u in unique]\n",
    "        else:\n",
    "            for i in range(1,len(unique)):\n",
    "                comb += list(itertools.combinations(unique,i))\n",
    "            \n",
    "        if len(comb) < 1:\n",
    "            return np.Inf, None, None\n",
    "        \n",
    "        loss_ = np.Inf\n",
    "        loss = np.Inf\n",
    "        for c in comb:\n",
    "            split_threshold_ = c\n",
    "            split_df_ =[df[df[name].isin(split_threshold_)],\n",
    "                        df[~df[name].isin(split_threshold_)]]\n",
    "            N = len(df.index)\n",
    "            n = [len(df_.index) for df_ in split_df_]\n",
    "            loss_ = n[0]/N * self._loss(split_df_[0]) + n[1]/N * self._loss(split_df_[1])\n",
    "            if loss_ < loss:\n",
    "                loss = loss_\n",
    "                split_threshold = split_threshold_\n",
    "                split_df = split_df_\n",
    "        return loss, split_df, split_threshold\n",
    "    \n",
    "    def _loss(self,df):\n",
    "        #return self._gini_impurity(df)\n",
    "        #return self._shannon_entropy(df)\n",
    "        #l = self._logistic_loss(df)\n",
    "        #print(l)\n",
    "        l = self._mean_squared_error(df)\n",
    "        return l\n",
    "    \n",
    "    def metrics(self,df=None):\n",
    "        if df is None:\n",
    "            df = self.df\n",
    "        return self._regression_metrics(df)\n",
    "    \n",
    "    def _classification_metrics(self,df=None):\n",
    "        confmat = self.confusion_matrix(df=df)\n",
    "        P = self._precision(confmat)\n",
    "        #print(f\"precision: {P}\")\n",
    "        R = self._recall(confmat)\n",
    "        #print(f\"recall: {R}\")\n",
    "        F = np.mean(self._F1(P,R))\n",
    "        #print(f\"F-score: {F}\")\n",
    "        A = self._accuracy(confmat)\n",
    "        return {\"precision\":P,\n",
    "                \"recall\":R,\n",
    "                \"F-score\":F,\n",
    "                \"accuracy\":A}\n",
    "    \n",
    "    def _regression_metrics(self,df=None):\n",
    "        R2 = self._r_squared(df)\n",
    "        return {\"R_squared\":R2}\n",
    "    \n",
    "    def _r_squared(self,df):\n",
    "        y = df[self.y_name].values\n",
    "        y_hat = []\n",
    "        for i in range(len(df.index)):\n",
    "            v = self.tree.predict(df.iloc[i]).value\n",
    "            y_hat.append(v)\n",
    "        e = y - np.array(y_hat)\n",
    "        sse = e.T @ e\n",
    "        sst = np.sum((y - np.nanmean(y))**2)\n",
    "        return 1 - sse/sst\n",
    "    \n",
    "    def prune(self,alpha_max=None, test_set=None):\n",
    "        #if not alpha_max:\n",
    "        #    tree = copy.deepcopy(self.tree)\n",
    "        #else:\n",
    "        tree = self.tree\n",
    "                \n",
    "        d={}\n",
    "        d[\"alpha\"]=[]\n",
    "        d[\"R\"]=[]\n",
    "        d[\"n_leafs\"]=[]\n",
    "        if test_set is not None:\n",
    "            d[\"A_cv\"] = []\n",
    "            d[\"R_cv\"] = []\n",
    "            d[\"P_cv\"] = []\n",
    "            d[\"F_cv\"] = []\n",
    "        n_iter = 0\n",
    "        g_min = 0\n",
    "        alpha = 0\n",
    "        #print(\"n_leafs\\tR\\talpha\")\n",
    "        n_leafs, R = self._g2(tree.root)\n",
    "        #print(f\"{n_leafs}\\t{R:.4f}\\t{g_min:.2e}\")\n",
    "        while tree.leaf_count() > 1 and n_iter < 100:\n",
    "            n_iter += 1\n",
    "            \n",
    "            alpha = g_min\n",
    "            if alpha_max is not None and alpha > alpha_max:\n",
    "                break\n",
    "            # compute g\n",
    "            nodes = tree.nodes()\n",
    "            g = []\n",
    "            pnodes = []\n",
    "            for n in nodes:\n",
    "                if not n.is_leaf:\n",
    "                    g.append(self._g(n))\n",
    "                    pnodes.append(n)\n",
    "                    \n",
    "            g_min = max(0,np.min(g))\n",
    "            for i, n in enumerate(pnodes):\n",
    "                if g[i] <= g_min:\n",
    "                    n.is_leaf = True\n",
    "            N, R = self._g2(tree.root)\n",
    "            #print(f\"{N}\\t{R:.4f}\\t{alpha:.2e}\")\n",
    "            if test_set is not None:\n",
    "                metrics = self.metrics(df=test_set)\n",
    "                d[\"A_cv\"].append(metrics[\"accuracy\"])\n",
    "                d[\"R_cv\"].append(metrics[\"recall\"])\n",
    "                d[\"P_cv\"].append(metrics[\"precision\"])\n",
    "                d[\"F_cv\"].append(metrics[\"F-score\"])\n",
    "            d[\"alpha\"].append(alpha)\n",
    "            d[\"n_leafs\"].append(N)\n",
    "            d[\"R\"].append(R)\n",
    "        return d\n",
    "            \n",
    "    \n",
    "    def _g(self,node):\n",
    "        n_leafs, R_desc = self._g2(node)\n",
    "        R = node.pinfo[\"R\"]\n",
    "        #print(n_leafs, R, R_desc)\n",
    "        return (R - R_desc)/(n_leafs - 1)\n",
    "                              \n",
    "    def _g2(self,node):\n",
    "        n_leafs = 0\n",
    "        R_desc = 0\n",
    "        if node.is_leaf:\n",
    "            return 1, node.pinfo[\"R\"]\n",
    "        \n",
    "        for b in node.branches:\n",
    "            nl, R = self._g2(b)\n",
    "            n_leafs += nl\n",
    "            R_desc += R\n",
    "        return n_leafs, R_desc\n",
    "    \n",
    "    def confusion_matrix(self,df=None):\n",
    "        if df is None:\n",
    "            df = self.df\n",
    "        unique = np.unique(self.df[self.y_name].values)\n",
    "        classes = unique.tolist()#self.tree.classes()\n",
    "        n_classes = len(classes)\n",
    "        confmat = np.zeros((n_classes,n_classes))\n",
    "        \n",
    "        for i in range(len(df.index)):\n",
    "            val_pred = self.tree.predict(df.iloc[i]).value\n",
    "            val_true = df[self.y_name].iloc[i]\n",
    "            i_pred = classes.index(val_pred)\n",
    "            i_true = classes.index(val_true)\n",
    "            confmat[i_true,i_pred] += 1\n",
    "        return confmat\n",
    "           \n",
    "    @staticmethod\n",
    "    def _precision(m):\n",
    "        return np.diag(m) / np.sum(m, axis=1)\n",
    "        \n",
    "    @staticmethod\n",
    "    def _recall(m):\n",
    "        return np.diag(m) / np.sum(m, axis=0)\n",
    "    \n",
    "    @staticmethod\n",
    "    def _F1(P,R):\n",
    "        #F = np.zeros_like(P)\n",
    "        #for i in range(len(\n",
    "        return 2 * P * R / (P + R)\n",
    "    \n",
    "    @staticmethod\n",
    "    def _accuracy(m):\n",
    "        return np.sum(np.diag(m))/np.sum(np.sum(m))\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Titanic dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Species</th>\n",
       "      <th>Weight</th>\n",
       "      <th>Length</th>\n",
       "      <th>Diagonal</th>\n",
       "      <th>Height</th>\n",
       "      <th>Width</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Bream</td>\n",
       "      <td>242.0</td>\n",
       "      <td>25.4</td>\n",
       "      <td>30.0</td>\n",
       "      <td>11.5200</td>\n",
       "      <td>4.0200</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Bream</td>\n",
       "      <td>290.0</td>\n",
       "      <td>26.3</td>\n",
       "      <td>31.2</td>\n",
       "      <td>12.4800</td>\n",
       "      <td>4.3056</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Bream</td>\n",
       "      <td>340.0</td>\n",
       "      <td>26.5</td>\n",
       "      <td>31.1</td>\n",
       "      <td>12.3778</td>\n",
       "      <td>4.6961</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Bream</td>\n",
       "      <td>363.0</td>\n",
       "      <td>29.0</td>\n",
       "      <td>33.5</td>\n",
       "      <td>12.7300</td>\n",
       "      <td>4.4555</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Bream</td>\n",
       "      <td>430.0</td>\n",
       "      <td>29.0</td>\n",
       "      <td>34.0</td>\n",
       "      <td>12.4440</td>\n",
       "      <td>5.1340</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>154</th>\n",
       "      <td>Smelt</td>\n",
       "      <td>12.2</td>\n",
       "      <td>12.2</td>\n",
       "      <td>13.4</td>\n",
       "      <td>2.0904</td>\n",
       "      <td>1.3936</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>155</th>\n",
       "      <td>Smelt</td>\n",
       "      <td>13.4</td>\n",
       "      <td>12.4</td>\n",
       "      <td>13.5</td>\n",
       "      <td>2.4300</td>\n",
       "      <td>1.2690</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>156</th>\n",
       "      <td>Smelt</td>\n",
       "      <td>12.2</td>\n",
       "      <td>13.0</td>\n",
       "      <td>13.8</td>\n",
       "      <td>2.2770</td>\n",
       "      <td>1.2558</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>157</th>\n",
       "      <td>Smelt</td>\n",
       "      <td>19.7</td>\n",
       "      <td>14.3</td>\n",
       "      <td>15.2</td>\n",
       "      <td>2.8728</td>\n",
       "      <td>2.0672</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>158</th>\n",
       "      <td>Smelt</td>\n",
       "      <td>19.9</td>\n",
       "      <td>15.0</td>\n",
       "      <td>16.2</td>\n",
       "      <td>2.9322</td>\n",
       "      <td>1.8792</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>159 rows × 6 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "    Species  Weight  Length  Diagonal   Height   Width\n",
       "0     Bream   242.0    25.4      30.0  11.5200  4.0200\n",
       "1     Bream   290.0    26.3      31.2  12.4800  4.3056\n",
       "2     Bream   340.0    26.5      31.1  12.3778  4.6961\n",
       "3     Bream   363.0    29.0      33.5  12.7300  4.4555\n",
       "4     Bream   430.0    29.0      34.0  12.4440  5.1340\n",
       "..      ...     ...     ...       ...      ...     ...\n",
       "154   Smelt    12.2    12.2      13.4   2.0904  1.3936\n",
       "155   Smelt    13.4    12.4      13.5   2.4300  1.2690\n",
       "156   Smelt    12.2    13.0      13.8   2.2770  1.2558\n",
       "157   Smelt    19.7    14.3      15.2   2.8728  2.0672\n",
       "158   Smelt    19.9    15.0      16.2   2.9322  1.8792\n",
       "\n",
       "[159 rows x 6 columns]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_fish = pd.read_csv(\"fish.txt\")\n",
    "df_fish"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Index(['Species', 'Weight', 'Length', 'Diagonal', 'Height', 'Width'], dtype='object')"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_fish.columns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Computed split:\n",
      "loss: 39786.48 (parent: 127342.51)\n",
      "attribute: Width\n",
      "threshold: 5.005274295811595\n",
      "count: [103, 56]\n",
      "Computed split:\n",
      "loss: 6087.95 (parent: 19505.88)\n",
      "attribute: Diagonal\n",
      "threshold: 28.52649207925825\n",
      "count: [71, 32]\n",
      "Computed split:\n",
      "loss: 1580.15 (parent: 4424.81)\n",
      "attribute: Length\n",
      "threshold: 18.81156638225784\n",
      "count: [27, 44]\n",
      "Computed split:\n",
      "loss: 151.55 (parent: 877.22)\n",
      "attribute: Diagonal\n",
      "threshold: 16.333300698107028\n",
      "count: [18, 9]\n",
      "Computed split:\n",
      "loss: 24.41 (parent: 113.73)\n",
      "attribute: Width\n",
      "threshold: 1.903212930208299\n",
      "count: [14, 4]\n",
      "Computed split:\n",
      "loss: 1040.78 (parent: 2011.50)\n",
      "attribute: Diagonal\n",
      "threshold: 24.73033588269824\n",
      "count: [28, 16]\n",
      "Computed split:\n",
      "loss: 674.21 (parent: 1027.81)\n",
      "attribute: Length\n",
      "threshold: 20.52786770636661\n",
      "count: [8, 20]\n",
      "Computed split:\n",
      "loss: 177.12 (parent: 261.25)\n",
      "attribute: Diagonal\n",
      "threshold: 23.85968049433315\n",
      "count: [13, 7]\n",
      "Computed split:\n",
      "loss: 244.62 (parent: 249.41)\n",
      "attribute: Length\n",
      "threshold: 21.503450454544055\n",
      "count: [8, 5]\n",
      "Computed split:\n",
      "loss: 659.15 (parent: 1063.48)\n",
      "attribute: Width\n",
      "threshold: 4.0232379927962585\n",
      "count: [11, 5]\n",
      "Computed split:\n",
      "loss: 412.30 (parent: 535.97)\n",
      "attribute: Species\n",
      "threshold: ('Roach',)\n",
      "count: [6, 5]\n",
      "Computed split:\n",
      "loss: 6320.93 (parent: 9778.03)\n",
      "attribute: Length\n",
      "threshold: 40.22231730803107\n",
      "count: [28, 4]\n",
      "Computed split:\n",
      "loss: 2139.53 (parent: 7000.61)\n",
      "attribute: Height\n",
      "threshold: 13.087007443615606\n",
      "count: [23, 5]\n",
      "Computed split:\n",
      "loss: 1976.67 (parent: 2474.22)\n",
      "attribute: Diagonal\n",
      "threshold: 31.603640975241916\n",
      "count: [15, 8]\n",
      "Computed split:\n",
      "loss: 394.89 (parent: 731.16)\n",
      "attribute: Width\n",
      "threshold: 4.594409832535237\n",
      "count: [10, 5]\n",
      "Computed split:\n",
      "loss: 235.88 (parent: 339.21)\n",
      "attribute: Length\n",
      "threshold: 27.006892385958672\n",
      "count: [6, 4]\n",
      "Computed split:\n",
      "loss: 37996.71 (parent: 77088.31)\n",
      "attribute: Length\n",
      "threshold: 54.16343249220135\n",
      "count: [52, 4]\n",
      "Computed split:\n",
      "loss: 17238.35 (parent: 39056.55)\n",
      "attribute: Diagonal\n",
      "threshold: 40.936783693311085\n",
      "count: [28, 24]\n",
      "Computed split:\n",
      "loss: 7212.96 (parent: 17055.32)\n",
      "attribute: Length\n",
      "threshold: 32.42028558560921\n",
      "count: [9, 19]\n",
      "Computed split:\n",
      "loss: 8431.11 (parent: 10343.21)\n",
      "attribute: Height\n",
      "threshold: 12.720316407830028\n",
      "count: [4, 5]\n",
      "Computed split:\n",
      "loss: 3203.79 (parent: 5730.22)\n",
      "attribute: Length\n",
      "threshold: 34.56217279367394\n",
      "count: [9, 10]\n",
      "Computed split:\n",
      "loss: 2348.96 (parent: 2559.00)\n",
      "attribute: Height\n",
      "threshold: 14.150183202691982\n",
      "count: [6, 4]\n",
      "Computed split:\n",
      "loss: 9060.19 (parent: 17451.89)\n",
      "attribute: Width\n",
      "threshold: 6.280238667483136\n",
      "count: [6, 18]\n",
      "Computed split:\n",
      "loss: 3540.39 (parent: 6208.95)\n",
      "attribute: Diagonal\n",
      "threshold: 42.551166078918634\n",
      "count: [6, 12]\n",
      "Computed split:\n",
      "loss: 1492.01 (parent: 3058.85)\n",
      "attribute: Species\n",
      "threshold: ('Bream',)\n",
      "count: [6, 6]\n",
      "A tree with 26 leafs was created\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<__main__.Tree at 0x7fefd6355210>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "c_fish = CART(df_fish,\"Weight\", min_leaf_samples=5, min_split_samples=4)\n",
    "c_fish.create_tree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Width<5.01\n",
      "├── False:Length<54.16\n",
      "│   ├── False:1512.5\n",
      "│   └── True: Diagonal<40.94\n",
      "│       ├── False:Width<6.28\n",
      "│       │   ├── False:Diagonal<42.55\n",
      "│       │   │   ├── False:Species in ('Bream',)\n",
      "│       │   │   │   ├── False:1033.3333333333333\n",
      "│       │   │   │   └── True: 954.1666666666666\n",
      "│       │   │   └── True: 884.1666666666666\n",
      "│       │   └── True: 745.6666666666666\n",
      "│       └── True: Length<32.42\n",
      "│           ├── False:Length<34.56\n",
      "│           │   ├── False:Height<14.15\n",
      "│           │   │   ├── False:706.25\n",
      "│           │   │   └── True: 735.8333333333334\n",
      "│           │   └── True: 623.3333333333334\n",
      "│           └── True: Height<12.72\n",
      "│               ├── False:503.0\n",
      "│               └── True: 415.0\n",
      "└── True: Diagonal<28.53\n",
      "    ├── False:Length<40.22\n",
      "    │   ├── False:508.25\n",
      "    │   └── True: Height<13.09\n",
      "    │       ├── False:480.0\n",
      "    │       └── True: Diagonal<31.60\n",
      "    │           ├── False:328.5\n",
      "    │           └── True: Width<4.59\n",
      "    │               ├── False:307.6\n",
      "    │               └── True: Length<27.01\n",
      "    │                   ├── False:256.25\n",
      "    │                   └── True: 277.0\n",
      "    └── True: Length<18.81\n",
      "        ├── False:Diagonal<24.73\n",
      "        │   ├── False:Width<4.02\n",
      "        │   │   ├── False:215.2\n",
      "        │   │   └── True: Species in ('Roach',)\n",
      "        │   │       ├── False:184.0\n",
      "        │   │       └── True: 161.66666666666666\n",
      "        │   └── True: Length<20.53\n",
      "        │       ├── False:Diagonal<23.86\n",
      "        │       │   ├── False:145.0\n",
      "        │       │   └── True: Length<21.50\n",
      "        │       │       ├── False:123.0\n",
      "        │       │       └── True: 127.5\n",
      "        │       └── True: 90.875\n",
      "        └── True: Diagonal<16.33\n",
      "            ├── False:72.38888888888889\n",
      "            └── True: Width<1.90\n",
      "                ├── False:32.925\n",
      "                └── True: 10.192857142857145\n",
      "\n"
     ]
    }
   ],
   "source": [
    "c_fish.tree.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "277.0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "c_fish.tree.predict(df_fish.iloc[0]).value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'R_squared': 0.9773019948277384}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "c_fish.metrics()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}