ml/hw4.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Hgs8vIo5pS9m"
      },
      "source": [
        "Before you submit this notebook, make sure everything runs as expected in the local test cases. \n",
        "Please, paste the solution to the designed cell and do not change anything else.\n",
        "\n",
        "Also, please, leave your first and last names below"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "d1WHI6m2pS9q"
      },
      "outputs": [],
      "source": [
        "FirstName = \"\"\n",
        "LastName = \"\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "05nVOgU2pS9r"
      },
      "source": [
        "---"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "jhiJxePGpS9r"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "from sklearn.base import BaseEstimator\n",
        "from sklearn.preprocessing import OneHotEncoder"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "deletable": false,
        "nbgrader": {
          "cell_type": "code",
          "checksum": "40b231b30fc9f58984904a569710f504",
          "grade": false,
          "grade_id": "cell-ac8fc52d8a39ccb4",
          "locked": false,
          "schema_version": 3,
          "solution": true,
          "task": false
        },
        "id": "8oE38mAdpS9t"
      },
      "outputs": [],
      "source": [
        "def entropy(y):  \n",
        "    \"\"\"\n",
        "    Computes entropy of the provided distribution. Use log(value + eps) for numerical stability\n",
        "    \n",
        "    Parameters\n",
        "    ----------\n",
        "    y : np.array of type float with shape (n_objects, n_classes)\n",
        "        One-hot representation of class labels for corresponding subset\n",
        "    \n",
        "    Returns\n",
        "    -------\n",
        "    float\n",
        "        Entropy of the provided subset\n",
        "    \"\"\"\n",
        "    EPS = 0.0005\n",
        "    p = np.mean(y, axis=0)\n",
        "    H = -np.sum(p * np.log(p + EPS))\n",
        "    return H\n",
        "    \n",
        "def gini(y):\n",
        "    \"\"\"\n",
        "    Computes the Gini impurity of the provided distribution\n",
        "    \n",
        "    Parameters\n",
        "    ----------\n",
        "    y : np.array of type float with shape (n_objects, n_classes)\n",
        "        One-hot representation of class labels for corresponding subset\n",
        "    \n",
        "    Returns\n",
        "    -------\n",
        "    float\n",
        "        Gini impurity of the provided subset\n",
        "    \"\"\"\n",
        "    return 1 - np.sum(np.mean(y, axis=0) ** 2)\n",
        "    \n",
        "def variance(y):\n",
        "    \"\"\"\n",
        "    Computes the variance the provided target values subset\n",
        "    \n",
        "    Parameters\n",
        "    ----------\n",
        "    y : np.array of type float with shape (n_objects, 1)\n",
        "        Target values vector\n",
        "    \n",
        "    Returns\n",
        "    -------\n",
        "    float\n",
        "        Variance of the provided target vector\n",
        "    \"\"\"\n",
        "    return np.var(y)\n",
        "\n",
        "def mad_median(y):\n",
        "    \"\"\"\n",
        "    Computes the mean absolute deviation from the median in the\n",
        "    provided target values subset\n",
        "    \n",
        "    Parameters\n",
        "    ----------\n",
        "    y : np.array of type float with shape (n_objects, 1)\n",
        "        Target values vector\n",
        "    \n",
        "    Returns\n",
        "    -------\n",
        "    float\n",
        "        Mean absolute deviation from the median in the provided vector\n",
        "    \"\"\"\n",
        "    return np.mean(np.abs(y - np.median(y)))\n",
        "\n",
        "\n",
        "def one_hot_encode(n_classes, y):\n",
        "    y_one_hot = np.zeros((len(y), n_classes), dtype=float)\n",
        "    y_one_hot[np.arange(len(y)), y.astype(int)[:, 0]] = 1.\n",
        "    return y_one_hot\n",
        "\n",
        "\n",
        "def one_hot_decode(y_one_hot):\n",
        "    return y_one_hot.argmax(axis=1)[:, None]\n",
        "\n",
        "\n",
        "class Node:\n",
        "    \"\"\"\n",
        "    This class is provided \"as is\" and it is not mandatory to it use in your code.\n",
        "    \"\"\"\n",
        "    def __init__(self, feature_index, threshold, proba=0):\n",
        "        self.feature_index = feature_index\n",
        "        self.value = threshold\n",
        "        self.proba = proba\n",
        "        self.left_child = None\n",
        "        self.right_child = None\n",
        "        \n",
        "        \n",
        "class DecisionTree(BaseEstimator):\n",
        "    all_criterions = {\n",
        "        'gini': (gini, True), # (criterion, classification flag)\n",
        "        'entropy': (entropy, True),\n",
        "        'variance': (variance, False),\n",
        "        'mad_median': (mad_median, False)\n",
        "    }\n",
        "\n",
        "    def __init__(self, n_classes=None, max_depth=np.inf, min_samples_split=2, \n",
        "                 criterion_name='gini', debug=False):\n",
        "\n",
        "        assert criterion_name in self.all_criterions.keys(), 'Criterion name must be on of the following: {}'.format(self.all_criterions.keys())\n",
        "        \n",
        "        self.n_classes = n_classes\n",
        "        self.max_depth = max_depth\n",
        "        self.min_samples_split = min_samples_split\n",
        "        self.criterion_name = criterion_name\n",
        "\n",
        "        self.depth = 0\n",
        "        self.root = None # Use the Node class to initialize it later\n",
        "        self.debug = debug\n",
        "\n",
        "        \n",
        "        \n",
        "    def make_split(self, feature_index, threshold, X_subset, y_subset):\n",
        "        \"\"\"\n",
        "        Makes split of the provided data subset and target values using provided feature and threshold\n",
        "        \n",
        "        Parameters\n",
        "        ----------\n",
        "        feature_index : int\n",
        "            Index of feature to make split with\n",
        "\n",
        "        threshold : float\n",
        "            Threshold value to perform split\n",
        "\n",
        "        X_subset : np.array of type float with shape (n_objects, n_features)\n",
        "            Feature matrix representing the selected subset\n",
        "\n",
        "        y_subset : np.array of type float with shape (n_objects, n_classes) in classification \n",
        "                   (n_objects, 1) in regression \n",
        "            One-hot representation of class labels for corresponding subset\n",
        "        \n",
        "        Returns\n",
        "        -------\n",
        "        (X_left, y_left) : tuple of np.arrays of same type as input X_subset and y_subset\n",
        "            Part of the providev subset where selected feature x^j < threshold\n",
        "        (X_right, y_right) : tuple of np.arrays of same type as input X_subset and y_subset\n",
        "            Part of the providev subset where selected feature x^j >= threshold\n",
        "        \"\"\"\n",
        "\n",
        "        left, right = [], []\n",
        "        n = X_subset.shape[0]\n",
        "        for i in range(n):\n",
        "          if X_subset[i][feature_index] < threshold:\n",
        "            left.append(i)\n",
        "          else:\n",
        "            right.append(i)\n",
        "\n",
        "        X_left, y_left = X_subset[left], y_subset[left]\n",
        "        X_right, y_right = X_subset[right], y_subset[right]\n",
        "        \n",
        "        return (X_left, y_left), (X_right, y_right)\n",
        "    \n",
        "    def make_split_only_y(self, feature_index, threshold, X_subset, y_subset):\n",
        "        \"\"\"\n",
        "        Split only target values into two subsets with specified feature and threshold\n",
        "        \n",
        "        Parameters\n",
        "        ----------\n",
        "        feature_index : int\n",
        "            Index of feature to make split with\n",
        "\n",
        "        threshold : float\n",
        "            Threshold value to perform split\n",
        "\n",
        "        X_subset : np.array of type float with shape (n_objects, n_features)\n",
        "            Feature matrix representing the selected subset\n",
        "\n",
        "        y_subset : np.array of type float with shape (n_objects, n_classes) in classification \n",
        "                   (n_objects, 1) in regression \n",
        "            One-hot representation of class labels for corresponding subset\n",
        "        \n",
        "        Returns\n",
        "        -------\n",
        "        y_left : np.array of type float with shape (n_objects_left, n_classes) in classification \n",
        "                   (n_objects, 1) in regression \n",
        "            Part of the provided subset where selected feature x^j < threshold\n",
        "\n",
        "        y_right : np.array of type float with shape (n_objects_right, n_classes) in classification \n",
        "                   (n_objects, 1) in regression \n",
        "            Part of the provided subset where selected feature x^j >= threshold\n",
        "        \"\"\"\n",
        "\n",
        "        left, right = [], []\n",
        "        n = X_subset.shape[0]\n",
        "        for i in range(n):\n",
        "          if X_subset[i][feature_index] < threshold:\n",
        "            left.append(i)\n",
        "          else:\n",
        "            right.append(i)\n",
        "\n",
        "        y_left, y_right = y_subset[left], y_subset[right]\n",
        "\n",
        "        return y_left, y_right\n",
        "\n",
        "    def choose_best_split(self, X_subset, y_subset):\n",
        "        \"\"\"\n",
        "        Greedily select the best feature and best threshold w.r.t. selected criterion\n",
        "        \n",
        "        Parameters\n",
        "        ----------\n",
        "        X_subset : np.array of type float with shape (n_objects, n_features)\n",
        "            Feature matrix representing the selected subset\n",
        "\n",
        "        y_subset : np.array of type float with shape (n_objects, n_classes) in classification \n",
        "                   (n_objects, 1) in regression \n",
        "            One-hot representation of class labels or target values for corresponding subset\n",
        "        \n",
        "        Returns\n",
        "        -------\n",
        "        feature_index : int\n",
        "            Index of feature to make split with\n",
        "\n",
        "        threshold : float\n",
        "            Threshold value to perform split\n",
        "\n",
        "        \"\"\"\n",
        "        \n",
        "        feature_index, threshold = 0, 0\n",
        "        n, m = X_subset.shape\n",
        "        G = 0\n",
        "        for i in range(m):\n",
        "          thresholds_array = np.sort(np.unique(X_subset[:, i]))[1:-1]#np.sort(np.unique(np.random.choice(X_subset[:, i], n)))[1:-1]\n",
        "          for threshold_ in thresholds_array:\n",
        "            y_left, y_right = self.make_split_only_y(i, threshold_, X_subset, y_subset)\n",
        "            G_ = self.criterion(y_subset) - y_left.shape[0] / n * self.criterion(y_left) - y_right.shape[0] / n * self.criterion(y_right)\n",
        "            if G_ > G:\n",
        "              feature_index, threshold, G = i, threshold_, G_ \n",
        "\n",
        "        return feature_index, threshold\n",
        "    \n",
        "    def make_tree(self, X_subset, y_subset):\n",
        "        \"\"\"\n",
        "        Recursively builds the tree\n",
        "        \n",
        "        Parameters\n",
        "        ----------\n",
        "        X_subset : np.array of type float with shape (n_objects, n_features)\n",
        "            Feature matrix representing the selected subset\n",
        "\n",
        "        y_subset : np.array of type float with shape (n_objects, n_classes) in classification \n",
        "                   (n_objects, 1) in regression \n",
        "            One-hot representation of class labels or target values for corresponding subset\n",
        "        \n",
        "        Returns\n",
        "        -------\n",
        "        root_node : Node class instance\n",
        "            Node of the root of the fitted tree\n",
        "        \"\"\"\n",
        "        def value(y):\n",
        "          if 0 == len(y):\n",
        "            return 0\n",
        "          if self.criterion_name in ('gini', 'entropy'):\n",
        "            return np.argmax(np.sum(y, axis=0))\n",
        "          if 'variance' == self.criterion_name:\n",
        "            return np.mean(y)\n",
        "          return np.median(y)\n",
        "\n",
        "        def proba(y):\n",
        "          if 0 == len(y):\n",
        "            return 0\n",
        "          if self.criterion_name in ('gini', 'entropy'):\n",
        "            return np.mean(y, axis=0)\n",
        "          return np.mean(y)\n",
        "\n",
        "        self.depth += 1\n",
        "        min_leaves = X_subset.shape[0]\n",
        "        if self.depth < self.max_depth and min_leaves >= self.min_samples_split:\n",
        "          feature_index, threshold = self.choose_best_split(X_subset, y_subset)\n",
        "          new_node = Node(feature_index, threshold)\n",
        "          (X_left, y_left), (X_right, y_right) = self.make_split(feature_index, threshold, X_subset, y_subset)\n",
        "          new_node.left_child = self.make_tree(X_left, y_left)\n",
        "          new_node.right_child = self.make_tree(X_right, y_right)\n",
        "        else:\n",
        "          new_node = Node(0, 0)\n",
        "          new_node.value = value(y_subset)\n",
        "          new_node.proba = proba(y_subset)\n",
        "        self.depth -= 1\n",
        "\n",
        "        return new_node\n",
        "        \n",
        "    def fit(self, X, y):\n",
        "        \"\"\"\n",
        "        Fit the model from scratch using the provided data\n",
        "        \n",
        "        Parameters\n",
        "        ----------\n",
        "        X : np.array of type float with shape (n_objects, n_features)\n",
        "            Feature matrix representing the data to train on\n",
        "\n",
        "        y : np.array of type int with shape (n_objects, 1) in classification \n",
        "                   of type float with shape (n_objects, 1) in regression \n",
        "            Column vector of class labels in classification or target values in regression\n",
        "        \n",
        "        \"\"\"\n",
        "        assert len(y.shape) == 2 and len(y) == len(X), 'Wrong y shape'\n",
        "        self.criterion, self.classification = self.all_criterions[self.criterion_name]\n",
        "        if self.classification:\n",
        "            if self.n_classes is None:\n",
        "                self.n_classes = len(np.unique(y))\n",
        "            y = one_hot_encode(self.n_classes, y)\n",
        "\n",
        "        self.root = self.make_tree(X, y)\n",
        "\n",
        "    def _recursion_predict(self, X, indexes, node, pred, proba=False):\n",
        "          if not node.left_child:\n",
        "            for i in indexes:\n",
        "              pred[i] = node.proba if proba else node.value\n",
        "          else:\n",
        "            (X_left, y_left), (X_right, y_right) = self.make_split(node.feature_index, node.value, X, indexes)\n",
        "            self._recursion_predict(X_left, y_left, node.left_child, pred, proba)\n",
        "            self._recursion_predict(X_right, y_right, node.right_child, pred, proba)\n",
        "\n",
        "    def predict(self, X):\n",
        "        \"\"\"\n",
        "        Predict the target value or class label  the model from scratch using the provided data\n",
        "        \n",
        "        Parameters\n",
        "        ----------\n",
        "        X : np.array of type float with shape (n_objects, n_features)\n",
        "            Feature matrix representing the data the predictions should be provided for\n",
        "\n",
        "        Returns\n",
        "        -------\n",
        "        y_predicted : np.array of type int with shape (n_objects, 1) in classification \n",
        "                   (n_objects, 1) in regression \n",
        "            Column vector of class labels in classification or target values in regression\n",
        "        \n",
        "        \"\"\"\n",
        "\n",
        "        tree = self.root\n",
        "        prediction = dict()\n",
        "        y_predicted = np.zeros(X.shape[0])\n",
        "        indexes = np.arange(X.shape[0])\n",
        "        self._recursion_predict(X, indexes, tree, prediction)\n",
        "        for i, value in prediction.items():\n",
        "          y_predicted[i] = value\n",
        "        return y_predicted\n",
        "        \n",
        "    def predict_proba(self, X):\n",
        "        \"\"\"\n",
        "        Only for classification\n",
        "        Predict the class probabilities using the provided data\n",
        "        \n",
        "        Parameters\n",
        "        ----------\n",
        "        X : np.array of type float with shape (n_objects, n_features)\n",
        "            Feature matrix representing the data the predictions should be provided for\n",
        "\n",
        "        Returns\n",
        "        -------\n",
        "        y_predicted_probs : np.array of type float with shape (n_objects, n_classes)\n",
        "            Probabilities of each class for the provided objects\n",
        "        \n",
        "        \"\"\"\n",
        "        assert self.classification, 'Available only for classification problem'\n",
        "\n",
        "        tree = self.root\n",
        "        prediction = dict()\n",
        "        y_predicted_probs = np.zeros((X.shape[0], self.n_classes))\n",
        "        indexes = np.arange(X.shape[0])\n",
        "        self._recursion_predict(X, indexes, tree, prediction, True)\n",
        "        for i, proba in prediction.items():\n",
        "          y_predicted_probs[i] = proba\n",
        "                \n",
        "        return y_predicted_probs"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yR52rFgbpS9v"
      },
      "source": [
        "### Test 0: Initialization (0.01 points)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "deletable": false,
        "editable": false,
        "nbgrader": {
          "cell_type": "code",
          "checksum": "3dee5ee83e0f63188671f08b57d70804",
          "grade": true,
          "grade_id": "cell-3473b7b6ffd64d07",
          "locked": true,
          "points": 0.01,
          "schema_version": 3,
          "solution": false,
          "task": false
        },
        "id": "y7U05HqCpS9w"
      },
      "outputs": [],
      "source": [
        "# do not change this cell\n",
        "import numpy as np\n",
        "import unittest\n",
        "import sys\n",
        "import io\n",
        "\n",
        "from sklearn.datasets import fetch_california_housing, load_digits\n",
        "from sklearn.metrics import accuracy_score, mean_squared_error\n",
        "from sklearn.model_selection import train_test_split\n",
        "\n",
        "digits_data = load_digits(n_class=2).data\n",
        "digits_target = load_digits(n_class=2).target[:, None]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3salpr3vpS9x"
      },
      "source": [
        "### Test 1: Make splits loops (0.1 points)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "deletable": false,
        "editable": false,
        "nbgrader": {
          "cell_type": "code",
          "checksum": "48b2963c650791df41dfbd190ed247fd",
          "grade": true,
          "grade_id": "cell-e3503c286039ec55",
          "locked": true,
          "points": 0.09,
          "schema_version": 3,
          "solution": false,
          "task": false
        },
        "id": "eB9NcksppS9x"
      },
      "outputs": [],
      "source": [
        "X = np.ones((4, 5), dtype=float) * np.arange(4)[:, None]\n",
        "y = np.arange(4)[:, None] + np.asarray([0.2, -0.3, 0.1, 0.4])[:, None]\n",
        "class_estimator = DecisionTree(max_depth=5, criterion_name='gini')\n",
        "\n",
        "(X_l, y_l), (X_r, y_r) = class_estimator.make_split(1, 1., X, y)\n",
        "\n",
        "flag_X = np.array_equal(X[:1], X_l) and np.array_equal(X[1:], X_r) \n",
        "flag_y = np.array_equal(y[:1], y_l) and np.array_equal(y[1:], y_r)\n",
        "assert flag_X and flag_y"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ccIJkeeGpS9z"
      },
      "source": [
        "### Test 2: Gini accuracy (0.2 points)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "deletable": false,
        "editable": false,
        "nbgrader": {
          "cell_type": "code",
          "checksum": "4a2a5e274d8d866e1242a339a7751642",
          "grade": true,
          "grade_id": "cell-e2c4124a6f815118",
          "locked": true,
          "points": 0.2,
          "schema_version": 3,
          "solution": false,
          "task": false
        },
        "id": "QN8_7YEypS90"
      },
      "outputs": [],
      "source": [
        "class_estimator = DecisionTree(max_depth=5, criterion_name='gini')\n",
        "class_estimator.fit(X_train, y_train)\n",
        "ans = class_estimator.predict(X_test)\n",
        "accuracy_gini = accuracy_score(y_test, ans)\n",
        "assert 0.96 < accuracy_gini"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0_A75Nf4pS91"
      },
      "source": [
        "### Test 3: Entropy accuracy (0.2 points)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "deletable": false,
        "editable": false,
        "nbgrader": {
          "cell_type": "code",
          "checksum": "b3b167fd8a4950ffe1f1b8f691ab7f91",
          "grade": true,
          "grade_id": "cell-69473387a23d8dff",
          "locked": true,
          "points": 0.2,
          "schema_version": 3,
          "solution": false,
          "task": false
        },
        "id": "A1ESqK-GpS91"
      },
      "outputs": [],
      "source": [
        "class_estimator = DecisionTree(max_depth=5, criterion_name='entropy')\n",
        "class_estimator.fit(X_train, y_train)\n",
        "ans = class_estimator.predict(X_test)\n",
        "accuracy = accuracy_score(y_test, ans)\n",
        "assert 0.96 < accuracy"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TUyyjISBpS92"
      },
      "source": [
        "### Test 4: Entropy probabilities (0.2 points)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "deletable": false,
        "editable": false,
        "nbgrader": {
          "cell_type": "code",
          "checksum": "2ea5402e3fc351fe4bdc17dc7d48b591",
          "grade": true,
          "grade_id": "cell-e5f59af66e6c111b",
          "locked": true,
          "points": 0.2,
          "schema_version": 3,
          "solution": false,
          "task": false
        },
        "id": "p9alDBHjpS92"
      },
      "outputs": [],
      "source": [
        "class_estimator = DecisionTree(max_depth=10, criterion_name='entropy')\n",
        "class_estimator.fit(X_train, y_train)\n",
        "ans = class_estimator.predict(X_test)\n",
        "reference = np.array([0.48611111, 0.51388889])\n",
        "assert np.abs(np.sum(class_estimator.predict_proba(X_test).mean(axis=0) - reference)) < 1e-6"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1IJP6sugpS92"
      },
      "source": [
        "### Test 5: MSE mad_median (0.15 points)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "deletable": false,
        "editable": false,
        "nbgrader": {
          "cell_type": "code",
          "checksum": "740411f734d1c9841d5fcc124eb129d1",
          "grade": true,
          "grade_id": "cell-1a9c1e3609ed9aab",
          "locked": true,
          "points": 0.15,
          "schema_version": 3,
          "solution": false,
          "task": false
        },
        "id": "PRkLu_p8pS93"
      },
      "outputs": [],
      "source": [
        "housing = fetch_california_housing()\n",
        "random_indices = np.random.choice(np.arange(len(housing.data)), 500)\n",
        "\n",
        "regr_data = housing.data[random_indices]\n",
        "regr_target = housing.target[random_indices, None]\n",
        "RX_train, RX_test, Ry_train, Ry_test = train_test_split(regr_data, regr_target, test_size=0.2, random_state=42)\n",
        "\n",
        "regressor = DecisionTree(max_depth=8, criterion_name='mad_median')\n",
        "regressor.fit(RX_train, Ry_train)\n",
        "predictions_mad = regressor.predict(RX_test)\n",
        "mse = mean_squared_error(Ry_test, predictions_mad)\n",
        "assert 0.4 < mse < 2"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1Wpjfsg_pS94"
      },
      "source": [
        "### Test 6: MSE Variance (0.15 points)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "deletable": false,
        "editable": false,
        "nbgrader": {
          "cell_type": "code",
          "checksum": "d8ae6da572b6c3a76405ebfa4b9f4fd6",
          "grade": true,
          "grade_id": "cell-1ddb0377b6c68deb",
          "locked": true,
          "points": 0.15,
          "schema_version": 3,
          "solution": false,
          "task": false
        },
        "id": "uJMD8Go3pS94"
      },
      "outputs": [],
      "source": [
        "housing = fetch_california_housing()\n",
        "random_indices = np.random.choice(np.arange(len(housing.data)), 500)\n",
        "\n",
        "regr_data = housing.data[random_indices]\n",
        "regr_target = housing.target[random_indices, None]\n",
        "RX_train, RX_test, Ry_train, Ry_test = train_test_split(regr_data, regr_target, test_size=0.2, random_state=42)\n",
        "\n",
        "regressor = DecisionTree(max_depth=8, criterion_name='variance')\n",
        "regressor.fit(RX_train, Ry_train)\n",
        "predictions_mad = regressor.predict(RX_test)\n",
        "mse = mean_squared_error(Ry_test, predictions_mad)\n",
        "assert 0.5 < mse < 1.8"
      ]
    }
  ],
  "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.7.7"
    },
    "colab": {
      "name": "assignment0_04_submission_template.ipynb",
      "provenance": []
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}