C4.5_without_pruning.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from scipy.io import loadmat\n",
    "from scipy.sparse import coo_matrix\n",
    "from sklearn.utils import shuffle\n",
    "from sklearn.model_selection import train_test_split\n",
    "import copy\n",
    "import pandas as pd\n",
    "from tqdm import tqdm\n",
    "from typing import Counter\n",
    "import math\n",
    "from sklearn.decomposition import PCA\n",
    "from sklearn.metrics import f1_score, recall_score, precision_score\n",
    "import sys\n",
    "import time\n",
    "\n",
    "\n",
    "def load_data():\n",
    "    data = loadmat(\"data/mnist_all.mat\")\n",
    "\n",
    "    # print(data.keys())\n",
    "\n",
    "    train_data = pd.DataFrame()\n",
    "    test_data = pd.DataFrame()\n",
    "\n",
    "    for i in range(10):\n",
    "        temp_df = pd.DataFrame(data[\"train\" + str(i)])\n",
    "        temp_df['label'] = i\n",
    "        train_data = train_data.append(temp_df)\n",
    "        temp_df = pd.DataFrame(data[\"test\" + str(i)])\n",
    "        temp_df['label'] = i\n",
    "        test_data = test_data.append(temp_df)\n",
    "\n",
    "    train_data = shuffle(train_data)\n",
    "    test_data = shuffle(test_data)\n",
    "\n",
    "    train_labels = np.array(train_data['label'])\n",
    "    test_labels = np.array(test_data['label'])\n",
    "\n",
    "    train_data = train_data.drop('label', axis=1)\n",
    "    test_data = test_data.drop('label', axis=1)\n",
    "    \n",
    "    train_data = np.array(train_data) / 255\n",
    "    test_data = np.array(test_data) / 255\n",
    "    \n",
    "    pca = PCA(0.95)\n",
    "    pca.fit(train_data)\n",
    "    train_data = pca.transform(train_data)\n",
    "    test_data = pca.transform(test_data)\n",
    "\n",
    "    return train_data, test_data, train_labels, test_labels\n",
    "\n",
    "\n",
    "X_train, X_test, y_train, y_test = load_data()\n",
    "\n",
    "X_train, X_valid, y_train, y_valid = train_test_split(\n",
    "    X_train, y_train, test_size=0.2, random_state=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 注意，经过PCA降维后，认为所有的特征都是连续值\n",
    "X = np.concatenate((X_train, X_valid), axis=0)\n",
    "y = np.concatenate((y_train, y_valid), axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(60000, 154) (60000,)\n"
     ]
    }
   ],
   "source": [
    "print(X.shape, y.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 在每个节点上，用于分割的特征、阈值、不等关系用一个三元组来表示，\n",
    "# 即（特征，阈值，不等关系），例子（第1维特征，0.338，'<='），元组可以作为dict的key\n",
    "\n",
    "# 当划分属性是连续值时，对应于 <= 和 > 两种情况，因此最后得到的决策树必然是一棵二叉树\n",
    "class C4_5_without_pruning:\n",
    "    def __init__(self, epsilon):\n",
    "        self.epsilon = epsilon\n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        self.tree = self.build_tree(X, y)\n",
    "\n",
    "        \n",
    "    def build_tree(self, X, y):\n",
    "        # 如果所有的X都属于一个y_i\n",
    "        temp_y = list(set(y))\n",
    "        if len(temp_y) == 1:\n",
    "            return temp_y[0]\n",
    "        \n",
    "        # 如果没有可以选择的划分属性？\n",
    "        # 不会存在这种情况，因为连续属性可以重复用作划分属性\n",
    "        \n",
    "        best_feature_index, threshold, best_gain_ratio = self.choose_best_feature_to_split(X, y)\n",
    "        \n",
    "        if best_gain_ratio < self.epsilon:\n",
    "            return Counter(y).most_common(1)[0][0]\n",
    "        \n",
    "        tree = {}\n",
    "        x1, y1, x2, y2 = self.split_data(X, y, best_feature_index, threshold)\n",
    "        tree[(best_feature_index, threshold, '<=')] = self.build_tree(x1, y1)\n",
    "        tree[(best_feature_index, threshold, '>')] = self.build_tree(x2, y2)\n",
    "        \n",
    "        return tree\n",
    "    \n",
    "    \n",
    "    def split_data(self, X, y, best_feature_index, threshold):\n",
    "        \n",
    "        x1, x2, y1, y2 = [], [], [], []\n",
    "        \n",
    "        for i in range(len(X)):\n",
    "            if X[i][best_feature_index] <= threshold:\n",
    "                x1.append(X[i])\n",
    "                y1.append(y[i])\n",
    "            else:\n",
    "                x2.append(X[i])\n",
    "                y2.append(y[i])\n",
    "        \n",
    "        return np.array(x1), np.array(y1), np.array(x2), np.array(y2)\n",
    "    \n",
    "        \n",
    "    def predict(self, x):\n",
    "        tree = self.tree\n",
    "        \n",
    "        while type(tree).__name__ == 'dict':\n",
    "            \n",
    "            for key in tree.keys():\n",
    "                if key[2] == '<=':\n",
    "                    key1 = key\n",
    "                elif key[2] == '>':\n",
    "                    key2 = key\n",
    "                    \n",
    "                \n",
    "            feature_index = key1[0]\n",
    "            threshold = key1[1]\n",
    "            \n",
    "            if x[feature_index] <= threshold:\n",
    "                tree = tree[key1]\n",
    "            elif x[feature_index] > threshold:\n",
    "                tree = tree[key2]\n",
    "\n",
    "        \n",
    "        if type(tree).__name__ == 'int64':\n",
    "            return tree\n",
    "        else:\n",
    "            pass\n",
    "            \n",
    "    \n",
    "    def calculate_gain_ratio(self, feature_index, X, y):\n",
    "        \n",
    "        values = []\n",
    "        for i in range(len(X)):\n",
    "            values.append(X[i][feature_index])\n",
    "        \n",
    "        values = list(set(values))\n",
    "        values.sort()\n",
    "        \n",
    "        best_gain_ratio = -sys.maxsize\n",
    "        best_threshold = None\n",
    "        \n",
    "        for i in range(len(values) - 1):\n",
    "            threshold = (values[i] + values[i + 1])/2\n",
    "            \n",
    "            # D1和D2的作用是分别计算 <=threshold 和 >threshold 的X的数量\n",
    "            D1, D2 = 0, 0\n",
    "            \n",
    "            # d1和d2的作用是分别计算D1和D2中各类标签（0-9）的数量\n",
    "            d1, d2 = [0]*10, [0]*10\n",
    "            for i in range(len(X)):\n",
    "                if X[i][feature_index] <= threshold:\n",
    "                    D1 += 1\n",
    "                    d1[y[i]] += 1\n",
    "                elif X[i][feature_index] > threshold:\n",
    "                    D2 += 1\n",
    "                    d2[y[i]] += 1\n",
    "                \n",
    "            # 下面计算H(D|A)\n",
    "            \n",
    "            part1 = 0 # <= threshold\n",
    "            part2 = 0 # > threshold\n",
    "            for i in range(10):\n",
    "                if d1[i] != 0:\n",
    "                    part1 += (d1[i]/D1)*np.log2(d1[i]/D1)\n",
    "                if d2[i] != 0:\n",
    "                    part2 += (d2[i]/D2)*np.log2(d2[i]/D2)\n",
    "            \n",
    "            part1 = part1*D1/len(X)\n",
    "            part2 = part2*D2/len(X)\n",
    "            H_D_A = -(part1 + part2)\n",
    "            \n",
    "            # 计算H(D)\n",
    "            C = [0]*10\n",
    "            for i in range(len(X)):\n",
    "                C[y[i]] += 1\n",
    "        \n",
    "            H_D = 0\n",
    "            for i in range(10):\n",
    "                if C[i] != 0:\n",
    "                    H_D += (C[i]/len(X))*np.log2(C[i]/len(X))\n",
    "        \n",
    "            info_gain = -H_D - H_D_A\n",
    "            \n",
    "            H_A_D = 0\n",
    "            if D1 != 0:\n",
    "                H_A_D += D1/len(X)*np.log2(D1/len(X))\n",
    "            if D2 != 0:\n",
    "                H_A_D += D2/len(X)*np.log2(D2/len(X))\n",
    "                \n",
    "            H_A_D = -H_A_D\n",
    "            \n",
    "            gain_ratio = info_gain / H_A_D\n",
    "            \n",
    "            if gain_ratio > best_gain_ratio:\n",
    "                best_threshold = threshold\n",
    "                best_gain_ratio = gain_ratio\n",
    "        \n",
    "        if best_threshold is None:\n",
    "            print('error in function calculate_gain_ratio')\n",
    "        \n",
    "        return best_gain_ratio, best_threshold\n",
    "    \n",
    "    \n",
    "    # 根据西瓜书：\n",
    "    # 需注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性\n",
    "    # 因此不需要记录哪些属性（特征）已经使用过了\n",
    "    def choose_best_feature_to_split(self, X, y):\n",
    "        feature_num = X.shape[1]\n",
    "        \n",
    "        best_feature_index = -1\n",
    "        best_gain_ratio = -sys.maxsize\n",
    "        best_feature_threshold = None\n",
    "        \n",
    "        for feature_index in range(feature_num):\n",
    "            gain_ratio, threshold = self.calculate_gain_ratio(feature_index, X, y)\n",
    "            \n",
    "            if gain_ratio > best_gain_ratio:\n",
    "                best_gain_ratio = gain_ratio\n",
    "                best_feature_index = feature_index\n",
    "                best_feature_threshold = threshold\n",
    "        \n",
    "        # 不会发生\n",
    "        if best_feature_index == -1:\n",
    "            pass\n",
    "        \n",
    "        return best_feature_index, best_feature_threshold, best_gain_ratio"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start training tree...\n",
      "finish training... time cost: 3440.8802881240845s\n"
     ]
    }
   ],
   "source": [
    "tree = C4_5_without_pruning(epsilon=0.1)\n",
    "\n",
    "print('start training tree...')\n",
    "start = time.time()\n",
    "tree.fit(X[:1000], y[:1000])\n",
    "end = time.time()\n",
    "print('finish training... time cost: {}s'.format(end-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "custom C4.5 without pruning test acc: 0.6173\n"
     ]
    }
   ],
   "source": [
    "result_list = []\n",
    "for i in range(len(X_test)):\n",
    "    result_list.append(tree.predict(X_test[i]))\n",
    "print('custom C4.5 without pruning test acc: {}'.format((sum(result_list == np.array(y_test)))/len(X_test)))"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}