决策树（decision tree）是一种基本的分类与回归方法；其分类决策模型是一种对类进行分类的树形结构，由节点和有向边组成；节点除了根节点外，又分为内部节点和叶节点，前者表示一个特征，后者表示一个类 决策树学习的算法通常是一个递归选择最优特征的过程，比如：先选择一个最优的特征，将训练集分割成子集，如果其中有子集还未被正确分类，则继续根据该子集选择新的最优特征并对其分类，迭代上述步骤直至发生下述情况才结束：
- 当前数据集（子集）都被正确分类，或者说当前子集已经同属同一类（熵达到阈值、增益小于阈值）
- 特征为空，或者说没有合适的特征
因此根据特征值选择的策略不同，有不同的生成决策树的方法：
- ID3：以信息增益准则来选择特征，选择信息增益较大的特征
- C4.5/C5.0：以信息增益比准则来选择特征，选择信息增益率较大的特征
- CART：以基尼系数准则来选择特征，选择基尼系数较小的特征（分类树）、均方差较小的特征（回归树）
上述准则的公式可看《统计学习方法》，从公式中可看出，信息增益比是对信息增益的一种改进，进而克服前者对于选择取值较多的特征的偏好（使得泛化能力弱），但是后者则又带来了对于选择取值较少的特征的偏好（解决办法似乎有：先选择信息增益高于平均值的特征，然后再根据信息增益率来选择上述前提下最大的那个特征，反正计算信息增益率的时候也要先计算信息增益的）
ID3/C4.5/CART都是贪婪算法，只考虑当前条件达到局部最优，而无法达到全局最优，但近似于全局最优；以上三个算法不同点在于：
- ID3/C4.5只能处理分类问题，而CART可以处理分类/回归问题
- ID3/C4.5构建多叉树，而CART构建二叉树（因此其适合于）；因此当某个特征有多个取值时，前者则会产生多个分支，而后者会根据切点，将多个特征取值分割成两部分，变成两个分支；但是由于CART这次没有把该特征完全分开，所以后续还会继续选择该特征；不像ID3/C4.5那样，特征只参与一次节点的构建
- ID3不支持连续型数值，而C4.5/CART则支持（其思路都是将连续的特征离散化，差别在于前者是用信息增益率，而后者则是基尼系数）
- ID3不支持缺失值，而C4.5/CART则支持
- ID3不支持树剪枝，而C4.5/CART则支持
剪枝是为了克服用生成算法产生的决策树过拟合的问题，过拟合是由于在学习的过程中产生了过于复杂的决策树，使得其在训练集中表现的很好，但是泛化能力过低，因此需要对决策进行简化；以及用后来出的随机森林可以减少过拟合现象
决策树的剪枝可以分成两部分：预剪枝和后剪枝：
- 预剪枝是在决策树生成过程中，在划分数据集的时候，根据一些条件，比如：结点中样本数是否小于阈值或者基尼系数是否小于阈值，来判断是否要继续划分
- 后剪枝则是先生成一个完整的决策树，再从底往顶进行剪枝处理，消除多余的结点
对于数据集中的缺失值，要么采用一定方法进行缺失值补空，要么按照其所在的比例分配到各个结点中，进而方便后续的计算
决策树的优点如下(参考自决策树算法的Python实现):
- 易于理解和解释，甚至比线性回归更直观；
- 与人类做决策思考的思维习惯契合；
- 模型可以通过树的形式进行可视化展示；
- 可以直接处理非数值型数据，不需要进行哑变量的转化，甚至可以直接处理含缺失值的数据；
缺点如下:
- 对于有大量数值型输入和输出的问题，决策树未必是一个好的选择；
- 特别是当数值型变量之间存在许多错综复杂的关系，如金融数据分析；
- 决定分类的因素取决于更多变量的复杂组合时；
- 模型不够稳健，某一个节点的小小变化可能导致整个树会有很大的不同。
关于决策树更深的模型有软决策树、决策森林、随机森林等
未含剪枝的决策树CART算法的Python实现基本思路如下，基本参考《统计学习方法》：
- 对每个特征的每个切点分别计算基尼系数
- 选择基尼系数最小的切点将数据集分成两部分（二叉树）
- 迭代上述两个步骤，直到满足停止阈值才停止，最终形成一个决策树
Python代码如下：
class decision_tree:
# 根据公式5.24计算基尼系数
def calc_sub_Gini(self, y_sub):
gini_sub = []
for cls in set(y_sub):
gini_sub.append((np.sum(y_sub == cls) / len(y_sub)) ** 2)
return 1- sum(gini_sub)
# 选择最优特征和最优切点
def calc_best_feature(self, dataset, label):
feature_gini = {}
for feature in range(dataset.shape[1]):
arr_len = len(np.unique(dataset[:,feature]))
if (arr_len == 1):
# 特征都为同一个数值，无切点（或者说该特征已被用尽）
continue
elif (arr_len == 2):
# 二类分类问题
feature_arr = np.unique(dataset[:,feature])[0]
split1 = dataset[:,feature] == feature_arr
split2 = dataset[:,feature] != feature_arr
gini = sum(split1) / len(split1) * self.calc_sub_Gini(label[split1]) + sum(split2) / len(split2) * self.calc_sub_Gini(label[split2])
feature_gini[(feature, feature_arr)] = gini
else:
# 多类分类问题
for feature_arr in set(dataset[:,feature]):
split1 = dataset[:,feature] == feature_arr
split2 = dataset[:,feature] != feature_arr
gini = sum(split1) / len(split1) * self.calc_sub_Gini(label[split1]) + sum(split2) / len(split2) * self.calc_sub_Gini(label[split2])
feature_gini[(feature, feature_arr)] = gini
if (len(feature_gini) == 0):
# 即该数据集的特征值为空了
return None
else:
# 取最小基尼系数的特征值作为切点
best_feature = min(feature_gini, key = feature_gini.get)
return best_feature
# 分割数据集到两个（左右）子节点中
def split_dat(self, dataset, label, best_feature):
feature = best_feature[0]
feature_value = best_feature[1]
left_label = label[dataset[:,feature] == feature_value]
right_label = label[dataset[:,feature] != feature_value]
left_dat = dataset[dataset[:,feature] == feature_value,:]
right_dat = dataset[dataset[:,feature] != feature_value,:]
return left_label,right_label,left_dat,right_dat
# 生成决策树
def create_Tree(self, dataset, label):
# 样本属于同一类，分配到单节点，函数停止
if (len(np.unique(label)) == 1):
return label[0]
best_feature = self.calc_best_feature(dataset, label)
# 没有更多的特征，特征已用完，函数停止
if (best_feature == None):
label_number = {}
label_number = dict(Counter(label))
return max(label_number, key=label_number.get)
left_label,right_label,left_dat,right_dat = self.split_dat(dataset, label, best_feature)
# 用字典构建树，并迭代函数
tree = {best_feature:{}}
tree[best_feature]["left"] = self.create_Tree(left_dat, left_label)
tree[best_feature]["right"] = self.create_Tree(right_dat, right_label)
return tree
# 通过已构建的决策树预测
def predict(self, test, tree):
for k,v in tree.items():
if (test[k[0]] == k[1]):
left_leaf = v["left"]
if (type(left_leaf) == dict):
return self.predict(test, v["left"])
else:
return v["left"]
else:
right_leaf = v["right"]
if (type(right_leaf) == dict):
return self.predict(test, v["right"])
else:
return v["right"]先以书中表5.1的训练数据集测试下：
dataset = pd.read_table("tree.txt")
dataset = np.array(dataset)
X = dataset[:,:-1]
y = dataset[:,-1]
dt = decision_tree()
res = dt.create_Tree(X,y)看下字典中储存的树信息,（2,1）代表第3个特征中1值，left:1代表左枝的标签为1
res
Out[177]: {(2, 1): {'left': 1, 'right': {(1, 1): {'left': 1, 'right': 2}}}}然后再结合测试数据集MNIST（数字识别），用上述决策树代码实现如下：
读入测试数据，并按照20%分割训练集和测试集
dataset = pd.read_csv("train.csv")
dataset = np.array(dataset)
dataset[:,1:][dataset[:,1:] != 0] = 1
label = dataset[:,0]
train_dat, test_dat, train_label, test_label = train_test_split(dataset[:,1:], label, test_size = 0.2, random_state = 123456)构建决策树，并计算测试误差
dtree = decision_tree()
dt = dtree.create_Tree(train_dat, train_label)
error = 0
for i in range(len(test_dat)):
if (dtree.predict(test_dat[i], dt) != test_label[i]):
error += 1
print(error / len(test_label) * 100)测试误差为：13.5%，跟之前的朴素贝叶斯的结果差不多，但是这个是未剪枝的，如果按照成熟的决策树算法，应该误差会再小一点
参考资料：
「决策树」| Part4—CART决策树
Python实现决策树2(CART分类树及CART回归树)
决策树之CART算法原理及python实现
机器学习|决策树算法及实现
统计学习方法|决策树原理剖析及实现
「决策树」| Part5—Python实现CART决策树
本文出自于http://www.bioinfo-scrounger.com转载请注明出处