{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "dfa098892a1e9b014263ab5bb2797776",
     "grade": false,
     "grade_id": "cell-6045e53795157412",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# Decision Tree Warmup Activity\n",
    "\n",
    "Enter your name in the cell below:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "3eb19a8c6f0d865be43b97b7c854f024",
     "grade": true,
     "grade_id": "cell-f00d1de43b512a8e",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "8e5566c7beb050dac2a5a7d4227e5fd0",
     "grade": false,
     "grade_id": "cell-8ac3e47a43681d6e",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Gini Impurity\n",
    "\n",
    "We've discussed entropy as a possible measure of impurity for the decision tree construction algorithm.  Another option is *Gini impurity*.  Gini impurity is defined as:\n",
    "\n",
    "$$ \\phi(\\mathbf{p}) = \\sum_i p_i(1-p_i) $$\n",
    "\n",
    "\n",
    "Where $\\mathbf{p} = (p_1, ... , p_n)$ and each $p_i$ is the fraction\n",
    "of elements from class $i$.  This expresses the fractions of incorrect\n",
    "predictions in the node if the class of each element was predicted by\n",
    "randomly selecting a label according to the distribution of classes in\n",
    "the node.  This value will be 0 if all elements are from the same\n",
    "class, and it increases as the mix becomes more uniform.  Because we know that the $p_i$ must sum to one, this can be rewritten as:\n",
    "\n",
    "$$ \\phi(\\mathbf{p}) = 1 - \\sum_i p_i^2 $$\n",
    "\n",
    "\\* Notation follows: Breiman,\n",
    "  Leo. ``Technical note: Some properties of splitting criteria.''\n",
    "  Machine Learning 24.1 (1996): 41-47.\n",
    "  \n",
    "### Exercise 1\n",
    "What is the Gini impurity of a node containing 3 items from class A, 7 items from class B and 10 items from class C?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "d29dcbefdd1447abf2aef546b5c552d3",
     "grade": true,
     "grade_id": "cell-6decfef393c2babd",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "6fc9dc41830ccd054827b8ced83f701e",
     "grade": false,
     "grade_id": "cell-60918903c7db0e32",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Split Generator for the Decision Tree PA\n",
    "\n",
    "I'm providing one potentially useful utility method that you can use in your decision tree construction algorithm.  The `split_generator` method illustrated below will allow you to iterate over all possible splits for a data set. Make sure you understand what's hapenning in this code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import decision_tree\n",
    "\n",
    "# This is the same housing data we worked with in class. \n",
    "# The three columns are \"homeowner\", \"marital status\" and \"income\".  \n",
    "# The label array (y) represents \"defaulted borrower\".\n",
    "\n",
    "X = np.array([[1., 0., 120.],\n",
    "              [0., 1., 100.],\n",
    "              [1., 0., 70.],\n",
    "              [0., 0., 150.],\n",
    "              [1., 2., 85.],\n",
    "              [0., 1., 80.],\n",
    "              [0., 0., 75.]])\n",
    "\n",
    "y = np.array([0, 0, 0, 1, 0, 1, 1])\n",
    "\n",
    "# Instantiate a generator\n",
    "split_gen = decision_tree.split_generator(X, y)\n",
    "\n",
    "# Print the information associated with the first two splits:\n",
    "print(\"FIRST SPLIT:\")\n",
    "print(next(split_gen))\n",
    "print(\"\\nSECOND SPLIT:\")\n",
    "print(next(split_gen))\n",
    "\n",
    "# Now let's count to see if we get the expected number of splits:\n",
    "counter = 0\n",
    "for split in decision_tree.split_generator(X, y):\n",
    "    counter += 1\n",
    "\n",
    "print(\"\\nThere are {} possible splits.\".format(counter))\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "50feaa4e62b065642f5796f4874202a7",
     "grade": false,
     "grade_id": "cell-8d254dbb9df42174",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exercise 2 - Implement Gini Impurity\n",
    "\n",
    "Complete the two unfinished functions below.  These will be useful in your decision tree implementation.\n",
    "\n",
    "Note that `np.fromiter` can be used to convert any iterable into a numpy array:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1, 2, 3]\n",
    "array = np.fromiter(a, dtype=float)\n",
    "print(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also note that the `Counter` type from the Python `collections` library is specialized dictionary for freqency calcuations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "a = ['A', 'B', 'B', 'B', 'C', 'C']\n",
    "counts = Counter(a)\n",
    "print(counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a957b829ce3e2b22a2942fbfd7cdd0a6",
     "grade": false,
     "grade_id": "cell-897692e890b283d7",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def impurity(y, y_counts=None):\n",
    "    \"\"\" Calculate Gini impurity for the class labels y.\n",
    "        If y_counts is provided it will be the counts of the labels in y.\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "7cc8423344357f2ab1984e6a2918632e",
     "grade": true,
     "grade_id": "impurity_tests",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# TESTS FOR IMPURITY\n",
    "\n",
    "np.testing.assert_allclose(impurity(y), 0.48979, atol=.001)\n",
    "\n",
    "split_gen = decision_tree.split_generator(X, y)\n",
    "\n",
    "split = next(split_gen)\n",
    "np.testing.assert_allclose(impurity(split.y_left, split.counts_left), 0.375, atol=.001)\n",
    "np.testing.assert_allclose(impurity(split.y_right, split.counts_right), 0, atol=.001)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8e8d0367553c0a080f6154b1974ab64f",
     "grade": false,
     "grade_id": "cell-72126e0caef47ce9",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def weighted_impurity(split):\n",
    "    \"\"\" Weighted gini impurity for a possible split. \"\"\" \n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "33a301229433af56191643f7b4a2bde9",
     "grade": true,
     "grade_id": "weighted_impurity_tests",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# TESTS FOR WEIGHTED IMPURITY\n",
    "\n",
    "split_gen = decision_tree.split_generator(X, y)\n",
    "\n",
    "split = next(split_gen)\n",
    "np.testing.assert_allclose(weighted_impurity(split), 0.214286, atol=.001)\n",
    "split = next(split_gen)\n",
    "np.testing.assert_allclose(weighted_impurity(split), 0.47619, atol=.001)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.12.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}