DecisionTree/ID3_decision_tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 决策树分类算法\n",
    "决策树学习包括3个步骤：\n",
    "\n",
    "* 特征选择\n",
    "* 决策树的生成\n",
    "* 决策树的修剪\n",
    "\n",
    "决策树的特征选择通常采用特征增益或特征增益比进行选择\n",
    "\n",
    "决策树的生成算法通常有Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法\n",
    "\n",
    "决策树的修剪往往通过极小化决策树的整体损失函数或代价函数进行，目的是为了减小决策树的过拟合问题，增大其泛化能力\n",
    "\n",
    "## 信息熵\n",
    "熵是表示随机变量不确定性的度量，设 X 是一个取有限个值的离散随机变量，其概率分布为：\n",
    "$$ P(X = x_i) = p_i,   i=1,2,...,n $$\n",
    "\n",
    "则随机变量X的熵为：\n",
    "$$ H(X) = -\\sum_{i=1}^{n}p_ilogp_i $$\n",
    "\n",
    "熵越大，随机变量的不确定性就越大，且\n",
    "$$ 0\\leq H(p)\\leq logn $$\n",
    "\n",
    "## 条件熵\n",
    "条件熵 $ H(Y|X) $ 表示在已知随机变量X的条件下随机变量Y的不确定性，定义为X给定的条件下Y的条件概率分布的熵对X的数学期望\n",
    "$$ H(Y|X) = \\sum_{i=1}^{n}p_iH(Y|X=x_i) $$\n",
    "\n",
    "这里，$ p_i = p(X=x_i), i=1,2,...,n $\n",
    "\n",
    "## 信息增益\n",
    "信息增益表示得知特征X的信息而使得Y的信息的不确定性减少的程度\n",
    "\n",
    "特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定的条件下D的经验条件熵H(D|A）之差，即：\n",
    "$$ g(D,A)=H(D)-H(D|A) $$\n",
    "\n",
    "一般的，熵H(Y)与条件熵H(Y|X)的差称为互信息，决策树学习中的信息增益等价于训练数据中类与特征的互信息\n",
    "\n",
    "## 信息增益比\n",
    "使用信息增益选择特征会使算法在选择特征时更倾向于选择特征取值个数多的特征，为了解决这一问题，可以采用信息赠增益比\n",
    "\n",
    "特征A对训练数据D的信息增益比$ g_r(D,A) $为A对D的信息增益g(D,A)与训练数据集D关于特征A的值的熵$ H_A(D) $的比\n",
    "$$ g_r(D,A)= \\frac{g(D,A)}{H_A(D)} $$\n",
    "$$ H_A(D) = -\\sum_{i=1}^{n}\\frac{|D_i|}{|D|}log_2\\frac{|D_i|}{|D|} $$\n",
    "n是特征A取值的个数\n",
    "\n",
    "\n",
    "## 创建决策树模型类\n",
    "该决策树生成算法使用 ID3 算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ID3_Decision_Tree():\n",
    "    def __init__(self):\n",
    "        self.ID3_Tree = None\n",
    "        \n",
    "    def fit(self, data_set, features_name):\n",
    "        \"\"\"训练\"\"\"\n",
    "        self.ID3_Tree = self.generate_tree(data_set, features_name)\n",
    "        return self.ID3_Tree\n",
    "    \n",
    "    def predict(self, test_data, test_features_name):\n",
    "        \"\"\"预测\"\"\"\n",
    "        model = self.ID3_Tree\n",
    "        result = []\n",
    "        for test_example in test_data:\n",
    "            example_cate = self.classify(model, test_example, test_features_name)\n",
    "            result.append(example_cate)\n",
    "        return result\n",
    "    \n",
    "    def classify(self, ID3_Tree, test_example, test_features_name,):\n",
    "        \"\"\"辅助分类的函数\"\"\"\n",
    "        if ID3_Tree is None:\n",
    "            raise NameError(\"未经过训练，没有可用的树\")\n",
    "        first_key = list(ID3_Tree.keys())[0]\n",
    "        second_dict = ID3_Tree[first_key]\n",
    "        feature_index = test_features_name.index(first_key)\n",
    "    \n",
    "        for key in second_dict.keys():\n",
    "            if test_example[feature_index] == key:\n",
    "                if type(second_dict[key]).__name__ == 'dict':\n",
    "                    example_category = self.classify(second_dict[key], test_example, test_features_name)\n",
    "                else:\n",
    "                    example_category = second_dict[key]\n",
    "        return example_category\n",
    "        \n",
    "    def cal_shannon_entropy(self, data_set):\n",
    "        \"\"\"计算一个数据集的信息熵\"\"\"\n",
    "        label_counts = {}\n",
    "        data_len = len(data_set)\n",
    "\n",
    "        for example in data_set:\n",
    "            label = example[-1]\n",
    "            if label in label_counts.keys():\n",
    "                label_counts[label] += 1.0\n",
    "            else:\n",
    "                label_counts[label] = 1.0\n",
    "\n",
    "        probs = np.asarray(list(label_counts.values())) / data_len\n",
    "        shannon_entropy = - np.sum(probs * np.log2(probs))\n",
    "\n",
    "        return shannon_entropy\n",
    "    \n",
    "    def split_data_set(self, data_set, axis):\n",
    "        \"\"\"根据给定的轴进行数据集划分\"\"\"\n",
    "        column_single_value = set([example[axis] for example in data_set])\n",
    "        all_sub_data = []\n",
    "        for value in column_single_value:\n",
    "            sub_data = []\n",
    "            for example in data_set:\n",
    "                sub_example = []\n",
    "                if example[axis] == value:\n",
    "                    sub_example.extend(example[:axis])\n",
    "                    sub_example.extend(example[axis+1:])\n",
    "                    sub_data.append(sub_example)\n",
    "            all_sub_data.append(sub_data)\n",
    "        return all_sub_data, column_single_value\n",
    "    \n",
    "    def choose_best_feature(self, data_set):\n",
    "        \"\"\"根据信息增益选择最好的特征进行数据集的划分\"\"\"\n",
    "        # 减一是因为数据集最后一列为标签，不是特征\n",
    "        features_len = len(data_set[0]) - 1\n",
    "        data_len = len(data_set)\n",
    "        data_set_entropy = self.cal_shannon_entropy(data_set)\n",
    "\n",
    "        all_feautre_info_gain = np.zeros(features_len)\n",
    "\n",
    "        for i in range(features_len):\n",
    "            all_sub_data, _ = self.split_data_set(data_set, i)\n",
    "            conditional_entropy = 0.0      \n",
    "            for sub_data in all_sub_data:\n",
    "                sub_prob = len(sub_data) / data_len\n",
    "                sub_enropy = self.cal_shannon_entropy(sub_data)\n",
    "                conditional_entropy += sub_prob * sub_enropy\n",
    "            feature_info_gain = data_set_entropy - conditional_entropy\n",
    "            all_feautre_info_gain[i] = feature_info_gain\n",
    "\n",
    "        best_feature_idx = np.argmax(all_feautre_info_gain)\n",
    "\n",
    "        return all_feautre_info_gain, best_feature_idx\n",
    "    \n",
    "    def vote(self, categories):\n",
    "        \"\"\"对多个类别进行投票多数表决\"\"\"\n",
    "        cate_count = {}\n",
    "\n",
    "        for cate in categories:\n",
    "            if cate in cate_count.keys():\n",
    "                cate_count[cate] += 1\n",
    "            else:\n",
    "                cate_count[cate] = 1\n",
    "\n",
    "        voted_category = max(cate_count.items(), key=lambda x: x[1])[0]\n",
    "        return voted_category\n",
    "\n",
    "    def generate_tree(self, data_set, features_name):\n",
    "        \"\"\"生成决策树\"\"\"\n",
    "        categories = [example[-1] for example in data_set]\n",
    "        if categories.count(categories[0]) == len(categories):    # 都是同一个类别的时候停止划分\n",
    "            return categories[0]\n",
    "        if len(data_set[0]) == 1:    # 划分完了所有的特征，停止\n",
    "            return self.vote(categories)\n",
    "\n",
    "        _, best_feature_id = self.choose_best_feature(data_set)\n",
    "\n",
    "        best_feature_name = features_name[best_feature_id]\n",
    "\n",
    "        ID3_tree = {best_feature_name: {}}\n",
    "\n",
    "        del features_name[best_feature_id]\n",
    "\n",
    "        all_sub_data, all_unique_values = self.split_data_set(data_set, best_feature_id)\n",
    "\n",
    "        for unique_value, sub_data in zip(all_unique_values, all_sub_data):\n",
    "            sub_featrues_name = features_name[:]    # 这样赋值 sub_features_name 和 featrues_name指向的是不同对象\n",
    "            ID3_tree[best_feature_name][unique_value] = self.generate_tree(sub_data, sub_featrues_name)\n",
    "\n",
    "        return ID3_tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 简单测试"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 实例化模型\n",
    "id3_tree_object = ID3_Decision_Tree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 创建训练集\n",
    "data_set = [[1, 1, 'yes'],\n",
    "            [1, 1, 'yes'],\n",
    "            [1, 0, 'no'],\n",
    "            [0, 1, 'no'],\n",
    "            [0, 1, 'no']]\n",
    "feature_name = ['color', 'weight']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'color': {0: 'no', 1: {'weight': {0: 'no', 1: 'yes'}}}}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 训练生成决策树\n",
    "id3_tree_object.fit(data_set, feature_name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 创建测试集\n",
    "test_data = [[0, 0],\n",
    "             [0, 1],\n",
    "             [1, 1]]\n",
    "test_feature_name = ['color', 'weight']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['no', 'no', 'yes']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 使用之前的决策树进行分类\n",
    "id3_tree_object.predict(test_data, test_feature_name)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 模型的剪枝尚未编写，后面会继续更新"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}