CH09 Tree Regression.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CH9 Tree Regression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## MLiA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class treeNode():\n",
    "    def __init__(self, feat, val, right, left):\n",
    "        featureToSplitOn = feat\n",
    "        valueOfSplit = val\n",
    "        rightBranch = right\n",
    "        leftBranch = left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def loadDataSet(fileName):\n",
    "    dataMat = []\n",
    "    fr = open(fileName)\n",
    "    for line in fr.readlines():\n",
    "        curLine = line.strip().split(\"\\t\")\n",
    "        dataMat.append(curLine)\n",
    "    return dataMat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def binSplitDataSet(dataSet, feature, value):\n",
    "    # \n",
    "    mat0 = dataSet[np.nonzero(dataSet[:,feature] >  value)[0],:]\n",
    "    mat1 = dataSet[np.nonzero(dataSet[:,feature] <= value)[0],:]\n",
    "    return mat0, mat1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def regLeaf(dataSet):\n",
    "    return np.mean(dataSet[:,-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 平方误差\n",
    "# 总方差\n",
    "def regErr(dataSet):\n",
    "    return np.var(dataSet[:,-1])*np.shape(dataSet)[0]                                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 二元切分\n",
    "def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):\n",
    "    tolS = ops[0]; tolN = ops[1]\n",
    "    #if all the target variables are the same value: quit and return value\n",
    "    if len(set(dataSet[:,-1].T.tolist())) == 1: #exit cond 1\n",
    "        return None, leafType(dataSet)\n",
    "    m,n = np.shape(dataSet)\n",
    "    #the choice of the best feature is driven by Reduction in RSS error from mean\n",
    "    S = errType(dataSet)\n",
    "    bestS = np.inf; bestIndex = 0; bestValue = 0\n",
    "    for featIndex in range(n-1):\n",
    "        for splitVal in set(dataSet[:,featIndex]):\n",
    "            mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)\n",
    "            if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN): continue\n",
    "            newS = errType(mat0) + errType(mat1)\n",
    "            if newS < bestS: \n",
    "                bestIndex = featIndex\n",
    "                bestValue = splitVal\n",
    "                bestS = newS\n",
    "    #if the decrease (S-bestS) is less than a threshold don't do the split\n",
    "    if (S - bestS) < tolS: \n",
    "        return None, leafType(dataSet) #exit cond 2\n",
    "    mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)\n",
    "    if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):  #exit cond 3\n",
    "        return None, leafType(dataSet)\n",
    "    return bestIndex,bestValue#returns the best feature to split on\n",
    "                              #and the value used for that split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):\n",
    "    feat, val = chooseBestSplit(dataSet, leafType, errType, ops)\n",
    "    if feat == None: return val\n",
    "    retTree = {}\n",
    "    retTree['spInd'] = feat\n",
    "    retTree['spVal'] = val\n",
    "    lSet, rSet = binSplitDataSet(dataSet, feat, val)\n",
    "    retTree['left'] = createTree(lSet, leafType, errType, ops)\n",
    "    retTree['right'] = createTree(rSet, leafType, errType, ops)\n",
    "    return retTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "testMat = np.mat(np.eye(4))\n",
    "mat0, mat1 = binSplitDataSet(testMat, 1, 0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1., 0., 0., 0.],\n",
       "        [0., 1., 0., 0.],\n",
       "        [0., 0., 1., 0.],\n",
       "        [0., 0., 0., 1.]])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "testMat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([0, 2, 3], dtype=int64), array([0, 0, 0], dtype=int64))"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.nonzero(testMat[:,1] < 0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0., 1., 0., 0.]])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mat0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1., 0., 0., 0.],\n",
       "        [0., 0., 1., 0.],\n",
       "        [0., 0., 0., 1.]])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mat1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Regression Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "myDat = loadDataSet(\"./Data/CH9/ex0.txt\")\n",
    "myMat = np.mat(myDat).astype(float)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'left': {'left': {'left': 3.9871632,\n",
       "   'right': 2.9836209534883724,\n",
       "   'spInd': 1,\n",
       "   'spVal': 0.797583},\n",
       "  'right': 1.980035071428571,\n",
       "  'spInd': 1,\n",
       "  'spVal': 0.582002},\n",
       " 'right': {'left': 1.0289583666666666,\n",
       "  'right': -0.023838155555555553,\n",
       "  'spInd': 1,\n",
       "  'spVal': 0.197834},\n",
       " 'spInd': 1,\n",
       " 'spVal': 0.39435}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "createTree(myMat.A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Model Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Sklearn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "275px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}