cart_example.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example of CART\n",
    "### See [CART WITH PYTHON](https://machinelearningmastery.com/implement-decision-tree-algorithm-scratch-python/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Define the Gini score (same as reminder in ID3) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini_score(partitions, labels):\n",
    "    # count the amount of samples (or instances) in the split point\n",
    "    n_instances = float(sum([len(partition) for partition in partitions]))\n",
    "    # sum the weighted Gini index for each group\n",
    "    gini = 0.0\n",
    "    for partition in partitions:\n",
    "        # Take the number of instances in each partition\n",
    "        size = float(len(partition))\n",
    "        # safety check to avoid dividing by cero. gini = 0 for this partition\n",
    "        if size == 0:\n",
    "            continue\n",
    "        else:\n",
    "            p_2 = 0.0 # probability of occurence squared\n",
    "            # for each posible level (or label) of the target feature\n",
    "            for label in labels:\n",
    "                # calculate the frequency of appearance of the label in the partition\n",
    "                p = [instance[-1] for instance in partition].count(label) / size\n",
    "                p_2 += p*p\n",
    "            # increase the score by the weighted gini index of each label\n",
    "            gini += (1.0-p_2)*(size/n_instances)\n",
    "    return gini"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.5\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "# test Gini values\n",
    "print(gini_score([[[1, 1], [1, 0]], [[1, 1], [1, 0]]], [0, 1]))\n",
    "print(gini_score([[[1, 0], [1, 0]], [[1, 1], [1, 1]]], [0, 1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create partitions from a dataset, separating instances by certain feature\n",
    "def test_split(feature, level, dataset):\n",
    "    left, right = list(), list()\n",
    "    for instance in dataset:\n",
    "        if instance[feature] < level:\n",
    "            left.append(instance)\n",
    "        else:\n",
    "            right.append(instance)\n",
    "    return left, right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "# select the best split point for a dataset\n",
    "def get_split(dataset):\n",
    "    labels = list(set(instance[-1] for instance in dataset))\n",
    "    b_feature, b_level, b_score, b_partitions = 999, 999, 999, None\n",
    "    # Iterate over each feature in the dataset (avoid target)\n",
    "    for feature in range(len(dataset[0])-1):\n",
    "        # Iterate over each instance in the dataset\n",
    "        for instance in dataset:\n",
    "            partitions = test_split(feature, instance[feature], dataset)\n",
    "            gini = gini_score(partitions, labels)\n",
    "            if gini < b_score:\n",
    "                b_feature, b_level, b_score, b_partitions = feature, instance[feature], gini, partitions\n",
    "    # return best feature, split level and children partitions for the node\n",
    "    return {'feature': b_feature, 'level':b_level,'partitions':b_partitions}    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Split: [X1 < 6.642]\n"
     ]
    }
   ],
   "source": [
    "dataset = [[2.771244718,1.784783929,0],\n",
    "\t[1.728571309,1.169761413,0],\n",
    "\t[3.678319846,2.81281357,0],\n",
    "\t[3.961043357,2.61995032,0],\n",
    "\t[2.999208922,2.209014212,0],\n",
    "\t[7.497545867,3.162953546,1],\n",
    "\t[9.00220326,3.339047188,1],\n",
    "\t[7.444542326,0.476683375,1],\n",
    "\t[10.12493903,3.234550982,1],\n",
    "\t[6.642287351,3.319983761,1]]\n",
    "split = get_split(dataset)\n",
    "print('Split: [X%d < %.3f]' % ((split['feature']+1), split['level']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### For each leaf in the tree, choose the most frequent label on the instances of the partition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a leaf node with the most common target level\n",
    "def to_terminal(partition):\n",
    "    outcomes = [instance[-1] for instance in partition]\n",
    "    return max(set(outcomes),key=outcomes.count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The terminal label of the above dataset is 0\n"
     ]
    }
   ],
   "source": [
    "# Testing above function\n",
    "print(\"The terminal label of the above dataset is\", to_terminal(dataset))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Using a recursive procedure, build the tree while spliting the dataset in partitions. Avoid overfitting relaying on pre-prunning (max. depth and min. num. instances)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create split of the dataset to make a new node or a leaf\n",
    "def split(node, max_depth, min_size, depth):\n",
    "    # Take partitions and delete the key in the node dict. structure\n",
    "    left, right = node['partitions']\n",
    "    del(node['partitions'])\n",
    "    # Check base conditions\n",
    "    # 1. No more instances\n",
    "    if not left or not right:\n",
    "        node['left'] = node['right'] = to_terminal( left + right )\n",
    "        return\n",
    "    # 2. max. depth reached\n",
    "    if depth >= max_depth:\n",
    "        node['left'], node['right'] = to_terminal(left), to_terminal(right)\n",
    "        return\n",
    "    # Process left child\n",
    "    if len(left) <= min_size:\n",
    "        node['left'] = to_terminal(left)      \n",
    "    else:\n",
    "        node['left'] = get_split(left)\n",
    "        split(node['left'], max_depth, min_size, depth+1 )\n",
    "        # Process right child\n",
    "    if len(right) <= min_size:\n",
    "        node['right'] = to_terminal(right)      \n",
    "    else:\n",
    "        node['right'] = get_split(right)\n",
    "        split(node['right'], max_depth, min_size, depth+1 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Build decision tree function\n",
    "def build_tree( train_dataset, max_depth, min_size):\n",
    "    # Start by taking the root node\n",
    "    root = get_split(train_dataset)\n",
    "    # Call split to traverse the rest of the tree\n",
    "    split(root, max_depth, min_size, 1)\n",
    "    # return tree\n",
    "    return root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Testing with the above dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Print a decision tree\n",
    "def print_tree(node, depth=0):\n",
    "\tif isinstance(node, dict):\n",
    "\t\tprint('%s[X%d < %.3f]' % ((depth*' ', (node['feature']+1), node['level'])))\n",
    "\t\tprint_tree(node['left'], depth+1)\n",
    "\t\tprint_tree(node['right'], depth+1)\n",
    "\telse:\n",
    "\t\tprint('%s[%s]' % ((depth*' ', node)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[X1 < 6.642]\n",
      " [X1 < 2.771]\n",
      "  [0]\n",
      "  [X1 < 2.771]\n",
      "   [0]\n",
      "   [0]\n",
      " [X1 < 7.498]\n",
      "  [X1 < 7.445]\n",
      "   [1]\n",
      "   [1]\n",
      "  [X1 < 7.498]\n",
      "   [1]\n",
      "   [1]\n"
     ]
    }
   ],
   "source": [
    "print_tree(build_tree(dataset,3,1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Create predicting function (also recursive)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Make a prediction with a decision tree\n",
    "def predict(node, query):\n",
    "    if query[node['feature']] < node['level']:\n",
    "        # Check whether the leaf was reached\n",
    "        if isinstance(node['left'],dict):\n",
    "            return predict(node['left'],query)\n",
    "        else:\n",
    "            return node['left']\n",
    "    else:\n",
    "    # Check whether the leaf was reached\n",
    "        if isinstance(node['right'],dict):\n",
    "            return predict(node['right'],query)\n",
    "        else:\n",
    "            return node['right']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected=0, Got=0\n",
      "Expected=0, Got=0\n",
      "Expected=0, Got=0\n",
      "Expected=0, Got=0\n",
      "Expected=0, Got=0\n",
      "Expected=1, Got=1\n",
      "Expected=1, Got=1\n",
      "Expected=1, Got=1\n",
      "Expected=1, Got=1\n",
      "Expected=1, Got=1\n"
     ]
    }
   ],
   "source": [
    "#  predict with a stump\n",
    "stump = {'feature': 0, 'right': 1, 'level': 6.642287351, 'left': 0}\n",
    "for instance in dataset:\n",
    "\tprediction = predict(stump, instance)\n",
    "\tprint('Expected=%d, Got=%d' % (instance[-1], prediction))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let use the Banknote dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import necessary modules\n",
    "from random import seed\n",
    "from random import randrange\n",
    "from csv import reader"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load a CSV file helper function\n",
    "def load_csv(filename):\n",
    "    file = open(filename,'r+')\n",
    "    lines = reader(file)\n",
    "    dataset = list(lines)\n",
    "    return dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Convert string column to float helper function\n",
    "def str_column_to_float(dataset,column):\n",
    "    for instance in dataset:\n",
    "        instance[column] = float(instance[column].strip())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Split the dataset into a number of folds for validation\n",
    "def cross_validation_split(dataset, n_folds):\n",
    "\tdataset_split = list()\n",
    "\tdataset_copy = list(dataset)\n",
    "\tfold_size = int(len(dataset) / n_folds)\n",
    "\tfor i in range(n_folds):\n",
    "\t\tfold = list()\n",
    "\t\twhile len(fold) < fold_size:\n",
    "\t\t\tindex = randrange(len(dataset_copy))\n",
    "\t\t\tfold.append(dataset_copy.pop(index))\n",
    "\t\tdataset_split.append(fold)\n",
    "\treturn dataset_split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate accuracy percentage (how many instances of the evaluation dataset were correctly predicted)\n",
    "def accuracy_metric(actual, predicted):\n",
    "    correct = 0\n",
    "    for i in range(len(actual)):\n",
    "        if actual[i] == predicted[i]:\n",
    "            correct += 1\n",
    "    return (correct / float(len(actual))) * 100.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Function for evaluating the learnt model\n",
    "def evaluate_algorithm(dataset, algorithm, n_folds, *args):\n",
    "\tfolds = cross_validation_split(dataset, n_folds)\n",
    "\tscores = list()\n",
    "\tfor fold in folds:\n",
    "\t\ttrain_set = list(folds)\n",
    "\t\ttrain_set.remove(fold)\n",
    "\t\ttrain_set = sum(train_set, [])\n",
    "\t\ttest_set = list()\n",
    "\t\tfor instance in fold:\n",
    "\t\t\tinstance_copy = list(instance)\n",
    "\t\t\ttest_set.append(instance_copy)\n",
    "\t\t\tinstance_copy[-1] = None\n",
    "\t\tpredicted = algorithm(train_set, test_set, *args)\n",
    "\t\tactual = [instance[-1] for instance in fold]\n",
    "\t\taccuracy = accuracy_metric(actual, predicted)\n",
    "\t\tscores.append(accuracy)\n",
    "\treturn scores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Classification and Regression Tree Algorithm\n",
    "def decision_tree(train_dataset, test_dataset, max_depth, min_size):\n",
    "\ttree = build_tree(train_dataset, max_depth, min_size)\n",
    "\tpredictions = list()\n",
    "\tfor instance  in test_dataset:\n",
    "\t\tprediction = predict(tree, instance)\n",
    "\t\tpredictions.append(prediction)\n",
    "\treturn predictions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Test CART on Bank Note dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Scores: [96.35036496350365, 97.08029197080292, 97.44525547445255, 98.17518248175182, 97.44525547445255]\n",
      "Mean Accuracy: 97.299%\n"
     ]
    }
   ],
   "source": [
    "seed(1)\n",
    "# load and prepare data\n",
    "filename = 'data_banknote_authentication.csv'\n",
    "dataset = load_csv(filename)\n",
    "# convert string attributes to integers\n",
    "for column in range(len(dataset[0])):\n",
    "\tstr_column_to_float(dataset, column)\n",
    "# evaluate algorithm\n",
    "n_folds = 5\n",
    "max_depth = 5\n",
    "min_size = 10\n",
    "scores = evaluate_algorithm(dataset, decision_tree, n_folds, max_depth, min_size)\n",
    "print('Scores: %s' % scores)\n",
    "print('Mean Accuracy: %.3f%%' % (sum(scores)/float(len(scores))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Doing the same with [random forest instead](https://github.com/llSourcell/random_forests/blob/master/Random%20Forests%20.ipynb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "# select the best split point for a dataset and apply feature select\n",
    "def get_split_rf(dataset, n_features):\n",
    "    labels = list(set(instance[-1] for instance in dataset))\n",
    "    b_feature, b_level, b_score, b_partitions = 999, 999, 999, None\n",
    "    features = list()\n",
    "    # Select random features\n",
    "    while len(features) < n_features:\n",
    "        index = randrange(len(dataset[0])-1)\n",
    "        if index not in features:\n",
    "            features.append(index)\n",
    "    # Iterate over each feature previously selected\n",
    "    for feature in features:\n",
    "        # Iterate over each instance in the dataset\n",
    "        for instance in dataset:\n",
    "            partitions = test_split(feature, instance[feature], dataset)\n",
    "            gini = gini_score(partitions, labels)\n",
    "            if gini < b_score:\n",
    "                b_feature, b_level, b_score, b_partitions = feature, instance[feature], gini, partitions\n",
    "    # return best feature, split level and children partitions for the node\n",
    "    return {'feature': b_feature, 'level':b_level,'partitions':b_partitions}    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create split of the dataset to make a new node or a leaf for random forest\n",
    "def split_rf(node, max_depth, min_size, n_features, depth):\n",
    "    # Take partitions and delete the key in the node dict. structure\n",
    "    left, right = node['partitions']\n",
    "    del(node['partitions'])\n",
    "    # Check base conditions\n",
    "    # 1. No more instances\n",
    "    if not left or not right:\n",
    "        node['left'] = node['right'] = to_terminal( left + right )\n",
    "        return\n",
    "    # 2. max. depth reached\n",
    "    if depth >= max_depth:\n",
    "        node['left'], node['right'] = to_terminal(left), to_terminal(right)\n",
    "        return\n",
    "    # Process left child\n",
    "    if len(left) <= min_size:\n",
    "        node['left'] = to_terminal(left)      \n",
    "    else:\n",
    "        node['left'] = get_split_rf(left, n_features)\n",
    "        split_rf(node['left'], max_depth, min_size, n_features, depth+1 )\n",
    "        # Process right child\n",
    "    if len(right) <= min_size:\n",
    "        node['right'] = to_terminal(right)      \n",
    "    else:\n",
    "        node['right'] = get_split_rf(right, n_features)\n",
    "        split_rf(node['right'], max_depth, min_size, n_features, depth+1 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Build decision tree function with feature select for random forest\n",
    "def build_tree_rf( train_dataset, max_depth, min_size, n_features):\n",
    "    # Start by taking the root node\n",
    "    root = get_split_rf(train_dataset, n_features)\n",
    "    # Call split to traverse the rest of the tree\n",
    "    split_rf(root, max_depth, min_size, n_features, 1)\n",
    "    # return tree\n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a random subsample from the dataset with replacement\n",
    "def subsample(dataset, ratio):\n",
    "\tsample = list()\n",
    "    # Take a pecentage of the dataset for making the sample\n",
    "\tn_sample = round(len(dataset) * ratio)\n",
    "\twhile len(sample) < n_sample:\n",
    "\t\tindex = randrange(len(dataset))\n",
    "\t\tsample.append(dataset[index])\n",
    "\treturn sample"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Make a combined prediction\n",
    "def bagging_predict(trees, query):\n",
    "\tpredictions = [predict(tree, query) for tree in trees]\n",
    "\treturn max(set(predictions), key=predictions.count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Model esemble: Random forest\n",
    "# First, train the model using the instances in train_dataset\n",
    "# Then predict the label of each instance in test_dataset\n",
    "def random_forest(train_dataset, test_dataset, max_depth, min_size, sample_size, n_trees, n_features):\n",
    "\ttrees = list()\n",
    "\tfor i in range(n_trees):\n",
    "\t\tsample = subsample(train_dataset, sample_size)\n",
    "\t\ttree = build_tree_rf(sample, max_depth, min_size, n_features)\n",
    "\t\ttrees.append(tree)\n",
    "\tpredictions = [bagging_predict(trees, query) for query in test_dataset]\n",
    "\treturn predictions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "#square root function\n",
    "from math import sqrt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Trees: 1\n",
      "Scores: [96.71532846715328, 97.44525547445255, 99.63503649635037, 94.16058394160584, 94.8905109489051]\n",
      "Mean Accuracy: 96.569%\n",
      "Trees: 5\n",
      "Scores: [100.0, 98.54014598540147, 98.17518248175182, 98.17518248175182, 98.17518248175182]\n",
      "Mean Accuracy: 98.613%\n",
      "Trees: 10\n",
      "Scores: [99.27007299270073, 99.63503649635037, 98.90510948905109, 98.54014598540147, 98.54014598540147]\n",
      "Mean Accuracy: 98.978%\n"
     ]
    }
   ],
   "source": [
    "# evaluate algorithm\n",
    "n_folds = 5\n",
    "max_depth = 10\n",
    "min_size = 1\n",
    "sample_size = 1.0\n",
    "n_features = int(sqrt(len(dataset[0])-1))\n",
    "for n_trees in [1, 5, 10]:\n",
    "\tscores = evaluate_algorithm(dataset, random_forest, n_folds, max_depth, min_size, sample_size, n_trees, n_features)\n",
    "\tprint('Trees: %d' % n_trees)\n",
    "\tprint('Scores: %s' % scores)\n",
    "\tprint('Mean Accuracy: %.3f%%' % (sum(scores)/float(len(scores))))"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}