Classification Trees.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from scipy.stats import mode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prob 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def giniImpurity(y,classes):\n",
    "    fk = np.array([(y == k).sum()/(1.*len(y)) for k in classes])\n",
    "    return 1 - sum(fk**2.)\n",
    "#classes = [0,1]\n",
    "#giniImpurity(trainSurvive,classes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prob 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def split(D,y,p,x):\n",
    "    if type(x) == float or type(x) == np.float64:\n",
    "        D1 = D[D.ix[:,p] <= x]\n",
    "        y1 = y[D.ix[:,p] <= x]\n",
    "        D2 = D[D.ix[:,p] > x]\n",
    "        y2 = y[D.ix[:,p] > x]\n",
    "    else:\n",
    "        D1 = D[D.ix[:,p] == x]\n",
    "        y1 = y[D.ix[:,p] == x]\n",
    "        D2 = D[D.ix[:,p] != x]\n",
    "        y2 = y[D.ix[:,p] != x]\n",
    "    return D1,y1,D2,y2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prob 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  9.92344045e-05])"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def infoGain(D,y,D1,y1,D2,y2,classes):\n",
    "    return (giniImpurity(y,classes) - len(y1)/(1.*len(D))*giniImpurity(y1,classes)\n",
    "                             - len(y2)/(1.*len(D))*giniImpurity(y2,classes))\n",
    "infoGain(train,trainSurvive,D1,y1,D2,y2,classes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prob 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def optimalSplit(D,y,classes):\n",
    "    best_x = None\n",
    "    best_p = None\n",
    "    max_I = -np.infty\n",
    "    for p in xrange(len(D.columns)):\n",
    "        vals = np.unique(D.ix[:,p])\n",
    "\n",
    "        for x in vals:\n",
    "            D1,y1,D2,y2 = split(D,y,p,x)\n",
    "            I = infoGain(D,y,D1,y1,D2,y2,classes)\n",
    "            if I > max_I:\n",
    "                best_x = x\n",
    "                best_p = p\n",
    "                max_I = I\n",
    "    return best_p,best_x\n",
    "#p,x = optimalSplit(train,trainSurvive,classes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prob 5 - 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,D,y,classes,max_dep,tol,cur_dep=1):\n",
    "        self.D = None\n",
    "        \n",
    "        self.tol = tol\n",
    "        self.cur_dep = cur_dep\n",
    "        self.max_dep = max_dep\n",
    "        \n",
    "        self.G = giniImpurity(y,classes)\n",
    "        \n",
    "        if self.G < self.tol or self.cur_dep == self.max_dep:\n",
    "            self.label = mode(y).mode[0][0]\n",
    "            self.leftChild = None\n",
    "            self.rightChild = None\n",
    "            self.p = None\n",
    "            self.x = None\n",
    "            \n",
    "        else:\n",
    "            self.label = None\n",
    "            \n",
    "            p,x = optimalSplit(D,y,classes)\n",
    "            if p == None:\n",
    "                self.label = mode(y).mode[0][0]\n",
    "                self.leftChild = None\n",
    "                self.rightChild = None\n",
    "                self.p = None\n",
    "                self.x = None\n",
    "            else:\n",
    "                D1,y1,D2,y2 = split(D,y,p,x)\n",
    "                self.leftChild = Node(D1,y1,classes,max_dep,tol,cur_dep+1)\n",
    "                self.rightChild = Node(D2,y2,classes,max_dep,tol,cur_dep+1)\n",
    "                self.p = p\n",
    "                self.x = x\n",
    "    def printTree(self):\n",
    "        if self.p != None:\n",
    "            print \" \"*(self.cur_dep-1),self.p,self.x\n",
    "            self.leftChild.printTree()\n",
    "            self.rightChild.printTree()\n",
    "        else:\n",
    "            print \" \"*(self.cur_dep-1),self.label\n",
    "    def classify(self,d):\n",
    "        if self.label != None:\n",
    "            return self.label\n",
    "        else:\n",
    "            if type(self.x) == float or type(self.x) == np.float64:\n",
    "                if d[self.p] <= self.x:\n",
    "                    return self.leftChild.classify(d)\n",
    "                else:\n",
    "                    return self.rightChild.classify(d)\n",
    "            else:\n",
    "                if d[self.p] == self.x:\n",
    "                    return self.leftChild.classify(d)\n",
    "                else:\n",
    "                    return self.rightChild.classify(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prob 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "allData = pd.read_csv(\"titanic4real.csv\")\n",
    "train = allData[:int(len(allData)*.8)]\n",
    "test = allData[int(len(allData)*.8):]\n",
    "\n",
    "train = train.fillna(0)\n",
    "trainSurvive = train[[\"Survived\"]]\n",
    "train = train[[\"Pclass\",\"Sex\",\"Age\"]]\n",
    "train = train.replace({'male': 1, 'female': 0})\n",
    "\n",
    "test = test.fillna(0)\n",
    "testSurvive = test[[\"Survived\"]]\n",
    "test = test[[\"Pclass\",\"Sex\",\"Age\"]]\n",
    "test = test.replace({'male': 1, 'female': 0})\n",
    "\n",
    "classes = [0,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tree = Node(train,trainSurvive,classes,10,.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 1 0\n",
      "  0 2.0\n",
      "   0 1.0\n",
      "    1.0\n",
      "    2 55.0\n",
      "     2 0.0\n",
      "      1.0\n",
      "      2 17.0\n",
      "       1.0\n",
      "       2 18.0\n",
      "        1.0\n",
      "        2 44.0\n",
      "         2 42.0\n",
      "          1.0\n",
      "          0.0\n",
      "         1.0\n",
      "     0.0\n",
      "   2 5.0\n",
      "    2 2.0\n",
      "     2 0.0\n",
      "      1.0\n",
      "      2 0.75\n",
      "       1.0\n",
      "       2 1.0\n",
      "        0.0\n",
      "        0.0\n",
      "     1.0\n",
      "    2 11.0\n",
      "     0.0\n",
      "     2 16.0\n",
      "      2 15.0\n",
      "       1.0\n",
      "       1.0\n",
      "      2 36.0\n",
      "       2 21.0\n",
      "        2 19.0\n",
      "         2 18.5\n",
      "          0.0\n",
      "          1.0\n",
      "         0.0\n",
      "        2 24.0\n",
      "         2 22.0\n",
      "          1.0\n",
      "          1.0\n",
      "         2 32.0\n",
      "          0.0\n",
      "          1.0\n",
      "       2 43.0\n",
      "        2 38.0\n",
      "         2 37.0\n",
      "          0.0\n",
      "          0.0\n",
      "         0.0\n",
      "        2 45.0\n",
      "         0.0\n",
      "         0.0\n",
      "  0 1.0\n",
      "   2 54.0\n",
      "    2 47.0\n",
      "     2 45.0\n",
      "      2 0.0\n",
      "       0.0\n",
      "       2 13.0\n",
      "        1.0\n",
      "        2 36.0\n",
      "         2 33.0\n",
      "          0.0\n",
      "          1.0\n",
      "         2 42.0\n",
      "          0.0\n",
      "          0.0\n",
      "      0.0\n",
      "     2 49.0\n",
      "      2 48.0\n",
      "       1.0\n",
      "       1.0\n",
      "      2 50.0\n",
      "       0.0\n",
      "       2 53.0\n",
      "        2 52.0\n",
      "         2 51.0\n",
      "          0.0\n",
      "          0.0\n",
      "         1.0\n",
      "        0.0\n",
      "    2 71.0\n",
      "     2 60.0\n",
      "      2 58.0\n",
      "       2 55.0\n",
      "        0.0\n",
      "        2 56.0\n",
      "         0.0\n",
      "         0.0\n",
      "       0.0\n",
      "      0.0\n",
      "     1.0\n",
      "   2 9.0\n",
      "    2 0.3333\n",
      "     2 0.0\n",
      "      0 2.0\n",
      "       0.0\n",
      "       0.0\n",
      "      0.0\n",
      "     0 2.0\n",
      "      1.0\n",
      "      2 3.0\n",
      "       2 1.0\n",
      "        2 0.8333\n",
      "         1.0\n",
      "         0.0\n",
      "        1.0\n",
      "       2 5.0\n",
      "        2 4.0\n",
      "         0.0\n",
      "         0.0\n",
      "        2 6.0\n",
      "         0.0\n",
      "         0.0\n",
      "    2 32.0\n",
      "     2 31.0\n",
      "      2 18.5\n",
      "       0.0\n",
      "       0 2.0\n",
      "        2 20.0\n",
      "         2 19.0\n",
      "          0.0\n",
      "          1.0\n",
      "         2 28.0\n",
      "          0.0\n",
      "          0.0\n",
      "        2 30.0\n",
      "         2 21.0\n",
      "          0.0\n",
      "          0.0\n",
      "         0.0\n",
      "      0 2.0\n",
      "       0.0\n",
      "       0.0\n",
      "     0.0\n"
     ]
    }
   ],
   "source": [
    "tree.printTree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "labs = test.apply(tree.classify,axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.782442748092\n"
     ]
    }
   ],
   "source": [
    "labs.to_frame()\n",
    "lv = labs.values\n",
    "tv = testSurvive.values.reshape(lv.shape[0])\n",
    "print (tv == lv).sum()/(1.*len(tv))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python2",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}