{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**决策树**（decision tree）是一种基于树结构的机器学习算法，它和人类在面临决策问题时的处理机制类似。譬如在判定一个西瓜是不是好瓜时，我们会进行一系列的判断：先看它是什么颜色，如果是青绿色，再看它的根蒂是什么形态，如果是蜷缩的，再听一听它敲起来是什么声音，如果是浊响的，最后得出结论，这是一个好瓜。（周志华, 机器学习, 第4章）\n",
    "\n",
    "![](../images/decision-tree-watermelon.png)\n",
    "\n",
    "可以看出，决策树算法和之前的算法有着明显的不同，它是一种 **非参数学习算法**（nonparametric methods）。之前的线性回归、逻辑回归等算法都是先选择一个目标函数，然后通过训练，学习目标函数的系数，这种算法称为 **参数学习算法**（parametric methods）。而非参数学习算法不需要对目标函数做过多的假设，算法可以自由的从训练数据中学习任意形式的函数。\n",
    "\n",
    "决策树算法的核心在于决策树的构建，如上图所示，决策树的每一个非叶子节点对应一个特征测试，所以要构建这样一棵树，首先我们要从样本数据中找出一个特征，通过该特征可以将数据划分成几个子集，然后在每个子集上重复上面的划分过程，直到所有的特征消耗完或子集不能再划分为止，这时生成的整个树形结构就是决策树。如何找到最优的划分特征，是构建过程中最关键的一步，这也是众多决策树算法的精华部分。\n",
    "\n",
    "### 决策树优缺点\n",
    "\n",
    "决策树最大的优点是简单，非常容易理解，而且模型可以可视化，非常直观。它的应用范围很广，可以用于解决回归和分类问题，天然支持多分类问题的求解。此外，无论特征是离散值，还是连续值，都可以处理。\n",
    "\n",
    "决策树很容易在训练数据中生成复杂的树结构，造成过拟合（overfitting），通常用剪枝来解决过拟合，譬如限制树的高度、叶子节点中的最少样本数量等。学习一棵最优的决策树被认为是 NP-Complete 问题，实际中的决策树是基于启发式的贪心算法建立的，这种算法不能保证建立全局最优的决策树，随机森林（Random Forest）可以缓解这个问题。"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}