当前位置 博文首页 > jcLee95的博客：机器学习 - [源码实现决策树小专题]决策树如何分
【导读】：节点的分裂是决策树建立重要的一个环节。本文在实现求解最佳特征和划分数据集的基础上带领大家实现如何实现决策树的分裂以拓展节点、最终建立一颗分类树。
【下一篇博文】：机器学习 - 决策树学习中如何进行分类预测（Python实现）该文在以本文训练得到的决策树为基础，源码实现数据的预测。
本文将用到其它的一些函数，这里将只展示它们的接口。
这写函数也是在假设不允许调用sklearn等现成及其学习库的前提下，我自己写的。
具体实现方法以及教程请依据链接跳转到对应的博文进行查看。
def impurity(anArray, impurity_t="entropy"):
"""
计算混杂度
【我的博客地址】:https://blog.csdn.net/qq_28550263/article/details/114883862
Parameters
----------
anArray： an Array like object，由某特征依次对应每条数据下的取值构成。
impurity_t： str，表示混杂度的度量方式，只能是{"entropy","gini"}中的一个。
Return
result: float
最终计算好的不纯度 impurity 的数值。
"""
def dividing_data_set(date_set,node_feature,node_feature_value):
"""
划分数据集
【我的博客地址】:https://blog.csdn.net/qq_28550263/article/details/114892718
整个划分方法的思想是"记录索引-重索引"。简而言之就是先记住特征取值为指定取值的索引号，然
后依据记录索引号保对其它特征下同索引号的元素进行保留。最终实现留下当前划分数据条的目的。
Parameters
----------
date_set： "dict"结构的数据集，其中键为”labels“的键值对对应为标签集（源于x_train），其余
的对应为特征取值键值对（源于y_train）。
node_feature：可以是num、str等类型，但是必须和date_set中的键的类型保持一致。表示需要划分
数据集的节点处对应的特征名。
node_feature_value：是对应与 node_feature 的一个特定取值。
Returns
-------
result : dict
返回子数据集字典，其形式与date_set保持一致。其中键`labels`对应的值类似是子标签集数组。
"""
def gain(impurity_t, impurity_before_divide, data_set, probable_feature):
"""
计算信息增益
【我的博客地址】:https://blog.csdn.net/qq_28550263/article/details/114891368
需要传入数据集划分前的不纯度、划分数据集所依赖特征对应的取值数组。考虑到在同一个节点测试不同子特征增益时都有用
到划分前的不纯度，为了提升运行效率故在gain()外计算好该节点分裂前的不纯度后再传入gain()函数。其中数据集划分前的
熵就是划分前的标签集labels的熵。其中按某特征划分后的不确定度，为依该特征各个取值划分的子数据集的中的标签集（即
该特征划分完后所有的子标签集）的不确定度总和。
Parameters
----------
impurity_t: str,不纯度的度量方式，只能是{"entropy","gini"}中的一个。
impurity_before_divide: float，表示数据集划分前的不纯度。
data_set： dict，划分前的数据集。
probable_feature: str，用于划分数据集的特征。
Return
------
result: float，表征信息增益值。
"""
def gain_rate(impurity_t, impurity_before_divide, data_set, probable_feature):
"""
计算信息增益率
【我的博客地址】:https://blog.csdn.net/qq_28550263/article/details/114891368
相对于信息增益的计算，信息增益率还要求解出由于该特征的不同取值带来的不确度。
- 若由于特征取值带来的不确定度为0，说明无特征取值连续化影响，直接返回信息增益；
- 若特征取值带来的不确定度不是0，则使用信息增益除以特征取证带来的不确定度。
Parameters
----------
impurity_t: str,不纯度的度量方式，只能是{"entropy","gini"}中的一个。
impurity_before_divide: float，表示数据集划分前的不纯度。
data_set： dict，划分前的数据集。
probable_feature: str，用于划分数据集的特征。
Return
------
result: float，表征信息增益值。
"""
def best_feature(impurity_t,date_set):
"""
求取节点处的最佳特征
【我的博客地址】:https://blog.csdn.net/qq_28550263/article/details/114891368
Parameters
----------
date_set: dict，与某个节点处的对应的数据集
Return
------
result： str，数据集date_set所属节点处可用于分裂的最佳特征
"""
import random
from collections import Counter
class Selector(object):
"""
选择器
Parameters
----------
labels: an Array-like object
"""
def majorityLabel(self):
"""
选择出现次数最多的元素
Return
------
result: labels中出现次数最多的那个成员
"""
def maxProbability_elem(self):
"""
有元素权重随机选择（元素随机）
Return
------
result: labels 中的某个成员
"""
def maxProbability_class(self):
"""
无元素权重随机选择（元素类随机）
Return
------
result: labels 中的某个成员
"""
本节讨论节点如何分裂与何时停止。
决策树的建立从根节点开始，并“缓慢地”逐个节点依次建立。总的说来建立一个节点需要做这两件大事：
下面我们分别围绕这两大事件主题讨论之。
请看示意图：
（1）对于根节点而言：它不存在从哪里它
（2）对于其它所有节点而言：它们都是从各自的父节点沿着一条 “专用的路径” 而来。
在讨论到哪里去问题之前，我们先来理解一下什么是分支（路径）。
>>那么在决策树中什么是路径（分支）呢？
——如果将节点认为是分类问题，分支本质上说就是分类条件。
回想决策树的原理，不就是通过不断地考虑多方面的因素对某一个问题做出判断吗？（只不过我们给每个判断因素都叫做特征）然而天下大事必作于细，我们不能同时使用这么多的特征进行一次性判断，只能一个一个来。因此说一个特征就成为了一个分类问题，也就是分类节点，与之对应的特征的不同取值就是节点处的多个分支。
每次到达一个节点处，我们依据节点处特征的不同取值，对节点进行分支以生长出其子节点，子节点处继续着它们各自父辈的故事。直到某个时候，不满足人为干预的一些条件了，或者完美地完成分类了，这时子节点不再继续分支而成为决策树的叶子节点。
class ClassificationTree(object):
def ... # 已省略该类其它部分，请参阅列出的博客
...
def expand_node(self, data_set, depth, branch):
"""
递归拓展节点
【我的博客地址】：https://blog.csdn.net/qq_28550263/article/details/114967776
Parameters
----------
data_set: dict，该节点的数据集。键为特征名，值为该特征名对应的训练集数据。
labels: an Array-like object，当前标签集。根节点的标签集即原始训练集的标签集。
depth: int，上一节点的深度。根节点进来时从0开始。
branch: str or a num object，表示节点来时的路。
- 除了``根节点``外，其它的节点由于是由分裂而来，都有“来时的路”
- 根节点没有来处，只剩归途（分支）。
Return
------
result: dict， 表征当前节点（及其预期的子节点）的字典。
如果是``非叶子节点``在递归调用拓展节点后必须返回该非叶子节点给
其父节点。
这也就是说，这类字典是依次连接一个个从``根节点``到所有``非叶子
节点``的纽带。
"""
node = {} # 初始化节点
if depth == 0: # 仅根节点不属于任何分支，不需要记录来时的路
if self.test == False:
print('正在训练决策树，请稍后...')
else:
node['branch'] = branch # 对于非根节点，都需要记住来时的路
nodedepth = depth + 1 # 每递归一次节点的深度就在父节点基础上加1
labels = data_set["labels"] # 当前数据集的标签集
node_label = self.get_lable(labels) # 节点标签。非叶子节点也给一个标签，因为测试集的数据不一定是训练集见过的！
# 停止递归：这是一种极端条件，
# 目前是最后一个可用特征
# 即用于分类的特征已经用完了
# 在这种情况下，不论标签集是否只有一种标签都需要停止递归了。
if (len(data_set) == 1):
if len(set(labels)) == 1:
node['label'] = list(labels)[0]
else:
node['label'] = node_label
return node
the_best_feature = self.best_feature(data_set) # 获取最佳特征
bestfeature_values = list(set(data_set[the_best_feature])) # 最佳特征的多有取值
samples = len(data_set) # 当前节点的样本数，
#也就是节点数据集中标签集的元素个数
# 记录当前节点处的相关数据
node['depth'] = nodedepth # 记录当前节点的深度
node['the_best_feature'] = the_best_feature # 记录当前节点最佳特征
node['bestfeature_values'] = bestfeature_values # 记录当前节点的最佳特征取值，也就是节点分支名称们
node['samples'] = len(labels) # 记录当前节点处的样本数量
# 停止递归：所有特征的类别标签labels完全相同，这包含两种情况
# 一种是还有很多样本时已经被完美地分类
# 另外一种是，之前一直没有完成分类，直到现在都已经最后一个样本了
if len(set(labels)) == 1: # 如果只有一种类别了，无需分裂，已经是叶节点
node['label'] = list(labels)[0]
return node
# 停止递归：没有要求的足够样本数了
elif node['samples'] < self.min_samples_split:
node['label'] = node_label
return node
# 停止递归：到达最大分裂深度
elif node['depth'] >= self.max_depth:
node['label'] = node_label
return node
else: # 递归扩展节点
branchs = [] # 是该非叶子节点的branch容器
node['label'] = node_label # 非叶子节点的标签可以预防测试集中遇到未学习过的数据
for value in node['bestfeature_values']:
subdata_set = self.dividing_data_set( # 划分子数据集
data_set=data_set,
node_feature=node['the_best_feature'],
node_feature_value=value
)
child_node = self.expand_node(subdata_set, nodedepth, branch=value) # 递归调用
branchs.append(child_node)
node['branchs'] = branchs # 每个node的分支们装在一个列表里，
# 列表中装一个node字典就有一个分支
return node
def fit(self, x_train, y_train):
"""
训练模型
- x_train ： an Array-like object，为最初的训练数据集；
- y_train ： an Array-like object，为最初的标签集。
"""
assert len(self.features) == len(x_train[0]) # 输入数据的特征数目应该和模型定义时的特征数目相同
data_set = dict(zip(self.features,x_train.T)) # 转换为数据集字典
data_set.update({"labels":y_train}) # 将标签集（labels，也就是输出y们）也加入数据集
# 拓展节点：初始深度为0，到第一个节点自动先变1，递归拓展
self.tree = self.expand_node(data_set=data_set, depth=0, branch=None)
if self.test == False:
print('训练完成，可以使用show()方法展示决策树。')
如果不考虑剪枝，主要在以下两种停止分裂：
1）已经完美地完成了分类任务。
分类其实就是在用不同维度（角度）的特征来筛分标签集中的标签使得子标签集纯度越来越大，直到标签集中标签一致了，这时的标签就是最“纯”的了，自然结束分裂过程。
（2）虽然没有完成分类（标签集中有不同地分类标签），但是没有进行下一次分类的依据维度（分类特征）了。
这就是说没办法，现有维度还不足以对当前数据沿着当前分支进行分类，使得即使没有完成每类也造不出下一个节点了，毕竟每造一个节点是要以消耗一个特征为代价的。
假设我们不进行剪枝，那么决策树在完成分裂后将按照能够满足训练集数据所有几乎分类条件的方向生长，这就产生了所谓的”过拟合“。所谓”过拟合“指的是分类器能够拟合好某一些特定的数据而缺少泛化能力。机器学习的思想是，在已知的数据上进行学习，使得学习器在遇到相同或者近似任务的情况下相比于学习前解决该问题性能有所提升。但是必须指出，用训练集数据是来自于万千世界中数据一个及其小的样本集。
以样本集估计全集必然会产生误差，特别是当样本集在采样时受到各种干扰时。况且，样本集之所以称之为样本集，是它不可能包含全集中所有的样本。这意味着当我们的分类器从”学习“走向”实践“时必然将会遇到没有学习过的样本。所有这些都要求我们的机器学习器具有泛化能力。为了提升泛化能力，最直接的一个作法就是剪枝。
剪枝的本质上看，其实剪枝就是想要去掉一些对于学习器对于决策作用相对弱的一些条件，让决策不要过度细化。
常见的预剪枝方案包括基于分裂深度的预剪枝、基于样本数的预剪枝、基于信息增益阈值的预剪枝等。
1.所谓基于分裂深度的预剪枝，就是提前设定一个最大的分裂深度，一旦在训练决策树时只要在某个节点处深度达到最大深度则提前结束分裂。
2.所谓基于样本数的预剪枝，这里的样本数指的是在分裂过程中，随着数据集不断地被划分，在某个节点位置处剩余地样本数。该预剪枝提前设定一个最小继续分裂样本数，只要节点处剩余样本数比这个样本数还少就不再分裂新的节点以实现剪枝。
