决策树

作者: 0xFFFFFG | 来源:发表于2019-06-11 18:03 被阅读0次

机器学习6-决策树
决策树
决策树
决策树算法总结
机器学习 - 决策树算法[一]
机器学习系列（三十六）——回归决策树与决策树总结
[机器学习]决策树
经典机器学习系列之【决策树详解】
第5章决策树
决策树与随机森林

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))$

机器学习6-决策树
一. 决策树概述 1.1 什么是决策树决策树输入: 测试集决策树输出: 分类规则(决策树) 1.2 决策树算法概...
决策树
1、决策树决策树学习通常包括3个步骤：特征选择。决策树生成。决策树剪枝。决策树的学习目标是：根据给定的训...
决策树
决策树决策树模型与学习特征选择决策树的生成决策树的剪枝 CART 算法决策树模型呈树形结构，在分类问题中...
决策树算法总结
目录一、决策树算法思想二、决策树学习本质三、总结一、决策树（decision tree）算法思想：决策树...
机器学习 - 决策树算法[一]
1 决策树模型与学习 1.1 决策树模型决策树定义：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由...
机器学习系列（三十六）——回归决策树与决策树总结
本篇主要内容：回归决策树原理、回归树学习曲线、决策树总结回归决策树原理回归决策树树是用于回归的决策树模型，回归...
[机器学习]决策树
决策树 @(技术博客)[机器学习, 决策树, python] 学习决策树首先要搞清楚决策树是什么（what），在弄...
经典机器学习系列之【决策树详解】
这节我们来讲说一下决策树。介绍一下决策树的基础知识、决策树的基本算法、决策树中的问题以及决策树的理解和解释。 ...
第5章决策树
内容一、决策树内容简介二、决策树的模型与学习三、特征选择四、决策树生成五、决策树剪枝六、CART算法 ...
决策树与随机森林
PART I 决策树 (Decision Tree) 决策树基本知识决策树何时停止生长：(I) all leaf...