决策树

本文部分图片、材料来自于课程Python3 入门机器学习

先来看一个招聘的例子，这就是一颗决策树，根据不同的问题进行一步步划分，最终将结果氛围录用和考察两类

决策树实例

采用sklearn的决策树算法包，见What-is-Decision-Tree

决策树的特点

• 非参数学习方法

• 可以解决分类问题

• 天然可以解决多分类问题

• 也可以解决回归问题

• 具有非常好的可解释性

关键问题

• 每个节点在哪个维度做划分

• 某个维度在哪个值上做划分

信息熵

熵在信息论中代表随机变量不确定度的度量

• 熵越大，数据的不确定性越高
• 熵越小，数据的不确定性越低

$Entropy(S) = -\sum p_ilog(p_i)$

二分类问题的信息熵效果图，当两个分类的p都为0.5时，信息熵最大，数据越不稳定

基尼系数

$G = 1 - \sum_{i=1}^{k}p^2_{i}$

同信息熵类似，G越大表示样本的不确定性越强，反之则表示样本的分类没有任何不确定，最小值为0

以二分类为例，其函数图像为开口向下的抛物线

np.argsort()将np.array中的值从小到大进行排序，按照此顺序依次返回元素在元数组中的index

Counter参数为list，求出列表中值的出现次数

信息熵VS基尼系数

• 信息熵的计算比基尼系数稍慢
• scikit-learn包中默认参数为基尼系数
• 大多数时候二者没有特别的效果优劣

CART(Classification And Regression Tree)

scikit-learn的决策树实现：CART

复杂度

• 预测： $O(logm)$
• 训练： $O(n*m*logm)$
• 剪支： 降低复杂度，解决过拟合

超参数

避免过拟合、欠拟合

• max_depth： 限制最大深度为2
• min_samples_split： 至少要有多少个样本数据才继续拆分下去
• min_samples_leaf： 对于叶子结点来说最少要有几个样本
• max_leaf_nodes：最多有多少个叶子节点

可以用网格搜素寻找合适的参数

决策树解决回归问题

决策树的局限性

• 决策边界只能是横平竖直，不能倾斜
• 不能学习参数
• 对个别样本比较敏感，可能会很大影响决策树

每天都汇报投了哪几个单位