tree oct 13th.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>fixed acidity</th>\n",
       "      <th>volatile acidity</th>\n",
       "      <th>citric acid</th>\n",
       "      <th>residual sugar</th>\n",
       "      <th>chlorides</th>\n",
       "      <th>free sulfur dioxide</th>\n",
       "      <th>total sulfur dioxide</th>\n",
       "      <th>density</th>\n",
       "      <th>pH</th>\n",
       "      <th>sulphates</th>\n",
       "      <th>alcohol</th>\n",
       "      <th>quality</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>7.4</td>\n",
       "      <td>0.70</td>\n",
       "      <td>0.00</td>\n",
       "      <td>1.9</td>\n",
       "      <td>0.076</td>\n",
       "      <td>11.0</td>\n",
       "      <td>34.0</td>\n",
       "      <td>0.9978</td>\n",
       "      <td>3.51</td>\n",
       "      <td>0.56</td>\n",
       "      <td>9.4</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>7.8</td>\n",
       "      <td>0.88</td>\n",
       "      <td>0.00</td>\n",
       "      <td>2.6</td>\n",
       "      <td>0.098</td>\n",
       "      <td>25.0</td>\n",
       "      <td>67.0</td>\n",
       "      <td>0.9968</td>\n",
       "      <td>3.20</td>\n",
       "      <td>0.68</td>\n",
       "      <td>9.8</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>7.8</td>\n",
       "      <td>0.76</td>\n",
       "      <td>0.04</td>\n",
       "      <td>2.3</td>\n",
       "      <td>0.092</td>\n",
       "      <td>15.0</td>\n",
       "      <td>54.0</td>\n",
       "      <td>0.9970</td>\n",
       "      <td>3.26</td>\n",
       "      <td>0.65</td>\n",
       "      <td>9.8</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>11.2</td>\n",
       "      <td>0.28</td>\n",
       "      <td>0.56</td>\n",
       "      <td>1.9</td>\n",
       "      <td>0.075</td>\n",
       "      <td>17.0</td>\n",
       "      <td>60.0</td>\n",
       "      <td>0.9980</td>\n",
       "      <td>3.16</td>\n",
       "      <td>0.58</td>\n",
       "      <td>9.8</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>7.4</td>\n",
       "      <td>0.70</td>\n",
       "      <td>0.00</td>\n",
       "      <td>1.9</td>\n",
       "      <td>0.076</td>\n",
       "      <td>11.0</td>\n",
       "      <td>34.0</td>\n",
       "      <td>0.9978</td>\n",
       "      <td>3.51</td>\n",
       "      <td>0.56</td>\n",
       "      <td>9.4</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   fixed acidity  volatile acidity  citric acid  residual sugar  chlorides  \\\n",
       "0            7.4              0.70         0.00             1.9      0.076   \n",
       "1            7.8              0.88         0.00             2.6      0.098   \n",
       "2            7.8              0.76         0.04             2.3      0.092   \n",
       "3           11.2              0.28         0.56             1.9      0.075   \n",
       "4            7.4              0.70         0.00             1.9      0.076   \n",
       "\n",
       "   free sulfur dioxide  total sulfur dioxide  density    pH  sulphates  \\\n",
       "0                 11.0                  34.0   0.9978  3.51       0.56   \n",
       "1                 25.0                  67.0   0.9968  3.20       0.68   \n",
       "2                 15.0                  54.0   0.9970  3.26       0.65   \n",
       "3                 17.0                  60.0   0.9980  3.16       0.58   \n",
       "4                 11.0                  34.0   0.9978  3.51       0.56   \n",
       "\n",
       "   alcohol  quality  \n",
       "0      9.4        5  \n",
       "1      9.8        5  \n",
       "2      9.8        5  \n",
       "3      9.8        6  \n",
       "4      9.4        5  "
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd # to read the csv\n",
    "import random # generate random numbers for train test split\n",
    "import math # to calculate log2 probabilities\n",
    "df = pd.read_csv(\"winequality-red.csv\", sep=';')\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# train test split function\n",
    "def split_train_test(df, train=0.60):\n",
    "    train_size = round(len(df) * train)\n",
    "    train_indices = random.sample(population=df.index.tolist(), k=train_size)\n",
    "    train_df = df.loc[train_indices]\n",
    "    test_df = df.loc[set(df.index) - set(train_df.index)] #get rest of index\n",
    "    return train_df, test_df\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9600\n",
      "9588\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# example\n",
    "train_df, test_df = split_train_test(df=df, train=0.5)\n",
    "print(train_df.size)\n",
    "print(test_df.size)\n",
    "print(df.size == test_df.size + train_df.size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#for continuous target\n",
    "# Split criteria based on reduction of variance (so maximising SSR)\n",
    "###attention group 1 is <= split !!!\n",
    "def variance_SSR(df, feature, split, target):\n",
    "    mean_target_group1 = df[df[feature]<=split][target].mean()\n",
    "    len_group1 = sum(df[feature]<=split)\n",
    "    mean_target_group2 = df[df[feature]>split][target].mean()\n",
    "    len_group2 = len(df.index) - len_group1\n",
    "    mean = df[target].mean()\n",
    "    variance_SSR = len_group1 * (mean_target_group1 - mean)**2 + len_group2 * (mean_target_group2 - mean)**2\n",
    "    return variance_SSR\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10.823548170824402"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# example\n",
    "variance_SSR(df, 'fixed acidity', 5.5, 'quality')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Alternate function, find max of SSR for all possible splits for a specific variable\n",
    "\n",
    "def variance_SSR_max(df, feature, target):\n",
    "    splits = df[feature].unique() # all possible splits are all unique values, except the first value\n",
    "    max_SSR = 0\n",
    "    mean = df[target].mean()\n",
    "    for split in splits[1:]: # We have to exclude the first value as split is <=\n",
    "        mean_target_group1 = df[df[feature]<=split][target].mean()\n",
    "        mean_target_group2 = df[df[feature]>split][target].mean()\n",
    "        len_group1 = sum(df[feature]<=split)\n",
    "        len_group2 = len(df.index) - len_group1\n",
    "        variance_SSR = len_group1 * (mean_target_group1 - mean)**2 + len_group2 * (mean_target_group2 - mean)**2\n",
    "        if variance_SSR > max_SSR:\n",
    "            best_split = split\n",
    "            max_SSR=variance_SSR\n",
    "    return best_split\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9.9000000000000004"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "variance_SSR_max(df,'fixed acidity', 'quality')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Alternate function to find the best split out of all possible splits (so for all variables):\n",
    "\n",
    "def variance_SSR_max(df, target):\n",
    "    max_SSR = 0\n",
    "    for column in df: \n",
    "        if column =='quality': # We can't splt on the target variable\n",
    "            continue\n",
    "        splits = df[column].unique() # Possible splits are all the unique values, except the last value (because of <=)\n",
    "        mean = df[column].mean()\n",
    "        for split in splits[:-1]: # We have to exclude the last value as split\n",
    "            mean_target_group1 = df[df[column]<=split][target].mean()\n",
    "            mean_target_group2 = df[df[column]>split][target].mean()\n",
    "            len_group1 = sum(df[column]<=split)\n",
    "            len_group2 = len(df.index) - len_group1\n",
    "            variance_SSR = len_group1 * (mean_target_group1 - mean)**2 + len_group2 * (mean_target_group2 - mean)**2\n",
    "            if variance_SSR > max_SSR:\n",
    "                best_split = split\n",
    "                max_SSR = variance_SSR\n",
    "                best_column = column\n",
    "    return best_split,best_column\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(59.0, 'total sulfur dioxide')"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "variance_SSR_max(df, 'quality')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What about if the target is not continuous?\n",
    "# We will use another data set, and calculate Gini or entropy instead. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>sepal_length</th>\n",
       "      <th>sepal_width</th>\n",
       "      <th>petal_length</th>\n",
       "      <th>petal_width</th>\n",
       "      <th>species</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>5.1</td>\n",
       "      <td>3.5</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>setosa</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>4.9</td>\n",
       "      <td>3.0</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>setosa</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>4.7</td>\n",
       "      <td>3.2</td>\n",
       "      <td>1.3</td>\n",
       "      <td>0.2</td>\n",
       "      <td>setosa</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4.6</td>\n",
       "      <td>3.1</td>\n",
       "      <td>1.5</td>\n",
       "      <td>0.2</td>\n",
       "      <td>setosa</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5.0</td>\n",
       "      <td>3.6</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>setosa</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   sepal_length  sepal_width  petal_length  petal_width species\n",
       "0           5.1          3.5           1.4          0.2  setosa\n",
       "1           4.9          3.0           1.4          0.2  setosa\n",
       "2           4.7          3.2           1.3          0.2  setosa\n",
       "3           4.6          3.1           1.5          0.2  setosa\n",
       "4           5.0          3.6           1.4          0.2  setosa"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iris = pd.read_csv('iris_data.csv', sep=',')\n",
    "iris.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# First step is to find the pk\n",
    "def pk(df, target):\n",
    "    categories = df[target].unique()\n",
    "    pk = []\n",
    "    i = 0\n",
    "    for category in categories:\n",
    "        pk.append(sum(df[target]==category) / len(df))\n",
    "        i = i +1\n",
    "    return categories, pk\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array(['setosa', 'versicolor', 'virginica'], dtype=object),\n",
       " [0.33333333333333331, 0.33333333333333331, 0.33333333333333331])"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pk(iris, 'species')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Gini function\n",
    "def gini(df, target):\n",
    "    categories = df[target].unique()\n",
    "    pk = []\n",
    "    i = 0\n",
    "    for category in categories:\n",
    "        pk.append(sum(df[target]==category) / len(df)) # Find proportion in each class\n",
    "        i = i +1\n",
    "    return 1-sum([p ** 2 for p in pk]) # Return gini\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Entropy function\n",
    "def entropy(df, target):\n",
    "    categories = df[target].unique()\n",
    "    pk = []\n",
    "    i = 0\n",
    "    for category in categories:\n",
    "        pk.append(sum(df[target]==category) / len(df)) # Find proportion in each class\n",
    "        i = i +1\n",
    "    return -1 * sum([p * math.log2(p) for p in pk]) # Return entropy\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5849625007211561"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy(iris, 'species')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.66666666666666674"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gini(iris, 'species')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Next we need to find all possible binary splits\n",
    "#### does not work with return, only works with yield, why?\n",
    "# Bacically the idea here is to generate the subsets (possible splits) in a smart way.\n",
    "# This is a recursive algo. Basically, you start with the first category. Call this left. \n",
    "# Next you take the second category and set it aside. Call this right. \n",
    "#The way to create a subset of size n when you have all the subsets of size (n-1) is to add the\n",
    "# new element to the left, then to the right, and then create a new subset with it on the left. \n",
    "#ex for n=3:\n",
    "# 1\n",
    "# 1 2\n",
    "# 13  2\n",
    "# 1   23\n",
    "# 3   12\n",
    "#for n=4:\n",
    "# same as n=3 plus:\n",
    "# 134  2\n",
    "# 13   24\n",
    "# 14   23\n",
    "# 1    234\n",
    "# 34   12\n",
    "# 3    124\n",
    "# 4    123\n",
    "def cat_split(categories):\n",
    "    if len(categories)==1:\n",
    "        yield [categories]\n",
    "    else:\n",
    "        first = categories[0]\n",
    "        for next_one in cat_split(categories[1:]): # need to exclude first category, as stored in 'first'\n",
    "            for i, subset in enumerate(next_one):\n",
    "                yield next_one[:i] + [[ first ] + subset] + next_one[i+1:]\n",
    "            yield [[first]] + next_one\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 [['setosa'], ['versicolor', 'virginica']]\n",
      "3 [['setosa', 'versicolor'], ['virginica']]\n",
      "4 [['setosa', 'virginica'], ['versicolor']]\n"
     ]
    }
   ],
   "source": [
    "#something = iris['species'][1:4].unique().tolist() #test if only one category\n",
    "something = iris['species'].unique().tolist()\n",
    "for n, p in enumerate(cat_split(something), 1):\n",
    "    if len(p)==2: # binary splits only\n",
    "        print(n, sorted(p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}