5. Random Forest.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import random\n",
    "import operator\n",
    "\n",
    "from sklearn import model_selection\n",
    "from sklearn.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#load data\n",
    "df = pd.read_csv('../data/breast-cancer-wisconsin.data.txt')\n",
    "\n",
    "#clean data\n",
    "df = df.replace('?',-99999)\n",
    "df = df.astype(float)\n",
    "df = df.drop(['id'],1)\n",
    "\n",
    "#shuffle data\n",
    "df = df.reindex(np.random.permutation(df.index))\n",
    "df = df.reset_index(drop=True)\n",
    "\n",
    "#copy data\n",
    "tf = df.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# prepare configuration for cross validation test harness\n",
    "seed = 7\n",
    "\n",
    "X_train, X_test, y_train, y_test = model_selection.train_test_split(tf.iloc[:,:9], \n",
    "                                                                    tf.iloc[:,9], \n",
    "                                                                    test_size=0.25, \n",
    "                                                                    random_state=seed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class RandomForest(object):\n",
    "    \n",
    "    def __init__(self, max_depth=5, min_size=1, n_trees=10, sample_size=1.0, printing=False):\n",
    "        self.max_depth = max_depth\n",
    "        self.min_size = min_size\n",
    "        self.n_trees = n_trees\n",
    "        self.sample_size = sample_size\n",
    "        self.printing = printing\n",
    "    \n",
    "    # Split a dataset based on an attribute and an attribute value\n",
    "    def threshold_split(self, feature_index, feature_value, dataset):\n",
    "        left, right = [], []\n",
    "        \n",
    "        #test each instance and split according to feature_value threshold\n",
    "        for row in dataset:\n",
    "            if row[feature_index] < feature_value:\n",
    "                left.append(row)\n",
    "            else:\n",
    "                right.append(row)\n",
    "        return left, right\n",
    "\n",
    "    # Calculate the Gini index for a split dataset\n",
    "    def gini_index(self, groups, class_values):\n",
    "        #measure of purity\n",
    "        #perfect class seperation: score of 0\n",
    "        #worst case; 50/50 mixed classes in each group: score of 1.0\n",
    "        \n",
    "        gini = 0.0\n",
    "        \n",
    "        #for each unique class...\n",
    "        for class_value in class_values:\n",
    "            #for each split group...\n",
    "            for group in groups:\n",
    "                #check if empty\n",
    "                size = len(group)\n",
    "                if size == 0:\n",
    "                    continue\n",
    "                \n",
    "                #if not empty, calculate class proportion\n",
    "                proportion = [row[-1] for row in group].count(class_value) / float(size)\n",
    "                \n",
    "                #update gini index score\n",
    "                gini += (proportion * (1.0 - proportion))\n",
    "        return gini\n",
    "    \n",
    "    def best_split(self, dataset):\n",
    "        #create list of unique classes\n",
    "        class_values = list(set(row[-1] for row in dataset))\n",
    "        \n",
    "        #initialize best records\n",
    "        b_index, b_value, b_score, b_groups = 999, 999, 999, None\n",
    "        \n",
    "        #randomly select n_features\n",
    "        features = []\n",
    "        \n",
    "        while len(features) < self.n_features:\n",
    "            index = random.randrange(len(dataset[0])-1)\n",
    "            if index not in features:\n",
    "                features.append(index)\n",
    "        \n",
    "        #for each feature...\n",
    "        for feature_index in features:\n",
    "            #test each instance's feature value as a threshold...\n",
    "            for row in dataset:\n",
    "                #split into groups\n",
    "                groups = self.threshold_split(feature_index, row[feature_index], dataset) #we try every feature value (row[feature_index])\n",
    "                #calculate gini index score for this split\n",
    "                gini = self.gini_index(groups, class_values)\n",
    "                #if gini index score is better (i.e. less) than the best score so far...\n",
    "                if gini < b_score:\n",
    "                    b_index, b_value, b_score, b_groups = feature_index, row[feature_index], gini, groups #update best records\n",
    "        \n",
    "        return {'index':b_index, 'value':b_value, 'groups':b_groups}\n",
    "\n",
    "    # Create a terminal node value\n",
    "    def to_terminal(self, group):\n",
    "        #selects the most common class value in the group to make predictions\n",
    "        outcomes = [row[-1] for row in group] #actual class array\n",
    "        return max(set(outcomes), key=outcomes.count) #return most common class\n",
    "\n",
    "    # Create child splits for a node or make terminal\n",
    "    def grow_tree(self, node, depth):\n",
    "        #recursive procedure -- calls upon itself until threshold condition met\n",
    "        \n",
    "        #retrieve left/right groups\n",
    "        left, right = node['groups']\n",
    "        \n",
    "        #delete node from memory\n",
    "        del(node['groups'])\n",
    "        \n",
    "        # check for a no split\n",
    "        if not left or not right:\n",
    "            node['left'] = node['right'] = self.to_terminal(left + right)\n",
    "            return\n",
    "        \n",
    "        # check for max depth\n",
    "        if depth >= self.max_depth:\n",
    "            node['left'], node['right'] = self.to_terminal(left), self.to_terminal(right)\n",
    "            return\n",
    "        \n",
    "        # process left child\n",
    "        if len(left) <= self.min_size: #check min_size\n",
    "            node['left'] = self.to_terminal(left)\n",
    "        else:\n",
    "            node['left'] = self.best_split(left) #calculate best split\n",
    "            self.grow_tree(node['left'], depth+1) #repeat until threshold condition met\n",
    "        \n",
    "        # process right child\n",
    "        if len(right) <= self.min_size: #check min_size\n",
    "            node['right'] = self.to_terminal(right)\n",
    "        else:\n",
    "            node['right'] = self.best_split(right) #calculate best split\n",
    "            self.grow_tree(node['right'], depth+1) #repeat until threshold condition met\n",
    "\n",
    "    # Build a decision tree\n",
    "    def build_tree(self, train):\n",
    "        root = self.best_split(train)\n",
    "        self.grow_tree(root, 1)\n",
    "        return root\n",
    "    \n",
    "    #trace tree for class\n",
    "    def trace_tree(self, node, row):\n",
    "        if row[node['index']] < node['value']:\n",
    "            if isinstance(node['left'], dict):\n",
    "                return self.trace_tree(node['left'], row)\n",
    "            else:\n",
    "                return node['left']\n",
    "        else:\n",
    "            if isinstance(node['right'], dict):\n",
    "                return self.trace_tree(node['right'], row)\n",
    "            else:\n",
    "                return node['right']\n",
    "    \n",
    "    # Create a random subsample from the dataset with replacement\n",
    "    def subsample(self, dataset, ratio):\n",
    "        sample = []\n",
    "        n_sample = round(len(dataset) * ratio)\n",
    "        while len(sample) < n_sample:\n",
    "            index = random.randrange(len(dataset))\n",
    "            sample.append(dataset[index])\n",
    "        return sample\n",
    "    \n",
    "    #fit model\n",
    "    def fit(self, X_train, y_train):\n",
    "        trainSet = np.asarray(pd.concat([X_train,y_train],axis=1))\n",
    "        \n",
    "        self.trainSet = trainSet\n",
    "        self.n_features = int(np.sqrt(len(trainSet[0])-1))\n",
    "        \n",
    "        trees = []\n",
    "        \n",
    "        #for each tree...\n",
    "        for i in range(self.n_trees):\n",
    "            sample = self.subsample(trainSet, self.sample_size) #sample training data\n",
    "            tree = self.build_tree(sample) #build tree\n",
    "            trees.append(tree)\n",
    "        \n",
    "        self.forest = trees\n",
    "        \n",
    "        return(trees)\n",
    "        \n",
    "    #individual prediction\n",
    "    def tree_predict(self,node):\n",
    "        \n",
    "        predictions = []\n",
    "        \n",
    "        for row in self.testSet:\n",
    "            prediction = self.trace_tree(node, row)\n",
    "            predictions.append(prediction)\n",
    "        \n",
    "        return(predictions)\n",
    "        \n",
    "    # Make an overall prediction with an ensemble of bagged trees\n",
    "    def predict(self, X_test):\n",
    "        self.testSet = np.asarray(X_test)\n",
    "        \n",
    "        forest = self.forest\n",
    "        \n",
    "        tree_votes = []\n",
    "        \n",
    "        #retrieve each tree's prediction\n",
    "        for tree in forest:\n",
    "            tree_votes.append(self.tree_predict(tree))\n",
    "        \n",
    "        #return most commonly predicted class\n",
    "        votes = pd.DataFrame(tree_votes).T\n",
    "        predictions = votes.mode(axis=1)[0]\n",
    "        \n",
    "        return predictions\n",
    "    \n",
    "    #evaluate predictions\n",
    "    def score(self, predictions, y_test):\n",
    "        actual = y_test.reset_index(drop=True)\n",
    "        correct = sum(predictions == actual) \n",
    "        accuracy = correct / len(actual)\n",
    "        return accuracy\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.96571428571428575"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rf = RandomForest()\n",
    "forest = rf.fit(X_train, y_train)\n",
    "predictions = rf.predict(X_test)\n",
    "rf.score(predictions,y_test)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}