15-基于信息熵的决策划分.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "决策树中基于信息熵的划分"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src='./img/11.jpg', width=600, height = 400>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%html\n",
    "<img src='./img/11.jpg', width=600, height = 400>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "# x, y 数据的样本， d指向的哪一列（对于哪个特征进行划分呢）， v是基于哪个值来进行划分（哪个候选点来进行划分）\n",
    "def split(x, y, d, v):\n",
    "    index_l = (x[:, d] <= v)\n",
    "    index_r = (x[:, d] > v)\n",
    "    # 使用fancy indexing来进行取值\n",
    "    return x[index_l], x[index_r], y[index_l], y[index_r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义我们的信息熵\n",
    "from collections import Counter\n",
    "from math import log\n",
    "def Ent(y):\n",
    "    result = 0;\n",
    "    counter = Counter(y)  # 计算每个y取值对应的概率\n",
    "    for num in counter.values():\n",
    "        p = num / len(y) # 用出现的次数/总的长度\n",
    "        result += -p * log(p) # 进行求和的操作\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def try_split(x, y):\n",
    "    best_ent = float('inf')  # 定义我们最好的值是无穷大\n",
    "    best_d, best_v = -1, -1  # 看我们最终要基于哪一列进行划分，且它对应信息熵最小的划分value是多少\n",
    "    for d in range(x.shape[1]):  # 基于我们的列数进行探索\n",
    "        sorted_index = np.argsort(x[:, d]) # 对我们的第d列进行下标的排序\n",
    "        for i in range(len(x) -1): # 对第d列的每行数据进行处理\n",
    "            v = (x[sorted_index[i], d] + x[sorted_index[i+1], d]) / 2 # 取平均值\n",
    "            x_l, x_r, y_l, y_r = split(x, y, d, v)\n",
    "            ent = Ent(y_l) + Ent(y_r)\n",
    "            if ent < best_ent: # 进行迭代处理\n",
    "                best_ent, best_d, best_v = ent, d, v\n",
    "    return best_ent, best_d, best_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 西瓜书中密度和含糖数据的准备\n",
    "x = [\n",
    "        [0.697, 0.460],\n",
    "        [0.774, 0.376],\n",
    "        [0.634, 0.264],\n",
    "        [0.608, 0.318],\n",
    "        [0.556, 0.215],\n",
    "        [0.403, 0.237],\n",
    "        [0.481, 0.149],\n",
    "        [0.437, 0.211],\n",
    "        [0.666, 0.091],\n",
    "        [0.243, 0.267],\n",
    "        [0.245, 0.057],\n",
    "        [0.343, 0.099],\n",
    "        [0.639, 0.161],\n",
    "        [0.657, 0.198],\n",
    "        [0.360, 0.370],\n",
    "        [0.593, 0.042],\n",
    "        [0.719, 0.103]\n",
    "     ]\n",
    "x = np.array(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "y = [1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0]\n",
    "y = np.array(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best_ent =  0.2703100720721096\n",
      "best_d =  1\n",
      "best_v =  0.126\n"
     ]
    }
   ],
   "source": [
    "best_ent, best_d, best_v = try_split(x, y)\n",
    "print(\"best_ent = \" , best_ent)\n",
    "print(\"best_d = \" , best_d)\n",
    "print(\"best_v = \" , best_v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "说明我们是先是按第一列来进行划分，这与西瓜书中的划分是一样，西瓜书中含糖率信息增益是大于密度的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x_l, x_r, y_l, y_r = split(x, y, best_d, best_v)\n",
    "Ent(y_l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.2703100720721096"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Ent(y_r)  # 说明我们的信息熵在y_r部分还能进行数据的划分呢"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "进行第二次划分"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best_ent =  0.17851484105136778\n",
      "best_d =  0\n",
      "best_v =  0.3815\n"
     ]
    }
   ],
   "source": [
    "best_ent, best_d, best_v = try_split(x_r, y_r)\n",
    "print(\"best_ent = \" , best_ent)\n",
    "print(\"best_d = \" , best_d)\n",
    "print(\"best_v = \" , best_v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "依次进行下去"
   ]
  }
 ],
 "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
}