Decision_tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class decision_tree:\n",
    "    # 根据公式5.24计算基尼系数\n",
    "    def calc_sub_Gini(self, y_sub):\n",
    "        gini_sub = []\n",
    "        for cls in set(y_sub):\n",
    "            gini_sub.append((np.sum(y_sub == cls) / len(y_sub)) ** 2)\n",
    "        return 1- sum(gini_sub)\n",
    "\n",
    "    # 选择最优特征和最优切点\n",
    "    def calc_best_feature(self, dataset, label):\n",
    "        feature_gini = {}\n",
    "        for feature in range(dataset.shape[1]):\n",
    "            arr_len = len(np.unique(dataset[:,feature]))\n",
    "            if (arr_len == 1):\n",
    "                # 特征都为同一个数值，无切点（或者说该特征已被用尽）\n",
    "                continue\n",
    "            elif (arr_len == 2):\n",
    "                # 二类分类问题\n",
    "                feature_arr = np.unique(dataset[:,feature])[0]\n",
    "                split1 = dataset[:,feature] == feature_arr\n",
    "                split2 = dataset[:,feature] != feature_arr\n",
    "                gini = sum(split1) / len(split1) * self.calc_sub_Gini(label[split1]) + sum(split2) / len(split2) * self.calc_sub_Gini(label[split2])\n",
    "                feature_gini[(feature, feature_arr)] = gini \n",
    "            else:\n",
    "                # 多类分类问题\n",
    "                for feature_arr in set(dataset[:,feature]):\n",
    "                    split1 = dataset[:,feature] == feature_arr\n",
    "                    split2 = dataset[:,feature] != feature_arr\n",
    "                    gini = sum(split1) / len(split1) * self.calc_sub_Gini(label[split1]) + sum(split2) / len(split2) * self.calc_sub_Gini(label[split2])\n",
    "                    feature_gini[(feature, feature_arr)] = gini\n",
    "        if (len(feature_gini) == 0):\n",
    "            # 即该数据集的特征值为空了\n",
    "            return None\n",
    "        else:\n",
    "            # 取最小基尼系数的特征值作为切点\n",
    "            best_feature = min(feature_gini, key = feature_gini.get)\n",
    "            return best_feature\n",
    "\n",
    "    # 分割数据集到两个（左右）子节点中\n",
    "    def split_dat(self, dataset, label, best_feature):\n",
    "        feature = best_feature[0]\n",
    "        feature_value = best_feature[1]\n",
    "        \n",
    "        left_label = label[dataset[:,feature] == feature_value]\n",
    "        right_label = label[dataset[:,feature] != feature_value]\n",
    "        left_dat = dataset[dataset[:,feature] == feature_value,:]\n",
    "        right_dat = dataset[dataset[:,feature] != feature_value,:]\n",
    "        \n",
    "        return left_label,right_label,left_dat,right_dat\n",
    "\n",
    "    # 生成决策树\n",
    "    def create_Tree(self, dataset, label):\n",
    "        # 样本属于同一类，分配到单节点，函数停止\n",
    "        if (len(np.unique(label)) == 1):\n",
    "            return label[0]\n",
    "        \n",
    "        best_feature = self.calc_best_feature(dataset, label)\n",
    "        \n",
    "        # 没有更多的特征，特征已用完，函数停止\n",
    "        if (best_feature == None):\n",
    "            label_number = {}\n",
    "            label_number = dict(Counter(label))\n",
    "            return max(label_number, key=label_number.get) \n",
    "    \n",
    "        left_label,right_label,left_dat,right_dat = self.split_dat(dataset, label, best_feature)\n",
    "        \n",
    "        # 用字典构建树，并迭代函数\n",
    "        tree = {best_feature:{}}\n",
    "        tree[best_feature][\"left\"] = self.create_Tree(left_dat, left_label)\n",
    "        tree[best_feature][\"right\"] = self.create_Tree(right_dat, right_label)\n",
    "    \n",
    "        return tree\n",
    "\n",
    "    # 通过已构建的决策树预测\n",
    "    def predict(self, test, tree):\n",
    "        for k,v in tree.items():\n",
    "            if (test[k[0]] == k[1]):\n",
    "                left_leaf = v[\"left\"]\n",
    "                if (type(left_leaf) == dict):\n",
    "                    return self.predict(test, v[\"left\"])\n",
    "                else:\n",
    "                    return v[\"left\"]\n",
    "            else:\n",
    "                right_leaf = v[\"right\"]\n",
    "                if (type(right_leaf) == dict):\n",
    "                    return self.predict(test, v[\"right\"])\n",
    "                else:\n",
    "                    return v[\"right\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 训练集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "先以书中表5.1的训练数据集测试下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "dataset = np.array(dataset)\n",
    "X = dataset[:,:-1]\n",
    "y = dataset[:,-1]\n",
    "dt = decision_tree()\n",
    "res = dt.create_Tree(X,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "再结合测试数据集MNIST（数字识别），用上述决策树代码实现如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = pd.read_csv(\"train.csv\")\n",
    "dataset = np.array(dataset)\n",
    "dataset[:,1:][dataset[:,1:] != 0] = 1\n",
    "label = dataset[:,0]\n",
    "\n",
    "train_dat, test_dat, train_label, test_label = train_test_split(dataset[:,1:], label, test_size = 0.2, random_state = 123456"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "构建决策树，并计算测试误差"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dtree = decision_tree()\n",
    "dt = dtree.create_Tree(train_dat, train_label)\n",
    "error = 0\n",
    "for i in range(len(test_dat)):\n",
    "    if (dtree.predict(test_dat[i], dt) != test_label[i]):\n",
    "        error += 1\n",
    "print(error / len(test_label) * 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "测试误差为：13.5%"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}