决策树/05. 连续值和缺失值.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 处理连续属性\n",
    "\n",
    "如果某个属性的取值是连续值，不能直接使用连续属性的可取值来对节点进行划分，通常采用 **二分法**（bi-partition）对连续属性进行处理。\n",
    "\n",
    "假设数据集 D 的 a 属性为连续属性，它有 n 个不同的取值，我们将其从小到大排序，得到 $\\{a^1, a^2, ..., a^n\\}$，对每两个相邻的点，我们取其中位点作为候选划分点，这样就得到了 n-1 个候选划分点：\n",
    "\n",
    "$$\n",
    "T_a = \\{ \\frac{a^i + a^{i+1}}{2} | i \\leqslant i \\leqslant n-1 \\}\n",
    "$$\n",
    "\n",
    "我们从中考察每一个划分点，假设划分点为 t，它可以将数据集划分为 $D_t^-$ 和 $D_t^+$，$D_t^-$ 表示属性 a 小于等于 t 的样本集合，$D_t^+$ 表示属性 a 大于 t 的样本集合。使用属性 a 上的划分点 t 对数据集进行划分后的信息熵可以记为：\n",
    "\n",
    "$$\n",
    "Ent(D_{a,t}) = \\frac{|D_t^-|}{|D|} Ent(D_t^-) + \\frac{|D_t^+|}{|D|} Ent(D_t^+)\n",
    "$$\n",
    "\n",
    "相应的信息增益为：\n",
    "\n",
    "$$\n",
    "Gain(D,a,t) = Ent(D) - Ent(D_{a,t})\n",
    "$$\n",
    "\n",
    "可以看出 t 的取值不同，划分后的信息熵也不同，信息增益自然也不同，我们希望划分后的信息增益越大越好，所以可以把信息增益最大值作为连续属性 a 的信息增益。\n",
    "\n",
    "$$\n",
    "Gain(D,a) = \\mathop \\max_{t \\in T_a} Gain(D,a,t)\n",
    "$$\n",
    "\n",
    "处理连续属性和处理离散属性的根本原理是一样的，都是选择信息增益最大的划分属性对数据集进行划分，不过在计算连续属性的信息增益时，还要计算合适的划分点。另外，还要注意一点，离散属性一当被选为划分属性，后代节点就不能再使用该属性进行划分，而连续属性却可以，譬如在父节点上使用了 $a \\leqslant 10$，子节点上还可以进一步使用 $a \\leqslant 5$。\n",
    "\n",
    "### 处理缺失属性\n",
    "\n",
    "我们有时候会遇到不完整的数据集，样本的某些属性值由于一些原因缺失了，这样的数据如果丢弃掉显然是很可惜的，缺失值处理是机器学习算法中一个很重要的问题。在决策树算法中，关键是找到最优的划分属性，可以使用信息增益或基尼指数等手段，不过前面学习的内容都是基于完整的数据集来划分的，有没有办法在属性缺失的情况下划分属性呢？\n",
    "\n",
    "假设有数据集 $D$ 和 属性 $a$，属性 $a$ 在某些样本上有缺失，我们剔除掉那些属性 $a$ 缺失的样本得到一个新数据集 $\\tilde{D}$，这样可以计算出新数据集在属性 $a$ 上的信息增益：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Gain(\\tilde{D}, a) &= Ent(\\tilde{D}) - \\sum_{v=1}^{V} \\frac{|\\tilde{D}^v|}{|\\tilde{D}|} Ent(\\tilde{D}^v) \\\\\n",
    "&= - \\sum_{k=1}^{\\left| \\mathcal{Y} \\right|} \\frac{|\\tilde{D}_k|}{|\\tilde{D}|} log_2 \\frac{|\\tilde{D}_k|}{|\\tilde{D}|} - \\sum_{v=1}^{V} \\frac{|\\tilde{D}^v|}{|\\tilde{D}|} Ent(\\tilde{D}^v)\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "$\\tilde{D}_k（k = 1,2,...,|\\mathcal{Y}|）$ 表示在数据集 $\\tilde{D}$ 中一种有 $\\mathcal{Y}$ 个类别，而 $\\tilde{D}^v（v = 1,2,...,V）$ 表示属性 a 一共有 V 个不同的取值。\n",
    "\n",
    "这里得到的是在数据集 $\\tilde{D}$ 上属性 a 的信息增益，可以根据完整样本的占比来推算在数据集 $D$ 上的信息增益：\n",
    "\n",
    "$$\n",
    "Gain(D, a) = \\frac{|\\tilde{D}|}{|D|} Gain(\\tilde{D}, a)\n",
    "$$\n",
    "\n",
    "通过上面的计算方法，可以得到每个属性的信息增益，选择信息增益最大的属性来进行划分，譬如该属性有 3 种不同的取值，将得到 3 个决策子树，每个子树对应一个相应的子集。但是，如果某个样本该属性值未知，这个样本该放入哪个子树呢？一种常见的处理方式是将其同时放入三个子树，不过要分别赋予不同的权重，为样本赋予权重之后，信息增益的计算方式也需要稍微调整下（假设样本 $x$ 的权重为 $w_x$）：\n",
    "\n",
    "$$\n",
    "\\left\\{\n",
    "\\begin{align}\n",
    "\\frac{|\\tilde{D}|}{|D|} &\\Longrightarrow \\frac{\\sum_{x \\in \\tilde{D}} w_x}{\\sum_{x \\in D} w_x} \\\\\n",
    "\\frac{|\\tilde{D}_k|}{|\\tilde{D}|} &\\Longrightarrow \\frac{\\sum_{x \\in \\tilde{D}_k} w_x}{\\sum_{x \\in \\tilde{D}} w_x} \\\\\n",
    "\\frac{|\\tilde{D}^v|}{|\\tilde{D}|} &\\Longrightarrow \\frac{\\sum_{x \\in \\tilde{D}^v} w_x}{\\sum_{x \\in \\tilde{D}} w_x}\n",
    "\\end{align}\n",
    "\\right.\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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}