实现三遍决策树,你就会想出更快的算法!

背景

决策树(Decision Tree)可以说是当下使用最为广泛的机器学习模型,任何一个刚刚学习人工智能或者数据挖掘的同学可能都接触过实现决策树的课程作业。

决策树的想法可以追溯到二十世纪60年代(Hunt's Algorithm),但是那个时候的计算机速度比现在慢好多个数量级,内存也很小,能做一些简单的方程求解就谢天谢地了。随着硬件计算能力的提升,也是到了90年代,决策树算法才真正逐渐走进更多的实践舞台。当时比较常见的决策树算法是ID3,C4.5和CART,这三个模型直到今天也被广发使用于各行各业。在我们今天的教程上,介绍的主流算法依然是这三个模型。

我个人最喜欢的模型是CART,其中tree pruning的办法非常精妙,每次复习到这里都会仔细体会一番先人的智慧。事实上,CART模型pruning的办法也被用于Variable-order Markov Model(生物信息经典模型之一)中variable-order state空间的pruning。我刚读博的时候发现我的co-advisor非常精通决策树算法和它的各种变体,我当时还十分诧异为什么她会如此了解,过了几年才意识到原来她读博的co-advisor就是CART的发明者之一。

在90年代,当时计算机的内存很小,IBM的科学家发现运行决策树算法的最大瓶颈是没法一次性把所有数据读进内存,于是研发了SLIQ算法。相比经典的递归实现,SLIQ是一个广度优先的决策树算法,它一层一层地来生成一棵树,每次生成新的一层需要遍历整个数据集两次。第一次用来寻找当前层所有最优的分割点,第二次根据找到的分割点,用来更新每个样本所在的叶子节点。

SLIQ算法同时也比传统的实现办法更快。这个没出现过在教程里的算法正是XGBoost里面使用的"exact" tree method的模块,Tianqi Chen在实现了SLIQ之后让XGBoost成了当时各大数据挖掘比赛又快又好的利器。到了今天,随着计算机硬件水平提升到新的高度,决策树算法的内存瓶颈逐渐弱化,单模型的计算速度和模型的复杂性和准确率逐渐变得更加重要。决策树的使用也逐渐从过去的单模型向集成模型(ensemble model)发展,Random Forest和Gradient Boosted Trees成了业界主流的两个集成模型。在这样的背景下,机器学习顶级会议NIPS最近几年依然会接受与提升决策树性能相关的文章。比如之前比较火的LightGBM就是高效实现了决策树的一种近似算法。

在这篇文章,我打算简要谈谈我过去三次实现决策树算法的经历和心得,以及我最近是如何发现一个新的又快又简单的决策树算法实现的。

第一次实现

第一次实现决策树是在大四的时候,用的语言是Matlab,当时在学习机器学习的基础内容。现在回想起来,自己当时实现的主要目的是为了重现一个正确的决策树算法,有很多实现细节都没有做到最优或者正确。比如在没有事先排序特征的情况下计算Gini index,在算法执行过程中对数据做了多份拷贝,没有实现tree pruning而只用了简单的termination criterion,以及duplicated values的处理等等。这些细节如果搞不清楚,实现出来的决策树会有很大问题,如果拿Matlab标准实现做一下对比,就会发现差异很大。

第二次实现

时隔三年,我在数据挖掘的课程上又有一次机会接触决策树的实现,这次是正儿八经的要实现CART。恰好当时我还在学习Scala,于是就用Scala写了一个决策树的实现。第一次实现过程中没有注意到的细节,这次都尽量体现出来。实际上,Scala的语言特性在很多时候会让实现变得更加方便,最终写出来大约也就200行的Scala code。

这次我还特别做了一个可视化的工具,可以用dot把整棵树画出来并用深浅的颜色标注reSubstition error。

具体的介绍可以参考:bobye/scalaCART

转自:豆豆叶

本文来自企鹅号 - 机器学习研究会媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技评论

干货 | 清华大学冯建江:指纹识别现状与研究进展

AI 科技评论按:2018 年 4 月 14 日-15 日,中国图象图形学学会围绕「生物特征识别」这一主题,在中科院自动化所举办第四期「CSIG 图像图形学科前...

38340
来自专栏云时之间

NLP入门之语言模型以及n元文法

各位小伙伴们大家好,在接下来的文章中我们将讲述一下什么是语言模型,以及语言模型上的应用,在完善之后我们将会简单的讲解一下语言模型的性能评估,这三点将是这一篇文章...

35290
来自专栏PPV课数据科学社区

空间数据挖掘常用的17种方法

PPV课大数据学习社区如果你对大数据感兴趣;如果你想转行做大数据;如果你想了解大数据是怎么改变我们生活,请点标题下蓝字关注PPV课大数据 ? 问题1:空间数据挖...

40990
来自专栏华章科技

【知识】人工智能数学基础知识

数学基础知识蕴含着处理智能问题的基本思想与方法,也是理解复杂算法的必备要素。今天的种种人工智能技术归根到底都建立在数学模型之上,要了解人工智能,首先要掌握必备的...

40120
来自专栏大数据文摘

论文Express | 把你的口哨变成莫扎特风,Facebook发布通用音乐迁移网络

20440
来自专栏新智元

Yoshua Bengio最新演讲:Attention 让深度学习取得巨大成功(46ppt)

【新智元导读】机器翻译是深度学习技术最切近实际的应用之一,现在在互联网上有很广泛的使用。此外,不久前,许多科技大公司也相应地推出了为图片或视频自动生成字幕的应用...

42240
来自专栏斑斓

掌握一点儿统计学

对于数据分析师而言,统计学必定是一门绕不开的学科。我今生做数据科学家已经无望了,但就工程角度来讲,致力于大数据行业,了解一些必备的统计学知识仍有必要。Data ...

35360
来自专栏云时之间

NLP入门之语言模型以及n元文法

各位小伙伴们大家好,在接下来的文章中我们将讲述一下什么是语言模型,以及语言模型上的应用,在完善之后我们将会简单的讲解一下语言模型的性能评估,这三点将是这一篇文章...

48450
来自专栏机器之心

EMNLP 2018 | 用强化学习做神经机器翻译:中山大学&MSRA填补多项空白

作者:Lijun Wu、Fei Tian、Tao Qin、Jianhuang Lai、Tie-Yan Liu

18510
来自专栏数据科学与人工智能

【知识】人工智能数学基础知识

数学是打开科学大门的钥匙。——培根 数学基础知识蕴含着处理智能问题的基本思想与方法,也是理解复杂算法的必备要素。今天的种种人工智能技术归根到底都建立在数学模型之...

35770

扫码关注云+社区

领取腾讯云代金券