决策树--从原理到Python实现

决策树基本上是每一本机器学习入门书籍必讲的东西,其决策过程和平时我们的思维很相似,所以非常好理解,同时有一堆信息论的东西在里面,也算是一个入门应用,决策树也有回归和分类,但一般来说我们主要讲的是分类,方便理解嘛。

虽然说这是一个很简单的算法,但其实现其实还是有些烦人,因为其feature既有离散的,也有连续的,实现的时候要稍加注意。

读一读

信息论的一些point:

(注:若看不清,可双击手机屏幕将图片放大)

然后加入一个叫信息增益的东西:

□.信息增益:(information gain)

g(D,A) = H(D)-H(D|A)

表示了特征A使得数据集D的分类不确定性减少的程度

□.信息增益比:(information gain ratio)

g‘(D,A)=g(D,A) / H(D)

□.基尼指数:

二.各种算法

1.ID3

ID3算法就是对各个feature信息计算信息增益,然后选择信息增益最大的feature作为决策点将数据分成两部分然后再对这两部分分别生成决策树。(注:若看不清,可双击手机屏幕将图片放大)

2.C4.5

C4.5与ID3相比其实就是用信息增益比代替信息增益,应为信息增益有一个缺点: 信息增益选择属性时偏向选择取值多的属性

算法的整体过程其实与ID3差异不大:

3.CART

CART(classification and regression tree)的算法整体过程和上面的差异不大,然是CART的决策是二叉树的每一个决策只能是“是”和“否”,换句话说,即使一个feature有多个可能取值,也只选择其中一个而把数据分类两部分而不是多个,这里我们主要讲一下分类树,它用到的是基尼指数:

三.代码及实现(注:若看不清,可双击手机屏幕将图片放大)

好吧,其实我就想贴贴代码而已…… 纯属toy~~~~~实现的CART算法:

这个maketree让我想起了线段树………………代码里的变量基本都有说明

试验代码:

四.reference

【1】:《机器学习》 -mitchell,卡耐基梅龙大学

【2】:《统计学习方法》-李航

(Via:CSDN博客 作者pi9nc)

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2015-05-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

通过嵌入隐层表征来理解神经网络

可视化神经网络总是很有趣的。例如,我们通过神经元激活的可视化揭露了令人着迷的内部实现。对于监督学习的设置,神经网络的训练过程可以被认为是将一组输入数据点变换为可...

692
来自专栏新智元

Ian Goodfellow最新论文:神经网络无比脆弱,对抗攻击重新编程

【新智元导读】对抗攻击通常会使得神经网络分类错误,但谷歌大脑团队的Ian Goodfellow 等人的新研究提出一个更加复杂的攻击目标:对神经网络重新编程,诱导...

780
来自专栏tiankonguse的专栏

图片上的算法之JPEG压缩

听了JPEG图片的压缩算法,发现蛮有意思的,这里通过JPEG的整体思想、色彩空间转换,缩减取样、DCT变换、量化以及熵编码技术分享一下心得。

4410
来自专栏量子位

听讲座的正确姿势:吴恩达1小时深度学习演讲精华笔记分享

允中 | 编译自Github 量子位·QbitAI 出品 吴恩达曾做了一次1小时19分钟的演讲:Nuts and Bolts of Applying Deep ...

3128
来自专栏专知

【NLP】十分钟快览自然语言处理学习总结

摘要:近来自然语言处理行业发展朝气蓬勃,市场应用广泛。笔者学习以来写了不少文章,文章深度层次不一,今天因为某种需要,将文章全部看了一遍做个整理,也可以称之为概述...

3577
来自专栏自然语言处理

十分钟学习自然语言处理概述

文本挖掘是信息挖掘的一个研究分支,用于基于文本信息的知识发现。文本挖掘的准备工作由文本收集、文本分析和特征修剪三个步骤组成。目前研究和应用最多的几种文本挖掘技术...

642
来自专栏机器学习算法与Python学习

DNN在搜索场景中的应用

2394
来自专栏新智元

【深度学习自动上色,数月工作几秒完成】开源神经网络图片上色技术解析

【新智元导读】本文是作者对Reddit社区用户Amir Avni深度学习上色机器人的实现,看完本文后,你也能打造媲美大师级着色效果的自动上色神经网络应用。此外,...

3797
来自专栏小詹同学

人脸识别(一)——从零说起

人脸识别的英文名称是 Face Recognition,前段时间查找资料学的时候发现,不少人将人脸识别和人脸检测(Face Detection)混为一谈,很大...

36510
来自专栏大数据文摘

代码实现! 教学视频!Python学习者最易上手的机器学习漫游指南

1513

扫码关注云+社区