Chapter5-DecisionTree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第5章 决策树\n",
    "顾名思义,\"决策树\"就是按照建立分支来进行决策的方法,即根据啥(往往是根据某个属性的某个值作为指标，比如“年龄大于20岁的”或“身高大于1米5的”)来区分不同类别的数据,也是一种监督式机器学习算法,从编程角度来看,可以看作是一系列的\"if... then... else...\"的集合,这个模型非常直观,也即可读性非常好,决策树的学习通常包含三个步骤:**特征选择**,**决策树生成**,**决策树的剪枝**.  \n",
    "给定数据集\n",
    ">$$D = \\{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N)\\}$$\n",
    "其中,$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T$为输入实例(特征向量),$n$为特征的个数,$y_i \\in \\{1,2,...,K\\}$为类别标记,$i = 1,2,...,N$,$N$为样本容量\n",
    "\n",
    "目标\n",
    ">构建决策树,使之能改对大量的实例进行正确分类（而为什么要引入决策树的剪枝呢？是要让这颗树尽可能地好，那什么叫好呢？就是用尽可能少的分叉来高效地区分更多的数据）  \n",
    "(本质是构建一组规则,这组规则可以对每个特征进行划分,但是又不能划分太好,不然容易过拟合,泛化能力就会变差)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.1数据集\n",
    "\n",
    "首先建立课本上的数据集合本身  \n",
    "><b>F0:年龄</b>：定义\"青年|中年|老年\"分别为\"1|2|3\",  \n",
    "<b>F1:是否有工作</b>：定义\"是|否\"为\"1|2\",  \n",
    "<b>F2:有自己的房子</b>：定义\"是|否\"为\"1|2\",  \n",
    "<b>F3:信贷情况</b>：\"一般|好|非常好\"为\"1|2|3\",  \n",
    "<b>类别</b>：\"是|否\"为\"1|2\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>年龄</th>\n",
       "      <th>是否有工作</th>\n",
       "      <th>有自己的房子</th>\n",
       "      <th>信贷情况</th>\n",
       "      <th>类别</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    年龄  是否有工作  有自己的房子  信贷情况  类别\n",
       "0    1      2       2     1   2\n",
       "1    1      2       2     2   2\n",
       "2    1      1       2     2   1\n",
       "3    1      1       1     1   1\n",
       "4    1      2       2     1   2\n",
       "5    2      2       2     1   2\n",
       "6    2      2       2     2   2\n",
       "7    2      1       1     2   1\n",
       "8    2      2       1     3   1\n",
       "9    2      2       1     3   1\n",
       "10   3      2       1     3   1\n",
       "11   3      2       1     2   1\n",
       "12   3      1       2     2   1\n",
       "13   3      1       2     3   1\n",
       "14   3      2       2     1   2"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "x = np.asarray([[1,2,2,1],[1,2,2,2],[1,1,2,2],[1,1,1,1],[1,2,2,1],\n",
    "               [2,2,2,1],[2,2,2,2],[2,1,1,2],[2,2,1,3],[2,2,1,3],\n",
    "               [3,2,1,3],[3,2,1,2],[3,1,2,2],[3,1,2,3],[3,2,2,1]])\n",
    "y = np.asarray([2,2,1,1,2,2,2,1,1,1,1,1,1,1,2])\n",
    "import pandas as pd\n",
    "\n",
    "df = pd.concat([pd.DataFrame(x,columns=[u'年龄',u'是否有工作',u'有自己的房子',u'信贷情况']),pd.DataFrame(y,columns=[u'类别'])],axis=1)\n",
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 此时某些用心的读者也许还会发现,给了这些数据之后,实际可以尝试性地按照x的某一列属性作为指标,给定阈值,阈值之上的为某个列别标签,阈值之下的为另一个类别标签,但是问题来啦:选择哪个属性最好呢?\n",
    "这里不得不说到\"信息增益\"的问题了,这个东西可以指导模型选择最合适的属性对原始数据进行第一阶的划分.\n",
    "\n",
    ">这里需要对“信息增益”进行一些讲解，信息增益可以这么理解：如果对一件事进行描述，并且需要10次才能描述完整，那么实际每次描述的时候，描述所涵盖的信息量是不相同的，信息增益，就可以理解为一次描述过程的量。对于这里的决策树来说，就是每次if和else所能带有的信息。实际的定义和形式化描述如下："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## 5.2信息熵和信息增益\n",
    "### 5.2.1信息熵，经验熵，相对熵\n",
    "（1）＂**熵**＂的定义：$$H(X) = -\\sum_{i=1}^nP_i\\log{P_i}$$\n",
    ">观察上式可以得知，熵只和数据分布有关，所以，$H(X)$可以直接写作$H(p)$，且从定义可以验证\n",
    "$$0 \\leq H(p) \\leq \\log n$$\n",
    ">（关于＂熵＂为什么要这么定义，这里给一下思路提示：比如，如果要定义一个三位数，实际只用３个字符存储空间就可以了，这也就是为什么取log的原因了，实际表示的是描述某个对象所需要的基本元素的个数，更详细的关于信息论的定义可以自行学习香浓的那一套信息理论，这里我也不懂很多，只给点提示，另外，这里结合课本给出求解信息熵的代码）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import Counter #计数插件\n",
    "def cal_entropy(x,i):\n",
    "    \"\"\"\n",
    "    计算熵值\n",
    "    x：数据集\n",
    "    ｉ：第ｉ个特征\n",
    "    \"\"\"\n",
    "    if x.ndim == 1:\n",
    "        x = x.reshape((len(x),1)) # 如果是一维的，那么定义为(len(x)行1列)的数据分布\n",
    "    col_i_data = x[:,i] # 第ｉ列数据\n",
    "    uniquevalue = np.unique(col_i_data) # 该属性下查找所有可能的值\n",
    "    H_X = 0 # 统计熵的加和\n",
    "    for j in range(len(uniquevalue)): \n",
    "        i_p = Counter(col_i_data)[j+1]/len(col_i_data) # 对每个属性值计数并计算概率值（占比）\n",
    "        if i_p != 0:\n",
    "            i_logp = np.log2(i_p) # 对数值\n",
    "            H_X = H_X + (-i_p*i_logp) # 累加\n",
    "        elif i_p == 0:\n",
    "            H_X = H_X + 1 # 对于概率值为0的，定义0*log0=1，并累加\n",
    "    return H_X"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "（2）**经验熵**的定义：\n",
    ">实际是对$y$求熵，即$H(Y)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "经验熵 = 0.9709505944546686\n"
     ]
    }
   ],
   "source": [
    "print('经验熵 =',cal_entropy(y,0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "（3）**\"相对熵\"**的定义：\n",
    ">$$H(Y|X) = \\sum_{i=1}^n H(Y|X=x_i)$$\n",
    "表示在已知随机变量$X$的条件下随机变量$Y$的不确定性．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cal_mutualinformation(x,y,i):\n",
    "    \"\"\"\n",
    "    计算第ｉ列的条件熵\n",
    "        x: 数据\n",
    "        y: 类别标签\n",
    "        i: 第ｉ列\n",
    "    \"\"\"\n",
    "    col_i_data = x[:,i]\n",
    "    data = np.column_stack((col_i_data,y)) # 合并了一个数组，[ｘ_i,y]\n",
    "    uniquevalue = np.unique(col_i_data) # 查找所有可能的值\n",
    "    H_YconX = 0 # 统计熵的加和\n",
    "    H_YconX = 0\n",
    "    for j in range(len(uniquevalue)):\n",
    "        D_i = data[col_i_data == uniquevalue[j],:]\n",
    "        uniqueclass = np.unique(y)\n",
    "        factor2 = 0\n",
    "        for k in range(len(uniqueclass)):# H(Di) = sum(|Dik|/Di * log |Dik|/Di)\n",
    "            D_ik = D_i[D_i[:,1] == uniqueclass[k],:]\n",
    "            if (D_ik.shape[0] == 0):\n",
    "                temp2 = 0\n",
    "            else:\n",
    "                temp2 = - D_ik.shape[0]/D_i.shape[0] * np.log2(D_ik.shape[0]/D_i.shape[0])\n",
    "                # print(temp2)\n",
    "            factor2 = factor2 + temp2\n",
    "        H_YconX = H_YconX + len(D_i)/len(col_i_data) * factor2\n",
    "    return H_YconX"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2.2信息增益"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "信息增益为\n",
    ">$$g(D,A) = H(D)-H(D|A)$$\n",
    "表示$A$特征对训练数据$D$的信息增益"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "第 0 个特征的信息增益值为： 0.08300749985576883\n",
      "第 1 个特征的信息增益值为： 0.32365019815155627\n",
      "第 2 个特征的信息增益值为： 0.4199730940219749\n",
      "第 3 个特征的信息增益值为： 0.36298956253708536\n"
     ]
    }
   ],
   "source": [
    "for m in range(x.shape[1]):\n",
    "    print('第',m,'个特征的信息增益值为：',cal_entropy(y,0) - cal_mutualinformation(x,y,m))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">将上面的过程定义成函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.083, 0.324, 0.42, 0.363]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def cal_information_gain(x,y):\n",
    "    \"\"\"\n",
    "    计算每个特征下的信息增益值\n",
    "    \"\"\"\n",
    "    result = []\n",
    "    for i in range(x.shape[1]):\n",
    "        value = cal_entropy(y,0) - cal_mutualinformation(x,y,i)\n",
    "        result.append(value)\n",
    "    return result\n",
    "[round(i,3) for i in cal_information_gain(x,y)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所以上面选择增益最大的(0.42)，即第２个特征（有无房子）\n",
    "注：\n",
    ">那么，这个特征下，以什么值作为分裂点最合适呢？这就像是我们首先在诸多的特征中决定了使用“有无房子”来作为第一个判断条件，那么这个判断的阈值是什么呢？\n",
    "是\n",
    "```python\n",
    "if('有无房子'>=1):\n",
    "```\n",
    "或是\n",
    "```python\n",
    "if('有无房子'>=2):\n",
    "```\n",
    "\n",
    "至此，这里就开始涉及到了决策树的生成过程，注意，从这里开始，就要开始造<b>决策树</b>了！\n",
    "![avatar](img/decision-tree.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# 5.3 ID3生成决策树\n",
    "ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归构建决策树\n",
    "\n",
    "<b>input</b>:  训练数据D，特征集A，阈值  \n",
    "<b>output</b>: 决策树  \n",
    "<b>步骤</b>  \n",
    "><b>S1</b>：若$D$中所有实例均属于同一类$C_k$,则$T$为单节点树，并将类$C_k$作为该节点的类别标记，返回$T$；    \n",
    "><b>S2</b>：若$A$为空集，则T为单节点树，将D中实例数最大的类$C_k$作为该节点的类标记，返回$T$；  \n",
    "><b>S3</b>：否则，选取信息增益最大的特征$A_g$；  \n",
    "><b>S4</b>：若信息增益$A_g$小于阈值，则$T$为单节点树（实质是继续分裂下去意义不大了）  \n",
    "><b>S5</b>：否则对$A_g$下的每个可能的值划分为非空子集$D_i$，$D_i$中实例数最大的类作为标记，构建子节点，由节点及其子节点构成$T$，返回$T$  \n",
    "><b>S6</b>：对第$i$个子节点，以$D_i$为训练集，以$A-{A_i}$为特征集，递归调用S1-S5，得到子树$T_i$，返回$T_i$\n",
    "\n",
    "* 首先：5.2.2中已经计算得出第一个适合分裂的特征是“有无房子”，这里“有无房子”就是根节点root的第一个判断条件：\n",
    ">注：\n",
    "```\n",
    "这里使用了Graphviz用于显示节点图：关于Graphviz的安装与配置\n",
    "1.pip install Graphviz\n",
    "2.官网下载Graphviz的msi安装包，地址：https://graphviz.gitlab.io/_pages/Download/Download_windows.html   \n",
    "3.配置环境变量 user variable：`C:\\Program Files (x86)\\Graphviz2.38\\bin` ,system variable：`C:\\Program Files (x86)\\Graphviz2.38\\bin\\dot.exe`   \n",
    "4.python代码里加入以下代码：\n",
    ">>> import os\n",
    ">>> os.environ[\"PATH\"] += os.pathsep + 'C:\\\\Program Files (x86)\\\\Graphviz2.38\\\\bin'\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3.1 第1次分裂，构建树的root节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'./img/tree.1.gv.png'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import os\n",
    "os.environ[\"PATH\"] += os.pathsep + 'C:\\\\Program Files (x86)\\\\Graphviz2.38\\\\bin'\n",
    "from graphviz import Digraph\n",
    "g = Digraph('G',filename='./img/tree.1.gv')\n",
    "g.edge('F2','?1')\n",
    "g.edge('F2','?2')\n",
    "g.format = 'png'\n",
    "g.view(cleanup=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![avatar](./img/tree.1.gv.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的图形，表示首先特征从F2开始分裂，但是F2的分裂条件是什么呢？  \n",
    "根据F2的取值，得到了两类分裂出来的集合：\n",
    "$D1$和$D2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>年龄</th>\n",
       "      <th>是否有工作</th>\n",
       "      <th>有自己的房子</th>\n",
       "      <th>信贷情况</th>\n",
       "      <th>类别</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    年龄  是否有工作  有自己的房子  信贷情况  类别\n",
       "3    1      1       1     1   1\n",
       "7    2      1       1     2   1\n",
       "8    2      2       1     3   1\n",
       "9    2      2       1     3   1\n",
       "10   3      2       1     3   1\n",
       "11   3      2       1     2   1"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D1 = df[df['有自己的房子'] == 1]\n",
    "D1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>年龄</th>\n",
       "      <th>是否有工作</th>\n",
       "      <th>有自己的房子</th>\n",
       "      <th>信贷情况</th>\n",
       "      <th>类别</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    年龄  是否有工作  有自己的房子  信贷情况  类别\n",
       "0    1      2       2     1   2\n",
       "1    1      2       2     2   2\n",
       "2    1      1       2     2   1\n",
       "4    1      2       2     1   2\n",
       "5    2      2       2     1   2\n",
       "6    2      2       2     2   2\n",
       "12   3      1       2     2   1\n",
       "13   3      1       2     3   1\n",
       "14   3      2       2     1   2"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D2 = df[df['有自己的房子'] == 2]\n",
    "D2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "读者会发现，D1中的类别标签都是1，所以D1就不用分裂了，因为，仅仅凭借“<b>有自己的房子 == 1</b>”这一个特征，就能决定是属于类别1的  \n",
    "即：  \n",
    "$$(有自己的房子 == 1) \\rightarrow (类别==1)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'./img/tree.2.gv.png'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = Digraph('G',filename='./img/tree.2.gv')\n",
    "g.edge('F2','F2==1')\n",
    "g.edge('F2','F2==2')\n",
    "g.edge('F2==1','Label=1,1 step,over')\n",
    "g.edge('F2==2','?')\n",
    "g.format = 'png'\n",
    "g.view(cleanup=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![avator](./img/tree.2.gv.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "那么剩下的D2怎么办呢？  \n",
    "怎么办？继续分裂呀~  \n",
    "### 5.3.2 第2次分裂 \n",
    "<b>此时，需要对数据重新计算信息增益值，来确定下次用哪个特征进行分裂！</b>  \n",
    "* 首先，将x剔除“有自己的房子 == 1”这个前提的，生于D2："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "D2_x：\n",
      " [[1 2 2 1]\n",
      " [1 2 2 2]\n",
      " [1 1 2 2]\n",
      " [1 2 2 1]\n",
      " [2 2 2 1]\n",
      " [2 2 2 2]\n",
      " [3 1 2 2]\n",
      " [3 1 2 3]\n",
      " [3 2 2 1]]\n",
      "D2_y：\n",
      " [2 2 1 2 2 2 1 1 2]\n"
     ]
    }
   ],
   "source": [
    "index = []\n",
    "for i in range(len(x)):\n",
    "    if x[i][2] != 1:\n",
    "        index.append(i)\n",
    "# 输出D2的x\n",
    "D2_x = x[index]\n",
    "# 输出D2的y\n",
    "D2_y = y[index]\n",
    "print('D2_x：\\n',D2_x)\n",
    "print('D2_y：\\n',D2_y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 计算生于特征的信息增益："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.252, 0.918, 0.0, 0.474]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[round(i,3) for i in cal_information_gain(D2_x,D2_y)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "此时信息增益最大的特征是F1（有无工作），通过“有无工作”这个特征将数据继续区分为了D3和D4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>年龄</th>\n",
       "      <th>是否有工作</th>\n",
       "      <th>有自己的房子</th>\n",
       "      <th>信贷情况</th>\n",
       "      <th>类别</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    年龄  是否有工作  有自己的房子  信贷情况  类别\n",
       "2    1      1       2     2   1\n",
       "12   3      1       2     2   1\n",
       "13   3      1       2     3   1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D3 = D2[D2['是否有工作']==1]\n",
    "D3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>年龄</th>\n",
       "      <th>是否有工作</th>\n",
       "      <th>有自己的房子</th>\n",
       "      <th>信贷情况</th>\n",
       "      <th>类别</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    年龄  是否有工作  有自己的房子  信贷情况  类别\n",
       "0    1      2       2     1   2\n",
       "1    1      2       2     2   2\n",
       "4    1      2       2     1   2\n",
       "5    2      2       2     1   2\n",
       "6    2      2       2     2   2\n",
       "14   3      2       2     1   2"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D4 = D2[D2['是否有工作']==2]\n",
    "D4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "此时，发现D3的类别标签都是1，而D4的类别标签都是2，已经完美分开了，所以这次使用这个特征分裂即可！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'./img/tree.3.gv.png'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = Digraph('G',filename='./img/tree.3.gv')\n",
    "g.edge('F2','F2==1')\n",
    "g.edge('F2','F2==2')\n",
    "g.edge('F2==1','Label=1,1 step,over')\n",
    "g.edge('F2==2','F1==1')\n",
    "g.edge('F2==2','F1==2')\n",
    "g.edge('F1==1','Label=1,2 step,over')\n",
    "g.edge('F1==2','Label=2,2 step,over')\n",
    "g.format = 'png'\n",
    "g.view(cleanup=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![avatar](./img/tree.3.gv.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 汇总上述的预测过程"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "预测类别标签： [2 2 1 1 2 2 2 1 1 1 1 1 1 1 2]\n",
      "真实类别标签： [2 2 1 1 2 2 2 1 1 1 1 1 1 1 2]\n",
      "准确率： 1.0\n"
     ]
    }
   ],
   "source": [
    "label = []\n",
    "for i in x:\n",
    "    if i[2]==1:\n",
    "        label.append(1)\n",
    "    if i[2]==2:\n",
    "        if i[1]==1:\n",
    "            label.append(1)\n",
    "        if i[1]==2:\n",
    "            label.append(2)\n",
    "print('预测类别标签：',np.asarray(label))\n",
    "print('真实类别标签：',y)\n",
    "print('准确率：',1.0-sum(np.sign(np.abs(np.asarray(label)-y)))/len(y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# 5.4 自己写一个决策树函数\n",
    "暂时使用ID3的策略生成决策树\n",
    "\n",
    "## 5.4.1 伪代码"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "def train(D):\n",
    "    x = D.x\n",
    "    y = D.y\n",
    "    \n",
    "    #     S1：如果所有的类别标签都一样为Ck，那么直接返回树\n",
    "    if all y == Ck:\n",
    "        return T\n",
    "    \n",
    "    #     S2：如果子特征集为空，返回T\n",
    "    A = 为已经去掉上一次特征列的新的子特征集\n",
    "    if A == 空:\n",
    "        return T\n",
    "    else:\n",
    "        计算A中各特征对D的信息增益，选择Ag（信息增益最大的特征）\n",
    "        if Ag的信息增益==极小:\n",
    "            返回Ck\n",
    "        else:\n",
    "            对Ag的每个可能值ai，将D分为若干子集Di，Di中实例数最大的类别作为标记"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.4.2 按照书上的详细输出每个步骤产生的输出"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------------------------------------------------------------------------------------\n",
      "\n",
      "****************************** -输入- ******************************\n",
      "训练数据集\n",
      "\tD =： [array([[1, 2, 2, 1],\n",
      "       [1, 2, 2, 2],\n",
      "       [1, 1, 2, 2],\n",
      "       [1, 1, 1, 1],\n",
      "       [1, 2, 2, 1],\n",
      "       [2, 2, 2, 1],\n",
      "       [2, 2, 2, 2],\n",
      "       [2, 1, 1, 2],\n",
      "       [2, 2, 1, 3],\n",
      "       [2, 2, 1, 3],\n",
      "       [3, 2, 1, 3],\n",
      "       [3, 2, 1, 2],\n",
      "       [3, 1, 2, 2],\n",
      "       [3, 1, 2, 3],\n",
      "       [3, 2, 2, 1]]), array([2, 2, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2])]\n",
      "特征集    \n",
      "\tA =： {0, 1, 2, 3}\n",
      "阈值    \n",
      "\tepsilon =： 0.01\n",
      "\n",
      "****************************** -S1- ******************************\n",
      "D中所有实例隶属于不同的类别标签→S2\n",
      "\n",
      "****************************** -S2- ******************************\n",
      "A不为空，将继续执行→S3\n",
      "\n",
      "****************************** -S3- ******************************\n",
      "信息增益最大的列：为第 2 列，即Ag = 2 ，其中信息增益值 = 0.4199730940219749 ，将继续执行→S4\n",
      "【模型参数】：分裂特征Index = 2\n",
      "\n",
      "****************************** -S4- ******************************\n",
      "信息增益值大于epsilon( 0.01 )，将继续执行，将继续执行→S5\n",
      "\n",
      "****************************** -S5- ******************************\n",
      "该特征所有可以分裂的节点包含了： [1 2]\n",
      "当第 2 列属性的值等于 1 时 D( 0 )= [[1 1 1 1]\n",
      " [2 1 1 2]\n",
      " [2 2 1 3]\n",
      " [2 2 1 3]\n",
      " [3 2 1 3]\n",
      " [3 2 1 2]] [1 1 1 1 1 1]\n",
      "当第 2 列属性的值等于 2 时 D( 1 )= [[1 2 2 1]\n",
      " [1 2 2 2]\n",
      " [1 1 2 2]\n",
      " [1 2 2 1]\n",
      " [2 2 2 1]\n",
      " [2 2 2 2]\n",
      " [3 1 2 2]\n",
      " [3 1 2 3]\n",
      " [3 2 2 1]] [2 2 1 2 2 2 1 1 2]\n",
      "实例数最大的类是： 1 ，包含的样本数是： 6\n",
      "【模型参数】：类别标签是 1\n",
      "实例数最大的类是： 2 ，包含的样本数是： 6\n",
      "【模型参数】：类别标签是 2\n",
      "\n",
      "****************************** -S6- ******************************\n",
      "【模型参数】：目前的A = {0, 1, 3}\n",
      "------------------------------------------------------------------------------------\n",
      "\n",
      "****************************** -输入- ******************************\n",
      "训练数据集\n",
      "\tD =： [array([[1, 1, 1, 1],\n",
      "       [2, 1, 1, 2],\n",
      "       [2, 2, 1, 3],\n",
      "       [2, 2, 1, 3],\n",
      "       [3, 2, 1, 3],\n",
      "       [3, 2, 1, 2]]), array([1, 1, 1, 1, 1, 1])]\n",
      "特征集    \n",
      "\tA =： {0, 1, 3}\n",
      "阈值    \n",
      "\tepsilon =： 0.01\n",
      "\n",
      "****************************** -S1- ******************************\n",
      "【模型参数】所有实例都为同一个类别标签 [1] ，在此终止，将会返回树T.\n",
      "------------------------------------------------------------------------------------\n",
      "\n",
      "****************************** -输入- ******************************\n",
      "训练数据集\n",
      "\tD =： [array([[1, 2, 2, 1],\n",
      "       [1, 2, 2, 2],\n",
      "       [1, 1, 2, 2],\n",
      "       [1, 2, 2, 1],\n",
      "       [2, 2, 2, 1],\n",
      "       [2, 2, 2, 2],\n",
      "       [3, 1, 2, 2],\n",
      "       [3, 1, 2, 3],\n",
      "       [3, 2, 2, 1]]), array([2, 2, 1, 2, 2, 2, 1, 1, 2])]\n",
      "特征集    \n",
      "\tA =： {0, 1, 3}\n",
      "阈值    \n",
      "\tepsilon =： 0.01\n",
      "\n",
      "****************************** -S1- ******************************\n",
      "D中所有实例隶属于不同的类别标签→S2\n",
      "\n",
      "****************************** -S2- ******************************\n",
      "A不为空，将继续执行→S3\n",
      "\n",
      "****************************** -S3- ******************************\n",
      "信息增益最大的列：为第 1 列，即Ag = 1 ，其中信息增益值 = 0.9182958340544896 ，将继续执行→S4\n",
      "【模型参数】：分裂特征Index = 1\n",
      "\n",
      "****************************** -S4- ******************************\n",
      "信息增益值大于epsilon( 0.01 )，将继续执行，将继续执行→S5\n",
      "\n",
      "****************************** -S5- ******************************\n",
      "该特征所有可以分裂的节点包含了： [1 2]\n",
      "当第 1 列属性的值等于 1 时 D( 0 )= [[1 1 2 2]\n",
      " [3 1 2 2]\n",
      " [3 1 2 3]] [1 1 1]\n",
      "当第 1 列属性的值等于 2 时 D( 1 )= [[1 2 2 1]\n",
      " [1 2 2 2]\n",
      " [1 2 2 1]\n",
      " [2 2 2 1]\n",
      " [2 2 2 2]\n",
      " [3 2 2 1]] [2 2 2 2 2 2]\n",
      "实例数最大的类是： 1 ，包含的样本数是： 3\n",
      "【模型参数】：类别标签是 1\n",
      "实例数最大的类是： 2 ，包含的样本数是： 6\n",
      "【模型参数】：类别标签是 2\n",
      "\n",
      "****************************** -S6- ******************************\n",
      "【模型参数】：目前的A = {0, 3}\n",
      "------------------------------------------------------------------------------------\n",
      "\n",
      "****************************** -输入- ******************************\n",
      "训练数据集\n",
      "\tD =： [array([[1, 1, 2, 2],\n",
      "       [3, 1, 2, 2],\n",
      "       [3, 1, 2, 3]]), array([1, 1, 1])]\n",
      "特征集    \n",
      "\tA =： {0, 3}\n",
      "阈值    \n",
      "\tepsilon =： 0.01\n",
      "\n",
      "****************************** -S1- ******************************\n",
      "【模型参数】所有实例都为同一个类别标签 [1] ，在此终止，将会返回树T.\n",
      "------------------------------------------------------------------------------------\n",
      "\n",
      "****************************** -输入- ******************************\n",
      "训练数据集\n",
      "\tD =： [array([[1, 2, 2, 1],\n",
      "       [1, 2, 2, 2],\n",
      "       [1, 2, 2, 1],\n",
      "       [2, 2, 2, 1],\n",
      "       [2, 2, 2, 2],\n",
      "       [3, 2, 2, 1]]), array([2, 2, 2, 2, 2, 2])]\n",
      "特征集    \n",
      "\tA =： {0, 3}\n",
      "阈值    \n",
      "\tepsilon =： 0.01\n",
      "\n",
      "****************************** -S1- ******************************\n",
      "【模型参数】所有实例都为同一个类别标签 [2] ，在此终止，将会返回树T.\n"
     ]
    }
   ],
   "source": [
    "# 算法的输入数据初始化D、A、epsilon\n",
    "#################################################################################################\n",
    "# 准备数据\n",
    "import numpy as np\n",
    "x = np.asarray([[1,2,2,1],[1,2,2,2],[1,1,2,2],[1,1,1,1],[1,2,2,1],\n",
    "               [2,2,2,1],[2,2,2,2],[2,1,1,2],[2,2,1,3],[2,2,1,3],\n",
    "               [3,2,1,3],[3,2,1,2],[3,1,2,2],[3,1,2,3],[3,2,2,1]])\n",
    "y = np.asarray([2,2,1,1,2,2,2,1,1,1,1,1,1,1,2])\n",
    "#################################################################################################\n",
    "level = 0\n",
    "D = []\n",
    "D.append(x)\n",
    "D.append(y)\n",
    "A = set(range(4))\n",
    "epsilon = 0.01\n",
    "def f(D,A):\n",
    "    print('------------------------------------------------------------------------------------')\n",
    "    x = D[0]\n",
    "    y = D[1]\n",
    "    print('\\n'+'**'*15,'-输入-','**'*15)\n",
    "    print('训练数据集\\n\\tD =：',D)\n",
    "    print('特征集    \\n\\tA =：',A)\n",
    "    print('阈值    \\n\\tepsilon =：',epsilon)\n",
    "    #############################################################################################\n",
    "    print('\\n'+'**'*15,'-S1-','**'*15)\n",
    "    if len(np.unique(y))==1:\n",
    "        print('【模型参数】所有实例都为同一个类别标签',np.unique(y),'，在此终止，将会返回树T.')\n",
    "    else:\n",
    "        print('D中所有实例隶属于不同的类别标签→S2')\n",
    "\n",
    "        #############################################################################################\n",
    "        print('\\n'+'**'*15,'-S2-','**'*15)\n",
    "        if len(A)==0:\n",
    "            print('A已经没有特征需要分析了，在此终止，将会返回树T.')\n",
    "        elif len(A)>0:\n",
    "            print('A不为空，将继续执行→S3')\n",
    "\n",
    "            #############################################################################################\n",
    "            print('\\n'+'**'*15,'-S3-','**'*15)\n",
    "            max_gain_col = np.argmax(cal_information_gain(x,y))\n",
    "            print('信息增益最大的列：为第',max_gain_col,'列，即Ag =',max_gain_col,'，其中信息增益值 =',cal_information_gain(x,y)[max_gain_col],'，将继续执行→S4')\n",
    "            print('【模型参数】：分裂特征Index =',max_gain_col)\n",
    "\n",
    "            #############################################################################################\n",
    "            print('\\n'+'**'*15,'-S4-','**'*15)\n",
    "            if cal_information_gain(x,y)[max_gain_col] < epsilon:\n",
    "                print('特征产生的信息增益过小，在此终止，将会返回树T.')\n",
    "            else:\n",
    "                print('信息增益值大于epsilon(',str(epsilon),')，将继续执行，将继续执行→S5')\n",
    "\n",
    "                #############################################################################################    \n",
    "                print('\\n'+'**'*15,'-S5-','**'*15)\n",
    "                print('该特征所有可以分裂的节点包含了：',np.unique(x[:,max_gain_col]))\n",
    "                Di_x = []\n",
    "                Di_y = []\n",
    "                for i in np.unique(x[:,max_gain_col]):\n",
    "                    Di_x.append(x[x[:,max_gain_col] == i])\n",
    "                    Di_y.append(y[x[:,max_gain_col] == i])\n",
    "                for i in range(len(np.unique(x[:,max_gain_col]))):\n",
    "                    print('当第',str(max_gain_col),'列属性的值等于',np.unique(x[:,max_gain_col])[i],'时','D(',str(i),')=',Di_x[i],Di_y[i])\n",
    "                for i in Di_y:\n",
    "                    max_count = -1\n",
    "                    max_count_class = -1\n",
    "                    for j in np.unique(i):\n",
    "                        count = list(i).count(j)\n",
    "                        if max_count<count:\n",
    "                            max_count = count\n",
    "                            max_count_class = j\n",
    "                    print('实例数最大的类是：',max_count_class,'，包含的样本数是：',max_count)\n",
    "                    print('【模型参数】：类别标签是',max_count_class)\n",
    "                #############################################################################################\n",
    "                print('\\n'+'**'*15,'-S6-','**'*15)\n",
    "                A.remove(max_gain_col)\n",
    "                print('【模型参数】：目前的A =',A)\n",
    "                for i in range(len(Di_x)):\n",
    "                    Di = [Di_x[i],Di_y[i]]\n",
    "                    f(Di,A)\n",
    "        \n",
    "f(D,A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.4.3 以下化简了输出，以方便查看决策树的决策流程"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--------------------------------------level =  0 --------------------------------------------\n",
      "   【      模型参数】：分裂第i = 2 个特征（i 属于  {0, 1, 2, 3} ,可以产生的信息增益为 0.42\n",
      "   【子节点模型参数】：可以分裂出类别标签 1\n",
      "   【子节点模型参数】：可以分裂出类别标签 2\n",
      ">> --------------------------------------level =  1 --------------------------------------------\n",
      "   【条件参数】：if x[ i, 2 ] = 1 :\n",
      "   [array([[1, 1, 1, 1],\n",
      "       [2, 1, 1, 2],\n",
      "       [2, 2, 1, 3],\n",
      "       [2, 2, 1, 3],\n",
      "       [3, 2, 1, 3],\n",
      "       [3, 2, 1, 2]]), array([1, 1, 1, 1, 1, 1])]\n",
      "     【      模型参数】在本Di分支中所有实例的标签一样，Label = [1] ，在此终止，将会返回树T.\n",
      ">> --------------------------------------level =  1 --------------------------------------------\n",
      "   【条件参数】：if x[ i, 2 ] = 2 :\n",
      "   [array([[1, 2, 2, 1],\n",
      "       [1, 2, 2, 2],\n",
      "       [1, 1, 2, 2],\n",
      "       [1, 2, 2, 1],\n",
      "       [2, 2, 2, 1],\n",
      "       [2, 2, 2, 2],\n",
      "       [3, 1, 2, 2],\n",
      "       [3, 1, 2, 3],\n",
      "       [3, 2, 2, 1]]), array([2, 2, 1, 2, 2, 2, 1, 1, 2])]\n",
      "     【      模型参数】：分裂第i = 1 个特征（i 属于  {0, 1, 2, 3} ,可以产生的信息增益为 0.918\n",
      "     【子节点模型参数】：可以分裂出类别标签 1\n",
      "     【子节点模型参数】：可以分裂出类别标签 2\n",
      ">>>> --------------------------------------level =  2 --------------------------------------------\n",
      "     【条件参数】：if x[ i, 1 ] = 1 :\n",
      "     [array([[1, 1, 2, 2],\n",
      "       [3, 1, 2, 2],\n",
      "       [3, 1, 2, 3]]), array([1, 1, 1])]\n",
      "       【      模型参数】在本Di分支中所有实例的标签一样，Label = [1] ，在此终止，将会返回树T.\n",
      ">>>> --------------------------------------level =  2 --------------------------------------------\n",
      "     【条件参数】：if x[ i, 1 ] = 2 :\n",
      "     [array([[1, 2, 2, 1],\n",
      "       [1, 2, 2, 2],\n",
      "       [1, 2, 2, 1],\n",
      "       [2, 2, 2, 1],\n",
      "       [2, 2, 2, 2],\n",
      "       [3, 2, 2, 1]]), array([2, 2, 2, 2, 2, 2])]\n",
      "       【      模型参数】在本Di分支中所有实例的标签一样，Label = [2] ，在此终止，将会返回树T.\n"
     ]
    }
   ],
   "source": [
    "# 算法的输入数据初始化D、A、epsilon\n",
    "#################################################################################################\n",
    "# 准备数据\n",
    "import numpy as np\n",
    "x = np.asarray([[1,2,2,1],[1,2,2,2],[1,1,2,2],[1,1,1,1],[1,2,2,1],\n",
    "               [2,2,2,1],[2,2,2,2],[2,1,1,2],[2,2,1,3],[2,2,1,3],\n",
    "               [3,2,1,3],[3,2,1,2],[3,1,2,2],[3,1,2,3],[3,2,2,1]])\n",
    "y = np.asarray([2,2,1,1,2,2,2,1,1,1,1,1,1,1,2])\n",
    "#################################################################################################\n",
    "level = 0\n",
    "D = []\n",
    "D.append(x)\n",
    "D.append(y)\n",
    "A = set(range(4))\n",
    "epsilon = 0.01\n",
    "def f(D,A,level = 0):\n",
    "    if level==0:\n",
    "        print('--------------------------------------level = ',str(0),'--------------------------------------------')\n",
    "    level = level + 1 \n",
    "    x = D[0]\n",
    "    y = D[1]\n",
    "    if len(np.unique(y))==1:\n",
    "        print('  '*level,'【      模型参数】在本Di分支中所有实例的标签一样，Label =',np.unique(y),'，在此终止，将会返回树T.')\n",
    "    else:\n",
    "        if len(A)==0:\n",
    "            print('A已经没有特征需要分析了，在此终止，将会返回树T.')\n",
    "        elif len(A)>0:\n",
    "            max_gain_col = np.argmax(cal_information_gain(x,y))\n",
    "            print('  '*level,'【      模型参数】：分裂第i =',max_gain_col,'个特征（i 属于 ',set(range(x.shape[1])),',可以产生的信息增益为',round(cal_information_gain(x,y)[max_gain_col],3))\n",
    "            if cal_information_gain(x,y)[max_gain_col] < epsilon:\n",
    "                print('  '*level,'特征产生的信息增益过小，在此终止，将会返回树T.')\n",
    "            else:\n",
    "                Di_x = []\n",
    "                Di_y = []\n",
    "                for i in np.unique(x[:,max_gain_col]):\n",
    "                    Di_x.append(x[x[:,max_gain_col] == i])\n",
    "                    Di_y.append(y[x[:,max_gain_col] == i])\n",
    "                for i in Di_y:\n",
    "                    max_count = -1\n",
    "                    max_count_class = -1\n",
    "                    for j in np.unique(i):\n",
    "                        count = list(i).count(j)\n",
    "                        if max_count<count:\n",
    "                            max_count = count\n",
    "                            max_count_class = j\n",
    "                    print('  '*level,'【子节点模型参数】：可以分裂出类别标签',max_count_class)\n",
    "                A.remove(max_gain_col)\n",
    "                for i in range(len(Di_x)):\n",
    "                    Di = [Di_x[i],Di_y[i]]\n",
    "                    print('>>'*level,'--------------------------------------level = ',str(level),'--------------------------------------------')\n",
    "                    print('  '*level,'【条件参数】：if x[ i,',max_gain_col,'] =',str(Di[0][0,max_gain_col]),':')\n",
    "                    print('  '*level,Di)\n",
    "                    f(Di,A,level)\n",
    "\n",
    "f(D,A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">上面的“条件参数”顺序是这样的：\n",
    "\n",
    "```python\n",
    "if x[ i, 2 ] = 1 :\n",
    "    Label = 1\n",
    "if x[ i, 2 ] = 2 :\n",
    "    if x[ i, 1 ] = 1 :\n",
    "        Label = 1\n",
    "    if x[ i, 1 ] = 1 :\n",
    "        Label = 2\n",
    "```\n",
    "至此，决策树就生成了！"
   ]
  }
 ],
 "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}