{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Деревья решений\n", "Шестаков А.В. Майнор по анализу данных 05/04/2016" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "На прошлых занятиях мы рассматривали **линейные** модели классификации и регрессии. Деревья решений - совсем другая история. Во-первых, потому что их можно использовать и для регрессии и для классификации, а во-вторых линейностью там только слегка веет.\n", "\n", "Формально, деревья решений можно представить в виде вложенного набора правил \"Если - То\", но гораздо нагляднее изображать их именно в виде дерева.\n", "\n", "Например, дерево может выглядеть так:\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Классификация с деревьями решений" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Давайте попробуем вспомнить, как они стоятся. Рассмотрим следующий набор данных\n", "\n", "\n", "| ID | Refund | Marital Status | Income | Cheat\n", "|-\n", "| 1 | Yes | Single | 125K | No\n", "| 2 | No | Married | 100K | No\n", "| 3 | No | Single | 70K | No\n", "| 4 | Yes | Married | 120K | No\n", "| 5 | No | Divorced | 95K | Yes\n", "| 6 | No | Married | 60K | No\n", "| 7 | Yes | Divorced | 220K | No\n", "| 8 | No | Single | 85K | Yes\n", "| 9 | No | Married | 75K | No\n", "| 10 | No | Single | 90K | Yes\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Имеем 3 признака и класс *Cheat*. Нужно выбрать признак, который наилучшим образом дифференцирует между классами. Посчитать это можно с помощью Impurity Measures и прироста информации:\n", "\n", "**Impurity Measures: (меры неравенства\\неопределенности)**\n", "* Gini index $I(S) = 1 - \\sum\\limits_k (p_k)^2$\n", "* Entropy $I(S) = -\\sum\\limits_k p_k \\log(p_k)$\n", "* Missclassification error $I(S) = 1 - \\max\\limits_k p_k$\n", "\n", "$p_k$ - доля класса $k$ в узле дерева $S$\n", "\n", "**Прирост информации: (насколько уменьшится неопределенность)**
\n", "$$ Gain(S, A) = I(S) - \\sum\\limits_v\\frac{|S_v|}{|S|}\\cdot I(S_v),$$ где $A$ - это некий атрибут, а $v$ - его значения\n", "\n", "Например, для нашей таблицы:\n", "$$I(S) = -(\\frac{3}{10}\\log(\\frac{3}{10}) + \\frac{7}{10}\\log(\\frac{7}{10})) = 0.61$$\n", "\n", "Возьмем, например, атрибут *Marital Status*\n", "\n", "$$Gain(S, \\text{`Marital Status`}) = I(S) - (\\frac{4}{10}\\cdot I(S_{single}) + \\frac{2}{10}\\cdot I(S_{divorced}) + \\frac{4}{10}\\cdot I(S_{married})) = 0.19$$\n", "\n", "Проделаем тоже самое для остальных атрибутов.." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Your code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Регрессия с деревьями решений" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "В этом случае всё очень похоже, с той разницой, что мы будем пытаться уменьшить среднюю квадратичную ошибку\n", "$$I(S) = \\frac{1}{|S|} \\sum\\limits_{i \\in S} (y_i - c)^2 $$ \n", "$$ c = \\frac{1}{|S|}\\sum\\limits_{i \\in S} y_i $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Как посмотреть на деревья?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Для этого вам понадобится специальная библиотека по работе с графами `graphviz`. [Здесь](http://scikit-learn.org/stable/modules/tree.html) вы можете увидеть пример нарисованного в Python дерева.\n", "\n", "Если вы хотите увидеть правила, то можно использовать код [отсюда](http://stackoverflow.com/questions/20224526/how-to-extract-the-decision-rules-from-scikit-learn-decision-tree)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def get_code(tree, feature_names):\n", " left = tree.tree_.children_left\n", " right = tree.tree_.children_right\n", " threshold = tree.tree_.threshold\n", " features = [feature_names[i] for i in tree.tree_.feature]\n", " value = tree.tree_.value\n", "\n", " def recurse(left, right, threshold, features, node):\n", " if (threshold[node] != -2):\n", " print \"if ( \" + features[node] + \" <= \" + str(threshold[node]) + \" ) {\"\n", " if left[node] != -1:\n", " recurse (left, right, threshold, features,left[node])\n", " print \"} else {\"\n", " if right[node] != -1:\n", " recurse (left, right, threshold, features,right[node])\n", " print \"}\"\n", " else:\n", " print \"return \" + str(value[node])\n", "\n", "\n", " recurse(left, right, threshold, features, 0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Немного интуиции" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import pandas as pd\n", "import numpy as np\n", "import subprocess\n", "\n", "from sklearn.datasets import make_circles\n", "from sklearn.tree import DecisionTreeRegressor\n", "from sklearn.tree import DecisionTreeClassifier\n", "from sklearn.tree import export_graphviz\n", "import matplotlib.pyplot as plt\n", "\n", "plt.style.use('ggplot')\n", "\n", "%matplotlib inline" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Классификация" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "X, y = make_circles(n_samples=500, noise=0.1, factor=0.2)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Your code here" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "with open('tree.dot', 'w') as fout:\n", " export_graphviz(tree, out_file=fout, feature_names=['x1', 'x2'], class_names=['0', '1'])\n", "command = ['dot', '-Tpng', 'tree.dot', '-o', 'tree.png']\n", "subprocess.check_call(command)\n", "plt.figure(figsize=(10, 10))\n", "plt.imshow(plt.imread('tree.png'))\n", "plt.axis('off')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Регрессия" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "X = np.linspace(-5, 5, 100)\n", "X += np.random.randn(X.shape[0])\n", "\n", "y = 5*np.sin(2*X) + X**2\n", "y += 2*np.random.randn(y.shape[0])" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "plt.scatter(X, y)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Your code here" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "with open('tree.dot', 'w') as fout:\n", " export_graphviz(tree, out_file=fout, feature_names=['x1'])\n", "command = ['dot', '-Tpng', 'tree.dot', '-o', 'tree.png']\n", "subprocess.check_call(command)\n", "plt.figure(figsize=(20, 20))\n", "plt.imshow(plt.imread('tree.png'))\n", "plt.axis('off')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Перейдем к практике" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Загрузите [данные](https://www.dropbox.com/s/3t1moa1wpflx2u9/california.dat?dl=0).\n", "\n", "**Задание 1:** Найти оптимальную глубину дерева.
\n", "Разделите выборку на train-test в пропорции 70/30.
\n", "Обучите деревья с глубиной от `1` до `30`. Для каждой глубины расчитайте среднюю квадратичную ошибку на train и на test
\n", "Изобразите эти ошибки на одном графике, сделайте вывод по поводу оптимальной глубины дерева." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Your code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Задание 2:** Выведите важности признаков. Для этого воспользуйтесь `DecisionTreeRegressor.feature_importances_`" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Your code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Задание 3:** Поразмышляйте на темы:\n", "* Нужна ли нормировка признаков для деревьев решений?\n", "* Обработки пропусков в данных.\n", "* Как сделать разделяющие плоскости непараллельные осям?" ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.11" } }, "nbformat": 4, "nbformat_minor": 0 }