decision_tree_classification.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Import tools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from sklearn.metrics import accuracy_score\n",
    "from sklearn.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Get the data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "col_names = ['sepal_length', 'sepal_width', 'petal_length', 'petal_width', 'type']\n",
    "data = pd.read_csv(\"data/train.csv\")#, skiprows=1, header=None, names=col_names)\n",
    "# data.head(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Node class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node():\n",
    "    def __init__(self, feature_index=None, threshold=None, left=None, right=None, info_gain=None, value=None):\n",
    "        ''' constructor ''' \n",
    "        \n",
    "        # for decision node\n",
    "        self.feature_index = feature_index\n",
    "        self.threshold = threshold\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.info_gain = info_gain\n",
    "        \n",
    "        # for leaf node\n",
    "        self.value = value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tree class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DecisionTreeClassifier():\n",
    "    def __init__(self, min_samples_split=2, max_depth=2):\n",
    "        ''' constructor '''\n",
    "        \n",
    "        # initialize the root of the tree \n",
    "        self.root = None\n",
    "        \n",
    "        # stopping conditions\n",
    "        self.min_samples_split = min_samples_split\n",
    "        self.max_depth = max_depth\n",
    "        \n",
    "    def build_tree(self, dataset, curr_depth=0):\n",
    "        ''' recursive function to build the tree ''' \n",
    "        \n",
    "        X, Y = dataset[:,:-1], dataset[:,-1]\n",
    "        num_samples, num_features = np.shape(X)\n",
    "        \n",
    "        # split until stopping conditions are met\n",
    "        if num_samples>=self.min_samples_split and curr_depth<=self.max_depth:\n",
    "            # find the best split\n",
    "            best_split = self.get_best_split(dataset, num_samples, num_features)\n",
    "            # check if information gain is positive\n",
    "            if best_split[\"info_gain\"]>0:\n",
    "                # recur left\n",
    "                left_subtree = self.build_tree(best_split[\"dataset_left\"], curr_depth+1)\n",
    "                # recur right\n",
    "                right_subtree = self.build_tree(best_split[\"dataset_right\"], curr_depth+1)\n",
    "                # return decision node\n",
    "                return Node(best_split[\"feature_index\"], best_split[\"threshold\"], \n",
    "                            left_subtree, right_subtree, best_split[\"info_gain\"])\n",
    "        \n",
    "        # compute leaf node\n",
    "        leaf_value = self.calculate_leaf_value(Y)\n",
    "        # return leaf node\n",
    "        return Node(value=leaf_value)\n",
    "    \n",
    "    def get_best_split(self, dataset, num_samples, num_features):\n",
    "        ''' function to find the best split '''\n",
    "        \n",
    "        # dictionary to store the best split\n",
    "        best_split = {}\n",
    "        max_info_gain = -float(\"inf\")\n",
    "        \n",
    "        # loop over all the features\n",
    "        for feature_index in range(num_features):\n",
    "            feature_values = dataset[:, feature_index]\n",
    "            possible_thresholds = np.unique(feature_values)\n",
    "            # loop over all the feature values present in the data\n",
    "            for threshold in possible_thresholds:\n",
    "                # get current split\n",
    "                dataset_left, dataset_right = self.split(dataset, feature_index, threshold)\n",
    "                # check if childs are not null\n",
    "                if len(dataset_left)>0 and len(dataset_right)>0:\n",
    "                    y, left_y, right_y = dataset[:, -1], dataset_left[:, -1], dataset_right[:, -1]\n",
    "                    # compute information gain\n",
    "                    curr_info_gain = self.information_gain(y, left_y, right_y, \"gini\")\n",
    "                    # update the best split if needed\n",
    "                    if curr_info_gain>max_info_gain:\n",
    "                        best_split[\"feature_index\"] = feature_index\n",
    "                        best_split[\"threshold\"] = threshold\n",
    "                        best_split[\"dataset_left\"] = dataset_left\n",
    "                        best_split[\"dataset_right\"] = dataset_right\n",
    "                        best_split[\"info_gain\"] = curr_info_gain\n",
    "                        max_info_gain = curr_info_gain\n",
    "                        \n",
    "        # return best split\n",
    "        return best_split\n",
    "    \n",
    "    def split(self, dataset, feature_index, threshold):\n",
    "        ''' function to split the data '''\n",
    "        \n",
    "        dataset_left = np.array([row for row in dataset if row[feature_index]<=threshold])\n",
    "        dataset_right = np.array([row for row in dataset if row[feature_index]>threshold])\n",
    "        return dataset_left, dataset_right\n",
    "    \n",
    "    def information_gain(self, parent, l_child, r_child, mode=\"entropy\"):\n",
    "        ''' function to compute information gain '''\n",
    "        \n",
    "        weight_l = len(l_child) / len(parent)\n",
    "        weight_r = len(r_child) / len(parent)\n",
    "        if mode==\"gini\":\n",
    "            gain = self.gini_index(parent) - (weight_l*self.gini_index(l_child) + weight_r*self.gini_index(r_child))\n",
    "        else:\n",
    "            gain = self.entropy(parent) - (weight_l*self.entropy(l_child) + weight_r*self.entropy(r_child))\n",
    "        return gain\n",
    "    \n",
    "    def entropy(self, y):\n",
    "        ''' function to compute entropy '''\n",
    "        \n",
    "        class_labels = np.unique(y)\n",
    "        entropy = 0\n",
    "        for cls in class_labels:\n",
    "            p_cls = len(y[y == cls]) / len(y)\n",
    "            entropy += -p_cls * np.log2(p_cls)\n",
    "        return entropy\n",
    "    \n",
    "    def gini_index(self, y):\n",
    "        ''' function to compute gini index '''\n",
    "        \n",
    "        class_labels = np.unique(y)\n",
    "        gini = 0\n",
    "        for cls in class_labels:\n",
    "            p_cls = len(y[y == cls]) / len(y)\n",
    "            gini += p_cls**2\n",
    "        return 1 - gini\n",
    "        \n",
    "    def calculate_leaf_value(self, Y):\n",
    "        ''' function to compute leaf node '''\n",
    "        \n",
    "        Y = list(Y)\n",
    "        return max(Y, key=Y.count)\n",
    "    \n",
    "    def print_tree(self, tree=None, indent=\" \"):\n",
    "        ''' function to print the tree '''\n",
    "        \n",
    "        if not tree:\n",
    "            tree = self.root\n",
    "\n",
    "        if tree.value is not None:\n",
    "            print(tree.value)\n",
    "\n",
    "        else:\n",
    "            print(\"X_\"+str(tree.feature_index), \"<=\", tree.threshold, \"?\", tree.info_gain)\n",
    "            print(\"%sleft:\" % (indent), end=\"\")\n",
    "            self.print_tree(tree.left, indent + indent)\n",
    "            print(\"%sright:\" % (indent), end=\"\")\n",
    "            self.print_tree(tree.right, indent + indent)\n",
    "    \n",
    "    def fit(self, X, Y):\n",
    "        ''' function to train the tree '''\n",
    "        \n",
    "        dataset = np.concatenate((X, Y), axis=1)\n",
    "        self.root = self.build_tree(dataset)\n",
    "    \n",
    "    def predict(self, X):\n",
    "        ''' function to predict new dataset '''\n",
    "        \n",
    "        preditions = [self.make_prediction(x, self.root) for x in X]\n",
    "        return preditions \n",
    "    \n",
    "    def make_prediction(self, x, tree):\n",
    "        ''' function to predict a single data point '''\n",
    "        \n",
    "        if tree.value!=None: return tree.value\n",
    "        feature_val = x[tree.feature_index]\n",
    "        if feature_val<=tree.threshold:\n",
    "            return self.make_prediction(x, tree.left)\n",
    "        else:\n",
    "            return self.make_prediction(x, tree.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Train-Test split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = data.iloc[:, :-1].values\n",
    "Y = data.iloc[:, -1].values.reshape(-1,1)\n",
    "X_train, X_test, Y_train, Y_test = train_test_split(X, Y, test_size=.2, random_state=50)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fit the model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X_9 <= 143.0 ? 0.2795848051344126\n",
      " left:X_9 <= 58.0 ? 0.04730414820372944\n",
      "  left:X_8 <= 2.0 ? 0.00457815946391027\n",
      "    left:X_2 <= 1.0 ? 0.0005226824457593496\n",
      "        left:1.0\n",
      "        right:X_0 <= 0.0 ? 0.0131944444444443\n",
      "                left:1.0\n",
      "                right:X_1 <= 0.0 ? 0.31999999999999984\n",
      "                                left:0.0\n",
      "                                right:1.0\n",
      "    right:X_1 <= 0.18 ? 0.04610581925878496\n",
      "        left:X_10 <= 22.0 ? 0.1742872512103283\n",
      "                left:0.0\n",
      "                right:X_1 <= 0.16 ? 0.1338842975206611\n",
      "                                left:X_9 <= 32.0 ? 0.046666666666666606\n",
      "                                                                left:1.0\n",
      "                                                                right:X_8 <= 3.0 ? 0.4444444444444444\n",
      "                                                                                                                                left:0.0\n",
      "                                                                                                                                right:1.0\n",
      "                                right:0.0\n",
      "        right:1.0\n",
      "  right:X_1 <= 0.19 ? 0.1884896812204549\n",
      "    left:X_0 <= 0.0 ? 0.1019988047015074\n",
      "        left:1.0\n",
      "        right:X_10 <= 399.0 ? 0.06824846707544652\n",
      "                left:X_5 <= 10.0 ? 0.041717907482735794\n",
      "                                left:X_2 <= 2.0 ? 0.09297520661157027\n",
      "                                                                left:X_2 <= 1.0 ? 0.08333333333333337\n",
      "                                                                                                                                left:X_9 <= 102.0 ? 0.17361111111111105\n",
      "                                                                                                                                                                                                                                                                left:X_10 <= 34.0 ? 0.11160714285714285\n",
      "                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                left:0.0\n",
      "                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                right:X_7 <= 0.0 ? 0.217687074829932\n",
      "                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                left:1.0\n",
      "                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                right:X_8 <= 0.0 ? 0.4444444444444444\n",
      "                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                left:1.0\n",
      "                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                right:0.0\n",
      "                                                                                                                                                                                                                                                                right:0.0\n",
      "                                                                                                                                right:0.0\n",
      "                                                                right:1.0\n",
      "                                right:0.0\n",
      "                right:1.0\n",
      "    right:X_7 <= 0.0 ? 0.010822060353798006\n",
      "        left:1.0\n",
      "        right:X_8 <= 5.0 ? 0.31999999999999984\n",
      "                left:1.0\n",
      "                right:0.0\n",
      " right:X_1 <= 0.33 ? 0.06105010842526848\n",
      "  left:X_0 <= 0.0 ? 0.028173966539563042\n",
      "    left:X_5 <= 0.0 ? 0.40816326530612246\n",
      "        left:1.0\n",
      "        right:0.0\n",
      "    right:X_5 <= 146.0 ? 0.007410622051098104\n",
      "        left:X_1 <= 0.18 ? 0.007537517828641968\n",
      "                left:X_10 <= 1109.0 ? 0.0012259962259963675\n",
      "                                left:X_9 <= 219.0 ? 0.0005340979366952239\n",
      "                                                                left:X_9 <= 218.0 ? 0.09070294784580502\n",
      "                                                                                                                                left:0.0\n",
      "                                                                                                                                right:1.0\n",
      "                                                                right:0.0\n",
      "                                right:X_10 <= 1124.0 ? 0.06816568047337264\n",
      "                                                                left:1.0\n",
      "                                                                right:X_9 <= 505.0 ? 0.01679999999999998\n",
      "                                                                                                                                left:X_8 <= 26.0 ? 0.375\n",
      "                                                                                                                                                                                                                                                                left:1.0\n",
      "                                                                                                                                                                                                                                                                right:0.0\n",
      "                                                                                                                                right:0.0\n",
      "                right:X_9 <= 221.0 ? 0.16302901250998159\n",
      "                                left:X_8 <= 8.0 ? 0.375\n",
      "                                                                left:1.0\n",
      "                                                                right:0.0\n",
      "                                right:X_10 <= 3678.0 ? 0.14201183431952646\n",
      "                                                                left:0.0\n",
      "                                                                right:1.0\n",
      "        right:X_6 <= 0.0 ? 0.17777777777777776\n",
      "                left:X_7 <= 0.0 ? 0.17999999999999994\n",
      "                                left:X_8 <= 9.0 ? 0.375\n",
      "                                                                left:0.0\n",
      "                                                                right:1.0\n",
      "                                right:0.0\n",
      "                right:0.0\n",
      "  right:X_5 <= 0.0 ? 0.308641975308642\n",
      "    left:1.0\n",
      "    right:X_1 <= 0.45 ? 0.2777777777777777\n",
      "        left:0.0\n",
      "        right:1.0\n"
     ]
    }
   ],
   "source": [
    "classifier = DecisionTreeClassifier(min_samples_split=2, max_depth=11)\n",
    "classifier.fit(X_train,Y_train)\n",
    "classifier.print_tree()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test the model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9051724137931034"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Y_pred = classifier.predict(X_test) \n",
    "accuracy_score(Y_test, Y_pred)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test the model using new data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.9083333333333333\n"
     ]
    }
   ],
   "source": [
    "data_new = pd.read_csv('data/test.csv')\n",
    "y_new = data_new['fake']\n",
    "X = data_new.drop(['fake'], axis = 1).values\n",
    "y_new_predict = classifier.predict(X)\n",
    "print(accuracy_score(y_new, y_new_predict))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}