最近给本科生当助教，出了一道实现决策树的题，还有一个预剪枝的题，自己也顺便实现一下。

我实现的这个决策树主要是参照了C4.5算法。没加入剪枝。实现的其实很简单，只针对离散特征，做了一个二叉决策树。也就是将所有特征先做one-hot，这样所有的特征都变成0和1了，然后对其进行二分。

原理其实很简单，选择一种划分指标，遍历所有的特征，找到最优划分特征，然后分割训练集，从剩余特征中删除当前的最优特征，然后分左子树和右子树递归地继续创建结点即可。无非是递归的终止条件，递归的终止条件有三点：

如果当前结点内所有的样本同属一类，则直接做叶子结点
如果当前深度达到最大深度，直接做叶子结点
如果无剩余特征可供划分，直接做叶子节点

第三题：实现决策树

实验内容：
使用LendingClub Safe Loans数据集：

实现信息增益、信息增益率、基尼指数三种划分标准
使用给定的训练集完成三种决策树的训练过程
计算三种决策树在最大深度为10时在训练集和测试集上的精度，查准率，查全率，F1值

在这部分，我们会实现一个很简单的二叉决策树

1. 读取数据

1
2
3
4
# 导入类库
import pandas as pd
import numpy as np
import json

1
2
# 导入数据
loans = pd.read_csv('data/lendingclub/lending-club-data.csv', low_memory=False)

数据中有两列是我们想预测的指标，一项是safe_loans，一项是bad_loans，分别表示正例和负例，我们对其进行处理，将正例的safe_loans设为1，负例设为-1，删除bad_loans这列

1
2
3
# 对数据进行预处理，将safe_loans作为标记
loans['safe_loans'] = loans['bad_loans'].apply(lambda x : +1 if x==0 else -1)
del loans['bad_loans']

我们只使用grade, term, home_ownership, emp_length这四列作为特征，safe_loans作为标记，只保留loans中的这五列

1
2
3
4
5
6
7
features = ['grade',              # grade of the loan
            'term',               # the term of the loan
            'home_ownership',     # home_ownership status: own, mortgage or rent
            'emp_length',         # number of years of employment
           ]
target = 'safe_loans'
loans = loans[features + [target]]

2. 划分训练集和测试集

1
2
3
4
5
6
from sklearn.utils import shuffle
loans = shuffle(loans, random_state = 34)

split_line = int(len(loans) * 0.6)
train_data = loans.iloc[: split_line]
test_data = loans.iloc[split_line:]

3. 特征预处理

可以看到所有的特征都是离散类型的特征，需要对数据进行预处理，使用one-hot编码对其进行处理。

one-hot编码的思想就是将离散特征变成向量，假设特征$A$有三种取值$\lbrace a, b, c\rbrace$，这三种取值等价，如果我们使用1,2,3三个数字表示这三种取值，那么在计算时就会产生偏差，有一些涉及距离度量的算法会认为，2和1离得近，3和1离得远，但这三个值应该是等价的，这种表示方法会造成模型在判断上出现偏差。解决方案就是使用一个三维向量表示他们，用$[1, 0, 0]$表示a，$[0, 1, 0]$表示b，$[0, 0, 1]$表示c，这样三个向量之间的距离就都是相等的了，任意两个向量在欧式空间的距离都是$\sqrt{2}$。这就是one-hot编码是思想。

pandas中使用get_dummies生成one-hot向量

1
2
3
def one_hot_encoding(data, features_categorical):
    '''
    Parameter