HW_Trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Деревья решений решают проблемы\n",
    "__Суммарное количество баллов: 10__\n",
    "\n",
    "Вы уже знакомы с классификацией методом KNN. В этом задании предстоит реализовать другой метод классификации - дерево решений. \n",
    "\n",
    "Одной из его особенностей является возможность объяснить в человекочитаемой форме, почему мы отнесли объект к определенному классу. Эта особенность позволяет использовать деревья решений для создания систем, которые могут подсказывать специалистам, на что именно стоит обратить внимание при принятии решений."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задание 1 (1 балл)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Во время построения дерева решений нам потребуется определить, какой из предикатов лучше всего разбивает обучающую выборку. Есть два критерия, которые позволяют это сделать: критерий Джини и энтропийный критерий. Первый для подсчета информативности разбиения использует коэффициент Джини, второй - энтропию. Реализуйте подсчет этих коэффициентов, а так же подсчет информативности разбиения. \n",
    "\n",
    "#### Описание функций\n",
    "`gini(x)` считает коэффициент Джини для массива меток\n",
    "\n",
    "`entropy(x)` считает энтропию для массива меток\n",
    "\n",
    "`gain(left_y, right_y, criterion)` считает информативность разбиения массива меток на левую `left_y` и правую `right_y` части при помощи `criterion`, который задается функцией (не строкой)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini(x):\n",
    "    raise NotImplementedError()\n",
    "    \n",
    "def entropy(x):\n",
    "    raise NotImplementedError()\n",
    "\n",
    "def gain(left_y, right_y, criterion):\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задание 2 (1 балл)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Деревья решений имеют хорошую интерпретируемость, т.к. позволяют не только предсказать класс, но и объяснить, почему мы предсказали именно его. Например, мы можем его нарисовать. Чтобы сделать это, нам необходимо знать, как оно устроено внутри. Реализуйте классы, которые будут задавать структуру дерева. \n",
    "\n",
    "#### DecisionTreeLeaf\n",
    "Поля:\n",
    "1. `y` должно содержать класс, который встречается чаще всего среди элементов листа дерева\n",
    "\n",
    "#### DecisionTreeNode\n",
    "В данной домашней работе мы ограничемся порядковыми и количественными признаками, поэтому достаточно хранить измерение и значение признака, по которому разбиваем обучающую выборку.\n",
    "\n",
    "Поля:\n",
    "1. `split_dim` измерение, по которому разбиваем выборку\n",
    "2. `split_value` значение, по которому разбираем выборку\n",
    "3. `left` поддерево, отвечающее за случай `x[split_dim] < split_value`. Может быть `DecisionTreeNode` или `DecisionTreeLeaf`\n",
    "4. `right` поддерево, отвечающее за случай `x[split_dim] >= split_value`. Может быть `DecisionTreeNode` или `DecisionTreeLeaf`\n",
    "\n",
    "__Интерфейс классов можно и нужно менять при необходимости__ (например, для вычисления вероятности в следующем задании)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DecisionTreeLeaf:\n",
    "    def __init__(self):\n",
    "        self.y = None\n",
    "        raise NotImplementedError()\n",
    "\n",
    "class DecisionTreeNode:\n",
    "    def __init__(self, split_dim, split_value, left, right):\n",
    "        self.split_dim = None\n",
    "        self.split_value = None\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задание 3 (6 баллов)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь перейдем к самому дереву решений. Реализуйте класс `DecisionTreeClassifier`.\n",
    "\n",
    "#### Описание методов\n",
    "`fit(X, y)` строит дерево решений по обучающей выборке.\n",
    "\n",
    "`predict_proba(X)` для каждого элемента из `X` возвращает словарь `dict`, состоящий из пар `(класс, вероятность)`. Вероятности классов в листе можно определить через количество объектов соответствующего класса в листе. \n",
    "\n",
    "#### Описание параметров конструктора\n",
    "`criterion=\"gini\"` - задает критерий, который будет использоваться при построении дерева. Возможные значения: `\"gini\"`, `\"entropy\"`.\n",
    "\n",
    "`max_depth=None` - ограничение глубины дерева. Если `None` - глубина не ограничена\n",
    "\n",
    "`min_samples_leaf=1` - минимальное количество элементов в каждом листе дерева.\n",
    "\n",
    "#### Описание полей\n",
    "`root` - корень дерева. Может быть `DecisionTreeNode` или `DecisionTreeLeaf`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DecisionTreeClassifier:\n",
    "    def __init__(self, criterion=\"gini\", max_depth=None, min_samples_leaf=1):\n",
    "        self.root = None\n",
    "        raise NotImplementedError()\n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        raise NotImplementedError()\n",
    "    \n",
    "    def predict_proba(self, X):\n",
    "        raise NotImplementedError()\n",
    "    \n",
    "    def predict(self, X):\n",
    "        proba = self.predict_proba(X)\n",
    "        return [max(p.keys(), key=lambda k: p[k]) for p in proba]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Построенное дерево можно нарисовать. Метод `draw_tree` рисует дерево и сохраняет его в указанный файл."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tree_depth(tree_root):\n",
    "    if isinstance(tree_root, DecisionTreeNode):\n",
    "        return max(tree_depth(tree_root.left), tree_depth(tree_root.right)) + 1\n",
    "    else:\n",
    "        return 1\n",
    "\n",
    "def draw_tree_rec(tree_root, x_left, x_right, y):\n",
    "    x_center = (x_right - x_left) / 2 + x_left\n",
    "    if isinstance(tree_root, DecisionTreeNode):\n",
    "        x_center = (x_right - x_left) / 2 + x_left\n",
    "        x = draw_tree_rec(tree_root.left, x_left, x_center, y - 1)\n",
    "        plt.plot((x_center, x), (y - 0.1, y - 0.9), c=(0, 0, 0))\n",
    "        x = draw_tree_rec(tree_root.right, x_center, x_right, y - 1)\n",
    "        plt.plot((x_center, x), (y - 0.1, y - 0.9), c=(0, 0, 0))\n",
    "        plt.text(x_center, y, \"x[%i] < %f\" % (tree_root.split_dim, tree_root.split_value),\n",
    "                horizontalalignment='center')\n",
    "    else:\n",
    "        plt.text(x_center, y, str(tree_root.y),\n",
    "                horizontalalignment='center')\n",
    "    return x_center\n",
    "\n",
    "def draw_tree(tree, save_path=None):\n",
    "    td = tree_depth(tree.root)\n",
    "    plt.figure(figsize=(0.33 * 2 ** td, 2 * td))\n",
    "    plt.xlim(-1, 1)\n",
    "    plt.ylim(0.95, td + 0.05)\n",
    "    plt.axis('off')\n",
    "    draw_tree_rec(tree.root, -1, 1, td)\n",
    "    plt.tight_layout()\n",
    "    if save_path is not None:\n",
    "        plt.savefig(save_path)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для двумерного набора данных дерево можно отобразить на плоскости с данными. Кроме того, как и для любого классификатора, для него можно построить roc-кривую"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_roc_curve(y_test, p_pred):\n",
    "    positive_samples = sum(1 for y in y_test if y == 0)\n",
    "    tpr = []\n",
    "    fpr = []\n",
    "    for w in np.arange(-0.01, 1.02, 0.01):\n",
    "        y_pred = [(0 if p.get(0, 0) > w else 1) for p in p_pred]\n",
    "        tpr.append(sum(1 for yp, yt in zip(y_pred, y_test) if yp == 0 and yt == 0) / positive_samples)\n",
    "        fpr.append(sum(1 for yp, yt in zip(y_pred, y_test) if yp == 0 and yt != 0) / (len(y_test) - positive_samples))\n",
    "    plt.figure(figsize = (7, 7))\n",
    "    plt.plot(fpr, tpr)\n",
    "    plt.plot([0, 1], [0, 1], linestyle=\"--\")\n",
    "    plt.xlabel(\"False positive rate\")\n",
    "    plt.ylabel(\"True positive rate\")\n",
    "    plt.xlim(-0.01, 1.01)\n",
    "    plt.ylim(-0.01, 1.01)\n",
    "    plt.tight_layout()\n",
    "    plt.show()\n",
    "\n",
    "def rectangle_bounds(bounds):\n",
    "    return ((bounds[0][0], bounds[0][0], bounds[0][1], bounds[0][1]), \n",
    "            (bounds[1][0], bounds[1][1], bounds[1][1], bounds[1][0]))\n",
    "\n",
    "def plot_2d_tree(tree_root, bounds, colors):\n",
    "    if isinstance(tree_root, DecisionTreeNode):\n",
    "        if tree_root.split_dim:\n",
    "            plot_2d_tree(tree_root.left, [bounds[0], [bounds[1][0], tree_root.split_value]], colors)\n",
    "            plot_2d_tree(tree_root.right, [bounds[0], [tree_root.split_value, bounds[1][1]]], colors)\n",
    "            plt.plot(bounds[0], (tree_root.split_value, tree_root.split_value), c=(0, 0, 0))\n",
    "        else:\n",
    "            plot_2d_tree(tree_root.left, [[bounds[0][0], tree_root.split_value], bounds[1]], colors)\n",
    "            plot_2d_tree(tree_root.right, [[tree_root.split_value, bounds[0][1]], bounds[1]], colors)\n",
    "            plt.plot((tree_root.split_value, tree_root.split_value), bounds[1], c=(0, 0, 0))\n",
    "    else:\n",
    "        x, y = rectangle_bounds(bounds)\n",
    "        plt.fill(x, y, c=colors[tree_root.y] + [0.2])\n",
    "\n",
    "def plot_2d(tree, X, y):\n",
    "    plt.figure(figsize=(9, 9))\n",
    "    colors = dict((c, list(np.random.random(3))) for c in np.unique(y))\n",
    "    bounds = list(zip(np.min(X, axis=0), np.max(X, axis=0)))\n",
    "    plt.xlim(*bounds[0])\n",
    "    plt.ylim(*bounds[1])\n",
    "    plot_2d_tree(tree.root, list(zip(np.min(X, axis=0), np.max(X, axis=0))), colors)\n",
    "    for c in np.unique(y):\n",
    "        plt.scatter(X[y==c, 0], X[y==c, 1], c=[colors[c]], label=c)\n",
    "    plt.legend()\n",
    "    plt.tight_layout()\n",
    "    plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задание 4 (2 балла)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Протестируйте решение на датасете spam.\n",
    "Для этой задачи используйте данные x_spam_train и y_spam_train:\n",
    "1. Выполните загрузку и предобработку файлов x_spam_train и y_spam_train.\n",
    "2. Разбейте x_spam_train и y_spam_train на x_train, y_train, x_test и y_test для оценки точности работы алгоритма.\n",
    "3. Посчитайте метрики `precision`, `recall`, `accuracy` для модели Decision Tree. Если необходимо, попробуйте разные наборы параметров для получения лучшего результата.\n",
    "4. Сравните значения метрик с результатами модели kNN из предыдущего задания (можно использовать реализацию из библиотеки `sklearn`).\n",
    "5. Ответьте на следующие вопросы:\n",
    "    - Какой нужен препроцессинг данных для моделей?\n",
    "    - Какая модель делает предсказания лучше?  Предположите, почему."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Ваш ответ_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.metrics import accuracy_score, recall_score, precision_score\n",
    "\n",
    "from sklearn.neighbors import KNeighborsClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train, y_train = #YOUR_CODE\n",
    "X_test, y_test = #YOUR_CODE\n",
    "tree = DecisionTreeClassifier(max_depth=5, min_samples_leaf=30)\n",
    "tree.fit(X_train, y_train)\n",
    "plot_roc_curve(y_test, tree.predict_proba(X_test))\n",
    "draw_tree(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Обучите модель на всех данных из x_spam_train и y_spam_train.\n",
    "2. Сделайте submit своего решения и получите значение f1_score не менее 0.6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "submission = pd.DataFrame(columns = [\"Id\", \"Expected\"])\n",
    "submission[\"Id\"] = test[\"Id\"]\n",
    "submission[\"Expected\"] = #YOUR CODE\n",
    "submission.to_csv('submission.csv', index=False)\n"
   ]
  }
 ],
 "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.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}