决策树

2019-06-11 本文已影响0人 0xFFFFFG

Profile

Decision Tree,非参数的学习算法,可以解决分类问题,天然地解决多分类问题(类似KNN,不需要通过ovr或者ovo),也可以解决回归问题(先将待测样本分到某一个叶子节点,再将同一叶子节点下所有样本的平均值作为预测值),具有良好的可解释性

Example

eg.1 OFFER FOR ML ENGINEER

+发表过顶会论文?
- Y OFFER
- N + 是否是研究生?
  - Y + ML专业相关?
    - Y OFFER
    - N + GPA TOP10%?
      - Y OFFER
      - N INSPECT
  - N + GPA TOP10%?
    - Y OFFER
    - N INSPECT

Explanation of nouns

depth: 一次决策最多需要进行判断的次数

构建决策树

选一个维度
找到这个维度的一个阈值
以这个阈值进行划分

信息熵

一组样本的不确定性越高(混乱程度越高),则它的信息熵越高,一个系统的熵
$H=-\sum_{i=1}^{k}h_i \\ 其中h_i=\begin{cases} p_ilog(p_i) &p_i \ne 0\\ 0 &p_i= 0 \end{cases}$
eg.
$\left\{\frac{1}{3},\frac{1}{3},\frac{1}{3}\right\}$ 的系统中, $H=-(\frac{1}{3}log\frac{1}{3}+\frac{1}{3}log\frac{1}{3}+\frac{1}{3}log\frac{1}{3})=1.0986$
$\left\{\frac{1}{10},\frac{2}{10},\frac{7}{10}\right\}$ 的系统中, $H=-(\frac{1}{10}log\frac{1}{10}+\frac{2}{10}log\frac{2}{10}+\frac{7}{10}log\frac{7}{10})=0.8018$
$\left\{10^{-8},10^{-8},1-2*10^{-8}\right\} 的系统中,H=3.7841\times10^{-7}$
$\left\{0,0,1\right\} 的系统中,H=0$
对于二分类问题, $H=-plog(p)-(1-p)log(1-p)$

基尼系数

$G={1}-\sum_{i=1}^{k}p_i^2 \\$
G函数和H函数在[0,1]上具有相同的递增区间和递减区间,对于二分类二者的图像如下
横轴为概率p,纵轴为系数G或者H

20190611165304.jpg
信息熵的计算比基尼系数慢一些,sklearn默认使用基尼系数,二者通常没有特别的效果优劣

CART

Classification And Regression Tree(分类与回归树),根据某一个维度d以及某一个阈值v进行二分,最后得到的决策树一定是一棵二叉树,这种树叫做CART是sklearn的决策树实现方式,其他的实现方式还有ID3,C4.5,C5.0等
构造一棵CART的流程如下:

遍历样本的所有维度(d),在每个维度中遍历所有相邻点的中点(v),以d=v作为超平面将训练点分成X_left和X_right两份,分别对应y_left和y_right
计算每个每一组y_left和y_right的信息熵(或者基尼系数)H,取H得最小值,此时对应的d=v即为当前节点的决策超平面
递归处理X_left->y_left和X_right->y_right,直到节点的信息熵=0,此时这个节点作为叶子节点

复杂度

CART树预测时间复杂度为 $O(log(m))$ ,训练复杂度为 $O(n*m*log(m))$

决策树